文献类型：期刊文献

英文题名：Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems

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

机构：[1]Shanghai Jiao Tong Univ, Sino US Global Logist Inst, Shanghai 200030, Peoples R China;[2]Macau Univ Sci & Technol, Macau Inst Syst Engn, Macau 999078, Peoples R China;[3]East China Univ Sci & Technol, Dept Comp Sci & Engn, Shanghai 200237, Peoples R China;[4]Chinese Univ Hong Kong Shenzhen, Inst Robot & Intelligent Mfg, Shenzhen 518172, Peoples R China;[5]Chinese Univ Hong Kong Shenzhen, Shenzhen Inst Artificial Intelligence & Robot Soc, Shenzhen 518172, Peoples R China;[6]New Jersey Inst Technol, Dept Elect & Comp Engn, Newark, NJ 07102 USA

年份：2022

卷号：23

期号：9

起止页码：16072

外文期刊名：IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS

收录：;EI(收录号：20221011758380);WOS:【SCI-EXPANDED(收录号:WOS:000767802500001)】；

基金：This work was supported in part by the Fundo Para o Desenvolvimento das Ciencias da Tecnologia (FDCT) under Grant 0047/2021/A1, in part by the National Natural Science Foundation of China under Grant 61903144, in part by the Shanghai Sailing Program under Grant 19YF1412400, in part by the Macau Young Scholars Program under Grant AM2020011, and in part by the Open Project of the Shenzhen Institute of Artificial Intelligence and Robotics for Society under Grant AC01202005002.

语种：英文

外文关键词：Urban areas; Color; Traveling salesman problems; Simulated annealing; Biological cells; Upper bound; Robots; Multi-neighborhood search; simulated annealing; iterated local search; colored traveling salesman problem

摘要：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.