JP5016605B2 - 経路探索装置、経路探索方法、経路探索プログラム及び記憶媒体 - Google Patents

Description

本発明は、地図データを利用する経路探索手法に関する。

カーナビゲーション装置、インターネットを利用した地図提供アプリケーションなどには経路探索機能が設けられている。経路探索機能は地理上の出発地から目的地に至る経路を、地図データを利用して自動計算し、ユーザに提示する機能である。

一般的に、遠距離の経路計算は、候補となる道路数が多くなるため時間を要する。通常、経路計算用データは階層構造となっており、遠距離の経路計算では、主要道路のみを含むデータを使用することにより、計算の高速化を図っている。しかし、主要道路に限っても、全国的には相当数の道路リンクが存在する。よって、複数の県を経由するような遠距離経路の計算においては、主要道路の道路リンク全てを計算の対象とするため、膨大な計算量が要求される。

遠距離の経路計算を高速に行うために、経路計算用データ中に、通常のノード及びリンクのデータ以外に特殊なデータを含める手法が知られている。例えば、出発地のエリアと目的地のエリアの組み合わせに対して、その間の経路計算に必要なリンクのみを格納したデータを用意し、これを用いて経路計算を行う手法が知られている。

また、特許文献１には以下のような手法が提案されている。まず、地図上の地域を複数の探索区画に分割し、各探索区画に対して、一般的な使用が予想される高速道路や国道などの候補道路、及び、その候補道路への接続点（出入口）を予め決めて記憶しておく。経路計算時には、始点及び終点を含む探索区画に対応する候補道路及びその候補道路への接続点を呼び出し、候補道路のみを用いて経路計算を行う。

特開平１１−６４０２３号公報

しかし、上記のような手法では、経路計算用データに含まれる特殊データの量が大きくなってしまう。また、道路の変更に応じて経路計算用データの更新が必要となった場合に、更新すべきデータ量も増大する。

本発明が解決しようとする課題としては、上記のようなものが例として挙げられる。本発明は、経路計算用データのデータ量を過度に増大させることなく、遠距離の経路計算を高速化することを課題とする。

請求項１に記載の発明では、経路探索装置は、道路に対応するリンクを示すリンクデータと、前記道路上の所定の地点に対応するノードを示すノードデータと、を含む経路計算用データを記憶する記憶部と、前記経路計算用データを用いて、目的地までの経路計算を行う経路計算手段と、を備え、前記リンクデータによって示されるリンクは、当該リンクを通って到達するエリアの情報を有する候補リンクを含み、前記経路計算手段は、目的地に対応するエリアの情報を有する候補リンクが存在するノードについては当該目的地に対応するエリアの情報を有する候補リンクを対象とし、目的地に対応するエリアの情報を有する候補リンクが存在しないノードについては道なりのリンクを対象として、経路計算を行うことを特徴とする。

請求項５に記載の発明では、経路探索方法は、コンピュータを備える端末装置により実行される経路探索方法であって、道路に対応するリンクを示すリンクデータと、前記道路上の所定の地点に対応するノードを示すノードデータと、を含む経路計算用データを用いて、目的地までの経路計算を行う経路計算工程を備え、前記リンクデータによって示されるリンクは、当該リンクを通って到達するエリアの情報を有する候補リンクを含み、前記経路計算工程は、目的地に対応するエリアの情報を有する候補リンクが存在するノードについては当該目的地に対応するエリアの情報を有する候補リンクを対象とし、目的地に対応するエリアの情報を有する候補リンクが存在しないノードについては道なりのリンクを対象として、経路計算を行うことを特徴とする。

請求項６に記載の発明では、道路に対応するリンクを示すリンクデータと、前記道路上の所定の地点に対応するノードを示すノードデータと、を含む経路計算用データを記憶する記憶部と、コンピュータと、を備える端末装置において実行される経路探索プログラムは、前記経路計算用データを用いて、目的地までの経路計算を行う経路計算手段として前記コンピュータを機能させ、前記リンクデータによって示されるリンクは、当該リンクを通って到達するエリアの情報を有する候補リンクを含み、前記経路計算手段は、目的地に対応するエリアの情報を有する候補リンクが存在するノードについては当該目的地に対応するエリアの情報を有する候補リンクを対象とし、目的地に対応するエリアの情報を有する候補リンクが存在しないノードについては道なりのリンクを対象として、経路計算を行うことを特徴とする。

