The multi-commodity pickup-and-delivery traveling salesman problem

The ‘multi‐commodity Pickup‐and‐Delivery Traveling Salesman Problem’ (m‐PDTSP) is a generalization of the well‐known ‘Traveling Salesman Problem’ in which cities correspond to customers providing or requiring known amounts of m different products, and the vehicle has a known capacity. Each customer must be visited exactly once by the vehicle serving the demands of the different products while minimizing the total travel distance. It is assumed that a unit of a product collected from a customer can be supplied to any other customer that requires this product. We introduce a mixed integer linear programming model for the m‐PDTSP, discuss a classical decomposition technique, describe valid inequalities to strengthen the linear programming relaxation of the model, and detail separation procedures to develop a branch‐and‐cut procedure. Computational experiments on randomly generated instances with up to 30 customers, three products, and small vehicle capacities are analyzed.