(57)【特許請求の範囲】
【請求項１】
車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得部と、
道路地図を構成する複数のブロックの各々に含まれるノードの位置情報を記憶する地図情報記憶部と、
前記ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び／または転出ノードとして定め、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶部と、
個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成部と、
複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索部とを備え、
前記ブロック内情報記憶部は、ブロック内の隣接ノード間の移動確率を示す移動確率テーブルを備え、
前記ブロック内経路生成部は、前記移動確率テーブルに記憶された移動確率に基づき、前記転入ノードから前記転出ノードに至る最適経路を探索することを特徴とするナビゲーション装置。
【請求項２】
前記ブロック内情報記憶部は、前記転入ノードから前記転出ノードに至る経路のリンクコスト情報を、前記ブロック内経路情報と対応付けて記憶する最適経路テーブルを備えたことを特徴とする、請求項１記載のナビゲーション装置。
【請求項３】
前記ブロック内情報記憶部は、前記ブロック内のノード間における車両の存在量を示す指標としてのフェロモン量を示すフェロモン量テーブルと、前記ブロック内のノード間のリンクコストを示すリンクコストテーブルを備え、
前記ブロック内経路生成部は、所定時間毎に、前記フェロモン量テーブル及び／又は前記リンクコストテーブルを更新するとともに、前記ノード間の前記フェロモン量及び前記リンクコストに基づいて前記移動確率を更新することを特徴とする、請求項１記載のナビゲーション装置。
【請求項４】
前記車両の通過経路を示す前記転入ノード及び前記転出ノードの情報を記憶する経路情報記憶部と、前記ブロック内の経路状態が変動したことを示す変動情報を、前記転入ノード及び前記転出ノードの組合せ毎に記憶する変動情報記憶部と、経路状態が変動した前記転入ノード及び前記転出ノードの組合せを通過経路に含む前記車両に対して、経路検索を促す通知を発する通知判定部とを備えたことを特徴とする，請求項１記載のナビゲーション装置。
【請求項５】
前記変動情報は、前記転入ノードから前記転出ノードに至る最適経路が変更されたか否かを示す情報であることを特徴とする，請求項４記載のナビゲーション装置。
【請求項６】
前記全体経路探索部は、前記最適経路テーブルに記憶された前記転入ノードから前記転出ノードへの経路を１つのリンクとみなして、前記現在位置から前記目的地までの経路情報を生成することを特徴とする、請求項２に記載のナビゲーション装置。
【請求項７】
前記ブロックにおける最適経路情報を更新する前記ブロック内経路生成部を複数備えたことを特徴とする、請求項１ないし６のいずれか１項に記載のナビゲーション装置。
【請求項８】
道路地図を複数のブロックに分割するとともに、分割された各ブロック内における最適経路情報を生成する複数の経路生成装置と、前記経路生成装置と接続されたナビゲーション装置を有するナビゲーションシステムにおいて、
前記ナビゲーション装置は、
車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得部と、
道路地図を構成する複数のブロックの各々に含まれるノードの位置情報を記憶する地図情報記憶部と、
前記ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び／または転出ノードとして定め、前記転入ノードから前記転出ノードへの最適経路を示すブロック内最適経路情報を記憶する最適経路記憶部と、
複数のブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索部を備え、
前記経路生成装置は、
前記ブロックの各々について、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶部と、
個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成部とを備え、
前記ナビゲーション装置は、前記ブロック内経路生成部で探索された前記経路情報に基づき、前記ブロック内最適経路情報を更新することを特徴とするナビゲーションシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地までの経路を示す経路情報を提供するナビゲーション装置に関する。
【背景技術】
【０００２】
カーナビゲーションシステム等に用いられるナビゲーション装置では、出発地から目的地までの経路を探索する機能を備えている。経路探索の方法としては、経路ネットワークを構成するノードやリンクに対して重み係数（コストパラメータ）を設定し、目的地までの総コストが最小となるような経路を、例えばダイクストラ法によって決定する。コストパラメータとしては、例えば距離、道路種別、道幅、信号機の有無、右左折等のパラメータが用いられる。
【０００３】
また、特許文献１では、コストパラメータを記憶するコストテーブルを、所定地域ごとに個別に設定しておき、これらコストテーブルを用いて目的地までの経路コストを算出するナビゲーション装置が開示されている。
【０００４】
さらに、特許文献２では、複数のコストテーブルを備えておき、時間帯や平日／休日といった短期的に変化するパラメータに基づき、ベイジアンネットワークを用いて条件付確率が最も高いコストテーブルを選択することで、運転手の好みが反映された経路を探索することができるナビゲーションシステムが開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−１８１０６３号公報
【特許文献２】特開２００７−１０５７１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記特許文献に記載の技術では、車両の現在位置（起点）から目的地（終点）に至る全ての経路について経路探索を行うため、経路探索に時間がかかってしまうという問題があった。特に、車両に搭載されたナビゲーション装置から、地図データを記憶する記憶装置を省略し、経路探索の機能を車両に接続された中央サーバで一元的に行うことが、装置のコスト削減の観点から好ましいところ、上記特許文献に記載の技術では、多数の車両から同時に経路探索要求がなされた場合に、迅速に経路探索を行うことができなかった。
【０００７】
本発明は、上記事情に鑑みなされたものであり、経路探索を短時間で効率的に行うことができるナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明のナビゲーション装置は、車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得部と、道路地図を構成する複数のブロックの各々に含まれるノードの位置情報を記憶する地図情報記憶部と、前記ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び／または転出ノードとして定め、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶部と、個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成部と、複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索部とを備えた構成を有している。
【０００９】
この構成により、道路地図を分割したブロックの各々について最適経路を算出し、得られたブロック毎の最適経路情報を組み合わせることで、現在地から目的地に至る経路情報を抽出するようにしたから、経路探索に要する時間を短縮することができる。
【００１０】
本発明のナビゲーション装置において、ブロック内情報記憶部は、前記転入ノードから前記転出ノードに至る経路のリンクコスト情報を、前記ブロック内経路情報と対応付けて記憶する最適経路テーブルを備えている。これにより、道路種別や渋滞状況といったリンクコストを用いて、ブロック内の最適経路を探索することができるから、経路探索の向上を図ることができる。
【００１１】
本発明のナビゲーション装置において、ブロック内情報記憶部は、ブロック内の隣接ノード間の移動確率を示す移動確率テーブルを備え、前記ブロック内経路生成部は、前記移動確率テーブルに記憶された移動確率に基づき、前記転入ノードから前記転出ノードに至る最適経路を探索する。ブロック内のノード間のフェロモン量を示すフェロモン量テーブルと、前記ブロック内のノード間の前記リンクコストを示すリンクコストテーブルを備え、前記ブロック内経路生成部は、所定時間毎に、前記フェロモン量テーブル及び／又は前記リンクコストテーブルを更新するとともに、前記ノード間の前記フェロモン量及び前記リンクコストに基づいて前記移動確率を更新することが好ましい。これにより、移動確率の最も高いノードの組合せを最適経路として定めることができるから、最適な経路を効率よく抽出することができる。
【００１２】
本発明のナビゲーション装置において、全体経路探索部は、前記最適経路テーブルに記憶された前記転入ノードから前記転出ノードへの経路を１つのリンクとみなして、前記現在位置から前記目的地までの経路情報を生成する。これにより、ブロック毎に予め定められた最適経路を組み合わせることで、目的地までの経路を探索することができるから、経路探索を短時間で効率的に行うことができる。
【００１３】
本発明のナビゲーション装置において、前記車両の通過経路を示す前記転入ノード及び前記転出ノードの情報を記憶する経路情報記憶部と、前記ブロック内の経路状態が変動したことを示す変動情報を、前記転入ノード及び前記転出ノードの組合せ毎に記憶する変動情報記憶部と、経路状態が変動した前記転入ノード及び前記転出ノードの組合せを通過経路に含む前記車両に対して、経路検索を促す通知を発する通知判定部とを備えた構成を有する。通知を受けた車両において、ナビゲーション装置に対して経路再探索を要求することができる。この構成により、目的地までの全体の最適経路が変動した場合に、ナビゲーション装置から車両に通知を行うようにしたので、目的地までの走行経路のアップデートを効率よく行うことができる。また、ナビゲーション装置において不必要な経路検索が行われることがなくなるから、処理の効率化、通信コストの削減を図ることができる。ここで、前記変動情報は、前記転入ノードから前記転出ノードに至る最適経路が変更されたか否かを示す情報とすることが好ましく、これにより、各ブロックにおける最適経路が変動した場合に、最適経路の変更を車両に通知することができる。
【００１４】
本発明のナビゲーション装置は、前記ブロックにおける最適経路情報を更新する前記ブロック内経路生成部を複数備えた構成を有する。この構成により、複数のブロックにおける最適経路の探索を並列して行うことができるから、最適経路の抽出処理に要する時間を短縮することができる。
【００１５】
本発明のナビゲーション方法は、車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得ステップと、道路地図を構成する複数のブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び／または転出ノードとして定め、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶ステップと、個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成ステップと、複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索ステップを備えた構成を有する。この構成によっても、上記と同様に、道路地図を構成する各ブロックにおける最適経路を算出し、これらを組み合わせることで、現在地から目的地に至る経路情報を抽出するので、経路探索に要する時間を短縮することができる。
【００１６】
本発明のナビゲーションシステムは、道路地図を複数のブロックに分割するとともに、分割された各ブロック内における最適経路情報を生成する複数の経路生成装置と、前記経路生成装置と接続されたナビゲーション装置を備え、前記ナビゲーション装置は、車両の現在位置を示す位置情報と、目的地の位置を示す目的地情報を取得する情報取得部と、道路地図を構成する複数のブロックの各々に含まれるノードの位置情報を記憶する地図情報記憶部と、前記ブロックの各々について、隣接するブロックとの境界上のノードを転入ノード及び／または転出ノードとして定め、前記転入ノードから前記転出ノードへの最適経路を示すブロック内最適経路情報を記憶する最適経路記憶部と、複数の前記ブロック内経路情報を組み合わせて、前記現在位置から前記目的地までの経路情報を生成する全体経路探索部を備え、前記経路生成装置は、前記ブロックの各々について、前記転入ノードから前記転出ノードに至る経路を示すブロック内経路情報を記憶するブロック内情報記憶部と、個々の前記ブロックにおける、前記転入ノードから前記転出ノードに至る最適経路を探索し、探索された経路情報を前記ブロック内経路情報として更新するブロック内経路生成部とを備え、前記ナビゲーション装置は、前記ブロック内経路生成部で探索された前記経路情報に基づき、前記ブロック内最適経路情報を更新する。この構成によっても、上記と同様に、道路地図を構成する各ブロックにおける最適経路を算出し、これらを組み合わせることで、現在地から目的地に至る経路情報を抽出するので、経路探索に要する時間を短縮することができる。
【発明の効果】
【００１７】
本発明によれば、道路地図を複数のブロックに分割し、各ブロックにおける最適経路を算出するとともに、これら各ブロックの最適経路を組み合わせることで、現在地から目的地に至る経路情報を抽出するようにしたから、経路探索を短時間で効率的に行うことができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態に係るナビゲーション装置から車両に経路情報を送信する例を示すブロック図
【図２】本発明の実施形態に係るナビゲーション装置の構成を示すブロック図
【図３】道路地図を複数のブロックに分割した例を示す説明図
【図４】道路地図を構成するブロック内の経路図の一例を示す説明図
【図５】ブロック内情報記憶部のデータ構成の一例を示す説明図
【図６】隣接ノード間の位置関係と各パラメータを示す説明図
【図７】フェロモン量テーブルのデータ構成の一例を示す説明図
【図８】エージェント経路テーブルのデータ構成の一例を示す説明図
【図９】最適経路テーブルのデータ構成の一例を示す説明図
【図１０】あるエージェントによる走行経路の一例を示す説明図
【図１１】別のエージェントによる走行経路の一例を示す説明図
【図１２】探索された経路の一例を示す説明図
【図１３】ブロック内の各種テーブルの更新処理の一例を示すフローチャート
【図１４】車両の現在位置から目的地までの経路探索処理の一例を示すフローチャート
【図１５】本発明の別の実施形態に係るナビゲーションシステムの構成を示すブロック図
【図１６】本発明のさらに別の実施形態に係るナビゲーションシステムの構成を示すブロック図
【図１７】図１５のシステムを構成するナビゲーション装置と経路生成装置の構成を示すブロック図
【図１８】本発明のさらに別の実施形態に係るナビゲーションシステムの構成を示すブロック図
【図１９】渋滞の発生によりブロック内の最短経路が変更された様子を説明するための図
【図２０】ブロック内の変化フラグテーブルの一例を示す説明図
【図２１】経路情報記憶部の一例を示す説明図
【図２２】ナビゲーション装置の動作の一例を示すフローチャート
【発明を実施するための形態】
【００１９】
（第１実施形態）
以下、図面を参照して、本発明の第１実施形態に係るナビゲーション装置について説明する。図１において、本実施形態に係るナビゲーション装置１０は、道路上を走行する複数の車両１２と例えば無線通信回線によって接続されており、目的地までの経路要求を車両１２から受信したときに、後述する手順により目的地までの経路を探索し、経路情報として車両１２に対して送信する。また、ナビゲーション装置１０は、ＶＩＣＳ（登録商標）センター１４に接続されており、渋滞情報や交通規制情報等の各種の交通情報を受信する。
【００２０】
図２において、ナビゲーション装置１０は、通信部２０、地図ＤＢ２２、交通情報取得部２４、ブロック内情報記憶部２６、経路生成部２８、全体経路探索部３０を備えており、図示しない制御回路によりその動作が制御されている。
【００２１】
通信部２０は、例えばインターネット回線に接続可能な無線通信モジュールであり、車両１２から現在位置及び目的地の情報を含む経路要求を受信するとともに、経路要求を発した車両１２に経路情報を送信する。また、通信部２０は、ＶＩＣＳ（登録商標）センター１４からの交通情報を受信する受信手段を備える。なお、通信部２０は、例えば車両との間で公知の路車間通信を行う通信装置との間で、情報の送受信を行う無線通信モジュールを備えても良い。
【００２２】
地図ＤＢ２２は、道路地図を構成する各区間（リンク）の位置情報、各リンクの端点（ノード）の位置情報、ノード及びリンクのコストを示すコスト情報（例えば、距離、道路種別、道幅、渋滞の程度、交通規制の有無、信号機の有無、右左折等の情報）、道路上の施設情報などのデータを含む。この地図ＤＢ２２内の情報は、例えばＶＩＣＳ（登録商標）センター１４からの交通情報に基づき更新される。
【００２３】
図３に示すように、地図ＤＢ２２に含まれる道路地図４０は、複数のブロック４２に区分けされており、区分けされた各ブロックの境界位置を示す情報（例えば、境界上のノードの位置情報）を記憶している。なお、道路地図４０の分割方法としては、図３に示されているような格子形状に限られることはなく、例えば市区町村ごとに個別のブロックを形成しても良い。
【００２４】
図４は、図３の道路地図を構成する一つのブロック４４を拡大したものである。ブロック４４は、例えば、隣接するブロックとの境界上に設けられたノードＯ１〜Ｏ３，Ｄ１〜Ｄ３と、ブロック４４内のリンクの端点を示すノードＮ１〜Ｎ４とを有する。また、図４において、ブロック４４内の矢印４６は道路（リンク）を示している。なお、これらノード及びリンクの位置情報は、地図ＤＢ２２に記憶されている。
【００２５】
図４において、「Ｏ１」と示されているのは、当該ブロックに車両が入る際に通過するノード（転入ノード）であり、「Ｄ１」と示されているのは、当該ブロックから別のブロックに車両が出る際に通過するノード（転出ノード）である。図４の例では、ノードＯ１〜Ｏ３，Ｄ１〜Ｄ３を通過する道路を介して、隣接ブロックと接続されていることが示されている。これら転入ノードは、ブロックを構成する各辺ごとに定められている。すなわち、各ブロックを構成する上下左右の辺ごとに、転入ノード及び転出ノードが設けられており、図４ではブロックの左辺を転入ノードとする例が示されている。なお、ブロックの他辺を転入ノードとする例については、図４の例と同様であるため、説明を省略する。
【００２６】
なお、図４の例では、転入ノードＯ１〜Ｏ３及び転出ノードＤ１〜Ｄ３が３つずつ設けられているが、転入ノード及び転出ノードの数はこれに限定されることはなく、ブロックをまたぐ道路の数に応じて、転入及び転出ノードを定めることができる。また、図４の例では、ブロックの上辺及び下辺に転出ノードが設けられていないが、ブロックの上辺あるいは下辺を通過する道路が存在する場合には、転出ノードが設けられることはもちろんである。
【００２７】
図２において、交通情報取得部２４は、経路要求を発した車両１２の位置情報及び目的地情報を取得するとともに、地図ＤＢ２２に記憶された各ブロックの境界ノードの位置情報を参照して、当該車両１２及び目的地の場所に対応するブロックの識別情報を取得する。また、交通情報取得部２４は、ＶＩＣＳ（登録商標）センター１４からの渋滞情報や交通規制情報等の各種交通情報を一時的に記憶し、地図ＤＢ２２内の情報を更新する。
【００２８】
ブロック内情報記憶部２６は、道路地図を構成する各ブロックの情報を記憶するものであり、図５に示すように、フェロモン量テーブル５０、移動確率テーブル５２、リンクコストテーブル５４、エージェント経路テーブル５６、最適経路テーブル５８を備える。これら各種テーブル５０〜５８は、道路地図を構成するブロックごとに設けられている。
【００２９】
ここで、フェロモン量とは、あるリンク（ノード間）における車両の存在量を示す指標であり、例えば、「車両が５台存在する場合に１０である」といった基準によって定められる。フェロモン量は、例えば時間ｔの関数として定められ、時間ｔの経過とともに減衰していくものであり、例えば１秒間に１割の程度で減衰する。なお、減衰させる時間は１秒間隔に限られず、また、減衰割合も１割に限られることはない。ノードＸとノードＹ間のフェロモン量τxyは、例えば次式で表される。
【００３０】
【数１】
0005608185.tif 000002
【００３１】
ここで、τxy（ｔ）は、時間ｔにおけるフェロモン量、ρは減衰率であり、Δτxyは、時間ｔから時間（ｔ＋１）の間に増加するフェロモン量（後述するエージェントの通過数）である。なお、フェロモン量τxyは、上式に限られることはなく、例えば、隣接するリンクから一定割合で伝達する（伝達フェロモン）成分を含んでも良い。また、所定時間、フェロモン量が増加しない場合（Δτが所定時間ゼロの場合）には、τの値をゼロにしても良い。
【００３２】
リンクコストとは、あるリンク（ノード間）における距離を示す重み値ηであり、地図ＤＢ２２に記憶されているノードの位置情報に基づき算出される。リンク間の距離が短い場合はηの値は小さく、リンクの距離が長い場合にはηの値が大きくなる。
【００３３】
また、移動確率ρは、あるノードから隣接する別ノードに移動する確率を示すものであり、移動確率ρが大きいほど、車両が通過する割合が高く、最適な走行経路であることが示される。ノードＸからノードＹに向かう移動確率ρxyは、例えば次式で表すことができる。
【００３４】
【数２】
0005608185.tif 000003
【００３５】
ここで、ηxy（ｔ）は、時間ｔにおけるノードＸ・Ｙ間のリンクコスト、αは正の定数、βは負の定数である。また、上式において、Ｙは、あるノードＸと隣接するノードを示す。上式によれば、フェロモンτの値が大きい場合や、リンクコストηの値が小さい場合はノード間の移動確率が高くなり、フェロモンτの値が小さい場合や、リンクコストηの値が大きい場合はノード間の移動確率が低くなる。
【００３６】
図６は、ブロック内の隣接ノード間の関係の一例を示したものである。図６の例では、ノードＮｘと隣接するＹ１，Ｙ２，Ｙ３の３つのノードが定められ、各ノード間において、移動確率ρ、フェロモン量τ、リンクコストηが定められており、これらの値が、フェロモン量テーブル５０、移動確率テーブル５２、リンクコストテーブル５４にそれぞれ記憶されている。
【００３７】
図７は、フェロモン量テーブル５０のデータ構成の一例を示したものである。フェロモン量テーブル５０は、ブロック４４の転出ノードＤ１〜Ｄ３ごとに、当該ブロック４４内におけるノード間のフェロモン量τのデータを記憶している。
【００３８】
図７において、τO1N1（Ｄ１）は、転出ノードをＤ１としたときの、ノードＯ１とノードＮ１との間のフェロモン量を示す。フェロモン量テーブル５０に記憶されたフェロモン量のデータは、後述するエージェントによるノード探索処理が行われる毎に更新される。同様に、移動確率テーブル５２、リンクコストテーブル５４は、それぞれ、ブロック４４内のノード間の移動確率ｐ及びリンクコストηを、転出ノードＤ１〜Ｄ３ごとに記憶している。なお、フェロモン量テーブル５０、移動確率テーブル５２、リンクコストテーブル５４は、全ての転入ノード（本実施形態ではＯ１〜Ｏ３）に共通である。
【００３９】
エージェント経路テーブル５６は、後述するエージェントによる、ブロック４４内の転入及び転出ノードに至る経路を一時的に記憶するものである。ここで、エージェントとは、ブロック４４内を移動する車両を仮想的に示したものであり、エージェントの各々は、複数の転入ノードからランダムに決定された転入ノードを出発点、予め定められた転出ノードを目的点として移動するとともに、ブロック内のノード間の移動は、移動確率テーブルに記憶された移動確率に従う。すなわち、あるノード（例えば、図６におけるノードＸ）と隣接するノードが複数存在する場合（例えば、図６におけるノードＹ１，Ｙ２，Ｙ３）、移動確率が高いノード間（例えば、Ｐxy1が最も大きい場合は、ノードＸ・Ｙ１間）を通過する確率が高くなる。
【００４０】
また、エージェント経路テーブル５６には、エージェントが通過した経路が、転入ノード・転出ノード間の最適経路であるか否かを示す最適フラグが設けられている。この最短フラグは、後述する最適経路テーブル５８に記憶されている最適経由ノードと、エージェントの通過経由ノードとが一致した場合に「１」が、異なる場合に「０」が記憶される。これにより、各エージェントの走行経路が最適であるか否かを検出することができる。
【００４１】
最適経路テーブル５８は、ブロック４４内の転入及び転出ノード毎に、最適経路を示す経路ノードの情報と、経路長の情報が記憶されている。本実施形態において、最適経路とは、転入ノードから転出ノードに至る最短経路を意味する。例えば、転入ノードを「Ｏ１」、転出ノードを「Ｄ１」とする場合の最適経路は、ノードＯ１、ノードＮ１、ノードＮ３、ノードＤ１となり、その経路による経路長はＬ１１となる。同様に、転入ノードを「Ｏ２」、転出ノードを「Ｄ３」とする場合の最適経路は、ノードＯ２、ノードＮ１、ノードＮ４、ノードＤ３となり、その経路による経路長はＬ２３となる。
【００４２】
ブロック内経路生成部２８は、各ブロック４４における、転入ノード・転出ノード間の最適経路を抽出する。この最適経路の抽出は、前述したエージェントを用いた経路探索の方法により行うことができる。すなわち、ブロック内経路生成部２８は、エージェントの転出ノードを固定するとともに、転入ノードをランダムに決定する。そして、ランダムに決定された転入ノードを出発点とし、移動確率テーブル５２に記憶されたノード間の移動確率に従い、移動すべきノードを決定する。そして、移動先のノードにおいて、同様に、移動確率テーブル５２内の移動確率に従い、次に移動すべきノードを決定する。このようにして、エージェントがノード間を移動する。
【００４３】
ブロック内経路生成部２８は、各エージェントの移動回数の上限値ＴＨを予め定めており、起点ノードからＴＨ回の移動によっても、目的地としての転出ノードに到達しない場合は、当該エージェントによる経路移動を中止する。そして、別のエージェントを、ランダムに決定された転入ノードに配置し、同様にしてエージェントを移動させる。ブロック内経路生成部２８は、設定された転出ノードに達したエージェントにつき、その走行経路（経由ノード）の情報を、エージェント経路テーブル５６に記憶する。
【００４４】
図１０は、エージェントの移動経路の一例を示したものである。このエージェントＡＧ１は、起点としての転入ノードが「Ｏ１」と定められ、ノード間の移動確率に従い、ノード間を移動する。エージェントＡＧ１は、ノードＮ２、ノードＮ３を経由して、目的地である転出ノードＤ１に到達する。そして、ブロック内経路生成部２８は、当該エージェントＡＧ１による経由ノードと、最適経路テーブル５８に記憶された経由ノードとを比較し、異なる場合には、当該エージェントＡＧ１の経路が最適ではないと判定し、エージェント経由テーブル５６内の対応する最適フラグを「０」とする。
【００４５】
図１１は、別のエージェントＡＧ２の移動経路の一例を示したものである。このエージェントＡＧ２は、起点としての転入ノードが「Ｏ２」と定められ、ノード間の移動確率に従いノード間を移動する。エージェントＡＧ２は、ノードＮ１、ノードＮ３を経由して、目的地である転出ノードＤ１に到達する。そして、ブロック内経路生成部２８は、当該エージェントＡＧ２による経由ノードと、最適経路テーブル５８に記憶された経由ノードとを比較し、一致する場合には、当該エージェントＡＧ２の経路が最適であると判定し、エージェント経由テーブル５６内の対応する最適フラグを「１」とする。
【００４６】
ブロック内経路生成部２８は、目的地である転出ノードＤ１に到達したエージェントの数が、予め定められた所定値ｍに達したときに、エージェントによる経路探索を終了する。そして、ブロック内経路生成部２８は、エージェント経由テーブル５６に記憶された全エージェントの走行経路情報に基づき、フェロモン量テーブル５０、移動確率テーブル５２及び最適経路テーブル５８を更新する。
【００４７】
すなわち、ブロック内経路生成部２８は、エージェント経由テーブル５６に記憶された経由ノード情報より、全エージェントの通過リンク数を、リンク毎に集計する。そして、例えばリンクＸＹ間におけるエージェントの通過回数を、前記（１）式のΔτXYと定め、前記（１）式により、リンクＸＹ間のフェロモン量を更新する（ローカル更新）。このようなローカル更新処理は、リンク毎及び転出ノード毎に行われる。
【００４８】
さらに、ブロック内経路生成部２８は、最適経路テーブル５８に記憶された最適経路情報と一致する経路を通過したエージェントがある場合には、当該エージェントが通過した経路に対応するリンクについて、前記（１）式のΔτXYの値に一定量を加算する（グローバル更新）。例えば、転入ノード「Ｏ１」、転出ノード「Ｄ１」に対応する最適経由ノード「Ｏ１，Ｎ１，Ｎ３，Ｄ１」と同じ経由ノードを通過したエージェントが存在する場合には、ΔτO1,N1、ΔτN1,N3、ΔτN3,N1の値に、それぞれ一定量を加算する。これにより、最適経路に対して多くのフェロモンが集まるので、最適経路を効率よく抽出することができる。
【００４９】
そして、ブロック内経路生成部２８は、フェロモン量テーブル５０を更新した後、前記（２）式に基づき、各ノード間の移動確率を更新する。また、ブロック内経路生成部２８は、最適経路テーブル５８に記憶された経路よりもコストの低い（距離が短い）経路が、エージェント経由テーブル５６に記憶されている場合には、当該エージェント経由テーブル５６に記憶された経路に置き換える。これにより、最適経路を更新することができる。
【００５０】
ブロック内経路生成部２８は、道路地図４０を構成する各ブロック４４について、フェロモン量テーブル５０、移動確率テーブル５２及び最適経路テーブル５８を更新する。
【００５１】
全体経路探索部３０は、ブロック内経路生成部２８によって生成された各ブロックの最適経路テーブル２８を参照して、各ブロックの転入ノードから転出ノードに至る距離情報を抽出し、これらを組み合わせることで、車両の現在位置から目的地に至る走行経路を抽出する。
【００５２】
図１２は、全体経路探索部３０において、車両の現在位置に対応する始点ノードＯＮから、車両の目的地である終点ノードＤＮに至る走行経路を抽出する一例を示したものである。全体経路探索部３０は、車両１２から送信され、交通情報取得部２４において取得した車両の位置情報に基づき、車両１２が存在するブロック（始点ブロック）６４と、始点ノードＯＮを特定する。同様に、車両１２から送信された目的地情報に基づき、目的地が存在するブロック（終点ブロック）６５と、当該目的地の終点ノードＤＮを特定する。
【００５３】
全体経路探索部３０は、始点ブロック及び終点ブロックにおけるノード情報及びコストテーブルを地図ＤＢ２２から読み出すとともに、始点ブロック及び終点ブロックを含む一定範囲のブロックに対応する最適経路テーブル５８から、各ブロックの転入ノード及び転出ノードの情報とこれら転入・転出ノード間のコスト情報（距離情報）を読み出す。そして、そして、全体経路探索部３０は、読み出されたノード間距離情報に基づき、例えばダイクストラ法により、始点ノードＯＮから終点ノードＤＮに至る走行経路を抽出する。図１２の例では、始点ノードＯＮから隣接するブロックの転入ノード６６及び転出ノード６７が求められ、以後同様にして、各ブロックの転入ノード及び転出ノードが算出される。そして、終点ブロックの転入ノード（終点ブロックに隣接するブロックの流出ノード）６８を経由して、終点ノードＤＮまでの走行経路が抽出される。
【００５４】
以下、上記構成によるナビゲーション装置の動作について、図１３，１４のフローチャートを用いて説明する。図１３は、ブロック内経路生成部２８において、各ブロックにおける最適経路を抽出する処理を示すフローチャートである。ブロック内経路生成部２８は、ブロックごとに、エージェントの到達目標としての転出ノードを設定し（Ｓ１０）、エージェントの転入ノードをランダムに選択し、選択された転入ノードにエージェントを配置する（Ｓ１１）。
【００５５】
次に、ブロック内経路生成部２８は、移動確率テーブル５２に記憶されたノード間の移動確率に従い、ブロック内でエージェントを移動させるとともに、当該エージェントが通過したノード（経由ノード）の情報を、エージェント経路テーブル５６に記憶する（Ｓ１２）。
【００５６】
ブロック内経路生成部２８は、各エージェントが、転入ノードから所定回数ＴＨ内の移動により、設定された転出ノードに到達したか否かを検出する（Ｓ１３）。エージェントが所定回数ＴＨ内に転出ノードに到達していない場合（ステップＳ１３において「Ｎ」）は、当該エージェントの通過ノードの情報を削除する。これにより、通過経路が多く、最適経路の抽出に寄与しないエージェントの情報を確実に排除することができる。
【００５７】
このエージェントが所定回数ＴＨ内の移動により転出ノードに到達した場合（ステップＳ１３において「Ｙ」）には、ブロック内経路生成部２８は、ｍ個のエージェントが転出ノードに到達したか否か、すなわち、エージェント経路テーブル５６に記憶されたエージェントの数がｍに達したか否かを検出する（Ｓ１５）。その結果、転出ノードに達したエージェント数がｍ未満である場合には、再びステップＳ１１に戻り、別のエージェントを転入ノードに配置して、上記と同様にしてブロック内でエージェントを移動させる。これにより、フェロモン量テーブル５０、移動確率テーブル５２及び最適経路テーブル５８の更新に必要な数のエージェントの通過ノード情報を得ることができる。
【００５８】
一方、転出ノードに達したエージェント数がｍに達した場合には、ブロック内経路生成部２８は、エージェント経路テーブル５６に記憶されたエージェントの通過ノード情報に基づき、フェロモン量テーブル５０を更新し、更新後のフェロモン量テーブル５０に基づいて移動確率テーブル５２を更新する（Ｓ１６）。これにより、最適な経路に対するフェロモン量及び移動確率を高くすることができ、最適経路を効率よく抽出することができる。
【００５９】
また、ブロック内経路生成部２８は、エージェント経路テーブル５６に記憶されたエージェントの通過ノード情報から得られる、転入ノードから転出ノードまでの距離が、最適経路テーブル５８に記憶された距離よりも短い場合には、当該最適経路テーブル５８の情報を更新する（Ｓ１７）。これにより、各ブロックにおける最適経路が更新される。
【００６０】
そして、ブロック内経路生成部２８は、ブロック内に定められた全ての転出ノードについて、上述した処理（各種テーブルの更新処理）が行われたか否かを検出する（Ｓ１８）。各種テーブルの更新処理が終了していない転出ノードが残っている場合（ステップＳ１８において「Ｎ」）は、再びステップＳ１０に戻り、別の転出ノードに対して、同様の更新処理を行う。
【００６１】
一方、ブロック内の全ての転出ノードに対して更新処理が終了した場合（ステップＳ１８において「Ｙ」）には、ブロック内における最適経路の抽出処理が終了する。ブロック内経路生成部２８は、上述した最適経路の抽出処理を、継続的に（あるいは一定時間間隔）で行う。これにより、各ブロックにおける最適経路を精度良く抽出することができる。なお、上述した最適経路の抽出処理は、地図画像を構成する全てのブロックについて行われる。
【００６２】
図１４は、車両１２からの経路探索要求に応答して最適経路を抽出する処理を示すフローチャートである。ナビゲーション装置１０は、車両１２より経路探索要求を受信したか否かを検出する（Ｓ２０）。そして、経路探索要求を受信したことが検出されると（ステップＳ２０において「Ｙ」）、交通情報取得部２４は、経路探索要求を発した車両の位置情報に基づき、出発点としての始点ノード及び始点ブロックの情報を、地図ＤＢ２２内の情報に基づき取得する。同様に、交通情報取得部２４は、経路探索要求に含まれる目的地情報に基づき、目的地としての終点ノード及び終点ブロックの情報を取得する（Ｓ２１）。
【００６３】
次に、全体経路探索部３０は、起点・終点ブロックを含む一定範囲のブロックに対応する最適経路テーブル５８を、ブロック内情報記憶部２６より読み出す（Ｓ２２）。そして、全体経路探索部３０は、各ブロックにおける転入・転出ノード間の距離情報に基づき、ブロック単位で、起点ノードから終点ノードに至る走行経路を探索する（Ｓ２３）。各ブロックで抽出された最適経路の情報に基づき、ブロック単位で走行経路を探索することができるので、各ブロック内の走行経路の探索を省略することができ、処理時間を短縮することができる。
【００６４】
全体経路探索部３０は、探索された走行経路情報に基づき、車両の現在地点から目的地までの走行経路を示すノード情報を生成し、ナビゲーション装置１０は、通信部２０を介して、目的地に至るノード情報を送信する。これにより、目的地までの走行経路の情報が、車両１２に備えられたディスプレイに表示される。したがって、地図情報を備えていない車両においても、目的地までの走行経路の情報を迅速に取得することができる。
【００６５】
上記実施形態では、ノード間のコストパラメータとして、リンクの距離のみを用いているが、本発明はこれに限られることはなく、道路種別（高速道路、国道、県道など）、道幅、渋滞の程度、交通量、交通規制（通行止め、速度規制等）の有無、信号機の有無、右左折の有無といった各種のパラメータを考慮して、ノード間のコストηの値を決定しても良い。これらのパラメータは、例えば、地図ＤＢ２２に記憶されている道路地図や、ＶＩＣＳ（登録商標）センター１４からの交通情報に基づいて取得することができる。
【００６６】
さらに、渋滞状況や交通規制の変化に応じて、リンクコストηの値を変動させても良い。この場合において、上述したフェロモン量テーブル５０や移動確率テーブル５２の更新処理と同じタイミングで、リンクコストテーブル５４内の情報を更新することができる。これにより、交通状況の変化を反映した経路情報を抽出することができるので、経路探索の精度を向上することができる。この場合においても、ブロック毎に、転入及び転出ノード間の最適経路を算出した最適経路テーブルを備えているため、車両１２からの経路要求に迅速に対応することができる。
【００６７】
上記実施形態では、最適経路として、転入及び転出ノード間の最短経路を適用しているが、本発明はこれに限られることはなく、例えば、フェロモン量が最も多いノード間の組合せや、移動確率が最も高い組合せを、転入及び転出ノード間の最短経路と定めても良い。フェロモン量が多い経路、移動確率が高い経路は、多くの車両が走行する経路であり、適切な走行経路である場合が多いことから、このような経路を最適経路として定めることで、適切な走行経路を抽出することができる。
【００６８】
なお、各ブロックにおける渋滞情報は、例えば、特開２００７−２１９９９０号公報に記載の方法により算出された、所定時間経過後（例えば１時間後）の渋滞予測情報を用いても良い。すなわち、道路リンクごとに車両の存在量を取得し、取得された存在量を含む時間関数存在量（発生フェロモン）と時間関数伝達量（伝達フェロモン）を算出し、これら時間関数存在量及び時間関数伝達量に基づき、所定時間経過後（例えば５分後）の渋滞予測情報を求めることができる。あるいは、ＶＩＣＳ（登録商標）サーバから送信される渋滞情報と、地図ＤＢ２２に記憶された地図情報とを照合して、各リンクにおける渋滞情報を取得しても良い。
【００６９】
（第２実施形態）
図１５は、本発明の第２実施形態に係るナビゲーション装置７０の構成を示すブロック図である。この第２実施形態に係るナビゲーション装置７０は、第１実施形態と比較して、ブロック内経路生成部７２が複数の経路生成ユニット７４から構成される点で相違する。なお、上記第１実施形態と同じ構成部材については、同一の符番を付して詳細な説明を省略する。
【００７０】
ブロック内経路生成部７２は、複数の経路生成ユニット７４から構成されており、個々の経路生成ユニット７４は、道路地図を構成する複数のブロックのうち、少なくとも１つのブロックが割り当てられている。経路生成ユニット７４は、割り当てられたブロックに対して、上記第１実施形態で説明したのと同様にして、フェロモン量テーブル５０、移動確率テーブル５２及び最適経路テーブル５８の更新処理を行う。全体経路探索部３０は、これら複数の経路生成ユニット７４によって更新された最適経路テーブル５８の情報に基づき、車両の位置から目的地に至る最適経路を抽出する。
【００７１】
このように、複数の経路生成ユニット７４により、個々のブロックにおける最適経路テーブルの更新処理を並列的に行うことで、道路地図を構成する全ブロックの最適経路テーブルの更新処理に要する時間を短縮することができる。
【００７２】
（第３実施形態）
図１６は、本発明の第３実施形態に係るナビゲーションシステムの構成を示すブロック図である。この第３実施形態は、第１実施形態と比較して、車両の位置から目的地に至る最適経路を抽出するナビゲーション装置８０と、ブロック毎の最適経路テーブルを更新する経路生成装置８２とを別個に設け、通信回線８４を介して互いに接続した点で相違する。なお、上記第１実施形態と同じ構成部材については、同一の符番を付して詳細な説明を省略する。
【００７３】
図１７は、本発明の第３実施形態に係るナビゲーション装置８０と経路生成装置８２の各々の構成を示すブロック図である。ナビゲーション装置８０は、第１実施形態におけるブロック内情報記憶部の代わりに最適経路記憶部８６を備えており、この最適経路記憶部８６は、道路地図を構成する各ブロックの転入及び転出ノードの最短経路情報及び最短距離情報（あるいは最小コスト情報）を記憶する。
【００７４】
経路生成装置８２は、ブロック内情報記憶部８８と、経路生成ユニット８９と通信部２０とを備えており、ナビゲーション装置８０との間で、各種の交通情報や各ブロックの最適経路情報等の情報を送受信する。経路生成装置８２の各々は、道路地図を構成する複数のブロックのうち、少なくとも１つのブロックが割り当てられており、ブロック内情報記憶部８８は、当該経路生成装置８２に割り当てられたブロックに対する、フェロモン量テーブル、移動確率テーブル、リンクコストテーブル、エージェント経路テーブル、最適経路テーブルが設けられている。これら各種テーブルの内容については、第１実施形態で説明したのと同様であり、詳細な説明を省略する。
【００７５】
経路生成ユニット８９は、割り当てられたブロックに対して、上記第１実施形態で説明したのと同様にして、フェロモン量テーブル、移動確率テーブル及び最適経路テーブルの更新処理を行う。そして、更新された最適経路テーブルの情報が、通信部２０を介して、ナビゲーション装置８０に送信され、最適経路記憶部８６に記憶される。ナビゲーション装置８０の全体経路生成部３０は、最適経路記憶部８６に記憶された情報に基づき、車両の位置から目的地に至る最適経路を抽出する。
【００７６】
このように、道路地図を構成する複数ブロックにおける最適経路の算出を、ネットワークで接続された複数の装置で行うことにより、最適経路の算出処理を分散化することができ、しかも、複数ブロックにおける処理を並列して行うことができるから、処理速度及び処理効率が向上する。
【００７７】
（第４実施形態）
図１８は、本発明の第４実施形態に係るナビゲーション装置９０の構成を示すブロック図であり、ナビゲーション装置９０は、道路上を走行する複数の車両９２ａ〜９２ｃと例えば無線通信回線によって接続されており、一定時間間隔で各ブロック内の最短経路情報を更新するとともに、変更された最短経路を通過する予定の車両に対して、経路再探索を促すための通知を発する。
【００７８】
ナビゲーション装置９０は、第１実施形態と比較して、ブロック内情報記憶部９３に備えられた変化フラグテーブル９６（本発明の変動情報記憶部に対応。図２０参照）と、経路情報記憶部９４と通知判定部９８が設けられている点で相違する。なお、上記第１実施形態と同じ構成部材については、同一の符番を付して詳細な説明を省略する。
【００７９】
図１９，２０は、渋滞や通行止めといった交通状況の変化により、ブロック内の最短経路が変化した様子を示す説明図である。ここで、図１９，２０では、ブロック内のノードＮ１とＮ３を結ぶ区間に渋滞が発生した場合を例にして説明するが、本発明はこれに限られない。
【００８０】
図１９において、ブロック（Ｂ６）のノードＮ１とＮ３を結ぶ区間に渋滞が発生し、当該区間のリンクコストが増加した結果、ノードＯ２からノードＤ２に至る最短経路が、「Ｏ２，Ｎ１，Ｎ３，Ｄ２」（符番９５ａ）から「Ｏ２，Ｎ１，Ｎ４，Ｄ２」（符番９５ｂ）へと変化する。
【００８１】
図２０は、変化フラグテーブル９６に記憶されたデータ構成の一例を示すものであり、最短経路が変化した入出力ノードの組合せに対して「１」が、変化していない入出力ノードの組合せに対して「０」が、それぞれ記憶される。図１９において、ノードＯ２からノードＤ２に至る最短経路が変化したことから、図２０の例では、当該ノードに対応する変化フラグが、「１」となっている。この変化フラグテーブル９６への変化フラグの更新は、ナビゲーション装置９０においてブロック毎の最短経路検索を行う毎に行われる。
【００８２】
経路情報記憶部９８は、ナビゲーション装置９０と接続された車両が走行予定の経路情報が記憶されている。図２１は、経路情報記憶部９８に記憶された経路情報の一例であり、車両（クライアントＩＤ）毎に、経由するブロック（経由ブロック）と、当該経由ブロックにおける入出力ノードの情報が記憶されている。なお、図２１では、図面を簡略化するために、渋滞が発生したブロックＢ６のみ、入出力ノードの情報を記載しているが、実際は全ての経由ブロックに対して、入出力ノードの情報が記憶されている。
【００８３】
通知判定部９８は、経路情報記憶部９４に記憶された経路情報と、変化フラグテーブル９６に記憶された変化フラグの情報を参照して、各車両の経路情報に、変化フラグが「１」となっているブロックの入出力ノードが含まれているか否かを判定する。そして、対応する入出力ノードが含まれている場合には、その車両に対してのみ、最短経路の変化を通知する。車両への通知の方法としては、ナビゲーション装置９０から車両に対して一方的に通知を行う方法（周知のＰＵＳＨ型）の他、一定時間毎に車両からナビゲーション装置９０にアクセスした際に通知を行う方法（疑似ＰＵＳＨ）、車両とナビゲーション装置９０との間で接続（セッション）を確立して通知を行う方法（例えば、Ｃｏｍｅｔ、ＸＭＰＰ（eXtensible Messaging and Presence Protocol））を用いることができる。
【００８４】
図２０，２１の例では、変化フラグが「１」となった入出力ノードが、「ブロックＢ６：ノードＯ２，Ｄ２」であり、この情報は、クライアントＩＤ「２」に対応する車両の２番目の経由ブロックに該当することから、通知判定部９８は、車両９２ｂのみに対して、最短経路が変化したことを通知する。
【００８５】
図２２は、本実施形態に係るナビゲーション装置９０の動作を示すフローチャートである。ナビゲーション装置９０では、ユーザ（車両）からの経路探索要求を受けて、目的地までの経路（経由ブロック）を算出し、その結果が経路情報記憶部９４に記憶されている。ナビゲーション装置９０は、一定時間毎に、交通情報取得部２４で取得した道路情報に基づき、各ブロックを構成するリンクのコストをアップデートする（Ｓ３０）。
【００８６】
ブロック内経路生成部２８では、更新されたリンクコストに基づき，各ブロックにおける入出力ノードごとに、最短経路情報を検索し、最適コストテーブル５８を更新する（Ｓ３１）。このとき、最適コストテーブル５８の内容に変更があったか否かの判定が行われ（Ｓ３２）、変更があった場合には、対応する入出力ノードの変化フラグを「１」とする（Ｓ３３）。
【００８７】
そして、通知判定部９８は、経路情報記憶部９４と変化フラグテーブル９６とを参照して、各車両の経路情報に、変化フラグが「１」となっているブロックの入出力ノードが含まれているか否かを判定する（Ｓ３４）。そして、通知判定部９８は、対応する入出力ノードが経路情報に含まれている車両に対してのみ、最短経路の変化を通知する（Ｓ３５）。通知を受けた車両において、ナビゲーション装置９０に対して、目的地までの経路再探索を要求する。
【００８８】
このように、各ブロックの最短経路が変化した場合に、経路再探索を促す通知をナビゲーション装置から車両に通知を行うようにしたので、目的地までの走行経路のアップデートを効率よく行うことができる。また、ナビゲーション装置において不必要な経路検索が行われることがなくなるから、処理の効率化、通信コストの削減を図ることができる。
【００８９】
なお、この第４実施形態において、ブロック内の最適コストテーブルの更新があった場合にのみ、最短経路の変化を通知しているが、例えばブロック内の全ての経路で渋滞が発生した場合には、ブロック内の最短経路が変化しないが、出発地から目的地に至る全体の経路については、最適経路が変化している場合がある。このため、ブロック内の最適コストテーブルが更新された場合のみならず、例えば、（ア）ブロック内の最適経路の所要時間が閾値を超えた場合、あるいは、（イ）ブロック内の全ての入出力ノードに対応する最適経路の平均値の変化が閾値を超えた場合に、目的地までの全体の最適経路が変動したとして、当該ブロックを通過する車両に対して、経路再探索を促す通知を発するようにしても良い。
【００９０】
また、隣接するブロックのリンクコストが大きく低下した場合には、対象ブロックのリンクコストの変動が小さくとも、全体の最適経路は変動する。このため、対象ブロックと隣接するブロック内の最適経路の所要時間が閾値を超えて変動した場合にも、当該対象ブロックを通過する車両に対して、経路再探索を促す通知を発するようにしても良い。
【００９１】
上記実施形態では、いずれも、道路地図を分割した各ブロックの最適経路情報を組み合わせることで、道路地図全体における経路情報の探索を行っているが、複数（例えば４つ）のブロック（小ブロック）を組み合わせた中ブロックを設けても良い。この場合、小ブロックにおける最適経路情報に基づき、中ブロックにおける最適経路情報を算出し、この中ブロックにおける最適経路情報に基づき、道路地図全体における経路情報を探索するようにしても良い。
【００９２】
上記実施形態では、いずれも、車両に対して経路情報を提供しているが、本発明はこれに限られることはなく、例えば、歩行者が有する携帯端末に対して、目的地までの経路情報を提供するようにしても良い。
【産業上の利用可能性】
【００９３】
以上説明したように、本発明によれば、目的地に至る経路探索を短時間で効率的に行うことができ、ナビゲーション装置として有用である。
【符号の説明】
【００９４】
１０，７０，８０，９０  ナビゲーション装置
１２，９２ａ〜９２ｃ  車両
２２  地図ＤＢ
２４  交通情報取得部
２６，８８，９３  ブロック内情報記憶部
２８，７２  ブロック内経路生成部
３０  全体経路生成部
４０  道路地図
４２，４４  ブロック
５０  フェロモン量テーブル
５２  移動確率テーブル
５４  リンクコストテーブル
５６  エージェント経路テーブル
５８  最適経路テーブル
７４，８９  経路生成ユニット
８２  経路生成装置
８６  最適経路記憶部
９４  経路情報記憶部
９８  通知判定部
【図１】
0005608185.tif 000004
【図２】
0005608185.tif 000005
【図３】
0005608185.tif 000006
【図４】
0005608185.tif 000007
【図５】
0005608185.tif 000008
【図６】
0005608185.tif 000009
【図７】
0005608185.tif 000010
【図８】
0005608185.tif 000011
【図９】
0005608185.tif 000012
【図１０】
0005608185.tif 000013
【図１１】
0005608185.tif 000014
【図１２】
0005608185.tif 000015
【図１３】
0005608185.tif 000016
【図１４】
0005608185.tif 000017
【図１５】
0005608185.tif 000018
【図１６】
0005608185.tif 000019
【図１７】
0005608185.tif 000020
【図１８】
0005608185.tif 000021
【図１９】
0005608185.tif 000022
【図２０】
0005608185.tif 000023
【図２１】
0005608185.tif 000024
【図２２】
0005608185.tif 000025