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

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

کلیدواژه ها:

طراحی شبکه خطوط ، شبکه شطرنجی ، اولویت بندی حریصانه ، پوشش