本発明の実施例において使用する地図データの構成を模式的に示す。 経路計算用データの構成例を示す。 ノードデータの構成例を示す。 リンク及びノードと、候補リンクデータとの関係を示す。 候補リンクデータの例を模式的に示す。 道なりのリンクの決定方法の例を示す。 中間目的地テーブルの例を示す。 実施例に係るナビゲーション装置の概略構成を示すブロック図である。 実施例による経路探索処理のフローチャートである。 実施例による経路探索の例を示す。 候補リンクデータの変形例を示す。

１２０ 地図データ
１２２ 地図表示用データ
１２４ 経路計算用データ
１２５ ノードデータ
１２６ リンクデータ
１３１、１３２ 候補リンクデータ
２００ ナビゲーション装置

本発明の１つの観点では、経路探索装置は、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを記憶する記憶部と、前記経路計算用データを用いて、経路計算を行う経路計算手段と、を備え、前記経路計算手段は、前記候補リンクデータが存在するノードについては当該候補リンクデータが示すリンクを対象とし、前記候補リンクデータが存在しないノードについては道なりのリンクを対象として経路計算を行う。

上記の経路探索装置は、ナビゲーション装置、又は、インターネット又は記憶媒体上の地図データを利用して経路探索を行うＰＣなどの端末装置として構成することができる。経路探索に使用される経路計算用データは、ノードデータ及びリンクデータに加え、ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータを含む。経路計算手段は、候補リンクデータが存在するノードについては当該候補リンクデータが示すリンクを対象とし、候補リンクデータが存在しないノードについては道なりのリンクを対象として経路計算を行う。

このように、経路計算においては道なりのリンクを選択することを原則とし、道なり以外のリンクを計算対象にする場合にのみ、それを示す候補リンクデータをノードに関連付けて用意する。よって、経路計算の高速化のために用意、記憶する候補リンクデータは必要なノードに対してのみ存在することとなり、そのデータ量を抑えることができる。また、経路計算手段は、候補リンクデータが存在しないノードについては、道なりのリンクのみを計算対象とすればよいので、迅速な計算が可能となる。

上記の経路探索装置の一態様では、前記候補リンクデータは探索条件毎に用意されており、前記経路計算手段は、ユーザが指定した探索条件に対応する候補リンクデータを用いて経路計算を行う。探索条件としては、例えば高速道路優先、高速道路回避、時間優先、距離優先などが挙げられる。探索条件毎に最適な経路が異なってくるので、候補リンクデータも探索条件毎に用意されることが好ましい。

上記の経路探索装置の他の一態様では、前記経路計算手段は、前記候補リンクデータが示すリンクのうち、目的地が示されているリンクのみを対象とする。候補リンクデータ中にリンクが示されていても、対応する目的地が示されていないリンクは、候補経路の計算対象から除外することにより、計算量を減らすことができる。

上記の経路探索装置の他の一態様では、前記経路計算用データは異なる縮尺に対応する複数のレイヤ毎に用意されており、前記候補リンクデータは、少なくとも最も広域の地図に対応するレイヤに対して用意されている。これにより、特に遠距離の経路探索において、広域の地図に含まれる高速道路や主要幹線道路上を利用した経路計算を高速化することができる。

上記の経路探索装置の他の一態様では、前記経路計算用データは、最終目的地と、当該最終目的地までの経路の途中に位置する中間目的地との対応を示す中間目的地テーブルを含み、前記経路計算手段は、前記最終目的地及び前記中間目的地を前記目的地として候補経路を計算する。経路計算用データにおいて、各リンクに対応して設定される目的地は多数存在するので、最終目的地と中間目的地の対応をテーブルとして記憶しておき、候補リンクデータには中間目的地を設定することにより、候補リンクデータのデータ量を低減することができる。

本発明の他の観点では、経路探索方法は、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを用いて、経路計算を行う経路計算工程を備え、前記経路計算工程は、前記候補リンクデータが存在するノードについては当該候補リンクデータが示すリンクを対象とし、前記候補リンクデータが存在しないノードについては道なりのリンクを対象として経路計算を行う。

この方法によっても、経路計算用データのデータ量を過度に増大させることなく、経路計算を高速化することができる。

本発明のさらに他の観点では、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを記憶する記憶部と、コンピュータと、を備える端末装置において実行される経路探索プログラムは、前記経路計算用データを用いて、経路計算を行う経路計算手段として前記コンピュータを機能させ、前記経路計算手段は、前記候補リンクデータが存在するノードについては当該候補リンクデータが示すリンクを対象とし、前記候補リンクデータが存在しないノードについては道なりのリンクを対象として経路計算を行う。

