JPH08106597A - 車載用ナビゲーション装置 - Google Patents

Abstract

(57)【要約】 【目的】 経路誘導を受けて走行中に渋滞に巻き込まれ
たき、渋滞を迂回して目的地に到達できる新たな経路誘
導を可能とする。 【構成】 経路誘導時、地図画像描画部１８はＧＰＳ受
信機２で検出された車両位置に基づき経路探索部１４に
よって探索され誘導経路記憶部１５に記憶された出発地
−目的地間の誘導経路データとＣＤ−ＲＯＭ１の地図デ
ータを用いて、車両位置を中心とする地図画像を誘導経
路、車両位置マークとともに描画し、ディスプレイ装置
４に画面表示させる。一方、計測部１６はＧＰＳ受信機
２で検出された車両速度に基づき車両速度が20km/h以下
となっている状態の継続時間を計測する。判別部１８は
計測された継続時間が３分を越えると再探索指令を経路
探索部１４に与え、再探索指令を受けた経路探索部１４
は地図データを用いて渋滞を迂回して目的地に到達する
最適経路を再探索し、誘導経路データを修正する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は車載用ナビゲーション装
置に係り、特に地図データを用いて出発地と目的地を結
ぶ最適な経路を自動探索し、探索した誘導経路データを
用いて経路誘導を行うようにした車載用ナビゲーション
装置に関する。

【０００２】

【従来の技術】車載用ナビゲーション装置は、地図デー
タを記憶したＣＤ−ＲＯＭ、ＩＣメモリカード等の地図
データ記憶装置、ディスプレイ装置、ＧＰＳ受信機等の
車両の現在位置、現在方位を検出する車両位置検出装置
等を有し、車両の現在位置を含む地図データをＣＤ−Ｒ
ＯＭ等から読み出し、該地図データに基づいて車両位置
を中心とする地図画像を描画し、ディスプレイ画面に表
示するとともに、車両位置マーク（ロケーションカーソ
ル）をディスプレイ画面の画面中央に固定し、車両の移
動に応じて地図画像をスクロール表示したり、地図画像
を画面に固定し車両位置マークを移動させたりして、車
両が現在どこを走行しているか一目で判るようにしてあ
る。

【０００３】ＣＤ−ＲＯＭ等に記憶されている地図は、
1/12500 、1/25000 、1/50000 、1/100000などの縮尺レ
ベルに応じて適当な大きさの経度幅、緯度幅に区切られ
ており、道路等は経緯度で表現された頂点（ノード）の
座標集合で示される。なお、道路は２以上のノードの連
結からなり、２つのノードを連結した部分はリンクと呼
ばれる。地図データには、（１）道路リスト、ノードテ
ーブル、交差点構成ノードリスト、交差点ネットリスト
などからなるマップマッチング、経路探索用の道路レイ
ヤ、（２）地図画面上に道路、建物、施設、公園、河川
等を表示するための背景レイヤ、（３）市町村名などの
行政区画名、道路名、交差点名、建物の名前等の文字、
地図記号等を表示するための文字・記号レイヤなどから
構成されている。

【０００４】車載用ナビゲーション装置には、運転者が
所望の目的地に向けて道路を間違うことなく容易に走行
できるようにした経路誘導機能を搭載したものがあり、
この経路誘導機能によれば地図データを用いて或る出発
地から或る目的地までを結ぶ最短の経路を横型探索法、
ダイクストラ法等のシュミレーション計算を行って自動
探索し、誘導経路データとして記憶しておき、走行中、
地図画像上に誘導経路を他の道路とは色を変えて太く描
画し、画面表示したり、車両が誘導経路上の進路を変更
すべき交差点に一定距離内に近づいたとき、地図画像上
の進路を変更すべき交差点に進路を示す矢印を描画し、
画面表示したりすることで、目的地に向けた最適な経路
をユーザが簡単に把握できるようになっている。更に、
経路再探索機能付であれば経路誘導を受けて走行中に車
両が誘導経路から外れた場合、その時点の車両位置から
目的地までを結ぶ最適な経路を再び自動探索し、誘導経
路データを修正する。これにより、寄り道等で車両が誘
導経路から外れても新たに探索された誘導経路に従い目
的地に向けた経路誘導を受けることができる。

【０００５】

【発明が解決しようとする課題】ところで、従来の経路
誘導機能では目的地に向け走行している途中で車両が渋
滞に巻き込まれた場合、そのまま経路誘導に従うと渋滞
の中をイライラしながら走行しなければならず、また、
目的地に到達するのに非常に時間が掛かってしまう問題
があった。一方、経路再探索機能が有るとき、渋滞を回
避するため誘導経路を外れれば目的地までを結ぶ新たな
誘導経路が探索されるので、このあとの経路誘導により
渋滞を迂回しながら目的地に到達できる場合も有るが、
元の誘導経路から適切な方向に外れないと、行き止まり
のため元の誘導経路に戻る経路が再探索されてしまい、
渋滞を何ら回避することができない場合があった。

【０００６】以上から本発明の目的は、経路誘導を受け
て走行中に渋滞に巻き込まれても、渋滞を迂回して目的
地に到達できる新たな経路誘導を行えるようにした車載
用ナビゲーション装置を提供することにある。

【０００７】

