Algorithm for Solving Traveling Salesman Problem Based on Self-Organizing Mapping Network

doi:10.1007/s12204-022-2517-3

Abstract

Abstract: 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.

Key words: traveling salesman problem (TSP), self-organizing mapping (SOM), combinatorial optimization, neural network

摘要： 旅行商问题是一个经典的非确定性多项式难优化问题。本文基于自组织映射网络的特性，从网络更新策略、初始化方法和参数选择等角度对自组织映射网络进行改进。比较了所提出的算法在旅行商问题上的性能与现有自组织映射网络算法的性能，并将其与几种启发式算法进行比较。仿真结果表明，与现有的自组织映射网络相比，本文改进的自组织映射网络提高了收敛速度和算法精度。与迭代局部搜索和启发式算法相比，提出的改进自组织映射网络算法在中规模旅行商问题上具有计算速度快的优势。

关键词: 旅行商问题（TSP），自组织映射（SOM），组合优化，神经网络

CLC Number:

TP18

ZHU Jianghui(朱江辉),YE Hanghang(叶航航), YAO Lixiu1(姚莉秀), CAI Yunze(蔡云泽). Algorithm for Solving Traveling Salesman Problem Based on Self-Organizing Mapping Network[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 463-470.

References

[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).