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 cust omer to be served is associated with two quantities of goods to be collecte d and delivered, respectively. A vehicle with given capacity starts at a de pot and must visit each customer exactly once. The vehicle capacity must no t be exceeded and the total length of the tour must be minimized. We descri be new heuristics for TSPPD, the first based on the exact solution of a spe cial case and the second based on tabu search, and we analyze their average performance through extensive computational experiments. (C) 1999 Elsevier Science Ltd. All rights reserved.