Predisaster Preparation of Transportation Networks

Hermann Schichl, Meinolf SellmannAAAI 2015 · DOI

Introduction

The Predisaster Transportation Network Preparation (PTNP) problem is a critical challenge in disaster management. When a major event like an earthquake occurs, transportation infrastructure—such as roads and bridges—is subject to probabilistic failure. The goal of PTNP is to determine which specific links should be "strengthened" or retrofitted within a fixed budget to minimize the expected shortest-path distance between critical locations, such as residential areas and hospitals, in the aftermath of the disaster.

Methodology

Traditional stochastic programming approaches to this problem struggle with the exponential number of failure scenarios. This research introduces a more efficient path-based approach integrated with advanced Constraint Programming (CP).

Path Bundling

Instead of evaluating every possible scenario, the authors identify the $r$ shortest simple paths for each origin-destination pair. They then calculate the probability that any given path will be the actual shortest path post-disaster. This "path bundling" technique effectively collapses a massive scenario space into a manageable set of calculations.

The Extreme Resource Constraint

The core technical innovation is the ExtremeLinearResource (ELR) constraint. Because the objective function is monotonic—meaning additional investment never worsens the outcome—an optimal solution must fully exhaust the budget. Unlike a standard knapsack constraint that only enforces an upper bound, the ELR constraint mandates that no further investments can fit within the remaining budget.

Visualization of the dynamic programming state space used by the Extreme Resource Constraint propagator to prune the search space.

The authors developed a propagator for this constraint using Dynamic Programming (DP). By enforcing that the budget must be exhausted, the solver can immediately infer that certain investments must be made if others are rejected, turning a loose optimization problem into a tightly constrained search. They provide a highly effective $O(nC)$ heuristic version of this propagator that prunes the search space aggressively.

Benchmarks and Datasets

The algorithm was evaluated on several high-fidelity benchmarks:

  • Istanbul Earthquake Benchmark: Based on a 2010 study of Istanbul’s medical support network.
  • Bay Area Earthquake Benchmark: A new, larger benchmark introduced in this paper. It models the Highway Evacuation Plan for the California Bay Area, involving evacuation routes from San Francisco, Oakland, and San Jose.
The Bay Area Earthquake Benchmark network, featuring critical evacuation routes and nodes across a large-scale urban environment.

The Bay Area benchmark represents a significant leap in complexity, involving over 3 million potential failure scenarios.

Key Results

The proposed CP approach demonstrates remarkable performance improvements over previous state-of-the-art methods:

  • Massive Speedups: On the Istanbul benchmark, the algorithm found optimal solutions in milliseconds, compared to approximately five minutes for previous methods—a speedup of two to three orders of magnitude.
  • Scalability: The system successfully solved the massive Bay Area benchmark in just a few seconds, proving its capability for real-time or large-scale urban planning.
  • Optimality and Flexibility: The method proved global optimality for instances that previously required approximation. Furthermore, it remained robust across various objective functions, such as minimizing the maximum expected travel time increase or the sum of squares of travel time ratios.

Conclusion

By leveraging the monotonicity of the PTNP problem through the Extreme Resource Constraint, the authors transformed a complex stochastic optimization task into a highly efficient search process. This methodology allows disaster planners to solve realistic, large-scale network preparation problems in seconds, providing a powerful tool for increasing urban resilience.

Summary updated

BibTeX
@inproceedings{schichl2015predisaster,
  author = {Hermann Schichl and Meinolf Sellmann},
  title = {{Predisaster Preparation of Transportation Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9247},
}
Figure