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

موضوع: جستجو همسایگی متغیر دو فاز برای حل مسئله مسیریابی موجودی چند محصولی

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

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

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

Bell و همکارانش (1983) برای اولین بار به بررسی مسائل مسیریابی موجودی پرداختن. آنxadها مسئله توزیع گاز را با تقاضای قطعی درنظر گرفتند. از روش مسئله عددصحیح مختلط برای پیدا کردم مقادیر تحویل، مجموعه وسایل نقلیه موردنیاز و زمان بازدید مشتریان استفاده کردند. Golden و همکارانش (1984) مسئله توزیع پروپان را برای یک شرکت با 3000 مشتری و تقاضای تصادفی بررسی کردند. برای حل مسئله سه الگوریتم ابتکاری پیشنهاد کردند. ابتدا با جواب بدست آمده از حل مسئله فروشنده دورهxadگر به تخمین هزینهxadهای حملxadونقل پرداختند، سپس مسیرها را بوسیله الگوریتم کلارک و رایت تعیین کردند. مسیرهای بدست آمده را به وسایل نقلیه تخصیص دادند و مسئله اصلی را حل کردند. Dror و همکارانش (1987) به بررسی یک مسئله مسیریابی موجودی با تقاضای تصادفی با هدف حداقل کردن هزینهxadهای حملxadونقل پرداختند و مسئله را با استفاده از برنامهxadریزی عددصحیح مختلط مدلسازی و حل کردند. Chien و همکارانش (1989) به مسئله مسیریابی موجودی با مقادیر محدودشده در انبار پرداخته است. آنxadها اطلاعاتی را درباره موجودی مشتریان دریافت میxadکنند. هدف مسئله رسیدن به سود ماکزیمم است در این مدل ابتدا موجودی انبارها را به مشتریان تخصیص میxadدهد و سپس مشتریxadها را به وسایلxadنقلیه تخصیص میxadدهد. Anily & Fredreguen (1990) یک مسئله توزیع با مجموعه فروشگاهxadها با تقاضای معین را درنظر میxadگیرند با استفاده از خوشهxadبندی مشتریان را به چند خوشه تقسیم میxadکنند. مقدار بهینه تحویل برای هر خوشه حداقل بین مقدار محاسبه شده از مدل اقتصادی سفارش و مدل مسیریابی وسیلهxadنقلیه ظرفیتxadدار است. Bertazzi و همکارانش (2002) دو نوع مسئله مسیریابی موجودی مختلف را با توابع هدف مختلف (حداقلxadسازی هزینه حملxadونقل/ هزینه نگهداری موجودی خردهxadفروش و یا تامینxadکننده) با هم تجزیه و تحلیل و مقایسه کردند. از یک الگوریتم ابتکاری برای حل مدل با یک وسیلهxadنقلیه و یک محصول استفاده کردند. Savelsbergh و همکارانش (2007) یک مسئله مسیریابی موجودی را با حرکت پیوسته درنظر گرفتند. در مسئله به تحویل یک محصول به مجموعه مشتریان توجه شده است. درواقع دو نوع مشتری وجود دارد، کسانی که در نزدیکی انبارها هستند و دیگر مشتریان که دورتر از انبارها قرار دارند. در این مقاله سه الگوریتم ابتکاری برای پیدا کردن مسیر و مقادیر بهینه تحویل پیشنهاد شد. Savelsbergh و همکارانش (2008) به منظور افزایش کارایی مدل خود الگوریتم GRASP را پیشنهاد کردند. Moin و همکارانش (2010) الگوریتم ژنتیک را برای حل مسئله مسیریابی موجودی چند محصوله چند دورهxadای پیشنهاد دادند. در این مقاله کران پایین و بهترین عدد صحیح مبدست آمده از فرمول برنامهxadریزی عدد صحیح مختلط را با جواب الگوریتم مقایسه کردند. در سالxadهای اخیر جستجوی همسایگی متغیر برای حل مسائل مسیریابی موجودی مورد توجه قرار گرفته است. Porovi’c و همکارانش (2012) یک مسئله توزیع سوخت با وسایلxadنقلیه چند محفظهxadای را مورد بررسی قرار دادند. آنxadها یک مدل برنامهxadریزی عددصحیح و الگوریتم جستجو همسایگی متغیر را برای حل مدل پیشنهاد کردند.

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

