بهــــترین مســـیر کــــدومه؟

وقتی برای پیاده روی میزنین بیرون از کدوم مسیرها میرین؟ درسته از خیابون هایی که زیباتره، سرسبزتره یا فروشگاه داره که میتونین قدم بزنین و اون ها رو تماشا کنین. یعنی بهینه ترین مسیر رو برای پیاده روی انتخاب می کنین. حالا اگه کار داشته باشین، باید کلی خرید انجام بدین، لباسها رو هم از اتوشویی بگیرین، یک سر هم باید به بانک بزنین و همه رو هم باید در بازه زمانی خاصی انجام بدین، کمی کارتون گیر میکنه!

باید فکر کنین چطور می تونین بهترین مسیرها رو انتخاب کنین که ترافیک کمتری داشته باشه، سر راهتون چندتا کار رو بتونین با کمترین معطلی انجام بدین، سر وقت هم به خونه برگردین!

این مشکل شما، مساله فروشنده دوره گرده؟

این مساله رو تعمیم بدین به همه کسانی که کسب و کارشون از طریق حمل و نقل و جابجایی انجام میشه، چندین برابر، این مشکل براشون بزرگ میشه، این نوشته مربوط به همه آدمهایی میشه که روزانه باهاش درگیر هستن.

احتمالا خودتون عنوان فروشنده دوره گرد رو شنیده باشین. جالبه من اولین بار که این عنوان رو شنیدم تصویر یه آدم سردر گم توی ذهنم تداعی شد و اشتباه هم نکرده بودم.

ببینین بچه ها! فروشنده های دوره گرد به همه افرادی گفته میشه که محصولات و یا خدماتی رو ارائه میدن و باید زمان بندی، مسیر و هزینه هاشون رو هم محاسبه کنن، تا بتونن به تمامی درخواست های مشتریانشون در زمان مقرر و به بهترین شکل ممکن پاسخ بدن. با بیشتر شدن کسب و کارهای اینترنتی خیلی از شرکت ها و مجموعه ها هستن که با مشکل فروشنده دوره گرد دست و پنجه نرم می کنن، مجموعه هایی مثله:

• شرکت های پستی، که یک عالمه محموله و نامه رو باید تا قبل از ساعت چهار و در بازه های زمانی تعریف شده تحویل مشتریانشون بدن.
• رستوران های آنلاین که باید در بازه های ناهار و شام، بین ساعت 12 تا 3 بعداز ظهر یا 7 تا 10 شب غذاهایی رو به آدرس های مختلف و قبل از اینکه سرد بشه و  دقیقاً در زمانی که مشتری خواسته، تحویل بدن.
• فروشگاه های اینترنتی، که مشتریانشون به آدرس هایی که داده ان و در بازه های زمانی محدودی در اون مکان ها حضور دارن.
• تاکسی های اینترنتی، که باید از کوتاه ترین مسیر چند نفر و جابجا کنن یا سر ساعت مشخصی به مقصد برسونن.
• سرویس های مدرسه، که باید بچه ها رو برای مثال از بین ساعت 12 تا 1 بعدازظهر از در مدرسه بردارن و به خونه هاشون برسونن.
• انباردارانی که قبل از اتمام روز، از چندین انبار مختلف که هر کدوم یک سر شهر هستن، باید محصولات و محموله ها رو بارگیری کنن که هیچ! تازه باید برای توزیع اون ها در زمان و در قسمت های مختلف شهر یا حتی شهرهای دیگه هم برنامه ریزی کنن. حالا باید هزینه سوخت و زمان و مسافت رو هم در نظر داشته باشن.
• سیستم های توزیع پخش مویرگی، در شهر و کشور که باید در بازه های زمانی خاصی، محصولات تاریخدار مثل شیر یا مواد غذایی رو به سوپرمارکت ها برسونن.
• ویزیتور و بازاریاب ها، که روزانه باید مکان هایی رو در بازه زمانی تعیین شده ویزیت کرده و بازاریابی کنن.

