مساله فروشنده دوره گرد

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

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

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

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

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

الگوریتم‌ها

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

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

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

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

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