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 starts with a set of routes containing one city each and then performs tabu moves consisting of inserting cities into different routes. 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. The algorithm ends with the application of a post-optimization procedure. Numerical tests on a set of benchmark problems indicate that the proposed algorithm outperforms previous heuristics.
Published June 1991 , 36 pages