(442e) Effect of Flexible Delivery Windows during Multi-Period Vehicle Routing
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 , 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  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 .
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.
 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.
 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.
 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.
 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.
 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.
 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.
 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).