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.
Index Terms—Generalized travelling salesman problem, genetic algorithms, greedy insert mutation, partially greedy crossover.
Z. Ahmed has completed his MS from University Institute of Information Technoloty, University of Arid Agriculture Rawalpindi, Pakistan (phone: +92-345-5990300; e-mail: zaheed1@hotmail.com ).
I. Younas is full Professor at HITEC University Taxila Cantt., Taxila, Pakistan. (e-mail: iyounas101@gmail.com).
M. Zahoor obtained the degree of MS in Computer Science from UIIT, Arid Agriculture University, Rawalpindi, Pakistan. (e-mail: zahoor_51@yahoo.com).
[PDF]
Cite: Zaheed Ahmed, Irfan Younas and Muhammad Zahoor, "A Novel Genetic Algorithm for GTSP,"
International Journal of Computer Theory and Engineering vol. 2, no. 6, pp. 892-896, 2010.