【課題を解決するための手段】上記課題は、本発明にお
いては、地図データを記憶した地図データ記憶手段と、
車両位置と車両方位を検出する車両位置検出手段と、地
図データを用いて出発地と目的地を結ぶ最適な経路を自
動探索し、誘導経路データとして誘導経路記憶手段に記
憶させる経路探索手段と、地図データを用いて車両位置
周辺の地図画像を車両位置マークとともに描画し、表示
手段に画面表示させる地図画像描画手段と、誘導経路デ
ータを用いて経路誘導を行う経路誘導手段とを備えた車
載用ナビゲーション装置において、車両速度を検出する
車両速度検出手段と、車両速度が一定以下となった状態
の継続時間を計測する計測手段と、計測手段で計測した
継続時間を所定の基準値と比較し、渋滞が発生している
か判別する判別手段とを備え、前記経路探索手段は経路
誘導中に判別手段で渋滞が発生していると判別されたと
き、地図データを用いて現在位置から渋滞を迂回して目
的地までを結ぶ最適な経路を再探索し、誘導経路記憶手
段に記憶された誘導経路データを修正することにより達
成される。

【０００８】

【作用】本発明によれば、車両速度が一定以下となった
状態の継続時間を計測し、該計測した継続時間を所定の
基準値と比較して渋滞が発生しているか判別し、経路誘
導中に渋滞が発生していると判別されたとき、地図デー
タを用いて現在位置から渋滞を迂回して目的地までを結
ぶ最適な経路を再探索し、誘導経路データを修正する。
これにより、経路誘導を受けて目的地に向け走行中に渋
滞に巻き込まれても、自動的に現在位置から渋滞を迂回
して目的地に到達できる最適な経路に切り換えて経路誘
導を受けることができ、所望の目的地に速やかに到達す
ることができる。

【０００９】

【実施例】図１は本発明の一実施例に係る車載用ナビゲ
ーション装置の全体構成図である。図中、１は縮尺別の
道路レイヤ、背景レイヤ、文字・記号レイヤなどから構
成された地図データを記憶したＣＤ−ＲＯＭ、２は車両
位置、車両方位、車両速度を衛星航法により検出するＧ
ＰＳ受信機である。３は地図スクロール用のカーソルキ
ー、目的地入力キー等を有する操作部、４は地図画像を
車両位置マーク、誘導経路などとともに表示するディス
プレイ装置である。

【００１０】１０はマイコン構成のナビゲーションコン
トローラであり、ＣＤ−ＲＯＭ１に記憶された地図デー
タを用いて車両の現在位置を含む地図画像を車両位置マ
ークとともに描画し、ディスプレイ装置４に画面表示さ
せたり、目的地が入力されると、地図データを用いて出
発地である現在位置からユーザ所望の目的地までを結ぶ
最短の経路を横型探索法により自動探索し、誘導経路と
して記憶したのち、地図画像上に他の道路とは異なる色
で誘導経路を描画し、車両位置マークとともに画面表示
させて経路誘導を行う。また、ナビゲーションコントロ
ーラ１０は、経路誘導中に車両が渋滞に巻き込まれたと
き渋滞を迂回して目的地に到達することのできる最短の
経路を再探索し、誘導経路データを修正する。

【００１１】ナビゲーションコントローラ１０の内、１
１はＣＤ−ＲＯＭ１から読み出された地図データを格納
するバッファメモリ、１２はカーソルキーの操作に従い
カーソル位置を計算するカーソル位置計算部、１３は目
的地入力キーが押圧された時点のカーソル位置を目的地
として設定する目的地設定部、１４は目的地が設定され
ると、ＣＤ−ＲＯＭ１から必要な地図データをバッファ
メモリ１１に読み出し、現在位置を出発地とし該出発地
から目的地までを結ぶ最短の経路をバッファメモリ１１
に読み出した地図データを用いて横型探索法により探索
する経路探索部である。１５は経路探索部１４で探索さ
れた経路を構成するノードデータを経路順に並べたノー
ドデータ列を誘導経路データとして記憶する誘導経路記
憶部であり、図２に示す如く、各ノードデータは経度、
緯度の座標データと、交差点ノードか否かを示す交差点
識別フラグを含む。

【００１２】１６はＧＰＳ受信機２で検出された車両速
度が一定以下（ここでは一例として20km/h以下とする）
となった状態の継続時間を計測する計測部、１７は計測
部１６で計測した継続時間を所定の基準値（ここでは一
例として３分とする）と比較して渋滞が発生しているか
判別する判別部であり、計測部１６で計測した継続時間
が基準値を上回った場合に渋滞が発生していると判別し
て経路探索部１４に対し渋滞を迂回して目的地に到達で
きる誘導経路の再探索指令を与える。

【００１３】１８は地図画像描画部であり、経路誘導し
ないときはＧＰＳ受信機２で検出された車両位置と車両
方位に基づき、ＣＤ−ＲＯＭ１に記憶された内、車両位
置を含む地図データをバッファメモリ１１に読み出し、
該読み出した地図データを用いて車両位置を中心とする
北を上向きにした地図画像を車両位置マークとともに描
画する。経路誘導するときは更に、誘導経路記憶部１５
の中から地図画像の描画エリアに入っている誘導経路デ
ータを読み出し、地図画像に重ねて通常の道路とは異な
る特定色で太く強調した誘導経路を描画する。１９は地
図画像描画部１８の描画した画像を記憶するビデオＲＡ
Ｍ、２０はビデオＲＡＭ１９に記憶された画像を読み出
し、所定の映像信号に変換してディスプレイ装置４に出
力する映像変換部である。

