احتمال توقف در بهینه‌های موضعی کاهش می‌یابد. این روش‌ها به سه دسته عمده تقسیم می‌شوند: روش‌های فراابتکاری بر اساس جستجوی همسایگی، روش‌های فراابتکاری براساس جستجوی جمعیت، و روش‌های فراابتکاری براساس شبکه‌های عصبی.
الگوریتم‌های جستجوی همسایگی به صورت متناوب اقدام به جستجوی در فضای جواب می‌کنند تا شرط خاتمه رخ دهد. در دهه گذشته تلاش‌های بسیاری در زمینه استفاده از نگرش جستجوی همسایگی برای حل VRP صورت گرفته است و الگوریتم‌های متنوعی ارائه گردیده است.
اولین الگوریتم‌های ارائه شده، الگوریتم شبیه‌سازی ذوب[1] است. استفاده از این الگوریتم در ابتدای دهه 90 بسیار رایج بود. معروفترین روش شبیه‌سازی ذوب توسط عثمان در سال 1993 توسعه یافت. عثمان در الگوریتم خود از الگوریتم ذخیره که توسط کلارک و رایت معرفی شد، برای تولید جواب های اولیه استفاده نمود. این الگوریتم جواب‌های خوبی تولید می‌کرد ولی جواب‌های بدست‌آمده قابل رقابت با جواب‌های حاصله از روش جستجوی ممنوعه[2] که در همان زمان ارائه شده بود نبود. الگوریتم شبیه‌سازی ذوب معین توسط گلدن در سال 1998براساس توسعه الگوریتم پیشنهاد شده توسط دوئک در سال 1993 که براساس
روش ابتکاری مسافرت رکورد به رکورد[3] بود، ارائه گردید. تاث و ویگو نیز اقدام به ارائه قوانین برای تعریف عملگرها در روش شبیه‌سازی ذوب نمودند (قصیری،2007) و(ظهره‌وند،2011).
جستجوی ممنوعه از دیگر روش‌های جستجوی همسایگی به شمار می‌رود. ویلارد اولین تلاش‌ها را برای استفاده از روش جستجوی ممنوع برای حل مسائل VRP انجام داد. یکی از موفقترین روش‌های جستجوی ممنوعه در سال 1993 توسط تایلارد ارائه شد. ریگو و روکایرول در سال 1996 با استفاده از زنجیره‌ی خروج یک الگوریتم جستجوی ممنوعه را ارئه دادند. توسعه این روش توسط ژو و کلی در همان سال اتفاق افتاد. روش جستجوی ممنوعه دانه بندی شده[4] (GTS)، قابلیت استحصال جواب بهینه را افزایش داد. این روش توسط تاث و ویگو در سال 2003 مطرح گردید. ایده اصلی این الگوریتم، حذف دائمی یال‌های طولانی که شباهت نزدیک به مجموعه جواب را ندارند، بود (قصیری،2007) و(ظهره‌وند،2011).
روش‌های فراابتکاری بر اساس جستجوی جمعیت با الهام از پدیده‌های طبیعی ایجاد شده و توسعه یافتند. منطق این روش مشتمل بر عناصری نظیر بازآفرینی، پدیده‌های تصادفی، رقابت، و انتخاب است. اولین نوع این روش‌ها، الگوریتم‌های ژنتیک[5] هستند. الگوریتم‌های ژنتیک از پدیده‌های طبیعی الهام گرفته شده‌اند. هالند این الگوریتم را اولین بار معرفی نمود. در سال 2004 پرینس با استفاده از عملگرهای تقاطعی و جهشی، یک الگوریتم کارآمد برای حل مدل CVRP توسعه داد. در الگوریتم مزبور جواب‌ها به صورت تورهای بزرگ در نظر گرفته شده‌اند. برای تولید یک فرزند از دو والد ابتدا یک زنجیره از راه‌ها را به عنوان والد اول و رئوس را به عنوان والد دوم در نظرگرفته شده است. فرزند دوم به همین صورت تولید می‌شود، فقط این عمل با معکوس کردن والد اول و دوم ایجاد می‌شود. با به کارگیری ترکیب‌های مختلف از گره‌ها و یال‌ها، فرزندها (جواب‌ها) بهبود می‌یابند. (ظهره‌وند،2011).
[1] Simulated Annealing
[2] Tabu Search
[3] Record-to-Record Travel Method
[4] Geranular Tabu Search