WO2008044281A1

WO2008044281A1 - Dispositif, procédé et logiciel de recherche d'itinéraire, et support d'enregistrement

Info

Publication number: WO2008044281A1
Application number: PCT/JP2006/320220
Authority: WO
Inventors: Ippei Nambata
Original assignee: Pioneer Corporation
Priority date: 2006-10-10
Filing date: 2006-10-10
Publication date: 2008-04-17
Also published as: US20100114470A1; JP5016605B2; JPWO2008044281A1

Description

明細書

経路探索装置、経路探索方法、経路探索プログラム及び記憶媒体技術分野

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

背景技術

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

[0003] 一般的に、遠距離の経路計算は、候補となる道路数が多くなるため時間を要する。

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

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

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

[0006] 特許文献 1 :特開平 11 64023号公報

発明の開示

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

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

課題を解決するための手段

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

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

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

[0012] 請求項 8に記載の発明では、道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを記憶した記憶媒体が提供される。

図面の簡単な説明

[0013] [図 1]本発明の実施例において使用する地図データの構成を模式的に示す。

[図 2]経路計算用データの構成例を示す。

[図 3]ノードデータの構成例を示す。

[図 4]リンク及びノードと、候補リンクデータとの関係を示す。

[図 5]候補リンクデータの例を模式的に示す。

[図 6]道なりのリンクの決定方法の例を示す。

[図 7]中間目的地テーブルの例を示す。

[図 8]実施例に係るナビゲーシヨン装置の概略構成を示すブロック図である。

[図 9]実施例による経路探索処理のフローチャートである。

[図 10]実施例による経路探索の例を示す。

[図 11]候補リンクデータの変形例を示す。

符号の説明

[0014] 120 地図データ

122 地図表示用データ

124 経路計算用データ

125 ノードデータ

126 リンクデータ

131、 132 候補リンクデータ

200 ナビゲーシヨン装置

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

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

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

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

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

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

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

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

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

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

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

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

実施例

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

[0028] [地図データ]

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

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

[0030] 図 2に経路計算用データの構成を示す。経路計算用データ 124は、ノードデータ 1 25及びリンクデータ 126を含む。ノードは道路上の交差点などの所定の地点に対応し、ノードデータ 125はノードを示すデータである。一方、リンクは交差点などにより区切られた道路の 1区画に対応し、リンクデータ 126はリンクを示すデータである。