【００１４】道路レイヤ 地図データ中の道路レイヤは図３に示す構成を有してい
る。道路リストＲＤＬＴは道路別に、道路の種別、道路
を構成する全ノード数、道路を構成するノードのノード
テーブルＮＤＴＢ上での位置と、次のノードまでの幅員
等のデータより構成されている。交差点構成ノードリス
トＣＲＬＴは地図上の各交差点毎に、該交差点に連結す
るリンク他端ノード（交差点構成ノードという）のノー
ドテーブルＮＤＴＢ上での位置の集合である。ノードテ
ーブルＮＤＴＢは地図上の全ノードのリストであり、ノ
ード毎に位置情報（経度、緯度）、該ノードが交差点で
あるか否かの交差点識別フラグ、交差点であれば交差点
構成ノードリスト上での位置を指し、交差点でなければ
道路リスト上で当該ノードが属する道路の位置を指すポ
インタ等で構成されている。

【００１５】また、交差点ネットリストＣＲＮＬは、図
４に示す如く構成されていて、固定データ領域ＦＤＡ
に、 （１）交差点シーケンシャル番号（当該交差点を特定す
る情報） （２）該交差点ノードが含まれる地図の図葉番号 （３）データユニットコード 以上、交差点ノードＩＤ （４）交差点構成ノード数 （５）各隣接交差点のシーケンシャル番号 （６）各隣接交差点までの距離 （７）各隣接交差点までの道路の属性（道路種別、幅
員） 等を有している。１つの交差点ネットリストには最大で
７つの隣接交差点データが格納されている。また、交差
点ネットリストＣＲＮＬは書き換えデータ領域ＲＤＡを
有しており、経路探索時に、累計距離及び１つ手前の
（次数の１つ少ない）交差点のシーケンシャル番号、検
索次数を格納できるようになっている。

【００１６】経路探索部１４はユーザの目的地入力操作
に基づき目的地が設定されると、交差点ネットリストＣ
ＲＮＬに格納された交差点間距離をそのまま用いて出発
地−目的地間を結ぶ最短の誘導経路を横型探索法により
探索する。その後、判別部１７から経路再探索指令を受
けたとき、既に探索してある誘導経路データの中から車
両の進行方向前方で現在位置から一定距離Ｌ₀ 以上離れ
た最寄りの交差点ＣＰ ₁ とＬ₁ （＝Ｌ₀ ＋Ｌ）以上離れ
た最寄りの交差点ＣＰ₂ との２つの交差点を選び出す。
そして、選び出した２つの交差点間の誘導経路に乗って
いる各交差点に対応する交差点ネットリストＣＲＮＬに
対し、当該選び出した２つの交差点間の誘導経路に沿っ
た部分の隣接交差点間距離（図４の項番９等参照）は極
めて大きな距離に置き換えておく。しかるのち、当該選
び出した２つの交差点の内、現在位置に近い方の交差点
ＣＰ₁ から遠い方の交差点ＣＰ₂ までを結ぶ最短の経路
を横型探索法により探索し、探索した経路で元の誘導経
路の一部を置き換え修正する。なお、Ｌ₀ はここでは車
両が20km/hで走行してもＣＰ₁ に到達する前に再探索を
十分に完了できる距離でなるべく小さな値であり、１分
程度で再探索を完了できるとしてＬ₀ ＝350mとする。Ｌ
は渋滞の予想長さであり、ここでは一例として５kmとす
る。

【００１７】図５〜図７はナビゲーションコントローラ
１０の動作を示す流れ図、図８は車両位置周辺の道路を
示す説明図、図９は横型探索法による経路探索方法の説
明図、図１０は画面表示例の説明図であり、以下、これ
らの図に従って説明する。経路探索 電源がオンされると、ＧＰＳ受信機２は衛星航法により
定期的に車両位置、車両方位、車両速度の検出を行う。
一方、ナビゲーションコントローラ１０はＧＰＳ受信機
２から車両位置データ、車両方位データを入力し（図５
のステップ１０１）、地図画像描画部１８が車両位置を
含む地図データをＣＤ−ＲＯＭ１からバッファメモリ１
１に読み出し、該読み出した地図データを用いて車両位
置を中心とする北を上向きにした地図画像をビデオＲＡ
Ｍ１９に描画し、更に、地図画像の中心に車両方位方向
を向けた車両位置マークを描画する。ビデオＲＡＭ１９
に描画された画像は映像変換部２０により読み出され、
所定の映像信号に変換されたのちディスプレイ装置４に
出力されて画面表示される（ステップ１０２）。

【００１８】このあと、ナビゲーションコントローラ１
０はカーソルキーにより地図スクロール操作がなされた
かチェックし（ステップ１０３）、ＮＯであればステッ
プ１０１に戻ってＧＰＳ受信機２から新たな車両位置デ
ータ、車両方位データを入力し、新たな車両位置を中心
とする地図画像を車両位置マークとともに描画し、画面
表示させる。以下、同様の処理が繰り返されることで車
両の走行に従い画面では車両位置が中央に固定したまま
地図がスクロールしていく。

