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

دسته دیگر از انواع مسایل VRP که آنرا در این بخش معرفی می‌کنیم عبارت است از مسأله مسیریابی دوره‌ای وسایل نقلیه (PVRP). همانند VRP عمومی، موقعیت تک تک مشتری‌ها به همراه تابع تقاضای قطعی آنها کاملا مشخص است. مسأله PVRP دارای یک افق برنامه‌ریزی مشتمل بر T روز است، و تواتر بازدید برای هر مشتری مشخص می‌کند که در این T-روزه هر چند وقت یکبار می‌بایست بازدید شود. یک جواب برای PVRP مشتمل بر T مجموعه از مسیرها است که در مجموع محدودیت‌های تقاضا و تواتر بازدید را برآورده می‌سازند. در این مسأله، تابع هدف معمولا حداقل نمودن مجموع هزینه‌های تمامی مسیرها در طول دوره برنامه‌ریزی است. واضح است که این دسته از مسایل حداقل به دشواری VRP است. انواع گوناگونی از PVRP در ادبیات موضوع معرفی شده است. یک طبقه‌بندی از انواع گوناگون PVRP را می‌توان در تحقیق که توسط مورگای و وندربک انجام گرفته است، یافت. تابع هدف‌های مختلف از یکدیگر متمایزند، به طور مثال حداقل‌سازی مسافت پیموده شده، زمان انتقال، و یا مجموع هزینه حمل و نقل؛ بنابراین منطقه‌بندی مسیرها، تقسیم یک بار کاری یکسان بر روی ماشین‌ها، و کیفیت سرویس‌دهی می‌تواند بخشی از تابع بهینه‌سازی باشد. تفاوت‌ها اغلب در محدودیت‌ها که می‌توانند به سه دسته کلی تقسیم شوند، رخ می‌دهد: محدودیت‌هایی که شامل (1) برنامه‌ریزی ملاقات‌ها (تواترهای مختلف، محدودیت در روزهای ویژه، و غیره)، (2) نوع تقاضا (ثابت و یا متغیر)، و (3) ناوگان ماشین‌ها (یکسان و یا غیریکسان) می‌شوند (مورگای و وندربک،2006).

2-8-5-1- تعریف ریاضی مسأله مسیریابی دوره ای وسایل نقلیه (PVRP)

مسأله مسیریابی دوره ای وسایل نقلیه، مسأله VRP را با توسعه دوره روزهای منفرد به دوره M-روزه تعمیم می‌دهد. اگر زیر مجموعه رئوس I={1,…,i,…,n} مطابق بامشتریان در نظر گرفته شود، در طول پریود، هر مشتری   بار ملاقات می‌شود (که تکرار ملاقات نامیده می‌شود). هر مشتری  با  تکرار ملاقاتش مشخص می‌شود. این ملاقات‌ها باید از ترکیب‌های روز ملاقات مجموعه مجاز پیروی کند. برای نمونه، اگر یک مشتری باید سه بار در یک دوره 6-روزه ملاقات شود، و ترکیب‌های مجاز روز-ملاقات (5،3،2) و (6،4،1) باشند، بنابراین این مشتری فقط می‌تواند در روزهای مرتبط با یکی از این ترکیبات ملاقات شود.

مسأله PVRP شامل یافتن همزمان مجموعه‌ای از V تور برای هر روز از پریود و تخصیص بهترین ترکیب روز-ملاقات به هر مشتری است بطوریکه همه نیازها تأمین شود و همه هزینه‌های سفر دوره M-روزه حداقل شود. مسأله PVRP همه محدودیت‌های VRP را رعایت می‌کند، و برخی محدودیت‌های اضافی عبارتند از:

1. هر مشتری باید یک ترکیب مجاز روز-ملاقات انتخاب نماید.
2. به هر مشتری فقط در روزهای مربوط به ترکیب روز-ملاقات سرویس داده می‌شود.
3. هر وسیله نقلیه می‌تواند بین دو مشتری در یک روز تردد کند اگر و تنها اگر هر دو مشتری برای ملاقات در آن روز زمانبندی شده باشند.