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

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

چکیده:

در این مقاله به بررسی مساله مسیریابی وسیله نقلیه ترکیبی که تعمیمی از مساله مسیریابی وسیله نقلیه سبز است، می‌پردازد. ما در این مقاله بر روی وسایل نقلیه‌ای که از منابع انرژی ترکیبی استفاده می‌کنند، تمرکز می‌کنیم و برای کمینه کردن هزینه کل مسافرت با این وسایل نقلیه، یک مدل ریاضی را توسعه می‌دهیم. بنابراین مدل، استفاده از هر دو نوع انرژی سوخت و الکتریکی با توجه به در دسترس بودن مراکز شارژ الکتریکی و ایستگاههای سوختگیری در نظر می‌گیرد. در این مقاله، شبیه‌سازی تبرید با یک استراتژی شروع مجدد برای حل این مساله استفاده می‌شود و شامل دو نسخه می‌باشد. نسخه اولیه، احتمال پذیرش بدترین جواب را با استفاده از تابع بولتزمان تعیین می‌کند. نسخه دوم، احتمال پذیرش بدترین جواب را با استفاده از تابع کوشی تعیین می‌کند. الگوریتم تبرید شبیه سازی ارائه شده در این مقاله، ابتدا با داده‌های معیار از مساله مسیریابی وسیله نقلیه با ظرفیت محدود بررسی می‌شود که نشان‌دهنده‌ی این قضیه است که به خوبی عمل می‌کند و کارایی آن را در حل مسائل مسیریابی وسیله نقلیه با ظرفیت محدود تایید می‌کند. تحلیل‌ها نشان می‌دهد که تابع کوشی در مقایسه با تابع بولتزمان ترجیح داده می‌شود و اینکه شبیه‌سازی تبرید با یک استراتژی شروع مجدد نسبت به شبیه‌سازی تبرید بدون یک استراتژی شروع مجدد، عملکرد بهتری دارد. ما از تابع کوشی برای حل مساله مسیریابی وسیله نقلیه ترکیبی استفاده می‌کنیم. آزمون‌های عددی نشان‌ می‌دهند که نوع وسیله نقلیه و تعداد ایستگاه‌های شارژ الکتریکی تاثیر بسیار زیادی بر روی کل هزینه‌ی سفر دارد.

 مقدمه:

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

این مقاله، مایل است تا مساله مسیریابی ترکیبی به عنوان توسعه‌ای از مساله مسیریابی سبز را مطرح کند. در این مقاله یک محدودیت زمانی و دو نوع منبع مصرفی برای سوخت در نظر گرفته شده است: الکتریسیته و سوخت. با توجه به NP-Hardبودن مساله، برای حل می‌توان از روش‌های ابتکاری و فراابتکاری استفاده نمود که ما در این مقاله از روش شبیه سازی تبرید با استراتژی شروع مجدد استفاده می‌کنیم.

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

·         ارائه نوع جدید از مساله مسیریابی وسیله نقلیه به نام مسیریابی وسیله نقلیه ترکیبی، که توسعه‌ای از مساله مسیریابی وسیله نقلیه سبز که توسط اردوغان و میلر-هوک ارائه شده است، می‌باشد.

·         برای حل، از روشی استفاده می‌شود که توسعه‌ای از شبیه‌سازی تبرید به نام شبیه‌سازی تبرید با استراتژی شروع مجدد می‌باشد که شامل دو نسخه می‌باشد: نسخه اولیه، احتمال پذیرش بدترین جواب را با استفاده از تابع بولتزمان تعیین می‌کند. نسخه دوم، احتمال پذیرش بدترین جواب را با استفاده از تابع کوشی تعیین می‌کند.

مرور ادبیات:

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

 تعریف مساله

