[E4] 移動・交通２

5:20 PM - 5:40 PM JST(8:20 AM - 8:40 AM UTC)

[E4-05] あいまいな条件設定に適応した巡回経路探索システムの構築

*Kei Nagaoka¹, Yamamoto Kayoko¹ (1. The University of Electro-Communications)

Keywords:

蟻コロニー最適化,巡回セールスマン問題,最適化アルゴリズム,巡回経路探索,あいまいな条件

巡回セールスマン問題（traveling salesman problem: TSP）は、複数地点を巡回して出発地点に戻る最短経路のうちで、総移動コストが最小のものを求める組合せ最適化問題である。巡回経路を求める時には、一般的に、何らかの目的を持って経路探索が行われる。しかし、これまでに、スポットの特徴に基づいてユーザが設定したあいまいな条件に適応した巡回経路探索は、行われてこなかった。
そのため、本研究は、徒歩による効率的な経路計画を作成するために、ユーザが設定したあいまいな条件に適応した巡回経路を探索するシステムの構築を目的とする。本システムでは、経路探索を行う時に、ユーザは巡回したいスポットの特徴を表すタグ、もしくは名称を入力し、これらの条件に適合した経路が提案される。
本研究では、TSPの最適解を導出できる点とパラメータを変えることで様々な条件を考慮することのできる柔軟性の高さの２つの理由から、経路探索手法として蟻コロニー最適化（Ant Colony Optimization: ACO）を用いた。