استفاده از رویکرد استوار در مسئله مسیریابی آلودگی تحت عدم قطعیت گذاشت و برداشت

 

مقدمه:

این مقاله مانند ۳ مقاله قبل به موضوع مسیریابی آلودگی یا PRP (Pollution routing problem) پرداخته است. دلیل اصلی توجه محققان به این مسئله افزایش انتشار گاز CO2، که یکی از عناصر گازهای گلخانه‌ای است، می‌باشد. انتشار بیش از حد این گاز در هوا باعث ایجاد مشکلاتی در چرخه طبیعی اکوسیستم می‌شود. فعالیت‌های انسانی مانند تولید انرژی و حمل و نقل با سوزاندن سوخت‌های فسیلی، عامل اصلی انتشار CO2 هستند. حمل و نقل جاده‌ای ۷۸ ٪ از کل گازهای گلخانه‌ای انتشار یافته در هوا را شامل می‌شود و همین باعث نگرانی در میان دانشمندان و محققان شده تا با استفاده از روش‌ها و مدل‌های پیشنهادی بتوانند میزان آلودگی را کاهش دهند.

مسئله مسیریابی وسیله نقلیه یا VRP (Vehicle routing problem) مجموعه بهینه‌ای از مسیرهایی که باید توسط ناوگانی از وسیله نقلیه، برای ارائه خدمات به مشتریان، طی شود را مشخص می‌کند. حرکت وسایل نقلیه در این مسئله باید از انبار شروع شده و به آن بازگردد. نوع کلاسیک VRP، مسئله مسیریابی وسیله نقلیه با ظرفیت محدود یا CVRP (Capacitate VRP) است که در آن ارسال تقاضای مشتریان با توجه به ظرفیت وسیله نقلیه انجام می‌شود. نوع رایج دیگر VRP، مسئله مسیریابی وسیله نقلیه با پنجره زمانی یا VRPTW (VRP with time window) است که در آن همه مشتریان باید در بازه تعیین شده (پنجره زمانی مربوط به مشتری) ملاقات و تقاضایشان برآورده شود.

 مرور ادبیات:

از جمله مقالاتی که در زمینه مسیریابی انجام شده است می‌توان به مقاله Negate و همکاران (۲۰۱۰) اشاره کرد؛ ؛ این مقاله یک مدل مسئله مسیریابی وسیله نقلیه ارائه کرده و به ازای نقض محدودیت پنجره زمانی، جریمه‌ای را در نظر گرفته است. الگوریتم استفاده شده برای حل مدل Memetic بوده و نتایج حاصل از آن نشان می‌دهد که الگوریتم توسعه داده شده، عملکرد خوبی داشته است. Jeon و همکاران (۲۰۰۷) یک مسئله مسیریابی وسیله نقلیه با گذاشت برداشت تعریف کرده اند و که این مسئله چند انباره، double trip و با وسایل نقلیه ناهمگن در نظر گرفته شده و با الگوریتم ژنتیک حل شده است. Gen و Tersan (۲۰۱۲) برای طراحی مسئله واقعی لجستیک معکوس، مدل مسیریابی وسیله نقلیه با عملیات گذاشت و برداشت همزمان را ارائه کرده اند. این مدل با الگوریتم ژنتیک حل شده و نتایج به دست آمده دقت مدل را اثبات می‌کند. نوع دیگری از مقالات مسیریابی وسیله نقلیه علاوه بر کاهش هزینه اقتصادی به تاثیرات محیط زیستی نیز توجه کرده اند. Goksal و همکاران (۲۰۱۳) مسئله مسیریابی وسیله نقلیه با گذاشت و برداشت همزمان را ارائه داده و با روشی ابتکاری بر پایه‌ی Practical swarm مسئله را حل کرده است. Erdugan و Miller Hooks (۲۰۱۲) یک مدل ریاضی ارائه کرده است که در آن با کمینه کردن فاصله‌ها سعی شده تا میزان مصرف سوخت را حداقل کند. Ubeda و همکاران (۲۰۱۱) مدلی بر پایه فاصله ارائه و تاثیرات آن بر مصرف سوخت را تحلیل کرده اند. این تحقیق نشان می‌دهد که تعریف مسیرهای برگشت، هزینه مسافت‌های بدون بار را هم از نظر محیط زیستی و هم اقتصادی کاهش می‌دهد. Suzuki (۲۰۱۱) در مقاله‌اش نشان داد که با کم کردن فاصله و بارگیری بیشتر مصرف سوخت کاهش می‌یابد. Bektas و Laporte (۲۰۱۱) یک مدل تحت عنوان «مسئله مسیریابی آلودگی» ارائه داد و در آن مقایسه‌ای بین پارامترهای بار، سرعت و هزینه‌های محیط زیستی انجام داده است. 

 

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

