An MDD Based Lagrangian Approach to the Multicommodity Pickup and Delivery TSP
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.
INFORMS J. Comput.