The One-Dimensional Dynamic Dispatch Waves Problem
| Autor: | Alan L. Erera, Alejandro Toriello, Mathias A. Klapp |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
050210 logistics & transportation
Service (systems architecture) Mathematical optimization Engineering 021103 operations research business.industry Dynamic dispatch 05 social sciences 0211 other engineering and technologies Transportation 02 engineering and technology Set (abstract data type) Dynamic programming Time-driven programming 0502 economics and business A priori and a posteriori Leverage (statistics) business Civil and Structural Engineering Double dispatch |
| Zdroj: | Transportation Science. 52:402-415 |
| ISSN: | 1526-5447 0041-1655 |
| DOI: | 10.1287/trsc.2016.0682 |
| Popis: | 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. The online appendix is available at https://doi.org/10.1287/trsc.2016.0682 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|