منطق الگوریتم شاخه وکران بر این اساس است که از استراتژی تقسیم و غلبه برای تقسیم‌بندی فضای جواب به چند زیر مسأله بهره می‌جوید، و سپس عملیات بهینه‌سازی را روی این زیر مسأله‌ها اجرا می‌نماید. الگوریتم های مختلفی از شاخه و کران برای حل CVRP در دسترس است. تا اواخر دهه 1980، موثرترین الگوریتم شاخه و کران بر مبنای آزاد سازی ترکیبی[4] بود، که شامل آن دسته از مسائل بر مبنای مسائل تخصیص[5] (AP)، و کوتاهترین درخت جستجو با محدودیت درجه[6] می باشند. در روش شاخه و کران بر مبنای مسائل تخصیص روش آزاد‌سازی با فرض حذف محدودیت‌های ظرفیتی صورت می‌پذیرد. مسأله حاصله را می‌توان یک مسأله تخصیص در نظر گرفت و نسبت به حل آن اقدام نمود. مسائل متقارن و نامتقارن را می‌توان با این روش حل کرد. لاپورته وهمکاران در سال 1986 و میلر در سال 1995 این روش را برای حل مسائل CVRP به کار گرفتند. در نوع دوم الگوریتم‌های شاخه و کران بر مبنای کوتاهترین درخت جستجو با محدودیت درجه با استفاده از تحدید شاخه و کران بعد از حذف محدودیت‌هایی که درجه آنها خارج از صورت مسأله است نسبت به حل مسأله اقدام نمود. کریستوفیدز در سال1981 این روش را برای حل مسائل CVRP به کار گرفت. آزاد سازی کیفیت پایینی در حل مسائل ترکیبی دارد به همین دلیل روش‌های آزاد‌سازی براساس مفاهیم لاگرانژ توسعه یافت. بوسیله این روش، مسائل بسیاری را می‌توان حل نمود. تاث و ویگو  بر اساس مفاهیم لاگرانژ به حل دقیق مسأله CVRP نمودند (ظهره‌وند،2011) و (قصیری،2007).

[1] Branch-and-Bound

[2] Branch-and -Cut

[3] Branch-and-Price

[4] Combinatorial Relaxation

[5] Assignment Problem

[6] Degree-Constrained Shortest Spanning Tree

[7] Linear Programming

[8] Column Generation

دانلود پایان نامه حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی با استفاده از یک الگوریتم فرابتکاری کارآمد