# Distribution-Free Model for Ambulance Location Problem with Ambiguous Demand

Authors: Feng Chu; Lu Wang; Xin Liu; Chengbin Chu; Yang Sui
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

Ambulance location problem is a key issue in Emergency Medical Service (EMS) system, which is to determine where to locate ambulances such that the emergency calls can be responded efficiently. Most related researches focus on deterministic problems or assume that the probability distribution of demand can be estimated. In practice, however, it is difficult to obtain perfect information on probability distribution. This paper investigates the ambulance location problem with partial demand information; i.e., only the mean and covariance matrix of the demands are known. The problem consists of determining base locations and the employment of ambulances, to minimize the total cost. A new distribution-free chance constrained model is proposed. Then two approximated mixed integer programming (MIP) formulations are developed to solve it. Finally, numerical experiments on benchmarks (Nickel et al., 2016) and 120 randomly generated instances are conducted, and computational results show that our proposed two formulations can ensure a high service level in a short time. Specifically, the second formulation takes less cost while guaranteeing an appropriate service level.


---

## Body

## 1. Introduction

The design of Emergency Medical Service (EMS) systems that affects people’s health and life focuses on how to respond to emergencies rapidly. Ambulance location problem is one of the key problems in EMS system, which mainly consists of determining where to locate bases, also named as emergency service facilities, and the employment of ambulances in order to serve emergencies efficiently and to guarantee patient survivability. There have been various researches investigating ambulance location problem (e.g., [1, 2]) since it is introduced by Toregas et al. (1974).Early studies addressing ambulance location problem mainly focus on deterministic environments, including set covering ambulance location problem that minimizes the number of ambulances to cover all demand points [3], maximal covering location problem to maximize the number of covered demand points with given number of ambulances [4], and double standard model (DSM) in which each demand point must be covered by one or more ambulances [5]. However, in practice, stochastic ambulance location problem is more realistic due to the inevitable uncertainties of emergency events (e.g., [6, 7], etc.). Usually, an emergency event has the following characteristics: (i) it is difficult to forecast precisely where an emergency will occur, and (ii) the required number of ambulances depends on the severity of the situation, which is also unforeseen [8].Most existing works investigate stochastic ambulance location problem by assuming that the demand probability distribution at each possible emergency is known (e.g., [9, 10], Beraldi and Bruni, 2008; etc.). However, as stated by Wagner [11] and Delage and Ye [12], it is usually impossible to obtain the perfect information on probability distribution, due to (i) the lack of historical data and the fact that (ii) the given historical data may not be represented by probability distribution.Moreover, how to cover as many emergencies as possible to guarantee a high patient service level (i.e., the portion of the satisfied emergency points among all emergency points) has always been a main goal of EMS operators. Motivated by the above observation, this work focuses on a stochastic ambulance location problem with only partial information of demand points, i.e., the mean and covariance matrix of the demands. Besides, we introduce a new individual chance constraint, which implies a minimum probability that each emergency demand has to be satisfied. For the problem, a new distribution-free model is presented, and then two approximated formulations are proposed. The contribution of this work mainly includes the following:(1)
For the studied stochastic ambulance location problem, we introduce a new individual chance constraint (i.e., safety level) guaranteeing each emergency demand satisfied with a least probability, while Nickel et al. [8] use a coverage constraint, where some service of individual emergencies may suffer insufficiency.(2)
A new distribution-free model based on individual chance constraints is proposed. To our best knowledge, it is the first distribution-free model for stochastic ambulance location problem.(3)
To solve the distribution-free model, two approximated mixed integer programming (MIP) formulations are developed. Experimental results show that our approximated formulations are efficient and effective for large size instances, compared to that proposed by Nickel et al. [8] in terms of both computational time and service level.The remainder of this paper is organized as follows. Section2 gives a brief literature review. In Section 3, we give the problem description and propose a new distribution-free model. In Section 4, two approximated MIP formulations are proposed. Computational results on benchmarks and 120 randomly generated instances are reported in Section 5. Section 6 summarizes this work and states future research directions.


## 2. Literature Review

The deterministic ambulance location problem has been well studied in literature (e.g., [2, 5, 13], etc.). Besides, there have been some works addressing ambulance location problem under uncertainty (e.g., [1, 6, 14], etc.). Since our study falls within the scope of stochastic ambulance location problem, in the following subsections, we first review existing studies on ambulance location problem with uncertain demand. Then we review the literature studying general and specific stochastic optimization problems with distribution-free approaches.


### 2.1. Ambulance Location Problem with Uncertain Demand

Ambulance location problem under uncertain demand has been investigated by many researchers. Most existing works address the uncertainty with given scenarios or known probability distribution.Chapman and White [15] first investigate the ambulance location problem with uncertain demand, in which the complete information on probability distributions is assumed to be known. Beraldi et al. [9] study the emergency medical service location problem with uncertain demand to minimize the total cost with a marginal probability distribution. Beraldi and Bruni (2008) investigate the emergency medical service facilities location problem with stochastic demand based on given set of scenarios and known probability distribution. A stochastic programming formulation with probabilistic constraints is proposed. Noyan [10] studies the ambulance location problem with uncertain demand on given scenarios and probability distribution. Then, two stochastic optimization models and a heuristic are proposed.Recently, Nickel et al. [8] first study the joint optimization of ambulance base location and ambulance employment. The objective is to minimize the total constructing base costs and ambulance employment costs. It is assumed that various scenarios are given beforehand. A coverage constraint is introduced in the paper. They propose a sampling approach that solves a finite number of scenario samples to obtain a feasible solution of the original problem. But with the coverage constraint, some emergency demands risk insufficient individual service or cannot be served. For the study, we propose a new distribution-free model for stochastic ambulance location problem.


### 2.2. Distribution-Free Approaches

In data-driven settings, the probability distributions of uncertain parameters may not always be perfectly estimated [16]. Therefore in the last decade, there have been many solution approaches developed to address stochastic problems under partial distributional knowledge. Most related researches focus on the distribution-free approach via considering chance constraints. Wagner [11] studies a stochastic 0-1 linear programming under partial distribution information, i.e., minX∈{0,1}n{c′x:aj′x≤bj,j=1,…,m}, where aj are random vectors with unknown distributions. The only information on aj are their moments, up to order k. A robust formulation, as a function of k, is given. Given the known second-order moment knowledge, i.e., k=2, an approximated formulation is developed as minX∈{0,1}n{c′x:x′Γjx≤pj/1-pj(bj=Eaj′x),j=1,…,m}, where Γikj=Eaij-Eaijakj-Eakj,∀i,k=1,…,n. Delage and Ye [12] investigate the stochastic program with limited distribution information, and they propose a new moment-based ambiguity set, which is assumed to include the true probability distribution, to describe the uncertainties. There have been various works successfully applying the distribution-free approaches. Ng [17] investigates a stochastic vessel deployment problem for liner shipping, in which only the mean, standard deviation, and an upper bound of demand are known. A distribution-free optimization formulation is proposed. Based on that, Ng [18] studies a stochastic vessel deployment problem for the liner shipping industry, where only the mean and variance of the uncertain demands are known. New models are proposed, and the provided bounds are shown to be sharp under uncertain environment. The stochastic dependencies between the shipping demands are considered.Jiang and Guan [19] develop approaches to solve stochastic programs with data-driven chance constraints. Two types of confidence sets for the possible probability distributions are proposed. For more distribution-free formulation applications, please see Lee and Hsu [20], Kwon and Cheong [21], etc., for the stochastic inventory problem, and Zhang et al. [23] for stochastic allocating surgeries problem in operating rooms, and Zheng et al. [24] for stochastic disassembly line balancing problem. To the best of our knowledge, there is no research for the stochastic ambulance location problem with only partial information on the uncertain demand.


## 2.1. Ambulance Location Problem with Uncertain Demand

Ambulance location problem under uncertain demand has been investigated by many researchers. Most existing works address the uncertainty with given scenarios or known probability distribution.Chapman and White [15] first investigate the ambulance location problem with uncertain demand, in which the complete information on probability distributions is assumed to be known. Beraldi et al. [9] study the emergency medical service location problem with uncertain demand to minimize the total cost with a marginal probability distribution. Beraldi and Bruni (2008) investigate the emergency medical service facilities location problem with stochastic demand based on given set of scenarios and known probability distribution. A stochastic programming formulation with probabilistic constraints is proposed. Noyan [10] studies the ambulance location problem with uncertain demand on given scenarios and probability distribution. Then, two stochastic optimization models and a heuristic are proposed.Recently, Nickel et al. [8] first study the joint optimization of ambulance base location and ambulance employment. The objective is to minimize the total constructing base costs and ambulance employment costs. It is assumed that various scenarios are given beforehand. A coverage constraint is introduced in the paper. They propose a sampling approach that solves a finite number of scenario samples to obtain a feasible solution of the original problem. But with the coverage constraint, some emergency demands risk insufficient individual service or cannot be served. For the study, we propose a new distribution-free model for stochastic ambulance location problem.


## 2.2. Distribution-Free Approaches

In data-driven settings, the probability distributions of uncertain parameters may not always be perfectly estimated [16]. Therefore in the last decade, there have been many solution approaches developed to address stochastic problems under partial distributional knowledge. Most related researches focus on the distribution-free approach via considering chance constraints. Wagner [11] studies a stochastic 0-1 linear programming under partial distribution information, i.e., minX∈{0,1}n{c′x:aj′x≤bj,j=1,…,m}, where aj are random vectors with unknown distributions. The only information on aj are their moments, up to order k. A robust formulation, as a function of k, is given. Given the known second-order moment knowledge, i.e., k=2, an approximated formulation is developed as minX∈{0,1}n{c′x:x′Γjx≤pj/1-pj(bj=Eaj′x),j=1,…,m}, where Γikj=Eaij-Eaijakj-Eakj,∀i,k=1,…,n. Delage and Ye [12] investigate the stochastic program with limited distribution information, and they propose a new moment-based ambiguity set, which is assumed to include the true probability distribution, to describe the uncertainties. There have been various works successfully applying the distribution-free approaches. Ng [17] investigates a stochastic vessel deployment problem for liner shipping, in which only the mean, standard deviation, and an upper bound of demand are known. A distribution-free optimization formulation is proposed. Based on that, Ng [18] studies a stochastic vessel deployment problem for the liner shipping industry, where only the mean and variance of the uncertain demands are known. New models are proposed, and the provided bounds are shown to be sharp under uncertain environment. The stochastic dependencies between the shipping demands are considered.Jiang and Guan [19] develop approaches to solve stochastic programs with data-driven chance constraints. Two types of confidence sets for the possible probability distributions are proposed. For more distribution-free formulation applications, please see Lee and Hsu [20], Kwon and Cheong [21], etc., for the stochastic inventory problem, and Zhang et al. [23] for stochastic allocating surgeries problem in operating rooms, and Zheng et al. [24] for stochastic disassembly line balancing problem. To the best of our knowledge, there is no research for the stochastic ambulance location problem with only partial information on the uncertain demand.


## 3. Problem Description and Formulation

In this section, we first describe the considered problem and then propose a new distribution-free model.


### 3.1. Problem Description

There is a given set of candidate base locationsI={1,2,…,I} and a set of potential emergency demand points J={1,2,…,J}. The emergency points may refer to a road, a part of the urban area and a village. Base i∈I is said to be covering an emergency point j if the driving time tij between i and j is no more than a predetermined value T. The set Ij of candidate bases covering emergency point j is denoted as Ij={i∈I∣tij≤T}.The number of ambulances required by an emergency pointj∈J is denoted as dj, which depends on the severity of the practical situation. We consider uncertain emergencies which are estimated or predicted by partial distributional information; thus the demand is regarded to be ambiguous. Besides, we focus on the case where the historical data cannot be represented by a precise probability distribution. It is assumed that the customer demands are independent of each other.The objective of the problem is to select a subset of base locations and determine the number of ambulances at each constructed base in order to minimize the total base construction cost and ambulance cost. Throughout this paper we assume that only the mean and covariance matrix of demands are known. Moreover, a predefinedsafety levelαj is given for each potential emergency point j∈J. That is, the number of ambulances serving each emergency point j∈J is larger than or equal to its demand with a least probability of αj.


### 3.2. Chance Constraint Construction

In this section, we introduce a chance constraint to guarantee the safety level of each emergency demand point. In the following,yij is a decision variable denoting the number of ambulances serving point j∈J from base i∈Ij and dj is the uncertain demand at point j∈J. The chance constrained inequality is presented as follows: (1)ProbP∑i∈Ijyij≥dj≥αj,∀j∈Jwhere ProbP(·) denotes the probability of the event in parentheses under any potential probability distribution P. Constraint (1) ensures that the number of ambulances serving emergency point j∈J is no less than its demand with a least probability of αj (i.e., safety level).


### 3.3. Distribution-Free Formulation

In the following, we give basic notations, define decision variables and propose the distribution-free formulationDF for the ambulance location problem with uncertain demand.Parameters i: index of base locations j: index of emergency points I: set of candidate base locations J: set of possible emergency demand points t i j: driving time between base i∈I and demand point j∈J T: maximum driving time for serving any emergency call I j: set of candidate bases that can cover emergency point j∈J, i.e., Ij={i∈I∣tij≤T} J i: set of potential emergency points covered by base i∈I, i.e., Ji={j∈J∣tij≤T} f i: fixed construction cost for installing a base at location i∈I g i: fixed cost associated with an ambulance to be located at i∈I d j: number of (stochastic) ambulances requested by emergency point j∈J M: a sufficiently large positive numberDecision Variables x i: a binary variable equal to 1 if a base is constructed at i∈I; 0 otherwise z i: number of ambulances assigned to possible base location i∈I y i j: number of ambulances serving emergency point j∈J from possible base location i∈IjDistribution-Free Model [DF] [DF]: (2) m i n  ∑ i ∈ I f i · x i + g i · z i s . t .  C o n s t r a i n t 1 (3) z i ≤ M · x i ,  ∀ i ∈ I (4) ∑ j ∈ J i y i j ≤ z i ,  ∀ i ∈ I (5) x i ∈ 0,1 ,  ∀ i ∈ I (6) z i ∈ Z + ,  ∀ i ∈ I (7) y i j ∈ Z + ,  ∀ i ∈ I ,   j ∈ J iThe objective function denotes the goal to minimize the total cost consisting of two parts: (i) the cost for constructing bases, i.e.,∑i∈I‍fi·xi, and (ii) the cost for deploying ambulances, i.e., ∑i∈I‍gi·zi.Constraint (3) ensures that ambulances can only be located at the opened bases. Constraint (4) ensures that the number of ambulances sent to serve emergency points from base i∈I does not exceed the total number of ambulances located at i∈I. Constraints (5)-(7) are the restrictions on decision variables.


## 3.1. Problem Description

There is a given set of candidate base locationsI={1,2,…,I} and a set of potential emergency demand points J={1,2,…,J}. The emergency points may refer to a road, a part of the urban area and a village. Base i∈I is said to be covering an emergency point j if the driving time tij between i and j is no more than a predetermined value T. The set Ij of candidate bases covering emergency point j is denoted as Ij={i∈I∣tij≤T}.The number of ambulances required by an emergency pointj∈J is denoted as dj, which depends on the severity of the practical situation. We consider uncertain emergencies which are estimated or predicted by partial distributional information; thus the demand is regarded to be ambiguous. Besides, we focus on the case where the historical data cannot be represented by a precise probability distribution. It is assumed that the customer demands are independent of each other.The objective of the problem is to select a subset of base locations and determine the number of ambulances at each constructed base in order to minimize the total base construction cost and ambulance cost. Throughout this paper we assume that only the mean and covariance matrix of demands are known. Moreover, a predefinedsafety levelαj is given for each potential emergency point j∈J. That is, the number of ambulances serving each emergency point j∈J is larger than or equal to its demand with a least probability of αj.


## 3.2. Chance Constraint Construction