【００１９】その後、ユーザが現在位置を出発地とし、
所望の目的地まで最適な経路に沿って走行したいとき、
カーソルキーにより地図スクロール操作を行い、目的地
を探す。このときカーソルキーの操作が開始されたとこ
ろで、カーソル位置計算部１２がＧＰＳ受信機２で検出
されている現在の車両位置を初期カーソル位置として初
期設定したのち（ステップ１０３、１０４）、カーソル
キーの操作に従いカーソル位置を連続的に変化させてい
く（ステップ１０６、１０７）。また、地図画像描画部
１８はＣＤ−ＲＯＭ１からカーソル位置を含む地図デー
タをバッファメモリ１１に読み出し、該読み出した地図
データを用いてカーソル位置を中心とする北を上向きに
した地図画像をビデオＲＡＭ１９に描画し、地図画像上
の中心にカーソルマークを描画する。ビデオＲＡＭ１９
の画像は映像変換部２０により読み出され、所定の映像
信号に変換されてディスプレイ装置４に出力される（ス
テップ１０５）。この結果、画面の地図画像はカーソル
キーの操作に従いスクロールしかつ中心にカーソルマー
クが表示される。

【００２０】カーソルが目的地に合ったところで目的地
入力キーを押圧すると（ステップ１０８でＹＥＳ）、目
的地設定部１３はその時点のカーソル位置を目的地とし
て設定し、経路探索部１４に目的地データとして出力す
る（ステップ１０９）。目的地データを入力した経路探
索部１４はＧＰＳ受信機２で検出されている現在位置を
出発地として設定する（ステップ１１０）。そして、出
発地から目的地までが入る範囲の地図データをＣＤ−Ｒ
ＯＭ１からバッファメモリ１１に読み出し、該読み出し
た地図データ中の特に道路レイヤを用いて出発地から目
的地までを結ぶ最短の経路を横型探索法により探索す
る。

【００２１】具体的な探索処理の仕方を図９を参照して
説明する。なお、ここでは簡単のため、どの交差点の交
差点ネットリストＣＲＮＬにも、第１〜第４の４つの隣
接交差点が含まれているものとし、図９における下隣が
第１隣接交差点、右隣が第２隣接交差点、上隣が第３隣
接交差点、左隣が第４隣接交差点になっているものとす
る。

【００２２】最初、経路探索部１４は出発地が交差点で
あるか調べ（図６のステップ２０１）、交差点であれば
出発地交差点ＳＴＰとし（ステップ２０２）、ステップ
２０４以降の処理を行い、交差点でなければ、最寄りの
交差点を出発地交差点ＳＴＰとし（ステップ２０３）、
ステップ２０４以降の処理を行う。出発地交差点ＳＴＰ
が決まれば、経路探索部１４は目的地が交差点であるか
調べ（ステップ２０４）、交差点であれば目的地交差点
ＤＳＰとし（ステップ２０５）、ステップ２０７以降の
処理を行い、交差点でなければ、最寄りの交差点を目的
地交差点ＤＳＰとし（ステップ２０６）、ステップ２０
７以降の処理を行う。

【００２３】出発地交差点ＳＴＰ及び目的地交差点ＤＳ
Ｐが決まれば、経路探索部１４はまず、出発地交差点Ｓ
ＴＰを中心とし、該出発地交差点ＳＴＰと目的地交差点
ＤＳＰ間より少し長い距離を半径とする円内に含まれる
全ての交差点の交差点ネットリストＣＲＮＬをＣＤ−Ｒ
ＯＭ１の地図データから読み出し、バッファメモリ１１
に記憶しておく（ステップ２０７）。そして、検索次数
ｉを０とする（ステップ２０８）。バッファメモリ１１
に記憶された第ｉ次交差点に係る交差点ネットリストＣ
ＲＮＬを参照して、当該第ｉ次交差点に隣接する交差点
が残存するかを調べる（ステップ２０９）。０次交差点
は出発地交差点ＳＴＰである。なお、ステップ２０９で
は、それまでに第ｊ次交差点（ｊ＝０，１，・・，ｉ）
とされたものは除く。

【００２４】ここでは、４つの隣接交差点が残存するの
で、最初の第１隣接交差点Ａ₁ について、出発地交差点
ＳＴＰに係る交差点ネットリストＣＲＮＬの中の出発地
交差点ＳＴＰから第１隣接交差点Ａ₁ までの距離ｄ₂ を
参照して、出発地交差点ＳＴＰから隣接交差点Ａ₁ まで
の累計距離Ｄを計算する（ステップ２１０）。Ｄは出発
地交差点ＳＴＰから第ｉ次交差点までの累計距離をｄ₁
とすると、次式 ｄ₁ ＋ｄ₂ →Ｄ により求まる。初めｉ＝０のときはｄ₁ ＝０なのでＤ＝
ｄ₂ となる。

