مقاله بهینه سازی زمان سفر با استفاده از الگوریتم کلونی مورچگان بهبود یافته

بخشی از مقاله

بهینه سازی زمان سفر با استفاده از الگوریتم کلونی مورچگان بهبود یافته

چکیده

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

واژگان کلیدی: سفر، زمان سفر، الگوریتم کلونی مورچگان، حمل و نقل

1. مقدمه

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

در کنار این امر داشتن سیستم حمل ونقلی عمومی پویا، کارآمد، بهینه و جذاب برای مسافران شهری جهت تسهیل رفت و آمدهای شهری و سوق دادن سفرهای شهری از وسیله نقلیه شخصی به سمت وسایل نقلیه عمومی؛ تلاشها برای بهبود شرایط کمی و کیفی در زمینه حملونقل عمومی را گسترش داده است. این پژوهش نیز در راستای این فعالیتها سعی کرده است تا با ارائه مدل یکپارچه ای از حملونقل عمومی و نوین و ارزیابی عملکردی آن با الگوریتم کلونی مورچگان در جهت کاهش زمان سفر مسافران درونشهری، جذب بیشتر مسافران شهری به سمت حملونقل عمومی و پایدار را توسعه دهد.

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

به دلیل افزایش روز افزون جمعیت و به تبع آن تمایل به شهر نشینی تقاضای سفر در شهرها رشد بسیار چشمگیری داشته است. در مقابل تقاضای سفر سه راهکار اصلی وجود دارد یکی مدیریت عرضه و دیگری مدیریت تقاضا و مدیریت کاربریهای اراضی ..

کوا و پرل1 در سال 1989 میلادی در مطالعه شان مسئله طراحی شبکه تغذیه کنندهها ( Feeder ) را به صورت مدل بهینه سازی ارائه نمودند .آنها دو شبکه مجزا برای بخش ریلی و اتوبوس در نظر گرفتند .موقعیت ایستگاههای اتوبوسرانی از قبل تعیین شده است و تقاضا در گرههای خطوط اتوبوسرانی فرض شده اند.[1]
شیراواتسا و دینگارا2در سال 2001 میلادی، مدلی برای عملکرد یکپارچه ایستگاههای ریلی حومه شهر و اتوبوسهای همگانی ایجاد کردند

.دراین مطالعه ،آنها یک الگوریتم ابتکاری برای تولید مسیرهای تغذیه کنندها به ایستگاههای ریلی پیشنهاد کردند.این الگوریتم ابتکاری تولید مسیرهای تغذیه کننده نسبت به ماتریس تقاضا بسیار حساس است؛ بطوری که اولویت با گرههای با تقاضای بالاتر است.[2] از جمله متغیرهای تصمیم گیری موجود در مطالعه آنهامی توان به مسیرها، تواتر و زمانبندی مسیرها اشاره کرد.[3]

کوان و همکاران در ادامه تلاشها و پیگیریهای خود برای ایجاد شبکه بهینه ای برای مسیرهای تغذیه کنندهها، مسئله طراحی شبکه تغذیه کننده را با دو الگوریتم فرا ابتکاری یعنی الگوریتم ژنتیک و الگوریتم کلونی مورچگان حل نموده اند .هر چند نتایج نشان می دهد که الگوریتم جستجوی ممنوعه جوابهای بهتری ایجاد میکند ولی الگوریتم کلونی مورچگان برای شبکههای بزرگ و پیچیده پیشنهاد شده است.[4]

شریعت وغلامی در سال 2010 مطالعاتی در رابطه با طراحی شبکههای تغذیه کننده چند طریقه ای ارائه نمود.[5] افندی زاده و فرح زاد مدل ابتکاری طراحی شبکه اتوبوسرانی تغذیه کننده شبکه ریلی با استفاده از الگوریتم کلونی مورچگان را ارائه نمودند

