Optimizing response times of an ambulance corp: short-term versus average
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.
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.
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.
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).