یک الگوریتم ترکیبی کارآمد بهبودیافته برای مسئله‌ی سفر چند فروشنده در مقیاس بزرگ

Abstract

مسئله‌ی چندین فروشنده‌ی دوره‌گرد )M‌T‌S‌P( گسترشی مشهور از مسئله‌ی فروشنده‌ی دوره‌گرد (T‌S‌P) است. تحقیقات این مسئله بر خلاف مسئله‌ی T‌S‌P که گستردگی آن توجه زیادی را به خود معطوف کرده است، بسیار محدودبوده و ازاین رو الگوریتم جدید ترکیبی موجود به نام الگوریتم ژنتیک ـ مورچگان بهبودیافته )I‌A‌C-P‌G‌A( ارائه شده است که در آن از یک روش جستجوی محلی به منظور بهبود الگوریتم بهره گرفته شده است. ایده‌ی اصلی این مقاله آن است که از الگوریتم ژنتیک برای تعیین تعداد شهرها و نقطه‌ی شروع هر فروشنده بهره بگیریم و سپس از الگوریتم مورچگان برای تعیین بهترین تور استفاده کنیم. نتایج حاصل از مقایسه‌ی نتایج الگوریتم با دیگر الگوریتم‌های موجود در ادبیات موضوع و تجزیه و تحلیل آن نشان می‌دهد که الگوریتم پیشنهادی در حل M‌T‌S‌P در مقیاس بزرگ مؤثر است.

Keywords

• الگوریتم ژنتیکی پارتنو
• الگوریتم کلونی مورچه‌ها
• مسئله‌ی فروشنده‌ی دوره‌گرد چندگانه همراه با الگوریتم ترکیبی بهبودیافته
• روش جستجوی محلی -o‌p‌t۲