"道路リンクと地図を区画するメッシュとを対応付けた地図データと、前記メッシュと前記メッシュの少なくとも1つの隣接メッシュとがメッシュ内最小コスト経路の両端ノードの各々を共有するときの前記メッシュ内最小コスト経路のコストを表すメッシュコストとに基づき、移動体の始点を含む始点メッシュと前記始点メッシュに隣接する始点隣接メッシュとの境界に位置する第1境界ノードから前記移動体の終点を含む終点メッシュと前記終点メッシュに隣接する終点隣接メッシュとの境界に位置する第2境界ノードまでの境界ノード間接続最小コスト経路に含まれる複数の中継メッシュを取得する中継メッシュ取得手段と、前記境界ノード間接続最小コスト経路に含まれる区間道路リンクを含むメッシュにおいて、前記区間道路リンクのリンクコストの更新に基づく新たなメッシュ内最小コスト経路のコストを表すように前記メッシュコストを更新し、更新された前記メッシュコストに基づき前記複数の中継メッシュを更新し、更新された前記複数の中継メッシュと前記新たなメッシュ内最小コスト経路とに基づき、前記始点から前記終点までの移動経路を探索する経路探索手段とを備えることを特徴とする経路演算装置。請求項1に記載の経路演算装置において、現況交通情報を取得する取得手段をさらに備え、前記経路探索手段は、前記リンクコストと、前記現況交通情報に基づく前記区間道路リンクの現況コストとの差分が所定の閾値以上のとき、前記リンクコストの更新に基づき前記メッシュコストの更新を行うことを特徴とする経路演算装置。請求項2に記載の経路演算装置において、前記所定の閾値は、前記移動体が前記始点を出発してから前記区間道路リンクを移動するまでの予測経過時間に応じた関数であることを特徴とする経路演算装置。請求項1に記載の経路演算装置において、前記中継メッシュ取得手段によって算出された前記メッシュコストを、前記両端ノードに対応付けたメッシュコストデータをさらに備え、前記第1の経路探索手段は、前記メッシュコストデータに含まれる前記メッシュコストを参照して、前記複数の中継メッシュを取得することを特徴とする経路演算装置。請求項1に記載の経路演算装置において、前記中継メッシュ取得手段によって算出された前記メッシュコストを、前記両端ノードに対応付けたメッシュコストデータをさらに備え、前記メッシュコストデータは、前記メッシュ内最小コスト経路を構成する前記道路リンクに関するデータを含むことを特徴とする経路演算装置。請求項4または5に記載の経路演算装置において、前記メッシュコストデータは、複数種類の経路探索条件に応じた複数種類のコストに関するデータを含むことを特徴とする経路演算装置。しかし、特許文献1に記載の方法によると、経路探索前のコスト計算の段階で、想定できない状況を考慮できない。例えば、自動車事故が原因で引き起こされた渋滞の情報を取得した際に、この渋滞を回避したい場合でも、既にコストが計算されていると、この渋滞の情報を加味できない。1請求項1に記載の経路演算装置は、道路リンクと地図を区画するメッシュデータとを対応付けた地図データと、メッシュとメッシュの少なくとも1つの隣接メッシュとがメッシュ内最小コスト経路の両端ノードの各々を共有するときのメッシュ内最小コスト経路のコストを表すメッシュコストとに基づき、移動体の始点を含む始点メッシュと始点メッシュに隣接する始点隣接メッシュとの境界に位置する第1境界ノードから移動体の終点を含む終点メッシュと終点メッシュに隣接する終点隣接メッシュとの境界に位置する第2境界ノードまでの境界ノード間接続最小コスト経路に含まれる複数の中継メッシュを取得する中継メッシュ取得手段と、境界ノード間接続最小コスト経路に含まれる区間道路リンクを含むメッシュにおいて、区間道路リンクのリンクコストの更新に基づく新たなメッシュ内最小コスト経路のコストを表すようにメッシュコストを更新し、更新されたメッシュコストに基づき複数の中継メッシュを更新し、更新された複数の中継メッシュと新たなメッシュ内最小コスト経路とに基づき、始点から終点までの移動経路を探索する経路探索手段とを備えることを特徴とする。本発明によると、ユーザーは、リアルタイムな情報に対応した経路探索を効率的に実行できる。本発明を用いた経路演算装置の実施の形態を、図面を参照して説明する。―第1の実施の形態―図1は本発明の第1の実施の形態における車載端末装置100の全体構成を示す図である。車載端末装置100は、目的地入力装置110、車載端末装置100の搭載された車両の自車位置算出装置130、地図データ140、メッシュコストデータ150、通過メッシュ算出装置160、経路探索装置170、経路探索結果記憶装置180、リアルタイム情報取得装置190、比較装置200、表示装置220を有する。また、車載端末装置100とセンサ類120とがCANなどの車載ネットワークを介して接続されている。目的地入力装置110は、ユーザーが、車載端末装置100の例えばリモコンのようなユーザーインターフェースを通して入力する目的地情報及び経路探索タイプ情報を受け付ける。目的地情報は、通過メッシュ算出装置160へ提供される。ユーザーは、目的地情報を入力する際、目的地の住所、カテゴリ、電話番号等をキーに、目的地のPOIを検索し、設定する。POIとは、PointOfInterestの略で、店舗情報などの地点に関する情報である。経路探索タイプ情報は、経路探索条件の種類を表す情報である。経路探索タイプ情報の種類としては、例えば、目的地まで最小の時間での到着を目指す最小所要時間経路、目的地まで最小の燃料消費量での到着を目指す最小燃料消費量経路、目的地まで距離を最短にすることを目指す最短経路がある。通過メッシュ算出装置160、経路探索装置170は、目的地入力装置110で受付けた経路探索タイプに対応する指標を最小化するように実行される。この指標とは、すなわちコストであり、例えば、経路探索タイプ情報が最小所要時間経路の場合は、目的地までの旅行時間、経路探索タイプ情報が最小燃料消費量経路の場合は、目的地までの燃料消費量、経路探索タイプ情報が最短経路の場合は、目的地までの距離である。センサ類120は、GPS、車速パルス、角速度センサなどをいう。このセンサを用いることで、車両の位置、車速、角速度を計測することができる。これらの情報は自車位置算出装置130へ提供される。自車位置算出装置130は、センサ類120の情報から、自車の位置を算出する。この算出には、公知の技術であるカルマンフィルタやデッドレコニングが用いられる。算出した自車位置の情報は、通過メッシュ算出装置160を介して経路探索装置170へ提供される。自車位置情報は、例えば緯度経度で表される。地図データ140は、ハードディスク、フラッシュメモリ等の記憶装置に格納され、道路データ、POIの情報を含む。通過メッシュ算出装置160及び経路探索装置170の地図領域に該当する道路情報、POIの情報を提供する。地図データ140の構成図を図2に示す。図2aは、地図データ140に格納されている道路データの構成を示している。道路データはノードからノードまでのリンク単位で構成される。ノードには、道路の交差点に設けられるような通常のノードと、メッシュの境界に設けられる図郭ノードとがある。通常のノードに対して、図郭ノードは、図郭ノードフラグで区別される。例えば、ノードが図郭ノードの場合は図郭ノードフラグに1、通常のノードの場合は図郭ノードフラグに0が設定される。各道路データは、道路を特定するリンクID、その道路リンクの存在するメッシュID、道路リンクの始端のノードIDとその緯度経度高度情報、図郭ノードフラグ、道路リンクの終端のノードIDとその緯度経度高度情報、図郭ノードフラグ、道路種別、規制情報、コストデータで構成される。規制情報は、制限速度情報、一方通行情報などである。なお、ノード間のリンク上に補間点が規定される場合、ノードと補間点との間および補間点同士の間にリンクを規定してもよい。また、道路リンクの高度は、始端終端ノードの高度情報ではなく、勾配情報で表してもよい。ここで、メッシュとは、地図を緯度経度に基づいて網の目状に区画する方法により得られる単位区画である。2次メッシュとは緯度差5分、経度差7分30秒で区画されて得られる一辺の長さが約10kmのメッシュである。また3次メッシュは2次メッシュを緯度方向および経度方向に10等分して得られるメッシュであり、緯度差30秒、経度差45秒で、一辺の長さが約1kmである。メッシュIDにより、メッシュを特定することができる。ここで、道路種別とは、道路リンクの種類を表す情報である。道路種別には、例えば、道路リンクが都市間高速道の場合は0、都市内高速道の場合は1、国道の場合は2、そのほかの道路の場合は3が設定される。ここで、コストデータとは、経路探索の際に使用される道路リンクに関連した重みである。例えば、コストデータの例に、統計交通情報がある。この統計交通情報は、リアルタイム情報取得装置200にて取得し、蓄積した道路の渋滞情報を統計処理することで作成される。この統計処理とは、平日、休日などの日種毎、及び000、2300などの時間毎に作成される。図2dに、コストデータの構成を示す。ここで、図郭ノードは、通常のノード間の道路リンクがメッシュを跨ぐ場合に、地図データ140内での管理上、道路リンクをメッシュの境界で分割するためのノードである。一端または両端が図郭ノードで規定されることにより、道路リンクが、メッシュをまたいで存在しないこととなる。図3に図郭ノードの例を示す。通常のノード間の道路リンクがメッシュID001および002の隣接するメッシュに跨がる場合図3、メッシュの境界線で道路リンクを分割し、分割後の道路リンクを各メッシュで管理する。このとき、分割位置を図郭ノードとして地図データ140内に格納する。また、メッシュ境界における同じ道路リンク上の同じ分割位置に規定される一対の図郭ノードは、隣接するメッシュ間で共通のノードID001を持つ。そのため、車載端末装置100は、その道路リンクによってメッシュID001のメッシュがどのメッシュに接続しているかを、知ることができる図3b。図2bは、図2aに示した道路データとともに地図データ140に含まれるメッシュ管理テーブルを示している。このメッシュ管理テーブルには、メッシュIDおよびそのメッシュの左下、左上、右下、右上のそれぞれの頂点の座標緯度経度が設定されている図2c参照。メッシュコストデータ150は、後述する第2の実施の形態と同様に外部のセンタ装置等で生成された後、予め車載端末装置100のハードディスク、フラッシュメモリ等の記憶装置に格納され、メッシュ境界の図郭ノード同士を結んだ経路のコストを表す。通過メッシュ算出装置160は、目的地入力装置110からの目的地情報、自車位置算出装置130からの自車位置情報、メッシュコストデータ150からメッシュ内の図郭ノード同士を結んだ経路のコストを取得し、通過メッシュを決定する。さらに、通過メッシュの地図データを地図データ140から取得してメモリに展開する。経路探索装置170は、通過メッシュ算出装置160によりメモリに展開された地図データを取得し、通過メッシュ内部の経路を算出する。算出した通過メッシュ内部の経路を、経路探索結果記憶装置180へ格納する。経路探索結果記憶装置180は、ハードディスク、フラッシュメモリ等の記憶装置であって、経路探索装置170で出力された経路と、通過メッシュ算出装置160で算出した通過メッシュの情報を記憶している。リアルタイム情報取得装置190は、例えばVICSセンター登録商標のような交通情報サービスセンターから全国の主要な道路の道路リンク毎の旅行時間を受信する。情報の更新周期は、予め定められた時間間隔とする。リンク毎の旅行時間は、例えば、道路リンク毎に道路に車両検知装置を設けて、道路リンク毎の走行に要した時間を測定すること、或いはプローブカーを道路リンク毎に時間測定しながら走行させることで得られる。比較装置200は、経路探索結果記憶装置180に格納されている経路探索結果に含まれる道路リンクのコストと、リアルタイム情報取得装置190にて取得したリアルタイム情報から算出される道路リンクのコストとを比較して、再探索が必要なメッシュがあるか否かを判定する。再探索が必要な場合は、再探索の必要なメッシュの情報を経路探索装置170へ送信する。経路探索装置170は、再探索が必要なメッシュの情報を比較装置200から受け取った場合、再探索対象のメッシュの始点側の図郭ノードから終点側の図郭ノードまでの経路を、リアルタイム情報取得装置190で取得したリアルタイム情報を使用して、再び探索する。表示装置220は、液晶ディスプレイ等であり、経路探索結果記憶装置180からの経路探索結果を表示する。以下、メッシュコストデータ150、通過メッシュ算出装置160、経路探索装置170、経路探索結果記憶装置180、比較装置200の構成及び処理フローを説明する。メッシュコストデータ150の構成図を図4に示す。図4aは、メッシュコストデータ150に格納されているメッシュ毎のコストデータの構成例を示している。メッシュコストデータ150においては、メッシュ内の特定道路種別の図郭ノード同士を結ぶ経路の数nと、各経路に対応する始点の図郭ノードIDおよび終点の図郭ノードID、ならびにその経路のコストデータとがメッシュ単位に管理されている。各経路は、図郭ノード同士の組合せを始点終点として地図データ140を用いて経路探索した結果であり、この経路のコストデータは、メッシュコストデータ150に格納される。このコストデータは、目的地入力装置110にて入力できる経路探索タイプ情報毎の経路探索結果のコストデータとコスト数とから構成される。図4bに示すメッシュID001の図郭ノードID101を始点、図郭ノードID102を終点としたときの最短経路の経路探索結果とそのコストが、図4aに表すコストデータとして管理されている。図4aの最小時間経路、最小燃料消費量経路も同様に、メッシュID001の図郭ノードID101を始点、図郭ノードID102を終点とし、経路探索を実行して算出される。同様にして、詳細を図示することは省略しているが、同じメッシュにおける図郭ノードID101を始点、図郭ノードID103を終点としたときの最短経路の経路探索結果とそのコストが管理されている。このようにして、図示を省略しているが、同じメッシュにおける図郭ノードID101~103のうちのいずれか2つを始点および終点としたときの各組み合わせ毎、すなわち6通りの経路n=6の各々について、最短経路の経路探索結果とそのコストが管理されている。後述するように、最短経路、最小時間経路および最小燃料消費量経路のうちから、目的地入力装置110にて入力された経路探索タイプ情報に対応する最小コスト経路が抽出される。その最小コスト経路のコストデータに基づき、メッシュ内の図郭ノード同士を結ぶ経路の最小コストが定まる。図4aに示すメッシュ毎のコストデータにおいては、上述したメッシュID001のコストデータに続いて、詳細を図示することは省略しているが、メッシュID002のコストデータが管理されている。このようにして、メッシュ毎のコストデータがメッシュコストデータ150に格納されている。外部のセンタ装置でメッシュコストデータ150を作成するための処理フローを図5に従って説明する。この処理は、経路探索の前段階の処理であり、地図データを入力する。はじめに、地図データの全メッシュを処理したかを判定するステップS101。処理した場合ステップS101でYes、処理を終了する。処理していない場合ステップS101でNo、対象のメッシュ内の図郭ノードで、特定の道路種別のものを抽出するステップS102。例えば、都市間高速、都市内高速および国道を抽出する。これは、全ての道路種別の図郭ノードを扱うと、ノード数が増えてしまうため、道路種別に基づいてノード数を絞ることとしたものである。次に、対象メッシュ内のステップS102で抽出した全ての図郭ノードを処理したかどうかを判定するステップS103。処理した場合ステップS103でYes、ステップS101へ進む。処理していない場合ステップS103でNo、処理中の図郭ノードを対象図郭ノードとし、ステップS104へ進む。このとき対象図郭ノードIDをIとする。ステップS104では、対象図郭ノードIDI以外の対象メッシュ内の図郭ノードIDを全て処理したかどうかを判定するステップS104。処理した場合ステップS104でYes、ステップS103へ進む。処理していない場合ステップS104でNo、対象図郭ノードIDI以外の対象メッシュ内の図郭ノードIDJIとJとは相異なるを抽出し、経路探索するステップS105。このとき、対象図郭ノードIDIを始点、図郭ノードIDJを終点とした経路を算出する。経路は、公知の技術であるダイクストラ法を用いて算出する。探索に用いるコストは、目的地入力装置110で設定できる経路探索タイプを用い、経路探索も経路探索タイプ毎に実行する。次に、ステップS105で用いた、始点の図郭ノードID、終点の図郭ノードID及び経路探索にて算出されたコストを、メッシュコストとしてメッシュコストデータ150へ格納するステップS106。ただし、特定道路種別の図郭ノード同士を結ぶ道路リンクが、対象メッシュ内に存在しない場合は、コストの項目には、道路リンクが存在しないことを判定できる値、例えば-1が入力される。ステップS106の終了後、ステップS104へ進む。図7に示すように、通過メッシュ算出装置160では、経路探索の際に、出発地S側の図郭ノードOから目的地G側の図郭ノードDまで、どのメッシュMを通過するのかを決定する。この通過する複数のメッシュMを通過メッシュM0と定義する。出発地側図郭ノードOは、出発地Sを含む出発地側メッシュMSとそれに隣接する通過メッシュM0との境界に位置する。目的地側図郭ノードDは、目的地Gを含む目的地側メッシュMGとそれに隣接する通過メッシュM0との境界に位置する。図7において、斜線のメッシュが、出発地S側の図郭ノードOと目的地M側の図郭ノードDとを結ぶ通過メッシュM0である。通過メッシュ算出装置160では、メッシュコストデータ150に格納されたメッシュコストを用いて、通過メッシュM0に含まれるメッシュM毎に図郭ノードOから図郭ノードDまで経路探索を行う。なお、図7において、各通過メッシュM0内の図郭ノード間を線分で結んでいるが、こうした表記は、その図郭ノード間を結ぶ経路が存在することを説明するための便宜上行ったものであり、その線分自体が上述したメッシュコストデータ150に含まれるものではない。図7以降の図面においても同様である。通過メッシュ算出装置160の処理フローを図6にしたがって説明する。はじめに、出発地と目的地周辺の候補図郭ノードを抽出するステップS201。候補図郭ノードとは、出発地及び目的地の周辺に存在し、出発地及び目的地からたどり着ける図郭ノードである。出発地及び目的地の周辺に存在する候補図郭ノードとは、候補図郭ノードが出発地及び目的地の属するメッシュに含まれる場合のみならず、候補図郭ノードが、出発地または目的地の属するメッシュの隣接するメッシュに含まれる場合をも意味する。図8に出発地S側の候補図郭ノードO1~O4の例を示す。図郭ノードO1及びO2は、出発地Sのある道路リンクL12が接続しているため、候補図郭ノードとなる。しかし、図郭ノードO3及びO4は、道路リンクL34上に位置し、出発地Sとは道路リンクで接続されていないため、候補図郭ノードにならない。ステップS201の詳細な処理フローを図9に従って説明する。はじめに、出発地周辺及び、目的地周辺の図郭ノードを抽出するステップS301。ここでは、出発地及び目的地の属するメッシュの図郭ノードを全て抽出する。次に、すべての抽出したすべての図郭ノードを処理したか否かを判定するステップS302。全てについて処理していない場合S302でNo、抽出した図郭ノードまで経路探索し、その抽出した図郭ノードが候補図郭ノードかどうかを判定するステップS303。図8の例で説明すると、出発地Sから、出発地Sを含む出発地側メッシュMSとその隣接メッシュとの境界に位置する図郭ノードO1,O2,O3,O4まで、地図データ140を用いて経路探索する。出発地Sから図郭ノードO1,O2,O3,O4まで道路のネットワークデータがある場合、候補図郭ノードと判定する図8の例では図郭ノードO1,O2が該当する。出発地から図郭ノードまで道路のネットワークデータがない場合、または経路探索の結果、コストが予め定めた値よりも大きい場合、その抽出した図郭ノードは候補図郭ノードには選ばれない図8の例ではO3,O4が該当する。目的地側の図郭ノードの場合は、目的地から図郭ノードまで経路探索する。全てについて処理した場合S302でYes、候補図郭ノードが、目的地側と出発地側にそれぞれ1個以上存在するか否かを判定するステップS304。候補図郭ノードが存在する場合S304でYes、処理を終了する。候補図郭ノードが存在しない場合S304でNo、図郭ノードを探索する範囲を広げて、ステップS302へ進むステップS305。探索範囲を広げるということは、すなわち、隣接するメッシュをも探索対象とするということを意味する。広げた探索範囲の中で、出発地及び目的地の周辺のメッシュの図郭ノードを新たに抽出する。図6の処理フローに戻り説明する。ステップS201で候補図郭ノードを決定した後に、出発地側及び目的地側の全ての候補図郭ノードの組合せを処理したかを判断するステップS202。全ての図郭ノードの組合せを処理した場合ステップS202でYes、処理を終了する。全ての図郭ノードの組合せを処理していない場合ステップS202でNo、メッシュコストデータ150に含まれる最短経路、最小時間経路および最小燃料消費量経路のうちから、目的地入力装置110にて入力された経路探索タイプ情報に対応する最小コスト経路のコストデータが、メッシュコストデータ150から最小コストとして抽出し、経路探索をするステップS203。図10にステップS203の例を示す。出発地側の候補図郭ノードO1、O2と目的地側の候補図郭ノードD1、D2との組合せは、O1からD1,O1からD2,O2からD1、O2からD2の4つである。ここでは、メッシュコストデータ150に格納されたメッシュコストを用いて、候補図郭ノードO1またはO2を出発地とし、候補図郭ノードD1またはD2を目的地として経路探索する。図10は、候補図郭ノードO1及びD2の組合せを出発地及び目的地の組合せとする例と、候補図郭ノードO2及びD1の組合せを出発地及び目的地の組合せとする例とを示している。候補図郭ノードO1を出発地、候補図郭ノードD2を目的地としたときの他経路探索が成り立つ。一方、候補図郭ノードO2を出発地、候補図郭ノードD1を目的地としたときの経路探索は、途中のメッシュ内の図郭ノードN1から図郭ノードN2までを接続する経路がメッシュ内に無いため、成立しない。したがって、この例では、候補図郭ノードO1からD2までの間の図郭ノードを結んだ経路が含まれる複数のメッシュが通過メッシュとなる。通過メッシュを決定したとき、出発地点側の図郭ノード、および目的地側の図郭ノードの情報を含む通過メッシュの情報を経路探索結果記憶装置180に記憶するステップS204。図11aに、ステップS204で経路探索結果記憶装置180に格納される通過メッシュの情報の構成図を示す。複数組の通過メッシュがある場合、経路探索結果記憶装置180はそれら複数組の通過メッシュの情報を記憶する。通過メッシュの情報は、出発地側の図郭ノードID,目的地側の図郭ノードID、通過メッシュ数、ステップS203の経路探索で算出したメッシュコストの総和と、詳細な通過メッシュ情報DMMを含む。詳細な通過メッシュDMMに含まれる情報を、図11bの例を用いて説明する。詳細な通過メッシュ情報DMMは、通過メッシュ数分記憶され、通過メッシュのID、始点図郭ノードID,終点図郭ノードID、およびコストデータ150に格納されているコストデータであって、始点図郭ノードIDと終点図郭ノードIDとの間のメッシュコストを含む。通過メッシュには、図郭ノードは2つ存在する。これらの図郭ノードはステップS203にて求めた経路の両端に位置しており、出発地に最も近い始点図郭ノードを出発地側図郭ノード、目的地に最も近い終点図郭ノードを目的地側図郭ノードと定義する。図11aにおける詳細な通過メッシュDMMには、通過メッシュID002についてのデータも含まれている。しかし、図11bの例においては通過メッシュが1つだけのため、これに対応して図11aにおける詳細な通過メッシュDMMには、通過メッシュのID001のデータのみが格納されることとなる。次に、経路探索装置170を図12の処理フローに従い説明する。図13に図12の処理フローに従って実行される経路探索処理の概念図の一例を示す。はじめに最小コストの通過メッシュ情報を取得するステップS401。この処理では、通過メッシュ算出装置160の処理によって経路探索結果記憶装置180に格納された通過メッシュ情報の中で、コスト総和の最小のものを取得する。このとき図13aのように、出発地から目的地までの間の図郭ノードNが含まれる通過メッシュが選ばれる。次に、取得した通過メッシュに含まれるメッシュ毎に、出発地側図郭ノードOを出発地、目的地側図郭ノードDを目的地として経路探索を実施するステップS402。この経路探索処理は、地図データ140に格納されている道路ネットワークデータのうち、処理対象のメッシュのデータをメモリ上に展開し、道路リンク毎のコストデータを使って経路探索することによって行われる。経路探索した結果は、例えば図13bのように表される。全てのメッシュに対して経路探索が終了した後、経路探索結果を経路データとして経路探索結果記憶装置180に格納するステップS403。図14は、経路探索結果記憶装置180に格納される経路データの構成の一例を表している。図14bの例を用いて、図14aに示す経路データ構成を説明する。経路データは、通過メッシュ毎に、始点図郭ノードID101、終点図郭ノードID102、経路を構成する道路リンク数3、経路を構成する道路リンクID1001,1002,1003およびそのコスト30m、50m、20mを含む。次に、比較装置200の処理フローについて、図15を用いて説明する。この比較装置200の処理フローは、リアルタイム情報を取得したタイミング、または予め定められた時間間隔で実行される。はじめに、経路探索結果記憶装置180から経路探索結果を取得するステップS501。次に、リアルタイム情報取得装置190で取得した情報と、経路探索結果とを比較して、再探索が必要か否かを判定するステップS502。経路探索装置180でメッシュコストデータの最小時間を用いて、経路探索をしたとき、コストは道路リンクを通過する旅行時間となる。メッシュコストデータ作成時に考慮される旅行時間は、過去の旅行時間を統計処理したものである。しかし、過去の交通情報でカバーできない状況が起きたとき、再探索が必要になる。例えば、経路上に、交通事故が発生し、渋滞が引き起こされたという情報を、リアルタイム情報取得装置190にて取得した場合、再度この渋滞を避けるように再探索をする必要がある。この再探索するか否かの判定をステップS502で行う。ステップS502においては、例えば、取得したリアルタイム交通情報の旅行時間と、過去の交通情報を統計処理した統計交通情報の旅行時間との差分が閾値以上であることが検出された場合、または事故発生情報を取得した場合に肯定判定される。再探索すると判定した場合ステップS502でYes、経路探索装置170へ再探索を要求し、処理を終了するステップS503。再探索を要求する際には、再探索が必要な通過メッシュのIDを経路探索装置170へ送信する。経路探索装置170では、後述するように、この再探索が必要な通過メッシュについて再探索を実行する。一方、再探索するか否かの判定において、再探索する必要がないと判定した場合ステップS502でNo、処理を終了する。図16は、ステップS502の処理の詳細を、ステップS5021~S5024として示した図である。以下、図16の処理フローについて説明する。ただし、ステップS501およびS503については、図15と同様であるため、説明を省略する。ステップS501における経路探索結果取得の後、ステップS5021において、後述するステップS5022およびS5023の処理を、ステップS501にて取得した経路が含まれる全てのメッシュについて行ったか否か、判定する。肯定判定の場合は処理をステップS5024へ進める。否定判定の場合は、ステップS5022において、リアルタイム情報取得装置190にて取得したリアルタイム情報のコストと、経路探索結果記憶装置180に格納されている経路探索結果の道路リンクのコストとの差が、閾値以上かを判定する。ステップS5022では、処理対象メッシュにおいて、経路探索結果記憶装置180に格納されているリンクIDに該当するリンクのリアルタイム情報のコストCRを取得する。さらに経路探索結果記憶装置180に格納されているリンクIDのリンクのコストCMを取得する。全ての経路上の道路リンクを処理し、リアルタイム情報のコストと経路探索結果のコストとの差が閾値以上の場合ステップS5022でYes、その道路リンクの存在するメッシュを再探索要求対象とするステップS5023。処理をステップS5021へ戻す。処理対象メッシュにおいて、リアルタイム情報と経路探索結果とのコスト差が閾値以上に該当する道路リンクが存在しない場合ステップS5022でNo、処理をステップS5021へ戻す。ステップS5021における判定が肯定判定の場合、ステップS5023において再探索要求対象とされたメッシュがあるか否かを判定するステップS5024。肯定判定の場合、処理を上述したステップS503を経て終了し、否定判定の場合は直ちに処理を終了する。例えば、コストCRは、リアルタイム交通情報に基づいて車両が道路リンクを走行する際のリンク旅行時間、コストCMは、統計交通情報または規制速度に基づいて車両がその道路リンクを走行する際のリンク旅行時間となる。このとき、コストCRと、コストCMから算出する閾値とを比較する。予め定められる閾値は、コストCMを係数k倍したコストkCMとする。例えば、コストをリンク旅行時間としたときCMが60秒で係数kを3としたとき、閾値は180秒となる。リアルタイム交通情報によるコストCRが200秒の場合、閾値180秒と比較して大きいため、この道路リンクに存在しているメッシュは再探索対象と判定する。この閾値は、車両が出発地Sを出発してからその道路リンクを走行するまでの予測経過時間に応じた関数でもよい。次に、経路探索装置170の再探索処理を説明する。再探索処理の概念図を図17に示す。図17に示すように、経路探索処理170による再探索が実行される際、出発地Sに最も近い候補図郭ノードO1から目的地Gに最も近い候補図郭ノードD2までの、図郭ノードNを経由する通過メッシュMOが既に決定されている。経路探索装置170では、通過メッシュMOのうち、再探索対象メッシュMR内の最小コスト経路を探索する。この探索は、再探索対象メッシュMRの出発地側図郭ノードORから再探索対象メッシュMRの目的地側図郭ノードDRまでの経路探索を、リアルタイム情報取得装置190から入力されるリアルタイム情報を用いて実行する。探索に用いるコストは、目的地入力装置110で設定できる経路探索タイプを用いる。このとき地図データ140を使用する。こうして、経路探索結果記憶装置180に格納されている通過メッシュMO中で、比較装置200で判定した再探索対象メッシュMRの最小コスト経路を更新する。この経路探索結果として得られる再探索された経路RRは、はじめにメッシュコストデータ150を計算したときに算出した経路と異なっても構わない。さらに、再探索対象のメッシュMRのORからDRまでのメッシュコストデータを、最小コスト経路のコストデータで更新する。更新した後、通過メッシュMOのメッシュコスト総和も更新する。全ての再探索対象のメッシュMR内の通過メッシュの通過する図郭ノード間の最小コスト経路のコストデータを、その図郭ノード間のメッシュコストデータとして更新した後、経路探索装置170においてステップS401の処理が実行される。このとき、更新したメッシュコストを用いて経路探索をする。表示装置220では、経路探索結果記憶装置180の経路探索結果を示す最適経路表示画面を、ディスプレイ上に表示し、ユーザーに提示する。表示例を図18に示す。図18aは、出発地Sから目的地Gまで経路探索したときに、地図上に経路探索結果記憶装置180の経路探索結果を最適経路1810として重畳表示し、さらに、吹き出し1820を用いて目的地までのコスト所要時間20分を提示している。また、他の表示の例を図18bに示す。この例は、通過メッシュ算出装置160から通過メッシュを算出し、経路探索装置170の処理中に、通過メッシュ1910の情報をディスプレイ上に表示し図18b、ユーザーに提示している。さらに、吹き出し1920を用いて通過メッシュを提示している。経路探索装置170から経路探索結果が出力された際に、表示していた通過メッシュの情報を経路探索結果の情報に置き換えて、ディスプレイ上に表示し図18a、ユーザーに提示している。図18bにおいて、通過メッシュ1910の情報はハッチングによって表されている。実際のディスプレイ上では、例えば、地図にメッシュの境界線を表示し、図18bではハッチングによって表されている通過するメッシュに色を塗って強調して表示させる。以上で説明した第1の実施の形態の車載端末装置100は、以下のような作用効果を奏する。1車載端末装置100は、道路リンクの始端のノードIDおよびその緯度経度高度情報、図郭ノードフラグ、ならびに道路リンクの終端のノードIDおよびその緯度経度高度情報、図郭ノードフラグとコストデータとを含む道路データと、メッシュ管理テーブル上で規定されるメッシュIDとを対応付けた地図データ140を有する。また、リアルタイム情報を取得するリアルタイム情報取得装置190を有する。車載端末装置100は通過メッシュ算出装置160を有し、通過メッシュ算出装置160は、図6のステップS201~S203において、地図データ140に基づき、車載端末装置100の搭載された車両の出発地Sを含む出発地側メッシュMSと出発地側メッシュMSに隣接する通過メッシュM0との境界に位置する出発地側図郭ノードOから、車両の目的地Gを含む目的地側メッシュMGと目的地側メッシュMGに隣接する通過メッシュM0との境界に位置する目的地側図郭ノードDまでの最小コスト経路が含まれる複数の通過メッシュM0を取得する。複数の通過メッシュM0のうちの各通過メッシュM0において、各通過メッシュM0と各通過メッシュM0の少なくとも1つの隣接する通過メッシュM0とが各通過メッシュM0内の最小コスト経路の両端の始点図郭ノードおよび終点図郭ノードを共有するときの最小コスト経路のコストを表すメッシュコストは予め記憶装置に格納されている。車載端末装置100は比較装置200を有し、比較装置200は、図16の処理ステップS5022において、出発地側図郭ノードOから目的地側図郭ノードDまでの最小コスト経路に含まれる道路リンクのコストと、その道路リンクに関するリアルタイム情報とに基づき、その道路リンクを含む通過メッシュM0の図郭ノード間のメッシュコストの更新を行うか否かを判定する。更新を行うことが肯定判定されたとき、経路探索装置170は、再探索対象メッシュMRの図郭ノード間のメッシュコストを更新するとともに、更新されたメッシュコストに対応する再探索対象メッシュMR内の最小コスト経路を求める。経路探索装置170は、更新された通過メッシュの図郭ノード間のメッシュコストに基づき複数の通過メッシュM0を更新し、更新された複数の通過メッシュM0と再探索対象メッシュMR内の最小コスト経路とに基づき、出発地Sから目的地Gまでの経路を探索する。すなわち、予め計算したメッシュコストを用いる車載端末装置100では、リアルタイム交通情報から、通過メッシュのメッシュコストを更新するかどうかを判定し、肯定判定されたときこのメッシュコストを更新することで、経路探索前のコスト計算の段階で想定できない状況を考慮することができる。したがって、ユーザーは、リアルタイムな情報に対応した経路探索を効率的に実行できる。2車載端末装置100において、比較装置200は、統計交通情報または規制速度に基づく道路リンクのコストCMと、リアルタイム情報に基づく道路リンクのコストCRとの差分が所定の閾値180秒以上のとき、通過メッシュのメッシュコストの更新を行うことを肯定判定することとした。したがって、統計交通情報または規制速度に基づく道路リンクのコストCMと、リアルタイム情報に基づく道路リンクのコストCRとが略等しい場合、ユーザーは、経路探索装置170による再探索対象メッシュMRの通過メッシュのメッシュコストの更新を行うこと無く、経路探索装置170によって探索された出発地Sから目的地Gまでの経路を得ることができる。3出発地Sから離れた道路リンクほど、その道路リンクに関して出発時に取得したリアルタイム情報は、車両がその道路リンクを走行する時点で有効性が低下している可能性が考えられる。車載端末装置100において、所定の閾値は、車両が出発地Sを出発してからその道路リンクを走行するまでの予測経過時間に応じた関数としてもよいこととした。したがって、出発地Sから離れた道路リンクほど所定の閾値を大きくすることにより、リアルタイム情報に基づく通過メッシュのメッシュコストの更新が行われにくくなるようにすることができる。4車載端末装置100は、通過メッシュ算出装置160が算出したメッシュコストを、始点図郭ノードおよび終点図郭ノードと対応付けたメッシュコストデータ150をさらに有することとした。経路探索装置170は、メッシュコストデータ150に含まれるメッシュコストを参照して、複数の通過メッシュM0を取得する。したがって、経路探索時には予め生成されたメッシュコストデータ150を参照するだけで速やかに複数の通過メッシュM0を取得することができる。―第2の実施の形態―図19は本発明の第2の実施の形態における経路演算システムの全体構成を示す図であって、経路演算システムは図19aに示す車載端末装置1000と図19bに示すセンタ装置5000とを有する。車載端末装置1000は、目的地入力装置110、センサ類120の情報から自車の位置を算出する自車位置算出装置130、表示装置220、通信装置310を有する。センタ装置5000は、地図データ140、メッシュコストデータ150、通過メッシュ算出装置160、経路探索装置170、経路探索結果記憶装置180、リアルタイム情報取得装置190、比較装置200、メッシュコストデータ作成装置210、通信装置320を有する。メッシュコストデータ作成装置210は、図5に示す処理フローに従ってメッシュコストデータ150を作成する。車載端末装置1000とセンタ装置5000とは通信装置310および320によって接続されている。通信装置310および320は、携帯電話機、無線LANモジュール、PDAPersonalDigitalAssistanceあるいは車載端末装置1000またはセンタ装置5000と一体化されたモデムでも構わない。センタ装置5000が経路探索装置180を実行することで、経路探索時の車載端末1000の処理負荷を軽減できる。センタ装置5000で算出した経路を、通信装置320を介して、車載端末装置1000へ送付される。車載端末装置1000は、通信装置310を介して、目的地入力装置110からの目的地情報、経路探索タイプ情報、自車位置算出装置130からの自車位置情報を入力とし、センタ装置5000へ送信する。センタ装置5000は、通信装置320を介して、これらの情報を受け取り、経路探索装置170へ入力させる。センタ装置5000の経路探索結果記憶装置180に格納されている経路探索結果は、通信装置320を介して、車載端末装置1000へ送信される。車載端末装置1000は、通信装置310を介して、経路探索結果の情報を受信する。さらに経路探索結果を示す最適経路表示画面を表示装置220のディスプレイ上に表示し、ユーザーに提示する。以上で説明した第2の実施の形態の経路演算システムは、第1の実施の形態の車載端末装置100が奏する作用効果に加え、車載端末装置1000を第1の実施の形態の車載端末装置100よりも小規模な装置として実現できるという作用効果を奏する。―変形例―1上述の第1及び第2の実施形態において、メッシュコストデータ150は、経路探索タイプ毎のメッシュ内経路探索結果として得られるメッシュコストに関するコストデータ及びメッシュ内経路を構成する全ての道路リンクIDを含むこととしても良い。経路探索タイプによりメッシュ内経路探索を行うため、メッシュ内経路を構成する道路リンクの構成は経路探索タイプにより異なっても構わない。メッシュコストデータ150の構成図を図20aに示す。メッシュコストデータ150は、経路探索タイプ毎のメッシュコストに関するコストデータの他に、経路探索タイプ毎の経路探索結果として得られるメッシュ内経路を構成する道路リンク数と道路リンクIDとを含む。このとき道路リンクIDは、始点側の図郭ノードから順に格納される。メッシュコストデータ150には、最短経路および最小時間経路といった2種類のメッシュコストに関するコストデータが格納されているため、メッシュコスト種類数には2が設定されている。図20bは、経路探索タイプ最短経路に対応する経路と最小時間経路に対応する経路とを表している。最短経路を構成する道路リンク数は3、最短経路を構成する道路リンクIDは、始点側の図郭ノードから順に1001、1002、1003となる。最小時間経路を構成する道路リンク数は2、最小時間経路を構成する道路リンクIDは、始点側の図郭ノードから順に1004、1005となる。このメッシュコストデータ150を用いた場合、経路探索装置170にて実行されるステップS402図12においては、メッシュコストデータ150の経路探索タイプに応じて経路を構成する道路リンクが参照される。2上述の実施の形態の説明において、ステップS5022おける判定処理で用いられる閾値は、リンクコストがリンク旅行時間である場合について説明した。リンクコストがリンク長、すなわち距離である場合、およびリンクコストがリンクあたりの燃料消費量である場合、これらはともに時間の関数であるため、時間に換算することにより、ステップS5022おける判定処理を実行することができる。たとえば、リンク長を、対応する道路リンクの平均移動速度で除することにより、リンク長は時間へ換算される。また、たとえば、リンクあたりの燃料消費量に、予め定められた所定の係数を乗じることによって、リンクあたりの燃料消費量は時間へ換算される。3上述の実施の形態の説明においては、本発明を車載端末装置100または1000に適用した実施の形態を説明したが、車載端末装置100または1000は、たとえば、PNDPersonalNavigationDeviceのような着脱可能な装置であってもよい。"