A Recycling Heuristic Capable of Generating Initial Solutions for Use in Vehicle Routing Metaheuristics

Instances of the vehicle routing problem (VRP) and its variants are notoriously difficult to solve. Moreover, when combining characteristics of multiple VRP variants, the underlying complexities of the variants proliferate. This has led to a variety of metaheuristics being proposed for solving VRP instances with side constraints. Metaheuristics, however, require the generation of an appropriate initial solution (trajectory-based metaheuristics) or a population of initial solutions (population-based metaheuristics), the quality of which affects the performance of the solution approach. When computing VRP solutions for a depot and its assigned customers, historical solutions generated for the same depot may be adapted to form the initial solution or part of the initial population for the metaheuristic employed, thereby effectively recycling historical solutions. In this paper, such a recycling heuristic is proposed. A genetic algorithm is applied to solve instances of the periodic VRP with time-windows (PVRPTW) and the effect of the recycling heuristic on the run time of the metaheuristic is evaluated. It is shown that a decrease in run time of up to 26% may be achieved by employing the recycling heuristic to generate initial solutions, without affecting the quality of the solutions returned.