A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems
Abstract 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 computa...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-08-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s44443-025-00127-x |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Abstract 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. |
|---|---|
| ISSN: | 1319-1578 2213-1248 |