Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees
Authors: Fu Luo
Yaoxin Wu
Zhi Zheng
Zhenkun Wang
Venue: NeurIPS 2025 poster ()
Keywords: Neural Combinatorial Optimization
Vehicle Routing Problem
Constraint Tightness
Primary area: optimization

Abstract: Recent neural combinatorial optimization (NCO) methods have shown promising problem-solving ability without requiring domain-specific expertise. Most existing NCO methods use training and testing data with a fixed constraint value and lack research on the effect of constraint tightness on the performance of NCO methods. This paper takes the capacity-constrained vehicle routing problem (CVRP) as an example to empirically analyze the NCO performance under different tightness degrees of the capacity constraint. Our analysis reveals that existing NCO methods overfit the capacity constraint, and they can only perform satisfactorily on a small range of the constraint values but poorly on other values. To tackle this drawback of existing NCO methods, we develop an efficient training scheme that explicitly considers varying degrees of constraint tightness and propose a multi-expert module to learn a generally adaptable solving strategy. Experimental results show that the proposed method can effectively overcome the overfitting issue, demonstrating superior performance on the CVRP and CVRP with time windows (CVRPTW) with various constraint tightness degrees. The code is available at [https://github.com/CIAM-Group/Rethinking\_Constraint\_Tightness](https://github.com/CIAM-Group/Rethinking\_Constraint\_Tightness).

Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees
Fu Luo Yaoxin Wu², Zhi Zheng', Zhenkun Wang
1 School of Automation and Intelligent Manufacturing.
Southern University of Science and Technology. Shenzhen, China
2 Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology,
Southern University of Science and Technology, Shenzhen, China Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, The Netherlands School of Computing, National University of Singapore, Singapore 1uof20230mail sustech. edu cn, y wu22uuue nn, zhi zhenguu. nus edu, wangzhenkunS0@gmiil.. com
Abstract
Recent neural combinatorial optimization (NCO) methods have shown promising problem-solwe solving ability without requiring domain-specific expertise. Most existing NCO methods use training and testing data with a fixed constraint value and lack research on the effect of constraint tightness on the performance of NCO methods. vehicle routing problem (CVRP) an
This paper takes the sppacity-constraiggg example to empirically analyze the NCO performance under different tightness degrees of the capacity constraint. Our analysis reveals that existing NCO meth- ods overfit the capacity constraint, and they can only perform satisfactorily on small range of the constraint values but poorly other values. To tackle this drawback of existing NCO methods, we develop an efficient training scheme that explicitly considers varying degrees of constraint tightness and propose multi- expert module to learn a generally adaptable solving strategy. Experimental results show that the proposed method effectively overcome the overfitting issue, demonstrating superior performance on the CVRP and CVRP with time windows (CVRPTW) with various constraint tightness degrees. The code is available Constraint, Tightness
1 Introduction
The vehicle routing problem (VRP) an important category of combinatorial optimization problems and is encountered in many real-world applications, including transportation M navigation (2]. and robotics (3]. Due to the NP-hard nature [4], is prohibitively expensive to obtain exact VRP solutions. Traditional methods typically employ problem-speciffe heuristic algorithms, which require extensive domain domain-specific expertise. As an alternative, neural combinatorial optimization (NCO) methods have received widespread attention recently (5-8). These methods automatically learn problem-solving strategies from data using neural networks. Some advanced NCO methods can even obtain near-optimal VRP solutions without the need for expert knowledge 17]
VRP instances are typically defined with some numeric constraints. For example, the solution of capacity conttaie- VRP (CVRP) should meet the capacity constraint of each vehicle, and the
*Correspondigg author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparison results of three representative NCO models on CVRPI00 instances with in- domain capacity value (C=50) and out-of-domain capacity values (C=(10,500)). "Gap" quantifies the percentage difference between method's ' solution and the ground truth provided by the heuristic solver HGS [2I]. "Expansion" measures the ratio of the increase in the gap relative to the in-domain baseline (C=50).
In-Domain
Out-Of-Domain
C=50
C=10
C=500
Gap
Gap
Expansion
Gap
Expansion
POMO
3.66%
20.26%
5.54x
34.12%
9.32
LEHD
4.22%
36.56%
8.66x
6.82%
1.62x
BQ
3,25%
18.02%
5.54x
8.16%
2.51
solution of CVRP with time windows (CVRPTW) should visit each customer in its admissible time windows. Existing NCO methods usually train their model on problem instances with fixed
numeric constraint settings. For example, the AM [18), POMO (9. BQ [19), and LEHD [20) train and test their models CVRP instances with 100 customers (CVRP100), assuming fixed vehicle capacity of 50 and an average customer demand of 5. In this case, the capacity C=50 corresponds to constraint of relatively moderate tightness. However, when dealing with CVRP100 instances with some extreme constraints (e.g.. C=10 as a tight constraint and C=500 as a loose constraint), the performance of these NCO models significantly degenerated, illustrated in Section 3
Current NCO research has been deluded by the seemingly promising results obtained on instances with certain specific tightness, lacking comprehensive study of how constraint tightness affects model performance. To fill this gap. this paper takes CVRP as an example and performs an empirical analysis of the NCO performance under different capacity constraint tightness. We evaluate three recently proposed NCO methods (i.e., POMO, LEHD, and BQ) that are trained using CVRP instances with fixed customer demands but different capacity values, and the results are presented in Table [ As can be seen from the table, when the CVRP has extremely tight or loose capacity constraints (C=10 and 500), the optimality gaps of the NCO methods deteriorate by at least 5.5 and 1.6x, demonstrating severe performance degradation. We believe that these NCO models overfit the training instances with specific capacity tightness, i.e., C=50, and thus exhibit limited generalization ability across instances with other capacity values. In this paper, we reveal the reasons behind the performance degradation by leveraging the problem similarity between CVRP and two other VRP variants, i.c., the traveling salesman problem (TSP) and the open vehicle routing problem (OVRP). More details are provided in Section 4.1
Beyond that, this paper presents a simple yet effective training scheme to enhance the performance of existing NCO models instances of varying constraint tightness degrees. The training scheme enables models to learn a policy that is effective across a wide range of changing constraint tightness. propose multi-expert module to augment neural architectures
To further enhance adaptability, of NCO models, in which each expert specializes in distinct ranges of constraint tightness degrees. Experiments on CVRP and CVRPTW validate the effectiveness of our method across instances with varying tightness degrees.
Our contribution can be summarized as follows:
We revisit the training setting of existing NCO models and find that models trained under these settings may overfit certain specific constraint tightness. They suffer from severe performance degradation when applied to VRP instances with out-of-domain tightness degrees.
We propose simple yet efficient training scheme that enables the NCO model to be efficient on a broad spectrum of constraint tightness degrees. Moreover, we propose a multi-expert module to enable the NCO model to learn more effective policy for coping with diverse constraint tightness degrees.
Through extensive experiments on CVRP and CVRPTW, we validate the effectiveness and robustness of our method in solving instances with constraint tightness ranging from tight to extremely loose. The ablation results demonstrate that the proposed training scheme and multi-expert module are efficient in enhancing existing NCO models.

---

Table 2: Performance of recent advanced NCO models on CVRP100 instances with different capacities. The lowest optimality gap of each model across all datasets is bold.
CVRP100
C=10
C=50
C=100
C=200
C=300
C=400
C=500
Varying Cupacities
Gap
Gap
Gap
Gap
Gap
Gap
Gap
Avg. Gap
HGS 21
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
AM 18
45.16%
7.66%
12.85%
21.63%
26.26%
25.35%
27.23%
23.76%
POMO 9
20.26%
3.66 %
11.17%
22.45%
29.56%
30.80%
34, 14%
21.72%
MDAM 22
7.47%
5.38%
12.47%
21.13%
24.31%
22.55%
23.91%
16.75%
BQ 19
18.02%
3.25%
3.48%
4.53%
6.53%
6.54%
8. 8.16%
7.22%
LEHD 20
36.56%
4.22%
4.87%
4.18%
5.78%
4.92%
6.82%
9.62%
ELG (23
10.44%
5.24%
10.91%
18.70%
22.81%
21 21.84%
24.05%
16.29%
INVIT 24
17.44%
7.85%
11.12%
14.36%
15.86%
12.61% %
13.71%
13.28%
POMO-MTL 25
13.62%
4.50%
8.20%
10.40%
14.12%
13 13.44%
15.57%
11.41%
MVMoE 26
10.72%
5.06%
10.52%
17.63%
21.80%
21.86%
16.00%
17.24%
2 Preliminaries
2.1 Problem Definition
A VRP instance S can be defined on a graph g = (V,E), where V denotes the node set and = (v,, (1,,,)))e 1y), 1/ E V. 0s # b2} denotes the edge set. The nodes from 2/1 2n represent n customers, and some VRPs (e.g.. CVRP, OVRP) contain depot Un with V {er In this work, we assume an unlimited fleet of homogeneous vehicles starting from and returning to the depot to serve all customers. This follows the classical VRP formulation used in seminal NCO papers [I8] 9
The solution of VRP instance a tour æ. which is a permutation of the nodes. Given an objective function f()) of solutions, solving the VRP instance is to search for the optimal solution л with minimal objective function value (e.g.. Euclidean distance of the tour) under certain problem-specific constraints (e.g., visiting each node exactly once in solving the traveling salesman problem (TSP)). Therefore, VRP can be formulated as follows:
n minimize
((T))
where is the set of all feasible solutions, with each solution æ satisfying the problem-specific constraints. The commonly studied VRPs are elaborated below.
TSP The TSP is defined with n customer nodes. It minimizes the length of tour starting from an arbitrary customer, visiting each customer exactly once, and returning the starting customer.
The CVRP contains a depot node uo and n customer nodes. Each customer node has a demand & to fulfill, and feasible tour in CVRP is constituted by set of sub-tours that start and end at the depot, ensuring the total demand in each sub-tour does not exceed the vehicle capacity. The objective is to minimize the total distance of the sub-tours while satisfying the capacity constraint.
CVRP
OVRP OVRP extends CVRP by removing the requirement for vehicles to return to the depot after servicing customers in each sub-tour. Instead, the vehicles can end their tours at the last served customers, offering more flexibility in practical vehicle routing.
2.2 VRP Solution Construction
NCO methods primarily employ encoder-decoder neural networks to learn policies for constructing VRP solutions 18 9 Given a VRP instance, the encoder calculates embedding h, for each node 2:- These embeddings f are then utilized by the decoder to incrementally construct VRP solution (i.e., tour) by adding one node at a time to the existing partial solution. Starting from an empty solution, the decoder iteratively selects one unvisited node each step, appends it to the incomplete solution, and marks it visited. For example, at step I, the incomplete solution is represented as (IT, m2,.... 1), where कi denotes the first node added to the solution and m represents the most recently added node. This code-by-node selection process continues until all
3

---

nodes are visited, resulting in complete solution. The encoder-decoder neural networks are often
trained by reinforcement learning [8 9 23 or supervised learning [27 28 19
2.3 Definition of Constraint Tightness
For CVRP, the "constraint tightness" is directly represented by the vehicle capacity value, C. A tight constraint corresponds to low capacity value (e.g., C 10 in our paper). In this scenario, each vehicle can only serve a very limited number of customers, forcing the solution to be composed of many short sub-tours. A loose constraint corresponds to a high capacity value (e.g., = 500), Here, the capacity is large that it is barely a limiting factor, allowing single vehicle to serve many or all customers. This makes the problem characteristics approach those of the Traveling Salesman Problem (TSP). Therefore, in the context of CVRP, constraint tightness is inversely proportional to the vehicle capacity C.
We also provide a more general definition of constraint tightness independent of the problem features, such as capacity, with details presented in Appendix
3 NCO Performance on CVRP with Different Constraint Tightnesses
To investigate the impact of different constraint tightnesses on model performance. in this section, we conduct an empirical study of advanced NCO models on CVRP instances with different constraint tightnesses.
3.1 Experiment Details
we generate seven test datasets, each comprising 10,000 CVRP100 instances. Customer demands are drawn uniformly from {1.....9) .9. so the average customer demand is 5. Vehicle capacities for these datasets are set to 10, 50, 100, 200, 300, 400, and 500, respectively. C=500 represents a loose constraint that is expected to allow a single vehicle to feasibly serve all customers in a single route, while C=10 represents the tight constraint that allows vehicle to serve only two customers on average. All node coordinates are uniformly sampled within unit square, these datasets differ solely in capacity values.
Dataset Following the data generator in prior works 18
91.
NCO Methods We comprehensively collect different NCO methods for solving CVRP, including
POMO 19. BQ 19). LEHD (20). INVIT (24). ELG [23] MVMoE (26). AM 18) MDAM [22). POMO-MTL 22 We adopt their provided pre-trained models, trained on CVRPI00 with C-50, for the following evaluation.
Metries & Inference We evaluate the optimality gap (Gap) across all methods and datasets, which quantifies the percentage difference between a method's solution and the ground truth (generated by the HGS solver (2I). All evaluated NCO methods use the greedy search for inference to present their basic problem-solving ability.
3.2 Results and Observations
The experimental results shown in Table We observe that all NCO methods achieve low optimality gaps on test instances with the same constraint tightness (e.g.. C=50) as the training instances. However, their performance drops significantly on instances with unseen loose or tight constraints, For example. the optimality gap of BQ model on the dataset with C=50 is 3.25%, but the gap on the dataset with C=10 drastically expands 18.02%. POMO also shows a similar trend, with the gap on the dataset with C=50 being 3.66%, and expanding to 84.12% on the dataset with C=500. Overall, compared to the test dataset with the same capacity value as the training set, all evaluated NCO models exhibit at least 1.7x increase in the average optimality gap (i.e., INVIT has an average gap of 13.28%, which 1.7 larger than 7.85% on the dataset with C=50) when tested on the datasets with different capacities. These results indicate that current NCO models generally overfit to the trained constraint tightness, which causes the learned strategies be poorly applied to instances with other constraint tightnesses, ultimately significantly degrading their performance.

---

