Robust Maximum Flow Network Interdiction Considering Uncertainties in Arc Capacity and Resource Consumption
Sponsor
This work was supported by the National Science Foundation through grants CMMI-1826320/1826337: Collaborative Research: Real-Time Stochastic Matching Models for Freight Electronic Marketplace, CMMI-1562109/1562291: Collaborative Research: Non-Additive Network Routing and Assignment Models, and CMMI-1254921: CAREER: Integrated Multiresolution Transportation Network Modeling.
Published In
Annals of Operations Research
Document Type
Citation
Publication Date
1-18-2024
Abstract
This article discusses a robust network interdiction problem considering uncertainties in arc capacities and resource consumption. The problem involves two players: an adversary seeking to maximize the flow of a commodity through the network and an interdictor whose objective is to minimize this flow. The interdictor plays first and selects network arcs to interdict, subject to a resource constraint. The problem is formulated as a bilevel problem, and an upper bound single level mix-integer linear formulation is derived. The upper bound formulation is solved using three heuristics tailored for this problem and the network structure, based on Lagrangian relaxation and Benders’ decomposition. On average, each heuristic provides a reduction in run time of at least 85% compared to a state-of-the-art solver. Enhanced Benders’ decomposition achieves a solution with an optimality gap of less than 5% for all tested instances. Sensitivity analyses are conducted for the level of uncertainty in network parameters and the uncertainty budget. Robust decisions are also compared to decisions not accounting for uncertainty to evaluate the value of robustness, showing a reduction in simulation maximum flows by as much as 89.5%.
Rights
© 2024 Springer Nature
Locate the Document
DOI
10.1007/s10479-023-05812-6
Persistent Identifier
https://archives.pdx.edu/ds/psu/41359
Citation Details
Chauhan, D., Unnikrishnan, A., Boyles, S. D., & Patil, P. N. (2024). Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption. Annals of Operations Research.