مسیریابی وسیله¬نقلیه – بررسی مقاله نهم

جستجوی محلی تکرارشونده با رویکرد انتخاب همسایگی انطباقی برای مسئله مسیریابی وسیله نقلیه چندانباره همراه با تحویل و ارسال همزمان

مقدمه

مسائل مسیریابی وسیله­نقلیه چندانباره با امکان همزمان تحویل و ارسال (MDVRPSDP) بیشتر در سناریوهای واقعی لجستیک حمل­ونقل مطرح می­شوند. در مسائل MDVRPSDP، مشتریان بطور همزمان می­توانند کالا را دریافت و درصورت خرابی یا انصراف و یا داشتن کالاهایی از قبل در موجودی آن­ها را ارسال کنند. همچنین حمل تمام کالاهای دریافت­شده باید از انبار شروع شده باشد و تمام کالاهای برگشتی از مشتریان باید به همان انبار ارسال شود. فروشگاه­های مواد غذایی معمولا دارای همچین سیستمی هستند زیرا غذای تازه را دریافت می­کنند و غذاهای قدیمی­تر یا بطری­های خالی را به همان انبار که قبلا از آن دریافت کرده­اند، برمی­گردانند.

 

در این مقاله درواقع با توسعه و گسترش مسئله مسیریابی وسیله­نقلیه با فرض همزمان تحویل و ارسال به مسئله ای با چندین انبار پرداخته شده­است. با افزایش تعاملات و ارتباطات و وجود هزینه­های سنگین حمل­و­نقل، توزیع مشترک انبارهای چندگانه جایگزین توزیع هر منطقه فقط توسط انبار در آن منطقه خاص شده است. با این امکان صرفه­جویی بیشتری در هزینه­ها صورت گرفته است. همانطور که در شکل (1) و (2) می­بینید مشتری C دور از مشتریان اصلی منطقه خود قرار گرفته است و به مشتریان منطقه دوم نزدیک­تر است. بنابراین اگر این امکان توزیع مشترک بین انبارها بدون درنظر گرفتن منطقه وجود داشته باشد با اختصاص مشتری C به انبار B، زمان پاسخ­دهی به مشتریان کاهش و سطح سرویس افزایش می­یابد. درواقع برای مثال، در سوپرمارکت­های زنجیره­ای به منظور برآورد به موقع نیاز مشتریان به دلیل ترافیک سنگین معمولا از چندین انبار در سطح شهر کالاهای خود را دریافت می­کنند.

از آنجا که مسئله MDVRPSDP یک مسئله پیچیده و NP-Hard است و در مسائل با مقیاس بالا با رویکردهای دقیق قابل حل می­باشد. هدف این مقاله یافتن یک روش متاهیوریستیک موثر برای حل می­باشد. ایده اصلی استفاده از روش الگوریتم جستجوی محلی تکرارشونده (ILS) است که یک روش همسایگی می­باشد که بر اساس احتمال موفقیت محل بعدی برای حرکت در جهت بهبود انتخاب می­شود. همچنین برای اینکه جستجو بهتر صورت گیرد از مکانیزم انتخاب همسایگی انطباقی (ANS) در مرحله بهبود و مرحله اختلال استفاده شده است. همچنین برای توسعه کار از روش­های جدید همسایگی تخریب استفاده شده­است. درواقع به منظور افزایش قدرت الگوریتم از یکسری استراتژی­ها مانند فهرست کاندید، تقویت، تنوع و ... می­توان استفاده کرد. روش­های مبتنی بر جستجوی محلی، آنقدر محلی هستند که زمان زیادی را فقط محدود به یک بخش از فضای جستجو می­کنند و ممکن است در همان قسمت بهترین جواب بدست آید ولی امکان جستجو و اکتشاف در مناطق دیگر کم می­شود. جستجو متنوع، عملگرهای متضاد جدید پیشنهاد می­دهند که با این کار جستجو را مجبور می­کنند به سمت مناطق جدید، حرکت کند.

مروری بر ادبیات

