最小全域木を用いたCHI法の改良

カテゴリ: 全国大会

論文No: 3-022

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

発行日: 2012/03/05

タイトル(英語): An Improved Convex Hull Insertion Algorithm with Minimum Spanning Tree

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

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

キーワード: 巡回セールスマン問題|Convex Hull Insertion法|最小全域木

要約(日本語): 本研究では，Traveling Salesman Problem(TSP)における巡回路の構築手法の一つであるConvex Hull Insertion(CHI)法を改良した近似解法の提案を行う。CHI法および提案手法は，都市による凸包の境界上の初期部分巡回路にそれ以外の都市を何らかの方法で追加していくことにより巡回路を構築していく。その際，新たに追加された都市と，その前後の都市のなす角を追加経路角と呼ぶことにする。提案する解法では，追加経路角にしきい値を設け，このしきい値を超える場合には，最も経路角を大きくさせる都市を追加し，しきい値より小さい場合には，最小全域木を用いて都市の追加を行う。また，TSPのベンチマーク問題に対してCHI法と提案手法の求解精度を比較し，提案した手法の有用性を検討する。

原稿種別: 日本語

PDFファイルサイズ: 1,697 Kバイト