Optimizing response times of an ambulance corp: short-term versus average

Question

Background: I work for an Ambulance service. We are one of the largest ambulance services in the world. We have a dispatch system that will always send the closest ambulance to any emergency call. There is a belief that this results in the fastest response time as an average across the system.

Example: Suppose we have the following simplified scenario. We have 3 ambulances available (labelled A, B and C). At any given point in time, there is an random chance of an emergency call originating equally anywhere inside this box:

If an emergency job appears (labelled 1), we will send the closest ambulance (in this case Ambulance C)

You will notice that Ambulances A and B are very close together on the left side of the box (lets pretend they are just leaving a hospital after dropping off their patients). There is now a large gap on the right. Suppose a small amount of time passes, and another emergency call drops in (labelled 2).

Ambulance C is no longer available, so you must use Ambulance A or B. They have a significantly longer distance to travel to reach incident 2. In this case we have sent Ambulance A to the job.

Hypothesis: If you always send the closest ambulance to an emergency call, you will have the quickest response time to that specific call, but the overall average response time of the ambulance service is not optimised.

Using that hypothesis - it would seem to be better to send Ambulance A or B to the original incident 1. This would mean the the next incident to happen, there will be "on average" a significantly shorter distance for the next ambulance to travel.

Question: How can I "prove" this? Is there a mathematical theory or formula? This is obviously a simplifed scenario, there are some other issues - but I just need to prove the fundamental issue that the "closest ambulance being sent to the next incident" actually results in a non-optimal response time across the system as a whole.

To answer some generic concerns:

"Just move A to C's location after C goes on the job" Yes - we already try to do this - however there is often another "incident" before A gets into the new position. And for other reasons {which are beyond this question} it is not always an option.

"Why are A+B so close together? Perhaps B should be elsewhere?" There are lots of reasons for ambulances to be 'clumped' together. The main reason is they have probably just offloaded a patient at a hospital - this often causes uneven dispersal of ambulances resources. Other reasons include the physical locations of our stations/depots.

"Volume of work" We are one of the largest ambulance services in the world. In my scenario I have 3 ambulances. In reality there are approx 100 ambulances, and we service approx 2000 "incidents" per day in our main metropolitan area. At some points in time we run at very high capacity - i.e. almost every ambulance is on an 'incident' - so applying a optimal response strategy across the system will have a significant impact to our response times.

"Ethics of not sending closest ambulance" Yes - this is not just a mathematical issue. But for the purpose of this Stack Exchange, please limit responses to a mathematical answer. In regards to ethics, I would suggest that if we can lower the "overall" response time (i.e. from 12mins to 10min average) - then "overall" we are ethically providing the best service. If we use a sub-optimal response, and "overall" we provide a slower response, then is not a bad ethical decision? Also - there would probably be exceptions to the rule (i.e. a heart attack or choking would ALWAYS get the closet ambulance - because seconds matter. But for this scenario lets not make it complicated)

Answer 1

Operations problems like this are tricky, because they always include a large element of uncertainty.

As Willie Wong points out, it is possible to construct a scenario in which "closest-first" is a non-optimal strategy. However, proving that there exists a non-optimal strategy does not mean that globally such a strategy is non-optimal.

Wait, what?

In these cases, you have to consider the probability distribution of events as a spatio-temporal process. In such a case, you may construct an algorithm for dispatching emergency services that is almost never optimal for any isolated case, but is globally optimal over all possible cases!

Here is an example: say that your region is circular, and that events only happen on the circumference. Your job is to determine where inside the circle to position your only ambulance. If the distribution of emergency events is uniformly distributed over the circumference, the solution is clearly to position the ambulance at the center of the circle. However, this solution is not optimal for any individual event.

Your question is to prove that the closest ambulance first scheme is not optimal "across the system as a whole." In order to prove that, you need to establish that the probability of a second event happening closer to $C$'s original position than any other ambulance within the time it takes for $C$ to complete its call is higher than not.

