The classical Vehicle Routing Problem consists of determining optimal routes for m identical vehicles, starting and leaving at the depot, such that every customer is visited exactly once. In the capacitated version (CVRP) the total demand collected along a route cannot exceed the vehicle capacity. This article considers the situation where some of the demands are stochastic. This implies that the level of demand at each customer is not known before arriving at the customer. In some cases, the vehicle may thus be unable to load the customer's demand, even if the expected demand along the route does not exceed the vehicle capacity. Such a situation is referred to as a failure. The capacitated vehicle routing problem with stochastic demands (SVRP) then consists of minimizing the total cost of the planned routes and of expected failures. Here, penalties for failures correspond to return trips to the depot. The vehicle first returns to the depot to unload, then resumes its trip as originally planned. This article studies an implementation of the Integer L-shaped method for the exact solution of the SVRP. It develops new lower bounds on the expected penalty for failures. In addition, it provides variants of the optimality cuts for the SVRP that also hold at fractional solutions. Numerical experiments indicate that some instances involving up to 100 customers and few vehicles can be solved to optimality within a relatively short computing time.
