Research On Multi-objective Evolutionary Optimization Based Algorithms For Vehicle Routing Problems

Vehicle routing problems(CVRPs)widely present in many aspects of real life,such as street garbage collection and logistics scheduling.This thesis focuses on two variants of routing problems,namely,large-scale capacitated vehicle routing problems(LSCVRPs)and vehicle routing problem with time window(VRPTW).LSCVRP and VRPTW are very complex optimization problems,and it is very difficult to solve these two problems.Although a number of algorithms can deal with small-scale CVRP,most of them are difficult to get satisfactory solutions as the scale of CVRPs increases.To this end,this thesis proposes an evolutionary multi-objective route grouping-based algorithm for large-scale CVRPs.For VRPTW,it is difficult for existing algorithms to deal with hard time window constraints efficiently.Therefore,this thesis proposes a coevolutionary framework based algorithm to solve VRPTW.The main contributions of this thesis is summarized as follows:(1)This thesis proposes an evolutionary multi-objective route grouping-based algorithm(EMRG-HA)to solve LSCVRPs.The main idea of EMRG-HA is to use the divide and conquer strategy where the large-scale CVRP is decomposed into small subcomponents.To this end,an evolutionary multi-objective route grouping(EMRG)method is suggested.The suggested EMRG adopts a multi-objective evolutionary algorithm for route grouping by simultaneously optimizing three well-defined objectives,intragroup distance,intergroup distance,and intergroup balance in size,which can obtain a set of promising decompositions of LSCVRPs.Based on EMRG,this thesis proposes a local search method to improve the quality of routes in groups,where only routes in one group instead of in all groups are improved which is determined according to the average serving cost of routes in each group.Experiments are conducted on 32 instances of two LSCVRP benchmarks to verify the performance of EMRG-HA.The experimental results show that the EMRG-HA is superior over eight existing algorithms on most test instances of LSCVRPs,in terms of both computational efficiency and solution quality.(2)This thesis proposes a coevolutionary framework for constrained multiobjective optimization(CCMO)to solve MO-VRPTW.The proposed CCMO adopts coevolutionary framework,where one population is used to solve the original problem whereas another population is used to solve a simple helper problem derived from the original one.In evolution,the assistance in solving the original problem is achieved by sharing useful information between the two populations.Here,the original problem is MO-VRPTW,whereas the simple helper question is the original problem without the constraints of time window.Experimental results demonstrate that the proposed CCMO has high competitiveness on MO-VRPTW and constrained multi-objective optimization benchmarks.