If the process is truly Poisson (i.e. completely spatially random in a 2-D region), then this process is simple -- the area of $C$'s Voronoi tessellation would need to be greater than half of the area of your district, assuming that the process intensity is such that the expected call time is short enough that only one event happens on average with Poisson intensity $\lambda$.

---

Let's explain that last paragraph.

Let's say that you run an ambulance service in Squareville, Australia. This city is completely flat, square, has no roads, and is one unit wide by one unit high.

Say emergencies happen randomly, anywhere in the city. This can be described by a completely uniform spatial 2D point process; the distribution of such a process is called a Poisson distribution. In a Poisson 2D point process, existing points have no influence on the location of the occurrence of subsequent points -- indeed, the location is truly random.

Let's say in an hour, $n$ events occur. The area of Squareville is 1 square unit. This leaves us with an average spatial intensity of $n$ events/unit area. This is known as the intensity factor, or Poisson parameter, often called $\lambda$ and is equivalent to both the mean and variance of the distribution.

In other words, $$\lambda = n.$$

Now, let's take a connected subset of Squareville, called Squareville Heights. This subset has some area less than 1, let's call it $a < 1$. Because the area of Squareville is 1 square unit, Squareville Heights covers exactly $100a$ percent of Squareville. (For example, if $a = .5$, the region covers 50% of the city).

If you look at the number of events that occur in this region, the average number will be $\lambda a$ -- the global probability, times the area of Squareville Heights. This turns out to be exactly $100a$ percent of the events.

We can look at this another way.

Let's take an hour, and chop it into small intervals $dt$ that are small enough that in any finite region of the city, no more than one emergency will occur. The probability of this emergency happening in Squareville Heights is exactly $a$.

---

Let's say we have $k$ ambulances distributed somehow throughout Squareville. We want to investigate the probabilities of events happening closer to one ambulance than to another. It turns out this is very easy.

Let $A$ be the co-ordinates of your ambulances. The Voronoi tesselation of a point pattern, $V(A)$, is a set of 2D regions such that each $v_i$ in $V(A)$ is the subset of Squareville such that every point in $v_i$ is closer to ambulance $a_i$ than to any other ambulance.

If an emergency happens in $v_i$, then $a_i$ will be the closest ambulance to the event.

We can inspect the probabilities. Let's say that an emergency happens in $v_1$, and $a_1$ responds. Now let a second event occur while $a_1$ is still responding. The probability of this happening in $a_1$'s original Voronoi tile, $v_1$, is exactly the area of $v_1$, denoted $|v_1|$.

As a result, we can then compute -- in this trivially simplified case -- the probability that sending $a_2$ to the first call would be better than $a_1$.

In this case, there is a $|v_1|$ percent chance that holding $a_1$ and sending $a_2$ to the first call will result in a response-time reduction for the second call.

If the ambulances are also randomly distributed, the mean areas of the tiles will be about .33; however, operationally, the distribution of ambulances is not Poisson, so you will probably have some ambulances that possess relatively large Voronoi tiles.

Answer 2

I have little familiarity with ambulances and am not sure if they are stationed when on call, such as a fire truck, but if they are not then you could simply position them such that the distance from any point in the region to the nearest ambulance is minimized. When a call comes in, the nearest ambulance could respond and the entire formation would reposition immediately such that the distance from any point to any current ambulance was again minimized.

Not sending the nearest available ambulance to an emergency sounds like a liability nightmare.

(Edit) If the ambulances must be stationed, I would propose the same solution with the only placement positions for the ambulances being the available stations.

In your example, I would still respond with C, and as soon as C leaves I would send A to C's station.

Answer 3

I actually see this problem a lot, believe it or not, in World of Warcraft.

The problem is vastly simplified, granted, as it comes in the context of a wargame with fixed points to defend and attack. But the general idea is the same: one may have, say, three points to defend. If one base comes under attack, the natural thing to do is to reinforce it--forces not engaged in combat are wasted, after all, but one still has to have adequate protection for the other two bases to deter an opportunistic attack. What I would do is move forces from the closest unthreatened base to the base being attacked, and then reinforce that base with forces from the furthest base. So lots of people are in motion, but each has a relatively short distance to go, compared to sending from the furthest base.