【００２５】次いで、バッファメモリ１１に記憶された
交差点Ａ₁ に係る交差点ネットリストＣＲＮＬの書き換
えデータ領域ＲＤＡを参照して、隣接交差点Ａ₁ の検索
次数が（ｉ＋１）となっているか、換言すれば、既に、
交差点Ａ₁ につき、異なる経路での累計距離及び１つ手
前の交差点を特定する情報が登録済かチェックし（ステ
ップ２１１）、ここではＮＯとなるので、当該隣接交差
点Ａ₁ に対応させるようにして、交差点Ａ₁ に係る交差
点ネットリストＣＲＮＬの中に、（ａ）現在着目してい
る第０次交差点ＳＴＰのシーケンシャル番号、（ｂ）出
発地交差点ＳＴＰから当該隣接交差点Ａ₁ までの累計距
離Ｄ（＝Ａｄ₁）、を書き換えデータ領域ＲＤＡに記憶
し、（ｃ）当該隣接交差点Ａ₁ の検索次数としての（ｉ
＋１）＝１を書き換えデータ領域ＲＤＡに記憶する（ス
テップ２１２）。

【００２６】そして、ステップ２０９に戻り、出発地交
差点ＳＴＰを対象とした交差点ネットリストＣＲＮＬを
参照して、着目している第０次交差点に隣接する交差点
がなお残存するか調べ、残存すれば同様の処理を繰り返
す。この結果、出発地交差点ＳＴＰの交差点ネットリス
トに隣接交差点Ａ₁ 〜Ａ₄ が存在しているので、これら
が１次交差点とされ、かつ、これら１次交差点に係る交
差点ネットリストＣＲＮＬの各データ書き換え領域に
は、累計距離Ａｄ₁ 〜Ａｄ₄ 及び各隣接交差点Ａ ₁ 〜Ａ
₄ に対応する１つ手前の交差点ＳＴＰを特定するシーケ
ンシャル番号が登録される。

【００２７】出発地交差点ＳＴＰを対象とした交差点ネ
ットリストＣＲＮＬに含まれる全ての隣接交差点につき
処理が終わると、経路探索部１４は、出発地交差点ＳＴ
Ｐ以外に第０次交差点が存在するか判断し（図６のステ
ップ２０９、図７のステップ３０１）、存在しないの
で、続いて目的地交差点ＤＳＰに到達したか、換言すれ
ば第（ｉ＋１）次交差点とした中に目的地交差点ＤＳＰ
が含まれているか判断し（ステップ３０２）、まだであ
れば、ｉをインクリメントして１とする（ステップ３０
３）。そして、図６のステップ２０９へ進み、第１次交
差点とされた中の１つＡ₁ に着目して、バッファメモリ
１１に記憶された交差点Ａ₁ に係る交差点ネットリスト
ＣＲＮＬを参照して、第０次交差点ＳＴＰを除き、隣接
交差点が残存するか判断する。

【００２８】ここでは、Ｂ₁₁，Ｂ₁₂，Ｂ₁₄が存在するの
で、この内、まず第１隣接交差点Ｂ ₁₁について、交差点
Ａ₁ に係る交差点ネットリストＣＲＮＬを参照しなが
ら、出発地交差点ＳＴＰから隣接交差点Ｂ₁₁までの累計
距離Ｄを計算する（ステップ２１０）。出発地交差点Ｓ
ＴＰから現在着目している第１次交差点Ａ₁ までの累計
距離ｄ₁ はバッファメモリ１１に、交差点Ａ₁ に係る交
差点ネットリストＣＲＮＬのＲＤＡにＡｄ₁ として記憶
されており、第１次交差点Ａ₁ から当該隣接交差点Ｂ₁₁
までの距離ｄ₂ は交差点Ａ₁ に係る交差点ネットリスト
ＣＲＮＬに記憶されているから、Ａｄ₁ ＋ｄ₂ →Ｄによ
り出発地交差点ＳＴＰから第１次交差点Ａ₁ を経由した
当該隣接交差点Ｂ₁₁までの累計距離Ｄが求まる。

【００２９】次いで、バッファメモリ１１に記憶された
隣接交差点Ｂ₁₁に係る交差点ネットリストＣＲＮＬの書
き換えデータ領域ＲＤＡを参照して、隣接交差点Ｂ₁₁の
検索次数が（ｉ＋１）かチェックし（ステップ２１
１）、ここではＮＯとなるので、当該隣接交差点Ｂ₁₁に
対応させるようにして、交差点Ｂ₁₁に係る交差点ネット
リストＣＲＮＬの中に、（ａ）現在着目している第１次
交差点Ａ₁ のシーケンシャル番号、（ｂ）出発地交差点
ＳＴＰから当該隣接交差点Ｂ₁₁までの累計距離Ｄ（＝Ｂ
ｄ₁）、を書き換えデータ領域ＲＤＡに記憶し、（ｃ）
当該隣接交差点Ｂ₁₁の検索次数としての（ｉ＋１）＝２
を書き換えデータ領域ＲＤＡに記憶する（ステップ２１
２）。そしてステップ２０９に戻り、バッファメモリ１
１に記憶された第１次交差点Ａ₁ に係る交差点ネットリ
ストＣＲＮＬを参照して、現在着目している第１次交差
点Ａ₁ に隣接する交差点がなお残存するか調べ、残存す
れば同様の処理を繰り返す。

