MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver

Dear Reviewer zdRP,

Thank 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.

---

Weakness 1: The method uses many known results (MTL, NCO, knowledge distillation), and does not appear to be very innovative.

Thank 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. Specifically:

• 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.

• 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.

---

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?

Thank 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.

1. 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.
2. 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.

---

Once 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.

Dear Authors,

I would like to thank you for the clarification.

Zero-Shot Generalization

Practicality and Scalability

These are good arguments. Where do you observe them?

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

R3C (Random Reordering Re-Construct) is entirely new.

Both the previous points seem to be heavily based on LEHD. Is it correct that you do not compare with the original LEHD? why it is so? You have a session, "KD vs. RL" but both build on LEHD. Is that correct?

Looking forward to the additional clarification.

Q2: Both the previous points seem to be heavily based on LEHD. Is it correct that you do not compare with the original LEHD? why it is so? You have a session, "KD vs. RL" but both build on LEHD. Is that correct?

Thank you very much for raising these questions. We would like to make the following clarification to address your questions point-by-point.

1. The Base Model

We acknowledge that the two points mentioned are heavily based on LEHD. We select the LEHD model as the base model since it demonstrates the promising generalization ability. However, due to its reliance on supervised learning (SL)for training, it is impractical to obtain a substantial amount (e.g., one million) of near-optimal instance-solution pairs for SL to train the LEHD model on each VRP variant. It motivates us to propose the label-free MTL-KD (multi-task learning method via knowledge distillation) method to tackle this issue. Moreover, we propose R3C, which is specifically designed for the 16 VRP tasks and further boosts the performance of the multi-task model.

2. Comparison with the Original LEHD Model

We did not directly compare our model with the original single-task LEHD model on the 16 VRP variants in the main text. The main reason is that the original LEHD model is only applicable to TSP or CVRP problems, and as mentioned before, it is computationally impractical to train the LEHD model on each VRP variant. Therefore, a comprehensive comparison across all 16 VRP problems may not be possible.

Nonetheless, on the CVRP problem, we did include a comparison on a real-world dataset (CVRPLIB Set-X), with results shown in Appendix C, Table 7. This result shows that our model's gap to the baseline solution is only 6.655%, which is superior to the single-task LEHD model's 12.836% gap. This highlights our model's stronger generalization ability in real-world scenarios.

Moreover, we would like to clarify that in this paper, our primary research objective is to design a generalizable neural vehicle routing solver for the multi-task domain. Therefore, we mainly compare our MTL-KD model with the recent advanced multi-task models such as MVMoE.

3. Explanation of the "KD vs. RL" Experiment

We sincerely apologize for the misleading description "we compared the MTL-KD model with a LEHD model trained using RL" in line 217 in the subsection 'KD vs. RL'. We clarify that in this section, both models are built on the same multi-task LEHD model architecture proposed in our paper.

In this subsection 'KD vs. RL', the experiment's purpose is to compare two different training paradigms on the exact same multi-task LEHD model architecture: knowledge distillation (KD) and traditional reinforcement learning (RL). The results in Table 3 in the main paper clearly show that for heavy-decoder models, the distillation-based training paradigm of MTL-KD is far more effective than the RL method in efficiently training the multi-task LEHD model and leads to superior performance.

---

Once again, we sincerely thank you for your valuable questions and hope that our responses have adequately addressed your concerns.

Dear Reviewer zdRP,

Thank you very for the follow-up questions and for giving us the opportunity to clarify. We would like to make the following clarifications to address your questions.

Q1: Where do you observe the model's zero-shot generalization, practicality, and scalability?

In our experimental design, our unified model is trained on only 6 fundamental VRP variants of problem size $n$=100, and then is tested on a total number of 16 VRP variants of problem sizes $n$=100, 500, and 1000, with 6 seen and 10 unseen VRP variants. We compare our model with two representative baseline neural solvers, MT-POMO and MVMoE, on these unseen VRP problems with varying problem sizes from 100 to 1k. The results are shown in Tables 1 and 2 in the main paper. The above arguments, i.e., zero-shot generalization practicality, and scalability of our method are observed from these tables. For the ease of reading, we present a part of the results in the table below, which shows the results on 10 unseen VRP variants of varying problem sizes. We make the following clarification to observe the arguments.

