• Jun 03, 2019 News!Vol.9, No.5-Vol.10, No.3 have been indexed by EI (Inspec).   [Click]
  • Jun 18, 2021 News!Vol.13, No.3 has been published with online version.   [Click]
  • Apr 09, 2021 News!Vol.13, No.2 has been published with online version.   [Click]
General Information
Prof. Wael Badawy
Department of Computing and Information Systems Umm Al Qura University, Canada
I'm happy to take on the position of editor in chief of IJCTE. We encourage authors to submit papers concerning any branch of computer theory and engineering.
IJCTE 2010 Vol.2(6): 892-896 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2010.V2.258

A Novel Genetic Algorithm for GTSP

Zaheed Ahmed, Irfan Younas and 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.

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


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.

Copyright © 2008-2021. International Association of Computer Science and Information Technology. All rights reserved.