Introduction

In most major cities, emergency medical services are provided by a fleet of ambulances complemented by physician cars. These are dispatched in addition to an ambulance to a limited number of high-emergency calls requiring the presence of a physician, which include car accidents involving major injuries, some cardiac arrest cases, etc. The physician vehicles must be located at appropriate points in order to provide adequate coverage. Whenever a vehicle is dispatched to a call, it may leave a significant fraction of the population without coverage; it is therefore customary for ambulance services to apply a relocation policy in order to maintain a proper coverage level. Our study is motivated by the problem of locating and relocating physician cars in the Montreal area. It provides a planning tool to optimally relocate these vehicles. While the number of ambulances serving the Montreal area (population: 2.5 million) varies between 40 and 60 depending on the time of the day, only a few physician cars are needed, typically between three and six. As will be seen, this small number makes our approach feasible.

Most available studies on such problems apply to ambulances only and very few address the relocation issue. There has been a marked evolution over the past three decades in the development of ambulance location models and algorithms. Some of the earliest models are the Location Set Covering Problem (LSCP) proposed by Toregas et al¹ and the Maximal Covering Location Problem (MCLP) introduced by Church and ReVelle.² In the LSCP, the aim is to minimize the number of vehicles required to cover a set of demand points. In this model, a point is said to be covered if it can be reached by at least one vehicle within a preset driving time r. The MCLP works with a given number n of vehicles and attempts to cover the largest possible demand. Both models make sense in practice. The first can be used to determine an appropriate fleet size to meet a certain demand whereas the second can help optimally allocate available but insufficient resources. A good compromise between coverage and cost can be reached by solving the MCLM with various values of n and selecting one of the solutions. Several extensions of these two basic models have been proposed by Schilling et al³, Daskin and Stern,⁴ Hogan and ReVelle,⁵ and Gendreau et al.⁶

In practice such static models are inadequate in the sense that their solution is unlikely to provide sufficient coverage once a vehicle is dispatched to a call. One way around this difficulty has been to develop probabilistic models which reflect the fact that emergency vehicles are busy only a fraction of the time and become unavailable once they respond to a call. They must in fact be considered as servers that operate within a queueing system. This line of research was pioneered by Larson.^{7, 8, 9} Well-known probabilistic covering models include the Maximum Expected Covering Problem (MEXCLP) proposed by Daskin,¹⁰ its extensions TIMEXCLP,¹¹ AMEXCLP¹² and QPLSCP,¹³ the Maximal Availability Location Problems (MALP I and MALP II) of ReVelle and Hogan,¹⁴ and the Rel-P Model of Ball and Lin.¹⁵ These models make different assumptions on travel time distribution, on the spatial dependency of vehicle availability, and on desired probabilistic covering thresholds. A third approach is the use of dynamic models. Here, instead of seeking a single solution to a static or probabilistic model, the idea is to dynamically relocate vehicles in real-time as vehicles are dispatched to calls. Each relocation amounts to solving a static model subject to side constraints on vehicle moves. For example, one should avoid relocating too many vehicles at once or moving the same vehicle too often over a short period. An early dynamic model was proposed by Kolesar and Walker¹⁶ for the relocation of fire companies. More recently Gendreau et al¹⁷ have developed a dynamic ambulance relocation model which can be applied in real-time through the use of parallel computing. For surveys of emergency vehicle location and relocation problems, see Marianov and ReVelle¹⁸ and Brotcorne et al.¹⁹

One drawback of dynamic relocation algorithms is the need to compute a new solution whenever a vehicle is dispatched to a call. This can be time consuming or even infeasible when calls arrive in quick succession throughout the day, as was the case in the Island of Montreal ambulance relocation problem studied by Gendreau et al.¹⁷ Since parallel computing is not always a practical option in emergency vehicle dispatching centres, an alternative is to precompute a series of location scenarios for k=1,..., n vehicles which can readily be applied whenever a call is made. This approach will work as long as n is not too large, as is the case in our application.

Our aim is to formulate and solve a dynamic problem arising in the relocation of physician vehicles. Events corresponding to emergency calls occur randomly at discrete time instants during the day. Whenever an event occurs, a vehicle is dispatched to the call location and a fleet relocation may take place. Each solution maximizes coverage given the number of available vehicles. The objective is to maximize the expected coverage over time subject to an upper bound on the number of waiting sites that can be changed at each event. This problem is called the Maximal Expected Coverage Relocation Problem (MECRP). The MECRP will be formulated in the next section, followed by computational results on real-life data, and by some conclusions.

Mathematical model

