# Optimization for the Locations of Ambulances under Two-Stage Life Rescue in the Emergency Medical Service: A Case Study in Shanghai, China

Authors: Ming Liu; Dapeng Yang; Fengxia Hao
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

With the development of society, public resources for healthcare are increasingly inadequate to meet the demands for the services. Therefore, it is extremely important for policymakers to provide citizens with the most effective healthcare services within the limited available resources. In order to achieve positive effect rescue operations in the Emergency Medical Services (EMS) system, the problems including where to locate the ambulance facilities and how many ambulance vehicles should be allocated to the stations have become the focus of attention. In this paper, we study the problem based on the demand for EMS in Songjiang District, Shanghai, China, followed by the joint planning of Emergency Medical Services management, which typically consists of ambulance facility locations planning and patient’s assignment to hospitals. We proposed a modified Double Standard Model (DSM) to maximize the demand points covered at least two times within the minimum coverage criteria. The problem is solved by integer linear programming technique with the CPLEX software and we make a comparison between the solutions and the locations which exist in the emergency system used by the Songjiang emergency center. Our results show that the demand coverage rate and response time can be efficiently improved through relocating the current facilities without additional vehicle resources.


---

## Body

## 1. Introduction

Because the Emergency Medical Services (EMS) provide the fundamental assistance and transportation for patients in need of urgent medical care in saving lives, numerous studies have been carried out in order to improve the quality of the EMS. However, under the pressure of the financial budget burden to meet the standard levels of performance criteria, EMS decision makers have to deal with the difficult tasks: where to locate the ambulance facilities, how many emergency vehicles can be allocated to the ambulance stations, and so forth. These kinds of problems become more and more complicated with the arrival of the aging society and the high population mobility, especially serious in the cities such as Shanghai and Beijing in China. According to the statistical data from Shanghai Municipal Commission of Health and Family Planning (SMCHF) in the year of 2014, the emergency calls in Shanghai climbed up to more than over 642 thousand times.Among the EMS literature, the problems of allocating ambulance vehicle resources and the location decisions of ambulance station have attracted special attention during the past decade of research (cf. Brotcorne et al. [1]; Li et al. [2]; Aringhieri et al. [3]). In order to improve the emergency efficiency for the service demand point, EMS departments manage to locate more ambulance vehicles or to add more ambulance stations. However, it is not reasonable to use a large number of vehicles or stations to cover the emergency demands. The new ambulance station construction cost is high and the ambulance vehicles are expensive (Su et al. [4]). Each service vehicle is completely equipped with all necessary emergency facilities that medical team may need in their missions (Moeini et al. [5]). Hence, with a limited number of ambulance vehicles, we need to have a balance between the ambulance stations and the desired objective.Though there is a substantial body of work on locating the emergency service vehicles and facilities planning, most existing models, solution approaches and studies in this research area concentrate on planning without considering the relationship between the ambulance facility locations and the hospitals destination. As one of the important aspects in the EMS, the selection of hospitals also plays a crucial role in the Emergency Medical Service for patients. Generally speaking, most studies considered that early detection, early response, and appropriate medical assistant are important factors in the EMS system. However, they are just the first stage in Emergency Medical Service. We should consider the distance between the demand point and the hospital, patients’ injury degree, and the ability and capacity of rescue team in hospitals as the second stage in the EMS system. Traditionally, most patients are sent to the nearest hospitals. As we all know, there is a hierarchy for the services provided by hospitals. In China, there are three different medical levels, where each level in a hospital has its own medical resources. On one hand, some badly wounded patients must be sent to the advanced hospitals; on the other hand, advanced hospitals have their own capacity limits, and not all the patients can be served by the advanced hospitals. For the sake of providing the first aid to patients efficiency in the emergency system, decision makers need to consider the demand characteristics, such as patients’ injury levels, and the existing hospitals’ service levels. To the best of our knowledge, only Yang et al. [6] have considered the two-stage emergency rescue in the EMS with the objective of the total social cost minimization, but they did not consider the ambulance vehicle busy fraction in their model.Under the above consideration, we are interested in proposing a new mathematical model that investigates the joint planning of ambulance station location, ambulance vehicle allocation, and the assignments of the ambulance stations to demand points and demand points to the hospitals. The new model is based on the Double Standard Model, called DSM. The DSM has been introduced by Gendreau et al. [7]. It aims to maximize the portion of demands being doubly covered within a primary standard and also ensures a full coverage within a secondary response standard. Both service coverage standards are measured as the travel time in minutes required by an ambulance vehicle to travel from an ambulance station to a demand point. In the DSM, all the patients’ injury level is implicitly assumed to be uniform. Therefore, patients cannot deal with the selections of ambulance stations and the corresponding hospitals. Also, in the DSM, the double service coverage treats each demand point separately and uniformly, which may generate results of service capacity redundancy for some demand points and shortage for other points. The chance constraint approach establishes a performance based reliability level by simultaneously considering the EMS vehicles and competing demand points, which could avoid the above limitations of imbalanced EMS vehicle allocation from the multiple service coverage approach (Liu et al. [8]).The remainder of the paper is organized as follows. In Section2, a brief literature review is given. Section 3 states the studied problem, and a mathematical formulation is proposed in Section 4. The model is tested on real-world data sets collected through the EMS system of Songjiang District, Shanghai. The computational experiments are reported in Section 5. Finally, the last section summarizes the work and indicates further research directions.


## 2. Related Work

Emergency Medical Service is a classical problem; it has attracted researchers’ attention in the last decade. There is a stream of literatures dedicated to the study of EMS, as it is vital and plays a preliminary function in providing high quality healthcare services in our life, which could give the first answer in distressing situations. We give a brief literature review which includes the most related references on ambulance location and the hospital selection.


### 2.1. Ambulance Location (Deterministic Models)

Most early proposed ambulance location models were integer linear formulations. Since these models did not consider the probability that an ambulance might be busy at a given time, they were classified as deterministic (Rajagopalan and Saydam [9]). The earliest EMS models have been introduced in the 70s by the articles of Toregas et al. [10] and Church and ReVelle [11]. Toregas et al. [10] studied the Location Set Covering Problem (LSCP) which identifies the minimum number of facilities and their locations that cover all demand points within a certain distance. However, the LSCP model cannot cover all demands with limited resources in reality, and one important thing is that once an ambulance is dispatched, some demand points are no longer covered. Due to the fact that LSCP model treats all demand points identically, the solution may require more ambulances than actually needed or underestimate the number of ambulances needed for those locations with relatively heavy demand (Saydam and Aytuǧ [12]). To avoid such limits, Church and ReVelle [11] proposed the Maximal Covering Location Problem (MCLP), which locates a fixed number of facilities so as to maximize the amount of demand that is covered by at least one facility.In each of the above models, a common problem is that coverage may become inadequate when some ambulance vehicles are busy. Hence, to compensate this shortcoming, most literature about the location problem of EMS have followed these two early studies by Toregas et al. (LSCP model) and Church and ReVelle (MCLP model). For example, Daskin and Stern [13] proposed a Hierarchical Objective Set Covering Problem model (HOSC), a hierarchical model for the LSCP, with the objective of minimizing the number of ambulance locations providing full coverage within a distance standard first and then maximizing the number of demand points under multiple coverage. As the HOSC may privilege the congestion of the ambulance, Hogan and ReVelle [14] proposed the Maximal Backup Coverage models BACOP 1 and BACOP 2. These models use two ambulances to cover the demands. Gendreau et al. [7] developed a model known as DSM in which all demands must be covered by ambulance located in a secondary coverage radius of r2 minutes, and in addition, a certain proportion of the demand must be covered in a primary coverage radius of r1 minutes. Liu et al. [8] proposed the service reliability for the demand points to make sure of double coverage.


### 2.2. Ambulance Location (Probabilistic Models)

Deterministic models did not account for the probability of a particular ambulance being busy at a given time and overestimated the actual coverage provided [9]. Hence, to compensate for this shortcoming, probabilistic models were later developed. Probabilistic location models recognized that any given ambulance may be busy when it is called. Such uncertainty can be modeled via programming techniques or using a queuing framework (Rajagopalan et al. [15]). One of the first probabilistic models for ambulance location is the Maximum Expected Coverage Location Problem (MEXCLP), which appears in Daskin [16]. He removed the implicit assumption of deterministic models; that is, all units are available at all times, by assuming each ambulance has the same probability q, called the busy fraction, of being unavailable to answer a call. He also assumed all ambulances are independent. Given a predetermined number of response units, MEXCLP maximizes the expected coverage subject to a response time standard.


### 2.3. Hospital Selection

