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

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