In this section, we introduce a chance constraint to guarantee the safety level of each emergency demand point. In the following,yij is a decision variable denoting the number of ambulances serving point j∈J from base i∈Ij and dj is the uncertain demand at point j∈J. The chance constrained inequality is presented as follows: (1)ProbP∑i∈Ijyij≥dj≥αj,∀j∈Jwhere ProbP(·) denotes the probability of the event in parentheses under any potential probability distribution P. Constraint (1) ensures that the number of ambulances serving emergency point j∈J is no less than its demand with a least probability of αj (i.e., safety level).


## 3.3. Distribution-Free Formulation

In the following, we give basic notations, define decision variables and propose the distribution-free formulationDF for the ambulance location problem with uncertain demand.Parameters i: index of base locations j: index of emergency points I: set of candidate base locations J: set of possible emergency demand points t i j: driving time between base i∈I and demand point j∈J T: maximum driving time for serving any emergency call I j: set of candidate bases that can cover emergency point j∈J, i.e., Ij={i∈I∣tij≤T} J i: set of potential emergency points covered by base i∈I, i.e., Ji={j∈J∣tij≤T} f i: fixed construction cost for installing a base at location i∈I g i: fixed cost associated with an ambulance to be located at i∈I d j: number of (stochastic) ambulances requested by emergency point j∈J M: a sufficiently large positive numberDecision Variables x i: a binary variable equal to 1 if a base is constructed at i∈I; 0 otherwise z i: number of ambulances assigned to possible base location i∈I y i j: number of ambulances serving emergency point j∈J from possible base location i∈IjDistribution-Free Model [DF] [DF]: (2) m i n  ∑ i ∈ I f i · x i + g i · z i s . t .  C o n s t r a i n t 1 (3) z i ≤ M · x i ,  ∀ i ∈ I (4) ∑ j ∈ J i y i j ≤ z i ,  ∀ i ∈ I (5) x i ∈ 0,1 ,  ∀ i ∈ I (6) z i ∈ Z + ,  ∀ i ∈ I (7) y i j ∈ Z + ,  ∀ i ∈ I ,   j ∈ J iThe objective function denotes the goal to minimize the total cost consisting of two parts: (i) the cost for constructing bases, i.e.,∑i∈I‍fi·xi, and (ii) the cost for deploying ambulances, i.e., ∑i∈I‍gi·zi.Constraint (3) ensures that ambulances can only be located at the opened bases. Constraint (4) ensures that the number of ambulances sent to serve emergency points from base i∈I does not exceed the total number of ambulances located at i∈I. Constraints (5)-(7) are the restrictions on decision variables.


## 4. Solution Approaches

The proposed distribution-free model is difficult to solve with the commercial software due to chance constraints. In this section, we propose two approximated MIP formulations based on those in Wagner [11] and in Delage and Ye [12], respectively. In the following subsections, we present the two approximated MIP formulations.


### 4.1. Approximated MIP Formulation:MIP-DF1

In this part, we first describe a widely used ambiguity set to describe the uncertainty. Then an approximated MIP formulationMIP-DF1 is proposed.Given a set of independent historical data samples{ds}s=1S of random vectors of demands, where S is the set of sample indexes, the mean vector μ and the covariance matrix Σ of demands can be estimated as follows:(8)μ=1S∑s∈Sds,Σ=1S∑s∈Sds-μds-μ⊤.where (·)⊤ implies the transposition of the vector in parentheses. Then, an ambiguity set of all probability distributions of demands P1(μ,Σ) can be described as the following: (9)P1μ,Σ=P:EPd=μ,EPd-μd-μ⊤=Σ,where P denotes a possible probability distribution satisfying the given conditions, and EP[·] denotes the expected value of the number in parentheses. Then the chance constraint (1) with the ambiguity set P1 can be presented as follows:(10)ProbP∑i∈Ijyij≥dj≥αj,∀j∈J,P∈P1.According to Wagner (2010) and Ng [18], constraint (1) can be conservatively approximated by the following: (11)∑i∈Ijyij≥μj+σj·αj1-αj,∀j∈Jwhere σj=Σjj, and Σjj denotes the j-th element in the j-th column of matrix Σ. In terms of conservative approximation, all solutions satisfying constraint (11) must satisfy constraint (1). Then we describe the approximated MIP formulationMIP-DF1 toDF combined with constraint (11):[MIP-DF1]:(12)min∑i∈Ifi·xi+gi·zis.t.Constraints4-8,12.MIP-DF1 can be exactly solved by the commercial software, such as CPLEX. As we can observe from the computational results in Section 5, it can obtain a relatively high service level. However, the system cost is also high. In order to save the system cost, another approximated MIP formulation ofDF is then proposed in the next subsection.


### 4.2. Approximated MIP Formulation:MIP-DF2

Ambiguity setP1 focuses on exactly matching the mean and covariance matrix of uncertain parameters. However, in practice, there may be considerable estimation errors in the mean and covariance matrix. To take the inevitable estimation errors into consideration, Delage and Ye [12] introduce a new moment-based ambiguity set. Therefore, we in the following employ the moment-based ambiguity set:(13)P2μ,Σ,γ1,γ2=P:EPd-μ⊤Σ-1EPd-μ≤γ1,EPd-μd-μ⊤⪯γ2Σ,where γ1≥0 and γ2≥0 are two parameters of ambiguity set P2(μ,Σ,γ1,γ2) with the following assumptions: (i) the true mean vector of demands is within an ellipsoid of size proportion to γ1 centered at μ, and (ii) the true covariance matrix of demands is in a positive semidefinite cone bounded by a matrix inequality of γ2Σ. The ambiguity set describes how likely the uncertain parameters are to be close to the mean in terms of the correlation [12]. Besides, under the moment-based ambiguity set, various stochastic programs with partial distributional information have been successfully modeled and solved [22, 23, 25].According to the approximation method in Zhang et al. [23], chance constraint (1) can be approximated by(14)11-a-b·1+1-αjαj·b·σj≤1-αjαj·∑i∈Ijyij-μj,j∈Jwhere(15)a=1-γ1+1γ2-γ1,b=γ1γ2-γ1.The second approximated MIP formulationMIP-DF2 toDF is presented as follows:[MIP-DF2]:(16)min∑i∈Ifi·xi+gi·zis.t.Constraints4-8,15.Notice that whenγ1=0 and γ2=1, inequality (14) reduces to (11) inMIP-DF1, which implies thatMIP-DF1 is a special case ofMIP-DF2.


## 4.1. Approximated MIP Formulation:MIP-DF1

In this part, we first describe a widely used ambiguity set to describe the uncertainty. Then an approximated MIP formulationMIP-DF1 is proposed.Given a set of independent historical data samples{ds}s=1S of random vectors of demands, where S is the set of sample indexes, the mean vector μ and the covariance matrix Σ of demands can be estimated as follows:(8)μ=1S∑s∈Sds,Σ=1S∑s∈Sds-μds-μ⊤.where (·)⊤ implies the transposition of the vector in parentheses. Then, an ambiguity set of all probability distributions of demands P1(μ,Σ) can be described as the following: (9)P1μ,Σ=P:EPd=μ,EPd-μd-μ⊤=Σ,where P denotes a possible probability distribution satisfying the given conditions, and EP[·] denotes the expected value of the number in parentheses. Then the chance constraint (1) with the ambiguity set P1 can be presented as follows:(10)ProbP∑i∈Ijyij≥dj≥αj,∀j∈J,P∈P1.According to Wagner (2010) and Ng [18], constraint (1) can be conservatively approximated by the following: (11)∑i∈Ijyij≥μj+σj·αj1-αj,∀j∈Jwhere σj=Σjj, and Σjj denotes the j-th element in the j-th column of matrix Σ. In terms of conservative approximation, all solutions satisfying constraint (11) must satisfy constraint (1). Then we describe the approximated MIP formulationMIP-DF1 toDF combined with constraint (11):[MIP-DF1]:(12)min∑i∈Ifi·xi+gi·zis.t.Constraints4-8,12.MIP-DF1 can be exactly solved by the commercial software, such as CPLEX. As we can observe from the computational results in Section 5, it can obtain a relatively high service level. However, the system cost is also high. In order to save the system cost, another approximated MIP formulation ofDF is then proposed in the next subsection.


## 4.2. Approximated MIP Formulation:MIP-DF2

Ambiguity setP1 focuses on exactly matching the mean and covariance matrix of uncertain parameters. However, in practice, there may be considerable estimation errors in the mean and covariance matrix. To take the inevitable estimation errors into consideration, Delage and Ye [12] introduce a new moment-based ambiguity set. Therefore, we in the following employ the moment-based ambiguity set:(13)P2μ,Σ,γ1,γ2=P:EPd-μ⊤Σ-1EPd-μ≤γ1,EPd-μd-μ⊤⪯γ2Σ,where γ1≥0 and γ2≥0 are two parameters of ambiguity set P2(μ,Σ,γ1,γ2) with the following assumptions: (i) the true mean vector of demands is within an ellipsoid of size proportion to γ1 centered at μ, and (ii) the true covariance matrix of demands is in a positive semidefinite cone bounded by a matrix inequality of γ2Σ. The ambiguity set describes how likely the uncertain parameters are to be close to the mean in terms of the correlation [12]. Besides, under the moment-based ambiguity set, various stochastic programs with partial distributional information have been successfully modeled and solved [22, 23, 25].According to the approximation method in Zhang et al. [23], chance constraint (1) can be approximated by(14)11-a-b·1+1-αjαj·b·σj≤1-αjαj·∑i∈Ijyij-μj,j∈Jwhere(15)a=1-γ1+1γ2-γ1,b=γ1γ2-γ1.The second approximated MIP formulationMIP-DF2 toDF is presented as follows:[MIP-DF2]:(16)min∑i∈Ifi·xi+gi·zis.t.Constraints4-8,15.Notice that whenγ1=0 and γ2=1, inequality (14) reduces to (11) inMIP-DF1, which implies thatMIP-DF1 is a special case ofMIP-DF2.


## 5. Computational Experiments

In this section, the performance of our proposed formulations first evaluated and compared to the sampling approach proposed in Nickel et al. [8]. Specifically, given a required service level α, we apply our MIP formulations by restricting the chance constraint for each emergency point to satisfy a safety level αj=α, while we adopt the sampling approach by restricting the coverage constraint with α. Then computational results on 120 randomly generated instances based on the information on emergencies in Shanghai are reported. Our approximated MIP formulations and the sampling approach are solved by coding in MATLAB_2014b calling CPLEX 12.6 solver. All numerical experiments are conducted on a personal computer with Core I5 and 3.30GHz processor and 8GB RAM under windows 7 operating system. The computational time for sampling approach is limited to 3600 seconds.


### 5.1. Out-of-Sample Test

Following Zhang et al.’s [22] methodology, we examine the out-of-sample performance of solutions obtained by our proposed approximated MIP formulations and the sampling approach [8]. The out-of-sample test includes three steps:(1)
The base locations and the employment of ambulances at each base are determined with known mean vector and covariance matrix of demands, which is named as in-sample test.(2)
1000 scenarios are sampled from the underlying true distribution, which represent realizing the uncertain demand.(3)
Based on the solution obtained in step(1), ambulances are assigned to serve emergency points in the 1000 scenarios to maximize the (out-of-sample) service level.The (out-of-sample) service level is defined as the ratio of the number of emergency points with demand satisfied to the total number of emergency points in 1000 scenarios. In the following subsections, the benchmarks are tested and then three common distributions are employed, i.e., uniform distribution, Poisson distribution, and normal distribution, respectively.


### 5.2. Benchmark Instances

We first test the benchmarks in Nickel et al. [8] to compare our proposed two approximated MIP formulations with the sampling approach. In Nickel et al. [8], they assume that demand nodes are also potential base locations, and the number of ambulances required by each emergency point is chosen from set {0,1,2} with given probability distribution. Computational results on benchmarks are reported in Tables 1 and 2.Table 1
α = 0.95.
| I | = J Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) 1 7 4.9 23 96.26 0.1 36 100.00 0.1 23 100.00 2 7 5.1 22 98.63 0.1 35 100.00 0.1 24 99.82 3 6 4.1 14 96.92 0.1 30 100.00 0.1 14 98.50 4 6 4.3 13 97.13 0.2 29 100.00 0.1 12 97.42 5 6 5.7 12 79.96 0.1 30 100.00 0.2 12 100.00 6 8 5.8 21 98.50 0.1 24 100.00 0.2 27 100.00  Average 5.0 17.5 94.57 0.1 30.7 100.00 0.1 18.7 99.29Table 2
α = 0.99.
| I | = | J | Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) 1 7 4.9 24 99.79 0.1 64 100.00 0.1 25 100.00 2 7 4.8 23 98.56 0.1 63 100.00 0.1 24 100.00 3 6 5.1 15 97.17 0.1 55 100.00 0.1 16 100.00 4 6 4.7 15 92.75 0.1 52 100.00 0.1 13 100.00 5 6 4.0 14 90.00 0.1 55 100.00 0.1 14 100.00 6 8 5.2 23 97.85 0.1 45 100.00 0.1 27 100.00  Average 4.8 19.0 93.43 0.1 55.7 100.00 0.1 19.8 100.00Table1 reports the computational results with service level requirement α=0.95. In Table 1, CT, Obj, and Sel denote the computational time, objective value (i.e., the system cost), and the service level, respectively. The first column includes the indexes of instances, and the second indicates the number of nodes. It shows that the average service level obtained by the sampling approach is 94.57%, which is smaller than the required service level, i.e., 85%. Specifically, the service level of instance 5 obtained by the sampling approach is only 79.96%. However, MIP-DF1 and MIP-DF2 can guarantee the service levels for all instances higher than the requirement. Concluding, from Table 1, we can observe that (i) the average computational time of sampling approach is about 50 times as those of the two approximated MIP formulations and (ii) MIP-DF1 and MIP-DF2 improve the average service level by about 5.74% and 4.99% compared with sampling approach, however, (iii) system costs obtained by MIP-DF1 and MIP-DF2 are, respectively, 75.43% and 6.86% higher than that of sampling approach.Table2 reports the computational results with service level requirement α=0.99. For instances 2-6, the service levels obtained by sampling approach cannot meet the requirement, i.e., 99%. Besides, it shows that the average computational time of sampling approach is 4.8, which is about 48 times greater than those of MIP-DF1 and MIP-DF2. The average service level is 93.43%. Although the average service levels obtained by MIP-DF1 and MIP-DF2 are both 100%, the average system cost obtained by MIP-DF1 is about 3 times larger than that of sampling approach. Besides, the average system cost obtained by MIP-DF2 is 4.21% higher than that of sampling approach.Concluding, for the benchmarks described in Nickel et al. [8], we can observe that (1) MIP-DF1 and MIP-DF2 can be solved in far less computational time compared with the sampling approach; (2) the sampling approach cannot meet the requirement of service level for all benchmarks, while the two MIP formulations can; (3) the average system cost of MIP-DF2 is very close to that of sampling approach; (4) with the increase of α, the average system costs obtained by MIP-DF2 is getting closer to that obtained by sampling approach.From Tables1 and 2, we can observe that, in spite of the lower system cost obtained by the sampling approach, there may exist extreme situations that demands of some emergency points are not satisfied. Take one benchmark in Nickel et al. [8], i.e., instance 4, where there are 6 nodes. A scenario in which demand at each emergency point is generated from the given probability distribution is shown in Figure 1. We can observe from Figure 1 that under the given scenario, the demand of each possible emergency point is {1,0,2,0,2,0}. The solutions obtained by sampling approach, MIP-DF1 and MIP-DF2, are shown in Table 3, which includes base locations and ambulance employment obtained by in-sample test and ambulance assignment under given scenario.Table 3
Solutions to instance 4 in Nickel et al. [8] for the given scenario.
Sampling approach MIP-DF1 MIP-DF2 Emergency points 1 2 3 4 5 6 Emergency points 1 2 3 4 5 6 Emergency points 1 2 3 4 5 6 Demand 1 0 2 0 2 0 Demand 1 0 2 0 2 0 Demand 1 0 2 0 2 0 Base locations Ambulance employment       Ambulance employment       Ambulance employment 1 0       0       0 2 1   1    0       3 1  2 3 1 1      26 1  2  2  0 4 0       0       0 5 0       6       0 6 2     2  0       4     2Figure 1
Instance 4 in Nickel et al. [8] under given scenario.In Table3, the first column includes the indexes of potential base locations. The second column represents the base locations and the ambulance employment at each location, in which a location with 0 ambulance implies that it is not selected for base construction. From Table 3, we can observe that the in-sample solutions obtained by sampling approach is to construct bases at locations 2, 3 and 6, where the number of ambulances is 1, 1, and 2, respectively. Besides, under given scenario, there is one ambulance serving emergency point 1 from base location 3, and one ambulance serving emergency point from base location 2, and 2 ambulances serving emergency point 5 from base location 6. It shows that the requirement of ambulances at emergency point 3 is not fully satisfied. The insufficient service may cause serious loss of life. However, we can find that the solutions obtained by MIP-DF1 and MIP-DF2 can provide sufficient ambulances for all emergency points.In sum, to guarantee the required service level with less cost, MIP-DF2 is recommended for the solutions with Nickel et al. [8]’s data set. Moreover, in the benchmarks, it is assumed that all nodes are possible emergency points as well as potential base locations and the number of required ambulances is small, which is not always consistent with the situation in Shanghai. Therefore, we further test the two approximated MIP formulations and the sampling approach on randomly generated instances by analysing the information on emergencies in Shanghai [26].


