An Integer L-shaped Method for the Generalized Vehicle Routing Problem with Stochastic Demands

In this work we consider the generalized vehicle routing problem with stochastic demands (GVRPSD). This NP-hard problem combines the clustering aspect of the generalized vehicle routing problem with the uncertainty aspect of the vehicle routing problem with stochastic demands. We propose an integer L-shaped method based on decomposition and branch-and-cut. The subproblem of computing the restocking costs is based on dynamic programming. We consider the preventive restocking strategy which is substantially harder than the standard restocking strategy used by the majority of the published articles for stochastic vehicle routing problems. Using this strategy the vehicle can make a return trip to the depot even before an actual stockout occurs and therefore save travel time. The GVRPSD has not been considered in the literature so far and this first exact solution attempt proves to be able to solve small to medium instances.