بهترین روش برای مسیریابی وسایل نقلیه

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

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

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

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

باید بفهمیم که مشکل مسیریابی وسایل نقلیه امون چیه؟

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

حالا VRP به چه معناست؟

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

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

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

مدل های VRP در حالت‌های کاربردی که در برخی موارد حتی مستقیما با توزیع فیزیکی کالاها مرتبط نیستن، به طور مکرر اتفاق میوفتن. سوارکردن کودکان به اتوبوس‌های مدرسه، تحویل تولیدات بین سوپرمارکت‌ها و فروشگاه‌های بزرگ، توزیع روزنامه، تورهای بازرسی و تعمیر بازدارنده، توزیعهر گونه کالا یا خدمت و غیره، همگی VRPهایی هستن که در اونها، کالاها و خودروها می‌تونن شکل های  متنوعی داشته باشن.

اغلب مسائل مسیریابی وسایل نقلیه (VRP)، NP-hard هستن و به نظر می‌رسه که قابل حل در زمانی چندجمله‌ای نباشن. الگوریتم‌های تحقیقاتی ارائه شده برای VRP عموماً شامل روش‌های دقیق و الگوریتم‌های بهینه‌سازی هوشمند هستن. الگوریتم‌های دقیق شامل روش‌های شاخه و کران، متدهای برنامه‌ریزی پویا و مانند اینها هستن. مثلا، Nobert روش‌های پیشرو شاخه و کران چندگانه پیشرو را ابداع کرده. در مقابل، الگوریتم‌های تقریبی عمدتاً شامل روش‌های جست‌وجوی ممنوع و شبیه‌سازی حرارتی، الگوریتم‌های ژنتیک بهینه‌سازی مورچگان و غیره است.

ضرورت مسایل مسیریابی وسایل نقلیه

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

برنامه ریزی هر یک از حمل و نقل های فوق از جایگاه ویژه ای برخوردار بوده و تحقیقات زیادی نیز در مورد اونها هنوزادامه داره. برنامه ریزی وسایل نقلیه به منظور جمع آوری قطعات از تأمین کنندگان و توزیع مواد اولیه به اون ها به طور هم زمان رو می شه به عنوان یک مسأله VRPSPD در نظر گرفت. در این مسأله سعی میشه که نحوه برنامه ریزی وسایل نقلیه به گونه ای انجام بشه که هزینه های حمل ونقل کاهش پیدا کنه.

از اون جا که مسأله مسیریابی وسایل نقلیه، جزء مسائل NP hard است و جواب بهینه ای برای این گونه مسائل با مقیاس بزرگ تا به حال شناخته نشده. از همین رو پژوهشگران زیادی با به کارگیری الگوریتم های ابتکاری برای رسیدن به جواب های بهتری در تلاش هستن تا مسأله مسیریابی وسایل نقلیه با جمع آوری و تحویل همزمان کالا نیز یک مسأله NP-hard رو حل کنن. در سال های اخیر از الگوریتم های فرا ابتکاری جهت حل این مسأله، بسیار استفاده شده و هنوز هم در تلاش هستن تا به بهترین شکل این مساله رو برطرف کنن. به همین خاطر در این جا سعی شده با ارائه یه روش فوق ابتکاری جهت حل این نسخه از مسأله مسیریابی، جواب های بهتری حاصل بشه.

انواع مدل های VRP

مسأله مسیریابی وسایل نقلیه (VRP) یک نام کلی برای تمام مجموعه هایی هست که در اونها ارتباط مشتری ها با وسیله نقلیه است، صورت می گیره. VRP با گذشت زمان، انواع مسأله مسیریابی با محدودیت هایی که بیشتر در عالم واقعی کاربرد داره، به وجود اومده که در زیر گفته شده ان:

مساله مسیریابی وسایل نقلیه VRP

• مسیریابی وسیله نقلیه با محدودیت ظرفیت – CVRP
• مسیریابی وسیله نقلیه با محدودیت مسافت – DCVRP
• مسیریابی وسیله نقلیه با بازه زمانی – VRPTW
• مسیریابی وسیله نقلیه دومسیره و برگشت کالا – VRPB
• مسیریابی وسیله نقلیه با ترکیبی از جمع آوری و تحویل کالا – VRPMD
• مسیریابی وسیله نقلیه با جمع آوری و تحویل همزمان کالا – VRPSPD

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

مسیریابی وسیله نقلیه با محدودیت مسافت (DCVRP)

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

مسأله مسیریابی وسایل نقلیه با پنجره های زمانی (VRPTW)

هر مشتری باید در محدوده ی زمانی مشخصی سرویس دهی شود . یکی از حالت های مسأله VRP، مسأله مسیریابی وسایل نقلیه با بازه زمانی نامیده می شه که در این مسأله علاوه بر محدودیت ظرفیت، هر یک از مشتری ها یا پایانه ها دارای فواصل زمانی مشخصی جهت ارائه خدمات هستن. در این مسأله زمان ارسال کالا از پایانه ممکن هست در ساعاتی با فواصل زمانی خاصی صورت بگیره که در چنین حالاتی گفته می شه پایانه بازه زمانی داره. ولی بیشتر اوقات این مشتری ها هستن که برای دریافت کالا محدودیت زمانی رو تعریف می کنن و فقط در اون ساعت ها، کالا رو دریافت نموده و یا برای ساعات ذکر شده اولویت در نظر می گیرن. با توجه به تعبیری که ارائه شد، دو نوع پنجره زمانی داریم: یکی این که گاهی اوقات این محدودیت زمانی به گونه ای هست که خارج از محدوده زمانی فوق، خدمات ارائه نمی شه، این پنجره زمانی رو پنجره زمانی سخت میگن. دیگه اینکه محدودیت زمانی، اولویت ترجیح دادن هست و می شه خارج از اون زمان خدمات ارائه کرد. ولی از مطلوبیت کمتری هم برخورداره. این نوع پنجره زمانی را پنجره زمانی نرم” میگن.

مسأله مسیریابی وسایل نقلیه با جمع آوری و تحویل کالا(VRPPD)

مشتری ها ممکن است مقداری از کالا را به انبار برگردانند. یکی از توسعه های معروف و پرکاربرد VRP مسأله مسیریابی وسایل نقلیه با جمع آوری و تحویل کالا” (VRPPD)  هست که مورد توجه بسیاری از محققان تحقیق در عملیات قرار گرفته. در حالت پایه ای مسأله مسیریابی وسایل نقلیه با جمع آوری و تحویل کالا، هر مشتری با دو پارامتر در نظر گرفته میشه که به ترتیب مقدار تقاضای تحویلی و جمع آوری رو برای مشتری هم نمایش می دن. فرض کنین در هر موقعیت مشتری، تحویل قبل از جمع آوری انجام بگیره، بنابراین مقدار بار موجود در وسيله نقليه، قبل از رسیدن به موقعیت داده شده به صورت مقدار بار اولیه منهای همه تقاضاهای تحویل شده به اضافه همه تقاضای جمع آوری شده حساب میشه.

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

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

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

• مسأله مسیریابی وسیله نقلیه با چند پایانه

فروشنده از انبارهای متعددی برای سرویس دهی به مشتریان استفاده می کنه. مسأله مسیریابی وسیله نقلیه با چند پایانه (MDVRP) نوعی مسأله مسیریابی با محدودیت ظرفیت هست که در اون چندین پایانه مرکزی جهت استقرار وسایل وجود داره و هر وسیله با یکی از این چندین پایانه حرکت خودش رو شروع کرده و پس از ارائه خدمات به مشتری ها، به همان پایانه یا پایانه های مرکزی دیگه برمی گرده. در این مسأله بیشتر از یک پایانه وجود داره که باعث پیچیده تر شدن مسأله می شه. ممکنه که کالاها در این چند مرکز نگهداری شده و از این مراکز برای مشتری ها ارسال بشن.

• مسأله مسیریابی وسیله نقلیه با مقدار تقاضای احتمالی

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

مسأله مسیریابی وسیله با وسایل همگن و ناهمگن

نوع وسیله نقلیه در این مساله یکی از پارامترهای خیلی مهمه، گاهی اوقات برای حمل و نقل کالاها از یک نوع وسیله با ظرفیت های یکسان استفاده می شه که به آنها وسایل همگن ها گفته میشه و در برخی مواقع ناوگان مورد استفاده، وسایل نقلیه متفاوت با ظرفیت های مختلف هست که اصطلاحا وسايل ناهمگن هم گفته میشه.

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