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

作　　者：Zakir Hussain Ahmed 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

出　　处：《Computer Systems Science & Engineering》2024年第5期1113-1131,共19页计算机系统科学与工程（英文）

基　　金：the Deanship of Scientific Research,Imam Mohammad Ibn Saud Islamic University(IMSIU),Saudi Arabia,for funding this research work through Grant No.(221412020).

摘　　要：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 crossovermethods 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 fromthe best-known solutions is between 0.00 and 14.07 for our investigated instances.

关 键 词：Generalized travelling salesman problem NP-HARD genetic algorithms sequential constructive crossover swap mutation 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]