مسئله مسیریابی خودرو

آمار وبلاگ میگه تا حالا چند نفر که دنبال مسئله مسیریابی خودرو یا VRP یا Vehicle Routing Problem میگشتن اومدن به این وبلاگ. بنابراین بر آن شدیم تا کمی راجع به این مسئله بنویسیم.

اصولا این مسئله رو میشه اینطوری توضیح داد: فرض کنید که یک انبار مرکزی داشته باشیم که اجناسی رو اونجا نگهداری میکنیم. طبعا دیوونه نیستیم و قصدمون فروش این محصولاته. بنابراین یک سری مشتری هم داریم که هر کدوم محل جغرافیایی خاصی دارن. فرض کنید تعداد این مشتری ها m تا باشه. در ضمن از در خونه هر مشتری به در خونه هر مشتری دیگه هم یه راه وجود داره. باز هم در ضمن از انبار به در خونه هر مشتری هم یه مسیر وجود داره. بنابراین تو رفت و آمد دنبال راه نمیگردیم. اما خوب هر مسیری رو که انتخاب کنیم، طول اون مسیر از قبل مشخصه. باز فرض کنید یه سری ماشین هم داریم که این اجناس رو به در خونه مشتری ها میبرن. ماشین ها هم خوب بالطبع هر کدوم یه ظرفیتی دارن.

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

1. طول کل مسیری که همه ماشین ها طی میکنن مینیمم بشه.

2. تعداد ماشین های لازم برای حمل و نقل کالاها مینیمم بشه.

3. ماکزیمم مسیری که یک ماشین طی میکنه رو پیدا کنیم، و این ماکزیمم مسیر رو مینیمم کنیم. اصولا به اینجور توابع هدف میگن توابع هدف مینیماکس.

4. سعی کنیم که هر ماشین به تعداد مساوی مشتری سرویس بده (این مورد تو مواردی مثل آژانس خیلی کاربرد داره).

5. سعی کنیم همه ماشین ها طول مسیر تقریبا یکسانی رو طی کنن. (این مورد هم تو مواردی مثل آژانس خیلی کاربرد داره).

6. هر ترکیبی از توابع هدف بالا که در اینصورت مسئله چند هدفه یا Multi-Objective میشه و الگوریتم های خاص خودشو داره.

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

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

1. تعداد ماشین ها از قبل مشخص نباشه و به صورت یه متغیر تصمیم در نظر گرفته بشه.

2. بیشتر از یه انبار مرکزی داشته باشیم. در اینصورت به مسئله میگن مسئله مسیریابی خودرو چندگانه یا Multiple Depot Vehicle Routing Problem.

3. اصلا از قبل معلوم نباشه چند تا انبار داریم ولی محل قرارگیری انبارهای احتمالی از قبل مشخص باشه و بخوایم در مورد تعدادشون تصمیم گیری کنیم.

4. اصلا از قبل معلوم نباشه چند تا انبار داریم و محل قرارگیری انبارها هم از قبل مشخص نباشه و بخوایم در محل و تعدادشون موردشون تصمیم گیری کنیم.

5. چند تا انبار داریم و میخوایم هر مشتری رو حتما به یکی از انبارها و قبل از حل مسئله تخصیص بدیم.

6. از قبل معلوم نباشه چند تا انبار داریم ولی محل قرارگیری انبارهای احتمالی از قبل مشخص باشه و بخوایم در مورد تعدادشون تصمیم گیری کنیم و باز هم بخوایم هر مشتری رو حتما به یکی از انبارها و قبل از حل مسئله تخصیص بدیم.

7. از قبل معلوم نباشه چند تا انبار داریم و محل قرارگیری انبارهای احتمالی هم از قبل مشخص نباشه و بخوایم در مورد محل و تعدادشون تصمیم گیری کنیم و باز هم بخوایم هر مشتری رو حتما به یکی از انبارها و قبل از حل مسئله تخصیص بدیم.

8. به جای یک نوع کالا چندین نوع کالا داریم که مشخصاتشون با هم فرق میکنه، اما هر مشتری به یکی از انواع کالاها احتیاج داره  (ترکیب این حالت رو با تمامی حالات بالا خودت لطف کن در نظر بگیر؛ مرسی).

9. به جای یک نوع کالا چندین نوع کالا داریم که مشخصاتشون با هم فرق میکنه و هر مشتری ممکنه به چندین نوع کالا احتیاج داشته باشه (بازم ترکیب این حالت رو با تمامی حالات بالا خودت لطف کن در نظر بگیر؛ مرسی).

