Predicting traffic congestion propagation patterns: A propagation graph approach

traffic congestion in a road network may propagate to upstream road segments. Such a congestion propagation may make a series of connected road segments congested in the near future. Given a spatial-temporal network and congested road segments in current time, the aim of predicting traffic congestion propagation pattern is to predict where those congestion will propagate to. This can provide users (e.g. city officials) with valuable information on how congestion will propagate in the near future to help mitigating emerging congestions. However, it is challenging to predict in realtime due to complex propagation process between roads and high computational intensity caused by large dataset. Recent studies have been focusing on finding frequent or most likely congestion propagation patterns in historical data. In contrast, this research will address the problem of predicting congestion propagation patterns in the near future. We predict the footprint of congestion propagation as Propagation Graphs (Pro-Graphs) where the root of each Pro-Graph is a set of congested roads propagating congestion to nearby roads. We propose an efficient algorithm called PPI_Fast to achieve this prediction. Our experiments on real-word dataset from Shenzhen, China shows that the PPI_Fast is able to predict near future propagations with AUC of 0.75 and improves the running time of the baseline algorithm. Two case studies have been done to show our work can find meaningful patterns.