مسیریابی وسیله نقلیه- بررسی مقاله دهم

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

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

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

مسائل مسیریابی تولیدی بیشتر مربوط به مسیریابی موجودی است زمانیکه نیازی به تصمیم­گیری تولیدی در سطح کارخانه/تامین­کننده نباشد. در این مقاله به ارائه یک الگوریتم ابتکاری چندمرحله­ای پرداخته­ایم که فاز اول الگوریتم ارائه شده براساس ایده سفر پیشین است که در مقالات Pinar & Sural (2006) و Solyali & Sural (2011) برای حل یک وسیله­نقلیه در مسائل مسیریابی موجودی ارائه شد. در این مقاله این ایده مسیرهای پیشین برای چندین وسیله­نقلیه گسترش داده شده است. در مرحله اول این است که یک دنباله ثابت از همه خرده­فروشان برای همه مسیرها که وسیله نقلیه دنبال می­کند تا به همه خرده­فروشان کالا عرضه کند و خرده­فروشی نباشد که بازدید نشده باشد. فاز اول از طریق مسئله فروشنده دوره­گرد (TSP) حل می­شود. در مرحله دوم، با استفاده از توالی بدست آمده یک مدل برنامه­ریزی عدد صحیح را برای مسئله فرمول­بندی می­کنیم و مثلا چندین مسئله TSP را با وسایل نقلیه ظرفیت­دار درنظر می­گیریم بنابراین در مرحله دوم به حل مسئله مسیریابی وسیله نقلیه ظرفیت­دار می­پردازیم و یا اینکه در مرحله سوم مسئله فروشنده دوره­گرد برای هر دوره با توجه به تعداد وسایل نقلیه موردنیاز در آن دوره برای دستیابی به مسیرهای وسیله­نقلیه بهینه حل می­کنیم. ممکن است در پایان مرحله سوم مسیرهای بدست آمده در مورد تعداد محدودی از وسایل نقلیه نامطلوب باشد. بنابراین در مرحله چهارم، سعی کردیم یک راه­حل امکان­پذیر و بهبود یافته با بهره­گیری از ایده پیشنهادی در مقالات Archetti و همکارانش (2012) و Coelho & Laporte (2013) برای مسیریابی موجودی بدست آوریم. بطور کلی، ما به یک مسئله برنامه­ریزی عددصحیح مختلط برای بدست آوردن مسیرهای وسایل نقلیه می­پردازیم و اجازه عملگر­های گذاشت و برداشت خرده­فروشان را در مسیرهای موجود می­دهیم. در فاز پنجم، مسئله TSP را برای هر دوره و هر وسیله­نقلیه و مسیرهای بهبودیافته از مرحله قبل حل می­کنیم.

نوآوری مسئله

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

مدلسازی مسئله

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

• یک سیستم تولید-توزیع شامل یک کارخانه تک محصولی و n خرده فروش در طول افق زمانی T را درنظر بگیرید.

• هر خرده­فروش در هر دوره زمانی با تقاضای مشتریان خارجی D_ij روبه­رو است و ممکن است این تقاضای را در انبار نگهداری کند تا بدون نیاز به پشتیبانی تقاضا را پاسخ بدهد.

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

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

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

محدودیت­ها: محدودیت­های (2) و (3) معادلات تعادل جریان در کارخانه و خرده­فروشان را تضمین می­کنند.

محدودیت (4) تضمین می­کند کل محصولات تولیدی در کارخانه از ظرفیت تولید بیشتر نشود و تولید درصورتی امکان­پذیر می­باشد که هزینه­ثابت لازم پرداخت شود.

محدودیت (5) برای محدود کردن ظرفیت ذخیره­سازی و نگهداری موجودی می­باشد.

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

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

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

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

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

روش حل مسئله

الگوریتم ابتکاری چندمرحله­ای پیشنهادی در این مقاله به 5 مرحله تقسیم شده است. چارچوب کلی و مراحل که باید طی کنیم بصورت زیر است:

