Formulations and exact algorithms for the vehicle routing problem with time windows

Brian Kallehauge

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    In this paper we review the exact algorithms proposed in the last three decades for the solution of the vehicle routing problem with time windows (VRPTW). The exact algorithms for the VRPTW are in many aspects inherited from work on the traveling salesman problem (TSP). In recognition of this fact this paper is structured relative to four seminal papers concerning the formulation and exact solution of the TSP, i.e. the arc formulation, the arc-node formulation, the spanning tree formulation, and the path formulation. We give a detailed analysis of the formulations of the VRPTW and a review of the literature related to the different formulations. There are two main lines of development in relation to the exact algorithms for the VRPTW. One is concerned with the general decomposition approach and the solution to certain dual problems associated with the VRPTW. Another more recent direction is concerned with the analysis of the polyhedral structure of the VRPTW. We conclude by examining possible future lines of research in the area of the VRPTW.
    Original languageEnglish
    JournalComputers & Operations Research
    Volume35
    Issue number7
    Pages (from-to)2307-2330
    ISSN0305-0548
    DOIs
    Publication statusPublished - 2008

    Keywords

    • Exact algorithms
    • Time windows
    • Vehicle routing

    Fingerprint

    Dive into the research topics of 'Formulations and exact algorithms for the vehicle routing problem with time windows'. Together they form a unique fingerprint.

    Cite this