GNN-Guided Network Reduction for Centralized Urban Traffic Routing

Nikolai Antonov; Lukáš Chrpa; Andrii Nyporko; Jan Hůla

cs.LGOct 27, 2026

GNN-Guided Network Reduction for Centralized Urban Traffic Routing

Authors: Nikolai Antonov, Lukáš Chrpa, Andrii Nyporko, Jan Hůla

Organizations: Czech Technical University in Prague, Czech Institute of Informatics, Robotics and Cybernetics, Jugoslávských partyzánů 1580/3, Prague, 160 00, Czech Republic · Czech Technical University in Prague, Faculty of Electrical Engineering, Technická 2, Prague, 166 27, Czech Republic

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.

Figures & tables

Variable	Domain	Description
$x_{r}^{i}$	$\{0,1,\dots,n^{i}\}$	Number of vehicles of flow $i$ assigned to segment $r$
$f_{a,b}^{i}$	$\mathbb{R}_{\geq 0}$	Number of vehicles of flow $i$ continuing from segment $a$ to segment $b$ through an allowed turn
$s_{r}$	$\mathbb{R}_{\geq 0}$	Load on segment $r$
$y_{r}$	$\mathbb{R}_{\geq 0}$	Cost contribution of segment $r$
$z_{r}^{k}$	$\{0,1\}$	Indicator that tier $k$ is active on segment $r$

Table 1: Decision variables of the CTR MILP.

Panel of Figure 1 — Figure 1: Fixed and episode-specific network reduction. Boxes show states, while arrow labels show operations. (a) The fixed procedure constructs the flow-specific segment sets $R_{i}^{\prime}$ independently of the current episode. (b) Our approach predicts per-flow segment scores and constructs these sets for the current episode. Both approaches use the same segment-flow MILP.

Panel of Figure 2 — Figure 2: GNN segment ranking model. The current CTR MILP instance is represented by variable, constraint, and objective nodes connected through six directed relation types. Node features combine MILP ( blue ), road network ( green ), and OD-flow ( orange ) information. Four GATv2 layers perform message passing (purple), after which a readout head assigns a raw score $q_{r}^{i}$ to each routing variable $x_{r}^{i}$ . These scores are ranked separately within each OD flow and passed to the network reduction procedure.

Node type	Features
Variable (77)	variable type, linear objective coefficient, and bounds; routing, network, and OD-flow features for $x_{r}^{i}$ ; turn context for $f_{a,b}^{i}$ ; segment features for $s_{r}$ , $y_{r}$ , and $z_{r}^{k}$ , with additional tier-specific features for $z_{r}^{k}$
Constraint (44)	constraint type, right-hand side, and sense; flow and OD context, segment and OD-flow features, congestion-tier information, and turn connectivity according to the constraint type
Objective (1)	a single bias feature

Table 2: Node features used in the GNN representation.

City	$\|V\|$	$\|R\|$	$\|T\|$	Length (km)
Dejvice	95	183	5	15.1
London	308	645	65	40.7
New York	212	453	9	51.8
Sydney	441	1058	20	106.4

Table 3: Topology of the four test cities.

Panel of Figure 3 — Figure 3: FG scalability. Solid: gap $\leq 1\%$ ; dashed: feasible solution; shading: selected $N_{F}$ .

Panel of Figure 4 — Figure 4: GNN validation ranking performance in the static (S) and increasing (I) regimes; bar labels show cumulative recall.

Mean relative objective difference to FG ref (%)
City	FG	GNN	LP	Random	SR	BR	SP
Static regime
Prague-Dejvice	1.14	1.12	142.00	4.52	40.34	23.85	422.96
London	1.68	0.54	3.85	1.17	309.25	201.56	545.60
New York	106.53	0.67	16.48	4.50	67.10	5.12	545.35
Sydney	31.06	0.24	118.94	6.34	43.51	11.51	341.89

Table 4: Optimization-level evaluation results.

Static regime
Method	Prague-Dejvice	London	New York	Sydney	All cities
FG	1.11/ 401.0	16.29 /47.1	2.37/589.6	17.45/43.8	5.98/ 130.4
GNN	1.17/407.6	15.83/48.9	2.44/585.2	17.89 / 43.6	6.02 /131.8
LP	1.21 /518.2	15.94/48.6	2.81 /571.3	12.24/85.5	5.27/177.0
Random	0.89/514.8	16.20/ 47.1	2.66/ 509.8	17.18/46.2	5.87/136.1
SR	0.45/691.9	10.63/99.8	1.75/987.4	15.36/54.4	4.40/216.2

Table 5: Microscopic simulation across rerouting shares. Cells report average arrival (%) / duration-to-arrival (s/pp); metric bests are bold.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 135 papers

Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networks
Mar 31, 2025Fangtong Zhou, Xiaorui Liu, Ruozhou Yu +1Graph Neural Networks Learning to Optimize
Department of Computer Science, North Carolina State University, Raleigh, NC, 27606, USA · School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ, 85287, USA
Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
Sep 30, 2026Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz +3Graph Neural Networks Approximation Algorithms
cortAIx Labs, Thales Deutschland, Ditzingen, Germany · Department of Mathematics/Computer Science, University of Osnabrück, Osnabrück, Germany
Neighbor-embedded Graph Neural Network-based Crowd Delivery Traffic Management in Smart City
Aug 23, 2026Kishu Gupta, Deepika Saxena, Ashutosh Kumar Singh +1Intelligent Transportation Systems Traffic Flow Estimation
Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, 80424, Taiwan · Department of Computer Science, VIZJA University, Warsaw, 01-043, Poland · Department of Computer Science and Engineering, University of Aizu, Aizuwakamatsu, 9650006, Fukushima Prefecture, Japan +1

Mar 31, 2025J/K move · Enter open · S save

Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networks

Fangtong Zhou, Xiaorui Liu, Ruozhou Yu, Guoliang Xue

Department of Computer Science, North Carolina State University, Raleigh, NC, 27606, USA · School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ, 85287, USA

Graph Neural Networks Learning to Optimize

Open paper AskPDF arXiv

Traffic Engineering (TE) in large-scale networks like cloud Wide Area Networks (WANs) and Low Earth Orbit (LEO) satellite constellations is a critical challenge. Although learning-based approaches have been proposed to address the scalability of traditional TE algorithms, their practical application is often hindered by a lack of generalization, high training overhead, and a failure to respect link capacities. This paper proposes TELGEN, a novel TE algorithm that learns to solve TE problems efficiently in large-scale network scenarios, while achieving superior generalizability across diverse network conditions. TELGEN is based on the novel idea of transforming the problem of "predicting the optimal TE solution" into "predicting the optimal TE algorithm", which enables TELGEN to learn and efficiently approximate the end-to-end solving process of classical optimal TE algorithms. The learned algorithm is agnostic to the exact underlying network topology or traffic patterns, and is able to very efficiently solve TE problems given arbitrary inputs and generalize well to unseen topologies and demands. We train and evaluate TELGEN with random and real-world topologies, with networks of up to 5000 nodes and 3.6x10^6 links in testing. TELGEN shows less than 3% optimality gap while ensuring feasibility in all testing scenarios, even when the test network has 2-20x more nodes than the largest training network. It also saves up to 84% TE solving time than traditional interior-point method, and reduces up to 79.6% training time per epoch than the state-of-the-art learning-based algorithm.

Abstract

Vehicle Routing

Explore similar work

Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networks

Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon

Neighbor-embedded Graph Neural Network-based Crowd Delivery Traffic Management in Smart City