Research On Evolutionary Algorithm Based On Local Information To Solve Vehicle Routing Problem

With the rapid growth of economy,vehicle routing problems have become a hot topic in the logistics field.An efficient vehicle route can improve the efficiency of transportation and reduce transportation costs.Therefore,since evolutionary algorithm can obtain a better solution when solving this problem,many scholars have developed a lot of research on evolutionary algorithm based solving methods.However,the existing algorithms have the problem of slow convergence speed,and their performance considerately deteriorates as the scale of the problem increases.This dissertation focuses on Capacitated Vehicle Routing Problems(CVRP)and Large-Scale Capacitated Vehicle Routing Problems(LSCVRP).Specifically,the contributions are list as follows:(1)This dissertation proposes an evolutionary algorithm for solving CVRPs by using local information(RMEA)to accelerate the convergence speed.RMEA uses relevance matrix to guide the crossover and mutation process of evolutionary algorithms.The elements in relevance matrix involve three kinds of local information,including the distance between each pair of customers,the customer density around each pair of customers,and the local information of elite individuals during evolution are considered.During the running of RMEA,the relevance matrix is adaptively updated to increase the weight of the local information of elite individuals.Moreover,a diversity preservation strategy based on the relevance matrix is proposed to increase the diversity of the population,where the lower-ranked customers calculated by the relevance matrix are insert into the routes.This dissertation verifies the performance of RMEA on three benchmark datasets.The experiments results show that compared to eight existing algorithms tailored for CVRPs,the proposed RMEA has advantage in convergence speed and the quality of solutions.(2)This dissertation proposes an evolutionary algorithm based on local information grouping to solve the LSCVRPs(LIGEA).This dissertation adopts the idea of divide and conquer to decompose LSCVRPs into small subcomponents.To this end,this dissertation uses several local information of the problem to measure the probability that two customers belong to the same group.The local information used by LIGEA contains three aspects,the density between customers,the size of the customer’s domain,and the local information of elite individuals.In addition,LIGEA uses different weight vectors to increase the diversity of groups.After decomposing,the decompositions of LSCVRPs are solving by evolutionary algorithms in parallel.This dissertation verifies the performance of LIGEA on two benchmark datasets.The experiments results show that compared to five existing algorithms tailored for LSCVRPs,the proposed LIGEA has advantage in computational efficiency.