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

از اصلی‌ترین روش‌های شناخته‌شده در دو دهه اخیر برای حل CVRP است، که در این قسمت معرفی خواهند شد. ابتدا، الگوریتم‌های بر مبنای شاخه و کران[1] توضیح داده خواهند شد. سپس، الگوریتم‌های بر مبنای روش شاخه و برش[2] بررسی می‌شوند. نهایتاً، الگوریتم‌های بر اساس روش شاخه و بها[3] معرفی می‌شوند.
یکی از دیدگاه‌های دقیق به مسأله VRP که توسط فیشر در سال 1994 مطرح گردید الگوریتم شاخه و کران می‌باشد که موفق شده است مسأله‌ای با 71 مشتری را با موفقیت حل نماید. برای حل مسائلی با ابعاد بزرگتر و یا یافتن جواب بهینه در زمان سریع‌تر می‌بایست از الگوریتم‌های ابتکاری بهره گرفت که در ادامه توضیح داده خواهند شد.
منطق الگوریتم شاخه وکران بر این اساس است که از استراتژی تقسیم و غلبه برای تقسیم‌بندی فضای جواب به چند زیر مسأله بهره می‌جوید، و سپس عملیات بهینه‌سازی را روی این زیر مسأله‌ها اجرا می‌نماید. الگوریتم های مختلفی از شاخه و کران برای حل CVRP در دسترس است. تا اواخر دهه 1980، موثرترین الگوریتم شاخه و کران بر مبنای آزاد سازی ترکیبی[4] بود، که شامل آن دسته از مسائل بر مبنای مسائل تخصیص[5] (AP)، و کوتاهترین درخت جستجو با محدودیت درجه[6] می باشند. در روش شاخه و کران بر مبنای مسائل تخصیص روش آزاد‌سازی با فرض حذف محدودیت‌های ظرفیتی صورت می‌پذیرد. مسأله حاصله را می‌توان یک مسأله تخصیص در نظر گرفت و نسبت به حل آن اقدام نمود. مسائل متقارن و نامتقارن را می‌توان با این روش حل کرد. لاپورته وهمکاران در سال 1986 و میلر در سال 1995 این روش را برای حل مسائل CVRP به کار گرفتند. در نوع دوم الگوریتم‌های شاخه و کران بر مبنای کوتاهترین درخت جستجو با محدودیت درجه با استفاده از تحدید شاخه و کران بعد از حذف محدودیت‌هایی که درجه آنها خارج از صورت مسأله است نسبت به حل مسأله اقدام نمود. کریستوفیدز در سال1981 این روش را برای حل مسائل CVRP به کار گرفت. آزاد سازی کیفیت پایینی در حل مسائل ترکیبی دارد به همین دلیل روش‌های آزاد‌سازی براساس مفاهیم لاگرانژ توسعه یافت. بوسیله این روش، مسائل بسیاری را می‌توان حل نمود. تاث و ویگو  بر اساس مفاهیم لاگرانژ به حل دقیق مسأله CVRP نمودند (ظهره‌وند،2011) و (قصیری،2007).
روش شاخه و برش از ترکیب یک روش شاخه و کران با روش صفحات برشی ایجاد گردید. در حال حاضر این روش به عنوان بهترین روش دقیق برای حل مسائلVRP مطرح است. در این روش صفحات برش به ازای هر گره به فرمولبندی  شاخه و کران اضافه می‌شوند. با این کار، آزاد سازی بهبود یافته و مسأله را می‌توان به کمک یک الگوریتم سیمپلکس به راحتی حل نمود. کاربرد این روش در حل مسائل VRP ابتدا توسط لاپورته و همکارانش در سال 1985 مطرح گردید. سپس در سال 1995 آئگرات و همکارانش نخستین روش شاخه و برش را برای حل چندین نمونه VRP تا حدی که شامل 134 مشتری می‌شد را به صورت کامل توسعه دادند. بالداچی و همکارانش در سال 2004 شکل دیگری از الگوریتم شاخه و برش را پیشنهاد دادند، که در آن آزادسازی برنامه‌ریزی خطی[7] (LP) با بکارگیری قوانین گوناگون کاهش متغیر و شاخه‌بندی تقویت شده است.
روش شاخه و هزینه یک روش دیگر برای حل مسائل عدد صحیح بزرگ به شمار می‌رود. این روش بر اساس روش‌های تولید ستون[8] ایجاد شده است. مهمترین و شناخته شده‌ترین روش شاخه و هزینه، الگوریتمی است که در سال 2006 توسط فوکوساوا و همکارانش برای حل مسائل مسیریابی وسایل نقلیه با ظرفیت محدود ارائه گردید. روش ارائه شده در حقیقت ترکیبی از روش‌های قبلی که آزاد‌سازی در آن بر اساس توسعه روشی بود که کریستوفیدز و همکارانش ارائه نمودند. این روش حدود کران بهتری نسبت به الگوریتم شاخه و برش ایجاد می‌نماید (ظهره‌وند،2011) و (قصیری،1007).
 
[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
 
دانلود پایان نامه حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی با استفاده از یک الگوریتم فرابتکاری کارآمد