Free Essay

A Stochasticoptimizationmodelforreal-Time Ambulance Redeployment

In: Science

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

Emergency calls arrival rate per hour Ambulances on shift 6:00–6:30
6:30–7:00
7:00–7:30
7:30–8:00
8:00–8:30
8:30–9:00
9:00–9:30
9:30–10:00
10:00–10:30
10:30–11:00
11:00–11:30
11:30–12:00
12:00–12:30
12:30–13:00
13:00–13:30
13:30–14:00
14:00–14:30
14:30–15:00
15:00–15:30
15:30–16:00
16:00–16:30
16:30–17:00
17:00–17:30
17:30–18:00

2.02
2.34
2.68
3
3.82
3.72
4.7
4.86
4.98
5.12
5.14
4.74
4.86
4.94
5.12
5.06
4.78
4.82
4.84
4.76
4.56
4.54
4.72
4.74

7
8
8
9
10
10
12
12
12
12
12
12
14
14
14
14
14
14
15
15
16
16
16
16

18:00–18:30
18:30–19:00
19:00–19:30
19:30–20:00
20:00–20:30
20:30–21:00
21:00–21:30
21:30–22:00
22:00–22:30
22:30–23:00
23:00–23:30
23:30–00:00
00:00–00:30
00:30–1:00
1:00–1:30
1:30–2:00
2:00–2:30
2:30–3:00
3:00–3:30
3:30–4:00
4:00–4:30
4:30–5:00
5:00–5:30
5:30–6:00

4.86
4.64
4.84
4.22
4.26
4.08
4.04
4.02
3.58
3.14
3.18
2.84
2.76
2.72
2.64
2.72
2.66
2.48
1.98
1.8
1.62
1.56
1.62
1.62

16
16
15
15
13
13
11
11
11
11
11
11
9
9
9
9
9
9
8
8
7
7
7
7

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)

CPU
(s)
(8)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120
120

51
52
53
54
55
56
57
58
59
60
61

120
120
120
120
120
120
120
120
120
120
120

06:02
07:15
07:19
07:28
08:22
08:34
08:55
10:04
10:27
10:30
10:59
12:31
13:21
14:00
14:12
14:27
15:01
16:31
17:53
19:36
21:57
22:15
23:56
00:54
01:27
02:58
03:48
04:12
05:23
05:53

7
8
8
8
10
10
10
12
12
12
12
14
14
14
14
14
15
16
16
15
11
11
11
9
9
9
8
7
7
7

50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50

2
2
2
3
2
2
1
2
2
2
1
1
1
2
1
2
2
1
1
2
3
3
4
2
2
2
3
1
1
1

93
92
93
96
94
91
91
95
96
92
93
94
91
92
91
92
93
94
92
93
92
91
91
95
93
93
91
94
92
92

27
29
34
29
27
31
27
32
29
34
26
30
36
30
27
27
22
27
36
22
34
35
30
39
29
35
22
33
33
27

Min
Avg.
Max

1
1.87
4

91%
92.73%
96%

22
29.97
39

Table 3
Evaluating the effect of the number of time periods in the planning horizon.
Test Time
Ambulances
of day on duty
(1) (2)
(3)

Time
Number of periods scenarios
(4)
(5)

Relocations Service level (6)
(7)

CPU
(s)
(8)

31
32
33
34
35
36
37
38
39
40

70
80
90
100
110
120
130
140
150
160

50
50
50
50
50
50
50
50
50
50

1
2
2
2
1
2
1
1
2
2

93
90
93
92
97
97
95
91
92
94

29
32
33
32
32
29
31
29
21
30

Min
Avg.
Max

1
1.6
2

90%
93.4%
97%

29
30.8
33

50
50
50
50
50
50
50
50
50
50

1
1
0
1
0
1
2
1
0
1

91
96
93
95
97
95
96
93
91
91

31
35
36
35
34
35
34
34
32
36

Min
Avg.
Max

0
0.8
2

91%
93.8%
97%

31
34.2
36

41
42
43
44
45
46
47
48
49
50

03:00
03:00
03:00
03:00
03:00
03:00
03:00
03:00
03:00
03:00

14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00

7
7
7
7
7
7
7
7
7
7

14
14
14
14
14
14
14
14
14
14