مسئله مسیریابی موجودی چندمحصولی شامل برآورد تقاضای قطعی از محصولات مختلف کارخانه مونتاژ در طی یک افق برنامهxadریزی است. وسایلxadنقلیه که در انبار قرار دارند، محصولات مختلف را از تامینxadکنندگان مختلف جمعxadاوری میxadکنند، هر تامین کننده یک محصول منحصر به فرد را فراهم میxadکنند و میxadتوانند توسط بیش از یک وسیلهxadنقلیه بازدید شوند. برگشت سفارش وجود ندارد. هزینه نگهداری موجودی در تامینxadکننده درنظر گرفته نشده است. افق برنامهxadریزی را برای چند دوره درنظر گرفته شده است. یه هزینه متفاوت در مقاله درنظر گرفته شده است:

• هزینه ثابت هر وسیلهxadنقلیه در هر دوره زمانی

• هزینه متغیر سفر بین دو تامینxadکننده

• هزینه نگهداری هر واحد محصول

تابع هدف:

معادله (1) هزینهxadهای ثابت و متغیر حملxadونقل و هزینهxadهای نگهداری را در کارخانه مونتاژ مینیمم میxadسازد.

محدودیتxadها:

محدودیت (2) تعادل موجودی برای هر محصول در کارخانه مونتاژ را تضمین میxadکند.

محدودیت (3) مربوط به تعادل جریان محصول و حذف زیرتور میxadباشد.

محدودیت (4) بیان میxadکند که مقدار محصولات حملxadشده توسط هر وسیلهxadنقلیه باید برابر با کل تقاضای کارخانه مونتاژ برای محصولات باشد.

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

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

محدودیت (8) بیان میxadکند که تقاضای کارخانه مونتاژ باید بطورکامل برآورده شود.

محدودیت (11) تضمین میxadکند هیچ مسیر مستقیمی از تامینxadکنندهxadها به انبار، از انبار به کارخانه مونتاژ، از کارخانه مونتاژ به تامینxadکنندهxadها وجود ندارد.

محدودیتxadهای (9)، (10)، (12) و (13) محدودیتxadهای نامنفی و عددصحیح مدل را تضمین میxadکنند.

روش ارائهxadشده و ساختار همسایگی

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

فرض کنید یک مسیر وجود دارد سه تغییر ممکن است در مسیر اولیه رخ دهد:

با توجه به سه حرکت فوق، 7 ساختار همسایگی در فضای جواب میxadتوان یافت.

انتقال همسایگی (N1)

همسایه انتقال در جواب S از طریق حذف یک تامینxadکننده از مسیرش و انتقال آن به مسیرهای مشابه و یا مسیرهای دیگر در یک دورهxadزمانی مشابه صورت میxadگیرد. همانطور که در شکل (1) مشخص است تامینxadکننده 6 از مسیر 2 به مسیر 1 در دورع زمانی مشابه حرکت کرده است.

شکل 1- انتقال همسایگی

تبادل همسایگی (N2)

زمانی اتفاق میxadافتد که یک تامینxadکننده در یک مسیر با یک تامینxadکننده دیگر در مسیری دیگر مکانxadهایشان را با هم تعویض کنند. مانند شکل (2) که تامینxadکننده 3 در مسیر اول با تامینxadکننده 6 در مسیر دوم در یک دوره زمانی مکانهاxadیشان مبادله شده است.

شکل2- تبادل همسایگی

حذف همسایگی (N3)

با حذف یک تامینxadکننده ایجاد میxadشود. برای مثال در شکل (3) با حذف تامینxadکننده 2 از مسیر 1 بوجود میxadآید.

شکل3- حذف همسایگی

درج همسایگی (N4)

با اضافه شدن یک تامینxadکننده در مسیر ایجاد میxadشود. در شکل (4)، تامینxadکننده 7 به مسیر شماره 1 اضافه شده است.

شکل4- درج همسایگی

انتقال همسایگی دورهxadای (N5)

یک همسایه از جواب S، با حذف یک تامینxadکننده از مسیر و درج آ در هر مسیری و در هر دوره زمانی بهxadدست میxadآید. در شکل (5) تامینxadکننده 5 در دوره زمانی t حذف شده و در مسیر جدیدی در دوره زمانی جدیدی قرار گرفته است.

