(626d) Periodic Vehicle Routing with Trips Spanning Multiple Days

One of the most vital elements in logistics and supply chain operations is the ability to perform efficient last-mile delivery. The Vehicle Routing Problem (VRP) has emerged as an important class of problems to address the optimization of this integral step of a supply chain [1]. The classical VRP focuses on optimization a single day (or other suitable defined period) of operation. However, many real-world applications such as waste collection, healthcare, industrial gas distribution [2], and maritime surveillance [3], among others, involve interactions among multiple periods. In multi-period routing, selecting the feasible visiting schedules for customers and designing routes in each day should be considered together. This setting is addressed by a generalized class of routing problems known as the Periodic VRP (PVRP).

It is quite common in practice that, due to long distances, reaching a customer might take more than a single work day. This usually happens because of applicable regulations on transportation dictating that a driver does not work more than a certain number of consecutive hours without a rest period. However, co-optimizing routes that extend across multiple days along with the normal routes that conclude in the course of a day is a challenging task, both from a modeling as well as solving point of view. We call this variant the Periodic Vehicle Routing with Multiple-Day Trips (PVRPMDT). The archetypal PVRP seeks to assign visiting schedules to customers and to determine a set of minimum-cost routes to be traversed each day by a fleet of vehicles, such that customers are served with regard to their schedules and such that vehicle capacities are respected [4]. The PVRPMDT extends this setting by allowing (a subset of) vehicles to travel across multiple days in the planning horizon, while respecting their route duration limits and/or the necessary intermittent rest periods.

PVRPs are inherently combinatorial complex problems, and there is sparse literature on exact solution methods. Two notable contributions come from [4] and [5], where the authors addressed the archetypal PVRP and the PVRP with customer time windows, respectively. However, with the addition of the multiple-day trips feature, there is no existing approach that can directly accommodate this variant. The study of [3] proposes a branch-and-price approach to address a setting that is partly related to PVRPMDT. In that work, traveling time limits are within different time scales. Nevertheless, the target problem is different than a VRP and is mostly classified as a maritime surveillance problem.

Here, we are proposing an adjusted branch-price-and-cut approach (BPC) [6] to solve the PVRPMDT. Our algorithm is the first one in the open literature to be able to address this problem. We first describe this setting using a set partitioning model, which features variables whose number increases exponentially with the size of the problem. These variables (columns) represent the routes that can also extend across multiple days. New columns are dynamically generated by solving the pricing subproblems as Shortest Path Problems with Resource Constraints (SPPRC) via dynamic programming [7]. Our approach extends the classic PVRP modeling and solution techniques in two directions. First, our model is able to capture the connections between the time periods so that the routes spanning across multiple days are correctly assigned days of customer visit with respect to the offered schedules of the customers. Second, the SPPRC and its dynamic programming solver are adjusted so that they can correctly generate and manage routes that extend across multiple days. A variety of expediting techniques, such as variable fixing [8], ng-routes [9], and route enumeration [10] are also incorporated for solving the SPPRCs more efficiently. Moreover, in order to further tighten the relaxation space, valid cuts, such as rounded capacity inequalities and limited-memory subset row cuts [6] that are conformed to handle the multi-day trips feature, are incorporated.

We evaluate our approach on PVRPMDT benchmark instances that we generate to this purpose using industrial data. We also used the classic PVRP instances and generated new PVRPMDT instances to act as the literature benchmark instances. Our computational studies verify our framework’s ability in addressing this new periodic vehicle routing problem class efficiently and show that PVRPMDT solutions can expose significant efficiencies compared to their PVRP counterparts involving only single-day routes.

[1]. Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.

[2]. Campbell, A. M., & Wilson, J. H. (2014). Forty years of periodic vehicle routing. Networks, 63(1), 2-15.

[3]. Fauske, M. F., Mannino, C., & Ventura, P. (2020). Generalized Periodic Vehicle Routing and Maritime Surveillance. Transportation Science, 54(1), 164-183.

[4]. Baldacci, R., Bartolini, E., Mingozzi, A., & Valletta, A. (2011). An exact algorithm for the period routing problem. Operations research, 59(1), 228-241.

[5]. Rothenbächer, A.K., 2019. Branch-and-price-and-cut for the periodic vehicle routing problem with flexible schedule structures. Transportation Science, 53(3), pp.850-866.

[6]. Pecin, D., Pessoa, A., Poggi, M. and Uchoa, E. (2017). Improved branch-cut-and price for capacitated vehicle routing. Mathematical Programming Computation, 9(1), pp.61-100.

[7]. Pugliese, L.D.P. and Guerriero, F., 2013. A survey of resource constrained shortest path problems: Exact solution approaches. Networks, 62(3), pp.183-200.

[8]. Irnich, S., Desaulniers, G., Desrosiers, J. and Hadjar, A. (2010). Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS Journal on Computing, 22(2), pp.297-313.

[9]. Baldacci, R., Mingozzi, A. and Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations Research, 59(5), pp.1269-1283.

[10]. Baldacci, R. and Mingozzi, A., (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120(2), p.347