For the hospital selection problem, a widely used rule consists of selecting the closest hospital to the demand points (Su and Shih [17]; Aboueljinane et al. [18]). However, Ingolfsson et al. [19] mentioned that the proximity could not be the only influencing factor as in Edmonton EMS, as 50% of patients are not transported to the closest hospitals. Savas [20] described some other factors that should be considered, such as the available capacity of hospitals, the hospital having the appropriate specialists, particular equipment for the patient, and the patient’s preference choice. Repoussis et al. [21] proposed a mixed integer linear programming formulation combining ambulance dispatching, patient to hospital assignment, and treatment ordering problem in mass-casualty incidents. Also, some researchers used the empirical distribution as estimated from historical data to select the area of the destination hospital (Ingolfsson et al. [19]; Repede and Bernardo [22]).With respect to the reviewed literature mentioned above, the requirements of locating ambulance facility in Emergency Medical Services are not onefold, and all the factors should be dealt with collectively, for practical purposes. Consequently, the main contribution of our study is that we propose a new mathematical model to address the problem of ambulance facility location jointly with hospital selection in the situation where there are patients with different types of injuries.


## 2.1. Ambulance Location (Deterministic Models)

Most early proposed ambulance location models were integer linear formulations. Since these models did not consider the probability that an ambulance might be busy at a given time, they were classified as deterministic (Rajagopalan and Saydam [9]). The earliest EMS models have been introduced in the 70s by the articles of Toregas et al. [10] and Church and ReVelle [11]. Toregas et al. [10] studied the Location Set Covering Problem (LSCP) which identifies the minimum number of facilities and their locations that cover all demand points within a certain distance. However, the LSCP model cannot cover all demands with limited resources in reality, and one important thing is that once an ambulance is dispatched, some demand points are no longer covered. Due to the fact that LSCP model treats all demand points identically, the solution may require more ambulances than actually needed or underestimate the number of ambulances needed for those locations with relatively heavy demand (Saydam and Aytuǧ [12]). To avoid such limits, Church and ReVelle [11] proposed the Maximal Covering Location Problem (MCLP), which locates a fixed number of facilities so as to maximize the amount of demand that is covered by at least one facility.In each of the above models, a common problem is that coverage may become inadequate when some ambulance vehicles are busy. Hence, to compensate this shortcoming, most literature about the location problem of EMS have followed these two early studies by Toregas et al. (LSCP model) and Church and ReVelle (MCLP model). For example, Daskin and Stern [13] proposed a Hierarchical Objective Set Covering Problem model (HOSC), a hierarchical model for the LSCP, with the objective of minimizing the number of ambulance locations providing full coverage within a distance standard first and then maximizing the number of demand points under multiple coverage. As the HOSC may privilege the congestion of the ambulance, Hogan and ReVelle [14] proposed the Maximal Backup Coverage models BACOP 1 and BACOP 2. These models use two ambulances to cover the demands. Gendreau et al. [7] developed a model known as DSM in which all demands must be covered by ambulance located in a secondary coverage radius of r2 minutes, and in addition, a certain proportion of the demand must be covered in a primary coverage radius of r1 minutes. Liu et al. [8] proposed the service reliability for the demand points to make sure of double coverage.


## 2.2. Ambulance Location (Probabilistic Models)

Deterministic models did not account for the probability of a particular ambulance being busy at a given time and overestimated the actual coverage provided [9]. Hence, to compensate for this shortcoming, probabilistic models were later developed. Probabilistic location models recognized that any given ambulance may be busy when it is called. Such uncertainty can be modeled via programming techniques or using a queuing framework (Rajagopalan et al. [15]). One of the first probabilistic models for ambulance location is the Maximum Expected Coverage Location Problem (MEXCLP), which appears in Daskin [16]. He removed the implicit assumption of deterministic models; that is, all units are available at all times, by assuming each ambulance has the same probability q, called the busy fraction, of being unavailable to answer a call. He also assumed all ambulances are independent. Given a predetermined number of response units, MEXCLP maximizes the expected coverage subject to a response time standard.


## 2.3. Hospital Selection

For the hospital selection problem, a widely used rule consists of selecting the closest hospital to the demand points (Su and Shih [17]; Aboueljinane et al. [18]). However, Ingolfsson et al. [19] mentioned that the proximity could not be the only influencing factor as in Edmonton EMS, as 50% of patients are not transported to the closest hospitals. Savas [20] described some other factors that should be considered, such as the available capacity of hospitals, the hospital having the appropriate specialists, particular equipment for the patient, and the patient’s preference choice. Repoussis et al. [21] proposed a mixed integer linear programming formulation combining ambulance dispatching, patient to hospital assignment, and treatment ordering problem in mass-casualty incidents. Also, some researchers used the empirical distribution as estimated from historical data to select the area of the destination hospital (Ingolfsson et al. [19]; Repede and Bernardo [22]).With respect to the reviewed literature mentioned above, the requirements of locating ambulance facility in Emergency Medical Services are not onefold, and all the factors should be dealt with collectively, for practical purposes. Consequently, the main contribution of our study is that we propose a new mathematical model to address the problem of ambulance facility location jointly with hospital selection in the situation where there are patients with different types of injuries.


## 3. Problem Statement

In this section, we first present the concerned problem in detail and then list the main assumptions.


### 3.1. Problem Description

Similar to the events sequence discussed by Nogueira et al. [23] for the EMS calls, Figure 1 depicts the sequence of events associated with an EMS management. An ambulance system begins immediately after an accident, such as traffic, natural disaster, and rebellion, and finishes once the patient has been delivered to a hospital. Some disease’s golden period for rescue is fairly short, such as heart disease in which a patient needs to receive help typically less than five minutes. The EMS department managers usually consider how to locate the ambulances in a coverage to access patients quickly. Most exciting literatures have considered the similar problems. Especially in 1973, the United States Emergency Medical Services Act set the “coverage” standards as follows: in urban areas, 95 percent of calls must be reached in 10 minutes, and in rural areas, calls should be reached in 30 minutes or less [24]. However, this is just the first phase in the EMS, as when an ambulance arrives at the demand point, only some simple treatments can be done, such as bandaging and CPR. This is because the ambulance can only load some basic medical devices and the patients’ diseases are various and complex. Therefore, how to transport a patient to a hospital facility quickly is also a curial decision considered in the EMS. Patients injury type is the first important factor considered in the transportation, and the hospital treatment capacity is another important factor which determines whether the patient can be transferred and accommodated. We call it as the second stage in the EMS when transferring the patient to the hospital.Figure 1
Flowchart for answering emergency calls.In this paper, we propose and formulate a joint location planning and ambulance assignment model based on the classic DSM. The objective of this model is to maximize the total number of demands covered by the primary coverage twice. LetJ be the set of potential vehicle locations, and let H be the set of hospitals. The set of demand locations is denoted by I. The problem is defined on two graphs, G1=(I∪J,A1) and G2=(I∪H,A2), where A1 is the set of edges {(i,j):i∈I,j∈J} and A2 is the set of edges {(i,h):i∈I,h∈H}. With each edge (j,i), the travel time from node j to node i is tji, and with edge (i,h), the travel time from node i to node h is tih. Each demand location i∈V is associated with a corresponding demand value di. The variable yijh=1 denotes the demand patient point i can be served by ambulance station j and be sent to hospital h. All demand locations must be reached within r1 minutes and at least have a proportion of λ of all the demand that must be covered by r2 minutes. The largest number of available vehicles can be located at a station denoted by B.When an emergency call is received from a demand pointi, the EMS department should send an ambulance vehicle to service it. But the ambulance may be busy, serving a competing demand at that time. As such, one or more vehicles in the neighborhood of the demand point i that could meet the service coverage standard should be targeted for the deployments to provide reliable service. In order to estimate the lowest number of ambulance vehicles needed to be deployed around demand point i to ensure a certain level of service reliability, a modified busy fraction of point i, denoted by qi, is introduced by [8] as follows:(1)qi=t¯∗∑l∈Ci,rfl24∗∑j∈Si,rzj=ρi∑j∈Si,rzj, in which the given parameter t¯ is the average service time by ambulance vehicle, the fixed parameter fl is the frequency of requests for emergency calls by competing demands around demand point i per day, Si,r=j∣j∈J,tji≤r denotes the set of ambulance station locations within the coverage r of demand point i, Ci,r=m∣m∈I,tjm≤r,j∈Si,r denotes the set of m competing demand points around demand point i, zj denotes the ambulance number in station j, and ρi is regarded as a given ratio. Assume the emergency calls are independent, and all demand points have the same local busy fraction, each following a binomial distribution. So the probability of having at least one vehicle available can be computed as follows:(2)1-qi∑j∈Si,rzj.With a predefined service reliability level,γ∈[0,1], for demand point i, to meet the requirement of having at least one ambulance vehicle that can service it within the coverage r, this constraint can be expressed as(3)1-ρi∑j∈Si,rzj∑j∈Si,rzj≥γ.The total number of ambulances in stationj∈Si,r can be expressed as follows:(4)∑j∈Si,rzj≥fi,r,where fi,r is the smallest integer meeting the following expression:(5)1-ρifi,rfi,r≥γ.


### 3.2. Assumptions for the Study

Some assumptions for this deterministic facility location and ambulance allocation problem are made as follows.(1)
We consider all hospitalsH, classified as level I (the higher level of care) and level II (the lower level of care).(2)
Each hospital has a fixed capacity ofQh, treating patients.(3)
To make full use of the hospital resources and give effective first aids to the patients, we also classified all the patients into two categories, as level I (the higher level of damage) and level II (the lower level of care).(4)
Once the primary treatment on scene is completed, a destination hospital has to be selected. Patients in damage level I can only be sent to the hospital level I, and the damage level II can be sent to either hospital level I or hospital level II.(5)
In our research, the traveling time from the demand point to the hospital should not exceed thirty minutes and the patient should be sent to the nearest hospital with appropriate service.


