道路網動的適応ヒエラルキーおよびルーティングのための方法およびシステム
道路網でのルーティングを計算するためのシステムおよび方法が説明されている。１つの実施形態にはヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理する工程、道路交通状況に関するリアルタイムデータに対応してヒエラルキーにリンクを動的に追加する工程、およびリアルタイム道路交通データに基づいてルーティング移動コストを概算するクラスタ・ルーティングを行う工程を含む。さらなる実施形態には、ａ）道路網の１つ以上の部分をリアルタイムデータに基づいて普通よりも好適であると見なす工程、ｂ）道路網の１つ以上の部分を一意的に識別可能なパスを備えている位置のシーケンスとして表わす工程、ｃ）道路の既に構築されているヒエラルキー網に１つ以上のリンクを追加するために一意的に識別可能なパスを備えている位置のシーケンスを用いる工程、およびｄ）パス探索アルゴリズムがリアルタイムデータに順応できるようにする工程を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル地図データベース、および地理情報システム（ＧＩＳ）、ナビゲーション・システム（埋め込み型、ＰＤＡ、無線）、インターネット・アプリケーションなどを含めて、そのようなデジタル地図データベースを用いるシステム、および特に、道路網で最良のパスを求める検索を最適化するための技術に関する。
【先行技術文献】
【特許文献】
【０００２】
【特許文献１】米国特許第６，８８５，９３７号
【発明の概要】
【０００３】
本発明の実施形態には、道路網でルーティングを計算するためのシステムおよび方法を含む。実施形態には、ヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを前処理する工程、道路交通状況に関するリアルタイムデータに対応してヒエラルキーにリンクを動的に追加する工程、およびリアルタイム道路交通データに基づいて移動コストを概算するためにクラスタ・ルーティングを行う工程を含む。
【図面の簡単な説明】
【０００４】
本発明の実施形態は、以下の図に基づいて詳細に説明することとする。
【図１】出発地から目的地までのパス探索の例を示す図である。
【図２】双方向パス探索の例を示す図である。
【図３】パス探索に対する双方向の発見的方法の例を示す図である。
【図４】ノード間で道路優先順位のヒエラルキーを示す図である。
【図５】１つの実施形態の高位レベルのアーキテクチャ図である。
【図６】１つの実施形態に対する方法を示す流れ図である。
【図７】１つの実施形態に対する方法を示す流れ図である。
【図８】１つの実施形態に対する方法を示す流れ図である。
【図９】１つの実施形態に対する方法を示す流れ図である。
【図１０】１つの実施形態に対する方法を示す流れ図である。
【図１１】１つの実施形態に従って、１つ以上の構成要素を具体化するのに用いられる場合がある、コンピュータ・システム例のハードウェア・ブロック図である。
【発明を実施するための形態】
【０００５】
電子地図は、段階的に準備されることが多い。ある地域から別の地域へのパスが、事前に計算される場合がある。地域間パスを事前に計算することは、移動者が速い応答を望む場合応答時間を向上させる。この状況において、応答時間の向上はシステムの応答性が向上することを意味し、そして応答する時間がそれにより減少する。事前の計算は、パスに必要な計算が複雑で、そして込み入っている場合、特に有用である。
【０００６】
しかしながら、ある程度の計算がなお、走行時に要求に対応して行われる。これが、パス探索処理の一部が前もって計算され、そして地図アプリケーションに盛り込まれる処理をもたらす。その後、移動者が出発地および目的地を含む情報を入力し、そしてパス探索アプリケーションが、事前に計算された関連する経路を活用して、経路を決定する。
【０００７】
パス・アルゴリズムの変遷には、ダイクストラの最短パスを当然含むであろう。電子地図は有向グラフであり、ノード、および各リンクに割り当てられたコストを持つリンクの集成であるといえる。出発地と目的地との間の最小コスト・パスが、経路中のリンクの総コストを最小にするであろう。有向グラフでは、どの決定地点もノードであることができよう。あるノードから別のノードへのどの遷移もリンクである。パス探索処理に対する多くの最適化が、計算上の複雑さを減らし、そして応答時間を向上させることが可能である。
【０００８】
ダイクストラの本来の方法は、目的地が波面により覆われるまで波のような形状で出発地から検索が伝わる、一方向のパス検索である。ダイクストラのアルゴリズムは、単一起点の最短パス問題を解き、最短パスツリーを出力する。図１は都市部の道路の地図に渡って重ね合わされていて、そして出発地１００から目的地１０２に行くために経路が探し求められていると仮定する。最短パス問題にダイクストラのアルゴリズムを適用して、検索が四方八方に放射状に広がるであろう。パス探索処理が半径１０４に達する場合、パス探索処理は四方八方に探査してきたが、まだ目的地１０２を見つけていない。パス探索処理が半径１０６に達する場合、目的地１０２が見つけられている。
【０００９】
双方向の検索は、出発地と目的地との双方から、波が重なるまで伝わる検索を有する。双方向の検索は検索領域および計算時間を半分に減らす。２つの検索の各々は、複雑性Ｏ（ｂｄ／２）を有し、そしてＯ（ｂｄ／２＋ｂｄ／２）は出発地から目的地までの１つの検索の走行時間より少なく、１つの検索の走行時間はＯ（ｂｄ）であろう。図２には、出発地２００から目的地２０２に行くのに双方向検索を適用する例を示す。出発地２００からの検索２０４が目的地２０２からの検索２０６と交差する場合、最短パスが見つけられている。２００と２０２との間の距離は、１００と１０２との間の距離と同程度であるけれども、検索領域は双方向検索アルゴリズムでは半分の大きさである。
【００１０】
Ａ＊アルゴリズムは、検索を目的地に向かう探査を優先することに集中する。Ａ＊は、出発地ノードから目的地ノードまでの最小コスト・パスを見つけるグラフ検索アルゴリズムである。Ａ＊は、ノード・コスト、そしてこのようにして、検索がツリーにおけるノードを訪れる順序を決めるのに発見的機能を用いる。図３には、出発地３００から目的地３０２に行く双方向のＡ＊アルゴリズムを適用する例を示す。出発地３００からの検索３０４が目的地からの検索３０６と交差する場合、最短パスが見つけられている。３００と３０２との間の距離は、１００と１０２との間の距離と同程度であり、その上検索の領域は双方向Ａ＊アルゴリズムを用いると大幅に減らされている。
【００１１】
ヒエラルキーモデルはさらなる最適化を提供できる。ノードの優先順位がノードのルーティング（経路指定）重要度およびネットワークヒエラルキーにおける場所を説明する。パス探索アルゴリズムの最終目標はコストを最小限に抑えることである。リンクのコストは、時間、距離であることができ、または他の要因に係る。リンクには最適化基準に基づいてコストが割り当てられる。コストの分類体系は、道路、高速道路、小道、ドライブウェイ、ランプ、非ランプ、有料道路、渡し場、国境などを識別できるようにする、多くのレベルを有することができる。コストは、距離に距離辺りコストを乗ずることにより調整できる。リンクは同時に複数のコスト・クラスを有することができ、たとえば、ヒエラルキーモデルで高い優先順位に分類されることができ、そしてまたアクセスが制限されることもできよう。一部のコスト・クラス（有料道路、渡し場など）はさらなる制御を有する場合がある。検索はその場合、探査されるノードの最小コストにより動かされて、ノードからノードへ伝わる。
【００１２】
ＲＤＳ ＴＭＣ（無線データ・システム−道路交通メッセージ・チャネル）は、ＦＭ無線でＲＤＳ副搬送波によって道路交通データを同報するための、世界的に認知された規格である。データはＴＭＣ規格に従って符号化され、そして移動者の位置および／または経路に関連する情報を提供するために、マッピング・システムにより復号される。
日本は道路交通情報通信システム（ＶＩＣＳ）を開発している。ＶＩＣＳは、路車間情報システム（ＲＡＣＳ）と新自動車交通情報通信システム（ＡＭＴＩＣＳ）との競合を解決し、そして双方の最良の特徴を用いる共通のシステムを規定することを最終目標とするプログラムである。１つの提案は、それぞれの各システムにより用いられているツールを本質的に結合させて、両方向の路車間通信および位置情報を提供する、デジタル・マイクロ・セルラ無線システムである。ＲＡＣＳタイプ１ビーコンおよび、（無線データ・システム−道路交通メッセージ・チャネル（ＲＤＳ−ＴＭＣ）のような）ＦＭカー・ラジオによる運転者への情報の同報を用いるＲＡＣＳ−ＡＭＴＩＣＳが、別の選択肢である。
【００１３】
国際標準化機構（ＩＳＯ）は、規格ＩＳＯ１７５７２−３高度道路交通システム−地理データベースのための位置参照−第３部：動的位置参照を創出していて、この規格はまたＡＧＯＲＡ−Ｃとしても知られる。この規格は、規模効率およびロバストな自律的複号化のために最適化されたマシン同士の位置表現をサポートするように設計されている。動的方法として、ＡＧＯＲＡ−Ｃは復号時に地図の版間の差異を予測する。ＡＧＯＲＡ−Ｃ規格は、ＴＭＣの置き換えを含めて、拡張ナビゲーション・サービスの進展を認めるように設計されている。ＡＧＯＲＡ−Ｃは、所定の位置コードまたは参照表を必要とすることなく、販売業者または版に係らず、位置参照を動的に符号化し、そして位置参照を任意の地図に復号するための方法を仕様化する。位置参照は、道路の合流点、出口ランプ、および郵便配達用住所のような地理的対象物の一意的な識別である。
【００１４】
道路交通流を明らかにするために、大抵の商用システムは、地図データ提供業者とアプリケーション提供業者との間で共有される政府規格または企業規格のいずれかである位置識別子によって、道路エンティティを参照する所定の位置コード集合に依存する。データ流に影響する道路交通事象は通常、ＴＭＣの書式（ＵＳおよびヨーロッパ）またはＶＩＣＳ（日本）によって記述される。事前に割り当てられた位置コードの必要性が必然的に、そのようなシステムを最も重要な交差点での位置の比較的小さな部分集合に制限する。大抵のルーティング・エンジンは、動的に修正された少量のデータに対処することができる。一部のルーティング・エンジンは最初にパスを計算し、それから道路交通事象が通知または再計算の正当な理由になるかどうかを決定するために調べる。
【００１５】
限られた位置表を同期させ、そして維持するためのコストは、道路交通提供業者が、厳選したＴＭＣセグメントだけでなく、ネットワーク全体に対して、過去にあったプローブ・データおよび、所与の週日、日付、および時間間隔で所与のリンクに対する速度パターンを予測することができるアルゴリズムを蓄えるにつれて、益々魅力がなくなる。ＩＳＯがＡＧＯＲＡ−Ｃに基づく位置参照規格の最初の草案を承認するに伴って、動的位置参照で、また進展がなされてきた。
【００１６】
ＡＧＯＲＡ−Ｃ、ＶＩＣＳ、およびＲＤＳ／ＴＭＣは、動的位置参照規格の例である。他の基準が熟慮されている。本発明の実施形態は、位置参照方法により提供される動的データを利用する。本発明の実施形態は本明細書で説明される位置参照規格に限定されない。
【００１７】
リアルタイム道路交通データはその大きさが増加しそうであり、そして現行のアルゴリズムが妥当な時間でデータを効率よく処理できなくなるような限度まで拡大しそうである。近い将来、センサーがこれまでよりも多数の道路での道路交通状況に関するデータを送信しているであろう。ナビゲーション・システムのための全地球測位システム（ＧＰＳ）および拡張位置決定システムは、車がその位置を決定できるようにするばかりでなく、両方向通信を活用して、道路交通データ提供業者がそのような装備をしている車の位置を決定し、そして車に影響を及ぼすその時点の道路交通状況を決定できるようにするであろう。（ＩＮＳ、推測航法などを含むことができることになる）ナビゲーション・システムに１つよりも多くのＧＰＳ受信機がある可能性がある。また、ＧＰＳ以外に、現在またはまもなく利用できる他の全地球航法衛星システム（ＧＮＳＳ）がある。
【００１８】
本発明の一部の実施形態は、交通事故および抗議行動のような事象を含めて、またルーティングに影響を及ぼす場合があるリアルタイムデータをパス探索が考慮できるようにする。大きなプラットホーム、小さなプラットホーム、および埋め込みプラットホームでのルーティング・アルゴリズムは、この極めて多量の動的コスト・データを効率よく用いることができるであろう。本明細書で説明されるルーティング・アルゴリズム技術の一部の実施形態は、高速ルーティングを可能にしたまさしくそのものである、地図データヒエラルキーおよび双方向集中検索を伴う問題、完全に動的なリンク通過の膨大なコストのために生じる問題を解決する。
【００１９】
リンク・コストはルーティング・アルゴリズムに必須である。共通の最終目標は、最短移動時間を計算することである。検索が道路網での最短移動に対して最適化される場合、リンク・コストは、かかるリンクでの移動時の通過速度またはかかるリンクを通過するに要する時間で表わされることができる。リンクは２つの決定地点間での道路のセグメントとして定義される。ノードは道路網で特定のリンクから到達する決定地点である。
【００２０】
道路は重要度、スループットおよび制限速度の点で異なるので、道路網は自然的なヒエラルキーを形成する。多くのルーティング・アルゴリズムは、移動距離および道路網の細部の状況に相応しい詳細度を保つために、この潜在的なヒエラルキーに依存している。重要性の劣った道路が、ある距離を移動するパスを計算するためにより重要な道路間の近道として役立つ場合もあるため、自然的な道路ヒエラルキーはルーティングには不完全であることが多い。高度なルーティング・データベース・アプリケーションは、パスを計算するのにグラフのごく一部だけを処理すればよいように、走行時間性能のためにヒエラルキーを事前に計算できる。
【００２１】
事前に計算されるルーティングヒエラルキーのための並列プロファイル
コストが移動速度に対して最適化される場合、ルーティング・アルゴリズムは、ルーティング・アルゴリズムの観点から残った道路が信号のない高速道路だけになるまで、ルーティング・アルゴリズムが徐々により重要な道路を好んで出発地および目的地から遠ざかるように伝わるので、重要度のより低い道路を放棄する傾向がある。目的地が遠ければ遠いほど、信号のない高速道路でのマイル距離の割合が高くなる。事前に計算されるヒエラルキーは、好都合なことに、道路のまさに適切な部分集合の検索を可能にする。事前に計算されるヒエラルキーは移動速度が道路の重要度とともに増すことを仮定している。
【００２２】
たとえば、朝の通勤は道路での道路交通流を渋滞させ、一方午後の通勤では高速に移動することが可能となる。同様に、混雑した道路に通じるまたは遠ざかる道路は、ある方向には影響されるが、その反対方向には影響されない場合がある。さらに、ヒエラルキーが道路に対する最高速度制限に基づいて構築されると、結果は必ずしも満足いくとは限らないであろう。
【００２３】
事前に計算されたデータがリレーショナル・データベース管理システム（ＲＤＢＭＳ）に記憶される場合、道路網のほんの一部を代表する高速道路は、性能を位大きく影響することなく更新できる。しかしながら、走行時に優先順位の低い道路を奨励することは、低いレベルにある非常に多くの道路のために、大規模な設備を考慮しても難しくなる可能性があって、性能への影響はシステムにはとても大きいだろう。
【００２４】
厳しい道路交通状況の下で、一部のシステムは、応答時間および、秒当たりに計算されるパスの数にマイナスの影響を与える、ツリーの上位レベルを用いないように決めており、一方商用車運営会社は“定期的”な通勤、“朝”の通勤、“午後”の通勤に対して異なるルーティング・データベースを維持する場合がある。
【００２５】
道路交通事象は、地図アプリケーションに対して事前に計算された典型的なヒエラルキーでは効率的に処理できないような、大量の動的リンク・コストを生成することがある。本発明の１つの実施形態は、動的適応ヒエラルキーの方法を用いてこの問題を解決する。
【００２６】
特許文献１は、ヒエラルキールーティング・アルゴリズムがより効率的になるように、高位レベルでデジタル地図を追加のリンクで増大させる近道ジェネレータを記載している。典型的なヒエラルキールーティング・アルゴリズムの例が図４に示されている。車道４００が最も高い優先順位を有しており、そして高速移動を可能とする、信号のない高速道路である。車道４０２、車道４０４、および車道４０６は、中間の優先順位を有し、そして中間の速度を許可する。地方道路４０８、４１０、４１２、４１４、４１６、および４１８は、停止信号、一時停止標識、および望ましさを減らす他の難事を有する道路である。ヒエラルキーの高位レベルでは、優先順位の低い道路がなくなるので、優先順位の高いノード間のリンクは益々遠距離にわたる。経路が長距離にわたるように意図されると、パス検索アルゴリズムは車道４００、４０２、４０４、および４０６を考慮するが、地方道路４０８、４１０、４１２、４１４、４１６、および４１８を考慮しないことにより最適化する場合がある。特許文献１に記載されている近道ジェネレータは、地方道路が優先順位の高い２つの道路間の望ましい近道であると、パス探索検討に対して、地方道路が優先して奨励されるようにする。たとえば、地方道路が２つの高速道路をつなぐと、近道ジェネレータは、地方道路がパス検索アルゴリズムにより考慮されるように奨励する場合がある。
【００２７】
他の地図ヒエラルキーと同様に、静的道路分類での近道ジェネレータ方法は、地図提供業者が仮定した速度制限と、使用時に所与のリンクに対する実際の速度または予測速度との間でコストに予測できない差異がある場合、あまりうまく機能しない。これらの予測できない差異に関する２つの主な原因がある。
【００２８】
経路が計算されるときのリンク・コストは、その時点の実際の道路交通、過去の顕著な道路交通パターン、または予測された道路交通情報によって、データが構築された当時に仮定されていたリンク・コストと異なる場合がある。
【００２９】
高い優先順位が付与されている道路は、実際には、危険物積載トラックに禁止される場合があり、それで禁止された道路を含むパスは、特定の車には役に立たないであろう。時間制限または車両制限に関する別の例は、ＨＯＶレーンに対してである場合があり、ＨＯＶレーンは、ある車に対して一日のある時間帯で利用できるだけである。
【００３０】
本発明の実施形態はこれらの問題への解決策を提案する。上述の特許で記載されているように、近道ジェネレータを一度だけ実行する代わりに、本発明の実施形態は、近道ジェネレータを何度も、そのたびに異なる“プロファイル”を用いて実行する。第１のプロファイルは、コストに修正を加えていない標準のプロファイルである。１つの実施形態では、環境プロファイルは動的パラメータ、ユーザ・パラメータ、および／または環境パラメータに基づいている。
【００３１】
過去にあった道路交通に対して、変化率が有意でない時間間隔は数少ないプロファイルに圧縮され、それから近道ジェネレータが、どれ程多くのプロファイルが望まれるかによって、妥当な時間セグメントの各々に対して実行される。１つの例では、１０個のプロファイルが、朝のラッシュアワー道路交通プロファイル、夕方のラッシュアワー道路交通プロファイル、週日の平坦な時間帯の道路交通プロファイル、週末の道路交通プロファイル、および他の典型的なプロファイルをカバーするように作成される。１つの実施形態は、各曜日の半時間の期間ごとに対してプロファイルを作成する。プロファイルは、それから類似性に基づいて比較され、そしてより小さいプロファイルの集合に統合される。環境プロファイルに対する時間スロットは、時間スロットが周期的（１時間、半時間、１５分など）であれ、または周期的でなかろうと（真夜中から６時、６時から１０時、１０時から午後３時、午後３時から午後７時など）、任意であることができる。
【００３２】
代わりの実施形態では、物流プロダクトが作り出される。この実施形態では、第１のプロファイルは標準的なコストを有し、そして制限がない。第２のプロファイルは、トラックが禁止されている、または許可されないすべての道路である。第３のプロファイルは危険物が禁止されている、または許可されないすべての道路である。ビジネス・ロジックが必要とするだけのさらなるプロファイルが、創出されるであろう。
【００３３】
一般に、プロファイルが多ければ多いほど、アルゴリズムによりもたらされる解答がより正確になる。事例の大部分を扱うには１０個以上のプロファイルを取り上げるべきではない。特定の状況がプロファイルと正確に合致しなくても、ヒエラルキーの豊富さが良好な対案を提供する可能性がある。１つの実施形態が、動的パラメータ、ユーザ・パラメータ、および環境パラメータを単一のヒエラルキーに統合する場合がある。
【００３４】
一旦近道ジェネレータが別々のプロファイルを構築すると、次の工程はプロファイルのすべてを１つの最終結果にまとめることである。これが行われる方法は、どのノードも、プロファイルすべての中で有する最高の優先順位の値を有することであり、そして複合リンク（単体リンクの集約）がプロファイルのどれかに存在すると、その場合複合リンクはまた最終結果に存在する。複合リンクは、新しい優先順位を持つ１つ以上のリンクを表わす場合がある。これらの複合リンクは近道ジェネレータにより生成された近道を表わす。多くのファイルは事実上、同じリンクを奨励するので、意図した結果は、近道ジェネレータによって実行されなかったプロファイルでさえ、その結果をうまく表されるよい機会を有することである。
【００３５】
最終結果は、まだ１０個の異なる状況として用いられる、１０個全体の状況を効率的に記憶する単なる方法ではなく、道路交通状態の特質に係らず、ネットワークは事前に構築された近道のすべてを有するので、むしろ最終結果は、効率的なルーティングが一日中いつでも行われることができるように、十分な複雑性を持つ１つのデータベースである。その場合、システムはまだ、（上位レベルで）合理的に疎なネットワークを有するが、そのネットワークは“混雑中の道路交通”選択肢に必要な近道を含むのに十分な密度を有する。その場合、動的な道路交通は、ヒエラルキーを再構築する必要がなく、（効率的に）リアルタイムでのリンク重みとして用いられることができる。
【００３６】
一部の他企業の解決策は、静的データで得たヒエラルキーの最高位のレベルへの奨励を無効にして、これらのレベルが道路交通事象により非効率な状態にされる場合、ルーティング不成功を引き起こす。これらの代替手法は、本発明の実施形態の手法の下で必要である以上に、考慮されなければならないリンクの数を大きくする。本発明の実施形態は二重の改善を提供しており、実施形態は、高位レベルでのルーティング検討に利用できる低位レベルのリンクの数を実現できるものだけに制限し、一方また低位レベルのリンクをヒエラルキーの所与のレベルに相応しいようにより長い一続き（複合リンク）に集約する。
【００３７】
１つの実施形態で、同じアルゴリズムが、料金所／渡し場／国境の通過回避、道路交通制限に対する複数の車両プロファイル、および／またはそのような動的パラメータ、ユーザ・パラメータ、または環境パラメータの組み合わせによって、複数のリンク・コストに対するルーティングヒエラルキーを強化するのに適用される。
【００３８】
動的適応ヒエラルキー
道路公社または動的状況が、ヒエラルキーの適当なレベルに存在しない迂回路を提案する場合がある。たとえば、道路交通が一時的に、建設または緊急の現場をバイパスするための方法として地方道路に迂回できよう。ルーティング・システムの１つの実施形態は以下のやり方でヒエラルキーを動的に調整する。
【００３９】
１つの実施形態で、道路のヒエラルキー網を記述する情報がデータベースに格納される。データ提供業者は、特定の時間に通常の場合より好適である場合がある道路のヒエラルキー網の一部を識別でき、そして道路のヒエラルキー網を一意的に識別可能なパスを備えている位置のシーケンスとして表現できる。道路のヒエラルキー網のこれらの部分はそれから、１つのリンクまたは複数のリンクとして、走行時に道路のヒエラルキー網に追加される。１つの実施形態で、道路交通状況に関するリアルタイムデータは、外部情報源により（ＲＤＳ ＴＭＳ、ＡＧＯＲＡ−Ｃ、ＶＩＣＳまたは同様な道路交通情報システムを通して）供給される。
【００４０】
１つの実施形態で、動的適応ヒエラルキーは走行時に事前に計算されたヒエラルキーに新しいリンクを追加することに係る。構築時に、ネットワーク・ビルダーは相互参照表を生成し、相互参照表は道路交通データ提供業者により用いられる最終のネットワークＩＤを、ルーティング・ソフトウェアにより用いられる道路網ＩＤに（リンクおよびノードの双方に対して）対応付ける。１つの実施形態で、この相互参照データは高速ランダム・アクセスを持つデータベースに格納される。走行時に、リアルタイム道路交通情報が迂回路を必要とする場合、この情報は、現存するネットワークにおけるどのノードが修正される必要があるかを識別するのに用いられる。単一の迂回路は、適当な優先順位を備えており、そして各レベルに相応しいように構成される、ヒエラルキーの異なるレベルで追加される複数のリンクをもたらすことができる。これらの新しいリンクは既に存在しているリンクと全く同じやり方でルーティング・アルゴリズムに供給され、このようにして、ルーティング・アルゴリズムは修正される必要がない。
【００４１】
ＡＧＯＲＡ−ＣはネットワークＩＤｓを有しないが、その代わりに道路要素の多少自由な形式の記述／参照に依存する。ＡＧＯＲＡ−Ｃおよび同様な参照システムに対して、相互参照表は作成できない。その代わりに、影響を受ける形状がリアルタイム復号処理により識別されなければならない。
【００４２】
これらの新しいリンクは、動的データに基づいて、パス探索アルゴリズムが、迂回路を必要とするリアルタイム道路交通事象に順応できるようにする。同じ方法が、１つ以上のプロファイルをヒエラルキーの既に存在する枝に漸次まとめることができるようにし、１つ以上のプロファイルが、ネットワークの大部分が自然災害または何らかのそのような事象によって通過時間を修正している場合に、必要となる場合がある。
【００４３】
双方向集中ルーティング
双方向ルーティングは、伝搬領域（およびこのようにしてノードの数および計算時間）をおおよそ半分に減らすために採用される。集中ルーティングはさらに、出発地または目的地に向かう伝搬を優先することにより検索領域を減らす。ダイクストラ最短パス・アルゴリズムでは、波面での最小コスト・ノードは、移動時間を最適化する場合に、最適パスが既に見つかっているということと、それに従って波の出発地からの到着時間も既に見つかっているという特徴がある。集中Ａ＊では、波面でのノード・コストは、波の中心からノードまでの移動コストと、反対側の波面の中心までの、通常何らかの発見的方法を用いて計算される推定コストとの合計である。どの工程でも最小コスト・ノードからの伝搬は、最小コスト・パスを見つけるのに必須である。
【００４４】
移動時間依存のリンク・コストは伝搬に対する問題を提起しており、出発地から目的地波面上のかかるノードまでの最良パスがまだ見つかっていないので、最良パスのコストおよびノードに到着する時間は未知であり、したがって正確なリンク・コストが確認できない。たとえば、経路が午後３時３０分に出発地を離れるように計画されていると、出発地近くの道路交通状況は、出発地を離れる波面を計算するために過去にあったデータに基づいて予測できる。しかしながら、パス探索処理はまだ完了していないので、目的地から広がる波に対するコストを計算する場合、目的地近くの道路交通状況に対してどの時間を用いるかは未知である。
【００４５】
従来のアルゴリズムは、コスト値が一定である静的グラフ上で行われる。従来のアルゴリズムは、これらのコストの動的性質を無視していたのでより効率的であった。時間依存のコスト値を考慮するより大きな静的グラフを創出することにより、Ａ＊アルゴリズムを時間依存のリンク・コストと連携するように修正することができる。しかしながら、そのような修正されたグラフの量は、元の静的グラフと大きさが１００倍ぐらい違うだろう。結果として、経路を計算する計算時間は、それに応じて受け入れ難いほどに増加するであろう。
【００４６】
問題を解決する別の方法は、短いパスに対して機能する可能性がある、ノードに到着する最小最大の時間間隔、およびこれらの間隔に対する平均リンク・コストを確認することであろう。混雑中の道路交通状況にあるより長いパスは不当に大きな間隔を有し、そしてより信頼できる手法を必要とする場合がある。
【００４７】
クラスタ・コスト近似法
静的手法に反して、１つの実施形態は、常に変化する道路交通状況の下で、合理的に迅速に妥当なパスを強いるようにしながら、動的ルーティングを近似の役割として認める。
【００４８】
１つの実施形態はルーティング・ネットワークを論理的なクラスタに分割することから始まる。どの方法がかかることのために用いられるかは、この議論には重要でない。１つの実施形態では、四分ツリーが利用される。簡単にするために、平方マイル当たりの道路密度、交通渋滞、移動頻度、または同様な基準の関数として、細分基準を持つ論理的なクラスタツリーを仮定する。代替の実施形態は、空間的指標で典型的な同様の基準を用いる。各クラスタは空間的な広がりを有し、そして隣接するクラスタへの移動時間を記憶して、移動時間は過去にあったデータまたは予測データから事前に計算され、および／またはリアルタイムデータ・プローブから動的に維持される。これは、移動時間に依存するコストを用いてクラスタ・ルーティングを行うためにクラスタに対する簡略化したグラフを生み出す。
【００４９】
１つの実施形態で、ナビゲーション・システムは、ナビゲーション・システムを備えた車が道路を通過して移動するのにどれぐらい時間が掛かるかを計算できる。ネットワークは、走行時プローブ・データから車が地図を横切るのにどれぐらい時間が掛かったかを承知している。地図がクラスタに分けられる場合、クラスタからクラスタに移動する複数の車からの走行時プローブ・データに基づいて、あるクラスタから別のクラスタに行くのにどれぐらい時間が掛かるようになるかが推定できる。
【００５０】
パスの出発地ノードが出発地クラスタと呼ばれるクラスタに存在し、そしてパスの目的地ノードが目的地クラスタに存在する。一部の実施形態では、このグラフの大きさが極めて小さいために、一方向ダイクストラ・アルゴリズムが、このクラスタ・グラフでパスを計算するのに用いることができる。道路網グラフにおける各ノードが何らかのクラスタに入るので、この計算からの結果は、ノードのクラスタと反対側の波面の中心が属するクラスタとの間で、移動方向における概算の時間を与えるであろう。
【００５１】
目的地の波面で、この値がノードに到着する推定時間の代わりに用いられ、同様に適切なリンク・コスト値の選択を可能にするであろう。その場合、ノードから反対側の波面の中心までのコストを、ノードのクラスタから反対側の波面の中心が属するクラスタまでのルーティング方向における移動の概算コストにより推定するために、発見的方法が代わりに用いられる。相対する波面からのノードが繋がる場合、対象の波での概算コストが、出発地からの実際のパスの新しく計算したコストにより代用される。
【００５２】
双方向Ａ＊アルゴリズムの残り部分が従来どおりに継続するであろう。
【００５３】
サーバにおいて、多くの異なるパス要求が同じ出発地クラスタおよび同じ目的地クラスタを有する場合、クラスタ・ルーティングの結果（すなわち、クラスタからクラスタまでのコスト）が地域内クラスタ間のコストの一部が変わってしまうまで、再使用できよう。
【００５４】
図５は１つの実施形態の高位レベルのアーキテクチャを示す。元の電子地図データ５００が環境プロファイル５０２を用いてヒエラルキーの中で事前に処理される。１つの実施形態で、ルーティングヒエラルキーが近道ジェネレータにより何度も処理される。１つの実施形態で、１０個のプロファイルが朝のラッシュアワー道路交通、夕方のラッシュアワー道路交通、平坦な時間帯の週日道路交通、週末道路交通、およびその他のプロファイルをカバーするように作成される。その後、プロファイルは最終結果にまとめられ、増強された地図データ５０４を生み出す。その後、増強された地図データはパス探索システム５１０に配信される。リアルタイム道路交通状況に基づいて道路網のいずれのリンクおよびノードを修正すべきかを決定するために、リアルタイム道路交通データ５０６が位置の好適な連続５０８を生成するのに用いられる。パス探索システム５１０はそれから、経路５１２を計算するために、並列プロファイルを持つ増強された地図データおよび、クラスタ・コスト近似法で動的に更新されるリンクを用いる。
【００５５】
図６は、１つの実施形態に対する流れ図を示しており、道路網でルーティングを計算するための方法である。本方法には、ヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理する工程６００を含む。本方法には、道路交通状況に関するリアルタイムデータに対応してリンクをヒエラルキーに動的に追加する工程６０２を含む。本方法には、リアルタイム道路交通データに基づいてルーティング移動コストを概算するために、クラスタ・ルーティングを行う工程６０４を含む。
【００５６】
図７は１つの実施形態に対する流れ図を示しており、道路網でルーティングの計算を改善するための方法である。本方法には、ヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理する工程７００を含む。本方法には、１つ以上の環境プロファイルに対する近道を計算する工程７０２を含む。本方法には、１つ以上の環境プロファイルに対する近道をデータベースにまとめる工程７０４を含んでおり、ノードはデータベースにまとめられた１つ以上の環境プロファイルの中で、ノードの値の最高の優先順位を有する。本方法にはさらに、「複合リンクが１つ以上の環境プロファイルにある場合、複合リンクはまた、データベースにある」という工程７０６を提供する。
【００５７】
図８は１つの実施形態に対する流れ図を示しており、既に構築されている道路のヒエラルキー網に新しいリンクを動的に追加するための方法である。本方法には、道路網の１つ以上の部分を、リアルタイムデータに基づいて通常よりも好適であると識別する工程８００を備える。本方法には、道路網の１つ以上の部分を、一意的に識別可能なパスを備える位置のシーケンスとして表わす工程８０２を含む。本方法には、既に構築されている道路のヒエラルキー網に１つ以上のリンクを追加するために一意的に識別可能なパスを備えている位置のシーケンスを用いる工程８０４を含む。本方法には、パス探索アルゴリズムがリアルタイムデータに順応できるようにする工程８０６を含む。
【００５８】
図９は１つの実施形態に対する流れ図であり、道路網で車両ナビゲーションの計算を改善するための方法である。本方法は、道路網を論理的なクラスタツリーに分割する工程９００を含む。本方法は、各クラスタに対して隣接するクラスタへの移動時間を記憶する工程９０２を含む。本方法は、ノードから反対側の波面の中心までの移動に関するコストを推定するための発見的方法の代わりに、ルーティングの方向でのノードのクラスタと反対側の波の中心のクラスタとの間の移動に関する概算コストを用いる工程９０４を含む。本方法は、目的地の波面ノードから伝搬している各リンクに対するコストを、かかるノードでのクラスタ近似による到着時間に基づいた時間間隔から計算する工程９０６を含む。本方法は、相対する波面からのノードが繋がる場合、対象の波での概算コストが、出発地からの実際のパスの新しく計算されたコストにより代用される工程９０８を含む。
【００５９】
図１０は１つの実施形態に対する流れ図を示しており、道路網で車両ナビゲーションの計算を改善するための方法である。本方法は、道路網を四分ツリーに分割する工程１０００を含む。本方法は、各四分ツリーに対して隣接する四分ツリーへの移動時間を記憶する工程１００２を含む。本方法は、ノードから反対側の波面の中心までのコストを推定するための発見的方法の代わりに、ルーティングの方向でのノードの四分ツリーと反対側の波の中心の四分ツリーとの間の移動の概算コストを用いる工程１００４を含む。本方法は、目的地の波面ノードから伝搬している各リンクに対するコストを、かかるノードでの四分ツリー近似による到着時間に基づいた時間間隔から計算する工程１００６を含む。本方法は、相対する波面からのノードが繋がる場合、対象の波での概算コストが、出発地からの実際のパスの新しく計算されたコストにより代用される工程１００８を含む。
【００６０】
図１１は典型的な処理システム１１００を説明しており、図５の要素の１つ以上を備えることができる。他の代替が利用される可能性があるが、図５のシステムの構成要素は、ハードウェア、ソフトウェアまたは、他に指示がなければ、これらと調和する１つ以上の計算システムによる何らかの組み合わせに実装されると考えられるであろう。
【００６１】
計算システム１１００は、１つ以上の汎用プロセッサまたは専用プロセッサ１１０２を含めて、１つ以上の通信チャネル（たとえば、バス１１０１）を通して結合される構成要素、たとえばペンティアム（登録商標）、セントリーノ（登録商標）、パワーＰＣ（登録商標）、デジタル信号プロセッサ（“ＤＳＰ”）、などを備える。システム１１００の構成要素にはまた、特定のアプリケーションに従って、１つ以上の入力装置１１０３（たとえば、マウス、キーボード、マイクロフォン、ペンなど）、および１つ以上の出力装置１１０４、たとえば相応しいディスプレイ、スピーカ、アクチュエータなどを含む。（当然のことながら、入力装置または出力装置はまた同様に、精神的または身体的な不自由者が用いるのに相応しいように機能が強化された、より特殊化した装置またはハードウェア／ソフトウェア装置を含むことができる）。
【００６２】
システム１１００はまた、コンピュータで読み取り可能な記憶媒体１１０６、たとえば記憶／メモリ装置またはハード、または取り外し可能な記憶／メモリ媒体に結合されたコンピュータで読み取り可能な記憶媒体読み取り装置１１０５を含み、そのような装置または媒体はさらに、別々に記憶１１０８およびメモリ１１０９として示され、特定のアプリケーションの要求条件に従って、ハードディスク系、フロッピー（登録商標）／コンパクト・ディスク系、デジタル多用途ディスク（“ＤＶＤ”）、スマート・カード、リード・オンリ・メモリ、ランダム・アクセス・メモリ、キャッシュ・メモリ、などを含む場合がある。直接に、または１つ以上の相応しい私設網または公衆網または既に論じたものを含むがこれらに限定されない場合がある他の構成要素を通して装置間通信を提供するために、１つ以上の相応しい通信インタフェース１１０７、たとえばモデム、ＤＳＬ、赤外線、ＲＦまたは他の相応しい送受信機などがまた含まれる場合がある。
【００６３】
作業用メモリ１１１０はさらに、使用中にそのなかに記憶される、または読み込まれる可能性がある、システム１１００の構成要素を実装するために、オペレーティング・システム（“ＯＳ”）１１１１要素および他のプログラム１１１２、たとえば、アプリケーション・プログラム、モバイル・コード、データなどのうちの１つ以上を含む。特定のＯＳまたは複数のＯＳが、特定の装置、特徴または特定のアプリケーションに従った他の態様に従って変わる場合がある（たとえば、ウィンドウズ（登録商標）、ウィンドウズＣＥ（商標）、マック（商標）、リナックス、ユニックスまたはパーム（商標）ＯＳ系、セル電話ＯＳ、独自ＯＳ、シンビアン（商標）など）。特定のアプリケーションの要求条件に従ってたとえば、Ｃ系（たとえば、Ｃ＋＋、Ｃ＃）、ジャバ（商標）２プラットホーム、エンタープライズ・エディション（“Ｊ２ＥＥ”）または他のプログラム言語と互換性のある、様々なプログラミング言語または他のツールがまた利用できる。他のプログラム１１１２はさらに、本明細書のいずれかで論じたものを含むがこれらに限定されずに、たとえば、活動システム、教育マネージャ、教育インテグレータ、またはインタフェース、セキュリティ、他の同期、他のブラウザまたはグループウェア・コードなどのうちの１つ以上を含む場合がある。
【００６４】
実施形態には、本開示の教示に従ってプログラムが組まれた、従来の（複数の）汎用コンピュータまたは（複数の）専用デジタル・コンピュータまたは（複数の）マイクロプロセッサを用いて実装される場合がある、コンピュータを使った方法およびシステムを含むことができる。適切なソフトウェアのコーディングは、本開示の教示に基づいてプログラマにより容易に準備できる。
【００６５】
実施形態には、コンピュータで読み取り可能な媒体、たとえばコンピュータで読み取り可能な記憶媒体を含むことができる。コンピュータで読み取り可能な記憶媒体は、本明細書で提示した特徴のいずれかを行うようにコンピュータをプログラミングするのに用いることができる命令を記憶しておくことができる。記憶媒体はまた、フロッピー・ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロ・ドライブおよび光磁気ディスクを含むいかなるタイプのディスク、ＲＯＭｓ、ＲＡＭｓ、ＥＰＲＯＭｓ、ＥＥＰＲＯＭｓ、ＤＲＡＭｓ、フラッシュ・メモリ、または命令および／またはデータを記憶するのに相応しい任意のメディアまたはデバイスを含むことができるが、これらに限定されない。本発明には、コンピュータ、たとえば汎用／専用の（複数の）コンピュータまたは（複数の）マイクロプロセッサのハードウェアを制御するための、およびこれらのコンピュータがヒューマン・ユーザまたは、本発明の結果を利用する他のメカニズムと情報をやり取りできるようにするためのソフトウェアを含むことができる。そのようなソフトウェアには、デバイス・ドライバ、オペレーティング・システム、実行環境／コンテナ、およびユーザ・アプリケーションを含む場合があるが、これらに限定されない。
【００６６】
実施形態には、処理を実装するためのコードを提供する工程を含むことができる。提供工程には、どんな方法によってもユーザにコードを提供する工程を含むことができる。たとえば、提供工程には、物理メディアでコードをユーザに提供することを含み得、またはコードを使用できるようにする他の任意の方法を提供する工程を含むこともできる。
【００６７】
実施形態は、実施形態の処理のいずれかを行うようにコンピュータで実行できるコードを送信するための、コンピュータに実装される方法を含むことができる。送信には、ネットワークの任意の部分、たとえば、インターネットを介する送信、有線送信、または他のどのような種類の送信をも含むことができる。送信には、コードの送信を開始する工程、または任意の地域または国から別の地域または国にコードを通すようにさせる工程を含むことができる。ユーザへの送信には、送信が送られる位置に係らず、任意の地域または国でユーザにより受信される任意の送信を含むことができる。
【００６８】
好適な実施形態のこれまでの記述は、説明および記述のために提供されてきた。これまでの記述は、網羅的であること、または開示した厳格な形式に本発明を限定することを意図していない。多くの修正および変更は、当該技術分野における当業者には明らかであろう。たとえば、開示した本発明の実施形態で行われる工程は、順序を換えて行われることができ、ある工程は割愛でき、そして付加的な工程が追加できる。実施形態は、本発明の原理および実際のアプリケーションを最もよく説明するために選ばれ、そして説明されていて、それにより当業者が、様々な実施形態に対して、そして意図した特定の用途に向いている様々な修正を用いて本発明を理解できるようにしている。本発明の範囲が、クレームおよびそれらの均等物により定義されることを意図している。
【技術分野】
【０００１】
本発明は、デジタル地図データベース、および地理情報システム（ＧＩＳ）、ナビゲーション・システム（埋め込み型、ＰＤＡ、無線）、インターネット・アプリケーションなどを含めて、そのようなデジタル地図データベースを用いるシステム、および特に、道路網で最良のパスを求める検索を最適化するための技術に関する。
【先行技術文献】
【特許文献】
【０００２】
【特許文献１】米国特許第６，８８５，９３７号
【発明の概要】
【０００３】
本発明の実施形態には、道路網でルーティングを計算するためのシステムおよび方法を含む。実施形態には、ヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを前処理する工程、道路交通状況に関するリアルタイムデータに対応してヒエラルキーにリンクを動的に追加する工程、およびリアルタイム道路交通データに基づいて移動コストを概算するためにクラスタ・ルーティングを行う工程を含む。
【図面の簡単な説明】
【０００４】
本発明の実施形態は、以下の図に基づいて詳細に説明することとする。
【図１】出発地から目的地までのパス探索の例を示す図である。
【図２】双方向パス探索の例を示す図である。
【図３】パス探索に対する双方向の発見的方法の例を示す図である。
【図４】ノード間で道路優先順位のヒエラルキーを示す図である。
【図５】１つの実施形態の高位レベルのアーキテクチャ図である。
【図６】１つの実施形態に対する方法を示す流れ図である。
【図７】１つの実施形態に対する方法を示す流れ図である。
【図８】１つの実施形態に対する方法を示す流れ図である。
【図９】１つの実施形態に対する方法を示す流れ図である。
【図１０】１つの実施形態に対する方法を示す流れ図である。
【図１１】１つの実施形態に従って、１つ以上の構成要素を具体化するのに用いられる場合がある、コンピュータ・システム例のハードウェア・ブロック図である。
【発明を実施するための形態】
【０００５】
電子地図は、段階的に準備されることが多い。ある地域から別の地域へのパスが、事前に計算される場合がある。地域間パスを事前に計算することは、移動者が速い応答を望む場合応答時間を向上させる。この状況において、応答時間の向上はシステムの応答性が向上することを意味し、そして応答する時間がそれにより減少する。事前の計算は、パスに必要な計算が複雑で、そして込み入っている場合、特に有用である。
【０００６】
しかしながら、ある程度の計算がなお、走行時に要求に対応して行われる。これが、パス探索処理の一部が前もって計算され、そして地図アプリケーションに盛り込まれる処理をもたらす。その後、移動者が出発地および目的地を含む情報を入力し、そしてパス探索アプリケーションが、事前に計算された関連する経路を活用して、経路を決定する。
【０００７】
パス・アルゴリズムの変遷には、ダイクストラの最短パスを当然含むであろう。電子地図は有向グラフであり、ノード、および各リンクに割り当てられたコストを持つリンクの集成であるといえる。出発地と目的地との間の最小コスト・パスが、経路中のリンクの総コストを最小にするであろう。有向グラフでは、どの決定地点もノードであることができよう。あるノードから別のノードへのどの遷移もリンクである。パス探索処理に対する多くの最適化が、計算上の複雑さを減らし、そして応答時間を向上させることが可能である。
【０００８】
ダイクストラの本来の方法は、目的地が波面により覆われるまで波のような形状で出発地から検索が伝わる、一方向のパス検索である。ダイクストラのアルゴリズムは、単一起点の最短パス問題を解き、最短パスツリーを出力する。図１は都市部の道路の地図に渡って重ね合わされていて、そして出発地１００から目的地１０２に行くために経路が探し求められていると仮定する。最短パス問題にダイクストラのアルゴリズムを適用して、検索が四方八方に放射状に広がるであろう。パス探索処理が半径１０４に達する場合、パス探索処理は四方八方に探査してきたが、まだ目的地１０２を見つけていない。パス探索処理が半径１０６に達する場合、目的地１０２が見つけられている。
【０００９】
双方向の検索は、出発地と目的地との双方から、波が重なるまで伝わる検索を有する。双方向の検索は検索領域および計算時間を半分に減らす。２つの検索の各々は、複雑性Ｏ（ｂｄ／２）を有し、そしてＯ（ｂｄ／２＋ｂｄ／２）は出発地から目的地までの１つの検索の走行時間より少なく、１つの検索の走行時間はＯ（ｂｄ）であろう。図２には、出発地２００から目的地２０２に行くのに双方向検索を適用する例を示す。出発地２００からの検索２０４が目的地２０２からの検索２０６と交差する場合、最短パスが見つけられている。２００と２０２との間の距離は、１００と１０２との間の距離と同程度であるけれども、検索領域は双方向検索アルゴリズムでは半分の大きさである。
【００１０】
Ａ＊アルゴリズムは、検索を目的地に向かう探査を優先することに集中する。Ａ＊は、出発地ノードから目的地ノードまでの最小コスト・パスを見つけるグラフ検索アルゴリズムである。Ａ＊は、ノード・コスト、そしてこのようにして、検索がツリーにおけるノードを訪れる順序を決めるのに発見的機能を用いる。図３には、出発地３００から目的地３０２に行く双方向のＡ＊アルゴリズムを適用する例を示す。出発地３００からの検索３０４が目的地からの検索３０６と交差する場合、最短パスが見つけられている。３００と３０２との間の距離は、１００と１０２との間の距離と同程度であり、その上検索の領域は双方向Ａ＊アルゴリズムを用いると大幅に減らされている。
【００１１】
ヒエラルキーモデルはさらなる最適化を提供できる。ノードの優先順位がノードのルーティング（経路指定）重要度およびネットワークヒエラルキーにおける場所を説明する。パス探索アルゴリズムの最終目標はコストを最小限に抑えることである。リンクのコストは、時間、距離であることができ、または他の要因に係る。リンクには最適化基準に基づいてコストが割り当てられる。コストの分類体系は、道路、高速道路、小道、ドライブウェイ、ランプ、非ランプ、有料道路、渡し場、国境などを識別できるようにする、多くのレベルを有することができる。コストは、距離に距離辺りコストを乗ずることにより調整できる。リンクは同時に複数のコスト・クラスを有することができ、たとえば、ヒエラルキーモデルで高い優先順位に分類されることができ、そしてまたアクセスが制限されることもできよう。一部のコスト・クラス（有料道路、渡し場など）はさらなる制御を有する場合がある。検索はその場合、探査されるノードの最小コストにより動かされて、ノードからノードへ伝わる。
【００１２】
ＲＤＳ ＴＭＣ（無線データ・システム−道路交通メッセージ・チャネル）は、ＦＭ無線でＲＤＳ副搬送波によって道路交通データを同報するための、世界的に認知された規格である。データはＴＭＣ規格に従って符号化され、そして移動者の位置および／または経路に関連する情報を提供するために、マッピング・システムにより復号される。
日本は道路交通情報通信システム（ＶＩＣＳ）を開発している。ＶＩＣＳは、路車間情報システム（ＲＡＣＳ）と新自動車交通情報通信システム（ＡＭＴＩＣＳ）との競合を解決し、そして双方の最良の特徴を用いる共通のシステムを規定することを最終目標とするプログラムである。１つの提案は、それぞれの各システムにより用いられているツールを本質的に結合させて、両方向の路車間通信および位置情報を提供する、デジタル・マイクロ・セルラ無線システムである。ＲＡＣＳタイプ１ビーコンおよび、（無線データ・システム−道路交通メッセージ・チャネル（ＲＤＳ−ＴＭＣ）のような）ＦＭカー・ラジオによる運転者への情報の同報を用いるＲＡＣＳ−ＡＭＴＩＣＳが、別の選択肢である。
【００１３】
国際標準化機構（ＩＳＯ）は、規格ＩＳＯ１７５７２−３高度道路交通システム−地理データベースのための位置参照−第３部：動的位置参照を創出していて、この規格はまたＡＧＯＲＡ−Ｃとしても知られる。この規格は、規模効率およびロバストな自律的複号化のために最適化されたマシン同士の位置表現をサポートするように設計されている。動的方法として、ＡＧＯＲＡ−Ｃは復号時に地図の版間の差異を予測する。ＡＧＯＲＡ−Ｃ規格は、ＴＭＣの置き換えを含めて、拡張ナビゲーション・サービスの進展を認めるように設計されている。ＡＧＯＲＡ−Ｃは、所定の位置コードまたは参照表を必要とすることなく、販売業者または版に係らず、位置参照を動的に符号化し、そして位置参照を任意の地図に復号するための方法を仕様化する。位置参照は、道路の合流点、出口ランプ、および郵便配達用住所のような地理的対象物の一意的な識別である。
【００１４】
道路交通流を明らかにするために、大抵の商用システムは、地図データ提供業者とアプリケーション提供業者との間で共有される政府規格または企業規格のいずれかである位置識別子によって、道路エンティティを参照する所定の位置コード集合に依存する。データ流に影響する道路交通事象は通常、ＴＭＣの書式（ＵＳおよびヨーロッパ）またはＶＩＣＳ（日本）によって記述される。事前に割り当てられた位置コードの必要性が必然的に、そのようなシステムを最も重要な交差点での位置の比較的小さな部分集合に制限する。大抵のルーティング・エンジンは、動的に修正された少量のデータに対処することができる。一部のルーティング・エンジンは最初にパスを計算し、それから道路交通事象が通知または再計算の正当な理由になるかどうかを決定するために調べる。
【００１５】
限られた位置表を同期させ、そして維持するためのコストは、道路交通提供業者が、厳選したＴＭＣセグメントだけでなく、ネットワーク全体に対して、過去にあったプローブ・データおよび、所与の週日、日付、および時間間隔で所与のリンクに対する速度パターンを予測することができるアルゴリズムを蓄えるにつれて、益々魅力がなくなる。ＩＳＯがＡＧＯＲＡ−Ｃに基づく位置参照規格の最初の草案を承認するに伴って、動的位置参照で、また進展がなされてきた。
【００１６】
ＡＧＯＲＡ−Ｃ、ＶＩＣＳ、およびＲＤＳ／ＴＭＣは、動的位置参照規格の例である。他の基準が熟慮されている。本発明の実施形態は、位置参照方法により提供される動的データを利用する。本発明の実施形態は本明細書で説明される位置参照規格に限定されない。
【００１７】
リアルタイム道路交通データはその大きさが増加しそうであり、そして現行のアルゴリズムが妥当な時間でデータを効率よく処理できなくなるような限度まで拡大しそうである。近い将来、センサーがこれまでよりも多数の道路での道路交通状況に関するデータを送信しているであろう。ナビゲーション・システムのための全地球測位システム（ＧＰＳ）および拡張位置決定システムは、車がその位置を決定できるようにするばかりでなく、両方向通信を活用して、道路交通データ提供業者がそのような装備をしている車の位置を決定し、そして車に影響を及ぼすその時点の道路交通状況を決定できるようにするであろう。（ＩＮＳ、推測航法などを含むことができることになる）ナビゲーション・システムに１つよりも多くのＧＰＳ受信機がある可能性がある。また、ＧＰＳ以外に、現在またはまもなく利用できる他の全地球航法衛星システム（ＧＮＳＳ）がある。
【００１８】
本発明の一部の実施形態は、交通事故および抗議行動のような事象を含めて、またルーティングに影響を及ぼす場合があるリアルタイムデータをパス探索が考慮できるようにする。大きなプラットホーム、小さなプラットホーム、および埋め込みプラットホームでのルーティング・アルゴリズムは、この極めて多量の動的コスト・データを効率よく用いることができるであろう。本明細書で説明されるルーティング・アルゴリズム技術の一部の実施形態は、高速ルーティングを可能にしたまさしくそのものである、地図データヒエラルキーおよび双方向集中検索を伴う問題、完全に動的なリンク通過の膨大なコストのために生じる問題を解決する。
【００１９】
リンク・コストはルーティング・アルゴリズムに必須である。共通の最終目標は、最短移動時間を計算することである。検索が道路網での最短移動に対して最適化される場合、リンク・コストは、かかるリンクでの移動時の通過速度またはかかるリンクを通過するに要する時間で表わされることができる。リンクは２つの決定地点間での道路のセグメントとして定義される。ノードは道路網で特定のリンクから到達する決定地点である。
【００２０】
道路は重要度、スループットおよび制限速度の点で異なるので、道路網は自然的なヒエラルキーを形成する。多くのルーティング・アルゴリズムは、移動距離および道路網の細部の状況に相応しい詳細度を保つために、この潜在的なヒエラルキーに依存している。重要性の劣った道路が、ある距離を移動するパスを計算するためにより重要な道路間の近道として役立つ場合もあるため、自然的な道路ヒエラルキーはルーティングには不完全であることが多い。高度なルーティング・データベース・アプリケーションは、パスを計算するのにグラフのごく一部だけを処理すればよいように、走行時間性能のためにヒエラルキーを事前に計算できる。
【００２１】
事前に計算されるルーティングヒエラルキーのための並列プロファイル
コストが移動速度に対して最適化される場合、ルーティング・アルゴリズムは、ルーティング・アルゴリズムの観点から残った道路が信号のない高速道路だけになるまで、ルーティング・アルゴリズムが徐々により重要な道路を好んで出発地および目的地から遠ざかるように伝わるので、重要度のより低い道路を放棄する傾向がある。目的地が遠ければ遠いほど、信号のない高速道路でのマイル距離の割合が高くなる。事前に計算されるヒエラルキーは、好都合なことに、道路のまさに適切な部分集合の検索を可能にする。事前に計算されるヒエラルキーは移動速度が道路の重要度とともに増すことを仮定している。
【００２２】
たとえば、朝の通勤は道路での道路交通流を渋滞させ、一方午後の通勤では高速に移動することが可能となる。同様に、混雑した道路に通じるまたは遠ざかる道路は、ある方向には影響されるが、その反対方向には影響されない場合がある。さらに、ヒエラルキーが道路に対する最高速度制限に基づいて構築されると、結果は必ずしも満足いくとは限らないであろう。
【００２３】
事前に計算されたデータがリレーショナル・データベース管理システム（ＲＤＢＭＳ）に記憶される場合、道路網のほんの一部を代表する高速道路は、性能を位大きく影響することなく更新できる。しかしながら、走行時に優先順位の低い道路を奨励することは、低いレベルにある非常に多くの道路のために、大規模な設備を考慮しても難しくなる可能性があって、性能への影響はシステムにはとても大きいだろう。
【００２４】
厳しい道路交通状況の下で、一部のシステムは、応答時間および、秒当たりに計算されるパスの数にマイナスの影響を与える、ツリーの上位レベルを用いないように決めており、一方商用車運営会社は“定期的”な通勤、“朝”の通勤、“午後”の通勤に対して異なるルーティング・データベースを維持する場合がある。
【００２５】
道路交通事象は、地図アプリケーションに対して事前に計算された典型的なヒエラルキーでは効率的に処理できないような、大量の動的リンク・コストを生成することがある。本発明の１つの実施形態は、動的適応ヒエラルキーの方法を用いてこの問題を解決する。
【００２６】
特許文献１は、ヒエラルキールーティング・アルゴリズムがより効率的になるように、高位レベルでデジタル地図を追加のリンクで増大させる近道ジェネレータを記載している。典型的なヒエラルキールーティング・アルゴリズムの例が図４に示されている。車道４００が最も高い優先順位を有しており、そして高速移動を可能とする、信号のない高速道路である。車道４０２、車道４０４、および車道４０６は、中間の優先順位を有し、そして中間の速度を許可する。地方道路４０８、４１０、４１２、４１４、４１６、および４１８は、停止信号、一時停止標識、および望ましさを減らす他の難事を有する道路である。ヒエラルキーの高位レベルでは、優先順位の低い道路がなくなるので、優先順位の高いノード間のリンクは益々遠距離にわたる。経路が長距離にわたるように意図されると、パス検索アルゴリズムは車道４００、４０２、４０４、および４０６を考慮するが、地方道路４０８、４１０、４１２、４１４、４１６、および４１８を考慮しないことにより最適化する場合がある。特許文献１に記載されている近道ジェネレータは、地方道路が優先順位の高い２つの道路間の望ましい近道であると、パス探索検討に対して、地方道路が優先して奨励されるようにする。たとえば、地方道路が２つの高速道路をつなぐと、近道ジェネレータは、地方道路がパス検索アルゴリズムにより考慮されるように奨励する場合がある。
【００２７】
他の地図ヒエラルキーと同様に、静的道路分類での近道ジェネレータ方法は、地図提供業者が仮定した速度制限と、使用時に所与のリンクに対する実際の速度または予測速度との間でコストに予測できない差異がある場合、あまりうまく機能しない。これらの予測できない差異に関する２つの主な原因がある。
【００２８】
経路が計算されるときのリンク・コストは、その時点の実際の道路交通、過去の顕著な道路交通パターン、または予測された道路交通情報によって、データが構築された当時に仮定されていたリンク・コストと異なる場合がある。
【００２９】
高い優先順位が付与されている道路は、実際には、危険物積載トラックに禁止される場合があり、それで禁止された道路を含むパスは、特定の車には役に立たないであろう。時間制限または車両制限に関する別の例は、ＨＯＶレーンに対してである場合があり、ＨＯＶレーンは、ある車に対して一日のある時間帯で利用できるだけである。
【００３０】
本発明の実施形態はこれらの問題への解決策を提案する。上述の特許で記載されているように、近道ジェネレータを一度だけ実行する代わりに、本発明の実施形態は、近道ジェネレータを何度も、そのたびに異なる“プロファイル”を用いて実行する。第１のプロファイルは、コストに修正を加えていない標準のプロファイルである。１つの実施形態では、環境プロファイルは動的パラメータ、ユーザ・パラメータ、および／または環境パラメータに基づいている。
【００３１】
過去にあった道路交通に対して、変化率が有意でない時間間隔は数少ないプロファイルに圧縮され、それから近道ジェネレータが、どれ程多くのプロファイルが望まれるかによって、妥当な時間セグメントの各々に対して実行される。１つの例では、１０個のプロファイルが、朝のラッシュアワー道路交通プロファイル、夕方のラッシュアワー道路交通プロファイル、週日の平坦な時間帯の道路交通プロファイル、週末の道路交通プロファイル、および他の典型的なプロファイルをカバーするように作成される。１つの実施形態は、各曜日の半時間の期間ごとに対してプロファイルを作成する。プロファイルは、それから類似性に基づいて比較され、そしてより小さいプロファイルの集合に統合される。環境プロファイルに対する時間スロットは、時間スロットが周期的（１時間、半時間、１５分など）であれ、または周期的でなかろうと（真夜中から６時、６時から１０時、１０時から午後３時、午後３時から午後７時など）、任意であることができる。
【００３２】
代わりの実施形態では、物流プロダクトが作り出される。この実施形態では、第１のプロファイルは標準的なコストを有し、そして制限がない。第２のプロファイルは、トラックが禁止されている、または許可されないすべての道路である。第３のプロファイルは危険物が禁止されている、または許可されないすべての道路である。ビジネス・ロジックが必要とするだけのさらなるプロファイルが、創出されるであろう。
【００３３】
一般に、プロファイルが多ければ多いほど、アルゴリズムによりもたらされる解答がより正確になる。事例の大部分を扱うには１０個以上のプロファイルを取り上げるべきではない。特定の状況がプロファイルと正確に合致しなくても、ヒエラルキーの豊富さが良好な対案を提供する可能性がある。１つの実施形態が、動的パラメータ、ユーザ・パラメータ、および環境パラメータを単一のヒエラルキーに統合する場合がある。
【００３４】
一旦近道ジェネレータが別々のプロファイルを構築すると、次の工程はプロファイルのすべてを１つの最終結果にまとめることである。これが行われる方法は、どのノードも、プロファイルすべての中で有する最高の優先順位の値を有することであり、そして複合リンク（単体リンクの集約）がプロファイルのどれかに存在すると、その場合複合リンクはまた最終結果に存在する。複合リンクは、新しい優先順位を持つ１つ以上のリンクを表わす場合がある。これらの複合リンクは近道ジェネレータにより生成された近道を表わす。多くのファイルは事実上、同じリンクを奨励するので、意図した結果は、近道ジェネレータによって実行されなかったプロファイルでさえ、その結果をうまく表されるよい機会を有することである。
【００３５】
最終結果は、まだ１０個の異なる状況として用いられる、１０個全体の状況を効率的に記憶する単なる方法ではなく、道路交通状態の特質に係らず、ネットワークは事前に構築された近道のすべてを有するので、むしろ最終結果は、効率的なルーティングが一日中いつでも行われることができるように、十分な複雑性を持つ１つのデータベースである。その場合、システムはまだ、（上位レベルで）合理的に疎なネットワークを有するが、そのネットワークは“混雑中の道路交通”選択肢に必要な近道を含むのに十分な密度を有する。その場合、動的な道路交通は、ヒエラルキーを再構築する必要がなく、（効率的に）リアルタイムでのリンク重みとして用いられることができる。
【００３６】
一部の他企業の解決策は、静的データで得たヒエラルキーの最高位のレベルへの奨励を無効にして、これらのレベルが道路交通事象により非効率な状態にされる場合、ルーティング不成功を引き起こす。これらの代替手法は、本発明の実施形態の手法の下で必要である以上に、考慮されなければならないリンクの数を大きくする。本発明の実施形態は二重の改善を提供しており、実施形態は、高位レベルでのルーティング検討に利用できる低位レベルのリンクの数を実現できるものだけに制限し、一方また低位レベルのリンクをヒエラルキーの所与のレベルに相応しいようにより長い一続き（複合リンク）に集約する。
【００３７】
１つの実施形態で、同じアルゴリズムが、料金所／渡し場／国境の通過回避、道路交通制限に対する複数の車両プロファイル、および／またはそのような動的パラメータ、ユーザ・パラメータ、または環境パラメータの組み合わせによって、複数のリンク・コストに対するルーティングヒエラルキーを強化するのに適用される。
【００３８】
動的適応ヒエラルキー
道路公社または動的状況が、ヒエラルキーの適当なレベルに存在しない迂回路を提案する場合がある。たとえば、道路交通が一時的に、建設または緊急の現場をバイパスするための方法として地方道路に迂回できよう。ルーティング・システムの１つの実施形態は以下のやり方でヒエラルキーを動的に調整する。
【００３９】
１つの実施形態で、道路のヒエラルキー網を記述する情報がデータベースに格納される。データ提供業者は、特定の時間に通常の場合より好適である場合がある道路のヒエラルキー網の一部を識別でき、そして道路のヒエラルキー網を一意的に識別可能なパスを備えている位置のシーケンスとして表現できる。道路のヒエラルキー網のこれらの部分はそれから、１つのリンクまたは複数のリンクとして、走行時に道路のヒエラルキー網に追加される。１つの実施形態で、道路交通状況に関するリアルタイムデータは、外部情報源により（ＲＤＳ ＴＭＳ、ＡＧＯＲＡ−Ｃ、ＶＩＣＳまたは同様な道路交通情報システムを通して）供給される。
【００４０】
１つの実施形態で、動的適応ヒエラルキーは走行時に事前に計算されたヒエラルキーに新しいリンクを追加することに係る。構築時に、ネットワーク・ビルダーは相互参照表を生成し、相互参照表は道路交通データ提供業者により用いられる最終のネットワークＩＤを、ルーティング・ソフトウェアにより用いられる道路網ＩＤに（リンクおよびノードの双方に対して）対応付ける。１つの実施形態で、この相互参照データは高速ランダム・アクセスを持つデータベースに格納される。走行時に、リアルタイム道路交通情報が迂回路を必要とする場合、この情報は、現存するネットワークにおけるどのノードが修正される必要があるかを識別するのに用いられる。単一の迂回路は、適当な優先順位を備えており、そして各レベルに相応しいように構成される、ヒエラルキーの異なるレベルで追加される複数のリンクをもたらすことができる。これらの新しいリンクは既に存在しているリンクと全く同じやり方でルーティング・アルゴリズムに供給され、このようにして、ルーティング・アルゴリズムは修正される必要がない。
【００４１】
ＡＧＯＲＡ−ＣはネットワークＩＤｓを有しないが、その代わりに道路要素の多少自由な形式の記述／参照に依存する。ＡＧＯＲＡ−Ｃおよび同様な参照システムに対して、相互参照表は作成できない。その代わりに、影響を受ける形状がリアルタイム復号処理により識別されなければならない。
【００４２】
これらの新しいリンクは、動的データに基づいて、パス探索アルゴリズムが、迂回路を必要とするリアルタイム道路交通事象に順応できるようにする。同じ方法が、１つ以上のプロファイルをヒエラルキーの既に存在する枝に漸次まとめることができるようにし、１つ以上のプロファイルが、ネットワークの大部分が自然災害または何らかのそのような事象によって通過時間を修正している場合に、必要となる場合がある。
【００４３】
双方向集中ルーティング
双方向ルーティングは、伝搬領域（およびこのようにしてノードの数および計算時間）をおおよそ半分に減らすために採用される。集中ルーティングはさらに、出発地または目的地に向かう伝搬を優先することにより検索領域を減らす。ダイクストラ最短パス・アルゴリズムでは、波面での最小コスト・ノードは、移動時間を最適化する場合に、最適パスが既に見つかっているということと、それに従って波の出発地からの到着時間も既に見つかっているという特徴がある。集中Ａ＊では、波面でのノード・コストは、波の中心からノードまでの移動コストと、反対側の波面の中心までの、通常何らかの発見的方法を用いて計算される推定コストとの合計である。どの工程でも最小コスト・ノードからの伝搬は、最小コスト・パスを見つけるのに必須である。
【００４４】
移動時間依存のリンク・コストは伝搬に対する問題を提起しており、出発地から目的地波面上のかかるノードまでの最良パスがまだ見つかっていないので、最良パスのコストおよびノードに到着する時間は未知であり、したがって正確なリンク・コストが確認できない。たとえば、経路が午後３時３０分に出発地を離れるように計画されていると、出発地近くの道路交通状況は、出発地を離れる波面を計算するために過去にあったデータに基づいて予測できる。しかしながら、パス探索処理はまだ完了していないので、目的地から広がる波に対するコストを計算する場合、目的地近くの道路交通状況に対してどの時間を用いるかは未知である。
【００４５】
従来のアルゴリズムは、コスト値が一定である静的グラフ上で行われる。従来のアルゴリズムは、これらのコストの動的性質を無視していたのでより効率的であった。時間依存のコスト値を考慮するより大きな静的グラフを創出することにより、Ａ＊アルゴリズムを時間依存のリンク・コストと連携するように修正することができる。しかしながら、そのような修正されたグラフの量は、元の静的グラフと大きさが１００倍ぐらい違うだろう。結果として、経路を計算する計算時間は、それに応じて受け入れ難いほどに増加するであろう。
【００４６】
問題を解決する別の方法は、短いパスに対して機能する可能性がある、ノードに到着する最小最大の時間間隔、およびこれらの間隔に対する平均リンク・コストを確認することであろう。混雑中の道路交通状況にあるより長いパスは不当に大きな間隔を有し、そしてより信頼できる手法を必要とする場合がある。
【００４７】
クラスタ・コスト近似法
静的手法に反して、１つの実施形態は、常に変化する道路交通状況の下で、合理的に迅速に妥当なパスを強いるようにしながら、動的ルーティングを近似の役割として認める。
【００４８】
１つの実施形態はルーティング・ネットワークを論理的なクラスタに分割することから始まる。どの方法がかかることのために用いられるかは、この議論には重要でない。１つの実施形態では、四分ツリーが利用される。簡単にするために、平方マイル当たりの道路密度、交通渋滞、移動頻度、または同様な基準の関数として、細分基準を持つ論理的なクラスタツリーを仮定する。代替の実施形態は、空間的指標で典型的な同様の基準を用いる。各クラスタは空間的な広がりを有し、そして隣接するクラスタへの移動時間を記憶して、移動時間は過去にあったデータまたは予測データから事前に計算され、および／またはリアルタイムデータ・プローブから動的に維持される。これは、移動時間に依存するコストを用いてクラスタ・ルーティングを行うためにクラスタに対する簡略化したグラフを生み出す。
【００４９】
１つの実施形態で、ナビゲーション・システムは、ナビゲーション・システムを備えた車が道路を通過して移動するのにどれぐらい時間が掛かるかを計算できる。ネットワークは、走行時プローブ・データから車が地図を横切るのにどれぐらい時間が掛かったかを承知している。地図がクラスタに分けられる場合、クラスタからクラスタに移動する複数の車からの走行時プローブ・データに基づいて、あるクラスタから別のクラスタに行くのにどれぐらい時間が掛かるようになるかが推定できる。
【００５０】
パスの出発地ノードが出発地クラスタと呼ばれるクラスタに存在し、そしてパスの目的地ノードが目的地クラスタに存在する。一部の実施形態では、このグラフの大きさが極めて小さいために、一方向ダイクストラ・アルゴリズムが、このクラスタ・グラフでパスを計算するのに用いることができる。道路網グラフにおける各ノードが何らかのクラスタに入るので、この計算からの結果は、ノードのクラスタと反対側の波面の中心が属するクラスタとの間で、移動方向における概算の時間を与えるであろう。
【００５１】
目的地の波面で、この値がノードに到着する推定時間の代わりに用いられ、同様に適切なリンク・コスト値の選択を可能にするであろう。その場合、ノードから反対側の波面の中心までのコストを、ノードのクラスタから反対側の波面の中心が属するクラスタまでのルーティング方向における移動の概算コストにより推定するために、発見的方法が代わりに用いられる。相対する波面からのノードが繋がる場合、対象の波での概算コストが、出発地からの実際のパスの新しく計算したコストにより代用される。
【００５２】
双方向Ａ＊アルゴリズムの残り部分が従来どおりに継続するであろう。
【００５３】
サーバにおいて、多くの異なるパス要求が同じ出発地クラスタおよび同じ目的地クラスタを有する場合、クラスタ・ルーティングの結果（すなわち、クラスタからクラスタまでのコスト）が地域内クラスタ間のコストの一部が変わってしまうまで、再使用できよう。
【００５４】
図５は１つの実施形態の高位レベルのアーキテクチャを示す。元の電子地図データ５００が環境プロファイル５０２を用いてヒエラルキーの中で事前に処理される。１つの実施形態で、ルーティングヒエラルキーが近道ジェネレータにより何度も処理される。１つの実施形態で、１０個のプロファイルが朝のラッシュアワー道路交通、夕方のラッシュアワー道路交通、平坦な時間帯の週日道路交通、週末道路交通、およびその他のプロファイルをカバーするように作成される。その後、プロファイルは最終結果にまとめられ、増強された地図データ５０４を生み出す。その後、増強された地図データはパス探索システム５１０に配信される。リアルタイム道路交通状況に基づいて道路網のいずれのリンクおよびノードを修正すべきかを決定するために、リアルタイム道路交通データ５０６が位置の好適な連続５０８を生成するのに用いられる。パス探索システム５１０はそれから、経路５１２を計算するために、並列プロファイルを持つ増強された地図データおよび、クラスタ・コスト近似法で動的に更新されるリンクを用いる。
【００５５】
図６は、１つの実施形態に対する流れ図を示しており、道路網でルーティングを計算するための方法である。本方法には、ヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理する工程６００を含む。本方法には、道路交通状況に関するリアルタイムデータに対応してリンクをヒエラルキーに動的に追加する工程６０２を含む。本方法には、リアルタイム道路交通データに基づいてルーティング移動コストを概算するために、クラスタ・ルーティングを行う工程６０４を含む。
【００５６】
図７は１つの実施形態に対する流れ図を示しており、道路網でルーティングの計算を改善するための方法である。本方法には、ヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理する工程７００を含む。本方法には、１つ以上の環境プロファイルに対する近道を計算する工程７０２を含む。本方法には、１つ以上の環境プロファイルに対する近道をデータベースにまとめる工程７０４を含んでおり、ノードはデータベースにまとめられた１つ以上の環境プロファイルの中で、ノードの値の最高の優先順位を有する。本方法にはさらに、「複合リンクが１つ以上の環境プロファイルにある場合、複合リンクはまた、データベースにある」という工程７０６を提供する。
【００５７】
図８は１つの実施形態に対する流れ図を示しており、既に構築されている道路のヒエラルキー網に新しいリンクを動的に追加するための方法である。本方法には、道路網の１つ以上の部分を、リアルタイムデータに基づいて通常よりも好適であると識別する工程８００を備える。本方法には、道路網の１つ以上の部分を、一意的に識別可能なパスを備える位置のシーケンスとして表わす工程８０２を含む。本方法には、既に構築されている道路のヒエラルキー網に１つ以上のリンクを追加するために一意的に識別可能なパスを備えている位置のシーケンスを用いる工程８０４を含む。本方法には、パス探索アルゴリズムがリアルタイムデータに順応できるようにする工程８０６を含む。
【００５８】
図９は１つの実施形態に対する流れ図であり、道路網で車両ナビゲーションの計算を改善するための方法である。本方法は、道路網を論理的なクラスタツリーに分割する工程９００を含む。本方法は、各クラスタに対して隣接するクラスタへの移動時間を記憶する工程９０２を含む。本方法は、ノードから反対側の波面の中心までの移動に関するコストを推定するための発見的方法の代わりに、ルーティングの方向でのノードのクラスタと反対側の波の中心のクラスタとの間の移動に関する概算コストを用いる工程９０４を含む。本方法は、目的地の波面ノードから伝搬している各リンクに対するコストを、かかるノードでのクラスタ近似による到着時間に基づいた時間間隔から計算する工程９０６を含む。本方法は、相対する波面からのノードが繋がる場合、対象の波での概算コストが、出発地からの実際のパスの新しく計算されたコストにより代用される工程９０８を含む。
【００５９】
図１０は１つの実施形態に対する流れ図を示しており、道路網で車両ナビゲーションの計算を改善するための方法である。本方法は、道路網を四分ツリーに分割する工程１０００を含む。本方法は、各四分ツリーに対して隣接する四分ツリーへの移動時間を記憶する工程１００２を含む。本方法は、ノードから反対側の波面の中心までのコストを推定するための発見的方法の代わりに、ルーティングの方向でのノードの四分ツリーと反対側の波の中心の四分ツリーとの間の移動の概算コストを用いる工程１００４を含む。本方法は、目的地の波面ノードから伝搬している各リンクに対するコストを、かかるノードでの四分ツリー近似による到着時間に基づいた時間間隔から計算する工程１００６を含む。本方法は、相対する波面からのノードが繋がる場合、対象の波での概算コストが、出発地からの実際のパスの新しく計算されたコストにより代用される工程１００８を含む。
【００６０】
図１１は典型的な処理システム１１００を説明しており、図５の要素の１つ以上を備えることができる。他の代替が利用される可能性があるが、図５のシステムの構成要素は、ハードウェア、ソフトウェアまたは、他に指示がなければ、これらと調和する１つ以上の計算システムによる何らかの組み合わせに実装されると考えられるであろう。
【００６１】
計算システム１１００は、１つ以上の汎用プロセッサまたは専用プロセッサ１１０２を含めて、１つ以上の通信チャネル（たとえば、バス１１０１）を通して結合される構成要素、たとえばペンティアム（登録商標）、セントリーノ（登録商標）、パワーＰＣ（登録商標）、デジタル信号プロセッサ（“ＤＳＰ”）、などを備える。システム１１００の構成要素にはまた、特定のアプリケーションに従って、１つ以上の入力装置１１０３（たとえば、マウス、キーボード、マイクロフォン、ペンなど）、および１つ以上の出力装置１１０４、たとえば相応しいディスプレイ、スピーカ、アクチュエータなどを含む。（当然のことながら、入力装置または出力装置はまた同様に、精神的または身体的な不自由者が用いるのに相応しいように機能が強化された、より特殊化した装置またはハードウェア／ソフトウェア装置を含むことができる）。
【００６２】
システム１１００はまた、コンピュータで読み取り可能な記憶媒体１１０６、たとえば記憶／メモリ装置またはハード、または取り外し可能な記憶／メモリ媒体に結合されたコンピュータで読み取り可能な記憶媒体読み取り装置１１０５を含み、そのような装置または媒体はさらに、別々に記憶１１０８およびメモリ１１０９として示され、特定のアプリケーションの要求条件に従って、ハードディスク系、フロッピー（登録商標）／コンパクト・ディスク系、デジタル多用途ディスク（“ＤＶＤ”）、スマート・カード、リード・オンリ・メモリ、ランダム・アクセス・メモリ、キャッシュ・メモリ、などを含む場合がある。直接に、または１つ以上の相応しい私設網または公衆網または既に論じたものを含むがこれらに限定されない場合がある他の構成要素を通して装置間通信を提供するために、１つ以上の相応しい通信インタフェース１１０７、たとえばモデム、ＤＳＬ、赤外線、ＲＦまたは他の相応しい送受信機などがまた含まれる場合がある。
【００６３】
作業用メモリ１１１０はさらに、使用中にそのなかに記憶される、または読み込まれる可能性がある、システム１１００の構成要素を実装するために、オペレーティング・システム（“ＯＳ”）１１１１要素および他のプログラム１１１２、たとえば、アプリケーション・プログラム、モバイル・コード、データなどのうちの１つ以上を含む。特定のＯＳまたは複数のＯＳが、特定の装置、特徴または特定のアプリケーションに従った他の態様に従って変わる場合がある（たとえば、ウィンドウズ（登録商標）、ウィンドウズＣＥ（商標）、マック（商標）、リナックス、ユニックスまたはパーム（商標）ＯＳ系、セル電話ＯＳ、独自ＯＳ、シンビアン（商標）など）。特定のアプリケーションの要求条件に従ってたとえば、Ｃ系（たとえば、Ｃ＋＋、Ｃ＃）、ジャバ（商標）２プラットホーム、エンタープライズ・エディション（“Ｊ２ＥＥ”）または他のプログラム言語と互換性のある、様々なプログラミング言語または他のツールがまた利用できる。他のプログラム１１１２はさらに、本明細書のいずれかで論じたものを含むがこれらに限定されずに、たとえば、活動システム、教育マネージャ、教育インテグレータ、またはインタフェース、セキュリティ、他の同期、他のブラウザまたはグループウェア・コードなどのうちの１つ以上を含む場合がある。
【００６４】
実施形態には、本開示の教示に従ってプログラムが組まれた、従来の（複数の）汎用コンピュータまたは（複数の）専用デジタル・コンピュータまたは（複数の）マイクロプロセッサを用いて実装される場合がある、コンピュータを使った方法およびシステムを含むことができる。適切なソフトウェアのコーディングは、本開示の教示に基づいてプログラマにより容易に準備できる。
【００６５】
実施形態には、コンピュータで読み取り可能な媒体、たとえばコンピュータで読み取り可能な記憶媒体を含むことができる。コンピュータで読み取り可能な記憶媒体は、本明細書で提示した特徴のいずれかを行うようにコンピュータをプログラミングするのに用いることができる命令を記憶しておくことができる。記憶媒体はまた、フロッピー・ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロ・ドライブおよび光磁気ディスクを含むいかなるタイプのディスク、ＲＯＭｓ、ＲＡＭｓ、ＥＰＲＯＭｓ、ＥＥＰＲＯＭｓ、ＤＲＡＭｓ、フラッシュ・メモリ、または命令および／またはデータを記憶するのに相応しい任意のメディアまたはデバイスを含むことができるが、これらに限定されない。本発明には、コンピュータ、たとえば汎用／専用の（複数の）コンピュータまたは（複数の）マイクロプロセッサのハードウェアを制御するための、およびこれらのコンピュータがヒューマン・ユーザまたは、本発明の結果を利用する他のメカニズムと情報をやり取りできるようにするためのソフトウェアを含むことができる。そのようなソフトウェアには、デバイス・ドライバ、オペレーティング・システム、実行環境／コンテナ、およびユーザ・アプリケーションを含む場合があるが、これらに限定されない。
【００６６】
実施形態には、処理を実装するためのコードを提供する工程を含むことができる。提供工程には、どんな方法によってもユーザにコードを提供する工程を含むことができる。たとえば、提供工程には、物理メディアでコードをユーザに提供することを含み得、またはコードを使用できるようにする他の任意の方法を提供する工程を含むこともできる。
【００６７】
実施形態は、実施形態の処理のいずれかを行うようにコンピュータで実行できるコードを送信するための、コンピュータに実装される方法を含むことができる。送信には、ネットワークの任意の部分、たとえば、インターネットを介する送信、有線送信、または他のどのような種類の送信をも含むことができる。送信には、コードの送信を開始する工程、または任意の地域または国から別の地域または国にコードを通すようにさせる工程を含むことができる。ユーザへの送信には、送信が送られる位置に係らず、任意の地域または国でユーザにより受信される任意の送信を含むことができる。
【００６８】
好適な実施形態のこれまでの記述は、説明および記述のために提供されてきた。これまでの記述は、網羅的であること、または開示した厳格な形式に本発明を限定することを意図していない。多くの修正および変更は、当該技術分野における当業者には明らかであろう。たとえば、開示した本発明の実施形態で行われる工程は、順序を換えて行われることができ、ある工程は割愛でき、そして付加的な工程が追加できる。実施形態は、本発明の原理および実際のアプリケーションを最もよく説明するために選ばれ、そして説明されていて、それにより当業者が、様々な実施形態に対して、そして意図した特定の用途に向いている様々な修正を用いて本発明を理解できるようにしている。本発明の範囲が、クレームおよびそれらの均等物により定義されることを意図している。
【特許請求の範囲】
【請求項１】
道路網でルーティングを計算するための方法であって、
データベースにある道路のヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理する工程と、
前記１つ以上の環境プロファイルに対する近道を計算する工程と、
前記１つ以上の環境プロファイルに対する前記近道を前記データベースにまとめる工程と、
道路網の１つ以上の部分をリアルタイムデータに基づいて普通よりも好適であると識別する工程と、
道路網の前記１つ以上の部分を、一意的に識別可能なパスを成す位置のシーケンスとして表わす工程と、
前記位置のシーケンスを、前記データベースにある前記道路のヒエラルキーに関連付けるリンクを動的に追加する工程と、
ルーティング移動コストを概算するために、リアルタイム道路交通データに基づいてクラスタ・ルーティングを行う工程と
を備えることを特徴とする方法。
【請求項２】
ルーティング移動コストを概算するために、リアルタイム道路交通データに基づいてクラスタ・ルーティングを行う前記工程が、
前記道路網を論理的クラスタツリーに分割する工程と、
各クラスタに対して隣接するクラスタへの移動時間を記憶する工程と、
ノードから反対側の波面の中心までのコストを推定するための発見的方法の代わりに、前記ルーティングの方向へのノードのクラスタと前記反対側の波の前記中心のクラスタとの間の移動の概算コストを用いる工程と、
目的地の波面ノードから伝わる各リンクに対するコストを、当該ノードへのクラスタ近似による到着時間に基づいた時間間隔から計算する工程と、
相対する波面からのノードが繋がる場合、対象の波での概算コストが、出発地からの実際のパスの新しく計算されたコストで置換される工程と
を備えることを特徴とする、請求項１に記載の方法
【請求項３】
前記１つ以上のプロファイルに対する前記近道が前記データベースにまとめられることを特徴とする、請求項１に記載の方法。
【請求項４】
ノードが前記データベースにまとめられた前記１つ以上のプロファイルの中で前記ノードの値の最高の優先順位を有することを特徴とする、請求項３に記載の方法。
【請求項５】
変化率が有意でない時間間隔がより少ない環境プロファイルに圧縮されることを特徴とする、請求項１に記載の方法。
【請求項６】
相互参照表が、道路交通データ提供業者により用いられる道路網ＩＤを、ルーティング・ソフトウェアにより用いられる道路網ＩＤに対応付けることを特徴とする、請求項５に記載の方法。
【請求項７】
前記相互参照表が、現存する前記道路網において、リアルタイムデータに応じて修正を必要とするノードおよびリンクを識別するのに用いられることを特徴とする、請求項６に記載の方法。
【請求項８】
外部より提供される迂回路を統合することにより、前記修正されたリンクがリアルタイムデータに基づいてパス探索アルゴリズムをリアルタイム道路交通状況に順応できるようにすることを特徴とする、請求項７に記載の方法。
【請求項９】
前記道路網が細分基準を用いてクラスタツリーに分割されることを特徴とする、請求項２に記載の方法。
【請求項１０】
前記細分基準が平方マイルあたりの道路密度、交通渋滞要因、移動の頻度、または同様な基準の関数であることを特徴とする、請求項９に記載の方法。
【請求項１１】
クラスタから１つ以上の隣接するクラスタまでの移動時間が記憶されることを特徴とする、請求項９に記載の方法。
【請求項１２】
クラスタ間の移動時間が事前に計算され、および／またはリアルタイムデータ・プローブから動的に維持されることを特徴とする、請求項１１に記載の方法。
【請求項１３】
ノードから前記反対側の波面の前記中心までのコストを推定するための発見的方法が、前記ルーティングの方向へのノードのクラスタと前記反対側の波の前記中心のクラスタとの間の移動の概算コストで置換されることを特徴とする、請求項９に記載の方法。
【請求項１４】
相対する波面からのノードが繋がる場合、波面での概算コストが、出発地からの実際のパスの新しく計算されたコストにより置換されることを特徴とする、請求項１３に記載の方法。
【請求項１５】
請求項１から請求項１４までのいずれかの方法による、道路網でのルーティングを計算するための命令を記憶するコンピュータで読み取り可能な記憶媒体。
【請求項１６】
ヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理するためのモジュールと、
道路交通状況のリアルタイムデータに対応して前記ヒエラルキーにリンクを動的に追加するためのモジュールと、
リアルタイム道路交通データに基づいてルーティング移動コストを概算するためのクラスタ・ルーティング・システムと
を備えるシステム。
【請求項１７】
道路網でルーティングを計算するための方法であって、
ａ）リアルタイムデータに基づいて道路網の１つ以上の部分を普通よりも好適であると識別する工程と、
ｂ）前記道路網の前記１つ以上の部分を、一意的に識別可能なパスを成す位置のシーケンスとして表わす工程と、
ｃ）１つ以上のリンクを既に構築された道路のヒエラルキー網に追加するために、一意的に識別可能なパスを成す前記位置のシーケンスを用いる工程と、
ｄ）パス探索アルゴリズムが前記リアルタイムデータに順応できるようにする工程と
を備えることを特徴とする方法。
【請求項１８】
前記リアルタイムデータが道路交通状況を含むことを特徴とする、請求項１７に記載の方法。
【請求項１９】
相互参照表が道路交通データ提供業者により用いられる道路網ＩＤをルーティング・ソフトウェアにより用いられる道路網ＩＤに対応付けることを特徴とする、請求項１７に記載の方法。
【請求項２０】
前記相互参照表が、現存する前記道路網において、リアルタイムデータに応じて修正を必要とするノードおよびリンクを識別するのに用いられることを特徴とする、請求項１９に記載の方法。
【請求項２１】
道路交通状況に関するリアルタイムデータが外部の情報源によって供給されることを特徴とする、請求項１７に記載の方法。
【請求項２２】
一続きの道路に、複数のリンクがヒエラルキーの異なるレベルで追加されることができることを特徴とする、請求項１７に記載の方法。
【請求項２３】
新しいリンクが現存するリンクと同様に前記パス探索アルゴリズムに供給されることを特徴とする、請求項１７に記載の方法。
【請求項２４】
前記リアルタイムデータが外部より提供される迂回路を統合する工程を含むことを特徴とする、請求項１７に記載の方法。
【請求項２５】
１つの迂回路に、複数のリンクがヒエラルキーの異なるレベルで追加されることができ、前記複数のリンクは適切な優先順位を備え、各レベルに適するように構成されることを特徴とする、請求項１７に記載の方法。
【請求項２６】
ネットワークの大部分の移動時間が修正された場合に、１つ以上のプロファイルをヒエラルキーの既に存在する枝に徐々に集成する工程をさらに備えることを特徴とする、請求項１７に記載の方法。
【請求項２７】
請求項１７から請求項２６までのいずれかに記載の方法による道路網でのルーティングを計算するための命令を記憶するコンピュータで読み取り可能な記憶媒体。
【請求項２８】
道路網で移動時間最適化ルーティングの計算を改善するための方法であって、
ａ）前記道路網を論理的なクラスタツリーに分割する工程と、
ｂ）各クラスタに対して隣接するクラスタまでの移動時間を記憶する工程と、
ｃ）ノードから反対側の波面の中心までのコストを推定するための発見的方法の代わりに、ルーティングの方向へのノードのクラスタと前記反対側の波の前記中心のクラスタとの間の移動の概算コストを用いる工程と、
ｄ）目的地の波面ノードから伝わる各リンクに対するコストを、当該ノードへのクラスタ近似による到着時間に基づいた時間間隔から計算する工程と、
ｅ）相対する波面からのノードが繋がる場合、対象の波での概算コストが出発地からの実際のパスの新しく計算されたコストで置換される工程と
を備えることを特徴とする方法。
【請求項２９】
Ａ＊アルゴリズムを用いる工程をさらに備えることを特徴とする、請求項２８に記載の方法。
【請求項３０】
過去にあった道路交通情報とリアルタイムの道路交通情報とそして予測の道路交通情報とが、最小時間しか必要とせず、移動時間の精度を向上させる経路を選ぶことにより、運転者が時間を節約できるようにすることを特徴とする、請求項２８に記載の方法。
【請求項３１】
道路交通状況に関するリアルタイムデータがＲＤＳ ＴＭＣ、ＡＧＯＲＡ−Ｃ、ＶＩＣＳ、または別の位置参照方法のようにフォーマットされたデータを備えることを特徴とする、請求項２８に記載の方法。
【請求項３２】
細分基準を用いて前記道路網を論理的なクラスタツリーに分割する工程をさらに備えることを特徴とする、請求項２８に記載の方法。
【請求項３３】
前記細分基準が平方マイル当たりの道路密度、交通渋滞、移動の頻度、または同様な基準の関数であることを特徴とする、請求項２８に記載の方法。
【請求項３４】
クラスタ間の移動時間が、過去にあったデータまたは予測データから事前に計算され、および／またはリアルタイムデータ・プローブから動的に維持されることを特徴とする、請求項２８に記載の方法。
【請求項３５】
クラスタから隣接するクラスタまで、またはノードのクラスタから対象の波のクラスタまで、車が横断するのにどれぐらいの時間がかかるかを計算するために走行時プローブ・データが用いられることを特徴とする、請求項２８に記載の方法。
【請求項３６】
請求項２８から請求項３５までに記載された前記方法のいずれかによる、道路網における時間で最適化されたルーティングの計算を改善するための命令を記憶する、コンピュータで読み取り可能な記憶媒体。
【請求項３７】
道路網における、移動時間が最適化されたルーティングの計算を改善するための方法であって、
ａ）前記道路網を四分ツリーに分割する工程と、
ｂ）各四分に対して隣接する四分までの移動時間を記憶する工程と、
ｃ）ノードから反対側の波面の中心までのコストを推定するための発見的方法の代わりに、前記ルーティングの方向へのノードの四分と前記反対側の波の前記中心の四分との間の移動の概算コストを用いる工程と、
ｄ）目的地の波面ノードから伝わる各リンクに対するコストを、当該ノードへの四分近似による到着時間に基づいた時間間隔から計算する工程と、
ｅ）相対する波面からのノードが繋がる場合、対象の波での概算コストが出発地からの実際のパスの新しく計算されたコストで置換される工程と
を備えることを特徴とする方法。
【請求項３８】
Ａ＊アルゴリズムを用いる工程をさらに備えることを特徴とする、請求項３７に記載の方法。
【請求項３９】
道路交通状況に関するリアルタイムデータがＲＤＳ ＴＭＣ、ＡＧＯＲＡ−Ｃ、ＶＩＣＳ、または別の位置参照方法のようにフォーマットされたデータを備えることを特徴とする、請求項３７に記載の方法。
【請求項４０】
四分の間の移動時間が、過去にあったデータまたは予測データから事前に計算され、および／またはリアルタイムデータ・プローブから動的に維持されることを特徴とする、請求項３７に記載の方法。
【請求項４１】
平方マイル当たりの道路密度、交通渋滞、移動の頻度、または同様な基準の関数のような細分基準を用いて前記道路網を論理的なクラスタツリーに分割する工程をさらに備えることを特徴とする、請求項３７に記載の方法。
【請求項１】
道路網でルーティングを計算するための方法であって、
データベースにある道路のヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理する工程と、
前記１つ以上の環境プロファイルに対する近道を計算する工程と、
前記１つ以上の環境プロファイルに対する前記近道を前記データベースにまとめる工程と、
道路網の１つ以上の部分をリアルタイムデータに基づいて普通よりも好適であると識別する工程と、
道路網の前記１つ以上の部分を、一意的に識別可能なパスを成す位置のシーケンスとして表わす工程と、
前記位置のシーケンスを、前記データベースにある前記道路のヒエラルキーに関連付けるリンクを動的に追加する工程と、
ルーティング移動コストを概算するために、リアルタイム道路交通データに基づいてクラスタ・ルーティングを行う工程と
を備えることを特徴とする方法。
【請求項２】
ルーティング移動コストを概算するために、リアルタイム道路交通データに基づいてクラスタ・ルーティングを行う前記工程が、
前記道路網を論理的クラスタツリーに分割する工程と、
各クラスタに対して隣接するクラスタへの移動時間を記憶する工程と、
ノードから反対側の波面の中心までのコストを推定するための発見的方法の代わりに、前記ルーティングの方向へのノードのクラスタと前記反対側の波の前記中心のクラスタとの間の移動の概算コストを用いる工程と、
目的地の波面ノードから伝わる各リンクに対するコストを、当該ノードへのクラスタ近似による到着時間に基づいた時間間隔から計算する工程と、
相対する波面からのノードが繋がる場合、対象の波での概算コストが、出発地からの実際のパスの新しく計算されたコストで置換される工程と
を備えることを特徴とする、請求項１に記載の方法
【請求項３】
前記１つ以上のプロファイルに対する前記近道が前記データベースにまとめられることを特徴とする、請求項１に記載の方法。
【請求項４】
ノードが前記データベースにまとめられた前記１つ以上のプロファイルの中で前記ノードの値の最高の優先順位を有することを特徴とする、請求項３に記載の方法。
【請求項５】
変化率が有意でない時間間隔がより少ない環境プロファイルに圧縮されることを特徴とする、請求項１に記載の方法。
【請求項６】
相互参照表が、道路交通データ提供業者により用いられる道路網ＩＤを、ルーティング・ソフトウェアにより用いられる道路網ＩＤに対応付けることを特徴とする、請求項５に記載の方法。
【請求項７】
前記相互参照表が、現存する前記道路網において、リアルタイムデータに応じて修正を必要とするノードおよびリンクを識別するのに用いられることを特徴とする、請求項６に記載の方法。
【請求項８】
外部より提供される迂回路を統合することにより、前記修正されたリンクがリアルタイムデータに基づいてパス探索アルゴリズムをリアルタイム道路交通状況に順応できるようにすることを特徴とする、請求項７に記載の方法。
【請求項９】
前記道路網が細分基準を用いてクラスタツリーに分割されることを特徴とする、請求項２に記載の方法。
【請求項１０】
前記細分基準が平方マイルあたりの道路密度、交通渋滞要因、移動の頻度、または同様な基準の関数であることを特徴とする、請求項９に記載の方法。
【請求項１１】
クラスタから１つ以上の隣接するクラスタまでの移動時間が記憶されることを特徴とする、請求項９に記載の方法。
【請求項１２】
クラスタ間の移動時間が事前に計算され、および／またはリアルタイムデータ・プローブから動的に維持されることを特徴とする、請求項１１に記載の方法。
【請求項１３】
ノードから前記反対側の波面の前記中心までのコストを推定するための発見的方法が、前記ルーティングの方向へのノードのクラスタと前記反対側の波の前記中心のクラスタとの間の移動の概算コストで置換されることを特徴とする、請求項９に記載の方法。
【請求項１４】
相対する波面からのノードが繋がる場合、波面での概算コストが、出発地からの実際のパスの新しく計算されたコストにより置換されることを特徴とする、請求項１３に記載の方法。
【請求項１５】
請求項１から請求項１４までのいずれかの方法による、道路網でのルーティングを計算するための命令を記憶するコンピュータで読み取り可能な記憶媒体。
【請求項１６】
ヒエラルキーに統合された１つ以上の環境プロファイルに対するルーティング・データを事前に処理するためのモジュールと、
道路交通状況のリアルタイムデータに対応して前記ヒエラルキーにリンクを動的に追加するためのモジュールと、
リアルタイム道路交通データに基づいてルーティング移動コストを概算するためのクラスタ・ルーティング・システムと
を備えるシステム。
【請求項１７】
道路網でルーティングを計算するための方法であって、
ａ）リアルタイムデータに基づいて道路網の１つ以上の部分を普通よりも好適であると識別する工程と、
ｂ）前記道路網の前記１つ以上の部分を、一意的に識別可能なパスを成す位置のシーケンスとして表わす工程と、
ｃ）１つ以上のリンクを既に構築された道路のヒエラルキー網に追加するために、一意的に識別可能なパスを成す前記位置のシーケンスを用いる工程と、
ｄ）パス探索アルゴリズムが前記リアルタイムデータに順応できるようにする工程と
を備えることを特徴とする方法。
【請求項１８】
前記リアルタイムデータが道路交通状況を含むことを特徴とする、請求項１７に記載の方法。
【請求項１９】
相互参照表が道路交通データ提供業者により用いられる道路網ＩＤをルーティング・ソフトウェアにより用いられる道路網ＩＤに対応付けることを特徴とする、請求項１７に記載の方法。
【請求項２０】
前記相互参照表が、現存する前記道路網において、リアルタイムデータに応じて修正を必要とするノードおよびリンクを識別するのに用いられることを特徴とする、請求項１９に記載の方法。
【請求項２１】
道路交通状況に関するリアルタイムデータが外部の情報源によって供給されることを特徴とする、請求項１７に記載の方法。
【請求項２２】
一続きの道路に、複数のリンクがヒエラルキーの異なるレベルで追加されることができることを特徴とする、請求項１７に記載の方法。
【請求項２３】
新しいリンクが現存するリンクと同様に前記パス探索アルゴリズムに供給されることを特徴とする、請求項１７に記載の方法。
【請求項２４】
前記リアルタイムデータが外部より提供される迂回路を統合する工程を含むことを特徴とする、請求項１７に記載の方法。
【請求項２５】
１つの迂回路に、複数のリンクがヒエラルキーの異なるレベルで追加されることができ、前記複数のリンクは適切な優先順位を備え、各レベルに適するように構成されることを特徴とする、請求項１７に記載の方法。
【請求項２６】
ネットワークの大部分の移動時間が修正された場合に、１つ以上のプロファイルをヒエラルキーの既に存在する枝に徐々に集成する工程をさらに備えることを特徴とする、請求項１７に記載の方法。
【請求項２７】
請求項１７から請求項２６までのいずれかに記載の方法による道路網でのルーティングを計算するための命令を記憶するコンピュータで読み取り可能な記憶媒体。
【請求項２８】
道路網で移動時間最適化ルーティングの計算を改善するための方法であって、
ａ）前記道路網を論理的なクラスタツリーに分割する工程と、
ｂ）各クラスタに対して隣接するクラスタまでの移動時間を記憶する工程と、
ｃ）ノードから反対側の波面の中心までのコストを推定するための発見的方法の代わりに、ルーティングの方向へのノードのクラスタと前記反対側の波の前記中心のクラスタとの間の移動の概算コストを用いる工程と、
ｄ）目的地の波面ノードから伝わる各リンクに対するコストを、当該ノードへのクラスタ近似による到着時間に基づいた時間間隔から計算する工程と、
ｅ）相対する波面からのノードが繋がる場合、対象の波での概算コストが出発地からの実際のパスの新しく計算されたコストで置換される工程と
を備えることを特徴とする方法。
【請求項２９】
Ａ＊アルゴリズムを用いる工程をさらに備えることを特徴とする、請求項２８に記載の方法。
【請求項３０】
過去にあった道路交通情報とリアルタイムの道路交通情報とそして予測の道路交通情報とが、最小時間しか必要とせず、移動時間の精度を向上させる経路を選ぶことにより、運転者が時間を節約できるようにすることを特徴とする、請求項２８に記載の方法。
【請求項３１】
道路交通状況に関するリアルタイムデータがＲＤＳ ＴＭＣ、ＡＧＯＲＡ−Ｃ、ＶＩＣＳ、または別の位置参照方法のようにフォーマットされたデータを備えることを特徴とする、請求項２８に記載の方法。
【請求項３２】
細分基準を用いて前記道路網を論理的なクラスタツリーに分割する工程をさらに備えることを特徴とする、請求項２８に記載の方法。
【請求項３３】
前記細分基準が平方マイル当たりの道路密度、交通渋滞、移動の頻度、または同様な基準の関数であることを特徴とする、請求項２８に記載の方法。
【請求項３４】
クラスタ間の移動時間が、過去にあったデータまたは予測データから事前に計算され、および／またはリアルタイムデータ・プローブから動的に維持されることを特徴とする、請求項２８に記載の方法。
【請求項３５】
クラスタから隣接するクラスタまで、またはノードのクラスタから対象の波のクラスタまで、車が横断するのにどれぐらいの時間がかかるかを計算するために走行時プローブ・データが用いられることを特徴とする、請求項２８に記載の方法。
【請求項３６】
請求項２８から請求項３５までに記載された前記方法のいずれかによる、道路網における時間で最適化されたルーティングの計算を改善するための命令を記憶する、コンピュータで読み取り可能な記憶媒体。
【請求項３７】
道路網における、移動時間が最適化されたルーティングの計算を改善するための方法であって、
ａ）前記道路網を四分ツリーに分割する工程と、
ｂ）各四分に対して隣接する四分までの移動時間を記憶する工程と、
ｃ）ノードから反対側の波面の中心までのコストを推定するための発見的方法の代わりに、前記ルーティングの方向へのノードの四分と前記反対側の波の前記中心の四分との間の移動の概算コストを用いる工程と、
ｄ）目的地の波面ノードから伝わる各リンクに対するコストを、当該ノードへの四分近似による到着時間に基づいた時間間隔から計算する工程と、
ｅ）相対する波面からのノードが繋がる場合、対象の波での概算コストが出発地からの実際のパスの新しく計算されたコストで置換される工程と
を備えることを特徴とする方法。
【請求項３８】
Ａ＊アルゴリズムを用いる工程をさらに備えることを特徴とする、請求項３７に記載の方法。
【請求項３９】
道路交通状況に関するリアルタイムデータがＲＤＳ ＴＭＣ、ＡＧＯＲＡ−Ｃ、ＶＩＣＳ、または別の位置参照方法のようにフォーマットされたデータを備えることを特徴とする、請求項３７に記載の方法。
【請求項４０】
四分の間の移動時間が、過去にあったデータまたは予測データから事前に計算され、および／またはリアルタイムデータ・プローブから動的に維持されることを特徴とする、請求項３７に記載の方法。
【請求項４１】
平方マイル当たりの道路密度、交通渋滞、移動の頻度、または同様な基準の関数のような細分基準を用いて前記道路網を論理的なクラスタツリーに分割する工程をさらに備えることを特徴とする、請求項３７に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公表番号】特表２０１１−５２６６７８（Ｐ２０１１−５２６６７８Ａ）
【公表日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願番号】特願２０１１−５１４６３９（Ｐ２０１１−５１４６３９）
【出願日】平成２１年４月９日（２００９．４．９）
【国際出願番号】ＰＣＴ／ＵＳ２００９／０３９９８３
【国際公開番号】ＷＯ２００９／１５８０５８
【国際公開日】平成２１年１２月３０日（２００９．１２．３０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
２．リナックス
【出願人】（５０７３８８８８９）テレ アトラス ノース アメリカ インコーポレイテッド (23)
【Ｆターム（参考）】
【公表日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願日】平成２１年４月９日（２００９．４．９）
【国際出願番号】ＰＣＴ／ＵＳ２００９／０３９９８３
【国際公開番号】ＷＯ２００９／１５８０５８
【国際公開日】平成２１年１２月３０日（２００９．１２．３０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
２．リナックス
【出願人】（５０７３８８８８９）テレ アトラス ノース アメリカ インコーポレイテッド (23)
【Ｆターム（参考）】
[ Back to top ]