Solving TSP Based on Multi-Segment Multi-Orientation Nearest Neighbor Algorithm

摘要：

Considering constructional algorithms for solving Traveling Salesman Problem (TSP), the solution process of Nearest Neighbor (NN) is the simplest one, but its performance is the worst. This paper proposes an improved NN algorithm for solving TSP in Euclidean Plane. Firstly, the algorithm searches four corner-nodes from all nodes, and gets a simple tour which only includes four corner-nodes, obtains four segments and their start nodes and end nodes, respectively. Then, each segment starts from current corner-node, and the algorithm selects a node as next target node from its multi-orientation nearest neighbor nodes, considering their distance and orientation comprehensively, and searching process repeatedly until each segment arrives at their end nodes. Furthermore, the algorithm inserts those rest nodes into a certain segment. At last, the algorithm connects four segments from stem to stern to form the final tour. Experimental results indicate that the proposed algorithm greatly improves the result of NN algorithm.

关键词： TSP construction algorithm NN search k-nearest neighbor multi-orientation nearest neighbor

作者: Xiang Zuo-Yong Gao Xing-Yu Chen Zhen-Yu Ouyang Liu-Bo Chen Duan-Lai

作者单位: School of Science, Central South University of Forestry and Tech., Changsha, Hunan, China College of Information Engineering.Xiangtan University,Xiangtan, Hunan, China Institute of Computing Technology.Chinese Academy of Sciences, Beijing, China School of Software, Hunan University, Changsha, China School of Math and Computing Science.Hunan University of Sci,and Tech., Hunan, China

会议类型: 国际会议

会议名称: 2010 IEEE International Conference on Intelligent Computing and Intelligent Systems(2010 IEEE 智能计算与智能系统国际会议 ICIS 2010)

会议地点: 厦门

会议语种:英文

页码: 452-457

在线出版日期: 2010-10-29（万方平台首次上网日期，不代表论文的发表时间）