Exact Approach for the Vehicle Routing Problem with Stochastic Demands and Preventive Returns.

This paper considers a vehicle routing problem where the customer demands are stochastic variables. Because of uncertainty along a route, the vehicle may be unable to load all planned customers' demand. Thus, the vehicle must return to the depot, unload, and then resume its trip. 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, unloads, and resumes 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 minimize 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 paper 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. [ABSTRACT FROM AUTHOR]