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.