Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Comparative analysis of enhanced metaheuristics for the colored traveling salesman problem

  • 期刊论文

  • 发表日期：

    2026年2月2日

查看全文
  • Karuna Panwar

摘要

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.