Research map / Label-efficient and robust learning / Knowledge distillation
MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Distills six single-task POMO-style RL teachers into one multi-task heavy-decoder (LEHD-style) student for VRP variants via label-free KD, plus a Random Reordering Re-Construct (R3C) inference strategy.
Problem
Multi-task neural VRP solvers mostly use heavy-encoder light-decoder models that generalize poorly to large instances, while heavy-decoder models are too costly to train with RL and lack labeled data for multi-task training.
Approach
Train one RL teacher per seen VRP variant, then distill their per-step action distributions into a single multi-task heavy-decoder student (KL divergence, label-free), and improve inference with R3C, which randomly reorders subtours before re-optimizing random-length segments.
Key results
- On seen tasks at n=1k, MTL-KD(R3C200) reaches 2.10% gap on CVRP and 1.56% on VRPL versus 14.28% for MT-POMO(M+aug8) and 12.86% for RF-MVMoE on VRPTW-type comparisons (CVRP 1k: 2.10% vs 11.08% RF-Transformer).
- On unseen tasks, MTL-KD(R3C200) achieves -8.08% gap on VRPBL at n=1k and -4.48% on OVRPB at n=1k (i.e., better than HGS-PyVRP) while MVMoE(M+aug8) has 62.10% and 98.81% gaps.
- Average gap across unseen tasks at n=1000 for MTL-KD (KD) is 13.33% versus 62.22% for the RL-trained heavy decoder (MTL-RL).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train the heavy decoder with knowledge distillation rather than reinforcement learning (ablation) | MTL heavy decoder · Seen tasks, n=1000 | average gap: 50.0606% -> 6.6413% | Helped |
| train the heavy decoder with knowledge distillation rather than reinforcement learning (ablation) | MTL heavy decoder · Unseen tasks, n=1000 | average gap: 62.2226% -> 13.3322% | Helped |
| use random rather than fixed re-optimization segment lengths (ablation) | R3C · 100-node CVRP, OVRP, VRPL, and VRPTW | objective value: CVRP: 15.91 -> 15.88; OVRP: 10.17 -> 10.17; VRPL: 15.97 -> 15.90; VRPTW: 25.65 -> 25.55 | Helped |
| randomly reorder subtour external order before segment sampling (ablation) | R3C · CVRP, VRPL, OVRP, and VRPTW at scale 100 | iterative solution quality | Helped |
| add random flipping to random reordering (ablation) | R3C on CVRP and VRPL · CVRP and VRPL at scale 100 | iterative solution quality | No clear effect |
Surprising findings
- The multi-task student generalizes across scales better than its single-scale POMO teachers, which lack cross-scale generalization.
- MTL-KD(R3C200) beats HGS-PyVRP (negative gap) on several large-scale unseen tasks such as VRPBL and OVRPB at n=500 and n=1000.
Limitations
- The heavy decoder structure results in high computational complexity.
- The method relies on pre-trained single-task RL teachers for every seen task, adding training cost.
- Results are single-run with fixed seeds; no error bars are reported.
Experimental setup
Datasets: synthetic VRP instances generated per MVMoE settings CVRPLIB Set-X Solomon VRPTW instances
Benchmarks: 16 VRP variants (6 seen, 10 unseen) at n=100, 200, 500, 1000 CVRPLIB Set-X Solomon VRPTW
Metrics: objective value gap to HGS-PyVRP
Baselines: HGS-PyVRP OR-Tools MT-POMO MVMoE RouteFinder CaDA
Builds on: POMO LEHD MVMoE RRC
Closest papers by meaning
- MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.89)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.89)
- Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP (NeurIPS 2025 · similarity 0.89)
- Distilling Autoregressive Models to Obtain High-Performance Non-autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speed (AAAI 2024 · similarity 0.88)
- DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems (ICML 2024 · similarity 0.87)
- Rethinking Light Decoder-based Solvers for Vehicle Routing Problems (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.