## 3.1. Problem Description

Similar to the events sequence discussed by Nogueira et al. [23] for the EMS calls, Figure 1 depicts the sequence of events associated with an EMS management. An ambulance system begins immediately after an accident, such as traffic, natural disaster, and rebellion, and finishes once the patient has been delivered to a hospital. Some disease’s golden period for rescue is fairly short, such as heart disease in which a patient needs to receive help typically less than five minutes. The EMS department managers usually consider how to locate the ambulances in a coverage to access patients quickly. Most exciting literatures have considered the similar problems. Especially in 1973, the United States Emergency Medical Services Act set the “coverage” standards as follows: in urban areas, 95 percent of calls must be reached in 10 minutes, and in rural areas, calls should be reached in 30 minutes or less [24]. However, this is just the first phase in the EMS, as when an ambulance arrives at the demand point, only some simple treatments can be done, such as bandaging and CPR. This is because the ambulance can only load some basic medical devices and the patients’ diseases are various and complex. Therefore, how to transport a patient to a hospital facility quickly is also a curial decision considered in the EMS. Patients injury type is the first important factor considered in the transportation, and the hospital treatment capacity is another important factor which determines whether the patient can be transferred and accommodated. We call it as the second stage in the EMS when transferring the patient to the hospital.Figure 1
Flowchart for answering emergency calls.In this paper, we propose and formulate a joint location planning and ambulance assignment model based on the classic DSM. The objective of this model is to maximize the total number of demands covered by the primary coverage twice. LetJ be the set of potential vehicle locations, and let H be the set of hospitals. The set of demand locations is denoted by I. The problem is defined on two graphs, G1=(I∪J,A1) and G2=(I∪H,A2), where A1 is the set of edges {(i,j):i∈I,j∈J} and A2 is the set of edges {(i,h):i∈I,h∈H}. With each edge (j,i), the travel time from node j to node i is tji, and with edge (i,h), the travel time from node i to node h is tih. Each demand location i∈V is associated with a corresponding demand value di. The variable yijh=1 denotes the demand patient point i can be served by ambulance station j and be sent to hospital h. All demand locations must be reached within r1 minutes and at least have a proportion of λ of all the demand that must be covered by r2 minutes. The largest number of available vehicles can be located at a station denoted by B.When an emergency call is received from a demand pointi, the EMS department should send an ambulance vehicle to service it. But the ambulance may be busy, serving a competing demand at that time. As such, one or more vehicles in the neighborhood of the demand point i that could meet the service coverage standard should be targeted for the deployments to provide reliable service. In order to estimate the lowest number of ambulance vehicles needed to be deployed around demand point i to ensure a certain level of service reliability, a modified busy fraction of point i, denoted by qi, is introduced by [8] as follows:(1)qi=t¯∗∑l∈Ci,rfl24∗∑j∈Si,rzj=ρi∑j∈Si,rzj, in which the given parameter t¯ is the average service time by ambulance vehicle, the fixed parameter fl is the frequency of requests for emergency calls by competing demands around demand point i per day, Si,r=j∣j∈J,tji≤r denotes the set of ambulance station locations within the coverage r of demand point i, Ci,r=m∣m∈I,tjm≤r,j∈Si,r denotes the set of m competing demand points around demand point i, zj denotes the ambulance number in station j, and ρi is regarded as a given ratio. Assume the emergency calls are independent, and all demand points have the same local busy fraction, each following a binomial distribution. So the probability of having at least one vehicle available can be computed as follows:(2)1-qi∑j∈Si,rzj.With a predefined service reliability level,γ∈[0,1], for demand point i, to meet the requirement of having at least one ambulance vehicle that can service it within the coverage r, this constraint can be expressed as(3)1-ρi∑j∈Si,rzj∑j∈Si,rzj≥γ.The total number of ambulances in stationj∈Si,r can be expressed as follows:(4)∑j∈Si,rzj≥fi,r,where fi,r is the smallest integer meeting the following expression:(5)1-ρifi,rfi,r≥γ.


## 3.2. Assumptions for the Study

Some assumptions for this deterministic facility location and ambulance allocation problem are made as follows.(1)
We consider all hospitalsH, classified as level I (the higher level of care) and level II (the lower level of care).(2)
Each hospital has a fixed capacity ofQh, treating patients.(3)
To make full use of the hospital resources and give effective first aids to the patients, we also classified all the patients into two categories, as level I (the higher level of damage) and level II (the lower level of care).(4)
Once the primary treatment on scene is completed, a destination hospital has to be selected. Patients in damage level I can only be sent to the hospital level I, and the damage level II can be sent to either hospital level I or hospital level II.(5)
In our research, the traveling time from the demand point to the hospital should not exceed thirty minutes and the patient should be sent to the nearest hospital with appropriate service.


## 4. Mathematical Model

In Section4.1, we formally give the definitions of the problem parameters and the decision variables. In Section 4.2, we present a mathematical model for the problem.


### 4.1. Notation

Index Sets
I: set of the demand points indexed by i, i∈I=1,…,n.
J: set of the potential ambulance locations indexed by j, j∈J=1,…,m.
H: set of the hospitals indexed by h, h∈H=1,…,h.
S
i
,
r: set of ambulance station locations with r coverage of the demand point i with tji≤r.
C
i
,
r: set of m competing demand points around demand point i, with any ambulance station j∈Si,r and tjm≤r.Problem Parameters
K: upper bound of the total ambulance vehicles.
B: upper bound of the ambulance in each station.
μ
h: the type of the hospital h: 1 means it has advanced medical level and 2 means otherwise.
φ
i: the type of the patient in demand i: 1 means patient is badly hurt and 2 otherwise.
γ: the service reliability level.
Q
h: the treatment capacity of hospital h.
d
i: the density of the emergency demand at point i.
q
i: the demand point i’s ambulance vehicle busy fraction.
λ: the portion of demand points covered within the primary standard r1.
f
i
,
r: the smallest number of vehicles assigned around demand point i at ambulance station j∈Si,r, which satisfies 1-ρi/fi,rfi,r≥γ.
t
¯: average service time including the time from ambulance station to demand point, demand point to hospital plus the time from hospital to ambulance station, and the corresponding round trip of an ambulance.
t
j
i: time needed for ambulance from ambulation station j to demand point i.
t
i
h: time needed for ambulance transferring patient from demand point i to hospital h.
δ
i
j: a binary parameter, equal to 1 if tji≤r2 minutes (secondary standard), 0 otherwise.
θ
i
j: a binary parameter, equal to 1 if tji≤r1 minutes (primary standard), 0 otherwise.
α
i
h: a binary parameter, equal to 1 if tih≤r3 minutes, 0 otherwise.
β
i
h: a binary parameter, equal to 1 if patients’ damage level matches hospital h’s level, that is, φi≥μh, 0 otherwise.
M: a sufficiently large integer.Decision Variables
y
i
j
h: binary, equal to 1 if ambulance at station j services demand point i and sent the patient to hospital h, 0 otherwise.
x
j: binary, equal to 1 if ambulance station j is open, 0 otherwise.
u
i
1: binary, equal to 1 if demand point i is covered one time by an ambulance vehicle within primary standard r1 at reliability level γ, 0 otherwise.
u
i
2: binary, equal to 1 if demand point i is covered two times by an ambulance vehicle within primary standard r1 at reliability level γ, 0 otherwise.
z
j: integer, the number of vehicles located at station j.


### 4.2. The Formulation of the Problem

(6)
m
a
x
Z
=
∑
i
=
1
n
d
i
∗
u
i
2
. Objective (6) means to maximize the demands in primary coverage r1 covered two times.(7)∑j=1m∑h=1hyijh=1i∈I,di>0. Constraint (7) means that every demand must be serviced by one ambulance station and sent to a hospital.(8)∑j=1mzj∗δij≥1i∈I. Constraint (8) means that every demand must be serviced by at least one ambulance vehicle at least.(9)∑i=1ndi∗ui1≥λ∗∑i=1ndii∈I. Constraint (9) ensures that a proportion λ of the demands must be covered in primary standard r1.(10)∑i=1n∑h=1hyijh≤M∗xjj∈J.∑i=1n∑h=1hyijh≥xjj∈J.Constraint (10) ensures that any demand point can only be serviced by an opened ambulance station. These constraints link variables yijh and xj.(11)zj≤B∗xjj∈J. Constraint (11) means that the number of ambulance vehicles in each ambulance station cannot exceed B.(12)zj≥xjj∈J. Constraint (12) guarantees that if the ambulance station is constructed, there is at least one ambulance vehicle. This constraint links variables zj and xj.(13)∑j=1mzj≤K. Constraint (13) denotes that the total number of ambulance vehicles should not exceed K.(14)∑j=1mzj≥ui1+ui2i∈I. In constraint (14), the left-hand side is the total number of the vehicles that covered site i within primary standard r1, and it should not be less than the summation of single and double coverage indicators, which is the right-hand side of the inequality.(15)ui1≥ui2i∈I. Constraint (15) ensures that demand site i can be doubly covered only if it is already singly covered. This constraint links variables ui1 and ui2.(16)∑j=1mzj∗θij≥fi,r∗ui1i∈I. Constraint (16) is a service reliability constraint, which ensures that point i must be covered by ambulances with service reliability level γ.(17)∑i=1ndi∑j=1myijh≤Qhh∈H. Constraint (17) ensures that the total number of patients transferred to a hospital should not exceed its own capacity.(18)∑j=1myijh≤αihi∈I,h∈H. Constraints (18) ensures that the travel time or distance between demand site i and the hospital h should not exceed r3 minutes.(19)∑j=1myijh≤βihi∈I,h∈H. Constraint (19) guarantees that the patient injury type must be matched with the hospital level.(20)yijh∈0,1i∈I,j∈J,h∈H,xj∈0,1j∈J,ui1∈0,1i∈I,ui2∈0,1i∈I,zj≥0j∈J.Constraint (20) defines the domains of the decision variables.


