SONG Jin-juan (宋锦娟)， BAI Yan-ping (白艳萍)， HU Hong-ping (胡红萍)
（Department of Mathematics, North University of China, Taiyuan 030051, China）
Abstract： Self-organizing map (SOM) proposed by Kohonen has obtained certain achievements in solving the traveling salesman problem (TSP). To improve Kohonen SOM, an effective initialization and parameter modification method is discussed to obtain a faster convergence rate and better solution. Therefore, a new improved self-organizing map (ISOM) algorithm is introduced and applied to four traveling salesman problem instances for experimental simulation, and then the result of ISOM is compared with those of four SOM algorithms: AVL, KL, KG and MSTSP. Using ISOM, the average error of four traveling salesman problem instances is only 2.895 0%, which is greatly better than the other four algorithms: 8.51% (AVL), 6.147 5% (KL), 6.555% (KG) and 3.420 9% (MSTSP). Finally, ISOM is applied to two practical problems: the Chinese 100 cities-TSP and 102 counties-TSP in Shanxi Province, and the two optimal touring routes are provided to the tourists.
Key words： self-organizing maps (SOM); traveling salesman problem (TSP); neural network
CLD number： O221.1 Document code： A
Article ID： 1674-8042(2013)04-0353-08 doi： 10.3969/j.issn.1674-8042.2013.04.012
References
[1] Laporte G. The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 1992，59 (3): 345-358.
[2] Leung K S, JIN Hui-dong, XU Zong-ben. An expanding self-organizing neural network for the traveling salesman problem. Neurocomputing, 2004, 62: 267-292
[3] Onoyama T, Maekawa T, Kubota S, et al. Intelligent evolutional algorithm for distribution network optimization. In: Proceedings of IEEE International Conference on Control and Applications, 2002, 2: 802-807.
[4] Takashi S, Kenji M, Fujimura K, et al. Optimization of surface component mounting on the printed circuit board using SOM-TSP method. IEIC Technical Report, 1999, 98(673): 289-296.
[5] Fujimura K, Fujiwaki S, Kwaw O C, et al. Optimization of electronic chip-mounting machine using SOM-TSP method with 5 dimensional data. In: Proceedings of International Conference on Info-tech and Info-net, Beijing, China, 2001, 4: 26-31.
[6] Fiechter L. A parallel tabu search algorithm for large traveling salesman problem. Discrete Applied Mathematics, 1994, 51 (3): 243-267.
[7] Van Laarhoven P J M, Aarts E H L. Simulated annealing: theory and applications. Kluwer Academic Publishers, Norwell, USA, 1987.
[8] Goldberg D E. Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publisher, Boston, USA, 1989.
[9] Dorigo M, Gambardella L M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1 (1): 53-66.
[10] Creput J C, Koukam A. A memetic neural network for the Euclidean traveling salesman problem. Neurocomputing, 2009, 72(4-6): 1250-1264.
[11] Kohonen T. The self-organizing map. In: Proceedings of IEEE, 1990, 78 (9): 1464-1480.
[12] Somhom S, Modares A, Enkawa T. A self-organising model for the travelling salesman problem. Journal of the Operational Research Society, 1997, 48 (9): 919-928.
[13] TPSLIB. [2013-01-08]. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.
[14] Angeniol B, la Croxi Vaubois C, Le Texier J Y. Self-organizing feature maps and the traveling salesman problem. Neural Networks, 1988, 1(4): 289-293.
[15] Aras N, Oommen B J, Altinel I K. The Kohonen network incorporating explicit statistics and itsapplication to the traveling salesman problem. Neural Networks, 1999, 12 (9): 1273-1284.
[16] ZHANG Wen-dong, BAI Yan-ping, HU Hong-ping. The incorporation of an efficient initialization method and parameter adaptation using self-organizing maps to solve the TSP. Applied Mathematics and Computation, 2006, 172 (1): 603-623.
[17] Latitude and longitude query of Chinese cities. [2013-01-11]. http://www.ximizi.com/jingweidu.php.
[18] Wang L. The neural network and combinatorial optimization. Doctor Thesis. Academy of Sciences, Beijing, 2000.
[19] WU Ling-yun. The application for Neural networks in combinatorial optimization and DNA sequencing. Doctor Thesis. Department of Mathematics, Academy of Sciences, Beijing, 2002: 46-50.
[20] Faigl J. On the performance of self-organizing maps for the non-Euclidean traveling salesman problem in the polygonal domain. Information Sciences, 2011, 181 (19): 4214-4229.
[full text view]