このプログラムを、端末装置上で実行することにより、本発明の経路計算装置を実現することができる。なお、端末装置とは、ナビゲーション装置、ＰＣなどを含む。

本発明のさらに他の観点では、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを記憶した記憶媒体が提供される。この記憶媒体から経路計算用データを取得することにより、迅速な経路計算が可能となる。

以下、図面を参照して本発明の好適な実施例について説明する。

［地図データ］
図１に、本実施例において使用する地図データの構成を模式的に示す。地図データは、異なる複数の縮尺に対応する複数のレイヤを含む階層構造に構成されている。図１は説明の便宜上、３階層の地図データを例示しているが、地図データはより多数の階層構造としてもよい。各レイヤにおいて、地図データの１つの単位をパーセルＰと呼ぶ。図１において、レイヤ３は最上位レイヤであり、最も広域の地図に対応する。レイヤ１は最下位レイヤであり、最も詳細な地図に対応する。

地図データ１２０は、各レイヤ毎に別個に用意されており、それぞれ地図表示用データ１２２と、経路計算用データ１２４とを含む。地図表示用データ１２２は、ユーザに対して地図画像を表示するために使用されるデータであり、主として地図に対応する画像データを含む。経路計算用データ１２４は、経路探索機能による経路計算に使用されるデータである。

図２に経路計算用データの構成を示す。経路計算用データ１２４は、ノードデータ１２５及びリンクデータ１２６を含む。ノードは道路上の交差点などの所定の地点に対応し、ノードデータ１２５はノードを示すデータである。一方、リンクは交差点などにより区切られた道路の１区画に対応し、リンクデータ１２６はリンクを示すデータである。

ノード及びリンクの例を図４（Ａ）及び４（Ｂ）に示す。図４（Ａ）に示す複数の道路１１１を含む地図は、図４（Ｂ）に示すように複数のノード及びリンクにより構成される。なお、図４（Ｂ）においては、各ノードをノードＩＤ（Ｎ００００１など）で示し、各リンクをリンクＩＤ（Ｌ００００１など）で示している。

図３にノードデータの構成を示す。ノードデータ１２５は、各ノードに対応するノードＩＤ毎に地理的な位置座標（緯度及び経度）を含む。また、いくつかのノードは、候補リンクデータを含む。候補リンクデータは候補リンクを示すデータである。ここで、候補リンクとは、経路計算において当該ノードを経由して目的地へ至る候補経路を計算する際に対象とすべきリンクを言う。

あるノードについて、候補リンクが存在するか否かは以下のように決定される。あるノードにおいて、特定の目的地へ至るリンクが道なりのリンクである場合には、候補リンクデータは用意されない。一方、特定の目的地へ進むために、道なり以外のリンクに進む必要がある場合には、そのリンクと目的地との関係を示すために候補リンクデータが用意される。従って、後述する経路計算処理においては、候補経路上に存在する各ノードについて、候補リンクデータが存在するか否かが判断され、存在しない場合には道なりのリンクのみを対象に候補経路が計算される。一方、候補リンクデータが存在する場合は、それが示す候補リンクを対象に候補経路が計算される。このように、経路計算においては、各ノードにおいて原則として道なりのリンクのみを経路計算の対象とし、例外として候補リンクデータが存在するノードについては当該候補リンクデータが示す候補リンクを経路計算の対象に含める。これにより、全てのノードについて、経路計算の対象となる候補リンクデータを用意し、記憶しておく必要が無くなり、経路計算の高速化のために予め用意、記憶すべき特殊データのデータ量を小さくすることができる。

具体的に、候補リンクデータは、各ノードに接続された候補リンクと、その候補リンクに対応する目的地との対応を示している。図３に示すノードＮ００００１における候補リンクデータを図５（Ａ）に示す。ノードＮ００００１においては、３つの進行可能な候補リンクＬ００１０１、Ｌ００１０２及びＬ００１０３がある。候補リンクＬ００１０１の目的地はエリアＡ（東京）であり、候補リンクＬ００１０２の目的地はエリアＢ（千葉）であり、候補リンクＬ００１０３の目的地はエリアＣ（横浜）である。

同様に、図３に示すノードＮ００００２における候補リンクデータを図５（Ｂ）に示す。ノードＮ００００１においては、２つの進行可能な候補リンクＬ００１０４及びＬ００１０５がある。候補リンクＬ００１０４の目的地はエリアＤであり、候補リンクＬ００１０２の目的地はエリアＥである。

