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

Luis Gouveia, Mario Ruthmair

    Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

    Abstract

    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.
    OriginalspracheEnglisch
    Seiten (von - bis)56-71
    Seitenumfang16
    FachzeitschriftComputers & Operations Research
    DOIs
    PublikationsstatusVeröffentlicht - 2015

    Research Field

    • Ehemaliges Research Field - Mobility Systems

    Fingerprint

    Untersuchen Sie die Forschungsthemen von „Load-Dependent and Precedence-Based Models for Pickup and Delivery Problems“. Zusammen bilden sie einen einzigartigen Fingerprint.

    Diese Publikation zitieren