شکل 5- انتقال دورهxadای همسایگی

جایگزین همسایگی (N6)

زمانیکه یک تامینxadکننده در یک مسیر حذف و تامینxadکننده دیگری جایگزین آن میxadشود. برای مثال در شکل (6)، تامینxadکننده 2 از مسیر 1 حذف شده و تامینxadکننده 7 جایگزین آن میxadشود.

شکل 6- جایگزین همسایگی

تبادل همسایگی دورهxadای (N7)

زمانیکه دو تامینxadکننده در دو مسیر در دو زمان متفاوت با هم تعویض شوند. در شکل (7)، زمانیکه تامینxadکننده 5 در یک مسیر در دوره زمانی t با تامینxadکننده 7 در یک مسیری در دوره زمانی دیگری جابهxadجا شوند، این همسایگی رخ داده است.

شکل 7- تبادل همسایگی دورهxadای

جستجوی همسایگی متغیر دو مرحلهxadای

در این بخش، جستجوی همسایگی متغیر دو مرحلهxadای برای مسائل IRP شرح داده میxadشود. در مرحله اول، جستجوی همسایگی متغیر VNS برای حل مسائل مسیریابی وسایلxadنقلیه ظرفیتxadدار در هر دوره زمانی برای یافتن جواب اولیه بدون درنظر گرفتن موجودی استفاده میxadشود. در مرحله دوم، با تکرار جواب اولیه را در راستای اهداف مسئله یعنی حداقلxadسازی هزینهxadهای حملxadونقل و نگهداری موجودی، بهبود میxadبخشیم.

فاز اول – ساخت جواب اولیه

الگوریتم VNS برای حل مسئله CVRP، دوره به دوره، به منظور یافتن جواب اولیه بدون درنظر گرفتن موجودی استفاده میxadشود. یعنی مقدار جمعxadآوری شده از هر تامینxadکننده در هر دوره با تقاضای کارخانه مونتاژ در آن دوره برابر است. هدف مجموعهxadای از مسیرهایی است که هزینهxadهای انتقال را به حداقل میxadرسانند. در این مرحله هزینهxadهای نگهداری صفر درنظر گرفته شده است. دو جستجوی محلی LS₁ و LS₂ را تعریف شده است. جستجوی محلی 1، از جواب اولیه شروع میxadکند و سعی میxadکند در هر تکرار با حرکت به سمت جواب همسایگی بهتر با استفاده از ساختار همسایگی N، جواب فعلی را بهبود ببخشد. در این مقاله، همسایگی N(S) با یک استراتژی بهبود مورد بررسی قرار میxadگیرد و اگر الگوریتم نتواند راهxadحل بهتری را پیدا کند، الگوریتم متوقف میxadشود. جستجوی محلی 2، با یک جواب اولیه شروع میxadشود و سعی میxadکند با دنبالهxadای از همسایگیxadها مثلا دو همسایگی N1 و N2 جواب اولیه را بهبود ببخشند. در هر تکرار بهبود اتفاق میxadافتد و جواب نهایی یک بهینه محلی نسبت به اجتماع دو ساختار همسایگی است. الگوریتم پیشنهادی این مقاله (الگوریتم 2) توسط دو بخش تشکیل شده است. یک بخش قطعی که در آن روش جستجوی محلی (LS₂) بکار گرفته شدهxadاست تا بهینه محلی را پیدا کند و بخش دیگر برای اینکه بتوان از این بهینهxadهای محلی رهایی پیدا کنیم.

فاز دوم – مرحله بهبود

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

مدیریت موجودی: مدل ریاضی

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

تابع هدف (14) هزینهxadهای موجودی کل را کاهش میxadدهد و برای کمبود یک جریمه درنظر میxadگیرد.

محدودیت (15) تضمین میxadکند که برای هر تامینxadکننده تعادل جریان محصولات برقرار باشد.

محدودیت (16) تضمین میxadکند که ظرفیت وسایلxadنقلیه نقض نشود.

محدودیتxadهای (17)- (19) متغیرهای تصمیم و نامنفی را نشان میxadدهند.

روش حل ابتکاری

