Research On Optimization Methods And Strategies Of Large-scale Vehicle Routing Problems

Vehicle Routing Problem(VRP)is a practical classic optimization problem in logistics industry.With the rapid development of logistics industry in China,the optimization of VRP becomes more difficult as the scale of the problem increases,and the optimization goals and demands become more complicated.The article studies the large-scale vehicle routing problem in China's carrier industry.Based on the real problem scale,objectives and constraints,this paper established effective optimization methods to improve the logistics operation efficiency of related industries,reduce operating costs and improve service quality.Most studies on vehicle routing problems are based on classical instances.The classic instances are aimed at minimizing the number of vehicles and the total travel distance;and only use a single optimization strategy,which cannot meet the complex needs;the default driving speed is constant in all areas of the city,ignoring the optimization of travel time;in addition,in the classical instances,only the late arrival time window is limited,and vehicles are allowed to arrive early.However,in real scenes,early arrival waiting time and late arrival delay time are both the key factors that affect operating costs and service levels.At the same time,the scales of these classic instances are relatively small,and the daily operation scale of the carrier industry is often as many as 300 points.Based on the real needs of a big carrier company in China,this paper modelled a large-scale vehicle routing problem with multiple objectives and constraints in the industry,with the goal of minimizing the number of vehicles,total working time and total travel distance,while considering satisfying the vehicle capacity,early time window,late time window and other constraints.However,the problem is difficult to solve because of the large scale and multiple constraints,therefore,the classical artificial bee colony algorithm(ABC)and variable neighborhood search algorithm(VNS)perform generally in terms of optimization results and efficiency.In order to further improve the optimization effect of the meta-heuristic algorithms,this paper innovatively proposed a hybrid algorithm based on clustering algorithm and metaheuristic algorithm.Specifically,we proposed that using the K-means clustering algorithm to provide honey sources(initial solutions)for the artificial bee colony algorithm,instead of using randomly generated honey sources.The classic K-means algorithm only focuses on the similarity in geographic location,and is not applicable to VRP with time windows.This paper specifically improved the clustering algorithm by adding time window.The experimental results showed that the new artificial bee colony algorithm is superior to the traditional artificial bee colony algorithm in objective value and operation efficiency.Similarly,the initial solution obtained by the K-means clustering algorithm can also effectively improve the optimization effect of the variable neighborhood search algorithm.Finally,for the complex and diverse needs of the carrier industry,this paper proposed three different optimization strategies,namely cost minimization strategy,work time balancing strategy,and emergency response strategy.They have good performance in reducing costs,reducing the risk of being robbed,and responding to emergencies.