Two Stage Hybrid Evolutionary Algorithm For Tri-objective VRPTW

Vehicle routing problem(VRP)is a discrete combinatorial optimization problem.It is also a famous NP-Hard problem.It is widely used in urban traffic improvement and logistics distribution management.In this dissertation,a two-stage hybrid evolutionary algorithm is proposed to optimize the three objectives vehicle routing problem with time windows(VRPTW).Firstly,in the first stage,the lower bound of the classification population is obtained by the improved harmony search algorithm,and the upper bound of the classification population is obtained by the Elitist Non-dominated Sorting Genetic Algorithm(NSGA-?).Then,in the second stage,the improved NSGA-? is used to gradually optimize the classification population obtained in the first stage.In this dissertation,the VRPTW is studied from the following aspects:(1)The characteristics of nonlinear discrete optimization problem and the exhaustible number of vehicles for the three objectives vehicle routing with time window.TSHEA extends the basic calculation method of crowding degree,and proposes a population structure based on classification.In addition,considering the increase of time complexity caused by higher dimensional objective optimization problems,the advantage of the two-stage computational framework is that the multiobjective optimization problems are reduced in dimension on the premise of obtaining approximate optimal solution,so as to improve the computational efficiency.(2)In the two-stage model of TSHEA,the hybrid strategy of improved harmony search algorithm and NSGA-? are used.Different algorithms are used in different stages for solving the three objectives vehicle routing problem with time windows,which give full play to the advantages of the improved harmony search algorithm in solving the number of vehicles and NSGA-? in solving the two objectives vehicle routing problem with time windows.In this dissertation,the Solomon test instances is used for simulation experiment.The experiment is divided into two parts: the first part shows the performance of the improved harmony search algorithm in the first stage,especially in solving the number of vehicles;the second part verifies the performance of the optimal solution from three different evaluation indexes.The experimental results show the front of the optimal solution set obtained by TSHEA has obvious advantages in approximation,distribution and extensibility.