MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver
Authors: Yuepeng Zheng
Fu Luo
Zhenkun Wang
Yaoxin Wu
Yu Zhou
Venue: NeurIPS 2025 poster ()
Keywords: Neural Combinatorial Optimization
Vehicle Routing Problem
Multi-Task Learning
Primary area: optimization
TL;DR: This paper proposes the Multi-Task Learning with Knowledge Distillation (MTL-KD) to train a single heavy decoder model without labeled data to solve various VRP variants.

Abstract: Multi-Task Learning (MTL) in Neural Combinatorial Optimization (NCO) is a promising approach for training a unified model capable of solving multiple Vehicle Routing Problem (VRP) variants. 
However, existing Reinforcement Learning (RL)-based multi-task methods can only train light decoder models on small-scale problems, exhibiting limited generalization ability when solving large-scale problems. 
To overcome this limitation, this work introduces a novel multi-task learning method driven by knowledge distillation (MTL-KD), which enables efficient training of heavy decoder models with strong generalization ability. 
The proposed MTL-KD method transfers policy knowledge from multiple distinct RL-based single-task models to a single heavy decoder model, facilitating label-free training and effectively improving the model's generalization ability across diverse tasks. 
In addition, we introduce a flexible inference strategy termed Random Reordering Re-Construction (R3C), which is specifically adapted for diverse VRP tasks and further boosts the performance of the multi-task model. 
Experimental results on 6 seen and 10 unseen VRP variants with up to 1,000 nodes indicate that our proposed method consistently achieves superior performance on both uniform and real-world benchmarks, demonstrating robust generalization abilities. The code is available at [https://github.com/CIAM-Group/MTLKD](https://github.com/CIAM-Group/MTLKD).

MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver
Yuepeng Zheng"' Fu Luo2,3, Zhenkun Wang?.,, Yaoxin Wa', Yu Zhou
College of Computer Science and Software Engineering. Shenzhen University, Shenzhen, China
2 School of Automation and Intelligent Manufacturing,
Southern University of Science and Technology, Shenzhen, China
3 Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University Science and Technology, Shenzhen, China Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, The Netherlands 20192710248email. szu, edu. en, luof2023@mail. sustech edu. wangzhenkunn90@mmai. com, y. wu2@tue nl, 2houyu_102201228 com
Abstract
Multi-Task Learning (MTL) in Neural Combinatorial Optimization (NCO) is a promising approach for training unified model capable of solving multiple Vehi- cle Routing Problem (VRP) variants. However, existing Reinforcement Learning (RL)-based multi-task methods can only train light decoder models on small-scale problems, exhibiting limited generalization ability when solving large-scale prob- lems. To overcome this limitation, this work introduces novel multi-task learning method driven by knowledge distillation (MTL-KD), which enables efficient train- ing of heavy decoder models with strong generalization ability. The proposed MTL-KD method transfers policy knowledge from multiple distinct RL-based single-task models to single heavy decoder model, facilitating label-free training and effectively improving the model's generalization ability across diverse tasks. addition, we introduce flexible inference strategy termed Random Reordering Re-Coostruuctin (R3C), which is specifically adapted for diverse VRP tasks and further boosts the performance the multi-task model. Experimental results on 6 seen and 10 unseen VRP variants with up to 1,000 nodes indicate that proposed method consistently achieves superior performance on both uniform and real- world benchmarks, demonstrating robust generalization abilities. The code is available at httpss//gthub.com/CAAM Aatpghuhu....ooCAAAAGGoGoAAAAA Group/MTLKD
Introduction
The Vehicle Routing Problem (VRP) is a classical combinatorial optimization problem (COP) with widespread application across numerous real-world scenarios, including logistics distribution, traffic scheduling, and emergency response 3 Obtaining exact VRP solutions is computationally difficult due to its NP-hard nature (6). Traditional heuristic algorithms [7-9] exhibit superior performance many classic VRP tasks. However, they typically necessitate substantial domain-specifie knowledge for design. In recent years, neural combinatorial optimization (NCO) (10-20] has emerged
"qqual contributors CCorresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

promising approach for tackling VRPs. This approach can automatically learn groblem-solving strategies using neural networks and has the potential to minimize reliance on specialized domain knowledge. This field has developed rapidly, with some NCO algorithms approaching or even surpassing the performance of classical heuristic algorithms on some COPs [21 22] However, when solving different tasks, many NCO methods require modifying the model components for each individual task and then retraining the model, which significantly restricts their versatility in handling
diverse VRP variants.
Recently, considerable research efforts have been devoted to developing unified models capable of solving multiple VRP variants using Multi-Task Learning (MTL) [23 [23-25]. The majority of unified models for VRP variants adopt a heavy encoder-light decoder (HELD) architecture. These models have relatively low computational costs and can be directly trained using RL, demonstrating excellent performance on small-scale problems. However, their generalization ability significantly deteriorates when solving with large-scale instances, primarily because the light decoder struggles to extract sufficient information from the high-density and complex node embeddings
26
On the other hand, the light encoder-heavy decoder (27H29 architecture demonstrates excellent generalization capabilities on large-scale problems. Its heavy decoder contributes to its strong scale generalization performance, which re-evaluates the relationships between the remaining nodes and first and last nodes during the iterative decoding process. Leveraging the heavy decoder architecture has the potential to achieve good scale generalization using a multi-task unified model. However, the substantial memory and computational demands inherent in heavy decoders render the model training using Reinforcement Learning (RL. impractical. Employing Supervised Learning (SI.) is
also difficult due to the absence of labeled data for multiple VRP variants. While SIT (2 employs
a self- iif-improved Training method using operations like local reconstruction (27 to refine model-
generated solutions as training labels, it suffers from the generation of numerous low-quality labels during early and mid-training, leading to protracted process and an increased training burden. We provide a comprehensive literature review on multi-task neural solvers for VRPs in Appendix A
To address the limitation associated with the training for the heavy decoder- based model on multiple VRP variants, we introduce a novel multi-task learning method driven by knowledge distillation (MTL-KD). The proposed MTL-KD method transfers policy knowledge from multiple distinct RL--based single-task models to a single heavy decoder model, facilitating label-free training and effectively improving the model's generalization ability across diverse tasks. Furthermore, during inference, we propose a general Random Reordering Reconstruction strategy for various variants of the VRP. By randomly reordering the external order of subtours, R3C significantly enhances solution sampling diversity, mitigates the risk of getting trapped in local optima, and further improves performance. Our contributions are summarized as follows: 1) We achieve efficient label-free training of heavy decoder models for multi-task VRPs through the proposed MTL-KD method. 2) We propose novel R3C strategy to further enhance the performance of the multi-tast model. 3) The MTL-KD model demonstrates excellent performance on 6 seen training tasks and 10 unseen tasks with up to 1,000 nodes, and real-world datasets, exhibiting good scale generalization ability and significantly outperforming existing multi-task VRP models.
2 Preliminaries
Capacitated Vehicle Routing Problem and Its Variants The Capacitated Vehicle Routing Problem (CVRP) is typically defined as follows: Given a central depot up and N customer nodes en to Un, all interconnected with distances eij- Each customer has demand d,, and all vehicles depart from the depot, serve customers, and return to the depot. Each vehicle has a capacity C, satisfying C' > dj. All customers must be visited exactly once, and the total load of the vehicle during its route must not exceed its capacity. The objective of CVRP is to minimize the total travel distance of all vehicles.
By introducing additional constraints, CVRP can be extended into various variants. The four types of additional constraints studied in this paper include: (1) Open Route (O): Vehicles are not required to return to the depot after completing their service. (2) Time Windows (TW): Each node has a service time window [s,, 4t). within which vehicles must arrive at the customer (early arrivals require waiting until the earliest service start time). (3) Backhaul (B): Customer demands can be positive (linehauls) or negative (backhauls), and there is no restriction on the sequence of visiting linehauls and backhauls customers. (4) Duration Limit (L): The total travel distance of each vehicle must not

---

exceed predefined threshold Lthre- Combining these constraints with CVRP can form 16 different VRP variants, with specific details provided in Appendix
Solution Construction Process by Neural Solver Constructive neural solvers [0 27 typically employ an encoder-decoder architecture and construct solutions in an autoregressive manner. For given VRP instance (V; E), where V denotes the of nodes, including node features such as demand, and E represents the set of edges, often formed by a distance matrix. The encoder is used extract node information and generate embedding vectors for each node, while the decoder constructs the next node based on the current partial solution state 9t-1. The decoder is subject to node constraints during the construction process avoid generating infeasible solutions. The entire solving process can be represented as:
To (T()))
II To (arlsss
where is the complete solution, a₂ is the action (node) selected at time step t, is the total number of actions, and Te represents the neural solver parameterized by O. The decoder continuously constructs nodes until all nodes have been visited, forming a complete solution. Through training, the model learns how to effectively select the next node based on the current partial solution, thereby optimizing the quality of the entire solution.
Knowledge distillation Knowledge Distillation 30 is model compression and knowledge trans- fer technique aimed at transferring the knowledge learned by a high-performing, pre-trained teacher model to a smaller student model. The core idea to achieve this transfer by minimizing the discrepancy between the outputs of the teacher and student models. The student model's training loss typically includes a distillation loss (CKD) that measures the difference between the student's 's predic- tions and the teacher's 's soft targets, generally the KL divergence LKD KL( (ss). Additionally, depending on the specific task requirements, an original task loss (Lrask) can optionally be included, and the total loss (L) for the student model can be expressed as:
== aLDD + (1 a) Caskk
where a is weight parameter. In the field of NCO, knowledge distillation has been used achieve model lightweighting and can improve the generalization ability of models on unseen problems to certain extent 31 B4].
3 Multi-Task Learning Via Knowledge Distillation
In this section, we propose a multi-task learning framework via knowledge distillation to address the challenge of applying heavy decoder models in the multi-task domain due to their reliance large amounts of labeled data. The proposed framework effectively enhances the model's generalization capabilities across different tasks and scales.
3.1 Framework Overview
Our proposed multi-task training framework via knowledge distillation aims to enhance the model's generalization capabilities across different tasks and scales. As depicted Figure [ the frame- work first categorizes VRP variants into seen and unseen tasks for model training. Given N seen tasks, we first pre-train N individual teacher models employing a Heavy Encoder-Light Decoder architecture [ Subsequently, construct multi-task heavy decoder student model and train using knowledge distillation, leveraging the output distributions the teacher models as supervision signals.
3.2 Teacher Model Training
For each seen VRP variant task, we first generate the corresponding instance data. Then, we independently train a teacher model for each task, which adopts the POMO [ structure and serves as policy network. We optimize the parameters of the teacher models using the policy
3

---

OVRP
VRPLTW OVRPBL
VRPOL VRPOTW
KD Loss
VEPB
OVEPRTW
Update
OVRPLTW
Teacher
OVRPTW
OVRFOLIWE
VRPBLTW
Model
Soen Task
Unseen Task
CVRP
6 cvr
CVRP
CVRP
CVRP
Sample
CVRP
cup
Student Model
VRPTW
6"
upti
VRPTW
VRPTW
VRPTW
VRPTW
urphr
Step
Teacher Training
Student Training
Figure 1: Framework for Multi-Tash Training via Knowledge Distillation. Top-left: seen and unseen tasks. Bottom-left: Independent training of teacher models. Right: Student model distillation via teacher output distributions.
gradient method in RL, with the objective of maximizing the reward (negative tour length). The loss function 35 can be expressed as:
[(e") = - (10)((()))))) bb) log क (r(9)),
where 12 (9) is the baseline (average reward of multi-start trajectories for the instance), Tar the teacher model's policy distribution, 0" represents the parameters of the teacher model, and the reward.
3.3 Student Model Training
During the training phase of the student model, we employ a multi-task heavy decoder architecture that processes instances from all M seen problem types simultaneously. For each training batch, we generate instances from all M seen problem types and process them together. each decoding step t, the student model parameterized by @ outputs a probability distribution Tgs (aglse, 9) over the next node to be selected.
For knowledge distillation, feed each problem instance its corresponding pre-trained teacher model parameterized by 0T m E (1,..., M) obtain the teacher's output distribution T.. (0r1 9) at the same decoding step, ensuring that each problem instance is supervised by its corresponding specialized teacher model.
The knowledge distillation loss at training step is computed as the Kullback-Leible divergence between the student model's output distribution and the corresponding teacher model's output distribution:
M
Σ m=1
KL(TTT (1l 9)).
KD
By minimizing this loss function, the student model learns to mimic the behavior of multiple teacher models simultaneously, thereby acquiring generalized knowledge from different problem types. After each decoding step, algorithm selects the next node based on the student model's probability distribution, transitions to the new state, and repeats this knowledge distillation process.

---

Architecture of Generalizable Multi-Task Neural Solver
Heavy decoder models have demonstrated remarkable scale generalization performance on single- task VRP. However, existing multi-task models for VRP variants predominantly rely on heavy encoder-light decoder architectures, exhibiting poor scale generalization, To address this limitation, depicted in Figure[2 we have developed multi-task heavy decoder model specifically designed for VRP variants, aiming to overcome the imadequate generalization capabilities of current approaches.
4.1 Encoder
Given an instance S of the VRP, which includes node features ( S,), in VRP variants, where each node feature is represented as (x;, di, 61, 81,4,, l,), denoting the coordinate information, demand, service time, and the start and end times of the time window, respectively, These node features are then mapped through linear layer to obtain the initial embedding matrix H " (hf .... h h,mit,, where hemit = Linear(s;)) and Linear(.) denotes the linear layer. Subsequently, these initial embeddings are passed through Transformer layer capture node relationships and generate the node embeddings. Therefore, the output of the encoder can be represented as:
Hene = (FL.( = TFL. init
init n
where H/ = (hi" .... he is the matrix of final node embeddings, TFL(-) denote the Trans- former layer, and h, represents the embedding the i-th node.
4.2 Decoder
At the step during the decoding phase, first extract the dynamic features D {1p, tos dr, o). encompassing the remaining vehicle load, current time, remaining route duration, and a binary flag indicating whether the route is open. These dynamic features combined with the last visited node (hrast) and the depot node (hdepor). respectively, and then each combination is passed through its own linear layer. The resulting embeddings. along with the unvisited nodes' embeddings (hunviested). are processed by an L-layer Transformer network to yield updated node embeddings:
( = concat (h one
invisited:: Linear(D D + huse). Linear + depot) ),
(1)) TFL (H Mead)
((.) TFL(H( MPnd).
Here, MMPad_ E {0, > denotes the padding mask, where 0 marks valid positions and -oc marks padded positions. We introduce this mask to handle different numbers of unvisited nodes across batch instances (which affects efficiency): sequences are padded to a unified length by appending depot tokens to shorter sequences and then masked by MPad
Next, we compute compatibility scores between the embeddings of all unvisited nodes and context embedding h, Linear(concat( hast> h (L] depot)) using single-heat attention:
c(h (L) h,)) SHA(h, (4) .h,).
Before selection, we add a padding mask and a feasibility mask to the logits to ensure valid routes. Finally, the probability T(]]s:) of selecting the i-th unvisited node determined by the softmax function applied to the masked compatibility scores:
न (()s,) softmax (c(h)") (.) h,y) + MPPal + M,
(L) hb)) is the compatibility score from SHA, h; (L) is the embedding of the i-th unvisited where c(h!
node, and 8, is the current decoder state. The masks take values in {0, -o0): MPad excludes padded tokens and fess excludes currently infeasible moves.
It is noteworthy that we remove layer normalization from all attention layers 27
5

---

Node embedding
Nest
Dynamic Feature
Aunvisited
Mepor
Dynamic Feature
last nade
depot node
Linner
Linner
Decoder Input Node
Transformrr
x1
Padding mask
Transformer
XN
Linner
Feasibility mask
SHA&Softmax
Padding Mask
Encoder
Decoder
Node Feature
Node Probability
Figure 2: Architecture of the proposed multi-tal task neural solver. Left to right: Encoder, Decoder, Node Padding & Masking.
Original Solution
RRC(Subtour Reversal)
R3C(Subtour Reordering)
Partial Solution
Figure 3: Comparison of RRC and R3C methods. RRC increases the diversity of sampled subprob- lems by randomly reversing subtours, while R3C enhances this diversity by randomly reordering the external sequence of subtours.
Random Reordering Re-Construct
Random Re-Construct (RRC) 27 an iterative method to improve solution quality by randomly sampling and re-optimizing segments of the initial solution. RRC enhances sampling diversity via random subtour reversals and segment lengths. However, reversals can violate feasibility for some problems (e.g., VRPTW), and sampling solely the original sequence limits diversity, hindering iterative performance. We thus propose Random Reordering Re-Construct to increase sampling diversity and improve iterative performance.
The R3C strategy is detailed in Figure 3 Given a solution, we first decompose it into subtours, then randomize their external order in the sequence. Subsequently, random-length contiguous segment randomly sampled and re-optimized by our model. the re-optimized segment improves the objective value, it replaces the original segment. By randomizing subtour order, R3C allows for more random combinations of subtours into partial solutions, aiding escape from local optima and improving iterative performance. All sampled segments end at the depot. Additionally, feasible subtour reversals are also incorporated to further enhance search diversity.
Experiments
In this section, we present series of experiments conducted on 16 VRP variants to validate the performance of our model. All experiments are performed using one NVIDIA RTX 4090 GPU.
Baselines
The baseline methods are categorized into two groups: traditional heuristic solvers and multi-task neural solvers. (1) Traditional Solvers: PyV [36] is an open-source Hybrid Genetic

---

Search --GSs- solver supporting multiple complex VRP variants. It represents the current state-of-the-art in heuristic approaches for the problems considered in this study. OR-Tools [9] is Google's s open-source optimization toolkit, applicable to all VRP variants examined in this study.
(2) Multi-task Neural Solvers: MT-POMO 23 is multi-task extension of the POMO framework, enabling simultaneous learning across different VRP variants. MVMoE (24] is an architecture that enhances model capacity and improves performance over MT-POMO by incorporating Mixture-of- Experts (MoE) modules. RouteFinder [25] is a multi-task training framework that enhances training efficiency through mixed batch training and enables fast adaptation to unseen tasks via lightweight adapter layers. The framework includes three model variants: RF- Transforfrre,, RF-POMO, and RF-MVMoE. CaDA [37] incorporates constraint awareness and a dual-branch structure to better handle diverse tasks within a multi-task learning framework.
Datasets We adopt the same problem settings as MVMoE 24.. We generate a test set comprising 16 VRP problems across four scales: 100, 200, 500, and 1000. The dataset at the 100-scale contains 1,000 instances, while the others contain 128 instances each. In these settings, the vehicle capacity is uniformly set to 50, the duration limit is set to 3, the time window for the depot node in Time Window problems [0, 3.0], and for backhaul problems, the proportion of backhaul nodes is set to 20%. Our datasets are generated based on the MVMoF codebase to evaluate the performance of various baselines.
Training Configuration and Model Parameters We follow a similar setup to MVMoE, training our model on 6 VRPs and evaluating its zero-shot generalization performance on 10 unseen tasks (refer to Figure [T. The training process consists of two phases: teacher model pre-training and student model training- (1) Teacher Model Pre-training: We employ the POMO model as our teacher model. For each of the 6 visible tasks, we independently train a single-task model using reinforcement learning. All teacher models share the same parameter configuration: encoder layers, decoder layer, embedding dimension of 128, 8 attention heads, and a Feedforward hidden dimension of 512. The teacher models are trained for 4000 epochs on random instances of scale 100, with 20,000 training instances per epoch, batch size of 128, and an initial learning rate of 0.0001. (2) Student Model Training: The student model consists of 1 encoder layer and 6 decoder layers, with embedding dimensions set to 128 and 96, employing 8 multi-head attention heads and Feedforward hidden dimension of 512. The student model simultaneously learns from the 6 pre-trained teacher models datasets with problem scale of 100. The training batch size is set to 1500 (250 x 6), with 24,000 training instances per epoch, an initial learning rate of 0.0001, and a total of 850 training epochs. After the 300th epoch, the learning rate is halved every 100 epochs.
Inference and Metrics We adopt the Average Objective Value and Gap as evaluation metrics, where smaller values indicate better performance. The Objective Value represents the total distance of the solution in the Vehicle Routing Problem, while the Gap evaluates the performance difference of each method compared to traditional baseline method (such as HGS-PyVRP).
We test all methods using Single Trajectory Greedy Search (S.T.). Furthermore, to compare with the results of other solvers exploring multiple trajectories under data augmentation (denoted as M Mxaug8, where M is the number of nodes and aug8 represents 8 types of data augmentation [lI), our method employs the R3C strategy with 200 iterations under single trajectory.
6.1 Main Results
Performance on seen Tasks We evaluate the performance of our model on the training tasks. and the results are shown in Table The results demonstrate that our proposed MTL-KD model exhibits excellent performance on the seen training tasks, particularly showeasing a more pronounced advantage when dealing with larger-scale problems. This validates the effectiveness of our proposed knowledge distillation training framework and model architecture.
The zero-shot generalization experimental results on 10 unseen tasks (as shown in Table indicate that our MTL-KD model outperforms the compared models in most cases, demonstrating remarkable cross-task generalization ability, especially with significant advantage on large-scale problems. This validates that multi-task knowledge distillation training endows the model with strong generalization capabilities across different VRP variants.
Performance on Unseen Tasks
7

---

Table I: Performance on seen VRPs across three scales.
represents the baseline used for gap
calculation.
Method
Pro.
Problem Size
Pro.
Problem Size
n=100
n-500
9- 1k
R-100
n-5000
m-1k
HGS-PyVRR
15.53(")
62.07(())
119,54(9)
24.35(*)
90.61(*)
166.47(*)
OR-Tools
15.94(2.65%)
66.5117.15%)
125.9115 32%6
25.21/2 5456)
98.4518.55%)
178.477721166
POMOSS...
16.25(4.64%)
13.64(13.744)
146.92/22 90%
26.66/10.4000
122.61135.500
24%)
(5.79(1.69%)
67.99(9.50%)
136.62(14 28%
25 (5,55115. 18%)
115.43(27.3995
229.82(38.000 (8.88)3)
MVMoEIS T.)
16.30(5.00%%
77.44(2.77%)
191,07(99 83%
26. (4110.41)))
122.78135.28 26633
267. 267.33(60.59)
MYMoE(M-uug))
15.7611.5U5g
73.61(18.5995 599)
40647 57%)
VRPTW
25. 03,5514,777 78
116.67(2K 76
253. 353.35152, 19%)
(5.82(1.88%)
67.7119088%)
132.79(11 08%)
27.39(12.4918
108.70.19.97%%
222,92135
RF-MITOMM0MM+uuE
(5.87().20%%)
67.1218
132,82(11 111)
26.2917.983)
193.57(16.88%) 102.27(1.-283
RF-MV Mo//M
(5.84(2.01%)
(7.36688528)
134 85( 80%)
26.294 9893)
100.78(11 2.22)))))
(87.87(12.868)
CaDacM-augh)
15.84(2.109)
175.65(182 99%)
542. 56(55)879)
50. 86/238888)
300. 100.1 211)
693.61(5166666 669)
MTL-KTaas
16.06(3.415)
64.57(4.025)
123 8813 639))
26 18(7522)5))
(18.17(10.5558
188. 94( (3.500)
MTL-KDD2s
(3.30%)
64.6114.09%)
124.44 (9%))
26.19/73226)
99.0519.315)
184.92111 .05%)
MTL-KDDR3C200m
(5.76(1448)
63.63/2.11%)
122.06 (2.10%)
25.31(3.93%)
96.4366.426)
(81.8(9.24%)
VRT
15:58(*)
63,55(*)
122
9.71(*)
35 3000
66. 11
OR-Tools
16.002 63
67. 67.53(6.269)
1664
9,84 38%)
37,8167.1199
70. 26.38(64885)
MTEPOMONS T.)
16-2944.525)
71,46(12.6685
149, 059.5521,0 90)
10
44.62(26.48))
92.78 36%)
MT-POMMMM=aag5)
(5.85(1.7%%)
(8.9518.495)
27%
10.17(4
11.93(18.7896
85,27129 006+
MVMoBIS. T.)
16.36(4.94%)
78.79(23.9766
192.29155.7455 74%)
90.79(10.9458
48.35(39.815))
135. 301 7016
MF-ThnnsformerMMM.
VRPL
15811145
15.88113 1.93%)
74.67 550%)
68.5917.990 933%)
138.15(10 17%)
177.89(45.00 00%
OVR
10.1144.116)
(0.
42.88(21 48%%)
16.23(30.9755
84, 68%)
116.82 74%)
AV-MTPOMOIM
15.93(..23%)
69.33(7.52%)
134,53/9
70%6)
41.60X
82.14124. 26%)
RF-MYMoE/M+ongS)
15.90)..06%)
68.39(7.62%)
138.60012 98%)
10.13(4
41.18(16.65%)
81.82(23 78%)
CaDa/M-augS)
15.89
176.01(177.00 (11).01%)
S36. 71(337
10. (0.10
187.72/431. 78%)
442.57( 55%)
MTL-KDas
16. (6.1413,58%)
65 65..999)999))
126. 11 79%)
38.7369.728)
72,73(10 035%)
MTL-KDiss
(5.1223)45%)
66(3
10.46/71195
18 18.)1.177))
72,7019
MTL-KINR3CA000
(5.82(1.50%)
64.5246 (1.53%)
(24.59(1.66))
(0.05(A33%)
37.7934 (7.07%)
PRP
13.951
48.15(*)
81.98()
11.97(*)
47.76(*)
88,57(*)
14.38(3.06%)
$2.48(9.00%)
00.0318..0
MT-POMOXM--UU8)
MT-POMONS.))
VRPB
12. (4/00.39)
12.4764.219)
48 (255)
50,0804 85%)
99 (1))5)))))))
95. 95.35((76655)
OVRITW
15. 15.56(11.5395)
14.85 4395)
66: (4(36666)
71.63(48. 76%)
135 833,9))63)878)
147. (4878.168)
MVM T.)
12.42(3.808
71.99(507558)
186,49(110.56 5456)
15,70112 545))
82.81 99%)
215.21 345)
MYMoEMMaag8)
12.0100.31
66,26(38.736)
167.26 (67.26688.88 84%%
14.78/5 9098)
16.28158.4399
195.64( 7666
MTL-KDss
12.39X 3.511
46.12(-3.445)
86 1989)
15.1108
53,74(11.615)
12.122133
MTL-KDus
(2.38(3.415))
35.99)33779%)
86 9.X-1.8%%)
15.00 (8.07%)
53.891119115)
93.96(13 225%)
12. (2.02(0.43%%
44.581-60665
83.56-5.55%)
14.53 (4.12%)
52.8888155%)
92.40K11.38%)
Performance on Real-World Instances We also evaluate the performance of our model on real- world datasets, including Set-X (medium and large scale) from CVRPLIB (38) for CVRP and the Solomon dataset [39] for VRPTW. We compare model against several single-task and multi-task experimentte models, and the experimental results are presented in Tables 6 7 and 8 AppendixD| Our model
consistently outperforms other single-task and multi-task models across all three real-world datasets, demonstrating particularly strong performance on the large-scale Set-X dataset, where the gap is significantly smaller than other baselines. This indicates the strong applicability of our approach to real-world scenarios.
6.2 Ablation Study
Scale Generalization Comparison: Student vs. Teacher While heavy decoders are generally considered to have significant potential for large-scale generalization, the teacher model, POMO, primarily excels at its specific training scale and lacks cross-scale generalization capabilities. This naturally raises a crucial question: Will the student model also be limited to learning knowledge specific to particular scale, thereby restricting its generalization ability? To investigate this, we compare the performance of several single-task teacher models with our MTL-KD model on the same dataset, as shown in Figure 4 In contrast to the teacher models, the student model demonstrates a notable capacity for scale generalization. This observation indicates that the MTL-KD model, during the learning process, does not simply replicate the teacher's 's knowledge but rather effectively adapts to scale variations, consequently achieving robust generalization performance.
Performance Comparison: KD vs. RL To highlight the effectiveness of our knowledge distillation approach, we train the proposed multi-task LEHD model under two distinct training paradigms: knowledge distillation (MTL-KD) and reinforcement learning (MTL-RL). Given the high computa- tional cost associated with training the LEHD model with RL, we are only able to train it at a scale of 20. Subsequently, we evaluate the average gap of both models in all tasks seen and unseen, with the experimental results presented in Table 3 The results indicate that the RL. method, due to its limitation to training small scales, struggles to leverage the full potential of the LEHD model,
8