なお、候補リンクデータにおいては、そのノードに接続された全ての候補リンクに対して目的地が設定されるわけではない。即ち、あるノードにおいては、当該ノードに接続された複数の候補リンクのうち、そのノードを経由する候補経路に含めるべき候補リンクのみに対して目的地が設定される。よって、該当する目的地が設定されていないリンクは、候補経路の計算対象から除外される。なお、目的地が設定されていないリンクは、一般的には、道なりのリンクが途中でとぎれており、その先に目的地が存在しないものである。例えば、図５（Ｃ）は、図３に示すノードＮ００００３に対応する候補リンクデータを示す。ノードＮ００００３においては、２つの進行可能な候補リンクＬ００１０６及びＬ００１０７が存在するが、候補リンクＬ００１０６に対しては目的地が設定されていない。従って、経路計算においては、経路計算しようとしている目的地がエリアＦに該当する場合ノードＮ００００３について候補リンクＬ００１０７のみが考慮され、候補経路が計算されることになる。

図３に示す候補リンクデータがノードに対応付けられた様子を図４（Ｂ）に模式的に示す。ノードＮ００００１においては図５（Ａ）に示す候補リンクデータ１３１が対応付けられており、ノードＮ００００２においては図５（Ｂ）に示す候補リンクデータ１３２が対応付けられている。

候補リンクデータは、経路探索機能においてユーザが指定可能な探索条件毎に用意することができる。探索条件としては、例えば、「有料道路優先」と「有料道路回避」、「フェリー使用」と「フェリー回避」、「時間優先」、「距離優先」などが挙げられる。これは、同じ目的地であっても、探索条件によって、計算される経路が異なるからである。例えば、同じ目的地であっても、「有料道路優先」の場合と「有料道路回避」の場合とでは、ユーザに提示すべき経路が異なってくるため、各々の条件について候補リンクデータが用意される。

また、実際のデータとしては、候補リンクデータに含まれるエリア（地名）は、対応するパーセルＩＤ（地域ＩＤ）として記憶されることになる。

次に、道なりのリンクについて説明する。上述のように、本実施例の経路計算では、各ノードにおいて、原則として道なりのリンクのみを経路計算の対象とする。ここで、道なりのリンクの決定方法をいくつかの例を挙げて説明しておく。いま、図６（Ａ）に示すように、５本のリンクＬ２０００１〜Ｌ２０００５が交わる交差点があるとする。

第１の例は、図６（Ｂ）に示すように、各リンクのリンクデータ中に、そのリンクについての道なりのリンクを示すリンク番号を格納しておく方法である。図６（Ｂ）において、各リンクＩＤの括弧内に示すリンクＩＤが、道なりのリンクのリンクＩＤを示している。例えば、リンクＬ２０００１についての道なりのリンクはＬ２０００４である。このように、リンクデータ中に道なりのリンクの情報を記憶しておけば、リンクデータを参照することにより、各リンクについての道なりのリンクを決定することができる。

第２の例は、各リンクのデータに基づいて、そのリンクの直進方向に最も近いリンクを道なりのリンクとする方法である。図６（Ｃ）において、リンクＬ２０００１の直進方向を破線で示している。この場合、リンクＬ２０００４は直進方向から角度αだけずれており、リンクＬ２０００３は直進方向から角度βだけずれている。角度α＜角度βであるので、リンクＬ２０００１についての道なりのリンクはＬ２０００４と決定される。

第３の例は、各リンクのデータに基づいて、道路種別が同一であるリンクを道なりのリンクと決定するものである。図６（Ｄ）において、リンクＬ２０００１及びＬ２０００５が国道であり、リンクＬ２０００２及びＬ２０００４が県道であり、リンクＬ２０００３が市道であるとする。この場合、リンクＬ２０００１についての道なりのリンクは、同一の道路種別（国道）を有するリンクＬ２０００５である。また、リンクＬ２０００２についての道なりのリンクは、同一の道路種別（県道）を有するリンクＬ２０００４である。

なお、本発明においては、道なりのリンクの決定方法は上記の例に限られるものではない。例えば、上記の例を複数組み合わせて使用してもよいし、上記以外の方法で道なりのリンクを決定してもよい。

