Let Trajectories Speak Out the Traffic Bottlenecks

Hui Luo, Zhifeng Bao, Gao Cong, J. Shane Culpepper, Nguyen Lu Dang Khoa

Introduction

Traffic congestion is a multi-billion dollar problem that plagues modern cities. Identifying the actual source of a traffic jam is surprisingly difficult. Traditional methods often rely on fixed sensors, which are frequently broken or missing, or simple speed thresholds that fail to capture the dynamic nature of traffic. A bottleneck isn't just a crowded road; it is a segment that causes a "cascade" of congestion in neighboring areas.

This paper introduces a data-driven framework to identify traffic bottlenecks by analyzing how congestion spreads through a road network using real-world vehicle trajectories. The authors tackle the Trajectory-driven Traffic Bottleneck Identification (TBI) problem: given a massive database of GPS trajectories, how do we find the $K$ most influential road segments (seeds) that, if improved, would yield the greatest reduction in congestion across the entire network?

Problem Formulation

The road network is modeled as a directed graph $R = \langle V, E \rangle$, where $V$ is a set of vertices and $E$ is a set of directed edges representing road segments.

A directed road network graph illustrating vertices and edges.

The TBI problem is proven to be NP-hard, meaning it cannot be solved perfectly in a reasonable timeframe for large cities. This necessitates the development of clever approximation algorithms that can handle city-scale data.

Methodology

The researchers propose a two-phase framework to address the complexity of traffic dynamics:

1. Influence Acquisition

They develop a Traffic Spread Model that calculates the probability $p(e, e')$ of traffic "diffusing" from one segment $e$ to another $e'$ based on historical trajectory data. Unlike previous models that use arbitrary constants, this model uses real travel times and "residual ratios"—the amount of traffic that stays on a road versus moving on.

Traffic diffusion probabilities between edges in the sample network.

They also introduce a $\tau$-consecutive constraint, which ensures that a segment is only flagged as a bottleneck if its influence persists over a meaningful period, filtering out temporary traffic glitches.

2. Bottleneck Identification

To find the best $K$ segments, they propose two algorithms:

  • Best-First (BF): A greedy algorithm that iteratively picks the segment providing the maximum "marginal gain" in influence. It boasts a theoretical approximation ratio of $1 - 1/e$.
  • Sampling-based Greedy (SG): Designed for massive networks, SG uses a sampling technique based on "reverse influenced sets." It provides similar theoretical guarantees but is significantly faster for city-scale data.

Datasets and Evaluation

The study evaluates the framework using three major real-world taxi trajectory datasets:

  • Xi’an & Chengdu (Didi Chuxing GAIA): High-resolution data (2-4 second sampling) covering thousands of road edges.
  • Porto (Kaggle): A much larger dataset with over 100,000 road edges and 1.5 million trajectories.

Key Insights and Results

  • Volume $\neq$ Influence: High-volume roads, like major highways, are not always the most important bottlenecks. A smaller "cut edge" connecting different parts of a city might have a much higher influence on surrounding traffic than a massive, but isolated, highway segment.
  • Submodularity: The traffic influence function is "submodular," exhibiting diminishing returns. This mathematical property allows greedy algorithms to provide strong performance guarantees.
  • Effectiveness and Efficiency: The BF and SG algorithms consistently achieved higher "coverage ratios" (total influenced edges) compared to baselines like ranking by volume. On the Porto dataset, the SG algorithm was orders of magnitude faster than community-based methods.

Conclusion

By using trajectories to calculate diffusion probabilities, this model captures real driver behavior—like common shortcuts or lane-merging patterns—that simple map-based models miss. While the paper identifies where the problems are, future work aims to prescribe specific fixes and evolve the framework into a real-time traffic analysis prototype.

Summary updated

BibTeX
@article{luo2022let,
  author = {Hui Luo and Zhifeng Bao and Gao Cong and J. Shane Culpepper and Nguyen Lu Dang Khoa},
  title = {{Let Trajectories Speak Out the Traffic Bottlenecks}},
  journal = {ACM Trans. Intell. Syst. Technol.},
  year = {2022},
  url = {https://openreview.net/forum?id=PbjIcH1LjJ2},
}
Figure