Optimizing Resilience in Large Scale Networks

Xiaojian Wu, Daniel Sheldon, and Shlomo Zilberstein. Optimizing Resilience in Large Scale Networks. Proceedings of the Thirtieth Conference on Artificial Intelligence (AAAI), Phoenix, Arizona, 2016.

Abstract

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.

Bibtex entry:

@inproceedings{WSZaaai16,
  author	= {Xiaojian Wu and Daniel Sheldon and Shlomo Zilberstein},
  title		= {Optimizing Resilience in Large Scale Networks},
  booktitle     = {Proceedings of the Thirtieth Conference on Artificial
                   Intelligence},
  year		= {2016},
  pages		= { },
  address       = {Phoenix, Arizona},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/WSZaaai16.html}
}

shlomo@cs.umass.edu