مسیریابی وسایل نقلیه کلاسیک:"پایان نامه مسیریابی وسایل نقلیه"

۲-۷-۱- روش های دقیق

از اصلی ترین روش های شناخته شده در بیست سال گذشته واسه حل CVRPه، که در این قسمت معرفی می شن. اول، الگوریتم های بر مبنای شاخه و کران توضیح داده می شن. بعد، الگوریتم های بر مبنای روش شاخه و برش بررسی می شن. در آخرً، الگوریتم های براساس روش شاخه و بها معرفی می شن.

 یکی از دیدگاه های دقیق به مسأله VRP که به وسیله فیشر در سال ۱۹۹۴ مطرح گردید الگوریتم شاخه و کران می باشه که موفق شده مسأله ای با ۷۱ مشتری رو با موفقیت حل کنه. واسه حل مسائلی با ابعاد بزرگتر و یا پیدا کردن جواب بهینه در زمان سریع تر می بایست از الگوریتم های ابتکاری استفاده کرد که در ادامه توضیح داده می شن.

 منطق الگوریتم شاخه وکران بر این اساسه که از راه هدف دار تقسیم و غلبه واسه تقسیم بندی فضای جواب به چند زیر مسأله بهره می جوید، و بعد عملیات بهینه سازی رو روی این زیر مسأله ها اجرا می کنه. الگوریتمای مختلفی از شاخه و کران واسه حل CVRP در دسترسه. تا اواخر دهه ۱۹۸۰، موثرترین الگوریتم شاخه و کران بر مبنای آزاد سازی ترکیبی بود، که شامل اون دسته از مسائل بر مبنای مسائل تخصیص (AP)، و کوتاهترین درخت جستجو با محدودیت درجه هستن. در روش شاخه و کران بر مبنای مسائل تخصیص روش آزاد سازی با فرض حذف محدودیت های ظرفیتی صورت می پذیرد. مسأله حاصله رو می توان یه مسأله تخصیص در نظر گرفت و نسبت به حل اون اقدام کرد. مسائل برابر و نامتقارن رو می توان با این روش حل کرد. لاپورته وهمکاران در سال ۱۹۸۶ و میلر در سال ۱۹۹۵ این روش رو واسه حل مسائل CVRP به کار گرفتن. در نوع دوم الگوریتم های شاخه و کران بر مبنای کوتاهترین درخت جستجو با محدودیت درجه با به کار گیری محدود کردن شاخه و کران بعد از حذف محدودیت هایی که درجه اونا خارج از صورت مسأله س نسبت به حل مسأله اقدام کرد. کریستوفیدز در سال۱۹۸۱ این روش رو واسه حل مسائل CVRP به کار گرفت. آزاد سازی کیفیت پایینی در حل مسائل ترکیبی داره به خاطر همین روش های آزاد سازی براساس مفاهیم لاگرانژ پیشرفت یافت. بوسیله این روش، مسائل بسیاری رو می توان حل کرد. تاث و ویگو  براساس مفاهیم لاگرانژ به حل دقیق مسأله CVRP کردن (ظهره وند،۲۰۱۱) و (قصیری،۲۰۰۷).

Capacitated VRP(CVRP)

Exact Method

Heuristic Method

Meta-Heuristic Method

Branch-and-Bound

Branch-and -Cut

Branch-and-Price

Combinatorial Relaxation