طراحي شبكه اتوبوسراني با الگوریتم کلونی مورچه

توضیحات

براي طراحي شبكه اتوبوسراني، پوشش جمعيتي بيشتر در سطح شهر يك ملاك اصلي است. بدين معني كه شبكه‌اي كه مقدار تقاضای بيشتري از شهر را پوشش بدهد، شبكه برتري است. اما با چنين هدفي، پاسخ مسأله اين است كه در تمام خيابانها و براي همه ناحيه‌ها خط اتوبوسراني درنظر گرفته شود، زيرا در اين صورت پوشش به حداكثر خود مي‌رسد. ولي چنين كاري از نظر بودجه و اجرايي امكانپذير نيست. از اين¬رو، بايد محدوديت بودجه نيز در اين مسأله ديده شود. براي اين منظور هزينه‌هاي شبكه اتوبوسراني بصورت تابعي از طول شبكه تعريف شده است. بدين ترتيب، منفعت تصميم به صورت پوشش بيشتر در سطح شهر، و هزينه آن به صورت تابعي از طول شبكه تعريف مي‌شود. در محاسبه پوشش شبكه اتوبوسراني چنانچه دو خط در قسمتي از مسير خود با يكديگر مشترك باشند (میزان همپوشانی) – از خيابانهاي يكساني عبور كنند – پوشش جمعيتي مربوط به آن خيابان براي آن شبكه فقط يك بار محاسبه مي‌شود. در واقع اين دو خط اتوبوسراني داراي پوشش مشترك هستند. بدين ترتيب، الگوريتم خطوطي را انتخاب مي‌كند كه داراي سه ويژگي زير باشند:
– از مناطق پرجمعيت شهر عبور كنند و در سطح شهر گسترش خوبي داشته باشند.
– تا مرز امكان كمترين مقدار همپوشاني بين خطوط مختلف شبكه اتوبوسراني وجود داشته باشد.
– کمترين هزينه کل ( طول خط) را داشته باشد.
الگوريتم ژنتيك از ميان خطوط اتوبوسراني نامزد انتخاب (30 خط)، تعدادي خط را برمي‌گزيند كه تابع هدف مسأله را بيشينه سازند.

كاربرد الگوريتم کلونی مورچه براي مسأله طراحي شبكه اتوبوسراني
در مسأله مورد نظر، هر مورچه نماينده يك خط اتوبوسراني است. در الگوریتم کلونی مورچه تعداد مشخصی از مورچه ها در کل فضای مسئله که در اینجا خطوط اتوبوسرانی می باشد، حرکت می کنند و انتخابهایی را انجام می دهند و یک راه حل در فضای مسئله می سازند. بعد از اینکه تمامی مورچه ها راه حل خود را ساختند ، به هر مورچه بنا به راه حلی که ساخته یک امتیاز می دهیم. مورچه های که دارای بهترین امتیاز است می تواند فرمون مسیر خود را با نسبتی افزایش دهد، تا مورچه های بعدی را به سمت بهترین راه حل بکشاند. این عمل اینقدر تکرار می شود تا بهترین مسیر با امتیاز بالاتر در انتها دارای بیشترین فرمون می شود و تمامی مورچه ها به این مسیر کشیده می شوند و جواب نهایی ما می باشد.