Skip to main content


eCommons@Cornell >
Cornell University Graduate School >
Cornell Theses and Dissertations >

Please use this identifier to cite or link to this item:
Title: Approximate Dynamic Programming Policies And Performance Bounds For Ambulance Redeployment
Authors: Maxwell, Matthew
Keywords: emergency services
approximate dynamic programming
post-decision state
Issue Date: 31-May-2011
Abstract: 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.
Committee Chair: Henderson, Shane G.
Committee Member: Ruppert, David
Lewis, Mark E.
Topaloglu, Huseyin
Discipline: Operations Research
Degree Name: Ph.D. of Operations Research
Degree Level: Doctor of Philosophy
Degree Grantor: Cornell University
No Access Until: 2016-09-29
Appears in Collections:Cornell Theses and Dissertations

Files in This Item:

File Description SizeFormat
msm57thesisPDF.pdf721.49 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us