مسئله مسیریابی – بررسی مقاله هفتم

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

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

مقدمه

مسئله مسیریابی وسایل­نقلیه یک مسئله بهینه­سازی ترکیبی است که در بسیاری از مسائل طراحی و مدیریت سیستم­های توزیع مطرح می­شود. مسئله VRP کلاسیک را به­عنوان مسئله مسیریابی وسیله­نقلیه ظرفیت­دار CVRP نیز مطرح می­کنند که هدفش تعیین مسیرهای وسایل­نقلیه همگن است که در یک انبار مرکزی مستقر هستند و باید تقاضاهای معین مجموعه­ای از مشتریان را برآورد سازند. هدف طراحی مسیر با کمترین هزینه است. مفروضات مسئله کلاسیک به شرح زیر هستند:

1. هر مسیری که توسط یک وسیله نقلیه انجام می­شود باید از انبار شروع شود.

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

3. مقدار کالای در حال جریان در هر مسیر (تحویل دادنی/ جمع­آوری شده) باید از ظرفیت وسیله­نقلیه تخصیص یافته به آن مسیر تجاوز نکند.

پارامترهای مسئله (مقادیر قابل­تحویل/ جمع­آوری شده) برای هر گره از مشتری، ثابت و معین است. اما زمانیکه نوسانات فصلی در عرضه و تقاضا اتفاق می­افتد کیفیت برنامه مسیریابی پایین می­آید. در مقاله حاضر میخواهیم کیفیت را بصورت مطلوب نگه داریم. ایده مقاله از جمع­آوری شیر و توزیع مجدد در صنعت لبنیات Quebec (Dayarian et al. 2015) گرفته شده است. مسیریابی مربوط به جمع­آوری یک محصول معین از تسهیلات تولیدکننده و سپس توزیع به کارخانه­های فرآوری می­باشد.مسیرها باید به­گونه­ای طراحی شوند که تقاضای کارخانه­ها کاملا برآورده شود. فرض شده است که تولید روزانه، تقاضای کل کارخانه را برآورد می­سازد. Dayarian و همکارانش (2015) یک مدل VRP چند دوره­ای با نوسانات فصلی مدلسازی کردند و یک راه­حل دقیق بر اساس رویکرد شاخه-قیمت پیشنهاد دادند.

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

