Faster Rollout Search for the Vehicle Routing Problem with Stochastic Demands and Restocking

Rollout algorithms are effective heuristics for the single vehicle routing problem with stochastic demands (VRPSD), a prototypical model of logistics under uncertainty. However, they can be computational intensive. To reduce their run time, we introduce a novel approach to approximate the expected cost of a route when executing any rollout algorithm for VRPSD under the restocking strategy. With a sufficiently large number of customers its theoretical speed-up factor is of big-o order 1/3. On a set of instances from the literature, our proposed technique applied to a known rollout algorithm and three variants thereof achieves speed-up factors that range from 0.26 to 0.34 when there are more than fifty customers, degrading only marginally the quality of the resulting routes. Our method also applies to the a priori case, in which case it is exact