経路探索装置、経路探索方法、経路探索プログラム及び記憶媒体
【課題】経路探索用データのデータ量を過度に増大させることなく、遠距離の経路計算を高速化する。
【解決手段】経路探索装置は、例えばカーナビゲーション装置などに搭載することができ、出発地から目的地へ至る経路探索のための経路探索用データを記憶している。経路探索用データは、探索用ブロックデータと、探索テーブルとを含む。探索用ブロックデータは、地理上の所定のブロック毎に１つ又は複数用意されており、経路探索に用いるリンクを示すデータである。また、探索テーブルは、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定するデータである。経路探索時には、出発地と目的地とが決定されると、出発地及び目的地の組合せに対応する前記探索用ブロックデータが決定され、決定された前記探索用ブロックデータを用いて経路探索が行われる。
【解決手段】経路探索装置は、例えばカーナビゲーション装置などに搭載することができ、出発地から目的地へ至る経路探索のための経路探索用データを記憶している。経路探索用データは、探索用ブロックデータと、探索テーブルとを含む。探索用ブロックデータは、地理上の所定のブロック毎に１つ又は複数用意されており、経路探索に用いるリンクを示すデータである。また、探索テーブルは、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定するデータである。経路探索時には、出発地と目的地とが決定されると、出発地及び目的地の組合せに対応する前記探索用ブロックデータが決定され、決定された前記探索用ブロックデータを用いて経路探索が行われる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データを利用する経路探索手法に関する。
【背景技術】
【０００２】
カーナビゲーション装置、インターネットを利用した地図提供アプリケーションなどには経路探索機能が設けられている。経路探索機能は地理上の出発地から目的地に至る経路を、地図データを利用して自動計算し、ユーザに提示する機能である。
【０００３】
一般的に、遠距離の経路探索は、候補となる道路数が多くなるため時間を要する。通常、経路探索用データは階層構造となっており、遠距離の経路計算では、主要道路のみを含むデータを使用することにより、計算の高速化を図っている。しかし、主要道路に限っても、全国的には相当数の道路リンクが存在する。よって、複数の県を経由するような遠距離経路の探索においては、主要道路の道路リンク全てを計算の対象とするため、膨大な計算量が要求される。
【０００４】
遠距離の経路探索を高速に行うために、経路探索用データ中に、通常のノード及びリンクのデータ以外に特殊なデータを含める手法が知られている。例えば、出発地のエリアと目的地のエリアの組合せに対して、その間の経路探索に必要なリンクのみを格納したデータを用意し、これを用いて経路探索を行う手法が知られている。
【０００５】
また、特許文献１には以下のような手法が提案されている。まず、地図上の地域を複数の探索区画に分割し、各探索区画に対して、一般的な使用が予想される高速道路や国道などの候補道路、及び、その候補道路への接続点（出入口）を予め決めて記憶しておく。経路探索時には、始点及び終点を含む探索区画に対応する候補道路及びその候補道路への接続点を呼び出し、候補道路のみを用いて経路計算を行う。
【０００６】
【特許文献１】特開平１１−６４０２３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、上記のような手法では、経路探索用データに含まれる特殊データの量が大きくなってしまう。また、道路の変更に応じて経路探索用データの更新が必要となった場合に、更新すべきデータ量も増大する。
【０００８】
本発明が解決しようとする課題としては、上記のものが一例として挙げられる。本発明は、経路探索用データのデータ量を過度に増大させることなく、遠距離の経路計算を高速化することを課題とする。
【課題を解決するための手段】
【０００９】
請求項１に記載の発明は、経路探索装置であって、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶した記憶部と、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段と、を備えることを特徴とする。
【００１０】
請求項４に記載の発明は、経路探索方法であって、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶部に記憶する記憶工程と、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索工程と、を備えることを特徴とする。
【００１１】
請求項５に記載の発明は、記憶部及びコンピュータを備える端末装置において実行される経路探索プログラムであって、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを前記記憶部に記憶する記憶手段、及び、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段、として前記コンピュータを機能させることを特徴とする。
【００１２】
請求項７に記載の発明は、記憶媒体であって、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶したことを特徴とする。
【００１３】
請求項１０に記載の発明は、探索用データ作成装置であって、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段と、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段と、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段と、前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段と、を備えることを特徴とする。
【００１４】
請求項１１に記載の発明は、探索用データ作成方法であって、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成工程と、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割工程と、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合工程と、前記統合工程による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力工程と、を備えることを特徴とする。
【００１５】
請求項１２に記載の発明は、コンピュータを備える端末装置において実行される探索用データ作成プログラムであって、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段、及び、前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段、として前記コンピュータを機能させることを特徴とする。
【発明を実施するための最良の形態】
【００１６】
本発明の１つの実施形態では、経路探索装置は、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶した記憶部と、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段と、を備える。
【００１７】
上記の経路探索装置は、例えばカーナビゲーション装置などに搭載することができ、出発地から目的地へ至る経路探索のための経路探索用データを記憶している。経路探索用データは、探索用ブロックデータと、探索テーブルとを含む。探索用ブロックデータは、地理上の所定のブロック毎に１つ又は複数用意されており、経路探索に用いるリンクを示すデータである。また、探索テーブルは、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定するデータである。経路探索時には、出発地と目的地とが決定されると、出発地及び目的地の組合せに対応する前記探索用ブロックデータが決定され、決定された前記探索用ブロックデータを用いて経路探索が行われる。
【００１８】
上記の経路探索装置の一態様では、１つのブロックに対応して用意された複数の探索用ブロックデータの各々は、当該１つのブロックに対応して用意された他の探索用ブロックデータとの間で共通するリンク数が所定割合以下である。これにより、共通するリンクを重複して含む探索用ブロックデータの数を減らすことができ、経路探索用データのデータ量を低減することができる。
【００１９】
上記の経路探索装置の他の一態様では、前記記憶部は、前記所定のブロック毎に用意され、当該ブロック内に存在する全てのリンクを示すリンクデータを記憶しており、前記経路探索手段は、前記出発地及び前記目的地が属するブロックについては、前記リンクデータを用いて経路探索を行う。これにより、出発地及び目的地の周辺では、多数の道路を考慮して適切な経路探索を行うことができる。
【００２０】
本発明の他の実施形態では、経路探索方法は、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶部に記憶する記憶工程と、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索工程と、を備える。
【００２１】
本発明のさらに他の実施形態では、記憶部及びコンピュータを備える端末装置において実行される経路探索プログラムは、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを前記記憶部に記憶する記憶手段、及び、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段、として前記コンピュータを機能させる。また、上記の経路探索プログラムは記憶媒体に記憶した状態で取り扱うことができる。
【００２２】
本発明のさらに他の実施形態では、記憶媒体は、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶する。
【００２３】
上記の記憶媒体の好適な例では、記経路探索用データは、複数のレイヤからなる階層構造を有しており、前記探索用ブロックデータ及び前記探索テーブルは、前記複数のレイヤのうち少なくとも最上位のレイヤの前記経路探索用データに含まれている。また、他の好適な例では、前記経路探索用データは、複数のレイヤからなる階層構造を有しており、前記複数のレイヤの前記経路探索用データは、所定範囲内に存在する前記出発地と目的地の組合せについてのみ、前記探索用ブロックデータ及び前記探索テーブルを含んでいる。
【００２４】
本発明のさらに他の実施形態では、探索用データ作成装置は、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段と、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段と、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段と、前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段と、を備える。
【００２５】
上記の探索用データ作成装置では、まず、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データが作成される。次に、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータが作成される。次に、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータが１つに統合され、統合処理後の前記探索用ブロックデータが探索用データとして出力される。
【００２６】
本発明のさらに他の実施形態では、探索用データ作成方法は、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成工程と、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割工程と、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合工程と、前記統合工程による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力工程と、を備える。
【００２７】
本発明のさらに他の実施形態では、コンピュータを備える端末装置において実行される探索用データ作成プログラムは、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段、及び、前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段、として前記コンピュータを機能させる。
【実施例】
【００２８】
以下、図面を参照して本発明の好適な実施例について説明する。
【００２９】
［地図データ］
図１に、本実施例において使用する地図データの構成を模式的に示す。地図データは、異なる複数の縮尺に対応する複数のレイヤを含む階層構造に構成されている。図１は説明の便宜上、３階層の地図データを例示しているが、地図データはより多数の階層構造としてもよい。各レイヤにおいて、地図データの１つの単位を「ブロック（Ｂ）」と呼ぶ。なお、「ブロック」は地理上の広がりを持った範囲を示す概念であり、「パーセル」、「メッシュ」などと表現することもできる。図１において、レイヤ３は最上位レイヤであり、最も広域の地図に対応する。レイヤ１は最下位レイヤであり、最も詳細な地図に対応する。
【００３０】
地図データ１２０は、各レイヤ毎に別個に用意されており、それぞれ地図表示用データ１２２と、経路探索用データ１２４とを含む。地図表示用データ１２２は、ユーザに対して地図画像を表示するために使用されるデータであり、主として地図に対応する画像データを含む。経路探索用データ１２４は、経路探索機能による経路探索に使用されるデータである。
【００３１】
図２に、最上位レイヤ３の経路探索用データの構成を示す。経路探索用データ１２４は、ノードデータ１２５、リンクデータ１２６、探索テーブル１２７及び探索用ブロックデータ１２８を含む。ノードは道路上の交差点などの所定の地点に対応し、ノードデータ１２５はノードを示すデータである。一方、リンクは交差点などにより区切られた道路の１区画に対応し、リンクデータ１２６はリンクを示すデータである。なお、本実施例では、最上位レイヤ以外のレイヤでは、経路探索用データは、ノードデータ１２５及びリンクデータ１２６を含むが、探索テーブル１２７及び探索用ブロックデータ１２８は含まないものとする。
【００３２】
但し、本発明の適用がこれに限られるものではなく、全てのレイヤにおいて経路探索用データが探索テーブル１２７及び探索用ブロックデータ１２８を含むように構成しても構わない。例えばレイヤ３は全国の組合せを持ち、レイヤ２は２００ｋｍ以内にあるブロックに対してのみそれらのデータを持つものとしてもよい。この場合、出発地と目的地のうち「東京と山梨」、「東京と栃木」などに関してはレイヤ３のみならずレイヤ２でも探索テーブル１２７及び探索用ブロックデータ１２８を持つが、「東京と北海道」、「東京と福岡」などに関してはレイヤ３のみが探索テーブル１２７及び探索用ブロックデータ１２８を持つ。
【００３３】
他の例では、最上位のレイヤにおいても、全国の組合せを持たずに、所定範囲内に存在する出発地と目的地の組合せについて探索テーブル１２７及び探索用ブロックデータ１２８を持つこととしてもよい。また、さらに他の例では、各レイヤによって、探索テーブル１２７及び探索用ブロックデータ１２８を持つ範囲が異なるようにしてもよい。この場合の好適な例では、上位レイヤになるにしたがって、探索テーブル１２７及び探索用ブロックデータ１２８を持つ範囲が広がるようにする。例えばレイヤ１は東京都内の出発地と目的地の組合せについて探索テーブル１２７及び探索用ブロックデータ１２８を持ち、レイヤ２は関東の出発地と目的地の組合せについて探索テーブル１２７及び探索用ブロックデータ１２８を持ち、レイヤ３は全国の出発地と目的地の組合せについて探索テーブル１２７及び探索用ブロックデータ１２８を持つようにしてもよい。
【００３４】
ノード及びリンクの例を図３（Ａ）及び３（Ｂ）に示す。図３（Ａ）に示す複数の道路１１１を含む地図は、図３（Ｂ）に示すように複数のノード及びリンクにより構成される。なお、図３（Ｂ）においては、各ノードをノードＩＤ（Ｎ００００１など）で示し、各リンクをリンクＩＤ（Ｌ００００１など）で示している。
【００３５】
探索テーブル１２７は、出発地と目的地の組合せ毎に、経路探索処理に使用する探索用ブロックデータ１２８を特定するテーブルである。探索用ブロックデータ１２８は、経路探索処理において使用されるリンクを示したデータであり、地理上の所定のブロック毎に用意される。即ち、詳細は後述するが、経路探索時には、探索テーブル１２７を参照して、出発地と目的地の組合せに対応する探索用ブロックデータ１２８が特定され、それら探索用ブロックデータ１２８に含まれるリンクを対象として経路探索処理が実行されることになる。
【００３６】
以下、探索用ブロックデータについて詳しく説明する。前述のように、経路探索用データ１２４は、各レイヤ毎にリンクデータ１２６を含んでいる。リンクデータ１２６は、地理上の所定のブロック毎に用意されたデータであり、対応するレイヤのレベルにおいて、基本的に当該ブロック内に存在する全てのリンクを含んでいる。よって、基本的には、リンクデータ１２６を利用すれば経路探索を実行することができる。しかし、リンクデータ１２６には、対応するブロック内の全てのリンクが含まれているので、経路探索の条件によっては不要なリンクも含まれている。例えば、あるブロック内に東西南北に延びる幹線道路があるとする。経路探索における出発地と目的地との位置関係が南北に離れている場合、経路探索において東西に延びる幹線道路を考慮する必要性は低い。即ち、南北方向に離れた出発地と目的地との間の経路探索では、各ブロック内に含まれるリンクのうち、主として南北方向に延びるリンクを考慮すればよく、東西方向に延びるリンクを考慮する必要性は低い。しかしながら、リンクデータ１２６は対応するブロック内に存在する全てのリンクを含んでいるので、リンクデータ１２６を利用して経路探索を実行すると、必要性の低いリンクまでを対象に経路探索の計算を行うこととなり、不必要に計算に時間を要することとなる。
【００３７】
このため、本実施例では、出発地と目的地の組合せ毎に、その出発地と目的地の間の経路探索において考慮すべきリンクを示すデータ（以下、「探索用データ」と呼ぶ。）を作成する。
【００３８】
図４及び図５に、出発地と目的地との間の探索用データ（以下、「探索用全体データ」とも呼ぶ。）の例を示す。図４（Ａ）は札幌から福岡への経路探索に用いられるリンクを示す探索用全体データを示し、図４（Ｂ）は札幌から高知への経路探索に用いられるリンクを示す探索用全体データを示し、図４（Ｃ）は札幌から那覇への経路探索に用いられるリンクを示す探索用全体データを示す。これらを比較すると、全体としては各探索用全体データに含まれるリンクは異なっている。特に中国、四国、九州あたりのエリアでは違いは顕著であり、破線１３０で示す東京を含むエリアでも微妙な差異があるが、東北や北陸においてはほぼ同じリンクが含まれていることがわかる。
【００３９】
他の例として、図５（Ａ）は仙台から名古屋への経路探索に用いられるリンクを示す探索用全体データを示し、図５（Ｂ）は仙台から金沢への経路探索に用いられるリンクを示す探索用全体データを示す。これらを比較すると、破線１３０で示すエリア内では、含まれるリンクは非常に類似している。
【００４０】
そこで、本実施例では、探索用データをブロック毎に分割して用意し、類似するブロックの探索用データを１つに統合して、探索用データの数を減らすこととした。これにより、経路探索専用に使用されるデータのデータ量を押さえつつ、迅速な経路探索を可能とした。なお、ブロック単位に分割された探索用データを「探索用ブロックデータ」と呼ぶ。
【００４１】
まず、探索用ブロックデータの統合方法について簡単に説明する。本実施例では、同一のブロックに対応する探索用ブロックデータであって、所定値以上の類似度を有するものを１つの探索用ブロックデータに統合する。統合する処理は、具体的にはリンクの論理和を採ることである。例えば、同一のブロックについて、図６に示すように、出発地Ｍから目的地Ｎへの経路探索において使用される探索用ブロックデータ１３１ａと、出発地Ｐから目的地Ｑへの経路探索において使用される探索用ブロックデータ１３１ｂがあったとする。両者はそれぞれ他方に無いリンクを１つずつ含んでいるが、これらが類似すると仮定した場合、探索用ブロックデータ１３１ａと１３１ｂの論理和を演算することにより、１つの探索用ブロックデータ１３１ｃに統合することができる。即ち、統合した探索用ブロックデータ１３１ｃを用意しておき、これを出発地Ｍから目的地Ｎへの探索と、出発地Ｐから目的地Ｑへの探索のどちらにおいても使用することとすれば、探索用ブロックデータとして記憶すべきデータ量を低減することができる。
【００４２】
次に、探索用ブロックデータの作成処理について説明する。図７は、探索用ブロックデータの作成処理を示すフローチャートである。なお、この処理は、ＰＣなどの端末装置において、コンピュータがプログラムを実行することにより実現することができる。
【００４３】
まず、出発地及び目的地の複数の組合せについて、図４及び図５に例示するような探索用全体データが作成される（ステップＳ１０）。この処理は、出発地及び目的地を含む探索条件に従って、リンクデータ中に含まれる複数のリンクから、当該出発地及び目的地の組合せに対して適切なリンクを抽出することにより行われる。具体的には、リンクデータ中の全リンクから、高速道路や主要幹線道路などのある程度の大きさの道路に対応するリンクや、出発地及び目的地の方角に延びている道路に対応するリンクを抽出する。
【００４４】
そして、複数の組合せに対して探索用全体データが作成されると、次に、各組合せに対応する探索用全体データが、地理上の所定のブロック単位に分割され、探索用ブロックデータが得られる（ステップＳ１１）。次に、同一のブロックに対応する複数の探索用ブロックデータから、類似するものが抽出され、統合される（ステップＳ１２）。ここで、「類似する」とは、比較の対象となる２つの探索用ブロックデータ中に共通するリンクがどの程度含まれているかにより判定される。１つの例では、あるブロック中に含まれる全リンク数を「Ｘ」とし、比較の対象となる２つの探索用ブロックデータ中に共通して含まれるリンク数を「Ｙ」としたときに、以下の式で類似度を計算する。
【００４５】
類似度＝Ｙ／Ｘ
こうして得られた類似度が所定値以上である場合に、それら２つの探索用ブロックデータは「類似する」と判定される。なお、上記の例では、比較の対象となる２つの探索用ブロックデータ中に含まれる共通するリンクの割合に基づいて類似度を判定しているが、その代わりに、比較の対象となる２つの探索用ブロックデータ中に含まれる共通するリンクの数に基づいて類似度を判定することとしてもよい。
【００４６】
なお、探索用ブロックデータを統合する処理は、図６を参照して既に説明したように、２つの探索用ブロックデータに含まれるリンクの論理和を演算することにより実現できる。こうして、類似する探索用ブロックデータが統合されると、１つのブロックについて、共通するリンクの割合が少ない、即ち類似していない複数の探索用ブロックデータが用意されることになる。
【００４７】
図８（Ａ）は、上記のように、ブロック毎に用意された探索用ブロックデータのリストの一例を示す。この例では、ブロックＡ、Ｂ及びＩについては１つのみの探索用ブロックデータが用意されており、ブロックＥ及びＨについては４つの探索用ブロックデータが用意されている。
【００４８】
次に、出発地及び目的地の各組合せについて、経路探索に使用すべき探索用ブロックデータを決定し、探索テーブルが作成される（ステップＳ１３）。ある出発地及び目的地の組合せに対して使用される探索用ブロックデータは、基本的には、当該組合せに対して作成された探索用全体データを分割して得られた各探索用ブロックデータとなる。但し、上記の統合処理により統合された場合には、統合後の探索用ブロックデータが使用される。こうして、探索用ブロックデータ及び探索テーブルが作成される。
【００４９】
作成された探索テーブルの例を図８（Ｂ）に示す。また、図９及び図１０は、図８（Ｂ）に例示する出発地と目的地の組合せに対応する探索用ブロックデータをブロック毎に示したものである。例えば図９（Ａ）に示す札幌から福岡への経路探索と、図９（Ｂ）に示す札幌から高知への経路探索とでは、ブロックＡ、Ｂ、Ｃ、Ｈ及びＩでは、同一の探索用ブロックデータが使用されるが、ブロックＣ、Ｄ、Ｅ及びＦでは異なる探索用ブロックデータが使用される。同様に、図１０（Ａ）に示す仙台から名古屋への経路探索と、図１０（Ｂ）に示す仙台から金沢への経路探索とでは、ブロックＣ、Ｆ及びＩでは同一の探索用ブロックデータが使用されるが、ブロックＥ及びＨでは異なる探索用ブロックデータが使用される。
【００５０】
このように、類似度の高い探索用ブロックデータを統合することにより、探索用ブロックデータ全体のデータ量を低減することができる。これにより、記憶容量の小さいシステムへの適用が可能となり、また、探索用ブロックデータの更新処理の時間も短縮することができる。
【００５１】
次に、ブロックの大きさについて検討する。本実施例では、ブロックの大きさを小さくしても、類似する探索用ブロックデータが統合されるため、探索用データの全体のデータ量は大きくならない。また、理論的にはブロックを小さくすればそれだけ類似する探索用ブロックデータが増加するので、探索用データの全体のデータ量は小さくなることが期待できる。但し、ブロックを小さくすると、探索用ブロックデータを用いて経路探索を行う際に多数の探索用ブロックデータを読み込む必要があり、経路探索処理に時間を要する可能性がある。よって、実際には様々なパラメータを調整して、ブロックの大きさを最適化することが望ましい。
【００５２】
［ナビゲーション装置］
図１１に、本発明の実施例に係るナビゲーション装置２００の構成を示す。図１１に示すように、ナビゲーション装置２００は、自立測位装置１０、ＧＰＳ受信機１８、システムコントローラ２０、ディスクドライブ３１、データ記憶ユニット３６、通信用インタフェース３７、通信装置３８、表示ユニット４０、音声出力ユニット５０及び入力装置６０を備える。
【００５３】
自立測位装置１０は、加速度センサ１１、角速度センサ１２及び距離センサ１３を備える。加速度センサ１１は、例えば圧電素子からなり、車両の加速度を検出し、加速度データを出力する。角速度センサ１２は、例えば振動ジャイロからなり、車両の方向変換時における車両の角速度を検出し、角速度データ及び相対方位データを出力する。距離センサ１３は、車両の車輪の回転に伴って発生されているパルス信号からなる車速パルスを計測する。
【００５４】
ＧＰＳ受信機１８は、複数のＧＰＳ衛星から、測位用データを含む下り回線データを搬送する電波１９を受信する。測位用データは、緯度及び経度情報等から車両の絶対的な位置を検出するために用いられる。
【００５５】
システムコントローラ２０は、インタフェース２１、ＣＰＵ（Central Processing Unit）２２、ＲＯＭ（Read Only Memory）２３及びＲＡＭ（Random Access Memory）２４を含んでおり、ナビゲーション装置２００全体の制御を行う。
【００５６】
インタフェース２１は、加速度センサ１１、角速度センサ１２及び距離センサ１３並びにＧＰＳ受信機１８とのインタフェース動作を行う。そして、これらから、車速パルス、加速度データ、相対方位データ、角速度データ、ＧＰＳ測位データ、絶対方位データ等をシステムコントローラ２０に入力する。ＣＰＵ２２は、システムコントローラ２０全体を制御する。ＲＯＭ２３は、システムコントローラ２０を制御する制御プログラム等が格納された図示しない不揮発性メモリ等を有する。ＲＡＭ２４は、入力装置６０を介して使用者により予め設定された経路データ等の各種データを読み出し可能に格納したり、ＣＰＵ２２に対してワーキングエリアを提供したりする。
【００５７】
システムコントローラ２０、ＣＤ−ＲＯＭドライブ又はＤＶＤ−ＲＯＭドライブなどのディスクドライブ３１、データ記憶ユニット３６、通信用インタフェース３７、表示ユニット４０、音声出力ユニット５０及び入力装置６０は、バスライン３０を介して相互に接続されている。
【００５８】
ディスクドライブ３１は、システムコントローラ２０の制御の下、ＣＤ又はＤＶＤといったディスク３３から、音楽データ、映像データなどのコンテンツデータを読み出し、出力する。なお、ディスクドライブ３１は、ＣＤ−ＲＯＭドライブ又はＤＶＤ−ＲＯＭドライブのうち、いずれか一方としてもよいし、ＣＤ及びＤＶＤコンパチブルのドライブとしてもよい。
【００５９】
データ記憶ユニット３６は、例えば、ＨＤＤなどにより構成され、地図データや施設データなどのナビゲーション処理に用いられる各種データを記憶する。
【００６０】
通信装置３８は、例えば、ＦＭチューナやビーコンレシーバ、携帯電話や専用の通信カードなどにより構成され、通信用インタフェース３７を介して、ＶＩＣＳ（Vehicle Information Communication System）センタから配信される渋滞や交通情報などの道路交通情報、その他の情報を受信する。
【００６１】
表示ユニット４０は、システムコントローラ２０の制御の下、各種表示データをディスプレイなどの表示装置に表示する。具体的には、システムコントローラ２０は、データ記憶ユニット３６から地図データを読み出す。表示ユニット４０は、システムコントローラ２０によってデータ記憶ユニット３６から読み出された地図データを、ディスプレイなどの表示画面上に表示する。表示ユニット４０は、バスライン３０を介してＣＰＵ２２から送られる制御データに基づいて表示ユニット４０全体の制御を行うグラフィックコントローラ４１と、ＶＲＡＭ（Video RAM ）等のメモリからなり即時表示可能な画像情報を一時的に記憶するバッファメモリ４２と、グラフィックコントローラ４１から出力される画像データに基づいて、液晶、ＣＲＴ（Cathode Ray Tube）等のディスプレイ４４を表示制御する表示制御部４３と、ディスプレイ４４とを備える。ディスプレイ４４は、例えば対角５〜１０インチ程度の液晶表示装置等からなり、車内のフロントパネル付近に装着される。
【００６２】
音声出力ユニット５０は、システムコントローラ２０の制御の下、ＣＤ−ＲＯＭドライブ３１又はＤＶＤ−ＲＯＭ３２、若しくはＲＡＭ２４等からバスライン３０を介して送られる音声デジタルデータのＤ／Ａ（Digital to Analog）変換を行うＤ／Ａコンバータ５１と、Ｄ／Ａコンバータ５１から出力される音声アナログ信号を増幅する増幅器（ＡＭＰ）５２と、増幅された音声アナログ信号を音声に変換して車内に出力するスピーカ５３とを備えて構成されている。
【００６３】
入力装置６０は、各種コマンドやデータを入力するための、キー、スイッチ、ボタン、リモコン、音声入力装置等から構成されている。入力装置６０は、車内に搭載された当該車載用電子システムの本体のフロントパネルやディスプレイ４４の周囲に配置される。また、ディスプレイ４４がタッチパネル方式である場合には、ディスプレイ４４の表示画面上に設けられたタッチパネルも入力装置６０として機能する。
【００６４】
なお、ＣＰＵ２２は、予めＲＯＭ２３などに記憶された経路探索プログラムを実行することにより、経路探索手段として機能する。また、図１に例示する地図データは、記憶部としてのデータ記憶ユニット３６に記憶される。
【００６５】
［経路探索処理］
次に、経路探索処理について説明する。図１２に経路探索処理のフローチャートを示す。実際には、ＣＰＵ２２が経路探索プログラムを実行することにより、ナビゲーション装置２００が経路探索装置として動作し、経路探索処理を実行する。
【００６６】
まず、経路探索を行うユーザは、ナビゲーション装置２００の入力装置６０を使用して、経路探索機能を呼び出し、目的地（最終目的地）及び探索条件などを指定、入力する。これに応じて、ＣＰＵ２２は、経路探索のための出発地及び目的地を決定する（ステップＳ２０）。通常、ナビゲーション装置２００を搭載した車両の自車位置が出発地に設定される。なお、ＰＣなどの端末装置が経路探索装置となる場合には、ユーザが出発地を指定する場合もある。
【００６７】
次に、ＣＰＵ２２は、図８（Ｂ）に例示する探索テーブルを参照して、決定された出発地と目的地の組合せに対応する探索用ブロックデータを決定し（ステップＳ２１）、それらの探索用ブロックデータを用いて、出発地から目的地へ至る複数の経路候補を算出する（ステップＳ２２）。
【００６８】
こうして、出発地から目的地へ至る複数の候補経路が得られると、ＣＰＵ２２は各候補経路についてコスト計算を行い、最小コストを有する候補経路を決定してユーザに提示する（ステップＳ２３）。こうして、経路探索処理が終了する。なお、コスト計算とは、経路計算において一般的に用いられる手法であり、リンク及びノードに予め対応付けされたコストの合計を計算することをいう。リンク及びノードに対応付けされたコストの値は、そのリンクやノードを通過する際に要する時間、道路の車線数などの各種の情報に基づいて予め設定されている。なお、コスト計算は既知の手法であるので、その詳細な説明は省略する。
【００６９】
なお、上記の例では、出発地と目的地を含むブロックについても、探索用ブロックデータを用いて経路探索を実行している。その代わりに、出発地及び目的地を含むブロックについては、探索用ブロックデータよりも細かいリンクを含むリンクデータを用いて、経路探索を行うこととしてもよい。これにより、出発地及び目的地と、高速道路や主要幹線道路との間において、小さい道路を含む多数の道路を考慮して適切な経路を設定することができる。
【図面の簡単な説明】
【００７０】
【図１】本発明の実施例において使用する地図データの構成を模式的に示す。
【図２】経路探索用データの構成例を示す。
【図３】リンク及びノードを説明する図である。
【図４】探索用全体データの例を示す。
【図５】探索用全体データの他の例を示す。
【図６】探索用ブロックデータの統合方法を説明する図である。
【図７】探索用ブロックデータ作成処理のフローチャートである。
【図８】探索用ブロックデータ及び探索テーブルの例である。
【図９】出発地と目的地の組合せに対応する探索用ブロックデータの例を示す。
【図１０】出発地と目的地の組合せに対応する探索用ブロックデータの例を示す。
【図１１】実施例によるナビゲーション装置の構成を示すブロック図である。
【図１２】経路探索処理のフローチャートである。
【符号の説明】
【００７１】
１０ 自立測位装置
１８ ＧＰＳ受信機
２０ システムコントローラ
２２ ＣＰＵ
３６ データ記憶ユニット
４０ 表示ユニット
６０ 入力装置
１２０ 地図データ
１２２ 地図表示用データ
１２４ 経路探索用データ
１２５ ノードデータ
１２７ 探索用テーブル
１２８ 探索用ブロックデータ
２００ ナビゲーション装置
【技術分野】
【０００１】
本発明は、地図データを利用する経路探索手法に関する。
【背景技術】
【０００２】
カーナビゲーション装置、インターネットを利用した地図提供アプリケーションなどには経路探索機能が設けられている。経路探索機能は地理上の出発地から目的地に至る経路を、地図データを利用して自動計算し、ユーザに提示する機能である。
【０００３】
一般的に、遠距離の経路探索は、候補となる道路数が多くなるため時間を要する。通常、経路探索用データは階層構造となっており、遠距離の経路計算では、主要道路のみを含むデータを使用することにより、計算の高速化を図っている。しかし、主要道路に限っても、全国的には相当数の道路リンクが存在する。よって、複数の県を経由するような遠距離経路の探索においては、主要道路の道路リンク全てを計算の対象とするため、膨大な計算量が要求される。
【０００４】
遠距離の経路探索を高速に行うために、経路探索用データ中に、通常のノード及びリンクのデータ以外に特殊なデータを含める手法が知られている。例えば、出発地のエリアと目的地のエリアの組合せに対して、その間の経路探索に必要なリンクのみを格納したデータを用意し、これを用いて経路探索を行う手法が知られている。
【０００５】
また、特許文献１には以下のような手法が提案されている。まず、地図上の地域を複数の探索区画に分割し、各探索区画に対して、一般的な使用が予想される高速道路や国道などの候補道路、及び、その候補道路への接続点（出入口）を予め決めて記憶しておく。経路探索時には、始点及び終点を含む探索区画に対応する候補道路及びその候補道路への接続点を呼び出し、候補道路のみを用いて経路計算を行う。
【０００６】
【特許文献１】特開平１１−６４０２３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、上記のような手法では、経路探索用データに含まれる特殊データの量が大きくなってしまう。また、道路の変更に応じて経路探索用データの更新が必要となった場合に、更新すべきデータ量も増大する。
【０００８】
本発明が解決しようとする課題としては、上記のものが一例として挙げられる。本発明は、経路探索用データのデータ量を過度に増大させることなく、遠距離の経路計算を高速化することを課題とする。
【課題を解決するための手段】
【０００９】
請求項１に記載の発明は、経路探索装置であって、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶した記憶部と、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段と、を備えることを特徴とする。
【００１０】
請求項４に記載の発明は、経路探索方法であって、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶部に記憶する記憶工程と、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索工程と、を備えることを特徴とする。
【００１１】
請求項５に記載の発明は、記憶部及びコンピュータを備える端末装置において実行される経路探索プログラムであって、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを前記記憶部に記憶する記憶手段、及び、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段、として前記コンピュータを機能させることを特徴とする。
【００１２】
請求項７に記載の発明は、記憶媒体であって、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶したことを特徴とする。
【００１３】
請求項１０に記載の発明は、探索用データ作成装置であって、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段と、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段と、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段と、前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段と、を備えることを特徴とする。
【００１４】
請求項１１に記載の発明は、探索用データ作成方法であって、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成工程と、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割工程と、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合工程と、前記統合工程による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力工程と、を備えることを特徴とする。
【００１５】
請求項１２に記載の発明は、コンピュータを備える端末装置において実行される探索用データ作成プログラムであって、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段、及び、前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段、として前記コンピュータを機能させることを特徴とする。
【発明を実施するための最良の形態】
【００１６】
本発明の１つの実施形態では、経路探索装置は、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶した記憶部と、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段と、を備える。
【００１７】
上記の経路探索装置は、例えばカーナビゲーション装置などに搭載することができ、出発地から目的地へ至る経路探索のための経路探索用データを記憶している。経路探索用データは、探索用ブロックデータと、探索テーブルとを含む。探索用ブロックデータは、地理上の所定のブロック毎に１つ又は複数用意されており、経路探索に用いるリンクを示すデータである。また、探索テーブルは、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定するデータである。経路探索時には、出発地と目的地とが決定されると、出発地及び目的地の組合せに対応する前記探索用ブロックデータが決定され、決定された前記探索用ブロックデータを用いて経路探索が行われる。
【００１８】
上記の経路探索装置の一態様では、１つのブロックに対応して用意された複数の探索用ブロックデータの各々は、当該１つのブロックに対応して用意された他の探索用ブロックデータとの間で共通するリンク数が所定割合以下である。これにより、共通するリンクを重複して含む探索用ブロックデータの数を減らすことができ、経路探索用データのデータ量を低減することができる。
【００１９】
上記の経路探索装置の他の一態様では、前記記憶部は、前記所定のブロック毎に用意され、当該ブロック内に存在する全てのリンクを示すリンクデータを記憶しており、前記経路探索手段は、前記出発地及び前記目的地が属するブロックについては、前記リンクデータを用いて経路探索を行う。これにより、出発地及び目的地の周辺では、多数の道路を考慮して適切な経路探索を行うことができる。
【００２０】
本発明の他の実施形態では、経路探索方法は、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶部に記憶する記憶工程と、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索工程と、を備える。
【００２１】
本発明のさらに他の実施形態では、記憶部及びコンピュータを備える端末装置において実行される経路探索プログラムは、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを前記記憶部に記憶する記憶手段、及び、前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段、として前記コンピュータを機能させる。また、上記の経路探索プログラムは記憶媒体に記憶した状態で取り扱うことができる。
【００２２】
本発明のさらに他の実施形態では、記憶媒体は、地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶する。
【００２３】
上記の記憶媒体の好適な例では、記経路探索用データは、複数のレイヤからなる階層構造を有しており、前記探索用ブロックデータ及び前記探索テーブルは、前記複数のレイヤのうち少なくとも最上位のレイヤの前記経路探索用データに含まれている。また、他の好適な例では、前記経路探索用データは、複数のレイヤからなる階層構造を有しており、前記複数のレイヤの前記経路探索用データは、所定範囲内に存在する前記出発地と目的地の組合せについてのみ、前記探索用ブロックデータ及び前記探索テーブルを含んでいる。
【００２４】
本発明のさらに他の実施形態では、探索用データ作成装置は、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段と、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段と、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段と、前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段と、を備える。
【００２５】
上記の探索用データ作成装置では、まず、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データが作成される。次に、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータが作成される。次に、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータが１つに統合され、統合処理後の前記探索用ブロックデータが探索用データとして出力される。
【００２６】
本発明のさらに他の実施形態では、探索用データ作成方法は、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成工程と、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割工程と、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合工程と、前記統合工程による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力工程と、を備える。
【００２７】
本発明のさらに他の実施形態では、コンピュータを備える端末装置において実行される探索用データ作成プログラムは、出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段、前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段、同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段、及び、前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段、として前記コンピュータを機能させる。
【実施例】
【００２８】
以下、図面を参照して本発明の好適な実施例について説明する。
【００２９】
［地図データ］
図１に、本実施例において使用する地図データの構成を模式的に示す。地図データは、異なる複数の縮尺に対応する複数のレイヤを含む階層構造に構成されている。図１は説明の便宜上、３階層の地図データを例示しているが、地図データはより多数の階層構造としてもよい。各レイヤにおいて、地図データの１つの単位を「ブロック（Ｂ）」と呼ぶ。なお、「ブロック」は地理上の広がりを持った範囲を示す概念であり、「パーセル」、「メッシュ」などと表現することもできる。図１において、レイヤ３は最上位レイヤであり、最も広域の地図に対応する。レイヤ１は最下位レイヤであり、最も詳細な地図に対応する。
【００３０】
地図データ１２０は、各レイヤ毎に別個に用意されており、それぞれ地図表示用データ１２２と、経路探索用データ１２４とを含む。地図表示用データ１２２は、ユーザに対して地図画像を表示するために使用されるデータであり、主として地図に対応する画像データを含む。経路探索用データ１２４は、経路探索機能による経路探索に使用されるデータである。
【００３１】
図２に、最上位レイヤ３の経路探索用データの構成を示す。経路探索用データ１２４は、ノードデータ１２５、リンクデータ１２６、探索テーブル１２７及び探索用ブロックデータ１２８を含む。ノードは道路上の交差点などの所定の地点に対応し、ノードデータ１２５はノードを示すデータである。一方、リンクは交差点などにより区切られた道路の１区画に対応し、リンクデータ１２６はリンクを示すデータである。なお、本実施例では、最上位レイヤ以外のレイヤでは、経路探索用データは、ノードデータ１２５及びリンクデータ１２６を含むが、探索テーブル１２７及び探索用ブロックデータ１２８は含まないものとする。
【００３２】
但し、本発明の適用がこれに限られるものではなく、全てのレイヤにおいて経路探索用データが探索テーブル１２７及び探索用ブロックデータ１２８を含むように構成しても構わない。例えばレイヤ３は全国の組合せを持ち、レイヤ２は２００ｋｍ以内にあるブロックに対してのみそれらのデータを持つものとしてもよい。この場合、出発地と目的地のうち「東京と山梨」、「東京と栃木」などに関してはレイヤ３のみならずレイヤ２でも探索テーブル１２７及び探索用ブロックデータ１２８を持つが、「東京と北海道」、「東京と福岡」などに関してはレイヤ３のみが探索テーブル１２７及び探索用ブロックデータ１２８を持つ。
【００３３】
他の例では、最上位のレイヤにおいても、全国の組合せを持たずに、所定範囲内に存在する出発地と目的地の組合せについて探索テーブル１２７及び探索用ブロックデータ１２８を持つこととしてもよい。また、さらに他の例では、各レイヤによって、探索テーブル１２７及び探索用ブロックデータ１２８を持つ範囲が異なるようにしてもよい。この場合の好適な例では、上位レイヤになるにしたがって、探索テーブル１２７及び探索用ブロックデータ１２８を持つ範囲が広がるようにする。例えばレイヤ１は東京都内の出発地と目的地の組合せについて探索テーブル１２７及び探索用ブロックデータ１２８を持ち、レイヤ２は関東の出発地と目的地の組合せについて探索テーブル１２７及び探索用ブロックデータ１２８を持ち、レイヤ３は全国の出発地と目的地の組合せについて探索テーブル１２７及び探索用ブロックデータ１２８を持つようにしてもよい。
【００３４】
ノード及びリンクの例を図３（Ａ）及び３（Ｂ）に示す。図３（Ａ）に示す複数の道路１１１を含む地図は、図３（Ｂ）に示すように複数のノード及びリンクにより構成される。なお、図３（Ｂ）においては、各ノードをノードＩＤ（Ｎ００００１など）で示し、各リンクをリンクＩＤ（Ｌ００００１など）で示している。
【００３５】
探索テーブル１２７は、出発地と目的地の組合せ毎に、経路探索処理に使用する探索用ブロックデータ１２８を特定するテーブルである。探索用ブロックデータ１２８は、経路探索処理において使用されるリンクを示したデータであり、地理上の所定のブロック毎に用意される。即ち、詳細は後述するが、経路探索時には、探索テーブル１２７を参照して、出発地と目的地の組合せに対応する探索用ブロックデータ１２８が特定され、それら探索用ブロックデータ１２８に含まれるリンクを対象として経路探索処理が実行されることになる。
【００３６】
以下、探索用ブロックデータについて詳しく説明する。前述のように、経路探索用データ１２４は、各レイヤ毎にリンクデータ１２６を含んでいる。リンクデータ１２６は、地理上の所定のブロック毎に用意されたデータであり、対応するレイヤのレベルにおいて、基本的に当該ブロック内に存在する全てのリンクを含んでいる。よって、基本的には、リンクデータ１２６を利用すれば経路探索を実行することができる。しかし、リンクデータ１２６には、対応するブロック内の全てのリンクが含まれているので、経路探索の条件によっては不要なリンクも含まれている。例えば、あるブロック内に東西南北に延びる幹線道路があるとする。経路探索における出発地と目的地との位置関係が南北に離れている場合、経路探索において東西に延びる幹線道路を考慮する必要性は低い。即ち、南北方向に離れた出発地と目的地との間の経路探索では、各ブロック内に含まれるリンクのうち、主として南北方向に延びるリンクを考慮すればよく、東西方向に延びるリンクを考慮する必要性は低い。しかしながら、リンクデータ１２６は対応するブロック内に存在する全てのリンクを含んでいるので、リンクデータ１２６を利用して経路探索を実行すると、必要性の低いリンクまでを対象に経路探索の計算を行うこととなり、不必要に計算に時間を要することとなる。
【００３７】
このため、本実施例では、出発地と目的地の組合せ毎に、その出発地と目的地の間の経路探索において考慮すべきリンクを示すデータ（以下、「探索用データ」と呼ぶ。）を作成する。
【００３８】
図４及び図５に、出発地と目的地との間の探索用データ（以下、「探索用全体データ」とも呼ぶ。）の例を示す。図４（Ａ）は札幌から福岡への経路探索に用いられるリンクを示す探索用全体データを示し、図４（Ｂ）は札幌から高知への経路探索に用いられるリンクを示す探索用全体データを示し、図４（Ｃ）は札幌から那覇への経路探索に用いられるリンクを示す探索用全体データを示す。これらを比較すると、全体としては各探索用全体データに含まれるリンクは異なっている。特に中国、四国、九州あたりのエリアでは違いは顕著であり、破線１３０で示す東京を含むエリアでも微妙な差異があるが、東北や北陸においてはほぼ同じリンクが含まれていることがわかる。
【００３９】
他の例として、図５（Ａ）は仙台から名古屋への経路探索に用いられるリンクを示す探索用全体データを示し、図５（Ｂ）は仙台から金沢への経路探索に用いられるリンクを示す探索用全体データを示す。これらを比較すると、破線１３０で示すエリア内では、含まれるリンクは非常に類似している。
【００４０】
そこで、本実施例では、探索用データをブロック毎に分割して用意し、類似するブロックの探索用データを１つに統合して、探索用データの数を減らすこととした。これにより、経路探索専用に使用されるデータのデータ量を押さえつつ、迅速な経路探索を可能とした。なお、ブロック単位に分割された探索用データを「探索用ブロックデータ」と呼ぶ。
【００４１】
まず、探索用ブロックデータの統合方法について簡単に説明する。本実施例では、同一のブロックに対応する探索用ブロックデータであって、所定値以上の類似度を有するものを１つの探索用ブロックデータに統合する。統合する処理は、具体的にはリンクの論理和を採ることである。例えば、同一のブロックについて、図６に示すように、出発地Ｍから目的地Ｎへの経路探索において使用される探索用ブロックデータ１３１ａと、出発地Ｐから目的地Ｑへの経路探索において使用される探索用ブロックデータ１３１ｂがあったとする。両者はそれぞれ他方に無いリンクを１つずつ含んでいるが、これらが類似すると仮定した場合、探索用ブロックデータ１３１ａと１３１ｂの論理和を演算することにより、１つの探索用ブロックデータ１３１ｃに統合することができる。即ち、統合した探索用ブロックデータ１３１ｃを用意しておき、これを出発地Ｍから目的地Ｎへの探索と、出発地Ｐから目的地Ｑへの探索のどちらにおいても使用することとすれば、探索用ブロックデータとして記憶すべきデータ量を低減することができる。
【００４２】
次に、探索用ブロックデータの作成処理について説明する。図７は、探索用ブロックデータの作成処理を示すフローチャートである。なお、この処理は、ＰＣなどの端末装置において、コンピュータがプログラムを実行することにより実現することができる。
【００４３】
まず、出発地及び目的地の複数の組合せについて、図４及び図５に例示するような探索用全体データが作成される（ステップＳ１０）。この処理は、出発地及び目的地を含む探索条件に従って、リンクデータ中に含まれる複数のリンクから、当該出発地及び目的地の組合せに対して適切なリンクを抽出することにより行われる。具体的には、リンクデータ中の全リンクから、高速道路や主要幹線道路などのある程度の大きさの道路に対応するリンクや、出発地及び目的地の方角に延びている道路に対応するリンクを抽出する。
【００４４】
そして、複数の組合せに対して探索用全体データが作成されると、次に、各組合せに対応する探索用全体データが、地理上の所定のブロック単位に分割され、探索用ブロックデータが得られる（ステップＳ１１）。次に、同一のブロックに対応する複数の探索用ブロックデータから、類似するものが抽出され、統合される（ステップＳ１２）。ここで、「類似する」とは、比較の対象となる２つの探索用ブロックデータ中に共通するリンクがどの程度含まれているかにより判定される。１つの例では、あるブロック中に含まれる全リンク数を「Ｘ」とし、比較の対象となる２つの探索用ブロックデータ中に共通して含まれるリンク数を「Ｙ」としたときに、以下の式で類似度を計算する。
【００４５】
類似度＝Ｙ／Ｘ
こうして得られた類似度が所定値以上である場合に、それら２つの探索用ブロックデータは「類似する」と判定される。なお、上記の例では、比較の対象となる２つの探索用ブロックデータ中に含まれる共通するリンクの割合に基づいて類似度を判定しているが、その代わりに、比較の対象となる２つの探索用ブロックデータ中に含まれる共通するリンクの数に基づいて類似度を判定することとしてもよい。
【００４６】
なお、探索用ブロックデータを統合する処理は、図６を参照して既に説明したように、２つの探索用ブロックデータに含まれるリンクの論理和を演算することにより実現できる。こうして、類似する探索用ブロックデータが統合されると、１つのブロックについて、共通するリンクの割合が少ない、即ち類似していない複数の探索用ブロックデータが用意されることになる。
【００４７】
図８（Ａ）は、上記のように、ブロック毎に用意された探索用ブロックデータのリストの一例を示す。この例では、ブロックＡ、Ｂ及びＩについては１つのみの探索用ブロックデータが用意されており、ブロックＥ及びＨについては４つの探索用ブロックデータが用意されている。
【００４８】
次に、出発地及び目的地の各組合せについて、経路探索に使用すべき探索用ブロックデータを決定し、探索テーブルが作成される（ステップＳ１３）。ある出発地及び目的地の組合せに対して使用される探索用ブロックデータは、基本的には、当該組合せに対して作成された探索用全体データを分割して得られた各探索用ブロックデータとなる。但し、上記の統合処理により統合された場合には、統合後の探索用ブロックデータが使用される。こうして、探索用ブロックデータ及び探索テーブルが作成される。
【００４９】
作成された探索テーブルの例を図８（Ｂ）に示す。また、図９及び図１０は、図８（Ｂ）に例示する出発地と目的地の組合せに対応する探索用ブロックデータをブロック毎に示したものである。例えば図９（Ａ）に示す札幌から福岡への経路探索と、図９（Ｂ）に示す札幌から高知への経路探索とでは、ブロックＡ、Ｂ、Ｃ、Ｈ及びＩでは、同一の探索用ブロックデータが使用されるが、ブロックＣ、Ｄ、Ｅ及びＦでは異なる探索用ブロックデータが使用される。同様に、図１０（Ａ）に示す仙台から名古屋への経路探索と、図１０（Ｂ）に示す仙台から金沢への経路探索とでは、ブロックＣ、Ｆ及びＩでは同一の探索用ブロックデータが使用されるが、ブロックＥ及びＨでは異なる探索用ブロックデータが使用される。
【００５０】
このように、類似度の高い探索用ブロックデータを統合することにより、探索用ブロックデータ全体のデータ量を低減することができる。これにより、記憶容量の小さいシステムへの適用が可能となり、また、探索用ブロックデータの更新処理の時間も短縮することができる。
【００５１】
次に、ブロックの大きさについて検討する。本実施例では、ブロックの大きさを小さくしても、類似する探索用ブロックデータが統合されるため、探索用データの全体のデータ量は大きくならない。また、理論的にはブロックを小さくすればそれだけ類似する探索用ブロックデータが増加するので、探索用データの全体のデータ量は小さくなることが期待できる。但し、ブロックを小さくすると、探索用ブロックデータを用いて経路探索を行う際に多数の探索用ブロックデータを読み込む必要があり、経路探索処理に時間を要する可能性がある。よって、実際には様々なパラメータを調整して、ブロックの大きさを最適化することが望ましい。
【００５２】
［ナビゲーション装置］
図１１に、本発明の実施例に係るナビゲーション装置２００の構成を示す。図１１に示すように、ナビゲーション装置２００は、自立測位装置１０、ＧＰＳ受信機１８、システムコントローラ２０、ディスクドライブ３１、データ記憶ユニット３６、通信用インタフェース３７、通信装置３８、表示ユニット４０、音声出力ユニット５０及び入力装置６０を備える。
【００５３】
自立測位装置１０は、加速度センサ１１、角速度センサ１２及び距離センサ１３を備える。加速度センサ１１は、例えば圧電素子からなり、車両の加速度を検出し、加速度データを出力する。角速度センサ１２は、例えば振動ジャイロからなり、車両の方向変換時における車両の角速度を検出し、角速度データ及び相対方位データを出力する。距離センサ１３は、車両の車輪の回転に伴って発生されているパルス信号からなる車速パルスを計測する。
【００５４】
ＧＰＳ受信機１８は、複数のＧＰＳ衛星から、測位用データを含む下り回線データを搬送する電波１９を受信する。測位用データは、緯度及び経度情報等から車両の絶対的な位置を検出するために用いられる。
【００５５】
システムコントローラ２０は、インタフェース２１、ＣＰＵ（Central Processing Unit）２２、ＲＯＭ（Read Only Memory）２３及びＲＡＭ（Random Access Memory）２４を含んでおり、ナビゲーション装置２００全体の制御を行う。
【００５６】
インタフェース２１は、加速度センサ１１、角速度センサ１２及び距離センサ１３並びにＧＰＳ受信機１８とのインタフェース動作を行う。そして、これらから、車速パルス、加速度データ、相対方位データ、角速度データ、ＧＰＳ測位データ、絶対方位データ等をシステムコントローラ２０に入力する。ＣＰＵ２２は、システムコントローラ２０全体を制御する。ＲＯＭ２３は、システムコントローラ２０を制御する制御プログラム等が格納された図示しない不揮発性メモリ等を有する。ＲＡＭ２４は、入力装置６０を介して使用者により予め設定された経路データ等の各種データを読み出し可能に格納したり、ＣＰＵ２２に対してワーキングエリアを提供したりする。
【００５７】
システムコントローラ２０、ＣＤ−ＲＯＭドライブ又はＤＶＤ−ＲＯＭドライブなどのディスクドライブ３１、データ記憶ユニット３６、通信用インタフェース３７、表示ユニット４０、音声出力ユニット５０及び入力装置６０は、バスライン３０を介して相互に接続されている。
【００５８】
ディスクドライブ３１は、システムコントローラ２０の制御の下、ＣＤ又はＤＶＤといったディスク３３から、音楽データ、映像データなどのコンテンツデータを読み出し、出力する。なお、ディスクドライブ３１は、ＣＤ−ＲＯＭドライブ又はＤＶＤ−ＲＯＭドライブのうち、いずれか一方としてもよいし、ＣＤ及びＤＶＤコンパチブルのドライブとしてもよい。
【００５９】
データ記憶ユニット３６は、例えば、ＨＤＤなどにより構成され、地図データや施設データなどのナビゲーション処理に用いられる各種データを記憶する。
【００６０】
通信装置３８は、例えば、ＦＭチューナやビーコンレシーバ、携帯電話や専用の通信カードなどにより構成され、通信用インタフェース３７を介して、ＶＩＣＳ（Vehicle Information Communication System）センタから配信される渋滞や交通情報などの道路交通情報、その他の情報を受信する。
【００６１】
表示ユニット４０は、システムコントローラ２０の制御の下、各種表示データをディスプレイなどの表示装置に表示する。具体的には、システムコントローラ２０は、データ記憶ユニット３６から地図データを読み出す。表示ユニット４０は、システムコントローラ２０によってデータ記憶ユニット３６から読み出された地図データを、ディスプレイなどの表示画面上に表示する。表示ユニット４０は、バスライン３０を介してＣＰＵ２２から送られる制御データに基づいて表示ユニット４０全体の制御を行うグラフィックコントローラ４１と、ＶＲＡＭ（Video RAM ）等のメモリからなり即時表示可能な画像情報を一時的に記憶するバッファメモリ４２と、グラフィックコントローラ４１から出力される画像データに基づいて、液晶、ＣＲＴ（Cathode Ray Tube）等のディスプレイ４４を表示制御する表示制御部４３と、ディスプレイ４４とを備える。ディスプレイ４４は、例えば対角５〜１０インチ程度の液晶表示装置等からなり、車内のフロントパネル付近に装着される。
【００６２】
音声出力ユニット５０は、システムコントローラ２０の制御の下、ＣＤ−ＲＯＭドライブ３１又はＤＶＤ−ＲＯＭ３２、若しくはＲＡＭ２４等からバスライン３０を介して送られる音声デジタルデータのＤ／Ａ（Digital to Analog）変換を行うＤ／Ａコンバータ５１と、Ｄ／Ａコンバータ５１から出力される音声アナログ信号を増幅する増幅器（ＡＭＰ）５２と、増幅された音声アナログ信号を音声に変換して車内に出力するスピーカ５３とを備えて構成されている。
【００６３】
入力装置６０は、各種コマンドやデータを入力するための、キー、スイッチ、ボタン、リモコン、音声入力装置等から構成されている。入力装置６０は、車内に搭載された当該車載用電子システムの本体のフロントパネルやディスプレイ４４の周囲に配置される。また、ディスプレイ４４がタッチパネル方式である場合には、ディスプレイ４４の表示画面上に設けられたタッチパネルも入力装置６０として機能する。
【００６４】
なお、ＣＰＵ２２は、予めＲＯＭ２３などに記憶された経路探索プログラムを実行することにより、経路探索手段として機能する。また、図１に例示する地図データは、記憶部としてのデータ記憶ユニット３６に記憶される。
【００６５】
［経路探索処理］
次に、経路探索処理について説明する。図１２に経路探索処理のフローチャートを示す。実際には、ＣＰＵ２２が経路探索プログラムを実行することにより、ナビゲーション装置２００が経路探索装置として動作し、経路探索処理を実行する。
【００６６】
まず、経路探索を行うユーザは、ナビゲーション装置２００の入力装置６０を使用して、経路探索機能を呼び出し、目的地（最終目的地）及び探索条件などを指定、入力する。これに応じて、ＣＰＵ２２は、経路探索のための出発地及び目的地を決定する（ステップＳ２０）。通常、ナビゲーション装置２００を搭載した車両の自車位置が出発地に設定される。なお、ＰＣなどの端末装置が経路探索装置となる場合には、ユーザが出発地を指定する場合もある。
【００６７】
次に、ＣＰＵ２２は、図８（Ｂ）に例示する探索テーブルを参照して、決定された出発地と目的地の組合せに対応する探索用ブロックデータを決定し（ステップＳ２１）、それらの探索用ブロックデータを用いて、出発地から目的地へ至る複数の経路候補を算出する（ステップＳ２２）。
【００６８】
こうして、出発地から目的地へ至る複数の候補経路が得られると、ＣＰＵ２２は各候補経路についてコスト計算を行い、最小コストを有する候補経路を決定してユーザに提示する（ステップＳ２３）。こうして、経路探索処理が終了する。なお、コスト計算とは、経路計算において一般的に用いられる手法であり、リンク及びノードに予め対応付けされたコストの合計を計算することをいう。リンク及びノードに対応付けされたコストの値は、そのリンクやノードを通過する際に要する時間、道路の車線数などの各種の情報に基づいて予め設定されている。なお、コスト計算は既知の手法であるので、その詳細な説明は省略する。
【００６９】
なお、上記の例では、出発地と目的地を含むブロックについても、探索用ブロックデータを用いて経路探索を実行している。その代わりに、出発地及び目的地を含むブロックについては、探索用ブロックデータよりも細かいリンクを含むリンクデータを用いて、経路探索を行うこととしてもよい。これにより、出発地及び目的地と、高速道路や主要幹線道路との間において、小さい道路を含む多数の道路を考慮して適切な経路を設定することができる。
【図面の簡単な説明】
【００７０】
【図１】本発明の実施例において使用する地図データの構成を模式的に示す。
【図２】経路探索用データの構成例を示す。
【図３】リンク及びノードを説明する図である。
【図４】探索用全体データの例を示す。
【図５】探索用全体データの他の例を示す。
【図６】探索用ブロックデータの統合方法を説明する図である。
【図７】探索用ブロックデータ作成処理のフローチャートである。
【図８】探索用ブロックデータ及び探索テーブルの例である。
【図９】出発地と目的地の組合せに対応する探索用ブロックデータの例を示す。
【図１０】出発地と目的地の組合せに対応する探索用ブロックデータの例を示す。
【図１１】実施例によるナビゲーション装置の構成を示すブロック図である。
【図１２】経路探索処理のフローチャートである。
【符号の説明】
【００７１】
１０ 自立測位装置
１８ ＧＰＳ受信機
２０ システムコントローラ
２２ ＣＰＵ
３６ データ記憶ユニット
４０ 表示ユニット
６０ 入力装置
１２０ 地図データ
１２２ 地図表示用データ
１２４ 経路探索用データ
１２５ ノードデータ
１２７ 探索用テーブル
１２８ 探索用ブロックデータ
２００ ナビゲーション装置
【特許請求の範囲】
【請求項１】
地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶した記憶部と、
前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段と、を備えることを特徴とする経路探索装置。
【請求項２】
１つのブロックに対応して用意された複数の探索用ブロックデータの各々は、当該１つのブロックに対応して用意された他の探索用ブロックデータとの間で共通するリンク数が所定割合以下であることを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記記憶部は、前記所定のブロック毎に用意され、当該ブロック内に存在する全てのリンクを示すリンクデータを記憶しており、
前記経路探索手段は、前記出発地及び前記目的地が属するブロックについては、前記リンクデータを用いて経路探索を行うことを特徴とする請求項１又は２に記載の経路探索装置。
【請求項４】
地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶部に記憶する記憶工程と、
前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索工程と、を備えることを特徴とする経路探索方法。
【請求項５】
記憶部及びコンピュータを備える端末装置において実行される経路探索プログラムであって、
地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを前記記憶部に記憶する記憶手段、及び、
前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段、として前記コンピュータを機能させることを特徴とする経路探索プログラム。
【請求項６】
請求項５に記載の経路探索プログラムを記憶したことを特徴とする記憶媒体。
【請求項７】
地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶した記憶媒体。
【請求項８】
前記経路探索用データは、複数のレイヤからなる階層構造を有しており、
前記探索用ブロックデータ及び前記探索テーブルは、前記複数のレイヤのうち少なくとも最上位のレイヤの前記経路探索用データに含まれていることを特徴とする請求項７に記載の記憶媒体。
【請求項９】
前記経路探索用データは、複数のレイヤからなる階層構造を有しており、
前記複数のレイヤの前記経路探索用データは、所定範囲内に存在する前記出発地と目的地の組合せについてのみ、前記探索用ブロックデータ及び前記探索テーブルを含んでいることを特徴とする請求項７に記載の記憶媒体。
【請求項１０】
出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段と、
前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段と、
同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段と、
前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段と、を備えることを特徴とする探索用データ作成装置。
【請求項１１】
出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成工程と、
前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割工程と、
同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合工程と、
前記統合工程による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力工程と、を備えることを特徴とする探索用データ作成方法。
【請求項１２】
コンピュータを備える端末装置において実行される探索用データ作成プログラムであって、
出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段、
前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段、
同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段、及び、
前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段、として前記コンピュータを機能させることを特徴とする探索用データ作成プログラム。
【請求項１】
地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶した記憶部と、
前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段と、を備えることを特徴とする経路探索装置。
【請求項２】
１つのブロックに対応して用意された複数の探索用ブロックデータの各々は、当該１つのブロックに対応して用意された他の探索用ブロックデータとの間で共通するリンク数が所定割合以下であることを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記記憶部は、前記所定のブロック毎に用意され、当該ブロック内に存在する全てのリンクを示すリンクデータを記憶しており、
前記経路探索手段は、前記出発地及び前記目的地が属するブロックについては、前記リンクデータを用いて経路探索を行うことを特徴とする請求項１又は２に記載の経路探索装置。
【請求項４】
地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶部に記憶する記憶工程と、
前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索工程と、を備えることを特徴とする経路探索方法。
【請求項５】
記憶部及びコンピュータを備える端末装置において実行される経路探索プログラムであって、
地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを前記記憶部に記憶する記憶手段、及び、
前記探索テーブルを参照して、出発地及び目的地の組合せに対応する前記探索用ブロックデータを決定し、決定された前記探索用ブロックデータを用いて経路探索を行う経路探索手段、として前記コンピュータを機能させることを特徴とする経路探索プログラム。
【請求項６】
請求項５に記載の経路探索プログラムを記憶したことを特徴とする記憶媒体。
【請求項７】
地理上の所定のブロック毎に１つ又は複数用意され、経路探索に用いるリンクを示す探索用ブロックデータと、出発地と目的地の組合せ毎に用意され、当該出発地から当該目的地への経路探索に使用すべき前記探索用ブロックデータを特定する探索テーブルと、を含む経路探索用データを記憶した記憶媒体。
【請求項８】
前記経路探索用データは、複数のレイヤからなる階層構造を有しており、
前記探索用ブロックデータ及び前記探索テーブルは、前記複数のレイヤのうち少なくとも最上位のレイヤの前記経路探索用データに含まれていることを特徴とする請求項７に記載の記憶媒体。
【請求項９】
前記経路探索用データは、複数のレイヤからなる階層構造を有しており、
前記複数のレイヤの前記経路探索用データは、所定範囲内に存在する前記出発地と目的地の組合せについてのみ、前記探索用ブロックデータ及び前記探索テーブルを含んでいることを特徴とする請求項７に記載の記憶媒体。
【請求項１０】
出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段と、
前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段と、
同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段と、
前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段と、を備えることを特徴とする探索用データ作成装置。
【請求項１１】
出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成工程と、
前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割工程と、
同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合工程と、
前記統合工程による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力工程と、を備えることを特徴とする探索用データ作成方法。
【請求項１２】
コンピュータを備える端末装置において実行される探索用データ作成プログラムであって、
出発地及び目的地の組合せに対して、当該出発地から当該目的地までの経路探索に使用すべき全てのリンクを含む探索用全体データを作成する探索用全体データ作成手段、
前記探索用全体データを、地理上の所定のブロック毎に分割して探索用ブロックデータを作成する分割手段、
同一のブロックに対応する複数の前記探索用ブロックデータのうち、類似する探索用ブロックデータを１つに統合する統合手段、及び、
前記統合手段による統合処理後の前記探索用ブロックデータを、探索用データとして出力する出力手段、として前記コンピュータを機能させることを特徴とする探索用データ作成プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００８−１４５１９３（Ｐ２００８−１４５１９３Ａ）
【公開日】平成２０年６月２６日（２００８．６．２６）
【国際特許分類】
【出願番号】特願２００６−３３０９４８（Ｐ２００６−３３０９４８）
【出願日】平成１８年１２月７日（２００６．１２．７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００５０１６）パイオニア株式会社 (3,620)
【Ｆターム（参考）】
【公開日】平成２０年６月２６日（２００８．６．２６）
【国際特許分類】
【出願日】平成１８年１２月７日（２００６．１２．７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００５０１６）パイオニア株式会社 (3,620)
【Ｆターム（参考）】
[ Back to top ]