経路演算装置
【課題】リアルタイムな情報に対応した経路探索を効率的に実行する。
【解決手段】経路探索前に隣接メッシュとの境界上の図郭ノードと他の図郭ノードとの間のメッシュ内の経路コストを予め計算し、メッシュコストデータを生成する。出発地から目的地までの経路探索の際に、出発地近傍の図郭ノードと目的地近傍の図郭ノードとの間の移動経路は、メッシュコストデータが最小となるように探索する。このようにして探索した移動経路に含まれる道路リンクのうち、メッシュ内の経路コストの計算に用いたリンクコストと、リアルタイム交通情報を考慮したリンクコストとの差が閾値以上の場合、そのリンクを含むメッシュにおける現況交通情報を考慮したメッシュ内の経路コストを再計算してメッシュコストデータを更新する。更新したメッシュコストデータに基づく再探索によって、メッシュ内経路を含む移動経路を特定する。
【解決手段】経路探索前に隣接メッシュとの境界上の図郭ノードと他の図郭ノードとの間のメッシュ内の経路コストを予め計算し、メッシュコストデータを生成する。出発地から目的地までの経路探索の際に、出発地近傍の図郭ノードと目的地近傍の図郭ノードとの間の移動経路は、メッシュコストデータが最小となるように探索する。このようにして探索した移動経路に含まれる道路リンクのうち、メッシュ内の経路コストの計算に用いたリンクコストと、リアルタイム交通情報を考慮したリンクコストとの差が閾値以上の場合、そのリンクを含むメッシュにおける現況交通情報を考慮したメッシュ内の経路コストを再計算してメッシュコストデータを更新する。更新したメッシュコストデータに基づく再探索によって、メッシュ内経路を含む移動経路を特定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体の経路を探索する経路演算装置に関する。
【背景技術】
【０００２】
経路演算装置は、例えば車両に搭載される車載端末装置または情報配信センタに配置されるセンタ装置に含まれ、デジタル化した地図データを用いて、出発地から目的地までの経路を計算する。さらに、経路演算装置は、算出した経路をユーザーに提供する。
【０００３】
従来の経路演算装置において、出発地から目的地までの経路を計算する方法は、例えば、特許文献１に記載されている。この方法は、地図をゾーンに分割し、ゾーン内のコストを、経路探索前に計算する。このとき、コストは、ゾーンを通過する方向別に計算される。この方向とは、例えば西から東、南から北などである。経路探索時には、（１）予め計算した方向別のコストを用いて、出発地から目的地までに通過するゾーンを決定する。次に、（２）通過するゾーン毎にゾーン内の経路を探索する。最後に、（３）通過するゾーンの経路を接続し、出発地から目的地までの経路が成り立つかどうかを判定し、成り立つ場合は、その経路を出力する。成り立たない場合は、出発地から目的地までの経路が成り立つまで、（１）から（３）を繰り返す。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−５５９１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１に記載の方法によると、経路探索前のコスト計算の段階で、想定できない状況を考慮できない。例えば、自動車事故が原因で引き起こされた渋滞の情報を取得した際に、この渋滞を回避したい場合でも、既にコストが計算されていると、この渋滞の情報を加味できない。
【課題を解決するための手段】
【０００６】
（１）請求項１に記載の経路演算装置は、道路リンクと地図を区画するメッシュデータとを対応付けた地図データと、メッシュとメッシュの少なくとも１つの隣接メッシュとがメッシュ内最小コスト経路の両端ノードの各々を共有するときのメッシュ内最小コスト経路のコストを表すメッシュコストとに基づき、移動体の始点を含む始点メッシュと始点メッシュに隣接する始点隣接メッシュとの境界に位置する第１境界ノードから移動体の終点を含む終点メッシュと終点メッシュに隣接する終点隣接メッシュとの境界に位置する第２境界ノードまでの境界ノード間接続最小コスト経路に含まれる複数の中継メッシュを取得する中継メッシュ取得手段と、境界ノード間接続最小コスト経路に含まれる区間道路リンクを含むメッシュにおいて、区間道路リンクのリンクコストの更新に基づく新たなメッシュ内最小コスト経路のコストを表すようにメッシュコストを更新し、更新されたメッシュコストに基づき複数の中継メッシュを更新し、更新された複数の中継メッシュと新たなメッシュ内最小コスト経路とに基づき、始点から終点までの移動経路を探索する経路探索手段とを備えることを特徴とする。
【発明の効果】
【０００７】
本発明によると、ユーザーは、リアルタイムな情報に対応した経路探索を効率的に実行できる。
【図面の簡単な説明】
【０００８】
【図１】本発明の車載端末装置の全体構成を示す図である。
【図２】地図データの構成を示す図である。
【図３】図郭ノードの例を示す図である。
【図４】メッシュコストデータの構成を示す図である。
【図５】メッシュコストデータ作成のための処理フローを示す図である。
【図６】通過メッシュ算出装置の処理フローを示す図である。
【図７】通過メッシュの例を示す図である。
【図８】出発地側の候補図郭ノードの例を示す図である。
【図９】候補図郭ノードを決定する処理フローを示す図である。
【図１０】メッシュコストデータを用いて経路探索する例を示す図である。
【図１１】経路探索結果記憶装置に格納される通過メッシュの構成を示す図である。
【図１２】経路探索装置の処理フローを示す図である。
【図１３】経路探索処理の概念図である。
【図１４】経路探索結果記憶装置に格納される経路探索結果の構成を示す図である。
【図１５】比較装置の処理フローを示す図である。
【図１６】再探索メッシュを判定する処理フローを示す図である。
【図１７】経路探索装置における再探索の概念図である。
【図１８】表示装置において経路探索結果の表示例を示す図である。
【図１９】経路探索システムを示す図である。
【図２０】メッシュコストデータに対応する道路リンクの構成を示す図である。
【発明を実施するための形態】
【０００９】
本発明を用いた経路演算装置の実施の形態を、図面を参照して説明する。
【００１０】
―第１の実施の形態―
図１は本発明の第１の実施の形態における車載端末装置１００の全体構成を示す図である。車載端末装置１００は、目的地入力装置１１０、車載端末装置１００の搭載された車両の自車位置算出装置１３０、地図データ１４０、メッシュコストデータ１５０、通過メッシュ算出装置１６０、経路探索装置１７０、経路探索結果記憶装置１８０、リアルタイム情報取得装置１９０、比較装置２００、表示装置２２０を有する。
【００１１】
また、車載端末装置１００とセンサ類１２０とがCANなどの車載ネットワークを介して接続されている。
【００１２】
目的地入力装置１１０は、ユーザーが、車載端末装置１００の例えばリモコンのようなユーザーインターフェースを通して入力する目的地情報及び経路探索タイプ情報を受け付ける。目的地情報は、通過メッシュ算出装置１６０へ提供される。ユーザーは、目的地情報を入力する際、目的地の住所、カテゴリ、電話番号等をキーに、目的地のＰＯＩを検索し、設定する。ＰＯＩとは、Point Of Interestの略で、店舗情報などの地点に関する情報である。
【００１３】
経路探索タイプ情報は、経路探索条件の種類を表す情報である。経路探索タイプ情報の種類としては、例えば、目的地まで最小の時間での到着を目指す「最小所要時間経路」、目的地まで最小の燃料消費量での到着を目指す「最小燃料消費量経路」、目的地まで距離を最短にすることを目指す「最短経路」がある。通過メッシュ算出装置１６０、経路探索装置１７０は、目的地入力装置１１０で受付けた経路探索タイプに対応する指標を最小化するように実行される。この指標とは、すなわちコストであり、例えば、経路探索タイプ情報が「最小所要時間経路」の場合は、目的地までの旅行時間、経路探索タイプ情報が「最小燃料消費量経路」の場合は、目的地までの燃料消費量、経路探索タイプ情報が「最短経路」の場合は、目的地までの距離である。
【００１４】
センサ類１２０は、ＧＰＳ、車速パルス、角速度センサなどをいう。このセンサを用いることで、車両の位置、車速、角速度を計測することができる。これらの情報は自車位置算出装置１３０へ提供される。
【００１５】
自車位置算出装置１３０は、センサ類１２０の情報から、自車の位置を算出する。この算出には、公知の技術であるカルマンフィルタやデッドレコニングが用いられる。算出した自車位置の情報は、通過メッシュ算出装置１６０を介して経路探索装置１７０へ提供される。自車位置情報は、例えば緯度・経度で表される。
【００１６】
地図データ１４０は、ハードディスク、フラッシュメモリ等の記憶装置に格納され、道路データ、ＰＯＩの情報を含む。通過メッシュ算出装置１６０及び経路探索装置１７０の地図領域に該当する道路情報、ＰＯＩの情報を提供する。
【００１７】
地図データ１４０の構成図を図２に示す。図２（ａ）は、地図データ１４０に格納されている道路データの構成を示している。道路データはノードからノードまでのリンク単位で構成される。ノードには、道路の交差点に設けられるような通常のノードと、メッシュの境界に設けられる図郭ノードとがある。通常のノードに対して、図郭ノードは、図郭ノードフラグで区別される。例えば、ノードが図郭ノードの場合は図郭ノードフラグに「１」、通常のノードの場合は図郭ノードフラグに「０」が設定される。各道路データは、道路を特定するリンクＩＤ、その道路リンクの存在するメッシュＩＤ、道路リンクの始端のノードＩＤとその緯度・経度・高度情報、図郭ノードフラグ、道路リンクの終端のノードＩＤとその緯度・経度・高度情報、図郭ノードフラグ、道路種別、規制情報、コストデータで構成される。規制情報は、制限速度情報、一方通行情報などである。なお、ノード間のリンク上に補間点が規定される場合、ノードと補間点との間および補間点同士の間にリンクを規定してもよい。また、道路リンクの高度は、始端・終端ノードの高度情報ではなく、勾配情報で表してもよい。
【００１８】
ここで、メッシュとは、地図を緯度・経度に基づいて網の目状に区画する方法により得られる単位区画である。２次メッシュとは緯度差５分、経度差７分３０秒で区画されて得られる一辺の長さが約１０ｋｍのメッシュである。また３次メッシュは２次メッシュを緯度方向および経度方向に１０等分して得られるメッシュであり、緯度差３０秒、経度差４５秒で、一辺の長さが約１ｋｍである。メッシュＩＤにより、メッシュを特定することができる。
【００１９】
ここで、道路種別とは、道路リンクの種類を表す情報である。道路種別には、例えば、道路リンクが都市間高速道の場合は「０」、都市内高速道の場合は「１」、国道の場合は「２」、そのほかの道路の場合は「３」が設定される。
【００２０】
ここで、コストデータとは、経路探索の際に使用される道路リンクに関連した重みである。例えば、コストデータの例に、統計交通情報がある。この統計交通情報は、リアルタイム情報取得装置２００にて取得し、蓄積した道路の渋滞情報を統計処理することで作成される。この統計処理とは、平日、休日などの日種毎、及び0:00、23:00などの時間毎に作成される。図２（ｄ）に、コストデータの構成を示す。
【００２１】
ここで、図郭ノードは、通常のノード間の道路リンクがメッシュを跨ぐ場合に、地図データ１４０内での管理上、道路リンクをメッシュの境界で分割するためのノードである。一端または両端が図郭ノードで規定されることにより、道路リンクが、メッシュをまたいで存在しないこととなる。図３に図郭ノードの例を示す。通常のノード間の道路リンクがメッシュＩＤ００１および００２の隣接するメッシュに跨がる場合（図３(ａ)）、メッシュの境界線で道路リンクを分割し、分割後の道路リンクを各メッシュで管理する。このとき、分割位置を図郭ノードとして地図データ１４０内に格納する。また、メッシュ境界における同じ道路リンク上の同じ分割位置に規定される一対の図郭ノードは、隣接するメッシュ間で共通のノードＩＤ００１を持つ。そのため、車載端末装置１００は、その道路リンクによってメッシュＩＤ００１のメッシュがどのメッシュに接続しているかを、知ることができる（図３（ｂ））。
【００２２】
図２（ｂ）は、図２（ａ）に示した道路データとともに地図データ１４０に含まれるメッシュ管理テーブルを示している。このメッシュ管理テーブルには、メッシュＩＤおよびそのメッシュの左下、左上、右下、右上のそれぞれの頂点の座標（緯度・経度）が設定されている（図２（ｃ）参照）。
【００２３】
メッシュコストデータ１５０は、後述する第２の実施の形態と同様に外部のセンタ装置等で生成された後、予め車載端末装置１００のハードディスク、フラッシュメモリ等の記憶装置に格納され、メッシュ境界の図郭ノード同士を結んだ経路のコストを表す。
【００２４】
通過メッシュ算出装置１６０は、目的地入力装置１１０からの目的地情報、自車位置算出装置１３０からの自車位置情報、メッシュコストデータ１５０からメッシュ内の図郭ノード同士を結んだ経路のコストを取得し、通過メッシュを決定する。さらに、通過メッシュの地図データを地図データ１４０から取得してメモリに展開する。
【００２５】
経路探索装置１７０は、通過メッシュ算出装置１６０によりメモリに展開された地図データを取得し、通過メッシュ内部の経路を算出する。算出した通過メッシュ内部の経路を、経路探索結果記憶装置１８０へ格納する。
【００２６】
経路探索結果記憶装置１８０は、ハードディスク、フラッシュメモリ等の記憶装置であって、経路探索装置１７０で出力された経路と、通過メッシュ算出装置１６０で算出した通過メッシュの情報を記憶している。
【００２７】
リアルタイム情報取得装置１９０は、例えばVICSセンター（登録商標）のような交通情報サービスセンターから全国の主要な道路の道路リンク毎の旅行時間を受信する。情報の更新周期は、予め定められた時間間隔とする。リンク毎の旅行時間は、例えば、道路リンク毎に道路に車両検知装置を設けて、道路リンク毎の走行に要した時間を測定すること、或いはプローブカーを道路リンク毎に時間測定しながら走行させることで得られる。
【００２８】
比較装置２００は、経路探索結果記憶装置１８０に格納されている経路探索結果に含まれる道路リンクのコストと、リアルタイム情報取得装置１９０にて取得したリアルタイム情報から算出される道路リンクのコストとを比較して、再探索が必要なメッシュがあるか否かを判定する。再探索が必要な場合は、再探索の必要なメッシュの情報を経路探索装置１７０へ送信する。
【００２９】
経路探索装置１７０は、再探索が必要なメッシュの情報を比較装置２００から受け取った場合、再探索対象のメッシュの始点側の図郭ノードから終点側の図郭ノードまでの経路を、リアルタイム情報取得装置１９０で取得したリアルタイム情報を使用して、再び探索する。
【００３０】
表示装置２２０は、液晶ディスプレイ等であり、経路探索結果記憶装置１８０からの経路探索結果を表示する。
【００３１】
以下、メッシュコストデータ１５０、通過メッシュ算出装置１６０、経路探索装置１７０、経路探索結果記憶装置１８０、比較装置２００の構成及び処理フローを説明する。
【００３２】
メッシュコストデータ１５０の構成図を図４に示す。図４（ａ）は、メッシュコストデータ１５０に格納されているメッシュ毎のコストデータの構成例を示している。メッシュコストデータ１５０においては、メッシュ内の特定道路種別の図郭ノード同士を結ぶ経路の数ｎと、各経路に対応する始点の図郭ノードＩＤおよび終点の図郭ノードＩＤ、ならびにその経路のコストデータとがメッシュ単位に管理されている。各経路は、図郭ノード同士の組合せを始点・終点として地図データ１４０を用いて経路探索した結果であり、この経路のコストデータは、メッシュコストデータ１５０に格納される。このコストデータは、目的地入力装置１１０にて入力できる経路探索タイプ情報毎の経路探索結果のコストデータとコスト数とから構成される。図４（ｂ）に示すメッシュＩＤ「００１」の図郭ノードＩＤ１０１を始点、図郭ノードＩＤ１０２を終点としたときの「最短経路」の経路探索結果とそのコストが、図４（ａ）に表すコストデータとして管理されている。図４（ａ）の「最小時間経路」、「最小燃料消費量経路」も同様に、メッシュＩＤ「００１」の図郭ノードＩＤ１０１を始点、図郭ノードＩＤ１０２を終点とし、経路探索を実行して算出される。同様にして、詳細を図示することは省略しているが、同じメッシュにおける図郭ノードＩＤ１０１を始点、図郭ノードＩＤ１０３を終点としたときの「最短経路」の経路探索結果とそのコストが管理されている。このようにして、図示を省略しているが、同じメッシュにおける図郭ノードＩＤ１０１〜１０３のうちのいずれか２つを始点および終点としたときの各組み合わせ毎、すなわち６通りの経路（ｎ＝６）の各々について、「最短経路」の経路探索結果とそのコストが管理されている。後述するように、「最短経路」、「最小時間経路」および「最小燃料消費量経路」のうちから、目的地入力装置１１０にて入力された経路探索タイプ情報に対応する最小コスト経路が抽出される。その最小コスト経路のコストデータに基づき、メッシュ内の図郭ノード同士を結ぶ経路の最小コストが定まる。図４（ａ）に示すメッシュ毎のコストデータにおいては、上述したメッシュＩＤ「００１」のコストデータに続いて、詳細を図示することは省略しているが、メッシュＩＤ「００２」のコストデータが管理されている。このようにして、メッシュ毎のコストデータがメッシュコストデータ１５０に格納されている。
【００３３】
外部のセンタ装置でメッシュコストデータ１５０を作成するための処理フローを図５に従って説明する。この処理は、経路探索の前段階の処理であり、地図データを入力する。
【００３４】
はじめに、地図データの全メッシュを処理したかを判定する（ステップＳ１０１）。処理した場合（ステップＳ１０１でＹｅｓ）、処理を終了する。処理していない場合（ステップＳ１０１でＮｏ）、対象のメッシュ内の図郭ノードで、特定の道路種別のものを抽出する（ステップＳ１０２）。例えば、都市間高速、都市内高速および国道を抽出する。これは、全ての道路種別の図郭ノードを扱うと、ノード数が増えてしまうため、道路種別に基づいてノード数を絞ることとしたものである。次に、対象メッシュ内のステップＳ１０２で抽出した全ての図郭ノードを処理したかどうかを判定する（ステップＳ１０３）。処理した場合（ステップＳ１０３でＹｅｓ）、ステップＳ１０１へ進む。処理していない場合（ステップＳ１０３でＮｏ）、処理中の図郭ノードを対象図郭ノードとし、ステップＳ１０４へ進む。このとき対象図郭ノードＩＤを「Ｉ」とする。ステップＳ１０４では、対象図郭ノードＩＤ「Ｉ」以外の対象メッシュ内の図郭ノードＩＤを全て処理したかどうかを判定する（ステップＳ１０４）。処理した場合（ステップＳ１０４でＹｅｓ）、ステップＳ１０３へ進む。処理していない場合（ステップＳ１０４でＮｏ）、対象図郭ノードＩＤ「Ｉ」以外の対象メッシュ内の図郭ノードＩＤ「Ｊ」（ＩとＪとは相異なる）を抽出し、経路探索する（ステップＳ１０５）。このとき、対象図郭ノードＩＤ「Ｉ」を始点、図郭ノードＩＤ「Ｊ」を終点とした経路を算出する。経路は、公知の技術であるダイクストラ法(Dijkstra's algorithm)を用いて算出する。探索に用いるコストは、目的地入力装置１１０で設定できる経路探索タイプを用い、経路探索も経路探索タイプ毎に実行する。次に、ステップＳ１０５で用いた、始点の図郭ノードＩＤ、終点の図郭ノードＩＤ及び経路探索にて算出されたコストを、メッシュコストとしてメッシュコストデータ１５０へ格納する（ステップＳ１０６）。ただし、特定道路種別の図郭ノード同士を結ぶ道路リンクが、対象メッシュ内に存在しない場合は、コストの項目には、道路リンクが存在しないことを判定できる値、例えば「−１」が入力される。ステップＳ１０６の終了後、ステップＳ１０４へ進む。
【００３５】
図７に示すように、通過メッシュ算出装置１６０では、経路探索の際に、出発地Ｓ側の図郭ノードＯから目的地Ｇ側の図郭ノードＤまで、どのメッシュＭを通過するのかを決定する。この通過する複数のメッシュＭを通過メッシュＭ０と定義する。出発地側図郭ノードＯは、出発地Ｓを含む出発地側メッシュＭＳとそれに隣接する通過メッシュＭ０との境界に位置する。目的地側図郭ノードＤは、目的地Ｇを含む目的地側メッシュＭＧとそれに隣接する通過メッシュＭ０との境界に位置する。図７において、斜線のメッシュが、出発地Ｓ側の図郭ノードＯと目的地Ｍ側の図郭ノードＤとを結ぶ通過メッシュＭ０である。通過メッシュ算出装置１６０では、メッシュコストデータ１５０に格納されたメッシュコストを用いて、通過メッシュＭ０に含まれるメッシュＭ毎に図郭ノードＯから図郭ノードＤまで経路探索を行う。なお、図７において、各通過メッシュＭ０内の図郭ノード間を線分で結んでいるが、こうした表記は、その図郭ノード間を結ぶ経路が存在することを説明するための便宜上行ったものであり、その線分自体が上述したメッシュコストデータ１５０に含まれるものではない。図７以降の図面においても同様である。
【００３６】
通過メッシュ算出装置１６０の処理フローを図６にしたがって説明する。はじめに、出発地と目的地周辺の候補図郭ノードを抽出する（ステップＳ２０１）。候補図郭ノードとは、出発地及び目的地の周辺に存在し、出発地及び目的地からたどり着ける図郭ノードである。出発地及び目的地の周辺に存在する候補図郭ノードとは、候補図郭ノードが出発地及び目的地の属するメッシュに含まれる場合のみならず、候補図郭ノードが、出発地または目的地の属するメッシュの隣接するメッシュに含まれる場合をも意味する。図８に出発地Ｓ側の候補図郭ノードＯ１〜Ｏ４の例を示す。図郭ノードＯ１及びＯ２は、出発地Ｓのある道路リンクＬ１２が接続しているため、候補図郭ノードとなる。しかし、図郭ノードＯ３及びＯ４は、道路リンクＬ３４上に位置し、出発地Ｓとは道路リンクで接続されていないため、候補図郭ノードにならない。
【００３７】
ステップＳ２０１の詳細な処理フローを図９に従って説明する。はじめに、出発地周辺及び、目的地周辺の図郭ノードを抽出する（ステップＳ３０１）。ここでは、出発地及び目的地の属するメッシュの図郭ノードを全て抽出する。次に、すべての抽出したすべての図郭ノードを処理したか否かを判定する（ステップＳ３０２）。全てについて処理していない場合（Ｓ３０２でＮｏ）、抽出した図郭ノードまで経路探索し、その抽出した図郭ノードが候補図郭ノードかどうかを判定する（ステップＳ３０３）。図８の例で説明すると、出発地Ｓから、出発地Ｓを含む出発地側メッシュＭＳとその隣接メッシュとの境界に位置する図郭ノードＯ１，Ｏ２，Ｏ３，Ｏ４まで、地図データ１４０を用いて経路探索する。出発地Ｓから図郭ノードＯ１，Ｏ２，Ｏ３，Ｏ４まで道路のネットワークデータがある場合、候補図郭ノードと判定する（図８の例では図郭ノードＯ１，Ｏ２が該当する）。出発地から図郭ノードまで道路のネットワークデータがない場合、または経路探索の結果、コストが予め定めた値よりも大きい場合、その抽出した図郭ノードは候補図郭ノードには選ばれない（図８の例ではＯ３，Ｏ４が該当する）。目的地側の図郭ノードの場合は、目的地から図郭ノードまで経路探索する。全てについて処理した場合（Ｓ３０２でＹｅｓ）、候補図郭ノードが、目的地側と出発地側にそれぞれ１個以上存在するか否かを判定する（ステップＳ３０４）。候補図郭ノードが存在する場合（Ｓ３０４でＹｅｓ）、処理を終了する。候補図郭ノードが存在しない場合（Ｓ３０４でＮｏ）、図郭ノードを探索する範囲を広げて、ステップＳ３０２へ進む（ステップＳ３０５）。探索範囲を広げるということは、すなわち、隣接するメッシュをも探索対象とするということを意味する。広げた探索範囲の中で、出発地及び目的地の周辺のメッシュの図郭ノードを新たに抽出する。
【００３８】
図６の処理フローに戻り説明する。ステップＳ２０１で候補図郭ノードを決定した後に、出発地側及び目的地側の全ての候補図郭ノードの組合せを処理したかを判断する（ステップＳ２０２）。全ての図郭ノードの組合せを処理した場合（ステップＳ２０２でＹｅｓ）、処理を終了する。
【００３９】
全ての図郭ノードの組合せを処理していない場合（ステップＳ２０２でＮｏ）、メッシュコストデータ１５０に含まれる「最短経路」、「最小時間経路」および「最小燃料消費量経路」のうちから、目的地入力装置１１０にて入力された経路探索タイプ情報に対応する最小コスト経路のコストデータが、メッシュコストデータ１５０から最小コストとして抽出し、経路探索をする（ステップＳ２０３）。図１０にステップＳ２０３の例を示す。出発地側の候補図郭ノードＯ１、Ｏ２と目的地側の候補図郭ノードＤ１、Ｄ２との組合せは、Ｏ１からＤ１，Ｏ１からＤ２，Ｏ２からＤ１、Ｏ２からＤ２の4つである。ここでは、メッシュコストデータ１５０に格納されたメッシュコストを用いて、候補図郭ノードＯ１またはＯ２を出発地とし、候補図郭ノードＤ１またはＤ２を目的地として経路探索する。図１０は、候補図郭ノードＯ１及びＤ２の組合せを出発地及び目的地の組合せとする例と、候補図郭ノードＯ２及びＤ１の組合せを出発地及び目的地の組合せとする例とを示している。候補図郭ノードＯ１を出発地、候補図郭ノードＤ２を目的地としたときの他経路探索が成り立つ。一方、候補図郭ノードＯ２を出発地、候補図郭ノードＤ１を目的地としたときの経路探索は、途中のメッシュ内の図郭ノードＮ１から図郭ノードＮ２までを接続する経路がメッシュ内に無いため、成立しない。したがって、この例では、候補図郭ノードＯ１からＤ２までの間の図郭ノードを結んだ経路が含まれる複数のメッシュが通過メッシュとなる。
【００４０】
通過メッシュを決定したとき、出発地点側の図郭ノード、および目的地側の図郭ノードの情報を含む通過メッシュの情報を経路探索結果記憶装置１８０に記憶する（ステップＳ２０４）。図１１（ａ）に、ステップＳ２０４で経路探索結果記憶装置１８０に格納される通過メッシュの情報の構成図を示す。複数組の通過メッシュがある場合、経路探索結果記憶装置１８０はそれら複数組の通過メッシュの情報を記憶する。通過メッシュの情報は、出発地側の図郭ノードＩＤ，目的地側の図郭ノードＩＤ、通過メッシュ数、ステップＳ２０３の経路探索で算出したメッシュコストの総和と、詳細な通過メッシュ情報ＤＭＭを含む。詳細な通過メッシュＤＭＭに含まれる情報を、図１１（ｂ）の例を用いて説明する。詳細な通過メッシュ情報ＤＭＭは、通過メッシュ数分記憶され、通過メッシュのＩＤ(001)、始点図郭ノードＩＤ(101)，終点図郭ノードＩＤ(102)、およびコストデータ１５０に格納されているコストデータであって、始点図郭ノードＩＤ(101)と終点図郭ノードＩＤ(102)との間のメッシュコスト(200m)を含む。通過メッシュには、図郭ノードは２つ存在する。これらの図郭ノードはステップＳ２０３にて求めた経路の両端に位置しており、出発地に最も近い始点図郭ノード(101)を出発地側図郭ノード、目的地に最も近い終点図郭ノード(102)を目的地側図郭ノードと定義する。図１１（ａ）における詳細な通過メッシュＤＭＭには、通過メッシュＩＤ002についてのデータも含まれている。しかし、図１１（ｂ）の例においては通過メッシュが１つだけのため、これに対応して図１１（ａ）における詳細な通過メッシュＤＭＭには、通過メッシュのＩＤ001のデータのみが格納されることとなる。
【００４１】
次に、経路探索装置１７０を図１２の処理フローに従い説明する。図１３に図１２の処理フローに従って実行される経路探索処理の概念図の一例を示す。はじめに最小コストの通過メッシュ情報を取得する（ステップＳ４０１）。この処理では、通過メッシュ算出装置１６０の処理によって経路探索結果記憶装置１８０に格納された通過メッシュ情報の中で、コスト総和の最小のものを取得する。このとき図１３（ａ）のように、出発地から目的地までの間の図郭ノードＮが含まれる通過メッシュが選ばれる。次に、取得した通過メッシュに含まれるメッシュ毎に、出発地側図郭ノードＯを出発地、目的地側図郭ノードＤを目的地として経路探索を実施する（ステップＳ４０２）。この経路探索処理は、地図データ１４０に格納されている道路ネットワークデータのうち、処理対象のメッシュのデータをメモリ上に展開し、道路リンク毎のコストデータを使って経路探索することによって行われる。経路探索した結果は、例えば図１３（ｂ）のように表される。全てのメッシュに対して経路探索が終了した後、経路探索結果を経路データとして経路探索結果記憶装置１８０に格納する（ステップＳ４０３）。図１４は、経路探索結果記憶装置１８０に格納される経路データの構成の一例を表している。図１４（ｂ）の例を用いて、図１４（ａ）に示す経路データ構成を説明する。経路データは、通過メッシュ毎に、始点図郭ノードＩＤ（１０１）、終点図郭ノードＩＤ（１０２）、経路を構成する道路リンク数（３）、経路を構成する道路リンクＩＤ（１００１，１００２，１００３）およびそのコスト（３０ｍ、５０ｍ、２０ｍ）を含む。
【００４２】
次に、比較装置２００の処理フローについて、図１５を用いて説明する。この比較装置２００の処理フローは、リアルタイム情報を取得したタイミング、または予め定められた時間間隔で実行される。はじめに、経路探索結果記憶装置１８０から経路探索結果を取得する（ステップＳ５０１）。次に、リアルタイム情報取得装置１９０で取得した情報と、経路探索結果とを比較して、再探索が必要か否かを判定する（ステップＳ５０２）。経路探索装置１８０でメッシュコストデータの最小時間を用いて、経路探索をしたとき、コストは道路リンクを通過する旅行時間となる。メッシュコストデータ作成時に考慮される旅行時間は、過去の旅行時間を統計処理したものである。しかし、過去の交通情報でカバーできない状況が起きたとき、再探索が必要になる。例えば、経路上に、交通事故が発生し、渋滞が引き起こされたという情報を、リアルタイム情報取得装置１９０にて取得した場合、再度この渋滞を避けるように再探索をする必要がある。この再探索するか否かの判定をステップＳ５０２で行う。ステップＳ５０２においては、例えば、取得したリアルタイム交通情報の旅行時間と、過去の交通情報を統計処理した統計交通情報の旅行時間との差分が閾値以上であることが検出された場合、または事故発生情報を取得した場合に肯定判定される。再探索すると判定した場合（ステップＳ５０２でＹｅｓ）、経路探索装置１７０へ再探索を要求し、処理を終了する（ステップＳ５０３）。再探索を要求する際には、再探索が必要な通過メッシュのＩＤを経路探索装置１７０へ送信する。経路探索装置１７０では、後述するように、この再探索が必要な通過メッシュについて再探索を実行する。一方、再探索するか否かの判定において、再探索する必要がないと判定した場合（ステップＳ５０２でＮｏ）、処理を終了する。
【００４３】
図１６は、ステップＳ５０２の処理の詳細を、ステップＳ５０２１〜Ｓ５０２４として示した図である。以下、図１６の処理フローについて説明する。ただし、ステップＳ５０１およびＳ５０３については、図１５と同様であるため、説明を省略する。ステップＳ５０１における経路探索結果取得の後、ステップＳ５０２１において、後述するステップＳ５０２２およびＳ５０２３の処理を、ステップＳ５０１にて取得した経路が含まれる全てのメッシュについて行ったか否か、判定する。肯定判定の場合は処理をステップＳ５０２４へ進める。否定判定の場合は、ステップＳ５０２２において、リアルタイム情報取得装置１９０にて取得したリアルタイム情報のコストと、経路探索結果記憶装置１８０に格納されている経路探索結果の道路リンクのコストとの差が、閾値以上かを判定する。ステップＳ５０２２では、処理対象メッシュにおいて、経路探索結果記憶装置１８０に格納されているリンクＩＤに該当するリンクのリアルタイム情報のコスト（ＣＲ）を取得する。さらに経路探索結果記憶装置１８０に格納されているリンクＩＤのリンクのコスト（ＣＭ）を取得する。全ての経路上の道路リンクを処理し、リアルタイム情報のコストと経路探索結果のコストとの差が閾値以上の場合（ステップＳ５０２２でＹｅｓ）、その道路リンクの存在するメッシュを再探索要求対象とする（ステップＳ５０２３）。処理をステップＳ５０２１へ戻す。
【００４４】
処理対象メッシュにおいて、リアルタイム情報と経路探索結果とのコスト差が閾値以上に該当する道路リンクが存在しない場合（ステップＳ５０２２でＮｏ）、処理をステップＳ５０２１へ戻す。ステップＳ５０２１における判定が肯定判定の場合、ステップＳ５０２３において再探索要求対象とされたメッシュがあるか否かを判定する（ステップＳ５０２４）。肯定判定の場合、処理を上述したステップＳ５０３を経て終了し、否定判定の場合は直ちに処理を終了する。例えば、コストＣＲは、リアルタイム交通情報に基づいて車両が道路リンクを走行する際のリンク旅行時間、コストＣＭは、統計交通情報または規制速度に基づいて車両がその道路リンクを走行する際のリンク旅行時間となる。このとき、コストＣＲと、コストＣＭから算出する閾値とを比較する。予め定められる閾値は、コストＣＭを係数（ｋ）倍したコストｋ＊ＣＭとする。例えば、コストをリンク旅行時間としたときＣＭが６０秒で係数ｋを３としたとき、閾値は１８０秒となる。リアルタイム交通情報によるコストＣＲが２００秒の場合、閾値１８０秒と比較して大きいため、この道路リンクに存在しているメッシュは再探索対象と判定する。この閾値は、車両が出発地Ｓを出発してからその道路リンクを走行するまでの予測経過時間に応じた関数でもよい。
【００４５】
次に、経路探索装置１７０の再探索処理を説明する。再探索処理の概念図を図１７に示す。図１７に示すように、経路探索処理１７０による再探索が実行される際、出発地Ｓに最も近い候補図郭ノードＯ１から目的地Ｇに最も近い候補図郭ノードＤ２までの、図郭ノードＮを経由する通過メッシュＭＯが既に決定されている。経路探索装置１７０では、通過メッシュＭＯのうち、再探索対象メッシュＭＲ内の最小コスト経路を探索する。この探索は、再探索対象メッシュＭＲの出発地側図郭ノードＯＲから再探索対象メッシュＭＲの目的地側図郭ノードＤＲまでの経路探索を、リアルタイム情報取得装置１９０から入力されるリアルタイム情報を用いて実行する。探索に用いるコストは、目的地入力装置１１０で設定できる経路探索タイプを用いる。このとき地図データ１４０を使用する。こうして、経路探索結果記憶装置１８０に格納されている通過メッシュＭＯ中で、比較装置２００で判定した再探索対象メッシュＭＲの最小コスト経路を更新する。この経路探索結果として得られる再探索された経路ＲＲは、はじめにメッシュコストデータ１５０を計算したときに算出した経路と異なっても構わない。さらに、再探索対象のメッシュＭＲのＯＲからＤＲまでのメッシュコストデータを、最小コスト経路のコストデータで更新する。更新した後、通過メッシュＭＯのメッシュコスト総和も更新する。全ての再探索対象のメッシュＭＲ内の通過メッシュの通過する図郭ノード間の最小コスト経路のコストデータを、その図郭ノード間のメッシュコストデータとして更新した後、経路探索装置１７０においてステップＳ４０１の処理が実行される。このとき、更新したメッシュコストを用いて経路探索をする。
【００４６】
表示装置２２０では、経路探索結果記憶装置１８０の経路探索結果を示す最適経路表示画面を、ディスプレイ上に表示し、ユーザーに提示する。表示例を図１８に示す。図１８（ａ）は、出発地Ｓから目的地Ｇまで経路探索したときに、地図上に経路探索結果記憶装置１８０の経路探索結果を最適経路１８１０として重畳表示し、さらに、吹き出し１８２０を用いて目的地までのコスト「所要時間２０分」を提示している。
【００４７】
また、他の表示の例を図１８（ｂ）に示す。この例は、通過メッシュ算出装置１６０から通過メッシュを算出し、経路探索装置１７０の処理中に、通過メッシュ１９１０の情報をディスプレイ上に表示し（図１８（ｂ））、ユーザーに提示している。さらに、吹き出し１９２０を用いて「通過メッシュ」を提示している。経路探索装置１７０から経路探索結果が出力された際に、表示していた通過メッシュの情報を経路探索結果の情報に置き換えて、ディスプレイ上に表示し（図１８（ａ））、ユーザーに提示している。図１８（ｂ）において、通過メッシュ１９１０の情報はハッチングによって表されている。実際のディスプレイ上では、例えば、地図にメッシュの境界線を表示し、図１８（ｂ）ではハッチングによって表されている通過するメッシュに色を塗って強調して表示させる。
【００４８】
以上で説明した第１の実施の形態の車載端末装置１００は、以下のような作用効果を奏する。
（１）車載端末装置１００は、道路リンクの始端のノードＩＤおよびその緯度・経度・高度情報、図郭ノードフラグ、ならびに道路リンクの終端のノードＩＤおよびその緯度・経度・高度情報、図郭ノードフラグとコストデータとを含む道路データと、メッシュ管理テーブル上で規定されるメッシュＩＤとを対応付けた地図データ１４０を有する。また、リアルタイム情報を取得するリアルタイム情報取得装置１９０を有する。車載端末装置１００は通過メッシュ算出装置１６０を有し、通過メッシュ算出装置１６０は、図６のステップＳ２０１〜Ｓ２０３において、地図データ１４０に基づき、車載端末装置１００の搭載された車両の出発地Ｓを含む出発地側メッシュＭＳと出発地側メッシュＭＳに隣接する通過メッシュＭ０との境界に位置する出発地側図郭ノードＯから、車両の目的地Ｇを含む目的地側メッシュＭＧと目的地側メッシュＭＧに隣接する通過メッシュＭ０との境界に位置する目的地側図郭ノードＤまでの最小コスト経路が含まれる複数の通過メッシュＭ０を取得する。複数の通過メッシュＭ０のうちの各通過メッシュＭ０において、各通過メッシュＭ０と各通過メッシュＭ０の少なくとも１つの隣接する通過メッシュＭ０とが各通過メッシュＭ０内の最小コスト経路の両端の始点図郭ノードおよび終点図郭ノードを共有するときの最小コスト経路のコストを表すメッシュコストは予め記憶装置に格納されている。車載端末装置１００は比較装置２００を有し、比較装置２００は、図１６の処理ステップＳ５０２２において、出発地側図郭ノードＯから目的地側図郭ノードＤまでの最小コスト経路に含まれる道路リンクのコストと、その道路リンクに関するリアルタイム情報とに基づき、その道路リンクを含む通過メッシュＭ０の図郭ノード間のメッシュコストの更新を行うか否かを判定する。更新を行うことが肯定判定されたとき、経路探索装置１７０は、再探索対象メッシュＭＲの図郭ノード間のメッシュコストを更新するとともに、更新されたメッシュコストに対応する再探索対象メッシュＭＲ内の最小コスト経路を求める。経路探索装置１７０は、更新された通過メッシュの図郭ノード間のメッシュコストに基づき複数の通過メッシュＭ０を更新し、更新された複数の通過メッシュＭ０と再探索対象メッシュＭＲ内の最小コスト経路とに基づき、出発地Ｓから目的地Ｇまでの経路を探索する。すなわち、予め計算したメッシュコストを用いる車載端末装置１００では、リアルタイム交通情報から、通過メッシュのメッシュコストを更新するかどうかを判定し、肯定判定されたときこのメッシュコストを更新することで、経路探索前のコスト計算の段階で想定できない状況を考慮することができる。したがって、ユーザーは、リアルタイムな情報に対応した経路探索を効率的に実行できる。
【００４９】
（２）車載端末装置１００において、比較装置２００は、統計交通情報または規制速度に基づく道路リンクのコストＣＭと、リアルタイム情報に基づく道路リンクのコストＣＲとの差分が所定の閾値１８０秒以上のとき、通過メッシュのメッシュコストの更新を行うことを肯定判定することとした。したがって、統計交通情報または規制速度に基づく道路リンクのコストＣＭと、リアルタイム情報に基づく道路リンクのコストＣＲとが略等しい場合、ユーザーは、経路探索装置１７０による再探索対象メッシュＭＲの通過メッシュのメッシュコストの更新を行うこと無く、経路探索装置１７０によって探索された出発地Ｓから目的地Ｇまでの経路を得ることができる。
【００５０】
（３）出発地Ｓから離れた道路リンクほど、その道路リンクに関して出発時に取得したリアルタイム情報は、車両がその道路リンクを走行する時点で有効性が低下している可能性が考えられる。車載端末装置１００において、所定の閾値は、車両が出発地Ｓを出発してからその道路リンクを走行するまでの予測経過時間に応じた関数としてもよいこととした。したがって、出発地Ｓから離れた道路リンクほど所定の閾値を大きくすることにより、リアルタイム情報に基づく通過メッシュのメッシュコストの更新が行われにくくなるようにすることができる。
【００５１】
（４）車載端末装置１００は、通過メッシュ算出装置１６０が算出したメッシュコストを、始点図郭ノードおよび終点図郭ノードと対応付けたメッシュコストデータ１５０をさらに有することとした。経路探索装置１７０は、メッシュコストデータ１５０に含まれるメッシュコストを参照して、複数の通過メッシュＭ０を取得する。したがって、経路探索時には予め生成されたメッシュコストデータ１５０を参照するだけで速やかに複数の通過メッシュＭ０を取得することができる。
【００５２】
―第２の実施の形態―
図１９は本発明の第２の実施の形態における経路演算システムの全体構成を示す図であって、経路演算システムは図１９（ａ）に示す車載端末装置１０００と図１９（ｂ）に示すセンタ装置５０００とを有する。車載端末装置１０００は、目的地入力装置１１０、センサ類１２０の情報から自車の位置を算出する自車位置算出装置１３０、表示装置２２０、通信装置３１０を有する。
【００５３】
センタ装置５０００は、地図データ１４０、メッシュコストデータ１５０、通過メッシュ算出装置１６０、経路探索装置１７０、経路探索結果記憶装置１８０、リアルタイム情報取得装置１９０、比較装置２００、メッシュコストデータ作成装置２１０、通信装置３２０を有する。メッシュコストデータ作成装置２１０は、図５に示す処理フローに従ってメッシュコストデータ１５０を作成する。
【００５４】
車載端末装置１０００とセンタ装置５０００とは通信装置３１０および３２０によって接続されている。通信装置３１０および３２０は、携帯電話機、無線ＬＡＮモジュール、ＰＤＡ（Personal Digital Assistance）あるいは車載端末装置１０００またはセンタ装置５０００と一体化されたモデムでも構わない。センタ装置５０００が経路探索装置１８０を実行することで、経路探索時の車載端末１０００の処理負荷を軽減できる。センタ装置５０００で算出した経路を、通信装置３２０を介して、車載端末装置１０００へ送付される。
【００５５】
車載端末装置１０００は、通信装置３１０を介して、目的地入力装置１１０からの目的地情報、経路探索タイプ情報、自車位置算出装置１３０からの自車位置情報を入力とし、センタ装置５０００へ送信する。
【００５６】
センタ装置５０００は、通信装置３２０を介して、これらの情報を受け取り、経路探索装置１７０へ入力させる。
【００５７】
センタ装置５０００の経路探索結果記憶装置１８０に格納されている経路探索結果は、通信装置３２０を介して、車載端末装置１０００へ送信される。車載端末装置１０００は、通信装置３１０を介して、経路探索結果の情報を受信する。さらに経路探索結果を示す最適経路表示画面を表示装置２２０のディスプレイ上に表示し、ユーザーに提示する。
【００５８】
以上で説明した第２の実施の形態の経路演算システムは、第１の実施の形態の車載端末装置１００が奏する作用効果に加え、車載端末装置１０００を第１の実施の形態の車載端末装置１００よりも小規模な装置として実現できるという作用効果を奏する。
【００５９】
―変形例―
（１）上述の第１及び第２の実施形態において、メッシュコストデータ１５０は、経路探索タイプ毎のメッシュ内経路探索結果として得られるメッシュコストに関するコストデータ及びメッシュ内経路を構成する全ての道路リンクＩＤを含むこととしても良い。経路探索タイプによりメッシュ内経路探索を行うため、メッシュ内経路を構成する道路リンクの構成は経路探索タイプにより異なっても構わない。メッシュコストデータ１５０の構成図を図２０（ａ）に示す。メッシュコストデータ１５０は、経路探索タイプ毎のメッシュコストに関するコストデータの他に、経路探索タイプ毎の経路探索結果として得られるメッシュ内経路を構成する道路リンク数と道路リンクＩＤとを含む。このとき道路リンクＩＤは、始点側の図郭ノードから順に格納される。メッシュコストデータ１５０には、「最短経路」および「最小時間経路」といった２種類のメッシュコストに関するコストデータが格納されているため、メッシュコスト種類数には２が設定されている。図２０（ｂ）は、経路探索タイプ「最短経路」に対応する経路と「最小時間経路」に対応する経路とを表している。最短経路を構成する道路リンク数は「３」、最短経路を構成する道路リンクＩＤは、始点側の図郭ノードから順に「１００１」、「１００２」、「１００３」となる。最小時間経路を構成する道路リンク数は「２」、最小時間経路を構成する道路リンクＩＤは、始点側の図郭ノードから順に「１００４」、「１００５」となる。このメッシュコストデータ１５０を用いた場合、経路探索装置１７０にて実行されるステップＳ４０２（図１２）においては、メッシュコストデータ１５０の経路探索タイプに応じて経路を構成する道路リンクが参照される。
【００６０】
（２）上述の実施の形態の説明において、ステップＳ５０２２おける判定処理で用いられる閾値は、リンクコストがリンク旅行時間である場合について説明した。リンクコストがリンク長、すなわち距離である場合、およびリンクコストがリンクあたりの燃料消費量である場合、これらはともに時間の関数であるため、時間に換算することにより、ステップＳ５０２２おける判定処理を実行することができる。たとえば、リンク長を、対応する道路リンクの平均移動速度で除することにより、リンク長は時間へ換算される。また、たとえば、リンクあたりの燃料消費量に、予め定められた所定の係数を乗じることによって、リンクあたりの燃料消費量は時間へ換算される。
【００６１】
（３）上述の実施の形態の説明においては、本発明を車載端末装置１００または１０００に適用した実施の形態を説明したが、車載端末装置１００または１０００は、たとえば、ＰＮＤ（Personal Navigation Device）のような着脱可能な装置であってもよい。
【符号の説明】
【００６２】
１００、１０００ 車載端末装置
１１０ 目的地入力装置
１２０ センサ類
１３０ 自車位置算出装置
１４０ 地図データ
１５０ メッシュコストデータ
１６０ 通過メッシュ算出装置
１７０ 経路探索装置
１８０ 経路探索結果記憶装置
１９０ リアルタイム情報取得装置
２００ 比較装置
２１０ メッシュコストデータ作成装置
２２０ 表示装置
３１０、３２０ 通信装置
１８１０ 最適経路
１８２０ 吹き出し
１９１０ 通過メッシュ
１９２０ 吹き出し
５０００ センタ装置
【技術分野】
【０００１】
本発明は、移動体の経路を探索する経路演算装置に関する。
【背景技術】
【０００２】
経路演算装置は、例えば車両に搭載される車載端末装置または情報配信センタに配置されるセンタ装置に含まれ、デジタル化した地図データを用いて、出発地から目的地までの経路を計算する。さらに、経路演算装置は、算出した経路をユーザーに提供する。
【０００３】
従来の経路演算装置において、出発地から目的地までの経路を計算する方法は、例えば、特許文献１に記載されている。この方法は、地図をゾーンに分割し、ゾーン内のコストを、経路探索前に計算する。このとき、コストは、ゾーンを通過する方向別に計算される。この方向とは、例えば西から東、南から北などである。経路探索時には、（１）予め計算した方向別のコストを用いて、出発地から目的地までに通過するゾーンを決定する。次に、（２）通過するゾーン毎にゾーン内の経路を探索する。最後に、（３）通過するゾーンの経路を接続し、出発地から目的地までの経路が成り立つかどうかを判定し、成り立つ場合は、その経路を出力する。成り立たない場合は、出発地から目的地までの経路が成り立つまで、（１）から（３）を繰り返す。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−５５９１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１に記載の方法によると、経路探索前のコスト計算の段階で、想定できない状況を考慮できない。例えば、自動車事故が原因で引き起こされた渋滞の情報を取得した際に、この渋滞を回避したい場合でも、既にコストが計算されていると、この渋滞の情報を加味できない。
【課題を解決するための手段】
【０００６】
（１）請求項１に記載の経路演算装置は、道路リンクと地図を区画するメッシュデータとを対応付けた地図データと、メッシュとメッシュの少なくとも１つの隣接メッシュとがメッシュ内最小コスト経路の両端ノードの各々を共有するときのメッシュ内最小コスト経路のコストを表すメッシュコストとに基づき、移動体の始点を含む始点メッシュと始点メッシュに隣接する始点隣接メッシュとの境界に位置する第１境界ノードから移動体の終点を含む終点メッシュと終点メッシュに隣接する終点隣接メッシュとの境界に位置する第２境界ノードまでの境界ノード間接続最小コスト経路に含まれる複数の中継メッシュを取得する中継メッシュ取得手段と、境界ノード間接続最小コスト経路に含まれる区間道路リンクを含むメッシュにおいて、区間道路リンクのリンクコストの更新に基づく新たなメッシュ内最小コスト経路のコストを表すようにメッシュコストを更新し、更新されたメッシュコストに基づき複数の中継メッシュを更新し、更新された複数の中継メッシュと新たなメッシュ内最小コスト経路とに基づき、始点から終点までの移動経路を探索する経路探索手段とを備えることを特徴とする。
【発明の効果】
【０００７】
本発明によると、ユーザーは、リアルタイムな情報に対応した経路探索を効率的に実行できる。
【図面の簡単な説明】
【０００８】
【図１】本発明の車載端末装置の全体構成を示す図である。
【図２】地図データの構成を示す図である。
【図３】図郭ノードの例を示す図である。
【図４】メッシュコストデータの構成を示す図である。
【図５】メッシュコストデータ作成のための処理フローを示す図である。
【図６】通過メッシュ算出装置の処理フローを示す図である。
【図７】通過メッシュの例を示す図である。
【図８】出発地側の候補図郭ノードの例を示す図である。
【図９】候補図郭ノードを決定する処理フローを示す図である。
【図１０】メッシュコストデータを用いて経路探索する例を示す図である。
【図１１】経路探索結果記憶装置に格納される通過メッシュの構成を示す図である。
【図１２】経路探索装置の処理フローを示す図である。
【図１３】経路探索処理の概念図である。
【図１４】経路探索結果記憶装置に格納される経路探索結果の構成を示す図である。
【図１５】比較装置の処理フローを示す図である。
【図１６】再探索メッシュを判定する処理フローを示す図である。
【図１７】経路探索装置における再探索の概念図である。
【図１８】表示装置において経路探索結果の表示例を示す図である。
【図１９】経路探索システムを示す図である。
【図２０】メッシュコストデータに対応する道路リンクの構成を示す図である。
【発明を実施するための形態】
【０００９】
本発明を用いた経路演算装置の実施の形態を、図面を参照して説明する。
【００１０】
―第１の実施の形態―
図１は本発明の第１の実施の形態における車載端末装置１００の全体構成を示す図である。車載端末装置１００は、目的地入力装置１１０、車載端末装置１００の搭載された車両の自車位置算出装置１３０、地図データ１４０、メッシュコストデータ１５０、通過メッシュ算出装置１６０、経路探索装置１７０、経路探索結果記憶装置１８０、リアルタイム情報取得装置１９０、比較装置２００、表示装置２２０を有する。
【００１１】
また、車載端末装置１００とセンサ類１２０とがCANなどの車載ネットワークを介して接続されている。
【００１２】
目的地入力装置１１０は、ユーザーが、車載端末装置１００の例えばリモコンのようなユーザーインターフェースを通して入力する目的地情報及び経路探索タイプ情報を受け付ける。目的地情報は、通過メッシュ算出装置１６０へ提供される。ユーザーは、目的地情報を入力する際、目的地の住所、カテゴリ、電話番号等をキーに、目的地のＰＯＩを検索し、設定する。ＰＯＩとは、Point Of Interestの略で、店舗情報などの地点に関する情報である。
【００１３】
経路探索タイプ情報は、経路探索条件の種類を表す情報である。経路探索タイプ情報の種類としては、例えば、目的地まで最小の時間での到着を目指す「最小所要時間経路」、目的地まで最小の燃料消費量での到着を目指す「最小燃料消費量経路」、目的地まで距離を最短にすることを目指す「最短経路」がある。通過メッシュ算出装置１６０、経路探索装置１７０は、目的地入力装置１１０で受付けた経路探索タイプに対応する指標を最小化するように実行される。この指標とは、すなわちコストであり、例えば、経路探索タイプ情報が「最小所要時間経路」の場合は、目的地までの旅行時間、経路探索タイプ情報が「最小燃料消費量経路」の場合は、目的地までの燃料消費量、経路探索タイプ情報が「最短経路」の場合は、目的地までの距離である。
【００１４】
センサ類１２０は、ＧＰＳ、車速パルス、角速度センサなどをいう。このセンサを用いることで、車両の位置、車速、角速度を計測することができる。これらの情報は自車位置算出装置１３０へ提供される。
【００１５】
自車位置算出装置１３０は、センサ類１２０の情報から、自車の位置を算出する。この算出には、公知の技術であるカルマンフィルタやデッドレコニングが用いられる。算出した自車位置の情報は、通過メッシュ算出装置１６０を介して経路探索装置１７０へ提供される。自車位置情報は、例えば緯度・経度で表される。
【００１６】
地図データ１４０は、ハードディスク、フラッシュメモリ等の記憶装置に格納され、道路データ、ＰＯＩの情報を含む。通過メッシュ算出装置１６０及び経路探索装置１７０の地図領域に該当する道路情報、ＰＯＩの情報を提供する。
【００１７】
地図データ１４０の構成図を図２に示す。図２（ａ）は、地図データ１４０に格納されている道路データの構成を示している。道路データはノードからノードまでのリンク単位で構成される。ノードには、道路の交差点に設けられるような通常のノードと、メッシュの境界に設けられる図郭ノードとがある。通常のノードに対して、図郭ノードは、図郭ノードフラグで区別される。例えば、ノードが図郭ノードの場合は図郭ノードフラグに「１」、通常のノードの場合は図郭ノードフラグに「０」が設定される。各道路データは、道路を特定するリンクＩＤ、その道路リンクの存在するメッシュＩＤ、道路リンクの始端のノードＩＤとその緯度・経度・高度情報、図郭ノードフラグ、道路リンクの終端のノードＩＤとその緯度・経度・高度情報、図郭ノードフラグ、道路種別、規制情報、コストデータで構成される。規制情報は、制限速度情報、一方通行情報などである。なお、ノード間のリンク上に補間点が規定される場合、ノードと補間点との間および補間点同士の間にリンクを規定してもよい。また、道路リンクの高度は、始端・終端ノードの高度情報ではなく、勾配情報で表してもよい。
【００１８】
ここで、メッシュとは、地図を緯度・経度に基づいて網の目状に区画する方法により得られる単位区画である。２次メッシュとは緯度差５分、経度差７分３０秒で区画されて得られる一辺の長さが約１０ｋｍのメッシュである。また３次メッシュは２次メッシュを緯度方向および経度方向に１０等分して得られるメッシュであり、緯度差３０秒、経度差４５秒で、一辺の長さが約１ｋｍである。メッシュＩＤにより、メッシュを特定することができる。
【００１９】
ここで、道路種別とは、道路リンクの種類を表す情報である。道路種別には、例えば、道路リンクが都市間高速道の場合は「０」、都市内高速道の場合は「１」、国道の場合は「２」、そのほかの道路の場合は「３」が設定される。
【００２０】
ここで、コストデータとは、経路探索の際に使用される道路リンクに関連した重みである。例えば、コストデータの例に、統計交通情報がある。この統計交通情報は、リアルタイム情報取得装置２００にて取得し、蓄積した道路の渋滞情報を統計処理することで作成される。この統計処理とは、平日、休日などの日種毎、及び0:00、23:00などの時間毎に作成される。図２（ｄ）に、コストデータの構成を示す。
【００２１】
ここで、図郭ノードは、通常のノード間の道路リンクがメッシュを跨ぐ場合に、地図データ１４０内での管理上、道路リンクをメッシュの境界で分割するためのノードである。一端または両端が図郭ノードで規定されることにより、道路リンクが、メッシュをまたいで存在しないこととなる。図３に図郭ノードの例を示す。通常のノード間の道路リンクがメッシュＩＤ００１および００２の隣接するメッシュに跨がる場合（図３(ａ)）、メッシュの境界線で道路リンクを分割し、分割後の道路リンクを各メッシュで管理する。このとき、分割位置を図郭ノードとして地図データ１４０内に格納する。また、メッシュ境界における同じ道路リンク上の同じ分割位置に規定される一対の図郭ノードは、隣接するメッシュ間で共通のノードＩＤ００１を持つ。そのため、車載端末装置１００は、その道路リンクによってメッシュＩＤ００１のメッシュがどのメッシュに接続しているかを、知ることができる（図３（ｂ））。
【００２２】
図２（ｂ）は、図２（ａ）に示した道路データとともに地図データ１４０に含まれるメッシュ管理テーブルを示している。このメッシュ管理テーブルには、メッシュＩＤおよびそのメッシュの左下、左上、右下、右上のそれぞれの頂点の座標（緯度・経度）が設定されている（図２（ｃ）参照）。
【００２３】
メッシュコストデータ１５０は、後述する第２の実施の形態と同様に外部のセンタ装置等で生成された後、予め車載端末装置１００のハードディスク、フラッシュメモリ等の記憶装置に格納され、メッシュ境界の図郭ノード同士を結んだ経路のコストを表す。
【００２４】
通過メッシュ算出装置１６０は、目的地入力装置１１０からの目的地情報、自車位置算出装置１３０からの自車位置情報、メッシュコストデータ１５０からメッシュ内の図郭ノード同士を結んだ経路のコストを取得し、通過メッシュを決定する。さらに、通過メッシュの地図データを地図データ１４０から取得してメモリに展開する。
【００２５】
経路探索装置１７０は、通過メッシュ算出装置１６０によりメモリに展開された地図データを取得し、通過メッシュ内部の経路を算出する。算出した通過メッシュ内部の経路を、経路探索結果記憶装置１８０へ格納する。
【００２６】
経路探索結果記憶装置１８０は、ハードディスク、フラッシュメモリ等の記憶装置であって、経路探索装置１７０で出力された経路と、通過メッシュ算出装置１６０で算出した通過メッシュの情報を記憶している。
【００２７】
リアルタイム情報取得装置１９０は、例えばVICSセンター（登録商標）のような交通情報サービスセンターから全国の主要な道路の道路リンク毎の旅行時間を受信する。情報の更新周期は、予め定められた時間間隔とする。リンク毎の旅行時間は、例えば、道路リンク毎に道路に車両検知装置を設けて、道路リンク毎の走行に要した時間を測定すること、或いはプローブカーを道路リンク毎に時間測定しながら走行させることで得られる。
【００２８】
比較装置２００は、経路探索結果記憶装置１８０に格納されている経路探索結果に含まれる道路リンクのコストと、リアルタイム情報取得装置１９０にて取得したリアルタイム情報から算出される道路リンクのコストとを比較して、再探索が必要なメッシュがあるか否かを判定する。再探索が必要な場合は、再探索の必要なメッシュの情報を経路探索装置１７０へ送信する。
【００２９】
経路探索装置１７０は、再探索が必要なメッシュの情報を比較装置２００から受け取った場合、再探索対象のメッシュの始点側の図郭ノードから終点側の図郭ノードまでの経路を、リアルタイム情報取得装置１９０で取得したリアルタイム情報を使用して、再び探索する。
【００３０】
表示装置２２０は、液晶ディスプレイ等であり、経路探索結果記憶装置１８０からの経路探索結果を表示する。
【００３１】
以下、メッシュコストデータ１５０、通過メッシュ算出装置１６０、経路探索装置１７０、経路探索結果記憶装置１８０、比較装置２００の構成及び処理フローを説明する。
【００３２】
メッシュコストデータ１５０の構成図を図４に示す。図４（ａ）は、メッシュコストデータ１５０に格納されているメッシュ毎のコストデータの構成例を示している。メッシュコストデータ１５０においては、メッシュ内の特定道路種別の図郭ノード同士を結ぶ経路の数ｎと、各経路に対応する始点の図郭ノードＩＤおよび終点の図郭ノードＩＤ、ならびにその経路のコストデータとがメッシュ単位に管理されている。各経路は、図郭ノード同士の組合せを始点・終点として地図データ１４０を用いて経路探索した結果であり、この経路のコストデータは、メッシュコストデータ１５０に格納される。このコストデータは、目的地入力装置１１０にて入力できる経路探索タイプ情報毎の経路探索結果のコストデータとコスト数とから構成される。図４（ｂ）に示すメッシュＩＤ「００１」の図郭ノードＩＤ１０１を始点、図郭ノードＩＤ１０２を終点としたときの「最短経路」の経路探索結果とそのコストが、図４（ａ）に表すコストデータとして管理されている。図４（ａ）の「最小時間経路」、「最小燃料消費量経路」も同様に、メッシュＩＤ「００１」の図郭ノードＩＤ１０１を始点、図郭ノードＩＤ１０２を終点とし、経路探索を実行して算出される。同様にして、詳細を図示することは省略しているが、同じメッシュにおける図郭ノードＩＤ１０１を始点、図郭ノードＩＤ１０３を終点としたときの「最短経路」の経路探索結果とそのコストが管理されている。このようにして、図示を省略しているが、同じメッシュにおける図郭ノードＩＤ１０１〜１０３のうちのいずれか２つを始点および終点としたときの各組み合わせ毎、すなわち６通りの経路（ｎ＝６）の各々について、「最短経路」の経路探索結果とそのコストが管理されている。後述するように、「最短経路」、「最小時間経路」および「最小燃料消費量経路」のうちから、目的地入力装置１１０にて入力された経路探索タイプ情報に対応する最小コスト経路が抽出される。その最小コスト経路のコストデータに基づき、メッシュ内の図郭ノード同士を結ぶ経路の最小コストが定まる。図４（ａ）に示すメッシュ毎のコストデータにおいては、上述したメッシュＩＤ「００１」のコストデータに続いて、詳細を図示することは省略しているが、メッシュＩＤ「００２」のコストデータが管理されている。このようにして、メッシュ毎のコストデータがメッシュコストデータ１５０に格納されている。
【００３３】
外部のセンタ装置でメッシュコストデータ１５０を作成するための処理フローを図５に従って説明する。この処理は、経路探索の前段階の処理であり、地図データを入力する。
【００３４】
はじめに、地図データの全メッシュを処理したかを判定する（ステップＳ１０１）。処理した場合（ステップＳ１０１でＹｅｓ）、処理を終了する。処理していない場合（ステップＳ１０１でＮｏ）、対象のメッシュ内の図郭ノードで、特定の道路種別のものを抽出する（ステップＳ１０２）。例えば、都市間高速、都市内高速および国道を抽出する。これは、全ての道路種別の図郭ノードを扱うと、ノード数が増えてしまうため、道路種別に基づいてノード数を絞ることとしたものである。次に、対象メッシュ内のステップＳ１０２で抽出した全ての図郭ノードを処理したかどうかを判定する（ステップＳ１０３）。処理した場合（ステップＳ１０３でＹｅｓ）、ステップＳ１０１へ進む。処理していない場合（ステップＳ１０３でＮｏ）、処理中の図郭ノードを対象図郭ノードとし、ステップＳ１０４へ進む。このとき対象図郭ノードＩＤを「Ｉ」とする。ステップＳ１０４では、対象図郭ノードＩＤ「Ｉ」以外の対象メッシュ内の図郭ノードＩＤを全て処理したかどうかを判定する（ステップＳ１０４）。処理した場合（ステップＳ１０４でＹｅｓ）、ステップＳ１０３へ進む。処理していない場合（ステップＳ１０４でＮｏ）、対象図郭ノードＩＤ「Ｉ」以外の対象メッシュ内の図郭ノードＩＤ「Ｊ」（ＩとＪとは相異なる）を抽出し、経路探索する（ステップＳ１０５）。このとき、対象図郭ノードＩＤ「Ｉ」を始点、図郭ノードＩＤ「Ｊ」を終点とした経路を算出する。経路は、公知の技術であるダイクストラ法(Dijkstra's algorithm)を用いて算出する。探索に用いるコストは、目的地入力装置１１０で設定できる経路探索タイプを用い、経路探索も経路探索タイプ毎に実行する。次に、ステップＳ１０５で用いた、始点の図郭ノードＩＤ、終点の図郭ノードＩＤ及び経路探索にて算出されたコストを、メッシュコストとしてメッシュコストデータ１５０へ格納する（ステップＳ１０６）。ただし、特定道路種別の図郭ノード同士を結ぶ道路リンクが、対象メッシュ内に存在しない場合は、コストの項目には、道路リンクが存在しないことを判定できる値、例えば「−１」が入力される。ステップＳ１０６の終了後、ステップＳ１０４へ進む。
【００３５】
図７に示すように、通過メッシュ算出装置１６０では、経路探索の際に、出発地Ｓ側の図郭ノードＯから目的地Ｇ側の図郭ノードＤまで、どのメッシュＭを通過するのかを決定する。この通過する複数のメッシュＭを通過メッシュＭ０と定義する。出発地側図郭ノードＯは、出発地Ｓを含む出発地側メッシュＭＳとそれに隣接する通過メッシュＭ０との境界に位置する。目的地側図郭ノードＤは、目的地Ｇを含む目的地側メッシュＭＧとそれに隣接する通過メッシュＭ０との境界に位置する。図７において、斜線のメッシュが、出発地Ｓ側の図郭ノードＯと目的地Ｍ側の図郭ノードＤとを結ぶ通過メッシュＭ０である。通過メッシュ算出装置１６０では、メッシュコストデータ１５０に格納されたメッシュコストを用いて、通過メッシュＭ０に含まれるメッシュＭ毎に図郭ノードＯから図郭ノードＤまで経路探索を行う。なお、図７において、各通過メッシュＭ０内の図郭ノード間を線分で結んでいるが、こうした表記は、その図郭ノード間を結ぶ経路が存在することを説明するための便宜上行ったものであり、その線分自体が上述したメッシュコストデータ１５０に含まれるものではない。図７以降の図面においても同様である。
【００３６】
通過メッシュ算出装置１６０の処理フローを図６にしたがって説明する。はじめに、出発地と目的地周辺の候補図郭ノードを抽出する（ステップＳ２０１）。候補図郭ノードとは、出発地及び目的地の周辺に存在し、出発地及び目的地からたどり着ける図郭ノードである。出発地及び目的地の周辺に存在する候補図郭ノードとは、候補図郭ノードが出発地及び目的地の属するメッシュに含まれる場合のみならず、候補図郭ノードが、出発地または目的地の属するメッシュの隣接するメッシュに含まれる場合をも意味する。図８に出発地Ｓ側の候補図郭ノードＯ１〜Ｏ４の例を示す。図郭ノードＯ１及びＯ２は、出発地Ｓのある道路リンクＬ１２が接続しているため、候補図郭ノードとなる。しかし、図郭ノードＯ３及びＯ４は、道路リンクＬ３４上に位置し、出発地Ｓとは道路リンクで接続されていないため、候補図郭ノードにならない。
【００３７】
ステップＳ２０１の詳細な処理フローを図９に従って説明する。はじめに、出発地周辺及び、目的地周辺の図郭ノードを抽出する（ステップＳ３０１）。ここでは、出発地及び目的地の属するメッシュの図郭ノードを全て抽出する。次に、すべての抽出したすべての図郭ノードを処理したか否かを判定する（ステップＳ３０２）。全てについて処理していない場合（Ｓ３０２でＮｏ）、抽出した図郭ノードまで経路探索し、その抽出した図郭ノードが候補図郭ノードかどうかを判定する（ステップＳ３０３）。図８の例で説明すると、出発地Ｓから、出発地Ｓを含む出発地側メッシュＭＳとその隣接メッシュとの境界に位置する図郭ノードＯ１，Ｏ２，Ｏ３，Ｏ４まで、地図データ１４０を用いて経路探索する。出発地Ｓから図郭ノードＯ１，Ｏ２，Ｏ３，Ｏ４まで道路のネットワークデータがある場合、候補図郭ノードと判定する（図８の例では図郭ノードＯ１，Ｏ２が該当する）。出発地から図郭ノードまで道路のネットワークデータがない場合、または経路探索の結果、コストが予め定めた値よりも大きい場合、その抽出した図郭ノードは候補図郭ノードには選ばれない（図８の例ではＯ３，Ｏ４が該当する）。目的地側の図郭ノードの場合は、目的地から図郭ノードまで経路探索する。全てについて処理した場合（Ｓ３０２でＹｅｓ）、候補図郭ノードが、目的地側と出発地側にそれぞれ１個以上存在するか否かを判定する（ステップＳ３０４）。候補図郭ノードが存在する場合（Ｓ３０４でＹｅｓ）、処理を終了する。候補図郭ノードが存在しない場合（Ｓ３０４でＮｏ）、図郭ノードを探索する範囲を広げて、ステップＳ３０２へ進む（ステップＳ３０５）。探索範囲を広げるということは、すなわち、隣接するメッシュをも探索対象とするということを意味する。広げた探索範囲の中で、出発地及び目的地の周辺のメッシュの図郭ノードを新たに抽出する。
【００３８】
図６の処理フローに戻り説明する。ステップＳ２０１で候補図郭ノードを決定した後に、出発地側及び目的地側の全ての候補図郭ノードの組合せを処理したかを判断する（ステップＳ２０２）。全ての図郭ノードの組合せを処理した場合（ステップＳ２０２でＹｅｓ）、処理を終了する。
【００３９】
全ての図郭ノードの組合せを処理していない場合（ステップＳ２０２でＮｏ）、メッシュコストデータ１５０に含まれる「最短経路」、「最小時間経路」および「最小燃料消費量経路」のうちから、目的地入力装置１１０にて入力された経路探索タイプ情報に対応する最小コスト経路のコストデータが、メッシュコストデータ１５０から最小コストとして抽出し、経路探索をする（ステップＳ２０３）。図１０にステップＳ２０３の例を示す。出発地側の候補図郭ノードＯ１、Ｏ２と目的地側の候補図郭ノードＤ１、Ｄ２との組合せは、Ｏ１からＤ１，Ｏ１からＤ２，Ｏ２からＤ１、Ｏ２からＤ２の4つである。ここでは、メッシュコストデータ１５０に格納されたメッシュコストを用いて、候補図郭ノードＯ１またはＯ２を出発地とし、候補図郭ノードＤ１またはＤ２を目的地として経路探索する。図１０は、候補図郭ノードＯ１及びＤ２の組合せを出発地及び目的地の組合せとする例と、候補図郭ノードＯ２及びＤ１の組合せを出発地及び目的地の組合せとする例とを示している。候補図郭ノードＯ１を出発地、候補図郭ノードＤ２を目的地としたときの他経路探索が成り立つ。一方、候補図郭ノードＯ２を出発地、候補図郭ノードＤ１を目的地としたときの経路探索は、途中のメッシュ内の図郭ノードＮ１から図郭ノードＮ２までを接続する経路がメッシュ内に無いため、成立しない。したがって、この例では、候補図郭ノードＯ１からＤ２までの間の図郭ノードを結んだ経路が含まれる複数のメッシュが通過メッシュとなる。
【００４０】
通過メッシュを決定したとき、出発地点側の図郭ノード、および目的地側の図郭ノードの情報を含む通過メッシュの情報を経路探索結果記憶装置１８０に記憶する（ステップＳ２０４）。図１１（ａ）に、ステップＳ２０４で経路探索結果記憶装置１８０に格納される通過メッシュの情報の構成図を示す。複数組の通過メッシュがある場合、経路探索結果記憶装置１８０はそれら複数組の通過メッシュの情報を記憶する。通過メッシュの情報は、出発地側の図郭ノードＩＤ，目的地側の図郭ノードＩＤ、通過メッシュ数、ステップＳ２０３の経路探索で算出したメッシュコストの総和と、詳細な通過メッシュ情報ＤＭＭを含む。詳細な通過メッシュＤＭＭに含まれる情報を、図１１（ｂ）の例を用いて説明する。詳細な通過メッシュ情報ＤＭＭは、通過メッシュ数分記憶され、通過メッシュのＩＤ(001)、始点図郭ノードＩＤ(101)，終点図郭ノードＩＤ(102)、およびコストデータ１５０に格納されているコストデータであって、始点図郭ノードＩＤ(101)と終点図郭ノードＩＤ(102)との間のメッシュコスト(200m)を含む。通過メッシュには、図郭ノードは２つ存在する。これらの図郭ノードはステップＳ２０３にて求めた経路の両端に位置しており、出発地に最も近い始点図郭ノード(101)を出発地側図郭ノード、目的地に最も近い終点図郭ノード(102)を目的地側図郭ノードと定義する。図１１（ａ）における詳細な通過メッシュＤＭＭには、通過メッシュＩＤ002についてのデータも含まれている。しかし、図１１（ｂ）の例においては通過メッシュが１つだけのため、これに対応して図１１（ａ）における詳細な通過メッシュＤＭＭには、通過メッシュのＩＤ001のデータのみが格納されることとなる。
【００４１】
次に、経路探索装置１７０を図１２の処理フローに従い説明する。図１３に図１２の処理フローに従って実行される経路探索処理の概念図の一例を示す。はじめに最小コストの通過メッシュ情報を取得する（ステップＳ４０１）。この処理では、通過メッシュ算出装置１６０の処理によって経路探索結果記憶装置１８０に格納された通過メッシュ情報の中で、コスト総和の最小のものを取得する。このとき図１３（ａ）のように、出発地から目的地までの間の図郭ノードＮが含まれる通過メッシュが選ばれる。次に、取得した通過メッシュに含まれるメッシュ毎に、出発地側図郭ノードＯを出発地、目的地側図郭ノードＤを目的地として経路探索を実施する（ステップＳ４０２）。この経路探索処理は、地図データ１４０に格納されている道路ネットワークデータのうち、処理対象のメッシュのデータをメモリ上に展開し、道路リンク毎のコストデータを使って経路探索することによって行われる。経路探索した結果は、例えば図１３（ｂ）のように表される。全てのメッシュに対して経路探索が終了した後、経路探索結果を経路データとして経路探索結果記憶装置１８０に格納する（ステップＳ４０３）。図１４は、経路探索結果記憶装置１８０に格納される経路データの構成の一例を表している。図１４（ｂ）の例を用いて、図１４（ａ）に示す経路データ構成を説明する。経路データは、通過メッシュ毎に、始点図郭ノードＩＤ（１０１）、終点図郭ノードＩＤ（１０２）、経路を構成する道路リンク数（３）、経路を構成する道路リンクＩＤ（１００１，１００２，１００３）およびそのコスト（３０ｍ、５０ｍ、２０ｍ）を含む。
【００４２】
次に、比較装置２００の処理フローについて、図１５を用いて説明する。この比較装置２００の処理フローは、リアルタイム情報を取得したタイミング、または予め定められた時間間隔で実行される。はじめに、経路探索結果記憶装置１８０から経路探索結果を取得する（ステップＳ５０１）。次に、リアルタイム情報取得装置１９０で取得した情報と、経路探索結果とを比較して、再探索が必要か否かを判定する（ステップＳ５０２）。経路探索装置１８０でメッシュコストデータの最小時間を用いて、経路探索をしたとき、コストは道路リンクを通過する旅行時間となる。メッシュコストデータ作成時に考慮される旅行時間は、過去の旅行時間を統計処理したものである。しかし、過去の交通情報でカバーできない状況が起きたとき、再探索が必要になる。例えば、経路上に、交通事故が発生し、渋滞が引き起こされたという情報を、リアルタイム情報取得装置１９０にて取得した場合、再度この渋滞を避けるように再探索をする必要がある。この再探索するか否かの判定をステップＳ５０２で行う。ステップＳ５０２においては、例えば、取得したリアルタイム交通情報の旅行時間と、過去の交通情報を統計処理した統計交通情報の旅行時間との差分が閾値以上であることが検出された場合、または事故発生情報を取得した場合に肯定判定される。再探索すると判定した場合（ステップＳ５０２でＹｅｓ）、経路探索装置１７０へ再探索を要求し、処理を終了する（ステップＳ５０３）。再探索を要求する際には、再探索が必要な通過メッシュのＩＤを経路探索装置１７０へ送信する。経路探索装置１７０では、後述するように、この再探索が必要な通過メッシュについて再探索を実行する。一方、再探索するか否かの判定において、再探索する必要がないと判定した場合（ステップＳ５０２でＮｏ）、処理を終了する。
【００４３】
図１６は、ステップＳ５０２の処理の詳細を、ステップＳ５０２１〜Ｓ５０２４として示した図である。以下、図１６の処理フローについて説明する。ただし、ステップＳ５０１およびＳ５０３については、図１５と同様であるため、説明を省略する。ステップＳ５０１における経路探索結果取得の後、ステップＳ５０２１において、後述するステップＳ５０２２およびＳ５０２３の処理を、ステップＳ５０１にて取得した経路が含まれる全てのメッシュについて行ったか否か、判定する。肯定判定の場合は処理をステップＳ５０２４へ進める。否定判定の場合は、ステップＳ５０２２において、リアルタイム情報取得装置１９０にて取得したリアルタイム情報のコストと、経路探索結果記憶装置１８０に格納されている経路探索結果の道路リンクのコストとの差が、閾値以上かを判定する。ステップＳ５０２２では、処理対象メッシュにおいて、経路探索結果記憶装置１８０に格納されているリンクＩＤに該当するリンクのリアルタイム情報のコスト（ＣＲ）を取得する。さらに経路探索結果記憶装置１８０に格納されているリンクＩＤのリンクのコスト（ＣＭ）を取得する。全ての経路上の道路リンクを処理し、リアルタイム情報のコストと経路探索結果のコストとの差が閾値以上の場合（ステップＳ５０２２でＹｅｓ）、その道路リンクの存在するメッシュを再探索要求対象とする（ステップＳ５０２３）。処理をステップＳ５０２１へ戻す。
【００４４】
処理対象メッシュにおいて、リアルタイム情報と経路探索結果とのコスト差が閾値以上に該当する道路リンクが存在しない場合（ステップＳ５０２２でＮｏ）、処理をステップＳ５０２１へ戻す。ステップＳ５０２１における判定が肯定判定の場合、ステップＳ５０２３において再探索要求対象とされたメッシュがあるか否かを判定する（ステップＳ５０２４）。肯定判定の場合、処理を上述したステップＳ５０３を経て終了し、否定判定の場合は直ちに処理を終了する。例えば、コストＣＲは、リアルタイム交通情報に基づいて車両が道路リンクを走行する際のリンク旅行時間、コストＣＭは、統計交通情報または規制速度に基づいて車両がその道路リンクを走行する際のリンク旅行時間となる。このとき、コストＣＲと、コストＣＭから算出する閾値とを比較する。予め定められる閾値は、コストＣＭを係数（ｋ）倍したコストｋ＊ＣＭとする。例えば、コストをリンク旅行時間としたときＣＭが６０秒で係数ｋを３としたとき、閾値は１８０秒となる。リアルタイム交通情報によるコストＣＲが２００秒の場合、閾値１８０秒と比較して大きいため、この道路リンクに存在しているメッシュは再探索対象と判定する。この閾値は、車両が出発地Ｓを出発してからその道路リンクを走行するまでの予測経過時間に応じた関数でもよい。
【００４５】
次に、経路探索装置１７０の再探索処理を説明する。再探索処理の概念図を図１７に示す。図１７に示すように、経路探索処理１７０による再探索が実行される際、出発地Ｓに最も近い候補図郭ノードＯ１から目的地Ｇに最も近い候補図郭ノードＤ２までの、図郭ノードＮを経由する通過メッシュＭＯが既に決定されている。経路探索装置１７０では、通過メッシュＭＯのうち、再探索対象メッシュＭＲ内の最小コスト経路を探索する。この探索は、再探索対象メッシュＭＲの出発地側図郭ノードＯＲから再探索対象メッシュＭＲの目的地側図郭ノードＤＲまでの経路探索を、リアルタイム情報取得装置１９０から入力されるリアルタイム情報を用いて実行する。探索に用いるコストは、目的地入力装置１１０で設定できる経路探索タイプを用いる。このとき地図データ１４０を使用する。こうして、経路探索結果記憶装置１８０に格納されている通過メッシュＭＯ中で、比較装置２００で判定した再探索対象メッシュＭＲの最小コスト経路を更新する。この経路探索結果として得られる再探索された経路ＲＲは、はじめにメッシュコストデータ１５０を計算したときに算出した経路と異なっても構わない。さらに、再探索対象のメッシュＭＲのＯＲからＤＲまでのメッシュコストデータを、最小コスト経路のコストデータで更新する。更新した後、通過メッシュＭＯのメッシュコスト総和も更新する。全ての再探索対象のメッシュＭＲ内の通過メッシュの通過する図郭ノード間の最小コスト経路のコストデータを、その図郭ノード間のメッシュコストデータとして更新した後、経路探索装置１７０においてステップＳ４０１の処理が実行される。このとき、更新したメッシュコストを用いて経路探索をする。
【００４６】
表示装置２２０では、経路探索結果記憶装置１８０の経路探索結果を示す最適経路表示画面を、ディスプレイ上に表示し、ユーザーに提示する。表示例を図１８に示す。図１８（ａ）は、出発地Ｓから目的地Ｇまで経路探索したときに、地図上に経路探索結果記憶装置１８０の経路探索結果を最適経路１８１０として重畳表示し、さらに、吹き出し１８２０を用いて目的地までのコスト「所要時間２０分」を提示している。
【００４７】
また、他の表示の例を図１８（ｂ）に示す。この例は、通過メッシュ算出装置１６０から通過メッシュを算出し、経路探索装置１７０の処理中に、通過メッシュ１９１０の情報をディスプレイ上に表示し（図１８（ｂ））、ユーザーに提示している。さらに、吹き出し１９２０を用いて「通過メッシュ」を提示している。経路探索装置１７０から経路探索結果が出力された際に、表示していた通過メッシュの情報を経路探索結果の情報に置き換えて、ディスプレイ上に表示し（図１８（ａ））、ユーザーに提示している。図１８（ｂ）において、通過メッシュ１９１０の情報はハッチングによって表されている。実際のディスプレイ上では、例えば、地図にメッシュの境界線を表示し、図１８（ｂ）ではハッチングによって表されている通過するメッシュに色を塗って強調して表示させる。
【００４８】
以上で説明した第１の実施の形態の車載端末装置１００は、以下のような作用効果を奏する。
（１）車載端末装置１００は、道路リンクの始端のノードＩＤおよびその緯度・経度・高度情報、図郭ノードフラグ、ならびに道路リンクの終端のノードＩＤおよびその緯度・経度・高度情報、図郭ノードフラグとコストデータとを含む道路データと、メッシュ管理テーブル上で規定されるメッシュＩＤとを対応付けた地図データ１４０を有する。また、リアルタイム情報を取得するリアルタイム情報取得装置１９０を有する。車載端末装置１００は通過メッシュ算出装置１６０を有し、通過メッシュ算出装置１６０は、図６のステップＳ２０１〜Ｓ２０３において、地図データ１４０に基づき、車載端末装置１００の搭載された車両の出発地Ｓを含む出発地側メッシュＭＳと出発地側メッシュＭＳに隣接する通過メッシュＭ０との境界に位置する出発地側図郭ノードＯから、車両の目的地Ｇを含む目的地側メッシュＭＧと目的地側メッシュＭＧに隣接する通過メッシュＭ０との境界に位置する目的地側図郭ノードＤまでの最小コスト経路が含まれる複数の通過メッシュＭ０を取得する。複数の通過メッシュＭ０のうちの各通過メッシュＭ０において、各通過メッシュＭ０と各通過メッシュＭ０の少なくとも１つの隣接する通過メッシュＭ０とが各通過メッシュＭ０内の最小コスト経路の両端の始点図郭ノードおよび終点図郭ノードを共有するときの最小コスト経路のコストを表すメッシュコストは予め記憶装置に格納されている。車載端末装置１００は比較装置２００を有し、比較装置２００は、図１６の処理ステップＳ５０２２において、出発地側図郭ノードＯから目的地側図郭ノードＤまでの最小コスト経路に含まれる道路リンクのコストと、その道路リンクに関するリアルタイム情報とに基づき、その道路リンクを含む通過メッシュＭ０の図郭ノード間のメッシュコストの更新を行うか否かを判定する。更新を行うことが肯定判定されたとき、経路探索装置１７０は、再探索対象メッシュＭＲの図郭ノード間のメッシュコストを更新するとともに、更新されたメッシュコストに対応する再探索対象メッシュＭＲ内の最小コスト経路を求める。経路探索装置１７０は、更新された通過メッシュの図郭ノード間のメッシュコストに基づき複数の通過メッシュＭ０を更新し、更新された複数の通過メッシュＭ０と再探索対象メッシュＭＲ内の最小コスト経路とに基づき、出発地Ｓから目的地Ｇまでの経路を探索する。すなわち、予め計算したメッシュコストを用いる車載端末装置１００では、リアルタイム交通情報から、通過メッシュのメッシュコストを更新するかどうかを判定し、肯定判定されたときこのメッシュコストを更新することで、経路探索前のコスト計算の段階で想定できない状況を考慮することができる。したがって、ユーザーは、リアルタイムな情報に対応した経路探索を効率的に実行できる。
【００４９】
（２）車載端末装置１００において、比較装置２００は、統計交通情報または規制速度に基づく道路リンクのコストＣＭと、リアルタイム情報に基づく道路リンクのコストＣＲとの差分が所定の閾値１８０秒以上のとき、通過メッシュのメッシュコストの更新を行うことを肯定判定することとした。したがって、統計交通情報または規制速度に基づく道路リンクのコストＣＭと、リアルタイム情報に基づく道路リンクのコストＣＲとが略等しい場合、ユーザーは、経路探索装置１７０による再探索対象メッシュＭＲの通過メッシュのメッシュコストの更新を行うこと無く、経路探索装置１７０によって探索された出発地Ｓから目的地Ｇまでの経路を得ることができる。
【００５０】
（３）出発地Ｓから離れた道路リンクほど、その道路リンクに関して出発時に取得したリアルタイム情報は、車両がその道路リンクを走行する時点で有効性が低下している可能性が考えられる。車載端末装置１００において、所定の閾値は、車両が出発地Ｓを出発してからその道路リンクを走行するまでの予測経過時間に応じた関数としてもよいこととした。したがって、出発地Ｓから離れた道路リンクほど所定の閾値を大きくすることにより、リアルタイム情報に基づく通過メッシュのメッシュコストの更新が行われにくくなるようにすることができる。
【００５１】
（４）車載端末装置１００は、通過メッシュ算出装置１６０が算出したメッシュコストを、始点図郭ノードおよび終点図郭ノードと対応付けたメッシュコストデータ１５０をさらに有することとした。経路探索装置１７０は、メッシュコストデータ１５０に含まれるメッシュコストを参照して、複数の通過メッシュＭ０を取得する。したがって、経路探索時には予め生成されたメッシュコストデータ１５０を参照するだけで速やかに複数の通過メッシュＭ０を取得することができる。
【００５２】
―第２の実施の形態―
図１９は本発明の第２の実施の形態における経路演算システムの全体構成を示す図であって、経路演算システムは図１９（ａ）に示す車載端末装置１０００と図１９（ｂ）に示すセンタ装置５０００とを有する。車載端末装置１０００は、目的地入力装置１１０、センサ類１２０の情報から自車の位置を算出する自車位置算出装置１３０、表示装置２２０、通信装置３１０を有する。
【００５３】
センタ装置５０００は、地図データ１４０、メッシュコストデータ１５０、通過メッシュ算出装置１６０、経路探索装置１７０、経路探索結果記憶装置１８０、リアルタイム情報取得装置１９０、比較装置２００、メッシュコストデータ作成装置２１０、通信装置３２０を有する。メッシュコストデータ作成装置２１０は、図５に示す処理フローに従ってメッシュコストデータ１５０を作成する。
【００５４】
車載端末装置１０００とセンタ装置５０００とは通信装置３１０および３２０によって接続されている。通信装置３１０および３２０は、携帯電話機、無線ＬＡＮモジュール、ＰＤＡ（Personal Digital Assistance）あるいは車載端末装置１０００またはセンタ装置５０００と一体化されたモデムでも構わない。センタ装置５０００が経路探索装置１８０を実行することで、経路探索時の車載端末１０００の処理負荷を軽減できる。センタ装置５０００で算出した経路を、通信装置３２０を介して、車載端末装置１０００へ送付される。
【００５５】
車載端末装置１０００は、通信装置３１０を介して、目的地入力装置１１０からの目的地情報、経路探索タイプ情報、自車位置算出装置１３０からの自車位置情報を入力とし、センタ装置５０００へ送信する。
【００５６】
センタ装置５０００は、通信装置３２０を介して、これらの情報を受け取り、経路探索装置１７０へ入力させる。
【００５７】
センタ装置５０００の経路探索結果記憶装置１８０に格納されている経路探索結果は、通信装置３２０を介して、車載端末装置１０００へ送信される。車載端末装置１０００は、通信装置３１０を介して、経路探索結果の情報を受信する。さらに経路探索結果を示す最適経路表示画面を表示装置２２０のディスプレイ上に表示し、ユーザーに提示する。
【００５８】
以上で説明した第２の実施の形態の経路演算システムは、第１の実施の形態の車載端末装置１００が奏する作用効果に加え、車載端末装置１０００を第１の実施の形態の車載端末装置１００よりも小規模な装置として実現できるという作用効果を奏する。
【００５９】
―変形例―
（１）上述の第１及び第２の実施形態において、メッシュコストデータ１５０は、経路探索タイプ毎のメッシュ内経路探索結果として得られるメッシュコストに関するコストデータ及びメッシュ内経路を構成する全ての道路リンクＩＤを含むこととしても良い。経路探索タイプによりメッシュ内経路探索を行うため、メッシュ内経路を構成する道路リンクの構成は経路探索タイプにより異なっても構わない。メッシュコストデータ１５０の構成図を図２０（ａ）に示す。メッシュコストデータ１５０は、経路探索タイプ毎のメッシュコストに関するコストデータの他に、経路探索タイプ毎の経路探索結果として得られるメッシュ内経路を構成する道路リンク数と道路リンクＩＤとを含む。このとき道路リンクＩＤは、始点側の図郭ノードから順に格納される。メッシュコストデータ１５０には、「最短経路」および「最小時間経路」といった２種類のメッシュコストに関するコストデータが格納されているため、メッシュコスト種類数には２が設定されている。図２０（ｂ）は、経路探索タイプ「最短経路」に対応する経路と「最小時間経路」に対応する経路とを表している。最短経路を構成する道路リンク数は「３」、最短経路を構成する道路リンクＩＤは、始点側の図郭ノードから順に「１００１」、「１００２」、「１００３」となる。最小時間経路を構成する道路リンク数は「２」、最小時間経路を構成する道路リンクＩＤは、始点側の図郭ノードから順に「１００４」、「１００５」となる。このメッシュコストデータ１５０を用いた場合、経路探索装置１７０にて実行されるステップＳ４０２（図１２）においては、メッシュコストデータ１５０の経路探索タイプに応じて経路を構成する道路リンクが参照される。
【００６０】
（２）上述の実施の形態の説明において、ステップＳ５０２２おける判定処理で用いられる閾値は、リンクコストがリンク旅行時間である場合について説明した。リンクコストがリンク長、すなわち距離である場合、およびリンクコストがリンクあたりの燃料消費量である場合、これらはともに時間の関数であるため、時間に換算することにより、ステップＳ５０２２おける判定処理を実行することができる。たとえば、リンク長を、対応する道路リンクの平均移動速度で除することにより、リンク長は時間へ換算される。また、たとえば、リンクあたりの燃料消費量に、予め定められた所定の係数を乗じることによって、リンクあたりの燃料消費量は時間へ換算される。
【００６１】
（３）上述の実施の形態の説明においては、本発明を車載端末装置１００または１０００に適用した実施の形態を説明したが、車載端末装置１００または１０００は、たとえば、ＰＮＤ（Personal Navigation Device）のような着脱可能な装置であってもよい。
【符号の説明】
【００６２】
１００、１０００ 車載端末装置
１１０ 目的地入力装置
１２０ センサ類
１３０ 自車位置算出装置
１４０ 地図データ
１５０ メッシュコストデータ
１６０ 通過メッシュ算出装置
１７０ 経路探索装置
１８０ 経路探索結果記憶装置
１９０ リアルタイム情報取得装置
２００ 比較装置
２１０ メッシュコストデータ作成装置
２２０ 表示装置
３１０、３２０ 通信装置
１８１０ 最適経路
１８２０ 吹き出し
１９１０ 通過メッシュ
１９２０ 吹き出し
５０００ センタ装置
【特許請求の範囲】
【請求項１】
道路リンクと地図を区画するメッシュとを対応付けた地図データと、前記メッシュと前記メッシュの少なくとも１つの隣接メッシュとがメッシュ内最小コスト経路の両端ノードの各々を共有するときの前記メッシュ内最小コスト経路のコストを表すメッシュコストとに基づき、移動体の始点を含む始点メッシュと前記始点メッシュに隣接する始点隣接メッシュとの境界に位置する第１境界ノードから前記移動体の終点を含む終点メッシュと前記終点メッシュに隣接する終点隣接メッシュとの境界に位置する第２境界ノードまでの境界ノード間接続最小コスト経路に含まれる複数の中継メッシュを取得する中継メッシュ取得手段と、
前記境界ノード間接続最小コスト経路に含まれる区間道路リンクを含むメッシュにおいて、前記区間道路リンクのリンクコストの更新に基づく新たなメッシュ内最小コスト経路のコストを表すように前記メッシュコストを更新し、更新された前記メッシュコストに基づき前記複数の中継メッシュを更新し、更新された前記複数の中継メッシュと前記新たなメッシュ内最小コスト経路とに基づき、前記始点から前記終点までの移動経路を探索する経路探索手段とを備えることを特徴とする経路演算装置。
【請求項２】
請求項１に記載の経路演算装置において、
現況交通情報を取得する取得手段をさらに備え、
前記経路探索手段は、前記リンクコストと、前記現況交通情報に基づく前記区間道路リンクの現況コストとの差分が所定の閾値以上のとき、前記リンクコストの更新に基づき前記メッシュコストの更新を行うことを特徴とする経路演算装置。
【請求項３】
請求項２に記載の経路演算装置において、
前記所定の閾値は、前記移動体が前記始点を出発してから前記区間道路リンクを移動するまでの予測経過時間に応じた関数であることを特徴とする経路演算装置。
【請求項４】
請求項１に記載の経路演算装置において、
前記中継メッシュ取得手段によって算出された前記メッシュコストを、前記両端ノードに対応付けたメッシュコストデータをさらに備え、
前記第１の経路探索手段は、前記メッシュコストデータに含まれる前記メッシュコストを参照して、前記複数の中継メッシュを取得することを特徴とする経路演算装置。
【請求項５】
請求項１に記載の経路演算装置において、
前記中継メッシュ取得手段によって算出された前記メッシュコストを、前記両端ノードに対応付けたメッシュコストデータをさらに備え、
前記メッシュコストデータは、前記メッシュ内最小コスト経路を構成する前記道路リンクに関するデータを含むことを特徴とする経路演算装置。
【請求項６】
請求項４または５に記載の経路演算装置において、
前記メッシュコストデータは、複数種類の経路探索条件に応じた複数種類のコストに関するデータを含むことを特徴とする経路演算装置。
【請求項１】
道路リンクと地図を区画するメッシュとを対応付けた地図データと、前記メッシュと前記メッシュの少なくとも１つの隣接メッシュとがメッシュ内最小コスト経路の両端ノードの各々を共有するときの前記メッシュ内最小コスト経路のコストを表すメッシュコストとに基づき、移動体の始点を含む始点メッシュと前記始点メッシュに隣接する始点隣接メッシュとの境界に位置する第１境界ノードから前記移動体の終点を含む終点メッシュと前記終点メッシュに隣接する終点隣接メッシュとの境界に位置する第２境界ノードまでの境界ノード間接続最小コスト経路に含まれる複数の中継メッシュを取得する中継メッシュ取得手段と、
前記境界ノード間接続最小コスト経路に含まれる区間道路リンクを含むメッシュにおいて、前記区間道路リンクのリンクコストの更新に基づく新たなメッシュ内最小コスト経路のコストを表すように前記メッシュコストを更新し、更新された前記メッシュコストに基づき前記複数の中継メッシュを更新し、更新された前記複数の中継メッシュと前記新たなメッシュ内最小コスト経路とに基づき、前記始点から前記終点までの移動経路を探索する経路探索手段とを備えることを特徴とする経路演算装置。
【請求項２】
請求項１に記載の経路演算装置において、
現況交通情報を取得する取得手段をさらに備え、
前記経路探索手段は、前記リンクコストと、前記現況交通情報に基づく前記区間道路リンクの現況コストとの差分が所定の閾値以上のとき、前記リンクコストの更新に基づき前記メッシュコストの更新を行うことを特徴とする経路演算装置。
【請求項３】
請求項２に記載の経路演算装置において、
前記所定の閾値は、前記移動体が前記始点を出発してから前記区間道路リンクを移動するまでの予測経過時間に応じた関数であることを特徴とする経路演算装置。
【請求項４】
請求項１に記載の経路演算装置において、
前記中継メッシュ取得手段によって算出された前記メッシュコストを、前記両端ノードに対応付けたメッシュコストデータをさらに備え、
前記第１の経路探索手段は、前記メッシュコストデータに含まれる前記メッシュコストを参照して、前記複数の中継メッシュを取得することを特徴とする経路演算装置。
【請求項５】
請求項１に記載の経路演算装置において、
前記中継メッシュ取得手段によって算出された前記メッシュコストを、前記両端ノードに対応付けたメッシュコストデータをさらに備え、
前記メッシュコストデータは、前記メッシュ内最小コスト経路を構成する前記道路リンクに関するデータを含むことを特徴とする経路演算装置。
【請求項６】
請求項４または５に記載の経路演算装置において、
前記メッシュコストデータは、複数種類の経路探索条件に応じた複数種類のコストに関するデータを含むことを特徴とする経路演算装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２０１２−１５９４３３（Ｐ２０１２−１５９４３３Ａ）
【公開日】平成２４年８月２３日（２０１２．８．２３）
【国際特許分類】
【出願番号】特願２０１１−２００６８（Ｐ２０１１−２００６８）
【出願日】平成２３年２月１日（２０１１．２．１）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
【公開日】平成２４年８月２３日（２０１２．８．２３）
【国際特許分類】
【出願日】平成２３年２月１日（２０１１．２．１）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
[ Back to top ]