The vehicle routing problem with time windows and temporal dependencies

Publication: Research - peer-reviewJournal article – Annual report year: 2011

View graph of relations

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
Publication date2011
Volume58
Issue4
Pages273-289
ISSN0028-3045
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 4

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
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 5881635