3-051
方向角を考慮した複数経路探索問題の一解法
◎村上直哉・星野貴弘・浜松芳夫(日本大学)
本研究では複数経路探索問題を対象とする。複数経路探索問題とは,利用可能な車両数及び訪問すべき都市の数とその位置情報が与えられたとき,複数の車両の経路の総和が最短となるような各車両の経路を求める問題である。このような組合せ最適化問題において,最適解の導出に要する時間は都市数の増加に伴い長くなる。本研究では近似解法として,車両に対する都市の割当てには,出発地点または目的地点に対する角度を用いる。また,経路決定には凸包の性質を利用したCHI法を用いる。提案手法の有効性を検討するために,都市をランダムに配置した問題に対して,遺伝的アルゴリズと提案手法を適用し,解の精度および計算時間の比較を行う。