New optimality cuts for a single-vehicle stochastic routing problem

In the Vehicle Routing literature, investigations have concentrated on problems in which the customer demands are known precisely. We consider an application in which the demands are unknown prior to the creation of vehicle routes, but follow some known probability distribution. Because of the variability in customer demands, it is possible that the actual total customer demand may exceed the capacity of the vehicle assigned to service those customers. In this case, we have a route failure, and there is an additional cost related to the customer at which the vehicle stocks out. We aim to find routes that minimise the sum of the distance travelled plus any additional expected costs due to route failure. Because of the difficulty of this problem, this investigation only considers a single-vehicle problem. To find optimal routes, the integer L-shaped method is used. We solve a relaxed IP in which the distance travelled is modelled exactly, but the expected costs due to route failure are approximated. Constraints are dynamically added to prevent subtours and to further improve the relaxation. Additional constraints (optimality cuts) are added which progressively form a tighter approximation of the costs due to route failure. Gendreau et al. apply a similar methodology to a closely related problem. They add optimality cuts, each of which imposes a useful bound on the route failure cost for only one solution. In addition to that cut, we generate ‘general’ optimality cuts, each of which imposes a useful bound on the route failure cost for many solutions. Computational results attesting to the success of this approach are presented.