The Dynamic Dispatch Waves Problem for same-day delivery

We study same-day delivery (SDD) systems by formulating the Dynamic Dispatch Waves Problem (DDWP). The DDWP models an order dispatching problem faced by a distribution center, where orders arise dynamically throughout a service day and must be delivered by day's end. At each decision epoch (wave), the system's operator chooses whether or not to dispatch a single vehicle loaded with orders ready for service in order to minimize vehicle travel costs and penalties for unserved requests. We formulate an arc-based integer programming model and design local search heuristics to solve a deterministic DDWP where order arrival times are known in advance. We use the deterministic variant to design an a priori solution approach, and provide two approaches to obtain dynamic policies using the a priori solution. We test and compare solution approaches on two sets of instances with different geography scenarios, size, information dynamism, and order timing variability. The computational results suggest that our best dynamic policy can reduce the average cost of an a priori policy by 9.1% and substantially improves the fraction of orders delivered (order coverage), demonstrating the importance of reactive optimization for dynamic SDD services. We also analyze the tradeoff between two common SDD objectives: total cost minimization versus order coverage maximization. We find structural differences in the dispatch frequency and route duration of solutions for the two different objectives, and demonstrate empirically that small increases in order coverage may require substantial increases in vehicle travel cost.