A tabu search heuristic for a vehicle routing problem

The purpose of this paper is to describe 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 an ejection chain strategy which produces compound moves for passing from a current solution to another solution. During the course of the algorithm, various types of moves are used and crossing infeasible solutions are allowed. Numerical tests on a set of benchmark problems indicate that the proposed algorithm is highly competitive with existing heuristics