تمام مراحل بالا بر مبنای مدل­های ریاضی فرمول­بندی و حل شده­اند که در زیر شرح داده شده­اند.

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

همچنین محدودیت­های (9) تا (12) حذف شده و محدودیت­های (18) تا (20) جایگزین آن­ها می­شوند.

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

 محدودیت­های (22) و (23) تعادل موجودی­ها را در خرده­فروشی و کارخانه تضمین می­کند.

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

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

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

محدودیت (27) تعداد کل برداشت­ها و گذاشت­ها را توسط L برای هر دوره و مسیری محدود می­کند. درواقع یعنی ممکن است تعداد برداشت و گذاشت­ها و احتمال آن­ها در یک مسیر زمانیکه زیاد شود، هزینه­های محاسبه شده و هزینه توزیع مسیر را با دقت زمانیکه در هر مسیر یک برداشت و گذاشت داریم محاسبه نکند.

محدودیت (28) و (29) متغیرهای نامنفی و باینری را مشخص می­کنند.

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

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

برای انجام تست 6 دسته A1,A2,A3,B1,B2,B3 تعریف شده است که هر دسته دارای تعدادی نمونه برای آزمایش است. تعداد خرده­فروشان، تعداد دوره، تعداد وسایل نقلیه و ... در جدول (2) آمده است. ما نتایج محاسباتی خود را با نتایج الگوریتم­های ابتکاری IM-VRP و IM-MultiTSP ارائه شده در مقاله Absi و همکارانش (2015) و الگوریتم جستجوی همسایگی بزرگ انطباقی ALNS در مقاله Adulyasak و همکارانش (2014) مقایسه کردیم. هر یک از نمونه­های A1-A3 از چهار کلاس تشکیل شده است. 120 نمونه در کلاس اول قرار گرفته و بقیه با استفاده از نمونه­های این کلاس تولید می­شوند. نمونه­های کلاس دوم هزینه تولید متغیر ده برابر بزرگتر از کلاس­بندی اول است. نمونه­های کلاس سوم درارای هزینه توزیع پنچ برابر بیشتر از نمونه­های کلاس اول است. در نهایت نمونه­های کلاس چهارم، هزینه­های موجودی را درنظر نگرفته اند. زمانیکه در پایان مرحله سوم هیچ جواب شدنی بدست نیامده باشد λ=1 قرار می­دهیم. همچنین برای تعیین مقدار L یک آزمایش اولیه انجام دادیم و مقدار آنرا از 3 تا 9 و بینهایت برای بررسی تاثیر آن­ها بر کیفیت جواب ارزیابی می­شوند. 20 نمونه را بصورت تصادفی از هر 4 کلاس در مجموعه A2 انتخاب می­کنیم. بنابراین در کل 80 نمونه از مجموعه A2 از بین 480 نمونه انتخاب شده­اند. میانگین مقدار تابع هدف نمونه­ها در بازه 448790.7 تا 448808.0 قرار گرفته­اند. بهترین جواب زمانی بدست آمد که L=6 در فرمول IF در فاز چهارم درنظر گرفته شده بود. برای محدود کردن زمان محاسباتی آنرا 1800 ثانیه و درصد شکاف را 0.01٪  بین بالاترین حد و پایین ترین حد برای حل معادله IF در مجموعه A2 و A3 درنظر گرفتند. فرمول IF بصورت بهینه در مجموعه A1 حل شد و فرمول F’ در تمام نمونه­ها بصورت بهینه حل شدند.

