PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
 
Eur J Oper Res. 2010 December 16; 207(3): 1293–1303.
PMCID: PMC2982752

Ambulance location and relocation problems with time-dependent travel times

Abstract

Emergency service providers are facing the following problem: how and where to locate vehicles in order to cover potential future demand effectively. Ambulances are supposed to be located at designated locations such that in case of an emergency the patients can be reached in a time-efficient manner. A patient is said to be covered by a vehicle if (s)he can be reached by an ambulance within a predefined time limit. Due to variations in speed and the resulting travel times it is not sufficient to solve the static ambulance location problem once using fixed average travel times, as the coverage areas themselves change throughout the day. Hence we developed a multi-period version, taking into account time-varying coverage areas, where we allow vehicles to be repositioned in order to maintain a certain coverage standard throughout the planning horizon. We have formulated a mixed integer program for the problem at hand, which tries to optimize coverage at various points in time simultaneously. The problem is solved metaheuristically using variable neighborhood search. We show that it is essential to consider time-dependent variations in travel times and coverage respectively. When ignoring them the resulting objective will be overestimated by more than 24%. By taking into account these variations explicitly the solution on average can be improved by more than 10%.

Keywords: Location, Time-dependent travel time, Ambulance vehicles, Variable neighborhood search

1. Introduction

1.1. Motivation

Much research has been focused on solving various kinds of vehicle location problems in both static and dynamic environments. Travel times however, which should form the basis for quantifying the objective to be optimized, mostly are assumed to be constant throughout the planning horizon. Variations in velocity and speed during peak hours usually are completely ignored. Recent developments in Global Positioning System (GPS) allow velocities – so called Floating Car Data (FCD) – to be collected over time. Based on past observations time-varying velocities can be defined for different street segments within a street network. As a consequence time-dependent travel times can be estimated for different time periods. Taking into account time-dependent travel times significantly influences the quality of the solution obtained. Especially in areas with high traffic volume during peak hours travel speed and the resulting travel time can vary significantly throughout the day. Just using (averaged) fixed travel times is no longer sufficient and will lead to sub-optimal or infeasible solutions. In order to overcome this issues we allow vehicles to be relocated throughout the planning horizon in an anticipatory manner in order to tackle variations in speed and the resulting changes in coverage.

Please note that the proposed model at hand can be applied to other applications (e.g. locating a fleet of taxis, service technicians, break-down service vehicles, etc.), where quality is usually measured in terms of coverage or response times, as well. It can be used to manage a set of service entities (i.e. ambulances, service vehicles, taxis), that need to be located such that customer entities (i.e. patients, customers, passengers, etc.) can be reached efficiently in case of a request.

1.2. Related work

1.2.1. Early models

Most ambulance location models found in the literature are extensions of the location set covering model (see Toregas et al., 1971), which try to minimize the number of ambulances necessary in order to cover all demand points. Another early model for the problem is the so called maximal covering location problem and was originally proposed by Church and ReVelle (1974), which tries to maximize the total demand covered given a fleet of fixed size. These are static models that do not consider the fact that ambulances will become unavailable throughout the day and certain demand points might not be covered any more. Several approaches have been developed in order to handle this. One possibility includes multiple coverage, i.e. demand points are supposed to be covered by more than one vehicle. Such a model, called the double standard model (DSM) was introduced by Gendreau et al. (1997). Other possibilities for handling vehicles becoming unavailable include busy fractions, where the probability that vehicles might become unavailable is modeled explicitly (see Daskin (1983)).

1.2.2. Static double standard model

The DSM maximizes the demand covered by at least two vehicles, implicitly taking into account the fact that vehicles might become unavailable, while ensuring certain additional requirements concerning coverage are met. In particular they try to ensure that α% of the population are covered within r1 time units and all demand points need to be covered by at least one vehicle within r2 time units, where r1 < r2. The model has been proposed in Gendreau et al. (1997) and has been solved using tabu search. Their formulation considered a single period only and treated travel times as static. It did not allow the resulting changes in coverage throughout the day to be taken into account. Another drawback of the single-period DSM formulation is that it does not limit the demand that can be covered by one single vehicle. Especially in densely populated areas defining coverage in terms of a radius within which patients shall be reached might not be sufficient. The DSM has been further extended by Doerner et al. (2005). In their paper they deviate from the traditional assumptions that vehicles can cover any emergency that lies within a predefined radius by taking into account capacity considerations. At most a certain amount of demand (i.e. number of inhabitants in the designated areas) can reasonably be covered by one single vehicle.

Successful applications of models based on DSM formulations include one by Thirion (2006) to two provinces in Wallonia, Belgium. The author has shown that a significant improvement in coverage could be reached without increasing the number of ambulances in use. Doerner et al. (2005) applied an extended version of the DSM to data coming from the eight rural provinces in Austria. A broader overview on different applications can be found in Laporte et al. (2009). Furthermore models have been applied successfully to data from Montreal, Canada (Gendreau et al., 1997). Their model has also been extended into a dynamic environment (Gendreau et al., 2001). They take advantage of the available time between consecutive calls by anticipating future decisions on the redeployment of the fleet.

1.2.3. Dynamic coverage models

Several approaches already have been proposed that handle the ambulance location problem in a dynamic setting. An extension of the maximum expected coverage location problem proposed by Daskin (1983) has been developed by Repede and J Bernardo (1994). The authors propose and solve a multi-period maximum expected coverage location problems with time-variant travel times and changing fleet sizes (TIMEXCLP). Their objective is to optimize the expected coverage at various points in time. They incorporate temporal variations in the daily demand process in addition to spatial variations and multiple states of vehicle availability. However, the resulting number of relocations of vehicles in between is neglected and not considered explicitly during the stage of optimization. In their paper Repede and Bernardo propose a decision support system. First the location of ambulances will be determined using the TIMEXCLP model, which then will be tested by means of a simulation model. If required system characteristics are not met a new TIMEXCLP will be generated. Another multi-period model for dynamic demand environments which minimized the number of ambulances required while meeting predetermined ambulance availability requirements has been proposed in K Rajagopalan et al. (2008). In contrast to previous models, ambulance specific busy probabilities have also been considered. They solved the model using tabu search. The solution then is validated by means of simulation. Only demand nodes that are covered with a certain probability are included in the system wide expected coverage. The model itself is solved iteratively starting from the first time period for a given fleet size. If coverage requirements are (not) exceeded the model will be rerun using a decremented (incremented) fleet size. The model itself however is solved iteratively for consecutive time periods, while ignoring the resulting relocations from the ambulance’s point of view. In Gendreau et al. (2006) a probabilistic model has been proposed, which also limits the number of reallocations allowed. A broad overview on different location problems and their applications in the context of ambulance location problems can be found in Brotcorne et al. (2003) and Laporte et al. (2009).

