A branch-and-price algorithm for the Vehicle Routing Problem with Stochastic Demands, Probabilistic Duration Constraint and Optimal Restocking Policy

A. M. Florio, R. F. Hartl, S. Minner, J. J. Salazar González

When demands are stochastic and restocking is allowed, the duration of the resulting routes are also stochastic. We consider the vehicle routing problem with stochastic demands and (probabilistic) duration constraints. We assume optimal restocking, meaning that during route execution replenishment trips to the depot are performed in an optimal way. The resulting optimization problem calls for a set of routes with minimal total expected cost visiting all customers, such that the duration of each route, with some high probability, does not exceed some prescribed limit. We solve the problem exactly for the first time with a novel branch-and-price algorithm. An orienteering-based completion bound is proposed to control the growth of labels in the pricing algorithm. Feasibility of a priori routes is verified either by applying Chebyshev's bounds, or by Monte Carlo simulation and statistical inference.

Palabras clave: Stochastic vehicle routing Branch-and-price

A. A. Juan Perez, J. Panadero, C. Bayliss, L. Martins, A. Freixes, D. Raba

J. M. Belenguer, E. Benavent, Á. Corberán, I. Plana, C. Prins, G. Reinelt, J. M. Sanchis

F. Perea Rojas-Marcos