(57)【特許請求の範囲】
【請求項１】
要因毎、ノード毎、および、当該ノードに対するすべての進入リンクおよび退出リンクの組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度が含まれた渋滞予測データを取得するための取得手段（１５）と、  前記取得手段（１５）が取得した前記渋滞予測データに基づいて、複数のリンクの渋滞度を予測する予測手段（１７）と、を備え、  前記予測手段（１７）は、渋滞度を予測するリンクの対象範囲である渋滞予測範囲を限定する範囲限定手段（１０５）と、  第１のリンクの第１の時点の実際の渋滞度を外部から取得し、前記第１の時点に適合する要因、前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから第１のノードを経て前記渋滞予測範囲中の第２のリンクに進入する第２の時点における、前記第２のリンクの予測渋滞度を取得する予測渋滞度取得手段（１２０〜１４５）と、を有し、 前記予測渋滞度取得手段（１２０〜１４５）は更に、 前記第２の時点に適合する要因、前記第２のリンクに該当する進入リンク、および、取得した前記第２のリンクの前記第２の時点における予測渋滞度を、前記渋滞予測データに当てはめることで、前記第２のリンクから第２のノードを経て前記渋滞予測範囲中の第３のリンクに進入する第３の時点における、前記第３のリンクの第１の予測渋滞度を取得し、  また、前記第２のノードに第４のリンクが接続しているとき、前記第３の時点から前記第４のリンクの通過時間だけ遡った第４の時点に適合する要因、前記第４のリンクに該当する進入リンク、および、前記第４のリンクの所定の渋滞度を、前記渋滞予測データに当てはめることで、前記第４のリンクから前記第２のノードを経て前記第３のリンクに進入する前記第３の時点における、前記第３のリンクの第２の予測渋滞度を取得し、  前記第３のリンクの前記第１の予測渋滞度と、前記第３のリンクの前記第２の予測渋滞度のうち、渋滞度の高い方を、前記第３のリンクの予測渋滞度とすることを特徴とする渋滞予測装置。
【請求項２】
前記予測渋滞度取得手段（１２０〜１４５）は更に、  前記第１の時点に適合する要因、前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから前記第１のノードを経て前記渋滞予測範囲中のリンクＰ（Ｌ５）に進入する前記第２の時点における、前記リンクＰの予測渋滞度を取得し、  また、前記第２の時点に適合する要因、前記リンクＰに該当する進入リンク、および、取得した前記リンクＰの前記第２の時点における予測渋滞度を、前記渋滞予測データに当てはめることで、前記リンクＰからノードＡ（Ｎ３）を経て前記渋滞予測範囲中のリンクＱ（Ｌ６）に進入する時点Ｖ（Ｔ１＋Ｔ２＋Ｔ６）における、前記リンクＱの第１の予測渋滞度を取得し、  また、前記ノードＡに前記渋滞予測範囲中のリンクＲ（Ｌ３）が接続しているとき、前記時点Ｖとは異なる時点Ｗ（Ｔ１＋Ｔ２＋Ｔ３）に適合する要因、前記リンクＲに該当する進入リンク、および、前記時点Ｗにおける前記リンクＲの渋滞度を、前記渋滞予測データに当てはめることで、前記リンクＲから前記ノードＡを経て前記リンクＱに進入する時点Ｘ（Ｔ１＋Ｔ２＋Ｔ３＋Ｔ５）における、前記リンクＱの第２の予測渋滞度を取得し、  前記リンクＱの前記第１の予測渋滞度と、前記リンクＱの前記第２の予測渋滞度のうち、渋滞度の高い方を、前記リンクＱの予測渋滞度とすることを特徴とする請求項１に記載の渋滞予測装置。
【請求項３】
要因毎、ノード毎、および、当該ノードに対するすべての進入リンクおよび退出リンクの組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度が含まれた渋滞予測データを取得するための取得手段（１５）と、  前記取得手段（１５）が取得した前記渋滞予測データに基づいて、複数のリンクの渋滞度を予測する予測手段（１７）と、を備え、  前記予測手段（１７）は、渋滞度を予測するリンクの対象範囲である渋滞予測範囲を限定する範囲限定手段（１０５）と、  第１のリンクの第１の時点の実際の渋滞度を外部から取得し、前記第１の時点に適合する要因、前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから第１のノードを経て前記渋滞予測範囲中の第２のリンクに進入する第２の時点における、前記第２のリンクの予測渋滞度を取得する予測渋滞度取得手段（１２０〜１４５）と、を有し、 前記予測渋滞度取得手段（１２０〜１４５）は更に、 前記第１の時点に適合する要因、前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから前記第１のノードを経て前記渋滞予測範囲中のリンクＰ（Ｌ５）に進入する前記第２の時点における、前記リンクＰの予測渋滞度を取得し、 また、前記第２の時点に適合する要因、前記リンクＰに該当する進入リンク、および、取得した前記リンクＰの前記第２の時点における予測渋滞度を、前記渋滞予測データに当てはめることで、前記リンクＰからノードＡ（Ｎ３）を経て前記渋滞予測範囲中のリンクＱ（Ｌ６）に進入する時点Ｖ（Ｔ１＋Ｔ２＋Ｔ６）における、前記リンクＱの第１の予測渋滞度を取得し、 また、前記ノードＡに前記渋滞予測範囲中のリンクＲ（Ｌ３）が接続しているとき、前記時点Ｖとは異なる時点Ｗ（Ｔ１＋Ｔ２＋Ｔ３）に適合する要因、前記リンクＲに該当する進入リンク、および、前記時点Ｗにおける前記リンクＲの渋滞度を、前記渋滞予測データに当てはめることで、前記リンクＲから前記ノードＡを経て前記リンクＱに進入する時点Ｘ（Ｔ１＋Ｔ２＋Ｔ３＋Ｔ５）における、前記リンクＱの第２の予測渋滞度を取得し、 前記リンクＱの前記第１の予測渋滞度と、前記リンクＱの前記第２の予測渋滞度のうち、渋滞度の高い方を、前記リンクＱの予測渋滞度とすることを特徴とすることを特徴とする渋滞予測装置。
【請求項４】
前記予測渋滞度取得手段（１２０〜１４５）は更に、  前記リンクＱの前記第１の予測渋滞度と、前記リンクＱの前記第２の予測渋滞度のうち、渋滞度の高い方を、前記リンクＱの予測渋滞度とすると共に、前記時点Ｖおよび前記時点Ｘのうち早い方を前記リンクＱへの進入時刻とし、  また、前記リンクＱへの進入時刻に適合する要因、前記リンクＱに該当する進入リンク、および、取得した前記リンクＱの当該進入時刻の予測渋滞度を、前記渋滞予測データに当てはめることで、前記リンクＱからノードＢを経て前記渋滞予測範囲中のリンクＳに進入する時点における、前記リンクＳの予測渋滞度を取得することを特徴とする請求項２または３に記載の渋滞予測装置。
【請求項５】
要因毎、ノード毎、および、当該ノードに対するすべての進入リンクおよび退出リンクの組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度が含まれた渋滞予測データを取得するための取得手段（１５）と、  前記取得手段（１５）が取得した前記渋滞予測データに基づいて、複数のリンクの渋滞度を予測する予測手段（１７）と、を備え、  前記予測手段（１７）は、渋滞度を予測するリンクの対象範囲である渋滞予測範囲を限定する範囲限定手段（１０５）と、  第１のリンクの第１の時点の実際の渋滞度を外部から取得し、前記第１の時点に適合する要因、前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから第１のノードを経て前記渋滞予測範囲中の第２のリンクに進入する第２の時点における、前記第２のリンクの予測渋滞度を取得する予測渋滞度取得手段（１２０〜１４５）と、を有し、 前記取得手段（１５）が取得する渋滞予測データは、階層が上位になるほどリンクおよびノードが間引かれる複数階層構造となっており、要因毎、階層毎、ノード毎、および、当該ノードに対するすべての進入リンクおよび退出リンクの組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度が含まれており、 前記予測渋滞度取得手段（１２０〜１４５）は、前記第１の時点に適合する要因、前記第１のリンクおよび前記第２のリンクの両方が含まれている階層のうち最も高い階層、前記前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから第１のノードを経て前記渋滞予測範囲中の第２のリンクに進入する第２の時点における、前記第２のリンクの予測渋滞度を取得することを特徴とする渋滞予測装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、渋滞予測装置および渋滞予測データに関するものである。
【背景技術】
【０００２】
従来、道路の渋滞度（混雑度合い）を予測する技術が、特許文献１、２に記載されている。特許文献１では、過去の交通情報を統計的に処理することによって作成された時刻毎の各道路の渋滞予測データをあらかじめ記憶しておき、この渋滞予測情報に基づいて、現在位置より離れた地点における未来の渋滞度を予測している。
【０００３】
また、特許文献２では、あるリンクに一定の交通量を設定し、道路の分岐部でその交通量を分配し、リンクで交通量を一部消滅させながらシミュレート走行させることにより、各リンクにおける通過交通量を算出するようになっている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−２３２７２７号公報
【特許文献２】特開２００２−０４９９８４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１の技術では、図１１に示すように、特定の年日時に、あるリンクが統計的に空いているといった、対象のリンクのみに着眼した予測しかできず、近隣のリンクで現に発生している一時的、突発的な交通状況を考慮した渋滞度の予測がされていない。そのため、当該リンクに接続する他のリンクの近辺で特別なイベントが行われるなどの理由によって、多くの想定数以上の車両が当該リンクに流入すると、当該リンクが統計情報の予測を超えて混雑してしまう場合がある。つまり、特許文献１の手法では、現に発生している一時的、突発的な交通状況を考慮した渋滞度の予測がされていない。
【０００６】
また、特許文献２の技術では、現に発生している一時的、突発的な交通量を考慮しているものの、発明者の検討によれば、交通量と渋滞度は必ずしも一致しないことに起因する問題がある。同じ交通量でも、道路の勾配や信号機といった外的要因により、道路が渋滞したりしなかったりすることがある。例えば、図１２のように、単位時間当たりの交通量は一定でも、ある閾値以上の交通量の場合、上り坂や信号機といった条件により渋滞する。したがって、通過交通量を用いて正確に渋滞予測をするためには、勾配や信号機といった情報を、外部パラメータを過不足なく用いて演算する必要があり、推測値の確からしさが低く、計算量も非常に大きくなる。
【０００７】
本発明は上記点に鑑み、リンクの渋滞度を予測する渋滞予測装置において、現に発生している一時的、突発的な交通状況を反映できると共に、交通量以外の影響も容易に渋滞度に反映できるような技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】  上記目的を達成するための請求項１、３、５に記載の発明は、要因毎、ノード毎、および、当該ノードに対するすべての進入リンクおよび退出リンクの組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度が含まれた渋滞予測データを取得するための取得手段（１５）と、前記取得手段（１５）が取得した前記渋滞予測データに基づいて、複数のリンクの渋滞度を予測する予測手段（１７）と、を備え、前記予測手段（１７）は、渋滞度を予測するリンクの対象範囲である渋滞予測範囲を限定する範囲限定手段（１０５）と、第１のリンクの第１の時点の実際の渋滞度を外部から取得し、前記第１の時点に適合する要因、前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから第１のノードを経て前記渋滞予測範囲中の第２のリンクに進入する第２の時点における、前記第２のリンクの予測渋滞度を取得する予測渋滞度取得手段（１２０〜１４５）と、を有することを特徴とする渋滞予測装置である。【０００９】
このように、渋滞予測データとして、要因毎、ノード毎、および、当該ノードに対するすべての進入リンクおよび退出リンクの組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度が含まれた渋滞予測データを用いることで、上記目的を達成することができる。
【００１０】
具体的には、第１のリンクの第１の時点の実際の渋滞度を外部から取得し、第１の時点に適合する要因、第１のリンクに該当する進入リンク、および、取得した第１のリンクの第１の時点の実際の渋滞度を、渋滞予測データに当てはめる。
【００１１】
すると、上記のような渋滞予測データの構造上、第１のリンク（進入リンク）から第１のノードを経て進入できる第２のリンク（退出リンク）を特定でき、さらに、当該第１のリンクの種々の渋滞度の結果生じる当該第２のリンクの種々の予測渋滞度が特定できで、さらに、第１のリンクの第１の時点の実際の渋滞度の結果生じる第２の時点の第２のリンクの予測渋滞度を取得することができる。
【００１２】
このような手法は、第１のリンクの第１の時点の実際の渋滞度を外部から取得し、取得した渋滞度に基づいて第２のリンクの予測渋滞を算出している点で、現に発生している一時的、突発的な交通状況を反映できる。しかも、従来のような交通量のシミュレーションではなく、渋滞予測データにおける第１のリンクの渋滞度と第２のリンクの渋滞度の因果関係を用いて、交通量の計算を経ることなく、直接的に第２のリンクの渋滞度を算出している。したがって、交通量以外の影響も容易に渋滞度に反映させることができる。
【００１３】
このようになっていることで、図１３（ａ）に示すように、太線で示す経路を算出して走行した場合に、図１３（ｂ）に示すように当該経路で渋滞に遭ってしまうといった事態が発生する可能性が低くなる。
【００１４】  また、請求項１に記載の発明は、前記予測渋滞度取得手段（１２０〜１４５）は更に、前記第２の時点に適合する要因、前記第２のリンクに該当する進入リンク、および、取得した前記第２のリンクの前記第２の時点における予測渋滞度を、前記渋滞予測データに当てはめることで、前記第２のリンクから第２のノードを経て前記渋滞予測範囲中の第３のリンクに進入する第３の時点における、前記第３のリンクの第１の予測渋滞度を取得し、また、前記第２のノードに第４のリンクが接続しているとき、前記第３の時点から前記第４のリンクの通過時間だけ遡った第４の時点に適合する要因、前記第４のリンクに該当する進入リンク、および、前記第４のリンクの所定の渋滞度を、前記渋滞予測データに当てはめることで、前記第４のリンクから前記第２のノードを経て前記第３のリンクに進入する前記第３の時点における、前記第３のリンクの第２の予測渋滞度を取得し、前記第３のリンクの前記第１の予測渋滞度と、前記第３のリンクの前記第２の予測渋滞度のうち、渋滞度の高い方を、前記第３のリンクの予測渋滞度とすることを特徴とする。【００１５】
このようにすることで、第２のリンクと第４のリンクが同じ第２のノードを経て第３のリンクに接続している場合、第２のリンクの渋滞度の結果生じる第３のリンクの渋滞度と、第４のリンクの渋滞度の結果生じる第３のリンクの渋滞度とが異なる場合、交通流のように足し合わせるのではなく、渋滞度の高い方を採用する。これは、第２のリンクの渋滞度の結果生じる第３のリンクの渋滞度予測データは、他のリンクから第３のリンクへの流入等の影響も反映されたデータとして作成されており、第４のリンクの渋滞度の結果生じる第３のリンクの渋滞度予測データは、他のリンクから第３のリンクへの流入等の影響も反映されたデータとして作成されているからである。
【００１６】  また、請求項２、３に記載の発明は、前記予測渋滞度取得手段（１２０〜１４５）は更に、前記第１の時点に適合する要因、前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから前記第１のノードを経て前記渋滞予測範囲中のリンクＰに進入する前記第２の時点における、前記リンクＰの予測渋滞度を取得し、また、前記第２の時点に適合する要因、前記リンクＰに該当する進入リンク、および、取得した前記リンクＰの前記第２の時点における予測渋滞度を、前記渋滞予測データに当てはめることで、前記リンクＰからノードＡを経て前記渋滞予測範囲中のリンクＱに進入する時点Ｖにおける、前記リンクＱの第１の予測渋滞度を取得し、また、前記ノードＡに前記渋滞予測範囲中のリンクＲが接続しているとき、前記時点Ｖとは異なる時点Ｗに適合する要因、前記リンクＲに該当する進入リンク、および、前記時点Ｗにおける前記リンクＲの渋滞度を、前記渋滞予測データに当てはめることで、前記リンクＲから前記ノードＡを経て前記リンクＱに進入する時点Ｘにおける、前記リンクＱの第２の予測渋滞度を取得し、前記リンクＱの前記第１の予測渋滞度と、前記リンクＱの前記第２の予測渋滞度のうち、渋滞度の高い方を、前記リンクＱの予測渋滞度とすることを特徴とする。【００１７】
このようにすることで、第５のリンクと第７のリンクが同じ第３のノードを経て第６のリンクに接続している場合、第５のリンクの渋滞度の結果生じる第６のリンクの渋滞度と、第７のリンクの渋滞度の結果生じる第６のリンクの渋滞度とが異なる場合、交通流のように足し合わせるのではなく、渋滞度の高い方を採用する。これは、第５のリンクの渋滞度の結果生じる第７のリンクの渋滞度予測データは、他のリンクから第６のリンクへの流入等の影響も反映されたデータとして作成されており、第７のリンクの渋滞度の結果生じる第６のリンクの渋滞度予測データは、他のリンクから第６のリンクへの流入等の影響も反映されたデータとして作成されているからである。
【００１８】  また、請求項４に記載の発明は、請求項２または３に記載の渋滞予測装置において、前記予測渋滞度取得手段（１２０〜１４５）は更に、前記リンクＱの前記第１の予測渋滞度と、前記リンクＱの前記第２の予測渋滞度のうち、渋滞度の高い方を、前記リンクＱの予測渋滞度とすると共に、前記時点Ｖおよび前記時点Ｗのうち早い方を前記リンクＱへの進入時刻とし、また、前記リンクＱへの進入時刻に適合する要因、前記リンクＱに該当する進入リンク、および、取得した前記リンクＱの当該進入時刻の予測渋滞度を、前記渋滞予測データに当てはめることで、前記リンクＱからノードＢを経て前記渋滞予測範囲中のリンクＳに進入する時点における、前記リンクＳの予測渋滞度を取得することを特徴とする。このようにすることで、リンクへの進入時刻を統一して、ノードの予測渋滞度の計算を進めることができる。【００１９】  また、請求項５に記載の発明は、前記取得手段（１５）が取得する渋滞予測データは、階層が上位になるほどリンクおよびノードが間引かれる複数階層構造となっており、要因毎、階層毎、ノード毎、および、当該ノードに対するすべての進入リンクおよび退出リンクの組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度が含まれており、前記予測渋滞度取得手段（１２０〜１４５）は、前記第１の時点に適合する要因、前記第１のリンクおよび前記第２のリンクの両方が含まれている階層のうち最も高い階層、前記前記第１のリンクに該当する進入リンク、および、取得した前記第１のリンクの前記第１の時点の実際の渋滞度を、前記渋滞予測データに当てはめることで、前記第１のリンクから第１のノードを経て前記渋滞予測範囲中の第２のリンクに進入する第２の時点における、前記第２のリンクの予測渋滞度を取得すると、を有することを特徴とする。【００２０】
このように、渋滞予測データを階層に分けて使用することで、予測渋滞度の算出の処理負荷を低減することができる。
【００２２】
なお、上記および特許請求の範囲における括弧内の符号は、特許請求の範囲に記載された用語と後述の実施形態に記載される当該用語を例示する具体物等との対応関係を示すものである。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施形態に係るナビゲーション装置１の構成図である。
【図２】渋滞予測データの構成例を示す図である。
【図３】渋滞予測処理のフローチャートである。
【図４】出発地Ｐｏから目的地ＰｄまでのリンクＬ１〜Ｌ６の図である。
【図５】時刻Ｔ１、ノードＮ１における進入リンクＬ１と退出リンクＬ２、Ｌ５の渋滞度の関係を表す表である。
【図６】時刻Ｔ１＋Ｔ２、ノードＮ２における進入リンクＬ２と退出リンクＬ３の渋滞度の関係を表す表である。
【図７】ノードＮ２における進入リンクＬ４と退出リンクＬ３の渋滞度の関係を表す表である。
【図８】時刻Ｔ１＋Ｔ２、ノードＮ３における進入リンクＬ５と退出リンクＬ６の渋滞度の関係を表す表である。
【図９】時刻Ｔ１＋Ｔ２＋Ｔ３、ノードＮ３における進入リンクＬ３と退出リンクＬ６の渋滞度の関係を表す表である。
【図１０】算出された最適な経路を表す図である。
【図１１】特許文献１で使用される渋滞予測データを示す図である。
【図１２】交通量と混雑度の違いを例示する図である。
【図１３】算出した経路を走行して渋滞に遭う例を示す図である。
【発明を実施するための形態】
【００２４】
以下、本発明の一実施形態について説明する。図１に、本実施形態に係るナビゲーション装置１（渋滞予測装置の一例に相当する）の一例を示す。このナビゲーション装置は、車両に搭載されていてもよいし、ユーザが車外に持ち運べるようになっていてもよい。
【００２５】
このナビゲーション装置１は、位置検出器１１、画像表示装置１２、操作部１３、スピーカ１４、通信部１５、制御回路１７を備えている。位置検出器１１は、ＧＰＳ受信機、車速センサ、加速度センサ、ジャイロセンサ等、車両の現在位置を特定するための信号を制御回路１７に出力するセンサである。画像表示装置１２は、制御回路１７の制御に従って文字や画像をユーザに表示する液晶ディスプレイ等の装置である。操作部１３は、ユーザの操作を受け付け、受け付けた操作に応じた信号を制御回路１７に出力する装置である。
【００２６】
通信部１５は、外部の渋滞予測データ配信サーバと無線通信し、渋滞予測データ配信サーバから渋滞予測データを受信するようになっている。受信した渋滞予測データは、ナビゲーション装置１の記憶媒体に記録される。この渋滞予測データの詳細については後述する。また通信部１５は、車両の外部の交通情報配信装置（例えばＶＩＣＳ送信局、ＶＩＣＳビーコン、プローブ車両情報配信サーバ）から、現在の各リンクの混雑度合いを表す渋滞度を含む交通情報データを、受信するようになっている。
【００２７】
地図データ取得部１６は、制御回路１７の制御に従って地図データを取得して制御回路１７に出力する装置である。地図データの取得方法は、ナビゲーション装置１が有する記憶媒体（ＨＤＤ、フラッシュメモリ、ＤＶＤメディア等）から地図データを読み出す方法でもよいし、通信部１５を用いた無線通信によって車両１の外部の地図提供サーバから地図データをダウンロードする方法でもよい。
【００２８】
地図データ取得部１６が取得する地図データは、地図表示用の道路形状データ、目的地検索用の施設データ、および誘導経路計算用の道路ネットワークデータ等を含んでいる。道路ネットワークデータは、リンクとノードとの接続関係、リンクのコスト等の情報を含む。
【００２９】
また、本実施形態の道路ネットワークデータは、リンク構造の詳細度の異なる複数の階層を有する階層構造となっている。複数の階層のうち、最下位の階層のデータには、すべての道路についてのリンク、ノードのデータが含まれ、階層が上位になるほど、その階層のデータに含まれるリンクおよびノードのデータが間引かれる。例えば、道路ネットワークデータが上位層と下位層の２つの階層を有する場合、下位層のデータには、主要道路および非主要道路の両方の道路についてのリンク、ノードのデータが含まれ、上位層のデータには、主要道路と非主要道路のうち、主要道路のみを構成するリンク、ノードのデータしか含まれない。
【００３０】
制御回路１７は、ＣＰＵ、ＲＡＭ、ＲＯＭ、フラッシュメモリ等を備えた装置（例えばマイクロコントローラ）であって、ＲＯＭまたはフラッシュメモリに記録されたプログラムをＣＰＵが実行することで、各種処理を実現するようになっている。
【００３１】
制御回路１７がプログラムを実行することによって行う具体的な処理としては、現在位置特定処理、地図表示処理、誘導経路算出処理、経路案内処理等がある。現在位置特定処理は、位置検出器１１からの信号に基づいて、周知のマップマッチング等の技術を用いて車両の現在位置や向きを特定する処理である。
【００３２】
地図表示処理は、車両の現在位置の周辺等の特定の領域の地図を、画像表示装置１２に表示させる処理である。この際、地図表示のために用いる情報は、道路形状データから取得する。
【００３３】
誘導経路算出処理は、操作部１３からユーザによる目的地の入力を受け付け、現在位置から当該目的地までの最適な誘導経路を算出する処理である。
【００３４】
経路案内処理は、算出された誘導経路に沿った走行を案内する処理であり、誘導経路と自車位置との位置関係を逐次監視し、誘導経路上の右左折交差点等の案内ポイントの手前に自車両が到達したときに、右折、左折等を指示する案内音声をスピーカ１４に出力させ、当該案内ポイントの拡大図を画像表示装置１２に表示させることで、誘導経路に沿った車両の運転を案内する処理である。
【００３５】
以下、誘導経路算出処理の詳細について説明する。本実施形態では、誘導経路算出処理において、まず渋滞予測処理を実行することで各リンクの渋滞度を予測し、その渋滞度に応じたコストを各リンクに割り振った上で、道路ネットワークデータを用いたダイクストラ法等の方法で、最も総コストの低い経路を誘導経路として採用する。各リンクの渋滞度を予測するためのこの渋滞予測処理では、通信部１５から取得した渋滞予測データを使用する。図２に、この渋滞予測データの構成例を示す。
【００３６】
この図に示すように、渋滞予測データは、要因（時間、曜日等の時期に関する要因。以下同じ）毎、階層毎、当該階層に含まれるノード毎、および、当該ノードに対するすべての進入リンク（当該階層に含まれるものに限る）および退出リンク（当該階層に含まれるものに限る）の組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度を含んでいる。また、渋滞予測データは、要因毎、階層毎、ノード毎、および、当該ノードに対する進入リンク毎に、当該進入リンクの種々の渋滞度と、その渋滞度における当該進入リンクの通過時間が含まれている。
【００３７】
より具体的には、渋滞予測データは、それぞれが１つの要因に対応する要因レコードＲ１を要因の数だけ複数個有し、各要因レコードＲ１は、当該要因レコードＲ１に対応する要因を表す要因データ２１を有し、更に、それぞれが１つの階層に対応する階層レコードＲ２を階層の数だけ複数個有している。なお、階層とは、上述の道路ネットワークデータと同等の階層である。したがって、渋滞予測データも、階層が上位になるほどリンクおよびノードが間引かれる複数階層構造となっている。
【００３８】
また、各階層レコードＲ２は、当該階層レコードＲ２に対応するレイヤ番号のデータ２２を有し、更に、それぞれが１つのノード（ただし、道路ネットワークデータで当該階層レコードＲ２の階層に含まれるノードに限る）に対応するノードレコードＲ３を、当該階層レコードＲ２の階層に含まれるノードの数だけ複数個有している。
【００３９】
また、各ノードレコードＲ３は、当該ノードレコードＲ３に対応するノード番号のデータ２３を有し、更に、それぞれが１つの進入リンク（ただし、当該ノードレコードＲ３のノードに進入するリンクに限る）に対応する進入リンクレコードＲ４を、当該ノードレコードＲ３のノードに進入するリンクの数だけ１個または複数個有している。
【００４０】
また、各進入リンクレコードＲ４は、当該進入リンクレコードＲ４に対応する進入リンクのリンク番号のデータ２４を有し、更に、それぞれが１つの渋滞度に対応する渋滞度レコードＲ５を、渋滞度の数だけ複数個有している。渋滞度は、例えば、混雑の度合いが大きくなるほど大きくなる１から６までの数値（具体的には１：非常に空いている、２：空いている、３：軽混雑、４：重混雑、５：軽渋滞、６：重渋滞）で表現する。
【００４１】
また、各渋滞度レコードＲ５は、当該渋滞度レコードＲ５に対応する渋滞度を表すデータ２５と、当該渋滞度レコードＲ５を含む進入リンクレコードＲ４の進入リンクを当該渋滞度で走行するのに要する通過時間ｔのデータ２６とを有し、更に、それぞれが１つの退出リンク（ただし、当該渋滞度レコードＲ５を含むノードレコードＲ３のノードから退出するリンクに限る）に対応する退出リンクレコードＲ６を、当該渋滞度レコードＲ５を含むノードレコードＲ３のノードから退出するリンクの数だけ１個または複数個有している。
【００４２】
また、各退出リンクレコードＲ６は、当該退出リンクレコードＲ６に対応する退出リンクのリンク番号のデータ２７を有し、更に、当該退出リンクレコードＲ６を含む進入リンクレコードＲ４の進入リンクに進入したときの当該進入リンクの渋滞度が、当該退出リンクレコードＲ６を含む渋滞度レコードＲ５の渋滞度であることに起因して生じる結果として、当該進入リンクから当該退出リンクに進入したときに当該退出リンクにおいて発生すると予測される予測渋滞度を表すデータ２８と、を有している。
【００４３】
ある進入リンクに進入したときのその進入リンクの渋滞度と、その進入リンクからノードを経て退出リンクに入った時点のその退出リンクの予測渋滞度との関係は、実地調査等によって統計的にあらかじめ決めた上で、渋滞予測データが作成されて渋滞予測データ配信サーバに記憶される。
【００４４】
ここで、渋滞予測データの階層について説明する。渋滞予測データの階層は、道路ネットワークデータの階層と同様、複数の階層のうち、最下位の階層のデータには、すべての道路についてのリンク、ノードのデータが含まれ、階層が上位になるほど、その階層のデータに含まれるリンクおよびノードのデータが間引かれる。
【００４５】
例えば、道路ネットワークが４階層で、最も下位の階層０が全経路探索対象のリンクおよびノードを含み、階層１が主要地方道以上の格のリンクおよびそれらが交わるノードのみを含み、階層２が県道以上の格のリンクおよびそれらが交わるノードのみ含み、階層３が国道以上の格のリンクおよびそれらが交わるノードのみを含み、階層４が高速道路およびそれらが交わるノードのみを含むようになっている。
【００４６】
そして、ある階層の各階層レコードＲ２は、その階層に含まれるノードについてのみノードレコードＲ３を有し、その階層に含まれる進入リンクについてのみ進入リンクレコードＲ４を有し、その階層に含まれる退出リンクについてのみ退出リンクレコードＲ６を有するようになっている。
【００４７】
制御回路１７は、誘導経路算出処理において、上記目的地の入力を受け付けると、まず、現在位置から目的地までの探索経路範囲、および、各種探索条件を、周知の方法で決定する。続いて制御回路１７は、通信部１５を介して、上記交通情報配信装置から、現在（すなわち、経路探索時の時刻Ｔ１）の各リンクの渋滞度の情報を含む交通情報データに受信する。この現在の各リンクの渋滞度の情報は、渋滞予測の際に初期値として採用する。
【００４８】
続いて制御回路１７は、図３に示す渋滞予測処理の実行を開始し、ステップ１０５で、渋滞予測処理全体の演算時間を短縮するため、渋滞度を算出するリンクの対象範囲（以下、渋滞予測範囲という）を限定する。渋滞予測範囲の限定方法は、例えば、上述の探索経路範囲に含まれる全リンクであってもよいし、あるいは、渋滞予測を行わずに、現在位置から目的地までの誘導経路を、総コストが最も低いものから複数個（例えば６個）抽出し、抽出した経路とその周辺のリンクを渋滞予測範囲としてもよい。この場合、抽出した抽出経路の周辺のリンクとしては、例えば、抽出した経路で囲まれる範囲を、面積が１０％増大するように拡大し、その拡大によって新たに含まれる範囲内のリンクとしてもよい。
【００４９】
例えば、一例として、図４に示すように、出発地（現在位置）Ｐｏから目的地Ｐｄまでの間のリンクＬ２、Ｌ３、Ｌ５、Ｌ６が、渋滞予測範囲となったとする。なおリンクＬ１は、すでに車両がその端部Ｐｏにいるので、現在の渋滞度を採用すればよく渋滞度を予測する対象にならない。また、上記の抽出経路は、リンクＬ１、Ｌ２、Ｌ５、Ｌ６をこの順に進む経路と、リンクＬ１、Ｌ３、Ｌ６をこの順に進む経路であったとする。
【００５０】
この例では、算出されたリンクＬ２、Ｌ３、Ｌ５、Ｌ６は、すべて同じ最下位の階層のみに含まれるのリンクであるとするが、リンクＬ１〜Ｌ６のうち、上位の階層に含まれるリンクがあってもよい。なお、通信部１５を介して受信した現在時刻Ｔ１における各リンクＬ１〜Ｌ６の渋滞度は、リンクＬ１が渋滞度５、リンクＬ２〜Ｌ６が渋滞度２であったとする。
【００５１】
続いてステップ１１０では、渋滞度算出対象の階層を算出する。渋滞度算出対象の階層は、事前に渋滞度を考慮しない経路計算を行ったときに演算される階層と同じものを用いても良い。本例では、リンクＬ２、Ｌ３、Ｌ５、Ｌ６はすべて最下位の１階層データと仮定しているので、渋滞度算出対象の階層も最下位階層のみであり、渋滞予測データで使用する階層レコードＲ３は、最下位の階層の階層レコードＲ３のみである。
【００５２】
しかし、複数階層データである場合、事前の経路計算演算で、リンクＬ１、Ｌ６が第１階層、リンクＬ２、Ｌ３，Ｌ５が第２階層が用いられた場合、渋滞度算出においても、リンクＬ１、Ｌ６を第一階層、リンクＬ２、Ｌ３、Ｌ５を第２階層にて演算することになる。  続いてステップ１１５では、現在自車両が位置している自車位置ノードＰｏから、各リンクＬ１〜Ｌ６の渋滞度予測を開始する。続いてステップ１２０では、渋滞度算出対象リンク（渋滞予測範囲内のリンク）Ｌ２、Ｌ３、Ｌ５、Ｌ６の中で、渋滞度を算出していないリンクがあるか否かを判定する。
【００５３】
最初は渋滞度を算出していないリンクがあるので、「ある」と判定してステップ１２５に進み、渋滞度を算出する対象のリンクを決定する。決定順序は、基本的に自車両が現在いるリンクＬ１に近い順とする。したがって、まずは、自車位置ノードＰｏに接続するリンクＬ１（第１のリンク）から１つのノードＮ１（第１のノードの一例に相当する）を経て進入するリンクＬ２、Ｌ５のうち、リンクＬ２（第２のリンクの一例に相当する）を対象のリンクとする。
【００５４】
続いてステップ１３０では、対象リンクＬ２への自車両の到着時刻を推定する。リンクＬ１については、すでに自車両がその端部Ｐｏに到着しているので、推定した時刻は現在時刻Ｔ１（第１の時点の一例に相当する）に、リンクＬ１の通過時間Ｔ２を加えた時刻Ｔ１＋Ｔ２（第２の時点の一例に相当する）である。
【００５５】
ここで、通過時間Ｔ２は、渋滞予測データを用いて決定する。具体的には、現在時刻Ｔ１に適合する要因、現在車両がいるリンクＬ１に対応する階層（最下位の階層）、現在車両がいるリンクＬ１に該当する進入リンク、当該リンクＬ１から進入するノードＮ１、現在の当該リンクＬ１の渋滞度（本例では５）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まるため、当該渋滞度レコードＲ５に対応する通過時間ｔが１つ定まる。したがって、その通過時間ｔを通過時間Ｔ２として採用する。
【００５６】
続いてステップ１３５では、対象リンクＬ２の始点のノードＮ１から対象リンクＬ２に進入する外部リンクのうち、渋滞度が算出されていないリンクがあるか否か判定する。ここで、外部リンクとは、渋滞予測範囲に入っていないリンクをいう。この例では、対象リンクＬ２に進入する外部リンクはないので、「ない」と判定してステップ１４５に進む。
【００５７】
ステップ１４５では、対象リンクＬ２の予測渋滞度を算出する。具体的には、時刻Ｔ１に適合する要因、最下位の階層、リンクＬ１に該当する進入リンク、および、リンクＬ１の時刻Ｔ１における実際の渋滞度（本例では５）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まり、その渋滞度レコードＲ５に含まれるリンクＬ２の退出リンクレコードＲ６も１つ決まるため、当該退出リンクレコードＲ６に対応する予測渋滞度が１つ決まる。
【００５８】
図５に、渋滞予測データから、時刻Ｔ１、下位層、ノードＮ１における、進入リンクＬ１の各種渋滞度と当該渋滞度の結果生じる退出リンクＬ２、Ｌ５の渋滞度との対応関係を抽出した表を示す。
【００５９】
この表の通り、時刻Ｔ１に進入リンクＬ１の渋滞度が５の場合は、それの結果生じる退出リンクＬ２の予測渋滞度は６である。したがって、時刻Ｔ１＋Ｔ２におけるリンクＬ２の予測渋滞度が６に決まる。
【００６０】
このように、時刻Ｔ１＋Ｔ２におけるリンクＬ２の予測渋滞度が決まると、処理はステップ１２０に戻り、再度渋滞予測範囲のリンクＬ２、Ｌ３、Ｌ５、Ｌ６中で渋滞度を算出していないリンクがあると判定し、ステップ１２５でリンクＬ５を対象リンクとする。
【００６１】
そしてステップ１３０で、対象リンクＬ５への自車両の到着時刻を推定する。この到着時刻は、同じノードＮ１に接続するリンクＬ２と同様、現在時刻Ｔ１（第１の時点の一例に相当する）にリンクＬ１の通過時間Ｔ２を加えた時刻Ｔ１＋Ｔ２（第２の時点の一例に相当する）である。
【００６２】
続いてステップ１３５で、対象リンクＬ５の始点のノードＮ１から対象リンクＬ５に進入する外部リンクのうち、渋滞度が算出されていないリンクがないと判定してステップ１４５に進み、ステップ１４５では、対象リンクＬ５の予測渋滞度を算出する。具体的には、時刻Ｔ１に適合する要因、最下位の階層、リンクＬ１に該当する進入リンク、および、リンクＬ１の時刻Ｔ１における実際の渋滞度（本例では５）を、渋滞予測データに当てはめることで、図５に示す通り、予測渋滞度が１つ決まる。具体的には、図５に示す通り、時刻Ｔ１に進入リンクＬ１の渋滞度が５の場合は、それの結果生じる退出リンクＬ５の予測渋滞度は２である。したがって、時刻Ｔ１＋Ｔ２におけるリンクＬ５の予測渋滞度が２に決まる。
【００６３】
このように、時刻Ｔ１＋Ｔ２におけるリンクＬ５の予測渋滞度が決まると、処理はステップ１２０に戻り、再度渋滞予測範囲のリンクＬ２、Ｌ３、Ｌ５、Ｌ６中で渋滞度を算出していないリンクがあると判定し、ステップ１２５でリンクＬ３を対象リンクとする。
【００６４】
その後、処理はステップ１２０に戻り、再度渋滞予測範囲のリンクＬ２、Ｌ３、Ｌ５、Ｌ６中で渋滞度を算出していないリンクがあると判定し、ステップ１２５でリンクＬ３を対象リンクとする。
【００６５】
そしてステップ１３０で、対象リンクＬ３への自車両の到着時刻を推定する。この到着時刻は、リンクＬ２への到着時刻がＴ１＋Ｔ２（第２の時点の一例に相当する）に、リンクＬ３の通過時間Ｔ３を加えた時刻Ｔ１＋Ｔ２＋Ｔ３（第３の時点の一例に相当する）である。
【００６６】
ここで、通過時間Ｔ２は、渋滞予測データを用いて決定する。具体的には、ノードＮ２を介してリンクＬ３に進入するリンクＬ２の到着時刻Ｔ１＋Ｔ２に適合する要因、当該リンクＬ２に対応する階層（最下位の階層）、リンクＬ２に該当する進入リンク、当該リンクＬ２から進入するノードＮ２、現在の当該リンクＬ２の渋滞度（本例では６）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まるため、当該渋滞度レコードＲ５に対応する通過時間ｔが１つ定まる。したがって、その通過時間ｔを通過時間Ｔ３として採用する。
【００６７】
続いてステップ１３５では、対象リンクＬ３の始点のノードＮ２から対象リンクＬ３に進入する外部リンクのうち、渋滞度が算出されていないリンクがあるか否か判定する。ここでは、リンクＬ４（第４のリンクの一例に相当する）がその外部リンクに相当するので、「ある」と判定してステップ１４０に進む。
【００６８】
ステップ１４０では、外部リンクのうち１つ（ここではリンクＬ４）を抽出し、抽出したリンクＬ４の渋滞度を算出する。ここでは、直前のステップ１３０で算出した時刻Ｔ１＋Ｔ２＋Ｔ３におけるリンクＬ３の渋滞度を算出するために、リンクＬ４の渋滞度を算出したいので、時刻Ｔ１＋Ｔ２＋Ｔ３からリンクＬ４の通過時間Ｔ４だけ遡った時刻Ｔ１＋Ｔ２＋Ｔ３−Ｔ４（第４の時点の一例に相当する）におけるリンクＬ４の渋滞度を算出する。
【００６９】
ここで、使用する通過時間Ｔ４は、時刻Ｔ１＋Ｔ２＋Ｔ３に適合する要因、最下位の階層、ノードＮ２、進入リンクＬ４、および、通信部１５から受信した現在時刻Ｔ１におけるリンクＬ４の渋滞度「２」に該当する渋滞度、のレコードにおける通過時間を採用する。
【００７０】
また、時刻Ｔ１＋Ｔ２＋Ｔ３−Ｔ４におけるリンクＬ４の渋滞度を、通信部１５から受信した現在時刻Ｔ１におけるリンクＬ４の渋滞度「２」と同じであるとする。このようにするのは、リンクＬ４が予測範囲から外れたリンクであるため、流入交通を推定できないためである。仮に、リンクＬ４も予測範囲内であり、リンクＬ４のノードＮ２の反対側端に、予測範囲の他のリンクが続いていたなら、この他のリンクと同じ階層のリンクの時刻Ｔ１の渋滞度をもとに予測データを用いてこの他のリンクおよびリンクＬ４の予測渋滞度の演算も行う。
【００７１】
ステップ１４０の後、処理は再度ステップ１３５に戻り、対象リンクＬ３の始点のノードＮ２から対象リンクＬ３に進入する外部リンクのうち、渋滞度が算出されていないリンクがないと判定してステップ１４５に進む。
【００７２】
ステップ１４５では、対象リンクＬ３の予測渋滞度を算出する。ただし、対象リンクＬ３には、ノードＮ２を介してリンクＬ２からも上記外部リンクＬ４からも進入するようになっている。したがって、ここでは、リンクＬ２の渋滞度の結果生じる対象リンクＬ３の予測渋滞度を第１の予測渋滞度として算出し、リンクＬ４の渋滞度の結果生じる対象リンクＬ３の予測渋滞度を第２の予測渋滞度として算出する。
【００７３】
第１の予測渋滞度の算出処理は、以下の通りである。時刻Ｔ１＋Ｔ２に適合する要因、最下位の階層、リンクＬ２に該当する進入リンク、および、リンクＬ２の時刻Ｔ１＋Ｔ２における予測渋滞度（本例では６）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まり、その渋滞度レコードＲ５に含まれるリンクＬ３の退出リンクレコードＲ６も１つ決まるため、当該退出リンクレコードＲ６に対応する予測渋滞度が１つ決まる。
【００７４】
図６に、渋滞予測データから、時刻Ｔ１＋Ｔ２、下位層、ノードＮ２における、進入リンクＬ２の各種渋滞度と当該渋滞度の結果生じる退出リンクＬ３の渋滞度との対応関係を抽出した表を示す。この表の通り、時刻Ｔ１＋Ｔ２に進入リンクＬ２の渋滞度が６の場合は、それの結果生じる退出リンクＬ３の時刻Ｔ１＋Ｔ２＋Ｔ３における第１の予測渋滞度は２である。
【００７５】
第２の予測渋滞度の算出処理は、以下の通りである。時刻Ｔ１＋Ｔ２＋Ｔ３−Ｔ４に適合する要因、最下位の階層、リンクＬ４に該当する進入リンク、および、リンクＬ４の時刻Ｔ１＋Ｔ２＋Ｔ３−Ｔ４における渋滞度（本例では２）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まり、その渋滞度レコードＲ５に含まれるリンクＬ３の退出リンクレコードＲ６も１つ決まるため、当該退出リンクレコードＲ６に対応する予測渋滞度が１つ決まる。
【００７６】
図７に、渋滞予測データから、時刻Ｔ１＋Ｔ２＋Ｔ３−Ｔ４、下位層、ノードＮ２における、進入リンクＬ４の各種渋滞度と当該渋滞度の結果生じる退出リンクＬ３の渋滞度との対応関係を抽出した表を示す。この表の通り、時刻Ｔ１＋Ｔ２＋Ｔ３−Ｔ４に進入リンクＬ４の渋滞度が２の場合は、それの結果生じる退出リンクＬ３の時刻Ｔ１＋Ｔ２＋Ｔ３における第２の予測渋滞度は３である。
【００７７】
ここで、第１の予測渋滞度が２であり、第２の予測渋滞度が３となり、両者が食い違っているが、これら第１、第２の予測渋滞度は交通量のように足し合うのではない。進入リンクＬ２の結果生じる退出リンクＬ３の渋滞度予測データは統計に基づくので、リンクＬ４からのリンクＬ３へ進入する車両についても反映されているからである。第１、第２の予測渋滞度のうち、混雑度が高い（すなわち、値が大きい）方（渋滞度３）を時刻Ｔ１＋Ｔ２＋Ｔ３のリンクＬ３の予測渋滞度として採用することで、確からしい結果を得られる。
【００７８】
ステップ１４５に続いては、処理はステップ１２０に戻り、再度渋滞予測範囲のリンクＬ２、Ｌ３、Ｌ５、Ｌ６中で渋滞度を算出していないリンクがあると判定し、ステップ１２５でリンクＬ６を対象リンクとする。
【００７９】  そしてステップ１３０で、対象リンクＬ６への自車両の到着時刻（進入時刻）を推定する。ただし、対象リンクＬ６の始点のノードＮ３には、リンクＬ３、Ｌ５という２つの渋滞予測範囲内のリンクが接続しているので、リンクＬ３からリンクＬ６へ進入する時点（すなわち進入時刻）と、リンクＬ５からリンクＬ６へ進入する時点（進入時刻）という、２つの時刻を算出する。
【００８０】  リンクＬ３からリンクＬ６への進入時刻は、リンクＬ２からリンクＬ３に進入した時刻Ｔ１＋Ｔ２＋Ｔ３（時点Ｗに相当する）に、リンクＬ３の通過時間Ｔ５を加えた時刻Ｔ１＋Ｔ２＋Ｔ３＋Ｔ５（時点Ｘに相当する）である。また、リンクＬ５からリンクＬ６への進入時刻は、リンクＬ１からリンクＬ５に進入した時刻Ｔ１＋Ｔ２に、リンクＬ５の通過時間Ｔ６を加えた時刻Ｔ１＋Ｔ２＋Ｔ６（時点Ｖに相当する）である。
【００８１】
ここで、通過時間Ｔ５、Ｔ６は、渋滞予測データを用いて決定する。具体的には、リンクＬ３の通過時間Ｔ５については、時刻Ｔ１＋Ｔ２＋Ｔ３に適合する要因、最下位の階層、リンクＬ３に該当する進入リンク、当該リンクＬ３から進入するノードＮ３、現在の当該リンクＬ３の渋滞度（本例では３）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まるため、当該渋滞度レコードＲ５に対応する通過時間ｔが１つ定まる。したがって、その通過時間ｔを通過時間Ｔ５として採用する。また、リンクＬ５の通過時間Ｔ６については、時刻Ｔ１＋Ｔ２に適合する要因、最下位の階層、リンクＬ５に該当する進入リンク、当該リンクＬ５から進入するノードＮ３、現在の当該リンクＬ５の渋滞度（本例では２）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まるため、当該渋滞度レコードＲ５に対応する通過時間ｔが１つ定まる。したがって、その通過時間ｔを通過時間Ｔ６として採用する。
【００８２】
この場合、時刻Ｔ１＋Ｔ２＋Ｔ３＋Ｔ５と時刻Ｔ１＋Ｔ２＋Ｔ６とが一致する場合と一致しない場合がある。一致する場合は、その一致する時刻を対象リンクＬ６への進入時刻とすればよいが、一致する場合は、上記２つの時刻Ｔ１＋Ｔ２＋Ｔ３＋Ｔ５と時刻Ｔ１＋Ｔ２＋Ｔ６のうち、早い方の時刻を採用する。このようにするのは、対象リンク６に進入する時間が早い方の経路が、経路案内用の最適経路として選ばれる可能性が高いからである。ここでは、時刻Ｔ１＋Ｔ２＋Ｔ６の方が早かったとする。したがって、時刻Ｔ１＋Ｔ２＋Ｔ６が対象リンクＬ６への進入時刻となる。
【００８３】
続いて処理はステップ１３５に進み、対象リンクＬ６の始点のノードＮ３から対象リンクＬ６に進入する外部リンクがないので、渋滞度が算出されていない外部リンクがないと判定してステップ１４５に進む。
【００８４】  ステップ１４５では、対象リンクＬ６（第６のリンクおよびリンクＱの一例に相当する）の予測渋滞度を算出する。ただし、対象リンクＬ６には、ノードＮ３を介してリンクＬ５（第５のリンクおよびリンクＰの一例に相当する）からもリンクＬ３（第７のリンクおよびリンクＲの一例に相当する）からも進入するようになっている。したがって、ここでは、リンクＬ５の渋滞度の結果生じる対象リンクＬ６の予測渋滞度を第１の予測渋滞度として算出し、リンクＬ３の渋滞度の結果生じる対象リンクＬ６の予測渋滞度を第２の予測渋滞度として算出する。
【００８５】
第１の予測渋滞度の算出処理は、以下の通りである。時刻Ｔ１＋Ｔ２に適合する要因、最下位の階層、リンクＬ５に該当する進入リンク、および、リンクＬ５の時刻Ｔ１＋Ｔ２における予測渋滞度（本例では２と算出した）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まり、その渋滞度レコードＲ５に含まれるリンクＬ３の退出リンクレコードＲ６も１つ決まるため、当該退出リンクレコードＲ６に対応する予測渋滞度が１つ決まる。
【００８６】
図８に、渋滞予測データから、時刻Ｔ１＋Ｔ２、下位層、ノードＮ３における、進入リンクＬ５の各種渋滞度と当該渋滞度の結果生じる退出リンクＬ６の渋滞度との対応関係を抽出した表を示す。この表の通り、時刻Ｔ１＋Ｔ２に進入リンクＬ５の渋滞度が２の場合は、それの結果生じる退出リンクＬ６の時刻Ｔ１＋Ｔ２＋Ｔ６における第１の予測渋滞度は２である。
【００８７】
第２の予測渋滞度の算出処理は、以下の通りである。時刻Ｔ１＋Ｔ２＋Ｔ３に適合する要因、最下位の階層、リンクＬ３に該当する進入リンク、および、リンクＬ３の時刻Ｔ１＋Ｔ２＋Ｔ３における予測渋滞度（本例では３と算出した）を、渋滞予測データに当てはめることで、それらに該当する渋滞度レコードＲ５が１つ決まり、その渋滞度レコードＲ５に含まれるリンクＬ３の退出リンクレコードＲ６も１つ決まるため、当該退出リンクレコードＲ６に対応する予測渋滞度が１つ決まる。
【００８８】
図９に、渋滞予測データから、時刻Ｔ１＋Ｔ２＋Ｔ３、下位層、ノードＮ３における、進入リンクＬ３の各種渋滞度と当該渋滞度の結果生じる退出リンクＬ６の渋滞度との対応関係を抽出した表を示す。この表の通り、時刻Ｔ１＋Ｔ２＋Ｔ３に進入リンクＬ３の渋滞度が３の場合は、それの結果生じる退出リンクＬ６の時刻Ｔ１＋Ｔ２＋Ｔ３＋Ｔ５における第２の予測渋滞度は３である。
【００８９】
ここで、第１の予測渋滞度が２であり、第２の予測渋滞度が３となり、両者が食い違っているが、リンクＬ３の予測渋滞で説明した通り、これら第１、第２の予測渋滞度は交通量のように足し合うのではなく、第１、第２の予測渋滞度のうち、混雑度が高い（すなわち、値が大きい）方（渋滞度３）を時刻Ｔ１＋Ｔ２＋Ｔ６（ステップ１３０で推定した時刻）のリンクＬ３の予測渋滞度として採用することで、確からしい結果を得られる。
【００９０】
ステップ１４５に続いては、処理はステップ１２０に戻り、再度渋滞予測範囲のリンクＬ２、Ｌ３、Ｌ５、Ｌ６中で渋滞度を算出していないリンクがないと判定し、図３の処理を終了する。
【００９１】
このような処理により、渋滞予測範囲内のリンクＬ２、Ｌ３、Ｌ５、Ｌ６のすべてについて、予測渋滞度が算出された。この予測渋滞度と、リンクＬ１の現在の渋滞度をに基づいて、各リンクの渋滞度に応じたコストを算出する。そして、このコストを用いて、出発地Ｐｏから目的地Ｐｄまでの総コストが最も低い最適経路を（例えばダイクストラ法で）算出する。そして、例えば図１０に示すように、現時点ではリンクＬ２の渋滞度は低くとも、車両がリンクＬ２に入るころには上記の計算のように渋滞度が高くなっている可能性が高い場合は、リンクＬ２を通る経路を避けて、リンクＬ１、Ｌ５、Ｌ３、Ｌ６をこの順に通る最適経路を算出して誘導経路とし、この誘導経路の経路案内を行う。これにより、リンクＬ２における混雑を未然に回避することができる。
【００９２】
以上説明した通り、本実施形態においては、各リンクの予測渋滞度を算出する際、渋滞予測データを用い、この渋滞予測データは、要因毎、階層毎、ノード毎、および、当該ノードに対するすべての進入リンクおよび退出リンクの組み合わせ毎に、当該進入リンクの種々の渋滞度の結果生じる当該退出リンクの種々の予測渋滞度を含んでいる。
【００９３】
渋滞予測データが要因毎の情報を有している効用は以下の通りである。同じ進入退出の組み合わせであっても、要因（曜日、時間）などによって、交通の流れが違うために、進入リンクの渋滞度と退出リンクの渋滞度の関係が変化することに対応することができる。
【００９４】
また、この渋滞予測データは、道路ネットワークデータの階層に合わせて階層化してデータを持つようになっており、進入リンクおよび退出リンクの両方が含まれている階層のうち最も高い階層のデータを用いて、ステップ１４５で当該退出リンクの予測渋滞度を算出する。これにより、例えば高速道路を使用した長距離走行を行う場合の予測渋滞度は、高速道路ネットワークの交通の流れのみを表現した渋滞予測データを用いることとなり、誤差の積算が小さくなり、演算時間も小さくなる。
【００９５】
さらに、この渋滞予測データは、交通の流れを表しているが、交通量の推移ではなく、渋滞度の推移にて表現している。交通量と渋滞度合いは一致せず、同じ交通量でも、勾配や信号機といった外的要因により、渋滞したりしなかったりすることがある。例えば、図１２のように、単位時間当たりの交通量は一定でも、ある閾値以上の交通量の場合、上り坂や信号機といった条件により渋滞する部分としない部分が生じる。したがって、通過交通量を用いて正確に渋滞予測をするためには、勾配や信号機といった情報を、外部パラメータを過不足なく用いて演算する必要があり、推測値の確からしさが低く、計算量も非常に増大する。しかし、本実施形態では、渋滞度の推移の渋滞予測データを用いることで、上記の現象を簡潔に表現でき、計算時間を増加させることなく、正確な渋滞予測を行うことができる。
【００９６】
具体的には、リンクＬ１（第１のリンク）の時刻Ｔ１（第１の時点）の実際の渋滞度を外部から取得し、時刻Ｔ１に適合する要因、下位階層、リンクＬ１に該当する進入リンク（すなわち、進入リンクＬ１そのもの）、および、取得したリンクＬ１の時刻Ｔ１の実際の渋滞度を、渋滞予測データに当てはめる。
【００９７】
すると、上記のような渋滞予測データの構造上、進入リンクＬ１からノードＮ１（第１のノード）を経て進入できる退出リンクＬ２を特定でき、さらに、進入リンクＬ１の種々の渋滞度の結果生じる退出リンクＬ２の種々の予測渋滞度が特定できで、さらに、リンクＬ１の時刻Ｔ１の実際の渋滞度の結果生じる時刻Ｔ１＋Ｔ２（第２の時点）のリンクＬ２の予測渋滞度を取得することができる。
【００９８】
このような手法は、リンクＬ１の時刻Ｔ１の時点の実際の渋滞度を外部から取得し、取得した渋滞度に基づいてリンクＬ２の予測渋滞を算出している点で、現に発生している一時的、突発的な交通状況を反映できる。しかも、従来のような交通量のシミュレーションではなく、渋滞予測データにおけるリンクＮ１の渋滞度とリンクＬ２の渋滞度の因果関係を用いて、交通量の計算を経ることなく、直接的にリンクＮ２の渋滞度を算出している。したがって、交通量以外の影響も容易に渋滞度に反映させることができる。
【００９９】
また、リンクＬ２（第２のリンク）とリンクＬ４（第４のリンク）が同じノードＮ２（第２のノード）を経てリンクＬ３（第３のリンクに）接続しており、リンクＬ３の予測渋滞度を算出する際、リンクＬ２の渋滞度の結果生じるリンクＬ３の第１の予測渋滞度と、リンクＬ４の渋滞度の結果生じるリンクＬ３の第２の予測渋滞度とが異なる場合、それらを足し合わせるのではなく、渋滞度の高い方を採用する。これは、第２のリンクの渋滞度の結果生じる第３のリンクの渋滞度予測データは、他のリンクから第３のリンクへの流入等の影響も反映されたデータとして作成されており、第４のリンクの渋滞度の結果生じる第３のリンクの渋滞度予測データは、他のリンクから第３のリンクへの流入等の影響も反映されたデータとして作成されているからである。
【０１００】  また同様に、リンクＬ５（第５のリンクおよびリンクＰ）とリンクＬ３（第７のリンクおよびリンクＲ）が同じノードＮ３（第３のノードおよびノードＡ）を経てリンクＬ６（第６のリンクおよびリンクＱ）に接続しており、リンク６３の予測渋滞度を算出する際、リンクＬ５の渋滞度の結果生じるリンクＬ６の第１の予測渋滞度と、リンクＬ３の渋滞度の結果生じるリンクＬ６の第２の予測渋滞度とが異なる場合、それらを足し合わせるのではなく、渋滞度の高い方を採用する。
【０１０１】  更に、リンクＬ５の通過時間に基づいて算出したリンクＬ６への第１の進入時刻（第３の時点および時点Ｖ）と、リンクＬ３の通過時間に基づいて算出したリンクＬ６への第２の進入時刻（時点Ｗ）とが異なる場合、第１、第２の進入時刻のうち早い方の進入時刻ＴＸをリンクＬ６への進入時刻とする。
【０１０２】  このようにすることで、図４を一部変更し、リンクＬ６の終点のノードＮ４（図示せず。第４のノードおよびノードＢの一例に相当する。）に、更に渋滞予測範囲内のリンクＬ８（図示せず。第８のリンクおよびリンクＳの一例に相当する。）のリンクが繋がり、そのリンクの終点が目的地Ｐｄとなっている場合、上述の進入時刻ＴＸに適合する要因、下位階層、ノードＮ４、リンクＬ６に該当する進入リンク、および、リンクＬ６の当該進入時刻ＴＸの予測渋滞度（上述の通り３と算出した）を、渋滞予測データに当てはめることで、リンクＬ６からノードＮ４を経て対象範囲中のリンクＬ８に進入する時点における、リンクのＬ８予測渋滞度を取得することができる。このようにすることで、リンクへの進入時刻を統一して、ノードの予測渋滞度の計算を進めることができる。 
【０１０３】
なお、上記実施形態において、制御回路１７が予測手段の一例として機能し、また、制御回路１７がステップ１０５を実行することで範囲限定手段の一例として機能し、また、ステップ１２０〜１４５を実行することで予測渋滞度取得手段の一例として機能する。
【０１０４】
（他の実施形態）
以上、本発明の実施形態について説明したが、本発明の範囲は、上記実施形態のみに限定されるものではなく、本発明の各発明特定事項の機能を実現し得る種々の形態を包含するものである。例えば、以下のような形態も許容される。
【０１０５】
例えば、上記実施形態では、各進入リンクの通過時間は、渋滞予測データにおいて渋滞度毎に記録されたものを用いているが、必ずしもこのようになっておらずともよい。例えば、渋滞度毎の進入リンクの通過時間は、当該渋滞度と当該進入リンクのリンク長およびリンクの格から推定するようになっていてもよい
また、ステップ１４５で、リンクＬ６の予測渋滞度を算出する際、第２の予測渋滞度として、時刻Ｔ１＋Ｔ２＋Ｔ３に適合する要因の要因レコードＲ１に含まれるデータを用いているが、直前のステップ１３０で、リンクＬ６への進入時刻をＴ１＋Ｔ２＋Ｔ６と算出しているので、リンクＬ３からリンクＬ６に時刻Ｔ１＋Ｔ２＋Ｔ６に進入するよう、時刻Ｔ１＋Ｔ２＋Ｔ６−Ｔ７に適合する要因の要因レコードＲ１に含まれるデータを用いて第２の渋滞度を算出するようになっていてもよい。ここで、時間Ｔ７は、リンクＬ３の通過時間である。
【０１０６】
ここで、使用する通過時間Ｔ７は、時刻Ｔ１＋Ｔ２＋Ｔ６に適合する要因、最下位の階層、ノードＮ３、進入リンクＬ３、および、リンクＬ３の推定された渋滞度、のレコードにおける通過時間を採用する。
【０１０７】
また、上記実施形態では、渋滞予測データは、１つの進入リンクについて渋滞度が決まると、対応する退出リンクの予測渋滞度が決まるようになっているが、必ずしもこのようになっておらずともよい。例えば、データ量、計算量が増加するが、渋滞予測データは、複数の進入リンクの渋滞度の組み合わせに対して、退出リンクの渋滞予測データが１つ決まるようになっていてもよい。
【０１０８】
また、上記実施形態では、渋滞予測データは、道路上のすべてのノードのそれぞれに対して、当該ノードに接続する進入リンクおよび退出リンクのすべての組み合わせについて、当該進入リンクの種々の渋滞度と当該退出リンクの種々の予測渋滞度との対応関係を含むようになっているが、よりデータ量を低減するために、複数のノードをグループ分けし、各グループを代表する代表ノードを設定し、それら各グループの代表ノードのみに対して、当該ノードに接続する進入リンク（すなわち、他端で他の代表ノードに接続する代表進入リンクに限る）および退出リンク（ただし、他端で他の代表ノードに接続する代表退出リンクに限る）のすべての組み合わせについて、当該進入リンクの種々の渋滞度と当該退出リンクの種々の予測渋滞度との対応関係を含むようになっていてもよい。この場合、予測渋滞度の計算は、代表退出リンクのみに対して行うようになっていればよい。
【０１０９】
また、上記の実施形態において、制御回路１７がプログラムを実行することで実現している各機能は、それらの機能を有するハードウェア（例えば回路構成をプログラムすることが可能なＦＰＧＡ）を用いて実現するようになっていてもよい。
【符号の説明】
【０１１０】
１                    ナビゲーション装置
１１                  位置検出器
１２                  画像表示装置
１３                  操作部
１４                  スピーカ
１５                  通信部
１６                  地図データ取得部
１７                  制御回路１７
【図１】
0005768526.tif 000002
【図２】
0005768526.tif 000003
【図３】
0005768526.tif 000004
【図４】
0005768526.tif 000005
【図５】
0005768526.tif 000006
【図６】
0005768526.tif 000007
【図７】
0005768526.tif 000008
【図８】
0005768526.tif 000009
【図９】
0005768526.tif 000010
【図１０】
0005768526.tif 000011
【図１１】
0005768526.tif 000012
【図１２】
0005768526.tif 000013
【図１３】
0005768526.tif 000014