یک روش ابتکاری برای تعیین مقدار محصول جمعxadآوری شده، پیشنهاد شده است. یک روش روبهxadعقب برای تعریف مقدار محصولات تحویل داده شده به هر وسیله، در هر دوره زمانی، برای برآوردن تقاضای دورهxadهای پیشین اتخاذ شده است. با توجه به اینکه چندین تامینxadکننده برای بازدید در هر دوره وجود دارند و هر تامینxadکننده ممکن است توسط بیش از یک وسیلهxadنقلیه بازدید شود، دو قانون اولویت پیشنهاد شده است. قانون اول این است که سفارشxadدهندهxadای مقدار سفارشات را تعریف میxadکند که مقدار آن محصول را تعیین میxadکند. دومین قانون، ترتیب تخصیص وسایلxadنقلیه میxadباشد. اولویت هر تامینxadکننده با یک ضریب آلفا تعیین شده است. تامینxadکننده ای در اولویت بالا قرار دارد که ضریب آلفای آن مقدار بزرگxadتری داشته باشد. هنگامیکه یک تامینxadکننده برای دوره t انتخاب میxadشود، باید وسایل نقلیه را برای بازدید به آن و جمعxadآوری محصولاتش تخصیص داده شود. با محاسبه تخمین میانگین هزینه در صورت عدم دریافت یک واحد محصول با وسیلهxadنقلیه v در دوره زمانی t، قانون اولویت را برای این تخصیص بصورت زیر تعریف میxadکنند.

بالاترین اولویت وسیلهxadنقلیه در هر دوره زمانی، جایی است که کوچکترین مقدار زیر بدست میxadآید.

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

نزول همسایگی متغیر VND

روش VND یک نوع قطعی از روش VNS است. از الگوریتم VND برای فاز دوم استفاده میxadشود و شامل ساختارهای همسایگی است. فرض کنید یک مجموعه از ساختار همسایگی بصورت زیر دارید:

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

جستجوی همسایگی متغیر

در الگوریتم 4 یک روش VND برای مرحله بهبود پیشنهاد شد. حال یک روش جایگزین بر اساس VNS پیشنهاد میxadکنیم. تعداد ساختارهای همسایگی را به 4 دسته N1، N3، N4، N6 محدود میxadکنیم. الگوریتم VNS الزاما دو مرحله دارد: یک بخش نزولی برای پیدا کردن بهینهxadهای محلی و یک بخش تکان دادن برای فرار از بهینه محلی است. در بخش نزولی ار ساختارهای محلی محدود شده استفاده میxadکنیم. در الگوریتم 5 خط 7 از این ساختارهای همسایگی به ترتیب N3، N1، N4، N1، N6، N1 استفاده شده است. در بخش تکان دادن خط 5 در الگوریتم 5، جستجوی همسایگی متغیر پیشنهادی بین دو ساختار N3 و N4 در هر تکرار متناوب است. ابتدا، میانگین هزینهxadها نگهداری را برای همه تامینxadکنندگان محاسبه میxadکنند. سپس، یک یا دو ساختار همسایگی را با احتمال p و (1-p) برای N3 و N4 انتخاب میxadکنند. تامینxadکنندگان با هزینهxadهای نگهداری کمتر از حذف میxadکنیم و تامینxadکنندگان با هزینهxadنگهداری بالاتر از هزینه میانگین نگهداری را در جای آنxadها قرار میxadدهیم. در حقیقت، میxadخواهیم محصولاتی را که هزینه نگهداری بالایی دارند را برای برآورد تقاضای کارخانه مونتاژ جمعxadآوری کنیم. همچنین به دنبال کاهش تعداد بازدیدهای برای جمعxadآوری محصولات با هزینهxadهای پایین هستیم تا فاصله کل سفر را به حداقل برسانیم(الگوریتم5).

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

مدل را بر روی نمونهxadهایی با اندازهxadهای متفاوت و دورهxadهای زمانی متفاوت بررسی و تست میxadکنیم. نمونهxadهایی در اندازه کوچک با 12 تامینxadکننده (S12Ty)، نمونه های با مقیاس متوسط با تامینxadکنندهxadهای 20 و 50 تایی (S20Ty & S50Ty) ، نمونهxadهایی در مقیاس بزرگ با 98 تامینxadکننده (S98Ty)، که y نشانxadدهنده تعداد دوره هر نمونه است. جزئیات هر نمونه در جدول (1) آورده شده است.

