Benchmarking online dispatch algorithms for Emergency Medical Services

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.

• View at Publisher

Full Text ( Final Version , 1mb )