مسئله فروشنده دوره گرد Travelling Salesman Problem – روش های حل مسئله فروشنده دوره گرد

تاریخچه پیدایش مسئله فروشنده دوره‌گرد

مسئله فروشنده دوره‌گرد مسئله‌ای مشهور است ولی ریشه پیدایش اولیه مسئله فروشنده دوره گرد واضح و مشخص نیست. از ۱۸۳۲ در کتاب های خطی، این مسئله را با عنوان تورهای نمونه در آلمان و سوئیس برای فروشندگان دوره گرد مطرح کرده‌اند و در آن‌ها از دیدگاه ریاضی به این مسئله پرداخته نشده است. اولین بار مسئله فروشنده دوره گرد به صورت یک مسئله ریاضی توسط ریاضیدان ایرلندی ویلیام همیلتون W.R. Hamilton و ریاضیدان بریتانیایی توماس کرکمن Thomas Penyngton Kirkman تدوین شد.

به نظر می‌رسد ایده اصلی طراحی مسئله فروشنده دوره گرد از بازی نمادین همیلتون icosian نشأت گرفته شده است. هدف بازی پیدا کردن یک چرخه همیلتونی در امتداد لبه‌های یک ۱۲ وجهی است به طوری که از هر راس یک بار بازدید می‌شود و نقطه پایان آن همان نقطه شروع است. شکل کامل تر مسئله TSP برای اولین بار توسط ریاضیدانان در دهه ۱۹۳۰ در دانشگاه وین و هاروارد مورد مطالعه قرار گرفته است، به ویژه توسط کارل منگر Karl Menger که طرح مسئله فروشنده دوره گرد را مشخص کرد. کارل برای حل مشکل پستچی‌ها برای توزیع نامه‌ها فکر کرد و این مسئله را به شکل ریاضی و تعداد جایگشت‌های مسئله و حل آن مطرح کرد.

در دهه ۱۹۳۰ مریل فلوید Merrill M. Flood که به دنبال حل مشکل مسیریابی اتوبوس مدرسه بود، حل مسئله فروشنده دوره گرد مورد توجه اش قرار گرفت. هسلر ویتنی Hassler Whitney در دانشگاه پرینستون علاقه‌ای به این مسئله ایجاد کرد، که او آن را مسئله ۴۸ ایالت یا 48states problem نامید. اولین نشریه‌ای که از عبارت مسئله فروشنده دوره گرد استفاده کرد گزارش RAND Corporation 1949 توسط جولیا رابینسون بود. در دهه‌های ۱۹۵۰ و ۱۹۶۰، این مسئله پس از آن‌که شرکت RAND در سانتا مونیکا برای مراحل حل مسئله جوایزی را اهدا کرد، در محافل علمی اروپا و ایالات متحده رواج بیشتری یافت.

در سال ۱۹۵۹، جیلیان بردوود، J.H. هالتون و جان هامرسلی مقاله‌ای تحت عنوان “کوتاه‌ترین مسیر از طریق بسیاری از نقاط” در مجله انجمن فلسفی کمبریج منتشر کردند. در دهه‌های بعد، این مسئله توسط بسیاری از محققان ریاضی، علوم کامپیوتر، شیمی، فیزیک و سایر علوم مورد مطالعه قرار گرفت. با این حال، در دهه ۱۹۶۰، رویکرد جدیدی ایجاد شد، که به جای جستجوی راه حل‌های بهینه، راه حلی را تولید می‌کرد که طول آن به طور اثبات شده با مضرب طول مطلوب محدود می‌شد و با این کار مرزهای پایین‌تری برای مسئله ایجاد می‌کرد. سپس از این محدوده‌های پایینی با رویکردهای شاخه و حد استفاده می‌شد.

