Clustering of Heterogeneous Networks with Directional Flows Based on “Snake” Similarities

In urban networks with high demand, pockets of congestion normally appear in different regions with different shapes and might propagate in particular directions varying from day to day. Therefore, finding a clustering method to capture spatiotemporal growth of congestion not only provides a deeper perception of traffic dynamics in urban networks but also allows us to utilize prevailing control methodologies for signalized intersection specifically hierarchical perimeter control approaches. In order to make the application of perimeter control feasible, clusters have to be homogeneous and have a near compact shape. To obtain connected clusters with low variances and reasonable sizes, the authors propose a three-step algorithm. The advantages of the proposed method compared to existing ones are the ability of finding directional congestion within a cluster, robustness with respect to parameters’ calibration, its good performance for networks with low connectivity and missing data. Firstly, the authors start to find best local components for each link of the network in an iterative way. A sequence of links, defined as snake, is updated in each step with adjacent ones based on their similarity to join previously added links. Secondly, based on the information from the first step, similarities are defined for each pair of the links in the whole network. The similarities are computed in a way that put more weight on adjacent local components and facilitate compact shaped clusters. Finally, to find clusters with high intra similarity and low inter similarity, the objective function of Normalized Cut (NCut) algorithm is optimized for the obtained similarity matrix. By using this approach, the authors avoid having clusters with small size which is the problem of solving Ratio Cut or Min-Max Cut functions. The proposed clustering framework is applied in medium and large-size networks based on micro-simulation and empirical data from probe vehicles.

• Supplemental Notes:
  • This paper was sponsored by TRB committee AHB45 Traffic Flow Theory and Characteristics.
• Corporate Authors:

  Transportation Research Board

  500 Fifth Street, NW
  Washington, DC  United States  20001
• Authors:
  • Saeedmanesh, Mohammadreza
  • Geroliminis, Nikolas
• Conference:
  • Transportation Research Board 94th Annual Meeting
  • Location: Washington DC, United States
  • Date: 2015-1-11 to 2015-1-15
• Date: 2015

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; References; Tables;
• Pagination: 17p
• Monograph Title: TRB 94th Annual Meeting Compendium of Papers

Subject/Index Terms

• TRT Terms: Algorithms; Cluster analysis; Methodology; Network links
• Geographic Terms: San Francisco (California); Shenzhen, China
• Subject Areas: Data and Information Technology; Highways; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01555703
• Record Type: Publication
• Report/Paper Numbers: 15-1354
• Files: TRIS, TRB, ATRI
• Created Date: Feb 27 2015 4:43PM