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

چکیده:

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

 مقدمه:

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

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

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

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

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

       II.            استفاده از روش ترکیبی فراابتکاری-ریاضی به نام جستجوی همسایگی بزرگ برای حل مدل توسعه داده شده

مرور ادبیات

دکر و همکاران در سال 2012 یک مروری کلی روی مباحثی نظیر حمل و نقل چند وجهی، مدل‌های انتخاب نحوه حمل و نقل، بهره برداری و انتخاب ناوگان، سیستم های توزیع هوشمند و انتخاب سوخت داشتند. در زمینه مرتبط با کاهش انتشار آلاینده ها، بکتاش ولاپورته در سال 2011، بحثی را به عنوان مسیریابی وسایل نقلیه در زمینه آلودگی (PRP) که تعمیمی از مساله مسیریابی وسایل نقلیه کلاسیک با پنحره زمانی می‌باشد، را ارائه دادند.

در اوایل قرن 21، پالایشگاه‌ها تمرکز زیادی بر روی حدف کردن سرب از گازوئیل، با هدف حفظ کیفیت هوا انجام دادند. سوخت های زیستی می‌توانند به آسانی با گازوئیل های استاندارد ترکیب شوند اگر چه این تکنولوژی به خاطر استفاده از موتورهای مرتبط با آن اندکی گران می‌باشد. وسایل نقلیه الکتریکی که دوستدار محیط زیست هستند تقریبا هیچ آلودگی توسط موتور‌های آنان صورت نمی‌گیرد. اگر چه آنها دارای محدودیت هایی در میزان مسافت طی شده هستند اما از آنها در جابجایی های درون شهری برای انتقال کالاها استفاده می‌شود. به همین دلیل برای تامین مجدد انرژی برای این نوع از خودرو ها، باید مراکز تامین مجدد سوخت الکتریکی در نزدیکی محلی که انتظار می‌رود که تمام شود احداث شوند. تحقیقات زیادی بر روی مکانیابی بهینه مراکز سوختگیری انجام شده است که می‌توان به کارهای نیکولاس و همکاران سال 2004، کوبی و لیم سال 2005، 2007 و لین و همکاران در سال 2008 اشاره کرد. تنها تعداد زیادی از مقالات تحقیقاتی مرتبط با وسایل نقلیه با سوخت های چند‌گانه را بررسی کرده اند. در مقاله گونکالوز و همکاران در سال 2011، آنها یک مساله مسیریابی ناوگان برداشت و گذاشت را با ناوگان چند گانه که از هر دو نوع سوخت الکتریکی و سنتی استفاده کردند، را بررسی کردند که هدفشان در این مقاله کمینه کردن هزینه های کل می‌باشد. در مقاله فیلیپ و همکاران در سال 2014 ، تکنولوژی شارژ مجدد چندگانه با زمان و هزینه شارژ مجدد متفاوت ارائه شده است.

تعریف مساله:

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

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

محدودیت ها و تابع هدف:

تابع هدف در رابطه (1) تعریف شده است. محدودیت (2) بیان می‌کند که هر مشتری دقیقا یکبار ملاقات می‌شود. محدودیت (3) بیان می کند که هر مرکز سوختگیری دقیقا یکبار ملاقات شود. پیوستگی مسیر توسط محدودیت (4) تضمین می‌شود. محدودیت های (5) و (6) حداکثر تعداد مسیرها را نشان می‌دهند. زمان رسیدن به هر نقطه توسط محدودیت (7) اعمال می‌شود. محدودیت های (8) و (9) تضمین می‌کنند که هر وسیله نقلیه دیرتر از زمان معین شده به انبار مرکزی برنمی‌گردد. سطح باتری در حال شارژ در زمان رسیدن به هر نقطه توسط محدودیت (10) تضمین می‌شود. زمان و سطح باتری توسط محدودیت‌های (7) و (10) به ترتیب، برای جلوگیری از احتمال شکل گرفتن زیرتور، تضمین می‌شود. محدودیت (11) میزان سطح باتری را موقع خروج از انبار و ورود به انبار برابر مقدار  قرار می‌دهد. محدودیت(12) به این قضیه اشاره دارد که باتری باقی مانده برای رسیدن به انبار مرکزی و یا مراکز سوختگیری کافی نباشد، بقیه مسیر توسط سوخت سنتی و با هزینه‌ی بیشتری طی می‌شود. محدودیت های (13) و (14) محدوده متغیر ها را نشان می‌دهد.

روش حل:

الگوریتم جستجوی همسایگی بزرگ

الگوریتم مربوطه طبق آنچه در ادامه گفته می‌شود عمل می‌کند. روند کار با یک جواب موجه شروع می‌شود. در هر تکرار دو مسیر تخریب می‌شوند و مدل دوباره اجرا می شود با یک فرجه زمانی (در حدود 10 ثانیه) روی آن دسته از مشتریانی که قبلا در آن مسیر ها بودند در حالی‌که باقی مسیرها بدون تغییر باقی می‌مانند. اگر تعداد مشتری های درگیر کم باشد، مدل قادر به یافتن جواب بهینه (یا نزدیک بهینه) در زمان خیلی کوتاه می‌باشد. روند کار زمانی تمام می‌شود که دیگر هیچ بهبودی نمی‌تواند از تخریب دو مسیر به دست آید یا زمانی که به تعداد معینی از تکرار‌ها برسد. در الگوریتم های جستجوی همسایگی قدیمی، تنها بخش کوچکی از همسایگی جستجو می‌شود در حالیکه در این روش، عملگر تخریب یک آشفتگی را در جواب ایجاد می‌کند که منجر به واگرایی بیشتر در فرایند جستجو می‌شود. نیاز می باشد تا مجموعه های زیر را تعریف کنیم:

سودوکد الگوریتم به شکل زیر می‌باشد:

محاسبات عددی:

محاسبات عددی برای دو دسته مساله انجام می‌گیرد. مساله با اندازه کوچک شامل 20 مشتری و مساله با ابعاد بزرگ شامل اندازه متغیر 100 تا 500 مشتری.

جدول زیر مقایسه بین روش‌های موجود در ادبیات و روش پیشنهادی این مقاله را نشان می‌دهد. ( برای 20 مشتری، 3 ایستگاه سوختگیری و 10 حالت مختلف)