A route generated by our algorithm
User specifies their location
Confirmation that they are in the system
The inspiration for our project came from hearing about the massive logistical challenges involved in organising evacuations for events such as Hurricane Florence. We felt that we could apply our knowledge of solving optimisation problems to great effect in this area.
What it does
ResQueue is a web-app that is designed to be deployed by an aid organisation that is organising rescue or evacuation efforts. It provides an interface for people in need of rescue to mark their location and the urgency of their request on a map.
In the admin interface the aid organisation is able to define the resources it has in terms of capacity and quantity of vehicles (i.e. 3 busses with 50 seats. 5 minibuses with 10 seats). Using clustering followed by path finding a route is generated for each vehicle that provides an efficient overall plan for rescuing as many people as possible, as fast as possible.
How we built it
The WebApp was built using Python combined with the Flask web framework. It was all hosted on Azure, with the database being an Azure Cosmo DB instance. This infrastructure setup would allow us to scale the project in times of crisis.
The routing is done using OpenStreetMap data, combined with the C++ based OSRM project. Groups of people who are required to be rescued are clustered using a minimum spanning tree based approach, combining additional weather data obtained from the IBM Cloud Weather API and self-reported required urgency. A greedy heuristic of the Travelling Salesman (farthest-insertion algorithm) was used to select the final order of visiting the users in each cluster.
Challenges we ran into
As the technical core of the problem, we were attempting to solve (The Travelling Salesman Problem and other vehicle routing problems) is NP-Hard. Due to the fact that we knew that no exact algorithm with an acceptable running time exists we needed to determine a tradeoff between execution time and performance. We did this by reading papers and experimenting with various heuristics and implementations.
We set up automatic scaling resources with Azure, this was necessary to allow for preprocessing of the OpenStreetMap data to be done in a reasonable timeframe. OSRM also used a non-standard GPS coordinate ordering. this cost us a tremendous amount of time and sanity.
Accomplishments that we're proud of
We managed to complete our project to a standard we can be proud of in the time frame allocated. We hope that what we have developed can be used to help those in need.
In doing so we came up with novel solutions to the tough technical challenges we faced and made difficult decisions and tradeoffs along the way.
What we learned
We learned a great deal about the current state of the art in solving TSP. It was also a first for all of us using Azure's services.
What's next for ResQueue
We will probably continue to add to ResQueue, there were many other cool features that didn't make the final cut suggested both from within the team and also from passerby hackathon-ers.
- A companion app for both drivers and rescuees to allow Uber-like tracking
- Support for special cases such as needing wheelchair accessible vehicles
- General improvements to the algorithms used, both efficiency and accuracy
- Allowing admins to geofence the area they are able to service.