As part of the STOR604 course at STOR-i, lecturers from around the world come to Lancaster to give a Masterclass in their area of research. In this blog post I’ll be discussing the use of Facility Location Models in the public sector which was introduced to me through a Masterclass given by Laura Albert from the University of Wisconsin-Madison. In particular I’ll be focusing on models that look to optimize the distribution of ambulances in order to maximize patient survival while balancing cost and the number of paramedics required.
Generally, the performance measure used for patient survival is the response time threshold (RTT). In most countries, including the US, an RTT of 8 minutes and 59 seconds is used. This time is based on research of cardiac arrest patients that suggest that a wait time of longer than 9 minutes severely diminishes their chance of survival. Therefore, our problem is where to locate \(p\) ambulances in order to cover the most calls in under 9 minutes.
In this blog we’ll be focusing on discrete cases in which the ambulances can be located at pre-defined points on a city map which form a set of vertices \(W\). Calls will then come in and be located on a separate set of vertices \(V\). We’ll discuss two of the more basic models that look at locating ambulances, we will not discuss models for dispatching ambulances but I’ll include references for further reading into this topic at the end of this post.
Maximum Coverage Location Problem
The Maximum Coverage Location Problem (MCLP) is one of the most basic models for locating ambulances on a set of vertices. We define the binary variable \(x_j\) equal to 1 if and only if an ambulance is located at vertex \(j\in W\). Similarly, the variable \(y_i\) is equal 1 if and only if vertex \(i\in V\) is covered by at least one ambulance. Let \(W_i\) be the set of location sites covering demand point \(i\). And finally let \(d_i\) be the demand on vertex \(i\). The model is then given as follows:
\begin{array}{lll}
\text{Maximize} & \sum_{i\in V} d_iy_i &\\
\text{s.t} & \sum_{j\in W_i} x_j\; \geq\; y_i & (i\in V),\\
& \sum_{j\in W}x_j\;=\;p,&\\
& x_j\;\in\;\{0,1\} &(j\in W),\\
&y_i\;\in\;\{0,1\} & (i\in V).
\end{array}
This may look rather complex for those of you who have not come across a linear programming model before so I will quickly run through line by line what it means. The first line is the objective function that simply states that we wish to maximize the total demand covered. The first constraint states that call \(i\) can only be covered if at least one of the potential ambulance location sites that covers \(i\) is selected. The next constraint says that we can use only \(p\) ambulances (this is included to limit fixed costs associated with locating more and more ambulances). The final two just mean that \(x_j\) and \(y_i\) are binary.
This model has several associated issues that make it unrealistic. For one, it doesn’t take into account that ambulance response times contain a large amount of uncertainty. This uncertainty can come from traffic delays, the weather or just time of day (Erkut et al. (2009)). It also assumes that the nearest ambulance is always available which may not be the case, instead we need some sort of back-up coverage. This problem stems from the fact that the MCLP only allows a single ambulance to be located at each vertex. Because of these issues several more advanced models have since been proposed that provide a more realistic solution.
The Maximum Expected Coverage Location Problem
The maximum expected coverage location problem is a direct extension of the MCLP that solves the issue of back-up coverage. In this model it allows more than one ambulance at each vertex so we need to adjust the definition of \(y_i\). We now define \(y_{ik}\) to be equal to 1 if and only if vertex \(i\in V\) is covered by at least \(k\) ambulances. In this model, each ambulance has an equal probability \(q\) of being busy and already out on a call. The model is as follows:
\begin{array}{lll}
\text{Maximize} & \sum_{i\in V}\sum_{k=1}^p d_i(1-q)q^{k-1}y_{ik} &\\
\text{s.t} & \sum_{j\in W_i} x_j\; \geq\; \sum^p_{k=1}y_{ik} & (i\in V),\\
& \sum_{j\in W}^px_j\;=\;p,&\\
& x_j\;\text{integer} &(j\in W),\\
&y_{ik}\;\in\;{0,1} & (i\in V,\;k=1,\ldots,p),\\
\end{array}
In this model the objective function is to maximize the expected coverage while the rest of the constraints remain similar to the MCLP model.
Extensions
Neither the MCLP nor the MEXCLP models are best for modelling the real life scenario of ambulance location, however both have been used to good effect to improve patient survival. There are now more advanced models that more realistically model the situation, these models address the following problems:
- More than one vehicle type may attend a call e.g advance life support (ALS) or quick response vehicles (QRVs) that can provide immediate patient care but cannot transport to hospitals and basic life support (BLS). See Mclay (2009).
- More than one ambulance may be dispatched on a call.
- Travel times are non-deterministic i.e. response times contain some level of uncertainty due to traffic, the weather or time of day.
- Each ambulance should respond to roughly the same number of calls to spread the workload.
- We also may want to consider models that look at both dispatching and locating ambulances simultaneously. See Ansari et. al (2015).
Thank you very much Laura Albert for introducing me to Public Sector OR, I thoroughly enjoyed your Masterclass!
References & Further Reading
I would highly recommend reading the papers by Brotcorne et. al (2003) and Erkut et. al (2009) as these give a thorough overview of the models I’ve discussed in this post, as well as, further extensions.
- Ansari, S., McLay L.A., Mayora, M.E., (2015). A Maximum Expected Covering Problem for District Design. Transportation Science 51(1), 376-390.
- Brotcorne, L., Laporte, G., Semet, F. (2003). Ambulance Location and Relocation Models. European Journal of operational research, 147(3), 451-463.
- Erkut, E., Ingolfsson, A., Sim, T., Erdogan, G. (2009). Computational Comparison of Five Maximal Covering Models for Locating Ambulances. Geographical Analysis, 41(1), 43-65.
- McLay, L.A., (2009). A Maximum Expected Covering Location Model with Two Types of Servers. IIE Transactions 41(8), 730-741.