Computational methods for static allocation and real-time redeployment of ambulances

Abstract

We propose new approaches to tackle the problems of static and dynamic ambulance fleet allocation. Static ambulance fleet allocation refers to deciding on home bases for ambulances, to which they return after serving calls. The number and location of bases are given. The goal is to keep response times to calls as small as possible. The first part introduces two models for this problem. Both of them are based on the Erlang loss formula. The first model is stylized and serves to illustrate that allocating ambulances to bases in proportion to base offered load is often non-optimal. The second model is similar in spirit to queueing theoretical models developed in the past but uses the but uses the Erlang loss function as a key ingredient. A careful computational comparison shows that the predictions obtained from our model are often more accurate than those produced by previous models, especially in low utilization regimes. This model can be used as a prescreening tool to find promising candidate allocations to be further evaluated through detailed simulation. Dynamic redeployment concerns the real-time relocation of idle ambulances so as to ensure better preparedness. The second part of this dissertation formulates this problem as a dynamic program in a high-dimensional and uncountable state space, and then resorts to approximate dynamic programing (ADP) techniques to obtain approximate solutions. To this end, a specially tailored approximation architecture for the problem is developed. The architecture depends on a small number of free parameters which are tuned using simulated cost trajectories of the system and linear regression. Computational experiments show that the relocation policies obtained from this approach offer significant performance improvements relative to benchmark static-relocation policies. In the third part we use the linear programming approach to ADP on the dynamic-redeployment problem, using the previously developed approximation architecture. We conclude that, although the policies obtained are comparable in quality to those obtained using regression, there are serious issues related to numerical stability. Furthermore, the amount of computation required makes this approach less practical than the regression-based one.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 20 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.