1.2.4. Time-dependent travel times

According to Repede and J Bernardo (1994) maximum coverage models in time variable settings tend to overestimate the resulting coverage. In traditional models travel times are supposed to be deterministic. Early models for considering time-dependent travel times in a general routing context were proposed in Hill and Benton (1992) and Horn (2000), who introduced the concept of piecewise linear continuous speed functions. A discussion of different model formulations for incorporating time-dependent travel times can be found in Malandraki and Daskin (1992). More recent and relevant articles were published by Ichoua et al. (2003), Fleischmann et al. (2004a), Fleischmann et al. (2004b) and Donati et al. (2003), Donati et al. (2008).

For an overview on the calculation of time-dependent travel times based on FCD-data see Reinthaler et al. (2007), Laborczi et al. (2006) and Linauer and Nowotny (2006).

Empirical evidence against time-dependent variations in traveling times encountered by fire engines is given in Kolesar et al. (1975), who validated a model for average fire engine travel times, depending on the distance traveled for the city of New York. They conclude that the time of day only has minor impact on average response velocities. A similar analysis has been repeated and extended for ambulances in Budge et al. (2010) for the city of Calgary. Despite this empirical evidence, the operating experience of practitioners in Austria indicates that travel speeds do vary over the course of a day, for the following reasons:

  • • Streets in Europe, as opposed to streets on the North American continent, typically tend to be narrower. Especially during peak times the traffic volumes in urban areas increases and causes congestion. Due to narrower streets ambulances, as regular vehicles, are affected and cannot circumnavigate jammed vehicles in congested street segments.
  • • Next one needs to point out that not every request ambulances have to serve entitles them to have right of way by all means. Only in case of life-threatening incidences and calls where the response time has medical consequences ambulances are allowed to make use of acoustic and light signals and – as a consequence – to speed up their drive.
  • • Even if ambulances are allowed to make use of their acoustic and/or light signals they are still bound to legal regulations concerning the maximum travel speed, which must not be exceeded. As the resulting accident rate would increase disproportionately, drivers furthermore are required not to drive unreasonably, endangering themselves or other road-users.

Due to these observations we were explicitly encouraged to investigate the ambulance location and relocation problem with time-varying travel times, as observed by our industry partner. The corresponding variations are significant and should be taken into account for a proper deployment of ambulances.

1.2.5. Solution methods

Due to the steady increase in computational power, sophisticated metaheuristics such as Variable Neighborhood Search (VNS) allow the solution space to be effectively searched for good solutions. VNS is a highly promising metaheuristic which has been developed by Hansen and Mladenović (1997) and extended in Hansen and Mladenović (2001). It is a local search based improvement heuristic. In contrast to population based approaches it concentrates on one single solution only and does not incorporate any type of adaptive memory. An efficient search within the solution space is guaranteed by both diversification and intensification strategies in use. VNS has proven to work exceptionally well on all kinds of problems from the field of location (see Brimberg et al., 2000; Mladenović et al., 2003; Crainic et al., 2004) and routing (see for example Bräysy (2002), Parragh et al. (2010), Polacek et al. (2004)).

1.3. Contribution

The DSM is an ideal formulation for solving the tactical problem under consideration. Stochastic demand of vehicles that can serve at most one call at a time can be handled by backup coverage (see Hogan and ReVelle, 1986). By enforcing double coverage of patients the dynamics of the underlying systems are already partially considered. Hence it is highly suitable for optimizing the location of ambulances in real-world. In order to overcome some of its drawbacks we have decided to extend their model in several ways.

  • (i) We have extended the single-period model to a multi-period version. Solving a single-period DSM once only taking into account current or average travel times is not satisfactory.
  • (ii) We will explicitly take into account time-dependent variations in speeds and the resulting changes with respect to the corresponding coverage.
  • (iii) Furthermore we will allow vehicles to be relocated in order to overcome this issue, rather then finding a static position for the entire planning horizon. Relocating too many vehicles should be avoided and hence this issue will be considered in the objective function.
  • (iv) Finally, we extend the model of Gendreau et al. (1997) relating to capacity considerations by further developing what was proposed by Doerner et al. (2005). In Doerner et al. (2005), however, all demand points that are located within a certain distance are considered for this kind of capacity consideration. In this paper, however, we explicitly assign fractions of patients’ demand to vehicles in order to model this feature more correctly. By using this approach, potential patients being counted more than once for capacity considerations can be avoided.

By ignoring time-dependent variations in travel times one severely misestimates the resulting coverage, which will lead to inferior solutions. By taking into account those variations during the optimization phase and allowing vehicles to be relocated, the quality of the solutions obtained can be increased significantly. The goal is to provide the decision maker with time-dependent location plans, such that the resulting coverage can be kept at the required level throughout the planning horizon. These plans are especially useful when dispatchers do not have access to an online decision support system. First, we take advantage of the availability of time-dependent data in order to get a clearer view of the traffic situation and the resulting changes in coverage throughout the day. Next we introduce a model which incorporates this information and allows vehicles to be repositioned to optimize the coverage at several points in time. Finally we developed an innovative metaheuristic search procedure, based on the concepts of VNS.

There are different ways to consider time-dependent data. First we solve our model in a myopic way at various points in time using the prevailing travel times respectively. All resulting relocations will be calculated ex post. Rather then solving the model independently several times, we try to solve the model simultaneously for various points in time. All resulting relocations will be considered implicitly during the optimization phase.

