A General Metaheuristic Algorithm For A Set Of Rich Vehicle Routing Problems

In recent years,China's logistics industry has a huge development,and ranked first all around the world.It has become a new bright spot of China's economic growth,while the major E-Commerce giant,logistics enterprises have achieved rapid development.However,the overall competitiveness of China's logistics industry is still not high,and has a great contrast to its huge market size,and the gap with developed countries is still great.In order to improve service quality and competitiveness of the logistics industry,taking into account the various needs of customers' constraints,the use of computer technology to provide intelligent route planning is of great importance for the transportation business enterprises,and this article is just to study the Rich Vehicle Routing Problem(RVRP).RVRP is a optimization problem,and has a difference with the traditional one.Traditional vehicle routing problem often focus on the optimization of one main constraint,so it is only can address this constraint;Fortunately,a variety of practical constraints are comprehensively taken into consideration of RVRP,and a series of combination constraints can be solved by the designed algorithm.The following five constraints are studied in this paper: weight constraint,multiple depots constraint,multiple trip time constraint,multiple time windows constraint,multiple vehicle type constraint,and the last four are called the "4-multiple constraints".And any combination of these constraints is supported.For the researched question,General Vehicle Routing Algorithm(GVRA)based on Skewed Variable Neighborhood Search(SVNS)is designed to address the problem of any combination on the five features.A slice of operators and heuristic approaches which are developed in terms of the specific constraints and depth optimization are embedded in GVRA.The first objective function is to minimize the total number of vehicles,the second is to minimize the total distance traveled or total cost.The algorithm includes the following three phase: the first is to generate an initial solution;second stage is the preliminary optimization by SVNS,and an improved solution will be generated;as the solution obtained by last stage for the initial solution,the final stage is the optimization for the specific constraints.Then,in order to verify the correctness and effectiveness of the designed algorithm,numerical experiments including the computation of six sub-problems in three levels are conducted on GVRA.The first level is to prove the ability on basic vehicle routing problem;The second level is the instance test on multiple depot,multiple trips,multiple time windows,and multiple vehicle types problems respectively;And to illustrate the effectiveness on “4-multiple constraints” is in level three.The computational results explain the validity and effectiveness of GVRA,and demonstrate that our algorithm is competitive on both benchmark instances and generated instances in terms of the accuracy of solution and computational time.