Rerouting evacuees when a shelter fills up
Written byZaki Hattaon
Dijkstra finds the shortest path to safety. Failover Node Elimination makes sure that path still leads somewhere with room.
The shortest route to the nearest shelter is the obvious answer in an evacuation app. It is also the answer every other phone in the neighbourhood gets, which is exactly how a shelter overflows and a road jams.
Starting with Dijkstra
Padang Rescue models the city's roads as a weighted graph and uses Dijkstra's algorithm to find the shortest path from the user to a shelter. It is reliable, well understood and fast on a city sized graph.
Adding a failover
To handle full or blocked shelters, I added a Failover Node Elimination step with a Top-K approach. The app keeps the best K shelter candidates. When one becomes unavailable, its node is removed from the candidate set and the route is recalculated toward the next best option.
- Rerouting to an alternative shelter takes about 0.4066 ms.
- People are spread across shelters instead of all converging on one.
- The user always sees a route, even when the first choice fails.
The lesson carries beyond disaster apps: design for the moment your best answer stops being available.
