Asymptotically Optimal Policies for Dynamic Ambulance Dispatch

We study the dynamic ambulance dispatch problem in emergency medical services, in which a decision-maker sequentially observes call arrivals and decides which unit to dispatch to service the call, where the service times follow independent and heterogeneous distributions for each station-location pair. This problem is formulated as a Markov decision process, which is intractable due to the curse of dimensionality. To solve this problem, we develop two easy-to-implement heuristics based on a deterministic linear program (LP) and the Lagrangian relaxation. We show that these policies have provably near-optimal performances as the number of units and arrival rates increase. We also show that the deterministic LP-based policy is still asymptotically optimal for general service time distributions. Finally, we examine the performance of these policies and the bounds on numerical experiments, including a case study based on real data from St. Paul, Minnesota