Research And Application Of Pseudo-Parallel Genetic Algorithm To Solve The VRPSTW

Distribution plays an important role in logistic system, and takes account for considerable proportion in variable costs in logistics. The planning of vehicle routing in distribution will take great effect on the efficiency, cost and benefit, especially in distributing for multi consumers. So, vehicle routing problem had become focus of many scholars to study. In the developed commercial sosciety, requirement of consumer for delivery time is higher and higher so that delivery day formerly had turned to delivery hour now. With popularization of Internet and development of Supply Chain Management, E-Commerce and information technology, the lagged logistic management becomes an emergent issue. In order to quench the versatile requirements of the customers, many decision-makers of enterprises and researchers have shown great interests in decreasing the transportation cost by efficient routing and scheduling.Vehicle Routing Problem is the key question and one of research hot spots in the Logistic distribution system. A reasonable routing arrangement can largely improve the transportation efficiency and reduce the service cost. With a new trend of more kinds, less batchs, high frequency and time restriction in materials distribution, the optimizations of the delivery route become more and more complicated.This paper gives a review of the past researches on vehicle routing problems and their solution methods. On the base of reality, we purpose the research problem —vehicle routing problem with soft time window (VRPSTW). Meanwhile.We construct a mathematical model: defines an objective function and constraints mathematically then solves it based on Sweep Algorithms and Pseudo-Parallel Genetic Algorithm (PPGA). An initial solution is constructed by the Sweep heuristic. Then PGA is used to improve it to acquire a best or better solution. We propose coding strategy, fitness function and three genetic operations when using PGA. Considering the disadvantage of 'Premature' commonly in GA, the Parallel of GA is applied during the evolution process. In the PGA, the optimum value in everyparallel is changed each other in proper time in order to overcome the phenomenon of 'Premature' and improve the performance of GA.Finally, this method is implemented on computer in VC++. The result proves the PGA is a efficient way to slove the VRP.