.تابع هدف پیشنهادی برای این مدل یک تابع در سطحی است که در سطح پایین به طراحی شبکه اتوبوسرانی تغذیه کننده می پردازد و در سطح بالا هزینه کل کمینه خواهد شد. در مدل ارائه شده تاثیر نقاط انتقال شبکه ریلی و میزان جابجایی در هر کمان برای نقاط مختلف شهر نیز در تابع هدف دیده شده است.[6]

2. بررسی عوامل موثر در طراحی شبکه شهری سامانه حملونقل همگانی

شبکههای حملونقل همگانی شامل خطوط جابجایی و ایستگاههای سوار و پیاده شدن مسافرین، یکی از مهمترین زیر ساختهای حملونقل عمومی می باشد. طراحی مناسب خطوط ترانزیت با توجه به حق عبور، تکنولوژی سیستم، مد مورد استفاده و همچنین جانمایی و مکانیابی صحیح ایستگاهها موجب افزایش کارایی شبکه و بهبود عملکرد سیستم میشود .[7]

-1 ملاحظات برنامه ریزی که شامل حداکثر نمودن جابجایی مسافر در شبکه حملونقل، دستیابی به حداکثر کارایی شبکه، ایجاد تاثیرات مثبت و جذب مسافر، پوشش

شبکه و .... میشود.

-2 بهره وری عملکرد شبکه بهره وری عملکرد شبکه، نشان دهنده کیفیت و هزینه عملکرد سیستم حملونقل عمومی می باشد. چند عامل موثر در بهره وری وجود

دارند که شامل -1 پیوستگی و متعادل کردن خطوط از لحاظ ظرفیتی، -2 انعطاف پذیری عملیاتی -3 هزینههای سیستم و ... می باشد .

.3 بررسی روشهای حل مساله تخصیص حملونقل همگانی ( بدست آوردن زمانهای سفر در مسیرهای مختلف )

مساله تخصیص همگانی شامل مدل کردن رفتار مسافران به منظور تعیین جریان مسافر در سیستم حملونقل عمومی می باشد. در این تحقیق پس از ارائه تعاریف و مفاهیم اولیه در این زمینه، مدلی را جهت مساله تخصیص حمل ونقل همگانی با مجموعه مسیرهای مشخص ارائه، در این راستا نشان داده شده که مسافرین استراتژی را انتخاب خواهند نمود که در عین کاهش زمان سفر خود در حین تغییر مسیر دادنهای مختلف، هزینههای مورد انتظار را نیز به حداقل می رسانند.

در قسمت بعدی به مفاهیم اولیه و تعاریفی که آشنایی با آنها جهت درک بهتر مساله ضروری بود پرداخته شد:[8]

- انجام سفر بین هر زوج مبدا - مقصد با سیستم حملونقل همگانی به کمک ترکیبی از 4 نوع حرکت زیر صورت می پذیرد: -1 پیاده روی

-2 سوار شدن به سیستم حملونقل عمومی -3 داخل وسیله حملونقل عمومی -4 پیاده شدن از سیستم حملونقل عمومی
- یک سیستم حملونقل همگانی شامل مجموعه ای مشخص از خطوط حملونقل عمومی بر روی شبکه معابر می باشد.

- تخصیص حملو نقل همگانی در دو حالت قابل بررسی می باشد:
-1 روش مبتنی بر زمان بندی:

این روش معمولاً برای شبکههای خلوت دارای کاربرد می باشد. در این حالت زمان ورود وسیله نقلیه به ایستگاه و همچنین زمان وارد شدن مسافر به ایستگاهها مشخص می باشد. بنابراین در این حالت زمان انتظار مشخص خواهد بود و لذا برای شبکههای خلوت که بتوان آن را زمان بندی کرد دارای کاربرد می باشد. این روش به عنوان مبتنی بر زمان بندی 3 شناخته میشود.

-2 روش مبتنی بر تواتر در این حالت فرض میشود که زمان رسیدن وسیله نقلیه به ایستگاه مشخص نمی باشد و لذا فرض بر آن است که زمان انتظار مسافر در

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

- قانون واردراپ در تخصیص تعادلی -1 پس از تخصیص هیچ راننده ای نمی تواند مسیری کوتاه تر از آنچه که انتخاب کرده است را انتخاب نماید.

