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 $# 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 $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.

Keywords

sustainability and resilience transportation systems resilience disaster response recovery business continuity emergency response

An emergency medical service (EMS) system aims to provide timely medical care for people in emergencies and transport them to the nearest hospital if needed. Ambulances are the most important constituent of any EMS system. The ability of ambulances to reach an emergency site within a few minutes substantially affects the recovery and survival of patients ( 1 ). Location of ambulances is one of the critical factors that influence the response time—the time between the call arrival and the ambulance reaching the emergency site. Effective planning of ambulance locations at the strategic, tactical, and operational levels is crucial to minimize the response time. At the strategic and tactical levels, ambulance location models help EMS planners to determine the number of ambulances that need to be sited and the location of each ambulance. Real-time decisions, such as dispatching and repositioning policies, are planned at the operational level. This work focuses on real-time dynamic repositioning policies for ambulances to improve performance. A related metric to quantify the performance of an EMS system is the coverage that is defined as the proportion of calls addressed within a predefined response time threshold ( 2 , 3 ). Toro-Díaz et al. show that maximizing the expected coverage of the system results in reducing its response time ( 4 ). Whenever an ambulance is dispatched to address an emergency request, it may leave a significant fraction of the population uncovered. To improve the coverage, ambulance service providers resort to ambulance repositioning strategies for redistributing the available ambulances.

Compliance table is one of the techniques to relocate ambulances in real-time. The compliance-table-based repositioning can be easily implemented in practice, and it depends solely on the number of idle ambulances in the system. Each row in the compliance table indicates the ideal base stations to which a given number of available ambulances can be assigned to improve the coverage. The system achieves compliance when the available ambulances are at the preferred waiting locations. To achieve compliance, the existing allocation of ambulances needs to be disturbed. Since it is desirable to reduce the disturbance, a constraint is imposed on the number of ambulance movements, leading to the development of a nested compliance table. A nested compliance table allows only one ambulance to move at each decision epoch. Our study focuses on developing a nested compliance table for the dynamic repositioning of ambulances.

Traditionally, to develop a compliance table, the criticality of each base station is computed—this is defined as the number of calls received at that base station in a given duration, that is, calls per day. For any number of idle ambulances, $n$ , we locate these n ambulances in the base stations with top $n$ criticality values to develop criticality-based compliance table. One possible drawback of such a compliance table is that the criticality value does not capture how crucial the base station is for the entire system—it does not account for positive externality that a base station may provide to other base stations. For example, a call coming to a base station can be diverted to the next nearest base station because of the unavailability of an ambulance at the parent base station. Alanis et al. show that the performance of an EMS system strongly depends on the compliance table used, and the choice of a compliance table is a tactical decision ( 5 ). The literature on computing compliance tables is scant. To compute an efficient compliance table, it is imperative to include a base station’s positive externality in the ambulance network. In other words, the compliance table should map idle ambulances to the base stations that are the most important for the ambulance network. Furthermore, this is akin to the question posed by the ambulance service providers: “If we have only one ambulance available, where shall we locate it to improve the coverage?” This is the primary motivation for this paper.

In network science, centrality measures assign a value to each node based on its importance in the network. Degree centrality, closeness centrality, and betweenness centrality are some of the well known centrality measures ( 6 ). In our research, we consider the EMS system as a network and the base stations as the nodes in the network. We use a game theory-based centrality measure, the Shapley value, that measures the importance of each base station in the network, to develop a nested compliance table. A solution concept for coalitional games, the Shapley value of a player in a coalitional game is a probabilistic value that captures the average marginal contribution of the player in each possible coalition ( 7 ). One related paper is Fragnelli et al. which uses the Shapley value for the ambulance location problem ( 8 ). Their work mainly focuses on ranking the candidate locations based on the demand at each location. However, we focus on developing the Shapley-value-based compliance table while considering the unavailability of ambulances at base stations and the variability in travel time for dynamic repositioning of ambulances.

Based on the above discussion, we develop the Shapley-value-based compliance table for dynamic repositioning of ambulances by incorporating the unavailability of ambulances at base stations and the variability in travel times. Since the problem of computing the Shapley value often comes under the complexity class of $♯ P$ (pronounced as sharp P), we propose a compact representation of the ambulance repositioning problem called the repositioning game ( 9 , 10 ). 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 $O (n^{3})$ time. Using discrete event simulation, we show that the Shapley-value-based compliance table provides higher coverage than the criticality-based compliance table when the ambulance network is constrained by the availability of free ambulances. In the literature, the maximum expected covering relocation problem (MEXCRP) is used as a benchmark model for repositioning ambulances ( 11 ). We also show that the Shapley-value-based compliance table provides higher coverage than MEXCRP when the ambulance network is constrained.

The rest of the paper is structured as follows. The next section discusses the related literature on the ambulance repositioning problem. Further, we propose a new class of games for ambulance repositioning called repositioning games. Using the real data of ambulance demand, unavailability, and travel time, we develop the Shapley-value-based compliance table for Chennai, India. Then, we perform a simulation-based comparison of the coverage with the existing models. Finally, we conclude this paper with practical implications.

Related Literature

Ambulance location problems are often formulated as network location problems where the demand for ambulances and base stations occurs only at the nodes of the network, and the edge denotes the travel distance ( 12 ). Review papers by Brotcorne et al., Aringhieri et al., and Bélanger et al. discuss the evolution of location models for addressing the ambulance positioning problem ( 13 – 15 ). The seminal papers on static ambulance location models that focus on strategic and tactical level decisions, such as determining the location of ambulance base stations and the number of ambulances in each base station, are Toregas et al., Church and ReVelle, and Daskin ( 2 , 16 , 17 ). Toregas et al. formulate the location set covering problem to identify the number of facilities required to provide adequate coverage ( 2 ). In practice, the number of ambulances required to provide total coverage can be significant and unrealistic. To address this limitation, Church and ReVelle propose the maximal covering location problem to maximize the coverage with a given number of facilities ( 16 ). Daskin proposes MEXCRP by considering the unavailability of ambulances ( 17 ). Church and Murray, and Daskin provide details of the above models and their extensions over the years ( 12 , 18 ).

Because of the high variability in demand and congestion in the road network over time, the solution obtained by solving the static model becomes suboptimal. The performance of the system can be improved by using a dynamic relocation strategy over static policies ( 19 , 20 ). Dynamic models mainly emphasize how to allocate the available ambulances for a given number of base stations in real-time to improve operational performance. In dynamic models, the ambulances no longer have designated base stations, and ambulances may be relocated to different base stations to ensure required coverage at all times. Ambulance redeployment or dynamic repositioning can be implemented either by solving the problem a priori to develop the compliance table or solving the problem in real-time with respect to the system’s state. Kolesar and Walker design the first relocation policy in the context of fire engine resources, and the results established redeployment as an effective method to improve performance ( 21 ). Berman formulates the Markov decision problem for dynamic repositioning of emergency units to minimize the long-term operational cost ( 22 ).

