RRNCO: Towards Real-World Routing with Neural Combinatorial Optimization
Authors: Jiwoo Son
Zhikai Zhao
Federico Berto
Chuanbo Hua
Zhiguang Cao
Changhyun Kwon
Jinkyoo Park
Venue: ICLR 2026 Poster (2026)
Keywords: Neural Combinatorial Optimization
Vehicle Routing Problem
Graph Learning
Sim-to-real
Primary area: applications to robotics, autonomy, planning
TL;DR: We propose RRNCO, a neural solver for vehicle routing that handles real-world asymmetric distances and durations and a new benchmark with data from 100 cities to close the sim-to-real gap.

Abstract: The practical deployment of Neural Combinatorial Optimization (NCO) for Vehicle Routing Problems (VRPs) is hindered by a critical sim-to-real gap. This gap stems not only from training on oversimplified Euclidean data but also from node-based architectures incapable of handling the node-and-edge-based features with correlated asymmetric cost matrices, such as those for real-world distance and duration. We introduce RRNCO, a novel architecture specifically designed to address these complexities. RRNCO's novelty lies in two key innovations. First, its Adaptive Node Embedding (ANE) efficiently fuses spatial coordinates with real-world distance features using a learned contextual gating mechanism. Second, its Neural Adaptive Bias (NAB) is the first mechanism to jointly model asymmetric distance, duration, and directional angles, enabling it to capture complex, realistic routing constraints. Moreover, we introduce a new  VRP benchmark grounded in real-world data crucial for bridging this sim-to-real gap,  featuring asymmetric distance and duration matrices from 100 diverse cities, enabling the training and validation of NCO solvers on tasks that are more representative of practical settings. Experiments demonstrate that RRNCO achieves state-of-the-art performance on this benchmark, significantly advancing the practical applicability of neural solvers for real-world logistics. Our code, dataset, and pretrained models are available at https://github.com/ai4co/real-routing-nco.

features with Published as a conference paper at ICLR 2026
RRNCO: TOWARDS REAL-WORDL ROUTING WITH
NEURAL COMBINATORIAL OPTIMIZATION
Jiwoo ;on'; Zhikai Zhao?; Federico Berto Chuanbo Hua?,
Zhiguang Cao", Changhyun Kwon Jinkyoo Park 1.2
Omelet
KAIST
Radical Numerics
SSingapree Management University
ABSTRACT
The practical deployment of Neural Combinatorial Optimization (NCO) for Vehi- cle Routing Problems (VRPs) is hindered by a critical sim-to-real gap. This gap stems not only from training on oversimplified Euclidean data but also from node- based architectures incapable of handling the wode-and-edge-beed correlated asymmetric cost matrices, such those for real-world distance and duration. We introduce RRNCO, a novel architecture specifically designed to ad- dress these complexities. RRNCO's 's novelty lies in two key innovations. First, its Adaptive Node Embedding (ANE) efficiently fuses spatial coordinates with real- world distance features using learned contextual gating mechanism. Second, its Neural Adaptive Bias (NAB) is the first mechanism to jointly model asymmetric distance, duration, and directional angles, enabling it to capture complex, realis- tic routing constraints. Morcover, we introduce a new VRP benchmark grounded in real-world data crucial for bridging this sim-to-real gap, featuring asymmet- ric distance and duration matrices from 100 diverse cities, enabling the training and validation of NCO solvers on tasks that are more representative of practical settings. Experiments demonstrate that RRNCO achieves state-of-the-art perfor- mance on this benchmark, significantly advancing the practical applicability neural solvers for real-world logistics. Our code, dataset, and pretrained models are available at https: htgg//gttttt gighhb........ com/ ai4co/ /eelrreallao caaal-rouut noo.
INTRODUCTION
Vehicle routing problems (VRPs) are combinatorial optimization (CO) problems that represent foun- dational challenges in logistics and supply chain management, directly impacting operations across diverse sectors, including last-mile delivery services, disaster response management, and urban mobility. These NP-hard optimization problems require determining optimal routes for fleet of vehicles while satisfying various operational constraints. While several traditional methods have been developed over decades (Laporte & Nobert, 1987; Vidal, 2022; Wouda et al., 2024; Perron & Furnon, 2023; Applegate et al., 2003; Wouda & Lan, 2023), these often face challenges in real-world applications. Their computational complexity makes them impractical for large-scale and real-time applications. Moreover, they often require careful parameter tuning, problem-specific adaptations, significant domain expertise, and lengthy development. With the global logistics market exceeding the 10 trillion USD mark in 2025 (Research and Markets, 2024), improvements in routing efficiency can yield substantial cost savings and environmental benefits.
Neural Combinatorial Optimization (NCO) has emerged as a promising paradigm for solving CO problems such as the VRP (Bengio et al., 2021; Wu el., 2024a). By automatically learning heuris- tics directly from data, i.c., by using Reinforcement Learning (RL), NCO approaches for VRPs can potentially overcome the limitations of traditional methods by providing efficient solutions without requiring extensive domain expertise and by providing more scalable solutions (Kool et al., 2019; Zhou al., 2023). Recent advances in NCO have demonstrated impressive results on synthetic VRP instances, suggesting the potential for learning-baser approaches to achieve significant impact in real-world logistics optimization won et al., 2020; Luo al., 2024; Ye et al., 2024b; Hottung et al., 2025).
"Equal contribution

---

Published as a conference paper at ICLR 2026
However, while real-world VRPs encompass various dynamic and operational complexities, the transition from synthetic to practical applications faces primary topological challenge.
Firstly, most existing NCO research primarily relies simplified synthetic datasets for both train- ing and testing that fail to capture the foundational asymmetries of real-world road networks, par- ticularly asymmetric travel times and distances arising from road networks with diverse conditions (Osaba, 2020; Thyssens et al., 2023). Hence, a comprehensive framework for real-world data gen- eration needed to bridge this gap. Secondly, most current NCO architectures are based on the bose- transformer paradigm (Vaswani et al., 2017) and, as such, are not designed to effectively and efficiently embed the rich edge features and structural information present in real-workd routing problems, limiting their practical applicability (Kwon et al., 2021). I). A new neural approach capable of effectively encoding information such as asymmetric durations and distances is thus needed to bridge the sim-to-real gap.
Our Real Routing NCO (RRNCO) bridges the critical topological gap between simplified NCO research and real-world routing applica- tions aa illustrated in Fig. 1-through archi- tectural innovations that specifically target the asymmetric nature of practical routing prob- lems while serving as an extensible foundation for complex environments. We make fun- damental contributions. First, on the model- ing side, introduce a novel neural architec- ture with two key technical innovations: (i) an Adaptive Node Embedding (ANE) that dy- namically fuses coordinates and distance in- formation via learned contextual gating and probability-wiighhedd sampling: and (ii) a Neu- ral Adaptive Bias (NAB), the first mechanism to jointly model asymmetric distance and duration matrices within deep routing framework, guid- ing our Adaptation Attention Free Module (AAFM). To validate our approach, we construct a com- prehensive benchmark dataset from 100 diverse cities, featuring real-worke world asymmetric distance and duration matrices from OpenStreetMap (OpenStreetMap contributors, 2025).
mee
Figure 1: [Left] Most NCO works consider simplified Euclidean settings. [Right] Our work models real-world instances where durations and travel times can asym- metric.
(1) A novel NCO architecture (RRNCO) with ANE and NAB to natively handle real-world routing asymmetries.
Our contributions:
(2) An extensive, open-source VRP dataset from 100 cities with asymmetric matrices. (3) State-of-the-art empirical results on realistic VRP instances. (4) Open- source code and data to foster reproducible research.
2 RELATED WORKS
Neural Combinatorial Optimization (NCO) Neural approaches to combinatorial optimization leam heuristics directly from data, reducing reliance on domain expertise (Bengio et al., 2021). Methods are typically classified as construction or improvement. Construction methods sequen- tially generate solutions, pioneered by Pointer Networks (Vinyals et al., 2015) and now led by Transformer-basee autoregressive models (Kool et al., 2019; Kwon et al., 2020) for their strong abil- ity to capture complex structures. Non-autoregressing variants predict edge- lige-probability heatmaps in single pass (Joshi et al., 2020), with later work enhancing performance via stronger models and search strategies (Ye et al., 2024a; Sun & Yang, 2024; Xia et al., 2024; Kim et al., 2025). Improve- ment methods iteratively refine an initial solution through learned operators or policies (Hottung & Tierney, 2019; Ma et al., 2023; Hottung et al., 2021; Son et al., 2023; Li et al., 2023; Chalumeau
et al., 2023; Kim et al., 2021; Ma et al., 2021: Ye et al., 2024b; Zheng et al., 2024). Our work targets autoregressive construction, striking effective balance between speed and solution quality for real-world logistics.
Vehicle Routing Problem (VRP) Datasets A significant gap exists between NCO research and real-world applicability, largely due to the datasets used for training and evaluation. For decades, the community has relied established benchmarks like TSPLIB (Reinelt, 1991) and CVRPLIB
2

---

