الگوریتم جستجوی بزرگ همسایگی انطباقی در مسئله مسیریابی آلودگی

مقدمه:

حمل و نقل جادهای عامل اصلی انتشار گاز کربن دی اکسید است که مستقیما از مصرف سوخت ایجاد میشود. مصرف سوخت به پارامترهای متفاوتی مانند سرعت، بار و شتاب وسیله نقلیه وابسته است. مسئله مسیریابی آلودگی (PRP) نوع توسعه یافته مسئله مسیریابی وسیله نقلیه (VRP) با پنجره زمانی است که به دنبال مسیریابی تعدادی وسیله نقلیه برای ارائه خدمات به مجموعهای از مشتریان دارای پنجره زمانی میباشد. در این نوع مسائل هدف تعیین سرعت بهینه در هر مسیر، کاهش مصرف سوخت و هزینههای راننده میباشد. اینگونه مسائل Np-hard هستند و روشهای دقیق قادر به حل آنها نیست به همین علت این مقاله الگوریتم جستجوی بزرگ همسایگی انطباقی که یک روش ابتکاری است را پیشنهاد داده است. تفاوت الگوریتم به کار رفته در این مقاله با حالت کلاسیک آن استفاده از الگوریتم بهینهسازی سرعت (SOA) است که در آن سرعت بهینه (در مسیر داده شده) محاسبه میشود؛ این عمل باعث کاهش مصرف سوخت، انتشار گازهای سمی و هزینههای راننده میشود. همچنین این الگوریتم میتواند به تنهایی در مسائل مسیریابی وسیله نقلیه با پنجره زمانی برای بهینهسازی سرعت استفاده شود.

مدل ریاضی مسئله مسیریابی وسیله نقلیه:

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

برای کاهش انتشار CO2 در محیط و کاهش مصرف سوخت نیاز به روشی برای محاسبه میزان مصرف سوخت وسایل نقلیه وجود دارد که انواع متفاوتی از مدلهای مصرف سوخت در ادبیات موجود است. برای محاسبه نرخ مصرف سوخت از فرمول (۱) استفاده می شود. که در آن k عامل اصطکاک موتور (کیلوژول بر دور بر ثانیه)، V میزان جابهجایی موتور (لیتر) و N دور موتور (رادیان بر ثانیه) هستند. رابطه (۲) توان خروجی موتور را محاسبه میکند. برای محاسبه توان موتور (موجود در فرمول ۲) از فرمول (۳) استفاده میشود. در فرمول (۳) v سرعت وسیله نقلیه (متر بر ثانیه)، M وزن وسیله نقلیه (کیلوگرم)، g ثابت گرانشی زمین (متر بر مجذور ثانیه)، تتا شیب جاده (رادیان)، A ناحیه سطح رو به روی وسیله نقلیه (متر مکعب) میباشد.

شکل ۱ منحنی مصرف سوخت مربوط به فرمول (۶) را در سرعت ۲۰ تا ۱۰۰ کیلومتر بر ساعت در ۱۰۰ کیلومتر مسیر را نشان میدهد. این شکل جمع ۲ جز را نشان میدهد که شامل منحنی خط چین شده که از معادله (۴) که در آن Kضریب اصطکاک موتور، N دور موتور و V حجم جابهجایی موتور میباشد. همچنین منحنی نقطه چین که از رابطه (۵) به دست آمده اند، میباشد. جز اول تابع (KNV) مختص سطوح پایین سرعت (کمتر از ۴۰ کیلومتر بر ساعت) و جز دوم تابع یاP(t) مختص سطوح بالا سرعت (بیشتر از ۴۰ کیلومتر بر ساعت) میباشد. در این مقاله وسیله نقلیه با سرعت کم در نظر گرفته شده است که مصرف سوخت زیاد را به همراه دارد پس از معادله (۶) به عنوان فرمول نرخ مصرف سوخت استفاده شده است. فرمول (۶) نرخ مصرف سوخت به صورت زیر محاسبه میشود. در این فرمول لاندا، الفا، گاما و بتا ضرایب ثابت مخصوص وسیله نقلیه و مسیر (مانند: شتاب، موتور، شیب و ...) هستند که در فاصله بین گرهها ضرب و بر سرعت خودرو تقسیم میشوند.