در مرحله اول، از یک الگوریتم VNS برای بهینهxadسازی هزینهxadهای حملxadونقل استفاده میکنیم. زمانیکه بهبودی از طریق جستجوی محلی نداشتیم الگوریتم متوقف میxadشود. زمانیکه الگوریتم متوقف شد، برای مرحله دوم یک الگوریتم VND یا VNS را برای بهبود جواب اولیه اجرا میxadکنیم. الگوریتم VND زمانیکه بهبود امکانxadپذیر نیست، متوقف میxadشود. برای الگوریتمxadهای پیشنهادی پارامترها را بصورت زیر تنظیم میxadکنیم:

• احتمال انتخاب N3 در محدوده N4 برابر 20٪ است.

• محدودیت زمانی 2000 ثانیه معیار توقف الگوریتم فرض شده است.

• برای هر مسئله نمونه الگوریتم را 10 بار اجرا میxadکنیم.

در جدول شماره (2) نتایج و تعداد وسایل نقلیه مورد استفاده برای 14 نمونه با تعداد تامینxadکنندگان N و تعداد دورهxadهای زمانی متفاوت t، با سه الگوریتم GA، 2p-VND، 2p-VNS حل و آورده شده است. نتایج بدست آمده از الگوریتم پیشنهادی را با نتایج الگوریتم ژنتیک مقایسه میxadکنیم. الگوریتم پیشنهادی جوابxadهای بهتری نسبت به الگوریتم ژنتیک به ما میxadدهد. الگوریتم 2p-VND بهترین نتایج را برای 4 نمونه از 14 نمونه و 2p-VNS بهترین نتایج را برای 13 نمونه بدست میxadآورند. در مقایسه با GA، 2p-VND همیشه بهتر عمل میxadکند، به جز در دو مورد S98T5 و S98T10. همچنین p2-VNS فقط نمونه S98T14 را بدتر از الگوریتم GA نشان میxadدهد. با توجه به نتایج میxadتوان گفت که الگوریتم 2p-VNS برای نمونهxadهای S12T5، S12T10، S12T14، S20T5، S20T10، S50T5 و S98T5 بر الگوریتم GA غالب است.

در جدول (3) حدود پایین و میزان انحراف حدود پایین با بهترین نتایج بدست آمده از الگوریتم GA گزارش شده است. همچنین حداقل، حداکثر و میانگین انحراف برای دو الگوریتم پیشنهادی نیز بعد از 10 بار اجرا محاسبه شده است. برای 12 نمونه اول، انحراف از معادله زیر محاسبه میxadشود:

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

با توجه به جدول (3)، بنظر میxadرسد که هر دو روش پیشنهادی جدید بطور قابل توجهی نسبت به الگوریتم GA از نظر کیفیت جوابxadها بهتر عمل میxadکنند. انحرافات بدست آمده در دو روش پیشنهادی در 10 بار تکرار برای هر نمونه کمتر از انحرافات در روش GA میxadباشد.

از نظر زمان محاسباتی الگوریتمxadها برای یافتن جواب بهینه، همانطور که در شکل (4) نتایج آمده است الگوریتم 2p-VNS زمان محاسباتی کمتری نسبت به الگوریتم 2p-VND و الگوریتم ژنتیک به جز در نمونه آخر S98T14 دارد.

نتیجهxadگیری

• در این مقاله، یک الگوریتم ابتکاری دو مرحلهxadای مبتنی بر جستجوی همسایگی متغیر برای مسائل مسیریابی موجودی با هدف کمینه کردن هزینهxadهای موجودی و حملxadونقل ارائه شده است.

• مرحله اول الگوریتم پیشنهادی حل مسئله مسیریابی وسایل نقلیه برای هر دوره با VNS پیشنهادی با هدف فقط کمینه کردن هزینهxadهای حملxadونقل و درواقع بدست آوردن مسیر بهینه صورت گرفت.

• در مرحله دوم مسیر بدست آمده از مرحله قبل را با استفاده از جستجوی محلی بهبود دادیم. در این مرحله از دو الگوریتم VNS و VND برای مدیریت موجودی و حداقل کردن هزینهxadهای نگهداری استفاده شد.

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

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