مقدمه

:بدون شک مسئله فروشنده دوره گرد یکی از معروفترین مسائلی است که در زمینه هوش مصـنوعی مطـرح اسـت. مسئله فروشنده دوره گرد یک مسئله بهینه سازي گسسته کلاسیک است که جزء مسائل NP-Hard می باشـد و تـا کنـون راه حل دقیقی براي حل آن ارائه نشده است. مساله فروشنده دوره گرد چیست ؟در این مسئله هـدف یـافتن یـک دور همیلتـونی بـا کمترین هزینه در گراف شهر هاي مورد نظر است .[1] در این مسئله فروشنده دوره گردي قصد رفتن به تعـدادي شـهر را دارد که فاصله بین شهرها ثابت بوده و می بایست هر شهر فقط یک بار بازدید شود و فروشنده دوره گرد به شهر اولیه باز گردد، هدف در این مساله یافتن کوتاهترین مسیر ممکن است. به این مسیر تور (Tour)گفته می شود.

این مسئله ابتدا در دهه 1800 توسط ویلیام همیلتون ایرلندي و توماس کرکمن بریتانیایی مطرح شد و سال ها بعد در دهه 1930 شکل عمومی آن بوسیله کارل منگر از گروه ریاضی دانشگاه هاروارد و هاسلر ویتنی از دانشـگاه پرینسـتون مـورد مطالعـه قـرار گرفت.[1] این مسئله در عین سادگی کاربردهاي فراوانی دارد که برخی از آنها عبارتست از: زمان بنـدي وسـیله نقلیـه[2] بهینـه کردن مسیر حرکت جهت انتقال کالا به نقاط مختلف، بهینه کردن مسیر حرکت جهت محموله هاي پستی، مسیر یابی خـودرو [3]و کمینه کردن مسیر حرکت یک تور مسافرتی..

 -مبانی نظري و پیشینه پژوهش

تا کنون روش ها و الگوریتم هاي مختلفی براي حل مسئله فروشنده دوره گرد مطرح شده است که هر کدام نقاط ضعف و قوت خود را دارند اما آنچه که حائز اهمیت است استفاده از روش و یا الگوریتمی است که در کمترین زمان ممکن بهترین تور را پیدا نماید. برخی از این الگوریتم هاي فراابتکاري بکار رفته جهت حل مسئله فروشنده دوره گرد، عباتند از :الگوریتم ژنتیک([4](GA، ازدحام ذرات([5](PSO، کلونی مورچگان([6](ACO،الگوریتم ممتیک([7] (Memeticو....که در هر یک از این الگوریتم ها می توان با تغییر پارامترها و بکار بردن تکنیک هایی به نتایج مطلوبتري دست پیدا کرد. سارانیا و وجاینتاي، در سال 2014 یک روش براي حل مشکل فروشنده دوره گرد، بر پایه جستجوي ممنوع و الگوریتم هاي زیستی شامل الگوریتم بهینه سازي مورچگان، الگوریتم فاخته و الگوریتم زنبور عسل ارائه کرده اند.[8] یانگ و همکاران، در سال 2012 یک رویکرد بهینه سازي براي کاهش هزینه هاي پردازش مرتبط با مسیریابی مورچه ها در ACO مرسوم مطرح کرده، و با استفاده از استراتژي تنوع فردي، ACO را بهبود دادند.[9] بطوري که سرعت و همگرایی ACO تا حد زیادي افزایش یافت. آنها این رویکرد را در حل مسئله فروشنده دوره گرد بکار بردند. ریزك االله و همکاران، در سال 2013 یک الگوریتم ترکیبی به نام ACO-FA، که الگوریتم مورچگان (ACO) را با الگوریتم کرم شب تاب (FA) براي حل مسائل نامحدود ادغام میکند، ارائه داده اند.[10] لاس زولوکوتا [11] الگوریتم کرم شبتاب را براي حل مساله فروشنده دوره گرد چند گانه به کار برد.دراین مقاله ما از یک روش جدید براي حل مساله فرمشنده دوره گرد با الگوریتم کرم شبتاب استفاده نمودیم.