No Access

Order-Guided Non-Conservative Maximum Flow in Uncertain Network Interdiction Problem with Budget Constraint

Badri Prasad Pangeni

https://orcid.org/0009-0003-9348-3119

Tribhuvan University, Prithvi Narayan Campus, Pokhara, Nepal

E-mail Address: badripangeni@gmail.com

Search for more papers by this author

and

Tanka Nath Dhamala

https://orcid.org/0000-0003-3390-9707

Tribhuvan University, Central Department of Mathematics, Kathmandu, Nepal

E-mail Address: tanka.nath.dhamala@gmail.com

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S1752890924500053Cited by:1 (Source: Crossref)

Abstract

Probability theory in decision science fails in the absence of sufficient data. In these situations, uncertainty theory is applied to the problem-solving process, taking into account the opinions of the domain experts. In order to minimize the maximum flow carried by the evader, we describe an interdiction problem in an uncertain network with intermediate storage and resource constraints. Such approaches would help law enforcement combat drug-related and smuggling activities.

This work first converts the bi-level deterministic conservative model of the interdictor vs evader problem (IEP) into a non-conservative deterministic IEP. With intermediate storage, a binary interdiction variable, and an interdiction resource constraint, the model is further transformed into an uncertain measure-based model. Then, utilizing uncertainty theory, the uncertain model is again converted into its deterministic equivalent. We have presented two techniques to identify the arc that the interdictor needs to block and to direct the order-guided maximum flow that the evader needs to deliver to the target. The models’ and algorithms’ efficacy is confirmed by an example. Lastly, a graphic representation of the shifting trend of the value of the objective function (VOF) is shown for a range of confidence levels.

Keywords:

References

