Optimization Online


The Dynamic Dispatch Waves Problem for Same-Day Delivery

Mathias Klapp(maklapp***at***ing.puc.cl)
Alan Erera(aerera***at***isye.gatech.edu)
Alejandro Toriello(atoriello***at***isye.gatech.edu)

Abstract: 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.

Keywords: same-day delivery, dynamic vehicle routing, approximate dynamic programming

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Transportation )

Category 3: Applications -- OR and Management Sciences (Supply Chain Management )


Download: [PDF]

Entry Submitted: 10/07/2016
Entry Accepted: 10/09/2016
Entry Last Modified: 10/07/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society