Exact approach to solve the Capacitated Vehicle Routing Problem with Stochastic Demands and Restocking Policy Event

Event details

This talk considers a vehicle routing problem where the customer demands are stochastic variables. Due to uncertainty, along a route the vehicle may be unable to load all planned customers' demand. The vehicle has to return to the depot, unload and then resume its trip. In order to avoid unplanned return trips to the depot, one may decide to make some preventive return: even if it is not full, the vehicle returns to the depot, unload and resume its trip at the next customer. These preventive returns avoid visiting the same customer twice at the expense of possibly making an unneeded return. In this paper, we propose an exact procedure for designing routes to minimise the total expected cost of the routes. It consists of a branch-and-cut algorithm based on the L-shaped method for stochastic programs with binary first-stage variables. The talk provides lower bounds and cuts on the expected costs, and describes the results of computational analysis of a computer implementation on benchmark instances. Instances involving up to 100 customers have been solved to optimality.