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

یکی از مسائل زیرساختی در مدیریت شهری توسعه شبکه شهری حمل و نقل به صورت احداث معابر جدید است. در یک تعریف رایج از این مساله، هدف آن است که، با درنظرگرفتن محدودیت بودجه، زیرمجموعه ای از پروژه ها (معابر) پیشنهادی به شبکه اضافه گردد به گونه ای که مجموع کل زمان سفر استفاده کنندگان شبکه به حداقل برسد. با توجه به ماهیت np-hard این مساله، تا کنون روشهای ابتکاری یا فراابتکاری فراوانی در ادبیات موضوع برای حل این مساله معرفی گردیده است، که از این میان، یکی از موارد موفق الگوریتم فراابتکاری کلونی مورچگان بوده است. علیرغم توجه و ارجاع فراوان به این الگوریتم در ادبیات موضوع، کاربرد این الگوریتم در مثالهای بزرگ مقیاس تا کنون کمتر مورد توجه قرار گرفته است. مطالعه پیش رو، با درنظرگرفتن الگوریتم کلونی مورچگان پیشنهادشده در مطالعات پیشین، به بررسی کیفیت جوابهای این الگوریتم در یک مثال بزرگ از شبکه شهری شیکاگو با تعداد 16 پروژه کاندیدا به منظور احداث میپردازد. کاربرد الگوریتم بر روی این مثال، نشان میدهد که از 12 اجرای مستقل الگوریتم کلونی مورچگان، این الگوریتم در 4 مورد به جواب دقیق مساله دست پیدا میکند. همچنین، به طور متوسط، اختلاف جوابهای به دست آمده این الگوریتم با جواب دقیق مساله تنها 07/0 درصد است، در حالیکه زمان اجرای الگوریتم کلونی مورچگان به شکل قابل ملاحظه ای از الگوریتم حل دقیق کمتر است.