次に、候補リンクデータを使用する場合の目的地の読み換えについて説明する。上記のように、候補リンクデータにおいては、各候補リンクに対して目的地が設定される。しかし、各候補リンクについて、対応する全ての目的地を設定すると、候補リンクデータとして記憶すべきデータ量が膨大となってしまう。例えば、東京から名古屋へ行く場合でも、その先の大阪、神戸、広島などへ行く場合でも、あるノードにおいては同一のリンクを使用する場合がある。この際、候補リンクデータにおいて、当該リンクの目的地として、名古屋、大阪、神戸、広島、..と全ての目的地を設定したのでは、記憶すべきデータ量が膨大となってしまう。

そこで、本実施例では、候補リンクデータ中には、必要に応じて中間目的地を設定し、中間目的地と最終目的地との対応を示したテーブル（「中間目的地テーブル」と呼ぶ。）を用いて、目的地の読み換えを行う。中間目的地とは、最終目的地までの経路上にある位置する目的地を言う。上記の例では、最終目的地が大阪、神戸、広島のいずれの場合でも名古屋を経由するので、最終目的地「大阪」、「神戸」、「広島」などに対して、中間目的地「名古屋」を規定する。中間目的地テーブルの例を図７に示す。なお、図７は、東京方面から出発する際の中間目的地テーブルの例である。

図７の例を参照すると、例えば、ユーザが経路探索の最終目的地として「大阪」を指定した場合、経路探索装置は中間目的地テーブルを参照し、候補リンクデータ中の各候補リンクが示す目的地が「大阪」であるリンクに加えて、「名古屋」となっているリンクも考慮して経路計算を行う。このように、中間目的地テーブルを用いて目的地の読み換えを行うことにより、候補リンクデータ中に、各候補リンクの先にある全ての目的地を設定する必要が無くなり、記憶すべきデータ量を大幅に減少させることができる。

［ナビゲーション装置］
図８に、本発明の実施例に係るナビゲーション装置２００の構成を示す。図８に示すように、ナビゲーション装置２００は、自立測位装置１０、ＧＰＳ受信機１８、システムコントローラ２０、ディスクドライブ３１、データ記憶ユニット３６、通信用インタフェース３７、通信装置３８、表示ユニット４０、音声出力ユニット５０及び入力装置６０を備える。

自立測位装置１０は、加速度センサ１１、角速度センサ１２及び距離センサ１３を備える。加速度センサ１１は、例えば圧電素子からなり、車両の加速度を検出し、加速度データを出力する。角速度センサ１２は、例えば振動ジャイロからなり、車両の方向変換時における車両の角速度を検出し、角速度データ及び相対方位データを出力する。距離センサ１３は、車両の車輪の回転に伴って発生されているパルス信号からなる車速パルスを計測する。

ＧＰＳ受信機１８は、複数のＧＰＳ衛星から、測位用データを含む下り回線データを搬送する電波１９を受信する。測位用データは、緯度及び経度情報等から車両の絶対的な位置を検出するために用いられる。

システムコントローラ２０は、インタフェース２１、ＣＰＵ（Central Processing Unit）２２、ＲＯＭ（Read Only Memory）２３及びＲＡＭ（Random Access Memory）２４を含んでおり、ナビゲーション装置２００全体の制御を行う。

インタフェース２１は、加速度センサ１１、角速度センサ１２及び距離センサ１３並びにＧＰＳ受信機１８とのインタフェース動作を行う。そして、これらから、車速パルス、加速度データ、相対方位データ、角速度データ、ＧＰＳ測位データ、絶対方位データ等をシステムコントローラ２０に入力する。ＣＰＵ２２は、システムコントローラ２０全体を制御する。ＲＯＭ２３は、システムコントローラ２０を制御する制御プログラム等が格納された図示しない不揮発性メモリ等を有する。ＲＡＭ２４は、入力装置６０を介して使用者により予め設定された経路データ等の各種データを読み出し可能に格納したり、ＣＰＵ２２に対してワーキングエリアを提供したりする。

システムコントローラ２０、ＣＤ−ＲＯＭドライブ又はＤＶＤ−ＲＯＭドライブなどのディスクドライブ３１、データ記憶ユニット３６、通信用インタフェース３７、表示ユニット４０、音声出力ユニット５０及び入力装置６０は、バスライン３０を介して相互に接続されている。

ディスクドライブ３１は、システムコントローラ２０の制御の下、ＣＤ又はＤＶＤといったディスク３３から、音楽データ、映像データなどのコンテンツデータを読み出し、出力する。なお、ディスクドライブ３１は、ＣＤ−ＲＯＭドライブ又はＤＶＤ−ＲＯＭドライブのうち、いずれか一方としてもよいし、ＣＤ及びＤＶＤコンパチブルのドライブとしてもよい。

