A general heuristic for vehicle routing problems

David Pisinger, Stefan Røpke

Research output: Contribution to journalJournal articleResearchpeer-review

3644 Downloads (Pure)

Abstract

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].
Keyword: vehicle routing problem,metaheuristics,,large neighborhood search
Original languageEnglish
JournalComputers & Operations Research
Volume34
Issue number8
Pages (from-to)2403-2435
ISSN0305-0548
DOIs
Publication statusPublished - 2007
Externally publishedYes

Fingerprint

Dive into the research topics of 'A general heuristic for vehicle routing problems'. Together they form a unique fingerprint.

Cite this