-
-
Hero section
-
Map
-
Road Closures & Explanation
Inspiration
I have always been interested in using my software skills for NPO/nonprofit impact. Although reaching out to multiple local and international NPOs offering my help and expertise, none of them landed a fit with me yet. Coming across this hackathon gave me the motivation to take the initiative and start a project with a meaningful purpose and real-world impact on society. Since I live in Doha, Qatar, I wanted to build something grounded in a place I actually know, using Doha's real road network rather than a generic city.
What it does
ReliefRoute finds the fastest road routes from supply depots to areas in need during a crisis, then decides how much aid should move along each route based on what each depot can supply and what each area actually needs. Roads and depots can be toggled live to see how routing adapts.
How we built it
After research, I realized the routes needed to reflect actual road distances, so I implemented Dijkstra's algorithm from scratch and combined it with Doha's OSMnx road graph to route across real streets. Upon further exploration, I realized calculating the shortest path alone doesn't solve the actual problem. The closest depot isn't necessarily the right depot to use, because using up its limited supply might leave another need point stranded. Then I added a "Min-Cost Max-Flow" algorithm from scratch which allowed the system to account for how much supply each depot actually had and split it across need points accordingly, making it a far more effective solution. To draw individual route lines on the map, I needed to know how much flow moved along each specific depot/need pair, not just the overall total the algorithm returns. MCMF tracks a "reverse edge" for each connection, and its capacity after the algorithm finishes equals exactly the flow that moved forward, so I read thar flow per pair instead of computing it separately. Finally, on the frontend, I built the interface by hand with HTML and CSS. No frameworks used. I styled it around a maroon and sand color palette embodying the values and colors of my country. The Folium map is embedded directly into the page.
Challenges we ran into
The MCMF algorithm started looping infinitely, specifically hitting a "parent cycle detected" state around one of the need points. There wasn't a crash, no traceback, the algorithm just kept cycling through the same nodes forever. After further investigation, I traced it down to the residual graph containing a cycle that should've summed to zero cost, but floating point rounding made it slightly off from exactly zero, creating small, fake cost improvements on paths that were mathematically supposed to be equal. Since the algorithm saw these as genuine improvements, it kept reassigning parents, which created an everlasting cycle in the parent chain. I fixed it by adding a tolerance threshold instead of a strict inequality, < distance - 1e-9 instead of <. I also changed the algorithm to build fresh copies of distance and parent at each pass instead of changing them while the algorithm is still working.
Accomplishments that we're proud of
I'm proud of the Dijkstra algorithm, built from scratch with no libraries and verified against NetworkX's built-in implementation to confirm it was correct. I'm equally proud of the Min-Cost Max-Flow algorithm, also built from scratch using Bellman Ford, where I found and fixed a real numerical stability bug that was causing the algorithm to loop infinitely. Beyond the algorithms, the whole system is integrated with Flask and deployed live on Render, with depots, need points, and road closures all toggleable in real time. Every toggle triggers an instant recalculation of the optimal routes, running on Doha's real road network.
What we learned
I learned that the shortest path alone doesn't solve true optimal resource allocation. The closest depot isn't always the right depot because of the limited supply. I also came to the realization that an algorithm can be mathematically correct on paper and still fail when floating point arithmetic comes into play. Both lessons shifted my approach on problems; think about the actual constraints surrounding my algorithms before implementation, and never fully trust an implementation until all edge cases have been tested.
What's next for ReliefRoute
This project was built as a proof of concept to explore real routing algorithms end to end, not because I believe Qatar's existing disaster-response infrastructure has a gap this fills. That said, there are a few directions I'd genuinely want to take it further. I plan to add real-time road-closure data while also improving the performance of the algorithm, allowing it to scale smoothly. I also plan on generalizing the system to work with any city which OSMnx provides, not just Doha.
Log in or sign up for Devpost to join the conversation.