02.3Research / Corresponding Author3 sheets
Post-Disaster Road Restoration Algorithm Research
Published research adapting the Kou–Markowsky–Berman 2-approximation algorithm to pick restoration routes through a road network broken by a disaster, tested on synthetic graphs, Istanbul benchmarks, and Cagayan de Oro itself.
Mapped restoration solution across a damaged road network
Sheet 1 of 3
Sheet 1 of 3. Mapped restoration solution across a damaged road network
- Tech stack
- Python
- QGIS
- Graph algorithms
- Steiner trees
- Skills
- Algorithm design
- Data analysis
- Technical research
- Context
- After a disaster, the road network is the constraint on everything else — relief, evacuation, repair crews. Clearing it all is not an option, so the question is which subset of blocked roads to reopen to reconnect the places that matter. That is a Steiner tree problem, and it is NP-hard.
- Role
- Corresponding author, with Gerlie Campion, Kathleen Grace Gultiano, and Junar Landicho, in the Department of Computer Science at USTP-CDO.
- Timeline
- About 3–4 months.
- Approach
- We adapted KMB so the cost it minimises is blocked road first, unblocked road second — a lexicographic order, because clearing a blocked road is what actually costs a restoration crew. That modification is the part that could have broken the algorithm’s 2-approximation guarantee, so most of the work was testing whether the bound survived it.
- Outcome
- It held. Across 30 randomly generated graphs every approximation ratio stayed under 2 and most were exactly 1 — the optimal answer — with a standard deviation near 0.03. On the Istanbul benchmark instances from Akbari et al. the ratio stayed within the bound on all twelve, and the same held on Cagayan de Oro and Eastern Cagayan de Oro road data.
- The Trade-off
- KMB is slower, and the paper says so rather than hiding it: roughly 8–12 seconds per Istanbul instance against under a second for the Greedy algorithm. What you buy with that time is a guarantee — Greedy hit a ratio of 3.10 on one instance and 2.76 on another, outside any bound, and Thresholding swung from 1.34 to 30.41 seconds depending on the network. Whether the guarantee is worth the wait depends on whether you are planning the restoration or running it.