CLUSTERING PROCESS TO SOLVE EUCLIDEAN TSP
No Thumbnail Available
Files
Date
2010-07-10
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE PRESS
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.
Description
Keywords
Hierarchical Clustering, Euclidean TSP, Tour Construction, Adjacency