1. تعریف جریمه‌ نقض محدودیت پنجره زمانی گره‌های برداشت برای کاهش زمان سفر، مصرف سوخت و انتشار CO2.
2. استفاده از محدودیت پنجره زمانی در مسئله مسیریابی وسیله نقلیه با عملیات گذاشت و برداشت برای کاهش زمان سفر رسیدن به گره‌های تحویل گیرنده.
3. استفاده از بهینه‌سازی استوار در محدودیت‌ها و با توجه به سرعت وسیله نقلیه به عنوان یک پارامتر غیرقطعی در مدل. این عدم قطعیت به ترافیک مربوط می‌شود و شامل توقف در پمپ بنزین و چراغ‌های راهنمایی می‌شود.
4. هزینه مصرف سوخت و انتشار گاز CO2 متغیر در نظر گرفته شده است.
5. از مفهوم استوار برای زمان سرویس دهی به مشتریان در شرایط متفاوت استفاده شده است.
6. ویژگی‌های فیزیکی وسیله نقلیه مثل سطح روبه‌روی وسیله نقلیه، وزن، شیب جاده در مدل در نظر گرفته شده است.

تعریف مسئله:

در این مقاله به یک مسئله مسیریابی وسیله نقلیه آلودگی با گذاشت و برداشت و پنجره زمانی (TWPDPRP) پرداخته شده است. این مسئله دارای ۲ گروه گره است. گروه اول مشتریانی است که باید بار آنها برداشته شود و گروه دوم مشتریانی است که باید بار به آنها تحویل داده شود. مدل برای انجام سرویس چند وسیله نقلیه در نظر گرفته است. همانطور که در شکل ۱ نشان داده شده، وسیله نقلیه بعد از بارگیری از انبار و سپس دریافت از مشریان، شروع به توزیع بار به مشتریانی می‌کند که تقاضا دریافت بار را دارند. میزان کالایی که هر وسیله نقلیه از گره اول یعنی انبار بارگیری می‌کند برابر با میزان تقاضای گره‌های تحویل گیرنده است که در طول مسیر ملاقات می‌شوند، منهای کالاهایی که از گره‌های برداشت جمع آوری شده است. اما اگر محصولاتی که از مشتریان برداشت شده است بیشتر یا برابر میزان تقاضا مشتریان تحویل گیرنده باشد، وسیله نقلیه خالی از انبار حرکت می‌کند. در این مقاله یک مسئله برنامه‌ریزی خطی عددصحیح مختلط یا MILP تحت عدم قطعیت ارائه شده است، که در آن مسائل مربوط به انتشار گازهای گلخانه‌ای قید شده است.

 

مفروضات:

1. همه گره‌های گذاشت و برداشت باید ملاقات شوند. بارهای اضافی می‌توانند در آخر مسیر توسط وسیله نقلیه به انبار بازگردانده شوند.
2. مکان انبار و گره مشتریان ثابت و تعریف شده است.
3. همه وسایل نقلیه بعد طی کردن کل مسیر به انبار باز می‌گردند.
4. هر وسیله نقلیه دارای ظرفیت مشخص و محدود است.

تابع هدف: تابع هدف کل هزینه‌ها را که شامل ۶ بخش می‌شود، کمینه می‌کند. ۳ بخش اول هزینه مصرف سوخت و هزینه انتشار CO2 را اندازه‌گیری می‌کند که در آن شرایط جاده مثل شیب در نظر گرفته می‌شود. وزن وسیله نقلیه، میزان باری که حمل می‌کند، سطح روبه‌روی وسیله نقلیه، چگالی هوا، شتاب، سرعت در مصرف سوخت تاثیر گذار است. بخش چهارم، هزینه‌ی راننده در هر مسیر را محاسبه می‌کند و ۲ مورد آخر دیر رسیدن یا زودرسیدن به گره برداشت را جریمه می‌کند و هزینه برای آن در نظر می‌گیرد.

محدودیت (۴): این اطمینان را می‌دهد که همه وسایل نقلیه حرکت خود را از انبار آغاز می‌کنند. محدودیت (۵): این اطمینان را می‌دهد که همه وسایل نقلیه به انبار بازمی‌‌گردند. محدودیت (۶) و (۷): بیان می‌کند که هر گره باید تنها یکبار ملاقات شود.

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

 محدودیت (۱۰): کل زمان سفر در یک تور توسط یک فرمول خطی که از یک فرمول غیر خطی مشتق شده است به دست می‌آید. محدودیت (۱۱): تعادل جریان کالا در این محدودیت بیان شده است. محدودیت (۱۲): تضمین می‌کند که میزان بار هر وسیله نقلیه از ظرفیت آن فراتر نباشد. محدودیت (۱۳) و (۱۴): این محدودیت‌ها بیان می‌کنند که مشتریانی که تقاضای برداشت کالا دارند باید قبل از مشتریانی که تقاضای دریافت کالا دارند ملاقات شوند. 

محدودیت (۱۵): محدودیت پنجره زمانی در این رابطه بیان شده است. محدودیت (۱۶) و (۱۷): محدودیت زود رسیدن و یا دیر رسیدن به هر گره را بیان می‌کند. محدودیت (۱۸): میزان باری که باید از انبار (در ابتدای مسیر) بارگیری شود را نشان می‌دهد. محدودیت (۱۹) و (۲۰): متغیرهای تصمیم غیر منفی و دودویی را نشان می‌دهد.

