DGL: Dynamic Global-Local Information Aggregation for Scalable VRP Generalization with Self-Improvement Learning

1 Introduction

The Vehicle Routing Problem (VRP) is a critical Combinatorial Optimization Problem (COP) with numerous real-world applications in logistics and transportation [Kim et al., 2015; Alkaya and Duman, 2013]. Given its significance, many exact and heuristic algorithms have been developed over the years [Applegate et al., 2007; Helsgaun, 2017; Li et al., 2021]. However, these traditional algorithms often incur high computational costs. Recently, neural network (NN)-based models have emerged as a promising alternative for solving VRPs [Wu et al., 2024]. These models typically leverage learned NNs to acquire heuristics for constructing solutions or improving the quality of current solutions. By leveraging the underlying patterns in training instances, neural VRP solvers [Kwon et al., 2020; Xiao et al., 2024a] achieve competitive or even superior solution quality compared to the traditional algorithms when solving test instances with the same pattern, while significantly reducing inference time.

Although neural VRP solvers have demonstrated impressive performance on instances matching the size and distribution pattern of the training data, their effectiveness often degrades significantly when applied to instances with varying scales or unseen distributions [Joshi et al., 2022; Bdeir et al., 2023]. For instance, fluctuations in customer numbers or changes in locations due to factors such as weather conditions or holidays can significantly alter problem characteristics, limiting the practical applicability of neural VRP solvers in real-world scenarios. To alleviate parts of these issues, researchers have proposed methods aimed at improving distribution and size generalization. Distribution generalization methods [Jiang et al., 2022; Bi et al., 2022] typically integrate various generalization algorithms into the model's learning framework. However, these approaches often struggle with cross-scale instances, particularly in large-scale VRPs. Conversely, state-of-the-art (SOTA) size generalization methods yield impressive results on large-scale VRPs by employing either a global-view [Drakulic et al., 2023; Luo et al., 2023] or local selection method [Fang et al., 2024; Goh et al., 2024]. However, global-view models suffer from excessive computational cost, while local selection models often lead to suboptimal solutions. Furthermore, most models [Kool et al., 2019; Kwon et al., 2020; Luo et al., 2023; Gao et al., 2024] rely on static embeddings during solution construction, failing to dynamically update information based on partial solutions, which limits the model's adaptability to changes in the problem state and hinders generalization.

To address the challenge of efficiently generalizing to the diverse and complex nature of real-world VRPs, we propose a novel model named DGL (Dynamically Global-Local Information Aggregation) that enhances problem awareness by integrating dynamically adjusted global and local features into the decision-making process. Specifically, since optimal solutions often emerge in the local neighborhood-a pattern consistently observed across problems of different scales and distributions-we select neighboring nodes as candidates for subsequent node selection, thereby capturing the problem's local invariance [Gao et al., 2024]. Simultaneously, global information is incorporated into the representations of these neighboring nodes and iteratively updated throughout the solution construction process, providing contextual understanding and facilitating the exploration of the solution space. By leveraging these continuously updated features, DGL captures the relationship between the current state and the broader problem context (e.g., direction to the destination), enabling more informed decision-making in node selection. Furthermore, to ensure DGL's robustness across diverse VRP instances, we propose a replacement-based selfimprovement learning (SIL) method. This method promotes the diversity of datasets through data augmentation and enhances model robustness by randomly removing portions of the generated dataset during training. Finally, we evaluate DGL through extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated VRP (CVRP), including synthetic datasets of varying scales and distribution patterns, two widely adopted benchmark datasets, and eight real-world country map instances. The results demonstrate that DGL exhibits excellent generalization capability, especially in solving large-scale VRP and real-world scenarios.

The key contributions of this work are as follows:

• We propose a novel model, DGL, that dynamically aggregates global and local information to enhance its perception of the current solving state, enabling it to efficiently solve diverse real-world VRPs.
• We introduce a replacement-based SIL method that uses data augmentation and random replacement to enhance DGL's robustness across different scenarios.
• We demonstrate DGL's excellent generalization performance through extensive experiments across a wide range of synthetic and real-world VRP instances, covering various scales and distribution patterns.

2 RelatedWork

In this section, we introduce several recent works aimed at enhancing model's generalization and review existing training paradigms for neural VRP solvers.

2.1 Generalization of Neural VRP Solvers

NN-based methods have shown promising results in solving VRPs [Kool et al., 2022; Qiu et al., 2022; Sun and Yang, 2023; Min et al., 2023; Xia et al., 2024; Xiao et al., 2020; Xiao et al., 2024b; Xiao et al., 2025] but with suboptimal generalization in unseen (especially in real world) scenarios that may deviate from the training data [Joshi et al., 2022]. Recent studies have been proposed to enhance model distribution and size generalization of these models, respectively.

