Optimal Dispatch in Emergency Service System via Reinforcement Learning

In the United States, medical responses by fire departments over the last four decades has increased by 367% (Figure 1), as reported by Evarts (2019). The reasons for the dramatic increase in medical calls include the aging population and health insurance that covers most of the ambulance costs (Boston Globe, Nov 29, 2015). Cities with tight budgets are short of response units to respond to the growing amount of medical calls in time. NBC10 in Philadelphia, on Feb 28, 2019, reported that two thirds of the emergency medical calls had an ambulance response time of more than nine minutes. Thus, how to efficiently use the existing resources becomes an important topic to decision makers in emergency response departments.

In current practice, cities dispatch ambulance units according to a fixed dispatch rule, which always dispatches the closest available unit. The dispatch policy is deemed as a myopic policy as it only considers the current call and ignores the impact of dispatching a unit to future calls. In this paper, we model the ambulance dispatch problem as an average-cost Markov decision process (MDP). We finds a dispatch policy that minimizes the mean response time using reinforcement learning. We propose an alternative MDP formulation for the problem using post-decision states that we show is mathematically equivalent to the original MDP formulation, but with a much smaller state space.

Due to the curse of dimensionality, the application of both formulations are only restricted to small problems. To solve larger problems, we use temporal difference learning (TD-learning) with the post-decision states. In our numerical experiments, we show that the TD-learning algorithm converges quickly and the policies obtained from our method outperform the myopic policy that always dispatches the closest available unit.

The remainder of this paper is organized as follows. In Section 2, we provide a review of the relevant literature. In Section 3, we present the Markov decision process formulation. Section 4 presents the formulation using post-decision states which reduces the state space of the original formulation. In Section 5, we present the temporal difference learning algorithm that is based on the post-decision states and its theoretical properties, while in Section 6, we show the performance of the algorithm in numerical experiments. We conclude the paper in Section 7.

There are a number of papers that study dispatch policies for emergency medical services (EMS) in different settings. The optimal dispatch rule was first studied in Carter et al. (1972). The authors studied a simple system of two units and provided a closed form solution that determines the response areas to be served by each unit to minimize average response time. However, such a closed form solution no longer exists in a system that has more than two units, and finding the optimal dispatch rule has been an important topic.

Bandara et al. (2014) developed a simulation model to evaluate priority dispatching strategies for ambulance systems with different priorities of calls to improve patient survival probability. The optimal policy was found via full enumeration using a simulation model, and the authors found that dispatching the closest available unit is not always optimal in this setting. The limitation of their method is due to the exponential computational complexity. A system with more than four units would take a significant amount of time. McLay and Mayorga (2013b) developed a Markov decision process to optimally dispatch ambulances to emergency calls with classification errors in identifying priorities to maximize the expected coverage of true high-risk patients. They compared the optimal policy to the myopic policy that sends the closest unit and found an advantage in increasing the utility. The authors applied the value iteration algorithm to find the optimal solution, but the solution method is also limited only to small problems. They extended the paper in McLay and Mayorga (2013a) to consider the optimal policy that balances equity and efficiency by adding four equity constraints.

Jagtenberg et al. (2017a) studied whether dispatching the closest available unit is optimal in a dynamic ambulance dispatching problem based on a Markov decision process. The problem was discretized by time using one minute as the time interval. Two objectives were considered: mean response time and the fraction of calls with response time beyond a certain time threshold. The value iteration method was used to find the optimal solution. A heuristic that leverages the dynamic maximum expected covering location problem (MEXCLP) model was proposed by Jagtenberg et al. (2015), where the MEXCLP problem was studied by Daskin (1983) to determine the best unit locations using expected covering demand as a proximal objective function than response time. They found an improvement of 18% on the fraction of late arrivals using the optimal policy compared to the myopic policy, which provides insights about deviating from the myopic policy. Jagtenberg et al. (2017b) empirically provide a bound for the gap between the existing solutions and the optimal solution.

