Local Search Integrated Genetic Algorithms for Solving the Colored Traveling Salesman Problem
Karuna Panwar, Kusum Deep · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2025
The Colored Traveling Salesman Problem (CTSP) is a generalization of the Multiple Traveling Salesman Problem (MTSP), wherein multiple salesmen are allowed to visit cities with specific restrictions. The CTSP introduces numerous constraints, making it complex and computationally challenging for conventional optimization techniques. This work advances the field by introducing four Genetic Algorithms (GAs) designed to solve CTSP efficiently: a basic GA, GA with greedy initialization (GAG), GA enhanced by a 2-opt local search, and GAG also enhanced by 2-opt. These algorithms employ tournament selection, city crossover, and city mutation techniques. The performance of these approaches is evaluated on 20 small- and medium-scale CTSP instances and compared with existing GAs for CTSP. The results show that integrating the 2-opt algorithm significantly enhances the balance between exploration and exploitation in GAs, improving solution accuracy. Among them, GA with 2-opt is particularly effective, optimizing both the solution quality and computational efficiency.