Stochastic Maximum Flow Network Interdiction with Endogenous Uncertainty

Sadeghi, Somayeh; Seifi, Abbas

doi:10.22034/2019.3.2

Stochastic Maximum Flow Network Interdiction with Endogenous Uncertainty

Document Type : Research Paper

Authors

Department of Industrial Engineering and Management Systems, Amirkabir University of Technology, Tehran, Iran

10.22034/2019.3.2

Abstract

We describe the two-stage maximum flow network interdiction problem under endogenous stochastic interdiction. Our model consists of two agents playing a Stackelberg game. A smuggler who wishes to maximize the expected flow of some illegal commodities that can be transmitted between a source and a sink without being detected. On the other hand, an attacker tries to minimize the flow of drugs by installing some detectors or adding some security controls on critical arcs to increase the probability of detection. We consider a stochastic program under endogenous uncertainty in which the interdictor’s decisions can alter the probability of detection. The problem can be formulated as a bilevel program in which the attacker, having a limited budget, chooses critical arcs to install detectors and enhances the interdiction probability of those arcs. The bottom level problem is a two-stage problem to maximize the flow in the network by smugglers. A bilevel decomposition algorithm has been applied to solve the problem by adding some Benders’ cuts iteratively. We applied a successive method, to deal with non-linearity arising in the probability measure of each path. A case study of drug trafficking network is applied to recognize which countries have the most significant effect in interdicting the drug trafficking network. The police can concentrate on those areas to decrease drug flow. Our results demonstrate that if the critical arcs are chosen wisely to enhance and the probability of opium seizers decrease slightly, a significant reduction in the expected total flow of drugs can be achieved.

Keywords

Main Subjects

logistics, transportation, distribution, and materials Handling

References

Akbari-Jafarabadi, M, Reza Tavakkoli-Moghaddam, M Mahmoodjanloo, and Yaser Rahimi. (2017). A Tri-Level r-Interdiction Median Model for a Facility Location Problem under Imminent Attack. Computers & Industrial Engineering, Vol. 114, pp. 151–165.

Altner, Douglas S, and Nelson A Uhan. (2009). The Maximum Flow Network Interdiction Problem : Valid Inequalities, Integrality Gaps, and Approximability. Operations Research, Vol. 38(1), pp. 1–12.

Assimakopoulos, Nikitas. (1987). A Network Interdiction Model for Hospital Infection Control. Computers in biology and medicine, Vol. 17(6), pp. 413–422.

Bayrak, Halil, and Matthew D Bailey. (2008). Shortest Path Network Interdiction with Asymmetric Information. Networks, Vol. 52(3), pp. 133–140.

Borndörfer, Ralf, Guillaume Sagnol, and Stephan Schwartz. (2016). An Extended Network Interdiction Problem for Optimal Toll Control. Electronic Notes in Discrete Mathematics, Vol. 52, pp. 301–308.

Chen, Yan, Cheng Guo, and Shenghan Yu. (2019). Bi-Objective Optimization Models for Network Interdiction. RAIRO-Operations Research, Vol. 53(2), pp. 461–472.

Church, Richard L, Maria P Scaparra, and Richard S Middleton. (2004). Identifying Critical Infrastructure: The Median and Covering Facility Interdiction Problems. Annals of the Association of American Geographers, Vol. 94(3), pp. 491–502.

Cormican, Kelly J., David P. Morton, and R. Kevin Wood. (1998). Stochastic Network Interdiction. Operations Research, Vol. 46(2), pp. 184–197.

Granata, Donatella, Gregory Steeger, and Steffen Rebennack. (2013). Network Interdiction via a Critical Disruption Path: Branch-and-Price Algorithms. Computers & Operations Research, Vol. 40(11), pp. 2689–2702.

Israeli, Eitan, and R. Kevin Wood. (2002). Shortest-Path Network Interdiction. Networks, Vol. 40(2), pp. 97–111.

Jabbarzare, Ziba, Hossein Zolfagharinia, and Mehdi Najafi. (2019). Dynamic Interdiction Networks with Applications in Illicit Supply Chains. Omega, in press.

Laumanns, Marco, Steven Prestwich, and Ban Kawas. (2014). Distribution Shaping and Scenario Bundling for Stochastic Programs with Endogenous Uncertainty. Stochastic Programming E-Print Series, in press.

Lei, Xiao, Siqian Shen, and Yongjia Song. (2018). Stochastic Maximum Flow Interdiction Problems under Heterogeneous Risk Preferences. Computers & Operations Research, Vol. 90, pp. 97–109.

Liberatore, Federico, Maria P Scaparra, and Mark S Daskin. (2011). Analysis of Facility Protection Strategies against an Uncertain Number of Attacks : The Stochastic R-Interdiction Median Problem with Fortification. Computers and Operation Research, Vol. 38(1), pp. 357–366.

