A tabu search algorithm for the open vehicle routing problem

The problem studied in this paper is different from the basic vehicle routing problem in that the vehicles do not return to the distribution depot after delivering the goods to the customers or, if they do so, they must visit the same customers, for the collection of goods, in the reverse order. The practical importance of this problem has been established some decades ago, but it has received very little attention from researchers. In this paper we present a new tabu search algorithm that explores the structure of this type of problem and we compare its performance with another heuristic designed for the same purpose, which has been published recently.