Ambulance Planning

Dennis Shasha

Omniheurist Course

Computer Science



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, rescue time)
hospital(xloc, yloc, number of ambulances)

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

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

Here is data and the best solution we could find (from Tyler Neylon).