时变条件下基于路径冗余识别关键路段方法

龚华天; 杨晓光

doi:10.3963/j.jssn.1674-4861.2024.05.002

时变条件下基于路径冗余识别关键路段方法

doi: 10.3963/j.jssn.1674-4861.2024.05.002

龚华天^{1, 2,},
杨晓光^{1, 2, ,}

1.
同济大学城市交通研究院上海 201804
2.
同济大学交通学院上海 201804

基金项目:

国家自然科学基金项目 52072264

广西科技重大专项项目 2023AA14006

郑州市重大科技创新专项子课题项目 2021KJZX0060-9

详细信息

作者简介:
龚华天（1995—），博士研究生. 研究方向：城市道路交通网络优化设计等. E-mail：ghttongji@tongji.edu.cn

通讯作者:
杨晓光（1959—），博士，教授. 研究方向：智能交通和复杂交通网络等. E-mail：yangxg@tongji.edu.cn

中图分类号: U491.5+4
计量
- 文章访问数: 119
- HTML全文浏览量: 50
- PDF下载量: 24
- 被引次数: 0
出版历程
- 收稿日期: 2023-12-05
- 网络出版日期: 2025-01-22

A Method for Identifying Key Links Based on Path Redundancy Under Time-Varying Conditions

GONG Huatian^{1, 2
,},
YANG Xiaoguang^{1, 2
, ,}

1.
Urban Mobility Institute, Tongji University, Shanghai 201804, China
2.
College of Transportation, Tongji University, Shanghai 201804, China

摘要

摘要: 针对道路网络路径冗余性的关键道路识别研究不仅有助于提高日常出行的效率，更在灾害应急时为救援和疏散提供重要的路径备选方案。本文提出了关键道路识别模型，该模型全面考虑了道路系统中的时变因素，包括出行起讫点（origin-destination，OD）需求、OD对（OD pair）以及道路交通网络的拥挤状况；通过分析每个时段下的时变因素，计算当前时段的道路网络路径冗余性；结合每个时段的权重和对应的道路网络路径冗余性，得到道路网络路径冗余性的期望值，从而准确地识别关键路段；为解决求解大规模路径冗余性带来的计算挑战，通过对城市道路网络结构进行重构，利用具有多项式计算时间性质的最大流和最小费用流算法迭代求解，实现模型的快速求解。本文在平陆运河桥梁群拆除重建工程的实际应用中，验证了模型和算法的有效性和适用性；结果表明：通过分析桥梁群在拆除重建前后对钦州市道路网络冗余性的影响，揭示了OD对路径冗余性的变化情况，从而为施工前后实施精细化的交通管理措施提供了依据；在计算效率方面，与商业软件Gurobi相比，计算时间提高了17.90倍，证明了其在处理大规模现实城市道路网络中的适用性。本文可以可以针对性地增强关键路段的抗灾能力，从而有助于构建1个更具抗灾救灾能力的城市道路交通系统。
- 交通工程 /
- 关键路段 /
- 时变 /
- 路径冗余 /
- 独立路径 /
- 平陆运河
Abstract: The study focuses on a model for identifying critical road links based on path redundancy in road networks. Path redundancy enhances efficiency for daily travel and provides crucial alternative routes during emergency situations. This model comprehensively considers time-varying factors in the road system, including origin-destination (OD) demand, OD pair, and road congestion. By analyzing time-varying factors for each period, the path redundancy of the road network is calculated. Furthermore, combining the weights of each period with their corresponding path redundancy yields the expected value of path redundancy, facilitating accurate identification of critical links. To address the computational challenge of solving for large-scale path redundancy, a reconstruction of the urban road network structure is performed, enabling the use of maximum flow and minimum cost flow algorithms, which have polynomial time complexity, for iterative solutions. The effectiveness and applicability of the model and algorithm are verified through practical application in the Pinglu Canal bridge reconstruction project. Results reveal the impact of the bridge group's removal and reconstruction on the redundancy of the road network in Qinzhou. Changes in OD pair path redundancy are highlighted, providing a basis for refined traffic management measures before and after construction. In terms of computational efficiency, the proposed algorithm shows a significant advantage over Gurobi. The computation time improves by 17.90 times, demonstrating its suitability for large-scale urban road networks. This paper can be targeted to enhance the resilience of key road sections, thereby contributing to the construction of a more resilient urban road transport system.
- transportation engineering /
- critical links /
- time-varying /
- path redundancy /
- distinct path /
- PingLu Canal

HTML全文

图 1 起终点的分解

Figure 1. Decomposition of origin and destination

下载: 全尺寸图片幻灯片

