Optimal ambulance location with random delays and travel times

Abstract

We describe an ambulance location optimization model that minimizes the number of ambulances needed to provide a specified service level. The model measures service level as the fraction of calls reached within a given time standard and considers response time to be composed of a random delay (prior to travel to the scene) plus a random travel time. In addition to modeling the uncertainty in the delay and in the travel time, we incorporate uncertainty in the ambulance availability in determining the response time. Models that do not account for the uncertainty in all three of these components may overestimate the possible service level for a given number of ambulances and underestimate the number of ambulances needed to provide a specified service level. By explicitly modeling the randomness in the ambulance availability and in the delays and the travel times, we arrive at a more realistic ambulance location model. Our model is tractable enough to be solved with general-purpose optimization solvers for cities with populations around one Million. We illustrate the use of the model using actual data from Edmonton.

Appendices

Appendix 1: Proof of Proposition 1

Recall that the system-wide coverage $s\left( x \right) = \sum\nolimits_{j \in N} {h_j s_j \left( x \right)}$ is a convex combination of the coverages $s_j \left( x \right)$ for each demand node j. To prove that s(x) is concave, it suffices to prove that the coverage $s_j \left( x \right)$ for a particular node j is concave, since the weights $h_j$ are positive. Therefore, we assume without loss of generality that there is only one demand node and we drop the demand node subscript j in the proof to simplify notation.

By assumption we have $\Delta w_{i} = w_{{i + 1}} - w_{i} \leqslant 0$ for all i. We can express the probability $f_i \left( x \right)$ as:

$$f_i \left( x \right) = Q_i \left( {1 - \rho _i^{x_i } } \right)\prod\limits_{u = 1}^{i - 1} {\rho _u^{x_u } } = Q_i \left( {\prod\limits_{u = 1}^{i - 1} {\rho _u^{x_u } } - \prod\limits_{u = 1}^i {\rho _u^{x_u } } } \right) = g_{i - 1} \left( x \right) - g_i \left( x \right)$$

where $g_i \left( x \right) = Q_i \prod\nolimits_{u = 1}^i {\rho _u^{x_u } }$ and $g_0 \left( x \right) = 1$. Consequently,

$$\begin{array}{*{20}c} {s\left( x \right) = \sum\limits_{i \in S} {f_i \left( x \right)w_i } = \sum\limits_{i = 1}^m {g_{i - 1} \left( x \right)w_i } - \sum\limits_{i = 1}^m {g_i \left( x \right)w_i } } \\ { = \sum\limits_{i = 0}^m {g_i \left( x \right)w_{i + 1} } - \sum\limits_{i = 1}^m {g_i \left( x \right)w_i } = w_1 + \sum\limits_{i = 1}^m {g_i \left( x \right)\Delta w_i } } \\ \end{array} $$

with the understanding that $w_{m + 1} = 0$.

The gradient of s(x) with respect to x has the following entries:

$$\frac{{\partial s}}{{\partial x_k }} = \left( {\ln \rho _k } \right)\sum\limits_{i = k}^m {g_i \left( x \right)\Delta w_i } $$

The entries in the Hessian matrix H are (assuming $k \leqslant l$):

$$h_{kl} = \frac{{\partial ^2 s}}{{\partial x_k \partial x_l }} = \left( {\ln \rho _k } \right)\left( {\ln \rho _l } \right)\sum\limits_{i = l}^m {g_i \left( x \right)\Delta w_i } $$

Recalling that $Q_i > 0$, $\rho _i \in \left( {0,1} \right)$ and $\Delta w_i \leqslant 0$, we see that ${{\partial s} \mathord{\left/ {\vphantom {{\partial s} {\partial x_k }}} \right. \kern-\nulldelimiterspace} {\partial x_k }}$ is non-negative for all k, and ${{\partial ^2 s} \mathord{\left/ {\vphantom {{\partial ^2 s} {\partial x_k \partial x_l }}} \right. \kern-\nulldelimiterspace} {\partial x_k \partial x_l }}$ is non-positive for all k and l.

Consider the quadratic form $y^T Hy$ where y is an arbitrary column vector with m elements. This quadratic form can be expressed as:

$$\begin{array}{*{20}c} {y^T Hy = \sum\limits_{k = 1}^m {\sum\limits_{l = 1}^m {y_k y_l h_{kl} } } = \sum\limits_{l = 1}^m {y_l^2 h_{ll} } + 2\sum\limits_{k = 1}^m {\sum\limits_{l = k + 1}^m {y_k y_l h_{kl} } } } \\ \end{array} $$

Substituting the expression for $h_{kl}$we get:

$$\begin{array}{*{20}c} {y^T Hy = \sum\limits_{l = 1}^m {y_l^2 \left( {\ln \rho _l } \right)^2 \sum\limits_{i = l}^m {g_i \left( x \right)\Delta w_i } } + 2\sum\limits_{k = 1}^m {\sum\limits_{l = k + 1}^m {y_k y_l \left( {\ln \rho _k } \right)\left( {\ln \rho _l } \right)\sum\limits_{i = l}^m {g_i \left( x \right)\Delta w_i } } } } \\ \end{array} $$