### 5.3. Computational Tests on Randomly Generated Instances

In the following subsection, numerical experiments on 120 randomly generated instances are described.


#### 5.3.1. Test Instances

By analysing the information on emergencies in Shanghai [26], the mean value μj of demand dj in each emergency point are randomly generated from a discrete Uniform distribution on interval [5,25]. The standard deviation σj is set to be 5. Since the sampling approach proposed in Nickel et al. [8] requires a sample of scenarios, in numerical experiments scenarios are produced with demands randomly generated from Uniform distribution, Poisson distribution and Normal distribution consistent with given mean and standard deviation.According to the instance settings in Erkut and Ingolfsson (2008), response time from a base to an emergency point is randomly generated from a discrete Uniform distribution on interval[3,30] in units of minutes. A base covers an emergency point if the driving time between them is less than 10 minutes to ensure the survival probability (Erkut and Ingolfsson, 2006). For an emergency point in each instance, if there is no base with 10 minutes driving time to it, then the base covering this point is set to be the nearest one. The cost of constructing a base and that of locating one ambulance are both set to be 1, as in Nickel et al. [8]. Besides, the number of emergency points is 3 times that of potential base locations.


#### 5.3.2. Results and Discussion

Different values of required service levelα are tested, i.e., 0.85, 0.9, 0.95. Computational results on 120 randomly generated instances are reported in Tables 4-6.Table 4
Computational results on instances with data generated from uniform distribution.
S e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) 1 (2,6) 2.7 89 73.17 0.1 149 99.06 0.1 107 92.22 2.8 96 73.73 0.1 155 99.33 0.1 107 91.67 2.7 106 75.85 0.1 185 99.87 0.1 107 91.28 2 (4,12) 4.7 169 74.23 0.0 291 99.19 0.0 207 91.22 5.8 181 74.38 0.1 303 99.97 0.1 207 93.63 5.0 199 77.02 0.0 363 99.82 0.0 207 93.38 3 (6,18) 7.2 258 75.06 0.1 438 99.76 0.1 312 91.06 7.5 279 80.82 0.1 456 99.96 0.1 312 93.69 7.8 304 83.37 0.1 546 99.97 0.1 312 93.57 4 (8,24) 9.9 314 79.56 0.1 553 99.93 0.1 385 92.06 11.1 338 82.02 0.1 577 99.99 0.1 385 96.02 11.2 366 84.92 0.1 697 99.94 0.1 385 96.20 5 (10,30) 13.2 415 84.06 0.1 722 98.96 0.1 512 94.06 14.3 441 83.22 0.2 752 99.83 0.1 512 96.92 14.2 476 86.09 0.1 902 99.93 0.1 512 96.92 6 (12,36) 17.0 475 82.49 0.2 843 98.70 0.1 591 93.67 18.1 504 82.51 0.1 879 99.82 0.1 591 96.08 18.9 535 87.26 0.1 1059 99.97 0.1 591 96.09 7 (14,42) 21.5 573 81.11 0.2 1006 98.49 0.2 712 96.06 24.3 609 82.17 0.2 1048 99.53 0.2 712 95.89 23.3 644 86.08 0.2 1258 99.92 0.2 712 95.82 8 (16,48) 24.8 686 75.32 0.2 1185 98.96 0.2 849 97.25 28.4 727 83.07 0.2 1233 99.49 0.2 849 96.13 28.1 768 90.63 0.2 1473 99.99 0.3 849 96.22 9 (18,54) 31.3 691 83.53 0.3 1236 99.74 0.4 858 97.09 35.1 731 83.97 0.3 1290 99.88 0.3 858 97.65 35.2 760 89.06 0.3 1560 99.94 0.3 858 97.58 10 (20,60) 37.2 794 81.74 0.3 1409 98.87 0.3 989 96.57 42.8 843 84.89 0.3 1469 99.47 0.3 989 97.73 43.2 892 90.04 0.3 1769 99.97 0.3 989 97.38 11 (22,66) 45.1 830 80.72 0.4 1493 99.49 0.3 1031 97.58 51.8 880 83.28 0.4 1559 99.82 0.3 1031 97.23 51.6 930 89.67 0.5 1889 99.95 0.3 1031 97.27 12 (24,72) 54.3 1025 79.70 0.4 1771 99.27 0.4 1267 98.35 60.1 1083 84.82 0.5 1843 99.49 0.4 1267 97.76 63.7 1146 90.14 0.4 2203 99.93 0.4 1267 97.77 13 (26,78) 63.1 1026 81.42 0.5 1819 98.98 0.4 1274 97.82 74.3 1087 86.78 0.5 1897 99.36 0.4 1274 97.78 76.5 1146 90.23 0.4 2287 99.97 0.5 1273 98.37 14 (28,84) 78.2 1101 79.03 0.5 1949 98.69 0.8 1361 98.04 87.8 1165 87.90 0.5 2033 99.35 0.7 1361 98.89 87.0 1227 90.56 0.5 2453 99.98 0.6 1361 98.08 15 (30,90) 90.7 1091 80.98 0.6 1997 99.15 0.6 1367 96.29 101.8 1155 83.29 0.6 2087 99.81 0.6 1367 98.07 102.0 1225 89.86 0.6 2537 99.99 0.8 1367 98.17 16 (32,96) 106.2 1160 87.98 0.7 2123 99.44 0.7 1449 97.87 118.3 1229 83.83 0.7 2219 99.88 0.6 1449 98.49 119.3 1300 91.05 0.6 2698 99.98 0.6 1449 98.15 17 (34,102) 120.2 1298 75.72 0.7 2328 99.69 0.7 1614 98.21 137.7 1374 88.60 0.8 2430 99.97 0.7 1614 98.24 126.0 1452 90.85 0.7 2940 99.99 0.8 1614 98.18 18 (36,108) 139.4 1408 81.21 0.8 2509 99.47 0.8 1752 98.09 154.4 1492 89.28 0.8 2617 99.83 0.8 1752 97.99 154.8 1580 91.73 0.8 3156 99.99 0.8 1752 98.09 19 (38,114) 161.8 1508 81.70 0.9 2676 98.99 1.1 1877 97.42 176.0 1598 91.30 0.9 2790 99.34 0.8 1877 99.08 175.5 1688 91.86 0.9 3360 99.99 0.9 1877 98.72 20 (40,120) 220.6 1628 77.19 1.0 2869 99.89 1.0 2029 98.73 200.7 1732 87.53 1.1 2990 99.97 0.9 2029 98.79 190.4 1827 91.38 1.0 3590 99.98 0.9 2029 98.75 21 (42,126) 278.0 1622 83.54 1.0 2900 99.78 1.0 2017 97.32 260.9 1718 88.54 1.0 3026 98.76 1.0 2017 98.18 267.0 1812 90.89 1.2 3655 99.99 1.0 2017 98.48 22 (44,132) 318.9 1735 84.94 1.1 3088 99.85 1.5 2165 98.57 297.0 1840 89.22 1.2 3220 99.25 1.2 2165 98.86 287.3 1952 92.06 1.1 3880 99.99 1.1 2165 98.50 23 (46,138) 363.0 1937 81.41 1.2 3372 98.93 1.3 2406 97.96 322.2 2048 89.37 1.2 3510 99.34 1.4 2406 99.06 346.1 2170 89.89 1.2 4199 100.00 1.2 2406 98.09 24 (48,144) 422.6 1968 82.26 1.3 3461 99.32 1.3 2453 98.14 367.4 2085 88.46 1.3 3605 99.56 1.5 2453 99.12 355.6 2211 93.00 1.3 4326 99.99 1.3 2453 98.19 25 (50,150) 472.7 1919 81.11 1.4 3456 99.99 1.5 2407 96.29 401.9 2037 86.99 1.4 3606 99.99 1.4 2407 98.57 425.7 2161 92.59 1.5 4356 99.95 1.4 2407 98.19 26 (52,156) 530.0 1906 80.96 1.5 3484 98.78 1.7 2392 96.58 449.5 2021 89.52 1.4 3640 99.99 1.5 2392 95.68 448.6 2142 91.82 1.5 4420 99.99 1.5 2392 98.54 27 (54,162) 591.3 2096 83.87 1.6 3751 98.46 1.7 2617 97.61 511.7 2221 90.45 1.6 3913 99.98 1.7 2617 95.44 483.0 2355 93.46 1.8 4723 99.99 1.6 2617 98.93 28 (56,168) 631.0 2110 77.58 1.7 3819 99.33 1.9 2643 98.29 577.7 2234 91.57 1.8 3987 99.98 1.8 2643 95.26 555.0 2365 90.45 1.8 4827 99.99 1.7 2643 98.31 29 (58,174) 678.0 2175 79.98 1.8 3937 98.98 1.8 2720 97.14 630.3 2307 90.22 2.0 4111 99.69 1.9 2720 96.23 618.9 2444 91.28 1.9 4981 100.00 1.9 2720 99.14 30 (60,180) 759.3 2384 83.21 1.9 4240 99.67 2.0 2979 98.41 679.1 2527 89.78 1.9 4419 99.79 2.3 2979 97.21 687.8 2679 91.43 2.1 5316 99.99 2.0 2979 98.69 31 (62,186) 822.0 2281 76.04 2.0 4157 99.84 2.1 2856 97.96 773.4 2416 89.34 2.1 4343 99.97 2.1 2856 96.79 746.6 2557 91.58 2.2 5273 99.99 2.3 2856 99.02 32 (64,192) 876.6 2517 83.78 2.1 4489 99.32 2.5 3145 97.29 827.6 2671 82.96 2.3 4680 99.77 2.4 3145 98.25 789.7 2822 90.89 2.4 5640 99.99 2.2 3145 98.91 33 (66,198) 1012.3 2532 78.06 2.3 4555 99.67 2.3 3169 96.15 901.0 2682 89.47 2.4 4752 99.89 2.4 3169 97.03 905.1 2835 91.57 2.4 5742 99.98 2.4 3169 98.67 34 (68,204) 1101.0 2535 79.34 2.4 4602 99.99 2.9 3174 96.31 989.8 2685 88.58 3.0 4806 99.98 2.8 3174 97.62 986.3 2844 92.36 2.6 5824 99.99 2.5 3174 98.89 35 (70,210) 1166.6 2714 80.62 2.5 4862 99.86 2.9 3391 97.87 1066.6 2875 91.37 2.6 5072 99.99 2.9 3391 97.16 1082.2 3043 93.15 2.6 6122 99.99 2.9 3391 99.23 36 (72,216) 1201.1 2827 81.04 2.6 5047 99.91 2.8 3535 97.98 1246.5 2984 90.16 2.8 5263 99.99 2.8 3535 98.78 1166.7 3169 92.53 3.0 6343 99.99 2.9 3535 98.96 37 (74,222) 1143.7 2826 82.28 2.8 5096 99.33 2.9 3543 98.84 1358.2 3098 88.95 2.9 5318 99.99 3.2 3543 98.88 1265.4 3178 91.39 2.9 6427 100.00 3.1 3543 98.93 38 (76,228) 1243.5 2839 81.52 2.9 5161 98.97 2.9 3565 97.88 1397.6 3103 89.26 2.9 5388 99.99 3.1 3565 97.24 1383.7 3185 92.55 3.3 6528 100.00 3.1 3565 98.95 39 (78,234) 1464.3 2945 84.12 3.1 5331 99.98 3.2 3695 98.76 1479.4 3210 90.05 3.1 5565 99.99 3.4 3695 97.13 1456.1 3313 90.81 3.4 6735 100.00 3.3 3695 98.78 40 (80,240) 1604.2 2975 85.10 3.2 5414 99.57 3.6 3734 97.96 1626.3 3346 89.99 3.5 5654 99.99 3.5 3734 98.06 1586.9 3343 92.48 3.5 6854 100.00 3.5 3734 98.73  Average 448.2 1584.6 80.67 1.2 2839.7 99.36 1.3 1978.7 96.82 437.9 1691.3 86.54 1.3 2962.6 99.75 1.3 1978.7 97.21 429.5 1778.8 89.85 1.3 3577.4 99.97 1.3 1978.7 97.75Table4 reports the numerical results of instances with demand generated from Uniform distribution. We observe that when α=0.85,0.9,0.95, the average computational times of the sampling approach are 448.2, 437.9 and 429.5 seconds, respectively. However, both approximated MIP formulations can produce solutions in much faster speeds, i.e., within 1.3 seconds on average. With the increase of α, (i) the out-of-sample average service level is getting higher, and (ii) the system costs of solutions obtained by all method are getting larger, and (iii) the system costs of solutions yielded by MIP-DF2 is getting closer to those of solutions obtained by the sampling approach. In terms of the average system cost, the sampling approach performs the best, while MIP-DF1 is the poorest. When α=0.85, for example, the average system cost of MIP-DF2 and the sampling approach are about 30.32% and 44.2% less than that of MIP-DF1, respectively. When α=0.95, the above gaps are even larger. Concluding, for the Uniform distribution, (1) the proposed two approximated MIP formulations are far more time saving than the sampling approach, (2) MIP-DF1 and MIP-DF2 can improve the service level by about 19.07% compared with the sampling approach, however, (3) despite of the highest service levels obtained by MIP-DF1, the system cost obtained by MIP-DF1 is also high, (4) MIP-DF2 can ensure an appropriate service level with much less cost than MIP-DF1, and (5) for the situations with small-scale instances and high service level requirement, MIP-DF1 is recommended.Computational results of instances with demand at each emergency point generated from Poisson distribution are presented in Table5. For MIP-DF1 and MIP-DF2, only mean and variance are involved. Therefore, with given mean and standard deviation of the demand at each point, computational results are the same for different probability distributions. We can obtain from Table 5 that the objective value obtained by the sampling approach increases with the increase of α. Besides, when the value of α equals 0.85, the average service level obtained by the sampling approach is about 81.43%, which is smaller than that of the two approximated MIP formulations. The highest service level 99.34% is obtained by MIP-DF1, and that obtained by MIP-DF2 is 97.08%. When α=0.9, the average service level of the sampling approach is 84.37%, and those obtained by MIP-DF1 and MIP-DF2 are 99.85% and 97.97%, respectively. When α=0.95, the average service level obtained by the sampling approach is 93.56%, and those yielded by MIP-DF1 and MIP-DF2 are 99.97% and 97.81%, respectively. For Poisson distribution, concluding, MIP-DF1 and MIP-DF2 can improve the service level compared with the sampling approach, especially, MIP-DF1 can obtain the highest service level.Table 5
Computational results on instances with data generated from Poisson distribution.
s e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) 1 (2,6) 2.7 90 72.94 99.67 90.01 2.7 98 77.70 99.79 90.13 2.4 103 92.73 99.99 94.68 2 (4,12) 4.6 170 79.61 99.21 91.17 5.1 183 83.05 99.46 91.28 4.9 201 93.92 99.98 95.46 3 (6,18) 6.8 258 75.78 99.38 89.11 7.4 280 80.28 99.68 90.04 6.9 307 91.82 99.99 96.58 4 (8,24) 9.3 315 80.01 99.28 91.96 10.2 338 84.38 99.67 91.72 9.2 368 94.68 99.99 96.13 5 (10,30) 12.0 413 80.41 99.39 94.49 13.3 443 84.47 99.76 92.72 12.1 479 95.44 99.99 97.52 6 (12,36) 15.5 476 80.84 98.77 95.54 16.7 508 88.63 99.91 95.69 15.9 536 94.56 99.99 97.34 7 (14,42) 19.5 573 78.76 98.92 96.63 21.3 609 91.24 99.98 97.29 20.5 643 93.14 100.00 97.68 8 (16,48) 23.2 687 79.64 99.97 97.88 26.7 724 85.23 99.88 96.87 23.8 772 94.22 99.98 96.89 9 (18,54) 29.3 692 82.67 98.93 98.09 32.7 730 83.86 99.99 97.50 29.8 757 92.28 99.99 97.55 10 (20,60) 35.6 796 79.46 98.99 98.01 39.9 840 82.99 99.76 96.86 36.0 885 96.68 99.99 97.05 11 (22,66) 42.3 829 82.01 98.95 97.56 48.9 877 83.78 99.87 97.88 44.8 927 94.76 99.99 98.12 12 (24,72) 51.2 1023 83.38 99.13 98.53 55.4 1085 85.01 99.99 98.81 51.4 1148 93.98 99.99 98.88 13 (26,78) 59.2 1045 84.16 99.07 98.73 68.7 1088 79.98 99.96 98.02 60.7 1152 95.04 99.99 98.21 14 (28,84) 72.3 1099 79.46 99.15 97.88 83.8 1166 80.56 99.92 98.29 77.6 1230 95.46 99.99 98.39 15 (30,90) 85.5 1089 79.15 99.64 97.03 94.2 1156 84.32 99.84 97.78 90.3 1225 92.23 99.98 97.85 16 (32,96) 100.9 1158 80.24 98.97 97.69 116.3 1231 85.00 99.96 98.24 104.5 1222 91.99 99.99 98.35 17 (34,102) 116.5 1299 80.34 99.19 97.79 128.5 1375 84.95 99.37 98.08 119.0 1457 92.58 100.00 98.46 18 (36,108) 125.4 1411 81.76 99.43 98.85 147.9 1492 85.61 99.68 98.68 134.5 1579 92.86 99.99 98.75 19 (38,114) 150.4 1506 79.70 99.23 98.42 165.1 1594 81.67 99.72 98.46 156.4 1694 93.76 99.99 97.86 20 (40,120) 170.6 1635 78.19 99.16 97.83 185.4 1734 86.07 99.68 97.76 177.8 1825 92.85 99.04 97.18 21 (42,126) 205.4 1622 83.54 99.18 98.34 235.7 1720 82.97 99.78 98.33 222.6 1856 95.01 99.99 98.34 22 (44,132) 240.0 1736 84.94 99.22 98.46 285.2 1844 82.69 99.99 98.16 268.0 1946 94.86 99.99 98.20 23 (46,138) 265.1 1934 81.41 99.53 97.93 315.9 2049 84.92 99.69 97.99 307.2 2172 93.58 100.00 98.13 24 (48,144) 300.4 1961 82.26 99.47 96.81 352.2 2086 85.13 99.98 97.06 310.2 2209 94.88 99.99 97.24 25 (50,150) 330.8 1924 81.11 99.65 97.46 389.8 2038 82.64 99.99 97.88 363.9 2161 95.46 99.99 98.13 26 (52,156) 366.9 1911 80.96 99.39 98.55 430.5 2027 87.22 99.67 98.74 445.3 2142 91.85 99.99 98.76 27 (54,162) 441.8 2095 83.87 99.27 97.54 477.1 2219 83.41 99.89 97.49 480.6 2353 92.89 99.99 97.55 28 (56,168) 536.7 2113 84.58 99.68 98.48 535.6 2237 84.52 99.78 98.55 522.1 2369 92.28 100.00 98.68 29 (58,174) 621.7 2186 79.98 99.89 96.94 594.2 2315 83.16 99.96 96.99 585.3 2371 91.67 99.99 97.05 30 (60,180) 726.3 2382 83.21 99.91 98.37 652.7 2543 83.59 99.98 98.86 621.4 2678 93.69 99.97 98.86 31 (62,186) 821.4 2346 84.04 99.36 98.88 781.3 2430 83.21 99.99 98.46 687.6 2560 93.58 99.99 98.47 32 (64,192) 886.3 2518 83.78 99.38 98.07 810.6 2677 83.56 99.99 98.33 787.7 2822 94.08 100.00 98.35 33 (66,198) 998.5 2532 84.06 99.17 97.09 968.4 2689 84.97 99.96 97.46 808.8 2838 95.07 99.99 97.49 34 (68,204) 1126.4 2534 85.43 99.08 98.97 1098.6 2685 88.09 99.96 97.82 846.9 2843 88.44 99.98 97.80 35 (70,210) 1203.5 2715 82.58 99.37 97.99 1209.8 2886 85.69 99.91 98.09 994.6 3041 94.59 99.99 98.13 36 (72,216) 1280.3 2825 81.04 99.29 98.27 1307.6 3010 86.51 99.94 98.34 1101.3 3170 94.68 99.99 98.65 37 (74,222) 1302.1 2830 82.28 99.49 98.26 1326.1 3009 83.76 99.99 98.26 1201.4 3172 93.46 99.99 98.88 38 (76,228) 1386.2 2843 81.52 99.33 98.07 1399.5 3028 87.60 99.98 98.41 1213.3 3187 97.06 99.99 98.76 39 (78,234) 1538.7 2953 83.12 99.64 97.99 1482.7 3133 90.01 99.95 97.83 1338.1 3304 89.13 99.99 97.99 40 (80,240) 1697.4 2975 85.10 99.85 97.67 1525.6 3249 82.17 99.93 97.81 1586.7 3347 91.11 99.99 97.91  Average 435.2 1587.5 81.43 99.34 97.08 436.2 1685.6 84.37 99.85 97.07 396.8 1776.3 93.56 99.97 97.81Table 6
Computational results on instances with data generated from normal distribution.
s e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) 1 (2,6) 2.7 90 72.94 99.64 91.17 2.7 94 78.44 99.70 92.02 2.558 106 84.22 100.00 92.08 2 (4,12) 4.6 170 79.61 99.21 92.83 4.8 183 83.28 99.82 92.83 4.508 183 88.23 100.00 93.70 3 (6,18) 6.8 258 75.78 99.16 92.28 6.8 280 77.98 99.71 94.17 6.803 307 76.58 99.98 94.47 4 (8,24) 9.3 315 80.00 98.99 93.67 9.6 337 83.79 99.79 94.67 9.373 368 84.38 99.99 95.79 5 (10,30) 12.0 413 78.41 99.27 94.37 12.4 443 87.63 99.63 94.76 12.62 499 88.50 99.98 97.08 6 (12,36) 15.5 476 79.21 99.19 95.19 16.2 504 81.24 99.82 95.82 16.021 536 89.54 100.00 97.56 7 (14,42) 19.5 573 79.76 99.33 95.98 19.6 609 82.87 99.75 96.19 20.11 646 84.67 99.99 97.67 8 (16,48) 23.2 687 80.31 99.18 97.05 23.5 727 81.15 99.65 96.50 24.04 772 82.78 99.99 97.65 9 (18,54) 29.3 692 80.86 98.98 97.59 29.1 734 84.64 99.74 97.55 29.815 796 86.17 99.98 98.35 10 (20,60) 35.6 796 79.84 99.37 97.70 35.8 842 82.23 99.88 97.65 37.973 921 88.46 100.00 98.38 11 (22,66) 42.1 829 81.01 99.40 97.55 43.6 877 82.11 99.86 97.86 45.148 959 84.97 99.99 97.89 12 (24,72) 51.4 1023 80.33 99.51 97.85 50.1 1085 81.62 99.83 97.88 52.073 1147 83.21 99.99 98.24 13 (26,78) 59.2 1023 81.38 99.16 98.85 59.9 1087 84.11 99.70 98.45 62.937 1194 86.09 99.98 97.95 14 (28,84) 72.8 1099 82.35 99.13 99.15 72.2 1168 84.35 99.87 98.06 75.053 1270 85.67 99.97 98.34 15 (30,90) 85.5 1089 81.87 99.22 98.61 88.0 1157 83.76 99.76 97.96 89.222 1300 86.11 99.96 97.98 16 (32,96) 100.9 1158 87.70 98.97 97.88 96.6 1231 88.45 99.84 98.23 106.288 1359 89.97 99.99 98.48 17 (34,102) 115.4 1299 84.34 99.25 98.49 113.7 1377 86.01 99.80 97.98 123.869 1493 87.98 99.96 98.77 18 (36,108) 140.7 1411 83.21 99.27 98.66 133.9 1495 83.01 99.65 98.22 133.807 1601 85.67 99.99 98.34 19 (38,114) 170.2 1506 82.06 99.15 98.05 167.2 1598 89.77 99.78 98.45 152.999 1694 89.98 99.99 98.47 20 (40,120) 209.1 1635 85.28 99.18 98.89 191.6 1737 88.05 99.76 98.37 189.002 1833 90.12 99.99 97.91 21 (42,126) 284.3 1622 85.50 99.34 99.13 243.2 1718 88.86 99.74 98.13 239.913 1815 90.08 100.00 98.15 22 (44,132) 330.0 1736 84.49 99.40 98.59 279.5 1843 87.86 99.77 97.56 253.106 1948 89.97 99.99 98.26 23 (46,138) 374.1 1934 81.33 99.11 98.76 314.3 2050 88.76 99.81 97.85 274.583 2173 90.14 99.99 98.58 24 (48,144) 453.1 1961 82.45 99.09 98.46 351.5 2090 83.44 99.93 98.19 308.089 2211 86.61 99.99 98.83 25 (50,150) 471.5 1924 81.11 99.29 98.88 395.9 2041 82.79 99.96 98.37 351.093 2158 85.27 99.99 98.27 26 (52,156) 522.3 1911 80.96 98.98 98.57 430.1 2025 82.51 99.97 97.57 421.747 2146 84.97 99.99 99.14 27 (54,162) 599.4 2095 83.87 99.08 97.75 483.5 2226 84.97 99.74 97.80 461.443 2359 86.95 99.99 98.37 28 (56,168) 640.6 2111 84.11 99.06 97.98 533.6 2240 85.58 99.91 98.20 494.113 2371 92.49 99.99 98.16 29 (58,174) 689.7 2176 80.12 99.16 97.91 594.8 2311 82.11 99.84 97.65 624.835 2445 85.31 100.00 98.51 30 (60,180) 743.6 2391 81.11 99.13 97.66 655.8 2533 83.05 99.68 97.95 696.116 2682 85.75 99.99 97.99 31 (62,186) 811.8 2282 81.19 99.28 98.06 706.9 2422 84.17 99.73 98.73 797.768 2564 86.67 99.99 98.46 32 (64,192) 889.5 2519 82.23 99.19 97.57 785.7 2675 86.31 99.82 97.69 864.813 2827 89.76 100.00 99.05 33 (66,198) 1123.5 2533 85.63 99.28 98.11 916.2 2688 85.47 99.79 98.28 973.089 2843 86.57 99.99 98.46 34 (68,204) 1158.7 2534 82.49 99.26 98.47 954.9 2686 87.98 99.38 98.56 1052.3 3041 89.99 100.00 98.77 35 (70,210) 1164.9 2715 80.98 98.95 98.72 1034.5 2880 86.02 99.98 98.69 1127.2 3052 90.21 99.99 98.97 36 (72,216) 1222.4 2825 84.03 99.58 97.70 1116.5 3002 86.57 99.99 98.39 1245.6 3175 91.13 99.99 98.64 37 (74,222) 1297.8 2830 83.57 99.37 97.95 1185.0 3005 84.96 99.98 98.94 1345.8 3176 88.27 99.99 99.05 38 (76,228) 1342.6 2844 82.67 99.66 97.59 1279.5 3019 86.04 99.99 97.97 1515.5 3121 89.78 99.99 98.53 39 (78,234) 1500.3 2955 83.03 99.56 98.67 1381.6 3132 85.88 99.96 98.85 1504.1 3310 90.16 99.99 99.12 40 (80,240) 1649.5 2978 82.57 99.54 98.26 1489.6 3160 84.95 99.97 98.37 1656.3 3349 89.57 99.99 99.33  Average 461.9 1585.5 81.74 99.25 97.42 407.7 1682.8 84.57 99.81 97.43 435.0 1793.8 87.32 99.99 97.94Similarly, Table6 reports the computational results for instances in which the demand at each emergency point is generated following Normal distribution. When α=0.85, the average service levels obtained by the sampling approach, MIP-DF1 and MIP-DF2 are 81.74%, 99.25%, and 97.42%, respectively. When α=0.9, the three values are 84.57%, 99.81%, and 97.43% respectively. Moreover, for α=0.95, the values are equal to 87.32%, 99.99%, and 97.94%, respectively. It can be observed that the performance of the sampling approach is the poorest in terms of the service level.By observing the above computational results on benchmarks and randomly generated instances, we conclude that(1) The proposed approximated MIP formulations, i.e., MIP-DF1 and MIP-DF2 are very time saving compared with the sampling approach; (2) MIP-DF1 an MIP-DF2 can achieve the requirement of service level and improve the service level by about 15.47% and 12.29% on average, compared with that of the sampling approach; (3) MIP-DF1 is more conservative in terms of overhigh emergency service level close to 100%, and the system cost is also high, which is about 56.8% larger than that of MIP-DF2; (4) Compared with MIP-DF1, MIP-DF2 is less conservative and much more cost saving while ensuring an appropriately service level on average, which is about 97%.In sum, for medium and large problem instances (e.g., Shanghai), which are common in practice, to guarantee the required service level with less cost, we recommend MIP-DF2 as solution method. However, for very small instances with high service level requirement, we recommend MIP-DF1 for solutions.


