An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP

Margarita P. Castro (), Andre A. Cire () and J. Christopher Beck ()
Additional contact information
Margarita P. Castro: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Andre A. Cire: Department of Management, University of Toronto Scarborough and Rotman School of Management, Toronto, Ontario M1E 1A4, Canada
J. Christopher Beck: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 263-278

Abstract: We address the one-to-one multicommodity pickup-and-delivery traveling salesman problem, a challenging variant of the traveling salesman problem that includes the transportation of commodities between locations. The goal is to find a minimum cost tour such that each commodity is delivered to its destination and the maximum capacity of the vehicle is never exceeded. We propose an exact approach that uses a discrete relaxation based on multivalued decision diagrams (MDDs) to better represent the combinatorial structure of the problem. We enhance our relaxation by using the MDDs as a subproblem to a Lagrangian relaxation technique, leading to significant improvements in both bound quality and run-time performance. Our work extends the use of MDDs for solving routing problems by presenting new construction methods and filtering rules based on capacity restrictions. Experimental results show that our approach outperforms state-of-the-art methodologies, closing 33 open instances from the literature, with 27 of those closed by our best variant.

Keywords: decision diagrams; Lagrangian duality; vehicle routing; traveling salesman problem (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0881 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:2:p:263-278

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().