حفاظت از خطوط ارتباطی در برابر عملیات تخریبی با استفاده از ممانعت برش کمینه پویا

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری، گروه ریاضی، دانشگاه بیرجند

2 گروه ریاضی، دانشکده علوم ریاضی و آمار، دانشکاه بیرجند، بیرجند، ایران

3 استادیار گروه مهندسی صنایع و علوم مهندسی، دانشگاه صنعتی بیرجند

چکیده

یکی از اهداف عمده دشمن در جنگ‌های زمینی رصد کردن شبکه‌های ارتباطی و قطع خطوط جابه‌جایی نیرو و تجهیزات می‌باشد. رویکرد بهینه برای این منظور قطع خطوط واقع بر یک برش کمینه است. دشمن این کار را معمولاً با حملات هوایی، موشکی یا توپخانه و همچنین تخریب پل‌ها و جاده‌ها انجام می‌دهد. از طرفی نیروهای مدافع می‌خواهند از منابع و امکانات موجود، حداکثر استفاده را کرده و مانع رسیدن دشمن به هدفش شوند. در این مقاله این مسأله را از دید نیروهای مدافع در قالب یک مسأله ممانعت شبکه دوسطحی فرمول‌بندی می‌کنیم. این مسأله را مسأله ممانعت از برش کمینه پویا می‌نامیم. با توجه به پیچیدگی ذاتی و ماهیت مسأله، آن را به کمک رویکرد تجزیه بندرز حل نموده و در نهایت اعتبار مسأله را به کمک یک نمونه کاربردی مورد ارزیابی قرار می‌دهیم.

کلیدواژه‌ها

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

Communication Line Protection Against Sabotages Using Dynamic Minimum Cut Interdiction

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

  • Abolfazl Abdolahzadeh 1
  • Massoud Aman 2
  • javad tayyebi 3
1 Department of Mathematics, Faculty of Science, University of Birjand, Iran
2 Department of Mathematics, Faculty of Mathematics and Statistics, University of Birjand, Birjand, Iran
3 Department of Industrial Engineering, Birjand University of Technology, Birjand, Ira
چکیده [English]

In ground wars, one of the enemy's main goals is to monitor communication networks and to interrupt the force and equipment lines. For this purpose, the optimal approach is to disconnect routes on a minimum cut. This is possible by air, missile, and artillery attacks, as well as the destruction of bridges and roads. On the other hand, the defense forces seek to exploit maximally the available resources and facilities to interdict the enemy reaching this goal. In this paper, we model this problem from the viewpoint of defense forces in the form of a bi-level network interdiction problem. Due to the inherent complexity and nature of the problem, we solve it using the Bender's decomposition approach. Finally, we establish the validity of the model by a practical example.

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

  • Communication Lines
  • Sabotages
  • Network Interdiction
  • Minimum Cut
  • Bender’s Decomposition

