Clustering Strategy to Euclidean TSP Hamilton Path Role in Tour Construction

摘要

TSP arises in many applications such as transportation, manufacturing and various logistics and scheduling. This problem has caught much attention of mathematicians and computer scientists. A clustering strategy will decompose TSP into subgraphs and form clusters, so it may reduce problem size into smaller problem. The primary objective of this research is to produce a better clustering strategy that fit into Euclidean TSP. Hamilton path play important role to construct Euclidean TSP tour in this approach. Hamilton will be applied within clusters or inter clusters. Hamilton path construction will be proceed after clustering process, followed by producing inter cluster connection algorithm to find global tour. This approach is capable of producing fast solution result with error less than 10% compare to best known solution in TSPLib. This paper proposes an improvement to a hierarchical clustering algorithm in searching for Euclidean TSP solution.