مسئله فروشنده دوره گرد Travelling Salesman Problem – روش های حل مسئله فروشنده دوره گرد
مسئله فروشنده دورهگرد یا Traveling Salesman Problem به اختصار TSP یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر است. مسئله به این صورت است که تعدادی شهر داریم و هزینه رفتن مستقیم از هر یک از شهرها به دیگری را میدانیم حال باید فروشنده دوره گرد به همه این شهرها برود و کالا یا محصولات خود را به فروش برساند و دوباره به شهر اول برگردد. بالطبع مسیری که این فروشنده طی می کند باید کم هزینه باشد پس بنابراین از بین مسافت های موجود باید مسیری طی شود که دارای کم ترین مسافت بوده و دقیقاً یک بار از هر شهر عبور شود.
تاریخچه پیدایش مسئله فروشنده دورهگرد
مسئله فروشنده دورهگرد مسئلهای مشهور است ولی ریشه پیدایش اولیه مسئله فروشنده دوره گرد واضح و مشخص نیست. از 1832 در کتاب های خطی، این مسئله را با عنوان تورهای نمونه در آلمان و سوئیس برای فروشندگان دوره گرد مطرح کرده اند و در آنها از دیدگاه ریاضی به این مسئله پرداخته نشده است. اولین بار مسئله فروشنده دوره گرد به صورت یک مسئله ریاضی توسط ریاضیدان ایرلندی ویلیام همیلتون W.R. Hamilton و ریاضیدان بریتانیایی توماس کرکمن Thomas Penyngton Kirkman تدوین شد.
به نظر می رسد ایده اصلی طراحی مسئله فروشنده دوره گرد از بازی نمادین همیلتون icosian نشأت گرفته شده است. هدف بازی پیدا کردن یک چرخه همیلتونی در امتداد لبه های یک 12 وجهی است به طوری که از هر راس یک بار بازدید می شود و نقطه پایان آن همان نقطه شروع است. شکل کامل تر مسئله TSP برای اولین بار توسط ریاضیدانان در دهه 1930 در دانشگاه وین و هاروارد مورد مطالعه قرار گرفته است، به ویژه توسط کارل منگر Karl Menger که طرح مسئله فروشنده دوره گرد را مشخص کرد. کارل برای حل مشکل پستچی ها برای توزیع نامه ها فکر کرد و این مسئله را به شکل ریاضی و تعداد جایگشت های مسئله و حل آن مطرح کرد.
در دهه 1930 مریل فلوید Merrill M. Flood که به دنبال حل مشکل مسیریابی اتوبوس مدرسه بود، حل مسئله فروشنده دوره گرد مورد توجه اش قرار گرفت. هسلر ویتنی Hassler Whitney در دانشگاه پرینستون علاقه ای به این مسئله ایجاد کرد، که او آن را مسئله 48 ایالت یا 48states problem نامید. اولین نشریه ای که از عبارت مسئله فروشنده دوره گرد استفاده کرد گزارش RAND Corporation 1949 توسط جولیا رابینسون بود. در دهه های 1950 و 1960، این مسئله پس از آنکه شرکت RAND در سانتا مونیکا برای مراحل حل مسئله جوایزی را اهدا کرد، در محافل علمی اروپا و ایالات متحده رواج بیشتری یافت.
در سال 1959، جیلیان بردوود، J.H. هالتون و جان هامرسلی مقاله ای تحت عنوان “کوتاهترین مسیر از طریق بسیاری از نقاط” در مجله انجمن فلسفی کمبریج منتشر کردند. در دهه های بعد، این مسئله توسط بسیاری از محققان ریاضی، علوم کامپیوتر، شیمی، فیزیک و سایر علوم مورد مطالعه قرار گرفت. با این حال، در دهه 1960، رویکرد جدیدی ایجاد شد، که به جای جستجوی راه حل های بهینه، راه حلی را تولید می کرد که طول آن به طور اثبات شده با مضرب طول مطلوب محدود می شد و با این کار مرزهای پایین تری برای مسئله ایجاد می کرد. سپس از این محدوده های پایینی با رویکردهای شاخه و حد استفاده می شد.
در سال 1976، کریستوفیدس و سردیوکوف مستقل از یکدیگر پیشرفت بزرگی در این راستا انجام دادند الگوریتم کریستوفیدس-سردیوکوف راه حلی را ارائه می داد که در بدترین حالت حداکثر 1.5 برابر طولانی تر از راه حل بهینه است. از آنجا که این الگوریتم ساده و سریع بود، بسیاری امیدوار بودند که جای خود را به روش حل تقریباً مطلوب بدهد. با این حال، این امید به بهبود، فوراً محقق نشد و کریستوفیدس-سردیوکوف تا سال 2011، زمانی که الگوریتم تقریبی (بسیار) کمی بهبود یافته بود، بهترین روش برای بدترین سناریو بود.
تشریح مسئله فروشنده دوره گرد به عنوان مسئله گراف
مسئله TSP را می توان به عنوان یک گراف وزن دار بدون جهت مدل کرد، به طوری که شهرها رأس های گراف هستند و مسیرها لبه های آن هستند و فاصله یک مسیر وزن لبه است. در این گراف مسئله، به حداقل رساندن شروع و پایان در یک رأس مشخص پس از بازدید دقیق از یک رأس است. اغلب مدل، یک گراف کامل است (یعنی هر جفت رأس با یک لبه یا یال به هم متصل می شوند). در واقع هدف از حل مسئله فروشنده دوره گرد از دیدگاه یک مسئله گراف می خواهیم در یک گراف وزن دار یک سیکل بهینه یا تور همیلتونی را بیابیم به شرطی که جمع وزن یال ها یا لبه ها مینیمم باشد.
همانطور که در شکل بالا مشاهده می شود در سمت چپ گراف کامل وزن دار داریم یعنی از تمامی گره ها به گره های دیگر یال وجود دارد اگر بخواهیم یک تور بهینه همیلتونی بدست بیاوریم یعنی مجموع وزن یال ها مینیمم شود به صورت گراف سمت راست می توان یال هایی را انتخاب کرد که مجموع وزن کمتری داشته باشد یا به عبارت دیگر با تعمیم به مسئله فروشنده دوره گرد مسافت طی شده کمتری را داشته باشد. اکنون اگر از هر شهر در این گراف شروع به حرکت کنید این مسیر مسیر بهینه خواهد بود.
روش های حل مسئله فروشنده دوره گرد
مسئله فروشنده دوره گرد یا TSP جزو مسائل NP-Hard می باشد یعنی به عبارت ساده تر تعداد جواب های احتمالی برای حل آن دارای فضا و بعد زیادی است. تعداد جواب های احتمالی برای n شهر در مسئله فروشنده دوره گرد !(n-1)1/2 است یعنی برای 10 شهر باید از بین !(9)1/2 حالت که 181400 است دنبال یک جواب بگردیم بنابراین بررسی تمامی این جایگشت ها حتی برای شهر های کمتر هم مشکل خواهد بود به همین خاطر مسئله فروشنده دوره گرد را جزو مسائل NP-Hard حساب می کنند. راههای معمول برای حل چنین مسائلی عبارتند از:
-
طراحی الگوریتم های دقیق
طراحی الگوریتمهایی برای پیدا کردن جوابهای دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت میگیرد. سرراستترین راه حل امتحان کردن تمامی جایگشت های ممکن برای پیدا کردن کم هزینه ترین مسیر است که چون تعداد جایگشتها !n است، این راه حل غیرعملی میشود. با استفاده از برنامهنویسی پویا مسئله میتواند با مرتبه زمانی n22n حل شود. راههای دیگر استفاده از الگوریتمهای انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامهنویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش صفحه برای اندازههای بزرگ است.
-
الگوریتمهای اکتشافی
استفاده از الگوریتمهای اکتشافی که جوابهایی بهدست میدهد که احتمالاً درست هستند. این نوع راه حل ها جواب قطعی از مسئله نیست و جواب های تقریبی را به ما خواهد داد الگوریتمهای تقریبی متنوعی وجود دارند که خیلی سریع جوابهای درست را با احتمال بالا بهدست میدهند در ادامه در مورد این روش بیشتر صحبت خواهیم کرد.
-
روش های تقسیم مسئله
پیدا کردن زیرمسئلههایی از مسئله یا به عبارت دیگر تقسیم مسئله به مسئلههای کوچکتر، تا بتوان الگوریتمهای مکاشفهای بهتر و دقیقتری ارائه داد. مثلاً می توان کل مسئله را به شهرهایی با تعداد کم تقسیم بندی کرد و کم هزینه ترین مسیر ها را در آن بخش ها پیدا کرد و سپس جواب ها های هر بخش را باهم ادغام کرد.
کد کردن راه حلهای مسئله فروشنده دوره گرد
برای حل مسئله فروشنده دوره گرد بوسیله الگوریتم های هوشمند و بویژه الگوریتم های فرا اکتشافی می بایستی راه حل های آن کد شوند به طور کلی 3 روش کد کردن مسئله TSP وجود دارد:
-
نمایش جواب به صورت رشته گسسته جایگشتی
در این نوع راه حل با توجه به ویژگی الگوریتم حل کننده در گسسته بودن، یک جایگشت از اعداد تولید می شود و در هر تکرار جای این اعداد به نوعی باهم عوض می شود تا در نهایت بهترین جایگشت به عنوان بهترین راه حل ارائه می شود. این روش نسبت به دو روش دیگر بهتر عمل می کند از مهم ترین الگوریتم ها در این دسته می توان به موارد زیر اشاره کرد:
-
- الگوریتم ژنتیک یا Genetic Algorithms
- شبیهسازی تبرید یا Simulated Annealing
- جستجوی ممنوعه یا Tabu Search
- جستجوی همسایگی متغیر یا Variable Neighborhood Search
- بهینهسازی کلونی مورچگان یا Ant Colony Optimization
- جستجوی هارمونی یا Harmony Search
-
نمایش جواب به صورت کلیدهای تصادفی یا Random Key
در این نوع راه حل که با الگوریتم های پیوسته انجام می شود جایگشت را مستقیماً نمی توان تولید کرد به همین دلیل از مرتب سازی تعداد مقادیر موجود در جواب الگوریتم یک جایگشت ایجاد می شود و به عنوان جواب مسئله فروشنده دوره گرد در هر تکرار مورد مقایسه قرار می گیرد. از مهم ترین الگوریتم ها در این دسته می توان به موارد زیر اشاره کرد:
-
- بهینهسازی ازدحام ذرات یا Particle Swarm Optimization
- الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm
- تکامل تفاضلی یا Differential Evolution
- بهینهسازی مبتنی بر جغرافیای زیستی یا Bio-geography Based Optimization
- استراتژیهای تکاملی یا Evolution Strategies
- برنامهریزی تکاملی یا Evolutionary Programming
برای مقایسه انواع الگوریتم ها با یکدیگر برای حل مسئله فروشنده دوره گرد می توانید مقایسه الگوریتم های حل مسئله TSP را مشاهده کنید.
-
نمایش جواب به شکل ماتریسهای فرومون
نمایش جواب به شکل ماتریسهای شبیه فرومون که توسط تمامی الگوریتمهای اشاره شده در قسمت قبل قابل استفاده میباشد.
الگوریتم جستجوی ممنوعه یا Tabu Search، از قویترین الگوریتمها در زمینه حل مسائل بهینهسازی، به خصوص مسائل بهینهسازی مبتنی بر گراف و مسائل بهینهسازی ترکیباتی است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل آنها از الگوریتم TS استفاده میشود، مسئله فروشنده دوره گرد یا TSP است. این الگوریتم پاسخهای بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه میکند.
پاورپوینت مسئله فروشنده دوره گرد
پارپوینت حل مسئله فروشنده دورهگرد یا Traveling Salesman Problem به اختصار TSP درباره روش های حل مسئله فروشنده دوره گرد و کد کردن راه حل های مسئله فروشنده دوره گرد توضیح داده است. برای اطلاعات بیشتر و دریافت این پاورپوینت بر روی لینک زیر کلیک نمایید.
درباره امین جلیل زاده رزین
پایه گذار و موسس وب سایت آموزشی پی استور، مدرس دانشگاه فنی و حرفه ای، برنامه نویس و تحلیل گر سیستم، پژوهشگر در حوزه الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده. ایشان در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.
جامع و کامل. فوق العاده بود
خیلی عالی