# Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP

arXiv: https://arxiv.org/abs/2510.21453 · HTML: https://mlsanity.com/paper/2510.21453/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 60 of its 84 references that are in the map.
- First posted on arXiv 24 Oct 2025.

## Builds on (most cited first, 30 of 60)

- [Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time](https://mlsanity.com/paper/2203.05482/) (2022)
- [Editing Models with Task Arithmetic](https://mlsanity.com/paper/2212.04089/) (2022)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [TIES-Merging: Resolving Interference When Merging Models](https://mlsanity.com/paper/2306.01708/) (2023)
- [AdapterFusion: Non-Destructive Task Composition for Transfer Learning](https://mlsanity.com/paper/2005.00247/) (2020)
- [Merging Models with Fisher-Weighted Averaging](https://mlsanity.com/paper/2111.09832/) (2021)
- [Git Re-Basin: Merging Models modulo Permutation Symmetries](https://mlsanity.com/paper/2209.04836/) (2022)
- [Dataless Knowledge Fusion by Merging Weights of Language Models](https://mlsanity.com/paper/2212.09849/) (2022)
- [LoraHub: Efficient Cross-Task Generalization via Dynamic LoRA Composition](https://mlsanity.com/paper/2307.13269/) (2023)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [AdaMerging: Adaptive Model Merging for Multi-Task Learning](https://mlsanity.com/paper/2310.02575/) (2023)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Mixture of LoRA Experts](https://mlsanity.com/paper/2404.13628/) (2024)
- [ZipIt! Merging Models from Different Tasks without Training](https://mlsanity.com/paper/2305.03053/) (2023)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Composing Parameter-Efficient Modules with Arithmetic Operations](https://mlsanity.com/paper/2306.14870/) (2023)
- [Pushing Mixture of Experts to the Limit: Extremely Parameter Efficient MoE for Instruction Tuning](https://mlsanity.com/paper/2309.05444/) (2023)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Mixture of Cluster-conditional LoRA Experts for Vision-language Instruction Tuning](https://mlsanity.com/paper/2312.12379/) (2023)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Model Ratatouille: Recycling Diverse Models for Out-of-Distribution Generalization](https://mlsanity.com/paper/2212.10445/) (2022)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)

## Built on by (most cited first, 7 of 7)

- [AutoSOTA: An End-to-End Automated Research System for State-of-the-Art AI Model Discovery](https://mlsanity.com/paper/2604.05550/) (2026)
- [Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS](https://mlsanity.com/paper/2605.03339/) (2026)
- [Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver](https://mlsanity.com/paper/2605.10122/) (2026)
- [Enhancing Cross-Problem Vehicle Routing via Federated Learning](https://mlsanity.com/paper/2604.10652/) (2026)
- [LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers](https://mlsanity.com/paper/2607.17708/) (2026)
- [Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement](https://mlsanity.com/paper/2608.24859/) (2026)
- [When Evidence Changes the Subject: Subject-Typed Claim Licensing for Learned Routing](https://mlsanity.com/paper/2609.33505/) (2026)

## Abstract (arXiv)

Existing neural methods for multi-task vehicle routing problems (VRPs) typically learn unified solvers to handle multiple constraints simultaneously. However, they often underutilize the compositional structure of VRP variants, each derivable from a common set of basis VRP variants. This critical oversight causes unified solvers to miss out the potential benefits of basis solvers, each specialized for a basis VRP variant. To overcome this limitation, we propose a framework that enables unified solvers to perceive the shared-component nature across VRP variants by proactively reusing basis solvers, while mitigating the exponential growth of trained neural solvers. Specifically, we introduce a State-Decomposable MDP (SDMDP) that reformulates VRPs by expressing the state space as the Cartesian product of basis state spaces associated with basis VRP variants. More crucially, this formulation inherently yields the optimal basis policy for each basis VRP variant. Furthermore, a Latent Space-based SDMDP extension is developed by incorporating both the optimal basis policies and a learnable mixture function to enable the policy reuse in the latent space. Under mild assumptions, this extension provably recovers the optimal unified policy of SDMDP through the mixture function that computes the state embedding as a mapping from the basis state embeddings generated by optimal basis policies. For practical implementation, we introduce the Mixture-of-Specialized-Experts Solver (MoSES), which realizes basis policies through specialized Low-Rank Adaptation (LoRA) experts, and implements the mixture function via an adaptive gating mechanism. Extensive experiments conducted across VRP variants showcase the superiority of MoSES over prior methods.