Published as a conference paper at ICLR 2026
(Lima et al., 2014). While invaluable for standardization, these datasets are typically based on symmetric Euclidean distances, assuming travel costs are equal in both directions (dy = dzs). This simplification fails to capture the inherent asymmetry of real road networks caused by one-way streets, traffic patterns, and turn restrictions (Osaba, 2020). Some recent works have attempted to create more realistic datasets (Duan et al., 2020; Ali & Saleem, 2024), but they suffer from critical limitations for NCO research: they often rely on proprietary, commercial APIs, are static and cannot be generated online key requirement for data-hungry RL agents), can be slow to generate, and are not always publicly released. Furthermore, they often omit crucial information like travel durations, which can be decoupled from distance in real traffic. Our work directly addresses these gaps by providing a fast, open-source, and scalable data generation framework that produces asymmetric distance and duration matrices from real-worle city topologies.
NCO for VRPs The application of NCO VRPs has evolved from early adaptations of recurrent models (Nazari et al., 2018) to the now-dominant Transformer-basee (Kool et al., 2019; Kwon et al., 2020; Kim al., 2022; Luo al., 2023; Zhou et al., 2024b; Huang et al., 2025; Luo et al., 2025; Berto et al., 2025b). These models have demonstrated impressive performance but are fundamentally node-centric; their attention mechanisms operate on node em- beddings, making it non-trivial to incorporate rich structural information contained in edge features like a full distance matrix. This limitation a primary contributor to the sim-to-real gap. To address this, some works have explored encoding edge information. GCN-based approaches (Duan et al., 2020) and attention via row and column embeddings of MatNet (Kwon et al., 2021) introduced early ways to handle asymmetry, with GOAL (Drakulic et al., 2024) incorporating edge data with cross-attention. While promising, existing methods typically handle only single cost matrix (e.g.. distance) and fail to leverage the correlated modalities of real-world routing (distance, duration, geometry). Efficiently fusing multiple asymmetric edge features remains an open challenge. Our model, RRNCO, addresses this with Adaptive Node Embeddings (ANE) and a Neural Adaptive Bias (NAB) mechanism that learns a unified routing context from distance, duration, and angle.
pecoder-decoded architectures
3 PRELIMINARIES
3.1 VEHICLE ROUTING PROBLEMS
Vehicle Routing Problems (VRPs) are a class of combinatorial optimization problems that aim to find optimal routes for fleet of vehicles serving a set of customers by minimizing cost func- tion. The simplest variant, the Traveling Salesman Problem (TSP), involves finding minimum-cost Hamiltonian cycle complete graph
(V, E) with n = [V] locations. Real-world applica- tions typically extend this basic formulation with operational constraints such as vehicle capacity limits (CVRP) or time windows for service (VRPTW) (Vidal et al., 2014). These problems are characterized by their input structure, consisting of node and edge features. Node features typically include location coordinates and customer demands, while edge features capture the relationships between locations. In real-world settings, these relationships are represented by distance and dura- tion matrices, D E Baxn, where dij and liy denote the distance and travel time from location to j. respectively. Previous NCO approaches typically rely on Euclidean distances computed directly from location coordinates, avoiding the use of distance matrices entirely. While this simplifica- tion works for synthetic problems with symmetric distances (d, djt. tyy tzt), real-world in- stances are inherently asymmetric due to factors such as traffic patterns and road network constraints. This asymmetry, combined with the problem's combinatorial nature, presents unique challenges for learning- based approaches, particularly in effectively encoding and processing the rich structural information present in edge features.
3.2 SOLVING VRPS WITH GENERATIVE MODELS
VRPs can be solved as a sequential decision process, and deep generative models can be learned to efficiently do so (Wu et al., 2024b). Given problem instance æ containing both node features (such as coordinates, demands, and time windows) and edge features (distance and duration matrices D.T), construct solutions through autoregressive generation. Our model iteratively selects the next location to visit based on the current partial route until all locations are covered. This construc- tion process naturally aligns with how routes executed in practice and allows the model to main-
3

---

Published as a conference paper at ICLR 2026
tain feasibility constraints throughout generation. In this work, we consider the encoder-decoder
framework as Kool et al. (2019). Formally, let 8 = {0). fgg denote the combined parameters
of our encoder and decoder networks. We learn policy my that maps input instances solutions through:
= (x),
(Ia)
T
( [x) = II go, (a, a a1. h),
(Ib)
1=1
where h represents the learned latent problem embedding, is the location selected at step t, and at-1,-..2 d1; denotes the partial route constructed so far. The architecture choices for the encoding
process (Eq. (1a)) and decoding (Eq. (1b)) via and g. respectively, are paramount to ensure high
solution quality.
3.3 TRAINING VIA REINFORCEMENT LEARNING
We frame the learning problem in reinforcement learning (RL) context, which enables data-free optimization by automatically discovering heuristics. The policy parameters are optimized to maximize the expected reward:
max J(0) = (an--D-aom R((a, m));
where the problem distribution we sample and R(a, a)) the reward (i.e., the negative cost) of solution. Policy gradient methods can be employed to solve this problem, such REINFORCE with the variance-reducing POMO baseline (Kwon et al., 2020). Due to RL's exploratory, i.c. trial and error, nature, many samples required. Thus, efficient generation and sampling of problem instances æ is essential to ensure training efficiency.
REAL-WORLD ROUTING MODEL
Instances
Adaptive Node Embedding
Encoder
Decoder
FFN
Prob.
Mode:
AAFM
Coordinates
Matis
Companiility Sufftmae
Row
Row Distance Contect
Embeding
Mode
K.V
F+N
Food Forward
AARM
Col Emb
Q
Coll Emb
IDT
Distance Matrix
Col Inc.
Dist Matix Emb
Emboding
Cal
MHA
Node to node Angle
Distance &. Duration Matris
K
Altribute
Astributes
Embeding
Adaptive
Figure 2: Our proposed RRNCO model for real-world routing.
Our model addresses real-world routing challenges where conventional methods struggle with asym- metric attributes like travel times and distances. We introduce two key innovations: (1) Adaptive Node Embedding with probability-wcigheed distance sampling efficiently integrating spatial co- ordinates with asymmetric distances through learned contextual gating, avoiding full distance ma- trix processing while preserving asymmetric relationships, and (2) Neural Adaptive Bias (NAB)- the first learnable mechanism to jointly model asymmetric distance and duration matrices in deep routing architectures, replacing hand-crafted heuristics in AAFM (Zhou et al., 2024a) with data- driven contextual biases. The model uses an encoder-decoder architecture where the encoder builds comprehensive node representations and the decoder generates solutions sequentially, with our tributions focusing on enhancing the encoder's real-world routing capabilities while maintaining efficiency.
4

---

Published as a conference paper at ICLR 2026
4.1 ENCODER
4.1.1 ADAPTIVE NODE EMBEDDING
The Adaptive Node Embedding module synthesizes distance-related features with node character- istics to create comprehensive node representations. A key aspect of our approach effectively integrating two complementary spatial features: distance matrix information and coordinate-based relationships. For distance matrix information, we employ a selective sampling strategy that cap- tures the most relevant node relationships while maintaining computational efficiency. Given distance matrix D e R NNN,, we sample nodes for each node i according to probabilities inversely proportional their distances:
1/dey
Pij =
ΣØ=1 1/4sj
where dı represents the distance between nodes i and The sampled distances are then transformed into an embedding space through a learned linear projection:
fast
Linear( Linear(dssampeed (saampled)
(4)
Coordinate information is processed separately to capture geometric relationships between nodes. For each node, we first compute its spatial features based on raw coordinates. These features are then projected into the same embedding space through another learned linear transformation:
fooord Linear
To effectively combine these complementary spatial representations, we employ Contextual Gating mechanism:
h g @ fooord (1 g) @ faist
where @ is the Hadamard product and represents learned gating weights determined by multi- layer perceptron (MIP):
g == o oMLP fdiss))
This gating mechanism allows the model to adaptively weigh the importance of coordinate-base and distance-based features for each node, enabling more nuanced spatial representation. To han- dle asymmetric routing scenarios effectively, 2021) and generate dual embeddings for each node: row embeddings h" and column embeddings h These embeddings are then combined with other node characteristics (such demand time windows) through learned linear transformations to produce the combined node representations:
follow the approach introduced in (Kwon et al.,
h comb MLP((h:; fmode))
homb MLP((M;; foodel)
where foode represents additional node features such as demand or time windows, which are trans- formed by an additional linear layer. This dual embedding approach allows the RRNCO model to better capture and process asymmetric relationships in real-world routing scenarios.
4.1.2 NEURAL ADAPTIVE BIAS FOR AAFM
Having established comprehensive node representations through adaptive embedding approach, RRNCO employs an Adaptation Attention-Free Free Module (AAFM) based on Zhou et al. (2024a) to model complex inter-node relationships. The AAFM operates on the dual representations h h and hoomb to capture asymmetric routing patterns through our novel Neural Adaptive Bias (NAB) mechanism. The AAFM operation is defined as:
K,V (Q) exp(A) (exp(K) @ V) exp(A) exp(K)
(10)
he with learnable weight matrices Wº W WV. While Zhou et al. (2024a) defines the adaptation bias heuristically as a-- log(oo)-d (with learnable a, node count N. and distance dıy), we introduce Neural Adaptive Bias (NAB) that learns asymmetric relationships directly from data. NAB processes distance matrix D, angle matrix & with entries dig arctan2(y, Ji v.). and optionally duration matrix T, enabling joint
where Q Whe K Whe
5

---

Published as a conference paper at ICLR 2026
modeling of Pratial-temporal asymmetries inherent in real-world routing. Let Wp. We, Wa
R.
D emb ReLU WD
(11)
T emb R W
(12)
T cmb ReL,U(WT,,W;
(13)
We then apply contextual gating to fuse these heterogeneous information sources. When duration information is available, we employ a multi-channel gating mechanism with softmax normalization:
[Demb:
Pemb:
Temb)
WG
G = softmax
(14)
exp(r)
where DDmmb 4 embi T Tomo] E BxNNNx3 is the concatenation of all embeddings, Wa a E 3 is a learnable weight matrix, and is a learnable temperature parameter. The fused representation is computed as:
H = G @ emb + G2 C emb + G3 @ Temb
(15)
Finally, the adaptive bias matrix is obtained by projecting the fused embedding H to a scalar value:
A = Hw E BBNNN
(16)
where Wont E R is learnable weight vector. The resulting A matrix serves as a learned inductive bias that captures complex asymmetric relationships arising from the interplay between distances, directional angles, and travel durations. The Neural Adaptive Bias is then incorporated into the Adaptation Attention Free Module (AAFM). Specifically, we employ the operation defined in (10)
by replacing the generic matrix A with the adaptive matrix generated by NAB.
The Neural Adaptive Bias (NAB), applied through the Adaptation Attention Free Module (AAFM), yields final node representations hy and hf after I passes through AAFM. These representations result from RRNCO's encoding process, leveraging joint modeling of distance, angle, and duration to capture complex asymmetric patterns in real-world routing networks.
4.2 DECODER
4.2.1
DECODER ARCHITECTURE
The decoder architecture integrates key elements from ReLD (Huang al., 2025) and Mat- Net (Kwon et al., 2021) to autoregressively construct solutions using the dense node embeddings produced by the encoder. At each decoding step t, takes as input the row and column node em- beddings alongside a context vector that encapsulates the current partial solution state, such as the last visited node and dynamic attributes like remaining capacity. This context serves as the query in multi-head attention mechanism to aggregate information from the embeddings, followed by residual connections and a multi-layer perceptron to refine the query vector. The resulting query is then employed in compatibility layer to compute selection probabilities for feasible nodes, incor- porating a negative logarithmic distance heuristic to prioritize nearby options and enhance explo- ration efficiency. This design enables our model to dynamically adapt static embeddings evolving contexts, yielding strong performance across vehicle routing problems; for full technical details, including equations and implementation specifies, please refer to the Appendix A.
REAL-WORLD VRP DATASET
significant challenge in applying Neural Combinatorial Optimization (NCO) to real-world routing is the lack of realistic datasets. Most existing benchmarks rely on synthetic instances with symmet- ric, Euclidean distances, failing to capture the complexities actual road networks, such as one-way streets and traffic-dependent travel times, which lead to asymmetric distance and duration matrices. To bridge this gap, we introduce a new, large-scale dataset for real-world VRPs. We developed a comprehensive data generation pipeline that leverages the OpenStreetMap Routing Engine (OSRM) (OpenStreetMap contributors, 2025) to create detailed topological maps for 100 diverse cities world- wide. Each map includes location coordinates along with their corresponding asymmetric distance

---

Published as a conference paper at ICLR 2026
and duration matrices. Furthermore, designed an efficient online subsampling method to gen- erate a virtually unlimited number of VRP instances for training our reinforcement learning agent. This approach ensures that model is trained data that faithfully represents real-world rout- ing challenges. In addition to serving as a henchmark, the dataset provides a structured basis for evaluating NCO solvers under realistic conditions and helps narrow the simulation-to-e fering a useful resource for future research on practical logistics. Details of the city selection, data generation framework, and subsampling methodology are given Appendix
gap, of-
Develiad
City Map Solect
Counircte Monia Dara Gereration
ØSRN
Coa Detanct
Visti
LC:100C
Ditance Matte
Durstio Motre
St Schoopping VIP
Intanes
genertee.
Mars
VSP Iralanot
Figure 3: Overview of RRNCO real-world data generation and sampling framework. We generate dataset of real- world cities with coordinates and respective distance and duration matrices obtained OSRM. Then, we efficiently subsample instances as a set of coordinates and their matrices from the city map dataset with additional generated VRP features.
EXPERIMENTS
6.1
EXPERIMENTAL SETUP
Classical Baselines In the experiments, we compare three SOTA traditional optimization ap- proaches: LKH3 (Helsgaun, 2017): a heuristic algorithm with strong performance on (A)TSP prob- lems, VRP (Wouda et al., 2024): specialized solver for VRPs with comprehensive constraint handling capabilities; and Google OR-Tools (Perron Didier, 2024): a versatile optimization li- brary for CO problems.
Shariing-Based Methods We compare against SOTA NCO methods divided in two categories. 1) Node-only encoding learning methods: POMO (Kwon al., 2020), end-to-end multi-trajectory RL-baasd method based on attention mechanisms; MTPOMO (Liu et al., 2024), a multi-task variant of POMO; MVMoE (7hou al., 2024b), mixture-offexpeers variant of MTPOMO; RF (Berto et al., 2025b): an RL-based foundation model for VRPs; ELG (Gao et al., 2024), hybrid of local and global policies for routing problems; BQ-NCO (Drakulic al., 2023): decoder-only trans- former trained with supervised learning; LEHD (Luo et al., 2023): supervised learning-based heavy decoder model and AAFM (Zhou al., 2024a), introduced in the ICAM framework as an instance-conditionee attention-fre free alternative enabling instance conditioned adaptation. 2) Node and edge encoding learning methods: GCN (Duan et al., 2020): a graph convolutional network with encoding of edge information for routing; MatNet (K (Kwon et al., 2021): RL-based solver encoding edge features via matrices; ReLD-MTL and ReLD-MoEL (Huang et al., 2025), which incorporate identity mapping and feed-for worddfoo decoder refinements to significantly improve cross-size and cross- moos--robbemm gener- alization and GOAL (Drakulic et al., 2024): generalist agent trained via supervised learning for several CO problems, including routing problems.
Training Configuration We perform training runs under the same settings for fair comparison for model, MatNet for ATSP and ACVRP, and GCN for ACVRP. Node-only models do not

---

Published as a conference paper at ICLR 2026
Table 1: Performance comparison real-world routing tasks and distributions. We report costs and gaps calculated with respect keswnn solutions (+) from traditional solvers. Horizontal lines separate traditional solvers, node-only methods, node-and-ode addeee methods, and our RRNCO. Lower is better (U).
In-distribution
Out-of-distribution (city)
Out-of-distribution (cluster)
Task
Method
Cost
Gap (%)
Time
Cost
Gap (%)
Time
Cost
Gap
Time
LKH3
38.387
1.6h
38,903
1.6h
12.170
*
1.6h
OR-Tools
39.685
3.381
7h
40.165
3.244
7h
12.711
4.445
7h
POMO
51.512
34.192
10s
50.594
30.051
10s
30.051
146.926
10s
AISP
ELG
51.046
32.976
42s
50.133
28.866
42s
23.017
89.131
42s
BQ-NCO
55.933
45.708
25s
54.739
40.706
258
27.872
129.022
25s
LEHD
56.099
46.140
13s
54.811
40,891
13s
27.819
128.587
13s
MatNet
39.915
3,981
27s
40.548
4.228
27s
12.886
5,883
27s
GOAL
41.976
9.350
91s
42.590
9.477
91s
13.654
12,194
91s
AAFM
45.992
19.812
151s
46.588
19.755
151s
15.211
24.987
151s
RRNCO
39.078
1.799
23s
39.785
2.268
23s
12.444
2.250
23s
PyVRP OR-Tools
69.739
70.488
7h
22.553
7h
72.597
4.097
73.286
3.969
7h
23.576
4.538
7h
POMO
85.888
23.156
16s
85.771
21.682
168
34.179
51.549
168
МTPOMO
86.521
24.063
16s
86.446
22.640
16s
34.287
52.029
16s
MVMoB
86.248
23.672
22.164
22s
34.135
$1.356
22s
RF
86.289
23.731
86.261
22.377
168
34.273
51.967
168
ACVRP
ELG
85,951
23.247
67s
85.741
21.639
66s
34.027
50.873
67s
BQ-NCO
93.075
33,462
30s
92.467
31.181
30s
40.110
77.848
30s
LEHD
93.648
34.284
17s
93.195
32.214
17s
40.048
77.573
17s
ReLD-MTL
88,331
26.659
16s
88.037
24.896
16s
36,169
60,373
16s
Rel ReI.D-MoFI.
85.154
26.406
16s
87.764
24.509
16s
36.137
60.231
16s
GCN
90.546
29.836
17s
90.805
28.823
17s
34,417
$2.605
17s
MatNet
74.801
7.258
30s
75.722
7.425
30s
24.844
10.158
30s
GOAL
84,341
20.938
104s
84,097
19.307
104s
34.318
52,166
104s
AAFM
76.663
9.928
11s
77.811
10.389
11s
25.131
11,431
11s
RRNCO
72.145
3.450
26s
73.010
3.578
26s
23.282
3.231
26s
PyVRP
118.056
118.513
7h 39.253
7h
OR-Tools
119.681
1.377
120.147
1.379
7h
39.903
1.655
7h
ACVRPIW
POMO
132.883
12.559
18s
132,743
12.007
17s
50.503
28.661
18%
МTPOМO
133.135
12.773
132.921
12.158
18s
50.372
28.328
18s
MVMoE
132.871
12.549
132.700
11.971
23s
28.227
24s
RF
132.887
12.563
132.731
11,997
18s
50.422
28.455
18s
ReI.DMMIL.
132.722
12,423
132.856
12.102
18s
$1.680
31.659
18s
ReLD-MoEL
132.594
12.314
18s
132.621
11.904
18s
51.647
31.575
18s
GOAL
134.699
14.098
107s
135.001
13.912
107s
47.966
22.197
107s
RRNCO
122,466
3.736
52s
122.986
3.775
52s
40.937
4.290
52s
necessitate retraining since our datasets are already normalized in the [0, 1]2 coordinates ranges (with locations sampled uniformly), and we do not retrain supervised-leariin would necessitate labeled data. The model trained for about 24 hours on 4x NVIDIA A100 40GB GPUs, with all training settings and train, test dataset details provided in Appendix Section C. and Appendix Section B.4.
models since they
Testing Protocol The test data consists of in-distribution evaluation for 1) In-dist: new instances generated from the 80 cities seen during training, 2) OOD (city) over new city maps and 3) OOD (cluster) out-of-distribution generalization to new location distri- butions across maps. The test batch size is 32, and data augmentation factor of 8 is applied to all models except supervised learning-based ones, i.e., LEHD, BQ-NCO, and GOAL. All evaluations conducted an NVIDIA A6000 GPU paired with an Intel(R) Xeon(R) CPU @ 2.20GHz
generalization
'Code: https: //gi thu. com/at 4co/ real rout routing-nco
8