2. Problem formulation

Let W be the set of potential vehicle locations. The set of demand locations is denoted by V. The problem itself is defined on a graph G=(VW,E), where E is the set of edges {(j,i):jW,iV}, each associated with travel time sjit prevailing at time t. Each demand location iV is associated with a corresponding demand value di. The goal is to locate p vehicles among all potential vehicle locations, such that all demand locations can be reached within r2 time units and α % of the population (0 < α < 1) can be reached within r1 (r1 < r2) time units at all times tT, where T={1,,T}. No more than pj vehicles can be located at location jW at any time. The objective is to maximize the demand covered by at least two vehicles within a radius of r1 at all tT. The number of vehicles to be located at vehicle location j(jW) in tT is denoted by yjt. The binary decision variable xik,t will be equal to one if the demand at vertex iV is covered k times (k = 1, 2) at time t. Let Wi1,t(Wi2,t) be the set of vehicle locations from which patient i can be reached within radius r1 (r2) at time t. (Wik,t={jW:sjitrk;k=1,2}). The set of patients that can be reached within r2 time units by a vehicle located at location jW is denoted by Vj2,t. In order to define the set of patients to be covered by locations, the shortest path was considered and then evaluated in terms of the prevailing speed at various points in time. The subset of time intervals excluding the very last one is denoted by T. The number of vehicles that are supposed to be relocated from location i to j(i,jW) between t and t + 1 (t [set membership] T′) is denoted by rijt. In order to consider the end-of-horizon-effects, the relocation of vehicles in period t = T influences the location of vehicles in period t = 1. The number of vehicles to be relocated between T and 1 is denoted by rijT.

In order to emphasize locating more vehicles in densely populated areas we assume that any given vehicle can cover at most ω inhabitants reasonably. The actual demand at patient location iV that is covered by a vehicle located at jW in t is denoted by zijt.

The DSM introduced by Gendreau et al. (1997) furthermore has been extended in terms of time-dependent travel times. We consider them as well as the resulting variations in coverage levels and all relocations necessary. The resulting model is a multi-period DSM (mDSM). Rather than optimizing the total demand covered at least twice within r1, the coverage throughout the entire planning horizon and all necessary relocations will be considered simultaneously. In the objective function (see Eq. (1)) we sum up the two objectives using a weighted sum approach. The penalty for relocating vehicles is denoted by β.

maxf(x)=tTiVdixi2,t-βi,jWrijt,
(1)
s.t.jWi2,tyjt1iV,tT,
(2)
iVdixi1,tαiVditT,
(3)
jWi1,tyjtxi1,t+xi2,tiV,tT,
(4)
xi2,txi1,tiV,tT,
(5)
jWyjt=ptT,
(6)
yjtpjjW,tT,
(7)
yjt+iWrijt-iWrjit=yjt+1jW,tT,
(8)
yjT+iWrijT-iWrjiT=yj1jW,
(9)
iVj2,tzijtωpjjW,tT,
(10)
jWi2,tzijt=diiV,tT,
(11)
xik,t{0,1}iV,tT,k{1,2},
(12)
yjtintegerjW,tT.
(13)

Throughout the planning horizon T a DSM has to be considered simultaneously at every instance tT, while considering the prevailing travel times. Constraints (2) ensure that every demand location i will be covered at least once within r2 at every point in time t. Constraints (3) ensure that α% of the total demand is covered within r1 at every instance of time t. The combination of Constraints (4) and (5) ensure that a demand location can only be covered once (twice) if sufficient vehicles are located around demand location iV. A total number of p vehicles has to be located (see Constraints (6)), while ensuring that capacity restrictions at the individual potential waiting sites are not exceeded (see Constraints (7)). Constraints (8) and (9) ensure that resulting relocations of vehicles between different location can take place accordingly. Due to Constraints (10) and (11) the demand of every patient will be assigned to locations, while making sure that no single vehicle can reasonably cover more than ω patients. The variables xik,t modeling the coverage are supposed to be binary (see Constraints (12)). The number of vehicles to be located is integral (see Constraints (13)).

Due to the changing traffic situation a feasible solution can not be guaranteed. In order to solve the problem Constraints (2), (3) and (11) will be relaxed. The following extended problem formulation will be used, including Constraints (4)–(9), (10), (13), where x+ = max{0,x}.

maxF(x)=f(x)-tT(γ1f1t(x)+γ2f2t(x)+γ3f3t(x)),
(14)

where

f1t(x)=iV1-jWi2,tyjt+tT,
(15)
f2t(x)=αiVdi-iVdixi1,t+tT,
(16)
f3t(x)=iV(di-jWi2,tzij)+tT.
(17)

By reducing the number of time intervals T to one, the problem at hand reduces to a static myopic problem, where the situation at a particular point in time, considering prevailing travel times only and without any relocations, will be optimized.

3. Variable neighborhood search

The problem at hand will be solved by methods inspired by means of VNS. A basic sketch of VNS is depicted in Algorithm 1. The algorithm stops after a certain number of iterations or as soon as a given time limit is reached. During the shaking phase, various neighborhoods are used to explore the solution space thoroughly and in order to escape local optima. Departing from the best solution x a neighboring solution x′ will be generated at random from neighborhood Nk(x). The embedded local search phase tries to improve any solution x′ obtained after the previous shaking step. If the resulting solution x″ is not worse than the best solution x, it will be accepted and becomes the new best solution x and the shaking phase will be restarted with the first neighborhood, otherwise the search continues with neighborhood k + 1. Due to the fact that many location solutions lead to the very same objective function value, the best solution will change more frequently. Therefore the concept of accepting deteriorating solutions is not considered as important or useful.

3.1. Variable neighborhood search for double standard model

Any solution for a DSM can be uniquely represented by the location of vehicles and the assignment of patients to locations respectively. The search procedure will be initialized by assigning vehicles to locations randomly. The assignment of patients to locations will be determined using a simple greedy procedure.

Table thumbnail

3.1.1. Initial solution

To start with all vehicles will be located randomly across all potential locations, while making sure capacity restrictions at those locations are obeyed.

3.1.2. Shaking

During the shaking phase the solution space will be explored more thoroughly. Two different shaking operators with resulting six neighborhoods Nk (k = 1 … 6) have been implemented and tested. The first shaking operator (move), responsible for neighborhood structure Nk (k = 1 … 3), tries to move vehicles currently located at k + 2 locations. Therefore a subset of locations S (where |S|=k+2) will be determined randomly. Vehicles will then be moved among the locations j within the subset S, while making sure the capacity restrictions at the involved locations jS are obeyed.

Neighborhood Structures Nk (k = 4 … 6) relate to the second shaking operator (swap). This operator tries to swap the sequence of assignment (of vehicles to vehicle locations) of any randomly drawn subset S, where |S|=k-1.

3.1.3. Local search

After the solution x has been perturbed using the corresponding neighborhood structure, the resulting solution x′ will tried to be further improved by means of local search. Within the local search phase any solution is tried to be further improved by means of small local changes. We’ve tested two local search operators. The main idea of our first local search operator is to move a single vehicle from one location to a different one. Using a first-improvement strategy any vehicle currently located at location j is tried to be inserted at all other locations j′ (j′ ≠ j). Our second local search operator tries to swap as many vehicles as possible between two locations i and j. Both operators are executed in a first-improvement fashion. Only feasible movements – in terms of the capacity restrictions prevailing at the potential waiting sites – are considered.

3.2. Variable neighborhood search for multi-period double standard model

Any solution for our mDSM can be uniquely represented by the location of the vehicles and the assignment of patients to vehicle locations. The position of all vehicles at time t is referred to as a location pattern. A location pattern for every time period t is used in order to represent a solution for the entire planning horizon. For runtime reasons the assignment of patients to vehicle locations will be determined using a simple greedy procedure.

3.2.1. Initial solution

In order to initialize the VNS for the mDSM the problem will be solved in a myopic fashion and independently, once for every time period tT. A DSM (using the procedures described in Section 3.1) will be solved at each step, taking into account the current travel times and corresponding coverage radii.

3.2.2. Shaking

Any two location pattern can be compared in terms of the Hamming distance (Hamming, 1950), where the number of necessary relocations to get from one location pattern to the other one is given by one half of the Hamming distance. In order to explore the solution space thoroughly a shaking operator with three resulting neighborhood structures has been designed. At first two consecutive time periods t1 and t2 (where t2 = t1 + 1) are randomly selected and evaluated in terms of the resulting coverage and the necessary number of relocations. In every shaking step one location pattern will be assimilated to another one. Any assimilation tries to make two location patterns more similar to each other in terms of the number of vehicles placed at all possible locations, hence reducing the Hamming distance. The decision which location patterns should be assimilated to each other is based on the following considerations.

First the solution quality of the location patterns lp(t1) (lp(t2)) prevailing at t1 (t2) will be evaluated and compared to the solution of the myopic problem lpM(t1) (lpM(t2)). The time period in which the current location pattern performs worse (best) with respect to the corresponding myopic location pattern will be denoted by t (t+). Furthermore the number of relocations involved in order to move from location pattern lp(t1) to lp(t2) will be determined by evaluating in terms of the Hamming distance. Depending on the solution quality and the number of relocations involved the following strategy will be chosen: In case the number of relocations necessary between the two location patterns prevailing at t1 and t2 is high (as compared to the average number of relocations to be executed per day) an attempt will be made to overcome this issue. The location pattern which currently performs worse lp(t) in terms of the resulting coverage will be assimilated to the other location pattern lp(t+) respectively. Hence emphasis will be put on improving the solution in terms of the necessary number of relocations while taking into account a potential decrease in the resulting coverage. In the case of a small Hamming distance between the two location patterns lp(t1) and lp(t2), the pattern which currently performs worse (lp(t)) relative to its corresponding myopic solution will be assimilated to the location pattern of the myopic solution (lpM(t)) prevailing at time t. Hence more emphasis will be put on the improvement of the solution in terms of the resulting coverage.

In every shaking step location pattern lp1 will be assimilated to lp2. Any neighborhood Nk (k = 1 … 3) changes the number of vehicles placed according to location pattern lp1 at up to 10·k% of all possible locations. The new number of vehicles to be placed at location j will be randomly drawn from the interval minvjlp1,vjlp2,maxvjlp1,vjlp2, where vjlp refers to the number of vehicles currently located at location l according to location pattern lp. As the total number of vehicles in the resulting pattern lp1 might have changed, location pattern lp1 might need to be revised such that exactly p vehicles are located at all locations in total. Hence excess (missing) vehicles are removed from (inserted into) the location pattern afterwards.

3.2.3. Local search

Within the local search phase any solution is tried to be further improved by means of small local changes. The main idea of our local search operator, similar to what has been done for the DSM (see Section 3.1.3), consists of moving single (or swapping several) vehicles from one location to a different one. In order to emphasize a diversification strategy at the very start of the solution process, the local search will limit itself to the location patterns currently prevailing at t1 and t2. Hence allowing a large number of neighborhoods to be explored without the burden of extensive local search phases in between. During the solution process however the search process will be intensified by steadily extending the number of time intervals considered within local search.

4. Computational experiments

4.1. Data description

For our computational experiments we used real-world data from the city of Vienna (Austria). The population of Vienna amounts to approximately 1.7 million inhabitants. The locations of potential patients were derived from census data. The 3920 demand points iV were derived by aggregating the population by squares (250 meter × 250 meter), each with a demand (measured in terms of inhabitants) between 1 and 2977. We are going to solve the problem inspired by an ambulance service provider in Vienna. The goal is to provide adequate coverage for the population in case of emergency. A real-world road network from Teleatlas using all streets accessible by car has been used. FCD was used in order to estimate time-dependent variations in travel time on each link over the course of time.