(10)

By changing the order of summation, the double sum in Eq. 10 can be expressed as:

$$\sum\limits_{l = 1}^m {y_l^2 \left( {\ln \rho _l } \right)^2 \sum\limits_{i = l}^m {g_i \left( x \right)\Delta w_i } } = \sum\limits_{i = 1}^m {g_i \left( x \right)\Delta w_i \sum\limits_{l = 1}^i {\left( {\ln \rho _l } \right)^2 y_l^2 } } $$

Similarly, the triple sum in Eq. 10 can be expressed as:

$$\begin{array}{*{20}c} {\sum\limits_{k = 1}^m {\sum\limits_{l = k + 1}^m {y_k y_l \left( {\ln \rho _k } \right)\left( {\ln \rho _l } \right)\sum\limits_{i = l}^m {g_i \left( x \right)\Delta w_i } } } = \sum\limits_{k = 1}^m {\sum\limits_{i = k + 1}^m {g_i \left( x \right)\Delta w_i \sum\limits_{l = k + 1}^i {y_k y_l \left( {\ln \rho _k } \right)\left( {\ln \rho _l } \right)} } } } \\ { = \sum\limits_{i = 2}^m {g_i \left( x \right)\Delta w_i \sum\limits_{k = 1}^{i - 1} {\sum\limits_{l = k + 1}^i {y_k y_l \left( {\ln \rho _k } \right)\left( {\ln \rho _l } \right)} } } } \\ \end{array} $$

Substitution in Eq. 10 results in:

$$\begin{array}{*{20}c} {y^T Hy = \sum\limits_{i = 1}^m {g_i \left( x \right)\Delta w_i } \left\{ {\sum\limits_{l = 1}^i {\left( {\ln \rho _l } \right)^2 y_l^2 } + 2\sum\limits_{k = 1}^{i - 1} {\sum\limits_{l = k + 1}^i {\left( {\ln \rho _k } \right)\left( {\ln \rho _l } \right)y_k y_l } } } \right\}} \\ { = \sum\limits_{i = 1}^m {g_i \left( x \right)\Delta w_i } \left( {\sum\limits_{l = 1}^i {\left( {\ln \rho _l } \right)y_l } } \right)^2 } \\ \end{array} $$

We see that each term in the outer summation is non-positive (because $g_i \left( x \right) \geqslant 0$, $\Delta w_i \leqslant 0$, and the squared summation is non-negative) and therefore $y^T Hy \leqslant 0$ for all y. Consequently, H is negative semi-definite and s(x) is concave.■

Appendix 2: Estimating the average busy fraction

The average fraction of time that an ambulance is busy (not available to respond to calls) is ${{\lambda \tau } \mathord{\left/ {\vphantom {{\lambda \tau } z}} \right. \kern-\nulldelimiterspace} z}$, i.e., the average server utilization for a z-server queueing system, assuming that the number of calls “lost” due to queueing is negligible. The average “service time”, τ, (during which an ambulance is tied up with a call) can be broken down into the following components: average travel time to the call, average on-scene time, and average time spent traveling to and remaining at a hospital, denoted $E\left[ {T_{{\text{to\; call}}} } \right]$, $E\left[ {T_{{\text{on \;scene}}} } \right]$, and $E\left[ {T_{{\text{hospital}}} } \right]$, respectively. Consequently, the average busy fraction can be expressed as $\lambda {\left( {E{\left[ {T_{{{\text{tocall}}}} } \right]} + E{\left[ {T_{{{\text{onscene}}}} } \right]} + E{\left[ {T_{{{\text{hospital}}}} } \right]}} \right)}/z$. The arrival rate λ as well as two of the three components of the average service time, the average on-scene time and the average time spent traveling to and being at a hospital, are exogenous input. The average travel time to a call can be expressed as $E\left[ {T_{{\text{to call}}} } \right] = \sum\nolimits_{j \in N} {h_j \sum\nolimits_{i \in S} {f_{ij} \left( x \right)E\left[ {T_{ij} } \right]} }$, where T _ij is the travel time from i to j. This leads to the following formula for approximating ρ as a function of x:

$$\rho \left( x \right) = \frac{\lambda }{{z\left( x \right)}}\left\{ {\sum\limits_{j \in N} {h_j \sum\limits_{i \in S} {f_{ij} \left( x \right)\operatorname{E} \left[ {T_{ij} } \right]} } + \operatorname{E} \left[ {T_{{\text{on scene}}} } \right] + \operatorname{E} \left[ {T_{{\text{hospital}}} } \right]} \right\}$$

The derivation of this formula required some approximations. In particular, we excluded the time spent traveling back to a station from the hospital from the average service time since the ambulance is available to respond to incoming calls during this time. On the other hand, our expression for $E\left[ {T_{{\text{to \;call}}} } \right]$ assumes that all calls are responded to from an ambulance at a station.