Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Providing high quality medical services and ensuring accessibility to these services for the general public is a key task for a health care system. Given a limited budget available resources, e. g. ambulances or locations of EMS and fire departments, have to be planned and used economically in order to ensure high quality supply [2–4]. Explicitly, during a regular day EMS-vehicles have to be positioned and re-positioned such that emergencies can be reached within a legal time frame. Empirical studies show that demand changes over time and that there are regional differences. In the current situation in Bochum ambulances are placed at existing EMS and fire departments. Because these rescue departments are located near the city center, this leads to a very high degree of coverage in the city center and causes undersupply in peripheral areas. In particular some demand areas are covered ninefold and in many cases far exceeds the required degree of coverage. In contrast peripheral regions are covered only once and some of these regions are not covered at all within a given time limit. In order to handle these effects, the required or necessary coverage is investigated empirically. An integer linear program (ILP) is applied in order to locate and relocate ambulances according to a required degree of coverage. For this, a number of additional, flexible ambulance locations will be considered. The goal is to use resources such as ambulances efficiently and ensure the empirically determined necessary coverage. This leads to a high level of service and at the same time avoids over-coverage and saves resources.

2 Identifying Empirically Necessary Coverage

A large number of models have been developed in order to support decision making for ambulance location in various decision situations. Farahani et al. [5] provide a comprehensive survey of covering models which are typical for EMS applications and Li et al. [8] provide a well structured survey of optimization models with focus on emergency response applications. Additionally, Başar et al. [1] and Hulshof et al. [7] give taxonomic overviews of decision support systems. In almost all presented models a unique degree of coverage is maximized. For example, a double-coverage is considered in the Double Standard Model (DSM) by Gendreau et al. [6] and its extensions [9]. Instead of ensuring double coverage for each demand region during the entire day analytics and data driven optimization can be used to determine a better level of necessary coverage. We investigate empirically the number of emergency situations occurring simultaneously in order to determine the required degree of coverage (see Fig. 1). Each demand site is analyzed individually due to the fact that usually observed demand is not equally distributed over the planning area. To calculate the necessary coverage degree \(\mathrm e (i)\) of a demand node \(i\) we have to ensure that the probability that an emergency call could not be served because no ambulance is available is less then \(1-\beta \,\%=5\,\%\), or in other words, that:

