مسیریابی وسایل نقلیه-قسمت پنجم

در ادامه مطالب قسمت های قبل در رابطه با تعریف مسئله مسیریابی وسایل نقلیه و شاخه های مختلف این مسائل، در این بخش، به ادامه معرفی شاخه ها و تقسیم بندی های این مسائل می ­پردازیم.

مسئله مسیریابی وسایل نقلیه دوره‌ای

(Periodic VRP)

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

مسئله مسیریابی وسایل نقلیه دوره‌ای با انتخاب سرویس دهی

(PVRP with service choice)

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

این حالت در مواردی مانند جمع آوری ضایعات و زباله که درآن هرمشتری باید در زمان مشخصی (مثلاً دوبار در هفته) سرویس داده شود کاربرد دارد.

مسئله مسیریابی وسایل نقلیه با ناوگان ترکیبی

(Mix Fleet VRP)

یکی از شاخه‌های مسئله مسیریابی وسایل نقلیه می‌باشد که در آن با وسائل نقلیه ناهمگن با ظرفیت ها و هزینه های ثابت و متغیر متفاوت سروکار داریم.

در این مسائل، هزینه کل یک مسیریابی، برابر با مجموع هزینه های ثابت و متغیر است که هزینه های متغیر با طول سفر در ارتیاط می باشد.

مسئله مسیریابی وسایل نقلیه با بارهای چندبخشی (تحویل گسسته)

(Split-delivery VRP)

همان‌طور که قبلاً اشاره شد، در مسئله مسیریابی وسیله نقلیه پایه‌ای فرض می‌شود که هر مشتری تنها توسط یک وسیله نقلیه و تنها در یک نوبت ملاقات می‌شود. اما این فرض همواره واقعی و درست نیست. در بسیاری از مواقع، تقاضای برخی از مشتریان از ظرفیت وسایل نقلیه بیشتر می‌باشد. در چنین مواقعی می‌بایست این فرض برداشته شده و امکان سرویس‌دهی به بعضی از مشتریان را با بیشتر از یک وسیله نقلیه فراهم نمود. مسئله مسیریابی وسایل نقلیه با بارهای چندبخشی (SDVRP)، توسعه‌ای از مسئله مسیریابی وسیله نقلیه بوده که به این موضوع در آن پرداخته شده و امکان سرویس‌دهی به مشتریان با بیشتر از یک وسیله نقلیه میسر می‌باشد.

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

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

(Open VRP)

یکی از شاخه‌های دیگر VRP، مسیریابی وسایل نقلیه باز (OVRP) می‌باشد که در این نوع مسائل پس از خدمت‌دهی هر وسیله نقلیه به تمامی مشتریان، وسائل نقلیه موظف نیستند که حتماً به محل دپو بازگردند.

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

حذف محدودیت بازگشت وسیله نقلیه به دپو لزوماً باعث ساده تر شدن مسئله مسیریابی وسایل نقلیه باز نمی گردد. چراکه مسئله همچنان به صورت یک مسئله NP-HARD باقی خواهد ماند.

مسیریابی وسایل نقلیه چند سطحی

(Multi-echelon VRP)

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

در قسمت بعدی این سری مطالب به معرفی سایر  انواع حالت های مسائل مسیریابی وسایل نقلیه و ادامه معرفی شاخه ها و تقسیم بندی های این مسائل و حالات خاص آنها خواهیم پرداخت.

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