抄録

D-027
旅行計画におけるIERの利用とその検証の高速化

現在地と最終目的地が与えられ、その最終目的地に達する途中で複数種類のPOIを経由する最短路を求める検索は、一般に旅行計画問題と呼ばれている。この旅行計画には複数の方式が提案されているが、訪れるPOIの順番が指定されない場合、NP困難な問題となる。そこで従来は、ユークリッド距離での近似アルゴリズムが提案されてきた。本稿では、訪れる順番が指定される場合や、訪れるPOIの種類が８種類程度より少ないときを対象として、ユークリッド距離での巡回路をインクリメンタルに生成し、それを道路網距離で検証するアプローチを提案する。また本稿では、以上の枠組みに基づく、道路網上での旅行計画を高速に決定するアルゴリズムを提案する。