So, I suspect--though I certainly couldn't say I can prove--that the optimal strategy here is to still use ambulance C to respond to the initial call and then move ambulance A to a position such that, for any random point in the box, the expected best response time of A and B is minimized. When C becomes available again, move A back to the configuration that is optimal for 3 ambulances.

By no means do I want to suggest this as the overall strategy without some level of rigor. I think the things you would want to consider are what the usual timescales are between time to respond to a call, tend to a call, and time between calls.

Answer 4

What I propose is this: Before assigning an ambulance to a call, check the coverage of that ambulance's current vicinity by OTHER ambulances. If you find the coverage to be poor, run the same algorithm on the SECOND nearest ambulance, and so forth. (Fundamentally, what we're trying to do is not just assign an ambulance to a call, but to assign an ambulance whose absence will not drag average times down too much.)

To prove its usefulness, I think you can use real-life statistical data and compare real-time response times vs. simulated response times (i.e. the calls are real-time data, but ambulance assignments are hypothetical).

Answer 5

Let's simplify the situation to the limit so that you'll see clearly what is going on without heavy computations. Assume that you have two stations at $A$ and $B$, which are $1$ mile apart on a straight road and you get calls from random places in between independently with the uniform distribution. Assume also that the total number of calls is exactly the same as the total number of vehicles. Start with the simplest case when you have $a$ vehicles at $A$ and nothing at $B$. Then you have no choice, so the average travel distance is $\frac a2$. The same is true if your vehicles are all at $B$. Now suppose that you have $1$ vehicle at $A$ and $1$ vehicle at $B$. Then for every position $x$ of the first call ($A=0$ and $B=1$), no matter which vehicle you send, the second call will be at the average distance $1/2$ from the remaining vehicle. Thus, your best bet for the first call is to send the nearest vehicle to it, averaging the distance $1/4$ with the total average $3/4$ for two calls. Suppose now that you have $2$ vehicles at $A$ and $1$ at $B$. Now it gets interesting. Let $x$ be the position of the first call. If you send the vehicle at $A$, you'll travel $x$ and will be left with the $1-1$ situation, which averages to $3/4$. So, your total is $x+\frac 34$. If you send the $B$-vehicle, you travel $1-x$ but after that you are left with $2-0$ and average $1$. So $A$-vehicle should be sent if $x+\frac 34<1-x+1$, i.e., if $x<5/8$. The average will be then $\frac 58(\frac 5{16}+\frac 34)+\frac 38(\frac 3{16}+1)=\frac{71}{64}$. For comparison, the nearest vehicle strategy will give $\frac 12(\frac 14+\frac 34)+\frac 12(\frac 14+1)=\frac 98$. There is a small gain of $\frac 1{64}$ on three calls if you use the optimal strategy. Now let us assume that we have $3$ vehicles at $A$ and $1$ at $B$. Let's run the same analysis. Let $x$ be the place of the first call. If you send an $A$-vehicle, you get $x+\frac{71}{64}$ for the expectation. If you send the $B$-vehicle, you get $1-x+\frac 32$. Now the cutoff is at $x$ satisfying $2x=\frac 52-\frac{71}{64}=\frac{89}{64}$, so $x=\frac{89}{128}$, i.e., now it makes sense to use the better staffed station more than $2/3$ of the way on the first call. I guess you see now what's going on: the better staffed stations (or the places with more stations per unit area) should sometimes be given preference even when the distance is larger (but not too much larger). It is not hard to make a full analysis of this two station model even when the number of calls is random and you have $a$ vehicles at $A$ and $b$ at $B$ and I'll gladly do it for you if you get interested and if I find free time (if you got the idea, you can play with it yourself too now). How much will it tell about the real life? Well, as much as any overly simplified math. model: the general conclusion is correct but the exact cutoffs, etc. are not very realistic.

