Graph neural networks reduce urban roads for faster traffic routing optimization
GNN-Guided Network Reduction for Centralized Urban Traffic Routing
Machine Learning
Summary
Traffic routing in cities is very complex because many roads and vehicles make calculating best routes slow. The paper’s authors developed a way to use a special type of AI called graph neural networks to pick only the most important roads for each group of travelers. Then, an optimization tool finds the best routes on this smaller network much faster. Tests in four big cities showed this method gets very close to the best solution much quicker, helping move traffic more efficiently.
What this means in practice
- •For urban traffic planners: Speed up route optimization by focusing on key road segments to reduce city-wide traffic congestion more effectively.
- •For traffic management center teams: Implement faster centralized route assignment strategies that maintain near-optimal traffic flow in large urban networks under real-time constraints.
Authors
Nikolai Antonov, Lukáš Chrpa, Andrii Nyporko, Jan Hůla
Abstract
We consider the centralized traffic routing (CTR) problem, where a central planner assigns routes to origin-destination (OD) vehicle flows to minimize congestion-dependent segment cost. Prior work formulates CTR efficiently as a mixed-integer linear program (MILP), but scaling this formulation to the full road network is computationally prohibitive within an operational time budget. Bounded Routes and Smart Routes speed up optimization using precomputed reduced networks; however, these methods do not account for vehicle information within each OD flow. Motivated by this gap, we propose a learning-based urban network reduction approach. A dedicated graph neural network (GNN) first scores road segments for each OD flow using the road network and vehicle-flow information. Highly ranked segments are then incorporated into complete OD routes, and the original segment-flow MILP is solved on the resulting reduced road network. The GNN thus guides the reduction of the road network, while the solver enforces feasibility and determines the routing. Experiments on four real urban networks -- Prague-Dejvice, London, New York, and Sydney -- show that the proposed approach achieves the smallest relative objective difference to the $30$-second full-graph reference in every city under both traffic regimes. Averaged across cities, this difference is more than six times lower than that of the best competing method. Moreover, traffic simulation results show that the optimization gains of the proposed method lead to more efficient routing, with the highest aggregate arrival rate and a competitive trip duration per arrival percentage point.