Initial Result of Clustering Strategy to Euclidean TSP

摘要

There has been growing interest in studying combinatorial optimization problems by clustering strategy, with a special emphasis on the traveling salesman problem (TSP). Since TSP naturally arises as a sub problem in many transportation, manufacturing and various logistics application, this problem has caught much attention of mathematicians and computer scientists, A clustering strategy will decompose TSP into subgraph and form clusters, so it may reduce the TSP graph to smaller problem. The primary objective of this research is to produce a better clustering strategy that fit into Euclidean TSP. General approach for this research is to produce an algorithm for generating clusters and able to handle large size cluster. The next step is to produce Hamilton path algorithm and followed by inter cluster connection algorithm to form global tour. The significant of this research is solution result error less than 10% compare to best known solution (TSPLIB) and there is an improvement to a hierarchical clustering strategy in order to fit in such the Euclidean TSP method.