Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits

We develop restocking-based rollout policies to make real-time, dynamic routing decisions for the vehicle routing problem with stochastic demand and duration limits. Leveraging dominance results, we develop a computationally tractable method to estimate the value of an optimal restocking policy along a fixed route. Embedding our procedure in rollout algorithms, we show restocking-based rollout outperforms a priori-based rollout, demonstrating the value of explicitly considering preemptive capacity replenishment in a rollout approach for dynamic routing. We also demonstrate the effectiveness of basic local search versus more sophisticated mechanisms for the heuristic component of the rollout procedure.