فرمولنویسی برنامهریزی عدد صحیح:

تابع هدف: به دنبال کمینه کردن هزینههای مربوط به مصرف سوخت، بار و حقوق رانندگان میباشد. عبارات (۷) تا (۱۰) تابع هدف مربوط به حداقل کردن مصرف سوخت با استفاده از فرمول ۶ است. عبارت (۷) مربوط به سرعت ۴۰ کیلومتر بر ساعت و کمتر میباشد. عبارات (۸) و (۹) مربوط به هزینههای ناشی از وزن خالص وسیله نقلیه و وزن بار آن میباشد. عبارت (۱۱) مربوط به هزینه حقوق رانندگان میباشد.

محدودیت (12): بیان میکند که همه وسایل نقلیه باید انبار را ترک کنند. محدودیت (13) و (14): مشخص میکند که همه مشتریان باید تنها یکبار دیده شوند. محدودیت (15) و (۱۶): مربوط به جریان موجود در کمانها هستند. محدودیت (۱۷) و (۱۹): پنجره زمانی ملاقات مشتریان را مشخص میکنند. هر مشتری باید در بازه زمانی مربوط به خودش دیده شود و با در نظر گرفتن مدت سرویس دهی به مشتری i ملاقات مشتری بعدی مشخص شود. محدودیت (20): این اطمینان را میدهد که فقط یک سطح سرعت (سرعت کم یا زیاد) برای هر کمان انتخاب شده است. محدودیت (21) تا (24): نامنفی بودن متغیرها و همچنین متغیرهای دودویی را نشان میدهند.

الگوریتم جستجوی بزرگ همسایگی انطباقی در مسئله مسیریابی آلودگی:

الگوریتم پیشنهاد داده شده در این مقاله دارای ۲ فاز است. فاز اول الگوریتم ابتکاری به نام جستجوی بزرگ همسایگی انطباقی یا ALNS و فاز دوم الگوریتم بهینه سازی سرعت یا SOA میباشد. الگوریتم ALNS حالت توسعه یافتهی جستجوی بزرگ همسایگی یا LNS است که شامل یک سری از حرکات برداشت و گذاشت در جستجوی همسایگی است؛ اما الگوریتم ALNS شامل چندین عملگر برداشت و گذاشت مشتریان در حین جستجوی همسایگی است. برای حل مدل در ابتدا یک جواب اولیه ایجاد شده و با استفاده از الگوریتمهای بهبود دهنده به جستجوی جوابهای همسایه برای رسیدن به جواب بهینه پرداخته میشود. انتخاب عملگر گذاشت و برداشت با مکانیزم چرخ رولت ایجاد میشود. برای ۱۲ عملگر برداشت و ۵ گذاشت احتمالها به ترتیب 1/12 و 1/5 در نظر گرفته شده است و در طول الگوریتم به صورت زیر به روز رسانی میشوند. که در آن r پارامتر چرخ رولت، عدد پی امتیاز عملگر i و w تعداد دفعاتی است که از آن استفاده شده است.

