時間に依存してルートを計画する方法及びナビゲーションデバイス
本発明は、固定の事前定義済みルート区間コスト（例えば、法定制限速度）を有する地理的な有効範囲を可能な場合は時間に依存するより高いコストと組み合わせる。従って、例えば携帯ナビゲーションデバイスのユーザは、格納された地図データベースが範囲に含む地方の任意の目的地までのルート計画を以前と同様に継続でき、可能であれば、時間に依存するコストを含む交通データを更に使用でき、時間的に予測可能な渋滞の影響が自動バックグラウンドプロセスとして正確に考慮される。それにより、ユーザは、現在存在する渋滞及びそれが行程に影響を与えるかに関して考慮する必要なく、ナビゲーションデバイスにより提供される案内に従って運転し続けられる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地までのルートを計画する方法に関する。本発明は、最適な運転ルートの計画を可能にする、コンピュータにより実現されるシステムにおいて応用される。
【背景技術】
【０００２】
道路での移動は、ビジネス、他の組織及び個人の日常生活の重要な部分である。交通の遅延のコストは非常に大きい。純粋な経済的なコストは、ＵＫのみで数十億ポンドと推定される［CFIT］。それらのコストを考慮すると、例えば最適なルートを選択し且つ渋滞による遅延を回避することにより運転者が自身の移動を最適化することを支援できるシステムは非常に有用である。実際に、種々の運転者情報システムが発達してきている。
・思いがけない出来事や遅延に関する主観的な助言を提供するために、多くの発信元（警察、上方からの監視及びより最近では渋滞に巻き込まれた運転者からの移動電話通話）からのデータを集約するラジオ放送交通レポートが長い間にわたり定着している。ＲＤＳラジオは、通常のラジオ番組を交通レポートに自動的に切り替わることによりそれらシステムをより効果的にしている。
・静的なルート計画システムは、主要な自動車協会（AA、RAC）によりウェブ上に提供されている。それらシステムにより、運転者は行程の複数の地点を入力でき、ルート及びそのルートに対する運転指示が与えられる。
・ＧＰＳを使用する車載パーソナルナビゲーションシステム（ＰＮＳ）が導入されている。それらシステムは、従来の静的なコスト関数を使用して計算されたルート及び車両の位置を使用して、運転者を目的地まで案内するための指示を出す。そのようなシステムは、交通情報をサービスに取り入れ始めたが、交通情報をルート選択に取り込むまでには至っていない。遅延が選択したルートに影響を与える場合には、ユーザはその遅延を観察し、必要であると考えられる場合に道路の遅延のある区間を回避するルートを手動でシステムに再計画させる必要がある。
・種々の技術（例えば、移動電話、固定カメラ、ＧＰＳの艦隊の追跡）に基づくリアルタイム交通監視システムは、交通の遅延を識別し且つ通知システムに情報を供給するために使用されている。
【０００３】
道路渋滞が増加するにつれて、ルート計画を提供するシステムはよりエラーを起こしやすくなる。運転者は、ＡからＢへの最速のルートを要求したくなくなり、その上、例えば５０分間の交通渋滞に巻き込まれていることに気付く。同様に、僅かに長い高速道路のルートで非常に速く移動できる可能性があるにも関わらず、５０ｍｐｈで大型車に追従して移動するような混雑するＡ道路に沿ってルーティングするようなシステムを運転者は信用しなくなるだろう。
【０００４】
改善されたルート計画のための周知の技術においては、交通が移動する際の予想速度をより正確に反映する道路及び道路区間に個々の道路の速度を割り当てる必要がある。この割り当ては一般に静的である。すなわち、道路区間には調査及び解析後の固定のコストが割り当てられ、そのコストはルーティングアルゴリズムにおいて道路区間のコストとして後で使用される。コストは見直されるが、その見直しには元のコストの割り当てと同様のコストがかかる。従って、ナビゲーションデバイスのルート計画アルゴリズムは、そのデバイスに格納された地図データベースにおいて規定される道路の種類を使用してルート区間通過時間を計算する。車両は、平均して、その種類の道路に対する法定制限速度又はその種類の道路に一貫したある速度で移動すると仮定されてもよい。TeleAtlas及びNavTech等の会社によるそれら地図データベースは、通常、多くのコストをかけて全国にわたる道路を徹底的に調査した結果である。この方法の長所は、地図データベースの道路毎に通過時間が推定されることである。しかし、その短所は、デバイスが信用できる交通情報を有さないため、法定制限速度で移動するという仮定は渋滞する領域に対して明らかに成り立たなくなることである。最小コストのルート（例えば、最速）を計算する一般的な方法は、包括的であると考えられるが、渋滞が発生した場合には不正確なものになる。
【０００５】
近年、TomTom International BVのＧＯ（商標）等の高性能なルート計画アルゴリズムを含むＧＰＳ携帯衛星ナビゲーションデバイスが普及しており、多くの一般の運転者により使用されている。それらシステムに有効な交通データを取り込むことによる利益は大きい。
【０００６】
従来の交通監視システムは、渋滞を回避するように交通量データを提供することに集中してきた。しかし、監視機器（例えば、道路に埋設されたループセンサや、ナンバープレート認識システム等のカメラを使用するシステム）を開発するインフラストラクチャのコストのため、あるいは、流動的車両システムに依存するため（流動的車両システムでは、比較的少数の車両（専用ハードウェアを搭載した）が追跡され、典型的には都市部ではなく主要な道路を動く車両が追跡される）それらシステムは主要な道路に制限されてきた。民間の運送会社には、それら会社のトラックは主要な道路を主に使用するため、それら制限は受け入れられるだろう。
【０００７】
全体的には、交通監視サービスは全く包括的ではないが、監視されている道路で渋滞が発生した場合には有用である。しかし、その有用性は２つの理由により制限される。第１に、ユーザは単に渋滞を通知されるのみである。通常、それによりユーザは、新しいルートを計画したり、渋滞を考慮する等の適切な動作を要求したりすることになっている。第２に、車両が現在渋滞していると示される場所に到着する時までに渋滞が解消される可能性がある。渋滞が予測可能である場合（すなわち、朝の混雑時又は重要な試合が行われている時のスタジアム周辺の渋滞、あるいは主要道路の一車線を閉鎖する事故等の、ある種の規則性によるもの又は予測可能なものである場合）、車両が現在渋滞している道路に到着した時に経験する可能性のある渋滞を推定できる。時間に依存する交通量又は通過時間データ（例えば、毎週月曜日の朝８時には、特定のルート区間に対する通過時間が２０分である；それは午後１時には１５分になり、午後１１時には５分になる等）は、その推定を行なうのに役立つ。特許文献１（米国特許第６，３５６，８３６号公報）及び特許文献２（国際公開第２００４／０２１３０６号公報）を参照されたい。しかし、上述したように今日まで、一般に、その種のデータはある国の道路のうち、相対的に少ない一部の道路に対するデータを提供する交通監視システムのみに適用されてきた。
【特許文献１】米国特許第６，３５６，８３６号公報
【特許文献２】国際公開第２００４／０２１３０６号公報
【非特許文献１】Dijkstra: Edsgar W. Dijkstra、A Note on Two Problems in Connection with Graphs、1959年
【非特許文献２】CFIT: UK Commission for Integrated Transport、Congestion Charging
【非特許文献３】RoDIN24: Applied Generics、RoDIN24 real-time road traffic information、2005年
【発明の開示】
【発明が解決しようとする課題】
【０００８】
全体的な効果は、ユーザが時間に依存するルート区間コストによるルート計画アルゴリズムを使用できることであるが、交通監視システムの範囲に含まれる比較的に少ない一部の道路に対するルート計画に限定される。正確度は、地理的な有効範囲を犠牲にすることで得られる。あるいは、ユーザは固定の事前に定義済みのルート区間コスト（例えば、法定制限速度）に基づくルート計画アルゴリズムを使用できる。地理的な有効範囲は広がるが、正確度は低減する。
【課題を解決するための手段】
【０００９】
本発明は、目的地までのルートを計画する方法に関するものであり、該方法は、
（ａ）ルート区間によって道路を規定し、地図データベース中の異なる各ルート区間に関連する時間に依存しない固定の事前定義済みコストを含む地図データベースを使用するステップと、
（ｂ）目的地までのルートの計画を可能にし、１つ以上のルート区間を使用して目的地に到着するまでの推定コストを計算するソフトウェアを使用するステップとを備え、
ソフトウェアを使用するステップは、（i）特定のルート区間について通過されると計画された特定の時間に応じたコストがその特定のルート区間を通過することに適用される、ルート中の１つ以上のルート区間に対する時間に依存するコストと（ii）時間に依存するコストにより規定されないルート中のルート区間に対する時間に依存しない固定の事前定義済みコストと、の組み合わせを自動的に使用することによりルートを計画することを含む。
【００１０】
本発明は、固定の事前定義済みルート区間コスト（例えば、法定制限速度）を含む地理的な有効範囲を、可能な限り時間に依存するより高度なコストと組み合わせる。従って、例えば携帯ナビゲーションデバイスのユーザは、格納された地図データベースが範囲に含む地方の任意の目的地までのルート計画を以前と同様に継続でき、可能な限り、時間に依存するコストを含む交通データを更に使用でき、時間的に予測可能な渋滞の影響が自動バックグラウンドプロセスとして正確に考慮される。それにより、ユーザは、現在存在する渋滞及びそれが行程に与える影響に関して考慮する必要なく、ナビゲーションデバイスにより提供される案内に従って運転し続けることができる。
【００１１】
更なる実現例の詳細は以下を含む。即ち、
特定のルート区間に関連する時間に依存するコストは、測定又は推測されたルート区間通過時間又は車両速度に関し、また、そのコストは一定ではなく且つ事前定義されない。測定値は種々の形態をとってもよく、それについては後述する。一方、特定のルート区間に関連する時間に依存しない固定の事前定義済みコストは、実際の車両交通量又は動きから測定又は推測されず、（i）そのルート区間に関連する道路の種類の関数であるか又は（ii）そのルート区間に適用可能な制限速度の関数である。時間に依存しないコスト及び時間に依存するコストの双方により規定されるルート区間の場合、時間に依存しないコストは時間に依存するコストと組み合わせて使用される。組み合せは、種々の形態をとってもよい。しかし、最も重要なことは、時間に依存するデータが利用可能であっても、ルート区間に対して最も正確なコストを設定する際に依然として時間に依存しないデータに値が存在することである。例えば、時間に依存するデータの品質が悪く、完全に信用できない場合がある。そのデータと適切な相対重みを有する時間に依存しない固定のデータとを組み合わせることにより、妥当な推定値が得られ得る。同様に、時間に依存するデータは特定のルート区間に対して利用可能でない場合があるが、同様のルート区間又は近くのルート区間から知ることができるため、時間依存性を推測することが可能である。しかし、以前と同様に、時間に依存しない固定のデータを重み付けすることが望ましい。
【００１２】
一般に、特定のルートに関連するコストは、目的地に到着するまでにかかる推定時間である。それは、殆どのユーザが最も興味を持っていることだからである。しかし、任意の他のコストも使用できる。コストは、道路区間に関連し且つ運転者又は他の誰かが要求又は提供することを選択できる実際のコスト又は知覚したコストである。例えば、特定のルートに関連するコストは、そのルートに関連する燃料使用量であってもよい。あるいは、道路の価格設定が機能しているか又は渋滞ゾーン等の他の形態の直接支払いが存在する場合に特に有用であるそのルートに関連して課される経済的なコストでもよい。特定のルートに関連するコストは、エンドユーザが演算装置に表示されるメニューリストから選択できる種類のコストである。上記例において、メニューリストは以下の項目の１つ以上を含む。即ち、ルートの通過時間、ルートの経済的なコスト、ルートにわたる燃料使用量、交通停滞。全ての場合において、ソフトウェアは、コスト最小化アルゴリズムの一部としてルートのコストを計算する。
【００１３】
１つの特徴は、車両の特定の運転者の目的地に到着するまでの推定コストは、運転者に関連する運転プロファイルの関数であることである。従って、運転の仕方（例えば、高速／積極的／スポーツ、標準、低速／慎重）がコスト（特に、通過時間及び燃料使用量）に大きな影響を与える。方法は、種々のプロファイルの選択を可能にする（例えば、運転者自身がナビゲーションデバイスに表示されるメニューリストから手動で選択するか、あるいはそのデバイスが実際の運転を監視することにより自動的に選択する）。それらプロファイルは、適切なコストの集合又はコストに適用される重み因子を選択するのに使用される。例えば、スポーツモードの運転者は、非常に渋滞する領域以外では５％低減した通過時間を有してもよい。
【００１４】
上述のように、実際の車両交通量又は動きデータを測定する方法は多く存在する。例えば、これはＧＰＳ軌跡（通常、一定の時刻又は距離間隔におけるＧＰＳの位置データのレコード）を使用して行なわれる。ＧＰＳ軌跡は、ルート区間に沿って移動している車両中のＧＰＳを使用するナビゲーションデバイスにより格納される。ＧＰＳ軌跡は、デバイスによりセルラ無線ネットワークを介して交通監視システムに直接送出されるか、あるいはデバイスにより交通監視システムに直接送出される。ＧＰＳ軌跡は、ピコネット又は他の形態の接続を介してデバイスに接続された移動電話により送出されるか、あるいはデバイスがＰＣとドッキングされる場合にはデバイスにより交通監視システムに送出される。
【００１５】
実際の車両交通量又は動きの測定は、移動電話の場所を測定することにより達成される。これは、移動電話から基地局への信号トラフィックを受動的に監視することにより行なわれる。実際の車両交通量又は動きの測定は、道路のループセンサを使用して達成されるか、あるいはカメラを使用するシステム（例えば、ナンバープレート認識システム）を使用して達成されるか、あるいはラジオビーコンを備えた車両を使用して達成される。
【００１６】
時間に依存するコストは、動的に更新可能である。従って、交通状態が変化すると、それら変化は交通監視システムにより検出され、変更されたコストはルート計画ソフトウェアにより使用される。これは、事故や他の予測不可能な事象が発生した場合も含む。リアルタイムの動的な更新は非常に望ましい。
【００１７】
ルート区間に関連する時間に依存するコストは、時間に関連する種々のパラメータのうちの１つ以上のパラメータの関数である。例えば、それらは以下のパラメータの関数であってもよい。即ち、
・日中又は夜間の時間、
・曜日、
・祝祭日、
・学校の休日、
・更に一般的には、ルート区間のコストに影響を与える可能性のある任意の事象；又はルート区間のコストに与える可能性のある影響を推測できる任意の未来の状況。
【００１８】
上記方法を使用すると、１つ以上の目的地までのルートを計画でき、各目的地への到着時間は現在の制限速度に基づく方法より非常に正確である。
【００１９】
本発明の別の面によるデバイスは、
（ａ）地図データベースであり、ルート区間によって道路を規定し且つ地図データベース中の異なる各ルート区間に関連する時間に依存しない固定の事前定義済みコストを含む地図データベースと、
（ｂ）目的地までのルートの計画を可能にし、１つ以上のルート区間を使用して目的地に到着するまでの推定コストを計算するソフトウェアと、
によりプログラムされるナビゲーションデバイスであって、
デバイスは、（i）特定のルート区間について通過されると計画された特定の時間に応じたコストがその特定のルート区間を通過することに適用されるような、ルート中の１つ以上のルート区間に対する時間に依存するコストと（ii）時間に依存するコストにより規定されないルート中のルート区間に対する時間に依存しない固定の事前定義済みコストとの組み合わせを自動的に使用することによりルートを計画できる。
【００２０】
それは、目的地までの最小コストのルート、例えば最速のルート、燃料使用量が最小であるルート、最も経済費用の低いなルートを計算できるデバイスである。時間に依存するコストは、デバイスにプッシュされるか又はデバイスによる要求時にデバイスに送出される。帯域幅の効率に対しては、デバイスにより受信された時間に依存するコストが道路の種類の分類に制限される。
【００２１】
デバイスは、地図データベースを含む同一のメモリ上に時間に依存するコストを含むことができる。従って、１つの方法は、完全な地図データベース及びデータベース中の多くのルート区間に関連する時間に依存するコストを含むメモリカード又は他のメモリ物理フォーマットを配布することである。あるいは、デバイスがサーバ、すなわちＯＴＡ（over-the-air）からデータをダウンロードできるインターネットに接続されたＰＣとドッキングされる場合、デバイスは時間に依存するコストを入手でき、時間に依存するコストはデバイス自体のメモリ（通常、ハードドライブ又は固体メモリ）に格納される。
【００２２】
別の方法は、リモートサーバが出発地から目的地までの動きに関連するコストをデバイスに送出することである。サーバは、時間に依存するコストを最近のデータで補足することを可能にするリアルタイムの交通情報出力を受信する。デバイスがリアルタイム又は最近の交通データ、あるいは渋滞情報をサーバから受信する場合、デバイスはそのデータ又は情報を自動的に使用して最適なルートを再計算する。
【００２３】
また、
（ａ）デバイス及びサーバは、それぞれ別個に時間に依存するコストを使用でき、
（ｂ）デバイスは、再計算した最小コストのルートをサーバに通知でき、
（ｃ）サーバは、計算した最小コストのルートがデバイスにより計算されたルートと異なる場合にデバイスに通知を送出できる。
【００２４】
サーバが単にルート間の相違を規定する通知をデバイスに送出する場合、帯域幅は節約される。
【００２５】
別の方法として、
（ａ）デバイス及びサーバは、それぞれ別個に時間に依存するコストを使用し、
（ｂ）デバイスは、最近のデータが有効である道路区間を識別し、サーバからその最近のデータを要求する。
【００２６】
任意の事象において、ユーザが到着したい時間を規定する場合、デバイスは行程の最適な出発時間を提案できる。
【００２７】
デバイス自体は、ＧＰＳを使用するナビゲーションデバイスであってもよい。デバイスは、ＧＰＳ等の位置探査システムを有する移動電話であってもよい。デバイスは、TomTomのＧＯ等の携帯ナビゲーションデバイスであってもよく、あるいは自動車に恒久的に組み込まれてもよい。
【００２８】
他の面は以下の通りである：
時間の関数として交通速度又は通過時間データを測定し、道路の区間に対する時間に依存する交通速度又は通過時間の履歴データベースを生成し、且つ少なくともそのデータベースの一部又はその内容を共有して上記方法の実行を可能にする交通監視システムである。
【００２９】
ルート計画ソフトウェアにより使用される場合に上記方法の実行を可能にするように適応されるある領域のデジタル地図であり、地図は、少なくとも道路区間の一部に関連する時間に依存するコストを規定するデータと共に道路区間を規定するデータを含む。
【００３０】
上記方法を使用してルートを計画するように動作可能な組込みナビゲーションシステムを含む自動車。
【発明を実施するための最良の形態】
【００３１】
特定の行程をとりたい運転者に道路網におけるルートを提案するための種々の機能が存在する。ここで、行程は、単純に２地点間で指定されてもよく、あるいは任意の順番で訪れる必要のある複数の場所を含むより複雑な行程であってもよい。これは、配達を行う運転者がとる行程の種類であってもよい。目的は、行程の形式に関わらず、その行程に関連するコストを最小化することである。最も明らかなコストは時間であるが、その行程をとるのに使用される燃料等の任意の他のコストが関連する場合がある。ユーザは、使用される道路の選択を制限できる。例えばいくつかの種類の営業用の車両は、都市圏外にいる場合に幹線道路以外の全てのルートの使用を禁止される。最も一般的には、それら機能は、ルートの区間にコストを割り当て且つ分岐点及びルートのグラフにコスト最小化アルゴリズム［Dijkstra］を適用するアルゴリズムをカプセル化するコンピュータシステムとして実現される。単純な例において、コストは、ルート毎に固定されており、ルートの標準速度（通常、その値は当該道路の制限速度であるか又は制限速度から得られる値である）で移動する場合のルートに沿った行程にかかる時間である。これを静的なコスト関数と呼ぶ。
【００３２】
これは、混雑時及び閑散時による変動等のルートに沿う潜在的な速度の変動を考慮していない。また、道路の制限速度が道路の使用可能な安全速度の非常に低品質な予測因子であるということを考慮していない。
【００３３】
ある期間にわたり道路のコストが変動する問題を解決するために、アルゴリズムは時間に依存するコストをルートに付加するように変更される。ルーティングアルゴリズムへの入力は、最適なルートに要求される時間を含み、関連する時間における適切なコストは各ルート区間に適用される。そのようなシステムの課題は、ルートに対して適切なコスト関数を提供することである。システムは混雑時により高いコストを割り当てることにより合成コスト関数を生成できるが、個々の道路は個々の渋滞パターンを有する傾向にある。従って、時間によって変動するコストは、実際のコストの改善された推定値であるが、完璧な値とは大きく異なる。
【００３４】
本発明は、より正確な運転者ルーティングシステムを与えるために、道路に対してより適切なコスト推定値を提供するという課題に対処する。交通監視システム（又は交通監視システムの履歴出力）がルーティングシステムに組み込まれる。監視システムにより与えられる履歴交通情報は、関心のあるルート及び時間に対するコストの予測値を提供するために処理される。コスト最小化アルゴリズムはルート区間の予測コストに対して適用され、提案された１つ以上のルート及びそれらの合計の予測コストを生成する。
【００３５】
新しいシステムが時間で変動するコスト推定値及びルート候補を提供する。そこで、本実施形態では、行程に対して最適なルートとして元々提案されたものを使用する運転者が、道路状態が動的に変化するにつれて、最適なルートに追従し続けることを保証するためのフレームワークについても説明する。
【００３６】
また、新しいシステムはルーティングサービスを更に改善する。例えば新しいシステムは、選択した時間ウィンドウ内での好適な運行時刻（行程の最小コストを結果として与える運行時刻）を提案するように適応される。
【００３７】
本発明は、特定の移動及び出発又は到着時間に対して最適化されたルート計画及び移動時間推定値を生成する方法及びシステムを提供し、最適な出発時間を提案するのにも使用さ得る。本発明は、交通監視システムにより生成されたデータ及び予測値を使用して、ルート区間の特定の時刻に対する正確な移動時間予測値を提供する。本発明は、従来のルーティングアルゴリズムと組み合わされると、発生する可能性のある交通状態を考慮して行程に対して最適なルートが選択されるのを可能にする。特に上述したように、実施例は、固定の事前定義済みルート区間コスト（例えば、法定制限速度）を含む地理的な有効範囲を可能な限り時間に依存するより高いコストと組み合わせる。従って、例えば携帯ナビゲーションデバイスのユーザは、格納された地図データベースがその範囲に含む地方の任意の目的地までのルート計画を以前と同様に継続でき、可能な限り、時間に依存するコストを含む交通データを更に使用でき、時間的に予測可能な渋滞の影響が自動バックグラウンドプロセスとして正確に考慮される。それにより、ユーザは、現在存在する渋滞及びそれが行程に影響を与えるかに関して考慮する必要なく、ナビゲーションデバイスにより提供される案内に従って運転し続けることができる。
【００３８】
図１にシステムを示す。システムは以下を具備する。
・交通監視システム１。
・ルーティングシステム２。
【００３９】
これら２つのシステムが組み込まれ、交通監視システム１は、ルーティングシステム２のコスト関数７により使用される通過時間予測機能３を提供し、時間に依存する正確な道路区間コストを提供する。
【００４０】
１．交通監視システム（ＴＭＳ）
Applied Generics社のRoDIN24［RoDIN24］等の交通監視システム１は、指定された地理的領域の交通をいくつかの機構を介して観察する収集／監視コア４を含む。
【００４１】
地理的領域内において、道路網は短い個別の区間に分割される。大きく離間された分岐点の間に複数の区間が存在する場合もあるが、通常、区間は分岐点で終了する。コアの内部の処理モジュールは以下のうちの一方又は双方を生成する：
・データベース５に格納された道路区間に対する履歴通過時間情報。規定の頻度で、道路区間を通過する現在の時間に対するシステムの推定値が、道路区間の交通に関連してシステムが生成する他のパラメータと共にデータベースに記録される。通過時間推定値を計算する方法は、交通監視システムに依存する。RoDIN24において、通過時間推定値は、システムが高い信頼性を置いている移動電話が、当該区間を通過する動きから得られる。国際公開ＷＯ０２４５０４６号を参照（ＷＯ０２４５０４６を引用することによってその内容をここに合体する）。
・渋滞情報及び通知６。システム６は、非常に渋滞している（予想された道路の速度より非常に低速で移動している）道路区間を識別し、協定されたプロトコルを使用して興味のあるクライアントに通知を発行する。
【００４２】
１．１ 通過時間の予測
交通監視システム１は、通過時間予測モジュール３により改善される。これは、任意の要求された未来の時間において、ＴＭＳ１の範囲内で任意の道路区間にわたる予想通過時間の推定値を提供するように設計される。道路の制限速度での通過時間を常に供給する通過時間予測モジュール３は、このシステムの退化した例であり、ルーティングシステムに組み込まれる場合に従来の静的な方法でルート予測を実現する役割を果たすことが分かる。従って、履歴データベース５又は渋滞情報／通知システムが有意義なデータを提供できない場合、デフォルト位置では、通過時間は制限速度の関数、すなわち従来の時間に依存しない固定のデータである。
【００４３】
好適な実施形態において、通過時間の予測は、履歴通過時間情報５の自動解析及び現在の渋滞情報６との統合に基づく。予測は、近い未来の全ての区間に対して継続的に実行されてもよく、あるいはルート計算の要求が特定の道路区間の予測通過時間を必要とする時の要望に応じて実行されてもよい。
【００４４】
交通の調査において、カレンダを日の種類に分類し、特定の種類の日において、混雑時、閑散時、日中、夜間等に時間を分類するのが一般的である。日の種類には以下のものがある：
・平日
・他の平日とは異なるパターンになる傾向がある金曜日
・土曜日
・日曜日
・祝祭日
【００４５】
年内の、学校が学期中であるか又は休暇中である時期は、更に時間が分割される。
【００４６】
そのようなカレンダをＴＭＳ１への入力として規定することにより、履歴データは適切なカテゴリに割り当てられる。各カテゴリ内において、短い時間ウィンドウ内の通過時間推定値がグループ化されてもよい。１５分は現実的なウィンドウの大きさである。履歴情報は、以下の形態で体系化される：
・平日、学校の学期中、０８：００〜０８：１５、推定通過時間は平均４３分
・金曜、学校の休暇中、０８：３０〜０８：４５、推定通過時間は平均２７分
【００４７】
通過時間予測３を実行する１つの機構は、上述したカテゴリような履歴情報カテゴリを使用することである。特定の時刻における行程に対する予測通過時間は、その時刻を含むカテゴリの平均通過時間値として与えられる。
【００４８】
当該機構の改善において、渋滞情報システム６により現在観察される異常な出来事及び渋滞が考慮される。観察された最新の通過時間は、それらのカテゴリの予測値と比較され、未来の予測値は、最近観察された通過時間と最近予測された通過時間との比に比例して変倍される。遠い未来の通過時間予測の場合、変倍は適用されるべきではない。更に一般的には、未来における予測の距離が大きくなるにつれ、予測は観察された値を平均の履歴の値に減衰させるべきである。
【００４９】
予測機構が非常に洗練されることは明らかである。最も重要な改善点は、履歴情報が入手可能であり、当該地理的領域のルート区間に対する通過時間のより正確な予測値を生成するために使用されることである。しかし、そのような情報がない場合、従来の時間に依存しない静的なコスト情報が使用される。
【００５０】
２．ルート探査器
ルート探査は、ネットワークのリンクにコストを割り当てる任意のルート探査アルゴリズムを使用してシステム２において実行される。動的なコスト関数は、ルーティングアルゴリズムに単純に取り入れられる。
【００５１】
２．１ 動的なコスト関数
動的なコスト関数は、道路区間及び関心のある（或いは未来の）時間の関数である。これは、道路区間のみの関数である静的なコスト関数とは対照的である。最も一般的な静的なコスト関数７は制限速度での通過時間であるが、他のコスト関数８が選択されてもよい。適切な動的なコスト関数は、ＴＭＳ１から通過時間予測機構を使用することにより実行される。コスト最小化アルゴリズム９が特定の移動時間に対して適用される場合、その動的なコスト関数は、より正確な予測行程時間及び最適により近いルートの選択を結果として与える。
【００５２】
２．２ Dijkstraによるルーティング
最短経路９がグラフのノード間で計算されるのを可能にする周知のアルゴリズム［Dijkstra］がある。これは、道路網の最短ルートを発見するのに採用される標準アルゴリズムである。Dijkstraのアルゴリズムにおいて、固定の重みがグラフの各端部に付加される。通常の道路ルーティングに対するコストは、道路区間に付加された固定の制限速度での道路区間の通過時間である。
【００５３】
動的なコスト関数を使用する場合、グラフの端部のコストは一定の値ではなく、時間と共に変動する。しかし、アルゴリズムに対して必要な僅かな拡張を行なうことで、特定の出発場所及び時間からの最小コストの経路が計算されることが分かる。実際には、１つのコストのみが特定の端部／道路区間に適用され（アルゴリズムの弛緩段階の間）、このコストが動的なコスト関数から入手可能であるため、この応用例におけるアルゴリズムの正確度はすぐに証明される。
【００５４】
この実現例において、いくつかのルート区間に対する固定の事前定義済みルート区間コスト（例えば、法定制限速度）が使用されるが、可能な限り他のルート区間に対する時間に依存するより高いコストが使用される。従って、例えば携帯ナビゲーションデバイスのユーザは、格納された地図データベースが範囲に含む地方の任意の目的地までのルート計画を以前と同様に継続でき、可能な限り、時間に依存するコストを含む交通データを更に使用でき、時間的に予測可能な渋滞の影響が自動バックグラウンドプロセスとして正確に考慮される。それにより、ユーザは、現在存在する渋滞及びそれが行程に影響を与えるかに関して考慮する必要なく、ナビゲーションデバイスにより提供される案内に従って運転し続けることができる。
【００５５】
２．３ 図２の例
動的ルーティングシステムが、ある移動例に関して、どのようにして時間を大きく節約するかを実証する。以下の概略的な道路地図を考慮する。運転者は、LilliputからBrobdingnagに移動したい場合に、運転者がとるべきルートと移動にかかる時間はどの程度か？を予測する。地図には道路に沿う距離と昼休み及び混雑時における速度とが示されている。例えば、30km(60kph/30kph)は、道路区間が３０ｋｍの長さであり、通過時間予測因子が使用可能な最適な情報によると、昼休み（１２：００）には６０ｋｐｈで移動し、混雑時（１６：００）には３０ｋｐｈで移動することを示す。
【００５６】
運転者のオプションが考慮される。運転者は、Blefuscu又はLaputaを経由して移動できる。全ての道路の制限速度が９０ｋｐｈであると仮定すると、Blefuscuを経由する移動の方が短く、従来のルーティングシステムは常にこのルートを提案するだろう。以下では、動的なコスト関数を使用してルーティングを検査する。
【００５７】
昼休み
１．１２：００において、LilliputからBlefuscuまでは６０ｋｐｈで３０分かかる。１２：３０において（運転者がBlefuscuに到着した時）、Brobdingnagまでの移動には６０ｋｐｈで２０分かかり、２０分が追加される。合計の移動時間は５０分である。
２．１２：００において、LilliputからLaputaまでは６０ｋｐｈで２０分かかる。１２：２０において（Laputaに到着する）、Brobdingnagまでの移動には６０ｋｐｈで４０分かかり、４０分が追加され、合計の時間は６０分である。
従って、昼休みにはBlefuscuを経由して移動した方がよいことは明らかである。
【００５８】
混雑時
１．１６：００において、LilliputからBlefuscuまでは３０ｋｐｈで６０分かかる。運転者は１７：００にBlefuscuに到着し、２０ｋｐｈでBrobdingnagまでの２０ｋｍを移動するには更に６０分かかる。移動には合計で１２０分かかる。
２．１６：００において、LilliputからLaputaまでは３０ｋｐｈで４０分かかる。運転者は１６：３０にLaputaに到着し、４０ｋｐｈでBrobdingnagまでの４０ｋｍを移動するには更に６０分かかる。移動には合計で１００分かかる。
従って、運転者は、混雑時にLaputaを経由する移動を選択することにより２０分の節約となる。
【００５９】
３．選択ルートの更新／監視
ルーティングシステムが運転者に対してルートを計算した場合、運転者がルートを通過している間に道路の状態が突然変化する場合がある。運転者が最適なルートをとっていることをリアルタイムで保証するルーティングシステムの実現例が構成され得る。これは以下のことを必要とする：
・運転者は、ルート上の到達した位置を示すためにルーティングシステムと接続している必要がある。代替システム（fallback）として、提案したルートの速度に基づいてシステムが運転者の位置を推定してもよい。
・ルーティングシステムは、運転者の現在の位置から目的地までのルートを周期的に再計算する。
・計算されたルートに変更が生じた場合、ルーティングシステムは、通信機構を使用して運転者に通知する。
【００６０】
３．１ 効率的な分散動的ルーティングシステム
動的ルーティングを提供するシステムの一般的な実現例は、パーソナルナビゲーションシステム（ＰＮＳ）をユーザの車両に配置するか又はユーザとともに移動可能な形態で配置する。ＰＮＳは、交通監視システムを含む固定ネットワーク相互接続システムである中央ナビゲーションシステム（ＣＮＳ）と通信する（間欠的に）。システムは、ＰＮＳとＣＮＳとの間に分散されていると考えられる。
【００６１】
ＰＮＳとＣＮＳとの間の通信システムの従来技術（例えば、ＧＰＲＳ）は、一般に広帯域、短い待ち時間及び連続通信を提供しないため、これよる通信の課題は実現例のアーキテクチャにおいて対処される必要がある。
【００６２】
更に、システムが多くのＰＮＳを含む場合、ＣＮＳにおいて多くの計算を実行するコスト、特にルーティングを行なうコストは非常に高い。同様に、ＣＮＳにおいて全てのＰＮＳの代わりに状態を維持すると、ＣＮＳにおいて展開される必要がある計算資源及び複雑度は非常に増加する。
【００６３】
分散動的ルーティングシステムにおいて、ルーティング能力はＰＮＳのみに配置されてもよいし、ＰＮＳとＣＮＳとの間で共有されてもよい。
・ＰＮＳのみに配置
・ＰＮＳは、履歴データベースの最近のスナップショットを含む。
・ＰＮＳは、ＣＮＳから渋滞情報を受信する。
・ＰＮＳは、通過時間予測を実行し、その近似値に基づくルーティングシステムを実現する。
・ＰＮＳとＣＮＳとの間で共有
・ＰＮＳ及びＣＮＳはユーザに対してルートを計算する。
・ＣＮＳ情報は常に最適である。
・ＣＮＳ及びＰＮＳは、ＰＮＳがユーザに対して最小限の意外性を含む常に十分に適切な（又はより適切な）ルートを提供することを保証しようとする。
【００６４】
ＣＮＳのみにおけるルーティングシステムは、ＣＮＳとＰＮＳとの間の接続性が十分に保証されないことの影響を受ける。そして、いずれの場合においても現在の技術のＰＮＳはＰＮＳにおける静的なルーティングを使用する。従って、単純にＰＮＳルーティングの退化した例として考えられるものを常に提供するものとなる。
【００６５】
種々の代替例が種々の利点を有する。そこで、各々が低通信コストで高速且つ正確なルート選択を提供する目的で実現される方法を検討する。最後に、ＣＮＳに対してステートレスであり且つ帯域幅のコストが低いという利点を有するルーティングシステムを説明する。
【００６６】
３．２ ＰＮＳルーティング
ＰＮＳは、ルーティングを行なう場合、ＰＮＳが関心ある地理的領域をＣＮＳに示す必要がある。これは、任意の検知可能なルートが常に領域内となるように十分な余裕を有するルートの出発地及び目的地を取り囲む領域である。これをルーティング可能領域と呼ぶ。ＣＮＳは以下のことを保証する必要がある。
１．ＰＮＳは、ルーティング可能領域の道路区間をＰＮＳにおいて情報により予測された速度と非常に異なる速度で移動している（従って、異なるコストを有する）場合に更新データを受信する。通常、これは、道路区間において予期しない遅延（渋滞）が存在することを意味する。
２．ＰＮＳは、ルーティング可能領域の最新履歴ビューを有する。履歴データベースは、徐々に変化する傾向があり、ＣＮＳは、ルーティング可能領域における期限切れとなった履歴情報の動的更新データをＰＮＳに提供してもよい。
【００６７】
要約すると、ＣＮＳは、ＣＮＳ自体が生成する最適なルートに最も近いルートを生成するのに十分に適切なルーティング可能領域のビューをＰＮＳが有することを保証する。ＰＮＳルーティングはリアルタイムの利点を有する。ＰＮＳがＣＮＳと接続されているか否かに関わらず、ルートを再計算するため且つ（ことによると）運転者の方向を変更するために更新データがＣＮＳから受信されるまで、周知の最適なルートが計算されて運転者により使用される。ルートが再計算され且つ運転者に利用される。
【００６８】
この形態のＰＮＳルーティングの１つの問題は、ＣＮＳがＰＮＳに更新データをプッシュできるように、ＣＮＳがＰＮＳのルーティング可能領域を記録する状態を維持する必要があるか、あるいはＰＮＳがルーティング可能領域の予測関数に対する更新データのためにＣＮＳをポーリングする必要があることである。
【００６９】
３．３ 共有ルーティング
ＰＮＳ及びＣＮＳは、ルート上の運転者を案内することに参加できる。ＰＮＳ及びＣＮＳが接続されている場合、それらＰＮＳ及びＣＮＳはルートを計算でき、それらが選択したルートの相違点に関して交渉できる、あるいは双方が同一ルートを選択した場合はそのままとする。
【００７０】
例えば：
１．運転者は（ルートＡＢ）についてＰＮＳに問い合わせる。
２．ＰＮＳは（ＡｒｓｔＢ）を計算する。
３．ＰＮＳは（選択したルートＡＢ（ｒｓ））をＣＮＳに送出する。それは、
・採用するように要求されたルート
・ＰＮＳが選択した第１の経由地点（すなわち、第１のルート区間）である。
４．ＣＮＳは、ルーティングシステムを使用して（ルートＡＢ）を計算する。定義上、これにより、この技術が生成できる可能な最適なルートが与えられる。（ＡｘｙｚＢ）
５．ＣＮＳは、ＣＮＳが生成したルートとＰＮＳが生成したルートとを比較する。この例において、ＣＮＳはｘ、ｙ及びｚを経由してルーティングし、これはＰＮＳに対して全く異なるルートであるため、ＰＮＳに知らせる必要があると考えられる。
６．相違点がある場合、ＣＮＳはそれら相違点を運転者に送信する。特に、ルートの開始時に相違点がある場合、単に迅速に送信する必要がある。ＣＮＳは、第１の相違点を単に送信する必要がある。ＰＮＳは、相違点を受信すると、ＰＮＳにより供給されたルート上の次の経由地点から残りのルートを計算できる。従って、ＣＮＳはＰＮＳに（選択したルートＡＢ（ｘ））を通知し、ＰＮＳは（ｘを経由するルートＡＢを）計算して、適切なルート（ＡｘｙｚＢ）として計算する。
・後でルート上に相違点が存在する場合、運転者がその相違点に到達した時には解消される一時的な渋滞が原因である相違点である可能性がある。そのため、ＰＮＳは、運転者がルートのその相違点に近付くまでルートを送信しないようにしてもよい。
７．ＣＮＳが後で異なるルートを再計算する場合、ＣＮＳは運転者のルートを監視し続けて通知を送出する。
【００７１】
この形態及び関連する形態の共有ルーティングは、帯域幅において非常に効率的である。正確な動的なコスト関数を仮定すると、その共有ルーティングはルート探査に対してほぼ最適である。共有ルーティングに関する主な問題は、ＣＮＳにおいて多くの計算及び状態コストがかかることである。
【００７２】
３．４ 図３の低ネットワーク負荷のＰＮＳルーティング
システムがＰＮＳルーティングを使用する場合、その結果として、履歴情報を符号化するＰＮＳにおける動的なルーティング関数及びＣＮＳから要求された非常に少量の遅延情報を使用して、十分に適切なルーティングが行なわれる。重要な点は、ＰＮＳ上でルーティングを行ない、コストがＰＮＳ上でＣＮＳにより計算される最新の値で更新される必要があるいくつかの道路区間を識別することである。これにより、ＰＮＳは、動的なコスト関数を使用してＣＮＳにより計算されたような最適なルートに近付くようにルートを改善できる。
【００７３】
以下、本機構を説明する。
１．ＰＮＳは、ルートＡ−Ｂに対してルーティング可能領域を構成し、ＣＮＳコスト関数によるコストがＰＮＳコスト関数によるコストより低いコストであるルーティング可能領域中の任意の道路区間に対して、ルートが使用される時間にわたるＣＮＳコスト値をＣＮＳに要求する。ＰＮＳが保持する履歴データベースのバージョンをＣＮＳに通知できるため、ＣＮＳはＰＮＳが使用しているコスト関数を認識している。ＣＮＳは、ＰＮＳの母集団に存在する全ての履歴データベースの符号化を保持するため、道路区間のコスト値がＰＮＳに返される必要があるかを任意の道路区間に対して判定できる。区間毎の最小コスト差dsが規定されるため、ＣＮＳは、道路区間及びＣＮＳコスト値（segment，costcns(segment)）をＰＮＳに送出する。それら値は、costcns(segment)+ds ≦ costpns(segment)を満足する。すなわち、ＣＮＳコスト値は少なくともdsだけ小さい。事実上、そのような選択した道路区間の数は少なく、従ってメッセージサイズ及びコストは小さい。
【００７４】
２．ここで、ＰＮＳは変更されたコスト関数routecostpnsを構成する。これは、先の段階で返されたより少ないコストの道路区間に対してＰＮＳにより返されたコスト値を割り当て、全ての他の道路区間に対してＰＮＳにより保持される履歴の値を割り当てる。ＰＮＳは、routecostpnsを使用してＡからＢへのルーティング計算を実行する。この計算により選択されたルートは、候補ルートbestroutepnsと呼ばれる。ＣＮＳコスト関数が認識している異常に高いコスト（遅延道路区間に相当する）について、変更されたＰＮＳコスト関数が認識していないため、ＣＮＳコスト関数routecostcnsは、routecostpnsより大きいコストをそのルートに付加するかもしれない。しかし、先の段階のＰＮＳコスト関数の変更のために、bestroutepnsは、bestroutecnsと呼ばれるroutecostcnsによる最小コストルートよりそれ程大きくないＰＮＳによるコストを有する。実際には、routecostpns(bestroutepns)≦routecostcns(bestroutecns)+ segmentcount(bestroutecns)*dsである。routecostpns(bestroutepns)のroutecostcns(bestroutepns)に対する類似性を段階１において道路区間及びコストを送信するのに必要とされる時間及びネットワーク帯域幅と相殺するために、システムにおいて使用されるdsの値が選択される。
【００７５】
３．ここで、ＣＮＳがＰＮＳにより選択された候補ルートに割り当てるコストroutecostcns(bestroutepns)は、ＰＮＳが割り当てるコストより非常に悪くないかのチェックが残っている。そのために、ＰＮＳはbestroutepnsの道路区間に対するＣＮＳコスト値を要求する。ＣＮＳは、それら道路区間に対するコスト値をＰＮＳに供給し、ＰＮＳは、ＣＮＳからのそれら道路区間コスト値を取り込むためにＰＮＳのコスト関数を更新する。ＣＮＳがＰＮＳの履歴データベースのバージョン番号を保存するか、あるいはＰＮＳが要求に応じてバージョン番号を再び送出する場合、ＣＮＳは、ＰＮＳがデータベースに保持する値とは異なる道路区間コスト値のみを返信するだけでよい。ここで、ＰＮＳコスト関数はroutecostpnsupdatedである。
【００７６】
４．ＰＮＳは、ここではルート上の道路区間に対するＣＮＳにより供給されたコスト値を使用して、先に選択した候補ルートのコストroutecostpnsupdated(bestroutepns)を計算する。尚、routecostpnsupdated(bestroutepns)=routecostcns(bestroutepns)である。受け入れ可能な最大のコスト差dextrarouteが規定され、bestroutepnsがこの段階でクライアントに提供するためのルートとして受け入れられるかをテストする。bestroutepnsは、routecostpnsupdated(bestroutepns)≦routecostpns(bestroutepns)+ dextrarouteの場合にのみ受け入れられる。システムにより使用されるdextrarouteの値は、routecostpnsupdated(bestroutepns)のroutecostcns(bestroutecns)に対する類似性を機構が消費する時間及びネットワーク帯域幅と相殺するように選択される。
【００７７】
５．bestroutepnsが受け入れられた場合、ルート選択の処理は完了し、bestroutepnsはＰＮＳのユーザに発行される。
【００７８】
６．bestroutepnsが受け入れられなかった場合、機構は段階２に戻る。但し、routecostpnsupdatedが新しい候補ルートbestroute'pnsを選択するのに使用される。bestroute'pns=bestroutepns（あるいは、更なる繰返しにおいては、先に選択された任意の候補ルート）である場合、bestroute'pnsはすぐに受け入れられる。bestroute'pns=bestroutepnsでない場合、システムは同一の処理を再び実行し、routecostpnsupdatedを更新するbestroute'pnsに対するＣＮＳコスト値を要求し（段階３）、routecost'pnsupdated(bestroute'pns)を計算する（段階４）。
【００７９】
７．最終的に、通常は非常に迅速に、dextrarouteの適当な選択を仮定すると、システムが生成した候補ルートの１つが受け入れられる。コスト関数routecostpnsupdatedが最終的にroutecostcnsに安定し、この時、routecostpnsupdated=routecostpnsであり且つ現在の候補ルートに対する受け入れ条件routecostpnsupdated(bestroutepns)≦routecostpns(bestroutepns)+ dextrarouteがすぐに満足されるため、ＰＮＳは最終的に候補ルートを受け入れる必要があることが分かる。
【００８０】
８．システムは、ＰＮＳのユーザに受け入れたルートを発行する。
【００８１】
９．任意の段階において、ＰＮＳとＣＮＳとの間の接続性が失われる場合、ＰＮＳはユーザに現在の候補ルートを発行できる。実際には、ルートの第１段階をすぐに発行し、運転者が近付く次の分岐点からルーティングするのが最適であることが多い。ユーザがルートを要求した後にシステムからの初期応答をコンマ何秒以上待つ必要がない場合、ユーザはシステムとの対話がより自然に見える。
【００８２】
１０．運転者が目的地に向けて移動する間、システムは受け入れたルートの残りの道路区間に対するコストを周期的に要求できる（段階３のように）。ルートの更に先の方で遅延が大きくなる場合、ＰＮＳは、段階４のアルゴリズムを再開することにより現在の位置から自動的に再度ルーティングできる。
【００８３】
低コストのＰＮＳルーティングは、ＰＮＳ（従って、ＰＮＳルーティング）において全てのルーティング計算を実行するが、それと同時にＣＮＳにおいて最小の状態を必要とし、帯域幅に対する要求を最小にする。低コストのＰＮＳルーティングは、ＣＮＳとの接続がない場合に有用であり続けられるというＰＮＳルーティングの利点を有する。更に、低コストのＰＮＳルーティングは、ＣＮＳにおいて動的ルーティングを使用して生成されたルートのコストに事実上十分に近いコストのルートを生成するため、動的ルーティングに関連するほぼ全てのコストの節約は実際に実現される。
【００８４】
３．５ 通信コストの低減
ルート選択に対する役割が分割されても、多くの技術を使用して、データ送信のコストは低く維持される：
【００８５】
位置に関係した区間番号付け
ＰＮＳ及びＣＮＳが通信している場合、運転者及びＰＮＳの正確な位置はほぼ常にＣＮＳにより必要とされる。殆どの関心道路区間が運転者（又は、運転者の要求ルート）にとって局所的であるため、別のルート番号付けシステムは、最も一般的に送信される道路区間を識別するために数ビットのみ必要であるＰＮＳとＣＮＳとの間に一時的に適切に配置される。
【００８６】
ルートに関係した区間番号付け
ＡからＢへのルートは、ルート上の通過した各分岐点における出口をカウントすることにより全体が説明される。各道路区間が非常に長い区間である場合、ルートの非常にコンパクトな表現が結果として得られる。
【００８７】
通常と同様に、ルートの大きな区間が同一の道路上にある場合、ランレングス符号化の形式が使用されてもよい。ルートは(3, 13, 2, 28, 2, 15)で表されてもよく、以下のことを意味する。
・次の分岐点の第３の出口
・次の１３個の分岐点を通り直進
・１４個目の分岐点における第２の出口
・次の２８個の分岐点を通り直進
・２９番目の分岐点における第２の出口
・１５個の分岐点を通り直進
・到着
【図面の簡単な説明】
【００８８】
【図１】図１は、本発明の一実施形態に係るルート計画システムを示す概略図である。
【図２】図２は、行程に対して最適化されたルートを選択するための動的なコスト関数の用途を示す地図である。
【図３】図３は、分散動的ルーティングシステムの動作を示す概略図である。
【技術分野】
【０００１】
本発明は、目的地までのルートを計画する方法に関する。本発明は、最適な運転ルートの計画を可能にする、コンピュータにより実現されるシステムにおいて応用される。
【背景技術】
【０００２】
道路での移動は、ビジネス、他の組織及び個人の日常生活の重要な部分である。交通の遅延のコストは非常に大きい。純粋な経済的なコストは、ＵＫのみで数十億ポンドと推定される［CFIT］。それらのコストを考慮すると、例えば最適なルートを選択し且つ渋滞による遅延を回避することにより運転者が自身の移動を最適化することを支援できるシステムは非常に有用である。実際に、種々の運転者情報システムが発達してきている。
・思いがけない出来事や遅延に関する主観的な助言を提供するために、多くの発信元（警察、上方からの監視及びより最近では渋滞に巻き込まれた運転者からの移動電話通話）からのデータを集約するラジオ放送交通レポートが長い間にわたり定着している。ＲＤＳラジオは、通常のラジオ番組を交通レポートに自動的に切り替わることによりそれらシステムをより効果的にしている。
・静的なルート計画システムは、主要な自動車協会（AA、RAC）によりウェブ上に提供されている。それらシステムにより、運転者は行程の複数の地点を入力でき、ルート及びそのルートに対する運転指示が与えられる。
・ＧＰＳを使用する車載パーソナルナビゲーションシステム（ＰＮＳ）が導入されている。それらシステムは、従来の静的なコスト関数を使用して計算されたルート及び車両の位置を使用して、運転者を目的地まで案内するための指示を出す。そのようなシステムは、交通情報をサービスに取り入れ始めたが、交通情報をルート選択に取り込むまでには至っていない。遅延が選択したルートに影響を与える場合には、ユーザはその遅延を観察し、必要であると考えられる場合に道路の遅延のある区間を回避するルートを手動でシステムに再計画させる必要がある。
・種々の技術（例えば、移動電話、固定カメラ、ＧＰＳの艦隊の追跡）に基づくリアルタイム交通監視システムは、交通の遅延を識別し且つ通知システムに情報を供給するために使用されている。
【０００３】
道路渋滞が増加するにつれて、ルート計画を提供するシステムはよりエラーを起こしやすくなる。運転者は、ＡからＢへの最速のルートを要求したくなくなり、その上、例えば５０分間の交通渋滞に巻き込まれていることに気付く。同様に、僅かに長い高速道路のルートで非常に速く移動できる可能性があるにも関わらず、５０ｍｐｈで大型車に追従して移動するような混雑するＡ道路に沿ってルーティングするようなシステムを運転者は信用しなくなるだろう。
【０００４】
改善されたルート計画のための周知の技術においては、交通が移動する際の予想速度をより正確に反映する道路及び道路区間に個々の道路の速度を割り当てる必要がある。この割り当ては一般に静的である。すなわち、道路区間には調査及び解析後の固定のコストが割り当てられ、そのコストはルーティングアルゴリズムにおいて道路区間のコストとして後で使用される。コストは見直されるが、その見直しには元のコストの割り当てと同様のコストがかかる。従って、ナビゲーションデバイスのルート計画アルゴリズムは、そのデバイスに格納された地図データベースにおいて規定される道路の種類を使用してルート区間通過時間を計算する。車両は、平均して、その種類の道路に対する法定制限速度又はその種類の道路に一貫したある速度で移動すると仮定されてもよい。TeleAtlas及びNavTech等の会社によるそれら地図データベースは、通常、多くのコストをかけて全国にわたる道路を徹底的に調査した結果である。この方法の長所は、地図データベースの道路毎に通過時間が推定されることである。しかし、その短所は、デバイスが信用できる交通情報を有さないため、法定制限速度で移動するという仮定は渋滞する領域に対して明らかに成り立たなくなることである。最小コストのルート（例えば、最速）を計算する一般的な方法は、包括的であると考えられるが、渋滞が発生した場合には不正確なものになる。
【０００５】
近年、TomTom International BVのＧＯ（商標）等の高性能なルート計画アルゴリズムを含むＧＰＳ携帯衛星ナビゲーションデバイスが普及しており、多くの一般の運転者により使用されている。それらシステムに有効な交通データを取り込むことによる利益は大きい。
【０００６】
従来の交通監視システムは、渋滞を回避するように交通量データを提供することに集中してきた。しかし、監視機器（例えば、道路に埋設されたループセンサや、ナンバープレート認識システム等のカメラを使用するシステム）を開発するインフラストラクチャのコストのため、あるいは、流動的車両システムに依存するため（流動的車両システムでは、比較的少数の車両（専用ハードウェアを搭載した）が追跡され、典型的には都市部ではなく主要な道路を動く車両が追跡される）それらシステムは主要な道路に制限されてきた。民間の運送会社には、それら会社のトラックは主要な道路を主に使用するため、それら制限は受け入れられるだろう。
【０００７】
全体的には、交通監視サービスは全く包括的ではないが、監視されている道路で渋滞が発生した場合には有用である。しかし、その有用性は２つの理由により制限される。第１に、ユーザは単に渋滞を通知されるのみである。通常、それによりユーザは、新しいルートを計画したり、渋滞を考慮する等の適切な動作を要求したりすることになっている。第２に、車両が現在渋滞していると示される場所に到着する時までに渋滞が解消される可能性がある。渋滞が予測可能である場合（すなわち、朝の混雑時又は重要な試合が行われている時のスタジアム周辺の渋滞、あるいは主要道路の一車線を閉鎖する事故等の、ある種の規則性によるもの又は予測可能なものである場合）、車両が現在渋滞している道路に到着した時に経験する可能性のある渋滞を推定できる。時間に依存する交通量又は通過時間データ（例えば、毎週月曜日の朝８時には、特定のルート区間に対する通過時間が２０分である；それは午後１時には１５分になり、午後１１時には５分になる等）は、その推定を行なうのに役立つ。特許文献１（米国特許第６，３５６，８３６号公報）及び特許文献２（国際公開第２００４／０２１３０６号公報）を参照されたい。しかし、上述したように今日まで、一般に、その種のデータはある国の道路のうち、相対的に少ない一部の道路に対するデータを提供する交通監視システムのみに適用されてきた。
【特許文献１】米国特許第６，３５６，８３６号公報
【特許文献２】国際公開第２００４／０２１３０６号公報
【非特許文献１】Dijkstra: Edsgar W. Dijkstra、A Note on Two Problems in Connection with Graphs、1959年
【非特許文献２】CFIT: UK Commission for Integrated Transport、Congestion Charging
【非特許文献３】RoDIN24: Applied Generics、RoDIN24 real-time road traffic information、2005年
【発明の開示】
【発明が解決しようとする課題】
【０００８】
全体的な効果は、ユーザが時間に依存するルート区間コストによるルート計画アルゴリズムを使用できることであるが、交通監視システムの範囲に含まれる比較的に少ない一部の道路に対するルート計画に限定される。正確度は、地理的な有効範囲を犠牲にすることで得られる。あるいは、ユーザは固定の事前に定義済みのルート区間コスト（例えば、法定制限速度）に基づくルート計画アルゴリズムを使用できる。地理的な有効範囲は広がるが、正確度は低減する。
【課題を解決するための手段】
【０００９】
本発明は、目的地までのルートを計画する方法に関するものであり、該方法は、
（ａ）ルート区間によって道路を規定し、地図データベース中の異なる各ルート区間に関連する時間に依存しない固定の事前定義済みコストを含む地図データベースを使用するステップと、
（ｂ）目的地までのルートの計画を可能にし、１つ以上のルート区間を使用して目的地に到着するまでの推定コストを計算するソフトウェアを使用するステップとを備え、
ソフトウェアを使用するステップは、（i）特定のルート区間について通過されると計画された特定の時間に応じたコストがその特定のルート区間を通過することに適用される、ルート中の１つ以上のルート区間に対する時間に依存するコストと（ii）時間に依存するコストにより規定されないルート中のルート区間に対する時間に依存しない固定の事前定義済みコストと、の組み合わせを自動的に使用することによりルートを計画することを含む。
【００１０】
本発明は、固定の事前定義済みルート区間コスト（例えば、法定制限速度）を含む地理的な有効範囲を、可能な限り時間に依存するより高度なコストと組み合わせる。従って、例えば携帯ナビゲーションデバイスのユーザは、格納された地図データベースが範囲に含む地方の任意の目的地までのルート計画を以前と同様に継続でき、可能な限り、時間に依存するコストを含む交通データを更に使用でき、時間的に予測可能な渋滞の影響が自動バックグラウンドプロセスとして正確に考慮される。それにより、ユーザは、現在存在する渋滞及びそれが行程に与える影響に関して考慮する必要なく、ナビゲーションデバイスにより提供される案内に従って運転し続けることができる。
【００１１】
更なる実現例の詳細は以下を含む。即ち、
特定のルート区間に関連する時間に依存するコストは、測定又は推測されたルート区間通過時間又は車両速度に関し、また、そのコストは一定ではなく且つ事前定義されない。測定値は種々の形態をとってもよく、それについては後述する。一方、特定のルート区間に関連する時間に依存しない固定の事前定義済みコストは、実際の車両交通量又は動きから測定又は推測されず、（i）そのルート区間に関連する道路の種類の関数であるか又は（ii）そのルート区間に適用可能な制限速度の関数である。時間に依存しないコスト及び時間に依存するコストの双方により規定されるルート区間の場合、時間に依存しないコストは時間に依存するコストと組み合わせて使用される。組み合せは、種々の形態をとってもよい。しかし、最も重要なことは、時間に依存するデータが利用可能であっても、ルート区間に対して最も正確なコストを設定する際に依然として時間に依存しないデータに値が存在することである。例えば、時間に依存するデータの品質が悪く、完全に信用できない場合がある。そのデータと適切な相対重みを有する時間に依存しない固定のデータとを組み合わせることにより、妥当な推定値が得られ得る。同様に、時間に依存するデータは特定のルート区間に対して利用可能でない場合があるが、同様のルート区間又は近くのルート区間から知ることができるため、時間依存性を推測することが可能である。しかし、以前と同様に、時間に依存しない固定のデータを重み付けすることが望ましい。
【００１２】
一般に、特定のルートに関連するコストは、目的地に到着するまでにかかる推定時間である。それは、殆どのユーザが最も興味を持っていることだからである。しかし、任意の他のコストも使用できる。コストは、道路区間に関連し且つ運転者又は他の誰かが要求又は提供することを選択できる実際のコスト又は知覚したコストである。例えば、特定のルートに関連するコストは、そのルートに関連する燃料使用量であってもよい。あるいは、道路の価格設定が機能しているか又は渋滞ゾーン等の他の形態の直接支払いが存在する場合に特に有用であるそのルートに関連して課される経済的なコストでもよい。特定のルートに関連するコストは、エンドユーザが演算装置に表示されるメニューリストから選択できる種類のコストである。上記例において、メニューリストは以下の項目の１つ以上を含む。即ち、ルートの通過時間、ルートの経済的なコスト、ルートにわたる燃料使用量、交通停滞。全ての場合において、ソフトウェアは、コスト最小化アルゴリズムの一部としてルートのコストを計算する。
【００１３】
１つの特徴は、車両の特定の運転者の目的地に到着するまでの推定コストは、運転者に関連する運転プロファイルの関数であることである。従って、運転の仕方（例えば、高速／積極的／スポーツ、標準、低速／慎重）がコスト（特に、通過時間及び燃料使用量）に大きな影響を与える。方法は、種々のプロファイルの選択を可能にする（例えば、運転者自身がナビゲーションデバイスに表示されるメニューリストから手動で選択するか、あるいはそのデバイスが実際の運転を監視することにより自動的に選択する）。それらプロファイルは、適切なコストの集合又はコストに適用される重み因子を選択するのに使用される。例えば、スポーツモードの運転者は、非常に渋滞する領域以外では５％低減した通過時間を有してもよい。
【００１４】
上述のように、実際の車両交通量又は動きデータを測定する方法は多く存在する。例えば、これはＧＰＳ軌跡（通常、一定の時刻又は距離間隔におけるＧＰＳの位置データのレコード）を使用して行なわれる。ＧＰＳ軌跡は、ルート区間に沿って移動している車両中のＧＰＳを使用するナビゲーションデバイスにより格納される。ＧＰＳ軌跡は、デバイスによりセルラ無線ネットワークを介して交通監視システムに直接送出されるか、あるいはデバイスにより交通監視システムに直接送出される。ＧＰＳ軌跡は、ピコネット又は他の形態の接続を介してデバイスに接続された移動電話により送出されるか、あるいはデバイスがＰＣとドッキングされる場合にはデバイスにより交通監視システムに送出される。
【００１５】
実際の車両交通量又は動きの測定は、移動電話の場所を測定することにより達成される。これは、移動電話から基地局への信号トラフィックを受動的に監視することにより行なわれる。実際の車両交通量又は動きの測定は、道路のループセンサを使用して達成されるか、あるいはカメラを使用するシステム（例えば、ナンバープレート認識システム）を使用して達成されるか、あるいはラジオビーコンを備えた車両を使用して達成される。
【００１６】
時間に依存するコストは、動的に更新可能である。従って、交通状態が変化すると、それら変化は交通監視システムにより検出され、変更されたコストはルート計画ソフトウェアにより使用される。これは、事故や他の予測不可能な事象が発生した場合も含む。リアルタイムの動的な更新は非常に望ましい。
【００１７】
ルート区間に関連する時間に依存するコストは、時間に関連する種々のパラメータのうちの１つ以上のパラメータの関数である。例えば、それらは以下のパラメータの関数であってもよい。即ち、
・日中又は夜間の時間、
・曜日、
・祝祭日、
・学校の休日、
・更に一般的には、ルート区間のコストに影響を与える可能性のある任意の事象；又はルート区間のコストに与える可能性のある影響を推測できる任意の未来の状況。
【００１８】
上記方法を使用すると、１つ以上の目的地までのルートを計画でき、各目的地への到着時間は現在の制限速度に基づく方法より非常に正確である。
【００１９】
本発明の別の面によるデバイスは、
（ａ）地図データベースであり、ルート区間によって道路を規定し且つ地図データベース中の異なる各ルート区間に関連する時間に依存しない固定の事前定義済みコストを含む地図データベースと、
（ｂ）目的地までのルートの計画を可能にし、１つ以上のルート区間を使用して目的地に到着するまでの推定コストを計算するソフトウェアと、
によりプログラムされるナビゲーションデバイスであって、
デバイスは、（i）特定のルート区間について通過されると計画された特定の時間に応じたコストがその特定のルート区間を通過することに適用されるような、ルート中の１つ以上のルート区間に対する時間に依存するコストと（ii）時間に依存するコストにより規定されないルート中のルート区間に対する時間に依存しない固定の事前定義済みコストとの組み合わせを自動的に使用することによりルートを計画できる。
【００２０】
それは、目的地までの最小コストのルート、例えば最速のルート、燃料使用量が最小であるルート、最も経済費用の低いなルートを計算できるデバイスである。時間に依存するコストは、デバイスにプッシュされるか又はデバイスによる要求時にデバイスに送出される。帯域幅の効率に対しては、デバイスにより受信された時間に依存するコストが道路の種類の分類に制限される。
【００２１】
デバイスは、地図データベースを含む同一のメモリ上に時間に依存するコストを含むことができる。従って、１つの方法は、完全な地図データベース及びデータベース中の多くのルート区間に関連する時間に依存するコストを含むメモリカード又は他のメモリ物理フォーマットを配布することである。あるいは、デバイスがサーバ、すなわちＯＴＡ（over-the-air）からデータをダウンロードできるインターネットに接続されたＰＣとドッキングされる場合、デバイスは時間に依存するコストを入手でき、時間に依存するコストはデバイス自体のメモリ（通常、ハードドライブ又は固体メモリ）に格納される。
【００２２】
別の方法は、リモートサーバが出発地から目的地までの動きに関連するコストをデバイスに送出することである。サーバは、時間に依存するコストを最近のデータで補足することを可能にするリアルタイムの交通情報出力を受信する。デバイスがリアルタイム又は最近の交通データ、あるいは渋滞情報をサーバから受信する場合、デバイスはそのデータ又は情報を自動的に使用して最適なルートを再計算する。
【００２３】
また、
（ａ）デバイス及びサーバは、それぞれ別個に時間に依存するコストを使用でき、
（ｂ）デバイスは、再計算した最小コストのルートをサーバに通知でき、
（ｃ）サーバは、計算した最小コストのルートがデバイスにより計算されたルートと異なる場合にデバイスに通知を送出できる。
【００２４】
サーバが単にルート間の相違を規定する通知をデバイスに送出する場合、帯域幅は節約される。
【００２５】
別の方法として、
（ａ）デバイス及びサーバは、それぞれ別個に時間に依存するコストを使用し、
（ｂ）デバイスは、最近のデータが有効である道路区間を識別し、サーバからその最近のデータを要求する。
【００２６】
任意の事象において、ユーザが到着したい時間を規定する場合、デバイスは行程の最適な出発時間を提案できる。
【００２７】
デバイス自体は、ＧＰＳを使用するナビゲーションデバイスであってもよい。デバイスは、ＧＰＳ等の位置探査システムを有する移動電話であってもよい。デバイスは、TomTomのＧＯ等の携帯ナビゲーションデバイスであってもよく、あるいは自動車に恒久的に組み込まれてもよい。
【００２８】
他の面は以下の通りである：
時間の関数として交通速度又は通過時間データを測定し、道路の区間に対する時間に依存する交通速度又は通過時間の履歴データベースを生成し、且つ少なくともそのデータベースの一部又はその内容を共有して上記方法の実行を可能にする交通監視システムである。
【００２９】
ルート計画ソフトウェアにより使用される場合に上記方法の実行を可能にするように適応されるある領域のデジタル地図であり、地図は、少なくとも道路区間の一部に関連する時間に依存するコストを規定するデータと共に道路区間を規定するデータを含む。
【００３０】
上記方法を使用してルートを計画するように動作可能な組込みナビゲーションシステムを含む自動車。
【発明を実施するための最良の形態】
【００３１】
特定の行程をとりたい運転者に道路網におけるルートを提案するための種々の機能が存在する。ここで、行程は、単純に２地点間で指定されてもよく、あるいは任意の順番で訪れる必要のある複数の場所を含むより複雑な行程であってもよい。これは、配達を行う運転者がとる行程の種類であってもよい。目的は、行程の形式に関わらず、その行程に関連するコストを最小化することである。最も明らかなコストは時間であるが、その行程をとるのに使用される燃料等の任意の他のコストが関連する場合がある。ユーザは、使用される道路の選択を制限できる。例えばいくつかの種類の営業用の車両は、都市圏外にいる場合に幹線道路以外の全てのルートの使用を禁止される。最も一般的には、それら機能は、ルートの区間にコストを割り当て且つ分岐点及びルートのグラフにコスト最小化アルゴリズム［Dijkstra］を適用するアルゴリズムをカプセル化するコンピュータシステムとして実現される。単純な例において、コストは、ルート毎に固定されており、ルートの標準速度（通常、その値は当該道路の制限速度であるか又は制限速度から得られる値である）で移動する場合のルートに沿った行程にかかる時間である。これを静的なコスト関数と呼ぶ。
【００３２】
これは、混雑時及び閑散時による変動等のルートに沿う潜在的な速度の変動を考慮していない。また、道路の制限速度が道路の使用可能な安全速度の非常に低品質な予測因子であるということを考慮していない。
【００３３】
ある期間にわたり道路のコストが変動する問題を解決するために、アルゴリズムは時間に依存するコストをルートに付加するように変更される。ルーティングアルゴリズムへの入力は、最適なルートに要求される時間を含み、関連する時間における適切なコストは各ルート区間に適用される。そのようなシステムの課題は、ルートに対して適切なコスト関数を提供することである。システムは混雑時により高いコストを割り当てることにより合成コスト関数を生成できるが、個々の道路は個々の渋滞パターンを有する傾向にある。従って、時間によって変動するコストは、実際のコストの改善された推定値であるが、完璧な値とは大きく異なる。
【００３４】
本発明は、より正確な運転者ルーティングシステムを与えるために、道路に対してより適切なコスト推定値を提供するという課題に対処する。交通監視システム（又は交通監視システムの履歴出力）がルーティングシステムに組み込まれる。監視システムにより与えられる履歴交通情報は、関心のあるルート及び時間に対するコストの予測値を提供するために処理される。コスト最小化アルゴリズムはルート区間の予測コストに対して適用され、提案された１つ以上のルート及びそれらの合計の予測コストを生成する。
【００３５】
新しいシステムが時間で変動するコスト推定値及びルート候補を提供する。そこで、本実施形態では、行程に対して最適なルートとして元々提案されたものを使用する運転者が、道路状態が動的に変化するにつれて、最適なルートに追従し続けることを保証するためのフレームワークについても説明する。
【００３６】
また、新しいシステムはルーティングサービスを更に改善する。例えば新しいシステムは、選択した時間ウィンドウ内での好適な運行時刻（行程の最小コストを結果として与える運行時刻）を提案するように適応される。
【００３７】
本発明は、特定の移動及び出発又は到着時間に対して最適化されたルート計画及び移動時間推定値を生成する方法及びシステムを提供し、最適な出発時間を提案するのにも使用さ得る。本発明は、交通監視システムにより生成されたデータ及び予測値を使用して、ルート区間の特定の時刻に対する正確な移動時間予測値を提供する。本発明は、従来のルーティングアルゴリズムと組み合わされると、発生する可能性のある交通状態を考慮して行程に対して最適なルートが選択されるのを可能にする。特に上述したように、実施例は、固定の事前定義済みルート区間コスト（例えば、法定制限速度）を含む地理的な有効範囲を可能な限り時間に依存するより高いコストと組み合わせる。従って、例えば携帯ナビゲーションデバイスのユーザは、格納された地図データベースがその範囲に含む地方の任意の目的地までのルート計画を以前と同様に継続でき、可能な限り、時間に依存するコストを含む交通データを更に使用でき、時間的に予測可能な渋滞の影響が自動バックグラウンドプロセスとして正確に考慮される。それにより、ユーザは、現在存在する渋滞及びそれが行程に影響を与えるかに関して考慮する必要なく、ナビゲーションデバイスにより提供される案内に従って運転し続けることができる。
【００３８】
図１にシステムを示す。システムは以下を具備する。
・交通監視システム１。
・ルーティングシステム２。
【００３９】
これら２つのシステムが組み込まれ、交通監視システム１は、ルーティングシステム２のコスト関数７により使用される通過時間予測機能３を提供し、時間に依存する正確な道路区間コストを提供する。
【００４０】
１．交通監視システム（ＴＭＳ）
Applied Generics社のRoDIN24［RoDIN24］等の交通監視システム１は、指定された地理的領域の交通をいくつかの機構を介して観察する収集／監視コア４を含む。
【００４１】
地理的領域内において、道路網は短い個別の区間に分割される。大きく離間された分岐点の間に複数の区間が存在する場合もあるが、通常、区間は分岐点で終了する。コアの内部の処理モジュールは以下のうちの一方又は双方を生成する：
・データベース５に格納された道路区間に対する履歴通過時間情報。規定の頻度で、道路区間を通過する現在の時間に対するシステムの推定値が、道路区間の交通に関連してシステムが生成する他のパラメータと共にデータベースに記録される。通過時間推定値を計算する方法は、交通監視システムに依存する。RoDIN24において、通過時間推定値は、システムが高い信頼性を置いている移動電話が、当該区間を通過する動きから得られる。国際公開ＷＯ０２４５０４６号を参照（ＷＯ０２４５０４６を引用することによってその内容をここに合体する）。
・渋滞情報及び通知６。システム６は、非常に渋滞している（予想された道路の速度より非常に低速で移動している）道路区間を識別し、協定されたプロトコルを使用して興味のあるクライアントに通知を発行する。
【００４２】
１．１ 通過時間の予測
交通監視システム１は、通過時間予測モジュール３により改善される。これは、任意の要求された未来の時間において、ＴＭＳ１の範囲内で任意の道路区間にわたる予想通過時間の推定値を提供するように設計される。道路の制限速度での通過時間を常に供給する通過時間予測モジュール３は、このシステムの退化した例であり、ルーティングシステムに組み込まれる場合に従来の静的な方法でルート予測を実現する役割を果たすことが分かる。従って、履歴データベース５又は渋滞情報／通知システムが有意義なデータを提供できない場合、デフォルト位置では、通過時間は制限速度の関数、すなわち従来の時間に依存しない固定のデータである。
【００４３】
好適な実施形態において、通過時間の予測は、履歴通過時間情報５の自動解析及び現在の渋滞情報６との統合に基づく。予測は、近い未来の全ての区間に対して継続的に実行されてもよく、あるいはルート計算の要求が特定の道路区間の予測通過時間を必要とする時の要望に応じて実行されてもよい。
【００４４】
交通の調査において、カレンダを日の種類に分類し、特定の種類の日において、混雑時、閑散時、日中、夜間等に時間を分類するのが一般的である。日の種類には以下のものがある：
・平日
・他の平日とは異なるパターンになる傾向がある金曜日
・土曜日
・日曜日
・祝祭日
【００４５】
年内の、学校が学期中であるか又は休暇中である時期は、更に時間が分割される。
【００４６】
そのようなカレンダをＴＭＳ１への入力として規定することにより、履歴データは適切なカテゴリに割り当てられる。各カテゴリ内において、短い時間ウィンドウ内の通過時間推定値がグループ化されてもよい。１５分は現実的なウィンドウの大きさである。履歴情報は、以下の形態で体系化される：
・平日、学校の学期中、０８：００〜０８：１５、推定通過時間は平均４３分
・金曜、学校の休暇中、０８：３０〜０８：４５、推定通過時間は平均２７分
【００４７】
通過時間予測３を実行する１つの機構は、上述したカテゴリような履歴情報カテゴリを使用することである。特定の時刻における行程に対する予測通過時間は、その時刻を含むカテゴリの平均通過時間値として与えられる。
【００４８】
当該機構の改善において、渋滞情報システム６により現在観察される異常な出来事及び渋滞が考慮される。観察された最新の通過時間は、それらのカテゴリの予測値と比較され、未来の予測値は、最近観察された通過時間と最近予測された通過時間との比に比例して変倍される。遠い未来の通過時間予測の場合、変倍は適用されるべきではない。更に一般的には、未来における予測の距離が大きくなるにつれ、予測は観察された値を平均の履歴の値に減衰させるべきである。
【００４９】
予測機構が非常に洗練されることは明らかである。最も重要な改善点は、履歴情報が入手可能であり、当該地理的領域のルート区間に対する通過時間のより正確な予測値を生成するために使用されることである。しかし、そのような情報がない場合、従来の時間に依存しない静的なコスト情報が使用される。
【００５０】
２．ルート探査器
ルート探査は、ネットワークのリンクにコストを割り当てる任意のルート探査アルゴリズムを使用してシステム２において実行される。動的なコスト関数は、ルーティングアルゴリズムに単純に取り入れられる。
【００５１】
２．１ 動的なコスト関数
動的なコスト関数は、道路区間及び関心のある（或いは未来の）時間の関数である。これは、道路区間のみの関数である静的なコスト関数とは対照的である。最も一般的な静的なコスト関数７は制限速度での通過時間であるが、他のコスト関数８が選択されてもよい。適切な動的なコスト関数は、ＴＭＳ１から通過時間予測機構を使用することにより実行される。コスト最小化アルゴリズム９が特定の移動時間に対して適用される場合、その動的なコスト関数は、より正確な予測行程時間及び最適により近いルートの選択を結果として与える。
【００５２】
２．２ Dijkstraによるルーティング
最短経路９がグラフのノード間で計算されるのを可能にする周知のアルゴリズム［Dijkstra］がある。これは、道路網の最短ルートを発見するのに採用される標準アルゴリズムである。Dijkstraのアルゴリズムにおいて、固定の重みがグラフの各端部に付加される。通常の道路ルーティングに対するコストは、道路区間に付加された固定の制限速度での道路区間の通過時間である。
【００５３】
動的なコスト関数を使用する場合、グラフの端部のコストは一定の値ではなく、時間と共に変動する。しかし、アルゴリズムに対して必要な僅かな拡張を行なうことで、特定の出発場所及び時間からの最小コストの経路が計算されることが分かる。実際には、１つのコストのみが特定の端部／道路区間に適用され（アルゴリズムの弛緩段階の間）、このコストが動的なコスト関数から入手可能であるため、この応用例におけるアルゴリズムの正確度はすぐに証明される。
【００５４】
この実現例において、いくつかのルート区間に対する固定の事前定義済みルート区間コスト（例えば、法定制限速度）が使用されるが、可能な限り他のルート区間に対する時間に依存するより高いコストが使用される。従って、例えば携帯ナビゲーションデバイスのユーザは、格納された地図データベースが範囲に含む地方の任意の目的地までのルート計画を以前と同様に継続でき、可能な限り、時間に依存するコストを含む交通データを更に使用でき、時間的に予測可能な渋滞の影響が自動バックグラウンドプロセスとして正確に考慮される。それにより、ユーザは、現在存在する渋滞及びそれが行程に影響を与えるかに関して考慮する必要なく、ナビゲーションデバイスにより提供される案内に従って運転し続けることができる。
【００５５】
２．３ 図２の例
動的ルーティングシステムが、ある移動例に関して、どのようにして時間を大きく節約するかを実証する。以下の概略的な道路地図を考慮する。運転者は、LilliputからBrobdingnagに移動したい場合に、運転者がとるべきルートと移動にかかる時間はどの程度か？を予測する。地図には道路に沿う距離と昼休み及び混雑時における速度とが示されている。例えば、30km(60kph/30kph)は、道路区間が３０ｋｍの長さであり、通過時間予測因子が使用可能な最適な情報によると、昼休み（１２：００）には６０ｋｐｈで移動し、混雑時（１６：００）には３０ｋｐｈで移動することを示す。
【００５６】
運転者のオプションが考慮される。運転者は、Blefuscu又はLaputaを経由して移動できる。全ての道路の制限速度が９０ｋｐｈであると仮定すると、Blefuscuを経由する移動の方が短く、従来のルーティングシステムは常にこのルートを提案するだろう。以下では、動的なコスト関数を使用してルーティングを検査する。
【００５７】
昼休み
１．１２：００において、LilliputからBlefuscuまでは６０ｋｐｈで３０分かかる。１２：３０において（運転者がBlefuscuに到着した時）、Brobdingnagまでの移動には６０ｋｐｈで２０分かかり、２０分が追加される。合計の移動時間は５０分である。
２．１２：００において、LilliputからLaputaまでは６０ｋｐｈで２０分かかる。１２：２０において（Laputaに到着する）、Brobdingnagまでの移動には６０ｋｐｈで４０分かかり、４０分が追加され、合計の時間は６０分である。
従って、昼休みにはBlefuscuを経由して移動した方がよいことは明らかである。
【００５８】
混雑時
１．１６：００において、LilliputからBlefuscuまでは３０ｋｐｈで６０分かかる。運転者は１７：００にBlefuscuに到着し、２０ｋｐｈでBrobdingnagまでの２０ｋｍを移動するには更に６０分かかる。移動には合計で１２０分かかる。
２．１６：００において、LilliputからLaputaまでは３０ｋｐｈで４０分かかる。運転者は１６：３０にLaputaに到着し、４０ｋｐｈでBrobdingnagまでの４０ｋｍを移動するには更に６０分かかる。移動には合計で１００分かかる。
従って、運転者は、混雑時にLaputaを経由する移動を選択することにより２０分の節約となる。
【００５９】
３．選択ルートの更新／監視
ルーティングシステムが運転者に対してルートを計算した場合、運転者がルートを通過している間に道路の状態が突然変化する場合がある。運転者が最適なルートをとっていることをリアルタイムで保証するルーティングシステムの実現例が構成され得る。これは以下のことを必要とする：
・運転者は、ルート上の到達した位置を示すためにルーティングシステムと接続している必要がある。代替システム（fallback）として、提案したルートの速度に基づいてシステムが運転者の位置を推定してもよい。
・ルーティングシステムは、運転者の現在の位置から目的地までのルートを周期的に再計算する。
・計算されたルートに変更が生じた場合、ルーティングシステムは、通信機構を使用して運転者に通知する。
【００６０】
３．１ 効率的な分散動的ルーティングシステム
動的ルーティングを提供するシステムの一般的な実現例は、パーソナルナビゲーションシステム（ＰＮＳ）をユーザの車両に配置するか又はユーザとともに移動可能な形態で配置する。ＰＮＳは、交通監視システムを含む固定ネットワーク相互接続システムである中央ナビゲーションシステム（ＣＮＳ）と通信する（間欠的に）。システムは、ＰＮＳとＣＮＳとの間に分散されていると考えられる。
【００６１】
ＰＮＳとＣＮＳとの間の通信システムの従来技術（例えば、ＧＰＲＳ）は、一般に広帯域、短い待ち時間及び連続通信を提供しないため、これよる通信の課題は実現例のアーキテクチャにおいて対処される必要がある。
【００６２】
更に、システムが多くのＰＮＳを含む場合、ＣＮＳにおいて多くの計算を実行するコスト、特にルーティングを行なうコストは非常に高い。同様に、ＣＮＳにおいて全てのＰＮＳの代わりに状態を維持すると、ＣＮＳにおいて展開される必要がある計算資源及び複雑度は非常に増加する。
【００６３】
分散動的ルーティングシステムにおいて、ルーティング能力はＰＮＳのみに配置されてもよいし、ＰＮＳとＣＮＳとの間で共有されてもよい。
・ＰＮＳのみに配置
・ＰＮＳは、履歴データベースの最近のスナップショットを含む。
・ＰＮＳは、ＣＮＳから渋滞情報を受信する。
・ＰＮＳは、通過時間予測を実行し、その近似値に基づくルーティングシステムを実現する。
・ＰＮＳとＣＮＳとの間で共有
・ＰＮＳ及びＣＮＳはユーザに対してルートを計算する。
・ＣＮＳ情報は常に最適である。
・ＣＮＳ及びＰＮＳは、ＰＮＳがユーザに対して最小限の意外性を含む常に十分に適切な（又はより適切な）ルートを提供することを保証しようとする。
【００６４】
ＣＮＳのみにおけるルーティングシステムは、ＣＮＳとＰＮＳとの間の接続性が十分に保証されないことの影響を受ける。そして、いずれの場合においても現在の技術のＰＮＳはＰＮＳにおける静的なルーティングを使用する。従って、単純にＰＮＳルーティングの退化した例として考えられるものを常に提供するものとなる。
【００６５】
種々の代替例が種々の利点を有する。そこで、各々が低通信コストで高速且つ正確なルート選択を提供する目的で実現される方法を検討する。最後に、ＣＮＳに対してステートレスであり且つ帯域幅のコストが低いという利点を有するルーティングシステムを説明する。
【００６６】
３．２ ＰＮＳルーティング
ＰＮＳは、ルーティングを行なう場合、ＰＮＳが関心ある地理的領域をＣＮＳに示す必要がある。これは、任意の検知可能なルートが常に領域内となるように十分な余裕を有するルートの出発地及び目的地を取り囲む領域である。これをルーティング可能領域と呼ぶ。ＣＮＳは以下のことを保証する必要がある。
１．ＰＮＳは、ルーティング可能領域の道路区間をＰＮＳにおいて情報により予測された速度と非常に異なる速度で移動している（従って、異なるコストを有する）場合に更新データを受信する。通常、これは、道路区間において予期しない遅延（渋滞）が存在することを意味する。
２．ＰＮＳは、ルーティング可能領域の最新履歴ビューを有する。履歴データベースは、徐々に変化する傾向があり、ＣＮＳは、ルーティング可能領域における期限切れとなった履歴情報の動的更新データをＰＮＳに提供してもよい。
【００６７】
要約すると、ＣＮＳは、ＣＮＳ自体が生成する最適なルートに最も近いルートを生成するのに十分に適切なルーティング可能領域のビューをＰＮＳが有することを保証する。ＰＮＳルーティングはリアルタイムの利点を有する。ＰＮＳがＣＮＳと接続されているか否かに関わらず、ルートを再計算するため且つ（ことによると）運転者の方向を変更するために更新データがＣＮＳから受信されるまで、周知の最適なルートが計算されて運転者により使用される。ルートが再計算され且つ運転者に利用される。
【００６８】
この形態のＰＮＳルーティングの１つの問題は、ＣＮＳがＰＮＳに更新データをプッシュできるように、ＣＮＳがＰＮＳのルーティング可能領域を記録する状態を維持する必要があるか、あるいはＰＮＳがルーティング可能領域の予測関数に対する更新データのためにＣＮＳをポーリングする必要があることである。
【００６９】
３．３ 共有ルーティング
ＰＮＳ及びＣＮＳは、ルート上の運転者を案内することに参加できる。ＰＮＳ及びＣＮＳが接続されている場合、それらＰＮＳ及びＣＮＳはルートを計算でき、それらが選択したルートの相違点に関して交渉できる、あるいは双方が同一ルートを選択した場合はそのままとする。
【００７０】
例えば：
１．運転者は（ルートＡＢ）についてＰＮＳに問い合わせる。
２．ＰＮＳは（ＡｒｓｔＢ）を計算する。
３．ＰＮＳは（選択したルートＡＢ（ｒｓ））をＣＮＳに送出する。それは、
・採用するように要求されたルート
・ＰＮＳが選択した第１の経由地点（すなわち、第１のルート区間）である。
４．ＣＮＳは、ルーティングシステムを使用して（ルートＡＢ）を計算する。定義上、これにより、この技術が生成できる可能な最適なルートが与えられる。（ＡｘｙｚＢ）
５．ＣＮＳは、ＣＮＳが生成したルートとＰＮＳが生成したルートとを比較する。この例において、ＣＮＳはｘ、ｙ及びｚを経由してルーティングし、これはＰＮＳに対して全く異なるルートであるため、ＰＮＳに知らせる必要があると考えられる。
６．相違点がある場合、ＣＮＳはそれら相違点を運転者に送信する。特に、ルートの開始時に相違点がある場合、単に迅速に送信する必要がある。ＣＮＳは、第１の相違点を単に送信する必要がある。ＰＮＳは、相違点を受信すると、ＰＮＳにより供給されたルート上の次の経由地点から残りのルートを計算できる。従って、ＣＮＳはＰＮＳに（選択したルートＡＢ（ｘ））を通知し、ＰＮＳは（ｘを経由するルートＡＢを）計算して、適切なルート（ＡｘｙｚＢ）として計算する。
・後でルート上に相違点が存在する場合、運転者がその相違点に到達した時には解消される一時的な渋滞が原因である相違点である可能性がある。そのため、ＰＮＳは、運転者がルートのその相違点に近付くまでルートを送信しないようにしてもよい。
７．ＣＮＳが後で異なるルートを再計算する場合、ＣＮＳは運転者のルートを監視し続けて通知を送出する。
【００７１】
この形態及び関連する形態の共有ルーティングは、帯域幅において非常に効率的である。正確な動的なコスト関数を仮定すると、その共有ルーティングはルート探査に対してほぼ最適である。共有ルーティングに関する主な問題は、ＣＮＳにおいて多くの計算及び状態コストがかかることである。
【００７２】
３．４ 図３の低ネットワーク負荷のＰＮＳルーティング
システムがＰＮＳルーティングを使用する場合、その結果として、履歴情報を符号化するＰＮＳにおける動的なルーティング関数及びＣＮＳから要求された非常に少量の遅延情報を使用して、十分に適切なルーティングが行なわれる。重要な点は、ＰＮＳ上でルーティングを行ない、コストがＰＮＳ上でＣＮＳにより計算される最新の値で更新される必要があるいくつかの道路区間を識別することである。これにより、ＰＮＳは、動的なコスト関数を使用してＣＮＳにより計算されたような最適なルートに近付くようにルートを改善できる。
【００７３】
以下、本機構を説明する。
１．ＰＮＳは、ルートＡ−Ｂに対してルーティング可能領域を構成し、ＣＮＳコスト関数によるコストがＰＮＳコスト関数によるコストより低いコストであるルーティング可能領域中の任意の道路区間に対して、ルートが使用される時間にわたるＣＮＳコスト値をＣＮＳに要求する。ＰＮＳが保持する履歴データベースのバージョンをＣＮＳに通知できるため、ＣＮＳはＰＮＳが使用しているコスト関数を認識している。ＣＮＳは、ＰＮＳの母集団に存在する全ての履歴データベースの符号化を保持するため、道路区間のコスト値がＰＮＳに返される必要があるかを任意の道路区間に対して判定できる。区間毎の最小コスト差dsが規定されるため、ＣＮＳは、道路区間及びＣＮＳコスト値（segment，costcns(segment)）をＰＮＳに送出する。それら値は、costcns(segment)+ds ≦ costpns(segment)を満足する。すなわち、ＣＮＳコスト値は少なくともdsだけ小さい。事実上、そのような選択した道路区間の数は少なく、従ってメッセージサイズ及びコストは小さい。
【００７４】
２．ここで、ＰＮＳは変更されたコスト関数routecostpnsを構成する。これは、先の段階で返されたより少ないコストの道路区間に対してＰＮＳにより返されたコスト値を割り当て、全ての他の道路区間に対してＰＮＳにより保持される履歴の値を割り当てる。ＰＮＳは、routecostpnsを使用してＡからＢへのルーティング計算を実行する。この計算により選択されたルートは、候補ルートbestroutepnsと呼ばれる。ＣＮＳコスト関数が認識している異常に高いコスト（遅延道路区間に相当する）について、変更されたＰＮＳコスト関数が認識していないため、ＣＮＳコスト関数routecostcnsは、routecostpnsより大きいコストをそのルートに付加するかもしれない。しかし、先の段階のＰＮＳコスト関数の変更のために、bestroutepnsは、bestroutecnsと呼ばれるroutecostcnsによる最小コストルートよりそれ程大きくないＰＮＳによるコストを有する。実際には、routecostpns(bestroutepns)≦routecostcns(bestroutecns)+ segmentcount(bestroutecns)*dsである。routecostpns(bestroutepns)のroutecostcns(bestroutepns)に対する類似性を段階１において道路区間及びコストを送信するのに必要とされる時間及びネットワーク帯域幅と相殺するために、システムにおいて使用されるdsの値が選択される。
【００７５】
３．ここで、ＣＮＳがＰＮＳにより選択された候補ルートに割り当てるコストroutecostcns(bestroutepns)は、ＰＮＳが割り当てるコストより非常に悪くないかのチェックが残っている。そのために、ＰＮＳはbestroutepnsの道路区間に対するＣＮＳコスト値を要求する。ＣＮＳは、それら道路区間に対するコスト値をＰＮＳに供給し、ＰＮＳは、ＣＮＳからのそれら道路区間コスト値を取り込むためにＰＮＳのコスト関数を更新する。ＣＮＳがＰＮＳの履歴データベースのバージョン番号を保存するか、あるいはＰＮＳが要求に応じてバージョン番号を再び送出する場合、ＣＮＳは、ＰＮＳがデータベースに保持する値とは異なる道路区間コスト値のみを返信するだけでよい。ここで、ＰＮＳコスト関数はroutecostpnsupdatedである。
【００７６】
４．ＰＮＳは、ここではルート上の道路区間に対するＣＮＳにより供給されたコスト値を使用して、先に選択した候補ルートのコストroutecostpnsupdated(bestroutepns)を計算する。尚、routecostpnsupdated(bestroutepns)=routecostcns(bestroutepns)である。受け入れ可能な最大のコスト差dextrarouteが規定され、bestroutepnsがこの段階でクライアントに提供するためのルートとして受け入れられるかをテストする。bestroutepnsは、routecostpnsupdated(bestroutepns)≦routecostpns(bestroutepns)+ dextrarouteの場合にのみ受け入れられる。システムにより使用されるdextrarouteの値は、routecostpnsupdated(bestroutepns)のroutecostcns(bestroutecns)に対する類似性を機構が消費する時間及びネットワーク帯域幅と相殺するように選択される。
【００７７】
５．bestroutepnsが受け入れられた場合、ルート選択の処理は完了し、bestroutepnsはＰＮＳのユーザに発行される。
【００７８】
６．bestroutepnsが受け入れられなかった場合、機構は段階２に戻る。但し、routecostpnsupdatedが新しい候補ルートbestroute'pnsを選択するのに使用される。bestroute'pns=bestroutepns（あるいは、更なる繰返しにおいては、先に選択された任意の候補ルート）である場合、bestroute'pnsはすぐに受け入れられる。bestroute'pns=bestroutepnsでない場合、システムは同一の処理を再び実行し、routecostpnsupdatedを更新するbestroute'pnsに対するＣＮＳコスト値を要求し（段階３）、routecost'pnsupdated(bestroute'pns)を計算する（段階４）。
【００７９】
７．最終的に、通常は非常に迅速に、dextrarouteの適当な選択を仮定すると、システムが生成した候補ルートの１つが受け入れられる。コスト関数routecostpnsupdatedが最終的にroutecostcnsに安定し、この時、routecostpnsupdated=routecostpnsであり且つ現在の候補ルートに対する受け入れ条件routecostpnsupdated(bestroutepns)≦routecostpns(bestroutepns)+ dextrarouteがすぐに満足されるため、ＰＮＳは最終的に候補ルートを受け入れる必要があることが分かる。
【００８０】
８．システムは、ＰＮＳのユーザに受け入れたルートを発行する。
【００８１】
９．任意の段階において、ＰＮＳとＣＮＳとの間の接続性が失われる場合、ＰＮＳはユーザに現在の候補ルートを発行できる。実際には、ルートの第１段階をすぐに発行し、運転者が近付く次の分岐点からルーティングするのが最適であることが多い。ユーザがルートを要求した後にシステムからの初期応答をコンマ何秒以上待つ必要がない場合、ユーザはシステムとの対話がより自然に見える。
【００８２】
１０．運転者が目的地に向けて移動する間、システムは受け入れたルートの残りの道路区間に対するコストを周期的に要求できる（段階３のように）。ルートの更に先の方で遅延が大きくなる場合、ＰＮＳは、段階４のアルゴリズムを再開することにより現在の位置から自動的に再度ルーティングできる。
【００８３】
低コストのＰＮＳルーティングは、ＰＮＳ（従って、ＰＮＳルーティング）において全てのルーティング計算を実行するが、それと同時にＣＮＳにおいて最小の状態を必要とし、帯域幅に対する要求を最小にする。低コストのＰＮＳルーティングは、ＣＮＳとの接続がない場合に有用であり続けられるというＰＮＳルーティングの利点を有する。更に、低コストのＰＮＳルーティングは、ＣＮＳにおいて動的ルーティングを使用して生成されたルートのコストに事実上十分に近いコストのルートを生成するため、動的ルーティングに関連するほぼ全てのコストの節約は実際に実現される。
【００８４】
３．５ 通信コストの低減
ルート選択に対する役割が分割されても、多くの技術を使用して、データ送信のコストは低く維持される：
【００８５】
位置に関係した区間番号付け
ＰＮＳ及びＣＮＳが通信している場合、運転者及びＰＮＳの正確な位置はほぼ常にＣＮＳにより必要とされる。殆どの関心道路区間が運転者（又は、運転者の要求ルート）にとって局所的であるため、別のルート番号付けシステムは、最も一般的に送信される道路区間を識別するために数ビットのみ必要であるＰＮＳとＣＮＳとの間に一時的に適切に配置される。
【００８６】
ルートに関係した区間番号付け
ＡからＢへのルートは、ルート上の通過した各分岐点における出口をカウントすることにより全体が説明される。各道路区間が非常に長い区間である場合、ルートの非常にコンパクトな表現が結果として得られる。
【００８７】
通常と同様に、ルートの大きな区間が同一の道路上にある場合、ランレングス符号化の形式が使用されてもよい。ルートは(3, 13, 2, 28, 2, 15)で表されてもよく、以下のことを意味する。
・次の分岐点の第３の出口
・次の１３個の分岐点を通り直進
・１４個目の分岐点における第２の出口
・次の２８個の分岐点を通り直進
・２９番目の分岐点における第２の出口
・１５個の分岐点を通り直進
・到着
【図面の簡単な説明】
【００８８】
【図１】図１は、本発明の一実施形態に係るルート計画システムを示す概略図である。
【図２】図２は、行程に対して最適化されたルートを選択するための動的なコスト関数の用途を示す地図である。
【図３】図３は、分散動的ルーティングシステムの動作を示す概略図である。
【特許請求の範囲】
【請求項１】
目的地までのルートを計画する方法であって、
（ａ）ルート区間によって道路を規定し、地図データベース中の異なる各ルート区間に関連する時間に依存しない固定の事前定義済みコストを含む前記地図データベースを使用するステップと、
（ｂ）目的地までのルートの計画を可能にし、１つ以上のルート区間を使用して前記目的地に到着するまでの推定コストを計算するソフトウェアを使用するステップとを備え、
前記ソフトウェアを使用するステップは、（i）特定のルート区間について通過されると計画された特定の時間に応じたコストが、前記特定のルート区間を通過することに適用される、前記ルート中の１つ以上の前記ルート区間に対する時間に依存するコストと、（ii）前記時間に依存するコストにより規定されない前記ルート中の前記ルート区間に対する前記時間に依存しない固定の事前定義済みコストと、の組み合わせを自動的に使用することによりルートを計画することを含む方法。
【請求項２】
特定のルート区間に関連する前記時間に依存するコストは、測定又は推測された固定でなく且つ事前定義されていない車両速度又はルート区間通過時間に関連する、請求項１に記載の方法。
【請求項３】
特定のルート区間に関連する前記時間に依存しない固定の事前定義済みコストは、実際の車両交通量又は動きから測定又は推測されたものではなく、（i）前記ルート区間に関連する道路の種類又は（ii）前記ルート区間に適用可能な制限速度の関数である、請求項１又は２に記載の方法。
【請求項４】
前記時間に依存しないコストは、前記時間に依存するコストと組み合わせて使用され、時間に依存しないコスト及び時間に依存するコストの双方により規定される前記ルート区間に対して使用される、請求項３に記載の方法。
【請求項５】
特定のルートに関連する前記コストは、前記目的地に到着するのにかかる推定時間である請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
特定のルートに関連する前記コストは、前記ルートに関連する燃料使用量である請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
特定のルートに関連する前記コストは、前記ルートに関連して課される経済的なコストである請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
特定のルートに関連する前記コストは、エンドユーザが演算装置上に表示されるメニューリストから選択できる種類のコストである請求項１乃至７のいずれか１項に記載の方法。
【請求項９】
前記メニューリストは、前記ルートの通過時間、前記ルートの経済的なコスト、前記ルートにわたる燃料使用量、交通停滞のうち１つ以上の項目を含む請求項８に記載の方法。
【請求項１０】
前記ソフトウェアは、コスト最小化アルゴリズムの一部として前記ルートの前記コストを計算する請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
車両の特定の運転者の目的地に到着するまでの推定コストは、前記運転者に関連する運転プロファイルの関数である請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
実際の車両交通量又は動きデータの測定は、前記ルート区間に沿って移動している車両中のＧＰＳを使用するナビゲーションデバイスにより格納されるＧＰＳ軌跡から得られる請求項１１に記載の方法。
【請求項１３】
ＧＰＳ軌跡は、前記デバイスによりセルラ無線ネットワークを介して交通監視システムに直接送出される請求項１２に記載の方法。
【請求項１４】
前記ＧＰＳ軌跡は、前記デバイスにより交通監視システムに直接送出される請求項１１又は１２に記載の方法。
【請求項１５】
前記ＧＰＳ軌跡は、ピコネット又は他の形態の接続を介して前記デバイスに接続された移動電話により送出される請求項１２に記載の方法。
【請求項１６】
前記ＧＰＳ軌跡は、前記デバイスがＰＣとドッキングされる場合には前記デバイスにより交通監視システムに送出される請求項１２に記載の方法。
【請求項１７】
実際の車両交通量又は動きの測定は、移動電話の場所を測定することにより達成される請求項１１に記載の方法。
【請求項１８】
移動電話の場所は、前記移動電話から基地局への信号トラフィックを受動的に監視することにより取得される請求項１７に記載の方法。
【請求項１９】
実際の車両交通量又は動きの測定は、道路のループセンサを使用して達成される請求項１１に記載の方法。
【請求項２０】
実際の車両交通量又は動きの測定は、カメラを使用するシステムを使用して達成される請求項１１に記載の方法。
【請求項２１】
実際の車両交通量又は動きの測定は、ラジオビーコンを備えた車両を使用して達成される請求項１１に記載の方法。
【請求項２２】
前記時間に依存するコストは、動的に更新可能である請求項１乃至２１のいずれか１項に記載の方法。
【請求項２３】
前記時間に依存するコストは、リアルタイムで動的に更新可能である請求項２２に記載の方法。
【請求項２４】
ルート区間に関連する前記時間に依存するコストは、日中又は夜間の時間の関数である請求項１乃至２３のいずれか１項に記載の方法。
【請求項２５】
ルート区間に関連する前記時間に依存するコストは、曜日の関数である請求項１乃至２４のいずれか１項に記載の方法。
【請求項２６】
ルート区間に関連する前記時間に依存するコストは、祝祭日の関数である請求項１乃至２５のいずれか１項に記載の方法。
【請求項２７】
ルート区間に関連する前記時間に依存するコストは、学校の休日の関数である請求項１乃至２６のいずれか１項に記載の方法。
【請求項２８】
ルート区間に関連する前記時間に依存するコストは、ルート区間のコストに影響を与える可能性のある任意の事象の関数である請求項１乃至２７のいずれか１項に記載の方法。
【請求項２９】
ルート区間に関連する前記時間に依存するコストは、ルート区間のコストに与える可能性のある影響を推測できる任意の未来の状況の関数である請求項１乃至２８のいずれか１項に記載の方法。
【請求項３０】
前記目的地は、２つ以上の目的地を含む請求項１乃至２９のいずれか１項に記載の方法。
【請求項３１】
前記方法は、ＧＰＳを使用するナビゲーションデバイスにより実行される請求項１乃至３０のいずれか１項に記載の方法。
【請求項３２】
（ａ）地図データベースであり、ルート区間によって道路を規定し且つ前記地図データベース中の異なる各ルート区間に関連する時間に依存しない固定の事前定義済みコストを含む地図データベースと、
（ｂ）目的地までのルートの計画を可能にし、１つ以上のルート区間を使用して前記目的地に到着するまでの推定コストを計算するソフトウェアと、
によりプログラムされるナビゲーションデバイスであって、
前記デバイスは、（i）特定のルート区間について通過されると計画された特定の時間に応じたコストが、前記特定のルート区間を通過することに適用される、ルート中の１つ以上の前記ルート区間に対する時間に依存するコストと、（ii）前記時間に依存するコストにより規定されない前記ルート中の前記ルート区間に対する、時間に依存しない固定の事前定義済みコストと、の組み合わせを自動的に使用することにより前記ルートを計画できるナビゲーションデバイス。
【請求項３３】
前記デバイスは、前記目的地までの最小コストのルートを計算する請求項３２に記載のデバイス。
【請求項３４】
前記デバイスは、最速のルートを計画する請求項３２又は３３に記載のデバイス。
【請求項３５】
前記デバイスは、燃料使用量が最小であるルートを計画する請求項３２又は３３に記載のデバイス。
【請求項３６】
前記デバイスは、最も経済費用が低いルートを計画する請求項３２又は３３記載のデバイス。
【請求項３７】
時間に依存するコストは、前記デバイスにプッシュされる請求項３２乃至３６のいずれか１項に記載のデバイス。
【請求項３８】
時間に依存するコストは、前記デバイスによる要求時に前記デバイスに送出される請求項３２乃至３６のいずれか１項に記載のデバイス。
【請求項３９】
前記デバイスにより受信された前記時間に依存するコストは、道路の種類の分類に制限される請求項３７又は３８に記載のデバイス。
【請求項４０】
前記デバイスは、前記地図データベースを含む同一のメモリ上に時間に依存するコストを含む請求項３２に記載のデバイス。
【請求項４１】
前記デバイスは、リモートサーバに保持される前記時間に依存するコストにアクセスする請求項３２に記載のデバイス。
【請求項４２】
前記デバイスは、インターネットに接続されたコンピュータとドッキングされ、前記インターネットに接続されたコンピュータを介して前記リモートサーバから前記時間に依存するコストを受信する請求項４１に記載のデバイス。
【請求項４３】
前記リモートサーバは、出発地から目的地までの動きに関連するコストを前記デバイスに送出する請求項４１に記載のデバイス。
【請求項４４】
前記リモートサーバは、前記時間に依存するコストを最近のデータで補足することを可能にするリアルタイムの交通情報出力を受信する請求項４１に記載のデバイス。
【請求項４５】
前記デバイスは、リアルタイム又は最近の交通データ、あるいは渋滞情報を前記リモートサーバから受信し、前記データ又は情報を自動的に使用して最適なルートを再計算する請求項４１に記載のデバイス。
【請求項４６】
（ａ）前記デバイス及び前記サーバは、それぞれ別個に前記時間に依存するコストを使用し、
（ｂ）前記デバイスは、計算した最小コストのルートを前記サーバに通知し、
（ｃ）前記リモートサーバは、計算した前記最小コストのルートが前記デバイスにより計算された前記ルートと異なる場合に前記デバイスに通知を送出する請求項４１に記載のデバイス。
【請求項４７】
前記サーバは、単に前記ルート間の相違を規定する通知を前記デバイスに送出する請求項４６に記載のデバイス。
【請求項４８】
（ａ）前記デバイス及び前記サーバは、それぞれ別個に前記時間に依存するコストを使用し、
（ｂ）前記デバイスは、最近のデータが有効である道路区間を識別し、前記サーバから前記最近のデータを要求する請求項４１に記載のデバイス。
【請求項４９】
前記デバイスは、行程の最適な出発時間を提案できる請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５０】
前記デバイスは、ＧＰＳを使用するナビゲーションデバイスである請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５１】
前記デバイスは、位置探査システムを有する移動電話である請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５２】
前記位置探査システムはＧＰＳである請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５３】
前記デバイスは、自動車に恒久的に組み込まれる請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５４】
時間の関数として交通速度又は通過時間データを測定し、道路の区間に対する時間に依存する交通速度又は通過時間の履歴データベースを生成し、且つ少なくとも前記データベースの一部又はその内容を共有して請求項１に記載の方法の実行を可能にする交通監視システム。
【請求項５５】
ルート計画ソフトウェアにより使用される場合に請求項１乃至３１のいずれか１項に記載の方法の実行を可能にするように適応されるある領域のデジタル地図であり、前記地図は、少なくとも道路区間の一部に関連する時間に依存するコストを規定するデータと共に前記道路区間を規定するデータを含むデジタル地図。
【請求項５６】
請求項１乃至３１のいずれか１項に記載の方法を使用してルートを計画するように動作可能な組込みナビゲーションシステムを含む自動車。
【請求項１】
目的地までのルートを計画する方法であって、
（ａ）ルート区間によって道路を規定し、地図データベース中の異なる各ルート区間に関連する時間に依存しない固定の事前定義済みコストを含む前記地図データベースを使用するステップと、
（ｂ）目的地までのルートの計画を可能にし、１つ以上のルート区間を使用して前記目的地に到着するまでの推定コストを計算するソフトウェアを使用するステップとを備え、
前記ソフトウェアを使用するステップは、（i）特定のルート区間について通過されると計画された特定の時間に応じたコストが、前記特定のルート区間を通過することに適用される、前記ルート中の１つ以上の前記ルート区間に対する時間に依存するコストと、（ii）前記時間に依存するコストにより規定されない前記ルート中の前記ルート区間に対する前記時間に依存しない固定の事前定義済みコストと、の組み合わせを自動的に使用することによりルートを計画することを含む方法。
【請求項２】
特定のルート区間に関連する前記時間に依存するコストは、測定又は推測された固定でなく且つ事前定義されていない車両速度又はルート区間通過時間に関連する、請求項１に記載の方法。
【請求項３】
特定のルート区間に関連する前記時間に依存しない固定の事前定義済みコストは、実際の車両交通量又は動きから測定又は推測されたものではなく、（i）前記ルート区間に関連する道路の種類又は（ii）前記ルート区間に適用可能な制限速度の関数である、請求項１又は２に記載の方法。
【請求項４】
前記時間に依存しないコストは、前記時間に依存するコストと組み合わせて使用され、時間に依存しないコスト及び時間に依存するコストの双方により規定される前記ルート区間に対して使用される、請求項３に記載の方法。
【請求項５】
特定のルートに関連する前記コストは、前記目的地に到着するのにかかる推定時間である請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
特定のルートに関連する前記コストは、前記ルートに関連する燃料使用量である請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
特定のルートに関連する前記コストは、前記ルートに関連して課される経済的なコストである請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
特定のルートに関連する前記コストは、エンドユーザが演算装置上に表示されるメニューリストから選択できる種類のコストである請求項１乃至７のいずれか１項に記載の方法。
【請求項９】
前記メニューリストは、前記ルートの通過時間、前記ルートの経済的なコスト、前記ルートにわたる燃料使用量、交通停滞のうち１つ以上の項目を含む請求項８に記載の方法。
【請求項１０】
前記ソフトウェアは、コスト最小化アルゴリズムの一部として前記ルートの前記コストを計算する請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
車両の特定の運転者の目的地に到着するまでの推定コストは、前記運転者に関連する運転プロファイルの関数である請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
実際の車両交通量又は動きデータの測定は、前記ルート区間に沿って移動している車両中のＧＰＳを使用するナビゲーションデバイスにより格納されるＧＰＳ軌跡から得られる請求項１１に記載の方法。
【請求項１３】
ＧＰＳ軌跡は、前記デバイスによりセルラ無線ネットワークを介して交通監視システムに直接送出される請求項１２に記載の方法。
【請求項１４】
前記ＧＰＳ軌跡は、前記デバイスにより交通監視システムに直接送出される請求項１１又は１２に記載の方法。
【請求項１５】
前記ＧＰＳ軌跡は、ピコネット又は他の形態の接続を介して前記デバイスに接続された移動電話により送出される請求項１２に記載の方法。
【請求項１６】
前記ＧＰＳ軌跡は、前記デバイスがＰＣとドッキングされる場合には前記デバイスにより交通監視システムに送出される請求項１２に記載の方法。
【請求項１７】
実際の車両交通量又は動きの測定は、移動電話の場所を測定することにより達成される請求項１１に記載の方法。
【請求項１８】
移動電話の場所は、前記移動電話から基地局への信号トラフィックを受動的に監視することにより取得される請求項１７に記載の方法。
【請求項１９】
実際の車両交通量又は動きの測定は、道路のループセンサを使用して達成される請求項１１に記載の方法。
【請求項２０】
実際の車両交通量又は動きの測定は、カメラを使用するシステムを使用して達成される請求項１１に記載の方法。
【請求項２１】
実際の車両交通量又は動きの測定は、ラジオビーコンを備えた車両を使用して達成される請求項１１に記載の方法。
【請求項２２】
前記時間に依存するコストは、動的に更新可能である請求項１乃至２１のいずれか１項に記載の方法。
【請求項２３】
前記時間に依存するコストは、リアルタイムで動的に更新可能である請求項２２に記載の方法。
【請求項２４】
ルート区間に関連する前記時間に依存するコストは、日中又は夜間の時間の関数である請求項１乃至２３のいずれか１項に記載の方法。
【請求項２５】
ルート区間に関連する前記時間に依存するコストは、曜日の関数である請求項１乃至２４のいずれか１項に記載の方法。
【請求項２６】
ルート区間に関連する前記時間に依存するコストは、祝祭日の関数である請求項１乃至２５のいずれか１項に記載の方法。
【請求項２７】
ルート区間に関連する前記時間に依存するコストは、学校の休日の関数である請求項１乃至２６のいずれか１項に記載の方法。
【請求項２８】
ルート区間に関連する前記時間に依存するコストは、ルート区間のコストに影響を与える可能性のある任意の事象の関数である請求項１乃至２７のいずれか１項に記載の方法。
【請求項２９】
ルート区間に関連する前記時間に依存するコストは、ルート区間のコストに与える可能性のある影響を推測できる任意の未来の状況の関数である請求項１乃至２８のいずれか１項に記載の方法。
【請求項３０】
前記目的地は、２つ以上の目的地を含む請求項１乃至２９のいずれか１項に記載の方法。
【請求項３１】
前記方法は、ＧＰＳを使用するナビゲーションデバイスにより実行される請求項１乃至３０のいずれか１項に記載の方法。
【請求項３２】
（ａ）地図データベースであり、ルート区間によって道路を規定し且つ前記地図データベース中の異なる各ルート区間に関連する時間に依存しない固定の事前定義済みコストを含む地図データベースと、
（ｂ）目的地までのルートの計画を可能にし、１つ以上のルート区間を使用して前記目的地に到着するまでの推定コストを計算するソフトウェアと、
によりプログラムされるナビゲーションデバイスであって、
前記デバイスは、（i）特定のルート区間について通過されると計画された特定の時間に応じたコストが、前記特定のルート区間を通過することに適用される、ルート中の１つ以上の前記ルート区間に対する時間に依存するコストと、（ii）前記時間に依存するコストにより規定されない前記ルート中の前記ルート区間に対する、時間に依存しない固定の事前定義済みコストと、の組み合わせを自動的に使用することにより前記ルートを計画できるナビゲーションデバイス。
【請求項３３】
前記デバイスは、前記目的地までの最小コストのルートを計算する請求項３２に記載のデバイス。
【請求項３４】
前記デバイスは、最速のルートを計画する請求項３２又は３３に記載のデバイス。
【請求項３５】
前記デバイスは、燃料使用量が最小であるルートを計画する請求項３２又は３３に記載のデバイス。
【請求項３６】
前記デバイスは、最も経済費用が低いルートを計画する請求項３２又は３３記載のデバイス。
【請求項３７】
時間に依存するコストは、前記デバイスにプッシュされる請求項３２乃至３６のいずれか１項に記載のデバイス。
【請求項３８】
時間に依存するコストは、前記デバイスによる要求時に前記デバイスに送出される請求項３２乃至３６のいずれか１項に記載のデバイス。
【請求項３９】
前記デバイスにより受信された前記時間に依存するコストは、道路の種類の分類に制限される請求項３７又は３８に記載のデバイス。
【請求項４０】
前記デバイスは、前記地図データベースを含む同一のメモリ上に時間に依存するコストを含む請求項３２に記載のデバイス。
【請求項４１】
前記デバイスは、リモートサーバに保持される前記時間に依存するコストにアクセスする請求項３２に記載のデバイス。
【請求項４２】
前記デバイスは、インターネットに接続されたコンピュータとドッキングされ、前記インターネットに接続されたコンピュータを介して前記リモートサーバから前記時間に依存するコストを受信する請求項４１に記載のデバイス。
【請求項４３】
前記リモートサーバは、出発地から目的地までの動きに関連するコストを前記デバイスに送出する請求項４１に記載のデバイス。
【請求項４４】
前記リモートサーバは、前記時間に依存するコストを最近のデータで補足することを可能にするリアルタイムの交通情報出力を受信する請求項４１に記載のデバイス。
【請求項４５】
前記デバイスは、リアルタイム又は最近の交通データ、あるいは渋滞情報を前記リモートサーバから受信し、前記データ又は情報を自動的に使用して最適なルートを再計算する請求項４１に記載のデバイス。
【請求項４６】
（ａ）前記デバイス及び前記サーバは、それぞれ別個に前記時間に依存するコストを使用し、
（ｂ）前記デバイスは、計算した最小コストのルートを前記サーバに通知し、
（ｃ）前記リモートサーバは、計算した前記最小コストのルートが前記デバイスにより計算された前記ルートと異なる場合に前記デバイスに通知を送出する請求項４１に記載のデバイス。
【請求項４７】
前記サーバは、単に前記ルート間の相違を規定する通知を前記デバイスに送出する請求項４６に記載のデバイス。
【請求項４８】
（ａ）前記デバイス及び前記サーバは、それぞれ別個に前記時間に依存するコストを使用し、
（ｂ）前記デバイスは、最近のデータが有効である道路区間を識別し、前記サーバから前記最近のデータを要求する請求項４１に記載のデバイス。
【請求項４９】
前記デバイスは、行程の最適な出発時間を提案できる請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５０】
前記デバイスは、ＧＰＳを使用するナビゲーションデバイスである請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５１】
前記デバイスは、位置探査システムを有する移動電話である請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５２】
前記位置探査システムはＧＰＳである請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５３】
前記デバイスは、自動車に恒久的に組み込まれる請求項３２乃至４８のいずれか１項に記載のデバイス。
【請求項５４】
時間の関数として交通速度又は通過時間データを測定し、道路の区間に対する時間に依存する交通速度又は通過時間の履歴データベースを生成し、且つ少なくとも前記データベースの一部又はその内容を共有して請求項１に記載の方法の実行を可能にする交通監視システム。
【請求項５５】
ルート計画ソフトウェアにより使用される場合に請求項１乃至３１のいずれか１項に記載の方法の実行を可能にするように適応されるある領域のデジタル地図であり、前記地図は、少なくとも道路区間の一部に関連する時間に依存するコストを規定するデータと共に前記道路区間を規定するデータを含むデジタル地図。
【請求項５６】
請求項１乃至３１のいずれか１項に記載の方法を使用してルートを計画するように動作可能な組込みナビゲーションシステムを含む自動車。
【図１】
【図２】
【図３】
【図２】
【図３】
【公表番号】特表２００９−５１３９５１（Ｐ２００９−５１３９５１Ａ）
【公表日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願番号】特願２００８−５３４０８２（Ｐ２００８−５３４０８２）
【出願日】平成１８年１０月１０日（２００６．１０．１０）
【国際出願番号】ＰＣＴ／ＧＢ２００６／００３７６５
【国際公開番号】ＷＯ２００７／０４２７９６
【国際公開日】平成１９年４月１９日（２００７．４．１９）
【出願人】（５０８０２３２７１）アプライド ジェネリクス リミテッド (2)
【氏名又は名称原語表記】ＡＰＰＬＩＥＤ ＧＥＮＥＲＩＣＳ ＬＴＤ
【住所又は居所原語表記】Ｐｅｎｔｌａｎｄｓ Ｓｃｉｅｎｃｅ Ｐａｒｋ， Ｐｅｎｉｃｕｉｋ， Ｍｉｄｌｏｔｈｉａｎ ＥＨ２６ ０ＰＺ， Ｕｎｉｔｅｄ Ｋｉｎｇｄａｍ
【Ｆターム（参考）】
【公表日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願日】平成１８年１０月１０日（２００６．１０．１０）
【国際出願番号】ＰＣＴ／ＧＢ２００６／００３７６５
【国際公開番号】ＷＯ２００７／０４２７９６
【国際公開日】平成１９年４月１９日（２００７．４．１９）
【出願人】（５０８０２３２７１）アプライド ジェネリクス リミテッド (2)
【氏名又は名称原語表記】ＡＰＰＬＩＥＤ ＧＥＮＥＲＩＣＳ ＬＴＤ
【住所又は居所原語表記】Ｐｅｎｔｌａｎｄｓ Ｓｃｉｅｎｃｅ Ｐａｒｋ， Ｐｅｎｉｃｕｉｋ， Ｍｉｄｌｏｔｈｉａｎ ＥＨ２６ ０ＰＺ， Ｕｎｉｔｅｄ Ｋｉｎｇｄａｍ
【Ｆターム（参考）】
[ Back to top ]