The Edge Set Cost of the Vehicle Routing Problem with Time Windows

Line Blander Reinhardt, Mads Kehlet Jepsen, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review

    295 Downloads (Pure)

    Abstract

    We consider an important generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. This fixed cost could reflect payment for toll roads, investment in new facilities, the need for certifications, and other costly investments. The certifications and investments impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company.
    This violates the traditional assumption that the path between two destinations is well defined and independent of other choices. Different versions for defining the edge sets are discussed and formulated. Both the multigraph case and the direct path case are described, and mixed-integer-programming formulations of the problem are presented for both cases. A solution method based on branch-price-and-cut is applied to the direct path case. The computational results show that instances with up to 40 customers can be solved in a reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX.
    Original languageEnglish
    JournalTransportation Science
    Volume50
    Issue number2
    Pages (from-to)694–707
    ISSN0041-1655
    DOIs
    Publication statusPublished - 2016

    Keywords

    • VRPTW
    • Branch cut and price
    • Multigraphs

    Cite this

    Reinhardt, Line Blander ; Jepsen, Mads Kehlet ; Pisinger, David. / The Edge Set Cost of the Vehicle Routing Problem with Time Windows. In: Transportation Science. 2016 ; Vol. 50, No. 2. pp. 694–707.
    @article{f149d692d21c4a939135b32ea67771ea,
    title = "The Edge Set Cost of the Vehicle Routing Problem with Time Windows",
    abstract = "We consider an important generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. This fixed cost could reflect payment for toll roads, investment in new facilities, the need for certifications, and other costly investments. The certifications and investments impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company.This violates the traditional assumption that the path between two destinations is well defined and independent of other choices. Different versions for defining the edge sets are discussed and formulated. Both the multigraph case and the direct path case are described, and mixed-integer-programming formulations of the problem are presented for both cases. A solution method based on branch-price-and-cut is applied to the direct path case. The computational results show that instances with up to 40 customers can be solved in a reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX.",
    keywords = "VRPTW, Branch cut and price, Multigraphs",
    author = "Reinhardt, {Line Blander} and Jepsen, {Mads Kehlet} and David Pisinger",
    year = "2016",
    doi = "10.1287/trsc.2015.0620",
    language = "English",
    volume = "50",
    pages = "694–707",
    journal = "Transportation Science",
    issn = "0041-1655",
    publisher = "Institute for Operations Research and the Management Sciences (I N F O R M S)",
    number = "2",

    }

    The Edge Set Cost of the Vehicle Routing Problem with Time Windows. / Reinhardt, Line Blander; Jepsen, Mads Kehlet; Pisinger, David.

    In: Transportation Science, Vol. 50, No. 2, 2016, p. 694–707.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - The Edge Set Cost of the Vehicle Routing Problem with Time Windows

    AU - Reinhardt, Line Blander

    AU - Jepsen, Mads Kehlet

    AU - Pisinger, David

    PY - 2016

    Y1 - 2016

    N2 - We consider an important generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. This fixed cost could reflect payment for toll roads, investment in new facilities, the need for certifications, and other costly investments. The certifications and investments impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company.This violates the traditional assumption that the path between two destinations is well defined and independent of other choices. Different versions for defining the edge sets are discussed and formulated. Both the multigraph case and the direct path case are described, and mixed-integer-programming formulations of the problem are presented for both cases. A solution method based on branch-price-and-cut is applied to the direct path case. The computational results show that instances with up to 40 customers can be solved in a reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX.

    AB - We consider an important generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. This fixed cost could reflect payment for toll roads, investment in new facilities, the need for certifications, and other costly investments. The certifications and investments impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company.This violates the traditional assumption that the path between two destinations is well defined and independent of other choices. Different versions for defining the edge sets are discussed and formulated. Both the multigraph case and the direct path case are described, and mixed-integer-programming formulations of the problem are presented for both cases. A solution method based on branch-price-and-cut is applied to the direct path case. The computational results show that instances with up to 40 customers can be solved in a reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX.

    KW - VRPTW

    KW - Branch cut and price

    KW - Multigraphs

    U2 - 10.1287/trsc.2015.0620

    DO - 10.1287/trsc.2015.0620

    M3 - Journal article

    VL - 50

    SP - 694

    EP - 707

    JO - Transportation Science

    JF - Transportation Science

    SN - 0041-1655

    IS - 2

    ER -