A heuristic methodology to tackle the Braess Paradox detecting problem tailored for real road networks

Bagloee, Saeed Asadi; Ceder, Avishai; Tavana, Madjid; Bozic, Claire · 2013 · OpenAlex-citations

DOI: 10.1080/23249935.2013.787557

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the Braess Paradox Detection (BPD) problem, which seeks to identify specific subsets of roads in existing traffic networks whose closure would improve overall traffic flow. The Braess Paradox (BP) describes the counter-intuitive phenomenon where adding capacity to a network worsens congestion due to selfish user routing behaviors. While previous literature has focused on identifying individual "Braess-tainted" links, this study tackles the more complex challenge of finding optimal combinations of links for closure. The authors note that BPD is an NP-hard problem, making exact solutions computationally intractable for large, real-world networks. Consequently, the research aims to develop a heuristic methodology capable of handling large-scale networks where previous methods failed. The proposed methodology employs a two-phase heuristic approach based on a Genetic Algorithm (GA). Phase 1 identifies a set of likely Braess-tainted roads by testing the closure of individual links. Phase 2 utilizes a search algorithm to find the optimal subset of these tainted roads. This phase consists of two modules: the first generates an enriched pool of scenarios (chromosomes) through random generation and evaluation, while the second mates these chromosomes to breed better solutions. To ensure network viability, the methodology caps the extent of road closure to preserve connectivity. The authors demonstrate the efficacy of this approach using two case studies: the benchmark Hagstrom–Abrams network and a large-scale real-world network of Winnipeg, Canada. The results indicate that the heuristic methodology is effective for large networks. In the Winnipeg case study, the improvement in traffic flow achieved by closing the identified subset of roads was equivalent to the construction of a new bridge. The study confirms that while individual links may appear Braess-tainted, their combined closure does not always yield improvements, validating the necessity of the combinatorial approach. The methodology successfully identified subsets of roads whose removal reduced total system costs, demonstrating that BP is prevalent in real-world networks and can be mitigated through strategic capacity reduction rather than expansion. The significance of this work lies in providing a practical tool for traffic planners to manage congestion in existing networks. By offering a feasible solution to an NP-hard problem, the study shifts the focus from network expansion to network optimization through selective closure. The findings imply that traffic authorities can improve system performance by identifying and closing specific road combinations, thereby reducing the "price of anarchy" associated with selfish routing. This approach offers a cost-effective alternative to infrastructure expansion and highlights the importance of considering combinatorial effects in network design and management.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• perceptual countermeasures