The Traveling Salesman Problem with Pickup and Delivery: Polyhedral Results and a Branch-and-Cut Algorithm

Irina Dumitrescu, Stefan Røpke, Jean-Francois Cordeau, Gilbert Laporte

Research output: Contribution to journalJournal articleResearchpeer-review

1320 Downloads (Pure)

Abstract

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-toone relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. In this paper, the TSPPD is modeled as an integer linear program and its polyhedral structure is analyzed. In particular, the dimension of the TSPPD polytope is determined and several valid inequalities, some of which are facet defining, are introduced. Separation procedures and a branch-and-cut algorithm are developed. Computational results show that the algorithm is capable of solving to optimality instances involving up to 35 pickup and delivery requests, thus more than doubling the previous record of 15.
Keyword: pickup and delivery,branch-and-cut algorithm,precedence relationships,Traveling salesman problem,separation procedures,valid inequalities,polyhedral results
Original languageEnglish
JournalMathematical Programming
Volume121
Issue number4
Pages (from-to)269-305
ISSN0025-5610
DOIs
Publication statusPublished - 2010
Externally publishedYes

Fingerprint

Dive into the research topics of 'The Traveling Salesman Problem with Pickup and Delivery: Polyhedral Results and a Branch-and-Cut Algorithm'. Together they form a unique fingerprint.

Cite this