جواب‌های استوار در مسئله مسیریابی آلودگی تحت عدم قطعیت تقاضا و زمان سفر

مقدمه :

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

مسئله مسیریابی وسیله نقلیه (VRP) از مسائل NP-hard است که که روش‌های حل دقیق قادر به حل این دسته مسائل در ابعاد بزرگ در زمان محاسباتی معقول نیستند. این موضوع اولین بار توسط  Dantzig و Ramser در سال ۱۹۹۵ ارائه شد و از آن زمان به بعد تحقیقات بسیاری در این زمینه انجام شد. مسئله مسیریابی وسیله نقلیه سنتی، به دنبال یافتن مسیر وسیله‌نقلیه برای پاسخ به تقاضای (معلوم) مشتریان و کاهش فاصله پیموده شده توسط وسایل نقلیه می‌باشد. ادبیات مربوط به این مسائل بسیار گسترده و دارای موضوعات بسیاری است که از جنبه‌ها و تصمیمات متفاوت بررسی شده و به طرق دقیق و با الگوریتم‌های ابتکاری مختلف حل شده اند. با افزایش نگرانی‌ها در مورد اثرات حمل و نقل بر محیط زیست، محققان به برنامه‌ریزی حمل و نقل جاده‌ای با در نظر گرفتن انتشار گازهای گلخانه‌ای پرداختند. در همین راستا تحقیقات اخیر مسئله مسیریابی وسیله نقلیه سبز و مسیریابی آلودگی یا Pollution Routing Problem) PRP) را ارائه داده اند. در این مقاله نیز به بررسی مسئله مسیریابی آلودگی پرداخته شده که هدف آن کاهش مصرف سوخت می‌باشد. تقاضا و زمان سفر غیر قطعی از مسائلی است که در این مقاله به آن پرداخته شده است. 

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

1. تقاضای غیر قطعی که تا به حال در مسائل مسیریابی وسیله نقلیه سبز به آن اشاره نشده است.
2. زمان سفر غیر قطعی متاثر از سرعت حرکت.
3. بکارگیری ۳ رویکرد استوار برای مواجهه با عدم قطعیت.

تعریف مسئله:

