ارائه یک الگوریتم ابتکاری جدید برای حل مساله مکان‌یابی پوشش کلی

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