Partition-informed Ant Colony Optimization for min–max multiple TSP

The multiple traveling salesmen problem (mTSP) generalizes the classical TSP by involving multiple travelers who must collectively visit all cities, starting and ending at a common depot. This work focuses on the min–max variant, where the objective is to minimize the length of the longest subtour, ensuring a balanced workload among travelers, which is a crucial factor in many real-world applications, such as emergency response and logistics. This paper proposes a novel Ant Colony System (ACS)-based approach that effectively addresses the min–max mTSP, designed to construct well-balanced tours while optimizing the maximum tour length. The method integrates two key strategies: a sector-based heuristic for guiding city assignments, and a dynamic traveler selection criterion to promote equitable route construction. The method was evaluated on 33 two-dimensional Euclidean benchmark instances and compared with four state-of-the-art ACO-based approaches, demonstrating consistently better fitness under the min–max objective. • An ACS-based method enhances workload balance for the min–max mTSP. • A sector-based partitioning heuristic distributes cities among travellers. • The method integrates sector partitioning, local search, and adaptive selection. • Experiments confirm performance gains from the proposed contributions. • The method outperforms four state-of-the-art ACO algorithms.