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

Mar 31, 2025

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

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.

Fangtong Zhou, Xiaorui Liu, Ruozhou Yu +1

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

Ask PDF

Sep 30, 2026

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

Neural combinatorial optimization typically assumes a centralized solver that reads the whole instance. We study the opposite: combinatorial optimization under a hard information horizon, where every node commits to its share of a global solution seeing only its

k

-hop neighborhood, and those commitments must compose into a globally feasible solution. We formalize this as local set cover and instantiate it on weighted multipoint relay (MPR) selection, the NP-hard 2-hop covering problem of the Optimized Link State Routing Protocol version 2 (OLSRv2) routing protocol (RFC7181), whose horizon is imposed by the protocol, not chosen by the modeler. We prove two results. Any deterministic selector whose horizon is one hop short must either fail coverage or land a factor $Δ$ from optimal, and an $L$ -layer graph neural network (GNN) read out at the deciding node is exactly an $L$ -hop selector, so capacity cannot buy back radius. Conversely, at the horizon a \ac{GNN} of depth $O(Δ)$ reproduces the RFC7181 covering greedy, and at width

O(c_{\max}Δ)

its metric-aware weighted analogue, inheriting the

(1+\lnΔ_2)

-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches

\text{cost}/\text{opt}=1.030\pm0.001

against greedy's

1.138

, closing

79.1\%

of the gap at

100\%

coverage. Restricting the same learner to one hop, on identical instances with the same decoder and demonstrations, collapses it to

1.344

, far worse than greedy. Two transfer checks target real-world networks. OLSRv2's unmodified selection code matches our cardinality greedy on

200/200

unit-cost instances, and on

40{,}308

instances of real battalion mobility the frozen model closes

48\%

of the gap at full coverage. The information horizon, not the model capacity, is the most significant variable.

Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz +3

cortAIx Labs, Thales Deutschland, Ditzingen, Germany · Department of Mathematics/Computer Science, University of Osnabrück, Osnabrück, Germany

Graph Neural Networks Approximation Algorithms Neural Combinatorial Optimization

Ask PDF

Aug 23, 2026

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

The significant upsurge in vehicle traffic presents a considerable challenge in the pursuit of smart mobilization and transportation (SMT) worldwide. Current approaches primarily focus on vehicular traffic management through congestion prediction but fall short in addressing essential objectives such as traffic reduction and appropriate vehicle selection to alleviate congestion in smart cities (

SmCt

). To address these concerns, this work introduces a novel Neighbor-Embedded Graph Neural Network-based Crowd Delivery Traffic Management (NeCDM) Model, comprising two key components: the Traffic Congestion Prediction Unit (TCPu) and the Traffic Observation and Management Unit (TOMu). The TCPu utilizes Graph Neural Network (GNN) optimization to accurately predict traffic flow levels at various delivery stations within

SmCt

ecosystems. Additionally, the TOMu facilitates the intelligent selection of the most suitable delivery vehicles for fulfilling crowd delivery requests (

CDR

). This work emphasizes the potential of crowd delivery as a feasible solution for achieving SMT goals while adhering to smart city parameters (

\mathcal{SCP}

s), such as reduced carbon emissions, shorter travel times, and minimized travel distances. The proposed model achieves notable improvements in computational efficiency, including reductions of up to 4.03% in L1 loss (

£

), 16.66% in L2 loss (

£_{rmse}

), and 7.64% in computation time.

Kishu Gupta, Deepika Saxena, Ashutosh Kumar Singh +1

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

Intelligent Transportation Systems Traffic Flow Estimation Vehicle Routing

Ask PDF

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