![[09127409082]](https://barast.com/wp-content/uploads/2021/01/newlogo.png){kind=small}
برنامهریزی دسته بندی کامیونها برای مسئله مسیریابی وسایل نقلیه با ظرفیت شبکه جادهای
گروهبندی کامیونها، یک فناوری اتصال کامیونها در بزرگراه، در سالهای اخیر به دلیل مزایای آن در صرفهجویی در انرژی و هزینههای عملیاتی، توجه زیادی را به خود جلب کرده است. با این حال، اکثر مطالعات موجود در مورد گروهبندی کامیونها، تمرکز خود را بر سناریوهای خاصی محدود میکنند که در آنها هر کامیون میتواند تنها به یک تقاضای مشتری پاسخ دهد و بنابراین دارای یک جفت مبدا-مقصد مشخص است، بنابراین فقط مسیریابی و برنامههای زمانی در نظر گرفته میشوند. با این وجود، در لجستیک دنیای واقعی، هر کامیون ممکن است نیاز به خدمترسانی به چندین مشتری واقع در مکانهای مختلف داشته باشد و اپراتوری که ناوگانی از کامیونها را مدیریت میکند، بنابراین باید نه تنها مسیریابی و برنامههای زمانی هر کامیون، بلکه مجموعه مشتریان اختصاص داده شده به هر کامیون و توالی بازدید آنها را نیز تعیین کند. این به عنوان یک مسئله مسیریابی وسیله نقلیه با ظرفیت محدود با پنجرههای زمانی (CVRPTW) شناخته میشود و بررسی کاربرد گروهبندی کامیونها در چنین مسئلهای مستلزم چارچوبهای مدلسازی جدید و الگوریتمهای راهحل متناسب است. با توجه به این موضوع، این مطالعه اولین تلاش خود را برای بهینهسازی طرح گروهبندی کامیونها برای یک شبکه جادهای CVRPTW به گونهای انجام میدهد که کل هزینه عملیات، شامل هزینه ثابت ارسال وسایل نقلیه و هزینه انرژی، را به حداقل برساند و در عین حال تمام تقاضاهای تحویل را در محدودیتهای پنجره زمانی خود برآورده کند. به طور خاص، طرح عملیات، تعداد کامیونهای اعزامی، مجموعه مشتریان و برنامههای مسیریابی و زمانی برای هر کامیون را تعیین میکند. علاوه بر این، چارچوب مدلسازی بر اساس یک شبکه جادهای به جای یک نمودار گره مشتری سنتی ساخته شده است تا عملیات گروهبندی را بهتر شبیهسازی و تسهیل کند. یک الگوریتم سه مرحلهای تعبیه شده با طرح “مسیر سپس برنامه”، برنامهنویسی پویا و روش ابتکاری درج اصلاحشده، برای حل مدل پیشنهادی به موقع توسعه داده شده است. آزمایشهای عددی برای اعتبارسنجی چارچوب مدلسازی پیشنهادی، نشان دادن عملکرد الگوریتم راهحل پیشنهادی و تعیین کمیت مزایای حاصل از فناوری گروهبندی کامیونها انجام شده است.
مقدمه
در عصر سیستمهای پیشرفته لجستیک و تحویل، گروهبندی کامیونها، مفهومی که از پیشرفتها در اتوماسیون خودرو و ارتباطات بیسیم بهره میبرد، به عنوان راه حلی برای متحول کردن عملیات تحویل بار ظهور کرده است. به طور خاص، انتظار میرود گروهبندی کامیونها، در تلفیق با لجستیک مدرن، مزایای قابل توجهی از جمله افزایش استفاده از ظرفیت با نزدیکتر شدن فاصله بین کامیونها (Chen et al., 2016, Chen et al., 2017)، کاهش هزینههای عملیاتی، کاهش خستگی رانندگی رانندگان و یک زنجیره تأمین پایدارتر و مؤثرتر (Gazran et al., 2022) را به همراه داشته باشد و در نتیجه باعث صرفهجویی قابل توجه در رفاه اجتماعی-اقتصادی و هزینهها در خدمات لجستیک شود. به طور خاص، کاهش در کل لجستیک 1 تا 2 درصد گزارش شده است (Marzano et al., 2022) که با توجه به حجم عظیم لجستیک قابل توجه است. علاوه بر این، با عملکرد گروهبندی، صرفهجویی در انرژی میتواند تا بیش از 8 درصد باشد، اگرچه ممکن است بسته به نوع وسیله نقلیه، بار و اندازه گروه متفاوت باشد. با توجه به وعدههای بزرگی که در مورد سیستم حمل و نقل دسته جمعی کامیونها وجود دارد، شرکتهایی مانند دایملر AG، ولوو، DAF، TuSimple، هوندا و Peleton به طور جدی این فناوری را آزمایش کردهاند. به عنوان مثال، TuSimple و Waymoe به ترتیب محصولات خودران دسته جمعی خود را با نامهای TuSimple Connect و Waymo Via به نمایش گذاشتهاند (TuSimple، 2022، Waymo، 2022). PATH، پیشگام در زمینهی چیدمان کامیونها و با همکاری گروه Volve، عملیات عملی چیدمان کامیونها را در بندر لسآنجلس و بزرگراه بین ایالتی I-66 در حومهی ویرجینیای شمالی واشنگتن دیسی در سال ۲۰۱۷ ارائه داد (برکلی، ۲۰۱۷). انجمن تولیدکنندگان خودرو اروپا نیز طرحی را ارائه داد که نحوهی دستیابی به چیدمان چند برندی را قبل از سال ۲۰۲۵ شرح میداد.
علاوه بر صنعت، بسیاری از محققان عملیات دسته بندی کامیونها را مطالعه کردهاند و ما ابتدا آنها را بررسی خواهیم کرد تا شکافهای تحقیقاتی که انگیزه این مطالعه هستند را شناسایی کنیم. با توجه به اینکه تشکیل یک دسته مستلزم رسیدن کامیونها به یک مکان در یک زمان است، هم برنامههای مسیریابی و هم برنامههای زمانبندی اهمیت دارند. در مورد برنامه مسیریابی، لارسون و همکاران (2015) یک مسئله مسیریابی گراف را بر اساس دسته بندی کامیونها فرموله کردند اما محدودیتهای مهلتهای تحویل را برای کاهش پیچیدگی مسئله نادیده گرفتند. دو روش اکتشافی سازنده و یک الگوریتم جستجوی محلی برای بهینهسازی مسیر هر کامیون برای تشکیل دستهها به روشی برای به حداقل رساندن هزینه سیستم پیشنهاد شده است. بر اساس منطقی مشابه، لارسون و همکاران (2013) سرعت وسایل نقلیه را برای به حداکثر رساندن صرفهجویی در سوخت با دسته بندی بهینه کردند و یک روش اکتشافی مبتنی بر هاب برای سادهسازی فرآیند حل استخراج کردند. در میان مطالعات مربوط به برنامه زمانی، بویسن و همکاران (2018) زمان حرکت کامیونها را برای تشکیل دستهها بر اساس یک سناریوی ساده بهینه کردند که در آن همه کامیونها یک مسیر یکسان را اتخاذ میکنند. بنابراین، راهحل بهینه برای به حداقل رساندن هزینه عملیات را میتوان به موقع پیدا کرد، و آنها همچنین بررسی کردند که پنجرههای زمانی تنگ و اندازه محدود گروه ممکن است مزیت گروهبندی را تضعیف کند. ون د هوف (2018) یک مسئله مشابه را مطالعه کرد اما کنترل سرعت را برای وسیله نقلیه عقب مجاز دانست و آنها یک روش ابتکاری بهبود محلی برای مقابله با نمونههای در مقیاس بزرگ پیشنهاد کردند. به عنوان یک بسط برای ون د هوف (2018) و ون د هوف و همکاران (2017) یک مدل برنامهریزی پویای تصادفی برای تعیین کمیت تأثیر عدم قطعیت زمانی ساختند. ژانگ و همکاران (2017) مطالعه دیگری است که گروهبندی را با عدم قطعیتهای زمانی در نظر میگیرد و آنها کشف کردند که گروهبندی تنها زمانی ترجیح داده میشود که فاصله زمانی سفر دو وسیله نقلیه در یک آستانه خاص باشد و عدم قطعیت زمان سفر این آستانه را بیشتر کاهش دهد.
با این وجود، برای تسهیل حرکت کامیونها در یک شبکه، لازم است که برنامههای مسیریابی و زمانبندی هر کامیون به طور مشترک در نظر گرفته شود. در این راستا، لارسون و همکاران (2016) یک برنامه عدد صحیح مختلط برای بهینهسازی برنامههای مسیریابی و زمانبندی کامیونها ساختند و از یک رویکرد تجزیه مدل برای دستیابی به راهحل دقیق استفاده کردند. علاوه بر این، یک فرآیند پیشپردازش برای حذف مسیرهای غیرضروری و در نتیجه کاهش اندازه مسئله توسعه داده شد. لو و همکاران (2018) مطالعه فوق را با در نظر گرفتن تنظیم سرعت کامیونها گسترش دادند. شو و همکاران (2022) برای درک بهتر سناریوی دنیای واقعی، توقفهای اجباری رانندگان در طول سفر یک مسئله حرکت کامیونها را در نظر گرفتند و یک رویکرد برنامه عدد صحیح مختلط جزئی که با روش جستجوی همسایگی تکرارشونده ادغام شده بود، برای حل کارآمد مسئله توسعه داده شد. لو و لارسون (2022) به طور نوآورانه یک فرآیند تکراری “مسیر-سپس-زمانبندی” را برای حل متوالی مسئله مسیریابی و مسئله زمانبندی به طور جداگانه اختراع کردند، در نتیجه پیچیدگی مسئله را در طول هر فرآیند حل کاهش دادند. آنها همچنین با استفاده از مکانیسم اصلاح هزینه لینک بازخورد طراحیشده خود، اثبات تحلیلی ارائه دادند که چنین فرآیند تکراری به یک راهحل غیربهینه همگرا خواهد شد. اخیراً، ژائو و لئوس (2024) با توجه به اینکه کامیونهای پیشرو نیز صرفهجویی در سوخت دارند و کامیونها مجاز به انتظار در طول سفر نیستند، به چارچوب راهحل «مسیر سپس زمانبندی» فوق برای حل مسئله مسیریابی کامیون متوسل شدند. عبدالمالکی و همکارانش (2021) به جای تعیین محدودیتهای سازگاری زمانی برای ثبت برنامههای کامیونها، یک شبکه با زمان گسترشیافته برای برنامهریزی برنامههای سفر کامیونها ایجاد کردند تا دستههایی برای صرفهجویی در انرژی تشکیل دهند و مسئله به عنوان یک مسئله جریان چندکالایی فرموله شد. سپس الگوریتمهای تقریبی به همراه برنامهنویسی پویا برای دستیابی به یک راهحل مناسب پیشنهاد شدند.
برای مطالعات فوقالذکر در مورد گروهبندی کامیونها، فرض میشود که هر کامیون فقط به یک تقاضای از پیش تعیینشده مشتری پاسخ میدهد و بنابراین فقط یک مبدا و مقصد دارد که هر دو نیز از پیش تعیینشده هستند. با این وجود، در خدمات لجستیک یا تحویل در دنیای واقعی، هر کامیون قادر به ارائه خدمات به چندین مشتری در طول مسیر خود است. علاوه بر این، مجموعه مشتریانی که قرار است توسط هر کامیون به آنها خدمات ارائه شود و توالی آنها برای دریافت خدمات هنوز مشخص نشده است. در این مطالعه، ما اولین تلاش را برای بهینهسازی طرح گروهبندی کامیونها برای مسئله تحویل در دنیای واقعی انجام میدهیم. به طور خاص، بدون از دست دادن کلیت، فرض میکنیم که مشتریان مشخصی در مکانهای مختلف شبکه قرار دارند. هر مشتری یک تقاضای خاص و یک بازه زمانی مورد نیاز برای ارائه خدمات دارد و هر کامیون حداکثر ظرفیت حمل کالا را دارد. هدف ما به عنوان یک هماهنگکننده مرکزی یا یک شرکت حمل و نقل، بهینهسازی طرح جابجایی کامیونها در یک شبکه جادهای برای خدمترسانی به تمام خواستههای مشتریان به گونهای است که هزینه کل، از جمله هزینه ارسال و هزینه انرژی را به حداقل برساند. به طور خاص، این طرح نه تنها مسیریابی و برنامههای زمانی هر کامیون، بلکه مجموعه مشتریان اختصاص داده شده به هر کامیون و توالی آنها برای خدمترسانی را نیز تعیین میکند. برخلاف مسائل سنتی مسیریابی وسایل نقلیه (VRP)، مسئله مورد بررسی در این مطالعه به جای نمودار گره مشتری، بر روی شبکه جادهای مدلسازی شده است تا تشکیل و جداسازی قطعات دسته را مشخص کند. علاوه بر این، از آنجایی که وزن یک کامیون در طول سفر تغییر میکند و بر صرفهجویی در انرژی ناشی از جابجایی کامیونها تأثیر میگذارد، تأثیر آن بر میزان مصرف انرژی به صراحت در نظر گرفته شده است. بنابراین، این مطالعه اساساً بر برنامهریزی جابجایی کامیونها برای یک مسئله مسیریابی وسایل نقلیه با ظرفیت شبکه جادهای و پنجرههای زمانی (RCVRPTW) تمرکز دارد.
در این مطالعه، ابتدا یک چارچوب برنامهریزی عدد صحیح مختلط (MIP) برای مدلسازی عملیات دسته بندی کامیونها برای RCVRPTW توسعه داده شده است. با توجه به اینکه مسئله NP-hard و مبتنی بر شبکه جادهای است (یائو و همکاران، 2021؛ بن تیچا و همکاران، 2019)، یک الگوریتم 3 مرحلهای با ادغام طرح “مسیر-سپس-برنامه” (لو و لارسون، 2022)، برنامهنویسی پویا و روش ابتکاری درج اصلاحشده، برای حل مدل پیشنهادی به موقع و با دقت بالا توسعه داده شده است. مجموعه مقالات موجود نشان میدهد که برخی از مسائل حمل و نقل کانتینر محلی شباهتهایی به مسائل مورد بررسی در تحقیق ما دارند. به طور خاص، این مسائل حمل و نقل به تحویل و جابجایی کانتینرها میپردازند و مسیریابی کامیونها را برای برآورده کردن تمام تقاضاها و در عین حال به حداقل رساندن هزینهها بهینه میکنند. زیرمجموعهای از این مطالعات، همانطور که در وانگ و ژانگ (2019) و وانگ و همکاران (2022) به آن اشاره شده است، به یک کامیون اجازه میدهد تا در طول سفر خود دو یا چند کانتینر را حمل کند. زمینههای مسئله آنها مشابه با مسئله ما در ارائه خدمات به چندین تقاضای مشتری در طول یک سفر بود، زیرا هر کانتینر را میتوان به عنوان یک تقاضای مجزا در نظر گرفت. با این حال، آنها محدودیتهای پنجره زمانی را در نظر نگرفتند و اندازه تقاضا را برای مشتریان مختلف یکسان فرض کردند. علاوه بر این، این مطالعات مربوط به مسائل حمل و نقل چند تریلری، ویژگی دسته بندی را در نظر نگرفتند که تفاوت بزرگی را در برنامهریزی عملیات نشان میدهد. همچنین چندین مطالعه حمل و نقل دیگر وجود دارد که برنامهریزی عملیات را تحت زمینه دسته بندی کامیونها مورد بحث قرار میدهند، مانند You و همکاران، 2020، Xue و همکاران، 2021 و Yan و همکاران (2023). با این وجود، این مطالعات فرض کردند که یک کامیون میتواند فقط یک کانتینر یا تقاضای مشتری را حمل کند، بنابراین برنامهریزی عملیات تحویل کانتینرها به طور کامل بررسی نشد. به طور خلاصه، اگرچه مطالعات حمل و نقل کانتینری فوق شباهتهایی با مسئله ما دارند، اما روشهای آنها را نمیتوان برای مسئله ما که نه تنها مسیرهای کامیونها، بلکه تخصیص مشتریان به هر کامیون و توالی آنها برای خدمترسانی را بهینه میکند، به کار برد.
سهم ما سه جنبه دارد: (1) این اولین مطالعهای است که برنامهریزی دستههای کامیون را برای یک مسئله مسیریابی وسیله نقلیه با ظرفیت شبکه جادهای بهینه میکند. این یک مسئله پیچیده است زیرا ما نه تنها شبکه جادهای و پتانسیل دستههای کامیون را در نظر میگیریم، بلکه این واقعیت را نیز در نظر میگیریم که هیچ مسیر از پیش تعیینشدهای برای کامیونها و تخصیصهای از پیش تعیینشدهای که هر کامیون به مشتریان خود خدمت خواهد کرد، وجود ندارد. (2) ما نه تنها هزینه اعزام وسیله نقلیه و مصرف سوخت در جاده را برای به تصویر کشیدن جامع هزینههای عملیاتی یک شرکت حمل و نقل در نظر میگیریم، بلکه تأثیر وزن کامیون را نیز در نظر میگیریم. این تأثیر فراتر از افزایش نرخ مصرف سوخت است. همچنین تأکید بر این نکته ضروری است که از آنجایی که صرفهجویی در انرژی بر اساس درصد محاسبه میشود، میزان صرفهجویی در دستهها با افزایش وزن به طور قابل توجهی بیشتر میشود. این امر نمایش دقیقتری از هزینههای سوخت را در زمینه مسائل حمل و نقل ارائه میدهد. (3) ما یک الگوریتم حل تکراری جدید پیشنهاد میکنیم که طرح «مسیر-سپس-زمانبندی»، برنامهنویسی پویا و روش ابتکاری درج اصلاحشده را به گونهای ترکیب میکند که مسائل عملی در مقیاس بزرگ را بتوان به طور کارآمد و دقیق حل کرد. (منبع).