巡回セールスマン問題におけるハイブリッド型解法

カテゴリ: 全国大会

論文No: 3-054

グループ名: 【全国大会】平成25年電気学会全国大会論文集

発行日: 2013/03/05

タイトル(英語): Hybrid Approximation Algorithm for Traveling Salesman Problem

著者名: 星野 貴弘(日本大学),浜松 芳夫(日本大学)

著者名(英語): Takahiro Hoshino(Nihon University),Yoshio Hamamatsu(Nihon University)

キーワード: 巡回セールスマン問題|しきい値|CCA法|最小全域木

要約(日本語): 巡回セールスマン問題における巡回路の構築手順の提案を行う。最近挿入法，ランダム挿入法などの構築法は，部分巡回路に対し，追加基準に合致する都市を1都市ずつ追加する近似解法である。このような後戻りを許さない貪欲的な挿入手続きは，残りの都市数が少なくなるにつれて，追加コストを大きく増加させる経路を作りやすい。本研究では，構築法の追加基準にしきい値を設けることで，このような問題を改善する解法を提案する。設定されたしきい値により，基となる手法の挿入手順とMSTによる挿入手順を使い分けることで精度を向上させる。性能評価にはTSP LIB95のベンチマーク問題に対して，基となる構築法としてCCA法を用いた結果と提案手法を用いた結果を比較した。

原稿種別: 日本語

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