General Information
    • ISSN: 1793-8201 (Print), 2972-4511 (Online)
    • Abbreviated Title: Int. J. Comput. Theory Eng.
    • Frequency: Quarterly
    • DOI: 10.7763/IJCTE
    • Editor-in-Chief: Prof. Mehmet Sahinoglu
    • Associate Editor-in-Chief: Assoc. Prof. Alberto Arteta, Assoc. Prof. Engin Maşazade
    • Managing Editor: Ms. Mia Hu
    • Abstracting/Indexing: Scopus (Since 2022), INSPEC (IET), CNKI,  Google Scholar, EBSCO, etc.
    • Average Days from Submission to Acceptance: 192 days
    • APC: 800 USD
    • E-mail: editor@ijcte.org
    • Journal Metrics:
    • SCImago Journal & Country Rank
Article Metrics in Dimensions

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

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


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