## 5.1. Out-of-Sample Test

Following Zhang et al.’s [22] methodology, we examine the out-of-sample performance of solutions obtained by our proposed approximated MIP formulations and the sampling approach [8]. The out-of-sample test includes three steps:(1)
The base locations and the employment of ambulances at each base are determined with known mean vector and covariance matrix of demands, which is named as in-sample test.(2)
1000 scenarios are sampled from the underlying true distribution, which represent realizing the uncertain demand.(3)
Based on the solution obtained in step(1), ambulances are assigned to serve emergency points in the 1000 scenarios to maximize the (out-of-sample) service level.The (out-of-sample) service level is defined as the ratio of the number of emergency points with demand satisfied to the total number of emergency points in 1000 scenarios. In the following subsections, the benchmarks are tested and then three common distributions are employed, i.e., uniform distribution, Poisson distribution, and normal distribution, respectively.


## 5.2. Benchmark Instances

We first test the benchmarks in Nickel et al. [8] to compare our proposed two approximated MIP formulations with the sampling approach. In Nickel et al. [8], they assume that demand nodes are also potential base locations, and the number of ambulances required by each emergency point is chosen from set {0,1,2} with given probability distribution. Computational results on benchmarks are reported in Tables 1 and 2.Table 1
α = 0.95.
| I | = J Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) 1 7 4.9 23 96.26 0.1 36 100.00 0.1 23 100.00 2 7 5.1 22 98.63 0.1 35 100.00 0.1 24 99.82 3 6 4.1 14 96.92 0.1 30 100.00 0.1 14 98.50 4 6 4.3 13 97.13 0.2 29 100.00 0.1 12 97.42 5 6 5.7 12 79.96 0.1 30 100.00 0.2 12 100.00 6 8 5.8 21 98.50 0.1 24 100.00 0.2 27 100.00  Average 5.0 17.5 94.57 0.1 30.7 100.00 0.1 18.7 99.29Table 2
α = 0.99.
| I | = | J | Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) 1 7 4.9 24 99.79 0.1 64 100.00 0.1 25 100.00 2 7 4.8 23 98.56 0.1 63 100.00 0.1 24 100.00 3 6 5.1 15 97.17 0.1 55 100.00 0.1 16 100.00 4 6 4.7 15 92.75 0.1 52 100.00 0.1 13 100.00 5 6 4.0 14 90.00 0.1 55 100.00 0.1 14 100.00 6 8 5.2 23 97.85 0.1 45 100.00 0.1 27 100.00  Average 4.8 19.0 93.43 0.1 55.7 100.00 0.1 19.8 100.00Table1 reports the computational results with service level requirement α=0.95. In Table 1, CT, Obj, and Sel denote the computational time, objective value (i.e., the system cost), and the service level, respectively. The first column includes the indexes of instances, and the second indicates the number of nodes. It shows that the average service level obtained by the sampling approach is 94.57%, which is smaller than the required service level, i.e., 85%. Specifically, the service level of instance 5 obtained by the sampling approach is only 79.96%. However, MIP-DF1 and MIP-DF2 can guarantee the service levels for all instances higher than the requirement. Concluding, from Table 1, we can observe that (i) the average computational time of sampling approach is about 50 times as those of the two approximated MIP formulations and (ii) MIP-DF1 and MIP-DF2 improve the average service level by about 5.74% and 4.99% compared with sampling approach, however, (iii) system costs obtained by MIP-DF1 and MIP-DF2 are, respectively, 75.43% and 6.86% higher than that of sampling approach.Table2 reports the computational results with service level requirement α=0.99. For instances 2-6, the service levels obtained by sampling approach cannot meet the requirement, i.e., 99%. Besides, it shows that the average computational time of sampling approach is 4.8, which is about 48 times greater than those of MIP-DF1 and MIP-DF2. The average service level is 93.43%. Although the average service levels obtained by MIP-DF1 and MIP-DF2 are both 100%, the average system cost obtained by MIP-DF1 is about 3 times larger than that of sampling approach. Besides, the average system cost obtained by MIP-DF2 is 4.21% higher than that of sampling approach.Concluding, for the benchmarks described in Nickel et al. [8], we can observe that (1) MIP-DF1 and MIP-DF2 can be solved in far less computational time compared with the sampling approach; (2) the sampling approach cannot meet the requirement of service level for all benchmarks, while the two MIP formulations can; (3) the average system cost of MIP-DF2 is very close to that of sampling approach; (4) with the increase of α, the average system costs obtained by MIP-DF2 is getting closer to that obtained by sampling approach.From Tables1 and 2, we can observe that, in spite of the lower system cost obtained by the sampling approach, there may exist extreme situations that demands of some emergency points are not satisfied. Take one benchmark in Nickel et al. [8], i.e., instance 4, where there are 6 nodes. A scenario in which demand at each emergency point is generated from the given probability distribution is shown in Figure 1. We can observe from Figure 1 that under the given scenario, the demand of each possible emergency point is {1,0,2,0,2,0}. The solutions obtained by sampling approach, MIP-DF1 and MIP-DF2, are shown in Table 3, which includes base locations and ambulance employment obtained by in-sample test and ambulance assignment under given scenario.Table 3
Solutions to instance 4 in Nickel et al. [8] for the given scenario.
Sampling approach MIP-DF1 MIP-DF2 Emergency points 1 2 3 4 5 6 Emergency points 1 2 3 4 5 6 Emergency points 1 2 3 4 5 6 Demand 1 0 2 0 2 0 Demand 1 0 2 0 2 0 Demand 1 0 2 0 2 0 Base locations Ambulance employment       Ambulance employment       Ambulance employment 1 0       0       0 2 1   1    0       3 1  2 3 1 1      26 1  2  2  0 4 0       0       0 5 0       6       0 6 2     2  0       4     2Figure 1
Instance 4 in Nickel et al. [8] under given scenario.In Table3, the first column includes the indexes of potential base locations. The second column represents the base locations and the ambulance employment at each location, in which a location with 0 ambulance implies that it is not selected for base construction. From Table 3, we can observe that the in-sample solutions obtained by sampling approach is to construct bases at locations 2, 3 and 6, where the number of ambulances is 1, 1, and 2, respectively. Besides, under given scenario, there is one ambulance serving emergency point 1 from base location 3, and one ambulance serving emergency point from base location 2, and 2 ambulances serving emergency point 5 from base location 6. It shows that the requirement of ambulances at emergency point 3 is not fully satisfied. The insufficient service may cause serious loss of life. However, we can find that the solutions obtained by MIP-DF1 and MIP-DF2 can provide sufficient ambulances for all emergency points.In sum, to guarantee the required service level with less cost, MIP-DF2 is recommended for the solutions with Nickel et al. [8]’s data set. Moreover, in the benchmarks, it is assumed that all nodes are possible emergency points as well as potential base locations and the number of required ambulances is small, which is not always consistent with the situation in Shanghai. Therefore, we further test the two approximated MIP formulations and the sampling approach on randomly generated instances by analysing the information on emergencies in Shanghai [26].


