(442e) Effect of Flexible Delivery Windows during Multi-Period Vehicle Routing

One of the most vital elements in logistics and supply chain operations is the ability to perform efficient last mile delivery. In solving the so-called Vehicle Routing Problem (VRP), the goal is to designate cost-optimal routes for vehicles to service a set of customers with known demand, respecting the available fleet size and vehicle capacities. The classical VRP focuses on a single period of operation, designing routes for that single time period—usually one day. However, many real-world applications involve interactions among multiple periods which requires planning at a tactical level. For instance, when customers actively place orders during a time horizon and specify a future day window for the delivery, after receiving the order the distributor should decide the day on which to visit each customer, in conjunction with designing the routes for each day. The Multi-Period Vehicle Routing Problem (MPVRP) is an extension of the VRP which addresses such a tactical planning setting that arises in many contexts, including the delivery of packaged industrial gases and auto-carrier transportation, to name but a few.

Several heuristics methods ([1,2,3,4,5]) have been proposed for solving the MPVRP, but to-date very little attention has been paid to developing an exact approach. In [6], for example, the authors proposed a set partitioning formulation to model the problem and a dual ascent algorithm to solve it to guaranteed optimality. Nevertheless, the above methods are deterministic inasmuch they ignore the possibility for receiving orders in the future and the effect that this might have on the optimality and/or feasibility of the designed routes. To address this gap, the authors of [5] accounted for the uncertainty in service requests by assuming the probability for each customer to place an order in the future. They solved a Prize Collecting VRP to determine the set of customers to serve and the corresponding routes for each day. In addition, we developed in our own previous work a multi-stage robust optimization model with binary recourse decisions to tackle customer order uncertainty in the MPVRP [7].

In this work, we create a simulation engine that closely imitates the real world operation of a distributor who manages a portfolio of vendor-managed (VM) customers and also operates a call center through which to receive orders placed ad-hoc by additional “call-in” (CI) customers. Whereas deliveries to VM customers occur at regular intervals, as suggested by some higher-level replenishment planning optimization solution, CI customers proactively place orders during the horizon, at irregular days, and are thus a major source of uncertainty for the daily MPVRP optimization task. Our simulation engine utilizes historic data to build a forecast regarding the potential for CI customer orders to materialize in the near future, and allows for in-sample and out-of-sample realizations of such orders. At each day, the engine solves the MPVRP and assigns delivery dates to all pertinent customers. For this, multiple decision policies are supported, including simple myopic policies often practiced in real life, as well as more sophisticated, look-ahead policies (both deterministic and robust). The resulting schedule is adopted for the immediately following day, and the process is repeated in a rolling horizon fashion.

Using representative data from a real world system, we conduct a comprehensive comparative study to elucidate the performance of the various decision policies. Furthermore, we generate various scenarios regarding the flexibility in terms of day windows that customers might be willing to afford the distributor, and rerun our rolling-horizon simulations to quantify in this manner the overall distribution cost savings that additional customer flexibility provides in this context of multi-period tactical route planning.

References

[1] Cordeau, J.F., Dell’Amico, M., Falavigna, S. and Iori, M., 2015. A rolling horizon algorithm for auto-carrier transportation. Transportation Research Part B: Methodological, 76, pp.68-80.

[2] Wen, M., Cordeau, J.F., Laporte, G. and Larsen, J., 2010. The dynamic multi-period vehicle routing problem. Computers & Operations Research, 37(9), pp.1615-1623.

[3] Estrada‐Moreno, A., Savelsbergh, M., Juan, A.A. and Panadero, J., 2019. Biased‐randomized iterated local search for a multiperiod vehicle routing problem with price discounts for delivery flexibility. International Transactions in Operational Research, 26(4), pp.1293-1314.

[4] Archetti, C., Fernández, E. and Huerta-Muñoz, D.L., 2018. A two-phase solution algorithm for the Flexible Periodic Vehicle Routing Problem. Computers & Operations Research, 99, pp.27-37.

[5] Albareda-Sambola, M., Fernández, E. and Laporte, G., 2014. The dynamic multiperiod vehicle routing problem with probabilistic information. Computers & Operations Research, 48, pp.31-39.

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

[7] Subramanyam, A., Mufalli, F., Lainez-Aguirre, J. M., Pinto, J. M., & Gounaris, C. E., 2017. Robust Multi-Period Vehicle Routing under Customer Order Uncertainty. Available at Optimization Online (2017/04/5947).