点击次数：

论文类型：期刊论文

发表时间：2013-01-01

发表刊物：International Journal of Innovative Computing, Information and Control

收录刊物：EI、Scopus

卷号：9

期号：9

页面范围：3685-3700

ISSN号：13494198

摘要：In this paper, a complex network-based method for analyzing solution space of traveling salesman problem (TSP) is proposed. The aim is to analyze what properties the complex network corresponding to a good heuristic has and understand its behavior solving TSP from the new point of view. It is found that solution space of one heuristic for TSP is a classical complex system that can be analyzed by using complex network theory. The method framework includes two parts: constructing a complex network according to a specified heuristic and computing the related indexes of the complex network. Then the solution spaces of 2-opt, Or-opt, 3-opt and Lin-Kernighan are analyzed by using the method proposed in this paper. Our findings demonstra,te that the complex networks corresponding to the good heuristics for solving TSP are similar to the small-world networks. According to the conclusion, three excellent heuristics are developed and evaluated to verify the effectiveness of the method. ? 2013 ISSN 1349-4198.