摘要
A coloring traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem, where colors are used to differentiate salesmen's the accessibility to individual cities to be visited. As a useful model for a variety of complex scheduling problems, CTSP is computationally challenging. In this paper, we propose a Multi-neighborhood Simulated Annealing-based Iterated Local Search (MSAILS) to solve it. Starting from an initial solution, it iterates through three sequential search procedures: a multi-neighborhood simulated annealing search to find a local optimum, a local search-enhanced edge assembly crossover to find nearby high-quality solutions around a local optimum, and a solution reconstruction procedure to move away from the current search region. Experimental results on two groups of 45 medium and large benchmark instances show that it significantly outperforms state-of-the-art algorithms. In particular, it is able to discover new upper bounds for 29 instances while matching 8 previous best-known upper bounds. Hence, this work greatly advances the field of CTSP.
学科与关键词
- Iterated two-phase local search for the colored traveling salesmen problemHe, Pengfei; Hao, Jin-Kao*ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2021, 97: 104018.被引 14
- Bi-Objective Colored Traveling Salesman ProblemsXu, Xiangping; Li, Jun*; Zhou, MengChuIEEE Transactions on Intelligent Transportation Systems, 2022, 23(7): 6326-6336.被引 17
- Precedence-Constrained Colored Traveling Salesman Problem: An Augmented Variable Neighborhood Search ApproachXu, Xiangping; Li, Jun*; Zhou, Mengchu; Yu, XinghuoIEEE Transactions on Cybernetics, 2022, 52(9): 9797-9808.被引 17
