مسئله ممانعت از بیشینه جریان در شبکه های پویای چند دوره ای در محیط دو ترکیبی تصادفی فازی

نوع مقاله : مقاله صنایع

نویسندگان

1 پژوهشگر، پژوهشکده عالی جنگ، دانشگاه فرماندهی و ستاد آجا، تهران، ایران

2 گروه مطالعات عام و فناوری، دانشگاه فرماندهی و ستاد آجا

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

چکیده

بدون شک بهترین ابزار برای کمک به تصمیم‌گیرندگان و فرماندهان نظامی برای انتخاب یک راهبرد مناسب، فرمول‌بندی مدل‌هایی است که تا حد امکان به دنیای واقعی نزدیک باشند. این امر زمانی میسر می‌شود که این مسائل در شرایط عدم قطعیت ارائه شوند. در این پژوهش، یک مسئله ممانعت پویای چند دوره‌ای در شرایط عدم قطعیت دو ترکیبی تصادفی فازی موردبررسی قرار می‌گیرد. به‌طورکلی، در مسائل ممانعت شبکه، منابع کمیابی برای تنزل کارایی دشمن اختصاص داده می‌شود که رفتار او به‌وسیله مسئله بهینه‌سازی شبکه قالب‌بندی شده است. در این مسئله، ممانعت کننده یا همان نیرو‌های مدافع درصدد کمینه کردن بیشینه جریان در طول T دوره زمانی هستند. از طرفی، در هر مرحله ممانعت کننده و دشمن به‌طور کامل از عملکرد طرف مقابل آگاه هستند. ظرفیت‌های یالی در این مدل به‌صورت متغیرهای تصادفی فازی در نظر گرفته می‌شوند. برای حل مدل‌ ارائه‌شده، ابتدا مسئله ممانعت پویای تصادفی فازی به کمک مفاهیم نظریه احتمال،‌ اندازه اعتبار و برنامه‌ریزی محدودیت شانس به مسئله ممانعت پویای قطعی تبدیل می‌شود. سپس با استفاده از دوگان‌گیری مسئله دوسطحی قطعی ایجادشده به یک مسئله تک سطحی تبدیل و سپس با استفاده از تعمیم الگوریتم تجزیه بندرز برای حل آن اقدام می‌شود. درنهایت اعتبار مسئله با ارائه یک نمونه عددی مورد ارزیابی قرار می‌گیرد.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

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

نویسندگان [English]

  • Salim Bavandi 1
  • Hamid Bigdeli 2
  • Javad tayebi 3
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
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Network interdiction
  • Fuzzy random variable
  • Credibility measure
  • Probability measure
  • Benders decomposition
[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.‏