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

スポンサーリンク

概要

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

著者

関連論文

もっと見る

スポンサーリンク