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

    Fingerprint

    Dive into the research topics of 'A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem'. Together they form a unique fingerprint.

    Cite this