مراجع

  1. Bigdeli, H.; Tayyebi, J.; Partovi, M. “War Game and Mathematical Models”; First Edition, Dafous Publications (In Persian).##
  2. Afshari Rad, M. “Maximum Flow Interdiction Problem In Network: New Solutions and Generalization to Dynamic Networks”; Doctoral Dissertation, Faculty of Mathematical Sciences, Ferdowsi University, 2012, (In Persian).##
  3. Steinrauf, R. L. “Network Interdiction Model, Master Thesis”, Monterey, California, 1991.##
  4. Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B. “Network Flows, Theory, Algorithms, and Applications”; 1st Prentice Hall, New Jersey, 1993.##
  5. Ford, L. R.; Fulkerson, D. R. “Flows in Networks”; Princeton University Press, New Jersey, 1962.##
  6. Bracken, J.; McGill, J. T. “Mathematical Programs with Optimization Problems in the Constraints”; Oper. Res.
    1973, 21, 37-44.##
  7. Candler, W.; Norton, R. “Multi-level Programming and Development Policy”; The World Bank, 1977.##
  8. Bard, J. “Practical Bi-level Optimization:  Algorithms and Applications”; Kluwer Academic Publishers, USA, 1998.##
  9. Wollmer, R. D. “Removing arcs from a Network”; J. Oper. Res. 1964, 12, 934-940.##
  10. McMastres, A.W.; Mustin, T. M. “Optimal Interdiction of a Supply Network”; Nav. Res. Log. Quar. 1970,
    17(3), 261-268.##
  11. Wood, R. K. “Deterministic Network Interdiction Problem”; Math. Comput. Modell. 1993, 17, 1-18.##
  12. Kennedy, K. T.; Deckro, R. F.; Moore, J. T.; Hopkinson, K. M. “Nodal Interdiction”; Math. Comput. Model 2011, 54
    (11-12), 3116–3125.##
  13. Lunday, B. J.; Sherali, H. D. “A Dynamic Network Interdiction Problem”; Inf. 2010, 21, 553-574.##‏
  14. Rad, M. A.; Kakhki, H. T. “Maximum Dynamic Network Flow Interdiction Problem: New Formulation and Solution Procedures”; Comput. Ind. Eng. 2013, 65, 531-536.##
  15. Ratliff, H. D.; Sicilia, G. T.; Lubore, S. H. “ Finding the Most Vital Links in Flow Networks”; Manage. Sci. 1975, 21, 531-539.##
  16. Akgün, İ.; Tansel, B. Ç.; Wood, R. K. “The Multi-Terminal Maximum-Flow Network-Interdiction Problem”; Eur. J. Oper. Res. 2011, 211, 241–251.##
  17. Lim, C.; Smith, J. C. “Algorithms for Discrete and Continuous Multicommodity Flow Network Interdiction Problems”; IIE Trans. 2007, 39, 15-26.##
  18. Mohammadi, A.; Tayyebi, J. “Maximum Capacity Path Interdiction Problem with Fixed Costs”; Asia-Pac. J. Oper. Res. 2019, 36, 1950018.##
  19. Ramirez-marquez, E.; Daniel, E.; Salazar, A.; Claudio, M.; Rocco, S. “Bi and Tri Objective Optimization in the Deterministic Network Interdiction Problem”; Rel. Eng. Syst. Saf. 2010, 95, 887–96.##
  20. Chen, Y.; Cheng, G.; Shenghan, Yu. “Bi-Objective Optimization Models for Network Interdiction”; RAIRO Oper. Res. 2019, 53, 461–472.##
  21. Lim, C.; Smith, J. “Algorithms for Discrete and Continuous Multicommodity Flow Network Interdiction Problems”; IIE Trans. 2007, 39,15–26.##
  22. Smith, J. C.; Yongjia, S. “A Survey of Network Interdiction Models and Algorithms”; Eur. J. Oper. Res. 2020, 283, 797-811.##
  23. Bigdeli, H.; Hassanpour, H.; Tayyebi, J. “The Optimistic and Pessimistic Solutions of Single and Multiobjective Matrix Games with Fuzzy Payoffs and Analysis of some of Military Problems”; Adv. Defence Sci. & Technol. 2016, 2, 133-145 (In Persian).##
  24. Bigdeli, H. “Quadratic Programming Method for Choosing Optimal Decision in Fuzzy and Complex Environment of Battle Scenario”; Adv. Defence Sci. & Technol. 2020, 11, 238-231.##
  25. Ben-Ayed, O.; Boyce, D. E.; Blair, C. E. “A General Bilevel Linear Programming Formulation of the Network Design Problem”; Trans. Res. Part B 1988, 22, 311-318.##
  26. Washburn, A. R. “Two-Person Zero-Sum Games”; Springer Edition 4, 2014.##

فایل ها

سابقه مقاله

  • تاریخ دریافت: 28 مرداد 1399
  • تاریخ بازنگری: 01 دی 1399
  • تاریخ پذیرش: 09 دی 1399
  • تاریخ انتشار: 01 مرداد 1400

هم رسانی

ارجاع به این مقاله

آمار