Iterated two-phase local search for the colored traveling salesmen problem

The colored traveling salesmen problem (CTSP) is a generalization of the popular traveling salesman problem with multiple salesmen. In CTSP, the cities are divided into m exclusive city sets (m is the number of salesmen) and one shared city set. The goal of CTSP is to determine a shortest Hamiltonian circuit (also called route or tour) for each of the m salesmen satisfying that (1) each route includes all cities of an exclusive city set and some (or all) cities of the shared city set, and (2) each city of the shared city set is included in one unique route. CTSP is a relevant model for a number of practical applications and is known to be computationally challenging. We present the first iterated two-phase local search algorithm for this important problem which combines a local optima exploration phase and a local optima escaping phase. We show computational results on 65 common benchmark instances to demonstrate its effectiveness and especially report 22 improved upper bounds. We make the source code of the algorithm publicly available to facilitate its use in future research and real applications.