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!
|
| _version_ | 1849225874803523584 |
|---|---|
| author | Zhicheng Lin Jun Li |
| author_facet | Zhicheng Lin Jun Li |
| author_sort | Zhicheng Lin |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e1075d4d0b4c4678b8bf85bc499da987 |
| institution | Kabale University |
| issn | 1319-1578 2213-1248 |
| language | English |
| publishDate | 2025-08-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj-art-e1075d4d0b4c4678b8bf85bc499da9872025-08-24T11:53:27ZengElsevierJournal of King Saud University: Computer and Information Sciences1319-15782213-12482025-08-0137712310.1007/s44443-025-00127-xA hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problemsZhicheng Lin0Jun Li1The Ministry of Education Key Laboratory of Measurement and Control of CSE, Southeast UniversityThe Ministry of Education Key Laboratory of Measurement and Control of CSE, Southeast UniversityAbstract 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.https://doi.org/10.1007/s44443-025-00127-xColored traveling salesman problemTask schedulingHeuristicsGenetic algorithmNeighborhood search |
| spellingShingle | Zhicheng Lin Jun Li A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems Journal of King Saud University: Computer and Information Sciences Colored traveling salesman problem Task scheduling Heuristics Genetic algorithm Neighborhood search |
| title | A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems |
| title_full | A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems |
| title_fullStr | A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems |
| title_full_unstemmed | A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems |
| title_short | A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems |
| title_sort | hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems |
| topic | Colored traveling salesman problem Task scheduling Heuristics Genetic algorithm Neighborhood search |
| url | https://doi.org/10.1007/s44443-025-00127-x |
| work_keys_str_mv | AT zhichenglin ahybridgeneticalgorithmwithcyclereassemblyforsolvingcoloredtravelingsalesmanproblems AT junli ahybridgeneticalgorithmwithcyclereassemblyforsolvingcoloredtravelingsalesmanproblems AT zhichenglin hybridgeneticalgorithmwithcyclereassemblyforsolvingcoloredtravelingsalesmanproblems AT junli hybridgeneticalgorithmwithcyclereassemblyforsolvingcoloredtravelingsalesmanproblems |