【００３０】経路探索部１４はステップ２０９に戻ると
隣接交差点Ｂ₁₂，Ｂ₁₄が存在しているのでＹＥＳと判断
する。そして、この内、第２隣接交差点Ｂ₁₂について、
出発地交差点ＳＴＰから隣接交差点Ｂ₁₂までの累計距離
Ｄを計算したあと（ステップ２１０）、バッファメモリ
１１に記憶された隣接交差点Ｂ₁₂に対応する交差点ネッ
トリストＣＲＮＬのデータ書き換え領域ＲＤＡを参照し
て検索次数が既に２となっているかチェックし（ステッ
プ２１１）、ＮＯなので、データ書き換え領域ＲＤＡに
第１次交差点Ａ₁ のシーケンシャル番号と累計距離Ｄ＝
Ｂｄ₁₂、検索次数２を登録する（ステップ２１２）。そ
して、ステップ２０９に戻って、前述と同様にして、交
差点Ａ₁ の交差点ネットリストＣＲＮＬに記憶された残
りの隣接交差点Ｂ₁₄につき処理する。

【００３１】Ｂ₁₄についての処理が終わると、経路探索
部１４は、他の第１次交差点が存在するかチェックし
（図７のステップ３０１）、ここではまだＡ₂ ，Ａ₃ ，
Ａ₄ が存在するので、続いてＡ₂ を新たな第１次交差点
として図６のステップ２０９以降の処理を行う（ステッ
プ３０４）。

【００３２】交差点Ａ₂ の交差点ネットリストＣＲＮＬ
に第１〜第４隣接交差点Ｂ₂₁〜Ｂ₂₄が存在しているが、
Ｂ₂₄＝出発地交差点ＳＴＰなので、第４隣接交差点Ｂ₂₄
はステップ２０９で外して処理される。そして、まずＢ
₂₁について、経路探索部１４は、交差点Ａ₂ の交差点ネ
ットリストＣＲＮＬを参照して、出発地交差点ＳＴＰか
ら第１次隣接交差点Ａ₂ を経由した隣接交差点Ｂ₂₁まで
の累計距離Ｄを計算する（ステップ２０９、２１０）。

【００３３】続いて、経路探索部１４はバッファメモリ
１１に記憶された隣接交差点Ｂ₂₁の交差点ネットリスト
ＣＲＮＬを参照して隣接交差点Ｂ₂₁の次数が２かチェッ
クするが（ステップ２１１）、Ｂ₂₁＝Ｂ₁₂であり、隣接
交差点Ｂ₁₂の次数が既に２となっているためＹＥＳとな
る。これは、先に第１次交差点Ａ₁ に隣接する交差点Ｂ
₁₂として処理済み（前記（ａ）〜（ｃ）のデータが記憶
済み）であることを示すが、この場合、まず、該隣接交
差点Ｂ₁₂に係る交差点ネットリストＣＲＮＬの書き換え
データ領域ＲＤＡに記憶してある出発地交差点ＳＴＰか
らの累計距離＊Ｄ＝Ｂｄ₁₂と今回ステップ２１０で求め
た距離Ｄの大小を比較する（ステップ２１３）。

【００３４】Ｄ＜＊Ｄであれば、当該隣接交差点Ｂ
₁₂（＝Ｂ₂₁）の交差点ネットリストＣＲＮＬの書き換え
データ領域ＲＤＡに記憶してある第ｉ次交差点Ａ₁ のシ
ーケンシャル番号を現在着目している第ｉ次交差点Ａ₂
のシーケンシャル番号で置き換えるとともに、累計距離
＊ＤをＤ＝Ｂｄ₂₁で書き換える（ステップ２１４）。Ｄ
≧＊ＤであればＲＤＡの書き換えはしない。このあと、
ステップ２０９に戻り、第１次交差点Ａ₂ に係る次の隣
接交差点について、同様の処理を行う。

【００３５】以下、同様の処理を順次繰り返していき、
図７のステップ３０２のチェックにおいて、第（ｉ＋
１）次とされた全ての交差点の中に目的地交差点ＤＳＰ
が含まれていて、ＹＥＳと判断されたとき、まず、バッ
ファメモリ１１に記憶された目的地交差点ＤＳＰに係る
交差点ネットリストＣＲＮＬの中で、書き換えデータ領
域ＲＤＡに記憶してある当該目的地交差点ＤＳＰ（ｍ次
の交差点とする）に対応する１つ手前の（ｍ−１）次交
差点、該（ｍ−１）次の交差点に係る交差点ネットリス
トＣＲＮＬの中で、書き換えデータ領域ＲＤＡに記憶し
てある当該交差点に対応する１つ手前の（ｍ−２）次交
差点、・・・、２次の交差点に係る交差点ネットリスト
ＣＲＮＬの中で、書き換えデータ領域ＲＤＡに記憶して
ある１次交差点、出発地交差点ＳＴＰを、逆順に結んで
累計距離で見た最短の最適経路を決定し、出発地交差点
ＳＴＰから目的地交差点ＤＳＰまでの最適経路を構成す
る交差点ノード列を基本誘導経路とする。そして、地図
データ中の道路レイヤを参照して基本誘導経路中の交差
点ノード間に単純ノード（交差点でないノード）を補間
したノードデータ列を最終的な誘導経路データとし、誘
導経路記憶部１５に記憶させる（ステップ３０５）。こ
の際、誘導経路上の交差点ノードについては交差点識別
フラグを立てておく。今回、探索された誘導経路は図８
に破線ＧＲで示す如くなったものとする。

