Maximum Flow Interdiction Problem in Multi-Period Dynamic Networks in Fuzzy Stochastic Hybrid Conditions

Document Type : Industry Article

Authors

1 Researcher, Institute for the study of war, AJA Command and Staff University, Tehran, Iran.

2 Department of Science and Technology Studies, Command and Staff University

3 Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran

Abstract

Undoubtedly, the best tool to help military decision-makers and commanders choose the appropriate strategy is to formulate models that are as close to the real world as possible. This is possible when these problems are presented in conditions of uncertainty. In this research, a multi-period dynamic interdiction problem in fuzzy stochastic conditions is investigated. In general, interdiction problem, scarce resources are allocated to degrade the enemy, whose behavior is formatted by the network optimization problem. In this problem, the defense forces in the role of interdictor try to minimize the maximum flow during the period so that at each stage the interdictor and the enemy are fully aware of the performance of the other side. Edge capacities in this model are considered as fuzzy stochastic variables. To solve the proposed model, first, the fuzzy stochastic dynamic interdiction problem is transformed into the deterministic dynamic interdiction problem with the help of the concepts of probability measure, credibility measure and chance constraint programming. Then, by creating the crisp two-level problem created by duality, it is transformed into a single-level problem, and then it is solved by using the generalization of Banders decomposition algorithm. Finally, the validity of the problem is evaluated by providing a numerical sample.

Keywords

Main Subjects

References

