(57)【要約】【課題】誘導経路上に渋滞が発生した場合、当該渋滞をなるべく遠回りせずに回避することが可能な経路を探索できるようにすることが可能な「ナビゲーション装置および誘導経路探索方法」を提供する。【解決手段】渋滞情報に基づいて車両の進行方向前方の誘導経路上に渋滞区間が存在すると判断した場合、渋滞区間に存在する何れかの交差点を仮経由地として設定し、現在位置から仮経由地を経由して目的地に至る第２の誘導経路を探索することにより、仮経由地として設定された地点の近辺道路を対象とした経路探索に詳細レベルの地図データが用いられるようにする。これにより、渋滞区間から遠くならない迂回経路が探索される可能性が高くなるようにし、なるべく遠回りせずに渋滞を回避することが可能な経路を探索することができるようにする。【選択図】図１
2011027610.tif 000002
【特許請求の範囲】
【請求項１】
車両の現在位置を検出する車両位置検出部と、
前記車両位置検出部により検出された前記現在位置と地図データ記憶部に記憶された地図データとに基づいて、予め設定された目的地までの誘導経路を探索する第１の誘導経路探索部と、
渋滞情報を取得する渋滞情報取得部と、
前記渋滞情報取得部により取得された渋滞情報に基づいて、前記車両の進行方向前方の前記誘導経路上に渋滞区間が存在するか否かを判定する渋滞判定部と、
前記渋滞判定部により前記渋滞区間が存在すると判定された場合、前記誘導経路上にあり当該渋滞区間の先頭から前記目的地側に数えて所定数以内の交差点、または、当該渋滞区間に存在する何れかの交差点を仮経由地として設定する仮経由地設定部と、
前記地図データに基づいて、前記現在位置から当該仮経由地を経由して前記目的地に至る第２の誘導経路を探索する第２の誘導経路探索部とを備えたことを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置において、
前記渋滞判定部により前記誘導経路上に前記渋滞区間が存在すると判定された場合、前記渋滞区間に要衝が存在するか否かを判定する要衝判定部を更に備え、
前記仮経由地設定部は、前記要衝判定部により前記渋滞区間に要衝が存在すると判定された場合に前記仮経由地を設定することを特徴とするナビゲーション装置。
【請求項３】
請求項１に記載のナビゲーション装置において、
前記渋滞判定部により前記誘導経路上に前記渋滞区間が存在すると判定された場合、前記渋滞区間を通らずに、前記現在位置から前記目的地に至る第３の誘導経路を探索する第３の誘導経路探索部と、
前記地図データと前記渋滞情報取得部により取得された渋滞情報とに基づいて、前記誘導経路で前記目的地に至るまでのコストと前記第３の誘導経路で前記目的地に至るまでのコストとを比較し、前記第３の誘導経路でのコストが前記誘導経路でのコストより所定値以上大きいか否かを判定するコスト判定部とを更に備え、
前記仮経由地設定部は、前記コスト判定部により前記第３の誘導経路でのコストが前記誘導経路でのコストより所定値以上大きいと判定された場合に前記仮経由地を設定することを特徴とするナビゲーション装置。
【請求項４】
請求項１に記載のナビゲーション装置において、
前記渋滞判定部により前記誘導経路上に前記渋滞区間が存在すると判定された場合、前記渋滞区間を通らずに、前記現在位置から前記目的地に至る第３の誘導経路を探索する第３の誘導経路探索部と、
前記地図データと前記渋滞情報取得部により取得された渋滞情報とに基づいて、前記第２の誘導経路で前記目的地に至るまでのコストと前記第３の誘導経路で前記目的地に至るまでのコストとを比較し、前記第２の誘導経路でのコストが前記第３の誘導経路でのコストより小さいか否かを判定するコスト判定部とを更に備え、
前記仮経由地設定部は、前記コスト判定部により前記第２の誘導経路でのコストが前記第３の誘導経路でのコストより小さくないと判定された場合、前記仮経由地設定部により仮経由地として設定された交差点から前記渋滞区間における渋滞終了地点までの間に存在する交差点のうち、当該設定された交差点から前記現在位置側に向かって１つ目の交差点を新たな仮経由地として再設定し、
前記第２の誘導経路探索部は、前記地図データに基づいて、前記現在位置から前記仮経由地設定部により再設定された仮経由地を経由して前記目的地に至る第２の誘導経路を再探索することを特徴とするナビゲーション装置。
【請求項５】
請求項１に記載のナビゲーション装置において、
前記仮経由地設定部は、前記誘導経路上にあり当該渋滞区間の先頭から前記目的地側に数えて所定数以内の交差点および前記渋滞区間に存在する交差点のうち、当該誘導経路に左折で進入した後にそのまま前記目的地側に進行可能な交差点を前記仮経由地として設定することを特徴とするナビゲーション装置。
【請求項６】
車両の現在位置を検出する現在位置検出部と、前記現在位置検出部により検出された前記現在位置と地図データ記憶部に記憶された地図データとに基づいて、目的地までの誘導経路を探索する誘導経路探索部とを備えたナビゲーション装置における誘導経路探索方法であって、
渋滞情報を取得する第１のステップと、
前記第１のステップにより取得された渋滞情報に基づいて、前記車両の進行方向前方の前記誘導経路上に渋滞区間が存在するか否かを判定する第２のステップと、
前記第２のステップにより前記誘導経路上に前記渋滞区間が存在すると判定された場合、前記誘導経路上にあり当該渋滞区間の先頭から前記目的地側に数えて所定数以内の交差点、または、当該渋滞区間に存在する何れかの交差点を仮経由地として設定する第３のステップと、
前記地図データに基づいて、前記現在位置から前記仮経由地を経由して前記目的地に至る第２の誘導経路を探索する第４のステップとを有することを特徴とする誘導経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置および誘導経路探索方法に関し、特に、最初に設定された誘導経路の走行中に、受信した道路交通情報に応じて、渋滞を避ける迂回経路を自動的に再探索する機能を有するナビゲーション装置に用いて好適なものである。
【背景技術】
【０００２】
一般に、車載用のナビゲーション装置では、自律航法センサやＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）受信機などを用いて車両の現在位置を検出し、その近傍の地図データを記録媒体から読み出して画面上に表示する。そして、画面上の所定箇所に自車位置を示す自車位置マークを重ね合わせて表示することにより、車両の現在位置を一目で分かるようにしている。
【０００３】
最近のナビゲーション装置は、道路交通情報センタから送られてくるＶＩＣＳ道路交通情報（ＶＩＣＳ情報：ＶＩＣＳは登録商標）を受信して、刻々と変化する道路状況をナビゲーション画面上に表示できるようになっているものが多い。ＶＩＣＳ機能を搭載したナビゲーション装置では、渋滞情報や規制情報といった道路交通情報をユーザに提供することが可能である。
【０００４】
また、ナビゲーション装置の殆どには、運転者が所望の目的地に向かって道路を間違うことなく容易に走行できるようにした経路誘導機能が搭載されている。この経路誘導機能では、地図データを用いて現在地から目的地までを結ぶ最もコストが小さな経路を自動探索し、その探索した経路を誘導経路として地図画面上で他の道路とは色を変えて太く描画する。また、車両が誘導経路上の案内交差点に一定距離内に近づいたときに交差点拡大図を表示して交差点案内を行うことにより、運転者を目的地まで案内するようになっている。
【０００５】
なお、コストとは、例えば距離をもとに、道路幅員、道路種別、右左折の別、交通規制などに応じて所定の定数を乗じた値であり、誘導経路として適正の程度を数値化したものである。距離が同一の２つの経路があったとしても、時間優先、距離優先、一般道路優先、高速道路優先、道幅優先などの探索条件を指定することにより、コストは異なったものとなる。経路探索処理においては、交差点や分岐など複数の道路が交わる点をノード、隣接するノード間を結ぶベクトルをリンクとして、現在地から目的地に至る様々な経路上のリンクコストを順次加算し、リンクコストの合計が最も小さい経路を誘導経路として設定する。
【０００６】
上述したＶＩＣＳ機能を搭載したナビゲーション装置では、誘導経路の設定時に、受信したＶＩＣＳ情報に応じて、渋滞を避ける迂回経路を自動的に再探索するように成されている。この種の迂回経路探索機能では、ＶＩＣＳ情報により特定される渋滞区間のリンクコストに対して充分に大きな重みを付加した上で、迂回経路の探索を行う。このように、現在発生している渋滞を回避する迂回経路を探索して利用者に提供することにより、利用者が渋滞に巻き込まれることを未然に防ぐことができる。
【０００７】
なお、渋滞を避ける迂回経路を探索する技術に関連して、当該渋滞を回避するための迂回経路をユーザが選べるようにした技術が開示されている（例えば、特許文献１を参照）。特許文献１に記載の技術では、車両が進むべき誘導経路上において、例えば、渋滞等により走行を回避するための回避区間を設定し、当該設定した回避区間を迂回する複数の迂回経路を探索する。そして、複数の迂回経路の中からユーザにより選択された迂回経路を含む経路を新たな誘導経路に変更するようにしている。
【０００８】
また、ＶＩＣＳなどから取得した渋滞情報に基づいて、渋滞している道路の付近の渋滞状況を推定し、当該推定した渋滞状況に基づいて現在地から目的地までの経路情報を作成する技術が開示されている（例えば、特許文献２を参照）。
【０００９】
また、経路上に渋滞または混雑が予測される道路区間がある場合、その道路区間の道路種別を判断し、その道路種別に応じて予め設定された距離範囲内で、当該道路区間を回避するための迂回路を地図データに基づいて探索する技術が開示されている（例えば、特許文献３を参照）。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００２−２４３４８０号公報
【特許文献２】特開２００６−１６２３９８号公報
【特許文献３】特開２００８−２０４１４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ところで、道路には、例えば橋、踏み切りおよびトンネルのように、そこを通らざるを得ないという要衝がある。要衝では、その要衝を含む道路に並行する道路が近傍に存在しないことが多いか、あっても細街路のような細い道路で主要道路ではないことが多い。そのため、車両が要衝に集中することにより当該道路に渋滞が発生しやすい。
【００１２】
従来のナビゲーション装置では、誘導経路上の要衝付近に渋滞が発生した場合、要衝の有無を考慮して経路を探索するのではなく、当該渋滞が発生している道路を単に回避するための経路を探索している。このため、渋滞が発生している要衝から遠く離れた道路を通行する遠回りの経路が探索されてしまうという問題があった。
【００１３】
図１０（ａ）は、自車両が目的地（Ｇ）へ向かって誘導経路（当初ルート）を走行している時に、当該誘導経路上の要衝である橋付近に渋滞が発生した様子を示している。図１０（ａ）に示すように、橋付近に発生した渋滞を回避するために、当該橋から遠く離れた別の橋を渡る遠回りの経路（渋滞回避ルート）が探索されてしまっている。
【００１４】
図１０（ｂ）は、自車両が目的地（Ｇ）へ向かって誘導経路（当初ルート）を走行している時に、当該誘導経路上の要衝である踏み切り付近に渋滞が発生した様子を示している。図１０（ｂ）に示すように、踏み切り付近に発生した渋滞を回避するために、当該踏み切りから遠く離れた別の踏み切りを渡る遠回りの経路（渋滞回避ルート）が探索されてしまっている。
【００１５】
図１０（ｃ）は、自車両が目的地（Ｇ）へ向かって誘導経路（当初ルート）を走行している時に、当該誘導経路上の要衝であるトンネル付近に渋滞が発生した様子を示している。図１０（ｃ）に示すように、トンネル付近に発生した渋滞を回避するために、当該トンネルが存在する山を迂回する遠回りの経路（渋滞回避ルート）が探索されてしまっている。
【００１６】
図１０（ａ）〜（ｃ）を用いて説明したように、要衝を含む道路に並行する道路が近傍に存在しても、渋滞が発生している要衝から遠く離れた道路を通行する遠回りの経路が探索されてしまう原因は、従来のナビゲーション装置における経路探索手法では、経路探索に使用可能なメモリ容量に制限があることや経路探索処理に用いる地図データ量が多くなるなどの問題により、全ての道路を経路探索の対象とすることができない点にある。
【００１７】
つまり、図１０（ａ）〜（ｃ）では、破線で示したような主要道路でない道路は、渋滞を回避するための経路を探索する際に対象とならない。そのため、主要道路でない道路も含めた全ての道路を経路探索の対象とすれば、遠回りをしない経路を探索することができる場合もあるのに、従来のナビゲーション装置ではそれができない。
【００１８】
この問題を、図１１を用いて詳しく説明する。図１１は、図１１（ａ）の自車位置１０から、図１１（ｅ）の目的地２０までの誘導経路を探索する様子を示している。なお、経路探索に用いる地図データベースには、細街路から高速道路まで全ての道路を格納したレベル０といわれる道路メッシュ、主に市道以上の道路を格納し、かつ、その対象領域を広くとっているレベル１といわれる道路メッシュ、高速道路や有料道路といった道路を広範囲にわたって格納しているレベル２といわれる道路メッシュがそれぞれ区別されて格納されている。
【００１９】
まず、図１１（ａ）に示すように、誘導経路の探索は、自車位置１０の周辺では、全ての道路を含むレベル０の道路メッシュ３０を使用して行う。そして、レベル１の道路メッシュ４０へのアップリンク５０（レベル０の道路メッシュ３０からレベル１の道路メッシュ４０への接続点）に探索枝が到達すると、図１１（ｂ）に示すように、アップリンク５０に対応するリンクを含むレベル１の道路メッシュ４０に切り替えて経路探索を行う。同様に、レベル１での経路探索によりレベル２へのアップリンク６０（レベル１の道路メッシュ４０からレベル２の道路メッシュ７０への接続点）に探索枝が到達すると、図１１（ｃ）に示すレベル２の道路メッシュ７０に切り替えて経路探索を行う。
【００２０】
一方、図１１（ｅ）に示すように、誘導経路の探索は、目的地２０の周辺では、全ての道路を含むレベル０の道路メッシュ８０を使用して行う。そして、目的地２０から逆に辿っていってレベル１の道路メッシュ９０へのアップリンク１００に探索枝が到達すると、図１１（ｄ）に示すように、アップリンク１００に対応するリンクを含むレベル１の道路メッシュ９０に切り替えて経路探索を行う。同様に、レベル１での経路探索によりレベル２へのアップリンク１１０（レベル１の道路メッシュ９０からレベル２の道路メッシュ７０への接続点）に探索枝が到達すると、図１１（ｃ）に示すレベル２の道路メッシュ７０に切り替えて経路探索を行う。
【００２１】
最後に、図１１（ｃ）に示すように、自車位置１０から経路探索により求めたレベル２の道路メッシュ７０上のアップリンク６０と目的地２０から経路探索により求めたレベル２の道路メッシュ７０上のアップリンク１１０とをつなぐ経路を、レベル２の道路メッシュ７０を用いた経路探索を行うことにより求める。これにより、自車位置１０から目的地２０に至る経路が全て決定されて、誘導経路の探索処理は終了する。
【００２２】
以上説明したような経路探索を行うことによって、自車位置から目的地までの経路を求めるために、細街路から高速道路まで全ての道路が格納されたレベル０の道路メッシュを全区間にわたって使用する必要がなくなる。そのため、経路探索に必要なリソース量を抑制することができる。この反面、自車位置と目的地との間の中間地点付近の探索にはレベル０の道路メッシュが使用されない。よって、自車位置と目的地との間の中間地点付近に存在する要衝で渋滞が発生した場合、その要衝の近辺で全ての道路を経路探索の対象とすれば、遠回りをしない経路を探索することが可能な場合があっても、当該要衝近辺の詳細道路は経路探索の対象外とされてしまうことにより、遠回りしない経路を探索することができないという問題があった。
【００２３】
なお、上記したような問題は、自車位置と目的地との間の中間地点付近に存在する要衝で渋滞が発生した場合以外でも生じ得る。
【００２４】
本発明は、このような問題を解決するために成されたものであり、誘導経路上に渋滞が発生した場合、なるべく遠回りせずに渋滞を回避することが可能な経路を探索できるようにすることを目的とする。
【課題を解決するための手段】
【００２５】
上記した課題を解決するために、本発明では、渋滞情報に基づいて車両の進行方向前方の誘導経路上に渋滞区間が存在すると判断した場合、当該誘導経路上にあり渋滞区間の先頭から目的地側に数えて所定数以内の交差点、または、当該渋滞区間に存在する何れかの交差点を仮経由地として設定し、自車位置から当該仮経由地を経由して目的地に至る第２の誘導経路を探索するようにしている。
【発明の効果】
【００２６】
上記のように構成した本発明によれば、仮経由地として設定された地点の近辺道路を対象とした経路探索には細街路から高速道路までの全ての道路が格納された詳細レベルの地図データが用いられることとなるので、渋滞区間から遠くならない迂回経路が探索される可能性が高くなる。よって、誘導経路上に渋滞が発生した場合、なるべく遠回りせずに渋滞を回避することが可能な経路を探索することができる。
【図面の簡単な説明】
【００２７】
【図１】第１の実施形態によるナビゲーション装置の機能構成例を示すブロック図である。
【図２】第１の実施形態によるナビゲーション装置にて使用される各種情報の構成例を示す図である。
【図３】第１の実施形態による仮経由地設定処理の例を示す図である。
【図４】誘導経路上の要衝付近に渋滞が発生したときに探索された第２の誘導経路の例を示す図である。
【図５】第１の実施形態によるナビゲーション装置の動作例を示すフローチャートである。
【図６】第２の実施形態によるナビゲーション装置の機能構成例を示すブロック図である。
【図７】第２の実施形態によるナビゲーション装置にて使用される各種情報の構成例を示す図である。
【図８】第２の実施形態による誘導経路探索処理の例を示す図である。
【図９】第２の実施形態によるナビゲーション装置の動作例を示すフローチャートである。
【図１０】誘導経路上の要衝付近に渋滞が発生したときに探索されるルートの従来例を示す図である。
【図１１】従来のナビゲーション装置における誘導経路探索処理の例を示す図である。
【発明を実施するための形態】
【００２８】
以下、本発明の第１の実施形態を図面に基づいて説明する。図１は、第１の実施形態によるナビゲーション装置２００の機能構成例を示すブロック図である。図１において、２１１はＤＶＤ−ＲＯＭ等の記録媒体であり、地図表示や経路探索等に必要な各種の地図データを記憶している。ＤＶＤ−ＲＯＭ２１１に記録された地図データは、広い地域を一望するための上位レベルの地図（縮尺の小さい地図）から、狭い地域を詳細に記述した下位レベルの地図（縮尺の大きい地図）まで、レベルと呼ばれる単位に階層化して管理されている。各レベルの地図データには、地図表示に必要な描画ユニットのデータ（地図上に存在する道路や建物、施設に関する各種のデータ）の他に、マップマッチングや経路探索等の各種の処理に必要な道路ユニットのデータが含まれている。道路ユニットのデータは、各道路リンクに関する道路リンク情報と各ノードに関するノード情報とから構成されている。なお、ここでは地図データや施設情報を記憶する記録媒体としてＤＶＤ−ＲＯＭ２１１を用いているが、ＣＤ−ＲＯＭ、ハードディスク、半導体メモリ等の他の記録媒体を用いても良い。
【００２９】
図２（ａ）は、本実施形態の地図データに含まれる道路リンク情報の詳細を示す図である。図２（ａ）に示すように、道路リンク情報は、道路リンクを識別するための「道路リンクＩＤ」、当該道路リンクの開始ノードを識別するための「開始ノードＩＤ」、当該道路リンクの終了ノードを識別するための「終了ノードＩＤ」、当該道路リンクのコストを示す「リンクコスト」および、当該道路リンクに対応する道路上に要衝がある場合における当該要衝の種類（例えば、橋、踏み切りまたはトンネルなど）を示す「要衝種別」を項目情報として含む。なお、道路リンクに対応する道路上に要衝がない場合、項目情報「要衝種別」の値には「なし」が設定される。道路リンク情報には、実際にはこれ以外の情報もあるが、ここでは本発明に特に関係するもののみを示した。
【００３０】
図２（ｂ）は、本実施形態の地図データに含まれるノード情報の詳細を示す図である。図２（ｂ）に示すように、ノード情報は、ノードを識別するための「ノードＩＤ」、当該ノードの緯度を示す「緯度」、当該ノードの経度を示す「経度」、当該ノードに接続されている道路リンクを表す「接続道路情報」、および当該ノードが交差点であるか否かを示す「属性フラグ」を項目情報として含む。具体的には、項目情報「接続道路情報」には、ノードに進入する道路リンクの道路リンクＩＤおよび進入方向、当該ノードから脱出する道路リンクの道路リンクＩＤおよび脱出方向が設定されている。なお、ノード情報には実際にはこれ以外の情報もあるが、ここでは本発明に特に関係するもののみを示した。
【００３１】
２１２は車両の現在位置を所定間隔毎に検出する車両位置検出部であり、自立航法センサ、ＧＰＳ受信機、位置計算用ＣＰＵ等で構成されている。自立航法センサは、所定走行距離毎に１個のパルスを出力して車両の移動距離を検出する車速センサ（距離センサ）と、車両の回転角度（移動方位）を検出する振動ジャイロ等の角速度センサ（相対方位センサ）とを含む。自立航法センサは、これらの車速センサおよび角速度センサによって車両の相対位置および方位を検出する。
【００３２】
位置計算用ＣＰＵは、自立航法センサから出力される自車両の相対的な位置および方位のデータに基づいて、絶対的な自車位置（推定車両位置）および車両方位を計算する。また、ＧＰＳ受信機は、複数のＧＰＳ衛星から送られてくる電波をＧＰＳアンテナで受信して、３次元測位処理あるいは２次元測位処理を行って車両の絶対位置および方位を計算する（車両方位は、現時点における自車位置と１サンプリング時間ΔＴ前の自車位置とに基づいて計算する）。
【００３３】
２１３は地図データ記憶部であり、ＤＶＤ−ＲＯＭ制御部２１４の制御によってＤＶＤ−ＲＯＭ２１１から読み出された地図データを一時的に格納する。ＤＶＤ−ＲＯＭ制御部２１４は、ＤＶＤ−ＲＯＭ２１１からの地図データの読み出しを制御する。すなわち、ＤＶＤ−ＲＯＭ制御部２１４は、車両位置検出部２１２から車両現在位置の情報を入力し、その車両現在位置を含む所定範囲の地図データの読み出し指示を出力することにより、地図表示や誘導経路の探索に必要な地図データをＤＶＤ−ＲＯＭ２１１から読み出して地図データ記憶部２１３に格納する。
【００３４】
２１５はリモコン、タッチパネルまたは操作スイッチ等の操作部であり、ユーザがナビゲーション装置２００に対して各種の情報（例えば、経路誘導の目的地や経由地）を設定したり、各種の操作（例えば、メニュー選択操作、地図の拡大／縮小操作、手動地図スクロール、数値入力など）を行ったりするためのものである。
【００３５】
２１６は目的地設定部であり、ディスプレイ２１７に表示されている目的地設定用の操作画面において、ユーザによる操作部２１５の操作を介して指定された地点を目的地として設定する。そして、目的地設定部２１６は、設定した目的地を示す目的地情報を誘導経路探索部２１８に出力する。
【００３６】
誘導経路探索部２１８は、車両位置検出部２１２により検出された自車位置情報と地図データ記憶部２１３に記憶されている地図データとに基づいて、目的地設定部２１６から出力された目的地情報により示される目的地までの誘導経路を探索する。また、誘導経路探索部２１８は、仮経由地設定部２１９から仮経由地情報が出力された場合、車両位置検出部２１２により検出された自車位置情報と地図データ記憶部２１３に記憶されている地図データとに基づいて、仮経由地情報により示される仮経由地を経由して目的地に至る第２の誘導経路を探索する。この第２の誘導経路の具体的な探索処理については後述する。なお、誘導経路探索部２１８は、本発明の第１の誘導経路探索部および第２の誘導経路探索部に対応する。
【００３７】
２２０は誘導経路メモリであり、誘導経路探索部２１８により誘導経路が探索された場合、その探索された誘導経路のデータ（現在位置から目的地に至るまでの道路リンクの集合）を誘導経路情報として一時的に格納する。図２（ｃ）は、本実施形態の誘導経路情報の詳細を示す図である。図２（ｃ）に示すように、誘導経路情報は、誘導経路を構成する道路リンクを識別するための「道路リンクＩＤ」、当該道路リンクに対応する道路上に要衝がある場合における当該要衝の種類を示す「要衝種別」を項目情報として含む。
【００３８】
また、誘導経路メモリ２２０は、誘導経路探索部２１８により第２の誘導経路が探索された場合、その探索された第２の誘導経路のデータ（現在位置から目的地に至るまでの道路リンクの集合）を第２の誘導経路情報として一時的に格納する。図２（ｄ）は、本実施形態の第２の誘導経路情報の詳細を示す図である。図２（ｄ）に示すように、第２の誘導経路情報は、第２の誘導経路を構成する道路リンクを識別するための「道路リンクＩＤ」、当該道路リンクに対応する道路上に要衝がある場合における当該要衝の種類を示す「要衝種別」を項目情報として含む。
【００３９】
２２１は地図表示制御部であり、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データとに基づいて自車位置周辺の地図画像データを生成する。そして、地図表示制御部２２１は、生成した地図画像データをディスプレイ２１７に出力する。
【００４０】
２２２は誘導経路案内部であり、誘導経路探索部２１８により誘導経路が探索された場合、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０に格納された誘導経路情報とに基づいて誘導経路案内を行う。具体的には、誘導経路案内部２２２は、ディスプレイ２１７に対して、地図表示制御部２２１により生成された地図画像に重ねて誘導経路を他の道路とは異なる色で太く表示することにより、誘導経路の目的地までの走行案内を行う。
【００４１】
また、誘導経路案内部２２２は、誘導経路探索部２１８により第２の誘導経路が探索された場合、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０に格納された第２の誘導経路情報とに基づいて誘導経路案内を行う。具体的には、誘導経路案内部２２２は、ディスプレイ２１７に対して、地図表示制御部２２１により生成された地図画像に重ねて第２の誘導経路を他の道路とは異なる色で太く表示することにより、第２の誘導経路の目的地までの走行案内を行う。
【００４２】
２２３は渋滞情報取得部であり、主に高速道路上に設置された電波ビーコン送受信機との間で電波を介して双方向通信を行うとともに、主に一般道路上に設置された光ビーコン送受信機との間で光を介して双方向通信を行うことにより、道路交通情報センタ（図示せず）からＶＩＣＳ情報（渋滞情報や規制情報といった道路交通情報）を取得する。そして、渋滞情報取得部２２３は、取得したＶＩＣＳ情報に含まれている渋滞情報を誘導経路探索部２１８、仮経由地設定部２１９、渋滞判定部２２４および要衝判定部２２５に出力する。
【００４３】
図２（ｅ）は、本実施形態の渋滞情報の詳細を示す図である。図２（ｅ）に示すように、渋滞情報は、渋滞が発生している道路リンクを識別するための「道路リンクＩＤ」および当該渋滞の種類（渋滞または混雑）を示す「渋滞種別」を項目情報として含む。
【００４４】
渋滞判定部２２４は、誘導経路メモリ２２０に格納された誘導経路情報と渋滞情報取得部２２３から出力された渋滞情報とに基づいて、車両の進行方向前方の誘導経路上に渋滞区間（渋滞、混雑の両方を含む）が存在するか否かを判定する。渋滞判定部２２４は、渋滞区間が存在すると判定した場合、その旨を要衝判定部２２５に通知する。
【００４５】
要衝判定部２２５は、渋滞区間が存在する旨の通知を渋滞判定部２２４から受けた場合、渋滞情報取得部２２３から出力された渋滞情報と誘導経路メモリ２２０に格納された誘導経路情報とに基づいて、誘導経路上の渋滞区間に要衝が存在するか否かを判定する。要衝判定部２２５は、誘導経路上の渋滞区間に要衝が存在すると判定した場合、その旨を仮経由地設定部２１９に通知する。要衝判定部２２５は、誘導経路上の渋滞区間に要衝が存在しないと判定した場合、仮経由地設定部２１９に何も通知しない。
【００４６】
仮経由地設定部２１９は、誘導経路上の渋滞区間に要衝が存在する旨の通知を要衝判定部２２５から受けた場合、渋滞情報取得部２２３から出力された渋滞情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０に格納された誘導経路情報とに基づいて、当該渋滞区間に存在する交差点のうち、当該誘導経路に左折で進入した後にそのまま目的地側に進行可能な交差点（以下、合流可能交差点ともいう）を仮経由地として設定する。そして、仮経由地設定部２１９は、設定した仮経由地を示す仮経由地情報を誘導経路探索部２１８に出力する。
【００４７】
次に、仮経由地設定部２１９による仮経由地設定処理を例を挙げて説明する。図３は、第１の実施形態による仮経由地設定処理の例を示す図である。図３（ａ）は、自車両が目的地（図示せず）へ向かって誘導経路（Ｒ１）を走行している場合、誘導経路（Ｒ１）上の要衝（道路リンク（Ｌ２）上にある）付近に渋滞が発生した様子を道路リンク（Ｌ１〜Ｌ８）およびノード（Ｎ１〜Ｎ５）で示している。
【００４８】
なお、図３に示す各道路リンクのうち、道路リンク（Ｌ１、Ｌ２、Ｌ５）で渋滞が発生しているものとする。図３（ｂ）は、道路リンク（Ｌ１〜Ｌ８）の道路リンク情報の各々を示したものである。図３（ｂ）に示すように、道路リンク（Ｌ２）上に要衝である橋が存在している。図３（ｃ）は、ノード（Ｎ１〜Ｎ５）のノード情報を示したものである。なお、図３（ｃ）に示す接続道路情報では、ノードに進入する道路リンクの進入方向、当該ノードから脱出する道路リンクの脱出方向の図示を省略している。図３（ｄ）は、誘導経路メモリ２２０に格納されている誘導経路情報を示したものである。
【００４９】
まず、仮経由地設定部２１９は、図３（ｂ）に示す各道路リンクの道路リンク情報と、図３（ｃ）に示す各ノードのノード情報と、渋滞情報とを参照することによって、渋滞区間に存在する交差点のうち最も目的地側に存在する交差点（Ｎ２）を特定する。次に、仮経由地設定部２１９は、図３（ｃ）に示すノード情報を参照することによって、さきほど特定した交差点（Ｎ２）の接続道路情報（Ｌ１、Ｌ２、Ｌ４）を参照することにより、交差点（Ｎ２）に左折で進入した後にそのまま目的地側に進行可能な道路リンクの特定を試みる。図３の例では、経路（Ｒ２）で示すように、交差点（Ｎ２）に左折で進入した後にそのまま目的地側に進行可能な道路リンク（Ｌ４）を特定することができたものとする。この場合、仮経由地設定部２１９は、交差点（Ｎ２）を仮経由地として設定する。これにより、合流可能交差点（Ｎ２）の近辺道路ではレベル０の道路メッシュを使用して経路探索をすることができる。
【００５０】
なお、仮経由地設定部２１９は、渋滞区間に存在する交差点のうち最も目的地側に存在する交差点が合流交差点でない場合、すなわち、当該交差点に左折で進入することができない場合、渋滞区間に存在する交差点のうち、当該交差点を除いて最も目的地側に存在する交差点を特定し、交差点に左折で進入した後にそのまま目的地側に進行可能な道路リンクの特定を試みる。
【００５１】
次に、誘導経路探索部２１８による第２の誘導経路の探索処理について具体的に説明する。誘導経路探索部２１８は、渋滞情報取得部２２３から出力された渋滞情報と仮経由地設定部２１９から出力された仮経由地情報とに基づいて、その仮経由地情報により示される仮経由地から渋滞区間における渋滞終了地点までの道路区間のリンクコストを例えば、無限大（通行不可）に変更する。一方、誘導経路探索部２１８は、仮経由地から渋滞区間における渋滞の先頭までの道路区間のリンクコストを数倍する。そして、誘導経路探索部２１８は、車両位置検出部２１２により検出された自車位置情報と地図データ記憶部２１３に記憶されている地図データと仮経由地設定部２１９から出力された仮経由地情報とに基づいて、自車位置から仮経由地を経由して目的地に至る第２の誘導経路を探索する。なお、誘導経路探索部２１８は、渋滞区間全域におけるリンクコストを数倍するようにしても良い。
【００５２】
図４は、誘導経路上の要衝付近に渋滞が発生したときに探索された第２の誘導経路の例を示す図である。図４（ａ）は、自車両２５０ａが目的地２６０ａへ向かって誘導経路２７０ａを走行している時に、誘導経路２７０ａ上の要衝である橋付近に渋滞２８０ａが発生した様子を示している。図４（ａ）に示すように、第２の誘導経路２９０ａは、橋付近に発生した渋滞２８０ａを回避するために、橋の直前の交差点２９５ａ（仮経由地）から左折にて元の誘導経路２７０ａに復帰する経路である。すなわち、交差点２９５ａの近辺ではレベル０の道路メッシュを使用をすることができるようになった結果、渋滞２８０ａを回避するための経路として、遠回りをする誘導経路３１０ａの代わりに第２の誘導経路２９０ａが経路探索できたわけである。
【００５３】
図４（ｂ）は、自車両２５０ｂが目的地２６０ｂへ向かって誘導経路２７０ｂを走行している時に、誘導経路２７０ｂ上の要衝である踏み切り付近に渋滞２８０ｂが発生した様子を示している。図４（ｂ）に示すように、第２の誘導経路２９０ｂは、踏み切り付近に発生した渋滞２８０ｂを回避するために、踏み切りの直前の交差点２９５ｂ（仮経由地）から左折にて元の誘導経路２７０ｂに復帰する経路である。すなわち、交差点２９５ｂの近辺ではレベル０の道路メッシュを使用をすることができるようになった結果、渋滞２８０ｂを回避するための経路として、遠回りをする誘導経路３１０ｂの代わりに第２の誘導経路２９０ｂが経路探索できたわけである。
【００５４】
図４（ｃ）は、自車両２５０ｃが目的地２６０ｃへ向かって誘導経路２７０ｃを走行している時に、誘導経路２７０ｃ上の要衝であるトンネル付近に渋滞２８０ｃが発生した様子を示している。図４（ｃ）に示すように、第２の誘導経路２９０ｃは、トンネル付近に発生した渋滞２８０ｃを回避するために、トンネルの直前の交差点２９５ｃ（仮経由地）から左折にて元の誘導経路２７０ｃに復帰する経路である。すなわち、交差点２９５ｃの近辺ではレベル０の道路メッシュを使用をすることができるようになった結果、渋滞２８０ｃを回避するための経路として、遠回りをする誘導経路３１０ｃの代わりに第２の誘導経路２９０ｃが経路探索できたわけである。
【００５５】
図４（ａ）〜（ｃ）を用いて説明したように、渋滞を迂回する経路の探索時に、仮経由地近辺でレベル０の詳細地図データを使用することができる。すなわち、要衝近辺の道路を使って渋滞の少なくとも一部を回避する第２の誘導経路２８０ａ，２８０ｂ，２８０ｃを探索することができるので、遠回りをする経路３１０ａ，３１０ｂ，３１０ｃを走行する必要がなくなり、より短い迂回距離で渋滞２８０ａ，２８０ｂ，２８０ｃを回避するルートを得ることが可能となる。
【００５６】
次に、第１の実施形態におけるナビゲーション装置２００の動作について説明する。図５は、自車両が目的地へ向かって誘導経路を走行している場合におけるナビゲーション装置２００の動作例を示すフローチャートである。
【００５７】
まず、渋滞情報取得部２２３は、道路交通情報センタ（図示せず）からＶＩＣＳ情報（渋滞情報や規制情報といった道路交通情報）を取得する（ステップＳ１００）。次に、渋滞判定部２２４は、誘導経路メモリ２２０に格納された誘導経路情報と渋滞情報取得部２２３から出力された渋滞情報とに基づいて、車両の進行方向前方の誘導経路上に渋滞区間が存在するか否かを判定する（ステップＳ１２０）。もし、誘導経路上に渋滞区間が存在しないと渋滞判定部２２４にて判定した場合（ステップＳ１２０にてＮＯ）、ナビゲーション装置２００は図５における処理を終了する。
【００５８】
一方、誘導経路上に渋滞区間が存在すると渋滞判定部２２４にて判定した場合（ステップＳ１２０にてＹＥＳ）、渋滞判定部２２４は、その旨を要衝判定部２２５に通知する。次に、要衝判定部２２５は、渋滞情報取得部２２３から出力された渋滞情報と、誘導経路メモリ２２０に格納された誘導経路情報とに基づいて、誘導経路上の渋滞区間に要衝が存在するか否かを判定する（ステップＳ１４０）。
【００５９】
もし、誘導経路上の渋滞区間に要衝が存在しないと要衝判定部２２５にて判定した場合（ステップＳ１４０にてＮＯ）、ナビゲーション装置２００は図５における処理を終了する。一方、誘導経路上の渋滞区間に要衝が存在すると要衝判定部２２５にて判定した場合（ステップＳ１４０にてＹＥＳ）、要衝判定部２２５は、その旨を仮経由地設定部２１９に通知する。
【００６０】
次に、仮経由地設定部２１９は、渋滞情報取得部２２３から出力された渋滞情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０に格納された誘導経路情報とに基づいて、渋滞区間に存在する交差点のうち、誘導経路に左折で進入した後にそのまま目的地側に進行可能な合流可能交差点を仮経由地として設定する（ステップＳ１６０）。そして、仮経由地設定部２１９は、設定した仮経由地を示す仮経由地情報を誘導経路探索部２１８に出力する。
【００６１】
次に、誘導経路探索部２１８は、渋滞情報取得部２２３から出力された渋滞情報と地図データ記憶部２１３に記憶されている地図データとに基づいて、渋滞区間におけるリンクコストを上述したように変更する（ステップＳ１８０）。そして、誘導経路探索部２１８は、車両位置検出部２１２により検出された自車位置情報と地図データ記憶部２１３に記憶されている地図データと仮経由地設定部２１９から出力された仮経由地情報とに基づいて、自車位置から仮経由地を経由して目的地に至る第２の誘導経路を探索する（ステップＳ２００）。
【００６２】
最後に、誘導経路案内部２２２は、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０に格納された第２の誘導経路情報とに基づいて、第２の誘導経路情報の誘導経路案内を開始する（ステップＳ２２０）。ステップＳ２２０の処理が完了することによって、ナビゲーション装置２００は、図５における処理を終了する。
【００６３】
以上詳しく説明したように、第１の実施形態では、渋滞情報に基づいて車両の進行方向前方の誘導経路上に渋滞区間が存在し、かつ、その渋滞区間に要衝が存在すると判定されたとき、当該渋滞区間に存在する交差点を仮経由地として設定し、自車位置から当該仮経由地を経由して目的地に至る第２の誘導経路を探索するようにしている。
【００６４】
このように構成した第１の実施形態によれば、仮経由地として設定された地点の近辺道路を対象とした経路探索には詳細レベルの地図データが用いられることとなるので、渋滞区間から遠くならない迂回経路が探索される可能性が高くなる。よって、誘導経路上に渋滞が発生した場合、なるべく遠回りせずに渋滞を回避することが可能な経路を探索することができる。
【００６５】
また、第１の実施形態では、渋滞区間に存在する交差点のうち、当該誘導経路に左折で進入した後にそのまま目的地側に進行可能な交差点を仮経由地として設定するようにしている。このように構成した第１の実施形態によれば、要衝付近に発生した渋滞を回避する際、予め設定されていた誘導経路にスムーズに復帰することが可能な経路を探索することができる。
【００６６】
次に、本発明の第２の実施形態を図面に基づいて説明する。図６は、第２の実施形態によるナビゲーション装置２００′の構成例を示すブロック図である。図６に示すように、ナビゲーション装置２００′は、その機能構成として、第１の実施形態で示した図１の要衝判定部２２５の代わりに、コスト判定部２２６を備えている。また、ナビゲーション装置２００′は、その機能構成として、図１の誘導経路探索部２１８、仮経由地設定部２１９、誘導経路メモリ２２０、誘導経路案内部２２２、渋滞情報取得部２２３および渋滞判定部２２４の代わりに、誘導経路探索部２１８′、仮経由地設定部２１９′、誘導経路メモリ２２０′、誘導経路案内部２２２′、渋滞情報取得部２２３′および渋滞判定部２２４′をそれぞれ備えている。なお、この図６において、図１に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００６７】
渋滞情報取得部２２３′は、主に高速道路上に設置された電波ビーコン送受信機との間で電波を介して双方向通信を行うとともに、主に一般道路上に設置された光ビーコン送受信機との間で光を介して双方向通信を行うことにより、道路交通情報センタ（図示せず）からＶＩＣＳ情報（渋滞情報や規制情報といった道路交通情報）を取得する。そして、渋滞情報取得部２２３′は、取得したＶＩＣＳ情報に含まれている渋滞情報を誘導経路探索部２１８′、仮経由地設定部２１９′、渋滞判定部２２４′およびコスト判定部２２６に出力する。
【００６８】
渋滞判定部２２４′は、誘導経路メモリ２２０′に格納された誘導経路情報と渋滞情報取得部２２３′から出力された渋滞情報とに基づいて、車両の進行方向前方の誘導経路上に渋滞区間（渋滞、混雑の両方を含む）が存在するか否かを判定する。渋滞判定部２２４′は、渋滞区間が存在すると判定した場合、その旨を誘導経路探索部２１８′および仮経由地設定部２１９′に通知する。
【００６９】
誘導経路探索部２１８′は、車両位置検出部２１２により検出された自車位置情報と地図データ記憶部２１３に記憶されている地図データとに基づいて、目的地設定部２１６から出力された目的地情報により示される目的地までの誘導経路を探索する。また、誘導経路探索部２１８′は、仮経由地設定部２１９′から仮経由地情報が出力された場合、車両位置検出部２１２により検出された自車位置情報と地図データ記憶部２１３に記憶されている地図データとに基づいて、仮経由地情報により示される仮経由地を経由して目的地に至る第２の誘導経路を探索する。なお、誘導経路または第２の誘導経路の探索において、渋滞区間のリンクコストの設定の仕方は第１の実施形態と同じである。
【００７０】
また、誘導経路探索部２１８′は、誘導経路上に渋滞区間が存在する旨の通知を渋滞判定部２２４′から受けた場合、渋滞区間を通らずに、自車位置から目的地に至る第３の誘導経路を探索する。例えば、誘導経路探索部２１８′は、渋滞区間全域のリンクコストを無限大（通行不可）に変更して、第３の誘導経路の探索を行う。なお、誘導経路探索部２１８′は、本発明の第１の誘導経路探索部、第２の誘導経路探索部および第３の誘導経路探索部に対応する。
【００７１】
誘導経路メモリ２２０′は、誘導経路探索部２１８′により誘導経路が探索された場合、その探索された誘導経路のデータ（現在位置から目的地に至るまでの道路リンクの集合）を誘導経路情報として一時的に格納する。また、誘導経路メモリ２２０′は、誘導経路探索部２１８′により第２の誘導経路が探索された場合、その探索された第２の誘導経路のデータ（現在位置から目的地に至るまでの道路リンクの集合）を第２の誘導経路情報として一時的に格納する。
【００７２】
また、誘導経路メモリ２２０′は、誘導経路探索部２１８′により第３の誘導経路が探索された場合、その探索された第３の誘導経路のデータ（現在位置から目的地に至るまでの道路リンクの集合）を第３の誘導経路情報として一時的に格納する。図７（ｆ）は、本実施形態の第３の誘導経路情報の詳細を示す図である。図７（ｆ）に示すように、第３の誘導経路情報は、第３の誘導経路を構成する道路リンクを識別するための「道路リンクＩＤ」を項目情報として含む。なお、図７（ａ）、（ｃ）、（ｄ）に示す道路リンク情報、誘導経路情報および第２の誘導経路情報は、図２（ａ）、（ｃ）、（ｄ）に示す道路リンク情報、誘導経路情報および第２の誘導経路情報から項目情報「要衝種別」を除いたそれぞれの情報と同様である。図７（ｂ）、（ｅ）に示すノード情報および渋滞情報は、図２（ｂ）、（ｅ）に示すノード情報および渋滞情報と同様である。
【００７３】
コスト判定部２２６は、誘導経路メモリ２２０′に格納された誘導経路情報および第３の誘導経路情報と、地図データ記憶部２１３に記憶されている地図データと、渋滞情報取得部２２３′から出力された渋滞情報とに基づいて、誘導経路で目的地に至るまでのコスト（例えば、距離や時間）と第３の誘導経路で目的地に至るまでのコスト（例えば、距離や時間）とを比較し、第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きいか否かを判定する。コスト判定部２２６は、第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きいと判定した場合、その旨を仮経由地設定部２１９′に通知する。
【００７４】
仮経由地設定部２１９′は、第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きい旨の通知をコスト判定部２２６から受けた場合、渋滞情報取得部２２３′から出力された渋滞情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０′に格納された誘導経路情報とに基づいて、渋滞区間に存在する合流可能交差点を仮経由地として設定する。そして、仮経由地設定部２１９′は、設定した仮経由地を示す仮経由地情報を誘導経路探索部２１８′に出力する。
【００７５】
一方、コスト判定部２２６は、第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きくないと判定した場合、その旨を誘導経路案内部２２２′に通知する。この場合、誘導経路案内部２２２′は、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０′に格納された第３の誘導経路情報とに基づいて、第３の誘導経路の誘導経路案内を開始する。
【００７６】
このように、第２の実施形態では、第３の誘導経路でのコストが現在設定されている誘導経路でのコストより所定値以上大きい場合に仮経由地を設定して第２の誘導経路を探索するようにしている。これは、第３の誘導経路が相当遠回りの経路である場合に限って第２の誘導経路を探索するようにすることによって、渋滞を回避するための経路が遠回りの経路であるとユーザが感じる可能性の低いときまで、第２の誘導経路を不必要に探索することを防止するためである。
【００７７】
また、コスト判定部２２６は、誘導経路メモリ２２０′に格納された第２の誘導経路情報および第３の誘導経路情報と、地図データ記憶部２１３に記憶されている地図データと、渋滞情報取得部２２３′から出力された渋滞情報とに基づいて、第２の誘導経路で目的地に至るまでのコスト（例えば、距離や時間）と第３の誘導経路で目的地に至るまでのコスト（例えば、距離や時間）とを比較し、第２の誘導経路でのコストが第３の誘導経路でのコストより小さいか否かを判定する。コスト判定部２２６は、第２の誘導経路でのコストが第３の誘導経路でのコストより小さいと判定した場合、その旨を誘導経路案内部２２２′に通知する。この場合、誘導経路案内部２２２′は、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０′に格納された第２の誘導経路情報とに基づいて、第２の誘導経路の誘導経路案内を開始する。
【００７８】
一方、コスト判定部２２６は、第２の誘導経路でのコストが第３の誘導経路でのコストより小さくないと判定した場合、その旨を仮経由地設定部２１９′に通知する。この場合、仮経由地設定部２１９′は、既に仮経由地として設定した合流可能交差点から渋滞区間における渋滞終了地点までの間に存在する交差点のうち、当該既に仮経由地として設定した合流可能交差点から自車位置側に向かって１つ目の交差点を新たな仮経由地として再設定する。そして、誘導経路探索部２１８′は、仮経由地設定部２１９′により再設定された仮経由地を経由して目的地に至る第２の誘導経路を再探索する。
【００７９】
このように、第２の実施形態では、第２の誘導経路でのコストが第３の誘導経路でのコストより小さくない場合、新たな仮経由地を再設定し、その再設定した仮経由地を経由して目的地に至る第２の誘導経路を再探索するようにしている。これは、遠回りの経路である第３の誘導経路が探索されてしまったという問題を解消するために、渋滞の一部を回避する第２の誘導経路を探索したところ、第３の誘導経路よりかえってコストが大きい第２の誘導経路が探索されてしまったときにそのまま第２の誘導経路が経路案内に使用されてしまうことを防止するためである。
【００８０】
また、仮経由地設定部２１９′は、渋滞区間中に合流可能交差点がないと判定した場合、その旨を誘導経路案内部２２２′に通知する。この場合、誘導経路案内部２２２′は、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０′に格納された第３の誘導経路情報とに基づいて、第３の誘導経路の誘導経路案内を開始する。このようにしているのは、渋滞区間に仮経由地を設定できない状況では、渋滞を回避するための経路として、第３の誘導経路のコストよりも小さいコストの第２の誘導経路を探索することが困難となるためである。
【００８１】
次に、第２の実施形態による誘導経路探索処理の例について説明する。図８は、第２の実施形態による誘導経路探索処理の例を示す図である。図８は、自車両４００が目的地４１０へ向かって誘導経路４２０を走行している時に、誘導経路４２０上の一部に渋滞（渋滞区間４３０で特定される）が発生した様子を示している。この場合、誘導経路探索部２１８′は、渋滞区間が存在する旨の通知を渋滞判定部２２４′から受けて、渋滞区間４３０を通らずに、自車位置４００から目的地４１０に至る第３の誘導経路５００を探索する。
【００８２】
次に、コスト判定部２２６は、誘導経路４２０で目的地４１０に至るまでのコストと第３の誘導経路５００で目的地４１０に至るまでのコストとを比較し、第３の誘導経路５００でのコストが誘導経路４２０でのコストより所定値以上大きいか否かを判定する。ここでは、第３の誘導経路５００が誘導経路４２０より大きく遠回りするルートのため、第３の誘導経路５００でのコストが誘導経路４２０でのコストより所定値以上大きいと判定したものとする。
【００８３】
この場合、仮経由地設定部２１９′は、渋滞区間４３０に存在する交差点のうち、最も目的地４１０側にあり、かつ、誘導経路４２０に左折で進入した後にそのまま目的地４１０側に進行可能な合流可能交差点４５０を仮経由地として設定する。誘導経路探索部２１８′は、仮経由地（交差点４５０）を経由して目的地４１０に至る第２の誘導経路５１０を探索する。
【００８４】
次に、コスト判定部２２６は、第２の誘導経路５１０で目的地４１０に至るまでのコストと第３の誘導経路５００で目的地４１０に至るまでのコストとを比較し、第２の誘導経路５１０でのコストが第３の誘導経路５００でのコストより小さいか否かを判定する。図８の例では、第２の誘導経路５１０は第３の誘導経路５００とほぼ同じくらい遠回りしていて、しかも、第２の誘導経路５１０は最後に渋滞区間４３０の一部を通るため、第２の誘導経路５１０でのコストが第３の誘導経路５００でのコストより小さくないと判定したものとする。
【００８５】
この場合、経由地設定部２１９′は、既に仮経由地として設定した合流可能交差点４５０から渋滞区間における渋滞終了地点４７０までの間に存在する交差点の中に、既に仮経由地として設定した合流可能交差点４５０より自車位置４００側に他の合流可能交差点があるか否かについて判定する。そして、他の合流可能交差点がある場合は、その中で最も目的地４１０側に近い交差点を新たな仮経由地として設定する。図８の例では、経由地設定部２１９′は、既に仮経由地として設定した合流可能交差点４５０から自車位置４００側に向かって１つ目の合流可能交差点４６０を新たな仮経由地として再設定する。そして、誘導経路探索部２１８′は、自車位置４１０から新たな仮経由地（交差点４６０）を経由して目的地４１０に至る第２の誘導経路４９０を再探索する。
【００８６】
次に、コスト判定部２２６は、第２の誘導経路４９０で目的地４１０に至るまでのコストと第３の誘導経路５００で目的地４１０に至るまでのコストとを比較し、第２の誘導経路４９０でのコストが第３の誘導経路５００でのコストより小さいか否かを判定する。図８の例では、第２の誘導経路４９０は渋滞区間４３０の一部を通っているが、第２の誘導経路４９０の方が第３の誘導経路５００より遠回りの程度がかなり小さいため、第２の誘導経路４９０でのコストが第３の誘導経路５００でのコストより小さいと判定したものとする。この場合、誘導経路案内部２２２′は、誘導経路４２０に基づく誘導経路案内に替えて、第２の誘導経路４９０に基づく誘導経路案内を開始する。
【００８７】
次に、第２の実施形態におけるナビゲーション装置２００′の動作について説明する。図９は、自車両が目的地へ向かって誘導経路を走行している場合におけるナビゲーション装置２００′の動作例を示すフローチャートである。
【００８８】
まず、渋滞情報取得部２２３′は、道路交通情報センタ（図示せず）からＶＩＣＳ情報を取得する（ステップＳ３００）。そして、渋滞情報取得部２２３′は、取得したＶＩＣＳ情報に含まれている渋滞情報を誘導経路探索部２１８′、仮経由地設定部２１９′、渋滞判定部２２４′およびコスト判定部２２６に出力する。
【００８９】
次に、渋滞判定部２２４′は、誘導経路メモリ２２０′に格納された誘導経路情報と渋滞情報取得部２２３′から出力された渋滞情報とに基づいて、車両の進行方向前方の誘導経路上に渋滞区間が存在するか否かを判定する（ステップＳ３２０）。もし、誘導経路上に渋滞区間が存在しないと渋滞判定部２２４′にて判定した場合（ステップＳ３２０にてＮＯ）、ナビゲーション装置２００′は図９における処理を終了する。
【００９０】
一方、誘導経路上に渋滞区間が存在すると渋滞判定部２２４′にて判定した場合（ステップＳ３２０にてＹＥＳ）、渋滞判定部２２４′は、その旨を誘導経路探索部２１８′および仮経由地設定部２１９′に通知する。次に、誘導経路探索部２１８′は、誘導経路上に渋滞区間が存在する旨の通知を渋滞判定部２２４′から受けて、渋滞区間を通らずに、自車位置から目的地に至る第３の誘導経路を探索する（ステップＳ３４０）。
【００９１】
コスト判定部２２６は、誘導経路メモリ２２０′に格納された誘導経路情報および第３の誘導経路情報と地図データ記憶部２１３に記憶されている地図データと渋滞情報取得部２２３′から出力された渋滞情報とに基づいて、誘導経路で目的地に至るまでのコストと第３の誘導経路で目的地に至るまでのコストとを比較し、第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きいか否かを判定する（ステップＳ３６０）。第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きくないとコスト判定部２２６にて判定した場合（ステップＳ３６０にてＮＯ）、処理はステップＳ５００へ遷移する。
【００９２】
一方、第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きいとコスト判定部２２６にて判定した場合（ステップＳ３６０にてＹＥＳ）、コスト判定部２２６は、その旨を仮経由地設定部２１９′に通知する。次に、仮経由地設定部２１９′は、渋滞情報取得部２２３′から出力された渋滞情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０′に格納された誘導経路情報とに基づいて、渋滞区間に存在する交差点のうち、最も目的地側にある合流可能交差点を仮経由地として設定する（ステップＳ３８０）。そして、仮経由地設定部２１９′は、設定した仮経由地を示す仮経由地情報を誘導経路探索部２１８′に出力する。
【００９３】
次に、誘導経路探索部２１８′は、渋滞情報取得部２２３′から出力された渋滞情報と地図データ記憶部２１３に記憶されている地図データとに基づいて、渋滞区間におけるリンクコストを変更する（ステップＳ４００）。そして、誘導経路探索部２１８′は、車両位置検出部２１２により検出された自車位置情報と地図データ記憶部２１３に記憶されている地図データと仮経由地設定部２１９′から出力された仮経由地情報とに基づいて、自車位置から仮経由地を経由して目的地に至る第２の誘導経路を探索する（ステップＳ４２０）。
【００９４】
次に、コスト判定部２２６は、誘導経路メモリ２２０′に格納された第２の誘導経路情報および第３の誘導経路情報と、地図データ記憶部２１３に記憶されている地図データと、渋滞情報取得部２２３′から出力された渋滞情報とに基づいて、第２の誘導経路で目的地に至るまでのコストと第３の誘導経路で目的地に至るまでのコストとを比較し、第２の誘導経路でのコストが第３の誘導経路でのコストより小さいか否かを判定する（ステップＳ４４０）。もし、第２の誘導経路でのコストが第３の誘導経路でのコストより小さいとコスト判定部２２６にて判定した場合（ステップＳ４４０にてＹＥＳ）、コスト判定部２２６は、その旨を誘導経路案内部２２２′に通知する。この場合、誘導経路案内部２２２′は、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０′に格納された第２の誘導経路情報とに基づいて、第２の誘導経路の誘導経路案内を開始する（ステップＳ４６０）。ステップＳ４６０の処理が完了することによって、ナビゲーション装置２００′は、図９における処理を終了する。
【００９５】
一方、第２の誘導経路でのコストが第３の誘導経路でのコストより小さくないとコスト判定部２２６にて判定した場合（ステップＳ４４０にてＮＯ）、コスト判定部２２６は、その旨を仮経由地設定部２１９′に通知する。次に、経由地設定部２１９′は、既に仮経由地として設定した交差点を除いて、他の合流可能交差点があるか否かについて判定する（ステップＳ４８０）。もし、他の合流交差点がないと仮経由地設定部２１９′にて判定した場合（ステップＳ４８０にてＮＯ）、仮経由地設定部２１９′は、その旨を誘導経路案内部２２２′に通知する。この場合、誘導経路案内部２２２′は、車両位置検出部２１２により検出された自車位置情報と、地図データ記憶部２１３に記憶されている地図データと、誘導経路メモリ２２０に格納された第３の誘導経路情報とに基づいて、第３の誘導経路情報の誘導経路案内を開始する（ステップＳ５００）。ステップＳ５００の処理が完了することによって、ナビゲーション装置２００′は、図９における処理を終了する。
【００９６】
一方、他の合流交差点があると仮経由地設定部２１９′にて判定した場合（ステップＳ４８０にてＹＥＳ）、仮経由地設定部２１９′は、目的地側に最も近い他の合流可能交差点を新たな仮経由地として再設定する（ステップＳ５２０）。そして、仮経由地設定部２１９′は、再設定した仮経由地を示す第２の仮経由地情報を誘導経路探索部２１８′に出力する。
【００９７】
次に、誘導経路探索部２１８′は、渋滞情報取得部２２３′から出力された渋滞情報と地図データ記憶部２１３に記憶されている地図データとに基づいて、渋滞区間におけるリンクコストを変更する（ステップＳ５４０）。そして、誘導経路探索部２１８′は、渋滞情報取得部２２３′から出力された渋滞情報と地図データ記憶部２１３に記憶されている地図データとに基づいて、自車位置から仮経由地設定部２１９′により再設定された仮経由地を経由して目的地に至る第２の誘導経路を再探索する（ステップＳ５６０）。その後、処理はステップＳ４４０に遷移する。
【００９８】
以上詳しく説明したように、第２の実施形態では、渋滞区間を通らずに、自車位置から目的地に至る第３の誘導経路でのコストが現在設定されている誘導経路でのコストより所定値以上大きい場合に仮経由地を設定するようにしている。このように構成した第２の実施形態によれば、相当遠回りの経路が探索された場合に限って第２の誘導経路が探索されることとなるので、渋滞を回避するための経路が遠回りの経路であるとユーザが感じる可能性の低いときまで、第２の誘導経路を不必要に探索することを防止することができる。
【００９９】
また、第２の実施形態では、第２の誘導経路でのコストが第３の誘導経路でのコストより小さくない場合、新たな仮経由地を再設定し、その再設定した仮経由地を経由して目的地に至る第２の誘導経路を再探索するようにしている。このように構成した第２の実施形態によれば、遠回りの経路である第３の誘導経路が探索されてしまうという問題を解消するために、第２の誘導経路を探索したところ、第３の誘導経路よりかえってコストが大きい第２の誘導経路が探索されたときにそのまま第２の誘導経路が経路案内に使用されてしまうことを防止することができる。
【０１００】
なお、上記第１および第２の実施形態では、渋滞区間に存在するいずれかの交差点を仮経由地として設定する例について説明したが、本発明はこれに限定されない。例えば、誘導経路上にあり渋滞区間の先頭から目的地側に数えて所定数以内の交差点を仮経由地として設定するようにしても良い。このようにすれば、誘導経路上に渋滞が発生した場合、なるべく遠回りせず、かつ、渋滞を完全に回避することが可能な経路を探索することができる。ただし、所定数を多くしすぎると、設定される仮経由地が渋滞区間から離れた地点となる可能性が生じ、渋滞区間近辺でレベル０の詳細な地図データを使えなくなるので、所定数は多くしすぎないようにする。好ましくは、所定数は１にする。
【０１０１】
また、上記第１および第２の実施形態では、誘導経路に左折で進入した後にそのまま目的地側に進行可能な交差点を仮経由地として設定する例について説明したが、本発明はこれに限定されない。例えば、誘導経路に左折で進入することは条件とせず、渋滞区間中の交差点を仮経由地として設定するようにしても良い。ただし、誘導経路に左折で進入した後にそのまま目的地側に進行可能な交差点を仮経由地として設定する方が、渋滞を回避する際、予め設定されていた誘導経路にスムーズに復帰することができる点で好ましい。
【０１０２】
また、図９のフローチャートにおいて、第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きくないとコスト判定部２２６にて判定した場合（ステップＳ３６０にてＮＯ）、コスト判定部２２６は、第３の誘導経路でのコストが誘導経路でのコストより小さいか否かについて判定するようにしても良い。もし、第３の誘導経路でのコストが誘導経路でのコストより小さいと判定した場合、誘導経路案内部２２２′は、第３の誘導経路の誘導経路案内を開始する。一方、第３の誘導経路でのコストが誘導経路でのコストより小さくないと判定した場合、ナビゲーション装置２００′は、図９における処理を終了する（すなわち、現在の誘導経路の誘導経路案内を続行する）。このような判定処理を追加することによって、経路案内中の誘導経路よりかえってコストが大きい第３の誘導経路が探索されてしまったときに、第３の誘導経路でのコストが誘導経路でのコストより所定値以上大きくないという理由だけで、そのまま第３の誘導経路が経路案内に使用されてしまうことを防止することができる。
【０１０３】
また、上記第１および第２の実施形態では、ノードに進入する道路リンクの進入方向、当該ノードから脱出する道路リンクの脱出方向がノード情報の接続道路情報に設定されている例について説明したが、本発明はこれに限定されない。例えば、ノード情報に交通規制情報を追加して、そのノードに接続されている道路リンクに存在する一方通行や右折禁止、Ｕターン禁止等の交通規制を設定するようにしても良い。この場合、仮経由地設定部２１９（２１９′）は、ノード情報の接続道路情報ではなく、ノード情報の交通規制情報を使用して合流可能交差点を求め、その求めた合流可能交差点を仮経由地として設定する。
【０１０４】
その他、上記第１および第２の実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその精神、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【０１０５】
２００，２００′  ナビゲーション装置
２１２  車両位置検出部
２１３  地図データ記憶部
２１８，２１８′  誘導経路探索部
２１９，２１９′  仮経由地設定部
２２３，２２３′  渋滞情報取得部
２２４，２２４′  渋滞判定部
２２５  要衝判定部
２２６  コスト判定部
【図１】
2011027610.tif 000003
【図２】
2011027610.tif 000004
【図３】
2011027610.tif 000005
【図４】
2011027610.tif 000006
【図５】
2011027610.tif 000007
【図６】
2011027610.tif 000008
【図７】
2011027610.tif 000009
【図８】
2011027610.tif 000010
【図９】
2011027610.tif 000011
【図１０】
2011027610.tif 000012
【図１１】
2011027610.tif 000013
【手続補正書】
【提出日】平成21年7月29日(2009.7.29)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2011027610.tif 000014
【図２】
2011027610.tif 000015
【図３】
2011027610.tif 000016
【図４】
2011027610.tif 000017
【図５】
2011027610.tif 000018
【図６】
2011027610.tif 000019
【図７】
2011027610.tif 000020
【図８】
2011027610.tif 000021
【図９】
2011027610.tif 000022
【図１０】
2011027610.tif 000023
【図１１】
2011027610.tif 000024