روش­های فراابتکاری ALNS، روش­های مبتنی بر جمعیت، الگوریتم شبه­سازی تبریدؤ الگوریتم ژنتیک، الگوریتم تکاملی و ... برای حل مسائل VRP در مقالات متفاوت مورد استفاده قرار می­گیرند. Ribeiro & Laporte (2012) الگوریتم ALNS را برای مسائل مسیریابی ظرفیت­دار تجمعی CCVRP ارائه دادند. در این مسائل زمان ورود مشتریان مهم می­باشد و هدف حداقل کردن کل زمان رسیدن به مشتریان است. Hemmelmayr و همکارانش (2012) الگوریتم ALNS را برای مسئله مسیریابی وسیله نقلیه دو سطحی 2E-VRP و مسئله مکانیابی مسیریابی LRP پیشنهاد کردند. نویسندگان از علاوه بر استفاده از غملگرهای موجود یکسری عملگر جدید طراحی کردند. Demir و همکارانش (2012) از الگوریتم ابتکاری برای حل مسئله مسیریابی آلوگی استفاده کردند. مسئله PRP الگوریتم پیشنهادی خود را برای دو زیرمسئله مسیریابی وسیله­نقلیه با پنجره زمانی VRPTW و مسئله بهینه­سازی سرعت بکار برد. VRPTW با استفاده از الگوریتم ALNS و مسئله بهینه­سازی سرعت با استفاده از یک چندجمله­ای حل شدند. در الگوریتم ALNS پیشنهادی از عملگرهای گذاشت و برداشت جدید استفاده کرده است تا بتواند کیفیت راه­حل را بهبود بخشد و نتایج نشان­دهنده اثربخشی الگوریتم در نمونه­هایی با 200 گره بوده است. Renaud و همکارانش (2013) یک مسئله تحویل و بازگشت را مطرح کردند. همچنین از الگوریتم ALNS با ارائه عملگرهای تخریب جدید از نقاط انتقال استفاده کردند. رویکرد پیشنهادی در دنیای واقعی برای مسائل مسیریابی حمل­ونقل افراد معلول اعمال شد. Adulyasak و همکارانش (2014) یک الگوریتم ابتکاری کارآمد را با استفاده از ALNS و همچنین تکنیک­های جریان شبکه برای حل مسئله مسیریابی تولید ارائه دادند. آن­ها برای پیاده سازی الگوریتم ALNS در زمینه مسیریابی تولید از ایده­هایی که توسط Coelho و همکارانش (2012) ارائه شد، الهام گرفتند. از الگوریتم ALNS برای مدیریت متغیرهای دودویی و از یک مدل جریان شبکه برای مدیرت متغیرهای دیگر استفاده شد. در نهایت الگوریتم پیشنهادی به عنوان موثرترین الگوریتم در حوزه مسیریابی تولید شناخته شد. Mancini (2015) یک مسئله مسیریابی وسیله­نقلیه قدرتمند را که چند دوره­ای و چند انباره بود مطرح کرد و برای حل مدل از الگوریتم ALNS با عملگرهای تخریب جدید استفاده کرد. تحقیقات دیگر مسیریابی در زمینه­های جمع­آوری ضایعات روغن­های زیستی برای تولید بیودیزل، جمع­آوری روغن زیتون و ... برای مسیریابی حمل­ونقل ضایعات و مواد قابل تجدید انجام گرفته است. Elbek & Wohlk (2016) یک مورد مطالعاتی درحوزه مدیریت زباله­های مسکونی را درنظر گرفتند که در آن شهروندان شیشه­ها و کاغذها را برای بازیافت به کیوسک­های کوچکی که در چند نقطه جمع­آوری قرار گرفته­اند، میفروشند. کیوسک­ها توسط وسایل­نقلیه تخلیه و به انبارها و مراکز بازیافت منتقل می­شوند. یکی از تفاوت­های این مسئله با مسئله MPVRPSF این است که تقاضای مربوط به تسهیلات وجود ندارد ولی انبارها دارای ظرفیت ذخیره­سازی محدودی هستند. Lahrichi و همکارانش (2013) شبکه حمل­ونقل لبنیات را بررسی کردند. آن­ها مسئله را با درنظر گرفتن زمان تحویل کارخانه، ظرفیت وسایل­نقلیه مختلف، تعداد مختلف وسیله­نقلیه در هر انبار و چند دوره­ای و چندانباره مدلسازی کردند و با استفاده از الگوریتم جستجوی ممنوع به حل مدل پرداختند. Dayarian و همکارانش (2015) به ارائه یک الگوریتم شاخه و قیمت برای برنامه­ریزی حمل­ونقل مواد لبنی با درنظر گرفتن پنجره زمانی تخصیص داده شده به هر تولیدکننده و سطح تولید ثابت در افق زمانی، پرداختند. مسائلی که به مسئله مورد مطالعه در این تحقیق نزدیک هستند مسائل مسیریابی وسیله­نقلیه دوره­ای یا چند دوره­ای است که درواقع مشتریان خدماتی درخواست می­دهند، که میتوانند در طول یک افق زمانی (چندین دوره) دریافت کنند. همچنین ممکن است در برخی از مقالات برای تعداد روزهایی که می­توان یک مشتری ملاقات و سرویس­دهی شود را با تعیین یک حد مجاز محدود کرد.

نوآوری­های مقاله

• در این مقاله به اینکه راه­حل سریع و کارآمد ارائه شود توجه شده است بنابراین برای مسئله MPVRPSF رویکرد حل براساس چارچوب جستجوی همسایگی بزرگ انطباقی ALNS طراحی شده است.

• برای ارزیابی کیفیت روش مجموعه­ای برای حدود بالا و پایین برای روش چند­دوره­ای محاسبه و جواب بدست آمده با روش ALNS با این حدود مقایسه شده است.

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

تعریف مسئله

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

شکل 1- تغییرات عرضه بر روی مسیر وسیله­­نقلیه

چارچوب راه­حل پیشنهادی ALNS

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

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

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

عملگرد گذاشت: الگوریتم عملگر گذاشت با استفاده از ورودی­های لیست مشتریانی که در مرحله برداشت از مسیر حذف شده بودند و با استفاده از جواب کاهش یافته و تعیین ماکزیمم تکرار، با استراتژی­های مشخصی به­عنوان مثال انتخاب حریصانه بهترین مکان را برای مشتری حذف شده از مسیر پیدا می­کندو در نهایت یک جواب جدید ارائه می­دهد.

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

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

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

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