There are two main ways of solving dynamic optimization problems. The a posteriori approach is the most common: it consists of computing and implementing a new solution whenever an event occurs. This is the strategy used in several dynamic vehicle routing algorithms (see, eg, Gendreau et al²⁰). The main drawback of this approach is that there is not always sufficient time to recompute a solution between two successive events if these occur in quick succession. To alleviate this difficulty, Gendreau et al¹⁷ have proposed an a priori methodology in which several solutions are precomputed in anticipation of future events and the appropriate solution, if available, is implemented whenever an event occurs. This methodology was successfully applied to an ambulance relocation problem in Montreal. It was shown that a precomputed solution was available in more than 95% of events. In the remaining cases the decision was to perform no vehicle relocation and simply wait for the next event to occur. The approach we develop in this study goes further in this direction. It precomputes a unique solution at the beginning of the planning period. This solution provides a full list of waiting sites for each possible event that may occur. What makes this strategy feasible is that the number of system states is relatively small in the application under study.

The MECRP is defined on a directed graph G=(VW, A) where V is the vertex set of demand points and W is a vertex set of potential waiting sites for n|W| emergency vehicles and A is a set of arcs defined on (VW)². To each arc (i, j)A is associated a driving time. Let d_i be the demand at vertex iV. As is often the case in location, it is assumed that the problem is discretized so that d_i may correspond to the population of a zone associated with i, for example, a city block. A vertex iV is said to be covered by a vertex jW whenever the driving time from j to i is less than a prespecified coverage radius r. Denote by W_i the subset of vertices of W covering iV.

It is useful at this stage to recall the classical MCLP formulation for n vehicles. Let x_j be a binary variable equal to 1 if and only if a vehicle is located at jW and let y_i be a binary variable equal to 1 if and only if demand point iV is covered. Denote the solution value by z_n. The MCLP for n vehicles is then:

In this model, constraints (2) mean that vertex iV is covered only if a least one vehicle is located in W_i, and constraints (3) control the number of vehicles used in the solution. A simple relaxation procedure for the MECRP consists of solving MCLP-k for k=1,..., n, and of applying the appropriate solution at each event. The expected solution cost is then _k=1ⁿ q_k z_k, where q_k is the probability of having k available vehicles. If the arrival rate of calls is and the average service rate is , then the probability that a vehicle is available is p=1-/n, where /n corresponds to the busy fraction in MEXCLP¹⁰ and related models. The value of q_k is easily obtained by means of a binomial distribution: .

This relaxation procedure ignores constraints on the number of allowed waiting site changes at each event. To incorporate such constraints, it is useful to view the system as being in a succession of states k over time, where k is the number of available vehicles waiting for calls (k=0,..., n). A given state k is described by binary variables x_jk equal to 1 if and only if a vehicle is located at jW, and by binary variables y_ik equal to 1 if and only if demand point iV is covered by at least one vehicle. We assume that at most one vehicle is dispatched to a call at any event (if the system is in state 0, then obviously no vehicle can be dispatched). When the system moves from state k to state k+1 (if kn-1), at most _k of the current k waiting sites can be changed; in the same vein, when the system moves from state k to state k-1 (if k1), at most _k-1+1 of the current waiting sites can be modified. This follows from the fact that _k-1 sites of configuration k-1 are possibly modified and another site is discarded when going down from state k to state k-1. To avoid multiple counting it is sufficient to keep track of waiting site changes when the system moves from state k to state k+1 (k=1,..., n-1). Hence define binary variables u_jk equal to 1 if and only if jW ceases to be a waiting site when the system moves from state k to state k+1. The MECRP is then:

In this model, constraints (7) and (8) play the same role as constraints (2) and (3) in MCLP-n. Constraints (9), (10) and (13) control the number of waiting site changes when the system moves from state k to state k+1. It is easy to see that MECRP reduces to MCLP-n when q_n=1. The relaxation procedure we have proposed for the MECRP solves this problem optimally whenever _kk for k=1,..., n-1. Note that our formulation does not contain relocation costs, but only upper bounds on the number of waiting site changes. Imposing this rule makes our model tractable although it may adversely affect the expected coverage. However, limiting the number of vehicle relocations is important in practice for physicians. The same requirement was present in an ambulance relocation problem recently studied by the authors.¹⁷ An alternative rule could have been to impose an upper limit on the relocation distance but because the number of vehicles is rather small, this would have resulted in an even worse expected coverage.

Our model assures there is no direct cost in implementing a new solution when the system moves to a different state. The only information required to maximize expected covered demand is the proportion of time the system is in each state, as opposed to state counts which would have been needed if transition costs had been used. To apply MECRP in a dynamic context it suffices to solve this problem only once and to implement the location decisions given by the variables x_jk whenever the system is in state k: one of the vehicles is assigned to a call and the relocation of the remaining k-1 vehicles from their current to their new waiting sites is achieved by solving a transportation problem.

Computational results