The aforementioned papers use enumeration or MDP models to analyze dispatch policies. While they are guaranteed to find the optimal policy, their computational complexity limit their use to only small systems, due to the curse of dimensionality. For larger problems, they normally fail badly computationally. Thus, many works have tried to resolve this issue using approximate dynamic programming (ADP). A comprehensive introduction to the application of Approximate Dynamic Programming in the operations research filed can be found in Powell (2010) and Powell (2007).

Schmid (2012) followed the same formulation as introduced in Powell (2010) that uses ADP with aggregation function approximation to an ambulance relocation and dispatching problem to reduce the mean response time. A seminal paper by Maxwell et al. (2010) applied ADP to the ambulance redeployment problem, where they used Monte Carlo simulation with one-step bootstrap to estimate complex expectations and applied least squares regression with linear function approximation to learn the approximate value functions. Nasrollahzadeh et al. (2018) studied the problem of real-time ambulance dispatching and relocation, which is formulated as a stochastic dynamic program and solved using ADP. Their formulation and method is the same as proposed in Maxwell et al. (2010). Issues of this approach include that while most of the time they can beat the benchmark policy, they normally never output the optimal policy. Also, it is not guaranteed that the learning method always converges and finding useful basis functions for approximation is more of an art than science, which requires domain knowledge and testing.

Our paper is different from the existing work in the following three aspects: 1) We model the problem as an average-cost MDP problem, which solves for the optimal policy that minimizes the mean response time. The papers we mentioned above use simpler discounted-reward schemes which minimize the sum of discounted response times as a surrogate to the mean response time. However, discounted response times are more difficult to interpret compared to mean response time. 2) We propose an alternative formulation with post-decision states and show its mathematical equivalence to the original problem formulation. 3) We show that the proposed TD-learning algorithm based on post-decision states is guaranteed to converge to the optimal solution, while little or no theoretical guarantees exist in the aforementioned works using ADP methods.

Consider a geographical region $R\subset\mathbb{R}^{2}$ that is served by a total of $N$ emergency units, all of the same type, e.g., ambulance units. Calls arrive in region $R$ according to a Poisson point process with an arrival intensity $\{\Lambda(x,y):(x,y)\in R\}$ at location with coordinate $(x,y)$. We partition the region $R$ into $J$ sub-regions and associate a center of mass with each sub-region $R_{j}\subset R$, which is also referred to as demand node $j$. Note that $J$ can be as large as needed. Denote the total call rate in node $j$ as

The overall call rate in region $R$ is denoted by

We assume the mean service time follows a negative exponential distribution with rate $\mu_{i}$ for unit $i$. We assume that the service time includes turnout time, travel time and time at the scene. The justification for this assumption is that travel time is usually a small portion of the total service time. With longer travel times, Jarvis (1975) mentioned a mean service time calibration to calibrate the service time to maintain the Markov property.

Let $b_{i}$ represent the state of unit $i$, where $b_{i}=0$ if the unit is available and $b_{i}=1$ if the unit is busy. We denote the state space of all units as an $N$-dimensional vector $B=\{b_{N}\cdots b_{1}\}\in\mathscr{B}$, which is in a backward order similar to the representation of binary numbers. We define $B=b_{i}$ as the status of unit $i$. Note that $|\mathscr{B}|=2^{N}$.

If all units are busy when a call is received, we assume that it is handled by a unit outside of the system, such as a private ambulance company, or a unit from a neighboring jurisdiction, which is common mutual aid policy.

Define $t_{ij}$ as the average response time from the base of unit $i$ to node $j$. In this paper, we aim to find the optimal dispatch policy that minimizes the average response time of all served calls.

The policy iteration method guarantees the convergence to the optimal dispatch policy that minimizes the average response time, which requires solving a linear system with $(J+1)2^{N}$ states repeatedly. In the section, by realizing the nature of the state transitions of the dispatch problem, we introduce the notion of post-decision states and use them as the new states in our problem. We show that the MDP formulation using post-decision states reduce the state space to $2^{N}$, which also guarantees to find the optimal dispatch policy. In the next section, we will develop the temporal difference learning method based on this formulation using post-decision states.

