# DeepMDV: Global Spatial Matching for Multi-depot Vehicle Routing Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 42 references that are in the map.
- First posted on arXiv 26 Nov 2024.

## Builds on (most cited first, 10 of 10)

- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy](https://mlsanity.com/paper/2308.14104/) (2023)
- [PyVRP: a high-performance VRP solver package](https://mlsanity.com/paper/2403.13795/) (2023)
- [UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.00312/) (2024)
- [Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2110.02629/) (2021)

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

- [SEAFormer: A Spatial Proximity and Edge-Aware Transformer for Real-World Vehicle Routing Problems](https://mlsanity.com/paper/2601.19395/) (2026)

## Abstract (arXiv)

The rapid growth of online retail and e-commerce has made effective and efficient Vehicle Routing Problem (VRP) solutions essential. To meet rising demand, companies are adding more depots, which changes the VRP problem to a complex optimization task of Multi-Depot VRP (MDVRP) where the routing decisions of vehicles from multiple depots are highly interdependent. The complexities render traditional VRP methods suboptimal and non-scalable for the MDVRP. In this paper, we propose a novel approach to solve MDVRP addressing these interdependencies, hence achieving more effective results. The key idea is, the MDVRP can be broken down into two core spatial tasks: assigning customers to depots and optimizing the sequence of customer visits. We adopt task-decoupling approach and propose a two-stage framework that is scalable: (i) an interdependent partitioning module that embeds spatial and tour context directly into the representation space to globally match customers to depots and assign them to tours; and (ii) an independent routing module that determines the optimal visit sequence within each tour. Extensive experiments on both synthetic and real-world datasets demonstrate that our method outperforms all baselines across varying problem sizes, including the adaptations of learning-based solutions for single-depot VRP. Its adaptability and performance make it a practical and readily deployable solution for real-world logistics challenges.