در تمام مواردی که گفتیم، بازه زمانی، هزینه سوخت و مسیر بهینه، مهمترین نقش رو دارن.  مسئله فروشنده دوره گرد  TSPیا Traveling Sales Man یکی از مسائل مهم در دسته تئوری پیچیدگی محاسباتی الگوریتم ها است، که در گروه NP-Hard قرار می گیره. این مسئله اولین بار در سده ۱۸ توسط دو دانشمند به نام های هامیلتون ایرلندی و کیرکمن بریتانیایی مطرح شد. معمولا بحث در خصوص این تئوری در مطالب اولیه دروس ریاضیات دانشجویان ریاضی ارائه می شه و در دروسی نظیر تئوری گراف می تونین مطالب مشابه رو نیز مطالعه کنین.

شرح مسئله بدین شکل است:

یه فروشنده دوره‌گرد داریم که اگه از نقطه A کارش رو شروع کنه و فواصل بین نقاط هم مشخص باشه، باید کوتاه‌ترین مسیری که از تمام نقاط یکبار بازدید می‌کنه و به A بر می گرده رو پیدا کنیم که کدوم مسیر هست؟ یعنی به همون نقطه ای که شروع کرده برگرده، ولی از تمام نقاط موجود در مسیرش یکبار بگذره. تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به  شهر دیگه رو هم می‌دونیم. حالا نتیجه مطلوب اینه که، کم‌هزینه‌ترین مسیری که از یک شهر شروع بشه و از تمامی شهرها دقیقاٌ یکبار عبور کنه و به شهر شروع برگرده.

تعداد کل راه‌حل‌ها برابر است با برای n>۲ که n هم تعداد شهرهاست. در واقع این عدد برابر هست با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.

الگوریتم‌ها
مسئله فروشنده دوره‌گرد جزء مسائل NP-hard است. راه‌های معمول مقابله با مسائلی این چنینی عبارتند از:

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

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

الگوریتم‌های تقریبی متنوعی وجود دارن که خیلی سریع جواب‌های درست را با احتمال بالا میدن که می‌شه اونها رو به شکل زیر دسته‌بندی کرد:

• مکاشفه‌ای سازنده
• بهبود تکراری
• مبادله دوبه‌دو
• مکاشفه‌ای k-opt
• مکاشفه‌ای V-opt
• بهبود تصادفی

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

• الگوریتم ژنتیک
• هوش مصنوعی
• پردازش سیگنال
• الگوریتم PSO
• الگوریتم چرخه آب
• الگوریتم تکامل تفاضلی
• الگوریتم جستجوی ممنوع
• الگوریتم شبیه سازی تبرید
• الگوریتم فرهنگی Cultural
• الگوریتم بهینه سازی TLBO
• الگوریتم مورچگان
• الگوریتم زنبورها Bees
• الگوریتم رقابت استعماری
• الگوریتم کرم شب‌تاب Firefly
• الگوریتم جهش قورباغه SFLA
• الگوریتم بهینه‌سازی ملخ GOA
• الگوریتم علف هرز مهاجم IWO
• الگوریتم کلونی زنبور مصنوعی

روشی که ما برای حل این مسئله بر اساس الگوریتم ژنتیک هست. اینجا یه توضیح کوچیک در مورد این مسئله و روش هایی که برای حل اون گفته شده دادم و حالا لینک میدم به مقاله ای که در مورد VRP نوشته شده. VRP مخفف عبارت (Vehicle routing problem) سرویسی هست که از طریق مسئله فروشنده دوره گرد و با استفاده از سرویس های نقشه، یه راهکار عملی برای همه کسانی که از سرویس های حمل و نقل استفاده می کنن، ارائه می ده، تا مشکلشون رو به بهترین شکل ممکن حل کنن.