A comparison of techniques for optimal infrastructure restoration

Abstract

Major disruptions such as terror attacks, natural disasters and human failures can have large impacts on critical infrastructure. The rapid reconstitution of those infrastructure systems after a major disruption is crucial to minimize the impact of the disaster. This thesis compares two different modeling techniques to minimize the cost for reconstructing the infrastructure system. The first technique uses a mixed integer linear program to minimize the operation cost of a infrastructure system. The second technique is a graph-based approach in which the vertices of a meta graph represent different operating states for the infrastructure system, and edges between vertices represent possible transitions between states (e.g., the repair of one or more infrastructure components). In this context, optimal restoration of the infrastructure system corresponds to finding the best (e.g., minimum cost) path from an initial damaged state to a fully restored state. We consider two different ways of finding the shortest path in this meta graph, specifically Dijkstra’s algorithm and the A-star algorithm. We compare these techniques in terms of quality of solution and required computation time.