Open AccessSolution of Cluster Traveling Salesman Problem using Heuristic Based Genetic Algorithm with Risk Constraint
Author(s) -
Arindam Roy
Publication year - 2019
Publication title -
international journal of innovative technology and exploring engineering
Language(s) - English
Resource type - Journals
ISSN - 2278-3075
DOI - 10.35940/ijitee.b7119.129219
Subject(s) - travelling salesman problem , hamiltonian path , mathematical optimization , hamiltonian path problem , heuristic , path (computing) , cluster (spacecraft) , mathematics , genetic algorithm , hamiltonian (control theory) , constraint (computer aided design) , algorithm , bottleneck traveling salesman problem , computer science , combinatorics , graph , geometry , programming language
This is a heuristic investigation with risk constraint for solving the traveling salesman problem (TSP) dividing given vertices (nodes) between a prespecified number of clusters. A Heuristic based Genetic Algorithm (HbGA) is applied on each cluster to produce a Hamiltonian path based on prespecified nodes of a cluster. Each cluster must have a unique set of nodes. Finally, all Hamiltonian path of each cluster together prepare a possible Hamiltonian cycle. The efficiency of our proposed algorithm has been tested for a number of symmetric TSPLIB instances of various sizes. The computational results show the proposed algorithm works well in realistic manner.