データ記憶ユニット３６は、例えば、ＨＤＤなどにより構成され、地図データや施設データなどのナビゲーション処理に用いられる各種データを記憶する。

通信装置３８は、例えば、ＦＭチューナやビーコンレシーバ、携帯電話や専用の通信カードなどにより構成され、通信用インタフェース３７を介して、ＶＩＣＳ（登録商標）（Vehicle Information Communication System）センタから配信される渋滞や交通情報などの道路交通情報、その他の情報を受信する。

表示ユニット４０は、システムコントローラ２０の制御の下、各種表示データをディスプレイなどの表示装置に表示する。具体的には、システムコントローラ２０は、データ記憶ユニット３６から地図データを読み出す。表示ユニット４０は、システムコントローラ２０によってデータ記憶ユニット３６から読み出された地図データを、ディスプレイなどの表示画面上に表示する。表示ユニット４０は、バスライン３０を介してＣＰＵ２２から送られる制御データに基づいて表示ユニット４０全体の制御を行うグラフィックコントローラ４１と、ＶＲＡＭ（Video RAM ）等のメモリからなり即時表示可能な画像情報を一時的に記憶するバッファメモリ４２と、グラフィックコントローラ４１から出力される画像データに基づいて、液晶、ＣＲＴ（Cathode Ray Tube）等のディスプレイ４４を表示制御する表示制御部４３と、ディスプレイ４４とを備える。ディスプレイ４４は、例えば対角５〜１０インチ程度の液晶表示装置等からなり、車内のフロントパネル付近に装着される。

音声出力ユニット５０は、システムコントローラ２０の制御の下、ＣＤ−ＲＯＭドライブ３１又はＤＶＤ−ＲＯＭ３２、若しくはＲＡＭ２４等からバスライン３０を介して送られる音声デジタルデータのＤ／Ａ（Digital to Analog）変換を行うＤ／Ａコンバータ５１と、Ｄ／Ａコンバータ５１から出力される音声アナログ信号を増幅する増幅器（ＡＭＰ）５２と、増幅された音声アナログ信号を音声に変換して車内に出力するスピーカ５３とを備えて構成されている。

入力装置６０は、各種コマンドやデータを入力するための、キー、スイッチ、ボタン、リモコン、音声入力装置等から構成されている。入力装置６０は、車内に搭載された当該車載用電子システムの本体のフロントパネルやディスプレイ４４の周囲に配置される。また、ディスプレイ４４がタッチパネル方式である場合には、ディスプレイ４４の表示画面上に設けられたタッチパネルも入力装置６０として機能する。

なお、ＣＰＵ２２は、予めＲＯＭ２３などに記憶された経路探索プログラムを実行することにより、経路計算手段として機能する。また、図１に例示する地図データは、データ記憶ユニット３６に記憶される。

［経路探索処理］
次に、経路探索処理について説明する。図９に経路探索処理のフローチャートを示す。実際には、ＣＰＵ２２が経路探索プログラムを実行することにより、ナビゲーション装置２００が経路探索装置として動作し、経路探索処理を実行する。

まず、経路探索を行うユーザは、ナビゲーション装置２００の入力装置６０を使用して、経路探索機能を呼び出し、目的地（最終目的地）及び探索条件などを指定、入力する。これに応じて、ＣＰＵ２２は、経路探索のための出発地及び目的地を決定する（ステップＳ１０）。通常、ナビゲーション装置２００を搭載した車両の自車位置が出発地に設定される。なお、ＰＣなどの端末装置が経路探索装置となる場合には、ユーザが出発地を指定する場合もある。

次に、ＣＰＵ２２は、ユーザが指定した探索条件に対応する候補リンクデータを含む経路計算用データをデータ記憶ユニット３６から読み出し、目的地までの候補経路を計算する（ステップＳ１１）。この際、前述のようにＣＰＵ２２は、各ノードに候補リンクデータが存在するか否かを判定し、候補リンクデータが存在するノードについては、当該候補リンクデータが示す候補リンク及び目的地に基づいて候補経路を計算する。一方、候補リンクデータが存在しないノードについては、道なりのリンクのみに基づいて候補経路を計算する。また、必要に応じて、前述の中間目的地テーブルを参照し、目的地の読み換えを行う。

