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