## 4.1. Notation

Index Sets
I: set of the demand points indexed by i, i∈I=1,…,n.
J: set of the potential ambulance locations indexed by j, j∈J=1,…,m.
H: set of the hospitals indexed by h, h∈H=1,…,h.
S
i
,
r: set of ambulance station locations with r coverage of the demand point i with tji≤r.
C
i
,
r: set of m competing demand points around demand point i, with any ambulance station j∈Si,r and tjm≤r.Problem Parameters
K: upper bound of the total ambulance vehicles.
B: upper bound of the ambulance in each station.
μ
h: the type of the hospital h: 1 means it has advanced medical level and 2 means otherwise.
φ
i: the type of the patient in demand i: 1 means patient is badly hurt and 2 otherwise.
γ: the service reliability level.
Q
h: the treatment capacity of hospital h.
d
i: the density of the emergency demand at point i.
q
i: the demand point i’s ambulance vehicle busy fraction.
λ: the portion of demand points covered within the primary standard r1.
f
i
,
r: the smallest number of vehicles assigned around demand point i at ambulance station j∈Si,r, which satisfies 1-ρi/fi,rfi,r≥γ.
t
¯: average service time including the time from ambulance station to demand point, demand point to hospital plus the time from hospital to ambulance station, and the corresponding round trip of an ambulance.
t
j
i: time needed for ambulance from ambulation station j to demand point i.
t
i
h: time needed for ambulance transferring patient from demand point i to hospital h.
δ
i
j: a binary parameter, equal to 1 if tji≤r2 minutes (secondary standard), 0 otherwise.
θ
i
j: a binary parameter, equal to 1 if tji≤r1 minutes (primary standard), 0 otherwise.
α
i
h: a binary parameter, equal to 1 if tih≤r3 minutes, 0 otherwise.
β
i
h: a binary parameter, equal to 1 if patients’ damage level matches hospital h’s level, that is, φi≥μh, 0 otherwise.
M: a sufficiently large integer.Decision Variables
y
i
j
h: binary, equal to 1 if ambulance at station j services demand point i and sent the patient to hospital h, 0 otherwise.
x
j: binary, equal to 1 if ambulance station j is open, 0 otherwise.
u
i
1: binary, equal to 1 if demand point i is covered one time by an ambulance vehicle within primary standard r1 at reliability level γ, 0 otherwise.
u
i
2: binary, equal to 1 if demand point i is covered two times by an ambulance vehicle within primary standard r1 at reliability level γ, 0 otherwise.
z
j: integer, the number of vehicles located at station j.


## 4.2. The Formulation of the Problem

(6)
m
a
x
Z
=
∑
i
=
1
n
d
i
∗
u
i
2
. Objective (6) means to maximize the demands in primary coverage r1 covered two times.(7)∑j=1m∑h=1hyijh=1i∈I,di>0. Constraint (7) means that every demand must be serviced by one ambulance station and sent to a hospital.(8)∑j=1mzj∗δij≥1i∈I. Constraint (8) means that every demand must be serviced by at least one ambulance vehicle at least.(9)∑i=1ndi∗ui1≥λ∗∑i=1ndii∈I. Constraint (9) ensures that a proportion λ of the demands must be covered in primary standard r1.(10)∑i=1n∑h=1hyijh≤M∗xjj∈J.∑i=1n∑h=1hyijh≥xjj∈J.Constraint (10) ensures that any demand point can only be serviced by an opened ambulance station. These constraints link variables yijh and xj.(11)zj≤B∗xjj∈J. Constraint (11) means that the number of ambulance vehicles in each ambulance station cannot exceed B.(12)zj≥xjj∈J. Constraint (12) guarantees that if the ambulance station is constructed, there is at least one ambulance vehicle. This constraint links variables zj and xj.(13)∑j=1mzj≤K. Constraint (13) denotes that the total number of ambulance vehicles should not exceed K.(14)∑j=1mzj≥ui1+ui2i∈I. In constraint (14), the left-hand side is the total number of the vehicles that covered site i within primary standard r1, and it should not be less than the summation of single and double coverage indicators, which is the right-hand side of the inequality.(15)ui1≥ui2i∈I. Constraint (15) ensures that demand site i can be doubly covered only if it is already singly covered. This constraint links variables ui1 and ui2.(16)∑j=1mzj∗θij≥fi,r∗ui1i∈I. Constraint (16) is a service reliability constraint, which ensures that point i must be covered by ambulances with service reliability level γ.(17)∑i=1ndi∑j=1myijh≤Qhh∈H. Constraint (17) ensures that the total number of patients transferred to a hospital should not exceed its own capacity.(18)∑j=1myijh≤αihi∈I,h∈H. Constraints (18) ensures that the travel time or distance between demand site i and the hospital h should not exceed r3 minutes.(19)∑j=1myijh≤βihi∈I,h∈H. Constraint (19) guarantees that the patient injury type must be matched with the hospital level.(20)yijh∈0,1i∈I,j∈J,h∈H,xj∈0,1j∈J,ui1∈0,1i∈I,ui2∈0,1i∈I,zj≥0j∈J.Constraint (20) defines the domains of the decision variables.


## 5. Case Study and Computational Results

In this section, we apply our model to the ambulance assignment optimization based on data obtained from Shanghai Trauma Emergency Center.


### 5.1. Database Analysis

Our case study corresponds to the EMS system in Songjiang District, Shanghai, China. Songjiang has a size of about 605 km2 and a resident population of approximately 1.75 million (2015). The urban extension is about 23.8 km in the north-south direction, 24.6 km in the east-west direction, and 39.3 km in the southwest-northeast direction. It currently has 17 administrative regions and the average population density is about 2893 inhabitants per square kilometer.


#### 5.1.1. Demand Points

The large number of EMS call locations makes it difficult to handle the ambulance station location optimization problem. In order to simplify the complexity of the ambulance location problem, most previous studies considered the center point of the administrative regions as the demand points [6]. But for some cities, the boundary of administrative regions is irregular, and thus it is hard to find the central points. And even worse, for some small countries, the administrative regions’ boundary is fuzzy. Based on the above consideration, we organize the county into 2-kilometer ∗ 2-kilometer square nodes with Arcgis 10.2 software. This gives us a total of 187 demand nodes and we assumed that the ambulances can be posted in any one of the nodes except in the nodes that make up the boundary. This can be seen in Figure 2 which displays all the demand points. Each demand point has patients of one or both of badly injured type and generally injured type. The EMS call center of the city receives more than 25,000 calls in the year of 2013, but just about 20,000 calls require ambulance vehicles. The spatial distribution of the whole year in 2013 can be seen in Figure 3. And the number of two types of patients in each demand point is seen in Figure 4.Figure 2
Location of 187 demand points.Figure 3
Locations of 8 current ambulance stations and 19447 EMS call origination points in Songjiang; EMS calls are marked as small red dots, and the 8 stations currently used are marked with a black cross. EMS calls from January 1 to December 31, 2013.Figure 4
Demand per demand point, where each colored line represents the injury of the patients.


#### 5.1.2. Demand Scenarios

To reflect the realistic demands, EMS calls would be further classified based on their time and date. Days are classified into workdays (Monday through Friday) and off-days (weekends and holidays) and the call times are arranged into four periods of a single day: (i) dawn (00:00 AM–6:00 AM), (ii) morning (6:00 AM–12:00 PM), (iii) afternoon (12:00 PM–18:00 PM), and (iv) evening (18:00 PM–24:00 PM). The number of emergency calls of the patients in each of these 8 scenarios is shown in Table1.Table 1
Distribution of calls from January 1 to December 31, 2013.
Scenario
Day time
Day type
Badly injured
General injury
Demand count
Proportion
1
Dawn
Workdays
192
1560
1752
9.0%
2
Morning
Workdays
469
3734
4203
21.6%
3
Afternoon
Workdays
411
3463
3874
19.9%
4
Evening
Workdays
395
3243
3638
18.7%
5
Dawn
Off-days
79
815
894
4.6%
6
Morning
Off-days
189
1446
1752
8.4%
7
Afternoon
Off-days
240
1522
1762
9.1%
8
Evening
Off-days
164
1525
1689
8.7%
Total
2139
17308
19447
100%


