Research On Vehicle Routing Problem With Time Windows Based On Improved Ant Colony Algorithm

With the development of society,the logistics industry in our country has become an important part of the national economy.However,the development of logistics in China has the problems of high cost and low efficiency.Logistics distribution is an important part of the logistics industry.Optimizing logistics distribution path is the key to reduce logistics transportation cost and promote logistics development.The vehicle routing problem with time windows(VRPTW)is an important problem in planning logistics service routes,which has important practical significance and practical value.The research of VRPTW algorithm can not only reduce the cost of logistics transportation,but also improve the efficiency of logistics distribution,promote the development of the industry and social progress.In this paper,the classic VRPTW problem is studied firstly.On this basis,the algorithm of the fleet size and mix vehicle routing problem with time windows(FSMVRPTW)and the dynamic vehicle routing problem with time windows(DVRPTW)are studied respectively.The main contents of the study are as follows:(1)An improved hybrid ant colony optimization algorithm(IHACO)is proposed for solving VRPTW problems of large-scale customers.At first,IHACO improves the efficiency of ant colony selection by adopting the surrounding selection strategy,and proposes a first node selection strategy to accelerate the convergence of the algorithm;secondly,it adds a penalty function related to the number of vehicles on the pheromone superposition formula,so that the algorithm optimizes the number of vehicles while optimizing the distance;finally,it mixes an insertion algorithm with 2-interchange to improve the search ability and vehicle benefit of the algorithm utilization rate.In the experimental part,six problems are selected from the Solomon data set to test the algorithm.The average results show that the total distance between IHACO and HACO is reduced by 25.0%,and the number of vehicles is reduced by 28.4%.(2)In view of the shortcomings of IHACO 's inability to select vehicle types efficiently in the face of multiple vehicle types,this paper proposes an improved algorithm(FSM-ACO)by combining IHACO with parallel split reconstruction strategy.FSM-ACO constructs the initial solution with the maximum capacity of vehicle type as the constraint,to reduce the number of vehicles in the initial solution.Then,based on the principle of the highest vehicle utilization,part of the routes is divided into lines and customer sets with lower model cost and the highest vehicle utilization.Then,the parallel insertion heuristic algorithm is used to integrate the factors such as time window width,driving distance,vehicle utilization,vehicle cost and so on to insert the split customers into other paths to realize the reconstruction of the solution.In the experimental part,12 questions on the standard data set are selected for testing.Compared with the improved algorithm,FSM-ACO reduces the average distribution cost by 16.06%,and improves the convergence speed of the algorithm.(3)In this paper,DVRPTW is studied from two aspects: solution strategy and solution algorithm.In the aspect of solving strategy,emergency order strategy and target customer strategy are used to solve the basic time slice method to solve DVRPTW,which has the disadvantages of poor ability to deal with emergency customers and unstable transition of scheduling scheme in adjacent time slices.In the aspect of solving algorithm,aiming at the low efficiency of IHACO in DVRPTW,the pheromone protection strategy is adopted to save the high-quality sequence information in each stage,which improves the efficiency of the algorithm.In the experimental part,the 10 test problems selected from the Lackner standard data set are tested.The results show that the average distribution distance of the algorithm in this paper is 27.4% lower than that of the algorithm before improvement.