In the original formulation, a state is a tuple of call locations and the statuses of all units $s=(j,B)$. A post-decision state $s_{x}$ is a state that the system is in immediately after observing state $s$ and taking action $a=\pi(s)$, before the next random information arrives into the system, which is the arrival of the next call location. Thus, given state $s$ and unit $i$ being dispatched, i.e., $a=\pi(s)=i$, the post-decision state $s_{x}$ is

Note that by defining the post-decision state this way, we only need information about the statuses of all units. Define $S_{x}$ as the post-decision state space; we have $|S_{x}|=2^{N}$. Indeed, $S_{x}=\mathscr{B}$.

Note that all components defining $c^{\pi}(s_{x})$ and $p_{x}^{\pi}(s_{x},s_{x}^{\prime})$ are known, which are computed beforehand. Define $J^{\pi}:S_{x}\mapsto\mathbb{R}$ as the value function for the post-decision state space $S_{x}$. Let $\mu_{x}^{\pi}$ be the average cost following policy $\pi$ in the post-decision state space. The Bellman’s equation is

Let $J^{\pi}$, $c_{x}^{\pi}$ and $P_{x}^{\pi}$ be the corresponding vector representations. The vector form Bellman’s equation around post-decision states is

Under this formulation, the new policy $\pi^{\prime}$ for state $s=(j,B)$ is updated as

We note that even though the state space is smaller using post-decision states, the policy state space remains the same. The new policy iteration around post-decision states is summarized in Algorithm 2.

The policy iteration method with post-decision states is also guaranteed to find the optimal policy while reducing the number of equations from $(J+1)2^{N}$ to $2^{N}$. However, the exponential complexity limits its application only to small or medium-sized problems. In this section, we present the temporal difference learning method using value function approximation based on the formulation with post-decision states that reduces the dimension of the problem.

Let $\phi_{[p]}:S_{x}\mapsto\mathbb{R}$, $p=1,2\cdots,P$, be the basis functions of post-decision states, and let $r=\{r_{[p]}:p=1,2\cdots,P\}$ be the tunable parameters. The value function approximation is given by $\tilde{J}(s_{x},r)$, where

Let $\tilde{J}(r)$ be the vector of approximate state values of all states given parameter vector $r$ and let $\Phi$ be an $2^{N}\times P$ matrix whose pth column is equal to the vector $\phi_{[p]}$ of all states in $S^{x}$. The vector form of the above equation is

Define $\left\{x_{t}\mid t=0,1,\ldots\right\}$ as the Markov chain on the post-decision state space $S_{x}$ with transition matrix $P_{x}^{\pi}$.

The proof of the above lemma is straightforward by noting that the Markov chain with post-decision state space forms a hypercube loss model whose property can be found in Larson (1974). We define the temporal difference $d_{t}$ as

where $c\left(x_{t}\right)-\frac{\mu_{t}}{2}+\tilde{J}\left(x_{t+1},r_{t}\right)$ is the differential cost function at state $x_{t}$ based on the one-step bootstrap and $\tilde{J}\left(x_{t},r_{t}\right)$ is the old approximate differential cost function at state $x_{t}$. Define $r_{t}$ as the parameter vector at time $t$. We update the parameter vector $r$ using this temporal difference by

We let $\gamma_{t}=\frac{a}{a+t}$ where $a\geq 1$ is a hyper-parameter that controls the learning speed. We note that when $a=1$, $\gamma_{t}$ forms the harmonic series, but usually the performance is not good empirically as discussed in Powell (2007). A larger $a$ slows the learning speed at the beginning of the process and choosing the appropriate value of $a$ depends on the nature of the problem.

In this paper, we present a simple way of defining the basis function. We give an index $i_{x}$ to each post-decision state $s_{x}=B$, where $i_{x}=\sum_{i}^{N}2^{i}\mathbbm{1}_{B(i)=1}$. We let the basis function $\phi_{[p]}(s_{x})$ be

The algorithm is described in Algorithm 3.

