مجله تحقیق در عملیات در کاربردهای آن ( ریاضی کاربردی سابق )

مساله پوشش مجموعه، از دسته مسائل سخت محسوب می‌شود که در کاربردهای مختلفی مانند سیستم اورژانس، مکانیابی تسهیلات خرده‌فروشی، بیمارستان‌ها، واحدهای دفاعی کشوری، پایگاه‌های نظامی، دستگاه‌های رادار و ... مورد استفاده قرار می‌گیرد. هدف از پوشش مجموعه، یافتن یک زیرمجموعه به گونه‌ایست که اجتماع اعضای این زیر مجموعه، کل مجموعه را پوشش دهد. در این مقاله یک الگوریتم ابتکاری برای حل مساله پوشش مجموعه پیشنهاد شده است. در الگوریتم پیشنهادی، برای هر یک از رئوس گراف، یک مقدار منسوب به میزان بهبود محاسبه می‌شود که بر اساس آن تصمیم برحضور یا عدم حضور راس متناظر در مجموعه پوشش گرفته می‌شود. با توجه به تخصیص تسهیل و اثر متقابل بر پوشش یا عدم پوشش رئوس مجاور، در هر مرحله مقادیر بهبود به روز می‌شود و این روند به طور تکراری ادامه می­یابد تا آنکه در خاتمه‌ی الگوریتم، مجموعه پوشش نزدیک به بهینه بدست آید. جهت ارزیابی الگوریتم پیشنهادی در مقایسه با سایر روش‌های متداول، یک الگوریتم شبیه‌سازی تبرید جهت حل ارائه شد و پارامترهای آن به روش تاگوچی تنظیم گردید. نتایج بدست آمده در مقایسه با نتایج بدست آمده از الگوریتم شبیه‌سازی تبریدی برای آزمایش‌های مختلف حاکی از موفقیت الگوریتم پیشنهادی به ویژه در مسائل با ابعاد بالا در مهار رشد زمان حل از O(2ⁿ) به زمان حل چند جمله­ای O(2n) است.