(1) Global-view models, e.g., LEHD (excessive costs)

(2) Local-selection models, e.g., INVIT (suboptimal)

(3) DGL (ours, local selection with global view)

Distribution generalization methods [Zhang et al., 2022; Geisler et al., 2022; Jiang et al., 2022; Bi et al., 2022; Zhou et al., 2023] aim to generalize models learned from VRPs of multiple predefined distribution patterns to instances with unseen distribution by adopting various generalization algorithms, such as adversarial training and meta-learning. However, these methods often face challenges when dealing with instances of varying scales, particularly in large-scale VRPs. As shown in Tables 1 and 2, even OMNI-VRP, the SOTA model trained on multiple distribution patterns, exhibits unsatisfactory performance on large-scale VRPs.

Prior size generalization methods [Zong et al., 2022; Zheng et al., 2024; Ye et al., 2024] often involve decomposing a large-scale problem into smaller sub-problems, which are then solved independently. However, decomposing VRP with complex constraints can be difficult and may produce suboptimal solutions by failing to capture inter-dependencies among sub-problems [Luo et al., 2024]. Recently, several SOTA VRP solvers that do not rely on D&C have been proposed. These solvers frequently utilize an encoder-decoder framework, where the encoder extracts node features, and the decoder selects the next node from a candidate set of unvisited nodes based on the encoded features. These methods have demonstrated promising results in large-scale problems and can broadly be categorized into global-view [Zhou et al., 2023; Drakulic et al., 2023; Li et al., 2024; Gao et al., 2024] and local selection [Fang et al., 2024; Lyu et al., 2024; Goh et al., 2024]) models. Global-view models consider all unvisited nodes as candidates, while local selection models restrict candidate nodes to the k-nearest neighbors. Furthermore, existing models often employ static embeddings, where the node features to determine the next node remain fixed throughout the solution process. This static nature limits the solver's ability to dynamically adapt to changes in the solution stage. We illustrate these limitations and the distinctions between DGL and the existing model in Figure 1.

2.2 Training Paradigms

Neural VRP solvers typically rely on either Supervised Learning (SL) or Reinforcement Leaning (RL). SL-based methods [Drakulic et al., 2023; Luo et al., 2023] require optimal solutions as training labels, which are often challenging to obtain and computationally expensive. In contrast, RL-based approaches [Gao et al., 2024; Fang et al., 2024] suffer from sparse rewards and excessive computing costs, making them difficult to scale to larger instances [Luo et al., 2023]. Recently, a novel SIL paradigm has been explored, which selects the best solution from multiple sampled solutions to serve as an expert trajectory for supervised imitation learning. SIL methods avoid the need for expensive labels required by SL and address some of the challenges associated with RL, achieving promising results. However, existing SIL methods [Pirnay and Grimm, 2024; Luo et al., 2024] rely on fixed training instances without replacement during each epoch, which limits the model's exploration capabilities and reduces robustness. Additionally, these SIL methods determine policy updates based solely on performance over a validation set, which not only reduces training efficiency but also risks overfitting to the validation set, potentially leading to suboptimal solutions.

Unlike existing training methods, in this paper, we propose a replacement-based SIL approach that eliminates the dependence on validation sets and introduces random replacement of training instances at each epoch. This strategy enhances model robustness and expands the exploration space, improving overall training efficiency and solution quality.

3 Methodology

This section first presents the formulation of VRPs and then proposes a novel model named DGL that dynamically aggregates global and local information to efficiently solve VRPs of varying scales and distributions. Furthermore, we propose a replacement-based SIL training method to enhance DGL's robustness. The framework of DGL is presented in Figure 2.

3.1 Problem Setting

We define a VRP-n instance as a graph with n nodes, where each node is represented by its h-dimensional coordinates vi ∈ R1×h . The optimal solution to a VRP is the tour π∗ that visits all nodes with the minimum cost, c(π∗ ), corresponding to the shortest overall length of the tour. Solving different VRP variants involves adhering to various problemspecific constraints. This study focuses on two prominent VRP variants, i.e., TSP and CVRP, due to their representativeness and extensive applications across diverse domains [Kim et al., 2015]. In TSP, each node must be visited exactly once. CVRP extends TSP by introducing a depot, vehicle capacity constraints, and node demands smaller than the vehicle's capacity. A CVRP tour comprises multiple sub-tours, each representing a vehicle that starts and ends at the depot, visiting a subset of nodes, with the total demand of each subtour not exceeding the vehicle's capacity.

