Open Access iconOpen Access

ARTICLE

Solving the Generalized Traveling Salesman Problem Using Sequential Constructive Crossover Operator in Genetic Algorithm

Zakir Hussain Ahmed1,*, Maha Ata Al-Furhood2, Abdul Khader Jilani Saudagar3, Shakir Khan4

1 Department of Mathematics and Statistics, College of Science, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, 11432, Saudi Arabia
2 Department of Computer Science, College of Computer and Information Sciences, Jouf University, Sakakah, 42421, Saudi Arabia
3 Information Systems Department, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, 11432, Saudi Arabia
4 College of Computer and Information Sciences, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, 11432, Saudi Arabia

* Corresponding Author: Zakir Hussain Ahmed. Email: email

(This article belongs to the Special Issue: Metaheuristics Optimization for Real-World Applications)

Computer Systems Science and Engineering 2024, 48(5), 1113-1131. https://doi.org/10.32604/csse.2024.053574

Abstract

The generalized travelling salesman problem (GTSP), a generalization of the well-known travelling salesman problem (TSP), is considered for our study. Since the GTSP is NP-hard and very complex, finding exact solutions is highly expensive, we will develop genetic algorithms (GAs) to obtain heuristic solutions to the problem. In GAs, as the crossover is a very important process, the crossover methods proposed for the traditional TSP could be adapted for the GTSP. The sequential constructive crossover (SCX) and three other operators are adapted to use in GAs to solve the GTSP. The effectiveness of GA using SCX is verified on some GTSP Library (GTSPLIB) instances first and then compared against GAs using the other crossover methods. The computational results show the success of the GA using SCX for this problem. Our proposed GA using SCX, and swap mutation could find average solutions whose average percentage of excesses from the best-known solutions is between 0.00 and 14.07 for our investigated instances.

Keywords


Cite This Article

APA Style
Ahmed, Z.H., Al-Furhood, M.A., Saudagar, A.K.J., Khan, S. (2024). Solving the generalized traveling salesman problem using sequential constructive crossover operator in genetic algorithm. Computer Systems Science and Engineering, 48(5), 1113-1131. https://doi.org/10.32604/csse.2024.053574
Vancouver Style
Ahmed ZH, Al-Furhood MA, Saudagar AKJ, Khan S. Solving the generalized traveling salesman problem using sequential constructive crossover operator in genetic algorithm. Comput Syst Sci Eng. 2024;48(5):1113-1131 https://doi.org/10.32604/csse.2024.053574
IEEE Style
Z.H. Ahmed, M.A. Al-Furhood, A.K.J. Saudagar, and S. Khan "Solving the Generalized Traveling Salesman Problem Using Sequential Constructive Crossover Operator in Genetic Algorithm," Comput. Syst. Sci. Eng., vol. 48, no. 5, pp. 1113-1131. 2024. https://doi.org/10.32604/csse.2024.053574



cc Copyright © 2024 The Author(s). Published by Tech Science Press.
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 484

    View

  • 98

    Download

  • 0

    Like

Share Link