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

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

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

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

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

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

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

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

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

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

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

تابع هدف:

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

محدودیت­ها:

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

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

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

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

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

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

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

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

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

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

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

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

  تامین­کننده­ای که در مکان k قرار دارد از مسیر مشخص شده حذف می­شود.

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

  مشتری i را با مقدار محصول جمع­شده q در مکان k در مسیر مشخص شده اضافه می­شود.

• همچنین ممکن است جای دو تامین­کننده جابه­جا شود و مسیر اولیه را تغییر دهد.

  تامین­کننده در مکان k با یک تامین­کننده جدید i با محصولات جمع­شده q جابه­جا می­شود.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

نتیجه­گیری

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

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

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

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

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