A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman Problem
This paper proposed a hierarchical hybrid algorithm for traveling salesman problem (TSP) according to the idea of divide-and-conquer. The TSP problem is decomposed into a few subproblems with small-scale nodes by density peaks clustering algorithm. Every subproblem is resolved by ant colony optimiza...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8404041/ |
| _version_ | 1818457662506926080 |
|---|---|
| author | Erchong Liao Changan Liu |
| author_facet | Erchong Liao Changan Liu |
| author_sort | Erchong Liao |
| collection | DOAJ |
| description | This paper proposed a hierarchical hybrid algorithm for traveling salesman problem (TSP) according to the idea of divide-and-conquer. The TSP problem is decomposed into a few subproblems with small-scale nodes by density peaks clustering algorithm. Every subproblem is resolved by ant colony optimization algorithm, this is the lower layer. The center nodes of all subproblems constitute a new TSP problem, which forms the upper layer. All local tours of these subproblems are joined to generate the initial global tour in the same order that the center nodes are traversed in the upper layer TSP problem. Finally, the global tour is optimized by k-Opt algorithms. Thirty benchmark instances taken from TSPLIB are divided into three groups on the basis of problem size: small-scale, large-scale, and very large-scale. The experimental result shows that the proposed algorithm can obtain the solutions with higher accuracy and stronger robustness, and significantly reduce runtime, especially for the very large-scale TSP problem. |
| first_indexed | 2024-12-14T22:46:08Z |
| format | Article |
| id | doaj.art-93ce71a252084436aa2eb391331cd088 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-14T22:46:08Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-93ce71a252084436aa2eb391331cd0882022-12-21T22:44:50ZengIEEEIEEE Access2169-35362018-01-016389213893310.1109/ACCESS.2018.28531298404041A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman ProblemErchong Liao0https://orcid.org/0000-0002-7018-5317Changan Liu1School of Control and Computer Engineering, North China Electric Power University, Baoding, ChinaSchool of Control and Computer Engineering, North China Electric Power University, Beijing, ChinaThis paper proposed a hierarchical hybrid algorithm for traveling salesman problem (TSP) according to the idea of divide-and-conquer. The TSP problem is decomposed into a few subproblems with small-scale nodes by density peaks clustering algorithm. Every subproblem is resolved by ant colony optimization algorithm, this is the lower layer. The center nodes of all subproblems constitute a new TSP problem, which forms the upper layer. All local tours of these subproblems are joined to generate the initial global tour in the same order that the center nodes are traversed in the upper layer TSP problem. Finally, the global tour is optimized by k-Opt algorithms. Thirty benchmark instances taken from TSPLIB are divided into three groups on the basis of problem size: small-scale, large-scale, and very large-scale. The experimental result shows that the proposed algorithm can obtain the solutions with higher accuracy and stronger robustness, and significantly reduce runtime, especially for the very large-scale TSP problem.https://ieeexplore.ieee.org/document/8404041/Ant colony optimizationdensity peaks clustering algorithmk-Opt algorithmtraveling salesman problem |
| spellingShingle | Erchong Liao Changan Liu A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman Problem IEEE Access Ant colony optimization density peaks clustering algorithm k-Opt algorithm traveling salesman problem |
| title | A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman Problem |
| title_full | A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman Problem |
| title_fullStr | A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman Problem |
| title_full_unstemmed | A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman Problem |
| title_short | A Hierarchical Algorithm Based on Density Peaks Clustering and Ant Colony Optimization for Traveling Salesman Problem |
| title_sort | hierarchical algorithm based on density peaks clustering and ant colony optimization for traveling salesman problem |
| topic | Ant colony optimization density peaks clustering algorithm k-Opt algorithm traveling salesman problem |
| url | https://ieeexplore.ieee.org/document/8404041/ |
| work_keys_str_mv | AT erchongliao ahierarchicalalgorithmbasedondensitypeaksclusteringandantcolonyoptimizationfortravelingsalesmanproblem AT changanliu ahierarchicalalgorithmbasedondensitypeaksclusteringandantcolonyoptimizationfortravelingsalesmanproblem AT erchongliao hierarchicalalgorithmbasedondensitypeaksclusteringandantcolonyoptimizationfortravelingsalesmanproblem AT changanliu hierarchicalalgorithmbasedondensitypeaksclusteringandantcolonyoptimizationfortravelingsalesmanproblem |