Abstract

Travelling salesman problem is one of the most important problems in graphs theory which is considered as NP-hard problems. The important of this problem is due to the fact that it is used in many fields such as transportation, logistics, semiconductor industry, problem of routing, scan chain optimization and drilling problem in integrated orbit test, production and many others scientific and industrial fields. Till now various methods that have been used to solve this problem have their own advantage and disadvantage and problems, become clearer when the problem become harder. Therefore, travelling salesman problem remain as an open problem in research field of computer science. This paper tried to solve the above problem with an optimization algorithm with less complexity in order to solve this problem with firefly algorithm with greedy approach and it was compare and examined with other standard algorithm. The results show the superiority of proposed algorithm compared to the other used algorithm

چکیده

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

1-مقدمه

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