Montag, 02. Mai 2016, 16:45 - 18:15 iCal

ISOR Colloquium

"Modeling and Solving Pickup and Delivery Traveling Salesman Problems"

Speaker: Mario Ruthmair

Lecture Hall 12 OMP1 (2nd Floor)
Oskar-Morgenstern-Platz 1, 1090 Vienna


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 find 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 defined by the source-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 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.

Zur Webseite der Veranstaltung


Institut für Statistik und Operations Research


Mag. Vera Lehmwald
Fakultät für Wirtschaftswissenschaften
Institut für Statistik und Operations Research
+43 1 4277 38651