# Parametrized Multi-Agent Routing via Deep Attention Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 30 Jul 2025.

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

- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [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)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [Self-Improved Learning for Scalable Neural Combinatorial Optimization](https://mlsanity.com/paper/2403.19561/) (2024)
- [Parameterized MDPs and Reinforcement Learning Problems -- A Maximum Entropy Principle Based Framework](https://mlsanity.com/paper/2006.09646/) (2020)

## Abstract (arXiv)

We propose a scalable deep learning framework for parametrized sequential decision-making (ParaSDM), where multiple agents jointly optimize discrete action policies and shared continuous parameters. A key subclass of this setting arises in Facility-Location and Path Optimization (FLPO), where multi-agent systems must simultaneously determine optimal routes and facility locations, aiming to minimize the cumulative transportation cost within the network. FLPO problems are NP-hard due to their mixed discrete-continuous structure and highly non-convex objective. To address this, we integrate the Maximum Entropy Principle (MEP) with a neural policy model called the Shortest Path Network (SPN)-a permutation-invariant encoder-decoder that approximates the MEP solution while enabling efficient gradient-based optimization over shared parameters. The SPN achieves up to 100× speedup in policy inference and gradient computation compared to MEP baselines, with an average optimality gap of approximately 6% across a wide range of problem sizes. Our FLPO approach yields over 10× lower cost than metaheuristic baselines while running significantly faster, and matches Gurobi's optimal cost with annealing at a 1500× speedup-establishing a new state of the art for ParaSDM problems. These results highlight the power of structured deep models for solving large-scale mixed-integer optimization tasks.