We study same-day delivery (SDD) distribution systems by formulating the Dynamic Dispatch Wave 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 which 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 to solve a deterministic variant, where all request arrival times are known. Next, we describe a class of a priori dispatch policies that plan the vehicle’s routes from the depot for each wave in advance, and provide a dynamic programming approach for determining an optimal policy of this kind. Finally, we propose heuristics and dual bounds for the dynamic case.
Citation
H. Milton Stewart School of Industrial and Systems Engineering, March 2015