Hits:

Indexed by:期刊论文

Date of Publication:2013-01-01

Journal:International Journal of Innovative Computing, Information and Control

Included Journals:EI、Scopus

Volume:9

Issue:9

Page Number:3685-3700

ISSN No.:13494198

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