الگوریتم‌های پیشنهاد شده برای حل PVRP به دو دسته کلی روش‌های ابتکاری و فراابتکاری طبقه‌بندی می‌شوند. روش‌های ابتکاری بطور وسیعی برای حل PVRP مورد بررسی قرار گرفته‌اند. اکثر این روش‌ها، رویکردهای بهینه‌سازی چند مرحله‌ای دارند، که به دنبال حل مسأله به صورت ترتیبی می‌باشند. راسل و گریبین در سال 1991، یک رویکرد چند مرحله‌ای را برای حل PVRP ارائه کردند. اولین مرحله از روش پیشنهادی شامل یک الگوریتم ابتکاری است، که جواب‌های اولیه را بوسیله یک روش تقریبی شبکه تعمیم یافته[1] تولید می‌کند. مرحله بعدی شامل یک روش ابتکاری تعویضی است، که کل هزینه سفرها را بر مبنای مسأله فروشنده دوره‌گرد کاهش می‌دهد. در مرحله سوم، کل هزینه سفر مجددا با توجه به مسیرهای حقیقی کاهش می‌یابد. سرانجام، یک مدل عدد صحیح 0-1 برای بهبود بیشتر مورد استفاده قرار می‌گیرد. چائو و همکارانش در سال 1995، یک روش ابتکاری دو مرحله‌ای را ابدا کردند. برای ایجاد جواب اولیه، آنها یک برنامه‌ریزی خطی عدد صحیح را برای تخصیص ترکیب روزهای بازدید به مشتری‌ها حل کردند. در مرحله بعد، آنها از عملگرهای بهبود دهنده مختلفی بهره جستند(ظهره‌وند،2011). برتازی و همکاران، یک الگوریتم ابتکاری را برای یک حالت خاص از PVRP تحت عنوان مسأله دوره‌ای فروشنده دوره‌گرد[2] (PTSP) را ارائه کردند. الگوریتم آنها یک نوع ساختاری به همرا دستورالعمل‌های بهبود ترکیبی است. در هر تکرار، یک دستورالعمل شهری را که ملاقات نشده است، به ترکیبی از روزهای بازدید تخصیص می‌دهد؛ و در هر روز از ترکیب روزهای بازدید، هر شهر را در بهترین مکان ممکن در تور قرار می‌دهد. فرایند تکرار به طور موقتی متوقف می‌شود، و الگوریتم درصدد بهبود جواب‌های موجود برمی‌آید(برتازی و همکاران،2004).
روش‌های ابتکاری امروزه با ظهور روش‌های فراابتکاری از قبیل جستجو ممنوعه، جستجو پراکنده[3]، و جستجو همسایگی متغیرها[4] (VNS)، دیگر کمتر مورد استفاده قرار می‌گیرند. کوردئو و همکارانش در سال 1997، در این تحقیق یک جستجو ممنوعه ابتکاری را برای حل PVRP که همچنین در حل PTSP مورد استفاده قرار می‌گیرد را معرفی کردند. همسایگی شامل حرکت از یک مشتری از یک مسیر به مسیر دیگر در همان روز، و یا تخصیص یک ترکیب ملاقات جدید به یک مشتری است. اضافه یا حذف کردن یک مشتری توسط عملگر GENI انجام می‌گیرد. جستجو ممنوعه این امکان را فراهم می‌آورد که جواب‌های نشدنی در طول فرآیند جستجو از یک تابع جریمه تطبیقی استفاه کنند. آنجلی و اسپرانزا در سال 2002، یک الگوریتم جستجوعه ممنوعه را برای حالت تعمیم یافته PVRP ارائه کردند. در مسأله آنها ماشین‌ها از قابلیت تجدید ظرفیت خود در امکانات بین راهی برخوردار هستند. تولید جواب اولیه در الگوریتم آنها مشابه دستورالعمل الگوریتم جاروب است. جواب‌های اولیه بوسیله دستورالعمل‌هایی بهبود می‌یابند که شامل چهار عملگر جابجایی : تخصیص مجدد، تغییر برنامه بازدید مشتری‌ها، توزیع مجدد، و تقاطع‌ها است. یکی از جذاب‌ترین بخش‌های این الگوریتم پیشنهادی، اجازه ورود جواب‌های نشدنی در طول فرایند جستجو است. به تازگی یک دستورالعمل برای الگوریتم جستجو پراکنده توسط الگره و همکارانش در سال 2007 برای حل یک مسأله برداشت مواد خام برای یک تولید کننده قطعات خودرو، توسعه داده شده است. آنها از یک روش دو مرحله‌ای بهره جسته‌اند، ابتدا توالی از روزها را ایجاد می‌کنند و سپس به تولید مسیر برای هر روز اقدام می‌کنند. آلونسو و همکارانش در سال 2008، یک الگوریتم جستجو ممنوعه را برای تعمیمی از PVRP که در آن ماشین‌ها امکان سرویس‌دهی به بیش از یک مسیر در طول یک روز را بشرطی که از حداکثر زمان تأخیر در سرویس تجاوز نکند، را دارند. با این وجود، برخی محدودیت‌های دسترسی هر ماشین به هر مشتری موجود است. اثر بخشی این الگوریتم پیشنهادی توسط اجرا بر روی برخی نمونه‌های تصادفی و موجود، ثابت شده است. در سال2009 هملمایر و همکارانش، یک VNS را برای حل PVRP توسعه دادند. ابتدا برای بدست آوردن جواب اولیه هر مشتری به طور تصادفی به یک ترکیب از روزهای بازدید تخصیص می‌یابد. هر مسیر با حل یک مدل VRP توسط الگوریتم پس‌انداز ایجاد می‌شود. سپس، در مرحله دوم برای جابجایی از روش‌های مرسوم و موثر از قبیل تبادل حرکت و تقاطع استفاده می‌شود، تا کیفیت جواب‌های آغازین در هر تکرار بهبود یابد. سرانجام جواب بدست آمده از طریق جابجایی با روش 3-opt تحت یک جستجو محلی مجدد بهبود می‌یابد(رفیعی،2010).
[1] Generalized Network Approximation Method
[2] Periodic Traveling Salesman Problem
[3] Scatter Search
[4] Variable Neighborhood Search