در سال ۱۹۷۶، کریستوفیدس و سردیوکوف مستقل از یکدیگر پیشرفت بزرگی در این راستا انجام دادند. الگوریتم کریستوفیدس-سردیوکوف راه حلی را ارائه می‌داد که در بدترین حالت حداکثر ۱.۵ برابر طولانی‌تر از راه حل بهینه است. از آن‌جا که این الگوریتم ساده و سریع بود، بسیاری امیدوار بودند که جای خود را به روش حل تقریباً مطلوب بدهد. با این حال، این امید به بهبود، فوراً محقق نشد و کریستوفیدس-سردیوکوف تا سال ۲۰۱۱، زمانی که الگوریتم تقریبی (بسیار) کمی بهبود یافته بود، بهترین روش برای بدترین سناریو بود.

ر

پاورپوینت مسئله فروشنده دوره گرد — Traveling Salesman Problem

کلیک کنید

تشریح مسئله فروشنده دوره گرد به عنوان مسئله گراف

مسئله TSP را می‌توان به عنوان یک گراف وزن دار بدون جهت مدل کرد، به طوری که شهرها رأس‌های گراف هستند و مسیرها لبه‌های آن هستند و فاصله یک مسیر وزن لبه است. در این گراف مسئله، به حداقل رساندن شروع و پایان در یک رأس مشخص پس از بازدید دقیق از یک رأس است. اغلب مدل، یک گراف کامل است (یعنی هر جفت رأس با یک لبه یا یال به هم متصل می‌شوند). در واقع هدف از حل مسئله فروشنده دوره گرد از دیدگاه یک مسئله گراف می‌خواهیم در یک گراف وزن دار یک سیکل بهینه یا تور همیلتونی را بیابیم به شرطی که جمع وزن یال‌ها یا لبه‌ها مینیمم باشد.

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

نظریه گراف — Graph Theory مطالب اساسی و انواع

کلیک کنید

روش‌های حل مسئله فروشنده دوره گرد

مسئله فروشنده دوره گرد یا TSP جزو مسائل NP-Hard می‌باشد یعنی به عبارت ساده‌تر تعداد جواب‌های احتمالی برای حل آن دارای فضا و بعد زیادی است. تعداد جواب‌های احتمالی برای n شهر در مسئله فروشنده دوره گرد !(n-1)1/2 است یعنی برای ۱۰ شهر باید از بین !(۹)۱/۲ حالت که ۱۸۱۴۰۰ است دنبال یک جواب بگردیم بنابراین بررسی تمامی این جایگشت‌ها حتی برای شهرهای کم‌تر هم مشکل خواهد بود به همین خاطر مسئله فروشنده دوره گرد را جزو مسائل NP-Hard حساب می‌کنند. راه‌های معمول برای حل چنین مسائلی عبارتند از:

• طراحی الگوریتم‌های دقیق

طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آن‌ها فقط برای مسائل با اندازه کوچک صورت می‌گیرد. سرراست‌ترین راه حل امتحان کردن تمامی جایگشت‌های ممکن برای پیدا کردن کم هزینه‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی n^۲۲ⁿ حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچک‌تر از ۲۰۰ شهر و استفاده از روش برش صفحه برای اندازه‌های بزرگ است.

• الگوریتم‌های اکتشافی

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

• روش‌های تقسیم مسئله

پیدا کردن زیرمسئله‌هایی از مسئله یا به عبارت دیگر تقسیم مسئله به مسئله‌های کوچک‌تر، تا بتوان الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه داد. مثلاً می‌توان کل مسئله را به شهرهایی با تعداد کم تقسیم بندی کرد و کم هزینه‌ترین مسیرها را در آن بخش‌ها پیدا کرد و سپس جواب‌های هر بخش را باهم ادغام کرد.

کد کردن راه حل‌های مسئله فروشنده دوره گرد

برای حل مسئله فروشنده دوره گرد بوسیله الگوریتم‌های هوشمند و بویژه الگوریتم‌های فرا اکتشافی می‌بایستی راه حل‌های آن کد شوند به طور کلی ۳ روش کد کردن مسئله 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 ارائه می‌کند.