Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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: enter image description here

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

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).

enter image description here

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. enter image description here

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)

share|improve this question
10  
The problem I can see, is time. If you know of both position 1 and 2 at the same time, then the best decision is to send C to 2 and A to 1. However, unless you have precogniscient dolphins, you don't have this information. The best decision you can make, with the information available, is that which you have in your 3rd diagram. –  Korgan Rivera Nov 7 '12 at 16:24
29  
The strategy of always sending the closest ambulance is akin to using a greedy algorithm for solving optimization problems, as in trying to solve the traveling salesman problem by always going to the closest unvisited location. In general, not an optimal situation. –  Harald Hanche-Olsen Nov 7 '12 at 16:28
5  
@TheShiftExchange the problem is that where events happen would be somewhat random, so you cannot expect to have a strategy that always optimises. What you can expect is a strategy that optimises in the long run (on average). But to actually prove whether a strategy is or is not optimal, we need to know about the typical distance traveled by an ambulance and the typical interval between incidences. If on average events happen infrequently enough then no strategy can beat the "closest responder" one. –  Willie Wong Nov 7 '12 at 16:29
12  
This kind of problem is known as an online job scheduling problem in the unrelated machines model, where the jobs are emergency calls and the machines are ambulances. You'll probably want to cross-post this to the theoretical computer science stack exchange. –  Perce Nov 7 '12 at 16:35
5  
On a side note, in your scenario it might make sense to send A across to the right as soon as C goes out on its call, in order to lower the maximal waiting time for a new emergency. But this sort of consideration will of course complicate the issue further … –  Harald Hanche-Olsen Nov 7 '12 at 16:40

16 Answers 16

up vote 55 down vote accepted

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.

share|improve this answer
3  
Could you clarify this last paragraph for the layman? :-) –  deed02392 Nov 8 '12 at 13:53
1  
@deed02392 Sure, it will take me some time, but I will attempt to do so today :) –  Arkamis Nov 8 '12 at 15:12
    
@deed02392 I have made an attempt at an explanation. –  Arkamis Nov 8 '12 at 21:44
    
That is fantastic, thank you very much for your time. –  deed02392 Nov 9 '12 at 8:27
1  
To explain "Voronoi tessellation" it might be worth including an image from a google image search from that phrase. It certainly helped me understand it. Great explanations though! –  George Duckett Nov 9 '12 at 12:10

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.

share|improve this answer
47  
Indeed, the true objective of any real-world optimization problem is not "compute the maximum of performance" but rather "compute the minimum loss due to litigation"... –  Arkamis Nov 7 '12 at 17:44
2  
In the US anyway, an ambulance is stationed at the base of the agency that owns it, and dispatched only by that agency. Pre-emptive shuffling of vehicles and personnel isn’t generally done outside of a large-scale emergency. –  Jon Purdy Nov 7 '12 at 21:23
    
Thanks Tyler. We already do this (I've just added an FAQ). The problem is due to the significant volume of 'incidents' - we often see that before A can even get close to C's old position, a new incident arrives. The whole situation is very dynamic and changes ever minute. –  TheShiftExchange Nov 7 '12 at 22:27
    
A thought comes to mind. Your solution of distributed servers(ambulances) makes it easier to define a Quality of Service metric and strive to uphold it e.g. maximum time to arrive less than X minutes. –  Vorac Nov 8 '12 at 11:35
    
+1 The best of course is to station ambulances like a game of tennis as you describe. Whenever one "player" moves, the other(s) move to be in an optimal position. The thing is I don't think it is feasible to always have ambulances on the move, and gas is not free. –  lc. Nov 9 '12 at 5:46

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.

share|improve this answer
2  
This sounds like approximately what I would start with -- effectively send BOTH C and A. C gets there first, but shortly there after, A is in the area (certainly faster than if you wait for call 2 to come in before dispatching A). The goal being to establish maintain an even distribution (and thus reduce response times and save lives). –  jmoreno Nov 8 '12 at 5:40
3  
+1 Never thought WoW could help in life & death situations :) –  Laurent Couvidou Nov 8 '12 at 9:56
4  
WoW units don't require fuel. –  Frantisek Kossuth Nov 9 '12 at 9:05

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).

share|improve this answer
7  
+1 for using real-life statistical data: Simulate with call data over the past year, "What would the average (simulated) response times be with the nearest-responder algorithm?" (Maybe you can check these against actual response times for calibration.) "What would the average (simulated) response times be with improved algorithm A? algorithm B?" Then maybe also, "How many individual incidents would have suboptimal response times using algorithm A or B? How suboptimal?" –  LarsH Nov 7 '12 at 20:59
1  
Thanks Vinod - I like your approach - I was thinking of something similar. I was hoping of some formula or mathematical 'proof' that this is the most optimal strategy, apart from just running simulations. Either way, I'm looking into how I might be able to simulate this and see the results. –  TheShiftExchange Nov 7 '12 at 23:14
    