مدل ریاضی استوار:

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

این رویکرد با استفاده از بدترین مقدار در پارامترهای غیر قطعی (در محدودیت ۲۵) در بدترین شرایط نیز موجه می‌باشد. همتای استوار برای محدودیت‌های دارای عدم قطعیت به صورت زیر نوشته می‌شود که به ازای همه سطوح عدم قطعیت شدنی هستند. مدل استوار به صورت زیر است که تابع هدف قبلی به همراه اتا مریوط به هر پارامتر غیر قطعی نوشته شده است. اتاهای نوشته شده، بازه هر پارامتر غیرقطعی را نشان می‌دهند.

محدودیت‌های همتای استوار به محدودیت‌های مدل اصلی که قبلا توضیح داده شد اضافه می‌شود و به شرح زیر است. همتای استوار به ازای تمام پارامترهای غیرقطعی تعریف می‌شود. ۴ محدودیت اول مربوط به پارامتر غیرقطعی هزینه انتشار گاز کربن دی اکسید است. ۲ محدودیت اول، بازه عدم قطعیت پارامتر هزینه انتشار را به ازای مسیرهای طی شده از i به j با وسیله نقلیه k و ۲ محدودیت آخر بازه همین پارامتر را به ازای بار حمل شده از i به j با وسیله نقلیه k را نشان می‌دهد. محدودیت‌های بعدی نیز به همین شکل به ترتیب مربوط به پارامتر غیر قطعی هزینه مصرف سوخت و زمان سفر می‌باشد. 

نتایج محاسباتی:

آزمایش عددی بر روی ۹ مسئله با ابعاد متفاوت انجام شده که در هر کدام ۶ سطح عدم قطعیت در نظر گرفته شده است. سپس ۶ مسئله با ۳ سطح عدم قطعیت برای ارزیابی جواب قطعی و استوار ارائه شده است. برای تحلیل واقع نمایی‌های تصادفی از میانگین و انحراف معیار مربوط به هر مدل استفاده کرده است.

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

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

1. تحلیل حساسیت هزینه انتشار CO2: با افزایش هزینه انتشار CO2 مقدار تابع هدف نیز افزایش می‌یابد. (شکل ۲)
2. تحلیل حساسیت تعداد گره‌های گذاشت و برداشت: تعداد مشتریان گذاشت و برداشت بر مقدار تابع هدف اثر گذار است. همانطور که در شکل ۳ مشخص است، کمترین تعداد مشتریانی که تقاضای برداشت کالا دارند، تابع هدف را به حداکثر مقدار آن می‌رساند. زیرا متوسط مقدار بار حمل شده در طول مسیر و زمان سفر بیشتر می‌شود که باعث افزایش مصرف سوخت نیز می‌شود. اما با افزایش گره‌های برداشت مقدار تابع هدف کاهش می‌یابد که این به دلیل کاهش میزان بار حمل شده و زمان سفر می‌باشد. زیرا بارگیری کالا برای مشتریانی که تقاضای تحویل کالا دارند به جای انبار از کالاهایی که در طول مسیر از گره‌های برداشت جمع آوری شده است تامین می‌شود. این روند تا زمانی ادامه دارد که تابع هدف کمترین و بهینه‌ترین تعداد مشتریان برداشت و گذاشت را پیدا کند. اگر برداشت‌ها مداوما افزایش پیدا کند مقدار تابع هدف دوباره افزایش می‌یابد چراکه باعث افزایش میزان بار، طول سفر و  همچنین مصرف سوخت می‌شود. (شکل ۳ و ۴)                                                                                                               
3. تحلیل حساسیت ظرفیت وسیله نقلیه: همانطور که در شکل ۵ مشخص است افزایش ظرفیت تا یک حد مشخصی نمی‌تواند مقدار تابع هدف را تغییر دهد. اما زمانی که ظرفیت به ۵۵ تن برسد وسیله نقلیه می‌تواند مشتریان بیشتری را سرویس دهد در نتیجه تعداد وسیله نقلیه موردنیاز کاهش می‌یابد. شکل ۶ نیز گویای این است که مسئله می‌تواند قبل از رسیدن به ظرفیت ۵۵ تن با ۳ یا ۴ وسیله نقلیه حل شود. به عبارت دیگر ۳وسیله نقلیه می‌توانند همه مشتریان را سرویس دهد اما مصرف سوخت زیادی را به همراه خواهد داشت، بنابراین ۴ وسیله نقلیه گزینه مناسب‌تری است. زمانی که ظرفیت به ۵۵ تن برسد ۳ وسیله نقلیه به گونه‌ای مسیریابی می‌شوند که مقدار تابع هدف آن مشابه زمانی باشد که از ۴ وسیله نقلیه (اما با ظرفیت زیر ۵۵ تن) استفاده کردیم.                                       

نتیجه گیری:

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