3.2 DGL: Dynamic Information Aggregation

Neural VRP solvers often exhibit unsatisfactory performance when applied to problems with varying sizes and distributions. While local selection-based approaches are effective for large-scale problems, they tend to converge to suboptimal solutions due to their reliance on limited local information.

To address these challenges, we propose a novel and efficient DGLmodel that incorporates global information into the features of local candidate nodes, which are then processed by a decoder to construct the solution. This strategy combines the computational efficiency of local selection with the broader perspective provided by global information. Furthermore, instead of using static embeddings to predict the next node, DGL dynamically updates global features at each step of the solution process, offering a more comprehensive representation of the current state and improving the model's ability to capture state-dependent changes.

Information Aggregation from Local and Global Views

Local View. A common observation in solving VRPs is that the optimal action (i.e., selecting the next node) lies within a small local neighborhood of the current node [Helsgaun, 2017]. This local neighborhood pattern has been consistently observed across VRPs with diverse scales and distributions [Gao et al., 2024]. To leverage this property, we focus DGL's action space on the local k-nearest neighbors, capturing local invariance across different VRPs and then enhancing model generalization capabilities.

Global View. However, focusing solely on local view often leads to suboptimal solutions, as shown by our ablation study (Section 4). Conversely, simply using the features of all nodes to capture global information as previous methods disrupts local invariance and significantly increases computational cost, making it impractical for large-scale problems. Consequently, the primary challenge lies in integrating local selection with global information effectively. The key challenge, therefore, is effectively integrating local selection with global information. To address this, we incorporate four global features-spatial relationships, distribution patterns, and relative positioning-into the candidate node representation within the local selection range.

1. Distance to the current node: We prioritize candidate nodes based on their distance to the current node to minimize cost and prevent distant routing. The global feature dist for candidate node i is computed as the euclidean distance d(i, j) between nodes i and j. πt denotes the current node at step t.
2. Average distance to all unvisited nodes: This feature allows the model to anticipate the impact of future steps by considering the spatial distribution of unvisited nodes. By integrating this information, we guide the model to consider not only the immediate next step but also the broader VRP topology. We compute this feature for candidate node i as:

where m(i) = 1 if node i has been visited and m(i) = 0 otherwise.

1. Standard deviation of distances to unvisited nodes: We consider the variability in distances from candidate node i to unvisited nodes. A higher standard deviation indicates greater variability in the node's spatial relationships, which could affect routing efficiency. We compute this feature as follows:

1. Directional vector to the starting node (or depot in CVRP): We include the directional information from the candidate node to the starting point (or depot) to align the model's decisions with the overall route direction, helping it avoid detours and move efficiently toward the destination (i.e., the starting node). The global feature for candidate node i is computed as follows:

where π0 denotes the starting node, vj i denotes the coordinates of the jth dimension of node i, and [·, ·] denotes the horizontal concatenation operator.

The distance-related features 1-3 provide insights into node positions within the VRP topology, ensuring the model can assess both local proximity and global distribution. The directional feature 4 adds orientation awareness, ensuring decisions align with the optimal path from the starting node. By integrating these position and orientation features into the knearest candidate nodes, DGL effectively maintains a global perspective when deciding the next node in the solution.

Finally, we concatenate these features for the k-nearest neighbor node i of the current node to form the model inputs as follows:

Normalization. To unify the scale of features and improve the robustness of the model, we normalize the node's features as follows:

Efficient Dynamic Feature Update. As the solution is constructed, the state at each step evolves, and the corresponding global features should be updated accordingly. However, recalculating the global features 2 and 3 at each step is computationally expensive and time-consuming due to their quadratic time complexity (O(n2 )). To address this issue, we propose using a recursive equation to update the mean and variance at each step t < n, preserving accuracy while reducing the time complexity to O(n) as follows:

Model Architecture

Unlike conventional encoder-decoder architectures, we adopt a decoder-only architecture to better capture the dynamic properties of the state during VRP solution construction. As demonstrated by the design of the GPT family [Chen et al., 2024], decoders, compared to encoders, are more effective in capturing dynamic patterns from the changing state, leading to improved generalization. Specifically, we use the features of the k-nearest nodes, processed via dynamic feature computation, as input. These features are then mapped to a probability distribution for the next node selection through L attention layers, as shown in eq. 9.

The initial embeddings are generated using a linear layer, expressed as {s1i }ki=1 = {W ˆ xi}ki=1 , where W denotes learnable parameters. The embedding at the first attention layer is then defined as follows:

