Paper Info
Title
IntraClusTSP - An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem.
Abstract
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.
Year
DOI
Venue
2018
10.3390/sym10120663
SYMMETRY-BASEL
Keywords
Field
DocType
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
Mathematical optimization,Combinatorics,Heuristic (computer science),Travelling salesman problem,Mathematics
Journal
Volume
Issue
ISSN
10
12
2073-8994
Citations 
PageRank 
References 
0
0.34
19
Authors
3
Name
Order
Citations
PageRank
László Kovacs134.15
Barna Laszlo Iantovics2198.47
Dimitrios K. Iakovidis3819.49