Answer 6

If you just want an explicit example, make your second incident happen exactly where C is stationed. Then in the scenario where

A picks up incident 2, C picks up incident 1

the total distance traveled is "distance between 1 and C" plus "distance between A and C" (since 2 is where C is stationed).

In the scenario where

A picks up incident 1, C picks up incident 2

the total distance traveled is "distance between A and 1" plus "distance between C and 2" (which is zero).

So we draw a picture with A, C, and 1 on it. The total distance traveled in the first scenario is two legs of the triangle formed by the three points. The total distance traveled in the second scenario is only one leg of the triangle. By the triangle inequality, the sum of lengths of two legs of one triangle must be bigger than the length of the third. This shows that the total distance traveled in scenario one, which is the "closest responder" scenario", can be non-optimal.

Answer 7

This is a neat problem and can be approached using stochastic calculus and non-linear optimization. I don't believe its explicitly solvable unless trivial assumptions are made. I'll first describe a way to optimize the initial positions of the ambulance. We will then use cost functions developed in from this optimization to discuss how sending a different ambulance effects response time for future visits.

Things you will need:

EventPdf(x,y): A Probability Distribution Function that describes the probability that an emergency event will occur in over an area. Some models might be equal probability in a bound range, equal probability proportional to population density, the best may be a PDF constructed from real world emergencies occurances.

AverageEmergencyTime: A constant or PDF describing how long an ambulance will be unavailable when going to a call. You can probably get away with a normal distribution or constant on this one.

Cost function:

You'll need a cost function that you will attempt to minimize. You'll probably start with this in time. This will probably include:

Standard Movement Cost: The average cost in time to move from one position to another. You'll achieve this by integrating over a combination of the ambulance position (x_i,y_i) and their distance from a service area times the frequency of calls in that area. For a grid element you'll always take the cost from the least expensive ambulance.

ElementCost(x,y,x_i,y_i) = distanceFrom(x,x_i,y,y_i)*EventPdf(x,y);

LeastElementCost(x,y) = Min( AmbulanceList.ElementCost(x,y) );

TotalStandardCost = integral(serviceAreaBounds) {(Least_Movement_Cost(x,y))}; 

This will give you a baseline for computing average response time.

ModifiedCost_i - Removed Ambulance Movement cost: You'll need to then compute the cost if one or more of these ambulances is removed.

W_i: You'll weight these proportional to the standard cost based on how likely they will be removed and how long they will be removed for. If you have alot of idle time, the standard will be weighted heavily. If one ambulance is almost always busy, you'll find the others weighted heavily. I'm not going to model this, but it can be modeled. You might want to throw out unlikely scenarios.

Cost: Now you construct a total cost function to be minimized.

Cost = W_0*TotalStandardCost + W_1*ModifiedCost_1 ... W_N*ModifiedCost_N

Now you put this into a non-linear optimizer, with x_i,y_i for each ambulance as input variables, and your Cost variable as an output and you tell it to minimize your cost by selecting x_i and y_i for the ambulances.

---

Anyway, this is a good starting point and is a somewhat realistic model but needs alot of work. You may want to weight your costs more heavily for long response times (e.g. getting sued for taking to long). You may also want to account for ambulances being able to move to new positions when one is busy.

Now that we have a good model we can address your question of sending a different ambulance rather than the closest ambulance. Now we assume a predefined set of x_i,y_i for each ambulance. We can makes changes to the function:

LeastElementCost(x,y) = Min( AmbulanceList.ElementCost(x,y) );

To pick out a different ambulance than the closest one for a response. This will create a different PDF for each of the weighted costs. Integrating over the new PDF will compute a new total cost that can be compared to the unmodified one, it will tell you if you benefit from sending a different ambulance.

This is a discrete case and can't be handled with a continuous solver. If you have a small number of ambulances ( N is not large), you can search over the entire solution space. I'm betting it'd take a few seconds for 10 ambulances if its coded right.

