تعیین ترکیب و اندازه ناوگان در مساله مکانیابی-مسیریابی با در نظر گرفتن پنجره زمانی

چکیده:

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

  مقدمه:

طراحی شبکه های توزیع برای بیشتر کارخانه ها تصمیمی حیاتی می باشد زیرا برای اجرای آن نیاز به سرمایه گذاری کلان می باشد. دو نوع مهم از تصمیمات که در این فرآیند دخیل هستند به نام تعیین مکان انبارها، و طراحی مسیریابی وسیله نقلیه برای تامین تقاضای مشتریان می باشد. در مسائل مکانیابی تسهیلات کلاسیک، فرض بر آن است که هر مشتری به طور حمل و نقل مستقیم سرویس داده می شود که زمانی محسوس می باشد که میزان تقاضای مشتریان نزدیک به ظرفیت وسیله نقلیه می باشد. به هر حال موارد بسیاری وجود دارد که تقاضای مشتریان تجمیع (یک کاسه سازی) شود. در چنین مواردی مساله مکانیابی تسهیلات باید به همراه مساله مسیریابی وسایل نقلیه حل شود. ایده ترکیب مسائل مسیریابی و مکانیابی چیزی در حدود 50 سال قبل توسط وون بونتر ارائه گردید و به عنوان LRP مطرح گردید. کاربرد مسائل LRP در حوزه های مختلف نظیر توزیع غذا و نوشیدنی، تحویل بسته های پستی و طراحی شبکه مخابراتی می باشد. الگوریتمهای زیادی که بیشتر آنان ابتکاری هستند برای LRP و مشتقات آن در 50 سال اخیر ارائه شده است که شامل الگوریتمهای فراابتکاری جمعیت محور، فراابتکاری های مبتنی بر همسایگی، شبیه سازی تبرید، الگوریتم ALNS می باشد. بر اساس مقاله هاف و اندرسون، بسیاری از مسائل توزیع در دنیای واقعی، بیشتر ناوگان غیرهمگن هستند تا همگن. تعیین ترکیب و اندازه ناوگان مساله مکانیابی-مسیریابی با در نظر گرفتن پنجره زمانی (FSMLRPTW) توسط لیو و شن در سال 1999 معرفی گردید که یک مساله LRP با ناوگان ناهمگن و پنجره زمانی می باشد. الگوریتم های ابتکاری زیادی برای (FSMLRPTW) توسعه داده شده است که شامل الگوریتم ابتکاری ساخت دو مرحله ای، ابتکاری ساخت متوالی و موارد بسیار زیاد دیگر می باشد.

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

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

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

·         ما مساله FSMLRPTW را به عنوان یکی از مشتقات جدید LRP معرفی می کنیم.

·         معرفی HESA به همراه معرفی رویه های ابتکاری که مختص مساله FSMLRPTW می باشد.

·         معرفی مساله مکانیابی-ناهمگن ALNS (L-HALNS) که در بسیاری از عملگرهای آن تغییراتی ایجاد شده است که شامل تغییراتی در بخش های INITIALIZATION، PARTITION و MUTATION می باشد.

تعریف مساله:

مساله FSMLRPTW، به عنوان یک گراف کامل G=(N,A) در نظر گرفته می شود که در آن N اجتماع N0 ( انبارهای بالقوه) و NC(مکان مشتریان) می باشد و A نیز مجموعه کمانها تعریف می شوند. هر کمان یک مسافت (هزینه، زمان) غیرمنفی Cij دارد. هر مشتری یک تقاضای qi دارد و برای هر انبار بالقوه یک ظرفیت و یک هزینه ی تاسیس دارد. پارامترها و متغیرهای دیگر نیز در ادامه تعریف شده اند.

توضیح محدودیتها:

معادله (1) مربوط به تابع هدف می باشد که کمینه کردن هزینه ها می باشد. محدودیت (2) نشان می دهد که هر مشتری باید دقیقا یکبار ملاقات شود. محدودیت  (3) نشان می دهد که تعداد ورود و خروج از یک گره با هم برابر باشد. محدودیت (4) بیان می کند که تقاضای هر مشتری پاسخ داده می شود. محدودیت (5) بیان می کند که بار منتقل شده بر روی یک مسیر نباید از ظرفیت وسیله نقلیه بیشتر باشد. محدودیت (6) نشان می دهد که میزان کل بار مربوط به هر انبار، برابر با تقاضای مشتریان تخصیص داده شده به آن می باشد. محدودیت (7) تضمین می کند که بار موجود در هر وسیله نقلیه در هنگام بازگشت به انبار باید برابر با صفر باشد. محدودیت (8) و (9) محدودیت های مقداری برای متغیرهای بار می باشند. محدودیت (10) تضمین می کند که کل تقاضای تامین شده توسط یک انبار نباید از ظرفیت آن تجاوز کند. محدودیت های (11) و (12) تضمین می کنند که هر مشتری باید تنها به یک انبار و تنها به یک نوع از وسیله نقلیه تخصیص پیدا کند. محدودیت های (13)-(15) از تشکیل مسیرهای غیرقانونی جلوگیری می کند. محدودیت های (16)و (17) محدویت های پنجره زمانی را نشان می دهد. محدودیت های (18)تا (22) نشان دهنده ی دامنه متغیرهای تصمیم می باشد.