I like this approach, because it's relatively simple. Obviously, you'd have to define what "poor" coverage is sufficiently rigorously to make this practical to apply, but simulations based on real-life data should help pin that down. –  Bobson Nov 8 '12 at 0:55
    
When using real-life data, you need not only the travel times from ambulances to sites, but consider the distribution of calls. For example, an old-folks home might generate two calls per day, whereas Daycare Acres generates one a month. Using this data, you would first determine where the optimal starting stations are in the no-calls situation, and then you can start distributing ambulances based on usage. –  John Deters Nov 8 '12 at 21:11

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.

share|improve this answer
    
wow - that is a really good starting point and "proves" it for two stations. Thanks - I'll look at this more closely... –  TheShiftExchange Nov 8 '12 at 2:03
    
Nice account, but I believe you have an error in calculating the expected travel in the 2 : 1 case. The expected value of x is 0.5, which is greater than 5/8. Hence, the closest ambulance should be dispatched. Please see my answer, which uses the same formalization (endpoints on a unit interval, uniform distribution), and shows that dispatching the closest ambulance is better over all. –  alexis Nov 8 '12 at 18:32
    
---The expected value of x is 0.5, which is greater than 5/8. Hence, the closest ambulance should be dispatched.--- I don't really understand this phrase. Since I showed that your initial approach was incomplete, now it is your turn to pinpoint an error in my argument if you see any :). –  fedja Nov 9 '12 at 15:49
    
Agreed; plus I misspoke, since 0.5 is less than 5/8! :-) Let me go over this again (what is the 5/8 factor in the next step?) –  alexis Nov 9 '12 at 16:43
    
The 5/8 cutoff is only for the first move. After you are left with 2 vehicles, send the nearest for the second call (if you still have a choice). –  fedja Nov 9 '12 at 17:07

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.

share|improve this answer

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.

share|improve this answer
    
Thanks Kaz. I've added a FAQ which might clear some of it up. Note - I would suspect that the most "correct" answer would factor in a weighted response - so the scenario you describe would not occur, or would be factored in. I was more thinking about instances where the difference is only 1-2 miles, not 10. In the case of "10 miles" - the weight formula would mean that the closest ambulance is still sent. –  TheShiftExchange Nov 7 '12 at 23:13

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.

share|improve this answer

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

share|improve this answer

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 the 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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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).

share|improve this answer

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.

share|improve this answer
    
Thanks alexis - I'm just as "open" to proving that dispatch-closet is the correct answer. The whole point of this question is proving something, one way or the other - because at the moment it is only done this way because we "think" it is best - I want proof :) –  TheShiftExchange Nov 8 '12 at 23:27
    
@Alexis. Yes, for the first two incidents sending the nearest car gives better average. However, for the three incidents it gets worse. If the third incident doesn't occur, then the strategy I proposed is inferior, but if it occurs, it is superior. Funny, isn't it? That's why I said "sometimes" in my conclusion. And no, there is no mistake in my computations; just the assumptions are different (3 incidents instead of two for 3 vehicles). –  fedja Nov 9 '12 at 0:46
    
@fedja, thanks for checking but I don't think that's right. Once two vehicles are gone, the situation is completely symmetric: It doesn't matter where the last vehicle is, there's a 50% probability that the third incident will be near it. So there's no way for one strategy to perform better than the other in the third step. –  alexis Nov 9 '12 at 11:52
    
@ShiftExchange, thanks. I'm confident my proof is correct, but I could be deluded of course. Let me know if you have any concerns. And feel free to upvote my answer so that more people can find it and weigh in. (Congrats for having such a hit as your first question, by the way :-) –  alexis Nov 9 '12 at 11:58
    
Yeah, you are right about the third step. This means you are wrong about the first two. Note that after the first step, if you are left with 1-1, you have a great advantage over being left with 2-0 (1/4 against 1/2 for the expected distance on the second call). That's what I exploited when saying that it is beneficial to send the A-vehicle a bit further. I'll have to go over your argument carefully to see where the mistake is... –  fedja Nov 9 '12 at 13:50

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.

share|improve this answer
3  
downvoters, would you mind explaining the downvote please? Thanks. –  peterph Nov 8 '12 at 13:17
    
Downvoting is anonymous on Stack Exchange; also, asking for explanation of downvotes is considered noise and should not take place in comments (it shouldn't be asked at all). –  casperOne Nov 8 '12 at 15:10
1  
If I had to conjecture, it would be because the answer provides no mathematical content. –  Arkamis Nov 8 '12 at 23:48

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.

share|improve this answer

protected by Qiaochu Yuan Nov 7 '12 at 22:52

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.