A Stochasticoptimizationmodelforreal-Time Ambulance Redeployment
In:
Submitted By saturn2200 Words 6493 Pages 26
Computers & Operations Research 40 (2013) 1972–1978
Contents lists available at SciVerse ScienceDirect
Computers & Operations Research journal homepage: www.elsevier.com/locate/caor
A stochastic optimization model for real-time ambulance redeployment
Joe Naoum-Sawaya a,n, Samir Elhedhli b a b
Engineering Management Program, American University of Beirut, Beirut, Lebanon
Department of Management Sciences, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada
a r t i c l e i n f o
a b s t r a c t
Available online 26 February 2013
When ambulances are engaged in responding to emergency calls, the ability to respond quickly to future calls is considerably compromised. The available ambulances are typically relocated to reestablish maximal coverage. We present a two-stage stochastic optimization model for the ambulance redeployment problem that minimizes the number of relocations over a planning horizon while maintaining an acceptable service level. We conduct computational testing based on the real historical data from the Region of Waterloo Emergency Medical Services. The results show that the optimal relocation strategies can be computed within 40 s of computational time for a desired service level of 90%.
& 2013 Elsevier Ltd. All rights reserved.
Keywords:
Emergency medical systems
Integer programming
1. Introduction
Ambulance deployment is a challenging problem encountered in emergency medical services (EMS). In practice, ambulance deployment is done at two levels. At the strategic level, the locations of the ambulance stations are determined taking into account the long term growth of the population. Many factors, such as the aging population and the expected rise in demand for medical services affect the long term planning of ambulance deployment. At the operational level, ambulance dispatching and redeployment are planned. Ambulance dispatching is the process of determining the ambulances that should respond to a received emergency call. Typically, when some ambulances are engaged in responding to emergency calls, the ability to respond quickly to future calls is compromised. The redeployment problem consists of relocating the available ambulances to reestablish maximum coverage. Coverage refers to the area that can be serviced within a certain amount of time by an available ambulance. In 2006–2007, the Region of Waterloo Emergency Medical
Systems (ROWEMS) accounted for 25,877 redeployment which constituted 27% of the total number of ambulance activities for that period. The current performance standard for ROWEMS requires that 90% of emergency calls should be reachable by an ambulance within 10 min and 30 s. A new Ambulance Act
Regulation which requires that an ambulance should arrive on scene in less than 8 min has been recently introduced. Since
n
Corresponding author.
E-mail addresses: joe.sawaya@aub.edu.lb (J. Naoum-Sawaya), elhedhli@uwaterloo.ca (S. Elhedhli).
0305-0548/$ - see front matter & 2013 Elsevier Ltd. All rights reserved. http://dx.doi.org/10.1016/j.cor.2013.02.006 Downloaded from http://www.elearnica.ir
adding new ambulances is associated with a very high cost, EMS managers are relying on increasing the utilization of the current fleet by employing advanced decision support systems to help them achieve better redeployment strategies. Currently, relocations in ROWEMS are made using a preplanned compliance table which indicates where the ambulances should be located given a certain number of available ambulances. The compliance table does not take into account the time of day, does not indicate which ambulances should be moved, and relies on the experience of the operator when making the relocation decisions.
As thoroughly presented in Brotcorne et al. [3], ambulance location models can be classified into two main categories: the deterministic models that are typically used at the planning stage and the probabilistic models that account for the fact that ambulances cannot be always available to respond to emergency calls. Early ambulance location optimization models focused on static and deterministic strategies used for long term planning.
The set covering location problem (SCLP) presented by Toregas et al. [19] aims at minimizing the number of ambulances needed to cover a certain area. The maximal covering location problem
(MCLP) presented by Church and ReVelle [5] maximizes the area that can be covered given a fixed number of ambulances. Both the
SCLP and the MCLP consider single coverage in which a given point is covered if it can be reached within t min by an ambulance. Other models introduced by Hogan and ReVelle [13] and Gendreau et al. [9] assume double coverage which requires that all the demand be covered within t1 minutes while a certain fraction of the demand be covered within t2 minutes. Although the SCLP, the MCLP, and the double coverage models are used for long term planning, they unrealistically assume that all the ambulances are always available when an emergency call is
J. Naoum-Sawaya, S. Elhedhli / Computers & Operations Research 40 (2013) 1972–1978
received. The maximum expected covering location problem
(MEXCLP) of Daskin [7] accounts for ambulance unavailability and maximizes the expected value of coverage given a fixed number of ambulances. Extensions for MEXCLP have been presented in Batta et al. [2], ReVelle and Hogan [17], and Ball and
Lin [1]. Another line of research uses queuing theory to analyze the EMS probabilistic models. The hypercube model which was introduced in Larson [15] has been extensively applied by Burwell et al. [4], Goldberg [12], and Takeda et al. [18] to analyze EMS systems. Moreover, Zaki et al. [20] and Ingolfsson et al. [14] adopted simulation to closely model EMS systems.
More recently, dynamic ambulance relocation models aimed for short term operational planning were introduced. The dynamic relocation models take into account the current location of the ambulances to provide a redeployment strategy that reestablishes maximum coverage after an ambulance is dispatched. Dynamic relocation models are repeatedly solved in real time, and since it is critical to find a relocation strategy in a very short time, heuristics have been typically applied. Gendreau et al.
[10] presented a double coverage model for dynamic relocation and applied a tabu search algorithm for solving the resulting model. They also consider practical features such as avoiding moving the same ambulance in successive redeployments, avoiding repeated round trips between the same two locations, and avoiding long trips. Gendreau et al. [11] formulated and solved a dynamic problem arising in the relocation of physician vehicles.
Maxwell et al. [16] presented a dynamic programming model for the ambulance relocation problem and an approximation is constructed to account for the high-dimensional state space of the problem. The approximation is tuned using simulation.
In this paper, we propose a two-stage stochastic program for the ambulance relocation problem. In the first stage, the model minimizes the number of relocations, while in the second stage, it minimizes the number of calls that are not reached within the desired service time. The presented formulation models time explicitly for a given planning horizon. This permits the modeling of some complicating features such as the shift schedules of the ambulances and the typical change in demand during the day.
The rest of this paper is organized as follows. The stochastic optimization model is presented in Section 2. Computational tests are presented in Section 3. Section 4 concludes.
2. A two-stage stochastic programming formulation
We model the ambulance redeployment problem as a twostage stochastic program based on the scenarios [6]. In the first stage, the model determines the optimal placement of the ambulances. These decisions are made prior to knowing the exact location of future emergency calls. The uncertainty in the location of the emergency calls is represented by a finite set of scenarios that represent the second stage of the model, where each scenario contains a random outcome for the locations of the emergency calls. Second stage decisions model the assignment of ambulances to emergency calls. The objective of the model is to minimize the number of ambulance relocations while meeting a minimum performance level. The scenarios are formed based on the historical data. Emergency Medical Services keep detailed historical data of all the ambulance activities which constitute a valuable asset that we use in our relocation model. For instance, the historical data contains the exact location, time of the day, and the ambulance travel time. Therefore a scenario can be built by looking at the number and location of calls for a particular day.
To model the dynamic relocation problem, we define the following notation:
1973
Indicies, parameters, and sets: i: index for ambulances, i A I. j: index for ambulance stations, j A J. t: index for time periods, t A T. s: index for scenarios, s A S.
Cj ¼ the capacity of station j.
N ¼total number of calls.
U(t) denotes the set of time periods t 0 A T, where an ambulance will not be available if it responds to the call at time period t.
8
> 1 if assigning ambulance i to station j requires a
<
dij ¼
ajts ¼
r ijt ¼
relocation,
0 otherwise:
8
> 1 if a call is received in time period t of scenario s
<
>
:
>
:
0
8
>1
>
>
<
>
>
>
:
(
gts ¼
and is reachable within target time fromstation j, otherwise: if ambulance i can reach station j before time period t ðif ordered to relocateat time t ¼ 0 from its current locationÞ,
0
otherwise:
1
0
if a call is received in time period t in scenario s, otherwise: ri ¼ Cost of relocating ambulance i. l ¼ Cost associated with not servicing an emergency call within the desired time. ps ¼ Probability of scenario s occurring. p ¼ Percentage of calls that should be reached within the target time.
Decision variables
(
1 if ambulance i is assigned to station j, yij ¼
0 otherwise:
8
> 1 if ambulance i is assigned to the call received in time
<
period t of scenario s, xits ¼
>
:
0 otherwise:
The two-stage stochastic program is formulated as follows:
!
XX
X
X X min ri dij yij þ l ps
1À xits , ð1Þ sAS
iAI jAJ
s:t:
X xits À ðr ijt ajts yij Þ r0,
tAT
iAI
8i A I, 8t A T, 8s A S,
ð2Þ
jAJ
X
xits þ
xit0 s r1,
8i A I, 8t A T, 8s A S,
ð3Þ
0
t A UðtÞ
X xits r gts ,
8t A T, 8s A S,
ð4Þ
iAI
X yij r C j ,
8j A J,
ð5Þ
XXX xits Z pN,
ð6Þ
iAI
iAI t ATsAS
yij A f0,1g, xits A f0,1g,
8i A I, 8j A J, 8t A T, 8sA S:
ð7Þ
The objective function has two components. The first stage minimizes the number of relocations while the second stage minimizes the number of emergency calls that are not serviced
1974
J. Naoum-Sawaya, S. Elhedhli / Computers & Operations Research 40 (2013) 1972–1978
within the target time. Similar to Gendreau et al. [10], parameter ri is a penalty coefficient associated with relocating ambulance i. A large penalty is hence enforced on ambulances that have been relocated frequently in the past or on ambulances that are close to the end of their shifts. We note that the penalty coefficients are updated each time the model is solved. Constraints (2) indicate that ambulance i can service a call within the desired time if it is assigned to a station from which the call can be reached within the target time. We note that if ambulance i is not currently at station j and is ordered to relocate to station j, parameter rijt ensures that the relocation travel time of ambulance i is accounted for and hence ambulance i is not considered present at station j before it actually arrives. Constraints (3) ensure that if ambulance i is assigned to service the call of time period t then this ambulance will be unavailable for all the time periods t 0 A UðtÞ. Constraints (4) ensure that at most one ambulance is assigned to each call.
Constraints (5) ensure that the maximum number of ambulances assigned to station j does not exceed its maximum capacity Cj.
Constraints (6) indicate that at least p% of the calls should be reached within the target time. We note that constraints (6) can be dropped from the model if no service level is enforced.
Generating scenarios for the model is relatively easy since all
EMS keep detailed historical data. For our computational testing, the Region of Waterloo EMS provided us with 2 years of historical data consisting of 95,840 calls. In the cases where historical data is not available, simulation can be used to generate the scenarios as in Domenica et al. [8].
2.1. Length of the time periods
To calculate the length of each of the time periods t A T, we assume that the emergency calls arrive according to a Poisson distribution with arrival rate l calls/hour. The probability of having 0 or 1 call in a time period t is then
Pð0Þ þ Pð1Þ ¼ eÀlt þ lteÀlt ¼ ð1 þ ltÞeÀlt :
ð8Þ
For small Àlt, eÀlt can be approximated as eÀlt I1Àlt. Considering that the time periods should be short enough to guarantee that the probability of having 0 or 1 call is at least 1ÀE, Eq. (8) leads to ð1þ ltÞð1ÀltÞ Z 1ÀE,
ð9Þ
2
1Àl t 2 Z 1ÀE,
ð10Þ pffiffiffi implying that the time period should be at most ð E=lÞ. As an example, for E ¼ 0:01 and l ¼ 2 calls/hour, the time period should be of length less than 3 min which implies 20 time periods for a planning horizon of 1 h.
in turn divided into 25 unit squares that are identified by a unique
Universal Transverse Mercator (UTM). The historical data indicates the UTM address of each emergency call. To test our model, we generated 128 problems by randomly sampling the historical data. The target service time Tmax was set to 10 min 30 s, the travel times were computed using a constant vehicle speed of 50 km/h, and the distances are computed based on the
Euclidean norm. We evaluate the quality of the solution in terms of the percentage of emergency calls that are reached within target time and in terms of the number of relocations. To account for the change in the arrival rates of emergency calls, the day is divided into 48 periods of 30 min each and the arrival rates are calculated for these periods. Given the arrival rates, the planning horizon should be split to time periods of t ¼1 min to guarantee a probability of 99% that 0 or 1 call is received in each time period
(see Section 2.1 for the details). Finally, the number of ambulances for each shift is given. The historical data are summarized in Table 1. We notice that the rate of emergency calls increases from 6:00 a.m. until noon, peaks at 11:00 a.m. and 1:00 p.m., is stable in the afternoon and the evening, and starts to decrease at around 8:00 p.m. until 6:00 a.m. (Fig. 2).
Computational results for 30 tests occurring at different times of the day are shown in Table 2. Column (1) indicates the test number. Column (2) indicates the time of the day. Columns (3),
(4) and (5) indicate the number of ambulances on duty, the number of time periods in the planning horizon and the number of generated scenarios respectively. The number of relocations is displayed in Column (6), the service level is displayed in Column
(7), and finally the computational time in seconds is displayed in
Column (8). The planning horizon is fixed to 120 periods (2 h) and
50 emergency call scenarios are generated for each of the tests. The number of ambulances on duty is set to the actual number of ambulances on shift. The computational results show that the optimal relocation strategy is computed in less than 39 s. The service level for the computed relocation strategies varies between
91% and 96% of calls serviced within the 10 min 30 s time limit. The number of relocations varies between 1 and 4. Being able to solve the redeployment problem in less than 40 s gives the ROWEMS an edge in improving the performance of their service and more importantly it maintains its service level above 90%.
In Table 3, we evaluate the effect of the planning horizon on the performance of the algorithm. We conduct two separate tests, the first occurring at 3:00 (tests 31–72) and the second occurring at 14:00 (tests 41–50). For tests (31–40), we set the number of
3. Computational results
Problem (1)–(7) is implemented in Matlab and solved using
CPLEX 11.0. There are two important sets of decision variables in the formulation. These are the assignment of ambulances to stations (variables yij) and the assignment of ambulances to calls
(variables xits). If the ambulances are assigned to stations, the problem reduces to identifying which calls are serviced within the target time. Since the number of yij variables is smaller than the number of xits variables, it is desired to first branch on yij. CPLEX was setup to first branch on the first stage variables yij before branching on the xits variables.
The test instances are generated from the historical data that were provided by ROWEMS. The region of Waterloo has a
2
geographic area of 1382 km and is displayed in Fig. 1. The region is divided into 76 squares, each with an area of 25 km2. These are
Fig. 1. Region of Waterloo.
J. Naoum-Sawaya, S. Elhedhli / Computers & Operations Research 40 (2013) 1972–1978
1975
Table 1
Summary of the historical data.
Time of day
Emergency calls arrival rate per hour Ambulances on shift Time
Fig. 2. Change in the expected number of emergency calls during a 24 h period.
ambulances on duty to 7, vary the planning horizon from 70 to
160 min in steps of 10, and fix the number of scenarios to 50. We notice that this change has little effect on the computational time which varies between 29 and 33 s, with no increase in computational time as the number of time periods increases. The service level varies between 90% and 97% while the number of relocations varies between 1 and 2. For tests (41–50), the number of ambulances on duty is set to 14 and the planning horizon is varied between 70 and 160. Similar to tests (31–40) we notice that the increase in the planning horizon has little effect on the computational time, being between 31 and 36 s. The service level varies between 91% and 97% and the number of relocations varies between 0 and 2.
In Table 4, we evaluate the effect of the number of ambulances on the performance of the algorithm. We conduct two separate tests, the first occurring at 8:00 (tests 51–61) and the second
occurring at 12:00 (tests 62–72). The number of ambulances is gradually increased from 5 to 15, the planning horizon is fixed to
120 min, and the number of scenarios generated for each test is set to 50. The results show that the computational time is between 27 and 40 s. As expected, the number of relocation decreases as the number of ambulances decreases.
In Table 5, we evaluate the effect of the number of scenarios on the performance of the algorithm. We vary the number of scenarios between 20 and 160 in steps of 10. We conduct two separate tests, the first occurring at 2:00 (tests 73–87) and the second occurring at 14:00 (tests 88–102). For (tests 73–87), the computational time increases from 28 to 44 s while the service level varies between 90% and 97%. The number of relocations is low and varies between 0 and 2 relocations. For (tests 88–102), the computational time increases from 35 to 43 s while the service level varies between 90% and 97% and the number of
1976
J. Naoum-Sawaya, S. Elhedhli / Computers & Operations Research 40 (2013) 1972–1978
Table 2
Computational results for tests occurring at different times of the day.
Table 4
Evaluating the effect of the number ambulances on duty.
Test Time Ambulances of day on duty
(1) (2)
(3)
Time
Number of Relocations Service periods scenarios level (4)
(5)
(6)
(7)
CPU
(s)
(8)
Test Time Ambulances of day on duty
(1) (2)
(3)
Time
Number of Relocations Service periods scenarios level (4)
(5)
(6)
(7)
relocations varies between 0 and 2 relocations. The computational results show a clear increasing trend in the computational time as the number of scenarios increases.
In Table 6, we evaluate the impact of the new Ambulance Act
Regulation which requires that an ambulance should arrive on scene in less than 8 min and compare the results against the current requirement of 10 min and 30 s service time. As expected, the new stricter requirements have a negative impact on the service level and the number of relocations. With an 8 min service time, the service level is always lower than the desired 90% level. For that we had to lower the required service level (constraint (6)) to 80% so that the model becomes feasible. On average, the service level is 84.85% while with a 10 min 30 s service time the service level is 92.08%. The relocations also increase as the service time is decreased. On average with an 8 min service time, the number of relocations is 3 compared to 1.38 for the 10 min 30 s service time standard.
Finally, we test if the 90% service level with 8 min service time can be attained if new ambulances are added. The results are shown in Fig. 3. As expected, adding ambulances increases the service level. The service level increases from 84.93% to 87.05% with 10 additional ambulances however fails to reach the 90% required service level even if 20 ambulances are added. Most importantly, these results suggest that with the new service time standard, ROWEMS will fail to meet the required 90% service level even if additional ambulances are added to the fleet and therefore
ROWEMS should seek other options such as building new stations and relocating existing ones in order to meet the minimum service levels. In fact, ROWEMS have started another study to find new station locations that improve their service level.
3.1. Using the Manhattan metric to compute the travel distance
Besides the Euclidean norm, the Manhattan metric is typically used to estimate the travel distances. In some regions and mostly
J. Naoum-Sawaya, S. Elhedhli / Computers & Operations Research 40 (2013) 1972–1978
Manhattan metric and compare them to using the Euclidean distance. The results are shown in Table 7. We notice that the problems that use the Manhattan metric have a higher number of relocations and a lower service level than the problems that use the Euclidean distance. This is since the distances estimated using the Manhattan metric are typically larger than those estimated when using the Euclidean distance. For tests 116–128, using the
Manhattan metric achieves an average number of relocations of
1.69 and an average service level of 91%, while for the same problems, by using the Euclidean distance the number of relocations is 1.38 and the service level is 92.15% on average.
in downtown areas, the road network has a geography that resembles to a rectangular grid where a Manhattan metric provides a more realistic estimate of the travel distances. In this section, we evaluate the results that are obtained when using the
Table 5
Evaluating the effect of the number of scenarios.
Test Time Ambulances of day on duty
(1) (2)
(3)
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
Time
Number of Relocations Service periods scenarios level (4)
(5)
(6)
(7)
0
0.73
2
90%
93.93%
97%
1977
35
38.6
43
4. Conclusion
In this paper, we considered the ambulance relocation problem for Emergency Medical Services, an important problem that aims to maximize the efficiency of the Emergency Medical Service
Units by redeploying available ambulances to reestablish maximum coverage when some ambulances are responding to emergency calls. Since relocations constitute a large portion of ambulance activities, we presented a stochastic optimization model that minimizes the number of relocations over a planning horizon while maintaining an adequate service level. The stochastic optimization model was based on the historical data that is typically available for Emergency Medical Services and constitutes a valuable resource for efficient planning.
Computational testing conducted using real data from the
Region of Waterloo EMS showed that the optimal relocation
strategies can be computed within 40 s of computational time. To the satisfaction of the ambulance crews, the number of relocations was low for a planning horizon of 2 h.
Acknowledgments
The authors would like to thank Armann Ingolfsson for suggesting the maximum length of the time period of Section
2.1 and the Region of Waterloo Emergency Medical Services for providing the historical data and the support for this research.
This research is also financially supported by the Natural Sciences and Engineering Research Council (NSERC) and the Mathematics of Information Technology and Complex Systems (MITACS).
References
[1] Ball M, Lin F. A reliability model applied to emergency service vehicle location. Operations Research 1993;41:18–36.
[2] Batta R, Dolan J, Krishnamorthy N. The maximal expected covering location model revisited. Transportation Science 1989;23:277–87.
[3] Brotcorne L, Laporte G, Semet F. Ambulance location and relocation models.
European Journal of Operational Research 2003;147:451–63.
[4] Burwell T, Jarvis J, McKnew M. Modeling co-located servers and dispatch ties in the hypercube model. Computers & Operations Research 1993;20:113–9.
[5] Church R, ReVelle C. The maximal covering location problem. Papers Regional
Science Association 1974;32:101–18.
[6] Dantzig G. Linear programming under uncertainty. Management Science
1955;1:197–206.
[7] Daskin M. The maximal expected covering location model: formulation, properties, and heuristic solution. Transportation Science 1983;17:48–70.
[8] Domenica ND, Lucas C, Mitra G, Valente P. Scenario generation for stochastic programming and simulation: a modelling perspective. IMA Journal of
Management Mathematics 2009;20(1):1–38.
[9] Gendreau M, Laporte G, Semet F. Solving an ambulance location model by tabu search. Location Science 1997;5:75–88.
[10] Gendreau M, Laporte G, Semet F. A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel Computing
2001;27:1641–53.
[11] Gendreau M, Laporte G, Semet F. The maximal expected coverage relocation problem for emergency vehicles. Journal of the Operational Research Society
2006;57:22–8.
[12] Goldberg J. Operations research models for the deployment of emergency services vehicles. EMS Management Journal 2004;1:20–39.
[13] Hogan K, ReVelle C. Concept and applications of backup coverage. Management Science 1986;32:1434–44.
[14] Ingolfsson A, Erkut E, Budge S. Simulating a single start station for Edmonton
EMS. Journal of the Operational Research Society 2003;54:736–46.
[15] Larson R. A hypercube queuing model for facility location and redistricting in urban emergency services. Computers & Operations Research 1974;1:67–95.
[16] Maxwell MS, Restrepo M, Henderson SG, Topaloglu H. Approximate dynamic programming for ambulance redeployment. Informs Journal on Computing
2010;22:266–81.
[17] ReVelle C, Hogan K. The maximum availability location problem. Transportation Science 1989;23:192–200.
[18] Takeda R, Widmer J, Morabito R. Analysis of ambulance decentralization in an urban medical emergency service using the hypercube queuing model.
Computers & Operations Research 2007;34:727–41.
[19] Toregas C, Swain R, ReVelle C, Bergman L. The location of emergency service facilities. Operations Research 1971;19:1363–73.
[20] Zaki A, Cheng H, Parker B. A simulation model for the analysis and management of an emergency service system. Socio-Economic Planning Sciences
1997;31:173–89.
