The Capacitated Vehicle Routing Problem with Planned Downtime

Abstract The Capacitated Vehicle Routing Problem with Planned Downtime introduced in this work is 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. In this paper, we formally define the problem, propose two mixed integer programming models for it, one of them based on bilevel programming, and devise exact branch-and-cut algorithms based on those models. The algorithms are first compared, and then the most efficient one is tested on different benchmark instances with up to 40 nodes and 5 vehicles.