CLUSTERING PROCESS TO SOLVE EUCLIDEAN TSP

Widyatama Repository

CLUSTERING PROCESS TO SOLVE EUCLIDEAN TSP

Show full item record

Title: CLUSTERING PROCESS TO SOLVE EUCLIDEAN TSP
Author: Fajar, Abdullah; Abu, Nur Azman; Herman, Nanna Suryana
Abstract: Human is able to cluster and filter object efficiently. Clustering problem has been approached from diverse domains of knowledge like graph theory, statistics, artificial neural network and so on. There has been growing interest in studying combinatorial optimization problems by clustering approach, with a special emphasis on the Euclidean Traveling Salesman Problem. Classical ETSP appears as a fundamental problem in various problem such as transportation, manufacturing and logistics application. This study will focus on tour construction. Most of methods focus on tour improvement and using nearest neighborhood for tour construction. This paper will use clustering process to decompose ETSP into smaller sub problem. Clustering process hierarchically arrange adjacency and vertices to form clusters. A threshold of edge weight is applied to split one clusters to several sub clusters. Using this approach the running time can be cut into half compared to TSPLib standard time. The main objective is to develop best clustering process to ETSP and produce a near optimal solution within 10% of best known solution in TSPLib.
URI: http://repository.widyatama.ac.id/xmlui/handle/123456789/1393
Date: 2010-07-10


Files in this item

Files Size Format View Description
content.pdf 2.144Mb PDF View/Open content

This item appears in the following Collection(s)

Show full item record