Approximate Dynamic Programming Policies And Performance Bounds For Ambulance Redeployment
Ambulance redeployment is the practice of dynamically relocating idle ambulances based upon real-time information to reduce expected response times for future emergency calls. Ambulance redeployment performance is often measured by the fraction of "lost calls" or calls with response times larger than a given threshold time. This dissertation is a collection of four papers detailing results for designing ambulance redeployment policies and bounding the performance of an optimal ambulance redeployment policy. In the first paper ambulance redeployment is modeled as a Markov decision process, and an approximate dynamic programming (ADP) policy is formulated for this model. Computational results show that the ADP policy is able to outperform benchmark policies in two different case studies based on real-life data. Results of practical concern including how the ADP policy performs with varying call arrival rates and varying ambulance fleet sizes are also included. In the second paper we discuss ADP tuning procedures, i.e., the process of selecting policy parameters to improve performance. We highlight limitations present in many ADP tuning procedures and propose direct-search tuning methods to overcome these limitations. To facilitate direct-search tuning for ambulance redeployment, we reformulate the ADP policy using the so-called "post-decision state" formulation. This reformulation allows policy decisions to be computed without computationally expensive simulations and makes direct- search tuning computationally feasible. In the third paper we prove that many ADP policies are equivalent to a simpler class of policies called nested compliance table (NCT) policies that assign ambulances to bases according to the total number of available ambulances. Furthermore, we show that if ambulances are not assigned to the bases dictated by the NCT policy, the ADP-based policies will restore compliance to the NCT policy without dispatcher intervention. In the fourth paper we derive a computationally tractable lower bound on the minimum fraction of lost calls and propose a heuristic bound based upon simulation data from a reference policy, i.e., a policy we believe to be close to optimal. In certain circumstances, both bounds can be quite loose so we introduce a stylized model of ambulance redeployment and show empirically that for this model the lower bound is quite tight.
emergency services; approximate dynamic programming; post-decision state
Henderson, Shane G.
Ruppert, David; Lewis, Mark E.; Topaloglu, Huseyin
Ph.D. of Operations Research
Doctor of Philosophy
Dissertation or Thesis