Traveling salesman problem (TSP) is a classic non-deterministic polynomial-hard optimization problem. Based on the characteristics of self-organizing mapping (SOM) network, this paper proposes an improved SOM network from the perspectives of network update strategy, initialization method, and parameter selection. This paper compares the performance of the proposed algorithms with the performance of existing SOM network algorithms on the TSP and compares them with several heuristic algorithms. Simulations show that compared with existing SOM networks, the improved SOM network proposed in this paper improves the convergence rate and algorithm accuracy. Compared with iterated local search and heuristic algorithms, the improved SOM network algorithms proposed in this paper have the advantage of fast calculation speed on medium-scale TSP.
ZHU Jianghui(朱江辉),YE Hanghang(叶航航), YAO Lixiu1(姚莉秀), CAI Yunze(蔡云泽)
. Algorithm for Solving Traveling Salesman Problem Based on Self-Organizing Mapping Network[J]. Journal of Shanghai Jiaotong University(Science), 2024
, 29(3)
: 463
-470
.
DOI: 10.1007/s12204-022-2517-3
[1] WANG J W, DAI G M, XIE B Q, et al. A survey of solving the traveling salesman problem [J].Computer Engineering & Science, 2008, 30(2): 72-74 (in Chinese).
[2] WANG D C. Improved genetic algorithm in the application of the TSP [J]. Journal of Liaoning Institute of Technology (Natural Science Edition), 2019, 39(4): 235-239 (in Chinese).
[3] LUO H R, XU W D, TAN Y. A discrete fireworks algorithm for solving large-scale travel salesman problem [C]//2018 IEEE Congress on Evolutionary Computation. Rio de Janeiro: IEEE, 2018: 1-8.
[4] ZHAO L, JIN X, WANG N, et al. Depth genetic algorithm solve ultra-large-scale traveling salesman problem [J]. Computer Engineering and Applications, 2009, 45(4): 56-58 (in Chinese).
[5] WANG D, WU X B, MAO X C, et al. Accurate solving hybrid algorithm for small scale TSP [J]. Systems Engineering and Electronics, 2008, 30(9): 1693-1696 (in Chinese).
[6] ZHOU X M, XU X M. Modified self-organizing map network for Euclidean travelling salesman problem [J]. Journal of Computer Applications, 2012, 32(7): 1962-
1964 (in Chinese).
[7] GUAN L, ZHANG B, HUANG D. An improved selforganizing algorithm for solving the traveling salesman problem [J]. Journal of Shanghai Second Polytechnic University, 2012, 29(1): 48-52 (in Chinese).
[8] ZHANG J, ZHOU B. Self organizing map with generalized and localized parallel competitions for the TSP [J]. Chinese Journal of Computers, 2008, 31(2): 220- 227 (in Chinese).
[9] TIAN P, WANG H, ZHANG D. Solving the travelling salesman problem by simulated annealing [J]. Journal of Shanghai Jiaotong University, 1995, 29(S1): 111-116 (in Chinese).
[10] DONG R Y, WANG S S, WANG G Y, et al. Hybrid optimization algorithm based on wolf pack search and local search for solving traveling salesman problem [J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(1): 41-47.
[11] DENG Y L, XIONG J X, WANG Q H. A hybrid cellular genetic algorithm for the traveling salesman problem [J]. Mathematical Problems in Engineering, 2021, 2021: 6697598.
[12] PHU-ANG A. An improve artificial immune algorithm for solving the travelling salesman problem [C]//2021 Joint International Conference on Digital Arts, Media and Technology with ECTI Northern Section Conference On Electrical, Electronics, Computer and Telecommunication Engineering. Cha-am: IEEE, 2021: 261-264.
[13] BAI Q Y, LI G Z, SUN Q H. An improved hybrid algorithm for traveling salesman problem [C]//2015 8th In ternational Conference on Biomedical Engineering and Informatics. Shenyang: IEEE, 2015: 806-809.
[14] AHMAD R, KIM D. An extended self-organizing map based on 2-opt algorithm for solving symmetrical traveling salesperson problem [J]. Neural Computing and Applications, 2015, 26(4): 987-994.
[15] BROCKI L, KORˇZINEK D. Kohonen self-organizing map for the traveling salesperson problem [M]//Recent advances in mechatronics. Berlin, Heidelberg: Springer, 2007: 116-119.
[16] MODARES A, SOMHOM S, ENKAWA T. A selforganizing neural network approach for multiple traveling salesman and vehicle routing problems [J]. International Transactions in Operational Research, 1999, 6(6): 591-606.
[17] MASUTTI T A S, DE CASTRO L N. A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem [J]. Information Sciences, 2009, 179(10): 1454-1468.
[18] VIEIRA F C, D′ORIA NETO A D, COSTA J A F. An efficient approach to the travelling salesman problem using self-organizing maps [J]. International Journal of Neural Systems, 2003, 13(2): 59-66.
[19] LOURENCO H R, MARTIN O C, STUTZLE T. Iterated local search [M]//Handbook of metaheuristics. Boston: Springer, 2003: 320-353.
[20] HASEGAWA M, IKEGUCHI T, AIHARA K. Combination of chaotic neurodynamics with the 2-opt algorithm to solve traveling salesman problems [J]. Physical Review Letters, 1997, 79(12): 2344-2347.
[21] JIANG D M. Improved particle swarm optimization for traveling salesman problem and LabVIEW implementation [J]. Informatization Research, 2018, 44(4): 24-29 (in Chinese).
[22] PAPALITSAS C, GIANNAKIS K, ANDRONIKOS T, et al. Initialization methods for the TSP with Time Windows using Variable Neighborhood Search [C]//2015 6th International Conference on Information, Intelligence, Systems and Applications. Corfu: IEEE, 2015: 1-6.
[23] LIU J. Applied research of hybrid genetic algorithm and simulated annealing algorithm in traveling salesman problem [D]. Guangzhou: South China University of Technology, 2014 (in Chinese).
[24] ZONG D C, WANG K K, DING Y. Review of ant colony algorithm for solving traveling salesman problem [J]. Computer & Digital Engineering, 2014, 42(11): 2004-2013 (in Chinese).
[25] WANG X, PENG S. Method for solving traveling salesman problem based on improved tabu search algorithm [C]//The 3rd China Conference on Command and Control. Beijing: Chinese Institute of Command and Control, 2015: 487-491 (in Chinese).
