بررسی عملکرد الگوریتم تپه‌نوردی در طراحی خطوط همگانی در شبکه شطرنجی با ماتریس‌های تقاضای تصادفی

چکیده مسئله¬ی طراحی شبکه حمل¬ونقل همگانی یکی از مهمترین مسائلی است که همزمان با توسعه پایدار شهری در نظر گرفته می¬شود. هدف آن است خطوط همگانی به گونه¬ای طراحی ¬شوند که ضمن حفظ محدودیت بودجه بیشترین پوشش تقاضا در سطح شبکه حاصل گردد. تاکنون روش¬¬های ابتکاری زیادی برای حل مسئله طراحی شبکه حمل-ونقل همگانی ارائه شد که جواب¬های نزدیک به بهینه جهانی را در مدت زمان کوتاهی می یابند، اما تمرکز بر روی شبکه¬های حمل¬ونقلی خاص در این حوزه اندک بوده¬است. هدف از این پژوهش ارزیابی عملکرد الگوریتم تپه نوردی در حل مسئله طراحی شبکه خطوط برای شبکه-های شهری با الگوی شطرنجی است. در این راستا مطابق با ادبیات موضوع یک الگوریتم جستجوی محلی از نوع تپه‌نوردی، معرفی می-شود، سپس جهت دستیابی به جواب¬ با کیفیت بالاتر و کاهش احتمال توقف در جواب¬های بهینه محلی با کیفیت پایین، الگوریتم مزبور در ۲۰ تکرار با جواب اولیه متفاوت اجرا می¬شود. مقایسه مقدار متوسط پوشش حاصله از این الگوریتم در یک شبکه شطرنجی ۱۰×۶ (دارای ۶۰ گره) برای ۳۰ ماتریس تقاضای سفر تصادفی، در مقابل جواب دقیق بدست آمده از روش شمارش جواب¬های غالب این امکان را می¬دهد کیفیت پاسخ الگوریتم تپه نوردی ارزیابی شود. این نتایج نشان می‌دهد، در مقایسه با حل دقیق مسئله با شمارش جواب¬های غالب در مدت زمان تقریبا ۴ ساعت پردازش، الگوریتم تپه نوردی می‌تواند تنها در مدت ۱۸ دقیقه و۴۵ ثانیه به جواب‌هایی با اختلاف زیر %۴ نسبت ‌‌به جواب‌های دقیق مسئله دست پیدا کند. واژه های کلیدی طراحی شبکه خطوط همگانی، شبکه شهری شطرنجی، پوشش، الگوریتم تپه‌نوردی، شمارش