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

طراحی خطوط همگانی، در این مقاله، به یافتن موقعیت خطوط همگانی در یک شبکه می پردازد، به طوری که هم زمان با حفظ محدودیت بودجه بیشترین پوشش تقاضا در شبکه حاصل گردد. روش های ابتکاری فراوانی برای حل مسیله طراحی شبکه حمل و نقل همگانی ارایه شده است که جواب هایی نزدیک به بهینه جهانی را در مدت زمان منطقی می یابند. بااین حال، تمرکز بر روی شبکه های حمل و نقلی خاص در این حوزه اندک بوده است. هدف از این پژوهش معرفی و ارزیابی عملکرد یک الگوریتم جستجوی محلی از نوع تپه نوردی در حل این مسیله برای شبکه های شهری با الگوی شطرنجی است. این الگوریتم، در هر اجرا، 20 بار و هر بار با شروع از یک جواب تصادفی اولیه، با تغییرات جزیی و حرکت به جواب های همسایه سعی می کند ترکیب خطوط همگانی را بهبود دهد. مقایسه مقدار متوسط پوشش حاصله از این الگوریتم در یک شبکه شطرنجی 10×6 (دارای 60 گره) برای 30 ماتریس تقاضای تصادفی نشان می دهد که -در مقایسه با حل دقیق مسیله از طریق شمردن جواب های غالب با مدت زمان متوسط 3 ساعت و 57 دقیقه- الگوریتم پیشنهادی به طور متوسط می تواند در مدت زمان زیر 20 دقیقه به جواب هایی با اختلاف زیر %4 پوشش نسبت به جواب های دقیق مسیله دست یابد.