مدل ارائه شده در قسمت قبل دارای حالت دیگری نیز می باشد که در آن برخی از محدودیت ها با هم جمع می شوند و برخی از محدودیت ها نیز جداسازی می شوند. با توجه به محدودیت (29)، محدودیت های (4) تا (9) توسط محدودیت های (23) تا (29) جایگزین می شوند. همچنین با استفاده از محدودیت (32)، محدودیت های (16) و(17) با محدودیتهای (30)و (31) جایگزین می شوند. محدودیت (3) نیز تبدیل به محدودیت (33) می شود. در ادامه نیز 4 نمونه از مشتقات مساله اصلی حاصل شده است.

نابرابری های معتبر:

در این بخش ما از 4 نابرابری معتبر با اندازه ی چند جمله ای استفاده می کنیم. این موارد برای مشتقات مساله LRP توسط نویسندگان زیادی به کار گرفته شده است. اولین نابرابری برای حذف زیرتور در مساله دوره گرد استفاده شده است که برای دو نقطه توسط معادله ی شماره (34) تعریف می شود. دومین نابرابری معروف به مساله مکانیابی نیروگاه-سیکل می باشد که در معادله ی شماره (35) آمده است و برای این است که تضمین کند تا زمانی که تسهیلی باز نشده باشد نتوان مشتری را به آن تسهیل تخصیص داد. نابرابری سوم که در معادله ی (36) ذکر شده است برای همین مقاله توسعه داده شده است و نشان دهنده ی حد پایین برای تعداد مسیرهایی می باشد که از انبار شروع می شوند. و در نهایت نابرابری چهارم یک حد پایین برای تعداد انبارهای افتتاح شده ایجاد می کند که در معادله ی (37) به آن اشاره شده است.

توضیح HESA :

ساختار کلی الگوریتم توسعه داده شده در شکل زیر آمده است:

جمعیت اولیه توسط رویه INITIALIZATION که در خط اول آمده است، تولید می شود. در خط سوم دو والد انتخاب می شوند و در خط 4 توسط عملگر تقاطع فرزند جدید شکل می گیرد. در خط 5 فرزندان ایجاد شده تحت رویه PARTITION قرار می گیرند که این یعنی فرزندان در مسیرها بخش بندی می شوند. رویه EDUCATION از عملگرهای L-HALNS استفاده می کند تا فرزندان را آموزش دهد و آنها را دوباره به جمعیت برگرداند (خط 6). احتمال مرتبط با عملگرهای L-HALNS که در رویه EDUCATION استفاده می شود با استفاده از یک رویه تنظیم وزنی انطباقی (AWAP) که در خط 7 توضیح داده شده است، به روز رسانی می شود. رویه INTENSIFICATION ، با توجه به خط 8 بر روی جوابهای نخبه انجام می شود. هنگامی که فرزندان جدید اضافه می شود، جمعیت na در طول تکرار ها تغییر می کند که مقدار آن محدود به no+np می باشد. که noجمعیت ایجاد شده در ابتدای الگوریتم می باشد و no یک مقدار ثابتی می باشد که نشان دهنده ی مقدار حداکثر تعداد فرزندانی می باشد که می توانند وارد جمعیت شوند. اگر مقدار na در هر تکرار به np+no  برسد آنگاه یک مکانیزم انتخاب برای بقا (خط 9) به کار گرفته می شود. رویه MUTATION این امکان را فراهم می کند تا از جمعیت اصلی یک سری جمعیت با احتمال pm انتخاب شوند (خط 10). هنگامی که تعداد تکرارهایی که در آنها هیچ بهبودی صورت نمی گیرد به مقدار wبرسد آنگاه الگوریتم HESA به پایان می رسد (خط 11).

فاز آغازین:

ما در این بخش از رویه INITIALIZATION  در سه فاز برای ایجاد جمعیت اولیه استفاده می کنیم. در فاز اول، مشتریان به انبار ها تخصیص داده می شوند. برای هر مشتری، در ابتدا نزدیکترین انبار با توجه به فاصله محاسبه می شود و مشتریان در یک ترتیب غیر افزایشی از فاصله مرتب می شوند. سپس هر مشتری به نزدیکترین انبار که از بالای لیست شروع می شود، بدون تخطی محدودیت ظرفیت انبار تخصیص پیدا می کند. این گامها برای باقی مشتریان به صورت تکراری صورت می گیرد ( برای مشتریانی که نمی توانند به دلیل محدودیت ظرفیت انبار به نزدیکترین انبار به خود تخصیص پیدا کنند). در فاز دوم، برای هر انبار، مسیرها با استفاده از الگوریتم کلارک و رایت ساخته و همچنین بزرگترین وسیله نقلیه برای هر مسیر انتخاب می شود. در فاز سوم، اعضای جدید با استفاده از عملگرهای L-HANS که بر روی جواب اولیه اعمال می شود ساخته می شوند تا زمانی که جمعیت اولیه به np می رسد. با استفاده از دو عملگر (یک عملگر حدف و دومی یک الحاقگر حریصانه)، واگرایی در جواب اولیه صورت می گیرد. تعداد گره هایی که در فاز تخریب به طور تصادفی حذف می شوند از بازه ی مربوطه انتخاب می شوند.

