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

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.