Comments
Description
Transcript
複数の最短距離検索を目的とした経路検索システムの提案 井立 圭治 A
複数の 複数 の 最短距離検索を 最短距離検索 を 目的とした 目的 とした経路検索 とした 経路検索シ 経路検索 シ ステムの ステム の 提案 井立 圭治 A Proposal of Route Search Engine to Retrieve Plural Beelines Keiji IDATE Abstract As for the WEB-GIS service for consumers, a lot of location information services including Google Maps are developed in recent years. Among such main offered services, POI (Point of Interest) is the most interesting. It is necessary for users to utilize the positional information fully and to grasp the best road route from the departure position to the destination. The feature of the system that I propose in this study is to provide more efficient route retrieval service, by applying the algorithm of the attainment sphere route retrieval, when users want to retrieve two or more route retrieval objects. Keywords 経 路 検 索 シ ス テ ム （ Route Search Engine）, 最 短 距 離 検 索 （Beeline Retrieval）, POI (Point of Interest)，アルゴリズム（Algorithm） しかし,地図上に複数の POI が表示されている場 １ ． はじめに 現 在 , コ ン シ ュ ー マ 向 け WEB-GIS サ ー ビ ス 合など,経路を調べたい POI が複数ある際には,そ は,Google Maps を初めとして,多くの位置情報サ れら複数の POI 全てに対して 2 点間最短経路検索 ービスが展開されている.その中で,主な提供サー を行うことは多大な計算コストが発生する. ビ ス の 一 つ と し て , 地 図 上 へ の POI( Point of 本研究で提案するシステムの特徴としては,そ Interest，以下 POI と表記する)表示がある.これは, ういった検索したい経路検索対象が複数存在する 利用ユーザーが,検索目的としているカテゴリに 場合に,到達圏経路検索のアルゴリズムを応用す 属する複数の POI を地図上へ表示することであり, ることで,より効率的な経路検索サービスを提供 このことにより検索対象の位置を効率的に把握す することである. ることができる. POI の位置を把握した利用ユーザーが,その位 ２ ． アルゴリズム 置情報をより活用するためには,実際にその位置 まずは,今回採用する検索方法である到達圏経 へ移動する際に,出発位置からどの道路ルートで 路検索について説明する.到達圏経路検索とは,指 移動することが最適であるかを把握する必要性な 定した 1 地点からまた別に指定した距離・時間で ども生じてくる.そして,その際に利用する技術と 到達可能なノードを検索する検索方法である. して，2 点間最短経路検索が存在する. 井立：〒101-0065 東京都千代田区西神田 3-8-1 この到達圏経路検索を行う上で,最短経路検索 のアルゴリズムを活用する.最短経路検索にはい 千代田ファーストビル東館 9F くつかのアルゴリズムが存在するが,その代表的 株式会社サイバーマップ・ジャパン なものにダイクストラ法がある. Tel:03-5275-2158 E-Mail:[email protected] 路取得処理手順もそれに応じて適切な方法を用い 7 8 8 る必要があると思われる. 範囲内の複数 POI への最短ルートを導き出す上 8 での処理手順としては,2 通り考えられる. 7 9 9 まず,1 つ目としては到達圏経路検索後,範囲内 に存在する POI を取得する方法である.到達圏経 路検索を行った後,その到達点ノードを結んだ多 8 8 角形の中に存在する POI を検索する.そして,範囲 内であったそれぞれの POI の位置と検索結果のノ ードまでの距離を求める.求めた距離にダイクス 9 8 9 トラ法を用いた到達圏経路検索で取得済みのノー ドまでの最短ルートの距離を合わせ,その距離が 最も短いものを対象 POI に対する最短ルートとす 開始ノード る.到達圏範囲内 POI を取得する例を図 2 に示す. 到達ノード 2 つ目は，到達圏経路検索を行う過程で POI に 対する最短ルートを決定する方法である.この方 図1 コストが 10 以下で到達可能な範囲 法の場合,到達圏経路検索を行う前に,対象とした い POI の位置を取得しておく必要がある.そして, ダイクストラ法とはグラフ理論を用いて検索開 その POI の位置を検索パラメータとして設定して 始点から各ノードに対して到達する最小コストを おくことで,最短経路検索過程の中で最寄りノー 確定させていく方法である.このアルゴリズムの ドを確定することができる.この方法は既に目的 特徴を活用することで,検索開始点から全方向の 地としたい複数の POI が確定している,あるいは 全てのノードに対して,最短ルートコストを求め より少ないコストで検索対象 POI を取得する方法 ることができる. を用いた場合には有効となる. 検索開始点の近辺のノードから最小コストを求 めていき,検索対象ノードの全てが指定距離・時間 全方向に対する特定ルート取得例を図 3 に示 す. のコストを越えるまで検索を続ける.その結果,コ ストを越える直前の範囲内ノードまでを到達範囲 内ノードとすることができる. ダイクストラ法で到達範囲ノード情報を取得す ることにより,その範囲内の各ノードに対する最 短コストを示す最短ルートが計算済みということ になる.この検索過程における各ノードの最短ル ート情報を保持しておく.このダイクストラ法を 用いた到達圏経路検索の検索結果の例を図 1 に示 到達圏ノード す. POI 次に,上記処理で取得した各ノードに対する最 短経路を活用して検索対象となる POI に結び付け る.ここで取得,表示の対象としたい POI は，その 情報の利用方法によって異なる.POI への最短経 図2 到達圏範囲内にある POI を検索対象として 抽出した結果 サービスのユーザーが地図から経路を検索する 場合,検索開始地点は現在位置など比較的明確で ある場合が多い.しかし,目的地点は前の例でも述 べているように,検索過程で目的地点を決定する 場合もあり,ユーザーが検索前の時点では,必ず目 的地点を決定しているとは限らないといえる.そ のような場合においては,今回のアルゴリズムを 出発地ノード 活用することで,ユーザーの求める経路候補を 1 最寄りノード 回の検索で複数取得することでサービスに対する その他ノード 負荷を軽減することができる. そして,乗換案内のような道路ネットワークを 図3 特定済みの最寄りノードに対して 利用した経路検索以外のナビゲーションサービス ダイクストラ法で検索した結果 との連携時にも利用できる.道路ネットワーク以 (全方向のノードへ到達距離を決定) 外の経路検索の結果に応じて,連携する道路ネッ トワークによる経路検索の位置情報も変化するこ このように 1 対多の経路検索を行う場合,求め とがありうるからである. る対象が 1 地点から距離，時間で到達できる範囲 これは,徒歩と乗換案内の経路検索結果を合わ の POI である場合は,1 つ目の方法,対象が検索前 せた最短経路時間を算出する際,出発地点近辺の から明確になっている場合は,2 つ目の検索方法 駅までの道路ルートの最短時間と各駅間の乗換情 を用いることが有用である. 報を総合した経路時間で考えることが必要となる ためである.この場合,道路ルートの最短距離で到 ３ ． 今後の 今後 の 活用方法の 活用方法 の 例 達できる駅からの乗換ルートが最短であるとは限 ここまで述べてきたアルゴリズム自体は，特に らず,場 合に よ っ ては, 徒歩 ル ート 距 離が 2 つ 目新しいものではない.しかし,既存のアルゴリズ 目,3 つ目に近い駅からの乗換ルートと徒歩ルー ムを応用していくことで,ユーザーに対して提供 トの総合した時間が最短ルートとなることがあり するサービスの幅を大きく広げていくことができ うる. る. 具体的な例をあげると,出発地から到達できる まず,ここまで述べてきたアルゴリズムを利用 駅 A,B,C までの到達コストがそれぞれ 3,2,4 であ したサービスの例として,経路情報を含んだ複数 り,目的地まで到達できる駅 D,E,F の到達コスト POI 間の情報比較に利用することが考えられる. が 3,4,2 である場合,徒歩ルートの最短はそれぞ このサービスでは，地図上に検索対象としている れ B までのルートと F までのルートになる.しかし カテゴリに属する POI を表示する際,地図上の 1 乗換ルートを含んだトータルの最短コストが最も 地点からの経路情報を含んだ到達圏検索を行う. 低いルートが駅 A から駅 E へのルートを通る経路 これにより取得した各 POI には同一の経路開始地 だった場合,実際に必要なルートは B,F 間のルー 点からの経路情報を含んでいるため,ユーザーが トではなく A,E 間のルートということになる. 取得済みの POI 間の情報を比較検討する際に, POI このような場合,複数の連携地点を事前に到達 固有の情報以外にも経路情報を比較検討材料とし 圏経路検索で近辺の複数駅に対する到達距離を取 て含めることができる. 得しておくことで,最小 2 回の経路検索で済ませ また,経路情報である以上,ナビゲーションサー ビス全般にも活用させることができる. ることができる. D A E 3 また別途検証すべきところである. 3 また,乗換案内サービスなど他の経路検索サー 4 B F 2 出発地・目的地 乗車駅・降車駅 ５ ． おわりに 今回研究対象とした道路ネットワークを用いた C 最短経路検索においては,主に採用した到達圏経 路検索以外に,2 点間経路検索や巡回経路検索な 数値 徒歩コスト 図4 外にも検討が必要な部分が多数あるため,これに ついても同様に別の機会で検証していきたい. 2 4 ビスとの連携時においても,今回挙げた検証点以 トータル最短経路 その他経路 徒歩ルートと駅乗換ルートの連携を考えた 場合の最短ルート検索パターン例 ど,その検索目的に応じたアルゴリズムが存在す る. 本研究では,到達圏経路検索を用いることで,そ の検索過程において到達圏に至るまでの各ノード に対しても最短経路を確定するという特性を活か し,効率的に必要な情報を得ることを可能とした. これにより,全ての連携地点に対して 2 点間経 同様に,他の経路検索手法においてもその特性を 路検索を行うことに比べると非常に少ないコスト 応用することで,その検索手法の主目的以外の情 で全体経路の検索をすることが可能となる.この 報を得ることも可能であると考えられる. 例を図 4 に示す. このような視点から，今後研究課題としては， 道路ネットワーク情報,あるいはその他位置情報 ４ ． 今後の 今後 の 課題 これらの検索アルゴリズム及びその活用例を用 の解析による既存アルゴリズムやデータの有効利 用について研究することがあげられる． いることで,提供可能なサービスの幅を広げるこ とが可能となる.しかし,実サービスとして提供す る際には,ここであげた点以外にもいくつかの考 慮しておくべき点がある. まず,アルゴリズムの面からは,到達圏範囲内の 複数 POI への最短ルートの確定方法を 2 通り示し 謝辞 最後に,今回論文発表の許可を下さったサイバ ーマップ・ジャパンと論文作成にあたりご支援を 下さった電気通信大学の山本佳世子准教授に深く 感謝するしだいである. た.しかし,状況に応じてどちらを適用することが 有用であるかを示してはいるが,実際に利用する 参考文献 際には,その状況に応じた詳細なパフォーマンス 1)張長平(2001)『空間データ分析』, 古今書院. の検証を行う必要はある. 2)KIWI-W コンソーシアム著(2003)『カーナビゲー また,サービスのパフォーマンスはここで挙げ たアルゴリズムによる負荷だけではなく,その他 の処理もその前後,あるいは平行して動いている 場合があるため,その点に関しても考慮しておく ションシステム』角本繁(編),共立出版株式会 社. 3)河西朝雄(2001)『JAVA によるはじめてのアルゴ リズム入門』,技術評論社. 必要はある.この課題を解決するためには,その処 4)奥村晴彦・首藤幸一・杉浦方紀・土村展之・津 理が行われるタイミングやユーザーインターフェ 留和生・細田孝之・松井吉光・光成滋生(2003) ースとの関わりも含まれるため,それについては 『JAVA によるアルゴリズム事典』,技術評論社.