# Solving the Min-Max Multiple Traveling Salesmen Problem via Learning-Based Path Generation and Optimal Splitting

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 23 Aug 2025.

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

- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Rethinking pooling in graph neural networks](https://mlsanity.com/paper/2010.11418/) (2020)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.00312/) (2024)
- [Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Context](https://mlsanity.com/paper/2306.02689/) (2023)
- [A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone](https://mlsanity.com/paper/2112.12545/) (2021)
- [Leveraging Partial Symmetry for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2401.00167/) (2023)
- [ESP: Exploiting Symmetry Prior for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2307.16186/) (2023)
- [A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem](https://mlsanity.com/paper/2307.07120/) (2023)
- [Reinforcement Learning for Solving Stochastic Vehicle Routing Problem](https://mlsanity.com/paper/2311.07708/) (2023)

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

- [A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems](https://mlsanity.com/paper/2605.14416/) (2026)

## Abstract (arXiv)

This study addresses the Min-Max Multiple Traveling Salesmen Problem (m3-TSP), which aims to coordinate tours for multiple salesmen such that the length of the longest tour is minimized. Due to its NP-hard nature, exact solvers become impractical under the assumption that P ne NP. As a result, learning-based approaches have gained traction for their ability to rapidly generate high-quality approximate solutions. Among these, two-stage methods combine learning-based components with classical solvers, simplifying the learning objective. However, this decoupling often disrupts consistent optimization, potentially degrading solution quality. To address this issue, we propose a novel two-stage framework named Generate-and-Split (GaS), which integrates reinforcement learning (RL) with an optimal splitting algorithm in a joint training process. The splitting algorithm offers near-linear scalability with respect to the number of cities and guarantees optimal splitting in Euclidean space for any given path. To facilitate the joint optimization of the RL component with the algorithm, we adopt an LSTM-enhanced model architecture to address partial observability. Extensive experiments show that the proposed GaS framework significantly outperforms existing learning-based approaches in both solution quality and transferability.