A novel probabilistic formulation for locating and sizing emergency medical service stations

Abstract

The paper proposes a novel probabilistic model with chance constraints for locating and sizing emergency medical service stations. In this model, the chance constraints are approximated as second-order cone constraints to overcome computational difficulties for practical applications. The proposed approximations associated with different estimation accuracy of the stochastic nature are meaningful on a practical uncertainty environment. Then, the model is transformed into a conic quadratic mixed-integer program by employing a conic transformation. The resulting model can be efficiently addressed by a commercial optimization package. A special case is also considered and a class of valid inequalities is introduced to improve computational efficiency. Lastly, computational experiences on real data and randomly generated data are reported to illustrate the validity of the program.

1 Introduction

Designing an effective and optimal emergency medical service (EMS) system is of extreme importance for metropolitan areas in most countries since such a system could save more lives and improve the satisfaction level without increasing the burden of the tax payers. However, it has never been a trivial process to design a good EMS system, especially for large cities. It requires determination of the locations of emergency facilities (EMS stations) and the number of emergency vehicles (ambulances) to allocate to each facility under a limited budget and perplexing facility conditions.

The present research is motivated by a real-world application, designing the EMS of the metropolitan of Beijing, China. The existing EMS system in Beijing is not able to provide high-quality services due to the fast growing population and quick changes in the geometric distribution of the population. In order to satisfy the growing demand for emergency medical service with the limited budget, the existing system has to be reconfigured with the consideration of EMS stations and demand sites.

Two major approaches have been proposed to solve the EMS design problem under demand uncertainty. One is the queueing model-based approach, the other is the stochastic programming-based approach (Essen et al. 2013). However, the computational complexity of these approaches limits their applications (Snyder 2006; Beraldi and Bruni 2009).

In this work, we study an EMS design problem under demand uncertainty and propose a novel formulation to overcome the limitation. We firstly formulate the EMS design problem as a probabilistic model with chance constraints. The concept of maximum number of concurrent demands (MNCD) is introduced to estimate the number of emergency vehicles at each station. We then derive closed-form approximations of the chance constraints that are valid for three families of probability distributions. Such approximations allow the nonconvex chance constraints to be converted into convex second-order cone constraints and thus make the problem computationally tractable.

The major contributions of our work are listed as follows. (1) A novel method is proposed to approximate the chance constraints into a class of second-order cone constraints characterized by the mean and variance of MNCDs. In doing that, we can apply the mean and covariance of random variables, which can be obtained through statistical processing, to construct the approximation and avoid identification of scenarios, which is extensively used to linearize noncovex chance constraints (Snyder 2006). After using the conic transformation, the resulting model can be solved efficiently by commercial optimization packages. (2) We provide managerial insights for designing an emergency medical service system through a case study.

The remainder of the paper is organized as follows. Section 2 provides a literature review on the EMS design. In Sect. 3, our EMS design problem is presented and formulated as a probabilistic model with chance constraints. In Sect. 4, the probabilistic model is converted to a conic quadratic program which can be efficiently solved. Section 5 considers a special case of the program. Section 6 reports the computational experiences on real data and randomly generated data. Managerial insights are explored as well. We conclude this study in Sect. 7.

2 Literature review

Numerous investigation efforts have been devoted to the EMS design problems (Marianov and ReVelle 1995; Brotcorne et al. 2003; Coskun and Erol 2010; Li et al. 2011; Aringhieri et al. 2013; Kou and Wu 2014). Early studies treated the EMS design as a deterministic problem with the assumption that the emergency demands were known in advance. Yet, this assumption is unlikely to be realistic. The emergency demands and the busy fraction of the emergency vehicles usually vary with location and time. Since 1980s, the inherent probabilistic feature of EMS, such as stochastic demands, has therefore received increasing attention and many probabilistic models have been developed in order to capturing this feature (Aly and White 1978; Daskin 1983; ReVelle and Hogan 1989; Marianov and ReVelle 1996).

There are two major approaches used in these studies for solving the EMS design problems under demand uncertainty. The first approach relies on the queueing model (Silva and Serra 2007; Takeda et al. 2007; McLay 2009; Geroliminis et al. 2009; Iannoni et al. 2010; Chanta et al. 2011) for evaluating the performance measures of the EMS system. The second approach uses the stochastic programming paradigm. This approach often incorporates the chance constraints in the formulation (Beraldi et al. 2004; Jia et al. 2007; Beraldi and Bruni 2009; Noyan 2010; Murali et al. 2012; Lejeune 2013; Ozbay et al. 2013; Hong et al. 2014), and provides probabilistic guarantees to a solution satisfying a given constraint (see the review by ReVelle (1989)).

