New Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands

This paper considers the vehicle routing problem with stochastic demands under optimal restocking. We develop an exact algorithm that is effective for solving instances with many vehicles and few customers per route. In our experiments, we show that in these instances, solving the stochastic problem is most relevant (i.e., the potential gains over the deterministic equivalent solution are highest). The proposed branch-price-and-cut algorithm relies on an efficient labeling procedure, exact and heuristic dominance rules, and completion bounds to price profitable columns. Instances with up to 76 nodes could be solved in less than five hours, and instances with up to 148 nodes could be solved in long runs of the algorithm. The experiments also allowed new findings on the problem. The solution to the stochastic problem is up to 10% less costly than the deterministic equivalent solution. Opening new routes reduces restocking costs and in many cases results in solutions with less transportation costs. When the number of routes is not fixed, the optimal solutions under detour-to-depot and optimal restocking are nearly equivalent. However, when the number of routes is limited and the expected demand along a route is allowed to exceed the vehicle capacity, optimal restocking may be significantly more cost-effective than the detour-to-depot policy.