Answer 8

Scheduling algorithms have only access to information about the past, and are making guesses about what will optimize the unknown future. You have no clue when or where the next emergency will occur. By not sending the closest ambulance to a current emergency, you're risking somebody for a potential gain, which seems unethical. What if you send an ambulance from 10 miles away instead of from 2 miles away, and someone dies? And after that incident, there is no emergency for another 45 minutes?

The problem of keeping the ambulances geographically distributed can be solved without doing away with the closest ambulance policy.

If an ambulance is dispatched somewhere, what you can do is instruct other ambulances to move around in order to keep the ambulances evenly distributed.

Answer 9

I would approach this by making clear assumptions to you model first.

if you say that

1) all points in the square are equiprobable for an incident

2) all incidents must be responded to by immediately sending an ambulance

3) the cost (time) can be measured as the simple distance between two points

=>you would always try to to have the ambulances distributed across the area (here square) as uniformly as possible.

=> you can always send the nearest ambulance immediately

=> directly after, you send the remaining ambulances to the new points for optimal coverage

=> if two ambulances are equidistant from an incident, you send the one which makes the other ambulances travel as little as possible to reach the new coverage points.

I am sure that this can be proven, however I am not sure if these assumptions are acceptable for you...

Cheers Fab

Answer 10

I think first you need to prove that better assignments are possible with hindsight. Get a log with, for each call, the time the ambulance was sent out, the positions of the ambulances and of the incident, the ambulance sent, and the time of arrival. If the availability of ambulances varies, also log the times that they are in service. If this information isn't available, make it available. Collect these logs for a year (the density of incidents and maximum traveling speed are likely to fluctuate).

Now you can make a model of travel times between any two points in the area on any time of the day.

Based on this model, determine, per day in the log, all alternative assignments of ambulances to incidents and for each assignment compute the sum of the expected travel time from assigned ambulances to incidents. Plot the results. Show how much of a difference it makes. Translate into numbers of lives lost or similar. Do circumstances matter? (Is the difference lower or higher when the density of incidents is higher?)

Once you've done this, you've established that a different assignment policy may exist that will improve the average response time in the long run. The next step is to propose such an algorithm and to compare the assignments it produces against the actual assignments in the log. One idea is to estimate the probability of an incident occurring per area and per time of day, and somehow use this in deciding which ambulance to send.

Answer 11

I think we should discuss the modeling of the scenario a bit before discussing optimizing the strategies handling it.

First thing is, we have an area relevant for the scenario that has a probability for an emergency to occur. This probability surely is directly proportional to the density of inhabitants, to the dangers connected with living there. In a big city that is only partly covered with your "area", the emergency probability is likely to be equally high everywhere. Compare this to having ambulances A and B inside a medium town, and ambulance C in a small town, with nothing but outback in between - the emergency probability would have some hot spots around each ambulance with nothing in between.

Second thing is: How urgent can every emergency call be? Not every emergency call is the same. While several situations require medical assistance, only some of them require immediate attention because lifes are in danger. This directly influences the dispatching of any ambulance car: If the second emergency needs more immediate attention, unless the ambulance C has already reached incident 1, can be rerouted to incident 2 while ambulance A or B can be sent to handle incident 1. But this topic is one of the solving strategies, let's save it for later.

Third thing is the positioning of the ambulances. Is having them stationary on defined spots required, or might they be located anywhere? Is every ambulance connected to it's home spot, or are they able to occupy ANY defined spot - at least temporarily.

Fourth: The thing missing is the fact that an emergency evolves in several phases. 1. Emergency call is received. 2. Ambulance is dispatched. 3. Ambulance is on it's way to destination. 4. Ambulance arrives and does first help. 5. Ambulance leaves emergency and transports casualty to a hospital. 6. Ambulance delivers casualty at hospital. 7. Ambulance leaves hospital and returns. 8. Ambulance arrives at home base. (Instead of the visit to the hospital, the ambulance might directly return home.) At each of these phases the ability of the ambulance to react to a new emergency call might be different, so this might offer an option to change plans if incident 2 gets known. But even being unable to change the plan for an already dispatched ambulance, the relevant factor is how long it usually takes to fully handle an emergency call.