The most well-known queuing models for EMS location problems are the hypercube and approximated hypercube models. Galvão and Morabito (2008) presented a comprehensive literature review on the use of the hypercube queueing model for the EMS design. The hypercube and approximated hypercube models were developed based on the spatially distributed queueing theory and Markovian analysis approximations (Iannoni et al. 2009). It has been shown that they are effective for planning server-to-customer systems. Iannoni et al. (2008) further incorporateed the hypercube model into a genetic algorithm for analyzing EMS on highways involving partial backup and multiple dispatching of ambulances. Rajagopalan and Saydam (2009) implemented the hypercube model to calculate the busy probabilities of EMS stations and developed a heuristic search algorithm to solve a minimum expected response location problem (MERLP). The model was applied to a real application from Mecklenburg County (Greater Charlotte), North Carolina and promising results were obtained. Geroliminis et al. (2011) integrated the hypercube model into a location model and deployed emergency response units in a real case. A genetic algorithm-based two-step approach was developed to solve the resulting model. Baptista and Oliveira (2012) applied the approximated hypercube model to assess alternative dispatching rules in operating Lisbon emergency medical services. Toro-Díaz et al. (2013) developed a mathematical formulation that combined an integer programming model representing location and dispatching decisions, with a hypercube model representing the queuing elements and congestion phenomena. Davoudpour et al. (2014) introduced a new probabilistic coverage model, which uses the ideas of the maximum expected covering location problem including the availability probability of queuing model and the average requests arrival of Poisson process, and mixed them with the hypercube queuing model. Although the idea of embedding the hypercube queueing model into probabilistic models is to make them more adherent to the real world (Galvão and Morabito 2008), the resulting formulations are usually solved by metaheursitc algorithms due to the computational complexity (Beraldi and Bruni 2009; Rajagopalan and Saydam 2009).

For the second approach, the major advantage of the chance constrained programming technique lies in that its deterministic equivalent problem has a limited program size even if the number of uncertain parameters can be large. Since the nonconvexity of chance-constrained problems always causes computational difficulties, these studies usually convert chance constraints into linear deterministic equivalents. For example, Beraldi and Bruni (2009) used a joint chance constraint to ensure that the probability of total emergency demands in a predetermined period less than the number of emergency vehicles at each demand site under each scenario must be larger than a reliability level. They created a deterministic equivalent scenario-based counterpart and applied the big-M method to solve the problem.

Noyan (2010) further introduced integrated chance constraints (ICCs) (Haneveld and Vlerk 2006) into EMS system design. The ICCs proposed firstly by Klein Haneveld (1986) were considered as relaxations of chance constraints and defined as expectation type constraints using maximal penalty functions. Given a scenario set and the corresponding probabilities, the expectations were expressed to deterministic equivalent formulations. Then convex approximations of the generally non-convex feasible sets defined by chance constraints were obtained. However, this scenario based approach has the two major drawbacks (Snyder 2006). One is the difficulty to identify scenarios. The other is that only a small number of scenarios can be identified due to computational cost, which limits the range of future states for decision making.

Recently, chance constraints have been extensively used in general location-allocation research. Murali et al. (2012) formulated a facility location problem to determine the medicine distribution points in a large city and used chance constraints to address the demand uncertainty. A locate-allocate heuristic was developed to solve the nonconvex program. Lejeune (2013) investigated multi-period service level policies for stochastic demands, which was applied in an opening problem of emergency operations centers. These service levels were formulated as chance constraints that can be linearized with system of inequalities. Then, the reformulated linear program can be solved by CPELX. Ozbay et al. (2013) proposed mathematical programming models with chance constraints in order to address incident response and resource allocation problem. An enumeration algorithm proposed by Prekopa et al. (1998) was applied to solve the nonlinear problem. Hong et al. (2014) proposed a risk-averse stochastic modeling approach for a pre-disaster relief network design problem under uncertain demand and transportation capacities. A chance constraint on the existence of a feasible flow was introduced to ensure that the demand for relief supplies across the network is satisfied with a specified high probability.

3 Problem statement and formulation

We consider an EMS network, which consists of multi candidate EMS stations and multi demand sites. In this network, the EMS stations provide emergency services for the corresponding demand sites once occurring emergency demands such as traffic accidents and emergent diseases. The demand at each site is uncertain and its mean, variance and covariance are known in advance. Emergency vehicles at an EMS station have to arrive at the demand sites that are serviced by this EMS station within a given time. We propose a model to determine the location of EMS stations and the number of emergency vehicles at each EMS station to minimize the expected total cost.

The following notations are used throughout this paper in order to simply the description.

Parameters

$I$ :

set of demand sites, indexed by $i$

$J$ :

set of candidate EMS stations, indexed by $j$

$I_j$ :

set of demand sites that can be covered by EMS station $j$, i.e., $I_j=\{i\in I|c_{ij}\le T\}$

$J_i$ :

set of candidate EMS stations that can cover demand site $i$, i.e., $J_i=\{j\in J|c_{ij}\le T\}$

$T$ :

the maximal time length required for the service trip

$f_j$ :

(daily) construction cost at EMS station $j$

$a_j$ :

(daily) maintain and purchase costs of per emergency vehicle at EMS station $j$

$c_{ij}$ :

distance between demand site $i$ and EMS station $j$

$\beta$ :

unit transportation cost

$\eta _i$ :

(daily) mean of demand at demand site $i$

$d_i$ :

maximum number of concurrent demands (MNCD) occurred at demand site $i$ with mean of $\mu _i$ and variance of $\sigma _i^2$

$\alpha$ :

service level at each EMS station

$M$ :

a large enough positive number

Decision variables

$X_{ij}$ :

percentage of demand at demand site $i$ served by EMS station $j$

$Y_j$ :

1, if a EMS station is constructed at candidate EMS station $j$; 0, otherwise

$N_j$ :

number of emergency vehicles at EMS station $j$

For each EMS station, an individual chance constraint is expressed as follows:

