Ant Colony Optimization for Multiple Traveling Salesmen Problem with Revisitable Cities
Bing Sun, Wei–Jie Yu, Zi-Jia Wang, Jian-Yu Li · 2024
Multiple traveling salesmen problem (MTSP) is a widespread combinatorial optimization problem that aims to minimize the total cost of all salesmen. MTSP with revisitable cities (MTSPR) is an extension of MTSP, which considers the possibility of visiting specific cities multiple times, making it more applicable to real-world scenarios. To address the issue, this paper presents a novel ant colony optimization for MTSPR (RACO), efficiently solving MTSPR with a novel path construction strategy. Specifically, first, the problem definition of the MTSPR is presented, followed by the mathematical formulation of its constraints and optimization objectives. Then, a collaborative balanced path selection strategy is proposed, which constructs paths for all salesmen through balanced control and parallel selection to achieve efficient path construction. In addition, a 2-opt local search strategy is employed to enhance the path optimization of elite ants. Finally, experiments on TSPLIB benchmark sets show that RACO has better performance than other state-of-art algorithms in solving MTSPR.