مقایسه الگوریتم‌های سریع VRP برای سیستم‌های حمل و نقل بار شهری مشارکتی: تحلیل مسئله حل

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

مقدمه

صنعت حمل و نقل بار با یک پارادوکس روبرو است: از یک سو، منبع اصلی اشتغال است و از توسعه اقتصادی یک کشور پشتیبانی می‌کند؛ از سوی دیگر، منشأ بسیاری از عوارض جانبی از جمله ازدحام و اختلالات زیست‌محیطی است که بر کیفیت زندگی، عمدتاً در مناطق شهری، تأثیر می‌گذارد. در سال‌های گذشته، چندین محقق و متخصص بر مطالعه و تحلیل بخش شهری زنجیره‌های تأمین تمرکز کرده‌اند، اگرچه نه همیشه از منظر لجستیک جهانی (آلن و براون، ۲۰۱۰). لجستیک شهری اکنون یک رشته علمی در نظر گرفته می‌شود که هدف آن درک، شناسایی، تجزیه و تحلیل و شبیه‌سازی جنبه‌های سازمانی، مکانی، نظارتی، فناوری، سیاست‌گذاری و زیست‌محیطی لجستیک در مناطق شهری و همچنین تعاملات آنها با محیط شهری است.

یکی از محبوب‌ترین موضوعات در لجستیک شهری، تجمیع شهری است، یعنی منطقی‌سازی کالاها در سکوهای تجمیع که در آن‌ها وسایل نقلیه با بارگذاری بهتر برای تحویل به مراکز شهر ترکیب می‌شوند. ما چندین اثر را در رابطه با این سوال می‌یابیم (برخی از نمونه‌های شاخص یا مجموعه آثار را می‌توان در Crainic و همکاران، ۲۰۰۴؛ Gonzalez-Feliu، ۲۰۰۸؛ Van Duin و همکاران، ۲۰۰۸؛ Danielis و همکاران، ۲۰۱۰؛ Vaghi و Percoco، ۲۰۱۱؛ Allen و همکاران، ۲۰۱۲ یافت). این آثار، انگیزه توسعه مسائل مسیریابی وسایل نقلیه سازگار با سیستم‌های حمل و نقل چند سطحی را ایجاد کرده‌اند (Crainic، ۲۰۰۸؛ Gonzalez-Feliu، ۲۰۱۲، ۲۰۱۳؛ Mancini، ۲۰۱۳). سیستم‌های حمل و نقل چند مرحله‌ای با طرح‌های حمل و نقلی سروکار دارند که یک یا چند وقفه در تغییر در تأسیسات لجستیک واسطه‌ای دارند که در آن‌ها می‌توان عملیات مختلفی را انجام داد (Gonzalez-Feliu, 2013). در این تأسیسات واسطه‌ای، برخی عملیات برای کمک به فرآیند توزیع، کاهش هزینه‌ها، ارائه خدمات با کیفیت بالاتر یا ارائه برخی خدمات اضافی به رانندگان وسایل نقلیه، عمدتاً مربوط به بارانداز متقاطع، انجام می‌شود (Gonzalez-Feliu, 2012). در مورد مسیریابی وسایل نقلیه، ما دو نوع اصلی از مشکلات مربوط به حمل و نقل چند مرحله‌ای را مشاهده می‌کنیم.

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

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

در ادبیات، اکثر آثار با مسائل تقسیم سروکار دارند (طبق گفته گونزالس-فلیو، ۲۰۱۳، تنها ۵ مورد از ۳۸ اثر علمی با مسائل ادغام برای توزیع بار سروکار دارند و ۸ مورد دیگر با ادغام برای جمع‌آوری بار، ۲۵ مورد باقی مانده مستقیماً با مسائل تقسیم سروکار دارند). با این حال، هنگام مشاهده کاربردهای عملی، ادغام شهری، در اشکال مختلف آن، مستقیماً با مسائل ادغام مرتبط است (تامپسون و هاسال، ۲۰۱۲؛ ورلینده و همکاران، ۲۰۱۲؛ گونزالس-فلیو، ۲۰۱۳). تصمیم‌گیرندگان دولتی و خصوصی در لجستیک شهری نیاز به پشتیبانی قوی دارند که درک و بازتولید آن نیز آسان باشد. با این حال، به نظر می‌رسد اکثر الگوریتم‌های امروزی که برای حمل و نقل چند مرحله‌ای اعمال می‌شوند، تطابق مستقیمی با موقعیت‌های واقعی ندارند. علاوه بر این، در سایر کاربردهای VRP، الگوریتم‌های اکتشافی کلاسیک (با جستجوی محلی) به طور گسترده در ابزارها به کار گرفته می‌شوند و الگوریتم‌های فراابتکاری عملیاتی که از نظر محاسباتی عملکرد بهتری دارند، برای ورود به بازار سیستم‌های مدیریت حمل و نقل با مشکل مواجه هستند.

به همین دلایل، اولین سوال مطرح می‌شود: پتانسیل الگوریتم‌های فراابتکاری برای حل نمونه‌های پیچیده و واقع‌گرایانه توزیع کالاهای شهری چیست؟ برای تلاش برای یافتن پاسخ، پیشنهاد می‌کنیم دو تکنیک کلاسیک را بر اساس کاربردهای واقعی مسیریابی دو مرحله‌ای وسایل نقلیه مقایسه کنیم: اول یک الگوریتم جستجوی محلی کلاسیک، مانند الگوریتم‌های TMS فعلی، که با یک طرح حمل و نقل دو مرحله‌ای تطبیق داده شده است؛ دوم یک الگوریتم ژنتیک، که آن هم با همان مشکل تطبیق داده شده است.

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