---

Published as a conference paper at ICLR 2026
In-dist
(city)
(cluster)
Gop 0%l
Gop (%6
Gap 0%)
our Coord
our Dist
our ANE
our AME hia
Courd
Ditt
our AME
NAB
our Courd
our bist
Our AME
ARE RAB
Figure 4: Study of our proposed model with different initial contexts: coordinates, distances, Adaptive Node Embedding (ANE), and Neural Adaptive Bias (NAB). ANE and NAB perform best, particularly in out-of- distribution (OOD) cases.
6.2
MAIN RESULTS
Table 1 shows the results between and the baseline models ATSP, ACVRP, and ACVRPTW tasks, with inference times in parentheses. The results clearly demonstrate that our method achieves sfate-of-the-art performance across all problem settings, consistently outperform- ing existing neural solvers in both solution quality and computational efficiency. Notably, unlike previous approaches that require separate models for different problem types, our method effec- tively handles all routing problems within a single unified framework. This key advantage highlights the model's adaptability and scalability across diverse problem instances while maintaining strong generalization for both in-distribution and out-of-distribution scenarios in real-world settings.
6.3 ANALYSES
Ablation study proposed components We perform ablation study proposed model components Fig. 4: initial contexts with coordinates, distances, and our Adaptive Node Em- bedding(ANE), well as the Neural Adaptive Bias (NAB). We find ANE and NAB perform the best, particularly in out-of-distributton (OOD) cases. Remarkably, in cluster distributions, the NAB shows a relative improvement greater than 15%.
Granular ablation on NAB inputs To further investigate the contribution of each input modality to the Neural Adaptive Bias (NAB), we conduct a granular ablation study on ACVRPTW in Table 2. Starting from the full model that jointly uses distance, duration, and angle matrices, performance: remove components. The results show that each modality contributes to the final removing duration increases the gap from 3.74% 3.93% (in-distribution), and further removing angle increases it to 4.06%. The performance degradation more pronounced in the OOD (cluster) setting, where the gap increases from 4.30% to 4. 4.84%, demonstrating that the joint modeling of all three features is essential for robust generalization.
progressively
Table 2: Granular ablation on NAB inputs for ACVRPTW. We progressively remove duration and angle from the full NAB model.
In-distribution
OOD (city)
OOD (cluster)
Model
Cost
Gap (%)
Cost
Gap (%)
Cost
Gap (%)
PyVRP
118.056
118.513
39,253
RRNCO Full (D +D+T+ +))
122.467
3.74
122.986
3.78
40,937
4.29
Duration (D ②))
122.693
3.93
123,249
4.00
41.077
4.65
Duration Angle (D only)
122.849
4.06
123.364
4.09
41.151
4.84
Importance of real-world data generators different data generators, including the ATSP from MatNet (Kwon et al., 2021), adding random
We study the effect training different models on

---

