Initial Result of Clustering Strategy to Euclidean TSP

February 17, 2012 in Optimasi, Prosiding, Sendiri

Fajar, A.;   Abu, N.A.;   Herman, N.S.;
Fac. of Inf. & Commun. Technol., Univ. Teknikal Malaysia, Ayer Keroh, Malaysia

This paper appears in: Soft Computing and Pattern Recognition, 2009. SOCPAR ’09. International Conference of


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.

Leave a reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code lang=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" extra="">