(57)【特許請求の範囲】
【請求項１】
目的地までの経路を探索するナビゲーション装置における経路探索方法において、
リンク情報に、リンク両端のノード、リンク長、リンクの制限速度、リンクの機能的クラスを含ませて地図情報を作成し、
経路探索に際して、目的地までの直線距離とリンクの機能的クラスとに基づいて該リンクの制限速度を補正し、
補正された制限速度とリンク長よりリンク通過時間を計算し、
該リンク通過時間に基づいて目的地までの所要時間が最短となる経路を探索し、
前記制限速度の補正に際して、上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように、かつ、目的地までの直線距離が長くなるほど補正の度合が大きくなるように該制限速度を補正する、
ことを特徴とする経路探索方法。
【請求項２】
幅員、制限速度、道路の種別のうち少なくとも１つが含まれる道路の機能的要素を考慮して前記機能的クラスを決定し、
上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように補正値を決定すると共に、目的地までの直線距離が長くなるほど、絶対値が大きくなるように該補正値を決定し、該補正値を制限速度に加算して制限速度を補正する、
ことを特徴とする請求項１記載の経路探索方法。
【請求項３】
目的地までの直線距離とリンクの機能的クラスとの組み合わせに対する制限速度の補正値を保持するテーブルを設け、
該テーブルより求まる補正値を用いてリンクの制限速度を補正する、
ことを特徴とする請求項１記載の経路探索方法。
【請求項４】
交差する道路の機能的クラス及び自リンクの機能的クラスを考慮してノード通過時間を推定し、
該ノード通過時間を前記リンク通過時間に加算して該リンク通過時間を補正する、
ことを特徴とする請求項１記載の経路探索方法。
【請求項５】
幅員、制限速度、道路の種別のうち少なくとも１つが含まれる道路の機能的要素を考慮して前記機能的クラスを決定し、
上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように補正値を決定すると共に、目的地までの直線距離が長くなるほど、絶対値が大きくなるように該補正値を決定し、該補正値を制限速度に加算して制限速度を補正する、
ことを特徴とする請求項４記載の経路探索方法。
【請求項６】
目的地までの直線距離とリンクの機能的クラスとの組み合わせに対する制限速度の補正値を保持するテーブルを設け、
該テーブルより求まる補正値を用いてリンクの制限速度を補正する、
ことを特徴とする請求項５記載の経路探索方法。
【請求項７】
目的地までの経路を探索するナビゲーション装置における経路探索方法において、
リンク情報に、リンク両端のノード、リンク長、リンクの制限速度、リンクの機能的クラスを含ませて地図情報を作成し、
経路探索に際して、目的地までの直線距離とリンクの機能的クラスとに基づいて該リンクの制限速度を補正し、
補正された制限速度とリンク長よりリンク通過時間を計算し、
該リンク通過時間に基づいて目的地までの所要時間が最短となる経路を探索し、
出発地が属するリンクの機能的クラスと同一クラスのリンクを用いて上位クラスのリンクに到達するまで該出発地より目的地に向けて経路探索を行い、
目的地が属するリンクの機能的クラスと同一クラスのリンクを用いて上位クラスのリンクに到達するまで該目的地より出発地に向けて経路探索を行い、
前記出発地より探索した上位クラスのリンクのノードを新たな出発地、前記目的地より探索した上位クラスのリンクのノードを新たな目的地とし、該上位クラスのリンクを用いて上記処理を繰り返し、
所定クラスにおいて目的地に到達すれば、出発地側から求めた各クラスの探索経路と目的地側から求めた各クラスの探索経路を順番に接続して誘導経路を形成し、
前記制限速度の補正に際して、上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように、かつ、目的地までの直線距離が長くなるほど補正の度合が大きくなるように該制限速度を補正する、
ことを特徴とする経路探索方法。
【請求項８】
前記新たな出発地をノードとするリンクのクラスと前記新たな目的地をノードとするリンクのクラスは同じである、
ことを特徴とする請求項７記載の経路探索方法。
【請求項９】
幅員、制限速度、道路の種別のうち少なくとも１つが含まれる道路の機能的要素を考慮して前記機能的クラスを決定し、
上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように補正値を決定すると共に、目的地までの直線距離が長くなるほど、絶対値が大きくなるように該補正値を決定し、該補正値を制限速度に加算して制限速度を補正する、
ことを特徴とする請求項８記載の経路探索方法。
【請求項１０】
目的地までの直線距離とリンクの機能的クラスとの組み合わせに対する制限速度の補正値を保持するテーブルを設け、
該テーブルより求まる補正値を用いてリンクの制限速度を補正する、
ことを特徴とする請求項９記載の経路探索方法。
【請求項１１】
交差する道路の機能的クラス及び自リンクの機能的クラスを考慮してノード通過時間を推定し、
該ノード通過時間を前記リンク通過時間に加算して該リンク通過時間を補正する、
ことを特徴とする請求項７記載の経路探索方法。
【請求項１２】
前記新たな出発地をノードとするリンクのクラスと前記新たな目的地をノードとするリンクのクラスは同じである、
ことを特徴とする請求項１１記載の経路探索方法。
【請求項１３】
幅員、制限速度、道路の種別のうち少なくとも１つが含まれる道路の機能的要素を考慮して前記機能的クラスを決定し、
上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように補正値を決定すると共に、目的地までの直線距離が長くなるほど、絶対値が大きくなるように該補正値を決定し、該補正値を制限速度に加算して制限速度を補正する、
ことを特徴とする請求項１２記載の経路探索方法。
【請求項１４】
目的地までの直線距離とリンクの機能的クラスとの組み合わせに対する制限速度の補正値を保持するテーブルを設け、
該テーブルより求まる補正値を用いてリンクの制限速度を補正する、
ことを特徴とする請求項１３記載の経路探索方法。
【請求項１５】
目的地までの経路を探索する経路探索装置において、
リンク情報に、リンク両端のノード、リンク長、リンクの制限速度、リンクの機能的クラスを含ませてなる地図情報を保存する地図情報記憶部、
上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように、かつ、目的地までの直線距離が長くなるほど、絶対値が大きくなるように該制限速度の補正値を決定し、該補正値を目的地までの直線距離とリンクの機能的クラスの組み合わせに対応させて保持するテーブル、
経路探索に際して、目的地までの直線距離とリンクの機能的クラスとに応じた前記補正値を用いて該リンクの制限速度を補正し、補正された制限速度とリンク長よりリンク通過時間を計算し、該リンク通過時間に基づいて目的地までの所要時間が最短となる経路を探索する経路探索部、
を備えたことを特徴とする経路探索装置。
【請求項１６】
前記経理探索部は、交差する道路の機能的クラス及び自リンクの機能的クラスを考慮してノード通過時間を推定し、該ノード通過時間を前記リンク通過時間に加算して該リンク通過時間を補正する、
ことを特徴とする請求項１５記載の経路探索装置。
【請求項１７】
目的地までの経路を探索する経路探索装置において、
リンク情報に、リンク両端のノード、リンク長、リンクの制限速度、リンクの機能的クラスを含ませてなる地図情報を保存する地図情報記憶部、
上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように、かつ、目的地までの直線距離が長くなるほど、絶対値が大きくなるように該制限速度の補正値を決定し、該補正値を目的地までの直線距離とリンクの機能的クラスの組み合わせに対応させて保持するテーブル、
経路探索に際して、目的地までの直線距離とリンクの機能的クラスとに応じた前記補正値を用いて該リンクの制限速度を補正し、補正された制限速度とリンク長よりリンク通過時間を計算し、該リンク通過時間に基づいて目的地までの所要時間が最短となる経路を探索する経路探索部、
を備え、前記経路探索部は、
出発地が属するリンクの機能的クラスと同一クラスのリンクを用いて上位クラスのリンクに到達するまで該出発地より目的地に向けて経路探索を行う手段、
目的地が属するリンクの機能的クラスと同一クラスのリンクを用いて上位クラスのリンクに到達するまで該目的地より出発地に向けて経路探索を行う手段、
前記出発地より探索した上位クラスのリンクのノードを新たな出発地、前記目的地より探索した上位クラスのリンクのノードを新たな目的地とし、該上位クラスのリンクを用いて上記処理を繰り返す手段、
所定クラスにおいて目的地に到達すれば、出発地側から求めた各クラスの探索経路と目的地側から求めた各クラスの探索経路を順番に接続して誘導経路を形成する手段、
を有することを特徴とする経路探索装置。
【請求項１８】
前記経理探索部は、交差する道路の機能的クラス及び自リンクの機能的クラスを考慮してノード通過時間を推定し、該ノード通過時間を前記リンク通過時間に加算して該リンク通過時間を補正する手段、
を備えることを特徴とする請求項１７記載の経路探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は経路探索方法及び経路探索装置に係わり、特に、目的地までの経路を探索するナビゲーション装置における経路探索方法及び経路探索装置に関する。
【０００２】
【従来の技術】
車載用ナビゲーション装置は、車両位置を検出してDVDなどの地図記憶媒体から車両位置周辺の地図データを読み出して地図をディスプレイ画面に描画するとともに該地図上の所定箇所に車両位置マークを重ねて描画する。そして、車両が移動するに従い、車両位置マークを画面中央等の所定位置に固定すると共に地図をスクロールして、常に、車両位置周辺の地図が一目で判るようにようになっている。かかる車載用ナビゲーション装置には、出発地点から目的地点まで例えば最短時間あるいは最短距離を辿るような誘導経路を探索し、画面に該経路を表示して運転者の走行案内をする経路誘導機能が設けられている。この経路誘導機能によれば、実際の運転に際して、誘導経路を特定の色で太く表示するなど他の道路と識別可能に表示して、運転者が目的地まで容易に到着できるようになっている。車両が走行する誘導経路を道路地図データから検索する方法として、ダイクストラ法やＡ*アルゴリズム等が知られている。
【０００３】
【発明が解決しようとする課題】
ナビゲーション装置の経路探索に際して、ユーザは生成される経路の質だけでは満足しない。その経路を探索するのに費やされる時間についても考慮する必要がある。理想的な経路探索に望まれるのは、より高速で、より質の良い解である。しかし、一般に解の質と探索時間はトレードオフの関係にあり、現実的に探索時間が短くて済む最適解に近い解の方が、長い探索時間を必要とする最適解よりも利用価値がある。ダイクストラ法やＡ*アルゴリズムは最適経路、すなわち、最短経路を探索できるが、探索範囲が広いため探索時間が長くなる。特に、出発地から目的地までの距離が長くなったり、道路網の密度が高くなると経路探索の対象となる交差点、リンクが多くなり、経路探索時間が増加する。
【０００４】
本発明の目的は、目的地までの距離が長くなれば少々距離が長くなってもフリーウェイ等のメインの道路を選択しやすくすることである。
本発明の別の目的は、短時間で目的地までの経路を探索できるようにすることである。
本発明の別の目的は、交差点における信号待ち、一時停止待ちなど交差点通過時間を考慮した経路探索を行えるようにすることである。
【０００５】
【課題を解決するための手段】
上記課題は本発明によれば、(1) リンク情報に、リンク両端のノード、リンク長、リンクの制限速度、リンクの機能的クラスを含ませて地図情報を作成すること、(2) 経路探索に際して、着目リンクのノードから目的地までの直線距離と該リンクの機能的クラスとに基づいて該リンクの制限速度を補正すること、(3) 補正制限速度とリンク長とからリンク通過時間を計算し、(4) 該リンク通過時間に基づいて目的地までの所要時間が最短となる経路を探索すること、を有する経路探索方法により達成される。なお、前記制限速度の補正に際して、上位クラスのリンクほど制限速度が大きくなるように、又、下位クラスのリンクほど制限速度が小さくなるように、かつ、目的地までの直線距離が長くなるほど補正の度合が大きくなるように該制限速度を補正する。
【０００６】
又、上記課題は、本発明によれば、更に、(1) 出発地が属するリンクの機能的クラスと同一クラスのリンクを用いて上位クラスのリンクに到達するまで該出発地より目的地に向けて経路探索を行うこと、(2) 同様に目的地が属するリンクの機能的クラスと同一クラスのリンクを用いて上位クラスのリンクに到達するまで該目的地より出発地に向けて経路探索を行うこと、(3) 前記出発地より探索した上位クラスのリンクのノードを新たな出発地、前記目的地より探索した上位クラスのリンクのノードを新たな目的地とし、該クラスのリンクを用いて上記処理を繰り返すこと、(4) ２つのパスが遭遇するとき、出発地側から求めた各クラスの探索経路と目的地側から求めた各クラスの探索経路を接続して誘導経路を形成すること、を有する経路探索方法により達成される。
【０００７】
又、上記課題は本発明によれば、(1) 交差する道路の機能的クラス及び自リンクの機能的クラスを考慮してノード通過時間を推定すること、(2) 該ノード通過時間を前記リンク通過時間に加算して該リンク通過時間を補正すること、を有する経路探索方法により達成される。
【０００８】
【発明の実施の形態】
（ａ）車載ナビゲーション装置の全体構成
図１は本発明の車載ナビゲーション装置の全体構成図である。図中、１１は地図データを記憶するDVD(Digital Video Disk)などの地図情報記憶部である。地図は縮尺レベルに応じて適当な大きさの経度幅、緯度幅に区切られており、道路は経緯度で表現された頂点(ノード)の座標集合で示され、各頂点(ノード)を順に直線で接続することに描画できる。２つの交差点ノードを連結した道路部分はリンクと呼ばれ、道路は多数のリンクで構成されている。
【０００９】
地図データには、図２に示すように、道路リスト、各道路の道路データ、道路を構成する各リンクのリンクデータを有している。道路データは、道路名、道路を構成するリンクIDを含んでいる。例えば、道路網が図３に示すような場合、Road 2の道路データは図２に示すようになる。リンクデータLink Dataは、(1) リンク両端のノードID(NDPT11、NDPT12)、(2) リンク長ＤL、(3) リンクの制限速度を特定するスピードカテゴリーSC、(4) リンクの機能的クラスFC(Functional Class)、その他、(5) 一方通行情報、(6) レーン数、(7)Free Road/ Toll Roadの別などを含んでいる。スピードカテゴリーSCと制限速度Ｖの関係は例えば図４に示す通りであり、制限速度Ｖは0〜7の８段階に区分されている。又、リンクの機能的クラスFCは、リンクの幅員（又はレーン数）、制限速度、道路の種別など機能的要素を考慮して決定され、例えばFC=0〜5まで６段階に区分されている。FC=0はメインクラスで、フリーウェイ（freeway）を意味し、FC=1はファーストクラスで、有料道路/州間ハイウェイ(tollhway/interstate highway)を意味し、FC=2はセカンドクラスで一般国道を意味し、FC=3はサードクラスで県道を意味し、FC=4はフォースクラスで、県道以下の狭い道路を意味し、FC=5はフォースクラス以下のクラス(Less Than Fourth クラス)であり、細街路を意味する。
【００１０】
図１に戻って、１２は車両の現在位置に応じた地図画像や車両位置マーク、誘導経路等を描画するディスプレイ装置（CRT）、１３は車両位置検出部であり、図示しないが、車両の進行方位を検出する振動ジャイロ等の方位センサと所定走行距離毎に１個のパルスを発生する距離センサとGPS衛星からの電波を受信して車両の絶対位置を測位するGPS受信機とを使って車両の現在位置（緯度、経度）を算出している。
１４はリモコンであり、画面に表示されている各種メニューリストからメニューを選択したり、地図をスクロールする際に使用する。１５はナビゲーション制御部であり、(1) 地図データを用いた車両周辺の地図画像発生処理、(2) 経路探索処理、(3) 車両位置マークや誘導経路画像の発生処理などを行う。
【００１１】
ナビゲーション制御部１５において、１５ａはリモコンの操作に応じた信号を受信して各部に指示するリモコン制御部である。１５ｂは車両位置データに基づき、現在地周辺で画面表示範囲より広い範囲の地図データ（例えば９画面分の地図データ）を地図情報記憶部１１から読み出し、該地図データに基づいてドットイメージの地図画像を発生する地図画像描画部である。１５ｃは誘導経路探索処理により得られた出発地から目的地までの誘導経路データに基づいて誘導経路画像を発生する誘導経路描画部、１５ｄは地図画像及び誘導経路画像を記憶するビデオRAMである。地図画像描画部１５ｂはディスプレイ画面の表示範囲がビデオRAM １５ｄの画像範囲を超えないように、車両の走行に従って、随時、ビデオRAM１５ｄを書き換え、また誘導経路描画部１５ｃも車両の走行に応じて誘導経路画像を発生してビデオRAM １５ｄに記憶させるようになっている。１５ｅは車両の現在位置がディスプレイ画面の中心に位置するようにビデオRAM １５ｄから１画面分の地図画像を切り出す画像切り出し制御部であり、切り出し位置は地図画像描画部１５ｂから指示される。１５ｆはディスプレイ画面の中心に車両位置マークを表示するための車両位置マーク発生部である。
【００１２】
１５ｇは誘導経路探索部であり、出発地（例えば車両現在位置）、目的地が入力されると地図情報に基づいて出発地から目的地までの誘導経路を探索する。誘導経路探索部１５ｇは出発地から目的地までの交差点間のリンク旅行時間の合計が最も短くなるような経路をＡ*アルゴリズムにしたがって探索し、この経路に沿って経路誘導を行う。15g-1は制限速度補正値テーブルを記憶する記憶部であり、制限速度補正値テーブル15g-1は図５に示すように、目的地までの直線距離Ｄmgとリンクの機能的クラスFCとの組み合わせに対するリンク制限速度Ｖの補正値Ｖcを保持している。この速度補正値Ｖcは目的地までの距離が長くなる程上位クラスのリンク(道路)が経路として選択されやすくなるように決定されている。すなわち、
(1) 速度補正値Ｖcは、上位クラスほど制限速度Ｖが大になるように決定され(Ｖc>0)、又、下位クラスほど制限速度Ｖが小さくなるように決定され(Ｖc<0)、更に、
(2) 目的地までの直線距離が長くなるほど速度補正値Ｖcの絶対値が大きくなるように決定されている。
【００１３】
１５ｈは出発地から目的地までの誘導経路を記憶する誘導経路記憶部、１５ｉは合成部で、ビデオＲＡＭ１５ｄ、車両位置マーク発生部１５ｆからそれぞれ読み出された地図画像及び誘導経路画像、車両位置マーク画像を合成してディスプレイ装置１２に出力し、画像表示する。
【００１４】
（ｂ）第１の経路探索処理
Ａ*アルゴリズムは、最短経路あるいは最短時間経路を効率的に発見できるアルゴリズムである。このＡ*アルゴリズムは、探索段階においてｈ(n)，ｇ(n)の和をノードｎ（交通網における交差点）の評価ｆ(n)とする。
つまり、
ｆ(n)＝ｇ(n)＋ｈ(n)      (1)
ただし、
ｈ(n)＝ノードｎから目的地ノード到達までに必要と予測される
最小コスト（ヒューリスティック関数）
ｇ(n)＝出発地点ノードからノードｎまでの実コスト
である。このノードの評価ｆ(n)を最小にするノードが探索の各段階で枝を広げ、探索が進められる。なお、最短時間経路探索において、良好な結果を与えるヒューリスティック関数として、次式
ｈ(n)＝［ノードｎからゴールＧまでの直線距離を平均走行速度Ｖavrで除算した値］・・・(2)
が知られている。図６は評価関数の図解的説明図であり、Ｓは出発地、Ｇは目的地、ｎは着目ノードである。Ａ*アルゴリズムの特徴として、次の２点があげられる。
【００１５】
・出発地点Ｓから目的地点Ｇまでの経路があるならば、必ず経路（解）を発見することができる。
・ヒューリスティック関数ｈ(n)が、真のコストを越えないのであれば、最短時間経路を発見することができる。
道路網における２点間の直線距離は、その２点を結ぶ最短経路の距離よりも必ず小さいので、前述の(2)式におけるヒューリスティック関数ｈ(n)は真のコストを越えることがなく、従って、必ず最短時間経路を得ることができる。
【００１６】
図７は本発明のＡ*アルゴリズムの処理フローである。なお、ノードｎからノードｍに至るリンクL(n、m)のコストをcost(n,m)、あるノードｎに接続する全てのリンクを求める処理を展開するといい、前記あるノードｎを親ノード、求めたリンクの他方のノードｍを子ノードという。又、展開可能性のあるノードの集合を  OPEN、既に展開済みのノードの集合をCLOSEDとする。
初期時、集合OPENを構成するノードを出発地Ｓのみとし、集合CLOSEDを空集合とする（ステップ101）。すなわち、
OPEN：（Ｓ）
CLOSED：［ ］
とする。
【００１７】
ついで、集合OPENが空集合であるかチェックし(ステップ102）、空集合であれば最適経路探索は失敗と判定する（ステップ103）。しかし、空集合でなければ、集合OPENの先頭ノード（初期時には出発地Ｓ）を取り出してｎとする（ステップ104）。先頭ノードを取り出すことにより該ノードを集合OPENより削除する。
ついで、ノードｎが目的地Ｇであるかチェックし（ステップ105）、目的地であれば、経路探索が成功する（ステップ106）。したがって、後述するポインタを用いて目的地Ｇより出発地Ｓ方向に辿ることにより最短時間経路を得ることができる。
一方、ステップ105において、ノードｎが目的地Ｇでなければ、該ノードｎと接続する全リンクを求め、ノードｎを集合CLOSEDに入れる（ステップ 107）。以後、求めた全てのリンクＬ(n,m)の子ノードｍについて以下のステップ108a〜 108dを実行する。
【００１８】
すなわち、子ノードｍについて、評価値を次式
ｆ(n,m)＝ｇ(n)+cost(n,m)＋ｈ(m)      (3)
により計算する（ステップ108a）。上記(3)式中のｇ(n)はノードｎまでの実コストで既知である。(3)式の評価値ｆ(n,m)の計算は図８に示すフローに従って行う。  まず、リンクL(n,m)のリンク長ＤL、スピードカテゴリーSC及び機能的クラスFCを求める(ステップ201)。ついで、着目リンクL(n,m)の子ノードｍから目的地までの直線距離Ｄmgを計算し(ステップ202)、平均速度Ｖavrを用いて次式
ｈ(m)＝Ｄmg／Ｖavr          (4)
によりヒューリスティック関数ｈ(m)を計算する(ステップ203)。
【００１９】
ついで、機能的クラスFC、直線距離Ｄmgに基づいて補正値テーブル(図５参照）より速度補正値Ｖcを求める（ステップ204)。又、スピードカテゴリーSCに応じた制限速度Ｖを制限速度テーブル（図４参照）より求める（ステップ205)。しかる後、リンク通過時間cost(n,m)を次式
cost(n,m)=ＤL／（Ｖ＋Ｖc）        (5)
により計算し(ステップ206)、最後に、ｇ(n), cost(n,m)、 ｈ(m)を用いて(3)式により評価値ｆ(n,m)を計算する(ステップ207)。
以上により、評価値ｆ(n,m)が求まれば、子ノードｍが集合OPENあるいは集合 CLOSEDに含まれているかチェックする。
子ノードが集合OPEN、CLOSEDのいずれにも含まれていなければ、
▲１▼子ノードｍから親ノードｎへのポインタを作成し、
▲２▼前記評価値ｆ(n,m)をｆ(m)とし（ｆ(n,m)→ｆ(m)）、
ポインタ及び評価値ｆ(m)をそれぞれ子ノードｍに関連付け、該子ノードｍを集合OPENに入れる（ステップ 108b）。
【００２０】
一方、子ノードｍが集合OPENに含まれていれば、集合OPENの該ノードに関連付けられている評価値ｆ(m)（第１の評価値）と前記計算した評価値    ｆ(n,m)（第２の評価値）を比較する。第２の評価値が小さければ、集合OPENの前記ノードｍの評価値を第２の評価値ｆ(n,m)で更新し（ｆ(n,m)→ｆ(m)）、かつ、該ノードｍの親ノードがノードｎとなるようにポインタを更新する（ステップ108c）。しかし、第２の評価値ｆ(n,m)が第１の評価値ｆ(m)より大きければ、ステップ  108cの処理をせず、着目している子ノードｍを棄てる。
このステップ108cは、ノードｍに到る既知経路より更に評価値の良い経路が発見された場合、ポインタを更新することにより評価値のよい経路を新たな既知経路とするものである。
【００２１】
一方、子ノードｍが集合CLOSEDに含まれていれば、集合CLOSEDの該ノードに関連付けられている評価値ｆ(m)（第１の評価値）と前記計算した評価値ｆ(n,m)（第２の評価値）を比較する。第２の評価値が小さければ、集合CLOSEDにおける着目ノード（子ノードｍ）の親ノードがノードｎとなるようにポインタを更新し、かつ、該着目ノードの評価値を第２の評価値ｆ(n,m)で更新し（ｆ(n,m)→ｆ(m)）、該着目ノードを集合OPENに戻す（ステップ108d）。尚、第２の評価値ｆ(n,m)が第１の評価値より大きければ、ステップ108dの処理はせず、着目している子ノードｍを棄てる。
このステップ108dは、ノードｍに到る既知の経路より更に評価値の良い経路が発見された場合であって、該ノードｍが既に展開済みになっている場合に、ノードｍのポインタを更新することにより評価値のよい経路を新たな既知経路とし、かつ、ノードｍを新たな既知経路に関連して展開可能性があるものとして集合  OPENに復活するものである。
【００２２】
ついで、集合OPENを構成する各ノードの評価値に基づいて評価値の小さい順に並び替える（ステップ109）。これにより、評価値が最小の、現時点では最も最適と思われるノードが集合OPENの先頭ノードになる。以後、ステップ102に戻り、目的地Ｇにたどり着くまで以降の処理を繰り返す。
目的地Ｇに到着すれば、ポインタを用いて目的地Ｇより出発地Ｓに向けて辿ることにより、出発地Ｓから目的地Ｇまでの最短時間経路を得ることができる。
以上第１の経路探索処理によれば、速度補正値Ｖcを上位クラスほど制限速度Ｖが大になるように決定し(Ｖc>0)、下位クラスほど制限速度Ｖが小さくなるように決定し(Ｖc<0)、又、目的地までの直線距離が長くなるほど速度補正値Ｖcの絶対値|Ｖc|が大きくなるように決定するから、目的地までの距離が長くなるほど上位クラスのリンク(道路)を経路として選択することができる。
【００２３】
（ｃ）評価値計算の別の処理
以上では、評価値ｆ(n,m)を交差点通過時間を考慮しないで計算したが、この交差点通過時間を考慮して評価値を計算することもできる。
地図情報には、信号の有無、一時停止、信号待ち時間などの情報が含まれていない。そこで、交差点における通過時間TPSを、交差するリンクの機能的クラス及び自リンクの機能的クラスを考慮して推定し、該交差点通過時間TPSを前記リンク通過時間cost(n,m)に加算して該リンク通過時間を補正する。図９Ａに示すように走行中リンク（L11、L12)の方が交差するリンク（L21、L22)より機能的クラスFCが上位であれば、交差点通過時間を小さい時間Tsとする。逆に走行中リンクの方が交差するリンクより機能的クラスFCが下位であれば、交差点通過時間を大きな時間TL(>Ts)とする。又、図９Ｂに示すように走行中リンク（L11、L12)と交差するリンク（L21、L22)の機能的クラスFCが同じであれば、交差点通過時間を Ts,TLの中間的な時間TM(=(Ts+TL)/2)とする。
【００２４】
図１０は交差点通過時間を考慮した評価値の計算処理フローであり、ステップ205までは図８の処理フローと同じである。ステップ205において、スピードカテゴリーSCに応じた制限速度Ｖを制限速度テーブルより求めれば、cost′(n,m)を次式
cost′(n,m)=ＤL／（Ｖ＋Ｖc）        (5)′
により計算する(ステップ211)。ついで、子ノードｍで交差するリンクの機能的クラスFCが自リンクより上位のクラスかチェックし(ステップ212)、上位のクラスであれば交差点通過時間TPS=TLとし(ステップ213a)、下位のクラスであれば交差点通過時間TPS=TSとし(ステップ213b)、同一クラスであれば交差点通過時間  TPS=TMとする(ステップ213c)。
【００２５】
ついで、リンク通過時間cost(n,m)を次式
cost(n,m)=cost′(n,m)+TPS      (6)
により計算し(ステップ214)、最後に、ｇ(n), cost(n,m)、 ｈ(m)を用いて(3)式により評価値ｆ(n,m)を計算する(ステップ215)。
【００２６】
（ｄ）第２の経路探索処理
図７の第１の経路探索では、全リンクを対象にＡ*アルゴリズムを適用した。しかし、全リンクを対象にすると探索時間が長くなる。そこで、第２の経路探索では、(1) 出発地が属するリンクの機能的クラスFCと同一クラスのリンクを用いて上位クラスのリンクに到達するまで該出発地より目的地に向けて経路探索を行い、(2) 同様に、目的地が属するリンクの機能的クラスと同一クラスのリンクを用いて上位クラスのリンクに到達するまで該目的地より出発地に向けて経路探索を行い、(3) 出発地より探索した上位クラスのリンクのノードを新たな出発地とし、又、目的地より探索した上位クラスのリンクのノードを新たな目的地とし、(4) 該上位クラスのリンクを用いて上記処理を繰り返し、(5) 所定クラスにおいて目的地に到達すれば、出発地側から求めた各クラスの探索経路と目的地側から求めた各クラスの探索経路を順番に接続して誘導経路を形成する。ただし、前記新たな出発地を１つのノードとするリンクのクラスと、前記新たな目的地を１つのノードとするリンクのクラスは同じである。
【００２７】
図１１は本発明の第２の経路探索処理フローである。
まず、出発地（車両現在位置）と目的地を入力し（ステップ301)、ｉ=5(最下位の機能的クラス）とする（ステップ302）。ついで、出発地よりFC=iのリンクのみを用いて図７の第１の経路探索処理を行い(ステップ303)、目的地に到達したかチェックする(ステップ304)。目的地に到達してなければ、FC=j(>i)の上位クラス（上層）のリンクまで探索できたかチェックし（ステップ305)、「NO」であれば、ステップ303以降の処理を繰り返す。
ステップ305で、「YES」となれば、目的地よりFC=iのリンクのみを用いて図７の第１の経路探索処理を行い(ステップ306)、FC=j(>i)の上層ノードまで探索できたかチェックし（ステップ307)、「NO」であれば、ステップ306以降の処理を繰り返す。FC=j(>i)の上層ノードまで探索できれば、出発地から上層リンクまでの経路S(FC)、目的地から上層リンクまでの経路G(FC)を保存する(ステップ308)。
【００２８】
ついで、j→iとし(ステップ 309)、出発地側の上層リンクのノードＮsを新たな出発地、目的地側の上層リンクのノードＮGを新たな目的地とし(ステップ310)、ステップ303以降の処理を繰り返す。
以後、上記処理が繰り返され、最終的にステップ304において目的地に到達すれば、保存してある出発地側から求めた各クラスの探索経路S(5),S(4),S(3),S(2),S(1),S(0)と目的地側から求めた各クラスの探索経路G(5),G(4),G(3),G(2),G(1),G(0)を順番に接続して誘導経路
S(5)→S(4)→S(3)→S(2)→S(1)→S(0)→G(0)→G(1)→G(2)→G(3)→G(4)→G(5)を形成する(ステップ311)。尚、ステップ303の経路探索処理において、評価値が等しければ、機能的クラスが上位のリンクが選ばれるように経路探索を行う。
【００２９】
第２の経路探索処理によれば、各リンクに機能的クラスを割付け、出発地及び目的地がFC=iのノードであれば、FC=iのみのリンクを用いて経路探索し、上位クラスj(>i)のリンクに到達すれば、上位クラスFC=jのみのリンクを用いて経路探索し、以下同様に経路探索するから、経路探索対象のリンク数が少なくなり、短時間で目的地までの経路を探索できる。
又、第２の経路探索によれば、速度補正値Ｖcを上位クラスほど制限速度Ｖが大になるように決定し(Ｖc>0)、下位クラスほど制限速度Ｖが小さくなるように決定し(Ｖc<0)、又、目的地までの直線距離が長くなるほど速度補正値Ｖcの絶対値|Ｖc|が大きくなるように決定するから、素早く上位クラスのリンクに到達することができ、探索時間を短縮できる。すなわち、上位クラスほどリンク数が少なく、かつ、エリアが広くなるから、素早く上位クラスのリンクに到達することにより探索時間を短縮できる。
【００３０】
以上では経路探索法としてＡ*アルゴリズムを用いた場合について説明したが、ダイクストラ法など別の経路探索処理を適用することもできる。
以上、本発明の実施例により説明したが、本発明は請求の範囲に記載した本発明の趣旨に従い種々の変形が可能であり、本発明はこれらを排除するものではない。
【００３１】
【発明の効果】
以上本発明によれば、目的地までの距離が長くなれば少々距離が長くなってもフリーウェイ等のメインの道路を選択しやすくできる。
又、本発明によれば、短時間で目的地までの経路を探索することができる。
又、本発明によれば、交差点における信号待ち、一時停止待ちなど交差点通過時間を考慮した経路探索を行うことができる。
【図面の簡単な説明】
【図１】本発明の車載ナビゲーション装置の全体構成図である。
【図２】地図データ説明図である。
【図３】道路データ説明図である。
【図４】スピードカテゴリーと制限速度の関係図である。
【図５】制限速度補正値テーブル説明図である。
【図６】Ａ*アルゴリズムにおける評価関数の図解的説明図である。
【図７】本発明のＡ*アルゴリズムによる経路探索処理フローである。
【図８】評価値の計算処理フローである。
【図９】図９Ａ、図９Ｂは交差点通過時間説明図である。
【図１０】交差点通過時間を考慮した評価値の計算処理フローである。
【図１１】本発明の第２の経路探索処理フローである。
【符号の説明】
１１  地図情報記憶部
１２  ディスプレイ装置（CRT）
１３  車両位置検出部
１４  リモコン
１５  ナビゲーション制御部
１５ａ  リモコン制御部
１５ｂ  地図画像描画部
１５ｃ  誘導経路描画部
１５ｄ  ビデオRAM
１５ｅ  画像切り出し制御部
１５ｆ  車両位置マーク発生部
１５ｇ  誘導経路探索部
１５ｈ  誘導経路記憶部
１５ｉ  合成部
【図１】
0004353658.tif 000002
【図２】
0004353658.tif 000003
【図３】
0004353658.tif 000004
【図４】
0004353658.tif 000005
【図５】
0004353658.tif 000006
【図６】
0004353658.tif 000007
【図７】
0004353658.tif 000008
【図８】
0004353658.tif 000009
【図９】
0004353658.tif 000010
【図１０】
0004353658.tif 000011
【図１１】
0004353658.tif 000012