A New Combinatorial Characteristic Parameter for Clustering-Based Traffic Network Partitioning

Duanyang Liu, Mengting Wang, Guojiang ShenIEEE Access 2019 · DOI

Abstract

Effective urban traffic management requires partitioning large networks into homogeneous subareas to facilitate synchronized signal control. Traditional partitioning methods often rely on single parameters, such as traffic flow, which may fail to capture the full complexity of urban road networks. This paper presents a novel approach using a "combinatorial characteristic parameter" that integrates traffic flow and vehicle speed data via Pearson correlation. By applying this parameter within a "snake" clustering algorithm and a Mixed Integer Linear Programming (MILP) model, the researchers achieved a traffic network partition that is significantly more accurate and consistent than traditional heuristic methods.

Introduction

Managing urban traffic effectively often involves partitioning a massive city network into smaller, homogeneous subareas where intersections share similar traffic patterns. This "divide and conquer" strategy allows for more effective coordination of traffic signals. However, the precision of these partitions is critical; poor partitioning leads to unsynchronized signals and increased congestion.

Problem Statement

The authors identify two major gaps in current partitioning methods:

  1. Parameter Limitation: Most algorithms use only one type of data, such as traffic flow or vehicle density. While flow data is accurate, it is often sparse. Speed data is widespread but noisy. Relying on a single metric provides an incomplete picture of the traffic state.
  2. Algorithmic Local Optima: Many partitioning tools utilize heuristic algorithms. Although computationally efficient, these methods often converge on "local optima"—solutions that are good but not mathematically optimal.

Methodology

The proposed approach consists of two primary modules designed to address the limitations of existing methods, as illustrated in the workflow below.

The proposed traffic network partitioning workflow, featuring combinatorial parameter calculation and the snake-based MILP optimization.

Module A: The Combinatorial Parameter

Instead of selecting a single metric, the researchers combine traffic flow and vehicle speed. They utilize the Pearson Correlation Coefficient (PCC) to determine the strength of the relationship between flow and speed in specific areas. This correlation serves as a weighting factor to blend the two normalized metrics into a single "combinatorial parameter," grounding the model in established traffic flow theory (e.g., Greenshields' model).

Module B: The "Snake" and Linear Programming

The partitioning process follows a three-step sequence:

  • Running Snake: An agglomerative clustering algorithm that starts at a single road link and "grows" by adding the most similar adjacent links.
  • Snake Segmentation: These "snakes" are processed through a Mixed Integer Linear Programming (MILP) model. Unlike heuristics, this model seeks an exact solution to minimize variance within each cluster.
  • Fine Tuning: A final optimization step ensures that any unassigned road links are placed into the most appropriate subarea.

Experimental Setup

The study utilized real-world traffic data from the Xiaoshan District in Hangzhou, China, comprising 473 intersections and 1,312 road links. The experiment focused on a congested corridor of 55 road links during the morning rush hour. Traffic flow was captured via high-definition video cameras, while link speeds were derived from vehicle GPS devices.

Results

The combinatorial parameter was compared against partitions based solely on flow or speed using two metrics: Similarity Rate (SR) (where 1.0 is a perfect match to ground truth) and Normalized Total Variance ($TV_N$) (where lower values indicate better homogeneity).

Parameter Similarity Rate (SR) Normalized Total Variance ($TV_N$)
Combinatorial Parameter 0.96 0.364
Link Speed Only 0.92 0.416
Traffic Flow Only 0.72 0.635

The results demonstrate that the combined metric is significantly more representative of the actual traffic state than any single parameter.

Conclusion

The integration of flow and speed data through a combinatorial parameter, coupled with exact optimization via MILP, provides a robust framework for urban traffic partitioning. While the computational complexity of MILP presents a challenge for real-time city-wide scaling, the gains in partitioning accuracy offer a worthwhile trade-off for high-quality traffic management. Future research will focus on improving algorithmic efficiency for larger networks.

Summary updated

BibTeX
@article{liu2019new,
  author = {Duanyang Liu and Mengting Wang and Guojiang Shen},
  title = {{A New Combinatorial Characteristic Parameter for Clustering-Based Traffic Network Partitioning}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2905618},
}
Figure