A general heuristic for vehicle routing problems

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP). All problem variants are transformed into a rich pickup and delivery model and solved using the adaptive large neighborhood search (ALNS) framework presented in Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, to appear]. The ALNS framework is an extension of the large neighborhood search framework by Shaw [Using constraint programming and local search methods to solve vehicle routing problems. In: CP-98, Fourth international conference on principles and practice of constraint programming, Lecture notes in computer science, vol. 1520, 1998. p. 417-31] with an adaptive layer. This layer adaptively chooses among a number of insertion and removal heuristics to intensify and diversify the search. The presented approach has a number of advantages: it provides solutions of very high quality, the algorithm is robust, and to some extent self-calibrating. Moreover, the unified model allows the dispatcher to mix various variants of VRP problems for individual customers or vehicles. As we believe that the ALNS framework can be applied to a large number of tightly constrained optimization problems, a general description of the framework is given, and it is discussed how the various components can be designed in a particular setting. The paper is concluded with a computational study, in which the five different variants of the vehicle routing problem are considered on standard benchmark tests from the literature. The outcome of the tests is promising as the algorithm is able to improve 183 best known solutions out of 486 benchmark tests. The heuristic has also shown promising results for a large class of vehicle routing problems with backhauls as demonstrated in Ropke and Pisinger [A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 2004, to appear]. (c) 2005 Elsevier Ltd. All rights reserved.