貪欲法に基づいた巡回セールスマンアルゴリズムの評価と改良

カテゴリ: 全国大会

論文No: 3-038

グループ名: 【全国大会】令和5年電気学会全国大会論文集

発行日: 2023/03/01

タイトル(英語): Evaluation and improvement of a greedy-based traveling salesman algorithm

著者名: 杉本拓哉（大阪電気通信大学）,阿部昇（大阪電気通信大学）,山口一章（神戸大学）

著者名(英語): Takuya Sugimoto (Osaka Electro-Communication University),Noboru Abe (Osaka Electro-Communication University),Kazuaki Yamaguchi (Kobe University)

キーワード: 巡回セールスマン問題|最適化|貪欲法|traveling salesman problem|optimization|greedy algorithm

要約(日本語): 近年，Sharmaらは動的に変化するグラフに対する4つの巡回セールスマンアルゴリズムを提案した。本研究は，そのうちの1つであるDg-TSPについて，評価および改良手法の提案を行うものである。評価の際には，整数計画ソルバーによって得られる最適解との比較を行う。そして，計算機実験により，いずれの手法も十分に高速であり，かつある程度よい巡回路が求められることを示す。また，改良Dg-TSPが，Dg-TSPに対して実行時間を大きく損なうことなく結果を改善することも示す。

本誌掲載ページ: 59-61 p

原稿種別: 日本語

PDFファイルサイズ: 665 Kバイト