Discovering Urban Traffic Congestion Propagation Patterns with Taxi Trajectory Data

Traffic congestion has gradually become a focal issue in people's daily life. When the traffic flow on a road segment exceeds its actual capacity, congestion takes place. During rush hours, a congested road segment must carry heavy loads for a long time and is very likely to spread traffic congestion to this road's adjacent segments via the spatial structure of the road. The new infected road segments continue propagating congestion in the same way. In this paper, we attempt to model the congestion propagation phenomenon with a space-temporal congestion subgraph (STCS). To this end, we detect each segment regardless of whether it is congested during consecutive time intervals and build the connection of two segments in terms of their spatio-temporal properties. Due to the sparseness of the trajectory data, two strategies of filling missing congestion edges from both temporal and spatial viewpoints are also proposed. Since STCSes are constructed from the same time interval over different days, we design a specific algorithm to discover the frequent congestion subgraphs. Finally, we evaluate the solution on Shanghai taxicab data and the corresponding road network. The experiment shows that the frequent congestion subgraph can reveal an urban congestion propagation pattern.