برخی مشکلات مدل‌سازی VRP در شرایط واقعی

مسأله مسیریابی وسیله‌نقلیه وقتی در قیاس با دنیای واقعی قرار می‌گیرد با پیچیدگی‌ها و محدودیت‌هایی مواجه می‌شود که مدل‌سازی آن را بسیار متفاوت از مسأله ارائه شده خواهد نمود.

در ادامه نمونه‌ای از این محدودیت‌ها و مشکلات اشاره خواهد شد.

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

2-6- تعریف ریاضی مسأله مسیریابی وسیله نقلیه در حالت کلی

فرض کنید   یک گراف کامل باشد به طوریکه  مجموعه نقاط تقاضا و  نیز مبین مجموعه کمان‌ها یا مسیرهای شبکه است که نقاط را به هم متصل می‌کند. رأس  به مشتریان باز می‌گردد که هر کدام یک تقاضای مشخص غیر‌منفی دارند ( . همچنین رأس 0 به مبدأ باز می‌گردد. یک هزینه غیر‌منفی مرتبط با هر کمان اندازه هزینه‌ی سفر از نقطه ی   به نقطه  را نشان می دهد (همچنین  طول کمان یا فاصله زمانی بین رئوس  و   را نشان می دهد). اگر مقدار هزینه  را برای تمامی  و  ها را برقرار سازیم. آنگاه مسأله تبدیل به یک مسأله متقارن VRP تبدیل می‌شود و در غیر اینصورت مسأله نامتقارن است.

مسأله مسیریابی وسیله‌ نقلیه عبارتست از یافتن یک دسته  تایی مسیرهای ساده که هر کدام مرتبط است با مسیر یک وسیله با هدف کمینه‌کردن هزینه مجموعه مسیرها که نکات زیر را شامل می‌شود:

1. هر کدام از مسیرها از نقطه مبدأ آغاز و در نقطه مبدأ پایان می‌یابد.
2. هر کدام از مشتریان تنها توسط یک وسیله سرویس‌دهی می‌شوند.
3. مجموع تقاضای مشتریان که در یک مسیر قرار می‌گیرند نباید از ظرفیت وسیله نقلیه تجاوز کند.

2-6-1-  مدل عمومی مسأله VRP

در اینجا به معرفی مدلی می‌پردازیم که  توسط گلدن و همکاران در سال 1998 مطرح شد.

پارامترهای ورودی مدل را به این صورت تعریف می‌کنیم:

  گرافی است که شبکه مسیرهای وسایل نقلیه را بیان می‌کند بطوریکه  کلیه نقاط موجود در مدل (مشتریان)  مجموعه کمان‌های اتصال‌دهنده نقاط

n: تعداد نقاط( گره‌ها) تقاضا. (قرار گاه مرکزی در گره i=1 قرار دارد.

 : تعدا وسایل نقلیه در دسترس

 : ظرفیت هر وسیله نقلیه

 : حداکثر زمانی که خودروی v می‌تواند طی مسیر کند.

 : تقاضای گره

 : هزینه سفر(طول فاصله) بین گره‌های i ,j

X: ماتریس با درایه‌های بصورت

S: زیر مجموعه‌ای از E که در آن  است.

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

مسأله مسیریابی وسایل نقلیه در شکل کلاسیک به مسأله مسیریابی وسیله نقلیه با محدودیت ظرفیت  (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

روش‌های ابتکاری

 روش‌های ابتکاری با انجام جستجو نسبی و محدود در فضای جواب، جوابی با کیفیت خوب و در زمان حلی متوسط پیدا می‌نمایند. این الگوریتم‌ها در مسائل عملی بسیاری مورد استفاده قرار می‌گیرند. الگوریتم‌های ابتکاری برای حل مسائل به سه دسته کلی تقسیم می‌شوند:

1. الگوریتم‌های ابتکاری سازنده : این الگوریتم‌ها از قدیمی‌ترین این روش‌ها به شمار می‌روند. در قدم اول توجهی به هزینه جواب تولید نشده ندارند و به صورت تدریجی جواب موجه را ایجاد می‌کنند.

الگوریتم صرفه‌جویی مطرح شده توسط کلارک و رایت در سال 1964 یکی از الگوریتم‌های مشهور در زمینه VRPکه بر پایه مفهوم صرفه‌جویی عمل می‌کند. این الگوریتم به طور طبیعی در مسائلی کاربرد دارد که تعداد وسایل نقلیه در آنها متغیر بوده و برای هر دو نوع مسائل جهت‌دار و غیر‌جهت‌دار استفاده می‌شود (قصیری،2007).

2. الگوریتم‌های ابتکاری دومرحله‌ای :این الگوریتم‌ها خود به دو فاز مهم تقسیم می‌گردند:
3. اول دسته‌بندی رئوس، سپس مسیریابی
4. اول مسیریابی و سپس دسته‌بندی

در نوع اول ابتدا با رئوس (مشتریان) به دسته‌ ها یا گروه‌های موجه تقسیم می‌گردند سپس با تخصیص یک وسیله نقلیه به هر گروه مسیر بهینه برای آن ایجاد می‌کنیم. ژیلت و میلر در سال 1974 برای اولین بار این روش را ارئه نمودند. که به الگوریتم پیمایش نامیده می‌شود. منطق این الگوریتم بر پایه دسته‌بندی رئوس به گروه‌های موجه می‌باشد که توسط دوران یکنواخت یک شعاع چرخشی به مرکز دپو صورت می‌گیرد. سپس در هر دسته با حل یک مسأله TSP، مسیرهای وسایل نقلیه معین می‌گردند. روش بعدی در این فاز روشی است که توسط فیشر و جایکومار در سال 1981 ارائه شده است. در الگوریتم آنها به جای استفاده از روش‌های هندسی برای گروه‌بندی رئوس، از روش تخصیص یافته(GAP) استفاده می‌نمایند. روش تخصیص بدنبال کمینه کردن هزینه تخصیص هر مورد به دسته است. سپس هر دسته را می‌توان توسط روش ابتکاری یا دقیق حل نمود. در نوع دوم ابتدا یک تور بزرگ برای تمامی رئوس تعیین می‌گردد (مانند تور TSP ) سپس این تور به بخش‌های کوچکتر و موجهی تجزیه می‌شود که هر کدام به منزله یک مسیر برای یک وسیله نقلیه می‌باشد(قصیری،2007).

3. روش‌های بهبود : این روش‌ها در تلاش هستند تا جواب بهینه یافت شده را بهبود و ارتقا بخشند که این کار توسط تبادل پی در پی رئوس یا کناره‌ها در یک مسیر و یا بین دو مسیر وسیله به طور همزمان می‌گیرد.

بیشتر روش‌های بهبود برای مسأله TSP توسط لین در سال 1965 تحت عنوان مکانیزم  مطرح گردیده است. در این روش  کناره از تور حذف شده و سپس مجددا این  بخش را در تمامی حالت‌های ممکن به هم متصل می‌نماییم (قصیری،2007).

Generalized Assignment Problem

روش‌های فراابتکاری

روش‌های فراابتکاری ابزاری قدرتمند برای حل مسائل بهینه‌سازی به شمار می‌روند. حسن این روش‌ها در مقایسه با روش‌های ابتکاری اینست که فضای جواب بهتر مورد جستجو قرار می‌گیرد و احتمال توقف در بهینه‌های موضعی کاهش می‌یابد. این روش‌ها به سه دسته عمده تقسیم می‌شوند: روش‌های فراابتکاری بر اساس جستجوی همسایگی، روش‌های فراابتکاری براساس جستجوی جمعیت، و روش‌های فراابتکاری براساس شبکه‌های عصبی.

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

اولین الگوریتم‌های ارائه شده، الگوریتم شبیه‌سازی ذوب است. استفاده از این الگوریتم در ابتدای دهه 90 بسیار رایج بود. معروفترین روش شبیه‌سازی ذوب توسط عثمان در سال 1993 توسعه یافت. عثمان در الگوریتم خود از الگوریتم ذخیره که توسط کلارک و رایت معرفی شد، برای تولید جواب ‌های اولیه استفاده نمود. این الگوریتم جواب‌های خوبی تولید می‌کرد ولی جواب‌های بدست‌آمده قابل رقابت با جواب‌های حاصله از روش جستجوی ممنوعه که در همان زمان ارائه شده بود نبود. الگوریتم شبیه‌سازی ذوب معین توسط گلدن در سال 1998براساس توسعه الگوریتم پیشنهاد شده توسط دوئک در سال 1993 که براساس روش ابتکاری مسافرت رکورد به رکورد بود، ارائه گردید. تاث و ویگو نیز اقدام به ارائه قوانین برای تعریف عملگرها در روش شبیه‌سازی ذوب نمودند (قصیری،2007) و(ظهره‌وند،2011).

جستجوی ممنوعه از دیگر روش‌های جستجوی همسایگی به شمار می‌رود. ویلارد اولین تلاش‌ها را برای استفاده از روش جستجوی ممنوع برای حل مسائل VRP انجام داد. یکی از موفقترین روش‌های جستجوی ممنوعه در سال 1993 توسط تایلارد ارائه شد. ریگو و روکایرول در سال 1996 با بهره گرفتن از زنجیره‌ی خروج یک الگوریتم جستجوی ممنوعه را ارئه دادند. توسعه این روش توسط ژو و کلی در همان سال اتفاق افتاد. روش جستجوی ممنوعه دانه بندی شده (GTS)، قابلیت استحصال جواب بهینه را افزایش داد. این روش توسط تاث و ویگو در سال 2003 مطرح گردید. ایده اصلی این الگوریتم، حذف دائمی یال‌های طولانی که شباهت نزدیک به مجموعه جواب را ندارند، بود (قصیری،2007) و(ظهره‌وند،2011).

روش‌های فراابتکاری بر اساس جستجوی جمعیت با الهام از پدیده‌های طبیعی ایجاد شده و توسعه یافتند. منطق این روش مشتمل بر عناصری نظیر بازآفرینی، پدیده‌های تصادفی، رقابت، و انتخاب است. اولین نوع این روش‌ها، الگوریتم‌های ژنتیک هستند. الگوریتم‌های ژنتیک از پدیده‌های طبیعی الهام گرفته شده‌اند. هالند این الگوریتم را اولین بار معرفی نمود. در سال 2004 پرینس با بهره گرفتن از عملگرهای تقاطعی و جهشی، یک الگوریتم کارآمد برای حل مدل CVRP توسعه داد. در الگوریتم مزبور جواب‌ها به صورت تورهای بزرگ در نظر گرفته شده‌اند. برای تولید یک فرزند از دو والد ابتدا یک زنجیره از راه‌ها را به عنوان والد اول و رئوس را به عنوان والد دوم در نظرگرفته شده است. فرزند دوم به همین صورت تولید می‌شود، فقط این عمل با معکوس کردن والد اول و دوم ایجاد می‌شود. با به کارگیری ترکیب‌های مختلف از گره‌ها و یال‌ها، فرزندها (جواب‌ها) بهبود می‌یابند. (ظهره‌وند،2011).

Simulated Annealing

Tabu Search

Record-to-Record Travel Method

Geranular Tabu Search

Genetic Algorithm

- انواع اصلی مسأله مسیریابی وسیله نقلیه

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

• مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه
• مسیریابی وسیله نقلیه با ناوگان ناهمگن
• مسیریابی وسیله نقلیه با تقسیم تحویل
• مسیریابی وسیله نقلیه باتحویل و جمع آوری
• مسیریابی دوره‌ای وسیله نقلیه
• مسیریابی وسیله نقلیه چند انبار
• مسیریابی وسیله نقلیه بادر نظر گرفتن پنجره زمانی

2-8-1- مسیریابی وسیله نقلیه باظرفیت محدود وسایل نقلیه

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

با توجه به میزان ظرفیت هر وسیله نقلیه دو گونه CVRP تعریف می‌شود:

• مسیریابی وسایل نقلیه با دیدگاه ظرفیت محدود یکسان برای تمامی وسایل نقلیه(SCVRP)  که در این حالت کلیه وسایل نقلیه باهم یکسان ومشابه خواهد بود.
• مسیریابی وسایل نقلیه با دیدگاه ظرفیت محدود غیر‌یکسان برای وسایل نقلیه(ACVRP) که در این حالت ظرفیت وسایل نقلیه غیر‌یکسان بوده و در نتیجه انتخاب خودرو برای مسیرهای مختلف تابع ظرفیت آن خواهد بود.(شریعت،2004).

2-8-2- مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن

مسأله مسیریابی وسایل نقلیه با ناوگان ناهمگن (HFVRP) شکل دیگری از VRP است که در آن نیازی نیست که کلیه ماشین‌های ظرفیت، هزینه ثابت و متغیر برابری داشته باشند. ما می‌توانیم یک مجموعه از مشتری‌ها، N، و یک تعداد معین از انواع ماشین‌ها، M، را داشته باشیم؛ بطوریکه هر دسته از ماشین‌ها دارای یک ظرفیت ، یک هزینه ثابت ، و یک واحد هزینه متغیر  داشته باشند (m=1,…,M). در VRP کلاسیک، هر مشتری تنها می‌بایست توسط یک ماشین سرویس داده شود، هر ماشین می‌بایست سفر خود را از انبار مرکزی آغاز و به همانجا ختم کند و ظرفیت ماشین و حداکثر زمان هر سفر نمی‌بایست از حد خود تجاوز کنند. هدف HFVRP حداقل نمودن کلیه هزینه‌ها شامل هر دو هزینه‌های ثابت و متغیر بهره‌گیری از ماشین‌ها است. این ایده تنها مربوط به مسیریابی نمی‌شود، بلکه ترکیب ناوگان ماشین‌ها را نیز در نظر دارد. تحقیقات موجود در ادبیات موضوع برای حل انواع HFVRP بر روی توسعه الگوریتم‌های ابتکاری بجای روش‌های دقیق متمرکزند. آنها را می‌شود در دو دسته کلی قرار داد: روش‌های ابتکاری کلاسیک که اکثرا از الگوریتم‌های ابتکاری VRP ساده برگرفته شده‌اند، و روش‌های فراابتکاری.

Capacity Vehicle Routing Problem

Symmetric CVRP

Asymmetric CVRP

Heterogeneous Fleet VRP(HFVRP)