## 5.3. Computational Tests on Randomly Generated Instances

In the following subsection, numerical experiments on 120 randomly generated instances are described.


### 5.3.1. Test Instances

By analysing the information on emergencies in Shanghai [26], the mean value μj of demand dj in each emergency point are randomly generated from a discrete Uniform distribution on interval [5,25]. The standard deviation σj is set to be 5. Since the sampling approach proposed in Nickel et al. [8] requires a sample of scenarios, in numerical experiments scenarios are produced with demands randomly generated from Uniform distribution, Poisson distribution and Normal distribution consistent with given mean and standard deviation.According to the instance settings in Erkut and Ingolfsson (2008), response time from a base to an emergency point is randomly generated from a discrete Uniform distribution on interval[3,30] in units of minutes. A base covers an emergency point if the driving time between them is less than 10 minutes to ensure the survival probability (Erkut and Ingolfsson, 2006). For an emergency point in each instance, if there is no base with 10 minutes driving time to it, then the base covering this point is set to be the nearest one. The cost of constructing a base and that of locating one ambulance are both set to be 1, as in Nickel et al. [8]. Besides, the number of emergency points is 3 times that of potential base locations.


### 5.3.2. Results and Discussion

Different values of required service levelα are tested, i.e., 0.85, 0.9, 0.95. Computational results on 120 randomly generated instances are reported in Tables 4-6.Table 4
Computational results on instances with data generated from uniform distribution.
S e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) 1 (2,6) 2.7 89 73.17 0.1 149 99.06 0.1 107 92.22 2.8 96 73.73 0.1 155 99.33 0.1 107 91.67 2.7 106 75.85 0.1 185 99.87 0.1 107 91.28 2 (4,12) 4.7 169 74.23 0.0 291 99.19 0.0 207 91.22 5.8 181 74.38 0.1 303 99.97 0.1 207 93.63 5.0 199 77.02 0.0 363 99.82 0.0 207 93.38 3 (6,18) 7.2 258 75.06 0.1 438 99.76 0.1 312 91.06 7.5 279 80.82 0.1 456 99.96 0.1 312 93.69 7.8 304 83.37 0.1 546 99.97 0.1 312 93.57 4 (8,24) 9.9 314 79.56 0.1 553 99.93 0.1 385 92.06 11.1 338 82.02 0.1 577 99.99 0.1 385 96.02 11.2 366 84.92 0.1 697 99.94 0.1 385 96.20 5 (10,30) 13.2 415 84.06 0.1 722 98.96 0.1 512 94.06 14.3 441 83.22 0.2 752 99.83 0.1 512 96.92 14.2 476 86.09 0.1 902 99.93 0.1 512 96.92 6 (12,36) 17.0 475 82.49 0.2 843 98.70 0.1 591 93.67 18.1 504 82.51 0.1 879 99.82 0.1 591 96.08 18.9 535 87.26 0.1 1059 99.97 0.1 591 96.09 7 (14,42) 21.5 573 81.11 0.2 1006 98.49 0.2 712 96.06 24.3 609 82.17 0.2 1048 99.53 0.2 712 95.89 23.3 644 86.08 0.2 1258 99.92 0.2 712 95.82 8 (16,48) 24.8 686 75.32 0.2 1185 98.96 0.2 849 97.25 28.4 727 83.07 0.2 1233 99.49 0.2 849 96.13 28.1 768 90.63 0.2 1473 99.99 0.3 849 96.22 9 (18,54) 31.3 691 83.53 0.3 1236 99.74 0.4 858 97.09 35.1 731 83.97 0.3 1290 99.88 0.3 858 97.65 35.2 760 89.06 0.3 1560 99.94 0.3 858 97.58 10 (20,60) 37.2 794 81.74 0.3 1409 98.87 0.3 989 96.57 42.8 843 84.89 0.3 1469 99.47 0.3 989 97.73 43.2 892 90.04 0.3 1769 99.97 0.3 989 97.38 11 (22,66) 45.1 830 80.72 0.4 1493 99.49 0.3 1031 97.58 51.8 880 83.28 0.4 1559 99.82 0.3 1031 97.23 51.6 930 89.67 0.5 1889 99.95 0.3 1031 97.27 12 (24,72) 54.3 1025 79.70 0.4 1771 99.27 0.4 1267 98.35 60.1 1083 84.82 0.5 1843 99.49 0.4 1267 97.76 63.7 1146 90.14 0.4 2203 99.93 0.4 1267 97.77 13 (26,78) 63.1 1026 81.42 0.5 1819 98.98 0.4 1274 97.82 74.3 1087 86.78 0.5 1897 99.36 0.4 1274 97.78 76.5 1146 90.23 0.4 2287 99.97 0.5 1273 98.37 14 (28,84) 78.2 1101 79.03 0.5 1949 98.69 0.8 1361 98.04 87.8 1165 87.90 0.5 2033 99.35 0.7 1361 98.89 87.0 1227 90.56 0.5 2453 99.98 0.6 1361 98.08 15 (30,90) 90.7 1091 80.98 0.6 1997 99.15 0.6 1367 96.29 101.8 1155 83.29 0.6 2087 99.81 0.6 1367 98.07 102.0 1225 89.86 0.6 2537 99.99 0.8 1367 98.17 16 (32,96) 106.2 1160 87.98 0.7 2123 99.44 0.7 1449 97.87 118.3 1229 83.83 0.7 2219 99.88 0.6 1449 98.49 119.3 1300 91.05 0.6 2698 99.98 0.6 1449 98.15 17 (34,102) 120.2 1298 75.72 0.7 2328 99.69 0.7 1614 98.21 137.7 1374 88.60 0.8 2430 99.97 0.7 1614 98.24 126.0 1452 90.85 0.7 2940 99.99 0.8 1614 98.18 18 (36,108) 139.4 1408 81.21 0.8 2509 99.47 0.8 1752 98.09 154.4 1492 89.28 0.8 2617 99.83 0.8 1752 97.99 154.8 1580 91.73 0.8 3156 99.99 0.8 1752 98.09 19 (38,114) 161.8 1508 81.70 0.9 2676 98.99 1.1 1877 97.42 176.0 1598 91.30 0.9 2790 99.34 0.8 1877 99.08 175.5 1688 91.86 0.9 3360 99.99 0.9 1877 98.72 20 (40,120) 220.6 1628 77.19 1.0 2869 99.89 1.0 2029 98.73 200.7 1732 87.53 1.1 2990 99.97 0.9 2029 98.79 190.4 1827 91.38 1.0 3590 99.98 0.9 2029 98.75 21 (42,126) 278.0 1622 83.54 1.0 2900 99.78 1.0 2017 97.32 260.9 1718 88.54 1.0 3026 98.76 1.0 2017 98.18 267.0 1812 90.89 1.2 3655 99.99 1.0 2017 98.48 22 (44,132) 318.9 1735 84.94 1.1 3088 99.85 1.5 2165 98.57 297.0 1840 89.22 1.2 3220 99.25 1.2 2165 98.86 287.3 1952 92.06 1.1 3880 99.99 1.1 2165 98.50 23 (46,138) 363.0 1937 81.41 1.2 3372 98.93 1.3 2406 97.96 322.2 2048 89.37 1.2 3510 99.34 1.4 2406 99.06 346.1 2170 89.89 1.2 4199 100.00 1.2 2406 98.09 24 (48,144) 422.6 1968 82.26 1.3 3461 99.32 1.3 2453 98.14 367.4 2085 88.46 1.3 3605 99.56 1.5 2453 99.12 355.6 2211 93.00 1.3 4326 99.99 1.3 2453 98.19 25 (50,150) 472.7 1919 81.11 1.4 3456 99.99 1.5 2407 96.29 401.9 2037 86.99 1.4 3606 99.99 1.4 2407 98.57 425.7 2161 92.59 1.5 4356 99.95 1.4 2407 98.19 26 (52,156) 530.0 1906 80.96 1.5 3484 98.78 1.7 2392 96.58 449.5 2021 89.52 1.4 3640 99.99 1.5 2392 95.68 448.6 2142 91.82 1.5 4420 99.99 1.5 2392 98.54 27 (54,162) 591.3 2096 83.87 1.6 3751 98.46 1.7 2617 97.61 511.7 2221 90.45 1.6 3913 99.98 1.7 2617 95.44 483.0 2355 93.46 1.8 4723 99.99 1.6 2617 98.93 28 (56,168) 631.0 2110 77.58 1.7 3819 99.33 1.9 2643 98.29 577.7 2234 91.57 1.8 3987 99.98 1.8 2643 95.26 555.0 2365 90.45 1.8 4827 99.99 1.7 2643 98.31 29 (58,174) 678.0 2175 79.98 1.8 3937 98.98 1.8 2720 97.14 630.3 2307 90.22 2.0 4111 99.69 1.9 2720 96.23 618.9 2444 91.28 1.9 4981 100.00 1.9 2720 99.14 30 (60,180) 759.3 2384 83.21 1.9 4240 99.67 2.0 2979 98.41 679.1 2527 89.78 1.9 4419 99.79 2.3 2979 97.21 687.8 2679 91.43 2.1 5316 99.99 2.0 2979 98.69 31 (62,186) 822.0 2281 76.04 2.0 4157 99.84 2.1 2856 97.96 773.4 2416 89.34 2.1 4343 99.97 2.1 2856 96.79 746.6 2557 91.58 2.2 5273 99.99 2.3 2856 99.02 32 (64,192) 876.6 2517 83.78 2.1 4489 99.32 2.5 3145 97.29 827.6 2671 82.96 2.3 4680 99.77 2.4 3145 98.25 789.7 2822 90.89 2.4 5640 99.99 2.2 3145 98.91 33 (66,198) 1012.3 2532 78.06 2.3 4555 99.67 2.3 3169 96.15 901.0 2682 89.47 2.4 4752 99.89 2.4 3169 97.03 905.1 2835 91.57 2.4 5742 99.98 2.4 3169 98.67 34 (68,204) 1101.0 2535 79.34 2.4 4602 99.99 2.9 3174 96.31 989.8 2685 88.58 3.0 4806 99.98 2.8 3174 97.62 986.3 2844 92.36 2.6 5824 99.99 2.5 3174 98.89 35 (70,210) 1166.6 2714 80.62 2.5 4862 99.86 2.9 3391 97.87 1066.6 2875 91.37 2.6 5072 99.99 2.9 3391 97.16 1082.2 3043 93.15 2.6 6122 99.99 2.9 3391 99.23 36 (72,216) 1201.1 2827 81.04 2.6 5047 99.91 2.8 3535 97.98 1246.5 2984 90.16 2.8 5263 99.99 2.8 3535 98.78 1166.7 3169 92.53 3.0 6343 99.99 2.9 3535 98.96 37 (74,222) 1143.7 2826 82.28 2.8 5096 99.33 2.9 3543 98.84 1358.2 3098 88.95 2.9 5318 99.99 3.2 3543 98.88 1265.4 3178 91.39 2.9 6427 100.00 3.1 3543 98.93 38 (76,228) 1243.5 2839 81.52 2.9 5161 98.97 2.9 3565 97.88 1397.6 3103 89.26 2.9 5388 99.99 3.1 3565 97.24 1383.7 3185 92.55 3.3 6528 100.00 3.1 3565 98.95 39 (78,234) 1464.3 2945 84.12 3.1 5331 99.98 3.2 3695 98.76 1479.4 3210 90.05 3.1 5565 99.99 3.4 3695 97.13 1456.1 3313 90.81 3.4 6735 100.00 3.3 3695 98.78 40 (80,240) 1604.2 2975 85.10 3.2 5414 99.57 3.6 3734 97.96 1626.3 3346 89.99 3.5 5654 99.99 3.5 3734 98.06 1586.9 3343 92.48 3.5 6854 100.00 3.5 3734 98.73  Average 448.2 1584.6 80.67 1.2 2839.7 99.36 1.3 1978.7 96.82 437.9 1691.3 86.54 1.3 2962.6 99.75 1.3 1978.7 97.21 429.5 1778.8 89.85 1.3 3577.4 99.97 1.3 1978.7 97.75Table4 reports the numerical results of instances with demand generated from Uniform distribution. We observe that when α=0.85,0.9,0.95, the average computational times of the sampling approach are 448.2, 437.9 and 429.5 seconds, respectively. However, both approximated MIP formulations can produce solutions in much faster speeds, i.e., within 1.3 seconds on average. With the increase of α, (i) the out-of-sample average service level is getting higher, and (ii) the system costs of solutions obtained by all method are getting larger, and (iii) the system costs of solutions yielded by MIP-DF2 is getting closer to those of solutions obtained by the sampling approach. In terms of the average system cost, the sampling approach performs the best, while MIP-DF1 is the poorest. When α=0.85, for example, the average system cost of MIP-DF2 and the sampling approach are about 30.32% and 44.2% less than that of MIP-DF1, respectively. When α=0.95, the above gaps are even larger. Concluding, for the Uniform distribution, (1) the proposed two approximated MIP formulations are far more time saving than the sampling approach, (2) MIP-DF1 and MIP-DF2 can improve the service level by about 19.07% compared with the sampling approach, however, (3) despite of the highest service levels obtained by MIP-DF1, the system cost obtained by MIP-DF1 is also high, (4) MIP-DF2 can ensure an appropriate service level with much less cost than MIP-DF1, and (5) for the situations with small-scale instances and high service level requirement, MIP-DF1 is recommended.Computational results of instances with demand at each emergency point generated from Poisson distribution are presented in Table5. For MIP-DF1 and MIP-DF2, only mean and variance are involved. Therefore, with given mean and standard deviation of the demand at each point, computational results are the same for different probability distributions. We can obtain from Table 5 that the objective value obtained by the sampling approach increases with the increase of α. Besides, when the value of α equals 0.85, the average service level obtained by the sampling approach is about 81.43%, which is smaller than that of the two approximated MIP formulations. The highest service level 99.34% is obtained by MIP-DF1, and that obtained by MIP-DF2 is 97.08%. When α=0.9, the average service level of the sampling approach is 84.37%, and those obtained by MIP-DF1 and MIP-DF2 are 99.85% and 97.97%, respectively. When α=0.95, the average service level obtained by the sampling approach is 93.56%, and those yielded by MIP-DF1 and MIP-DF2 are 99.97% and 97.81%, respectively. For Poisson distribution, concluding, MIP-DF1 and MIP-DF2 can improve the service level compared with the sampling approach, especially, MIP-DF1 can obtain the highest service level.Table 5
Computational results on instances with data generated from Poisson distribution.
s e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) 1 (2,6) 2.7 90 72.94 99.67 90.01 2.7 98 77.70 99.79 90.13 2.4 103 92.73 99.99 94.68 2 (4,12) 4.6 170 79.61 99.21 91.17 5.1 183 83.05 99.46 91.28 4.9 201 93.92 99.98 95.46 3 (6,18) 6.8 258 75.78 99.38 89.11 7.4 280 80.28 99.68 90.04 6.9 307 91.82 99.99 96.58 4 (8,24) 9.3 315 80.01 99.28 91.96 10.2 338 84.38 99.67 91.72 9.2 368 94.68 99.99 96.13 5 (10,30) 12.0 413 80.41 99.39 94.49 13.3 443 84.47 99.76 92.72 12.1 479 95.44 99.99 97.52 6 (12,36) 15.5 476 80.84 98.77 95.54 16.7 508 88.63 99.91 95.69 15.9 536 94.56 99.99 97.34 7 (14,42) 19.5 573 78.76 98.92 96.63 21.3 609 91.24 99.98 97.29 20.5 643 93.14 100.00 97.68 8 (16,48) 23.2 687 79.64 99.97 97.88 26.7 724 85.23 99.88 96.87 23.8 772 94.22 99.98 96.89 9 (18,54) 29.3 692 82.67 98.93 98.09 32.7 730 83.86 99.99 97.50 29.8 757 92.28 99.99 97.55 10 (20,60) 35.6 796 79.46 98.99 98.01 39.9 840 82.99 99.76 96.86 36.0 885 96.68 99.99 97.05 11 (22,66) 42.3 829 82.01 98.95 97.56 48.9 877 83.78 99.87 97.88 44.8 927 94.76 99.99 98.12 12 (24,72) 51.2 1023 83.38 99.13 98.53 55.4 1085 85.01 99.99 98.81 51.4 1148 93.98 99.99 98.88 13 (26,78) 59.2 1045 84.16 99.07 98.73 68.7 1088 79.98 99.96 98.02 60.7 1152 95.04 99.99 98.21 14 (28,84) 72.3 1099 79.46 99.15 97.88 83.8 1166 80.56 99.92 98.29 77.6 1230 95.46 99.99 98.39 15 (30,90) 85.5 1089 79.15 99.64 97.03 94.2 1156 84.32 99.84 97.78 90.3 1225 92.23 99.98 97.85 16 (32,96) 100.9 1158 80.24 98.97 97.69 116.3 1231 85.00 99.96 98.24 104.5 1222 91.99 99.99 98.35 17 (34,102) 116.5 1299 80.34 99.19 97.79 128.5 1375 84.95 99.37 98.08 119.0 1457 92.58 100.00 98.46 18 (36,108) 125.4 1411 81.76 99.43 98.85 147.9 1492 85.61 99.68 98.68 134.5 1579 92.86 99.99 98.75 19 (38,114) 150.4 1506 79.70 99.23 98.42 165.1 1594 81.67 99.72 98.46 156.4 1694 93.76 99.99 97.86 20 (40,120) 170.6 1635 78.19 99.16 97.83 185.4 1734 86.07 99.68 97.76 177.8 1825 92.85 99.04 97.18 21 (42,126) 205.4 1622 83.54 99.18 98.34 235.7 1720 82.97 99.78 98.33 222.6 1856 95.01 99.99 98.34 22 (44,132) 240.0 1736 84.94 99.22 98.46 285.2 1844 82.69 99.99 98.16 268.0 1946 94.86 99.99 98.20 23 (46,138) 265.1 1934 81.41 99.53 97.93 315.9 2049 84.92 99.69 97.99 307.2 2172 93.58 100.00 98.13 24 (48,144) 300.4 1961 82.26 99.47 96.81 352.2 2086 85.13 99.98 97.06 310.2 2209 94.88 99.99 97.24 25 (50,150) 330.8 1924 81.11 99.65 97.46 389.8 2038 82.64 99.99 97.88 363.9 2161 95.46 99.99 98.13 26 (52,156) 366.9 1911 80.96 99.39 98.55 430.5 2027 87.22 99.67 98.74 445.3 2142 91.85 99.99 98.76 27 (54,162) 441.8 2095 83.87 99.27 97.54 477.1 2219 83.41 99.89 97.49 480.6 2353 92.89 99.99 97.55 28 (56,168) 536.7 2113 84.58 99.68 98.48 535.6 2237 84.52 99.78 98.55 522.1 2369 92.28 100.00 98.68 29 (58,174) 621.7 2186 79.98 99.89 96.94 594.2 2315 83.16 99.96 96.99 585.3 2371 91.67 99.99 97.05 30 (60,180) 726.3 2382 83.21 99.91 98.37 652.7 2543 83.59 99.98 98.86 621.4 2678 93.69 99.97 98.86 31 (62,186) 821.4 2346 84.04 99.36 98.88 781.3 2430 83.21 99.99 98.46 687.6 2560 93.58 99.99 98.47 32 (64,192) 886.3 2518 83.78 99.38 98.07 810.6 2677 83.56 99.99 98.33 787.7 2822 94.08 100.00 98.35 33 (66,198) 998.5 2532 84.06 99.17 97.09 968.4 2689 84.97 99.96 97.46 808.8 2838 95.07 99.99 97.49 34 (68,204) 1126.4 2534 85.43 99.08 98.97 1098.6 2685 88.09 99.96 97.82 846.9 2843 88.44 99.98 97.80 35 (70,210) 1203.5 2715 82.58 99.37 97.99 1209.8 2886 85.69 99.91 98.09 994.6 3041 94.59 99.99 98.13 36 (72,216) 1280.3 2825 81.04 99.29 98.27 1307.6 3010 86.51 99.94 98.34 1101.3 3170 94.68 99.99 98.65 37 (74,222) 1302.1 2830 82.28 99.49 98.26 1326.1 3009 83.76 99.99 98.26 1201.4 3172 93.46 99.99 98.88 38 (76,228) 1386.2 2843 81.52 99.33 98.07 1399.5 3028 87.60 99.98 98.41 1213.3 3187 97.06 99.99 98.76 39 (78,234) 1538.7 2953 83.12 99.64 97.99 1482.7 3133 90.01 99.95 97.83 1338.1 3304 89.13 99.99 97.99 40 (80,240) 1697.4 2975 85.10 99.85 97.67 1525.6 3249 82.17 99.93 97.81 1586.7 3347 91.11 99.99 97.91  Average 435.2 1587.5 81.43 99.34 97.08 436.2 1685.6 84.37 99.85 97.07 396.8 1776.3 93.56 99.97 97.81Table 6
Computational results on instances with data generated from normal distribution.
s e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) 1 (2,6) 2.7 90 72.94 99.64 91.17 2.7 94 78.44 99.70 92.02 2.558 106 84.22 100.00 92.08 2 (4,12) 4.6 170 79.61 99.21 92.83 4.8 183 83.28 99.82 92.83 4.508 183 88.23 100.00 93.70 3 (6,18) 6.8 258 75.78 99.16 92.28 6.8 280 77.98 99.71 94.17 6.803 307 76.58 99.98 94.47 4 (8,24) 9.3 315 80.00 98.99 93.67 9.6 337 83.79 99.79 94.67 9.373 368 84.38 99.99 95.79 5 (10,30) 12.0 413 78.41 99.27 94.37 12.4 443 87.63 99.63 94.76 12.62 499 88.50 99.98 97.08 6 (12,36) 15.5 476 79.21 99.19 95.19 16.2 504 81.24 99.82 95.82 16.021 536 89.54 100.00 97.56 7 (14,42) 19.5 573 79.76 99.33 95.98 19.6 609 82.87 99.75 96.19 20.11 646 84.67 99.99 97.67 8 (16,48) 23.2 687 80.31 99.18 97.05 23.5 727 81.15 99.65 96.50 24.04 772 82.78 99.99 97.65 9 (18,54) 29.3 692 80.86 98.98 97.59 29.1 734 84.64 99.74 97.55 29.815 796 86.17 99.98 98.35 10 (20,60) 35.6 796 79.84 99.37 97.70 35.8 842 82.23 99.88 97.65 37.973 921 88.46 100.00 98.38 11 (22,66) 42.1 829 81.01 99.40 97.55 43.6 877 82.11 99.86 97.86 45.148 959 84.97 99.99 97.89 12 (24,72) 51.4 1023 80.33 99.51 97.85 50.1 1085 81.62 99.83 97.88 52.073 1147 83.21 99.99 98.24 13 (26,78) 59.2 1023 81.38 99.16 98.85 59.9 1087 84.11 99.70 98.45 62.937 1194 86.09 99.98 97.95 14 (28,84) 72.8 1099 82.35 99.13 99.15 72.2 1168 84.35 99.87 98.06 75.053 1270 85.67 99.97 98.34 15 (30,90) 85.5 1089 81.87 99.22 98.61 88.0 1157 83.76 99.76 97.96 89.222 1300 86.11 99.96 97.98 16 (32,96) 100.9 1158 87.70 98.97 97.88 96.6 1231 88.45 99.84 98.23 106.288 1359 89.97 99.99 98.48 17 (34,102) 115.4 1299 84.34 99.25 98.49 113.7 1377 86.01 99.80 97.98 123.869 1493 87.98 99.96 98.77 18 (36,108) 140.7 1411 83.21 99.27 98.66 133.9 1495 83.01 99.65 98.22 133.807 1601 85.67 99.99 98.34 19 (38,114) 170.2 1506 82.06 99.15 98.05 167.2 1598 89.77 99.78 98.45 152.999 1694 89.98 99.99 98.47 20 (40,120) 209.1 1635 85.28 99.18 98.89 191.6 1737 88.05 99.76 98.37 189.002 1833 90.12 99.99 97.91 21 (42,126) 284.3 1622 85.50 99.34 99.13 243.2 1718 88.86 99.74 98.13 239.913 1815 90.08 100.00 98.15 22 (44,132) 330.0 1736 84.49 99.40 98.59 279.5 1843 87.86 99.77 97.56 253.106 1948 89.97 99.99 98.26 23 (46,138) 374.1 1934 81.33 99.11 98.76 314.3 2050 88.76 99.81 97.85 274.583 2173 90.14 99.99 98.58 24 (48,144) 453.1 1961 82.45 99.09 98.46 351.5 2090 83.44 99.93 98.19 308.089 2211 86.61 99.99 98.83 25 (50,150) 471.5 1924 81.11 99.29 98.88 395.9 2041 82.79 99.96 98.37 351.093 2158 85.27 99.99 98.27 26 (52,156) 522.3 1911 80.96 98.98 98.57 430.1 2025 82.51 99.97 97.57 421.747 2146 84.97 99.99 99.14 27 (54,162) 599.4 2095 83.87 99.08 97.75 483.5 2226 84.97 99.74 97.80 461.443 2359 86.95 99.99 98.37 28 (56,168) 640.6 2111 84.11 99.06 97.98 533.6 2240 85.58 99.91 98.20 494.113 2371 92.49 99.99 98.16 29 (58,174) 689.7 2176 80.12 99.16 97.91 594.8 2311 82.11 99.84 97.65 624.835 2445 85.31 100.00 98.51 30 (60,180) 743.6 2391 81.11 99.13 97.66 655.8 2533 83.05 99.68 97.95 696.116 2682 85.75 99.99 97.99 31 (62,186) 811.8 2282 81.19 99.28 98.06 706.9 2422 84.17 99.73 98.73 797.768 2564 86.67 99.99 98.46 32 (64,192) 889.5 2519 82.23 99.19 97.57 785.7 2675 86.31 99.82 97.69 864.813 2827 89.76 100.00 99.05 33 (66,198) 1123.5 2533 85.63 99.28 98.11 916.2 2688 85.47 99.79 98.28 973.089 2843 86.57 99.99 98.46 34 (68,204) 1158.7 2534 82.49 99.26 98.47 954.9 2686 87.98 99.38 98.56 1052.3 3041 89.99 100.00 98.77 35 (70,210) 1164.9 2715 80.98 98.95 98.72 1034.5 2880 86.02 99.98 98.69 1127.2 3052 90.21 99.99 98.97 36 (72,216) 1222.4 2825 84.03 99.58 97.70 1116.5 3002 86.57 99.99 98.39 1245.6 3175 91.13 99.99 98.64 37 (74,222) 1297.8 2830 83.57 99.37 97.95 1185.0 3005 84.96 99.98 98.94 1345.8 3176 88.27 99.99 99.05 38 (76,228) 1342.6 2844 82.67 99.66 97.59 1279.5 3019 86.04 99.99 97.97 1515.5 3121 89.78 99.99 98.53 39 (78,234) 1500.3 2955 83.03 99.56 98.67 1381.6 3132 85.88 99.96 98.85 1504.1 3310 90.16 99.99 99.12 40 (80,240) 1649.5 2978 82.57 99.54 98.26 1489.6 3160 84.95 99.97 98.37 1656.3 3349 89.57 99.99 99.33  Average 461.9 1585.5 81.74 99.25 97.42 407.7 1682.8 84.57 99.81 97.43 435.0 1793.8 87.32 99.99 97.94Similarly, Table6 reports the computational results for instances in which the demand at each emergency point is generated following Normal distribution. When α=0.85, the average service levels obtained by the sampling approach, MIP-DF1 and MIP-DF2 are 81.74%, 99.25%, and 97.42%, respectively. When α=0.9, the three values are 84.57%, 99.81%, and 97.43% respectively. Moreover, for α=0.95, the values are equal to 87.32%, 99.99%, and 97.94%, respectively. It can be observed that the performance of the sampling approach is the poorest in terms of the service level.By observing the above computational results on benchmarks and randomly generated instances, we conclude that(1) The proposed approximated MIP formulations, i.e., MIP-DF1 and MIP-DF2 are very time saving compared with the sampling approach; (2) MIP-DF1 an MIP-DF2 can achieve the requirement of service level and improve the service level by about 15.47% and 12.29% on average, compared with that of the sampling approach; (3) MIP-DF1 is more conservative in terms of overhigh emergency service level close to 100%, and the system cost is also high, which is about 56.8% larger than that of MIP-DF2; (4) Compared with MIP-DF1, MIP-DF2 is less conservative and much more cost saving while ensuring an appropriately service level on average, which is about 97%.In sum, for medium and large problem instances (e.g., Shanghai), which are common in practice, to guarantee the required service level with less cost, we recommend MIP-DF2 as solution method. However, for very small instances with high service level requirement, we recommend MIP-DF1 for solutions.