Published as a conference paper at ICLR 2026
Table 3: Comparison of routing solvers and their training data generators real-world data.
Method
Data Gen.
In-dist
OOD City
OOD Clust.
Cost
Gap%
Cost
Gap%
Cost
Gap%
LKH3
38.39
38.90
12.17
MatNet
ATSP
80.86
110.70
81 31.04
108.30
27.78
128.23
RRNCO
Noise
41.35
7.72
42.01
7.98
13.66
12.20
MatNet
Real
39.92
3.98
40.55
4.23
12.89
5.88
RRNCO
Real
39.08
1.80
39.79
2.27
12.44
2.25
noise break symmetries in distance matrices, and our proposed real-world generator when testing in the real world. Table demonstrates our proposed real-world data generation achieves remarkable improvements in both in-distribution and out-of-distribution settings.
Generalization to stochastic VRPs RRNCO demonstrates remarkable performance when ap- plied to real-world topologies that surpass prior works. We further evaluate the robustness of RRNCO and generalizability to settings, i.e., under stochastic and time-dependent traffic con- ditions and conduct experiments on the recently released Stochastic Multi-period Timeedependent VRP (SMTVRP) benchmark from SVRPBench (Heakl et al., 2025). We also benchmark against additional traditional baselines, including Nearest Neighbor + 2-opt (NN+2opt) (Laporte & Nobert, 1987: Potvin& & Rousseau, 1995) and Ant Colony Optimization (ACO) (Dorigo al., 2006).
As shown in Table 4, RRNCO achieves the lowest cost (601.03) while maintaining full feasibil- ity and zero time window violations. Notably, OR-Tools fails find feasible solutions for 75.8% of instances within the time limit, highlighting the practical advantage of neural solvers in time- constrained scenarios. These results demonstrate that RRNCO generalizes effectively more com- plex, time-dependent routing problems beyond the benchmarks used for training. For more details of the dataset, baselines, and training configurations, please refer to Appendix E.
Table 4: Performance comparison on SMTVRP benchmark. Feasibility indicates the proportion of instances with valid solutions. Lower cost better.
Method
Cost
Feasibility
Runtime
TW Violations
ACO
763.52
1.00
41.3s
OR-Tools
610.08
0.242
1000s
45.15
NN 2opt
969.96
1.00
10s
()
RF
602.20
1.00
0.05s
GOAL
1319.00
1.00
0.28s
0
RRNCO
601.03
1.00
0.20s
CONCLUSION
In this paper, we introduced RRNCO, novel Neural Combinatorial Optimization architecture bridging simplified benchmarks and real-world routing challenges. Our core contribution is model explicitly handling asymmetric and multi-modal travel costs through two key innovations: Adaptive Node Embedding (ANE) efficiently fusing coordinates with sampled distance features, and Neural Adaptive Bias (NAB) mechanism. This NAB represents the first approach to jointly model multiple distance,
asymmetric metrics distacs-dissance, duration, and directional angles real-world routing problems. To validate our model, we constructed a large-scale dataset with realistic routing data from 100 di- verse cities. This dataset provides a reproducible and diverse testbed that supports future research on robust and generalizable NCO solvers. On this challenging benchmark, RRNCO achieves state-of- the-art performance among NCO methods. By releasing our model and dataset, we aim accelerate progress in practical, deployable neural optimization solutions.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
To facilitate reproducibility of our results, we provide complete access to our implementation, in- cluding dataset generators and training configurations. The source code is available https: //github. com/a a 1/14////o real -rout ing-nnn.... We will additionally disclose the URL of generated data and model weights on HuggingFace. Detailed descriptions of model architectures, dataset creation, training procedures, and experimental setups are provided in the main paper and appendix.
REFERENCES
Hina Ali and Khalid Saleem. Generating large-scale real-world vehicle routing dataset with novel spatial data extraction tool. PLOS ONE, 196))e0304422, June 2024. ISSN 1932-6203. doi: 10. n0.1377/joummal..nnn.008.33
David Applegate, Robert Bixby, Václav Chvátal, and William Cook. Concorde TSP solver. http: / /www. . math. uwaterloo ca/tsp/ concorde html, 2003.
Andrius Barauskas, Agnundefined Brilingaituddffned, Linas Bukauskas, Vaida Čeikutundefined, Alminas Civilis. and Simonas Šaltenis. Test-data generation and integration for long- miittdieeance e- vehicle routing. Geoinformatica. 27(4):737-758, January 2023. ISSN 1384-6175, doi: 10.1007)
$10707-002-00488--y URL. https: /twi//oioo///// http://oooooor/o////////oo 1007 1 00000022-00000000000000000
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d d'horizon. European Journal of Operational Research, 290(2): 405 421, 2021.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Lin Xie, and Jinkyoo Park. RL4CO: an Extensive Reinforcement Learning for Combina- torial Optimization Benchmark. In Proceedings of the 31st ACM SIGKDD Conference on Knowl- edge Discovery and Data Mining, 2025a. URL https: / //g//tttuuu com/ ai 401//oo/r44c/
Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Juny- oung Park, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems. Transactions on Machine Learning Research, 2025b. ISSN 2835-8856. URL
https: wppp/eveeeeevvveeeeeeeeeeeee net forum? forumiid=QzGLoa0PP
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Tom Barrett. Combinatorial optimization with policy adaptation using latent space search. Advances in Neural Information Processing Systems, 36:7947-7955 2023.
Nitin Chopde and Mangesh Nichat. Landmark based shortest path detection by using a and haversine formula. International Journal of Innovative Research in Computer and Communica- tion Engineering, (22:299-302, 2013.
Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Ant colony optimization IEEE Computational Intelligence Magazine, 1(4):28-39, 2006. doi: 10. 10.1199/CC1.20063299999
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-nco:
Bisimulation quotienting for generalizable neural combinatorial optimization. arXiv preprint arXiv:2301.03313. 2023.
Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. Goal: A generalist combinatorial optimiza- tion agent learner. arXiv preprint arXiv:2406. /5079, 2024.
Lu Duan, Yang Zhan, Haoyuan Hu, Yu Gong, Jiangwen Wei, Xiaodong Zhang, and Yinghui Xu. Efficiently Solving the Practical Vehicle Routing Problem: A Novel Joint Learning Approach. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 3054-3063. 3063, Virtual Event CA USA, August 2020. ACM. ISBN 978-1-4888 1-4503- 7998-4. doi: 10. 1 144/1394486.3400333
11

---

Published as a conference paper at ICLR 2026
Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. IJCAI, 2024.
Aldy Gunawan, Graham Kendall, Barry McCollum, Hsin Vonn Seow, and Lai Soon Lee. Vehicle routing: Review of benchmark datasets. Journal of the Operational Research Society, 72:1794- 1807, 2021. URL https:// http:///aa..ssanssssssseeeeeeeee www.stttttcooool.........o orgg otg/ Cttpg//oopss:::2220 2333991636.
Ahmed Heakl, Yahia Salaheldin Shaaban, Martin Takac, Salem Lahlou, and Zangir Iklassov. Svrpbench: A realistic benchmark for stochastic vehicle routing problem. arXiv preprint arXiv:2505.21887, 2025.
Keld Helsgaun. An extension of the lin-kenighannhclssee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017.
André Hottung and Kevin Tiemny. Neural large neighborhood search for the capacitated vehicle routing problem. arXiv preprint arXiv: 19111991111 1.09539, 2019.
André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106.05 10t.:22006.0116, 2021.
André Hottung, Paula Wong-Chung, and Kevin Tiemney Neural deconstruction search for vehicle routing problems. arXiv preprint wrXiv:2501.037/11 2025.
Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin XU. Rethinking light decoder-based solvers for vehicle routing problems. In The Thirteenth International Conference Learning Represen- tations, 2025. URL https:/ /ppporeeeeeeeeeeeeeeeeeeeeeeeeee n forum? werpummmd=pppwwypaaa
Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learn- ing the travelling salesperson problem requires rethinking generalization. arXiv preprint arXiv:2006.0705: 2020.
Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve NP-hard routing problems. Advances in Neural Information Processing Systems, 34:10418-10430 2021.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:1936-1949,
2022.
Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jiwoo Son, Jinkyoo Park, and Yoshua Bengio. Ant colony sampling with GFlownets for combinatorial optimization. In The 28th International Con- ference on Artificial Intelligence and Statistics, 2025. URL httpt:ttttpteeeeeeeeeee wpw.neview..ee.eeooooeeee/o.ee.e / Gorum?id=KLJSAgTTI
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! Inter- national Conference on Learning Representations, 2019.
Yeong- -De Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188 21198, 2020.
Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Ma- trix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138-5144 2021.
Gilbert Laporte and Yves Nobert. Exact algorithms for the vehicle routing problem. In North- Holland mathematics studies, volume 132, pp. 147-184. Elsevier, 1987.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. Advances Neural Information Processing Systems, 36:50020-50040. 2023.
Ivan Lima, Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Anand Subramanian, and Thibaut Vidal. CVRPLIB capacitated vehicle routing problem library. http://vrp. ga gos. inf, www.ppu..brro...o 2014.
12

---

Published as a conference paper at ICLR 2026
Fei Liu, Xi Lin, Qingfu Zhang, Xialiang Tong, and Mingxuan Yuan. Multi-task learning for routing problem with cross posss-problem zero-shot generalization. arXiv preprint arXiv:2402.16891, 2024.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36:8845-8864, 2023.
Fu Luo, Xi Lin, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Self-improved learning for scalable neural combinatorial optimization. arXiv preprini arXiv:2403.19561 2024,
Fu Luo, Xi Lin, Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehicle routing problems. In The Thir- teenth International Conference Learning Representations, 2025.
Dennis Luxen and Christian Vetter. Real-time routing with openstreetmap data. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS '11, pp. 513-516, New York, NY, USA, 2011. ACM. ISBN 978- 178-1-4503-1031- URL http: doi. acm. org/o0.g///..ooo..o
4. doi: 10. 0001145/2093973..204400 2094062.
Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song. Le Zhang, Zhenghua Chen, and Jing Tang. Learning iteratively solve routing problems with dual-aspect collaborative transformer. Ad- vances in Neural Information Processing Systems, 34:1 1111119991100 2021.
Yining Ma. Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible gions of routing problems with flexible neural k-opt. Advances in Neural Information Processing Systems, 01449555-49577 2023.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
OpenStreetMap contributors.
Openstreetmap database [data set].
https://www.
openstreetmap. org, 2025. Accessed: 2025-02-06.
Eneko Osaba. Benchmark dataset for the Asymmetric and Clustered Vehicle Routing Problem with Simultaneous Pickup and Deliveries, Variable Costs and Forbidden Paths. Data in Brief, 29: 105142, January 2020. ISSN 2352-3409. doi: 10. 10.1016/j.dib.2200100111 105142.
Laurent Perron and Frédéric Didier. CP-SAT, 2024. URL http::: UtL.ttpps://aeveeoppsss.ooo com/ opt immiiaiiiinnn
htcp/cp_solveee
Laurent Perron and Vincent Furnon. OR-Tools Google, 2023.
Jean-Y Potvin and Jean-Mare Rousseau. An exchange heuristic for routing problems with time windows. Journal of the Operational Research Society, 46(12):1433-1444 1446, 1995.
Ao Qu and Cathy Wu. Revisiting the correlation between simulated and field-observed conflicts using large-scale traffic reconstruction. Accident Analysis & Prevention, 210:107808, 2025.
Gerhard Reinelt. TSPLIB a traveling salesman problem library. INFORMS on Computing, 3844 1991. doi: 10.1287/jjoc.34.3366 URL https::/ppubsnnl/////
informs.
org//di/10. 1287 joo........ 3..4 4.76.
Research and Markets. Size of the global logistics industry from 2018 to 2023, with forecasts until
2028 (in trillion dollars). https: /www statista com/ statis iisiiicas /943517// logistin cicicsiii Andustry-glooall-e
2024. Accessed: January 22, 2025. The forecast is based on 2023 market size of approximately $9.41 trillion and CAGR of 5.6%, which implics an estimated global industry value of roughly $10.5 trillion in 2025.
Jiwoo Son, Minsu Kim, Hyeonah Kim, and Jinkyoo Park. Meta-sage: scale meta- meta-learning scheduled adaptation with guided exploration for mitigating scale shift on combinatorial optimization. In International Conference Machine Learning, pp. 32210. PMLR, 2023.
13

---

Published as a conference paper at ICLR 2026
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimiza- tion. Advances in Neural Information Processing Systems, 36, 2024.
Daniela Thyssens, Tim Dernedde, Jonas K Falkner, and Lars Schmidt-Thieme Routing arena: A benchmark suite for neural routing solvers. arXiv preprint arXiv:2310.04144 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neigh- borhood. Computers & Operations Research, 140: 105643, 2022.
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, and Christian Prins. A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Re- search, 234(3):658-4 673765666666666 2014. ISSN 0377-2217. doi: https://doi.org// 1tgg/10.1111 1tt6//066....... ejor 20100091104455.. 09.045.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. Advances in neural informa- lion processing systems, 28, 2015.
Fahui Wang and Yanqing Xu. Estimating o-d travel time matrix by google maps api: implementa- tion, advantages, and implications. Annals of GIS, 17(4):199-20 2011.
Niels A Wouda and Leon Lan. Alns: A python implementation of the adaptive large neighbourhood search metaheuristic. Journal of Open Source Software, 1885),0, 2023.
Niels Wouda, Leon Lan, and Wouter Kool. PyVRP: high-performance VRP solver package.
INFORMS Journal on Computing, 2024.
Xuan Wu, Di Wang. Lijie Wen, Yubin Xiao, Chunguo Wu, Yuesong Wu, Chaoyu Yu, Douglas L Maskell, and You Zhou. Neural combinatorial optimization algorithms for solving vehicle routing problems: A comprehensive survey with perspectives. arXiv preprint arXiv:2406.0m 404400 2024a.
Xuan Wu, Di Wang, Lijie Wen, Yubin Xiao, Chunguo Wu, Yuesong Wu, Chaoyu Yu, Douglas L. Maskell, and You Zhou. Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives, October 2024b.
Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems. In Proceedings of the 41st International Conference on Machine Learning, pp. 54178-54190, 2024.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. DeepACO: Neural-enhanced ant systems for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024a.
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. AAAI 2024, 2024b.
Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. Ude: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. arXiv preprint MXX1::2407.00312.2 2024.
Changliang Zhou, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang- Instance-conditionnd adaptation for large-scale generalization of neural combinatorial optimiza- tion. arXiv preprint arXiv:2405.0720 01906 2024a.
Jianan Zhou, Yaoxin Wu, Zhiguang Cao, Wen Song, and Jie Zhang. Collaboration! Towards robust neural methods for vehicle routing problems. 2023.
Jianan Zhou, Zhiguang Cao. Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. MV- MoE: Multi-task vehicle routing solver with mixture-of- exxeeess.... International Conference on Machine Learning, 2024b.
14

