A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem

Mads Kehlet Jepsen, Simon Spoorendonk, Stefan Røpke

    Research output: Contribution to journalJournal articleResearchpeer-review

    1 Downloads (Pure)

    Abstract

    This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality surpassing previous exact algorithms.
    Original languageEnglish
    JournalTransportation Science
    Volume47
    Pages (from-to)23-37
    ISSN0041-1655
    DOIs
    Publication statusPublished - Feb 2013

    Keywords

    • Vehicle routing
    • Two-echelon systems
    • Branch-and-cut

    Cite this

    @article{4bf4eb679f5d44cd9ac437bb44219b97,
    title = "A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem",
    abstract = "This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality surpassing previous exact algorithms.",
    keywords = "Vehicle routing, Two-echelon systems, Branch-and-cut",
    author = "Jepsen, {Mads Kehlet} and Simon Spoorendonk and Stefan R{\o}pke",
    year = "2013",
    month = "2",
    doi = "10.1287/trsc.1110.0399",
    language = "English",
    volume = "47",
    pages = "23--37",
    journal = "Transportation Science",
    issn = "0041-1655",
    publisher = "Institute for Operations Research and the Management Sciences (I N F O R M S)",

    }

    A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. / Jepsen, Mads Kehlet; Spoorendonk, Simon; Røpke, Stefan.

    In: Transportation Science, Vol. 47, 02.2013, p. 23-37.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem

    AU - Jepsen, Mads Kehlet

    AU - Spoorendonk, Simon

    AU - Røpke, Stefan

    PY - 2013/2

    Y1 - 2013/2

    N2 - This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality surpassing previous exact algorithms.

    AB - This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality surpassing previous exact algorithms.

    KW - Vehicle routing

    KW - Two-echelon systems

    KW - Branch-and-cut

    U2 - 10.1287/trsc.1110.0399

    DO - 10.1287/trsc.1110.0399

    M3 - Journal article

    VL - 47

    SP - 23

    EP - 37

    JO - Transportation Science

    JF - Transportation Science

    SN - 0041-1655

    ER -