時間制約を持つ寄り道経路探索システムの実現と評価

情報処理学会 Web Site

書誌事項

タイトル別名
  • 時間制約を持つ寄り道経路探索システムの実現と評価時間制約を持つ寄り道経路探索システムの実現と評価
  • ジカン セイヤク オ モツ ヨリミチ ケイロ タンサク システム ノ ジツゲン ト ヒョウカ ジカン セイヤク オ モツ ヨリミチ ケイロ タンサク システム ノ ジツゲン ト ヒョウカ
  • Time Constrained Trip Planning Search System

この論文をさがす

抄録

近年，カーナビ，インターネット等で地図検索，特にルート探索等のサービスが多数提供されている．本論文は，これらのルート探索において，経由地に時間制約があるような最短経路探索問題である「タイムセール寄り道探索」の概念を示すとともに，その解を求める手法を提案する．従来の寄り道探索手法をそのまま利用できる「基本導出法」を示し，その課題を指摘し，さらに，グラフの探索を行いつつ制約条件をチェックし解を導出する「動的導出法」を提案した．動的導出法は，グラフの探索範囲と候補となる解の個数を抑制し，性能を改善させることを特徴に持つ．グラフデータベース上に構築した実験システムを用いて提案方式の比較評価を行い，動的導出法が基本導出法に比べて，特にサービス密度（サービスを実施しているノードの割合）が低い場合に性能的に優れており，探索対象が大規模となる場合において適用性が高いことを示した．

We propose and formalize “time-sale trip planning search”, which is a variation of shortest path problem. This is a trip planning which includes time-constrained services. We clarify “basic method” of this search, which is a simple extension of existing trip planning method, and “dynamic method” which can restrict search range and number of candidate answers using time constraints. We implemented these methods on a graph database system, and showed that dynamic method has advantages in performance under low service density (ratio of nodes in service), so that can be applicable for very large graph databases.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