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

Journal Article


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. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 46–59 2014

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.