امتیاز هر عملگر نشان میدهد که چقدر هر عملگر در هر تکرار خوب عمل کرده است. اگر بهترین جواب به دست بیاید امتیاز عملگر به اندازه (s(1 (در این مقاله مقدار ۱) افزایش مییابد. اگر جواب بهتر از جواب جاری باشد امتیاز به اندازه (s(2 (در این مقاله مقدار 0) افزایش مییابد و اگر جواب از جواب جاری بدتر باشد امتیاز به اندازه (s(3 (در این مقاله مقدار ۵) افزایش مییابد.

عملگرهای برداشت:

در این مقاله ۱۲ عملگر برداشت معرفی شده و در الگوریتم از آنها استفاده شده است. ورودی این عملگرها جواب جاری مسئله است که تعدادی گره از آن برداشت شده و یک جواب کاهش یافته و لیستی از مشتریان برداشته شده از جواب به عنوان خروجی این عملگر ایجاد میشود.

1. برداشت تصادفی: این عملگر با یک لیست خالی برداشت آغاز میشود و به صورت تصادفی s گره را برمیدارد و برای s تکرار اجرا می کند. ایده انتخاب تصادفی به ایجاد تنوع در مکانیسم جستجو کمک میکند.
2. برداشت بدترین مسافت: این عملگر در هر تکرار مشتریان با بیشترین هزینه را حذف میکند. هزینه آنها از مجموع مسافت هر گره از گره قبل و بعد محاسبه میشود.
3. برداشت بدترین زمان: این عملگر در هر تکرار مشتری با بیشترین میزان انحراف در زمان رسیدن و زودترین زمان شروع خدمت را طبق رابطه زیر انتخاب میکند. که در آن y نشان دهنده زمان شروع سرویس در گره j را نشان میدهد.
4. برداشت مسیر: این عملگر مسیرهای پر شده را از جواب برمیدارد. به صورت تصادفی مسیری را از مجموعه مسیرهای جواب انتخاب میکند. سپس عملگر برداشت به طور مداوم گرهای را انتخاب و از مسیر خارج میکند تا زمانی که هیچ گرهای باقینماند.
5. برداشت شاو: این عملگر مجموعهای از گرهها با ویژگیهای شبیه به هم را انتخاب میکند. الگوریتم با انتخاب تصادفی گره آغاز شده و گرههای بعد را بر اساس رابطه زیر انتخاب میکند. گره با کمترین مقدار برای برداشت انتخاب شده و گره بعدی هم بر اساس گره ماقبل خود انتخاب میشود. در رابطه زیر گره i نشان دهنده آخرین گره برداشت انتخاب شده است و d مسافت گره i تا j، زمان شروع سرویس a، میزان تقاضا گره L و فی ۱ تا فی ۴ وزنهای نرمال کردن میباشند.
6. عملگر بر پایه نزدیکی: عملگر مجموعهای از گرهها را با توجه به فاصله آنها برمیدارد. نحوه عملکرد این عملگر در گراف در شکل ۳ نشان داده شده است. این عملگر حالت خاصی از عملگر شاو است با فی(۱) =۱ و فی(۲) =فی(۳) = فی(۴)=۰ است.
7. عملگر بر پایه زمان: این عملگر نیز حالت خاصی از عملگر شاو بوده که معیار مورد نظر آن صرف زمان میباشد. به این صورت که فی۲=۱ و فی۱ = فی3 = فی۴= ۰ میباشد.
8. عملگر بر پایه تقاضا: این عملگر نیز حالت خاصی از عملگر شاو بوده و بر پایه تقاضا میباشد که در آن فی (4)=۱ و فی(۱) = فی(2) = فی(3)= ۰ میباشد.
9. برداشت گرهها با استفاده از دانش تاریخی: عملگر HRمشابه عملگر برداشت همسایگی است. این عملگر حافظهای از حالت هزینه در هر گره i را ایجاد میکند. این هزینه از جمع فاصله بین گره قبل تا گره i و از گره i تا گره بعد به دست میآید و در هر تکرار محاسبه میشود. در هر مرحله از الگوریتم بهترین حالت هزینه (d*) از گره i به روز رسانی میشود تا بتوان کمترین مقدار d را تا آن نقطه به دست آورد. عملگر HR گره j*که بیشترین انحراف را از بهترین حالت هزینه دارد را برداشته و به لیست برداشت اضافه میکند.
10. برداشت همسایگی: این عملگر برداشت گرهها را بر اساس فاصلههای آنها در یک مسیر انجام میدهد.
11. برداشت منطقهای: عملگر برداشت منطقهای بر این اساس است که گرهها در یک فضای از پیش تعریف شده در دستگاه مختصات قرار دارند. عملگر ابتدا نقاط گوشهای فضا را محاسبه میکند سپس کل منطقه به ناحیههای کوچکتر تقسیم میشوند. ناحیهها به صورت تصادفی انتخاب شده و همه گرههای آن برداشته میشوند. عملگر برداشت، گرهها را به صورت زیر انتخاب میکند که در آن x(i²) و x(i¹) مختصات i در محور x و y(i²) و y(i¹) مختصات i در محور y میباشد. اگر ناحیهای گرهای نداشت، ناحیهی دیگری به صورت تصادفی انتخاب میشود و این روند تا زمانی که s گره خارج شود ادامه دارد.
12. برداشت همسایگی گره: این عملگر به صورت تصادفی گرهای را انتخاب میکند و s-1گره اطراف آن را در ناحیه چهارگوشی اطراف گره انتخاب شده قرار می دهد. انگیزه این ناحیه همسایگی قرار گرفتن در شبکه میباشد که در شکل ۴ نشان داده شده است. اگر تعداد گرهها در منطقه انتخاب شده کمتر از s-1 باشد با یک درصد مشخصی آن را بزرگ میکنند.

عملگرهای گذاشت:

در این بخش ۵ عملگر گذاشت در الگوریتم ALNS معرفی شده است. عملگرهای گذاشت برای ساخت دوباره مسیر از لیست مشتریان برداشت شده به کار می روند.

1. گذاشت حریصانه: این عملگر در هر تکرار خود یک گره از گرههای برداشت شده را در بهترین جای ممکن و موجه خود وارد میکند.
2. گذاشت پشیمانی: یکی از مشکلاتی که در گذاشت حریصانه وجود دارد این است که زمانی که حرکات شدنی کمی ممکن است عملیات گذاشت گره را به تکرار بعد موکول میکند. برای حل این مشکل این عملگر از ۲ معیار پشیمانی استفاده میکند. برای این کار دلتایی تعریف میشود که نشان دهنده تغییرات مقدار هدف با قرار دادن گره iدر بهترین و دومین بهترین حالت با توجه به فاصله میباشد.
3. گذاشت حریصانه با تابع noise: این عملگر نوع توسعه یافته الگوریتم حریصانه است که از یک درجه آزادی استفاده میکند. این درجه آزادی با تغییر هزینه گره به صورت زیر به دست میآید که در آن d بیشترین فاصله بین گرهها و میو نشان دهنده پارامتر noise که برابر 0.1 است، میباشد.
4. گذاشت پشیمانی با تابع noise: این عملگر نوع توسعه یافته الگوریتم گذاشت پشیمانی است که از تابع noise مشابه عملگر GIN استفاده میکند.
5. گذاشت منطقهای: این عملگر مشابه نوع پایه گذاشت است با این تفاوت که به جای استفاده از فاصله، برای تعیین بهترین گذاشت هر گره، از پنجره زمانی آن استفاده میکند. این الگوریتم بهترین حالت گذاشت هر گره را تعیین کرده و به جستجوی حالت بهتری در اطراف آن میگردد که در پنجره زمانی آن گره شدنی باشد.

بهینهسازی سرعت:

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

تابع هدف: به دنبال کمبنه کردن کل هزینه مصرف سوخت و درآمد راننده میباشد.

محدودیت (۲۶): این اطمینان را میدهد که زمان رسیدن به گره i+1 برابر جمع زمان رسیدن به گره i، زمان سرویسدهی به گره i و زمان سفر تا گره i است.

محدودیت (۲۷): تضمین میکند که خدمات مربوط به گره i در بازه a تا b انجام شود.

محدودیت (۲۸): حد بالا و پایین سرعت را تعریف میکند.

محدودیت (۲۹) تا (۳۱): نامنفی بودن متغیرها را بیان میکند.

در ابتدای الگوریتم، سرعتها برای هر کمان با در نظر گرفتن پنجره زمانی و کل زمان در دسترس محاسبه میشوند. مقادیر سرعت برای پیدا کردن خطاها استفاده میشوند. به این صورت که اگر زمان ارسال کمتر از جمع a و t در گره i باشد و یا زمان رسیدن به گره i بزرگتر از b باشد خطا به حساب میآید. در غیر این صورت خطا صفر است. اگر حداقل سرعت ممکن بیشتر از سرعت بهینه باشد، سرعت بهینه به حداقل سرعت ممکن افزایش مییابد و اگر سرعت فعلی کمتر از مقدار بهینه باشد آن را به مفدار بهینه تغییر میدهد. الگوریتم در هر فاز، کمان با بیشترین خطا در پنجره زمانی را انتخاب کرده و خطای آن را حذف میکند.

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

در این بخش نتایج محاسباتی مربوط به اجرای الگوریتم ALNS ارائه شده است. در ابتدا نمونه های تعریف شده در مسئله توضیح داده شده سپس نتایج بیان میشوند.

9 مجموعه که هر کدام دارای ۲۰ نمونه هستند تولید شده است. نمونهها به صورت تصادفی از شهرهای انگلستان انتخاب شدهاند. فاصلههای در نظر گرفته شده بین شهرها مقدار واقعی آنها هستتند. پنجره زمانی و زمان سرویسدهی به صورت تصادفی تولید شده است. این نمونه ها برای تعداد مشتریان ۱۰، ۱۵، ۲۰،۲۵، ۵۰، ۷۵، ۱۰۰، ۱۵۰ و ۲۰۰ تولید شده است. الگریتم ارائه شده شامل ۱۵ پارامتر است که در ۳ گروه دستهبندی شده اند.

گروه اول روند انتخاب را با مکانیزم چرخ رولت تعریف انجام میدهد.

گروه دوم از پارامترها برای تنظیم کردن شبیهسازی تبرید استفاده میکند و دما و نرخ سرد شدن الگریتم را تعریف میکند. شکل ۵ رفتار رویکرد ابتکاری ۱۰۰ گرهی نمونه را نشان میدهد. با توجه به شکل بهترین جواب، جواب فعلی و جواب جدید در بیش از ۲۵۰۰۰ تکرار تغییر میکنند. در این شکل نمودار نقطه چین شده جواب جدید، نمودار خط چین شده جواب فعلی و خط ممتد بهترین جواب را نشان میدهد.

گروه سوم: از پارامترهای مختص عملگرهای برداشت و گذاشت تشکیل شده است.

اثرات بهینه سازی سرعت:

الگوریتم بهینهسازی سرعت یا SOA بسیار سریع است و قابلیت بهبود نتایج حاصل از الگوریتم ALNS را دارد. برای مثال شکل ۶ بهبود جوابهای ایجاد شده در الگوریتم ALNS را در ۱۰۰ گره نشان میدهد. نتایج نشان میدهد که در کل الگوریتم SOA، جوابهای به دست آمده از ALNS را به اندازه ۲ تا ۴درصد بهبود بخشیده است.

نتیجه گیری:

در این مقاله یک الگوریتم ابتکاری برای حل مسئله مسیریابی آلودگی پیشنهاد شده است. این الگوریتم در مسئله مسیریابی وسیله نقلیه با پنجره زمانی و مسئله بهینهسازی سرعت تکرار میشود. در الگوریتم ALNS از عملگرهای گذاشت و برداشت موجود در ادبیات و جدید استفاده شده است که باعث افزایش کیفیت جواب میشود. این عملگرها میتوانند در ALNS برای حل انواع دیگر مسائل استفاده شوند. SOA باعث بهبود جواب به دست آمده از ALNS و کاهش هزینههای مصرف سوخت و حقوق راننده وسیله نقلیه میشود. SOA زمان اجرای کوتاهی دارد و میتواند به تنهایی در انواع دیگر مسائل مسیریابی و بهینه سازی سرعت استفاده شود. برای ارزیابی کامل الگوریتم ابتکاری، دستههای متفاوتی نمونه از دادههای جغرافیایی واقعی تولید شده است. نتایج محاسباتی نشان میدهد که الگوریتم پیشنهادی برای پیدا کردن جوابهای با کیفیت در مسائل دارای نمونههایی که تعداد آنها نا ۲۰۰ گره باشد، بسیار کارآمد است.