  Unlike its deterministic counterpart, static and stochastic vehicle routing
problems (SS-VRP) aim at modeling and solving real-life operational problems by
considering uncertainty on data. We consider the SS-VRPTW-CR introduced in
Saint-Guillain et al. (2017). Like the SS-VRP introduced by Bertsimas (1992),
we search for optimal first stage routes for a fleet of vehicles to handle a
set of stochastic customer demands, i.e., demands are uncertain and we only
know their probabilities. In addition to capacity constraints, customer demands
are also constrained by time windows. Unlike all SS-VRP variants, the
SS-VRPTW-CR does not make any assumption on the time at which a stochastic
demand is revealed, i.e., the reveal time is stochastic as well. To handle this
new problem, we introduce waiting locations: Each vehicle is assigned a
sequence of waiting locations from which it may serve some associated demands,
and the objective is to minimize the expected number of demands that cannot be
satisfied in time. In this paper, we propose two new recourse strategies for
the SS-VRPTW-CR, together with their closed-form expressions for efficiently
computing their expectations: The first one allows us to take vehicle
capacities into account; The second one allows us to optimize routes by
avoiding some useless trips. We propose two algorithms for searching for routes
with optimal expected costs: The first one is an extended branch-and-cut
algorithm, based on a stochastic integer formulation, and the second one is a
local search based heuristic method. We also introduce a new public benchmark
for the SS-VRPTW-CR, based on real-world data coming from the city of Lyon. We
evaluate our two algorithms on this benchmark and empirically demonstrate the
expected superiority of the SS-VRPTW-CR anticipative actions over a basic
"wait-and-serve" policy.
