Research On Vehicle Routing Problem With Time Window Based On Improved Adaptive Large Neighborhood Search Algorithm

With the rapid development of the transportation and logistics distribution industry,logistics enterprises are gradually able to meet the service time requirements specified by merchants or customers.The vehicle routing problem with time windows is widely used in real life,such as logistics distribution,takeaway delivery,school bus pickup,shuttle bus pickup,and mail collection.Through the fast and accurate optimization algorithm,according to the needs of users,the logistics enterprises can be provided with the best distribution scheme under the premise of ensuring the logistics efficiency,so as to achieve the goal of reducing the total transportation cost and the number of delivery vehicles.In this paper,on the premise of fully considering the constraints in the process of urban commodity distribution,such as the customer point time window,the load of distribution vehicles,the maximum transport distance of distribution vehicles and so on,the FSMVRPTW model is established,in which the first optimization objective is to minimize the total transport cost and the second optimization objective is to minimize the number of distribution vehicles.By designing six kinds of destruction operators and six kinds of repair operators,the operator selection pool of ALNS algorithm is enriched,and the scoring strategy and operator selection strategy of ALNS algorithm are improved,which further expands the search ability of ALNS algorithm in solving large-scale customer node problems.The main contents of this study are as follows:(1)This paper introduces the research background of the vehicle routing problem with time window,and understands and grasps the research significance of VRPTW from both theoretical and practical aspects.Summarize the research status of various types of vehicle routing problems and corresponding solving algorithms at home and abroad.(2)According to the characteristics of the actual distribution problem,the optimization goal is determined.Identify the key elements that affect path planning decisions,fully consider multiple constraints involving key elements in VRP,and linearize nonlinear relationships between variables during the research process.Finally,a mathematical model of multi-vehicle,multi-cost and multi-optimization target VRP with time window is established.(3)The principle,advantages and disadvantages of the classic ant colony algorithm and neighborhood search algorithm are introduced,and the improved design is carried out.The ALNS algorithm is introduced to solve the VRPTW,the construction method of the initial solution based on the mileage saving method is introduced,and the basic framework of the ALNS algorithm,the simulated annealing acceptance criterion,the classical removal operator and repair operator,the weight update method in the adaptive layer and the termination condition of the algorithm.At the same time,according to the characteristics of the problem,the algorithm is improved,and new removal operator and repair operator,scoring strategy and operator selection strategy are designed.(4)The basic situation of Solomon,Gehring & Homberger benchmark sets in the international public data set and the known optimal solution submission platform are introduced,and the optimal parameter values of the improved ALNS algorithm determined by the control variable method are given.Comparing the results of the improved ALNS algorithm,the hybrid ant colony algorithm,and the neighborhood search algorithm,the experimental results show that the solution results of the improved ALNS algorithm are better than the known optimal solutions,and show strong applicability in solving VRPTW.At the same time,in some large-scale customer point experiments,the algorithm calculation results are better than the known optimal solutions submitted by the Cainiao network warehouse allocation intelligent algorithm team.