where sπt denotes the embeddings of current node πt at step t. Notably, instead of explicitly including the starting node information in the input as done in conventional methods [Drakulic et al., 2023], we implicitly encode it into the global feature representation, i.e., through features 3 and 4. This design choice is based on the observation that the starting node often falls outside the local view of the current node after several steps. Explicit inclusion of the starting node could therefore interfere with the local focus on the current node.

Finally, DGL maps these embeddings to the probability distribution of each candidate node being the next node through L attention layers Attnlayer as follows:

where θ denotes model parameters. In each step of t, DGL selects an unvisited node πt according to θ, while masking invalid nodes (those already visited or exceeding capacity constraints) to ensure solution feasibility. This process continues until the tour is complete.

3.3 Replacement-based SILMethod

Considering the limitations of conventional learning paradigms (see Section 2.2), we propose a replacementbased SIL method to improve the diversity of the dataset through data augmentation and enhance DGL's robustness by randomly removing portions of the generated dataset during training. We outline the five key steps as follows:

Initialization. We randomly generate B VRP instances from a uniform distribution X and use a simple nearest-neighbor heuristic algorithm to generate initial solutions, which serve as initial pseudo-labels to warm up DGL.

Sampling. At each update step, we employ the current policy to sample M solutions for each instance via beam search. If the best solution among the M sampled solutions improves upon the current best solution for a given instance, it replaces the current solution.

Data Augmentation. To enhance model robustness, we apply data augmentation techniques to both the problem and solution sides, thereby increasing the diversity of training instances. For the problem side, we use transformations such as rotation, reflection, and normalization on the VRP topology. On the solution side, we use problem-specific enhancement methods: for TSP, considering the solution forms a cyclic sequence, we randomly apply an integer offset ϵ to the solution, i.e., πi = πi+ϵ; for CVRP, considering the solution comprises multiple sub-tours, we randomly flip sub-tours and swap the order of adjacent sub-tours. The augmented problem and solution then replace the current dataset.

Algorithm 1 Replacement-based SIL method of DGL

Require: Uniform distribution X, number of epochs E,

batch size B, sampling number M, replacement rate α. 1: Initialize policy θ 2: xi ←Generate B instances fromX ∀i ∈ {1, . . . ,B} 3: πi ←Nearest-neighbor(xi ) ∀i ∈ {1, . . . ,B} 4: for e = 1, . . . ,E do 5: for i = 1, . . . , B do 6: πj ← Sampling(DGL, xi ,M, θ) ∀j ∈ {1, . . . ,M} 7: if πi = Null or c(πi ) > minj∈{1,2,...,M} c(πj ) then 8: πi ← πj 9: end if 10: end for 11: xi , πi ←Augmentation(xi , πi ) ∀i ∈ {1, . . . ,B} 12: θ ←DGL(xi , πi , θ) ∀i ∈ {1, . . . ,B} 13: ˆ xj ← Generate α · B instances from X ∀j ∈ {1, . . . , α · B} 14: j ←Randomly select α·B indices ∀j ∈ {1, . . . , α· B} 15: xj , πj ← ˆ xj ,Null ∀i ∈ {1, . . . , α · B} 16: end for

Imitation Learning. Using the augmented dataset as training instances with pseudo-labels yi, we apply the cross-entropy loss function L(θ) = - ∑ni=1 yi log(pi(θ)) to maximize the likelihood of selecting the current best node at each step.

Random Replacement. To mitigate overfitting to a fixed dataset, which often impedes generalization to unseen scenarios, we propose a data replacement strategy that reduces the model's dependence on specific instances, promoting more flexible and generalizable learning. Specifically, we randomly replace a fraction α of the training instances with resampled data and set the solution length of these instances to infinity during the subsequent update. This introduces controlled variability into the dataset and encourages the model to learn from a broader range of data distributions, thereby enhancing its generalization capability.

In contrast to existing SIL methods that rely on static datasets without replacement, our approach eliminates the need for a separate validation set. This enables the model to improve continuously throughout training, avoiding the computational overhead of cross-validation. Consequently, our method streamlines the training process and boosts the model's robustness by exposing it to a more diverse range of data variations. We present the overall SIL strategy of DGL in Algorithm 1. The source code of DGL is accessible online 1 .

4 Experimental Results

In this section, we conduct extensive experiments on both synthetic and real-world dataset to evaluate the generalization performance of our DGL compared to baselines.

DGL Settings. To demonstrate superior generalization ability of our method, we train a single model exclusively on randomly generated instances with 100 nodes and a uniform distribution, then directly evaluate it on test instances of varying sizes and distributions. Our proposed DGL consists of 4 decoder layers with a hidden dimension of 128 and 8 attention heads. The learning rate is 1e-4 with a decay rate of 0.97. Training spans 100 epochs with 100 iterations per epoch, a batch size of 256, 64 samples per iteration, and a replacement rate of 12.5%. The hyperparameter k is set to 30 for TSP and 50 for CVRP.