---

Published as a conference paper at ICLR 2026
APPENDIX
A DETAILED MODEL DECODER ARCHITECTURE
The decoder architecture combines key elements from the ReLD and MatNet effectively process the dense node embeddings generated by the encoder and construct solutions for vehicle routing problems. At each decoding step t, the decoder takes as imput the row and column node embeddings (hG. h&) produced by the encoder and a context vector hG. The composition of hh adapts to the problem type. For VRP variants (ACVRP and ACVRPTW), ) the context relies on the last visited node and the dynamic state. In contrast, for ATSP, we additionally include the embedding of the first node ag to explicitly anchor the tour's origin. Formally, the context vector is defined as:
Wao 1 M D4J E 2d for ATSP, W Dt Rda+dar
h.
(17)
for ACVRP and ACVRPTW.
where D' E: Rd represents the dynamic features derived from the state sf. The specific contents of D are tailored to the constraints of each problem variant: for ACVRP, 1) consists of the current load; for ACVRPTW, includes both the current load and the current time. In the case of ATSP, which is unconstrained by capacity or time windows, no dynamic features are utilized (i.e., D' = 0). To aggregate information from the node embeddings, the decoder applies a multi-head attention (MHA) mechanism, using the context vector he as the query and H' E RlF'(xd, as the key and value:
h/ = MHA(he, We n.)
(18)
The ReLD model introduces a direct influence of context by adding a residual connection between the context vector he and the refined query vector h/:
M. No + IDT(
(19)
where IDT(.) is an identity mapping function that reshapes the context vector to match the di- mension of the query vector, allowing context-aware information to be directly embedded into the representation. To further enhance the decoder performance, an MLP with residual connections is incorporated to introduce non-linearity into the computation of the final query vector 9e:
ge = h'. + MLP(hh).
(20)
The MLP consists of two linear transformations with a ReLU activation function, transforming the decoder into a transformer block with single query that can model complex relationships and adapt the embeddings based on the context. Finally, the probability of selecting node E F* is
calculated by applying compatibility layer with negative logarithmic distance heuristic score:
(go) W
ps Softmax
(C- ttanh
log(dist;)
(21)
Vdn
where C' is a clipping hyperparameter, d, is the embedding dimension, and dist, denotes the distance between node and the last selected node o.-1. This heuristic guides the model to prioritize nearby nodes during the solution construction process. The combination of ReLD's architectural modifi- cations and MatNet's decoding mechanism with our rich, Icarned encoding enables the RRNCO model to effectively leverage static node embeddings while dynamically adapting to the current context, leading to improved performance various vehicle routing problems.
B REAL-WORLD VRP DATASET GENERATION
Existing methodologies often require integrating massive datasets (e.g., traffic simulators and multi-source spatial data) - for instance, Barauskas et al. (2023) rely on simplistic synthetic bench- marks, which either resource- resource-intensive or lack real-world complexity (Gunawan et al., 2021).
To address these limitations, we design a three-step pipeline to create a diverse and realistic vehicle routing dataset aimed at training and testing NCO models. First, we select cities worldwide based on
15

---

Published as a conference paper at ICLR 2026
multi-dimensional urban descriptors (morphology, traffic flow regimes, land-use mix). Second, develop a framework using the Open Source Routing Machine (OSRM) (Luxen & Vetter, 2011) to create city maps with topological data, generating both precise location coordinates and their corre- sponding distance and duration matrices between each other. Finally, we efficiently subsample these topologies to generate diverse VRP instances by adding and time windows, thus preserving the inherent spatial relationships while enabling the rapid genera- tion of instances with varying operational constraints, leveraging the precomputed distance/duration matrices from the base maps. The whole pipeline is illustrated in Fig. 3.
features such demands
B.1 CITY MAP SELECTION
We select a list of 100 cities distributed actoss six continents, with 25 in Asia, 21 in Europe, 15 each in North America and South America, 14 in Africa, and 10 in Occania. The selection empha- sizes urban diversity through multiple dimensions, including population scale (50 large cities > IM inhabitants, 30 medium cities 100K-1M, and 20 small cities <100K), infrastructure development stages, and urban planning approaches. Cities feature various layouts, from grid-based systems like Manhattan radial patterns like Paris and organic developments like Fez, representing different ge- ographic and climatic contexts from coastal to mountain locations. We prioritized cities with reliable data availability while balancing between globally recognized metropolitan areas and lesser-knowe urban centers, providing comprehensive foundation for evaluating vehicle routing algorithms un- der diverse real-world conditions. Moreover, by including cities from developing regions, we aim to advance transportation optimization research that could benefit underprivileged areas and contribute to their socioeconomic development.
B.2 TOPOLOGICAL DATA GENERATION FRAMEWORK
In the second stage, we generate base maps that capture real urban complexities. This topological data generation is composed itself of three key components: geographic boundary information, point sampling from road networks, and travel information computation.
Geographic boundary information We establish standardized 9 km2 areas (3x3 km) centered on each target city's municipal coordinates, ensuring the same spatial coverage across different urban environments. Given that the same physical distance corresponds to different longitudinal spans different latitudes due the Earth's spherical geometry, we need a precise distance calculation method: thus, the spatial boundaries are computed using the Haversine spherical distance formula- tion (Chopde Nichat, 2013):
d 2R aresin (Van? (Ar)
AA)) 2
441) 2
+ cos( cos (22) sin?
(22)
where d is the distance between two points along the great circle, R is Earth's radius (approximately 6,371 kilometers), Φ1 and Φ2 are the latitudes of point and point in radians, Aó 62 di represents the difference in latitudes, and AA X2 A represents the difference in longitudes. This enables precise spatial boundary calculations and standardized cross-city comparisons while maintaining consistent analysis areas across different geographic locations.
Point sampling from road networks Our RRNCO framework interfaces with OpenStreetMap (OpenStreetMap contributors, 2025) for point sampling. More specifically, we extract both road networks and water features within defined boundaries using graph_from.bbor and Employing boolean indexing, the sampling process implements several filtering mechanisms to filter the DataFrame and ensure point quality: we exclude bridges, tunnels, and highways to focus accessible street-level locations and create buffer zones around water fea- tures to prevent sampling from (close to) inaccessible areas. Points are then generated through a weighted random sampling approach, where road segments weighted by their length to ensure uniform spatial distribution.
16

---

Published as a conference paper at ICLR 2026
Travel information computation The travel information computation component leverages lo- cally hosted Open Source Routing Machine (OSRM) server (Luxen & Vetter, 2011) to calculate real travel distances and durations between sampled points, ensuring full reproducibility of results. Through the efficient get. table e function in our router implementation via the OSRM table ser- vice", we can process complete 1000x 1000 origin-destination matrix within 18 seconds, making it highly scalable for urban-scale analyses. In contrast to commercial API-based approaches that require more than 20 seconds for 350x350 matrices (Ali & Salcem, 2024), our open-source local OSRM implementation achieves the same computations in approximately 5 seconds. Additionally, it enables the rapid generation of multiple instances from small datasets with negligible computa- tional cost per iteration epoch. The RRNCO framework finally processes this routing data through a normalization strategy that addresses both unreachable destinations and abnormal travel times. This step captures real-world routing complexities, including one-way streets, turn restrictions, and varying road conditions, resulting in asymmetric distance and duration matrices that reflect actual urban travel patterns. All computations are performed locally', allowing for consistent results and independent verification of the analysis pipeline.
B.3 VRP INSTANCE SUBSAMPLING
From the large-scale city base maps, we generate diverse VRP instances by subsampling a set of locations along with their corresponding distance and duration matrices, allowing us generate an effectively unlimited number of instances while preserving the underlying structure. The subsam- pling process follows another three-step procedure:
1. Index Selection: Given a city dataset containing Nix locations, we define a subset size Nuub representing the number of locations to be sampled for the VRP instance. We generate an in- dex vector s = ($1, $2...., where each S; is drawn from selections. 2. Matrix Subsampling: Using S, we extract submatrices from the precomputed dis- tance matrix D NN Nua and duration matrix T E IR Nu Noe, forming instance-specific ma- trices sunh- = D(s, s] E NRN x Not and Taub T(s, E R x Mus, preserving spatial rela- tionships among selected locations. 3. Feature Generation: Each VRP can have different fea- tures. For example, in Asymmetric Capacitated VRP (ACVRP) we can generate a demand vector d E R N such that d = (d1, dg....,dN..)! where each d, represents the demand at location 8t. Similarly, we can extend to ACVRPTW (time windows) represented as W e R Naxx2 where (w (u (o.)) ), defining the valid service interval for each node.
No ensuring unique
W {(w )..nd)..... .,....
Unlike previous methods that generate static datasets offline (Duan et al., 2020; Ali & Saleem, 2024), RRNCO generation framework dynamically generates instances the fly in few milliseconds, reducing disk memory consumption while maintaining high diversity. Fig. illustrates the overall process, showing how city map is subsampled using an index vector create VRP instances with distance and duration matrices enriched with node-specific features such as demands and time windows. Our approach allows us to generate a (arbitrarily) large number of problem instances from a relatively small set of base topology maps totaling around 1.5GB, in contrast to previous works that required hundreds of gigabytes of data to produce just a few thousand instances.
B.4 ADDITIONAL DATA INFORMATION
We present a comprehensive urban mobility dataset encompassing 100 cities across diverse geo- graphical regions worldwide. For each city, we collected 1000 sampling points distributed through- out the same size urban area. The dataset includes the precise geographical coordinates (latitude and longitude) for each sampling point. Additionally, we computed and stored complete distance and travel time matrices between all pairs of points within each city, resulting in 1000x1000 matrices per city. The cities in our dataset exhibit significant variety in their characteristics, including population size (ranging from small to large), urban layout patterns (such as grid, organic, mixed, and historical layouts), and distinct geographic features (coastal, mountain, river, valley, etc.). The dataset covers multiple regions including Asia, Oceania, Americas, Europe, and Africa. This diversity in urban
P Phtpps: http://rojjjocoooooo osw.ectttoorrm.o.mmmoo org/ docs///c////e/ /vv 24 /pppp/pp//////pp i / /ttabl e- service
'Our framework can also be extended to include real-time commercial map API integrations and powerful traffic forecasting to obtain better-informed routing (Wang& & Xu, 2011; Qu & Wu, 2025), which we leave as future works.
17

---

Published as a conference paper at ICLR 2026
environments enables comprehensive analysis of mobility patterns across different urban contexts and geographical settings. Table on the following page provides information about our topology dataset choices.
Table 5: Comprehensive City Details
City
Populatio:
Layout
Geographic
Region
Split
Features
Addis Ababa Alexandria
Large Large Large
Organic Mixed Canal grid
Highland
East Africa
Train
Coastal
North Africa
Train
Amsterdam
River
Western
Train
Europe
Almaty Asunción
Large Medium
Grid Grid
Mountain
Central Asia
Train
River
South
Test
America
Athens
Large
Mixed
Historical
Southern
Train
Europe
Auckland Baku
Large Large
Harbor layout
Isthmus Coastal
Oceania
Train
Mixed
Western
Train
Asia
Bangkok
Large
River layout
River
Southeast
Train
Asia
Barcelona
Large
Grid & historic
Coastal
Southern
Train
Europe
Beijing Bergen
Large
Ring layout
Plains
East Asia
Train
Small
Fjord
Coastal mountain
Northern
Train
Europe
Brisbane
Large
River grid Grid
River River
Oceania
Train
Buenos Aires
Large
South
Train
America
Bukhara Cape Town
Small Large
Medieval Mixed colonial Colonial
Historical
Central Asia
Test
Coastal&mountain
Southern
Train
Africa
Cartagena
Medium
Coastal
South
Train
America
Casablanca
Large
Mixed
Coastal
North Africa
Train
colonial Grid
Chengdu Colombo
Large
Basin
East Asia
Train
Medium
Colonial grid Grid
Coastal
South Asia
Train
Chicago
Large
Lake
North
Test
America
Christchurch Copenhagen
Medium Large
Grid Mixed
Coastal plain
Oceania
Train
Coastal
Northern
Train
Europe
Curitiba
Large
Grid
Highland
South
Train
America
Cusco
Medium
Historie mixed
Mountain
South
Test
America
Daejeon
Large
Grid
Valley
East Asia
Train
Dakar
Medium
Peninsula grid
Coastal
West Africa
Train
Dar es Salaam
Large
Coastal grid Grid
Coastal
East Africa
Train
Denver
Large
Mountain
North
Train
America
Dhaka
Large Large
Organic Linear modern
River Coastal& desert
South Asia
Train
Dubai
Western
Train
Asia
Continued on next page
18

---

Published as a conference paper at ICLR 2026
Table 5 Continued from previous page
City
Populatio:
Layout
Geographie Features
Region
Split
Dublin
Large
Georgian grid
Coastal
Northern
Train
Europe
Dubrovnik
Small
Medieval walled Historic mixed
Coastal
Southern
Train
Europe
Edinburgh
Medium
Hills
Northern
Train
Europe
Fez
Medium
Medieval organic Valley grid
Historical
North Africa
Test
Guatemala City
Large
Valley
Central America
Train
Hanoi
Large
Mixed
River
Southeast
Train
Asia
Havana Helsinki
Large Large
Colonial Grid
Coastal
Caribbean
Train
Peninsula
Northern
Train
Europe
Hobart
Small
Mountain
Harbor
Occania
Test
harbor
Hong Kong Istanbul
Large Large
Vertical
Harbor Strait
East Asia
Train
Mixed
Western
Train
Asia
Kigali Kinshasa
Medium Large
Hill organic
Highland River
East Africa
Train
Organic
Central
Train
Africa
Kuala Lumpur
Large
Modern mixed
Valley
Southeast
Test
Asia
Kyoto La Paz
Large
Historical grid Valley organic
Valley Mountain
East Asia
Train
Large
South
Train
America
Lagos Lima
Large
Organic Mixed grid
Coastal
West Africa
Train
Large
Coastal desert
South
Train
America
London
Large
Radial organic
River
Northern
Test
Europe
Los Angeles
Large
Grid sprawl
Coastal basin
North
Train
America
Luanda
Large
Mixed
Coastal
Southern
Train
Africa
Mandalay
Large
Grid
River
Southeast
Train
Asia
Marrakech Medellín
Medium Large
Medina Valley grid
Desert edge
North Africa
Train
Mountain
South
Train
America
Melbourne Mexico City
Large Large
Grid Mixed
River Valley
Oceania
Train
North
Test
America
Montevideo
Large
Grid
Coastal
South
Train
America
Montreal
Large
Mixed
Island
North
Train
America
Moscow
Large
Ring layout
River
Eastern
Train
Europe
Mumbai Nairobi
Large Large
Linear coastal
Coastal
South Asia
Test
Mixed
Highland
East Africa
Train
Continued next page
19

---

Published as a conference paper at ICLR 2026
Table 5 Continued from previous page
City
Populatio:
Layout
Geographic Features
Region
Split
New Orleans
Medium
Colonial
River delta
North
Train
America
New York City
Large
Grid
Coastal
North
Train
America
Nouméa
Small
Peninsula
Coastal
Occania
Test
Osaka
Large
Grid
Harbor
East Asia
Test
Panama City
Large
Coastal
Coastal
Central
Train
modern
America
Paris
Large
Radial
River
Western
Train
Europe
Perth
Large
Coastal sprawl
Coastal
Oceania
Test
Port Moresby
Medium
Harbor sprawl
Coastal hills
Oceania
Train
Porto
Medium
Medieval
River mouth
Southern
Train
organic
Europe
Prague
Large
Historic grid
River
Central
Train
Europe
Quebec City
Medium
Historic walled
River
North
Test
America
Quito
Large
Linear valley
Highland
South
Test
America
Reykjavik
Small
Modern grid
Coastal
Northern
Test
Europe
Rio de Janeiro
Large
Coastal organic Historical
Mountain& coastal Seven hills
South
Train
America
Rome
Large
Southern
Test
organic
Europe
Salvador
Large
Mixed historic
Coastal
South
Train
America
Salzburg
Small
Medieval core
River
Central
Train
Europe
San Francisco
Large
Hill grid
Peninsula
North
Train
America
San Juan
Medium Large
Mixed historic
Coastal Valley
Caribbean
Test
Santiago
Grid
South
Train
America
São Paulo
Large
Sprawl
Highland
South
Train
America
Seoul Shanghai
Large Large Large
Mixed Modern mixed
River
East Asia
Train
River
East Asia
Train
Singapore
Planned
Island
Southeast
Train
Asia
Stockholm
Large
Archipelago
Island
Northern
Train
Europe
Sydney
Large
Harbor
Harbor
Oceania
Train
organic
Taipei
Large
Grid
Basin
East Asia
Train
Thimphu
Small
Valley organic
Mountain
South Asia
Train
Tokyo
Large
Mixed
Harbor
East Asia
Test
Toronto
Large
Grid
Lake
North
Train
America
Ulaanbaatar Valparaíso
Large Medium
Grid Hill organic
Valley
East Asia
Train
Coastal hills
South
Train
America
Continued next page
20

---

Published as a conference paper at ICLR 2026
Table 5 Continued from previous page
City
Populatio:
Layout
Geographic Features
Region
Split
Vancouver
Large
Grid
Peninsula
North
Train
America
Vienna
Large
Ring layout
River
Central
Train
Europe
Vientiane
Medium
Mixed
River
Southeast
Train
Asia
Wellington Windhoek
Medium Small
Harbor basin Grid
Coastal hills Highland
Oceania
Train
Southern
Test
Africa
Yogyakarta
Medium
Traditional
Cultural center
Southeast
Train
Asia
C ADDITIONAL EXPERIMENTAL DETAILS
C.1 HYPERPARAMETER DETAILS
Table shows the hyperparameters we employ for RRNCO. The configuration can be changed through yaml files as outlined in RL4CO (Berto et al., 2025a), which we employ as the base frame- work for our codebase.
Table Hyperparameters for RRNCO.
Hyperparameter
Value
Optimizer
Adam
Learning Rate
4 10-4
LR Decay Schedule
0.1 at epochs 180, 195
Batch Size
256
Instances per Epoch
100,000
Embedding Dimension
128
Feedforward Dimension
512
AAFM Layers
12
Clipping C
10
C.2 TESTING DATASET
For each dataset of the main experiments Section 6.2, subsampling described in Sec- tion B.3 and sample 1, 1,280 instances for each test set. Whole test sets and seeds are provided in the shared code for reproducibiliity
C.3 BASELINES DETAILS
All evaluations are conducted on an NVIDIA A6000 GPU paired with an Intel(R) Xeon(R) CPU @ 2.GOHH For neural methods, we employ the provided models and code in the original repositories to ensure fairness and reproducibilty.
We evaluate all traditional solvers on single CPU core sequentially. To reflect a realistic deployment scenario, we do not perform instance-specific hyperparameter tuning, instead re- lying on the robust default configurations provided by each library. For LKH-3 (Helsgaun, 2017), we utilize the standard parameter set from the official distribution (e.g., PATCHING.C- PATCHING for VRPs), imposing a TIME_LING (Wouda al., 2024), employ the default Hybrid Genetic Search (HGS) parameters specifically nb elite=4 and generatin inn s size=40 with a 20-second time limit via MaxRunt ime. Sim- ilarly, for Google OR-Tools (Perron & Didier, 2024), configure the routing model the
of seconds per instance. For PyVRP
21

---

Published as a conference paper at ICLR 2026
GUIDED LOCAL.SEARCH metaheuristic initialized with PATH-CHEAPEST ARC, restricted 20-second budget. This protocol, consistent with Liu et al. (2024), results total evaluation time of approximately 7 hours for the test set (1,280 instances).
D USE OF LARGE LANGUAGE MODELS
Large language models were employed solely as general-purpose writing assistants. Their use was restricted to refining phrasing, improving clarity, and conrecting grammar in draft versions of the manuscript. All research ideas, methodologies, analyses, results, and interpretations were conceived, executed, and validated exclusively by the authors. Any text generated with the assistance of LLMs was thoroughly reviewed, edited, and integrated by the authors to ensure accuracy, correctness, and compliance with academic standards.
E ADDITIONAL MATERIAL ON STOCHASTIC BENCHMARKS
We further evaluate RRNCO on routing scenarios with mnrryig travel conditions. Specifically, benchmark the Stochastic Multi-period Time-dependent VRP (SMTVRP), which incorporates realistic traffic dynamics following the simulation protocol of SVRPBench (Heakl et al., 2025).
E. BENCHMARK SETUP
Dynamic Travel Time Model Real-world travel times exhibit significant temporal variation due congestion patterns, stochastic delays, and unexpected incidents. We model the travel time from node a to b departing at time as:
T(a, b, Thase (a. b) T conngestion (a, b, + Tincidem (t),
(23)
where (a, b) D(a, b)/V represents the free-flow travel time based on Euclidean distance D(a, b) and average speed V. The congestion component captures systematic daily patterns:
Taungestion (a, b, b,a, R(t).
(24)
with Baa,b b, () encoding deterministic congestion and R(t) introducing stochastic variability.
The congestion factor combines temporal and spatial dependencies:
B(a, b,t) = a
B+T Σ
Mt:: Up: op)
(1- ---e- e(aa-//
(25)
(am
Fas(DD)
Fam (t)
where G(t: ()) denotes Gaussian kernel. The bimodal temporal structure with peaks Mam and μpm = 17 reflects typical morning and evening rush hours. The distance factor captures the empirical observation that longer trips have higher congestion exposure.
To model traffic variability, R(t) follows a log-normal distribution with time-dependent parameters:
R(t) (ogN) (R(())
(26)
where both (t) and (())) increase during peak hours to reflect heightened uncertainty. Incident-induced delays are modeled as:
Tincident (1) (incident at 1 Aincident;
(27)
where incident occurrences follow time- iatmme-ioooogencouss Poisson process with elevated rates during nighttime hours (Hiighh = 21), and delay durations Aiciddent ~ (0.5, 2.0) hours align with industry clearance statistics.
22

---

Published as a conference paper at ICLR 2026
Time Window Generation Customer availability windows sampled reflect realistic delivery scenarios. We distinguish between two customer types with distinct temporal preferences:
Tetees
~ 0.5 (Jaam a + 0.5 N (Hmm- pm
(28)
sturt
for residential customers with morning (Nam 480 min) and evening (44pm 1140 min) availability peaks, and
T
NV (Htiii biz);
(29)
for commercial customers centered on business hours (Jbbi 780 min). Window durations pled uniformly within problem-specffee bounds. Complete parameter specifications follow SVRP- Bench (Heakl al., 2025).
E.2 BASELINE CONFIGURATIONS
We evaluate set of baseline methods on the stochastic multi-period time-dependent VRP (SMTVRP) benchmark to ensure rigorous and fair comparisons. All methods are configured fol- lowing standard practices SVRPßench and prior VRP literature, with adjustments only when necessary to accommodate time-dependent travel information.
ACO (Ant Colony Optimization) We adopt a conventional parameterization commonly used in the SVRP literature. To balance solution quality and computational efficiency in dynamic envi- ronments, we set the number of ants to 50 and the maximum number of iterations to 100, The reltted parameters temporal update SMTVRP, heuristic costs are recomputed while pheromone trails are preserved maintain stability across time periods.
fixed to 1.0, B = 2.0, and evaporation rate 0.5. At each
OR-Tools We use the guided local search (GLS) implementation included in SVRPBench with a strict time limit of 1000 seconds per instance. This extended budget allows the solver explore large neighborhoods under dynamic updates. Following each change in the time-dependent duration matrix, OR- TRoTooll is restarted from the most recent feasible solution when possible, but no custom tuning beyond the default GLS configuration is introduced.
NN + 2-opt accordance with the SVRPBench protocol, a Nearest Neighbor (NN) heuristic is first used to construct initial solution, followed by 2-opt local improvement phase. The search terminates upon convergence or after reaching a maximum runtime of seconds per instance. Under dynamic conditions, NN 2-opt is rerun every update step preserve consistency with the updated travel-time information.
We evaluate GOAL using its official pre-trained checkpoint trained CVRPTW in- stances. No additional training or adaptation is performed. For each temporal update, GOAL re- evaluates its autoregressive decoding process under the current duration matrix, thereby testing its zero-shot generalization capacity to dynamic inputs.
GOAL
RouteFinder We initialize RouteFinder from its official pre-trained model and apply Efficient Active Learning (EAL) for 20 epochs to adapt the policy to the SMTVRP distributions. After EAL adaptation, inference proceeds closed-loop manner: at each step, the updated travel-time matrix processed, and actions are generated based on the current state of the dynamic environment.
E.3 MULTI-SNAPSHOT NAB FOR STOCHASTIC ROUTING
To extend RRNCO to robustly handle time-dependent and stochastic traffic variations, we intro- duce a Multi- Snatii-t variant of the Neural Adaptive Bias (NAB). While the standard NAB fuses single duration matrix, real-world traffic is highly dynamic and uncertain. To address this, integrate a dynamics-infomee traffic simulation directly into the encoder pipeline and extend the NAB architecture to process multiple temporal "snapshots" of traffic conditions simultaneously.
23

---

Published as a conference paper at ICLR 2026
E.3.1 DYNAMICS- DIMMICS-INFORRDD INPUT GENERATION
To approximate the stochastic nature of real-world travel times, we employ the dynamics-informm traffic modeling framework proposed in SVRPBench (Heakl et al., 2025). Instead of single static duration matrix, the model takes as input a set of K distinct duration snapshots (T.,..., Tx In our experiments, we set K = 3 to represent distinct traffic regimes (e.g., morning peak, noon, evening peak).
These snapshots are generated using Gaussian kernels centered at learnable "time anchors" to model congestion peaks, combined with stochastic noise injection. Specifically, for a snapshot k. the du- ration 13 is derived by modulating the base travel time with congestion factor drawn from time-dependent Gaussian distribution, multiplicative noise sampled from a LogNormal distribution to simulate flow variability, and sparse additive noise modeled via Poisson process to account for random incidents (accidents). This ensures the model receives a global, "look-ahead" view of potential traffic states and their associated uncertainties.
E.3.2 MULTI-SNAPPHOT GATING MECHANISM
We extend the Neural Adaptive Bias (NAB) module to aggregate these heterogeneous temporal views. The Multi- Snalti- NAB employs unified gating network that dynamically weighs the importance of the static spatial structure against the variable traffic conditions.
First, we project the static Distance matrix D, the Relative Angle matrix p, and each of the K dynamic Duration snapshots into shared high-dimensional embedding space:
D emb ReL.U(DW,, >)
(30)
c cmb ReLU(@W, +) W
(31)
T( ReLU(T, WT) vk (K.
(32)
To fuse these K 2 feature maps, compute set of scalar importance weights via a learned gating network. Let Egonent = [Demhi Pemb; ((U) T(K) denote the concatenation of embeddings.
We compute the gating weights g E TR2+ via a softmax function:
Eccocat WG exp(T)
g = softmax
(33)
where We is a learnable weight matrix and 7 is the temperature parameter. The final fused repre- sentation H fused is computed probability-weighted sum of the static and dynamic features:
K
4k+2 C ((())
H fused = I1 O Demb + 92 O T
emb
cmb
(34)
Similar to the standard NAB, this fused representation is projected to a scalar bias matrix A = Huseed Wout- This bias A modulates the attention scores in the Adaptation Attention Free Module (AAFM), guiding the solver to avoid routes that are consistently congested across the simulated snapshots or leverage time windows where traffic is predicted to be lighter.
E.4 TRAINING DETAILS
RRNCO (NAB) The standard RRNCO model equipped with the Neural Adaptive Bias (NAB) is trained for 100 epochs on static instances sampled from the real-world generator introduced in the main paper. Each epoch consists of 100,000 training instances, with a batch size of 256 and the Adam optimizer with learning rate of x 10-4, The learning rate is decayed following the schedule described in Table of the appendix. No fine-tuning is performed on the SMTVRP benchmark; instead, the model is directly evaluated in dynamic closed-loop setting.
RRNCO (Multi-Snapshot NAB) As detailed in Section E.3, this variant integrates temporal vari- ability by augmenting the Neural Adaptive Bias (NAB) module with a dynamics dynamicc-informed traffic simulator and temporal gating mechanism designed statically fuse multiple duration snapshots.
24

---

Published as a conference paper at ICLR 2026
In experiments, the model receives K temporal duration snapshots training time, responding to short-horizon predictions of traffic fluctuations. The model is trained for 100 epochs under the same reinforeement learning setup as the base RRNCO. During dynamic evaluation SMTVRP, the NAB module processes and fuses the K snapshots once during the initial encoding step. This process enables the resultant node representations embed global context of potential traffic variations, allowing the autoregressive decoder to anticipate near-future congestion patterns without requiring dynamic re-encoding at every decision step.
Inference Protocol Both RRNCO variants operate autoregressively in a closed-loop dynamic en- vironment. After each routing action, the updated time-dependent duration matrix provided by the SMTVRP simulator. The model recomputes its route continuation based on this updated infor- mation. A decoding augmentation factor of 8 is applied during inference to reduce variance and enhance route stability across dynamic updates.
E.5 RESULTS FOR MULTI-SNAPSHOT NAB
Table 7 demonstrates that RRNCO with Multi-Snapshng NAB achieves state-of-the-art performance with a cost of 594.19, 19, surpassing both the standard NAB (601 (601.03) and RouteFinder (602.20), This improvement confirms that fusing multiple temporal snapshots allows the model to better antici- pate traffic stochasticity. On the other hand, OR-Tools fails to find feasible solutions for 75.8% of instances despite 1000s budget. RRNCO maintains 100% feasibility and zero time window vio- lations, offering superior robustness and speed (0.20s) with virtually no additional inference latency compared to the standard model.
Table 7: Performance comparison on SMTVRP benchmark. Feasibility indicates the proportion of instances with valid solutions. Lower cost better.
Method
Cost
Feasibility
Runtime
TW Violations
ACO
763.52
1.00
41.3s
OR-Tools
610.08
0.242
1000s
45.15
NN + 2opt
969.96
1.00
10s
0
RF
602.20
1.00
0.05s
0
GOAL
1319.00 .00
1.00
0.28s
0
RRNCO (NAB)
601.03
1.00
0.20s
0
RRNCO (Multi-Snapsiie NAB)
594.19
1.00
0.20s
0
25


Reviews:
[{"review_id": "7ASMyzNyVv", "reviewer": "Reviewer_jJZH", "summary": "This paper proposes RRNCO, a neural combinatorial optimization architecture aimed to handle the asymmetry in vehicle routing problems. The contributions are twofold: (1) the Adaptive Node Embedding (ANE), which integrates spatial coordinates and asymmetric distance information through a contextual gating mechanism, and (2) the Neural Adaptive Bias (NAB), which jointly models distance, duration, and directional angle features. The authors also construct a new benchmark dataset with asymmetric real-world routing data from OpenStreetMap. Experiments on ATSP, ACVRP, and ACVRPTW demonstrate that RRNCO outperforms prior neural and classical solvers.", "questions": "1. Are there any theoretical analysis about of RRNCO (e.g., learnability, convergence, or generalization bound)?\n2. Is it possible to evaluate the robustness of RRNCO with respect to the time-dependent or stochastic variations of traffic conditions?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Clear motivation and relevance: the paper addresses a significant practical limitation of current NCO research: the reliance on symmetric, synthetic datasets. The focus on the sim-to-real gap is well-motivated and meaningful for practical deployment.\n2. Valuable benchmark contribution: the creation of an asymmetric VRP dataset derived from 100 OpenStreetMap cities represents a substantial and reusable resource for future research. It enhances reproducibility and encourages broader progress in realistic NCO studies.", "weaknesses": "1. Limited theoretical novelty: both ANE and NAB are constructed from existing attention and gating mechanisms. While effective, they represent architectural refinements rather than fundamentally new theoretical concepts.\n2. Insufficient evaluation for real-world robustness: the sim-to-real gap also arises from dynamic traffic conditions that alter travel times in real operations. The proposed model does not evaluate robustness under such time-dependent or stochastic variations. When congestion occurs after route generation, the model would likely suffer from the same limitations as prior works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pfoM791y4P", "reviewer": "Reviewer_yCJJ", "summary": "This paper addresses the critical sim-to-real gap for Neural Combinatorial Optimization (NCO) in Vehicle Routing Problems (VRPs), which stems from oversimplified symmetric data and inadequate node-centric architectures. The authors make a dual contribution: 1)  introducing an Adaptive Node Embedding (ANE) and a Neural Adaptive Bias (NAB) to jointly model real-world asymmetric distance, duration, and angles, and 2) a new, open-source VRP benchmark with asymmetric data from 100 real-world cities. Experiments show RRNCO achieves state-of-the-art performance among NCO solvers on this more realistic benchmark.", "questions": "1. How is the \"angle matrix\" $\\Phi$, a key input to the NAB (Section 4.1.2), defined and computed?\n\n2. For the classical solver runtimes (LKH3, PyVRP) in Table 1, what was the CPU configuration? Did they utilize multi-core parallel processing, and if so, how many cores were used?\n\n3. Figure 2 is ambiguous. Please clarify the encoder architecture: (1) Is my understanding correct that ANE is a one-time initial embedding step, not part of the attention stack? If so, I suggest revising Figure 2, Figure 2 ambiguously depicts ANE as part of the encoder stack and also omits the multi-layer stacking logic. (2) Why does the encoder diagram omit the Feed-Forward Network (FFN), while the decoder includes one? Does the encoder not require an FFN?\n\n4. In Figure 4, when the NAB is removed, does the model revert to the original heuristic bias, or does it use a different attention mechanism entirely, such as a standard Multi-Head Attention (MHA) block?\n\nReferences:\n\n[1] Instance-conditioned adaptation for large-scale generalization of neural combinatorial optimization. arXiv preprint arXiv:2405.01906, 2024.\n\n[2] Rethinking Light Decoder-based Solvers for Vehicle Routing Problems. ICLR, 2025.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides an open-source benchmark dataset. This is a major service to the NCO community, enabling the training and validation of NCO solvers on tasks that are more representative of practical settings.\n\n2. The Adaptive Node Embedding (ANE) and Neural Adaptive Bias (NAB)  are effective for fusing multiple asymmetric edge features.\n\n3. The authors compare against a wide range of strong baselines (both traditional and NCO). The evaluation on in-distribution, OOD-city, and OOD-cluster scenarios provides robust support for the authors' claims.", "weaknesses": "1. The NAB is a core contribution that models distance, duration, and an \"angle matrix\".However, the main paper does not define how this angle matrix is computed.\n\n2. The paper fails to specify any of the runtime parameters, configurations, or computational budgets (e.g., time limits) used for these traditional solvers.\n\n3. For dynamic features $D^t$ (defined in Appendix A), it never specifies what these features are for each problem type (ATSP, ACVRP, ACVRPTW). This is a critical missing detail for implementation.\n\n4. In Decoder, the formulation in Line 710 only uses the last node's embedding, this is a significant deviation from standard NCO practice for problems like ATSP (which also use the first node's embedding for context). The paper provides no justification for this non-standard design, making it unclear if it's an intentional choice or an omission.\n\n5. The study does not include a granular ablation on the inputs to NAB. Consequently, it is impossible to determine if the performance gain comes from the novel combination of all three features (D+T+$\\Phi$), or if it is overwhelmingly driven by just the distance matrix (D) alone.\n\n6. RRNCO's encoder is based on the AAFM from [1]  and its decoder on [2]. However, these two highly relevant works are not included as baselines in the comparison.\n\n7. The overall quality of this paper is good, but its clarity would benefit from a final proofreading pass to correct some minor typos and inconsistencies: \n- In Line 260,  \"adaptation\" is spelled as \"adaption\" ; \n- The attention layers are referred to as \"AAFM\" in the text but \"AFT Layers\" in Table 4; \n- The \"clipping hyperparameter $C$\" from Equation 20 is not defined in the hyperparameter list (Table 4);\n- Equation 10 is defined twice (lines 265 and 295);", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JmlEMGHNaF", "reviewer": "Reviewer_mJYV", "summary": "This paper introduces RRNCO, a new neural combinatorial optimization (NCO) architecture targeting practical real-world vehicle routing problems (VRP). The paper also presents a new and comprehensive VRP dataset based on OpenStreetMap data from 100 cities, enabling both in-distribution and out-of-distribution evaluation.", "questions": "1. On the Definition of \"Real-World\": Besides asymmetry, what other real-world features (as per logistics practice) does your approach not cover? How might your model adapt to additional complexities such as time-dependent or dynamic edge lengths?\n\n2. On ATSP Baselines: Why was OR-Tools not included in the ATSP comparison, given that it supports ATSP solutions? Are there technical limitations, or was this a deliberate choice? Please elaborate.\n\n\n3. On OR-Tools Computation Time: The reported computation time for OR-Tools on VRP benchmarks is shown as “7h” or “several hours.” How was this measured?\n\n4. On Generalization to Other VRP Benchmarks: How easily can your RRNCO be adapted to incorporate other benchmarks?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper introduces a large, scalable, and diverse real-world VRP dataset that captures the essential complexities (asymmetry, real-world travel times) often ignored in current research. Making this dataset open-source will prove highly valuable to the research community.\n\n2. The proposed ANE and NAB mechanisms are well-motivated, addressing the need to handle node-and-edge features natively, especially asymmetric matrices, which are more representative in real logistics.\n\n3. This paper is clearly written.", "weaknesses": "1. Problem Definition: The definition of “real-world VRP” in the paper appears to focus almost exclusively on the presence of asymmetric cost matrices (distance, duration). While this is a major source of realism, real-world VRPs are also characterized by other features such as dynamic distance changes, rich operational constraints (e.g., skills, priorities, real-time updates), time-dependent travel times, etc. The current problem definition could be more comprehensive and better justified in context.\n\n2. Comparison to OR-Tools in ATSP: In the ATSP experiments, the baseline comparisons do not include Google OR-Tools.\n\n3. Computation Time Reporting: For some baselines (e.g., OR-Tools takes “several hours”), the exact computation protocol is unclear. \n\n4. Scope of Generalization: Experiments are done on the proposed real-world dataset with varied geographies, but it’s not clear if the model's performance holds for even more complex cases. Better to show results on estinblished dataset or benchmarks as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x3iu9vtIqm", "reviewer": "Reviewer_XMP3", "summary": "This paper investigates the application of neural combinatorial optimization solvers to real-world problem instances. Specifically, the authors use a adaptive attention-free module from prior work to incorporate real-world travel time and distance features, in contrast to existing studies that rely on synthetic data with Euclidean distances. They further compile a comprehensive dataset covering problem instances from 100 cities, which serves as a testbed for evaluating the proposed method against established baselines.", "questions": "See above", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "I personally found this paper very exciting, as it presents (to the best of my knowledge) the first large-scale real-world dataset for benchmarking neural combinatorial solvers. This represents a valuable step forward, and the dataset has the potential to benefit many researchers in the community.", "weaknesses": "I do not have much to complain about this paper, below is a question that I am curious about. \n\n- Can the adaptive attention-free module handle features other than travel time and distances? What about contextual features that are shared among node pairs, for example, time of the day and weather?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)