International Symposium on Nonlinear Theory and its Applications


Session Number:A2L-F



Chaotic search method using the Lin-Kernighan algorithm for traveling salesman problems

Shun Motohashi,  Takafumi Matsuura,  Tohru Ikeguchi,  


Publication Date:2008/9/7

Online ISSN:2188-5079


PDF download (112.3KB)

The traveling salesman problem (TSP) belongs to a class of NP-hard. Thus, it is required to develop effective algorithms for finding near optimal solutions or approximate solutions in a reasonable time frame. We have already proposed several methods which use chaotic dynamics to drive a local search method, such as the 2-opt algorithm or the adaptive k-opt algorithm. In these methods, chaotic dynamics efficiently controls to avoid local minima. In this paper, extending this idea, we propose a new method for solving the TSP. In the proposed method, one of the most powerful local search methods, the Lin-Kernighan algorithm, is driven by chaotic dynamics. As a result, the proposed method obtains better solutions than the conventional chaotic search methods.