图 2 算法计算示意流程图

Figure 2. Algorithm flow diagram

下载: 全尺寸图片幻灯片

图 3 平陆运河示意图

Figure 3. Pinglu Canal diagram

下载: 全尺寸图片幻灯片

图 4 6座桥梁拆建位置

Figure 4. Location of the six bridges demolition

下载: 全尺寸图片幻灯片

图 5 钦州市道路网络

Figure 5. Road network in Qinzhou

下载: 全尺寸图片幻灯片

图 6 钦州市区交通小区划分和应急设施

Figure 6. Division of traffic zone and emergency facilities in Qinzhou

下载: 全尺寸图片幻灯片

图 7 不同时间段内OD对之间的出行需求分布

Figure 7. Distribution of travel demand between OD pairs in different time periods

下载: 全尺寸图片幻灯片

图 8 子材大桥拆除前后3个时间段的OD对路径冗余性影响情况

Figure 8. Impact of OD on path redundancy in three time periods before and after dismantling of zhicai bridge

下载: 全尺寸图片幻灯片

图 9 2种方法的计算性能比较

Figure 9. Comparative analysis of computational performance between two methods

下载: 全尺寸图片幻灯片

图 10 2种方法计算每个OD对的性能比较

Figure 10. Performance comparison of computing each od pair between the two methods

下载: 全尺寸图片幻灯片

表 1 6座桥梁的关键路段指标

Table 1. Critical road link indicators for six bridges

桥名	各个时间段OD对z_od(t) = 1			关键路段指标I_{(i, j)}
桥名	06∶00—09∶00	09∶00—17∶00	17∶00—20∶00	关键路段指标I_{(i, j)}
子材大桥	83	182	95	0.18
钦江大桥	91	194	104	0.14
永福大桥	86	206	108	0.13
金海湾大桥	100	225	118	0.06
环城北路大桥	103	236	124	0.03
南北公路大桥	105	239	126	0.02
桥梁拆除重建前	106	240	127
OD对总数	225	512	227

下载: 导出CSV

参考文献(27)

