Optimizing Traffic Flow Using Graph Theory How graph theory and optimization algorithms can improve transportation systems by reducing congestion and increasing efficiency.

Source abstract

This paper investigates the application of graph theory and mathematical optimization to urban transportation networks, aiming to quantify and mitigate urban traffic congestion. Road infrastructure is modeled as a directed, weighted graph 𝐺=(𝑉,𝐸), where link travel times are dynamically determined by flow volume through the Bureau of Public Roads (BPR) performance function. We compare two routing paradigms: User Equilibrium (UE), representing selfish route choice by individual drivers, and System Optimum (SO), representing global delay minimization. Using benchmark networks such as the Sioux Falls network alongside real-world municipal street data extracted via OpenStreetMap (OSMnx), we simulate pathfinding efficiency using Dijkstra's and A* algorithms and calculate network inefficiencies via the Price of Anarchy (PoA). Our findings indicate that selfish routing accounts for a 15% to 30% increase in total travel time across major metro areas, with the Price of Anarchy peaking at approximately 1.30 in dense network configurations. Furthermore, structural analysis demonstrates how topological features—such as betweenness centrality concentration—exacerbate bottlenecks, occasionally triggering counterintuitive effects like Braess's Paradox. We conclude that implementing socially-aware navigation algorithms that redistribute a small fraction of vehicular flow can recover the majority of system-wide efficiency losses without significantly burdening individual drivers.