Load-Dependent and Precedence-Based Models for Pickup and Delivery Problems

Luis Gouveia, Mario Ruthmair

    Research output: Contribution to journalArticlepeer-review


    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 and such that 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 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 (which is known as the sequential ordering problem) we are able to solve to optimality several open instances from the TSPLIB and SOPLIB.
    Original languageEnglish
    Pages (from-to)56-71
    Number of pages16
    JournalComputers & Operations Research
    Publication statusPublished - 2015

    Research Field

    • Former Research Field - Mobility Systems


    Dive into the research topics of 'Load-Dependent and Precedence-Based Models for Pickup and Delivery Problems'. Together they form a unique fingerprint.

    Cite this