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.

Keywords: Stochastic vehicle routing, Branch-and-price

GT10-2 Transport
September 5, 2019  12:00 PM
I3L10. Georgina Blanes building

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