بخشی از مقاله
چکیده
در این مقاله یک مدل ریاضی برای جمعآوری پسماندهای شهری با توجه به شرایط دنیای واقعی و نیز روشی برای حل مساله ارائه شده است. مدل بر مبنای مسالهی مسیریابی خودروهای ظرفیتدار با ناوگان ناهمگن و محدودیت خودروها میباشد. با توجه به هزینههای اولیه در تجهیز خودروها و محدودیتهای صرف هزینه، خودروها ملزم به تخلیه و بارگیریهای متعدد میباشند. هدف مساله کمینه کردن هزینه - مسافت - طی شده توسط خودروها میباشد. مدل پیشنهادی برای تعدادی مثال عددی با استفاده از روش های حل دقیق و روش فراابتکاری شبیه سازی تبرید حل و نتایج گزارش شده است. سپس با توجه به کارآمدی روش فراابتکاری از آن برای حل مساله در مطالعه موردی برای جمعآوری پسماند شهری استفاده گردیدهاست.
کلمات کلیدی:مساله مسیریابی خودروها، جمعآوری پسماند، ناوگان ناهمگن، تخلیه و بارگیری متعدد، الگوریتم فراابتکاری شبیهسازی تبرید.
-1 مقدمه
با توجه به اینکه بخش زیادی از هزینههای جمعآوری پسماندهای شهری مربوط به مرحلهی جمعآوری میباشد تلاش در جهت بهینه-سازی این فرایند و بهبود در آن از سالها پیش به چشم میخورد. استفاده از مسالهی مسیریابی خودروها برای بهبود مسیرهایی که توسط خودروهای جمعآوری و حمل پسماندها طی میشود میتواند به کاهش هزینهها در مدیریت خدمات شهری کمک کند.
با توجه به [1] استفاده از مسالهی مسیریابی برای کاهش هزینههای مدیریت پسماند در ایالات متحده آمریکا بسیار موفق بوده است. در همین راستا تلاشهای بسیاری صورت گرفته که به برخی از آنها در سالهای اخیر اشاره میکنیم.
در [2] از مدل پیشنهادی [1] استفاده شده و در آن سعی بر آن بودهاست که روش حل مناسبی برای مسالهی مسیریابی خودروهای ظرفیتدار و با پنجره زمانی با استفاده از الگوریتم ژنتیک ارائه شود. در [3] با در نظر گرفتن یک مسالهی مسیریابی خودروها به صورت چندهدفه، با دو هدف به حداقل رساندن زمان سفر و تعداد وسایلنقلیه و با محدودیتهای پنجرهی زمانی، محلهای تخلیه مختلف و درگیری بین خواص زبالهها، سعی شده است به کمک یک الگوریتم ممتیک حل شود. در [4] با بررسی متغیرهای مختلف برای طراحی مجدد سیستم جمعآوری پسماند به هدف سازگاری با شاخصهای زیستمحیطی بر اساس مدل مسیریابی وسیلهی نقلیه، رویکرد جدیدی در زمینهی جمعآوری بازیافت ارائه شده است.
در [5] یک برنامهی پیشنهادی برای جمعآوری زباله به صورت پویا با استفاده از کانتینرهای زیرزمینی مجهز به سنسور برای مساله موجودی مسیریابی ارائه شد. در [6] نویسندگان، یک روش حل جدید فراابتکاری برای مساله پرش/ذخیره در جمعآوری زبالهها ارائه کردند و با دو روش فراابتکاری جستجوی ممنوعه و جستجوی محلی مقایسه کردند. محدودیتهای این مساله شامل پنجرهی زمانی مورد توجه مشتریان، امکانات دفع و انبار است. دورهی استراحت رانندگان نیز مدنظر قرار داده شدهاست. همان نویسندگان در [7] در ادامهی مقالهی قبلی با در نظر گرفتن شرایط جدید برای مکانیابی تسهیلات دفع به حل مجدد مساله میپردازند. هدف یافتن بهترین تسهیلات برای قرارگیری در مسیر حرکت خودروها میباشد. نتایج کامپیوتری نشاندهندهی بهبود الگوریتم نسبت به حالت گذشته میباشد.
در [8] با استفاده از الگوریتم ممتیک به حل مسالهی مسیریابی خودروها پرداخته شدهاست. در این مقاله یک مسالهی چندهدفه - با اهداف به حداقل رساندن زمان سفر و تعداد وسایل نقلیه - و بامحدودیتهای پنجرهی زمانی، محلهای تخلیه مختلف و درگیری بین خواص زبالهها مورد بررسی قرار گرفته است. در >9@ مسالهی مسیریابی با تقاضاهای احتمالی برای جمعآوری پسماند با استفاده از الگوریتم فراابتکاری بهینهسازی ازدحام ذرات حل شدهاست. در [10] تلاش شده الگوریتم قطرهی آب هوشمند برای حل یک مسالهی مسیریابی در حوزهی جمعآوری زبالهها بهبود یابد. استفاده از این الگوریتم نتایج مناسبی را نشان دادهاست. در [11] طی یک مقاله مساله مسیریابی خودرو بزرگ مقیاس برای جمعآوری زباله در شهرستان اسکندریه در مصر حل شده است.
مدل مبتنی بر سیستم اطلاعات جغرافیایی و مساله مسیریابی خودروها با پنجره زمانی توسعه داده شده و با استفاده از نرم افزار TransCAD حل شده است. حالات مختلف توسعه یافته و مورد مقایسه قرار گرفتند. نتایج نشان دهندهی برتری سناریوهای مبتنی بر خوشهبندی میباشد. در [12] نویسندگان مقاله پیشنهاد یک سیستم جمعآوری زبالههای شهری به صورت پویا را ارائه نمودند. آنها در این مقاله با استفاده از الگوریتم کلونی مورچگان به حل مسالهی مسیریابی خودروهای پویا پرداختند.در ادامه مقاله با بررسی شرایط مساله در دنیای واقعی سعی می-شود مدل مناسبی برای مساله طرح گردد که در آن محدودیتهای دنیای واقعی لحاظ شود، سپس با استفاده از روش دقیق و روش فراابتکاری شبیهسازی تبرید سعی میشود روش حل مناسبی برای این مدل بیان شود.
-2 مدل سازی مساله
با توجه به چالشهای متفاوت مسائل در دنیای واقعی یک مدل متناسب با مطالعهی موردی که در شهرداری کاشمر صورت گرفته-است، پیشنهاد میگردد. این مدل تعمیمی از مسالهی مسیریابی خودروها میباشد که باید علاوه بر محدودیتهای معمول مساله محدودیتها و شرایط موجود در مطالعهی موردی موردنظر را نیز دربر-گیرد.با توجه به محدودیت منابع مالی و هزینههای اولیهی تهیه و تجهیز خودروهای جمعآوری پسماندهای شهری، ناوگان حمل و نقل برای خدمات شهری محدود میباشد. بنابراین باید بهینهسازی مساله به صورتی باشد که با استفاده از منابع موجود کمترین هزینه بر سیستم تحمیل شود.
همچنین کیفیت موردنظر برای خدمترسانی محدودیتهایی را ایجاد میکند که باید پاسخ داده شود. محدود بودن ظرفیت خودروهای جمعآوری پسماند، اولین محدودیتی است که باید در مساله مورد توجه قرار بگیرد. همچنین تفاوت ظرفیت خودروهامحدودیت دیگری است که مساله را به یک مساله مسیریابی خودروها با ناوگان ناهمگن تبدیل میکند. در مسالهی پیش رو با شرایطی مواجه هستیم که با توجه به کمبود تعداد خودروهای حمل پسماند و نیز محدودیت زمانی برای جمعآوری پسماندها که باید در ساعات انتهایی شب صورت گیرد، چارهای جز کاهش کیفیت خدمات و جمعآوری پسماندهای شهری به صورت شیفتی - شب در میان - نمیباشد.
البته این مورد به جای آنکه در مدل اعمال گردد، میتواند با در نظر گرفتن دوبرابری ناوگان به صورت فرضی و تفکیک آن پس از حل مساله اعمال شود. محدودیت در تعداد و ظرفیت خودروها باعث میشود که خودروها ملزم شوند برای تخلیهی پسماند جمعآوری شده به محل دفن زباله مراجعه کرده و پس از تخلیه دوباره برای بارگیری مجدد اقدام نمایند. بدیهی است، کمینه کردن تعداد این مراجعات با توجه به دور بودن محل تخلیه پسماندها از مناطق شهری موجب کاهش قابل توجه هزینههای حمل و نقل میشود. همچنین باید تلاش شود تا علاوه بر جمعآوری پسماند و خدمت رسانی به همهی نقاط تقاضا از همهی خودروها به نسبت تقریبا مساوی استفاده شود.
-1-2 مدل ریاضی
شبکهی G= - V,A - را در نظر بگیرید که در آن V مجموعهی گرهها را نشان میدهد و A مجموعهی کمانهاست. گره v0 قرارگاه خودروهاست که مسیر تمامی خودروها از آن شروع و به آن منتهی می-شود. گرههای v1 تا vN مجموعه نقاط تقاضا میباشند که باید خدمت داده شوند و گره vN+1 مربوط به محل تخلیهی پسماند میباشد.متغیر تصمیم یک متغیر صفر و یک است و به صورت xijk تعریف میشود و زمانی مقدار یک میگیرد که کمان i تا j توسط خودرو k پیموده شود.اگر مسیر گره i تا j توسط خودرو k طی شوددر غیر این صورت متغییر Nk تعداد دفعاتی که هر خودرو باید به محل تخلیه مراجعه کند را مشخص میکند. متغیر CDi,k ظرفیت تجمعی گره i و خودرو kاست.پارامترهای فاصله گره i تا j، di تقاضای گره i و Dkظرفیت خودرو k را بیان میکنند.با توجه به تعاریف بالا مدل ریاضی مساله که محدودیتهای موجود را در نظر گرفته و همزمان هزینهی حمل و نقل سیستم را کاهش دهد به این صورت نوشته میشود:
محدودیت اول تعیین میکند که همهی خودروها مسیر حرکت خود را از محل پارکینگ شروع میکنند. محدودیت دوم باعث میشود هر گره تقاضا از یک خودرو خدمت بگیرد و محدودیت سوم برای طی مسیر به صورت متوالی است. به عبارت دیگر تعداد ماشینهایی که به هر گره وارد میشود برابر با تعداد ماشینهایی است که از آنها خارج میشوند. محدودیت چهارم باعث میشود که هر خوردو پس از رسیدن به حداکثر ظرفیت ملزم به مراجعه به محل تخلیه باشد مقدار CDi,k در این محدودیت محاسبه میشود. محدویت بعدی مربوط به ظرفیت خودروها میباشد. در محدودیت بعدی ظرفیت تجمعی هر خودرو با عبور از گره محل دفن زباله صفر میشود. محدودیت هفتم تعداد مراجعه هر خودرو به محل تخلیه را تعیین میکند که باید یک عدد طبیعی باشد. محدودیت هشتم خوردوها را ملزم میکند در نهایت از محل تخلیه به پارکینگ برگردند.
-3 روش حل مساله
مسالهی مسیریابی خودروها جز مسائل NP-Hard به شمار میرود و حل آن با استفاده از روشهای دقیق مشکل بوده و در مسائل با ابعاد بزرگ تقریبا غیرممکن است. با توجه به این موضوع باید برای حل مدل