---

Table 2: Performance on unseen VRPs across three scales. represents the bascline used for gap
calculation.
Method
Pm
Problem Size
Pro.
Problem Size
n=100
p=5500
b=lk
n=100
n=500
m=1k
HGS-PyVRR
9:67(*)
34,70(*)
65,38/*)
24.44(%)
91,86(*)
174.79(*)
OR-Tools
9,79:1.25%
37.09(6.89%)
69 (1)54)6.519)
99.5008.319)
186.38(6.628)
10.6119.69%)
137%)
45.69(41445%)
26. 70(9556)))
123.97(34955%)
252.82((4.65%)
MT-POMMDM-aagg)
OVRL
10.1364.72%)
(1.28(18.95%)
+4.40029.08%)
VRPLIW
25. (1.99)
116.62/26.955)
235.911(41.99%)
MVM TD)
10,76(11.259)
18.60640.059)
135.08:106.560 5856)
27.00(10-488)
124.25(35 25%)
274.68:57. 15%)
MVMoE(M-augB)
(0.10)4.43%)
45.58(31.3698
116.71(78.88%)
25. (5.62)(.84%))
118.00228.40 45%%)
260.07(48. 79%
MTL-KDDSS T.bs
10.12(7.73%%
38.23(10.17%)
72.32(10.51%%)
26.37 (7.89%%
101.39 36%)
195. (85.65(11
MTL-KDIS.Thhr
10.44(7.55%)
38.43(0.766%)
11.7%)
25.35(7781
100. 40 (9. (9,30%)
192, (92.41(10.089)
(TLKKD)337200,.s
1..00(4.29%)
37.2777.41%)
71.35(
25.55(4.544))
97.85(6.5115 (6)
189.82 (8.14%)
[+00X")
47.97 (*)
83
OR-Toll
14. 14.28(1.989)
52.94 (2.94))0.368)
91 6919
K.37(5)
29.98 (5)
54.87 (*)
MT-POMOIS.T)
1541(11 (66%)
71 52.24)
147 147.97766828
9:52(13.8258)
35.49(18
74.59(35 35.05%)
MT-POMO(M--ug))
14.9066 395)
66 (5)
137. 1363388755
OVRR
8.98/7 349)
288))
66 21 (1(98995))
MYMoE(S T.
15.74(12.399)
82.49[71 97%)
219 2106116619555
9.74(16.19)
45 45.00/52206
129 28/1135555 (15.888 819))
MVMaF
14. 14.83959999)
76. 12158.55898
197 $4(136,4195)
8 8.967.1058
an 41411774799 (798)
109 0969 8156)
STL--DDS.TL Taas
15.28 (9.12%)
53.38 (11.28%)
94.65 (13.11%)
9,25(10.588) 5856)
300033.080 0.880)
58.576. 7086
- T.Ss
15. 15.2618 9593)
53,56(11 6555)
9.27(10819)
30 (1 (1-5889)
56.22 (3.738)
MTI- MTI-KDIR3C200:.0
(4.70(5.02%)
51.978834%)
93.91(12.22%%
8.78(4.95%)
28.73441669
OR-Tools
12,02()
47.93
(9)82())
25
97.7717
19 (00
MT-POMOIS..)
12.7115.7998
50.2015.779)
28 2X.64/22.000 700%)
126.0028880 6756)
270.696 (056)
12.1010.66%)
48. (5(045))
94 (44)
VRPBBW VRPBTN
26. 9466.0498)
118,20220.80 20/20.99691
251.58 20 22%)
MVMeE(S.T.
12.86(7.06%)
10.03666.119)
159 (1799178)009))
28, (..66%))))7
125 255.8928.700 76%)
294.2M51. 13%)
MYMoE(M-aug()
12.05(0.28%)
63.57(32.63%)
(16.11)62.10%)
26.89)))22))
16.4422.10 16%)
276.177 176.17(11.55 855%)
MTL- T.bs
52.5614.549%
9.0-43)))
86. (5.755%)))
28. 28.48(12. 1 196)
105. 43(7.836))
115.94410.9233
MTL- K.LL-KDS...hh
12.54(4.32%)
(5.77%))
86. 28/ 3.95%)
(12.9
103.85 (6.21%%
(09.5227.779)
MTL xD(R3C200)
12.08(0.55%)
$2.561-8.08%)
100.25(2.53%) 26.64(4.84%)
205.13(5.3%)
Tool
(*)
20.00
(4
14,38(*)
51.58 (?)
90.30 (*)
MT-POMMIS.T.
9.50(13.79%)
35,34119.3788
74 RL1333777. 80%)
(6.92177611))
12,91(10.539)
152. 63.66466..8 98%)
MT-POMMMM-uugS)
8.96(7.35%)
12.60(0011385)
83(3313%%)
OV OVRPBTT
15.85(10.39 (.9)
67 96%)
840.72154887)
MVMoE(S.T.
9.75(16.75%)
45 (5(55.))))7%
127 34(1344999))
17.07(18.688) (.86)
81.57(57. 22%)
214,76(136. 369)
MVMoE(M-aug8)
9. 9.29(11.275) 8.9.1(.112%)
10 10.35(36.299)
108 $3/99389999
15 05..81999900 (0%)
71.43
193, (22.777)
MTL-KD(S. T.bs
31 (6666699))
61,37(13,0118
16, 70 10%)
56.02(7.977)
99, 8519 89%)
MTL-KDIS
(127(2)))%
14%)
29025//91119
74(66
8.84(5.95%)
29.22-1..665
53.77-00.885)
15.58(8.00%)
53.75(362%))
37.37(7
OR-Taols
25.34
103, 17(*)
189.31(*)
14.25(*)
$2,37(*)
92. 12.16(")
MT.POMOIS
28.92(44.118))
131,68(27.648) 645))
(9939.668)
16.78(17.795)
(9.26639.9058)
60%)
MT-POMOMM-MugS)
27. 27.25(7,52%)
123.71(19991%)
245 (1661129755)
15.74(10.45%)
68.08. (3.00%)
141. 27(53 28%)
MV T.
29.191551185
132,25 17%)
286 (151.25)))
16,95(18 9455)
82,36657 2855)
215 6A 134 54.03%)
MVMoE(M
27.14(7.10%)
125.27(21 43%%)
15 (5.67799975))
74,83(42 9096)
195, 12.00%)
KDIS. Thss
(3.01(14447038)
111.33(7 92%%)
111.191)
16, 16.78(17.745)
56.34(7.5965
101.43 (10.0666
- Thss
29.13 (14.965)
110.33 (6 (6.94%)
205 52
(8. (8.56%)
16.95(18995))
57.15(9. 1399)
101 6-4(1) 2955)
MTL KDIR3CD):)
27.12(7.03%)
106.52(3.669)
201.29(6333%)
15:65 (9.84%)
54.6814.4115 (6
19.64/8811))
CVRP
OVRP
VRPTW
22-
Studert/MTL KD)
26.8%
StudentMML KD)
47.7%
3>-
studentMTL KDI
SUSentINTL KD)
78.5%
tuacchr(POMM)
teacher(PONO!
(eacher(POMG)
70-
teachariPPMO)
40-
30-
26.8%
31.4%
42
5.3%
2.0%
3.6%
4,1%
30
8.4%
12.6%
18.2%
18.2%
3.2.%%v
6%
3.0%
10.0%
5.2%
20
30-
30
7.38..%
20:
.33%
200
200
500
2000
3000
zt0
200
1002
100
200
500
A000
176
220
500
2000
Probiom
Froblom
Problem
Figure 4: Performance Comparison between Teacher and Student Models, both trained on instances of scale 100.
leading significantly poorer performance. In contrast, our dosillattio--aased MTL-KD model demonstrates a clear performance advantage.
Effectiveness Analysis of R3C To validate the effectiveness of our proposed R3C method, we conduct experiments on CVRP, VRPL, OVRP, and VRPTW at scale 100. We perform an abla- tion study on the random reordering of the subtour external order component, with the following comparative experiments: random sampling on the original solution only (RS); random reordering of the subtour external order followed by sampling (RS+Ro); and for CVRP and VRPL, we also analyze the impact of adding random flipping operation (F) since it does not affect the legality of the solution. The experimental results are shown in F Incorporating the random reordering operation significantly improves the iterative performance during reconstruction, which benefits from the ability of random reordering to enhance the diversity of sampled subproblems. Furthermore, the random flipping operation can moderately increase the diversity of sampled solutions when
9

---

Table 3: Heavy Decoder Performance (RL vs, KD) on Seen/Unseen Tasks (Average Gap).
Problem Size
100
200
500
1000
MTL-RL
21.7834%
27.2457%
38.2808%
50.0606%
Training task
MTL-KD
5,4569 %
5.2775%
5.8028% %
6.6413%
MTL-RL
31.2513%
37.1404%
48.9074%
62.2226% 13.3322% %
unseen task
MTL-KD
19.1658%
12.9145%
10.8275%
only initial solution random sampling is performed; however, its impact minimal with random reordering, further confirming the effectiveness of the random reordering operation.
CVRP
DVVPPP
VIPI
VRPTW
00.0
85 155-1z
RS+R004
RS-Hlbet
RS+Ro
RS+Ro
RS+F
50:80
RS
R5
Itoration
Beratton
Iteration
Iteration
Figure 5: Impact of Different Components in R3C.
7 Conclusion
This paper presents heavy decoder model for the multi-task VRP domain and achieves label-free training of this model through a multi-task knowledge distillation method. The proposed approach has demonstrated excellent performance both seen and unseen tasks, well as real-world, datasets, exhibiting significant large-scale generalization ability and thereby validating the effectiveness of method. Furthermore, the proposed R3C method has further enhanced the model's performance. However, the structure of the heavy decoder results in high computational complexity. Future work will explore how implement more efficient and robust model architectures in the multi-task domain.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China (Grant 62476118, 18, Grant 72271168), the Natural Science Foundation of Guangdong Province (Grant 2024A151501 1759), the Guangdong Science and Technology Program (Grant 2024B 121 1212010002). the Guangdong Basic and Applied Basic Research Foundation (Grant 1824415150111 Center for Computational Science and Engineering at Southern University of Science and Technology.
and the
References
Diego Cattaruzza, Nabil Absi, Dominique Feillet, and Jesús González-Feliu. Vehicle routing problems for city logistics. EURO Journal on Transportation and Logistics, 6(1):51-79, 2017.
[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 1945-1967. IGI Global, 2021.
[3] Jianan Zhou, Yaoxin Wu, Zhiguang Cao, Wen Song, Jie Zhang, and Zhenghua Chen. Learning large neighborhood search for vehicle routing airport ground handling. IEEE Transactions on knowledge and data engineering, 35(9):9769-9782 2023.
[4] 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 253. 2025.
10

---

[5] Kai Li, Ruihao Zheng. Xinye Hao, and Zhenkun Wang. Multi-objectivv infeasibility diagnosis for routing problems using large language models. arXiv preprint wrXiv:2508.03400 2025.
[6] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti Spaccamela. and Marco Protasi. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012.
[7] Keld Helsgaun. An extension of the te---enighan--heelgaane tsp solver constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-998 2017.
[8] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140: 140:105643, 2022.
[9] Vincent Furnon and Laurent Perron. Or-tools routing library, 2023. RtL.lattte::/dddellpprre.. google com/ comn/opttimlaaiioo/rouutigg
[10] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
[11] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188 21198, 2020.
[12] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:1 15:1936-1949 1949, 2022.
[13] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced multi muilti- transformer for the traveling salesman problem. Proceedings of the AAAI Conference on Artificial Intelligence, 37(7):8133 11188-11--1 122-81445 8140, 2023.
[14] Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. Monte carlo tree search for comprehensive exploration in Lased automatic heuristic design. In International Conference Muchine Learning. 2025. URL https:: wtwp:erwwwweeeeeeeoueeeeraaeeeee hott:/oorummddd-ool000111
[15] Rui Sun, Zhi Zheng, and Zhenkun Wang. Learning encodings for constructive neural combinatorial optimization needs regret. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18): 20803-20811, Mar. 2024, doi: 10. 10.1669/anii.v33 v38i 13111...008188 18,0066 URI. httpptttt:///ooe aaai .rrg/ org/index. iiddx.idexx... php/ MMTT/article/vier/00000
[16] Zhi Zheng, Shunyu Yao, Genghui Li, Linxi Han, and Zhenkun Wang. Pareto improver: Learning improvement heuristics for multi objei-obeective route planning. IEEE Transactions on Intelligent Transportation Systems, 25(1):1033 1141100333331111,-11111111113331 2024. doi: 10.1109/TITS 2023.3313688.
[17] Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. CaDA: Cross-problem routing solver with constraint-aware dual-attention. In International Conference on Machine Learning, 2025. URL
https://openrevierr net/Eoruum?ddCCSRRyhuiiii
[18] Luo, Yaoxin Wu, Zhi Zheng, and Zhenkun Wang. Rethinking neural combinatorial optimization for vehicle routing problems with different constraint tightness degrees, 2025. /ttppst/t////xxitt org/ abs/2505. 24627
[19] Changliang Zhou, Xi Lin, Zhenkun Wang, and Qingfu Zhang. Learning to reduce search space for generalizable neural routing solver. arXiv preprint arXiv:2503.031377 2025.
[20] Changliang Zhou, Canhong Yu, Shunyu Yao, Xi Lin, Zhenkun Wang, Yu Zhou, and Qingfu Zhang. Urs: A unified neural routing solver for cross-problem zero-shot generalization. arXiv preprint 2rXiv:2509.2341 2025.
[21] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin- ker-keiigha---eeeseee heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, volume 34, 2021.
[22] André Hottung, Paula Wong-Chung, and Kevin Tiemey. Neural deconstruction search for vehicle routing problems, 2025. URL http:///:///a org/ hts/ /200.. 03715
[23] Fei Liu, Xi Lin, Qingfu Zhang, Xialiang Tong, and Mingxuan Yuan. Multi-task learning for routing problem with cross cross- prosleproblm zero-shot generalization. International Conference on Knowledge Discovery and Data Mining (KDD), 2024.

---

[24] 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. In International Conference on Machine Learning, pages 61804-61824, 2024.
[25] Federico Berto. Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Junyoung Park, Kevin Tiemey, and Jinkyoo Park. Routefidder: Towards foundation models for vehicle routing problems, arXiv preprint arXiv:2406. 15007, 2024.
[26] 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.
[27] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Newral Information Processing Systems, volume 36, pages 8845-8864.
Curran Associates, Inc., 2023.
[28] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-aco: Bisimulation quotienting for efficient neural combinatorial optimization. In A. Oh, T. Naumann, A. Globerson, K. Sacnko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 77416-77429, Curran Associates, Inc., 2023.
[29] Fu Luo, Xi Lin, Yaoxin Wu, Zhenkun Wang. Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehicle routing problems. In International Conference on Learning Reprexentations, 2025.
[30] GeoffreyE. Hinton, Oriol Vinyals, and J.Michael Dean. Distilling the knowledge in neural network. arXiv: Machine Learning.rXiiv Machine Learning, Mar 2015.
[31] Jicyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. Advances in Neural Information Processing Systems, 35:31226-31238, 31238, 2022.
[32] Yubin Xiao, Di Wang, Boyang Li, Mingzhao Wang, Xuan Wu, Changliang 7hou, and You Zhou. Distilling autoregressive models to obtain high-performance non-autoregressive solvers for vehicle routing problems with faster inference speed. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18):
20274-20283 2024.
[33] Qidong Liu, Xin Shen, Chaoyue Liu, Dong Chen, Xin Zhou, and Mingliang Xu. Enhancing the general- ization capability of 2d array pointer networks through multiple teacher-forcie knowledge distillation. Journal of Automation and Intelligence. 2025.
[34] Sisi Zheng and Rongye Yc. Aspdd: An adaptive knowledge distillation framework for tsp generalization problems. IEEE Access, 2024.
[35] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229 222, 1992.
[36] Niels A Wouda, Leon Lan, and Wouter Kool. PyVRP: A high-performance VRP solver package. INFORMS Journal on Computing, 2024.
[37] Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. Cada: Cross-problem routing solver with constraint-awar aware dual- attention. arXiv preprint arXiv:2412.0034 2024.
[38] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-855) 2017.
[39] Marius M Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2):554-265, 1987.
[40] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[41] Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representations Workshop Track, 2017. URL http://///pppeeeeeeeeeeee//rr/r/
DD49xx
[42] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
12

---

[43] Yeong- Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park. and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 54:5138-5149 2021.
[44] Liang Xin. Wen Song, Zhiguang Cao, and Jie Zhang. Multi dulti-decoder attention model with embedding glimpse for solving vehicle routing problems. Proceedings of the AAAI Conference on Artificial Intelligence. 35(13):12042-122) -22499 2021.
[45] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Zhang. Towards omni- gene-generllizable neural methods for vehicle routing problems. In International Conference on Machine Learning, pages 42769 42789. PMLR. 2023.
[46] 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) (8))): 20803-20811, 2024.
[47] Zhi Zheng. Shunyu Yao, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan. and Ke Tang. DPN: Decou- pling partition and navigation for neural solvers of min-max vehicle routing problems. In International Conference on Machine Learning, 2024.
[48] 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. In Proceedings of Thirty-Third Third International Joint Conference on Artificial Intelligence, pages 6914-6922, 2024.
[49] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. Invit: generalizable routing problem solver with invariant nested view transformer. In International Conference on Machine Learning, pages 12973-12992 2024.
[50] 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 S0fiv:2405.019000 2024.
[51] Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In International Conference on Learning Representations, 2023.
[52] Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems real-time. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18):20284200
2024.
[53] Zhi Zheng, Changliang Zhou, Xialiang Tong, Mingxuan Yuan, and Zhenkun Wang. Ude: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. In A. Globerson. L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neurul Information Procensing Systems, volume 37, pages 6081-6125 Curran Associates, Inc., 2024.
[54] Chenguang Wang and Tianshu Yu. Efficient training of multi-task combinarotial neural solver with multi-armed bandits. arXiv preprint arXiv:2305.06361, 2023.
[55] Zhuoyi Lin, Yaoxin Wu, Bangjian Zhou Zhiguang Cao, Wen Song, Yingqian Zhang, and Jayavelu Senthilnath. Cross-problem learning for solving vehicle routing problems. In The 33rd International Joint Conference on Artificial Intelligence (JCAAI-24) 2024.
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: The main claims made in the abstract and introduction accurately reflectthe contributions and scope of the paper.
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 not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the limitations of the work in the last 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 does not include theoretical results
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 referenced in the statement of any theorems.
The proof' 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 or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We will make our code, datasets, and pre-trained models publicly available upon final manuscript submission, with all implementation details thoroughly described in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 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 a specific model and empirical evaluation, it may be necessary either make it 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 appropriate to the research performed.
While NeurlPS 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
See the abstract for the link to the code and trained models.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a 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
/ mripss.cc/ubbliccgui.eee CoodeSumeeieeeeee ssi iessonPolll molyicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
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 much information possible in supplemental material (appended to the paper) 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: Both the testing and training settings are detailed Section Experiment Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Neural Combinatorial Optimization (NCO) methods typically only report the mean or the gap to the optimal solution (or the best-known solution). In this method, there is randomness involved, and all random seeds fixed at 2025.
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, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
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 enror 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 com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We describe the required computational resources for the experiments in the experimental section
Guidelines:
The answer NA means that the paper does 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 as well as 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 I 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 /ttiingtttts////ppppp.p.pppppapp
Answer: [Yes]
Justification: This paper strictly adheres to the standards academic writing, especially NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
This work focuses solving and optimizing combinatorial optimization (CO) problems, which holds the potential to significantly enhance real-world applications. appears to have negative social impact. More discussion refers Appendix
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or 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.
The conference expects that many papers will be foundational research and not tied to 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 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 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
The paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses no 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 to 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We list the licenses in Appendix
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.paperssit
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.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: The paper does not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodll as part 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 or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According 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 (TRB) 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/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

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 to the NeurIPS Code of Ethics and the guidelines for their institution.
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
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The paper does not describe the usage of LLMs as an important, original, or non-standard component of the methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neuri)) http::///eerrrpp.ccoooooooerre/r ccC////feeeeeenee/222///... for what should or should not be described.
20

---

A Related work
A.1 Single-task Autoregressive Neural Solver
Research on high-performance autoregressive neural solvers for VRP is a hot topic in NCO. is typically based on the encoder-decoder structure, where the encoder generates node embeddings. and the decoder is used to dynamically generate node sequences. Early works are based on Pointer Net-
works [40], gradually evolving from supervised learning to reinforcement learning training [41] 42 Subsequently, the Transformer framework is introduced and becomes a mainstream paradigm [0] POMO [1T further leverages the symmetry of the VRP, optimizing the baseline calculation in RI. training and enhancing the exploration diversity of the model. Subsequent research largely focuses on improving the Transformer framework 443 44
12 45/47). However, these approaches predominantly adopt the Heavy Encoder and Light Decoder (HELD) structure, which poses chal- lenges in handling large-scale problems. To enhance the capability of solving large instances, some methods continue to build upon HELD. Examples include ELG [48], which integrates local search strategies; INVIT [4), which utilizes K-nearest neighbor multi-view embeddings enhance local information; and ICAM [50, which introduces cestance-conditionn
adaptation to better perceive problem scales. On the other hand, some studies 27 explore heavy decoder architectures. By dynamically capturing the relationships between remaining nodes during the decoding process, these methods demonstrate superior generalization performance on large-scale problems. However, their high computational demands, often necessitating training on labeled data, represent a significant limitation. Furthermore, some methods [51553 29] decompose large-scale problems into multiple smaller subproblems for solving, and autoregressive neural solvers can be employed at the lower level to address these subproblems.
A.2 Multi-Task Autoregressive Neural Solver
To enhance the generalizability of neural solvers across diverse VRP variants, several existing methods have proposed unified multi-task models. For example, Wang and Yu (54] employ a multi-armed bandit approach to achieve efficient training across multiple combinatorial optimization problems. Lin et al. (55) pre-train a Transformer backbone on the Traveling Salesman Problem and fine-tune it for specific VRP variants, thereby extending its applicability represent initial attempts at cross pross-problem learning but are limited in scope, focusing primarily on small number of problems. Building on these foundations, MT-POMO [23 views VRP variants as combinations of distinct attributes, enabling unified representation and zero-shot ceneralization across multiple VRP variants, achieving notable performance on ten tasks. MVMoE (24 further boosts model capacity and multi-task performance by introducing a mixture-of-ene experrs model. RouteFinder [25] enhances multi-task training efficiency and performance through mixed batch training and enables rapid adaptation to unseen tasks via efficient adapter layers. CaDA (37) improves the model's ability to handle diverse tasks within a multi-task framework by incorporating constraint awareness and dual-branch structure. However, these studies have predominantly focused on small-scan problems, lacking extensive exploration of large-scale generalization capabilities.
subset of VRP problems. These methods
B Problem Definition and Settings
Our VRP variant problem settings follow the work of Zhou et al. 24 The detailed settings are as follows:
Coordinates: All node coordinates are uniformly sampled from the 2D space [0, [0, 1). Demands: For all customer nodes, demands are randomly sampled from the set {1, 2.. 9}.
Vehicle Capacity: Each vehicle has a fixed transportation capacity, which we set to 50 across all problem scales. The sum of demands for nodes visited by a vehicle must be less than or equal to current capacity.
In open vehicle routing problems, vehicles are not required to return to the depot. We use a binary flag vector to distinguish whether a path is open; setting it to I indicates an open path.
Open Routes:
21

---

Table 4: 16 VRP variants with five constraints.
Constraint
Capacity
Open Route
Backhaul
Duration Limit
Time Window
CVRP
OVRP
VRPB
VRPL
VRPTW
OVRPTW
OVRPB
OVRPL
VRPBL
VRPBTW
VRPLTW
OVRPBL
OVRPBTW
OVRPLTW
VRPBLTW
OVRPBLTW
Backhauls: In problems involving backhauls, portion of the nodes have negative demands, referred to as backhaul nodes. We designate 20% of the customer nodes as backhaul nodes, whose demands are randomly sampled from {-1, -2, ..... -9].
Duration Limit: Each vehicle has maximum travel distance limit, which
to 3.
Time Windows: Customer node time windows are uniformly sampled, and service time is uniformly set to 0.2. Vehicles must visit nodes within their time windows; a vehicle arrives early, it must wait until the earliest start time. The depot's 's time window is set to [0, 3], with service time of Vehicle speed is uniformly set to I, meaning the time spent traveling on path equals its distance divided by speed. Notably, for non-open problems, it erucial ensure that after visiting the last customer node, the vehicle can return to the depot within its latest allowable time window; this consideration is not necessary for open problems.
By combining different constraints, 16 VRP variants can be formed, detailed in Table 4
C Sensitivity Analysis on R3C Re-optimization Segment Length
To confirm the efficacy of our random segment length selection in the R3C strategy, we compare against fixed segment lengths (k (10. 20, 30, 40, 503) on 100-node instances for four VRP variants (CVRP, OVRP, VRPL, VRPTW). As shown in Table[5] the random length consistently yields the best performance across all problems. We attribute this advantage the increased solution diversity provided by varying segment lengths, which effectively prevents the search from getting trapped in local optima, a common issue with fixed segment sampling.
Table 5: Results after 50 iterations of R3C with different Re-optimization Segment Lengths 100-node instances.
Problem
segment=10
segment=20
segment=30
segment=40
segment=50
Random
CVRP
16.01
15.96
15.94
15.91
15.91
15.88
OVRP
10.34
10.21
10.17
10.20
10.17
VRPL
16.09
16.03
16.00
15.97
15.98
15.90
VRPTW
26.02
25.86
25.77
25.65
25.69
25.55
D Performance on Real-World Instances
Our test results on real-world instance datasets are presented in Tables 6 and 8 All models
trained on instances of size N 100. During inference, data augmentation is applied, and
22

---

greedy rollout strategy is adopted by default. Some results for comparative models are sourced from MVMoE (24] and RouteFinder 25
Table 6: Results on small-scale CVRPLIB instances (Set-X) of size N = 100, and inference utilizes data augmentation and greedy rollout by default.
38
All models are trained instances
Set-X
POMO
POMO-MTL
MVMeB/4E
MVMOEME-L
MTL-KD
Instance
Opt.
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
X-n101-k25
27591
30138
9.231%
32482
17.727%
29361
6.415%
29015
5.161%
29058
5,317%
X-n106-k14
26362
39322
49.162%
27369
3.820%
27278
3.475%
27242
3.338%
26918
2.109%
X-n110-k13
14971
15223
I 1.68%%
15151
1.202%
15089
0.788 %
15196
I 1.503%
15407
2.912%
X-n115-k10
12747
16113
26.406%
14785
15.988%
13847
8.629%
13325
4.534%
13513
6.009
X-n120-16
13332
14085
5.648%
13931
4.493%
14089
5.678%
3.758%
13657
2.438%
X-n125-130
55539
58513
5.355
60687
9.269%
58944
6.131
58603
5.517%
57615
3.738
X-n129-k18
28940
29246
1.057%
30332
4,810%
29802
2.979%
29457
1.786%
29309
1.275%
X-n134-k13
10916
11302
3.536%
11581
6.092%
11353
4.003%
11398
4.416%
11363
4.095%
X-n139-k10
13590
14035
3,274%
13911
2.362%
13825
1.729%
13800
1.545%
13911
2.362%
X-n143-k7
15700
16131
2.745%
16660
6.115%
16125
2.707%
16147
2.847%
15955
1.624%
X-n148-k46
43448
49328
13.533%
50782
16 880%
46758
7.618%
45599
4.951
45463
4.638%
X-n153-122
21220
53.040%
262.37
23.643%
23793
12.5%
23316
9.877%
23340
9.991%
X-1157k133
16876
17660
4.646%
17510
3.757%
17650
4.586%
17410
3.164%
17161
1.689
X-1162.k11
14138
14889
5.312%
14720
4.117%
14654
3.650%
14662
3.706%
14487
2.469%
X-n167-k10
20557
21822
6.154%
21399
4.0961
21340
3.809%
21275
3,493%
21053
2.413%
X-1172-K51
45607
8.659%
56385
23.632%
51292
12.465%
7.600%
47850
4.918
X-n176-126
47812
54197
13.354%
57637
20.549%
55520
16.121%
52727
10,280%
52476
9.755
X-n181-k23
25569
37311
45.923%
26219
2,542%
26258
2.695%
26241
2.628%
25919
1.369%
X-n186-k15
24145
25222
4.461
25000
3.541%
25182
4.295%
24836
2.862%
24711
2.344%
X-n190-K8
16980
18315
7,862%
18113
6.673%
18327
7.933%
18113
6.673%
17539
3.292
X-n195-151
44225
49158
11.154%
54090
22.306%
49984
13.0225
48185
8.954%
46301
4.694%
X-n200-366
58578
64618
10.311
61654
5.251%
61530
5.039%
61483
4.959%
60978
4.097%
X-1209-k16
30656
32212
5.076%
32011
4.420%
32033
4.492%
32055
4.564%
31536
2.871
X-n219-173
117595
133545
13.564%
119887
1.949%
121046
2.935
120421
2.403%
118499
0.769%
X-n228-1:23
25742
48689
89.142%
33091
28.549%
31054
20.636%
28561
10.951%
28156
9.378%
X-n237-k14
27042
29893
10.543%
28472
5.288%
28550
5.577%
284866
5.340%
27789
2.762%
X-n247-k50
37274
56167
50.687%
45065
20.902%
43673
17.167%
41800
12.143%
41106
10.281% %
X-n251-128
38684
40263
4.082%
40614
4.989%
41022
6.044%
40822
5.527%
39877
3.084%
Avg. Gap
16.629%
9.820%
6.884%
5.160%
4.025%
E Licenses for Code and Datasets
The licenses for the codes and the datasets used in this work are listed in Table g
F
Broader Impacts
This research contributes to the field of neural combinatorial optimization by employing advanced machine learning techniques address large-scale and multi-variant VRP problems. We believe that the proposed multi-task knowledge distillation training framework, heavy decoder model, and Random Reordering Reconstruction (R3C) strategy can provide valuable insights and inspire subse- quent work to explore more efficient and effective neural methods for solving large-scale and diverse VRP problems. As general learning-based approach to solving the VRP, the proposed multi-task knowledge distillation training framework and R3C strategy do not inherently possess any specific potential negative social impacts.
23

---

Table 7: Results on VRPTW instances (Set-Solomon) size = 100, and inference utilized data augmentation and greedy rollout by default.
39
All models are trained on instances of
Set-Solomon
POMO
POMO-MTL
MVMOBAE-L
MTL-KD
Opt.
Ohj.
Gap
Obj.
Gap
Ohj.
Gap
Ohj.
Gap
Ohj.
Gap
RI01
1637.7
1805.6
10.252%
1821.2
11.205%
1798.1
9,794%
1730.1
5.641%
1768.0
7.956%
RI02
1466.6
1556.7
6.143%
1596.0
8.823%
1572.0
7.187%
1574.3
7.345%
1564.4
6.668%
R103
1208.7
1341.4
10.979%
1327.3
9.812%
1328.2
9.887%
1359.4
12.470%
1379.0
14.090%
971.5
15.142%
15.358%
1124.8
15.780%
13.100%
10.561%
R105
1355.3
1506.4
11.149%
1514.6
11.754%
1479.4
9.157%
1456.0
7.433%
1465.2
8.109%
106
1234.6
1365.2
10.578%
1380.5
11.818%
1362.4
10.3529
1353.5
9.627%
1346.1
9.031%
1077
1064.6
1214.2
14.052%
1209.3
13.592%
1182.1
11.037%
1196.5
12.391%
1193.9
12.145%
100
932.1
1058.9
13.604%
1061.8
13.915%
1023.2
9.774%
1039.1
11.481%
1035.4
11.082%
R 109
1146.9
1249.0
8.902%
1265.7
10.358%
1255.6
9,478%
1224.3
6.750%
1260.0
9.861%
R110
1068.0
1180.4
10.524%
1171.4
9.682%
1185.7
11.021%
1160.2
8.635%
1199.5
12.313%
RI11
1048.7
1177.2
12.253%
1211.5
15.524%
1176.1
12.148% %
1197.8
14.220%
1178.7
12.396%
R112
948.6
1063.1
12.070%
1057.0
11.427%
1045.2
10.183%
1044.2
10.082%
1057.2
11.448%
RC101
1619.8
2643.0
63.168%
1833.3
13.181%
1774.4
9,544%
1749.2
7.988%
1774.0
9.520%
RC102
1457.4
1534.8
5.311
6.086%
1544.5
5,976%
1556.1
6.771%
1588.4
8.989%
RC103
1258.0
1407.5
11.884%
1396.2
10.986%
1402.5
11.466%
1415.3
12.502%
1451.8
15.405%
RC104
1132.3
1261.8
11.437%
1271.7
12.311%
1265.4
11.755%
1264.2
11.649%
1241.6
9.653%
RC105
1513.7
1612.9
6.553%
1644,9
8.668%
1635.5
8.047%
1619.4
6.980%
1688.3
11.535%
RC106
1372.7
1539,3
12.137%
1552.8
13.120%
1505.0
9.638%
1509.5
9.968%
1468.8
7.001 %
RC107
1207.8
1347.7
11.583%
1384,8
14.655%
1351.6
11.906%
1324.1
9.625%
1367.6
13.231%
RC108
1114.2
1305,5
17.169%
1274,4
14.378%
1254.2
12.565%
1247.2
11.939%
1232.3
10.600%
RC201
1261.8
2045.6
62,11899
1761.1
39.570%
1577.3
25.004%
1517.8
20.285%
1490.8
18.149%
RC202
1092.3
1805.1
65.257%
1486.2
36.062%
1616.5
47.990%
1480.3
35.520%
1336.5
22.356%
RC203
923.7
1470.4
59.186%
1360.4
47.277%
1473.5
59.5219
1479.6
68.1822%
1237.8
34.005
RC204
783.5
1323.9
68.973%
1331.7
69.968%
1286.6
64.212%
1232.8
57.342%
1066.0
36.056%
RC205
1154.0
1568.4
35.910%
1539.2
33.380%
1537.7
33.250%
1440.8
24.850%
1448.3
25.503%
RC206
1051.1
1707.5
62.449%
1472.6
40.101%
1468.9
39.7491
1394.5
32.671%
1354.7
28.884%
RC207
962.9
1567.2
62.758%
1375.7
42.870%
1442.0
49.756%
1346.4
39.831%
1235.9
28.352%
RC208
776.1
1.50544
93.970%
1185.6
52.764%
1107.4
42. 12.688%
1167.5
50.437%
1064.0
37.096%
Avg. Gap
28.05 28.054%
21.380%
20.317%
18.490%
15.786%
24

---

Table 8: Results on large-scale CVRPLIB instances (Set-X) of size N 100, and inference utilizes data augmentation and greedy rollout by default.
38
All models are trained on instances
XrxX
PTMO
1,3D
POHO-MII
MVMGEMI
MVMOGMEE
RE-MVMOE
KF-TE
KTTL KD
0p1
08H
[ap
Dap
Cap
0H)
Gip
Tap
[13
GGp
(h)
Gup
X-5924399
69236
23617
9,229
71436
1,005%
77254
11,4429
13533
6.2299
74429
1,515
T6356
102249
7179
3/059
71124
27425
24238
34518
105
15634
3.80%
20510
17:9355
12102
32.47%
31231
212409
33839
34,00555
2546
11A995
2944
7.15%
X-52441533
154993
300877
90 5909
230556
19234
26.3599
19534)
21,659
17.922
IT0999
16422
77588
12.9099
171305
10.111%
X
94646
196207
100135
22.025
00A31
15.305
208343
144419
103947
11,9955
00272
5.5445
10093
X-548-159
95330
10399
13.00%
00644
4.50%
94582
1066%
55894
10.0449
69NT
13
104259
3028766
100556
164439
3960
2.488
X-5601442
6
13007%
51810
X4573-330
39679
28545
648719
53482
5.5499
6393
20
59413
17.3569
STA4
12.50%%
61534
11414%
5962
104139
53496
5.5228
X45ts4159
13.900
9761%
133319
214577
13.4866
11 11,4736
300575
8018%
X45994922
109451
150572
33.33%9
115317
5.3999
130888
103359
129949
189009
125279
15.11%
126578
16.714%
11600
7.77%
10313
4.48%
X45134622
14192%
387188
25
T3456
43161
67764
33060
17,574%
T0967
110615
T0114
133715
67472
87005
63755
X-444:435
66549
73647
140718
18.359
72005
140006
7065
11:259
106781
133381
14.1345
115533
100WSS
11668
117078
10 103705
118175
10 10
11609
11 11:975
189081
43
42,1906
509776
10018
29/9226
197995
35
183447
25.1646
166336
100099
15,200%
1600
X-sass-77 275
48305
70
15.5545
77916
48515
35833
18,015
07188
11. 15.1
53566
30
11:175
7334
73399
12.9225
213979
13375
11311
161695
16000
121145
13329
21,5995
16113
33-4995
63550
70-0775
11:1145
162255
00145
77259
67756
13.011%
83439
25542
17,2230
103435
23.955
21.599
02141
15:2599
83171
162277
42315
6.565%
Xx413-244
12366
90029
24.759
76766
6/51%
$3169
14.977%
100333
02N0
16316
134676
53185
140199
77382
68339
X
158121
13345:
22.344%
115556
120259
177157
120099
183999
16.113%
J85932
115259
115556
11.5115
174441
10.21
171072
7.519%
X433741422
193737
10.569%
229035
184436
14220%
7.63%
4.40%%
X-155-235
89955
152123
7..47%
52526
4,864%
100774
14,799%
59129
11.425%
206915
23.00%
100801
9629
104439
54079
5.348
X-176459
49186
20.4536
R.174%
X-155-237
$3850
70045
30421%
50605
1.739%
63557
21,773%
19015
46.700%
64310
60069
21.2946
64871
21-4449
59905
Xa3164207
329.79
9365%
383621
7.235%
197755
337675
196917
18.075
18636
730936
66 1165
196907
41 1TIS
161343
5715
163K3
55.447%
153991
Xa357a87
85455
53.00%
98396
E
33
105829
102609
118836
187687
1356
177973
138800
16007%
046317
250005
134687
17 AB/
131794
16 1079
0.335%
12569)
7,2015
Xa3006-443
72355
T6669
5.0006
21,153%
1764
94734
33,020%
79835
3.553
Aug. Gip
29/0005
12:0W5
167338
26 418%
12.333%
6.05%
Table 9: Licenses of Used Codes and Datasets
Type
Resource
License Type
URI Reference
Code
MVMoE
24
MIT License
https://jithub.c Roy MVME
Code
MT-POMO 23
MIT Lisense
bitps////itbbb cowFFFi..
Code
HGS-PyVRP
56
MIT License
VRPPY
Code
OR-Tools 0
Apache Licease
https///gttbbb.oomm/oooooooooooo
Datasel
CVRPLIB(SeL Sei
38
Available for acudemic reseurch use
http::/vrpp www.geaiiiooooeooooooiiioiooooio http::/wwww.ieemmm//ooooettww/es
Dataset
Solomon
3y
Available for scademic research
25


Reviews:
[{"review_id": "0pB3cQEl7D", "reviewer": "Reviewer_6wtN", "summary": "This paper introduces a multi-task learning method called MTL-KD that enables efficient training of heavy decoder models with strong generalization ability for solving diverse Vehicle Routing Problem (VRP) variants. The main works include 1)  label-free training of heavy decoder models through knowledge distillation from multiple RL-based single-task teacher models; 2) a Random Reordering Reconstruction (R3C) strategy to further enhance the performance of the multi-task model; Experimental results show superior performance of the MTL-KD model on both seen and unseen VRP tasks, as well as real-world datasets, exhibiting good scale generalization ability and outperforming existing multi-task VRP models.", "questions": "What are the clear benefits of neural VRP solvers in comparison with traditional VRP methods from OR community (e.g. branch-and-price-and-cut methods) and metaheuristics (e.g. genetic algorithm, VLNS, etc.)? \n\nWhy is the Random Reordering Reconstruction (R3C) strategy used? Does this imply weak performance by the proposed neural solver?", "limitations": "The motivation of using neural solver for VRP could be better explained and the use of iterative procedure of R3C needs further justification  and the fairness of comparisons with other methods is questionable as many other methods do not use local search style improvement procedure.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength: \nThe paper is well written and relatively easy to follow. The idea of a generic solver for several of VRP variants is well motivated. The use of knowledge distillation for training the proposed model makes good sense. \n\nWeakness: \n1) the introduction fails to explain why the neural solvers are preferred compared to the traditional VRP solvers. As was shown in the paper and the results by the current SOTA neural VRP solvers, the gap of these results to the best heuristic/OR methods is still quite large (sometime as high as 5% or higher). Even for large scale instances, the metaheuristics have proven to be very effective. What are the clear benefits of neural VRP solvers? It is not clearly stated in the paper. \n\n2) the proposed method uses a Random Reordering Reconstruction (R3C) strategy to further improve the performance. However, this would make the proposed method similar to an iterative improvement method widely used in metaheuristics. Therefore, a comparison with the state of the art metaheuristic for VRP should be necessary.", "was_revised": true, "final_justification": "I would like to maintain the previous rating on the balance of the positive changes and responses from the authors but remain concerned with the large performance gaps of the proposed method when compared with the SOTA exact method.", "rebuttal": "Dear Reviewer 6wtN,\n\nThank you for your time and effort in reviewing our work. We're glad you found our paper well-written, our experiments convincing in addressing existing NCO limitations, and our analysis insightful. We also appreciate your recognition of the proposed approach's significant improvements.\n\nWe address your concerns point-by-point as follows.\n\n---\n\n### W1 & Q1: Why are neural solvers preferred compared to traditional VRP solvers? What are their clear benefits?\n\nThank you very much for raising this concern. While classical heuristics still hold a slight edge in solution quality, their performance is highly dependent on expert-designed operators and meticulous parameter tuning, leading to very high deployment costs. Neural solvers, on the other hand, replace manual heuristic construction with **end-to-end learning**, requiring only data for training, which significantly **reduces the reliance on domain knowledge**.\n\nFurthermore, traditional methods experience a sharp increase in online solution time as the problem scale grows. In contrast, neural solvers, after a one-time offline training, can provide feasible solutions in a very short amount of time. This makes them particularly valuable for **real-time scheduling** and other scenarios requiring rapid responses, where their practical utility is significantly higher.\n\n---\n\n### W2: The proposed method uses R3C, making it similar to iterative improvement. A comparison with state-of-the-art metaheuristics is necessary.\n\nThank you very much for raising this concern. As demonstrated in the experimental section of our paper, we have already compared our proposed method with metaheuristic solvers such as **PyVRP** and **OR-Tools**, which are widely regarded as strong baselines. Our method even **outperformed OR-Tools in some scenarios**.\n\nIn our framework, the R3C strategy serves merely as an **optional enhancement module**. Even without enabling this strategy, our model itself surpasses other multi-task neural solvers. Therefore, our research focus remains on **elevating the inherent capabilities of Neural Combinatorial Optimization (NCO) methods**, rather than degenerating into a traditional metaheuristic iterative improvement framework.\n\n---\n\n### Q2: Why is the Random Reordering Reconstruction (R3C) strategy used? Does this imply weak performance by the proposed neural solver?\n\nThank you very much for raising this concern. We would like to clarify that the use of the R3C strategy does **not imply insufficient performance** of our proposed neural solver. Instead, it is an **optional post-processing method** designed to further enhance performance, essentially \"trading time for accuracy.\"\n\nOur model already significantly outperforms existing neural solvers in greedy decoding mode (as shown in Table 1), demonstrating its **strong inherent performance**. The introduction of R3C is intended to further unlock the potential of neural solvers and provide users with a **simple, general, and scalable way to improve solution accuracy**. Unlike methods such as LEHD-RRC, which are only applicable to TSP/CVRP, R3C can be seamlessly applied to **various VRP variants**, offering greater versatility.\n\nTable 1: Average performance of multi-task models on visible tasks. **Single t**: Results obtained via single trajectory inference. **aug8**: Results obtained using data augmentation (8 augmentations).\n\n| **Method** | **100 (Single t)** | **100 (aug8)** | **500 (Single t)** | **500 (aug8)** | **1000 (Single t)** | **1000 (aug8)** |\n| :-------- | :------------- | :----------- | :------------- | :----------- | :-------------- | :----------- |\n| MTPOMO | 7.5217% | 3.3900% | 23.6533% | 17.3883% | 40.3667% | 27.6867% |\n| MVMOE | 7.9433% | **3.0600%** | 41.0917% | 32.1633% | 91.9567% | 74.3500% |\n| MTLKD | **5.4569%** | 3.5920% | **5.8028%** | **4.5730%** | **6.6413%** | **5.6071%** |\n\n---\n\n### Limitations: Motivation of using neural solver, justification of R3C, and fairness of comparisons.\n\nThank you very much for raising this concern. We have provided a clearer explanation for the motivation behind using VRP neural solvers in our response to **Q1/W1**. The justification for using R3C has been elaborated in our response to **Q2/W2**.\n\nAdditionally, to ensure fairness in comparisons, we will supplement the main text with inference results obtained using aug8 with greedy decoding, consistent with practices in other related papers, as shown in Table 2. Compared to the other methods we evaluated, our model demonstrates superior performance in most scenarios.\n\nTable 2: MTLKD Performance with aug8 Augmentation under Greedy Decoding\n| **Problem Type** | **Scale 100** | **Scale 500** | **Scale 1000** | **Problem Type** | **Scale 100** | **Scale 500** | **Scale 1000** |\n| :----------- | :--------------- | :--------------- | :--------------- | :----------- | :--------------- | :--------------- | :--------------- |\n| CVRP | 15.850 (2.077%) | 64.169 (3.379%) | 123.759 (3.526%) | VRPTW | 25.718 (5.619%) | 97.859 (8.000%) | 183.389 (10.166%)|\n| OVRP | 10.184 (4.900%) | 38.343 (8.629%) | 71.803 (8.633%) | VRPB | 12.101 (1.104%) | 45.396 (-4.947%) | 85.814 (-3.118%) |\n| VRPL | 15.915 (2.118%) | 65.093 (2.425%) | 125.729 (2.484%) | OVRPTW | 14.753 (5.734%) | 52.942 (9.952%) | 92.902 (11.951%) |\n| OVRPL | 10.200 (5.494%) | 37.809 (8.959%) | 71.556 (9.433%) | VRPLTW | 25.910 (6.024%) | 99.400 (8.203%) | 190.778 (9.149%) |\n| OVRPLTW | 14.907 (6.468%) | 52.772 (10.015%) | 94.115 (12.464%) | OVRPB | 9.270 (10.810%) | 29.662 (-1.063%) | 54.805 (-0.115%) |\n| VRPBL | 12.178 (1.345%) | 45.067 (-5.974%) | 84.687 (-5.718%) | VRPBTW | 27.602 (8.637%) | 101.916 (4.237%) | 238.529 (22.520%)|\n| OVRPBL | 9.037 (8.249%) | 30.491 (2.997%) | 57.506 (5.896%) | OVRPBTW | 16.135 (12.173%) | 54.724 (5.476%) | 97.596 (7.410%) |\n| VRPBLTW | 28.093 (10.857%) | 108.349 (5.025%) | 202.361 (6.892%) | OVRPBLTW | 16.203 (13.711%) | 55.639 (6.250%) | 99.444 (7.902%) |\n\n---\n\nOnce again, we would like to express our heartfelt gratitude for the time and effort you've dedicated to reviewing our work. We sincerely hope that our response can address your concerns."}, {"review_id": "F3dn1jHBvm", "reviewer": "Reviewer_RweB", "summary": "In their work, the authors attempt to mitigate the issue of poor generalization in multi-task learning for vehicle routing problems. They propose the use of knowledge distillation to train a heavy decoder model using the outputs of individual single-task models, each trained for a VRP variant, and then applying a loss on the difference in the outputted probability distributions. Additionally, to escape local optimas they propose the use of Random Reordering Re-Construction (R3C), which divides routes into smaller sub-routes and shuffles the internal order while respecting the problem constraints. They then study the generalization ability of the model on unseen VRP variants and unseen problem scales.", "questions": "1. What seperates your method from a direct application of [3] to MT Solvers?\n2. Although not necessary for this paper, have you tried seeing if the method generalizes to the dynamic constraint problems as well?\n3. Have you tried different sized subsets for R3C?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe knowledge distillation approach does seem to greatly improve generalization ability in most scenarios with good ablation experiments. Additionally, the R3C method is relatively novel and well founded in avoiding the local optimization minimas.\n\nWeaknesses:\n\nI do have a few concerns with the paper namely:\n* The authors argue that this is a label free method, however this is not entirely correct since the teachers need to be trained on \"labeled\" data. It is more of a labeled training delegation.\n* Some key baselines are omitted from the results. Namely [1, 2] are referenced in the paper but never compared against, despite being state-of-the-art multi-task VRP neural solvers and reporting better results (I could not find any in-text citation for [1] in the main paper either, only its reference in the bibliography).\n* The novelty of knowledge distillation for VRP solvers is questionable since previous papers such as [3], which the author references, have previously shown the effectiveness of this approach in enhancing model generalization abilities. There was no actual discussion or comparison to it from a methodological perspective. \n* There are some issues with formatting, but this is minor, specifically in table 1 for VRPL MT POMO, the number is unintelligible.\n\n[1] Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. Cada: Cross-problem routing297 solver with constraint-aware dual-attention. arXiv preprint arXiv:2412.00346, 2024.\n[2] Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan,249 Junyoung Park, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for250 vehicle routing problems. arXiv preprint arXiv:2406.15007, 2024.\n[3] Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng252 Chee. Learning generalizable models for vehicle routing problems via knowledge distillation.253 Advances in Neural Information Processing Systems, 35:31226–31238, 2022.", "was_revised": true, "final_justification": "The exprimental section does seem more convincing now with the aligned ablation datasets and some baselines but I still have some reserves on the novelty of the approach.", "rebuttal": "Dear Reviewer RweB,\n\nThank you very much for taking the time andeffort to review our work. We are delighted toknow you find that our paper is well written andrelatively easyto follow,that the idea of ageneric solver for several of the VRP variantsis well motivated, and that the use of knowledgedistillation for training the proposed modelmakes good sense. We address your concerns pointby-point as follows：\n\n---\n\n### W1: Clarifying \"Label-Free\" Methodology\n\nThank you very much for raising this concern. We'd like to clarify that our teacher model is trained purely through RL, completely devoid of explicit optimal path labels. Similarly, the student model's distillation relies solely on the policy distribution from the teacher, eliminating the need for human or external labels throughout the entire framework. Therefore, our \"label-free\" training claim stands firm.\n\n---\n\n### W2: Additional baselines.\n\nThank you very much for highlighting the omission of certain baselines. We've now conducted additional experiments, including comparisons with SOTA multi-task Vehicle Routing Problem (VRP) neural solvers, RF[2] and CaDA[1], on the same visible tasks and settings as our model. As **Table 1** shows, our model consistently demonstrates superior performance.\n\nTable 1: Performance Comparison of RF, CaDA, and MTL-KD on seen Tasks\n| Method | Problem Type | n=100 | n=500 | n=1k |\n| :----- | :----------- | :---- | :---- | :--- |\n| RF-Transformer | CVRP | 15.82(1.88%) | 67.71(9.08%) | 132.79(11.08%) |\n| RF-MTPOMO | CVRP | 15.87(2.20%) | 67.42(8.62%) | 132.82(11.11%) |\n| RF-MVMoE | CVRP | 15.84(2.01%) | 67.36(8.52%) | 134.85(12.80%) |\n| CaDA | CVRP | 15.84(2.00%) | 175.65(182.99%) | 542.56(353.87%) |\n| MTL-KD$\\_{aug8}$ | CVRP | 15.85(2.08%) | 64.17(3.38%) | 123.76(3.53%) |\n| MTL-KD$\\_{R3C}$ | CVRP | **15.76(1.48%)** | **63.63(2.51%)** | **122.06(2.10%)** |\n| RF-Transformer | VRPTW | 27.39(12.49%) | 108.70(19.97%) | 222.92(33.91%) |\n| RF-MTPOMO | VRPTW | 26.29(7.98%) | 102.77(13.42%) | 193.57(16.28%) |\n| RF-MVMoE | VRPTW | 26.29(7.98%) | 100.78(11.22%) | 187.87(12.86%) |\n| CaDA | VRPTW | 30.16(23.87%) | 300.11(231.21%) | 693.61(316.66%) |\n| MTL-KD$\\_{aug8}$ | VRPTW | 25.72(5.62%) | 97.86(8.00%) | 183.39(10.17%) |\n| MTL-KD$\\_{R3C}$ | VRPTW | **25.31(3.93%)** | **96.43(6.42%)** | **181.85(9.24%)** |\n| RF-Transformer | VRPL | 15.88(1.93%) | 68.59(7.93%) | 135.15(10.17%) |\n| RF-MTPOMO | VRPL | 15.93(2.23%) | 68.33(7.52%) | 134.53(9.66%) |\n| RF-MVMoE | VRPL | 15.90(2.06%) | 68.39(7.62%) | 138.60(12.98%) |\n| CaDA | VRPL | 15.89(2.00%) | 176.04(177.01%) | 536.71(337.49%) |\n| MTL-KD$\\_{Single t}$ | VRPL | 15.92(2.12%) | 65.09(2.42%) | 125.73(2.48%) |\n| MTL-KD$\\_{R3C}$ | VRPL | **15.82(1.50%)** | **64.52(1.53%)** | **124.59(1.56%)** |\n| RF-Transformer | OVRP | 10.11(4.11%) | 42.88(21.48%) | 84.40(27.68%) |\n| RF-MTPOMO | OVRP | 10.17(4.70%) | 41.60(17.86%) | 82.14(24.26%) |\n| RF-MVMoE | OVRP | 10.13(4.29%) | 41.18(16.65%) | 81.82(23.78%) |\n| CaDA | OVRP | 10.10(4.04%) | 187.72(431.78%) | 442.57(569.55%) |\n| MTL-KD$\\_{Single t}$ | OVRP | 10.18(4.90%) | 38.34(8.63%) | 71.80(8.63%) |\n| MTL-KD$\\_{R3C}$ | OVRP | **10.05(3.53%)** | **37.79(7.07%)** | **71.40(8.03%)** |\n\n---\n\n### W3 & Q1: Novelty of Knowledge Distillation and Comparison to AMDKD[3]\n\nThank you very much for raising this concern. We want to clarify that our paper doesn't simply apply AMDKD to a multi-task scenario; instead, we introduce three key innovations:\n\n**Heterogeneous Teacher-Student Architecture:** Unlike AMDKD's homogeneous distillation, we propose **heterogeneous distillation** from a heavy encoder to a lightweight encoder. This allows us to leverage the low-cost training of the heavy encoder for generating soft probability distributions as supervision, while exploiting the heavy decoder's strong generalization for larger scales.\n**Label-Free Multi-Task Training Paradigm for Heavy Encoders:** We present a novel, **label-free multi-task training approach for the heavy decoder model**. This is achieved by allowing multiple lightweight decoder teacher models to undergo label-free reinforcement learning, with the heavy decoder student model directly distilling knowledge from them, opening a new avenue for training heavy encoders.\n**R3C Strategy for Enhanced Inference Performance:** We designed the **R3C strategy** specifically for MTL-KD. This strategy is adaptable to various VRP problems and significantly improves the model's inference performance.\n\nTo provide a quantitative comparison, we also reproduced a multi-task extended version of AMDKD. As **Table 2** shows, our model demonstrates superior performance.\n\nTable 2: Performance Comparison of MTL-AMDKD and MTLKD Models\n\n| **Problem** | **MTLAMDKD (n=100)** | **MTLKD (n=100)** | **MTLAMDKD (n=500)** | **MTLKD (n=500)** | **MTLAMDKD (n=1000)** | **MTLKD (n=1000)** |\n| :---------- | :-------------------- | :----------------- | :-------------------- | :----------------- | :--------------------- | :------------------ |\n| CVRP | 16.10 (3.72%) | **16.04 (3.30%)** | 67.73 (9.11%) | **64.61 (4.09%)** | 134.22 (12.28%) | **124.44 (4.09%)** |\n| VRPTW | 26.13 (7.32%) | **26.13 (7.32%)** | 108.71 (19.98%) | **99.05 (9.31%)** | 224.93 (35.12%) | **184.92 (11.09%)** |\n| VRPB | **12.30 (2.74%)** | 12.38 (3.41%) | 49.90 (4.49%) | **45.99 (-3.70%)** | 101.76 (14.88%) | **86.99 (-1.78%)** |\n| VRPL | 16.16 (3.67%) | **16.12 (3.45%)** | 68.59 (7.94%) | **65.48 (3.03%)** | 136.22 (11.03%) | **126.66 (3.25%)** |\n| OVRP | **10.38 (6.95%)** | 10.46 (7.19%) | 42.23 (19.63%) | **38.89 (10.17%)** | 83.33 (26.07%) | **72.70 (9.98%)** |\n| OVRPTW | 15.25 (9.29%) | **15.08 (8.07%)** | 64.82 (34.61%) | **53.89 (11.91%)** | 137.34 (65.50%) | **93.96 (13.22%)** |\n| OVRPB | 9.72 (16.15%) | **9.27 (10.81%)** | 33.97 (13.32%) | **30.45 (1.58%)** | 64.87 (18.23%) | **56.92 (3.73%)** |\n| OVRPL | **10.34 (6.95%)** | 10.44 (7.95%) | 41.59 (19.87%) | **38.43 (10.76%)** | 82.84 (26.68%) | **72.78 (11.31%)** |\n| VRPBL | **12.37 (2.91%)** | 12.54 (4.32%) | 49.70 (3.69%) | **45.67 (-4.72%)** | 100.72 (12.14%) | **86.28 (-3.95%)** |\n| VRPBTW | **27.64 (8.79%)** | 28.49 (12.12%) | 111.25 (13.78%) | **103.85 (6.21%)** | 245.08 (25.89%) | **209.82 (7.77%)** |\n| VRPLTW | **26.23 (7.32%)** | 26.35 (7.81%) | 109.92 (19.65%) | **100.40 (9.30%)** | 230.50 (31.87%) | **192.41 (10.08%)** |\n| OVRPBL | 9.70 (16.22%) | **9.41 (12.75%)** | 33.94 (14.65%) | **31.42 (6.14%)** | 64.61 (18.97%) | **59.25 (9.11%)** |\n| OVRPBTW | **16.40 (14.02%)** | 16.74 (16.39%) | 65.54 (26.32%) | **56.02 (7.98%)** | 138.67 (52.61%) | **99.20 (9.18%)** |\n| OVRPLTW | 15.30 (9.25%) | **15.26 (8.95%)** | 64.61 (34.68%) | **53.56 (11.65%)** | 137.44 (64.24%) | **95.33 (13.92%)** |\n| VRPBLTW | 27.97 (10.36%) | **29.13 (14.96%)** | 116.66 (13.08%) | **110.33 (6.94%)** | 239.00 (26.25%) | **205.52 (8.56%)** |\n| OVRPBLTW | **16.24 (13.98%)** | 16.95 (18.93%) | 65.94 (25.91%) | **57.15 (9.13%)** | 138.73 (50.53%) | **101.64 (10.29%)** |\n---\n\n### W4: Formatting Issues\n\nThank you for your comments; we will fix all formatting issues.\n\n---\n\n### Q2: Generalization to Dynamic Constraint Problems\n\nThank you very much for this valuable suggestion. While our heavy decoder's dynamic 're-encoding' concept naturally aligns with dynamic VRPs, adapting our current static model poses significant challenges. It's not a simple fine-tuning; it requires fundamental architectural changes for dynamic input and, crucially, building a new simulation environment for retraining from scratch. This is a substantial undertaking we can't complete now, but it's a valuable direction for future research.\n\n---\n\n### Q3: Different Sized Subsets for R3C\n\nThank you very much for this insightful question. To understand how different subset sizes affect our R3C strategy, we ran an extra experiment. We systematically compared fixed sampling lengths (10, 20, 30, 40, 50) against our paper's random size strategy on 100-node instances for four core VRP variants. As Table 3 details, all results reflect performance after 50 iterations.\n\nThe results clearly show that a random subset size strategy consistently outperforms fixed sizes across all tested problems, delivering the best performance. We believe this is because random sizes generate a more diverse range of subproblems. Fixed sizes can lead the model to get stuck in local optima by repeatedly processing similar structures, while random sizes help it escape local optima and find better solutions.\n\nTable 3: Results after 50 iterations of R3C with different sampling lengths on scale 100\n\n| **Problem** | **subset=10** | **subset=20** | **subset=30** | **subset=40** | **subset=50** | **random** |\n| :---------- | :------------ | :------------ | :------------ | :------------ | :------------ | :--------- |\n| CVRP | 16.01 | 15.96 | 15.94 | 15.91 | 15.91 | **15.88** |\n| OVRP | 10.34 | 10.25 | 10.21 | 10.17 | 10.20 | **10.17** |\n| VRPL | 16.09 | 16.03 | 16.00 | 15.97 | 15.98 | **15.90** |\n| VRPTW | 26.02 | 25.86 | 25.77 | 25.65 | 25.69 | **25.55**|\n\n\n[1] Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. Cada: Cross-problem routing solver with constraint-aware dual-attention. ICML, 2025.\n\n[2] Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Junyoung Park, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems. ArXiv, 2024. \n\n[3] Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. NeurIPS, 2022.\n\n---\n\nOnce again, we would like to express our heartfelt gratitude for the time and effort you've dedicated to reviewing our work. We sincerely hope that our response can address your concerns."}, {"review_id": "o2IJnBqodx", "reviewer": "Reviewer_sUQS", "summary": "This paper proposes a knowledge distillation-based multi-task VRP solver (MTL-KD) aimed at addressing the generalization limitations of existing methods when handling large-scale VRP problems. MTL-KD employs a lightweight encoder–heavy decoder (LEHD) architecture to train multiple teacher models and transfers their knowledge to a decoder model through knowledge distillation, enabling efficient label-free training and improved generalization. In addition, the paper introduces a Random Reordering Reconstruction (R3C) strategy to further enhance model performance.", "questions": "1.\tThe training process of the student model, particularly how it distills and incorporates knowledge from the teacher models, is not clearly described. The current explanation may leave readers uncertain about the effectiveness and implementation details of the knowledge distillation mechanism. Try to make the training procedure of the student model more explicit in both the textual description and the framework figure.\n2.\tThe encoder used in the current model may not fully capture the complex spatial and relational structures present in large-scale VRP instances. This may limit the model’s expressiveness and scalability. Have the authors considered employing graph-based encoder architectures (e.g., GNNs) to better model the underlying structure of the problem? A discussion or experiment in this direction could enhance the technical depth and applicability of the approach.\n3.\tSome figures, especially in the ablation study section, contain text that is too small to read clearly. This affects the readability and interpretability of the experimental results. Improve the visual clarity of these figures would make the paper more accessible and reader-friendly.", "limitations": "The paper does not explicitly discuss the computational overhead introduced by simultaneously training multiple teacher models alongside the student model. This process is likely to incur significant training costs, which may limit the practicality of the approach in resource-constrained settings. It would be helpful for the authors to provide a discussion on whether this overhead is acceptable. Including such analysis would improve the transparency and practical relevance of the method.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n•\tQuality: The paper is technically sound and addresses an interesting and practical problem. It introduces a knowledge distillation-based approach to tackle the challenges of training models under multi-variant conditions and limited data availability. Experimental results demonstrate that the proposed MTL-KD model achieves strong performance on training tasks, unseen tasks, and real-world datasets, validating its effectiveness and practicality. Moreover, the authors conduct extensive comparative and ablation studies to verify the model's design.\n•\tClarity: The paper is well-structured, and the writing is fluent. The experimental results and conclusions are clearly articulated. Detailed descriptions of the model architecture and experimental setup help readers understand the main contributions. In addition, the use of well-designed diagrams enhances the clarity of the proposed architecture and the applied optimizations.\n•\tSignificance: The findings of this study are significant for both the VRP and Neural Combinatorial Optimization (NCO) communities. The proposed MTL-KD model demonstrates advantages in both performance and generalization, offering a novel approach to solving large-scale VRP problems.\n•\tOriginality: The paper applies knowledge distillation techniques to the VRP domain and introduces a novel Random Reordering Reconstruction (R3C) strategy, showcasing a degree of innovation.\nWeaknesses\n•\tThe encoder architecture used in the current model appears relatively simplistic for capturing the intricate relational structures present in large-scale VRP problems. This might hinder the model’s overall representational capacity and performance.\n•\tThe description of the training process for the student model is somewhat unclear, which may lead to confusion regarding its training effectiveness. Additionally, the text in the ablation study figures is too small and difficult to read.\nSuggestions\n•\tConsider exploring more powerful encoder designs, such as graph neural network-based encoders, to improve scalability and performance.\n•\tImprove the clarity of the figures, particularly in the ablation study section, and provide a clearer explanation of the student model training process.\nOverall, this paper demonstrates notable strengths in terms of quality, clarity, significance, and originality. However, there are still some areas that require improvement.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer sUQS,\n\nThank you for your insightful comments and questions regarding our paper. We truly appreciate your thorough review and value your feedback, which has helped us enhance our presentation and technical depth. We address your points in detail below.\n\n---\n\n### Weakness 1 & Question 2: Encoder Architecture and Scalability\nThank you very much for raising these concerns. We would like to make the following clarification to address your concerns.\n\n**W1:** The encoder architecture used in the current model appears relatively simplistic for capturing the intricate relational structures present in large-scale VRP problems. This might hinder the model’s overall representational capacity and performance. Consider exploring more powerful encoder designs, such as graph neural network-based encoders, to improve scalability and performance.\n\n**Q2:** The encoder used in the current model may not fully capture the complex spatial and relational structures present in large-scale VRP instances. This may limit the model’s expressiveness and scalability. Have the authors considered employing graph-based encoder architectures (e.g., GNNs) to better model the underlying structure of the problem? A discussion or experiment in this direction could enhance the technical depth and applicability of the approach.\n\nThank you for raising this excellent point, which touches upon a core design choice in neural combinatorial optimization: how should model complexity be distributed between the encoder and decoder? The prevalent heavy-encoder-light-decoder paradigm relies on a powerful encoder (such as the GNN you suggested) to generate information-dense static node representations. However, as discussed in our paper, such static representations struggle to capture the dynamic changes during the solving process when faced with large-scale problems, thereby limiting their generalization ability.\n\nIn contrast, we adhere to a \"Light-Encoder-Heavy-Decoder\" (LEHD) design. The core idea is that a concise encoder is only responsible for basic feature extraction, while the true \"intelligence\" is embedded within a powerful heavy decoder. At each decoding step, the heavy decoder dynamically and iteratively re-evaluates and models the complex relationships among the remaining nodes based on the partially formed solution. This dynamic modeling approach has been proven to possess stronger generalization capabilities when handling large-scale problems.\n\nTo further validate our design philosophy—that in the LEHD architecture, performance is primarily driven by the heavy decoder—we conducted an additional ablation study. We replaced our existing single-layer Transformer encoder with a more basic Multi-Layer Perceptron (MLP) encoder and re-evaluated the model's performance. The experimental results are shown in the table below:\n\n| Pro. | scale=100 | scale=100 | scale=500| scale=500| scale=1000| scale=1000  |\n| :--- | :----------------------- | :--------------------- | :----------------------- | :--------------------- | :----------------------- | :--------------------- |\n|      | MTLKD(MLP)               | MTLKD                  | MTLKD(MLP)               | MTLKD                  | MTLKD(MLP)               | MTLKD                  |\n| CVRP | 16.05 (3.37%)            | **16.04 (3.30%)**         | 64.63 (4.13%)            | **64.61 (4.09%)**          | **124.09 (3.80%)**           | 124.44 (4.09%)         |\n| VRPTW| 26.14 (7.37%)            | **26.13 (7.32%)**          | **99.04 (9.30%)**            | 99.05 (9.31%)          | 184.97 (11.12%)          | **184.92 (11.09%)**        |\n| VRPBL| 12.54 (4.33%)            | **12.54 (4.32%)**          | **45.59 (-4.88%)**           | 45.67 (-4.72%)         | 85.82 (-4.46%)           | **86.28 (-3.95%)**         |\n| VRPLTW| 26.38 (7.93%)            | **26.35 (7.81%)**          | 100.52 (9.42%)           | **100.40 (9.30%)**         | 192.61 (10.20%)          | **192.41 (10.08%)**        |\n| VRPBTW| 28.50 (12.16%)           | **28.49 (12.12%)**         | 104.27 (6.64%)           | **103.85 (6.21%)**         | 210.32 (8.03%)           | **209.82 (7.77%)**         |\n\nThe results clearly demonstrate that even with the encoder simplified to an MLP, the overall model performance shows only minor changes. This strongly supports that, within our LEHD framework, the encoder's structure is not the performance bottleneck, and its role is relatively limited. Therefore, designing a GNN or other complex encoder architectures for our model is not only unnecessary but also inconsistent with our architectural philosophy, which aims to highlight the decoder's role.\n\n---\n\n### Weakness 2 & Questions 1 & 3: Clarity of Training Process and Figure Readability\nThank you very much for raising these comments. We would like to make the following clarification to address your concerns.\n\n**W2:** The description of the training process for the student model is somewhat unclear, which may lead to confusion regarding its training effectiveness. Additionally, the text in the ablation study figures is too small and difficult to read.\n\n**Q1:** The training process of the student model, particularly how it distills and incorporates knowledge from the teacher models, is not clearly described. The current explanation may leave readers uncertain about the effectiveness and implementation details of the knowledge distillation mechanism. Try to make the training procedure of the student model more explicit in both the textual description and the framework figure.\n\n**Q3:** Some figures, especially in the ablation study section, contain text that is too small to read clearly. This affects the readability and interpretability of the experimental results. Improve the visual clarity of these figures would make the paper more accessible and reader-friendly.\n\nThank you very much for pointing out the lack of clarity in the student model's training process description. We appreciate you highlighting this, as ensuring the transparency of our methodology is paramount. To help readers more accurately understand our multi-teacher knowledge distillation mechanism, we have elaborated on the training procedure as follows and have revised the text and figures accordingly in the final manuscript.\n\nIn a training batch, we first construct instances that simultaneously include all N=6 types of visible VRP tasks. At any decoding step $t$, the student model $S$ outputs a unified probability distribution $\\pi_{\\theta^S}(a_t|s_t, \\mathcal{G})$ based on the shared state $s_t$ of all instances. Concurrently, for each instance in the batch, we invoke its task-specific \"expert\" teacher model to perform a parallel forward pass under the exact same state $s_t$, thereby obtaining its guiding probability distribution. For example, a CVRP instance is guided by the CVRP teacher, and a VRPTW instance by the VRPTW teacher. Our objective is to align the student's behavior with the corresponding teacher's output by minimizing the KL divergence between them. The total loss is the sum of losses for all instances across all decoding steps within the batch. By optimizing this objective, the student model's single parameter set is driven to learn a unified policy that can imitate the respective experts based on different task types.\n\n---\n\nOnce again, we would like to express our heartfelt gratitude for the time and effort you've dedicated to reviewing our work. We sincerely hope that our response can address your concerns."}, {"review_id": "f49fSVhaF9", "reviewer": "Reviewer_zdRP", "summary": "The paper presents an extension of Neural Combinatorial Optimization (NCO).\n\nThe proposed approach considers smaller instances and multiple smaller and easier models trained on the smaller problems.\n\nThe smaller models are trained first (pre-trained models).\n\nThen the final model is trained in a way similar to multi-task learning, where the largest model has an extended loss function that includes all the instances and the associated small pre-trained models, at the same time.", "questions": "The smaller models represent different types of problems; for example, VRP with or without Time windows. \n\nWhy should the method take advantage of the instances of other types of problems?", "limitations": "The approach does not seem to have any criticality, so there does not seem to be a necessity for a limitation session.  \n\nThe authors describe the limitations of the work in the last session.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths :\n1. From the experimental session, it is possible to see that the method produces better solutions\n2. The paper describes the protocol for training that is relatively intuitive\n3. relatively extensive experiments and comparison with other baselines\n\nWeaknesses\n1. The method uses many known results (MTL, NCO, knowledge distillation), and does not appear to be very innovative", "was_revised": true, "final_justification": "I have not changed my score. In my initial review, I did not fully understand the context.\n\nThe paper has two contributions: 1) the use of knowledge distillation to train the multi-task LDHE, 2) the use of data augmentation with a variant of the partial solutions reconstruction.\n\nThe paper then shows improved results with the state-of-the-art models.\n\nOn one side, I think the paper has a proper contribution; on the other side, the presentation of the information is confusing and not self-contained.", "rebuttal": "Dear Reviewer zdRP,\n\nThank you very much for your thorough review and valuable feedback on our work. We have carefully considered your comments and would like to provide detailed elaborations and clarifications for the points you raised.\n\n---\n\n### Weakness 1: The method uses many known results (MTL, NCO, knowledge distillation), and does not appear to be very innovative.\n\nThank you very much for raising this concern. We fully understand the reviewer's concern regarding innovation. As we elaborate below, the innovation of our work does not lie in inventing isolated techniques, but rather in **synthesizing them through a novel architecture and strategy** to effectively solve a series of critical challenges, from model training to inference.\nSpecifically:\n\n+ Firstly, concerning the **training paradigm**, our core innovation validates that in the NCO domain, **knowledge distillation (KD) can be leveraged to allow multiple easy-to-train single-task \"teacher\" models to provide label-free guidance to a unified, heavy-decoder multi-task \"student\" model.** Previously, heavy decoders were difficult to apply efficiently in multi-task scenarios due to their reliance on training labels. Our design **is the first to enable this technical path**, and its architectural innovation is a core value of our work.\n\n+ Secondly, regarding the **inference strategy**, our proposed **R3C (Random Reordering Re-Construct) is entirely new**. Existing reconstruction methods (e.g., RRC) primarily rely on \"flipping\" sub-paths to increase diversity. However, this has limited effectiveness and can even disrupt the feasibility of certain VRP tasks (e.g., VRPTW). The core innovation of R3C lies in **randomly reordering the external sequence of various sub-paths**. This creates far more diverse sub-problems at a structural level than \"flipping,\" more effectively helping the model escape local optima and further improving performance.\n\n---\n\n### Question 1: The smaller models represent different types of problems; for example, VRP with or without Time windows. Why should the method take advantage of the instances of other types of problems?\n\nThank you very much for raising this crucial question about leveraging cross-task data. The motivation behind our work to build a unified multi-task model is precisely to address the fundamental limitations of single-task methods in generalization ability and real-world applications.\n\n1.  **Zero-Shot Generalization:** By co-training on diverse VRP variants, the model is compelled to learn a more **generic problem representation** rather than \"overfitting\" to specific constraints. This understanding of the problem's inherent structure enables it to perform **zero-shot generalization** to new tasks (i.e., new combinations of constraints) not encountered during training. This is crucial for tackling the ever-emerging challenges in the real world.\n2.  **Practicality and Scalability:** From a practical perspective, real-world routing problems are often complex combinations of various constraints. Maintaining a single-task model for every possible combination would lead to a \"combinatorial explosion,\" making deployment and maintenance impractical. A **unified model significantly simplifies engineering processes**, offering a more flexible and scalable solution, making its widespread application in industry possible.\n\n---\n\nOnce again, we would like to express our heartfelt gratitude for the time and effort you've dedicated to reviewing our work. We sincerely hope that our response can address your concerns."}]

Author rebuttal:

Meta-review: This paper introduces a multi-task learning framework which uses knowledge distillation to train a single neural solver that can generalize to multiple variants of the Vehicle Routing Problem (VRP).

The reviewers agreed that the paper is well-written, and the method is technically sound with strong empirical results. The initial concerns were around the lack of some baselines, the clarity of the training process, and a more fundamental critique on the value of neural solvers given their performance gap with traditional exact methods. The authors addressed nearly all concerns with additional results. 
Although there was a criticism about the ML-based approach given the existence of exact algorithms, I believe that Neural Combinatorial Optimization (NCO) is generally a well-established research field. Thus, it is not a sufficient reason to reject a paper.

Given the paper's technical contributions and comprehensive empirical validation, I recommend acceptance. I encourage the authors to incorporate a more detailed motivation for NCO in their camera-ready version to address the broader context raised by Reviewer 6wtN.
Decision: Accept (poster)