こうして、出発地から目的地へ至る複数の候補経路が得られると、ＣＰＵ２２は各候補経路についてコスト計算を行い、最小コストを有する候補経路を決定してユーザに提示する（ステップＳ１２）。こうして、経路探索処理が終了する。なお、コスト計算とは、経路計算において一般的に用いられる手法であり、リンク及びノードに予め対応付けされたコストの合計を計算することをいう。リンク及びノードに対応付けされたコストの値は、そのリンクやノードを通過する際に要する時間、道路の車線数などの各種の情報に基づいて予め設定されている。なお、コスト計算は既知の手法であるので、その詳細な説明は省略する。

上記の経路探索処理では、出発地から目的地に至る間の各ノードにおいて、原則として道なりのリンクのみを使用して候補経路を計算することとし、道なり以外のリンクを計算の対象に含める必要がある場合には、そのリンクを示す候補リンクデータが用意されている。よって、ＣＰＵ２２は、候補リンクデータが存在しない場合は道なりのリンクのみを対象とし、候補リンクデータが存在する場合にはそれが示す候補リンクを対象として候補経路の計算を行うので、遠距離の経路計算を迅速に実行することができる。また、道なりのリンクのみを計算の対象とすればよいノードについては、候補リンクデータを記憶する必要がないので、候補リンクデータとして記憶すべき全データ量をかなり抑えることができる。よって、膨大な量の特殊データを用意し、記憶する必要なく、迅速な経路探索が可能となる。

次に、本実施例による経路探索の例を説明する。いま、図１０（Ａ）に示す地図上において、出発地１４１から目的地１４２（「地点Ｐ」とする）までの経路を探索するものとする。本実施例による候補リンクデータを使用しない場合には、図１０（Ａ）に示す全ての道路（リンク）が経路計算の対象となり、計算量は膨大となる。

一方、本実施例によれば、図１０（Ｂ）に示すように、地点１４３及び１４４に候補リンクデータが用意される。よって、図中の下方向からの道路にて出発地１４１に至った場合、地点１４４までの間の各ノードには候補リンクデータが存在しないので、地点１４４までは道なりに進むリンクが選択される。次に、地点１４４の候補リンクデータを参照し、目的地として「地点Ｐ」が示されている候補リンクが選択される（即ち、左折）。その後、候補リンクデータが存在しないノードを道なりに進むリンクが選択され、目的地１４２（地点Ｐ）に到る。こうして、破線で示す候補経路１４５ａが得られる。同様に、図中右側からの道路にて出発点１４１に至った場合、地点１４３までは候補リンクデータが無いので道なりのリンクが選択され、地点１４３で経路候補データが示す地点Ｐ方向への候補リンクが選択され（即ち、斜め右方向へ進む）、その後、道なりのリンクが選択されて目的地１４２に至る。こうして、破線で示す候補経路１４５ｂが得られる。

このように、本実施例によれば、候補リンクデータが存在しないノードは全て道なりのリンクのみを対象として経路計算を行うので、計算の対象となるリンクを大幅に減少させることができ、迅速な経路計算が可能となる。なお、本実施例を用いても、上記の例のように、目的地に至る複数の候補経路を得ることが可能である。

［変形例］
上記の例では、候補リンクデータにおいて、異なる候補リンクには異なる目的地が設定されているが、図１１（Ａ）に例示するように、異なる候補リンクに対して同一の目的地が設定されることがある。これは、エリアＸが比較的広い場合など、どちらの候補リンクを使用しても同一の目的地に到達できる場合があるからである。

また、上記の候補リンクデータの例は、あるノードに接続された複数のリンクのうちの１つのリンクから当該ノードに進入した場合の候補リンクデータを示している。しかし、同一のノードに、異なるリンクから進入した場合は、候補リンクデータの内容は異なるものとなる。即ち、あるノードに対して記憶される候補リンクデータは、そのノードに接続されたリンク毎に用意され、記憶されることになる。例えば、東西南北の方向にリンクを有するノードについては、各方向から進入した場合について、独立に候補リンクデータが必要となる。従って、実際のデータとしては、そのノードに接続されたリンク毎に独立して候補リンクデータを記憶しても良いし、全てのリンクに対する候補リンクデータをまとめて記憶してもよい。

候補リンクデータをまとめて記憶する場合の例を図１１（Ｂ）に示す。図１１（Ｂ）において、リンクＬ００２０１からノードＺに進入した場合、リンクＬ００２０２及びＬ００２０３が候補リンクとなる。一方、リンクＬ００２０２からノードＺに進入した場合、リンクＬ００２０１及びＬ００２０３が候補リンクとなり、リンクＬ００２０３からノードＺに進入した場合、リンクＬ００２０１及びＬ００２０２が候補リンクとなる。

