# iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 47 references that are in the map.
- First posted on arXiv 1 May 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Backpropagation through the Void: Optimizing control variates for black-box gradient estimation](https://mlsanity.com/paper/1711.00123/) (2017)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Implicit Reparameterization Gradients](https://mlsanity.com/paper/1805.08498/) (2018)
- [Interpolated Policy Gradient: Merging On-Policy and Off-Policy Gradient Estimation for Deep Reinforcement Learning](https://mlsanity.com/paper/1706.00387/) (2017)
- [iPlanner: Imperative Path Planning](https://mlsanity.com/paper/2302.11434/) (2023)
- [ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning](https://mlsanity.com/paper/2106.03051/) (2021)
- [Control Variates for Stochastic Gradient MCMC](https://mlsanity.com/paper/1706.05439/) (2017)
- [Using Large Ensembles of Control Variates for Variational Inference](https://mlsanity.com/paper/1810.12482/) (2018)
- [iSLAM: Imperative SLAM](https://mlsanity.com/paper/2306.07894/) (2023)
- [A Comprehensive Survey on the Multiple Travelling Salesman Problem: Applications, Approaches and Taxonomy](https://mlsanity.com/paper/2102.12772/) (2021)
- [Multi-Source Causal Inference Using Control Variates](https://mlsanity.com/paper/2103.16689/) (2021)
- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Algorithms for Routing an Unmanned Aerial Vehicle in the presence of Refueling Depots](https://mlsanity.com/paper/1304.0494/) (2013)

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

- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)
- [CAMO: A Conditional Neural Solver for the Multi-objective Multiple Traveling Salesman Problem](https://mlsanity.com/paper/2603.19074/) (2026)
- [NaviFormer: A Deep Reinforcement Learning Transformer-like Model to Holistically Solve the Navigation Problem](https://mlsanity.com/paper/2604.16967/) (2026)
- [Neuro-Symbolic Learning for Long-Horizon Task Planning Under Complex Logical Constraints](https://mlsanity.com/paper/2606.06877/) (2026)

## Abstract (arXiv)

This paper considers a Min-Max Multiple Traveling Salesman Problem (MTSP), where the goal is to find a set of tours, one for each agent, to collectively visit all the cities while minimizing the length of the longest tour. Though MTSP has been widely studied, obtaining near-optimal solutions for large-scale problems is still challenging due to its NP-hardness. Recent efforts in data-driven methods face challenges of the need for hard-to-obtain supervision and issues with high variance in gradient estimations, leading to slow convergence and highly suboptimal solutions. We address these issues by reformulating MTSP as a bilevel optimization problem, using the concept of imperative learning (IL). This involves introducing an allocation network that decomposes the MTSP into multiple single-agent traveling salesman problems (TSPs). The longest tour from these TSP solutions is then used to self-supervise the allocation network, resulting in a new self-supervised, bilevel, end-to-end learning framework, which we refer to as imperative MTSP (iMTSP). Additionally, to tackle the high-variance gradient issues during the optimization, we introduce a control variate-based gradient estimation algorithm. Our experiments showed that these innovative designs enable our gradient estimator to converge 20% faster than the advanced reinforcement learning baseline and find up to 80% shorter tour length compared with Google OR-Tools MTSP solver, especially in large-scale problems (e.g. 1000 cities and 15 agents).