Im pretty sure reality inflicts plenty of more factors that have to be considered, like rush hour, quality of the roads, average and maximum speed, etc. but they should be irrelevant for this discussion.

Edge cases: The time it takes for ambulances A or B to arrive at incident 2 has to be less than it takes for ambulance C to handle incidents 1 and 2 one after another, otherwise it's useless to think about dispatching them.

Now about strategies. If we construct a scenario where the two incidents happen within few minutes after each other, and it is impossible to reroute an already dispatched ambulance because the second emergency would be more life threatening, this ambulance will take way longer to handle it's incident than it takes the second ambulance to arrive, and the positions for all the ambulances are fixed, and no ambulance should be sent elsewhere because of the first incident happening, then there really is nothing left to change to improve the situation.

Having the incident handling set in stone allows you to calculate the likeliness of such unfortunate situation to occur based on the factors I described above: a) How likely is it that two incidents occur shortly after another? b) How likely is it that the second incident occurs in a place that is located nearer to the now dispatched ambulance? Think about the emergency probability distribution on the map. c) How likely is it that the second incident is more urgent than the first, and the first is so unhasty that the proper order would be to handle the second first if both emergencies would have been reported at the same time, thus allowing to choose the order.

If you think about it, it might be easy to construct a scenario where dispatching ambulance A to the first emergency makes sense: If ambulance C is located in an area with high emergency probability, thus high probability of two emergencies to occur, and both being equally urgent, and ambulance A being close enough that it can reach emergency 1 in time. But in such a scenario it might be a better option to permanently relocate ambulance A next to ambulance C to improve the situation, because the probability distribution for an emergency would make it somehow predictable that such a situation will occur.

I would conclude that it is in general the best strategy to send the nearest available ambulance to any emergency that occurs. Deviating from such strategy can only be justified if the initial location of ambulances is suboptimal compared to the probability of an emergency.

Answer 12

It seems your (mathematical) intuition is wrong, at least under the constraints you specified. Let's firm them up as follows:

1. The goal is to optimize the average time it takes to reach an incident.

2. The starting locations of the ambulances are fixed. The question is what order to dispatch them in.

3. Once an ambulance is dispatched, it is permanently unavailable: It cannot serve other incidents during the same trip, or return to service before the end of the calculation.

Note that after the second ambulance is dispatched, there is only one ambulance left, and it no longer matters where, timewise: There's a 50% chance that the third incident will be in the opposite side of the map. So, the question is: Starting with the 2 : 1 configuration you present, which dispatch strategy will result in the quickest response, on average, over the first two incidents?

The result can be generalized to larger sizes, but the two-incident case is instructive. The answer will surprise you: The nearest-ambulance strategy is better!

A, B ----------------------'---------------------- C

Let's draw a line from A/B to C, and label it as the interval [0, 1]. An incident is a uniformly distributed random variable t in this interval. We can equate response time to distance: If there are ambulances on both sides, the response time to an incident at point t is min(t, 1-t). If ambulance A must be dispatched, the response time is simply t.

The expected value of t, E(t), is 0.5. Obviously t is closer to the left if t < 0.5. It's easiest to consider scenarios by grouping incidents into two random events: Let's call an event L if t is in the left half of the range (t < 0.5), and R if it is in the right half. Then R and L occur with probability 0.5 each.

There can be four two-incident patterns, occurring with equal probability (0.25): LL, LR, RL, RR. If you could always dispatch from the closest side, the expected travel is 0.25 per incident. You incur a cost when you have to dispatch from the wrong side of the map. The expected length of a "long" trip is 0.75.

So, the payoff matrix is:

incidents   dispatch closest   dispatch A
 L L            A, B             A, B
 L R            A, C             A, C
 R L            C, A             A*, B
 R R            C, A*            A*, C

