境界カテゴリーを設定した双方向探索による高速OSR探索法

摘要

あらまし　位置に関連した情報サービス（LBS）やカーナビでの応用を目的に，OSR（optimalsequenced route）探索が提案されている．これは訪れるPOI（pointofinterest）カテゴ1）－の順序が与えられ，それぞれのカテゴリーのPOIを一つずつ順番に訪れる距離最小の経路を求めるものである．本論文では，出発地と目的地から同時に探索を開始する双方向探索と，境界カテゴリーと呼ぶ経路途中に設定したカテゴリーまでの探索を始終点双方から行い，最終的にそれらを結合した経路を求める方法を提案する．実際の道路地図を用いた性能比較実験により，提案方式が従来方式に比して大幅な速度向上が達成されていることを示す．