Progressive Focus Search for the Static and Stochastic VRPTW with both
  Random Customers and Reveal Times
  Static stochastic VRPs aim at modeling real-life VRPs by considering
uncertainty on data. In particular, the SS-VRPTW-CR considers stochastic
customers with time windows and does not make any assumption on their reveal
times, which are stochastic as well. Based on customer request probabilities,
we look for an a priori solution composed preventive vehicle routes, minimizing
the expected number of unsatisfied customer requests at the end of the day. A
route describes a sequence of strategic vehicle relocations, from which nearby
requests can be rapidly reached. Instead of reoptimizing online, a so-called
recourse strategy defines the way the requests are handled, whenever they
appear. In this paper, we describe a new recourse strategy for the SS-VRPTW-CR,
improving vehicle routes by skipping useless parts. We show how to compute the
expected cost of a priori solutions, in pseudo-polynomial time, for this
recourse strategy. We introduce a new meta-heuristic, called Progressive Focus
Search (PFS), which may be combined with any local-search based algorithm for
solving static stochastic optimization problems. PFS accelerates the search by
using approximation factors: from an initial rough simplified problem, the
search progressively focuses to the actual problem description. We evaluate our
contributions on a new, real-world based, public benchmark.