#### 5.1.3. Potential Ambulance Station Locations and the Hospital Locations

We selected a total of 17 potential ambulance location sites in the city of Songjiang including the hospitals and community health service centers. The current 8 ambulance stations are also in our potential location sites and we add the remaining potential stations in each administrative region mentioned in the previous context. All the potential ambulance stations’ information in detail can be seen in Figure2 and Table 2. From the detailed emergency call records, we find that there are more than 50 hospitals that are the potential destination hospitals. But some hospitals received the amount of patients in single digit in the whole year. Finally, we select 29 hospitals as the destination hospitals, each of which has received more than ten patients according to the emergency call records. Table 3 shows the detailed coordinates data for these hospitals. All the geographic coordinates of these potential stations and hospitals are obtained from the Baidu API with JAVA program; then we convert them into WGS-84 coordinates through Arcgis 10.2 software.Table 2
The detailed information of the potential ambulance stations.
Station ID
Ambulance count
Region
Property
WGS-84 coordinates
1
2
Che Dun
Current
31.01609698
121.2995794
2
2
Ye Xie
Current
30.94145835
121.3132912
3
2
Se San
Current
31.09752613
121.1760262
4
3
Xin Bang
Current
30.93380957
121.0623737
5
3
Si Jing
Current
31.12191941
121.2501306
6
2
Jiu Ting
Current
31.13326665
121.3150484
7
6
Lao Chengqu
Current
31.00930546
121.2173128
8
9
Zhong Xin
Current
31.04150089
121.2209912
9
—
Xin Qiao
Adding
31.06454997
121.3122161
10
—
Shi Hudang
Adding
30.98881041
121.1155610
11
—
Mao Gang
Adding
30.93558684
121.2061368
12
—
Xiao Kunshan
Adding
31.03015255
121.1206874
13
—
Dong Jing
Adding
31.08462687
121.2778089
14
—
Fang Song
Adding
31.03461475
121.2029791
15
—
Yong Feng
Adding
31.01882373
121.1885977
16
—
Yue Yang
Adding
31.00817409
121.2264765
17
—
Zhong Shan
Adding
31.02874777
121.2418646Table 3
The detailed information of hospitals.
Hospital ID
Hospital name
WGS-84 coordinates
1
Central Hospital of Songjiang District
31.0093054
121.2173128
2
Shanghai General Hospital of Songjiang Branch
31.04150089
121.2209912
3
Central Hospital of Minhang District
31.11021934
121.3716066
4
Sijing Hospital of Songjiang District
31.12191941
121.2501306
5
Jiuting Hospital of Songjiang District
31.13326665
121.3150484
6
Children’s Hospital of Fudan University
31.14094419
121.3916987
7
Health Center for Women and Children of Songjiang District
31.02702047
121.2145908
8
Shanghai No. 6 People Hospital
31.18098825
121.4192638
9
Armed Police Corps Hospital of Shanghai
31.19437713
121.3845042
10
Fangta Hospital of Traditional Chinese Medicine of Songjiang District
31.00850645
121.2480138
11
85 Hospital of People’s Liberation Army
31.21162286
121.4277839
12
Ruijin Hospital Shanghai Jiaotong University School of Medicine
31.21244079
121.4618436
13
International Peace Maternity and Child Health Hospital
31.19873795
121.4336423
14
455 Hospital of Chinese People’s Liberation Army
31.20217576
121.4232472
15
Zhongshan Hospital of Fudan University
31.19963334
121.4502016
16
Ledu Hospital of Songjiang District
31.01587166
121.2268316
17
Huashan Hospital of Fudan University
31.21836632
121.4383563
18
Shanghai No. 8 People Hospital
31.16975424
121.4282042
19
Shanghai No. 9 People Hospital
31.20422312
121.4813137
20
Health Center for Women and Children of Minhang District
31.14230556
121.3887969
21
Health Center for Women and Children of Changning District
31.21485631
121.4099054
22
Longhua Hospital Shanghai University of Traditional Chinese Medicine
31.18947654
121.4454596
23
Xinbang Community Health Service Center of Songjiang District
30.93334086
121.0623618
24
Huadong Hospital of Fudan University
31.22139226
121.4372887
25
Xinbang Community Health Service Center of Songjiang District
31.06454997
121.3122161
26
Shanghai Chest Hospital
31.19987994
121.420508
27
Jiuting Community Health Service Center of Songjiang District
31.11773795
121.3223082
28
Shanghai No. 5 People Hospital
31.00815517
121.4038781
29
Central Hospital of Changning District
31.21092818
121.3726881


### 5.2. Results and Discussion

In our experiments, we suppose that each of the emergency calls must be covered in less than 12 minutes; that is to say, the secondary coverage is twelve minutes following the standards set from the 13th Five-Year Plan of Shanghai prehospital service of first aid by the Shanghai Municipal Commission of Health and Family Planning (SMCHF) in the year of 2016. At least60% of the calls must be covered in 8 minutes with the prespecified service reliability level of 90%, which means λ≥60% and γ=90%. The number of ambulances in the system is K=29, which is the exact number of ambulances operated in 2013. Furthermore, the maximum number of ambulances per station is 4.The shortest travel time from ambulance stations to demand points and from demand points to hospitals is calculated on the basis of Euclidean distance. The running average speed of an ambulance is 55 km/ph, which is consistent with the traffic condition for most of the Shanghai urban streets.Sincefi,r in the proposed model is determined by the ratio ρi and service reliability level γ using (5), it is imperative to compute ρi by using (1) prior to estimating fi,r. The service call frequency at each demand point uses data in the year of 2013 calls, and we get the day average call per demand point. The average service time for EMS vehicles is set to be 0.9 h, which is calculated through 19,447 EMS calls received in the year of 2013. With the above parameter values, the steps to compute ratio ρi for a demand point i are as follows [8]: (i) finding all the ambulance station sets which can service demand point i, that is, j∈Si,r; (ii) determining all demand points, including i, that are within the coverage of 5 minutes for each ambulance station in Si,r, then summing their competing demands fl, and ensuring no duplication; (iii) computing the ratio by (1). Finally, the smallest integer fi,r can be found by iterations (or binary search).The solutions reported in the next section have been carried out on Intel Core™ i7-6700K CPU @ 4.00 GHz with 32 GB of RAM. The standard solver Gurobi (version 7.0.1) has been used to solve the integer linear programming model, coded with C++. Since the size of the model is not too large, solution time for each integer program run is less than ten minutes.


#### 5.2.1. Current Ambulance Station

We start from investigating the performance of the 8 stations and 29 ambulances currently utilized by the EMS system in Songjiang District. We attempted to solve our model by limiting potential bases to these 8 stations. The resulting optimization problem is infeasible, indicating that the current bases cannot satisfy the predefined EMS standards. This is the case even if the secondary coverage fractionλ is set to be 0, which indicates that the current bases cannot ensure the second coverage within r2=12 minutes. In fact, the smallest value of r2 for which we could obtain a feasible solution was 13 minutes. Even so, feasibility is attained only for a maximum value of λ = 0.3, which corresponds to 30% coverage within r1=8 minutes. The conclusion is that the current bases are far from achieving both primary and secondary coverage requirements. Those two cases are listed in Table 4.Table 4
Results of the ambulance location problem in current Songjiang EMS system.
Problem ID
Current station set
r
2 (min)
λ
Station numbers needed
Objective
1
8 stations
12
60%
Unfeasible
—
2
8 stations
13
30%
8
6011


#### 5.2.2. Is There a Feasible Solution of 8 Ambulance Stations?

Having failed to meet the predetermined standards with the current 8 bases, we seek to determine whether any other set of 8 bases would satisfy those requirements. In order to handle this problem, we need to add an additional constraint on the maximum number of bases. To find out the reasons why the optimization based on current ambulance stations fails to meet the coverage standard, we used the same quantity of ambulance stations. After solving the above model, we found that it is possible to locate a different set of ambulances from all the potential ambulance stations which fulfill the full coverage withinr2=12 minutes, with the limitation. When we used the problem 2’s r2 standard r2=13 minutes, we can get the proportion with λ=0.46. Table 5 shows the trade-off between the proportion λ and the objective value. Figures 5 and 6 show the 8 optimal ambulance locations within all the demand points satisfying the service coverage in 13 minutes and 12 minutes, respectively.Table 5
Results of the ambulance location problem in Songjiang EMS system.
Problem ID
Potential station set
r
2 (min)
λ
Station numbers needed
Objective
3
Any 8 stations
13
46%
8
9091
4
Any 8 stations
12
42%
8
8290Figure 5
Optimal locations of any 8 ambulance stations inr2=13 minutes.Figure 6
Optimal locations of any 8 ambulance stations inr2=12 minutes.


#### 5.2.3. Optimization for All Ambulance Stations

