Research On Vehicle Routing Problems Of Logistics Distribution Based On Improved Ant Colony Algorithm

This paper studies vehicle routing problem(VRP) in the logistics distribution. Through introducing some constraints, the models are more suitable to actual circumstances. Then, algorithms for them are proposed. Simulations show the validity and effectiveness of these algorithms. The study includes the following aspects:First, We give the survey of the current research on vehicle routing problem at home and abroad. The deficiencies in the current research are noted. After introducing some constraints, such as capacity, distance, time window and simultaneous delivery and pickup, the mathematical models of extensional VRPs are established. Cases studies verify the validity of models. Second, the paper summarizes a variety of solving methods for VRP, including exact algorithms, traditional heuristic and modern heuristic algorithm. Specially, analysize the research condition of ant colony algorithm (ACA) in detail. Third, the paper concentrates on improvement of ant colony algorithm. After analyzing the relative important parameters and classic improved ant colony algorithms, two improved algorithms are proposed. One is the double level ant colony algorithm based on density clustering (DLACADC) for large-scale VRP. The other is hybrid ant colony algorithm. Finally, the proposed ant colony algorithms are applied to the vehicle routing problem. However, vehicle routing problem is very complex, including a variety of extensional problems, and solution methods for different kinds of vehicle routing problems show great difference. So, we must design algorithm combined with specific problems. This paper analysizes representative vehicle routing problems,including capacitated vehicle routing problem, vehicle routing problem with time window,vehicle routing problem with simultaneous delivery and pickup, and multi-objective vehicle routing problem.The improved algorithms are compared with other algorithms through cases.The main innovation works of this paper are as follows:(1) Double level ant colony algorithm based on density clustering is proposed for large-scale VRP. Through clustering client nodes, the large amount of actual clients are divided into a small amount of virtual clients nodes, thereby the size of problem is reduced.(2) Hybrid ant colony algorithm is proposed. Through introducing the genetic operators (such as mutation and crossover), an improved hybrid ant colony algorithm is proposed.(3) New state-transfer rule is proposed. The algorithm introduces time-window width and waiting time of customers into state-transfer rules of VRPTW to give priority to those urgent customers. New rule ensures feasibility of solution.(4) The mathematical model of multi-objective vehicle routing problem is established. After introducing goals, such as the number of vehicles, distance and Clients’ satisfaction,the mathematical model of multi-objective vehicle routing problem is established. Sub-goal multiplication and division is adopted to evaluate the obtained solutions and pareto optimal solutions are obtained.