Benchmarking online dispatch algorithms for Emergency Medical Services

C.J. Jagtenberg, P. L. van den Berg, R.D. van der Mei

Research output: Contribution to journalArticleScientificpeer-review

12 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)715-725
Number of pages11
JournalEuropean Journal of Operational Research
Volume258
Issue number2
DOIs
Publication statusPublished - 2017

Keywords

  • Ambulances
  • Dispatch
  • Emergency medical services
  • Online optimization
  • OR in health services

Fingerprint Dive into the research topics of 'Benchmarking online dispatch algorithms for Emergency Medical Services'. Together they form a unique fingerprint.

Cite this