You are browsing the archive for Optimasi Archives - Personal Blog Resmi Abdullah Fajar.

Hierarchical Approach in Clustering to Euclidean Traveling Salesman Problem

February 17, 2012 in Optimasi, Prosiding, Publikasi, Sendiri

Abdulah FajarNanna Suryana HermanNur Azman Abu and Sahrin Shahib

Abstract

There has been growing interest in studying combinatorial optimization problems by clustering strategy, with a special emphasis on the traveling salesman problem (TSP). TSP naturally arises as a sub problem in much transportation, manufacturing and logistics application, this problem has caught much attention of mathematicians and computer scientists. A clustering approach will decompose TSP into sub graph and form cluster, so it may reduce problem size into smaller problem. Impact of hierarchical approach will be investigated to produce a better clustering strategy that fit into Euclidean TSP. Clustering strategy to Euclidean TSP consist of two main step, there are; clustering and tour construction. The significant of this research is clustering approach solution result has error less than 10% compare to best known solution (TSPLIB) and there is improvement to a hierarchical clustering algorithm in order to fit in such Euclidean TSP solution method.

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

ABSTRACT

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.