The proof of the above theorem follows from Lemma 3, and the basis functions $\phi(s_{x})$ being linearly independent for all states. Also it is necessary to have the sequence $\gamma_{t}$ is positive, deterministic, and satisfies $\sum_{t=0}^{\infty}\gamma_{t}=\infty$ and $\sum_{t=0}^{\infty}\gamma_{t}^{2}<\infty$. A detailed proof are shown in Tsitsiklis and Van Roy (1999).

Theorem 2 guarantees that the TD-Learning algorithm with post-decision states shown in Algorithm 3 always returns the optimal policy if $T$ is large enough. When $T$ is moderately large, it is enough to obtain a policy close to optimal as we will show in the next section. Our algorithm avoids solving the complex bellman’s equation which has an exponential complexity. Once calculated the cost vector $c_{x}^{\pi}$ and transition matrix $P_{x}^{\pi}$, we easily obtain the temporal differences $d_{t}$ by Monte Carlo simulation and evaluate the value functions that is needed for policy improvement in the policy iteration algorithm. One can also leverage parallel computing to obtain multiple sample paths at the same time, which further reduces the computation time.

In this section, we show the numerical results comparing the policy obtained from the TD-Learning method to the myopic policy that always dispatch the closest available unit for systems with $N=5,10$ and $15$ units. We created an imaginary region which is partitioned into $J=30$ demand nodes. We randomly locate units in the region and obtain the corresponding response times from each unit to each demand point.

The myopic policy $\pi^{m}$ is obtained by choosing from the available units in each state $s\in S$ that results in the shortest response time. We solve the exact mean response time of the myopic policy using the hypercube queuing model developed by Larson (1974) for the cases of $N=5$ and $10$ units. For the case where $N=15$, the hypercube model becomes computationally costly due to its exponential complicity, and we obtain the approximate mean response time using the approximation method developed by Larson (1975), which has been tested to be very close to the exact value. An alternative is to obtain the approximate result via simulation which could be more accurate while taking a longer time.

The policy from the proposed TD-Learning method with post-decision states is obtained by running the algorithm in 25 iterations. We perform a roll-out with 200,000 state transitions in each iteration and update the parameter vector $r$ using the temporal differences $d$. We record the sample average response time in each iteration and the results are shown in Figures 2, 3, and 4, respectively.

From the three experiments we observe that the TD-Learning algorithm converges quickly in all cases as expected. We show the updates of the post-decision state values $\tilde{J}$ in one TD-Learning iteration for the case of $N=5$ in Figure 5. The resulted policies in all three cases outperform the myopic policy that always dispatch the closest available units. We also observe that our algorithm obtains a superior policy fairly quickly in about three iterations. In the case where $N=15$, solving the Bellman’s equation requires solving a system with $31\times 2^{15}=1,015,808$ states, which is very computational costly, if not infeasible, by most modern computers. In contrast, our method obtains a good policy in less than two minutes in this case, and it applies virtually to systems with any sizes as guaranteed by its theoretical properties.

Note that the policies obtained from our algorithm result in an average of three seconds reduction in terms of response time with no additional resources. This suggests that myopic policies are unnecessarily wasting critical resources and slightly more intelligent policies can provide improved performance with little to no cost.

In this paper, we model the ambulance dispatch problem as an average-cost Markov decision process and aim to find the optimal dispatch policy that minimizes the mean response time. The regular MDP formulation has a state space of $(J+1)\cdot 2^{N}$, where $J$ is the number of demand nodes that partition the entire region and $N$ is the total number of ambulances in the system. The policy iteration is able to find the optimal policy. We propose an alternative MDP formulation that uses the post-decision states and reduce the state space to $2^{N}$. We show that this formulation is mathematically equivalent to the original MDP formulation.

Even though the state space is reduced in the new formulation, due to the curse of dimensionality, its application is only restricted to small problems. We next present a TD-Learning algorithm based on the post-decision states that is guaranteed to converge to the optimal solution. In our numerically experiments, we show that the TD-Learning algorithm with post-decision states converge quickly and the policies obtained from our method outperforms the myopic policy that always dispatch the closest available unit in all cases.