  This paper considers the vehicle routing problem with stochastic demands
(VRPSD) 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 5 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. Solving the stochastic problem leads to solutions up
to 10% superior to the deterministic equivalent solution. When the number of
routes is not fixed, the optimal solutions under detour-to-depot and optimal
restocking are nearly equivalent. Opening new routes is a good strategy to
reduce restocking costs, and in many cases results in solutions with less
transportation costs. For the first time, scenarios where the expected demand
in a route is allowed to exceed the capacity of the vehicle were also tested,
and the results indicate that superior solutions with lower cost and fewer
routes exist.
