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

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.


90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
Full Text: DOI