• لیست مسیر اختصاصی: هر مسیر یک شماره دارد تمام مشتریان که در مسیر 1 قرار می­گیرند در این فهرست عدد 1 را می­گیرند.

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

شکل 2- نمونه جواب از یک مسئله مسیریابی

فضای جستجو

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

مقدار ƞ در ابتدا برابر یک است. اگر تعداد جواب­های غیرمجاز بیشتر از d_max باشد ضربدر 2 می­شود و اگر تعداد جواب­های غیرمجاز کمتر از d_min شود بر 2 تقسیم می­شود.

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

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

موتور جستجوی انطباقی

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

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

1. δ₄: عملکرد عملگر منجر به بهترین جواب جدید می­شود.

2. δ₃: عملکرد اپراتور منجر به جواب بهتری نسبت به جواب فعلی می­باشد اما بهترین جواب نیست.

3. δ₂: جواب جدید معیارهای پذیرش را دارد و در مجموعه بهترین جواب­های شدنی قرار می­گیرد.

4. δ₁: جواب جدید معیارهای پذیرش را دارد ولی در مجموعه جواب­ها نشدنی قرار می­گیرد.

تخریب ابتکاری

 4 عملگر پرکاربر در ادبیات موضوع که در این مقاله به آن­ها توجه شده است، بصورت زیر می­باشند:

1. حذف بدترین: گره­هایی با بدترین مکان چه از لحاظ هزینه چه بعد مسافتی حذف شده و در یک لیست سیاه قرار می­گیرند.

2. حذف مسیر: یک مسیر به تصادف انتخاب می­شود و تمام گره­های موجود در آن مسیر حذف می­شوند. البته ممکن است مسیر حذف شده بر اساس معیارهای دیگری انتخاب شود.

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

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

در مقاله 6 عملگر برداشت زیر پیشنهاد شده است:

1.  حذف مبتنی بر هزینه گره

2.  حذف مبتنی بر هزینه مسیر

3. حذف جفتی

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

5. حذف Depot-producer-related: گره­هایی را شناسایی می­کنند که ممکن است به انبار منتقل شوند. وزن به هر جفت گره و انبار تخصیص داده می­شود. یه لیست از هر جفت گره و انبار تهیه می­شود و به هر کدام وزنی داده می­شود. از هر جفت گره و انبار با کمترین وزن شروع می­کنیم و با احتمال زیر حذف می­کنیم:

   

6. حذف Plant-producer-related: حذف گره­های تولید بر اساس وزن گره و کارخانه­ در عملکرد گذشته­شان

بازسازی ابتکاری

2 عملگر گذاشت زیر درنظر گرفته شده است:

1. گذاشت بهترین- اولین

2. گذاشت با تاسف

عملگر گذاشت حداقل تقاضای از دست رفته از فرمول زیر محاسبه می­شود:

کران بالا و پایین جواب

برای ارزیابی عملکرد بالا و پایین الگوریتم پیشنهادی کران بالا و پایین تابع هدف را بدست می­آوریم. هزینه­های مسیر بصورت زیر نوشته می­شوند.

برای هر جواب شدنی C(X) یک کران بالا برای جواب مطلوب مسئله چند دوره­ای و F(X)، یک کران پایین حساب می­شود. درواقع باتوجه به حداقل تعداد وسایل­نقلیه می­توانیم هزینه کل را بر اساس معادلا (16) بدست آوریم.

مدلسازی ریاضی

تابع هدف:

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

محدودیت­ها:

محدودیت­های (19) و (20) تضمین می­کنند  که ظرفیت وسای­نقلیه رعایت شود.

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

محدودیت (22) تضمین می­کند که تقاضای کارخانه باید برآورده شود.

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

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

برای هر دوره محدودیت­های (25)- (27) تعداد مکان­های شکست برای هر وسیله­نقلیه را تعیین می­کنند.

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

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

محدودیت (30) متغیرهای باینری را تضمین می­کنند.

محدودیت­های (18) تا (30) مدل ممکن است منجر به افزایش مقدار تابع هدف بشوند. زمانی این اتفاق رخ می­دهد که در دوره زمانی مختلف هر دو شکست در نزدیک­تری گره به کارخانه باشند.

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

