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

یکی از مسائل زیرساختی در مدیریت شهری توسعه شبکه شهری حمل ونقل به صورت احداث معابر جدید است. در یک تعریف رایج از این مسئله، هدف آن است که، با درنظرگرفتن محدودیت بودجه، زیرمجموعهای از پروژه ها (معابر) پیشنهادی به شبکه اضافه گردد به گونه ای که مجموع کل زمان سفر استفاده کنندگان شبکه به حداقل برسد. با توجه به ماهیت NP-Hard این مسئله، تاکنون روشهای ابتکاری یا فرا ابتکاری فراوانی در ادبیات موضوع برای حل این مسئله معرفی گردیده است، که از این میان، یکی از موارد موفق الگوریتم فرا ابتکاری کلونی مورچگان بوده است. علیرغم توجه و ارجاع فراوان به این الگوریتم در ادبیات موضوع، کاربرد این الگوریتم در مثالهای بزرگ مقیاس تاکنون کمتر موردتوجه قرارگرفته است. مطالعه پیش رو، با درنظرگرفتن الگوریتم کلونی مورچگان پیشنهادشده در مطالعات پیشین، به بررسی کیفیت جوابهای این الگوریتم در یک مثال بزرگ از شبکه شهری شیکاگو با تعداد ۱۶ پروژه کاندیدا به منظور احداث میپردازد. کاربرد الگوریتم بر روی این مثال، نشان میدهد که از ۱۲ اجرای مستقل الگوریتم کلونی مورچگان، این الگوریتم در ۴ مورد به جواب دقیق مسئله دست پیدا میکند. همچنین، بهطور متوسط، اختلاف جوابهای به دست آمده این الگوریتم با جواب دقیق مسئله تنها ۰/۷ درصد است، در حالیکه زمان اجرای الگوریتم کلونی مورچگان به شکل فراوانی از الگوریتم حل دقیق کمتر است.

کلیدواژه ها:

طراحی شبکه ، مسئله NP-Hard ، الگوریتم فرا ابتکاری ، الگوریتم کلونی مورچگان