Volume 21 Issue 5
Nov.  2021
Turn off MathJax
Article Contents
Article Navigation >  Journal of Traffic and Transportation Engineering  > 2021  >  21(5): 238-250
YIN Chen-kun, FANG Ru, LI Tuo. NCut partitioning algorithm for urban road networks based on similarity of traffic flow time series[J]. Journal of Traffic and Transportation Engineering, 2021, 21(5): 238-250. doi: 10.19818/j.cnki.1671-1637.2021.05.020
Citation: YIN Chen-kun, FANG Ru, LI Tuo. NCut partitioning algorithm for urban road networks based on similarity of traffic flow time series[J]. Journal of Traffic and Transportation Engineering, 2021, 21(5): 238-250. doi: 10.19818/j.cnki.1671-1637.2021.05.020
shu

NCut partitioning algorithm for urban road networks based on similarity of traffic flow time series

doi: 10.19818/j.cnki.1671-1637.2021.05.020
  • 1.

    School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China

  • 2.

    Luban (Beijing) E-Commerce Technology Co., Ltd., Beijing 102308, China

Funds:

National Natural Science Foundation of China 62073025

National Natural Science Foundation of China 62073026

More Information
  • Author Bio:

    YIN Chen-kun(1981-), male, associate professor, PhD, chkyin@bjtu.edu.cn

  • Received Date: 2021-05-10
    Available Online: 2021-11-13
  • Publish Date: 2021-10-01
    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.

     

    • FullText(HTML)
  • loading
    • References(30)
  • [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.042

    LIU 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.htm

    LU 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.004

    YIN 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.
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML

    Article Metrics

    Article views (812) PDF downloads(103) Cited by()
    Proportional views
    Related

    Copyright《Journal of Traffic and Transportation Engineering》编辑部陕ICP备05001904号-1

    Address ：Editorial Department of Journal of Traffic and Transportation Engineering, Chang 'an University, Middle Section of South Second Ring Road, Xi 'an, Shaanxi（710064） Tel：029-82334388 Email：jygc@chd.edu.cn

    All visit:Today's visit:

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return