Summary
International Symposium on Nonlinear Theory and its Applications
2009
Session Number:B1L-B
Session:
Number:B1L-B2
Solution-Space Reduction Method by Using Geographic Complex Network Model for Traveling Salesman Problem
Yusuke Kawamura, Yutaka Shimada, Takafumi Matsuura, Tohru Ikeguchi,
pp.-
Publication Date:2009/10/18
Online ISSN:2188-5079
Summary:
The traveling salesman-problem (TSP) is one of the most typical NP-hard combinatorial optimization problems. To construct a heuristic algorithm for solving TSPs, a nearest-neighbor method is often used to reduce a solution-space because it is very rare to connect two cities which are located in the far distance. On the other hand, to analyze the characteristics of real networks many geographical complex network models have already been proposed. The networks constructed by the geographical complex network model have similar properties with the optimal tours of TSPs: the edges which connect distant two vertices and intersection of edges are inhibited. In this paper, we propose a new reduction method for the solution-space of TSP using the geographical complex network models.