Optimization Online


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

Anirudh Subramanyam (asubramanyam***at***cmu.edu)
Akang Wang (akangw***at***andrew.cmu.edu)
Chrysanthos Gounaris (gounaris***at***cmu.edu)

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.

Keywords: vehicle routing under uncertainty, time window assignment, service consistency, stochastic programming, decomposition, branch-and-bound

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Stochastic Programming

Citation: Transportation Research Part B: Methodological, Volume 117, Part A, 2018, Pages 296-317, https://doi.org/10.1016/j.trb.2018.09.008.


Entry Submitted: 06/08/2018
Entry Accepted: 06/09/2018
Entry Last Modified: 09/20/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society