10. ظرفیت ماشین ها با هم فرق میکنه.

11. هزینه ای که یک ماشین برای طی یک مسیر خاص باید تحمل کنه با هزینه سایر ماشین ها فرق کنه.

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

13. محل جغرافیایی مشتری ها با گذشت زمان تغییر کنه.

14. تعداد مشتری ها با گذشت زمان تغییر کنه.

15. محل و تعداد مشتری ها با گذشت زمان تغییر کنه. (به این سه مورد اخیر مسائل پویا یا Dynamic میگیم)

16. مشخصات ماشین ها با گذشت زمان تغییر کنه. (بازم پویا)

17. نیاز هر مشتری رو باید در یک بازه زمانی خاص از قبل تعیین شده پاسخ داد. به این مسئله میگن Vehicle Routing Problem with Time Window یا VRPTW. (لطف کن بازم ترکیب این حالت رو با حالت های بالا در نظر بگیر)

18. مجبور نباشیم که به همه مشتری ها سرویس بدیم و بتونیم تصمیم بگیریم که نیاز یه سری از مشتری ها رو پاسخ ندیم. (لطف کن بازم ترکیب این حالت رو با حالت های بالا در نظر بگیر)

19. مشخصات مسیرها با گذشت زمان تغییر کنه.

20. و غیره و غیره و غیره.

سخت ترین مسئله ای که تا حالا در این زمینه دیدم این بوده که لزومی نداشته به همه مشتری ها سرویس بده و به هر مشتری باید در یه بازه زمانی خاص سرویس میداده و تعداد مشتری ها در طول زمان تغییر میکردن و مشتری رو باید از یه جایی اول سوار میکرده و بعد یه جای دیگه پیاده میکرده و در این حین حق سرویس دادن به مشتری دیگه رو نداشته. قیافش آشناس نه؟ آره دوست من. در مورد تاکسی تلفنی صحبت میکنیم. اسم مسئله رو طرف گذاشته بود VRPPDTW یا Vehicle Routing Problem with Pickup and Delivery and Time Window. یکمی تو اینترنت بگردی میتونی پیدا کنی این مقاله رو.

این لیست بالا رو میشه تا تقریبا شماره 50 (حداقل) ادامه داد. حوصله داشتی ادامه بده واسه منم بنویس. بنابراین تعداد بسیار بسیار زیادی مسئله داریم که روش حل و خصوصیات ناحیه شدنی هر کدوم با اون یکی فرق داره. تقریبا همه این مسئله ها هم NP-Complete هستن. قول میدم پست بعدی در مورد مسائل NP-Complete باشه اما حالا علی الحساب معنیش اینه که نمیشه این مسئله ها رو راحت حل کرد. بنابراین برای حل هر کدوم میشه هزار تا روش پیشنهاد داد و کارایی هاشون رو با هم مقایسه کرد. خیلی از انواع این مسائل رو تا حالا حتی کسی حل هم نکرده.

همه اون چیزی که بیان شد یعنی این مسئله خوراک مقاله میباشه. دوست عزیزی که میخوای دکترا بخونی و رشته شما تحقیق در عملیات (OR) یا مهندسی صنایعه، به این مسئله فکر کن. شاید جالب باشه. یکی از مواردی که میشه روش کار کرد مثلا تغییر سود دریافتی از مشتری ها ئر طول زمانه. این تغییر میتونه خطی یا غیر خطی باشه که در هر دو صورت دهنت مسواک زده میشه تا بخوای مسئله رو حل کنی (اونایی که رسته های بالا رو خوندن حتما میدونن من چی میگم).

پی نوشت: ببخشید که اینهمه طولانی شد.

پی نوشت 2: قول میدم دیگه هیچ کسی با این جستجو به این وبلاگ وارد نخواهد شد. اینم میزاریم به حساب قوانین مورفی.

پی نوشت 3: یه منبع خوب میتونه کتاب THE VEHICLE ROUTING PROBLEM: LATEST ADVANCES AND NEW CHALLENGES نوشته Sharda و Stefan باشه.

پی نوشت 4: یه منبع خوب دیگه میتونه کتاب The Vehicle Routing Problem نوشته Toth و Vigo باشه.

اسباب کشی و مابقی قضایا

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

