استفاده از تبدیل فضا برای حل مسئله فروشنده دوره‌گرد با معیار فاصله جغرافیایی

Abstract

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