Design And Application Of Improved Guided Local Search Based Algorithm For Period Vehicle Routing Problem

The Period Vehicle Routing Problem (PVRP), a variant of the classical Vehicle Routing Problem (VRP), is an extension to time period of VRP. Typically, VRP is a routing problem in 1 day, and PVRP extending the planning period from a single day to several days. PVRP model occurs in a wide range of applications, including courier services, elevator maintenance and repair, vending machine replenishment and the collection of waste, etc.The paper analyzes the Period Vehicle Routing Problem and Guided Local Search (GLS), and reviews both Chinese and international related literatures. Based on the analysis of PVRP, an improved guided local search (IGLS) Algorithm is developed, which contain two phases: Creating initial solution and Improvement. The phase 1 is to create an initial feasible solution by applying amendatory Clarke and Wright Saving method. Guided local search (GLS), a near recent developed heuristic algorithm, in general, obtains very good results for combinatorial optimization problems like TSP, VRP and Scheduling problem. IGLS improves the penalty strategy of GLS, and develops dynamic penalty strategy. For PVRP problems, at the very beginning of iteration, the penalized arcs, generally, would never reenter the routes again, so it makes sense to penalize them heavily at one time, in order that the solution's improvement would not use these arcs again to save computational time; however, with the process continuing, the still existent penalized arcs intend to be necessary for better solution, so we expect the arcs was not penalized too heavily, and therefore, a smaller penalty parameter is wanted.The paper evaluates the developed IGLS by computational experiments using classic instances. After the comparison between IGLS and other heuristics on results and computational time, it's shown that IGLS is a competitive heuristic. Also, the paper shows the effect of both dynamic and static penalty strategies to the result and computational time, and the comparison demonstrates that dynamic penalty strategy can improve the result and decrease computational time. Different from static penalty strategy, dynamic penalty strategy uses more parameters to control penalty parameter and performs well to PVRP, combined with the nature of computation.This paper also introduces a case study, that a third party logistic company transports goods for some suppliers to a distribution center of a supermarket, and solve the problem. From the case study, it's demonstrated that PVRP is useful and effective to real-world problems.