روش های حل مسأله مسیریابی وسایل نقلیه کلاسیک

مسأله مسیریابی وسایل نقلیه در شکل کلاسیک به مسأله مسیریابی وسیله نقلیه با محدودیت ظرفیت  (CVRP) هم معروف است، سیستم توزیعی را مدل می‌کند که در آن به تعیین چگونگی توزیع کالا بین مشتریانی که از نظر موقعیت جغرافیایی با هم متمایزند توسط مجموعه مشخصی از وسایل نقلیه پرداخته می‌شود. جواب نهایی مسأله مسیرهایی را شامل می‌شود که هر یک ازآنها از یک انبار شروع شده، پس از گذشتن از تعدادی از مشتریان مجددا به مرکز باز می‌گردند. از آنجایی که هر یک از این مسیرها توسط یک وسیله نقلیه بایستی طی شود، لذا مجموعه تقاضاهای مشتریان در یک مسیر از ظرفیت وسیله نقلیه نبایستی تجاوز کند. هدف نهایی مسأله پیدا کردن مجموعه‌ای از مسیرهاست که در آن کلیه مشتریان بازدید شده و مجموع هزینه‌های سیستم توزیع حداقل گردد. گاهی اوقات به جای هزینه مسافت طی شده توسط خودروها، مجموع زمان صرف شده توسط آنها برای سرویس‌دهی به مشتریان لحاظ می‌شود. مقادیر بسیاری از نتایج تحقیقات که در آنها مسائل مسیریابی وسایل نقلیه با ظرفیت محدود بررسی شده‌اند، در قالب تئوری‌ها، روش‌ها، و الگوریتم‌ها ارائه شده‌اند. بطور کلی، روش‌های حل معرفی شده برای CVRP می‌تواند به در قالب روش‌های دقیق، ابتکاری، فراابتکاری تقسیم‌بندی شوند. مفهوم و موضوعات بحث برانگیز این سه دسته در ادامه بررسی خواهند شد.

2-7-1- روش‌های دقیق

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

 یکی از دیدگاه‌های دقیق به مسأله VRP که توسط فیشر در سال 1994 مطرح گردید الگوریتم شاخه و کران می‌باشد که موفق شده است مسأله‌ای با 71 مشتری را با موفقیت حل نماید. برای حل مسائلی با ابعاد بزرگتر و یا یافتن جواب بهینه در زمان سریع‌تر می‌بایست از الگوریتم‌های ابتکاری بهره گرفت که در ادامه توضیح داده خواهند شد.

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

Capacitated VRP(CVRP)

Exact Method

Heuristic Method

Meta-Heuristic Method

Branch-and-Bound

Branch-and -Cut

Branch-and-Price

Combinatorial Relaxation

Assignment Problem

Degree-Constrained Shortest Spanning Tree