FIT2016 第15回情報科学技術フォーラム 開催日:2016年9月7日(水)~9日(金) 会場:富山大学キャンパス
抄録
D-010
連続旅行計画の為のsafe-region生成方法
塩澤光貴・Htoo Htoo・大沢 裕(埼玉大)
車などの移動体が、移動しながら経路探索を行うことを連続検索という。本稿では、旅行計画問題の一つであるOSR探索に適応させた連続検索について扱う。OSR探索とは、出発地(S)、訪問POIカテゴリ、目的地(D)が指定されたとき、Sから指定された順に各POIカテゴリを一つずつ経由しDに至るまでの最短経路を求める問題である。連続検索では、検索結果が変わらない領域を生成するsafe-regionという考え方が提案されており、本稿では、このsafe-regionをOSR探索において高速に生成する方式を提案する。また従来のOSR探索は実行時間がPOI密度の変化に影響を受けやすかったため、POI密度によらず安定した実行時間で探索可能なOSR探索も提案する。