[1] L. Bingol, A Lagrangian Heuristic for Solving Network Interdiction Problem. NAVAL POSTGRADUATE SCHOOL MONTEREY CA, 2001.
[2] R. Wollmer, "Removing Arcs from a Network". Operations Research, Vol.12, December 1964, pp. 934-940.
[3] C. A. Phillips, The network inhibition problem. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, 1993.
[4] J. Salmeron, K. Wood and R. Baldick, "Analysis of electric grid security under terrorist threat". IEEE Transactions on Power Systems, Vol.19, May 2004, pp. 905-912.
[5] N. Assimakopoulos, "A network interdiction model for hospital infection control". Computers in Biology and Medicine, Vol.17, 1987, pp. 413-422.
[6] A. Gutfraind, New Models of Interdiction in Networked Systems on JSTOR. Military Operations Research Society, 2010.
[7] R.A. Collado, and D. Papp, Network interdiction–models, applications, unexplored directions. Rutcor Res Rep, RRR4, Rutgers University, New Brunswick, NJ, 2012.
[8] A. Abdolahzadeh, M. Aman, and J. Tayyebi, "Minimum st-cut interdiction problem". Computers and Industrial Engineering, Vol.148, October 2020, pp. 106708.
[9] حمید بیگدلی، مهدی کبیری و جواد طیبی، "کاربرد مسئله بازی ممانعت شبکه دونفره در شناسایی دشمن"، آینده‌پژوهی دفاعی، دوره 6، شماره 21، تابستان 1400، صفحه 69-83.
[10] حمید بیگدلی، سید محمد صادق میردامادی و جواد طیبی، "یک روش حل فرا ابتکاری برای مسئله ممانعت از بیشینه ظرفیت با چندین مهاجم"، مدل سازی در مهندسی، دوره 20، شماره 70، پاییز 1401، صفحه 133-146.
[11] K. Xiao, C. Zhu, W. Zhang, and X. Wei, "The Bi-Objective Shortest Path Network Interdiction Problem: Subgraph Algorithm and Saturation Property". IEEE Access, Vol.8, July 2020, pp, 146535–146547.
[12] A. Forghani, F. Dehghanian, M. Salari, and Y. Ghiami, "A bi-level model and solution methods for partial interdiction problem on capacitated hierarchical facilities". Computers and Operations Research, Vol.114, February 2020, pp. 104831.
[13] مهدی کبیری و جواد طیبی، "کاربرد مسأله ممانعت از حداکثر جریان در بازی جنگ زمینی". فصلنامه بازی جنگ، دوره 3، شماره 6، تابستان 1399، صفحه 30-53.
[14] B. J. Lunday, and H. D. Sherali, "A dynamic network interdiction problem". Informatica, Vol.21, July 2010, pp. 553-574.
[15] C. Lim, and J. C. Smith, "Algorithms for discrete and continuous multicommodity flow network interdiction problems". IIE Transactions (Institute of Industrial Engineers), Vol.39, April 2007, pp. 15-26.
[16] M. Afshari Rad, and H. T. Kakhki, "Maximum dynamic network flow interdiction problem: New formulation and solution procedures". Computers and Industrial Engineering, Vol.65,  August 2013, pp. 531-536.
[17] M. Soleimani-Alyar, M. and A. Ghaffari-Hadigheh, "Dynamic Network Interdiction Problem with Uncertain Data". International Journal of Uncertainty, Fuzziness and Knowlege-Based Systems, Vol.26, 2018, pp. 327-342.
[18] D.B. Liu, Uncertainty Theory. Uncertainty Theory, 2007.
[19] حمید بیگدلی و سلیم باوندی، "تصمیم‌گیری بهینه در مواجهه با عملیات‌های تخریبی دشمن با استفاده از مسئله ممانعت از بیشینه جریان در شبکه‌های پویای چند دوره‌ای در شرایط فازی". آینده‌پژوهی دفاعی، دوره 7، شماره 24، بهار 1401، صفحه 61-79.
[20] مهسا زارعی، مهدی نصراللهی و امیر یوسفلی، "توسعه شبکه زنجیره تامین سبز حلقه بسته در فضای غیرقطعی". مدل سازی در مهندسی، دوره 20، شماره 68, صفحه 165-187.
[21] مجتبی رادمهر و حسن زرآبادی پور، "کنترل مد لغزشی فازی برای ردیابی پروفایل بهینه سرعت قطار با وجود نامعینی". مدل‌سازی در مهندسی، دوره 20، شماره 68، فروردین 1401، صفحه 139-152.
[22] H. Kwakernaak, "Fuzzy random variables—I. Definitions and theorems". Information Sciences, Vol.15, July 1978, pp. 1–29.
[23] T.G. Crainic, A. Frangioni, and B. Gendron, "Bundle-based relaxation methods for multicommodity capacitated fixed charge network design". Discrete Applied Mathematics, Vol.112, September 2001, pp. 73-99.
[24] B. Liu, and Y.K. Liu, "Expected value of fuzzy variable and fuzzy expected value models". IEEE Transactions on Fuzzy Systems, Vol.10, August 2002, pp. 445-450.
[25] X. Li, and B. Liu, "A Sufficient and necessary condition for credibility measures". International Journal of Uncertainty, Fuzziness and Knowlege-Based Systems, Vol.14, 2006, pp. 527-535.
[26] B. Liu, "A survey of credibility theory". In Fuzzy Optimization and Decision Making, Vol.5, October 2006, pp. 387-408.
[27] Y.-K. Liu, and J. Gao, "The independence of fuzzy variables with applications to fuzzy random optimization". International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, Vol.15, 2007, pp. 1-20.
[28] D. Dubois, and H.M. Prade, Fuzzy sets and systems : theory and applications. Academic press, 1980.
[29] Y.-K. Liu, and B. Liu, "Fuzzy random variables: A scalar expected value operator". Fuzzy Optimization and Decision Making, Vol.2, June 2003, pp. 143–160.
[30] S. Wang, and J. Watada, Fuzzy Random Variable. In Fuzzy Stochastic Optimization. Springer, Boston, MA, 2012.‏
[31] Y.-K. Liu, and B. Liu, "On minimum-risk problems in fuzzy random decision systems". Computers and Operations Research, Vol. 32, February 2005, pp. 257–283.
[32] M.S. Bazaraa, J.J. Jarvis, and H.D. Sherali, Linear programming and network flows. John Wiley & Sons, 2011.‏
 
Journal of Modeling in Engineering
Volume 21, Issue 72
March 2023
Pages 221-233

Files

History

  • Receive Date: 13 October 2022
  • Revise Date: 08 January 2023
  • Accept Date: 16 January 2023

Share

How to cite

Statistics