Repositioning Game for Ambulance Services

Abstract

In emergency medical services, ambulances are the first line of response, and the location of ambulances is one of the critical factors that influence the response time and, in turn, the coverage that is used as a metric to quantify the performance of an ambulance network. In this paper, we contribute to the literature of the dynamic repositioning of ambulances using compliance tables to improve coverage. We use a centrality measure, the Shapley value—a solution concept from coalitional game theory that measures the importance of a node in a network—to develop a compliance table for ambulance repositioning. Since the problem of computing the Shapley value often comes under the complexity class of $\#\mathcal{P}$ , we propose a compact representation of the ambulance repositioning problem called the repositioning game. The repositioning game includes the unavailability of ambulances and the variability in travel times. We show that the Shapley value of the repositioning game can be computed in polynomial $\mathcal{O}(n^3)$ time. Using the ambulance demand data of Chennai, India, we conduct discrete event simulation, and the simulation results indicate that the Shapley-value-based compliance table provides higher coverage than the criticality-based compliance table and the compliance table developed using the maximum expected covering location problem (MEXCRP) model when the ambulance network is constrained.