$$\begin{aligned} \fancyscript{P}\left( \sum _{i\in I_j}d_i X_{ij}\le N_j\right) \ge \alpha . \end{aligned}$$

This constraint suggests that the probability that the sum of the maximum number of concurrent demands (MNCDs) occurred at all the demand sites ($d_i$) assigned to EMS station $j$ is no more than the number of emergency vehicles is larger than a predetermined service level.

Note that although the individual chance constraints introduced above do not ensure to attain a service level for the entire geographical area (Beraldi et al. 2004; Beraldi and Bruni 2009), these constraints are still adopted due to their easy manageability for each site since we can apply a performance indicator decomposition procedure to decompose a service level for the entire geographical area into a service level for each EMS station, and determine an identical service level for each individual site exogenously so as to ensure high-quality services.

Given the above constraints and notations, we formulate the EMS design problem as a probabilistic model with the chance constraints as follows:

$$\begin{aligned}&\fancyscript{M}:min \sum _{j\in J} f_j Y_j+\sum _{j\in J}a_j N_j+\sum _{j\in J}\sum _{i\in I}\beta c_{ij}\eta _i X_{ij},\end{aligned}$$

(1)

$$\begin{aligned}&\quad s.t.\sum _{j\in J_i}X_{ij}= 1,\quad \forall i\in I,\end{aligned}$$

(2)

$$\begin{aligned}&\qquad X_{ij}\le Y_j,\quad \forall i\in I,\quad j\in J,\end{aligned}$$

(3)

$$\begin{aligned}&\qquad N_j\le M Y_j,\quad \forall j\in J,\end{aligned}$$

(4)

$$\begin{aligned}&\qquad \fancyscript{P}\left( \sum _{i\in I_j}d_i X_{ij}\le N_j\right) \ge \alpha ,\quad \forall j\in J, \end{aligned}$$

(5)

$$\begin{aligned} 0\le X_{ij}\le 1,\quad \forall i\in I, j\in J, \end{aligned}$$

(6)

$$\begin{aligned} Y_j\in \{0,1\},\quad \forall j\in J, \end{aligned}$$

(7)

$$\begin{aligned} N_j\in Z_+,\quad \forall j\in J. \end{aligned}$$

(8)

This model minimizes the expected total cost, which is the sum of fixed costs of constructing EMS stations (daily amortization of the cost of establishing the EMS station), maintenance, and purchasing costs of emergency vehicles as well as the expected transportation costs between EMS stations and corresponding demand areas. Constraint (2) requires that the demand of each site is completely assigned to the associated EMS stations. Constraints (3) and (4) imply that demand sites and emergency vehicles can only be assigned to open EMS station, respectively. Constraint (5) is the chance constraints, which has been described above. Constraint (6) represents the range of $X_{ij}$. Constraints (7) and (8) are standard binary and integral constraints.

4 Reformulation

It is intractable to solve the proposed program due to the non-convexity of chance constraints (5) (Haneveld and Vlerk 2006). Traditionally, these constraints were linearized using scenario based approaches (Haneveld and Vlerk 2006; Beraldi and Bruni 2009; Noyan 2010). However, the drawbacks of the scenario based approach limit its applications in the network design (Snyder 2006).

Approximation methods for linearizing chance constraints have increasingly attracted attentions in other application fields such as network design (Baron et al. 2011) and portfolio optimization (Bonami and Lejeune 2009). Bonami and Lejeune (2009) studied a probabilistic constraint that is expressed as:

$$\begin{aligned} \fancyscript{P}\left( \xi ^TX\ge R\right) \ge \alpha , \end{aligned}$$

in which the coefficients $\xi$ multiplying the decision variable $X$ are stochastic and not (necessarily) independent, guarantees that the expectation of $\xi ^TX$ is above the prescribed minimal level of return $R$ with a high probability $\alpha$. If random variable $\xi$ follows symmetric or positively skewed probability distributions and $\alpha \in [0.5, 1)$, then a class of convex approximation was derived, which is expressed as

$$\begin{aligned} \mu ^TX+F^{-1}(1-\alpha )\parallel \varSigma ^{\frac{1}{2}}X\parallel _2\ge R. \end{aligned}$$

in which $F^{-1}(1-\alpha )$ is the $(1-\alpha )$-quantile of $F$ which is cumulative probability distribution of normalized $\xi ^TX$, $\varSigma$ is variance-covariance matrix of $\xi$. The approximation has been widely used in the robust optimization methodology (Ben-Tal et al. 2009) and differs in terms of their conservativeness.

Inspired by these approximation methods, we propose a novel approach to approximate chance constraints (5) to a second-order convex cone constraints without the assumption of independence of MNCDs as describe blow.

Theorem 1

Let $D_j=\sum _{i\in I}d_iX_{ij}$. The chance constraint

$$\begin{aligned} \fancyscript{P}(D_j\le N_j)\ge \alpha , \end{aligned}$$

(9)

can be approximated as the following second-order cone constraint

$$\begin{aligned} \mu ^T \bar{X}_j+\hat{\alpha }\parallel \varSigma _j^{\frac{1}{2}} \bar{X}_j\parallel _2\le N_j, \end{aligned}$$

(10)

