Clustering Strategy to Euclidean TSP Hamilton Path Role in Tour Construction

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Fajar, A., Abu, N.A., Herman, N.S.
Format: Conference Proceeding
Language:English
Subjects:
Adjacency List
Application software
Cities and towns
Clustering algorithms
Computational modeling
Computer aided manufacturing
Computer simulation
Euclidean TSP
Hamilton Path
Hierarchical Clustering Strategy
Logistics
Polynomials
Transportation
Traveling salesman problems
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 and 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.
DOI:10.1109/ICCMS.2010.476