Véhicle Capacity
C-500
CVRP
solutios
On CVRPI00 with C=
On CVRP100 with C= 500
(Tight Constraint)
(Loose Constraint)
Optimality Gap (96
Optimellty Cap (%)
30
30
20
OVRP solition
10-
10
POwO cYRP
INVIT-TRR
LENO CVPP
80- J0-CRRP
POMO for
POMO eVRP
WVmT-CViE
LOND eVPP ao.cme
TSP soluton
POMO
Figure 1: Impact of Capacity on Prob- lem Similarity. The CVRP100 solu- tion closely resembles the OVRP solu- tion when capacity very small (e.g.. C=10) and becomes equivalent TSP solution when capacity is extremely large (e.g., C=500). We systematically quantify the problem similarity in Ap-
Figure 2: Performance of different NCO meth- ods on CVRPI00 instances with extreme con- straint tightness degrees (i.e., C=10/500). " OVRP", "-TSP", and "-CVRP" indicate that the methods specifically designed solve OVRP, TSP, and CVRP instances, respectively. A smaller optimality gap indicates better perfor- mance.
the
pendix
4 Methodology
In this section, we analyze the limitations of current NCO models from the perspective of constraint tightness. To address the performance degradation led by the constraint tightness, we propose two effective modifications to NCO models in terms of the training protocol and neural architecture. These modifications aim to enable the model learn strategies that can adapt varying degrees of constraint tightness, thereby improving the performance of NCO models in solving more general vRPs.
4.1 Limitations of NCO Methods
As observed in Section 3
NCO models generally fail to retain good performance under varying
constraint tightnesses.
When the constraint tightness changes drastically, the optimal solution structure of CVRP undergoes significant transformations, indicating that the problem requires fundamentally different solving strategies. As shown Fig. under the tight capacity constraint C=10, where the capacity capped at twice the average customer demand, each sub-tour in the CVRP solution can only serve a limited number of customers (e.g., two three). In this case, CVRP solutions exhibit structural similarities to OVRP solutions under identical capacity constraints, as sub-tours in their solutions only visit very few customers. That is, when vehicle capacity is severely limited, the sabblem-solving strategy for CVRP becomes similar to that of OVRP (except that returning to the depot is neglected). Conversely, under loose capacity constraints (e.g., C=500, approaching total customer demand), the vehicles can serve all customers in few even single sub-tour. The solution structure of CVRP resembles that TSP in this situation. Therefore, TSP-oriented solving strategies could work well for solving CVRP instances with large capacities.
We conduct experiments validate our conjecture. Specitically, we employ the POMO model specialized for solving OVRP100 instances with C=10 (denoted as POMO-OVRP) to solve CVRP100 instances (with C=10). Also, we employ the POMO model specialized for TSP (denoted POMO- TSP) to solve CVRP100 instances (with C=500). For comparison, we test several representative NCO methods, including POMO, INVIT, LEHD, and BQ, on CVRP100 instances with C=10 and C=500. These models are trained on CVRP100 instances with C=50. The results are shown in Figure 2 We observe that under small capacity, POMO-OVRP outperforms all CVRP models. For example, POMO-OVRP achieves optimality gap of 1.9%, which is much lower than INVIT's
5

---

Solution
Solution 2
Solation
Probability
xT steps
Decoder
Mulli-eapert Layer
Expert
Expert
Expert
Layer xL
Ciste
Instance
Instance 2.
Instance
Hidden State
Cj:
C
C2
C₁
5-th Instance
Constraint Tightness
High
Low
Figure 3: Model structure featuring multi-expert module. The model adopts light encoder and heavy decoder architecture, incorporating an effective multi-expert module within the decoder. The multi-expert module consists of gate mechanism and expert layers. The gate mechanism selects instances within specific ranges of constraint tightness to their corresponding expert layer for processing. Each expert layer processes the node embeddings from the L stacked attention layers and generates probability distributions for node selection during solution construction.
17.44%. Conversely, for CVRP instances with C=500, the POMO-TSP model with a gap of 2.5% demonstrates superiority over specialized NCO models for CVRP (e.g.. LEHD with a gap of 6.8%).
The results corroborate conjecture that solving strategies for CVRP under different capacities (C= (00,50,,000) differ significantly. The NCO models trained on CVRP instances with C=50 cannot be effectively applied to instances with different capacity values, thereby exhibiting significant performance degradation.
4.2 Training with Varying Constraint Tightness
In order to address the overfitting issue of existing NCO methods to enable the model to learn effective problem-solving strategies across different degrees of constraint tightness, we propose straightforward yet effective training scheme, which explicitly exposes the model to the full range of constraint tightnesses. Specifically, let Crain and Cmaz denote the minimum and maximum constraint tightness degrees in the target domain (e.g., vehicle capacities in VRPs). During training, the constraint tightness degrees are uniformly sampled from [Cmin Cmaz] for each training instance. By continuously changing the constraint tightness of the training data, the NCO model is able to learn to adjust its
strategy response to varying problem domains, improving its robustness in solving general VRP instances.
In addition, we attempt to assign all instances training batch the identical tightness degree, randomly sampled from [Cmin m. This batch-level tightness assignment, compared to the above instance-level assignment, leads to inferior model performance. A more detailed discussion with experiments can be found in Appendix E
4.3 Multi-Expert Module
When training models to handle instances with varying constraint tightness degrees, inconsistencies in problem characteristics may create conflicting optimization directions, leading to suboptimal lcarning outcomes. To address this challenge, propose integrating multi-expert module into existing NCO models, fostering more general and effective routing strategy across a broader range constraint tightnesses.
Given the outstanding performance of the Lightweight Encoder- Heavy Decoder (LEHD) model [19 20). we adopt it as the backbone model to exemplify the implementation of the multi-expert module. In general, LEHD uses L stacked attention layers the decoder construct a VRP solution step by step. As shown in Fig. we integrate the multi-expert module after the stacked attention layers in the decoder of LEHD.. The multi-expert module consists of an instance-level gate mechanism G(-) and expert layers {E,, Eg, .Em..

---

Table 3: Comparison results between model and the existing best model in each dataset. Gaps C=10, C=50/100, and C=200 to 500 come from MDAM, BQ, and LEHD, respectively.
CVRP100
C-10
C=50
C=100
C=200
C=300
C=400
C=500
Varying Capacities
Gap
Gup
Gap
Gap
Gap
Gap
Gap
Avg. Gap
Existing Best
7.47%
3.25%
3.48%
4.18%
5.78%
4.92%
6.82%
5.13%
Ours
1.54%
3.82%
3.67%
1.49%
0.87%
0.75%
0.87%
1.86%
Given an instance with constraint tightness Ck. we denote its node embedding matrix after the where No represents the number of unvisited nodes
stacked attention layers as H, the t-th step during solution construction. With C₁ and H; as inputs, the multi-expert module generates the node selection probability matrix Pts which can be formulated as
P = MEM(H, Cx)= Σ B(C.)).(H..)
(2)
Gate Mechanism Given instance, the gate mechanism assigns the node embedding matrix He to the appropriate expert layer based on the constraint tightness C₁. Specifically, the i-th expert layer E 21, m)) processes instances with constraint tightnesses in the interval [(i 1)3, where 3 = |Cmar -mmal Therefore, the gate mechanism can be formulated as a one-hot vector
if (i - 1)8 S C. -Cmin < i3, G(C,) = 0 otherwise.
{1
Expert Layer Each expert layer transforms the node embedding matrix H. into the probability matrix for node selection. To enhance the adaptability to varying constraint tightness, each expert layer comprises m, stacked attention layers (see Appendix [. for details) before the probability prediction. The calculation process within the i-th expert layer can be formulated
( AttnLayer, (He);
(4)
H(me) AttnLayer, (H 1)),
P. Softmax(W,H. (ma) + b;).
where W; and b, are learnable parameters, Different expert layers are specialized in processing different constraint tightnesses, corresponding more effective VRP strategies within one single NCO model.
Experiment
In this section, we first evaluate the effectiveness of our method across varying degrees of constraint tightness. Next, we conduct ablation studies on the key components of the proposed method. Finally, we validate the versatility of our method by applying it to CVRPTW.
Dataset& Baseline We reuse the seven test datasets from Section 3.1 to evaluate models. We evaluate the NCO methods mentioned in Section 3.T as baselines. To make our results more significant, consistently compare the best NCO model for each dataset.
the backbone demonstrate the effectiveness of the proposed method. The embedding dimension is set to d = 192. the hidden 512, the query dimension q is set to 16, and the head
Model Setting& Training We utilize the LEHD model 20 19
dimension of the feed-forward layer is number in multi-head attention is set to 12. The decoder includes L = 6 stacked attention layers and a multi-expert module with m expert layers, each containing m. = 3 layers. Following 20), we use supervised learning to train the model. The training dataset comprises one million CVRP100 instances and their corresponding labeled solutions. Each training instance has a random capacity drawn from (10, 11, ... 500). and the labeled solutions are generated using HGS [1] solver. The Adam optimizer 22) is utilized for training the models, with an initial learning rate of 1e-4 and
decay rate of 0.9 per epoch. We train the model for 40 epochs, with the batch size set to 512.
7

---

For comparative analysis, we evaluate the metric of optimality gap (Gap) across all methods and datasets, as done in Section 3.1 All models use the greedy search for inference. The inference time that quantifies a method's computational efficiency is shown in Appendix A All experiments, including training and testing, are executed on a single NVIDIA GeForce RTX 3090 GPU with 24GB of memory.
Metries&Infereece
5.1
Comparison Results
The experimental results are presented in Table 3 which demonstrate that our method outperforms oftte-of-the-ar NCO methods overall. Specifically, our method achieves an average gap of 1.86%, significantly lower than existing NCO models' average best gap of 3.71%. While our method exhibits marginally inferior performance compared the baselines C=50 and 100, it outperforms all competing methods in other scenarios (C=10, C=200, and above). Notably, for instances with C=300 C=500, our method maintains an optimality gap below 1%. These results highlight the effectiveness of our method in solving problems across varying degrees of constraint tightness.
Table 4: Effects of Varying Constraint Tightness training (VCT) and Mupti-Expert Module (MEM). The Base Model only trained on instances with C=50 and without MEM.
CVRP100
C=10 Gap
C=50
C=100
C=200
C=300
C=400
C=500
Varying Capacities Avg. Gap
Gap
Gap
Gap
Gap
Gap
Gap
Base Model
45.64%
3.72%
4.21%
3.62%
5.61%
5.36%
7.29%
10.78%
Base Model-MEM
37.03%
3.28%
4.41%
2.90%
4.56%
4.39%
6.11%
8.95%
Base Model+VCT
1.88%
4.51%
4.69%
2.25%
1.28%
1.03%
1.25%
2.41%
Base Model-VCTTMME
1.54%
3.82%
3.67%
1.49%
0.87%
0.75%
0.87%
1.86%
Table 5: Results on CVRPTW instances with different degrees time windows constraint tightness.
CVRPTW100
0.2
0.5
1.0
1.5
2.0
2.5
3.0
Varying Time Windows
Gap
Gap
Gap
Gap
Gap
Gap
Gap
Avg. Gap
POMO
14.95%
13.11%
11.39%
16.40%
21.62%
27.34%
33.56%
19.58% 11.23%
POMO-VCT
12.22%
14.11%
13.73%
12.40%
12.14%
POMO-VCT+MEM
9.13%
11.57%
11.91%
13.30%
13.24%
11.58%
10.37%
11.58%
5.2
Ablation Study
We conduct an ablation study evaluate the contributions of two key components: 1) varying constraint tightness training (VCT) and 2) the multi-expert module (MEM). We compare three training configurations: the model trained on CVRPI00 instances with fixed capacity (C=50) 1) without MEM and 2) with MEM; 3) the model trained on instances with capacities C ~ Uni 500)) and without MEM; 4) the model trained on instances with capacities C. Unif([10, 500]) and with MEM. We maintain& consistent training data budget across all experimental settings. Results of these models on the test sets are presented in Table
From these results, we can observe that while adding only the MEM reduces the average gap from 10.78% to 8.95%. providing modest benefit, varying constraint tightness training leads to significant improvements in the model's problem-solvine gap from 10. 78. to 2.41%. However, this approach causes a slight performance degradation on the datasets with C=50 and C=100. The reason may be that the different constraint tightness degrees create conflicting optimization directions, leading suboptimal learning outcomes. When the multi-expert module is incorporated, the model achieves consistent performance gains across all datasets, reducing the average gap by 23% (from 2.41% % to 1.86%). These results demonstrate that while varying constraint tightness training enhances moos-constraint-tiihneee generalization, the integration of the multi-expert module further strengthens this capability, enabling more robust adaptation to problem instances with varying constraint tightness.
ability on 5 out of 7 datasets, reducing the average
8

---

