説明

経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラム

【課題】適切な経由地を効率よく探索することができる、経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラムを提供することを課題とする。
【解決手段】本発明は、交通網を規定するネットワークデータを記憶し、ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索し、探索した、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラムに関する。
【背景技術】
【0002】
従来、経路の途中の立寄り地を探索する技術がある。
【0003】
例えば、特許文献1,2においては、出発地から目的地までの経路から、所定距離や所定時間の範囲内に存在する立寄り地を探索する技術が開示されている。
【0004】
また、特許文献3においては、現在位置から立寄り地を経由して目的地に到達するまでにかかる迂回所要時間と、当該立寄り地を経由しない場合の所要時間を比較して、ロスタイムを算出する技術が開示されている。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特許第3242968号公報
【特許文献2】特開2002−257567号公報
【特許文献3】特許第3161276号公報
【発明の概要】
【発明が解決しようとする課題】
【0006】
しかしながら、従来の経由地(経路の途中の立寄り地)を探索する技術においては、適切な経由地を効率よく探索することができないという問題点を有していた。
【0007】
例えば、特許文献1,2の技術においては、出発地から目的地までの経路から所定の範囲外となるものの、ロスタイムが短い経由地については探索されないという問題点を有していた。
【0008】
また、特許文献3の技術においては、立寄り地ごとに目的地までの経路を探索するため、立寄り地の数に比例して処理時間が長くなるという問題点を有していた。より具体的には、特許文献3に例示されるように、ダイクストラ法を用いて経路探索を実行すると、立ち寄り地を基準地点として、リンクコストを計算しながら順次到達したノードやリンク等を広げていく拡散処理を行うことになる。そして、立寄り地ごとに目的地までの経路探索を実行すると、立ち寄り地の数だけ拡散処理を繰り返さなければならず、処理時間が増大するという問題点を有していた。
【0009】
本発明は、上記問題点に鑑みてなされたもので、適切な経由地を効率よく探索することができる、経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラムを提供することを目的とする。
【課題を解決するための手段】
【0010】
このような目的を達成するため、本発明の記憶部と制御部とを少なくとも備えた経路探索装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、を備えたことを特徴とする。
【0011】
また、本発明の経路探索装置は、上記記載の経路探索装置において、上記記憶部は、地点に関する地点情報を記憶する地点情報記憶手段、を更に備え、上記制御部は、上記地点情報記憶手段の上記地点情報から、上記複数の経由地候補を検索する経由地候補探索手段、を更に備え、上記経路探索手段は、上記ネットワークデータに基づいて、上記経由地候補検索手段により検索された上記複数の経由地候補について、上記経路探索条件の上記出発地から当該複数の経由地候補までの上記探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの上記探索経路を、それぞれ1回ずつ拡散させることを特徴とする。
【0012】
また、本発明の経路探索装置は、上記記載の経路探索装置において、上記経由地候補検索手段は、上記経路探索手段により上記出発地からの上記探索経路および上記目的地からの上記探索経路が拡散される際に、上記地点情報記憶手段から当該拡散される上記探索経路付近の上記経由地候補を検索することを特徴とする。
【0013】
また、本発明の経路探索装置は、上記記載の経路探索装置において、上記ネットワークデータ記憶手段は、上記交通網のうち、詳細な上記交通網を規定する下位階層の上記ネットワークデータと、主要な上記交通網を規定する上位階層の上記ネットワークデータと、を含む階層化された上記ネットワークデータを記憶し、上記経路探索手段は、上記出発地から上記複数の経由地候補までの上記探索経路および上記目的地から当該複数の経由地候補までの上記探索経路を拡散させる前に、上記複数の経由地候補から、上記下位階層の上記ネットワークデータに基づいて上記探索経路を拡散させることを特徴とする。
【0014】
また、本発明の経路探索装置は、上記記載の経路探索装置において、上記経路探索手段は、上記経路探索条件の上記出発地から上記目的地までの上記探索経路を拡散させて経路を更に探索し、上記探索結果情報生成手段は、上記経路探索手段により探索された、上記出発地から上記目的地までの上記経路と、上記出発地から上記経由地候補を介した上記目的地までの上記経路と、を比較した比較結果を含む上記探索結果情報を生成することを特徴とする。
【0015】
また、本発明の経路探索装置は、上記記載の経路探索装置において、上記制御部は、移動体の現在位置を示す現在位置情報を取得する現在位置情報取得手段、を更に備え、上記経路探索手段は、上記現在位置情報取得手段により取得された上記現在位置情報の上記現在位置を、上記経路探索条件の上記出発地として経路探索を行うことを特徴とする。
【0016】
また、本発明の経路探索装置は、上記記載の経路探索装置において、上記制御部は、時刻ごと地点ごとに予想される渋滞発生を示す渋滞情報を取得する渋滞情報取得手段、を更に備え、上記経路探索手段は、探索した上記出発地から上記経由地候補までの上記経路および上記目的地から当該経由地候補までの上記経路に基づいて当該目的地への予想到達時刻を算出し、上記渋滞情報に基づいて上記予想到達時刻を修正することを特徴とする。
【0017】
また、本発明の経路探索装置は、上記記載の経路探索装置において、出力部を更に備え、上記制御部は、上記出発地および上記目的地を少なくとも含む上記経路探索条件を設定する経路探索条件設定手段と、上記探索結果情報生成手段により生成された上記探索結果情報を上記出力部に出力する探索結果出力手段と、を更に備えたことを特徴とする。
【0018】
また、本発明の経路探索システムは、記憶部と制御部とを少なくとも備えたサーバ装置、および、出力部と制御部とを少なくとも備えた端末装置、を通信可能に接続した経路探索システムにおいて、上記サーバ装置の上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記サーバ装置の上記制御部は、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信手段と、上記ネットワークデータに基づいて、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、上記探索結果情報生成手段により生成された上記探索結果情報を、上記端末装置に送信する探索結果情報送信手段と、を備え、上記端末装置の上記制御部は、上記経路探索条件を上記サーバ装置に送信する経路探索条件送信手段と、上記サーバ装置から送信される、上記探索結果情報を受信する探索結果情報受信手段と、上記探索結果情報受信手段により受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力手段と、を備えたことを特徴とする。
【0019】
また、本発明の経路探索システムは、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段と、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、を備えたことを特徴とする。
【0020】
また、本発明のサーバ装置は、出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信手段と、上記ネットワークデータに基づいて、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、上記探索結果情報生成手段により生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信手段と、を備えたことを特徴とする。
【0021】
また、本発明の端末装置は、記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信手段と、上記サーバ装置から送信される、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信手段と、上記探索結果情報受信手段により受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力手段と、を備えたことを特徴とする。
【0022】
また、本発明の経路探索方法は、記憶部と制御部とを少なくとも備えた経路探索装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を含むことを特徴とする。
【0023】
また、本発明の経路探索方法は、記憶部と制御部とを少なくとも備えたサーバ装置、および、出力部と制御部とを少なくとも備えた端末装置、を通信可能に接続した経路探索システムにおいて実行される経路探索方法であって、上記サーバ装置の上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記端末装置の上記制御部において実行される、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置の上記制御部において実行される、上記端末装置から送信される、上記経路探索条件を受信する経路探索条件受信ステップと、上記サーバ装置の上記制御部において実行される、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記サーバ装置の上記制御部において実行される、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記サーバ装置の上記制御部において実行される、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信する探索結果情報送信ステップと、上記端末装置の上記制御部において実行される、上記サーバ装置から送信される、上記探索結果情報を受信する探索結果情報受信ステップと、上記端末装置の上記制御部において実行される、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を含むことを特徴とする。
【0024】
また、本発明の経路探索方法は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段と、経路探索手段と、探索結果情報生成手段と、を備えた経路探索システムにおいて実行される経路探索方法であって、上記経路探索手段が、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記探索結果情報生成手段が、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を含むことを特徴とする。
【0025】
また、本発明の経路探索方法は、出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信ステップと、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信ステップと、を含むことを特徴とする。
【0026】
また、本発明の経路探索方法は、記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置から送信される、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信ステップと、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を含むことを特徴とする。
【0027】
また、本発明のプログラムは、記憶部と制御部とを少なくとも備えた経路探索装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を実行させることを特徴とする。
【0028】
また、本発明のプログラムは、出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信ステップと、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信ステップと、を実行させることを特徴とする。
【0029】
また、本発明のプログラムは、記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置から送信される、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信ステップと、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を実行させることを特徴とする。
【発明の効果】
【0030】
この発明によれば、交通網を規定するネットワークデータを記憶し、ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索し、探索した、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する。これにより、本発明は、適切な経由地を効率よく探索することができるという効果を奏する。より具体的には、出発地から目的地までの経路から所定距離や所定時間の範囲内にない経路であっても、ロスタイムや追加の距離等が短い適切な経由地を探索することができる。また、経由地ごとに経路探索を実行するのではなく、1回の探索経路の拡散により纏めて複数の経由地の経路探索を実行することができるので、処理時間を短く効率的に探索することができる。
【0031】
また、本発明によれば、上記において、地点に関する地点情報を更に記憶し、地点情報から、複数の経由地候補を検索し、ネットワークデータに基づいて、検索された複数の経由地候補について、経路探索条件の出発地から当該複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させる。これにより、本発明は、予め記憶した地点情報の中から、適切な経由地候補を選択することができるという効果を奏する。
【0032】
また、本発明によれば、上記において、経路探索により出発地からの探索経路および目的地からの探索経路が拡散される際に、当該拡散される探索経路付近の経由地候補を地点情報から検索する。これにより、本発明は、出発地から目的地までの経路を探索しながら、探索経路に沿って好適な経由地候補を検索することができるという効果を奏する。
【0033】
また、本発明によれば、上記において、交通網のうち、詳細な交通網を規定する下位階層のネットワークデータと、主要な交通網を規定する上位階層のネットワークデータと、を含む階層化されたネットワークデータを記憶し、出発地から複数の経由地候補までの探索経路および目的地から当該複数の経由地候補までの探索経路を拡散させる前に、複数の経由地候補から、下位階層のネットワークデータに基づいて探索経路を拡散させる。これにより、本発明は、出発地周辺から目的地周辺までは上位階層のネットワークデータを用いて主要な交通網を利用した経路を探索するような場合に、経由地が主要な交通網と直接接続されていない場合であっても、経由地周辺の主要な交通網まで詳細な交通網を使って接続させることができるという効果を奏する。
【0034】
また、本発明によれば、上記において、経路探索条件の出発地から目的地までの探索経路を拡散させて経路を更に探索し、探索した、出発地から目的地までの経路と、出発地から経由地候補を介した目的地までの経路と、を比較した比較結果を含む探索結果情報を生成する。これにより、本発明は、出発地から目的地までの経路において、経由地を経由する場合と経由しない場合とで、距離や所要時間等の比較結果を利用者に分かり易く提示することができるという効果を奏する。
【0035】
また、本発明によれば、上記において、移動体の現在位置を示す現在位置情報を取得し、取得した現在位置情報の現在位置を、経路探索条件の出発地として経路探索を行うので、例えば、現在位置の更新に応じてリアルタイムに利用者に適切な経由地候補を提示することができるという効果を奏する。
【0036】
また、本発明によれば、上記において、時刻ごと地点ごとに予想される渋滞発生を示す渋滞情報を取得し、探索した出発地から経由地候補までの経路および目的地から当該経由地候補までの経路に基づいて当該目的地への予想到達時刻を算出し、渋滞情報に基づいて予想到達時刻を修正する。これにより、本発明は、渋滞情報に基づいて渋滞を加味した予想到達時間を算出するために必要となる渋滞を加味しない予想到達時間を、出発地と目的地との双方向の探索経路の拡散によって求めることができ、予想到達時間を的確に算出することができるという効果を奏する。
【0037】
また、本発明によれば、上記において、出発地および目的地を少なくとも含む経路探索条件を更に設定し、生成した探索結果情報を出力部に出力するので、利用者等に出発地と目的地を含む経路探索条件を設定させて、当該経路探索条件に基づいて生成された探索結果情報を出力することができるという効果を奏する。
【図面の簡単な説明】
【0038】
【図1】図1は、第1の実施形態における経路探索システムの構成の一例を示すブロック図である。
【図2】図2は、第1の実施形態における経路探索システムの基本処理の一例を示すフローチャートである。
【図3】図3は、双方向拡散による経路探索結果と通常の経路探索結果とを模式的に示した図である。
【図4】図4は、階層化されたネットワークデータを用いて経路探索を行う例を模式的に示した図である。
【図5】図5は、第1の実施形態における経路探索システムの具体化処理の一例を示すフローチャートである。
【図6】図6は、経路探索条件設定部102bにより表示される、経由地の検索条件の入力画面の一例を示す図である。
【図7】図7は、経路探索条件設定部102bにより表示される経由地(POI)の検索条件(エリア検索条件)の入力画面の一例を示す図である。
【図8】図8は、経路探索条件設定部102bにより表示される経由地(POI)の検索条件(周辺検索条件)の入力画面の一例を示す図である。
【図9】図9は、双方向拡散による経路探索処理の一例を示すフローチャートである。
【図10】図10は、探索結果情報生成部202dにより生成される表示画面の一例を示す図である。
【図11】図11は、探索結果情報生成部202dにより生成される複数の経由地候補を重畳させた表示画面の一例を示す図である。
【図12】図12は、第2の実施形態における経路探索装置400の構成の一例を示すブロック図である。
【図13】図13は、第2の実施形態における経路探索装置400の処理の一例を示すフローチャートである。
【発明を実施するための形態】
【0039】
以下に、本発明にかかる経路探索システム、サーバ装置、端末装置、経路探索装置、経路探索方法、および、プログラムの実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【0040】
以下、本発明の構成および処理について、第1の実施形態(経路探索システム)、第2の実施形態(経路探索装置(スタンドアローン型))の順にて詳細に説明する。
【0041】
[第1の実施形態]
最初に、本発明の第1の実施形態(経路探索システム)について、図1から図11を参照して以下に説明する。但し、以下に示す第1の実施形態は、本発明の技術思想を具体化するための経路探索システムを例示するものであって、本発明をこの経路探索システムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態の経路探索システムにも等しく適用し得るものである。例えば、第1の実施形態で例示する経路探索システムにおけるサーバ側と端末側の機能分散の形態は以下に限られず、同様の効果や機能を奏し得る範囲において、任意の単位で機能的または物理的に分散・統合して構成することができる。
【0042】
[経路探索システムの構成]
まず、第1の実施形態における経路探索システムの構成の一例について、図1を参照して以下に説明する。ここで、図1は、第1の実施形態における経路探索システムの構成の一例を示すブロック図であり、該構成のうち本発明に関係する部分のみを概念的に示している。なお、本実施形態1においては、通信型のナビゲーションを提供する経路探索システムを具体例として説明するが、本発明はこれに限ることなく、スタンドアローンタイプの経路探索システムなどにも適用可能である。
【0043】
図1に示すように、第1の実施形態の経路探索システムは、概略的に、サーバ装置200、端末装置100、および、外部機器600を通信可能に接続して構成される。ここで、図1に示すように、通信には、一例として、ネットワーク300を介した有線・無線通信等の遠隔通信等を含む。
【0044】
図1に示すように、第1の実施形態の経路探索システムにおいて、サーバ装置200は、概略的に、制御部202と記憶部206とを少なくとも備えており、端末装置100は、位置取得部112と出力部114と入力部116と記憶部106と制御部102とを備える。また、これら経路探索システムの各部は任意の通信路を介して通信可能に接続されている。
【0045】
[サーバ装置200の構成]
ここで、図1において、サーバ装置200は、端末装置100から送信される、少なくとも出発地と目的地を含む経路探索条件を受信し、ネットワークデータに基づいて、受信した経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索し、探索した、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成し、生成した探索結果情報を端末装置100に送信する等の機能を有する。サーバ装置200は、通信制御インターフェース部204を介してネットワーク300を経由し、端末装置100や外部機器600と相互に通信可能に接続されており、制御部202と記憶部206とを備える。また、ネットワーク300は、端末装置100、サーバ装置200、および、外部機器600等を相互に接続する機能を有し、例えば、インターネット、電話回線網(携帯端末回線網および一般電話回線網等)、イントラネット、または、電力線通信(PLC)等であってもよい。
【0046】
また、制御部202は、各種処理を行う制御手段である。通信制御インターフェース部204は、通信回線や電話回線等に接続されるアンテナやルータ等の通信装置(図示せず)に接続されるインターフェースであり、サーバ装置200とネットワーク300との間における通信制御を行う機能を有する。すなわち、通信制御インターフェース部204は、端末装置100や外部機器600等と通信回線を介してデータを通信する機能を有している。記憶部206は、HDD(Hard Disk Drive)等の固定ディスク装置やSSD(Solid State Drive)等のストレージ手段であり、各種のデータベースやテーブル(ネットワークデータベース206a、地図データベース206b、POIデータベース206c、および、渋滞情報データベース206d等)を格納する。
【0047】
これら記憶部206の各構成要素のうち、ネットワークデータベース206aは、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段である。ここで、ネットワークデータベース206aに記憶されるネットワークデータは、道路ネットワークデータの他、路線網ネットワークデータ等の交通機関の交通ネットワークデータであってもよい。ここで、ネットワークデータベース206aに記憶されるネットワークデータは、階層化されたネットワークデータであってもよく、例えば、交通網のうち、詳細な交通網を規定する下位階層のネットワークデータと、主要な交通網を規定する上位階層のネットワークデータと、を含んでもよい。一例として、ネットワークデータベース206aにより記憶される階層化された道路ネットワークデータは、細い路地等を含む詳細な交通網を規定する下位階層のネットワークデータと、幹線道路等を含む主要な交通網を規定する上位階層のネットワークデータとを含んでもよい。なお、階層は、道路の太さ(幅員等)や制限速度等で分類してもよく、また、2つの階層とは限らず、3以上の複数の階層があってもよい。また、階層の上位と下位は、複数の階層の中の相対的なものであり、絶対的なものではない。すなわち、中位の階層は、上位階層から見れば下位階層であり、下位階層から見れば上位階層である。これらネットワークデータは、ネットワークデータベース206aに予め記憶されており、サーバ装置200の制御部202は、定期的に、および/または、制御部202による処理に応じて(例えば、制御部202においてデータが必要となる契機等)、ネットワーク300を介して最新のデータを外部機器600(例えば、ネットワークデータを提供するネットワークデータサーバなど)等からダウンロードしてネットワークデータベース206aに記憶されたネットワークデータをアップデートしてもよい。
【0048】
ここで、ネットワークデータベース206aに記憶される道路ネットワークデータは、道路網を規定するネットワークデータであり、例えば、交差点や分岐点等の道路網表現上の結節点であるノードのノードデータと、ノード間の道路区間であるリンクのリンクデータとの組み合わせによって表現されるネットワークデータである。ノードデータには、ノード番号、緯度経度等の位置座標、ノード種別、接続するリンク本数、接続ノード番号、信号機や一時停止標識等の車両停止位置、および、交差点名称等を含んでいてもよい。また、リンクデータには、リンク番号、接続する道路の種別、国道や県道や市道等の路線番号、重用する路線情報、リンクの存在する行政区域の属性情報、リンク長、道路供用状況、異常気象時通行規制区間、車重制限、車両高さ制限、幅員、道路幅員区分、車線数、制限速度など交通規制、一時停止標識や踏切直前等の車両停止位置、高架やトンネルや橋等のリンク内属性、所要時間、および、名称等を含んでいてもよい。特に、リンクデータは、当該リンクのリンクコストを含んでいてもよく、例えば、当該道路リンクを通過するのに必要な時間や、距離や、利用料金データ等の料金に関するデータを含んでいてもよい。また、道路ネットワークデータは、交通規制データや利用料金データ等を含んでいてもよい。ここで、交通規制データは、各種の交通規制を定義するデータであり、例えば、道路の損壊や道路工事等による車両通行止、交通の安全を確保するために設置されるコミュニティ・ゾーン等による一般車の進入禁止、および、私有地への接続路であることによる一般車の進入禁止等の情報などを含んでもよい。また、利用料金データは、自動車、オートバイ等で移動する場合に消費する燃料料金、高速自動車国道や自動車専用道路等の有料道路の通行料金等を表す情報等であってもよい。また、道路ネットワークデータは、自動車、オートバイ、自転車、徒歩等で移動する場合の経路上に存在する施設等の地点の緯度経度情報などの位置情報等を記憶してもよい。なお、ネットワークデータには、ノードとリンクで構成される各案内経路についての評価を行うために、ノード番号やリンク番号等に対応付けて評価用情報が格納されてもよい。一例として、評価用情報として交通規制データは、各種の交通規制を定義するデータであり、例えば、道路の損壊や道路工事等による車両通行止、交通の安全を確保するために設置されるコミュニティ・ゾーン等による一般車の進入禁止、私有地への接続路であることによる一般車の進入禁止等の情報などを含む。
【0049】
ネットワークデータベース206aに記憶される交通ネットワークデータは、電車やバス等の交通機関の路線網等を規定したネットワークデータである。一例として、交通ネットワークデータは、電車の路線網を規定した路線網ネットワークデータであってもよく、バスの路線網を規定した路線網ネットワークデータであってもよい。例えば、ネットワークデータベース206aに記憶される交通ネットワークデータは、電車、飛行機、バス、路面電車、ロープウェイ、モノレール、ケーブルカー、および、船等の各交通機関の路線網を規定するネットワークデータであり、例えば、駅、空港、港、および、停留所(バス停)等の停止位置などの路線網表現上の結節点であるノードのノードデータと、ノード間を接続する鉄道路線、航空路線、航路、および、バス路線等のリンクのリンクデータとの組み合わせによって表現されるネットワークデータである。なお、ノードデータには、ノード番号、緯度経度等の位置座標、ノード種別、接続するリンク本数、接続ノード番号、および、線路が交差する駅名等を含んでいてもよい。また、リンクデータには、リンク番号、接続する駅等の種別、列車等の路線番号、重用する路線情報、リンクの存在する行政区域の属性情報、リンク長、道路供用状況、異常気象時通行規制区間、車重制限、車両高さ制限、幅員、道路幅員区分、車線数、制限速度など交通規制、高架やトンネルや橋等のリンク内属性、および、名称等を含んでいてもよい。また、交通ネットワークデータは、交通機関の利用運賃料金データ、および、乗車位置データ等を含んでいてもよい。ここで、利用運賃料金データは、例えば、電車、飛行機、バス、路面電車、ロープウェイ、モノレール、ケーブルカー、および、船等の各交通機関を利用した場合に生じる利用料金等を表す情報等であってもよい。
【0050】
また、地図データベース206bは、地図データを記憶する地図データ記憶手段である。一例として、地図データベース206bに記憶される地図データは、全国および各地方の道路地図等の地図データであってもよい。例えば、地図データベース206bに記憶される地図データは、地図上に表示される地物(例えば、ビルや住宅や駅等の建造物、道路、線路、橋、トンネル、等高線、海岸線や湖岸線等の水涯線、海、河川、湖、池、沼、公園や屋外施設等の地、行政界、行政区域、および、街区等)の形状についての形状データ、地図上に表示される注記(例えば、地名、住所、電話番号、店や公園や駅等の施設名称、名所や旧跡や河川や湖や湾や山や森林等の俗称を含む名称、道路や橋やトンネル等の名称、路線名称、地点情報、および、口コミ情報等)の注記データ、および、地図上に表示される記号(例えば、山、史跡、寺社、学校、病院、工場および墓地等の地図記号、ガソリンスタンド、コンビニエンスストア、スーパーマーケット、レストラン、銀行および郵便局等の店舗記号、道路上の信号、有料道路の出入口、料金所、サービスエリア、パーキングエリアおよびインターチェンジ等の記号、駐車場、駅、ホテル、美術館および博物館等の施設記号、ならびに、口コミ地点記号等)の記号データ等のデータを含んでいてもよい。なお、地図データは、道路地図等の地図データに限らず、路線図等の地図データであってもよい。ここで、地図データは、縮尺に従ってメッシュ化された地図データ(例えば、JIS規格の第1〜3次地域区画メッシュデータ、および、100mメッシュデータ等)等であってもよい。また、地図データは、ラスタ形式、ベクタ形式等の地図描画用の画像データであってもよい。これら地図データは、地図データベース206bに予め記憶されており、サーバ装置200の制御部202は、定期的に、および/または、制御部202による処理に応じて(例えば、制御部202においてデータが必要となる契機等)、ネットワーク300を介して最新のデータを、外部機器600(地図データを提供する地図提供サーバ等の外部機器等)からダウンロードして地図データベース206bに記憶された地図データをアップデートしてもよい。
【0051】
また、POIデータベース206cは、POI等に関する地点情報を記憶する地点情報記憶手段である。ここで、本実施の形態において、POI(point of interest)は、便利な場所や興味のある場所などとして人が知覚する特定の地点や施設や領域等であって、建造物や、設備、店舗、会社、事務所、公共施設、娯楽施設、および、屋外施設、観光スポットや景勝地などの地点や地物や領域等であってもよい。すなわち、本実施形態において、POIデータベース206cは、POIの地点情報を含むPOI情報を記憶する。POI情報は、少なくともPOIの地点情報(緯度経度等)のほか、POIの名称(地点名称)、カテゴリ(種別)等の属性、住所、電話番号、URL、営業時間情報、取扱商品情報、写真データ、クーポン情報、口コミ情報、使用条件、使用可能性、施設規模情報、POIの緯度経度高度、POI ID、および、当該POI情報の更新日時等の情報を含んでいてもよい。ここで、店舗は、例えば、飲食店、食料品店、酒店、タバコ店、百貨店、ショッピングセンター、スーパーマーケット、コンビニエンスストア、ガソリンスタンド、金融機関、郵便局、立体駐車場、および、ホテルや旅館等の宿泊施設等であってもよい。また、公共施設は、例えば、官庁、警察署、交番、消防署、駅、医療機関、美術館、博物館、および、学校等であってもよい。また、娯楽施設は、例えば、映画館、劇場、遊園地、パチンコ店、カジノ、競馬場等であってもよい。また、屋外施設は、バスターミナル、公園、遊園地、キャンプ場、連絡通路、屋外駐車場、および、動物園等であってもよい。これらPOI情報は、POIデータベース206cに予め記憶されており、サーバ装置200の制御部202は、定期的に、および/または、制御部202による処理に応じて(例えば、制御部202においてデータが必要となる契機等)、ネットワーク300を介して最新のデータを外部機器600(例えば、POI情報を提供する施設情報提供サーバなど)等からダウンロードしてPOIデータベース206cに記憶されたPOI情報をアップデートしてもよい。
【0052】
また、渋滞情報データベース206dは、渋滞情報を記憶する交通情報記憶手段である。ここで、渋滞情報は、時刻ごと地点ごとに予想される渋滞発生を示す情報である。一例として、渋滞情報は、道路上のリンクID等に対応づけて、渋滞が発生すると予測される時刻等を含んでもよい。また、渋滞情報は、渋滞発生地点や渋滞距離や道路上の二地点間の通過時間(すなわち、旅行時間など)等の渋滞情報を含んでいてもよい。ここで、渋滞情報は、交通障害情報や交通規制情報、鉄道等の交通機関の運行情報を含んでもよい。ここで、交通規制情報は、各種の交通規制を定義するデータであり、例えば、降水量規制、積雪・凍結規制、超波規制、風速規制、および視程規制等の異常気象時通行規制、高さ規制および重量規制等の車両通行規制、道路工事や作業、道路周辺の工事に伴う工事時規制、時間帯や車種により通行できる通行帯を規制している通行帯規制および道路の損壊等による車両通行止、交通の安全を確保するために設置されるコミュニティ・ゾーン等による一般車の進入禁止、ならびに、私有地への接続路であることによる一般車の進入禁止等の情報などを含んでもよい。また、交通規制情報は、工事、事故、または、車両故障等により車両通行帯等が走行不能または走行困難となる通行規制情報であってもよい。また、これら渋滞情報は、渋滞情報データベース206dに予め記憶されており、サーバ装置200の制御部202(後述する渋滞情報取得部202f)は、定期的(例えば、5分毎等)にネットワーク300を介して最新のデータを外部機器600(例えば、警察庁、VICS(Vehicle Information and Communication System)(登録商標)、および、ATiS(Advanced Traffic Information Service)(登録商標)、日本道路交通情報センター(JARTIC)(登録商標)、鉄道会社、および、渋滞情報配信サーバ(サービス)など)等からダウンロードして渋滞情報データベース206dに記憶された交通情報をアップデートしてもよい。
【0053】
また、制御部202は、OS(Operating System)等の制御プログラムや、各種の処理手順等を規定したプログラム、および、所要データを格納するための内部メモリを有する。そして、制御部202は、これらのプログラム等により、種々の処理を実行するための情報処理を行う。制御部202は、機能概念的に、経路探索条件受信部202a、経由地候補検索部202b、経路探索部202c、探索結果情報生成部202d、探索結果情報送信部202e、および、渋滞情報取得部202fを備える。
【0054】
このうち、経路探索条件受信部202aは、端末装置100から送信される、少なくとも出発地と目的地を含む経路探索条件を受信する経路探索条件受信手段である。なお、経路探索条件受信部202aにより受信される経路探索条件は、現在位置情報を含んでもよい。例えば、経路探索条件受信部202aは、現在位置情報受信部202aにより受信される端末装置100の現在位置情報による現在位置を、経路探索条件の出発地として取得してもよい。また、端末装置100より送信される更新された現在位置情報を受信した場合等には、経路探索条件受信部202aは、最新の現在位置情報による現在位置を、経路探索条件の出発地として再設定してもよい。
【0055】
また、経由地候補検索部202bは、POIデータベース206cに記憶されたPOIの地点情報(POI情報)から、複数の経由地候補を検索する経由地候補探索手段である。ここで、経路探索部202cにより経路探索条件の出発地からの探索経路および目的地からの探索経路が拡散されると同時に、経由地候補検索部202bは、拡散される探索経路に基づいて、POIデータベース206cから探索経路付近の複数のPOIを、複数の経由地候補として検索してもよい。すなわち、経路探索部202cが探索経路を拡散させる場合に、経由地候補検索部202bは、POIデータベース206cに記憶されたPOIの地点情報に基づいて、当該拡散中の探索経路上または探索経路付近に存在するPOIを経由地候補として取得してもよい。なお、上記に限らず、経由地候補検索部202bは、経路探索条件の出発地や現在位置(所定時間後の予想現在位置でもよい。)や目的地等の周辺(例えば、所定の形状範囲内)に存在するPOIを、POIデータベース206cから検索してもよい。例えば、経由地候補検索部202bは、出発地および目的地の2点を焦点とする楕円の範囲内に位置するPOIを経由地候補として検索してもよい。また、経由地候補検索部202bは、経路探索条件としてPOIのカテゴリが指定されている場合に、当該カテゴリに該当するPOIに絞込み検索を行ってもよい。
【0056】
また、経路探索部202cは、ネットワークデータベース206aに記憶されたネットワークデータに基づいて、経路探索を実行する経路探索手段である。例えば、経路探索部202cは、経路探索条件受信部202aにより受信された経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索してもよい(なお、ネットワークデータ等の木構造データにおいて、探索経路は探索木と呼ばれることがある)。出発地から目的地への方向から見れば、出発地から経由地へは順方向であり、目的地から経由地へは逆方向となるので、本実施の形態においては、当該経路探索方法を、「双方向拡散」による経路探索と呼ぶ。なお、経路探索部202cは、双方向拡散による経路探索に限らず、経路探索条件の出発地から目的地までの探索経路を拡散させて、通常の経路探索を行ってもよい。なお、上述したように、経路探索部202cは、双方向拡散による経路探索を行う際に、経由地候補検索部202bにより、拡散中の探索経路上または探索経路付近に存在するPOIを経由地候補として検索させてもよい。
【0057】
ここで、本実施形態において実行される、経路探索部202cによる「拡散」について説明する。本実施形態において、「拡散」とは、ダイクストラ法やA*(エースター)探索アルゴリズム等の公知の経路探索手法において、順次到達したノードやリンク等が広がることをいう。例えば、ダイクストラ法においては、基準点(一般的には、出発地に近いノード)から、順次、接続されたリンクを辿って次のノードに到達し、辿ったリンクのリンクコスト(距離や通過所要時間等)を積算し、リンクコストが最小となるように次に辿るリンク群(探索経路)を管理しながら、目的の点(一般的には、目的地に近いノード)まで探索経路を広げていくものであるが、この探索経路を広げることを拡散と呼ぶ。なお、当然、分岐が存在し、一つのノードに3本以上のリンクが接続される場合があるので、探索経路は、通常一本のままではなく、積算リンクコストが同列(同程度)の複数の探索経路が拡散とともに増えていくことになる。なお、上述の説明では、一般的な探索手法として、出発地から目的地までの通常の拡散による経路探索を行う例を挙げて説明したが、本実施形態では、経路探索部202cは、双方向拡散による経路探索において、出発地(基準点)から複数の経由地候補(目的の点)までの1回の拡散と、目的地から(基準点)から当該複数の経由地候補までの1回の拡散を、それぞれ実行する点に特徴がある。なお、通常は、目的の点は1点であるので、当該1点に到達したときに拡散を終了させるが、経路探索部202cは、複数の経由地候補の全ての点に到達するまで探索経路を拡張させる。なお、拡散の終了条件は、これに限られず、拡散リンクが反対側の地点(例えば、出発地側からの拡散の場合は目的地、目的地側からの拡散の場合は出発地)に到達したことであってもよく、また、算出されるリンクコストに従って、目的地または出発地に到達してから拡散により、所定分多くのリンクコスト(時間、距離、料金等)が算出されたときであってもよい。これにより、より多くのPOI等を候補リンクとすることができる。
【0058】
なお、ダイクストラ法等で経路探索を行う場合、拡散していく探索経路の1本毎にリンクコストを演算して求めていかなければならず、探索経路の数に応じて処理時間が長くなり、サーバ装置200の処理負荷が大きくなってしまうという問題点がある。そのため、出発地や目的地や経由地候補等の地点周辺では、(細い路地まで詳細な道路網を規定した)下位階層のネットワークデータを用いて探索経路を拡張し、その後、地点間では、(主要な道路網のみを規定した)上位階層のネットワークデータを用いて探索経路を拡張して、経路探索を行ってもよい。特に、本実施の形態において双方向拡散による経路探索を行う場合、経路探索部202cは、双方向拡散を行う前に、複数の経由地候補から、下位階層のネットワークデータに基づいて探索経路を拡散させてもよい。
【0059】
また、経路探索部202cは、双方向拡散により算出した出発地から経由地までの所要時間と目的地から経由地までの所要時間を加算することにより、出発地から経由地(候補)を経由して目的地に到達するための所要時間を計算することができる。また、経路探索部202cは、経由地(候補)での滞在時間を考慮して所要時間を算出するようにしてもよい。例えば、経由地(候補)が飲食店の時は所要時間に1時間を加算することなどが考えられる。
【0060】
また、経路探索部202cは、双方向探索により算出した出発地から目的地までの経路に対して、別途所要時間の再計算処理を行うようにしてもよい。双方向拡散のうち目的地側から拡散させる場合、各リンクにおける参照すべき渋滞情報の時刻が未知であり、それにより算出される所要時間の精度が低くなる。出発地から目的地までの経路を構成する全ノードに対し、出発地側から順に「出発地から対象ノードまでの所要時間」を再計算することで、各ノードにおける通過時刻が高い精度で求まる(出発時刻に「出発地から対象ノードまでの所要時間」を加算したものが対象ノードの通過時刻となる)。これにより、各リンクにおいて適切な時刻の渋滞情報を参照できるようになり、出発地から目的地までの所要時間および予想到達時刻の精度を高くすることができる。
【0061】
また、経路探索部202cは、双方向拡散の目的地側から拡散させる場合に、各リンクの予測通過時刻を他の情報から予測するようにしてもよい。一例として、別途計算される目的地への仮の予測到着時刻から「目的地から拡散対象リンクまでの所要時間」を引くことで、拡散対象リンクの予測通過時刻を決定してもよい。目的地への仮の予測到着時刻の算出方法の一例として、別途出発地から目的地への経由地無しの経路探索を行い、これにより得られた到着時刻を仮の予測到着時刻とすることが考えられる。また、別の例として、出発地から目的地への直線距離を平均走行時速で割ることにより、出発地から目的地までの所要時間を計算し、そこから仮の予測到着時刻を算出することが考えられる。また、経路探索部202cは、経由地(候補)での滞在時間を考慮して仮の予測到着時刻を算出するようにしてもよい。例えば、経由地候補がすべて飲食店の時は仮の予測到着時刻に1時間を加算することなどが考えられる。
【0062】
また、探索結果情報生成部202dは、経路探索部202cにより探索された、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する探索結果情報生成手段である。例えば、探索結果情報生成部202dは、双方向拡散により探索された、出発地から経由地候補までの経路と、目的地から当該経由地候補までの経路とを繋ぎ合わせることによって、出発地から当該経由地候補を介した目的地までの経路を生成し、当該経路を示す探索結果情報を生成してもよい。ここで、探索結果情報生成部202dは、経路探索部202cにより探索された、出発地から目的地までの経路と、出発地から経由地候補を介した目的地までの経路と、を比較した比較結果を含む探索結果情報を生成してもよい。例えば、探索結果情報生成部202dは、両経路の所要時間の比較結果(経由地候補を経由しない場合と比べて増大する所要時間(すなわち、ロスタイム)等)のほか、両経路の距離や料金等の比較結果(差,比,割合等)を示す探索結果情報を生成してもよい。なお、探索結果情報生成部202dは、これら比較結果を降順や昇順にソート等を行って、決定した表示順序で表示されるように(例えば、ロスタイムが短い順にPOIが表示されるように)探索結果情報を生成してもよい。また、探索結果情報生成部202dは、候補数が所定数以上の場合に、比較結果に従って上位のものだけ表示されるようにフィルタリング処理を行って、探索結果情報を生成してもよい。また、探索結果情報生成部202dは、地図データベース206bに記憶された地図データに経由地候補を重畳させた表示画面を含む探索結果情報を生成してもよい。その際、探索結果情報生成部202dは、出発地や、目的地、出発地から目的地までの経路、出発地から経由地候補を介した目的地までの経路等を地図データ上に重畳させてもよい。
【0063】
また、探索結果情報送信部202eは、探索結果情報生成部202dにより生成された探索結果情報を、端末装置100に送信する探索結果情報送信手段である。
【0064】
また、渋滞情報取得部202fは、渋滞情報を取得する渋滞情報取得手段である。例えば、渋滞情報取得部202fは、定期的(例えば、5分毎等)にネットワーク300を介して最新のデータを外部機器600(例えば、警察庁、VICS(登録商標)などの渋滞情報配信サーバなど)等からダウンロードして渋滞情報データベース206dに記憶された交通情報をアップデートしてもよい。
【0065】
[端末装置100の構成]
また、図1において、端末装置100は、経路探索条件をサーバ装置200に送信し、サーバ装置200から送信される、探索結果情報を受信し、受信した探索結果情報を出力部114に出力する等の機能を有する。端末装置100は、例えば、一般に市販されるデスクトップ型またはノート型のパーソナルコンピュータ等の情報処理装置、携帯電話やPHSやPDA等の携帯端末装置、および、走行経路案内等を行なうナビゲーション端末等である。ここで、端末装置100は、インターネットブラウザ等を搭載していてもよく、経路案内アプリケーションや乗換案内アプリケーション等を搭載していてもよい。また、端末装置100は、リアルタイムに現在位置取得が行えるよう、GPS機能やIMES機能等を有する位置取得部112を備える。また、端末装置100は、少なくとも出力部114と入力部116と制御部102を備える。ここで、出力部114は、表示案内データ等の表示画面を表示する表示手段(例えば、液晶や有機EL等から構成されるディスプレイやモニタ等)のほか、サーバ装置200から受信した探索結果情報を音声として出力する音声出力手段(例えば、スピーカ等)であってもよい。また、入力部116としては、例えば、キー入力部、タッチパネル、キーボード、マイク等であってもよい。また、入出力制御インターフェース部108は、位置取得部112、出力部114、および、入力部116等の制御を行う。
【0066】
ここで、位置取得部112は、例えば、位置発信装置500から発信される位置情報信号を受信する位置取得手段であってもよい。ここで、位置発信装置500は、位置情報信号(GPS信号)を発信するGPS装置であってもよく、また、GPS信号と類似した特徴を持つ位置情報信号を用いて屋内測位を可能とするIMES(Indoor Message System)技術を実現するIMES装置であってもよい。なお、IMES技術は測位衛星システムである準天頂衛星の枠組みから発案されたシステムである。また、位置発信装置500は、屋外で受信したGPS信号を屋内で発信するGPSリピータであってもよい。また、位置発信装置500は、建物(例えば、立体駐車場等)内の各フロアや地下構造物(例えば、トンネル、地下駐車場等)の各所に任意に設置される小型発信装置であってもよい。なお、この小型発信装置には、設置場所に応じた自己位置情報(位置ID等)が割り振られている。そして、端末装置100が通信可能範囲に入ると、端末装置100は、小型発信装置から送信される自己位置情報を位置情報信号として受信する。この際の通信方式は、例えば、RFID(Radio Frequency Identification)タグシステムやBluetooth(登録商標)等の各種近距離無線方式や、赤外線通信方式等であってもよい。また、位置発信装置500は、無線LANのアクセスポイントであってもよい。本実施形態において、位置取得部112は、無線LAN信号等を受信して、アクセスポイントの識別情報を取得してもよい。そして、制御部102は、位置取得部112にて取得したアクセスポイント固有の識別情報からアクセスポイントの位置を特定して位置情報を取得してもよい。また、本実施形態において、制御部102は、位置取得部112にて取得された位置情報信号から、緯度、経度、および、高さ情報を含む位置情報を算出してもよい。ここで、位置情報は、緯度および経度により特定される絶対位置の他、基準となる位置からの相対位置を示すものであってもよい。
【0067】
また、位置取得部112は、例えば、位置取得部112の加速度センサにて検出した端末装置100の加速度情報、方位センサにて検出した端末装置100の進行方向等の方位情報、距離センサにて検出した距離情報、および、地図データに基づいて端末装置100の利用者の現在位置を示す位置情報を取得してもよい。ここで、方位センサには、端末装置100の絶対走行方位を検出する地磁気センサおよび端末装置100の相対走行方位を検出する光ジャイロが使用されてもよい。また、方位センサは、地磁気センサと加速度センサを組み合わせることで方位や傾きに関する情報を取得できる電子コンパスであってもよい。
【0068】
また、通信制御インターフェース部104は、通信回線や電話回線等に接続されるアンテナやルータ等の通信装置(図示せず)に接続されるインターフェースであり、端末装置100とネットワーク300との間における通信制御を行う機能を有する。すなわち、通信制御インターフェース部104は、サーバ装置200等と通信回線を介してデータを通信する機能を有している。
【0069】
また、記憶部106は、HDDやSSD等の大容量のストレージ手段、および/または、SRAM(Static Random Access Memory)等を用いて構成される小容量高速メモリ(例えば、キャッシュメモリ)等のストレージ手段であり、各種のデータベースやファイルやテーブルを格納してもよい。ここで、記憶部106は、外部機器600等から受信した地図情報や、サーバ装置200から受信した探索結果情報などの各種のファイル等を一時的に記憶するものであってもよい。
【0070】
また、案内データファイル106aは、案内データを記憶する案内データ記憶手段である。案内データファイル106aに記憶される案内データは、案内経路上において出力される音声案内データや表示案内データ等のデータである。ここで、音声案内データは、案内経路上の分岐点等における進行方向に対応付けられた「次の交差点を左に曲がります」や、現在位置が目的地に近づいた場合に対応付けられた「まもなく目的地周辺です」等の音声案内用のデータであってもよく、この音声案内データは、端末装置100の探索結果情報出力部102eが、探索結果情報に記憶された経路の情報に基づいて、音声案内等の経路案内を実行する際に用いられてもよい。また、表示案内データは、案内経路上の分岐点等における進行方向に対応付けられたターンバイターン(TBT)や、現在位置が選択施設に近づいた旨の案内等の表示案内用のデータであってもよく、この表示案内データは、端末装置100の探索結果情報出力部102eが表示案内を実行する際に用いられる。ここで、TBTとは、右左折等の誘導を画面に表示する矢印ナビゲーションである。これら案内データは、探索結果情報として受信されてもよく、案内データファイル106aに予め記憶されてもよい。端末装置100の制御部102は、定期的に、および/または、制御部102による処理に応じて(例えば、制御部102においてデータが必要となる契機等)、ネットワーク300を介して最新の案内データを外部機器600(例えば、案内データを提供する案内データ提供サーバなど)等からダウンロードして案内データファイル106aに記憶された案内データをアップデートしてもよい。
【0071】
また、制御部102は、OS等の制御プログラムや、各種の処理手順等を規定したプログラム、および、所要データを格納するための内部メモリを有する。そして、制御部102は、これらのプログラム等により、種々の処理を実行するための情報処理を行う。制御部102は、機能概念的に、現在位置情報取得部102a、経路探索条件設定部102b、経路探索条件送信部102c、探索結果情報受信部102d、および、探索結果情報出力部102eを備える。
【0072】
このうち、現在位置情報取得部102aは、端末装置100の利用者の現在位置情報を取得する現在位置情報取得手段である。ここで、現在位置情報取得部102aは、端末装置100の利用者の現在位置情報を所定周期ごと(例えば、1秒ごと等)に取得してもよい。ここで、現在位置情報取得部102aは、定期的に、または、更新毎に、取得した現在位置情報をサーバ装置200に送信してもよい。また、現在位置情報取得部102aは、位置取得部112にて位置発信装置500から受信した位置情報信号から算出した位置情報を、端末装置100の利用者の現在位置情報として取得してもよい。更に、位置取得部112の方位センサ等にて検出した端末装置100の進行方向等の方位情報や、位置取得部112の加速度センサにて検出した端末装置100の加速度情報を、端末装置100の利用者の現在位置情報として取得してもよい。また、現在位置情報取得部102aは、利用者により入力部116を介して入力された現在位置についての位置座標等を端末装置100の利用者の現在位置情報として取得してもよい。ここで、利用者により入力部116を介して入力された現在位置は、利用者が現実に存在する位置であってもよく、利用者により任意に選択された仮想の現在位置(一例として、東京にいる利用者により選択された大阪の駅や空港等の任意の地点)であってもよい。具体的には、現在位置情報取得部102aは、入力部116を介して利用者に出力部114に表示された地図データの表示画面上で指定(例えば、タッチパネル式の表示部での指定操作等)させた座標を端末装置100の利用者の現在位置情報として取得してもよい。更に、入力部116を介して利用者に出力部114に表示された地図データの表示画面上で指定させた方位情報を端末装置100の利用者の現在位置情報として取得してもよい。ここで、現在位置情報取得部102aは、利用者の現在位置情報とともに、当該現在位置情報を取得した日時情報を取得してもよい。
【0073】
また、経路探索条件設定部102bは、出発地および目的地を少なくとも含む経路探索条件を設定する経路探索条件設定手段である。ここで、経路探索条件設定部102bは、入力部116を介して、利用者に出発地や目的地等の経路探索条件を入力させるよう制御してもよい。また、経路探索条件は、更に、出発時刻または到着時刻を含んでいてもよい。ここで、出発時刻は、現在時刻であってもよい。また、経路探索条件に、経由地の嗜好や経由時刻を加えてもよく、例えば、経路探索条件設定部102bは、利用者に入力部116を介して、経由地候補として検索されるPOIのカテゴリ等を指定させるよう制御してもよい。また、経路探索条件設定部102bは、経路探索条件に、現在位置情報取得部102aにより取得された現在位置情報の現在位置を追加してもよく、経路探索条件の目的地として当該現在位置を設定してもよい。
【0074】
また、探索結果情報受信部102dは、サーバ装置200から送信される、探索結果情報を受信する探索結果情報受信手段である。
【0075】
また、探索結果情報出力部102eは、探索結果情報受信部102dにより受信された探索結果情報を、出力部114に出力する探索結果情報表示手段である。例えば、探索結果情報出力部102eは、探索結果情報をモニタ等の出力部114に表示させてもよく、探索結果情報に従ってスピーカ等に音声出力してもよい。なお、探索結果情報出力部102eは、探索結果情報に含まれる経路の情報に従って、案内データファイル106aに記憶された案内データ等を参照して、音声案内等の経路案内を行ってもよい。
【0076】
以上で、本実施形態における経路探索システムの構成の一例の説明を終える。
【0077】
[経路探索システムの処理]
次に、このように構成された本実施形態における経路探索システムの基本処理の一例について、以下に図2から図4を参照して詳細に説明する。図2は、第1の実施形態における経路探索システムの基本処理の一例を示すフローチャートである。
【0078】
図2に示すように、まず、端末装置100の経路探索条件設定部102bは、利用者に入力部116を介して、少なくとも出発地と目的地を含む経路探索条件を設定させる(ステップSA−1)。ここで、出発地は、現在位置情報取得部102aにより取得される現在位置情報に基づく端末装置100の利用者の現在位置であってもよく、経路探索条件に、出発地とは別に当該現在位置の条件を加えてもよい。なお、経路探索条件設定部102bは、経路探索条件として、経由地の嗜好(例えば、経由地候補として検索されるPOIのカテゴリ等)を、利用者に指定させてもよい。
【0079】
そして、端末装置100の経路探索条件送信部102cは、経路探索条件設定部102bにより設定された経路探索条件を、サーバ装置200に送信する(ステップSA−2)。
【0080】
そして、サーバ装置200の経路探索条件受信部202aは、端末装置100から送信される、少なくとも出発地と目的地を含む経路探索条件を受信する(ステップSA−3)。
【0081】
そして、サーバ装置200の経由地候補検索部202bは、POIデータベース206cに記憶された地点情報(POI情報等)から、複数の経由地候補を検索する(ステップSA−4)。ここで、経由地候補検索部202bは、経路探索条件受信部202aにより受信された経路探索条件の出発地や現在位置(所定時間後の予想現在位置でもよい。)や目的地等を含む、所定の形状範囲内に存在するPOIを、POIデータベース206cから検索してもよい。所定の形状範囲の一例として、経由地候補検索部202bは、出発地および目的地の2点を焦点とする楕円の範囲内に位置するPOIを経由地候補として検索してもよい。また、経由地候補検索部202bは、経路探索条件としてPOIのカテゴリ等が指定されている場合に、当該指定されたカテゴリ等に該当するPOIに絞込み検索を行ってもよい。
【0082】
そして、サーバ装置200の経路探索部202cは、ネットワークデータベース206aに記憶されたネットワークデータに基づいて、経由地候補検索部202bにより検索された複数の経由地候補について双方向拡散による経路探索を実行する(ステップSA−5)。具体的には、経路探索部202cは、経路探索条件受信部202aにより受信された経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて、双方向拡散による経路探索を行う。なお、双方向拡散による経路探索以外にも、経路探索部202cは、出発地から目的地まで探索経路を拡散させる、通常の経路探索を行ってもよい。ここで、図3は、双方向拡散による経路探索結果と通常の経路探索結果とを模式的に示した図である。図3において、Sは、出発地を示し、Gは、目的地を示し、星印は、経由地候補を示す。また、図中の矢印は、探索結果の経路を表し、実線の矢印は、出発地から目的地までの通常の経路探索による経路(例えば、最短経路)を示し、破線の矢印は、双方向拡散の経路探索による、出発地または目的地から、経由地候補までの経路を示している。
【0083】
図3に示すように、経由地候補検索部202bにより3箇所の経由地候補(立ち寄り候補点A〜C)が検索された場合、経路探索部202cは、出発地から3箇所の経由地候補まで、探索経路を1回拡散させて、経路探索を行う。すなわち、経路探索部202cは、探索経路が3箇所全ての経由地候補に到達するまで拡散処理を継続し、出発地から各経由地候補までの経路R10〜R12の探索を1度の拡散処理で完了する。同様に、経路探索部202cは、目的地から3箇所の経由地候補まで探索経路を1回拡散させて、目的地から各経由地候補までの経路R20〜R22を得る。なお、出発地から各経由地候補までの拡散処理と、目的地から各経由地候補までの拡散処理とは、いずれを先に実行してもよく、同時に並列処理を行ってもよい。図3に示すように、双方向拡散による経路探索に加えて通常の経路探索を行ってもよく、経路探索部202cは、出発地から目的地まで探索経路を拡散させて、経路R1を取得してもよい。なお、経路探索において計算するリンクコストを所要時間とした場合、図3の各経路に付した時間(分)に示すように、それぞれの最短時間経路を求めることができるが、これに限られず、求めるリンクコストは、距離や料金等であってもよい。
【0084】
また、図3の吹き出しに記載のように、経路探索部202cは、双方向拡散の結果探索した、経路探索条件の出発地から経由地候補までの経路、および、目的地から当該経由地候補までの経路に基づいて(具体的には、両者の所要時間を加算して)、予測される当該目的地への到着時刻を算出してもよい。なお、経路探索部202cは、目的地から当該経由地候補までの経路を逆向きに探索する場合、参照すべき渋滞情報の時刻が未知であるため、そのままでは渋滞を加味した予想到達時刻の算出ができない。そのため、経路探索部202cは、得られた経路に対して、出発地から目的地までのノードに対して順に通過時刻を求めていくことで目的地への予想到達時刻を再計算するようにしてもよい。すなわち、出発時刻と「出発地から対象ノードまでの経路の所要時間」から対象ノードの通過時刻が算出できるため、渋滞情報データベース206dから正しい時刻の渋滞情報を取得することができ、その結果精度の高い予想到着時刻を計算することができる。
【0085】
ここで、経路探索部202cは、処理時間を短縮するために、ネットワークデータベース206aに記憶された、階層化されたネットワークデータを用いて経路探索を行ってもよい。すなわち、経路探索では、拡散していく探索経路の1本毎にリンクコストを演算して求めていかなければならないため、全ての詳細な道路網まで規定したネットワークデータを用いると、探索経路の数が爆発的に増えて膨大な処理時間がかかるという問題が発生する。そのため、経路探索部202cは、出発地や目的地や経由地候補等の地点周辺では、下位階層の(細い路地までの詳細な道路網を規定した)ネットワークデータを用いて探索経路を拡張し、地点間では、上位階層の(主要な道路網のみを規定した)ネットワークデータを用いて探索経路を拡張して、経路探索を実行してもよい。特に、双方向拡散による経路探索を実行する際、経路探索部202cは、双方向拡散を行う前に、複数の経由地候補から、下位階層のネットワークデータに基づいて探索経路を拡散させてもよい。ここで、図4は、階層化されたネットワークデータを用いて経路探索を行う例を模式的に示した図である。図3と同様に、Sは出発地、Gは目的地、星印は経由地候補を示す。
【0086】
図4は、出発地、目的地、および、3箇所の経由地候補の位置関係と、この位置空間において用いるネットワークデータの階層L1〜L3の関係を表している。L1は、比較的下位階層であり、L3は、比較的上位階層である。図4に示すように、経路探索部202cは、まず、出発地、目的地、経由地候補のそれぞれから、L1のネットワークデータを用いて、探索経路を拡散させる。つぎに、経路探索部202cは、L1で拡散させた探索経路に続けて、L2のネットワークデータを用いて、探索経路を拡散させる。そして、以上の下準備を終えると、経路探索部202cは、到達したリンク(探索経路を構成するリンク群)に「探索対象」のラベルを付しておく。そして、経路探索部202cは、双方向拡散による経路探索実行時に、主要な道路等のL3のネットワークデータに加えて、探索対象のネットワークデータを用いて、探索経路を拡散させる。これにより、特に、経由地候補が、L3のリンク近傍にない場合であっても、出発地または目的地からの探索経路を、L1やL2の比較的下位の階層のネットワークデータを用いて、各経由地候補まで辿り着かせることができる。換言すれば、経由地候補に接続される道路の階層が低いことにより、出発地または目的地から当該経由地候補までを探索できなくなる可能性を軽減させることができる。その一方で、出発地や経由地候補や目的地の地点周辺以外の地点間では、幹線道路などの主要な道路網のネットワークデータを用いて経路探索を行うので、所要時間や距離等が短い経由地候補を発見することができる。
【0087】
再び図2に戻り、サーバ装置200の探索結果情報生成部202dは、経路探索部202cにより探索された、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する(ステップSA−6)。例えば、探索結果情報生成部202dは、双方向拡散により探索された、出発地から経由地候補までの経路と、目的地から当該経由地候補までの経路とを繋ぎ合わせることによって、出発地から当該経由地候補を介した目的地までの経路を生成し、当該経路を示す探索結果情報を生成してもよい。また、探索結果情報生成部202dは、地図データベース206bに記憶された地図データに経由地候補を重畳させた表示画面を含む探索結果情報を生成してもよい。その際、探索結果情報生成部202dは、出発地や、目的地、出発地から目的地までの経路、出発地から経由地候補を介した目的地までの経路等を地図データ上に重畳させた探索結果情報を生成してもよい。
【0088】
ここで、探索結果情報生成部202dは、経路探索部202cにより探索された、出発地から目的地までの経路と、出発地から経由地候補を介した目的地までの経路と、を比較した比較結果を含む探索結果情報を生成してもよい。例えば、上述した図3に示したように、探索結果情報生成部202dは、両経路の所要時間の差、すなわち、経由しない場合と比べて各経由地候補を経由することで増加する所要時間(すなわち、ロスタイム)を、下記の式を用いて算出してもよい。そして、当該ロスタイムを図3のように表示する表示画面を含む探索結果情報を生成してもよい。
(ロスタイム)=(出発地から経由地候補までの所要時間)+(目的地から当該経由地候補までの所要時間)−(出発地から目的地までの所要時間)
【0089】
このほか、探索結果情報生成部202dは、両経路の距離や料金等の比較結果(差,比,割合等)を示す探索結果情報を生成してもよい。なお、探索結果情報生成部202dは、これら比較結果を降順や昇順にソート等して、決定した表示順序で一覧表示されるように(例えば、ロスタイムが短い順にPOIが表示されるように)探索結果情報を生成してもよい。なお、探索結果情報生成部202dは、出発地から目的地までの(経由地候補を経由しない)経路との比較結果に基づいて表示順序を決定することに限らず、出発地から目的地までの経路探索を行うことなく、出発地から各経由地候補を介した目的地までの経路を、経由地候補同士で所要時間や距離や料金等に基づいて、ソート等を行って表示順序を決定してもよい。また、ソートを行うことに限らず、探索結果情報生成部202dは、候補数が所定数以上の場合に、比較結果に従って上位のものだけ表示されるようにフィルタリング処理を行って、探索結果情報を生成してもよい。
【0090】
そして、サーバ装置200の探索結果情報送信部202eは、探索結果情報生成部202dにより生成された探索結果情報を端末装置100に送信する(ステップSA−7)。
【0091】
そして、端末装置100の探索結果情報受信部102dは、サーバ装置200から送信された探索結果情報を受信する(ステップSA−8)。
【0092】
そして、端末装置100の探索結果情報出力部102eは、探索結果情報受信部102dにより受信された探索結果情報を、出力部114に出力する(ステップSA−9)。ここで、探索結果情報出力部102eは、探索結果情報に含まれる地図データや経路上に、現在位置情報取得部102aにより更新される現在位置情報を重畳した表示画面を、出力部114に表示させてもよい。また、探索結果情報出力部102eは、現在位置情報取得部102aにより更新される現在位置情報の現在位置が、探索結果情報に含まれる経由地候補の所定範囲内または経由地候補を介する経路への分岐点に近づいた場合に、当該経由地候補があることを音声や表示等により出力してもよい。ここで、利用者により入力部116を介して複数の経由地候補の中から一の経由地が選択された場合、探索結果情報出力部102eは、探索結果情報に基づいて、選択された経由地を経由する経路に従って経路案内を実行してもよい。なお、端末装置100は、探索結果情報に当該経由地を経由する経路を示す情報が格納されていない場合、経路探索条件送信部102cにより、当該経路を示す情報の要求(選択された経由地を更に含む経路探索条件等)をサーバ装置200に送信して、サーバ装置200から当該経路を示す情報を含む探索結果情報を受信してもよい。その際、サーバ装置200の経路探索部202cは、経路探索の精度を上げるため、選択された経由地について再度、経路探索を行ってもよい。すなわち、上述した双方向拡散による経路探索(SA−5)において上述のように、目的地から経由地候補に向けて本来と逆方向に経路探索を行っていたので、各経由地候補を介した経路について再計算を行っていなかった場合、精度に劣る。そこで、経路探索部202cは、出発地から選択された経由地を介して目的地に至るまでの探索経路について、出発地から目的地までのノードに対して順に通過時刻を求めていくことで、より精度の高い目的地への予想到達時刻を再計算してもよい。なお、その際、経由地での滞在時間を考慮してもよく、例えば、経由地が飲食店の場合は、所要時間に1時間を加算してもよい。
【0093】
なお、本実施の形態において、上述したステップSA−1〜ステップSA−9の処理が繰り返されるよう制御してもよい。例えば、端末装置100の経路探索条件送信部102cが、現在位置情報取得部102aにより現在位置情報が更新される毎に、経路探索条件設定部102bにより再設定された現在位置情報を含む経路探索条件をサーバ装置200に送信することにより、上述したステップSA−1〜ステップSA−9の処理が繰り返されるよう制御してもよい。これにより、現在位置情報の更新に応じて、探索結果情報出力部102eにより出力される探索結果情報がリアルタイムに更新されることになる。また、サーバ装置200の渋滞情報取得部202fが、渋滞情報の更新を検出した場合(外部機器600等から新たな渋滞情報を受信した場合など)あるいは一定間隔ごとに、既に取得した経路探索条件に基づいて、ステップSA−4〜ステップSA−9の処理を繰り返すよう処理を行ってもよい。
【0094】
以上が、第1の実施形態における経路探索システムの基本処理の一例である。
【0095】
[具体化処理]
つづいて、本実施形態における経路探索システムの具体化処理の一例について図5から図11を参照して説明する。この具体化処理においては、上述した基本処理において特にサーバ装置200側の処理の詳細について説明する。ここで、図5は、第1の実施形態における経路探索システムの具体化処理の一例を示すフローチャートである。
【0096】
図5に示すように、端末装置100は、経路探索条件設定部102bにより、少なくとも出発地と目的地を含む経路探索条件を設定し、経路探索条件送信部102cにより、経路探索条件をサーバ装置200に送信すると、サーバ装置200の経路探索条件受信部202aは、端末装置100から送信された経路探索条件を取得する(ステップSB−1)。ここで、経路探索条件は、経由地の検索条件を含んでもよく、例えば、経由地の嗜好(POIのカテゴリなど)等であってもよい。ここで、図6は、経路探索条件設定部102bにより表示される、経由地の検索条件の入力画面の一例を示す図である。なお、この例では、出発地と目的地の経路探索条件が入力されていることを前提としてもよい。
【0097】
図6に示すように、経路探索条件設定部102bは、POIデータベース206cからカテゴリ(種別)等の属性に基づいてPOIを検索するための、検索条件を利用者に入力部116を介して入力させる入力画面を出力部114に表示してもよい。例えば、図6に示すように、入力画面は、利用者が予め設定しておいた利用者の嗜好に合うカテゴリ(この例では、ラーメンやガソリン)の中から選択させるための、Myジャンル選択ボタンMA−1を含んでもよい。また、POIの名称や属性等のPOI情報を検索するためのキーワードを入力させるための、フリーワード入力欄MA−2を入力画面に含んでもよい。また、利用者が複数の項目(この例では、評判、ロスタイム、到着時刻)について優先度をGUI(Graphical User Interface)形式で入力させるための優先度レーダーチャートMA−3を入力画面に含んでもよい。なお、図6に示すように、到着時刻の項目については、「今すぐ」、「12:30頃(30分毎)」、「○○ICまで」などの選択肢がドロップリストMA−4(またはダイアログ)で選択できるよう入力画面に表示される。また、優先度レーダーチャートMA−3の項目は、図の「一覧」を押下する等により表示される項目一覧の中から選択することが可能である。ここで、図7は、経路探索条件設定部102bにより表示される経由地(POI)の検索条件(エリア選択条件)の入力画面の一例を示す図である。
【0098】
図7に示すように、この例では、端末装置100は、POI検索を行うためのエリア選択画面MB−1を表示し、利用者にPOIを検索するエリア(各都道府県または周辺)を、入力部116を介して選択するよう制御する。なお、この例では、利用者が都道府県名の最初の50音の行(あ行〜わ行)を選択すると、端末装置100は、選択された行に対応する都道府県名を表示するユーザーインターフェースを実現している。ここで、図8は、経路探索条件設定部102bにより表示される経由地(POI)の検索条件(周辺検索条件)の入力画面の一例を示す図である。
【0099】
図8に示すように、端末装置100は、現在位置周辺検索ボタンMB−21とルート途中検索ボタンMB−22を含む周辺検索選択画面MB−2を、出力部114に表示させてもよい。そして、利用者がルート途中検索ボタンMB−22をクリック等により押下すると、経路探索条件設定部102bは、探索される経路周辺でPOIを検索する条件を設定し、一方、利用者が現在位置周辺検索ボタンMB−21をクリック等により押下すると、経路探索条件設定部102bは、現在位置周辺でPOIを検索する条件を設定する。なお、検索するPOIのカテゴリ等を更に利用者に選択させるため、端末装置100は、図6で上述したような経由地の検索条件の入力画面を表示させてもよい。
【0100】
再び図5に戻り、以上のように経路探索条件が取得されると(ステップSB−1)、サーバ装置200の経路探索部202cは、ネットワークデータベース206aに記憶されたネットワークデータに基づいて、経路探索条件受信部202aにより受信された経路探索条件の出発地から目的地までの経路探索を開始する(ステップSB−2)。すなわち、経路探索部202cは、出発地を基点として目的地に到達するまで探索経路を拡散させる。なお、経路探索部202cは、後述する双方向拡散処理における目的地側からの拡散処理(ステップSB−43)に用いるため、探索経路にかかる予想到達時刻を算出してもよい。
【0101】
そして、サーバ装置200の経由地候補検索部202bは、POIデータベース206cからPOIを経由地候補として検索を開始する(ステップSB−3)。例えば、経由地候補検索部202bは、ステップSA−4で上述したように経路探索条件の出発地や現在位置(所定時間後の予想現在位置でもよい。)や目的地等の、所定の形状範囲内に存在するPOIを、POIデータベース206cから検索してもよい。なお、このように、双方向拡散処理(ステップSB−4)を行う前に、経由地候補を検索することに限られず、当該双方向拡散処理(ステップSB−4)と同時に、当該経由地候補の検索処理(ステップSB−3)を行ってもよい。
【0102】
すなわち、経由地候補検索部202bは、後述する双方向拡散による経路探索の処理(ステップSB−4)と同時に、拡散される探索経路に応じて、POIデータベース206cに記憶されたPOIの地点情報に基づいて、当該拡散中の探索経路上または探索経路付近に存在するPOIを経由地候補として取得してもよい。より具体的には、経由地候補検索部202bは、ネットワークデータに基づいて経路探索部202cの処理により拡散されるリンクごとに、リンクに隣接するPOIをPOIデータベース206cから検索し、経由地候補に追加する。なお、図4を用いて上述したように階層化されたネットワークデータを用いる場合で経路探索部202cが比較的上位階層のリンクを用いて拡散を行っている場合であっても、経由地候補検索部202bは、上位階層リンクに隣接するPOIのみではなく、当該上位階層リンク周辺の下位階層リンクに隣接するPOIをも検索してもよい。すなわち、経由地候補検索部202bは、POIと直接接続されていなくとも、上位階層のネットワークデータと関連付けがなされているPOIであれば、経由地候補に含めてもよい。また、POI検索の際、経由地候補検索部202bは、経路探索条件に含まれるPOIの検索条件(利用者に指定されたカテゴリ等)に基づいて、取得したPOIを絞込んでもよい。
【0103】
そして、サーバ装置200の経路探索部202cは、双方向拡散による経路探索を実行する(ステップSB−4)。ここで、双方向拡散による経路探索処理の詳細について以下に図9を参照して説明する。図9は、双方向拡散による経路探索処理の一例を示すフローチャートである。
【0104】
図9に示すように、まず、経路探索部202cは、ダイクストラ法やA*アルゴリズム等の公知の経路探索手法を用いて、出発地から目的地方向に順方向に、探索経路を拡散させて、順次リンクコストを積算等して確定させる(ステップSB−41)。
【0105】
そして、経路探索部202cは、例えば新たなノードに到達する毎に、全ての複数の経由地候補までリンクコストを確定させたか否かを判定する(ステップSB−42)。なお、出発地側の拡散の終了条件は、これに限られず、拡散リンクが目的地に到達したことであってもよく、また、算出されるリンクコストに従って、反対側の地点(例えば、出発地側からの拡散の場合は目的地、目的地側からの拡散の場合は出発地)に到達してから拡散により、所定分多くのリンクコスト(時間、距離、料金等)が算出されたときであってもよい。
【0106】
全ての経由地候補までリンクコストが確定されていない場合(ステップSB−42,No)、経路探索部202cは、探索経路の拡散とそれに伴うリンクコストの確定処理(ステップSB−41)を継続する。
【0107】
一方、全ての経由地候補までリンクコストが確定されると(ステップSB−42,Yes)、経路探索部202cは、今度は目的地から出発地方向に順方向に(先ほどとは逆方向に)、探索経路を拡散させて、順次リンクコストを積算等して確定させる(ステップSB−43)。ここで、目的地側からの拡散を行う場合、出発地側からの拡散とは異なり、参照すべき渋滞情報の時刻が未知であるため予想到達時刻を算出できないという問題が生じる。そのため、経路探索部202cは、ステップSB−2において算出した予想到達時刻を用いて、対応する時刻の渋滞情報を渋滞情報データベース206dから取得することによって予想到達時刻を算出してもよい。すなわち、経路探索部202cは、ステップSB−2において別途計算された出発地から目的地までの仮の予測到着時刻から、ステップSB−4における出発地から経由地候補を介した目的地までの経路を構成する対象ノードについての「目的地から拡散対象リンクまでの所要時間」を引くことで、拡散対象リンクの予測通過時刻を決定してもよい。目的地への仮の予測到着時刻の算出方法は、これに限られず、経路探索部202cは、出発地から目的地への直線距離を平均走行時速で割ることにより、出発地から目的地までの所要時間を計算し、そこから仮の予測到着時刻を算出してもよい。なお、経路探索部202cは、経由地候補での滞在時間を考慮して仮の予測到着時刻を算出するようにしてもよい。例えば、経由地候補がすべて飲食店の時は仮の予測到着時刻に1時間を加算してもよい。
【0108】
そして、同様に、経路探索部202cは、全ての複数の経由地候補までリンクコストを確定させたか否かを判定する(ステップSB−44)。なお、目的地側の拡散の終了条件は、これに限られず、拡散リンクが目的地に到達したときであってもよく、また、算出されるリンクコストに従って、目的地に到達してから拡散により、所定分多くのリンクコスト(時間、距離、料金等)が算出されたときであってもよい。
【0109】
全ての経由地候補までリンクコストが確定されていなければ(ステップSB−44,No)、探索経路の拡散とそれに伴うリンクコストの確定処理(ステップSB−43)を継続する。
【0110】
そして、双方向とも全ての経由地候補までリンクコストが確定されると(ステップSB−44,Yes)、経路探索部202cは、ステップSB−41で求めた出発地から経由地候補までの経路の所要時間と、ステップSB−43で求めた目的地から当該経由地候補までの経路の所要時間とを加算する等により、各経由地候補を経由した場合の所要時間を算出する(ステップSB−45)。
【0111】
再び図5に戻り、サーバ装置200の探索結果情報生成部202dは、ステップSB−45で算出された各経由地候補を経由した場合の所要時間から、ステップSB−2において算出された出発地から(経由地を経由せず)目的地までの経路の所要時間を、減算することにより、各経由地候補を経由した場合のロスタイムを算出する(ステップSB−5)。
【0112】
そして、サーバ装置200の探索結果情報生成部202dは、POIの検索条件(利用者の嗜好等)とのマッチ度順に、複数の経由地候補をソートする(ステップSB−6)。例えば、探索結果情報生成部202dは、マッチ度に降順に(マッチ度が高い順に)経由地候補を並び替えてもよい。ここで、探索結果情報生成部202dは、マッチ度等に基づいてソートすることに限らず、経由地候補が所定以上の場合に出力する数を限定するフィルタリング処理を行ってもよい。例えば、探索結果情報生成部202dは、マッチ度が上位のものから順に所定数の経由地候補を選択し、残りを探索結果情報の生成対象から除外してもよい。なお、探索結果情報生成部202dは、POI情報に基づいて広告を出稿している店舗のPOIを並び替え上位に配置してもよい。また、探索結果情報生成部202dは、同乗者のピックアップを支援する等の利用者の希望(検索条件)に合わせて、駅等の特定のカテゴリの順位を高めてもよい。なお、探索結果情報生成部202dは、渋滞情報や空席や在庫や価格等のリアルタイム情報と連携させてもよい。
【0113】
そして、サーバ装置200の探索結果情報生成部202dは、各経由地候補をPOIの地点情報に基づいて、地図データベース206bの地図データ上に、重畳表示させた表示画面を含む探索結果情報を生成する(ステップSB−7)。ここで、図10は、探索結果情報生成部202dにより生成される表示画面の一例を示す図である。
【0114】
図10に示すように、経路探索条件に現在位置情報が含まれる場合、探索結果情報生成部202dは、当該現在位置情報の現在位置を示す現在地マーク(図中の三角印)を重畳させた地図表示領域MC−1を含む表示画面を生成してもよい。その際、探索結果情報生成部202dは、経由地候補の中から現在位置に近い経由地候補を抽出して、当該経由地候補のPOI情報(この例では、ジャンル:「ラーメン」、名称:「KT麺」、評価:4つ星)や当該経由地候補を経由した場合の目的地到着時刻「12:30着」やロスタイム「+3分」を示すポップアップ表示領域MC−2を表示画面に含めてもよい。なお、この例では、端末装置100が、更新される現在位置情報を含む経路探索条件を定期的に送信しており、現在位置情報の更新に応じてバックグラウンドでステップSB−1〜SB−7の処理が繰り返し行われ、表示画面が遷移する(現時位置が一つの経由地候補に近づいたらポップアップ表示する)ことを前提としてもよい。また、ポップアップ表示させるタイミングは、現在位置情報の履歴等に基づいて、所定時間走行した後の予想位置等に基づいて判定してもよい。これにより、利用者にポップアップ表示された経由地候補に立ち寄るか否かを判断する時間を与えることができ、利用者は余裕をもって現在走行中の経路を外れることが可能となる。なお、お勧めのPOIに到達するための経路から外れた場合、端末装置100は、表示したポップアップを非表示にしてもよい。複数の経由地候補を表示させる場合、探索結果情報生成部202dは、ソートした先頭から強調表示されるように制御してもよく、例えば、経由地候補を示す星印の大きさをソート順に変更してもよい。ここで、図11は、探索結果情報生成部202dにより生成される複数の経由地候補を重畳させた表示画面の一例を示す図である。図11において、Sは出発地を示し、Gは目的地を示し、地図上の各黒丸印は経由地候補を示す。なお、POIの検索条件(利用者の嗜好等)とのマッチ度が黒丸印の大きさで表現されている。また、図中の実線は、ステップSB−2で経路探索された出発地から目的地までの経路を示し、破線は、ステップSB−4で経路探索された、出発地から経由地候補を経由した目的地までの経路を示している。なお、吹き出し内の星印の数は、口コミ等に基づいた評判の高さを示している。
【0115】
図11に示すように、ステップSB−7でソートした結果、上位のものは、大きな黒丸印で表し、かつ、吹き出しで、店名や評判や到着時刻(ロスタイム)を表示させてもよい。なお、ソート結果が下位のものは、小さな黒丸印で表される。そして、この表示画面を含む探索結果情報が端末装置100の出力部114に表示され、利用者がタッチパネル等の入力部116を介してタッチ操作等により、一つの経由地を選択すると(この例では、店名「KT麺」のPOIが選択されている。)、その吹き出しが最上位の階層で重畳されるとともに、探索結果情報に格納された当該経由地を経由した経路が表示されるように、探索結果情報生成部202dは、探索結果情報を生成してもよい。また、吹き出し内の「立ち寄る」ボタンをダブルタッチ等のタッチ操作により押下することにより、経路探索条件設定部102bは、選択された経由地候補を経由地とした経路探索条件を再設定してもよい。
【0116】
そして、サーバ装置200の経路探索部202cは、経由地候補を経由地として、再度、経路探索を実行する(ステップSB−8)。なお、経由地とする経由地候補は、上記のように端末装置100から再送された経由地を含む経路探索条件に基づいて設定してもよく、また、複数の経由地候補の全てについて、それぞれを経由地として再探索を行ってもよい。すなわち、上述した双方向拡散による経路探索(ステップSB−4)では、目的地から経由地候補に向けて逆方向に経路探索を行っていたので、渋滞を加味していないか加味するとしても別途算出した予想到達時刻を参照するなど精度に劣る場合があるが、経路探索部202cは、出発地から選択された経由地までの探索経路、および、当該選択された経由地から目的地までの探索経路をそれぞれ拡散させることによって、出発地から目的地まで順方向に探索経路を拡散させて、渋滞情報データベース206dに記憶された渋滞情報等を考慮した精度の高い経路や所要時間等を算出してもよい。当該ステップSB−8の処理は、正確な経路や所要時間等を算出するための処理であるので、処理を高速化するために省略してもよい。また、このように当該ステップSB−8もしくはステップSB−4で算出された予想到達時刻や所要時間等は、出力部114を介して利用者に通知されることとなる。また、上述のステップSB−7およびステップSB−8による表示画面や経路探索結果を含む探索結果情報は、端末装置100に送信され出力されるが、上述のステップSA−7〜SA−9の処理と同様であるので説明を省略した。また、上述したステップSB−1〜ステップSB−8の処理を、定期的に、または、検索条件や現在位置等の更新に応じて、繰り返し実行させてもよい。特に、図6に示した入力画面を介して利用者により再度、検索条件が入力された場合(例えば、利用者のカテゴリ等に対する優先度が変更された場合)、サーバ装置200は、ステップSB−6〜ステップSB−8の処理のみを繰り返し実行してもよい。
【0117】
以上が、第1の実施形態における経路探索システムの具体化処理の一例である。これにより、目的地の宿までの間で立ち寄る観光地を探したり、高速ICまでの間でロスタイムなく入れる飲食店を探したり、利用履歴やジャンル指定や広告出稿に応じて、おすすめ立ち寄り地点を自動ポップ表示させる等のさまざまな需要に応えることができる。
【0118】
[第2の実施形態]
続いて、本発明の第2の実施形態(経路探索装置400(スタンドアローン型))について、図12および図13を参照して以下に説明する。ここで、図12は、第2の実施形態における経路探索装置400の構成の一例を示すブロック図であり、該構成のうち本発明に関係する部分のみを概念的に示している。
【0119】
なお、第2の実施形態においては、全ての機能を経路探索装置400に集約し、交通網を規定するネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索し、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する。このように、第2の実施形態は、経路探索装置400がスタンドアローン型に構成され単独で処理を行う点が第1の実施形態と異なる。
【0120】
[経路探索装置400(スタンドアローン型)の構成]
まず、第2の実施形態における経路探索装置400(スタンドアローン型)の構成の一例について、図12を参照して以下に説明する。
【0121】
図12に示すように、本発明の第2の実施形態の経路探索装置400は、位置取得部412と出力部414と入力部416と制御部402と記憶部406とを少なくとも備える。これら経路探索装置400の各部は任意の通信路を介して通信可能に接続されている。例えば、経路探索装置400は、一般に市販されるデスクトップ型またはノート型のパーソナルコンピュータ等の情報処理装置、携帯電話やPHSやPDA等の携帯端末装置、および、走行経路案内等を行なうPND(Portable Navigation Device)等のナビゲーション端末等である。
【0122】
図12において、入出力制御インターフェース部408、通信制御インターフェース部404、位置取得部412、出力部414、および、入力部416、並びに、ネットワーク300、位置発信装置500、および、外部機器600の各機能は、第1の実施形態と同様であるため説明を省略する。また、記憶部406の各部(ネットワークデータベース406a、地図データベース406b、POIデータベース406c、および、渋滞情報データベース406d等)についても、サーバ装置200ではなく経路探索装置400に備えられている点を除き、各機能が第1の実施形態と同様であるため説明を省略する。なお、記憶部406は、更に、第1の実施形態における案内データファイル106aに記憶された案内データを記憶してもよい。
【0123】
また、制御部402の各部(経路探索条件設定部402a〜現在位置情報取得部402g等)について、本実施形態の経路探索装置400がスタンドアローン型であり、制御部402が各送受信部を備えていない点を除き、各機能は第1の実施形態の経路探索システムと基本的に同様である。
【0124】
図12において、制御部402は、OS等の制御プログラムや、各種の処理手順等を規定したプログラム、および、所要データを格納するための内部メモリを有する。そして、制御部402は、これらのプログラム等により、種々の処理を実行するための情報処理を行う。制御部402は、機能概念的に、経路探索条件設定部402a、経由地候補検索部402b、経路探索部402c、探索結果情報生成部402d、探索結果情報出力部402e、渋滞情報取得部402f、および、現在位置情報取得部402gを備える。これらの機能は、第1の実施形態における、経路探索条件設定部102b、経由地候補検索部202b、経路探索部202c、探索結果情報生成部202d、探索結果情報出力部102e、渋滞情報取得部202f、および、現在位置情報取得部102aの機能と同様であるため説明を省略する。
【0125】
以上で、第2の実施形態における経路探索装置400の構成の一例の説明を終える。
【0126】
[経路探索装置400(スタンドアローン型)の処理]
次に、このように構成された第2の実施形態における経路探索装置400の処理の一例について、以下に図13を参照して詳細に説明する。ここで、図13は、第2の実施形態における経路探索装置400の処理の一例を示すフローチャートである。
【0127】
図13に示すように、まず、経路探索条件設定部402aは、利用者に入力部416を介して、少なくとも出発地と目的地を含む経路探索条件を設定させる(ステップSC−1)。ここで、出発地は、現在位置情報取得部402gにより取得される現在位置情報に基づく経路探索装置400の利用者の現在位置であってもよく、経路探索条件に、出発地とは別に当該現在位置の条件を加えてもよい。なお、経路探索条件設定部402aは、経路探索条件として、経由地の嗜好(例えば、経由地候補として検索されるPOIのカテゴリ等)を、利用者に指定させてもよい。
【0128】
そして、経由地候補検索部402bは、POIデータベース406cに記憶された地点情報(POI情報等)から、複数の経由地候補を検索する(ステップSC−2)。ここで、経由地候補検索部402bは、経路探索条件設定部402aにより設定された経路探索条件の出発地や現在位置(所定時間後の予想現在位置でもよい。)や目的地等を含む、所定の形状範囲内に存在するPOIを、POIデータベース406cから検索してもよい。所定の形状範囲の一例として、経由地候補検索部402bは、出発地および目的地の2点を焦点とする楕円の範囲内に位置するPOIを経由地候補として検索してもよい。また、経由地候補検索部402bは、経路探索条件としてPOIのカテゴリ等が指定されている場合に、当該指定されたカテゴリ等に該当するPOIに絞込み検索を行ってもよい。また、経由地候補検索部402bは、経路探索部402cにより以下に実行される双方向拡散より前に、経路探索部402cにより出発地から目的地まで探索経路を拡散させると同時に、拡散される当該出発地から当該目的地までの探索経路に基づいて、POIデータベース406cから複数のPOIを、複数の経由地候補として検索してもよい。すなわち、経路探索部402cにより出発地から目的地までの探索経路が拡散される際に、経由地候補検索部402bは、POIデータベース406cに記憶されたPOIの地点情報に基づいて、当該拡散中の探索経路上または探索経路付近に存在するPOIを経由地候補として取得してもよい。
【0129】
そして、経路探索部402cは、ネットワークデータベース406aに記憶されたネットワークデータに基づいて、経由地候補検索部402bにより検索された複数の経由地候補について双方向拡散による経路探索を実行する(ステップSC−3)。具体的には、経路探索部402cは、経路探索条件設定部402aにより設定された経路探索条件の出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて、双方向拡散による経路探索を行う。このほか、双方向拡散による経路探索の詳細は、第1の実施の形態と同様である。例えば、経路探索部402cは、処理時間を短縮するために、ネットワークデータベース406aに記憶された、階層化されたネットワークデータを用いて経路探索を行ってもよい。なお、ステップSC−3で上述したように、双方向拡散による経路探索以外にも、経路探索部402cは、出発地から目的地まで探索経路を拡散させる、通常の経路探索を行ってもよい。
【0130】
そして、探索結果情報生成部402dは、経路探索部402cにより探索された、出発地から経由地候補を介した目的地までの経路を含む探索結果情報を生成する(ステップSC−4)。例えば、探索結果情報生成部402dは、双方向拡散により探索された、出発地から経由地候補までの経路と、目的地から当該経由地候補までの経路とを繋ぎ合わせることによって、出発地から当該経由地候補を介した目的地までの経路を生成し、当該経路を示す探索結果情報を生成してもよい。また、探索結果情報生成部402dは、地図データベース406bに記憶された地図データに経由地候補を重畳させた表示画面を含む探索結果情報を生成してもよい。その際、探索結果情報生成部402dは、出発地や、目的地、出発地から目的地までの経路、出発地から経由地候補を介した目的地までの経路等を地図データ上に重畳させた探索結果情報を生成してもよい。また、探索結果情報生成部402dは、経路探索部402cにより探索された、出発地から目的地までの経路と、出発地から経由地候補を介した目的地までの経路と、を比較した比較結果を含む探索結果情報を生成してもよい。例えば、探索結果情報生成部402dは、両経路の時間や距離や料金等の比較結果(差,比,割合等)を示す探索結果情報を生成してもよい。なお、探索結果情報生成部402dは、これら比較結果を降順や昇順にソート等して、決定した表示順序で一覧表示されるように(例えば、ロスタイムが短い順にPOIが表示されるように)探索結果情報を生成してもよい。なお、探索結果情報生成部402dは、出発地から目的地までの(経由地候補を経由しない)経路との比較結果に基づいて表示順序を決定することに限らず、出発地から目的地までの経路探索を行うことなく、出発地から各経由地候補を介した目的地までの経路を、経由地候補同士で所要時間や距離や料金等に基づいて、表示順序を決定してもよい。
【0131】
そして、探索結果情報出力部402eは、探索結果情報生成部402dにより生成された探索結果情報を、出力部414に出力する(ステップSC−5)。ここで、探索結果情報出力部402eは、探索結果情報に応じた地図データや経路上に、現在位置情報取得部402gにより更新される現在位置情報を重畳して、出力部414に表示させてもよい。また、探索結果情報出力部402eは、現在位置情報取得部402gにより更新される現在位置情報の現在位置が、探索結果情報に含まれる経由地候補の所定範囲内または経由地候補を介する経路への分岐点に近づいた場合に、当該経由地候補があることを音声や表示等により出力してもよい。ここで、利用者により入力部416を介して複数の経由地候補の中から一の経由地が選択された場合、探索結果情報出力部402eは、探索結果情報に基づいて、選択された経由地を経由する経路に従って経路案内を実行してもよい。なお、経路探索部402cは、経路探索の精度を上げるため、選択された経由地について再度、経路探索を行ってもよい。
【0132】
以上が、第2の実施形態における経路探索装置400による処理の一例である。なお、本実施の形態において、上述したステップSC−1〜ステップSC−5の処理が繰り返されるよう制御してもよい。例えば、現在位置情報取得部402gにより現在位置情報が更新される毎に、経路探索条件設定部402aにより再設定された現在位置情報を含む経路探索条件を設定することにより、上述したステップSC−1〜ステップSC−5の処理が繰り返されるよう制御してもよい。これにより、現在位置情報の更新に応じて、探索結果情報出力部402eにより出力される探索結果情報がリアルタイムに更新されることになる。このほか、経由地候補(POI)の検索条件(利用者により指定されたカテゴリ)が経路探索条件に追加された場合等に上述の処理を繰り返して、経由地候補の絞込みを行ってもよい。また、渋滞情報取得部402fが新たな渋滞情報を取得した場合や一定期間毎に、ステップSC−2〜ステップSC−5の処理を繰り返すよう処理を行ってもよい。
【0133】
以上で、第2の実施形態における経路探索装置400の処理の説明を終える。
【0134】
[他の実施の形態]
さて、これまで本発明の実施の形態について説明したが、本発明は、上述した実施の形態以外にも、特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施の形態にて実施されてよいものである。
【0135】
例えば、経路探索装置400がスタンドアローンの形態で処理を行う場合を一例に説明したが、経路探索装置400は、クライアント端末からの要求に応じて処理を行い、その処理結果を当該クライアント端末に返却するようにしてもよい。
【0136】
また、実施の形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。
【0137】
このほか、上記文献中や図面中で示した処理手順、制御手順、具体的名称、各処理の登録データや検索条件等のパラメータを含む情報、画面例、データベース構成については、特記する場合を除いて任意に変更することができる。
【0138】
また、端末装置100、サーバ装置200、および、経路探索装置400に関して、図示の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。
【0139】
例えば、端末装置100、サーバ装置200、および、経路探索装置400の各装置が備える処理機能、特に制御部102,202,402にて行われる各処理機能については、その全部または任意の一部を、CPU(Central Processing Unit)および当該CPUにて解釈実行されるプログラムにて実現してもよく、また、ワイヤードロジックによるハードウェアとして実現してもよい。尚、プログラムは、後述する記録媒体に記録されており、必要に応じて端末装置100、サーバ装置200、および、経路探索装置400に機械的に読み取られる。すなわち、ROMまたはHDDなどの記憶部106,206,406などには、OS(Operating System)として協働してCPUに命令を与え、各種処理を行うためのコンピュータプログラムが記録されている。このコンピュータプログラムは、RAMにロードされることによって実行され、CPUと協働して制御部を構成する。
【0140】
また、このコンピュータプログラムは、端末装置100、サーバ装置200、および、経路探索装置400に対して任意のネットワーク300を介して接続されたアプリケーションプログラムサーバに記憶されていてもよく、必要に応じてその全部または一部をダウンロードすることも可能である。
【0141】
また、本発明に係るプログラムを、コンピュータ読み取り可能な記録媒体に格納してもよく、また、プログラム製品として構成することもできる。ここで、この「記録媒体」とは、メモリーカード、USBメモリ、SDカード、フレキシブルディスク、光磁気ディスク、ROM、EPROM、EEPROM、CD−ROM、MO、DVD、および、Blu−ray Disc等の任意の「可搬用の物理媒体」を含むものとする。
【0142】
また、「プログラム」とは、任意の言語や記述方法にて記述されたデータ処理方法であり、ソースコードやバイナリコード等の形式を問わない。なお、「プログラム」は必ずしも単一的に構成されるものに限られず、複数のモジュールやライブラリとして分散構成されるものや、OS(Operating System)に代表される別個のプログラムと協働してその機能を達成するものをも含む。なお、実施の形態に示した各装置において記録媒体を読み取るための具体的な構成、読み取り手順、あるいは、読み取り後のインストール手順等については、周知の構成や手順を用いることができる。
【0143】
記憶部106,206,406に格納される各種のデータベース等(案内データファイル106a、および、ネットワークデータベース206a,406a〜渋滞情報データベース206d,406d)は、RAM、ROM等のメモリ装置、ハードディスク等の固定ディスク装置、フレキシブルディスク、および、光ディスク等のストレージ手段であり、各種処理やウェブサイト提供に用いる各種のプログラム、テーブル、データベース、および、ウェブページ用ファイル等を格納する。
【0144】
また、サーバ装置200は、既知のパーソナルコンピュータ、ワークステーション等の情報処理装置として構成してもよく、また、該情報処理装置に任意の周辺装置を接続して構成してもよい。また、サーバ装置200は、該情報処理装置に本発明の方法を実現させるソフトウェア(プログラム、データ等を含む)を実装することにより実現してもよい。
【0145】
更に、装置の分散・統合の具体的形態は図示するものに限られず、その全部または一部を、各種の付加等に応じて、または、機能負荷に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。すなわち、上述した実施形態を任意に組み合わせて実施してもよく、実施形態を選択的に実施してもよい。
【産業上の利用可能性】
【0146】
以上詳述に説明したように、本発明によれば、適切な経由地を効率よく探索することができる、経路探索装置、経路探索システム、サーバ装置、端末装置、経路探索方法、および、プログラム、並びに、記録媒体を提供することができる。
【符号の説明】
【0147】
100 端末装置
102 制御部
102a 現在位置情報取得部
102b 経路探索条件設定部
102c 経路探索条件送信部
102d 探索結果情報受信部
102e 探索結果情報出力部
104 通信制御インターフェース部
106 記憶部
106a 案内データファイル
108 入出力制御インターフェース部
112 位置取得部
114 出力部
116 入力部
200 サーバ装置
202 制御部
202a 経路探索条件受信部
202b 経由地候補検索部
202c 経路探索部
202d 探索結果情報生成部
202e 探索結果情報送信部
202f 渋滞情報取得部
204 通信制御インターフェース部
206 記憶部
206a ネットワークデータベース
206b 地図データベース
206c POIデータベース
206d 渋滞情報データベース
300 ネットワーク
400 経路探索装置
402 制御部
402a 経路探索条件設定部
402b 経由地候補検索部
402c 経路探索部
402d 探索結果情報生成部
402e 探索結果情報出力部
402f 渋滞情報取得部
402g 現在位置情報取得部
404 通信制御インターフェース部
406 記憶部
406a ネットワークデータベース
406b 地図データベース
406c POIデータベース
406d 渋滞情報データベース
408 入出力制御インターフェース部
412 位置取得部
414 出力部
416 入力部
500 位置発信装置
600 外部機器