Lim, Churlzu, and J. Cole Smith. (2007). Algorithms for Discrete and Continuous Multicommodity Flow Network Interdiction Problems. IIE Transactions, Vol. 39(1), pp. 15–26.

Malaviya, Ajay, Chase Rainwater, and Thomas Sharkey. (2012a). Multi-Period Network Interdiction Problems with Applications to City-Level Drug Enforcement. IIE Transactions, Vol. 44(December), pp. 368–380.

Michalopoulos, Dennis P., J. Wesley Barnes, and David P. Morton. (2014). Prioritized Interdiction of Nuclear Smuggling via Tabu Search. Optimization Letters, Vol. 9(8): 1477–1494.

Morton, David P, Feng Pan, and Kevin J Saeger. (2007). Models for Nuclear Smuggling Interdiction. IIE Transactions, Vol. 39(1), pp. 3–14.

Nehme, Michael Victor. (2009). Two-Person Games for Stochastic Network Interdiction : Models, Methods, and Complexities. University of Texas, Austin.

Pan, Feng, and Aaron Schild. (2016). Interdiction Problems on Planar Graphs. Discrete Applied Mathematics, Vol. 198, pp. 215–231.

Qiao, Jianhong et al. (2007). Allocating Security Resources to a Water Supply Network. IIE Transactions, Vol. 39(1), pp. 95–109.

Rad, M Afshari, and H Taghizadeh Kakhki. (2013). Maximum Dynamic Network Flow Interdiction Problem : New Formula- Tion and Solution Procedures. Computers & Industrial Engineering, Vol. 65, pp. 531–36.

Ramirez-marquez, Emmanuel, Daniel E Salazar A, and Claudio M Rocco S. (2010). Bi and Tri-Objective Optimization in the Deterministic Network Interdiction Problem. Reliability Engineering and System Safety, Vol. 95, pp. 887–96.

Ramirez-Marquez, José Emmanuel, and Claudio M. Rocco S. (2009). Stochastic Network Interdiction Optimization via Capacitated Network Reliability Modeling and Probabilistic Solution Discovery. Reliability Engineering & System Safety, Vol. 94(5), pp. 913–921.

Rocco S., Claudio M., and José Emmanuel Ramirez-Marquez. (2010). A Bi-Objective Approach for Shortest-Path Network Interdiction. Computers & Industrial Engineering, Vol. 59(2), pp. 232–240.

Sadeghi, Somayeh, Abbas Seifi, and Elnaz Azizi. (2017). Trilevel Shortest Path Network Interdiction with Partial Fortification. Computers & Industrial Engineering, Vol. 106, pp. 400–411.

Salmeron, J, K Wood, and R Baldick. (2004). Analysis of Electric Grid Security under Terrorist Threat. Power Systems, IEEE Transactions, Vol. 19(2), pp. 905–12.

Scaparra, Maria P, and Richard L Church. (2008). A Bilevel Mixed-Integer Program for Critical Infrastructure Protection Planning. Computers & Operations Research, Vol. 35(6), pp. 1905–1923.

Smith, J. Cole, and Yongjia Song. (2019). A Survey of Network Interdiction Models and Algorithms. European Journal of Operational Research, in press.

Smith, J Cole, Mike Prince, and Joseph Geunes. (2013). Modern Network Interdiction Problems and Algorithms. In Handbook of Combinatorial Optimization, eds. Panos M. Pardalos, Ding-Zhu Du, and Ronald L. Graham. New York, NY: Springer New York, 1949–1987.

Soleimani-Alyar, Maryam, Alireza Ghaffari-Hadigheh, and Fatemeh Sadeghi. (2016). Controlling Floods by Optimization Methods. Water Resources Management, Vol. 30(12), pp. 4053–4062.

Song, Yongjia, Siqian Shen. (2016). Risk-Averse Shortest Path Interdiction. INFORMS Journal on Computing, Vol. 28 (No. 3), pp. 527-539.

Steinrauf, Robert L, and R Kevin Wood. (1991). Network Interdiction Models. thesis.

Von Stackelberg, H. (1952). The Theory of the Market Economy. William Hodge.

Wollmer, R. (1964). Removing Arcs from a Network. Transportation Research Part B: Methodological, Vol. 12, pp. 934–940.

Wood, R.Kevin. (1993). Deterministic Network Interdiction. Math. Comput. Model. Vol. 17(2), pp. 1–18.

Zhang, Jing, Jun Zhuang, and Brandon Behlendorf. (2018). Stochastic Shortest Path Network Interdiction with a Case Study of Arizona – Mexico Border. Reliability Engineering & System Safety, Vol. 179(November 2017), pp. 62-73.