道路網を構成する複数のリンクからいずれかのリンクを選択リンクとして選択するリンク選択手段と、前記選択リンクの前方に存在する交差点のいずれかを対象交差点として、前記選択リンクの道路状況および前記対象交差点の種類に応じた走行パターンを前記選択リンクにおける車両の走行パターンとして予測する走行パターン予測手段とを備えることを特徴とする走行パターン予測装置。請求項1に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの道路状況が順調であり、かつ前記対象交差点が信号機の設置されている信号機交差点である場合、前記対象交差点における停止確率と前記選択リンクの始端における停止確率とに基づいて、前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項2に記載の走行パターン予測装置において、交差点において互いに交差する道路の道路種別の組み合わせに応じた停止確率を表す赤信号停止確率テーブルが予め記憶されており、前記走行パターン予測手段は、前記赤信号停止確率テーブルに基づいて、前記対象交差点における停止確率を決定することを特徴とする走行パターン予測装置。請求項2または3に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの始端および前記対象交差点の両方で停止しない第1の走行パターンと、前記選択リンクの始端で停止せずに前記対象交差点で停止する第2の走行パターンと、前記選択リンクの始端で停止して前記対象交差点で停止しない第3の走行パターンと、前記選択リンクの始端および前記対象交差点の両方で停止する第4の走行パターンとについて、前記対象交差点における停止確率と前記選択リンクの始端における停止確率とに基づく発生確率をそれぞれ算出し、前記第1の走行パターン、前記第2の走行パターン、前記第3の走行パターンおよび前記第4の走行パターンを各々の前記発生確率に応じた割合で重畳することにより、前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項1乃至4のいずれか一項に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの道路状況が順調であり、かつ前記対象交差点が一時停止交差点である場合、前記対象交差点において一時停止する先行車両の台数に基づいて加減速回数を決定し、前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項5に記載の走行パターン予測装置において、交差点において互いに交差する道路の道路種別の組み合わせに応じた先行車両の台数を表す先行台数テーブルが予め記憶されており、前記走行パターン予測手段は、前記先行台数テーブルに基づいて、前記対象交差点において一時停止する先行車両の台数を決定することを特徴とする走行パターン予測装置。請求項5または6に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記車両の過去の走行履歴に基づいて、前記走行パターンにおける加減速度を決定することを特徴とする走行パターン予測装置。請求項7に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記加減速度と、予め定められた車両一台当たりの停止占有長とに基づいて、前記走行パターンにおける加減速時の最大走行速度を算出し、前記加減速時の最大走行速度が所定の一定走行速度以下である場合は、前記加減速時の最大走行速度に基づいて前記走行パターンを予測し、前記加減速時の最大走行速度が前記一定走行速度よりも大きい場合は、前記一定走行速度に基づいて前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項8に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記車両の過去の走行履歴に基づいて、前記一定走行速度を決定することを特徴とする走行パターン予測装置。請求項5乃至9のいずれか一項に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの始端で停止しないときの走行パターンと、前記選択リンクの始端で停止するときの走行パターンとを、前記選択リンクの始端における停止確率に応じた割合で重畳することにより、前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項1乃至10のいずれか一項に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの道路状況が順調であり、かつ前記対象交差点が信号機の設置されている信号機交差点でも一時停止交差点でもない場合、前記選択リンクの始端から終端まで一定の走行速度による走行パターンと、所定の加速度に応じて上昇した後に一定となる走行速度による走行パターンとを、前記選択リンクの始端における停止確率に応じた割合で重畳することにより、前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項2乃至11のいずれか一項に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの終端に当たる交差点を前記対象交差点とすることを特徴とする走行パターン予測装置。請求項1乃至12のいずれか一項に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの道路状況が混雑または渋滞であり、かつ前記対象交差点が信号機の設置されている信号機交差点である場合、前記対象交差点における青信号時間に基づいて加減速回数を算出し、前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項13に記載の走行パターン予測装置において、交差点において互いに交差する道路の道路種別の組み合わせに応じた青信号時間を表す青信号時間テーブルが予め記憶されており、前記走行パターン予測手段は、前記青信号時間テーブルに基づいて、前記対象交差点における青信号時間を決定することを特徴とする走行パターン予測装置。請求項13または14に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記車両の過去の走行履歴に基づいて、前記走行パターンにおける加減速度を決定することを特徴とする走行パターン予測装置。請求項15に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記青信号時間、前記加減速度、車両一台当たりの停止占有長および単位時間当たりの車両通過台数に基づいて、前記走行パターンにおける一定走行速度を算出することを特徴とする走行パターン予測装置。請求項1乃至16のいずれか一項に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの道路状況が混雑または渋滞であり、かつ前記対象交差点が一時停止交差点である場合、前記選択リンクの長さと予め定められた車両一台当たりの停止占有長とに基づいて加減速回数を算出し、前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項17に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記車両の過去の走行履歴に基づいて、前記走行パターンにおける加減速度を決定することを特徴とする走行パターン予測装置。請求項18に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記加減速度と、予め定められた車両一台当たりの停止占有長とに基づいて、前記走行パターンにおける加減速時の最大走行速度を算出し、前記加減速時の最大走行速度が所定の一定走行速度以下である場合は、前記加減速時の最大走行速度に基づいて前記走行パターンを予測し、前記加減速時の最大走行速度が前記一定走行速度よりも大きい場合は、前記一定走行速度に基づいて前記走行パターンを予測することを特徴とする走行パターン予測装置。請求項19に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記車両の過去の走行履歴に基づいて、前記一定走行速度を決定することを特徴とする走行パターン予測装置。請求項13乃至20のいずれか一項に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクが含まれている混雑または渋滞の先頭に当たる交差点を前記対象交差点とすることを特徴とする走行パターン予測装置。請求項13乃至21のいずれか一項に記載の走行パターン予測装置において、前記走行パターン予測手段は、前記選択リンクの始端から前記対象交差点までの距離が所定のしきい値以上である場合、前記走行パターンの変動幅を低減するためのなまり処理を行うことを特徴とする走行パターン予測装置。車両に搭載される装置であって、道路網を構成する複数のリンクを含む地図データを記憶する地図データ記憶手段と、前記地図データに基づいて前記複数のリンクからいずれかのリンクを選択リンクとして選択するリンク選択手段と、前記選択リンクの前方に存在する交差点のいずれかを対象交差点として、前記選択リンクの道路状況および前記対象交差点の種類に応じた走行パターンを前記選択リンクにおける前記車両の走行パターンとして予測する走行パターン予測手段とを備えることを特徴とする車載装置。道路網を構成する複数のリンクを含む地図データを記憶した記憶装置と、演算装置とを備えたコンピュータによる車両の走行パターン予測方法であって、前記演算装置により、前記記憶装置から前記地図データを読み出し、読み出した前記地図データに基づいて前記複数のリンクからいずれかのリンクを選択リンクとして選択し、前記選択リンクの前方に存在する交差点のいずれかを対象交差点として、前記選択リンクの道路状況および前記対象交差点の種類に応じた走行パターンを前記選択リンクにおける前記車両の走行パターンとして予測することを特徴とする走行パターン予測方法。上述した従来のカーナビゲーション装置では、リンク旅行時間Tと道路種別により決まる定数Cとに基づいて、N=T/Cの式により各道路リンクにおける車両の加減速の回数Nを推定し、これを用いて車両の走行パターンを予測している。しかし、このような単純な予測方法では、道路状況や交差点における信号機の有無等が考慮されていないため、車両の走行パターンを正確に予測することは困難である。本発明による走行パターン予測装置は、道路網を構成する複数のリンクからいずれかのリンクを選択リンクとして選択するリンク選択手段と、選択リンクの前方に存在する交差点のいずれかを対象交差点として、選択リンクの道路状況および対象交差点の種類に応じた走行パターンを選択リンクにおける車両の走行パターンとして予測する走行パターン予測手段とを備える。本発明による車載装置は、車両に搭載されており、道路網を構成する複数のリンクを含む地図データを記憶する地図データ記憶手段と、地図データに基づいて複数のリンクからいずれかのリンクを選択リンクとして選択するリンク選択手段と、選択リンクの前方に存在する交差点のいずれかを対象交差点として、選択リンクの道路状況および対象交差点の種類に応じた走行パターンを選択リンクにおける車両の走行パターンとして予測する走行パターン予測手段とを備える。本発明による走行パターン予測方法は、道路網を構成する複数のリンクを含む地図データを記憶した記憶装置と、演算装置とを備えたコンピュータにより行われるものであり、演算装置により、記憶装置から地図データを読み出し、読み出した地図データに基づいて複数のリンクからいずれかのリンクを選択リンクとして選択し、選択リンクの前方に存在する交差点のいずれかを対象交差点として、選択リンクの道路状況および対象交差点の種類に応じた走行パターンを選択リンクにおける車両の走行パターンとして予測する。本発明によれば、道路状況や交差点における信号機の有無等を考慮して、車両の走行パターンを正確に予測することができる。本発明の一実施の形態による走行パターン予測装置について以下に説明する。図1は、本発明の一実施形態による走行パターン予測装置の適用例としてのナビゲーション装置の構成を示すブロック図である。ナビゲーション装置1は、車両に搭載されて使用されるものであり、図1に示すように、制御部10、振動ジャイロ11、車速センサ12、ハードディスクドライブHDD13、GPSGlobalPositioningSystem受信部14、VICSVehicleInformationandCommunicationSystem登録商標情報受信部15、表示モニタ16、スピーカ17および入力装置18を備えている。制御部10は、マイクロプロセッサや各種周辺回路、RAM、ROM等によって構成されており、HDD13に記録されている制御プログラムや地図データに基づいて、各種の処理を実行する。たとえば、目的地を設定する際の目的地の検索処理、設定された目的地までの推奨経路の探索処理、自車両の現在位置の検出処理、各種の画像表示処理、音声出力処理などが制御部10によって実行される。振動ジャイロ11は、自車両の角速度を検出するためのセンサである。車速センサ12は、自車両の走行速度を検出するためのセンサである。これらのセンサにより自車両の運動状態を所定の時間間隔ごとに検出することにより、制御部10において自車両の移動方向および移動量が求められる。HDD13は不揮発性の記録媒体であり、制御部10において上記のような処理を実行するための制御プログラムや地図データなどが記録されている。HDD13に記録されているデータは、必要に応じて制御部10の制御により読み出され、制御部10が実行する様々な処理や制御に利用される。HDD13に記録された地図データは、経路計算データと、道路データと、背景データとを含む。経路計算データは、目的地までの推奨経路を探索する際などに用いられるデータである。道路データは、道路の形状や種別などを表すデータである。道路データにおいて、各道路は後述するようにノードや形状補間点と呼ばれる点を複数繋げることによって構成されている。背景データは、地図の背景を表すデータである。なお、地図の背景とは、地図上に存在する道路以外の様々な構成物である。たとえば、河川、鉄道、緑地帯、各種構造物などが背景データによって表される。地図データにおいて道路網を構成する各道路の最小単位はリンクと呼ばれている。すなわち、所定の道路区間にそれぞれ対応する複数のリンクによって道路網が構成されており、リンク単位で経路計算データおよび道路データが表現されている。なお、道路データにおいて各リンクの両端には、座標情報がそれぞれ設定されたノードと呼ばれる点が設けられている。また、各リンクの途中には形状補間点と呼ばれる点が必要に応じて設けられている。各形状補間点には、ノードと同様に座標情報がそれぞれ設定されている。これらの点を順に繋げることにより、道路データにおいて道路の形状が表される。一方、経路計算データには、各道路区間に対応するリンクごとに、自車両が当該道路区間を走行する際の通過所要時間等に応じたリンクコストが設定されている。このリンクコストに基づいて、予め設定された経路探索条件に応じたリンクの組合せを求めることにより、ナビゲーション装置1において推奨経路の探索が行われる。たとえば、移動時間の短さを最優先として経路探索を行うような経路探索条件が設定されている場合は、出発地から目的地までの通過所要時間が最小となるリンクの組合せが推奨経路として求められる。なお、上記ではナビゲーション装置1において地図データがHDD13に記録されている例を説明したが、これらをHDD以外の記録媒体に記録することとしてもよい。たとえば、CD-ROMやDVD-ROM、メモリカードなどに記録された地図データを用いることができる。すなわち、本実施の形態によるナビゲーション装置1では、どのような記録媒体を用いてこれらのデータを記憶してもよい。GPS受信部14は、GPS衛星から送信されるGPS信号を受信して制御部10へ出力する。GPS信号には、自車両の現在位置を求めるための情報として、そのGPS信号を送信したGPS衛星の位置と送信時刻に関する情報が含まれている。したがって、所定数以上のGPS衛星からGPS信号を受信することにより、これらの情報に基づいて、自車両の現在位置を制御部10において算出することができる。このGPS信号に基づく自車両の現在位置の算出結果と、前述の振動ジャイロ11および車速センサ12の各検出結果に基づく移動方向および移動量の算出結果とにより、制御部10において所定時間ごとに自車両の現在位置を検出するための位置検出処理が実行され、自車両の現在位置が検出される。VICS情報受信部15は、図示しないVICSセンターからナビゲーション装置1に対して送信されるVICS情報を受信する。このVICS情報をVICS情報受信部15が受信することにより、渋滞情報を始めとする様々な道路交通情報がナビゲーション装置1において取得される。VICS情報により提供される渋滞情報では、各リンクの道路状況を順調、混雑または渋滞の3種類の道路状況のうちいずれかで表現している。VICS情報受信部15により受信されたVICS情報は、制御部10に出力され、渋滞情報の表示や推奨経路の探索などに利用される。なお、VICSセンターからナビゲーション装置1へのVICS情報の送信は、主に高速道路上に設置されている電波ビーコンや、主に一般道路上に設置されている光ビーコン、またはFM多重放送によって行われる。電波ビーコンや光ビーコンは、その設置地点付近を通過する車両に対して、電波あるいは光赤外線により局所的にVICS情報を送信するものである。これに対して、FM多重放送では比較的広い地域に対してVICS情報を送信することができる。表示モニタ16は、ナビゲーション装置1において様々な画面表示を行うための装置であり、液晶ディスプレイ等を用いて構成される。この表示モニタ16により、地図画面の表示や推奨経路の案内表示などが行われる。表示モニタ16に表示される画面の内容は、制御部10が行う画面表示制御によって決定される。表示モニタ16は、たとえば自車両のダッシュボード上やインストルメントパネル内など、ユーザが見やすいような位置に設置されている。スピーカ17は、制御部10の制御により様々な音声情報を出力する。たとえば、推奨経路に従って自車両を目的地まで案内するための経路案内用の音声や、各種の警告音などがスピーカ17から出力される。入力装置18は、ナビゲーション装置1を動作させるための様々な入力操作をユーザが行うための装置であり、各種の入力スイッチ類を有している。ユーザは、入力装置18を操作することにより、たとえば、目的地に設定したい施設や地点の名称等を入力したり、推奨経路の探索条件を設定したり、予め登録された登録地の中から目的地を選択したり、地図を任意の方向にスクロールしたりすることができる。この入力装置18は、操作パネルやリモコンなどによって実現することができる。あるいは、入力装置18を表示モニタ16と一体化されたタッチパネルとしてもよい。ユーザが入力装置18を操作して目的地を設定すると、ナビゲーション装置1は、前述のようにして検出された自車両の現在位置を出発地として、前述の経路計算データに基づいて所定のアルゴリズムの演算による経路探索処理を行う。この処理により、出発地から目的地まで至る推奨経路を探索する。さらにナビゲーション装置1は、たとえば色を変える等の方法により、表示モニタ16に表示された地図上において他の道路と識別可能な形態で探索された推奨経路を表示する。そして、推奨経路に従って所定の画像情報や音声情報を表示モニタ16やスピーカ17から出力することにより、自車両を目的地まで案内する。またナビゲーション装置1は、地図データから対象リンクを抽出し、その対象リンクにおける自車両の走行パターンを予測する走行パターン予測処理を必要に応じて行うことができる。この走行パターン予測処理を行うことにより、ナビゲーション装置1は、道路状況や交差点における信号機の有無等を考慮した実際の車両走行パターンを正確に予測する走行パターン予測装置として動作することができる。以降では、ナビゲーション装置1において実行される本発明の走行パターン予測処理について詳細に説明する。始めに、本発明の走行パターン予測処理と比較するために、従来の走行パターン予測処理についての説明を行う。図2は、従来の走行パターン予測処理により予測された走行パターンの一例を示している。図2に示すように、従来の走行パターン予測処理では、道路状況や交差点の種類などに関わらず、各リンクにおいて車両が所定の加減速度で加減速を繰り返すような走行パターンを予測していた。しかし、このような走行パターンは実際の車両の走行状況を正しく反映したものとは言い難い。このように、従来の走行パターン予測処理を用いた場合、実際の車両走行パターンを正確に予測することは困難である。一方、本発明の走行パターン予測処理では、図3のフローチャートに示す処理を行うことにより、走行パターンを予測するリンクの前方に存在する交差点のいずれかを対象交差点として、当該リンクの道路状況および対象交差点の種類に応じた走行パターンを当該リンクにおける車両の走行パターンとして予測する。これにより、道路状況や交差点における信号機の有無等を考慮した実際の車両走行パターンを正確に予測するようにしている。図3のフローチャートについて以下に説明する。このフローチャートに示す走行パターン予測処理は、ユーザの指示や所定の処理開始条件などに応じて、ナビゲーション装置1において制御部10により実行される。ステップS10において、制御部10は、HDD13に記録されている地図データから走行パターンの予測対象とする対象リンクを抽出する。ここでは、たとえばユーザにより指定された地域内に含まれる全てのリンクを対象リンクとして抽出する。また、たとえば図3のフローチャートに示す走行パターン予測処理によって予測された走行パターンを用いることにより、出発地から目的地までの最小燃費経路を探索することができる。このような場合は、出発地と目的地を含む抽出範囲を所定の設定方法により設定し、その抽出範囲内に存在するリンクを対象リンクとして抽出する。これ以外にも、任意のリンクを対象リンクとして抽出することができる。ステップS20において、制御部10は、ステップS10で抽出した対象リンクの中からいずれかのリンクを選択する。以降では、このリンクを選択リンクと称する。これにより、地図データにおいて道路網を構成する複数のリンクからいずれかのリンクが選択リンクとして選択される。ステップS30において、制御部10は、ステップS20で選択した選択リンクについて渋滞情報を取得する。ここでは、VICS情報受信部15により受信されたVICS情報から選択リンクの渋滞情報を取得する。ステップS40において、制御部10は、ステップS30で取得した渋滞情報に基づいて、選択リンクの道路状況が順調であるか否かを判定する。選択リンクの道路状況が順調である場合はステップS50へ進む。この場合、以降で説明するステップS50~S90の処理により、選択リンクの終端に当たる交差点を対象交差点として、その対象交差点の種類に応じた走行パターンを予測する。一方、選択リンクの道路状況が順調でない場合、すなわち混雑または渋滞である場合はステップS100へ進む。この場合、後で説明するステップS100~S150の処理により、当該混雑または渋滞の先頭に当たる交差点を対象交差点として、その対象交差点の種類に応じた走行パターンを予測する。なお、以降の説明では、選択リンクが混雑している場合と渋滞している場合を総称して単に渋滞と表現することがある。ステップS50において、制御部10は、対象交差点である選択リンク終端が信号機の設置されている交差点以降、信号機交差点と称するであるか否かを判定する。選択リンク終端が信号機交差点である場合はステップS60へ進み、信号機交差点でない場合はステップS70へ進む。ステップS60において、制御部10は、順調時の信号機走行パターン予測処理を実行する。この処理により、選択リンクの道路状況が順調であり、かつ対象交差点である選択リンク終端が信号機交差点である場合の走行パターンが予測される。なお、順調時の信号機走行パターン予測処理の具体的な内容については、後で図4のフローチャートを用いて詳しく説明する。ステップS60を実行したら、制御部10はステップS160へ進む。ステップS70において、制御部10は、対象交差点である選択リンク終端が一時停止交差点であるか否かを判定する。選択リンク終端が一時停止交差点である場合はステップS80へ進み、一時停止交差点でない場合はステップS90へ進む。ステップS80において、制御部10は、順調時の一時停止走行パターン予測処理を実行する。この処理により、選択リンクの道路状況が順調であり、かつ対象交差点である選択リンク終端が一時停止交差点である場合の走行パターンが予測される。なお、順調時の一時停止走行パターン予測処理の具体的な内容については、後で図5のフローチャートを用いて詳しく説明する。ステップS80を実行したら、制御部10はステップS160へ進む。ステップS90において、制御部10は、順調時の通過走行パターン予測処理を実行する。この処理により、選択リンクの道路状況が順調であり、かつ対象交差点である選択リンク終端が信号機交差点でも一時停止交差点でもない場合の走行パターンが予測される。なお、順調時の通過走行パターン予測処理の具体的な内容については、後で図6のフローチャートを用いて詳しく説明する。ステップS90を実行したら、制御部10はステップS160へ進む。ステップS100において、制御部10は、渋滞の先頭を推定する。ここでは、後で図23を参照して説明するような方法により、道路状況が順調であるリンクが見つかるまで選択リンクから先に繋がっているリンクを辿っていくことで、どの交差点が渋滞の先頭であるかを推定する。これにより、選択リンクが含まれている混雑または渋滞の先頭に当たる対象交差点としての交差点が推定される。ステップS110において、制御部10は、ステップS100の処理によって対象交差点として推定された渋滞の先頭が信号機交差点であるか否かを判定する。渋滞の先頭が信号機交差点である場合はステップS120へ進み、信号機交差点でない場合はステップS130へ進む。ステップS120において、制御部10は、渋滞時の信号機走行パターン予測処理を実行する。この処理により、選択リンクの道路状況が混雑または渋滞であり、かつ対象交差点である渋滞の先頭が信号機交差点である場合の走行パターンが予測される。なお、渋滞時の信号機走行パターン予測処理の具体的な内容については、後で図7のフローチャートを用いて詳しく説明する。ステップS120を実行したら、制御部10はステップS160へ進む。ステップS130において、制御部10は、ステップS100の処理によって対象交差点として推定された渋滞の先頭が一時停止交差点であるか否かを判定する。渋滞の先頭が一時停止交差点である場合はステップS140へ進み、一時停止交差点でない場合はステップS150へ進む。ステップS140において、制御部10は、渋滞時の一時停止走行パターン予測処理を実行する。この処理により、選択リンクの道路状況が混雑または渋滞であり、かつ対象交差点である渋滞の先頭が一時停止交差点である場合の走行パターンが予測される。なお、渋滞時の一時停止走行パターン予測処理の具体的な内容については、後で図8のフローチャートを用いて詳しく説明する。ステップS140を実行したら、制御部10はステップS160へ進む。ステップS150において、制御部10は、予め設定されたデフォルト走行パターンを選択リンクの走行パターンとして適用する。たとえば、図2に例示したような従来の予測方法による走行パターンをデフォルト走行パターンとして選択リンクに適用することができる。これにより、選択リンクの道路状況が混雑または渋滞であり、かつ対象交差点である渋滞の先頭が信号機交差点でも一時停止交差点でもないため渋滞原因が不明である場合の走行パターンが予測される。ステップS150を実行したら、制御部10はステップS160へ進む。なお、たとえば高速道路の登り坂や踏切などのように、信号機交差点や一時停止交差点ではないにも関わらず渋滞が多発する場所を渋滞多発地点として予め登録しておき、この渋滞多発地点が渋滞の先頭である場合は、それに応じたデフォルト走行パターンをステップS150において適用してもよい。このとき適用するデフォルト走行パターンは、過去の収集データを統計的に処理した統計データ等に基づいて予め設定することができる。さらに、事故渋滞などのように渋滞原因が明らかである場合は、その渋滞原因に応じたデフォルト走行パターンをステップS150において適用してもよい。これ以外にも、様々なデフォルト走行パターンを選択リンクに対して適用することができる。ステップS160において、制御部10は、ステップS10で抽出した対象リンクの全てをステップS20において選択リンクとして選択済みであるか否かを判定する。全ての対象リンクを選択リンクとして選択済みである場合、すなわち全対象リンクについて走行パターンを予測済みであるとき、制御部10は図3のフローチャートに示す走行パターン予測処理を終了する。一方、未選択の対象リンクが存在する場合、制御部10はステップS20へ戻る。この場合、制御部10はステップS20において未選択の対象リンクの中からいずれかを選択リンクとして選択した後、その選択リンクに対してステップS30以降の処理を実行する。これを全ての対象リンクについて繰り返し行うことにより、全対象リンクの走行パターンが予測される。ナビゲーション装置1は、以上説明したような走行パターン予測処理を制御部10において実行することで、任意の対象リンクにおける車両走行パターンを予測する。こうして予測された車両走行パターンは、ナビゲーション装置1において様々な処理に利用することができる。たとえば、前述のように出発地から目的地までの最小燃費経路を探索する場合は、図3の走行パターン予測処理によって求められた走行パターンに基づいて各対象リンクの消費エネルギー値を推定する。この消費エネルギー値の合計が最小となるリンクの組合せを出発地から目的地までの間について求めることにより、最小燃費経路を探索することができる。次に、図3のステップS60において実行される順調時の信号機走行パターン予測処理の具体的な内容について説明する。図4は、順調時の信号機走行パターン予測処理のフローチャートである。以下では、図9に示すような始端ノードNa、終端ノードNbの選択リンクを例として、図4のフローチャートの各処理について説明する。なお、図9において終端ノードNbは信号機交差点である。ステップS200において、制御部10は、HDD13に予め記憶された赤信号停止確率テーブルを参照し、対象交差点に当たる選択リンクの終端ノードNbにおける自車両の停止確率Pbを決定する。赤信号停止確率テーブルとは、様々な信号機交差点について自車両が赤信号で停止する確率を道路種別に応じてテーブル化したものである。すなわち、HDD13には、交差点において互いに交差する道路の道路種別の組合せに応じた停止確率を表すルックアップテーブル情報が赤信号停止確率テーブルとして記録されている。図10に赤信号停止確率テーブルの例を示す。図10の赤信号停止確率テーブルでは、自道路と交差道路の道路種別が国道、県道、その他の道路種別にそれぞれ分類されており、その各道路種別同士の組合せに対して、赤信号による自車両の停止確率がパーセント表記でそれぞれ設定されている。ステップS200では、この赤信号停止確率テーブルを参照することにより、図9に例示した選択リンクの終端ノードNbの停止確率Pbが決定される。たとえば自道路である選択リンクが国道であり、終端ノードNbで選択リンクと交差する道路が県道である場合、図10の赤信号停止確率テーブルから終端ノードNbの停止確率Pbは300.3と決定される。ステップS210において、制御部10は、選択リンクの始端ノードNaにおける自車両の停止確率Paを決定する。ここでは、選択リンクの始端ノードNaの種類に応じた方法により停止確率Paを決定する。たとえば始端ノードNaが信号機交差点である場合は、ステップS200と同様に、赤信号停止確率テーブルを参照することで始端ノードNaにおける自車両の停止確率Paを決定する。一方、始端ノードNaが一時停止交差点である場合は、始端ノードNaにおいて自車両は必ず一時停止することから、停止確率Paを1100とする。また、始端ノードNaが信号機交差点でも一時停止交差点でもない場合は、始端ノードNaにおいて自車両は停止しないとして停止確率Paを0とする。このようにして、選択リンクの始端ノードNaの種類に応じて停止確率Paを決定することができる。なお、これ以外の方法により停止確率Paを決定してもよい。たとえば、選択リンクが国道であり、始端ノードNaが信号機交差点であるときに、その始端ノードNaで選択リンクと交差する道路が国道でも県道でもない道路であるとする。この場合、図10の赤信号停止確率テーブルから始端ノードNaの停止確率Paは100.1と決定される。ステップS220において、制御部10は、ステップS200、S210でそれぞれ決定した終端ノードNbの停止確率Pbおよび始端ノードNaの停止確率Paに基づいて、選択リンクにおける各シナリオの発生確率をそれぞれ算出する。シナリオとは、選択リンクの始端ノードNaと終端ノードNbのそれぞれにおいて自車両が停止する場合と停止しない場合に予測される各走行パターンを表している。図9の選択リンクに対応するシナリオの例を図11に示す。図11aに示すシナリオ1は、始端ノードNaおよび終端ノードNbの両方において自車両が停止しない場合の走行パターンを表している。シナリオ1によると、自車両は始端ノードNaから終端ノードNbまで、一定走行速度Vconstで一定速走行時間Tconstの間だけ選択リンクを走行する。図11bに示すシナリオ2は、始端ノードNaにおいて自車両が停止せず、終端ノードNbにおいて停止する場合の走行パターンを表している。シナリオ2によると、自車両は始端ノードNaから一定走行速度Vconstで一定速走行時間Tconstの間だけ選択リンクを走行した後、減速度Gで減速時間Vconst/Gの間減速し、終端ノードNbにおいて停止する。図11cに示すシナリオ3は、始端ノードNaにおいて自車両が停止し、終端ノードNbにおいて停止しない場合の走行パターンを表している。シナリオ3によると、自車両は始端ノードNaにおいて停止し、そこから一定走行速度Vconstに達するまでの加速時間Vconst/Gの間は、加速度Gで加速しながら選択リンクを走行する。一定走行速度Vconstに達すると、一定走行速度Vconstで終端ノードNbまで一定速走行時間Tconstの間だけ選択リンクを走行する。図11dに示すシナリオ4は、始端ノードNaおよび終端ノードNbの両方において自車両が停止する場合の走行パターンを表している。シナリオ4によると、自車両は始端ノードNaにおいて停止し、そこから一定走行速度Vconstに達するまでの加速時間Vconst/Gの間は、加速度Gで加速しながら選択リンクを走行する。一定走行速度Vconstに達したら一定走行速度Vconstで一定速走行時間Tconstの間だけ選択リンクを走行した後、減速度Gで減速時間Vconst/Gの間減速し、終端ノードNbにおいて停止する。なお、図11a~dに示した各シナリオにおいて、時刻Taは自車両が始端ノードNaを通過または始端ノードNaから走行開始する時刻を表し、時刻Tbは自車両が終端ノードNbを通過または終端ノードNbにおいて停止する時刻を表している。図12は、図11a~dの各シナリオの内容とその発生確率の一覧表を示している。図12に示すように、シナリオ1~4の発生確率をP1~P4とすると、この発生確率P1~P4は、始端ノードNaの停止確率Paと終端ノードNbの停止確率Pbに基づいて、それぞれ以下の式1により算出することができる。なお、式1において、停止確率PaおよびPbは、図10の赤信号停止確率テーブルに示したようなパーセント表記の確率値ではなく、0≦Pa、Pb≦1である。1ステップS230において、制御部10は、ステップS220で算出した各シナリオの発生確率P1~P4に基づいて、自車両の一定走行速度Vconstを算出する。ここでは、以下の計算方法により一定走行速度Vconstを算出する。一定走行速度Vconstを算出するために、各シナリオにおける走行距離の期待値を考える。自車両が加速中に選択リンクを走行する距離の期待値は、シナリオ3、4の発生確率P3、P4と加速度Gを用いて以下の式2により表すことができる。2一方、自車両が減速中に選択リンクを走行する距離の期待値は、シナリオ2、4の発生確率P2、P4と減速度Gを用いて以下の式3により表すことができる。3自車両が一定走行速度Vconstで選択リンクを走行する距離の期待値は、シナリオ1~4の発生確率P1~P4と加減速度Gを用いて以下の式4により表すことができる。ここでTは選択リンクのリンク旅行時間を表している。制御部10は、地図データやVICS情報受信部15により受信されたVICS情報に含まれる渋滞情報からリンク旅行時間Tを決定することができる。4P1P2P3P4=1であることを利用して式4を変形すると、以下の式5が得られる。5式2、3および5を合計することにより、自車両が選択リンクを走行する距離の期待値を式6のように求めることができる。6ここで、選択リンクのリンク長をLとすると、式6で表される走行距離の期待値はリンク長Lと一致する。したがって、以下の二次方程式7が得られる。7二次方程式7を解くことにより、一定走行速度Vconstが以下の式8のように求められる。なお、式8においてP=P2P32P4である。8式8におけるPの値は、式1を用いることにより、以下の式9のようにして求めることができる。9式9によって表されるように、式8におけるPの値は、始端ノードNaの停止確率Paと終端ノードNbの停止確率Pbの合計値で表すことができる。ステップS230では、以上説明したような計算方法により一定走行速度Vconstを算出することができる。ステップS240において、制御部10は、ステップS230で算出した一定走行速度Vconstに基づいて、自車両が選択リンクを一定走行速度Vconstで走行する距離と時間をそれぞれ表す一定速走行距離Lconstおよび一定速走行時間Tconstを算出する。ここでは、以下の式10、11を用いることにより、一定速走行距離Lconstと一定速走行時間Tconstをそれぞれ算出することができる。1011ステップS250において、制御部10は、ステップS230で算出した一定走行速度Vconstと、ステップS240で算出した一定速走行距離Lconstおよび一定速走行時間Tconstとに基づいて、選択リンクにおける自車両の予測走行パターンを決定する。ここでは、一定走行速度Vconst、一定速走行距離Lconstおよび一定速走行時間Tconstによって特定されるシナリオ1~4の各走行パターンをその発生確率P1~P4に応じた割合で重畳することにより、選択リンクにおける自車両の予測走行パターンを決定する。すなわち、各シナリオの期待値に応じた重ね合わせパターンを選択リンクの走行パターンとして予測する。ステップS250を実行したら、制御部10は図4のフローチャートを終了して図3のフローチャートに戻る。以上説明したようにして、順調時の信号機走行パターン予測処理が実行される。上述した順調時の信号機走行パターン予測処理によって得られる予測走行パターンの例を図13に示す。図13の予測走行パターンにおいて時刻Taから時刻Tbの間に破線で示した部分は、加速または減速する場合の走行パターンと一定走行速度Vconstの場合の走行パターンとが各シナリオの発生確率P1~P4に応じて重ね合わせられていることを表している。次に、図3のステップS80において実行される順調時の一時停止走行パターン予測処理の具体的な内容について説明する。図5は、順調時の一時停止走行パターン予測処理のフローチャートである。以下では、図14に示すような始端ノードNa、終端ノードNbの選択リンクを例として、図5のフローチャートの各処理について説明する。なお、図14において終端ノードNbは一時停止交差点である。ステップS300において、制御部10は、HDD13に予め記憶された先行台数テーブルを参照し、選択リンクにおける加減速回数を決定する。先行台数テーブルとは、様々な一時停止交差点について自車両が到着したときに既に並んでいると予測され、その交差点において一時停止する先行車両の台数を道路種別に応じてテーブル化したものである。すなわち、HDD13には、交差点において互いに交差する道路の道路種別の組合せに応じた先行車両の台数を表すルックアップテーブル情報が先行台数テーブルとして記録されている。図15に先行台数テーブルの例を示す。図15の先行台数テーブルでは、自道路と交差道路の道路種別が国道、県道、その他の道路種別にそれぞれ分類されており、その各道路種別同士の組合せに対して、自車両が到着したときに予測される先行車両の台数がそれぞれ設定されている。ステップS300では、この先行台数テーブルを参照することにより選択リンクの終端ノードNbにおける先行車両の台数を予測し、その台数を選択リンクにおける加減速回数として決定する。たとえば自道路である選択リンクが国道であり、終端ノードNbで選択リンクと交差する道路が県道である場合、図15の先行台数テーブルから加減速回数は5回と決定される。ステップS310において、制御部10は、選択リンクの始端ノードNaにおける自車両の停止確率Paを決定する。ここでは、図4のステップS210と同様の方法を用いて停止確率Paを決定することができる。ステップS320において、制御部10は、HDD13に予め記憶された徐行走行テーブルを参照し、選択リンクにおける自車両の加速度Gおよび一定走行速度Vconstを決定する。徐行走行テーブルとは、ナビゲーション装置1がこれまでに学習した自車両の徐行走行時における前進距離と加速度および走行速度との関係をテーブル化して表したものである。すなわち、HDD13には、自車両の過去の走行履歴に基づく徐行走行時の前進距離に応じた学習加速度および学習走行速度を表すルックアップテーブル情報が徐行走行テーブルとして記録されている。図16に徐行走行テーブルの例を示す。図16の徐行走行テーブルでは、前進距離が1~30m、31~60m、61~90m、91~120m、121m以上に分類されており、その各前進距離に対して、自車両の徐行走行時における学習加速度および学習走行速度がそれぞれ設定されている。ステップS320では、この徐行走行テーブルを参照することにより、選択リンクにおける自車両の加速度Gおよび一定走行速度Vconstを決定する。たとえば、一時停止交差点で自車両が停止しているときの先行車両一台当たりの停止占有長車間を含む先行車両一台当たりの長さをLcarとする。このLcarを前進距離として図16の徐行走行テーブルを参照することにより、選択リンクにおける自車両の加速度Gおよび一定走行速度VconstをステップS320において決定することができる。たとえば停止占有長Lcarを7mとすると、図16の徐行走行テーブルから、選択リンクにおける加速度Gは2.5km/h/s、一定走行速度Vconstは10km/sとそれぞれ決定される。なお、ナビゲーション装置1は、自車両が停止状態から加速して所定値以下の一定走行速度で所定距離以上を走行したときに徐行走行中であると判定し、そのときの前進距離、加速度および一定走行速度を学習情報として記憶する。こうして自車両が徐行走行するたびに記憶された学習情報に基づいて、徐行走行中の加速度および走行速度を前進距離ごとに分類して統計的処理を行うことにより、図16のような徐行走行テーブルが求められ、HDD13において記憶される。ステップS330において、制御部10は、ステップS320で決定した加速度Gに基づいて、自車両が徐行走行時に停止状態から加速し、加速後すぐに減速して停止する場合の加減速時の最大走行速度Vmaxを算出する。この場合の一回の加減速の予測走行パターンの例を図17aに示す。図17aに示す予測走行パターンにおいて、自車両の走行速度が0から最大走行速度Vmaxに達するまでの加速時間と、最大走行速度Vmaxから0に達するまでの減速時間とは、いずれもVmax/Gにより表すことができる。したがって、一回の加減速当たりの走行距離はVmax2/Gと表すことができる。この走行距離が前述の停止占有長Lcarと等しいことから、以下の式12が成り立つ。12式12から、加減速時の最大走行速度Vmaxが以下の式13のように求められる。13ステップS340において、制御部10は、ステップS320で決定した一定走行速度Vconstと、ステップS330で算出した加減速時の最大走行速度Vmaxとを比較し、Vmax≦Vconstであるか否かを判定する。Vmax≦Vconstである場合はステップS350へ進み、Vmax≦Vconstでない場合、すなわちVmax>Vconstである場合はステップS360へ進む。ステップS350において、制御部10は、ステップS330で算出した加減速時の最大走行速度Vmaxに基づく走行パターン、すなわち図17aのような走行パターンを選択リンクにおける一回の加減速の予測走行パターンとして採用する。ステップS350を実行したら、制御部10はステップS380へ進む。ステップS360において、制御部10は、自車両が一回の加減速において一定走行速度Vconstまで加速してから減速を開始するまでの間の時間を一回の加減速における一定速走行時間T ́constとして算出する。この場合の一回の加減速の予測走行パターンの例を図17bに示す。図17bに示す予測走行パターンにおいて、自車両の走行速度が0から一定走行速度Vconstに達するまでの加速時間と、一定走行速度Vconstから0に達するまでの減速時間とは、ステップS320で決定した加速度Gと一定走行速度Vconstを用いて、いずれもVconst/Gにより表すことができる。したがって、一回の加減速当たりの走行距離はT ́const×VconstVconst2/Gと表すことができる。この走行距離が前述の停止占有長Lcarと等しいことから、以下の式14が成り立つ。14式14から、一回の加減速における一定速走行時間T ́constが以下の式15のように求められる。15ステップS370において、制御部10は、ステップS320で決定した一定走行速度Vconstに基づく走行パターン、すなわち図17bのような走行パターンを選択リンクにおける一回の加減速の予測走行パターンとして採用する。なお、図17bにおける一定速走行時間T ́constは、ステップS360において式15により求められたものである。ステップS370を実行したら、制御部10はステップS380へ進む。ステップS380において、制御部10は、ステップS300で決定した加減速回数と、ステップS350またはS370で採用した一回の加減速の予測走行パターンとに基づいて、選択リンクにおける自車両の予測走行パターンを決定する。ここでは、自車両が選択リンクを所定の走行速度で走行した後、選択リンクの終端ノードNbに到達するまで、ステップS300で決定した加減速回数だけ一回の加減速の予測走行パターンが繰り返される走行パターンを選択リンクにおける自車両の予測走行パターンとして決定する。すなわち、ステップS350を実行した場合は、ステップS330で算出した加減速時の最大走行速度Vmaxに基づいて自車両の走行パターンを予測する。一方、ステップS370を実行した場合は、ステップS320で決定した一定走行速度Vconstに基づいて自車両の走行パターンを予測する。さらに、ステップS310で決定した選択リンクの始端ノードNaにおける自車両の停止確率Paに基づいて、自車両が始端ノードNaで停止する場合の走行パターンと、始端ノードNaで停止しない場合の走行パターンとを、図4のステップS250で行ったのと同様にして、それぞれの発生確率に応じた割合で重畳する。ここで、前者の走行パターンの発生確率は停止確率Paと等しい。また、停止確率Paを百分率ではない確率値、すなわち1を基準とした確率値で表すと、後者の走行パターンの発生確率は1-Paと表すことができる。すなわち、停止確率Paに応じた割合で二つの走行パターンが重畳される。ステップS380を実行したら、制御部10は図5のフローチャートを終了して図3のフローチャートに戻る。以上説明したようにして、順調時の一時停止走行パターン予測処理が実行される。上述した順調時の一時停止走行パターン予測処理によって得られる予測走行パターンの例を図18に示す。図18の予測走行パターンでは、先行台数テーブルから決定された加減速回数が3であり、これに応じて図17aに示したような加減速時の最大走行速度Vmaxに基づく走行パターンを3回繰り返した予測走行パターンの例を示している。なお、時刻Taから時刻Tbの間に破線で示した部分は、自車両が始端ノードNaで停止する場合の走行パターンと停止しない場合の走行パターンとが停止確率Paに応じて重ね合わせられていることを表している。次に、図3のステップS90において実行される順調時の通過走行パターン予測処理の具体的な内容について説明する。図6は、順調時の通過走行パターン予測処理のフローチャートである。以下では、図19に示すような始端ノードNa、終端ノードNbの選択リンクを例として、図6のフローチャートの各処理について説明する。ステップS400において、制御部10は、選択リンクの始端ノードNaが信号機交差点または一時停止交差点であるか否かを判定する。始端ノードNaが信号機交差点または一時停止交差点である場合はステップS410へ進み、信号機交差点でも一時停止交差点でもない場合はステップS460へ進む。ステップS410において、制御部10は、選択リンクの始端ノードNaにおける自車両の停止確率Paを決定する。ここでは、図4のステップS210や図5のステップS310と同様の方法を用いて停止確率Paを決定することができる。ステップS420において、制御部10は、ステップS410で決定した停止確率Paに基づいて、選択リンクにおける各シナリオの発生確率をそれぞれ算出する。ここでは、自車両が始端ノードNaで停止しない場合に相当する図11aのシナリオ1と、自車両が始端ノードNaで停止する場合に相当する図11cのシナリオ3とについて、停止確率Paに基づく発生確率をそれぞれ算出する。これは、前述の式1において終端ノードNbの停止確率Pbを0とした場合の発生確率P1、P3として求められる。すなわち、P1=1-Pa、P3=Paである。ステップS430において、制御部10は、ステップS420で算出した各シナリオの発生確率P1、P3に基づいて、自車両の一定走行速度Vconstを算出する。ここでは図4のステップS230と同様に、前述の式8を用いて一定走行速度Vconstを算出することができる。このとき、式8におけるPの値は、式9においてP2=P4=0、Pb=0とすることにより求められる。すなわち、P=P3=Paである。ステップS440において、制御部10は、ステップS430で算出した一定走行速度Vconstに基づいて、自車両が選択リンクを一定走行速度Vconstで走行する距離と時間をそれぞれ表す一定速走行距離Lconstおよび一定速走行時間Tconstを算出する。ここでは図4のステップS240と同様に、前述の式10、11を用いることにより、一定速走行距離Lconstと一定速走行時間Tconstをそれぞれ算出することができる。ステップS450において、制御部10は、ステップS430で算出した一定走行速度Vconstと、ステップS440で算出した一定速走行距離Lconstおよび一定速走行時間Tconstとに基づいて、選択リンクにおける自車両の予測走行パターンを決定する。ここでは図4のステップS250と同様に、一定走行速度Vconst、一定速走行距離Lconstおよび一定速走行時間Tconstによって特定されるシナリオ1、3の各走行パターンをその発生確率P1、P3に応じた割合で重畳することにより、選択リンクにおける自車両の予測走行パターンを決定する。すなわち、選択リンクの始端ノードNaから終端ノードNbまで一定の走行速度であるシナリオ1の走行パターンと、加速度Gで上昇した後に一定走行速度Vconstとなるシナリオ3の走行パターンとを、選択リンクの始端ノードNaにおける停止確率Paに応じた割合で重畳する。このようにして選択リンクの走行パターンを予測する。ステップS460において、制御部10は、自車両の一定走行速度Vconstを算出する。この場合、自車両は選択リンクの始端ノードNaで停止することなく、始端ノードNaから終端ノードNbまでの間を一定走行速度Vconstで走行する。したがって、このときの一定走行速度Vconstは、選択リンクのリンク長Lとリンク旅行時間Tとを用いて以下の式16により求められる。16ステップS470において、制御部10は、ステップS460で算出した一定走行速度Vconstに基づいて、選択リンクにおける自車両の予測走行パターンを決定する。ここでは、始端ノードNaから終端ノードNbまで一定走行速度Vconstの走行パターンを選択リンクの予測走行パターンとして決定する。ステップS450またはS470を実行したら、制御部10は図6のフローチャートを終了して図3のフローチャートに戻る。以上説明したようにして、順調時の通過走行パターン予測処理が実行される。上述した順調時の通過走行パターン予測処理によって得られる予測走行パターンの例を図20、21および22に示す。図20は、選択リンク始端が信号機交差点である場合の予測走行パターンの例を示している。この予測走行パターンにおいて、時刻Taから時刻Tbの間に破線で示した部分は、自車両が始端ノードNaで停止する場合の走行パターンと停止しない場合の走行パターンとが停止確率Paに応じて重ね合わせられていることを表している。なお、このような予測走行パターンは、図6のステップS450において決定されるものである。図21は、選択リンク始端が一時停止交差点である場合の予測走行パターンの例を示している。この場合、自車両が一時停止交差点である始端ノードNaで必ず停止するため、時刻Taにおける走行速度は0であり、そこから一定走行速度Vconstに達するまで加速していく。一定走行速度Vconstに達したら、その走行速度をそのまま時刻Taまで維持する。なお、このような予測走行パターンは、図6のステップS450において始端ノードNaの停止確率Paが1100である場合の予測走行パターンとして決定されるものである。図22は、選択リンク始端が信号機交差点でも一時停止交差点でもない場合の予測走行パターンの例を示している。この場合、自車両が始端ノードNaで停止しないため、始端ノードNaから終端ノードNbまで一定走行速度Vconstが維持される。なお、このような予測走行パターンは、図6のステップS470において決定されるものである。次に、図3のステップS100において渋滞の先頭を推定する方法について説明する。図23は、渋滞の先頭を推定する方法を説明するための図である。図23において、ノード22とノード23の間にあるリンクが渋滞しており、その先のノード23とノード24の間にあるリンクが順調である。したがって、ノード21、22および23の間にある各リンクが選択リンクである場合、渋滞の先頭はノード23であると推定される。次に、ノード24とノード25の間にあるリンクが渋滞している。ここでノード25から先は、ノード26へ向かうリンクと、ノード30へ向かうリンクと、ノード32へ向かうリンクとに分岐している。このような場合、分岐先の各リンクを渋滞がなくなるまで辿っていき、最終的な渋滞の長さが最も長くなる分岐先において渋滞または混雑から順調に切り替わるノードを渋滞の先頭と推定する。すなわち、ノード24とノード25の間にあるリンクが選択リンクである場合、渋滞の先頭はノード28であると推定される。なお、ノード25、26、27および28の間にある各リンクが選択リンクである場合も、渋滞の先頭はノード28であると推定される。一方、ノード25からノード30へ向かうリンクが選択リンクである場合、当該リンクは混雑しており、ノード30とノード31の間にあるリンクが順調である。したがって、渋滞の先頭はノード30であると推定される。また、ノード25からノード32へ向かうリンクが選択リンクである場合は、当該リンクおよびノード32とノード33の間にあるリンクが渋滞しており、ノード33とノード34の間にあるリンクが順調である。したがって、渋滞の先頭はノード33であると推定される。ノード32とノード33の間にあるリンクが選択リンクである場合も同様に、渋滞の先頭はノード33であると推定される。以上説明したようにして、渋滞の先頭に当たる渋滞先頭ノードが推定される。図3のステップS120における渋滞時の信号機走行パターン予測処理や、ステップS140における渋滞時の一時停止走行パターン予測処理では、こうして推定された渋滞先頭ノードが対象交差点とされる。次に、図3のステップS120において実行される渋滞時の信号機走行パターン予測処理の具体的な内容について説明する。図7は、渋滞時の信号機走行パターン予測処理のフローチャートである。以下では、図24に示すような始端ノードNa、終端ノードNbの選択リンクを例として、図7のフローチャートの各処理について説明する。なお、図9に例示した順調時の信号機走行パターン予測処理における選択リンクの場合とは異なり、図24において終端ノードNbは信号機交差点とは限らない。ステップS500において、制御部10は、HDD13に予め記憶された青信号時間テーブルを参照し、対象交差点に当たる渋滞先頭ノードにおいて信号機が青信号となるときの一回当たりの青信号時間Tadvを決定する。青信号時間テーブルとは、様々な信号機交差点について青信号一回当たりの時間を道路種別に応じてテーブル化したものである。すなわち、HDD13には、交差点において互いに交差する道路の道路種別の組合せに応じた青信号時間を表すルックアップテーブル情報が青信号時間テーブルとして記録されている。図25に青信号時間テーブルの例を示す。図25の青信号時間テーブルでは、自道路と交差道路の道路種別が国道、県道、その他の道路種別にそれぞれ分類されており、その各道路種別同士の組合せに対して、青信号一回当たりの時間がそれぞれ設定されている。ステップS500では、この青信号時間テーブルを参照することにより、渋滞先頭ノードにおける青信号時間Tadvが決定される。このとき、渋滞先頭ノードを終端ノードとするリンクが自道路とされ、その自道路と渋滞先頭ノードで交差する道路が交差道路とされる。たとえば自道路が国道、交差道路が県道である場合、図25の青信号時間テーブルから渋滞先頭ノードの青信号時間Tadvは100秒と決定される。なお、道路の交通量や時間帯などに応じて青信号一回当たりの時間が変化する信号機の場合、その変化に対応して異なる青信号時間テーブルを参照するようにしてもよい。このようにすれば、適切な青信号時間Tadvとすることができる。ステップS510において、制御部10は、ステップS500で青信号時間テーブルから決定した青信号時間Tadvに基づいて、選択リンクにおける加減速回数を決定する。ここでは、以下のようにして加減速回数を決定することができる。渋滞時において一回の青信号の間に自車両が前進する距離Ladvは、上記の青信号時間Tadvと、単位時間当たりに青信号を通過する車両の台数を表す通過台数Ncarおよび前述の停止占有長Lcarとを用いて、以下の式17により表すことができる。17式17において、通過台数Ncarおよび停止占有長Lcarは予め設定されている値をそれぞれ用いることができる。この値は固定値であってもよいし、渋滞の度合いや道路種別などに応じて変化させてもよい。選択リンクにおける加減速回数をNadvとすると、式17により、この加減速回数Nadvは以下の式18のように求められる。なお、式18において、Lは選択リンクのリンク長を表す。また、式18の括弧はガウス記号であり、その括弧内の数値を超えない最大の整数を表している。18ステップS510では、以上説明したような計算方法により選択リンクにおける加減速回数Nadvを算出することができる。ステップS520において、制御部10は、HDD13に予め記憶された徐行走行テーブルを参照し、選択リンクにおける自車両の加速度Gを決定する。この徐行走行テーブルは、図5のステップS320で参照されるのと同じものであり、図16に例示したように、ナビゲーション装置1がこれまでに学習した自車両の徐行走行時における前進距離と加速度および走行速度との関係をテーブル化して表している。ここでは、上記式17で求められる前進距離Ladvに対応する加速度の欄を徐行走行テーブルにおいて参照することにより、選択リンクにおける自車両の加速度Gを決定する。なお、このとき加速度の欄のみを参照すれば十分であり、走行速度の欄については参照する必要はない。続くステップS530において、制御部10は、ステップS500で決定した青信号時間Tadv、ステップS520で決定した加速度G、停止占有長Lcarおよび車両通過台数Ncarに基づいて、選択リンクにおける自車両の一定走行速度Vconstを算出する。ここでは、図26に例示するような青信号一回当たりの加減速の予測走行パターンを用いて、以下の計算方法により一定走行速度Vconstを算出する。図26に示す一回の加減速の予測走行パターンにおいて、自車両の走行速度が0から一定走行速度Vconstに達するまでの加速時間と、一定走行速度Vconstから0に達するまでの減速時間とは、加速度Gを用いて、いずれもVconst/Gにより表すことができる。これらの加速時間および減速時間を青信号時間Tadvから差し引いた時間が、一回の青信号において自車両が一定走行速度Vconstで走行する時間であることから、一回の加減速当たりの走行距離はTadv-Vconst/G×Vconstと表すことができる。この走行距離が式17で表される前進距離Ladvと等しいことから、以下の式19が成り立つ。19式19を変形することにより、以下の二次方程式20が得られる。20二次方程式20を解くことにより、一定走行速度Vconstが以下の式21のように求められる。21ステップS530では、以上説明したような計算方法により一定走行速度Vconstを算出することができる。ステップS540において、制御部10は、ステップS530で算出した一定走行速度Vconstと、ステップS510で算出した加減速回数Nadvとに基づいて、自車両が選択リンクを一定走行速度Vconstで走行する距離と時間をそれぞれ表す一定速走行距離Lconstおよび一定速走行時間Tconstを算出する。ここでは、以下の式22、23を用いることにより、一定速走行距離Lconstと一定速走行時間Tconstをそれぞれ算出することができる。2223なお、式22、23で表される一定速走行距離Lconstと一定速走行時間Tconstは、自車両が加減速を繰り返しながら選択リンクを走行するときに一定走行速度Vconstとなる走行距離および走行時間の各合計値を表している。すなわち、式22で表される一定速走行距離Lconstと、式23で表される一定速走行時間Tconstとを加減速回数Nadvでそれぞれ除算することで、一回の加減速当たりの走行距離および走行時間を求めることができる。ステップS550において、制御部10は、ステップS530で算出した一定走行速度Vconstと、ステップS540で算出した一定速走行距離Lconstおよび一定速走行時間Tconstとに基づいて、選択リンクにおける自車両の予測走行パターンを決定する。ここでは、選択リンクの始端ノードNaから終端ノードNbに到達するまで、自車両がステップS510で算出した加減速回数Nadvだけ図26のような一回の加減速の予測走行パターンが繰り返される走行パターンを選択リンクにおける自車両の予測走行パターンとして決定する。ステップS560において、制御部10は、選択リンクの始端ノードNaから対象交差点である渋滞先頭ノードまでの距離が所定のしきい値D1以上であるか否かを判定する。このしきい値D1は、渋滞の先頭における車両の加減速の動きに対して選択リンクを走行している自車両が追従しなくなる距離を表しており、たとえば300mなどの値が予め設定される。選択リンクの始端ノードNaから渋滞先頭ノードまでの距離がしきい値D1以上である場合はステップS570へ進む。ステップS570において、制御部10は、ステップS550で決定した予測走行パターンに対して波形なまり処理を行う。この波形なまり処理では、ステップS550で決定した予測走行パターンの変動幅を所定量、たとえば20だけ低減する。すなわち、予測走行パターンにおける走行速度の下限値を0、上限値を100としたときに、そこから上下10の各範囲に含まれる波形部分をカットし、それ以上走行速度が変化しないように制限する。このようにすることで、自車両から渋滞先頭までの距離がある程度離れているときに、渋滞先頭における先行車両の加減速の動きに自車両が十分に追従しなくなることで生じる走行速度のなまり、すなわち変動幅の低減を予測走行パターンにおいて再現する。なお、ステップS570の波形なまり処理は必要に応じて行えばよく、不要であれば省略しても構わない。ステップS570を実行したら、制御部10は図7のフローチャートを終了して図3のフローチャートに戻る。なお、ステップS560において選択リンクの始端ノードNaから渋滞先頭ノードまでの距離がしきい値D1未満であると判定された場合は、ステップS570を実行せずに図7のフローチャートを終了する。以上説明したようにして、渋滞時の信号機走行パターン予測処理が実行される。上述した渋滞時の信号機走行パターン予測処理によって得られる予測走行パターンの例を図27に示す。図27の予測走行パターンでは、ステップS510で算出された加減速回数が3であり、これに応じて図26に示したような一回の加減速の走行パターンを3回繰り返した予測走行パターンの例を示している。なお、時刻Taから時刻Tbまでの時間は、選択リンクのリンク旅行時間Tである。そのため、一回の加減速の各走行パターンをリンク旅行時間Tの範囲内において均等に割り振って配置することで、図27のような予測走行パターンを得ることができる。次に、図3のステップS140において実行される渋滞時の一時停止走行パターン予測処理の具体的な内容について説明する。図8は、渋滞時の一時停止走行パターン予測処理のフローチャートである。以下では、前述した渋滞時の信号機走行パターン予測処理と同じく、図24に示すような始端ノードNa、終端ノードNbの選択リンクを例として、図8のフローチャートの各処理について説明する。なお、図14に例示した順調時の一時停止走行パターン予測処理における選択リンクの場合とは異なり、図24において終端ノードNbは一時停止交差点とは限らない。ステップS600において、制御部10は、選択リンクにおける加減速回数を決定する。ここでは、順調時の一時停止走行パターン予測処理において図5のステップS300で加減速回数を決定した場合とは異なり、先行台数テーブルを参照せずに加減速台数を決定する。具体的には、以下のようにして加減速回数を決定することができる。一時停止交差点を先頭とする渋滞が発生している場合、その一時停止交差点から選択リンクまでの間には多数の車両が連なっており、各車両は一時停止交差点の手前で必ず一時停止してからその交差点を通過すると考えられる。したがって、選択リンクにおける加減速回数をNadvとすると、この加減速回数Nadvは以下の式24のように求められる。なお、式24において、L、Lcarは前述のように選択リンクのリンク長と停止占有長をそれぞれ表す。また、式24の括弧はガウス記号であり、その括弧内の数値を超えない最大の整数を表している。24ステップS600では、以上説明したような計算方法により選択リンクにおける加減速回数Nadvを算出することができる。ステップS610において、制御部10は、HDD13に予め記憶された徐行走行テーブルを参照し、選択リンクにおける自車両の加速度Gおよび一定走行速度Vconstを決定する。この徐行走行テーブルは、図5のステップS320や図7のステップS520で参照されるのと同じものであり、図16に例示したように、ナビゲーション装置1がこれまでに学習した自車両の徐行走行時における前進距離と加速度および走行速度との関係をテーブル化して表している。ここでは、図5のステップS320の場合と同様に、停止占有長Lcarを前進距離として徐行走行テーブルを参照することにより、選択リンクにおける自車両の加速度Gおよび一定走行速度Vconsを決定する。ステップS620において、制御部10は、ステップS610で決定した加速度Gに基づいて、自車両が徐行走行時に停止状態から加速し、加速後すぐに減速して停止する場合の加減速時の最大走行速度Vmaxを算出する。ここでは、図5のステップS330で行ったのと同様の方法により、図17aに示したような予測走行パターンにおいて前述の式13で与えられる最大走行速度Vmaxを算出する。ステップS630において、制御部10は、図5のステップS340と同様に、ステップS610で決定した一定走行速度Vconstと、ステップS620で算出した加減速時の最大走行速度Vmaxとを比較し、Vmax≦Vconstであるか否かを判定する。Vmax≦Vconstの場合はステップS640へ進み、Vmax≦Vconstでない場合、すなわちVmax>Vconstである場合はステップS650へ進む。ステップS640において、制御部10は、図5のステップS350と同様に、ステップS620で算出した加減速時の最大走行速度Vmaxに基づく図17aのような走行パターンを、選択リンクにおける一回の加減速の予測走行パターンとして採用する。ステップS640を実行したら、制御部10はステップS670へ進む。ステップS650において、制御部10は、ステップS610で決定した加速度Gおよび一定走行速度Vconstに基づいて、一回の加減速の一定速走行時間T ́constを算出する。ここでは、図5のステップS360で行ったのと同様の方法により、図17bに示したような予測走行パターンにおいて前述の式15で与えられる一定速走行時間T ́constを算出する。ステップS660において、制御部10は、図5のステップS370と同様に、ステップS610で決定した一定走行速度Vconstに基づく図17bのような走行パターンを、選択リンクにおける一回の加減速の予測走行パターンとして採用する。ステップS660を実行したら、制御部10はステップS670へ進む。ステップS670において、制御部10は、ステップS600で決定した加減速回数と、ステップS640またはS660で採用した一回の加減速の予測走行パターンとに基づいて、選択リンクにおける自車両の予測走行パターンを決定する。ここでは図5のステップS380と同様に、自車両が選択リンクを所定の走行速度で走行した後、選択リンクの終端ノードNbに到達するまで、ステップS600で決定した加減速回数だけ一回の加減速の予測走行パターンが繰り返される走行パターンを選択リンクにおける自車両の予測走行パターンとして決定する。すなわち、ステップS640を実行した場合は、ステップS620で算出した加減速時の最大走行速度Vmaxに基づいて自車両の走行パターンを予測する。一方、ステップS660を実行した場合は、ステップS610で決定した一定走行速度Vconstに基づいて自車両の走行パターンを予測する。なお、上記のステップS670では、図5のステップS380の場合とは異なり、選択リンクの始端ノードNaで自車両が必ず停止するものとして扱う。すなわち、前述のような始端ノードNaの停止確率Paに応じた走行パターンの重ね合わせは行わずに、予測走行パターンを決定する。ステップS680において、制御部10は、図7のステップS560と同様に、選択リンクの始端ノードNaから対象交差点である渋滞先頭ノードまでの距離が所定のしきい値D2以上であるか否かを判定する。このしきい値D2は、前述のしきい値D1と同じ値であってもよいし、異なる値としてもよい。選択リンクの始端ノードNaから渋滞先頭ノードまでの距離がしきい値D2以上である場合はステップS690へ進む。ステップS690において、制御部10は、ステップS670で決定した予測走行パターンに対して、図7のステップS570と同様の波形なまり処理を行う。なお、この波形なまり処理も図7の場合と同様に必要に応じて行えばよく、不要であれば省略しても構わない。ステップS690を実行したら、制御部10は図8のフローチャートを終了して図3のフローチャートに戻る。なお、ステップS680において選択リンクの始端ノードNaから渋滞先頭ノードまでの距離がしきい値D2未満であると判定された場合は、ステップS690を実行せずに図8のフローチャートを終了する。以上説明したようにして、渋滞時の一時停止走行パターン予測処理が実行される。上述した渋滞時の一時停止走行パターン予測処理によって得られる予測走行パターンの例を図28に示す。図28の予測走行パターンでは、ステップS600で算出された加減速回数が5であり、これに応じて図17aに示したような一回の加減速の走行パターンを5回繰り返した予測走行パターンの例を示している。なお、時刻Taから時刻Tbまでの時間は、選択リンクのリンク旅行時間Tである。そのため、一回の加減速の各走行パターンをリンク旅行時間Tの範囲内において均等に割り振って配置することで、図28のような予測走行パターンを得ることができる。なお、図28では、図8のステップS630においてVmax≦Vconstと判定され、それに応じてステップS640が実行されることにより、図17aのような加減速時の最大走行速度Vmaxに基づく走行パターンを採用した場合の予測走行パターンの例を示している。しかし、ステップS630においてVmax>Vconstであると判定され、それに応じてステップS660が実行された場合は、図17bのような一定走行速度Vconstに基づく走行パターンが採用されることにより、図28とは異なる形状の予測走行パターンが得られる。すなわち、図27に示したように、自車両の速度が0から一定走行速度Vconstの間で周期的に変化する予測走行パターンが得られる。以上説明したような処理を対象リンクとして抽出された各リンクに対してそれぞれ行い、得られた予測走行パターンを各リンクの並び順序に応じてそれぞれ繋ぎ合わせることにより、対象リンク全体の予測走行パターンが得られる。こうして得られた対象リンク全体の予測走行パターンの例を図29に示す。図29では、ノード41~49の間にある各リンクを対象リンクとして得られた予測走行パターンの例を示している。図29において、ノード42、43、45~49は信号機交差点であり、ノード44は一時停止交差点である。また、ノード41~43間とノード44~46間は順調であり、ノード46~47間は混雑している。ノード43~44間とノード47~49間は渋滞しており、ノード44、49はそれぞれ渋滞の先頭であると推定される。このような条件下で前述のような走行パターン予測処理が行われることにより、たとえば図29に示すような走行パターンが推定され、これに基づいて各リンクでの推定消費エネルギー値が求められる。以上説明した実施の形態によれば、次のような作用効果を奏することができる。1ナビゲーション装置1は、制御部10の処理により、道路網を構成する複数のリンクからいずれかのリンクを選択リンクとして選択しステップS20、その選択リンクの前方に存在する交差点のいずれかを対象交差点として、順調時の信号機走行パターン予測処理ステップS60、順調時の一時停止走行パターン予測処理ステップS80、順調時の通過走行パターン予測処理ステップS90、渋滞時の信号機走行パターン予測処理ステップS120、または渋滞時の一時停止走行パターン予測処理ステップS140を実行する。あるいは、予め設定されたデフォルト走行パターンを選択リンクの走行パターンとして適用するステップS150。これにより、選択リンクの道路状況および対象交差点の種類に応じた走行パターンを選択リンクにおける車両の走行パターンとして予測する。このようにしたので、道路状況や交差点における信号機の有無等を考慮して、車両の走行パターンを正確に予測することができる。2制御部10は、選択リンクの道路状況が順調であり、かつ対象交差点が信号機の設置されている信号機交差点である場合、ステップS60において順調時の信号機走行パターン予測処理を実行する。この順調時の信号機走行パターン予測処理では、対象交差点に当たる選択リンクの終端ノードNbにおける停止確率Pbと選択リンクの始端ノードNaにおける停止確率Paとに基づいて、選択リンクの走行パターンを予測する。このようにしたので、選択リンクの道路状況が順調であり、かつ対象交差点が信号機の設置されている信号機交差点である場合の車両の走行パターンを正確に予測することができる。3ナビゲーション装置1のHDD13には、交差点において互いに交差する道路の道路種別の組み合わせに応じた停止確率を表す赤信号停止確率テーブルが予め記憶されている。制御部10は、順調時の信号機走行パターン予測処理において、HDD13に記憶されている赤信号停止確率テーブルを参照し、これに基づいて対象交差点である選択リンクの終端ノードNbにおける停止確率Pbを決定するステップS200。これにより、対象交差点における停止確率をある程度正確に、かつ容易に決定することができる。4制御部10は、順調時の信号機走行パターン予測処理において、選択リンクの始端ノードNaと終端ノードNbのそれぞれにおいて自車両が停止する場合と停止しない場合に予測される各走行パターンを、選択リンクにおける各シナリオの発生確率としてそれぞれ算出するステップS220。すなわち、始端ノードNaおよび終端ノードNbの両方で停止しない第1の走行パターンと、始端ノードNaで停止せずに終端ノードNbで停止する第2の走行パターンと、始端ノードNaで停止して終端ノードNbで停止しない第3の走行パターンと、始端ノードNaおよび終端ノードNbの両方で停止する第4の走行パターンとについて、終端ノードNbにおける停止確率Pbと始端ノードNaにおける停止確率Paとに基づく発生確率をそれぞれ算出する。そして、第1の走行パターン、第2の走行パターン、第3の走行パターンおよび第4の走行パターンを、ステップS220で算出した各々の発生確率に応じた割合で重畳することにより、選択リンクの走行パターンを予測するステップS250ようにした。これにより、選択リンクの始端と終端のそれぞれにおける車両停止の有無を考慮して、選択リンクの走行パターンを正確に予測することができる。5制御部10は、選択リンクの道路状況が順調であり、かつ対象交差点が一時停止交差点である場合、ステップS80において順調時の一時停止走行パターン予測処理を実行する。この順調時の一時停止走行パターン予測処理では、対象交差点に当たる選択リンクの終端ノードNbにおいて一時停止する先行車両の台数に基づいて加減速回数を決定しステップS300、選択リンクの走行パターンを予測する。このようにしたので、選択リンクの道路状況が順調であり、かつ対象交差点が一時停止交差点である場合の車両の走行パターンを正確に予測することができる。6ナビゲーション装置1のHDD13には、交差点において互いに交差する道路の道路種別の組み合わせに応じた先行車両の台数を表す先行台数テーブルが予め記憶されている。制御部10は、順調時の一時停止走行パターン予測処理において、HDD13に記憶されている先行台数テーブルを参照し、これに基づいて対象交差点である選択リンクの終端ノードNbにおいて一時停止する先行車両の台数を決定することで、加減速回数を決定するステップS300。これにより、対象交差点における先行車両の台数から加減速回数をある程度正確に、かつ容易に決定することができる。7ナビゲーション装置1のHDD13には、これまでに学習した自車両の徐行走行時における前進距離と加速度および走行速度との関係をテーブル化して表した徐行走行テーブルが予め記憶されている。制御部10は、順調時の一時停止走行パターン予測処理において、HDD13に記憶されている徐行走行テーブルを参照し、これに基づいて選択リンクにおける自車両の加速度Gを決定するステップS320。このようにして、自車両の過去の走行履歴に基づいて選択リンクの走行パターンにおける加減速度を決定するようにしたので、自車両の走行特性や運転者の運転傾向などを反映して走行パターンを予測することができる。8制御部10は、順調時の一時停止走行パターン予測処理において、ステップS320で決定した加速度Gと、予め定められた車両一台当たりの停止占有長Lcarとに基づいて、選択リンクの走行パターンにおける加減速時の最大走行速度Vmaxを算出するステップS330。そして、算出した加減速時の最大走行速度Vmaxが所定の一定走行速度Vconst以下であるか否かを判定するステップS340。その結果、加減速時の最大走行速度Vmaxが一定走行速度Vconst以下である場合は、加減速時の最大走行速度Vmaxに基づく走行パターンを採用することで選択リンクの走行パターンを予測するステップS350。一方、加減速時の最大走行速度Vmaxが一定走行速度Vconstよりも大きい場合は、一定走行速度Vconstに基づく走行パターンを採用することで選択リンクの走行パターンを予測するステップS370。このようにしたので、自車両が先行車両に追随して一時停止と徐行を繰り返しながら対象交差点である一時停止交差点に向かって選択リンクを走行する状況を考慮して、走行パターンを正確に予測することができる。9制御部10は、順調時の一時停止走行パターン予測処理において、HDD13に記憶されている徐行走行テーブルを参照し、これに基づいて一定走行速度Vconstを決定するステップS320。このようにして、自車両の過去の走行履歴に基づいて一定走行速度Vconstを決定するようにしたので、自車両の走行特性や運転者の運転傾向などを走行パターンの予測に反映させることができる。10制御部10は、順調時の一時停止走行パターン予測処理において、選択リンクの始端ノードNaで停止しないときの走行パターンと、選択リンクの始端ノードNaで停止するときの走行パターンとを、選択リンクの始端ノードNaにおける停止確率Paに応じた割合で重畳することにより、選択リンクの走行パターンを予測するステップS380ようにした。これにより、選択リンクの始端における車両停止の有無を考慮して、選択リンクの走行パターンを正確に予測することができる。11制御部10は、選択リンクの道路状況が順調であり、かつ対象交差点が信号機の設置されている信号機交差点でも一時停止交差点でもない場合、ステップS90において順調時の通過走行パターン予測処理を実行する。この順調時の通過走行パターン予測処理では、選択リンクの始端ノードNaから終端ノードNbまで一定の走行速度による走行パターンを表すシナリオ1の走行パターンと、所定の加速度Gに応じて上昇した後に一定となる走行速度による走行パターンを表すシナリオ3の走行パターンとを、選択リンクの始端ノードNaにおける停止確率Paに応じた割合で重畳することにより、選択リンクの走行パターンを予測するステップS450、S470。このようにしたので、選択リンクの道路状況が順調であり、かつ対象交差点が信号機の設置されている信号機交差点でも一時停止交差点でもない場合の車両の走行パターンを正確に予測することができる。12制御部10は、ステップS60で順調時の信号機走行パターン予測処理を実行する場合、ステップS80で順調時の一時停止走行パターン予測処理を実行する場合、またはステップS90で順調時の通過走行パターン予測処理を実行する場合には、選択リンクの終端ノードNbに当たる交差点を対象交差点とするようにした。これにより、選択リンクの道路状況が順調である場合の走行パターンを予測するのに適切な交差点を対象交差点とすることができる。13制御部10は、選択リンクの道路状況が混雑または渋滞であり、かつ対象交差点が信号機の設置されている信号機交差点である場合、ステップS120において渋滞時の信号機走行パターン予測処理を実行する。この渋滞時の信号機走行パターン予測処理では、対象交差点に当たる渋滞の先頭ノードにおける青信号時間Tadvに基づいて加減速回数Nadvを算出しステップS510、選択リンクの走行パターンを予測する。このようにしたので、選択リンクの道路状況が混雑または渋滞であり、かつ対象交差点が信号機の設置されている信号機交差点である場合の車両の走行パターンを正確に予測することができる。14ナビゲーション装置1のHDD13には、交差点において互いに交差する道路の道路種別の組み合わせに応じた青信号時間を表す青信号時間テーブルが予め記憶されている。制御部10は、渋滞時の信号機走行パターン予測処理において、HDD13に記憶されている青信号時間テーブルを参照し、これに基づいて対象交差点である渋滞先頭ノードにおける青信号時間Tadvを決定するステップS500。これにより、対象交差点における青信号時間をある程度正確に、かつ容易に決定することができる。15制御部10は、渋滞時の信号機走行パターン予測処理において、HDD13に記憶されている徐行走行テーブルを参照し、これに基づいて選択リンクにおける自車両の加速度Gを決定するステップS520。このようにして、自車両の過去の走行履歴に基づいて選択リンクの走行パターンにおける加減速度を決定するようにしたので、自車両の走行特性や運転者の運転傾向などを反映して走行パターンを予測することができる。16制御部10は、渋滞時の信号機走行パターン予測処理において、ステップS500で決定した青信号時間Tadv、ステップS520で決定した加速度G、車両一台当たりの停止占有長Lcarおよび単位時間当たりの車両通過台数Ncarに基づいて、選択リンクの走行パターンにおける一定走行速度Vconstを算出するステップS530。このようにしたので、渋滞先頭ノードの信号機が青信号である間に、自車両が先行車両に追随して一時停止と徐行を繰り返しながら選択リンクを走行する状況を考慮して、走行パターンを正確に予測することができる。17制御部10は、選択リンクの道路状況が混雑または渋滞であり、かつ対象交差点が一時停止交差点である場合、ステップS140において渋滞時の一時停止走行パターン予測処理を実行する。この渋滞時の一時停止走行パターン予測処理では、選択リンクの長さを表すリンク長Lと予め定められた車両一台当たりの停止占有長Lcarとに基づいて加減速回数Nadvを算出しステップS600、選択リンクの走行パターンを予測する。このようにしたので、選択リンクの道路状況が混雑または渋滞であり、かつ対象交差点が一時停止交差点である場合の車両の走行パターンを正確に予測することができる。18制御部10は、渋滞時の一時停止走行パターン予測処理において、HDD13に記憶されている徐行走行テーブルを参照し、これに基づいて選択リンクにおける自車両の加速度Gを決定するステップS610。このようにして、自車両の過去の走行履歴に基づいて選択リンクの走行パターンにおける加減速度を決定するようにしたので、自車両の走行特性や運転者の運転傾向などを反映して走行パターンを予測することができる。19制御部10は、渋滞時の一時停止走行パターン予測処理において、ステップS610で決定した加速度Gと、予め定められた車両一台当たりの停止占有長Lcarとに基づいて、選択リンクの走行パターンにおける加減速時の最大走行速度Vmaxを算出するステップS620。そして、算出した加減速時の最大走行速度Vmaxが所定の一定走行速度Vconst以下であるか否かを判定するステップS630。その結果、加減速時の最大走行速度Vmaxが一定走行速度Vconst以下である場合は、加減速時の最大走行速度Vmaxに基づく走行パターンを採用することで選択リンクの走行パターンを予測するステップS640。一方、加減速時の最大走行速度Vmaxが一定走行速度Vconstよりも大きい場合は、一定走行速度Vconstに基づく走行パターンを採用することで選択リンクの走行パターンを予測するステップS660。このようにしたので、自車両が先行車両に追随して一時停止と徐行を繰り返しながら対象交差点である一時停止交差点に向かって選択リンクを走行する状況を考慮して、走行パターンを正確に予測することができる。20制御部10は、渋滞時の一時停止走行パターン予測処理において、HDD13に記憶されている徐行走行テーブルを参照し、これに基づいて一定走行速度Vconstを決定するステップS610。このようにして、自車両の過去の走行履歴に基づいて一定走行速度Vconstを決定するようにしたので、自車両の走行特性や運転者の運転傾向などを走行パターンの予測に反映させることができる。21制御部10は、ステップS120で渋滞時の信号機走行パターン予測処理を実行する場合、またはステップS140で渋滞時の一時停止走行パターン予測処理を実行する場合には、選択リンクが含まれている混雑または渋滞の先頭に当たる交差点を推定しステップS100、その交差点を対象交差点とするようにした。これにより、選択リンクの道路状況が混雑または渋滞である場合の走行パターンを予測するのに適切な交差点を対象交差点とすることができる。22制御部10は、ステップS120の渋滞時の信号機走行パターン予測処理、またはステップS140の渋滞時の一時停止走行パターン予測処理において、選択リンクの始端ノードNaから対象交差点である渋滞先頭ノードまでの距離が所定のしきい値D1またはD2以上であるか否かを判定するステップS560、S680。その結果、始端ノードNaから渋滞先頭ノードまでの距離がしきい値D1またはD2以上である場合は、走行パターンの変動幅を低減するためのなまり処理を行うS570、S690。このようにしたので、自車両から渋滞先頭までの距離がある程度離れているときに、渋滞先頭における先行車両の加減速の動きに自車両が十分に追従しなくなることで生じる走行速度のなまりを考慮して、走行パターンを予測することができる。なお、上記実施の形態では、走行パターン予測処理によって予測された走行パターンを最小燃費経路の探索などに利用するナビゲーション装置1での適用例を説明したが、ナビゲーション装置以外の車載装置において本発明を適用してもよい。あるいは、たとえばパーソナルコンピュータなど、車載装置以外の装置において本発明を適用することもできる。前述のような走行パターン予測処理を用いて任意の対象リンクにおける車両の走行パターンを予測できるものである限り、どのような装置についても本発明を適用可能である。以上説明した実施の形態や各種の変形例はあくまで一例であり、発明の特徴が損なわれない限り、本発明はこれらの内容に限定されるものではない。