Genetic Algorithms for the Multiple Travelling Salesman Problem

被引:0
作者
Al-Furhud, Maha Ata [1 ,3 ]
Ahmed, Zakir Hussain [2 ,3 ]
机构
[1] Jouf Univ, Coll Comp & Informat Sci, Dept Comp Sci, Al Jouf, Saudi Arabia
[2] Al Imam Mohammad Ibn Saud Islamic Univ IMSIU, Coll Sci, Dept Math & Stat, Riyadh, Saudi Arabia
[3] Al Imam Mohammad Ibn Saud Islamic Univ, Dept Comp Sci, Coll Comp & Informat Sci, Riyadh, Saudi Arabia
关键词
Multiple travelling salesman problem; NP-hard; genetic algorithm; sequential constructive crossover; adaptive; greedy; comprehensive; SEQUENTIAL CONSTRUCTIVE CROSSOVER;
D O I
10.14569/IJACSA.2020.0110768
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the multiple travelling salesman Problem (MTSP) that is one of the generalization of the travelling salesman problem (TSP). For solving this problem genetic algorithms (GAs) based on numerous crossover operators have been described in the literature. Choosing effective crossover operator can give effective GA. Generally, the crossover operators that are developed for the TSP are applied to the MTSP. We propose to develop simple and effective GAs using sequential constructive crossover (SCX), adaptive SCX, greedy SCX, reverse greedy SCX and comprehensive SCX for solving the MTSP. The effectiveness of the crossover operators is demonstrated by comparing among them and with another crossover operator on some instances from TSPLIB of various sizes with different number of salesmen. The experimental study shows the promising results by the crossover operators, especially CSCX, for the MTSP.
引用
收藏
页码:553 / 560
页数:8
相关论文
共 50 条
[41]   An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with a Modified Crossover Operator [J].
Hossain, Md. Sabir ;
Choudhury, Sadman Sakib ;
Hayat, S. M. Afif Ibne ;
Tanim, Ahsan Sadee ;
Kabir, Muhammad Nomani ;
Islam, Mohammad Mainul .
EMITTER-INTERNATIONAL JOURNAL OF ENGINEERING TECHNOLOGY, 2019, 7 (02) :480-493
[42]   A multi-objective genetic algorithm to solve a real life travelling salesman problem [J].
AbdulSattar, Khadija ;
Harrath, Youssef ;
Kaabi, Jihene ;
Mahjoub, Amine .
2017 9TH IEEE-GCC CONFERENCE AND EXHIBITION (GCCCE), 2018, :817-822
[43]   Application of Genetic Algorithm on Travelling Salesman Person [J].
Massinanke, Sambourou ;
Zhang ChaoZhu .
ADVANCES IN TEXTILE ENGINEERING AND MATERIALS IV, 2014, 1048 :526-530
[44]   Efficiency Analysis of Genetic Algorithm and Ant Colony Optimization Techniques for Travelling Salesman Problem [J].
Binod, Bajracharya .
PROCEEDINGS OF THE 2015 INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INTELLIGENT COMMUNICATION, 2015, 16 :263-266
[45]   UNRAVELING TRAVELLING SALESMAN PROBLEM BY GENETIC ALGORITHM USING M-CROSSOVER OPERATOR [J].
Mudaliar, Devasenathipathi N. ;
Modi, Nilesh K. .
INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING, IMAGE PROCESSING AND PATTERN RECOGNITION (ICSIPR 2013), 2013, :127-130
[46]   Comparing Performance of Evolutionary Algorithms - A Travelling Salesman Perspective [J].
Donbosco, Immanuel Savio ;
Chakraborty, Udit Kr. .
2021 11TH INTERNATIONAL CONFERENCE ON CLOUD COMPUTING, DATA SCIENCE & ENGINEERING (CONFLUENCE 2021), 2021, :182-187
[47]   Three-Part Genetic Algorithm to Optimize the Outbound Train Loading Process Using a Multiple Travelling Salesman Problem Approach [J].
Correia, Goncalo ;
Estima, Jacinto ;
Cardoso, Alberto .
INTELLIGENT DATA ENGINEERING AND AUTOMATED LEARNING - IDEAL 2024, PT II, 2025, 15347 :120-131
[48]   Comparison Metaheuristic Methods by Solving Travelling Salesman Problem [J].
Mica, Ondrej .
PROCEEDINGS OF THE 9TH INTERNATIONAL SCIENTIFIC CONFERENCE INPROFORUM: COMMON CHALLENGES - DIFFERENT SOLUTIONS - MUTUAL DIALOGUE, 2015, :161-165
[49]   Usage of the extremal algebra in solving the travelling salesman problem [J].
Pozdilkova, Alena ;
Cimler, Richard .
PROCEEDINGS OF 30TH INTERNATIONAL CONFERENCE MATHEMATICAL METHODS IN ECONOMICS, PTS I AND II, 2012, :733-738
[50]   Application of a hybrid genetic algorithm based on the travelling salesman problem in rural tourism route planning [J].
Chen, Zhijia ;
Zhang, Ping ;
Peng, Lei .
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND MATHEMATICS, 2024, 19 (01) :1-14