Skip to main content
JCR.DEV
All work

SSRN preprint

01.5Case Plates

Road Restoration

Reopening the fewest roads after a disaster.

Year
May 2025
Role
Corresponding author
Stack
Python and QGIS
< 2
approximation ratio on all 30 random graphs
12
Istanbul benchmark instances, all within the bound
3.10
worst Greedy ratio, against KMB’s guaranteed 2
Decisions
  1. 01A crew’s real costBlocked roads cost first, open roads second, as they do for a restoration crew.
  2. 02The bound holdsVerified the 2-approximation still holds under the modified cost.
  3. 03Quality over speedKMB takes 8 to 12 seconds where Greedy takes under one, for a guaranteed bound.
Technical notes
Context
Post-disaster road access gates relief, evacuation and repair. The task is selecting the minimum set of blocked roads to reopen so critical sites reconnect: an NP-hard Steiner tree problem.
Role
Corresponding author, with Gerlie Campion, Kathleen Grace Gultiano and Junar Landicho, Department of Computer Science, USTP-CDO.
Timeline
3–4 months.
Approach
KMB modified to minimise a lexicographic cost: blocked road first, unblocked road second, matching the real cost to a restoration crew. The core work was verifying that the 2-approximation bound holds under this modification.
Outcome
The bound holds. Across 30 random graphs every ratio stayed under 2 and most were exactly 1 (optimal), with a standard deviation near 0.03. All twelve Istanbul benchmark instances from Akbari et al. and both Cagayan de Oro networks stayed within the bound.
Performance
KMB runs 8–12 seconds per Istanbul instance against under one second for Greedy, in exchange for a guaranteed bound. Greedy reached ratios of 3.10 and 2.76, and Thresholding runtime ranged from 1.34 to 30.41 seconds. KMB fits restoration planning, where solution quality outweighs latency.

Full stack

  • Python
  • QGIS
  • Graph algorithms
  • Steiner trees
Next projectEnduro Group