Finally, we solve the concerned problem allowing all 17 potential bases to be optimized. In this context, the problem is feasible with the probationλ≥0.6 and the service reliability γ=0.9. After optimizing, λ can reach 0.71. The optimal objective value is shown in Table 6. Figure 7 shows the detailed optimal locations of the ambulance stations.Table 6
Results of the ambulance location problem in Songjiang EMS system.
Problem ID
Potential station set
r
2 (min)
λ
Station numbers needed
Objective
5
All stations (17 stations)
12
71%
12
13881Figure 7
Optimal locations of ambulance stations among all the potential locations.


#### 5.2.4. Comparisons with Classical Models

We compare the model proposed in this paper with the classic DSM. This is because the model proposed in this paper is derived from classical DSM. The proposed model formulation considers two-stage rescue. We want to find out the difference between the classic DSM and our proposed model. However, in our model, we consider service reliability, which aims to find the optimal deployments of EMS vehicles to achieve maximized coverage of demand points. Each covered demand point is serviced by at least one ambulance in90% of the time. In order to examine the effect considering two-stage rescue, our model is slightly modified by removing the reliability constraint. Results are shown in Figures 8 and 9. The proposed model can achieve a better objective value than the DSM, with the primary coverage r1=8 minutes. An interesting phenomenon is that when the number of stations exceeds eleven, our model can get full coverage. Besides, the coverage value obtained from the classic DSM cannot increase even if the number of stations exceeds nine. As for the range of primary coverage standard r1, our model can achieve full coverage in 8 minutes. However, the classic model gets full coverage with 12 minutes.Figure 8
Comparisons of double coverage within the same primary standardr1=8 minutes (without considering service reliability).Figure 9
Comparisons of double coverage count in different primary standardr1 within the same ambulance stations (without considering service reliability).


## 5.1. Database Analysis

Our case study corresponds to the EMS system in Songjiang District, Shanghai, China. Songjiang has a size of about 605 km2 and a resident population of approximately 1.75 million (2015). The urban extension is about 23.8 km in the north-south direction, 24.6 km in the east-west direction, and 39.3 km in the southwest-northeast direction. It currently has 17 administrative regions and the average population density is about 2893 inhabitants per square kilometer.


### 5.1.1. Demand Points

The large number of EMS call locations makes it difficult to handle the ambulance station location optimization problem. In order to simplify the complexity of the ambulance location problem, most previous studies considered the center point of the administrative regions as the demand points [6]. But for some cities, the boundary of administrative regions is irregular, and thus it is hard to find the central points. And even worse, for some small countries, the administrative regions’ boundary is fuzzy. Based on the above consideration, we organize the county into 2-kilometer ∗ 2-kilometer square nodes with Arcgis 10.2 software. This gives us a total of 187 demand nodes and we assumed that the ambulances can be posted in any one of the nodes except in the nodes that make up the boundary. This can be seen in Figure 2 which displays all the demand points. Each demand point has patients of one or both of badly injured type and generally injured type. The EMS call center of the city receives more than 25,000 calls in the year of 2013, but just about 20,000 calls require ambulance vehicles. The spatial distribution of the whole year in 2013 can be seen in Figure 3. And the number of two types of patients in each demand point is seen in Figure 4.Figure 2
Location of 187 demand points.Figure 3
Locations of 8 current ambulance stations and 19447 EMS call origination points in Songjiang; EMS calls are marked as small red dots, and the 8 stations currently used are marked with a black cross. EMS calls from January 1 to December 31, 2013.Figure 4
Demand per demand point, where each colored line represents the injury of the patients.


### 5.1.2. Demand Scenarios

To reflect the realistic demands, EMS calls would be further classified based on their time and date. Days are classified into workdays (Monday through Friday) and off-days (weekends and holidays) and the call times are arranged into four periods of a single day: (i) dawn (00:00 AM–6:00 AM), (ii) morning (6:00 AM–12:00 PM), (iii) afternoon (12:00 PM–18:00 PM), and (iv) evening (18:00 PM–24:00 PM). The number of emergency calls of the patients in each of these 8 scenarios is shown in Table1.Table 1
Distribution of calls from January 1 to December 31, 2013.
Scenario
Day time
Day type
Badly injured
General injury
Demand count
Proportion
1
Dawn
Workdays
192
1560
1752
9.0%
2
Morning
Workdays
469
3734
4203
21.6%
3
Afternoon
Workdays
411
3463
3874
19.9%
4
Evening
Workdays
395
3243
3638
18.7%
5
Dawn
Off-days
79
815
894
4.6%
6
Morning
Off-days
189
1446
1752
8.4%
7
Afternoon
Off-days
240
1522
1762
9.1%
8
Evening
Off-days
164
1525
1689
8.7%
Total
2139
17308
19447
100%


### 5.1.3. Potential Ambulance Station Locations and the Hospital Locations

We selected a total of 17 potential ambulance location sites in the city of Songjiang including the hospitals and community health service centers. The current 8 ambulance stations are also in our potential location sites and we add the remaining potential stations in each administrative region mentioned in the previous context. All the potential ambulance stations’ information in detail can be seen in Figure2 and Table 2. From the detailed emergency call records, we find that there are more than 50 hospitals that are the potential destination hospitals. But some hospitals received the amount of patients in single digit in the whole year. Finally, we select 29 hospitals as the destination hospitals, each of which has received more than ten patients according to the emergency call records. Table 3 shows the detailed coordinates data for these hospitals. All the geographic coordinates of these potential stations and hospitals are obtained from the Baidu API with JAVA program; then we convert them into WGS-84 coordinates through Arcgis 10.2 software.Table 2
The detailed information of the potential ambulance stations.
Station ID
Ambulance count
Region
Property
WGS-84 coordinates
1
2
Che Dun
Current
31.01609698
121.2995794
2
2
Ye Xie
Current
30.94145835
121.3132912
3
2
Se San
Current
31.09752613
121.1760262
4
3
Xin Bang
Current
30.93380957
121.0623737
5
3
Si Jing
Current
31.12191941
121.2501306
6
2
Jiu Ting
Current
31.13326665
121.3150484
7
6
Lao Chengqu
Current
31.00930546
121.2173128
8
9
Zhong Xin
Current
31.04150089
121.2209912
9
—
Xin Qiao
Adding
31.06454997
121.3122161
10
—
Shi Hudang
Adding
30.98881041
121.1155610
11
—
Mao Gang
Adding
30.93558684
121.2061368
12
—
Xiao Kunshan
Adding
31.03015255
121.1206874
13
—
Dong Jing
Adding
31.08462687
121.2778089
14
—
Fang Song
Adding
31.03461475
121.2029791
15
—
Yong Feng
Adding
31.01882373
121.1885977
16
—
Yue Yang
Adding
31.00817409
121.2264765
17
—
Zhong Shan
Adding
31.02874777
121.2418646Table 3
The detailed information of hospitals.
Hospital ID
Hospital name
WGS-84 coordinates
1
Central Hospital of Songjiang District
31.0093054
121.2173128
2
Shanghai General Hospital of Songjiang Branch
31.04150089
121.2209912
3
Central Hospital of Minhang District
31.11021934
121.3716066
4
Sijing Hospital of Songjiang District
31.12191941
121.2501306
5
Jiuting Hospital of Songjiang District
31.13326665
121.3150484
6
Children’s Hospital of Fudan University
31.14094419
121.3916987
7
Health Center for Women and Children of Songjiang District
31.02702047
121.2145908
8
Shanghai No. 6 People Hospital
31.18098825
121.4192638
9
Armed Police Corps Hospital of Shanghai
31.19437713
121.3845042
10
Fangta Hospital of Traditional Chinese Medicine of Songjiang District
31.00850645
121.2480138
11
85 Hospital of People’s Liberation Army
31.21162286
121.4277839
12
Ruijin Hospital Shanghai Jiaotong University School of Medicine
31.21244079
121.4618436
13
International Peace Maternity and Child Health Hospital
31.19873795
121.4336423
14
455 Hospital of Chinese People’s Liberation Army
31.20217576
121.4232472
15
Zhongshan Hospital of Fudan University
31.19963334
121.4502016
16
Ledu Hospital of Songjiang District
31.01587166
121.2268316
17
Huashan Hospital of Fudan University
31.21836632
121.4383563
18
Shanghai No. 8 People Hospital
31.16975424
121.4282042
19
Shanghai No. 9 People Hospital
31.20422312
121.4813137
20
Health Center for Women and Children of Minhang District
31.14230556
121.3887969
21
Health Center for Women and Children of Changning District
31.21485631
121.4099054
22
Longhua Hospital Shanghai University of Traditional Chinese Medicine
31.18947654
121.4454596
23
Xinbang Community Health Service Center of Songjiang District
30.93334086
121.0623618
24
Huadong Hospital of Fudan University
31.22139226
121.4372887
25
Xinbang Community Health Service Center of Songjiang District
31.06454997
121.3122161
26
Shanghai Chest Hospital
31.19987994
121.420508
27
Jiuting Community Health Service Center of Songjiang District
31.11773795
121.3223082
28
Shanghai No. 5 People Hospital
31.00815517
121.4038781
29
Central Hospital of Changning District
31.21092818
121.3726881