1 https://github.com/wuyuesong/DGL

Baselines Settings. We select seven SOTA models for comparison, including 1) RL-based models: Omni-VRP [Zhou et al., 2023], ELG [Gao et al., 2024], INVIT-3V [Fang et al., 2024] and UDC [Zheng et al., 2024]; 2) SL-based models: LEHD [Luo et al., 2023] and BQ [Drakulic et al., 2023]; and 3) SIL based models: GD [Pirnay and Grimm, 2024]. We follow the publicly available pre-trained parameters and default settings for all baselines. We report results for LEHD and BQ with the greedy search for a fair comparison in terms of computational efficiency. We apply the same inference setup for both DGL and INVIT. All experiments were conducted on an Intel(R) Xeon(R) Platinum 8352V CPU and an NVIDIA RTX 4090 GPU (24GB).

Dataset. For the synthetic data, we adopt the MSVDRP dataset [Fang et al., 2024], which comprises 16 subsets for TSP, encompassing 4 distributions (uniform, clustered, explosion, and implosion) and 4 scales (TSP-100, TSP-1000, TSP-5000 and TSP-10000), and 12 subsets for CVRP under the same distributions but at three scales (CVRP-50, CVRP500, and CVRP-5000).

For real-world data, we adopt the widely recognized TSPLIB and CVRPLIB benchmarks. TSPLIB95 contains 77 instances varying in scale from 51 to 18512. CVRPLIB Set-X

[Uchoa et al., 2017] contains 100 instances varying in scale from 100 to 1,000. Furthermore, we test on eight country maps to further evaluate model's performance in real-world scenarios with city counts from 194 to 22775.

For all baselines and DGL, we report their average gap to the (near-)optimal solutions, i.e., LKH results for synthetic data and the best known solutions for real-world data.

Performance on Synthetic Datasets. We compare DGL against baseline models on synthetic datasets. The key findings are as follows: 1) Most models experience performance degradation when generalizing to VRPs with varying scales and distributions. 2) As shown in Table 1, DGL achieves state-of-the-art performance compared to global-view-based baselines like Omni-VRP, LEHD, and BQ, demonstrating the effectiveness of local selection. 3) DGL outperforms INViT in both solution quality and inference speed, leveraging global information and dynamically updating features to avoid local optima and better adapt to problem variations. 4) Compared to other SIL models like GD, DGL with replacement-based SIL significantly improves solution quality. 5) The increased number of nodes leads to more complex route patterns and greater diversity (CVRP-5000 in Table 2). DGL efficiently integrating information and handling this increased complexity compared to baselines.

Performance on Real-world Datesets. We compare DGL against baseline models on TSPLIB, CVRPLIB, and Country maps datasets (see Table 3). On these real-world instances, DGL consistently demonstrates superior generalization performance compared to the baselines. Real-world instances have more complex distributions than synthetic datasets, and DGL effectively integrates global information via dynamic feature computation while leveraging local invariance to handle these complexities, showcasing its robust applicability in unseen and pratical scenarios.

Ablation Studies. We conduct extensive ablation studies to evaluate the design of DGL, focusing on: 1) the effectiveness of the four global features and 2) the sensitivity to the replacement rate α and local range k. (Please contact the first author for the detailed experimental results).

The results of the ablation study on global features indicate that their inclusion significantly enhances performance, while their exclusion results in notable degradation, underscoring their critical importance. Sensitivity analysis for α shows that performance remains stable across configurations, except when α = 0, where a sharp decline is observed, validating the necessity of the replace operation. Similarly, varying k demonstrates DGL's robustness across different local range settings.

5 Conclusion

This study presents DGL, a novel approach that integrates global and local information to effectively solve VRPs. Extensive experimental evaluations on VRPs of varying sizes and distribution patterns demonstrate DGL's superior generalization capabilities and its promise for real-world applications. In future work, we aim to further improve DGL's computational efficiency. Additionally, we plan to leverage learning-based methods to automatically derive and better fuse global features, and to extend DGL to more complex combinatorial optimization problems.

Acknowledgments

This work is supported by the Jilin Provincial Department of Science and Technology Project (20240302086GX). Any opinions, findings and conclusions or recommendations expressed in this material are those of authors and do not reflect the views of the funding agencies.

Contribution Statement

Yubin Xiao, Yuesong Wu, and Rui Cao made equal contributions to this study. You Zhou and Yuan Jiang serve as the corresponding authors.