NCut partitioning algorithm for urban road networks based on similarity of traffic flow time series
-
摘要: 针对大规模城市道路交通路网分区的实际需求，基于可反映时间序列变化趋势的皮尔逊相关系数和度量空间关系的欧式距离，构建了一种衡量交通流时间序列相似性的综合指标; 结合交通流时间序列的时空相似性特点，引入子区内的空间连通约束，利用归一化割(NCut)算法设计了一种改进的路网静态分区算法; 为体现交通路网分区的时变特征，选取了合适的评价指标来确定每一时间段内合理的分区数量，提出了一种基于时间序列的NCut路网动态分区算法; 利用北京市东北二环区域内采集的路段交通流速度数据，应用所设计的算法对7.23 km2的路网进行分区，对比了晚高峰时期的分区效果。研究结果表明：所提出的分区算法能实现对路网内不同区域交通状况的有效识别，以30 min为间隔的动态分区算法能划分出数量和范围随时间变化的多个可变子区域; 与子区数固定为2、3、4、5的静态分区算法相比，动态分区算法的评价指标分别提升了63.77%、50.06%、6.43%和7.13%，提高了路网分区效果。可见，本文提出的动态分区算法在保证子区内部连通性的基础上可将异质路网划分成多个内部同质子区域，并充分体现交通流动态演化的时空特性，有利于制定动态的多区域边界控制方案。Abstract: Under practical demand of partitioning for large-scale urban road traffic networks, a comprehensive index that measures the similarity of traffic flow time series was constructed based on the Pearson correlation coefficient and Euclidean distance which reflects the trend and describes the spatial relationships for time series. By incorporating the spatial-temporal similarity of the traffic flow time series, an improved static partitioning algorithm for road networks was designed using the normalized cut (NCut) algorithm under the spatial connectivity constraint for each subregion. To reflect the time-varying characteristics of road networks, reasonable cluster numbers during each time period was determined by selecting an appropriate evaluation criterion, and a dynamic partitioning algorithm of the road network based on NCut for the time series was proposed. By using the link traffic flow speed data collected within a region in the Northeast Second Ring of Beijing, the designed partitioning algorithms were applied to the road network covering 7.23 km2, and the partitioning performances during evening peak hours was compared. Analysis results indicate that the proposed partitioning algorithms can effectively distinguish the traffic conditions in different areas within the road network. Using the dynamic partitioning algorithm with a time interval of 30 min, the road network can be divided into several alterable subregions with time-varying cluster numbers and time-varying scopes. Compared to the static partitioning algorithm using fixed subregion numbers of 2, 3, 4, and 5, the evaluation criterion of the proposed dynamic partitioning algorithm increase by 63.77%, 50.06%, 6.43%, and 7.13%, respectively, and the partitioning performance for the road network improves. Therefore, the proposed dynamic partitioning algorithm can divide the heterogeneous road networks into a number of internally homogeneous subregions while the internal connectivity within each subregion is guaranteed, and can fully embody the spatial-temporal evolution characteristics of the traffic flow, and can benefit to formulating dynamical perimeter control scheme for multiple regions. 2 tabs, 8 figs, 30 refs.
-
图 2 不同时段的路网速度分布直方图
Figure 2. Histograms of road network speed distribution at different time intervals
图 3 16:30~17:00时段内不同子区数k的静态分区结果
Figure 3. Static partitioning results for different cluster numbers during 16:30-17:00
图 4 16:30~17:00内不同子区数下的子区域速度分布直方图
Figure 4. Histogram of subregion speed distribution for different cluster numbers during 16:30-17:00
图 5 静态分区下不同分区数时变曲线
Figure 5. Time-varying curves of different cluster numbers using static partitioning
图 7 动态分区下子区路段数量和平均速度时变曲线
Figure 7. Time-varying curves of link numbers and average speeds using dynamic partitioning
图 8 动态分区下子区域更新、分裂和合并过程
Figure 8. Updating, splitting and merging process of dynamic partitioning
表 1 静态分区下各子区路段速度的统计结果及分区评价指标
Table 1. Statistics of link speed in different subregions and evaluation index for static partitioning
k 子区1速度/ (km·h-1) 子区2速度/ (km·h-1) 子区3速度/ (km·h-1) 子区4速度/ (km·h-1) 子区5速度/ (km·h-1) Vk Sk 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 2 30.51 9.74 30.54 9.30 0.97 0.87 3 30.40 9.79 32.70 9.06 29.40 9.19 0.89 0.97 4 30.77 9.01 32.66 8.90 29.89 10.76 27.70 9.12 0.78 0.79 5 31.16 8.94 35.62 9.18 29.09 9.21 28.62 8.68 29.89 10.77 0.83 0.80 
下载: 导出CSV
表 2 16:00~20:00内动态分区和静态分区下的M
Table 2. M of dynamic partitioning and static partitioning during 16:00-20:00
分区 SP (k=2) SP (k=3) SP (k=4) SP (k=5) DP M/(km·h-1) 21.34 23.29 32.83 32.61 34.94 DP性能提升率/% 63.77 50.06 6.43 7.13
下载: 导出CSV
-
[1] LIU Qiang, WANG Qing, LIU Shu-an. An improved sub- networks partitioning method for urban traffic networks[C]// IEEE. 31st Chinese Control and Decision Conference. New York: IEEE, 2019: 6405-6410. [2] XUN Jing, LIU Tong, NING Bin, et al. Using approximate dynamic programming to maximize regenerative energy utilization for metro[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(9): 3650-3662. doi: 10.1109/TITS.2019.2930766 [3] 刘小明, 何忠贺. 城市智能交通系统技术发展现状及趋势[J]. 自动化博览, 2015, 32(1): 58-60. doi: 10.3969/j.issn.1003-0492.2015.01.042LIU Xiao-ming, HE Zhong-he. Development and tendency of intelligent transportation systems in China[J]. Automation Panorama, 2015, 32(1): 58-60. (in Chinese) doi: 10.3969/j.issn.1003-0492.2015.01.042 [4] WALINCHUS R J. Real-time network decomposition and subnetwork interfacing[J]. Highway Research Record, 1971, 366: 20-28. [5] DAGANZO C F. Urban gridlock: macroscopic modeling and mitigation approaches[J]. Transportation Research Part B: Methodological, 2007, 41(1): 49-62. doi: 10.1016/j.trb.2006.03.001 [6] GEROLIMINIS N, DAGANZO C F. Existence of urban- scale macroscopic fundamental diagrams: some experimental findings[J]. Transportation Research Part B: Methodological, 2008, 42(9): 759-770. doi: 10.1016/j.trb.2008.02.002 [7] JI Y, GEROLIMINIS N. On the spatial partitioning of urban transportation networks[J]. Transportation Research Part B: Methodological, 2012, 46(10): 1639-1656. doi: 10.1016/j.trb.2012.08.005 [8] SAEDI R, SAEEDMANESH M, ZOCKAIE A, et al. Estimating network travel time reliability with network partitioning[J]. Transportation Research Part C: Emerging Technologies, 2020, 112: 46-61. doi: 10.1016/j.trc.2020.01.013 [9] MA Dong-fang, LI Wen-jing, SONG Xiang, et al. Time-of-day breakpoints optimisation through recursive time series partitioning[J]. IET Intelligent Transport Systems, 2019, 13(4): 683-692. doi: 10.1049/iet-its.2018.5162 [10] LECLERCQ L, LADINO A, BECARIE C. Enforcing optimal routing through dynamic avoidance maps[J]. Transportation Research Part B: Methodological, 2021, 149: 118-137. doi: 10.1016/j.trb.2021.05.002 [11] ZHANG Yi-cheng, SU Rong. An optimization model and traffic light control scheme for heterogeneous traffic systems[J]. Transportation Research Part C: Emerging Technologies, 2021, 124: 102911. doi: 10.1016/j.trc.2020.102911 [12] DANTSUJI T, HIRABAYASHI S, GE Q, et al. Cross comparison of spatial partitioning methods for an urban transportation network[J]. International Journal of Intelligent Transportation Systems Research, 2019, 18(3): 412-421. [13] LI Dai, HOU Zhong-sheng. Perimeter control of urban traffic networks based on model-free adaptive control[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(10): 1-13. doi: 10.1109/TITS.2021.3113621 [14] HADDAD J, MIRKIN B. Resilient perimeter control of macroscopic fundamental diagram networks under cyberattacks[J]. Transportation Research Part B: Methodological, 2020, 132: 44-59. doi: 10.1016/j.trb.2019.01.020 [15] HADDAD J, ZHENG Z. Adaptive perimeter control for multi-region accumulation-based models with state delays[J]. Transportation Research Part B: Methodological, 2020, 137: 133-153. doi: 10.1016/j.trb.2018.05.019 [16] DO L N N, VU H L, VO B Q, et al. An effective spatial-temporal attention based neural network for traffic flow prediction[J]. Transportation Research Part C: Emerging Technologies, 2019, 108: 12-28. doi: 10.1016/j.trc.2019.09.008 [17] WANG Wei, ZHANG Han-yu, LI Tong, et al. An interpretable model for short term traffic flow prediction[J]. Mathematics and Computers in Simulation, 2019, 171: 264-278. [18] WANG Chen, LIU Lin, LU Zhen-bo. On the safety effects of spatially aggregated traffic flow parameters at macro-levels[J]. Advances in Mechanical Engineering, 2019, 11(1): 1-13. [19] GU Zi-yuan, SABERI M. A bi-partitioning approach to congestion pattern recognition in a congested monocentric city[J]. Transportation Research Part C: Emerging Technologies, 2019, 109: 305-320. doi: 10.1016/j.trc.2019.10.016 [20] YANG Sen-yuan, WU Jian-ping, XU Yan-yan, et al. Revealing heterogeneous spatiotemporal traffic flow patterns of urban road network via tensor decomposition-based clustering approach[J]. Physica A: Statistical Mechanics and its Applications, 2019, 526(3): 120688. [21] 卢守峰, 陶黎明, 江勇东. 考虑连接性的路网划分算法[J]. 交通运输系统工程与信息, 2018, 18(5): 95-102. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201805015.htmLU Shou-feng, TAO Li-ming, JIANG Yong-dong. Road network partition algorithm considering connectivity[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(5): 95-102. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201805015.htm [22] SAEEDMANESH M, GEROLIMINIS N. Optimization-based clustering of traffic networks using distinct local components[C]// IEEE. 2015 IEEE 18th International Conference on Intelligent Transportation Systems. New York: IEEE, 2015: 2135-2140. [23] DIMITRIOU L, NIKOLAOU P. Dynamic partitioning of urban road networks based on their topological and operational characteristics[C]//IEEE. 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems. New York: IEEE, 2017: 457-462. [24] 尹洪英, 徐丽群, 曹永荣. 基于谱聚类算法的城市路网动态分区研究[J]. 交通信息与安全, 2010, 28(1): 16-19, 25. doi: 10.3963/j.issn.1674-4861.2010.01.004YIN Hong-ying, XU Li-qun, CAO Yong-hua. City transportation road network dynamic zoning based on spectral clustering algorithm[J]. Journal of Transport Information and Safety, 2010, 28(1): 16-19, 25. (in Chinese) doi: 10.3963/j.issn.1674-4861.2010.01.004 [25] GUO Ya-juan, YANG Li-cai, HAO Shen-xue, et al. Dynamic identification of urban traffic congestion warning communities in heterogeneous networks[J]. Physica A: Statistical Mechanics and its Applications, 2019, 522(3): 98-111. [26] SAEEDMANESH M, GEROLIMINIS N. Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks[J]. Transportation Research Part B: Methodological, 2017, 105: 193-211. doi: 10.1016/j.trb.2017.08.021 [27] SAEEDMANESH M, GEROLIMINIS N. On the spatial partitioning of urban transportation networks[J]. Transportation Research Part B: Methodological, 2012, 46(10): 1639-1656. doi: 10.1016/j.trb.2012.08.005 [28] SAEEDMANESH M, GEROLIMINIS N. Clustering of heterogeneous networks with directional flows based on "Snake" similarities[J]. Transportation Research Part B: Methodological, 2016, 91: 250-269. doi: 10.1016/j.trb.2016.05.008 [29] HOU Zhong-sheng, LI Xing-yi. Repeatability and similarity of freeway traffic flow and long-term prediction under big data[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(6): 1786-1796. doi: 10.1109/TITS.2015.2511156 [30] PERERA S, PERERA H N, PERERA K. Topological structure of the road traffic network in the western regional megapolis, Sri Lanka[C]//IEEE. 4th International Multidisciplinary Moratuwa Engineering Research Conference. New York: IEEE, 2018: 37-42. -
点击查看大图
图(8) / 表(2)
计量
- 文章访问数: 789
- HTML全文浏览量: 206
- PDF下载量: 102
- 被引次数: 0
