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

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

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

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

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

مسئله مسیریابی وسایل نقلیه با ظرفیت محدود یا CVRP یا Capacitated Vehicle Routing Problem

در این نوع مسئله، هر وسیله دارای ظرفیت مشخصی بوده که از پیش تعیین شده است و بارگیری وسیله بیش‌تر از آن حد مشخص مجاز نمی‌باشد. در این گونه مسائل، معمولاً متناظر با هر کمان یک هزینه غیر منفی در نظر گرفته می‌شود که این هزینه نشان‌دهنده هزینه سفر از یک رأس به رأس دیگر می‌باشد. و به ماتریسی که از مجموع تمامی این هزینه ها تشکیل می یابد ماتریس هزینه ها گفته می شود. حال اگر این ماتریس هزینه ها متقارن باشد (یعنی هزینه های رقت از یک رأس به رأس دیگر با هزینه های برگشت آن برابر باشد) ما با یک مسئله مسیریابی وسیله نقلیه ظرفیت دار متقارن (SCVRP) یا Symmetric Capacitated Vehicle Routing Problem روبرو خواهیم بود و در صورتی که این ماتریس هزینه ها نامتقارن باشد (یعنی هزینه های رقت از یک رأس به رأس دیگر با هزینه های برگشت آن نابرابر باشد) حاصل کار یک مسئله مسیریابی وسیله نقلیه ظرفیت دار نامتقارن (ACVRP) یا Asymmetric Capacitated Vehicle Routing Problem خواهد بود.

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

مسئله مسیریابی وسایل نقلیه همراه با پنجره‌های زمانی (VRP with Time windows)

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

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

مسئله مسیریابی وسایل نقلیه با پنجره‌های زمانی سخت

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

مسئله مسیریابی وسایل نقلیه با پنجره‌های زمانی نرم

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

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

 

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