بطور کلی در زمینه حل MDVRPSDP، دو مقاله وجود دارد که با استفاده از متاهیوریستیک­ها به حل مدل پرداخته­اند. salhi & Nagy (1999) برای نخستین بار به حل این مسائل با الگوریتم هیوریستیک پرداختند. همچنین برای بار دوم در سال 2005 روش پیشنهادی قبلی خود را برای حل مسائل مسیریابی وسیله­نقلیه مربوطه را برای حل مسائل VRPSDP توسعه دادند. در هر دو مقاله مشتریان بصورت دو زیرمجموعه مرزی و غیرمرزی تقسیم شده­اند که اول مشتریان غیرمرزی به نزدیکترین انبار تخصیص داده می­شوند. سپس مشتریان مرزی که تخصیص داده نشده اند به انبار واقع در همان منطقه تخصیص داده شده و به مسیر ایجاد شده اضافه می­شود.

با توسعه لجستیک معکوس در مقالات الگوریتم­های دقیق فقط مثال­هایی با نمونه­های کوچک را می­توانند حل کنند. Dell’Amico و همکارانش با استفاده از الگوریتم­ دقیق رویکرد برش و قیمت برای نمونه­هایی با بیش از 40 مشتری فقط یک جواب بهینه پیدا کردند. بنابراین بیشتر تحقیقات بر روی استفاده از الگوریتم­های متاهیوریستیک تمرکز کردند. Crispim & Brandao (2005) از الگوریتم جستجوی ممنوع برای حل مسئله خود استفاده کردند. در سالهای 2010 به بعد بیشتر از الگوریتم­های متاهیوریستیک مثل کلونی مورچگان، ژنتیک، شبیه­سازی تبرید، جستجوی همسایگی بزرگ، جستجو همسایگی محلی و ... استفاده شده است.

تعریف مسئله و مدلسازی

مسئله MDVROSDP از یک گراف G=(V,E) تشکیل شده است که V مجموعه ای از راس­ها است که شامل دو زیرمجموعه مشتریان (V_c) و انبارها (V_d) می­شود و E نشان­دهنده کمان­ها می­باشد. در کمان­ها ماتریس هزینه و مسافت بین هر جفت راس (مشتری تا مشتری یا مشتری تا انبار) متقارن می­باشند. مفروضات بصورت زیر است:

• شروع و پایان هر مسیر باید یک انبار باشد.

• هر مشتری فقط یکبار توسط یک وسیله­نقلیه یا در یک مسیر ملاقات می­شود.

• حداکثر بار هر مسیر نباید از ظرفیت وسیله­نقلیه تخصیص­یافته به آن مسیر تجاوز کند.

• کل مدت هر مسیر (از جمله زمان سفر و زمان سرویس­دهی) نباید از زمان از پیش تعیین شده بیشتر شود.

• تمامی وسایل­نقلیه همگن هستند.

هدف مسئله: تعیین مسیرهای بهینه با به حداقل رساندن مجموع وزنی هزینه­های ثابت شامل تعداد وسیله نقلیه استفاده شده و مسافت طی شده توسط همه وسایل نقلیه می­باشد.

محدودیت­های مسئله:

با توجه به اینکه تعدادی وسیله نقلیه به هر انبار داده شده است محدودیت (2) تضمین می­کند که تعداد وسایل نقلیه خارج شده از انبار برای خدمت­دهی نباید بیشتر از تعداد وسایل نقلیه دردسترس در انبار مربوطه باشند.

محدودیت (3) تضمین می­کند که هر مشتری فقط یکبار و فقط توسط یک وسیله­نقلیه باید سرویس­دهی شود.

محدودیت (4) بیان می­کند هر وسیله­نقلیه از هر انباری که برای ارائه خدمت به مشتریان شروع به کار کرده باشد در نهایت و بعد از آخرین مشتری خود باید به همان انبار برگردد.

محدودیت (5) مربوط به حذف زیرتور است که تضمین می­کند حل برای یافتن بهترین جواب بدون زیرتور ادامه پیدا می­کند.

