برخی مشکلات مدل‌سازی VRP در شرایط واقعی

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

در ادامه نمونه‌ای از این محدودیت‌ها و مشکلات اشاره خواهد شد.

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

2-6- تعریف ریاضی مسأله مسیریابی وسیله نقلیه در حالت کلی

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

مسأله مسیریابی وسیله‌ نقلیه عبارتست از یافتن یک دسته  تایی مسیرهای ساده که هر کدام مرتبط است با مسیر یک وسیله با هدف کمینه‌کردن هزینه مجموعه مسیرها که نکات زیر را شامل می‌شود:

1. هر کدام از مسیرها از نقطه مبدأ آغاز و در نقطه مبدأ پایان می‌یابد.
2. هر کدام از مشتریان تنها توسط یک وسیله سرویس‌دهی می‌شوند.
3. مجموع تقاضای مشتریان که در یک مسیر قرار می‌گیرند نباید از ظرفیت وسیله نقلیه تجاوز کند.

2-6-1-  مدل عمومی مسأله VRP

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

پارامترهای ورودی مدل را به این صورت تعریف می‌کنیم:

  گرافی است که شبکه مسیرهای وسایل نقلیه را بیان می‌کند بطوریکه  کلیه نقاط موجود در مدل (مشتریان)  مجموعه کمان‌های اتصال‌دهنده نقاط

n: تعداد نقاط( گره‌ها) تقاضا. (قرار گاه مرکزی در گره i=1 قرار دارد.

 : تعدا وسایل نقلیه در دسترس

 : ظرفیت هر وسیله نقلیه

 : حداکثر زمانی که خودروی v می‌تواند طی مسیر کند.

 : تقاضای گره

 : هزینه سفر(طول فاصله) بین گره‌های i ,j

X: ماتریس با درایه‌های بصورت

S: زیر مجموعه‌ای از E که در آن  است.