70
80
90
100
110
120
130
140
150
160

5
6
7
8
9
10
11
12
13
14
15

120
120
120
120
120
120
120
120
120
120
120

3
3
3
3
2
4
2
2
1
0
0

92
95
96
92
91
91
90
95
94
94
92

27
28
32
32
35
33
37
38
36
39
38

0
2.09
4

90%
92.91%
96%

27
34.09
39

50
50
50
50
50
50
50
50
50
50
50

3
3
2
2
3
2
2
1
1
0
0

96
93
95
90
94
95
91
96
94
92
90

27
28
28
32
32
33
37
35
38
38
40

Min
Avg.
Max

12:00
12:00
12:00
12:00
12:00
12:00
12:00
12:00
12:00
12:00
12:00

5
6
7
8
9
10
11
12
13
14
15

50
50
50
50
50
50
50
50
50
50
50
Min
Avg.
Max

62
63
64
65
66
67
68
69
70
71
72

08:00
08:00
08:00
08:00
08:00
08:00
08:00
08:00
08:00
08:00
08:00

0
1.73
3

90%
93.27%
96%

27
33.45
40

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

100
100
100
100
100
100
100
100
100
100
100
100
100
100
100

14
14
14
14
14
14
14
14
14
14
14
14
14
14
14

100
100
100
100
100
100
100
100
100
100
100
100
100
100
100

20
30
40
50
60
70
80
90
100
110
120
130
140
150
160

1
1
0
1
1
2
0
1
0
1
1
0
1
1
1

94
90
96
95
95
92
97
95
93
91
95
92
95
93
94

28
31
33
32
35
34
36
37
38
38
37
39
38
42
44

0
0.8
2

90%
93.8%
97%

28
36.13
44

20
30
40
50
60
70
80
90
100
110
120
130
140
150
160

1
0
2
1
1
1
0
0
0
1
1
0
1
1
1

93
95
93
96
95
97
90
93
93
95
94
90
96
93
96

35
38
36
38
37
37
38
38
39
39
40
39
40
42
43

Min
Avg.
Max

14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00
14:00

12
12
12
12
12
12
12
12
12
12
12
12
12
12
12

CPU
(s)
(8)

Min
Avg.
Max
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

02:00
02:00
02:00
02:00
02:00
02:00
02:00
02:00
02:00
02:00
02:00
02:00
02:00
02:00
02:00

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

Fig. 3. Service level.

Table 6
8 min vs 10 min 30 s service time.
Test

Time of day

Ambulances on duty

Time periods

Scenarios

Service time
8 min

10 min 30 s

Relocations
103
104
105
106
107
108
109
110
111
112
113
114
115

7:32
7:56
7:40
10:25
11:04
12:32
14:17
15:56
21:29
22:40
23:11
1:18
4:55

8
8
9
12
12
14
14
15
11
11
11
9
8

100
100
100
100
100
100
100
100
100
100
100
100
100

Service level

CPU (s)

Relocations

Service level

CPU (s)

50
50
50
50
50
50
50
50
50
50
50
50
50

4
2
3
2
3
3
4
4
2
3
3
2
4

82
88
83
82
86
84
87
85
83
86
88
84
85

35
29
33
32
33
29
33
37
25
31
22
28
27

2
2
2
2
1
1
1
1
0
1
1
2
2

92
92
93
92
91
92
90
92
94
91
92
94
92

32
29
36
33
37
29
31
34
28
27
25
25
29

Min
Avg.
Max

2
3
4

82%
84.85%
88%

22
30.31
37

0
1.38
2

90%
92.08%
94%

25
30.38
37

1978

J. Naoum-Sawaya, S. Elhedhli / Computers & Operations Research 40 (2013) 1972–1978

Table 7
Manhattan metric vs Euclidean norm.
Test

Time of day

Ambulances on duty

Time periods

Scenarios

Manhattan metric

Euclidean distance

Relocations
6:35
6:54
7:25
8:33
10:50
11:45
12:35
14:30
20:30
21:30
22:00
5:25
6:00

8
9
9
10
12
12
14
14
13
11
11
7
7

100
100
100
100
100
100
100
100
100
100
100
100
100

50
50
50
50
50
50
50
50
50
50
50
50
50

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.

CPU (s)

Relocations

Service level

CPU (s)