بخش بندی:

هدف از این بخش، تقسیم کردن جواب به مسیرها پس از بخش های جهش و تقاطع می باشد. پیش از استفاده از این رویه، هر جواب به عنوان جایگشتی از مشتریان نشان داده می شود و از این رو می تواند به عنوان لیست Lr برای حذف استفاده شود. این رویه دارای دو فاز می باشد. در فاز اول، همه ی مشتریانِ جواب تازه تولید شده در لیست Lr قرار می گیرند. در فاز دوم، ما از یک عملگر الحاق مبتنی بر همگرایی (الحاقگر حریصانه) برای وارد کردن مشتریان لیست به بهترین مکانهای ممکن استفاده می کنیم. رویه PARTITIONیک جواب موجه برای مساله FSMLRPTW ایجاد می کند.

آموزش:

در هر تکرار، رویه آموزش به کار گرفته می شود تا کیفیت فرزندان تازه تولید شده، افزایش پیدا کند. ALNSروشی برای بهبود جواب ها می باشد که به طور پایه یک روشی ابتکاری برای بهبود می باشد که شامل دو رویه می باشد: حذف، تحت پیگیری الحاق. در فاز حذف، n’ گره مکررا توسط عملگرهای حذف مبتنی بر همگرایی حذف می شوند و در لیست حذف Lr قرار می گیرند. در فاز الحاق و درج کردن، گره های لیست Lr مرتبا در جایگاه با کمترین هزینه در جوابهای غیر کامل وارد می شوند. که برای هر دو بخش حذف و الحاق توابع صرفه جویی و هزینه توسط معادلات (38)و (39) نمایش داده می شوند.

شکل بالا مثالی از کاربرد عملگرهای حذف و الحاق می باشد.

عملگرهای حذف مبتنی بر واگرایی:

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

·         عملگر (DR): این عملگر به طور تصادفی انباری را انتخاب می کند و آن را می بندد. عملگر همه ی مشتریان این نبار را حذف می کند. این عملگر همچنین یک انبار بسته را انتخاب می کند و آن را باز می کند.

·         عملگر (DOR): به طور تصادفی یک انبار بسته را باز می کند. تعداد n’مشتری حذف شده از جواب، همانهایی هستند که بر طبق فاصله کمترین مسافت را تا این انبار را دارند.

·         عملگر (RR): این عملگر تصادفی n’مشتری را انتخاب می کند و آنها را در لیست حذف قرار می دهد.

·         عملگر (DDR): این عملگر بر اساس عملگر DR می باشد با این تفاوت که معیار آن برای باز کردن انبار بسته شده متفاوت می باشد. برای بازکردن انبار، این عملگر نزدیکترین انبار را با توجه به مورد حذف شده انتخاب می کند.

عملگرهای حذف مبتنی بر هم گرایی:

در این بخش نیز از 8 عملگر برای حذف استفاده شده است .

عملگرهای الحاق:

دو عملگر الحاق در رویه EDUCATION به قرار زیر استفاده می شوند:

ü      عملگر (GIO): این عملگر بهترین جایگاه ممکنه برای همه ی گره های موجود در Lr راپیدا می کند. محاسبات مربوط به هزینه بر اساس مسافت می باشد. عملگر الحاق مرتبا برای همه ی گره های موجود در Lr به کار گرفته می شود.

ü      عملگر (GINFO): این عملگر نوعی از عملگر بالایی می باشد که عملگر بالایی را از طریق معرفی درجه آزادی در انتخاب بهترین مکان الحاق برای برای یک گره توسعه می دهد.

جهش:

در این بخش یک رویه MUTATION برای افزایش واگرایی در جواب ها در طول تکرارها معرفی می کنیم. در این رویه از احتمال pm استفاده می شود. هر عضو به جز اعضای نخبه به طور تصادفی انتخاب می شود. یک عملگر حذف مبتنی بر واگرایی و عملگر GINFO به منظور واگرایی اعضای انتخاب شده استفاده می شوند. از این دو عملگر برای تغییر جایگاه تعداد مشخصی از گره ها استفاده می شود.

تحلیل نتایج:

جدول زیر نشان دهنده ی اطلاعات 3 زیر مسئله و مساله اصلی است که برای مثالهای مختلف به کار گرفته شده است و زمان های اجرا برای آن نشان داده شده است. اطلاعات مربوط به این 4 نوع مساله در زیر آمده است: