Optimization Online


The One-Dimensional Dynamic Dispatch Waves Problem

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

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

Keywords: same-day delivery, dynamic dispatch, approximate dynamic program, approximate linear program

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

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

Category 3: Other Topics (Dynamic Programming )

Citation: H. Milton Stewart School of Industrial and Systems Engineering, March 2015

Download: [PDF]

Entry Submitted: 03/18/2015
Entry Accepted: 03/18/2015
Entry Last Modified: 06/30/2015

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