Multi-objective Vehicle Route Planning Based On Non-dominated Sorting Genetic Algorithm

Vehicle routing planning is one of the most important problems in logistics field.It is multi-constraine and multi-objective combinatorial optimization problem.In recent years,NSGA-? has been used to deal with multi-objective vehicle routing problem.However,when NSGA-?'s congestion distance-based selection strategy is faced with three or more objective optimization problems,the solutions obtained are unevenly distributed in the non-dominant layer,the convergence and diversity of the algorithm are not good,and the algorithm is easy to fall into local optimum.At present,the constraints and solving objectives involved in vehicle routing planning in logistics field are becoming more and more complex,and the effect of vehicle routing planning based on NSGA-? needs to be improved urgently.In view of the above shortcomings,this paper explores an improved vehicle routing method based on non-dominated sorting genetic algorithm.The main research contents are as follows:(1)Constructing multi-objective vehicle route planning mathematical model.The model takes vehicle capacity constraints,single loop constraints,time window constraints and other factors as constraints,and optimizes vehicle scheduling path with the objective of the number of transport vehicles,scheduling distance and customer service satisfaction level.At the same time,the road congestion is analyzed,and a dynamic vehicle routing model and a dynamic vehicle routing adjustment method are proposed.(2)Using NSGA-? algorithm to solve multi-objective vehicle routing problem.In order to solve the problem that NSGA-? is prone to fall into local optimum when dealing with three or more objectives and can not find the optimal result,this paper uses NSGA-? algorithm to solve the multi-objective vehicle routing problem,so as to improve the effect of multi-objective vehicle routing planning.(3)A new algorithm H-NSGA-? is designed to speed up the solution rate of multi-objective vehicle routing problem.H-NSGA-? proposes a hybrid crossover operator,crossover probability and mutation probability adjustment mechanism to improve the convergence rate of the algorithm,so as to improve the efficiency of solving vehicle routing problem.(4)A dynamic vehicle routing adjustment algorithm based on road congestion is proposed.Aiming at the traffic jam in the road section of the customer points will to be served in the process of carrying out the distribution task according to the plan,the route adjustment method is put forward.(5)Experiments verify the effectiveness and efficiency of H-NSGA-? algorithm.Compared with NSGA-? and NSGA-?,H-NSGA-? can achieve better objective value and improve the convergence rate of the algorithm in vehicle routing planning.The hybrid crossover operator proposed in H-NSGA-? algorithm is analyzed,and its performance is better than that of one of the crossover operators alone.It is proved that H-NSGA-?algorithm is suitable for solving multi-objective vehicle routing problems.Finally,the simulation experiment of Dalian Zhongtong Logistics is carried out,and the feasibility of the logistics distribution route planning method designed is analyzed.