The Pickup-and-Delivery Travelling Salesman Problem

It is a related problem to the well-known Travelling Salesman Problem 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 serving the demand while minimizing the total travel distance. We assume that the product collected from pickup customers can be delivery to delivery customers, i.e., it is a non-deteriorable product . We introduce a 0-1 integer linear model for this problem and describe a branch-and-cut procedure for finding an optimal solution. Several results form the classical Capacitated Vehicle Routing Problem can be extended to this new problem, and the so-called Pickup and Delivery Travelling Salesman Problem can be solved as a particular case. Some computational results are presented to analyze the performance of our proposal. Also similar ideas can be extended to, e.g., the Dial-a-Ride Travel ling Salesman Problem.

TPP instances:

Short version.

Full version.