مسئله مورد بررسی در یک گراف کامل G(N,A)‌ تعریف شده است. N نشان دهنده مجموعه گره‌ها و گره صفر به عنوان انبار سیستم و (N(0 مجموعه مشتریان می‌باشد. A مجموعه مسیرها را نشان داده و تعداد وسایل نقلیه همگن که یک پارامتر قطعی است، برابر K و ظرفیت آن برابر Q می‌باشد. هر مشتری دارای تقاضای غیر منفی (q(i در بازه زمانی [a,b] است. سرویس باید به محض رسیدن به مشتری شروع شود اما اگر وسیله نقلیه‌ای زودتر از زمان بازه تعیین شده برسد باید تا زمان a صبر کرده و بعد عملیات سرویس را آغاز کند. فاصله عدم قطعیت به صورت زیر است که در کران پایین مقدار اسمی پارامترهای دارای عدم قطعیت از بخش غیر قطعی آن کم و در کران بالای بازه به آن اضافه می‌شود.  

تقاضای غیرقطعی به دلایل متفاوتی ایجاد می‌شود؛ بعضی موارد همچون سلیقه مشتریان، مد بازار، نیاز مشتری به محصولات متفاوت و تعداد رقبای بازار باعث تغییر تقاضای مشتریان بعد از ارسال سفارش می‌شود. همچنین شرایط مربوط به دنیای واقعی مثل ترافیک و ازدحام و آب و هوا می‌تواند منجربه افزایش زمان سفر شود. زمان سفر طولانی که به دلیل سرعت کم وسیله نقلیه باشد، باعث افزایش مصرف سوخت و اثرات CO2 می‌شود.

مصرف سوخت و اثرات CO2:

مدل PRP با یک تابع نرخ مصرف سوخت دقیق‌ توسط محققان توسعه داده شده است؛ که در فرمول 1 نرخ مصرف سوخت به صورت زیر محاسبه می‌شود. در این فرمول لاندا، الفا، گاما و بتا ضرایب ثابت مخصوص وسیله نقلیه و مسیر (مانند: شتاب، موتور، شیب و ...) هستند که در فاصله بین گره‌ها ضرب و بر سرعت خودرو تقسیم می‌شوند. برای در نظر گرفتن سرعت وسیله ‌نقلیه نیز، ۲ پارامتر سرعت کم و سرعت بالا تعریف شده است.

در حمل و نقل محموله‌ها، مصرف سوخت برای انتقال از یک مکان به مکان دیگر با میزان بار حمل شده رابطه مستقیم دارد. همانطور که در شکل 1 مشاهده می‌کنید، مصرف سوخت با دو فاکتور مهم (سرعت سفر و بار حمل شده) در ارتباط است. شرایط آب و هوایی، ترافیک و راننده در تمام حالت یکسان فرض شده است. زمانی که سرعت وسیله‌ نقلیه کم است مصرف سوخت، به علت استفاده نامناسب از سوخت، بسیار زیاد است. با افزایش سرعت، تا سطح مشخصی، مصرف سوخت کاهش می‌یابد. اما در سرعت‌های بالاتر مصرف سوخت به دلیل کشش ایرودینامیکی، دوباره افزایش می‌یابد. به علاوه شکل ۱ گویای این است که بار  وسیله ‌نقلیه نیز بر مصرف سوخت تاثیر‌گذار است و با افزایش میزان بار، مصرف سوخت افزایش می‌یابد.

 مدل ریاضی:

تابع هدف: میزان کل سوخت مصرف شده را با توجه به توضیحات مذکور (با استفاده از معادله ۱) کمینه می‌کند.

محدودیت (۶): بیان می‌کند که همه وسایل‌ نقلیه باید انبار را ترک کنند. محدودیت (۷) و (۸): مشخص می‌کند که همه مشتریان باید تنها یکبار دیده شوند. محدودیت (۹) و (۱۰): محدودیت‌های حذف زیرتور هستند. به این صورت که این محدودیت‌ها تضمین می‌کنند که تمام جریان‌ها از انبار آغاز شده به نقاط تقاضا برود و دوباره به همان انبار بازگردد. محدودیت (۱۱) و (۱۲): پنجره زمانی ملاقات مشتریان را مشخص می‌کنند. هر مشتری باید در بازه زمانی مربوط به خودش دیده شود و با در نظر گرفتن مدت سرویس دهی به مشتری i ملاقات مشتری بعدی مشخص شود. محدودیت (۱۳): این اطمینان را می‌دهد که فقط یک سطح سرعت (سرعت کم یا زیاد) برای هر کمان انتخاب شده است. محدودیت (۱۴) تا (۱۷): نامنفی بودن متغیرها و همچنین متغیرهای دودویی را نشان می‌دهند.

مدل‌سازی تقاضای غیر قطعی:

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

1. رویکرد بدینانه سخت (HWC)
2.  رویکرد بدبینانه نرم (SWC)
3.  رویکرد واقع‌گرایانه

در میان این ۳ دسته، رویکرد بدبینانه سخت بالاترین سطح محافظه کاری را دارد. به عبارت دیگر، جوابهای به دست آمده با این رویکرد همیشه و به ازای همه مقدارهای ممکن از پارامتر غیرقطعی، شدنی است. با توجه به مقدار تابع هدف، این رویکرد این اطمینان را می‌دهد که مقدار تابع هدف هیچگاه از فضای شدنی منحرف نمی‌شود. رویکرد HWC می‌تواند در مسائل مختلف مدیریت لجستیک استفاده شود. رویکرد بدبینانه نرم منعطف‌تر از رویکرد قبل است و تصمیم‌گیرنده می‌تواند سطح استواری را متناسب با هزینه‌های ایجاد شده، مشخص کند. رباست محدودیت شانسی (CCR) گونه‌ای منعطف‌تر از HWC است که دارای متغیر و محدودیت کمتری می‌باشد. خلاصه‌ای از هر کدام از رویکردها ارائه شده است:

1) رویکرد بهینه‌سازی استوار بدبینانه سخت:

این رویکرد توسط Ben-Tal  و Nemirovski (1998) تعریف شده است. بعدها این رویکرد توسط Sungur و همکاران به صورت مدل بهینه‌سازی استوار برای مسئله مسیریابی وسیله نقلیه با ظرفیت محدود و تقاضای غیر قطعی توسعه داده شد؛ هدف آنها مواجهه با عدم قطعیت و مقایسه جواب استوار با حالت قطعی بود که به دلیل در نظر گرفتن بیشترین مقدار تقاضا، مسئله به ازای همه سناریوها شدنی بود اما در همه مسائل مسیریابی آلودگی و مسائل مسیریابی وسیله نقلیه، جواب به دست آمده لزوما بدترین جواب تابع هدف نیست. برای روشن شدن این اختلاف این مقاله یک شبکه با ۴ گره (شکل ۲) را در نظر گرفته است که فاصله بین هر جفت گره ۱۰۰ واحد می‌باشد. در این مسئله ۱ وسیله نقلیه وجود دارد که از گره صفر شروع به حرکت کرده و به ۳ مشتری سرویس می‌دهد. تقاضای دقیق مشتریان نامعلوم و تنها بازه‌ای از آن مشخص است.

مشتری ۱ یا (q1)=[50,120] ، مشتری ۲ یا (q2)= [80,100] ، مشتری ۳ یا  (q3)= [90,100]

دو تابع هدف اصلی مسئله مسیریابی وسیله نقلیه در نظر گرفته شده است. تابع هدف اول (مدل اول) به دنبال کمینه کردن فاصله کلی و تابع هدف دوم (مدل دوم) به دنبال کمینه کردن وزن بارگیری شده و فاصله می‌باشد؛ محدودیت‌های هرکدام از آنها مشابه محدودیت ۶ تا ۱۰ و ۱۴ و ۱۵ این مقاله می‌باشد. این مدلها در ۲ مسئله با هم مقایسه شده اند. ۱) مشتریان به اندازه حد بالای تقاضایشان سرویس داده شوند. ۲) مشتریان به اندازه حد پایین تقاضایشان سرویس داده شوند. در هر دو مسئله، مدل اول ۲ مسیر بهینه دارد که آنها (0,1,2,3,0) و (0,3,2,1,0) با طول ۴۰۰، هستند. اما با توجه به جدول ۴ در مدل ۲ در هر مسئله، مسیرهای بهینه متفاوتی به دست آمده است. در این مدل با در نظر گرفتن وزن بارگیری شده، مقدار بهینه در هر سناریو تغییر می‌کند. مسیر (0,1,2,3,0) بهینه مسئله اول با ۶۲۰۰۰ واحد و مسیر (0,3,2,1,0) بهینه مسئله دوم با ۸۰۰۰۰ واحد می‌باشد. در نتیجه مدل ارائه شده توسط Sungur و همکاران برای مدل‌سازی رویکرد بدبینانه سخت در مسائل مسیریابی وسیله نقلیه مناسب نیست، زیرا همانطور که در بالا توضیح داده شد، با اضافه کردن قیود جدید به آن تابع هدف‌های متفاوتی به دست آمده است.

 این مقاله برای مدل‌سازی رویکرد بدبینانه سخت تابع هدف و محدودیت‌ها را با تغییراتی بازنویسی کرده است که در ادامه توضیح داده خواهد شد:

تابع هدف به صورت تابع هدف اصلی مسئله تعریف شده با این تفاوت که برای پیاده کردن رویکرد استوار، متغیر f’(i,j) جایگزین متغیر f(i,j) می‌شود. متغیر f’(i,j) کل جریان‌های عبوری از i به j را نشان می‌دهد اگر هر مشتری کران پایین تقاضا خود را دریافت کند و وسیله نقلیه با حد بالای تقاضا بارگیری شده باشد. متغیر f(i,j) کل جریانهای عبوری از i به j را نشان می‌دهد اگر هر مشتری کران بالای تقاضای خود را دریافت کند و وسیله نقلیه با حد بالای تقاضا بارگیری شده باشد. 

 محدودیت‌ها نیز شامل محدودیت‌های ۶ تا ۸ و ۱۱ تا ۱۷ مدل اصلی، به علاوه محدودیت‌های زیر هستند:

محدودیت (۲۱) و (۲۲): جریانهای بدبینانه سخت و محدودیت زیرتور را نشان می‌دهد. محدودیت (۲۳) و (۲۴): حدود مجاز بارگیری را نشان می‌دهند. محدودیت (۲۵) و (۲۶): محدودیت‌های بالانس جریان هستند و ارتباط f(i,j) و f’(i,j) را نشان می‌دهند.

2) رویکرد بهینه‌سازی استوار بدبینانه نرم:

