Invited ReviewAmbulance location and relocation models
Introduction
This review article traces the evolution of ambulance location and relocation models proposed over the past 30 years. This period was marked by an unprecedented growth not only in computer technology, but also in modeling and algorithmic sophistication, in the performance of mathematical programming solvers, and in the widespread adoption of computer software at several levels of decision making. The literature on ambulance positioning systems truly reflects this evolution. The first models proposed were unsophisticated integer linear programming formulations, but over time more realistic features were gradually introduced, and solution techniques also evolved.
Most of the early models dealt with the static and deterministic location problem. These were meant to be used at the planning stage and they ignored stochastic considerations. Several probabilistic models were then developed to reflect the fact that ambulances operate as servers in a queueing system and are sometimes unavailable to answer a call. Dynamic models are more recent. They address the problem of repeatedly relocating ambulances in the same day to provide better coverage. In recent years, the development of powerful local search algorithms, particularly tabu search (Glover and Laguna, 1997), coupled with the growth of parallel computing (Crainic and Toulouse, 1998) have given rise to a new stream of research that deals effectively with the dynamic nature of the problem. With the newest models and algorithms, large scale problems can be solved rapidly and dynamically in real time, with a high level of accuracy.
There exists a rich literature on emergency vehicles sitting models. The survey by Marianov and ReVelle (1995) provides an overview of the most important models published until that date. Our review is less general since it focuses on ambulance services, but it unavoidably covers some of the same material, albeit with a different emphasis. The Marianov–ReVelle survey ends with an indirect reference to dynamic relocation models integrated within geographic information systems: “rarely have ambulances been positioned at free standing stations” …, “Lastly we have a warming competition … The technique of GIS” (p. 223). Our survey precisely addresses this issue by devoting a section to dynamic relocation models which have just started to emerge. We also report on actual implementations of ambulance location and relocation models. Finally, we provide a synthetic overview, in table form, of all the models we discuss.
The article is structured as follows. In Section 2, we briefly describe the functioning of emergency medical services. Two early models developed for the static case are described in Section 3. An important shortcoming of these models is that they may no longer guarantee adequate coverage as soon as ambulances dispatched to a call become unavailable. Two types of models have been developed to handle the need to provide extra coverage: deterministic models and probabilistic models. These are presented in 4 Deterministic static models with extra coverage, 5 Probabilistic static models with extra coverage, respectively. We have chosen to concentrate on the most important models, leaving aside several minor variants already listed in the articles of ReVelle (1989), Swersey (1994) and Marianov and ReVelle (1995). In Section 6, we provide an account of some of the emerging research in the area of dynamic ambulance repositioning. A summary and conclusions follow in Section 7.
Section snippets
How emergency medical services operate
The chain of events leading to the intervention of an ambulance to the scene of an incident includes the following four steps: (1) incident detection and reporting, (2) call screening, (3) vehicle dispatching and (4) actual intervention by paramedics. Decisions made by emergency services managers are concerned with the second and third steps. The main function of the screening process is to determine the severity of the incident and its degree of urgency (e.g., on a one-to-four scale), and to
Two early models for the static ambulance location problem
Ambulance location models are defined on graphs. The set of demand points is denoted by V and the set of potential ambulance location sites is denoted by W. The shortest travel time tij from vertex i to vertex j of the graph is known. As is common in location theory, assigning demands to a discrete set can be achieved through an aggregation process which unavoidably results in a loss of accuracy. Various techniques have been proposed to measure and control the error bound (Erkut and Bozkaya,
Deterministic static models with extra coverage
Neither LSCM nor MCLP recognizes the fact that on occasions vehicles of several types may be dispatched to the scene of an incident. Also, even if only one vehicle type is used, solving MCLP alone may not provide a sufficiently robust location plan. We present in this section a number of deterministic models developed to deal with the issue of multiple coverage. Probabilistic models will be presented in Section 5.
One of the first models developed to handle several vehicle types is the tandem
Probabilistic static models with extra coverage
One of the first probabilistic models for ambulance location is the maximum expected covering location problem formulation (MEXCLP) due to Daskin (1983). In this model, it is assumed that each ambulance has the same probability q, called the busy fraction, of being unavailable to answer a call, and all ambulances are independent. The busy fraction can be estimated by dividing the total estimated duration of calls for all demand points by the total number of available ambulances. Thus, if vertex
A dynamic model
When siting emergency vehicles, relocation decisions must periodically be made in order not to leave areas unprotected. This was recognized by Kolesar and Walker (1974) who designed a relocation system for fire companies. The ambulance relocation problem is more difficult to tackle since it has to be solved more frequently at very short notice. More powerful solution methodologies are called for in this case. With the development of faster heuristics and advanced computer technologies, it is
Summary and conclusions
There has been an important evolution in the development of ambulance location and relocation models over the past thirty years. The first models were very basic and did not take into account the fact that some coverage is lost when an ambulance is dispatched to a call. Nevertheless, these early models served as a sound basis for the development of all subsequent models. The question of ambulance non-availability was addressed in two main ways. Deterministic models yield solutions in which
Acknowledgements
This research was partially funded by the Canada Research Chair in Distribution Management, by the Fonds de recherche en santé du Québec (FRSQ) under grant 980861, and by the Canadian Natural Sciences and Engineering Research Council (NSERC) under grants OGP0039682 and OGP0184123. This support is gratefully acknowledged. Thanks are due to two referees for their valuable comments.
References (48)
- et al.
An application of a spatially distributed queueing model to an ambulance system
Socio-Economic Planning Sciences
(1992) - et al.
The maximal covering location problem
Papers of the Regional Science Association
(1974) Analysis of the deployment of emergency medical services
Omega
(1981)- et al.
Analysis of aggregation errors for the p-median problem
Computers and Operations Research
(1999) - et al.
Emergency ambulance location using the contiguous zone search routine
Journal of Operations Management
(1982) - et al.
Ambulance deployment analysis: A case study of Bangkok
European Journal of Operational Research
(1987) - et al.
Solving an ambulance location model by Tabu search
Location Science
(1997) - et al.
A dynamic model and parallel Tabu search heuristic for real-time ambulance relocation
Parallel Computing
(2001) - et al.
Validating and applying a model for locating emergency medical services in Tucson, AZ
European Journal of Operational Research
(1990) Covering models for two-tiered emergency medical services systems
Location Science
(1998)
The queueing probabilistic location set covering problem and some extensions
Socio-Economic Planning Sciences
Developing and validating a decision support system for locating emergency medical vehicles in Louisville, Kentucky
European Journal of Operational Research
Review, extension and prediction in emergency services siting models
European Journal of Operational Research
All-advanced life support vs tired-response ambulance systems
Prehospital Emergency Care
The deployment of police, fire, and emergency medical units
Police Operations
A reliability model applied to emergency service vehicle location
Operations Research
The maximal expected covering location problem: Revisited
Transportation Science
Geographic Information Systems: An Introduction
Introduction to Stochastic Programming
Guide Économique et Méthodologique des SIG
Chance constrained programming
Management Science
Principles of Emergency Medical Dispatch
Cited by (621)
Ambulance location routing problem considering all sources of uncertainty: Progressive estimating algorithm
2023, Computers and Operations ResearchAdaptive variable neighbourhood search approach for time-dependent joint location and dispatching problem in a multi-tier ambulance system
2023, Computers and Operations ResearchA survey of dynamic pickup and delivery problems
2023, NeurocomputingA review on hypercube queuing model's extensions for practical applications
2023, Socio-Economic Planning SciencesCapturing delays in response of emergency services in Delhi
2023, Socio-Economic Planning Sciences