Applicable Prevention Method of Braess Paradox in Urban Traffic Flow Guidance System

Zhaosheng Yang, Peng Gao, Mo Li, Nan ZhangInternational Journal of Computational Intelligence Systems 2011 · DOI

Abstract

Urban Traffic Flow Guidance Systems (UTFGS) are designed to optimize city travel but can inadvertently trigger the "Braess Paradox," where providing optimal route information leads to concentrated traffic and increased congestion. This paper proposes a constrained K-shortest paths algorithm that utilizes a dynamic restricted searching area to distribute traffic more effectively. By applying detour and overlap constraints, the system provides diverse route options, balancing network load. Simulation results using VISSIM demonstrate a 92% increase in optimization efficiency and a significant reduction in computational overhead, making it suitable for real-time urban management.

Introduction: The Challenge of the Braess Paradox

The primary goal of UTFGS is to alleviate urban congestion by directing drivers toward the most efficient routes. However, these systems often face the Braess Paradox: when a single "best" route is broadcast to all users, the resulting mass migration to that route creates a new bottleneck, potentially making overall travel times worse than if no guidance were provided.

Beyond this paradox, standard shortest-path algorithms like Dijkstra’s are often too computationally intensive for massive, real-time urban networks. To be effective, a guidance system must generate multiple, high-quality, and distinct routes almost instantaneously.

Proposed Methodology

The researchers developed a "Constrained K-shortest paths algorithm" designed to operate within a dynamic restricted searching area. This approach minimizes the search space while ensuring route diversity through three main innovations:

1. Dynamic Search Area Restriction

To reduce computational load, the algorithm limits its search to a geometric corridor between the origin and destination. It initially searches within a rectangle; if insufficient paths are found, it expands to a contour-rectangle of an ellipse. This targeted approach ignores thousands of irrelevant road segments, drastically speeding up processing.

2. Diversity and Quality Constraints

To prevent "behavior homoplasy"—where all drivers choose the same path—the algorithm applies two critical filters:

  • Detour Constraint: Ensures that the suggested paths are not excessively longer than the absolute shortest path.
  • Overlap Constraint: Limits the number of shared road segments between the $K$ paths to ensure they are geographically distinct.
Figure 3: Visualization of three distinct paths (K=3) generated between an origin and destination, demonstrating the diversity achieved through overlap constraints.

3. Implementation and Parameter Tuning

The system allows for real-time adjustment of these parameters via a user interface. By sharding traffic across multiple distinct routes, the system prevents the concentration of vehicles that leads to the Braess Paradox.

Figure 4: The initial set dialog box for the navigation software, showing parameters for K-paths, detour constraints, and overlap constraints.

Experimental Results

The algorithm was tested using VISSIM 5.1 microscopic simulation software on road networks from Changchun and Guangzhou, China.

  • Computational Efficiency: In the large-scale Guangzhou network, the restricted search area reduced CPU processing time from 15.01 seconds to just 1.06 seconds—an 89.6% improvement.
  • Network Performance: In a simulated incident, the total travel cost for the network was reduced from 35,903,950 seconds (under the Braess Paradox) to 24,397,420 seconds using the proposed algorithm. This represents a significant improvement in traffic dissipation.
  • Optimization Gain: The authors reported an overall path optimization efficiency increase of approximately 92%.

Conclusion

By combining geometric search restrictions with diversity-focused path selection, the proposed algorithm effectively mitigates the Braess Paradox while meeting the real-time demands of urban traffic management. Future work will focus on integrating individual route choice behavior models to better account for the psychological factors influencing human drivers.

Summary updated

Abstract

Urban Traffic Flow Guidance System (UTFGS) may cause the overreaction and concentration of travelers and lead to the phenomenon of Braess Paradox. The paper develops a constrained K-shortest paths algorithm within a dynamic restricted searching area in consideration of realistic road network spatial distribution features. Through the test with the microscopic transportation simulation tool VISSIM, the algorithm could not only decrease the searching scale but also efficiently balance the traffic flow in the net and avoid the phenomenon of Braess Paradox.
BibTeX
@article{yang2011applicable,
  author = {Zhaosheng Yang and Peng Gao and Mo Li and Nan Zhang},
  title = {{Applicable Prevention Method of Braess Paradox in Urban Traffic Flow Guidance System}},
  journal = {International Journal of Computational Intelligence Systems},
  year = {2011},
  doi = {10.2991/ijcis.2011.4.6.17},
}
Figure