# A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2023.

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

- [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024)
- [Solving the Min-Max Multiple Traveling Salesmen Problem via Learning-Based Path Generation and Optimal Splitting](https://mlsanity.com/paper/2508.17087/) (2025)
- [Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization](https://mlsanity.com/paper/2506.09404/) (2025)
- [Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem](https://mlsanity.com/paper/2602.23579/) (2026)

## Abstract (arXiv)

This paper proposes a hybrid genetic algorithm for solving the Multiple Traveling Salesman Problem (mTSP) to minimize the length of the longest tour. The genetic algorithm utilizes a TSP sequence as the representation of each individual, and a dynamic programming algorithm is employed to evaluate the individual and find the optimal mTSP solution for the given sequence of cities. A novel crossover operator is designed to combine similar tours from two parents and offers great diversity for the population. For some of the generated offspring, we detect and remove intersections between tours to obtain a solution with no intersections. This is particularly useful for the min-max mTSP. The generated offspring are also improved by a self-adaptive random local search and a thorough neighborhood search. Our algorithm outperforms all existing algorithms on average, with similar cutoff time thresholds, when tested against multiple benchmark sets found in the literature. Additionally, we improve the best-known solutions for 21 out of 89 instances on four benchmark sets.