تعداد تولیدکننده در رنج 40 تا 200، هر نمونه 4 یا 5 دوره زمانی و 5 سناریوی مختلف درنظر گرفته شده است. نمونه­ها از لحاظ توزیع وزن و سطح SRT متفاوت هستند. جزئیات در جدول (2) آمده است. تغییرات در پارامترها بر عملکرد یک الگوریتم تاثیرگذار است. افزایش پارامتر به میزان قابل توجهی دقت الگوریتم را پایین می­آورد. یک روش دو مرحله­ای برای تنظیم پارامترها درنظر گرفته­ایم. در فاز اول، پارامترهایی که تاثیر بیشتری بر عملکرد الگوریتم دارند تنظیم می­شوند. در فاز دوم، پارامترهایی با حساسیت کمتر با آزمایش سعی و خطا تنظیم می­شوند. پارامترها بر اساس اولویت و از طریق الگوریتم Opal تنظیم می­شوند. این الگوریتم درواقع شامل یک ماتریس است که حدود پایین و بالای هر پارامتر را به­عنوان ورودی می­گیرد و ارزش پارامتر را بر اساس معیار عملکرد آن­ها تعیین می­کند. برای تعریف معیارهای اندازه­گیری Opal آزمایش­هایی در نمونه­هایی با 40-200 تولید­کننده، 2-6 انبار و کارخانه انجام شده است. در هر بار تکرار الگوریتم مقدار میانگین تابع هدف برای هر نمونه در 5 بار اجرا می­شود. یک جواب اولیه و یک دمای اولیه تنظیم شده است. تنظیم دمای اولیه بگونه­ای است که اجازه می­دهد الگوریتم جواب­هایی که تا 5٪ از جواب فعلی بدتر هستند هم با احتمال 50٪ بپذیرد. برای بررسی ارزیابی عملگرهای مختلف مقایسه براساس بهترین مقدار تابع هدف، مقدار میانگین هزینه­های مسیریابی و درصد زمان پردازش صورت می­گیرد. نتایج نشان می­دهد با بررسی این معیارها همه عملگرها کارا هستند. اما تغییرات قابل ملاحظه­ای بین مقادیر حداقل و حداکثر احتمال انتخاب عملگرها (مثل عملگر برداشت depot-producer-related با عملگر گذاشت باتاسف یا عملگر برداشت مرتبط با هزینه مسیر با عملگر گذاشت باتاسف) مشاهده می­شود. بر اساس نتایج جدول 6، مشاهده می­شود که عملگر گذاشت باتاسف نسبت به دیگر عملگرهای گذاشت بهتر عمل می­کند.

جفت­شدن عملگرها شاید کیفیت را به دنبال نداشته باشد اما ای امکان را به ما می­دهد که در کل زمان محاسباتی را بطور میانگین به میزان 11.88 تا 30.07٪ بهبود ببخشد. عدم وجود جستجوی محلی در الگوریتم باعث کاهش 1.28-0.02٪  از مقدار بهترین جواب و کاهش 1.08- 0.03 ٪ از مقدار میانگین­ جواب­های بدست آمده در 5 تکرار با 40 تا 200 تولیدکننده می­شود. جستجوی محلی همچنین باعث افزایش زمان محاسبات از 0.24 تا 10.23 ٪ می­شود اما بدلیل کیفیت جواب­ها از افزایش زمان محاسبات چشم­پوشی می­کنیم. الگوریتم پیشنهادی همانطور که در جدول 8 گزارش شده است، بهترین راه­حل­ها را نسبت به مقاله Pisinger & Ropke (2007) ارائه دادند که 0.76 تا 4.76 ٪ بهبود در جواب­ها دیده می­شود. افزایش ارزش میانگین انحراف هزینه مسیریابی از بهترین ALNS در مقایسه با نمونه­های 40-50 تولیدکننده نشان­دهنده پیچیدگی این موارد است. نتایج بدست آمده نشان می­دهد برای موارد 40 و 50 تولیدکننده، کاهش قابل توجهی در زمان محاسباتی نسبت به 60 تولیدکننده داشته­اند. بطورکلی افزایش تعداد انبارها و کارخانه­ها زمان محاسبات را افزایش می­دهد.

نتیجه­گیری

• یک مسئله حمل­ونقل از طرح­های تاکتیکی بخش جمع­آوری شیر با درنظر گرفتن تغییرات و نوسانات در عرضه آن مورد بررسی قرار گرفت و مدل مسیریابی چند دوره­ای مدلسازی شد. از الگوریتم ALNS برای حل مدل استفاده کردند.

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

• درحالیکه الگوریتم پیشنهادی در این مقاله تا حدودی خاص می­باشد. شاید بتوان از الگوریتم پیشنهادی برای مسائل VRP پیچیده استفاده کرد.

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