where, $\bar{X}_j=(X_{1j}, X_{2j}, \cdots , X_{nj})^T$, $\mu =(\mu _1,\mu _2,\cdots ,\mu _n)^T$, $\mu _i=E[d_i]$, $n=|I|$, $\varSigma _j$ is variance-covariance matrix of $D_j$, and

$$\begin{aligned} \hat{\alpha }=\left\{ \begin{array}{ll} \sqrt{\frac{\alpha }{1-\alpha }},&{} \text{ if } d_i \text{ is } \text{ a } \text{ arbitray } \text{ random } \text{ variable, }\\ \sqrt{\frac{1}{2(1-\alpha )}},&{} \text{ if } d_i \text{ is } \text{ a } \text{ symmetric } \text{ random } \text{ variable, } \alpha \in [0.5, 1)\\ \sqrt{\frac{2}{9(1-\alpha )}},&{} \text{ if } d_i \text{ is } \text{ a } \text{ unimodal } \text{ symmetric } \text{ random } \text{ variable, } \alpha \in [0.5, 1)\text{. } \end{array} \right. \end{aligned}$$

Proof

See Appendix 8. $\square$

In comparison with the work of Bonami and Lejeune (2009), we propose a second-order convex approximation for a different type of probability constraint. Moreover, the proposed approximation can be applied to three types of random variables, which follow arbitrary, symmetric and unimodal symmetric probability distributions, respectively. To the best of our knowledge, it is the first study which applies this type of constraints to design an EMS system.

Substitute constraint (5) with constraint (10), the resulting model is a conic quadratic mixed-integer program (CQMIP), which is defined as follows:

Definition 1

A conic quadratic mixed-integer program (CQMIP) is an optimization problem of the form:

$$\begin{aligned}&min c'x\\&s.t. \parallel A_{i}x+ b_{i}\parallel _2 \ \le \ d_{i}'x+e_{i},\,\,\,\,\,\,i=1,\ldots ,p, \end{aligned}$$

where $x \in \mathbb {Z}^{n}\times \mathbb {R}^{m}$, $A_i\in R^{n_i\times (n+m)}$, $\parallel \cdot \parallel _2$ is the Euclidean norm, and all parameters are rational.

The type of the program can be solved efficiently by branch-and-cut method in commercial optimization package.

Note that

Remark 1

Constraint (4) is redundant because inequality (10) guarantees that $X_{ij}\le N_j$.

Remark 2

Constraint (2) ensures that $X_{ij}\le 1$.

And, employing a conic transformation to linearize inequality (10), we further reformulate the model as follows:

$$\begin{aligned}&\fancyscript{M}^a:min \sum _{j\in J} f_j Y_j+\sum _{j\in J}a_j N_j+\sum _{j\in J}\sum _{i\in I}\beta c_{ij}\eta _i X_{ij},\end{aligned}$$

(11)

$$\begin{aligned}&\quad s.t.\sum _{j\in J_i}X_{ij}= 1,\quad \forall i\in I,\end{aligned}$$

(12)

$$\begin{aligned}&\qquad X_{ij}\le Y_j,\quad \forall i\in I,\quad j\in J,\end{aligned}$$

(13)

$$\begin{aligned}&\qquad \mu ^T \bar{X}_j+\hat{\alpha }W_j\le N_j,\quad \forall j\in J, \end{aligned}$$

(14)

$$\begin{aligned} W_j\ge \parallel \varSigma _j^{\frac{1}{2}}\bar{X}_j\parallel _2,\quad \forall j\in J, \end{aligned}$$

(15)

$$\begin{aligned} Y_j\in \{0,1\},\quad \forall i\in I, j\in J, \end{aligned}$$

(16)

$$\begin{aligned} N_j\in Z_+,\quad \forall j\in J, \end{aligned}$$

(17)

$$\begin{aligned} X_{ij},W_j\in R_+,\quad \forall j\in J. \end{aligned}$$

(18)

where $W_j$ is an auxiliary variable.

We illustrate a potential advantage of the proposed method by comparing our model with the model proposed by Beraldi et al. (2004). In which, the following chance constraints are mentioned.

$$\begin{aligned} \fancyscript{P}\left( \sum _{j\in J_i}n_{ij}\ge d_i\right) \ge \alpha ,\quad \forall i\in I, \end{aligned}$$

(19)

where $n_{ij}$ denotes the number of emergency vehicles located at $j$ that are used to cover the service requests at the demand site $i$. Constraint (19) ignores the correlation among the demand sites. According to Theorem 1, the chance constraint (19) is approximated as:

$$\begin{aligned} \mu _i+\hat{\alpha }\sigma _i\le \sum _{j\in J_i}n_{ij},\quad \forall i\in I. \end{aligned}$$

(20)

Then, we derive the following property and the benefit of capacity pooling is illustrated.

Property 1

In comparison to the model with chance constraint (20), $\fancyscript{M}^a$ estimates less number of emergency vehicles used in a station.

Proof

See Appendix 9. $\square$

It implies that at a given service level the higher utilization of the emergency vehicles at each station can be achieved due to the value of pooling capacity (Jain 2007) and therefore the cost can be reduced.

5 A special case

In practical applications, the following two assumptions are often made (Beraldi and Bruni 2009; Toro-Díaz et al. 2013):

• one demand site can only be served by one EMS station;

• the MNCDs among the demand sites are independent.

Therefore, $X_{ij}$ is redefined as a binary variable: 1, if demand site $i$ is served by EMS station $j$; 0 otherwise. The problem becomes more complicated because more binary variables are presented. We introduce a class of valid inequality to speed up the solution process.

Constraint (15) is rewritten:

$$\begin{aligned}&W_j\ge \sqrt{\sum _{i\in I}\sigma _{i}^2X_{ij}^2},\quad \forall j\in J, \end{aligned}$$

(21)

Property 2

The RHS of Constraint (21) is a submodular function.

Proof

Refer to Atamtürk and Narayanan (2008). $\square$

For this kind of submodular function, a class of valid inequality can be added to the model for improving the computational efficiency.

Theorem 2

Define $\fancyscript{Q}_f$ as the lower convex envelope of the sets of solutions which Constraints (21) are hold, i.e.,

$$\begin{aligned} \fancyscript{Q}_f=conv\left\{ W_j\in R: W_j\ge \sqrt{\sum _{i\in I}\sigma _{i}^2X_{ij}^2}\right\} . \end{aligned}$$

Then, the inequality $\sum _{i\in I}\pi _i X_{ij}\le W_j$ is valid for $\fancyscript{Q}_j$, where $\pi _i=\sqrt{\sum _{i\in S_{(i)}}\sigma _i^2}-\sqrt{\sum _{i\in S_{(i-1)}}\sigma _i^2}$, $S=\{i|X_{ij}=1\}$ and $S_{(i)}=\{(1), (2), \cdots , (i)\}, 1\le i\le |I|$ for some permutation.

Proof

Note $X_{ij}^2=X_{ij}$ and define $g(S)=\sqrt{\sigma (S)}$, where $\sigma (S)=\sum _{i\in S}\sigma _i^2$. Since it is a submodular function, $\pi _i=\sqrt{\sigma (S_{(i)})}-\sqrt{\sigma (S_{(i-1)})}$ is an extreme point of the polyhedron associated with the submodular function $g$ (Edmonds 1970). The polyhedron is named as extended polymatriod ($EP_g$) (Schrijver 2003) and is defined as:

$$\begin{aligned} EP_g:=\left\{ \pi \in R^N|\pi (S)\le g(S)\right\} . \end{aligned}$$

Therefore, $\pi (S)\le g(S)\le W_j$. $\square$

The separation problem for the inequality can be computed by a greedy algorithm described in Wolsey and Nemhauser (1999) and Atamtürk and Narayanan (2008). Then, the valid inequality is added to the root node of the branch and bound tree.

6 Computational experiences

We report the computational experience in this section in order to assess and validate our model. We code the model using CPLEX12.1 and the experiments are carried on SUN Fire X4600 server with Solaris 10 X86-64 OS. The MIQCP solver of CPLEX 12.1, which solves CQMIP relaxations at the nodes of the branch-and-bound tree, was used to solve the model.

6.1 Design of computational experiments

Two types of test data are used to test the performance of our algorithm.

Firstly, we apply the proposed model to several problem instances which come from a real application of designing the EMS of the metropolitan of Beijing, China. We assume that each site is a demand site as well as a candidate EMS station. Note that all of the data used in the instances was collected empirically. The detailed records of vehicle dispatching history in 2005 were used including the request time, site, phone number etc. Three datasets with the number of candidate EMS stations 30, 50, 69 were considered in the computational experiments. The 30-dataset and 50-dataset were subsets of the 69-dataset generated by taking first 30 and 50 data points from the 69-dataset.

Secondly, test data are generated randomly to evaluate the efficiency of the approach for large scale instances.

The parameters used in the model were determined as follows.

• The cost-related parameters were determined empirically. We assume that fixed asset investment will be depreciated straight-line to zero over ten years. Consequently, the (daily) construction cost at EMS stations was 50. The (daily) maintaining and purchasing costs of an emergency vehicle was 2. The service level ($\alpha$) is {95, 96, 97, 98, 99 %} and the unit transportation cost ($\beta$) is set to {1, 2, 5, 10, 20, 50}. For the demand realization, it is generated based on the historical data of emergency calls. We made statistical processing to make the data available for our model. We use the mean daily number of emergency calls to represent the mean of demand ($\eta$) at the corresponding demand site. According to the national standard, the coverage distance threshold of an EMS station is ranged from 3$\sim$15 km in center area and 10$\sim$50 km in urban fringe area. We set $c_{ij}$ to be the distance between EMS station $j$ and demand site $i$ if the current serving area of demand $i$ is also within the coverage distance of EMS station $j$. And we replace the unavailable value in the distance matrix with a large enough positive number ($M$).

• To calculate MNCD, we assume that the average time of an emergency task is one hour. It is a reasonable time required for the service trip according to the national standard. The assumption is also applied in Beraldi et al. (2004) and Noyan (2010). At a demand site, suppose the first call comes on 1 o’clock, we count the number of emergency calls come in the subsequent one-hour period and a number of concurrent demand (NCD) during this time period is obtained. We repeat it again on the second emergency call till to the last one. If there are $S$ calls in one day, we can obtain $S-1$ NCDs and MNCD is the maximum one.

6.2 Performance of the approach

We test the performance of the approach as follows. For each dataset, we generate ten test instances by multiplying the values of the real data and the fixed costs by ($1+\epsilon$), where $\epsilon$ is drawn from a uniform [$-$0.1, 0.1]. For different unit transportation costs ($\beta$) and service levels ($\alpha$), the average running times of ten instances are shown graphically in Figs. 1, 2 and 3, which are associated with the different type of MNCD, respectively. In each subfigure, X-axis indicates the number of candidate EMS stations and Y-axis refers to the running time. And, the average running times of the instances with different service level from 0.95 to 0.99 are reported.

From the extensive computational experiments, we find that:

• the optimal solutions of the all instances can be found in a reasonable amount of time;

• the impact of the unit transportation cost $\beta$ on the running time seems to be intricate. As the number of candidate EMS stations increases from 30 to 69, the running time increases when the unit transportation cost is cheap ($\beta =1, 2, 5, 10$). However, once the unit transportation cost becomes expensive ($\beta =20, 50$), the running time no longer increases monotonically with the number of the candidate EMS stations. When $\beta =20$ and 50, some instances exhibit shorter running times when considering more candidate EMS stations.

• the impact of the service level ($\alpha$) and the type of MNCD on the running time is insignificant.

Fig. 1

Performance of the algorithm: $d_i$ is a arbitrary random variable

Fig. 2

Performance of the algorithm: $d_i$ is a symmetric random variable

Fig. 3

Performance of the algorithm: $d_i$ is an unimodal symmetric random variable

Furthermore, several test data are generated randomly by using the following parameter values (Table 1) to test the efficiency of the approach for large scale instances.

Table 1 Parameter values used to generate test data

The means and the covariance matrix of the MNCDs are drawn from several series of $[d_1, d_2, \cdots , d_{|I|}]$ whose elements are generated uniformly from [0.1, 10]. We use them to simulate the three types of MNCDs because the means and the covariance matrix are used only in the model. The other parameter values are set to the same values as these used in the previous computational experiments.

For each group of the parameter values, five instances are generated and the average running time and the optimal gaps are reported in Table 2. The first column lists the numbers of candidate EMS stations and demand sites. The following two columns show the average running times and average optimal gaps, respectively. Although the running time increases significantly when the number of candidate site increases, it is expected for the planning problem. Also, the computations become efficient when we estimate the MNCDs more accurately.

Table 2 Performance of the approach, time limits = 7200 s

The performance of the valid inequality

In the rest of this section, a comparison between CPLEX with and without the valid inequality is made to test the performance of the valid inequality for the special case. The same test data are used and the covariances of the MNCDs betweens two different demand sites are set to be zero. The valid inequality is added to the root node of the branch and bound tree and the default setting of CPLEX is used. The results are reported in Table 3. The first column shows the number of candidate sites. The sequent two columns report the running time, optimal gaps when directly using CPLEX to solve the problem. The last three columns report the running time, optimal gaps, and the number of the valid inequalities added when using CPLEX with the valid inequality to solve the problem. The model associated with the special case become computational intractable. The instances with more candidate sites ($>100$) can not find a feasible solution within the time limits. As shown in Table 3, CPLEX with the valid inequality outperforms CPLEX without the valid inequality in terms of both quality of solutions obtained and computational time.

Table 3 Comparisons between CPLEX with and without the valid inequality, time limits = 7200 s

6.3 Validity of the second-order cone constraint

We test the valid of the approximation of Constraint (5) by Monte Carlo simulation. Under different service level ($\alpha$) and three kinds of the MNDC (arbitrary, symmetric, and unimodal symmetric), a Monte Carlo simulation procedure is summarized as follows. First, we solve the problem with the 50-dateset. And, the optimal EMS networks and the corresponding ambulance numbers at each EMS station are obtained. Then, we generate the MNCD at each demand site by assuming that the MNCD follows Normal distributions with the same means and variance-covariance matrix with those of the 50-dateset. At last, the MNCDs generated at the demand sites are served partially or completely by the EMS stations that are assigned to those demand sites. At each EMS station, the number of MNCDs and the ambulances are recorded. For each type of MNCD and each service level, one million of experiments are carried out and the ratio of the number of experiments that the number of MNCDs is less than the number of ambulances to the total experiments is the approximated service level of the EMS station.

The ratios are reported in Table 4. The first column lists the open EMS stations. “A”, “S”, and “U” in the first row refer to that the MNCD is arbitrary, symmetric, and unimodal symmetric random variables, respectively. Spaces in the table refer to that the corresponding EMS station is not constructed under that condition. As shown in the table, all the approximated service levels exceed the predetermined service level ($\alpha$), which implies that the approximation of constraint (10) is valid. Moreover, the approximated service levels become smaller if we can estimate the distribution of the MNCD more exactly, which implies the reduction of the costs.

Table 4 Approximated service levels obtained from Monte Carlo simulation, $|I|\times |J|=50\times 50$, $\beta =5$

The rows labeled by “Service level$_{norm}$” list the service levels when we assume the MNCDs follow Normal distributions, which are determined by searching the values of $\hat{\alpha }$ from the standard Normal distribution table. Under different $\alpha$, the minimal approximated service levels are exactly approximated to that service levels when the MNCDs are symmetric (columns with label of “S (%)” in the table) or unimodal symmetric random variables (columns with label of “U (%)” in the table) that are the properties of a Normal distribution function.

6.4 Sensitivity analysis

In order to explore the behavior of the system, we carry out sensitivity analysis on the model parameters. The number of candidate EMS stations is 69 and an extensive computational study is performed. In Figs. 4 and 5, the black and white bars with numbers represent the total numbers of EMS stations and emergency vehicles respectively. The curve indicates the optimal objective value. And, the X-axis in Figs. 4 and 5 refer to the unit transportation costs and service levels, respectively. The left Y-axis indicates the number of EMS stations and emergency vehicles and the right Y-axis means the optimal value of the objective function.

Fig. 4

Number of EMS stations and emergency vehicles and optimal objective value as $\beta$ varies: $d_i$ is an unimodal symmetric random variable

Fig. 5

Number of EMS stations and emergency vehicles and optimal objective value as $\alpha$ varies: $d_i$ is an unimodal symmetric random variable

Figure 4 shows that the higher unit transportation cost ($\beta$) leads to more expensive transportation cost and then more EMS stations are constructed and more emergency vehicles are needed. As shown in Fig. 5, in order to obtain the higher service level, total costs increase and more emergency vehicles are maintained. While, the number of EMS stations has a little impact on the service level. It implies that it is a preferred decision for improving the service levels to invest to emergency vehicles instead of to EMS stations. Furthermore, the number of EMS stations shows a tiny decrease in case of service levels 98%. The similar results are also observed in other instances (For example, $\beta =2$ and 10 in Figs. 7, 8 and 9 in Appendix 10). Therefore, it is interesting to note that sometimes construction of more EMS stations has a negative impact on the service level of the system.

The benefit of accurate evaluation of the random MNCD is found as well. As shown in Table 5, with fixed unit transportation unit and service level, the total costs are cut down and the number of emergency vehicles also decreases if more accurate estimation of the distribution of the MNCD is carried out. The number of EMS stations is affected a little. The same conclusion can be drawn from the instances shown in Figs. 7, 8 and 9 in Appendix 10. Therefore, a cost-efficient network with less emergency vehicles can be designed. The drawbacks of the accurate evaluation are that high quality historical data are needed.

Table 5 The numbers of EMS stations and ambulances and the optimal objective values of the instance with $|I|\times |J|=69\times 69$ and $\beta =5$

Moreover, for different type of MNCD ($d_i$), the location and the size of EMS stations may be different even the total number of EMS stations is identical. Figure 6 illustrates the location and size of EMS stations in two instances that have the idential total number of EMS stations. The number associated with each EMS station represents the number of emergency vehicles in that station. EMS station in rectangle uniquely emerges in the corresponding figure. We also observe that the change of service level ($\alpha$) impacts the location and the size of EMS stations. Thus, greedy algorithms that myopically add/remove EMS stations to the solution are not likely to be very effective.

Fig. 6

Location and size of each EMS station, total number of constructed EMS stations = 42, $\alpha =0.95$, $\beta =10$

7 Conclusions

To handle the inherent uncertainty of EMS, we propose a probabilistic model with chance constraints to determine the location of EMS stations and the number of emergency vehicles at each station. A mean-variance constraint, which is well studied in finance applications, is derived. Then, the original model is transformed to a conic quadratic mixed-integer program by approximating the chance constraints as a second-order cone constraints and employing a conic transformation. The advantages of the resulting model are as follows: (1) from the modeling perspective: both mean and variance of the MNCD are taken into consideration and independence among the demand sites are relaxed; (2) from the computational perspective: it is a convex program and the computational experiments on real data show that it is capable of addressing the cases with practical scales in a reasonable time.

According to the numerous computational studies, we find that (1) the proposed model performs well when solving problems of practical sizes; (2) the number of the emergency vehicles has significant impact on the service level of the system. Therefore, it is a more cost-efficient method for improving the service levels to increase the number of emergency vehicles instead of the number of EMS stations. (3) Moreover, more accurate estimation of MNCD from historical data contributes to the design of cost-efficient EMS system. (4) The different value of the parameters (service level, distribution of MNCD, etc) has impact on the location and sizing decisions of EMS stations. Therefore, greedy algorithms that myopically add/remove EMS stations to the solution, which is generated from less accurate estimation of MNCD, are not likely to be very effective.

Finally, we suggest some avenues of further research. Firstly, robust optimization (RO) is an alternative method used to deal with uncertainty if it is hard to extract exactly the distribution function from data. Secondly, this model can naturally be extended to a capacitated EMS design problem and more efficient algorithms have to be proposed. Thirdly, a bi-objective model with minimization of the response time and the costs is interesting as well.

Appendices

The proof of Theorem 1

Proof

$D_j=\sum _{i\in I}d_iX_{ij}$ and it follows probability distribution with mean $\mu ^T \bar{X}_j$ and variance $\bar{X}_j^T \varSigma \bar{X}_j$.

(1) For arbitrary random variable $d_i$, applying the following inequality (Popescu 2005)

$$\begin{aligned} \fancyscript{P}(D_j> N_j)\le \left\{ \begin{array}{ll} \frac{\bar{X}_j^T \varSigma \bar{X}_j}{\bar{X}_j^T\varSigma _j \bar{X}_j+(N_j-\mu ^T \bar{X}_j)^2}, &{}\quad if N_j-\mu ^T \bar{X}_j> 0,\\ 1,&{}\quad otherwise, \end{array}\right. \end{aligned}$$

we obtain

$$\begin{aligned} 1-\fancyscript{P}(D_j\le N_j)&\le \frac{\bar{X}_j^T \varSigma _j \bar{X}_j}{\bar{X}_j^T\varSigma _j \bar{X}_j+(N_j-\mu ^T \bar{X}_j)^2},\\ \fancyscript{P}(D_j\le N_j)&\ge 1-\frac{\bar{X}_j^T \varSigma _j \bar{X}_j}{\bar{X}_j^T\varSigma _j \bar{X}_j+(N_j-\mu ^T \bar{X}_j)^2}. \end{aligned}$$

Therefore,

$$\begin{aligned} 1-\frac{\bar{X}_j^T \varSigma _j \bar{X}_j}{\bar{X}_j^T\varSigma _j \bar{X}_j+(N_j-\mu ^T \bar{X}_j)^2}\ge \alpha \end{aligned}$$

is sufficient for constraint (9) to hold. The expression above can be rewritten as

$$\begin{aligned}&\alpha \bar{X}_j^T\varSigma _j \bar{X}_j\le (N_j-\mu ^T \bar{X}_j)^2 (1-\alpha ),\\&\mu ^T \bar{X}_j+\sqrt{\frac{\alpha }{1-\alpha }}\sqrt{\bar{X}_j^T \varSigma _j \bar{X}_j}\le N_j,\\&\mu ^T \bar{X}_j+\sqrt{\frac{\alpha }{1-\alpha }}\parallel \varSigma _j^{\frac{1}{2}} \bar{X}_j\parallel _2 \le N_j. \end{aligned}$$

(2) For symmetric random variables $d_i$, the following inequalities are hold (Popescu 2005):

$$\begin{aligned} \fancyscript{P}(D_j> N_j)\le \left\{ \begin{array}{l@{\quad }l} \frac{1}{2}min\left[ 1,\frac{\bar{X}_j^T\varSigma _j \bar{X}_j}{(N_j-\mu ^T \bar{X}_j)^2}\right] , &{}\quad if N_j-\mu ^T \bar{X}_j> 0,\\ 1,&{}\quad otherwise. \end{array}\right. \\ \end{aligned}$$

Because $\alpha \in [0.5, 1)$, the following inequalities are satisfied in order to hold constraint (9).

$$\begin{aligned} \fancyscript{P}(D_j\le N_j)\ge 1-\frac{1}{2}\frac{\bar{X}_j^T\varSigma _j \bar{X}_j}{(N_j-\mu ^T \bar{X}_j)^2}\ge \alpha .\\ \end{aligned}$$

Then,

$$\begin{aligned} \mu ^T\bar{X}_j+\sqrt{\frac{1}{2(1-\alpha )}}\parallel \varSigma ^{\frac{1}{2}} \bar{X}_j\parallel _2\le N_j. \end{aligned}$$

(3) For unimodal symmetric random variables $d_i$, the following inequalities are hold (Popescu 2005):

$$\begin{aligned} \fancyscript{P}(D_j> N_j)\le \left\{ \begin{array}{l@{\quad }l} \frac{1}{2}min\left[ 1,\frac{4}{9}\frac{\bar{X}_j^T\varSigma _j \bar{X}_j}{(N_j-\mu ^T \bar{X}_j)^2}\right] , &{}if N_j-\mu ^T \bar{X}_j> 0,\\ 1,&{}otherwise. \end{array}\right. \\ \end{aligned}$$

Using the same approach as that of the symmetric random variable, we can show the result for the unimodal symmetric random variables:

$$\begin{aligned} \mu ^T\bar{X}_j+\sqrt{\frac{2}{9(1-\alpha )}}\parallel \varSigma ^{\frac{1}{2}}\bar{X}_j \parallel _2\le N_j. \end{aligned}$$

Constraint (10) is a second-order cone constraint since $\parallel \varSigma _j^\frac{1}{2}\bar{X}_j\parallel _2$ is convex. $\square$

The proof of Property 1

Proof

The total number of emergency vehicles at EMS station $j$ satisfies the following inequality

$$\begin{aligned} \sum _{i\in I_j}X_{ij}(\mu _i+\hat{\alpha }\sigma _i)\le \sum _{i\in I_j}X_{ij}\sum _{j^{'}\in J_i}n_{ij^{'}}=\sum _{i\in I_j}n_{ij}=N_j. \end{aligned}$$

By Cauchy inequality we know that $cov(\xi \eta )\le [D(\xi )]^{\frac{1}{2}}[D(\eta )]^{\frac{1}{2}}$, then

$$\begin{aligned} \mu ^T \bar{X}_j+\hat{\alpha }\parallel \varSigma _j^{\frac{1}{2}}\bar{X}_j\parallel _2\le \mu ^T \bar{X}_j+\hat{\alpha }\sigma ^T\bar{X}_j \le N_j. \end{aligned}$$

$\square$

The computational results for three classes of the random MNCD

See Figs. 7, 8 and 9.

Fig. 7

Number of EMS stations and emergency vehicles and optimal objective value: $d_i$ is a arbitrary random variable

Fig. 8

Number of EMS stations and emergency vehicles and optimal objective value: $d_i$ is a symmetric random variable

Fig. 9

Number of EMS stations and emergency vehicles and optimal objective value: $d_i$ is an unimodal symmetric random variable