The Research Of Genetic Algorithm For Vehicle Routing Problem

Vehicle Routing Problem (VRP), which is a NP-complete problem of combinatorial optimization realm, is a hotspot topic in the subjects of operational research, application mathematics, analysis of networks, theory of chart, computer application and transportation during the latest twenty years.Genetic algorithm for VRP is studied in this thesis. Firstly, vehicle routing problem in the case of specific demand is studied. According to internal characteristic of genetic algorithm, a good or a bad method of building initial colony will influence its performance capability seriously. In chapter 2, a genetic algorithm for VRP with multi- type fleet base on petal decomposition and a novel crossover operator is put forward. Experiment result indicates that the satisfying scheme of VRP is acquired quickly. In chapter 3,a genetic algorithm for VRP with multi-type and time windows is studied. The satisfying scheme of VRP is acquired also.During the realistic application process of vehicle routing problem, demand of customer is stochastic usually. In chapter 4, VRP in case of stochastic demands is analysed in detail. The model of VRP in case of stochastic demands is constructed. What's more, a self-adapt genetic algorithm is put forward.Because vehicle routing problem is a NP-complete problem of combinatorial optimization realm, it is very significant to construct a high effective parallel algorithm. A master-slave scheme parallel genetic algorithm based on coarse granularity for VRP is put forward in chapter 5.Finally, a tentative plan for next work is put forward.