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

نوع مقاله : مقاله پژوهشی

نویسندگان

1 استادیار، گروه مهندسی عمران، دانشگاه مازندران، مازندران، ایران

2 دانشجوی کارشناسی، گروه مهندسی عمران، دانشگاه مازندران، مازندران، ایران

چکیده

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

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Transit Routes Network Design by Greedy Prioritization of the Routes in Grid Networks

نویسندگان [English]

  • Amirali Zarrinmehr 1
  • Hanie Moloukzade 2
1 Assistant Professor, Department of Civil Engineering, University of Mazandaran, Mazandaran, Iran.
2 B.Sc., Student, Department of Civil Engineering, University of Mazandaran, Mazandaran, Iran.
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Routes Network Design
  • Grid Network
  • Greedy Prioritization
  • Coverage

مراجع

-افندی زاده زرگری، ش. و افیونیان، م. ر.، (1382)، "طراحی شبکه خطوط حمل و نقل عمومی (اتوبوس‌رانی) با استفاده از تکنیک شاخه و کرانه"، امیرکبیر، 14، (د-54)، ص.589-578.
- وطن­خواه، ا. و قریب، ف.، (1388)، "بررسی اثرات کاربری زمین و توسعه شهری بر حمل و نقل سریع همگانی"، علوم
و تکنولوژی محیط زیست، 11(3)، ص.256-249.
-امین زاده گوهرریزی، ب.، جبارزاده، آ.، رستگار، س.،
و رحمانی، م.، (1398)، "بهینه سازی یکپارچه تخصیص تراکم و کاربری زمین و طراحی شبکه حمل ونقل عمومی-موردپژوهی: منطقه 22 تهران"، مهندسی حمل و نقل، 11 (1)،
ص.199-181.
-دزفولی نژاد، م.، رؤفی، ر.، و دالوند، ا. (1399)، "بررسی اثر تغییر در چگالی شبکه بر نحوه بهینه­سازی تخصیص بودجه محدود بین پل‌‌ها جهت تاب آورسازی شبکه حمل و نقل"، مهندسی زیرساختهای حمل و نقل، 6 (4)، ص.99-81.
-شفاهی، ی.، و عامری، م.، (1396)، "دو روش حل برای انتخاب و زمان بندی پروژه­ها در مساله طراحی شبکه­های حمل و نقل چنددوره یی، مهندسی عمران شریف، 33 (2)،
ص.118-111.
-وزارت نیرو، (1397)، "ترازنامه انرژی، دفتر برنامه‌ریزی کلان برق و انرژی"، معاونت امور برق و انرژی.
-Baaj, M. H., & Mahmassani, H. S. (1991), “An AI‐based approach for transit route system planning and design”, Journal of advanced transportation, 25(2), pp.187-209.
-Cacchiani, V., Iori, M., Locatelli, A., & Martello, S., (2022), “Knapsack problems-An overview of recent advances”, Part II: Multiple, multidimensional, and quadratic knapsack problems, Computers & Operations Research, 143, in press, https://doi.org/10.1016/j.cor.2021.105693.
-Daganzo, C. F., (2010), “Structure of competitive transit networks”, Transportation Research Part B: Methodological, 44(4), pp.434-446.
-Kepaptsoglou, K., & Karlaftis, M., (2009), “Transit route network design problem”, Journal of transportation engineering, 135(8), pp.491-505.
-Khanzad, I., Zarrinmehr, A., Seyedabrishami, S., & Saffarzadeh, M., (2017), “Application of a route expansion algorithm for transit routes design in grid networks”, International Journal of Transportation Engineering, 4(3), pp.179-196.
-Lee, Y. J., & Vuchic, V. R., (2005), “Transit network design with variable demand”, Journal of Transportation Engineering, 131(1), pp.1-10.
-Li, W., Ding, Y., Yang, Y., Sherratt, R. S., Park, J. H., & Wang, J., (2020), “Parameterized algorithms of fundamental NP-hard problems: a survey”, Human-Centric Computing and Information Sciences, 10(1), pp.1-24.
-Mauttone, A., Cancela, H., & Urquhart, M. E., (2021), “Public transportation, In Network Design with Applications to Transportation and Logistics, Springer, Cham., pp. 539-565.
-Miyagawa, M., (2018), “Spacing of intersections in hierarchical road networks”, Journal of the Operations Research Society of Japan, 61(4), pp.272-280.
-Saif, M. A., Zefreh, M. M., & Torok, A., (2019), “Public transport accessibility: a literature review”, Periodica Polytechnica Transportation Engineering, 47(1), pp.36-43.
-Seyedabrishami, S., Rahimi, A., & Zarrinmehr, A., (2017), “Planning the departure of vacant transit vehicles to the median stops in a single line”, Transportation Research Procedia, 25,
pp.1317-1326.
-Stern, R., (1996), “Passenger transfer system review”, 19, Transportation Research Board.
-Tang, L., & Xu, X., (2022), “Optimization for operation scheme of express and local trains in suburban rail transit lines based on station classification and bi-level programming. Journal of Rail Transport Planning & Management, 21, in press, https://doi.org/10.1016/j.jrtpm.2021.100283.
-Ul Abedin, Z., Busch, F., Wang, D. Z., Rau, A., & Du, B., (2018), “Comparison of public transport network design methodologies using solution-quality evaluation”, Journal of Transportation Engineering, Part A: Systems, 144(8), 04018036.
-Walker, J., (2020), “Why do so many public transport networks use grid systems?” https://www.citymetric.com/transport/why-do-so-many-public-transport-networks-use-grid-systems-955.
-Zarrinmehr, A., Aashtiani, H. Z., Nie, Y. M., Azizian, H., (2019), “Complementarity formulation and solution algorithm for auto-transit assignment problem”, Transportation Research Record, 2673(4), pp.384-397
-Zarrinmehr, A., Saffarzadeh, M., & Seyedabrishami, S., (2018), “A local search algorithm for finding optimal transit routes configuration with elastic demand” International Transactions in Operational Research, 25(5), pp.1491-1514.
-Zarrinmehr, A., Saffarzadeh, M., Seyedabrishami, S., & Nie, Y. M., (2016), “A path-based greedy algorithm for multi-objective transit routes design with elastic demand”, Public Transport, 8(2), pp.261-293.
-Zarrinmehr, A., & Shafahi, Y., (2014), “Enumeration of dominant solutions: an application in transport network design”, International Journal of Transportation Engineering, 1(4), pp.335-348.
-Zarrinmehr, A., & Shafahi, Y., (2015), “Accelerating the performance of parallel depth-first-search branch-and-bound algorithm in transportation network design problem”, International Conference on Operations Research and Enterprise Systems (ICORES), Lisbon, Portugal, 10-12 January, pp.359-366.
-Zhao, F., (2006), “Large-scale transit network optimization by minimizing user cost and transfers", Journal of Public Transportation, 9(2), 6.
پژوهشنامه حمل و نقل
دوره 20، شماره 2
تیر 1402
صفحه 147-160

فایل ها

هم رسانی

ارجاع به این مقاله

آمار