No road left behind: Optimal assignment of emergency routes during flooding

Abstract

The Philippines is highly susceptible to flooding, which can fragment connected street networks into flooded components and paralyze emergency response efforts. In alignment with mandates for local government units (LGUs) to enhance disaster response, we present a graph-theoretic framework for optimizing rescue missions to these flooded regions while ensuring exhaustive road coverage. We identify connected components in the Pasig street network across various flooding scenarios and create hub-and-spoke graphs originating from a central transport hub to these inundated street sub-graphs. We solve a Chinese Postman Problem (CPP) in these graphs with a sorting heuristic to find an approximate solution that visits every edge. We find up to 23 priority missions in the worst flooding scenario, and 3 in the best-case scenario. Our system, combined with ground-based decisions, can complement the current assignment strategies of emergency routes for disasters.