Research On Multi-objective Optimization Method For Vehicle Routing Problem With Time Windows

The routing problem widely exists in practical applications such as logistics scheduling,and the time window is a necessary consideration in the route planning problem.With the enhancement of people’s awareness of environmental protection and the response to the "dual carbon" policy,carbon emissions are also being considered by more and more researchers in route planning.Energy saving and emission reduction and time windows have gradually become two important considerations in the routing problem,and the vehicle routing problem has also produced many variants: such as the vehicle routing problem considering the location of gas stations,and the vehicle routing problem considering the charging of electric vehicles.Taking the time window and carbon emission as the starting point,this paper conducts a series of researches on the path planning problem,such as modeling,optimization,algorithm design and comparison.The main research contents and innovations are as follows:1.For the problem: Based on the traditional pickup and delivery routing problem,according to the characteristics of the problem,a vehicle time window model and carbon emission model that meet this problem are established.According to the classification of customer points in the model,an area division method is designed to allocate time windows for different customers.In order to solve the problem of capacity constraints in the process of vehicle dispatch,a corresponding capacity constraint processing algorithm is proposed based on the improvement of the algorithm code.This paper optimizes and analyzes the model based on the NSGA-II algorithm.The experimental results show the accuracy and applicability of the established model.Finally,in order to facilitate the subsequent verification of the algorithm designed in this paper,on the basis of the established low-carbon belt time window vehicle model,this paper expands the optimization objective and city scale,and designs a multi-dimensional and multi-scale vehicle model.A low-carbon vehicle routing model with time windows.2.For algorithm architecture: Kn EA is a multi-objective optimization method based on inflection point to improve solution set domination,which has the characteristics of high convergence and excellent distribution.In this paper,the Kn EA algorithm is used to optimize the model.In the optimization process,the algorithm is prone to long-tail effects in order to maintain diversity.However,in the consideration of practical application problems,the point with high convergence has met the needs of decision makers for the diversity of solution sets.Therefore,in order to better address the application problem,this paper designs a vector-guided adaptive Kn EA algorithm（Vk EA）.The algorithm updates the vector in real time by supervising the target decline state in the algorithm optimization process,so as to indicate the most potential evolution direction for the population at the next moment.At the same time,on the basis of the vector,a dynamic knee point generation method based on the neighborhood size is proposed,which further improves the population convergence ability from the selection of the guiding solution.In this paper,the designed Vk EA algorithm and the traditional multi-objective optimization algorithm are verified on the established multi-dimensional and multi-scale vehicle routing model.The experimental results show that the designed Vk EA algorithm has good convergence and distribution in the high-dimensional large-scale vehicle routing problem.3.For the search operator: The search operator is an important part of the path optimization algorithm.Traditional combinatorial optimization directly conducts cross-mutation for individuals including all routes,and the search operator is single.In the routing problem,there are shortcomings such as insufficient preservation of excellent routes and weak later search.In this paper,a single route is used as the search unit,aiming at the low-carbon vehicle route planning model with time window,and according to the route state in the actual situation,five kinds of route search operators are proposed to improve the route.In order to better determine the operator’s insertion position,a corresponding operator re-insertion strategy is designed to search the insertion position.Finally,since different operators have different search performances before and after evolution,in order to better determine the use stage of operators,this paper designs a dynamic selection and invocation of search operators based on operator improvement probability.In this paper,the use parameters,use scenarios and use effects of the designed search operator are determined through experiments,and the proposed search operator is combined with the Vk EA algorithm to compare the traditional optimization algorithms in the multi-dimensional and multi-scale vehicle routing optimization model.The experimental results show that the new algorithm has a good effect on solving the vehicle routing problem.