[Zurück]

L. Gouveia, M. Ruthmair:
"Load-dependent and precedence-based models for pickup and delivery problems.";
Optimization Online, 06 (2014), 34 S.

We address the one-to-one multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) which is a generalization of the TSP and arises in several transportation and logistics applications. The objective is to nd a minimum-cost directed Hamiltonian path which starts and ends at given depot nodes, the demand of each given commodity is transported from the associated source to its destination, and the vehicle capacity is never exceeded. In contrast, 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. We show
that the m-PDTSP is equivalent to the 1-PDTSP with additional precedence constraints de ned by the source-destination pairs for each commodity and explore several models based on this equivalence. In particular, we consider layered graph models for the capacity constraints and introduce new valid inequalities for the precedence relations. Especially for tightly capacitated instances with a large number of commodities our branch-and-cut algorithms outperform the existing approaches. For the uncapacitated m-PDTSP (sequential ordering problem) we are able to solve to optimality several open
instances from the TSPLIB and SOPLIB.

Transportation, Traveling Salesman, Sequential ordering

http://publik.tuwien.ac.at/files/PubDat_233245.pdf