Summary
International Symposium on Nonlinear Theory and its Applications
2009
Session Number:B1L-B
Session:
Number:B1L-B4
Chaotic Search based on the Ejection Chain Method for Traveling Salesman Problems
Shun Motohashi, Takafumi Matsuura, Tohru Ikeguchi,
pp.-
Publication Date:2009/10/18
Online ISSN:2188-5079
Summary:
In the real world, we are often asked to solve difficult problems of combinatorial optimization: for example, vehicle routing, computer wiring, circuit drilling, scheduling, and so on. To solve these problems, the traveling salesman problem (TSP) has been studied widely. Because the TSP belongs to a class of NP-hard, it is required to develop an effective approximate algorithm for obtaining near optimal solutions in a reasonable time frame. As an approximate algorithm, a method using chaotic dynamics shows good performance. In this method, chaotic dynamics controls local search methods to avoid local minima. In this paper, we propose a new chaotic search method using the stem-and-cycle structure for solving TSPs. Evaluating performance, we show that the new chaotic search method is very effective for solving TSPs.