Search

Network-based systems widely appear in different service, community, industrial, and economic systems such as electric power, water supply, transportation, and telecommunication networks. Due to the significant role of such systems in society, it is essential to have an effective plan to enhance the resilience of infrastructure networks against disruption (e.g., natural disasters, malevolent attacks, or operational failures). In relation to the concept of resilience, two relevant questions arise: (i) how does performance degrade after a disruption, or what is the vulnerability of the system? and (ii) how rapid does the disrupted system return to the desired performance level, or how can we characterize the system’s recoverability? To enhance the resilience of a system against disruption, we address simultaneous actions of vulnerability reduction and recoverability enhancement through interdiction model, particularly defender-attacker-defender (DAD) model. As such, the first contribution of this research is to propose a tri-level protection-interdiction-restoration problem for a system of interdependent networks, to balance vulnerability and recoverability before and after a disruption. In particular, the proposed tri-level model represents decisions made (i) by a defender before a disruption to reduce network vulnerability, (ii) by an attacker to effectively disrupt the network, and (iii) by a defender after the disruption to enhance recoverability. To solve the proposed protection-interdiction-restoration model to optimality, we use a tailored extension of the covering decomposition algorithm. To illustrate the proposed tri-level model and the modified covering decomposition algorithm, we present a case-study of the system of interdependent water, gas, and power utilities in Shelby County, TN. The computational results show the value of simultaneous analysis of both pre-disruption investments (to reinforce critical network components) and post-disruption resource assignment and crew scheduling. Interdiction models have a wide variety of real-world applications from military to facility location problem to project management. DAD formulation is a type of interdiction model that can be applied to study the resilience of a system against intelligent attacks. However, DAD models are computationally challenging to solve, requiring efficient solution methods to deal with such complex problems. As the second contribution of this research, we address this issue by designing a decomposition-based solution algorithm as a general framework to optimally solve tri-level DAD models in more efficiently. The proposed solution technique is demonstrated with the existing DAD model, namely a tri-level protection-interdiction-restoration model. To define the critical components subject to protection and disruption, an efficient clustering technique is applied which results in generating three sets of candidate components based on three centrality measures. We represent an illustrative case study based on the system of interdependent infrastructure networks in Shelby County, TN, for which we solve the model and assess the computational results for each set of candidate components. The results indicate that the proposed solution algorithm substantially outperforms the traditional covering decomposition method with regard to computational complexity, particularly for the higher budget scenarios. In addition, we compare and analyze the results of the existing interdiction model, the protection-interdiction-restoration formulation represented by M-I, with a new protection-interdiction-counteraction model, denoted by M-II, in which the restoration level is not considered. Results suggest that although M-I is a comprehensive interdiction model relative to M-II, it suffers substantially from computational complexity. Therefore, there exists a tradeoff between employing a more comprehensive model with higher computational complexity and neglecting the recovery process with the interdiction model. The third contribution of this research is to develop a general framework for novel hybrid solution techniques that are applicable in a wide range of interdiction (particularly DAD) models. Hence, we propose two hybrid algorithms that solve smaller nested bi-level problems (master problem and subproblem) to cope with the computational burden of tri-level DAD models. The first solution approach integrates Benders decomposition method with a metaheuristic algorithm, while the second combines a set covering approach and metaheuristic algorithm. The two hybrid algorithms are applied to solve the existing DAD model, namely a tri-level protection-interdiction-restoration model. Two systems of interdependent networks with different sizes are studied to demonstrate the efficient solvability of the developed solution approaches for real-sized problems. The results highlight the capabilities of the two solution approaches for solving such a complex model under different budget scenarios in terms of the quality of solution and computational time. Finally, we address optimization of protection strategies of a critical infrastructure network for cascading failures. This work aims to enhance network resilience against cascading failures initiated by intentional attack with a model that accounts for both pre- and post-disruption planning. The proposed model is a novel DAD model determining (i) which component needs to be protected prior to the disruptive event, (ii) which component is critical in terms of its failure by itself along with causing other parts failures defined as cascading failures, and (iii) what restoration crew schedule is efficient following a disruptive event. To verify the model for cascading failures, we focus on interdiction and restoration levels of this formulation. We present a case study of IEEE 9-bus electric power test system consisting of 9 buses, 3 generators, and 3 loads indicated transshipment, supply and demand nodes, respectively. The results indicate how an initial damage could propagate throughout the system resulting in further disruption and system loss.