مسئله فروشنده دوره گرد (Travelling salesman problem):
تعریف: در این مسئله تعدادی شهر داریم، به طوری که هزینه مسیر بین شهرها مشخص است، ما می‌خواهیم کم هزینه‌ترین مسیر را به گونه‌ای پیدا کنیم که فروشنده از یک شهر شروع کند و از تمامی شهرها دقیقا یک بار عبور کرده و به شهر ابتدایی بازگردد.
برای مثال شکل زیر را در نظر بگیرید. می‌خواهیم کوتاه‌ترین مسیر را با شروع از یک شهر دلخواه و بازگشت به آن پیدا کنیم.
و ماتریس فاصله بین شهرها به صورت ماتریس زیر خواهد بود.این فاصله از طریق محاسبه فاصله اقلیدسی بین دو شهر مورد نظر محاسبه شده است. همان‌طور که می‌بینید ماتریس حاصل یک ماتریس متقارن می‌باشد. که حاصل آن TSP متقارن می‌باشد، به این معنا که مسیر رفت و برگشت با یکدیگر برابر می‌باشند.
یکی از راه حل های موجود بر اساس مدار همیلتونی برابر خواهند بود با:
(تعریف مدار همیلتونی: مداری است که هر راس را دقیقاً یک بار مشاهده می‌کند.(به جز راسی که هم به عنوان آغاز و هم پایان می‌باشد. در نتیجه این راس دو بار دیده می‌شود.))
که هرکدام از راه حل‌های موجود برابر یک جایگشت می‌باشد.اینکه بخواهیم تمامی جایگشت‌های ممکن را نوشته و از میان آن کوچک‌ترین را پیدا کنیم, حتی برای تعداد کم شهرها نامناسب خواهد بود.
تعداد جواب‌های این مسئله برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n راس، یعنی برابر است با (n-1)! که n برابر با تعداد شهرها می‌باشد.(توجه شود در این گراف گره‌ها شهرها و یال‌ها نشان دهنده مسیر بین شهرها می‌باشد). و پیچیدگی زمانی آن (!o(n می‌باشد که حتی برای تعداد شهرهای کم نیز نامناسب خواهد بود.
به همین علت برای به دست آوردن جواب بهینه در این مسئله روش‌های متعددی ایجاد شده است:
الف) نمایش جواب به‌صورت رشته گسسته جایگشتی که در الگوریتم‌های زیر قابل استفاده است: الگوریتم‌های ژنتیک، شبیه سازی تبرید، جستجوی ممنوعه، جستجوی همسایگی متغیر، بهینه‌سازی کلونی مورچگان، جستجوی هارمونی و سایر الگوریتم‌های بهینه‌سازی گسسته
ب) نمایش جواب به‌صورت کلیدهای تصادفی که در الگوریتم‌های زیر قابل استفاده است: الگوریتم‌های ژنتیک، بهینه سازی ازدحام ذرات، الگوریتم رقابت استعماری، تکامل تفاضلی، بهینه‌سازی مبتنی بر جغرافیای زیستی، استراتژی‌های تکاملی، برنامه‌ریزی تکاملی و سایر الگوریتم‌های بهینه سازی پیوسته
پ) نمایش جواب به‌شکل ماتریس‌های شبیه فرومون که توسط تمامی الگوریتم های اشاره شده در مورد (ب) قابل استفاده می‌باشد.
در اینجا ابتدا راه حل‌های این مسئله بر اساس الگوریتم ژنتیک و سپس شبیه سازی تبرید را خواهیم دید:
نتیجه حاصل از اجرای الگوریتم ژنتیک بر روی ده شهر ابتدایی در محیط متلب:
نتیجه حاصل از اعمال الگوریتم شبیه سازی تبرید بر روی ده شهر در برنامه نویسی متلب:
نتایج حاصل از اجرای الگوریتم ژنتیک و شبیه سازی تبرید (به ترتیب) برای ۲۰شهر:
فروشنده دوره گرد احتمالی (probabilistic travelling sales man):
مساله فروشنده دوره گرد احتمالی اولین بار توسط Jaillet ارائه شده است. که در هر نمونه از مسئله تنها مجموعه‌ای از شهرها حضور دارند.
همان مسئله فروشنده دوره گرد معمولی بوده است در حالی که تعداد گره ها (شهرها) یی که در هر تور ملاقات می‌کند، زیر مجموعه‌ای از تور اولیه می‌باشد. در واقع به این معنی است که تعداد شهرها در هر زمان یک متغیر تصادفی محسوب می‌شود.
و هدف این مساله این است که اولا تور اولیه با کمترین طول را پیدا کرده و ثانیا اگر هر زیر مجموعه تصادفی از شهرها، با همان ترتیبی که در تور اولیه ظاهر شده‌اند، بازدید شود، کمترین طول را داشته باشد.
مهم‌ترین تفاوت PTSP با TSP در این است که در مسئله فروشنده دوره گرد احتمالی، احتمال ملاقات هر گره بین صفر و یک می‌باشد در حالی که در مسئله فروشنده دوره گرد معمولی احتمال ملاقات هر گره، یک می‌باشد. در یک نمونه داده شده از مسئله، گره‌های موجود باید بر اساس ترتیب تور اولیه ملاقات بشوند، در حالی که از سایر گره‌ها می‌توان به راحتی صرفه نظر نمود.
ثبت ديدگاه