【００３６】経路誘導 誘導経路の探索が終わると、ナビゲーションコントロー
ラ１０はＧＰＳ受信機２から車両位置データ、車両方位
データ、車両速度データを入力し（ステップ３０６）、
地図画像描画部１８が車両位置を含む地図データをＣＤ
−ＲＯＭ１からバッファメモリ１１に読み出し、該読み
出した地図データを用いて車両位置を中心とする北を上
向きにした地図画像をビデオＲＡＭ１９に描画する。次
に、誘導経路記憶部１５に記憶された誘導経路データの
中から地図画像の描画エリアに入っているものを選び出
し、地図画像に重ねて通常の道路とは異なる色で太く強
調した誘導経路を描画する。そして、地図画像の中心に
車両方位方向を向けた車両位置マークを描画する。ビデ
オＲＡＭ１９に描画された画像は映像変換部２０により
読み出され、所定の映像信号に変換されてディスプレイ
装置４に出力され、画面表示される（ステップ３０
７）。この結果、画面には図１０（１）に示す如く車両
位置を含む地図画像ＭＰが誘導経路ＧＲ、車両位置マー
クＣＭとともに表示される。

【００３７】次に、計測部１６はＧＰＳ受信機２から入
力した車両速度データに基づき、車両速度が20km/h以下
となった状態の継続時間を計測するため車両速度が20km
/h以下かチェックし（ステップ３０８）、ＮＯであれば
計測部１６に内蔵したタイマ（図示せず）を停止状態に
する（ステップ３０９）。このあと、ナビゲーションコ
ントローラ１０はステップ３０６に戻ってＧＰＳ受信機
２から新たな車両位置データ、車両方位データ、車両速
度データを入力し、新たな車両位置を中心とする地図画
像を、誘導経路、車両位置マークとともに描画し、画面
表示させる（ステップ３０７）。以下、車両速度が20km
/hを越えている限り、同様の処理を繰り返す。車両の走
行に従い画面は車両位置が中央に固定したまま誘導経路
を表した地図がスクロールしていく。運転者は誘導経路
に沿って走行することで目的地に到達することができ
る。

【００３８】渋滞判別 車両が誘導経路を走行中に図８の符号Ｓで示す渋滞に巻
き込まれると車両速度が遅くなる。渋滞で車両速度が20
km/h以下になったとき、計測部１６はステップ３０８で
ＹＥＳと判断する。このとき、タイマが計時中かチェッ
クし（ステップ３１０）、ここではＮＯなのでタイマを
スタートさせて計時を開始させておく（ステップ３１
１）。このあと、ナビゲーションコントローラ１０はス
テップ３０６に戻り、ＧＰＳ受信機２から新たな車両位
置データ、車両方位データ、車両速度データを入力し、
新たな車両位置を中心とする地図画像を、誘導経路、車
両位置マークとともに描画し、画面表示させる（ステッ
プ３０７）。そして、再び、計測部１６が車両速度が20
km/h以下かチェックし（ステップ３０８）、ＹＥＳであ
れば、現在、タイマが計時中かチェックし（ステップ３
１０）、今度はＹＥＳなので車両速度が20km/h以下の状
態になっている継続時間を示すタイマの計時時間データ
を判別部１８に出力する。

【００３９】判別部１８はタイマの計時時間データを入
力すると、３分を越えたかチェックする（ステップ３１
２）。ＮＯであればまだ再探索指令の出力はせず、ナビ
ゲーションコントローラ１０はステップ３０６に戻って
前述と同様の処理を行う。その後、車両速度が20km/h以
下の状態になっている継続時間が３分を越えたとき、判
別部１８は車両が渋滞に巻き込まれているとしてステッ
プ３１１でＹＥＳと判断し、経路探索部１４に対し目的
地までの最適な経路の再探索指令を出力する。

【００４０】経路再探索 判別部１７から再探索指令を受けた経路探索部１４は既
に探索してある誘導経路データの中から車両の進行方向
前方で現在位置から一定距離Ｌ₀ 以上離れた最寄りの交
差点とＬ₁ （＝Ｌ₀ ＋Ｌ）以上離れた最寄りの交差点を
選び出す（ステップ３１３）。ここでは図８のＣＰ₁ と
ＣＰ₂ であったとき、経路探索部１４はＣＰ₁ からＣＰ
₂ までが入る範囲の地図データをＣＤ−ＲＯＭ１からバ
ッファメモリ１１に読み出し、該読み出した地図データ
中の交差点ネットリストＣＲＮＬを用いてＣＰ₁ からＣ
Ｐ₂ までを結び、それまでの誘導経路以外の最短の経路
を先に説明した横型探索法により探索する（ステップ３
１４）。

【００４１】この際、再探索処理を開始する前に、ＣＰ
₁ からＣＰ₂ までの誘導経路に乗っている各交差点に対
応する交差点ネットリストＣＲＮＬに対し、ＣＰ₁ から
ＣＰ ₂ までの誘導経路に沿った部分の隣接交差点間距離
は極めて大きな距離に置き換えておく。これにより、Ｃ
Ｐ₁ からＣＰ₂ までを結ぶ元の誘導経路は累計距離が大
きくなり過ぎて最早、最短の経路として探索されること
はなく、ＣＰ₁ からＣＰ₂ までを結びそれまでの誘導経
路を迂回する種々の経路の中で最短の経路（図８の一点
鎖線ＧＲ´参照）が探索される。このあと、経路探索部
１４は誘導経路記憶部１５に記憶された当初の誘導経路
データの内、ＣＰ₁ からＣＰ₂ までの間を今回再探索し
たノードデータ列で置き換えて、誘導経路データの修正
を行う（ステップ３１５）。