2
2
2
1
2
2
1
0
2
2
2
3
1

92
91
90
90
90
92
92
91
93
91
90
90
91

28
28
28
28
33
29
29
32
30
30
30
26
29

2
2
1
1
2
1
1
1
2
1
1
2
1

92
93
90
94
90
92
92
95
93
91
93
92
91

29
30
26
27
31
30
29
33
30
28
23
23
29

0
1.69
3

116
117
118
119
120
121
122
123
124
125
126
127
128

Service level

90%
91%
93%

26
29.23
33

1
1.38
2

90%
92.15%
95%

23
28.31
33

[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.…...

Similar Documents

Free Essay

Time

...Time is said to be eternal. It is said that it has neither a beginning nor an end. Yet men are able to measure it as years, months, days, hours, minutes and seconds. They have also given meanings to the words – past, present and future. True, time has a meaning. It moves. What was yesterday is not today. What is today will not be tomorrow. Yesterday is gone. Today is and tomorrow is yet to come. Yet time is said to have no holiday. It exists always. The entire creation moves on according to a time pattern. There is birth, growth and death. There is time for everything. Plants flower and give fruits. Seasons come according to time. A child is born, grows into boyhood, adolescence, youth, middle age and old age according to age and time. Every movement of creation is linked with time. One cannot grow paddy in a month nor can a child become an adult in a year. Everything is fixed to a time-frame. Time is a free force. It does not wait for any one. It is commonly said that time and tide waits for no man. Time is money. A minute not usefully spent is an eternal loss. You can never get back the lost minute. One has to strike the iron when it is hot. The time flies and never returns. If you waste time it wastes you. ‘Time is the best medicine’, says Ovid. It is said that time heals all wounds and it even heals what reason cannot. All human beings are emotional. When negative emotions like fear, anger, envy and jealousy overtake them, they lose reason and act in haste......

Words: 584 - Pages: 3

Free Essay

Time

...new phases is common throughout the book. Tom's adolescence is a time of great accomplishment and pain, as he is horrifyed by the accident that is brother Daniel was involved with and the inmpact it had on the family. Throughtout this time he is also trying to find himself after the event change his life. In this time he questions what is really inportant to him. His realtionship with is new football tean in Coghill is highly significant. In his role as halfback for his football team, he takes on the role of trainning and guiding the team. This involvement with football become an important symbol of growing up. He starts to appreciate and enjoy the game and comes to realise winning isn;t everything. But in the book it take a while for the characters to venture into the world. n the story of Tom Brennan many individulas venture into new experiences but coming across new experices you may have to encounter obstacles. In the end its all worth it because you may also gain significant rewards. New phases and experiences in life are exciting for all individuals. in the story of tom brennan, this idea of new phases is common throughout the book. Tom's adolescence is a time of great accomplishment and pain, as he is horrifyed by the accident that is brother Daniel was involved with and the inmpact it had on the family. Throughtout this time he is also trying to find himself after the event change his life. In this time he questions what is really inportant to him. His......

Words: 793 - Pages: 4

Premium Essay

Time

...Time What does time mean to me? For a long portion of my life time meant the hours I had in a day to do things that I thought were fun. Time was a way I measured how long I had until the next instance of something that I had to do. Time was not important it was numbers on a clock. Time was what I had to keep track of the days as they flew by with nothing important to do. Time in its essence had no meaning, no value, or no real importance. Then one remark made a point in time the most important occurrence of time in my life. One question asked gave value to time, one voice gave meaning to time, and one smile forever made time important. The first time I saw her made me question what I was using time for. How could someone I just met change my views on the importance of time? “How big is that shirt? It is like a tarp on you.” That one question followed by that one comment was the first event in my time that had real importance. It was the first time in my life that time had meaning, value, and importance. Her answer made me blush. Her smile made me forget who I was, and her eyes slowed time. As I tried to regain my thoughts I hurried to the back office. What was I thinking was the first thing that came to my mind. That was the first real event in my life. It was the first event in my life where time had a meaning....

Words: 274 - Pages: 2

Premium Essay

Taylor Ambulance Memo

...Taylor Ambulance Database Memo DBM/381 10/14/2014 Kevin Woodson Memo To: Technical Services/Logistics Manager From: Date: October 14, 2013 Subject: New Database Design for Taylor Ambulance This memo is to inform you of the design that I intend to pursue when converting your current paper system into an electronic format. It is my intention to create a system in which the database will not only be functional, but will cover all your needs as well. In order to implement my design, I would like to set up a meeting to so we may collaborate on your exact specifications and wants for the database. During this meeting, we will create a blueprint that will help us navigate through the rest of the phases of the design, and build, of your database. For us to proceed, we first need to discuss your knowledge level of database systems. Understanding your level of expertise will help us better gauge how we can better serve you. We have the staff that will be able to bring you up to speed on the specifics on what databases are, and how they are expected to perform. Once you are on a comfortable level, we will start to identify what you need in database performance. After we find the exact specifications that your company needs, we will need to discuss the type of database model that will fit your business. If we are able to flesh out all design issues, we will be able to have a better performing database that will last the length of the business. Before...

Words: 314 - Pages: 2

Free Essay

Time

...Time. Many people use their time differently, Some use there time inventing, inspiring. There is one thing that everyone can agree on is time is not something to waste. Steve Jobs once said, “Your time is limited, so don't waste it living someone ease’s life. Don't be trapped by dogma which is living with the results of other people's thinking. Don't let the noise of others' opinions drown out your own inner voice. And most important, have the courage to follow your heart and intuition.” .this quote explains time well because you don’t want to let other peoples options get in the way of your goal and cause someone to waste their time. One will never know when their time will be up, Good time management for a student requires three points. One step to make time management effective is to develop a time strategy. The time strategy should be based on a short list of time priorities. This short list forms the basis for a student's time planning for every week of the year. The dictionary definition of the word time is “the system of those sequential relations that any event has to any other, as past, present, or future; indefinite and continuous duration regarded as that in which events succeed one another.” My own personal definition of time is the opportunity you are give to succeed of or fail. The first of the three points that a student should keep in his or her mind is not taking on more than he or she can handle. If a student has scheduled to many classes to take in one......

Words: 946 - Pages: 4

Premium Essay

London Ambulance Service Software Failure

...London Ambulance Service Software Failure The London Ambulance Service (LAS) responds between 2000 and 2500 calls per day with a fleet of 750 vehicles, in less than three minutes. Their system was originally manually operated where details of an incident call taken by a control assistant is used to ascertain the location of an incident scene through the use of a map book. This information is then passed to a dispatch team who direct the appropriate ambulance to the incident scene through a radio call. Due to the short comings of this manual system, the LAS thought to computerize its dispatch system in 1987. The first attempt was started in the 1980’s, abandoned in 1990 and failed after spending £7.5 million. The second attempt by LAS was signed in May 1991. On the morning of Monday 26th October 1992 the LAS CAD system went live for the first time. Unfortunately there were 81 known bugs in the system at that time and it had been 10 months since the control room staff were first trained to use the software. The system had 4 primary flaws when it went live; it did not function well. Furthermore, the user interface had black spots which meant that the user could not see all the information on screen and finally, additionally, the system stored incident information even after it was not needed, which caused the system to fill up memory and fail. The first of these problems began to show during the morning rush of calls; there were a number of duplicate calls which led to a...

Words: 1738 - Pages: 7

Premium Essay

Time

...Introduction cont.. * Poor time management can negatively affect the performance of the working students in several ways. First if they don’t structure their time for homework & projects, they may not able to complete them on time. Second is the cramming for examination which is the another common trait of disorganized or undisciplined college students that rather than setting aside time each evening for study, poor time managers try to absorb everything in a few late hours the day before the test. * Trying to manage all the demands of working and going to school is not an easy task, but it is possible. Time management is the key to their daily survival and success in reaching their goal. Introduction cont.. * Poor time management can negatively affect the performance of the working students in several ways. First if they don’t structure their time for homework & projects, they may not able to complete them on time. Second is the cramming for examination which is the another common trait of disorganized or undisciplined college students that rather than setting aside time each evening for study, poor time managers try to absorb everything in a few late hours the day before the test. * Trying to manage all the demands of working and going to school is not an easy task, but it is possible. Time management is the key to their daily survival and success in reaching their goal. Statement of the problem The study aims to answer the following......

Words: 1189 - Pages: 5

Free Essay

Time

...understanding and compassionate. I also have very strong interpersonal skills and a couple of experience in customer service from my home country Tanzania. I believe that these skills acquired from my experiences can be applicable to my position as a waitress in a benefiting way.  My resume, which is attached to this letter, contains additional information on my education and skills. I look forward to hearing from you and will be glad if you could set me up for an interview. Your time taken to read this is highly appreciated.   Sincerely yours, 
 Angela Kundi. Angela Kundi #4-1520 1st Street South. Cranbrook BC. V1C 1B9 | angelkundi@yahoo.com| C+1-250-464-0099                        Objective  To find a full time job in Cranbrook Skills/Qualification Summary * Positive Team Player * Great Customer Service Skills * Ability to pay attention to details * Great interpersonal communication skills * Knowledge on Microsoft Word, Excel and Access Work Experience * Baraza resort and spa April 2012- June......

Words: 327 - Pages: 2

Premium Essay

Time

...Running head: Time management in nursing 1 Time management in nursing Running Head: Time management in nursing 2 Nursing is a demanding career in and of itself. Without effective time management both at work and home a nurse be easily become affected by prolonged stress. Learning to manage your time effectively is highly rewarding. By managing time you become more effective and less hassled . At the end of the work day you go home with little more energy and better attitude. Time may be one of the the precious source to manage.There is an old saying that time is money. In health care time affects both money and quality. For each nurse there is a finite and identifiable limit to the hours to do work. With the same second in every minuites nurse need to find ways to stretch the time available to meet the needs that arise(Hurber,20006)Many nurses complain about needing more time. They are stressed and frustrated . At any point in time nurse guggle work and other roles such as student, partner, parent, child,or friend.As work places are restructures for efficiency and employ......

Words: 878 - Pages: 4

Premium Essay

London Ambulance Service

...Introduction The London Ambulance Service is unfortunately known for having a troubled past in terms of reliability of computer-aided dispatch (CAD) systems. In 1992, an updated version of the 1987-1990 system was re-launched but after 9 days it failed, resulting in millions of pounds being wasted as well several lives being lost (source 1). The 1992 failure will forever be remembered as a colossal accounting information systems failure. The second CAD attempt in 1992 was forced to back to a manual system after the system was overflowed with calls and could not reliably dispatch ambulances. The main problem with the software was that it was rushed into use without following the adequate steps of systems development life cycle (source 2). Other important factors that caused such a disaster included weak feasibility and initial investigation, the software never having been adequately tested, the staff using the software not having been properly trained, and the absence of a backup plan in case the system failed. Scope This case review will focus on the failure of the 1992 system, which was expected to be fully automated and reliable, fixing errors made during the 1980s and the shortcomings of previous systems. These failures will be explained and broken down based on the steps used in the systems development life cycle starting with systems analysis, followed by conceptual design, physical design, implementation and conversion, and ending with operation and......

Words: 2238 - Pages: 9

Premium Essay

Time

...guys are all bundled up." Clearly animated and looking well, he said he didn't feel much different than he did after his five-month station mission five years ago. Kelly and Kornienko had checked out of the space station 3½ hours earlier. In total, they traveled 144 million miles through space, circled the world 5,440 times and experienced 10,880 orbital sunrises and sunsets during the longest single spaceflight by an American. Kelly posted one last batch of sunrise photos Tuesday on Twitter, before quipping, "I gotta go!" His final tweet from orbit came several hours later: "The journey isn't over. Follow me as I rediscover # Earth!" Piloting the Soyuz capsule home for Kelly, 52, and Kornienko, 55, was the much fresher and decade younger cosmonaut Sergey Volkov, whose space station stint lasted the typical six months. The two yearlong spacemen faced a series of medical tests following touchdown. Before committing to even longer Mars missions, NASA wants to know the limits of the human body for a year, minus gravity. As he relinquished command of the space station Monday, Kelly noted that he and Kornienko "have been up here for a really, really long time" and have been jokingly telling one another, "We did it!" and "We made it!"...

Words: 724 - Pages: 3

Premium Essay

London Ambulance Case Update Report

...Cover sheet Lessons Learned Report London Ambulance Service CONTENTS 1. Overview .........................................................................................................4 2. Management and Quality Processes ...............................................................5 3. Abnormal Events Causing Deviation............................................................. 7 4. Assessment of Specialist Methods and Tools................................................ 8 5. Project Issues and Results........................ ...................................................... 9 6. Product Estimates and Actuals ..................................................................... 10 7. Recommends for improvement of the project management method ............ 10 8. Quality Review Effectiveness........................................................................ 11 9. Bibliography………………………………………………………………………………………………..12 10. Appendix…………………………………………………………………………………………………..13 1. Overview A lessons learned report defines the lessons that were learned from the project. Traditionally held during project close off but can also be done at any stage of the project’s life cycle. The purpose of the lesson learned is to use the knowledge derived from the experience: * Promote recurrence of desirable outcomes * Avoid recurrence of undesirable......

Words: 2620 - Pages: 11

Free Essay

Star Air Ambulance

...TO: Management, Stakeholders & Employees of STARS Air Ambulance FROM: Sharaz Khan, CIO DATE: March 1, 2008 SUBJECT: Revamping Information Systems (IS) Unit Today’s challenging healthcare environment demands an experienced organization that can deliver innovative service solutions, while operating on budget. We at Shock Trauma Air Rescue Society or STARS Air Ambulance service have the experience and expertise to meet these needs, making us the preferred choice for trauma and emergency services nationwide. After my inception as the CIO, I requested our employees and executives to join in an internal dialogue about important issues facing our organization. I’ve been buoyed by the thought and discussion we’ve heard and read over the past few weeks. Even though we are performing well, there are few areas of concern which I think needs to be addressed in order for our organization to perform better. During my inquiry, I found that STARS needed to review its business and IS infrastructure. Information Systems (IS) never played a major role in any of STARS major operations and strategic planning, which has led to many organizational and operational issues. We need to understand that technology plays an important role in our day to day activities. We employ and leverage the use of information systems to communicate across the organization and also with our external partners. Although we are unable to make optimal use of the IS unit, we need to value the little innovation......

Words: 1440 - Pages: 6

Free Essay

Case Analysis for Star Air Ambulance

...new CIO are lack of prioritization of critical IT projects, lack of IT governance and lack of control on IS budget not only due to “distributed” IS but also due to inconsistent system development practices and disintegrated IT infrastructure. The new CIO should handle these three challenges by first creating IS mission and vision statements followed by a strategic plan that is aligned with business strategy as shown in figure 1. But he should also consider the fact that Steve Romero mentioned “IT strategy should not just follow business strategy; rather it should be embedded in it.” -------------------------------------------- [ 1 ]. Munro M.C. and Huff S. (2008, Feb) “STARS Air Ambulance: An Information Systems Challenge”, Ivey, p 3 [ 2 ]. Munro M.C. and Huff S. (2008, Feb) “STARS Air Ambulance: An Information Systems Challenge”, Ivey, p 12 [ 3 ]. McNurlin B.C., Sprague R.H. and Bui T. (2006 ) “Leading: Creating a Vision by understanding the business”, Information Systems Management in Practice, Eighth edition, Prentice-Hall Inc., p 63-65 [ 4 ]. Romero S. (2012, Feb) “Realizing the most value from technology through business governance of IT”, Romero Consulting, p 24...

Words: 353 - Pages: 2

Free Essay

Star Ambulance

...Case Study : STARS AIR AMBULANCE If I was given the task of determining the mission statement, I would include the use of the words people and technology in the mission, since it appears STARS need skilled and dedicated staff to achieve their goal. They also plan to replace their current fleet of helicopters for faster and longer range coverage of their service. The mission statement could be as follows: Providing a safe, rapid , highly specialized emergency medical transport system for the critically ill and injured , through the best people and cutting edge technology. If STARS manage to provide these services to cover the whole state of ALBERTA, then the mission statement could also cover the scope of its geographic operations. It is very important that the information system is well managed because: * Information increases flexibility with regard to how, when and where resources may be utilized to achieve strategic advantage for the organization. * Enhanced information exchange facilitates collaboration and redefines relationships between an organization, employees, suppliers and the public at large. * Managers will use it to better manage resources towards achieving goals through human resource in an organization. IS is therefore the thread that links the organization’s activities into an integrated process Based on my analysis, it can be seen that there is no coherent IS strategy in STARS because from the 72 page STARS Critical, Strategic......

Words: 2104 - Pages: 9