Solving Colored Traveling Salesman Problem via Multi-neighborhood Simulated Annealing Search

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.

I. Introduction

Consider a complete graph G = (V,E), where vertices representing cities are numbered from 0 to n−1, and each edge (i, j) ∈ E, i ≠ j is associated with weight w_ij that represents the distance between cities i and j. V can be divided into m + 1 disjoint non-empty sets: a shared city set C₀ and m exclusive city sets C₁, C₂, …, and C_m, i.e., and C_i ∩ C_j = ∅, ∀i ≠ j, where i,j ∈ {0,1,…,m}. The cities in C_k (k > 0) can only be visited by salesman k, while the cities in C₀ can be visited by anyone of m salesmen. The (depot) city c₀ belongs to C₀, and it is visited by all m salesmen. Salesman i is of color i ∈ {1,2,…,m}. All cities in C_i are colored by i, meaning that only salesman i can visit them. The objective of a colored traveling salesman problem (CTSP) is to determine m tours over G with the minimal total tour cost such that all cities of each exclusive city set must be visited exactly once by a particular salesman and all cities of the shared city set must be visited exactly once by one of the salesmen.