Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks

The problem of clustering in urban traffic networks has been mainly studied in static framework by considering traffic conditions at a given time. Nevertheless, it is important to underline that traffic is a strongly time-variant process and it needs to be studied in the spatiotemporal dimension. Investigating the clustering problem over time in the dynamic domain is critical to better understand and reveal the hidden information during the process of congestion formation and dissolution. The primary motivation of the paper is to study the spatiotemporal relation of congested links, observing congestion propagation from a macroscopic perspective, and finally identifying critical pockets of congestion that can aid the design of peripheral control strategies. To achieve this, we first introduce a static clustering method to partition the heterogeneous network into homogeneous connected sub-regions. This method guarantees connectivity of the cluster, which eases the development of a dynamic framework. The proposed clustering approach obtains a feasible set of connected homogeneous components in the network called snakes, which represent a sequence of connected links with similar level of congestion. Secondly, the problem is formulated as a mixed integer linear optimization to find major skeleton of clusters out of this feasible set by minimizing a heterogeneity index. Thirdly, a fine-tuning step is designed to assign the unclustered links of the network to proper clusters while keeping the connectivity. The approach is extended to capture spatiotemporal growth and formation of congestion. The dynamic clustering is based on an iterative and fast procedure that considers the spatiotemporal characteristics of congestion propagation and identifies the links with the highest degree of heterogeneity due to time dependent conditions and finally re-cluster them while by minimizing heterogeneity and imposing connectivity. The developed framework can be directly implemented in a real-time framework due to its fast computation and proper integration of physical properties of congestion.