A Tabu Search Heuristic for the Vehicle Routing Problem
Michel Gendreau, Alain Hertz, Gilbert Laporte
Management Science · 1994 · Volume 40 · Issue 10
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
Enable JavaScript for citation tools and additional paper interactions.