مساله مسیریابی وسیله نقلیه ترکیبی، به‌صورت شرکت‌هایی که تعدادی از وسایل نقلیه ترکیبی را برای خدمت رسانی به مشتریان یا  نهاد‌های دیگر به کار می‌گیرند و در یک منطقه وسیع جغرافیایی واقع شده است، نمایش داده می‌شود. هدف از مساله مسیریابی ترکیبی پیدا کردن حداکثر mتور که از انبار شروع می‌شود و به انبار برمی‌گردد. هر تور توسط یک وسیله نقلیه ترکیبی سرویس داده می‌شود و از تعدادی از رئوس شامل مشتریان و مراکز منابع انرژی نوع Z(Sz) ardوشی در مقایسه با تابع بولتزمانزمانی که نیاز است ملاقات می‌کند. هر مشتری باید دقیقا یکبار ملاقات شود. ایستگاه انرژی می‌تواند بیش از یکبار ملاقات شود یا اصلا هیج بار ملاقات نشود. دو نوع Szوجود دارد : ایستگاه الکتریکی و ایستگاه سوخت. هر ایستگاه می‌تواند تا نهایت ظرفیت را پر کند. هر وسیله که برای یک تور انتخاب شده است نمی‌تواند از حداکثر زمان مجاز  Tmax تجاوز کند.

فرضیات مدل: 

·         این مساله به‌صورت قطعی و ایستا می‌باشد

·         مساله مسیریابی ترکیبی شامل مشتریان، یک انبار و مجموعه‌ای از ایستگاه‌ها (الکتریکی و سوخت) می‌باشد

·         هر بار که وسیله به انبار برمی‌گردد، ظرفیت مخازن الکتریکی و سوخت تا حدنهایت پر می‌شود

·         همه‌ی ایستگاهها ظرفیت نامحدود دارند و همواره قادر به سرویس دادن به وسایل نقلیه هستند و هیچ محدودیتی از نظر تعداد توقف ها در ایستگاه‌های سوختگیری برای وسایل نقلیه وجود ندارد

·         هر بار که یک وسیله نقلیه ایستگاه سوختگیریSz  را ملاقات می‌کند ظرفیت نوعz  وسیله نقلیه پر می‌شود

·         هر ایستگاه سوختگیری مجاز است که اصلا ملاقات نشود یا بیشتر از یکبار ملاقات شود

·         وسایل نقلیه برای ملاقات همه‌ی مشتریان نیاز می‌باشد. یک وسیله می‌تواند Szرا ملاقات کند هنگامی که نیاز است تا کمترین هزینه‌ی تور را پیدا کند

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

تابع هدف (1) در پی یافتن کمترین هزینه کل سفر با استفاده از وسیله نقلیه ترکیبی در یک روز مشخص می‌باشد. محدودیت (2) تضمین می‌کند که هر مشتری تنها یک عنصر ما بعد دارد: مشتری، ایستگاه سوخت یا انبار. محدودیت (3) تضمین می‌کند که هر ایستگاه حداکثر یک عنصر مابعد دارد: یک مشتری، ایستگاه یا انبار. محدودیت (4) بیان می‌کند که تعداد خروجی و ورودی یک گره باید با هم برابر باشد. محدودیت (5) تضمین می‌کند که حداکثرm  وسیله نقلیه از انبار خارج می‌شوند و محدودیت (6) تضمین می‌کند که در یک روز معین حداکثرm  وسیله نقلیه به انبار مراجعه می‌کنند (برمی‌گردنند). محدودیت (7) زمان رسیدن و ورود هر وسیله نقلیه به هر گره را نشان می‌دهد. محدودیت (7) به همراه محدودیتهای (8) و (9) نشان می‌دهند که وسایل نقلیه نباید دیرتر از موعد مقرر Tmaxبه انبار برگردند. محدودیت (8) زمان خروج از انبار و یک حد بالا برای زمان ورود در حین برگشتن به انبار را نشان می‌دهد. حد بالا و پایین زمان رسیدن به یک مشتری و یا به یک ایستگاه در محدودیت (9) نمایش داده شده است که تضمین می‌کند هر مسیر در مدت زمان  Tmax  تکمیل می‌شود. محدودیت (10) میزان سطح سوخت وسیله نقلیه را بر اساس توالی گره‌ها و نوع آن مشخص می‌کند. محدودیت (11) بیان میکند که فاصله بین گره i و گره j با منبع انرژی نوع z سرویس داده شود. محدودیت (12) میزان توان نوعz  به Qz را بعد از ملاقات کردن انبار و یا ایستگاههای نوع  zتنظیم مجدد می‌کند. محدودیت (13) بیان می‌کند که حداقل یک نوع انرژی برای انتقال از نقطهi  به نقطه j وجود دارد. محدودیت (14) نشان می‌دهد که انرژی کافی باقی مانده برای بازگشت مستقیم به انبار یا ملاقات یک ایستگاه از هر یک از مشتریان وجود دارد. محدودیت‌های (15) و (16) نشان دهنده‌ی متغیر‌های تصمیم‌گیری باینری هستند.

