Scholarlink

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

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

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月19日

查看全文
  • Zhicheng Lin,
  • Jun Li

摘要

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.