مسئله ی فروشنده دوره گرد یکی از مسائل معروف جهان است که الگوریتم‌های مختلفی برای حل اون طراحی شده و کاربردهای زیادی در بهینه سازی مسائل داره.
مسئله‌ی فروشنده‌ی دوره گرد
یک فروشنده‌ی محترم دوره گرد داریم که با چرخیدن در بین شهرهای مختلف (و احتمالاً فروش کالاهایی که همراهش هست) زندگی خودش رو می‌گذرونه. این فروشنده هزینه‌ی سفر رو از هر شهر به شهر دیگه می‌دونه (هزینه‌ی رفت و برگشت بین دو شهرِ A و B ممکنِ یکسان نباشه) و دنبال یک راه حل می‌گرده که از هر شهر فقط یک بار عبور کنه و با کمترین هزینه به شهر شروعش برگرده.
به عنوان مثال، عوامل ترافیکی، وزن بارِ همراه فروشنده، مسافت مسیر و… عواملی هستن که ممکنِ روی هزینه‌ی سفر تاثیر بذارن.
ایده‌های کاربردی
یکی از کاربردهای حل این مسئله، میتونه در برنامه‌های کاربردیِ (Application) تاکسی‌های اینترنتی مثل اسنپ باشه. به این صورت که برنامه یه مسیر بهینه به راننده پیشنهاد می‌ده و می‌گه اگه این مسیر‌ها رو قبول کنی، بعد از مثلا چهار سفر مبلغ 50000 تومان درآمد خواهی داشت و در عین حال توی ترافیک گیر نمی‌کنی، در اکثر اوقات مسافر داری و در آخر هم برمی‌گردی به خونه‌ی خودت. (البته ممکنِ یکی حاضر بشه توی ترافیک گیر کنه ولی پول بیشتری دربیاره)
یکی دیگه از کاربردهاش اینِ که برج‌های مراقبت می‌تونن مسیر حرکت هواپیماشون رو با حل این مسئله طراحی کنن (که البته فکر کنم این کار رو می‌کنن)
به ظاهر این مسئله می‌خوره که خیلی خفن باشه! و کاربردهای زیادی داشته باشه.
حل مسئله فروشنده‌ی دوره گرد در بهینه سازی چه مسائل دیگه‌ای میتونه کاربرد داشته باشه؟ (ترجیحاً خلاقانه باشه و مثل مثال‌های من کلیشه‌ای نباشه)
منم چن تا چیز به ذهنم رسیده، نمیدونم خلاقانه هست یا نه!
توی طراحی یه بیمارستان که بخش‌های مختلفش کجا باشن و چجوری بهم ارتباط دارن میتونه کمک کنه
توی نقشه یه خونه که بخش های مختلفش با توجه به مسیر هایی که طی می کنیم چه جوری باشن
مثلن آماری ببینیم رفت و آمدمون تو خونه چه جوریه و با این کار اتاق ها، آشپزخونه، سرویس‌ها و… کجا باشن بهتره
اصلن برای ساختن هر جایی بیایم حالت های مختلف رو در نظر بگیریم و براش مساله رو حل کنیم ببینیم کدوم بهینه تره
برای مراحل کارهای اداری بین جاهای مختلف، اینکه چه جوری بریم و اینا فک کنم خوبه
برای اون خدمت هایی که باید یه شهر رو کامل پوشش بدن، مثل:
جمع کردن زباله‌ها از سطح شهر. که چگونه تقسیم کار بشه و سریع همه کار انجام بشه
ماشین‌های پخش مویرگی تو سطح شهر
مسئله فروشنده دوره گرد(TSP) یه مسئله NP_hard هست. و تو مسائلی که بهشون اشاره شد نمیشه راه حل بهینه پیدا کرد. اما خب همونطور که گفتید کاربرد زیادی داره. حتی تو زندگی روزمره مثلا اینکه چجوری تخته وایت بورد رو پاک کنم که بهینه باشه.(این مسئله به صورت یه مسئله TSP مدل میشه.) چجوری تو مصرف سوخت کامیونای حمل بار یه کارخونه صرفه جویی کرد؟(این مسئله به خاطر قیمت سوخت تو ایران به چشم نمیاد. اما تو کشورایی که دارن برا گازوئیل لیتری چند یورو پول میدن مسئله خیلی مهمیه) لوله کشی آب. فاضلاب شهری و …
و کاربردهای زیادی داشته باشه.