محدودیت (6) بیان می­کند که جابه­جایی بین انبارها وجود ندارد و وسیله­نقلیه نمی­تواند بصورت مشتقیم از انبار i به سمت انبار j برود.

محدودیت (7) مربوط به برقراری تعادل جریان­های ورودی و خروجی از هر گره می­باشد.

محدودیت (8) تضمین می­کند که ظرفیت هر وسیله نقلیه حفظ شود و بیشتر از ظرفیت بار جابه­جا نکند.

محدودیت (9) حداکثر مسافت مجاز که هر وسیله نقلیه می­تواند طی کند را بیان می­کند.

محدودیت­های (10) و (11) نشان­دهنده متغیرهای باینری و مثبت هستند.

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

روش حل پیشنهادی

جستجوی محلی تکرارشونده (ILS) می­تواند به بهینه­سازی محلی کمک کند تا از به دام افتادن در بهینه­های محلی جلوگیری شود. در این مقاله از ILS به عنوان چارچوب الگوریتم استفاده شده است. جستجوی محلی از یک راه­حل تصادفی شروع شده و همسایه­های جواب اولیه را جستجو می­کند. از دو فاز تشکیل شده است در فاز اول بهبود، بهترین جواب نسبت به جواب اولیه را پیدا می­کند و روش­هایی با بهترین مقدار تابع هدف را انتخاب می­کند اما این مرحله در یک مینیمم محلی متوقف می­شود. در فاز بعدی هدف جلوگیری از ایجاد سیکل می­باشد و بیشتر به معنی تغییر در راه­حل ایجاد شده است. مقدار این تغییر با متغیری به نام تقویت تعریف می­شود. از طریق روش­های مختلف جستجوی همسایگی، راه­حل­هایی با کیفیت متفاوت بدست می­آید. بنابراین برای نمونه­های مختلف باید تصمیم­گیری شود که از کدام روش جستجو همسایگی برای مرحله بعد جستجو استفاده شود. بجای استفاده از روش­های کلاسیک و تصادفی در انتخاب همسایگی در این مقاله از یک مکانیزم انتخاب جستجو همسایگی انطباقی در چارچوب جستجو همسایگی محلی تکرارشونده (ILS-ANS) استفاده شده است.

الگوریتم ILS-ANS

با یک جواب اولیه S₀ شروع می­شود. سپس الگوریتم یک روش همسایگی بهبود را برای حل و بدست آوردن یک جواب بهینه بهتر S_w اتخاذ می­کند. اگر S_w معیارهای پذیرش را پوشش دهد، جایگزین جواب فعلی S_c می­شود درغیراین صورت به جستجو برای یافتن جوابی بهتر از جواب قبلی می­پردازد. اگر پس از تکرارهای متوالی S_c نتواند بهبود یابد، بهترین جواب بدست آمده S_b جایگزین S_c می­شود. سپس روش همسایگی تخریب برای پذیرفتن جواب فعلی S_c و S_p انتخاب می­شود. بهبود بعدی بر روی جواب S_p زمانیکه f(s) نشان­دهنده هزینه­های S است، اعمال می­شود.

در راستای اینکه بتوانیم شناسایی کنیم که آیا این جواب جدید است، یک ساختار طراحی شده که تمام جواب­های پذیرفته شده را ذخیره­ می­کند. بطورکلی، پیگیری و بررسی تمام راه­حل­های قبلی دشوار و زمان­بر است به همین منظور، در این مقاله یک روش ساده و سریع ردیابی از طریق تابع هدف بررسی شده است. روش ثبت جواب­ها بصورت زیر است: مقدار فاصله سفر f(s) را از طریق بزرگنمایی به عددصحیح F تبدیل می­کنیم( مثلا f(s)=816.1 با بزرگنمایی داریم ۤF=8161). سپس یک آرایه Ar برای ثبت دفعاتی که جواب­ها پذیرفته شده­اند، تشکیل می­دهیم. آرایه­ها هر سری بروز رسانی می­شوند (Ar(F)=Ar(F)+1). اگر Ar(F)<1 بود آنگاه جواب جدید است درغیراینصورت جواب جدید نمی­باشد.

