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

مساله طراحی شبکه خطوط همگانی از مسائل اساسی در دستیابی به توسعه پایدار شهری به‌شمار می‌رود. این مساله به یافتن ترکیب بهینه خطوط حمل‌ونقل همگانی می‌پردازد، به‌گونه‌ای که با حفظ محدودیت بودجه، هدف خاصی در شبکه تامین گردد. باتوجه به این‌که طراحی شبکه، یک مسئله از نوع پیچیده و نمایی است، دستیابی به جواب دقیق (بهینه جهانی) آن در ابعاد بزرگ نیازمند روش‌های‌حل سیستماتیک همچون الگوریتم‌های ابتکاری/فرابتکاری است. این الگوریتم‌ها به‌طور گسترده در ادبیات تحقیق مورد استفاده قرارگرفتند، اما تمرکز بر روی انواع شبکه‌های حمل‌ونقلی با ویژگی‌های خاص اندک بوده‌است. هدف این مقاله طراحی خطوط شبکه حمل‌ونقلی در شبکه‌های شهری با الگوی شطرنجی است به گونه‌ای که، ضمن حفظ محدودیت بودجه، حداکثر پوشش در شبکه حاصل گردد. برای این منظور، این مطالعه یک الگوریتم جدید، از نوع ابتکاری –طراحی‌شده به طور خاص با تمرکز برای شبکه های شطرنجی– پیشنهاد میکند. الگوریتم پیشنهادی یک شاخص حریصانه موسوم به شاخص تقاضا ارائه داده و از آن برای ارتباط بین گره های پرتقاضا در شبکه استفاده میکند؛ به این ترتیب که به طور تکراری، هربار گره دارای بیشترین شاخص تقاضا انتخاب و یک خط همگانی کاندیدای عبوری از آن به ترکیب خطوط موجود اضافه میشود. مقایسه بهترین جواب های حاصل از الگوریتم ابتکاری در یک شبکه شطرنجی 10×6 برای 30 ماتریس تقاضای سفر تصادفی، در مقابل جواب‌های دقیق مساله نشان می‌دهد که الگوریتم ابتکاری می‌تواند در زمان کوتاه قابل‌توجه‌ای، جواب هایی نزدیک‌به جواب‌های دقیق مسئله را بیابد. مطابق نتایج به دست آمده، در مقایسه با حل دقیق در مدت زمان تقریبا 4 ساعت، الگوریتم پیشنهاد شده می‌تواند در مدت‌زمان (8±) 29 ثانیه، به طور متوسط، به جواب‌هایی با اختلاف 2/9 درصد نسبت ‌‌به جواب‌های بهینه جهانی دست پیدا کند.

transit routes network design by greedy prioritization of the routes in grid networks

the problem of transit routes network design is one of the fundamental problems in moving towards sustainable urban development. this problem deals with finding the optimal configuration of transit routes so as to satisfy a specific objective while holding the budget constraint. regarding that network design is a complex and exponential problem, achieving a solution close to the exact solution (global optimum) in large-scale calls for systematic methods such as heuristic/meta-heuristic algorithms. such algorithms have been extensively devised in the related literature, though, less effort has been put to investigate various types of transportation network topologies with specific settings. this paper aims to design urban transit routes configuration in urban settings for “grid” networks in order to achieve the maximum coverage through the network within the budget level. to this end, this study proposes a novel heuristic-type algorithm dedicated to deal with grid-type networks. the proposed algorithm introduces a greedy index namely the “demand index” and exploits this index to make connections among the nodes with high levels of demand. in each iteration, the node with the highest demand index is selected and one of the candidate routes passing through that node is incorporated into the existing routes configuration. comparing the results obtained from the proposed algorithm against the exact solutions in a 6×10 grid network over 30 random demand matrices suggests that the proposed algorithm is capable to hit near-optimal solutions within notably short run-times. according to the results, in comparison to the exact solution in almost 4 hours run-time, within only 29(±8) seconds of run-time, on average, the proposed algorithm can achieve solutions with 2.9% difference from global optimal solutions.