Application Of Hybrid Differential Evolution Algorithm In Multi-objective Vehicle Routing Problem

Logistics distribution is an important part of the transportation industry,vehicle routing problem is the most basic problem in logistics distribution.With the development of society,the vehicle routing problem with single objective optimization can not meet the actual market demand.Therefore,the vehicle routing problem with multi-objective optimization has gradually become the focus of logistics distribution.On the basis of optimizing the number of vehicles and driving distance,at the same time,ensuring high-quality service to customers and reducing environmental pollution in the process of transportation have also become the criteria of logistics transportation.Therefore,in this paper,considering the actual conditions such as vehicle load,running time and vehicle arrival time in the process of logistics distribution,the optimization objectives of carbon emissions,customer satisfaction,driving distance and the number of vehicles used in the process of vehicle transportation are studied to realize the multi-objective optimization of vehicle routing problem.The modeling of multi-objective vehicle routing problem includes:(1)the multi-objective vehicle routing optimization problem considering customer satisfaction is established.The multi-objective mathematical model is established to minimize the number of vehicles and vehicle distance,and maximize customer satisfaction.The maximum transportation time limit,time window and vehicle load are considered as constraints.(2)Considering the multi-objective vehicle routing problem of carbon emissions and customer satisfaction,a multi-objective mathematical model with the minimum carbon emissions,the maximum customer satisfaction and the minimum number of vehicles is es Tab.lished.The maximum transportation distance,the number of vehicles and the time window are considered as constraints.Aiming at the algorithm design of multi-objective vehicle routing problem,a hybrid differential evolution algorithm combined with variable neighborhood local search is proposed.The algorithm uses the method of vehicle random loading to generate the initial population,and introduces the arena rule to make the chromosomes in the population compare and judge one by one,so as to preliminarily construct the Pareto non dominated solution set;Furthermore,an alternative mutation operator is designed to increase the number of different solutions to ensure the diversity of the population;Secondly,in order to avoid that the crossing parents are the same and can’t produce new children,a crossover operator with random crossing points is constructed;Finally,aiming at the problem that the traditional differential evolution algorithm is easy to converge prematurely and fall into the local optimum,combined with the local search strategy of variable neighborhood,two neighborhood structures are proposed to balance the local optimization ability of the algorithm.An example is analyzed and compared with NSGA-Ⅱ algorithm which is commonly used to solve multi-objective vehicle routing problem.The results show that the frontiers of Pareto solutions obtained by this algorithm are well distributed and have more optimal solutions.The average route customer satisfaction is improved by 3.1%,and the average driving distance and the number of vehicles are reduced by 6.8% and 5.4% respectively.For the multi-objective vehicle routing problem based on customer satisfaction,the proposed algorithm can quickly find the route with the maximum customer satisfaction,the minimum number of vehicles and the shortest distance,and compare with the average value of each objective to find an optimal compromise route;For the multi-objective vehicle routing problem considering carbon emissions,customer satisfaction and the number of vehicles used,this algorithm can still find the route with the minimum carbon emissions,the maximum customer satisfaction and the minimum number of vehicles used,and has good optimization results.