タイリングを用いた最適ルートの決定
【課題】道路網などにおける最適ルートを決定する方法およびシステムを確立すること。
【解決手段】最適ルートを計算するために道路セグメントデータを前処理する方法、前処理された道路セグメントデータに基づいて、最適ルートを決定する方法、および、対応するシステムが提供される。道路セグメントデータを前処理する方法に従うと、タイリングが提供され、ランク情報（ｒ）が、タイリング情報に基づいて、道路セグメント（ｖ）に対して、計算される。このランク情報（ｒ）は、タイリングのタイルを結ぶ最適ルートに対する道路セグメントの妥当性の尺度となる。地図上の相対位置に基づき計算されるランク情報（ｒ）を用いて、引き続く最適ルート計算にランク情報情報が提供される。これによって、例えば、車両におけるナビゲーションシステムにおいて、最適ルートの計算を効率的に実行することが可能になる。
【解決手段】最適ルートを計算するために道路セグメントデータを前処理する方法、前処理された道路セグメントデータに基づいて、最適ルートを決定する方法、および、対応するシステムが提供される。道路セグメントデータを前処理する方法に従うと、タイリングが提供され、ランク情報（ｒ）が、タイリング情報に基づいて、道路セグメント（ｖ）に対して、計算される。このランク情報（ｒ）は、タイリングのタイルを結ぶ最適ルートに対する道路セグメントの妥当性の尺度となる。地図上の相対位置に基づき計算されるランク情報（ｒ）を用いて、引き続く最適ルート計算にランク情報情報が提供される。これによって、例えば、車両におけるナビゲーションシステムにおいて、最適ルートの計算を効率的に実行することが可能になる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適ルートの決定に関する。特に、本発明は、道路セグメントデータを前処理する方法および対応するシステム、前処理された道路セグメントデータに基づいて、最適ルートを決定する方法および対応するシステム、ならびに、ナビゲーションシステムに関する。
【背景技術】
【０００２】
所定の出発点から所定の目的地に至る最適ルートを求めることは、カーナビゲーションシステムあるいは最適ルート情報を提供する他のシステムの主要機能の一つである。
【０００３】
幾つかのアルゴリズムが、最適ルートを求める問題の解決のために、知られているが、これらアルゴリズムを直接、欧州の一国やあるいは米国の道路網のような道路網への適用は、実現できないことが多い。なぜなら、これら道路網には、道路セグメントおよび道路セグメント頂点（ｖｅｒｔｅｘ）が膨大な数あるからである。頂点の数は、百万のオーダーか、それ以上になり得る。なぜなら、カーナビゲーションシステムにおけるメモリおよびルーチンに制約があるために、長距離最適ルート探索に標準的な最短経路アルゴリズムを直接用いることは、実現できないからである。
【０００４】
例えば、ドイツにおける「アウトバーン（Ａｕｔｏｂａｈｎ）」、「連邦道路（Ｂｕｎｄｅｓｓｔｒａｓｓβｅ）」および「郡道（Ｋｒｅｉｓｓｔｒａβｅ）」、英国における「高速道路（Ｍｏｔｏｒｗａｙ）」、「Ａ道路（Ａ ｒｏａｄ）」および「Ｂ道路（Ｂ ｒｏａｄ）」のように、道路網には、道路分類によって表わされる自然な階層構造があることが、最適ルート探索の複雑さを減らすために利用されることが多い。最適ルートの決定は、幾つかのサブタスクに分解される。すなわち、出発地から、例えば、高速道路ジャンクションまたは高速で長距離移動可能な他の道路のジャンクションまでのルート、および、目的地から、例えば、別の高速道路ジャンクションまたは高速で長距離移動可能な他の道路のジャンクションまでのルートそれぞれの２つの短距離ルートを求めるタスクと、使用する高速道路または高速で長距離移動のみを可能とする他の道路におけるこれら２つの高速道路ジャンクション間の最適ルートを求めるタスクである。
【０００５】
道路網の階層構造は、標準化されたＧＤＦ（Ｇｅｏｇｒａｐｈｉｃ Ｄａｔａ Ｆｉｌｅ）形式を有するマップによっても反映される。ここで、全ての道路セグメントは、機能的道路階級（ＦＲＣ）と呼ばれる属性を有し、このＦＲＣは、道路階層を定義し、地域的に重要な道路から国家的あるいは国際的に重要な道路に分類することを意図している。
【０００６】
特許文献１は、出発点と目的点との間の行程を決定するプロセスを開示している。ここで、道路網は、少なくとも２つのレベルに分類され、格納されている。すなわち、通行され得る道路全ては、低レベルに含まれ、低レベルの道路網の異なる地域を結ぶ道路は、高レベルに含まれる。典型的には、高レベルは、高速で長距離移動可能な高速道路のような道路を含む。
【０００７】
しかしながら、道路セグメントの階層構造は、人間の専門家によって、指定されるので、決定されたルートが、真に最適でないこともあることに留意すべきである。さらに、最速ルートを狙いとするＦＲＣのような標準的道路階層に頼っても満足いかないこともある。それゆえ、最短ルートあるいは他のルート選択を計算するのに不適切なこともある。それゆえ、人間の専門家によって指定された道路重要性を定量化する値は、不十分であり得る。むしろ、地図上の相対位置（ｍａｐ ｇｅｏｍｅｔｒｙ）から道路セグメント属性を決定する方法が、望ましい。
【０００８】
特許文献２は、ソースノードから目的地ノードへの望ましい経路を決定する方法を開示している。特許文献２では、道路網の各ノードと関連する範囲測定基準（ｒｅａｃｈ ｍｅｔｒｉｃ）の証印（ｉｎｄｉｃｉａ）を含む予備的なルーティングのデータセットが、提供される。所定のノードに対する範囲測定基準は、道路網の任意の許容可能な他のノードの間の望ましい経路の一部をなす、その所定ノードのポテンシャルを示す。
【特許文献１】欧州特許第０ ３２３ ４８５号明細書
【特許文献２】国際公開第０３／０７９１５５号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、それでもなお、地図上の相対位置に基づいて決定される道路セグメント属性に基づく最適ルート決定方法を提供する必要性がある。特に、このような道路セグメント属性が、たとえ大きな道路網であっても効率的に決定され得る最適ルートの決定方法に対する必要性がある。
【課題を解決するための手段】
【００１０】
（発明の概要）
本発明に従うと、この必要性は、請求項１に記載の道路セグメントデータを前処理する方法、請求項１９に記載の最適ルートを決定する方法、請求項２８に記載の道路セグメントデータを前処理するシステム、請求項３６に記載の最適ルートを決定するシステム、および、請求項４１に記載のナビゲーションシステムによって、対処される。従属の請求項は、本発明の好ましい実施形態あるいは有利な実施形態を規定する。
【００１１】
本発明に従って、道路セグメントデータを前処理する方法は、該道路セグメントデータを提供するステップと、該道路セグメントが含まれるエリアをカバーするタイリングを定義するステップと、該タイリングのタイルを結ぶ最適ルート用の該道路セグメントの妥当性を定量化するランク情報を、道路セグメントに対して決定するステップとを包含する。この道路セグメントデータを前処理する方法は、最適ルートの決定前に実行され、道路セグメントのランク情報が提供されると、最適ルートを迅速に求める（ｅｘｐｅｄｉｔｅ）。道路セグメントデータを前処理する方法は、主として、カーナビゲーションシステムで、最適ルート決定の一部として実行される。道路セグメントデータを前処理する方法は、自動的に行われることが好ましい。タイリングを定義するステップによって、ランク情報が効率的に決定できるようになる。
【００１２】
様々な実施形態に従うと、ランク情報は、タイリングに基づき、そのタイリングに依存して決定される。実施形態において、道路セグメントが任意の最適ルートに含まれるかどうかによって、道路セグメントの「妥当性」が定量化される。その最適ルートは、所定のタイル数を通過するルートか、または、出発タイルから所定の距離離れ、出発タイルから目的地タイルに延びるルートか、あるいは、出発タイルと目的地タイルとが、その道路セグメントが位置するタイルから所定の最低距離を有して、出発タイルから目的地タイルに延びるルートである。
【００１３】
以下の本明細書の様々な実施形態の記述から明らかになるように、ランク情報は様々な方法で定義され、決定され得る。好ましい実施形態においては、ランク情報は、タイリングのタームで測定された最適ルートの長さに対する尺度を示す。その尺度には、道路セグメントが、依然として含まれている。
【００１４】
ランク情報は、タイル端部（ｅｄｇｅ）に位置する点を結ぶ最適ルートに対する道路セグメントの妥当性を定量化することが好ましい。これによって、考慮されるべき潜在的な出発点と目的地の総数を減らし、効率的に迅速にランク情報を決定できる。
【００１５】
タイルまたは道路セグメントは、各道路セグメントが、タイリングの多くとも１つのタイルに含まれるように定義されることが、さらに好ましい。すなわち、道路セグメントが、その頂点を除いては、タイル内側の中に含まれるようなタイルは、１つのみしかないように、各道路セグメントに対して、定義されることが好ましい。このようなタイリングの定義は、各道路セグメントを１つのタイルにユニークに割り当てることを可能とし、それゆえ、タイリング情報に基づいたランク情報を決定できる。こうして、また、タイリングの定義は、道路セグメントを含むタイルを特定する各道路セグメントに対して、追加属性の意味でも提供され得る。各道路セグメントがタイリングのタイルの多くとも１つにしか含まれないように定義することは、元々の道路セグメントとタイル端部との交点に補助の頂点を導入することで、達成される。それゆえ、このようにタイリングを定義することは、道路セグメントを再定義するステップも含み得る。
【００１６】
道路セグメントに対して、ランク情報を決定するステップは、道路セグメントを含むタイルを決定するステップと、道路セグメントを含むタイルから、少なくとも所定のタイル距離を有する第一のタイルを選択するステップと、道路セグメントが、第一のタイルに位置する出発道路セグメント（すなわち、第一のタイルの内部または端部に位置する出発道路セグメントの頂点）を有する最適ルートに含まれるかどうかを決定するステップとを包含する。これらのステップに従って、ランク情報は、最適ルート用の道路セグメントの妥当性に対する尺度として決定される。その最適ルートは、その道路セグメントから少なくとも所定のタイル距離を有するタイルに位置する出発道路セグメントを有する。最適ルートの決定は、該第一のタイルの端部に位置する出発点を有するルートに制限され得る。可能な出発点の数を制限することによって、ランク情報の決定は、より効率的に実行され得る。
【００１７】
ランク情報を決定するステップは、ランク情報が決定されるべき道路セグメントを含むタイルから、少なくとも所定のタイル距離を有する第二のタイルを選択するステップをさらに包含し得る。ここで、最適経路の目的地道路セグメントは、この第二のタイルに位置する。こうして、ランク情報は、最適ルート用の道路セグメントの妥当性に対する尺度となる。この最適ルートにおいては、出発道路セグメントおよび目的地道路セグメントの双方が、ランク情報が決定されるべき道路セグメントから少なくとも所定のタイル距離を有するタイルに位置する。可能な目的地道路セグメントは、第二のタイルの端部に位置する頂点を有する目的地道路セグメントに制限されることが好ましい。可能な目的地の数を制限することで、ランク情報の決定は、さらに、より効率的に実行され得る。
【００１８】
ランク情報を決定するステップは、さらに、ランク情報が決定されるべき道路セグメントを含むタイルから所定の距離を有する全ての可能な第一および第二のタイルを選択するステップと、その道路セグメントが、第一のタイルのうちの１つのタイルにある出発道路セグメントと、第二のタイルのうちの１つのタイルにある目的地道路セグメントとを結ぶ最適ルートに含まれるかどうかを決定するステップとを含む。ここで、再び、最適ルート探索は、第一のタイルの端部に位置する出発点と、第二のタイルの端部に位置する目的地とに制限され得る。このランク情報を決定する方法によって、道路セグメントが、特定の要求に合う任意の最適経路に含まれるかどうかを決定でき、こうして、一般的な道路セグメント属性を提供できる。
【００１９】
ランク情報を決定するステップは、道路セグメントが上述したような最適ルートに含まれる所定のタイル距離の最大を決定するステップをさらに包含し得る。こうして、ランク情報は、道路セグメントを依然として含む最長の最適ルートと、それゆえに、道路セグメントが依然として重要な長距離ルートの長さとを定量化する。さらに、ランク情報はタイリングに基づき決定されるので、ランク情報は効率的に決定され得る。
【００２０】
ランク情報を決定するステップは、所定のタイル距離の値を増やして、連続的に実行されることが好ましい。それは、所定のタイル距離の大きい値に対して、ランク情報の決定がより複雑化したステップにおいても、所定のタイル距離の小さな値に対する先行するステップで得られた結果に基づいて、実行できるようにするためである。特に、ランク情報を決定するのに、必要とされる最適ルート探索は、道路セグメントのサブセット上で実行され得る。このサブセットは、所定のタイル距離の小さな値に対して得られた結果に基づいて、選択される。こうして、以前に得られた結果に依存する道路セグメントを消去して、ランク情報の複雑さを減らすことが実現でき、それゆえ、引き続くステージで、ランク情報の決定が容易になる。
【００２１】
ランク情報を決定する後のステージにおいて、所定のタイル距離の値が増えるに伴い、タイルサイズは、増えることも、増えないこともあり得る。有利な実施形態においては、ランク情報が幾つかの連続的なランク値に対して決定された後、タイリングは粗調整され、その一方で、道路網は同時に再定義される。規則的なタイリングに対して、粗調整は、タイルの端部長さを増やすことからなり得る。道路網の再定義は、今までに決定された最大のランク情報を有する道路セグメントのサブセットとして、新たな道路網を定義することからなり得る。これらのステップが繰り返さられ得る結果として、粗調整されたタイリングの階層およびランク値の関連する階層が形成される。好ましい実施形態においては、３回または４回連続的に増やしたランク値に対して、ランク情報を決定した後に、正方形タイリングのタイル端部の長さが２倍になり、道路網は再定義される。これらの実施形態において、次いで、道路網は、粗調整する階層の以前のレベルに対して決定されたように、少なくとも３または４のランク情報を有する道路セグメントのセットとして、再定義される。
【００２２】
道路セグメントデータを前処理する方法は、道路セグメント重み付けファクタを提供するステップをさらに包含し得る。このファクタは、ランク情報を決定するステップの間に考慮される。このような重み付けファクタによって、追加の道路セグメント属性を考慮に入れることが可能となる。可能な重み付けファクタは、道路セグメント長、道路セグメントを通過する時間、あるいは、特徴的な道路セグメント移動速度と組み合わせた道路セグメント長を定量化する。重み付けファクタは、また、道路セグメントがトンネル区間あるいはフェリー区間を含むかどうかにも依存し得る。重み付けファクタは、また、道路セグメント上の移動方向にも依存し得る。追加的に、あるいは、代替的に、重み付けファクタは、道路セグメントの頂点との関連から提供され得る。この場合、頂点の重み付けファクタは、所定のルートと関連するコスト関数を計算するために、道路セグメントの重み付けファクタへの追加として、あるいは、その代替として、考慮され得る。道路セグメントの頂点と関連する重み付けファクタを提供することで、例えば、道路セグメントの頂点で運転方向を変更するのに関連する時間が考慮され得る。それゆえ、重み付けファクタによって、様々な移動の選択において、最適ルートの決定、あるいは、引き続く最適ルートの決定で用いるための道路セグメントデータの前処理が可能となる。
【００２３】
ランク情報を決定するステップは、各道路セグメントに対して、実行され得ることが好ましい。次いで、ランク情報は、引き続く最適ルートの決定の中で、各道路セグメントに提供され得る。こうして、特定の最適ルートの決定に対して、全ての道路セグメントの妥当性を決定することが可能となる。
【００２４】
ランク情報を定義するステップが、上述した実施形態の幾つかに記載したように、最適ルート探索を含む場合、この最適ルート探索は、ＤｉｊｋｓｔｒａのアルゴリズムまたはＡ＊アルゴリズム、あるいは、グラフ理論で知られる任意の他の最適経路アルゴリズムを使用して実行され得る。こうして、ランク情報の効率的決定が可能になる。
【００２５】
タイリングを決定するステップは、各タイルに端部データまたは頂点データを提供するステップを包含し得る。代替的に、タイリングを決定する方法は、例えば、タイル形状およびサイズ、ならびに、第一のタイル位置を特定することによって、特定され得る。このタイリングの定義における柔軟性は、タイリングを定義する方法の選択を可能とする。これは、ストレージまたはランタイムの要求に対する観点から、最も都合がよい。
【００２６】
タイルサイズは、タイリング全体にわたって異なり得る。タイルサイズは、道路セグメントが含まれるエリアにおける地域の道路セグメント密度または道路頂点密度によって、選択され得る。こうして、異なるタイルで、１つのタイル内の道路セグメントまたは頂点の数が、同程度になり得て、その結果、計算の複雑さも同程度になり得る。
【００２７】
タイルは、多角形の形状になるように選択され得る。特に、タイルは、長方形の形状であり得る。好ましくは、タイルは正方形の形状が選択される。この場合、どのタイルに、所定の道路セグメントまたは道路頂点が含まれるかを決定することが、特に簡単になる。
【００２８】
ランク情報を決定するステップのために、タイル距離が定義される必要がある場合、様々な定義が使用され得る。２つのタイル間のタイル距離は、タイル距離が整数となるように、２つのタイルを結ぶ経路を通過するタイル端部またはタイル頂点の最小数として定義されるのが好ましい。このことは、さらなる処理において、都合がよい。代替的に、タイル距離は、タイルの中心またはタイルの角、あるいは、任意の他の測定基準の間の距離として、定義され得る。
【００２９】
道路セグメントデータを前処理する方法は、１つのタイルに含まれる道路セグメントのシーケンスを新たな道路セグメントに、相互結合するステップをさらに包含し得る。重み付けファクタが道路セグメントおよび／または道路セグメント頂点に提供される場合、このステップは、典型的には、重み付けファクタを新たな重み付けファクタに相互結合するステップを伴う。この道路セグメントを新たなより長い道路セグメントへの相互結合によって、引き続く最適ルート探索における計算の複雑さを緩和できる。
【００３０】
ランク値が、増加するランク値に対して、再帰的に決定される場合、道路セグメントのシーケンスを新たな道路セグメントに相互結合するステップは、また、中間ステージでも実行され得る。こうして、引き続くステップでの計算の複雑さをさらに緩和できる。同様に、ランク情報が、上述のような粗調整されたタイリングの階層に基づいて決定される場合、道路セグメントを相互結合するステップは、道路網が再定義されたときに、実行され得る。
【００３１】
ランク値が、増加するランク値に対して、再帰的に決定される場合、道路セグメントデータを前処理する方法は、所定の道路セグメントのランク情報が決定された後、タイリングを粗調整するステップを包含し得ることが好ましい。これによって、タイルの総数を減らすことができ、こうして、ランク情報の効率的な決定がさらに容易なる。
【００３２】
データを前処理する方法は、道路セグメントを備える道路網の観点から記載されてきたが、この方法は道路網に限定されない。むしろ、上述の局面または実施形態の任意の一つに従う方法は、複数の端部を含む任意のグラフ上で実行され得る。こうして、グラフは道路網として解釈されるべきであり、グラフの端部は、上述の観点で道路セグメントとして解釈されるべきである。グラフは、方向性があることも、ないこともあり得る。本発明が適用され得るグラフの追加の例としては、電力網の電線、または、通信のデータライン、あるいは、データネットワークを含む。
【００３３】
道路セグメントデータを前処理する方法は、引き続く最適ルートの決定での使用のために、決定されたランク情報を出力するステップを包含することが好ましい。ランク情報を出力するステップは、また、道路セグメントデータを格納するステップを含むことが好ましい。ここで、道路セグメントデータは、道路セグメントおよび／または道路セグメントを含むタイルに対応するランク情報に従って、アレンジされている。タイルサイズが、ランク情報を決定する間に、変動する場合、道路セグメントデータは、ランク値および／または対応するタイルに加えて、タイルサイズにも従って、さらにアレンジされ得る。出力された道路セグメントデータは、道路セグメント属性として決定されたランク情報を含む。追加のデータセットは、出力された道路セグメントデータを含むファイルまたはデータベースで、タイルに対応する道路セグメントデータの位置に関する情報を含んで提供されることが、さらに好ましい。
【００３４】
本発明に従って、出発点から目的地への最適ルートを決定する方法は、道路セグメントデータを提供するステップと、本発明の道路セグメントデータを前処理する方法に従って決定されたランク情報データを提供するステップと、該道路セグメントデータおよび該ランク情報データに基づいて、出発点から目的地への最適ルートを決定するステップとを包含する。ランク情報データを提供することによって、最適ルートの決定は、より効率的に、より迅速に実行され得る。ランク情報は、全ての道路セグメントに、提供されることが好ましい。代替的に、ランク情報は、道路セグメントのサブセットのみに、提供され得る。ランク情報は、追加の道路セグメント属性として、道路セグメントデータに組み込まれることも、あるいは、個別に提供されることもあり得る。
【００３５】
好ましい実施形態において、最適ルートを決定する方法は、ランク情報に基づいて、道路セグメントのサブセットを選択するステップを包含する。最適ルートを決定するステップは、この道路セグメントのサブセットに基づいて、実行される。道路セグメントのサブセットを選択することによって、最適ルート探索における計算の複雑さは緩和される。
【００３６】
最適ルートを決定する方法は、道路セグメントが含まれるエリアをカバーするタイリングを定義するステップを包含することが好ましい。この道路セグメントの各道路セグメントは、そのタイリングの多くても１つのタイルの中にしか含まれないように、タイリングが定義されること、あるいは、道路セグメントが定義されることが、さらに好ましい。タイリングは、道路セグメントのランク情報を決定するのに対して使用されるタイリングと同一であることが、さらになお好ましい。タイリングを定義することで、最適ルートの決定は、さらに単純化される。好ましい実施形態において、最適ルートを決定するのに使用されるタイリングは、データを前処理するのに使用されるタイリングと同一である。同様に、好ましい実施形態において、粗調整されたタイリングの階層が、データを前処理するために使用される場合、同じ粗調整されたタイリングの階層が、最適ルートを決定するために使用される。これらの好ましい実施形態に従うと、ほぼ最適なルートだけでなく、正しい最適ルートを決定することが可能になる。
【００３７】
道路セグメントのサブセットを選択するステップは、次いで、出発点を含む出発タイルを決定するステップと、目的地を含む目的地タイルを決定するステップと、道路セグメントランク情報、および、道路セグメントを含むタイルの出発タイルまたは目的地タイルからのタイル距離に基づいて、道路セグメントを道路セグメントのサブセットに含めるステップとを包含する。次いで、道路セグメントのサブセットに組み込まれるべき道路セグメントの選択は、タイリングに対して、長距離最適ルート用の道路セグメントの妥当性をランク情報が定量化するという事実を反映し得る。それゆえ、最適ルートの正確な決定が可能となる。
【００３８】
特に、好ましい実施形態において、道路セグメントのサブセットを選択するステップは、出発点を含む出発タイルから、目的地を含む目的地タイルまでの出発−目的地タイル距離を決定するステップと、出発−目的地のタイル距離に基づく最小ランク値を選択するステップと、最小ランク値以上のランク値を有する全ての道路セグメントを、道路セグメントのサブセットに含めるステップとを包含する。より詳細には、最小ランク値は、出発−目的地のタイル距離を２で除算し、１を加算したフロア以下から選択され得る。それゆえ、大きな出発−目的地のランク値に対して、最小ランク値は、大きくなるように選択され得る。その結果として、サブセットに含まれる道路セグメントの数は、道路セグメントの総数より、実質的に小さくなる。
【００３９】
好ましい実施形態に従って、道路セグメントのサブセットを選択するステップは、出発タイルまたは目的地タイルからの距離が、最低ランク値から１を減じた値以下を有するタイルを決定するステップと、そのタイルに含まれる道路セグメントに対するランク情報を取り出すステップと、そのランク値が、そのタイルの出発タイルからのタイル距離と、そのタイルの目的地タイルからのタイル距離とのそれぞれのうちの小さなタイル距離以上であれば、道路セグメントを道路セグメントのサブセットに含めるステップとをさらに包含する。
【００４０】
道路セグメントのサブセットに基づき、最適ルートを決定するステップに対して、道路セグメント重み付けファクタおよび／または道路セグメント頂点重み付けファクタが、例えば、道路セグメント属性として、提供され得る。道路セグメント重み付けファクタおよび／または道路セグメント頂点重み付けファクタは、道路セグメントデータを前処理するために提供されたものと、同一であることが好ましい。前処理の段階（ｐｈａｓｅ）と同様に、重み付けファクタは、異なる移動の選択に基づいて、最適ルートを決定することができる。再び、重み付けファクタは、道路セグメントを通過する方向に依存し得る。好ましい実施形態において、道路セグメント重み付けファクタおよび／または道路セグメント頂点重み付けファクタは、道路セグメントデータを前処理する間に使用されたものと、同一である。それは、正確な最適ルートが決定できるようにするためである。
【００４１】
最適ルートを決定するステップは、ＤｉｊｋｓｔｒａのアルゴリズムまたはＡ＊アルゴリズム、あるいは、グラフ理論で知られる任意の他の最適経路アルゴリズムを使用して実行され得る。こうして、最適ルートの効率的な決定が可能になる。Ａ＊アルゴリズムが使用された場合、最適ルートのコストの下限に対する見積もりは、距離ベースのルート探索に対してはエア距離によって、時間ベースのルート探索に対しては特徴的な移動速度でエア距離を除算することによって得られる。
【００４２】
最適ルートを決定する方法は、車両位置データを受信するステップと、その車両位置から目的地への最適ルートを決定するステップとを、さらに包含し得る。この方法に従うと、運転手は、自分の現在地をはっきりと決定できない場合ですら、自分の目的地に行くために、案内され得る。
【００４３】
最適ルートを決定する方法が、道路セグメントを含む道路網の観点から記載されてきたが、この方法は道路網に限定されない。むしろ、上述の局面または実施形態の任意の一つに従う方法は、複数のエッジ部を含む任意のグラフ上で実行され得る。ここで、グラフは道路網として解釈されるべきであり、グラフのエッジ部は、上述の観点からは道路セグメントとして解釈されるべきである。
【００４４】
本発明に従う道路セグメントデータを前処理するシステムは、道路セグメントデータを含む第一のストレージユニットと、タイリング定義データを含む第二のストレージユニットと、該道路セグメントデータのサブセットを格納する作業メモリユニットと、該作業メモリユニットに格納されたデータを処理し、該タイリングに基づいて、道路セグメントのランク情報を決定するのに、適合された処理ユニットとを備える。ここで、該ランク情報は、該タイリングのタイルを結ぶ最適ルートに対する該道路セグメントとの重要度を定量化する。第一および第二のストレージユニットは、個別のデバイスでも、単一のデバイスでもあり得る。タイリング定義データは、数学的関数の形式で提供され得て、これによって、特定の点を含むタイルを決定できる。このシステムは、本発明に従う道路セグメントデータを前処理する方法を実行するように適合されることが好ましい。作業メモリユニットはタイリング定義データのサブセットを、また、格納できるようにも適合されることが、さらに好ましい。このシステムは、タイリングに基づいて、道路セグメントランク情報を決定するように適合される。
【００４５】
道路セグメントデータを前処理するシステムは、処理ユニットに結合され、決定されたランク情報を格納するように適合された追加作業メモリユニットを、さらに備えることが好ましい。追加作業メモリユニットに格納されたランク情報は、ストレージユニットの中に出力されることも、引き続くステップで使用されることもあり得る。追加作業メモリユニットの後者の機能は、ランク情報が再帰的方法に従って決定される場合、特に重要である。この再帰的方法は、短距離移動にのみ重要な道路セグメントから開始し、長距離移動にも妥当性ある道路セグメントまで行う。追加作業メモリユニットは、作業メモリユニットと同一のことも、異なることもあり得る。すなわち、作業メモリユニットと追加作業メモリユニットとは、別個のデバイスでも、単一のデバイスでもあり得る。
【００４６】
処理ユニットは、ランク情報を決定するための追加作業メモリユニットに格納されたデータを処理するように適合され得る。再び、このことは、ランク値を増加に対して、連続的にランク情報が決定される場合、特に重要となる。
【００４７】
作業メモリユニットは、ランク情報を決定するステップの間、最適ルートの決定に必要とされる道路セグメントデータのサブセットを格納するのに、十分なストレージ容量を有することが好ましい。特に、作業メモリユニットは、１つのタイルの道路セグメントデータ、あるいは、道路セグメントのサブセットで適切に選択されたサブセットの道路セグメントデータを格納するのに十分な容量を有することが好ましい。これらの道路セグメントデータは、特徴的なタイリングおよび特徴的な道路セグメント密度のために、少なくとも１つの所定の道路セグメントに対するランク情報を決定するために必要とされる。作業メモリユニットは、そのように設計されると、処理ユニットは、ストレージユニットへのアクセスする頻度がより少なくてすみ、ランク情報に必要とされるランタイムも短縮される。
【００４８】
道路セグメントデータを前処理するシステムは、決定されたランク情報を出力するための出力ユニットをさらに備えることが好ましい。これによって、決定されたランク情報はアクセス可能となり、引き続く最適ルートの決定で、すなわち、ナビゲーションシステムで使用される。出力ユニットは、道路セグメントデータの前処理のために、取り外し可能なストレージ媒体（例えば、ＣＤ−Ｒ／Ｗ）あるいはシステムに組み込まれたストレージ媒体に、ランク情報を出力するように設計され得る。すなわち、システムは、決定されたランク情報を格納するための第三のストレージユニットを包含し得る。このストレージユニットは、こうして、追加ランク情報を決定するための処理ユニットによっても、また、アクセスされるように適合され得る。
【００４９】
道路セグメントデータを前処理するシステムは、並列して、道路セグメントのランク情報を決定するように適合される複数の処理ユニットを備えることが好ましい。道路セグメントのランク情報の計算は、少なくとも所定のタイルに含まれる道路セグメントに対して、ローカルなタスクである。それは、この計算が、このタイルのみの特定の近傍における他の道路セグメントと関連する情報を必要とするという意味からである。このようなランク情報決定の並列化は、ランタイム要求の観点で有効である。さらに、本発明に従う道路セグメントデータを前処理する方法は、並列化によく適合される。様々な並列化スキームがコンピュータクラスタあるいはグリッド（例えば、ピアツーピア（ｐｅｅｒ−ｔｏ−ｐｅｅｒ）またはマスタワーカ（ｍａｓｔｅｒ−ｗｏｒｋｅｒ）スキーム）を使用して、実現され得る。後者の場合において、道路セグメントデータを前処理するシステムは、マスタシステムと、少なくとも１つのワーカシステムとを備える。ここで、このマスタシステムは、タイルにわたって繰り返すこと、および、ワーカシステムに情報を渡すことに適合される。この少なくとも１つのワーカシステムは、マスタシステムによって選択されたタイルに含まれる道路セグメントのランク情報を決定するように適合される。ランク情報が再帰的方法を使用して決定されるべきである場合、マスタシステムは、タイル近傍サイズの増大にわたって、繰り返しを実行するように、さらに適合される。好ましい実施形態において、マスタシステムは、問題を小さなジョブに分解する。これらジョブは、複数のワーカシステムに委託される。特定的には、マスタシステムから少なくともタイル情報を受け取れば、ワーカシステムは、そのタイルの含まれる道路セグメントのランク情報を決定する。その決定は、道路セグメントデータ、および、おそらく、そのタイルのローカルな近傍に含まれる道路セグメントに対して、先行するステップで得られたランク情報データに基づく。マスタシステムおよびワーカシステムは、道路セグメントデータおよびランク情報データの共通のコピーで動作し得るか、あるいは、ワーカシステムは、マスタシステムに結果を戻して、データのローカルコピーを使用し得る。道路セグメントデータを前処理するシステムが、マスタシステムおよび少なくとも１つのワーカシステムを含む実施形態において、前処理は、並列なデータ処理で迅速に行われる。
【００５０】
本発明に従う最適ルートを決定するシステムは、道路セグメントデータを含む第一のストレージユニットと、本発明に従う道路セグメントデータを前処理する方法に従って決定されたランク情報データを含む第二のストレージユニットと、該道路セグメントデータのサブセットを格納する作業メモリユニットと、該作業メモリユニットに結合され、ランク情報データに基づいて、出発点から目的地への最適ルートを決定するように適合された処理ユニットとを備える。第一および第二のストレージユニットは、個別のデバイスでも、単一のデバイスでもあり得る。好ましい実施形態において、道路セグメントデータおよびランク情報は、共通のストレージユニットに格納される。このシステムは、本発明に従う最適ルートの決定方法を実行するように適合されることが好ましい。このようなシステムは、ランク情報に基づいて、最適ルートの決定を効率的に実行するのに適合される。
【００５１】
最適ルートを決定するシステムは、さらに、所望の目的地、および、おそらくルートの出発点を入力する入力手段を備える。この入力手段は、目的地および出発点のデータが作業メモリユニットに格納され得るように、処理ユニットおよび作業メモリユニットに結合される。
【００５２】
好ましい実施形態において、この最適ルートを決定するシステムは、ランク情報データに基づいて、道路セグメントデータまたはランク情報データを、作業メモリユニットに格納されたデータに入れること、あるいは、作業メモリユニットに格納されたデータから取り出すことに適合された追加処理ユニットをさらに備える。追加処理ユニットは、処理ユニットと同一でも、個別のデバイスでもあり得る。追加処理ユニットを提供することで、作業メモリの中に、道路セグメントデータのサブユニットをロード可能となる。このサブセットは、決定されるべき最適ルートと潜在的に関連する道路セグメントを含む。追加処理ユニットは、作業メモリユニットに格納された目的地および出発点の情報へのアクセスすることにも、目的地および出発点の情報に応じて、作業メモリユニットに格納されたデータにデータを入れること、あるいは、作業メモリユニットに格納されたデータからデータを取り出すことにも、さらに適合され得る。処理ユニットおよび追加処理ユニットは、個別のデバイスでも、同一のデバイスでもあり得る。
【００５３】
最適ルートを決定するシステムは、タイリング定義データを含む第三のストレージユニットを備えることが好ましい。タイリング定義データは、道路セグメントに対する属性としても、また、格納され得る。この属性は、道路セグメントが属するタイルを特定する。第三のストレージユニットは、処理ユニットまたは追加処理ユニットによってアクセス可能である。追加処理ユニットは、ランク情報およびタイリング定義データの双方に応じて、作業メモリユニットに格納されたデータにデータを入れること、あるいは、そこからデータを取り出すことのそれぞれに適合されることが好ましい。これによって、最適ルート探索が実行されるべき道路セグメントのサブセットが、タイリングおよびランク情報データの双方に基づいて、選択されることが可能となる。第一、第二および第三のストレージユニットは、全てが個別のデバイスであることも、そのうちの２つのストレージユニットが単一のデバイスであることも、あるいは、これらストレージユニットの全てが単一のデバイスであることもあり得る。規則的なタイリングあるいは規則的なタイリングの階層を有する有用な実施形態において、タイリング定義データは、再び、数学的関数の形式で提供され得て、その座標に基づいて、特定の点を含むタイルを決定できる。
【００５４】
好ましい実施形態において、前記作業メモリユニットは、最適ルート探索に（少なくとも特徴的なタイルサイズと道路セグメント密度に）必要とされる道路セグメントデータのサブセットを格納するのに、十分なストレージ容量を有する。次いで、最適ルートは、作業メモリユニットにのみアクセスしている処理ユニットを用いて決定され得るので、ランタイムを短縮できる。
【００５５】
本発明に従うナビゲーションシステムは、本発明に従う最適ルート決定システムを備える。このナビゲーションシステムは、さらに、入出力ユニット、ディスプレイ、ラウドスピーカなどのような従来式ナビゲーションシステムから知られている全てのコンポーネントをさらに備え得る。特に、ナビゲーションシステムは、この最適ルートを決定するシステムに、車両位置情報を提供するように適合された位置決定手段を備え得る。これによって、運転手が出発点情報をわざわざ提供することなく、現在の車両位置から目的地への最適ルートの決定が可能となる。
【００５６】
「道路セグメント」という用語は、本明細書全体を通して使用されるが、道路セグメントとして記された対象は、必ずしも物理的な道路である必要はなく、例えば、河川や湖水を行き交うフェリーが通過するルートでもあり得ることに留意すべきである。
【００５７】
さらに、道路セグメントは、最適ルート探索が関心事となり得るネットワークを構成する任意の他の種類の対象に対応し得る。その例には、コンピュータネットワークにおけるデータ接続または電力送信線を含む。本発明は、道路網における最適ルートの意味で記載されているが、このようなアプリケーションの全ても、また包含されることも理解されるべきである。
【００５８】
また、「最適ルート」という用語は全体を通して使用されるが、本発明の様々な実施形態に従う方法およびシステムは、数学的意味で最適でないが、ほぼ最適なルートである有利なルートを決定するためにも、また適合されることに留意すべきである。このような変種の全ても、また、本発明によって企図される。しかしながら、本発明の好ましい実施形態に従うと、道路セグメントデータを前処理する方法およびシステムと、これに対応して最適ルートを決定する方法およびシステムとが提供され、正しい最適ルートを決定することが可能となる。これら好ましい実施形態に従うと、最適ルートの決定における複雑さは、例えば、車両に搭載されるナビゲーションシステムで実行され得る程度になる。
【００５９】
本発明のアプリケーションの主たる分野は、道路網における最適ルートの決定である。
【００６０】
本発明はさらに、以下の手段を提供する。
【００６１】
（項目１）
最適ルート決定用の道路セグメントデータを前処理する方法であって、
該道路セグメントデータを提供するステップと、
該道路セグメントが含まれるエリアをカバーするタイリングを定義するステップと、
道路セグメントに対するランク情報を決定するステップで、該ランク情報は該タイリングのタイルを結ぶ最適ルート用の該道路セグメントの妥当性を定量化する、ステップと
を包含する、道路セグメントデータを前処理する方法。
【００６２】
（項目２）
上記ランク情報は、上記タイリングに依存して決定され、タイル端部に位置する点を結ぶ最適ルート用の道路セグメントの妥当性を定量化すること
を特徴とする、項目１に記載の道路セグメントデータを前処理する方法。
【００６３】
（項目３）
上記道路セグメントの各道路セグメントは、上記タイリングの多くても１つのタイルに含まれるように、上記タイリングが定義されるか、または、上記道路セグメントが再定義されること、および、上記ランク情報が、該タイリングに依存して決定されること
を特徴とする、項目１または項目２に記載の道路セグメントデータを前処理する方法。
【００６４】
（項目４）
上記道路セグメントに対するランク情報を決定するステップは、
該道路セグメントを含むタイルを決定するステップと、
該道路セグメントを含む該タイルから、少なくとも所定のタイル距離を有する第一のタイルを選択するステップと、
該道路セグメントが、該第一のタイルに位置する出発道路セグメントを有する最適ルートに含まれるかどうかを決定するステップと
を包含することを特徴とする、項目３に記載の道路セグメントデータを前処理する方法。
【００６５】
（項目５）
上記出発道路セグメントの頂点は、上記第一のタイルの端部に位置すること
を特徴とする、項目４に記載の道路セグメントデータを前処理する方法。
【００６６】
（項目６）
上記ランク情報を決定するステップは、
上記道路セグメントを含む上記タイルから、少なくとも上記所定のタイル距離を有する第二のタイルを選択するステップであって、上記最適ルートの目的地道路セグメントは該第二のタイルに位置する、ステップ
をさらに包含する
ことを特徴とする、項目４または項目５に記載の道路セグメントデータを前処理する方法。
【００６７】
（項目７）
上記目的地道路セグメントの頂点は、上記第二のタイルの端部に位置すること
を特徴とする、項目６に記載の道路セグメントデータを前処理する方法。
【００６８】
（項目８）
上記ランク情報を決定するステップは、
上記道路セグメントが最適ルートに含まれるように、上記所定のタイル距離の最大を決定するステップをさらに包含すること
を特徴とする、項目４〜項目７のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００６９】
（項目９）
上記ランク情報を決定するステップは、上記所定のタイル距離の値を増やして、再帰的に実行されること
を特徴とする、項目４〜項目８のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７０】
（項目１０）
上記所定のタイル距離の所定の値に対して、最適ルート探索は、該所定のタイル距離のより小さな値に対して得られた結果に基づいて、選択された道路セグメントのサブセット上で実行されること
を特徴とする、項目４〜項目９のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７１】
（項目１１）
道路セグメント重み付けファクタを提供するステップを特徴とし、
上記ランク情報を決定するステップは、該重み付けファクタにさらに基づくことと
項目１〜項目１０のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７２】
（項目１２）
上記ランク情報を決定するステップは、上記道路セグメントの各道路セグメントに対して、実行されること
を特徴とする、項目１〜項目１１のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７３】
（項目１３）
上記タイリングのタイルは、長方形の形状であること
を特徴とする、項目１〜項目１２のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７４】
（項目１４）
２つのタイル間のタイル距離は、該２つのタイルを結ぶ経路を通過するタイル端部またはタイル頂点の最小数として定義されること
を特徴とする、項目１〜項目１３のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７５】
（項目１５）
１つのタイルに含まれる道路セグメントシーケンスを新たな道路セグメントに、相互結合するステップ
を特徴とする、項目１〜項目１４のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７６】
（項目１６）
所定の道路セグメントのランク情報が決定された後、上記タイリングを粗調整するステップ
を特徴とする、項目１〜項目１５のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７７】
（項目１７）
上記決定されたランク情報を出力するステップ
を特徴とする、項目１〜項目１６のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７８】
（項目１８）
上記道路網は任意のグラフであり、各道路セグメントは該グラフのエッジ部であること
を特徴とする、項目１〜項目１７のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７９】
（項目１９）
道路セグメントデータを提供するステップと、
項目１〜項目１８のいずれか１項に記載の方法に従って決定されたランク情報データを提供するステップと、
該道路セグメントデータおよび該ランク情報データに基づいて、出発点から目的地への最適ルートを決定するステップと
を包含する、出発点から目的地への最適ルートを決定する方法。
【００８０】
（項目２０）
上記ランク情報に基づいて、道路セグメントのサブセットを選択するステップ
を特徴とし、
上記最適ルートを決定するステップは、該道路セグメントのサブセットに基づいて実行される、項目１９に記載の最適ルートを決定する方法。
【００８１】
（項目２１）
上記道路セグメントが含まれるエリアをカバーするタイリングを定義するステップ
を特徴とする、項目１９または項目２０に記載の最適ルートを決定する方法。
【００８２】
（項目２２）
上記道路セグメントの各道路セグメントは、上記タイリングの多くても１つのタイルの中にしか含まれないように、上記タイリングが定義されるか、または、該道路セグメントが再定義されること
を特徴とする、項目１９または項目２１に記載の最適ルートを決定する方法。
【００８３】
（項目２３）
上記道路セグメントのサブセットを選択するステップは、
上記出発点を含む出発タイルを決定するステップと、
上記目的地を含む目的地タイルを決定するステップと、
道路セグメントを、道路セグメントランク情報、および、該道路セグメントを含むタイルの該出発タイルまたは目的地タイルからのタイル距離に基づいて、上記道路セグメントのサブセットに含めるステップと
を包含することを特徴とする、項目２０に従属した項目２１または項目２２およびに記載の最適ルートを決定する方法。
【００８４】
（項目２４）
上記道路セグメントのサブセットを選択するステップは、
上記出発点を含む出発タイルから、上記目的地を含む目的地タイルまでの出発−目的地タイル距離を決定するステップと、
該出発−目的地タイル距離に基づいて最小ランク値を選択するステップと、
該最小ランク値以上のランク値を有する全ての道路セグメントを、該道路セグメントのサブセットに含めるステップと
を包含することを特徴とする、項目２０に従属した項目２１〜項目２３のいずれか１項に記載の最適ルートを決定する方法。
【００８５】
（項目２５）
道路セグメント重み付けファクタを提供するステップを特徴とし、
上記最適ルートを決定するステップは、該重み付けファクタに、さらに基づく、項目１９〜項目２４のいずれか１項に記載の最適ルートを決定する方法。
【００８６】
（項目２６）
車両位置データを受信するステップと、
車両位置から上記目的地への最適ルートを決定するステップと
を特徴とする、項目１９〜項目２５のいずれか１項に記載の最適ルートを決定する方法。
【００８７】
（項目２７）
上記道路網は任意のグラフであり、各道路セグメントは該グラフのエッジ部であること
を特徴とする、項目１９〜項目２５のいずれか１項に記載の最適ルートを決定する方法
（項目２８）
道路セグメントデータを含む第一のストレージユニット（１０）と、
タイリング定義データを含む第二のストレージユニット（２０）と、
該道路セグメントデータのサブセットおよび該タイリング定義データのサブセットを格納する作業メモリユニット（５０）と、
該作業メモリユニット（５０）に格納されたデータを処理し、該タイリングに基づいて、道路セグメントのランク情報を決定するように適合された処理ユニット（４０）と
を備え、
該ランク情報は、該タイリングのタイルを結ぶ最適ルートに対する該道路セグメントとの妥当性を定量化する、道路セグメントデータを前処理するシステム。
【００８８】
（項目２９）
上記システムは、項目１〜項目１８のいずれか１項に記載の道路セグメントデータを前処理する方法を実行するように適合されることを特徴とする、項目２８に記載の道路セグメントデータを前処理するシステム。
【００８９】
（項目３０）
上記処理ユニット（４０）に結合され、決定されたランク情報を格納するように適合された追加作業メモリユニット（６０）
を特徴とする、項目２８または項目２９に記載の道路セグメントデータを前処理するシステム。
【００９０】
（項目３１）
上記処理ユニット（４０）は、上記ランク情報を決定するための上記追加作業メモリユニット（６０）に格納されたデータを処理するように適合されること
を特徴とする、項目３０に記載の道路セグメントデータを前処理するシステム。
【００９１】
（項目３２）
上記作業メモリユニット（５０）は、上記ランク情報を決定するための最適ルート探索に必要とされる道路セグメントデータのサブセットを格納するのに十分なストレージ容量を有すること
を特徴とする、項目２８〜項目３１のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【００９２】
（項目３３）
決定されたランク情報を出力するための出力ユニット（７０）
を特徴とする、項目２８〜項目３２のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【００９３】
（項目３４）
決定されたランク情報を格納するための第三のストレージユニット（３０）
を特徴とする、項目２８〜項目３３のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【００９４】
（項目３５）
上記システムは、上記タイリングに基づく道路セグメントのランク情報を決定するのに適合された少なくとも１つの追加処理ユニットを備え、
上記処理ユニット（４０）および該追加処理ユニットは、並行して、道路セグメントランク情報を決定するように適合されていること
を特徴とする、項目２８〜項目３４のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【００９５】
（項目３６）
道路セグメントデータを含む第一のストレージユニット（４３０）と、
ランク情報データを含む第二のストレージユニット（４３０）と、
該道路セグメントデータのサブセットを格納する作業メモリユニット（４６０）と、
該作業メモリユニット（４６０）に結合され、ランク情報データに基づいて、出発点から目的地への最適ルートを決定するように適合された処理ユニット（４５０）と
を備え、
該ランク情報データは、項目１〜項目１８のいずれか１項に記載の道路セグメントデータを前処理する方法に従って決定されることを特徴とする、最適ルート決定システム。
【００９６】
（項目３７）
上記ランク情報データに基づいて、道路セグメントデータまたはランク情報データを、上記作業メモリユニット（４６０）に格納されたデータに入れること、あるいは、該作業メモリユニット（４６０）に格納されたデータから取り出すように適合された追加処理ユニット（４５０）
を特徴とする、項目３６に記載の最適ルート決定システム。
【００９７】
（項目３８）
タイリング定義データを含む第三のストレージユニット（４４０）
を特徴とする、項目３６または項目３７に記載の最適ルート決定システム。
【００９８】
（項目３９）
上記作業メモリユニット（４５０）は、最適ルート決定に必要とされる上記道路セグメントデータのサブセットを格納するのに、十分なストレージ容量を有すること
を特徴とする、項目３６〜項目３８のいずれか１項に記載の最適ルート決定システム。
【００９９】
（項目４０）
上記システムは、項目１９〜項目２７のいずれか１項に記載の最適ルートを決定する方法を実行するように適合されていること
を特徴とする、項目３６〜項目３９のいずれか１項に記載の最適ルート決定システム。
【０１００】
（項目４１）
項目３６〜項目４０のいずれか１項に記載の最適ルート決定システム（４２０）
を特徴とする、ナビゲーションシステム。
【０１０１】
（項目４２）
上記最適ルート決定システム（４２０）に車両位置データを提供するように適合された位置決定手段（４１２）
を特徴とする、項目４１に記載のナビゲーションシステム。
【発明の効果】
【０１０２】
本発明により、地図上の相対位置に基づいて決定される道路セグメント属性に基づく最適ルート決定方法が提供され得、このような道路セグメント属性が、たとえ大きな道路網であっても効率的に決定され得る最適ルートの決定方法が提供され得る。
【発明を実施するための最良の形態】
【０１０３】
本発明の付加的な特徴と利点は、添付図面を参考して、好ましい実施形態または有利な実施形態の以下の詳細に関する記述から、より容易に理解される。
【０１０４】
図１を参照しながら、本発明の実施形態に従う道路セグメントデータを前処理するシステム１は、記載される。このシステムは、道路セグメントのセットにある各道路セグメントに対して、長距離移動用に道路セグメントの妥当性を定量化するランク情報を決定することに、より特定的には、計算することに適合される。より特定的には、本実施形態に従うと、道路セグメントが含まれるエリアに対して、タイリングが提供される。ここで、ランク情報は、そのタイリングの異なるタイルを結ぶ最適ルート用の道路セグメントの妥当性を定量化する。
【０１０５】
システム１は、道路セグメントデータを格納する第一のストレージユニット１０、タイリング定義データを格納する第二のストレージユニット２０、および、決定されたランク情報を格納する第三のストレージユニット３０を備える。第一、第二および第三のストレージユニットは、図１に示すように異なる物理的エンティティであり得るが、ＣＤ−ＲＯＭまたはＣＤ−Ｒ／Ｗ、あるいは、コンピュータのハードドライブのような１つの物理的ストレージユニットに結合され得る。
【０１０６】
第一のストレージユニット１０に格納された道路セグメントデータは、道路網を構成する道路セグメントを関連付ける情報を含む。典型的には、道路セグメントに対し、これらデータは、出発点と終点の地理的位置のような道路セグメントの位置および方向と関連する地理的情報と、道路セグメントの長さ、道路セグメントでの特徴的な移動速度、および／または、道路セグメントを通過するのに要する特徴的な移動時間を定量化する追加情報とを備える。より一般的には、重み付けファクタが、道路セグメントの後者の特徴の一つに対応する道路セグメントに対して、提供され得る。以下に、重み付けファクタは、道路セグメントの重み付けファクタとして記載されるが、これら重み付けファクタは、道路セグメントまたは道路セグメント頂点のいずれかと関連し得ることは理解されるべきである。さらに、重み付けファクタは、道路セグメント（すなわち、グラフの端）および道路セグメント頂点（すなわち、グラフのノード）の双方に提供され得る。単純化するために、重み付けファクタを、道路セグメントおよび／または道路セグメント頂点と関連付けるこれら全ての可能性は、本明細書にて、以下、まとめて、道路セグメントの重み付けファクタとして、言及される。また、道路セグメントデータは、道路セグメントに関して、さらに追加情報を含み得る。しばしば、道路セグメントデータは、第一のメモリユニット１０の中に格納されたデータセット１１〜１３によって模式的に示されるように、データアレイの形式で格納される。
【０１０７】
第二のメモリユニット２０に格納されたタイリング定義データは、どのランク情報が計算されるべきは基づいて、タイリングの全てのタイルを決定する。データは、１つまたは幾つかのタイル角の座標を特定する数字多重項の形式で、提供され得る。例えば、長方形のタイルからなるタイリングに対し、左上角および右下角の座標が提供され得る。タイリング定義データは、アレイ２１〜２３の形式で格納され得る。ここで、各アレイが、タイリングの１つのタイルに対応する。しかしながら、タイリング定義データは、任意の他の適切な方法でも提供され得る。例えば、人がタイル頂点およびタイル端部を決定することを可能にするアルゴリズムの形式で提供され得る。
【０１０８】
第三のメモリユニット３０は、ランク情報計算の結果を格納するために、提供される。
【０１０９】
道路セグメントデータを前処理するシステムは、さらに処理ユニット４０、作業メモリユニット５０、追加作業メモリユニット６０、および、出力ユニット７０を備える。処理ユニット４０は、ストレージユニット１０、２０または３０の１つに格納されるデータを作業メモリユニット５０に入れること、作業メモリユニット５０に格納されたデータをそこから取り出すこと、および、作業メモリユニット５０に格納されたデータを処理することに適合される。作業メモリユニット５０に格納されたデータは、第一のストレージユニットからの道路セグメントデータのサブセットを含む。計算されたランク情報は、出力ユニット７０を介して出力され得るか、あるいは、引き続く使用のために追加作業メモリユニット６０に格納され得る。作業メモリユニット５０および追加作業メモリユニット６０は、単一のデバイスでも、異なるデバイスでもあり得る。
【０１１０】
以下の記述から明らかになり、以下に詳細に記載されるように、本発明に従う道路セグメントを前処理する方法は、コンピュータネットワーク上あるいはクラスタ上で実行されるように適合される。道路セグメントデータを前処理する方法の並列化に対する様々なインプリメンテーションは、例えば、ピアツーピアまたはマスタワーカのスキームを使用して実現可能である。後者の場合、例えば、マスタコンピュータおよび複数のワーカコンピュータの各コンピュータは、少なくとも、処理ユニットおよび作業メモリユニットを備える。さらに、コンピュータは、共通のストレージユニットを分かち合い得るし、あるいは、個々のストレージユニットを備え得る。
【０１１１】
次いで、図１に示すシステム１によって実行される道路セグメントデータを前処理する方法が、説明される。道路セグメントデータの前処理は、その道路セグメントが含まれるエリアをカバーするタイリングに基づく。図２に模式的に示すタイリング８０は、タイル９０〜９２を含む複数のタイルを備える。最適ルートが計算されるべき道路網は、複数の道路を含む。道路は、実線と破線とで示される。道路は、例えば、許容移動速度の観点から、異なるタイプであり得て、道路は、重み付けファクタによって定量化され得る。図２に示す道路網は、２つの異なるタイプの道路を備える。一方は、第一の特徴的な移動速度（図２の実線で表示）で、例えば、道路セグメント９３であり、他方は、第二の特徴的な移動速度（図２の破線で表示）で、例えば、道路セグメント９４である。道路セグメントの終点、あるいは、道路セグメントのジャンクションまたは交差点は、道路網の頂点（図２の黒丸で表示）を定義し、例えば、点９５である。
【０１１２】
典型的には、道路セグメントおよび道路セグメント頂点の密度は、空間によって異なり、都会エリアで高い。タイリングは、道路セグメントまたは道路セグメント頂点の密度が高いエリア９６および９７において、道路セグメントまたは道路セグメント頂点の密度が低いエリアより、タイルサイズが小さくなるように選択される。タイリング全体を通して、１タイル当たりの道路セグメントまたは道路セグメント頂点の数が大きくばらつかないようにするためである。しかしながら、以下で議論する好ましい実施形態の多くでは、同じサイズからなる小さな正方形を有するタイリングで開始することも可能である。
【０１１３】
道路セグメントデータの前処理にあたって、タイリングは、各道路セグメントが、タイリングの１つのタイルのみに含まれるように、あるいは、より正確には、各道路セグメントが、その頂点を例外として、１つのタイルの内側に位置するように選ばれる。これは、道路セグメントがタイル端部と交わる全ての点に追加の頂点を導入することで、もっとも容易に達成される。例えば、図２の点９８（白丸で表示）である。このような追加頂点を導入することで、道路セグメントは、幾つかの新たな道路セグメントに分裂する。各道路セグメントが１つのタイルのみに含まれるようにタイリングを選択するには、上記に説明されたように、道路セグメントを再定義されるべきことが必要とされ得るのは、理解されるべきである。以下においては、道路セグメントデータおよびタイリング定義データは、既に、各道路セグメントは１つのタイルのみに含まれる形式であると仮定される。このようにならない場合は、第一のステップで、道路セグメントデータを前処理するシステム１は、追加頂点を導入し、新たな道路セグメントに重み付けファクタを計算して、道路セグメントを再定義する。再定義された道路セグメントデータは、システム１の第一のストレージユニットまたは作業メモリユニットの１つに格納され得る。
【０１１４】
図３〜図９を参照して、以下に示されるように、提供され、タイリングの定義に基づく道路セグメントデータから、システム１は、道路セグメントのそれぞれに対するランク情報を計算する。図３Ａは、道路セグメントデータを前処理する方法の間のシステム１によって実行される基本ステップを示す模式的な流れ図１００を示す。第一のステップにおいて、未知のランクを有する道路セグメントｖが、ステップ１０１で選択される。ステップ１１０で、以下に詳細に示されるように、道路セグメントｖに対するランク情報は計算され、ステップ１２０で、出力ユニット７０を介して出力されるか、あるいは、第三のストレージユニット３０または追加作業メモリユニット６０に格納される。ランク情報が未知の道路セグメントがまだあるかどうかが、ステップ１３０で判断され、上述のステップは、未知のランク情報を有する異なる道路セグメントに対して、繰り返されるか、あるいは、ステップ１４０で終了する。
【０１１５】
プロセス１００の中心部分は、所定の道路セグメントｖに対するランク情報を決定するステップ１１０であり、さらなる詳細が、図３Ｂおよび図３Ｃを参照して記述される。図３Ｂは、ランク情報を決定するステップ１１０で実行されたプロセスの模式的な流れ図である。まず、ｖを含むタイルＴが、ステップ１１１で決定される。引き続き、タイル距離の最大が決定される。そのタイル距離の最大は、道路セグメントｖが、相変わらず、タイルＴからこのタイル距離を有するタイルを含む出発道路セグメントと、タイルＴからこのタイル距離を有するタイルを含む目的地道路セグメントとを結ぶ最適ルートに、含まれる。タイル距離のこの最大は、道路セグメントのランク値となるように定義される。ランク情報は、ランク値と等しいことも、以下に詳細に説明されるように、ランク値に基づいて決定されることもある。この最大値を決定することは、ステップ１１２で定義される初期値からタイル距離を１つずつ増やすことによって達成される。引き続き、ステップ１１３で、まだｖが最適経路に含まれているかどうかを判断する。そして、ステップ１１３の結果によって、ステップ１１４で、タイル距離を増やすか、あるいは、ランク情報がタイル距離の最大と等しくなるように、すなわち、そのランク値と等しくなるように設定する。そのタイル距離の最大は、道路セグメントｖが、依然として、タイルＴからこのタイル距離を有するタイルを含む出発道路セグメントと、タイルＴからこのタイル距離を有するタイルを含む目的地道路セグメントとを結ぶ最適ルートに含まれる。すなわち、ステップ１１５においては、ランク値と等しい。
【０１１６】
タイル距離は、様々な方法で定義され得るが、本発明の実施形態に従うと、２つのタイル間の距離は、２つのタイルを結ぶ経路を通過するタイル端部またはタイル角の最小数として定義されるか、あるいは、別に言うと、２つのタイルの一方に、その２つのタイルの他方から到達するのに必要とされる隣り合うタイル間で、横、縦または対角線に飛び越えの最小数として定義される。図７はタイリング３００について、模式的に示している。直前に記載されたように定義されたタイル距離を用い、数字は中心タイルＴからタイルそれぞれへのタイル距離を示す。
【０１１７】
図３Ｂに戻ると、タイルＴに含まれる道路セグメントｖが、出発道路セグメントから目的地道路セグメントへの最適ルートに含まれるかどうかを決定するステップ１１３は、タイルＴから少なくともタイル距離ｄを有するタイルの中に位置する出発道路セグメントおよび目的地道路セグメントを用いて、全ての最適ルートを決定することによって実行され得る。この全ての最適ルートは、タイルＴからタイル距離ｄを有する任意のタイルに位置する任意の出発道路セグメントの頂点と、タイルＴからタイル距離ｄを有する任意のタイルに位置する任意の目的地道路セグメントの頂点とを結ぶ。しかしながら、図８から分かるように、このような可能性のある出発点と目的地のサブセットのみを考慮すれば、十分である。
【０１１８】
図８は、模式的に道路網およびタイリング３１０を示す。道路セグメントｖａのランク値が決定されるべきものと仮定すると、第一ステップで、出発道路セグメントと目的地道路セグメントとを結ぶ最適ルートがあるかどうかが決定されるべきである。各道路セグメントはタイル３１１からタイル距離１を有するタイルの中に位置し、最適ルートは道路セグメントｖａを含む。原則的に、それゆえ、点３１２〜点３１８から選択された出発点と目的地との任意のペアを結ぶ全ての最適ルートを計算することが必要である。しかしながら、タイル３１１からのタイル距離が１に等しいタイル内に位置する出発道路セグメントおよび目的地道路セグメントを有する任意の最適ルートは、必然的にタイル３１１の端部と交差するので、また、各道路セグメントは１つのタイル内にのみあるので、それぞれタイル３１１の端部にある出発点および目的地を結ぶ最適ルートを計算すれば、十分である。この場合において、最適ルート探索には、考慮されるべく残された点のみが考慮される。それらの点は、それゆえ、点３１２および点３１３である。
【０１１９】
同様の議論は、タイル距離の値がさらに大きい場合でも、依然として有効である。特に、タイルＴからのタイル距離ｄを有するタイル内にある出発道路セグメントおよび目的地道路セグメントを相互に結ぶ全ての最適ルートを決定する代わりに、タイルＴからのタイル距離がｄ未満である全てのタイルの境界に位置する出発点および目的地に対して、最適経路を計算すれば十分である。以下において、タイルＴのｄ境界は、Ｂ（ｄ，Ｔ）と称される。
【０１２０】
それゆえ、ステップ１１３は、図３Ｃによって示される以下の方法に従って、実行され得る。タイルＴのｄ境界に位置する出発点および目的地は、それぞれ、ステップ１１３０および１１３１で選択され、これら２つの点を結ぶ最適ルートは、ステップ１１３２で計算される。ステップ１１３２における計算は、ＤｉｊｋｓｔｒａアルゴリズムまたはＡ＊アルゴリズムのような標準的方法を使用して実行され得る。後者の場合には、最適ルートのコスト見積もりは、距離ベースの最適ルート探索に対しては、エア距離から、時間ベースの最適ルート探索に対しては、エア距離を特徴的な移動速度で除算して、それぞれ求められ得る。ｖが計算された最適ルートを含んでいる場合は、プロセス１１３は、ステップ１１３４で「はい」を出力する。含んでいない場合は、そのプロセスは、ステップ１１３５および１１３６で、全ての可能な出発点および目的地のペアに対して繰り返される。それは、ステップ１１３７および１１３８で、Ｔのｄ境界上の異なる目的地および出発点を選択することによってである。ｖがこのような最適ルートのいずれにも含まれていない場合は、ステップ１１３は、ステップ１１３９で「いいえ」を出力する。
【０１２１】
「最適」とは、距離、移動時間、トンネルまたはフェリーを避けるこれら２つのいずれか、あるいは、ユーザが関心を示し得る任意の他のルーティングオプションの観点からの最適を意味し得る。最適ルートは、選択されたルーティングオプションによって異なる。技術的に、選択されたモードに依存する異なる道路セグメントの重み付けファクタによって、通常は、異なるモードが採用される。
【０１２２】
図３Ａ〜図３Ｃに示す流れ図を組み合わせることで、全ての道路セグメントに対するランク情報を計算する完全なプロセスが得られる。しかしながら、真のランク値ｒを知る必要が必ずしもないことには留意すべきである。むしろ、ランク値が特定の閾値未満である場合のみ、正確なランク値が分かれば十分であり得る。所定の最大ランクは、特徴的な値によって与えられ得る。この特徴的な値に対して、それを超えるランクを有する道路セグメントの数は、十分に少ないので、そのような全ての道路セグメントは、例えば、カーナビゲーションシステムのような作業メモリユニットに容易に格納され得る。次いで、ランク情報の計算は、図４に示すプロセス２１０によって、特定値で終了し得る。これは、図３Ａのプロセス１１０に置換して適合される。プロセス１１０によって実行されたステップに加え、ステップ２１３で、最適ルートが計算されるべきｄの値が、既に所定の最大ランクを超えているかどうかが決定される。道路セグメントに対するランク情報は、次いで、ランク値が所定の最大ランク以下の場合、そのランク値と等しくなり、そうでない場合、所定の最大ランクに等しくなる。
【０１２３】
次に、ランク情報を計算する方法の変種が記載される。この変種は、ランク値のより効率的な決定を可能とする。上述の方法と比較すると、主たる違いは、第一のステップにおいて、少なくとも１のランク値を有する全ての道路セグメントが、決定される。次いで、第二のステップにおいて、少なくとも２のランク値を有する全ての道路セグメントが、決定されるなどである。すなわち、ランク情報は、ランク値を増やして、連続的に計算される。道路セグメントｖが最適ルートに含まれるかどうかを決定する中心ステップは、図３Ｃに示すように、上述の方法と同様のままである。しかしながら、ランク値の計算が、ランク値を増やしながら連続的に実行されるので、出発点と目的地が選択された後に、１１３２で最適ルートを計算するステップは、先行するステップで得られた結果に基づき得る。これは、ランク値の計算を非常に単純化する。これは、次に、図９Ａおよび図９Ｂを参照しながら記載される。
【０１２４】
図９Ａは、タイリング３２０を示す。少なくとも２のランク値を有するタイルＴ内の道路セグメントが決定されるべきであると、仮定する。上述のように、タイルＴの２境界（太い実線３２１で表示）上に位置する出発点および目的地を結ぶ全ての最適ルートは、計算されるべきである。ランク情報を計算する変種の方法に従うと、先行するステップで、少なくとも１のランク値を有する全ての道路セグメントは、全てのタイルに対し、決定されていることに留意すべきである。それゆえ、少なくとも２のランク値を有するＴ内の全ての道路セグメントを決定するステップは、少なくとも１のランク値を有するような全ての道路セグメントに制限され得る。さらに、タイルＴの２境界に位置する出発点と目的地とを結ぶ任意の最適経路は、タイルＴから１に等しいタイル距離を有するタイルを通過する。ステップ１１３２における最適ルート探索は、それゆえ、少なくとも１のランク値を有するタイルで、Ｔから１に等しいタイル距離を有するタイルを含むこれら道路セグメントに制限され得る。これは、タイルＴから１に等しい距離を有するタイルに数字によって、模式的に図９Ａで示される。最適ルート探索のために考慮すべき道路セグメントの数を減らすことによって、計算の複雑さを減らし、ランタイムも短縮し得る。
【０１２５】
同様の議論はｄ値がより大きな場合に対しても、図９Ｂに模式的における格子３３０で示すように、依然有効である。少なくとも３のランク値を有するタイルＴ内の道路セグメントが決定されるべきであると、仮定する。ステップ１１３２における最適ルート探索は、タイルＴから２に等しいタイル距離を有するタイルに対して、少なくとも１のランク値を有する道路セグメントと、タイルＴから１に等しいタイル距離を有するタイルに対して、少なくとも２のランク値を有する道路セグメントとに制限され得る。これらの道路セグメントは、先行するステップで、既に決定されていることに留意すべきである。それゆえ、計算の複雑さは、ランク値を再帰的に計算することで、減少され得る。
【０１２６】
より一般的には、タイルＸに含まれる出発点と、タイルＹに含まれる目的地とを結ぶ最適ルートが決定されるべきであれば、タイルＺにおいて、タイルＺとＸとの間のタイル距離と、タイルＺとＹとの間のタイル距離とのいずれか小さなタイル距離以上のランク値を有する道路セグメントのみを考慮される必要がある。それゆえ、増加するランク値に対して、最適ルート探索が実行されるべき道路セグメントのセットは、全てのタイルに対して、先行するステップで得られた結果に基づいて、減少され得る。
【０１２７】
図５の流れ図によって、模式的に示されるランク情報を計算する第二の代替的方法に従うと、少なくともｄの値のランク値を有するタイルＴに含まれる全ての道路セグメントを同時に決定することで、最適ルートの計算回数を最小にして、ランタイムをさらに減らし得る。これは、タイルＴのｄ境界上に位置する出発点および目的地を結ぶ全ての最適ルートを計算し、次いで、ステップ２２６に示すように、この最適ルートに含まれるタイルＴ内の全ての道路セグメントを同時に決定することにより、上記のランク情報計算の代替方法を変更することによって達成される。これら全ての道路セグメントのランク情報は、更新されて、ｄになる。このステップは、ステップ２２７〜２３０で示すように、出発点と目的地との全ての可能な組み合わせに対して、繰り返される。ランク情報を計算する代替方法で上述したように、重要なのは、ステップ２２５での最適ルート探索が、道路セグメントのサブセットに基づいていることである。このサブセットは、より低いランク値に対して先行するステップで得られた結果に基づき選択されたものである。
【０１２８】
図６に示すランク情報を計算する第三の代替的方法に従うと、ランク情報の計算は、タイルサイズを増やすことによって、さらに合理化され得る。すなわち、それは、決定されるべきランク値が増加する間にタイルを再定義することによってであり、同時に道路網、つまり、より技術的には最適ルート探索が実行されるべきグラフを再定義することによってである。この方法２５０に従うと、まず、ステップ２５１で、タイリングが定義される。ステップ２５２で、補助道路セグメント頂点が道路セグメントとタイル端部との交点で導入される。道路網またはグラフが空でない間、１、２および３以上のランク値を有する道路セグメントが、ステップ２５４〜２５８で計算される。一つの実施形態において、ステップ２５５は、図５のステップ２２３〜２３０を備える。重要なことは、これらステップで要求される任意の最適ルートの計算は、より小さなランク値に対して先行して得られた結果に、再び、基づき得ることである。少なくともｋのランク値を有するタイルＴの道路セグメントは、Ｇ（ｋ，Ｔ）で記される。完全なタイリングのこのような道路セグメント全てのセットのユニオン（ｕｎｉｏｎ）は、Ｇ（ｋ）で記される。Ｇ（ｋ，Ｔ）は、Ｔの（ｋ−１）境界上にある出発点および目的地を有する最適ルートで生じるＴ内の全ての道路セグメントのセットであることに留意すべきである。ステップ２５９で、道路網は、先行するループにおいて少なくとも３のランク値を有するように決定された全ての道路セグメントのセットとして再定義される。道路セグメントの数は、以下に詳細に述べられるように、ステップ２６０で、ショートカットを導入することで減少される。ステップ２６２で、タイル端部の長さを２倍にした後、上記のステップは、新たな道路網またはグラフＧおよび新たなタイリングに基づいて、繰り返される。
【０１２９】
第三の代替方法に従うと、初期の端部長さがｓ１（例えば、ｓ１＝１０００ｍ）の小さな正方形タイルから開始するランク情報を計算することが可能である。この方法で割り当てられたランク情報は、格子が中間ステップで再定義されるので、以前の方法のランク情報とは幾分か異なることに留意すべきである。例えば、タイル端部長さがｓ２＝２×ｓ１で再定義されたタイリングと、これに対応する再定義された道路網のために、１に等しいランク値を有するように決定された道路セグメントに対して、ランク情報は４に等しいと設定される。このランク情報は、元々のタイリングに対するランク値に直接変換しない（ｔｒａｎｓｌａｔｅ）「擬似ランク」であることに留意すべきである。むしろ、本方法の４というランク情報は、再定義された道路網において、少なくとも１のランク値を有する道路セグメントを元々のタイル端部長さの２倍を有する再定義されたタイリングに対して示す。ランク情報は、引き続く繰り返しに対応するように割り当てられる。
【０１３０】
また、このランク情報の定義に関して、増大する粗調整されたタイリングに基づく間、ランク情報は、長距離移動用、つまり、より特定的には、タイリングのタイルを結ぶ長距離ルート用の道路セグメントの重要性に対する尺度である。粗調整されたタイリングの階層用に計算されたランク情報または擬似ランク情報は、元々のタイリングに対するランク値に直接変換し戻す（ｔｒａｎｓｌａｔｅ ｂａｃｋ）ことはできない一方で、それらは、依然、このランク情報に基づいて、最適ルートの正確な決定が可能である。これについては、後述される。
【０１３１】
さらに、元々の道路網および元々のタイリングの意味で定義されたランク値と、第一に再定義されたタイリングおよび第一に粗調整されたタイリング用に定義されたランク値とは、包含関係（ｉｎｃｌｕｓｉｏｎ ｒｅｌａｔｉｏｎ）によって、相変わらず、相互接続されることに留意すべきである。例えば、元々の道路網および元々のタイリングのタームで、少なくとも６のランク値を有する全ての道路セグメントのセットは、第一に再定義されたタイリングのタームで、少なくとも２のランク値を有する再定義された道路網の道路セグメントのセットのサブセットである。ここで、タイル距離は、後者の場合に再定義されたタイルの単位で測定される。同様に、元々の道路網および元々のタイリングの意味で、少なくとも５のランク値を有する全ての道路セグメントのセットは、第一に再定義されたタイリングのタームで、少なくとも３のランク値を有する再定義された道路網の道路セグメントのセットを含む。ここで、タイル距離は、後者の場合に再定義されたタイルの単位で測定される。後者の関係は、以下の事実から容易に理解され得る。Ａが元々のタイリングＴのタイルで、Ａ’が第一に粗調整されたＡを含むタイリングＴ’の場合、タイル距離がＴの意味で測定され、Ａから４以下のタイル距離を有するＴ内のタイルのセットは、タイル距離がＴ’のタームで測定され、Ａ’から２以下のタイル距離を有するＴ’内のタイルのセットに含まれる。このような包含関係も、また、以下に説明されるように、最適ルートの決定に使用され得る。
【０１３２】
図６に示す方法は、粗調整されたタイリングおよび対応するランク情報の階層を導入する。
【０１３３】
当然、図６に示す有利な方法の他の変種も、また、可能である。例えば、繰り返しのランク値計算の回数、すなわち、ループ２５４〜２５８における異なるｋ値の数は、タイルサイズに応じて、変化し得る。例えば、繰り返しは、元々のタイルサイズに対して、１から３の値に拡張し得るが、全ての引き続くタイルサイズに対しては、１から４に拡張し得る。さらに、再定義された道路網およびタイル端部長さに対する繰り返しは、道路網またはグラフＧが空になるまで継続される必要がなく、終了し得る。
【０１３４】
図８に戻ると、道路セグメントｖａおよびｖｄは、タイル３１１の１境界上の点３１２と点３１３とを結ぶ最適ルートを必然的に含まれるので、ランク値は少なくとも１を有する。道路セグメントｖｅ、ｖｆおよびｖｇは、タイル３１１を通過する最適ルートに含まれていないので、０に等しいランク値を有する。道路セグメントｖｂ、ｖｃおよびｖｈのランク値は、点３１２と点３１３とを結ぶ最適ルートが道路セグメントｖｂおよびｖｃを経由するか、あるいは、道路セグメントｖｈを経由するかに、依存する。これは、個々の道路セグメントに割り当てられる重み付けファクタに依存する。最適ルートに基づく距離に対して、道路セグメントｖｂおよびｖｃは、１に等しいランク値を有し、一方で、道路セグメントｖｈはランク値０を有する。時間ベースの最適ルート探索に対して、道路セグメントｖｈ上での移動時間が、道路セグメントｖｂおよびｖｃ上での移動時間に比べ、短ければ、ｖｈはランク値１を有する。重み付けファクタ、および、それゆえ、最適ルートは、移動方向にも依存し得ることに留意すべきである。例えば、ｖｂ、ｖｃおよびｖｈが一方通行の道路であり、ｖｈ上で許可される走行方向が、ｖｂおよびｖｃの双方上で許可される走行方向と逆であると仮定すると、ｖｂ、ｖｃおよびｖｈは、全て１に等しいランク値となる。
【０１３５】
図８に関して続けて述べると、正確なランク値あるいはその正確なランク値の下界（ｌｏｗｅｒ ｂｏｕｎｄ）のいずれかを特定することによって、タイル内の全ての道路セグメントのランク値を計算した後に、ランク値が所定の閾値を超える場合、道路セグメントデータの前処理は、シーケンスを形成し、１つのタイル内に含まれる幾つかの道路セグメントを、１つの新たな道路セグメントに、相互結合するステップを含み得る。これは、例えば、図６のように、ショートカットを形成することを意味する。例えば、道路セグメントｖｂおよびｖｃも、また、ランク値１を有する場合、道路セグメントｖａ、ｖｂ、ｖｃおよびｖｄは、３１２から３１３に伸びる新たな道路セグメントに相互結合され得る。新たな道路セグメントの重み付けファクタは、ｖａ、ｖｂ、ｖｃおよびｖｄの重み付けファクタから計算される。このような道路セグメントの相互結合は、上記で図６を参照して説明されたランク情報を計算する方法の一部をなす。道路セグメントの総数を減らすことで、引き続く最適ルートの決定の間に、例えば、ナビゲーションシステムにおいて、さらなる迅速化が達成され得る。しかしながら、新たな道路セグメントは、引き続くステップの間、そのコンポーネントに分解されねばならないこともあり得ることに留意すべきである。それゆえ、元々の道路セグメントを参照する情報は、新たな道路セグメントの属性として、含まれるべきである。また、道路セグメントの相互結合は、さらに、ランク情報に基づき得る。例えば、実施形態に従うと、特定の最小値に等しいランクか、あるいは、特定の最小値に少なくとも等しいランク値を有する道路セグメントのみが、相互結合され得る。
【０１３６】
計算されたランク情報は、図１に示すシステム１の第三のストレージユニット３０または追加作業メモリユニット６０の中に格納され得る。特に、ランク情報を、システム１の作業メモリユニット５０または６０に格納することは、上述したようなランク情報を計算する再帰的方法で、ランク情報を引き続き取り出しするのに、特に有効である。ランク情報は、対応する道路セグメントを識別できるようにする識別子を用いて、個別のストレージユニットまたはメモリユニットに格納され得る。あるいは、図１のアレイ３１、３２、６１および６２で示されるように、ランク情報は、道路セグメントデータと一緒に、対応する道路セグメントに対する追加属性として、格納され得る。
【０１３７】
上述したランク情報を計算する方法の一部、特に再帰的方法に従うと、図３Ｃのステップ１１３２あるいは図５のステップ２２５における最適ルートの計算の複雑さは、最適ルート探索が実行されるべき道路セグメントのサブセットを選択することによって、緩和される。考慮すべき道路セグメントの総数を減らすことによって、少なくとも所定のタイルＴおよびその所定のタイルの所定の境界に対して、作業メモリユニット５０の中に、最適ルートの計算に必要とされる全ての道路セグメントを格納することが実行可能となる。それゆえ、システム１の作業メモリユニット５０は、全ての道路セグメントデータと、また、必要に応じて、ステップ１１３２または２２５で、それぞれ実行されるような最適ルートの計算に必要なタイリング定義データとを格納することに適合されることが好ましい。
【０１３８】
既に上述したように、本発明に従うランク情報を計算する方法は、コンピュータクラスタまたはグリッド上で実行されるように適合される。これは、ランク計算に対する全体の処理時間を短縮するのに望ましい。タイルに含まれる道路セグメントに対するランク情報を計算する上述の方法の各ステップは、そのタイルの近傍で動作するのみであるため、その方法に、道路セグメントのランク情報を並列計算するように適合された様々なスキーム（例えば、ピアツーピアまたはマスタワーカスキームのような）を適応するのは容易である。例示的に、しかし、決して限定する意味でないが、次いで、マスタワーカスキームが説明される。ここで、マスタと指定された１台と、任意の台数のワーカからなるコンピュータネットワークが、使用され得る。概念的に、マスタは、問題を小さなジョブに分解し、そのジョブをワーカに委託し、また、最終的にその結果の回収も行い得る。マスタおよびワーカは、道路網のデータの共通のコピー上で動作し得て、各道路セグメントは、今までに計算された最大ランクでマークされている。実際には、マスタに対する限定的なアクセスを用いて、完全なデータのコピー１つのみを有し、各ジョブに対して、マスタによって生成された道路セグメントのサブセットのローカルコピー上で、ワーカに動作させることが、容易であり得る。ランク情報が増加するランク値に対して計算される上述の再帰的方法において、外側のループで、マスタは、ランク値０から開始して、ランク値ｋにわたり繰り返す。すなわち、マスタは、考慮すべきタイル近傍のサイズにわたり、繰り返す。内側のループで、マスタは、全てのタイルにわたり繰り返し、少なくともランクｋ＋１を有し、そのようなタイル（例えば、Ａ）に含まれる道路セグメントのサブセットの計算を委託する。特定のタイルＡに対し、これら道路セグメントＧ（ｋ＋１，Ａ）を計算するために、道路セグメントのサブセットのみが、考慮される必要がある。このサブセットは、上述の方法で記載されたように選択され得る。より特定的には、例えば、Ｇ（ｋ＋１，Ａ）を計算するためには、タイルＡからタイル距離ｄＡＢ＝ｋを有するタイルＢにおいて、Ｇ（ｍｉｎ（ｋ＋１−ｄＡＢ），Ｂ）を含む道路セグメントのみが、考慮される必要がある。ランク情報は、増加するランク値に対して計算されるので、これら道路セグメントは、既知である。全てのタイルＢにわたるこれら道路セグメントのユニオンは、Ｇ（ｋ＋１，Ａ）の計算に対して十分である。ワーカが、道路セグメントがＧ（ｋ＋１，Ａ）に含まれることを決定すると、共通ストレージ内の道路セグメントのランク属性は、ｋ＋１に増える。共通ストレージのない場合、ワーカはマスタによって送信されたローカルコピーを使用し、そのローカルコピー内のランクを更新し、そして、更新されたデータをマスタに返信する。次いで、マスタは、完全なデータセットのコピー内に格納されたデータを更新する。全てのワーカが、所望の結果を計算した後に、マスタは、ｋをインクリメントし、外側ループの次の繰り返しを開始する。
【０１３９】
上記のマスタワーカスキームは、さらに最適化され得る。特に、単一のグループのタイルに対してより、タイルのより大きなグループに対して、ジョブを生成することは、より効率的である。それゆえ、ワーカは、選択されるタイルのセットの各セットが十分小さくなるように、これら選択されたセットを割り当たえられ得る。こうして、このセットの中の各Ａに対して、Ｇ（ｋ＋１，Ａ）を計算するのに必要とされる全ての道路セグメントデータおよび関連するデータのユニオンは、ワーカのメモリ内に同時に格納され得る。ワーカは、この必要とされるデータを全て取り込み、そのワーカに割り当てられたタイルのセット内の全てのタイルにわたって、繰り返す。このようにして、マスタとワーカとの間の通信処理量（ｃｏｍｍｕｎｉｃａｔｉｏｎ ｏｖｅｒｈｅａｄ）は、軽減され得る。
【０１４０】
ランク情報の計算に使用されるのが、単独のコンピュータであるか、あるいは、コンピュータクラスタまたはグリッドであるかに関わらず、計算されたランク情報は、引き続く最適ルートの計算で使用するために、出力ユニット７０を介して、出力され得る。後者をさらに迅速化するために、道路セグメントデータおよび対応するランク情報は、必要とされるデータの取り出しを容易にし、効率よくこなせるように、アレンジされることが好ましい。これは、特定の方法で、格納または出力のために、道路セグメントデータをアレンジすることによって、達成される。上記のランク情報を決定する第三の代替的方法で議論したように、タイルサイズが、ランク値の決定において異なっている場合、道路セグメントデータは、まず、タイルサイズに従って、アレンジされる。異なるタイルに対応するデータは、タイルの地理的位置に従って、アレンジされる。各タイルに対して、データは、ランク情報に従ってアレンジされる。典型的には、道路セグメントデータは、道路セグメント属性のようなランク情報を含むアレイとして、格納される。そして、対応する道路セグメントが、幾つかの元々の道路セグメントを相互結合して形成されているなら、道路セグメントは、また、元々の道路セグメントに関連する情報も含む。さらに、データの取り出しを効率よくするために、索引ファイルが、特定のタイルサイズ、タイル、および、ランク情報に関連するデータが、道路セグメントのどこに見つけられ得るかに関する情報を含んで、提供され得る。
【０１４１】
前処理する段階（ｐｈａｓｅ）で計算されるランク情報は、地図上の相対位置に基づく道路セグメントの重要性の尺度を提供するので、ランク情報は、後のステージで実行される最適ルートの決定を迅速化するために、取り出され得る。このような最適ルートの決定は、車両に搭載するナビゲーションシステムによって、実行されることが多い。本発明の実施形態に従うナビゲーションシステム、および、そのシステムの最適ルートを決定するシステムは、図１０〜図１３を参照しながら、以下に記載される。
【０１４２】
図１０に示すナビゲーションシステムは、入力ユニット４１０、出力ユニット４１１、位置検出手段４１２、および、最適ルートを決定する（より特定的には計算する）システム４２０を備える。コンポーネント４１０〜４１２のそれぞれは、従来のナビゲーションシステムから知られている対応するコンポーネントの一つであり得る。例えば、入力ユニットは、タッチスクリーンを備え得るし、出力ユニットは、文書音声変換ユニットに結合されたディスプレイまたはラウドスピーカを備え得るし、また、位置検出手段は、ＧＰＳ受信機またはジャイロスコープを備え得る。
【０１４３】
最適ルートを決定するシステム４２０は、図１１に、より詳細に示される。システム４２０は、第一のストレージユニット４３０を備える。このユニット４３０は、本実施形態に従うと、道路セグメントデータ、および、上述した前処理する段階の間に計算された関連するランク情報データの双方を格納するように適合される。データはアレイ４３１〜４３３として格納され、ランク情報は追加道路セグメントの属性として、これらアレイの中に含まれる。代替的に、ランク情報データは、個別のストレージユニットを介しても、また、提供され得る。システム４２０は、さらに、例えば、数字の多重項４４１、４４２、４４３の形式で、タイリング定義データを格納するために、追加のストレージユニット４４０を備える。システム４２０は、さらに、処理ユニット４５０、および、道路セグメントデータのサブセットを、例えば、これもまた、アレイ４６１および４６２の形式で、格納するのに適合された作業メモリユニット４６０を備える。これらアレイは、道路セグメントの位置および方向、ならびに、関連する重み付けファクタおよび／またはランク情報に関する情報を含む。タイリング定義データおよび道路セグメントデータは、道路セグメントデータを前処理するために使用されたデータセットと、実質的に同一である。ただし、この道路セグメントデータは、追加的に、ランク情報を含む点は異なる。
【０１４４】
ルートの出発点と目的地に関する情報を受信した後、最適ルートを決定するシステム４２０は、最適ルート探索を開始し、最適ルートを計算する。ランク情報、および、道路セグメントを含むエリア用のタイリングを提供することによって、最適ルートの計算を、効率的に実行することが可能になる。これについては、図１２Ａおよび図１２Ｂを参照して、以下に記載される。出発点が出発タイルＳに含まれ、目的地が目的地タイルＤに含まれると仮定し、さらに、出発タイルと目的地タイルは、１より大きいタイル距離を有すると仮定すると、出発点と目的地とを結ぶ任意の最適ルートは、出発タイルと目的地タイルとから、それぞれ少なくとも１のタイル距離を有するタイルを通過する。それゆえ、全てのそのようなタイルの中で、少なくとも１のランク値を有する道路セグメントのみを考慮すれば、十分である。同様にして、上述のようなランク値の定義によって、出発タイルおよび目的地タイルの双方から少なくとも２のタイル距離を有するタイルの中で、少なくとも２のランク値を有する道路セグメントは、出発点から目的地への最適ルートに、潜在的に含まれる。それゆえ、最適ルート探索を、対応するタイルの中で、これら道路セグメントに、限定すれば、十分である。これは、タイリング５１０に対して、出発点タイルＳと目的地タイルＤとがそのタイリング５１０の向かい合う角にあるようにアレンジされて、図１２Ａに模式的に示されている。タイル５１１およびタイル５１５は、出発タイルおよび目的地タイルの双方から、１以上のタイル距離を有する。それゆえ、少なくとも１のランク値を有する道路セグメントのサブセットのみが、考慮される必要があり、これは、このサブセットが対応するタイル用であることを表す記号Ｇ（１）によって模式的に示される。当然、Ｇ（１）は、タイル５１１および５１５に対しては異なり、タイル索引は、簡略化のために削除されていることに、留意すべきである。同様の議論は、タイル５１２およびタイル５１６に関しても当てはまる。タイル５１２および５１６に対して、少なくとも２のランク値を有する道路セグメントのサブセットのみが、考慮される必要があり、タイル５１３および５１７に対して、少なくとも３のランク値を有する道路セグメントのサブセットのみが、考慮される必要があり、タイル５１４に対して、少なくとも４のランク値を有する道路セグメントのサブセットのみが、考慮される必要がある。それゆえ、最適ルートの計算は、ランク情報を考慮して実行される。より特定的には、道路セグメントのサブセットに対する最適ルートを計算し、そのサブセットは、ランク情報およびタイリングデータに基づいて選択されることで、実行される。
【０１４５】
ランク情報の計算が、所定の最大ランク値で終了した場合、最適ルート探索が実行される道路セグメントのサブセットは、図１２Ｂに示すように、追加の道路セグメントを含み得る。タイリング５２０に対して、所定の最大ランク値が３に等しい場合、すなわち、ランク情報３が、３以上のランク値を有する全ての道路セグメントに割り当てられた場合、最適ルート探索が実行される道路セグメントのサブセットも、また、タイル５２４および５２５で、ランク値３に等しいランク値を有する道路セグメントを含む。サブセットに道路セグメントを加えることで、計算の複雑さは増加するが、最適ルートを決定するシステム４２０によって実行される方法は、それでもなお、正確な結果を提供する。
【０１４６】
システム４２０によって実行される方法は、以下に図１３Ａおよび図１３Ｂを参照しながら説明される。図１３Ａを参照すると、この実施形態に従う最適ルートを計算する方法は、ステップ６１０で示すように、ランク情報およびタイリングデータに基づいて、道路セグメントのサブセットを選択するステップと、ステップ６２０で示すように、道路セグメントのサブセットに基づいて、最適ルートを計算するステップと、ステップ６３０で、最適ルートを、例えば、ナビゲーションシステムの出力ユニットに出力するステップを包含する。
【０１４７】
本実施形態に従う道路セグメントのサブセットを選択するプロセスの流れ図は、より詳細に図１３Ｂに示される。まず、ステップ６１１で、出発点を含む出発タイルと、目的地を含む目的地タイルとが、決定される。ステップ６１２で、これらタイルの間の出発−目的地タイル距離ｄＳＤが計算される。続いて、ステップ６１３で、ｄＳＤを２で除算したフロア以下の整数値ｋが選択される。前処理段階でのランク情報の計算が、所定の最大ランク値で終了した場合、ｋは典型的には、この最大ランク値から１を減じた値を超えないような値が選択される。ステップ６１４で、最適ルートの探索が実行されるべき道路セグメントのサブセットＧ’は、そのタイリングの全てのタイルを含み、少なくともｋ＋１のランク値（Ｇ（ｋ＋１）で示す）を有する全ての道路セグメントのセットとして、初期化される。サブセットＧ’が初期化された後、ステップ６１５〜６１９で、追加の道路セグメントは、Ｇ’の中に含まれる。出発タイルＳまたは目的地タイルＴから各タイルＴまでの距離は、ｄＴＳおよびｄＴＤと記されるが、出発タイルＳまたは目的地タイルＤのいずれかからｋ以下のタイル距離を有する各タイルＴに対して、Ｔに含まれ、タイル距離ｄＴＳおよびｄＴＤの小さなタイル距離以上のランク値を有するセットは、Ｇ’の中に含まれる。Ｔの中に含まれ、タイル距離ｄＴＳおよびｄＴＤの小さなタイル距離以上のランク値を有する道路セグメントのセットは、Ｇ（ｄｍ，Ｔ）で示される。このステップは、出発タイルＳまたは目的地タイルＤのいずれかから、ｋ以下の距離を有する全てのタイルに対して、繰り返される。特に、この方法に従うと、出発タイルまたは目的地タイルに含まれる全ての道路セグメントは、Ｇ’に含まれる。繰り返しが終了した後、Ｇ’は、さらなる処理のために、ステップ６１８に提供される。
【０１４８】
上述したように、例えば、図６に示されるランク情報を計算する第三の代替方法において、ランク情報は、粗調整されたタイリングの階層のために計算され得る。この場合、粗調整されたタイリングに対して計算されたランク情報または擬似ランク情報は、元々のタイリングに対するランク値に、直接、変換（ｔｒａｎｓｌａｔｅ）しない。しかしながら、道路セグメントのデータを前処理する間と同様に、最適ルートを計算する間にも、粗調整されたタイリングの同じ階層を使用することによって、正確な最適ルートは、それでもなお、効率的に決定され得る。それゆえ、道路セグメントデータの前処理が、タイリングの階層に基づいてなされた場合、タイリング定義データは、最適ルートの計算のために、例えば、タイリングのそれぞれを記述する数学的関数の形式で、これらタイリングのそれぞれに対し、提供される。
【０１４９】
タイリングの階層のために、ランク値はその階層の様々なレベルに対して計算され、道路セグメント６１０のサブセットを選択するステップは、上記に記載されたステップと比較し、変更される。それにも関わらず、粗調整する階層の各レベルで、プロセスは、図１３Ｂに示すプロセスと、実質的に同様である。データ前処理の間で、少なくともｒのランク値を有する全ての道路セグメントの計算後、道路網は最初に再定義される。この間、タイリングは、元々のタイリングＴからＴ’に、同時に粗調整される。次いで、少なくとも０の値を有する道路セグメント、少なくとも１の値を有する道路セグメントなどが順に、少なくともｒの値を有する道路セグメントまでが、元々のタイリングのタームでから知られている。次いで、ステップ６１０で、道路セグメントのサブセットが、以下の方法で選択される。まず、出発点を含むタイルＳおよび目的地を含むタイルＤからｒ未満の距離を有する全ての道路セグメントに対して、道路セグメントは、上述の図１３Ｂのステップ６１５、６１６、６１７および６１９と同様に、Ｇ’に含まれる。引き続き、Ｓからｒ未満の距離を有し、Ｄからｒ未満の距離を有する元々のタイリングＴ内のタイルのセット（それぞれ、Ｓ’およびＤ’と記し、元々のタイルの「ハル（ｈｕｌｌ）」と称する）をカバーするＴ’内のタイルのセットが、決定される。ｒ未満のタイル距離は、それでもなお、元々のタイリングＴのタームで測定されることに留意すべきである。引き続き、Ｓ’に含まれ、Ｓから少なくともｒの距離を有する元々の各タイルに対して、および、Ｄ’に含まれ、Ｄから少なくともｒの距離を有する元々の各タイルに対して、少なくともｒ−１のランク値を有するこれらタイルの道路セグメントは、道路セグメントのサブセットＧ’に含まれる。Ｓ’およびＤ’の外側で、道路セグメントは、最初に粗調整されたタイリングに対し計算されたランク情報に基づいて、Ｇ’に含まれ得る。より特定的には、Ｓ’およびＤ’の双方から少なくともｋの距離を有する粗調整されたタイリングの任意のタイルＡ’に対しては、Ａ’に含まれ、少なくともｋのランク値を有する道路セグメントのセットを含めば、十分であるが、今や、粗調整されたタイリングに関して決定されたように、道路セグメントのセットは、図１３Ｂのステップ６１５、６１６、６１７および６１９と同様に、Ｇ’に含まれる。粗調整されたタイリングに対するランク値の計算が、ｋより小さな値で終了した場合は、Ａ’に含まれ、決定された最大ランク値を有する道路セグメントは、Ｇ’に含まれる。
【０１５０】
幾つかの増えていく粗調整されたタイリングを備えるタイリングの階層に対して、特定のタイル近傍のハルを決定し、これらハルの外側で、粗調整されたタイリングおよび対応するランク値をもとに、道路セグメントを、道路セグメントのサブセットＧ’に含める上述の方法は、再度、繰り返され得る。
【０１５１】
最適ルートを決定するシステム４２０において、道路セグメントのサブセットの選択は、処理ユニット４５０によって、行われる。処理ユニット４５０は、上述した基準にのっとって、ランク情報およびタイリング定義に従い、道路セグメントを作業メモリ４６０に格納されたデータに含める。作業メモリ４６０は、十分なストレージ容量を提供することが好ましい。それは、サブセットＧ’に対応する道路セグメントデータが、同時に格納され、最適ルート探索が、このデータ上で実行され得るようにするためである。
【０１５２】
道路セグメントのサブセットに対して、最適ルートを計算するステップ６２０は、ＤｉｊｋｓｔｒａのアルゴリズムまたはＡ＊アルゴリズムのような標準的な最適経路アルゴリズムを使用して実行される。こうして、後者の場合、距離ベースの最適ルートに対して、２点間のエア距離が、実際の最適経路コストに対する下限を提供する。時間ベースの最適ルートに対して、特徴的な移動速度で除算されたエア距離が、最適経路コストに対する下限を提供する。
【０１５３】
最適ルートは、ステップ６３０で、例えば、ナビゲーションシステムの出力ユニット４１１のようなユーザインターフェースに出力される。本実施形態に従う最適ルートを計算するシステムは、最適ルートを決定する従来のシステムと本質的に同じ方法で、ナビゲーションデバイスの他のコンポーネントと、インターフェースするために、業界のナビゲーションシステムから既知の様々な機能と、容易に組み合わされ得る。
【０１５４】
最適ルートを計算する上述の方法は、最適ルート問題に正確な解を提供するが、上述の方法の幾つかの変種も、少なくともほぼ最適なルートを提供することは、考えられる。例えば、計算の複雑さを緩和するために、それゆえ、ランタイムを短縮し、メモリスペースの要求を減らすために、道路セグメントがＧ’に含まれるより厳しい条件を設定して、タイル距離およびランク値に依存するサブセットＧ’に含まれる道路セグメントの総数は、減らされ得る。また、最適ルートを決定する間に、タイリング定義と独立した道路セグメントの妥当性の尺度として、ランク情報を使用することも考えられる。例えば、道路セグメントは、ランク値に１を加算した値が、それぞれ出発点から道路セグメント頂点の一つまでの距離と、目的地から道路セグメント頂点の一つまでの距離との最短距離を、道路セグメントを前処理する間に使用される特徴的なタイル端部長さで除算された値未満でない場合、サブセットＧ’に含まれ得る。
【０１５５】
最適ルートを計算する上述の方法は、タイルサイズが１つのみについて説明されてきたが、道路セグメントデータを前処理する間に、タイルサイズが変動する場合は、最適ルートを決定する間に、タイルサイズは、対応して変動することは理解される。特に、出発点または目的地からの距離が増加すると、より高いランク情報値を有する道路セグメントのみが、考慮される必要がある。このランク情報が、ますます粗調整されるタイリングに基づいて、計算されると、タイリングは、最適ルート計算中に、対応して粗調整される。
【０１５６】
上述した実施形態に従うと、最適ルートの計算の１つのモードのみが考慮されてきたが、多数のランク情報データが１つの道路セグメントに対して、提供され得る。異なるランク値は、最短ルート、最速ルート、トンネルなしのルートまたはフェリーなしのルートなどに対応する。次いで、最適ルートの計算は、これら異なるモードの任意の一つに対して、ユーザの選択したモードに基づき、それぞれのモードに対応するランク情報に基づき選択される道路セグメントのサブセットを用いて、実行され得る。ランク情報が様々な異なるコスト関数に対して計算された場合、これらコスト関数のそれぞれに対応するランク情報は、各道路セグメントに対して、格納される。代替的に、各道路セグメントに対し、異なるコスト関数に対して得られたランク値の最大のみが格納され得て、こうして、要求されるストレージ容量を削減し得る。しかしながら、最適ルートの計算は、この後者の場合ですら、正確な最適ルートをもたらす。
【０１５７】
以上のように、本発明の好ましい実施形態を用いて本発明を例示してきたが、本発明は、この実施形態に限定して解釈されるべきものではない。本発明は、特許請求の範囲によってのみその範囲が解釈されるべきであることが理解される。当業者は、本発明の具体的な好ましい実施形態の記載から、本発明の記載および技術常識に基づいて等価な範囲を実施することができることが理解される。本明細書において引用した特許、特許出願および文献は、その内容自体が具体的に本明細書に記載されているのと同様にその内容が本明細書に対する参考として援用されるべきであることが理解される。
【０１５８】
最適ルートを計算するために道路セグメントデータを前処理する方法、前処理された道路セグメントデータに基づいて、最適ルートを決定する方法、および、対応するシステムが提供される。道路セグメントデータを前処理する方法に従うと、タイリングが提供され、ランク情報（ｒ）が、タイリング情報に基づいて、道路セグメント（ｖ）に対して、計算される。このランク情報（ｒ）は、タイリングのタイルを結ぶ最適ルートに対する道路セグメントの妥当性の尺度となる。地図上の相対位置に基づき計算されるランク情報（ｒ）を用いて、引き続く最適ルート計算にランク情報情報が提供される。これによって、例えば、車両におけるナビゲーションシステムにおいて、最適ルートの計算を効率的に実行することが可能になる。
【図面の簡単な説明】
【０１５９】
【図１】図１は、本発明の実施形態に従う道路セグメントデータを前処理するシステムの模式ブロック図を示す。
【図２】図２は、道路セグメントのセットの模式図を示す。
【図３Ａ】図３Ａは、本発明の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図３Ｂ】図３Ｂは、本発明の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図３Ｃ】図３Ｃは、本発明の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図４】図４は、本発明の別の実施形態に従う道路セグメントデータを前処理する方法のサブルーチンを表す流れ図を示す。
【図５】図５は、本発明の別の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図６】図６は、本発明の更なる別の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図７】図７は、タイリングを示し、本発明の実施形態に従うタイル距離の定義を模式的に示す。
【図８】図８は、タイリングおよび道路セグメントを示し、本発明の実施形態に従うランク情報の決定ステップを模式的に示す。
【図９】図９Ａおよび図９Ｂは、本発明の実施形態に従う道路セグメントデータを前処理する方法の再帰的ステップを模式的に示す。
【図１０】図１０は、本発明の実施形態に従うナビゲーションシステムの模式的なブロック図を示す。
【図１１】図１１は、本発明の実施形態に従う最適ルートを決定するシステムの模式的なブロック図を示す。
【図１２】図１２Ａおよび図１２Ｂは、本発明の実施形態に従う最適ルートを決定するために、道路セグメントのサブセットを選択するステップを模式的に示す。
【図１３Ａ】図１３Ａは、個々に、本発明の実施形態に従う最適ルートを決定する方法を表す流れ図を示す。
【図１３Ｂ】図１３Ｂは、本発明の実施形態に従う最適ルートを決定する方法における道路セグメントのサブセットを選択するステップを表す流れ図を示す。
【符号の説明】
【０１６０】
３１０ タイリング
３１１ タイル
３１２、３１３、３１４、３１５、３１６、３１７、３１８ 点
ｖａ、ｖｂ、ｖｃ、ｖｄ、ｖｅ、ｖｆ、ｖｇ 道路セグメント
【技術分野】
【０００１】
本発明は、最適ルートの決定に関する。特に、本発明は、道路セグメントデータを前処理する方法および対応するシステム、前処理された道路セグメントデータに基づいて、最適ルートを決定する方法および対応するシステム、ならびに、ナビゲーションシステムに関する。
【背景技術】
【０００２】
所定の出発点から所定の目的地に至る最適ルートを求めることは、カーナビゲーションシステムあるいは最適ルート情報を提供する他のシステムの主要機能の一つである。
【０００３】
幾つかのアルゴリズムが、最適ルートを求める問題の解決のために、知られているが、これらアルゴリズムを直接、欧州の一国やあるいは米国の道路網のような道路網への適用は、実現できないことが多い。なぜなら、これら道路網には、道路セグメントおよび道路セグメント頂点（ｖｅｒｔｅｘ）が膨大な数あるからである。頂点の数は、百万のオーダーか、それ以上になり得る。なぜなら、カーナビゲーションシステムにおけるメモリおよびルーチンに制約があるために、長距離最適ルート探索に標準的な最短経路アルゴリズムを直接用いることは、実現できないからである。
【０００４】
例えば、ドイツにおける「アウトバーン（Ａｕｔｏｂａｈｎ）」、「連邦道路（Ｂｕｎｄｅｓｓｔｒａｓｓβｅ）」および「郡道（Ｋｒｅｉｓｓｔｒａβｅ）」、英国における「高速道路（Ｍｏｔｏｒｗａｙ）」、「Ａ道路（Ａ ｒｏａｄ）」および「Ｂ道路（Ｂ ｒｏａｄ）」のように、道路網には、道路分類によって表わされる自然な階層構造があることが、最適ルート探索の複雑さを減らすために利用されることが多い。最適ルートの決定は、幾つかのサブタスクに分解される。すなわち、出発地から、例えば、高速道路ジャンクションまたは高速で長距離移動可能な他の道路のジャンクションまでのルート、および、目的地から、例えば、別の高速道路ジャンクションまたは高速で長距離移動可能な他の道路のジャンクションまでのルートそれぞれの２つの短距離ルートを求めるタスクと、使用する高速道路または高速で長距離移動のみを可能とする他の道路におけるこれら２つの高速道路ジャンクション間の最適ルートを求めるタスクである。
【０００５】
道路網の階層構造は、標準化されたＧＤＦ（Ｇｅｏｇｒａｐｈｉｃ Ｄａｔａ Ｆｉｌｅ）形式を有するマップによっても反映される。ここで、全ての道路セグメントは、機能的道路階級（ＦＲＣ）と呼ばれる属性を有し、このＦＲＣは、道路階層を定義し、地域的に重要な道路から国家的あるいは国際的に重要な道路に分類することを意図している。
【０００６】
特許文献１は、出発点と目的点との間の行程を決定するプロセスを開示している。ここで、道路網は、少なくとも２つのレベルに分類され、格納されている。すなわち、通行され得る道路全ては、低レベルに含まれ、低レベルの道路網の異なる地域を結ぶ道路は、高レベルに含まれる。典型的には、高レベルは、高速で長距離移動可能な高速道路のような道路を含む。
【０００７】
しかしながら、道路セグメントの階層構造は、人間の専門家によって、指定されるので、決定されたルートが、真に最適でないこともあることに留意すべきである。さらに、最速ルートを狙いとするＦＲＣのような標準的道路階層に頼っても満足いかないこともある。それゆえ、最短ルートあるいは他のルート選択を計算するのに不適切なこともある。それゆえ、人間の専門家によって指定された道路重要性を定量化する値は、不十分であり得る。むしろ、地図上の相対位置（ｍａｐ ｇｅｏｍｅｔｒｙ）から道路セグメント属性を決定する方法が、望ましい。
【０００８】
特許文献２は、ソースノードから目的地ノードへの望ましい経路を決定する方法を開示している。特許文献２では、道路網の各ノードと関連する範囲測定基準（ｒｅａｃｈ ｍｅｔｒｉｃ）の証印（ｉｎｄｉｃｉａ）を含む予備的なルーティングのデータセットが、提供される。所定のノードに対する範囲測定基準は、道路網の任意の許容可能な他のノードの間の望ましい経路の一部をなす、その所定ノードのポテンシャルを示す。
【特許文献１】欧州特許第０ ３２３ ４８５号明細書
【特許文献２】国際公開第０３／０７９１５５号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、それでもなお、地図上の相対位置に基づいて決定される道路セグメント属性に基づく最適ルート決定方法を提供する必要性がある。特に、このような道路セグメント属性が、たとえ大きな道路網であっても効率的に決定され得る最適ルートの決定方法に対する必要性がある。
【課題を解決するための手段】
【００１０】
（発明の概要）
本発明に従うと、この必要性は、請求項１に記載の道路セグメントデータを前処理する方法、請求項１９に記載の最適ルートを決定する方法、請求項２８に記載の道路セグメントデータを前処理するシステム、請求項３６に記載の最適ルートを決定するシステム、および、請求項４１に記載のナビゲーションシステムによって、対処される。従属の請求項は、本発明の好ましい実施形態あるいは有利な実施形態を規定する。
【００１１】
本発明に従って、道路セグメントデータを前処理する方法は、該道路セグメントデータを提供するステップと、該道路セグメントが含まれるエリアをカバーするタイリングを定義するステップと、該タイリングのタイルを結ぶ最適ルート用の該道路セグメントの妥当性を定量化するランク情報を、道路セグメントに対して決定するステップとを包含する。この道路セグメントデータを前処理する方法は、最適ルートの決定前に実行され、道路セグメントのランク情報が提供されると、最適ルートを迅速に求める（ｅｘｐｅｄｉｔｅ）。道路セグメントデータを前処理する方法は、主として、カーナビゲーションシステムで、最適ルート決定の一部として実行される。道路セグメントデータを前処理する方法は、自動的に行われることが好ましい。タイリングを定義するステップによって、ランク情報が効率的に決定できるようになる。
【００１２】
様々な実施形態に従うと、ランク情報は、タイリングに基づき、そのタイリングに依存して決定される。実施形態において、道路セグメントが任意の最適ルートに含まれるかどうかによって、道路セグメントの「妥当性」が定量化される。その最適ルートは、所定のタイル数を通過するルートか、または、出発タイルから所定の距離離れ、出発タイルから目的地タイルに延びるルートか、あるいは、出発タイルと目的地タイルとが、その道路セグメントが位置するタイルから所定の最低距離を有して、出発タイルから目的地タイルに延びるルートである。
【００１３】
以下の本明細書の様々な実施形態の記述から明らかになるように、ランク情報は様々な方法で定義され、決定され得る。好ましい実施形態においては、ランク情報は、タイリングのタームで測定された最適ルートの長さに対する尺度を示す。その尺度には、道路セグメントが、依然として含まれている。
【００１４】
ランク情報は、タイル端部（ｅｄｇｅ）に位置する点を結ぶ最適ルートに対する道路セグメントの妥当性を定量化することが好ましい。これによって、考慮されるべき潜在的な出発点と目的地の総数を減らし、効率的に迅速にランク情報を決定できる。
【００１５】
タイルまたは道路セグメントは、各道路セグメントが、タイリングの多くとも１つのタイルに含まれるように定義されることが、さらに好ましい。すなわち、道路セグメントが、その頂点を除いては、タイル内側の中に含まれるようなタイルは、１つのみしかないように、各道路セグメントに対して、定義されることが好ましい。このようなタイリングの定義は、各道路セグメントを１つのタイルにユニークに割り当てることを可能とし、それゆえ、タイリング情報に基づいたランク情報を決定できる。こうして、また、タイリングの定義は、道路セグメントを含むタイルを特定する各道路セグメントに対して、追加属性の意味でも提供され得る。各道路セグメントがタイリングのタイルの多くとも１つにしか含まれないように定義することは、元々の道路セグメントとタイル端部との交点に補助の頂点を導入することで、達成される。それゆえ、このようにタイリングを定義することは、道路セグメントを再定義するステップも含み得る。
【００１６】
道路セグメントに対して、ランク情報を決定するステップは、道路セグメントを含むタイルを決定するステップと、道路セグメントを含むタイルから、少なくとも所定のタイル距離を有する第一のタイルを選択するステップと、道路セグメントが、第一のタイルに位置する出発道路セグメント（すなわち、第一のタイルの内部または端部に位置する出発道路セグメントの頂点）を有する最適ルートに含まれるかどうかを決定するステップとを包含する。これらのステップに従って、ランク情報は、最適ルート用の道路セグメントの妥当性に対する尺度として決定される。その最適ルートは、その道路セグメントから少なくとも所定のタイル距離を有するタイルに位置する出発道路セグメントを有する。最適ルートの決定は、該第一のタイルの端部に位置する出発点を有するルートに制限され得る。可能な出発点の数を制限することによって、ランク情報の決定は、より効率的に実行され得る。
【００１７】
ランク情報を決定するステップは、ランク情報が決定されるべき道路セグメントを含むタイルから、少なくとも所定のタイル距離を有する第二のタイルを選択するステップをさらに包含し得る。ここで、最適経路の目的地道路セグメントは、この第二のタイルに位置する。こうして、ランク情報は、最適ルート用の道路セグメントの妥当性に対する尺度となる。この最適ルートにおいては、出発道路セグメントおよび目的地道路セグメントの双方が、ランク情報が決定されるべき道路セグメントから少なくとも所定のタイル距離を有するタイルに位置する。可能な目的地道路セグメントは、第二のタイルの端部に位置する頂点を有する目的地道路セグメントに制限されることが好ましい。可能な目的地の数を制限することで、ランク情報の決定は、さらに、より効率的に実行され得る。
【００１８】
ランク情報を決定するステップは、さらに、ランク情報が決定されるべき道路セグメントを含むタイルから所定の距離を有する全ての可能な第一および第二のタイルを選択するステップと、その道路セグメントが、第一のタイルのうちの１つのタイルにある出発道路セグメントと、第二のタイルのうちの１つのタイルにある目的地道路セグメントとを結ぶ最適ルートに含まれるかどうかを決定するステップとを含む。ここで、再び、最適ルート探索は、第一のタイルの端部に位置する出発点と、第二のタイルの端部に位置する目的地とに制限され得る。このランク情報を決定する方法によって、道路セグメントが、特定の要求に合う任意の最適経路に含まれるかどうかを決定でき、こうして、一般的な道路セグメント属性を提供できる。
【００１９】
ランク情報を決定するステップは、道路セグメントが上述したような最適ルートに含まれる所定のタイル距離の最大を決定するステップをさらに包含し得る。こうして、ランク情報は、道路セグメントを依然として含む最長の最適ルートと、それゆえに、道路セグメントが依然として重要な長距離ルートの長さとを定量化する。さらに、ランク情報はタイリングに基づき決定されるので、ランク情報は効率的に決定され得る。
【００２０】
ランク情報を決定するステップは、所定のタイル距離の値を増やして、連続的に実行されることが好ましい。それは、所定のタイル距離の大きい値に対して、ランク情報の決定がより複雑化したステップにおいても、所定のタイル距離の小さな値に対する先行するステップで得られた結果に基づいて、実行できるようにするためである。特に、ランク情報を決定するのに、必要とされる最適ルート探索は、道路セグメントのサブセット上で実行され得る。このサブセットは、所定のタイル距離の小さな値に対して得られた結果に基づいて、選択される。こうして、以前に得られた結果に依存する道路セグメントを消去して、ランク情報の複雑さを減らすことが実現でき、それゆえ、引き続くステージで、ランク情報の決定が容易になる。
【００２１】
ランク情報を決定する後のステージにおいて、所定のタイル距離の値が増えるに伴い、タイルサイズは、増えることも、増えないこともあり得る。有利な実施形態においては、ランク情報が幾つかの連続的なランク値に対して決定された後、タイリングは粗調整され、その一方で、道路網は同時に再定義される。規則的なタイリングに対して、粗調整は、タイルの端部長さを増やすことからなり得る。道路網の再定義は、今までに決定された最大のランク情報を有する道路セグメントのサブセットとして、新たな道路網を定義することからなり得る。これらのステップが繰り返さられ得る結果として、粗調整されたタイリングの階層およびランク値の関連する階層が形成される。好ましい実施形態においては、３回または４回連続的に増やしたランク値に対して、ランク情報を決定した後に、正方形タイリングのタイル端部の長さが２倍になり、道路網は再定義される。これらの実施形態において、次いで、道路網は、粗調整する階層の以前のレベルに対して決定されたように、少なくとも３または４のランク情報を有する道路セグメントのセットとして、再定義される。
【００２２】
道路セグメントデータを前処理する方法は、道路セグメント重み付けファクタを提供するステップをさらに包含し得る。このファクタは、ランク情報を決定するステップの間に考慮される。このような重み付けファクタによって、追加の道路セグメント属性を考慮に入れることが可能となる。可能な重み付けファクタは、道路セグメント長、道路セグメントを通過する時間、あるいは、特徴的な道路セグメント移動速度と組み合わせた道路セグメント長を定量化する。重み付けファクタは、また、道路セグメントがトンネル区間あるいはフェリー区間を含むかどうかにも依存し得る。重み付けファクタは、また、道路セグメント上の移動方向にも依存し得る。追加的に、あるいは、代替的に、重み付けファクタは、道路セグメントの頂点との関連から提供され得る。この場合、頂点の重み付けファクタは、所定のルートと関連するコスト関数を計算するために、道路セグメントの重み付けファクタへの追加として、あるいは、その代替として、考慮され得る。道路セグメントの頂点と関連する重み付けファクタを提供することで、例えば、道路セグメントの頂点で運転方向を変更するのに関連する時間が考慮され得る。それゆえ、重み付けファクタによって、様々な移動の選択において、最適ルートの決定、あるいは、引き続く最適ルートの決定で用いるための道路セグメントデータの前処理が可能となる。
【００２３】
ランク情報を決定するステップは、各道路セグメントに対して、実行され得ることが好ましい。次いで、ランク情報は、引き続く最適ルートの決定の中で、各道路セグメントに提供され得る。こうして、特定の最適ルートの決定に対して、全ての道路セグメントの妥当性を決定することが可能となる。
【００２４】
ランク情報を定義するステップが、上述した実施形態の幾つかに記載したように、最適ルート探索を含む場合、この最適ルート探索は、ＤｉｊｋｓｔｒａのアルゴリズムまたはＡ＊アルゴリズム、あるいは、グラフ理論で知られる任意の他の最適経路アルゴリズムを使用して実行され得る。こうして、ランク情報の効率的決定が可能になる。
【００２５】
タイリングを決定するステップは、各タイルに端部データまたは頂点データを提供するステップを包含し得る。代替的に、タイリングを決定する方法は、例えば、タイル形状およびサイズ、ならびに、第一のタイル位置を特定することによって、特定され得る。このタイリングの定義における柔軟性は、タイリングを定義する方法の選択を可能とする。これは、ストレージまたはランタイムの要求に対する観点から、最も都合がよい。
【００２６】
タイルサイズは、タイリング全体にわたって異なり得る。タイルサイズは、道路セグメントが含まれるエリアにおける地域の道路セグメント密度または道路頂点密度によって、選択され得る。こうして、異なるタイルで、１つのタイル内の道路セグメントまたは頂点の数が、同程度になり得て、その結果、計算の複雑さも同程度になり得る。
【００２７】
タイルは、多角形の形状になるように選択され得る。特に、タイルは、長方形の形状であり得る。好ましくは、タイルは正方形の形状が選択される。この場合、どのタイルに、所定の道路セグメントまたは道路頂点が含まれるかを決定することが、特に簡単になる。
【００２８】
ランク情報を決定するステップのために、タイル距離が定義される必要がある場合、様々な定義が使用され得る。２つのタイル間のタイル距離は、タイル距離が整数となるように、２つのタイルを結ぶ経路を通過するタイル端部またはタイル頂点の最小数として定義されるのが好ましい。このことは、さらなる処理において、都合がよい。代替的に、タイル距離は、タイルの中心またはタイルの角、あるいは、任意の他の測定基準の間の距離として、定義され得る。
【００２９】
道路セグメントデータを前処理する方法は、１つのタイルに含まれる道路セグメントのシーケンスを新たな道路セグメントに、相互結合するステップをさらに包含し得る。重み付けファクタが道路セグメントおよび／または道路セグメント頂点に提供される場合、このステップは、典型的には、重み付けファクタを新たな重み付けファクタに相互結合するステップを伴う。この道路セグメントを新たなより長い道路セグメントへの相互結合によって、引き続く最適ルート探索における計算の複雑さを緩和できる。
【００３０】
ランク値が、増加するランク値に対して、再帰的に決定される場合、道路セグメントのシーケンスを新たな道路セグメントに相互結合するステップは、また、中間ステージでも実行され得る。こうして、引き続くステップでの計算の複雑さをさらに緩和できる。同様に、ランク情報が、上述のような粗調整されたタイリングの階層に基づいて決定される場合、道路セグメントを相互結合するステップは、道路網が再定義されたときに、実行され得る。
【００３１】
ランク値が、増加するランク値に対して、再帰的に決定される場合、道路セグメントデータを前処理する方法は、所定の道路セグメントのランク情報が決定された後、タイリングを粗調整するステップを包含し得ることが好ましい。これによって、タイルの総数を減らすことができ、こうして、ランク情報の効率的な決定がさらに容易なる。
【００３２】
データを前処理する方法は、道路セグメントを備える道路網の観点から記載されてきたが、この方法は道路網に限定されない。むしろ、上述の局面または実施形態の任意の一つに従う方法は、複数の端部を含む任意のグラフ上で実行され得る。こうして、グラフは道路網として解釈されるべきであり、グラフの端部は、上述の観点で道路セグメントとして解釈されるべきである。グラフは、方向性があることも、ないこともあり得る。本発明が適用され得るグラフの追加の例としては、電力網の電線、または、通信のデータライン、あるいは、データネットワークを含む。
【００３３】
道路セグメントデータを前処理する方法は、引き続く最適ルートの決定での使用のために、決定されたランク情報を出力するステップを包含することが好ましい。ランク情報を出力するステップは、また、道路セグメントデータを格納するステップを含むことが好ましい。ここで、道路セグメントデータは、道路セグメントおよび／または道路セグメントを含むタイルに対応するランク情報に従って、アレンジされている。タイルサイズが、ランク情報を決定する間に、変動する場合、道路セグメントデータは、ランク値および／または対応するタイルに加えて、タイルサイズにも従って、さらにアレンジされ得る。出力された道路セグメントデータは、道路セグメント属性として決定されたランク情報を含む。追加のデータセットは、出力された道路セグメントデータを含むファイルまたはデータベースで、タイルに対応する道路セグメントデータの位置に関する情報を含んで提供されることが、さらに好ましい。
【００３４】
本発明に従って、出発点から目的地への最適ルートを決定する方法は、道路セグメントデータを提供するステップと、本発明の道路セグメントデータを前処理する方法に従って決定されたランク情報データを提供するステップと、該道路セグメントデータおよび該ランク情報データに基づいて、出発点から目的地への最適ルートを決定するステップとを包含する。ランク情報データを提供することによって、最適ルートの決定は、より効率的に、より迅速に実行され得る。ランク情報は、全ての道路セグメントに、提供されることが好ましい。代替的に、ランク情報は、道路セグメントのサブセットのみに、提供され得る。ランク情報は、追加の道路セグメント属性として、道路セグメントデータに組み込まれることも、あるいは、個別に提供されることもあり得る。
【００３５】
好ましい実施形態において、最適ルートを決定する方法は、ランク情報に基づいて、道路セグメントのサブセットを選択するステップを包含する。最適ルートを決定するステップは、この道路セグメントのサブセットに基づいて、実行される。道路セグメントのサブセットを選択することによって、最適ルート探索における計算の複雑さは緩和される。
【００３６】
最適ルートを決定する方法は、道路セグメントが含まれるエリアをカバーするタイリングを定義するステップを包含することが好ましい。この道路セグメントの各道路セグメントは、そのタイリングの多くても１つのタイルの中にしか含まれないように、タイリングが定義されること、あるいは、道路セグメントが定義されることが、さらに好ましい。タイリングは、道路セグメントのランク情報を決定するのに対して使用されるタイリングと同一であることが、さらになお好ましい。タイリングを定義することで、最適ルートの決定は、さらに単純化される。好ましい実施形態において、最適ルートを決定するのに使用されるタイリングは、データを前処理するのに使用されるタイリングと同一である。同様に、好ましい実施形態において、粗調整されたタイリングの階層が、データを前処理するために使用される場合、同じ粗調整されたタイリングの階層が、最適ルートを決定するために使用される。これらの好ましい実施形態に従うと、ほぼ最適なルートだけでなく、正しい最適ルートを決定することが可能になる。
【００３７】
道路セグメントのサブセットを選択するステップは、次いで、出発点を含む出発タイルを決定するステップと、目的地を含む目的地タイルを決定するステップと、道路セグメントランク情報、および、道路セグメントを含むタイルの出発タイルまたは目的地タイルからのタイル距離に基づいて、道路セグメントを道路セグメントのサブセットに含めるステップとを包含する。次いで、道路セグメントのサブセットに組み込まれるべき道路セグメントの選択は、タイリングに対して、長距離最適ルート用の道路セグメントの妥当性をランク情報が定量化するという事実を反映し得る。それゆえ、最適ルートの正確な決定が可能となる。
【００３８】
特に、好ましい実施形態において、道路セグメントのサブセットを選択するステップは、出発点を含む出発タイルから、目的地を含む目的地タイルまでの出発−目的地タイル距離を決定するステップと、出発−目的地のタイル距離に基づく最小ランク値を選択するステップと、最小ランク値以上のランク値を有する全ての道路セグメントを、道路セグメントのサブセットに含めるステップとを包含する。より詳細には、最小ランク値は、出発−目的地のタイル距離を２で除算し、１を加算したフロア以下から選択され得る。それゆえ、大きな出発−目的地のランク値に対して、最小ランク値は、大きくなるように選択され得る。その結果として、サブセットに含まれる道路セグメントの数は、道路セグメントの総数より、実質的に小さくなる。
【００３９】
好ましい実施形態に従って、道路セグメントのサブセットを選択するステップは、出発タイルまたは目的地タイルからの距離が、最低ランク値から１を減じた値以下を有するタイルを決定するステップと、そのタイルに含まれる道路セグメントに対するランク情報を取り出すステップと、そのランク値が、そのタイルの出発タイルからのタイル距離と、そのタイルの目的地タイルからのタイル距離とのそれぞれのうちの小さなタイル距離以上であれば、道路セグメントを道路セグメントのサブセットに含めるステップとをさらに包含する。
【００４０】
道路セグメントのサブセットに基づき、最適ルートを決定するステップに対して、道路セグメント重み付けファクタおよび／または道路セグメント頂点重み付けファクタが、例えば、道路セグメント属性として、提供され得る。道路セグメント重み付けファクタおよび／または道路セグメント頂点重み付けファクタは、道路セグメントデータを前処理するために提供されたものと、同一であることが好ましい。前処理の段階（ｐｈａｓｅ）と同様に、重み付けファクタは、異なる移動の選択に基づいて、最適ルートを決定することができる。再び、重み付けファクタは、道路セグメントを通過する方向に依存し得る。好ましい実施形態において、道路セグメント重み付けファクタおよび／または道路セグメント頂点重み付けファクタは、道路セグメントデータを前処理する間に使用されたものと、同一である。それは、正確な最適ルートが決定できるようにするためである。
【００４１】
最適ルートを決定するステップは、ＤｉｊｋｓｔｒａのアルゴリズムまたはＡ＊アルゴリズム、あるいは、グラフ理論で知られる任意の他の最適経路アルゴリズムを使用して実行され得る。こうして、最適ルートの効率的な決定が可能になる。Ａ＊アルゴリズムが使用された場合、最適ルートのコストの下限に対する見積もりは、距離ベースのルート探索に対してはエア距離によって、時間ベースのルート探索に対しては特徴的な移動速度でエア距離を除算することによって得られる。
【００４２】
最適ルートを決定する方法は、車両位置データを受信するステップと、その車両位置から目的地への最適ルートを決定するステップとを、さらに包含し得る。この方法に従うと、運転手は、自分の現在地をはっきりと決定できない場合ですら、自分の目的地に行くために、案内され得る。
【００４３】
最適ルートを決定する方法が、道路セグメントを含む道路網の観点から記載されてきたが、この方法は道路網に限定されない。むしろ、上述の局面または実施形態の任意の一つに従う方法は、複数のエッジ部を含む任意のグラフ上で実行され得る。ここで、グラフは道路網として解釈されるべきであり、グラフのエッジ部は、上述の観点からは道路セグメントとして解釈されるべきである。
【００４４】
本発明に従う道路セグメントデータを前処理するシステムは、道路セグメントデータを含む第一のストレージユニットと、タイリング定義データを含む第二のストレージユニットと、該道路セグメントデータのサブセットを格納する作業メモリユニットと、該作業メモリユニットに格納されたデータを処理し、該タイリングに基づいて、道路セグメントのランク情報を決定するのに、適合された処理ユニットとを備える。ここで、該ランク情報は、該タイリングのタイルを結ぶ最適ルートに対する該道路セグメントとの重要度を定量化する。第一および第二のストレージユニットは、個別のデバイスでも、単一のデバイスでもあり得る。タイリング定義データは、数学的関数の形式で提供され得て、これによって、特定の点を含むタイルを決定できる。このシステムは、本発明に従う道路セグメントデータを前処理する方法を実行するように適合されることが好ましい。作業メモリユニットはタイリング定義データのサブセットを、また、格納できるようにも適合されることが、さらに好ましい。このシステムは、タイリングに基づいて、道路セグメントランク情報を決定するように適合される。
【００４５】
道路セグメントデータを前処理するシステムは、処理ユニットに結合され、決定されたランク情報を格納するように適合された追加作業メモリユニットを、さらに備えることが好ましい。追加作業メモリユニットに格納されたランク情報は、ストレージユニットの中に出力されることも、引き続くステップで使用されることもあり得る。追加作業メモリユニットの後者の機能は、ランク情報が再帰的方法に従って決定される場合、特に重要である。この再帰的方法は、短距離移動にのみ重要な道路セグメントから開始し、長距離移動にも妥当性ある道路セグメントまで行う。追加作業メモリユニットは、作業メモリユニットと同一のことも、異なることもあり得る。すなわち、作業メモリユニットと追加作業メモリユニットとは、別個のデバイスでも、単一のデバイスでもあり得る。
【００４６】
処理ユニットは、ランク情報を決定するための追加作業メモリユニットに格納されたデータを処理するように適合され得る。再び、このことは、ランク値を増加に対して、連続的にランク情報が決定される場合、特に重要となる。
【００４７】
作業メモリユニットは、ランク情報を決定するステップの間、最適ルートの決定に必要とされる道路セグメントデータのサブセットを格納するのに、十分なストレージ容量を有することが好ましい。特に、作業メモリユニットは、１つのタイルの道路セグメントデータ、あるいは、道路セグメントのサブセットで適切に選択されたサブセットの道路セグメントデータを格納するのに十分な容量を有することが好ましい。これらの道路セグメントデータは、特徴的なタイリングおよび特徴的な道路セグメント密度のために、少なくとも１つの所定の道路セグメントに対するランク情報を決定するために必要とされる。作業メモリユニットは、そのように設計されると、処理ユニットは、ストレージユニットへのアクセスする頻度がより少なくてすみ、ランク情報に必要とされるランタイムも短縮される。
【００４８】
道路セグメントデータを前処理するシステムは、決定されたランク情報を出力するための出力ユニットをさらに備えることが好ましい。これによって、決定されたランク情報はアクセス可能となり、引き続く最適ルートの決定で、すなわち、ナビゲーションシステムで使用される。出力ユニットは、道路セグメントデータの前処理のために、取り外し可能なストレージ媒体（例えば、ＣＤ−Ｒ／Ｗ）あるいはシステムに組み込まれたストレージ媒体に、ランク情報を出力するように設計され得る。すなわち、システムは、決定されたランク情報を格納するための第三のストレージユニットを包含し得る。このストレージユニットは、こうして、追加ランク情報を決定するための処理ユニットによっても、また、アクセスされるように適合され得る。
【００４９】
道路セグメントデータを前処理するシステムは、並列して、道路セグメントのランク情報を決定するように適合される複数の処理ユニットを備えることが好ましい。道路セグメントのランク情報の計算は、少なくとも所定のタイルに含まれる道路セグメントに対して、ローカルなタスクである。それは、この計算が、このタイルのみの特定の近傍における他の道路セグメントと関連する情報を必要とするという意味からである。このようなランク情報決定の並列化は、ランタイム要求の観点で有効である。さらに、本発明に従う道路セグメントデータを前処理する方法は、並列化によく適合される。様々な並列化スキームがコンピュータクラスタあるいはグリッド（例えば、ピアツーピア（ｐｅｅｒ−ｔｏ−ｐｅｅｒ）またはマスタワーカ（ｍａｓｔｅｒ−ｗｏｒｋｅｒ）スキーム）を使用して、実現され得る。後者の場合において、道路セグメントデータを前処理するシステムは、マスタシステムと、少なくとも１つのワーカシステムとを備える。ここで、このマスタシステムは、タイルにわたって繰り返すこと、および、ワーカシステムに情報を渡すことに適合される。この少なくとも１つのワーカシステムは、マスタシステムによって選択されたタイルに含まれる道路セグメントのランク情報を決定するように適合される。ランク情報が再帰的方法を使用して決定されるべきである場合、マスタシステムは、タイル近傍サイズの増大にわたって、繰り返しを実行するように、さらに適合される。好ましい実施形態において、マスタシステムは、問題を小さなジョブに分解する。これらジョブは、複数のワーカシステムに委託される。特定的には、マスタシステムから少なくともタイル情報を受け取れば、ワーカシステムは、そのタイルの含まれる道路セグメントのランク情報を決定する。その決定は、道路セグメントデータ、および、おそらく、そのタイルのローカルな近傍に含まれる道路セグメントに対して、先行するステップで得られたランク情報データに基づく。マスタシステムおよびワーカシステムは、道路セグメントデータおよびランク情報データの共通のコピーで動作し得るか、あるいは、ワーカシステムは、マスタシステムに結果を戻して、データのローカルコピーを使用し得る。道路セグメントデータを前処理するシステムが、マスタシステムおよび少なくとも１つのワーカシステムを含む実施形態において、前処理は、並列なデータ処理で迅速に行われる。
【００５０】
本発明に従う最適ルートを決定するシステムは、道路セグメントデータを含む第一のストレージユニットと、本発明に従う道路セグメントデータを前処理する方法に従って決定されたランク情報データを含む第二のストレージユニットと、該道路セグメントデータのサブセットを格納する作業メモリユニットと、該作業メモリユニットに結合され、ランク情報データに基づいて、出発点から目的地への最適ルートを決定するように適合された処理ユニットとを備える。第一および第二のストレージユニットは、個別のデバイスでも、単一のデバイスでもあり得る。好ましい実施形態において、道路セグメントデータおよびランク情報は、共通のストレージユニットに格納される。このシステムは、本発明に従う最適ルートの決定方法を実行するように適合されることが好ましい。このようなシステムは、ランク情報に基づいて、最適ルートの決定を効率的に実行するのに適合される。
【００５１】
最適ルートを決定するシステムは、さらに、所望の目的地、および、おそらくルートの出発点を入力する入力手段を備える。この入力手段は、目的地および出発点のデータが作業メモリユニットに格納され得るように、処理ユニットおよび作業メモリユニットに結合される。
【００５２】
好ましい実施形態において、この最適ルートを決定するシステムは、ランク情報データに基づいて、道路セグメントデータまたはランク情報データを、作業メモリユニットに格納されたデータに入れること、あるいは、作業メモリユニットに格納されたデータから取り出すことに適合された追加処理ユニットをさらに備える。追加処理ユニットは、処理ユニットと同一でも、個別のデバイスでもあり得る。追加処理ユニットを提供することで、作業メモリの中に、道路セグメントデータのサブユニットをロード可能となる。このサブセットは、決定されるべき最適ルートと潜在的に関連する道路セグメントを含む。追加処理ユニットは、作業メモリユニットに格納された目的地および出発点の情報へのアクセスすることにも、目的地および出発点の情報に応じて、作業メモリユニットに格納されたデータにデータを入れること、あるいは、作業メモリユニットに格納されたデータからデータを取り出すことにも、さらに適合され得る。処理ユニットおよび追加処理ユニットは、個別のデバイスでも、同一のデバイスでもあり得る。
【００５３】
最適ルートを決定するシステムは、タイリング定義データを含む第三のストレージユニットを備えることが好ましい。タイリング定義データは、道路セグメントに対する属性としても、また、格納され得る。この属性は、道路セグメントが属するタイルを特定する。第三のストレージユニットは、処理ユニットまたは追加処理ユニットによってアクセス可能である。追加処理ユニットは、ランク情報およびタイリング定義データの双方に応じて、作業メモリユニットに格納されたデータにデータを入れること、あるいは、そこからデータを取り出すことのそれぞれに適合されることが好ましい。これによって、最適ルート探索が実行されるべき道路セグメントのサブセットが、タイリングおよびランク情報データの双方に基づいて、選択されることが可能となる。第一、第二および第三のストレージユニットは、全てが個別のデバイスであることも、そのうちの２つのストレージユニットが単一のデバイスであることも、あるいは、これらストレージユニットの全てが単一のデバイスであることもあり得る。規則的なタイリングあるいは規則的なタイリングの階層を有する有用な実施形態において、タイリング定義データは、再び、数学的関数の形式で提供され得て、その座標に基づいて、特定の点を含むタイルを決定できる。
【００５４】
好ましい実施形態において、前記作業メモリユニットは、最適ルート探索に（少なくとも特徴的なタイルサイズと道路セグメント密度に）必要とされる道路セグメントデータのサブセットを格納するのに、十分なストレージ容量を有する。次いで、最適ルートは、作業メモリユニットにのみアクセスしている処理ユニットを用いて決定され得るので、ランタイムを短縮できる。
【００５５】
本発明に従うナビゲーションシステムは、本発明に従う最適ルート決定システムを備える。このナビゲーションシステムは、さらに、入出力ユニット、ディスプレイ、ラウドスピーカなどのような従来式ナビゲーションシステムから知られている全てのコンポーネントをさらに備え得る。特に、ナビゲーションシステムは、この最適ルートを決定するシステムに、車両位置情報を提供するように適合された位置決定手段を備え得る。これによって、運転手が出発点情報をわざわざ提供することなく、現在の車両位置から目的地への最適ルートの決定が可能となる。
【００５６】
「道路セグメント」という用語は、本明細書全体を通して使用されるが、道路セグメントとして記された対象は、必ずしも物理的な道路である必要はなく、例えば、河川や湖水を行き交うフェリーが通過するルートでもあり得ることに留意すべきである。
【００５７】
さらに、道路セグメントは、最適ルート探索が関心事となり得るネットワークを構成する任意の他の種類の対象に対応し得る。その例には、コンピュータネットワークにおけるデータ接続または電力送信線を含む。本発明は、道路網における最適ルートの意味で記載されているが、このようなアプリケーションの全ても、また包含されることも理解されるべきである。
【００５８】
また、「最適ルート」という用語は全体を通して使用されるが、本発明の様々な実施形態に従う方法およびシステムは、数学的意味で最適でないが、ほぼ最適なルートである有利なルートを決定するためにも、また適合されることに留意すべきである。このような変種の全ても、また、本発明によって企図される。しかしながら、本発明の好ましい実施形態に従うと、道路セグメントデータを前処理する方法およびシステムと、これに対応して最適ルートを決定する方法およびシステムとが提供され、正しい最適ルートを決定することが可能となる。これら好ましい実施形態に従うと、最適ルートの決定における複雑さは、例えば、車両に搭載されるナビゲーションシステムで実行され得る程度になる。
【００５９】
本発明のアプリケーションの主たる分野は、道路網における最適ルートの決定である。
【００６０】
本発明はさらに、以下の手段を提供する。
【００６１】
（項目１）
最適ルート決定用の道路セグメントデータを前処理する方法であって、
該道路セグメントデータを提供するステップと、
該道路セグメントが含まれるエリアをカバーするタイリングを定義するステップと、
道路セグメントに対するランク情報を決定するステップで、該ランク情報は該タイリングのタイルを結ぶ最適ルート用の該道路セグメントの妥当性を定量化する、ステップと
を包含する、道路セグメントデータを前処理する方法。
【００６２】
（項目２）
上記ランク情報は、上記タイリングに依存して決定され、タイル端部に位置する点を結ぶ最適ルート用の道路セグメントの妥当性を定量化すること
を特徴とする、項目１に記載の道路セグメントデータを前処理する方法。
【００６３】
（項目３）
上記道路セグメントの各道路セグメントは、上記タイリングの多くても１つのタイルに含まれるように、上記タイリングが定義されるか、または、上記道路セグメントが再定義されること、および、上記ランク情報が、該タイリングに依存して決定されること
を特徴とする、項目１または項目２に記載の道路セグメントデータを前処理する方法。
【００６４】
（項目４）
上記道路セグメントに対するランク情報を決定するステップは、
該道路セグメントを含むタイルを決定するステップと、
該道路セグメントを含む該タイルから、少なくとも所定のタイル距離を有する第一のタイルを選択するステップと、
該道路セグメントが、該第一のタイルに位置する出発道路セグメントを有する最適ルートに含まれるかどうかを決定するステップと
を包含することを特徴とする、項目３に記載の道路セグメントデータを前処理する方法。
【００６５】
（項目５）
上記出発道路セグメントの頂点は、上記第一のタイルの端部に位置すること
を特徴とする、項目４に記載の道路セグメントデータを前処理する方法。
【００６６】
（項目６）
上記ランク情報を決定するステップは、
上記道路セグメントを含む上記タイルから、少なくとも上記所定のタイル距離を有する第二のタイルを選択するステップであって、上記最適ルートの目的地道路セグメントは該第二のタイルに位置する、ステップ
をさらに包含する
ことを特徴とする、項目４または項目５に記載の道路セグメントデータを前処理する方法。
【００６７】
（項目７）
上記目的地道路セグメントの頂点は、上記第二のタイルの端部に位置すること
を特徴とする、項目６に記載の道路セグメントデータを前処理する方法。
【００６８】
（項目８）
上記ランク情報を決定するステップは、
上記道路セグメントが最適ルートに含まれるように、上記所定のタイル距離の最大を決定するステップをさらに包含すること
を特徴とする、項目４〜項目７のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００６９】
（項目９）
上記ランク情報を決定するステップは、上記所定のタイル距離の値を増やして、再帰的に実行されること
を特徴とする、項目４〜項目８のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７０】
（項目１０）
上記所定のタイル距離の所定の値に対して、最適ルート探索は、該所定のタイル距離のより小さな値に対して得られた結果に基づいて、選択された道路セグメントのサブセット上で実行されること
を特徴とする、項目４〜項目９のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７１】
（項目１１）
道路セグメント重み付けファクタを提供するステップを特徴とし、
上記ランク情報を決定するステップは、該重み付けファクタにさらに基づくことと
項目１〜項目１０のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７２】
（項目１２）
上記ランク情報を決定するステップは、上記道路セグメントの各道路セグメントに対して、実行されること
を特徴とする、項目１〜項目１１のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７３】
（項目１３）
上記タイリングのタイルは、長方形の形状であること
を特徴とする、項目１〜項目１２のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７４】
（項目１４）
２つのタイル間のタイル距離は、該２つのタイルを結ぶ経路を通過するタイル端部またはタイル頂点の最小数として定義されること
を特徴とする、項目１〜項目１３のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７５】
（項目１５）
１つのタイルに含まれる道路セグメントシーケンスを新たな道路セグメントに、相互結合するステップ
を特徴とする、項目１〜項目１４のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７６】
（項目１６）
所定の道路セグメントのランク情報が決定された後、上記タイリングを粗調整するステップ
を特徴とする、項目１〜項目１５のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７７】
（項目１７）
上記決定されたランク情報を出力するステップ
を特徴とする、項目１〜項目１６のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７８】
（項目１８）
上記道路網は任意のグラフであり、各道路セグメントは該グラフのエッジ部であること
を特徴とする、項目１〜項目１７のいずれか１項に記載の道路セグメントデータを前処理する方法。
【００７９】
（項目１９）
道路セグメントデータを提供するステップと、
項目１〜項目１８のいずれか１項に記載の方法に従って決定されたランク情報データを提供するステップと、
該道路セグメントデータおよび該ランク情報データに基づいて、出発点から目的地への最適ルートを決定するステップと
を包含する、出発点から目的地への最適ルートを決定する方法。
【００８０】
（項目２０）
上記ランク情報に基づいて、道路セグメントのサブセットを選択するステップ
を特徴とし、
上記最適ルートを決定するステップは、該道路セグメントのサブセットに基づいて実行される、項目１９に記載の最適ルートを決定する方法。
【００８１】
（項目２１）
上記道路セグメントが含まれるエリアをカバーするタイリングを定義するステップ
を特徴とする、項目１９または項目２０に記載の最適ルートを決定する方法。
【００８２】
（項目２２）
上記道路セグメントの各道路セグメントは、上記タイリングの多くても１つのタイルの中にしか含まれないように、上記タイリングが定義されるか、または、該道路セグメントが再定義されること
を特徴とする、項目１９または項目２１に記載の最適ルートを決定する方法。
【００８３】
（項目２３）
上記道路セグメントのサブセットを選択するステップは、
上記出発点を含む出発タイルを決定するステップと、
上記目的地を含む目的地タイルを決定するステップと、
道路セグメントを、道路セグメントランク情報、および、該道路セグメントを含むタイルの該出発タイルまたは目的地タイルからのタイル距離に基づいて、上記道路セグメントのサブセットに含めるステップと
を包含することを特徴とする、項目２０に従属した項目２１または項目２２およびに記載の最適ルートを決定する方法。
【００８４】
（項目２４）
上記道路セグメントのサブセットを選択するステップは、
上記出発点を含む出発タイルから、上記目的地を含む目的地タイルまでの出発−目的地タイル距離を決定するステップと、
該出発−目的地タイル距離に基づいて最小ランク値を選択するステップと、
該最小ランク値以上のランク値を有する全ての道路セグメントを、該道路セグメントのサブセットに含めるステップと
を包含することを特徴とする、項目２０に従属した項目２１〜項目２３のいずれか１項に記載の最適ルートを決定する方法。
【００８５】
（項目２５）
道路セグメント重み付けファクタを提供するステップを特徴とし、
上記最適ルートを決定するステップは、該重み付けファクタに、さらに基づく、項目１９〜項目２４のいずれか１項に記載の最適ルートを決定する方法。
【００８６】
（項目２６）
車両位置データを受信するステップと、
車両位置から上記目的地への最適ルートを決定するステップと
を特徴とする、項目１９〜項目２５のいずれか１項に記載の最適ルートを決定する方法。
【００８７】
（項目２７）
上記道路網は任意のグラフであり、各道路セグメントは該グラフのエッジ部であること
を特徴とする、項目１９〜項目２５のいずれか１項に記載の最適ルートを決定する方法
（項目２８）
道路セグメントデータを含む第一のストレージユニット（１０）と、
タイリング定義データを含む第二のストレージユニット（２０）と、
該道路セグメントデータのサブセットおよび該タイリング定義データのサブセットを格納する作業メモリユニット（５０）と、
該作業メモリユニット（５０）に格納されたデータを処理し、該タイリングに基づいて、道路セグメントのランク情報を決定するように適合された処理ユニット（４０）と
を備え、
該ランク情報は、該タイリングのタイルを結ぶ最適ルートに対する該道路セグメントとの妥当性を定量化する、道路セグメントデータを前処理するシステム。
【００８８】
（項目２９）
上記システムは、項目１〜項目１８のいずれか１項に記載の道路セグメントデータを前処理する方法を実行するように適合されることを特徴とする、項目２８に記載の道路セグメントデータを前処理するシステム。
【００８９】
（項目３０）
上記処理ユニット（４０）に結合され、決定されたランク情報を格納するように適合された追加作業メモリユニット（６０）
を特徴とする、項目２８または項目２９に記載の道路セグメントデータを前処理するシステム。
【００９０】
（項目３１）
上記処理ユニット（４０）は、上記ランク情報を決定するための上記追加作業メモリユニット（６０）に格納されたデータを処理するように適合されること
を特徴とする、項目３０に記載の道路セグメントデータを前処理するシステム。
【００９１】
（項目３２）
上記作業メモリユニット（５０）は、上記ランク情報を決定するための最適ルート探索に必要とされる道路セグメントデータのサブセットを格納するのに十分なストレージ容量を有すること
を特徴とする、項目２８〜項目３１のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【００９２】
（項目３３）
決定されたランク情報を出力するための出力ユニット（７０）
を特徴とする、項目２８〜項目３２のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【００９３】
（項目３４）
決定されたランク情報を格納するための第三のストレージユニット（３０）
を特徴とする、項目２８〜項目３３のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【００９４】
（項目３５）
上記システムは、上記タイリングに基づく道路セグメントのランク情報を決定するのに適合された少なくとも１つの追加処理ユニットを備え、
上記処理ユニット（４０）および該追加処理ユニットは、並行して、道路セグメントランク情報を決定するように適合されていること
を特徴とする、項目２８〜項目３４のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【００９５】
（項目３６）
道路セグメントデータを含む第一のストレージユニット（４３０）と、
ランク情報データを含む第二のストレージユニット（４３０）と、
該道路セグメントデータのサブセットを格納する作業メモリユニット（４６０）と、
該作業メモリユニット（４６０）に結合され、ランク情報データに基づいて、出発点から目的地への最適ルートを決定するように適合された処理ユニット（４５０）と
を備え、
該ランク情報データは、項目１〜項目１８のいずれか１項に記載の道路セグメントデータを前処理する方法に従って決定されることを特徴とする、最適ルート決定システム。
【００９６】
（項目３７）
上記ランク情報データに基づいて、道路セグメントデータまたはランク情報データを、上記作業メモリユニット（４６０）に格納されたデータに入れること、あるいは、該作業メモリユニット（４６０）に格納されたデータから取り出すように適合された追加処理ユニット（４５０）
を特徴とする、項目３６に記載の最適ルート決定システム。
【００９７】
（項目３８）
タイリング定義データを含む第三のストレージユニット（４４０）
を特徴とする、項目３６または項目３７に記載の最適ルート決定システム。
【００９８】
（項目３９）
上記作業メモリユニット（４５０）は、最適ルート決定に必要とされる上記道路セグメントデータのサブセットを格納するのに、十分なストレージ容量を有すること
を特徴とする、項目３６〜項目３８のいずれか１項に記載の最適ルート決定システム。
【００９９】
（項目４０）
上記システムは、項目１９〜項目２７のいずれか１項に記載の最適ルートを決定する方法を実行するように適合されていること
を特徴とする、項目３６〜項目３９のいずれか１項に記載の最適ルート決定システム。
【０１００】
（項目４１）
項目３６〜項目４０のいずれか１項に記載の最適ルート決定システム（４２０）
を特徴とする、ナビゲーションシステム。
【０１０１】
（項目４２）
上記最適ルート決定システム（４２０）に車両位置データを提供するように適合された位置決定手段（４１２）
を特徴とする、項目４１に記載のナビゲーションシステム。
【発明の効果】
【０１０２】
本発明により、地図上の相対位置に基づいて決定される道路セグメント属性に基づく最適ルート決定方法が提供され得、このような道路セグメント属性が、たとえ大きな道路網であっても効率的に決定され得る最適ルートの決定方法が提供され得る。
【発明を実施するための最良の形態】
【０１０３】
本発明の付加的な特徴と利点は、添付図面を参考して、好ましい実施形態または有利な実施形態の以下の詳細に関する記述から、より容易に理解される。
【０１０４】
図１を参照しながら、本発明の実施形態に従う道路セグメントデータを前処理するシステム１は、記載される。このシステムは、道路セグメントのセットにある各道路セグメントに対して、長距離移動用に道路セグメントの妥当性を定量化するランク情報を決定することに、より特定的には、計算することに適合される。より特定的には、本実施形態に従うと、道路セグメントが含まれるエリアに対して、タイリングが提供される。ここで、ランク情報は、そのタイリングの異なるタイルを結ぶ最適ルート用の道路セグメントの妥当性を定量化する。
【０１０５】
システム１は、道路セグメントデータを格納する第一のストレージユニット１０、タイリング定義データを格納する第二のストレージユニット２０、および、決定されたランク情報を格納する第三のストレージユニット３０を備える。第一、第二および第三のストレージユニットは、図１に示すように異なる物理的エンティティであり得るが、ＣＤ−ＲＯＭまたはＣＤ−Ｒ／Ｗ、あるいは、コンピュータのハードドライブのような１つの物理的ストレージユニットに結合され得る。
【０１０６】
第一のストレージユニット１０に格納された道路セグメントデータは、道路網を構成する道路セグメントを関連付ける情報を含む。典型的には、道路セグメントに対し、これらデータは、出発点と終点の地理的位置のような道路セグメントの位置および方向と関連する地理的情報と、道路セグメントの長さ、道路セグメントでの特徴的な移動速度、および／または、道路セグメントを通過するのに要する特徴的な移動時間を定量化する追加情報とを備える。より一般的には、重み付けファクタが、道路セグメントの後者の特徴の一つに対応する道路セグメントに対して、提供され得る。以下に、重み付けファクタは、道路セグメントの重み付けファクタとして記載されるが、これら重み付けファクタは、道路セグメントまたは道路セグメント頂点のいずれかと関連し得ることは理解されるべきである。さらに、重み付けファクタは、道路セグメント（すなわち、グラフの端）および道路セグメント頂点（すなわち、グラフのノード）の双方に提供され得る。単純化するために、重み付けファクタを、道路セグメントおよび／または道路セグメント頂点と関連付けるこれら全ての可能性は、本明細書にて、以下、まとめて、道路セグメントの重み付けファクタとして、言及される。また、道路セグメントデータは、道路セグメントに関して、さらに追加情報を含み得る。しばしば、道路セグメントデータは、第一のメモリユニット１０の中に格納されたデータセット１１〜１３によって模式的に示されるように、データアレイの形式で格納される。
【０１０７】
第二のメモリユニット２０に格納されたタイリング定義データは、どのランク情報が計算されるべきは基づいて、タイリングの全てのタイルを決定する。データは、１つまたは幾つかのタイル角の座標を特定する数字多重項の形式で、提供され得る。例えば、長方形のタイルからなるタイリングに対し、左上角および右下角の座標が提供され得る。タイリング定義データは、アレイ２１〜２３の形式で格納され得る。ここで、各アレイが、タイリングの１つのタイルに対応する。しかしながら、タイリング定義データは、任意の他の適切な方法でも提供され得る。例えば、人がタイル頂点およびタイル端部を決定することを可能にするアルゴリズムの形式で提供され得る。
【０１０８】
第三のメモリユニット３０は、ランク情報計算の結果を格納するために、提供される。
【０１０９】
道路セグメントデータを前処理するシステムは、さらに処理ユニット４０、作業メモリユニット５０、追加作業メモリユニット６０、および、出力ユニット７０を備える。処理ユニット４０は、ストレージユニット１０、２０または３０の１つに格納されるデータを作業メモリユニット５０に入れること、作業メモリユニット５０に格納されたデータをそこから取り出すこと、および、作業メモリユニット５０に格納されたデータを処理することに適合される。作業メモリユニット５０に格納されたデータは、第一のストレージユニットからの道路セグメントデータのサブセットを含む。計算されたランク情報は、出力ユニット７０を介して出力され得るか、あるいは、引き続く使用のために追加作業メモリユニット６０に格納され得る。作業メモリユニット５０および追加作業メモリユニット６０は、単一のデバイスでも、異なるデバイスでもあり得る。
【０１１０】
以下の記述から明らかになり、以下に詳細に記載されるように、本発明に従う道路セグメントを前処理する方法は、コンピュータネットワーク上あるいはクラスタ上で実行されるように適合される。道路セグメントデータを前処理する方法の並列化に対する様々なインプリメンテーションは、例えば、ピアツーピアまたはマスタワーカのスキームを使用して実現可能である。後者の場合、例えば、マスタコンピュータおよび複数のワーカコンピュータの各コンピュータは、少なくとも、処理ユニットおよび作業メモリユニットを備える。さらに、コンピュータは、共通のストレージユニットを分かち合い得るし、あるいは、個々のストレージユニットを備え得る。
【０１１１】
次いで、図１に示すシステム１によって実行される道路セグメントデータを前処理する方法が、説明される。道路セグメントデータの前処理は、その道路セグメントが含まれるエリアをカバーするタイリングに基づく。図２に模式的に示すタイリング８０は、タイル９０〜９２を含む複数のタイルを備える。最適ルートが計算されるべき道路網は、複数の道路を含む。道路は、実線と破線とで示される。道路は、例えば、許容移動速度の観点から、異なるタイプであり得て、道路は、重み付けファクタによって定量化され得る。図２に示す道路網は、２つの異なるタイプの道路を備える。一方は、第一の特徴的な移動速度（図２の実線で表示）で、例えば、道路セグメント９３であり、他方は、第二の特徴的な移動速度（図２の破線で表示）で、例えば、道路セグメント９４である。道路セグメントの終点、あるいは、道路セグメントのジャンクションまたは交差点は、道路網の頂点（図２の黒丸で表示）を定義し、例えば、点９５である。
【０１１２】
典型的には、道路セグメントおよび道路セグメント頂点の密度は、空間によって異なり、都会エリアで高い。タイリングは、道路セグメントまたは道路セグメント頂点の密度が高いエリア９６および９７において、道路セグメントまたは道路セグメント頂点の密度が低いエリアより、タイルサイズが小さくなるように選択される。タイリング全体を通して、１タイル当たりの道路セグメントまたは道路セグメント頂点の数が大きくばらつかないようにするためである。しかしながら、以下で議論する好ましい実施形態の多くでは、同じサイズからなる小さな正方形を有するタイリングで開始することも可能である。
【０１１３】
道路セグメントデータの前処理にあたって、タイリングは、各道路セグメントが、タイリングの１つのタイルのみに含まれるように、あるいは、より正確には、各道路セグメントが、その頂点を例外として、１つのタイルの内側に位置するように選ばれる。これは、道路セグメントがタイル端部と交わる全ての点に追加の頂点を導入することで、もっとも容易に達成される。例えば、図２の点９８（白丸で表示）である。このような追加頂点を導入することで、道路セグメントは、幾つかの新たな道路セグメントに分裂する。各道路セグメントが１つのタイルのみに含まれるようにタイリングを選択するには、上記に説明されたように、道路セグメントを再定義されるべきことが必要とされ得るのは、理解されるべきである。以下においては、道路セグメントデータおよびタイリング定義データは、既に、各道路セグメントは１つのタイルのみに含まれる形式であると仮定される。このようにならない場合は、第一のステップで、道路セグメントデータを前処理するシステム１は、追加頂点を導入し、新たな道路セグメントに重み付けファクタを計算して、道路セグメントを再定義する。再定義された道路セグメントデータは、システム１の第一のストレージユニットまたは作業メモリユニットの１つに格納され得る。
【０１１４】
図３〜図９を参照して、以下に示されるように、提供され、タイリングの定義に基づく道路セグメントデータから、システム１は、道路セグメントのそれぞれに対するランク情報を計算する。図３Ａは、道路セグメントデータを前処理する方法の間のシステム１によって実行される基本ステップを示す模式的な流れ図１００を示す。第一のステップにおいて、未知のランクを有する道路セグメントｖが、ステップ１０１で選択される。ステップ１１０で、以下に詳細に示されるように、道路セグメントｖに対するランク情報は計算され、ステップ１２０で、出力ユニット７０を介して出力されるか、あるいは、第三のストレージユニット３０または追加作業メモリユニット６０に格納される。ランク情報が未知の道路セグメントがまだあるかどうかが、ステップ１３０で判断され、上述のステップは、未知のランク情報を有する異なる道路セグメントに対して、繰り返されるか、あるいは、ステップ１４０で終了する。
【０１１５】
プロセス１００の中心部分は、所定の道路セグメントｖに対するランク情報を決定するステップ１１０であり、さらなる詳細が、図３Ｂおよび図３Ｃを参照して記述される。図３Ｂは、ランク情報を決定するステップ１１０で実行されたプロセスの模式的な流れ図である。まず、ｖを含むタイルＴが、ステップ１１１で決定される。引き続き、タイル距離の最大が決定される。そのタイル距離の最大は、道路セグメントｖが、相変わらず、タイルＴからこのタイル距離を有するタイルを含む出発道路セグメントと、タイルＴからこのタイル距離を有するタイルを含む目的地道路セグメントとを結ぶ最適ルートに、含まれる。タイル距離のこの最大は、道路セグメントのランク値となるように定義される。ランク情報は、ランク値と等しいことも、以下に詳細に説明されるように、ランク値に基づいて決定されることもある。この最大値を決定することは、ステップ１１２で定義される初期値からタイル距離を１つずつ増やすことによって達成される。引き続き、ステップ１１３で、まだｖが最適経路に含まれているかどうかを判断する。そして、ステップ１１３の結果によって、ステップ１１４で、タイル距離を増やすか、あるいは、ランク情報がタイル距離の最大と等しくなるように、すなわち、そのランク値と等しくなるように設定する。そのタイル距離の最大は、道路セグメントｖが、依然として、タイルＴからこのタイル距離を有するタイルを含む出発道路セグメントと、タイルＴからこのタイル距離を有するタイルを含む目的地道路セグメントとを結ぶ最適ルートに含まれる。すなわち、ステップ１１５においては、ランク値と等しい。
【０１１６】
タイル距離は、様々な方法で定義され得るが、本発明の実施形態に従うと、２つのタイル間の距離は、２つのタイルを結ぶ経路を通過するタイル端部またはタイル角の最小数として定義されるか、あるいは、別に言うと、２つのタイルの一方に、その２つのタイルの他方から到達するのに必要とされる隣り合うタイル間で、横、縦または対角線に飛び越えの最小数として定義される。図７はタイリング３００について、模式的に示している。直前に記載されたように定義されたタイル距離を用い、数字は中心タイルＴからタイルそれぞれへのタイル距離を示す。
【０１１７】
図３Ｂに戻ると、タイルＴに含まれる道路セグメントｖが、出発道路セグメントから目的地道路セグメントへの最適ルートに含まれるかどうかを決定するステップ１１３は、タイルＴから少なくともタイル距離ｄを有するタイルの中に位置する出発道路セグメントおよび目的地道路セグメントを用いて、全ての最適ルートを決定することによって実行され得る。この全ての最適ルートは、タイルＴからタイル距離ｄを有する任意のタイルに位置する任意の出発道路セグメントの頂点と、タイルＴからタイル距離ｄを有する任意のタイルに位置する任意の目的地道路セグメントの頂点とを結ぶ。しかしながら、図８から分かるように、このような可能性のある出発点と目的地のサブセットのみを考慮すれば、十分である。
【０１１８】
図８は、模式的に道路網およびタイリング３１０を示す。道路セグメントｖａのランク値が決定されるべきものと仮定すると、第一ステップで、出発道路セグメントと目的地道路セグメントとを結ぶ最適ルートがあるかどうかが決定されるべきである。各道路セグメントはタイル３１１からタイル距離１を有するタイルの中に位置し、最適ルートは道路セグメントｖａを含む。原則的に、それゆえ、点３１２〜点３１８から選択された出発点と目的地との任意のペアを結ぶ全ての最適ルートを計算することが必要である。しかしながら、タイル３１１からのタイル距離が１に等しいタイル内に位置する出発道路セグメントおよび目的地道路セグメントを有する任意の最適ルートは、必然的にタイル３１１の端部と交差するので、また、各道路セグメントは１つのタイル内にのみあるので、それぞれタイル３１１の端部にある出発点および目的地を結ぶ最適ルートを計算すれば、十分である。この場合において、最適ルート探索には、考慮されるべく残された点のみが考慮される。それらの点は、それゆえ、点３１２および点３１３である。
【０１１９】
同様の議論は、タイル距離の値がさらに大きい場合でも、依然として有効である。特に、タイルＴからのタイル距離ｄを有するタイル内にある出発道路セグメントおよび目的地道路セグメントを相互に結ぶ全ての最適ルートを決定する代わりに、タイルＴからのタイル距離がｄ未満である全てのタイルの境界に位置する出発点および目的地に対して、最適経路を計算すれば十分である。以下において、タイルＴのｄ境界は、Ｂ（ｄ，Ｔ）と称される。
【０１２０】
それゆえ、ステップ１１３は、図３Ｃによって示される以下の方法に従って、実行され得る。タイルＴのｄ境界に位置する出発点および目的地は、それぞれ、ステップ１１３０および１１３１で選択され、これら２つの点を結ぶ最適ルートは、ステップ１１３２で計算される。ステップ１１３２における計算は、ＤｉｊｋｓｔｒａアルゴリズムまたはＡ＊アルゴリズムのような標準的方法を使用して実行され得る。後者の場合には、最適ルートのコスト見積もりは、距離ベースの最適ルート探索に対しては、エア距離から、時間ベースの最適ルート探索に対しては、エア距離を特徴的な移動速度で除算して、それぞれ求められ得る。ｖが計算された最適ルートを含んでいる場合は、プロセス１１３は、ステップ１１３４で「はい」を出力する。含んでいない場合は、そのプロセスは、ステップ１１３５および１１３６で、全ての可能な出発点および目的地のペアに対して繰り返される。それは、ステップ１１３７および１１３８で、Ｔのｄ境界上の異なる目的地および出発点を選択することによってである。ｖがこのような最適ルートのいずれにも含まれていない場合は、ステップ１１３は、ステップ１１３９で「いいえ」を出力する。
【０１２１】
「最適」とは、距離、移動時間、トンネルまたはフェリーを避けるこれら２つのいずれか、あるいは、ユーザが関心を示し得る任意の他のルーティングオプションの観点からの最適を意味し得る。最適ルートは、選択されたルーティングオプションによって異なる。技術的に、選択されたモードに依存する異なる道路セグメントの重み付けファクタによって、通常は、異なるモードが採用される。
【０１２２】
図３Ａ〜図３Ｃに示す流れ図を組み合わせることで、全ての道路セグメントに対するランク情報を計算する完全なプロセスが得られる。しかしながら、真のランク値ｒを知る必要が必ずしもないことには留意すべきである。むしろ、ランク値が特定の閾値未満である場合のみ、正確なランク値が分かれば十分であり得る。所定の最大ランクは、特徴的な値によって与えられ得る。この特徴的な値に対して、それを超えるランクを有する道路セグメントの数は、十分に少ないので、そのような全ての道路セグメントは、例えば、カーナビゲーションシステムのような作業メモリユニットに容易に格納され得る。次いで、ランク情報の計算は、図４に示すプロセス２１０によって、特定値で終了し得る。これは、図３Ａのプロセス１１０に置換して適合される。プロセス１１０によって実行されたステップに加え、ステップ２１３で、最適ルートが計算されるべきｄの値が、既に所定の最大ランクを超えているかどうかが決定される。道路セグメントに対するランク情報は、次いで、ランク値が所定の最大ランク以下の場合、そのランク値と等しくなり、そうでない場合、所定の最大ランクに等しくなる。
【０１２３】
次に、ランク情報を計算する方法の変種が記載される。この変種は、ランク値のより効率的な決定を可能とする。上述の方法と比較すると、主たる違いは、第一のステップにおいて、少なくとも１のランク値を有する全ての道路セグメントが、決定される。次いで、第二のステップにおいて、少なくとも２のランク値を有する全ての道路セグメントが、決定されるなどである。すなわち、ランク情報は、ランク値を増やして、連続的に計算される。道路セグメントｖが最適ルートに含まれるかどうかを決定する中心ステップは、図３Ｃに示すように、上述の方法と同様のままである。しかしながら、ランク値の計算が、ランク値を増やしながら連続的に実行されるので、出発点と目的地が選択された後に、１１３２で最適ルートを計算するステップは、先行するステップで得られた結果に基づき得る。これは、ランク値の計算を非常に単純化する。これは、次に、図９Ａおよび図９Ｂを参照しながら記載される。
【０１２４】
図９Ａは、タイリング３２０を示す。少なくとも２のランク値を有するタイルＴ内の道路セグメントが決定されるべきであると、仮定する。上述のように、タイルＴの２境界（太い実線３２１で表示）上に位置する出発点および目的地を結ぶ全ての最適ルートは、計算されるべきである。ランク情報を計算する変種の方法に従うと、先行するステップで、少なくとも１のランク値を有する全ての道路セグメントは、全てのタイルに対し、決定されていることに留意すべきである。それゆえ、少なくとも２のランク値を有するＴ内の全ての道路セグメントを決定するステップは、少なくとも１のランク値を有するような全ての道路セグメントに制限され得る。さらに、タイルＴの２境界に位置する出発点と目的地とを結ぶ任意の最適経路は、タイルＴから１に等しいタイル距離を有するタイルを通過する。ステップ１１３２における最適ルート探索は、それゆえ、少なくとも１のランク値を有するタイルで、Ｔから１に等しいタイル距離を有するタイルを含むこれら道路セグメントに制限され得る。これは、タイルＴから１に等しい距離を有するタイルに数字によって、模式的に図９Ａで示される。最適ルート探索のために考慮すべき道路セグメントの数を減らすことによって、計算の複雑さを減らし、ランタイムも短縮し得る。
【０１２５】
同様の議論はｄ値がより大きな場合に対しても、図９Ｂに模式的における格子３３０で示すように、依然有効である。少なくとも３のランク値を有するタイルＴ内の道路セグメントが決定されるべきであると、仮定する。ステップ１１３２における最適ルート探索は、タイルＴから２に等しいタイル距離を有するタイルに対して、少なくとも１のランク値を有する道路セグメントと、タイルＴから１に等しいタイル距離を有するタイルに対して、少なくとも２のランク値を有する道路セグメントとに制限され得る。これらの道路セグメントは、先行するステップで、既に決定されていることに留意すべきである。それゆえ、計算の複雑さは、ランク値を再帰的に計算することで、減少され得る。
【０１２６】
より一般的には、タイルＸに含まれる出発点と、タイルＹに含まれる目的地とを結ぶ最適ルートが決定されるべきであれば、タイルＺにおいて、タイルＺとＸとの間のタイル距離と、タイルＺとＹとの間のタイル距離とのいずれか小さなタイル距離以上のランク値を有する道路セグメントのみを考慮される必要がある。それゆえ、増加するランク値に対して、最適ルート探索が実行されるべき道路セグメントのセットは、全てのタイルに対して、先行するステップで得られた結果に基づいて、減少され得る。
【０１２７】
図５の流れ図によって、模式的に示されるランク情報を計算する第二の代替的方法に従うと、少なくともｄの値のランク値を有するタイルＴに含まれる全ての道路セグメントを同時に決定することで、最適ルートの計算回数を最小にして、ランタイムをさらに減らし得る。これは、タイルＴのｄ境界上に位置する出発点および目的地を結ぶ全ての最適ルートを計算し、次いで、ステップ２２６に示すように、この最適ルートに含まれるタイルＴ内の全ての道路セグメントを同時に決定することにより、上記のランク情報計算の代替方法を変更することによって達成される。これら全ての道路セグメントのランク情報は、更新されて、ｄになる。このステップは、ステップ２２７〜２３０で示すように、出発点と目的地との全ての可能な組み合わせに対して、繰り返される。ランク情報を計算する代替方法で上述したように、重要なのは、ステップ２２５での最適ルート探索が、道路セグメントのサブセットに基づいていることである。このサブセットは、より低いランク値に対して先行するステップで得られた結果に基づき選択されたものである。
【０１２８】
図６に示すランク情報を計算する第三の代替的方法に従うと、ランク情報の計算は、タイルサイズを増やすことによって、さらに合理化され得る。すなわち、それは、決定されるべきランク値が増加する間にタイルを再定義することによってであり、同時に道路網、つまり、より技術的には最適ルート探索が実行されるべきグラフを再定義することによってである。この方法２５０に従うと、まず、ステップ２５１で、タイリングが定義される。ステップ２５２で、補助道路セグメント頂点が道路セグメントとタイル端部との交点で導入される。道路網またはグラフが空でない間、１、２および３以上のランク値を有する道路セグメントが、ステップ２５４〜２５８で計算される。一つの実施形態において、ステップ２５５は、図５のステップ２２３〜２３０を備える。重要なことは、これらステップで要求される任意の最適ルートの計算は、より小さなランク値に対して先行して得られた結果に、再び、基づき得ることである。少なくともｋのランク値を有するタイルＴの道路セグメントは、Ｇ（ｋ，Ｔ）で記される。完全なタイリングのこのような道路セグメント全てのセットのユニオン（ｕｎｉｏｎ）は、Ｇ（ｋ）で記される。Ｇ（ｋ，Ｔ）は、Ｔの（ｋ−１）境界上にある出発点および目的地を有する最適ルートで生じるＴ内の全ての道路セグメントのセットであることに留意すべきである。ステップ２５９で、道路網は、先行するループにおいて少なくとも３のランク値を有するように決定された全ての道路セグメントのセットとして再定義される。道路セグメントの数は、以下に詳細に述べられるように、ステップ２６０で、ショートカットを導入することで減少される。ステップ２６２で、タイル端部の長さを２倍にした後、上記のステップは、新たな道路網またはグラフＧおよび新たなタイリングに基づいて、繰り返される。
【０１２９】
第三の代替方法に従うと、初期の端部長さがｓ１（例えば、ｓ１＝１０００ｍ）の小さな正方形タイルから開始するランク情報を計算することが可能である。この方法で割り当てられたランク情報は、格子が中間ステップで再定義されるので、以前の方法のランク情報とは幾分か異なることに留意すべきである。例えば、タイル端部長さがｓ２＝２×ｓ１で再定義されたタイリングと、これに対応する再定義された道路網のために、１に等しいランク値を有するように決定された道路セグメントに対して、ランク情報は４に等しいと設定される。このランク情報は、元々のタイリングに対するランク値に直接変換しない（ｔｒａｎｓｌａｔｅ）「擬似ランク」であることに留意すべきである。むしろ、本方法の４というランク情報は、再定義された道路網において、少なくとも１のランク値を有する道路セグメントを元々のタイル端部長さの２倍を有する再定義されたタイリングに対して示す。ランク情報は、引き続く繰り返しに対応するように割り当てられる。
【０１３０】
また、このランク情報の定義に関して、増大する粗調整されたタイリングに基づく間、ランク情報は、長距離移動用、つまり、より特定的には、タイリングのタイルを結ぶ長距離ルート用の道路セグメントの重要性に対する尺度である。粗調整されたタイリングの階層用に計算されたランク情報または擬似ランク情報は、元々のタイリングに対するランク値に直接変換し戻す（ｔｒａｎｓｌａｔｅ ｂａｃｋ）ことはできない一方で、それらは、依然、このランク情報に基づいて、最適ルートの正確な決定が可能である。これについては、後述される。
【０１３１】
さらに、元々の道路網および元々のタイリングの意味で定義されたランク値と、第一に再定義されたタイリングおよび第一に粗調整されたタイリング用に定義されたランク値とは、包含関係（ｉｎｃｌｕｓｉｏｎ ｒｅｌａｔｉｏｎ）によって、相変わらず、相互接続されることに留意すべきである。例えば、元々の道路網および元々のタイリングのタームで、少なくとも６のランク値を有する全ての道路セグメントのセットは、第一に再定義されたタイリングのタームで、少なくとも２のランク値を有する再定義された道路網の道路セグメントのセットのサブセットである。ここで、タイル距離は、後者の場合に再定義されたタイルの単位で測定される。同様に、元々の道路網および元々のタイリングの意味で、少なくとも５のランク値を有する全ての道路セグメントのセットは、第一に再定義されたタイリングのタームで、少なくとも３のランク値を有する再定義された道路網の道路セグメントのセットを含む。ここで、タイル距離は、後者の場合に再定義されたタイルの単位で測定される。後者の関係は、以下の事実から容易に理解され得る。Ａが元々のタイリングＴのタイルで、Ａ’が第一に粗調整されたＡを含むタイリングＴ’の場合、タイル距離がＴの意味で測定され、Ａから４以下のタイル距離を有するＴ内のタイルのセットは、タイル距離がＴ’のタームで測定され、Ａ’から２以下のタイル距離を有するＴ’内のタイルのセットに含まれる。このような包含関係も、また、以下に説明されるように、最適ルートの決定に使用され得る。
【０１３２】
図６に示す方法は、粗調整されたタイリングおよび対応するランク情報の階層を導入する。
【０１３３】
当然、図６に示す有利な方法の他の変種も、また、可能である。例えば、繰り返しのランク値計算の回数、すなわち、ループ２５４〜２５８における異なるｋ値の数は、タイルサイズに応じて、変化し得る。例えば、繰り返しは、元々のタイルサイズに対して、１から３の値に拡張し得るが、全ての引き続くタイルサイズに対しては、１から４に拡張し得る。さらに、再定義された道路網およびタイル端部長さに対する繰り返しは、道路網またはグラフＧが空になるまで継続される必要がなく、終了し得る。
【０１３４】
図８に戻ると、道路セグメントｖａおよびｖｄは、タイル３１１の１境界上の点３１２と点３１３とを結ぶ最適ルートを必然的に含まれるので、ランク値は少なくとも１を有する。道路セグメントｖｅ、ｖｆおよびｖｇは、タイル３１１を通過する最適ルートに含まれていないので、０に等しいランク値を有する。道路セグメントｖｂ、ｖｃおよびｖｈのランク値は、点３１２と点３１３とを結ぶ最適ルートが道路セグメントｖｂおよびｖｃを経由するか、あるいは、道路セグメントｖｈを経由するかに、依存する。これは、個々の道路セグメントに割り当てられる重み付けファクタに依存する。最適ルートに基づく距離に対して、道路セグメントｖｂおよびｖｃは、１に等しいランク値を有し、一方で、道路セグメントｖｈはランク値０を有する。時間ベースの最適ルート探索に対して、道路セグメントｖｈ上での移動時間が、道路セグメントｖｂおよびｖｃ上での移動時間に比べ、短ければ、ｖｈはランク値１を有する。重み付けファクタ、および、それゆえ、最適ルートは、移動方向にも依存し得ることに留意すべきである。例えば、ｖｂ、ｖｃおよびｖｈが一方通行の道路であり、ｖｈ上で許可される走行方向が、ｖｂおよびｖｃの双方上で許可される走行方向と逆であると仮定すると、ｖｂ、ｖｃおよびｖｈは、全て１に等しいランク値となる。
【０１３５】
図８に関して続けて述べると、正確なランク値あるいはその正確なランク値の下界（ｌｏｗｅｒ ｂｏｕｎｄ）のいずれかを特定することによって、タイル内の全ての道路セグメントのランク値を計算した後に、ランク値が所定の閾値を超える場合、道路セグメントデータの前処理は、シーケンスを形成し、１つのタイル内に含まれる幾つかの道路セグメントを、１つの新たな道路セグメントに、相互結合するステップを含み得る。これは、例えば、図６のように、ショートカットを形成することを意味する。例えば、道路セグメントｖｂおよびｖｃも、また、ランク値１を有する場合、道路セグメントｖａ、ｖｂ、ｖｃおよびｖｄは、３１２から３１３に伸びる新たな道路セグメントに相互結合され得る。新たな道路セグメントの重み付けファクタは、ｖａ、ｖｂ、ｖｃおよびｖｄの重み付けファクタから計算される。このような道路セグメントの相互結合は、上記で図６を参照して説明されたランク情報を計算する方法の一部をなす。道路セグメントの総数を減らすことで、引き続く最適ルートの決定の間に、例えば、ナビゲーションシステムにおいて、さらなる迅速化が達成され得る。しかしながら、新たな道路セグメントは、引き続くステップの間、そのコンポーネントに分解されねばならないこともあり得ることに留意すべきである。それゆえ、元々の道路セグメントを参照する情報は、新たな道路セグメントの属性として、含まれるべきである。また、道路セグメントの相互結合は、さらに、ランク情報に基づき得る。例えば、実施形態に従うと、特定の最小値に等しいランクか、あるいは、特定の最小値に少なくとも等しいランク値を有する道路セグメントのみが、相互結合され得る。
【０１３６】
計算されたランク情報は、図１に示すシステム１の第三のストレージユニット３０または追加作業メモリユニット６０の中に格納され得る。特に、ランク情報を、システム１の作業メモリユニット５０または６０に格納することは、上述したようなランク情報を計算する再帰的方法で、ランク情報を引き続き取り出しするのに、特に有効である。ランク情報は、対応する道路セグメントを識別できるようにする識別子を用いて、個別のストレージユニットまたはメモリユニットに格納され得る。あるいは、図１のアレイ３１、３２、６１および６２で示されるように、ランク情報は、道路セグメントデータと一緒に、対応する道路セグメントに対する追加属性として、格納され得る。
【０１３７】
上述したランク情報を計算する方法の一部、特に再帰的方法に従うと、図３Ｃのステップ１１３２あるいは図５のステップ２２５における最適ルートの計算の複雑さは、最適ルート探索が実行されるべき道路セグメントのサブセットを選択することによって、緩和される。考慮すべき道路セグメントの総数を減らすことによって、少なくとも所定のタイルＴおよびその所定のタイルの所定の境界に対して、作業メモリユニット５０の中に、最適ルートの計算に必要とされる全ての道路セグメントを格納することが実行可能となる。それゆえ、システム１の作業メモリユニット５０は、全ての道路セグメントデータと、また、必要に応じて、ステップ１１３２または２２５で、それぞれ実行されるような最適ルートの計算に必要なタイリング定義データとを格納することに適合されることが好ましい。
【０１３８】
既に上述したように、本発明に従うランク情報を計算する方法は、コンピュータクラスタまたはグリッド上で実行されるように適合される。これは、ランク計算に対する全体の処理時間を短縮するのに望ましい。タイルに含まれる道路セグメントに対するランク情報を計算する上述の方法の各ステップは、そのタイルの近傍で動作するのみであるため、その方法に、道路セグメントのランク情報を並列計算するように適合された様々なスキーム（例えば、ピアツーピアまたはマスタワーカスキームのような）を適応するのは容易である。例示的に、しかし、決して限定する意味でないが、次いで、マスタワーカスキームが説明される。ここで、マスタと指定された１台と、任意の台数のワーカからなるコンピュータネットワークが、使用され得る。概念的に、マスタは、問題を小さなジョブに分解し、そのジョブをワーカに委託し、また、最終的にその結果の回収も行い得る。マスタおよびワーカは、道路網のデータの共通のコピー上で動作し得て、各道路セグメントは、今までに計算された最大ランクでマークされている。実際には、マスタに対する限定的なアクセスを用いて、完全なデータのコピー１つのみを有し、各ジョブに対して、マスタによって生成された道路セグメントのサブセットのローカルコピー上で、ワーカに動作させることが、容易であり得る。ランク情報が増加するランク値に対して計算される上述の再帰的方法において、外側のループで、マスタは、ランク値０から開始して、ランク値ｋにわたり繰り返す。すなわち、マスタは、考慮すべきタイル近傍のサイズにわたり、繰り返す。内側のループで、マスタは、全てのタイルにわたり繰り返し、少なくともランクｋ＋１を有し、そのようなタイル（例えば、Ａ）に含まれる道路セグメントのサブセットの計算を委託する。特定のタイルＡに対し、これら道路セグメントＧ（ｋ＋１，Ａ）を計算するために、道路セグメントのサブセットのみが、考慮される必要がある。このサブセットは、上述の方法で記載されたように選択され得る。より特定的には、例えば、Ｇ（ｋ＋１，Ａ）を計算するためには、タイルＡからタイル距離ｄＡＢ＝ｋを有するタイルＢにおいて、Ｇ（ｍｉｎ（ｋ＋１−ｄＡＢ），Ｂ）を含む道路セグメントのみが、考慮される必要がある。ランク情報は、増加するランク値に対して計算されるので、これら道路セグメントは、既知である。全てのタイルＢにわたるこれら道路セグメントのユニオンは、Ｇ（ｋ＋１，Ａ）の計算に対して十分である。ワーカが、道路セグメントがＧ（ｋ＋１，Ａ）に含まれることを決定すると、共通ストレージ内の道路セグメントのランク属性は、ｋ＋１に増える。共通ストレージのない場合、ワーカはマスタによって送信されたローカルコピーを使用し、そのローカルコピー内のランクを更新し、そして、更新されたデータをマスタに返信する。次いで、マスタは、完全なデータセットのコピー内に格納されたデータを更新する。全てのワーカが、所望の結果を計算した後に、マスタは、ｋをインクリメントし、外側ループの次の繰り返しを開始する。
【０１３９】
上記のマスタワーカスキームは、さらに最適化され得る。特に、単一のグループのタイルに対してより、タイルのより大きなグループに対して、ジョブを生成することは、より効率的である。それゆえ、ワーカは、選択されるタイルのセットの各セットが十分小さくなるように、これら選択されたセットを割り当たえられ得る。こうして、このセットの中の各Ａに対して、Ｇ（ｋ＋１，Ａ）を計算するのに必要とされる全ての道路セグメントデータおよび関連するデータのユニオンは、ワーカのメモリ内に同時に格納され得る。ワーカは、この必要とされるデータを全て取り込み、そのワーカに割り当てられたタイルのセット内の全てのタイルにわたって、繰り返す。このようにして、マスタとワーカとの間の通信処理量（ｃｏｍｍｕｎｉｃａｔｉｏｎ ｏｖｅｒｈｅａｄ）は、軽減され得る。
【０１４０】
ランク情報の計算に使用されるのが、単独のコンピュータであるか、あるいは、コンピュータクラスタまたはグリッドであるかに関わらず、計算されたランク情報は、引き続く最適ルートの計算で使用するために、出力ユニット７０を介して、出力され得る。後者をさらに迅速化するために、道路セグメントデータおよび対応するランク情報は、必要とされるデータの取り出しを容易にし、効率よくこなせるように、アレンジされることが好ましい。これは、特定の方法で、格納または出力のために、道路セグメントデータをアレンジすることによって、達成される。上記のランク情報を決定する第三の代替的方法で議論したように、タイルサイズが、ランク値の決定において異なっている場合、道路セグメントデータは、まず、タイルサイズに従って、アレンジされる。異なるタイルに対応するデータは、タイルの地理的位置に従って、アレンジされる。各タイルに対して、データは、ランク情報に従ってアレンジされる。典型的には、道路セグメントデータは、道路セグメント属性のようなランク情報を含むアレイとして、格納される。そして、対応する道路セグメントが、幾つかの元々の道路セグメントを相互結合して形成されているなら、道路セグメントは、また、元々の道路セグメントに関連する情報も含む。さらに、データの取り出しを効率よくするために、索引ファイルが、特定のタイルサイズ、タイル、および、ランク情報に関連するデータが、道路セグメントのどこに見つけられ得るかに関する情報を含んで、提供され得る。
【０１４１】
前処理する段階（ｐｈａｓｅ）で計算されるランク情報は、地図上の相対位置に基づく道路セグメントの重要性の尺度を提供するので、ランク情報は、後のステージで実行される最適ルートの決定を迅速化するために、取り出され得る。このような最適ルートの決定は、車両に搭載するナビゲーションシステムによって、実行されることが多い。本発明の実施形態に従うナビゲーションシステム、および、そのシステムの最適ルートを決定するシステムは、図１０〜図１３を参照しながら、以下に記載される。
【０１４２】
図１０に示すナビゲーションシステムは、入力ユニット４１０、出力ユニット４１１、位置検出手段４１２、および、最適ルートを決定する（より特定的には計算する）システム４２０を備える。コンポーネント４１０〜４１２のそれぞれは、従来のナビゲーションシステムから知られている対応するコンポーネントの一つであり得る。例えば、入力ユニットは、タッチスクリーンを備え得るし、出力ユニットは、文書音声変換ユニットに結合されたディスプレイまたはラウドスピーカを備え得るし、また、位置検出手段は、ＧＰＳ受信機またはジャイロスコープを備え得る。
【０１４３】
最適ルートを決定するシステム４２０は、図１１に、より詳細に示される。システム４２０は、第一のストレージユニット４３０を備える。このユニット４３０は、本実施形態に従うと、道路セグメントデータ、および、上述した前処理する段階の間に計算された関連するランク情報データの双方を格納するように適合される。データはアレイ４３１〜４３３として格納され、ランク情報は追加道路セグメントの属性として、これらアレイの中に含まれる。代替的に、ランク情報データは、個別のストレージユニットを介しても、また、提供され得る。システム４２０は、さらに、例えば、数字の多重項４４１、４４２、４４３の形式で、タイリング定義データを格納するために、追加のストレージユニット４４０を備える。システム４２０は、さらに、処理ユニット４５０、および、道路セグメントデータのサブセットを、例えば、これもまた、アレイ４６１および４６２の形式で、格納するのに適合された作業メモリユニット４６０を備える。これらアレイは、道路セグメントの位置および方向、ならびに、関連する重み付けファクタおよび／またはランク情報に関する情報を含む。タイリング定義データおよび道路セグメントデータは、道路セグメントデータを前処理するために使用されたデータセットと、実質的に同一である。ただし、この道路セグメントデータは、追加的に、ランク情報を含む点は異なる。
【０１４４】
ルートの出発点と目的地に関する情報を受信した後、最適ルートを決定するシステム４２０は、最適ルート探索を開始し、最適ルートを計算する。ランク情報、および、道路セグメントを含むエリア用のタイリングを提供することによって、最適ルートの計算を、効率的に実行することが可能になる。これについては、図１２Ａおよび図１２Ｂを参照して、以下に記載される。出発点が出発タイルＳに含まれ、目的地が目的地タイルＤに含まれると仮定し、さらに、出発タイルと目的地タイルは、１より大きいタイル距離を有すると仮定すると、出発点と目的地とを結ぶ任意の最適ルートは、出発タイルと目的地タイルとから、それぞれ少なくとも１のタイル距離を有するタイルを通過する。それゆえ、全てのそのようなタイルの中で、少なくとも１のランク値を有する道路セグメントのみを考慮すれば、十分である。同様にして、上述のようなランク値の定義によって、出発タイルおよび目的地タイルの双方から少なくとも２のタイル距離を有するタイルの中で、少なくとも２のランク値を有する道路セグメントは、出発点から目的地への最適ルートに、潜在的に含まれる。それゆえ、最適ルート探索を、対応するタイルの中で、これら道路セグメントに、限定すれば、十分である。これは、タイリング５１０に対して、出発点タイルＳと目的地タイルＤとがそのタイリング５１０の向かい合う角にあるようにアレンジされて、図１２Ａに模式的に示されている。タイル５１１およびタイル５１５は、出発タイルおよび目的地タイルの双方から、１以上のタイル距離を有する。それゆえ、少なくとも１のランク値を有する道路セグメントのサブセットのみが、考慮される必要があり、これは、このサブセットが対応するタイル用であることを表す記号Ｇ（１）によって模式的に示される。当然、Ｇ（１）は、タイル５１１および５１５に対しては異なり、タイル索引は、簡略化のために削除されていることに、留意すべきである。同様の議論は、タイル５１２およびタイル５１６に関しても当てはまる。タイル５１２および５１６に対して、少なくとも２のランク値を有する道路セグメントのサブセットのみが、考慮される必要があり、タイル５１３および５１７に対して、少なくとも３のランク値を有する道路セグメントのサブセットのみが、考慮される必要があり、タイル５１４に対して、少なくとも４のランク値を有する道路セグメントのサブセットのみが、考慮される必要がある。それゆえ、最適ルートの計算は、ランク情報を考慮して実行される。より特定的には、道路セグメントのサブセットに対する最適ルートを計算し、そのサブセットは、ランク情報およびタイリングデータに基づいて選択されることで、実行される。
【０１４５】
ランク情報の計算が、所定の最大ランク値で終了した場合、最適ルート探索が実行される道路セグメントのサブセットは、図１２Ｂに示すように、追加の道路セグメントを含み得る。タイリング５２０に対して、所定の最大ランク値が３に等しい場合、すなわち、ランク情報３が、３以上のランク値を有する全ての道路セグメントに割り当てられた場合、最適ルート探索が実行される道路セグメントのサブセットも、また、タイル５２４および５２５で、ランク値３に等しいランク値を有する道路セグメントを含む。サブセットに道路セグメントを加えることで、計算の複雑さは増加するが、最適ルートを決定するシステム４２０によって実行される方法は、それでもなお、正確な結果を提供する。
【０１４６】
システム４２０によって実行される方法は、以下に図１３Ａおよび図１３Ｂを参照しながら説明される。図１３Ａを参照すると、この実施形態に従う最適ルートを計算する方法は、ステップ６１０で示すように、ランク情報およびタイリングデータに基づいて、道路セグメントのサブセットを選択するステップと、ステップ６２０で示すように、道路セグメントのサブセットに基づいて、最適ルートを計算するステップと、ステップ６３０で、最適ルートを、例えば、ナビゲーションシステムの出力ユニットに出力するステップを包含する。
【０１４７】
本実施形態に従う道路セグメントのサブセットを選択するプロセスの流れ図は、より詳細に図１３Ｂに示される。まず、ステップ６１１で、出発点を含む出発タイルと、目的地を含む目的地タイルとが、決定される。ステップ６１２で、これらタイルの間の出発−目的地タイル距離ｄＳＤが計算される。続いて、ステップ６１３で、ｄＳＤを２で除算したフロア以下の整数値ｋが選択される。前処理段階でのランク情報の計算が、所定の最大ランク値で終了した場合、ｋは典型的には、この最大ランク値から１を減じた値を超えないような値が選択される。ステップ６１４で、最適ルートの探索が実行されるべき道路セグメントのサブセットＧ’は、そのタイリングの全てのタイルを含み、少なくともｋ＋１のランク値（Ｇ（ｋ＋１）で示す）を有する全ての道路セグメントのセットとして、初期化される。サブセットＧ’が初期化された後、ステップ６１５〜６１９で、追加の道路セグメントは、Ｇ’の中に含まれる。出発タイルＳまたは目的地タイルＴから各タイルＴまでの距離は、ｄＴＳおよびｄＴＤと記されるが、出発タイルＳまたは目的地タイルＤのいずれかからｋ以下のタイル距離を有する各タイルＴに対して、Ｔに含まれ、タイル距離ｄＴＳおよびｄＴＤの小さなタイル距離以上のランク値を有するセットは、Ｇ’の中に含まれる。Ｔの中に含まれ、タイル距離ｄＴＳおよびｄＴＤの小さなタイル距離以上のランク値を有する道路セグメントのセットは、Ｇ（ｄｍ，Ｔ）で示される。このステップは、出発タイルＳまたは目的地タイルＤのいずれかから、ｋ以下の距離を有する全てのタイルに対して、繰り返される。特に、この方法に従うと、出発タイルまたは目的地タイルに含まれる全ての道路セグメントは、Ｇ’に含まれる。繰り返しが終了した後、Ｇ’は、さらなる処理のために、ステップ６１８に提供される。
【０１４８】
上述したように、例えば、図６に示されるランク情報を計算する第三の代替方法において、ランク情報は、粗調整されたタイリングの階層のために計算され得る。この場合、粗調整されたタイリングに対して計算されたランク情報または擬似ランク情報は、元々のタイリングに対するランク値に、直接、変換（ｔｒａｎｓｌａｔｅ）しない。しかしながら、道路セグメントのデータを前処理する間と同様に、最適ルートを計算する間にも、粗調整されたタイリングの同じ階層を使用することによって、正確な最適ルートは、それでもなお、効率的に決定され得る。それゆえ、道路セグメントデータの前処理が、タイリングの階層に基づいてなされた場合、タイリング定義データは、最適ルートの計算のために、例えば、タイリングのそれぞれを記述する数学的関数の形式で、これらタイリングのそれぞれに対し、提供される。
【０１４９】
タイリングの階層のために、ランク値はその階層の様々なレベルに対して計算され、道路セグメント６１０のサブセットを選択するステップは、上記に記載されたステップと比較し、変更される。それにも関わらず、粗調整する階層の各レベルで、プロセスは、図１３Ｂに示すプロセスと、実質的に同様である。データ前処理の間で、少なくともｒのランク値を有する全ての道路セグメントの計算後、道路網は最初に再定義される。この間、タイリングは、元々のタイリングＴからＴ’に、同時に粗調整される。次いで、少なくとも０の値を有する道路セグメント、少なくとも１の値を有する道路セグメントなどが順に、少なくともｒの値を有する道路セグメントまでが、元々のタイリングのタームでから知られている。次いで、ステップ６１０で、道路セグメントのサブセットが、以下の方法で選択される。まず、出発点を含むタイルＳおよび目的地を含むタイルＤからｒ未満の距離を有する全ての道路セグメントに対して、道路セグメントは、上述の図１３Ｂのステップ６１５、６１６、６１７および６１９と同様に、Ｇ’に含まれる。引き続き、Ｓからｒ未満の距離を有し、Ｄからｒ未満の距離を有する元々のタイリングＴ内のタイルのセット（それぞれ、Ｓ’およびＤ’と記し、元々のタイルの「ハル（ｈｕｌｌ）」と称する）をカバーするＴ’内のタイルのセットが、決定される。ｒ未満のタイル距離は、それでもなお、元々のタイリングＴのタームで測定されることに留意すべきである。引き続き、Ｓ’に含まれ、Ｓから少なくともｒの距離を有する元々の各タイルに対して、および、Ｄ’に含まれ、Ｄから少なくともｒの距離を有する元々の各タイルに対して、少なくともｒ−１のランク値を有するこれらタイルの道路セグメントは、道路セグメントのサブセットＧ’に含まれる。Ｓ’およびＤ’の外側で、道路セグメントは、最初に粗調整されたタイリングに対し計算されたランク情報に基づいて、Ｇ’に含まれ得る。より特定的には、Ｓ’およびＤ’の双方から少なくともｋの距離を有する粗調整されたタイリングの任意のタイルＡ’に対しては、Ａ’に含まれ、少なくともｋのランク値を有する道路セグメントのセットを含めば、十分であるが、今や、粗調整されたタイリングに関して決定されたように、道路セグメントのセットは、図１３Ｂのステップ６１５、６１６、６１７および６１９と同様に、Ｇ’に含まれる。粗調整されたタイリングに対するランク値の計算が、ｋより小さな値で終了した場合は、Ａ’に含まれ、決定された最大ランク値を有する道路セグメントは、Ｇ’に含まれる。
【０１５０】
幾つかの増えていく粗調整されたタイリングを備えるタイリングの階層に対して、特定のタイル近傍のハルを決定し、これらハルの外側で、粗調整されたタイリングおよび対応するランク値をもとに、道路セグメントを、道路セグメントのサブセットＧ’に含める上述の方法は、再度、繰り返され得る。
【０１５１】
最適ルートを決定するシステム４２０において、道路セグメントのサブセットの選択は、処理ユニット４５０によって、行われる。処理ユニット４５０は、上述した基準にのっとって、ランク情報およびタイリング定義に従い、道路セグメントを作業メモリ４６０に格納されたデータに含める。作業メモリ４６０は、十分なストレージ容量を提供することが好ましい。それは、サブセットＧ’に対応する道路セグメントデータが、同時に格納され、最適ルート探索が、このデータ上で実行され得るようにするためである。
【０１５２】
道路セグメントのサブセットに対して、最適ルートを計算するステップ６２０は、ＤｉｊｋｓｔｒａのアルゴリズムまたはＡ＊アルゴリズムのような標準的な最適経路アルゴリズムを使用して実行される。こうして、後者の場合、距離ベースの最適ルートに対して、２点間のエア距離が、実際の最適経路コストに対する下限を提供する。時間ベースの最適ルートに対して、特徴的な移動速度で除算されたエア距離が、最適経路コストに対する下限を提供する。
【０１５３】
最適ルートは、ステップ６３０で、例えば、ナビゲーションシステムの出力ユニット４１１のようなユーザインターフェースに出力される。本実施形態に従う最適ルートを計算するシステムは、最適ルートを決定する従来のシステムと本質的に同じ方法で、ナビゲーションデバイスの他のコンポーネントと、インターフェースするために、業界のナビゲーションシステムから既知の様々な機能と、容易に組み合わされ得る。
【０１５４】
最適ルートを計算する上述の方法は、最適ルート問題に正確な解を提供するが、上述の方法の幾つかの変種も、少なくともほぼ最適なルートを提供することは、考えられる。例えば、計算の複雑さを緩和するために、それゆえ、ランタイムを短縮し、メモリスペースの要求を減らすために、道路セグメントがＧ’に含まれるより厳しい条件を設定して、タイル距離およびランク値に依存するサブセットＧ’に含まれる道路セグメントの総数は、減らされ得る。また、最適ルートを決定する間に、タイリング定義と独立した道路セグメントの妥当性の尺度として、ランク情報を使用することも考えられる。例えば、道路セグメントは、ランク値に１を加算した値が、それぞれ出発点から道路セグメント頂点の一つまでの距離と、目的地から道路セグメント頂点の一つまでの距離との最短距離を、道路セグメントを前処理する間に使用される特徴的なタイル端部長さで除算された値未満でない場合、サブセットＧ’に含まれ得る。
【０１５５】
最適ルートを計算する上述の方法は、タイルサイズが１つのみについて説明されてきたが、道路セグメントデータを前処理する間に、タイルサイズが変動する場合は、最適ルートを決定する間に、タイルサイズは、対応して変動することは理解される。特に、出発点または目的地からの距離が増加すると、より高いランク情報値を有する道路セグメントのみが、考慮される必要がある。このランク情報が、ますます粗調整されるタイリングに基づいて、計算されると、タイリングは、最適ルート計算中に、対応して粗調整される。
【０１５６】
上述した実施形態に従うと、最適ルートの計算の１つのモードのみが考慮されてきたが、多数のランク情報データが１つの道路セグメントに対して、提供され得る。異なるランク値は、最短ルート、最速ルート、トンネルなしのルートまたはフェリーなしのルートなどに対応する。次いで、最適ルートの計算は、これら異なるモードの任意の一つに対して、ユーザの選択したモードに基づき、それぞれのモードに対応するランク情報に基づき選択される道路セグメントのサブセットを用いて、実行され得る。ランク情報が様々な異なるコスト関数に対して計算された場合、これらコスト関数のそれぞれに対応するランク情報は、各道路セグメントに対して、格納される。代替的に、各道路セグメントに対し、異なるコスト関数に対して得られたランク値の最大のみが格納され得て、こうして、要求されるストレージ容量を削減し得る。しかしながら、最適ルートの計算は、この後者の場合ですら、正確な最適ルートをもたらす。
【０１５７】
以上のように、本発明の好ましい実施形態を用いて本発明を例示してきたが、本発明は、この実施形態に限定して解釈されるべきものではない。本発明は、特許請求の範囲によってのみその範囲が解釈されるべきであることが理解される。当業者は、本発明の具体的な好ましい実施形態の記載から、本発明の記載および技術常識に基づいて等価な範囲を実施することができることが理解される。本明細書において引用した特許、特許出願および文献は、その内容自体が具体的に本明細書に記載されているのと同様にその内容が本明細書に対する参考として援用されるべきであることが理解される。
【０１５８】
最適ルートを計算するために道路セグメントデータを前処理する方法、前処理された道路セグメントデータに基づいて、最適ルートを決定する方法、および、対応するシステムが提供される。道路セグメントデータを前処理する方法に従うと、タイリングが提供され、ランク情報（ｒ）が、タイリング情報に基づいて、道路セグメント（ｖ）に対して、計算される。このランク情報（ｒ）は、タイリングのタイルを結ぶ最適ルートに対する道路セグメントの妥当性の尺度となる。地図上の相対位置に基づき計算されるランク情報（ｒ）を用いて、引き続く最適ルート計算にランク情報情報が提供される。これによって、例えば、車両におけるナビゲーションシステムにおいて、最適ルートの計算を効率的に実行することが可能になる。
【図面の簡単な説明】
【０１５９】
【図１】図１は、本発明の実施形態に従う道路セグメントデータを前処理するシステムの模式ブロック図を示す。
【図２】図２は、道路セグメントのセットの模式図を示す。
【図３Ａ】図３Ａは、本発明の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図３Ｂ】図３Ｂは、本発明の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図３Ｃ】図３Ｃは、本発明の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図４】図４は、本発明の別の実施形態に従う道路セグメントデータを前処理する方法のサブルーチンを表す流れ図を示す。
【図５】図５は、本発明の別の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図６】図６は、本発明の更なる別の実施形態に従うランク情報を決定する方法を表す流れ図を示す。
【図７】図７は、タイリングを示し、本発明の実施形態に従うタイル距離の定義を模式的に示す。
【図８】図８は、タイリングおよび道路セグメントを示し、本発明の実施形態に従うランク情報の決定ステップを模式的に示す。
【図９】図９Ａおよび図９Ｂは、本発明の実施形態に従う道路セグメントデータを前処理する方法の再帰的ステップを模式的に示す。
【図１０】図１０は、本発明の実施形態に従うナビゲーションシステムの模式的なブロック図を示す。
【図１１】図１１は、本発明の実施形態に従う最適ルートを決定するシステムの模式的なブロック図を示す。
【図１２】図１２Ａおよび図１２Ｂは、本発明の実施形態に従う最適ルートを決定するために、道路セグメントのサブセットを選択するステップを模式的に示す。
【図１３Ａ】図１３Ａは、個々に、本発明の実施形態に従う最適ルートを決定する方法を表す流れ図を示す。
【図１３Ｂ】図１３Ｂは、本発明の実施形態に従う最適ルートを決定する方法における道路セグメントのサブセットを選択するステップを表す流れ図を示す。
【符号の説明】
【０１６０】
３１０ タイリング
３１１ タイル
３１２、３１３、３１４、３１５、３１６、３１７、３１８ 点
ｖａ、ｖｂ、ｖｃ、ｖｄ、ｖｅ、ｖｆ、ｖｇ 道路セグメント
【特許請求の範囲】
【請求項１】
最適ルート決定用の道路セグメントデータを前処理する方法であって、
該道路セグメントデータを提供するステップと、
該道路セグメントが含まれるエリアをカバーするタイリングを定義するステップと、
道路セグメントに対するランク情報を決定するステップで、該ランク情報は該タイリングのタイルを結ぶ最適ルート用の該道路セグメントの妥当性を定量化する、ステップと
を包含する、道路セグメントデータを前処理する方法。
【請求項２】
前記ランク情報は、前記タイリングに依存して決定され、タイル端部に位置する点を結ぶ最適ルート用の道路セグメントの妥当性を定量化すること
を特徴とする、請求項１に記載の道路セグメントデータを前処理する方法。
【請求項３】
前記道路セグメントの各道路セグメントは、前記タイリングの多くても１つのタイルに含まれるように、前記タイリングが定義されるか、または、前記道路セグメントが再定義されること、および、前記ランク情報が、該タイリングに依存して決定されること
を特徴とする、請求項１または請求項２に記載の道路セグメントデータを前処理する方法。
【請求項４】
前記道路セグメントに対するランク情報を決定するステップは、
該道路セグメントを含むタイルを決定するステップと、
該道路セグメントを含む該タイルから、少なくとも所定のタイル距離を有する第一のタイルを選択するステップと、
該道路セグメントが、該第一のタイルに位置する出発道路セグメントを有する最適ルートに含まれるかどうかを決定するステップと
を包含することを特徴とする、請求項３に記載の道路セグメントデータを前処理する方法。
【請求項５】
前記出発道路セグメントの頂点は、前記第一のタイルの端部に位置すること
を特徴とする、請求項４に記載の道路セグメントデータを前処理する方法。
【請求項６】
前記ランク情報を決定するステップは、
前記道路セグメントを含む前記タイルから、少なくとも前記所定のタイル距離を有する第二のタイルを選択するステップであって、前記最適ルートの目的地道路セグメントは該第二のタイルに位置する、ステップ
をさらに包含する
ことを特徴とする、請求項４または請求項５に記載の道路セグメントデータを前処理する方法。
【請求項７】
前記目的地道路セグメントの頂点は、前記第二のタイルの端部に位置すること
を特徴とする、請求項６に記載の道路セグメントデータを前処理する方法。
【請求項８】
前記ランク情報を決定するステップは、
前記道路セグメントが最適ルートに含まれるように、前記所定のタイル距離の最大を決定するステップをさらに包含すること
を特徴とする、請求項４〜請求項７のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項９】
前記ランク情報を決定するステップは、前記所定のタイル距離の値を増やして、再帰的に実行されること
を特徴とする、請求項４〜請求項８のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１０】
前記所定のタイル距離の所定の値に対して、最適ルート探索は、該所定のタイル距離のより小さな値に対して得られた結果に基づいて、選択された道路セグメントのサブセット上で実行されること
を特徴とする、請求項４〜請求項９のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１１】
道路セグメント重み付けファクタを提供するステップを特徴とし、
前記ランク情報を決定するステップは、該重み付けファクタにさらに基づくことと
請求項１〜請求項１０のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１２】
前記ランク情報を決定するステップは、前記道路セグメントの各道路セグメントに対して、実行されること
を特徴とする、請求項１〜請求項１１のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１３】
前記タイリングのタイルは、長方形の形状であること
を特徴とする、請求項１〜請求項１２のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１４】
２つのタイル間のタイル距離は、該２つのタイルを結ぶ経路を通過するタイル端部またはタイル頂点の最小数として定義されること
を特徴とする、請求項１〜請求項１３のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１５】
１つのタイルに含まれる道路セグメントシーケンスを新たな道路セグメントに、相互結合するステップ
を特徴とする、請求項１〜請求項１４のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１６】
所定の道路セグメントのランク情報が決定された後、前記タイリングを粗調整するステップ
を特徴とする、請求項１〜請求項１５のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１７】
前記決定されたランク情報を出力するステップ
を特徴とする、請求項１〜請求項１６のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１８】
前記道路網は任意のグラフであり、各道路セグメントは該グラフのエッジ部であること
を特徴とする、請求項１〜請求項１７のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１９】
道路セグメントデータを提供するステップと、
請求項１〜請求項１８のいずれか１項に記載の方法に従って決定されたランク情報データを提供するステップと、
該道路セグメントデータおよび該ランク情報データに基づいて、出発点から目的地への最適ルートを決定するステップと
を包含する、出発点から目的地への最適ルートを決定する方法。
【請求項２０】
前記ランク情報に基づいて、道路セグメントのサブセットを選択するステップ
を特徴とし、
前記最適ルートを決定するステップは、該道路セグメントのサブセットに基づいて実行される、請求項１９に記載の最適ルートを決定する方法。
【請求項２１】
前記道路セグメントが含まれるエリアをカバーするタイリングを定義するステップ
を特徴とする、請求項１９または請求項２０に記載の最適ルートを決定する方法。
【請求項２２】
前記道路セグメントの各道路セグメントは、前記タイリングの多くても１つのタイルの中にしか含まれないように、前記タイリングが定義されるか、または、該道路セグメントが再定義されること
を特徴とする、請求項１９または請求項２１に記載の最適ルートを決定する方法。
【請求項２３】
前記道路セグメントのサブセットを選択するステップは、
前記出発点を含む出発タイルを決定するステップと、
前記目的地を含む目的地タイルを決定するステップと、
道路セグメントを、道路セグメントランク情報、および、該道路セグメントを含むタイルの該出発タイルまたは目的地タイルからのタイル距離に基づいて、前記道路セグメントのサブセットに含めるステップと
を包含することを特徴とする、請求項２０に従属した請求項２１または請求項２２およびに記載の最適ルートを決定する方法。
【請求項２４】
前記道路セグメントのサブセットを選択するステップは、
前記出発点を含む出発タイルから、前記目的地を含む目的地タイルまでの出発−目的地タイル距離を決定するステップと、
該出発−目的地タイル距離に基づいて最小ランク値を選択するステップと、
該最小ランク値以上のランク値を有する全ての道路セグメントを、該道路セグメントのサブセットに含めるステップと
を包含することを特徴とする、請求項２０に従属した請求項２１〜請求項２３のいずれか１項に記載の最適ルートを決定する方法。
【請求項２５】
道路セグメント重み付けファクタを提供するステップを特徴とし、
前記最適ルートを決定するステップは、該重み付けファクタに、さらに基づく、請求項１９〜請求項２４のいずれか１項に記載の最適ルートを決定する方法。
【請求項２６】
車両位置データを受信するステップと、
車両位置から前記目的地への最適ルートを決定するステップと
を特徴とする、請求項１９〜請求項２５のいずれか１項に記載の最適ルートを決定する方法。
【請求項２７】
前記道路網は任意のグラフであり、各道路セグメントは該グラフのエッジ部であること
を特徴とする、請求項１９〜請求項２５のいずれか１項に記載の最適ルートを決定する方法
【請求項２８】
道路セグメントデータを含む第一のストレージユニット（１０）と、
タイリング定義データを含む第二のストレージユニット（２０）と、
該道路セグメントデータのサブセットおよび該タイリング定義データのサブセットを格納する作業メモリユニット（５０）と、
該作業メモリユニット（５０）に格納されたデータを処理し、該タイリングに基づいて、道路セグメントのランク情報を決定するように適合された処理ユニット（４０）と
を備え、
該ランク情報は、該タイリングのタイルを結ぶ最適ルートに対する該道路セグメントとの妥当性を定量化する、道路セグメントデータを前処理するシステム。
【請求項２９】
前記システムは、請求項１〜請求項１８のいずれか１項に記載の道路セグメントデータを前処理する方法を実行するように適合されることを特徴とする、請求項２８に記載の道路セグメントデータを前処理するシステム。
【請求項３０】
前記処理ユニット（４０）に結合され、決定されたランク情報を格納するように適合された追加作業メモリユニット（６０）
を特徴とする、請求項２８または請求項２９に記載の道路セグメントデータを前処理するシステム。
【請求項３１】
前記処理ユニット（４０）は、前記ランク情報を決定するための前記追加作業メモリユニット（６０）に格納されたデータを処理するように適合されること
を特徴とする、請求項３０に記載の道路セグメントデータを前処理するシステム。
【請求項３２】
前記作業メモリユニット（５０）は、前記ランク情報を決定するための最適ルート探索に必要とされる道路セグメントデータのサブセットを格納するのに十分なストレージ容量を有すること
を特徴とする、請求項２８〜請求項３１のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【請求項３３】
決定されたランク情報を出力するための出力ユニット（７０）
を特徴とする、請求項２８〜請求項３２のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【請求項３４】
決定されたランク情報を格納するための第三のストレージユニット（３０）
を特徴とする、請求項２８〜請求項３３のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【請求項３５】
前記システムは、前記タイリングに基づく道路セグメントのランク情報を決定するのに適合された少なくとも１つの追加処理ユニットを備え、
前記処理ユニット（４０）および該追加処理ユニットは、並行して、道路セグメントランク情報を決定するように適合されていること
を特徴とする、請求項２８〜請求項３４のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【請求項３６】
道路セグメントデータを含む第一のストレージユニット（４３０）と、
ランク情報データを含む第二のストレージユニット（４３０）と、
該道路セグメントデータのサブセットを格納する作業メモリユニット（４６０）と、
該作業メモリユニット（４６０）に結合され、ランク情報データに基づいて、出発点から目的地への最適ルートを決定するように適合された処理ユニット（４５０）と
を備え、
該ランク情報データは、請求項１〜請求項１８のいずれか１項に記載の道路セグメントデータを前処理する方法に従って決定されることを特徴とする、最適ルート決定システム。
【請求項３７】
前記ランク情報データに基づいて、道路セグメントデータまたはランク情報データを、前記作業メモリユニット（４６０）に格納されたデータに入れること、あるいは、該作業メモリユニット（４６０）に格納されたデータから取り出すように適合された追加処理ユニット（４５０）
を特徴とする、請求項３６に記載の最適ルート決定システム。
【請求項３８】
タイリング定義データを含む第三のストレージユニット（４４０）
を特徴とする、請求項３６または請求項３７に記載の最適ルート決定システム。
【請求項３９】
前記作業メモリユニット（４５０）は、最適ルート決定に必要とされる前記道路セグメントデータのサブセットを格納するのに、十分なストレージ容量を有すること
を特徴とする、請求項３６〜請求項３８のいずれか１項に記載の最適ルート決定システム。
【請求項４０】
前記システムは、請求項１９〜請求項２７のいずれか１項に記載の最適ルートを決定する方法を実行するように適合されていること
を特徴とする、請求項３６〜請求項３９のいずれか１項に記載の最適ルート決定システム。
【請求項４１】
請求項３６〜請求項４０のいずれか１項に記載の最適ルート決定システム（４２０）
を特徴とする、ナビゲーションシステム。
【請求項４２】
前記最適ルート決定システム（４２０）に車両位置データを提供するように適合された位置決定手段（４１２）
を特徴とする、請求項４１に記載のナビゲーションシステム。
【請求項１】
最適ルート決定用の道路セグメントデータを前処理する方法であって、
該道路セグメントデータを提供するステップと、
該道路セグメントが含まれるエリアをカバーするタイリングを定義するステップと、
道路セグメントに対するランク情報を決定するステップで、該ランク情報は該タイリングのタイルを結ぶ最適ルート用の該道路セグメントの妥当性を定量化する、ステップと
を包含する、道路セグメントデータを前処理する方法。
【請求項２】
前記ランク情報は、前記タイリングに依存して決定され、タイル端部に位置する点を結ぶ最適ルート用の道路セグメントの妥当性を定量化すること
を特徴とする、請求項１に記載の道路セグメントデータを前処理する方法。
【請求項３】
前記道路セグメントの各道路セグメントは、前記タイリングの多くても１つのタイルに含まれるように、前記タイリングが定義されるか、または、前記道路セグメントが再定義されること、および、前記ランク情報が、該タイリングに依存して決定されること
を特徴とする、請求項１または請求項２に記載の道路セグメントデータを前処理する方法。
【請求項４】
前記道路セグメントに対するランク情報を決定するステップは、
該道路セグメントを含むタイルを決定するステップと、
該道路セグメントを含む該タイルから、少なくとも所定のタイル距離を有する第一のタイルを選択するステップと、
該道路セグメントが、該第一のタイルに位置する出発道路セグメントを有する最適ルートに含まれるかどうかを決定するステップと
を包含することを特徴とする、請求項３に記載の道路セグメントデータを前処理する方法。
【請求項５】
前記出発道路セグメントの頂点は、前記第一のタイルの端部に位置すること
を特徴とする、請求項４に記載の道路セグメントデータを前処理する方法。
【請求項６】
前記ランク情報を決定するステップは、
前記道路セグメントを含む前記タイルから、少なくとも前記所定のタイル距離を有する第二のタイルを選択するステップであって、前記最適ルートの目的地道路セグメントは該第二のタイルに位置する、ステップ
をさらに包含する
ことを特徴とする、請求項４または請求項５に記載の道路セグメントデータを前処理する方法。
【請求項７】
前記目的地道路セグメントの頂点は、前記第二のタイルの端部に位置すること
を特徴とする、請求項６に記載の道路セグメントデータを前処理する方法。
【請求項８】
前記ランク情報を決定するステップは、
前記道路セグメントが最適ルートに含まれるように、前記所定のタイル距離の最大を決定するステップをさらに包含すること
を特徴とする、請求項４〜請求項７のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項９】
前記ランク情報を決定するステップは、前記所定のタイル距離の値を増やして、再帰的に実行されること
を特徴とする、請求項４〜請求項８のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１０】
前記所定のタイル距離の所定の値に対して、最適ルート探索は、該所定のタイル距離のより小さな値に対して得られた結果に基づいて、選択された道路セグメントのサブセット上で実行されること
を特徴とする、請求項４〜請求項９のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１１】
道路セグメント重み付けファクタを提供するステップを特徴とし、
前記ランク情報を決定するステップは、該重み付けファクタにさらに基づくことと
請求項１〜請求項１０のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１２】
前記ランク情報を決定するステップは、前記道路セグメントの各道路セグメントに対して、実行されること
を特徴とする、請求項１〜請求項１１のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１３】
前記タイリングのタイルは、長方形の形状であること
を特徴とする、請求項１〜請求項１２のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１４】
２つのタイル間のタイル距離は、該２つのタイルを結ぶ経路を通過するタイル端部またはタイル頂点の最小数として定義されること
を特徴とする、請求項１〜請求項１３のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１５】
１つのタイルに含まれる道路セグメントシーケンスを新たな道路セグメントに、相互結合するステップ
を特徴とする、請求項１〜請求項１４のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１６】
所定の道路セグメントのランク情報が決定された後、前記タイリングを粗調整するステップ
を特徴とする、請求項１〜請求項１５のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１７】
前記決定されたランク情報を出力するステップ
を特徴とする、請求項１〜請求項１６のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１８】
前記道路網は任意のグラフであり、各道路セグメントは該グラフのエッジ部であること
を特徴とする、請求項１〜請求項１７のいずれか１項に記載の道路セグメントデータを前処理する方法。
【請求項１９】
道路セグメントデータを提供するステップと、
請求項１〜請求項１８のいずれか１項に記載の方法に従って決定されたランク情報データを提供するステップと、
該道路セグメントデータおよび該ランク情報データに基づいて、出発点から目的地への最適ルートを決定するステップと
を包含する、出発点から目的地への最適ルートを決定する方法。
【請求項２０】
前記ランク情報に基づいて、道路セグメントのサブセットを選択するステップ
を特徴とし、
前記最適ルートを決定するステップは、該道路セグメントのサブセットに基づいて実行される、請求項１９に記載の最適ルートを決定する方法。
【請求項２１】
前記道路セグメントが含まれるエリアをカバーするタイリングを定義するステップ
を特徴とする、請求項１９または請求項２０に記載の最適ルートを決定する方法。
【請求項２２】
前記道路セグメントの各道路セグメントは、前記タイリングの多くても１つのタイルの中にしか含まれないように、前記タイリングが定義されるか、または、該道路セグメントが再定義されること
を特徴とする、請求項１９または請求項２１に記載の最適ルートを決定する方法。
【請求項２３】
前記道路セグメントのサブセットを選択するステップは、
前記出発点を含む出発タイルを決定するステップと、
前記目的地を含む目的地タイルを決定するステップと、
道路セグメントを、道路セグメントランク情報、および、該道路セグメントを含むタイルの該出発タイルまたは目的地タイルからのタイル距離に基づいて、前記道路セグメントのサブセットに含めるステップと
を包含することを特徴とする、請求項２０に従属した請求項２１または請求項２２およびに記載の最適ルートを決定する方法。
【請求項２４】
前記道路セグメントのサブセットを選択するステップは、
前記出発点を含む出発タイルから、前記目的地を含む目的地タイルまでの出発−目的地タイル距離を決定するステップと、
該出発−目的地タイル距離に基づいて最小ランク値を選択するステップと、
該最小ランク値以上のランク値を有する全ての道路セグメントを、該道路セグメントのサブセットに含めるステップと
を包含することを特徴とする、請求項２０に従属した請求項２１〜請求項２３のいずれか１項に記載の最適ルートを決定する方法。
【請求項２５】
道路セグメント重み付けファクタを提供するステップを特徴とし、
前記最適ルートを決定するステップは、該重み付けファクタに、さらに基づく、請求項１９〜請求項２４のいずれか１項に記載の最適ルートを決定する方法。
【請求項２６】
車両位置データを受信するステップと、
車両位置から前記目的地への最適ルートを決定するステップと
を特徴とする、請求項１９〜請求項２５のいずれか１項に記載の最適ルートを決定する方法。
【請求項２７】
前記道路網は任意のグラフであり、各道路セグメントは該グラフのエッジ部であること
を特徴とする、請求項１９〜請求項２５のいずれか１項に記載の最適ルートを決定する方法
【請求項２８】
道路セグメントデータを含む第一のストレージユニット（１０）と、
タイリング定義データを含む第二のストレージユニット（２０）と、
該道路セグメントデータのサブセットおよび該タイリング定義データのサブセットを格納する作業メモリユニット（５０）と、
該作業メモリユニット（５０）に格納されたデータを処理し、該タイリングに基づいて、道路セグメントのランク情報を決定するように適合された処理ユニット（４０）と
を備え、
該ランク情報は、該タイリングのタイルを結ぶ最適ルートに対する該道路セグメントとの妥当性を定量化する、道路セグメントデータを前処理するシステム。
【請求項２９】
前記システムは、請求項１〜請求項１８のいずれか１項に記載の道路セグメントデータを前処理する方法を実行するように適合されることを特徴とする、請求項２８に記載の道路セグメントデータを前処理するシステム。
【請求項３０】
前記処理ユニット（４０）に結合され、決定されたランク情報を格納するように適合された追加作業メモリユニット（６０）
を特徴とする、請求項２８または請求項２９に記載の道路セグメントデータを前処理するシステム。
【請求項３１】
前記処理ユニット（４０）は、前記ランク情報を決定するための前記追加作業メモリユニット（６０）に格納されたデータを処理するように適合されること
を特徴とする、請求項３０に記載の道路セグメントデータを前処理するシステム。
【請求項３２】
前記作業メモリユニット（５０）は、前記ランク情報を決定するための最適ルート探索に必要とされる道路セグメントデータのサブセットを格納するのに十分なストレージ容量を有すること
を特徴とする、請求項２８〜請求項３１のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【請求項３３】
決定されたランク情報を出力するための出力ユニット（７０）
を特徴とする、請求項２８〜請求項３２のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【請求項３４】
決定されたランク情報を格納するための第三のストレージユニット（３０）
を特徴とする、請求項２８〜請求項３３のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【請求項３５】
前記システムは、前記タイリングに基づく道路セグメントのランク情報を決定するのに適合された少なくとも１つの追加処理ユニットを備え、
前記処理ユニット（４０）および該追加処理ユニットは、並行して、道路セグメントランク情報を決定するように適合されていること
を特徴とする、請求項２８〜請求項３４のいずれか１項に記載の道路セグメントデータを前処理するシステム。
【請求項３６】
道路セグメントデータを含む第一のストレージユニット（４３０）と、
ランク情報データを含む第二のストレージユニット（４３０）と、
該道路セグメントデータのサブセットを格納する作業メモリユニット（４６０）と、
該作業メモリユニット（４６０）に結合され、ランク情報データに基づいて、出発点から目的地への最適ルートを決定するように適合された処理ユニット（４５０）と
を備え、
該ランク情報データは、請求項１〜請求項１８のいずれか１項に記載の道路セグメントデータを前処理する方法に従って決定されることを特徴とする、最適ルート決定システム。
【請求項３７】
前記ランク情報データに基づいて、道路セグメントデータまたはランク情報データを、前記作業メモリユニット（４６０）に格納されたデータに入れること、あるいは、該作業メモリユニット（４６０）に格納されたデータから取り出すように適合された追加処理ユニット（４５０）
を特徴とする、請求項３６に記載の最適ルート決定システム。
【請求項３８】
タイリング定義データを含む第三のストレージユニット（４４０）
を特徴とする、請求項３６または請求項３７に記載の最適ルート決定システム。
【請求項３９】
前記作業メモリユニット（４５０）は、最適ルート決定に必要とされる前記道路セグメントデータのサブセットを格納するのに、十分なストレージ容量を有すること
を特徴とする、請求項３６〜請求項３８のいずれか１項に記載の最適ルート決定システム。
【請求項４０】
前記システムは、請求項１９〜請求項２７のいずれか１項に記載の最適ルートを決定する方法を実行するように適合されていること
を特徴とする、請求項３６〜請求項３９のいずれか１項に記載の最適ルート決定システム。
【請求項４１】
請求項３６〜請求項４０のいずれか１項に記載の最適ルート決定システム（４２０）
を特徴とする、ナビゲーションシステム。
【請求項４２】
前記最適ルート決定システム（４２０）に車両位置データを提供するように適合された位置決定手段（４１２）
を特徴とする、請求項４１に記載のナビゲーションシステム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【公開番号】特開２００７−１３２９２４（Ｐ２００７−１３２９２４Ａ）
【公開日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願番号】特願２００６−２６７６１１（Ｐ２００６−２６７６１１）
【出願日】平成１８年９月２９日（２００６．９．２９）
【出願人】（５０４１４７９３３）ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Ｆターム（参考）】
【公開日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願日】平成１８年９月２９日（２００６．９．２９）
【出願人】（５０４１４７９３３）ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Ｆターム（参考）】
[ Back to top ]