## 5.3.1. Test Instances

By analysing the information on emergencies in Shanghai [26], the mean value μj of demand dj in each emergency point are randomly generated from a discrete Uniform distribution on interval [5,25]. The standard deviation σj is set to be 5. Since the sampling approach proposed in Nickel et al. [8] requires a sample of scenarios, in numerical experiments scenarios are produced with demands randomly generated from Uniform distribution, Poisson distribution and Normal distribution consistent with given mean and standard deviation.According to the instance settings in Erkut and Ingolfsson (2008), response time from a base to an emergency point is randomly generated from a discrete Uniform distribution on interval[3,30] in units of minutes. A base covers an emergency point if the driving time between them is less than 10 minutes to ensure the survival probability (Erkut and Ingolfsson, 2006). For an emergency point in each instance, if there is no base with 10 minutes driving time to it, then the base covering this point is set to be the nearest one. The cost of constructing a base and that of locating one ambulance are both set to be 1, as in Nickel et al. [8]. Besides, the number of emergency points is 3 times that of potential base locations.


## 5.3.2. Results and Discussion

Different values of required service levelα are tested, i.e., 0.85, 0.9, 0.95. Computational results on 120 randomly generated instances are reported in Tables 4-6.Table 4
Computational results on instances with data generated from uniform distribution.
S e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) CT Obj Sel (%) 1 (2,6) 2.7 89 73.17 0.1 149 99.06 0.1 107 92.22 2.8 96 73.73 0.1 155 99.33 0.1 107 91.67 2.7 106 75.85 0.1 185 99.87 0.1 107 91.28 2 (4,12) 4.7 169 74.23 0.0 291 99.19 0.0 207 91.22 5.8 181 74.38 0.1 303 99.97 0.1 207 93.63 5.0 199 77.02 0.0 363 99.82 0.0 207 93.38 3 (6,18) 7.2 258 75.06 0.1 438 99.76 0.1 312 91.06 7.5 279 80.82 0.1 456 99.96 0.1 312 93.69 7.8 304 83.37 0.1 546 99.97 0.1 312 93.57 4 (8,24) 9.9 314 79.56 0.1 553 99.93 0.1 385 92.06 11.1 338 82.02 0.1 577 99.99 0.1 385 96.02 11.2 366 84.92 0.1 697 99.94 0.1 385 96.20 5 (10,30) 13.2 415 84.06 0.1 722 98.96 0.1 512 94.06 14.3 441 83.22 0.2 752 99.83 0.1 512 96.92 14.2 476 86.09 0.1 902 99.93 0.1 512 96.92 6 (12,36) 17.0 475 82.49 0.2 843 98.70 0.1 591 93.67 18.1 504 82.51 0.1 879 99.82 0.1 591 96.08 18.9 535 87.26 0.1 1059 99.97 0.1 591 96.09 7 (14,42) 21.5 573 81.11 0.2 1006 98.49 0.2 712 96.06 24.3 609 82.17 0.2 1048 99.53 0.2 712 95.89 23.3 644 86.08 0.2 1258 99.92 0.2 712 95.82 8 (16,48) 24.8 686 75.32 0.2 1185 98.96 0.2 849 97.25 28.4 727 83.07 0.2 1233 99.49 0.2 849 96.13 28.1 768 90.63 0.2 1473 99.99 0.3 849 96.22 9 (18,54) 31.3 691 83.53 0.3 1236 99.74 0.4 858 97.09 35.1 731 83.97 0.3 1290 99.88 0.3 858 97.65 35.2 760 89.06 0.3 1560 99.94 0.3 858 97.58 10 (20,60) 37.2 794 81.74 0.3 1409 98.87 0.3 989 96.57 42.8 843 84.89 0.3 1469 99.47 0.3 989 97.73 43.2 892 90.04 0.3 1769 99.97 0.3 989 97.38 11 (22,66) 45.1 830 80.72 0.4 1493 99.49 0.3 1031 97.58 51.8 880 83.28 0.4 1559 99.82 0.3 1031 97.23 51.6 930 89.67 0.5 1889 99.95 0.3 1031 97.27 12 (24,72) 54.3 1025 79.70 0.4 1771 99.27 0.4 1267 98.35 60.1 1083 84.82 0.5 1843 99.49 0.4 1267 97.76 63.7 1146 90.14 0.4 2203 99.93 0.4 1267 97.77 13 (26,78) 63.1 1026 81.42 0.5 1819 98.98 0.4 1274 97.82 74.3 1087 86.78 0.5 1897 99.36 0.4 1274 97.78 76.5 1146 90.23 0.4 2287 99.97 0.5 1273 98.37 14 (28,84) 78.2 1101 79.03 0.5 1949 98.69 0.8 1361 98.04 87.8 1165 87.90 0.5 2033 99.35 0.7 1361 98.89 87.0 1227 90.56 0.5 2453 99.98 0.6 1361 98.08 15 (30,90) 90.7 1091 80.98 0.6 1997 99.15 0.6 1367 96.29 101.8 1155 83.29 0.6 2087 99.81 0.6 1367 98.07 102.0 1225 89.86 0.6 2537 99.99 0.8 1367 98.17 16 (32,96) 106.2 1160 87.98 0.7 2123 99.44 0.7 1449 97.87 118.3 1229 83.83 0.7 2219 99.88 0.6 1449 98.49 119.3 1300 91.05 0.6 2698 99.98 0.6 1449 98.15 17 (34,102) 120.2 1298 75.72 0.7 2328 99.69 0.7 1614 98.21 137.7 1374 88.60 0.8 2430 99.97 0.7 1614 98.24 126.0 1452 90.85 0.7 2940 99.99 0.8 1614 98.18 18 (36,108) 139.4 1408 81.21 0.8 2509 99.47 0.8 1752 98.09 154.4 1492 89.28 0.8 2617 99.83 0.8 1752 97.99 154.8 1580 91.73 0.8 3156 99.99 0.8 1752 98.09 19 (38,114) 161.8 1508 81.70 0.9 2676 98.99 1.1 1877 97.42 176.0 1598 91.30 0.9 2790 99.34 0.8 1877 99.08 175.5 1688 91.86 0.9 3360 99.99 0.9 1877 98.72 20 (40,120) 220.6 1628 77.19 1.0 2869 99.89 1.0 2029 98.73 200.7 1732 87.53 1.1 2990 99.97 0.9 2029 98.79 190.4 1827 91.38 1.0 3590 99.98 0.9 2029 98.75 21 (42,126) 278.0 1622 83.54 1.0 2900 99.78 1.0 2017 97.32 260.9 1718 88.54 1.0 3026 98.76 1.0 2017 98.18 267.0 1812 90.89 1.2 3655 99.99 1.0 2017 98.48 22 (44,132) 318.9 1735 84.94 1.1 3088 99.85 1.5 2165 98.57 297.0 1840 89.22 1.2 3220 99.25 1.2 2165 98.86 287.3 1952 92.06 1.1 3880 99.99 1.1 2165 98.50 23 (46,138) 363.0 1937 81.41 1.2 3372 98.93 1.3 2406 97.96 322.2 2048 89.37 1.2 3510 99.34 1.4 2406 99.06 346.1 2170 89.89 1.2 4199 100.00 1.2 2406 98.09 24 (48,144) 422.6 1968 82.26 1.3 3461 99.32 1.3 2453 98.14 367.4 2085 88.46 1.3 3605 99.56 1.5 2453 99.12 355.6 2211 93.00 1.3 4326 99.99 1.3 2453 98.19 25 (50,150) 472.7 1919 81.11 1.4 3456 99.99 1.5 2407 96.29 401.9 2037 86.99 1.4 3606 99.99 1.4 2407 98.57 425.7 2161 92.59 1.5 4356 99.95 1.4 2407 98.19 26 (52,156) 530.0 1906 80.96 1.5 3484 98.78 1.7 2392 96.58 449.5 2021 89.52 1.4 3640 99.99 1.5 2392 95.68 448.6 2142 91.82 1.5 4420 99.99 1.5 2392 98.54 27 (54,162) 591.3 2096 83.87 1.6 3751 98.46 1.7 2617 97.61 511.7 2221 90.45 1.6 3913 99.98 1.7 2617 95.44 483.0 2355 93.46 1.8 4723 99.99 1.6 2617 98.93 28 (56,168) 631.0 2110 77.58 1.7 3819 99.33 1.9 2643 98.29 577.7 2234 91.57 1.8 3987 99.98 1.8 2643 95.26 555.0 2365 90.45 1.8 4827 99.99 1.7 2643 98.31 29 (58,174) 678.0 2175 79.98 1.8 3937 98.98 1.8 2720 97.14 630.3 2307 90.22 2.0 4111 99.69 1.9 2720 96.23 618.9 2444 91.28 1.9 4981 100.00 1.9 2720 99.14 30 (60,180) 759.3 2384 83.21 1.9 4240 99.67 2.0 2979 98.41 679.1 2527 89.78 1.9 4419 99.79 2.3 2979 97.21 687.8 2679 91.43 2.1 5316 99.99 2.0 2979 98.69 31 (62,186) 822.0 2281 76.04 2.0 4157 99.84 2.1 2856 97.96 773.4 2416 89.34 2.1 4343 99.97 2.1 2856 96.79 746.6 2557 91.58 2.2 5273 99.99 2.3 2856 99.02 32 (64,192) 876.6 2517 83.78 2.1 4489 99.32 2.5 3145 97.29 827.6 2671 82.96 2.3 4680 99.77 2.4 3145 98.25 789.7 2822 90.89 2.4 5640 99.99 2.2 3145 98.91 33 (66,198) 1012.3 2532 78.06 2.3 4555 99.67 2.3 3169 96.15 901.0 2682 89.47 2.4 4752 99.89 2.4 3169 97.03 905.1 2835 91.57 2.4 5742 99.98 2.4 3169 98.67 34 (68,204) 1101.0 2535 79.34 2.4 4602 99.99 2.9 3174 96.31 989.8 2685 88.58 3.0 4806 99.98 2.8 3174 97.62 986.3 2844 92.36 2.6 5824 99.99 2.5 3174 98.89 35 (70,210) 1166.6 2714 80.62 2.5 4862 99.86 2.9 3391 97.87 1066.6 2875 91.37 2.6 5072 99.99 2.9 3391 97.16 1082.2 3043 93.15 2.6 6122 99.99 2.9 3391 99.23 36 (72,216) 1201.1 2827 81.04 2.6 5047 99.91 2.8 3535 97.98 1246.5 2984 90.16 2.8 5263 99.99 2.8 3535 98.78 1166.7 3169 92.53 3.0 6343 99.99 2.9 3535 98.96 37 (74,222) 1143.7 2826 82.28 2.8 5096 99.33 2.9 3543 98.84 1358.2 3098 88.95 2.9 5318 99.99 3.2 3543 98.88 1265.4 3178 91.39 2.9 6427 100.00 3.1 3543 98.93 38 (76,228) 1243.5 2839 81.52 2.9 5161 98.97 2.9 3565 97.88 1397.6 3103 89.26 2.9 5388 99.99 3.1 3565 97.24 1383.7 3185 92.55 3.3 6528 100.00 3.1 3565 98.95 39 (78,234) 1464.3 2945 84.12 3.1 5331 99.98 3.2 3695 98.76 1479.4 3210 90.05 3.1 5565 99.99 3.4 3695 97.13 1456.1 3313 90.81 3.4 6735 100.00 3.3 3695 98.78 40 (80,240) 1604.2 2975 85.10 3.2 5414 99.57 3.6 3734 97.96 1626.3 3346 89.99 3.5 5654 99.99 3.5 3734 98.06 1586.9 3343 92.48 3.5 6854 100.00 3.5 3734 98.73  Average 448.2 1584.6 80.67 1.2 2839.7 99.36 1.3 1978.7 96.82 437.9 1691.3 86.54 1.3 2962.6 99.75 1.3 1978.7 97.21 429.5 1778.8 89.85 1.3 3577.4 99.97 1.3 1978.7 97.75Table4 reports the numerical results of instances with demand generated from Uniform distribution. We observe that when α=0.85,0.9,0.95, the average computational times of the sampling approach are 448.2, 437.9 and 429.5 seconds, respectively. However, both approximated MIP formulations can produce solutions in much faster speeds, i.e., within 1.3 seconds on average. With the increase of α, (i) the out-of-sample average service level is getting higher, and (ii) the system costs of solutions obtained by all method are getting larger, and (iii) the system costs of solutions yielded by MIP-DF2 is getting closer to those of solutions obtained by the sampling approach. In terms of the average system cost, the sampling approach performs the best, while MIP-DF1 is the poorest. When α=0.85, for example, the average system cost of MIP-DF2 and the sampling approach are about 30.32% and 44.2% less than that of MIP-DF1, respectively. When α=0.95, the above gaps are even larger. Concluding, for the Uniform distribution, (1) the proposed two approximated MIP formulations are far more time saving than the sampling approach, (2) MIP-DF1 and MIP-DF2 can improve the service level by about 19.07% compared with the sampling approach, however, (3) despite of the highest service levels obtained by MIP-DF1, the system cost obtained by MIP-DF1 is also high, (4) MIP-DF2 can ensure an appropriate service level with much less cost than MIP-DF1, and (5) for the situations with small-scale instances and high service level requirement, MIP-DF1 is recommended.Computational results of instances with demand at each emergency point generated from Poisson distribution are presented in Table5. For MIP-DF1 and MIP-DF2, only mean and variance are involved. Therefore, with given mean and standard deviation of the demand at each point, computational results are the same for different probability distributions. We can obtain from Table 5 that the objective value obtained by the sampling approach increases with the increase of α. Besides, when the value of α equals 0.85, the average service level obtained by the sampling approach is about 81.43%, which is smaller than that of the two approximated MIP formulations. The highest service level 99.34% is obtained by MIP-DF1, and that obtained by MIP-DF2 is 97.08%. When α=0.9, the average service level of the sampling approach is 84.37%, and those obtained by MIP-DF1 and MIP-DF2 are 99.85% and 97.97%, respectively. When α=0.95, the average service level obtained by the sampling approach is 93.56%, and those yielded by MIP-DF1 and MIP-DF2 are 99.97% and 97.81%, respectively. For Poisson distribution, concluding, MIP-DF1 and MIP-DF2 can improve the service level compared with the sampling approach, especially, MIP-DF1 can obtain the highest service level.Table 5
Computational results on instances with data generated from Poisson distribution.
s e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) 1 (2,6) 2.7 90 72.94 99.67 90.01 2.7 98 77.70 99.79 90.13 2.4 103 92.73 99.99 94.68 2 (4,12) 4.6 170 79.61 99.21 91.17 5.1 183 83.05 99.46 91.28 4.9 201 93.92 99.98 95.46 3 (6,18) 6.8 258 75.78 99.38 89.11 7.4 280 80.28 99.68 90.04 6.9 307 91.82 99.99 96.58 4 (8,24) 9.3 315 80.01 99.28 91.96 10.2 338 84.38 99.67 91.72 9.2 368 94.68 99.99 96.13 5 (10,30) 12.0 413 80.41 99.39 94.49 13.3 443 84.47 99.76 92.72 12.1 479 95.44 99.99 97.52 6 (12,36) 15.5 476 80.84 98.77 95.54 16.7 508 88.63 99.91 95.69 15.9 536 94.56 99.99 97.34 7 (14,42) 19.5 573 78.76 98.92 96.63 21.3 609 91.24 99.98 97.29 20.5 643 93.14 100.00 97.68 8 (16,48) 23.2 687 79.64 99.97 97.88 26.7 724 85.23 99.88 96.87 23.8 772 94.22 99.98 96.89 9 (18,54) 29.3 692 82.67 98.93 98.09 32.7 730 83.86 99.99 97.50 29.8 757 92.28 99.99 97.55 10 (20,60) 35.6 796 79.46 98.99 98.01 39.9 840 82.99 99.76 96.86 36.0 885 96.68 99.99 97.05 11 (22,66) 42.3 829 82.01 98.95 97.56 48.9 877 83.78 99.87 97.88 44.8 927 94.76 99.99 98.12 12 (24,72) 51.2 1023 83.38 99.13 98.53 55.4 1085 85.01 99.99 98.81 51.4 1148 93.98 99.99 98.88 13 (26,78) 59.2 1045 84.16 99.07 98.73 68.7 1088 79.98 99.96 98.02 60.7 1152 95.04 99.99 98.21 14 (28,84) 72.3 1099 79.46 99.15 97.88 83.8 1166 80.56 99.92 98.29 77.6 1230 95.46 99.99 98.39 15 (30,90) 85.5 1089 79.15 99.64 97.03 94.2 1156 84.32 99.84 97.78 90.3 1225 92.23 99.98 97.85 16 (32,96) 100.9 1158 80.24 98.97 97.69 116.3 1231 85.00 99.96 98.24 104.5 1222 91.99 99.99 98.35 17 (34,102) 116.5 1299 80.34 99.19 97.79 128.5 1375 84.95 99.37 98.08 119.0 1457 92.58 100.00 98.46 18 (36,108) 125.4 1411 81.76 99.43 98.85 147.9 1492 85.61 99.68 98.68 134.5 1579 92.86 99.99 98.75 19 (38,114) 150.4 1506 79.70 99.23 98.42 165.1 1594 81.67 99.72 98.46 156.4 1694 93.76 99.99 97.86 20 (40,120) 170.6 1635 78.19 99.16 97.83 185.4 1734 86.07 99.68 97.76 177.8 1825 92.85 99.04 97.18 21 (42,126) 205.4 1622 83.54 99.18 98.34 235.7 1720 82.97 99.78 98.33 222.6 1856 95.01 99.99 98.34 22 (44,132) 240.0 1736 84.94 99.22 98.46 285.2 1844 82.69 99.99 98.16 268.0 1946 94.86 99.99 98.20 23 (46,138) 265.1 1934 81.41 99.53 97.93 315.9 2049 84.92 99.69 97.99 307.2 2172 93.58 100.00 98.13 24 (48,144) 300.4 1961 82.26 99.47 96.81 352.2 2086 85.13 99.98 97.06 310.2 2209 94.88 99.99 97.24 25 (50,150) 330.8 1924 81.11 99.65 97.46 389.8 2038 82.64 99.99 97.88 363.9 2161 95.46 99.99 98.13 26 (52,156) 366.9 1911 80.96 99.39 98.55 430.5 2027 87.22 99.67 98.74 445.3 2142 91.85 99.99 98.76 27 (54,162) 441.8 2095 83.87 99.27 97.54 477.1 2219 83.41 99.89 97.49 480.6 2353 92.89 99.99 97.55 28 (56,168) 536.7 2113 84.58 99.68 98.48 535.6 2237 84.52 99.78 98.55 522.1 2369 92.28 100.00 98.68 29 (58,174) 621.7 2186 79.98 99.89 96.94 594.2 2315 83.16 99.96 96.99 585.3 2371 91.67 99.99 97.05 30 (60,180) 726.3 2382 83.21 99.91 98.37 652.7 2543 83.59 99.98 98.86 621.4 2678 93.69 99.97 98.86 31 (62,186) 821.4 2346 84.04 99.36 98.88 781.3 2430 83.21 99.99 98.46 687.6 2560 93.58 99.99 98.47 32 (64,192) 886.3 2518 83.78 99.38 98.07 810.6 2677 83.56 99.99 98.33 787.7 2822 94.08 100.00 98.35 33 (66,198) 998.5 2532 84.06 99.17 97.09 968.4 2689 84.97 99.96 97.46 808.8 2838 95.07 99.99 97.49 34 (68,204) 1126.4 2534 85.43 99.08 98.97 1098.6 2685 88.09 99.96 97.82 846.9 2843 88.44 99.98 97.80 35 (70,210) 1203.5 2715 82.58 99.37 97.99 1209.8 2886 85.69 99.91 98.09 994.6 3041 94.59 99.99 98.13 36 (72,216) 1280.3 2825 81.04 99.29 98.27 1307.6 3010 86.51 99.94 98.34 1101.3 3170 94.68 99.99 98.65 37 (74,222) 1302.1 2830 82.28 99.49 98.26 1326.1 3009 83.76 99.99 98.26 1201.4 3172 93.46 99.99 98.88 38 (76,228) 1386.2 2843 81.52 99.33 98.07 1399.5 3028 87.60 99.98 98.41 1213.3 3187 97.06 99.99 98.76 39 (78,234) 1538.7 2953 83.12 99.64 97.99 1482.7 3133 90.01 99.95 97.83 1338.1 3304 89.13 99.99 97.99 40 (80,240) 1697.4 2975 85.10 99.85 97.67 1525.6 3249 82.17 99.93 97.81 1586.7 3347 91.11 99.99 97.91  Average 435.2 1587.5 81.43 99.34 97.08 436.2 1685.6 84.37 99.85 97.07 396.8 1776.3 93.56 99.97 97.81Table 6
Computational results on instances with data generated from normal distribution.
s e t I , J α = 0.85 α = 0.9 α = 0.95 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 Sampling approach MIP-DF1 MIP-DF2 CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) CT Obj Sel (%) Sel (%) Sel (%) 1 (2,6) 2.7 90 72.94 99.64 91.17 2.7 94 78.44 99.70 92.02 2.558 106 84.22 100.00 92.08 2 (4,12) 4.6 170 79.61 99.21 92.83 4.8 183 83.28 99.82 92.83 4.508 183 88.23 100.00 93.70 3 (6,18) 6.8 258 75.78 99.16 92.28 6.8 280 77.98 99.71 94.17 6.803 307 76.58 99.98 94.47 4 (8,24) 9.3 315 80.00 98.99 93.67 9.6 337 83.79 99.79 94.67 9.373 368 84.38 99.99 95.79 5 (10,30) 12.0 413 78.41 99.27 94.37 12.4 443 87.63 99.63 94.76 12.62 499 88.50 99.98 97.08 6 (12,36) 15.5 476 79.21 99.19 95.19 16.2 504 81.24 99.82 95.82 16.021 536 89.54 100.00 97.56 7 (14,42) 19.5 573 79.76 99.33 95.98 19.6 609 82.87 99.75 96.19 20.11 646 84.67 99.99 97.67 8 (16,48) 23.2 687 80.31 99.18 97.05 23.5 727 81.15 99.65 96.50 24.04 772 82.78 99.99 97.65 9 (18,54) 29.3 692 80.86 98.98 97.59 29.1 734 84.64 99.74 97.55 29.815 796 86.17 99.98 98.35 10 (20,60) 35.6 796 79.84 99.37 97.70 35.8 842 82.23 99.88 97.65 37.973 921 88.46 100.00 98.38 11 (22,66) 42.1 829 81.01 99.40 97.55 43.6 877 82.11 99.86 97.86 45.148 959 84.97 99.99 97.89 12 (24,72) 51.4 1023 80.33 99.51 97.85 50.1 1085 81.62 99.83 97.88 52.073 1147 83.21 99.99 98.24 13 (26,78) 59.2 1023 81.38 99.16 98.85 59.9 1087 84.11 99.70 98.45 62.937 1194 86.09 99.98 97.95 14 (28,84) 72.8 1099 82.35 99.13 99.15 72.2 1168 84.35 99.87 98.06 75.053 1270 85.67 99.97 98.34 15 (30,90) 85.5 1089 81.87 99.22 98.61 88.0 1157 83.76 99.76 97.96 89.222 1300 86.11 99.96 97.98 16 (32,96) 100.9 1158 87.70 98.97 97.88 96.6 1231 88.45 99.84 98.23 106.288 1359 89.97 99.99 98.48 17 (34,102) 115.4 1299 84.34 99.25 98.49 113.7 1377 86.01 99.80 97.98 123.869 1493 87.98 99.96 98.77 18 (36,108) 140.7 1411 83.21 99.27 98.66 133.9 1495 83.01 99.65 98.22 133.807 1601 85.67 99.99 98.34 19 (38,114) 170.2 1506 82.06 99.15 98.05 167.2 1598 89.77 99.78 98.45 152.999 1694 89.98 99.99 98.47 20 (40,120) 209.1 1635 85.28 99.18 98.89 191.6 1737 88.05 99.76 98.37 189.002 1833 90.12 99.99 97.91 21 (42,126) 284.3 1622 85.50 99.34 99.13 243.2 1718 88.86 99.74 98.13 239.913 1815 90.08 100.00 98.15 22 (44,132) 330.0 1736 84.49 99.40 98.59 279.5 1843 87.86 99.77 97.56 253.106 1948 89.97 99.99 98.26 23 (46,138) 374.1 1934 81.33 99.11 98.76 314.3 2050 88.76 99.81 97.85 274.583 2173 90.14 99.99 98.58 24 (48,144) 453.1 1961 82.45 99.09 98.46 351.5 2090 83.44 99.93 98.19 308.089 2211 86.61 99.99 98.83 25 (50,150) 471.5 1924 81.11 99.29 98.88 395.9 2041 82.79 99.96 98.37 351.093 2158 85.27 99.99 98.27 26 (52,156) 522.3 1911 80.96 98.98 98.57 430.1 2025 82.51 99.97 97.57 421.747 2146 84.97 99.99 99.14 27 (54,162) 599.4 2095 83.87 99.08 97.75 483.5 2226 84.97 99.74 97.80 461.443 2359 86.95 99.99 98.37 28 (56,168) 640.6 2111 84.11 99.06 97.98 533.6 2240 85.58 99.91 98.20 494.113 2371 92.49 99.99 98.16 29 (58,174) 689.7 2176 80.12 99.16 97.91 594.8 2311 82.11 99.84 97.65 624.835 2445 85.31 100.00 98.51 30 (60,180) 743.6 2391 81.11 99.13 97.66 655.8 2533 83.05 99.68 97.95 696.116 2682 85.75 99.99 97.99 31 (62,186) 811.8 2282 81.19 99.28 98.06 706.9 2422 84.17 99.73 98.73 797.768 2564 86.67 99.99 98.46 32 (64,192) 889.5 2519 82.23 99.19 97.57 785.7 2675 86.31 99.82 97.69 864.813 2827 89.76 100.00 99.05 33 (66,198) 1123.5 2533 85.63 99.28 98.11 916.2 2688 85.47 99.79 98.28 973.089 2843 86.57 99.99 98.46 34 (68,204) 1158.7 2534 82.49 99.26 98.47 954.9 2686 87.98 99.38 98.56 1052.3 3041 89.99 100.00 98.77 35 (70,210) 1164.9 2715 80.98 98.95 98.72 1034.5 2880 86.02 99.98 98.69 1127.2 3052 90.21 99.99 98.97 36 (72,216) 1222.4 2825 84.03 99.58 97.70 1116.5 3002 86.57 99.99 98.39 1245.6 3175 91.13 99.99 98.64 37 (74,222) 1297.8 2830 83.57 99.37 97.95 1185.0 3005 84.96 99.98 98.94 1345.8 3176 88.27 99.99 99.05 38 (76,228) 1342.6 2844 82.67 99.66 97.59 1279.5 3019 86.04 99.99 97.97 1515.5 3121 89.78 99.99 98.53 39 (78,234) 1500.3 2955 83.03 99.56 98.67 1381.6 3132 85.88 99.96 98.85 1504.1 3310 90.16 99.99 99.12 40 (80,240) 1649.5 2978 82.57 99.54 98.26 1489.6 3160 84.95 99.97 98.37 1656.3 3349 89.57 99.99 99.33  Average 461.9 1585.5 81.74 99.25 97.42 407.7 1682.8 84.57 99.81 97.43 435.0 1793.8 87.32 99.99 97.94Similarly, Table6 reports the computational results for instances in which the demand at each emergency point is generated following Normal distribution. When α=0.85, the average service levels obtained by the sampling approach, MIP-DF1 and MIP-DF2 are 81.74%, 99.25%, and 97.42%, respectively. When α=0.9, the three values are 84.57%, 99.81%, and 97.43% respectively. Moreover, for α=0.95, the values are equal to 87.32%, 99.99%, and 97.94%, respectively. It can be observed that the performance of the sampling approach is the poorest in terms of the service level.By observing the above computational results on benchmarks and randomly generated instances, we conclude that(1) The proposed approximated MIP formulations, i.e., MIP-DF1 and MIP-DF2 are very time saving compared with the sampling approach; (2) MIP-DF1 an MIP-DF2 can achieve the requirement of service level and improve the service level by about 15.47% and 12.29% on average, compared with that of the sampling approach; (3) MIP-DF1 is more conservative in terms of overhigh emergency service level close to 100%, and the system cost is also high, which is about 56.8% larger than that of MIP-DF2; (4) Compared with MIP-DF1, MIP-DF2 is less conservative and much more cost saving while ensuring an appropriately service level on average, which is about 97%.In sum, for medium and large problem instances (e.g., Shanghai), which are common in practice, to guarantee the required service level with less cost, we recommend MIP-DF2 as solution method. However, for very small instances with high service level requirement, we recommend MIP-DF1 for solutions.


## 6. Conclusion

This paper investigates an ambulance location problem with ambiguity set of demand, in which the probability distribution of the uncertain demand is unknown. In such a data-driven environment, only the mean and covariance demands at emergency points are known. The problem is to determine the base locations and the number of ambulances at each base, aiming at minimizing the total cost associated with locating bases and assigning ambulances. We propose a distribution-free model with chance constraints. Then two approximated MIP formulations with different approximation methods of chance constraints are proposed, which are based on different ambiguity sets of the unknown probability distribution. Numerical experiments on benchmarks and 120 randomly generated instances are conducted, and the computational results show that the first approximated MIP formulation is much conservative with overhigh system cost, while the second approximated MIP formulation is more cost saving with service level appropriately ensured.In future research, we may consider the following relevant issues. First, the uncertainty of driving time from a base to an emergency point shall be analysed. Besides, unexpected or sudden disasters may be taken into consideration. Moreover, other uncertainties should be considered, such as travel time, the number of available vehicles and so on. The stochastic dependence should also further considered.



---

*Source: 9364129-2018-09-13.xml*