الگوریتم 1: الگوریتم پیشنهادی ILS-ANS

تولید یک جواب اولیه

اجرای الگوریتم تا زمانیکه شرط توقف برقرار نباشد

انتخاب همسایگی بهبود توسط مکانیزم انتخاب انطباقی

همسایگی بهبود توسط مکانیزم انتخاب انطباقی

S_p را با اعمال همسایگی بهبود انتخاب­شده بهبود داده و در مجموعه S_w ذخیره کنید

اگر S_w معیارهای پذیرش را داشته باشد جایگزین جواب فعلی می­شود.

اگر تابع جواب فعلی کوچکتر از تابع بهترین جواب باشد آنگاه جواب فعلی به عنوان بهترین جواب خوانده می­شود و آنگاه برای مرحله دوم الگوریتم به عنوان مقدار S_P تلقی می­شود.

اگر جواب فعلی در تکرار دوم بهبود پیدا نکند بهترین جواب قبلی به­عنوان جواب فعلی انتخاب می­شود و با مکانیزم انتخاب انطباقی یک همسایگی تخریب برای تغییر جواب فعلی انتخاب و الگوریتم تا یافتن بهترین جواب تکرار می­شود.

توسعه­های این مقاله نسبت به مقالات دیگر که از روش ILS استفاده کرده­اند:

1. زمانیکه روش­های همسایگی زیادی وجود دارد، بیان و بررسی لیست ممنوع برای الگوریتم جستجوی ممنوع خیلی سخت و پیچیده می­شود. بنابراین به­جای الگوریتم جستجوی ممنوع، انتخاب همسایگی انطباقی برای بهبود جواب فعلی در مرحله بهبود استفاده شده است.

2. از چندین همسایگی­های تخریب متعدد با مکانیزم انتخاب انطباقی در مرحله اختلال برای تقویت کردن عملگر متنوع تخریب استفاده شده است.

3. احتمال اینکه راه­حل بدتری انتخاب شود بستگی به تعداد دفعات انتخاب جواب­های پذیرفته دارد.

الگوریتم 2: مراحل ساختن جواب اولیه

مرحله1: مشتریان را به نزدیکترین انبار تخصیص دهید.

مرحله2: عمل صرفه­جویی را برای هر انبار  اعمال کنید

مرحله 1-2: برای هر مشتری یک مسیر مجزا درنظر بگیرید.

مرحله2-2: صرفه جویی را بصورت زیر محاسبه کنید:

مرحله 3-2: یک لیست صرفه­جویی تشکیل دهید.

مرحله 4-2: دو گره ای که بیشترین فاصله را دارند انتخاب می­کنیم . اگر برای مسیرانتخابی شرایط محدودیت­ها برقرار بود به عنوان یک مسیر شدنی انتخاب می­شود و از لیست حذف می­شود.

مرحله 3: تمام مسیرها را بررسی و ادغام می­کنیم.

ساختار همسایگی بهبود: سه نوع ساختار بهبود inter-route بین انبارهای مختلف، inter-route بین انبارهای مشابه، intera-route وجود دارد. برای بهبود جواب موثر هر یک از روش­های بهبود همسایگی inter-route ، روش­های همسایگی intra-route را تضمین می­کند. یعنی هر قید به عنوان عملگر همسایگی محسوب می­شود.

ساختار همسایگی تخریب: روش همسایگی تخریب در الگوریتم پیشنهادی برای تولید یک جواب جدید برای جستجوی متنوع استفاده می­شود. برای کشف فضاهای جواب، ساختارهای متفاوت همسایگی برای برآشفتن بهینه­های محلی بکار گرفته می­شوند. درواقع الگوریتم LNS متشکل از دو بخش است: حذف مشتریان و ورود مجدد مشتریان حذف­شده. تفاوت روش LNS پیشنهادی در این مقاله نسبت به روش سنتی در تایید ورود مجدد مشتریان حذف شده است. دو روش قرار دادن جدید پیشنهاد شده است:

