×

zbMATH — the first resource for mathematics

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.

MSC:
90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI