Home | About | Journals | Submit | Contact Us | Français |

**|**Elsevier Sponsored Documents**|**PMC2982752

Formats

Article sections

- Abstract
- 1. Introduction
- 2. Problem formulation
- 3. Variable neighborhood search
- 4. Computational experiments
- 5. Conclusions and outlook
- References

Authors

Related links

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

PMCID: PMC2982752

Department of Business Administration, University of Vienna, Bruenner Strasse 72, 1210 Vienna, Austria

Verena Schmid: ta.ca.eivinu@dimhcS.anereV; Karl F. Doerner: ta.ca.eivinu@renreoD.lraK

Received 2009 August 7; Accepted 2010 June 22.

Copyright © 2010 Elsevier B.V.

Open Access under CC BY-NC-ND 3.0 license

This document was posted here by permission of the publisher.
At the time of the deposit, it included all changes made during peer review,
copy editing, and publishing. The U. S. National Library of Medicine is responsible
for all links within the document and for incorporating any publisher-supplied
amendments or retractions issued subsequently. The published journal article,
guaranteed
to be such by Elsevier, is available for free, on ScienceDirect, at: http://dx.doi.org/10.1016/j.ejor.2010.06.033

This article has been cited by other articles in PMC.

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%.

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.

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)).

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
*r*_{1} time units and all demand
points need to be covered by at least one vehicle within
*r*_{2} time units, where
*r*_{1} < *r*_{2}.
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.

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).

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.

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)).

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.

Let $\mathcal{W}$ be the set of potential vehicle locations. The set of demand
locations is denoted by $\mathcal{V}$. The problem itself is defined on a graph $G=(\mathcal{V}\cup \mathcal{W}\text{,}\mathcal{E})$, where $\mathcal{E}$ is the set of edges $\{(j\text{,}i):j\in \mathcal{W}\text{,}i\in \mathcal{V}\}$, each associated with travel time ${s}_{\mathit{ji}}^{t}$ prevailing at time *t*. Each demand location
$i\in \mathcal{V}$ is associated with a corresponding demand value
*d*_{i}. The goal
is to locate *p* vehicles among all potential vehicle
locations, such that all demand locations can be reached within
*r*_{2} time units and
*α* % of the population (0 < *α* < 1) can be reached within
*r*_{1} (*r*_{1} < *r*_{2}) time units at all
times $t\in \mathcal{T}$, where $\mathcal{T}=\{1\text{,}\dots \text{,}T\}$. No more than
*p*_{j}
vehicles can be located at location $j\in \mathcal{W}$ at any time. The objective is to maximize the demand covered by at
least two vehicles within a radius of *r*_{1}
at all $t\in \mathcal{T}$. The number of vehicles to be located at vehicle location $j\phantom{\rule{0.35em}{0ex}}(j\in \mathcal{W})$ in $t\in \mathcal{T}$ is denoted by ${y}_{j}^{t}$. The binary decision variable ${x}_{i}^{k\text{,}t}$ will be equal to one if the demand at vertex $i\in \mathcal{V}$ is covered *k* times
(*k* = 1, 2) at time *t*. Let ${W}_{i}^{1\text{,}t}\phantom{\rule{0.35em}{0ex}}({W}_{i}^{2\text{,}t})$ be the set of vehicle locations from which patient
*i* can be reached within radius
*r*_{1}
(*r*_{2}) at time
*t*. $({W}_{i}^{k\text{,}t}=\{j\in \mathcal{W}:{s}_{\mathit{ji}}^{t}\u2a7d{r}_{k}\text{;}k=1\text{,}2\})$. The set of patients that can be reached within
*r*_{2} time units by a vehicle located
at location $j\in \mathcal{W}$ is denoted by ${V}_{j}^{2\text{,}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 ${\mathcal{T}}^{\prime}$. The number of vehicles that are supposed to be relocated from
location *i* to $j\phantom{\rule{0.35em}{0ex}}(i\text{,}j\in \mathcal{W})$ between *t* and *t* + 1 (*t* *T*′) is denoted by
${r}_{\mathit{ij}}^{t}$. 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
${r}_{\mathit{ij}}^{T}$.

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 $i\in \mathcal{V}$ that is covered by a vehicle located at $j\in \mathcal{W}$ in *t* is denoted by ${z}_{\mathit{ij}}^{t}$.

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 *r*_{1}, 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
*β*.

$$\mathrm{max}\phantom{\rule{1em}{0ex}}f(x)=\sum _{t\in T}\left(\sum _{i\in \mathcal{V}}{d}_{i}{x}_{i}^{2\text{,}t}-\beta \sum _{i\text{,}j\in \mathcal{W}}{r}_{\mathit{ij}}^{t}\right)\text{,}$$

(1)

$$\text{s.t.}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.35em}{0ex}}\sum _{j\in {\mathcal{W}}_{i}^{2\text{,}t}}{y}_{j}^{t}\u2a7e1\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\forall i\in \mathcal{V}\text{,}\phantom{\rule{1em}{0ex}}t\in \mathcal{T}\text{,}$$

(2)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\sum _{i\in \mathcal{V}}{d}_{i}{x}_{i}^{1\text{,}t}\u2a7e\alpha \sum _{i\in \mathcal{V}}{d}_{i}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.12em}{0ex}}\forall t\in \mathcal{T}\text{,}$$

(3)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\sum _{j\in {\mathcal{W}}_{i}^{1\text{,}t}}{y}_{j}^{t}\u2a7e{x}_{i}^{1\text{,}t}+{x}_{i}^{2\text{,}t}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.35em}{0ex}}\forall i\in \mathcal{V}\text{,}\phantom{\rule{1em}{0ex}}t\in \mathcal{T}\text{,}$$

(4)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}{x}_{i}^{2\text{,}t}\u2a7e{x}_{i}^{1\text{,}t}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.25em}{0ex}}\forall i\in \mathcal{V}\text{,}\phantom{\rule{1em}{0ex}}t\in \mathcal{T}\text{,}$$

(5)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\sum _{j\in \mathcal{W}}{y}_{j}^{t}=p\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.25em}{0ex}}\forall t\in \mathcal{T}\text{,}$$

(6)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}{y}_{j}^{t}\u2a7d{p}_{j}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.35em}{0ex}}\forall j\in \mathcal{W}\text{,}\phantom{\rule{1em}{0ex}}t\in \mathcal{T}\text{,}$$

(7)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}{y}_{j}^{t}+\sum _{i\in \mathcal{W}}{r}_{\mathit{ij}}^{t}-\sum _{i\in W}{r}_{\mathit{ji}}^{t}={y}_{j}^{t+1}\phantom{\rule{2em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.35em}{0ex}}\forall j\in \mathcal{W}\text{,}\phantom{\rule{1em}{0ex}}t\in {\mathcal{T}}^{\prime}\text{,}$$

(8)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}{y}_{j}^{T}+\sum _{i\in \mathcal{W}}{r}_{\mathit{ij}}^{T}-\sum _{i\in W}{r}_{\mathit{ji}}^{T}={y}_{j}^{1}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.35em}{0ex}}\forall j\in \mathcal{W}\text{,}$$

(9)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\sum _{i\in {\mathcal{V}}_{j}^{2\text{,}t}}{z}_{\mathit{ij}}^{t}\u2a7d\omega {p}_{j}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{0.35em}{0ex}}\forall j\in \mathcal{W}\text{,}\phantom{\rule{1em}{0ex}}t\in \mathcal{T}\text{,}$$

(10)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\sum _{j\in {\mathcal{W}}_{i}^{2\text{,}t}}{z}_{\mathit{ij}}^{t}={d}_{i}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{0.35em}{0ex}}\forall i\in \mathcal{V}\text{,}\phantom{\rule{1em}{0ex}}t\in \mathcal{T}\text{,}$$

(11)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}{x}_{i}^{k\text{,}t}\in \{0\text{,}1\}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.35em}{0ex}}\forall i\in \mathcal{V}\text{,}\phantom{\rule{1em}{0ex}}t\in \mathcal{T}\text{,}\phantom{\rule{1em}{0ex}}k\in \{1\text{,}\phantom{\rule{0.12em}{0ex}}2\}\text{,}$$

(12)

$$\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}{y}_{j}^{t}\phantom{\rule{0.35em}{0ex}}\mathrm{integer}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.35em}{0ex}}\phantom{\rule{0.35em}{0ex}}\forall j\in \mathcal{W}\text{,}\phantom{\rule{1em}{0ex}}t\in \mathcal{T}\text{.}$$

(13)

Throughout the planning horizon $\mathcal{T}$ a DSM has to be considered simultaneously at every instance
$t\in \mathcal{T}$, while considering the prevailing travel times. Constraints
(2) ensure that every demand
location *i* will be covered at least once within
*r*_{2} at every point in time
*t*. Constraints (3) ensure that *α*% of the total
demand is covered within *r*_{1} 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 $i\in \mathcal{V}$. 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 ${x}_{i}^{k\text{,}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*}.

$$\mathrm{max}F(x)=f(x)-\sum _{t\in \mathcal{T}}({\gamma}_{1}{f}_{1}^{t}(x)+{\gamma}_{2}{f}_{2}^{t}(x)+{\gamma}_{3}{f}_{3}^{t}(x))\text{,}$$

(14)

where

$${f}_{1}^{t}(x)=\sum _{i\in \mathcal{V}}\left\{{\left(1-\sum _{j\in {\mathcal{W}}_{i}^{2\text{,}t}}{y}_{j}^{t}\right)}^{+}\right\}\phantom{\rule{1em}{0ex}}\forall t\in \mathcal{T}\text{,}$$

(15)

$${f}_{2}^{t}(x)={\left(\alpha \sum _{i\in \mathcal{V}}{d}_{i}-\sum _{i\in \mathcal{V}}{d}_{i}{x}_{i}^{1\text{,}t}\right)}^{+}\phantom{\rule{1em}{0ex}}\forall t\in \mathcal{T}\text{,}$$

(16)

$${f}_{3}^{t}(x)=\sum _{i\in \mathcal{V}}\left\{{({d}_{i}-\sum _{j\in {\mathcal{W}}_{i}^{2\text{,}t}}{z}_{\mathit{ij}})}^{+}\right\}\phantom{\rule{1em}{0ex}}\forall t\in \mathcal{T}\text{.}$$

(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.

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
*N*_{k}(*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.

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.

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

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

Neighborhood Structures
*N*_{k}
(*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
${\mathcal{S}}^{\prime}$, where $|{\mathcal{S}}^{\prime}|=k-1$.

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.

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.

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 $t\in \mathcal{T}$. 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.

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 *t*_{1}
and *t*_{2} (where
*t*_{2} = *t*_{1} + 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*(*t*_{1}) (*lp*(*t*_{2}))
prevailing at *t*_{1}
(*t*_{2}) will be evaluated and
compared to the solution of the myopic problem
*lp*^{M}(*t*_{1})
(*lp*^{M}(*t*_{2})).
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*(*t*_{1})
to *lp*(*t*_{2})
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
*t*_{1} and
*t*_{2} 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*(*t*_{1})
and
*lp*(*t*_{2}),
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
(*lp*^{M}(*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
*lp*_{1} will be assimilated to
*lp*_{2}. Any neighborhood
*N*_{k}
(*k* = 1 … 3) changes the
number of vehicles placed according to location pattern
*lp*_{1} 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 $\left[\mathit{min}\left({v}_{j}^{{\mathit{lp}}_{1}}\text{,}{v}_{j}^{{\mathit{lp}}_{2}}\right)\text{,}\mathit{max}\left({v}_{j}^{{\mathit{lp}}_{1}}\text{,}{v}_{j}^{{\mathit{lp}}_{2}}\right)\right]$, where ${v}_{j}^{\mathit{lp}}$ 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 ${\mathit{lp}}_{1}^{\ast}$ might have changed, location pattern ${\mathit{lp}}_{1}^{\ast}$ 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.

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
*t*_{1} and
*t*_{2}. 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.

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 $i\in \mathcal{V}$ 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
*r*_{1} (*α*) are set to 10 minutes (95%). The
second coverage radius, *r*_{2}, was set
to 20 minutes. A total number of 14 vehicles had to be located at various
potential waiting sites, each having a capacity ${p}_{j}=1(j\in \mathcal{W})$. For a topographical representation of the four testcases under
consideration see Fig.
1(a)–(d).

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%.

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.

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 *a*^{2} 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.

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 $(|\mathcal{W}|)$. The solution
(*F*_{max}),
the resulting coverage
(*C*(*F*_{max})),
the best bound
(*b*_{min})
as well as the time necessary for finding it
(*t*_{max})
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
*F*_{max}
and *F*_{avg}
respectively. The best solutions found are italicised. The column headed
by
*C*(*F*_{avg})
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
*t*_{avg}.
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* = *W*), is given in the column headed
by $\overline{C}$.

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.

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 *r*_{1}. 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
(*b*_{min}),
best solution
(*F*_{max}),
the consequential coverage
(*C*(*F*_{max}))
as well as the resulting number of relocations
(*r*_{max})
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
*F*_{max}
and *F*_{avg}
respectively. The average coverage is denoted by
*C*(*F*_{avg}).
The average run times (in seconds) until solutions have been found using
VNS is denoted by
*t*_{avg}.
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
*r*_{avg}.
The best solutions obtained are italicised.

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.

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.

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
*F*_{avg}.
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
*r*_{avg}
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 ${F}_{\mathit{avg}}\phantom{\rule{0.35em}{0ex}}({F}_{\mathit{avg}}^{\mathit{noR}})$. 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%.

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
(*F*_{avg})
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.

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
*r*_{1} in order to justify an
additional relocation. By reducing *β* from
100,000 to 25,000 the solution improves from 8.85 × 10^{6} to 9.07 × 10^{6}.

A more detailed overview on the effects of parameter
*β* is shown in Table 4. The average
solution quality throughout the day
(*F*_{avg}),
as well as the resulting coverage
(*C*(*F*_{avg}))
and average number of reallocations
(*r*_{avg})
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.

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.

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.

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.

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |