研究者総覧

キーワード

※ スペース区切りで絞り込み検索が可能です。

種別

論文

タイトル: 時間制約を持つ寄り道経路探索システムの実現と評価
タイトル（英）: Time Constrained Trip Planning Search System
参照URL: https://researchmap.jp/ggszk/published_papers/27034698
著者: 鈴木源吾,榎本俊文,小林伸幸,山室雅司,鬼塚真
著者（英）
担当区分
概要: 近年，カーナビ，インターネット等で地図検索，特にルート探索等のサービスが多数提供されている．本論文は，これらのルート探索において，経由地に時間制約があるような最短経路探索問題である「タイムセール寄り道探索」の概念を示すとともに，その解を求める手法を提案する．従来の寄り道探索手法をそのまま利用できる「基本導出法」を示し，その課題を指摘し，さらに，グラフの探索を行いつつ制約条件をチェックし解を導出する「動的導出法」を提案した．動的導出法は，グラフの探索範囲と候補となる解の個数を抑制し，性能を改善させることを特徴に持つ．グラフデータベース上に構築した実験システムを用いて提案方式の比較評価を行い，動的導出法が基本導出法に比べて，特にサービス密度（サービスを実施しているノードの割合）が低い場合に性能的に優れており，探索対象が大規模となる場合において適用性が高いことを示した．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.
概要（英）: 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.
出版者・発行元: 情報処理学会
出版者・発行元（英）
誌名: 情報処理学会論文誌
誌名（英）
巻: 53
号: 2
開始ページ: 857
終了ページ: 867
出版年月: 2012年2月15日
査読の有無: 査読有り
招待の有無
掲載種別
ISSN: 1882-7764
DOI URL
共同研究・競争的資金等の研究課題

研究者

鈴木源吾 (スズキゲンゴ)