Gendreau et al. propose the dynamic double standard model (DDSM) to solve the repositioning problem to maximize the total demand coverage ( 23 ). They consider using a parallel tabu heuristic search to solve the DDSM and precomputed multiple solutions in anticipation of future demand, allowing quick decision-making when calls are received. Andersson and Värbrand use the concept of preparedness to develop the redeployment plan ( 24 ). However, solving this model to get the exact solution is difficult in real-time. Similarly, Lee develop relocation algorithms based on the notion of preparedness of base stations, where the preparedness of a base station captures the ability of the base station to respond to a call arising in its region ( 25 ). Jagtenberg et al. develop the dynamic MEXCLP heuristic for relocating the ambulances in real-time such that the expected fraction of demand which the ambulances reach later than the standard time is minimized ( 26 ). The algorithm also reduced the overall response time of the system. Sometimes, solving the problem in real-time is time-consuming, or even infeasible, when the frequency of calls is high.

Another approach to analyzing the ambulance repositioning problem can be based on the compliance-table-based relocation plans. Gendreau et al. formulate MEXCRP, for which the solution was precomputed at the beginning of the planning period, to provide adequate demand coverage while regulating the number of relocations ( 11 ). Maleki et al. state that the compliance tables are just the first part of the decision ( 27 ). They formulate a bottleneck assignment model for repositioning ambulances to minimize the total distance traveled by all ambulances. Alanis et al. model the EMS system as a Markov chain model and study the performance measures for various compliance-table-based relocation policies ( 5 ). The results show that their model can identify the near-optimal compliance table, improving coverage performance. Similarly, Sudtachat et al. use the Markov chain model to determine an optimal nested compliance table that dispatchers can use to maximize the coverage ( 3 ). Van Barneveld extends the MEXCRP model to compute compliance tables by introducing penalty functions for limiting the number of relocations ( 28 ). Van Barneveld et al. modify the hypercube model to estimate the busy fractions and extend MEXCRP by considering two types of ambulances to develop nested compliance tables ( 29 ). Sudtachat et al. develop the maximum realized covering relocation and districting problem and determine the relocation strategies in each district ( 30 ).

Game theory has been used for location problems. Hotelling studies the behavior of two firms selling a homogeneous product that have to decide the optimal location ( 31 ). Several extensions of competitive location problems have been studied in the literature. The cost allocation problem has been widely studied in the cooperative setting. Tamir proposes a game-theoretic model to find the optimal cost allocation for covering problems on the network ( 32 ). Curiel deals with games for p-center and p-median location problems ( 33 ). The above discussion points out that the game-theoretic ideas have not been used for ambulance repositioning. Amer et al. proposes a coalition game approach based on particle swarm optimization (CGA-PSO) for the ambulance routing problem ( 34 ). The model defines the coalition among the different attributes for each ambulance route, traffic conditions, and distributed ambulances to determine the optimal routing for emergency vehicles, reducing response time. To the best of our knowledge, the only related paper is Fragnelli et al. which discusses the coverage game to study the strategic interactions among the candidate locations for locating the ambulances ( 8 ). However, we focus on ambulance repositioning by incorporating the unavailability of ambulances and the travel time information and propose a compact representation named repositioning games. The Shapley value of each base location in the repositioning game is used to develop the compliance table for ambulance repositioning. The representation of the game ensures that the Shapley value can be computed in polynomial time.

The Repositioning Game

We model the ambulance repositioning problem as a coalitional game. In coalitional game theory, the modeling unit is a coalition of rational and selfish agents, and they are usually represented as the games in characteristic form.

Definition 1. A coalitional game in characteristic form is a tuple $〈 N, υ 〉$ , where

• N is a finite set of players in the game.

• $υ : 2^{n} \to R$ is the characteristic function, that assigns a real-valued number called its payoff to each coalition S $\subseteq N$ . $n$ is the cardinality of the set $N$ .

• $υ (\emptyset) = 0$ .

In Definition 1, $υ (S)$ is a payoff to coalition $S \subseteq N$ . $υ (S)$ can be defined as the maximum payoff that the coalition $S$ can achieve by joint action of the players in $S$ , independent of the actions of the players in $N \ S$ . Using a set of axioms, Shapley proposes a solution concept called the Shapley value for the games in characteristic form ( 7 ).

Definition 2. Shapley ( 7 ). Given $〈 N, υ 〉$ , the Shapley value of player $i$ is given by

ϕ_{i} (N, v) = \frac{1}{N!} \sum_{S \subseteq N \ {i}} | S |! (| N | - | S | - 1)! [v (S \cup {i}) - v (S)]

The Shapley value assigns a value to each player based on their average marginal contribution over all possible permutations of players. Shapley characterized $ϕ_{i}$ as the unique value that satisfies the following set of axioms:

A1. Symmetry: If two players $i$ and $j$ are symmetric for a game $〈 N, υ 〉$ , then $ϕ_{i} (υ) = ϕ_{j} (υ)$ .

A2. Dummy Player: If $i$ is a dummy player such that $υ (S \cup {i}) = υ (S)$ for each $S \subseteq N \ {i}$ , then $ϕ_{i} (υ) = 0$ .

A3. Additivity: Given two games $υ_{1}$ and $υ_{2}$ with same set of players $N$ , let the sum $(υ_{1} + υ_{2})$ be the game with same set of players $N$ and $(υ_{1} + υ_{2}) (S) = υ_{1} (S) + υ_{2} (S)$ for each $S \subseteq N$ , then $ϕ_{i} (υ_{1} + υ_{2}) = ϕ_{i} (υ_{1}) + ϕ_{i} (υ_{2})$ for each $i \in N$ .

A4. Efficiency: For each game $〈 N, υ 〉$ , $\sum_{i \in N} ϕ_{i} (υ) = υ (N)$ .

The Shapley value is one of the fundamental solution concepts for coalitional games and measures each player’s strength based on the player’s marginal contribution to possible coalitions. We use the Shapley value to develop the compliance table for ambulance repositioning, where the importance of a base station is computed using the Shapley value. The desiderata of the problem formulation are discussed next.

The Preliminaries

We model the ambulance system as a network $G (N, A)$ , where $N$ denotes a set of locations at which demand for ambulance service can arise. $M \subseteq N$ be the set of base stations in which ambulances can be deployed. In this paper, we assume $M$ and $N$ are the same, which means the base stations and demand locations overlap. The arc $A$ represents the travel time $t_{ij}$ between any base station $i \in M$ and the demand node $j \in N$ , which is assumed to be random. Let $d_{j}$ be the number of emergency requests from the node $j$ in a given time interval. All emergency requests are assumed to have equal priority. The ambulances are assigned to emergency calls based on the closest dispatch policy. When there are no ambulances available in the system, the call is considered lost. When an ambulance arrives at the patient’s location, the paramedics provide the first aid and decide whether the patient needs transport to the hospital. The ambulance takes the patient to the nearest hospital if needed.

We define the covering probability of the base station $i \in M$ for the demand location $j \in N$ as

p_{ij} = (1 - ρ_{i}) \times r_{ij}

(1)

that depends on the ability to reach the demand location within the prescribed threshold time and its busy probability. The busy fraction of ambulances $ρ_{i}$ corresponds to the probability of $i^{th}$ base station being unavailable because of the service of a patient. Further, the reachability $r_{ij}$ is defined as the probability of an ambulance from $i^{th}$ base station reaching $j^{th}$ demand point within the threshold time $τ$ .

