A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery

We study a generalization of the well-known traveling salesman problem (TSP) where each customer provides or requires a given non-zero amount of product, and the vehicle in a depot has a given capacity. Each customer and the depot must be visited exactly once by the vehicle supplying the demand while minimizing the total travel distance. We assume that the product collected from pickup customers can be delivered to delivery customers. We introduce a 0-1 integer linear model for this problem and describe a branch-and-cut procedure for finding an optimal solution. The model and the algorithm are adapted to solve instances of TSP with pickup and delivery. Some computational results are presented to analyze the performance of our proposal. (C) 2004 Published by Elsevier B.V.