  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. We
prove that a sampled deterministic equivalent of this stochastic model can be
reduced to a variant of the Consistent Vehicle Routing Problem, and we leverage
this result to develop a new scenario decomposition algorithm to solve it. 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.