The right column is your proposed strategy: dispatch A first, then whichever is closest. A star means that the ambulance had to make a long trip (from the wrong side of the map) to get there. Note that there are more stars (penalties) on the right column.

The fourth row in the table is the one you're worried about: What if there's another incident on the right side of the map, after you've dispatched C? The answer is, don't worry! The bottom row has exactly the same cost under the two strategies: When you dispatched A to the first incident, you already incurred the cost you were trying to avoid in the second incident.

But the third case is one you didn't factor in: What if you send A on a long trip, and then C is not needed after all? In this case, dispatch-A will take longer than the dispatch-closest algorithm.

Since dispatch-A is not better under any scenario, dispatch-closest is superior on average.

Informal summary: If C is closer but you dispatch A, as you propose, you incur a penalty equal to the benefit you will reap if the next incident is nearer to C. So you would break even at best. But the next incident might be closer to A, and you'll never get to collect on your investment. Conclusion: Dispatching the closest ambulance is the better strategy. You can only do better by improving the distribution of ambulances before the second call comes in, as various others suggested. Once the phone rings, sending the closest car is in fact globally optimal.

Answer 13

Considering that there is no real way to know where or when the next call comes in then there is no real way to pick an ambulance other than the current closest one.

However, you can alter the situation a bit in order to optimize response times.

To do this rebalance the equation. What I mean by this is that once ambulance C has responded to the first call, then you should reposition ambulance A to provide equal coverage across the given area.

This means that ambulances must be constantly manned and they will be in motion quite a bit moving from one part of the area to another. This will result in increased costs (for example gas). However, if you pay attention and properly place your ambulances while constantly rebalancing the target coverage you will end up with reduced response times.

Answer 14

I'd like to work the solution in a slightly different way, by refining the model to conform a bit more to reality, and also decrease the problem complexity a bit.

