インスタンスの進化に基づくTSPのための発見的解法の改良

• Item type: SIG Technical Reports(1)
• 公開日: 2004-06-22
• タイトル: インスタンスの進化に基づくTSPのための発見的解法の改良
• タイトル / 言語: en
• タイトル: An Improved Heuristic for Solving TSP Based on the Evolution of Easy Instances
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information Engineering Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Department of Information Engineering Graduate School of Engineering, Hiroshima University
• 著者名: 藤田, 聡; 梅實真一郎
• 著者名(英): Satoshi, Fujita; Shin'Ichiro, Umezane
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では「与えられたインスタンスを簡単なインスタンスに進化させて解く」という考え方に基づいた、ユークリッド平面上のTSPに対する発見的解法の提案と評価を行う。提案手法は1998年にPapadimitriouとSideriによって提案された手法の改良になっている。提案手法の効果を評価するために行った実験の結果、提案手法を用いることで進化の効率が向上し，従来手法に比べてよりよい解がより高速に求められることが明らかとなった。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a heuristic scheme for solving TSP in the Euclidean plane based on the notion of ``evolution of easy instances.'' The proposed scheme is an improvement of the scheme proposed by Papadimitriou and Sideri in 1998. We conducted several experiments to evaluate the goodness of the schemes. The result of experiments indicates that our scheme really improves the accuracy of solutions compared with the previous one.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 2004, 号 67(2004-MPS-050), p. 1-4, 発行日 2004-06-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会