مسئله‌ی بارگیری و تحویل کامل کامیون با دسته بندی کامیون‌ها

گروه‌بندی کامیون‌ها یک فناوری امیدوارکننده برای کاهش مصرف انرژی، افزایش ایمنی وسایل نقلیه و بهبود بهره‌وری ترافیک است. در این مقاله، ما مقرون‌به‌صرفه بودن گروه‌بندی کامیون‌ها را از دیدگاه یک شرکت حمل‌ونقل که درخواست‌های بارگیری و تحویل کامل کامیون‌ها را از طریق یک شبکه حمل‌ونقل انجام می‌دهد، بررسی می‌کنیم. در طول حمل‌ونقل، کامیون‌ها می‌توانند در بخش‌های جاده‌ای پیمایش‌شده، گروه‌بندی تشکیل دهند تا هزینه‌های سفر کامیون‌های بعدی کاهش یابد. مشکل این است که چگونه مسیریابی و زمان‌بندی کامیون‌ها باید تعیین شود تا از گروه‌بندی کامیون‌ها به‌طور کامل استفاده شود و کل هزینه حمل‌ونقل به حداقل برسد. ما دو فرمول‌بندی مدل را در یک شبکه با زمان گسترش‌یافته برای این مشکل پیشنهاد می‌کنیم: یک مدل تحویل مستقیم و یک مدل تحویل غیرمستقیم، که در آن مدل تحویل غیرمستقیم به کامیون‌ها اجازه می‌دهد تا در طول تحویل‌ها از مکان‌های میانی بازدید کنند تا تشکیل گروه‌ها را تسهیل کند. در هر دو مدل، کامیون‌ها مجاز به انتظار در هر گره پیمایش‌شده هستند، مشروط بر اینکه پنجره‌های زمانی درخواست‌ها نقض نشوند. ما یک الگوریتم بهبود یافته کشف گسسته‌سازی پویا (DDD) را برای حل دقیق این دو مدل توسعه می‌دهیم. از طریق آزمایش‌های محاسباتی گسترده، دریافتیم که (1) الگوریتم بهبود یافته DDD می‌تواند دقت راه‌حل را با تلاش محاسباتی بسیار کمتری در مقایسه با الگوریتم DDD پایه افزایش دهد؛ (2) اثر صرفه‌جویی در هزینه حمل کامیون مطلوب است؛ و (3) برای شرکت‌های باربری که در شبکه‌های حمل و نقل کوچک فعالیت می‌کنند، استفاده از مدل تحویل مستقیم ممکن است مناسب‌تر باشد.

مقدمه

گروه‌بندی کامیون‌ها یک فناوری رانندگی خودکار ضروری در صنعت حمل و نقل است زیرا می‌تواند ایمنی را افزایش داده و هزینه‌های عملیاتی را کاهش دهد. یک گروه کامیون که توسط فناوری‌های خودروهای خودکار و متصل فعال می‌شود، ناوگانی از کامیون‌ها است که توسط کامیون پیشرو هدایت می‌شود و بقیه کامیون‌ها با فاصله کمی برای هماهنگی با کامیون پیشرو، آن را دنبال می‌کنند (Slowik and Sharpe, 2018; Xue et al., 2024). گروه‌بندی کامیون‌ها در کامیون‌های سطح 1 SAE یا بالاتر موجود است و می‌تواند اولین گام در اتوماسیون حمل و نقل در نظر گرفته شود (Bhoopalam et al., 2018). در عمل، گروه‌بندی کامیون‌ها می‌تواند در محیط‌های مختلفی مانند حمل و نقل مکرر کالا بین انبارها و کارخانه‌ها و بارگیری و تخلیه فشرده کانتینرها در پایانه‌های بندری به کار گرفته شود. تأثیر گروه‌بندی کامیون‌ها بر کاهش هزینه‌های عملیاتی دوگانه است: (1) نزدیک نگه داشتن کامیون‌ها به یکدیگر در حین حرکت، نیروی آیرودینامیکی را کاهش می‌دهد که به نوبه خود باعث کاهش مصرف انرژی می‌شود؛ (2) با افزایش اتوماسیون، رانندگان کامیون‌های پشت سر می‌توانند از وظایف رانندگی خود برای استراحت یا انجام کارهای دیگر دست بکشند که این امر باعث بهبود راحتی رانندگی و کاهش هزینه‌های نیروی کار می‌شود (مونیوس و برگکویست، 2019؛ شول و همکاران، 2023).

