規則変動型m-step7S-opt法 : 対称巡回セールス員問題のO(n)近似解法(<特集>経営システム工学特集)
スポンサーリンク
概要
- 論文の詳細を見る
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 O(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.
- 東海大学の論文
- 2004-09-30