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

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

Keywords:

طراحی خطوط همگانی , شبکه شطرنجی , پوشش , جستجوی محلی