【特許請求の範囲】
【請求項1】
記憶部と制御部とを少なくとも備えた経路探索装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、を備えたことを特徴とする、経路探索装置。
【請求項2】
請求項1に記載の経路探索装置において、上記記憶部は、地点に関する地点情報を記憶する地点情報記憶手段、を更に備え、上記制御部は、上記地点情報記憶手段の上記地点情報から、上記複数の経由地候補を検索する経由地候補探索手段、を更に備え、上記経路探索手段は、上記ネットワークデータに基づいて、上記経由地候補検索手段により検索された上記複数の経由地候補について、上記経路探索条件の上記出発地から当該複数の経由地候補までの上記探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの上記探索経路を、それぞれ1回ずつ拡散させることを特徴とする、経路探索装置。
【請求項3】
請求項2に記載の経路探索装置において、上記経由地候補検索手段は、上記経路探索手段により上記出発地からの上記探索経路および上記目的地からの上記探索経路が拡散される際に、当該拡散される上記探索経路付近の上記経由地候補を上記地点情報記憶手段から検索することを特徴とする、経路探索装置。
【請求項4】
請求項1乃至3のいずれか一つに記載の経路探索装置において、上記ネットワークデータ記憶手段は、上記交通網のうち、詳細な上記交通網を規定する下位階層の上記ネットワークデータと、主要な上記交通網を規定する上位階層の上記ネットワークデータと、を含む階層化された上記ネットワークデータを記憶し、上記経路探索手段は、上記出発地から上記複数の経由地候補までの上記探索経路および上記目的地から当該複数の経由地候補までの上記探索経路を拡散させる前に、上記複数の経由地候補から、上記下位階層の上記ネットワークデータに基づいて上記探索経路を拡散させることを特徴とする、経路探索装置。
【請求項5】
請求項1乃至4のいずれか一つに記載の経路探索装置において、上記経路探索手段は、上記経路探索条件の上記出発地から上記目的地までの上記探索経路を拡散させて経路を更に探索し、上記探索結果情報生成手段は、上記経路探索手段により探索された、上記出発地から上記目的地までの上記経路と、上記出発地から上記経由地候補を介した上記目的地までの上記経路と、を比較した比較結果を含む上記探索結果情報を生成することを特徴とする、経路探索装置。
【請求項6】
請求項1乃至5のいずれか一つに記載の経路探索装置において、上記制御部は、移動体の現在位置を示す現在位置情報を取得する現在位置情報取得手段、を更に備え、上記経路探索手段は、上記現在位置情報取得手段により取得された上記現在位置情報の上記現在位置を、上記経路探索条件の上記出発地として経路探索を行うことを特徴とする、経路探索装置。
【請求項7】
請求項1乃至6のいずれか一つに記載の経路探索装置において、上記制御部は、時刻ごと地点ごとに予想される渋滞発生を示す渋滞情報を取得する渋滞情報取得手段、を更に備え、上記経路探索手段は、探索した上記出発地から上記経由地候補までの上記経路および上記目的地から当該経由地候補までの上記経路に基づいて当該目的地への予想到達時刻を算出し、上記渋滞情報に基づいて上記予想到達時刻を修正することを特徴とする、経路探索装置。
【請求項8】
請求項1乃至7のいずれか一つに記載の経路探索装置において、出力部を更に備え、上記制御部は、上記出発地および上記目的地を少なくとも含む上記経路探索条件を設定する経路探索条件設定手段と、上記探索結果情報生成手段により生成された上記探索結果情報を上記出力部に出力する探索結果出力手段と、を更に備えたことを特徴とする、経路探索装置。
【請求項9】
記憶部と制御部とを少なくとも備えたサーバ装置、および、出力部と制御部とを少なくとも備えた端末装置、を通信可能に接続した経路探索システムにおいて、上記サーバ装置の上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記サーバ装置の上記制御部は、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信手段と、上記ネットワークデータに基づいて、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、上記探索結果情報生成手段により生成された上記探索結果情報を、上記端末装置に送信する探索結果情報送信手段と、を備え、上記端末装置の上記制御部は、上記経路探索条件を上記サーバ装置に送信する経路探索条件送信手段と、上記サーバ装置から送信される、上記探索結果情報を受信する探索結果情報受信手段と、上記探索結果情報受信手段により受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力手段と、を備えたことを特徴とする、経路探索システム。
【請求項10】
交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段と、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、を備えたことを特徴とする、経路探索システム。
【請求項11】
出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信手段と、上記ネットワークデータに基づいて、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索手段と、上記経路探索手段により探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成手段と、上記探索結果情報生成手段により生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信手段と、を備えたことを特徴とする、サーバ装置。
【請求項12】
記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置において、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部は、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信手段と、上記サーバ装置から送信される、上記経路探索条件受信手段により受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信手段と、上記探索結果情報受信手段により受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力手段と、を備えたことを特徴とする、端末装置。
【請求項13】
記憶部と制御部とを少なくとも備えた経路探索装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を含むことを特徴とする、経路探索方法。
【請求項14】
記憶部と制御部とを少なくとも備えたサーバ装置、および、出力部と制御部とを少なくとも備えた端末装置、を通信可能に接続した経路探索システムにおいて実行される経路探索方法であって、上記サーバ装置の上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記端末装置の上記制御部において実行される、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置の上記制御部において実行される、上記端末装置から送信される、上記経路探索条件を受信する経路探索条件受信ステップと、上記サーバ装置の上記制御部において実行される、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記サーバ装置の上記制御部において実行される、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記サーバ装置の上記制御部において実行される、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信する探索結果情報送信ステップと、上記端末装置の上記制御部において実行される、上記サーバ装置から送信される、上記探索結果情報を受信する探索結果情報受信ステップと、上記端末装置の上記制御部において実行される、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を含むことを特徴とする、経路探索方法。
【請求項15】
交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段と、経路探索手段と、探索結果情報生成手段と、を備えた経路探索システムにおいて実行される経路探索方法であって、上記経路探索手段が、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記探索結果情報生成手段が、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を含むことを特徴とする、経路探索方法。
【請求項16】
出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信ステップと、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信ステップと、を含むことを特徴とする、経路探索方法。
【請求項17】
記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置において実行される経路探索方法であって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において実行される、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置から送信される、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信ステップと、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を含むことを特徴とする、経路探索方法。
【請求項18】
記憶部と制御部とを少なくとも備えた経路探索装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、上記ネットワークデータに基づいて、出発地および目的地を少なくとも含む経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、を実行させるためのプログラム。
【請求項19】
出力部を少なくとも備えた端末装置に通信可能に接続された、記憶部と制御部とを少なくとも備えたサーバ装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、上記端末装置から送信される、出発地および目的地を少なくとも含む経路探索条件を受信する経路探索条件受信ステップと、上記ネットワークデータに基づいて、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ拡散させて経路を探索する経路探索ステップと、上記経路探索ステップにて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を生成する探索結果情報生成ステップと、上記探索結果情報生成ステップにて生成された上記探索結果情報を、上記端末装置に送信することにより、上記端末装置の上記出力部に出力させる探索結果情報送信ステップと、を実行させるためのプログラム。
【請求項20】
記憶部を少なくとも備えたサーバ装置に通信可能に接続された、出力部と制御部とを少なくとも備えた端末装置に実行させるためのプログラムであって、上記記憶部は、交通網を規定するネットワークデータを記憶するネットワークデータ記憶手段、を備え、上記制御部において、出発地および目的地を少なくとも含む経路探索条件を上記サーバ装置に送信する経路探索条件送信ステップと、上記サーバ装置から送信される、上記経路探索条件受信ステップにて受信された上記経路探索条件の上記出発地から複数の経由地候補までの探索経路、および、当該経路探索条件の上記目的地から当該複数の経由地候補までの探索経路を、それぞれ1回ずつ上記ネットワークデータに基づいて拡散させて探索された、上記出発地から上記経由地候補を介した上記目的地までの上記経路を含む探索結果情報を、受信する探索結果情報受信ステップと、上記探索結果情報受信ステップにて受信された上記探索結果情報を、上記出力部に出力する探索結果情報出力ステップと、を実行させるためのプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate


【公開番号】特開2012−242296(P2012−242296A)
【公開日】平成24年12月10日(2012.12.10)
【国際特許分類】
【出願番号】特願2011−113937(P2011−113937)
【出願日】平成23年5月20日(2011.5.20)
【出願人】(500168811)株式会社ナビタイムジャパン (410)
【Fターム(参考)】