A Tabu Search Heuristic for the Vehicle Routing Problem

Michel Gendreau, Alain Hertz and Gilbert Laporte
Additional contact information
Michel Gendreau: Centre de recherche sur les transports Université de Montréal, C.P. 6128, succursale A, Montréal, Québec, Canada H3C 3J7
Alain Hertz: Département de mathématiques, École Polytechnique Fédérale de Lausanne, Ecublens, CH-1015 Lausanne, Switzerland
Gilbert Laporte: Centre de recherche sur les transports Université de Montréal, C.P. 6128, succursale A, Montréal, Québec, Canada H3C 3J7

Management Science, 1994, vol. 40, issue 10, 1276-1290

Abstract: The purpose of this paper is to describe TABUROUTE, a new tabu search heuristic for the vehicle routing problem with capacity and route length restrictions. The algorithm considers a sequence of adjacent solutions obtained by repeatedly removing a vertex from its current route and reinserting it into another route. This is done by means of a generalized insertion procedure previously developed by the authors. During the course of the algorithm, infeasible solutions are allowed. Numerical tests on a set of benchmark problems indicate that tabu search out performs the best existing heuristics, and TABUROUTE often produces the best known solutions.

Keywords: vehicle routing problem; tabu search; generalized insertion (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (180)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.40.10.1276 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:40:y:1994:i:10:p:1276-1290

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().