[1]	GONÇALVES L, RIBEIRO P. Resilience of urban transportation systems. Concept, characteristics, and methods[J]. Journal of Transport Geography, 2020, 85: 102727. doi: 10.1016/j.jtrangeo.2020.102727
[2]	陈思妤, 李洁, 胡演诚, 等. 面向常发性拥堵的城市局部路网韧性评价与分析[J]. 交通信息与安全, 2022, 40 (4): 138-147. doi: 10.3963/j.jssn.1674-4861.2022.04.015 CHEN S Y, LI J, HU Y C, et al. An evaluation and analysis on the resilience of the urban local road network for recurrent congestions[J]. Journal of Transport Information and Safety, 2022, 40 (4): 138-147. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2022.04.015
[3]	程国柱, 周传淼, 别一鸣. 占道施工影响下区域路网容量计算与关键路段识别方法[J]. 哈尔滨工业大学学报, 2024, 56 (3): 126-135. CHENG G Z, ZHOU C M, BIE Y M. Regional road network capacity calculation and key section identification under the impact of road occupation construction[J]. Journal of Harbin Institute of Technology, 2024, 56 (3): 126-135. (in Chinese)
[4]	ALMOTAHARI A, YAZICI M A. A link criticality index embedded in the convex combinations solution of user equilibrium traffic assignment[J]. Transportation Research Part A: Policy and Practice, 2019, 126: 67-82. doi: 10.1016/j.tra.2019.06.005
[5]	HOLME P, KIM B J, YOON C N, et al. Attack vulnerability of complex networks[J]. Physical Review E, 2002, 65(5): 056109. doi: 10.1103/PhysRevE.65.056109
[6]	AYDIN N Y, DUZGUN H S, WENZEL F, et al. Integration of stress testing with graph theory to assess the resilience of urban road networks under seismic hazards[J]. Natural Hazards, 2018, 91: 37-68. doi: 10.1007/s11069-017-3112-z
[7]	NAGURNEY A, QIANG Q. A network efficiency measure with application to critical infrastructure networks[J]. Journal of Global Optimization, 2008, 40: 261-275. doi: 10.1007/s10898-007-9198-1
[8]	JAFINO B A, KWAKKEL J, VERBRAECK A. Transport network criticality metrics: a comparative analysis and a guideline for selection[J]. Transport Reviews, 2020, 40(2): 241-264. doi: 10.1080/01441647.2019.1703843
[9]	GOKALP C, PATIL P N, BOYLES S D. Post-disaster recovery sequencing strategy for road networks[J]. Transportation Research Part B: Methodological, 2021, 153: 228-245. doi: 10.1016/j.trb.2021.09.007
[10]	ZHANG W, WANG N. Resilience-based risk mitigation for road networks[J]. Structural Safety, 2016, 62: 57-65. doi: 10.1016/j.strusafe.2016.06.003
[11]	GU Y, FU X, LIU Z, et al. Performance of transportation network under perturbations: reliability, vulnerability, and resilience[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 133: 101809. doi: 10.1016/j.tre.2019.11.003
[12]	DONG S, WANG H, MOSTAFAVI A, et al. Robust component: a robustness measure that incorporates access to critical facilities under disruptions[J]. Journal of the Royal Society Interface, 2019, 16 (157): 20190149. doi: 10.1098/rsif.2019.0149
[13]	DONG S, ESMALIAN A, FARAHMAND H, et al. An integrated physical-social analysis of disrupted access to critical facilities and community service-loss tolerance in urban flooding[J]. Computers, Environment and Urban Systems, 2020, 80: 101443. doi: 10.1016/j.compenvurbsys.2019.101443
[14]	GANGWAL U, SIDERS A, HORNEY J, et al. Critical facility accessibility and road criticality assessment considering flood-induced partial failure[J]. Sustainable and Resilient Infrastructure, 2023, (8): 337-355.
[15]	龚华天, 杨晓光. 时变交通拥挤和需求随机的移动设施运营优化[J]. 交通运输工程与信息学报, 2024, 22 (2): 147-162. GONG H T, YANG X G. Optimization of mobile facility operations under time-varying traffic congestion and stochastic demand[J]. Journal of Transportation Engineering and Information, 2024, 22 (2): 147-162. (in Chinese)
[16]	GONG H T, YANG X G. A two-stage stochastic programming for the integrated emergency mobility facility allocation and road network design under uncertainty[J]. Networks and Spatial Economics, 2024, 144: 1-42.
[17]	XU X D, CHEN A, XU G, et al. Enhancing network resilience by adding redundancy to road networks[J]. Transportation Research Part E: Logistics and Transportation Review, 2021, 154: 102448. doi: 10.1016/j.tre.2021.102448
[18]	XU X D, CHEN A, JANSUWAN S, et al. Transportation network redundancy: complementary measures and computational methods[J]. Transportation Research Part B: Methodological, 2018, 114: 68-85. doi: 10.1016/j.trb.2018.05.014
[19]	SHRESTHA J K, PUDASAINI P, MUSSONE L. Rural road network performance and pre-disaster planning: an assessment methodology considering redundancy[J]. Transportation Planning and Technology, 2021, 44 (7): 726-743. doi: 10.1080/03081060.2021.1956809
[20]	BOYLES S D, LOWNES N E, UNNIKRISHNAN A. Transportation network analysis[M/OL]. (2023-8-21)[2023-12-22]. https://sboyles.github.io/book.pdf.
[21]	DIAL R B. A probabilistic multipath traffic assignment model which obviates path enumeration[J]. Transportation Research, 1971, 5 (2): 83-111. doi: 10.1016/0041-1647(71)90012-8
[22]	JANSUWAN S, CHEN A, XU X D. Analysis of freight transportation network redundancy: an application to Utah's bi-modal network for transporting coal[J]. Transportation Research Part A: Policy and Practice, 2021, 151: 154-171. doi: 10.1016/j.tra.2021.06.019
[23]	LEURENT F M. Curbing the computational difficulty of the logit equilibrium assignment model[J]. Transportation Research Part B: Methodological, 1997, 31 (4): 315-326.
[24]	ZHAO R, XU X, CHEN A. Alternative method of counting the number of efficient paths in a transportation network[J]. Transportmetrica A: Transport Science, 2022, 18(3): 1207-1233.
[25]	KURAUCHI F, UNO N, SUMALEE A, et al. Network evaluation based on connectivity vulnerability[C]. The 18th International Symposium on Transportation and Traffic Theory, Boston, US: IAC, 2009.
[26]	CRUZ-MEJÍA O, LETCHFORD A N. A survey on exact algorithms for the maximum flow and minimum-cost flow problems[J]. Networks, 2023, 82 (2): 167-176.
[27]	中华人民共和国住房和城乡建设部. 城市道路工程设计规范: CJJ 37—2012[S]. 北京: 中国建筑工业出版社, 2012. Ministry of Housing and Urban-Rural Development, People's Republic of China. Urban road engineering design code: CJJ 37—2012[S]. Beijing: China Building and Construction Press, 2012. (in Chinese)