We study same-day delivery systems by formulating the Dynamic Dispatch Waves Problem (DDWP), which models a distribution center where geographically located delivery orders realize dynamically throughout the day. At each decision epoch (wave), the system's operator chooses whether or not to dispatch a vehicle route loaded with orders ready for service, to minimize vehicle travel and penalties for unserved requests. This work extends the one-dimensional variant in Klapp et al. (2016) to any network topology. We formulate an arc-based integer programming model and design local search heuristics to solve the deterministic DDWP and use this variant to design an a priori solution determined only with information disclosed at the start of the operation, and provide three approaches to obtain dynamic policies from it. We design two sets of computational experiments with different settings of geography, size, information dynamism, and order timing variability. Our results suggest that our best dynamic policies can cut the average cost of an a priori policy by 9.1%, achieving a gap of 12.1%. The marginal value of dynamic policies is concentrated in improving order coverage and increases for instances with greater variability and information dynamism. We also analyze the tradeoff between two common SDD objectives: total cost minimization versus maximizing order coverage. We find structural differences in the solution's structure for the two cases, and empirically show marginally increasing sacrifices to be made in vehicle routing efficiency to increase request coverage.
Article
View The Dynamic Dispatch Waves Problem for Same-Day Delivery