Modeling and Solving the One-to-One Multi-Commodity Pickup and Delivery Traveling Salesman Problem

Description

We address the one-to-one multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) introduced by Hernandez-Perez and Salazar-Gonzalez in 2009. The m-PDTSP is a generalization of the TSP and arises in several transportation and logistics applications. We are given a complete directed graph with a node set consisting of start and end depot and a set of customers. For each arc a travel distance (or cost) is given. A set of commodities is defined, each one associated with a demand, a source and a destination node. The objective is to find a minimum-cost Hamiltonian path such that the vehicle starts and ends at the corresponding depot, the demand of each commodity is transported from its source to its destination, and the given vehicle capacity is not exceeded throughout the path. A different problem variant, the many-to-many one-commodity pickup and delivery traveling salesman problem (1-PDTSP), just considers a single commodity and each node can be a source or target for units of this commodity, defined by a given positive or negative demand. We show that the m-PDTSP is equivalent to the 1-PDTSP with additional precedence constraints defined by the origin-destination pairs for each commodity and explore several models based on this equivalence. In particular, we consider a formulation based on a 3-dimensional layered graph that combines time and load together and achieves tight LP bounds, at the cost of a large model size. Especially for tightly capacitated instances with a large number of commodities our branch-and-cut algorithms are able to outperform the approaches by Hernandez-Perez and Salazar-Gonzalez. Additionally, an adapted variant of our branch-and-cut algorithm for the uncapacitated m-PDTSP (sequential ordering problem) is able to solve to optimality several open instances from the TSPLIB.

Period	5 Mar 2014 → 7 Mar 2014
Event title	3rd International Symposium on Combinatorial Optimization
Event type	Other
Degree of Recognition	International