در این رویکرد برای کنترل سطح محافظه کاری یک پارامتر جدید با عنوان بودجه عدم قطعیت یا قیمت استواری (توسط Bertsimas و  Sim) تعریف شده است. این پارامتر می‌تواند مقدارهای متفاوتی در بازه [(N(0 و 0] داشته باشد. حد بالای بازه بیشترین سطح محافظه کاری را نشان می‌دهد. این رویکرد از رویکرد قبل انعطاف بیشتری دارد و امکان نقض محدودیت در آن وجود دارد. همچنین متغیر دودویی جدیدی برای کنترل درجه محافظه کاری در هر محدودیت تعریف شده که با در نظر گرفتن حد بالایی از پارامتر غیر قطعی، این متغیر برابر ۱ می‌شود و در غیر اینصورت برابر صفر است. لازم به ذکر است که جمع متغیرهای دودویی جدید برابر پارامتر بودجه عدم قطعیت است. تابع هدف و محدودیت‌های این رویکرد به صورت زیر است:

تابع هدف این رویکرد مانند رویکرد قبلی است و محدودیت‌های آن مانند محدودیت‌های (۲)، (۳)، (۵) و (۲۰) به علاوه محدودیت‌های زیر می‌باشد:

محدودیت (۲۸) تا (۳۱): مانند محدودیت‌های ۲۲ تا ۲۴ و ۲۶ با در نظر گرفتن متغیر دودویی جدیدی که برای دریافت حد بالا تقاضا مشتریان می‌باشد. محدودیت (۳۲): این اطمینان را می‌دهد که تنها تعداد مشخصی از مشتریان مقدار کران بالای تقاضایشان را دریافت می‌کنند؛ حداکثر میزان این مقدار مشخص از مشتریان به اندازه گره‌ها می‌باشد.

3) رویکرد بهینه‌سازی استوار محدودیت شانسی:

اگر توزیع احتمالی تقاضا معلوم باشد، می‌توان مدلی بر پایه‌ی برنامه‌ریزی محدودیت شانسی ایجاد کرد. زمانی که هدف ایجاد جواب‌های شدنی، حداقل برای (الفا -۱)٪ از سناریوها باشد، فرمول رویکرد بدبینانه سخت می‌تواند با تغییر محدودیت‌های ۲۱ تا ۲۴ و ۲۶ به استوار محدودیت شانسی تبدیل شود. اگر برای پارامترهای تقاضا یک توزیع یکنواخت در نظر گرفته شود، مدل استوار محدودیت شانسی دارای تابع هدف مربوط به رویکرد بدبینانه سخت و محدودیت‌های آن مانند موارد ۶ تا ۸، ۱۱ تا ۱۷، ۲۱، ۲۵ و ۲۷ به علاوه محدودیت‌های مربوط به رویکرد بدبینانه سخت است که ضریب اطمینانی برای شدنی بودن آنها تعریف شده است. 

نتایج:

نمونه به کار رفته در این مقاله شهرهایی از انگلستان است که به صورت تصادفی انتخاب شده و فاصله واقعی بین آنها در نظر گرفته شده است. پنجره زمانی و زمان سرویس‌دهی به صورت تصادفی تولید شده اند. اندازه مدل بین ۱۰ تا ۲۰ مشتری تعیین شده به این صورت که ۳ دسته‌ی (۱۰ گره، ۱۵ گره و ۲۰ گره) ۵ تایی از شهرها به عنوان نمونه در نظر گرفته شده است. در رویکرد بدبینانه نرم به هر شهر سطوح استواری با مقادیر صفر، کم، متوسط و زیاد و به رویکرد بدبینانه سخت بدترین حالت و به محدودیت شانسی ۲ سطح اطمینان کم و زیاد داده شده‌ است. مدل در نرم افزار AIMMS با ۲ سطح عدم قطعیت کم و زیاد حل شده است.

 نتایج سطح عدم قطعیت کم:

عدم قطعیت کم تقاضا (۱۰ درصد) و اثر آن بر مصرف سوخت از مواردی است که مقاله به تحلیل آن پرداخته است. از مقایسه جواب‌های قطعی و استوار می‌توان متوجه شد که جواب‌های استوار دارای مسیرهایی با قابلیت اطمینان بالاتر اما با افزایش اندک مصرف سوخت می‌باشد. جواب بهینه مدل قطعی (اسمی) شامل ۲ مسیر است. در هر مسیر وسیله نقلیه ممکن است با احتمال 0.5 با کمبود مواجه شود و با احتمال 0.25 شدنی است؛ اما مدل استوار در همه شرایط، تنها با 2.58 متر افزایش فاصله، 2.13 لیتر افزایش در مصرف سوخت و 8.9 کیلوگرم افزایش اثرات CO2، همواره شدنی است. همانطور که در جدول ۸ مشاهده می‌کنید، نتایج به دست آمده در همه سناریوهای استوار با رویکرهای متفاوت، بررسی شده است. متوسط افزایش مصرف سوخت در رویکرد بدبینانه نرم، در سطوح استواری صفر، کم، متوسط و زیاد، به ترتیب برابر 1.18، 1.37، 1.99 و 3.13 لیتر می‌باشد. متوسط افزایش مصرف سوخت در رویکرد بدبینانه سخت برابر 5.99 لیتر است و متوسط افزایش مصرف سوخت در دو سطح اطمینان کم و زیاد به ترتیب برابر 4.97 و 5.96 لیتر می‌باشد. 

نتایج سطح عدم قطعیت زیاد:

 عدم قطعیت زیاد تقاضا (50 درصد) و اثرات مربوط به مصرف سوخت نیز تحلیل شده که در مقایسه با جواب قطعی افزایش اندک مصرف سوخت را نشان داده است. با توجه به جدول ۹، متوسط افزایش مصرف سوخت در رویکرد بدبینانه نرم، در سطوح استواری صفر، کم، متوسط، زیاد، به ترتیب برابر 5.78، 6.68، 10.13 و 18.90 لیتر می‌باشد. متوسط افزایش مصرف سوخت در رویکرد بدبینانه سخت برابر 34.55 لیتر است و متوسط افزایش مصرف سوخت در دو سطح اطمینان کم و زیاد به ترتیب برابر 30.22 و 34.31 می‌باشد. با توجه به نتایج به دست آمده می‌توان ادعا کرد که تقاضای غیر قطعی نقش مهمی در برنامه‌ریزی حمل و نقل دارد. با استفاده از رویکردهای استوار مصرف سوخت افزایش می‌یابد اما از طرف دیگر قابلیت اطمینان سیستم افزایش یافته و از ایجاد هزینه‌هایی مثل کمبود جلوگیری می‌کند. 

نتایج اثرات عدم قطعیت زمان سفر:

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

 نتیجه‌گیری:

هدف عمده مسائل مسیریابی وسیله نقلیه کاهش تعداد وسیله نقلیه و کم کردن فاصله و هزینه‌های مسیریابی می‌باشد. موردی که اخیرا در این مسائل به آن توجه می‌شود، اثرات حمل و نقل بر محیط زیست است و در این زمینه تحقیقاتی انجام شده است. در این مقاله نیز به بررسی یکی از مسائل مسیریابی وسیله نقلیه سبز، با عنوان مسیریابی آلودگی پرداخته شده است. تقریبا اکثر تحقیقات انجام شده در زمینه مسیریابی وسیله نقلیه سبز با پارامترهای قطعی انجام شده اما این مقاله با استفاده از تکنیک‌های استوار نشان داده که با مواجهه با عدم قطعیت می‌توان جوابهای قابل اطمینان‌تری به دست آورد. در همین راستا ۳ رویکرد بهینه‌سازی استوار برای مواجهه با عدم قطعیت در تقاضا و زمان سفر ارائه شده است. اگرچه نتایج، گویای مصرف سوخت بیشتر مدل استوار (۳۰ لیتر برای نمونه با ۱۰ گره، 5۰ لیتر برای نمونه با ۱۵ گره و ۶۰ لیتر برای نمونه با ۲۰ گره) نسبت به مدل قطعی است، اما ریسک مواجهه با کمبود و عدم ارضای تقاضا که خود باعث افزایش هزینه می‌شود را تا حد زیادی کاهش می‌دهد.

پیشنهادات آتی:

به عنوان پیشنهاد آتی می‌توان به استفاده از مدل مکانیابی و مسیریابی اشاره کرد که در آن به تغییر مکان انبارها و یا اضافه کردن تسهیلات پرداخته شود. مورد دیگری که می‌توان در نظر گرفت نوع وسیله نقلیه است که از وسایل نقلیه سبز با تکنولوژی بالاتر استفاده شود.