文献类型：期刊文献

英文题名：Solving Colored Traveling Salesman Problem via Multi-neighborhood Simulated Annealing Search

作者：Zhou, Yangming[1,2]; Xu, Wenqiang[1]; Fu, Zhang-Hua[3,4]; Zhou, Mengchu[5,6]

机构：[1] East China University of Science and Technology, Department of Computer Science and Engineering, Shanghai, 200237, China; [2] Macau Institute of Systems Engineering, Macau University of Science and Technology, 999078, China; [3] Shenzhen Institute of Artificial Intelligence and Robotics for Society, Shenzhen, 518172, China; [4] Institute of Robotics and Intelligent Manufacturing, The Chinese University of Hong Kong, Shenzhen, Shenzhen, 518172, China; [5] New Jersey Institute of Technology, Department of Electrical and Computer Engineering, Newark, NJ, 07102, United States; [6] Department of Cyber-Physical Systems, St. Petersburg State Marine Technical University, St. Petersburg, 198262, Russia

年份：2021

外文期刊名：ICNSC 2021 - 18th IEEE International Conference on Networking, Sensing and Control: Industry 4.0 and AI

收录：EI(收录号：20221211824600)

语种：英文

外文关键词：Simulated annealing - Heuristic algorithms - Benchmarking - Local search (optimization)

摘要：A colored traveling salesman problem (CTSP) is an important variant of the well-known multiple traveling salesman problem, which uses colors to differentiate salesmen's accessibility to individual cities to be visited. As a highly useful model for some complex scheduling problems, CTSP is NP-hard. A Multi-neighborhood Simulated Annealing Search (MSAS) approach is proposed to solve it in this paper. Starting from an initial solution, it iterates through two complementary neighborhoods: intra-route and inter-route neighborhoods. Experiments on three groups of 60 widely-used benchmark instances show that it achieves highly competitive performance compared to state-of-the-art algorithms. Moreover, MSAS can be integrated into other search methods to further improve performance, which is demonstrated by using a recently proposed iterated two-phase local search. ? 2021 IEEE.