The periodic vehicle routing problem with multi-day trips

This work proposes the Periodic Vehicle Routing Problem with Multi-Day Trips, a new routing problem variant that is inspired by regional distribution operations in the industrial gases sector. In this problem, customers provide multiple visiting patterns, a.k.a. schedules, comprising specific days within the planning horizon when they expect to receive product. The goal is then to assign each customer to one valid schedule and design the corresponding routes for each day such that the distribution costs are minimized across the horizon. In our setting, we allow for long-haul routes that cannot be concluded within the course of one shift and the driver must have one or more layovers, in conformance to applicable hours-of-service regulations. To that end, we introduce a set partitioning model and propose a branch-price-and-cut algorithm, extending the classical periodic vehicle routing solution approach to accommodate the multi-day trips. Our approach is able to properly capture the connections between the time periods such that, along with the normal daily routes, the pricing subproblems and their dynamic programming solver also generate routes that extend across multiple days and are compliant with the regulations, all the while ensuring that customers are visited in accordance to their offered schedules. Instances with schedule-dependent demands, a.k.a. service choice, are also supported. We extend literature benchmark instances as well as use an industrial case study to assess the performance of our approach, which we show can routinely solve to guaranteed optimality instances with 20 customers along a 6-day planning horizon.