خلاصه نتایج محاسباتی مجموعه A1-A3 در جدول (3) آماده است. ستون اول نشان­دهنده نام الگوریتم ابتکاری اجرا شده می­باشد، برای هر الگوریتم مقدار میانگین تابع هدف بدست آمده از 480 نمونه محاسبه شده است. همچنین برای هر الگوریتم تعداد دفعاتی که الگوریتم توانسته است مقدار بهینه (مینیمم) را برای تابع هدف پیدا کند آورده شده است. مجموعه A1 دارای 14 خرده­فروش، مجموعه A2 دارای 50 خرده­فروش و مجموعه A3 دارای 100 خرده­فروش می­باشد. روش حل بهینه در مجموعه A1 (برای نمونه­هایی با یک وسیله نقلیه) در مقاله Ruokokoski و همکارانش (2010) الگوریتم شاخه و کران بوده است. دو روش دیگر استفاده شده IM-VRP و IM-MultiTSP و ALNS نیز در مقالات بکار رفته شده است. در جدول شماره (4) و (5) نتایج حاصل از جزئیات نتایج حاصل از الگوریتم­های IM-MS، ALNS و 5P گزارش شده است.نتایج محاسباتی نشان می­دهند که 5P بهترین نتیجه را از لحاظ درصد شکاف متوسط بین مقادیر حل ابتکاری و مقدار حل بهینه و زمان محاسباتی، برای همه کلاس­ها به جز کلاس چهارم ارائه می­دهد. میانگین درصد شکاف با توجه به بهترین راه­حل های شناخته شده و متوسط زمان محاسباتی برای مجموعه A2 و A3 به ترتیب در جداول (6) و (7) ارائه شده است. در جدول (6) مشاهده می­شود که درصد شکاف متوسط الگوریتم 5P با توجه به بهترین مقادیر جواب بدست آمده، در مقایسه با سه الگوریتم دیگر، کمترین است. از لحاظ محاسباتی نیز در مجموعه A2 سریعتر به جواب رسیده است. درحالیکه بعد از آن ALNS در مجموعه A3 به جواب بهینه در کمترین زمان رسیده است که در جدول (7) نشان داده شده است.اگرچه در مجموعه A3 الگوریتم 5P نیز به زمان متوسط حدود 2.2 دقیقه دارد و این زمان بیشتر از الگوریتم IM-VRP است ولی در نمونه­های بزرگ مسیریابی تولید در مقیاس بزرگ در کمتر از 4 دقیقه به جواب می­رسیم. متوسط زمان محاسباتی در هر فاز از الگوریتم پیشنهادی در جدول (8) آورده شده است. ستون اول نشان­دهنده مجموعه نمونه است و بقیه ستون­ها زمان­های محاسباتی موردنیاز در هر مرحله از 5P را تعیین می­کند. البته فرمول IF در مرحله 4 در مجموعه A3 با بزرگترین IG=0.12% حل می­شود. به جز زمان­های محاسباتی فازهای 2 و 4 در 5P بقیه زمان­ها برای مجموعه­ها قابل مقایسه هستند.

یک تحلیل حساسیت روی 6 مثال با 30 نمونه روی مجموعه B1 انجام دادیم تا بهترین جفت مقدار λ و L را بدست آوریم. بر اساس این آزمایش­ها بهترین مقدار L برای فاز دوم مقدار یک و L برابر با بینهایت برای فاز چهارم تعیین شد. خلاصه نتایج محاسباتی در جدول (9) گزارش شده است. در ستون اول نام الگوریتم و در ستون بعدی تعداد دفعاتی که الگوریتم بهترین جواب را می­تواند پیدا کند نوشته شده است.جدول (10) میانگین درصد شکاف را نشان می­دهد. بر اساس جدول (9) و (10) نشان می­دهد که در مجموعه­های B1، B2 الگوریتم پیشنهادی چه از نظر یافتن بهترین جواب چه از نظر زمان محاسبات عملکرد بهتری نسبت به الگوریتم­های قبلی داشته است. جدول (11) میانگین زمان محاسباتی سه مجموعه B را برای الگوریتم­های متفاوت نشان می­دهد.

نتیجه­گیری

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

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