3-023
CHI法を用いた複数経路探索問題の一解法
◎村上直哉・星野貴弘・浜松芳夫(日本大学)
本研究では,組合せ最適化問題の一つである複数経路探索問題を対象とする。複数経路探索問題とは,複数の車両によって与えられた都市すべてを通過する経路の組合せの中から最短経路を求める問題である。このような組合せ最適化問題において,最適解の導出に要する時間は都市数の増加に伴い長くなる。本研究では近似解法として,経路決定には凸包の性質を利用したCHI法を用い,車両に対する都市の割当てには,遠近率という指標を用いた解法を提案する。提案手法の有効性を検討するために,都市をランダムに配置した問題に対して,組合せ最適化問題の解法として知られている遺伝的アルゴリズと提案手法を適用し,距離と計算時間の比較を行う。