Data-Driven Omniscient Bounds and Greedy Policies for Ambulance Allocation and Dynamic Redeployment

We present an efficient data-driven computational bounding and solution approach for static allocation of ambulance fleet and its dynamic redeployment, where the goal is to position (or re-position) ambulances to bases to maximize the systems service level. We leverage the framework presented, to find data-driven omniscient bounds on the performance of a static location or dynamic redeployment policy. Central to our approach, is a discrete-event simulator to evaluate the impact of ambulance deployments to given call logs of emergency requests. We model ambulance allocation as an approximate submodular maximization problem, and devise a simple and efficient greedy algorithm that produces good solutions for static allocation, and can also be repeatedly employed in real-time for dynamic repositioning. Although the objective is not submodular, we generate data-driven guarantees on solution quality by formulating an omniscient upper bound (in both static and dynamic cases) using integer programming. We show that omniscient dispatch, as well as omniscient location combined with dispatch, are submodular upper bounds. Our experiments based on real data from an Asian city's EMS, demonstrate how optimality gaps can be computed, and that they are small in this setting. The bound formulation that we present is general and can be applied for any alternative data-driven simulation framework or solution. We also test settings with customer abandonment and demonstrate the working of our algorithmic and bounding approach in that setting