Summary
International Symposium on Nonlinear Theory and its Applications
2010
Session Number:B2L-A
Session:
Number:B2L-A3
A Method for Solving Very Large Scale TSPs by Chaotic Dynamics
Tohru Ikeguchi, Shun Motohashi, Takafumi Matsuura,
pp.293-296
Publication Date:2010/9/5
Online ISSN:2188-5079
Summary:
To solve traveling salesman problems (TSPs), we have already proposed two chaotic search methods, the Lin-Kernighan (LK) algorithm controlled by the chaotic dynamics (CS-LK) and the stem-and-cycle (S&C) ejection chain method controlled by the chaotic dynamics (CS-SC). The basic concept of the methods is that chaotic dynamics can effectively resolve a local minimum problem intrinsic to the heuristic algorithm. Although the CS-SC shows higher performance than the CS-LK, it is not so easy to apply the CS-SC to large scale instances because this method takes much calculation time to find good results. It is also important to develop an effective algorithm which finds good near-optimal solutions with less calculation time. In this paper, we propose a new method for solving very large scale TSPs with the order of 105 cities. In the method, we introduced a hybrid strategy by combining these two chaotic search methods. We used large scale instances form TSPLIB to evaluate the proposed method. We show that the proposed method exhibits very small gaps from the optimal solutions with less calculation time.