Heuristics for the traveling salesman problem with pickup and delivery

We consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), an extension of the well-known Traveling Salesman Problem where each customer to be served is associated with two quantities of goods to be collected and delivered, respectively. A vehicle with given capacity starts at a depot and must visit each customer exactly once. The vehicle capacity must not be exceeded and the total length of the tour must be minimized. We describe new heuristics for TSPPD, the first based on the exact solution of a special case and the second based on tabu search, and we analyze their average performance through extensive computational experiments.