Hybrid algorithms for enhanced efficiency and scalability of network-based tri-level interdiction models

Nafiseh Ghorbani-Renani, Andrés D. González and Kash Barker ()
Additional contact information
Nafiseh Ghorbani-Renani: Stevens Institute of Technology
Andrés D. González: University of Oklahoma
Kash Barker: University of Oklahoma

Journal of Heuristics, 2025, vol. 31, issue 2, No 3, 43 pages

Abstract: Abstract This study focuses on optimizing resilience strategies for interdependent infrastructure networks (e.g., electric power, water supply, transportation system) against intelligent attacks. We formulate this problem as a tri-level defender-attacker-defender (DAD) model, which is known for its computational complexity. To address this challenge, we propose two novel hybrid decomposition-based algorithms: the hybrid Benders decomposition-based (HBD) algorithm and the hybrid set covering-based (HSC) algorithm. These algorithms efficiently solve the nested subproblems (master problem and subproblem) of the tri-level DAD formulation, incorporating metaheuristic algorithms for improved performance. The proposed algorithms are applied to a tri-level protection-interdiction-restoration model to optimize network resilience. Two case studies are used to evaluate the effectiveness of the solution techniques: (i) An interdependent system of water, gas, and power networks with 125 nodes and 164 links, and (ii) A simulated system of two networks with 252 nodes and 507 links. Our results demonstrate that both hybrid algorithms offer high-quality solutions with significantly improved computational efficiency compared to the existing exact solution method based on the set covering approach. In our comparison across different case studies and budget scenarios, we find that for higher budget scenarios, the HBD algorithm outperforms the HSC algorithm and is more computationally efficient. For lower budget scenarios, the performance of both algorithms is similar, with the HSC algorithm showing slightly better performance in terms of computational speed. Both algorithms show clear advantages over the set covering (CD) approach, particularly when available budget grows. This study highlights that the choice between the HBD and HSC algorithms depends on both the case study size and available budget, with the HBD algorithm being preferable in higher budget scenarios and the HSC algorithm being slightly more efficient in lower budget scenarios.

Keywords: Network protection and interdiction; Tri-level optimization; Hybrid solution technique; Decomposition-based method; Interdependent infrastructure networks (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09554-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:2:d:10.1007_s10732-025-09554-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09554-5

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().