ارائه مدل و الگوریتم حل مسئله جمع آوری پسماندهای شهری در ابعاد واقعی

در این مقاله سعی شده است تا روشی برای یافتن کوناه ترین مسیر حرکت ماشین های جمع آوری زباله ارائه شود. هدف اصلی مقاله ارائه راه حلی برای این نوع مسائل در ابعاد واقعی می باشد. با توجه به پهنه گسترده شهرها و انجام هر روزه این فعالیت، جمع آوری پسماند ها هزینه های بالایی را بر سازمان های متصدی امر تحمیل میکتد که قسمت عمده این هزینه ها مربوط به سوخت مصرفی ماشین های جمع آوری می باشد. میزان مصرف سوخت رابطه مستقیمی با مسافت طی شده توسط ماشین های جمع آوری پسماند دارد که با مینیمم کردن مسافت طی شده می توان هزینه ها را کاهش داد و به دلیل بالا بودن هزینه ها حتی در صد اندکی بهبود در عملکرد سیستم، موجب کاهش هزینه ها به میزان قابل ملاحظه ای می شود.ماشین های جمع آوری زباله از یک نقطه مشخص، در یک محدوده، فعالیت جمع آوری را آغاز کرده و با پیمودن تمام سطلهای آن محدوده در نقطه معین دیگری بارگیری را به اتمام رسانده و به سمت محل تخلیه بار حرکت می کنند. با توجه به شرایط حاکم بر این مسئله نزدیکترین الگوریتم بهینه سازی شبکه برای حل آن مسئله فروشنده دوره گرد (TSP) می با شد با این تفاوت که در این مسئله فروشنده به همان نقطه شروع باز می گردد. همچنین این الگوریتم برای گرافهای کامل طراحی شده است اما مسئله جمع آوری پسماندها به دلیل موانع توپولوژیکی و ترافیکی گراف کامل نمی باشد.با مدل سازی این مسئله به روش Pure Integer Linear Programming مشاهده شد که حل این مسئله در ابعاد واقعی به روشهای متداول انشعاب و تحدید و برش به دلیل تعداد زیاد متغیرهای تصمیم گیری و محدودیت های حاکم بر مسئله بسیار زمان بر بوده و برای مسائل با ابعاد واقعی تقریبا غیر ممکن می باشد. مدل ریاضی این مسئله از نوع PILP با یک نوع متغیر تصمیم گیری و سه نوع محدودیت دارای1.500.000 متغیر و 1.506.006 محدودیت می شود که برای حل آن در زمان نسبتا کوتاه یک روشی ابتکاری شامل سه الگوریتم پیشنهاد گردید.برای ارزیابی عملکرد الگوریتمهای پیشنهادی یک مسئله واقعی با استفاده از داده های یکی از مناطق شهرداری تهران حل شد. محدوده جغرافیایی مورد نظر به مساحت 12 کیلومتر مربع و شامل تعداد 500 سطل زباله، هریک با ظرفیت اسمی و عملی به ترتیب 90 و 80 کیلوگرم، می باشد که 6 کامیون در سه نوع با ظرفیتهای اسمی 3 و 7 و 10 تن برای جمع آوری تخصیص می یابند. در روش پیشنهادی این مقاله ، ابتدا کل منطقه مورد بررسی را با استفاده از الگوریتم اول به نواحی کوچکتر تقسیم می کنیم؛ هرناحیه از تعدادی سطل تشکیل می شود و بین چهار خیابان محصور است. هر یک از نقاط واقع در مرز ناحیه میتواند یک نقطه شروع یا پایان بالقوه عملیات جمع آوری زباله باشد. پس با استفاده از الگوریتم دوم برای هر ناحیه کوتاه ترین مسیر بین هر زوج نقطه شروع و پایان را پیدا می نمائیم. در گام بعد الگوریتم دیگری با ترکیب این نواحی، در دسته های متناسب با ظرفیت ماشین های حمل، نواحی همجوار مناسب را برای هر کامیون مشخص می کند بطوریکه کل مسافت طی شده در مجموع این نواحی به حداقل برسد. کامیونهای با ظرفیت بالاتر در اولویت می باشند بدین معنا که تخصیص کامیون به سطلها برای کامیونهای بزرگتر قبل از کامیونهای کم ظرفیت صورت میپذیرد. فرایند ترکیب به گونه ای صورت میگیرد که کل مسافت طی شده توسط تمام ماشین های فعال در منطقه مینیمم شود. جزئیات الگوریتمها در متن اصلی مقاله معرفی خواهند شد. در این روش ابتکاری موانع توپولوژیکی مانند بن بستها و بلوارها و همچنین مقررات ترافیکی مانند یک طرفه بودن به عنوان محدودیت لحاظ شده اند تا نتایج حاصل از این روش هر چه بیشتر به واقعیت نزدیک با شند. این مساله در منطقه 2 شهرداری ، ناحیه 1 آن حل شده است که مرزهای آن ناحیه از شمال یادگار امام، از جنوب بلوار دریا، از شرق بلوار فرهنگ و از غرب بلوار پاکنژاد می باشند. مسیر طی شده در این نمونه واقعی توسط ماشین های جمع آوری زباله در هر شیفت کاری به میزان 148687 متر می باشد.با استفاده از الگوریتم پیشنهادی کل طول مسیر پیموده شده به میزان 139125 متر بوده که در مقایسه با میزان مسافت طی شده در حالت واقعی به میزان 5/6 درصد کاهش پیدا کرده است که این میزان کاهش اگرچه برای یک شیفت کاری میزان زیادی نیست ولی مجموع این کاهش در طول یک سال مقدار قابل ملاحظه ای می باشد.