The vehicle routing problem with time windows and temporal dependencies

Anders Høeg Dohn, Matias Sevel Rasmussen, Jesper Larsen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    In this article, we formulate the vehicle routing problem with time windows and temporal dependencies. The problem is an extension of the well studied vehicle routing problem with time windows. In addition to the usual constraints, a scheduled time of one visit may restrain the scheduling options of other visits. Special cases of temporal dependencies are synchronization and precedence constraints. Two compact formulations of the problem are introduced and the Dantzig–Wolfe decompositions of these formulations are presented to allow for a column generation‐based solution approach. Temporal dependencies are modeled by generalized precedence constraints. Four different master problem formulations are proposed and it is shown that the formulations can be ranked according to the tightness with which they describe the solution space. A tailored time window branching is used to enforce feasibility on the relaxed master problems. Finally, a computational study is performed to quantitatively reveal strengths and weaknesses of the proposed formulations. It is concluded that, depending on the problem at hand, the best performance is achieved either by relaxing the generalized precedence constraints in the master problem, or by using a time‐indexed model, where generalized precedence constraints are added as cuts when they become severely violated. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 273–289 2011
    Original languageEnglish
    JournalNetworks
    Volume58
    Issue number4
    Pages (from-to)273-289
    ISSN0028-3045
    DOIs
    Publication statusPublished - 2011

    Keywords

    • integer programming.
    • branch‐and‐price
    • temporal dependency
    • column generation
    • vehicle routing with time windows
    • set partitioning
    • set covering
    • generalized precedence constraints
    • branch‐and‐cut‐and‐price
    • relaxation
    • time‐window branching

    Fingerprint Dive into the research topics of 'The vehicle routing problem with time windows and temporal dependencies'. Together they form a unique fingerprint.

    Cite this