A tabu search heuristic for the single vehicle pickup and delivery problemwith time windows

The single vehicle pickup and delivery problem with time windows is a gener alization of the traveling salesman problem. In such a problem, a number of transportation requests have to be satisfied by one vehicle, each request having constraints to respect: a pickup at its origin and a delivery at its destination, and a time window at each location. The capacity of the vehic le has to be respected. The aim is to minimize the total distance traveled by the vehicle. A number of exact and approximate solution methods exists i n the literature, but to the author's knowledge none of them make use of me taheuristics, still promising with other vehicle routing problems. In this paper we present tabu search and probabilistic tabu search. Results obtaine d on classical traveling salesman problems and a class of randomly generate d instances indicate that our approach often produces optimal solutions in a relatively short execution time.