The integer program (6), 7, 8, 9, 10, 11, 12 and (13) was run on CPLEX 7.0 on a Sun Ultra 5 Station (400 MHz). We first executed the model using the following data corresponding to the neighbouring cities of Montreal and Laval with |V|=3049, |W|=64, and n=3, 4, 5 and 6. The demand points and the waiting sites are shown in Figure 1. Each of the 3049 demand points iV is the result of an aggregation process and has an associated demand d_i ranging between 2 and 7000. Travel times were computed using a Manhattan metric and a constant vehicle speed of 60 km/h. We used a coverage radius r equal to 8 min. To compute p we used =1.03 and =1.46. These figures were obtained from real data provided by Urgences Santé which runs the emergency medical services in Montreal and Laval. In the data set provided, 869 calls were observed over a 5-week period, yielding an average hourly arrival rate of 1.03. The average service time was 41 min, that is, 60/.

Figure 1.

Demand points and waiting sites in Montreal and Laval.

Full figure and legend (54K)

The model was solved for the following values of _k controlling the number of waiting site changes: _k=0, _k=1, _k=k/2⌉, and _k=k. Figure 2 and Table 1 provide the waiting locations suggested by the model for n=3, 4, 5 and 6, and k=1, ..., n. Expected coverage ratios equal to _k=1ⁿ_iVd_iq_ky_ik/_iVd_i and computation times are provided in Table 2.

Figure 2.

Waiting sites indices used in Table 1.

Full figure and legend (66K)

Table 1 - Waiting sites for several values of n and k.

Full table

Table 2 - Expected coverage ratios (first line) and computation times in minutes (second line).

Full table

As expected, the column _k=0 of Table 1 displays embedded waiting site sets since all sites present at state k are also used at state k+1 (kn-1). In addition, the expected coverage ratio increases as _k becomes larger but no difference is observed when going from _k=k/2⌉ to _k=k; in other words no added benefit is obtained by letting more than half of all waiting sites to change. With one exception (n=6 and _k=0), sites number 5 and 9 are always selected. This makes sense since these locations are located in one of the most densely populated area of Montreal (see Figure 1). When n increases more excentric sites are selected. The choice of site 28 when n=6 and _k=0 is explained by the multiplicity of equivalent optimal solutions for this case.

Table 2 also indicates that depending on n and a_k, computation times vary between less than one minute for n=3 to slightly more than three hours for n=6. These rather important computing times are due to the very large number of binary variables in the MECRP model. However, one should bear in mind that this model is used as a medium-term planning tool (eg, a season) and is not frequently solved.

Simulations were then performed using the results of the model for n=3, 4, 5, 6 and the actual calls received by Urgences Santé over the five week period. We distinguish between the 'static case' and '_k=0'. In the static case no vehicle is relocated. For example, if there are three waiting sites 5, 9 and 20 and the vehicle located at site 5 answer a call, then the remaining two vehicles do not move. Under the policy _k=0, the waiting sites do not change but some vehicles may move. Using the same example, the vehicle located at 20 moves to site 5. In other words, waiting sites are modified as prescribed by the solution whenever a call occurs and a transportation problem is solved to determine vehicle relocations. The vehicle dispatched to answer a call is always the closest one. The following statistics on the system performance were compiled:

1. average coverage ratio;
2. average response time (min);
3. maximum response time (min);
4. average repositioning distance (km);
5. maximum repositioning distance (km);
6. number of calls delayed out of 869 (these are calls that could not be immediately served because no physician car was available);
7. proportion of calls covered within 8 min.

Simulation results reported in Table 3 indicate that applying a relocation policy is better than using a static approach. Thus, in our simulations, moving from the static case to _k=0 decreases the average response time between 3.33% (for n=6) and 8.88% (for n=5); similarly the proportion of calls covered within 8 min increases from 5.29% (for n=4) to 8.79% (for n=5). Allowing even more relocations produces more dramatic results; when _k=k/2⌉ theaverage response time is reduced between 7.63% (for n=4) and 13.67% (for n=5); similarly the proportion of calls covered within 8 min increases from 14.72% (for n=6) to 22.80% (for n=5). Note, however, that allowing up to k waiting site relocations does not provide any improvement over the case where k/2⌉ relocations are allowed. One interesting observation is that using n vehicles and allowing all waiting sites to change (_k=k) can have about the same effect as using n+1 vehicles and allowing no vehicle relocation. Thus using five vehicles with _k=k yields a better proportion of calls covered within 8 min (0.684) than using six vehicles without vehicle relocations (0.652). The average response time (7.89 min) is slightly larger in the first case than in the second case (7.82 min). These observations must be interpreted with care since they do not hold for all values of n. It is interesting to see that the average coverage ratios observed in the simulations are consistent with the theoretical values of Table 2, which indicates that our model matches reality.

