#

#
Ambulance Planning

#
Dennis Shasha

#
Omniheurist Course

#
Computer Science

##
*
Description
*

The ambulance planning real-time problem is to rescue as many people as
possible following a disaster.
The problem statement identifies
a set of ambulances at various hospital nodes
a set of delays on the edges, various people in need of help
within a certain time. The problem is to get as many people to the hospitals
on time as possible.

In our case, the graph is the Manhattan grid with every
street going both ways.
It takes a minute to go one block either north-south or east-west.
Each hospital has an (x,y) location.
The ambulances must return to the hospital where they begin.
Each ambulance can carry up to two people.
It takes one minute to load a person and one minute to unload
either one or two people.
Each person will have a rescue time which is the number of minutes
from now when the person should be unloaded in the hospital
to survive.
By the way, this problem is very similar to the vehicle routing
problem about which there is an enormous literature.
If anyone wants to take a break from programming, he/she may volunteer
to look up that literature and propose some good heuristics.

So the data will be in the form:

person(xloc, yloc, rescuetime)

hospital(xloc, yloc, numambulance)

Here is a
typical scenario from Dr. Dobb's journal,

In our case, there will be 5 hospitals and 300 victims.
Here is some typical data with only 50 victims
.
You will have the usual 2 minutes of user time.

Here is data and the best solution we could find (from
Tyler Neylon) but not in the format we want.

Here is a validator written by Yusuke Shinyama
This tar.gz file includes README, sample_data, sample_result,
and sample_wrong_result (which causes a validation error) files.