6 Versatility
To demonstrate that our proposed method is applicable to other routing problems, validate it on CVRPTW instances with varying degrees of time window constraint tightness. We provide the CVRPTW definition and introduce a coefficient to quantify the tightness of the time window constraint coefficient in Appendix [F]
We apply our proposed method to the classic POMO model to solve CVRPTW instances with varying degrees of time window constraint tightness. The hyperparameter settings of the POMO model follow the description in its original literature [9]. We train the model for 1,000 epochs using reinforcement learning, with each epoch containing 10,000 samples and a batch size of 64. For training under different constraint tightness degrees, the tightness coefficient for the time window constraints is set to a ~ Uniform (0.0, 3.0), where a - 0.0, a = 1.0, and a = 3.0 denote the extremely tight, moderate, and loose constraints, respectively. For the multi-expert module incorporated into POMO, the i-th expert layer is specialized in solving instances with time window tightness in the range [(i [(i-1) 1),, Implementation details for the multi-expert module can be found in Appendix G We train three POMO models separately: 1) the original POMO model trained with the instances of default time window constraint (i.e., 1.0). 2) the model with varying constraint tightness training, and 3) the model with varying constraint tightness training and the multi-expert module. These models use greedy search for inference and are evaluated datasets with tightness coefficients ranging from = 0.2 to a = 3.0. The experimental results are presented in Table 5
From the experimental results, we observe that when alpha changes from 1.0 to 0.2/3.0, the optimality gap of the original POMO model increases from 1 11.39% to 14.95% and 33.56%, respectively. The introduction of varying constraint tightness training improves the model's 's' performance in all cases except for a = 1.0. The augmentation of the multi-expert module further enhances the model performance across all degrees of constraint tightness. These results indicate that CVRPTW, the NCO method also has the overfitting issue and exhibits significant performance degradation when the constraint tightness changes drastically, and the proposed method can effectively tackle the limitation, enhancing the NCO model for VRP with varying domains of time windows.
Related Work
7.1
NCO on VRPs with Fixed Constraint Tightness
NCO methods primarily learn construction heuristics to arrange input nodes into feasible solutions. The pioneering Ptr-Net [27 introduces a Recurrent Neural Network (RNN)-based architecture to solve TSP through supervised learning. In contrast, Bello et al. (30 employs reinforcement learning to eliminate dependency on labeled solutions. Subsequent work by Nazari et al. 31 extends this framework to solve CVRP. A significant advancement comes with the Attention Model [8] which adopts the Transformer architecture (32 to achieve sate--of-the-rt performance across various VRPs with up to 100 nodes. This inspires numerous AM-based enhancements 19 33 22 37 that narrow the performance gap with classical heuristic solvers. However, these methods share a critical limitation: they are typically trained on VRP instances with fixed constraint tightness. For example, models trained CVRP100 instances typically adopt fixed capacity of C=50 9 38 26 25 23 This training paradigm may overfit the NCO models on training instances with certain specific constraint tightness, restricting their adaptability to other cases. As result, these models suffer severe performance degradation when applied to instances with out-of-domain constraint tightness. Our work systematically investigates the underlying causes of this limitation and provides new insights to tackle it.
19
20 24
7.2
NCO on VRPs with Varying Constraint Tightness
Among them, Manchanda et al. [39 apply meta-learning [41] to train models on CVRP instances with a few certain capacities C' E {10, 30, 40}. while Zhou et al. [40 focus on the instance-level large- scale generalization considering different capacities. While these approaches demonstrate improved generalization compared to fixed-capacity training, they exhibit two key shortcomings. First, they lack comprehensive study of how constraint tightness affects model performance and an in-depth analysis of the cause. Second, they fail to account for extreme scenarios (c.g., C=500), which
Recent efforts have attempted to incorporate capacity variations during training 39 40

---

may lead to model performance deterioration when solving instances with extremely small or large capacities. Our work revisits these challenges through systematic analysis of constraint tightness impacts, providing methods to tackle different tightnesses of general VRP constraints (i.e., vehicle capacity and time window).
8 Conclusion, Limitation, and Future Work
Conclusion In this work, we revisit the training setting of existing NCO models and empirically reveal that models trained under this setting may overfit instances of specific constraint tightness, thereby suffering from severe performance degradation when applied to instances with out-of-domain tightness degrees. To overcome the limitation, scheme and a multi-expert module. Extensive experiments on CVRP and CVRPTW validate the effectiveness and robustness of our method in solving instances with constraint tightness ranging from extremely tight to extremely loose. In future work, we plan to apply the proposed method to other NCO models to further explore its generality.
propose varying constraint tightmess training
Limitation and Future Work While our model demonstrates strong generalization performance across varying degrees of constraint tightness, is currently trained using a uniform sampling strategy, where the constraint tightness degrees of training instances uniformly sampled. A promising direction is to develop an adaptive sampling strategy for further performance enhancement across the entire constraint tightness spectrum. Another important future direction involves extending our method to other COPs, such as scheduling, planning, and bin packing.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China (Grant 62476118) the Natural Science Foundation of Guangdong Province (Grant 2024A151501 17599, the Guangdong Science and Technology Program (Grant 2024BI 1212010002)) and the Center for Computational Science and Engineering Southern University of Science and Technology.
References
[1] Thierry Garaix, Christian Artigues, Dominique Feillet, and Didier Josselin. Vehicle routing problems with alternative paths: An application to on-demand transportation. European Journal of Operational Research, 204(1):62 2010.
[2] Mouhcine Elgarej, Mansouri Khalifa, and Mohamed Youssfi. Optimized path planning for electric vehicle routing and charging station navigation systems. In Research Anthology on Architectures, Frameworks, and Integration Strategies for Distributed and Cloud Computing, pages 1967-1167. IGI Global, 2021.
[3] Francesco Bullo, Emilio Frazzoli, Marco Pavone. Ketan Savla, and Stephen Smith. Dynamic vehicle routing for robotic systems. Proceedings of the IEEE, 9989):1482-1544, 2011.
[4] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Saaechetii-Saaccamed and Marco Protasi. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290K2):405-21,, 2021.
Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. CaDA: Cross-problem routing solver with constraint-awarc dual-attention. International Conference on Machine Learning, 2025. URL https://openreviee
[7] Changliang Zhou, Xi Lin, Zhenkun Wang, and Qingfu Zhang. Learning reduce search space for generalizable neural routing solver. arXiv preprint 2rXiv:2503.03137, 2025.
[8] Changliang Zhou, Canhong Yu, Shunyu Yao, Xi Lin, Zhenkun Wang. Yu Zhou, and Qingfu Zhang. Urs: A unified neural routing solver for cross cooslemoblem zero-shot generalization. arXiv preprint 2rXiv:250..2343.. 2025.
10

---

[9] Yeong- Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 21 188-21199,, 2020.
[10] Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. UDC: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. In Advances in Neural Information Processing Systems. 2024.
[11] 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. 195611 2024.
[12] Kai Li, Fei Liu, Zhenkun Wang, Xialiang Tong, Xiongwei Han, Mingxuan Yuan, and Qingfu Zhang. Ars: Automatic routing solver with large language models. arXiv preprint arXiv:2502.15335 2025.
[13] Kai Li, Ruihao Zheng. Xinye Hao, and Zhenkun Wang. Multi-objective infeasibility diagnosis for routing problems using large language models. arXiv preprint arXiv: 03306, 2025.
[14] Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. Monte carlo tree search for comprehensive exploration in LLM-based automatic heuristic design. In International Conference Machine Learning, 2025. URL
[15] Rui Sun, Zhi Zheng, and Zhenkun Wang. Learning encodings for constructive neural combinatorial optimization needs to regret. Proceedings of the AAAI Conference on Artificial Intelligence. 38(18): 20803-20811, Mar. 2024. doi: 10.1669/aaii.v33 138:18.30069 / aaai orgg/ndez...........o iid/x.ddexxxx... php/
AMT/articlle/vier/0006.
[16] Zhi Zheng, Shunyu Yao, Genghui Li, Linxi Han, and Zhenkun Wang- improvement heuristics for multi-objective route planning. IEEE Transactions on Intelligent Transportation
Pareto improver: Learning
Systems, 25(1):1033 1043, 2024, doi: 10.1109/TITS, 201TI3.022.333166
[17] Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin XU. Rethinking light decoder-based solvers for vehicle routing problems. In International Conference on Learning Representations, 2025. URL
httpa://openreviee net/forumm iddporn/
[18] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn solve routing problems! In International Conference on Learning Representations, 2019.
[19] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[20] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Information Processing Systems, 2023.
[21] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap" neighborhood. Computers Operations Research, 140: 105643 2022.
[22] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12042 12049, 2021.
[23] 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. International Joint Conference on Artificial Intelligence, 2024.
[24] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. INVit: A generalizable routing problem solver with invariant nested view transformer. In International Conference on Machine Learning, 2024.
[25] Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1898-1908. 2024.
[26] Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. arXiv preprint arXiv:2405.01009, 2024.
[27] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, 2015.

---

[28] Chaitanya K Joshi. Thomas Laurent. and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint 19Xx::1906.01227, 2019.
[29] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, San Diega, CA, USA, 2015.
[30] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 16.1.9990 2016.
[31]
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, volume 31, 2018.
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, 2017.
[33] Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions on Industrial Informatics, 17(7):4611448777 2020.
[34] André Hottung, Yeong- Dae Kwon, and Kevin Tiemney. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
[35] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combi- natorial optimization. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[36] Jinho Choo, Yeong-Dac Kwon, Jihoon Kim, Jeongwon Jac, André Hottung, Kevin Tiemne, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. In Advances in Neurul Information Processing Systems, volume 35, pages
2022.
[37] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: deep reinforced multi-pointer transformer for the traveling salesman prohlem. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
[38] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards amni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learning, pages 42769- 42789. PMLR, 2023.
[39] Sahil Manchanda, Sofia Michel, Darko Drakulic, and Jean-Mare Andreoli. On the generalization of neural combinatorial optimization heuristics. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 426-442. Springer, 2022.
[40] Changliang Zhou, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Instance- conditioned adaptation for large-scale generalization of neural combinatorial optimization. arXiv preprint arXiv:2405.0 200.0990.. 2024.
[41] A Nichol. On first-order meta- meta-learing algorithms. arXiv preprint arXiv:1803.0299 2018.
[42] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[43] Sergey loffc and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift, In International Conference on Machine Learning, pages 448-456. pmir, 2015.
[44] Keld Helsgaun. An extension of the in-kkrmighann-ellgaan tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University. 12, 2017.
[45] Robert Bixby Vašek Chvátal David Applegate and William Cook. Concorde tsp solver. Concorde tsp solver. 2006.
[46] Heinrich Paessens. The savings algorithm for the vehicle routing problem. Eurupean Journal of Operational Research, 34(3):336-34, 1988.
[47] Marius M Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2):254-263 1987.
[48] Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, and Jie Zhang. Learning to handle complex constraints for vehicle routing problems. Advances in Neural Information Processing Systems, 37:93479 935099, 2024.
12

---

[49] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Advances in Neural Information Processing Systems, volume 34, pages 26198-26211, 2021.
[50] David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver, 2006.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have introduced the scope in both the abstract and introduction, and summarized the contributions in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitation and future works in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
14

---

Justification:
The paper is mainly based on experiments.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided detailed implementation details and experiment settings in Section G and Section 5 respectively, to ensure reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
We have released the code, the link to which shown in the abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
www.SSubmisiooooiiiooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experiment settings are detailed in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Neural combinatorial optimization (NCO) methods typically operate deter- ministically and report the mean objective value or the gap to the optimal (or best-known) solution key performance metrics.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The Experiments compute resources are detailed in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
The research presented in this paper fully conforms to the NeurlPS Code of Ethics.
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The proposed learning based method for solving VRPs is not anticipated to have any specific negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work does not release such data or models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have included the licenses of baseline solvers and datasets in Section P
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The datasets utilized this paper are either sourced from prior research generated using methodologies established in earlier studies, all of which have been appropriately cited.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: this paper, we study neural methods for solving TSP and CVRP without the need of crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
19

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non standdad components.
Please refer to our LLM policy for what should or should not be described.
20

---

A Inference Time Between Different Methods
We have recorded the inference times for all baseline models as well as HGS, and present them alongside their average optimality gaps in Table For the NCO models, the reported times represent the total duration required to solve a standard test set of 10,000 CVRPI00 instances on a single NVIDIA RTX 3090 GPU. It is important note that HGS runs single CPU, and its reported inference time is not directly comparable to the GPU-accelerated times of the learning-based methods.
The results highlight that our proposed method achieves an effective balance between solution quality and computational efficiency. Compared to the baseline model LEHDD, our method's inference time approximately 2.1x longer (57.6s vs. 27.0s). However, this modest computational increase yields substantial 5.2x reduction the average optimality gap (from 9.62% to 1.86%). Furthermore, when compared to other recent methods like BQ and INVIT, model is not only more accurate but also faster. For example, our method reduces the optimality gap by over 3.8x compared to BQ (1.86% vs. 7.22%) while being nearly twice fast (57.6s 109.8s).
Table 6: Total Inference time for solving 10,000 CVRP100 instances. The average inference time (Avg. Time) quantifies method's s average computational efficiency on each dataset (consisting of 10,000 instances).
CVRP100
Avg. Gap
Avg. Time
HGS
0,00
4.5h
AM
23.74%
2.0g
POMO
21.72%
3.0g
MDAM
BQ
7,22%
1.8m
LEHD
9.62%
27.0s
16.29%
9,5s
INVI
13.28%
2.6m
POMO-MTL
11.41%
3.0g
MVMoE
17.24%
12.6s
Ours-CVRP
1.86%
57.6s
B Detailed Formulation of Attention Layer
B.1
Attention Layer
The attention layer (32 is widely used in the neural VRP solver. It comprises a multi-head attention (MHA) block and node-wise feed-forward (FF) block. Each block incorporates the residual connection [2] and normalization (Norm) 43 operations. Given ( E RRadd and ((-11) Rmxd the inputs the ε-th attention layer, the output (() is calculated as
X = NoroooMM(HHAA
((-1)) +x((2))),
(5)
( Norm(FF(X* x) + X).
For simplicity, the entire process can be represented by
( AttnLayer(X (())))).
(6)
For readability, omit the (E) and (e 1) in the following context.
B.2 Multi-head Attention
We first describe the single-head attention function as follows:
Aun(X, Y) softmax ("WW)) YWv.
(7)
Vd
where X E R and Y E R are the input matrices, and Wq E Rdxdi Wx E Rdxds Wy pddd, are learnable parameters.
21

---

The multi-head attention sublayer applies the single-head attention function in Equation times in parallel with independent parameters:
7 for
MHA(X, Y) Concat(head,, head, W
(8)
head; Attn, (XX, (X, Y),
where for each of
d2 = d, d/h. wo E Rdxd is learnable matrix.
B.3 Feed-Forward Layer
FF(X) max (W, b1) +2, where W1 gaxddr, by Rd and W2 E R xd E IRd are learnable parameters.
C
Quantification of Problem Similarity
To measure how the similarity of two COPs under different constraint tightness, we propose problem similarity metrie. Intuitively, the similarity between two COPs increases as the difference between their objective values values- calculated by applying each problem's 's optimal solution to the other's s constraints diminishes. Therefore, given two COPs (Problem A and B), we formally define the problem similarity as:
caluul--cleulatedd
Si = -11 Obbj((A) -A)j (1 Obbja Objj
Obja
Obja
(10)
BB Transferability
B-A Transferability
where Obja and Objø the objective values of the optimal solutions for Problems A and B under their original constraints. Obja(4 (AA) represents the objective value of Problem A's solution adapted to Problem B's constraints, and Obj (B) is defined analogously. The first term quantifies the transferability of Problem A's solution to Problem B, while the second term measures the reverse. High similarity requires both terms to be large.
Problem Similarity between CVRP and OVRP/TSP To validate Equation 10 we compute
similarities between three problem classes: TSP, CVRP, and OVRP. We vary the capacity constraint
tightness for CVRP instances (CVRPI00 dataset) by setting capacities to C' = 10, 50, 400, 500, ranging from tight loose. We use the classical solver HGS [1]. LKH3 [44], and Concorde [45]
to solve the dataset under CVRP, OVRP, and TSP constraints, separately, with results presented in Table
From these results, we observe two key trends: 1) When capacity is small (e.g., C' 10), CVRP and OVRP show strong similarity (97.5% but weak similarity to TSP (25.5%). 2) As capacity increases (e.g., C 500), CVRP's similarity to OVRP drops to 74. %, while its similarity to TSP rises sharply to 2..2%. This aligns with the observations from Section 4.1 relaxed capacity constraints make CVRP resemble TSP (a single route with no capacity limits), whereas tight constraints emphasize the routing structure shared with OVRP.
Table 7:
Problem similarity analysis across capacity constraints. Transferring rules: OVRP->CVRP adds return trips the depot: CVRP-iTSP removes capacity constraints, and TSP= reintro- duces them. We detail solution transformation in Appendix
CVRP100
C10
C50
C400
C500
OVRP cost
30.88
9.84
7.49
7.49
CVRP cost
59.77
15.55
7.87
TSP
7.80
7.80
7,80
7.80
OVRP -CVRP cost
60.67
17.25
9.78
9.74
CVRP- cost
31.18
11.33
7.76
7.70
TSP-CCRP
70.47
17.91
8.78
7.98
CVRP-
13.17
10.68
7.96
7.83
Similarity CVRP-OVRP
97.5%
75.66 75.6%
75.5%
74.1%
Similarity CVRP-TSP
25.5%
53.5%
88.9
98.2%
22

---

Table 8: Analysis of problem similarity between CVRP and CVRPTW under varying time window constraint tightness degrees.
CVRPI00
0.2
3.0
5.0
CVRP cost CVRPTW cost
15.51
15:51
15.51
[5.51
33.77
24.42
15.81
15.55
CVRP-CVVRPS CVRPTW cost
59.69
38.89
18.89
16.08
CVRPTW -CVP cost
24.42
21.24
15.80
15.55
Similarity CVRP-CVRPTT
25.7%
79.0%
96.3%
Problem Similarity between CVRP and CVRPTW To validate the versatility of Equation T0 we employ it quantify the similarity between CVRPTW and CVRP across varying time window constraint tightness degrees. Using the classic heuristic solver HGS [21], we solve CVRPI00 instances with vehicle capacity C 50, incorporating time window constraints with tightness coefficients a E {0.2, 1.0, 3.0, 5.0}. The results Table S demonstrate a clear trend: under tight constraints (i.e., higher than those of CVRP. In contrast, loose constraints (i.e., a = 5.0) yield 96.3% similarity and approximate solution costs. This trend occurs because tight time windows force vehicles return to the depot frequently after serving only a few customers, resulting in elongated sub-tous. In contrast, under loose time window constraints, vehicles serve multiple customers before returning, shifting the dominant constraint to capacity, and aligning the behavior more closely with standard CVRP.
0.2), the similarity drops to 9.9%, with CVRPTW solution costs 2.18 times
D Details for Solution Transformation
D.1 CVRP-TSP
We transform the solutions of CVRP and TSP into each other in the following handerafted manner.
Converting CVRP Solution to TSP Solution
1. Path Segmentation Phase:
We disconnect the edges linking each sub-tour with the depot in the CVRP solution, forming independent path segments. For each isolated node (such as the depot), a virtual path segment consisting of two identical points is constructed.
We gradually merge path segments using a greedy strategy. Initially, random path segment selected. Then we calculate the length of the selected path between its endpoints and those of the remaining path segments using four connection methods (head-head, head-tail, tail-head. tail-tail) and choose the connection combination with the shortest distance to merge. We iteratively execute this process until all path segments are merged into single path, and finally close the path into a loop by connecting its ends.
Path Reconstruction Phase:
Converting TSP Solution to CVRP Solution Let the depot be any node in the path. The conversion process starts traversing from the starting point of the TSP path, dynamically maintaining the cumulative demand value. When adding the next node would cause the total demand exceed the vehicle capacity, perform the following operations:
1. Insert depot node after the current node.
Reset the cumulative demand value to zero.
3. Start visiting the next node from the depot again.
This process continues until the TSP path is fully traversed, ultimately forming a CVRP solution that complies with the capacity constraints.
D.2 CVRP-OVRP
We transform the solutions of CVRP and OVRP into each other in the following handcrafted manner.
Converting CVRP Solution to OVRP Solution For each sub-tour in the CVRP solution, we first identify the two edges directly connected to the depot, corresponding to the vehicle's
23

---

departure path (first edge) and return path (last edge), respectively. We then calculate the Euclidean distances of these two connecting edges and mark the longer one as the final return path. By removing this return path, the closed-loop sub-tour is converted into an open sub-tour, forming a solution that conforms to the characteristics of OVRP.
Converting OVRP Solution to CVRP Solution For each open sub-tour in the OVRP solution, the edge between the end customer node and the depot node is connected, forming a solution that complies with the closed-loop constraints of CVRP.
D.3 CVRP-CVRPIW
Converting CVRP Solution to CVRPTW Solution
First, we decompose the solution into independent sub-tours. For example, the solution 0-1-2-0-3 is decomposed into sub-paths [0,1,2,0] and [0,3,4,0] where each sub-tour starts and ends exclusively at the depot.
Second, we perform the time window-based path splitting for each sub-tour:
1. Sequential calculation: Starting from the depot, for each node, we calculate: 1) the arrival time (departure time from the previous node travel time), 2) the service start time (the maximum value between the arrival time and the node's 's earliest service time), and 3) the service end time (service start time + service duration).
Violation detection:
node's arrival time exceeds its latest service time, or the return time to the depot exceeds the depot's ' operating deadline, a new depot node is immediately inserted before this node, splitting the path into two sub-tours.
3. Iterative correction: Repeat the above verification for newly generated sub-tours until all sub-tours satisfy the time window constraints.
Third, the path direction optimization performed. We perform bidirectional time window- based path splitting for each sub-tour: Calculate the total travel distance of split sub-tours by performing the time window-based path splitting on the sub-tour for both the forward and reverse directions, separately. And finally choose the sub-tour with the shorter distance. Finally, collect all the split sub-tours to form complete CVRPTW solution.
. Converting CVRPTW solution to CVRP Solution
1. Merge optimization phase: First, calculate the merge savings value 46 for all sub-tour pairs (the difference between the sum of the distances traveled separately by the two paths and the distance traveled by the merged path) in the CVRPTW solution and establish a priority queue in descending order of savings value. we then sequentially select the top sub-tour pairs from the queue for verification, and perform the merge operation only if the total demand after merging does not exceed the vehicle capacity and the merged sub-tour length is strictly shortened.
we repeat the above operation until no more sub-tours can be merged. this situation, all the merged sub-tours form a legal CVRP solution.
E
Batch-level vs. Instance-level Strategy for Assigning Constraint Tightness
During model training, the strategy of assigning varying capacities to instances within each batch significantly impacts training outcomes. We compared two capacity allocation schemes: the batch- level random capacity, where all instances in batch share an identical value randomly sampled from [10, 500] during training, and the instance-level random capacity method, where each instance's s capacity is independently sampled from the same interval, allowing heterogencous capacities within a batch. We train two models under these two settings, with testing results presented in Table
From these results, we observe that the instance- random capacity strategy consistently outper- formed the batch-level one across all datasets. We suspect that this superiority arises from differences in training dynamics: batch-level random capacity causes drastic batch capacity changes, leading to inconsistent parameter update directions and persistent optimization misalignment that hinders gradient descent and convergence quality. In contrast, the instance-level random capacity approach maintains statistically consistent update directions by exposing the model to diverse capacity values within each batch, resulting in stabilized convergence trajectories.
24

---

Table 9: Batch-level vs. Instance-level random C' for model training.
CVRPIO0
C10 Gap
C50 Gap
C100
C200
C300
C400
C500
Gap
Gap
Gap
Gap
Gap
Ratch-level random C'
1.99%
4.66%
5.02%
2.46%
1.6%
0.89%
0.94%
Instance-level random C
1.54%
3.82%
3.67%
1.49%
0.87%
0.75%
0.87%
F
Quantification of Time Window Constraint Tightness for CVRPTW
CVRPTW Following 47 we define the CVRPTW as follows. Building upon CVRP, CVRPTW introduces a time window [ea, 4] for each customer node i, representing the earliest and latest times at which customer can be visited. Additionally, each node has a service time 8,, which represents the duration vehicle must remain at the node upon arrival. The depot has time window (co, lo] but no service time. Each vehicle departs from the depot at time ep and must return before 4-- Let i and] be two consecutive nodes sub-tour and let Dÿ denote the time at which the vehicle on sub-tour r arrives at node i. The departure time from node is given by by + 8,, and the arrival time the next node is calculated as: bj max(ej, by 8; + taz), where taj is the travel time from node to node j. equal to the Euclidean distance between the two points. The calculation of arrival time indicates that if the vehicle arrives node j earlier than its start time ej, it must wait until ej to begin service. the vehicle arrives at node j later than Ij. the sub-tour becomes infeasible. The objective of CVRPTW is minimize the total Euclidean distance of all sub-tours.
Time Window Tightness Based on the original time windows, we relax or tighten the time window for each customer node follows:
8 1; a0)
(11)
é max(e; + +,,0)
1 -
where the original constraints correspond to = 1.0. This formula indicates that small coefficient represents narrow time windows and a large coefficient represents wide ones. The negative start time will be clipped to zero. In addition, we adjust the service time. Since the service time at each node already relatively long, increasing further could lead to problem becoming infeasible. Therefore, only allow relaxation of the service time, defined as: sf max 2 st).
G Implementation Details of Multi-expert Module in POMO
POMO model The POMO model [9] also has an encoder that generates the node embeddings using the input node features, and a decoder used to convert the node embeddings into the node selection probabilities.
We denote the node embedding matrix generated by the encoder as H. = (1. (4) JEN, where N. represents the number of unvisited nodes, h4 is the embedding vector of the i-th unvisited node. The context vector is fi., concating the first and last node embeddings. The original decoder is formulated as:
hr MHA(he. H.). P= (C) tanh (M)THH vdz.
(12)
where C is a constant.
POMO model with Multi-expert Module For POMO, instead of adding the multi-expert module the decoder, we add it to the encoder since we empirically find that works better. The multi-expert module is generally the same as the one presented in Section
25

---

H Discussion on Multi-expert Modules: Discrete Switching and Continuous Generalization
Our multi-expert module, in its current form, functions by switching between specialized experts rather than learning single, continuously adaptable policy. This is a deliberate design choice informed by empirical investigation.
The goal of learning unified policy that generalizes continuously across the entire constraint spectrum is indeed highly desirable. We explore this direction by implementing a top-K Mixture-of- Experts (MoE) model with learnable and soft gating network following MVMoE [1], with K This approach replaces the discrete, rule- based switching with mechanism that learns to assign weights different experts, allowing for a weighted combination of their outputs based on the imput features. Due to space limitations. We detail the implementation of the top-K MoE module as follows.
Implementation of Top-K mechanism:
Gating Mechanism:
The gating network G is used to select K experts from N experts for each input instance x with capacity of C. Firstly, the gating network calculates gating score vector based on the instance features x: (xx) E N
S(x) = G(x).
Next, we adopt the Top-K strategy to select the K experts with the highest scores (in our implemen- tation, K = 2). Let [ax) be the index of the K experts with the highest scores. The final gated weight vector (xx) E RN is obtained by applying the Softmax function to the sparse scores:
(x(x) [Softmax ((,ftaaxSS(())) if i T(x),
0
otherwise.
Here, (z) represents the weight assigned to instance x by the i-th expert.
2. Sparse Computation and Output Fusion:
The key advantage MoE lies the K experts selected by the gating network (i.e., F, for i ((x)) will be activated and perform the computation. The final output (ar) of the model is the weighted sum of the outputs of these experts:
Conditional Computation feature. For each instance x, only
N
O(x)
Σ Ex(x)
Since for the experts with é I(x), Wi(x) 0. this summation is actually only performed on the selected K experts. Thus, while ensuring the model capacity, it significantly saves computational resources.
Load Balancing Auxiliary Loss:
To prevent the gated network from only activating few "popular" experts while neglecting the training of other experts, we introduce auxiliary loss faur encourage load balancing. This loss consists of two parts: the importance loss and the load loss, both of which are achieved by minimizing the square of the coefficient of variation (CV) of the task allocation among experts:
Lava CV² (Importance) CV2((Lat)
Among them, the "Importance" metric measures the total gating weight that each expert obtains in the batch data B:
Importance, Σ Wi(z).
And the "Load" measures the number of times each expert activated (i.e., selected as the Top-K) in the batch data B. Let (x) be indicator function, which is when expert is selected and
26

---

otherwise:
i T()), otherwise.
Load, Σ M.(),,
where M((x)
ZEB
The square of the coefficient of variation is defined as:
std (V) mean V) +
CV²(V)=
Here, V is vector (such as Importance or Load), and is small constant used to prevent division by zero.
4. Final Training Objective
During the training process, will weigh and sum the main task loss Cg- and the auxiliary loss Lauz to form the final optimization objective:
Crotal = Lmasn + a Loux-
Here, a is a hyperparameter used to balance the main task learning and the expert load balancing, In this way, the model can learn a more generalized strategy to handle VRP problems under different constraint intensities. We set a to 0.01 following MVMoE [26].
We train the model with this Top-K MoE module using the same settings method (detailed in Section 5) and compare against the discrete switching mechanism ("Switch- ing"). The models are evaluated {10, 50, 100, 200, 300, 400, 500]. As shown in Table 3, while the Top-K MoE approach is con- ceptually appealing, the simpler, discrete switching mechanism achieved superior performance across most tightness regimes, resulting in a lower overall average gap (Switching: 1.86% vs. Top-K: 2.17%). Given these empirical results, we select the more performant switching mechanism.
proposed
CVRP100 instances with the capacity values C
Table 10: Comparison of our proposed discrete switching mechanism against a soft, learnable Top-K MoE gating mechanism on CVRP100 instances.
CVRP100
C=10 Gap
C=50 Gap
C=100
C=200
C=300
C=400
C=500 Gap
Varying Capacities Avg. Gap
Gap
Gap
Gap
Gap
Top-K MoE
1.48 %
4.58%
4.49%
1.94%
1.07%
0.77%
0.83% %
2.17%
Switching
1.54%
3.82%
3.67%
1.49 %
0.87 %
0.75%
0.87%
1.86 %
Furthermore, would like emphasize that a primary contribution of this work is the identification and systematic analysis of the constraint tightness-overffiting problem in existing NCO methods. While our proposed solution is straightforward, it effectively alleviates this newly highlighted issue. We believe our findings and methods provide valuable insights that can inspire interesting future works, including the development of more sophisticated, continuously generalized policies.
I Discussion on Generality: Extending the Constraint Tightness Framework to More Complex VRP Variants
Our current definitions of "constraint tightness" for capacity and time windows are tailored to the specific VRP variants studied in the paper. This was deliberate starting point to thoroughly investigate phenomenon we found to be overlooked.
However, capacity and time windows are two of the most fundamental and ubiquitous constraints in the entire field of vehiele routing. Their presence is standard in vast array of VRP variants. Therefore, a method that robustly handles the tightness spectrum of these core constraints already possesses significant potential for broad applicability.
To empirically test the universality of our framework, we conduct experiments on more complex VRP variants: the VRP with Backhauls and Time Windows (VRPBTW) and the VRP with Backhauls,
27

---

Duration Limit (L), and Time Windows (VRPBLTW). These problems introduce additional structural constraints (backhaul and duration limit) on top of the standard capacity and time window constraints. We apply our proposed method (VCT training and the MEM module) to the time window constraint in these new, more complex settings, using POMO as the base model. We follow MVMoF (26 to configure the settings of additional constraints, backhaul, and duration limit.
The results presented in Table II demonstrate the effectiveness of our approach. From the table, we can observe that the standard POMO model once again suffers from severe performance degradation as the time window constraint moves to be either tighter or looser than the standard = 1.0. In contrast, our enhanced model (POMO our method) significantly mitigates this issue, maintaining much more stable and superior performance across the entire tightness spectrum.
These results strongly suggest that our framework is not a fragile solution limited to simple problems. Instead, it can function as robust and adaptable sub-system. It can be integrated into solvers for more complex problems to specifically handle the challenge of varying constraint tightness, without conflicting with the logic required for other constraints. We hope this work brings attention the critical issue of constraint tightness in the NCO community and inspires future research to develop diverse strategies for this challenge across a wider range of combinatorial optimization problems.
Table 11: Performance on Complex VRP Variants (i.e., VRPBTW and VRPBLTW) with Varying Time Window Tightness
VRPBTW100
alphu=0.2 Gap
alplu=0.5 Gap
alpha=1
alpha=1.5 1.5
alphu=2
alpha=2.5
alpha=3 Gap
Varying Time Windows
Gap
Gap
Gap
Gap
Avg. Gap
OR Tools
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
POMO
18.81%
13.35%
8.46%
12.12%
19.42%
30.27%
43.96%
20.91%
POMO+ Our Method
13.23%
11.97%
9.34%
8.67%
9.07 %
8.80%
9.11%
10.03%
VRPBLTW100
alpha=0.2
alpha=0.5
alpha=1
alpha=1.5
alpha=2
alpha=2.5 Gap
alpha=3 Gap
Varying Time Windows
Gup
Gop
Gup
Gap
Gup
Avg. Gap
OR-Tools
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
POMO
98%9
13.32%
8.29%
11.42%
17 17.06%
23.73%
31.16%
17.70%
POMO Our Method
13.00%
11.80% %
9.09%
8.42%
8.92%
8.45%
8.56%
9.75%
Formal Definition of Constraint Tightness
A more rigorous and general definition of "constraint tightness" is important, and more general definition that is independent of specific problem features shown as follows.
We propose to define the "tightness" of a constraint as: the degree of degradation in the objective value of solution produced by a reference algorithm due to the introduction of that constraint.
The intuition that tighter constraints restrict the solution space, forcing a reference algorithm to find higher-cost solutions. That is, constraint acts an impediment to the heuristic algorithm, forcing it to construct a less direct, more complex solution path. This manifests as a quantifiable increase the final objective value. For example, in CVRP, tight capacity constraint (e.g., C 10) necessitates frequent returns to the depot, resulting in many short, high-cost sub-tours. This contrasts with a loose constraint (e.g., C 500), where the solution structure resembles single, efficient TSP tour.
In this paper, we use simple, general heuristics like Nearest Neighbor (NN) as reference algorithms. We avoid using strong solvers to ensure that our definitions are both practically simple and general. Furthermore, simple heuristics are computationally inexpensive, facilitating an efficient analysis.
1. Formal Definition of Constraint Tightness
We formalize this definition with the following equation. Let P be combinatorial optimization (CO) problem instance, with the objective of minimizing the function (TT), where π is a solution to the instance:
Let Pa be the instance with specific constraint &.
Let Pg be the unconstrained baseline, representing the problem with constraint ş fully relaxed.
28

---

Let Pi be the extreme- extreme-constrain version, where the constraint is exceedingly tight, serving as an upper bound for the solution objective value degradation.
Let H. be simple, general deterministic heuristic solving algorithm. It serves the reference algorithm.
The heuristic H. can find a feasible solution to the problem P.
Let ((H(P)) be the objective value of the solution generated by the algorithm H for instance P.
The value of f used compute tightness refers the objective value of feasible solution.
The range of the function is strictly greater than 0.
Then, the tightness Tg)) of the constraint & can be defined as:
log(s (H.)) log(s [ (H (Po)) P,H() log(f (H (Pt)) -logff (H (P)))
(13)
Interpretation of the Formula:
This formula calculates normalized rate of the objective value degradation caused by constraint ç. The numerator measures the logarithmic increase the objective value relative to the unconstrained baseline Pg. This is then normalized by the denominator, which measures the maximum possible logarithmic increase in the objective value from the "unconstrained" to the "extreme" case.
The resulting tightness score, T(g), is dimensionless value within the range [0,1]. A score of T()) signifies completely "loose" constraint with no negative impact on the solution. T({) = indicates that the constraint imposes the maximum possible solution objective value degradation, equivalent to the extreme case.
Logarithmic Scaling: We observe that objective function values in CO problems change sharply as the constraint tightness changes (as shown in the table below). Therefore, employ the logarithm compress this scale, making the tightness metric stable.
This formula offers several key advantages:
1. Generality: quantifies tightness by observing the impact the constraint on the solution generated by general heuristic algorithm, rather than relying on problem-specific physical parameters (such as capacity, time window width, etc.). It is therefore applicable any combinatorial optimization problem for which "unconstrained" and "extreme" baseline cases can be defined.
2. Absolute Quantifiability: It provides dimensionless scalar value for any given instance, enabling meaningful tightness comparisons across diffeeennt instances.
3. Reproducibility: By using the simple, general, and deterministic heuristic (c.g., Nearest Neighbor) as reference algorithm, the tightness calculation is fully reproducible and computationally inexpensive.
While developing this definition, we also considered alternative definitions, such as those based on solution structure (e.g., number of sub-tours) or constraint features (e.g., capacity values). These were found be either too problem- speciffc or difficult to generalize. We therefore selected defining tightness via its impact on the objective function value, mentioned above.
2. Generalization to Different Problems
To demonstrate the versatility this general definition, we apply to three CO problems: two VRP variants (CVRP and CVRPTW) and the classic Knapsack Problem (KP) follows.
2.1 For CVRP:
Constrained Instance (P²): standard CVRP instance with a finite vehicle capacity Goop- Unconstrained Baseline (P)): This baseline is formed by relaxing the capacity value to sufficiently large value to serve all customers in single tour.
29

---

Extreme Constraint Baseline (Pi): This baseline represents the most restrictive scenario, where constraints are so tight (e.g.. capacity is minimal) that each vehicle can serve only one customer before returning to the depot.
Reference Algorithm (H)): We use a Nearest Neighbor (NN) heuristic adapted for the CVRP. The algorithm iteratively constructs routes by adding the closest unvisited customer. If adding a customer would violate the vehicle's remaining capacity, the current route is finalized, and a new route begins from the depot.
2.2 For CVRPTW:
Constrained Instance (Pę): A standard CVRPTW instance with time window constraints.
Unconstrained Baseline (P)): This baseline derived by relaxing the time windows to be infinitely large.
Extreme Constraint Baseline (Pi): Similar to the CVRP case, extremely tight time windows can force a vehicle to return to the depot after each delivery, resulting in single-customer routes.
Reference Algorithm (H): The reference heuristic is an adapted Nearest Neighbor (NN) algorithm. It extends the CVRP's NN logic by verifying both capacity and time window feasibility before appending customer route.
2.3 For the Knapsack Problem (KP):
Problem Description: Given set of items, each with weight and value randomly sampled from (0, 1), select which items to include in a knapsack so that the total weight is less than equal given limit weight capacity Ckp- The objective is maximize the total value of items in the knapsack. The instances used in this study, denoted as KP200, consist of 200 items.
Constrained Instance (Pt): A standard KP instance with knapsack capacity constraint Ckp-
Unconstrained Baseline (P)): This corresponds to knapsack with infinite capacity. The optimal solution is trivial: select all items.
Extreme Constraint Baseline (Pi): This occurs when the knapsack capacity is set to the minimum weight among all available items. Consequently, the only feasible non-empty solutions involve selecting the single, lightest item.
Reference Algorithm (H): The reference a standard greedy algorithm. sorts items by their value-to-weight ratio in descending order and sequentially adds them to the knapsack until no more items can fit within the capacity limit.
Experimental Validation
We evaluate the proposed tightness formula across the CVRP, CVRPTW, and KP instances. The results, summarized in Table 1, reveal clear and consistent trend: constraints relaxed from the extreme case towards the unconstrained baseline, the calculated Tightness value smoothly transitions from O. For example, in the CVRP instances, increasing the vehicle capacity (Coap) from 10 to 50 and then to 500 causes the tightness to decrease from 0.837 to 0.280 and 0.018 8, respectively, bridging the gap between the extreme case (Tightness 1.0) and the unconstrained TSP (Tightness 0.0).
These findings confirm that our metric provides robust and intuitive measure of constraint intensity, successfully quantifies the absolute tightness of a single instance while also enabling direct comparison of relative tightness between different instances.
In addition, we would like to clarify that the analysis in our main paper explores a comprehensive range of tightness values, i.e., [0.018, 0.837] for CVRP with C' E [10, 500] and [0.072, 0.717] for CVRPTW with a E [0.2, 3). This scope is broad enough to reflect the overfitting issue associated with the NCO model trained CVRP100 (tightness = 0.280) and CVRPTW (tightness = 0.418).
30

---

Table 12: Tightness Value Calculation Results for Different Problems under Various Degrees of Constraint Tightness. "Extreme Case" means that the constraint exceedingly tight, serving as an upper bound for the solution objective value degradation.
CVRP1000
Method
Extreme Case
C=10
C=50
C=100
C=200
C=300
C=400
C=500
Unlimited
NN
Obj. Value Tightness
103. 986
70.684
18,886
13.774
11.329
10.415
10.494
10.146
9.726
1.000
0.837
0.280
0.147
0.064
0.029
0.032
0.018
0.000
CVRPTW100 Extreme Case
a=0.2
a=0.5
a=1
0=1.5
a=2
a=2.5
0=3
Unlimited
NN
Obj. Value
103. 986
64.422
51.709
40.473
30:436
25.687
23.043
21.611
19.136
Tightness
0.717
0.587
0.443
0.274
0.174
0.110
0.072
0.000
KP200
Extreme Case
C=0.1
C=1
C=2
C=55
C=10
C=25
C=50
Unlimited
Greedy
Obj. Value Tightness
0.532
3.346
11,217
16.103
36.477
57.655
81,116
99.865
1.000
0.649
0.418
0.349
0.259
0.192
0.105
0.040
0,000
K
Additional Experimental Demonstration on the Model's Overfitting to Capacity Constraints
Analyzing how the solution structure changes with varying capacity provides more direct and powerful evidence for our claim that existing models overfit to the capacity constraint on which they are trained. To provide this justification, we conduct supplementary analysis focusing solution structure: the average number of vehicles used. We compare the solutions generated by three representative neural solvers (POMO, BQ, and LEHD), all pre-trained on CVRPI00 instances with C=50, against the (optial solutions from the classical HGS solver. The evaluation is performed on datasets with varying capacities (C = 10, 50, 100, 500), each containing 10,000 instances. The results presented in Table [3] show the average number of vehicles used by each method and the percentage gap relative to the HGS baseline.
key aspect of the
Table 13: Comparison of average number of vehicles used across different capacities
Mothod
Validee
Vehucle Nun.
Vehicle
Vehicle
Velicle Nuci
Vehicle Nun.
Veliele
Vchicle
19G5
$3.19
0.00%
10.44
0.00%
5.44
0,00%
1.44
0.00%
POMO 57.18
3.50%
10.65
2115
6:11
14.15%
3.7%
159 075
PQ
56384
6,86%
1062
1.72%
5.61
3.15%
1.91
32.04%
LEHD 65.43
23.01%
10.95
7.72%
1.9c
From these results, we can observe that the gap the average number of vehicles used by the neural models, relative to the HGS baseline, is minimized at C=50. As the capacity deviates from this training value, i.e., becoming either tighter (C=10) or looser (C=100, 500), the gap increases substantially. For example, the gap for LEHD at C=10 and C=500 is 4.7x and 7.1x larger. respectively, than its gap at C=50. This demonstrates that when faced with instances requiring a fundamentally different solution structure (e.g., <53 vehicles for C=10 or m1 vehicles for C=500), the models fail to adapt. They generate solutions with a suboptimal number of vehicles, which directly contributes to the higher overall travel costs reported in main paper.
L Explanation and rationality analysis regarding the selection of the constraint range (Ominy Cmaz]
We would like to offer detailed discussion about how to determine this range in practical applications.
1. Determining the Range in Practical Applications
In practical applications, a direct and effective method is to analyze historical operational data. For example, logistics company could derive empirical range that reflects its specific business characteristics by statistically analyzing the vehicle capacities and total customer demands from its past tasks. Our method be flexibly applied to train model on any such empirically derived range [Omin Cmar]] to achieve promising performance for that specific operational context.
2. Principled Rationale for the Range Selection in Our Paper.
31

---

The primary motivation for selecting the range [10, 500] is to comprchensively cover the entire spectrum of the CVRPI00 problem's 's characteristies within controlled experimental environment. (a) Lower Bound Cmin 10: This value is set to simulate a tight constraint scenario. In our experimental setup, following the seminal works [8] 9), customer demands are uniformly distributed A vehicle capacity of 10 means vehicle can serve only two customers on average,
in (1....,). 9). pushing the problem to the brink of feasibility.
(b) Upper Bound Cmaz = 500: This value is set to simulate loose constraint scenario. For CVRPI00 instance with 100 customers and an average demand of 5, the total expected demand is 500. When the capacity approaches this value, the capacity constraint becomes nearly irrelevant. This range ensures that model is exposed to the full spectrum of problem structures during training. This is crucial for thoroughly analyzing and addressing the overfitting issue of NCO models under varying constraints.
Representativeness of the Chosen Range on Real-World Benchmarks
To further validate that our chosen range holds practical relevance, we analyze 192 instances from the classic CVRPLIB benchmarks (A, B, E, F, M. P. and X sets). We find that across these real-world instances, the number of customers served by single vehicle in a sub-tour ranges from a minimum of 2 a maximum of 27. In our experimental setting, vehicle can serve between 2 (for C' 10) and 100 (for C = 500) customers. This demonstrates that our training setup's range of possible sub-tour sizes fully encompasses those observed these widely used real-world benchmarks. This strong quantitative evidence shows that our selected range is not only conceptually comprehensive but also highly representative of real-world application scenarios.
M Analysis of the Computational Cost of the Multi-Expert Module
We record the average inference time and optimality gap for our model with and without the module, with the results presented in Table 14 below. The results clearly demonstrate that the MEM module achieves a significant improvement in solution quality at modest computational cost.
Specifically, incorporating the MEM reduces the average optimality gap from 2.41 41% to 1.86% which constitutes relative performance improvement of 23%. We acknowledge that this performance gain accompanied by a moderate increase inference time (from 0.67 min to 0.96 min). However, we believe that this trade-off is highly favorable. In many weal-world application scenarios (c.g., logistics planning and resource scheduling), the economic benefits derived from a higher-quality solution (e.g., reduced travel distance and vehicle costs) typically far outweigh this one-time computational expense.
Table 14: Impact of the Multi-Expert Module (MEM) on Performance and Inference Time. Both models are trained with varying constraint tightness.
CVRPI00 Varying Capacities Avg. Gap
Avg. Time
Ours without MEM
2.41%
0.67m 0.96m
Ours with MEM
1.86%
N Impact of Node Demand Distribution on Model Performance
The distribution of node demands is also critical factor influencing model performance. While did consider this factor in our initial experimental design, we made a deliberate choice to isolate a single variable, vehicle capacity, for our study. This approach allows us to clearly and rigorously demonstrate the constraint overfitting issue inherent in existing methods.
A heterogeneous demand distribution would likely pose an even greater challenge. We have conducted an experiment to validate this. We create a new test dataset where customer demands follow a more realistic heterogeneous distribution: long-tailed distribution. We choose this distribution because, in many real-world applications (such as e-commerce and parcel delivery), the majority of customers have small demands, while only few have very large demands.
32

---

Specifically, we generate the long-tailed demand distribution follows: for each possible demand value d E (1, 4, 5, 6, 9}. its probability of occurrence P(d) is given by the formula below:
P(d)
Ei=1
where the hyperparameter d 1.5 controls the skewness of the distribution. The specific probabilities for each demand value are shown Table 15
Table 15: Probabilities of demand values under a long-tailed distribution.
demand (d)
2
8
P(d) 0,5042 0.1800
0.098
0.0637
0.0455
0.0346
0.0275
0.0225
0.0189
this basis, we evaluate the performance of several NCO models across different scenar- ios. These models are pre-trained instances with uniform demand distribution (C=50, CVRPI00). The test scenarios include: (a) Fixed Capacity (C=50): Tested under both uniform and long-tailed demand distributions. (b) Varying Capacities: Capacity C' is drawn from the set {10, 50, 100,200. 200. 300, 400, 500), also tested under both uniform and long-tailed demand distribu- tions. For each of these seven capacity values, the corresponding test set comprises 10,000 instances. The experimental results are shown in Table T6]
Table 16: Impact of demand distribution on exisiting models' performance. The bolded Gap indicates significant decline in performance of the model when the distribution of demand changes to Long-Tailed pattern.
CVRP100
C=50
Varying Capacitios
Uniformed Demand Gap
Long: Thiled Demand
Uniformed Demand
Long. Tailed Demand Avg. Gap
Gup
Avg. Gap
HGS
0.00%
0.00%
0.00%
0.00%
23.58%
POMO
3.60%
12.16%
21.72%
26.04 %
MDAM
5.38%
13.71 %
16.75%
19.41
LEHD
4,22%
4.54%
9.62%
7.98%
BLG
5.24%
11.29% %
16.29%
18.92%
12.31
POMO-MTL
4.50%
6.93%
11.41%
12.76 %
MVMoF
5.00%
8.53%
17.24%
19.29 %
The results clearly show that under the fixed capacity (C=50) setting, when the demand distribu- tion shifts from uniform long-tailed, almost all evaluated NCO models experience significant performance degradation. For instance, POMO's gap drastically increases from 3.66% to 12. 12.16%. Under the varying capacities setting, most models also exhibit trend of performance decline. These experimental results strongly confirm your assessment: the distribution of customer demands is indeed crucial factor affecting the generalization capability NCO models. The performance of existing models is substantially compromised under more realistic and challenging heterogeneous demand distributions.
33

---

Generalization of the Constraint Overfitting Issue: From VRPs to Other CO Problems
The overfitting issue with respect to constraint tightness, which we discuss in the context of VRPs, also manifests other CO problems. can be observed in other CO problems, such as the Knapsack Problem (KP) with its capacity limit, the Bin Packing Problem (BPP) with bin capacities, or the Job-Shop Scheduling Problem (JSSP) with task completion deadlines.
To provide empirical evidence, we conduct a case study on KP. Following the setup of POMO, we generated KP200 instances with varying capacities: C E {2, 10, 25, 503. We then evaluate two representative models, POMO and BQ, using their publicly available checkpoints that are trained specifically KP200 instances with fixed capacity of C=25, Both models used greedy search for inference. The results are presented in Table 17
Table 17: Performance of baseline NCO models on KP200 instances with different capacities. The larger the value is, the better the model performs.
KP200
C=2
C=5
C=10
C=25
C=50
Method
Value
Gap
Value
Gap
Valuo
Gup
Value
Gap
Value
Gap
OR-Tools
0.000%
0.000%
36.467
0.000%
57.665
0.000%
81,163
0.000%
POMO
9.673
40.132%
23.539
8.488%
34.128
5.590%
57.393
0.472%
79.855
1611%
BQ
15,653
3.119%
25.546
0.686%
36.369
0.269%
57.611
0.094%
80.624
0.664%
As shown in the table, the performance of both POMO and BQ degrades significantly as the capacity deviates from the training value of 25. For the tight constraint C=2, the POMO model's gap explodes to 40.132%, an 85x increase compared to its performance at C=25. Similarly, the BQ model's gap at C=2 is 33x larger than its gap at C=25. When the constraint becomes looser at C=50, the performance drop is also evident, with the gaps for POMO and BQ increasing by 3.4x and 7 x. respectively. These experimental results on KP strongly demonstrate that the constraint overfitting issue also occurs in other CO problems extending beyond VRPs.
34

---

P Licenses
The licenses for the codes used this work listed in Table
Table Licenses for codes used in this work
Resource
Type
Link
License
LKH
Code
bttp:///weebooteli.n did Keld/resauccbLKK133
Available for academic research
bttps://ittubb.com http://....mmcccc/////ooom HyHyee
Concorde 50
Code bttps://ithubb.co
BSD 3- 3-Clause License
POMO
0
Code https///ittuu..com/ coomydd-kwwe Somiyddkwow//PMM0 AWO
MIT I License
bttpp///itbubb.oo www.://ao..mmcmmmmaa CroAAMG
Livense
BQ
Code http://giiuu..oo/mmeeeeebe nco
DC-NC--SA 4,0
INVI 25
Code http:://ituu.ccom/keee htthhhoomm//aaa
Available for academic research use
ELG
Code http://gtbub.coo/gacrr//t/
MIT License
https///ithub..oo wwtp://..oooooeoooooeoooooo
License
AM 1
Code
MIT License
MDAM
Code
MIT License
35


Reviews:
[{"review_id": "AhhLoqgdpj", "reviewer": "Reviewer_tHuz", "summary": "The paper studies the effect of constraint tightness on neural solvers for vehicle routing problems. It shows that existing approaches overfit to the capacity tightness of the training data and provide low quality solutions if the capacity in test differs from the one used in training. It then studies two approaches for addressing this shortcoming based on data augmentation and using capacity as a feature. The advantage of the proposed approach is shown in numerical experiments.", "questions": "I find the experimental results convincing. However, I would like to see the trade-off between computational budget and solution quality more clearly presented. Specifically:\n- can you show explicitly the number of training instances used in the ablation study?\n- can you show the training time as a function of the constraint tightness?\n- can you show the inference time between the different method as well as compared to HGS?", "limitations": "See questions.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is well-written. It presents convincingly the limitations of existing NCOs in extensive experiments. I find the analysis of CVRP solutions as a continuum between OVRP and TSP solutions very intuitive, and clearly showing the effect of constraint tightness on solutions. The methodological contributions to address the shortcomings of existing approach are: (1) augmenting the data with varying constraint tightness, and (2) integrating constraint tightness as a feature when computing node probabilities. Interestingly, the first approach is already sufficient to provide significant improvements compare to the baselines.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer tHuz,\n\nThank you very much for taking the time and effort to review our work. We are delighted to know you find our paper well-written, convincingly presents in solving the limitations of existing NCOs in extensive experiments, the analysis of CVRP solutions as a continuum between OVRP and TSP solutions is very intuitive, and clearly shows the effect of constraint tightness on solutions, and the proposed approach provides significant improvements compared to the baselines.\n\nWe address your concerns point-by-point as follows.\n\n> **Q1. can you show explicitly the number of training instances used in the ablation study?**\n\nThank you very much for raising this question. To ensure a fair and direct comparison in our ablation study (Section 5.2, Table 4 in our main paper), we maintain a consistent training data budget across all experimental settings. Specifically, **each model is trained on a dataset of 1000,000 CVRP100 instances** along with their corresponding labeled solutions. This number is consistent with the main experimental setup detailed in Section 5.1 (line 223).\n\n\n> **Q2. can you show the training time as a function of the constraint tightness?**\n\n\nThank you very much for raising this question. We would like to clarify that in our framework, **the training time remains almost constant regardless of the constraint tightness**. To empirically validate this, we conduct an experiment. Specifically, we train seven separate LEHD models (with MEM module but without varying constraint tightness training), each on a dataset of one million CVRP100 instances with a distinct, fixed capacity constraint: $C \\in ${10, 50, 100, 200, 300, 400, 500}. All other training parameters and the model architecture were held constant across these experiments. The training time per epoch for each model is reported in Table 1.\n\n\nAs the results show, the training time is almost constant across different capacity values. This is an inherent characteristic of the constructive NCO models we investigate. The model builds a solution by sequentially selecting one node at each step for a fixed number of steps (i.e., 100 steps for CVRP100). The capacity constraint $C$ is used to check the feasibility of a partial tour and guide the policy network's output, but it does not alter the number of operations required in each forward and backward pass. Therefore, since the number of nodes and the size of the training dataset are fixed, the training time per epoch is unaffected by the tightness of the capacity constraint.\n\n\n\nTable 1: Model Training time associated with different degrees of constraint tightness\n\n|  | C=10 | C=50 | C=100 | C=200 | C=300 | C=400 | C=500 |\n|---|---|---|---|---|---|---|---|\n| Training time per epoch | 2.40h | 2.39h | 2.37h | 2.44h | 2.44h | 2.45h | 2.45h |\n\n\n> **Q3. can you show the inference time between the different method as well as compared to HGS?**\n\n\nThank you very much for raising this question. We have recorded the inference times for all baseline models as well as HGS, and present them alongside their average optimality gaps in Table 2. For the NCO models, the reported times represent the total duration required to solve a standard test set of 10,000 CVRP100 instances on a single NVIDIA RTX 3090 GPU. It is important to note that HGS runs on a single CPU, and its reported inference time is not directly comparable to the GPU-accelerated times of the learning-based methods.\n\n\nTable 2: Total Inference time for solving 10,000 CVRP100 instances.\n|  | CVRP100 |  |\n|---|:---:|:---:|\n|  | Avg. Gap | Avg. Time |\n| HGS | 0.00 \\% | 4.5h |\n| AM | 23.74\\% | 2.0s |\n| POMO | 21.72\\% | 3.0s |\n| MDAM | 16.75\\% | 26.8s |\n| BQ | 7.22\\% | 1.8m |\n| LEHD | 9.62\\% | 27.0s |\n| ELG | 16.29\\% | 9.5s |\n| INViT | 13.28\\% | 2.6m |\n| POMO-MTL | 11.41\\% | 3.0s |\n| MVMoE | 16.00\\% | 12.6s |\n| Ours | **1.86\\%** | 57.6s |\n\nThe results highlight that our proposed method achieves an effective balance between solution quality and computational efficiency. Compared with the baseline model LEHD, while our method's inference time increases moderately, it yields a substantial 5.2x reduction in the average optimality gap (from 9.62\\% to 1.86\\%). Furthermore, when compared to other recent methods like BQ and INViT, our model is not only more accurate but also faster. For example, our method reduces the optimality gap by over 3.8x compared to BQ (1.86\\% vs. 7.22\\%) while being nearly twice as fast (57.6s vs. 109.8s).\n\nThank you again for your time and effort dedicated to reviewing our work.  We will carefully incorporate the above discussions into our revised paper. We sincerely hope that our responses can effectively address your concerns."}, {"review_id": "v35vNz8r3j", "reviewer": "Reviewer_tyK7", "summary": "This paper investigates a critical, yet often overlooked, challenge in Neural Combinatorial Optimization (NCO) for Vehicle Routing Problems (VRPs): the impact of constraint tightness on model performance. Most existing NCO methods train and test on data with fixed constraint values, leading to a strong tendency to overfit specific constraint degrees. This results in significant performance degradation when applied to problems with different (i.e., looser or tighter) constraints, limiting their real-world applicability.\n\nTaking the Capacitated Vehicle Routing Problem (CVRP) as a primary example, the paper empirically demonstrates this overfitting issue. To address this drawback, the authors propose a novel training scheme and a multi-expert module designed to learn a more generally adaptable solving strategy.\n\nThe key contributions of this work are:\n\nEmpirical Analysis of Constraint Overfitting: The paper provides a thorough empirical analysis demonstrating that existing NCO methods for CVRP overfit the capacity constraint, performing well only within a narrow range of constraint values.\n\nEfficient Training Scheme for Varying Tightness: A new training scheme is introduced that explicitly considers and incorporates varying degrees of constraint tightness during the training phase.\n\nMulti-Expert Module: A novel multi-expert module is proposed. This module learns to adapt its solving strategy based on the specific constraint tightness of a given problem instance, making the overall model more robust and generalizable.\n\nImproved Generalization: Extensive experimental results on CVRP and CVRP with Time Windows (CVRPTW) with diverse constraint tightness degrees show that the proposed method effectively overcomes the overfitting issue and achieves superior performance across a wide range of constraint values.", "questions": "Question: The paper proposes a \"multi-expert module\" to learn a generally adaptable solving strategy. However, could the authors elaborate on whether the model truly learns a continuous, unified generalization across the entire spectrum of constraint tightness, or if its adaptation primarily involves switching between implicitly specialized \"experts\" optimized for specific ranges of tightness?\n\nQuestion: The definition of \"constraint tightness\" is effectively applied to CVRP and CVRPTW. However, how can this specific definition and the proposed multi-expert framework be universally applied or adapted to other types of Combinatorial Optimization Problems (COPs) or more diverse VRP variants with qualitatively different or more complex constraint structures (e.g., time windows for specific deliveries, vehicle type constraints, dynamic capacities)?", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nQuality: The paper addresses a highly relevant and often overlooked problem in NCO: generalization across different constraint tightness degrees. The empirical analysis demonstrating overfitting in existing methods is well-conducted and clearly illustrates the problem. The proposed solution, involving both a novel training scheme and a multi-expert module, is technically sound and logically designed to tackle the identified issue. The experimental validation is comprehensive, testing on CVRP and CVRPTW with varying capacities and time window tightness, showing consistent and significant improvements over strong baselines.\n\nClarity: The paper is well-written and structured. The problem of constraint overfitting is clearly defined and motivated. The empirical analysis supporting this problem is presented concisely with illustrative figures. The proposed training scheme and the multi-expert module are explained logically, with clear diagrams (e.g., Figure 2) that aid in understanding the architecture and flow. The mathematical formulations are clear, and the overall narrative flows smoothly, making it easy to comprehend complex ideas.\n\nSignificance: This paper makes a significant contribution by highlighting and providing an effective solution for the constraint overfitting problem in NCO. This issue is a major barrier to the practical deployment of NCO models, as real-world problems rarely conform to a single, fixed constraint value. By enabling NCO models to generalize across different constraint tightness degrees, the work significantly enhances the robustness, flexibility, and real-world applicability of neural solvers for VRPs. The insight into \"rethinking\" how NCO models are trained with respect to constraints is impactful.\n\nOriginality: The core idea of systematically analyzing and then addressing the problem of NCO overfitting to specific constraint tightness degrees is highly original. While multi-task learning or conditional models exist, the specific formulation of the \"constraint tightness embedding\" and the design of the \"multi-expert module\" to adapt the solving strategy based on this embedding are novel contributions within the NCO domain. The empirical evidence of this overfitting phenomenon is also an original insight that challenges common NCO training paradigms.\n\nWeaknesses:\nWhile the paper proposes a \"multi-expert module\" to learn a generally adaptable solving strategy, a weakness is that this module, in practice, function more akin to an ensemble of specialized sub-models, each implicitly optimized for a specific range of constraint tightness. If the adaptation primarily involves switching between these specialized \"experts\" rather than a continuous, unified generalization across the entire spectrum of tightness, it could diminish the originality of achieving a single, truly adaptable policy and might be seen as a sophisticated form of training multiple models for different tightness regimes.\n\nThe specific definition of \"constraint tightness\", while effective for the Capacitated Vehicle Routing Problem (CVRP) and CVRP with Time Windows (CVRPTW), might be too problem-specific. This could limit the universality and direct applicability of the proposed multi-expert architecture and training scheme to other types of Combinatorial Optimization Problems (COPs) or even more diverse VRP variants with different or more complex constraint structures, thus potentially reducing its overall generalizability beyond the explored VRP contexts.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer tyK7,\n\nThank you very much for taking the time and effort to review our work. \nWe are delighted to know you find our paper well-written and structured, makes a significant contribution by highlighting and providing an effective solution for the constraint overfitting problem in NCO, and our core idea is highly original.\n\nWe address your concerns point-by-point as follows.\n\n\n> **C1. While the paper proposes a \"multi-expert module\" to learn a generally adaptable solving strategy, a weakness is that this module, in practice, functions more akin to an ensemble of specialized sub-models, each implicitly optimized for a specific range of constraint tightness. If the adaptation primarily involves switching between these specialized \"experts\" rather than a continuous, unified generalization across the entire spectrum of tightness, it could diminish the originality of achieving a single, truly adaptable policy and might be seen as a sophisticated form of training multiple models for different tightness regimes.**\n\n> **The paper proposes a \"multi-expert module\" to learn a generally adaptable solving strategy. However, could the authors elaborate on whether the model truly learns a continuous, unified generalization across the entire spectrum of constraint tightness, or if its adaptation primarily involves switching between implicitly specialized \"experts\" optimized for specific ranges of tightness?**\n\n\nThank you very much for your insightful comment and comment and question. We acknowledge that our multi-expert module, in its current form, functions by switching between specialized experts rather than learning a single, continuously adaptable policy. This is a deliberate design choice informed by empirical investigation, and we appreciate the opportunity to elaborate on our reasoning.\n\nThe goal of learning a unified policy that generalizes continuously across the entire constraint spectrum is indeed highly desirable. We explore this direction by implementing a top-K Mixture-of-Experts (MoE) model with a learnable and soft gating network following MVMoE [1], with $K=2$. This approach replaces the rule-based switching with a mechanism that learns to assign weights to different experts, allowing for a weighted combination of their outputs based on the input features. Due to space limitations, we will detail the implementation of the top-K MoE module in the revised paper.\n\nWe train the model with this Top-K MoE module using the same settings as our proposed method (detailed in Section 5) and compare it against the switching mechanism (\"Switching\"). The models are evaluated on CVRP100 instances with the capacity values $C \\in${10,50,100,200,300,400,500}. As shown in Table 3, while the Top-K MoE approach is conceptually appealing, the simpler switching mechanism achieved superior performance across most tightness regimes, resulting in a lower overall average gap (Switching: 1.86\\% vs. Top-K: 2.17\\%). Given these empirical results, we select the more performant switching mechanism. \n\n\nTable 3: Comparison of our switching mechanism against a learnable Top-K MoE gating mechanism on CVRP100 instances\n||CVRP100||||||||\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n||C=10|C=50|C=100|C=200|C=300|C=400|C=500|Varying Capacities|\n||Gap|Gap|Gap|Gap|Gap|Gap|Gap|Avg.Gap|\n|Top-K|**1.48\\%**|4.58\\%|4.49\\%|1.94\\%|1.07\\%|0.77\\%|**0.83\\%**|2.17\\%|\n|Switching|1.54\\%|**3.82\\%**|**3.67\\%**|**1.49\\%**|**0.87\\%**|**0.75\\%**|0.87\\%|**1.86\\%**|\n\n\nFurthermore, we would like to respectfully emphasize that a primary contribution of this work is the identification and systematic analysis of the constraint tightness-overfitting problem in existing NCO methods. While our proposed solution is straightforward, it effectively addresses this newly highlighted issue. We believe our finding and method provide valuable insights that can inspire interesting future works, including the development of more sophisticated, continuously generalized policies.\n\n[1] MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts, ICML2024.\n\n\n\n\n\n\n> **C2. The specific definition of \"constraint tightness\", while effective for the Capacitated Vehicle Routing Problem (CVRP) and CVRP with Time Windows (CVRPTW), might be too problem-specific. This could limit the universality and direct applicability of the proposed multi-expert architecture and training scheme to other types of Combinatorial Optimization Problems (COPs) or even more diverse VRP variants with different or more complex constraint structures, thus potentially reducing its overall generalizability beyond the explored VRP contexts.**\n\n\n> **Q2.The definition of \"constraint tightness\" is effectively applied to CVRP and CVRPTW. However, how can this specific definition and the proposed multi-expert framework be universally applied or adapted to other types of Combinatorial Optimization Problems (COPs) or more diverse VRP variants with qualitatively different or more complex constraint structures (e.g., time windows for specific deliveries, vehicle type constraints, dynamic capacities)?**\n\nThank you very much for your constructive comment. We acknowledge that our current definitions of \"constraint tightness\" for capacity and time windows are tailored to the specific VRP variants studied in the paper. Nonetheless, we would like to make the following clarification to discuss the generalizability of applying these two constraints and their tightness to other VRP variants.\n\n\n**1. Generalizability of Capacity and Time Windows Constraint Tightness**\n\nWe respectfully argue that capacity and time windows are two of the most fundamental and ubiquitous constraints in the entire field of vehicle routing. Their presence is standard in a vast array of VRP variants. Therefore, a method that robustly handles the tightness spectrum of these core constraints already possesses significant potential for broad applicability.\n\n\n\n**2. Empirical Validation on More Complex VRP Variants**\n\n\nTo empirically test the universality of our framework, we conducted new experiments on more complex VRP variants: the Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW) and the Vehicle Routing Problem with Backhauls, Duration Limit (L), and Time Windows (VRPBLTW). These problems introduce additional structural constraints (backhaul and duration limit) on top of the standard capacity and time window constraints. We applied our proposed method (VCT training and the MEM module) to the time window constraint in these new, more complex settings, using POMO as the base model. We follow [1] to configure the settings of additional constraints, backhaul, and duration limit.\n\nThe results presented in Table 4 demonstrate the effectiveness of our approach. From the table, we can observe that the standard POMO model once again suffers from severe performance degradation as the time window constraint moves to be either tighter or looser than the standard $\\alpha=1.0$. In contrast, our enhanced model (POMO + our method) significantly mitigates this issue, maintaining much more stable and superior performance across the entire tightness spectrum.\n\n\n\nTable 4: Performance on Complex VRP Variants (i.e., VRPBTW and VRPBLTW) with Varying Time Window Tightness. \"Gap\" represents the performance gap between the model and OR-Tools.\n||VRPBTW100||||||||\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n||alpha=0.2|alpha=0.5|alpha=1|alpha=1.5|alpha=2|alpha=2.5|alpha=3|VaryingTimeWindows|\n||Gap|Gap|Gap|Gap|Gap|Gap|Gap|Avg.Gap|\n|POMO|18.81\\%|13.35\\%|**8.46\\%**|12.12\\%|19.42\\%|30.27\\%|43.96\\%|20.91\\%|\n|POMO+Our Method|**13.23\\%**|**11.97\\%**|9.34\\%|**8.67\\%**|**9.07\\%**|**8.80\\%**|**9.11\\%**|**10.03\\%**|\n||||||||||\n||**VRPBLTW100**||||||||\n||alpha=0.2|alpha=0.5|alpha=1|alpha=1.5|alpha=2|alpha=2.5|alpha=3|VaryingTimeWindows|\n||Gap|Gap|Gap|Gap|Gap|Gap|Gap|Avg.Gap|\n|POMO|18.90\\%|13.32\\%|**8.29\\%**|11.42\\%|17.06\\%|23.73\\%|31.16\\%|17.70\\%|\n|POMO+Our Method|**13.00\\%**|**11.80\\%**|9.09\\%|**8.42\\%**|**8.92\\%**|**8.45\\%**|**8.56\\%**|**9.75\\%**|\n\n\n\nThese results suggest that our framework is not a fragile solution limited to simple problems. Instead, it can function as a robust and adaptable sub-system. It can be integrated into solvers for more complex problems to specifically handle the challenge of varying constraint tightness, without conflicting with the logic required for other constraints. We hope this work brings attention to the critical issue of constraint tightness in the NCO community and inspires future research to develop diverse strategies for this challenge across a wider range of combinatorial optimization problems. \n\n\nThank you again for your time and effort dedicated to reviewing our work. We will carefully add the above important discussion and the new experimental results to our revised paper. We sincerely hope that our responses have effectively addressed your concerns."}, {"review_id": "c56YWhDXsO", "reviewer": "Reviewer_H9mr", "summary": "This study focuses on capacitated vehicle routing problems (CVRP) and aims to improve the generalization performance of neural solvers with respect to the tightness of capacity constraints. Based on the hypothesis that existing methods fail to generalize because they are trained only on instances with a single capacity constraint, the authors propose training on instances with various capacity constraints. Experimental results demonstrate that this approach improves generalization performance regarding constraint tightness. Additionally, the introduction of a multi-expert module is shown to produce solutions with shorter route lengths.", "questions": "I would appreciate it if the authors could answer the following questions.\n- Could you provide a formal definition of constraint tightness as used in the paper?\n\n- Besides the experimental results presented, do you have other evidence supporting the claim that existing methods overfit to capacity constraints?\n\n- Between VCT and MEM, which component contributes more to the performance improvement?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- The paper demonstrates that a simple approach of changing the training data from instances with a single capacity constraint to instances with multiple capacity constraints improves generalization performance with respect to capacity constraint tightness.\n\n- Based on the observation that the structure of solutions differs depending on the tightness of capacity constraints, the authors introduce a multi-expert module and show that it further shortens route lengths beyond what can be achieved by changing the training data alone.\n\n**Weaknesses**\n\n- The paper has several issues regarding clarity. First, definitions of key terminology are missing. For example, “constraint tightness,” a central concept in the paper, is not clearly defined. Second, the problem setting itself is not clearly described. In many CVRP formulations, the number of vehicles is part of the problem instance (i.e., given). In such settings, feasibility cannot be determined solely based on vehicle capacity. This affects the observation in Section 4.1 that solution characteristics change depending on constraint tightness.\n\n- The paper lacks sufficient experimental justification for why existing methods have limited generalization performance with respect to constraint tightness. For example, an analysis of whether the solution structure (e.g., the number of vehicles used, or the number of nodes visited per vehicle) changes significantly when the capacity varies would strengthen the claim that existing models are overfitting to capacity constraints.\n\n- The ablation study is incomplete. Table 4 reports results for the base model, base model + VCT, and base model + VCT + MEM, but does not include results for the base model + MEM. To clarify the contribution of VCT versus MEM, I recommend reporting the performance of the base model + MEM as well.", "was_revised": true, "final_justification": "This paper addresses the issue of overfitting to the degree of constraint tightness present in the training data, an important limitation of neural network–based combinatorial optimization solvers.\nThe proposed method is simple, yet its effectiveness is demonstrated empirically.\nMy initial concerns regarding the definition of constraint tightness, the inclusion of ablation studies, and the clarity of the problem setting have been largely resolved through the rebuttal process.", "rebuttal": "Dear Reviewer H9mr,\n\nThank you very much for taking the time and effort to review our work. We are delighted to know that you find our paper to demonstrate a simple approach that can improve model generalization performance with respect to constraint tightness, and that our introduction of a multi-expert module further provides additional performance gains.\n\nWe address your concerns point-by-point as follows.\n\n> **C1. The paper has several issues regarding clarity. First, definitions of key terminology are missing. For example, “constraint tightness,” a central concept in the paper, is not clearly defined.**\n\n> **Q1. Could you provide a formal definition of constraint tightness as used in the paper?**\n\nThank you very much for these valuable comments. We apologize for not providing a clear, formal definition of constraint tightness in the submitted version. In response to your comment, we would like to provide the formal definition as follows.\n\n**1. Definition of Constraint Tightness:**\n\nIn this paper, “constraint tightness” is a metric used to quantify the degree of restriction imposed by a specific constraint in a combinatorial optimization problem. \n\nA higher degree of tightness implies that the constraint more severely limits the feasible solution space, making the problem more restricted. For example, in CVRP, an extremely tight constraint—such as a capacity so small that a vehicle can only serve one customer—dramatically shrinks the solution space to a single, fixed solution. Conversely, a lower degree of tightness implies that the constraint is less restrictive, allowing for greater flexibility in the solution space. For example, when the vehicle capacity is large enough to serve all customers, this loose constraint effectively transforms the problem into TSP, causing the solution space to explode to a factorial size with respect to the total number of customer nodes.\n\nTo be more specific, we implement this concept for the two vehicle routing problems studied in our paper as follows:\n\n**2. For the Capacitated Vehicle Routing Problem (CVRP):**\n\nThe “constraint tightness” is directly represented by the vehicle capacity value, $C$.\n\n+ A tight constraint corresponds to a low capacity value (e.g., $C=10$ in our paper). In this scenario, each vehicle can only serve a very limited number of customers, forcing the solution to be composed of many short sub-tours.\n+ A loose constraint corresponds to a high capacity value (e.g., $C=500$). Here, the capacity is so large that it is barely a limiting factor, allowing a single vehicle to serve many or all customers. This makes the problem characteristics approach those of TSP.\n+ Therefore, in the context of CVRP, constraint tightness is inversely proportional to the vehicle capacity $C$.\n\n**3. For the CVRP with Time Windows (CVRPTW):**\n\nThe “constraint tightness” refers to the strictness of the customer service time windows. As detailed in Appendix E of our paper, we introduce a coefficient, $\\alpha$, to quantify this.\n\n+ We use the following equation to relax or tighten each customer's original time window $[e_i, l_i]$ to the new time window $[e_i',l_i']$: $  e_i' = \\max(e_i + \\delta,0),l_i' = l_i - \\delta, \\text{where} \\ \\delta = \\frac{l_i-e_i}{2} \\cdot (1 - \\alpha)$.\n+ A tight constraint corresponds to a small $\\alpha$ value (e.g., $\\alpha=0.2$). This significantly narrows the permissible service time window for each customer, increasing the difficulty of finding a feasible route.\n+ A loose constraint corresponds to a large $\\alpha$ value (e.g., $\\alpha=3.0$). This relaxes the time window constraints, providing more flexibility in routing.\n+ Therefore, for CVRPTW, the tightness of the time window constraint is inversely proportional to the coefficient $\\alpha$.\n\n> **W2. Second, the problem setting itself is not clearly described. In many CVRP formulations, the number of vehicles is part of the problem instance (i.e., given). In such settings, feasibility cannot be determined solely based on vehicle capacity. This affects the observation in Section 4.1 that solution characteristics change depending on constraint tightness.**\n\nThank you very much for this valuable comment. We apologize for not making the number of vehicles in the problem setting sufficiently clear. We would like to clarify that our work assumes an unlimited fleet of homogeneous vehicles for each problem instance, which follows the classical VRP formulation used in seminal NCO papers [1, 2]. We will carefully revise Section 2.1 (Problem Definition) in our paper to explicitly state this assumption.\n\n[1] Attention, learn to solve routing problems! ICLR, 2019.\n\n[2] Pomo: Policy optimization with multiple optima for reinforcement learning. NeurIPS, 2020.\n\n> **W3. The paper lacks sufficient experimental justification for why existing methods have limited generalization performance with respect to constraint tightness. For example, an analysis of whether the solution structure (e.g., the number of vehicles used, or the number of nodes visited per vehicle) changes significantly when the capacity varies would strengthen the claim that existing models are overfitting to capacity constraints.**\n\n> **Q2. Besides the experimental results presented, do you have other evidence supporting the claim that existing methods overfit to capacity constraints?**\n\nThank you very much for your insightful and constructive comment. To provide other evidence supporting our claim, we conduct an analysis focusing on a key aspect of the solution structure: the average number of vehicles used. We compare the solutions generated by three representative neural solvers (POMO, BQ, and LEHD), all pre-trained on CVRP100 instances with C=50, against the (near)-optimal solutions from the classical HGS solver. The evaluation is performed on datasets with varying capacities (C = 10, 50, 100, 500). The results presented in Table 5 show the average number of vehicles used by each method and the percentage gap in the number of vehicles relative to the HGS baseline.\n\nTable 5: Comparison of average number of vehicles used across different capacities\n||C=10||C=50||C=100||C=500||\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|Method|Avg. Vehicle Num.|Vehicle Num. Gap|Avg. Vehicle Num|Vehicle Num. Gap|Avg. Vehicle Num|Vehicle Num. Gap|Avg. Vehicle Num|Vehicle Num. Gap|\n|HGS|53.19|0.00\\%|10.44|0.00\\%|5.44|0.00\\%|1.44|0.00\\%|\n|POMO|57.18|7.50\\%|10.66|**2.11\\%**|6.21|14.15\\%|3.73|159.03\\%|\n|BQ|56.84|6.86\\%|10.62|**1.72\\%**|5.61|3.13\\%|1.91|32.64\\%|\n|LEHD|65.43|23.01\\%|10.95|**4.89\\%**|5.86|7.72\\%|1.94|34.72\\%|\n\nFrom these results, we can observe that the gap in the average number of vehicles used by the neural models, relative to the HGS baseline, is minimized at C=50. As the capacity deviates from this training value, i.e., becoming either tighter (C=10) or looser (C=100, 500), the gap increases substantially. For example, the gap for LEHD at C=10 and C=500 is 4.7x and 7.1x larger, respectively, than its gap at C=50. \nThis demonstrates that when faced with instances requiring a fundamentally different solution structure (e.g., $\\approx$53 vehicles for C=10 or $\\approx$1 vehicles for C=500), the models fail to adapt. They generate solutions with a suboptimal number of vehicles, which directly contributes to the higher overall travel costs reported in our main paper.\n\n \n> **W3. The ablation study is incomplete. I recommend reporting the performance of the base model + MEM as well.**\n\n> **Q3. Between VCT and MEM, which component contributes more to the performance improvement?**\n\nThank you very much for this constructive comment. We agree with you that including the \"Base Model + MEM\" configuration is essential for a complete ablation study and for clearly isolating the individual contributions of VCT and MEM.\n\nFollowing your suggestion, on top of Table 4 in the main paper, we have added the ablation study on the effect of MEM. We train the base model with the Multi-Expert Module (MEM) but without Varying Constraint Tightness (VCT) training, that is, the model was trained exclusively on CVRP100 instances with a fixed capacity of C=50. We then evaluated its performance on the same test sets. The complete results are presented in the updated table below.\n\nFrom these comprehensive results, we can observe that:\n\n+ **Base Model + MEM:** Adding only the MEM reduces the average gap from 10.78\\% to 8.95\\%. This shows that the MEM provides a modest benefit, likely by improving performance on the in-domain (C=50) and nearby capacities.\n+ **Base Model + VCT:** Adding only VCT training leads to a dramatic improvement, reducing the average gap from 10.78\\% to just 2.41\\%. This demonstrates that exposing the model to a wide range of constraint tightnesses during training is the primary driver of generalization.\n\n\nTherefore, these results clearly show that VCT contributes significantly more to the overall performance improvement than MEM does. The role of MEM is to further refine the generalized policy learned via VCT, leading to the best overall performance (1.86\\% average gap).\n\nTable 6: Effects of Varying Constraint Tightness training (VCT) and Multi-Expert Module (MEM). The Base Model is only trained on instances with C=50 and without MEM.\n||CVRP100||||||||\n|-|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n||C=10|C=50|C=100|C=200|C=300|C=400|C=500|Varying Capacities|\n||Gap|Gap|Gap|Gap|Gap|Gap|Gap|Avg.Gap|\n|Base Model|45.64\\%|3.72\\%|4.21\\%|3.62\\%|5.61\\%|5.36\\%|7.29\\%|10.78\\%|\n|Base Model+MEM|37.03\\%|**3.28\\%**|4.41\\%|2.90\\%|4.56\\%|4.39\\%|6.11\\%|8.95\\%|\n|Base Model+VCT|1.88\\%|4.51\\%|4.69\\%|2.25\\%|1.28\\%|1.03\\%|1.25\\%|2.41\\%|\n|Base Model+VCT+MEM|**1.54\\%**|3.82\\%|**3.67\\%**|**1.49\\%**|**0.87\\%**|**0.75\\%**|**0.87\\%**|**1.86\\%**|\n\n\nThank you again for your time and effort dedicated to reviewing our work. We will carefully incorporate the above discussions into our revised paper. We sincerely hope that our responses can effectively address your concerns."}, {"review_id": "Tpz1NxEImn", "reviewer": "Reviewer_acR7", "summary": "This paper systematically identifies and addresses a critical limitation in existing NCO models: overfitting to fixed constraint tightness. The proposed multi-expert module technique is sound, empirically effective, and practically applicable. Despite some minor shortcomings (e.g., lack of efficiency analysis), the work is of high quality and makes a meaningful contribution to the NCO literature.", "questions": "1.\tHave you considered the impact of the node demand distribution? Most neural methods simply employ uniform node demands, which means that the capacity constraint is just counting the number of visited nodes. If the node demands were drawn from a more heterogeneous distribution, would the performance of current methods be similarly affected or further compromised?\n\n2.\tDoes the overfitting issue discussed in the context of VRPs also manifest in other combinatorial optimization problems?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. This paper, for the first time, reveals that many NCO methods tend to overfit a certain degree of constraint tightness, which is a critical yet underexplored limitation. This insight represents a meaningful and timely contribution to the field.\n\n2. The proposed multi-expert module is conceptually simple yet empirically effective, significantly enhancing the model's capacity to handle varying levels of constraint tightness. Furthermore, the authors demonstrate that this modular design can be seamlessly integrated into a broad range of backbone architectures, indicating its versatility and general applicability.\n\n3. The paper provides a comprehensive empirical evaluation, including experiments across multiple models, varying constraint levels, and different problem variants. In addition, the inclusion of ablation studies and problem similarity analyses offers strong empirical support for the paper’s central claims.\n\nWeaknesses:\n1. The proposed training approach assumes prior knowledge of the constraint tightness range $[C_{min}, C_{max}]$, but there is little discussion about how to determine this range in practical applications. \n\n2. While the proposed multi-expert module improves performance, its additional computational cost is not analyzed or quantified.", "was_revised": true, "final_justification": "This paper is the first to reveal the overfitting issue of neural methods with respect to constraint tightness (e.g., vehicle capacity and time window tightness), and proposes well-motivated solutions that empirically mitigate this problem. This contribution is both significant and timely for the field of neural combinatorial optimization.\n\nMy earlier concerns primarily pertained to the generalizability of the conclusions. The authors' rebuttal convincingly demonstrates that their findings extend to other constraint-related features (e.g., node demand) and to other constrained combinatorial optimization problems beyond the VRP, which has effectively addressed my concerns.", "rebuttal": "Dear Reviewer acR7,\n\nThank you very much for taking the time and effort to review our work. We are delighted that you find that our paper is the first to reveal the critical yet underexplored limitation that NCO methods tend to overfit a certain degree of constraint tightness, representing a meaningful and timely contribution, and that our comprehensive empirical evaluation provides strong support for the paper's central claims.\n\nWe address your concerns point-by-point as follows.\n\n> **W1. There is little discussion about how to determine the constraint tightness range [$C_{min}$, $C_{max}$] in practical applications.**\n\nThank you very much for your valuable comment. We would like to provide a detailed discussion about how to determine this range in practical applications. \n\n**1. Determining the Range in Practical Applications**\n\nIn practical applications, a direct and effective method is to analyze historical operational data. For example, a logistics company could derive an empirical range that reflects its specific business characteristics by statistically analyzing the vehicle capacities and total customer demands from its past tasks.\n\n**2. Rationale for the Range Selection in Our Paper.**\n\nThe primary motivation for selecting the range [10, 500] is to comprehensively cover the entire spectrum of the CVRP100 problem's characteristics. **(a) Lower Bound $C_{min}=10$:** This value is set to simulate a tight constraint scenario. In our experimental setup, customer demands are uniformly distributed in {1, ..., 9}$. C=10 means a vehicle can serve only two customers on average, pushing the problem to the brink of feasibility. **(b) Upper Bound $C_{max}=500$:** This value is set to simulate a loose constraint scenario. For a CVRP100 instance with 100 customers and an average demand of 5, the total expected demand is 500. When the capacity approaches this value, the capacity constraint becomes nearly irrelevant. This range is crucial for thoroughly analyzing and addressing the overfitting issue of NCO models under varying constraints.\n\n**3. Representativeness of the Chosen Range on Real-World Benchmarks**\n\nTo validate that our chosen range holds practical relevance, we analyze 192 instances from the classic CVRPLIB benchmarks (A, B, E, F, M, P, and X sets). We find that across these real-world instances, the number of customers served by a single vehicle ranges from a minimum of 2 to a maximum of 27 on average. In our experimental setting, a vehicle can serve between 2 (for $C=10$) and 100 (for $C=500$) customers. This quantitative evidence shows that our selected range is not only conceptually comprehensive but also highly representative of real-world application scenarios.\n\n\n\n> **W2. While the proposed multi-expert module improves performance, its additional computational cost is not analyzed or quantified.**\n\nThank you very much for this constructive comment. To quantify the additional computational cost of the multi-expert module (MEM), we record the inference time and optimality gap for our model with and without the module, with the results presented in Table 7 below.\nFrom these results, we can observe that incorporating the MEM reduces the average optimality gap from 2.41\\% to 1.86\\%, which constitutes a relative performance improvement of 23\\%. We acknowledge that this performance gain is accompanied by a moderate increase in inference time (from 0.67 min to 0.96 min). However, we believe that this trade-off is acceptable. As shown in Table 8, when compared to two recent methods like BQ and INViT, our model is not only more accurate but also faster. \n\nTable 7: Impact of the Multi-Expert Module (MEM) on Performance and Inference Time.\n||CVRP100 （Varying Capacities）||\n|-|:-:|:-:|\n||Avg. Gap|Avg. Time|\n|Ours without MEM|2.41\\%|0.67m|\n|Ours with MEM|**1.86\\%**|0.96m|\n\n\n\nTable 8: Total Inference time of baseline models for solving 10,000 CVRP100 instances.\n|  | CVRP100 （Varying Capacities） |  |\n|---|:---:|:---:|\n|  | Avg. Gap | Avg. Time |\n| BQ | 7.22\\% | 1.8m |\n| INViT | 13.28\\% | 2.6m |\n| Ours | **1.86\\%** | 0.96m |\n\n\n> **Q1. Have you considered the impact of the node demand distribution? If the node demands were drawn from a more heterogeneous distribution, would the performance of current methods be similarly affected or further compromised?**\n\nThank you very much for raising this insightful question. While we did consider the factor of the distribution of node demands in our initial experimental design, we made a deliberate choice to isolate a single variable—vehicle capacity—for our study. This approach allows us to clearly and rigorously demonstrate the constraint overfitting issue inherent in existing methods. \n\nA heterogeneous demand distribution would likely pose an even greater challenge. We conduct an experiment to validate this. We generate a new test dataset where customer demands follow a more realistic heterogeneous distribution: a long-tailed distribution. We choose this distribution because, in many real-world applications (such as e-commerce and parcel delivery), the majority of customers have small demands, while only a few have very large demands. Specifically, in the long-tailed distribution, each possible demand value $d\\in$ {1, 2, 3, 4, 5, 6, 7, 8, 9}, and its probability of occurrence $P(d)$ is given by the formula below:\n\n$$P(d) = \\frac{\\frac{1}{d^\\delta}}{\\sum_{i=1}^{9} \\frac{1}{i^\\delta}}$$\n\nwhere the hyperparameter $d=1.5$ controls the skewness of the distribution. The specific probabilities for each demand value are shown in Table 9:\n\nTable 9: Probabilities of demand values under a long-tailed distribution\n|demand(d)=|1|2|3|4|5|6|7|8|9|\n|-|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|P(d)=|0.5092|0.1800|0.098|0.0637|0.0455|0.0346|0.0275|0.0225|0.0189|\n\n\nOn this basis, we evaluate the performance of several NCO models across different scenarios. These models are pre-trained on instances with a uniform demand distribution (C=50, CVRP100). The test scenarios include: **(a) Fixed Capacity (C=50):** Tested under both uniform and long-tailed demand distributions. **(b) Varying Capacities:** Capacity $C$ is drawn from the set {10, 50, 100, 200, 300, 400, 500}, also tested under both uniform and long-tailed demand distributions. The experimental results are shown in Table 10.\n\nTable 10: Impact of demand distribution on existing models' performance.\n||CVRP100||||\n|:-:|:-:|:-:|:-:|:-:|\n||C=50|C=50|Varying Capacities|Varying Capacities|\n||Uniformed Demand|Long-Tailed Demand|Uniformed Demand|Long-Tailed Demand|\n|Method|Gap|Gap|Avg.Gap|Avg. Gap|\n|HGS|0.00\\%|0.00\\%|0.00\\%|0.00\\%|\n|AM|**7.66\\%**|14.10\\%|23.76\\%|**23.58\\%**|\n|POMO|**3.66\\%**|12.16\\%|**21.72\\%**|26.04\\%|\n|MDAM|**5.38\\%**|13.71\\%|**16.75\\%**|19.41\\%|\n|BQ|**3.25\\%**|3.53\\%|**7.22\\%**|7.39\\%|\n|LEHD|**4.22\\%**|4.54\\%|9.62\\%|**7.98\\%**|\n|ELG|**5.24\\%**|11.29\\%|**16.29\\%**|18.92\\%|\n|INViT|**7.85\\%**|12.31\\%|**13.28\\%**|13.87\\%|\n|POMO-MTL|**4.50\\%**|6.93\\%|**11.41\\%**|12.76\\%|\n|MVMoE|**5.06\\%**|8.53\\%|**17.24\\%**|19.29\\%|\n\n\nThe results clearly show that under the fixed capacity (C=50) setting, when the demand distribution shifts from uniform to long-tailed, almost all evaluated NCO models experience a significant performance degradation. For instance, POMO's gap drastically increases from 3.66\\% to 12.16\\%. Under the varying capacities setting, most models also exhibit a trend of performance decline. These experimental results strongly confirm that the performance of existing models is substantially compromised under more realistic and challenging heterogeneous demand distributions.\n\n\n> **Q2. Does the overfitting issue discussed in the context of VRPs also manifest in other combinatorial optimization problems?**\n\nThank you very much for this insightful question. The overfitting issue with respect to constraint tightness, which we discuss in the context of VRPs, does indeed manifest in other combinatorial optimization (CO) problems, such as the Knapsack Problem (KP) with its capacity limit and the Bin Packing Problem (BPP) with bin capacities.\n\nTo validate this, we conduct a case study on KP. Following the setup of POMO, we generated KP200 instances with varying capacities: $C \\in$ {2, 5, 10, 25, 50}. We then evaluate two representative models, POMO and BQ, using their publicly available checkpoints that are trained specifically on KP200 instances with a fixed capacity of C=25. Both models used greedy search for inference. The results are presented in Table 11.\n\n\nTable 11: Performance of baseline NCO models on KP200 instances with different capacities. The larger the value is, the better the model performs.\n||KP200||||||||||\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n||C=2||C=5||C=10||C=25||C=50||\n|Method|Value|Gap|Value|Gap|Value|Gap|Value|Gap|Value|Gap|\n|OR-Tools|16.157|0.000\\%|25.723|0.000\\%|36.467|0.000\\%|57.665|0.000\\%|81.163|0.000\\%|\n|POMO|9.673|40.132\\%|23.539|8.488\\%|34.428|5.590\\%|57.393|**0.472\\%**|79.855|1.611\\%|\n|BQ|15.653|3.119\\%|25.546|0.686\\%|36.369|0.269\\%|57.611|**0.094\\%**|80.624|0.664\\%|\n\nAs shown in the table, the performance of both POMO and BQ degrades significantly as the capacity C deviates from the training value of 25. For the tight constraint C=2, the POMO model's gap explodes to 40.132\\%, an 85$\\times$ increase compared to its performance at C=25. Similarly, the BQ model's gap at C=2 is 33$\\times$ larger than its gap at C=25. When the constraint becomes looser at C=50, the performance drop is also evident, with the gaps for POMO and BQ increasing by 3.4$\\times$ and 7$\\times$, respectively. These experimental results on KP strongly demonstrate that the constraint overfitting issue also occurs in other CO problems, extending beyond VRPs.\n\n\nThank you again for your time and effort dedicated to reviewing our work. We will carefully incorporate the above discussions into our revised paper. We sincerely hope that our responses can effectively address your concerns."}]

Author rebuttal:

Meta-review: This paper clearly surfaces an overlooked issue in NCO—dependence on constraint tightness—and substantiates it with systematic analyses on CVRP/CVRPTW. The proposed training scheme and multi-expert module are empirically persuasive across variants. Most reviewers are positive (two Accepts, one Borderline-Accept). One reviewer remains cautious about “truly adaptable policy,” but the authors provided additional experiments and clarified the work’s “rethinking” positioning.

Overall, the novelty, empirical rigor, and expected impact meet the NeurIPS bar. Recommend Accept.
Decision: Accept (poster)