1. روش قرار دادن بر اساس رقابت

2. تخصیص اول احتمالی، روش قراردادن مجدد

الگوریتم 3: روش ابتکاری قراردادن حریصانه پایه

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

الگوریتم 4: الگوریتم ابتکاری قراردادن حریصانه مبتنی بر رقابت

این الگوریتم تفاوتش با الگوریتم قبلی در این است که مجموعه مشتریان به چند زیرمجموعه تبدیل می­شوند و انتخاب از بین این زیرمجموعه ها در هر تکرار صورت می­گیرد.

ابتدا در بین تورهای تشکیل شده مختلف یک تور را به تصادف انتخاب می­کنید. آنگاه دو مسیر که بیشترین مسافت را دارند انتخاب و کمان­های مربوط به آنها را حذف می­کنید. سپس مشتریان حذف شده از مسیر را به مسیرهای دیگر که نزدیکتر هستند متصل می­کنیم. شکل (3) نحوه حذف و قرارگرفتن مجدد مشتریان و رسیدن به جوابی موثرتر را نشان می­دهد.

شکل 3- حذف مشتریان با طول قوس زیاد و جایابی در دیگر مسیرها

مکانیزم ANS: از مکانیزم انطباقی برای بهبود و تخریب روش همسایگی استفاده شده­است. با توجه به امتیاز هر یک از روش­های همسایگی از انتخاب چرخ رولت برای تصمیم­گیری راجعبه اینکه کدوم روش برای مسئله دریافت و ارسال همزمان موثرتر و موفق­تر عمل می­کند استفاده می­شود.

در الگوریتم پیشنهادی مکانیزم انتخاب همسایگی انطباقی به دو قسمت انتخاب انطباقی روش همسایگی تخریب و بهبود تقسیم می­شود. انتخاب انطباقی در روش همسایگی بهبود بدین صورت است که هر روش همسایگی بهبود توسط روش انتخاب چرخ رولت با احتمالی متناسب با کیفیت تجربی­اش، انتخاب شده­است (مثلا اگر k روش وجود داشته باشد وزن روش j ام می­شود احتمال وزن روش j تقسیم بر مجموع وزن کل k تا روش). در شروع جستجو وزن­های برابر به همه روش­های بهبود داده می­شود. اما در طول جستجو، وزن روش­ها در هر مرحله بسته به موفقیت هر یک از روش­ها به­روزرسانی می­شود. وزن هر روش از طریق سه مرحله زیر تنظیم می­شود:

مرحله1: تقسیم فرآیند جستجو به بخش­های زیادی که هر بخش شامل تکرار زیادی باشد.

مرحله 2: محاسبه امتیاز هر روش بعد از تکمیل هر بخش. درواقع زمانیکه یک روش جدید پیدا شود امتیاز h1 می­گیرد. اگر روش در الگوریتم ILS بعنوان روش بهبود انتخاب شود امتیاز h2 می­گیرد و اگر راه­حل پذیرفته شود امتیاز h3 می­گیرد.

مرحله3: در هر مرحله بهبود وزن­ها بروزرسانی می­شوند.

انتخاب انطباقی در روش همسایگی تخریب هم مثل روش همسایگی بهبود است با این تفاوت که در وزن­دهی اولیه متفاوت است. اگر بهترین راه­حل جدید بدست آید امتیاز h4 و در غیر این صورت امتیاز h5 فقط در یک صورت بعد از پذیرش روش همسایگی تخریب اعمال می­شود. روش مرحله بعد یا بطور مستقیم یا از طریق چرخ رولت انتخاب می­شود.

تابع هدف و مکانیزم تنوع

برای اینکه جستجو را تقویت کنیم در تابع هدف (1)، فاصله و حداکثر بار مجاز هر مسیر را با یکسری وزن به تابع هدف اضافه می­کنیم که باعث می­شود به جواب عملی­تر و بهتر دست پیدا کنیم.