$$ Probability \left\{ \genfrac{}{}{0.0pt}{}{\#\text { of ambulances can cover}}{\text {demand node }i}\,\,\ge \,\,\genfrac{}{}{0.0pt}{}{\#\text { of parallel emergencies in}}{\text {the area around }i} \right\} \ge 95\,\% $$

First a static version of the model which maximizes the empirically determined necessary coverage is formulated and then we consider dynamic, time-dependent modifications.

Fig. 1
figure 1

Consideration of parallel emergency operations. In this situations a double coverage (two ambulances) is necessary

Full size image

2.1 Model with Empirically Necessary Coverage

The (standard) DSM seeks to maximize the demand covered twice within a time standard of \(r_1\), using \(p\) ambulances and subject to the double covering constraints. In our approach the static model maximizes the demand, which is covered \(\mathrm e (i)\)-times:

$$\begin{aligned} \max \quad&\sum _{i\in I} d_i x_i^\mathrm{e (i)} \end{aligned}$$
(1)
$$\begin{aligned} \mathrm s.\,t. \quad&\sum _{j\in \mathcal {N}_i^{r_2}} y_{j} \ge 1 \qquad \qquad \qquad \, \forall i\in I \end{aligned}$$
(2)
$$\begin{aligned}&\sum _{i\in I} d_i x_{i}^1 \ge \alpha \sum _{i\in I} d_i \qquad \quad \forall i \in I \end{aligned}$$
(3)
$$\begin{aligned}&x_i^{k-1} \ge x_i^{k} \qquad \qquad \qquad \qquad \forall i \in I,\, \forall k\in \{2,\ldots ,p\} \end{aligned}$$
(4)
$$\begin{aligned}&\sum _{j\in \mathcal {N}_i^{r_1}} y_j \ge \sum _{k=1}^{p}x_i^k \qquad \quad \quad \forall i \in I \end{aligned}$$
(5)
$$\begin{aligned}&\sum _{j\in J} y_j \le p \end{aligned}$$
(6)
$$\begin{aligned}&x_{i}^k \in \{0,1\} \qquad \qquad \qquad \qquad \forall i\in I,\,\forall k\in \{1,\ldots ,p\} \end{aligned}$$
(7)
$$\begin{aligned}&y_j \in \mathbb {N}_0 \qquad \qquad \qquad \qquad \quad \,\, \forall j\in J \end{aligned}$$
(8)

where \(d_i\) is the demand at node \(i \in I\), \(\mathcal {N}_i^{r_\ell } := \{j \in J \mid t_{ij} \le r_\ell \}\) for \(r_1 < r_2\) characterises the neighborhood sets of demand node \(i\) and \(p\) represents the total number of ambulances. The decision variable

$$ x_i^k := \left\{ \begin{array}{ll} 1,&{}\text {if demand node}\,\, i\,\, \text {is covered}\,\, k\in \{1,\ldots ,p\}\,\text {times} \\ 0,&{}\text {else.} \end{array}\right. $$

\(y_j\) represents the number of ambulances located at node \(j\). The objective function computes the demand covered \(\mathrm e (i)\)-times within \(r_1\) time units. The combination of constraints (2) and (3) ensures that a proportion \(\alpha \) of the total demand is covered within \(r_1\) and the whole demand area is covered within \(r_2\). Constraints (3) and (4) express the necessary coverage requirements. The left-hand side of (5) represents the number of ambulances covering demand node \(i\) within \(r_1\) time-units, while the right-hand side is 1 if \(i\) is covered once and so on within \(r_1\). Equation (6) limits the number of ambulances to \(p\). (7) and (8) describe the domain of the decision variables.

2.2 Time-Dependent Considerations

Fig. 2
figure 2

Number of emergency calls for a 24-h-day in a German mid-size city and average (aggregated) speed

Full size image

In addition to considering empirical necessary coverage \(\mathrm e (i)\), significant time-dependent variations in the input parameters as demand, travel-time and necessary coverage can be observed. Almost all models in literature do not include all dynamic aspects at the same time. In Fig. 2 the number of emergency calls is indicated with respect to every hour of the day. The figure shows that there are significant differences in demand between night, day and peaks especially during rush hours. Moreover, this figure clearly indicates that demand changes during the day. A required constant degree of coverage will either underestimate or overestimate actual demand, e. g. \(\mathrm e (i,t)\) is time-dependent. However, existing models do not consider time-dependency of model parameters such as demand and travel times for ambulances. A new modeling approach is developed that explicitly integrates demand and travel times varying simultaneously throughout the day. In order to generate more flexibility in the EMS-system, we allow the assignment of ambulances not only to existing EMS-departments but also to additional, flexible locations such as hospitals or volunteer fire departments. Variations in the fleet size during the day depending on changes in travel speed are explicitly included to consider economic aspects. Dynamic allocation of ambulances at additional, flexible locations and relocations to the main EMS-departments are required to handle time-dependent changes in travel-speed and demand. The degree of coverage, the number of relocations and the fleet size are considered to be major performance indicators. Incorporating these aspects leads to a dynamic version of model (1)–(8).

3 Improvement of Status Quo

The dynamic model is part of a decision support tool that is developed for urban emergency services. The aim is to support strategic and tactical decisions. The following figures clearly show the improvement of the status quo. For Bochum (Germany) it can be seen, that the new model also outperforms the double coverage model.

Fig. 3
figure 3

Differences between the required empirical coverage and the coverage obtain from (1) status quo, (2) solution by the double covering maximization model, and (3) our solution by the empirically determined suitable covering maximization model for rush hour period (8–12 a.m.)

Full size image

Figure 3 illustrates the positive effects of maximizing the empirical coverage for a time period around midday in which demand is typically high (see Fig. 1). The three maps depict the deviation from empirical coverage to (1) the actual solution (“status quo”) which is applied by the EMS in Bochum, Germany, (2) a solution determined by dynamic model similar to the model presented by Schmid and Doerner [9] with a double coverage optimization function and the solution of our new model (3). The evaluation considers the deviation of necessary coverage and the coverage obtain by the status quo or the models. White squares mean that the empirically necessary degree of coverage is achieved by the solution. Attaining the empirical level and also small positive differences are preferable. Besides a very low level of coverage (dark gray) which can lead to non-sufficient supply of population, also a very high degree of coverage (light gray) should not be tolerated because it wastes resources that could be utilized in a better way. The current situation shows typical results for urban areas: planning sites in the city center are “over-covered” to a large extent (more than 7-times over the necessary level). Yet, the resulting degree of coverage in the periphery is very often below a target level. The improvements according to integrating time-dependent and spatial demand become obvious. Data driven optimization and analytic methods as well as dynamic considerations lead to an efficient ambulance utilization. The same service level in the system can be ensured by less ambulances.

4 Conclusions

An evaluation using real-world data from 2010 to 2012 clearly points out that considering time-dependent travel times and time-dependent demand in our approach outperforms existing solutions using static model parameters. Overall, the proposed approach leads to a high quality solution with respect to coverage and cost criteria.