1. A. W. McMasters and T. M. Mustin , Optimal interdiction of a supply network, Nav. Res. Logist. Q. 17 (1970) 261–268. Crossref, Google Scholar
2. N. Assimakopoulos , A network interdiction model for hospital infection control, Comput. Biol. Med. 17 (1987) 413–422. Crossref, Google Scholar
3. D. Morton, F. Pan and K. Saeger , Models for nuclear smuggling interdiction, IIE Trans. 39 (2007) 3–14. Crossref, Google Scholar
4. C. Lim and J. C. Smith , Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Trans. 39(1) (2007) 15–26. Crossref, Google Scholar
5. K. M. Sullivan et al., Securing a border under asymmetric information, Nav. Res. Logist. 61(2) (2014) 91–100. Crossref, Google Scholar
6. R. A. Konrad et al., Overcoming human trafficking via operations research and analytics: Opportunities for methods, models, and applications, Eur. J. Oper. Res. 259(1) (2017) 733–745. Crossref, Google Scholar
7. R. D. Wollmer , Removing arcs from a network, Oper. Res. 12 (1964) 934–940. Crossref, Google Scholar
8. E. P. Durbin , An Interdiction Model of Highway Transportation (Rand Corporation, 1966). Google Scholar
9. R. D. Wollmer , Algorithms for targeting strikes in a lines-of-communication network, Oper. Res. 18(3) (1970) 497–515. Crossref, Google Scholar
10. R. K. Wood , Deteministic network interdiction, Math. Comput. Model. 17 (1993) 1–18. Crossref, Google Scholar
11. A. Malaviya, C. Rainwater and T. Sharkey , Multi-period network interdiction problems with applications to city-level drug enforcement, IIE Trans. 44(5) (2012) 368–380. Crossref, Google Scholar
12. M. Afshari-Rad and H. Taghizadeh-Kakhki , Maximum dynamic network flow interdiction problem: New formulation and solution procedures, Comput. Ind. Eng. 65 (2013) 531–536. Crossref, Google Scholar
13. M. Soleimani-Alyar and A. Ghaffari-Hadigheh , Solving multi-period interdiction via generalized Benders decomposition, Acta Math. Appl. Sin. 33 (2015) 633–644. Crossref, Google Scholar
14. X. Fu and E. Modiano , Network interdiction using adversarial traffic flows, IEEE INFOCOM 2019-IEEE Conf. Computer Communications (IEEE, 2019), pp. 1765–1773. Crossref, Google Scholar
15. K. J. Cormican, D. P. Morton and R. K. Wood , Stochastic network interdiction, Oper. Res. 46 (1998) 184–197. Crossref, Google Scholar
16. D. L. Woodruff , Network Interdiction and Stochastic Integer Programming (Kluwer Academic Publishers, 2003). Crossref, Google Scholar
17. F. Pan, Stochastic network interdiction: Models and methods, Ph.D. Thesis, The University of Texas, Austin (2005). Google Scholar
18. J. Zheng and D. A. Castanon , Stochastic dynamic network interdiction games, American Control Conference (2012). Google Scholar
19. J. E. Ramirez-Marquez and S. C. M. Rocco , Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery, Reliab. Eng. Syst. Saf. 94(5) (2008) 913–921. Crossref, Google Scholar
20. A. Carrigy, J. E. Ramirez-Marquez and C. M. Rocco , Multi-state stochastic network interdiction via reliability modeling and evolutionary optimization, J. Risk Reliab. 224(1) (2009) 27–42. Google Scholar
21. D. Bertsimas, E. Nasrabadi and J. B. Orlin , On the power of randomization in network interdiction, Oper. Res. Lett. 44(1) (2016) 114–120. Crossref, Google Scholar
22. M. He et al., A cooperative network interdiction model and its optimization solution algorithm, Int. J. Comput. Intell. Syst. 11 (2018) 560–572. Crossref, Google Scholar
23. A. Atamturk, C. Deck and H. Jeon , Successive quadratic upper-bounding for discrete mean-risk minimization and network interdiction, INFORMS J. Comput. 32(2) (2019) 346–355. Google Scholar
24. B. Liu , Uncertainty Theory, 2nd edn. (Springer, Berlin, 2007). Crossref, Google Scholar
25. B. Liu , Some research problems in uncertainty theory, J. Uncertain Syst. 3(1) (2009) 3–10. Google Scholar
26. B. Liu , Theory and Practice of Uncertain Programming, 2nd edn. (Springer, Berlin, 2009). Crossref, Google Scholar
27. B. Liu , Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty, 2nd edn. (Springer, Berlin, 2010). Crossref, Google Scholar
28. S. Han, Z. Peng and S. Wang , The maximum flow problem of uncertain network, Inf. Sci. 265 (2014) 167–175. Crossref, Google Scholar
29. S. Ding , The $α$ -maximum flow model with uncertain capacities, Appl. Math. Model. 39 (2015) 2056–2063. Crossref, Google Scholar
30. M. Soleimani-Alyar and A. Ghaffari-Hadigheh , Uncertain network interdiction problem, J. Uncertain Syst. 12(2) (2018) 141–150. Google Scholar
31. M. Soleimani-Alyar and A. Ghaffari-Hadigheh , Dynamic network interdiction problem with uncertain data, Int. J. Uncertainty Fuzziness Knowledge-Based Syst. 26(2) (2018) 327–342. Link, Google Scholar
32. B. Zhang, J. Peng and S. Li , Minimax models for capacitated p-center problem in uncertain environment, Fuzzy Optim. Dec. Making 20(3) (2021) 273–292. Crossref, Google Scholar
33. B. Zhang and J. Peng , Uncertain Graph and Network Optimization (Springer, Singapore, 2022). Crossref, Google Scholar
34. S. Bavandi and H. Bigdeli , A maximum flow network interdiction model in fuzzy stochastic hybrid uncertainty environments, Yugoslav J. Oper. Res. 33(3) (2023) 409–424, https://doi.org/10.2298/YJOR220415038B. Crossref, Google Scholar
35. B. Liu , Why is there a need for uncertainty theory? J. Uncertain Syst. 6(1) (2012) 3–10. Google Scholar
36. U. Pyakurel and S. Dempe , Network flow with intermediate storage: Models and lgorithms, in SN Operations Research Forum, Vol. 1 (Springer International Publishing, 2020), pp. 1–23. Crossref, Google Scholar
37. Y. P. Aneja, R. Chandrasekaran and K. P. K. Nair , Maximizing residual flow under an arc destruction, Networks Int. J. 38 (2001) 194–198. Google Scholar
38. E. Minieka , Maximal, lexicographic, and dynamic network flows, Oper. Res. 21 (1973) 517–527. Crossref, Google Scholar
39. D. P. Khanal, U. Pyakurel and T. N. Dhamala , Maximum multi-commodity flow with intermediate storage, Math. Probl. Eng. 2021 (2021) 5063207, https://doi.org/10.1155/2021/5063207. Crossref, Google Scholar
40. D. P. Khanal, U. Pyakurel, T. N. Dhamala and S. Dempe , Abstract temporally repeated flow with intermediate storage, The Nepali Math. Sci. Rep. 39(2) (2022) 67–78. Crossref, Google Scholar
41. U. Pyakurel, D. P. Khanal and T. N. Dhamala , Abstract network flow with intermediate storage for evacuation planning, Eur. J. Oper. Res. 305(3) (2023) 1178–1193, https://doi.org/10.1016/j.ejor.2022.06.054. Crossref, Google Scholar
42. T. N. Dhamala, M. C. Adhikari, D. P. Khanal and U. Pyakurel , Generalized maximum flow over time with intermediate storage, Ann. Oper. Res. 335 (2024) 111–134, https://doi.org/10.1007/s10479-023-05773-w. Crossref, Google Scholar