## 5.1.1. Demand Points

The large number of EMS call locations makes it difficult to handle the ambulance station location optimization problem. In order to simplify the complexity of the ambulance location problem, most previous studies considered the center point of the administrative regions as the demand points [6]. But for some cities, the boundary of administrative regions is irregular, and thus it is hard to find the central points. And even worse, for some small countries, the administrative regions’ boundary is fuzzy. Based on the above consideration, we organize the county into 2-kilometer ∗ 2-kilometer square nodes with Arcgis 10.2 software. This gives us a total of 187 demand nodes and we assumed that the ambulances can be posted in any one of the nodes except in the nodes that make up the boundary. This can be seen in Figure 2 which displays all the demand points. Each demand point has patients of one or both of badly injured type and generally injured type. The EMS call center of the city receives more than 25,000 calls in the year of 2013, but just about 20,000 calls require ambulance vehicles. The spatial distribution of the whole year in 2013 can be seen in Figure 3. And the number of two types of patients in each demand point is seen in Figure 4.Figure 2
Location of 187 demand points.Figure 3
Locations of 8 current ambulance stations and 19447 EMS call origination points in Songjiang; EMS calls are marked as small red dots, and the 8 stations currently used are marked with a black cross. EMS calls from January 1 to December 31, 2013.Figure 4
Demand per demand point, where each colored line represents the injury of the patients.


## 5.1.2. Demand Scenarios

To reflect the realistic demands, EMS calls would be further classified based on their time and date. Days are classified into workdays (Monday through Friday) and off-days (weekends and holidays) and the call times are arranged into four periods of a single day: (i) dawn (00:00 AM–6:00 AM), (ii) morning (6:00 AM–12:00 PM), (iii) afternoon (12:00 PM–18:00 PM), and (iv) evening (18:00 PM–24:00 PM). The number of emergency calls of the patients in each of these 8 scenarios is shown in Table1.Table 1
Distribution of calls from January 1 to December 31, 2013.
Scenario
Day time
Day type
Badly injured
General injury
Demand count
Proportion
1
Dawn
Workdays
192
1560
1752
9.0%
2
Morning
Workdays
469
3734
4203
21.6%
3
Afternoon
Workdays
411
3463
3874
19.9%
4
Evening
Workdays
395
3243
3638
18.7%
5
Dawn
Off-days
79
815
894
4.6%
6
Morning
Off-days
189
1446
1752
8.4%
7
Afternoon
Off-days
240
1522
1762
9.1%
8
Evening
Off-days
164
1525
1689
8.7%
Total
2139
17308
19447
100%


## 5.1.3. Potential Ambulance Station Locations and the Hospital Locations

We selected a total of 17 potential ambulance location sites in the city of Songjiang including the hospitals and community health service centers. The current 8 ambulance stations are also in our potential location sites and we add the remaining potential stations in each administrative region mentioned in the previous context. All the potential ambulance stations’ information in detail can be seen in Figure2 and Table 2. From the detailed emergency call records, we find that there are more than 50 hospitals that are the potential destination hospitals. But some hospitals received the amount of patients in single digit in the whole year. Finally, we select 29 hospitals as the destination hospitals, each of which has received more than ten patients according to the emergency call records. Table 3 shows the detailed coordinates data for these hospitals. All the geographic coordinates of these potential stations and hospitals are obtained from the Baidu API with JAVA program; then we convert them into WGS-84 coordinates through Arcgis 10.2 software.Table 2
The detailed information of the potential ambulance stations.
Station ID
Ambulance count
Region
Property
WGS-84 coordinates
1
2
Che Dun
Current
31.01609698
121.2995794
2
2
Ye Xie
Current
30.94145835
121.3132912
3
2
Se San
Current
31.09752613
121.1760262
4
3
Xin Bang
Current
30.93380957
121.0623737
5
3
Si Jing
Current
31.12191941
121.2501306
6
2
Jiu Ting
Current
31.13326665
121.3150484
7
6
Lao Chengqu
Current
31.00930546
121.2173128
8
9
Zhong Xin
Current
31.04150089
121.2209912
9
—
Xin Qiao
Adding
31.06454997
121.3122161
10
—
Shi Hudang
Adding
30.98881041
121.1155610
11
—
Mao Gang
Adding
30.93558684
121.2061368
12
—
Xiao Kunshan
Adding
31.03015255
121.1206874
13
—
Dong Jing
Adding
31.08462687
121.2778089
14
—
Fang Song
Adding
31.03461475
121.2029791
15
—
Yong Feng
Adding
31.01882373
121.1885977
16
—
Yue Yang
Adding
31.00817409
121.2264765
17
—
Zhong Shan
Adding
31.02874777
121.2418646Table 3
The detailed information of hospitals.
Hospital ID
Hospital name
WGS-84 coordinates
1
Central Hospital of Songjiang District
31.0093054
121.2173128
2
Shanghai General Hospital of Songjiang Branch
31.04150089
121.2209912
3
Central Hospital of Minhang District
31.11021934
121.3716066
4
Sijing Hospital of Songjiang District
31.12191941
121.2501306
5
Jiuting Hospital of Songjiang District
31.13326665
121.3150484
6
Children’s Hospital of Fudan University
31.14094419
121.3916987
7
Health Center for Women and Children of Songjiang District
31.02702047
121.2145908
8
Shanghai No. 6 People Hospital
31.18098825
121.4192638
9
Armed Police Corps Hospital of Shanghai
31.19437713
121.3845042
10
Fangta Hospital of Traditional Chinese Medicine of Songjiang District
31.00850645
121.2480138
11
85 Hospital of People’s Liberation Army
31.21162286
121.4277839
12
Ruijin Hospital Shanghai Jiaotong University School of Medicine
31.21244079
121.4618436
13
International Peace Maternity and Child Health Hospital
31.19873795
121.4336423
14
455 Hospital of Chinese People’s Liberation Army
31.20217576
121.4232472
15
Zhongshan Hospital of Fudan University
31.19963334
121.4502016
16
Ledu Hospital of Songjiang District
31.01587166
121.2268316
17
Huashan Hospital of Fudan University
31.21836632
121.4383563
18
Shanghai No. 8 People Hospital
31.16975424
121.4282042
19
Shanghai No. 9 People Hospital
31.20422312
121.4813137
20
Health Center for Women and Children of Minhang District
31.14230556
121.3887969
21
Health Center for Women and Children of Changning District
31.21485631
121.4099054
22
Longhua Hospital Shanghai University of Traditional Chinese Medicine
31.18947654
121.4454596
23
Xinbang Community Health Service Center of Songjiang District
30.93334086
121.0623618
24
Huadong Hospital of Fudan University
31.22139226
121.4372887
25
Xinbang Community Health Service Center of Songjiang District
31.06454997
121.3122161
26
Shanghai Chest Hospital
31.19987994
121.420508
27
Jiuting Community Health Service Center of Songjiang District
31.11773795
121.3223082
28
Shanghai No. 5 People Hospital
31.00815517
121.4038781
29
Central Hospital of Changning District
31.21092818
121.3726881


## 5.2. Results and Discussion

In our experiments, we suppose that each of the emergency calls must be covered in less than 12 minutes; that is to say, the secondary coverage is twelve minutes following the standards set from the 13th Five-Year Plan of Shanghai prehospital service of first aid by the Shanghai Municipal Commission of Health and Family Planning (SMCHF) in the year of 2016. At least60% of the calls must be covered in 8 minutes with the prespecified service reliability level of 90%, which means λ≥60% and γ=90%. The number of ambulances in the system is K=29, which is the exact number of ambulances operated in 2013. Furthermore, the maximum number of ambulances per station is 4.The shortest travel time from ambulance stations to demand points and from demand points to hospitals is calculated on the basis of Euclidean distance. The running average speed of an ambulance is 55 km/ph, which is consistent with the traffic condition for most of the Shanghai urban streets.Sincefi,r in the proposed model is determined by the ratio ρi and service reliability level γ using (5), it is imperative to compute ρi by using (1) prior to estimating fi,r. The service call frequency at each demand point uses data in the year of 2013 calls, and we get the day average call per demand point. The average service time for EMS vehicles is set to be 0.9 h, which is calculated through 19,447 EMS calls received in the year of 2013. With the above parameter values, the steps to compute ratio ρi for a demand point i are as follows [8]: (i) finding all the ambulance station sets which can service demand point i, that is, j∈Si,r; (ii) determining all demand points, including i, that are within the coverage of 5 minutes for each ambulance station in Si,r, then summing their competing demands fl, and ensuring no duplication; (iii) computing the ratio by (1). Finally, the smallest integer fi,r can be found by iterations (or binary search).The solutions reported in the next section have been carried out on Intel Core™ i7-6700K CPU @ 4.00 GHz with 32 GB of RAM. The standard solver Gurobi (version 7.0.1) has been used to solve the integer linear programming model, coded with C++. Since the size of the model is not too large, solution time for each integer program run is less than ten minutes.


### 5.2.1. Current Ambulance Station

