# Optimal Installation Locations for Automated External Defibrillators in Taipei 7-Eleven Stores: Using GIS and a Genetic Algorithm with a New Stirring Operator

Authors: Chung-Yuan Huang; Tzai-Hung Wen
Journal: Computational and Mathematical Methods in Medicine
 (2014)

---

## Abstract

Immediate treatment with an automated external defibrillator (AED) increases out-of-hospital cardiac arrest (OHCA) patient survival potential. While considerable attention has been given to determining optimal public AED locations, spatial and temporal factors such as time of day and distance from emergency medical services (EMSs) are understudied. Here we describe a geocomputational  genetic algorithm with a new stirring operator (GANSO) that considers spatial and temporal cardiac arrest occurrence factors when assessing the feasibility of using Taipei 7-Eleven stores as installation locations for AEDs. Our model is based on two AED conveyance modes, walking/running and driving, involving service distances of 100 and 300 meters, respectively. Our results suggest different AED allocation strategies involving convenience stores in urban settings. In commercial areas, such installations can compensate for temporal gaps in EMS locations when responding to nighttime OHCA incidents. In residential areas, store installations can compensate for long distances from fire stations, where AEDs are currently held in Taipei.


---

## Body

## 1. Introduction

The American Heart Association defines out-of-hospital cardiac arrest (OHCA) as the cessation of mechanical cardiac activity outside of a medical care setting as confirmed by the absence of circulation [1, 2]. Survival is strongly correlated with time between OHCA occurrence and first defibrillation, with 4 minutes or less considered as optimum for survival [3, 4]. Survival potential declines by 7–10% for each minute that treatment is delayed [5]. For 80% of OHCA patients whose events occur at home and 60% whose events occur in the presence of another individual [6], survival is heavily dependent on the dispatch point of the nearest ambulance or emergency medical service (EMS) team [7, 8]. Accordingly, EMS timeliness is a top priority for emergency medicine researchers [9]. While cardiopulmonary resuscitation (CPR) performed while waiting for other forms of treatment increases OHCA survival by approximately 8% [10], CPR requires voluntary participation in a 2-3 hour training session. The installation of automated external defibrillators (AEDs) in public locations is therefore considered the most effective means of reducing the time from OHCA onset to first defibrillation [11–13]. Early defibrillation programs in Taipei began in June of 2000 [14], with the immediate goal of making AEDs available in public locations such as airports, fire stations, university campuses, and shopping malls.Despite the research attention given to spatial analytical methods and patterns in the design of medical services [15, 16], few efforts have been made to thoroughly study the spatial and temporal aspects of OHCA incidents and EMS availability when determining optimal locations for AED installations [12, 17, 18]. In terms of temporal variation, lower cardiac arrest rates at night are likely due to less human activity in public areas, reducing the probability of OHCA discovery and increasing treatment delays. In light of evidence indicating variance in temporal OHCA frequency [19], defibrillator installation planners must identify areas with higher rates of cardiac arrest to increase the potential for bystanders to provide emergency treatment prior to the arrival of trained emergency personnel. In terms of spatial variation, optimal AED installation location can compensate for geographic obstacles to deliver timely EMS treatment [7]. Defibrillators have been installed in many cities at fixed locations such as parks, shopping malls, bus stops, and airports [17]. Despite the easy identification of AEDs installed at fixed locations, much higher concentrations are found in high-activity areas, leaving low-activity areas underserved. Fixed AED locations must therefore be supplemented by mobile AEDs in police cars and other emergency vehicles [20]. However, since public safety personnel are often occupied by other emergencies, fixed location for AEDs is the favored approach.In this paper, we describe ageocomputational genetic algorithm with a new stirring operator (GANSO) that considers spatial and temporal cardiac arrest occurrence factors when assessing the feasibility of using Taipei 7-Eleven stores as installation locations for AEDs. Taipei has the highest density of 24-hour convenience stores in the world, nearly 2,000 serving the needs of over two million residents. The country’s public health officials are examining the feasibility of installing AEDs in many of these stores to compensate for the shortage of EMSs in locations away from urban centers and in commercial neighborhoods with less activity during nighttime hours. Given the prohibitive cost of installing an AED in every 7-Eleven store, an appropriate subset of locations providing the greatest coverage must be identified [21, 22]. This task requires consideration of spatial and temporal factors including OHCA onset time, location, frequency, distance between potential AED locations, and distance to EMS facilities (usually fire stations). It can be formulated as either a location-allocation optimization problem [21, 22] or a weighted set-covering problem (i.e., a nondeterministic polynomial time complete [NP-complete] problem) [23]. Computational complexity can be reduced by using a weighted set-covering genetic algorithm (GA) (in location-allocation optimization problems involving EMSs [24, 25], GAs offer high utility value in scenarios involving geographic information systems (GISs) [26]—for example, when comparing response times for evaluating EMS and ambulance allocation [27]; GAs have also been used to maximize coverage for fire stations, post offices, and banks [22]; GA performance and convergence are closely associated with appropriate methods for encoding candidate solutions, objective functions, selection and reproduction operators, parameter settings, and specific success criteria [25, 28]) to obtain a set of approximation solutions [29, 30].


## 2. Materials and Methods

