Submit

Login Login

Register Register

Home / Journals / CSSE / Online First / doi:10.32604/csse.2024.053574
Journal Menu
Special Issues
Table of Content

All issues

Online First

2024

2023

2022

2021

2020

2019

2018

Past Issues

Open 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 https://doi.org/10.32604/csse.2024.053574

Received 04 May 2024; Accepted 21 June 2024; Published online 10 July 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

Generalized travelling salesman problem; NP-hard; genetic algorithms; sequential constructive crossover; swap mutation

  • 64

    View

  • 5

    Download

  • 0

    Like

Related articles
Copyright© 2024 Tech Science Press
© 1997-2024 TSP (Henderson, USA) unless otherwise stated

Share Link