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

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

مسئله مسیریابی وسیله نقلیه، که اولین بار توسط دانتزیک و رامزر معرفی شد، یکی از مهمترین مسائل بهینه سازی از دو دیدگاه تحقیقاتی و عملیاتی هست که در دسته مباحث طراحی سیستم های صنعتی هم جا می گیره. این مسئله که حالت ترکیبی از دو مسئله فروشنده دوره گرد (نامحدود در نظر گرفتن ظرفیت وسیله نقلیه) و بسته بندی صندوق ها (صفر در نظر گرفتن هزینه حمل و نقل) است، به نام (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 با گذشت زمان، انواع مسأله مسیریابی با محدودیت هایی که بیشتر در عالم واقعی کاربرد داره، به وجود اومده که در زیر گفته شده ان:

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