但し、この場合、単純に各リンクから進入した際の候補リンクデータをまとめて記憶すると、計算対象となるリンクが増えてしまうことがある。そのような場合には、図１１（Ｃ）の括弧書きに示すように、進入方向の条件を付加することにより、不要な計算量の増加を防止することができる。

また、上記の例は、経路計算用データとして候補リンクデータを用意するものであるが、地図データには、交差点において曲がる方向やリンクと方面の名称、地名を紐付けたデータが、経路誘導用に格納されていることがある。これを上記の候補リンクデータとして利用して経路計算を行ってもよい。また、逆に、上記の候補リンクデータを用いて、方面名称等を音声等で案内を行っても良いし、方面看板として地図データの表示画像中に表示しても良い。

本発明は、地図データを用いて経路を探索する機能を有する各種の端末装置に利用することができる。具体的には、カーナビゲーション装置の他、ウェブ上で経路探索サービスを提供するサーバ装置、ウェブ上のサーバからダウンロードした地図データ又はＤＶＤ−ＲＯＭなどの記憶媒体に記憶されている地図データを用いてＰＣ上で経路を計算するアプリケーションなどに利用することができる。

Claims (6)

1. 道路に対応するリンクを示すリンクデータと、前記道路上の所定の地点に対応するノードを示すノードデータと、を含む経路計算用データを記憶する記憶部と、
   前記経路計算用データを用いて、目的地までの経路計算を行う経路計算手段と、を備え、
   前記リンクデータによって示されるリンクは、当該リンクを通って到達するエリアの情報を有する候補リンクを含み、
   前記経路計算手段は、目的地に対応するエリアの情報を有する候補リンクが存在するノードについては当該目的地に対応するエリアの情報を有する候補リンクを対象とし、目的地に対応するエリアの情報を有する候補リンクが存在しないノードについては道なりのリンクを対象として、経路計算を行うことを特徴とする経路探索装置。
2. 前記候補リンクは探索条件毎に用意されており、
   前記経路計算手段は、ユーザが指定した探索条件に対応する候補リンクを用いて経路計算を行うことを特徴とする請求項１に記載の経路探索装置。
3. 前記経路計算用データは異なる縮尺に対応する複数のレイヤ毎に用意されており、
   前記候補リンクは、少なくとも最も広域の地図に対応するレイヤに対して用意されていることを特徴とする請求項１に記載の経路探索装置。
4. 前記経路計算用データは、最終目的地と、当該最終目的地までの経路の途中に位置する中間目的地との対応を示す中間目的地テーブルを含み、
   前記経路計算手段は、前記最終目的地及び前記中間目的地を前記目的地として候補経路を計算することを特徴とする請求項１に記載の経路探索装置。
5. コンピュータを備える端末装置により実行される経路探索方法であって、道路に対応するリンクを示すリンクデータと、前記道路上の所定の地点に対応するノードを示すノードデータと、を含む経路計算用データを用いて、目的地までの経路計算を行う経路計算工程を備え、
   前記リンクデータによって示されるリンクは、当該リンクを通って到達するエリアの情報を有する候補リンクを含み、
   前記経路計算工程は、目的地に対応するエリアの情報を有する候補リンクが存在するノードについては当該目的地に対応するエリアの情報を有する候補リンクを対象とし、目的地に対応するエリアの情報を有する候補リンクが存在しないノードについては道なりのリンクを対象として、経路計算を行うことを特徴とする経路探索方法。
6. 道路に対応するリンクを示すリンクデータと、前記道路上の所定の地点に対応するノードを示すノードデータと、を含む経路計算用データを記憶する記憶部と、コンピュータと、を備える端末装置において実行される経路探索プログラムであって、
   前記経路計算用データを用いて、目的地までの経路計算を行う経路計算手段として前記コンピュータを機能させ、
   前記リンクデータによって示されるリンクは、当該リンクを通って到達するエリアの情報を有する候補リンクを含み、
   前記経路計算手段は、目的地に対応するエリアの情報を有する候補リンクが存在するノードについては当該目的地に対応するエリアの情報を有する候補リンクを対象とし、目的地に対応するエリアの情報を有する候補リンクが存在しないノードについては道なりのリンクを対象として、経路計算を行うことを特徴とする経路探索プログラム。

Images