پذیرش و توقف معیار

هرگاه بهترین راه­حل جدید در مرحله بهبود پیدا شد، جایگزین جواب فعلی می­شود و اگر این جواب قبلا پذیرفته نشده باشد، در این مرحله پذیرفته می­شود. هرگاه بعد از تکرارهای از پیش تعیین شده، راه­حل فعلی بهبود نیافت آنگاه عملگر تخریب دوباره اعمال خواهد شد. الگوریتم زمانی متوقف می­شود که تعداد مشخصی تکرار صورت گیرد.

نتایج محاسبات

در مقاله 22 تا مسئله چند انباره (2-5 انبار، 50-249 مشتری) و 28 مسئله تک انباره (50-199 مشتری) درنظر گرفته شده است. ویژگی­های این مسائل بصورت جزئی در جدول های (1) و (2) آورده شده است. هدف حل کمینه مسئله از نظر تعداد وسایل مورد استفاده و بعد مسافت طی شده می­باشد که هزینه­های ثابت و متغیر بصورت قطعی درنظر گرفته شده است. در جدول (4) نتایج حل و یافتن بهترین جواب ILS تعبیه شده در دو الگوریتم انتخاب همسایگی انطباقی ILS-ANS و انتخاب همسایگی تصادفی ILS-SNS گزارش شده است. همانطور که مشاهده می­شود الگوریتم ILS-ANS بهترین راه­حل ها را ارائه داده است در صورتیکه که الگوریتم ILS-SNS فقط در 4 تا نمونه از 22 نمونه از لحاظ زمان محاسباتی نسبت به الگوریتم انطباقی عملکرد خوبی داشته است. در جدول 5 جواب­های بهینه الگوریتم پیشنهادی نسبت به الگوریتم­های ارائه شده در مقالات قبلی محاسبه شده است و حتی میانگین تابع­هدف بدست­آمده از جواب­های الگوریتم ILS-ANS، نسبت به میانگین مقدار تابع هدف الگوریتم­های ارائه شده پیشین 10٪ بهبود داشته است و در جواب بهینه نهایی بدست آمده درصد بهبود تا 14٪ هم بهبود یافته است. درواقع این بهبود نسبت به الگوریتم­های فراابتکاری به این دلیل است که زمانیکه جواب در بهینه­های محلی گیر می­افتد باید از طریق عملگر تخریب از این بهینه محلی خارج شود درصورتیکه الگوریتم­های ابتکاری پیشین این امکان را درنظر نگرفته­اند. همچنین نتایج نشان می­دهد که عملکرد الگوریتم ILS-ANS با الگوریتم­های جستجو همسایگی بزرگ، بهینه­سازی ازدحام ذرات، بهینه­سازی مورچگان برای روش­های پیچیده برای مسائل VRPSDP رقابت می­کند.

نتیجه­گیری

• در این مقاله از یک روش ILS با مکانیزم انتخاب انطباقی در دو مرحله بهبود و تخریب استفاده کرده است و با استفاده از قوانین احتمالی انتخاب یک جواب بدتر را بر اساس تعداد تکرار برای خارج شدن از بهینه­های محلی درنظر گرفته است.

• روش پیشنهادی در مقایسه با روش­های دیگر انعطاف­پذیرتر است زیرا می­توان با شناسایی جواب اولیه و بررسی شدنی بودن جستجوی همسایگی به راحتی مسائل را حل کرد.

• در قسمت نتایج محاسبات نشان داده شده که رویکرد پیشنهادی بهتر از رویکردهای قبلی جواب داده است و جواب بهینه نسبت به حل با الگوریتم­های بهینه­سازی ذرات، مورچگان، جستجوی همسایگی بزرگ بهتر بوده است.

• برای پیشنهادات آتی می­توان به ارائه الگوریتم پیشنهادی با ویژگی­های مختلف در مرحله بهبود و تخریب برای بررسی و ارزیابی کارایی روش جستجو پرداخت.