Optimization-based Clustering of Traffic Networks Using Distinct Local Components

Unpredictability of travel behaviors and high complexity of accurate physical modeling have challenged researches to discover implicit patterns of congestion propagation and spatial distribution in large urban networks.... [ view full abstract ]

Unpredictability of travel behaviors and high complexity of accurate physical modeling have challenged researches to discover implicit patterns of congestion propagation and spatial distribution in large urban networks. Spatial data mining and clustering allows to partition heterogeneous networks into homogeneous regions and chase spatiotemporal growth of congestion, which is crucial for real-time hierarchical traffic control schemes. In this paper, we develop and solve a binary quadratic optimization model for partitioning heterogeneous networks taking into account contiguity and size constraints for clusters. The proposed approach utilizes set of distinct and robust homogeneous components in the network called ‘snakes’. In the context of this paper, ‘snake’ refers to a sequence of links created by adding new adjacent links iteratively based on their similarity to join previously added links. Firstly, snakes corresponding to all different initial points grow in a way that they have the highest possible homogeneity. Based on robust behavior observed in sub-regions with different level of congestion, we reduce the search space by selecting a sub-set of distinct snakes which cover different parts of the network. Secondly, a quadratic binary optimization framework is designed to find major skeleton of clusters from obtained distinct snakes by minimizing a heterogeneity index. Finally, a fine-tuning step is utilized to associate unassigned links, remaining from the first step, with proper clusters. The proposed clustering framework can be applied in heterogeneous large-scale real networks with fast computation to obtain low variance clusters.