- انواع اصلی مسأله مسیریابی وسیله نقلیه

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

• مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه
• مسیریابی وسیله نقلیه با ناوگان ناهمگن
• مسیریابی وسیله نقلیه با تقسیم تحویل
• مسیریابی وسیله نقلیه باتحویل و جمع آوری
• مسیریابی دوره‌ای وسیله نقلیه
• مسیریابی وسیله نقلیه چند انبار
• مسیریابی وسیله نقلیه بادر نظر گرفتن پنجره زمانی

2-8-1- مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه

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

با توجه به میزان ظرفیت هر وسیله نقلیه دو گونه CVRP تعریف می‌شود:

• مسیریابی وسایل نقلیه با دیدگاه ظرفیت محدود یکسان برای تمامی وسایل نقلیه(SCVRP)  که در این حالت کلیه وسایل نقلیه باهم یکسان ومشابه خواهد بود.
• مسیریابی وسایل نقلیه با دیدگاه ظرفیت محدود غیر‌یکسان برای وسایل نقلیه(ACVRP) که در این حالت ظرفیت وسایل نقلیه غیر‌یکسان بوده و در نتیجه انتخاب خودرو برای مسیرهای مختلف تابع ظرفیت آن خواهد بود.(شریعت،2004).

2-8-2- مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن

مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن (HFVRP) شکل دیگری از VRP است که در آن نیازی نیست که کلیه ماشین‌های ظرفیت، هزینه ثابت و متغیر برابری داشته باشند. ما می‌توانیم یک مجموعه از مشتری‌ها، N، و یک تعداد معین از انواع ماشین‌ها، M، را داشته باشیم؛ بطوریکه هر دسته از ماشین‌ها دارای یک ظرفیت ، یک هزینه ثابت ، و یک واحد هزینه متغیر  داشته باشند (m=1,…,M). در VRP کلاسیک، هر مشتری تنها می‌بایست توسط یک ماشین سرویس داده شود، هر ماشین می‌بایست سفر خود را از انبار مرکزی آغاز و به همانجا ختم کند و ظرفیت ماشین و حداکثر زمان هر سفر نمی‌بایست از حد خود تجاوز کنند. هدف HFVRP حداقل نمودن کلیه هزینه‌ها شامل هر دو هزینه‌های ثابت و متغیر بهره‌گیری از ماشین‌ها است. این ایده تنها مربوط به مسیریابی نمی‌شود، بلکه ترکیب ناوگان ماشین‌ها را نیز در نظر دارد. تحقیقات موجود در ادبیات موضوع برای حل انواع HFVRP بر روی توسعه الگوریتم‌های ابتکاری بجای روش‌های دقیق متمرکزند. آنها را می‌شود در دو دسته کلی قرار داد: روش‌های ابتکاری کلاسیک که اکثرا از الگوریتم‌های ابتکاری VRP ساده برگرفته شده‌اند، و روش‌های فراابتکاری.

Capacity Vehicle Routing Problem

Symmetric CVRP

Asymmetric CVRP

Heterogeneous Fleet VRP(HFVRP)