We start from investigating the performance of the 8 stations and 29 ambulances currently utilized by the EMS system in Songjiang District. We attempted to solve our model by limiting potential bases to these 8 stations. The resulting optimization problem is infeasible, indicating that the current bases cannot satisfy the predefined EMS standards. This is the case even if the secondary coverage fractionλ is set to be 0, which indicates that the current bases cannot ensure the second coverage within r2=12 minutes. In fact, the smallest value of r2 for which we could obtain a feasible solution was 13 minutes. Even so, feasibility is attained only for a maximum value of λ = 0.3, which corresponds to 30% coverage within r1=8 minutes. The conclusion is that the current bases are far from achieving both primary and secondary coverage requirements. Those two cases are listed in Table 4.Table 4
Results of the ambulance location problem in current Songjiang EMS system.
Problem ID
Current station set
r
2 (min)
λ
Station numbers needed
Objective
1
8 stations
12
60%
Unfeasible
—
2
8 stations
13
30%
8
6011


### 5.2.2. Is There a Feasible Solution of 8 Ambulance Stations?

Having failed to meet the predetermined standards with the current 8 bases, we seek to determine whether any other set of 8 bases would satisfy those requirements. In order to handle this problem, we need to add an additional constraint on the maximum number of bases. To find out the reasons why the optimization based on current ambulance stations fails to meet the coverage standard, we used the same quantity of ambulance stations. After solving the above model, we found that it is possible to locate a different set of ambulances from all the potential ambulance stations which fulfill the full coverage withinr2=12 minutes, with the limitation. When we used the problem 2’s r2 standard r2=13 minutes, we can get the proportion with λ=0.46. Table 5 shows the trade-off between the proportion λ and the objective value. Figures 5 and 6 show the 8 optimal ambulance locations within all the demand points satisfying the service coverage in 13 minutes and 12 minutes, respectively.Table 5
Results of the ambulance location problem in Songjiang EMS system.
Problem ID
Potential station set
r
2 (min)
λ
Station numbers needed
Objective
3
Any 8 stations
13
46%
8
9091
4
Any 8 stations
12
42%
8
8290Figure 5
Optimal locations of any 8 ambulance stations inr2=13 minutes.Figure 6
Optimal locations of any 8 ambulance stations inr2=12 minutes.


### 5.2.3. Optimization for All Ambulance Stations

Finally, we solve the concerned problem allowing all 17 potential bases to be optimized. In this context, the problem is feasible with the probationλ≥0.6 and the service reliability γ=0.9. After optimizing, λ can reach 0.71. The optimal objective value is shown in Table 6. Figure 7 shows the detailed optimal locations of the ambulance stations.Table 6
Results of the ambulance location problem in Songjiang EMS system.
Problem ID
Potential station set
r
2 (min)
λ
Station numbers needed
Objective
5
All stations (17 stations)
12
71%
12
13881Figure 7
Optimal locations of ambulance stations among all the potential locations.


### 5.2.4. Comparisons with Classical Models

We compare the model proposed in this paper with the classic DSM. This is because the model proposed in this paper is derived from classical DSM. The proposed model formulation considers two-stage rescue. We want to find out the difference between the classic DSM and our proposed model. However, in our model, we consider service reliability, which aims to find the optimal deployments of EMS vehicles to achieve maximized coverage of demand points. Each covered demand point is serviced by at least one ambulance in90% of the time. In order to examine the effect considering two-stage rescue, our model is slightly modified by removing the reliability constraint. Results are shown in Figures 8 and 9. The proposed model can achieve a better objective value than the DSM, with the primary coverage r1=8 minutes. An interesting phenomenon is that when the number of stations exceeds eleven, our model can get full coverage. Besides, the coverage value obtained from the classic DSM cannot increase even if the number of stations exceeds nine. As for the range of primary coverage standard r1, our model can achieve full coverage in 8 minutes. However, the classic model gets full coverage with 12 minutes.Figure 8
Comparisons of double coverage within the same primary standardr1=8 minutes (without considering service reliability).Figure 9
Comparisons of double coverage count in different primary standardr1 within the same ambulance stations (without considering service reliability).


## 5.2.1. Current Ambulance Station

We start from investigating the performance of the 8 stations and 29 ambulances currently utilized by the EMS system in Songjiang District. We attempted to solve our model by limiting potential bases to these 8 stations. The resulting optimization problem is infeasible, indicating that the current bases cannot satisfy the predefined EMS standards. This is the case even if the secondary coverage fractionλ is set to be 0, which indicates that the current bases cannot ensure the second coverage within r2=12 minutes. In fact, the smallest value of r2 for which we could obtain a feasible solution was 13 minutes. Even so, feasibility is attained only for a maximum value of λ = 0.3, which corresponds to 30% coverage within r1=8 minutes. The conclusion is that the current bases are far from achieving both primary and secondary coverage requirements. Those two cases are listed in Table 4.Table 4
Results of the ambulance location problem in current Songjiang EMS system.
Problem ID
Current station set
r
2 (min)
λ
Station numbers needed
Objective
1
8 stations
12
60%
Unfeasible
—
2
8 stations
13
30%
8
6011


## 5.2.2. Is There a Feasible Solution of 8 Ambulance Stations?

Having failed to meet the predetermined standards with the current 8 bases, we seek to determine whether any other set of 8 bases would satisfy those requirements. In order to handle this problem, we need to add an additional constraint on the maximum number of bases. To find out the reasons why the optimization based on current ambulance stations fails to meet the coverage standard, we used the same quantity of ambulance stations. After solving the above model, we found that it is possible to locate a different set of ambulances from all the potential ambulance stations which fulfill the full coverage withinr2=12 minutes, with the limitation. When we used the problem 2’s r2 standard r2=13 minutes, we can get the proportion with λ=0.46. Table 5 shows the trade-off between the proportion λ and the objective value. Figures 5 and 6 show the 8 optimal ambulance locations within all the demand points satisfying the service coverage in 13 minutes and 12 minutes, respectively.Table 5
Results of the ambulance location problem in Songjiang EMS system.
Problem ID
Potential station set
r
2 (min)
λ
Station numbers needed
Objective
3
Any 8 stations
13
46%
8
9091
4
Any 8 stations
12
42%
8
8290Figure 5
Optimal locations of any 8 ambulance stations inr2=13 minutes.Figure 6
Optimal locations of any 8 ambulance stations inr2=12 minutes.


## 5.2.3. Optimization for All Ambulance Stations

Finally, we solve the concerned problem allowing all 17 potential bases to be optimized. In this context, the problem is feasible with the probationλ≥0.6 and the service reliability γ=0.9. After optimizing, λ can reach 0.71. The optimal objective value is shown in Table 6. Figure 7 shows the detailed optimal locations of the ambulance stations.Table 6
Results of the ambulance location problem in Songjiang EMS system.
Problem ID
Potential station set
r
2 (min)
λ
Station numbers needed
Objective
5
All stations (17 stations)
12
71%
12
13881Figure 7
Optimal locations of ambulance stations among all the potential locations.


## 5.2.4. Comparisons with Classical Models

We compare the model proposed in this paper with the classic DSM. This is because the model proposed in this paper is derived from classical DSM. The proposed model formulation considers two-stage rescue. We want to find out the difference between the classic DSM and our proposed model. However, in our model, we consider service reliability, which aims to find the optimal deployments of EMS vehicles to achieve maximized coverage of demand points. Each covered demand point is serviced by at least one ambulance in90% of the time. In order to examine the effect considering two-stage rescue, our model is slightly modified by removing the reliability constraint. Results are shown in Figures 8 and 9. The proposed model can achieve a better objective value than the DSM, with the primary coverage r1=8 minutes. An interesting phenomenon is that when the number of stations exceeds eleven, our model can get full coverage. Besides, the coverage value obtained from the classic DSM cannot increase even if the number of stations exceeds nine. As for the range of primary coverage standard r1, our model can achieve full coverage in 8 minutes. However, the classic model gets full coverage with 12 minutes.Figure 8
Comparisons of double coverage within the same primary standardr1=8 minutes (without considering service reliability).Figure 9
Comparisons of double coverage count in different primary standardr1 within the same ambulance stations (without considering service reliability).


## 6. Conclusion

This paper considers the optimization of the ambulance station location and ambulance allocation with the existing hospital locations to meet the patients’ injury types. After studying and analyzing the optimized ambulances locations for the Emergency Medical Services (EMS) in Songjiang, Shanghai, China, we concluded the ambulance base locations and the destination hospital locations affect the EMS performance significantly. Our proposed model can achieve remarkable results of coverage compared to the classic DSM in terms of used ambulance stations and the primary coverage standardr1. However, our results are based upon the real demands in only one-year data and our model is a deterministic model. It may be helpful in the strategic level but it lacks certain flexibility in the operational level. Also, we do not consider the cost of the ambulance station set up and the ambulance vehicle utilization.Future research direction may include (i) the development of efficient algorithms for the large scale demand points and the potential ambulance station locations; (ii) the consideration of the EMS problem in a stochastic setting, such as considering stochastic emergency calls arrival and ambulance uncertainty.



---

*Source: 1830480-2017-08-30.xml*