A Tabu Search Heuristic for the Vehicle Routing Problem

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.

• 저널Management Science · 40(10) · 1276–1290
• 토픽Vehicle Routing Optimization Methods · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.40.10.1276
• 저자Michel Gendreau, Alain Hertz, Gilbert Laporte