-2 پس از تخصیص، زمان سفر در شبکه به حداقل خود می رسد به عبارتی زمان بهینه میشود.

- تصادفی بودن زمان انتظار، انتخاب مسیر را پیچیده می نماید. چرا که در این شرایط کوتاهترین مسیر قطعی بین زوج مبدا - مقصدهای سفر مشخص نمی باشد.

- هر مجموعه ای مشخص از ترکیب 4 حالت مختلف پیاده روی، سوار شدن، داخل وسیله نقلیه و پیاده شدن که بر اساس قانون سفر انتخاب خواهند شد ( در ادامه توضیح داده خواهد شد ) یک استراتژی نامیده میشود. هر مسیر یک استراتژی می باشد. به عبارت دیگر هر مجموعه مشخص از کمانهای پیاده روی و خطوط جذاب که توسط مسافر براساس قانون سفر انتخاب شوند، یک استراتژی نامیده میشود. از تعاریف و مدلهای ارائه شده در تحقیق مطالعه شده در جهت تکمیل مدل برای بهینه سازی زمان سفر بهره برده شده است.

4. معرفی الگوریتم مورچگان و کاربردهای آن

در مسائل بهینه سازی با تعداد زیادی پارامتر روبرو هستیم به گونه ای که روشهای کلاسیک کارایی چندانی ندارند.در این گونه موارد بهتر است به جای بررسی تمام فضای جواب از روشهای دیگری استفاده شود که به صورت هوشمند فضای گستره ی جستجو را کاهش می دهند. یکی از این روشها، الگوریتم کلونی مورچهها می باشند.

