Fast Heuristic Method by Combining Global and Local Strategies for Traveling Salesman Problem

スポンサーリンク

概要

• 論文の詳細を見る

• A new algorithm for the Euclidean and symmetrical Traveling Salesman Problem (TSP) is proposed, which achieves fast computations and practically sufficient accuracy. This algorithm, called the fast convex hull (FCH) algorithm, is created by modifying and combining appropriately the convex hull and nearest neighbor algorithms, as global and local strategies, respectively. This method was applied to problems reported in the literature including five 100-city problems presented first by Krolak et al. An accuracy of 3.3 percent with respect to the optimal solution was achieved with computations of the order of less than N^<1.4>. In addition, reasonable results were obtained for a 550-city problem with random distribution. Compared with other heuristic methods, the effectiveness of this algorithm is suggested in terms of computations and accuracy.

• 鈴鹿医療科学大学の論文
• 1996-03-30

著者

• 関谷 富男

  Department of Medical Information Science, Faculty of Medical Engineering. Suzuka University of Medi

• 渡辺 瞭

  Department of Medical Electronics, Faculty of Medical Engineering. Suzuka University of Medical Scie

関連論文

• Fast Heuristic Method by Combining Global and Local Strategies for Traveling Salesman Problem

スポンサーリンク