Solving Vehicle Routing Problem With PBIL Algorithm

Logistics industry is the third most important source of national economic development, especially in the 21st century, the development of modern logistics industry is strongly advocated. Vehicle routing problem is the key to modern logistics, and the research on vehicle routing problem has important theoretical and economic significance. Dantzing and Ramser first proposed vehicle routing problem (VRP) in 1959. Now VRP has been the research hotspot for many experts in the subject areas of operations research, and it has been applied in mathematics and computer applications etc. VRP problem can be divided into a plurality of scheduling problems based on different constraints. The earliest research is on asymmetric TSP problem (ATSP); more research is on vehicle routing problem with capacity (CVRP); research combined with the actual closely is vehicle routing problem with soft time windows (VRPSTW). VRP problem has been proved with a NP-hard property,and have a high significance in theory and application. Traditional exact algorithms can not solve such large-scale problems, therefore we need to use intelligent algorithms to obtain better solution. Population-based incremental learning algorithm (PBIL) is one of estimation of distribution algorithms (EDA), which have unique probabilistic model, and the method can guide the detailed search in the quality solution space. In This paper, some algorithms based on population-based incremental learning algorithm are proposed in order to solve TSP,VRP,VRPTW problem.(1)For the ATSP problem, a new PBIL algorithm is proposed. The binary coding mode in traditional PBIL is converted into a decimal coding mode so that it reduces encoding conversion process, by use of a new way to update the learning probability matrix, and the search efficiency of the algorithm is improved.(2)For the problem with capacity constraints, the learning probability update mode in (1) PBIL algorithm is improved so that it makes global search more ccurate and effectiveand, and algorithm combined with local algorithm is robust.(3)For the problem with soft time windows, two types of selections,which are uniform distribution and roulette, are assimilated into the (2) PBIL algorithm,and 2-opt and Insert local search are added, In addition, a three-dimensional probability matrix is designed to balance global and local search and the effectiveness and efficiency of the algorithm are all improved.Finally, the results of simulation tests show that these proposed algorithms are effective.