شبیه سازی تبرید برای مساله مسیریابی وسیله نقلیه ترکیبی:

مساله مسیریابی وسیله نقلیه ترکیبی یک مساله بهینه سازی ترکیبیNP-Hard  است. درسال‌های اولیه، برای حل اینگونه مسائل روش‌های ابتکاری مخصوصی توسعه داده شدند. شبیه سازی تبرید یکی از این روش‌های موفقیت آمیز در حل اینگونه مسائل است. شبیه سازی تبرید یک الگوریتم جستجوگر محلی می‌باشد که دارای مکانیزمی می‌باشد برای فرار از بهینه محلی و برای رسیدن به بهینه کلی. مسائل مسیریابی و مسائل مرتبط به صورت موثری توسط الگوریتم شبیه‌سازی تبرید حل می‌شوند. این الگوریتم، یک الگوریتم تک جوابی می‌باشد که مرتبا به دنبال جوابی با تابع هدف بهتر می‌باشد. ویژگی اصلی این الگوریتم، حرکت تپه نوردی با معرفی یک معیار پذیرش به نام تابع بولتزمان می‌باشد. در الگوریتم شبیه‌سازی شده در این مقاله از تابع کوشی استفاده می‌شود. هنگامی که پارامتر دما تا 0 درجه کاهش پیدا می‌کند، حرکات تپه نوردی کمتر اتفاق میافتد. به منظور دور شدن از خطر بهینگی محلی،  از یک مکانیزم واگرایی به نام استراتژی شروع مجدد استفاده شده است.

نحوه نمایش جواب:

الگوریتم تبرید شبیه‌سازی شده برای مسائل مسیریابی وسیله نقلیه ترکیبی، نحوه نمایش مشخص و خاصی را دارد. جواب شامل n  مشتری و  mایستگاه انتخاب شده برای ایستگاه سوخت و الکتریکی از مجموعه Se و Sf می‌باشد. این نوع از نمایش جواب، امکان این را فراهم می‌کند که یک جواب طولی متفاوت با جواب‌های دیگر داشته باشد. شماره‌ی iدر مجموعه 1 تا n نشان می‌دهد که به عنوانi  مین مشتری سرویس ببیند. شماره‌های بعدی از مجموعه n+1 تا n+m نشان دهنده‌ی ایستگاه‌های شارژ می‌باشد که باید ملاقات شوند.

توضیحاتی در مورد نحوه نمایش جواب:

شکل 1 حالات ممکن مسیر را برای 20 مشتری بدون رفتن به ایستگاه‌های سوختگیری نشان می‌دهد.

این جواب بر اساس محدودیت زمانی و ظرفیت وسیله نقلیه تقسیم بندی شده است. بنابراین 5 مسیر برای سرویس‌دهی به همه‌ی مشتریان وجود دارد. هنگامی که یک مسیر تعیین می‌شود این امکان وجود دارد که به دلیل محدودیت ظرفیت وسیله نقلیه، تعدادی از مشتریان امکان سرویس داده شدن را نداشته باشند. به هر حال استفاده از ایستگاه‌های سوختگیری کمک می‌کند تا یک جواب موجه ساخته شود.

شکل شماره 2 مسیرها را برای 20 مشتری پس از وارد کردن ایستگاه‌های سوخت و الکتریکی نشان می‌دهد. جواب متشکل از یک انبار، دو مرکز سوخت الکتریکی، دو مرکز سوخت و 20 مشتری می‌باشد. یک مقدار جریمه برابر با  pبا توجه به تعداد مشتری‌های سرویس داده نشده برای جواب تعریف می‌شود.

جواب آغازین:

