A tabu search heuristic for the vehicle routing problem. (English) Zbl 0822.90053

Gendreau, Michel; Hertz, Alain; Laporte, Gilbert

Manage. Sci. 40, No. 10, 1276-1290 (1994).

Summary: 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 outperforms the best existing heuristics, and TABUROUTE often produces the best known solutions.

MSC:

90B06	Transportation, logistics and supply chain management
90C35	Programming involving graphs or networks

Keywords:

TABUROUTE; tabu search heuristic; vehicle routing; capacity and route length restrictions