A hybrid genetic algorithm, list-based simulated annealing algorithm, and different heuristic algorithms for travelling salesman problem

被引:17
作者
Ilin, Vladimir [1 ]
Simic, Dragan [1 ]
Simic, Svetislav D. [1 ]
Simic, Svetlana [2 ]
Saulic, Nenad [1 ]
Luis Calvo-Rolle, Jose [3 ]
机构
[1] Univ Novi Sad, Fac Tech Sci, Trg Dositeja Obradovica 6, Novi Sad 21000, Serbia
[2] Univ Novi Sad, Fac Med, Hajduk Veljkova 1-9, Novi Sad 21000, Serbia
[3] Univ A Coruna, Dept Ind Engn, Ferrol A Coruna 15405, Spain
关键词
hybrid approach; travelling salesman problem; tour construction and tour improvement algorithms; list-based simulated annealing algorithm; genetic algorithm; OPTIMIZATION ALGORITHM; SEARCH ALGORITHM; SOLVE;
D O I
10.1093/jigpal/jzac028
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The travelling salesman problem (TSP) belongs to the class of NP-hard problems, in which an optimal solution to the problem cannot be obtained within a reasonable computational time for large-sized problems. To address TSP, we propose a hybrid algorithm, called GA-TCTIA-LBSA, in which a genetic algorithm (GA), tour construction and tour improvement algorithms (TCTIAs) and a list-based simulated annealing (LBSA) algorithm are used. The TCTIAs are introduced to generate a first population, and after that, a search is continued with the GA. The problem of premature convergence of the GA to local optimum is tackled by a method called social disaster technique. Afterwards, the LBSA is applied to generate a new population based on one of two proposed operators called packing and judgement day. The proposed algorithm is implemented in the MATLAB environment, and its two variants, called GA-TCTIA-LBSA packing and GA-TCTIA-LBSA judgement day, are tested on symmetric and asymmetric instances from TSPLIB. The overall results demonstrate that the proposed GA-TCTIA-LBSAs offer promising results, particularly for small-sized instances.
引用
收藏
页码:602 / 617
页数:16
相关论文
共 38 条
[1]   A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem [J].
Alipour, Mir Mohammad ;
Razavi, Seyed Naser ;
Derakhshi, Mohammad Reza Feizi ;
Balafar, Mohammad Ali .
NEURAL COMPUTING & APPLICATIONS, 2018, 30 (09) :2935-2951
[2]   Using list-based simulated annealing and genetic algorithm for order batching and picker routing in put wall based picking systems [J].
Ardjmand, Ehsan ;
Bajgiran, Omid Sanei ;
Youssef, Eyad .
APPLIED SOFT COMPUTING, 2019, 75 :106-119
[3]  
Bansal Jagdish Chand, 2013, International Journal of Advanced Intelligence Paradigms, V5, P123
[4]   Spider Monkey Optimization algorithm for numerical optimization [J].
Bansal, Jagdish Chand ;
Sharma, Harish ;
Jadon, Shimpi Singh ;
Clerc, Maurice .
MEMETIC COMPUTING, 2014, 6 (01) :31-47
[5]   An effective hybrid harmony search for the asymmetric travelling salesman problem [J].
Boryczka, Urszula ;
Szwarc, Krzysztof .
ENGINEERING OPTIMIZATION, 2020, 52 (02) :218-234
[6]   The Harmony Search algorithm with additional improvement of harmony memory for Asymmetric Traveling Salesman Problem [J].
Boryczka, Urszula ;
Szwarc, Krzysztof .
EXPERT SYSTEMS WITH APPLICATIONS, 2019, 122 :43-53
[7]  
Brammya G., 2019, Comput J, P133, DOI [10.1093/COMJNL/BXY133, DOI 10.1093/COMJNL/BXY133, 10.1093/comjnl/bxy133]
[8]   A memetic neural network for the Euclidean traveling salesman problem [J].
Creput, Jean-Charles ;
Koukam, Abderrafiaa .
NEUROCOMPUTING, 2009, 72 (4-6) :1250-1264
[9]  
Davis L, 1985, INT JOINT C ARTIFICI, P162
[10]   A novel two-stage hybrid swarm intelligence optimization algorithm and application [J].
Deng, Wu ;
Chen, Rong ;
He, Bing ;
Liu, Yaqing ;
Yin, Lifeng ;
Guo, Jinghuan .
SOFT COMPUTING, 2012, 16 (10) :1707-1722