Open Access

ARTICLE

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

by Zakir Hussain Ahmed^1,*, Maha Ata Al-Furhood², Abdul Khader Jilani Saudagar³, Shakir Khan⁴

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:

(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

Received 04 May 2024; Accepted 21 June 2024; Issue published 13 September 2024

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

---