The One-Dimensional Dynamic Dispatch Waves Problem

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.