(57)【要約】  ここに記載されているのは、少なくとも２つの部分ルートに分けられる全体ルートを計算して、スタート地点から目的地点までナビゲーションする方法である。これらの部分ルートのうち、少なくとも１つの部分ルートは移動式のナビゲーションクライアントにおいてローカルに計算され、また少なくとも１つの別の部分ルートは中央の固定式のルートサーバにおいて計算される。本発明では、結果的に得られる全体ルートに依存して第１の部分ルートの終点および第２と部分ルートのスタート点としての少なくとも１つの引き継ぎ点を求める。
2008510152.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの部分ルートに分けられる全体ルートを計算して、スタート地点から目的地点までナビゲーションする方法であって、
前記の部分ルートのうち、少なくとも１つの部分ルートを移動式のナビゲーションクライアントに計算し、また少なくとも１つの別の部分ルートを固定式の中央のルートサーバにおいて計算する形式の方法において、
結果的に得られる全体ルートに依存して、第１の部分ルートの終点および第２の部分ルートのスタート点としての少なくとも１つの引き継ぎ点を求めることを特徴とする、
スタート地点から目的地点までナビゲーションする方法。
【請求項２】
−  目的地点までの全体ルートがローカルでは計算できないことを識別するステップと；
−  移動式のナビゲーションクライアントから固定のルートサーバに目的地点を伝達するステップと；
−  目的地点リストを移動式のナビゲーションクライアントに伝達するステップと；
−  ナビゲーションクライアントにてユーザにより、１つの目的地点を確認するステップと、
−  少なくとも１つの引き継ぎ点を求めるステップと；
−  当該引き継ぎ点をルートサーバに伝達するステップと；
−  選択した引き継ぎ点から目的地点までの各部分ルートを固定式のルートサーバにおいて計算するステップと；
−  計算した各部分ルートを移動式のナビゲーションクライアントに伝達するステップ通知するステップとを有する、
請求項１に記載の方法。
【請求項３】
引き継ぎ点として、ローカルに計算可能な部分ルート上の点であって、目的地点までの地理的な距離が最も短い点を選択する、
請求項２に記載の方法。
【請求項４】
引き継ぎ点として、ローカルに計算可能な部分ルート上の点であって、目的地までの地理的な距離が最も短い前記部分ルート上の点とスタート地点との間にある点を選択する、
請求項２に記載の方法。
【請求項５】
−  ローカルに計算可能な部分ルート上の点であって、目的地点との地理的な距離が最も短くかつ部分ルート上にある点とスタート地との間にある複数の点をあらかじめ選出し、
−  各部分ルートを計算し、また部分ルート毎に区間長および時間の長さを計算し；
−  前記のあらかじめ選出した点のうちの１点を引き継ぎ点として選択して、当該の部分ルートから組み合わされる全体ルートにより、区間長および／または走行時間を考慮した最適な全体ルートが得られるようにした、
請求項２に記載の方法。
【請求項６】
−  ローカルに計算される点であって、目的地点に対してあらかじめ定めた最大の地理的な距離を有する複数の点をあらかじめ選出し；
−  各部分ルートを計算し、また部分ルート毎に区間長および時間の長さを計算し；
−  前記のあらかじめ選出した点のうちの１点を引き継ぎ点として選択して、当該の部分ルートから組み合わされる全体ルートにより、区間長および／または走行時間を考慮した最適な全体ルートが得られるようにした、
請求項２に記載の方法。
【請求項７】
前記のあらかじめ選出される点は、すでに存在する交差点ないしは分岐点に位置している、
請求項３から６までのいずれか１項に記載の方法。
【請求項８】
前記のあらかじめ選出される点は、既存の交差点ないしは分岐点または交差点の間のほぼ中央に位置している、
請求項３から６までのいずれか１項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも２つの部分ルートに分けられる全体ルートを計算して、スタート地点から目的地点までナビゲーションする方法に関する。ここではこれらの部分ルートのうち、少なくとも１つの部分ルートを移動式のナビゲーションクライアントにおいてローカルに計算し、また少なくとも１つの別の部分ルートを固定式の中央のルートサーバにおいて計算する。
【０００２】
ナビゲーションシステムはここ数年間で広く普及している。現在では殊に自立形のナビゲーションシステムが広く使用されており、これは独立して動作しまたそれ自体でルート計算を行う。これらのナビゲーションシステムは、ナビゲーションの対象となる移動手段、例えば自動車、飛行機または船舶に設けられており、したがって移動式である。
【０００３】
さらに、サーバを有する固定式の中央ユニットによってルートを計算するナビゲーションシステムが公知である。この際にナビゲーションの対象となる移動手段は、例えば移動無線などを介してセンタと通信を行う。上記の移動手段からは、最新の位置データと設定目的地がセンタに送信され、このセンタは、これに基づいてルートを計算して、完全に計算したルートを上記の移動手段に伝送するのである。
【０００４】
さらにこれらの２つの方法の組み合わせ、いわゆるハイブリッドナビゲーションも公知であり、ここでは分散されたナビゲーションクライアントの要求に応じてルート計算が固定式のルートサーバによって行われ、この計算したルートが各ナビゲーションクライアントに伝達される。しかしながらこのナビゲーションクライアントは、独立したルート計算にも適しているのである。
【０００５】
例えば、EP 1 141 910 B1には、ナビゲーションシステムの内部目的地ガイドアルゴリズムにより、内部で計算したルート部分に基づいて目的地ガイドが行われるか、または外部目的地ガイドアルゴリズムにより、外部で計算したルート部分に基づいて目的地ガイドが行われるナビゲーション方法が記載されている。
【０００６】
しかしながらこのようなハイブリッド方式、すなわち内部および外部のルート計算の組み合わせ方式では、新たに計算すべきルートが、完全に互いに独立して計算された２つ部分区間ないかは部分ルートに必然的に分解されてしまうという重大な欠点を有するのである。この場合に組み合わされる全体ルートはふつう、実際に探し出そうとしている最適全体ルートを表さない。それはこれらの部分ルートは、それぞれ不完全で互いに異なるデータバンクに基づいて計算されたものだからである。
【０００７】
このような背景の元で本発明の課題は、冒頭に述べた形式のナビゲーション方法を改善することである。
【０００８】
この課題を解決するため、本発明では、結果的に得られる全体ルートに依存して、第１の部分ルートの終点および第２部分ルートのスタート点としての少なくとも１つの引き継ぎ点（Uebergabepunkt）を求める。
【０００９】
上記の引き継ぎ点を決定するナビゲーションシステム、すなわち、移動式のナビゲーションクライアントまたは固定式のルートサーバのいずれかが、この引き継ぎ点をそれぞれ単にそれ自体のデータバンクに基づいて求めるのでなく、むしろ２つのシステムをベースにして全体として得られた情報に基づいて求めるのである。ルート計算のために互いに通信する２つのシステムを用いることによって、公知のハイブリッドナビゲーション方法に比較して、走行時間および／または走行距離について一層最適なルートの計算が可能になる。
【００１０】
本発明の方法の有利な実施例はつぎのステップを有する。すなわち、
−  目的地点までの全体ルートがローカルでは計算できないことを識別するステップ；
−  移動式のナビゲーションクライアントから固定のルートサーバに目的地点を伝達するステップ；
−  目的地点リストを移動式のナビゲーションクライアントに伝達するステップ；
−  ナビゲーションクライアントにおいてユーザにより、１つの目的地点を確認するステップ；
−  少なくとも１つの引き継ぎ点を求めるステップ；
−  この引き継ぎ点をルートサーバに伝達するステップ；
−  選択した引き継ぎ点から目的地点までの各部分ルートを固定のルートサーバにおいて計算するステップ；
−  計算した各部分ルートを移動式のナビゲーションクライアントに伝達するステップを有する。
【００１１】
本発明の方法の有利な実施形態では、引き継ぎ点として、ローカルに計算可能な部分ルート上の点であって目的地点までの地理的な距離が最も短い点を選択する。ここでこの選択は、一般的には一層完全な地図資料を利用可能な固定式のルートサーバによって行うことも可能である。しかしながら、固定式のルートサーバによって設定目的地の座標が伝達された後、移動式のナビゲーションクライアントにより、上記の引き継ぎ点を求めることも同様に可能である。
【００１２】
本発明の方法の択一的かつ有利な実施形態では、引き継ぎ点として、ローカルに計算可能な部分ルート上の点であって、目的地点までの地理的な距離が最も短い、部分ルート上の点とスタート地点と間にある点を選択する。一般的には計算した走行距離は、直線距離ではないため、このようにした求めた引き継ぎ点により、一層区間長の短い全体ルートが得られることがある。
【００１３】
本発明の方法の有利な実施形態は以下のステップを有する。すなわち、
−  ローカルに計算可能な部分ルート上の点であって、目的地点との地理的な距離が最も短くかつ部分ルート上にある点とスタート地点との間にある複数の点をあらかじめ選出するステップ；
−  各部分ルートを計算し、また部分ルート毎に区間長および時間の長さを計算するステップ；
−  あらかじめ選出した点のうちの１点を引き継ぎ点として選択して、上記の部分ルートから組み合わされる全体ルートにより、区間長および／または走行時間を考慮した最適な全体ルートが得られるようにするステップとを有する。
【００１４】
本発明の方法の有利な実施形態は以下のステップを有する。すなわち、
−  ローカルに計算可能な点であって、目的地点に対してあらかじめ定めた最大の地理的な距離を有する複数の点をあらかじめ選出するステップ；
−  各部分ルートを計算し、また部分ルート毎に区間長および時間の長さを計算するステップ；
−  あらかじめ選出した点のうちの１点を引き継ぎ点として選択して、上記の部分ルートから組み合わされる全体ルートにより、区間長および／または走行時間を考慮した最適な全体ルートが得られるようにするステップとを有する。
【００１５】
上記の最適な全体ルートにより、ユーザによって設定されたルートオプション（例えば１００％の速さ＋０％短さ〜０％の速さ＋１００％の短さ）が考慮される。
【００１６】
この実施形態では、あらかじめの選択の際に設定目的地の周りに仮想的な半径が引かれ、また形成された円内のすべての引き継ぎ点候補が考慮される。ここでは、従来のハイブリッド形ナビゲーションシステムの移動式に計算されたルートにまたはその近くに、引き継ぎ点候補があるか否かは考慮しないままにされる。これによって、見かけ上は迂回であるが、走行すべき道路および／または考慮した最新の交通状況に基づいて最適な択一ルートである全体ルートを計算することも可能である。
【００１７】
有利な発展形態では、上記のあらかじめ選出した点は、既存の交差点または分岐点に位置している。これによって上記のあらかじめの選出はやや制限されるが、計算コストが低減され、ひいては一層高速に結果が得られる。
【００１８】
１発展形態において択一的に、上記のあらかじめ選出される点は既存の交差点ないしは分岐点またはこれらの交差点のほぼ中央に位置することが可能である。以下では添付の図面に基づき、例示によって本発明の方法を詳しく説明する。図面において、
図１ａは、引き継ぎ点を決定する第１の例を示しており、
図１ｂは、固定式のルートサーバによって計算した部分ルートを付加的に有する、図１ａの部分地図を示しており、
図２は、引き継ぎ点を決定する第２の例を示しており、
図３ａは、選択された複数の点を有する第３の例を示しており、
図３ｂは、それぞれ計算した部分ルートを付加的に有する、図３ａの部分地図を示しており、
図４ａは、選択された複数の点を有する第４の例を示しており、
図４ｂは、それぞれ新たに計算した部分ルートを付加的に有する、図４ａの部分地図を示している。
【００１９】
移動式のナビゲーションクライアントは、カバーされた地方が限られているまたは地図精度が限られているデジタル化地図およびルート計算のためのアルゴリズムを有する。さらにこのシステムは、中央のルートサーバに対して通信コネクションを確立することができる。このルートサーバは、広範囲にわたる地図データ、理想的には１００％のカバーレンジを有しており、また解像度が高くかつアップデートの度合いが高い。最後にこのルートサーバは、ルートを計算するためのアルゴリズムを有する。
【００２０】
移動式のナビゲーションクライアントが配置されている移動手段において移動中のユーザが、この移動式のナビゲーションクライアントの地図データにない目的地を所望すると、この目的地は移動無線コネクションを介して中央のルートサーバに問い合わされる。このルートサーバに利用可能なデータバンクに基づいてこのルートサーバによってこの目的地が識別されると、このことは移動式のナビゲーションクライアントに通知される。例えば、この移動式のナビゲーションクライアントは、ルートサーバからナビゲーションクライアントに伝送されテキストで表される目的地に基づいて目的地を確認した後、設定目的地をテキスト表示で伝達する。また固定式のルート計画部によって座標値が戻される。
【００２１】
スタート地点と目的地点との間の全体ルートは、少なくとも２つの部分ルートに分割され、ここで引き継ぎ点までの第１の部分は移動式のナビゲーションクライアントによって、または引き継ぎ点に続く第２の部分は中央のルートサーバによって計算される。全体ルートの第２の部分は、上述の移動無線区間を介して移動式のナビゲーションクライアントに伝送される。ユーザは、スタート地点から引き継ぎ点まで移動式のナビゲーションクライアントによって計算した第１の部分ルートに沿ってガイドされる。引き継ぎ点において移動式のナビゲーションクライアントは、中央のルートサーバによって計算した第２の部分ルートに切り替わる。
【００２２】
引き継ぎ点の有利な決定は、本発明によるナビゲーション方法を効果的に実施するために重要である。図１ａおよびｂに基づいて、引き継ぎ点を決定する第１の例を示す。図１には部分地図１が示されており、ここにはさまざまな道路２の経過が示されている。ルート計算に対し、参照符号３によってスタート地点がまた参照符号４によって目的地点が示されている。スタート地点３が移動式のナビゲーションクライアントに既知の道路上またはそのそばにあるのに対して、目的地４は、移動式のナビゲーションクライアントに利用可能な地図データの外にある。
【００２３】
移動式の通信システムと中央のルートサーバとの間の通信に基づいて、この移動式のナビゲーションクライアントには目的地の座標が既知であるが、これは、走行可能な完全なルートを算出することができない。目的地４の座標が既知であるため、移動式のナビゲーションクライアントは、利用可能な地図データにおいて点５を決定し、この点５を引き継ぎ点として決定する。この例において決定は、つぎのような前提に基づいて行われる。すなわち、破線６によって示された引き継ぎ点５と目的地４との間の直線距離が、目的地４と、移動式のナビゲーションクライアントに利用可能な地図データのすべての点との間の最小の直線距離であるという前提に基づいて行われるのである。
【００２４】
移動式のナビゲーションクライアントによって引き継ぎ点５が決定された後、この点５は、移動無線コネクションを介して中央のルートサーバに通知される。ここでこの中央のルートサーバは、引き継ぎ点５と目的地４との間の部分ルートを計算する。この部分ルートは、図１ｂにおいて参照符号７で示されている。この方法は、移動式のナビゲーションクライアントの地図データにだけアクセスして引き継ぎ点が決定されるため、簡単に実行できるが、部分ルート７の経過はふつうの場合に上記の直線距離に等しくないため、ユーザは迂回路を走行することがあり得る。これは図１ｂに示した通りである。
【００２５】
図２には引き継ぎ点を決定する別の例が示されている。図２にも図１から既知の道路経過２を有する部分地図１が示されている。スタート地点３および目的地点４も同じである。引き継ぎ箇所として、目的地４への最小の直線距離６を有する点５が決定されるのではなく、スタート地点３と点５との間のルート上にある点８が決定される。引き継ぎ点８は、目的地４に対する直線距離８が一層大きいが、ルートの全体距離は小さくなり得る。
【００２６】
この際に限界条件を定めて、引き継ぎ点としてスタート点３が選択されることを阻止しなければならない。それはスタート地点３と目的地点４との間の最小の距離は、直接の直線距離だからである。限界条件として考えられるのは、例えば、直線距離９が、最小の直線距離６の２倍または３倍の値よりも大きくなってはならないという条件である。別の限界条件とは、スタート地点３と引き継ぎ点８との間の部分ルートの区間距離が、スタート地点３と引き継ぎ点５との間の部分ルートの区間距離の半分よりも大きくなければならないという条件にすることが可能である。図２からわかるようにこの例においてスタート地点３と目的地点４との間の（部分ルート７ｂによる）全体ルートは、図１ｂに示した全体ルートよりも短い。
【００２７】
図３ａおよび３ｂに基づいて説明する実施例では、移動式のナビゲーションクライアントにより、このナビゲーションクライアントに利用可能な地図データから得られる事前の選択肢として複数の点１０〜１４が選出される。これらの点は、引き継ぎ点候補として中央のルートサーバに伝達される。中央のルートサーバはつぎに引き継ぎ点１０〜１４毎に部分ルート１５〜１８を計算する。さらに部分ルート１５〜１８毎に走行時間および区間長を計算して、移動式のナビゲーションクライアントに通知する。移動式のナビゲーションクライアントはここですべての全体ルートに対して、全体走行時間ないしは全体走行距離を計算し、引き続いて最適な全体ルートを求める。
【００２８】
図４ａでは引き継ぎ点候補２０〜２６が移動式のナビゲーションクライアントによって選出される。選出されたすべての点は、目的地４からあらかじめ定めた半径２７内にある。点２０〜２６を選出するための別の条件は、これらのすべての引き継ぎ点候補が、交差点または２つの交差点間のほぼ中央にあるという条件にすることが可能である。図３ａおよび３ｂの例に基づいてすでに説明したように、すべての引き継ぎ点候補に対して、図４ｂに示したように部分ルート２８を中央のルートサーバによって計算し、引き続いてナビゲーションクライアントに通知する。このナビゲーションクライアントは、全体ルートの走行時間ないしは走行距離を考慮して、最適な全体ルートを選択し、この選択された全体ルートに基づいてユーザをスタート地点３から目的地点４まで案内する。
【図面の簡単な説明】
【００２９】
【図１ａ】引き継ぎ点を決定する第１の例を示す図である。
【図１ｂ】固定式のルートサーバによって計算した部分ルートを付加的に有する、図１ａの部分地図である。
【図２】引き継ぎ点を決定する第２の例を示す図である。
【図３ａ】選出された複数の点を有する第３の例を示す図である。
【図３ｂ】それぞれ計算した部分ルートを付加的に有する、図３ａの部分地図である。
【図４ａ】選出された複数の点を有する第４の例を示す図である。
【図４ｂ】それぞれ新たに計算した部分ルートを付加的に有する、図４ａの部分地図である。
【図１ａ】
2008510152.tif 000003
【図１ｂ】
2008510152.tif 000004
【図２】
2008510152.tif 000005
【図３ａ】
2008510152.tif 000006
【図３ｂ】
2008510152.tif 000007
【図４ａ】
2008510152.tif 000008
【図４ｂ】
2008510152.tif 000009
【国際調査報告】
2008510152.tif 000010
2008510152.tif 000011
2008510152.tif 000012
2008510152.tif 000013