یک روش حل فرا ابتکاری برای مسئله ممانعت از بیشینه ظرفیت با چندین مهاجم
نویسندگان
1 Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran
2 پژوهشکده عالی جنگ، دانشگاه فرماندهی و ستاد آجا
3 پژوهشگر پژوهشکده عالی جنگ، دانشگاه فرماندهی و ستاد آجا
doi
10.22075/jme.2022.26026.2213چکیده
مسائل ممانعت در شبکه، دستهای از مسائل هستند که دو بازیگر با اهداف متضاد به تقابل با یکدیگر میپردازند و به صورت کلی منفعت یک بازیگر موجب متضرر شدن بازیگر دیگر میشود. در مسئله ممانعت از بیشینه ظرفیت، یک مدافع در نقش رهبر اقدامات ممانعتی خود را با توجه به بودجه موجود بر روی یالهای یک شبکه اعمال میکند. در سطح بعدی، تعدادی مهاجم به عنوان پیرو و با مشاهده اقدامات ممانعتی مدافع، مسئله بیشینهسازی ظرفیت مسیر را از مبدأ به مقصد بهینهسازی مینمایند. ممانعت در واقع حمله به کمانهای شبکه و تخریب آنها، با هدف کاهش ظرفیت عبوری کمان میباشد. در این پژوهش در ابتدا یک مدل برنامهریزی ریاضی دو سطحی صفر و یک برای مسئله مورد نظر بیان شده است. سپس با توجه به پیچیدگی حل مسائل دو سطحی، یک الگوریتم ترکیبی شامل الگوریتم دایکسترا اصلاح شده و الگوریتم شبیهسازی تبرید برای حل مسئله پیشنهاد شده است. الگوریتم دایکسترا اصلاح شده همواره جواب بهینه مسئله بیشینه ظرفیت را ارائه میدهد که سبب تولید جوابهای مطلوب در الگوریتم ترکیبی میگردد. سپس کارایی الگوریتم پیشنهادی تا ابعاد 100 گره و 150 کمان مورد بررسی قرار گرفت که نشان دهنده توانایی الگوریتم برای حل مسائل در ابعاد مختلف میباشد. بر اساس نتایج حاصل شده، افزایش بودجه مدافع تا میزان مشخصی بر بهبود تابع هدف مسئله تأثیرگذار میباشد. همچنین مقدار ضریب اهمیت مهاجمان در مسئله، ارتباط معکوس با کیفیت مسیر مهاجمان دارد و موجب افزایش یا کاهش بیشینه ظرفیت مسیر مهاجمان میگردد.
