The One-Dimensional Dynamic Dispatch Waves Problem

Mathias A. Klapp (), Alan L. Erera () and Alejandro Toriello ()
Additional contact information
Mathias A. Klapp: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332; Engineering School, Pontificia Universidad Católica de Chile, Santiago, Chile
Alan L. Erera: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Alejandro Toriello: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Transportation Science, 2018, vol. 52, issue 2, 402-415

Abstract: We study same-day delivery systems by formulating the dynamic dispatch waves problem (DDWP), which models a depot where delivery requests arrive dynamically throughout a service day. At any dispatch epoch (wave), the information available to the decision maker is (1) a set of known, open requests that remain unfulfilled, and (2) a set of potential requests that may arrive later in the service day. At each wave, the decision maker decides whether or not to dispatch a vehicle, and if so, which subset of open requests to serve, with the objective of minimizing expected vehicle operating costs and penalties for unserved requests. We consider the DDWP with a single delivery vehicle and request destinations on a line, where vehicle operating times and costs depend only on the distance between points. We propose an efficient dynamic programming approach for the deterministic variant, and leverage it to design an optimal a priori policy with predetermined routes for the stochastic case. We then show that fully dynamic policies may perform arbitrarily better than a priori ones, and propose heuristics and dual bounds for this case.

Keywords: same-day delivery; dynamic dispatch; approximate dynamic programming (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (33)

Downloads: (external link)
https://doi.org/10.1287/trsc.2016.0682 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:2:p:402-415

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().