Table 3 - Summary of simulation results.

Full table

As expected, when _k increases, the average and maximum repositioning distances decrease. This is not directly controlled by the model but results from the fact that allowing more vehicles to relocate will result in a shorter relocation distance for each of them. This phenomenon was also observed in a previous ambulance relocation study.¹⁷ Finally, the average and maximum response times also decrease when _k increases. This is an indirect consequence of our model because allowing more waiting site relocations also increases the proportion of the demand covered within a preset time standard and hence decreases the average response time.

Conclusions

We have formulated and solved a dynamic relocation problem arising in the management of emergency vehicles. The aim was to provide a relocation policy ensuring an adequate expected demand coverage while controlling the number of relocations. In contexts where the number of vehicles is relatively small, as is the case of physicians cars, the problem can be modelled and solved directly using a standard optimizer like CPLEX. Simulations conducted using a 5-week sample of calls in Montreal and Laval confirm the feasibility of the proposed approach. Our results clearly demonstrate the benefits of relocating emergency vehicles in terms of average response time and proportion of calls covered within 8 min. To our knowledge, very few studies have addressed dynamic emergency vehicle relocation problems. Contrary to what was done by Gendreau et al¹⁷ and to the current practice in dynamic vehicle routing,²⁰ the dynamic problem we have studied is rather interesting in that it can be solved optimally through the execution of a single integer linear program.

References

1. Toregas C, Swain R, ReVelle CS and Bergman L (1971). The location of emergency service facilities. Opns Res 19: 1363–1373.
2. Church RL and ReVelle CS (1974). The maximal covering location problem. Papers Regional Sci Assoc 32: 101–118. | Article |
3. Schilling DA et al. (1979). The TEAM/FLEET models for simultaneous facility and equipment sitting. Transportation Sci 13: 163–175.
4. Daskin MS and Stern EH (1981). A hierarchical objective set covering model for emergency medical service vehicle deployment. Transportation Sci 15: 137–152.
5. Hogan K and ReVelle CS (1986). Concept and applications of backup coverage. Mngt Sci 32: 1434–1444.
6. Gendreau M, Laporte G and Semet F (1997). Solving an ambulance location model by tabu search. Location Sci 5: 75–88. | Article |
7. Larson RC (1972). Urban Police Patrol Analysis. The MIT Press: Cambridge, MA.
8. Larson RC (1974). A hypercube queuing model for facility location and redistricting in urban emergency services. Comput Opns Res 1: 67–75. | Article |
9. Larson RC (1975). Approximating the performance of emergency service systems. Opns Res 23: 845–868.
10. Daskin MS (1983). The maximal expected covering location model: formulation, properties, and heuristic solution. Transportation Sci 17: 48–70.
11. Repede JF and Bernardo JJ (1994). Developing and validating a decision support system for locating emergency medical vehicles in Louisville, Kentucky. Eur J Opl Res 75: 567–581. | Article |
12. Batta R, Dolan JM and Krishnamorthy NN (1989). The maximal expected covering location model revisited. Transportation Sci 23: 277–287.
13. Marianov V and ReVelle CS (1994). The queuing probabilistic location set covering problem and some extensions. Socio-Economic Plann Sci 28: 167–178. | Article |
14. ReVelle CS and Hogan K (1989). The maximum availability location problem. Transportation Sci 23: 192–200.
15. Ball MO and Lin FL (1993). A reliability model applied to emergency service vehicle location. Opns Res 41: 18–36.
16. Kolesar P and Walker WE (1974). An algorithm for the dynamic relocation of fire companies. Opns Res 22: 249–274.
17. Gendreau M, Laporte G and Semet F (2001). A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel Comput 27: 1641–1653. | Article |
18. Marianov V and ReVelle CS (1995). Siting emergency services. In: Drezner Z (ed). Facility Location: A Survey of Applications and Methods. Springer-Verlag, New York, pp 199–223.
19. Brotcorne L, Laporte G and Semet F (2003). Ambulance location and relocation models. Eur J Opl Res 147: 451–463. | Article |
20. Gendreau M, Guertin F, Potvin J-Y and Taillard É (1999). Parallel tabu search for real-time vehicle routing and dispatching. Transportation Sci 33: 381–390.

Acknowledgements

This work was partly supported by the Fonds de la recherche en santé du Québec under Grant 980861, by the Canadian Natural Sciences and Engineering Council under Grants OGP0038816, OGP0039682 and by the Région Nord-Pas de Calais, France. This support is gratefully acknowledged. Thanks are also due to Émilie Frot and Geneviève Hernu for their help with programming and to Marko Blais from Urgences Santé who provided some data. We are also grateful to the referees for their valuable comments.