The FCD-data were aggregated from data collected by a fleet of taxis in the city of Vienna, communicating their speed and positions throughout several months by means of GPS. The raw data has been aggregated by Austrian Institute of Technology which provided us with the average travel speed on each link within 96 intervals, each with a length of 15 minutes, starting at midnight. The average travel speed along the individual links varied by up to 25% from the overall average throughout the course of the day. Especially in the core of the city the average speed decreased significantly during rush hours. A graphical representation of the changes concerning the traffic situation throughout the day is given in Section 4.2.5. We use this data in order to solve the problem at hand at a tactical level. Only observations collected during weekdays were used.

Please note that the data were collected by a fleet of taxis, which serves as an estimate for the travel times experienced by ambulances. Unlike regular cars they are allowed to use designated lanes. This however is perfectly suitable for our application at hand, as ambulances are also allowed to use those special lanes within the network. The total planning horizon of 24 hours was equally split into 6 time intervals and time-dependent travel times were aggregated accordingly. Analyzing the data led to the conclusion that a more fine-grained level of discretization is not necessary (see Section 4.2.2).

The algorithm was tested on various scenarios, each with a different number of potential locations spread throughout the city of Vienna. Testcase 1 considered the 16 potential waiting sites currently in use. For testcases 2, 3 and 4 the number of potential waiting sites was changed to 51, 94 and 163 respectively. In testcase 2 the shops of a large fast food chain are used as potential vehicle location sites. Testcase 3 comprises all police stations in Vienna as potential vehicle locations and in testcase 4 a selection of typical Austrian luncheonettes is used. There are no legal regulations concerning coverage standards in Austria. The model uses the rules set by the United States Emergency Medical Services Act of 1973, where r1 (α) are set to 10 minutes (95%). The second coverage radius, r2, was set to 20 minutes. A total number of 14 vehicles had to be located at various potential waiting sites, each having a capacity pj=1(jW). For a topographical representation of the four testcases under consideration see Fig. 1(a)–(d).

Fig. 1
Graphical visualization of test instances.

4.2. Results

4.2.1. Importance of time-dependent travel time

In order to emphasize the importance of time-dependent travel times and the resulting coverage radii the following experiment was set up first: The DSM formulation (using the approach described in Section 3.1) was solved once for the entire planning horizon using average travel times only. By completely ignoring time-dependent variations in travel times, this naive approach optimizes the location of vehicles using average travel times only. The resulting coverage throughout the day was evaluated ex post, by explicitly taking into account the prevailing travel times given the naive location pattern obtained before. On the other hand we solved the DSM several times in a myopic fashion taking into account the current travel times respectively. A designated run time limit of 10 seconds per time interval was used in order to solve the DSM using VNS.

The results obtained represent average values over five independent runs per testcase. Fig. 2 shows the average solutions (dotted line) obtained by the VNS for the DSM if solved in a naive way (i.e. when assuming fixed average travel times). The DSM has been solved once for the entire planning horizon using average travel times only. Afterwards we evaluated the resulting solutions using the current travel times in order to access the solutions’ robustness to time-dependent variations in travel times and coverage radii respectively (dashed line). The obtained solutions are compatible during off-peak hours but fail to perform well during peak hours. This clearly shows the importance of time-dependent data. Neglecting time-dependent variations will lead to serious over-estimation of the resulting coverage. In fact during peak hours the resulting objective is overestimated by 24.35%.

Fig. 2
Average solution quality throughout planning horizon when (i) solved in a naive way, (ii) evaluated ex post and (iii) solved myopically.

Furthermore we show the average solutions (solid line) obtained for the mDSM when using the myopic approach and optimizing each point in time independently. The deterioration during peak hours cannot be avoided, but the situation can be improved significantly. By explicitly taking into account time-dependent variations in travel times and speed the solutions obtained using the naive approach can be improved by up to 10.2% .

The VNS in use is capable of obtaining (near-) optimal solutions. See Section 4.2.3 for a detailed comparison of the solutions obtained by VNS as compared to CPLEX.

4.2.2. Effects of level of aggregation

In the most detailed level of aggregation a potential patient corresponds to the set of inhabitants living in a square of length 250 meter. In order to decrease the size of the underlying model we tried to aggregate demand nodes into larger super-nodes. Depending on the level of aggregation a a super-node was obtained by combining squares of a2 original demand nodes. At first sight the solutions obtained using aggregated patients nodes seem to be insensitive to changes in the underlying level of aggregation. However when re-evaluating the solution obtained in terms of the underlying original patient nodes (at the finest level of detail available), it can be shown that on average the solution is overestimated dramatically. This effect is commonly referred to as the optimality error (see Francis et al. (2009) for a detailed analysis of errors associated with aggregation in the context of location models). Fig. 3 shows the resulting misestimation of the obtained solutions when changing the level of aggregation. The level of aggregation a is plotted on the horizontal axis. The resulting number of aggregated demand nodes in shown in parenthesis. When a is set to 2 on average the resulting solution is overestimated by 18.5% (i.e. the corresponding solution for the aggregated problem suggests an objective function value that is 18.35% above the solution, when the corresponding optimized location pattern is evaluated in terms of the original demand nodes at the finest level of detail). When further increasing the level of aggregation to 5 the resulting solution will be overestimated by 26.7%. In order not to misestimate the resulting quality of the solution and get an adequate level of realism it is essential to use the data at the finest level of detail.

Fig. 3
Overestimation of solution quality with varying level of aggregation a. (The resulting number of aggregated demand nodes is given in parenthesis.)

4.2.3. Solving the double standard model

In order to demonstrate the effectiveness of the proposed VNS algorithm for the DSM (as described in Section 3.1) the problem was first solved using CPLEX. The total run time limit for the execution of the model was set to 10 hours. All relevant results can be found in Table 1. The first two columns indicate the test instance (n) as well as the number of potential waiting locations (|W|). The solution (Fmax), the resulting coverage (C(Fmax)), the best bound (bmin) as well as the time necessary for finding it (tmax) are shown in the first part of the table. The problem then was solved using VNS. The run time limit was set to 10 seconds. The best and average solutions found are indicated in the two columns labeled Fmax and Favg respectively. The best solutions found are italicised. The column headed by C(Favg) denotes the average coverage, measured in terms of the percentage of all inhabitants that are covered by at least two vehicles. The necessary run times (in seconds) until the best solution was found are given by tavg. Because of the random nature of the proposed algorithm five independent test runs, using a different stream of random numbers, were executed per instance. As a benchmark value an upper bound on the possible coverage, assuming that an ambulance is located at every location (i.e. p = [mid ]W[mid ]), is given in the column headed by C¯.

Table 1
VNS vs. CPLEX for DSM.

Please note that the value of the objective function (F) is made up by several components. The original objective is to optimize coverage. Violating constraints types 2, 3 and 10 would lead to a penalization in the objective function value as indicated by Eqs. (15)–(17). The DSM focuses on one single time period only. Hence no relocations and penalties therefore will occur.

The results show that the implemented VNS is a robust algorithm finding high quality solutions in a reasonable amount of run time. Given the short run time limit of 10 seconds per instance for the VNS the algorithm was able to find the same solution as CPLEX for the smaller instances 1 and 2. For the remaining two instances the best solutions found by VNS within a couple of seconds outperformed the ones found by CPLEX in ten hours. Please note that the resulting coverage is almost equivalent to the value of the objective function obtained, as the penalties associated with the three aforementioned soft constraints are very small.

4.2.4. Solving the multi-period double standard model

One of the drawbacks of the single-period DSM formulations is that the resulting number of relocations is not explicitly considered and most likely will result in a high number of relocations. Obviously the location problem at hand cannot be solved independently at various points in time. Hence the mDSM, considering the single-period DSM-approach for several points in time plus all resulting relocations between time periods, has been solved using both CPLEX and VNS (as described in Section 3.2). Table 2 shows the results obtained. In order to emphasize the effectiveness of the proposed algorithm an experiment was set up in which the entire time horizon corresponding to one single day (24 hours, starting from midnight) was equally split into six time periods, each of length four hours. The total run time designated for the execution of VNS was set to 60 seconds. The penalty β for relocating vehicles was set to 10000. Hence relocating a vehicle would be considered beneficial if an additional number of 10,000 (equivalent to 0.58 % of the total population) inhabitants would be covered twice within r1. Please note that β is independent on the time necessary to relocate the vehicle or the distance involved. For a more detailed evaluation of the choice of β see Table 4. The penalties γ1, γ2 and γ3 for the violation of the relaxed constraints were set to 2, 0.5 and 0.25 respectively. The problem at hand was also solved using CPLEX, whose execution was aborted after ten hours. We show the best bound (bmin), best solution (Fmax), the consequential coverage (C(Fmax)) as well as the resulting number of relocations (rmax) obtained by CPLEX. The results obtained by means of VNS are shown in the last five columns. The best and average solution obtained can be found in the column labeled Fmax and Favg respectively. The average coverage is denoted by C(Favg). The average run times (in seconds) until solutions have been found using VNS is denoted by tavg. Again the VNS was executed five times per instance and the results have been averaged accordingly. The average resulting number of relocations per day is denoted by ravg. The best solutions obtained are italicised.

Table 2
VNS vs. CPLEX for mDSM.
Table 4
Solution and number of relocations for mDSM depending on β.

