Approaches to the Capacitated Vehicle Routing Problem with Planned Downtime

M. Landete Ruíz, M. Leal Palazón, J. F. Monge Ivars, I. Rodríguez Martín

We introduce the Capacitated Vehicle Routing Problem with Planned Downtime, a generalization of the classical vehicle routing problem in which two sets of routes have to be jointly designed: one set considering that all the vehicles of the fleet are available, and another set that considers the scheduled unavailability of a vehicle. Besides routing cost minimization, it is also intended that the routes for the two cases (when all vehicles are available and when one is missing) are as similar as possible in order to reduce the impact on the customers. We formally define two versions of the problem, propose mixed integer programming models, and devise exact branch-and-cut algorithms based on those models. The algorithms are tested on different benchmark instances with up to 40 nodes and 5 vehicles.

Keywords: vehicle routing scheduled downtime branch-and-cut

P. Diaz-Cachinero, J. Contreras, J. I. Muñoz-Hernandez, M. Pourakbari-Kasmaei, M. Lehtonen

A. Mayoral Gómez, D. Gómez González, C. Simón de Blas

L. F. López-Castro, E. L. Solano-Charris, A. Pagès Bernaus

T. Corberán Fabra, I. Plana Andani, J. M. Sanchis Llopis