(57)【要約】【課題】経路計算用データのデータ量を過度に増大させることなく、遠距離の経路計算を高速化する。【解決手段】経路探索に使用される経路計算用データは、ノードデータ及びリンクデータに加え、経路計算フラグを含む。経路計算フラグは、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す。経路計算フラグは、例えば、出発地と目的地の組合せに対して付与された組合せＩＤ毎に、経路計算に使用することを示す値「１」と経路計算に使用しないことを示す値「０」のいずれかを設定したデータとすることができる。経路計算手段は、特定の出発地から特定の目的地への経路計算において、前記経路計算フラグを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う。【選択図】図７
2008122266.tif 000002
【特許請求の範囲】
【請求項１】
道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを記憶する記憶部と、
特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算手段と、を備えることを特徴とする経路探索装置。
【請求項２】
前記経路計算データは、リンク毎に用意され、出発地と目的地の複数の組合せの各々について、各リンクを使用するか否かを示すフラグであることを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記経路計算データは、ノード毎に用意され、出発地と目的地の複数の組合せの各々について、各ノードを使用するか否かを示すフラグであることを特徴とする請求項１に記載の経路探索装置。
【請求項４】
前記経路計算データは、出発地と目的地の組合せ毎に、経路計算に使用するリンク又はノードのＩＤを集めたデータとして構成されることを特徴とする請求項１に記載の経路探索装置。
【請求項５】
道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを記憶部に記憶する記憶工程と、
特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算工程と、を備えることを特徴とする経路探索方法。
【請求項６】
記憶部と、コンピュータと、を備える端末装置において実行される経路探索プログラムであって、
道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを前記記憶部に記憶する記憶手段、及び、
特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算手段、として前記コンピュータを機能させることを特徴とする経路探索プログラム。
【請求項７】
道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを記憶したことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データを利用する経路探索手法に関する。
【背景技術】
【０００２】
カーナビゲーション装置、インターネットを利用した地図提供アプリケーションなどには経路探索機能が設けられている。経路探索機能は地理上の出発地から目的地に至る経路を、地図データを利用して自動計算し、ユーザに提示する機能である。
【０００３】
一般的に、遠距離の経路計算は、候補となる道路数が多くなるため時間を要する。通常、経路計算用データは階層構造となっており、遠距離の経路計算では、主要道路のみを含むデータを使用することにより、計算の高速化を図っている。しかし、主要道路に限っても、全国的には相当数の道路リンクが存在する。よって、複数の県を経由するような遠距離経路の計算においては、主要道路の道路リンク全てを計算の対象とするため、膨大な計算量が要求される。
【０００４】
遠距離の経路計算を高速に行うために、経路計算用データ中に、通常のノード及びリンクのデータ以外に特殊なデータを含める手法が知られている。例えば、出発地のエリアと目的地のエリアの組合せに対して、その間の経路計算に必要なリンクのみを格納したデータを用意し、これを用いて経路計算を行う手法が知られている。
【０００５】
また、特許文献１には以下のような手法が提案されている。まず、地図上の地域を複数の探索区画に分割し、各探索区画に対して、一般的な使用が予想される高速道路や国道などの候補道路、及び、その候補道路への接続点（出入口）を予め決めて記憶しておく。経路計算時には、始点及び終点を含む探索区画に対応する候補道路及びその候補道路への接続点を呼び出し、候補道路のみを用いて経路計算を行う。
【０００６】
【特許文献１】特開平１１−６４０２３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、上記のような手法では、経路計算用データに含まれる特殊データの量が大きくなってしまう。また、道路の変更に応じて経路計算用データの更新が必要となった場合に、更新すべきデータ量も増大する。
【０００８】
本発明が解決しようとする課題としては、上記のものが一例として挙げられる。本発明は、経路計算用データのデータ量を過度に増大させることなく、遠距離の経路計算を高速化することを課題とする。
【課題を解決するための手段】
【０００９】
請求項１に記載の発明は、経路探索装置であって、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを記憶する記憶部と、特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算手段と、を備えることを特徴とする。
【００１０】
請求項４に記載の発明は、経路探索方法であって、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを記憶部に記憶する記憶工程と、特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算工程と、を備えることを特徴とする。
【００１１】
請求項５に記載の発明は、記憶部と、コンピュータと、を備える端末装置において実行される経路探索プログラムであって、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを前記記憶部に記憶する記憶手段、及び、特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算手段、として前記コンピュータを機能させることを特徴とする。
【００１２】
請求項６に記載の発明は、記憶媒体であって、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを記憶したことを特徴とする。
【発明を実施するための最良の形態】
【００１３】
本発明の好適な実施形態では、経路探索装置は、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを記憶する記憶部と、特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算手段と、を備えることを特徴とする。
【００１４】
上記の経路探索装置は、ナビゲーション装置、又は、インターネット又は記憶媒体上の地図データを利用して経路探索を行うＰＣなどの端末装置として構成することができる。経路探索に使用される地図データは、ノードデータ及びリンクデータに加え、経路計算データを含む。経路計算データは、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す。経路計算データは、例えば、出発地と目的地の組合せに対して付与された組合せＩＤ毎に、経路計算に使用することを示す値「１」と経路計算に使用しないことを示す値「０」のいずれかを設定したフラグとすることができる。経路計算手段は、特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う。
【００１５】
この経路探索装置によれば、経路計算に使用するリンク又はノードを示す経路計算データをリンクデータ又はノードデータと対応付けて記憶すればよいので、通常のリンクデータとは別個に経路計算専用のリンクデータなどを記憶する場合と比較して、地図データのデータ量を必要以上に増加させることなく、迅速な経路計算が可能となる。
【００１６】
上記の経路探索装置の好適な例では、前記経路計算データは、リンク毎に用意され、出発地と目的地の複数の組合せの各々について、各リンクを使用するか否かを示すフラグとすることができる。また、他の好適な例では、前記経路計算データは、ノード毎に用意され、出発地と目的地の複数の組合せの各々について、各ノードを使用するか否かを示すフラグとすることができる。
【００１７】
上記の経路探索装置の他の好適な例では、前記経路計算データは、出発地と目的地の組合せ毎に、経路計算に使用するリンク又はノードのＩＤを集めたデータとすることができる。
【００１８】
本発明の他の実施形態では、経路探索方法は、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを記憶部に記憶する記憶工程と、特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算工程と、を備える。
【００１９】
この経路探索方法によれば、経路計算に使用するリンク又はノードを示す経路計算データをリンクデータ又はノードデータと対応付けて記憶すればよいので、通常のリンクデータとは別個に経路計算専用のリンクデータなどを記憶する場合と比較して、地図データのデータ量を必要以上に増加させることなく、迅速な経路計算が可能となる。
【００２０】
本発明の他の実施形態では、記憶部と、コンピュータと、を備える端末装置において実行される経路探索プログラムは、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データを前記記憶部に記憶する記憶手段、及び、特定の出発地から特定の目的地への経路計算において、前記経路計算データを参照して当該出発地から当該目的地への経路計算に使用すべきリンク又はノードを決定し、決定されたリンク又はノードを用いて経路計算を行う経路計算手段、として前記コンピュータを機能させる。
【００２１】
上記の経路探索プログラムを、端末装置のコンピュータが実行することにより、上記の経路探索装置を実現することができる。
【００２２】
本発明の他の実施形態では、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、リンク又はノード毎に用意され、出発地から目的地への経路計算において当該リンク又はノードを使用するか否かを示す経路計算データと、を含む地図データが記憶媒体に記憶される。
【００２３】
この記憶媒体に記憶された地図データを利用することにより、通常のリンクデータとは別個に経路計算専用のリンクデータなどを記憶する場合と比較して、地図データのデータ量を必要以上に増加させることなく、迅速な経路計算が可能となる。
【実施例】
【００２４】
以下、図面を参照して本発明の好適な実施例について説明する。
【００２５】
［地図データ］
図１に、本実施例において使用する地図データの構成を模式的に示す。地図データは、異なる複数の縮尺に対応する複数のレイヤを含む階層構造に構成されている。図１は説明の便宜上、３階層の地図データを例示しているが、地図データはより多数の階層構造としてもよい。図１において、レイヤ３は最上位レイヤであり、最も広域の地図に対応する。レイヤ１は最下位レイヤであり、最も詳細な地図に対応する。各レイヤにおいて、地図データの１つの単位を「ブロック（Ｂ）」と呼ぶ。なお、「ブロック」は地理上の広がりを持った範囲を示す概念であり、「パーセル」、「メッシュ」などと表現されることもある。
【００２６】
地図データ１２０は、各レイヤ毎に別個に用意されており、それぞれ地図表示用データ１２２と、経路計算用データ１２４とを含む。地図表示用データ１２２は、ユーザに対して地図画像を表示するために使用されるデータであり、主として地図に対応する画像データを含む。経路計算用データ１２４は、経路探索機能による経路計算に使用されるデータである。
【００２７】
図２に経路計算用データの構成を示す。経路計算用データ１２４は、ノードデータ１２５及びリンクデータ１２６を含む。ノードは道路上の交差点などの所定の地点に対応し、ノードデータ１２５はノードを示すデータである。一方、リンクは交差点などにより区切られた道路の１区画に対応し、リンクデータ１２６はリンクを示すデータである。
【００２８】
ノード及びリンクの例を図４（Ａ）及び４（Ｂ）に示す。図４（Ａ）に示す複数の道路１１１を含む地図は、図４（Ｂ）に示すように複数のノード及びリンクにより構成される。なお、図４（Ｂ）においては、各ノードをノードＩＤ（Ｎ００００１など）で示し、各リンクをリンクＩＤ（Ｌ００００１など）で示している。
【００２９】
図３にリンクデータの構成を示す。リンクデータ１２６は、各リンクに対応するリンクＩＤ毎に、そのリンクに対応する道路の属性を示すリンク属性、及び、経路計算フラグを含む。リンク属性は、例えば対応する道路の道路種別、幅員、座標、長さなどを含む。経路計算フラグは、経路計算において使用されるフラグであり、当該リンクＩＤに対応するリンクが、特定の出発地から特定の目的地への経路計算において使用されるか否かを示している。なお、経路計算フラグは本発明における経路計算データの一例である。
【００３０】
経路計算フラグについて図５を用いて詳細に説明する。経路計算フラグは、出発地と目的地の複数の組合せについて、当該出発地から当該目的地への経路計算において、そのリンクを使用するか否かを示す。図５（Ａ）は、出発地と目的地の複数の組合せを示す組合せテーブルの例を示す。図５（Ａ）に示すように、出発地と目的地の複数の組合せに対して、組合せＩＤが付与されている。出発地と目的地の組合せは、後述のカーナビゲーション装置などにおいて必要とされる出発地と目的地の数だけ用意される。なお、以下の説明では、出発地及び目的地は、説明の便宜上、「東京」、「札幌」などの都市名を使用しているが、実際の地図データ上では、東京、札幌などを含むエリア同士の組合せに対して経路計算フラグが設定される。即ち、地図データ上では、組合せＩＤ１は、東京を含むエリアと福岡を含むエリアとの組合せを指す。
【００３１】
図５（Ｂ）に経路計算フラグの例を示す。この例では、経路計算フラグは、リンクＩＤ毎に用意され、組合せＩＤが示す出発地と目的地の組合せについての経路計算において各リンクが使用されるか否かを示している。具体的に、経路計算フラグは、その値が「１」であるときに経路計算に使用されることを示し、その値が「０」であるときに経路計算に使用されないことを示す。例えば図５（Ｂ）の例において、リンク番号Ｌ００００１のリンクについて、組合せＩＤ「１」に対応する経路計算フラグは「１」であるから、組合せＩＤ「１」に対応する出発地「東京」から目的地「福岡」への経路計算においては、リンク番号Ｌ００００１のリンクは使用されることになる。同様に、リンク番号Ｌ００００１のリンクについて、組合せＩＤ「２」に対応する経路計算フラグは「０」であるから、組合せＩＤ「２」に対応する出発地「東京」から目的地「高知」への経路計算においては、リンク番号Ｌ００００１のリンクは使用されないことになる。
【００３２】
このように、経路計算フラグは、各リンクについて、特定の出発地から特定の目的地への経路計算において当該リンクを使用するか否かを示している。よって、経路計算時において、出発地及び目的地が決定されると、図５（Ｂ）を参照することにより、その出発地から目的地への経路計算において使用するリンクを特定することができる。よって、本実施例の経路計算フラグを利用することにより、全ての道路に対応するリンクが含まれるリンクデータに基づいて経路計算を行うよりも非常に少ない演算量で迅速に経路計算を行うことができる。
【００３３】
なお、通常のリンクデータを用いて経路計算を行う場合と比較すると、本実施例では、上記の経路計算フラグという別個のデータを用意し記憶することが必要となる。しかし、図５（Ｂ）から理解されるように、経路計算フラグは、「０」、「１」のフラグであり、１ビットで示すことができる。よって、経路計算フラグは、各リンクに対して出発地と目的地の組合せの数に相当するビット数の情報量で足りることになり、通常のリンクデータとは別個に経路計算専用のリンクデータなどを記憶する手法と比較して、増加するデータ量は非常に小さくてすむ。
【００３４】
なお、実際の経路計算フラグの記憶の方法はいくつかある。第１の方法は、図３に示すように、各リンクＩＤに対応する経路計算フラグを、当該リンクのリンクデータ内に収容する。なお、図３の例では、リンクＩＤＬ００００１に対応する経路計算フラグの内容は図５（Ｂ）の第１行に示すリンクＩＤＬ００００１の経路計算データとなる。この方法では、１つのリンクに関連するリンク属性などの情報と経路計算フラグとを１つのデータとして管理することができる。
【００３５】
第２の方法は、第１の方法のようにリンクデータ内に経路計算フラグを含めるのではなく、リンクデータと経路計算フラグとを別個のデータとして記憶、管理する。この場合、リンクデータ自体は、リンクＩＤとリンク属性のみを含むこととなり、そのリンクデータとは別個に、図５（Ｂ）に例示するような経路計算フラグテーブルを記憶することになる。この第２の方法では、地理上の道路（リンク）に変更が生じてリンクデータを更新する際に更新処理が楽になるという利点がある。例えば、新規道路が１つできた場合、リンクデータ自体はその新規道路に対応するリンクのリンクデータを増加すればよい。これに対し、経路経路計算フラグはその新規道路の発生に応じて更新すべき対象が複数のリンクや出発地と目的地の組合せに及ぶので、経路計算フラグテーブル自体を新規に作成し直す方が効率的である場合が多い。第２の方法では、このように、リンクデータ自体と、経路計算フラグテーブルとを独立して必要な更新を行うことができるという利点がある。
【００３６】
なお、図１に示すように、経路計算用データ１２４は複数のレイヤ毎に用意されているが、通常、経路計算フラグは最上位のレイヤのみに用意すれば足りる。
【００３７】
［ナビゲーション装置］
図６に、本発明の実施例に係るナビゲーション装置２００の構成を示す。図６に示すように、ナビゲーション装置２００は、自立測位装置１０、ＧＰＳ受信機１８、システムコントローラ２０、ディスクドライブ３１、データ記憶ユニット３６、通信用インタフェース３７、通信装置３８、表示ユニット４０、音声出力ユニット５０及び入力装置６０を備える。
【００３８】
自立測位装置１０は、加速度センサ１１、角速度センサ１２及び距離センサ１３を備える。加速度センサ１１は、例えば圧電素子からなり、車両の加速度を検出し、加速度データを出力する。角速度センサ１２は、例えば振動ジャイロからなり、車両の方向変換時における車両の角速度を検出し、角速度データ及び相対方位データを出力する。距離センサ１３は、車両の車輪の回転に伴って発生されているパルス信号からなる車速パルスを計測する。
【００３９】
ＧＰＳ受信機１８は、複数のＧＰＳ衛星から、測位用データを含む下り回線データを搬送する電波１９を受信する。測位用データは、緯度及び経度情報等から車両の絶対的な位置を検出するために用いられる。
【００４０】
システムコントローラ２０は、インタフェース２１、ＣＰＵ２２、ＲＯＭ２３及びＲＡＭ２４を含んでおり、ナビゲーション装置２００全体の制御を行う。
【００４１】
インタフェース２１は、加速度センサ１１、角速度センサ１２及び距離センサ１３並びにＧＰＳ受信機１８とのインタフェース動作を行う。そして、これらから、車速パルス、加速度データ、相対方位データ、角速度データ、ＧＰＳ測位データ、絶対方位データ等をシステムコントローラ２０に入力する。ＣＰＵ２２は、システムコントローラ２０全体を制御する。ＲＯＭ２３は、システムコントローラ２０を制御する制御プログラム等が格納された図示しない不揮発性メモリ等を有する。ＲＡＭ２４は、入力装置６０を介して使用者により予め設定された経路データ等の各種データを読み出し可能に格納したり、ＣＰＵ２２に対してワーキングエリアを提供したりする。
【００４２】
システムコントローラ２０、ＣＤ−ＲＯＭドライブ又はＤＶＤ−ＲＯＭドライブなどのディスクドライブ３１、データ記憶ユニット３６、通信用インタフェース３７、表示ユニット４０、音声出力ユニット５０及び入力装置６０は、バスライン３０を介して相互に接続されている。
【００４３】
ディスクドライブ３１は、システムコントローラ２０の制御の下、ＣＤ又はＤＶＤといったディスク３３から、音楽データ、映像データなどのコンテンツデータを読み出し、出力する。なお、ディスクドライブ３１は、ＣＤ−ＲＯＭドライブ又はＤＶＤ−ＲＯＭドライブのうち、いずれか一方としてもよいし、ＣＤ及びＤＶＤコンパチブルのドライブとしてもよい。
【００４４】
データ記憶ユニット３６は、例えば、ＨＤＤなどにより構成され、地図データや施設データなどのナビゲーション処理に用いられる各種データを記憶する。
【００４５】
通信装置３８は、例えば、ＦＭチューナやビーコンレシーバ、携帯電話や専用の通信カードなどにより構成され、通信用インタフェース３７を介して、ＶＩＣＳ（Ｖｅｈｉｃｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ）センタから配信される渋滞や交通情報などの道路交通情報、その他の情報を受信する。
【００４６】
表示ユニット４０は、システムコントローラ２０の制御の下、各種表示データをディスプレイなどの表示装置に表示する。具体的には、システムコントローラ２０は、データ記憶ユニット３６から地図データを読み出す。表示ユニット４０は、システムコントローラ２０によってデータ記憶ユニット３６から読み出された地図データを、ディスプレイなどの表示画面上に表示する。表示ユニット４０は、バスライン３０を介してＣＰＵ２２から送られる制御データに基づいて表示ユニット４０全体の制御を行うグラフィックコントローラ４１と、ＶＲＡＭ（Ｖｉｄｅｏ  ＲＡＭ）等のメモリからなり即時表示可能な画像情報を一時的に記憶するバッファメモリ４２と、グラフィックコントローラ４１から出力される画像データに基づいて、液晶、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）等のディスプレイ４４を表示制御する表示制御部４３と、ディスプレイ４４とを備える。ディスプレイ４４は、例えば対角５〜１０インチ程度の液晶表示装置等からなり、車内のフロントパネル付近に装着される。
【００４７】
音声出力ユニット５０は、システムコントローラ２０の制御の下、ＣＤ−ＲＯＭドライブ３１又はＤＶＤ−ＲＯＭ３２、若しくはＲＡＭ２４等からバスライン３０を介して送られる音声デジタルデータのＤ／Ａ変換を行うＤ／Ａコンバータ５１と、Ｄ／Ａコンバータ５１から出力される音声アナログ信号を増幅する増幅器（ＡＭＰ）５２と、増幅された音声アナログ信号を音声に変換して車内に出力するスピーカ５３とを備えて構成されている。
【００４８】
入力装置６０は、各種コマンドやデータを入力するための、キー、スイッチ、ボタン、リモコン、音声入力装置等から構成されている。入力装置６０は、車内に搭載された当該車載用電子システムの本体のフロントパネルやディスプレイ４４の周囲に配置される。また、ディスプレイ４４がタッチパネル方式である場合には、ディスプレイ４４の表示画面上に設けられたタッチパネルも入力装置６０として機能する。
【００４９】
なお、ＣＰＵ２２は、予めＲＯＭ２３などに記憶された経路探索プログラムを実行することにより、経路計算手段として機能する。また、図１に例示する地図データは、データ記憶ユニット３６に記憶される。
【００５０】
［経路探索処理］
次に、経路探索処理について説明する。図７に経路探索処理のフローチャートを示す。なお、実際には、ＣＰＵ２２が経路探索プログラムを実行することにより、ナビゲーション装置２００が経路探索装置として動作し、経路探索処理を実行する。
【００５１】
まず、経路探索を行うユーザは、ナビゲーション装置２００の入力装置６０を使用して、経路探索機能を呼び出し、目的地を指定、入力する。これに応じて、ＣＰＵ２２は、経路探索のための出発地及び目的地を決定する（ステップＳ１０）。通常、ナビゲーション装置２００を搭載した車両の自車位置が出発地に設定される。なお、ＰＣなどの端末装置が経路探索装置となる場合には、ユーザが出発地を指定する場合もある。
【００５２】
次に、ＣＰＵ２２は、図３に示す各リンクデータ内の経路計算フラグ又は図５（Ｂ）に示す経路計算フラグテーブルを参照し、ステップＳ１０で決定された出発地と目的地の経路計算に使用するリンクを特定する（ステップＳ１１）。そして、ＣＰＵ２２は、特定したリンクを用いて、目的地までの候補経路を計算する（ステップＳ１２）。出発地から目的地へ至る複数の候補経路が得られると、ＣＰＵ２２は各候補経路についてコスト計算を行い、最小コストを有する候補経路を決定してユーザに提示する（ステップＳ１３）。こうして、経路探索処理が終了する。
【００５３】
なお、コスト計算とは、経路計算において一般的に用いられる手法であり、リンク及びノードに予め対応付けされたコストの合計を計算することをいう。リンク及びノードに対応付けされたコストの値は、そのリンクやノードを通過する際に要する時間、道路の車線数などの各種の情報に基づいて予め設定されている。なお、コスト計算は既知の手法であるので、その詳細な説明は省略する。
【００５４】
図８に、経路探索処理の他のフローチャートを示す。まず、経路探索を行うユーザは、ナビゲーション装置２００の入力装置６０を使用して、経路探索機能を呼び出し、目的地を指定、入力する。これに応じて、ＣＰＵ２２は、経路探索のための出発地及び目的地を決定する（ステップＳ２０）。
【００５５】
次に、ＣＰＵ２２は、図３に示す各リンクデータ内の経路計算フラグ又は図５（Ｂ）に示す経路計算フラグテーブルを参照し、ステップＳ１０で決定された出発地と目的地の経路計算に使用するリンクを、出発地から目的地へ向かって順に１つずつ特定し、目的地までの候補経路を計算する（ステップＳ２１）。こうして、出発地から目的地へ至る複数の候補経路が得られると、ＣＰＵ２２は各候補経路についてコスト計算を行い、最小コストを有する候補経路を決定してユーザに提示する（ステップＳ２２）。こうして、経路探索処理が終了する。
【００５６】
次に、図９を参照して本発明の経路計算フラグを用いた経路計算手法の利点を説明する。図９（Ａ）、（Ｂ）はある出発地から目的地への経路計算に使用すべきリンクを予め計算し、出発地と目的地の組合せ毎に記憶する手法（以下、「比較例の手法」と呼ぶ。）により用意された経路計算用データ（以下、「経路計算専用リンクデータ」とも呼ぶ）を示す。図９（Ａ）は出発地Ｘ１から目的地Ｙ１への経路計算専用リンクデータの例を示し、図９（Ｂ）は出発地Ｘ２から目的地Ｙ２の経路計算専用リンクデータの例を示す。比較例の手法では、出発地と目的地の組合せに対して、その出発地から目的地への経路計算に使用する全てのリンクを示した経路計算専用リンクデータを１つ用意する。よって、経路計算時には、その経路計算専用リンクデータ１つを読み出し、経路計算を行えばよい。しかしながら、そのような経路計算専用リンクデータを出発地と目的地の組合せ数だけ用意する必要があるので、経路計算専用リンクデータの全データ量は膨大となる。また、この経路計算専用リンクデータに含まれるリンクデータは通常のリンクデータにも含まれており、実質的に同じリンクデータを重複して保持することとなる。
【００５７】
これに対し、本実施例の手法では、各ブロック毎に用意されたリンクデータに含まれる各リンクについて、特定の出発地から特定の目的地への経路計算に使用するか否かをフラグとして記憶している。図９（Ｃ）、（Ｄ）はその例を示す。図９（Ｃ）及び９（Ｄ）はもともと同じデータであり、出発地Ｘ１、目的地Ｙ１に着目したものが図９（Ｃ）であり、出発地Ｘ２、目的地Ｙ２に着目したものが図９（Ｄ）である。図中の実線のリンクは経路計算フラグが「０」であるリンク（即ち、経路計算に使用しないリンク）、破線のリンクは経路計算フラグが「１」であるリンク（即ち、経路計算に使用するリンク）である。
【００５８】
このように、本実施例の手法では、リンクデータ中の各リンクについて経路計算フラグを設定するだけで良い。また、経路計算時には、同じリンクデータを使用し、その中から、経路計算フラグを参照して出発地と目的地との間の経路計算に使用するリンクを抽出して経路計算を行えばよい。
【００５９】
また、本実施例による経路計算手法として第１及び第２の方法を例示したが、図８に示す第２の手法を使用する場合には、出発地から順に１つずつリンクをたどりながら経路計算を行うので、例えば図９（Ｄ）の例のような場合には、経路計算フラグが「１」となっているリンク（即ち、破線で示すリンク）を含まないブロックＢ１、Ｂ２、Ｂ３のリンクデータは、結果的に参照する必要はなく、メモリなどに読み込む必要もない。これにより、経路探索処理が効率化、迅速化される。
【００６０】
なお、上記の比較例の手法では、出発地と目的地の組合せ毎に、経路計算に使用するリンクのリンクデータを含む経路計算専用リンクデータを作成している。このため、前述のように、経路計算時には、その経路計算専用リンクデータ１つを読み出し、経路計算を行えばよいという利点がある。出発地と目的地の組合せ毎に経路計算専用リンクデータのような経路計算専用に使用するデータを用意したい場合には、本実施例の経路計算フラグと同内容の経路計算データを出発地と目的地の組合せ毎に用意すればよい。即ち、出発地と目的地との組合せ毎に、経路計算に使用するリンクのリンクＩＤの集合を求め、これを経路計算データとする。こうすれば、経路計算データの内容は、リンクＩＤの集合に過ぎないので、比較例の経路計算専用リンクデータのようにリンクデータ自体を保有する場合と比べて、データ量を格段に減少させることができる。
【００６１】
この場合、経路計算においては、ナビゲーション装置は、まず、リンクＩＤの集合である経路計算データを参照して出発地と目的地との組合せに対応するリンクを特定する。次に、それらのリンクに対応するリンクデータを参照し、経路計算を実行する。なお、リンクＩＤの集合は、リンクＩＤでソートしておけば、経路計算時に参照がしやすくなる。
【００６２】
［変形例］
上記の例では、経路計算フラグをリンク毎に用意し、図３に示すようにリンクデータ内に含めるか、若しくは図５（Ｂ）に示すように全てのリンクに対応する経路計算フラグを記述した経路計算フラグテーブルを作成した。その代わりに、経路計算フラグをノード毎に用意することも可能である。図１０に、経路計算フラグをノード毎に用意した場合のノードデータの例を示す。図１０に示すように、ノードデータ１２５は、各ノードを示すノードＩＤに対応付けて、当該ノードの位置座標と、経路計算フラグとを含む。経路計算フラグは、図５（Ｂ）に示すように、出発地と目的地の組合せを示す組合せＩＤ毎に、「０」又は「１」の値を有する。
【００６３】
この場合、実際の経路探索処理においては、出発地と目的地の組合せに基づいて、上記のノードデータ中の経路計算フラグを参照し、経路計算に使用するノードを特定して経路計算を実行すればよい。
【００６４】
なお、上記実施例は、本発明をカーナビゲーション装置に適用した例を示したが、本発明は、地図データを用いて経路を探索する機能を有する各種の端末装置に利用することができる。具体的には、カーナビゲーション装置の他、ウェブ上で経路探索サービスを提供するサーバ装置、ウェブ上のサーバからダウンロードした地図データ又はＤＶＤ−ＲＯＭなどの記憶媒体に記憶されている地図データを用いてＰＣ上で経路を計算するアプリケーションなどに利用することができる。
【図面の簡単な説明】
【００６５】
【図１】本発明の実施例において使用する地図データの構成を模式的に示す。
【図２】経路計算用データの構成例を示す。
【図３】実施例によるリンクデータの構成例を示す。
【図４】リンク及びノードを説明する図である。
【図５】実施例による経路計算フラグの構成例を示す。
【図６】本発明の経路計算装置の実施例であるナビゲーション装置の構成を示す。
【図７】経路探索処理のフローチャートである。
【図８】経路探索処理の他のフローチャートである。
【図９】実施例による手法と比較例による手法とを比較する図である。
【図１０】変形例によるノードデータの構成例を示す。
【符号の説明】
【００６６】
１０  自立測位装置
１８  ＧＰＳ受信機
２０  システムコントローラ
２２  ＣＰＵ
３６  データ記憶ユニット
４０  表示ユニット
６０  入力装置
１２０  地図データ
１２２  地図表示用データ
１２４  経路計算用データ
１２５  ノードデータ
１２６  リンクデータ
２００  ナビゲーション装置
【図１】
2008122266.tif 000003
【図２】
2008122266.tif 000004
【図３】
2008122266.tif 000005
【図４】
2008122266.tif 000006
【図５】
2008122266.tif 000007
【図６】
2008122266.tif 000008
【図７】
2008122266.tif 000009
【図８】
2008122266.tif 000010
【図９】
2008122266.tif 000011
【図１０】
2008122266.tif 000012