(57)【要約】本発明は、自動車を目的地に動的にナビゲートする方法に関し、この方法により、車載装置が無線により交通センタから運転目的地までのルート関連データを要求し、その時に交通センタは、自動車の運転目的地までのルートを計算しかつ記憶し、無線により車載装置にルート関連データを送信する。本発明によれば、計算されたルートには位置しない、少なくとも１カ所の交通渋滞が交通センタ内で監視され、計算されたルートは、この交通渋滞が緩和した際、少なくとも該ルートの一部が再計算される。
2005524061.tif 000002
【特許請求の範囲】
【請求項１】
車載装置が無線により交通管理センタから目的地までのルート関連データを要求し、前記交通管理センタが続いて自動車の前記目的地までのルートを計算し、該ルートを記憶し、ルート関連データを無線により前記車載装置に送信する、自動車を動的にナビゲートする方法であって、
前記計算されたルート上に位置しない少なくとも１カ所の交通渋滞が、前記交通管理センタ内で監視され、前記交通渋滞が減少すると前記計算されたルートが少なくとも部分的に再計算されることを特徴とする方法。
【請求項２】
前記計算されたルート周辺の予め画定可能な領域に位置する交通渋滞の全てが、監視されることを特徴とする請求項１に記載の方法。
【請求項３】
前記計算されたルートと比較して、前記再計算されたルートに変化がある場合、前記交通管理センタは情報を前記車載装置に送信することを特徴とする請求項１あるいは２に記載の方法。
【請求項４】
前記交通管理センタは、前記ルートの変更の位置、及び計算されたルートの変更の時間を、前記車載装置に追加的に送信することを特徴とする請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記計算されたルート上に位置しない交通渋滞が予め画定可能な程度を超えて減少する場合に限り、前記ルートは、再計算されることを特徴とする請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記ルート関連データは、交通データの形態であることを特徴とする請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記ルート関連データは、ルートデータの形態であることを特徴とする請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記計算されたルートの経過に関する情報は、前記車載装置と前記交通管理センタとの間で無線により追加的に送信されることを特徴とする請求項６に記載の方法。
【請求項９】
前記予め画定可能な領域に関する情報は、前記車載装置と前記交通管理センタとの間で無線により追加的に送信されることを特徴とする請求項２〜６あるいは８のいずれか一項に記載の方法。
【請求項１０】
最小速度を想定して、前記自動車がまだ通過していない前記計算されたルートの少なくとも一部が、再計算されることを特徴とする請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記再計算は、前記自動車の３種類の異なる平均速度を使用して３回実行されることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記交通渋滞又は個々の交通渋滞は、少なくとも、前記自動車が前記目的地に到達するのに要するであろうと、前記交通管理センタにおいて推定される期間、監視されることを特徴とする請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
自動車側において決定される前記目的地への到着時間は、前記車載装置から前記交通管理センタに無線により追加的に送信されることを特徴とする請求項１〜１２のいずれか一項に記載の方法。
【請求項１４】
監視されるべきである交通渋滞を決定するために、前記目的地へのルートＲ１が交通渋滞を考慮に入れずに計算される第１のステップと、
前記目的地へのルートＲＡが前記交通渋滞の全てを考慮に入れて計算される第２のステップと、
前記ルートＲ１上の前記交通渋滞の全てが監視され、すでに監視されている前記交通渋滞だけを考慮に入れて前記目的地へのルートＲ２が計算される第３のステップと、
以前に計算された前記ルートＲｉ、（ｉ≧２）上の前記交通渋滞の全てが監視され、前記監視された交通渋滞を考慮に入れて前記目的地へのルートＲｉ＋１が計算される第４のステップと、
前記ルートＲｉが前記ルートＲＡに対応するまで前記第４のステップが繰り返され、前記ルートＲＡ上に存在し得る前記交通渋滞の全ては、１つ前のステップにおいてすでに監視されていることを特徴とする請求項１〜１３のいずれか一項に記載の方法。
【請求項１５】
計算されるべき前記ルートＲｉの数は、予め画定可能な最大値ｎまでに制限されることを特徴とする請求項１４に記載の方法。
【請求項１６】
さらに別のルートＲｉが計算されることを特徴とする請求項１５に記載の方法。
【請求項１７】
コンピュータプログラムがコンピュータで実行される場合の、請求項１〜１６のいずれかに記載のステップの全てを実行するためのプログラムコード手段を備えたコンピュータプログラム。
【請求項１８】
コンピュータプログラムプロダクトがコンピュータで実行される場合の、請求項１〜１６のいずれかに記載の方法を実行するためにコンピュータ読み取り可能なデータキャリヤに記憶されるプログラムコード手段を備えたコンピュータプログラムプロダクト。
【請求項１９】
少なくとも１つの車載装置と交通管理センタとから構成され、
−前記車載装置がルート関連データを無線により要求するための受信手段であって、前記ルート関連データが自動車の目的地に関連する受信手段と、
−自動車の目的地までのルートを計算するための計算手段と、
−前記計算されたルートを記憶する記憶手段と、
−前記車載装置へ前記ルート関連データを無線により送信のための送信手段と、を具備する、自動車を動的にナビゲートするシステムであって、
前記計算されたルート上に位置しない少なくとも１カ所の交通渋滞を監視する手段が、追加的に提供されることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、請求項１の前文に記載の自動車を動的にナビゲートする方法、及び請求項１９の前文に記載の自動車を動的にナビゲートするシステムに関する。
【背景技術】
【０００２】
自動車が動的にナビゲートされるとき、現在の交通状況、及び目的地の途中で起こることが予測される未来の交通状況が、目的地へのルートの選択の際に考慮に入れられる。このような状況において、一方では、目的地へのルートが車載装置内で決定される「オンボード方式」と称されるものが採用される。他方では、目的地へのルートが交通管理センタ内で計算される「オフボード方式」が採用される。オンボード方式では、ルートを決定するために使用される交通状況を無線により車載装置が利用できるようになり、オフボード方式では、交通状況は、交通管理センタ内に記憶され、計算されたルートが無線により車載装置に送信される。車載装置が無線により利用できるようになり、交通状況−例えば交通渋滞−に関連するデータ、又は計算されたルートは、以下では、組合せてルート関連データと称される。
【０００３】
特許文献１は、ルート関連データが交通管理センタから車載装置に無線により送信され、自動車の目的地までの道程のシミュレーションが、交通管理センタ及び／又は車載装置内でリアルタイムで行うことを提案している。
【０００４】
特許文献２は、ルート関連データを受信するように構成される車載装置を開示している。自動車の目的値及び出発地点が予め定められると、第１のルートがルート関連データを考慮せず決定される。さらに、受信したルート関連データが第１のルートに関連する限り、第２のルートが、受信したルート関連データを考慮に入れて決定される。第２のルートで予測される所要時間が第１のルートで予測される所要時間よりも短い場合、選択情報が運転者に発せられる。この選択情報は、第１のルートに代わるルートとして第２のルートを提供する。
【０００５】
特許文献３は、特許文献２の主題を発展させる。これに関して、特許文献３は、受信したルート関連データが特定の第１のルートに関連する場合、車載装置が代わりのルートのために複数のルートを決定する動作を実行することを提案している。この状況において、代わりのルートは、計算された第１のルートを離れることができる複数の分岐点に対し決定され、対応する選択情報が運転者に発せられる。
【０００６】
関連技術を開示する特許文献４は、車載装置が交通管理センタからルート関連データを無線により受信する方法を開示している。交通渋滞が交通管理センタ内の計算されたルートで検出される場合、交通管理センタは、新しいルートを獲得し、この新しいルートを車載装置に無線により送信する。
【０００７】
【特許文献１】独国特許出願公開第１９５４７５７４  Ａ１号明細書
【特許文献２】欧州特許出願公開第０８３８７９７  Ａ１号明細書
【特許文献３】独国特許出願公開第１９９５６１０８  Ａ１号明細書
【特許文献４】欧州特許第０９７４１３７  Ｂ１号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、自動車に関連する交通渋滞を考慮に入れ、コスト効果に優れた、最適なルートを常に確保する、自動車を動的にナビゲートする汎用的な方法を提案することである。本発明の目的はまた、上記方法に対応するシステムを提案することでもある。
【課題を解決するための手段】
【０００９】
本発明は、請求項１の特徴による方法、及び請求項１９の特徴によるシステムに関し、この目的を達成する。従属請求項は、好ましい実施形態や発展形態に関する。
【００１０】
本発明によれば、計算されたルート上には位置しない、少なくとも１カ所の渋滞が、交通管理センタ内で監視され、交通渋滞が減少すると、計算されたルートは少なくとも部分的に再計算される。つまり、本発明の装置では、例えば、計算されたルートに代わるルートがあり、さらにその代わりのルート上に交通渋滞が位置しなかった場合には、その代わりのルートが「より良い」ルートとされる。この状況において、「より良い」とは、例えば、より短い又はよりコスト効果の優れたものであることである。それで、交通渋滞が減少、例えば解消される場合、そのルートは少なくとも部分的に再計算される。その結果、自動車にとって「最良の」ルートとなるルートが本発明により常に計算される。
【００１１】
計算されたルートを監視して交通渋滞がそこで起こっているかを判断することは公知であるが、ここでは、交通渋滞が、計算されたルート上に位置しない場合が考えられる。本発明によれば、このような交通渋滞が減少する場合に、新しいルートが、自動車に対して計算される。というのは、例えば、このような交通渋滞が「悪化する」場合には、ルートを再計算して計算されたルート以外のルートを持ってくることは、いかなる状況にあってもないからである。さらに、対応する監視されるべき交通渋滞を選択することにより、交通渋滞の全てが監視されるわけではないが、代わりに「関連する」交通渋滞が監視されることが保証される。交通渋滞は、例えば、「関連する」ものであり、したがって、この交通渋滞が計算されたルートに取って代わる可能なルート上に位置するかどうか監視される。その結果、本発明は、コストに関して最適化される交通管理センタを利用して、自動車を動的にナビゲートする手順を確保する。これは、通常では出費が発生するルート関連データの送信が、たとえ交通状況が変化しても実行されず、監視される交通渋滞が減少する場合にのみ実行されるからである。本発明による方法は、この状況で汎用的にオンボードナビゲーション及びオフボードナビゲーションの両方、ならびにハイブリッド形態（ハイブリッドナビゲーション）に対し使用できる。さらに、車載装置及び交通管理センタ内での計算作業は、たとえ交通状況が変化したときでもルートの再決定又は再計算が不要となるということで、オンボードナビゲーション及びオフボードナビゲーションの両方に対し、最小限に抑えられる。このような再決定又は再計算は、監視される交通渋滞が減少するときに限り必要となる。本発明による方法は、したがって、一般的に、コストに関し最適化される手順を保証する。
【００１２】
計算されたルート周辺の予め画定可能な領域内に位置する全ての交通渋滞が監視される場合には、監視されるべきであって上記計算されたルート上に位置しない交通渋滞が、計算により容易に選択される。上記計算されたルート周辺の予め画定可能な領域は、例えば、このルート周辺の交通路の形態であっても良い。
【００１３】
１つの特に好ましい実施形態において、計算されたルートと比較して再計算されたルートに変化があると、情報は、交通管理センタによって車載装置に無線により送信される。その結果、車載装置は、予想される変化について直ちに連絡され、自動車の運転者は、例えば、続いて交通管理センタからルート関連データを無線で要求できる。この状況において、計算されたルートは、交通管理センタ内で記憶され、上記自動車が移動しているルートが常に交通管理センタ内で把握されているので、上記自動車に個別に役立つように対応することが可能である。車載装置及び／又は自動車の運転者自身は、この自動車の正確な場所を知っているので、新しいルート関連データを交通管理センタに要求すべきであるかどうかについての目標とする決定が、可能である。ゆえに、通常ではコストが発生するルート関連データの送信は、それが自動車にとって好ましい場合に限り、自動車側で開始されるが、上記送信は、再計算されたルートが変化したときでも開始はされない。この状況において、交通管理センタによって無線により送信される情報はまた、新たに計算されたルートが、既に計算されたルートと比較して、利点、例えば、時間的利点を提供するか、さらにこの利点がどれだけ大きいかを示すデータを包含できる。
【００１４】
交通管理センタが、ルート関連データに加えて、少なくとも１つのルート変更の位置と少なくとも１つの変更時間とを、計算されたルートと共に、車載装置に送信するならば好都合である。例えば、ルートが計算されると、未来の交通状況がその自動車の道程の予想コースを使用して推測される。その自動車が、例えば、途中で停止するので、推定されたものと比べて道程の異なるコースをとる場合、推測されるべき交通状況は変わってしまう。このことは、次にもう１つのルートを計算させることとなる。計算されたルートの予測される変更の位置と時間とが、車載装置内にある場合、通常ではコストの発生となる新たなルート関連データを、交通管理センタから要求すべきであるかどうかに関する簡単な（自動的でもある）決定が、自動車側で可能となる。この状況においては、計算されたルートが「適用できる」ことから始まる、「開始時間」、及び／又は計算されたルートがもはや「適用できない」ことから始まる、「終了時間」が、変更の時間として提供される。上記に加えて又は代わりに、計算されたルート上の自動車の道程の−交通管理センタ内で想定された−コースについての情報を車載装置に送信するように、交通管理センタを備えることが可能である。道程の予想コースは、例えば、予想される平均自動車速度としてマップ化される。同様に、ルート変更の位置から始まる新たに計算されたルートに関するルート関連データを、追加的に車載装置に送信するように交通管理センタを備えることが可能である。
【００１５】
計算されたルート上に位置しない交通渋滞が、予め画定可能な程度よりも減少する場合にのみ、上記ルートが再計算されるようにすると好都合である。このようなしきい値を使用することで、ルートを再計算する頻度が、精度を比較的大きく低下させることなく、減少する。
【００１６】
本発明の好ましい一実施形態において、ルート関連データは、交通データの形態である。これは、オンボードナビゲーションシステムとしての本発明の実施形態に相当する。この状況において、交通管理センタは、交通データを車載装置に無線により送信し、車載装置は、受信した交通データを使用して、ルートを決定するためにこの交通データを使用することによって自動車を動的にナビゲートする。例えば、自動車に「関連する」もの、すなわち交通管理センタ内で監視される交通渋滞は、交通データとして送信される。この状況においては、交通管理センタ内で自動車に対し個別に集められるように交通データを備えることが可能である。このような「個別化した」交通データは、例えば、ルート関連データが自動車側から要求されると、この自動車の位置を送信することによって、得られる。特に、交通管理センタ内で再計算されるルートが、計算されたルートと比較して変化するとき、情報が交通管理センタから車載装置に無線により送信される場合には、最新の個別化された交通データがリアルタイムの条件下で車載装置によって常に要求できる。
【００１７】
本発明の他の好ましい実施形態において、ルート関連データは、ルートデータの形態である。これは、オフボードナビゲーションシステムとしての本発明の実施形態に相当する。この状況においては、自動車のルートは、例えば、監視された交通渋滞を使用して交通管理センタ内で計算され、次に、この計算されたルートが無線により車載装置で利用できるようになる。
【００１８】
オンボードナビゲーションシステムの場合、すなわち、ルート関連データが交通データの形態であるとき、計算された又は決定されたルートのコースに関する情報が、車載装置と交通管理センタとの間で無線により追加的に送信されることが提案されると、好都合である。例えば、経路を指定するポイントと称されるもの、すなわち、計算された又は決定されたルート上に位置する「基準ポイント」が、交通管理センタ及び車載装置が同じルートを計算又は決定することを保証するために使用される。これを実行するために、車載装置又は交通管理センタは、そのルート上にある適切なポイントを選択し、例えばルート関連データのそれぞれの要求又は送信と共に、これらのポイントを送信する。さらに、車載装置内で決定されたルートが、交通管理センタ内で計算されたルートと一致しない場合には、一致する対応の情報が無線により送信されるように、規定することが可能である。この一致については、例えば車載装置において、交通管理センタ内で計算されたルートのコースに関する情報がこのルートを再構成するために使用され、車載装置自体で決定されるルートと比較されるように、ここではチェックされる。このことにより、車載装置内で決定されたルートと交通管理センタ内で計算されたルートとが、たとえそれぞれ異なる整合及び／又は経路の指定方法及び／又はデータベース（デジタル道路地図）が使用されても、一致することが保証される。上記に代えて又は加えて、車載装置内で計算されたルートのコースに関する情報を使用してこのルートを再構成し、それを交通管理センタ自体で決定されたルートと比較する手法が、交通管理センタ内にはある。この状況においては、このような再構成されたルートが、交通管理センタ自体で決定されたルートと一致しない場合には、その再構成されたルートを交通管理センタ内で（例えば監視されるべき交通渋滞を選択するために）使用することも可能である。
【００１９】
オンボードナビゲーションの場合、予め画定可能な領域に関する情報が、車載装置と交通管理センタとの間で追加的に送信されることも好都合である。例えば、車載装置は、交通管理センタに、特定の予め画定可能な領域を問い合わせることができ、したがって、この領域内に位置した交通渋滞について連絡を受けるか、又は交通管理センタが予め画定可能な領域の大きさについて車載装置に連絡する。このことにより、自動車が、最低限の可能なコストで、最大限に可能な方法で、機能することが確実に保証される。結果的に、例えば、自動車がそのルートを離れるとき、新しい目的地が選択されるとき、又は自動車が中間の目的地に向かうとき、新しいルートの一部が予め画定可能な領域の外部に、すなわちルート関連データのない範囲にある場合に限り、新しい交通データが、交通管理センタに要求される。この要求は、運転者により手動で、又は自動的に行われる。つまり、このようにして車載装置における予め画定可能な領域に関する情報により、自動車が予め画定可能な領域内部にあるルート内で変更するとき、新しいルートのためのルート関連データが車載装置内にも存在することが保証される。
【００２０】
交通管理センタ内でのルートの再計算は、最小限の速度を想定して、自動車が未だ通過していない計算されたルートの一部が、再計算される場合に限り、単純化される。このような最小限の速度は、例えば、対応するデータベースから読み出されても良い。ルートについての３つの再計算が、そのルートでの自動車の３種類の異なる平均速度を使用して実行されると特に好都合である。これらの３種類の平均速度は、統計的に、最低速度の運転スタイル、最高速度の運転スタイル、及び平均速度の運転スタイルに対応する。このような統計的なデータは、例えば、移動時間情報と共に記憶された、履歴としての、出発地−目的地の関係から得られる。このことは、自動車の正確な位置が交通管理センタ内では未知であるという事実を考慮に入れている。これらの３つの再計算により、自動車が、新たに計算されたルートに変更するために予め計算されたルートを離れることができる「決定ポイント」を、最適な方法で考慮に入れることが特に可能となる。３種類の異なる平均速度を使用することによって、自動車の位置に関する実用的な適用状況の全てに対応できる。例えば、新たに計算されたルートが、既に計算されたルートと比較して変化する場合、交通管理センタは、無線により、決定ポイントを含む情報を車載装置に送信する。自動車の現在位置を決定ポイントと比較することによって、自動車にとって最良である、すなわち、そのルートに最も近い決定ポイントを選択することが可能となる。
【００２１】
少なくとも、交通管理センタにおいて、自動車が目的地に到達するのに要するであろうと推測される時間のために、所定の交通渋滞又は個々の交通渋滞が監視されると好都合であると提案されている。このことにより、特に簡単に、自動車が、全道程中、最適に機能することが保証される。自動車が目的地に到達するのに要するであろうと推測される時間は、例えば、最小限の速度を使用して推測される。
【００２２】
自動車側で決定される、例えば推定される目的地への到着時間は、車載装置から交通管理センタに無線により追加的に送信されると好都合である。このことにより、所定の交通渋滞又は個々の交通渋滞が交通管理センタ内で監視される時間を、確実に決定することが可能となる。例えば、この目的のため、車載装置は、対応する情報を交通管理センタに、ルート関連データの要求と共に送信する。目的地への到着時間に達すると、交通管理センタ内での、所定の交通渋滞又は個々の交通渋滞の監視は、終了する。さらに、目的地への到着時間は、自動車内にも記憶される。次に、目的地への到着時間が特定の時間間隔で自動車内において更新される場合、更新された目的地への到着時間と記憶された目的地への到着時間との間の予め画定可能な偏差を超えると、更新された目的地への到着時間が、交通管理センタに送信される。その結果、所定の交通渋滞又は個々の交通渋滞が交通管理センタ内で監視される時間が、自動車の道程のコースに正確に適合される。このことにより、例えば自動車が、その目的地に到達するために予め画定可能な偏差よりも大きな偏差（例えば、自動車が推測されたよりもゆっくり移動するか若しくは途中の道程で中断する場合）又は小さな偏差（例えば、自動車が推測されたよりも速く移動する場合）を必要とするかを考慮に入れる。上記に代えて又は加えて、そのような偏差が検出されると、自動車の現在位置が車載装置によって交通管理センタに送信されることが規定される。さらに上記に代えて又は加えて、交通管理センタからルート関連データを受信した後、車載装置は、受信確認を交通管理センタに自動的に送信することが規定される。このことにより、自動車がその目的地に到着すると、及び／又はナビゲーションプロセスが中断されると、交通管理センタ内での監視が終了し、その後は、車載装置がこのような受信確認を送信しないことが確実に保証される。車載装置と交通管理センタとの間の無線による回線が短時間利用できない可能性をある程度見込むために、所定の交通渋滞又は個々の交通渋滞の監視が終了する前に、ルート関連データが自動車へ送信された後の所定の時間、この受信確認を待つように、交通管理センタを備えることが可能である。
【００２３】
監視されるべきである交通渋滞を判断するために、第１のステップにおいて目的地へのルートＲ１が交通渋滞を考慮せずに計算され、第２のステップにおいて目的地へのルートＲＡが交通渋滞の全てを考慮に入れて計算され、第３のステップにおいてルートＲ１上の交通渋滞の全てが監視され、そして、すでに監視されている交通渋滞だけを考慮に入れて、目的地へのルートＲ２が計算され、第４のステップにおいて先に計算されたルートＲｉ（ｉ≧２）上の交通渋滞の全てが監視され、そして、この監視された交通渋滞を考慮に入れて、目的地へのルートＲｉ＋１が計算され、この第４のステップは、ルートＲｉがルートＲＡに一致するまで繰り返され、そして、ルートＲＡ上の全ての存在し得る交通渋滞は前のステップですでに監視されていることが、特に好都合である。この手順によって、一方では、再計算が行われる場合に、自動車にとって１つの新しいルートとなるルート上に位置する交通渋滞だけが、判断される。他方では、交通渋滞が減少するか又は無い場合には、ルートの再計算により１つの修正されたルートを与え得る交通渋滞だけが、監視される。したがって、「関連する」ルート（すなわち、代わりのルート）上の「関連する」交通渋滞だけが監視される。この状況において、代わりのルートは、１カ所又はそれ以上の交通渋滞が解消する場合に、その自動車の新しいルートとして計算されるルートである。
【００２４】
第１の利点は、各ステップにおいて、実際に存在する幾つかの交通渋滞を考慮に入れて「最適」であるルートが計算されるという事によりもたらされる。つまり、これらのルートは、監視されていない交通渋滞が解消されていれば最適となろう。このように計算されるルート上の交通渋滞だけが監視されるので、このことが実際、第１の利点となる。第２の利点は、矛盾を証明することによって実証される。１カ所以上の交通渋滞Ｓ１、．．．、Ｓｎが位置し、記載されている方法では監視されなかったルートＲＸがあったと仮定する。さらに、これらの交通渋滞Ｓ１、．．．、Ｓｎが解消された場合、このルートＲＸは、交通渋滞の全てを考慮に入れて計算されたルートＲＡよりも良いと仮定する。重要な要因は、交通渋滞Ｓ１、．．．、Ｓｎが最適なルートの変化を検出するために監視されなければならないかどうかであるので、交通渋滞の全てが完全に解消されているという仮定はまた、全ての他の場合にも当てはまる。１つの交通渋滞が解消することは、交通渋滞が監視されなかった場合未検出のままとなったであろう最も著しい変化である。この仮定によれば、交通渋滞Ｓ１、．．．、Ｓｎは監視されない、したがって、ルートの決定において考慮に入れられない。このことは、ルート計算に関し、交通渋滞の全てが解消された場合に対応する。但し、この状況において、ルートＲｘはルートＲＡよりも良くなり、ルートＲｘはまた、中止の基準に達する前に、最適なルートＲｉとして決定される。但し、この方法によれば、全ての渋滞Ｓ１、．．．、Ｓｎが、監視されるようにマークされ、このことは上記仮定と矛盾する。
【００２５】
通常では、少数の交通渋滞だけしか監視する必要がないので、目的地へのルートを計算する交通管理センタ内の作業は、少量の計算作業しか必要ない。但し、計算作業が増加しすぎるのを確実に防止するために、計算されるルートＲｉの数が、予め画定可能な最大値ｎまでに制限されることが好都合であると提案されている。その結果、最も重要な交通渋滞が、最小限度の計算作業で監視される。
【００２６】
１つの好ましい発展形態は、別のルートＲｉが、例えば、しばらく経って計算されると言う事から得られる。例えば、別のルートＲｉは、交通管理センタへの計算負荷が低いときに計算される。その結果、交通管理センタの過負荷がピークタイムにおいて防止されるが、それでも交通渋滞の全てが監視される。
【００２７】
本発明は、プログラムコード手段を備えたコンピュータプログラムとして実施されるのが好ましく、本発明による方法のそれぞれの実施形態は、それぞれのプログラムがコンピュータで実行される場合に、実行される。
【００２８】
本発明の別の好ましい実施形態は、プログラムコード手段を備えたコンピュータプログラムプロダクトを構成し、プログラムコード手段は、それぞれのプログラムプロダクトがコンピュータで実行される場合に、本発明による方法のそれぞれの実施形態を実施するために、コンピュータ読み出し可能なデータキャリヤに記憶される。
【００２９】
本発明について図面を参考にしてより詳細に以下で説明する。
【発明を実施するための最良の形態】
【００３０】
図１は、出発位置Ｓから目的地Ｚへの動的ナビゲーションの場合の多様な交通渋滞の概略図である。従来、自動車のために計算されたルートＲ上に位置する交通渋滞Ａ、Ｂが監視される。この状況において、上記ルートは、このルート上の交通状況が悪化するとき、すなわち、Ａ及び／若しくはＢが悪化するとき、並びに／又は新しい交通渋滞が生じるとき、再計算され；逆に、計算されたルート上の交通状況が改善するとき、再計算は実行されない。
【００３１】
新規の方法では、計算されたルートＲ上に位置しない「関連する」交通渋滞が、ここでは追加的に監視される。この状況において、「関連する」とは、交通渋滞の減少又は交通渋滞の解消により、もう１つ別のルートが生じることを意味する。図１の交通渋滞１、２、３、４は、計算されたルートＲ上に位置しない。交通渋滞１、２、３、４は、出発位置Ｓから目的地Ｚへの代わりのルート上に位置する。交通渋滞１、２、３の１つが、減少又は解消し−さらに計算されたルートＲ上の交通渋滞が、不変のままであった場合−対応する代わりのルートが「より良い」ことになろう。この理由で、交通渋滞１、２、３は、「関連する」ものであり、監視される。その一方、交通渋滞４は、非常に長い迂回路を経由しなければ目的地Ｚに至らない道路の区間上にある。交通渋滞４が解消したとしても、これは計算されたルートＲに代わる良い選択肢のルートとはならない。この理由で、交通渋滞４は、関連性が無く、監視されない。計算されたルートＲの外側の交通状況が悪化する結果として（すなわち、１カ所以上の交通渋滞１、２、３、４が増加する結果として、及び／又は新しい交通渋滞が新たに生じる結果として）計算されたルートの変更は不可能であることが留意されるべきである。
【００３２】
「関連する」交通渋滞１、２、３に加えて、図１の交通渋滞４もまた、交通渋滞が監視される予め画定可能な領域についての対応する選択を与えると考えると、関連あるものと考えられることも留意すべきである。この交通渋滞４が減少又は解消しても、ルートの変更にはならないが、そのルートは、この場合では再計算されることになる。但し、交通管理センタは、新たに計算されたルートが、当然、（先に計算された）ルートＲに対応するので、車載装置にいかなる情報も送信しない。予め画定可能な領域の「寛大な」選択を前提とすると、「関連する」交通渋滞が決定されるときに車載装置により元のルートを求めることに伴う少量の計算作業は、交通状況が改善される場合に、ルートが再計算されるときに多数の交通渋滞を考慮に入れた、大量の計算作業とは対照的である。より小さい領域を選択する結果として、ルートの再計算に伴う計算作業は低減されるが、恐らく「関連する」交通渋滞は、「無関係な」ものと見なされる。いかなる場合においても、ルートの再計算は、ここでは交通状況が予め画定可能な程度だけ改善するときに、実行される。
【００３３】
図２は、監視されるべき交通渋滞を選択中の、本発明による方法の好ましい実施形態のステップを示す。ここでは、図２ａは、交通渋滞を考慮しない最適ルートＲ１の計算（第１のステップ）を示し、図２ｂは、全ての交通渋滞を考慮したルートＲＡの計算（第２のステップ）を示し、図２ｃは、「関連する」ものとしてルートＲ１上の交通渋滞２の選択、及びこの交通渋滞を考慮したルートＲ２の計算を示し（第３のステップ）、図２ｄは、交通渋滞１の選択、及びルートＲ３の計算を示し、ルートＲ３はルートＲＡに対応し（第４のステップ；ルートＲＡ上の交通渋滞の幾つかは未だマークされていないので、さらなるルート計算が実行されなければならない）、図２ｅは、交通渋滞Ａ及びＢの選択、及びルートＲ４の計算を示し（第４のステップの第１回目の反復）、及び図２ｆは、交通渋滞３の選択、及びルートＲ５の計算を示し、ルートＲ５はルートＲＡに対応する（第４のステップの第２回目の反復、交通渋滞Ａ及びＢは１つ前のステップですでにマークされているので、そのプロセスはここで中止される）。
【００３４】
交通渋滞ＶＳの限界コストＧ（ＶＳ）の定義が、図３に示される。出発位置Ｓから交通渋滞ＶＳの開始点（位置Ｐ）までの部分ルートＲＡ、ｎｅｗ（１）、交通渋滞ＶＳの開始点（位置Ｐ）から目的地Ｚまでの部分ルートＲＡ、ｎｅｗ（２）、計算されたルートＲＡ、及び交通渋滞ＶＳが、示される。
【００３５】
「関連する」ものとして認識される個々の交通渋滞ＶＳは、例えば、結果的に時間の無駄となることを含むコストＫ（ＶＳ）として割り当てられる。さらに、限界コストＧ（ＶＳ）が決定され、この限界コストを下回ると計算されたルートの変更が可能となる。何らかの交通渋滞ＶＳがあるときで計算されたルートに変更がある場合には、限界コストを下回るように、ここでは、限界コストＧ（ＶＳ）が選択される。逆に、たとえ新たに計算されたルートが不変のままであっても、すなわち、すでに計算されたルートと同じであっても、交通渋滞の際には限界コストを下回り得る。
【００３６】
特定された限界コストＧ（ＶＳ）を導き出すために、そのコストがより低い値Ｋｎｅｗ（ＶＳ）まで下がり、その結果、計算されたルートに変更をもたらす交通渋滞ＶＳが考慮に入れられる。「関連する」交通渋滞の全ては、不変のままである。次に、新たに計算されたルートＲＡ、ｎｅｗに沿った移動時間が決定される。新たに計算されたルートは、交通渋滞ＶＳが減少するという条件に従ってもたらされるので、ルートＲＡ、ｎｅｗは交通渋滞ＶＳを通過しなければならない。したがって、このルートＲＡ、ｎｅｗは、出発位置Ｓから位置Ｐにおける交通渋滞ＶＳの開始点まで続く部分ルートＲＡ、ｎｅｗ（１）と、位置Ｐから交通渋滞ＶＳを通って目的地Ｚに至る部分ルートＲＡ、ｎｅｗ（２）とから構成される。これに関し、交通渋滞ＶＳがあるところのルートの一部に沿った道路の区間からそれることはできない。この場合には、ルートＲＡ、ｎｅｗは、必ずしも全ての交通渋滞ＶＳを通過するわけではなく、ここで考慮中の限界コストにより、計算されたルートの変更が検出されないことが保証される。
【００３７】
元のルートを求める場合において、交通渋滞ＶＳが位置するルートＲｉが、出発位置Ｓから目的地Ｚまで計算されたとき、交通渋滞ＶＳは、「関連する」ものとして選択された。ルートＲｉは、出発位置Ｓから位置Ｐまでの部分ルートＲｉ（１）と、位置Ｐから目的地Ｚまでの部分ルートＲｉ（２）とから構成される。ルートＲｉが計算された時点において「関連する」ものとして選択された交通渋滞しか考慮に入れないという条件において、ルートＲｉは、「最適」である。したがって、ルートＲｉが、「最適」であるので、部分ルートＲｉ（１）及びＲｉ（２）もこの条件において「最適」である。ルートＲｉ上の移動時間、ここではすでに選択された交通渋滞しか考慮に入れられない場合であるが、上記移動時間は、ｔ＊（Ｒｉ）と表され、同様のことが、部分ルートＲｉ（１）及びＲｉ（２）の移動時間にも当てはまる。交通渋滞ＶＳそれ自体は、ルートＲｉが計算される時点において「関連する」ものとして未だマークされていないことも、ここでは留意されるべきである。全ての交通渋滞を考慮に入れて「最適」とされる部分ルートＲＡ、ｎｅｗ（１）は、全ての交通渋滞のうち数カ所しか考慮に入れられていない移動時間ｔ＊（Ｒｉ（１））よりも、長い移動時間、又はそれと同じ移動時間を有する。部分ルートＲＡ、ｎｅｗ（２）と部分ルートＲｉ（２）との両方が、交通渋滞ＶＳを通過し、交通渋滞ＶＳのコストが移動時間ｔ＊（Ｒｉ（２））に含まれていないので、部分ルートＲＡ、ｎｅｗ（２）は、交通渋滞ＶＳのコストだけ延長される部分ルートＲｉ（２）の移動時間よりも、長い移動時間、又はそれと同じ移動時間しか有さない。
ｔ＊（Ｒｉ（２））＋Ｋｎｅｗ（ＶＳ）。
【００３８】
したがって、以下のことが当てはまる。
ｔ＊（Ｒｉ（１））≦ｔ（ＲＡ、ｎｅｗ（１））
及び
ｔ＊（Ｒｉ（２））＋Ｋｎｅｗ（ＶＳ）≦ｔ（ＲＡ、ｎｅｗ（２））、
したがって、以下のことが当てはまる。
ｔ＊（Ｒｉ）＋Ｋｎｅｗ（ＶＳ）≦ｔ（ＲＡ、ｎｅｗ）。
ＲＡ、ｎｅｗは、その条件によれば、初めに計算されたルートＲＡよりも好ましいので、以下も真となる。
ｔ（ＲＡ、ｎｅｗ）＜ｔ（ＲＡ）
ゆえに、
ｔ＊（Ｒｉ）＋Ｋｎｅｗ（ＶＳ）＜ｔ（ＲＡ）及び、それぞれ、Ｋｎｅｗ（ＶＳ）＜ｔ（ＲＡ）−ｔ＊（Ｒｉ）。
この理由で、限界コストＧ（ＶＳ）＝ｔ（ＲＡ）−ｔ＊（Ｒｉ）が選択される。この値は、元のルートを求める時の「関連する」交通渋滞の決定中に計算でき、その交通渋滞がいつ変化しても、上記値を下回るかどうかをチェックすることは、容易に可能である。
【００３９】
ルート上で複数の連続部分にわたって延びる交通渋滞の場合でも、「最適」なルートの変更が検出されることを保証するために、このような交通渋滞は、ルートの交通渋滞の影響を受けた部分毎に、１つの部分に分割される。つまり、ルートの複数の部分区間ｋ１、．．．ｋｎにわたって延びる交通渋滞ＶＳは、それぞれが独立して交通渋滞と見なされる複数の交通渋滞Ｓ１、．．．Ｓｎに分割され、個々の交通渋滞Ｓｉは、交通渋滞Ｓの分割部分に相当し、ルートの部分区間ｋｉ上に位置する。
【００４０】
決定ポイントの概念を、図４及び図５を参考して、より詳細に説明する。ここで、図４は、計算されたルート上の決定ポイントを示し、図５は、交通渋滞が減少したため、新たに計算されたルート上の決定ポイントを示す。決定ポイントは、計算されたルートに変化があると、交通管理センタによって使用されるものであり、代わりのルートへの変更がコスト的に優位（例えば時間に関して優位）となるであろうポイント、すなわち、初めに計算されたルートの位置について、自動車の位置について正確な認識をせずに、自動車に連絡するためのものである。自動車が、この自動車の移動方向にある次の決定ポイントにおいて、初めに計算されたルートを離れる場合、最大にコスト的な優位性が得られる。この理由で、この決定ポイントが、車載装置によって選択され、表示される。したがって、予想されるコスト的な優位性のため、運転者が新しいルート関連データ（オンボードナビゲーションの場合の交通データ、又はオフボードナビゲーションの場合のルートが再計算された後のルートデータ）に対し、コストが発生しそうな要求を開始するかどうかについての決定を、例えば自動車の運転者によって又は自動的に行うことが可能となる。
【００４１】
決定ポイントＰ１、Ｐ２及びルートＲ１、Ｒ２、Ｒｓ及び交通渋滞ＶＳが、図４に示されている。ここで、「最適」なルートは、元の計算されたルートＲｓ上で最近発生した交通渋滞ＶＳのため、変更されている。自動車の位置により、２つの代わりのルートのうちの１つ、又は元のルートの１つが最も好ましい。自動車が、決定ポイントＰ１前に位置する場合、ルートＲ１は、ゆえに、「最良の」ルートとなる。自動車が、決定ポイントＰ１とＰ２との間に位置する場合、ルートＲ２は、ゆえに、「最良の」ルートとなる。自動車が、決定ポイントＰ２後に位置する場合、ルートＲｓは、ゆえに、「最良の」ルートとなる。
【００４２】
決定ポイントの原理も、計算されたルートが、関連する渋滞の減少又は解消の結果として変化する場合には、適用できる。このことは、図５で示される。順に、決定ポイントＰ１、Ｐ２及びルートＲ’、Ｒ（Ｐ１）、Ｒ（Ｐ２）及び交通渋滞ＶＳ’が示されている。ここで、「最適」なルートＲ’は、監視された交通渋滞ＶＳ’が減少する結果として変化している。再計算後、「最適」なルートは、監視された交通渋滞ＶＳ’がある道路の区間を含む。自動車が、決定ポイントＰ１前に位置する場合、ルートＲ（Ｐ１）が、ゆえに「最良の」ルートとなる。自動車が決定ポイントＰ１とＰ２との間に位置する場合、ルートＲ（Ｐ２）が、ゆえに、「最良の」ルートとなる。自動車が決定ポイントＰ２後に位置する場合、元の計算されたルートＲ’が、ゆえに、「最良の」ルートとなる。
【００４３】
図６は、「最短経路ツリー」を計算することによって、決定ポイントがどのように決定されるかを示す。ここで、最短経路ツリー（「ツリー」）は、それ自体が公知である方法、例えばダイクストラのアルゴリズムに従って、目的地Ｚへの最短経路が計算される。これは、ルートネットワーク、例えばデジタル道路マップのルートノード（「ノード」）を使用するルート計算を構成する。さらに、元々計算されたルートＲが示される。ツリー上のノードＰ１は、元のルートＲ上に位置しないノードＰ２に続く。この理由で、ノードＰ１は、ルート上の第１の決定ポイントである。元のルート上のノードＰ１に続くノードＰ３は、対照的に、ツリーエッジを介してノードＰ１に接続されない。対照的に、ノードＰ４は、ツリー上と元のルート上との両方でノードＰ３から続くので、ノードＰ３は決定ポイントではない。ツリー上のノードＰ４から続くノードＰ５は、元のルート上のノードＰ４から続かないので、ノードＰ４は第２の決定ポイントである。
【００４４】
ツリー上の決定ポイントを辿るノードを追跡することによって、この決定ポイントに対する目的地への最短経路を読み取ることも可能となる。したがって、図６では、決定ポイントＰ４から目的地Ｚへの最短経路は、ノードＰ５及びノードＰ７を経由する。自動車が新たに計算された「最適」なルートについて連絡されるときに十分な送信能力があれば、１カ所以上の決定ポイントについての新たに計算された「最適」なルートのコースも包含できる。
【００４５】
決定ポイントを決定するこの手順は、経路に対し唯一の後方に向かうサーチによって実施でき、最短経路ツリーは目的地Ｚから計算され、前記最短経路ツリーは、交通ネットワークの各ポイントから目的地Ｚまでの最適経路を含む。この状況において、目的地Ｚまでの最適経路上にある、特に唯一画定された後続するノードは、交通ネットワーク上のノード毎に決定され、目的地Ｚまでの最速のルート上での移動時間はノード毎に決定される。最短経路ツリー上の後続するノードがルートＲ上に無いような、計算されたルートＲ上のノードが、選択され、決定ポイントとして選ばれる。決定ポイント毎に、決定ポイントから目的地Ｚまでの計算されたルートＲ上での移動時間と、新たに計算された最短経路ツリー上での対応する移動時間との間の差をとって、時間の節約を計算する。
【００４６】
上記の代わりに、決定ポイントを決定するために、「最適」なルートは、最小限の速度を仮定して、自動車がすでに通過し計算されたルートＲ上のポイントから最初に再計算され、交通予測を考慮に入れると、自動車が現時点でこのポイントに位置することが推定される。このルートは、第１の決定ポイントＥｉまで計算されたルートＲに沿って延び、次にそこから分岐する。第２のステップにおいて、「最適」なルートＲ’は、計算されたルートＲでの最後のステップで計算された決定ポイントＥｉの直後にあるルートＥｉ’から計算され、自動車が現時点においてポイントＥｉ’に位置すると推定される。このルートＲ’が元のルートＲに対応しない場合、これはさらなる決定ポイントＥｉ＋１となる。この第２のステップは、予め画定された最大反復回数に達するまで、又は最後に計算される決定ポイントＥｉが、最大速度と仮定して自動車がすでに到着しているはずの最も遠いポイントであるルート上のポイントの後になるまで、又は最後に計算されたルートが元々計算されたルートに対応するまで、繰り返される。決定ポイント毎に、決定ポイントから目的地Ｚに対して元々計算されたルート上での移動時間と新たに計算されたルート上での対応する移動時間との間の差が取られて、時間の節約を計算する。
【００４７】
図７ａ、ｂ、ｃは、複数のルート計算から成るシーケンスによる決定ポイントの決定を示す。図６で、すでに示した初期状況をここでは参考にする。第１のルート計算中、図７ａを参照すると、この新しいルート計算の時間ｔ１において、自動車は少なくともノードＰ０に到着していると推定されるので、出発ポイント（ノード）Ｐ０が選択される。このルート計算中、現在の及び予測される交通データは、自動車が時間ｔ１においてノードＰ０に位置すると仮定して考慮に入れられる。この第１のルート計算は、「最適」なルートがノードＰ１において、計算されたルートＲから分岐することを示し、この理由で、Ｐ１が、第１の決定ポイントＥ１として選択される。第２のルート計算は、図７ｂを参照して、計算されたルートＲ上で、ノードＥ１’＝Ｐ３へと続くノードＥ１で始まる。したがって、自動車が時間ｔ１においてノードＰ３に位置すると推定される。この第２のルート計算中、ノードＰ４＝Ｅ２は、第２の決定ポイントとして決定される。第３の計算中に得られるルートは、図７ｃを参照して、初めに計算されたルートＲに一致するので、さらなる決定ポイントは何も検出されない。ルート計算のシーケンスは、したがって、終了する。
【００４８】
第２の選択肢においては、最新の方法でのルート計算は、最短経路ツリーの計算とほぼ同じ程度の複雑さであるので、第１の選択肢と比べてより長い計算時間を投入しなければならない。第２の選択肢の利点は、交通予測のより正しい使い方にある。新しいルート計算の時間ｔ１において、自動車が元のルート上の様々なポイントに位置するという事が考慮される。その結果、そのルートの各部分の未来の交通状況も、自動車がそこに到着できるおよその時間に対し考慮に入れられる。対照的に、最短経路ツリーが第１の選択肢に従って計算されると、目的地Ｚにおける自動車の到着時間ｔ２が画定される。ルートの他の全ての部分の到着時間は、時間ｔＺに目的地Ｚに到着するために、自動車がそこを発たなければならない時間である。
【００４９】
この差は、図８で示されており、最短経路ツリーが計算されるとき、目的地において同一の到着時間ｔｚ＝時刻１０：４０が仮定される。図８ａを参照。このことにより、ノードＰ６において時刻１０：２０、ノードＰ３において時刻１０：００、及びノードＰ０において時刻９：４０の出発時間となる。但し、実際は、時刻１０：００において自動車は、元のルート上のノードＰ０とノードＰ６との間のどこかに位置する。図８ｂに示されるノードＰ０、Ｐ３、Ｐ６の３つのルート計算に対し、それぞれの場合で時刻１０：００という出発時間が仮定される。これは、したがって、時刻１１：００、時刻１０：４０、及び時刻１０：２０の３つの予想到着時間となる。その結果、図８ａの最短経路ツリーには当てはまらない、目的地Ｚに近い交通状況も、これらの３種類の異なる時間に対し考慮に入れられる。その結果、交通状況に著しい予測された変化があると、異なるルートを計算すること、及び一定の状況下では、２つの方法を使用して異なる決定ポイントをも計算することが可能となる。つまり、図８ｂで示された第２の選択肢において、各ルート計算ｉ（ｉ＝１、２、３）が開始されるとき、自動車がｔ（ｉ）＝時刻１０：００において、それぞれの出発位置（ノード）Ｐ０、Ｐ３、Ｐ６に位置すると推測される。
【００５０】
決定ポイントを計算する第３の代わりの方法では、交通管理センタにおいて未知である自動車の位置が推定される。この目的のため、例えば自動車によって決定され、送信される最後の到着時間が使用される。交通状況が変わると、３つの（予想される）自動車の位置が交通管理センタ内で推定され、これらの位置は、すなわち最低速度の運転操作、最高速度の運転操作、及び平均速度の運転操作に対するものであり、したがって、計算されたルートＲの変化、そして適切であれば、決定ポイントが、これらの推定される自動車の位置について決定され、自動車に送信される。
【００５１】
元々計算されたルートＲ上の決定ポイントＥ１及びＥ２により、現在利用できる交通データ及び予測に従って、計算されたルート、すなわち、元のルートＲからより好ましいルート上に分岐するノードは、ルートＲ上の残っている区間以外に通じる。この状況において、「より好ましい」ルート上への変更によって得られるそのコスト的な優位（例えば時間に関する優位）は、決定ポイントＥ１、Ｅ２毎に計算される。少なくとも移動の方向にある最後の決定ポイント及びそのコスト的な優位は、ルート関連データの一部として自動車に無線により送信される。上記に代えて又は加えて、決定ポイントについての予め画定可能な最大数が、無線により、自動車に決定ポイントのコスト的な優位と共に送信されるように規定することも可能である。当然、それぞれのコスト的な優位についての送信を省くことも可能である。
【００５２】
このような送信を受信した後、車載装置は、移動方向にある自動車に最も近い決定ポイントを選択する。次に、この決定ポイントの位置は、自動車の運転者に、恐らく予想されるコストの節約と共に、表示される。したがって、自動車の運転者は、交通管理センタから新たに計算されたルート（オフボードナビゲーション）又は変化した交通状況（オンボードナビゲーション）の形態のルート関連データを、無線により要求する。この状況において、移動方向にもはや決定ポイントがないか、又はナビゲーションプロセスがすでに終了されている場合には、車載装置によって、受信される送信内容は、無視される。
【００５３】
図９は、出発位置Ｓから目的地Ｚまでの動的ナビゲーションでの自動車の位置（ノード）Ｐ１、Ｐ２、Ｐ３と関連した決定ポイントＥ（Ｐ１）及びＥ（Ｐ２）の使用を、もう一度示す。車載装置は、どの決定ポイントが適当であるかをチェックするために、自動車の位置を使用し、自動的に又は要求に応じて、交通管理センタから対応するルート関連データを無線により要求する。自動車が位置Ｐ１に位置する場合、決定ポイントＥ（Ｐ１）において、計算されたルートＲから新たに計算されたルートＲ１上に分岐すると、交通渋滞１の周囲を走行することが可能となり、したがって、計算されたルートＲと比べて新たに計算されたルートＲ１の方がより長い道程であるにも関わらず、自動車が計算されたルートＲ上に留まる場合よりも速く、目的地Ｚまで移動することが可能となる。自動車が位置Ｐ２に位置する場合、決定ポイントＥ（Ｐ２）において計算されたルートＲから新たに計算されたルートＲ２上に分岐すると、交通渋滞１の周囲を走行することが尚も可能であり、したがって、短い交通渋滞２が新たに計算されたルートＲ２上に位置する事実にも関わらず、自動車が計算されたルートＲ上に留まる場合よりも速く、目的地Ｚまで移動することが可能となる。対照的に、自動車が位置Ｐ３に位置する場合、自動車を計算されたルートＲから分岐させ、従って交通渋滞１の周囲を走行させるであろう決定ポイントは、もはや無い。
【００５４】
図１０は、予め画定可能な領域に関する情報の使用を示す。自動車は、予め画定可能な領域Ｖを発った後は、もはや目的地Ｚについてのいかなるルート関連データも持たず、さらに交通管理センタも、自動車が計算されたルートＲを辿り続けるかどうかについてのいかなる情報も持たないので、ルート関連データは、予め画定可能な領域Ｖに関する情報を含んで成る。新しいルートＲ２が、運転者によって選択された中間目的地ＺＺ２に続くときでも、自動車内でルート関連データを使用することが可能である。これは、ルートＲ２が領域Ｖによって完全にカバーされているからである。対照的に、自動車が、運転者によって選択された中間目的地ＺＺ１への新しいルートＲ１を辿る場合、自動車内でルート関連データを使用することはできない。これは、ルートＲ１の大部分が領域Ｖによってカバーされていないからである。その結果、所望の中間目的地が尚も予め画定可能な領域Ｖ内部にあるかどうか、及び／又は中間目的地における到着時間が元の到着時間と大きく異なるかどうかを、自動車側においてチェックすることが常に可能である。この場合、新しいルート関連データは、自動的に又は運転者の要求に応じて、交通管理センタから要求される。
【００５５】
図１１は、交通管理センタ内で、所定の交通渋滞又は個々の交通渋滞についての監視の期間を決定するため、自動車側において決定される目的地における到着時間の使用を示す。監視は、余りにも早く−例えば自動車が交通管理センタ内で推定されたよりももっと緩やかに移動する場合−又は余りにも遅く−例えば自動車が交通管理センタ内で推定されたよりも速く移動する場合−中断されないように、自動車側において決定される、目的地における到着時間Ｔ０は、車載装置から交通管理センタに無線により送信される。次に、目的地における記憶された到着時間Ｔ０を、現在決定されている到着時間ＴＡと連続的に比較することが、自動車側において行われる。現在決定されている到着時間ＴＡが、予め画定可能なしきい値Ｘ（例えばＸ＝３０分）よりも大きく、目的地における記憶された到着時間Ｔ０と異なる場合、対応する情報が、車載装置から交通管理センタに、自動的に又は要求に応じて送信され、現在決定されている到着時間ＴＡが、目的地における記憶された到着時間Ｔ０に上書きされる。したがって、現在の到着時間ＴＡが、順に決定される。現在決定されている到着時間ＴＡが、予め画定可能なしきい値Ｘよりも大きく目的地への記憶された到着時間Ｔ０と異ならない場合、現在の到着時間ＴＡが、順に決定される。
【００５６】
図１２は、計算されたルート変更の時間と共に、ルート変更の位置の使用を表す概略図である。図１２ａは、出発位置Ａから目標位置Ｄまでの動的ナビゲーションの概略図である。ここでは、特に出発位置Ａから位置Ｂを経由して目標位置Ｄまで、又は上記の代わりに出発位置Ａから位置Ｂ及びＣを経由して目標位置Ｄまでの、２つの予想される接続がある。位置Ｂから目標位置Ｄまでの接続は、位置Ｂ及びＣを経由して目標位置Ｄへの接続よりも短いが、交通渋滞ＶＳが第１の選択肢のルート上に一時的に存在している。
【００５７】
この交通渋滞ＶＳにより、図１２ｂで示されるように、第１の選択肢のルートＲ１、及び第２の選択肢のルートＲ２、及びルートの変更の位置Ｂにおける様々な到着時間に対し位置Ｂから目標位置Ｄまで移動するのにそれぞれ要する時間を示す、移動時間プロファイルが表される。交通渋滞ＶＳに帰因する移動時間Ｒ１の一時的な増加が、明確に示されている。時間ｔＥのとき、位置Ｂにおける自動車の予想到着時間を考えると、位置Ｂ及びＣを経由して目標位置Ｄに至る接続が、時間ｔＥにおいて最も速い接続であるので、交通管理センタ内でルートとして計算される。
【００５８】
但し、自動車が時間ｔｍｉｎ前に又は時間ｔｍａｘ後に位置Ｂに到達する場合、この計算されたルートは、もはや最速のものではない。この理由で、位置Ｂは、交通管理センタから車載装置に、変更の時間ｔｍｉｎ及び時間ｔｍａｘと共に、ルートの変更の位置として送信される。さらに、位置Ｂから目標位置Ｄへの接続に関するルート関連データも、車載装置に送信される。この場合、自動車が時間ｔｍｉｎ前か又は時間ｔｍａｘ後にルートの変更の位置Ｂに到着するとき、位置Ｂから目標位置Ｄへの新しいルートに、自動的に又は要求に応じて変更することが可能である。対応するルート関連データを、ルートの変更の位置Ｂにおいて、代わりのルートのために車載装置内で利用できない場合、このルート関連データは、交通管理センタから自動的に又は要求に応じて要求される。
【００５９】
上記の代わりに、図１２ｃに示されるように、移動時間が少なくとも一定量Δｔだけ低減される場合に限り、ルートの変更が自動車によって実行されるように規定することも可能である。この場合、自動車が時間ｔ’ｍｉｎ前又は時間ｔ’ｍａｘ後にルートの変更の位置Ｂに到着する場合、その装置は、位置Ｂから目標位置Ｄへの新しいルートに、自動的に又は要求に応じて変更される。この手順は、特に車載装置が、交通管理センタから通常ではコストが発生する新しいルート関連データを要求しなければならない場合に、適している。
【００６０】
図１３は、計算されたルートの変更の時間と共にルート変更の位置についての使用を示す。図１３において、図２からの例が使用され、さらなる計算は、図２ｆの後に実行される。監視されるべき「関連する」交通渋滞が位置するルートＲｉ、ｉ＝１．．．ｍが、図２で計算された。次に、最も早い到着時間ｔｍｉｎ、ｄｒｉｖｅｒと最も遅い到着時間ｔｍａｘ、ｄｒｉｖｅｒが、自動車又は運転者のパラメータ、例えば想定できる最小及び最大平均速度に従って、交通渋滞の各到着時間に割り当てられた。これらの到着時間は、例えば、それぞれの計算されたルートでの最小及び最大の想定される平均速度から、得られる。次に、ルートのさらなる計算が実行され、その間にコストｍａｘ（Ｃｋ（ｔ））、ｔ∈［ｔｍｉｎ、ｄｒｉｖｅｒ、ｔｍａｘ、ｄｒｉｖｅｒ］が、コストＣｋ（ｔＥ）（ここで時間ｔＥは縁道ｋにおける自動車の予想到着時間である）の代わりに監視されるべき交通渋滞がある縁道ｋのコスト（例えば移動時間）として使用される。つまり、「最も好ましくない」場合の移動時間が使用される。交通渋滞のないコストは、残りの縁道のコストとして使用される。新たに計算されたルートＲｊがここで先に計算されたルートＲｊ−１と異なる限り、ルートＲｊ上の交通渋滞の全てが監視されるべきものとしてマークされ、別のルートが計算される。図１３ａにおいて、交通渋滞１、２、Ａ、及びＢは、図２の場合よりも大きくなり、ルートＲ６が計算され、交通渋滞４が追加的に監視される。ここで監視されるべきものとして追加的にマークされる交通渋滞４は、交通管理センタから車載装置に送信されない。
【００６１】
次に、平均速度を想定して「最適」となるルートＲＡからルートＲｉが分岐する、ルートの変更の位置として、全ルートＲｉ≠ＲＡ（ｉ＝ｌ．．．ｍ．．．ｎ）に対して、位置Ｐが決定され、さらに２つのルートが再び合流する位置Ｑが決定される。位置Ｐにおける予想される到着時間［ｔｍｉｎ、ｄｒｉｖｅｒ、ｔｍａｘ、ｄｒｉｖｅｒ］の範囲が計算され、ルートＲＡ及びルートＲｉ上を時間ｔｍｉｎ、ｄｒｉｖｅｒと時間ｔｍａｘ、ｄｒｉｖｅｒとの間に位置Ｐを出発し、位置Ｐから位置Ｑまでの予想される移動時間が比較される。存在する場合には、ルートＲｉ上の位置Ｐと位置Ｑとの間の移動時間が、少なくとも予め画定された程度だけルートＲＡ上での対応する移動時間よりも減少する位置Ｐにおける、予想される到着時間ｔＥ前の最も遅い時間ｔｍｉｎが計算される。存在する場合には、これも当てはまる時間ｔＥ後の最も早い時間ｔｍａｘが計算される。図１３ｂにおいて、ルートＲＡ上の位置Ｐ及びＱが、ルートＲ６と共に示されている。図１３ｃは、ルートＲ６及びルートＲＡ上の位置Ｐと位置Ｑとの間の移動時間を、一例として示している。時間ｔｍｉｎは、時間ｔｍｉｎ、ｄｒｉｖｅｒと時間ｔＥとの間でルートＲ６上での移動時間が常にルートＲＡ上での移動時間よりも長いので、ここでは存在しない。
【００６２】
図１４は、ルートの変更位置に関するどのデータが、交通管理センタから車載装置に送信されるかを示す。ルートの変更についての個々の決定された位置Ｐｉ（ｉ＝ｌ．．．ｎ；Ｐｉは、ｉ＞ｊのためＰｊよりも出発位置Ｓからより遠くにある）においてチェックされて、自動車がいかなる到着時間ｔｍｉｎ（Ｐｊ）、（ｊ＜ｉ）も下回らず、いかなる到着時間ｔｍａｘ（Ｐｊ）、（ｊ＜ｉ）も上回らず、さらに予想される最小速度Ｖｍｉｎを下回ることも、予想される最大速度Ｖｍａｘを上回ることもない場合に、関連する到着時間ｔｍｉｎ（Ｐｉ）を下回るか又は到着時間ｔｍａｘ（Ｐｉ）を上回るかを決定する。この条件が満たされる場合に限り、到着時間ｔｍｉｎ（Ｐｉ）又はｔｍａｘ（Ｐｉ）がそれぞれ、自動車に送信され、その場合に、位置Ｐｉの座標は、到着時間ｔｍｉｎ（Ｐｉ）も到着時間ｔｍａｘ（Ｐｉ）も送信されるべきでない場合、どちらも送信されない。
【００６３】
図１４に関し、次の到着時間ｔｍｉｎ（Ｐｉ）及びｔｍａｘ（Ｐｉ）が送信される。到着時間ｔｍｉｎ（Ｐｉ）及びｔｍａｘ（Ｐｉ）は、最小速度Ｖｍｉｎと最大速度Ｖｍａｘの間の速度で到達できる領域内にあり、したがって、送信される。対照的に、自動車が最大速度Ｖｍａｘで走行し、到着時間ｔｍｉｎ（Ｐ１）前に位置（ポイント）Ｐ１に到着しない場合、到着時間ｔｍｉｎ（Ｐ２）をもはや下回ることはない。到着時間ｔｍａｘ（Ｐ１）及び最小速度Ｖｍｉｎが条件を満たす場合、到着時間ｔｍａｘ（Ｐ２）を上回ることはない。この理由で、位置（ポイント）Ｐ２は自動車に送信されない。位置（ポイント）Ｐ３は、到着時間ｔｍａｘ（Ｐ３）を上回り得るので送信され、到着時間ｔｍｉｎ（Ｐ３）は送信されない。
【００６４】
さらに、想定できる最小速度に従い、さらに到着時間ｔｍａｘ（Ｐｉ）で設定された制限時間に従いながら、自動車が、最大時間に対し目的地Ｚへの途上にある場合に限り、交通渋滞が交通管理センタ内で監視されるように規定することが可能であり、その場合に、ルートの再計算ができるとすれば、少なくとも通過するルートの一部は、最小速度、及び到着時間ｔｍａｘ（Ｐｉ）との準拠性を想定して、初めに計算されたルートで決定される。
【図面の簡単な説明】
【００６５】
【図１】動的ナビゲーションの場合の多様な交通渋滞の概略図である。
【図２ａ】監視されるべき交通渋滞の選択時の本発明による方法の好ましい実施形態のステップを示す。
【図２ｂ】監視されるべき交通渋滞の選択時の本発明による方法の好ましい実施形態のステップを示す。
【図２ｃ】監視されるべき交通渋滞の選択時の本発明による方法の好ましい実施形態のステップを示す。
【図２ｄ】監視されるべき交通渋滞の選択時の本発明による方法の好ましい実施形態のステップを示す。
【図２ｅ】監視されるべき交通渋滞の選択時の本発明による方法の好ましい実施形態のステップを示す。
【図２ｆ】監視されるべき交通渋滞の選択時の本発明による方法の好ましい実施形態のステップを示す。
【図３】交通渋滞に伴う限界コストの概要である。
【図４】計算されたルート上の決定ポイントを示す。
【図５】交通渋滞の減少のため再計算されたルート上の決定ポイントを示す。
【図６】「最短経路ツリー」を計算することによる決定ポイントの決定を示す。
【図７ａ】複数のルート計算から構成されるシーケンスによる決定ポイントの決定を示す。
【図７ｂ】複数のルート計算から構成されるシーケンスによる決定ポイントの決定を示す。
【図７ｃ】複数のルート計算から構成されるシーケンスによる決定ポイントの決定を示す。
【図８ａ】「最短経路ツリー」の計算と独立した部分ルート計算の間の差を示す。
【図８ｂ】「最短経路ツリー」の計算と独立した部分ルート計算の間の差を示す。
【図９】自動車位置に関連した決定ポイントの使用を示す。
【図１０】予め画定可能な領域に関する情報の使用を示す。
【図１１】自動車側において決定される目的地への到着時間の使用を示す。
【図１２ａ】計算されたルートの変更の時間と共に、ルート変更の位置の使用の概略図である。
【図１２ｂ】計算されたルートの変更の時間と共に、ルート変更の位置の使用の概略図である。
【図１２ｃ】計算されたルートの変更の時間と共に、ルート変更の位置の使用の概略図である。
【図１３ａ】計算されたルートの変更の時間と共にルート変更の位置の使用を示す。
【図１３ｂ】計算されたルートの変更の時間と共にルート変更の位置の使用を示す。
【図１３ｃ】計算されたルートの変更の時間と共にルート変更の位置の使用を示す。
【図１４】ルート変更の位置に関するどのデータが交通管理センタから車載装置に送信されるかを示す。
【図１】
2005524061.tif 000003
【図２ａ】
2005524061.tif 000004
【図２ｂ】
2005524061.tif 000005
【図２ｃ】
2005524061.tif 000006
【図２ｄ】
2005524061.tif 000007
【図２ｅ】
2005524061.tif 000008
【図２ｆ】
2005524061.tif 000009
【図３】
2005524061.tif 000010
【図４】
2005524061.tif 000011
【図５】
2005524061.tif 000012
【図６】
2005524061.tif 000013
【図７ａ】
2005524061.tif 000014
【図７ｂ】
2005524061.tif 000015
【図７ｃ】
2005524061.tif 000016
【図８】
2005524061.tif 000017
2005524061.tif 000018
【図９】
2005524061.tif 000019
【図１０】
2005524061.tif 000020
【図１１】
2005524061.tif 000021
【図１２ａ】
2005524061.tif 000022
【図１２ｂ】
2005524061.tif 000023
【図１２ｃ】
2005524061.tif 000024
【図１３ａ】
2005524061.tif 000025
【図１３ｂ】
2005524061.tif 000026
【図１３ｃ】
2005524061.tif 000027
【図１４】
2005524061.tif 000028
【国際調査報告】
2005524061.tif 000029
2005524061.tif 000030
2005524061.tif 000031
2005524061.tif 000032
2005524061.tif 000033
2005524061.tif 000034