Ambulance

Yves Maison introduced himself as a disaster planner.
He didn't say which city he was planning a disaster (response) for,
but it couldn't have
been one of the old ones of his native France, because the
city was laid out in a grid.
"You see, docteur Ecco," he began, "we have a new kind of ambulance that can
carry two beds.
We have 10 such ambulances,
4 at the Austerlitz Hospital, 3 at 
the Pasteur Hospital, and 3 at the De Gaulle Hospital.

"We serve our population very well in normal circumstances.
But we have not a plan for disasters.
That is my job."
With that introduction, Yves lit a cigarette and sat down.
We were all amazed to see a medical person smoking,
but even Liane let it pass.

"Dr. Maison," Ecco said putting a plastic cup
near his guest in lieu of an ash tray, "please tell us more about
your city."

"We are laid out
as a 100 by 100 grid," Maison replied. "Each grid point is an intersection,
so the city is divided in blocks like your Manhattan.
Our hospitals are at positions 
(45, 45), for Austerlitz; (50,50) for Pasteur; and (55,55)
for De Gaulle.

"If there is a disaster, we want to save as many people as possible,
but perhaps not all.
We in France remember the La Grande Guerre 
[World War I to the rest
of Europe] 
where doctors would triage patients
into `require immediate surgery', `can travel back to hospital',
and `will die no matter what'.
We view this as reality in any disaster.

"It takes one minute for an ambulance to travel on block.
To rescue a person takes the time to get to the victim,
plus
3 minutes to get him into the ambulance, plus the time
to get him to the hospital, plus 1 minute
to get him out at the hospital and deliver him
to the emergency room.
Each ambulance fits two victims.
European ambulances can perform some emergency care, but these disasters
are anticipated to require hospital care. 
Each victim has a certain amount of time, called
his survival time, beyond which it is no longer
worthwhile to get him to the hospital.
We want to figure out whom to rescue and by whom.

"We have a sample problem for you and would like to hear how many
people you could rescue in time to enable them to survive.

In our sample problem, we characterize the 30 victims by their positions
and their survival time.

So, for example victim 0 (the first one) is at position (50,55) and 
has a survival time of 35 minutes.
(So, if we don't deliver victim 0 to a hospital in 35 minutes
we don't attempt a rescue.)

0: 50 55 35 
1: 48 64 42 
2: 49 53 32 
3: 53 56 39 
4: 53 48 31 
5: 51 47 28 
6: 52 51 33 
7: 52 50 32 
8: 52 60 42 
9: 47 65 42 
10: 57 54 31 
11: 69 50 39 
12: 57 57 34 
13: 56 58 34 
14: 64 50 34 
15: 62 51 33 
16: 56 56 32 
17: 63 61 44 
18: 60 51 31 
19: 58 53 31 
20: 57 72 39 
21: 66 60 36 
22: 77 56 43 
23: 57 62 29 
24: 65 65 40 
25: 58 69 37 
26: 61 56 27 
27: 65 57 32 
28: 63 70 43 
29: 65 56 31 


"Our question to you is how many people can you rescue, assuming
that each ambulance starting at some hospital H, will pick up
one or possibly two victims (if there is time
for both) and return to hospital H?
We are interested in both an answer and a method."

Ecco and Liane started discussing the method.
I kept hearing words like "pruning" and "greedy", but didn't
catch the details.  
Liane wrote a little program in her favorite language K
and concluded that, with her heuristics, she could rescue
only 14 out of the 30 victims.

{\em Reader: would you like to try, given the initial
distribution of ambulances, which is 4 at (45,45), 3 at (50,50), 
and 3 at (55,55)?}