Research map / Architectures and efficiency / Mixture of experts
MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts
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.
Proposes MVMoE, a unified neural VRP solver built on POMO with mixture-of-experts layers in encoder and decoder plus a hierarchical gating mechanism, trained on six VRP variants and evaluated zero-shot on ten unseen variants.
Problem
Neural VRP solvers are typically designed and trained separately for each VRP variant, so they lack generality and fail to transfer zero-shot to unseen variants with different constraint combinations.
Approach
Replace FFN layers in the POMO encoder and the decoder's multi-head attention output projection with mixture-of-experts layers, and add a hierarchical gate that uses a problem-level gate to choose between a sparse MoE and a dense layer, reducing decoder compute while keeping most of the performance gain.
Key results
- On 10 unseen VRP variants, MVMoE/4E reduces average zero-shot gap relative to POMO-MTL (e.g., OVRPBTW n=100: 9.948% vs 10.453%; VRPBTW n=50: 8.600% vs 8.841%), with consistent improvements across variants.
- Average gap on trained VRPs: POMO-MTL 2.102% vs MVMoE/4E 1.925%; MVMoE/4E-L (hierarchical decoder gating) is slightly worse than MVMoE/4E but uses less computation.
- Ablation with unseen VRPs shows node-level input-choice gating performs best while expert-choice gating in the decoder hurts optimization (average gap 7.190% when MoE only in encoder).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MVMoE/4E instead of dense multi-task POMO-MTL | multi-task VRP solver · trained VRPs | average gap: 2.102% -> 1.925% | Helped |
| use hierarchical decoder gating (MVMoE/4E-L) instead of base input-choice gating (ablation) | MVMoE · trained VRPs | performance | Mixed |
| use hierarchical decoder gating (ablation) | MVMoE · large CVRPLIB instances | solution quality | Helped |
| place MoEs in shallow raw-feature processing (ablation) | MVMoE · 10 unseen VRPs | zero-shot generalization performance | Hurt |
| place MoEs in all encoder layers or in the decoder (ablation) | MVMoE · 10 unseen VRPs | zero-shot generalization performance | Helped |
| increase expert count and scale training data with it (ablation) | MVMoE · 10 unseen VRPs | zero-shot generalization performance | Helped |
| use node-level input-choice gating instead of other tested gating configurations (ablation) | MVMoE · 10 unseen VRPs | zero-shot generalization performance | Helped |
| use node-level expert-choice gating (ablation) | MVMoE · 10 unseen VRPs | zero-shot generalization performance: 7.190% average gap | Hurt |
| use MoEs only in the decoder with expert-choice gating (ablation) | MVMoE · 10 unseen VRPs | zero-shot generalization performance | Hurt |
| replace conventional gating with soft MoEs (ablation) | MVMoE decoder · n=50 zero-shot evaluation | performance | Hurt |
| use the 4-expert model instead of POMO-MTL | multi-task VRP solver · 10 unseen VRP variants | objective value | Helped |
| remove OVRPTW from multi-task training (ablation) | POMO-MTL · unseen variants combining open route and time window | zero-shot generalization performance | Hurt |
Surprising findings
- Expert-choice gating in the decoder makes MVMoE hard to optimize, and performance remains inferior to baseline even when MoEs are restricted to the encoder.
- MVMoE/4E performs poorly on large-scale CVRPLIB instances (n>500), while the hierarchical-gating variant MVMoE/4E-L generalizes better out-of-distribution.
Limitations
- Parameter scale (about 3.68M for MVMoE/4E) is far below LLM scale; authors call it a first attempt at a large VRP model.
- Performance degrades on large-scale benchmark instances (n>500), and the sparse MoE shows OOD generalization issues.
- Trained only on uniform instances of size n=100 and with a limited set of six training variants; cross-size and cross-distribution training not explored.
Experimental setup
Datasets: synthetically generated VRP instances (uniform coordinates in unit square) CVRPLIB Set-X CVRPLIB Set-Solomon
Benchmarks: 16 VRP variants (6 trained, 10 unseen) CVRPLIB Set-X CVRPLIB Set-Solomon
Metrics: objective value optimality gap time
Baselines: HGS LKH3 OR-Tools POMO POMO-MTL LEHD
Builds on: POMO sparsely-gated mixture-of-experts soft mixture-of-experts LEHD
Closest papers by meaning
- Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP (NeurIPS 2025 · similarity 0.93)
- A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver (ICML 2025 · similarity 0.90)
- MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.89)
- SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy (ICML 2025 · similarity 0.89)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.89)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.88)
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.