• Zero-Shot Generalization: From these results, we can observe that without any fine-tuning or additional training, our model achieves the lowest gaps on 9 out of 10 unseen VRPs of problem size $n$=100, and achieves the lowest gaps on all 10 unseen VRPs of larger problem size $n$=500 and $n$=1000. These results demonstrate the promising zero-shot generalization ability of our model.

• Practicality: Our single unified model can handle a total number of 16 VRP variants, with 6 seen and 10 unseen. This effectively avoids the "combinatorial explosion" problem of training and maintaining a specialized model for every possible combination of constraints, which effectively reduces a substantial amount of training budget.

• Scalability: Our model, only trained in problems with size $n$=100, can effectively scale to different problem sizes $n$=500 and 1000, achieving the lowest gaps in most cases. This highlights the good scalability of our model.

Table 1: Performance in terms of gap of MTL-KD and baseline neural solvers on Ten Unseen Tasks. Gap measures the difference between solutions achieved by different methods and the solutions obtained using the classical solvers HGS or OR-Tools. The full table can be found in Table 2 in the main paper.

Dear Reviewer sUQS,

Thank 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.

---

Weakness 1 & Question 2: Encoder Architecture and Scalability

Thank you very much for raising these concerns. We would like to make the following clarification to address your concerns.

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.

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.

Thank 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.

In 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.

To 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:

The 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.

---

Weakness 2 & Questions 1 & 3: Clarity of Training Process and Figure Readability

Thank you very much for raising these comments. We would like to make the following clarification to address your concerns.

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.

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.

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.

Thank 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.

In 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.

---

Once 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.

Dear Reviewer RweB,

Thank 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：

---

W1: Clarifying "Label-Free" Methodology

Thank 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.

---

W2: Additional baselines.

Thank 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.

Table 1: Performance Comparison of RF, CaDA, and MTL-KD on seen Tasks

---

W3 & Q1: Novelty of Knowledge Distillation and Comparison to AMDKD[3]

Thank 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:

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. 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. 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.

To provide a quantitative comparison, we also reproduced a multi-task extended version of AMDKD. As Table 2 shows, our model demonstrates superior performance.

Table 2: Performance Comparison of MTL-AMDKD and MTLKD Models

---

W4: Formatting Issues

Thank you for your comments; we will fix all formatting issues.

---

Q2: Generalization to Dynamic Constraint Problems

Thank 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.

---

Q3: Different Sized Subsets for R3C

Thank 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.

The 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.

Table 3: Results after 50 iterations of R3C with different sampling lengths on scale 100

[1] Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. Cada: Cross-problem routing solver with constraint-aware dual-attention. ICML, 2025.

[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.

[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.

---

Once 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.

Dear Reviewer 6wtN,

Thank 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.

We address your concerns point-by-point as follows.

---

W1 & Q1: Why are neural solvers preferred compared to traditional VRP solvers? What are their clear benefits?

Thank 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.

Furthermore, 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.

---

W2: The proposed method uses R3C, making it similar to iterative improvement. A comparison with state-of-the-art metaheuristics is necessary.

Thank 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.

In 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.

---

Q2: Why is the Random Reordering Reconstruction (R3C) strategy used? Does this imply weak performance by the proposed neural solver?

Thank 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."

Our 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.

Table 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).

---

Limitations: Motivation of using neural solver, justification of R3C, and fairness of comparisons.

Thank 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.

Additionally, 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.

Table 2: MTLKD Performance with aug8 Augmentation under Greedy Decoding

---

Once 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.

Yeah on this issue, I also wouldn't disregard the deep learning approaches because they hold promise in advancing heuristic methods such as in [1]. And while pure neural methods still fall behind in terms of optimality gaps, they are better suited for time sensitive scenarios.

Overall, the insights gained from these approaches can be employed in hybrid heuristic architectures. And in general this is a valid direction where even exploratory research that shows what doesnt work is beneficial in itself (so long as the approach is well justified and aligns with state of the art methods in other applications etc...). Although papers that show improved performances are obviously "more relevant" in terms of publication importance.

[1] Xin, Liang, et al. "Neurolkh: Combining deep learning model with lin-kernighan-helsgaun heuristic for solving the traveling salesman problem." Advances in Neural Information Processing Systems 34 (2021): 7472-7483.