【００４２】このあと、ナビゲーションコントローラ１
０は図７のステップ３０６に戻り、車両位置を中心とす
る地図画像を修正後の誘導経路、車両位置マークととも
に描画し、画面表示する（図１０（２）参照）。よっ
て、ユーザは渋滞を回避するため試行錯誤で迂回路を探
さなくても、新たな誘導経路に沿って走行するだけで渋
滞を回避しながら目的地に簡単かつ速やかに到達できる
ことになる。

【００４３】なお、上記した実施例では、再探索指令を
受けた経路探索部１４は誘導経路上の車両の進行方向前
方で現在位置から一定距離Ｌ₀ だけ離れた交差点ＣＰ₁
とＬ ₁ （＝Ｌ₀ ＋Ｌ）だけ離れた交差点ＣＰ₂ の間につ
き、渋滞を迂回して走行できる経路を再探索して誘導経
路データの一部を修正するようにしたが、ＣＰ₁ から目
的地までの間を結び渋滞を迂回する経路を再探索し、誘
導経路データ全体を修正するようにしても良い。また、
再探索時、誘導経路上のＣＰ１₁ −ＣＰ₂ 間について交
差点ネットリストＣＲＮＬ中の隣接交差点間距離を極め
て大きな距離に置き換えることは同じであるが、他の区
間は交差点ネットリストＣＲＮＬ中の隣接交差点間距離
をそのまま用いた単純な最短経路、交差点ネットリスト
ＣＲＮＬ中の隣接交差点間距離を隣接交差点間の幅員に
応じて重み付けした幅員優先の最短経路（幅員が大きい
ほど隣接交差点間距離を実際より短く扱う）、交差点ネ
ットリストＣＲＮＬ中の隣接交差点間距離を隣接交差点
間の道路種別に応じて重み付けした種別優先の最短経路
（高速道路や国道は一般道より隣接交差点間距離を実際
より短く扱う）の３つを全て再探索して誘導経路記憶部
１５に別個に記憶させ、地図画像描画部１８はこれら３
つの迂回経路を同時に地図画像上に描画し、画面表示さ
せるようにして、ユーザが３つの迂回路の中から任意の
１つを選択して走行できるようにしても良い。

【００４４】

【発明の効果】以上本発明によれば、車両速度が一定以
下となった状態の継続時間を計測し、該計測した継続時
間を所定の基準値と比較して渋滞が発生しているか判別
し、経路誘導中に渋滞が発生していると判別されたと
き、地図データを用いて現在位置から渋滞を迂回して目
的地までを結ぶ最適な経路を再探索し、誘導経路データ
を修正するように構成したから、経路誘導を受けて目的
地に向け走行中に渋滞に巻き込まれても、自動的に現在
位置から渋滞を迂回して目的地に到達できる最適な経路
に切り換えて経路誘導を受けることができ、所望の目的
地に速やかに到達することができる。

【図面の簡単な説明】

【図１】本発明の一実施例に係る車載用ナビゲーション
装置の全体構成図である。

【図２】誘導経路記憶部に記憶されるデータの説明図で
ある。

【図３】道路レイヤのデータ構造を示す説明図である。

【図４】交差点ネットリストの説明図である。

【図５】ナビゲーションコントローラの動作を示す第１
の流れ図である。

【図６】ナビゲーションコントローラの動作を示す第２
の流れ図である。

【図７】ナビゲーションコントローラの動作を示す第３
の流れ図である。

【図８】車両位置周辺の道路を示す説明図である。

【図９】経路探索方法の説明図である。

【図１０】画面表示例を示す説明図である。

【符号の説明】

１ ＣＤ−ＲＯＭ ２ ＧＰＳ受信機 ３ 操作部 ４ ディスプレイ装置 １０ ナビゲーションコントローラ １１ バッファメモリ １２ カーソル位置計算部 １３ 目的地設定部 １４ 経路探索部 １５ 誘導経路記憶部 １６ 計測部 １７ 判別部 １８ 地図画像描画部 １９ ビデオＲＡＭ ２０ 映像変換部

Claims (1)

【特許請求の範囲】
1. 【請求項１】 地図データを記憶した地図データ記憶手
   段と、車両位置と車両方位を検出する車両位置検出手段
   と、地図データを用いて出発地と目的地を結ぶ最適な経
   路を自動探索し、誘導経路データとして誘導経路記憶手
   段に記憶させる経路探索手段と、地図データを用いて車
   両位置周辺の地図画像を車両位置マークとともに描画
   し、表示手段に画面表示させる地図画像描画手段と、誘
   導経路データを用いて経路誘導を行う経路誘導手段とを
   備えた車載用ナビゲーション装置において、 車両速度を検出する車両速度検出手段と、 車両速度が一定以下となった状態の継続時間を計測する
   計測手段と、 計測手段で計測した継続時間を所定の基準値と比較し、
   渋滞が発生しているか判別する判別手段とを備え、 前記経路探索手段は経路誘導中に判別手段で渋滞が発生
   していると判別されたとき、地図データを用いて現在位
   置から渋滞を迂回して目的地までを結ぶ最適な経路を再
   探索し、誘導経路記憶手段に記憶された誘導経路データ
   を修正するようにしたこと、 を特徴とする車載用ナビゲーション装置。