(57)【要約】【課題】ユーザが煩わしい操作をしなくても、走行中の状況変化等によって経由地や目的地を適宜変更して経路誘導を行うことができるようにする。【解決手段】経由地Ａ，Ｂまたは目的地Ｐに設定される地点が他の地点に代替可能かどうかの代替可否、代替可能である場合の代替地点を表した代替情報をあらかじめ記憶しておき、ＶＩＣＳ渋滞情報を受信する等の所定のトリガが与えられたときに代替情報を参照し、経由地Ａ，Ｂおよび目的地Ｐを代替地点Ａ’，Ｂ’，Ｐ’に置き換えて渋滞回避ルートを探索するようにすることにより、ユーザが経由地や目的地を設定し直すなどの煩わしい操作をしなくても、渋滞区間を確実に回避する代替経路を設定することができるようにする。【選択図】　　　　図１
2004093240.tif 000002
【特許請求の範囲】
【請求項１】
経由地または目的地に設定される地点が他の地点に代替可能かどうかの代替可否、代替可能である場合の代替地点を表した代替情報を記憶する代替情報記憶手段と、
所定のトリガに応じて上記代替情報を参照し、上記経由地および目的地の少なくとも一方を上記代替地点に適宜置き換えて、初期経路上の車両の現在位置から上記代替地点を通る代替経路を探索する代替経路探索手段とを備えたことを特徴とするナビゲーション装置。
【請求項２】
上記代替経路探索手段は、渋滞情報を受信した場合に、渋滞区間中に経由地または目的地が含まれているかどうかを判断し、含まれている場合に上記代替情報を参照し、上記経由地および目的地の少なくとも一方を上記渋滞区間外にある上記代替地点に適宜置き換えて渋滞回避ルートの探索を行うことを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
上記代替経路探索手段は、上記初期経路上の経由地または目的地への到着予想時刻がその地点の営業時間内かどうかを判断し、営業時間外の場合には上記代替情報を参照し、上記経由地および目的地の少なくとも一方を、上記営業時間内に到着可能な上記代替地点に適宜置き換えて、上記代替経路の探索を行うことを特徴とする請求項１に記載のナビゲーション装置。
【請求項４】
上記代替経路探索手段により設定された代替経路を上記初期経路と共に画面上に表示するように制御する表示制御手段を備えたことを特徴とする請求項１〜３の何れか１項に記載のナビゲーション装置。
【請求項５】
上記渋滞情報を受信した場合に、上記経由地および目的地の双方を上記代替地点に置き換えることなく渋滞回避ルートを探索する迂回経路探索手段と、
上記代替経路探索手段により設定された代替経路および上記迂回経路探索手段により探索された迂回経路を共に画面上に表示するように制御する表示制御手段とを備えたことを特徴とする請求項２に記載のナビゲーション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はナビゲーション装置に関し、特に、出発地および目的地のほかに経由地を設定してこれらを結ぶ最適な経路を探索し、その探索した誘導経路に沿って運転者を目的地まで案内する経路誘導機能を備えたナビゲーション装置に用いて好適なものである。
【０００２】
【従来の技術】
一般に、車両の走行案内を行うナビゲーション装置においては、自立航法センサやＧＰＳ（Ｇｌｏｂａｌ　Ｐｏｓｉｔｉｏｎｉｎｇ　Ｓｙｓｔｅｍ）受信機などを用いて車両の現在位置を検出する。そして、検出した現在位置周辺の地図データをＤＶＤ等の記録媒体から読み出し、地図画像をディスプレイ装置に描画するとともに、その地図画像の所定位置に車両位置マークを重ねて描画する。そして、車両の移動により現在位置が変化するに従って、画面上で車両位置マークを移動したり、車両位置マークは画面上の所定箇所に固定してその近傍の地図画像をスクロールしたりすることにより、車両が現在どこを走行しているのかを一目で分かるようにしている。
【０００３】
このようなナビゲーション装置の殆どは、出発地から目的地までの誘導経路を設定して案内する機能を備えている。この経路誘導機能では、地図データを用いて出発地から目的地までを結ぶ最もコストが小さな経路を、幅優先探索（ＢＦＳ）法あるいはダイクストラ法などのシミュレーションを行って自動探索し、その探索した経路を誘導経路として記憶する。
【０００４】
なお、コストとは、距離をもとに、道路幅員、道路種別（一般道か高速道路かなど）、右折および左折、交通規制などに応じた所定の定数を乗じた値であり、誘導経路として適正の程度を数値化したものである。経路探索処理においては、交差点や分岐など複数の道路が交わる点をノード、隣接するノード間を結ぶベクトルをリンクとして、出発地から目的地に至る様々な経路上のリンクコストを順次加算し、リンクコストの合計が最も小さい経路を選択する。
【０００５】
誘導経路の設定後は、車両の走行中に地図画像上で誘導経路を他の道路と識別可能なように色を変えて太く描画する。また、車両が誘導経路上の案内交差点から所定距離内に近づいたときに、交差点案内図（交差点拡大図とこの交差点での進行方向を示す矢印）を表示したり、進行方向を音声で案内したりするなどの交差点案内を行うことにより、運転者を目的地まで案内するようになっている。
【０００６】
また、このような経路誘導機能を搭載したナビゲーション装置の多くでは、出発地と目的地だけでなく、目的地へ向かう途中で立ち寄りたい経由地を設定して経路探索を行うことができるようになっている。この経路誘導機能を用いて誘導経路を探索し、案内に従って走行していけば、運転者が道を知らなくても、経由地を通って目的地に確実に到達することができる。
【０００７】
【発明が解決しようとする課題】
しかしながら、従来のナビゲーション装置においては、ユーザが一度設定した経由地や目的地は固定であり、設定された経由地や目的地を必ず通るように誘導経路が設定される。そのため、走行中の状況変化等によってその経由地や目的地を通ることが好ましくない状態になったとしても、その経由地や目的地を通らざるを得なかった。
【０００８】
例えば、従来のナビゲーション装置の中には、目的地までの推奨ルート（初期経路）を走行中にＶＩＣＳ渋滞・事故情報を受信した場合に、現在位置から渋滞等を回避する迂回経路を探索する迂回経路探索機能を備えたものが存在する。この迂回経路探索機能では、渋滞している道路のリンクコストを大きくし、あるいは、渋滞している道路を擬似的に削除した上で、時間的に最短で行ける１本の経路を探索するようになっている。ところが、このように迂回経路を探索しても、経由地や目的地が渋滞区間に含まれていると、結果的に渋滞を回避できない場合がある。
【０００９】
このことを、図１３に従って具体的に説明する。図１３は、従来の渋滞回避ルート自動探索の様子を示す図である。図１３（ａ）は、２つの経由地Ａ，Ｂと目的地Ｐとを設定して経路探索を行い、探索された推奨ルートを走行中に、当該推奨ルート上に渋滞が発生した状態を示している（渋滞区間を太線で示している）。このような渋滞情報をナビゲーション装置が受信すると、その渋滞区間を回避する迂回経路の探索を自動的に実行する。
【００１０】
この迂回経路の探索結果を示すのが、図１３（ｂ）である。図１３（ｂ）に示すように、この例では２つの経由地Ａ，Ｂが設定されているため、迂回経路もこれらの経由地Ａ，Ｂを必ず通るように設定される。ところが、この例で２つの経由地Ａ，Ｂは共に渋滞区間に含まれているため、探索される迂回経路は図１３（ｂ）の点線に示すようになり、迂回経路を探索しても渋滞を回避することができないという問題が生じる。
【００１１】
また、設定された誘導経路上に渋滞等が発生することにより、経由地や目的地への到着時刻が予想以上に遅くなってしまうこともある。この場合、経路誘導機能を利用すれば必ず経由地や目的地に到達できるが、到着した時点でその地点の営業時間が既に終了してしまっている場合がある。この場合には、せっかく経由地や目的地に行っても、その施設等を利用することができなくなってしまうという問題を生じる。
【００１２】
これらの場合に、経由地や目的地を設定し直して経路探索を再度行えば、渋滞を回避したり、営業時間内に到着したりすることができる。ところが、そのためには車両を一旦停止させてリモコン等による煩雑な操作をする必要があり、非常に面倒であった。
【００１３】
本発明は、このような問題を解決するために成されたものであり、ユーザが煩わしい操作をしなくても、走行中の状況変化等によって経由地や目的地を適宜変更して経路誘導を行うことができるようにすることを目的とする。
【００１４】
【課題を解決するための手段】
上記した課題を解決するために、本発明のナビゲーション装置においては、経由地または目的地に設定される地点が他の地点に代替可能かどうかの代替可否、代替可能である場合の代替地点を表した代替情報を代替可能リストとしてあらかじめ記憶しておき、所定のトリガが与えられたとき（例えば渋滞情報の受信時、到着予想時刻情報の算出時など）に代替情報を参照し、目的地および経由地の少なくとも一方を代替地点に適宜置き換えて代替経路を探索する。
【００１５】
上記のように構成した本発明によれば、例えば渋滞情報によって示される渋滞区間中に初期経路上の経由地または目的地が含まれている場合は、それらが渋滞区間外にある代替地点に置き換えられて、当該代替地点を通る渋滞回避ルートが探索される。これにより、ユーザが経由地や目的地を設定し直すなどの煩わしい操作をすることなく、渋滞区間を確実に回避する代替経路を設定することが可能となる。
【００１６】
別の例では、初期経路上の経由地または目的地への到着予想時刻がその地点の営業終了時刻を過ぎると判断される場合に、それらの経由地や目的地が、営業終了時刻よりも前に到着可能な代替地点に置き換えられて、代替経路の探索が行われる。これにより、ユーザが経由地や目的地を設定し直すなどの煩わしい操作をすることなく、営業時間内に到着可能な経由地や目的地を通る代替経路を設定することが可能となる。
【００１７】
【発明の実施の形態】
（第１の実施形態）
以下、本発明の第１の実施形態を図面に基づいて説明する。図１は、第１の実施形態に係る渋滞回避ルート探索処理の概要を説明するための図である。図１（ａ）は、２つの経由地Ａ，Ｂと目的地Ｐとを設定して経路探索を行い、探索された推奨ルート（初期経路）を走行中に、当該推奨ルート上に渋滞が発生した状態を示している（渋滞区間を太線で示している）。この状態は、図１３（ａ）の状態と同じである。
【００１８】
このような渋滞情報をナビゲーション装置が受信すると、その渋滞区間を回避する迂回経路の探索を自動的に実行する。この迂回経路の探索結果を示すのが、図１（ｂ）である。図１（ｂ）に示すように、この例で経由地Ａ，Ｂは共に渋滞区間に含まれている。この場合は、これらの経由地Ａ，Ｂを共に、渋滞区間外の代替経由地Ａ’，Ｂ’に置き換える。また、このとき目的地Ｐを代替目的地Ｐ’に置き換えても良い。そして、推奨ルート上の車両の現在位置から代替地点Ａ’，Ｂ’，Ｐ’を通る渋滞回避ルート（一点鎖線で示す経路１）を、代替経路として探索する。
【００１９】
経由地や目的地が銀行やコンビニエンスストアなどの場合、それらの経由地や目的地は必ずそこを通ることが必須ではなく、同じジャンルの地点であればそれに代替可能である場合が多い。そこで本実施形態では、図２に示すような代替可能リストをあらかじめ用意しておく。そして、渋滞情報を受信するなどのトリガを受けたときに、渋滞区間中に経由地または目的地が含まれているかどうかを判断し、含まれている場合には代替可能リストを参照する。これにより、経由地および目的地の少なくとも一方を渋滞区間外にある代替地点に置き換えて、その上で渋滞回避ルートの探索を行うようにする。
【００２０】
図２に示す代替可能リストでは、複数の地点ごとに、ジャンルおよび地点の名称、他の地点に代替可能かどうかの代替可否を表した情報を記憶するとともに、代替可能である場合の代替地点を表した情報を記憶している。代替可能地点は、１つの地点に対して複数登録することも可能である。
【００２１】
本実施形態ではさらに、経由地および目的地の双方を代替地点に置き換えることなく、元の経由地Ａ，Ｂと目的地Ｐのままで渋滞回避ルート（点線で示す経路２）を探索する。そして、代替地点Ａ’，Ｂ’，Ｐ’を通る渋滞回避ルート１と、元の地点Ａ，Ｂ，Ｐを通る渋滞回避ルート２とを共にナビゲーション画面上に表示してユーザに提示する。ユーザは、提示された２つの渋滞回避ルート１，２のうち所望する方を選択すれば良い。
【００２２】
図３は、上述した動作を実現するためのナビゲーション装置の構成例を示すブロック図である。図３において、１１はＤＶＤ−ＲＯＭ等の地図記憶媒体であり、地図表示や経路探索などに必要な各種の地図データを記憶している。なお、ここでは地図データを記憶する記録媒体としてＤＶＤ−ＲＯＭ１１を用いているが、ＣＤ−ＲＯＭ、ハードディスクなどの他の記録媒体を用いても良い。１２はＤＶＤ−ＲＯＭ制御部であり、ＤＶＤ−ＲＯＭ１１からの地図データの読み取りを制御する。
【００２３】
ここで、ＤＶＤ−ＲＯＭ１１に記録された地図データの詳細について説明する。ＤＶＤ−ＲＯＭ１１に記録された地図データは、広い地域を一望するための上位レベルの地図から、狭い地域を詳細に記述した下位レベルの地図まで、レベルと呼ばれる単位に階層化して管理されている。各レベルは、所定の経度および緯度で区切られた区画と呼ばれる矩形領域を単位として分割されている。各区画の地図データは、区画番号を指定することにより特定され、読み出すことが可能となる。
【００２４】
区画ごとの地図データには、地図表示に必要な各種のデータから成る描画ユニットと、マップマッチングや経路探索、経路案内等の各種の処理に必要なデータから成る道路ユニットと、交差点の詳細データから成る交差点ユニットとが含まれている。また、上述した描画ユニットには、建物あるいは河川等を表示するために必要な背景レイヤのデータと、市町村名や道路名等を表示するために必要な文字レイヤのデータと、道路交通情報センタ（ＶＩＣＳセンタ）から送られてくる渋滞・事故情報に基づいて対応する道路を特定するために必要なＶＩＣＳ変換レイヤのデータとが含まれている。
【００２５】
上述の道路ユニットは、交差点や分岐など、複数の道路が交わる点に対応するノードと、道路上のあるノードとこれに隣接する他のノードとの間を接続する、道路や車線等に対応するリンクとを含んでいる。図４は、この道路ユニットの全体構成を示す図である。同図に示すように、道路ユニットには、道路ユニットであることを識別するためのユニットヘッダと、全ノードの詳細データを納めた接続ノードテーブルと、接続ノードテーブルの格納位置を示すノードテーブルと、隣接する２つのノードによって特定されるリンクの詳細データを納めたリンクテーブルとが含まれている。
【００２６】
図５は、道路ユニットに含まれる各種テーブルの詳細な内容を示す図である。ノードテーブルは、図５（Ａ）に示すように、着目している区画に含まれる全ノードに対応したノードレコード＃０，＃１，＃２，・・・・を格納している。各ノードレコードは、その並び順に＃０から順にノード番号が与えられており、このノード番号が各ノードに対応する接続ノードテーブルの格納位置を示している。
【００２７】
また、接続ノードテーブルには、図５（Ｂ）に示すように、存在するノードのそれぞれ毎に、ａ．ノードの正規化経度・緯度、ｂ．ノードの属性フラグ、ｃ．接続しているノードの数、ｄ．交通規制の数、ｅ．接続ノードレコード、ｆ．交通規制レコード、ｇ．隣接ノードレコード、ｈ．交差点レコードの格納位置およびサイズ等の情報が含まれている。
【００２８】
ａ．ノードの正規化経度・緯度は、区画を基準とした経度方向・緯度方向の相対位置を示す。ｂ．ノードの属性フラグは、そのノードが交差点ノードであるか否かを示す交差点ノードフラグや、他の区画との境界にあるノードであるか否かを示す隣接ノードフラグなどから成る。ｃ．接続しているノードの数は、そのノードをリンクの一方端とするリンクがある場合に、各リンクの他方端を構成するノードの数を示す。
【００２９】
ｄ．交通規制の数は、そのノードに接続されているリンクに右折禁止やＵターン禁止等の交通規制が存在する場合に、その交通規制の数を示す。ｅ．接続ノードレコードは、そのノードが一方端となっている各リンクのリンク番号を、リンク本数分だけ示す。ｆ．交通規制レコードは、上述した交通規制が存在する場合にはその数に対応した交通規制の具体的な内容を示す。
【００３０】
ｇ．隣接ノードレコードは、そのノードが他の区画との境界にある隣接ノードである場合に、隣接する区画の対応するノードの接続ノードテーブルの位置を示す。ｈ．交差点レコードの格納位置およびサイズは、そのノードが交差点ノードである場合に、交差点ユニットにおける対応する交差点レコードの格納位置およびサイズを示す。
【００３１】
また、リンクテーブルは、図５（Ｃ）に示すように、着目している区画に含まれる全てのリンクに対応したリンクレコード＃０，＃１，＃２，・・・・を格納している。各リンクレコードには、その並び順に＃０から順にリンク番号が与えられており、このリンク番号が各リンクに対応するリンクレコードの格納位置を示している。
【００３２】
各リンクレコードには、ａ．リンクＩＤ、ｂ．ノード番号１，２、ｃ．リンクの距離、ｄ．リンクのコスト、ｅ．道路属性フラグ、ｆ．道路種別フラグ、ｇ．路線番号、ｈ．ＶＩＣＳリンク対応フラグ等の情報が含まれている。ａ．リンクＩＤは、主に探索経路表示用に各リンクに付されたコードを示す。ｂ．ノード番号１，２は、リンクの両端に位置する２つのノードを特定する番号を示す。ｃ．リンクの距離は、当該リンクに対応した実際の道路の実距離を示す。
【００３３】
ｄ．リンクのコストは、そのリンクを走行する場合の所要時間を道路種別等から計算により求めて、そのリンクの通過に必要な時間を例えば分単位で示したものである。なお、このリンクのコストは、そのリンクを走行する場合の実際の所要時間を統計的に求めても良いし、そのリンクに対応した実際の道路の法定速度から計算により求めても良い。ｅ．道路属性フラグは、そのリンクに関する各種の属性を示す。ｆ．道路種別フラグは、そのリンクに対応した実際の道路が高速道路であるか一般道であるかといった種別を示す。
【００３４】
ｇ．路線番号は、そのリンクに対応した実際の道路に付された番号を示す。ｈ．ＶＩＣＳリンク対応フラグは、そのリンクがＶＩＣＳセンタで管理しているＶＩＣＳリンク（道路交通情報を受信可能なリンク）と対応しているか否かを示す。なお、以下では、ＶＩＣＳリンクと区別するために道路ユニットに含まれる各リンクを特に「道路リンク」と称する。
【００３５】
図６は、描画ユニットに含まれるＶＩＣＳ変換レイヤの詳細な内容を示す図である。同図に示すように、描画ユニットのＶＩＣＳ変換レイヤには、ＶＩＣＳ変換テーブルが含まれている。さらに、このＶＩＣＳ変換テーブルには、ＶＩＣＳ変換テーブルであることを識別するためのＶＩＣＳユニットヘッダと、道路リンク番号テーブルと、ＶＩＣＳリンク変換テーブルとが含まれている。道路リンク番号テーブルは、道路リンク番号の順に、各道路リンクのデータがＶＩＣＳ変換テーブル内のどの位置に格納されているかを示すものであり、着目している区画の全リンクに対応している。
【００３６】
また、ＶＩＣＳリンク変換テーブルには、存在する道路リンクのそれぞれに対応して、ａ．ＶＩＣＳリンク情報フラグ（ＶＩＣＳリンクと道路リンクの相対的な長さを示すＶＩＣＳリンク長と、着目している道路リンクの上下線が同じか異なるかを示す上下線区別を含む）、ｂ．着目している道路リンクを一方（他方）のノードから他方（一方）のノードに向かって見た場合の対応するＶＩＣＳリンクの数、ｃ．ＶＩＣＳリンクの一方（他方）のノード方向からこの道路リンク開始位置までの距離（ＶＩＣＳリンク全体の距離で見た場合のパーセンテージ）、ｄ．道路リンクの一方（他方）のノードから他方（一方）のノードに向かって見た場合のＶＩＣＳリンクのそれぞれに対応した２次メッシュコード、ＶＩＣＳリンクＩＤ、ＶＩＣＳリンクまでの距離等の情報が含まれる。
【００３７】
図３に戻って説明する。１３は車両の現在位置を測定する位置測定装置であり、自立航法センサ、ＧＰＳ受信機、位置計算用ＣＰＵ等で構成されている。自立航法センサは、所定走行距離毎に１個のパルスを出力して車両の移動距離を検出する車速センサ（距離センサ）と、車両の回転角度（移動方位）を検出する振動ジャイロ等の角速度センサ（相対方位センサ）とを含んでいる。自立航法センサは、これらの車速センサおよび角速度センサによって車両の相対位置および方位を検出する。
【００３８】
位置計算用ＣＰＵは、自立航法センサから出力される自車の相対的な位置および方位のデータに基づいて、絶対的な自車位置（推定車両位置）および車両方位を計算する。また、ＧＰＳ受信機は、複数のＧＰＳ衛星から送られてくる電波をＧＰＳアンテナで受信して、３次元測位処理あるいは２次元測位処理を行って車両の絶対位置および方位を計算する（車両方位は、現時点における自車位置と１サンプリング時間ΔＴ前の自車位置とに基づいて計算する）。
【００３９】
１４は地図情報メモリであり、ＤＶＤ−ＲＯＭ制御部１２の制御によってＤＶＤ−ＲＯＭ１１から読み出された地図データを一時的に格納する。すなわち、ＤＶＤ−ＲＯＭ制御部１２は、位置測定装置１３から車両現在位置の情報を入力して、その車両現在位置を含む所定範囲の地図データの読み出し指示を出力することにより、地図表示や誘導経路の探索に必要な地図データをＤＶＤ−ＲＯＭ１１から読み出して地図情報メモリ１４に格納する。１５は代替リストメモリであり、図２に示したような代替可能リストを記憶する。
【００４０】
１６はビーコン送受信機であり、主に高速道路上に設置された電波ビーコン送受信機との間で電波を介して双方向通信を行うとともに、主に一般道上に設置された光ビーコン送受信機との間で光を介して双方向通信を行うことにより、ＶＩＣＳセンタから送られてくるＶＩＣＳ道路交通情報を受信する。
【００４１】
図７は、ＶＩＣＳセンタから送られてくるＶＩＣＳ道路交通情報に含まれる渋滞情報を示す図である。同図に示す渋滞情報パケットは、あるＶＩＣＳリンクの特定箇所がどの程度渋滞しているかを示すものであり、ａ．２次メッシュコード、ｂ．ＶＩＣＳリンク番号、ｃ．始点からの距離、ｄ．長さ、ｅ．渋滞の度合い等の各種情報を含んでいる。
【００４２】
ａ．２次メッシュコードは、そのＶＩＣＳリンクが含まれるエリアを特定するためのコードを示す。ｂ．ＶＩＣＳリンク番号は、その道路に対応したリンク番号を示す。ｃ．始点からの距離は、渋滞が始まる位置を特定するための始点（ＶＩＣＳリンクの一方端）からの距離を示す。ｄ．長さは、渋滞の区間を示す。ｅ．渋滞の度合いは、例えば車両が一定の速度以下になる「渋滞」と、ほとんど車両が動かなくなる「混雑」との２種類の状態が特定される。この図７に示す渋滞情報パケットと、図６に示したＶＩＣＳ変換レイヤとを用いることにより、渋滞情報に対応するリンクを特定することができる。
【００４３】
１７はリモートコントローラ（リモコン）等の操作部であり、ユーザがナビゲーション装置に対して各種の情報（例えば、経路誘導の経由地や目的地）を設定したり、各種の操作（例えば、メニュー選択操作、拡大／縮小操作、手動地図スクロール、数値入力など）を行ったりするための各種操作子（ボタンやジョイスティック等）を備えている。上記代替リストメモリ１５内の代替可能リストは、ユーザがリモコン１５を操作することによって任意に編集することが可能である。１８はリモコンインタフェースであり、リモコン１５からその操作状態に応じた赤外線信号を受信する。
【００４４】
１９はプロセッサ（ＣＰＵ）であり、ナビゲーション装置の全体を制御する。２０はＲＯＭであり、各種プログラム（誘導経路探索処理プログラム、迂回経路探索処理プログラム等）を記憶する。２１はＲＡＭであり、各種処理の過程で得られるデータや、各種処理の結果得られるデータを一時的に格納する。
【００４５】
上述のＣＰＵ１９は、ＲＯＭ２０に記憶されている誘導経路探索処理プログラムに従って、地図情報メモリ１４に格納された地図データを用いて、出発地から経由地を通って目的地までを結ぶ最もコストが小さな誘導経路（初期経路）を探索する処理を行う。また、ＣＰＵ１９は、迂回経路探索処理プログラムに従って、代替可能リストを参照して経由地および目的地の少なくとも一方を代替地点に適宜置き換えて、または代替地点に置き換えることなく、現在位置から初期経路上の渋滞区間を回避するような渋滞回避ルートを探索する処理も行う。
【００４６】
渋滞回避ルートを探索する際は、ＶＩＣＳ渋滞情報により示される渋滞区間を回避対象リンクとして決定する。そして、当該回避対象リンクを擬似的に削除（交差点ネットワークリストから回避対象リンクを削除）して、時間最短の条件下でコストが最小となる経路を探索する。なお、ここでは回避対象リンクを擬似的に削除した上で渋滞回避ルートの探索を行っているが、回避対象リンクのリンクコストを定数倍した上で、このように重み付けした回避対象リンクも含めて渋滞回避ルートの探索を行うようにしても良い。
【００４７】
２２は誘導経路メモリであり、ＣＰＵ１９が探索した誘導経路（初期経路、迂回経路）のデータを記憶する。誘導経路のデータは、出発地から経由地を通って目的地まで至る各ノードに対応させて、各ノードの位置と、各ノードが交差点か否かを表す交差点識別フラグとを記憶したものである。
【００４８】
２３は交差点拡大図メモリであり、誘導経路中にある全誘導対象交差点の拡大図のデータ（目的地に向けて車両を案内するための交差点拡大図、行先、進行方向矢印の画像）を一時的に格納する。この交差点拡大図のデータも、ＤＶＤ−ＲＯＭ制御部１２の制御によってＤＶＤ−ＲＯＭ１１から適宜読み出される。
【００４９】
２４はディスプレイコントローラであり、地図情報メモリ１４に格納された地図データに基づいて、表示装置３０への表示に必要な地図画像データを生成する。２５はビデオＲＡＭであり、ディスプレイコントローラ２４によって生成された地図画像データを一時的に格納する。すなわち、ディスプレイコントローラ２４によって生成された地図画像データはビデオＲＡＭ２５に一時的に格納され、１画面分の地図画像データが読み出されて画像合成部２９に出力される。
【００５０】
２６はメニュー発生部であり、リモコン１７を用いて各種の操作を行う際に必要なメニュー画像を発生して出力する。２７は誘導経路発生部であり、誘導経路メモリ２２に記憶された経路探索処理の結果を使用して、誘導経路のデータを発生する。すなわち、誘導経路メモリ２２に記憶された誘導経路データの中から、その時点でビデオＲＡＭ２５に描画された地図エリアに含まれるものを選択的に読み出し、地図画像に重ねて他の道路と異なる所定色で太く強調した誘導経路を描画する。また、自車が誘導経路前方にある案内交差点から所定距離内に接近したときに、交差点拡大図メモリ２３に格納された交差点拡大図データに基づいて、接近中の交差点の案内図の画像を生成して出力する。
【００５１】
２８はマーク発生部であり、マップマッチング処理された後の自車位置に表示する車両位置マークや、ガソリンスタンドやコンビニエンスストア等を表示する各種ランドマーク等を発生して出力する。なお、マップマッチング処理とは、地図情報メモリ１４に読み出されている地図データと、位置測定装置１３によって測定されたＧＰＳ受信機による自車位置および車両方位のデータと、自立航法センサによる推定車両位置および車両方位のデータとを用いて、自車の走行位置を地図データの道路上に位置修正する処理のことを言う。
【００５２】
２９は画像合成部であり、各種画像を合成して出力する。すなわち、ディスプレイコントローラ２４により読み出された地図画像データに、メニュー発生部２６、誘導経路発生部２７、マーク発生部２８のそれぞれから出力される各画像データを重ねて画像合成を行い、表示装置３０に出力する。これにより、表示装置３０の画面上には、自車周辺の地図情報が車両位置マークや出発地マーク、目的地マーク等と共に表示される。また、この地図上に誘導経路が表示されるとともに、車両の位置が案内交差点近傍に近づいたときに交差点拡大図が表示される。
【００５３】
３１は音声発生部であり、交差点案内の音声や、各種操作案内の音声などを発声する。３２はスピーカであり、音声発生部３１により発生された音声を外部に出力する。３３はバスであり、上述した各種の機能構成どうしで互いにデータの授受を行うために使用される。
【００５４】
次に、上記のように構成した本実施形態のナビゲーション装置による迂回経路（渋滞回避ルート）自動探索の動作について説明する。図８は、渋回避ルート自動探索処理の全体の流れを示すフローチャートである。図８に示すフローチャートは、ビーコン送受信機１６がＶＩＣＳセンタから渋滞情報を受信したことをトリガとして実行される。
【００５５】
図８において、ＣＰＵ１９は、初期経路上に存在する目的地または経由地が、ＶＩＣＳ渋滞情報により示される渋滞区間に含まれているか否かを判定する（ステップＳ１）。含まれていない場合は、当該目的地および経由地を代替地点に置き換えることなく渋滞回避ルートの探索を行い（ステップＳ３）、その結果を表示装置３０に表示して処理を終了する。
【００５６】
一方、初期経路上に存在する目的地または経由地が渋滞区間に含まれている場合は、代替リストメモリ１５に記憶されている図２のような代替可能リストを参照して、代替可否の情報に基づいて、当該目的地または経由地が他の地点に代替可能かどうかを判定する（ステップＳ２）。代替可能でない場合は、当該目的地および経由地を代替地点に置き換えることなく渋滞回避ルートの探索を行い（ステップＳ３）、その結果を表示装置３０に表示して処理を終了する。
【００５７】
目的地および経由地の代替が可能な場合は、代替可能リストを参照して代替可能な地点を探索し（ステップＳ４）、探索した代替地点を新たな目的地および経由地に設定する（ステップＳ５）。そして、この新たに設定した代替地点を通る渋滞回避ルートの探索を行う（ステップＳ６）。このとき、元の目的地および経由地を通る渋滞回避ルートの探索も行う。なお、上記ステップＳ４で１つの地点に対して複数の代替地点が探索された場合、その後のステップＳ５およびステップＳ６においては、複数の代替地点のうち最もコストが小さくなる地点を選んで渋滞回避ルートを設定する。
【００５８】
最後に、初期経路上の元の経由地や目的地を通るように設定された渋滞回避ルートと、代替地点を通るように設定された渋滞回避ルートとを表示装置３０に表示し（ステップＳ７）、処理を終了する。このステップＳ７においては、新たに設定された渋滞回避ルートと共に元の初期経路を表示装置３０に表示するようにしても良い。
【００５９】
なお、上記ステップＳ２では、代替可否の情報に基づいて代替可能かどうかを判定しているが、更に代替地点が渋滞区間外にあるかどうかも見て代替可能かどうかを判定するようにしても良い。すなわち、代替可否の情報では代替可能であるとされていても、その代替地点も渋滞区間に含まれているような場合には、代替ができないと判定するようにする。
【００６０】
以上詳しく説明したように、第１の実施形態によれば、ＶＩＣＳ渋滞情報によって示される渋滞区間中に初期経路上の経由地または目的地が含まれている場合に、それらを代替地点に適宜置き換えて、当該代替地点を通る渋滞回避ルートを探索するようにしている。これにより、ユーザが経由地や目的地を設定し直すなどの煩わしい操作をすることなく、渋滞区間を確実に回避する代替経路を設定することができる。
【００６１】
（第２の実施形態）
次に、本発明の第２の実施形態を図面に基づいて説明する。図９は、第２の実施形態に係る代替経路探索処理の概要を説明するための図である。図９中に点線で示す誘導経路は、ファミリーレストランおよびガソリンスタンドの２つの経由地Ａ，Ｂと、スキー場の目的地Ｐとを設定して経路探索を行った結果の初期経路を示している。また、実線で示す誘導経路は、初期経路に対する代替経路を示している。
【００６２】
図９に示すように、最初の経由地Ａとして当初設定したファミリーレストランの営業終了時刻は２３時であり、現在地からの距離および走行速度をもとに算出した経由地Ａへの到着予想時刻は１７時５０分であったとする。よって、ファミリーレストランには営業時間内に到着することができるので、ここはそのまま経由地とする。
【００６３】
一方、２番目の経由地Ｂとして当初設定したガソリンスタンドの営業終了時刻は２０時であり、現在地からの距離および走行速度をもとに算出した経由地Ｂへの到着予想時刻は２０時１０分であったとする。よって、このガソリンスタンドには営業時間内に到着することができない。この場合には、当初の経由地Ｂを、同じジャンル（ガソリンスタンド）に属する別の経由地Ｂ’に置き換えて再度経路探索を行い、経路誘導を行う。
【００６４】
すなわち、本実施形態では、図１０に示すような代替可能リストをあらかじめ用意しておく。そして、出発前あるいは経路誘導中に経由地や目的地への到着予想時刻を計算する度に、当該到着予想時刻が営業終了時刻を過ぎるかどうかを判断し、過ぎる場合には代替可能リストを参照する。これにより、目的地および経由地の少なくとも一方を、営業終了時刻よりも前に到着可能な代替地点に置き換えて、その上で経路探索を行うようにする。
【００６５】
図１０に示す代替可能リストでは、図２に示した代替可能リストが持つ情報に加えて、各地点の営業終了時刻に関する情報を記憶している。
【００６６】
図１１は、第２の実施形態に係るナビゲーション装置の構成例を示すブロック図である。なお、この図１１において、図３に示した符号と同一の符号を付したものは互いに同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００６７】
図１１において、３４は地点情報メモリであり、経由地または目的地に設定される各地点の詳細情報を記憶する。この詳細情報の中には、その地点の名称、住所、電話番号、営業開始時間、営業終了時間などの情報が含まれている。３５は代替リストメモリであり、図１０に示したような代替可能リストを記憶する。
【００６８】
本実施形態においてＣＰＵ１９は、最初の経路探索時および、そのとき設定された初期経路に沿って経路誘導を実行している際の適当なタイミング毎に、経由地および目的地への到着予想時刻を算出する。これは、地図データ中に含まれている距離情報と走行速度情報とから求めることが可能である。ＣＰＵ１９は、求めた到着予想時刻と、経由地および目的地に関して地点情報メモリ３４に記憶されている営業終了時刻とを比較し、到着予想時刻が営業終了時刻を過ぎるかどうかを判断する。
【００６９】
ここで、到着予想時刻が営業終了時刻を過ぎると判断した場合は、代替リストメモリ３５に記憶されている図１０のような代替可能リストを参照して、到着予想時刻が営業終了時刻を過ぎると予想される目的地または経由地を、営業終了時刻よりも前に到着可能な代替地点に置き換える。そして、新たに設定した代替地点を通る誘導経路を探索し、その結果に基づいて経路誘導を行う。
【００７０】
次に、上記のように構成した本実施形態のナビゲーション装置による代替ルート自動探索の動作について説明する。図１２は、本実施形態による代替ルート自動探索処理の全体の流れを示すフローチャートである。図１２に示すフローチャートは、ＣＰＵ１９が経由地および目的地への到着予想時刻を算出したことをトリガとして実行される。
【００７１】
図１２において、ＣＰＵ１９は、当初の目的地および経由地について算出した到着予想時刻と、地点情報メモリ３４に記憶されている営業終了時刻とを比較して、目的地および経由地への到着予想時刻がそれらの営業終了時刻を過ぎるか否かを判定する（ステップＳ１１）。到着予想時刻が営業終了時刻を過ぎない場合は、以降は何もせずに処理を終了する（現在の経路誘導を引き続き行う）。
【００７２】
一方、到着予想時刻が営業終了時刻を過ぎる場合は、代替リストメモリ３５に記憶されている図１０のような代替可能リストを参照して、代替可否の情報に基づいて、当該目的地および経由地が他の地点に代替可能かどうかを判定する（ステップＳ１２）。代替可能でない場合は、その旨のメッセージを表示装置３０に表示して（ステップＳ１５）、処理を終了する。
【００７３】
目的地または経由地の代替が可能な場合は、代替可能リストを参照して代替可能な地点を探索する（ステップＳ１３）。そして、その探索した代替地点について代替可能リストに登録されている営業終了時刻と、当該代替地点について新たに算出した到着予想時刻とを比較し、その代替地点に営業終了時刻前に到着可能かどうかを判定する（ステップＳ１４）。
【００７４】
ここでは、代替地点について新たに算出した到着予想時刻を、代替可能リスト中に登録されている営業終了時刻と比較することによって営業終了時刻前に到着可能かどうかを判定しているが、当該代替地点について地点情報メモリ３４に記憶されている営業終了時刻と比較することによって営業終了時刻前に到着可能かどうかを判定するようにしても良い。この場合、代替可能リスト中に営業終了時刻の情報は不要であり、図２に示したものと同様で良い。
【００７５】
上記ステップＳ１４において、代替地点にも営業終了時刻前に到着できないと予想される場合には、その旨のメッセージを表示装置３０に表示して（ステップＳ１５）、処理を終了する。一方、代替地点に営業終了時刻前に到着できると予想される場合は、その代替地点を新たな目的地および経由地に設定する（ステップＳ１６）。そして、この新たに設定した代替地点を通る代替ルートの探索を行い（ステップＳ１７）、その結果を表示装置３０に表示して（ステップＳ１８）、処理を終了する。
【００７６】
なお、上記第２の実施形態では、初期経路上の経由地または目的地への到着予想時刻が営業終了時刻を過ぎるか否かに応じて代替ルートの探索を行う例について説明しているが、到着予想時刻が営業開始時刻よりも前になるか否かに応じて代替ルートの探索を行うようにしても良い。また、経由地および目的地が休業日か否かに応じて代替ルートの探索を行うようにしても良い。
【００７７】
以上詳しく説明したように、第２の実施形態によれば、初期経路上の経由地または目的地への到着予想時刻が営業時間外となる場合に、それらを代替地点に適宜置き換えて、当該代替地点を通る代替ルートを探索するようにしている。これにより、ユーザが経由地や目的地を設定し直すなどの煩わしい操作をすることなく、営業時間内に到着可能な経由地や目的地を通る代替経路を設定することができる。
【００７８】
なお、上記第１および第２の実施形態では、渋滞区間中に経由地または目的地が含まれているか否か、経由地または目的地への到着予想時刻が営業時間内か否かに応じて代替地点を設定する例について説明したが、本発明はこの例に限定されるものではない。
【００７９】
例えば、経由地や目的地が進行方向に向かって左手側にあるか右手側にあるかに応じて代替地点を設定するようにしても良い。例えば、最初に設定した経由地が進行方向の右手側にある場合に、その付近で進行方向の左手側にある代替地点を探して置き換えるといった具合である。経由地や目的地は進行方向の左手側にある方が、出入りが楽にできるからである。
【００８０】
また、経由地や目的地に設定した銀行やコンビニエンスストア等の込み具合に応じて代替地点を設定するようにしても良い。例えば、最初に設定した経由地が混雑している場合に、混雑していない付近の代替地点を探して置き換えるといった具合である。この場合には、経由地や目的地の混雑情報を何らかの手段で受信することが必要となる。これには、例えば携帯電話網を利用して携帯電話経由で混雑情報を受信してナビゲーション装置に提供したり、いわゆる無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ、特定省電力無線機などの通信手段を利用してナビゲーション装置にて直接受信するなどの方法が考えられる。
【００８１】
また、経由地や目的地に駐車場があるか否か等に応じて代替地点を設定するようにしても良い。例えば、最初に設定した経由地や目的地に駐車場がないか、あっても満車状態である場合に、駐車場があって空車状態となっている付近の代替地点を探して置き換えるといった具合である。この場合にもナビゲーション装置は、駐車場の空き情報を何らかの手段で受信することが必要となる。
【００８２】
その他、上記に説明した各実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその精神、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【００８３】
【発明の効果】
本発明は上述したように、経由地または目的地に設定される地点の代替地点に関する情報を代替可能リストとしてあらかじめ記憶しておき、所定のトリガが与えられたときに代替情報を参照し、目的地および経由地の少なくとも一方を代替地点に適宜置き換えて代替経路を探索するようにしたので、ユーザが経由地や目的地を設定し直すなどの煩わしい操作をしなくても、走行中の状況変化等によって経由地や目的地を適宜変更して経路誘導を行うことができる。
【図面の簡単な説明】
【図１】第１の実施形態に係る渋滞回避ルート探索処理の概要を説明するための図である。
【図２】第１の実施形態に係る代替可能リストの例を示す図である。
【図３】第１の実施形態に係るナビゲーション装置の構成例を示すブロック図である。
【図４】ＤＶＤ−ＲＯＭに記録された地図データに含まれる道路ユニットの全体構成を示す図である。
【図５】道路ユニットに含まれる各種テーブルの詳細な内容を示す図である。
【図６】ＤＶＤ−ＲＯＭに記録された地図データの描画ユニットに含まれるＶＩＣＳ変換レイヤの詳細な内容を示す図である。
【図７】ＶＩＣＳ情報に含まれる渋滞情報を示す図である。
【図８】第１の実施形態に係る渋滞回避ルート自動探索処理の全体の流れを示すフローチャートである。
【図９】第２の実施形態に係る代替ルート探索処理の概要を説明するための図である。
【図１０】第２の実施形態に係る代替可能リストの例を示す図である。
【図１１】第２の実施形態に係るナビゲーション装置の構成例を示すブロック図である。
【図１２】第２の実施形態に係る代替ルート自動探索処理の全体の流れを示すフローチャートである。
【図１３】従来の渋滞回避ルート探索処理の概要を説明するための図である。
【符号の説明】
１１　ＤＶＤ−ＲＯＭ
１２　ＤＶＤ−ＲＯＭ制御部
１３　位置測定装置
１４　地図情報メモリ
１５　代替リストメモリ
１６　ビーコン送受信機
１７　リモコン
１８　リモコンインタフェース
１９　ＣＰＵ
２０　ＲＯＭ
２１　ＲＡＭ
２２　誘導経路メモリ
２３　交差点拡大図メモリ
２４　ディスプレイコントローラ
２５　ビデオＲＡＭ
２６　メニュー発生部
２７　誘導経路発生部
２８　マーク発生部
２９　画像合成部
３０　表示装置
３１　音声発生部
３２　スピーカ
３３　バス
３４　地点情報メモリ
３５　代替リストメモリ
【図１】
2004093240.tif 000003
【図２】
2004093240.tif 000004
【図３】
2004093240.tif 000005
【図４】
2004093240.tif 000006
【図５】
2004093240.tif 000007
【図６】
2004093240.tif 000008
【図７】
2004093240.tif 000009
【図８】
2004093240.tif 000010
【図９】
2004093240.tif 000011
【図１０】
2004093240.tif 000012
【図１１】
2004093240.tif 000013
【図１２】
2004093240.tif 000014
【図１３】
2004093240.tif 000015