ضمن گشت و گذار واسه پیدا کردن خونه، نتیجه گرفتم که معمولا دو قشر از آدمای اینجا این کار رو میکنن. چیکار میکنن؟ یکی از اطاق های خونشون رو به یه دانشجو و در ازای مبلغ خیلی کمی اجاره میدن و حتی بعضی وقتا برای طرف غذا هم درست میکنن. دسته اول آدمای خیلی مذهبی که قصدشون فقط کمک کردن به آدمای فقیر و از جمله دانشجوهاس (و البته تعداد این آدما تو آمریکای شمالی خیلی هم زیاده). یه دسته هم آدمایی که سنشون زیاده و هیچ کس رو ندارن و میخوان یکی باشه که باهاش صحبت کنن. صاحبخونه من رسما تو اشتراک هر دو تا مجموعه بالا قرار میگیره.

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

البته اجاره کردن اینجا به همین راحتی نبود. چرا؟ چون صاحبخونه خیلی مذهبیه. هزار تا شرط و شروط واسم گذاشتن. مثلا اینکه به هیچ عنوان حق ندارم دختری رو ببرم تو اطاقم. و هزار تا چیز دیگه که تقریبا همشون تو همین حدود یکمی بالاتر و یکمی پایین تر از شکم دور میزد.

منم البته بهشون پاتک زدم و شرط و شروط خودم رو گذاشتم. مثلا اینکه باهاشون شرط کردم به هیچ عنوان گوشت خوک نمیخورم؛ آخه این خانومه قراره روزی یک وعده غذای گرم واسم درست کنه. و البته هزار تا چیز دیگه که تقریبا همشون مربوط به دقیقا خود شکم میشد.

حالا یه مشکل خیلی بزرگ دارم. اونم اینکه این خانومه خیلی خیلی زیاد غذا درست میکنه. ما کلا سه نفریم ولی اندازه حداقل شش هفت نفر غذا درست میکنه. مثلا یه شب 23 تا رون مرغ درست کرده بود. شمردم به خدا.

یه شب دیگه ورداشته بود Roas Pork درست کرده بود و چون من گوشت خوک نمیخورم واسه من Roast Beef درست کرده بود. فکر کنم حدود 10 کیلو گوشت بود حداقل. جالب اینه که با هر غذایی که درست میکنه یه قابلمه هم پلو درست میکنه. یه دفعه ازش پرسیدم چرا هی پلو درست میکنی؟ گفت آخه تو ایرانی هستی و غذای اصلی اونجا برنجه. بهش گفتم من تو ایران هم که بودم زیاد پلو نمیخوردم چون پلو دوست ندارم. ولی بازم هر شب یه قابلمه پلو درست میکنه. خلاصه هر شب همین برنامس. امشب هم واسه سه نفر آدم اینا رو درست کرده بود:

1. یه بوقلمون درسته که تو فر کبابش کرده بود.

2. یه قابلمه پلو.

3. سیب زمینی آب پز به مقدار بسیار زیاد.

4. کلم بروکلی آب پز.

5. سالاد.

6. کیک.

7. شربت آلبالو.

بوقلمون خیلی بزرگه. ما سه نفری بیشتر از دو پنجمش رو نتونستیم بخوریم. اوضاع کلم بروکلی بهتر بود، چون همه دوست داریم کلم بروکلی رو. سالاد هم همینطور. اما سیب زمینی ها و پلو و کیک و سایر موارد واقعا خورده نشد. باقیمونده غذا رو چیکار کردیم؟ معلومه. سطل آشغال. از مرده پرسیدم اینجا کسی فقیر نیست اضافی غذا رو بهش بدیم؟ گفت همه همسایه ها هر روز همین قدر غذا دور میریزن. خیالت راحت باشه. حالا من موندم و عذاب وجدان. بابا جان تو آفریقا مردم دارن از گرسنگی میمیرن. ما اونوقت اینهمه غذا دور میریزیم.

صاحبخونه عزیز. یکمی غذا کمتر درست کن. به جاش یا اجاره خونه رو کم کن، یا اضافی پول رو ببر به گرسنه ها کمک کن. منم اینطوری شب بدون عذاب وجدان میخوابم.

رفتم از چیزایی که از غذا باقی مونده بود عکس گرفتم تا یکمی تو عذاب وجدان با من شریک بشی…

پول یا گول

همیشه واسم سوال بوده که این مردم گول خوردن یا پول گرفتن؟

رو کلمه “این مردم” کلیک کن تا ببینی منظورم کدوم مردمه.

مادر