Two-Layer Based Neighborhood Search For Solving Large Scale Vehicle Routing Problem

Vehicle Routing Problem(VRP)widely exists in logistics and transportation scenarios such as trunk transportation,take-out delivery,community group purchasing and urban public services and so on.With the development of society,many of these scenarios far exceed the traditional VRP scenarios in terms of scale and real-time requirements.However,the solution space of large scale VRP is very large,and the complexity of the problem is further increased due to various constraints of the VRP.There is a lack of effective method to obtain satisfactory solutions of VRP quickly in existing public research.First,the VRP model is transformed where constraints are converted into penalty items for constraint violation and objectives are transformed into total cost which represents the main objective(number of vehicles,total distance and constraint violations)of VRP,then a non-constrained auxiliary objective(the number of vehicles and the total distance)is constructed for the main objective.Second,a Two-Layer based Neighborhood Search(TLNS)algorithm is designed for solving large scale VRP which modelled into two-layer representation.The upper layer optimizes the auxiliary objective,the lower layer optimizes the main objective.Optimizing the two objectives at the same time can speed up the convergence of the solution while reducing the amount of constraint violation.Each cycle of TLNS consists of several upper layer search and several lower layer search.In the upper layer search,the current solution is taken from the lower layer solution set and the optimized neighborhood solution is used to replace the solution with the largest auxiliary objective value in the upper layer solution set.In the lower layer search,the current solution is taken from the upper layer solution set and the optimized neighborhood solution is used to replace the solution with the largest main objective value in the lower layer solution set.With the iteration going on,the upper layer obtains the solution with smaller constraint violations from the lower layer and further optimizes number of vehicles and total distance of the solution,while the lower layer obtains the solution with smaller number of vehicles and total distance from the upper layer and further optimizes constraint violations of the solution.The upper layer search and the lower layer search are alternately performed so that the upper and lower solution sets can update and restrict each other.The implementation of TLNS includes: 1)Initial constraint relaxation is performed when initializing the upper and lower layers’ solution sets using multiple construction strategies;2)Several operators are designed for the upper operator set and the lower operator set respectively;3)A new operator selection strategy is proposed,which combines the fair random selection method with small proportion and the weight based selection method with large proportion to select the upper and lower layers’ operator;and 4)A new weight updating method updates the operator’s weight once every several iterations,and resets the operator’s weight after updating weight several times.To verify the effectiveness of TLNS,three sets of comparative experiments are carried out by comparing TLNS with three VRP algorithms,it is verified that TLNS can obtain high quality satisfactory solutions of large scale VRP in a short time.This paper also designs corresponding experiments to investigate the performance and optimization effects of the algorithm parameter settings.