مسئلهٔ K مسیر کوتاهِ شدنی چندشیوه‌ای در شبکهٔ حمل‌ونقل عمومی تهران و حل آن با الگوریتم‌های کلونی مورچگان و تبرید شبیه‌سازی‌شده

نویسندگان: Malihe Niksirat، Mehdi Ghatee، S. Mehdi Hashemi

منتشرشده در: Applied Mathematical Modelling، جلد 36، شمارهٔ 11، نوامبر 2012، صفحات 5709–5726.

چکیده:

این مقاله به مسئلهٔ K کوتاه‌ترین مسیر مجاز در یک شبکهٔ حمل‌ونقل شامل چند شیوهٔ جابه‌جایی می‌پردازد. شیوه‌های در نظر گرفته‌شده عبارت‌اند از مترو، اتوبوس تندرو، وسیلهٔ نقلیهٔ شخصی و پیاده‌روی. در این شبکه، مسیر مجاز مسیری است که تعداد تغییر شیوهٔ جابه‌جایی در آن محدود باشد و زمان پیمایش و نیز میزان استفاده از پیاده‌روی، مترو و وسیلهٔ شخصی تحت قیودی محدود شوند. زمان پیمایش وابسته به سطح تراکم تعریف می‌شود. ازآنجاکه مسئلهٔ کوتاه‌ترین مسیر مقید، NP-hard است، دو الگوریتم فراابتکاری با نام‌های GASA و BACS را برای مسئلهٔ موردنظر توسعه می‌دهیم. GASA ترکیبی از الگوریتم حریصانه و تبرید شبیه‌سازی‌شده است و BACS، سامانهٔ کلونی مورچه با جست‌وجوی دوطرفه است که از دو کلونی مورچه تشکیل شده است. اعتبار این الگوریتم‌ها را با استفاده از چند شبکهٔ تصادفی چندشیوه‌ای ارزیابی می‌کنیم. افزون بر این، نتایج آن‌ها با CPLEX 12.1 مقایسه می‌شوند. درمی‌یابیم که GASA برای شبکه‌های کوچک مناسب است و BACS در شبکه‌های متوسط و بزرگ‌مقیاس عملکرد بهتری دارد. نتایج ما بر شبکهٔ تهران نیز نشان می‌دهند که BACS مقادیر تابع هدف بهتری نسبت به BACS فراهم می‌کند، زیرا شبکهٔ حمل‌ونقل عمومی تهران تُنُک است.