Source-linked AI summary
GNN-Guided Network Reduction for Centralized Urban Traffic Routing
Nikolai Antonov, Lukáš Chrpa, Andrii Nyporko, Jan Hůla
TL;DR
Large centralized traffic-routing MILPs are difficult to solve on full road networks within short operational budgets, and fixed reductions do not use current flow information. This paper ranks segments per OD flow with a GNN, then solves the original MILP on a reduced network; it reports the smallest relative objective difference across cities and traffic regimes, while noting limits in how well its optimization model represents traffic dynamics.
Problem
Solving the CTR MILP becomes increasingly difficult as road networks and vehicle flows grow, while fixed route-based reductions do not account for current episode vehicle information.
Source: §1 · p. 2, §2.3 · p. 6Method
A GNN ranks road segments for each OD flow using network and current-flow information, and the solver optimizes the original segment-flow MILP on the resulting reduced network.
Source: §1 · p. 3, §6 · p. 32Results
The GNN achieves the smallest relative objective difference from the 30-second full-graph reference in every city and traffic regime, averaging 0.4–0.6% across cities.
Source: §6 · p. 33Takeaways & Limitations
In the considered simulation settings, optimization gains remain useful, but the results do not establish that every MILP-objective improvement improves traffic performance.
Source: §6 · p. 33The MILP models congestion through tiered segment costs, while SUMO also models signals, queues, vehicle interactions, lane changes, and rerouting over time.
Source: §6 · p. 33
Abstract
from arXiv · showhide
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.
1. Introduction
Centralized traffic routing must assign routes jointly, but solving the segment-flow MILP on large networks within operational time limits is difficult. The paper uses episode-specific GNN rankings to reduce the network before optimization, reporting the best objective comparison across cities and traffic regimes and strong simulation outcomes.
Motivation
- Full-network MILP solving becomes harder as networks and vehicle flows grow, while fixed reductions trade smaller models against retaining useful routing alternatives.The planner must compute joint routes within a short operational time budget.Source: §1 · p. 2
Contributions
- The reduction connects selected segments through complete OD paths and locally expands their union, reducing routing variables in the original segment-flow MILP.This produces an episode-specific reduced network for optimization.Source: §1 · p. 3
- A dedicated GNN ranks road segments separately for each OD flow using network and current-flow information, while the MILP solver enforces feasibility and determines final routes.The model learns segment orderings rather than predicting exact vehicle counts or final routes.Source: §1 · p. 3
- For each city and traffic regime, a single trained model generalizes to unseen scenarios with different numbers of OD flows.The model is trained separately for each city and traffic regime.Source: §1 · pp. 3–4
Results
- The GNN-guided reduction achieves the smallest mean relative objective difference among compared methods in every city and traffic regime.The evaluation compares solution quality against a 30-second full-network MILP reference.Source: §1 · pp. 3–4
- Under the considered simulation stress tests, the approach has the highest overall arrival rate across cities in both traffic regimes and competitive trip duration relative to arrival rate.Recovered routes are replayed in SUMO to assess whether optimization-level differences carry over to traffic outcomes.Source: §1 · pp. 3–4
2. Related Work
The related work situates centralized routing among decentralized and partially centralized approaches, then reviews static CTR formulations, network reduction, and learning-assisted optimization. It identifies episode-insensitive fixed reductions and feasibility concerns in direct learned routing as context for learning-guided MILP reduction.
2. Related Work
- The paper reviews centralized-routing formulations and solution approaches, road-network reduction, and learning-assisted routing and optimization.It distinguishes its focus on reducing a given segment-flow MILP from work introducing or extending CTR formulations.Source: §2 · p. 4, §2.2 · p. 6
2.1. Decentralized, partially centralized, and centralized routing
- Decentralized routing is generally less efficient than system-optimal routing, while centralized joint assignment targets system-wide cost but becomes computationally difficult as networks and traffic volumes grow.Partially centralized methods use information, incentives, or compliance-aware recommendations, with effectiveness depending on driver response.Source: §2.1 · p. 5
2.2. CTR formulations and static mixed-integer optimization
- Static segment-flow MILPs assign integer vehicle flows to segments and minimize congestion-dependent objectives, while dynamic traffic assignment models traffic evolution over time and is outside this paper’s scope.Related static formulations add practical route-length constraints or piecewise-linear approximations.Source: §2.2 · pp. 5–6
2.3. Road network reduction for mixed-integer CTR
- Bounded Routes and Smart Routes preprocess reduced networks, but their fixed episode-independent sets trade MILP size against preserving alternatives useful for current OD flows.Smart Routes clusters route segment sets and retains representative alternatives; stronger pruning has previously been associated with longer simulated trip durations.Source: §2.3 · p. 7
2.4. Learning-assisted optimization for CTR
- Learned routing can use current OD flows, but predicted routes may violate original constraints unless feasibility is enforced separately.Learning-assisted optimization instead uses models to guide the optimization process rather than directly predict final routing.Source: §2.4 · pp. 7–8
3. Problem formulation
The formulation models centralized routing as a static, episode-level segment-flow MILP with congestion-dependent costs and turn restrictions. It assigns aggregate OD flows to available segments, selects congestion tiers, and uses turn-flow variables to represent permitted transitions.
3.1. Network, OD flows, and congestion model
- The road network is a directed graph of junctions and road segments, with turn restrictions represented as allowed incoming-to-outgoing segment pairs at selected junctions.A segment aggregates lanes and parallel roadways connecting the same ordered pair of junctions.Source: §3.1 · pp. 8–9
- Each episode comprises OD groups of identical vehicles and is solved independently, with static segment costs and aggregate flows rather than individual vehicle trajectories.Each flow has an origin, destination, vehicle count, and available segment set.Source: §3.1 · p. 9
- Segment cost increases with load through a piecewise-linear function whose active tier is determined by segment load.The formulation has no hard segment-capacity limit; the final congestion tier extends without an upper load bound.Source: §3.1 · p. 9
3.2. MILP formulation
- The MILP uses routing variables for flow on available segments, segment load and cost variables, congestion-tier selectors, and turn-flow variables for allowed turns.Table 1 summarizes the decision variables of the CTR MILP.Source: §3.2 · pp. 9–10, Table 1 · p. 10
- The constraints conserve flow at nodes, prevent flow entering origins or leaving destinations, and define segment loads as the total routed vehicles.The episode vehicle total bounds segment load and informs the formulation’s big-M constants.Source: §3.2 · p. 10
- The MILP selects one congestion tier per segment and constrains its load to that tier’s bounds, using the selected tier to linearize segment cost.At an exact threshold, either adjacent tier is feasible; the lower-cost tier is selected because unit costs increase and segment cost is minimized.Source: §3.2 · pp. 10–11
- At restricted junctions, turn-flow constraints reproduce incoming and outgoing segment flows; integer turn assignments can be recovered by a maximum-flow procedure after solving.The formulation need not impose integrality on turn-flow variables, avoiding a potentially harder MILP.Source: §3.2 · p. 11
- Fixed reduction constructs flow-specific segment sets independently of the episode, whereas the proposed approach uses per-flow scores to construct episode-specific sets; both then use the same segment-flow MILP.The ranking-guided procedure connects selected segments through complete OD routes and locally expands their union.Source: Figure 1 · p. 12
4. Solution Methodology
The methodology restricts each flow’s segment-flow MILP to a flow-specific reduced segment set, obtained either from fixed route pools or episode-specific rankings. A GNN supplies segment rankings, while turn-aware route recovery converts solver flows into individual vehicle routes.
4.1. Fixed reduction methods
- Full graph retains all routing variables as the reference; Bounded Routes preserves enumerated alternatives, Smart Routes removes overlapping routes, and Shortest Path retains only one route per OD pair.The fixed reductions use the same segment sets across episodes and do not use current vehicle information.Source: §4.1 · pp. 13–14
4.2. Ranking-guided network reduction
- For each flow, ranked segments passing turn, simplicity, and detour checks are assembled into complete routes, locally expanded, pruned for OD reachability, then optimized by the original MILP.The shortest turn-restricted path is retained in the route pool regardless of rankings.Source: §4.2 · pp. 14, 16
4.3. GNN-based segment ranking
- A heterogeneous MILP graph with six directed relations and MILP, network, and episode-specific flow features feeds four GATv2 layers and a readout scoring routing variables.The GNN is trained using full-graph solutions, with segment usage determining the target ordering within each flow.Source: §4.3 · pp. 16–18, Figure 2 · p. 17
4.4. Route recovery
- At restricted junctions, maximum flow converts potentially fractional turn assignments to integer ones; DFS then assigns vehicles along positive-residual-flow routes and discards circulations.The maximum-flow construction uses integer capacities derived from segment-flow values, so it has an integer solution.Source: §4.4 · pp. 19–20
5. Experimental Evaluation
The evaluation tests scalability, learned ranking, optimization quality, and simulated traffic outcomes across four urban networks and two traffic regimes. GNN-guided reduction achieves the smallest relative objective difference to the 30-second full-graph reference in every city and regime, while also delivering the strongest overall simulation performance.
5.1. Experimental setup
- Experiments cover Prague-Dejvice, London, New York, and Sydney, with static and increasing traffic regimes and a 10-second operational solver budget.A separate 30-second FG run provides the optimization reference; the setup also compares fixed reductions and GNN, LP, and random ranking oracles.Source: §5.1 · pp. 20–22
5.2. Scalability of the MILP formulation
- FG scalability declines at network-dependent OD-flow counts; in Sydney, finding any feasible solution becomes almost as difficult as finding a high-quality one.The selected five-value NF ranges target cases where a 10-second run struggles but a 30-second run remains substantially better; these ranges are used in later experiments.Source: §5.2 · pp. 23, 25, Figure 3 · p. 24
5.3. GNN training results
- Validation pairwise accuracy remains above 92% across cities and regimes, while top-K recall varies by network and reaches 90.9–94.4% at K = 200.Prague-Dejvice exceeds 99.5% recall at K = 50; London reaches approximately 99.5% at K = 200, motivating city- and regime-specific prefix calibration.Source: §5.3 · pp. 26–27
5.4. Optimization-level evaluation
- GNN achieves the smallest average relative objective difference from FGref in all four cities and both traffic regimes, reducing the difference versus Random by 3.49 and 4.85 percentage points.The reductions apply to the static and increasing regimes, respectively; GNN also beats FGref in increasing-regime New York and Sydney.Source: §5.4 · pp. 27, 29, Table 4 · p. 28
5.5. Microscopic simulation evaluation
- The simulation uses high-load stress tests, and its outcomes are not estimates of normal city traffic performance or expected to match the MILP objective exactly.Simulation metrics depend on vehicle interactions, departure times, rerouting, queues, and other conditions not directly modeled by the tiered segment-cost objective.Source: §5.5 · p. 30
- GNN has the best arrival rate in both regimes and ranks first for R in the increasing regime and second in the static regime.In Sydney, GNN records arrival rates of 17.89% static and 18.04% increasing, with R values of 43.6 and 40.1 s/pp, respectively.Source: Table 5 · p. 31, §5.5 · pp. 31–32
6. Conclusion
The proposed method uses vehicle-aware, episode-specific network reduction to narrow the CTR MILP while leaving feasibility and final routing to the solver. It achieves the smallest objective difference from the full-graph reference across cities and traffic regimes, and its optimization gains remain useful in the considered simulations.
6. Conclusion
- A dedicated GNN ranks segments separately for each OD flow, and the MILP—not the GNN—ensures feasibility and determines final routing.Highly ranked segments form complete OD paths in a reduced network; local expansion adds neighboring segments.Source: §6 · p. 32
- The same model remains effective across five consecutive problem sizes and previously unseen scenarios within each city and traffic regime.Across eight trained models, validation accuracy ranges from 92.0% to 96.1%.Source: §6 · pp. 32–33
- GNN achieves the smallest relative objective difference from the 30-second full-graph reference in every city and traffic regime, averaging 0.4–0.6% across cities.Among methods using the proposed reduction procedure, GNN also outperforms Random and LP, while the procedure improves solution quality over fixed-reduction methods.Source: §6 · p. 33
- GNN obtains the highest average arrival rate in both traffic regimes in the simulation experiment.The optimization gains remain useful under the considered simulation settings, but do not establish that every MILP-objective improvement improves traffic performance.Source: §6 · p. 33
- The MILP captures only part of traffic dynamics because it uses tiered segment costs, while SUMO models signals, queues, vehicle interactions, lane changes, and rerouting over time.Future work could incorporate current traffic information and update rankings and routes as conditions change.Source: §6 · p. 33