A Novel Genetic Algorithm for GTSP

Zaheed Ahmed, Irfan Younas, Muhammad Zahoor

Abstract

The Generalized Travelling Salesman Problem (GTSP) is a special instance of the well-known travelling salesman problem which belongs to NP-hard class of problems. In the GTSP problem which is being addressed in this research we split the set of nodes (e.g. cities) into non-overlapping subsets; where the optimal solution is a minimum cost tour visiting exactly one node from each subset. In this paper a genetic algorithm with new and innovative way of generating initial population is presented. Concepts like cluster segmentation, partially greedy crossover, greedy insert mutation and enhanced swap mechanisms are also introduced. An initial analysis of the proposed algorithm shows enhanced results in terms of optimality and computational time as compared to existing approaches.
Keywords: 
Generalized travelling salesman problem, genetic algorithms, greedy insert mutation, partially greedy crossover
Document Type: 
Journal Articles
Journal: 
International Journal of Computer Theory and Engineering
Volume: 
2
Number: 
6
Pages: 
892-896
Month: 
12
Year: 
2010
DOI: 
10.7763/IJCTE.2010.V2.258
2024 © Software Engineering For Distributed Systems Group

Main menu 2