A skip-type m-step 7S-opt: An 0(n) improvement algorithm leading to a near-optimal solution of symmetric TSP(ABSTRACTS OF PROCEEDINGS OF THE SCHOOL OF INFORMATION TECHNOLOGY AND ELECTRONICS SERIES J TOKAI UNIVERSITY -2003-2004-)
スポンサーリンク
概要
- 論文の詳細を見る
The symmetric traveling salesman problem (symmetric TSP) has appeared variously in scientific and engineering fields. Further, since the problem is standing in the class of NP-hard, it is important to develop a fast algorithm improvement to provide a near-optimal solution. This report deals with a new algorithm "skip-type m-step 7S-opt" having O(n) computational complexity both in running time and in storage space. The approach robustly derives a feasible tour, and predicts computational time limits for obtaining the tour because of running in 0(n) complexity. Moreover this algorithm, which is applicable to the asymmetric TSP, requires no searching for parameters for each problem. These characteristics highlight differences from conventional heuristics. Using standard PC, we have systematically proved the high efficiency of this approach through 27 instances from TSPLIB as real-world problems, covering small to large-scale problems exhibiting no uniform distributions. For the instances, even with constraints on accuracy of the solution, the excess over optimum shows 7.3% on average, and 11.4% at worst.
- 東海大学の論文
著者
関連論文
- A Stochastic Dynamical System with Nonlinear State-Transition Rates and its Moment-Stability
- A skip-type m-step 7S-opt: An 0(n) improvement algorithm leading to a near-optimal solution of symmetric TSP(ABSTRACTS OF PROCEEDINGS OF THE SCHOOL OF INFORMATION TECHNOLOGY AND ELECTRONICS SERIES J TOKAI UNIVERSITY -2003-2004-)