CLUSTERING STRATEGY TO EUCLIDEAN TSP HAMILTON PATH ROLE IN TOUR CONSTRUCTION
No Thumbnail Available
Date
2010-01-22
Journal Title
Journal ISSN
Volume Title
Publisher
ICCMS - Sanya China
Abstract
TSP arises in many applications such as
transportation, manufacturing and various logistics and
scheduling. This problem has caught much attention of
mathematicians and computer scientists. A clustering strategy
will decompose TSP into subgraphs and form clusters, so it
may reduce problem size into smaller problem. The primary
objective of this research is to produce a better clustering
strategy that fit into Euclidean TSP. Hamilton path play
important role to construct Euclidean TSP tour in this
approach. Hamilton will be applied within clusters or inter
clusters. Hamilton path construction will be proceed after
clustering process, followed by producing inter cluster
connection algorithm to find global tour. This approach is
capable of producing fast solution result with error less than
10% compare to best known solution in TSPLib. This paper
proposes an improvement to a hierarchical clustering
algorithm in searching for Euclidean TSP solution.
Description
-
Keywords
Hierarchical Clustering Strategy, Hamilton Path, Euclidean TSP, Adjacency List