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.