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 leng th restrictions. The algorithm considers a sequence of adjacent soluti ons obtained by repeatedly removing a vertex from its current route an d reinserting it into another route. This is done by means of a genera lized insertion procedure previously developed by the authors. During the course of the algorithm, infeasible solutions are allowed. Numeric al tests on a set of benchmark problems indicate that tabu search outp erforms the best existing heuristics, and TABUROUTE often produces the best known solutions.