الگوریتم کلونی مورچهها برای اولین بار توسط دوریگو5وهمکارانش به عنوان یک راه حل چند عامله برای مسائل مشکل بهینه سازی مثل فروشنده ی دوره گرد(6( TSP ارائه شد.
الگوریتم کلونی مورچهها،گروهی از الگوریتمهای بهینه سازی می باشند که الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچهها
است.

این مطالعات نشان می دهد مورچهها حشراتی اجتماعی هستند که در کلونیها زندگی می کنندو رفتار آنها بیشتر در جهت بقاء کلونی است تا در جهت بقاء یک جزء از آن.

یکی از مهم ترین و جالبترین رفتار مورچهها،رفتار آنها برای یافتن غذاست و بویژه چگونگی پیدا کردن کوتاه ترین مسیر میان منابع غذایی و آشیانه شان.

در دنیای واقعی مورچه ها ابتدا به طور تصادفی به این سو و آن سو میروند تا غذا بیابند. سپس به لانه بر میگردند و ردّی از فرومون7 به جا میگذارند. چنین ردهایی پس از باران به رنگ سفید در میآیند و قابل رویت اند. مورچههای دیگر وقتی این مسیر را مییابند، گاه پرسه زدن را رها کرده و آن را دنبال میکنند. سپس اگر به غذا برسند به خانه بر میگردند و رد دیگری از خود در کنار رد قبل میگذارند؛ و به عبارتی مسیر قبل را تقویت میکنند. فرومون به مرور تبخیر میشود که از سه جهت مفید است:

-1 باعث میشود مسیر جذابیت کمتری برای مورچههای بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راههای کوتاهتر را بیش تر میپیماید و تقویت میکند هر راهی بین خانه و غذا که کوتاهتر(بهتر) باشد بیشتر تقویت میشود و آنکه دورتر است کمتر.
-2اگر فرومون اصلاً تبخیر نمیشد، مسیرهایی که چند بار طی میشدند، چنان بیش از حد جذّاب میشدند که جستجوی تصادفی برای غذا را بسیار محدود میکردند.

-3وقتی غذای انتهای یک مسیر جذاب تمام میشد رد باقی می ماند.

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

شکل(:(1 نمایش روند بهبود مسئله مسیریابی توسط الگوریتم مورچگان

از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دورهگرد است. به طوری که انواع الگوریتم مورچهها برای حل این مساله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و ژنتیک در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که، الگوریتمی است با قابلیت تکرار و لذا با گذر زمان میتواند جواب را به طور زنده تغییر دهد. که این خاصیت در روتینگ شبکههای کامپیوتری و سامانه حمل ونقل شهری مهم است.

1-4 بهینه سازی مسائل به روش کلونی مورچهها
مسئله یافتن کوتاه ترین مسیر،یک مسئله بهینه سازیست که گاه حل آن بسیا ر دشوار است و گاه نیز بسیار زمانبربه. عنوان مثال مسُله فروشنده ی دورهگرد((TSPکه باروشهای کلاسیک قابل حل نیست. ACOالگوریتم کامل و مناسبی برای حل مسُلهTSP است.

2-4 نحوه پیدا کردن کوتاه ترین مسیر

مشاهدات نشان داده که هر مورچه هنگام حرکت به سمت هدف مورد نظر (غذا)، در مسیر حرکت خود ماده ای به نام فرومون (Pheromone) بر جای میگذارد که البته این ماده به زودی تبخیر میشودولی درکوتاه مدّت به عنوان رد مورچه بر سطح زمین باقی می ماند و مورچههای دیگر را به سمت خود جذب میکند.
آنهاهنگام انتخاب بین دومسیربه صورت احتمالاتی مسیری راانتخاب می کنند که فرومون بیشتری داشته باشد یا به عبارت دیگر مورچههای بیشتری قبلا از آن عبور کرده باشند.پیدا کردن کوتاه ترین مسیر مراحلی دارد که روی شکل((2 توضیح می دهیم.

شکل(:(2 مراحل پیدا کردن مسیر

همانطور که در شکل 1 مشاهده می کنید مورچهها ابتدا روی یک مسیر مستقیم در حال حرکت اند.(در ابتدا هیچ فورومون وجودندارد) در شکل 2 در مسیر مورچهها مانعی قرار می دهیم.

در شکل 3 اولین مورچه از A می آید و به C می رسد.در مسیر حرکت هیچ فورومونی نمی بیند.بنابراین 2 راه برای انتخاب کردن دارد.(یا به سمت بالا حرکت میکند یا به سمت پایین)
اولین مورچه از مسیرCED می رود. دومین مورچه ازمسیرCFD می رود. ولی اولین مورچه زودتر از دومی ،به مقصد می رسد. بنابراین مسیرCED به عنوان مسیر کوتاه ترو پرفورومون تر وبهینه شناخته میشود.

همانطور که در شکل 4 مشاهده میشود،تجمع مورچهها درمسیرCED بیشتر است.

نکته بسیاربا اهمیت این است که هرچنداحتمال مسیر پرفرومون توسط مورچهها بیشتراست ولی این کماکان احتمال است وقطعیت نیست. اگر فرض کنیم که به جای این احتمال قطعیت وجود می داشت، آنگاه اساسا این روش ممکن نبود به جواب برسد.

نکته دیگر مسُله تبخیر شدن فرومون بر جای گذاشته شده است. تبخیر شدن فرومون و احتمال به مورچههاامکان پیدا کردن مسیر کوتاه تر جدید را می دهند.

3-4 مزایا ACO

همان طور که گفته شد »تبخیر شدن فرومون« و »احتمالBتصادف«به مورچهها امکان پیداکردن کوتاه ترین مسیر را می دهند.
این دو ویژگی باعث ایجادنعطاف در حل هر گونه مسُله بهینه سازی میشوندمثلادرگراف. شهرهای مسُله فروشنده دوره گرد،اگریکی ازیالها(گره ها) حذف شود،الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با تو جه به شرایط جدید پیدا کند.

4-4 انواع مختلف الگوریتم بهینه سازی مورچگان
در پایین تعدادی از انواع شناخته شده از الگوریتم بهینه سازی مورچگان را معرفی میکنیم:

1 -سیستم مورچه نخبگان: در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد میکند .همچنین این روش برای تمام مورچههای مصنوعی باید انجام شود.