推定関数を使用する最適ルート決定
【課題】道路網の出発点から目的地までのルートを決定する方法において、部分的な地図アップデートが容易に実行されることを可能にすること。
【解決手段】道路網の出発点から目的地までのルートを決定する方法およびシステムが提供され、道路網の頂点のための推定関数が使用され、タイリングが道路網の少なくとも一部分が含まれる地域をカバーするように定義され、タイリングの各タイルの抵抗値が提供され、道路網の頂点のための推定関数の値がタイリングのタイルの抵抗値に応じて決定される。好ましい実施形態において、所定のタイル（Ｔ０）の抵抗値は、一対の頂点のエアライン距離（１２、１４）によって分割される所定のタイルの境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を接続する最適ルート（１１、１３）に関連するコストの下限または最小値である。
【解決手段】道路網の出発点から目的地までのルートを決定する方法およびシステムが提供され、道路網の頂点のための推定関数が使用され、タイリングが道路網の少なくとも一部分が含まれる地域をカバーするように定義され、タイリングの各タイルの抵抗値が提供され、道路網の頂点のための推定関数の値がタイリングのタイルの抵抗値に応じて決定される。好ましい実施形態において、所定のタイル（Ｔ０）の抵抗値は、一対の頂点のエアライン距離（１２、１４）によって分割される所定のタイルの境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を接続する最適ルート（１１、１３）に関連するコストの下限または最小値である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適ルート決定に関し、特に、推定関数に基づいて道路網における最適ルートを決定する方法およびシステムに関する。本発明の方法およびシステムは、たとえば自動車に搭載されたナビゲーションシステムにおいて、任意の最適ルート検索のため、特に道路網における最適ルートを検索するために有利に使用され得る。
【背景技術】
【０００２】
所定の出発点から所定の目的地までの最適ルートを見出すことは、最適ルート情報を提供する自動車ナビゲーションシステムまたは他のシステムの主要な特徴の一つである。
【０００３】
最適ルートを見出すいくつかの標準的なアルゴリズムが当該技術分野において公知であり、なかでも最も有名なものは、ダイクストラのアルゴリズム（Ｄｉｊｋｓｔｒａ‘ｓ ａｌｇｏｒｉｔｈｍ）およびＡ＊−アルゴリズムである。本明細書の全体にわたって、「最適ルート」という用語は、最小コストのルートについて使用され、ルートのコストは、該ルートを移動するときに横断される道路セグメントのコストの合計と、交差点または道路セグメント頂点に関連するコストの合計とによって決定される。ナビゲーションシステムにおいて、いくつかの異なるコストモデルがしばしば使用され、たとえば、道路セグメントのコストが道路セグメントの長さによって与えられる最短ルートモデル、または道路セグメントのコストが、道路セグメントにおける特徴的な移動速度によって分割される道路セグメントの長さによって与えられる、最速ルートモデルである。さらに、コストモデルは、幹線道路を回避すること、トンネルを回避すること、またはフェリー接続を回避することなどのユーザプリファランスをしばしば考慮に入れる。
【０００４】
ダイクストラのアルゴリズムにおいては、道路網、すなわちより一般的にグラフは、エッジ緩和（ｅｄｇｅ ｒｅｌａｘａｔｉｏｎ）によってルートの出発点から出発して探索され、道路網の異なる頂点は、頂点と出発点とを接続するルートに関連する最小コストの順に訪問される。目的地が伸ばされるときに、出発点から目的地までの最適ルートが見出され、ダイクストラのアルゴリズムは終了する。
【０００５】
Ａ＊−アルゴリズムは、ダイクストラのアルゴリズムの修正であり、道路網のすべての頂点のための推定関数を使用する。所定の頂点のための推定関数は、所定の頂点と目的地とを接続する最適ルートに関連するコストに対して推定を提供する。ルート検索において、異なる経路が優先度に応じて分類され、該優先度は、出発点から頂点までにそれまで発生したコストの合計と、頂点の推定関数とによって与えられる。推定関数が、頂点と目的地とを接続する最適ルートのコストを決して過大評価しないようになっている場合には、Ａ＊−アルゴリズムは、最適ルート問題に対する正しい解決策を見出すことが知られている。
【０００６】
道路網における最適ルート検索については、発見的推定がしばしば使用され、該発見的推定は、最短ルート検索における頂点と目的地とのエアライン距離と、最速検索における特徴的な移動速度によって分割されるエアライン距離とに基づいて決定される。一般的に、推定関数が優れているほど、最適ルートの決定のために訪問されなければならない道路セグメント頂点の数は小さくなり、アルゴリズム実行時間が短くなる。
【０００７】
しかし、エアライン距離に基づく推定関数は、しばしば不正確である。さらに、車両に搭載されたナビゲーションシステムにおいては、メモリと実行時間との制約が対処される必要がある。後者の制約のために、ダイクストラのアルゴリズムおよびＡ＊−アルゴリズムを、ヨーロッパの田舎またはアメリカ合衆国の道路網などの道路網に直接的に適用することは、これらの道路網における道路セグメントおよび道路セグメント頂点が多数であるために、しばしば実行可能ではない。これらの理由のために、ダイクストラのアルゴリズムまたはＡ＊−アルゴリズムは、たとえば、異なる道路セグメントの異なるレイヤへの分類を提供することによって、または道路網幾何学を特徴づける追加情報を提供することによって、ナビゲーションシステムにおける使用のためにしばしば変更され、これはオフラインで決定され、ナビゲーションシステムにおける最適ルート検索を容易にする。
【０００８】
このような文脈において、特許文献１は、最小コストのルート指定（ｒｏｕｔｉｎｇ）システムを開示しており、そこでは長距離移動のための道路セグメントの関連性を定量化するリーチメトリック（ｒｅａｃｈ ｍｅｔｒｉｃ）が提供される。このリーチメトリックは、地図の幾何学のみに基づくという利点を有する。しかし、リーチメトリックは、所定の道路セグメントの範囲が、遠くの異なる道路セグメントに関連するコストに強く依存し得るという意味で非常に非局所的であるという不都合がある。たとえば、道路セグメントのコスト要因の増加は、たとえ異なる道路セグメントが遠くても、異なる道路セグメントの範囲の増加または減少を引き起こし得る。したがって、特許文献１に開示される方法およびシステムは、部分的な地図アップデートおよび動的なルート決定にうまく適合しない。
【０００９】
したがって、当該技術分野において、最適ルートを決定する改善された方法およびシステムに対するニーズが存在する。より具体的には、最適ルートを決定するシステムおよび方法であって、部分的な地図アップデートが容易に実行されることを可能にする、動的なルート決定に適した、最適ルートが確実に決定されることを可能にする方法およびシステムのニーズが、当該技術分野において存在する。
【特許文献１】国際公開第０３／０７９１５５号パンフレット
【発明の開示】
【課題を解決するための手段】
【００１０】
本発明によれば、このニーズは、請求項１に係る、道路網のルートを決定する方法と、請求項２４に係る、道路網データを前処理する方法と、請求項２７に係る、ルートを決定するシステムとによって、対処される。従属請求項は、本発明の好ましいまたは有利な実施形態を定義する。
【００１１】
本発明の局面によれば、道路網の出発点から目的地までのルートを決定する方法が提供され、該方法は複数の頂点のための推定関数を使用し、該推定関数は道路網の頂点と目的地とを接続する任意のルートに関連するコストの下限を提供する。該方法は、道路網の少なくとも一部分が含まれる地域をカバーするタイリングを定義するステップと、該タイリングの各タイルの抵抗値を提供するステップと、該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点に対して推定関数値を決定するステップとを包含する。該抵抗値は、所定のタイルについて、抵抗値が、該所定のタイルの抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する道路網の頂点を接続するルートに関連するコストを表すように、定義される数値である。いくつかの利点は、地図をタイルに細分すること（ｓｕｂｄｉｖｉｄｉｎｇ）に関連し、各タイルの抵抗値の提供に関連する。第一に、推定関数は、たとえばナビゲーションシステムにおける該方法の実行時に、該抵抗値から確実にかつ容易に計算され得る。さらに、抵抗値は、タイルのみに位置する道路網の一部分によって決定される局所的なパラメータであるので、影響されたタイルの抵抗値を対応してアップデートすることによって、部分的な地図アップデートが容易に実行され得る。さらに、動的なルート決定が容易に実行され得る。さらにまた、抵抗値は一般的に単一の数値のみであるので、抵抗値を格納するために格納容量がほとんど必要とされない。
【００１２】
好ましくは、抵抗値は、所定のタイルに対して、抵抗値が、一対の頂点のエアライン距離に関連して、所定のタイルの境界に位置する一対の頂点を接続する最適ルートに関連するコストの下限であるように、定義され、ルートは所定のタイルを横断する。さらに好ましくは、抵抗値は、所定のタイルに対して、抵抗値が、一対の頂点のエアライン距離によって分割される所定のタイルの境界に位置する任意の一対の頂点を接続する最適ルートに関連するコストの最小値または下限であるように、定義される。次に、所定のタイルの境界に位置する任意の一対のテスト頂点に対して、所定のタイルの抵抗値とテスト一対の頂点のエアライン距離との積が、タイル内のテスト一対の頂点を接続する最適ルートに関連するコストの下限を提供する。したがって、抵抗値は、道路網の幾何学のみの特性と組み合わせられるときに、タイルを横断する任意のルートに関連するコストの下限を確立することを可能にする。これらの下限は、道路網の頂点のための推定関数を計算するために有利に使用され得る。
【００１３】
好ましくは、タイル境界頂点のための推定関数値を決定するステップは、目的地を含む目的地タイルを決定するステップと、目的地タイルの境界に位置する目的地タイル境界頂点と推定関数が計算されるべきタイル境界頂点とを接続する最適ルートに関連するコストの第１の下限を決定するステップとを包含する。特に、第１の下限は、タイルの抵抗値に応じて、またはタイリングの複数のタイルの抵抗値に応じて、決定され得る。より具体的には、第１の下限は、境界のみに位置する頂点を含む道路網のサブグラフに対して、ダイクストラのアルゴリズムを使用して決定され得、任意のタイルの境界に位置する第１および第２の頂点を接続するサブグラフのエッジに関連するコストは、任意のタイルの抵抗値と、第１および第２の頂点のエアライン距離とから決定される。特に、サブグラフのエッジに関連するコストは、第１および第２の頂点のエアライン距離が乗算された任意のタイルの抵抗値に等しく設定され得る。このようにして、目的地タイルの境界に位置する各頂点に対して、この目的地タイル境界頂点と推定関数が計算されるべきタイル境界頂点とを接続する最適ルートの下限が計算され得る。重要なことには、関連する最適ルート検索は、もともとの道路網に対応するグラフ上で実行される必要はなく、タイル境界のみに位置する頂点からなるサブグラフ上でのみ実行され、このようにこのステップの計算の複雑さを非常に低減する。好ましい実施形態において、下限は別々のアルゴリズムにおいて各目的地タイルに対して確立されるのではなく、すべての目的地タイル境界頂点が、出発点として同時にダイクストラのアルゴリズムに供給される。すべての目的地タイル境界頂点に対して、目的地タイル境界頂点とタイル境界頂点とを接続する最適ルートに関連するコストの下限が確立される場合には、この下限は、タイル境界頂点と目的地とを接続する最適ルートに関連するコストの下限をも提供し、したがってタイル境界頂点のための推定関数として使用され得る。
【００１４】
しかし、推定関数の正確性がさらに増大され得る。このために、タイル境界頂点のための推定関数を決定するステップは、好ましくは、目的地と目的地タイル境界頂点とを接続する最適ルートに関連するコストの第２の下限を決定するステップと、第１の下限および第２の下限を加算するステップとをさらに包含する。すべての目的地タイル境界頂点にわたって第１の下限と第２の下限とのこの合計の最小値を決定することによって、タイル境界頂点のための改善された推定関数値が得られる。
【００１５】
特に好ましい実施形態において、目的地からの目的地タイル境界頂点の一つずつへの最適ルートのコストを決定するために、目的地から開始して目的地タイルのみにおいてまずダイクストラのアルゴリズムを実行することによって、タイル境界頂点のための推定関数値が決定され、次に、該コストは、タイル境界のみに位置する頂点からなるサブグラフ上で実行されるさらなるダイクストラのアルゴリズムの中に入力され、サブグラフのエッジに関連するコストは、再び、上述のように、タイル抵抗値と頂点エアライン距離とに基づいて決定される。
【００１６】
別の好ましい実施形態において、タイル境界頂点のための推定関数値は、目的地タイルに位置する道路セグメントと、目的地タイル以外のタイルについて、境界のみに位置する頂点とを含む再定義されたグラフ上で、目的地から出発して、ダイクストラのアルゴリズムを実行することによって決定され、任意のタイルの境界に位置する２つの頂点を接続するエッジに関連するコストは、任意のタイルの抵抗値と頂点のエアライン距離とに基づいて決定される。
【００１７】
好ましくは、推定関数値は、上述の方法を使用して、道路網の各タイル境界頂点に対して決定される。代替的には、タイル境界頂点のための推定関数値の決定は、任意の適切な終了基準に応じて終了され得る。タイル境界に位置するすべての頂点に対して、この情報に基づいて推定関数値がひとたび決定されると、タイルの内側に位置する頂点のための推定関数値もまた容易に確立され得る。本発明の一実施形態において、該方法は、タイルの境界に位置するタイル境界頂点のための推定関数値と、内側頂点とタイル境界頂点とを接続する最適ルートに関連するコストの下限とから、タイルの内側に位置する内側頂点のための推定関数を決定するステップを包含する。後者の下限は、たとえばダイクストラのアルゴリズムを使用して決定され得る。代替的には、たとえば内側頂点とタイル境界頂点とのエアライン距離に基づいて、またはタイル境界頂点が位置するタイルのエッジからの内側頂点の最小エアライン距離に基づいて、より単純な推定が使用され得る。このようにして、正確な推定関数値が、タイルの内側に位置する各頂点に対して容易に決定され得る。道路網のすべての頂点について、または少なくともルート決定に関連するタイルに位置するすべての頂点について、推定関数値が知られる場合には、最適ルートを決定するために標準的なＡ＊−アルゴリズムが次に実行され得る。
【００１８】
道路セグメントのコストが増加する場合には、道路セグメントを含むタイルの抵抗値は一定であるかまたは増加もする、という意味において、上述のように定義される抵抗値は、対応するタイルに位置する道路セグメントに関連するコストの単調な関数であるので、本発明に係る方法は、動的なルート決定に容易に適合させられ得る。このために、該方法は、道路網の道路セグメントのコスト要因における増加を検出するステップと、コスト要因における検出された増加に応じて道路セグメントを含むタイルの抵抗値を増加させるステップとを包含する。特に、抵抗値は倍数的に増加させられ得る。代替的には、抵抗値は、道路セグメントのコストが増加させられたときでさえも、変更されないままにしておかれ得る。コスト要因が変化する道路セグメントを含むタイルの抵抗値を増加させることは、道路網の頂点のための推定関数を決定する前に実行される。道路セグメントのコストは、たとえば、トンネルを回避すること、フェリー接続や有料道路を回避すること、幹線道路を回避することなどの、ユーザプリファレンスを指定するユーザ入力に応じて、種々の方法で増加され得る。代替的または追加的に、交通メッセージが受信され得、道路セグメントのコストまたは道路セグメントが、受信された交通メッセージ信号に応じて増加され得る。たとえば、特定の道路セグメントについて交通渋滞が発表される場合、この道路セグメントのコストは、回避関数を実行するなどのように増加され得る。
【００１９】
本発明の一実施形態において、タイリングのタイルのタイルサイズは一定である。しかし、別の実施形態においては、タイリングは、出発点および目的地からの距離が増加するにつれてタイルのサイズが増加するように、定義される。この場合には、第１の規則的なタイリングの各タイルに対して第１の抵抗値が提供され、第２の規則的なタイリングの各タイルに対して第２の抵抗値が提供され、道路網の一部分を含む地域をカバーするタイリングは、第１の規則的なタイリングのタイルと、第２の規則的なタイリングのタイルとの両方を含み、タイリングのタイルの抵抗値は、第１および第２の抵抗値にそれぞれ対応するように選択される。タイリングのタイルのタイルサイズを適切に選択することによって、該方法はより一層効果的になされ得る。好ましい実施形態において、すべてのタイルは四角形の形状を有するが、本発明はこれに限定されない。むしろ、タイリングのタイルは、任意の形状を有するように定義され得、タイリングのすべてのタイルが同一の形状を有するに必要はない。
【００２０】
上記において、本発明による方法は、タイリングの各タイルに対して一つのみの抵抗値が提供されるように説明されたが、単一のタイルに対して複数の抵抗値も提供され得る。特に、タイリングの各タイルに対して、第１の基礎抵抗値および第２の基礎抵抗値が提供され、それぞれ、第１および第２の基礎コストモデルを表す。次に、第１および第２の基礎コストモデルの線形な組み合わせとして形成されたコストモデルに対して、第１および第２の基礎抵抗値の線形な組み合わせによって、抵抗値の下限が決定される。たとえば、第１および第２の基礎コストモデルは、最短ルートおよび最速ルートであり得る。多数の異なるコストモデルに対して抵抗値を提供するのではなくて、基礎をなす基礎コストモデルの抵抗値から、組み合わせられたコストモデルのタイル抵抗値を決定することが可能なので、より少数の基礎コストモデルのみに対して抵抗値を提供することで十分である。
【００２１】
別の実施形態において、各タイルに対して複数の抵抗値が提供され、所定のタイルについて、複数の抵抗値の一つずつが、たとえば、上方のエッジから下方のエッジまで、左のエッジから右のエッジまで、および、おそらく、追加のエッジの組み合わせなどの、特定の方向において、所定のタイルを横断する最適ルートに関連するコストを特徴づける。タイリングの各タイルの複数の抵抗値に基づいて決定された推定関数は、一般的により一層正確である。
【００２２】
上述の本発明の実施形態のいずれか一つについて記述されたように決定された推定関数に基づいて、本発明による方法において、出発点から目的地までの最適ルート検索が実行される。アルゴリズムは、推定関数を使用する任意のアルゴリズムであり得るが、好ましくはＡ＊−アルゴリズムである。
【００２３】
本発明は上述の道路網について説明されたが、本発明は等しい機能を有する任意のグラフに対して適用され得る。
【００２４】
本発明の別の局面によれば、道路網データを前処理する方法が提供され、該方法は、道路網の少なくとも一部分が含まれる地域をカバーするタイリングを定義するステップと、タイリングのタイルに対して、タイルの境界に位置する頂点を決定するステップと、一対の頂点のエアライン距離によって分割されるタイルの境界に位置する任意の一対の頂点を接続する最適ルートに関連するコストの下限を決定するステップと、決定された下限を出力するステップとを包含する。特に、下限は、一対の頂点のエアライン距離によって分割されるタイルの境界に位置する任意の一対の頂点を接続するルートに関連するコストの最小値に等しく設定され得る。このようにして決定された下限は、抵抗値を提供し、該抵抗値は、本発明に応じて最適ルートを決定する方法において使用され得る。
【００２５】
本発明の別の局面によれば、道路網における出発点から目的地までのルートを決定するシステムが提供され、該システムは、道路網の複数の頂点のための推定関数を使用し、該推定関数は、道路網の頂点と目的地とを接続するルートに関連するコストの下限を提供し、該システムは、道路網データを含む第１の格納ユニットと、各タイルについてのタイリングと抵抗値とを定義するタイリング定義データを含む第２の格納ユニットと、タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点のための推定関数値を決定する処理ユニットとを備える。再び、第２の格納ユニットに含まれる所定のタイルの抵抗値は、所定のタイルの境界に位置する頂点を接続するルートに関連するコストの下限が、所定のタイルの抵抗値から処理ユニットによって導出され得るように、所定のタイルの境界に位置する道路網の頂点を接続するルートに関連するコストを表す。この構成を有するシステムは、本発明に応じてルートを決定する方法を実行し、したがってそれに関連する利点を利用するように適合される。
【００２６】
特に、該システムにおいて、処理ユニットは、目的地を含む目的地タイルの境界に位置する目的地タイル頂点を決定し得、タイル境界頂点と目的地タイル境界頂点とを接続する最適ルートに関連するコストの下限を計算し得、該下限はタイリングのタイルの抵抗値に応じて決定される。特に、処理ユニットは、下限を決定するために、目的地タイル境界頂点または同時に原点としてのすべての目的地タイル頂点を有する、ダイクストラのアルゴリズムを使用するように適合され得る。上記に詳細に説明されたように、このようにして、推定関数は、タイル境界頂点に対して容易に決定され得る。ダイクストラのアルゴリズムを使用するのではなく、推定関数はまた、目的地タイル境界頂点から出発してＡ＊−アルゴリズムを使用して、かつエアライン距離によって実行されるべきルート検索の出発点に対するコストを推定して、決定され得る。推定関数がすべての関連するタイルに対して決定されることを確実にするために、出発点が拡大された後でさえも、所定の時間にわたってＡ＊−アルゴリズムが計算される。推定関数値が後の段階において必要とされる場合には、最適ルート検索の間に、これらはオンデマンドで計算され得る。好ましい実施形態において、該システムは、タイル頂点の座標と処理ユニットによって決定される関連する推定関数値とを格納する、メモリユニットをさらに備える。有利な実施形態において、タイル境界頂点の座標は、対応するタイルの境界によって規定される線に沿ったタイル境界頂点の位置を指定する一次元座標の形で格納され得る。
【００２７】
さらに、処理ユニットは、道路網の道路セグメントについての交通メッセージ信号を受信し得、受信された交通メッセージ信号に応じて、道路セグメントを含むタイルの抵抗値を変更し得る。代替的には、それぞれのタイルの抵抗値は、変更されずに留まり得る。
【００２８】
該システムは、タイリングのタイルの抵抗値に応じて決定され、メモリユニットに格納された推定関数値を使用するＡ＊−アルゴリズムを使用して、出発点から目的地までの最適ルートを、さらに好ましくは決定する。
【００２９】
本発明に応じてルートを決定する該システムにおいて、第１および第２の格納ユニットは、単一のフィジカルデバイスであり得るか、または別のデバイスであり得る。たとえば、第１および第２の格納ユニットは、ＣＤ、ＤＶＤ、メモリカード、またはナビゲーションシステムの内蔵ハードディスクであり得る。
【００３０】
本発明の別の局面にれば、ナビゲーションシステムが提供され、該ナビゲーションシステムは、目的地を入力する入力手段と、決定されたルートを出力する出力手段と、本発明のいずれか一つの局面または実施形態に応じてルートを決定するシステムとを備え、該システムは、そこから目的地を受信する入力手段と、そこへ決定されたルートを出力する出力手段とに結合される。該ナビゲーションシステムは、現在の車両位置を決定する位置決定手段などの、ナビゲーションシステムにおいて通例使用される任意の構成要素をさらに備え得、ナビゲーションシステムは、たとえば、ＧＰＳ受信機、ルート決定のために出発点として現在の車両位置を提供するためのルートを決定する、システムに結合された位置決定手段、または交通メッセージ信号をそこへ提供するために処理ユニットに結合されたＴＭＣ受信機を備え得る。
【００３１】
再び、「道路網」という用語は、本発明を説明するためにこの書類の全体を通して使用されるが、本発明の適用は、物理的な道路網に限定されないことが留意されるべきである。むしろ、本発明は、最適ルート検索が重要であり得る任意のネットワークに適用され得る。例は、フェリー接続、コンピュータネットワークにけるデータ接続、または送電線を含む。
【００３２】
さらに、本発明は、複数のタイルが定義される面において定義される道路網に関連して説明されるが、本発明は面において定義されるグラフに限定されないことが留意されるべきである。むしろ、本発明の原理は、より高次元のオブジェクト、たとえば３次元グラフについて等しく適用可能である。
【００３３】
本発明の適用の主な分野は、道路網における、特に車両に搭載されたナビゲーションシステムにおける、最適ルートの決定である。
【００３４】
本発明は、さらに、以下の手段を提供する。
【００３５】
（項目１）
道路網の出発点から目的地までのルートを決定する方法であって、
該方法は、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
該道路網の少なくとも一部分が含まれる地域をカバーするタイリング（Ｔ）を定義するステップと、
該タイリングの各タイルの抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数値を決定するステップと
を包含し、
所定のタイルの抵抗値は、該所定のタイルの境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表す、
方法。
【００３６】
（項目２）
上記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルにおける上記道路網の幾何学的特性に関連して、該所定のタイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を接続するルート（１１、１３）に関連するコストを表す、ことを特徴とする、項目１に記載の方法。
【００３７】
（項目３）
上記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルの境界に位置する一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する上記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、項目１または２に記載の方法。
【００３８】
（項目４）
上記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連するコストの最小値である、ことを特徴とする、項目３に記載の方法。
【００３９】
（項目５）
上記タイル境界頂点（２３）に対して上記推定関数値を決定するステップが、
上記目的地（２２）を含む目的地タイル（Ｔ３）を決定するステップと、
該目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）と、該タイル境界頂点（２３）と、を接続する最適ルートに関連するコストの第１の下限を決定するステップと
をさらに包含する、ことを特徴とする、項目１ないし４のいずれか１項に記載の方法。
【００４０】
（項目６）
上記第１の下限が、上記タイルの上記抵抗値に応じて、または上記タイリングの複数のタイルの上記抵抗値に応じて、決定される、ことを特徴とする、項目５に記載の方法。
【００４１】
（項目７）
上記第１の下限が、タイル境界のみに位置する頂点（２３〜２５）を含む上記道路網のサブグラフに対して、ダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、項目６に記載の方法。
【００４２】
（項目８）
任意のタイル（Ｔ２）の境界に位置する第１および第２の頂点（２３、２４）を接続するサブグラフのエッジ（２６ａ）に関連するコストが、該任意のタイルの抵抗値と、該第１および第２の頂点（２３、２４）のエアライン距離とから決定される、ことを特徴とする、項目７に記載の方法。
【００４３】
（項目９）
上記サブグラフのエッジ（２６ａ）に関連する上記コストが、上記第１および第２の頂点（２３、２４）のエアライン距離が乗算された上記任意のタイル（Ｔ２）の抵抗値に等しく設定される、ことを特徴とする、項目８に記載の方法。
【００４４】
（項目１０）
上記タイル境界頂点（２３）に対して上記推定関数を決定する上記ステップが、
上記目的地（２２）と、上記少なくとも一つの目的地タイル境界頂点（２４、２５）と、を接続する最適ルートに関連するコストの第２の下限を決定するステップと、
上記第１の下限と上記第２の下限とを加算するステップと
をさらに含む、ことを特徴とする、項目５ないし９のいずれか１項に記載の方法。
【００４５】
（項目１１）
上記タイル境界頂点（２３）に対して上記推定関数値を決定する上記ステップが、
すべての目的地タイル境界頂点（２４、２５）にわたる上記第１の下限と上記第２の下限との合計の最小値を決定するステップをさらに含む、ことを特徴とする、項目１０に記載の方法。
【００４６】
（項目１２）
上記タイル（Ｔ２）の上記境界に位置するタイル境界頂点（２３、２４）のための推定関数値からの該タイル（Ｔ２）の内側に位置する内側頂点（２９）のための推定関数値と、該内側頂点（２９）と該タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの下限と、を決定する、ステップによって特徴付けられる、項目１ないし１１のいずれか１項に記載の方法。
【００４７】
（項目１３）
上記内側頂点（２９）と上記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの上記下限が、該内側頂点（２９）と該タイル境界頂点（２３、２４）とのエアライン距離から決定される、ことを特徴とする、項目１２に記載の方法。
【００４８】
（項目１４）
上記内側頂点（２９）と上記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの上記下限が、該タイル境界頂点（２３、２４）が位置する上記タイルのエッジからの上記内側頂点の最小エアライン距離（２７’、２８’）から決定される、ことを特徴とする、項目１２に記載の方法。
【００４９】
（項目１５）
上記道路網の道路セグメントのコスト要因における増加を検出するステップと、
該コスト要因における検出された増加に応じて、該道路セグメントを含むタイルの抵抗値を増加させる、ステップとによって特徴づけられる、項目１ないし１４のいずれか１項に記載の方法。
【００５０】
（項目１６）
上記道路セグメントを含む上記タイルの抵抗値を増加させることが、乗法による、ことを特徴とする、項目１５に記載の方法。
【００５１】
（項目１７）
上記道路セグメントの上記コスト要因が、ユーザ入力に依存して増加する、ことを特徴とする、項目１５または１６に記載の方法。
【００５２】
（項目１８）
交通メッセージ信号を自動的に受信し、上記道路セグメントの上記コスト要因が該受信された交通メッセージ信号に依存して増加する、ステップによって特徴づけられる、項目１５ないし１７のいずれか１項に記載の方法。
【００５３】
（項目１９）
上記タイリング（Ｔ）のタイル（Ｔ１’、Ｔ２’、Ｔ１’’〜Ｔ６’’）のタイルサイズが、上記出発点と上記目的地からの増加する距離とともに増加する、ことを特徴とする、項目１ないし１８のいずれか１項に記載の方法。
【００５４】
（項目２０）
第１の抵抗値が、第１の規則的なタイリング（Ｔ’）の各タイルに対して提供され、
第２の抵抗値が、第２の規則的なタイリング（Ｔ’’）の各タイルに対して提供され、
上記地域をカバーする上記タイリング（Ｔ）が、該第１の規則的なタイリング（Ｔ’）のタイル（Ｔ１’、Ｔ２’）と、第２の規則的なタイリング（Ｔ’’）のタイル（Ｔ１’’〜Ｔ６’’）とを含み、該タイリングのタイルの抵抗値が、対応する該第１および該第２の抵抗値とそれぞれ等しい、ことを特徴とする、項目１９に記載の方法。
【００５５】
（項目２１）
上記タイリング（Ｔ）の各タイルに対して、第１の基礎抵抗値および第２の基礎抵抗値が提供され、これらの抵抗値が第１および第２の基礎コストモデルをそれぞれ表し、該第１および第２の基礎コストモデルの線形な組み合わせとして形成されるコストモデルに対して、該抵抗値の下限が、該第１および第２の基礎抵抗値の線形な組み合わせによって決定される、ことを特徴とする、項目１ないし２０のいずれか１項に記載の方法。
【００５６】
（項目２２）
上記出発点から上記目的地までの最適ルートが、上記タイリングのタイルの抵抗値に応じて決定される推定関数を使用するＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、項目１ないし２１のいずれか１項に記載の方法。
【００５７】
（項目２３）
グラフ上の目的地へのルートを決定する方法であって、
該方法は、該グラフの複数の頂点のための推定関数を使用し、
該推定関数は、該グラフの頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該グラフの少なくとも一部分が含まれる、ステップと、
該タイリングの各タイルに対して抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数を決定するステップと
を含み、
所定のタイルの抵抗値は、該所定のタイルの該境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値に基づいて導出可能であるように、該所定のタイルの境界に位置する該グラフの頂点を接続するルートに関連するコストを表す、方法。
【００５８】
（項目２４）
道路網データを前処理する方法であって、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該道路網の少なくとも一部分が含まれる、ステップと、
該タイリングのタイル（Ｔ０）に対して、該タイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を決定するステップと、
任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離によって分割される該タイルの境界に位置する該一対の頂点を接続する最適ルート（１１、１３）に関連するコストの下限を決定するステップと、
該決定された下限を出力するステップと
を含む、方法。
【００５９】
（項目２５）
上記下限が、任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）の上記エアライン距離によって分割される上記タイルの境界に位置する該一対の頂点を接続するルートに関連する上記コストの最小値から決定される、ことを特徴とする、項目２４に記載の方法。
【００６０】
（項目２６）
上記下限が、出力の前に離散化される、ことを特徴とする、項目２４または２５に記載の方法。
【００６１】
（項目２７）
道路網の出発点から目的地までのルートを決定するシステムであって、
該システムは、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該システムは、
道路網データを含む第１の格納ユニット（３）と、
タイリングを定義するタイリング定義データと、各タイルの抵抗値と、を含む第２の格納ユニット（４）と、
該タイリングの該タイルの該抵抗値に応じて、タイル境界に位置するタイル境界頂点のための推定関数を決定する処理ユニット（２）と
を備え、
該第２の格納ユニット（４）に含まれる、所定のタイルの該抵抗値は、該所定のタイルの該境界に位置する頂点を接続する該ルートに関連するコストの下限が、該所定のタイルの該抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表す、システム。
【００６２】
（項目２８）
上記第２の格納ユニット（４）に含まれる、上記所定のタイル（Ｔ０）の上記抵抗値が、該所定のタイルの上記境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する上記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、項目２７に記載のシステム。
【００６３】
（項目２９）
上記第２の格納ユニット（４）に含まれる、上記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連する上記コストの最小値である、ことを特徴とする、項目２７または２８に記載のシステム。
【００６４】
（項目３０）
上記処理ユニット（２）が、上記目的地（２２）を含む目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）を決定し、上記タイル境界頂点（２３）と該少なくとも一つの目的地タイル境界頂点（２４、２５）とを接続する最適ルートに関連するコストの下限を計算し、該下限が上記タイリングのタイルの抵抗値に応じて決定される、ことを特徴とする、項目２７ないし２９のいずれか１項に記載のシステム。
【００６５】
（項目３１）
上記下限が、上記目的地タイル境界頂点（２４、２５）を原点として有するダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して計算される、ことを特徴とする、項目３０に記載のシステム。
【００６６】
（項目３２）
上記タイル境界頂点（２３）の座標と、上記処理ユニット（２）によって決定される該タイル境界頂点（２３）のための上記推定関数値と、を格納するメモリユニット（５）、によって特徴づけられる、項目２７ないし３１のいずれか１項に記載のシステム。
【００６７】
（項目３３）
上記メモリユニット（５）が、上記タイルの境界によって規定される線に沿った上記タイル境界頂点（２３）の位置を指定する一次元的座標の形式において、該タイル境界頂点の該座標を格納する、ことを特徴とする、項目３２に記載のシステム。
【００６８】
（項目３４）
上記処理ユニット（２）が、上記道路網の道路セグメントのための交通メッセージ信号を受信し、該受信された交通メッセージ信号に応じて、該道路セグメントを含むタイルの抵抗値を変更する、ことを特徴とする、項目２７ないし３３のいずれか１項に記載のシステム。
【００６９】
（項目３５）
上記処理ユニット（２）が、上記タイリングのタイルの上記抵抗値に応じて決定されて上記メモリユニット（５）に格納された推定関数値を使用するＡ＊−アルゴリズムを使用して、上記出発点から上記目的地までの最適ルートを決定する、ことを特徴とする、項目２７ないし３４のいずれか１項に記載のシステム。
【００７０】
（項目３６）
上記システムが、項目１ないし２３のいずれか１項に記載の方法を実行する、ことを特徴とする、項目２７ないし３５のいずれか１項に記載のシステム。
【００７１】
（項目３７）
ナビゲーションシステムであって、
目的地を入力する入力手段（６）と、
決定されたルートを出力する出力手段（７）と、
項目２７ないし３６のいずれか１項に応じてルートを決定するシステム（２〜５）とを備え、
該システムは、そこから該目的地を受信する該入力手段（６）と、そこへ決定されたルートを出力する出力手段（７）とに結合されている、ナビゲーションシステム。
【００７２】
（項目３８）
現在の車両位置を決定する位置決定手段（８）を備え、該位置決定手段（８）は、上記ルートを決定するシステム（２〜５）に結合され、該現在の車両位置を上記出発点として提供する、項目３７に記載のナビゲーションシステム。
【００７３】
（項目３９）
上記位置決定手段（８）が、ＧＰＳ受信機を備える、ことを特徴とする、項目３８に記載のナビゲーションシステム。
【００７４】
（項目４０）
交通メッセージ信号を提供する上記処理ユニット（２）に結合されたＴＭＣ受信機（９）、によって特徴づけられる、項目３７ないし３９のいずれか１項に記載のナビゲーションシステム。
【００７５】
（摘要）
道路網の出発点から目的地までのルートを決定する方法およびシステムが提供され、道路網の頂点のための推定関数が使用され、タイリングが道路網の少なくとも一部分が含まれる地域をカバーするように定義され、タイリングの各タイルの抵抗値が提供され、道路網の頂点のための推定関数の値がタイリングのタイルの抵抗値に応じて決定される。好ましい実施形態において、所定のタイル（Ｔ０）の抵抗値は、一対の頂点のエアライン距離（１２、１４）によって分割される所定のタイルの境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を接続する最適ルート（１１、１３）に関連するコストの下限または最小値である。
【発明を実施するための最良の形態】
【００７６】
図１を参照して、本発明の実施形態によるナビゲーションシステム１が説明される。該システムは、Ａ＊−アルゴリズムなどの推定関数を使用するアルゴリズムを使用して、道路網の出発点から目的地までのルートを決定するように適応される。システムは、処理ユニット２、道路網データを含む第１の格納ユニット３、タイリング定義データおよびタイリングのタイルの抵抗値を含む第２の格納ユニット４、およびメモリユニット５を備え、これらの構成要素が組み合わせられて、本発明の実施形態に応じて、ルートを決定するシステムを形成する。第１の格納ユニット３および第２の格納ユニット４は、異なるフィジカルデバイスである得るか、または単一のフィジカルデバイス、たとえば、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＤＶＤ、メモリカード、または内蔵ハードディスクであり得る。
【００７７】
第１の格納ユニット３に格納される道路網データは、たとえば、道路セグメントの出発点および終点の地理的位置などの、道路のセグメント位置と方向性とに関するグラフィカル情報、および道路セグメントを横断する、長さ、特徴的な移動速度、および／または特長的な移動時間を定量化する追加情報を備える、従来の道路網データである。より一般的には、一つまたはいくつかの属性が、各道路セグメントに関連づけられ、特定のコストモデルに対して道路セグメントを横断することに関連するコスト、ならびに、一般的に、道路セグメント交差点に関連するコストを特定する。
【００７８】
第２のメモリユニット４に格納されるタイリング定義データ４ａ〜４ｃは、タイリングのすべてのタイルの配置を決定する。すべてのタイルが均等なサイズを有する四角形のタイリングの単純な場合について、各タイルは、その角の一つの座標によって、またはタイリングにおけるタイルの位置を指定するインデックスまたは一対のインデックスによって、一意に決定される。重要なことには、以下に図２を参照してより詳細に説明されるように、第２の格納ユニットもまた、タイリングの各タイルの抵抗値を含み、抵抗値はタイルを横断することに関連するコストを表す。
【００７９】
第１の格納ユニット３および第２の格納ユニット４に格納されるデータは、処理ユニット２によるさらなる処理のために、メモリユニット５に格納され得る。
【００８０】
ナビゲーションシステム１は、たとえば目的地またはユーザプリファランスを入力する入力手段６、決定されたルートを出力する出力手段７、たとえばディスプレイまたは音声出力ユニット、ＧＰＳ受信機を備える位置決定手段８、およびＴＭＣ受信機９を、さらに備える。
【００８１】
次に、図２を参照して、抵抗値を決定する方法を記述することによって、タイルの抵抗値の定義がより詳細に説明される。図２は、道路網の部分が位置するタイルＴ０を示す。道路セグメントは、四角形によって示される頂点において終了し、小さな四角形はタイルの内部に位置する頂点を示し、一方大きな四角形はタイルの境界に位置する頂点ｔｂｖ１〜ｔｂｖ４を示す。
【００８２】
タイルＴ０の抵抗値を決定するために、まず、境界に位置するすべての頂点、この場合は頂点ｔｂｖ１〜ｔｂｖ４が決定される。次に、タイル境界に位置するこれらの各対の頂点に対して、たとえばダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムを使用して、一対の頂点を接続する最適ルートが決定される。頂点ｔｂｖ１とｔｂｖ２とからなる対、および頂点ｔｂｖ２とｔｂｖ４とからなる対について、これらの最適ルートは、それぞれ図２Ａおよび図２Ｂにおける太線１１および１３として模式的に示される。次に、そのような各対の頂点に対して、エアライン距離（ａｉｒ−ｌｉｎｅ ｄｉｓｔａｎｃｅ）が計算され、エアライン距離は、頂点ｔｂｖ１とｔｂｖ３とについて、および頂点ｔｂｖ２とｔｂｖ４とについて、それぞれ図２Ａおよび図２Ｂにおける点線１２および１４として模式的に示される。次に、２つの頂点を接続する最適ルートに関連するコストと、２つの頂点のエアライン距離との、商（ｑｕｏｔｉｅｎｔ）が計算される。最後に、タイルの境界に位置する種々の対の頂点に対する、すべてのこれらの商の最小値が決定される。タイルＴ０の抵抗値は、この最小値に等しく設定される。
【００８３】
したがって、タイルの抵抗値は、以下の数式によって与えられる：
【００８４】
【数１】
ここで、Ｒはタイルの抵抗値を示し、ｔｖｂｉおよびｔｂｖｊはタイルの境界に位置する頂点を示し、ｃｏｓｔ（ｔｖｂｉ；ｔｂｖｊ）はｔｖｂｉとｔｂｖｊとを接続してタイルを横断する最もコストの低い経路に関連するコストを示し、ａｉｒ−ｌｉｎｅ ｄｉｓｔａｎｃｅ（ｔｖｂｉ；ｔｂｖｊ）は一対の頂点ｔｖｂｉとｔｂｖｊとのエアライン距離を示す。コストは、道路セグメントコストと道路セグメント交差点に関連するコストの両方の寄与を一般的に含み、両方とも考慮に入れられる。
【００８５】
抵抗値の定義によって、タイルの境界に位置する任意の頂点ｔｖｂｉとｔｂｖｊとに対して、これらの頂点を接続する最適ルートに関連するコストは、以下の不等式を満たす：
【００８６】
【数２】
二つの頂点のエアライン距離は道路網の幾何学にのみ依存するので、一対の頂点を接続する最適ルートに関連するコストに対する下限を提供するために、タイルの抵抗値Ｒは既知であるので（数式２）の右側は容易に計算され得ることが、留意されるべきである。以下により詳細に説明されるように、この特徴は、本発明に応じてルートを決定する方法によって、有利に利用される。
【００８７】
道路網における最適ルート検索は、有向グラフにおけるルート検索に一般的に対応することが留意されるべきであり、すなわち、たとえば一方通行道路がタイルの中に位置する場合、または道路セグメントの速度制限が反対の移動方向で異なる場合に、ｔｂｖ１からｔｂｖ３へのルートに関連するコストは、ｔｂｖ３からｔｂｖ１へのルートに関連するコストとは異なり得る。したがって、一般的に、（数式１）の右側の式は、有向グラフに対して評価されなければならず、すなわち、商の分子における頂点の順序は重要である。
【００８８】
さらに、タイル境界に位置する頂点を接続する最適ルートに関連するコストは、使用されるコストモデルに一般的に依存する。したがって、タイリングの各タイルに対して、最短ルートおよび最速ルートなどの最も重要なコストモデルに対していくつかの抵抗値が一般的に決定され、異なる抵抗値が第２の格納ユニット４に格納される。この点で、抵抗値は自動車内で計算されるのではなく、ルート決定における次の使用のための道路網データの前処理のフェーズの間に計算されるということが、再び強調される。
【００８９】
図３を参照して次に説明されるように、上記に示されたように計算される抵抗値は、ルート決定において有利に使用され得る。より具体的には、たとえばＡ＊−アルゴリズムにおいて使用されるような推定関数は、抵抗値から容易に引き出され得る。
【００９０】
図３は、例示的な道路網およびタイリングＴを示す。タイリングは、タイルＴ１〜Ｔ９を備える。道路網の頂点は、この場合もやはり、四角形によって示され、大きな四角形はタイル境界に位置する頂点を示す。説明の目的のみのために、最適ルートは、出発点２１から目的地２２にかけて決定されるものと想定されるべきである。さらに、上記に示されたように決定される抵抗値は、タイリングのすべてのタイルＴ１〜Ｔ９について既知であると想定される。Ａ＊−アルゴリズムを使用して最適ルートを決定するために、推定関数は道路網の各頂点について既知でなければならず、推定関数は道路網の任意の頂点と目的地とを接続する最適ルートに関連するコストの下限を提供する。
【００９１】
タイル境界に位置する頂点、たとえば図３における頂点２３について、この頂点に関する推定関数の値は以下のように決定され得る。
【００９２】
まず、目的地２２を含む目的地タイルＴ３が特定され、目的地タイルの境界に位置する頂点２４および２５が特定される。次に、タイル境界のみに位置する道路網の頂点、すなわち図３の大きな四角形によって示される頂点からなるグラフに対して、目的地タイルＴ３の境界に位置する頂点２４および２５の一つずつから始めて、ダイクストラのアルゴリズムが実行される。このサブグラフのエッジの一部は、図３における点線２６ａ〜２６ｄによって示される。サブグラフの任意のそのようなエッジに関連するコストは、（数式２）によって決定され得、すなわち、サブグラフエッジに関連するコストは、エッジによって接続される頂点のエアライン距離が乗算されたサブグラフエッジによって横断されるタイルの抵抗値に等しく設定される。たとえば、エッジ２６ａに関連するコストは、頂点２３および２４のエアライン距離が乗算されたタイルＴ２の抵抗値に等しく設定される。タイル境界のみに位置する頂点からなるサブグラフは、もともとの道路網よりも一般的にはるかに小さいので、目的地タイルの境界に位置する頂点２４および２５のうちの任意の一つから始めて、ダイクストラのアルゴリズムは容易に実行され得る。好ましい実施形態において、これらの頂点のすべてを一組の原点としてダイクストラのアルゴリズムの中に入力することによって、ダイクストラのアルゴリズムは、すべての目的地タイル境界頂点に対して同時に実行される。さらに、（数式２）によって、サブグラフ上の最適ルートに関連するコストは、もともとの道路網の最適ルートに関連するコストに関する下限である。たとえば、サブグラフ上の最適ルートが、エッジ２６ａを介して頂点２４を頂点２３に接続すると想定して、エッジ２６ａの長さによって乗算されるタイルＴ２の抵抗値は、もともとの道路網の頂点２４から頂点２３への最適ルートに関連するコストに関する下限を提供する。
【００９３】
したがって、タイル境界に位置する頂点２３と、目的地タイルの境界に位置する頂点２４および２５のうちの任意の一つとを接続する最適ルートに関連するコストが、サブグラフ上でひとたび知られると、すべてのこれらのコストの最小値もまた、もともとのグラフ上の最適ルートに関連するコストの下限を提供する。
【００９４】
より一般的には、タイル境界に位置する頂点ｔｂｖのための推定関数（ｅｓｔｉｍａｔｉｏｎ ｆｕｎｃｔｉｏｎ（ｔｂｖ））は、以下の数式から確立され得る：
【００９５】
【数３】
ここで、ｄｔｂｖｉは目的地タイルの境界に位置する頂点を示し、ｃｏｓｔｓＳＧはサブグラフ上の最適ルートに関連するコストを示し、サブグラフは上記に説明されたように定義され、ルートはｄｔｂｖｉとｔｂｖとを接続する。上記の式の右側に関する最小値は、目的地タイルの境界に位置するすべての頂点にわたって取られる。
【００９６】
推定関数の正確性は、目的地２２を目的地タイル境界頂点２４および２５に接続するルートに関連するコストを考慮に入れることによって、さらに改善され得る。
【００９７】
【数４】
ここで、（数式４）の右側に関する角括弧における第２項は、目的地を目的地タイル境界頂点の一つずつと接続する最適ルートのコストを表す。これらのコストは、目的地タイルＴ３においてダイクストラのアルゴリズムを使用して、たとえば決定され得る。しかし、任意の下限は、実際のコストの代わりに使用され得る（たとえばエア距離（ａｉｒ ｄｉｓｔａｎｃｅ）のみに基づいた下限）。普通の下限の場合については、（数式４）の角括弧における第２項がゼロに設定され、（数式４）が（数式３）に置き換えられる。
【００９８】
好ましい実施形態において、すべての目的地タイル境界頂点が原点のセットとして同時に入力されるようにダイクストラのアルゴリズムが使用され、たとえばもともとの道路網の目的地タイル上でダイクストラのアルゴリズムを実行することによってコスト（ｄ；ｄｔｂｖｉ）が既知である場合に、かつこれらの値が上述にように定義されるサブグラフ上で実行されるダイクストラのアルゴリズムに入力される場合に、（数式４）の右側はこのダイクストラのアルゴリズムによって容易に決定され得る。
【００９９】
代替的に、（数式４）の右側は、目的地タイルの中に位置するもともとの道路セグメントと、目的地タイルの外側ではタイルのエッジのみに位置する頂点を接続するエッジとを含む、新しいグラフを定義することによって、計算され得る。図１１に示される、そのような再定義されたグラフが、以下により詳細に説明される。再定義されたグラフ上でダイクストラのアルゴリズムを実行することによって境界頂点に対して決定されたコストは、各タイル境界頂点について（数式４）の右側である。
【０１００】
上記の説明は説明的な目的のために頂点２３に限定されているが、タイル境界に位置する任意の頂点のための推定関数は、上述のように決定され得ることが理解される。タイル境界に位置するすべての頂点のための推定関数がひとたび決定されると、次に説明されるように、それはタイルの内側に位置する頂点についても容易に決定され得る。
【０１０１】
図４および５は、図３のタイリングＴのタイルＴ２とその中に位置する道路網の部分とを示す。推定関数は頂点２３および２４に対してすでに決定され、その推定関数はこれらの頂点と目的地とを接続する最適ルートに関連するコストの下限を提供するので、タイルＴ２の内側に位置する頂点２９のための推定関数は以下のように決定され得る。
【０１０２】
一実施形態において、頂点２９を頂点２３および２４にそれぞれ接続する最適ルートに関連する正確なコストは、ダイクストラのアルゴリズムを使用して決定される。次に、これらのコストと、タイル境界に位置する頂点に対応する推定関数との合計が計算され、合計のうちの小さいほうの一つが頂点２９のための推定関数値を提供する。
【０１０３】
しかし、頂点２９を頂点２３および２４に接続する最適ルートに関連する正確なコストを計算する必要はない。むしろ、任意の適切な下限が使用され得る。たとえば、図４において示されるように、それぞれ点線２７および２８として模式的に示されるエアライン距離は、頂点２９とタイルＴ２の境界に位置する頂点とを接続するルートに関連するコストを推定するために使用され得る。
【０１０４】
図４において示されるエアライン距離の計算は平方根の評価を伴なうので、推定関数の計算をさらに促進するために、代替的に、図５において模式的に示されるように、垂直距離２７’および２８’も、タイルの内側のルートに関連するコストの下限として使用され得る。たとえば、最短ルート検索を想定して、頂点２９の推定関数は、垂直距離２７’をプラスした頂点２４の推定関数と、垂直距離２８’をプラスした頂点２４の推定関数とのうちの、小さいほうに等しく設定される。最後に、さらに別の実施形態において、タイルの内側の各頂点のための推定関数は、このタイルの境界に位置する頂点の推定関数の最小値に等しく単純に設定され得、これによって、推定関数の正確性を犠牲にして、推定関数を決定することにおける計算の複雑さを低減する。
【０１０５】
図２〜５は、本発明の種々の実施形態による推定関数の決定の基礎をなす根本的な原理を説明する役割を果す。図２を参照して説明されるような抵抗値の決定も、本発明の範囲によって含まれることが意図されることが留意されるべきである。
【０１０６】
次に、図６〜１０を参照して、種々の実施形態に応じて出発点から目的地までのルートを決定する方法が、詳細に説明される。
【０１０７】
図６は、本発明の実施形態に応じてルートを決定する方法を、模式的に示すフローチャートを示し、該方法は一般的に３０によって示されている。まず、ステップ３１において、出発点および目的地が受信される。出発点および目的地に関する情報は、たとえば、ユーザ入力によって提供され得、あるいは出発点もまた位置決定手段８によって自動的に提供され得る。
【０１０８】
ステップ３２において、タイリングＴが定義され、タイリングＴは、ルート検索が実行されるべき道路網の少なくとも部分が含まれるべき地域をカバーする。ステップ３３において、推定関数が道路網の複数の頂点に対して決定され、このステップは以下に図７〜１０を参照してより詳細に説明される。道路網のすべてのまたは少なくともすべての関連する頂点に対して、ひとたび推定関数が知られると、ステップ３６において、ステップ３３においてすでに決定された推定関数に基づいて、出発点から目的地までの最適ルートを決定するためにＡ＊−アルゴリズムが実行される。最後に、ステップ３７において、出力手段７を介して、たとえば電子地図の形でまたは音声出力として、最適ルートが出力される。
【０１０９】
本発明の一実施形態において、図７〜９を参照して次に説明されるように、道路網の頂点のための推定関数を決定するステップ３３は、２つのステッププロセスとして実行される。図７のフローチャートにおいて模式的に示されるように、まず、ステップ３４において、境界に位置する頂点に対して推定関数が決定され、次に、ステップ３５において、タイル内側に位置する頂点に対して推定関数が決定される。
【０１１０】
図８は、タイル境界に位置する頂点に対して推定関数を決定するステップ３４を表すフローチャートを模式的に示す。まず、ステップ３４１において、目的地ｄを含むタイルＴｄが決定され、ステップ３４２において、Ｔｄの境界に位置する頂点が決定され、これらの頂点はｄｔｂｖｉによって示される。ステップ３４３において、目的地タイルの境界に位置する各頂点に対して、目的地ｄと目的地タイル境界頂点とを接続する最適ルートに関連するコストの下限が決定され、下限はｃｏｓｔ（ｄｔｂｖｉ）として示される。この下限は、たとえば、目的地タイル上でダイクストラのアルゴリズムを使用して、または上記の図３を参照して説明された任意の他の適切な方法を使用して、決定され得る。
【０１１１】
ステップ３４４において、新しいグラフが定義され、そのグラフは、もともとの道路網のサブグラフであり、境界のみに位置する頂点を含む。重要なことには、上記に図３を参照して説明されたように、サブグラフのエッジに関連するコストは、一般的に道路網の幾何学的特性とともに、タイリングの種々のタイルの抵抗値に基づいて決定される。ステップ３４５において、目的地タイルに位置する頂点の一つずつから始まる、ダイクストラのアルゴリズムが実行される。好ましい実施形態において、ステップ３４５におけるダイクストラのアルゴリズムは、一回のみ実行され、原点のセットとしてすべての目的地タイル境界頂点を有する。
【０１１２】
ダイクストラのアルゴリズムの代わりに、Ａ＊−アルゴリズムが、ステップ３４５において、目的地タイル境界頂点から出発点に向けて、エアラインベースの推定を使用して、実行され得る。
【０１１３】
最後に、ステップ３４６〜３４８において、これらの頂点のための推定関数を決定するために、タイル境界に位置する頂点にわたって反復が実行される。ステップ３４６において、タイル境界に位置する頂点が選択される。ステップ３４７において、上記の（数式４）を参照して説明されたように、すなわち、ステップ３４５において決定される、頂点と目的地タイルの境界に位置する頂点とを接続する最適ルートに関連するコストの下限と、目的地タイルの境界に位置する頂点と目的地とを接続するルートに関連するコストとから、この頂点のための推定関数が決定される。最後に、ステップ３４８において、決定された推定関数値がメモリユニット５に格納される。
【０１１４】
ステップ３４６〜３４８における、境界に位置する頂点にわたる反復は、任意の適切な終了基準に応じて終了され得、それはたとえば、タイル境界に位置するすべての頂点に対して、または少なくとも、最適ルート決定に関連し得るタイルの境界に位置するすべての頂点に対して、推定関数が知られた場合である。
【０１１５】
図８のフローチャートは模式的のみであり、そこに示されるステップのいくつかは並行して実行され得ることが、留意されるべきである。たとえば、好ましい実施形態において、ステップ３４５およびステップ３４６〜３４８における反復は実行され、その結果、すべての目的地タイル境界頂点を同時に入力として有する、ダイクストラのアルゴリズムまたはＡ＊−アルゴリズムが実行され、ルート検索の出発点に向けて検索が実行される。代替的に、ステップ３４３、３４５、および３４６〜３４８は、以下に図１１を参照して説明されるように、まずグラフを再定義することによって、次に再定義されたグラフ上でダイクストラのアルゴリズムまたはＡ＊−アルゴリズムを実行することによって、並行して実行され得る。
【０１１６】
図９を参照して次により詳細に説明されるように、タイル境界に位置するすべての関連する頂点に対して推定関数がひとたび知られると、ステップ３５において、タイルの内側に位置する頂点に対して推定関数が決定される。まず、ステップ３５１において、タイルＴｉが選択される。次に、ステップ３５２において、このタイルの境界に位置するすべての頂点が決定される。ステップ３５３〜３５６において、タイルの内側に位置するすべての頂点にわたる反復が実行される。まず、ステップ３５３において、タイル内側に位置する頂点が選択される。ステップ３５４において、このタイルの境界に位置する各頂点に対して、タイルの内側における選択された頂点とタイル境界に位置する頂点とを接続する最適ルートのコストに関する下限が決定される。図９において、この値は、たとえば選択されたタイル上でダイクストラのアルゴリズムを使用して得られた、これらの２つの頂点を接続する最適ルートに関連する正確なコストとして模式的に表されるが、上記に図４および５を参照して説明されたように、これらのコストの下限を入手する任意の他の適切な方法が使用され得る。次に、ステップ３５５において、タイル境界に位置する対応する頂点のための推定関数がプラスされたこれらのコストの最小値が決定され、タイル内側に位置する頂点のための推定関数が、この最小値に等しく設定される。ステップ３５６において、決定された推定関数値が格納される。ステップ３５３〜３５６が、タイル内側に位置するすべての頂点にわたって反復される。タイル内側に位置する頂点にわたる反復の終了後、ステップ３５７において新しいタイルＴｉが選択され、ステップ３５２〜３５６がタイリングのすべての関連するタイルにわたって反復される。
【０１１７】
図６に戻って、上述のように、道路網のすべての関連する頂点のための推定関数が、タイリングのタイルの抵抗値に基づいて決定されて、この推定関数を使用するＡ＊−アルゴリズムが実行され得る。再び、タイリングＴの定義、およびタイリングのタイルの抵抗値の提供は、Ａ＊−アルゴリズムにおいて使用される推定関数が容易にかつ確実に計算されることを可能にすることが、強調されるべきである。
【０１１８】
図６〜９を参照した上記の説明は、本発明による方法の一つの有利な実施形態を表すのみであり、種々の変更が考え得ることが理解される。ステップ３４４において、サブグラフのエッジに関連するコストは、タイルの抵抗値を、このタイルの境界に位置する一対の頂点のエアライン距離によって乗算することによって推定され得るが、サブグラフのエッジに関連するコストは、任意の他の適切な方法でも決定され得る。たとえば、頂点がタイル境界の対向するエッジに位置する場合には、一対の頂点を接続するエッジに関連するコストは、タイルの抵抗値とエッジの長さとの積によって近似され得る。さらにまた、推定関数を計算するために、タイルの一つのエッジに位置する複数の頂点が単一の頂点に縮約され得、したがって推定関数の計算の複雑さをさらに低減させる。
【０１１９】
上記の説明において、ステップ３４３、３４７、３５４、および３５５において、タイルの内側に位置する頂点とタイル境界に位置する頂点とを接続する最適ルートに関連する正確なコストが使用されているが、これらのコストの下限を提供する任意の他の適切な方法が使用され得る。たとえば、上記に図４および５を参照して説明されたように、頂点のエアライン距離、またはタイル境界からの頂点の距離が、これらのコストの下限を引き出すために使用され得る。
【０１２０】
図６において示される方法の別の変更が、次に図１０および１１を参照して説明される。この変更に応じて、図６のステップ３３は、図１０のステップ３３’によって置き換えられる。この変更の基礎をなす根本的な考えは、出発点から目的地までの最適ルートを決定するために、タイル内側に位置する頂点のための推定関数を必ずしも計算する必要はないということである。
【０１２１】
変更によれば、まず、ステップ３４において、タイル境界に位置する頂点に対して推定関数が決定される。このステップは、上記の図８を参照して説明されたように実行される。次に、ステップ３８において、出発点を含む出発タイルの内側に位置する頂点、および目的地を含む目的地タイルの内側に位置する頂点に対して、推定関数が決定される。目的地タイルに対しては、これは、たとえば、目的地から始まるダイクストラのアルゴリズムを使用して達成され得る。出発タイルに対しては、推定関数は、上記の図９を参照して説明されたように決定され得る。次に、ステップ３９において、最適ルート検索が実行されるべきグラフが、出発タイルおよび目的地タイルに位置するすべての頂点、ならびにタイル境界に位置するすべての頂点からなるように、再定義される。図３に示される道路網について、これは図１１において模式的に示される。一つのタイルの境界に位置する一対の頂点を接続する、変更されたグラフのこれらのエッジに関連するコストは、たとえば、このタイル上でダイクストラのアルゴリズムを実行し、境界に位置する一対の頂点を接続するルートに関連する最小コストを決定することによって、任意の適切な方法によって決定され得る。次に、変更されたグラフ上で最適ルート検索が実行される。タイルの頂点は、タイルの境界に位置する、より少ない数の頂点に縮約されるので、頂点は、決定された最適ルートをユーザに出力する前に抽出されなければならない。これは、たとえば、個々のタイルのダイクストラのアルゴリズムに基づいて、最適ルート検索によって再び達成され得る。
【０１２２】
図３および１１において、タイリングＴは、同一のサイズと形状とを有する複数のタイルからなるように示されるが、必ずしもそうである必要はない。
【０１２３】
実際には、次に図１２を参照して説明されるように、不均一なタイリングサイズを有するタイリングを選択することは有利であり得る。この目的のために、図１２Ａおよび１２Ｂにおいて示される２つの異なるタイリングＴ’とＴ’’とは、少なくとも道路網の一部分が含まれる地域をカバーするように定義される。タイリングＴ’’については、道路網が各道路セグメントの交差点とタイル境界とに頂点を有するように定義されるが、表示の明瞭さのためにこれらの頂点のすべてが表示されるわけではない、ということが留意されるべきである。
【０１２４】
タイリングＴ’およびＴ’’の両方について、上記に図２を参照して説明されたように、各タイルに対して抵抗値が計算される。タイリング定義データおよび関連する抵抗値は、両方のタイリングＴ’およびＴ’’について、第２の格納ユニット４に格納される。
【０１２５】
出発点および目的地が入力されて初めて、図１２Ｃに模式的に示されるタイリングＴは、より大きなタイルサイズを有するタイリングＴ’のタイルと、より小さなタイルサイズを有するタイリングＴ’’のタイルとの両方を含むように、定義される。より具体的には、出発点および目的地の近郊に対しては、より小さなタイルＴ１’’〜Ｔ６’’が選択され、一方、出発点および目的地の両方から距離のある地域に対しては、より大きなタイルＴ１’およびＴ２’が選択される。不均一なタイルサイズを有するこのタイリングの各タイルに対して、抵抗値は、個々のタイルサイズに対して決定された抵抗値に選択され、第２の格納ユニット４に格納される。上記に図６〜１０を参照して説明された、出発点から目的地までのルートを決定する種々の方法が、図１２Ｃに示される不均一なタイリングに対して容易に適用され得る。
【０１２６】
このような文脈において、図においては四角形のタイルが示されるが、任意の他の適切なタイルの形状が使用され得ることもまた理解されるべきである。さらに、すべてのタイルが同じ形状を有する必要はない。
【０１２７】
本発明によれば、ルートを決定する方法が実行されるときに、タイルの抵抗値に基づいて推定関数が決定されるので、本発明の方法は、次に図１３を参照して説明されるように、動的なルート決定に容易に適合し得る。動的なルート決定の方法は、一般的に４０において示される。まず、ステップ４１において、ＴＭＣ信号またはユーザ入力が受信され、そのことは、たとえば交通渋滞が原因で、またはユーザプリファランスが原因で、特定の道路セグメントが回避されることを示す。次に、ステップ４２において、ＴＭＣ信号またはユーザ入力によって影響された道路セグメントが特定される。その後で、ステップ４３において、影響された道路セグメントを含むすべてのタイルが特定される。ステップ４４において、影響された道路セグメントに関連するコストは、受信されたＴＭＣ信号またはユーザ入力に応じてアップデートされる。ステップ４５において、影響された道路セグメントを含むタイルの、一つのまたは複数の抵抗値がアップデートされる。次に、上記に図６〜１０を参照して説明されたように、影響された道路セグメントのアップデートされたコスト、および影響されたタイルのアップデートされた抵抗値の両方を考慮に入れて、ルート決定３０が実行される。特に、ステップ３３において、推定関数は、アップデートされた抵抗値に基づいて計算される。
【０１２８】
影響されたタイルの抵抗値のアップデートは、ステップ４５において、種々の異なる方法で実行され得る。たとえば、影響されたタイルに位置する道路セグメントに関連するコストが増加された場合には、影響されたタイルの抵抗値は、所定の定数によって乗算され得る。該定数は、受信されたユーザ入力またはＴＭＣ信号に依存し得る。多くのユーザ入力またはＴＭＣ信号は、所定のタイルに含まれるすべての道路セグメントが好ましく回避されるべきであるという結果になるようになっている。そのような場合において、これらの道路セグメントの一つずつに関連するコストが、倍数因子によって増加する場合には、これらの道路セグメントを含むタイルの抵抗値は、同じ因子によって乗算される。そのような場合においてもまた、正確な最適ルートが決定され得る。
【０１２９】
たとえ道路セグメントコストが変更されたとしても、タイルの抵抗値をアップデートする必要はないことが、留意されるべきである。むしろ、もともとの抵抗値に基づいて決定された推定関数は、それでも目的地へのコストを過小評価している。したがって、ステップ４５もまた省略され得る。
【０１３０】
代替的に、いくつかの抵抗値は単一のタイルに対して提供され得、それらの抵抗値は、いかなるユーザプリファランスまたはＴＭＣ信号も用いない所定のコストモデルについて、および一般的なＴＭＣ信号またはユーザプリファランスを考慮に入れたときのこの所定のモデルについて、それぞれ計算された抵抗値を反映する。たとえば、交通渋滞する傾向がある道路セグメントを含むタイルに対して、２つの抵抗値が計算され得、一つは道路セグメントがブロックされない場合についてであり、もう一つは道路セグメントがブロックされる場合についてである。次に、ステップ４１において受信されたＴＭＣ信号に応じて、ステップ４５においてこれらの抵抗値のうちのいずれか一つが選択される。
【０１３１】
しばしば、最適ルートは、異なるコストモデルの線形な組み合わせの形をなすコストモデルに対して決定される。たとえば、最短ルートおよび最速ルートの種々の重み付けされた組み合わせが使用され得る。ＸとＹとが異なるコストモデルを示し、α・Ｘ＋β・Ｙがそれらの線形な組み合わせを示す場合には、組み合わせられたコストモデルのタイルの抵抗値は、以下の関係を満たし：
【０１３２】
【数５】
ここで、Ｒ（Ｘ）およびＲ（Ｙ）は、それぞれコストモデルＸおよびＹに基づいた各タイルの抵抗値を示す。したがって、コストモデルの抵抗値の線形な組み合わせは、コストモデルの線形な組み合わせの抵抗値に関する下限を提供する。推定関数を決定するためには、コストの下限を提供することで十分であるので、コストモデルα・Ｘ＋β・Ｙのための推定関数は、基礎をなす根本的なコストモデルＸおよびＹの抵抗値のそれぞれの線形な組み合わせにより、組み合わせられたコストモデルの抵抗値を近似することによって得られ得る。
【０１３３】
したがって、本発明の実施形態において、タイリングの各タイルについて、異なる基礎コストモデルに対応する複数の抵抗値が格納される。基礎コストモデルの線形な組み合わせに対応するコストモデルに対してルート検索が実行される場合には、図６〜１０において示される方法において、最初のステップにおいて、タイルの抵抗値が、基礎コストモデルの線形な組み合わせとして決定される。一実施形態において、基礎コストモデルは、最短ルートおよび最速ルートを含む。
【０１３４】
抵抗値の局所的な性質のために、本方法および本システムは、部分的な地図アップデートに良好に適していることが理解される。より具体的には、既存の道路網が変更される場合、または道路網がその外側の追加の道路セグメントによって補われる場合、たとえば、道路網の新しい部分がデジタル化される場合には、道路網が実際に変更されたこれらのタイルの抵抗値だけがアップデートされる必要がある。
【０１３５】
図１４は、北部と中部ドイツとの地図部分を示し、その中でタイルの抵抗値はグレースケール表示で示される。タイルは、形状において四角形であるように選択され、８キロメートルのエッジ長さを有する。抵抗値は、最速ルートのコストモデルに対して計算される。理解され得るように、ドイツの道路網の幹線道路は、抵抗値において明瞭に検出され得る。
【０１３６】
図１５は、グレースケール表示における、北部ドイツから南部ドイツまでの最適ルート検索における検索された地域を示し、この場合も８キロメートルのエッジの長さを有する四角形のタイリングを使用している。図１５Ａは本発明に応じた最適ルート決定における検索された地域を示し、一方、図１５Ｂは従来の方法に応じた最適ルート決定における検索された地域を示す。より具体的には、図１５Ａにおいては、タイル抵抗値に基づいて推定関数が決定され、一方、図１５Ｂにおいては、エアライン距離に基づいた従来の推定関数が使用されている。最適ルートは、Ａ＊−アルゴリズムを使用して決定される。エッジ緩和を介して調査されたタイルは、種々のグレースケールで示され、異なる色は出発点からの発生した移動時間を表す。明らかに理解され得るように、調査される必要のあるタイルの数は、従来の方法におけるよりも（図１５Ｂ）、本発明による方法においてはるかに小さい（図１５Ａ）。このことは、結果として最適ルート検索のためのより短い実行時間になる。
【０１３７】
本発明の種々の実施形態による方法は、最適ルート検索において道路セグメントの部分集合のみが検索される任意の方法と容易に相互併用され得る。そのような方法の例は、たとえば、ＥＰ １ ０２７ ５７８において、またはＷＯ ０３／０７９１５５において、または欧州特許出願第０５ ０２４ ４１４号において開示されるか、あるいはＦＲＣに基づいた発見的方法である。これらの方法は、道路網をＡ＊−アルゴリズムにおいて検索されるようにしかるべく制限することによって、本発明による方法と一体化され得る。
【０１３８】
要約すれば、本発明によれば、推定関数を使用する、ルートを決定する方法およびシステムが提供され、道路網の頂点のための推定関数の値は、タイリングに基づいて、かつタイリングのタイルの抵抗値に基づいて、決定される。好ましい実施形態の上記の説明から明らかなように、本発明によれば、正確な推定関数が決定され得、部分的な地図アップデートが容易に実行され得、かつ動的なルート決定が容易に実行され得る。本発明は、任意の最適ルート検索において、特に、道路網の最適ルートの決定において、有利に使用され得る。
【図面の簡単な説明】
【０１３９】
本発明の追加の特徴および利点は、添付の図面を参照して、好ましいまたは有利な実施形態の詳細な説明から、より容易に理解される。
【図１】図１は、本発明の実施形態によるルートを決定するシステムの模式的なブロック図を示す。
【図２】図２Ａは、道路網の一部分を示し、本発明の実施形態による抵抗値の決定を図示する役目を果たす。図２Ｂは、道路網の一部分を示し、本発明の実施形態による抵抗値の決定を図示する役目を果たす。
【図３】図３は、道路網および対応するタイリングを示し、本発明の実施形態によるタイル境界に位置する頂点のための推定関数を決定する方法を図示する役目を果たす。
【図４】図４は、図３の道路網の一部分を示し、本発明の実施形態によるタイルの内側頂点のための推定関数を決定する方法を図示する役目を果たす。
【図５】図５は、図３の道路網の一部分を示し、本発明の実施形態によるタイルの内側頂点のための推定関数を決定する方法を図示する役目を果たす。
【図６】図６は、本発明の実施形態によるルートを決定する方法を表すフローチャートを示す。
【図７】図７は、図６によって表される方法のサブルーチンを表すフローチャートを示す。
【図８】図８は、図６によって表される方法のさらに別のサブルーチンを表すフローチャートを示す。
【図９】図９は、図６によって表される方法のさらなる別のサブルーチンを表すフローチャートを示す。
【図１０】図１０は、本発明の代替的な実施形態による、図６によって表される方法のサブルーチンを表すフローチャートを示す。
【図１１】図１１は、図３の道路網とタイリングとを示し、図１０によって表される代替的な実施形態による方法を図示する役目を果たす。
【図１２Ａ】図１２Ａは、図３の道路網と、異なるタイリングとを示し、本発明による方法のさらに別の実施形態を図示する役目を果たす。
【図１２Ｂ】図１２Ｂは、図３の道路網と、異なるタイリングとを示し、本発明による方法のさらに別の実施形態を図示する役目を果たす。
【図１２Ｃ】図１２Ｃは、図３の道路網と、異なるタイリングとを示し、本発明による方法のさらに別の実施形態を図示する役目を果たす。
【図１３】図１３は、動的なルート決定の方法を表すフローチャートを示し、図６によって表されるルート決定の方法を使用する。
【図１４】図１４は、地図の一部分を示し、抵抗値はグレースケールで示される。
【図１５Ａ】図１５Ａは、本発明の実施形態による方法に従って実行された最適ルート決定の間に検索された地域を示す。
【図１５Ｂ】図１５Ｂは、一方、従来の方法に応じて実行された同じ最適ルート決定における、検索された地域を示す。
【符号の説明】
【０１４０】
１ ナビゲーションシステム
２ 処理ユニット
３ 第１の格納ユニット
４ 第２の格納ユニット
４ａ タイリング定義データ
４ｂ タイリング定義データ
４ｃ タイリング定義データ
５ メモリユニット
６ 入力手段
７ 出力手段
８ 位置決定手段
９ ＴＭＣ受信機
【技術分野】
【０００１】
本発明は、最適ルート決定に関し、特に、推定関数に基づいて道路網における最適ルートを決定する方法およびシステムに関する。本発明の方法およびシステムは、たとえば自動車に搭載されたナビゲーションシステムにおいて、任意の最適ルート検索のため、特に道路網における最適ルートを検索するために有利に使用され得る。
【背景技術】
【０００２】
所定の出発点から所定の目的地までの最適ルートを見出すことは、最適ルート情報を提供する自動車ナビゲーションシステムまたは他のシステムの主要な特徴の一つである。
【０００３】
最適ルートを見出すいくつかの標準的なアルゴリズムが当該技術分野において公知であり、なかでも最も有名なものは、ダイクストラのアルゴリズム（Ｄｉｊｋｓｔｒａ‘ｓ ａｌｇｏｒｉｔｈｍ）およびＡ＊−アルゴリズムである。本明細書の全体にわたって、「最適ルート」という用語は、最小コストのルートについて使用され、ルートのコストは、該ルートを移動するときに横断される道路セグメントのコストの合計と、交差点または道路セグメント頂点に関連するコストの合計とによって決定される。ナビゲーションシステムにおいて、いくつかの異なるコストモデルがしばしば使用され、たとえば、道路セグメントのコストが道路セグメントの長さによって与えられる最短ルートモデル、または道路セグメントのコストが、道路セグメントにおける特徴的な移動速度によって分割される道路セグメントの長さによって与えられる、最速ルートモデルである。さらに、コストモデルは、幹線道路を回避すること、トンネルを回避すること、またはフェリー接続を回避することなどのユーザプリファランスをしばしば考慮に入れる。
【０００４】
ダイクストラのアルゴリズムにおいては、道路網、すなわちより一般的にグラフは、エッジ緩和（ｅｄｇｅ ｒｅｌａｘａｔｉｏｎ）によってルートの出発点から出発して探索され、道路網の異なる頂点は、頂点と出発点とを接続するルートに関連する最小コストの順に訪問される。目的地が伸ばされるときに、出発点から目的地までの最適ルートが見出され、ダイクストラのアルゴリズムは終了する。
【０００５】
Ａ＊−アルゴリズムは、ダイクストラのアルゴリズムの修正であり、道路網のすべての頂点のための推定関数を使用する。所定の頂点のための推定関数は、所定の頂点と目的地とを接続する最適ルートに関連するコストに対して推定を提供する。ルート検索において、異なる経路が優先度に応じて分類され、該優先度は、出発点から頂点までにそれまで発生したコストの合計と、頂点の推定関数とによって与えられる。推定関数が、頂点と目的地とを接続する最適ルートのコストを決して過大評価しないようになっている場合には、Ａ＊−アルゴリズムは、最適ルート問題に対する正しい解決策を見出すことが知られている。
【０００６】
道路網における最適ルート検索については、発見的推定がしばしば使用され、該発見的推定は、最短ルート検索における頂点と目的地とのエアライン距離と、最速検索における特徴的な移動速度によって分割されるエアライン距離とに基づいて決定される。一般的に、推定関数が優れているほど、最適ルートの決定のために訪問されなければならない道路セグメント頂点の数は小さくなり、アルゴリズム実行時間が短くなる。
【０００７】
しかし、エアライン距離に基づく推定関数は、しばしば不正確である。さらに、車両に搭載されたナビゲーションシステムにおいては、メモリと実行時間との制約が対処される必要がある。後者の制約のために、ダイクストラのアルゴリズムおよびＡ＊−アルゴリズムを、ヨーロッパの田舎またはアメリカ合衆国の道路網などの道路網に直接的に適用することは、これらの道路網における道路セグメントおよび道路セグメント頂点が多数であるために、しばしば実行可能ではない。これらの理由のために、ダイクストラのアルゴリズムまたはＡ＊−アルゴリズムは、たとえば、異なる道路セグメントの異なるレイヤへの分類を提供することによって、または道路網幾何学を特徴づける追加情報を提供することによって、ナビゲーションシステムにおける使用のためにしばしば変更され、これはオフラインで決定され、ナビゲーションシステムにおける最適ルート検索を容易にする。
【０００８】
このような文脈において、特許文献１は、最小コストのルート指定（ｒｏｕｔｉｎｇ）システムを開示しており、そこでは長距離移動のための道路セグメントの関連性を定量化するリーチメトリック（ｒｅａｃｈ ｍｅｔｒｉｃ）が提供される。このリーチメトリックは、地図の幾何学のみに基づくという利点を有する。しかし、リーチメトリックは、所定の道路セグメントの範囲が、遠くの異なる道路セグメントに関連するコストに強く依存し得るという意味で非常に非局所的であるという不都合がある。たとえば、道路セグメントのコスト要因の増加は、たとえ異なる道路セグメントが遠くても、異なる道路セグメントの範囲の増加または減少を引き起こし得る。したがって、特許文献１に開示される方法およびシステムは、部分的な地図アップデートおよび動的なルート決定にうまく適合しない。
【０００９】
したがって、当該技術分野において、最適ルートを決定する改善された方法およびシステムに対するニーズが存在する。より具体的には、最適ルートを決定するシステムおよび方法であって、部分的な地図アップデートが容易に実行されることを可能にする、動的なルート決定に適した、最適ルートが確実に決定されることを可能にする方法およびシステムのニーズが、当該技術分野において存在する。
【特許文献１】国際公開第０３／０７９１５５号パンフレット
【発明の開示】
【課題を解決するための手段】
【００１０】
本発明によれば、このニーズは、請求項１に係る、道路網のルートを決定する方法と、請求項２４に係る、道路網データを前処理する方法と、請求項２７に係る、ルートを決定するシステムとによって、対処される。従属請求項は、本発明の好ましいまたは有利な実施形態を定義する。
【００１１】
本発明の局面によれば、道路網の出発点から目的地までのルートを決定する方法が提供され、該方法は複数の頂点のための推定関数を使用し、該推定関数は道路網の頂点と目的地とを接続する任意のルートに関連するコストの下限を提供する。該方法は、道路網の少なくとも一部分が含まれる地域をカバーするタイリングを定義するステップと、該タイリングの各タイルの抵抗値を提供するステップと、該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点に対して推定関数値を決定するステップとを包含する。該抵抗値は、所定のタイルについて、抵抗値が、該所定のタイルの抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する道路網の頂点を接続するルートに関連するコストを表すように、定義される数値である。いくつかの利点は、地図をタイルに細分すること（ｓｕｂｄｉｖｉｄｉｎｇ）に関連し、各タイルの抵抗値の提供に関連する。第一に、推定関数は、たとえばナビゲーションシステムにおける該方法の実行時に、該抵抗値から確実にかつ容易に計算され得る。さらに、抵抗値は、タイルのみに位置する道路網の一部分によって決定される局所的なパラメータであるので、影響されたタイルの抵抗値を対応してアップデートすることによって、部分的な地図アップデートが容易に実行され得る。さらに、動的なルート決定が容易に実行され得る。さらにまた、抵抗値は一般的に単一の数値のみであるので、抵抗値を格納するために格納容量がほとんど必要とされない。
【００１２】
好ましくは、抵抗値は、所定のタイルに対して、抵抗値が、一対の頂点のエアライン距離に関連して、所定のタイルの境界に位置する一対の頂点を接続する最適ルートに関連するコストの下限であるように、定義され、ルートは所定のタイルを横断する。さらに好ましくは、抵抗値は、所定のタイルに対して、抵抗値が、一対の頂点のエアライン距離によって分割される所定のタイルの境界に位置する任意の一対の頂点を接続する最適ルートに関連するコストの最小値または下限であるように、定義される。次に、所定のタイルの境界に位置する任意の一対のテスト頂点に対して、所定のタイルの抵抗値とテスト一対の頂点のエアライン距離との積が、タイル内のテスト一対の頂点を接続する最適ルートに関連するコストの下限を提供する。したがって、抵抗値は、道路網の幾何学のみの特性と組み合わせられるときに、タイルを横断する任意のルートに関連するコストの下限を確立することを可能にする。これらの下限は、道路網の頂点のための推定関数を計算するために有利に使用され得る。
【００１３】
好ましくは、タイル境界頂点のための推定関数値を決定するステップは、目的地を含む目的地タイルを決定するステップと、目的地タイルの境界に位置する目的地タイル境界頂点と推定関数が計算されるべきタイル境界頂点とを接続する最適ルートに関連するコストの第１の下限を決定するステップとを包含する。特に、第１の下限は、タイルの抵抗値に応じて、またはタイリングの複数のタイルの抵抗値に応じて、決定され得る。より具体的には、第１の下限は、境界のみに位置する頂点を含む道路網のサブグラフに対して、ダイクストラのアルゴリズムを使用して決定され得、任意のタイルの境界に位置する第１および第２の頂点を接続するサブグラフのエッジに関連するコストは、任意のタイルの抵抗値と、第１および第２の頂点のエアライン距離とから決定される。特に、サブグラフのエッジに関連するコストは、第１および第２の頂点のエアライン距離が乗算された任意のタイルの抵抗値に等しく設定され得る。このようにして、目的地タイルの境界に位置する各頂点に対して、この目的地タイル境界頂点と推定関数が計算されるべきタイル境界頂点とを接続する最適ルートの下限が計算され得る。重要なことには、関連する最適ルート検索は、もともとの道路網に対応するグラフ上で実行される必要はなく、タイル境界のみに位置する頂点からなるサブグラフ上でのみ実行され、このようにこのステップの計算の複雑さを非常に低減する。好ましい実施形態において、下限は別々のアルゴリズムにおいて各目的地タイルに対して確立されるのではなく、すべての目的地タイル境界頂点が、出発点として同時にダイクストラのアルゴリズムに供給される。すべての目的地タイル境界頂点に対して、目的地タイル境界頂点とタイル境界頂点とを接続する最適ルートに関連するコストの下限が確立される場合には、この下限は、タイル境界頂点と目的地とを接続する最適ルートに関連するコストの下限をも提供し、したがってタイル境界頂点のための推定関数として使用され得る。
【００１４】
しかし、推定関数の正確性がさらに増大され得る。このために、タイル境界頂点のための推定関数を決定するステップは、好ましくは、目的地と目的地タイル境界頂点とを接続する最適ルートに関連するコストの第２の下限を決定するステップと、第１の下限および第２の下限を加算するステップとをさらに包含する。すべての目的地タイル境界頂点にわたって第１の下限と第２の下限とのこの合計の最小値を決定することによって、タイル境界頂点のための改善された推定関数値が得られる。
【００１５】
特に好ましい実施形態において、目的地からの目的地タイル境界頂点の一つずつへの最適ルートのコストを決定するために、目的地から開始して目的地タイルのみにおいてまずダイクストラのアルゴリズムを実行することによって、タイル境界頂点のための推定関数値が決定され、次に、該コストは、タイル境界のみに位置する頂点からなるサブグラフ上で実行されるさらなるダイクストラのアルゴリズムの中に入力され、サブグラフのエッジに関連するコストは、再び、上述のように、タイル抵抗値と頂点エアライン距離とに基づいて決定される。
【００１６】
別の好ましい実施形態において、タイル境界頂点のための推定関数値は、目的地タイルに位置する道路セグメントと、目的地タイル以外のタイルについて、境界のみに位置する頂点とを含む再定義されたグラフ上で、目的地から出発して、ダイクストラのアルゴリズムを実行することによって決定され、任意のタイルの境界に位置する２つの頂点を接続するエッジに関連するコストは、任意のタイルの抵抗値と頂点のエアライン距離とに基づいて決定される。
【００１７】
好ましくは、推定関数値は、上述の方法を使用して、道路網の各タイル境界頂点に対して決定される。代替的には、タイル境界頂点のための推定関数値の決定は、任意の適切な終了基準に応じて終了され得る。タイル境界に位置するすべての頂点に対して、この情報に基づいて推定関数値がひとたび決定されると、タイルの内側に位置する頂点のための推定関数値もまた容易に確立され得る。本発明の一実施形態において、該方法は、タイルの境界に位置するタイル境界頂点のための推定関数値と、内側頂点とタイル境界頂点とを接続する最適ルートに関連するコストの下限とから、タイルの内側に位置する内側頂点のための推定関数を決定するステップを包含する。後者の下限は、たとえばダイクストラのアルゴリズムを使用して決定され得る。代替的には、たとえば内側頂点とタイル境界頂点とのエアライン距離に基づいて、またはタイル境界頂点が位置するタイルのエッジからの内側頂点の最小エアライン距離に基づいて、より単純な推定が使用され得る。このようにして、正確な推定関数値が、タイルの内側に位置する各頂点に対して容易に決定され得る。道路網のすべての頂点について、または少なくともルート決定に関連するタイルに位置するすべての頂点について、推定関数値が知られる場合には、最適ルートを決定するために標準的なＡ＊−アルゴリズムが次に実行され得る。
【００１８】
道路セグメントのコストが増加する場合には、道路セグメントを含むタイルの抵抗値は一定であるかまたは増加もする、という意味において、上述のように定義される抵抗値は、対応するタイルに位置する道路セグメントに関連するコストの単調な関数であるので、本発明に係る方法は、動的なルート決定に容易に適合させられ得る。このために、該方法は、道路網の道路セグメントのコスト要因における増加を検出するステップと、コスト要因における検出された増加に応じて道路セグメントを含むタイルの抵抗値を増加させるステップとを包含する。特に、抵抗値は倍数的に増加させられ得る。代替的には、抵抗値は、道路セグメントのコストが増加させられたときでさえも、変更されないままにしておかれ得る。コスト要因が変化する道路セグメントを含むタイルの抵抗値を増加させることは、道路網の頂点のための推定関数を決定する前に実行される。道路セグメントのコストは、たとえば、トンネルを回避すること、フェリー接続や有料道路を回避すること、幹線道路を回避することなどの、ユーザプリファレンスを指定するユーザ入力に応じて、種々の方法で増加され得る。代替的または追加的に、交通メッセージが受信され得、道路セグメントのコストまたは道路セグメントが、受信された交通メッセージ信号に応じて増加され得る。たとえば、特定の道路セグメントについて交通渋滞が発表される場合、この道路セグメントのコストは、回避関数を実行するなどのように増加され得る。
【００１９】
本発明の一実施形態において、タイリングのタイルのタイルサイズは一定である。しかし、別の実施形態においては、タイリングは、出発点および目的地からの距離が増加するにつれてタイルのサイズが増加するように、定義される。この場合には、第１の規則的なタイリングの各タイルに対して第１の抵抗値が提供され、第２の規則的なタイリングの各タイルに対して第２の抵抗値が提供され、道路網の一部分を含む地域をカバーするタイリングは、第１の規則的なタイリングのタイルと、第２の規則的なタイリングのタイルとの両方を含み、タイリングのタイルの抵抗値は、第１および第２の抵抗値にそれぞれ対応するように選択される。タイリングのタイルのタイルサイズを適切に選択することによって、該方法はより一層効果的になされ得る。好ましい実施形態において、すべてのタイルは四角形の形状を有するが、本発明はこれに限定されない。むしろ、タイリングのタイルは、任意の形状を有するように定義され得、タイリングのすべてのタイルが同一の形状を有するに必要はない。
【００２０】
上記において、本発明による方法は、タイリングの各タイルに対して一つのみの抵抗値が提供されるように説明されたが、単一のタイルに対して複数の抵抗値も提供され得る。特に、タイリングの各タイルに対して、第１の基礎抵抗値および第２の基礎抵抗値が提供され、それぞれ、第１および第２の基礎コストモデルを表す。次に、第１および第２の基礎コストモデルの線形な組み合わせとして形成されたコストモデルに対して、第１および第２の基礎抵抗値の線形な組み合わせによって、抵抗値の下限が決定される。たとえば、第１および第２の基礎コストモデルは、最短ルートおよび最速ルートであり得る。多数の異なるコストモデルに対して抵抗値を提供するのではなくて、基礎をなす基礎コストモデルの抵抗値から、組み合わせられたコストモデルのタイル抵抗値を決定することが可能なので、より少数の基礎コストモデルのみに対して抵抗値を提供することで十分である。
【００２１】
別の実施形態において、各タイルに対して複数の抵抗値が提供され、所定のタイルについて、複数の抵抗値の一つずつが、たとえば、上方のエッジから下方のエッジまで、左のエッジから右のエッジまで、および、おそらく、追加のエッジの組み合わせなどの、特定の方向において、所定のタイルを横断する最適ルートに関連するコストを特徴づける。タイリングの各タイルの複数の抵抗値に基づいて決定された推定関数は、一般的により一層正確である。
【００２２】
上述の本発明の実施形態のいずれか一つについて記述されたように決定された推定関数に基づいて、本発明による方法において、出発点から目的地までの最適ルート検索が実行される。アルゴリズムは、推定関数を使用する任意のアルゴリズムであり得るが、好ましくはＡ＊−アルゴリズムである。
【００２３】
本発明は上述の道路網について説明されたが、本発明は等しい機能を有する任意のグラフに対して適用され得る。
【００２４】
本発明の別の局面によれば、道路網データを前処理する方法が提供され、該方法は、道路網の少なくとも一部分が含まれる地域をカバーするタイリングを定義するステップと、タイリングのタイルに対して、タイルの境界に位置する頂点を決定するステップと、一対の頂点のエアライン距離によって分割されるタイルの境界に位置する任意の一対の頂点を接続する最適ルートに関連するコストの下限を決定するステップと、決定された下限を出力するステップとを包含する。特に、下限は、一対の頂点のエアライン距離によって分割されるタイルの境界に位置する任意の一対の頂点を接続するルートに関連するコストの最小値に等しく設定され得る。このようにして決定された下限は、抵抗値を提供し、該抵抗値は、本発明に応じて最適ルートを決定する方法において使用され得る。
【００２５】
本発明の別の局面によれば、道路網における出発点から目的地までのルートを決定するシステムが提供され、該システムは、道路網の複数の頂点のための推定関数を使用し、該推定関数は、道路網の頂点と目的地とを接続するルートに関連するコストの下限を提供し、該システムは、道路網データを含む第１の格納ユニットと、各タイルについてのタイリングと抵抗値とを定義するタイリング定義データを含む第２の格納ユニットと、タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点のための推定関数値を決定する処理ユニットとを備える。再び、第２の格納ユニットに含まれる所定のタイルの抵抗値は、所定のタイルの境界に位置する頂点を接続するルートに関連するコストの下限が、所定のタイルの抵抗値から処理ユニットによって導出され得るように、所定のタイルの境界に位置する道路網の頂点を接続するルートに関連するコストを表す。この構成を有するシステムは、本発明に応じてルートを決定する方法を実行し、したがってそれに関連する利点を利用するように適合される。
【００２６】
特に、該システムにおいて、処理ユニットは、目的地を含む目的地タイルの境界に位置する目的地タイル頂点を決定し得、タイル境界頂点と目的地タイル境界頂点とを接続する最適ルートに関連するコストの下限を計算し得、該下限はタイリングのタイルの抵抗値に応じて決定される。特に、処理ユニットは、下限を決定するために、目的地タイル境界頂点または同時に原点としてのすべての目的地タイル頂点を有する、ダイクストラのアルゴリズムを使用するように適合され得る。上記に詳細に説明されたように、このようにして、推定関数は、タイル境界頂点に対して容易に決定され得る。ダイクストラのアルゴリズムを使用するのではなく、推定関数はまた、目的地タイル境界頂点から出発してＡ＊−アルゴリズムを使用して、かつエアライン距離によって実行されるべきルート検索の出発点に対するコストを推定して、決定され得る。推定関数がすべての関連するタイルに対して決定されることを確実にするために、出発点が拡大された後でさえも、所定の時間にわたってＡ＊−アルゴリズムが計算される。推定関数値が後の段階において必要とされる場合には、最適ルート検索の間に、これらはオンデマンドで計算され得る。好ましい実施形態において、該システムは、タイル頂点の座標と処理ユニットによって決定される関連する推定関数値とを格納する、メモリユニットをさらに備える。有利な実施形態において、タイル境界頂点の座標は、対応するタイルの境界によって規定される線に沿ったタイル境界頂点の位置を指定する一次元座標の形で格納され得る。
【００２７】
さらに、処理ユニットは、道路網の道路セグメントについての交通メッセージ信号を受信し得、受信された交通メッセージ信号に応じて、道路セグメントを含むタイルの抵抗値を変更し得る。代替的には、それぞれのタイルの抵抗値は、変更されずに留まり得る。
【００２８】
該システムは、タイリングのタイルの抵抗値に応じて決定され、メモリユニットに格納された推定関数値を使用するＡ＊−アルゴリズムを使用して、出発点から目的地までの最適ルートを、さらに好ましくは決定する。
【００２９】
本発明に応じてルートを決定する該システムにおいて、第１および第２の格納ユニットは、単一のフィジカルデバイスであり得るか、または別のデバイスであり得る。たとえば、第１および第２の格納ユニットは、ＣＤ、ＤＶＤ、メモリカード、またはナビゲーションシステムの内蔵ハードディスクであり得る。
【００３０】
本発明の別の局面にれば、ナビゲーションシステムが提供され、該ナビゲーションシステムは、目的地を入力する入力手段と、決定されたルートを出力する出力手段と、本発明のいずれか一つの局面または実施形態に応じてルートを決定するシステムとを備え、該システムは、そこから目的地を受信する入力手段と、そこへ決定されたルートを出力する出力手段とに結合される。該ナビゲーションシステムは、現在の車両位置を決定する位置決定手段などの、ナビゲーションシステムにおいて通例使用される任意の構成要素をさらに備え得、ナビゲーションシステムは、たとえば、ＧＰＳ受信機、ルート決定のために出発点として現在の車両位置を提供するためのルートを決定する、システムに結合された位置決定手段、または交通メッセージ信号をそこへ提供するために処理ユニットに結合されたＴＭＣ受信機を備え得る。
【００３１】
再び、「道路網」という用語は、本発明を説明するためにこの書類の全体を通して使用されるが、本発明の適用は、物理的な道路網に限定されないことが留意されるべきである。むしろ、本発明は、最適ルート検索が重要であり得る任意のネットワークに適用され得る。例は、フェリー接続、コンピュータネットワークにけるデータ接続、または送電線を含む。
【００３２】
さらに、本発明は、複数のタイルが定義される面において定義される道路網に関連して説明されるが、本発明は面において定義されるグラフに限定されないことが留意されるべきである。むしろ、本発明の原理は、より高次元のオブジェクト、たとえば３次元グラフについて等しく適用可能である。
【００３３】
本発明の適用の主な分野は、道路網における、特に車両に搭載されたナビゲーションシステムにおける、最適ルートの決定である。
【００３４】
本発明は、さらに、以下の手段を提供する。
【００３５】
（項目１）
道路網の出発点から目的地までのルートを決定する方法であって、
該方法は、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
該道路網の少なくとも一部分が含まれる地域をカバーするタイリング（Ｔ）を定義するステップと、
該タイリングの各タイルの抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数値を決定するステップと
を包含し、
所定のタイルの抵抗値は、該所定のタイルの境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表す、
方法。
【００３６】
（項目２）
上記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルにおける上記道路網の幾何学的特性に関連して、該所定のタイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を接続するルート（１１、１３）に関連するコストを表す、ことを特徴とする、項目１に記載の方法。
【００３７】
（項目３）
上記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルの境界に位置する一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する上記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、項目１または２に記載の方法。
【００３８】
（項目４）
上記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連するコストの最小値である、ことを特徴とする、項目３に記載の方法。
【００３９】
（項目５）
上記タイル境界頂点（２３）に対して上記推定関数値を決定するステップが、
上記目的地（２２）を含む目的地タイル（Ｔ３）を決定するステップと、
該目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）と、該タイル境界頂点（２３）と、を接続する最適ルートに関連するコストの第１の下限を決定するステップと
をさらに包含する、ことを特徴とする、項目１ないし４のいずれか１項に記載の方法。
【００４０】
（項目６）
上記第１の下限が、上記タイルの上記抵抗値に応じて、または上記タイリングの複数のタイルの上記抵抗値に応じて、決定される、ことを特徴とする、項目５に記載の方法。
【００４１】
（項目７）
上記第１の下限が、タイル境界のみに位置する頂点（２３〜２５）を含む上記道路網のサブグラフに対して、ダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、項目６に記載の方法。
【００４２】
（項目８）
任意のタイル（Ｔ２）の境界に位置する第１および第２の頂点（２３、２４）を接続するサブグラフのエッジ（２６ａ）に関連するコストが、該任意のタイルの抵抗値と、該第１および第２の頂点（２３、２４）のエアライン距離とから決定される、ことを特徴とする、項目７に記載の方法。
【００４３】
（項目９）
上記サブグラフのエッジ（２６ａ）に関連する上記コストが、上記第１および第２の頂点（２３、２４）のエアライン距離が乗算された上記任意のタイル（Ｔ２）の抵抗値に等しく設定される、ことを特徴とする、項目８に記載の方法。
【００４４】
（項目１０）
上記タイル境界頂点（２３）に対して上記推定関数を決定する上記ステップが、
上記目的地（２２）と、上記少なくとも一つの目的地タイル境界頂点（２４、２５）と、を接続する最適ルートに関連するコストの第２の下限を決定するステップと、
上記第１の下限と上記第２の下限とを加算するステップと
をさらに含む、ことを特徴とする、項目５ないし９のいずれか１項に記載の方法。
【００４５】
（項目１１）
上記タイル境界頂点（２３）に対して上記推定関数値を決定する上記ステップが、
すべての目的地タイル境界頂点（２４、２５）にわたる上記第１の下限と上記第２の下限との合計の最小値を決定するステップをさらに含む、ことを特徴とする、項目１０に記載の方法。
【００４６】
（項目１２）
上記タイル（Ｔ２）の上記境界に位置するタイル境界頂点（２３、２４）のための推定関数値からの該タイル（Ｔ２）の内側に位置する内側頂点（２９）のための推定関数値と、該内側頂点（２９）と該タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの下限と、を決定する、ステップによって特徴付けられる、項目１ないし１１のいずれか１項に記載の方法。
【００４７】
（項目１３）
上記内側頂点（２９）と上記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの上記下限が、該内側頂点（２９）と該タイル境界頂点（２３、２４）とのエアライン距離から決定される、ことを特徴とする、項目１２に記載の方法。
【００４８】
（項目１４）
上記内側頂点（２９）と上記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの上記下限が、該タイル境界頂点（２３、２４）が位置する上記タイルのエッジからの上記内側頂点の最小エアライン距離（２７’、２８’）から決定される、ことを特徴とする、項目１２に記載の方法。
【００４９】
（項目１５）
上記道路網の道路セグメントのコスト要因における増加を検出するステップと、
該コスト要因における検出された増加に応じて、該道路セグメントを含むタイルの抵抗値を増加させる、ステップとによって特徴づけられる、項目１ないし１４のいずれか１項に記載の方法。
【００５０】
（項目１６）
上記道路セグメントを含む上記タイルの抵抗値を増加させることが、乗法による、ことを特徴とする、項目１５に記載の方法。
【００５１】
（項目１７）
上記道路セグメントの上記コスト要因が、ユーザ入力に依存して増加する、ことを特徴とする、項目１５または１６に記載の方法。
【００５２】
（項目１８）
交通メッセージ信号を自動的に受信し、上記道路セグメントの上記コスト要因が該受信された交通メッセージ信号に依存して増加する、ステップによって特徴づけられる、項目１５ないし１７のいずれか１項に記載の方法。
【００５３】
（項目１９）
上記タイリング（Ｔ）のタイル（Ｔ１’、Ｔ２’、Ｔ１’’〜Ｔ６’’）のタイルサイズが、上記出発点と上記目的地からの増加する距離とともに増加する、ことを特徴とする、項目１ないし１８のいずれか１項に記載の方法。
【００５４】
（項目２０）
第１の抵抗値が、第１の規則的なタイリング（Ｔ’）の各タイルに対して提供され、
第２の抵抗値が、第２の規則的なタイリング（Ｔ’’）の各タイルに対して提供され、
上記地域をカバーする上記タイリング（Ｔ）が、該第１の規則的なタイリング（Ｔ’）のタイル（Ｔ１’、Ｔ２’）と、第２の規則的なタイリング（Ｔ’’）のタイル（Ｔ１’’〜Ｔ６’’）とを含み、該タイリングのタイルの抵抗値が、対応する該第１および該第２の抵抗値とそれぞれ等しい、ことを特徴とする、項目１９に記載の方法。
【００５５】
（項目２１）
上記タイリング（Ｔ）の各タイルに対して、第１の基礎抵抗値および第２の基礎抵抗値が提供され、これらの抵抗値が第１および第２の基礎コストモデルをそれぞれ表し、該第１および第２の基礎コストモデルの線形な組み合わせとして形成されるコストモデルに対して、該抵抗値の下限が、該第１および第２の基礎抵抗値の線形な組み合わせによって決定される、ことを特徴とする、項目１ないし２０のいずれか１項に記載の方法。
【００５６】
（項目２２）
上記出発点から上記目的地までの最適ルートが、上記タイリングのタイルの抵抗値に応じて決定される推定関数を使用するＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、項目１ないし２１のいずれか１項に記載の方法。
【００５７】
（項目２３）
グラフ上の目的地へのルートを決定する方法であって、
該方法は、該グラフの複数の頂点のための推定関数を使用し、
該推定関数は、該グラフの頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該グラフの少なくとも一部分が含まれる、ステップと、
該タイリングの各タイルに対して抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数を決定するステップと
を含み、
所定のタイルの抵抗値は、該所定のタイルの該境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値に基づいて導出可能であるように、該所定のタイルの境界に位置する該グラフの頂点を接続するルートに関連するコストを表す、方法。
【００５８】
（項目２４）
道路網データを前処理する方法であって、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該道路網の少なくとも一部分が含まれる、ステップと、
該タイリングのタイル（Ｔ０）に対して、該タイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を決定するステップと、
任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離によって分割される該タイルの境界に位置する該一対の頂点を接続する最適ルート（１１、１３）に関連するコストの下限を決定するステップと、
該決定された下限を出力するステップと
を含む、方法。
【００５９】
（項目２５）
上記下限が、任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）の上記エアライン距離によって分割される上記タイルの境界に位置する該一対の頂点を接続するルートに関連する上記コストの最小値から決定される、ことを特徴とする、項目２４に記載の方法。
【００６０】
（項目２６）
上記下限が、出力の前に離散化される、ことを特徴とする、項目２４または２５に記載の方法。
【００６１】
（項目２７）
道路網の出発点から目的地までのルートを決定するシステムであって、
該システムは、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該システムは、
道路網データを含む第１の格納ユニット（３）と、
タイリングを定義するタイリング定義データと、各タイルの抵抗値と、を含む第２の格納ユニット（４）と、
該タイリングの該タイルの該抵抗値に応じて、タイル境界に位置するタイル境界頂点のための推定関数を決定する処理ユニット（２）と
を備え、
該第２の格納ユニット（４）に含まれる、所定のタイルの該抵抗値は、該所定のタイルの該境界に位置する頂点を接続する該ルートに関連するコストの下限が、該所定のタイルの該抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表す、システム。
【００６２】
（項目２８）
上記第２の格納ユニット（４）に含まれる、上記所定のタイル（Ｔ０）の上記抵抗値が、該所定のタイルの上記境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する上記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、項目２７に記載のシステム。
【００６３】
（項目２９）
上記第２の格納ユニット（４）に含まれる、上記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連する上記コストの最小値である、ことを特徴とする、項目２７または２８に記載のシステム。
【００６４】
（項目３０）
上記処理ユニット（２）が、上記目的地（２２）を含む目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）を決定し、上記タイル境界頂点（２３）と該少なくとも一つの目的地タイル境界頂点（２４、２５）とを接続する最適ルートに関連するコストの下限を計算し、該下限が上記タイリングのタイルの抵抗値に応じて決定される、ことを特徴とする、項目２７ないし２９のいずれか１項に記載のシステム。
【００６５】
（項目３１）
上記下限が、上記目的地タイル境界頂点（２４、２５）を原点として有するダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して計算される、ことを特徴とする、項目３０に記載のシステム。
【００６６】
（項目３２）
上記タイル境界頂点（２３）の座標と、上記処理ユニット（２）によって決定される該タイル境界頂点（２３）のための上記推定関数値と、を格納するメモリユニット（５）、によって特徴づけられる、項目２７ないし３１のいずれか１項に記載のシステム。
【００６７】
（項目３３）
上記メモリユニット（５）が、上記タイルの境界によって規定される線に沿った上記タイル境界頂点（２３）の位置を指定する一次元的座標の形式において、該タイル境界頂点の該座標を格納する、ことを特徴とする、項目３２に記載のシステム。
【００６８】
（項目３４）
上記処理ユニット（２）が、上記道路網の道路セグメントのための交通メッセージ信号を受信し、該受信された交通メッセージ信号に応じて、該道路セグメントを含むタイルの抵抗値を変更する、ことを特徴とする、項目２７ないし３３のいずれか１項に記載のシステム。
【００６９】
（項目３５）
上記処理ユニット（２）が、上記タイリングのタイルの上記抵抗値に応じて決定されて上記メモリユニット（５）に格納された推定関数値を使用するＡ＊−アルゴリズムを使用して、上記出発点から上記目的地までの最適ルートを決定する、ことを特徴とする、項目２７ないし３４のいずれか１項に記載のシステム。
【００７０】
（項目３６）
上記システムが、項目１ないし２３のいずれか１項に記載の方法を実行する、ことを特徴とする、項目２７ないし３５のいずれか１項に記載のシステム。
【００７１】
（項目３７）
ナビゲーションシステムであって、
目的地を入力する入力手段（６）と、
決定されたルートを出力する出力手段（７）と、
項目２７ないし３６のいずれか１項に応じてルートを決定するシステム（２〜５）とを備え、
該システムは、そこから該目的地を受信する該入力手段（６）と、そこへ決定されたルートを出力する出力手段（７）とに結合されている、ナビゲーションシステム。
【００７２】
（項目３８）
現在の車両位置を決定する位置決定手段（８）を備え、該位置決定手段（８）は、上記ルートを決定するシステム（２〜５）に結合され、該現在の車両位置を上記出発点として提供する、項目３７に記載のナビゲーションシステム。
【００７３】
（項目３９）
上記位置決定手段（８）が、ＧＰＳ受信機を備える、ことを特徴とする、項目３８に記載のナビゲーションシステム。
【００７４】
（項目４０）
交通メッセージ信号を提供する上記処理ユニット（２）に結合されたＴＭＣ受信機（９）、によって特徴づけられる、項目３７ないし３９のいずれか１項に記載のナビゲーションシステム。
【００７５】
（摘要）
道路網の出発点から目的地までのルートを決定する方法およびシステムが提供され、道路網の頂点のための推定関数が使用され、タイリングが道路網の少なくとも一部分が含まれる地域をカバーするように定義され、タイリングの各タイルの抵抗値が提供され、道路網の頂点のための推定関数の値がタイリングのタイルの抵抗値に応じて決定される。好ましい実施形態において、所定のタイル（Ｔ０）の抵抗値は、一対の頂点のエアライン距離（１２、１４）によって分割される所定のタイルの境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を接続する最適ルート（１１、１３）に関連するコストの下限または最小値である。
【発明を実施するための最良の形態】
【００７６】
図１を参照して、本発明の実施形態によるナビゲーションシステム１が説明される。該システムは、Ａ＊−アルゴリズムなどの推定関数を使用するアルゴリズムを使用して、道路網の出発点から目的地までのルートを決定するように適応される。システムは、処理ユニット２、道路網データを含む第１の格納ユニット３、タイリング定義データおよびタイリングのタイルの抵抗値を含む第２の格納ユニット４、およびメモリユニット５を備え、これらの構成要素が組み合わせられて、本発明の実施形態に応じて、ルートを決定するシステムを形成する。第１の格納ユニット３および第２の格納ユニット４は、異なるフィジカルデバイスである得るか、または単一のフィジカルデバイス、たとえば、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＤＶＤ、メモリカード、または内蔵ハードディスクであり得る。
【００７７】
第１の格納ユニット３に格納される道路網データは、たとえば、道路セグメントの出発点および終点の地理的位置などの、道路のセグメント位置と方向性とに関するグラフィカル情報、および道路セグメントを横断する、長さ、特徴的な移動速度、および／または特長的な移動時間を定量化する追加情報を備える、従来の道路網データである。より一般的には、一つまたはいくつかの属性が、各道路セグメントに関連づけられ、特定のコストモデルに対して道路セグメントを横断することに関連するコスト、ならびに、一般的に、道路セグメント交差点に関連するコストを特定する。
【００７８】
第２のメモリユニット４に格納されるタイリング定義データ４ａ〜４ｃは、タイリングのすべてのタイルの配置を決定する。すべてのタイルが均等なサイズを有する四角形のタイリングの単純な場合について、各タイルは、その角の一つの座標によって、またはタイリングにおけるタイルの位置を指定するインデックスまたは一対のインデックスによって、一意に決定される。重要なことには、以下に図２を参照してより詳細に説明されるように、第２の格納ユニットもまた、タイリングの各タイルの抵抗値を含み、抵抗値はタイルを横断することに関連するコストを表す。
【００７９】
第１の格納ユニット３および第２の格納ユニット４に格納されるデータは、処理ユニット２によるさらなる処理のために、メモリユニット５に格納され得る。
【００８０】
ナビゲーションシステム１は、たとえば目的地またはユーザプリファランスを入力する入力手段６、決定されたルートを出力する出力手段７、たとえばディスプレイまたは音声出力ユニット、ＧＰＳ受信機を備える位置決定手段８、およびＴＭＣ受信機９を、さらに備える。
【００８１】
次に、図２を参照して、抵抗値を決定する方法を記述することによって、タイルの抵抗値の定義がより詳細に説明される。図２は、道路網の部分が位置するタイルＴ０を示す。道路セグメントは、四角形によって示される頂点において終了し、小さな四角形はタイルの内部に位置する頂点を示し、一方大きな四角形はタイルの境界に位置する頂点ｔｂｖ１〜ｔｂｖ４を示す。
【００８２】
タイルＴ０の抵抗値を決定するために、まず、境界に位置するすべての頂点、この場合は頂点ｔｂｖ１〜ｔｂｖ４が決定される。次に、タイル境界に位置するこれらの各対の頂点に対して、たとえばダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムを使用して、一対の頂点を接続する最適ルートが決定される。頂点ｔｂｖ１とｔｂｖ２とからなる対、および頂点ｔｂｖ２とｔｂｖ４とからなる対について、これらの最適ルートは、それぞれ図２Ａおよび図２Ｂにおける太線１１および１３として模式的に示される。次に、そのような各対の頂点に対して、エアライン距離（ａｉｒ−ｌｉｎｅ ｄｉｓｔａｎｃｅ）が計算され、エアライン距離は、頂点ｔｂｖ１とｔｂｖ３とについて、および頂点ｔｂｖ２とｔｂｖ４とについて、それぞれ図２Ａおよび図２Ｂにおける点線１２および１４として模式的に示される。次に、２つの頂点を接続する最適ルートに関連するコストと、２つの頂点のエアライン距離との、商（ｑｕｏｔｉｅｎｔ）が計算される。最後に、タイルの境界に位置する種々の対の頂点に対する、すべてのこれらの商の最小値が決定される。タイルＴ０の抵抗値は、この最小値に等しく設定される。
【００８３】
したがって、タイルの抵抗値は、以下の数式によって与えられる：
【００８４】
【数１】
ここで、Ｒはタイルの抵抗値を示し、ｔｖｂｉおよびｔｂｖｊはタイルの境界に位置する頂点を示し、ｃｏｓｔ（ｔｖｂｉ；ｔｂｖｊ）はｔｖｂｉとｔｂｖｊとを接続してタイルを横断する最もコストの低い経路に関連するコストを示し、ａｉｒ−ｌｉｎｅ ｄｉｓｔａｎｃｅ（ｔｖｂｉ；ｔｂｖｊ）は一対の頂点ｔｖｂｉとｔｂｖｊとのエアライン距離を示す。コストは、道路セグメントコストと道路セグメント交差点に関連するコストの両方の寄与を一般的に含み、両方とも考慮に入れられる。
【００８５】
抵抗値の定義によって、タイルの境界に位置する任意の頂点ｔｖｂｉとｔｂｖｊとに対して、これらの頂点を接続する最適ルートに関連するコストは、以下の不等式を満たす：
【００８６】
【数２】
二つの頂点のエアライン距離は道路網の幾何学にのみ依存するので、一対の頂点を接続する最適ルートに関連するコストに対する下限を提供するために、タイルの抵抗値Ｒは既知であるので（数式２）の右側は容易に計算され得ることが、留意されるべきである。以下により詳細に説明されるように、この特徴は、本発明に応じてルートを決定する方法によって、有利に利用される。
【００８７】
道路網における最適ルート検索は、有向グラフにおけるルート検索に一般的に対応することが留意されるべきであり、すなわち、たとえば一方通行道路がタイルの中に位置する場合、または道路セグメントの速度制限が反対の移動方向で異なる場合に、ｔｂｖ１からｔｂｖ３へのルートに関連するコストは、ｔｂｖ３からｔｂｖ１へのルートに関連するコストとは異なり得る。したがって、一般的に、（数式１）の右側の式は、有向グラフに対して評価されなければならず、すなわち、商の分子における頂点の順序は重要である。
【００８８】
さらに、タイル境界に位置する頂点を接続する最適ルートに関連するコストは、使用されるコストモデルに一般的に依存する。したがって、タイリングの各タイルに対して、最短ルートおよび最速ルートなどの最も重要なコストモデルに対していくつかの抵抗値が一般的に決定され、異なる抵抗値が第２の格納ユニット４に格納される。この点で、抵抗値は自動車内で計算されるのではなく、ルート決定における次の使用のための道路網データの前処理のフェーズの間に計算されるということが、再び強調される。
【００８９】
図３を参照して次に説明されるように、上記に示されたように計算される抵抗値は、ルート決定において有利に使用され得る。より具体的には、たとえばＡ＊−アルゴリズムにおいて使用されるような推定関数は、抵抗値から容易に引き出され得る。
【００９０】
図３は、例示的な道路網およびタイリングＴを示す。タイリングは、タイルＴ１〜Ｔ９を備える。道路網の頂点は、この場合もやはり、四角形によって示され、大きな四角形はタイル境界に位置する頂点を示す。説明の目的のみのために、最適ルートは、出発点２１から目的地２２にかけて決定されるものと想定されるべきである。さらに、上記に示されたように決定される抵抗値は、タイリングのすべてのタイルＴ１〜Ｔ９について既知であると想定される。Ａ＊−アルゴリズムを使用して最適ルートを決定するために、推定関数は道路網の各頂点について既知でなければならず、推定関数は道路網の任意の頂点と目的地とを接続する最適ルートに関連するコストの下限を提供する。
【００９１】
タイル境界に位置する頂点、たとえば図３における頂点２３について、この頂点に関する推定関数の値は以下のように決定され得る。
【００９２】
まず、目的地２２を含む目的地タイルＴ３が特定され、目的地タイルの境界に位置する頂点２４および２５が特定される。次に、タイル境界のみに位置する道路網の頂点、すなわち図３の大きな四角形によって示される頂点からなるグラフに対して、目的地タイルＴ３の境界に位置する頂点２４および２５の一つずつから始めて、ダイクストラのアルゴリズムが実行される。このサブグラフのエッジの一部は、図３における点線２６ａ〜２６ｄによって示される。サブグラフの任意のそのようなエッジに関連するコストは、（数式２）によって決定され得、すなわち、サブグラフエッジに関連するコストは、エッジによって接続される頂点のエアライン距離が乗算されたサブグラフエッジによって横断されるタイルの抵抗値に等しく設定される。たとえば、エッジ２６ａに関連するコストは、頂点２３および２４のエアライン距離が乗算されたタイルＴ２の抵抗値に等しく設定される。タイル境界のみに位置する頂点からなるサブグラフは、もともとの道路網よりも一般的にはるかに小さいので、目的地タイルの境界に位置する頂点２４および２５のうちの任意の一つから始めて、ダイクストラのアルゴリズムは容易に実行され得る。好ましい実施形態において、これらの頂点のすべてを一組の原点としてダイクストラのアルゴリズムの中に入力することによって、ダイクストラのアルゴリズムは、すべての目的地タイル境界頂点に対して同時に実行される。さらに、（数式２）によって、サブグラフ上の最適ルートに関連するコストは、もともとの道路網の最適ルートに関連するコストに関する下限である。たとえば、サブグラフ上の最適ルートが、エッジ２６ａを介して頂点２４を頂点２３に接続すると想定して、エッジ２６ａの長さによって乗算されるタイルＴ２の抵抗値は、もともとの道路網の頂点２４から頂点２３への最適ルートに関連するコストに関する下限を提供する。
【００９３】
したがって、タイル境界に位置する頂点２３と、目的地タイルの境界に位置する頂点２４および２５のうちの任意の一つとを接続する最適ルートに関連するコストが、サブグラフ上でひとたび知られると、すべてのこれらのコストの最小値もまた、もともとのグラフ上の最適ルートに関連するコストの下限を提供する。
【００９４】
より一般的には、タイル境界に位置する頂点ｔｂｖのための推定関数（ｅｓｔｉｍａｔｉｏｎ ｆｕｎｃｔｉｏｎ（ｔｂｖ））は、以下の数式から確立され得る：
【００９５】
【数３】
ここで、ｄｔｂｖｉは目的地タイルの境界に位置する頂点を示し、ｃｏｓｔｓＳＧはサブグラフ上の最適ルートに関連するコストを示し、サブグラフは上記に説明されたように定義され、ルートはｄｔｂｖｉとｔｂｖとを接続する。上記の式の右側に関する最小値は、目的地タイルの境界に位置するすべての頂点にわたって取られる。
【００９６】
推定関数の正確性は、目的地２２を目的地タイル境界頂点２４および２５に接続するルートに関連するコストを考慮に入れることによって、さらに改善され得る。
【００９７】
【数４】
ここで、（数式４）の右側に関する角括弧における第２項は、目的地を目的地タイル境界頂点の一つずつと接続する最適ルートのコストを表す。これらのコストは、目的地タイルＴ３においてダイクストラのアルゴリズムを使用して、たとえば決定され得る。しかし、任意の下限は、実際のコストの代わりに使用され得る（たとえばエア距離（ａｉｒ ｄｉｓｔａｎｃｅ）のみに基づいた下限）。普通の下限の場合については、（数式４）の角括弧における第２項がゼロに設定され、（数式４）が（数式３）に置き換えられる。
【００９８】
好ましい実施形態において、すべての目的地タイル境界頂点が原点のセットとして同時に入力されるようにダイクストラのアルゴリズムが使用され、たとえばもともとの道路網の目的地タイル上でダイクストラのアルゴリズムを実行することによってコスト（ｄ；ｄｔｂｖｉ）が既知である場合に、かつこれらの値が上述にように定義されるサブグラフ上で実行されるダイクストラのアルゴリズムに入力される場合に、（数式４）の右側はこのダイクストラのアルゴリズムによって容易に決定され得る。
【００９９】
代替的に、（数式４）の右側は、目的地タイルの中に位置するもともとの道路セグメントと、目的地タイルの外側ではタイルのエッジのみに位置する頂点を接続するエッジとを含む、新しいグラフを定義することによって、計算され得る。図１１に示される、そのような再定義されたグラフが、以下により詳細に説明される。再定義されたグラフ上でダイクストラのアルゴリズムを実行することによって境界頂点に対して決定されたコストは、各タイル境界頂点について（数式４）の右側である。
【０１００】
上記の説明は説明的な目的のために頂点２３に限定されているが、タイル境界に位置する任意の頂点のための推定関数は、上述のように決定され得ることが理解される。タイル境界に位置するすべての頂点のための推定関数がひとたび決定されると、次に説明されるように、それはタイルの内側に位置する頂点についても容易に決定され得る。
【０１０１】
図４および５は、図３のタイリングＴのタイルＴ２とその中に位置する道路網の部分とを示す。推定関数は頂点２３および２４に対してすでに決定され、その推定関数はこれらの頂点と目的地とを接続する最適ルートに関連するコストの下限を提供するので、タイルＴ２の内側に位置する頂点２９のための推定関数は以下のように決定され得る。
【０１０２】
一実施形態において、頂点２９を頂点２３および２４にそれぞれ接続する最適ルートに関連する正確なコストは、ダイクストラのアルゴリズムを使用して決定される。次に、これらのコストと、タイル境界に位置する頂点に対応する推定関数との合計が計算され、合計のうちの小さいほうの一つが頂点２９のための推定関数値を提供する。
【０１０３】
しかし、頂点２９を頂点２３および２４に接続する最適ルートに関連する正確なコストを計算する必要はない。むしろ、任意の適切な下限が使用され得る。たとえば、図４において示されるように、それぞれ点線２７および２８として模式的に示されるエアライン距離は、頂点２９とタイルＴ２の境界に位置する頂点とを接続するルートに関連するコストを推定するために使用され得る。
【０１０４】
図４において示されるエアライン距離の計算は平方根の評価を伴なうので、推定関数の計算をさらに促進するために、代替的に、図５において模式的に示されるように、垂直距離２７’および２８’も、タイルの内側のルートに関連するコストの下限として使用され得る。たとえば、最短ルート検索を想定して、頂点２９の推定関数は、垂直距離２７’をプラスした頂点２４の推定関数と、垂直距離２８’をプラスした頂点２４の推定関数とのうちの、小さいほうに等しく設定される。最後に、さらに別の実施形態において、タイルの内側の各頂点のための推定関数は、このタイルの境界に位置する頂点の推定関数の最小値に等しく単純に設定され得、これによって、推定関数の正確性を犠牲にして、推定関数を決定することにおける計算の複雑さを低減する。
【０１０５】
図２〜５は、本発明の種々の実施形態による推定関数の決定の基礎をなす根本的な原理を説明する役割を果す。図２を参照して説明されるような抵抗値の決定も、本発明の範囲によって含まれることが意図されることが留意されるべきである。
【０１０６】
次に、図６〜１０を参照して、種々の実施形態に応じて出発点から目的地までのルートを決定する方法が、詳細に説明される。
【０１０７】
図６は、本発明の実施形態に応じてルートを決定する方法を、模式的に示すフローチャートを示し、該方法は一般的に３０によって示されている。まず、ステップ３１において、出発点および目的地が受信される。出発点および目的地に関する情報は、たとえば、ユーザ入力によって提供され得、あるいは出発点もまた位置決定手段８によって自動的に提供され得る。
【０１０８】
ステップ３２において、タイリングＴが定義され、タイリングＴは、ルート検索が実行されるべき道路網の少なくとも部分が含まれるべき地域をカバーする。ステップ３３において、推定関数が道路網の複数の頂点に対して決定され、このステップは以下に図７〜１０を参照してより詳細に説明される。道路網のすべてのまたは少なくともすべての関連する頂点に対して、ひとたび推定関数が知られると、ステップ３６において、ステップ３３においてすでに決定された推定関数に基づいて、出発点から目的地までの最適ルートを決定するためにＡ＊−アルゴリズムが実行される。最後に、ステップ３７において、出力手段７を介して、たとえば電子地図の形でまたは音声出力として、最適ルートが出力される。
【０１０９】
本発明の一実施形態において、図７〜９を参照して次に説明されるように、道路網の頂点のための推定関数を決定するステップ３３は、２つのステッププロセスとして実行される。図７のフローチャートにおいて模式的に示されるように、まず、ステップ３４において、境界に位置する頂点に対して推定関数が決定され、次に、ステップ３５において、タイル内側に位置する頂点に対して推定関数が決定される。
【０１１０】
図８は、タイル境界に位置する頂点に対して推定関数を決定するステップ３４を表すフローチャートを模式的に示す。まず、ステップ３４１において、目的地ｄを含むタイルＴｄが決定され、ステップ３４２において、Ｔｄの境界に位置する頂点が決定され、これらの頂点はｄｔｂｖｉによって示される。ステップ３４３において、目的地タイルの境界に位置する各頂点に対して、目的地ｄと目的地タイル境界頂点とを接続する最適ルートに関連するコストの下限が決定され、下限はｃｏｓｔ（ｄｔｂｖｉ）として示される。この下限は、たとえば、目的地タイル上でダイクストラのアルゴリズムを使用して、または上記の図３を参照して説明された任意の他の適切な方法を使用して、決定され得る。
【０１１１】
ステップ３４４において、新しいグラフが定義され、そのグラフは、もともとの道路網のサブグラフであり、境界のみに位置する頂点を含む。重要なことには、上記に図３を参照して説明されたように、サブグラフのエッジに関連するコストは、一般的に道路網の幾何学的特性とともに、タイリングの種々のタイルの抵抗値に基づいて決定される。ステップ３４５において、目的地タイルに位置する頂点の一つずつから始まる、ダイクストラのアルゴリズムが実行される。好ましい実施形態において、ステップ３４５におけるダイクストラのアルゴリズムは、一回のみ実行され、原点のセットとしてすべての目的地タイル境界頂点を有する。
【０１１２】
ダイクストラのアルゴリズムの代わりに、Ａ＊−アルゴリズムが、ステップ３４５において、目的地タイル境界頂点から出発点に向けて、エアラインベースの推定を使用して、実行され得る。
【０１１３】
最後に、ステップ３４６〜３４８において、これらの頂点のための推定関数を決定するために、タイル境界に位置する頂点にわたって反復が実行される。ステップ３４６において、タイル境界に位置する頂点が選択される。ステップ３４７において、上記の（数式４）を参照して説明されたように、すなわち、ステップ３４５において決定される、頂点と目的地タイルの境界に位置する頂点とを接続する最適ルートに関連するコストの下限と、目的地タイルの境界に位置する頂点と目的地とを接続するルートに関連するコストとから、この頂点のための推定関数が決定される。最後に、ステップ３４８において、決定された推定関数値がメモリユニット５に格納される。
【０１１４】
ステップ３４６〜３４８における、境界に位置する頂点にわたる反復は、任意の適切な終了基準に応じて終了され得、それはたとえば、タイル境界に位置するすべての頂点に対して、または少なくとも、最適ルート決定に関連し得るタイルの境界に位置するすべての頂点に対して、推定関数が知られた場合である。
【０１１５】
図８のフローチャートは模式的のみであり、そこに示されるステップのいくつかは並行して実行され得ることが、留意されるべきである。たとえば、好ましい実施形態において、ステップ３４５およびステップ３４６〜３４８における反復は実行され、その結果、すべての目的地タイル境界頂点を同時に入力として有する、ダイクストラのアルゴリズムまたはＡ＊−アルゴリズムが実行され、ルート検索の出発点に向けて検索が実行される。代替的に、ステップ３４３、３４５、および３４６〜３４８は、以下に図１１を参照して説明されるように、まずグラフを再定義することによって、次に再定義されたグラフ上でダイクストラのアルゴリズムまたはＡ＊−アルゴリズムを実行することによって、並行して実行され得る。
【０１１６】
図９を参照して次により詳細に説明されるように、タイル境界に位置するすべての関連する頂点に対して推定関数がひとたび知られると、ステップ３５において、タイルの内側に位置する頂点に対して推定関数が決定される。まず、ステップ３５１において、タイルＴｉが選択される。次に、ステップ３５２において、このタイルの境界に位置するすべての頂点が決定される。ステップ３５３〜３５６において、タイルの内側に位置するすべての頂点にわたる反復が実行される。まず、ステップ３５３において、タイル内側に位置する頂点が選択される。ステップ３５４において、このタイルの境界に位置する各頂点に対して、タイルの内側における選択された頂点とタイル境界に位置する頂点とを接続する最適ルートのコストに関する下限が決定される。図９において、この値は、たとえば選択されたタイル上でダイクストラのアルゴリズムを使用して得られた、これらの２つの頂点を接続する最適ルートに関連する正確なコストとして模式的に表されるが、上記に図４および５を参照して説明されたように、これらのコストの下限を入手する任意の他の適切な方法が使用され得る。次に、ステップ３５５において、タイル境界に位置する対応する頂点のための推定関数がプラスされたこれらのコストの最小値が決定され、タイル内側に位置する頂点のための推定関数が、この最小値に等しく設定される。ステップ３５６において、決定された推定関数値が格納される。ステップ３５３〜３５６が、タイル内側に位置するすべての頂点にわたって反復される。タイル内側に位置する頂点にわたる反復の終了後、ステップ３５７において新しいタイルＴｉが選択され、ステップ３５２〜３５６がタイリングのすべての関連するタイルにわたって反復される。
【０１１７】
図６に戻って、上述のように、道路網のすべての関連する頂点のための推定関数が、タイリングのタイルの抵抗値に基づいて決定されて、この推定関数を使用するＡ＊−アルゴリズムが実行され得る。再び、タイリングＴの定義、およびタイリングのタイルの抵抗値の提供は、Ａ＊−アルゴリズムにおいて使用される推定関数が容易にかつ確実に計算されることを可能にすることが、強調されるべきである。
【０１１８】
図６〜９を参照した上記の説明は、本発明による方法の一つの有利な実施形態を表すのみであり、種々の変更が考え得ることが理解される。ステップ３４４において、サブグラフのエッジに関連するコストは、タイルの抵抗値を、このタイルの境界に位置する一対の頂点のエアライン距離によって乗算することによって推定され得るが、サブグラフのエッジに関連するコストは、任意の他の適切な方法でも決定され得る。たとえば、頂点がタイル境界の対向するエッジに位置する場合には、一対の頂点を接続するエッジに関連するコストは、タイルの抵抗値とエッジの長さとの積によって近似され得る。さらにまた、推定関数を計算するために、タイルの一つのエッジに位置する複数の頂点が単一の頂点に縮約され得、したがって推定関数の計算の複雑さをさらに低減させる。
【０１１９】
上記の説明において、ステップ３４３、３４７、３５４、および３５５において、タイルの内側に位置する頂点とタイル境界に位置する頂点とを接続する最適ルートに関連する正確なコストが使用されているが、これらのコストの下限を提供する任意の他の適切な方法が使用され得る。たとえば、上記に図４および５を参照して説明されたように、頂点のエアライン距離、またはタイル境界からの頂点の距離が、これらのコストの下限を引き出すために使用され得る。
【０１２０】
図６において示される方法の別の変更が、次に図１０および１１を参照して説明される。この変更に応じて、図６のステップ３３は、図１０のステップ３３’によって置き換えられる。この変更の基礎をなす根本的な考えは、出発点から目的地までの最適ルートを決定するために、タイル内側に位置する頂点のための推定関数を必ずしも計算する必要はないということである。
【０１２１】
変更によれば、まず、ステップ３４において、タイル境界に位置する頂点に対して推定関数が決定される。このステップは、上記の図８を参照して説明されたように実行される。次に、ステップ３８において、出発点を含む出発タイルの内側に位置する頂点、および目的地を含む目的地タイルの内側に位置する頂点に対して、推定関数が決定される。目的地タイルに対しては、これは、たとえば、目的地から始まるダイクストラのアルゴリズムを使用して達成され得る。出発タイルに対しては、推定関数は、上記の図９を参照して説明されたように決定され得る。次に、ステップ３９において、最適ルート検索が実行されるべきグラフが、出発タイルおよび目的地タイルに位置するすべての頂点、ならびにタイル境界に位置するすべての頂点からなるように、再定義される。図３に示される道路網について、これは図１１において模式的に示される。一つのタイルの境界に位置する一対の頂点を接続する、変更されたグラフのこれらのエッジに関連するコストは、たとえば、このタイル上でダイクストラのアルゴリズムを実行し、境界に位置する一対の頂点を接続するルートに関連する最小コストを決定することによって、任意の適切な方法によって決定され得る。次に、変更されたグラフ上で最適ルート検索が実行される。タイルの頂点は、タイルの境界に位置する、より少ない数の頂点に縮約されるので、頂点は、決定された最適ルートをユーザに出力する前に抽出されなければならない。これは、たとえば、個々のタイルのダイクストラのアルゴリズムに基づいて、最適ルート検索によって再び達成され得る。
【０１２２】
図３および１１において、タイリングＴは、同一のサイズと形状とを有する複数のタイルからなるように示されるが、必ずしもそうである必要はない。
【０１２３】
実際には、次に図１２を参照して説明されるように、不均一なタイリングサイズを有するタイリングを選択することは有利であり得る。この目的のために、図１２Ａおよび１２Ｂにおいて示される２つの異なるタイリングＴ’とＴ’’とは、少なくとも道路網の一部分が含まれる地域をカバーするように定義される。タイリングＴ’’については、道路網が各道路セグメントの交差点とタイル境界とに頂点を有するように定義されるが、表示の明瞭さのためにこれらの頂点のすべてが表示されるわけではない、ということが留意されるべきである。
【０１２４】
タイリングＴ’およびＴ’’の両方について、上記に図２を参照して説明されたように、各タイルに対して抵抗値が計算される。タイリング定義データおよび関連する抵抗値は、両方のタイリングＴ’およびＴ’’について、第２の格納ユニット４に格納される。
【０１２５】
出発点および目的地が入力されて初めて、図１２Ｃに模式的に示されるタイリングＴは、より大きなタイルサイズを有するタイリングＴ’のタイルと、より小さなタイルサイズを有するタイリングＴ’’のタイルとの両方を含むように、定義される。より具体的には、出発点および目的地の近郊に対しては、より小さなタイルＴ１’’〜Ｔ６’’が選択され、一方、出発点および目的地の両方から距離のある地域に対しては、より大きなタイルＴ１’およびＴ２’が選択される。不均一なタイルサイズを有するこのタイリングの各タイルに対して、抵抗値は、個々のタイルサイズに対して決定された抵抗値に選択され、第２の格納ユニット４に格納される。上記に図６〜１０を参照して説明された、出発点から目的地までのルートを決定する種々の方法が、図１２Ｃに示される不均一なタイリングに対して容易に適用され得る。
【０１２６】
このような文脈において、図においては四角形のタイルが示されるが、任意の他の適切なタイルの形状が使用され得ることもまた理解されるべきである。さらに、すべてのタイルが同じ形状を有する必要はない。
【０１２７】
本発明によれば、ルートを決定する方法が実行されるときに、タイルの抵抗値に基づいて推定関数が決定されるので、本発明の方法は、次に図１３を参照して説明されるように、動的なルート決定に容易に適合し得る。動的なルート決定の方法は、一般的に４０において示される。まず、ステップ４１において、ＴＭＣ信号またはユーザ入力が受信され、そのことは、たとえば交通渋滞が原因で、またはユーザプリファランスが原因で、特定の道路セグメントが回避されることを示す。次に、ステップ４２において、ＴＭＣ信号またはユーザ入力によって影響された道路セグメントが特定される。その後で、ステップ４３において、影響された道路セグメントを含むすべてのタイルが特定される。ステップ４４において、影響された道路セグメントに関連するコストは、受信されたＴＭＣ信号またはユーザ入力に応じてアップデートされる。ステップ４５において、影響された道路セグメントを含むタイルの、一つのまたは複数の抵抗値がアップデートされる。次に、上記に図６〜１０を参照して説明されたように、影響された道路セグメントのアップデートされたコスト、および影響されたタイルのアップデートされた抵抗値の両方を考慮に入れて、ルート決定３０が実行される。特に、ステップ３３において、推定関数は、アップデートされた抵抗値に基づいて計算される。
【０１２８】
影響されたタイルの抵抗値のアップデートは、ステップ４５において、種々の異なる方法で実行され得る。たとえば、影響されたタイルに位置する道路セグメントに関連するコストが増加された場合には、影響されたタイルの抵抗値は、所定の定数によって乗算され得る。該定数は、受信されたユーザ入力またはＴＭＣ信号に依存し得る。多くのユーザ入力またはＴＭＣ信号は、所定のタイルに含まれるすべての道路セグメントが好ましく回避されるべきであるという結果になるようになっている。そのような場合において、これらの道路セグメントの一つずつに関連するコストが、倍数因子によって増加する場合には、これらの道路セグメントを含むタイルの抵抗値は、同じ因子によって乗算される。そのような場合においてもまた、正確な最適ルートが決定され得る。
【０１２９】
たとえ道路セグメントコストが変更されたとしても、タイルの抵抗値をアップデートする必要はないことが、留意されるべきである。むしろ、もともとの抵抗値に基づいて決定された推定関数は、それでも目的地へのコストを過小評価している。したがって、ステップ４５もまた省略され得る。
【０１３０】
代替的に、いくつかの抵抗値は単一のタイルに対して提供され得、それらの抵抗値は、いかなるユーザプリファランスまたはＴＭＣ信号も用いない所定のコストモデルについて、および一般的なＴＭＣ信号またはユーザプリファランスを考慮に入れたときのこの所定のモデルについて、それぞれ計算された抵抗値を反映する。たとえば、交通渋滞する傾向がある道路セグメントを含むタイルに対して、２つの抵抗値が計算され得、一つは道路セグメントがブロックされない場合についてであり、もう一つは道路セグメントがブロックされる場合についてである。次に、ステップ４１において受信されたＴＭＣ信号に応じて、ステップ４５においてこれらの抵抗値のうちのいずれか一つが選択される。
【０１３１】
しばしば、最適ルートは、異なるコストモデルの線形な組み合わせの形をなすコストモデルに対して決定される。たとえば、最短ルートおよび最速ルートの種々の重み付けされた組み合わせが使用され得る。ＸとＹとが異なるコストモデルを示し、α・Ｘ＋β・Ｙがそれらの線形な組み合わせを示す場合には、組み合わせられたコストモデルのタイルの抵抗値は、以下の関係を満たし：
【０１３２】
【数５】
ここで、Ｒ（Ｘ）およびＲ（Ｙ）は、それぞれコストモデルＸおよびＹに基づいた各タイルの抵抗値を示す。したがって、コストモデルの抵抗値の線形な組み合わせは、コストモデルの線形な組み合わせの抵抗値に関する下限を提供する。推定関数を決定するためには、コストの下限を提供することで十分であるので、コストモデルα・Ｘ＋β・Ｙのための推定関数は、基礎をなす根本的なコストモデルＸおよびＹの抵抗値のそれぞれの線形な組み合わせにより、組み合わせられたコストモデルの抵抗値を近似することによって得られ得る。
【０１３３】
したがって、本発明の実施形態において、タイリングの各タイルについて、異なる基礎コストモデルに対応する複数の抵抗値が格納される。基礎コストモデルの線形な組み合わせに対応するコストモデルに対してルート検索が実行される場合には、図６〜１０において示される方法において、最初のステップにおいて、タイルの抵抗値が、基礎コストモデルの線形な組み合わせとして決定される。一実施形態において、基礎コストモデルは、最短ルートおよび最速ルートを含む。
【０１３４】
抵抗値の局所的な性質のために、本方法および本システムは、部分的な地図アップデートに良好に適していることが理解される。より具体的には、既存の道路網が変更される場合、または道路網がその外側の追加の道路セグメントによって補われる場合、たとえば、道路網の新しい部分がデジタル化される場合には、道路網が実際に変更されたこれらのタイルの抵抗値だけがアップデートされる必要がある。
【０１３５】
図１４は、北部と中部ドイツとの地図部分を示し、その中でタイルの抵抗値はグレースケール表示で示される。タイルは、形状において四角形であるように選択され、８キロメートルのエッジ長さを有する。抵抗値は、最速ルートのコストモデルに対して計算される。理解され得るように、ドイツの道路網の幹線道路は、抵抗値において明瞭に検出され得る。
【０１３６】
図１５は、グレースケール表示における、北部ドイツから南部ドイツまでの最適ルート検索における検索された地域を示し、この場合も８キロメートルのエッジの長さを有する四角形のタイリングを使用している。図１５Ａは本発明に応じた最適ルート決定における検索された地域を示し、一方、図１５Ｂは従来の方法に応じた最適ルート決定における検索された地域を示す。より具体的には、図１５Ａにおいては、タイル抵抗値に基づいて推定関数が決定され、一方、図１５Ｂにおいては、エアライン距離に基づいた従来の推定関数が使用されている。最適ルートは、Ａ＊−アルゴリズムを使用して決定される。エッジ緩和を介して調査されたタイルは、種々のグレースケールで示され、異なる色は出発点からの発生した移動時間を表す。明らかに理解され得るように、調査される必要のあるタイルの数は、従来の方法におけるよりも（図１５Ｂ）、本発明による方法においてはるかに小さい（図１５Ａ）。このことは、結果として最適ルート検索のためのより短い実行時間になる。
【０１３７】
本発明の種々の実施形態による方法は、最適ルート検索において道路セグメントの部分集合のみが検索される任意の方法と容易に相互併用され得る。そのような方法の例は、たとえば、ＥＰ １ ０２７ ５７８において、またはＷＯ ０３／０７９１５５において、または欧州特許出願第０５ ０２４ ４１４号において開示されるか、あるいはＦＲＣに基づいた発見的方法である。これらの方法は、道路網をＡ＊−アルゴリズムにおいて検索されるようにしかるべく制限することによって、本発明による方法と一体化され得る。
【０１３８】
要約すれば、本発明によれば、推定関数を使用する、ルートを決定する方法およびシステムが提供され、道路網の頂点のための推定関数の値は、タイリングに基づいて、かつタイリングのタイルの抵抗値に基づいて、決定される。好ましい実施形態の上記の説明から明らかなように、本発明によれば、正確な推定関数が決定され得、部分的な地図アップデートが容易に実行され得、かつ動的なルート決定が容易に実行され得る。本発明は、任意の最適ルート検索において、特に、道路網の最適ルートの決定において、有利に使用され得る。
【図面の簡単な説明】
【０１３９】
本発明の追加の特徴および利点は、添付の図面を参照して、好ましいまたは有利な実施形態の詳細な説明から、より容易に理解される。
【図１】図１は、本発明の実施形態によるルートを決定するシステムの模式的なブロック図を示す。
【図２】図２Ａは、道路網の一部分を示し、本発明の実施形態による抵抗値の決定を図示する役目を果たす。図２Ｂは、道路網の一部分を示し、本発明の実施形態による抵抗値の決定を図示する役目を果たす。
【図３】図３は、道路網および対応するタイリングを示し、本発明の実施形態によるタイル境界に位置する頂点のための推定関数を決定する方法を図示する役目を果たす。
【図４】図４は、図３の道路網の一部分を示し、本発明の実施形態によるタイルの内側頂点のための推定関数を決定する方法を図示する役目を果たす。
【図５】図５は、図３の道路網の一部分を示し、本発明の実施形態によるタイルの内側頂点のための推定関数を決定する方法を図示する役目を果たす。
【図６】図６は、本発明の実施形態によるルートを決定する方法を表すフローチャートを示す。
【図７】図７は、図６によって表される方法のサブルーチンを表すフローチャートを示す。
【図８】図８は、図６によって表される方法のさらに別のサブルーチンを表すフローチャートを示す。
【図９】図９は、図６によって表される方法のさらなる別のサブルーチンを表すフローチャートを示す。
【図１０】図１０は、本発明の代替的な実施形態による、図６によって表される方法のサブルーチンを表すフローチャートを示す。
【図１１】図１１は、図３の道路網とタイリングとを示し、図１０によって表される代替的な実施形態による方法を図示する役目を果たす。
【図１２Ａ】図１２Ａは、図３の道路網と、異なるタイリングとを示し、本発明による方法のさらに別の実施形態を図示する役目を果たす。
【図１２Ｂ】図１２Ｂは、図３の道路網と、異なるタイリングとを示し、本発明による方法のさらに別の実施形態を図示する役目を果たす。
【図１２Ｃ】図１２Ｃは、図３の道路網と、異なるタイリングとを示し、本発明による方法のさらに別の実施形態を図示する役目を果たす。
【図１３】図１３は、動的なルート決定の方法を表すフローチャートを示し、図６によって表されるルート決定の方法を使用する。
【図１４】図１４は、地図の一部分を示し、抵抗値はグレースケールで示される。
【図１５Ａ】図１５Ａは、本発明の実施形態による方法に従って実行された最適ルート決定の間に検索された地域を示す。
【図１５Ｂ】図１５Ｂは、一方、従来の方法に応じて実行された同じ最適ルート決定における、検索された地域を示す。
【符号の説明】
【０１４０】
１ ナビゲーションシステム
２ 処理ユニット
３ 第１の格納ユニット
４ 第２の格納ユニット
４ａ タイリング定義データ
４ｂ タイリング定義データ
４ｃ タイリング定義データ
５ メモリユニット
６ 入力手段
７ 出力手段
８ 位置決定手段
９ ＴＭＣ受信機
【特許請求の範囲】
【請求項１】
道路網の出発点から目的地までのルートを決定する方法であって、
該方法は、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
該道路網の少なくとも一部分が含まれる地域をカバーするタイリング（Ｔ）を定義するステップと、
該タイリングの各タイルの抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数値を決定するステップと
を包含し、
所定のタイルの抵抗値は、該所定のタイルの境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表す、
方法。
【請求項２】
前記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルにおける前記道路網の幾何学的特性に関連して、該所定のタイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を接続するルート（１１、１３）に関連するコストを表す、ことを特徴とする、請求項１に記載の方法。
【請求項３】
前記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルの境界に位置する一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する前記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連するコストの最小値である、ことを特徴とする、請求項３に記載の方法。
【請求項５】
前記タイル境界頂点（２３）に対して前記推定関数値を決定するステップが、
前記目的地（２２）を含む目的地タイル（Ｔ３）を決定するステップと、
該目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）と、該タイル境界頂点（２３）と、を接続する最適ルートに関連するコストの第１の下限を決定するステップと
をさらに包含する、ことを特徴とする、請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
前記第１の下限が、前記タイルの前記抵抗値に応じて、または前記タイリングの複数のタイルの前記抵抗値に応じて、決定される、ことを特徴とする、請求項５に記載の方法。
【請求項７】
前記第１の下限が、タイル境界のみに位置する頂点（２３〜２５）を含む前記道路網のサブグラフに対して、ダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、請求項６に記載の方法。
【請求項８】
任意のタイル（Ｔ２）の境界に位置する第１および第２の頂点（２３、２４）を接続するサブグラフのエッジ（２６ａ）に関連するコストが、該任意のタイルの抵抗値と、該第１および第２の頂点（２３、２４）のエアライン距離とから決定される、ことを特徴とする、請求項７に記載の方法。
【請求項９】
前記サブグラフのエッジ（２６ａ）に関連する前記コストが、前記第１および第２の頂点（２３、２４）のエアライン距離が乗算された前記任意のタイル（Ｔ２）の抵抗値に等しく設定される、ことを特徴とする、請求項８に記載の方法。
【請求項１０】
前記タイル境界頂点（２３）に対して前記推定関数を決定する前記ステップが、
前記目的地（２２）と、前記少なくとも一つの目的地タイル境界頂点（２４、２５）と、を接続する最適ルートに関連するコストの第２の下限を決定するステップと、
前記第１の下限と前記第２の下限とを加算するステップと
をさらに含む、ことを特徴とする、請求項５ないし９のいずれか１項に記載の方法。
【請求項１１】
前記タイル境界頂点（２３）に対して前記推定関数値を決定する前記ステップが、
すべての目的地タイル境界頂点（２４、２５）にわたる前記第１の下限と前記第２の下限との合計の最小値を決定するステップをさらに含む、ことを特徴とする、請求項１０に記載の方法。
【請求項１２】
前記タイル（Ｔ２）の前記境界に位置するタイル境界頂点（２３、２４）のための推定関数値からの該タイル（Ｔ２）の内側に位置する内側頂点（２９）のための推定関数値と、該内側頂点（２９）と該タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの下限と、を決定する、ステップによって特徴付けられる、請求項１ないし１１のいずれか１項に記載の方法。
【請求項１３】
前記内側頂点（２９）と前記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの前記下限が、該内側頂点（２９）と該タイル境界頂点（２３、２４）とのエアライン距離から決定される、ことを特徴とする、請求項１２に記載の方法。
【請求項１４】
前記内側頂点（２９）と前記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの前記下限が、該タイル境界頂点（２３、２４）が位置する前記タイルのエッジからの前記内側頂点の最小エアライン距離（２７’、２８’）から決定される、ことを特徴とする、請求項１２に記載の方法。
【請求項１５】
前記道路網の道路セグメントのコスト要因における増加を検出するステップと、
該コスト要因における検出された増加に応じて、該道路セグメントを含むタイルの抵抗値を増加させる、ステップとによって特徴づけられる、請求項１ないし１４のいずれか１項に記載の方法。
【請求項１６】
前記道路セグメントを含む前記タイルの抵抗値を増加させることが、乗法による、ことを特徴とする、請求項１５に記載の方法。
【請求項１７】
前記道路セグメントの前記コスト要因が、ユーザ入力に依存して増加する、ことを特徴とする、請求項１５または１６に記載の方法。
【請求項１８】
交通メッセージ信号を自動的に受信し、前記道路セグメントの前記コスト要因が該受信された交通メッセージ信号に依存して増加する、ステップによって特徴づけられる、請求項１５ないし１７のいずれか１項に記載の方法。
【請求項１９】
前記タイリング（Ｔ）のタイル（Ｔ１’、Ｔ２’、Ｔ１’’〜Ｔ６’’）のタイルサイズが、前記出発点と前記目的地からの増加する距離とともに増加する、ことを特徴とする、請求項１ないし１８のいずれか１項に記載の方法。
【請求項２０】
第１の抵抗値が、第１の規則的なタイリング（Ｔ’）の各タイルに対して提供され、
第２の抵抗値が、第２の規則的なタイリング（Ｔ’’）の各タイルに対して提供され、
前記地域をカバーする前記タイリング（Ｔ）が、該第１の規則的なタイリング（Ｔ’）のタイル（Ｔ１’、Ｔ２’）と、第２の規則的なタイリング（Ｔ’’）のタイル（Ｔ１’’〜Ｔ６’’）とを含み、該タイリングのタイルの抵抗値が、対応する該第１および該第２の抵抗値とそれぞれ等しい、ことを特徴とする、請求項１９に記載の方法。
【請求項２１】
前記タイリング（Ｔ）の各タイルに対して、第１の基礎抵抗値および第２の基礎抵抗値が提供され、これらの抵抗値が第１および第２の基礎コストモデルをそれぞれ表し、該第１および第２の基礎コストモデルの線形な組み合わせとして形成されるコストモデルに対して、該抵抗値の下限が、該第１および第２の基礎抵抗値の線形な組み合わせによって決定される、ことを特徴とする、請求項１ないし２０のいずれか１項に記載の方法。
【請求項２２】
前記出発点から前記目的地までの最適ルートが、前記タイリングのタイルの抵抗値に応じて決定される推定関数を使用するＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、請求項１ないし２１のいずれか１項に記載の方法。
【請求項２３】
グラフ上の目的地へのルートを決定する方法であって、
該方法は、該グラフの複数の頂点のための推定関数を使用し、
該推定関数は、該グラフの頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該グラフの少なくとも一部分が含まれる、ステップと、
該タイリングの各タイルに対して抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数を決定するステップと
を含み、
所定のタイルの抵抗値は、該所定のタイルの該境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値に基づいて導出可能であるように、該所定のタイルの境界に位置する該グラフの頂点を接続するルートに関連するコストを表す、方法。
【請求項２４】
道路網データを前処理する方法であって、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該道路網の少なくとも一部分が含まれる、ステップと、
該タイリングのタイル（Ｔ０）に対して、該タイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を決定するステップと、
任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離によって分割される該タイルの境界に位置する該一対の頂点を接続する最適ルート（１１、１３）に関連するコストの下限を決定するステップと、
該決定された下限を出力するステップと
を含む、方法。
【請求項２５】
前記下限が、任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）の前記エアライン距離によって分割される前記タイルの境界に位置する該一対の頂点を接続するルートに関連する前記コストの最小値から決定される、ことを特徴とする、請求項２４に記載の方法。
【請求項２６】
前記下限が、出力の前に離散化される、ことを特徴とする、請求項２４または２５に記載の方法。
【請求項２７】
道路網の出発点から目的地までのルートを決定するシステムであって、
該システムは、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該システムは、
道路網データを含む第１の格納ユニット（３）と、
タイリングを定義するタイリング定義データと、各タイルの抵抗値と、を含む第２の格納ユニット（４）と、
該タイリングの該タイルの該抵抗値に応じて、タイル境界に位置するタイル境界頂点のための推定関数を決定する処理ユニット（２）と
を備え、
該第２の格納ユニット（４）に含まれる、所定のタイルの該抵抗値は、該所定のタイルの該境界に位置する頂点を接続する該ルートに関連するコストの下限が、該所定のタイルの該抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表す、システム。
【請求項２８】
前記第２の格納ユニット（４）に含まれる、前記所定のタイル（Ｔ０）の前記抵抗値が、該所定のタイルの前記境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する前記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、請求項２７に記載のシステム。
【請求項２９】
前記第２の格納ユニット（４）に含まれる、前記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連する前記コストの最小値である、ことを特徴とする、請求項２７または２８に記載のシステム。
【請求項３０】
前記処理ユニット（２）が、前記目的地（２２）を含む目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）を決定し、前記タイル境界頂点（２３）と該少なくとも一つの目的地タイル境界頂点（２４、２５）とを接続する最適ルートに関連するコストの下限を計算し、該下限が前記タイリングのタイルの抵抗値に応じて決定される、ことを特徴とする、請求項２７ないし２９のいずれか１項に記載のシステム。
【請求項３１】
前記下限が、前記目的地タイル境界頂点（２４、２５）を原点として有するダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して計算される、ことを特徴とする、請求項３０に記載のシステム。
【請求項３２】
前記タイル境界頂点（２３）の座標と、前記処理ユニット（２）によって決定される該タイル境界頂点（２３）のための前記推定関数値と、を格納するメモリユニット（５）、によって特徴づけられる、請求項２７ないし３１のいずれか１項に記載のシステム。
【請求項３３】
前記メモリユニット（５）が、前記タイルの境界によって規定される線に沿った前記タイル境界頂点（２３）の位置を指定する一次元的座標の形式において、該タイル境界頂点の該座標を格納する、ことを特徴とする、請求項３２に記載のシステム。
【請求項３４】
前記処理ユニット（２）が、前記道路網の道路セグメントのための交通メッセージ信号を受信し、該受信された交通メッセージ信号に応じて、該道路セグメントを含むタイルの抵抗値を変更する、ことを特徴とする、請求項２７ないし３３のいずれか１項に記載のシステム。
【請求項３５】
前記処理ユニット（２）が、前記タイリングのタイルの前記抵抗値に応じて決定されて前記メモリユニット（５）に格納された推定関数値を使用するＡ＊−アルゴリズムを使用して、前記出発点から前記目的地までの最適ルートを決定する、ことを特徴とする、請求項２７ないし３４のいずれか１項に記載のシステム。
【請求項３６】
前記システムが、請求項１ないし２３のいずれか１項に記載の方法を実行する、ことを特徴とする、請求項２７ないし３５のいずれか１項に記載のシステム。
【請求項３７】
ナビゲーションシステムであって、
目的地を入力する入力手段（６）と、
決定されたルートを出力する出力手段（７）と、
請求項２７ないし３６のいずれか１項に応じてルートを決定するシステム（２〜５）とを備え、
該システムは、そこから該目的地を受信する該入力手段（６）と、そこへ決定されたルートを出力する出力手段（７）とに結合されている、ナビゲーションシステム。
【請求項３８】
現在の車両位置を決定する位置決定手段（８）を備え、該位置決定手段（８）は、前記ルートを決定するシステム（２〜５）に結合され、該現在の車両位置を前記出発点として提供する、請求項３７に記載のナビゲーションシステム。
【請求項３９】
前記位置決定手段（８）が、ＧＰＳ受信機を備える、ことを特徴とする、請求項３８に記載のナビゲーションシステム。
【請求項４０】
交通メッセージ信号を提供する前記処理ユニット（２）に結合されたＴＭＣ受信機（９）、によって特徴づけられる、請求項３７ないし３９のいずれか１項に記載のナビゲーションシステム。
【請求項１】
道路網の出発点から目的地までのルートを決定する方法であって、
該方法は、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
該道路網の少なくとも一部分が含まれる地域をカバーするタイリング（Ｔ）を定義するステップと、
該タイリングの各タイルの抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数値を決定するステップと
を包含し、
所定のタイルの抵抗値は、該所定のタイルの境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表す、
方法。
【請求項２】
前記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルにおける前記道路網の幾何学的特性に関連して、該所定のタイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を接続するルート（１１、１３）に関連するコストを表す、ことを特徴とする、請求項１に記載の方法。
【請求項３】
前記所定のタイル（Ｔ０）の抵抗値が、該所定のタイルの境界に位置する一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する前記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連するコストの最小値である、ことを特徴とする、請求項３に記載の方法。
【請求項５】
前記タイル境界頂点（２３）に対して前記推定関数値を決定するステップが、
前記目的地（２２）を含む目的地タイル（Ｔ３）を決定するステップと、
該目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）と、該タイル境界頂点（２３）と、を接続する最適ルートに関連するコストの第１の下限を決定するステップと
をさらに包含する、ことを特徴とする、請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
前記第１の下限が、前記タイルの前記抵抗値に応じて、または前記タイリングの複数のタイルの前記抵抗値に応じて、決定される、ことを特徴とする、請求項５に記載の方法。
【請求項７】
前記第１の下限が、タイル境界のみに位置する頂点（２３〜２５）を含む前記道路網のサブグラフに対して、ダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、請求項６に記載の方法。
【請求項８】
任意のタイル（Ｔ２）の境界に位置する第１および第２の頂点（２３、２４）を接続するサブグラフのエッジ（２６ａ）に関連するコストが、該任意のタイルの抵抗値と、該第１および第２の頂点（２３、２４）のエアライン距離とから決定される、ことを特徴とする、請求項７に記載の方法。
【請求項９】
前記サブグラフのエッジ（２６ａ）に関連する前記コストが、前記第１および第２の頂点（２３、２４）のエアライン距離が乗算された前記任意のタイル（Ｔ２）の抵抗値に等しく設定される、ことを特徴とする、請求項８に記載の方法。
【請求項１０】
前記タイル境界頂点（２３）に対して前記推定関数を決定する前記ステップが、
前記目的地（２２）と、前記少なくとも一つの目的地タイル境界頂点（２４、２５）と、を接続する最適ルートに関連するコストの第２の下限を決定するステップと、
前記第１の下限と前記第２の下限とを加算するステップと
をさらに含む、ことを特徴とする、請求項５ないし９のいずれか１項に記載の方法。
【請求項１１】
前記タイル境界頂点（２３）に対して前記推定関数値を決定する前記ステップが、
すべての目的地タイル境界頂点（２４、２５）にわたる前記第１の下限と前記第２の下限との合計の最小値を決定するステップをさらに含む、ことを特徴とする、請求項１０に記載の方法。
【請求項１２】
前記タイル（Ｔ２）の前記境界に位置するタイル境界頂点（２３、２４）のための推定関数値からの該タイル（Ｔ２）の内側に位置する内側頂点（２９）のための推定関数値と、該内側頂点（２９）と該タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの下限と、を決定する、ステップによって特徴付けられる、請求項１ないし１１のいずれか１項に記載の方法。
【請求項１３】
前記内側頂点（２９）と前記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの前記下限が、該内側頂点（２９）と該タイル境界頂点（２３、２４）とのエアライン距離から決定される、ことを特徴とする、請求項１２に記載の方法。
【請求項１４】
前記内側頂点（２９）と前記タイル境界頂点（２３、２４）とを接続する最適ルートに関連するコストの前記下限が、該タイル境界頂点（２３、２４）が位置する前記タイルのエッジからの前記内側頂点の最小エアライン距離（２７’、２８’）から決定される、ことを特徴とする、請求項１２に記載の方法。
【請求項１５】
前記道路網の道路セグメントのコスト要因における増加を検出するステップと、
該コスト要因における検出された増加に応じて、該道路セグメントを含むタイルの抵抗値を増加させる、ステップとによって特徴づけられる、請求項１ないし１４のいずれか１項に記載の方法。
【請求項１６】
前記道路セグメントを含む前記タイルの抵抗値を増加させることが、乗法による、ことを特徴とする、請求項１５に記載の方法。
【請求項１７】
前記道路セグメントの前記コスト要因が、ユーザ入力に依存して増加する、ことを特徴とする、請求項１５または１６に記載の方法。
【請求項１８】
交通メッセージ信号を自動的に受信し、前記道路セグメントの前記コスト要因が該受信された交通メッセージ信号に依存して増加する、ステップによって特徴づけられる、請求項１５ないし１７のいずれか１項に記載の方法。
【請求項１９】
前記タイリング（Ｔ）のタイル（Ｔ１’、Ｔ２’、Ｔ１’’〜Ｔ６’’）のタイルサイズが、前記出発点と前記目的地からの増加する距離とともに増加する、ことを特徴とする、請求項１ないし１８のいずれか１項に記載の方法。
【請求項２０】
第１の抵抗値が、第１の規則的なタイリング（Ｔ’）の各タイルに対して提供され、
第２の抵抗値が、第２の規則的なタイリング（Ｔ’’）の各タイルに対して提供され、
前記地域をカバーする前記タイリング（Ｔ）が、該第１の規則的なタイリング（Ｔ’）のタイル（Ｔ１’、Ｔ２’）と、第２の規則的なタイリング（Ｔ’’）のタイル（Ｔ１’’〜Ｔ６’’）とを含み、該タイリングのタイルの抵抗値が、対応する該第１および該第２の抵抗値とそれぞれ等しい、ことを特徴とする、請求項１９に記載の方法。
【請求項２１】
前記タイリング（Ｔ）の各タイルに対して、第１の基礎抵抗値および第２の基礎抵抗値が提供され、これらの抵抗値が第１および第２の基礎コストモデルをそれぞれ表し、該第１および第２の基礎コストモデルの線形な組み合わせとして形成されるコストモデルに対して、該抵抗値の下限が、該第１および第２の基礎抵抗値の線形な組み合わせによって決定される、ことを特徴とする、請求項１ないし２０のいずれか１項に記載の方法。
【請求項２２】
前記出発点から前記目的地までの最適ルートが、前記タイリングのタイルの抵抗値に応じて決定される推定関数を使用するＡ＊−アルゴリズムを使用して決定される、ことを特徴とする、請求項１ないし２１のいずれか１項に記載の方法。
【請求項２３】
グラフ上の目的地へのルートを決定する方法であって、
該方法は、該グラフの複数の頂点のための推定関数を使用し、
該推定関数は、該グラフの頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該方法は、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該グラフの少なくとも一部分が含まれる、ステップと、
該タイリングの各タイルに対して抵抗値を提供するステップと、
該タイリングのタイルの抵抗値に応じて、タイル境界に位置するタイル境界頂点（２３）に対して推定関数を決定するステップと
を含み、
所定のタイルの抵抗値は、該所定のタイルの該境界に位置する頂点を接続するルートに関連するコストの下限が、該所定のタイルの抵抗値に基づいて導出可能であるように、該所定のタイルの境界に位置する該グラフの頂点を接続するルートに関連するコストを表す、方法。
【請求項２４】
道路網データを前処理する方法であって、
地域をカバーするタイリング（Ｔ）を定義するステップであって、該道路網の少なくとも一部分が含まれる、ステップと、
該タイリングのタイル（Ｔ０）に対して、該タイルの境界に位置する頂点（ｔｂｖ１〜ｔｂｖ４）を決定するステップと、
任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離によって分割される該タイルの境界に位置する該一対の頂点を接続する最適ルート（１１、１３）に関連するコストの下限を決定するステップと、
該決定された下限を出力するステップと
を含む、方法。
【請求項２５】
前記下限が、任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）の前記エアライン距離によって分割される前記タイルの境界に位置する該一対の頂点を接続するルートに関連する前記コストの最小値から決定される、ことを特徴とする、請求項２４に記載の方法。
【請求項２６】
前記下限が、出力の前に離散化される、ことを特徴とする、請求項２４または２５に記載の方法。
【請求項２７】
道路網の出発点から目的地までのルートを決定するシステムであって、
該システムは、該道路網の複数の頂点のための推定関数を使用し、
該推定関数は、該道路網の頂点と該目的地とを接続する任意のルートに関連するコストの下限を提供し、
該システムは、
道路網データを含む第１の格納ユニット（３）と、
タイリングを定義するタイリング定義データと、各タイルの抵抗値と、を含む第２の格納ユニット（４）と、
該タイリングの該タイルの該抵抗値に応じて、タイル境界に位置するタイル境界頂点のための推定関数を決定する処理ユニット（２）と
を備え、
該第２の格納ユニット（４）に含まれる、所定のタイルの該抵抗値は、該所定のタイルの該境界に位置する頂点を接続する該ルートに関連するコストの下限が、該所定のタイルの該抵抗値を使用して導出可能であるように、該所定のタイルの境界に位置する該道路網の頂点を接続するルートに関連するコストを表す、システム。
【請求項２８】
前記第２の格納ユニット（４）に含まれる、前記所定のタイル（Ｔ０）の前記抵抗値が、該所定のタイルの前記境界に位置する任意の一対の頂点（ｔｂｖ１〜ｔｂｖ４）を、一対の頂点のエアライン距離（１２、１４）に関連して接続する最適ルート（１１、１３）に関連する前記コストの下限であり、該ルートが該所定のタイルを横断する、ことを特徴とする、請求項２７に記載のシステム。
【請求項２９】
前記第２の格納ユニット（４）に含まれる、前記所定のタイルの抵抗値と、該所定のタイル（Ｔ０）の境界に位置する任意の一対のテスト頂点（ｔｂｖ１〜ｔｂｖ４）のエアライン距離（１２、１４）との積が、該所定のタイルの範囲内の該一対のテスト頂点を接続する最適ルート（１１、１３）に関連するコストの下限であるように、該所定のタイルの抵抗値が、該一対の頂点のエアライン距離によって分割される該所定のタイルの境界に位置する任意の一対の頂点を接続する該最適ルートに関連する前記コストの最小値である、ことを特徴とする、請求項２７または２８に記載のシステム。
【請求項３０】
前記処理ユニット（２）が、前記目的地（２２）を含む目的地タイル（Ｔ３）の境界に位置する少なくとも一つの目的地タイル境界頂点（２４、２５）を決定し、前記タイル境界頂点（２３）と該少なくとも一つの目的地タイル境界頂点（２４、２５）とを接続する最適ルートに関連するコストの下限を計算し、該下限が前記タイリングのタイルの抵抗値に応じて決定される、ことを特徴とする、請求項２７ないし２９のいずれか１項に記載のシステム。
【請求項３１】
前記下限が、前記目的地タイル境界頂点（２４、２５）を原点として有するダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムまたはＡ＊−アルゴリズムを使用して計算される、ことを特徴とする、請求項３０に記載のシステム。
【請求項３２】
前記タイル境界頂点（２３）の座標と、前記処理ユニット（２）によって決定される該タイル境界頂点（２３）のための前記推定関数値と、を格納するメモリユニット（５）、によって特徴づけられる、請求項２７ないし３１のいずれか１項に記載のシステム。
【請求項３３】
前記メモリユニット（５）が、前記タイルの境界によって規定される線に沿った前記タイル境界頂点（２３）の位置を指定する一次元的座標の形式において、該タイル境界頂点の該座標を格納する、ことを特徴とする、請求項３２に記載のシステム。
【請求項３４】
前記処理ユニット（２）が、前記道路網の道路セグメントのための交通メッセージ信号を受信し、該受信された交通メッセージ信号に応じて、該道路セグメントを含むタイルの抵抗値を変更する、ことを特徴とする、請求項２７ないし３３のいずれか１項に記載のシステム。
【請求項３５】
前記処理ユニット（２）が、前記タイリングのタイルの前記抵抗値に応じて決定されて前記メモリユニット（５）に格納された推定関数値を使用するＡ＊−アルゴリズムを使用して、前記出発点から前記目的地までの最適ルートを決定する、ことを特徴とする、請求項２７ないし３４のいずれか１項に記載のシステム。
【請求項３６】
前記システムが、請求項１ないし２３のいずれか１項に記載の方法を実行する、ことを特徴とする、請求項２７ないし３５のいずれか１項に記載のシステム。
【請求項３７】
ナビゲーションシステムであって、
目的地を入力する入力手段（６）と、
決定されたルートを出力する出力手段（７）と、
請求項２７ないし３６のいずれか１項に応じてルートを決定するシステム（２〜５）とを備え、
該システムは、そこから該目的地を受信する該入力手段（６）と、そこへ決定されたルートを出力する出力手段（７）とに結合されている、ナビゲーションシステム。
【請求項３８】
現在の車両位置を決定する位置決定手段（８）を備え、該位置決定手段（８）は、前記ルートを決定するシステム（２〜５）に結合され、該現在の車両位置を前記出発点として提供する、請求項３７に記載のナビゲーションシステム。
【請求項３９】
前記位置決定手段（８）が、ＧＰＳ受信機を備える、ことを特徴とする、請求項３８に記載のナビゲーションシステム。
【請求項４０】
交通メッセージ信号を提供する前記処理ユニット（２）に結合されたＴＭＣ受信機（９）、によって特徴づけられる、請求項３７ないし３９のいずれか１項に記載のナビゲーションシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図１３】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図１３】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【公開番号】特開２００７−３３３７３０（Ｐ２００７−３３３７３０Ａ）
【公開日】平成１９年１２月２７日（２００７．１２．２７）
【国際特許分類】
【出願番号】特願２００７−１２６９７５（Ｐ２００７−１２６９７５）
【出願日】平成１９年５月１１日（２００７．５．１１）
【出願人】（５０４１４７９３３）ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Ｆターム（参考）】
【公開日】平成１９年１２月２７日（２００７．１２．２７）
【国際特許分類】
【出願日】平成１９年５月１１日（２００７．５．１１）
【出願人】（５０４１４７９３３）ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Ｆターム（参考）】
[ Back to top ]