در این مقاله، ما به بررسی مقرون به صرفه بودن حمل و نقل گروهی کامیون‌ها از دیدگاه یک شرکت حمل و نقل که درخواست‌های بارگیری و تحویل با ظرفیت کامل کامیون (FTL) را از طریق یک شبکه حمل و نقل انجام می‌دهد، می‌پردازیم. ما بر FTL تمرکز می‌کنیم زیرا یک روش مهم حمل و نقل بار است و بخش بزرگی از کل حجم بار را تشکیل می‌دهد (Jothi Basu et al., 2015; Xue et al., 2021). در حمل و نقل FTL، کامیون‌ها معمولاً بدون مراجعه به مکان‌های واسطه، تحویل مستقیم انجام می‌دهند (Jothi Basu et al., 2015). با این حال، تحویل مستقیم ممکن است تشکیل گروه‌ها را محدود کرده و مزایای گروه‌بندی را کاهش دهد.

برای تسهیل تشکیل دسته‌ها، ممکن است انجام تحویل غیرمستقیم برای کامیون‌ها مفید باشد، یعنی کامیون‌ها می‌توانند از کوتاه‌ترین مسیر خود منحرف شوند و برای پیوستن به یک دسته، کمی انحراف داشته باشند (Bhoopalam و همکاران، ۲۰۱۸). با این حال، مجاز دانستن تحویل غیرمستقیم، پیچیدگی مسیریابی و برنامه‌ریزی کامیون‌ها را افزایش می‌دهد. یک سوال طبیعی این است که کامیون‌هایی که تحویل غیرمستقیم انجام می‌دهند، چگونه باید در حمل و نقل FTL مسیریابی و برنامه‌ریزی شوند تا از مزایای دسته کامیون‌ها به طور کامل بهره‌مند شوند؟ همچنین، چگونه می‌توان مزایای تحویل غیرمستقیم را با مزایای تحویل مستقیم مقایسه کرد؟ علاوه بر این، برای شرکت‌های حمل و نقل، خرید کامیون‌هایی که قادر به دسته بندی هستند، هزینه‌های عملیاتی را کاهش می‌دهد اما هزینه‌های سرمایه‌ای را افزایش می‌دهد (Chottani و همکاران، ۲۰۱۸؛ Aboulkacem و Combes، ۲۰۲۳). بنابراین، بررسی این موضوع ضروری است که آیا استفاده از دسته بندی کامیون‌ها برای شرکت‌های حمل و نقل مزیت مشخصی دارد یا خیر.

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

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

ما همچنین چندین بهبود جدید در الگوریتم پایه DDD برای تسریع همگرایی الگوریتم پیاده‌سازی می‌کنیم. به عنوان مثال، ما به صورت پویا تلرانس بهینگی را در حل مسئله آزادسازی شبکه در هر تکرار الگوریتم DDD کاهش می‌دهیم. هنگامی که تلرانس بهینگی کاهش می‌یابد، از روش‌های اکتشافی برای حل مسئله آزادسازی شبکه استفاده می‌کنیم. هدف، کاهش زمان محاسباتی صرف شده برای مسئله آزادسازی شبکه بدون تأثیر بر همگرایی الگوریتم DDD است. همچنین، ما از شبکه با زمان گسترش جزئی با لینک‌های بسیار طولانی برای کاهش اندازه مسئله آزادسازی شبکه و دستیابی به حد بالای بهتر استفاده می‌کنیم. علاوه بر این، ما پیشنهاد می‌کنیم که آزادسازی خطی FTPDP-TP را برای دستیابی به حد پایین بهتر حل کنیم. ما ثابت می‌کنیم که مقدار هدف بهینه آزادسازی خطی مدل تحویل مستقیم برابر با مدل تحویل غیرمستقیم است. ما تصمیم گرفتیم که مدل تحویل مستقیم را با روش آزادسازی خطی حل کنیم، زیرا حل آن آسان‌تر است. از طریق آزمایش‌های محاسباتی گسترده، دریافتیم که (1) الگوریتم بهبود یافته DDD می‌تواند دقت حل را با تلاش محاسباتی بسیار کمتری در مقایسه با الگوریتم DDD پایه افزایش دهد؛ (2) اثر صرفه‌جویی در هزینه ناشی از گروه‌بندی کامیون‌ها مطلوب است؛ و (3) برای شرکت‌های باربری که در شبکه‌های حمل و نقل کوچک فعالیت می‌کنند، استفاده از مدل تحویل مستقیم ممکن است مناسب‌تر باشد.(منبع).