Three categories of data were used in this study: OHCA information, 7-Eleven locations, and fire station locations. OHCA data are from the Emergency Medical Service Registry System of the Taipei City Government. Filter criteria for the OHCA cases include nontrauma events between January and December of 2010 involving patients over 18 years of age who were treated by emergency medical services personnel. The registry system was established by the Taipei City Department of Health. Data were compiled by the City’s Fire Department and Taipei area hospitals. OHCA data include time and date of onset, location, ambulance/EMS vehicle response time, and type of cardiovascular life support used (advanced, basic, or a combination). Convenience store and fire station data were collected from the 7-Eleven Chain Store Corporation and Taipei City Fire Department. Geographic distributions of OHCA patients, convenience stores, and fire stations are shown in Figure1.Figure 1
Geographic distribution of 1,625 OHCA cases, 677 7-Eleven stores, and 44 fire stations in Taipei in 2010. Each green dot denotes one OHCA case, each purple dot one 7-Eleven store, and each red icon one fire station.(a) Chromosome-encoding scheme. (b) Proposed GANSO crossover operator flow.
(a)
(b)Our proposed framework consists of two stages: (a) determining the spatial and temporal weights of OHCA incidents and covering sets for individual convenience stores and (b) using GANSO with first-stage findings to solve AED location-allocation optimization problems entailing spatial and temporal variation. We will describe two scenarios for determining AED conveyance from convenience stores to cardiac arrest victims, with service distance set at either 100 or 300 meters. At 100 meters, the primary conveyance mode is running at an average speed of 80–100 meters per minute. This allows for defibrillation within the four-minute time span considered optimal for saving the lives of OHCA victims. When the service distance is set at 300 meters, a vehicle moving at an average speed of 320–400 meters per minute is required to stay below the four-minute target.


### 2.1. Temporally and Spatially Weighted Models

We assumed a total ofM OHCA patients (labeled 1 to M), N 7-Eleven stores (labeled 1 to N), and L fire stations (labeled 1 to L) in Taipei in 2010. Each OHCA patient is denoted as an object variable o
i
(
i
∈
{
1,2
,
…
,
M
}
) belonging to a patient set O
=
{
o
1
,
o
2
,
…
,
o
M
} consisting of all M OHCA patients. Each 7-Eleven store is denoted as an object variable c
j
(
j
∈
{
1,2
,
…
,
N
}
) belonging to a store set C
=
{
c
1
,
c
2
,
…
,
c
N
} consisting of all N 7-Eleven stores. Subscript j on store object c is also used to denote the serial number of 7-Eleven stores (
i
.
e
.
,
c
j
.
s
e
r
i
a
l
_
n
o
=
j
). Each fire station is denoted by an object variable f
k
(
k
∈
{
1
,
2
,
…
,
L
}
) belonging to a set F
=
{
f
1
,
f
2
,
…
,
f
L
,
} consisting of all L fire stations.Each OHCA patient objecto
i had three major member attributes (sometimes referred to as “properties”):event_time,event_date, andloc. Theevent_time attribute denotes the onset time of an OHCA event using the formathh:mm:ss (24-hour clock—00:00:00 to 23:59:59),event_date denotes the onset date of an OHCA event using the formatyyyy.mm.dd., andloc denotes the onset location of an OHCA event using an (
x
,
y
) GPS geographic position format. Next, we developed two weighting schemes to capture spatial and temporal variation for AED location selection: (a) occurrence frequency and time of cardiac arrest in a given location for temporal variation and (b) distance between EMS facility and convenience store for spatial variation. We assumed that convenience store AEDs compensate for lost time when they are located far from the closest EMS facilities.For the TWM parameters, time of cardiac arrest event was categorized in terms of month and time period. An attempt was made to determine the monthly temporal weightweight
(
o
i
,
m
o
n
) of each OHCA patient. We considered situations in which the OHCA event onset monthequaled a mon parameter value
(
i
.
e
.
,
m
o
n
t
h
(
o
i
.
e
v
e
n
t
_
d
a
t
e
)
=
m
o
n
), with a function weight
(
o
i
,
m
o
n
) return of 1.0 (nighttime) or 0.5 (daytime) according to subfunction weight
(
o
i
), depending on what time of day the event occurred. Otherwise, the weight
(
o
i
,
m
o
n
) function returns an interpolated value indicating the sum of the weighted OHCA, standardized in terms of inverse distance weighting:(1)
weight
(
o
i
,
m
o
n
)
=
{
weight
(
o
i
)
m
o
n
t
h
(
o
i
.
e
v
e
n
t
_
d
a
t
e
)
=
m
o
n
∑
m
o
n
t
h
(
o
j
.
e
v
e
n
t
_
d
a
t
e
)
=
m
o
n
weight
(
o
j
)
×
distance
_
weight
(
o
i
,
o
j
)
∑
k
≠
i
∧
m
o
n
t
h
(
o
k
.
e
v
e
n
t
_
d
a
t
e
)
=
m
o
n
distance
_
weight
(
o
i
,
o
k
)
otherwise
,where
(2)
weight
(
o
i
)
=
{
0.5
if
time
_
period
(
o
i
.
e
v
e
n
t
_
t
i
m
e
)
=
"
daytime
"
1.0
if
time
_
period
(
o
i
.
e
v
e
n
t
_
t
i
m
e
)
=
"
nighttime
"
,
distance
_
weight
(
o
i
,
o
j
)
=
1
distance
(
o
i
.
l
o
c
,
o
j
.
l
o
c
)
2
.Three user-defined functions were used to determine the monthly temporal weight of an OHCA patient:month
(
d
a
t
e
) returns the month from a passed date parameter. The time
_
period
(
t
i
m
e
) returns one of two period strings from a passed time parameter—08:00 to 17:00 representing “daytime” and all other values “nighttime.” The distance
(
l
o
c
i
,
l
o
c
j
) returns a Euclidean distance between two passed position parameters of a plane with Cartesian coordinates on a map. The functions of time
_
period
(
t
i
m
e
) and distance
(
l
o
c
i
,
l
o
c
j
) are defined as follows:
(3)
time
_
period
(
t
i
m
e
)
=
{
"
daytime
"
08:00:00
≤
t
i
m
e
≤
17:00:00
"
nighttime
"
otherwise
,
distance
(
l
o
c
i
,
l
o
c
j
)
=
(
l
o
c
i
.
x
-
l
o
c
j
.
x
)
2
+
(
l
o
c
i
.
y
-
l
o
c
j
.
y
)
2
.Next, we computed an OHCA temporal weight by combining 12 monthly weight values (weight(
o
i
,
1
)
, weight (
o
i
,
2
)
,
…, weight (
o
i
,
12
)). A coefficient of variation (COV), defined as a ratio of the mean mean
(
o
i
) to standard deviation sd
⁡
(
o
i
), served as the OHCA weight—that is,
(4)
temporal
_
wieght
(
o
i
)
=
mean
(
o
i
)
sd
⁡
(
o
i
)
with mean
(
o
i
) and sd
⁡
(
o
i
) computed as
(5)
mean
(
o
i
)
=
∑
m
=
1
12
weight
(
o
i
,
m
)
12
,
sd
⁡
(
o
i
)
=
∑
m
=
1
12
(
weight
(
o
i
,
m
)
-
mean
(
o
i
)
)
2
12
.In the SWM, a higher weight indicates a longer distance to the nearest fire station. Spatial weight was assumed as the minimum square Manhattan distance to each fire station(
f
k
):
(6)
spatial
_
weight
(
o
i
)
=
min
⁡
k
Manhattan
_
distance
(
o
i
.
l
o
c
,
f
k
.
l
o
c
)
2
.Due to the grid-like characteristic of urban street networks, we used Manhattan distances to compute distances from fire stations to OHCA victims expressed as(7)
Manhattan
_
distance
(
l
o
c
i
,
l
o
c
j
)
=
|
l
o
c
i
.
x
-
l
o
c
j
.
x
|
+
|
l
o
c
i
.
y
-
l
o
c
j
.
y
|
.


### 2.2. Genetic Algorithm with a New Stirring Operator (GANSO)

We formulated the AED location-allocation optimization problem as a choice within a limitedK-sized subset of convenience stores, using GANSO to determine an optimum subset based on the temporal or spatial characteristics of OHCA victims. As shown in Pseudocode 1, our proposed GANSO (GANSO was implemented as a Python program, which supports future simulation experiments and possible extensions; all input/output data from our application were managed and processed using Quantum GIS (QGIS), an open source (general public license) GIS; for source code and input data for OHCA information, 7-Eleven locations, and fire station locations, contact the corresponding author) consists of nine steps.Pseudocode 1
Step 1.  Reset all GA parameters and operators (i.e., selection, crossover, and mutation) to  their
default settings.
Step 2.  Randomly generate a population of chromosomes (candidates or potential solutions) of  size
n
GA  (defulat: 300), with each  s  chromosome  containing K  (default: 100) elements, and with
each element  corresponding to the serial number (ranging from 1 to N) of a  specific
convenience store (Figure 2(a)).
Step 3.  Assign each chromosome in the initial population a fitness  score obtained by the objective
function.
Step 4.   Repeat Steps 4a–4c until n
GA  offspring have been created.
Step 4a.  Using a roulette wheel sampling mechanism in which selection probability  is
proportional to the fitness score, randomly select two chromosomes from  the
population to serveas parents. Note that any chromosome can be selected more
than once (i.e., in other iterations).
Step 4b.  Using a two-point crossover process to exchange elements between
parent  chromosomes, producing two new offspring with Probabilityρ  (default: 0.8)
from each pair of parents (Figure2(b)). If no crossover occurs, the two new offspring
Will be exact copies of their respective parents. To avoid repeats,  rearrange parental
elements prior to this exchange so that the same elements are moved to the front of
each chromosome.
Step 4c.  Mutate the two offspring for each element at probability  γ
(default: 0.01) and insert the resulting chromosomes into the new population.
Step 5.  Replace the current population with the new one.
Step 6.  Assign each chromosome in the current population a fitness
score obtained by the objective function.
Step 7.  Maintain the best chromosome as the approximate global optimal  solution for the AED
location-allocation problem and its associated fitness score for each generation in the current
population.
Step 8.  Use the stirring operator to prevent premature convergence.  Evolution should be  sufficiently
stable so that the sum of the difference of best fitness scores over  g  generations (default: 20)
falls  below a tolerance value ε  (default: 10−10). In the stirring operator, replace ω  percent
(default: 20%) of the chromosomes in the current population  with new and randomly
generated chromosomes to trigger searches for  additional  g  generations.
Step 9.  If the sum of the difference of best fitness scores in
Additional  g  generations ≤
ε  then  Stop the evolution process and
return the AED location-allocation solution with the best fitness score
else
Go  to Step 4.
end ifIn Step 2, population sizen
GA depends on both the individual chromosome length and fitness function details. For this project, a population size between 200 and 400 chromosomes generated good solutions for the AED location-allocation problem after testing trial runs of up to 1,000 chromosomes. The evolutionary process from Steps 4 to 10 represents an equilibrium between “exploring” the entire search space (2
10
K) and “exploiting” the current best solution to search for an optimal or near-optimal AED location-allocation solution. Although crossover rate ρ in Step 4b is generally applied with a high probability (0.7 to 0.9), excessive use of the crossover operation can disrupt the balance of this equilibrium and create excessive diversity to cause the process to drift from a fit structure. Inadequate diversity can also result in premature convergence and a locally optimum rather than globally fit structure. A balance between exploration and exploitation increases the probability of achieving a global optimum solution, but the γ mutation rate in Step 4c is normally set at a very low probability (e.g., 0.01). A higher mutation rate reproduces an excessive number of random populations, which can also impair the evolutionary mechanism [26]. In GANSO, crossover rate ρ and mutation rate γ are set at 0.8 and 0.01, respectively, to achieve an optimum outcome.To evaluate the fitness score of each chromosome during the GANSO evolution process, eachK-element chromosome is transformed into a one-dimensional binary array X of length N corresponding to index X
[
j
]
(
j
∈
{
1,2
,
…
,
N
}
) of convenience store candidates (
X
[
j
]
=
1 denoting the chosen index, 0 otherwise) for use as a parameter for the following location-allocation optimization problem fitness function:
(8)
fitness
(
X
)
=
maximize
∑
i
=
1
M
W
[
i
,
]
∘
X
subject
to
∑
j
=
1
N
X
[
j
]
=
K
,
transform
(
chromosome
s
)
=
declare
variable
X
as
an
array
[
1
…
N
]
of binary integer
for each index in range
(
1
,
N
)
do loop
X
[
i
n
d
e
x
]
⟵
0
for
each
i
n
d
e
x
in
range
(
1
,
K
)
do
loop
s
o
t
r
e
_
s
e
r
i
a
l
_
n
o
⟵
Integer
(
s
[
i
n
d
e
x
s
]
)
X
[
s
t
o
r
e
_
s
e
r
i
a
l
_
n
o
]
⟵
1
return
X
,
where W denotes an M-row by N-column weighting matrix determined by the temporal or spatial characteristics of all OHCA patients in question and W
[
i
,
] refers to the ith row of the constant weighting matrix W, with W
[
i
,
j
] representing the weight of the ith OHCA patient covered by the jth 7-Eleven store. The ∘ operator is defined as the maximum value among chosen elements:
(9)
W
i
∘
X
=
max
⁡
j
(
W
[
i
,
j
]
·
X
[
j
]
)
.The covering set consists of all 7-Eleven stores in Taipei: for each store, the coverable object is one OHCA incident. Coverable OHCAs are assumed for eachc
j cutoff by a constant distance_threshold as follows:
(10)
o
i
∈
c
j
⟷
Manhattan
_
distance
(
o
i
.
l
o
c
,
c
j
.
l
o
c
)
≤
d
i
s
t
a
n
c
e
_
t
h
r
e
s
h
o
l
d
.Correspondingly, theW constant weighting matrix is defined as
(11)
W
[
i
,
j
]
=
{
model
_
weight
(
o
i
)
o
i
∈
c
j
⟷
Manhattan
_
distance
(
o
i
.
l
o
c
,
c
j
.
l
o
c
)
≤
d
i
s
t
a
n
c
e
_
t
h
r
e
s
h
o
l
d
0
otherwise
,
where
(12)
model
_
weight
(
o
i
)
=
{
temporal
_
weight
(
o
i
)
if
the
adopted
weighting
model
is
"
TWM
"
spatial
_
weight
(
o
i
)
if
the
adopted
weighting
model
is
"
SWM
"
,
d
i
s
t
a
n
c
e
_
t
h
r
e
s
h
o
l
d
=
{
100
when
the
maximal
service
distance
was
set
at
100
meters
300
when
the
maximal
service
distance
was
set
at
300
meters
.Figure3 presents a summary of results from a single TWM experiment using 100 meters as the service distance. As shown, our proposed GANSO (Figure 3, red curve) outperformed simple genetic algorithm (SGA) (blue curve). The x-axis denotes the evolutionary generation number and the y-axis the ratio of the fitness score (the sum of weights for OHCA cases covered by 100 7-Eleven stores) to the total sum of OHCA weights. Experiment results indicate that the new stirring operator was effective in addressing evolution time and performance issues. While GANSO performed poorly during the first few generations, its overall performance was satisfactory: by stirring the population, its best fitness values gradually increased over 180–400 generations, yielding better solutions for AED location selection.Figure 3
Comparison of GANSO and SGA performance over 421 generations.


## 2.1. Temporally and Spatially Weighted Models

We assumed a total ofM OHCA patients (labeled 1 to M), N 7-Eleven stores (labeled 1 to N), and L fire stations (labeled 1 to L) in Taipei in 2010. Each OHCA patient is denoted as an object variable o
i
(
i
∈
{
1,2
,
…
,
M
}
) belonging to a patient set O
=
{
o
1
,
o
2
,
…
,
o
M
} consisting of all M OHCA patients. Each 7-Eleven store is denoted as an object variable c
j
(
j
∈
{
1,2
,
…
,
N
}
) belonging to a store set C
=
{
c
1
,
c
2
,
…
,
c
N
} consisting of all N 7-Eleven stores. Subscript j on store object c is also used to denote the serial number of 7-Eleven stores (
i
.
e
.
,
c
j
.
s
e
r
i
a
l
_
n
o
=
j
). Each fire station is denoted by an object variable f
k
(
k
∈
{
1
,
2
,
…
,
L
}
) belonging to a set F
=
{
f
1
,
f
2
,
…
,
f
L
,
} consisting of all L fire stations.Each OHCA patient objecto
i had three major member attributes (sometimes referred to as “properties”):event_time,event_date, andloc. Theevent_time attribute denotes the onset time of an OHCA event using the formathh:mm:ss (24-hour clock—00:00:00 to 23:59:59),event_date denotes the onset date of an OHCA event using the formatyyyy.mm.dd., andloc denotes the onset location of an OHCA event using an (
x
,
y
) GPS geographic position format. Next, we developed two weighting schemes to capture spatial and temporal variation for AED location selection: (a) occurrence frequency and time of cardiac arrest in a given location for temporal variation and (b) distance between EMS facility and convenience store for spatial variation. We assumed that convenience store AEDs compensate for lost time when they are located far from the closest EMS facilities.For the TWM parameters, time of cardiac arrest event was categorized in terms of month and time period. An attempt was made to determine the monthly temporal weightweight
(
o
i
,
m
o
n
) of each OHCA patient. We considered situations in which the OHCA event onset monthequaled a mon parameter value
(
i
.
e
.
,
m
o
n
t
h
(
o
i
.
e
v
e
n
t
_
d
a
t
e
)
=
m
o
n
), with a function weight
(
o
i
,
m
o
n
) return of 1.0 (nighttime) or 0.5 (daytime) according to subfunction weight
(
o
i
), depending on what time of day the event occurred. Otherwise, the weight
(
o
i
,
m
o
n
) function returns an interpolated value indicating the sum of the weighted OHCA, standardized in terms of inverse distance weighting:(1)
weight
(
o
i
,
m
o
n
)
=
{
weight
(
o
i
)
m
o
n
t
h
(
o
i
.
e
v
e
n
t
_
d
a
t
e
)
=
m
o
n
∑
m
o
n
t
h
(
o
j
.
e
v
e
n
t
_
d
a
t
e
)
=
m
o
n
weight
(
o
j
)
×
distance
_
weight
(
o
i
,
o
j
)
∑
k
≠
i
∧
m
o
n
t
h
(
o
k
.
e
v
e
n
t
_
d
a
t
e
)
=
m
o
n
distance
_
weight
(
o
i
,
o
k
)
otherwise
,where
(2)
weight
(
o
i
)
=
{
0.5
if
time
_
period
(
o
i
.
e
v
e
n
t
_
t
i
m
e
)
=
"
daytime
"
1.0
if
time
_
period
(
o
i
.
e
v
e
n
t
_
t
i
m
e
)
=
"
nighttime
"
,
distance
_
weight
(
o
i
,
o
j
)
=
1
distance
(
o
i
.
l
o
c
,
o
j
.
l
o
c
)
2
.Three user-defined functions were used to determine the monthly temporal weight of an OHCA patient:month
(
d
a
t
e
) returns the month from a passed date parameter. The time
_
period
(
t
i
m
e
) returns one of two period strings from a passed time parameter—08:00 to 17:00 representing “daytime” and all other values “nighttime.” The distance
(
l
o
c
i
,
l
o
c
j
) returns a Euclidean distance between two passed position parameters of a plane with Cartesian coordinates on a map. The functions of time
_
period
(
t
i
m
e
) and distance
(
l
o
c
i
,
l
o
c
j
) are defined as follows:
(3)
time
_
period
(
t
i
m
e
)
=
{
"
daytime
"
08:00:00
≤
t
i
m
e
≤
17:00:00
"
nighttime
"
otherwise
,
distance
(
l
o
c
i
,
l
o
c
j
)
=
(
l
o
c
i
.
x
-
l
o
c
j
.
x
)
2
+
(
l
o
c
i
.
y
-
l
o
c
j
.
y
)
2
.Next, we computed an OHCA temporal weight by combining 12 monthly weight values (weight(
o
i
,
1
)
, weight (
o
i
,
2
)
,
…, weight (
o
i
,
12
)). A coefficient of variation (COV), defined as a ratio of the mean mean
(
o
i
) to standard deviation sd
⁡
(
o
i
), served as the OHCA weight—that is,
(4)
temporal
_
wieght
(
o
i
)
=
mean
(
o
i
)
sd
⁡
(
o
i
)
with mean
(
o
i
) and sd
⁡
(
o
i
) computed as
(5)
mean
(
o
i
)
=
∑
m
=
1
12
weight
(
o
i
,
m
)
12
,
sd
⁡
(
o
i
)
=
∑
m
=
1
12
(
weight
(
o
i
,
m
)
-
mean
(
o
i
)
)
2
12
.In the SWM, a higher weight indicates a longer distance to the nearest fire station. Spatial weight was assumed as the minimum square Manhattan distance to each fire station(
f
k
):
(6)
spatial
_
weight
(
o
i
)
=
min
⁡
k
Manhattan
_
distance
(
o
i
.
l
o
c
,
f
k
.
l
o
c
)
2
.Due to the grid-like characteristic of urban street networks, we used Manhattan distances to compute distances from fire stations to OHCA victims expressed as(7)
Manhattan
_
distance
(
l
o
c
i
,
l
o
c
j
)
=
|
l
o
c
i
.
x
-
l
o
c
j
.
x
|
+
|
l
o
c
i
.
y
-
l
o
c
j
.
y
|
.


## 2.2. Genetic Algorithm with a New Stirring Operator (GANSO)

We formulated the AED location-allocation optimization problem as a choice within a limitedK-sized subset of convenience stores, using GANSO to determine an optimum subset based on the temporal or spatial characteristics of OHCA victims. As shown in Pseudocode 1, our proposed GANSO (GANSO was implemented as a Python program, which supports future simulation experiments and possible extensions; all input/output data from our application were managed and processed using Quantum GIS (QGIS), an open source (general public license) GIS; for source code and input data for OHCA information, 7-Eleven locations, and fire station locations, contact the corresponding author) consists of nine steps.Pseudocode 1
Step 1.  Reset all GA parameters and operators (i.e., selection, crossover, and mutation) to  their
default settings.
Step 2.  Randomly generate a population of chromosomes (candidates or potential solutions) of  size
n
GA  (defulat: 300), with each  s  chromosome  containing K  (default: 100) elements, and with
each element  corresponding to the serial number (ranging from 1 to N) of a  specific
convenience store (Figure 2(a)).
Step 3.  Assign each chromosome in the initial population a fitness  score obtained by the objective
function.
Step 4.   Repeat Steps 4a–4c until n
GA  offspring have been created.
Step 4a.  Using a roulette wheel sampling mechanism in which selection probability  is
proportional to the fitness score, randomly select two chromosomes from  the
population to serveas parents. Note that any chromosome can be selected more
than once (i.e., in other iterations).
Step 4b.  Using a two-point crossover process to exchange elements between
parent  chromosomes, producing two new offspring with Probabilityρ  (default: 0.8)
from each pair of parents (Figure2(b)). If no crossover occurs, the two new offspring
Will be exact copies of their respective parents. To avoid repeats,  rearrange parental
elements prior to this exchange so that the same elements are moved to the front of
each chromosome.
Step 4c.  Mutate the two offspring for each element at probability  γ
(default: 0.01) and insert the resulting chromosomes into the new population.
Step 5.  Replace the current population with the new one.
Step 6.  Assign each chromosome in the current population a fitness
score obtained by the objective function.
Step 7.  Maintain the best chromosome as the approximate global optimal  solution for the AED
location-allocation problem and its associated fitness score for each generation in the current
population.
Step 8.  Use the stirring operator to prevent premature convergence.  Evolution should be  sufficiently
stable so that the sum of the difference of best fitness scores over  g  generations (default: 20)
falls  below a tolerance value ε  (default: 10−10). In the stirring operator, replace ω  percent
(default: 20%) of the chromosomes in the current population  with new and randomly
generated chromosomes to trigger searches for  additional  g  generations.
Step 9.  If the sum of the difference of best fitness scores in
Additional  g  generations ≤
ε  then  Stop the evolution process and
return the AED location-allocation solution with the best fitness score
else
Go  to Step 4.
end ifIn Step 2, population sizen
GA depends on both the individual chromosome length and fitness function details. For this project, a population size between 200 and 400 chromosomes generated good solutions for the AED location-allocation problem after testing trial runs of up to 1,000 chromosomes. The evolutionary process from Steps 4 to 10 represents an equilibrium between “exploring” the entire search space (2
10
K) and “exploiting” the current best solution to search for an optimal or near-optimal AED location-allocation solution. Although crossover rate ρ in Step 4b is generally applied with a high probability (0.7 to 0.9), excessive use of the crossover operation can disrupt the balance of this equilibrium and create excessive diversity to cause the process to drift from a fit structure. Inadequate diversity can also result in premature convergence and a locally optimum rather than globally fit structure. A balance between exploration and exploitation increases the probability of achieving a global optimum solution, but the γ mutation rate in Step 4c is normally set at a very low probability (e.g., 0.01). A higher mutation rate reproduces an excessive number of random populations, which can also impair the evolutionary mechanism [26]. In GANSO, crossover rate ρ and mutation rate γ are set at 0.8 and 0.01, respectively, to achieve an optimum outcome.To evaluate the fitness score of each chromosome during the GANSO evolution process, eachK-element chromosome is transformed into a one-dimensional binary array X of length N corresponding to index X
[
j
]
(
j
∈
{
1,2
,
…
,
N
}
) of convenience store candidates (
X
[
j
]
=
1 denoting the chosen index, 0 otherwise) for use as a parameter for the following location-allocation optimization problem fitness function:
(8)
fitness
(
X
)
=
maximize
∑
i
=
1
M
W
[
i
,
]
∘
X
subject
to
∑
j
=
1
N
X
[
j
]
=
K
,
transform
(
chromosome
s
)
=
declare
variable
X
as
an
array
[
1
…
N
]
of binary integer
for each index in range
(
1
,
N
)
do loop
X
[
i
n
d
e
x
]
⟵
0
for
each
i
n
d
e
x
in
range
(
1
,
K
)
do
loop
s
o
t
r
e
_
s
e
r
i
a
l
_
n
o
⟵
Integer
(
s
[
i
n
d
e
x
s
]
)
X
[
s
t
o
r
e
_
s
e
r
i
a
l
_
n
o
]
⟵
1
return
X
,
where W denotes an M-row by N-column weighting matrix determined by the temporal or spatial characteristics of all OHCA patients in question and W
[
i
,
] refers to the ith row of the constant weighting matrix W, with W
[
i
,
j
] representing the weight of the ith OHCA patient covered by the jth 7-Eleven store. The ∘ operator is defined as the maximum value among chosen elements:
(9)
W
i
∘
X
=
max
⁡
j
(
W
[
i
,
j
]
·
X
[
j
]
)
.The covering set consists of all 7-Eleven stores in Taipei: for each store, the coverable object is one OHCA incident. Coverable OHCAs are assumed for eachc
j cutoff by a constant distance_threshold as follows:
(10)
o
i
∈
c
j
⟷
Manhattan
_
distance
(
o
i
.
l
o
c
,
c
j
.
l
o
c
)
≤
d
i
s
t
a
n
c
e
_
t
h
r
e
s
h
o
l
d
.Correspondingly, theW constant weighting matrix is defined as
(11)
W
[
i
,
j
]
=
{
model
_
weight
(
o
i
)
o
i
∈
c
j
⟷
Manhattan
_
distance
(
o
i
.
l
o
c
,
c
j
.
l
o
c
)
≤
d
i
s
t
a
n
c
e
_
t
h
r
e
s
h
o
l
d
0
otherwise
,
where
(12)
model
_
weight
(
o
i
)
=
{
temporal
_
weight
(
o
i
)
if
the
adopted
weighting
model
is
"
TWM
"
spatial
_
weight
(
o
i
)
if
the
adopted
weighting
model
is
"
SWM
"
,
d
i
s
t
a
n
c
e
_
t
h
r
e
s
h
o
l
d
=
{
100
when
the
maximal
service
distance
was
set
at
100
meters
300
when
the
maximal
service
distance
was
set
at
300
meters
.Figure3 presents a summary of results from a single TWM experiment using 100 meters as the service distance. As shown, our proposed GANSO (Figure 3, red curve) outperformed simple genetic algorithm (SGA) (blue curve). The x-axis denotes the evolutionary generation number and the y-axis the ratio of the fitness score (the sum of weights for OHCA cases covered by 100 7-Eleven stores) to the total sum of OHCA weights. Experiment results indicate that the new stirring operator was effective in addressing evolution time and performance issues. While GANSO performed poorly during the first few generations, its overall performance was satisfactory: by stirring the population, its best fitness values gradually increased over 180–400 generations, yielding better solutions for AED location selection.Figure 3
Comparison of GANSO and SGA performance over 421 generations.


## 3. Results and Discussion

At a service distance of 100 meters, 19.9% (323 cases) of the 1,625 cardiac arrest victims were within adequate coverage zones of 38.7% (262) of the 677 7-Eleven stores operating in Taipei. When the distance was increased to 300 meters, 78.2% (1,271 cases) were within the adequate coverage zones of 92% (623) of those stores. Spatial and temporal weight distribution patterns for the OHCA cases are shown in Figure4; larger red dots denote higher SWM and TWM weights. Note that TWM-associated OHCA weights were concentrated in west Taipei, which has a higher population density. In comparison, OHCA weights associated with SWM cases were uniformly distributed throughout the city.Spatial and temporal weight distributions of OHCA cases. (a) SWM, 100-meter coverage; (b) TWM, 100-meter coverage; (c) SWM, 300-meter coverage; and (d) TWM, 300-meter coverage. Red dots denote OHCA case weights.
(a)
(b)
(c)
(d)Optimal solutions are summarized in Table1. When the number of stores was limited to 100 and the service distance was fixed at either 100 or 300 meters, coverage was higher for the TWM parameters—specifically, 180 OHCA patients (55.7%) compared to 176 (54.5%) for the SWM parameters. When the service distance was increased to 300 meters, 704 cases (55.4%) were covered by the TWM and 658 (51.8%) by the SWM parameters. Overall, the TWM and SWM coverage rates for 100 meters were higher than for 300 meters (55.7% versus 55.4% and 54.5% versus 51.8%, resp.). Table 2 and Figure 5 present a detailed comparison of optimal solutions for different service ranges (from 100 to 500 meters in steps of 50 meters) and weighting schemes (TWM and SWM) when the number of stores earmarked for installing AEDs was limited to between 100 and 200.Table 1
Comparison of results for different parameter settings when the number of 7-Eleven convenience stores is limited to 100.
Parameter
Coverable OHCA cases
Coverable OHCA weights
AED service range
Weighting scheme
100 meters
TWM
180 (55.73%)
56.23%
SWM
176 (54.49%)
71.63%
300 meters
TWM
704 (55.39%)
53.88%
SWM
658 (51.77%)
66.25%Table 2
Comparison of results for different AED service ranges when the number of 7-Eleven convenience stores is limited to 100, 150, or 200.
Parameter
100 stores for AED installation
150 stores for AED installation
200 stores for AED installation
AED service range
7-Eleven stores (N = 677)
OHCA (M = 1625)
Weighting scheme
Coverable OHCAcases
Coverable OHCAweights
Coverable OHCAcases
Coverable OHCAweights
Coverable OHCAcases
Coverable OHCAweights
100 meters
262 (38.70%)
323 (19.88%)
TWM
180 (55.73%)
56.23%
230 (71.21%)
73.04%
280 (86.69%)
88.40%
SWM
176 (54.49%)
71.63%
229 (70.90%)
87.85%
278 (86.07%)
95.99%
150 meters
418 (61.74%)
623 (38.34%)
TWM
313 (50.24%)
48.47%
398 (63.88%)
61.85%
461 (74.00%)
72.46%
SWM
292 (46.87%)
61.65%
375 (60.19%)
73.47%
440 (70.63%)
83.23%
200 meters
527 (77.84%)
908 (55.88%)
TWM
446 (49.12%)
47.16%
568 (62.56%)
60.57%
644 (70.93%)
70.01%
SWM
418 (46.04%)
61.09%
522 (57.49%)
71.83%
618 (68.06%)
80.20%
250 meters
595 (87.89%)
1117 (68.74%)
TWM
584 (52.28%)
50.81%
723 (64.73%)
63.15%
818 (73.23%)
72.58%
SWM
549 (49.15%)
61.04%
674 (60.34%)
74.43%
781 (69.92%)
80.6%
300 meters
623 (92.02%)
1271 (78.22%)
TWM
704 (55.39%)
53.88%
861 (67.74%)
66.42%
999 (78.60%)
77.43%
SWM
658 (51.77%)
66.25%
827 (65.07%)
76.01%
951 (74.82%)
82.57%
350 meters
646 (95.57%)
1380 (84.92%)
TWM
834 (60.43%)
59.27%
1014 (73.48%)
72.10%
1125 (81.52%)
81.04%
SWM
804 (58.26%)
69.58%
969 (70.22%)
80.85%
1098 (79.57%)
86.17%
400 meters
657 (97.05%)
1440 (88.62%)
TWM
920 (63.89%)
63.23%
1107 (76.88%)
76.20%
1261 (87.57%)
86.89%
SWM
880 (61.11%)
74.81%
1068 (74.17%)
83.67%
1204 (83.61%)
89.55%
450 meters
660 (97.49%)
1473 (90.65%)
TWM
1037 (70.40%)
69.32%
1227 (83.30%)
82.40%
1337 (90.77%)
90.28%
SWM
989 (67.14%)
76.37%
1184 (80.38%)
87.07%
1300 (88.26%)
92.22%
500 meters
664 (98.08%)
1501 (92.37%)
TWM
1148 (76.48%)
75.26%
1307 (87.08%)
86.61%
1400 (93.27%)
92.72%
SWM
1126 (75.02%)
81.00%
1277 (85.08%)
89.15%
1376 (91.67%)
94.83%Figure 5
Comparison of coverable OHCA rates for different AED service ranges when the number of 7-Eleven convenience stores is limited to 100.As shown in Figure6(a), most of the TWM store locations were in high-density areas and most of the SWM locations in lower-density areas, perhaps due to the TWM preference for locations with higher nighttime OHCA frequencies, as denoted by the large number of blue dots in the densely populated southwest area of Taipei. The SWM parameters indicated a preference for locations farther away from fire stations, which explains why most of the green dots are in outlying neighborhoods (see also Figure 6(a) and Table 3(a)). The overlapping areas marked by black dots indicate high-priority communities for AED installations in convenience stores.Table 3
Comparison of selected 7-Eleven stores at different population densities and for different neighborhood types.
TWM
SWM
TWM-SWM overlap
100 meters
300 meters
100 meters
300 meters
100 meters
300 meters
(a) Population density
Low
30
22
31
30
13
11
Middle
30
39
29
28
15
16
High
40
39
40
42
23
18
Total
100
100
100
100
51
45
(b) Neighborhood type
Commercial
31
29
27
22
14
11
Residential
47
54
53
62
25
28
Other
22
17
20
16
12
6
Total
100
100
100
100
51
45Spatial distributions of (a) population density and (b) land-use type with locations of 7-Eleven stores selected based on SWM and TWM parameters with a 100-meter service range. Data are from 2010 census. Each dot denotes one store. Blue dots indicate stores selected according to TWM parameters and green dots according to SWM parameters. Black dots represent stores identified by both models.
(a)
(b)According to Figure6(b), the TWM parameters favored stores in commercial areas (blue dots), while the SWM parameters favored stores in residential areas (green dots). A higher OHCA incidence rate in commercial areas suggests higher levels of human activity. Note that the SWM parameters identified a larger number of AED installation points due to the smaller number of fire stations in residential areas and their greater distances from identified convenience stores. Although the TWM parameters determined more commercial locations, the SWM-selected locations were more uniform in both high- and low-density areas (Tables 3(b) and 4).Table 4
Average and standard deviation for distances from each 7-Eleven store to the nearest fire station (meters).
Weighting scheme and statistics: min, max, mean, SD
AED service range
100 meters
300 meters
Mean
SD
Mean
SD
TWM
4.68, 34.46, 9.56, 1.67
869
429
881
458
SWM
12.39, 39796162.90, 1198850.25, 1801599.73
1,230
344
1,303
432The tendencies of both models to select convenience stores in densely populated areas based on spatial and temporal considerations are consistent with those reported by Malcom III et al. [18]. They are likely due to the positive correlation between OHCA incidence rate and population density—a link that also explains the greater likelihood of identifying stores for AED installation in commercial areas characterized by higher levels of human activity. Further, optimal locations identified by the TWM parameters were more likely to be located in commercial areas and those identified by the SWM parameters in residential areas. These results are consistent with those reported by Folke et al. [31]. In addition to emphasizing the importance of temporal variation, our results underscore the need for more AED locations in commercial areas. Conversely, since residential areas in Taipei tend to have less business activity and fewer and more widely spaced fire stations, the SWM tendency to identify stores in residential neighborhoods may be viewed as compensating for lower EMS efficiency.Whereas the SWM parameters gave higher priority to locations far from fire stations, the TWM parameters prioritized areas of greater human/commercial activity and locations (more residential than commercial) with higher nighttime OHCA incidence rates. This overlap also emphasizes the importance of installing AEDs in public locations to compensate for shortcomings in EMS facility numbers and locations. Regardless of the model used, the most efficient AED installations in convenience stores or other public locations must consider transport time to cardiac arrest victims. Determining the effects of heavy foot or vehicle traffic is extremely difficult; therefore, AED installation decisions must reflect OHCA incident frequencies and average traffic volumes. Our findings suggest that shorter service distances should be emphasized in areas where OHCA rates are higher and that longer distances are appropriate in areas with low traffic volumes.


## 4. Conclusion

In this paper, we presented a novel framework for solving the NP-complete weighted set-covering problem of allocating AEDs in a subset of 7-Eleven stores in Taipei. To develop a GA with a new stirring operator, we modified a simple GA by adding new chromosomes to a stable evolution process to prevent premature convergence. Two spatially and temporally weighted models (SWM and TWM) were created to consider the spatial and temporal characteristics of convenience stores and OHCA incidents in order to validate the feasibility of using our proposed GANSO to solve AED location-allocation optimization problems. Experiment results indicate that the highest priority for installing AEDs in Taipei communities should be given to convenience stores located in high-density areas. In commercial areas, AEDs in convenience stores can help compensate for temporal gaps in EMSs for cardiac arrest victims in general and for nighttime OHCA cases in particular. In residential areas, AEDs in convenience stores can help compensate for spatial gaps in terms of EMS delivery.



---

*Source: 241435-2014-06-17.xml*