Comparative analysis of enhanced metaheuristics for the colored traveling salesman problem

The Colored Traveling Salesman Problem (CTSP) is a complex combinatorial optimization problem that extends the classical Traveling Salesman Problem by incorporating multiple salesmen and color constraints. In this study, we first enhance existing metaheuristic algorithms for CTSP—Genetic Algorithm (GA), Novel Genetic Algorithm (NGA), and Ant Colony Optimization (ACO)—by greedy nearest-neighbor initialization and integrating 2-opt local search and Simulated Annealing (SA) to improve solution quality and computational efficiency. The 2-opt local search intensifies solution refinement, while SA facilitates escape from local optima through probabilistic acceptance of worse solutions. Together, they balance exploration and exploitation to improve convergence and solution quality. We then perform a comprehensive comparative analysis of the enhanced algorithms across a diverse set of benchmark CTSP instances, ranging in size from 21 to 1002 cities with salesmen 2 to 25. Experimental results on 30 small, medium and large scale CTSP instances confirm that 2-opt significantly strengthens local search across all algorithms. GA benefits most from 2-opt alone and with SA step provided only marginal gains, achieving superior performance in both solution quality and computational efficiency. In contrast, NGA and ACO perform better with the combined use of SA and 2-opt, which helps overcome local minima and achieve higher-quality solutions. However, the inclusion of SA leads to increased computational time, particularly in medium-scale instances. These findings establish 2-opt as a critical enhancement and underscore SA’s strategic value—particularly when paired with NGA and ACO—for effectively addressing complex CTSP scenarios.