[0031] ノード及びリンクの例を図 4 (A)及び 4 (B)に示す。図 4 (A)に示す複数の道路 111 を含む地図は、図 4 (B)に示すように複数のノード及びリンクにより構成される。なお、図 4 (B)においては、各ノードをノード ID (N00001など）で示し、各リンクをリンク ID ( LOOOO 1など）で示して!/、る。

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

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

[0034] 具体的に、候補リンクデータは、各ノードに接続された候補リンクと、その候補リンクに対応する目的地との対応を示している。図 3に示すノード NOOOOlにおける候補リンクデータを図 5 (A)に示す。ノード NOOOOlにおいては、 3つの進行可能な候補リンク: L00101、： L00102及び L00103力ある。候ネ甫リンク: LOO 101の目的地 ίまエリア Α (東京)であり、候補リンク L00102の目的地はエリア B (千葉)であり、候補リンク LO 0103の目的地はエリア C (横浜)である。 [0035] 同様に、図 3に示すノード N00002における候補リンクデータを図 5 (B)に示す。ノード NOOOOlにおいては、 2つの進行可能な候補リンク L00104及び L00105がある。候ネ ΐリンク L00104の目的地はエリア Dであり、候ネ甫リンク L00102の目的地はエリァ Εである。

[0036] なお、候補リンクデータにおいては、そのノードに接続された全ての候補リンクに対して目的地が設定されるわけではない。即ち、あるノードにおいては、当該ノードに接続された複数の候補リンクのうち、そのノードを経由する候補経路に含めるべき候補リンクのみに対して目的地が設定される。よって、該当する目的地が設定されていないリンクは、候補経路の計算対象から除外される。なお、目的地が設定されていないリンクは、一般的には、道なりのリンクが途中でとぎれており、その先に目的地が存在しないものである。例えば、図 5 (C)は、図 3に示すノード Ν00003に対応する候補リンクデータを示す。ノード Ν00003においては、 2つの進行可能な候補リンク L00106 及び L00107が存在する力候補リンク L00106に対しては目的地が設定されていない。従って、経路計算においては、経路計算しょうとしている目的地がエリア Fに該当する場合ノード Ν00003について候補リンク LOO 107のみが考慮され、候補経路力 S計算されること〖こなる。

[0037] 図 3に示す候補リンクデータがノードに対応付けられた様子を図 4 (B)に模式的に示す。ノード NOOOOlにおいては図 5 (A)に示す候補リンクデータ 131が対応付けられており、ノード Ν00002においては図 5 (B)に示す候補リンクデータ 132が対応付けられている。

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

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

[0040] 次に、道なりのリンクについて説明する。上述のように、本実施例の経路計算では、各ノードにおいて、原則として道なりのリンクのみを経路計算の対象とする。ここで、道なりのリンクの決定方法をいくつかの例を挙げて説明しておく。いま、図 6 (A)に示すように、 5本のリンク L20001〜L20005が交わる交差点があるとする。

[0041] 第 1の例は、図 6 (B)に示すように、各リンクのリンクデータ中に、そのリンクについての道なりのリンクを示すリンク番号を格納しておく方法である。図 6 (B)において、各リンク IDの括弧内に示すリンク ID力道なりのリンクのリンク IDを示している。例えば、リンク L20001【こつ!/、ての道なりのリンク ίま L20004である。このよう【こ、リンクデータ中に道なりのリンクの情報を記憶しておけば、リンクデータを参照することにより、各リンクについての道なりのリンクを決定することができる。

[0042] 第 2の例は、各リンクのデータに基づいて、そのリンクの直進方向に最も近いリンクを道なりのリンクとする方法である。図 6 (C)において、リンク L20001の直進方向を破線で示している。この場合、リンク L20004は直進方向カゝら角度 αだけずれており、リンク L20003は直進方向から角度 |8だけずれている。角度 αく角度 j8であるので、リンク L20001につ!/、ての道なりのリンクは L20004と決定される。

[0043] 第 3の例は、各リンクのデータに基づいて、道路種別が同一であるリンクを道なりのリンクと決定するものである。図 6 (D)において、リンク L20001及び L20005力国道であり、リンク L20002及び L20004力 S県道であり、リンク L20003力 S市道であるとする。この場合、リンク L20001についての道なりのリンクは、同一の道路種別（国道）を有するリンク L20005である。また、リンク L20002につ!/ヽての道なりのジンクは、同一の道路種別（県道）を有するリンク L20004である。

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

[0045] 次に、候補リンクデータを使用する場合の目的地の読み換えについて説明する。

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

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

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

[0048] [ナビゲーシヨン装置]

図 8に、本発明の実施例に係るナビゲーシヨン装置 200の構成を示す。図 8に示すように、ナビゲーシヨン装置 200は、自立測位装置 10、 GPS受信機 18、システムコントローラ 20、ディスクドライブ 31、データ記憶ユニット 36、通信用インタフェース 37、通信装置 38、表示ユニット 40、音声出力ユニット 50及び入力装置 60を備える。

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

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

[0051] システムコントローラ 20は、インタフェース 21、 CPU (Central Processing Unit) 22、 ROM (Read Only Memory) 23及び RAM (Random Access Memory) 24を含んでおり、ナビゲーシヨン装置 200全体の制御を行う。

[0052] インタフェース 21は、加速度センサ 11、角速度センサ 12及び距離センサ 13並びに GPS受信機 18とのインタフェース動作を行う。そして、これらから、車速パルス、加速度データ、相対方位データ、角速度データ、 GPS測位データ、絶対方位データ等をシステムコントローラ 20に入力する。 CPU22は、システムコントローラ 20全体を制御する。 ROM23は、システムコントローラ 20を制御する制御プログラム等が格納された図示しない不揮発性メモリ等を有する。 RAM24は、入力装置 60を介して使用者により予め設定された経路データ等の各種データを読み出し可能に格納したり、 C PU22に対してワーキングエリアを提供したりする。

[0053] システムコントローラ 20、 CD— ROMドライブ又は DVD— ROMドライブなどのディスクドライブ 31、データ記憶ユニット 36、通信用インタフェース 37、表示ユニット 40、音声出力ユニット 50及び入力装置 60は、バスライン 30を介して相互に接続されてヽる。

[0054] ディスクドライブ 31は、システムコントローラ 20の制御の下、 CD又は DVDといったディスク 33から、音楽データ、映像データなどのコンテンツデータを読み出し、出力する。なお、ディスクドライブ 31は、 CD— ROMドライブ又は DVD— ROMドライブのうち、いずれか一方としてもよいし、 CD及び DVDコンパチブルのドライブとしてもよい

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

[0056] 通信装置 38は、例えば、 FMチューナやビーコンレシーバ、携帯電話や専用の通信カードなどにより構成され、通信用インタフェース 37を介して、 VICS (Vehicle Infor mation Communication System)センタから配信される渋滞や交通情報などの道路交通情報、その他の情報を受信する。

[0057] 表示ユニット 40は、システムコントローラ 20の制御の下、各種表示データをディスプレイなどの表示装置に表示する。具体的には、システムコントローラ 20は、データ記憶ユニット 36から地図データを読み出す。表示ユニット 40は、システムコントローラ 2 0によってデータ記憶ユニット 36から読み出された地図データを、ディスプレイなどの表示画面上に表示する。表示ユニット 40は、バスライン 30を介して CPU22から送られる制御データに基づいて表示ユニット 40全体の制御を行うグラフィックコントローラ 41と、 VRAM (Video RAM )等のメモリからなり即時表示可能な画像情報を一時的に記憶するノッファメモリ 42と、グラフィックコントローラ 41から出力される画像データに基づいて、液晶、 CRT (Cathode Ray Tube)等のディスプレイ 44を表示制御する表示制御部 43と、ディスプレイ 44とを備える。ディスプレイ 44は、例えば対角 5〜10ィンチ程度の液晶表示装置等力なり、車内のフロントパネル付近に装着される。

[0058] 音声出力ユニット 50は、システムコントローラ 20の制御の下、 CD— ROMドライブ 3 1又は DVD—ROM32、若しくは RAM24等からバスライン 30を介して送られる音声デジタルデータの DZA (Digital to Analog)変換を行う DZAコンバータ 51と、 Ό/Α コンバータ 51から出力される音声アナログ信号を増幅する増幅器 (AMP) 52と、増幅された音声アナログ信号を音声に変換して車内に出力するスピーカ 53とを備えて構成されている。

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

[0060] なお、 CPU22は、予め ROM23などに記憶された経路探索プログラムを実行することにより、経路計算手段として機能する。また、図 1に例示する地図データは、データ記憶ユニット 36に記憶される。 [0061] [経路探索処理]

次に、経路探索処理について説明する。図 9に経路探索処理のフローチャートを示す。実際には、 CPU22が経路探索プログラムを実行することにより、ナビゲーシヨン装置 200が経路探索装置として動作し、経路探索処理を実行する。

[0062] まず、経路探索を行うユーザは、ナビゲーシヨン装置 200の入力装置 60を使用して、経路探索機能を呼び出し、目的地 (最終目的地)及び探索条件などを指定、入力する。これに応じて、 CPU22は、経路探索のための出発地及び目的地を決定する（ステップ S10)。通常、ナビゲーシヨン装置 200を搭載した車両の自車位置が出発地に設定される。なお、 PCなどの端末装置が経路探索装置となる場合には、ユーザが出発地を指定する場合もある。

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

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

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

[0066] 次に、本実施例による経路探索の例を説明する。いま、図 10 (A)に示す地図上にお!、て、出発地 141から目的地 142 (「地点 P」とする）までの経路を探索するものとする。本実施例による候補リンクデータを使用しない場合には、図 10 (A)に示す全ての道路 (リンク)が経路計算の対象となり、計算量は膨大となる。

[0067] 一方、本実施例によれば、図 10 (B)に示すように、地点 143及び 144に候補リンクデータが用意される。よって、図中の下方向力もの道路にて出発地 141に至った場合、地点 144までの間の各ノードには候補リンクデータが存在しないので、地点 144 までは道なりに進むリンクが選択される。次に、地点 144の候補リンクデータを参照し、目的地として「地点 P」が示されている候補リンクが選択される（即ち、左折)。その後、候補リンクデータが存在しないノードを道なりに進むリンクが選択され、目的地 142 ( 地点 P)に到る。こうして、破線で示す候補経路 145aが得られる。同様に、図中右側力もの道路にて出発点 141に至った場合、地点 143までは候補リンクデータが無いので道なりのリンクが選択され、地点 143で経路候補データが示す地点 P方向への候補リンクが選択され (即ち、斜め右方向へ進む）、その後、道なりのリンクが選択されて目的地 142に至る。こうして、破線で示す候補経路 145bが得られる。

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

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

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

[0071] 候補リンクデータをまとめて記憶する場合の例を図 11 (B)に示す。図 11 (B)において、リンク L00201力らノード Zに進入した場合、リンク L00202及び L00203力候ネ甫リンクとなる。一方、リンク L00202からノード Zに進入した場合、リンク L00201及び L 00203力候ネ甫リンクとなり、リンク L00203力らノード Zに進入した場合、リンク L0020 1及び L00202が候補リンクとなる。

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

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

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

Claims

請求の範囲

[1] 道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを記憶する記憶部と、

前記経路計算用データを用いて、経路計算を行う経路計算手段と、を備え、前記経路計算手段は、前記候補リンクデータが存在するノードについては当該候補リンクデータが示すリンクを対象とし、前記候補リンクデータが存在しないノード〖こついては道なりのリンクを対象として、経路計算を行うことを特徴とする経路探索装置

[2] 前記候補リンクデータは探索条件毎に用意されており、

前記経路計算手段は、ユーザが指定した探索条件に対応する候補リンクデータを用いて経路計算を行うことを特徴とする請求項 1に記載の経路探索装置。

[3] 前記経路計算手段は、前記候補リンクデータが示すリンクのうち、目的地が示されて、るリンクのみを対象とすることを特徴とする請求項 1に記載の経路探索装置。

[4] 前記経路計算用データは異なる縮尺に対応する複数のレイヤ毎に用意されており前記候補リンクデータは、少なくとも最も広域の地図に対応するレイヤに対して用意されて、ることを特徴とする請求項 1に記載の経路探索装置。

[5] 前記経路計算用データは、最終目的地と、当該最終目的地までの経路の途中に位置する中間目的地との対応を示す中間目的地テーブルを含み、

前記経路計算手段は、前記最終目的地及び前記中間目的地を前記目的地として候補経路を計算することを特徴とする請求項 1に記載の経路探索装置。

[6] 道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを用いて、経路計算を行う経路計算工程を備え、

前記経路計算工程は、前記候補リンクデータが存在するノードについては当該候補リンクデータが示すリンクを対象とし、前記候補リンクデータが存在しないノード〖こついては道なりのリンクを対象として、経路計算を行うことを特徴とする経路探索方法

[7] 道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを記憶する記憶部と、コンビユータと、を備える端末装置において実行される経路探索プログラムであって、

前記経路計算用データを用いて、経路計算を行う経路計算手段として前記コンビユータを機能させ、

前記経路計算手段は、前記候補リンクデータが存在するノードについては当該候補リンクデータが示すリンクを対象とし、前記候補リンクデータが存在しないノード〖こついては道なりのリンクを対象として、経路計算を行うことを特徴とする経路探索プログラム。

[8] 道路に対応するリンクを示すリンクデータと、道路上の所定の地点に対応するノードを示すノードデータと、前記ノードを経由する候補経路の計算対象とすべきリンクを示す候補リンクデータと、を含む経路計算用データを記憶した記憶媒体。