IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem
The Symmetric Traveling Salesman Problem (sTSP) is an intensively studied NP-hard problem. It has many important real-life applications such as logistics, planning, manufacturing of microchips and DNA sequencing. In this paper we propose a cluster level incremental tour construction method called In...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-11-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/10/12/663 |
| _version_ | 1798004897709293568 |
|---|---|
| author | László Kovács László Barna Iantovics Dimitris K. Iakovidis |
| author_facet | László Kovács László Barna Iantovics Dimitris K. Iakovidis |
| author_sort | László Kovács |
| collection | DOAJ |
| description | The Symmetric Traveling Salesman Problem (sTSP) is an intensively studied NP-hard problem. It has many important real-life applications such as logistics, planning, manufacturing of microchips and DNA sequencing. In this paper we propose a cluster level incremental tour construction method called Intra-cluster Refinement Heuristic (IntraClusTSP). The proposed method can be used both to extend the tour with a new node and to improve the existing tour. The refinement step generates a local optimal tour for a cluster of neighbouring nodes and this local optimal tour is then merged into the global optimal tour. Based on the performed evaluation tests the proposed IntraClusTSP method provides an efficient incremental tour generation and it can improve the tour efficiency for every tested state-of-the-art methods including the most efficient Chained Lin-Kernighan refinement algorithm. As an application example, we apply IntraClusTSP to automatically determine the optimal number of clusters in a cluster analysis problem. The standard methods like Silhouette index, Elbow method or Gap statistic method, to estimate the number of clusters support only partitional (single level) clustering, while in many application areas, the hierarchical (multi-level) clustering provides a better clustering model. Our proposed method can discover hierarchical clustering structure and provides an outstanding performance both in accuracy and execution time. |
| first_indexed | 2024-04-11T12:30:45Z |
| format | Article |
| id | doaj.art-fa612cec68a64680a138a65de9758fb2 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-04-11T12:30:45Z |
| publishDate | 2018-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-fa612cec68a64680a138a65de9758fb22022-12-22T04:23:46ZengMDPI AGSymmetry2073-89942018-11-01101266310.3390/sym10120663sym10120663IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman ProblemLászló Kovács0László Barna Iantovics1Dimitris K. Iakovidis2Department of Information Technology, University of Miskolc, H-3515 Miskolc-Egyetemváros, HungaryDepartment of Informatics, University of Medicine, Pharmacy, Sciences and Technology of Targu Mures, R-540139 Târgu Mureș, RomaniaDepartment of Computer Science and Biomedical Informatics, University of Thessaly, GR-35131 Lamia, GreeceThe Symmetric Traveling Salesman Problem (sTSP) is an intensively studied NP-hard problem. It has many important real-life applications such as logistics, planning, manufacturing of microchips and DNA sequencing. In this paper we propose a cluster level incremental tour construction method called Intra-cluster Refinement Heuristic (IntraClusTSP). The proposed method can be used both to extend the tour with a new node and to improve the existing tour. The refinement step generates a local optimal tour for a cluster of neighbouring nodes and this local optimal tour is then merged into the global optimal tour. Based on the performed evaluation tests the proposed IntraClusTSP method provides an efficient incremental tour generation and it can improve the tour efficiency for every tested state-of-the-art methods including the most efficient Chained Lin-Kernighan refinement algorithm. As an application example, we apply IntraClusTSP to automatically determine the optimal number of clusters in a cluster analysis problem. The standard methods like Silhouette index, Elbow method or Gap statistic method, to estimate the number of clusters support only partitional (single level) clustering, while in many application areas, the hierarchical (multi-level) clustering provides a better clustering model. Our proposed method can discover hierarchical clustering structure and provides an outstanding performance both in accuracy and execution time.https://www.mdpi.com/2073-8994/10/12/663Symmetric Traveling Salesman Problemsymmetrysymmetric distance matrixNearest Neighbour methodChained Lin-Kernighan refinement algorithmIntra-cluster Refinementclusteringoptimal number of clusterssimilar elements |
| spellingShingle | László Kovács László Barna Iantovics Dimitris K. Iakovidis IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem Symmetry Symmetric Traveling Salesman Problem symmetry symmetric distance matrix Nearest Neighbour method Chained Lin-Kernighan refinement algorithm Intra-cluster Refinement clustering optimal number of clusters similar elements |
| title | IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem |
| title_full | IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem |
| title_fullStr | IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem |
| title_full_unstemmed | IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem |
| title_short | IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem |
| title_sort | intraclustsp an incremental intra cluster refinement heuristic algorithm for symmetric travelling salesman problem |
| topic | Symmetric Traveling Salesman Problem symmetry symmetric distance matrix Nearest Neighbour method Chained Lin-Kernighan refinement algorithm Intra-cluster Refinement clustering optimal number of clusters similar elements |
| url | https://www.mdpi.com/2073-8994/10/12/663 |
| work_keys_str_mv | AT laszlokovacs intraclustspanincrementalintraclusterrefinementheuristicalgorithmforsymmetrictravellingsalesmanproblem AT laszlobarnaiantovics intraclustspanincrementalintraclusterrefinementheuristicalgorithmforsymmetrictravellingsalesmanproblem AT dimitriskiakovidis intraclustspanincrementalintraclusterrefinementheuristicalgorithmforsymmetrictravellingsalesmanproblem |