Particle Swarm Optimization For Vehicle Routing Problem And Its Application

Logistics, which is regarded as "the third profit source", has obvious impact on economic activity of the world day by day, and cause people's more and more attention too. Transportation and delivery is the key part in the logistics, 60% of all the logistics cost. Vehicle routing problem (VRP), which is research on how to plan the vehicles routes in order to save the transportation cost, is the well known NP problem in the field of operation research and combination optimization. It has been applied to many fields, such as flight scheduling, train organizing. VPR have many models because of its many constraints, such as custom, network and vehicle type. For NP complexity, the polynomial method has not been found now, so most researchers concentrate on the research of heuristic method.The dissertation mainly studied four VRP models: capacity vehicle routing Problem (CVRP), Open Vehicle Routing Problem (OVRP), the Customer Satisfaction Vehicle Routing Problem (CSVRP) and the Time Dependent Vehicle Routing Problem (TDVRP). The main contributions of the paper are as follows:(1) First the research background and significance of the thesis is introduced, and the definition of vehicle routing problem is given. The composition elements of Vehicle routing problem is analyzed. Then based on summing up a large number of domestic and foreign literatures, survey the status of vehicle routing problem deeply from the model and algorithms. Open vehicle routing problem and time dependent vehicle routing problem as hot issues are discussed detailedly.(2) The CVRP is deeply and systematically studied based on Particle Swarm Optimization. Two encoding methods: integer encoding and real number encoding are presented. In the integer number encoding, based on the "exchange number", the velocity of the particles is redefined, and various operator of velocity is defined. "Exchange minus operator" is constructed to compute particle's velocity. In the real number encoding, the vehicle is mapped into the integer part of the real number; and the sequence of customers in the vehicle is mapped into the decimal fraction of the real number. The crossover operator is inducted to improve the diversity of the population. The impact of various parameters for the result is discussed detailedly. For the sake of comparing with other intelligent algorithms, Genetic Algorithm and Artificial Fish School Algorithm are studied. Double Genetic Algorithm is presented for CVRP, and two populations is initialization, each has its probability of crossover and mutation, and the two populations exchange the better chromosome. It can break the balance of inter-population in the local minimization, increase the diversity of the population, escape the local minimization. For Artificial Fish School Algorithm, some definitions and rules when the AFS A algorithm is applied into combination optimization problem is presented. The operation rules of AFSA for VRP are presented, method of encoding, behavior evaluation and so on. The computational complexity of these algorihtms are analyzed and the parameters of algorithms are discussed through experiments.(3) The mathematical model of Open Vehicle Routing Problem is founded, and Particle Swarm Optimization combined the global search and local search algorithms are presented. Several heurist methods are applied into the post-optimization procedure,such as 2-Opt,3-Opt, Nearest Insertion Algortihm. They are used to optimize the inner or outer routes and modify illegal solutions. The computational complexity of these algorihtms are analyzed . In the experiments, the performance of the proposed post-optimization algorithm is analyzed and the particle swarm optimization algorithm is compared with other heuristic methods.(4) The multi-objective vehicle routing problem to optimize both customer satisfaction and the transportation cost is proposed. The customer satisfaction is denoted by trapezia fuzzy number. The improvement Nearest Neighbor Algorithm and Cheapest Insertion Algorithm are presented. The general cost is defined, which is included customer satisfaction, distance, waiting time and other factors. The two algorithms hybrid PSO is proposed to solve the problem. The complexity of the algorithm and the algorithm's parameters are discussed. Finally, in the experiments, these algorithms are analyzed and compared.(5) Time dependent vehicle routing problem is more complex than other VRPs, because its travel cost changed with the time. In the paper, the mathematic model of the problem is founded, and a continuous function is presented for the time dependent network model. The auto-adapt parameter of PSO is presented. Each particle's parameterωcan auto-adapt regulate according to the fitness changing. At the same time, call-board policy is introduced in the algorithm, and the particle update its position according to the fitness. For the better particle, a new updating fomula is applied,and for the inactivity particle, they are displaced by the new particles. In the experiment, the parameters of the algorithm are discussed detailedly, and the result show the algorithm is efficiency.(6)Based on the above the academic research, an intelligent vehicle routing system based on the 3rd party logistics industry is developed. The system include the following functions, such as vehicle scheduling, route planning, delivering order building, electronic map display, and basic information manager. The system supports the models of CVRP, VRPTW, and provides the genetic algorithm, particle swarm optimization and so on. The system has been applied in a 3rd party logistics company, and have favourable economic benefit.