A scenario decomposition algorithm for strategic time window assignment vehicle routing problems

Anirudh Subramanyam, Akang Wang, Chrysanthos E. Gounaris

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

We study the strategic decision-making problem of assigning time windows to customers in the context of vehicle routing applications that are affected by operational uncertainty. This problem, known as the Time Window Assignment Vehicle Routing Problem, can be viewed as a two-stage stochastic optimization problem, where time window assignments constitute first-stage decisions, vehicle routes adhering to the assigned time windows constitute second-stage decisions, and the objective is to minimize the expected routing costs. To that end, we develop in this paper a new scenario decomposition algorithm to solve the sampled deterministic equivalent of this stochastic model. From a modeling viewpoint, our approach can accommodate both continuous and discrete sets of feasible time window assignments as well as general scenario-based models of uncertainty for several routing-specific parameters, including customer demands and travel times, among others. From an algorithmic viewpoint, our approach can be easily parallelized, can utilize any available vehicle routing solver as a black box, and can be readily modified as a heuristic for large-scale instances. We perform a comprehensive computational study to demonstrate that our algorithm strongly outperforms all existing solution methods, as well as to quantify the trade-off between computational tractability and expected cost savings when considering a larger number of future scenarios during strategic time window assignment.

Original languageEnglish (US)
Pages (from-to)296-317
Number of pages22
JournalTransportation Research Part B: Methodological
Volume117
DOIs
StatePublished - Nov 2018

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Transportation

Fingerprint

Dive into the research topics of 'A scenario decomposition algorithm for strategic time window assignment vehicle routing problems'. Together they form a unique fingerprint.

Cite this