r_{ij} = \Pr (t_{ij} \leq τ)

(2)

where

$t_{ij}$ = the travel time from $i^{th}$ base station to $j^{th}$ demand point.

The Repositioning Game for the Ambulance System

We propose a representation called the repositioning game, in which the base stations act as players. As mentioned earlier, the set of base stations ( $M$ ) and the set of demand locations ( $N$ ) are completely overlapping. We define the repositioning subgame for each demand node $j \in N$ as

υ^{j} (S_{j}) = d_{j} \times (1 - \underset{i \in S_{j}}{Π} (1 - p_{ij}))

(3)

where

$S_{j} = {i \in M | p_{ij} > 0}$ = the set of base stations providing coverage for demand node $j$ , and

$υ^{j}$ = the expected coverage at $j$ computed based on the demand that can be covered by at least one base station with covering probability $p_{ij} > 0$ .

The set of such base stations that can cover $j$ with $p_{ij} > 0$ is $S_{j}$ . Figure 1 represents the coalition $S_{4}$ for the demand node $4$ , where $ρ_{i}$ ( $i = 1, \dots, 6$ ) is the busy fraction at base location $i$ and $r_{i 4}$ is the reachability from $i$ to node $4$ within the threshold time $τ$ . It is evident in Figure 1 that base locations $i = 5, 6$ do not provide coverage to node 4 as $r_{64} = r_{54} = 0$ . Moreover, $r_{44} = 1$

Figure 1.

Coalition of base stations providing services to demand node 4.

Lemma 1. $υ^{j} (A)$ is increasing in $| A |, A \subset S_{j} for each j$ .

Proof. To prove this lemma, it is sufficient to prove $υ^{j} (A \cup {k}) > υ^{j} (A)$ , where $k \in S_{j}$

\begin{matrix} υ^{j} (A \cup {k}) - υ^{j} (A) = d_{j} \times (1 - \underset{i \in A \cup {k}}{Π} (1 - p_{ij})) \\ - d_{j} \times (1 - \underset{i \in A}{Π} (1 - p_{ij})) \\ = d_{j} \times [(1 - \underset{i \in A \cup {k}}{Π} (1 - p_{ij})) \\ - (1 - \underset{i \in A}{Π} (1 - p_{ij}))] \\ > 0 \end{matrix}

(3)

where the inequality holds because of the multiplicative nature of the probabilities.

Lemma 1 shows that the expected coverage at demand location $j$ is increasing with the number of ambulances in $S_{j}$ —the repositioning subgame is superadditive and, therefore, we consider the coalition $S_{j}$ , and not its subsets.

We now define the value of each $i \in M$ in each repositioning subgame. The repositioning subgame is defined in such a way that the demand at $j$ is covered if there exists at least one ambulance in $S_{j}$ that can provide service to the demand zone. Using the symmetry axiom of the Shapley value, the value of each base location $i$ in repositioning subgame $υ^{j} (S_{j})$ is defined as

ϕ_{i} (υ^{j} (S_{j})) = {\begin{matrix} \frac{υ^{j} (S_{j})}{| S_{j} |} if i \in S_{j} \\ 0 otherwise \end{matrix}

(4)

It means that each base location in $S_{j}$ provides equal value in coverage for the demand at $j$ . As we are considering coalition $S_{j}$ and not its subsets, the value computed in Equation 4 gives a conservative estimate of the value. Each $i \in M$ can contribute to the coverage in multiple repositioning subgames. The set of repositioning subgames $υ^{j} (S_{j})$ for all $j$ is the repositioning game for the ambulance network. Using the additivity axiom of the Shapley value, we define the Shapley value $ϕ_{i}$ as the sum of the contributions of $i$ in all repositioning subgames.

ϕ_{i} = \sum_{j \in N} ϕ_{i} (υ^{j})

(5)

The Shapley value of the repositioning game is used to develop the compliance table for ambulance repositioning. The representation dovetails with the multi-issue representation as discussed in Shoham and Leyton-Brown ( 35 ). Shoham and Leyton-Brown note that “the Shapley value of a coalitional game specified in the multi-issue representation can be found efficiently” ( 35 ). Based on the above model, we develop Algorithm 1 to compute the Shapley value of each base station. Proposition 1 shows that computing the Shapley value of the repositioning game is polynomial in time.

Algorithm 1 COMPUTING SHAPLEY VALUE IN THE REPOSITIONING GAME
Input: base locations $M$ , demand locations $N$ , call data, distributional parameters for travel time between $i$ and $j$ , threshold ( $τ$ ) Output: Shapley value $ϕ_{i}$ foreach $j$ in $N$ do foreach $i$ in $M$ do $ρ_{i} = \frac{total service time of i}{total available time of i}$ reachability $r_{ij} = \Pr (t_{ij} \leq τ)$ Covering prob $p_{ij} = (1 - ρ_{i}) \times r_{ij}$ $S_{j}$ is a set of $i$ based on covering probability end end foreach $i$ in $M$ do $ϕ_{i} (υ) = 0$ for each $j$ in $N$ do $z = 1$ for each $i$ in $S_{j}$ do $z = z \times (1 - p_{ij})$ end value of $j^{th}$ sub game $υ^{j} = d_{j} \times (1 - z)$ Shapley value for each base $i$ is $ϕ_{i} (υ) = ϕ_{i} (υ) + \frac{υ^{j}}{\| S_{j} \|}$ end end

Algorithm 1 COMPUTING SHAPLEY VALUE IN THE REPOSITIONING GAME

Input: base locations

M

, demand locations

N

, call data, distributional parameters for travel time between

i

and

j

, threshold (

τ

)
Output: Shapley value

ϕ_{i}

foreach $j$ in

N

do
foreach $i$ in

M

ρ_{i} = \frac{total service time of i}{total available time of i}

reachability

r_{ij} = \Pr (t_{ij} \leq τ)

Covering prob

p_{ij} = (1 - ρ_{i}) \times r_{ij}

S_{j}

is a set of

i

based on covering probability
end
end
foreach $i$ in

M

ϕ_{i} (υ) = 0

for each

j

N

z = 1

for each

i

S_{j}

z = z \times (1 - p_{ij})

end
value of

j^{th}

sub game

υ^{j} = d_{j} \times (1 - z)

Shapley value for each base

i

ϕ_{i} (υ) = ϕ_{i} (υ) + \frac{υ^{j}}{| S_{j} |}

end
end

Proposition 1. For a repositioning game with equal sets $M$ and $N$ of cardinality $n$ , the worst case time complexity for computing the Shapley value $ϕ_{i}$ of each base station $i \in M$ using Algorithm 1 is $O (n^{3})$ .

Proof. The value of the repositioning subgame $υ^{j} (S_{j})$ is computed as the expected coverage provided by at least one ambulance in $i \in S_{j}$ , and the value of each base station $i \in M$ in each subgame is computed using Equation 4. This involves $n^{2}$ operations. The Shapley value of each base station involves $n$ operations. These operations are part of the nested FOR-LOOP starting at line 6 in Algorithm 1. Therefore, the time complexity of computing the Shapley value of the repositioning game is $O (n^{3})$ .

Example 1. Let us illustrate the algorithm with a numerical example. We consider a network with six nodes that act as base stations as well as demand nodes, $M = N = {1, 2, 3, 4, 5, 6}$ . The busy fraction of the demand nodes is given as the 6-tuple

ρ = (0.4893, 0.5050, 0.1556, 0.2795, 0.2841, 0.612)

and the cumulative demand from each node is given as as the 6-tuple

d = (259, 738, 175, 442, 533, 811)

Assume that the travel time between each pair of nodes follows log-normal distribution. We consider the response time threshold as 10 min and obtain the reachability matrix (Table 1) as follows

Table 1.

Reachability Matrix

	1	2	3	4	5	6
1	1	0	0	0	0	0.784
2	0	1	0.846	0	0	0
3	0	0.846	1	0.640	0	0
4	0	0	0.640	1	0	0
5	0	0	0	0	1	0
6	0.784	0	0	0	0	1

Covering probability is computed as $p_{ij} = (1 - ρ_{i}) \times r_{ij}$ , and is shown in Table 2.

Table 2.

Covering Probability

	1	2	3	4	5	6
1	0.511	0	0	0	0	0.304
2	0	0.495	0.714	0	0	0
3	0	0.419	0.844	0.461	0	0
4	0	0	0.541	0.721	0	0
5	0	0	0	0	0.716	0
6	0.400	0	0	0	0	0.387

The value of the repositioning subgame for each demand node $j \in N$ is

υ^{j} (S_{j}) = d_{j} \times (1 - \underset{i \in S_{j}}{Π} (1 - p_{ij}))

Using the previous data,

υ^{j} (S_{j}) = (170.736, 631.521, 166.471, 385.244, 381.575, 512.989)

$S_{j}$ is the set of nodes that provides coverage for the demand node $j$ .

\begin{matrix} S_{1} = {1, 6} \\ S_{2} = {2, 3} \\ S_{3} = {3, 4, 5} \\ S_{4} = {4, 5} \\ S_{5} = {5} \\ S_{6} = {1, 6} \\ ϕ_{i} (υ^{j} (S_{j})) = {\begin{matrix} \frac{υ^{j} (S_{j})}{| S_{j} |} if i \in S_{j} \\ 0 otherwise \end{matrix} \\ ϕ_{i} = \sum_{j \in N} ϕ_{i} (υ^{j}) \end{matrix}

The Shapley value of the base stations is the following tuple

ϕ_{i} = (341.863, 371.251, 563.873, 248.112, 381.575, 341.863)

Computing the Shapley-Value-Based Compliance Tables for Ambulance Repositioning in Chennai, India

In this section, we compute the Shapley value for developing a compliance table for ambulance repositioning in Chennai (one of the major cities in India and the capital of the state of Tamil Nadu). In Chennai, one of the ambulance networks is operated by GVK–EMRI, a non-profit organization operating in public-private-partnership (PPP) with the government of Tamil Nadu. For computing the Shapley value, we use the data provided by GVK-EMRI for 2016, with ambulances at 31 base locations in Chennai. The base locations are indicated in Figure 2.

Figure 2.

Base locations in Chennai.

The data have a total of 15,818 call records for July, August, and September, 2016. Each call record has the details of call location, emergency type, and the base station from which the ambulance is assigned. It also contains the time stamp of the call, starting from the time when the call is reported to the time at which the ambulance returned to the base location after completing the call. Based on the call data, we calculate the input parameters, such as busy probability and aggregate demand, for our model. We also collect week-long data of travel time between each pair of nodes from the Google Maps platform. The study by Shi et al. shows that the lognormal distribution fits better for the urban travel times under both light and heavy traffic conditions ( 36 ). Therefore, we approximate the travel time data as a lognormal distribution. Although it is reasonable to assume a lognormal distribution, the results can be improved by considering realistic travel time models. Using the travel time distribution, we compute the reachability matrix with the travel time threshold as 10 min, as shown in Table 3.

Table 3.

Reachability Matrix

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
1	1	0	0	0	0	0	0	0	0	0	0	0	0.6197	0	0	0	0	0	0	0	0	0.9996	0	0.9573	0	0	0	0.8739	0	0	0
2	0	1	0	0	0	0	0	0	0.7626	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0.9999	0	0	0.9714	0	0	0	0	0
4	0	0	0	1	0	0	0	0.9996	0	0	0	0	0	0	0	0	0	0	0	0	0	0.5968	0	0.6522	0	0	0	0	0	0	0
5	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0.9996	0	0	0
6	0	0	0	0	0	1	0	0	0	0.9997	0	0	0	0	0	0	0	0	0	0	0	0.9857	0	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0.7889	0	0	0	0	0	0	0	0	0	0
8	0	0	0	0.9996	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0.7848	0	0.9865	0	0	0
9	0	0.7626	0	0	0	0	0	0	1	0	0	0	0	0	0.5866	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
10	0	0	0	0	0	0.9997	0	0	0	1	0	0	0	0	0.7838	0	0	0	0.7513	0	0	0	0	0	0	0	0	0	0	0	0
11	0	0	0	0	0	0	0	0	0	0	1	0.8459	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0.9995	0	0	0
12	0	0	0	0	0	0	0	0	0	0	0.8459	1	0.6402	0	0	0	0	0	0	0	0.9997	0	0	0	0	0	0	0	0	0	1
13	0.6197	0	0	0	0	0	0	0	0	0	0	0.6402	1	0	0	0	0	0	0	0	0.5873	0	0	0.7059	0	0	0	0	0	0.7150	0
14	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0.9999	0	0.9999	0	0	0	0	0	0	0	0
15	0	0	0	0	0	0	0	0	0.5866	0.7838	0	0	0	0	1	0	0	0	0	0	0	0.8376	0	0	0	0	0	0	0	0	0
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0.7764	0	0	0	0	0	0	0
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0.9983	0	0	0	0	0	0	0	0	0	0
19	0	0	0	0	0	0	0	0	0	0.7513	0	0	0	0	0	0	0	0	1	0	0	0	0	0.7839	0	0	0	0	0	0.8954	0
20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0.9999	0	0	0	0	0	0	0	0	0.5827
21	0	0	0	0	0	0	0.7889	0	0	0	0	0.9997	0.5873	0.9999	0	0	0	0.9983	0	0	1	0	0	0	0	0	0	0	0	0	0
22	0.9996	0	0	0.5968	0	0.9857	0	0	0	0	0	0	0	0	0.8376	0	0	0	0	0.9999	0	1	0	0	0	0	0	0	0	0	0
23	0	0	0.9999	0	0	0	0	0	0	0	0	0	0	0.9999	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
24	0.9573	0	0	0.6522	0	0	0	0	0	0	0	0	0.7059	0	0	0.7764	0	0	0.7839	0	0	0	0	1	0	0	0	0	0	0	0
25	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0.6892	0	0.7646	0	0
26	0	0	0.9714	0	0	0	0	0.7848	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0.9999	0	0	0	0
27	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0.6892	0.9999	1	0	0	0	0
28	0.8739	0	0	0	0.9996	0	0	0.9865	0	0	0.9995	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
29	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0.7646	0	0	0	1	0	0
30	0	0	0	0	0	0	0	0	0	0	0	0	0.7150	0	0	0	0	0	0.8954	0	0	0	0	0	0	0	0	0	0	1	0
31	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0.5827	0	0	0	0	0	0	0	0	0	0	1

The unavailability/busy fraction of the ambulances in each base station is computed by estimating the total workload divided by the total available time of ambulances in each base station. The aggregate demand for each node is obtained from the call data. Consider the sample data for Nandhanam fire station, where the total number of emergency requests is 373, the total available time of ambulance at Nandhanam fire station is 1,440 h, and the workload of the ambulance in Nandhanam fire station is obtained as 471.82 h, then the busy fraction of the ambulance is approximately computed as 0.328. Using Algorithm 1, we compute the Shapley value for each base station to capture its importance in the ambulance network. The Shapley value in Table 4 indicates the cumulative coverage that each base station provides in the ambulance network while considering the availability of ambulances and the reachability of ambulances to reach the incident location. The call data collected from Chennai for July, August, and September, 2016, is also used to compute the criticality of each base station in the ambulance network. The criticality value in Table 4 represents the average number of calls each base station handles per day.

Table 4.

The Shapley Value of Base Locations

Base station ID	Latitude	Longitude	Criticality	Shapley value
1	13.02058	80.22416	6.13	455.3881
2	13.10961	80.25983	6.51	328.9182
3	13.08193	80.2712	6.58	485.5601
4	13.09997	80.21475	7.04	338.1175
5	12.98538	80.22303	5.84	262.3102
6	13.06827	80.20663	2.13	355.1997
7	13.11687	80.28626	7.64	408.5783
8	13.05614	80.27905	0.81	343.72
9	13.04589	80.2496	2.88	296.2326
10	13.08777	80.28851	8.2	350.118
11	13.07229	80.25846	1.94	184.7591
12	12.9977	80.25568	4.91	539.1631
13	13.05867	80.25423	5.92	567.3878
14	13.125	80.261	9.01	553.088
15	13.07824	80.17408	0.54	304.4624
16	13.0599	80.27869	2.61	198.9992
17	13.09776	80.23018	7.94	350.0285
18	13.07728	80.21835	8.47	459.7515
19	13.11517	80.2235	4.71	500.181
20	13.03592	80.20866	6.63	385.246
21	13.07968	80.28697	10.93	1049.096
22	13.06209	80.26235	6.56	607.7504
23	13.03011	80.2769	5.69	560.5447
24	13.05389	80.22045	6.57	613.7242
25	13.07868	80.24289	12.91	496.4519
26	13.03482	80.22945	5.88	408.9892
27	13.05472	80.265	2.51	440.1747
28	13.07844	80.24288	2.2	448.4362
29	13.06811	80.20518	3.61	401.8302
30	13.08008	80.28741	4.88	358.2766
31	13.02952	80.23757	4.03	346.3454

The Compliance Tables and Comparative Analysis

Using the computed Shapley value, we can develop the Shapley-value-based compliance table such that ambulances should be located at base locations based on the decreasing order of their Shapley values. Table 5 is the Shapley-value-based compliance table. We adapted the MEXCRP model by modifying the constraints that control the number of waiting site changes when the system moves from one state to other ( 11 ). In particular, we defined the constraint such that existing allocation will not change, but some vehicles may move when system state changes lead to the nested compliance table as shown in Table 6. We also developed the nested compliance table based on the criticality of each base station, as shown in Table 7.

Table 5.

Shapley-Value-Based Compliance Table

No. of available ambulances	Ambulance base stations
No. of available ambulances	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	19	30	31
31	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
30	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
29	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
28	1	1	1	1	0	1	1	1	1	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
27	1	1	1	1	0	1	1	1	0	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
26	1	1	1	1	0	1	1	1	0	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
25	1	0	1	1	0	1	1	1	0	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
24	1	0	1	0	0	1	1	1	0	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
23	1	0	1	0	0	1	1	0	0	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
22	1	0	1	0	0	1	1	0	0	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0
21	1	0	1	0	0	1	1	0	0	1	0	1	1	1	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0
20	1	0	1	0	0	1	1	0	0	0	0	1	1	1	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0
19	1	0	1	0	0	0	1	0	0	0	0	1	1	1	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0
18	1	0	1	0	0	0	1	0	0	0	0	1	1	1	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	0	0
17	1	0	1	0	0	0	1	0	0	0	0	1	1	1	0	0	0	1	1	0	1	1	1	1	1	1	1	1	1	0	0
16	1	0	1	0	0	0	1	0	0	0	0	1	1	1	0	0	0	1	1	0	1	1	1	1	1	1	1	1	0	0	0
15	1	0	1	0	0	0	0	0	0	0	0	1	1	1	0	0	0	1	1	0	1	1	1	1	1	1	1	1	0	0	0
14	1	0	1	0	0	0	0	0	0	0	0	1	1	1	0	0	0	1	1	0	1	1	1	1	1	0	1	1	0	0	0
13	1	0	1	0	0	0	0	0	0	0	0	1	1	1	0	0	0	1	1	0	1	1	1	1	1	0	0	1	0	0	0
12	1	0	1	0	0	0	0	0	0	0	0	1	1	1	0	0	0	1	1	0	1	1	1	1	1	0	0	0	0	0	0
11	0	0	1	0	0	0	0	0	0	0	0	1	1	1	0	0	0	1	1	0	1	1	1	1	1	0	0	0	0	0	0
10	0	0	1	0	0	0	0	0	0	0	0	1	1	1	0	0	0	0	1	0	1	1	1	1	1	0	0	0	0	0	0
9	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0	0	0	0	1	0	1	1	1	1	1	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0	0	0	0	1	0	1	1	1	1	0	0	0	0	0	0	0
7	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0	0	0	0	0	0	1	1	1	1	0	0	0	0	0	0	0
6	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	1	1	1	1	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	1	1	1	1	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	1	1	0	1	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	1	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0

Table 6.

Maximum Expected Covering Location Problem (MEXCRP)-Based Compliance Table

No. of available ambulances	Ambulance base stations
No. of available ambulances	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
31	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
30	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
29	1	1	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
28	1	1	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1
27	1	1	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
26	1	1	1	0	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
25	1	1	1	0	0	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
24	1	1	1	0	0	0	0	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
23	1	1	1	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
22	1	1	1	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
21	1	0	1	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
20	1	0	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
19	1	0	1	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
18	1	0	1	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
17	1	0	1	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
16	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
15	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0
14	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	0	1	1	1	1	0
13	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	0	1	1	1	1	0
12	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	0	1	1	1	1	0
11	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	0	1	1	1	1	0
10	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	0	1	1	1	1	0
9	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0	1	1	1	1	0
8	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	1	1	1	1	0
7	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	1	1	1	0
6	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	0
5	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	0
4	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0
3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0

Table 7.

Criticality-Based Compliance Table

No. of available ambulances	Ambulance base stations
No. of available ambulances	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
31	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
30	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
29	1	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
28	1	1	1	1	1	1	1	0	1	1	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
27	1	1	1	1	1	0	1	0	1	1	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
26	1	1	1	1	1	0	1	0	1	1	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1
25	1	1	1	1	1	0	1	0	1	1	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	0	0	1	1	1
24	1	1	1	1	1	0	1	0	1	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	0	0	1	1	1
23	1	1	1	1	1	0	1	0	0	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	0	0	1	1	1
22	1	1	1	1	1	0	1	0	0	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	0	0	0	1	1
21	1	1	1	1	1	0	1	0	0	1	0	1	1	1	0	0	1	1	1	1	1	1	1	1	1	1	0	0	0	1	0
20	1	1	1	1	1	0	1	0	0	1	0	1	1	1	0	0	1	1	0	1	1	1	1	1	1	1	0	0	0	1	0
19	1	1	1	1	1	0	1	0	0	1	0	1	1	1	0	0	1	1	0	1	1	1	1	1	1	1	0	0	0	0	0
18	1	1	1	1	1	0	1	0	0	1	0	0	1	1	0	0	1	1	0	1	1	1	1	1	1	1	0	0	0	0	0
17	1	1	1	1	1	0	1	0	0	1	0	0	1	1	0	0	1	1	0	1	1	1	0	1	1	1	0	0	0	0	0
16	1	1	1	1	0	0	1	0	0	1	0	0	1	1	0	0	1	1	0	1	1	1	0	1	1	1	0	0	0	0	0
15	1	1	1	1	0	0	1	0	0	1	0	0	1	1	0	0	1	1	0	1	1	1	0	1	1	0	0	0	0	0	0
14	1	1	1	1	0	0	1	0	0	1	0	0	0	1	0	0	1	1	0	1	1	1	0	1	1	0	0	0	0	0	0
13	0	1	1	1	0	0	1	0	0	1	0	0	0	1	0	0	1	1	0	1	1	1	0	1	1	0	0	0	0	0	0
12	0	0	1	1	0	0	1	0	0	1	0	0	0	1	0	0	1	1	0	1	1	1	0	1	1	0	0	0	0	0	0
11	0	0	1	1	0	0	1	0	0	1	0	0	0	1	0	0	1	1	0	1	1	0	0	1	1	0	0	0	0	0	0
10	0	0	1	1	0	0	1	0	0	1	0	0	0	1	0	0	1	1	0	1	1	0	0	0	1	0	0	0	0	0	0
9	0	0	0	1	0	0	1	0	0	1	0	0	0	1	0	0	1	1	0	1	1	0	0	0	1	0	0	0	0	0	0
8	0	0	0	1	0	0	1	0	0	1	0	0	0	1	0	0	1	1	0	0	1	0	0	0	1	0	0	0	0	0	0
7	0	0	0	0	0	0	1	0	0	1	0	0	0	1	0	0	1	1	0	0	1	0	0	0	1	0	0	0	0	0	0
6	0	0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	1	1	0	0	1	0	0	0	1	0	0	0	0	0	0
5	0	0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	0	1	0	0	1	0	0	0	1	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	1	0	0	0	1	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	1	0	0	0	1	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0

We use discrete event simulation to compare the coverage provided by different compliance tables. The call data provided by GVK-EMRI shows that the demand at each base location is random. As assumed in the formulation, the base locations and demand locations overlap in our model. Based on the statistical analysis of the data, we infer that the inter-arrival time of emergency requests for each demand location follows an exponential distribution. The empirical and theoretical cumulative distribution function (CDF) of the exponential distribution for calls at Nandhanam fire station are shown in Figure 3a. The P-P plot is shown in Figure 3b to evaluate the fitness of the exponential distribution. We use the Kolmogorov-Smirnov (KS) test to study the goodness of fit of exponential distribution for inter-arrival time of emergency requests at Nandhanam fire station. Based on the KS test, the $p$ -value obtained is 0.3178, which is greater than 0.05 level of significance; therefore, we conclude that our data follows exponential distribution with the average inter-arrival time between the calls being 240.945 min. Similarly, we computed the parameters for other base stations.

Figure 3.

Demand distribution at Nandhanam Fire Station, Chennai. (a) empirical and theoretical cumulative distribution function (CDF) of exponential distribution for inter-arrival times and (b) P-P plot for inter-arrival times based on exponential distribution.

In the simulation, the demand for each location is randomly generated using the parameters of the exponential distribution obtained from the data. The travel time between any demand node and the base station is simulated using the lognormal distribution. The random seeds are initialized to reduce the variability in the system while conducting multiple simulations. We define the threshold for response time as 10 min, and the demand node that can be reached within 10 min is considered covered. Based on the parameters obtained from the data, the simulation is conducted on Python for the realization of 10 days. The simulation is repeated for 50 runs with different sets of random seeds. The results obtained are used to compute the coverage performance metrics. Table 8 shows the expected coverage (in percentage) offered by the system for any given number of ambulances, along with their $95 %$ confidence intervals for different compliance tables. We use the paired-t test with a null hypothesis stating that the coverage performance of the Shapley-value-based compliance table is less than or equal to the criticality-based compliance table and the compliance table developed using the modified MEXCRP. The results in Table 9 indicate that p-values are less than the significance level of 0.05 in most of the cases. Therefore, we reject the null hypothesis and conclude that the Shapley-value-based compliance table provides better coverage, especially when the ambulance network has resource constraints.

Table 8.

Average Coverage by Different Compliance Tables

No. of free ambulances	Criticality-based	Maximum expected covering location problem (MEXCRP)-based	Shapley-value-based
1	4.19 ± 0.075	4.19 ± 0.079	6.06 ± 0.115
2	10.25 ± 0.137	7.57 ± 0.219	12.06 ± 0.197
3	14.67 ± 0.15	13.58 ± 0.319	15.66 ± 0.279
4	18.67 ± 0.195	18.02 ± 0.378	21.41 ± 0.32
5	23.53 ± 0.213	24.46 ± 0.381	24.73 ± 0.335
6	27.7 ± 0.239	28.51 ± 0.461	29.15 ± 0.329
7	30.37 ± 0.236	30.49 ± 0.438	32.99 ± 0.349
8	32.65 ± 0.284	34.09 ± 0.443	35.4 ± 0.338
9	36.17 ± 0.388	37.38 ± 0.452	38.91 ± 0.361
10	39.49 ± 0.514	41.99 ± 0.429	42.93 ± 0.345
11	41.41 ± 0.407	45.59 ± 0.404	46.34 ± 0.314
12	47.6 ± 0.363	47.43 ± 0.395	48.19 ± 0.307
13	49.89 ± 0.36	51.28 ± 0.39	52.18 ± 0.339
14	54.33 ± 0.37	55.27 ± 0.407	56.62 ± 0.351
15	58.81 ± 0.376	57.62 ± 0.429	59.11 ± 0.364
16	61.17 ± 0.388	60.81 ± 0.464	62.5 ± 0.437
17	63.41 ± 0.381	62.8 ± 0.459	65.18 ± 0.437
18	66.66 ± 0.382	67.22 ± 0.434	67.54 ± 0.471
19	69.07 ± 0.389	69.62 ± 0.437	69.39 ± 0.442
20	71.41 ± 0.393	72.03 ± 0.438	71.26 ± 0.366
21	72.97 ± 0.371	73.55 ± 0.477	72.92 ± 0.367
22	75.14 ± 0.307	75.84 ± 0.456	74.91 ± 0.363
23	78.53 ± 0.366	77.36 ± 0.446	78.49 ± 0.352
24	81.18 ± 0.301	78.41 ± 0.439	80.21 ± 0.304
25	83.22 ± 0.301	81.08 ± 0.417	82.22 ± 0.266
26	84.27 ± 0.288	82.8 ± 0.332	83.74 ± 0.234
27	86.06 ± 0.284	85.04 ± 0.311	85.33 ± 0.233
28	87.77 ± 0.198	87.68 ± 0.286	87.62 ± 0.202
29	88.62 ± 0.223	88.94 ± 0.278	89.87 ± 0.187
30	89.42 ± 0.213	90.74 ± 0.239	90.64 ± 0.184
31	91.41 ± 0.206	91.41 ± 0.206	91.41 ± 0.206

Table 9.

Paired t-Test for Coverage Comparison

No. of free ambulances	Criticality		Maximum expected covering location problem (MEXCRP)
No. of free ambulances	t-statistic	P(T ≤t)	t-statistic	P(T ≤ t)
1	27.8147	0.0000	27.2970	0.0000
2	15.8233	0.0000	30.7225	0.0000
3	6.1937	0.0000	9.6576	0.0000
4	14.1816	0.0000	13.2898	0.0000
5	5.9132	0.0000	0.9955	0.3218
6	6.9786	0.0000	2.1308	0.0354
7	11.9064	0.0000	8.4566	0.0000
8	11.7893	0.0000	4.2904	0.0000
9	9.6909	0.0000	4.7774	0.0000
10	10.3248	0.0000	3.0580	0.0028
11	16.9212	0.0000	2.5084	0.0136
12	2.1730	0.0320	2.6025	0.0106
13	7.8664	0.0000	2.8980	0.0046
14	7.0533	0.0000	3.9056	0.0002
15	0.9204	0.3594	4.1738	0.0001
16	3.4595	0.0008	4.2694	0.0000
17	4.5235	0.0000	5.9844	0.0000
18	2.1176	0.0365	0.7769	0.4389
19	0.7751	0.4400	−0.5454	0.5866
20	−0.3850	0.7010	−1.9271	0.0566
21	−0.1323	0.8950	−1.5271	0.1297
22	−0.6180	0.5379	−2.2645	0.0256
23	−0.0983	0.9219	2.6991	0.0081
24	−2.5318	0.0128	4.3318	0.0000
25	−2.4706	0.0151	2.6917	0.0083
26	−1.3146	0.1915	2.3518	0.0205
27	−1.7833	0.0774	0.7085	0.4802
28	−0.3872	0.6994	−0.1438	0.8859
29	3.0549	0.0028	2.2093	0.0293
30	2.9185	0.0043	−0.2566	0.7980
31	na	na	na	na

na = not applicable.

Conclusion

In this paper, we contribute to the literature of 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 $# 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 $O (n^{3})$ time. Using the ambulance demand data of Chennai, India, we conduct a 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 MEXCRP model, when the ambulance network is constrained.

This paper demonstrates the application of coalitional game theory for ambulance repositioning. In this paper, we aggregate the demand at each location for developing the repositioning game. The model can be improved by computing the Shapley-value-based compliance table with the dynamic spatio-temporal demand data. One of the limitations of the proposed model is that we assume ambulances will travel on the optimal path. Because of traffic flow at a given time, the ambulance may take a longer time than usual. The proposed model can be improved by utilizing the framework developed by Amer et al. for the dynamic relocation of ambulances to reduce the response time in the congested network ( 34 ). Another interesting extension is using the Aumann-Shapley value for nonatomic games to identify the important locations for ambulance locations.

Footnotes

Acknowledgements

The authors thank the editor and two anonymous referees for the insightful comments that helped improve the manuscript’s quality significantly. The authors would like to thank GVK-EMRI Chennai for providing the data and their constant support in conducting this study.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: R. K. Amit, T. Rudramoorthi; data collection: T. Rudramoorthi, R. K. Amit; analysis and interpretation of results: T. Rudramoorthi, R. K. Amit; draft manuscript preparation: R. K. Amit, T. Rudramoorthi. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research work is partially funded under Urban Governance Scheme of National Geospatial Programme, Department of Science and Technology (DST), Government of India (NRDMS/U/G/RKAmit/IIT Madras/e-08/2019).

ORCID iDs

T. Rudramoorthi

R.K. Amit

Data Accessibility Statement

The data used for this research are not publicly available because of a non-disclosure agreement but are available from the corresponding author on reasonable request.

References

Wilde

E. T.

Do Emergency Medical System Response Times Matter for Health Outcomes?

Health Economics, Vol. 22, No. 7, 2013, pp. 790–806. https://doi.org/10.1002/hec.2851. https://onlinelibrary-wiley-com-443.web.bisu.edu.cn/doi/abs/10.1002/hec.2851.

Toregas

Swain

ReVelle

Bergman

The Location of Emergency Service Facilities. Operations Research, Vol. 19, No. 6, 1971, pp. 1363–1373. https://doi.org/10.1287/opre.19.6.1363.

Sudtachat

Mayorga

M. E.

Mclay

L. A.

A Nested-Compliance Table Policy for Emergency Medical Service Systems Under Relocation. Omega, Vol. 58, 2016, pp. 154–168. https://doi.org/10.1016/j.omega.2015.06.001.

Toro-Díaz

Mayorga

M. E.

Chanta

McLay

L. A.

Joint Location and Dispatching Decisions for Emergency Medical Services. Computers and Industrial Engineering, Vol. 64, No. 4, 2013, pp. 917–928. https://doi.org/10.1016/j.cie.2013.01.002.

Alanis

Ingolfsson

Kolfal

A Markov Chain Model for an EMS System With Repositioning. Production and Operations Management, Vol. 22, No. 1, 2013, pp. 216–231. https://doi.org/10.1111/j.1937-5956.2012.01362.x.

Koschützki

Lehmann

K. A.

Peeters

Richter

Tenfelde-Podehl

Zlotowski

Centrality Indices. In Network Analysis ( Brandes

Erlebach

, eds.), Springer, Berlin, Heidelberg, 2005, pp. 16–61. https://doi.org/10.1007/978-3-540-31955-9_3.

Shapley

L. S.

A Value for n-Person Games. In Contributions to the Theory of Games (AM-28), Volume II ( Kuhn

H. W.

Tucker

A. W.

, eds.), Princeton University Press, Princeton, 1953, pp. 307–318. https://doi.org/10.1515/9781400881970-018.

Fragnelli

Gagliardo

Gastaldi

A Game Theoretic Approach to an Emergency Units Location Problem. In Springer Optimization and Its Applications ( Mallozzi

D’Amato

Pardalos

, eds.), Springer, Cham, 2017, pp. 171–191. https://doi.org/10.1007/978-3-319-52654-6_8.

Deng

Papadimitriou

C. H.

On the Complexity of Cooperative Solution Concepts. Mathematics of Operations Research, Vol. 19, No. 2, 1994, pp. 257–266. https://doi.org/10.1287/moor.19.2.257.

10.

Fatima

S. S.

Wooldridge

Jennings

N. R.

A Linear Approximation Method for the Shapley Value. Artificial Intelligence, Vol. 172, No. 14, 2008, pp. 1673–1699. https://doi.org/10.1016/j.artint.2008.05.003.

11.

Gendreau

Laporte

Semet

The Maximal Expected Coverage Relocation Problem for Emergency Vehicles. Journal of the Operational Research Society, Vol. 57, No. 1, 2006, pp. 22–28. https://doi.org/10.1057/palgrave.jors.2601991.

12.

Daskin

M. S.

Network and Discrete Location: Models, Algorithms, and Applications, 2nd ed. John Wiley & Sons, Inc., Hoboken, NJ, 2013. https://doi.org/10.1002/9781118537015.

13.

Brotcorne

Laporte

Semet

Ambulance Location and Relocation Models. European Journal of Operational Research, Vol. 147, No. 3, 2003, pp. 451–463. https://doi.org/10.1016/S0377-2217(02)00364-8.

14.

Aringhieri

Bruni

M. E.

Khodaparasti

van Essen

J. T.

Emergency Medical Services and Beyond: Addressing New Challenges Through a Wide Literature Review. Computers and Operations Research, Vol. 78, 2017, pp. 349–368. https://doi.org/10.1016/j.cor.2016.09.016.

15.

Bélanger

Ruiz

Soriano

Recent Optimization Models and Trends in Location, Relocation, and Dispatching of Emergency Medical Vehicles. European Journal of Operational Research, Vol. 272, No. 1, 2019, pp. 1–23. https://doi.org/10.1016/j.ejor.2018.02.055.

16.

Church

ReVelle

The Maximal Covering Location Problem. Papers of the Regional Science Association, Vol. 32, 1974, pp. 101–118.

17.

Daskin

M. S.

A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution. Transportation Science, Vol. 17, No. 1, 1983, pp. 48–70. https://doi.org/10.1287/trsc.17.1.48.

18.

Church

R. L.

Murray

Location Covering Models. Advances in Spatial Science, Springer, Cham, 2018. https://doi.org/10.1007/978-3-319-99846-6. http://link.springer.com/10.1007/978-3-319-99846-6.

19.

Nair

Miller-Hooks

Evaluation of Relocation Strategies for Emergency Medical Service Vehicles. Transportation Research Record: Journal of the Transportation Research Board, 2009. 2137: 63–73.

20.

Bélanger

Kergosien

Ruiz

Soriano

An Empirical Comparison of Relocation Strategies in Real-Time Ambulance Fleet Management. Computers and Industrial Engineering, Vol. 94, 2016, pp. 216–229. https://doi.org/10.1016/j.cie.2016.01.023.

21.

Kolesar

Walker

W. E.

An Algorithm for the Dynamic Relocation of Fire Companies. Operations Research, Vol. 22, No. 2, 1974, pp. 249–274. https://doi.org/10.1287/opre.22.2.249.

22.

Berman

Dynamic Repositioning of Indistinguishable Service Units on Transportation Networks. Transportation Science, Vol. 15, No. 2, 1981, pp. 115–136. https://doi.org/10.1287/trsc.15.2.115.

23.

Gendreau

Laporte

Semet

A Dynamic Model and Parallel Tabu Search Heuristic for Real-Time Ambulance Relocation. Parallel Computing, Vol. 27, No. 12, 2001, pp. 1641–1653. https://doi.org/10.1016/S0167-8191(01)00103-X.

24.

Andersson

Värbrand

Decision Support Tools for Ambulance Dispatch and Relocation. Journal of the Operational Research Society, Vol. 58, 2007, pp. 195–201. https://doi.org/10.1057/palgrave.jors.2602174.

25.

Lee

The Role of Preparedness in Ambulance Dispatching. Journal of the Operational Research Society, Vol. 62, No. 10, 2011, pp. 1888–1897. https://doi.org/10.1057/jors.2010.145.

26.

Jagtenberg

C. J.

Bhulai

van der Mei

R. D.

An Efficient Heuristic for Real-Time Ambulance Redeployment. Operations Research for Health Care, Vol. 4, 2015, pp. 27–35. https://doi.org/10.1016/j.orhc.2015.01.001.

27.

Maleki

Majlesinasab

Sepehri

M. M.

Two New Models for Redeployment of Ambulances. Computers and Industrial Engineering, Vol. 78, 2014, pp. 271–284. https://doi.org/10.1016/j.cie.2014.05.019.

28.

van Barneveld

The Minimum Expected Penalty Relocation Problem for the Computation of Compliance Tables for Ambulance Vehicles. INFORMS Journal on Computing, Vol. 28, No. 2, 2016, pp. 370–384. https://doi.org/10.1287/ijoc.2015.0687.

29.

van Barneveld

T. C.

van der Mei

R. D.

Bhulai

Compliance Tables for an EMS System With Two Types of Medical Response Units. Computers and Operations Research, Vol. 80, 2017, pp. 68–81. https://doi.org/10.1016/j.cor.2016.11.013.

30.

Sudtachat

Mayorga

M. E.

Chanta

Albert

L. A.

Joint Relocation and Districting Using a Nested Compliance Model for EMS Systems. Computers & Industrial Engineering, Vol. 142, 2020, p. 106327. https://doi.org/10.1016/j.cie.2020.106327.

31.

Hotelling

Stability in Competition. The Economic Journal, Vol. 39, No. 153, 1929, pp. 41–57. https://doi.org/10.2307/2224214.

32.

Tamir

On the Core of Cost Allocation Games Defined on Location Problems. Transportation Science, Vol. 27, No. 1, 1993, pp. 81–86. https://doi.org/10.1287/trsc.27.1.81.

33.

Curiel

Cooperative Game Theory and Applications,

Theory and Decision Library, Vol. 16. Springer, Boston, MA, 1997. https://doi.org/10.1007/978-1-4757-4871-0. http://link.springer.com/10.1007/978-1-4757-4871-0.

34.

Amer

H. M.

Al-Kashoash

H. A.

Kemp

Mihaylova

Mayfield

Coalition Game for Emergency Vehicles Re-Routing in Smart Cities. Proc., IEEE 10th Sensor Array and Multichannel Signal Processing Workshop (SAM), Sheffield, IEEE, New York, 2018, pp. 306–310.

35.

Shoham

Leyton-Brown

Multiagent Systems. Cambridge University Press, Cambridge, 2008. https://doi.org/10.1017/CBO9780511811654, p. 386.

36.

Shi

Chen

B. Y.

Estimation of Travel Time Distributions in Urban Road Networks Using Low-Frequency Floating Car Data. ISPRS International Journal of Geo-Information, Vol. 6, No. 8, p. 253. https://doi.org/10.3390/ijgi6080253. https://www-mdpi-com-s.web.bisu.edu.cn/2220-9964/6/8/253.