مدل ریاضی PVRP

تابع هدف مدل برابر با مجموع دوهزینه ناوگان وکل مسافت طی شده به وسیله آن است. جزء اول نشان می‌دهد که اگر خودرو v مورد استفاده قرار گیرد. آنگاه هزینه  به سیستم تحمیل خواهد شد. جزء دوم مبین هزینه کل مسافت طی شده به وسیله ناوگان است. پارامتر ، جزء دوم هدف را به هزینه تبدیل می‌کند تا دیمانسیون جزء اول ودوم یکسان باشد. محدودیت (2-9) و (2-10)تضمین می‌کنند که هر خودروکه از مرکز گسیل شده مجددا بدان برگردد. محدودیت(2-11)و(2-12) تضمین می‌کند که به هر نقطه تقاضا به تعداد دفعات تعیین شده مراجعه صورت گیرد. محدودیت (2-11) بیان می‌کند که به نقطه i باید  خودرو وارد شود. محدودیت (2-12) بیان می‌کند که از نقطه i باید  خودروخارج شود. محدودیت (2-13) تضمین می‌کند هر خودرویی که به یک نقطه وارد می‌شوداز آن نیز خارج شود (محدودیت تعادل). محدودیت (2-14) اطمینان می‌دهد که کل تقاضای سرویس داده شده توسط هر خودرو از ظرفیت آن تجاوز نکند. محدودیت (2-15) اطمینان می‌دهد که کل زمان سرویس برای هر خودرو از حداکثر مجاز تجاوز نکند. محدودیت (2-16) مربوط به حذف زیر‌تورها است. زیرتورها عبارتند از مسیرهایی که در آن انبار وجود ندارد. (ازجمله مشکلات مسائل VRP وجود زیر تورها است که یکی از راه حل‌های آن استفاده از زیر‌مجموعه‌ها برای گره‌ها است. بدین صورت که برای مسأله‌ای با N گره باید تمام ترکیبات دوتایی، سه‌تایی، تا N‌تایی آن را تشکیل داده و محدودیت‌های مربوط به آنها را نوشت و به دلیل تعداد بسیار بالای ترکیبات فوق معمولا ابتدا بودن در نظر گرفتن این محدودیت‌ها مسأله حل می‌شود و در صورتی که زیر توری تشکیل نشده باشد، جواب حاصل جواب بهینه مسأله نیز است اما اگر یک یا چند زیر‌تور تشکیل شود باید با اضافه نمودن محدودیت‌های زیر‌تور‌های تشکیل شده مجددا مسأله حل شود. فرایند فوق ممکن است چندین بار تکرار شود که معمولا بسیار زمانبر بوده و به همین لحاظ در مسائلی که تعداد گره‌ها زیاد باشد اعمال نمی‌شود.

الگوریتم‌های پیشنهاد شده برای حل PVRP به دو دسته کلی روش‌های ابتکاری و فراابتکاری طبقه‌بندی می‌شوند. روش‌های ابتکاری بطور وسیعی برای حل PVRP مورد بررسی قرار گرفته‌اند. اکثر این روش‌ها، رویکردهای بهینه‌سازی چند مرحله‌ای دارند، که به دنبال حل مسأله به صورت ترتیبی می‌باشند. راسل و گریبین در سال 1991، یک رویکرد چند مرحله‌ای را برای حل PVRP ارائه کردند. اولین مرحله از روش پیشنهادی شامل یک الگوریتم ابتکاری است، که جواب‌های اولیه را بوسیله یک روش تقریبی شبکه تعمیم یافته تولید می‌کند. مرحله بعدی شامل یک روش ابتکاری تعویضی است، که کل هزینه سفرها را بر مبنای مسأله فروشنده دوره‌گرد کاهش می‌دهد. در مرحله سوم، کل هزینه سفر مجددا با توجه به مسیرهای حقیقی کاهش می‌یابد. سرانجام، یک مدل عدد صحیح 0-1 برای بهبود بیشتر مورد استفاده قرار می‌گیرد. چائو و همکارانش در سال 1995، یک روش ابتکاری دو مرحله‌ای را ابدا کردند. برای ایجاد جواب اولیه، آنها یک برنامه‌ریزی خطی عدد صحیح را برای تخصیص ترکیب روزهای بازدید به مشتری‌ها حل کردند. در مرحله بعد، آنها از عملگرهای بهبود دهنده مختلفی بهره جستند(ظهره‌وند،2011). برتازی و همکاران، یک الگوریتم ابتکاری را برای یک حالت خاص از PVRP تحت عنوان مسأله دوره‌ای فروشنده دوره‌گرد (PTSP) را ارائه کردند. الگوریتم آنها یک نوع ساختاری به همرا دستورالعمل‌های بهبود ترکیبی است. در هر تکرار، یک دستورالعمل شهری را که ملاقات نشده است، به ترکیبی از روزهای بازدید تخصیص می‌دهد؛ و در هر روز از ترکیب روزهای بازدید، هر شهر را در بهترین مکان ممکن در تور قرار می‌دهد. فرایند تکرار به طور موقتی متوقف می‌شود، و الگوریتم درصدد بهبود جواب‌های موجود برمی‌آید(برتازی و همکاران،2004).

روش‌های ابتکاری امروزه با ظهور روش‌های فراابتکاری از قبیل جستجو ممنوعه، جستجو پراکنده، و جستجو همسایگی متغیرها (VNS)، دیگر کمتر مورد استفاده قرار می‌گیرند. کوردئو و همکارانش در سال 1997، در این تحقیق یک جستجو ممنوعه ابتکاری را برای حل PVRP که همچنین در حل PTSP مورد استفاده قرار می‌گیرد را معرفی کردند. همسایگی شامل حرکت از یک مشتری از یک مسیر به مسیر دیگر در همان روز، و یا تخصیص یک ترکیب ملاقات جدید به یک مشتری است. اضافه یا حذف کردن یک مشتری توسط عملگر GENI انجام می‌گیرد. جستجو ممنوعه این امکان را فراهم می‌آورد که جواب‌های نشدنی در طول فرایند جستجو از یک تابع جریمه تطبیقی استفاه کنند. آنجلی و اسپرانزا در سال 2002، یک الگوریتم جستجوعه ممنوعه را برای حالت تعمیم یافته PVRP ارائه کردند. در مسأله آنها ماشین‌ها از قابلیت تجدید ظرفیت خود در امکانات بین راهی برخوردار هستند. تولید جواب اولیه در الگوریتم آنها مشابه دستورالعمل الگوریتم جاروب است. جواب‌های اولیه بوسیله دستورالعمل‌هایی بهبود می‌یابند که شامل چهار عملگر جابجایی : تخصیص مجدد، تغییر برنامه بازدید مشتری‌ها، توزیع مجدد، و تقاطع‌ها است. یکی از جذاب‌ترین بخش‌های این الگوریتم پیشنهادی، اجازه ورود جواب‌های نشدنی در طول فرایند جستجو است. به تازگی یک دستورالعمل برای الگوریتم جستجو پراکنده توسط الگره و همکارانش در سال 2007 برای حل یک مسأله برداشت مواد خام برای یک تولید کننده قطعات خودرو، توسعه داده شده است. آنها از یک روش دو مرحله‌ای بهره جسته‌اند، ابتدا توالی از روزها را ایجاد می‌کنند و سپس به تولید مسیر برای هر روز اقدام می‌کنند. آلونسو و همکارانش در سال 2008، یک الگوریتم جستجو ممنوعه را برای تعمیمی از PVRP که در آن ماشین‌ها امکان سرویس‌دهی به بیش از یک مسیر در طول یک روز را بشرطی که از حداکثر زمان تأخیر در سرویس تجاوز نکند، را دارند. با این وجود، برخی محدودیت‌های دسترسی هر ماشین به هر مشتری موجود است. اثر بخشی این الگوریتم پیشنهادی توسط اجرا بر روی برخی نمونه‌های تصادفی و موجود، ثابت شده است. در سال2009 هملمایر و همکارانش، یک VNS را برای حل PVRP توسعه دادند

Generalized Network Approximation Method

Periodic Traveling Salesman Problem

Scatter Search

Variable Neighborhood Search