In reality there isn't a continuum of points across the space which are being dealt with, but rather a discrete set of vertices (addresses) connected by (or placed along) edges (roads) of some length (weights) (in other words, the ambulances can't travel through space freely, like a helicopter, but have to use roads to get between points). Additionally the roads are directed in most cities (one-way streets) so we can take lanes of traffic flow to each be a unique edge in a weighted digraph. Additionally each "incident location" can be stated to occur at the intersection closest to the address of the event along the edge (since that's just a shortest distance along a line problem and is easily found).

So to be clear my assumptions are the following:

• The incidents occur at intersections only (as they are aggregated to the closest intersection to the actual location of incident)
• The ambulances must travel along the roads between intersections
• Roads have lengths (which can also be thought of as travel times) between intersections (weights), and directions (for one-way travel).

This means that the problem can be reduced to a weighted digraph within the space. The objective then becomes to minimize the average time taken for an ambulance to get from its current location to any other location after a sequence of random events.

There is some additional information we can get from this model however, mainly the fact that a vertex will have a probability of incident relative to the number of people within its range of effect. As a result the probability distribution need not be considered uniform anymore (Which allows much easier optimization).

Additionally the graph can be thought of as a planar graph in most cases due to the way roads in any service area are likely considered. This gives a very restricted model (of less mathematical complexity) compared to the original (which is also a better approximation of reality).

Now, for optimization of the response times, let's take another thing into consideration, that the vertex is only considered "in" the graph with probability equal to the probability that an incident will occur at the vertex (a fuzzy set). There is then a "maximal" fuzzy dominating subset of the vertices which will have the highest probability of forming a dominating set over the graph (A set for which every vertex is adjacent to at least one vertex in the dominating set). The ambulances will the attempt to move towards this arrangement constantly unless they are "used" (going to or unloading at a hospital).

To be mathematically clear: Given a fuzzy graph $G = (V,E)$ with probability that a vertex v is in G of $\mu_v$

for $D \subseteq V$, D dominates V with probability P(V).

The probability of a set dominating the graph is then the aggregate probability of all of the vertices existing, and the probability that their removal from the graph will cause a non-dominated graph (the expression is a complicated dependent events probability over the entire graph).

By taking only the set which maximizes this as the objective we will minimize the distance from an event that an ambulance is likely to have to travel (which optimizes positioning). The ambulance which should be sent to any location is then the one for which a ratio of the difference in dominating probability should that ambulance go, to the distance of the ambulance from the event:

So given the set of ambulances $A = {a_1, ..., a_n}$ (which can also be thought of as the vertex closest to their location), the one which should go would then be: $$max(\frac{|P(D)-P(D-{a_i})|}{\delta(a_i,v)} | a_i \in A) = min(\frac{P(D-a_i)}{\delta(a_i,v)} | a_i \in A)$$ Where $\delta(a_i,v)$ is the minimum sum of edge weights between the ambulance $a_i$ and the vertex where the problem happened v (all of these factors will vary dependent on the particular situation in question).

Answer 15

Do you have some legal obligations you must comply with? Some countries have laws that guarantee (to some degree of course) the citizens that ambulance arrives in some specified time frame after an incident has been reported. Which is (probably) actually more important than arriving as soon as possible, since there are some physiological processes that simply are time constrained and had help arrived later it would have just wasted resources.

In such a case you might want to take into account how big unserviceable area would be created by sending C to 1 in the sense of the time constraint and compare it with the same area created by sending A there (because A is either not located at exactly the same place as B or the probability of an incident there is much higher). You "just" need to find the least wrong metric that would take into account at least the most important factors.

Of course - as already mentioned - real-life data will help you a lot. It can even show, that the current distribution of stations is suboptimal with respect to the long-term statistical distribution of incidents.

Answer 16

I think @Gracchus has a great insight into this problem in proposing the Kelly Criterion as a way to attack it.

The late Thomas Cover of Stanford and other information theorists, following Kelly and incorporating his ideas, have looked at similar problems. They developed "universal" multivariate optimization approaches, that may very well give you a good way to approach and think about this problem.

These universal approaches have applications in "Universal Data Compression", "Universal Portfolios", gambling, and a wide range of other areas.

Let me see if I can do them justice.

These approaches don't have parameters to fit. They make no assumptions about the underlying probability distribution. They make no attempt to predict the future. Yet their performance can converge upon that of some most successful approach as if it had hindsight.

In framing your problem universally, I think you can consider an infinite set of ambulance locations (@Gracchus already kind of thinks like this). Consider each actual ambulance call an event. After each event calculate the response time of every possible ambulance location.

Rank the response times and accumulate these rankings over all historical events. Finally, find the location of the mean-historically-ranked location.

This "mean ranked" or weighted location will drift over time as random clusters of event locations emerge and dissipate. It won't necessarily stay at the center of your area.

In use, I'd guess that you could use this universal locating algorithm in two steps. Calculate the universal location after each event. Send the ambulance closest to the universal location to the next call and until you have the next ranking, shift your staging of ambulances so that you have an ambulance heading for the location of the most recently calculated universal position. When the most recently dispatched ambulance reaches its target, recalculate and reposition.

This doesn't "follow the leader" by assuming that the next call will come from the same place as the last. I think it would place your ambulances at a kind of the center of gravity of an adaptive optimization.

Such approaches have something in common with evolution. Darwin said or implied that the strongest, fastest, or smartest, don't necessarily succeed in the next random events that face the next generation, but rather those whose genetic makeup have placed them in the best position to adapt to whatever really does come next.

Evolution doesn't speculate about the probability of future events. It doesn't predict the future. I think these universal approaches have some of the same properties.

The approach also has the interesting ability that you can easily adapt it to the actual times that it takes ambulances to respond, rather than just assuming distance as the measure. Over time it would adapt to things like traffic, population density, accidents or events that affect more than one person.

Cover and others have proofs for these kinds of approaches.

These approaches have some limitations. They like lots of events to process. The larger the number of events the more closely they approach their optimum performance.

Still, it seems like something that might prove useful.