گاهی اوقات یک جواب اولیه خوب می‌تواند منجر به تولید جواب نهایی بهتر و عملکرد بهتر در الگوریتم شود. الگوریتم شبیه‌سازی تبرید با استراتژی شروع مجدد ارائه شده در این مقاله، برای تولید جواب اولیه از رویکرد ابتکاری معروف نزدیکترین همسایگی استفاده می‌کند.

گام 1: برای هر مسیر، یک مشتری که هنوز سرویس داده نشده است بر اساس نزدیکترین فاصله با نقطه‌ای که از انبار شروع می‌شود انتخاب می‌شود. یک مسیر پایان یافته تلقی می‌شود اگر بدون تجاوز از بیشترین زمان مسافرت، یک مشتری خدمت دیده نشده را نتوان به مسیر تخصیص داد.

گام 2: Rرا مسیری در نظر بگیرید که در آن بیش از ظرفیت وسیله نقلیه استفاده می‌شود. برای هر مسیر R، ما به طور تصادفی یک ایستگاه شارژمجدد را به آن تخصیص می‌دهیم در حالی که مساله را از نظر محدودیت زمانی موجه نگه می‌دارد.

گام 3: برای هر مسیر R که همچنان محدودیت ظرفیت را نقض می‌کند، یک مقدار جریمه Rرا بر اساس تعداد نقاطی که محدودیت را نقض می‌کند برای تابع هدف در نظر می‌گیریم. بعد از گام 3 این روند را تمام می‌کنیم.

همسایگی:

الگوریتم به دنبال یک همسایگی ‌در هر تکرار، که از میان 5 همسایگی (مسیر) که قبلا مشخص شده است، می‌باشد. ساختار همسایگی شامل، انواع مختلف حرکت شامل، وارد کردن، تعویض و معکوس کردن که در ادبیات مسیریابی معروف هستند می‌باشند. حرکات همسایگی توسط N(x)مشخص می‌شود. عملکرد وارد کردن بدین صورت می‌باشد که از جواب xیک گره تصادفیi  انتخاب می‌شود و سپس دقیقا بعد از خانه‌ی تصادفیj  وارد می‌شود. عملکرد تعویض بدین صورت می‌باشد که جایگاه دو گره تصادفی iو jاز جواب xبا هم تعویض می‌شود. عملکرد وارونگی و معکوس نیز بدین صورت می‌باشد که دو گره تصادفی iو jاز جواب xانتخاب می‌شوند و گره‌های بین آنها دقیقا وارنه می‌شوند.

تنظیم پارامترها:

شبیه‌سازی تبرید با استراتژی شروع مجدد با 6 پارامتر شروع می‌شود که عبارتند از:

برای هر نقطه‌ای که سرویس داده نمی‌شود معادل 25 دلار آمریکا جریمه در نظر گرفته شده است.

روند الگوریتم ارائه شده در این مقاله:

الگوریتم ارائه شده دارای دو فاز می‌باشد: 1. فاز آغازین 2. فاز بهبود. در فاز آغازین، الگوریتم نزدیکترین همسایگی، همانطور که در بخشهای قبل توضیح داده شد برای ساختن مسیر اولیه به کار گرفته می‌شود. بعد از فاز آغازین، الگوریتم شروع به فاز بهبود می‌کند. فاز بهبود سعی می‌کند نتایج حاصل از فاز اولیه را با استفاده از تابع همسایگی بهبود دهد.

الگوریتم با تنظیم کردن دما فعلی با دمای اولیه و برابر قراردادن بهترین جواب Fgbestبرابر با یک عدد بزرگ مثل Mو تولید یک جواب اولیه مثل Xشروع می‌شود.‌ بهترین جواب فعلی Xbestو مقدار تابع هدف بهترین جواب فعلی Fbestاز ابتدا به ترتیب برابر با Xو تابع هدف متناظر با Xمی‌باشد.

 

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

مساله کوچکی با یک انبار، 5 مشتری، 2ایستگاه سوخت و 2 ایستگاه شارژ الکتریکی برای توضیح عملکرد مدل انتخاب شده است. اطلاعات مساله در ادامه آمده است: