AAAI Publications, Thirtieth AAAI Conference on Artificial Intelligence

Font Size: 
Optimizing Resilience in Large Scale Networks
Xiaojian Wu, Daniel Sheldon, Shlomo Zilberstein

Last modified: 2016-11-02


We propose a decision making framework to optimize the resilience of road networks to natural disasters such as floods. Our model generalizes an existing one for this problem by allowing roads with a broad class of stochastic delay models. We then present a fast algorithm based on the sample average approximation (SAA) method and network design techniques to solve this problem approximately. On a small existing benchmark, our algorithm produces near-optimal solutions and the SAA method converges quickly with a small number of samples. We then apply our algorithm to a large real-world problem to optimize the resilience of a road network to failures of stream crossing structures to minimize travel times of emergency medical service vehicles. On medium-sized networks, our algorithm obtains solutions of comparable quality to a greedy baseline method but is 30–60 times faster. Our algorithm is the only existing algorithm that can scale to the full network, which has many thousands of edges.


Network Design; Resilience Optimization;

Full Text: PDF