Simulated-Annealing General Variable Neighborhood Search With Satellite Lists for Solving Colored Traveling Salesman Problems

A colored traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem (MTSP). CTSP leverages colors to distinguish the accessibility of cities to different salesmen, thereby broadening MTSP's applications in intelligent transportation, manufacturing, and logistics. It has been proven to be NP-hard, and its complexity grows exponentially with problem size. This article presents a simulated-annealing general variable neighborhood search with satellite lists (SLs), or SGV-SL, to solve large-scale CTSPs. It consists of four main procedures: pregeneration of a Delaunay candidate set, greedy construction of an initial solution, exploration of the solution space using simulated-annealing-based variable insertion and 2-opt, and partial reconstruction of the current solution to escape from local optima. Notably, we introduce a new data structure, SLs, to represent a CTSP solution in SGV-SL. They can efficiently reduce the time complexity of insertion and flip operations to a constant level, thus substantially improving SGV-SL's computational efficiency. Finally, extensive experiments are conducted on 21 general and 31 radial CTSP (RCTSP) instances. The results show that SGV-SL comprehensively outperforms state-of-the-art algorithms in both solution quality and efficiency across general CTSP instances. Its performance is also highly competitive on RCTSP ones.