TY - JOUR
T1 - Benchmarking online dispatch algorithms for Emergency Medical Services
AU - Jagtenberg, C.J.
AU - van den Berg, P. L.
AU - van der Mei, R.D.
PY - 2017
Y1 - 2017
N2 - Providers of Emergency Medical Services (EMS) face the online ambulance dispatch problem, in which they decide which ambulance to send to an incoming incident. Their objective is to minimize the fraction of arrivals later than a target time. Today, the gap between existing solutions and the optimum is unknown, and we provide a bound for this gap. Motivated by this, we propose a benchmark model (referred to as the offline model) to calculate the optimal dispatch decisions assuming that all incidents are known in advance. For this model, we introduce and implement three different methods to compute the optimal offline dispatch policy for problems with a finite number of incidents. The performance of the offline optimal solution serves as a bound for the performance of an – unknown – optimal online dispatching policy. We show that the competitive ratio (i.e., the worst case performance ratio between the optimal online and the optimal offline solution) of the dispatch problem is infinitely large; that is, even an optimal online dispatch algorithm can perform arbitrarily bad compared to the offline solution. Then, we performed benchmark experiments for a large ambulance provider in the Netherlands. The results show that for this realistic EMS system, when dispatching the closest idle vehicle to every incident, one obtains a fraction of late arrivals that is approximately 2.7 times that of the optimal offline policy. We also analyze another online dispatch heuristic, that manages to reduce this gap to approximately 1.9. This constitutes the first quantification of the gap between online and offline dispatch policies.
AB - Providers of Emergency Medical Services (EMS) face the online ambulance dispatch problem, in which they decide which ambulance to send to an incoming incident. Their objective is to minimize the fraction of arrivals later than a target time. Today, the gap between existing solutions and the optimum is unknown, and we provide a bound for this gap. Motivated by this, we propose a benchmark model (referred to as the offline model) to calculate the optimal dispatch decisions assuming that all incidents are known in advance. For this model, we introduce and implement three different methods to compute the optimal offline dispatch policy for problems with a finite number of incidents. The performance of the offline optimal solution serves as a bound for the performance of an – unknown – optimal online dispatching policy. We show that the competitive ratio (i.e., the worst case performance ratio between the optimal online and the optimal offline solution) of the dispatch problem is infinitely large; that is, even an optimal online dispatch algorithm can perform arbitrarily bad compared to the offline solution. Then, we performed benchmark experiments for a large ambulance provider in the Netherlands. The results show that for this realistic EMS system, when dispatching the closest idle vehicle to every incident, one obtains a fraction of late arrivals that is approximately 2.7 times that of the optimal offline policy. We also analyze another online dispatch heuristic, that manages to reduce this gap to approximately 1.9. This constitutes the first quantification of the gap between online and offline dispatch policies.
KW - Ambulances
KW - Dispatch
KW - Emergency medical services
KW - Online optimization
KW - OR in health services
UR - http://www.scopus.com/inward/record.url?scp=84992744442&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2016.08.061
DO - 10.1016/j.ejor.2016.08.061
M3 - Article
AN - SCOPUS:84992744442
SN - 0377-2217
VL - 258
SP - 715
EP - 725
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -