A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems

As a generalization of the well-known multiple traveling salesman problem, the Colored Traveling Salesman Problem (CTSP) can completely delineate individual salesmen’s "spheres of influence" of city visits using colors. CTSP has numerous real-world applications but remains computationally challenging. To solve this we propose a Hybrid Genetic Algorithm (HGA) that effectively combines population evolution and neighborhood search. HGA consists of four main components: (1) a path-guided initialization strategy for constructing an initial population, (2) an extended edge assembly crossover for generating high-quality offspring solutions by merging cycles formed from parent solution edges, (3) a local search process employing five color-preserving neighborhood operators to refine solutions, (4) a tabu-list-based mutation mechanism designed to diversify individual genotypes. Moreover, HGA incorporates an individual elimination mechanism that maintains population diversity by removing similar and low-fitness individuals from a population. Extensive experiments are conducted on 91 CTSP benchmark cases. The results show that HGA outperforms state-of-the-art algorithms in terms of solution quality and convergence. Notably, it achieves the best-known results in 50 cases.