Research map / Reinforcement learning / Visual and representation RL
Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP
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 SDMDP and its latent-space extension LS-SDMDP to reuse optimal basis VRP policies, implemented as MoSES, a mixture of LoRA experts with adaptive gating for multi-task VRP solving across 16 variants.
Problem
Unified neural solvers for multi-task vehicle routing problems (VRPs) fail to exploit the compositional structure of VRP variants derived from shared basis variants, and multi-task adapter approaches suffer from combinatorial explosion of variants.
Approach
Reformulate VRP states as a Cartesian product of basis state spaces (SDMDP), so each basis VRP variant has an optimal basis policy; reuse these basis policies in latent space via a learnable mixture function, implemented as frozen LoRA experts on a CVRP-pretrained backbone combined with an adaptive gating mechanism and a trainable residual LoRA.
Key results
- MoSES(RF) reduces average optimality gap over 16 VRP variants from 2.063% (RF-TE) to 1.535% at N=50 and from 3.125% to 2.782% at N=100.
- MoSES(CaDA) reduces average gap from 1.715% to 1.515% at N=50 and from 2.766% to 2.631% at N=100 compared to CaDA.
- MoSES adds moderate inference overhead, e.g., MoSES(RF) averages 5.8s vs 2.0s for RF-TE over 1K instances at N=50.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add specialized LoRA experts and adaptive gating to RF-TE | RF-TE · 16 VRP variants, N=50 | average optimality gap: 2.063% -> 1.535% | Helped |
| Add specialized LoRA experts and adaptive gating to RF-TE | RF-TE · 16 VRP variants, N=100 | average optimality gap: 3.125% -> 2.782% | Helped |
| Add specialized LoRA experts and adaptive gating to CaDA | CaDA · 16 VRP variants, N=50 | average optimality gap: 1.715% -> 1.515% | Helped |
| Add specialized LoRA experts and adaptive gating to CaDA | CaDA · 16 VRP variants, N=100 | average optimality gap: 2.766% -> 2.631% | Helped |
| Use Gated-LoRA instead of standard LoRA for specialized expert fine-tuning (ablation) | MoSES basis solvers · OVRP, VRPB, VRPL, and VRPTW at N=50 | average optimality gap | Helped |
| Use norm_softplus gating activation (ablation) | MoSES(RF) · VRP variants | average optimality gap | Helped |
| Use sigmoid gating activation (ablation) | MoSES(CaDA) · VRP variants | average optimality gap | Helped |
| Use dense routing rather than alternative routing strategies (ablation) | MoSES(RF) and MoSES(CaDA) · VRP variants | average optimality gap | Helped |
| Add the trainable LoRA residual module (ablation) | MoSES · VRP variants | average optimality gap | Helped |
| Reduce frozen expert LoRA ranks rather than the trainable LoRA rank (ablation) | MoSES(CaDA) · 16 VRP variants, N=50 | average optimality gap | Hurt |
| Reduce the trainable LoRA rank rather than frozen expert LoRA ranks (ablation) | MoSES(CaDA) · 16 VRP variants, N=100 | average optimality gap | Hurt |
Surprising findings
- Reducing the rank of the frozen basis LoRA experts hurts more than reducing the trainable residual LoRA at N=50, but the reverse holds at N=100.
- MoSES(CaDA) gains are small at N=100 (2.766% to 2.631%), and it is not uniformly better across all variants (e.g., marginal drops on CVRP and OVRPB at N=100).
Limitations
- Computational overhead from layer-wise and token-wise routing and dynamic aggregation compared with other neural solvers.
- Theoretical guarantees rely on mild assumptions (conditionally independent basis states, bijective deterministic mixture function).
- Gains over strongest baseline are modest for some settings (e.g., N=100 for CaDA-based variant).
Experimental setup
Datasets: randomly generated CVRP instances on-the-fly generated VRP variant instances
Benchmarks: 16 VRP variants (N=50, N=100) OOD capacity/distance limit/time window settings CVRPLIB X set
Metrics: average cost optimality gap total time
Baselines: HGS-PyVRP OR-Tools MTPOMO MVMoE RF-POMO RF-MoE RF-TE CaDA
Builds on: LoRA POMO MVMoE RouteFinder REINFORCE
Closest papers by meaning
- MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.93)
- A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver (ICML 2025 · similarity 0.91)
- SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver (NeurIPS 2026 · similarity 0.89)
- MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.89)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.88)
- 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.