The mDSM cannot be solved by means of CPLEX in a reasonable amount of run time. For easier test instances 1 and 2 (where the number of potential locations is set to 16 and 51 respectively) the solution obtained by CPLEX within 10 hours is slightly (less than 0.26%) better then the best solution obtained by VNS within one minute. For the larger instances however (with 94 and 163 potential waiting sites) CPLEX fails to find meaningful solutions. The negative values can be explained by the severe violation of Constraints (2, 3 and 10, which leads to a high penalization in the objective function value due to Eqs. (15)–(17). The maximum gap between the best and average solution found by VNS is as small as 0.03% (0.6%) for the smaller (larger) instances. The maximum gap between the best bound found by CPLEX within 10 hours and the best solution found by our VNS is as small as 3.4%. This clearly indicates that the proposed algorithm is highly robust and works extremely well for the problem under consideration. One can clearly see that the coverage obtained deviates significantly from the value of the objective function. This is due to the fact that the imposed coverage standards can not be satisfied, when considering the actual time-dependent travel times and the resulting changes in coverage throughout the day. When considering only average travel times (as done in Section 4.2.3) it seems misleadingly that those violations would not be an issue. Hence one thinks oneself safe ignoring time-dependent variations and the imposed coverage standards can not be met using the true traffic situation.

4.2.5. Spatial patterns of solution

The capital of Vienna is located in the north-east of Austria. The shape of the city can be approximated by a circle. The majority of the population lives close to the center of the city, whereas the outskirts of the city are less densely populated. Most of the inhabitants (83.6%) live on the south-western side of the river Danube. On average the speed along streets close to the center of the city is lower than for the rest of the city. Fig. 4(a) and (b) depict the traffic situation (in terms of the prevailing speeds) during peak and off-peak hours. Areas with lower average travel times are shaded in light gray. These figures also shows a typical solution to testcase 4, where the location of vehicles are indicated by dark squares. During peak hours the center of the city tends to be heavily congested, resulting in an even larger decrease of travel times downtown. In order to guarantee an acceptable level of coverage during peak hours vehicles should be relocated towards the city center, however during off-peak hours the traffic situation downtown recovers and vehicles tend not to be concentrated on the center of the city only, but are also located in more remote areas.

Fig. 4
Spatial pattern of solution and traffic situation during (off-) peak hours.

4.2.6. Myopic vs. multi-period double standard model solution

We show that the quality of the solutions obtained can be improved significantly by explicitly taking into account time-dependent variations in travel time and the resulting loss of coverage. When locating vehicles in an anticipatory manner, the resulting number of relocations can be improved, while keeping the quality of the solution from deteriorating too much. Table 3 compares the solutions obtained when solving the location problem in a myopic fashion, compared to the solution of the mDSM. The planning horizon of one day (24 hours) was equally split into 6 time intervals of length 4 hours each. All solutions have been obtained by means of VNS. The results shown are averaged over all 4 test instances, each having been executed five times independently. The myopic solution obtained is shown in column Favg. Note that for solving the model in a myopic fashion the static location problem has been solved independently for each time interval, taking into account the prevailing travel times respectively. The total run time limit was set to 10 seconds per time interval. Column ravg shows the average number of resulting relocations, which had been evaluated ex post by solving a simple transportation problem. When solving the mDSM however the problem was only solved once, while explicitly taking into account the resulting number of relocations during the stage of optimization. The penalty value β for relocations was set to 10000. The resulting average values of the objective function per time interval with (without) taking into account the cost for relocating vehicles is shown in column Favg(FavgnoR). The average total number of relocations per day can be reduced from 20.9 to 10.5, which corresponds to a decrease of 50.0%. The quality of the solution (ignoring the costs for relocations) only deteriorates marginally by 0.36%.

Table 3
Solution myopic DSM vs. mDSM.

4.2.7. Effects of the choice of the penalty value for relocations (β)

In order to take into account time-dependent variations and the resulting relocations of vehicles explicitly the following experiment was conducted. A total run time limit of 10 seconds was set for the execution of VNS. The resulting average solution obtained, which was averaged over five independent runs per test case, is shown in Fig. 5. The mDSM (using the approach described in Section 3.2) was solved given different values for β. The penalty value for relocating vehicles was varied between 0 and 150,000 respectively. For generating the initial solutions for the mDSM a total run time limit of 0.5 seconds was set. We have plotted the average solution (Favg) with respect to the prevailing penalty value β. Obviously when the costs for relocating vehicles is set to 0, the solution approaches the one obtained when solving the mDSM in a myopic fashion. The higher relocations of vehicles will be penalized, the less frequent these relocations will happen, which will lead to a deterioration of the solution.

Fig. 5
Average solution (Favg) with respect to varying cost per relocation (β).

If the penalty value β for relocating vehicles is set to zero, the solution obtained approaches the one obtained if the model is solved in a myopic fashion, i.e. independently at designated times, without taking into account resulting relocations during the stage of optimization explicitly. The higher relocations will be penalized, the lower the amount of relocations that are going to take place. Similarly also the quality of solution decreases. Please note that β indicates the additional number of inhabitants that would need to be covered twice within r1 in order to justify an additional relocation. By reducing β from 100,000 to 25,000 the solution improves from 8.85 × 106 to 9.07 × 106.

A more detailed overview on the effects of parameter β is shown in Table 4. The average solution quality throughout the day (Favg), as well as the resulting coverage (C(Favg)) and average number of reallocations (ravg) are shown. The total run time limit was set to ten seconds. The shown values are averages which have been obtained from five independent test runs.

5. Conclusions and outlook

The availability of FCD allowed us to take advantage of time-dependent data, analyze their benefits, develop new models and design innovative solution concepts for the new problem at hand. Furthermore we showed that ignoring time-dependent information can lead to misleading conclusions. Especially when it comes to meeting coverage standards one tends to think oneself safe.

We have extended the single-period DSM for the allocation of a fleet of ambulances to a set of potential waiting locations, such that the resulting coverage can be maximized. In the first step the single-period formulation has been extended in terms of capacity considerations for vehicles. When solving the DSM one tries to optimize coverage, which is usually measured in terms of potential patients that can be reached within a predefined time limit. The time necessary to reach patients in case of an emergency depends on the prevailing speed of the vehicles in the network, which in turn is highly variable throughout the day. Hence solving the DSM only once taking into account current or average travel times is not satisfactory. Therefore we developed a formulation for the mDSM, a multi-period version of the DSM, which explicitly takes into account time-dependent variations of travel times and the resulting changes with respect to coverage. We allow vehicles to be repositioned in order to respond to changing coverage circumstances throughout the day in an anticipatory manner. With the mDSM we manage to optimize the tradeoff between the coverage at different point in times and the resulting number of relocations.

A metaheuristic algorithm based on VNS has been developed and tested using real-world data from the city of Vienna. The total population has been clustered in terms of 4000 demand locations. The number of potential waiting sites of the ambulances was varied between 16 and 163 in order to place a fleet of 14 vehicles. The proposed algorithm using VNS for solving the DSM works extremely well, given the combinatorial complexity of the problem at hand. On average it took only 5 seconds to find a solution which was at least as good as the ones found by CPLEX within 10 hours. The mDSM cannot be solved exactly using CPLEX in a reasonable amount of run time. Good solutions have been found using VNS. But other local search based (meta-) heuristics may work as well. The proposed VNS for the mDSM allows both a diversification and intensification strategy. Location patterns of consecutive time periods that are already good in terms of the resulting number of relocations are tried to be improved in terms of the resulting coverage and vice versa.

Especially in areas with high variations in travel speed and times throughout the day it is essential to consider these variations explicitly. This kind of data (FCD) is readily available and its highly important to take advantage of this knowledge in order to build real-life models, as the coverage will be interpreted misleadingly otherwise. By taking into account these variations the quality of the solution can be improved by up to 10%. In order to achieve this improvement vehicles should not be located at the same locations throughout the entire day. Rather they should be repositioned in order to handle time-dependent variations in coverage. We have shown that relocating vehicles reactively can help to improve the coverage standards during the day. When solving the problem in a myopic fashion on average 21.1 vehicles need to be relocated (see Table 4, where β = 0). The quality of the solution – in terms of the resulting average coverage however – on average only decreases slightly if the resulting average number of relocations is cut in half (see Table 4, where β = 10,000). By allowing only 10 relocations per day in a mDSM framework, the quality of the solution on average only deviated by 0.2% from the myopic solution.

So far this approach is based on the static location problem, taking into account time-dependent variations of travel times throughout the course of the day. In the future we would like to also consider this problem in a dynamic setting, where emergency calls occur and vehicles need to be dispatched in order to cope with their demand respectively. So far we have used the number of inhabitants as a proxy for the demand in terms of potential patients. In the future we are planning to incorporate temporal and spatial variations of the requests to be generated.

Acknowledgements

Financial support from the FWF (Translational Research) under Grant L510-N13 is gratefully acknowledged. Special thanks go to the Austrian Institute of Technology for the preparation of FCD-data. For the street network of Vienna the data provided by Teleatlas was used. We would also like to thank two anonymous referees for their valuable comments that considerably helped us to improve the quality of this paper.

References

Bräysy O. A reactive variable neighborhood search for the vehicle routing problem with time windows. INFORMS Journal on Computing. 2002;15(4):347–368.
Brimberg J., Hansen P., Mladenović N., Taillard E.D. Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem. Operations Research. 2000;48(3):444–460.
Brotcorne L., Laporte G., Semet F. Ambulance location and relocation models. European Journal of Operational Research. 2003;147(3):451–463.
Budge S., Ingolfsson A., Zerom D. Empirical analysis of ambulance travel times: The case of calgary emergency medical services. Management Science. 2010;56(4):716–723.
Church R., ReVelle C. The maximal covering location problem. Papers in Regional Science. 1974;32(1):101–118.
Crainic T.G., Gendreau M., Hansen P., Mladenović N. Cooperative parallel variable neighborhood search for the p-median. Journal of Heuristics. 2004;10(3):293–314.
Daskin M.S. A maximum expected covering location model: Formulation, properties and heuristic solution. Transportation Science. 1983;17(1):48–70.
Doerner K.F., Gutjahr W.J., Hartl R.F., Karall M., Reimann M. Heuristic solution of an extended double-coverage ambulance location problem for Austria. Central European Journal of Operations Research. 2005;13(4):325–340.
Donati A.V., Montemanni R., Casagrande R., Rizzoli A.E., Gambardella L.M. Time-dependent vehicle routing problem with a multi ant colony system. European Journal of Operational Research. 2008;185(3):1174–1191.
Donati, A.V., Montemanni, R., Gambardella, L.M., Rizzoli, A.E., 2003. Integration of a robust shortest path algorithm with a time-dependent vehicle routing model and applications. In: 2003 IEEE International Symposium on Computational Intelligence for Measurement Systems and Applications, CIMSA’03, pp. 26–31.
Fleischmann B., Gietz M., Gnutzmann S. Time-varying travel times in vehicle routing. Transportation Science. 2004;38(2):160–173.
Fleischmann B., Gnutzmann S., Sandvoss E. Dynamic vehicle routing based on online traffic information. Transportation Science. 2004;38(4):420–433.
Francis R.L., Lowe T.J., Rayco M.B., Tamir A. Aggregation error for location models: Survey and analysis. Annals of Operations Research. 2009;167(1):171–208.
Gendreau M., Laporte G., Semet F. Solving an ambulance location model by tabu search. Location Science. 1997;5(2):75–88.
Gendreau M., Laporte G., Semet F. A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel Computing. 2001;27(12):1641–1653.
Gendreau M., Laporte G., Semet F. The maximal expected coverage relocation problem for emergency vehicles. Journal of the Operational Research Society. 2006;57:22–28.
Hamming R.W. Error detecting and error correcting codes. The Bell System Technical Journal. 1950;29(2):147–160.
Hansen P., Mladenović N. Variable neighborhood search. Computers & Operations Research. 1997;24(11):1097–1100.
Hansen P., Mladenović N. Variable neighborhood search: Principles and applications. European Journal of Operational Research. 2001;130(3):449–467.
Hill A.V., Benton W.C. Modelling intra-city time-dependent travel speeds for vehicle scheduling problems. The Journal of the Operational Research Society. 1992;43(4):343–351.
Hogan K., ReVelle C. Concepts and applications of backup coverage. Management Science. 1986;32(11):1434–1444.
Horn M.E.T. Efficient modeling of travel in networks with time-varying link speeds. Networks. 2000;36(2):80–90.
Ichoua S., Gendreau M., Potvin J.-Y. Vehicle dispatching with time-dependent travel times. European Journal of Operational Research. 2003;144(2):379–396.
Kolesar P., Walker W., Hausner J. Determining the relation between fire engine travel times and travel distances in New York City. Operations Research. 1975;23(4):614–627.
Laborczi, P., Linauer, M., Nowotny, B., 2006. Travel time estimation based on incomplete probe car information. In: 13th World Congress on Intelligent Transport Systems, London, United Kingdom.
Laporte G., Louveaux F.V., Semet F., Thirion A. Innovations in distribution logistics. Springer; 2009. Applications of the double standard model for ambulance location; pp. 235–249. (Lecture Notes in Economics and Mathematical Systems).
Linauer, M., Nowotny, B., 2006. Availability and quality of floating car data on intraurban arterials and motorways in Austria. In: Emerging Technologies Workshop, International Symposium of Transport Simulation, Lausanne, Switzerland.
Malandraki C., Daskin M.S. Time-dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation Science. 1992;26(3):185–200.
Mladenović N., Labbé M., Hansen P. Solving the p-center problem with tabu search and variable neighborhood search. Networks. 2003;42(1):48–64.
Parragh S.N., Doerner K.F., Hartl R.F. Variable neighborhood search for the dial-a-ride problem. Computers & Operations Research. 2010;37:1129–1138.
Polacek M., Hartl R.F., Doerner K.F., Reimann M. A variable neighborhood search for the multi depot vehicle routing problem with time windows. Journal of Heuristics. 2004;10(6):613–627.
Rajagopalan H.K., Saydam C., Xiao J. A multi-period set covering location model for dynamic redeployment of ambulances. Computers & Operations Research. 2008;35(3):814–826.
Reinthaler, M., Nowotny, B., Weichenmeier, F., Hildebrandt, R., 2007. Evaluation of speed estimation by floating car data within the research project Dmotion. In: 14th World Congress on Intelligent Transport Systems, Beijing, China.
Repede J.F., J Bernardo J. Developing and validating a decision support system for location emergency medical vehicles in Louisville, Kentucky. European Journal of Operational Research. 1994;75(3):567–581.
Thirion, A., 2006. Modéles de localisation et de réallocation d’ambulances. Application aux communes en provinces de Namur et Brabant Wallon. Ph.D. Thesis, Facultés Universitaires Notre-Dame de la Paix, Namur, Belgium.
Toregas C., Swain R., ReVelle C., Bergman L. The location of emergency service facilities. Operations Research. 1971;19(6):1363–1373.