Dispatching fire trucks under stochastic driving times
Computers and Operations Research , Volume 114 p. 104829
To accommodate a swift response to fires and other incidents, fire departments have stations spread throughout their coverage area, and typically dispatch the closest fire truck(s) available whenever a new incident arises. However, it is not obvious that the policy of always dispatching the closest truck(s) minimizes the long-run fraction of late arrivals, since it may leave gaps in the coverage for future incidents. Although the research literature on dispatching of emergency vehicles is substantial, the setting with multiple trucks has received little attention. This is despite the fact that here careful dispatching is even more important, since the potential coverage gap is much larger compared to the single-truck case. Moreover, when dispatching multiple trucks, the uncertainty in the trucks’ driving time plays an important role, in particular due to possible correlation in driving times of the trucks if their routes overlap. In this paper we discuss optimal dispatching of fire trucks, based on a particular dispatching problem that arises at the Amsterdam Fire Department, where two fire trucks are sent to the same incident location for a quick response. We formulate the dispatching problem as a Markov Decision Process, and numerically obtain the optimal dispatching decisions using policy iteration. We show that the fraction of late arrivals can be significantly reduced by deviating from current practice of dispatching the closest available trucks, with a relative improvement of on average about 20%, and over 50% for certain instances. We also show that driving-time correlation has a non-negligible impact on decision making, and if ignored may lead to performance decrease of over 20% in certain cases. As the optimal policy cannot be computed for problems of realistic size due to the computational complexity of the policy iteration algorithm, we propose a dispatching heuristic based on a queueing approximation for the state of the network. We show that the performance of this heuristic is close to the optimal policy, and requires significantly less computational effort.
|Dynamic dispatching, Emergency services, Logistics, Markov process, MDP, One-step improvement|
|Computers and Operations Research|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam, The Netherlands|
Usanov, D, van de Ven, P.M, & van der Mei, R.D. (2019). Dispatching fire trucks under stochastic driving times. Computers and Operations Research, 114. doi:10.1016/j.cor.2019.104829