# Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2018.

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

- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning](https://mlsanity.com/paper/2106.03051/) (2021)
- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems](https://mlsanity.com/paper/2405.17272/) (2024)
- [Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning](https://mlsanity.com/paper/2209.06094/) (2022)
- [Neural Airport Ground Handling](https://mlsanity.com/paper/2303.02442/) (2023)
- [DAN: Decentralized Attention-based Neural Network for the MinMax Multiple Traveling Salesman Problem](https://mlsanity.com/paper/2109.04205/) (2021)
- [Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation](https://mlsanity.com/paper/2207.09860/) (2022)
- [Boosting Graph Search with Attention Network for Solving the General Orienteering Problem](https://mlsanity.com/paper/2109.04730/) (2021)
- [Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Size](https://mlsanity.com/paper/2201.01529/) (2022)
- [Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01443/) (2022)
- [Graph Learning-based Fleet Scheduling for Urban Air Mobility under Operational Constraints, Varying Demand & Uncertainties](https://mlsanity.com/paper/2401.04851/) (2024)
- [Bigraph Matching Weighted with Learnt Incentive Function for Multi-Robot Task Allocation](https://mlsanity.com/paper/2403.07131/) (2024)
- [A Graph-based Adversarial Imitation Learning Framework for Reliable & Realtime Fleet Scheduling in Urban Air Mobility](https://mlsanity.com/paper/2407.12113/) (2024)
- [Hierarchically Structured Scheduling and Execution of Tasks in a Multi-Agent Environment](https://mlsanity.com/paper/2203.03021/) (2022)
- [Test-Time Augmentation for Traveling Salesperson Problem](https://mlsanity.com/paper/2405.04767/) (2024)
- [Learning-aided Bigraph Matching Approach to Multi-Crew Restoration of Damaged Power Networks Coupled with Road Transportation Networks](https://mlsanity.com/paper/2506.19703/) (2025)
- [Understanding the Nature of Depth-1 Equivariant Quantum Circuit](https://mlsanity.com/paper/2511.10756/) (2025)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [EGAM: Extended Graph Attention Model for Solving Routing Problems](https://mlsanity.com/paper/2601.21281/) (2026)

## Abstract (arXiv)

While there are optimal TSP solvers, as well as recent learning-based approaches, the generalization of the TSP to the Multiple Traveling Salesmen Problem is much less studied. Here, we design a neural network solution that treats the salesmen, cities and depot as three different sets of varying cardinalities. We apply a novel technique that combines elements from recent architectures that were developed for sets, as well as elements from graph networks. Coupled with new constraint enforcing output layers, a dedicated loss, and a search method, our solution is shown to outperform all the meta-heuristics of the leading solver in the field.