JP2000055689A - 可変的ル―ト案内のために交通情報を使用する方法 - Google Patents

Abstract

(57)【要約】 【課題】 車両ナビゲーションシステムにおいて、最速
ルートを生成する方法を提供する。 【解決手段】 その方法は、複数の道路区分についての
実際の速度データを提供する放送信号を受信する工程で
あって、複数の道路区分の各々はある長さを有し、複数
の道路区分のうちの選択された区分は結合してある位置
から目的地への複数のルートの少なくとも一部分を構成
する工程と、実際の速度データを使用して複数のルート
を生成する工程と、実際の速度データを使用して複数の
ルートの各々についての通行時間を決定する工程と、お
よび、通行時間上の少なくとも一部に基づいて、複数の
ルートから最速ルートを選択する工程と、を有する。実
際の速度データは例えば毎時２０〜３０（約３２ｋｍ〜
４８ｋｍ）マイルまたは毎時４０〜５０（約６４ｋｍ〜
８０）マイル、もしくはさらに通常の速度制限または毎
時４５マイル（約７２ｋｍ）などの正確な速度から正ま
たは負のずれを示すものとすることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、リアルタイムな交
通データを使用する車両ナビゲーションに関する。より
詳細には、本発明は、放送されたリアルタイムな交通デ
ータを使用し、時々刻々変化する交通状況を考慮して少
なくとも１つの新しい最速ルートを提供することに関す
る。

【０００２】

【従来の技術】車両において実行される車両ナビゲーシ
ョンシステムは、運転者またはユーザを補助して、車両
の現在位置から所定の目的地までの最速ルートを見つけ
ようと試みる。本発明の記載との関連において使用され
る「最速ルート」という用語は、選択された目的地へ到
達するために最小の時間で通行するルートを指す。道路
の閉鎖、交通の密集、事故、回り道、警察の行動、また
は緊急電話報告の出来事、その他の予期せぬ道路事情が
交通の流れを妨げる場合に、そのようなシステムは特に
有用である。そのような道路事情の存在下で、車両が例
えばその出発点から開始する時に最速と思われるルート
は、もはや最速では無いかもしれない。この点、車両ナ
ビゲーションシステムは、上述の道路事情の存在を考慮
に入れた新しい最速ルートをユーザに提供しようとす
る。

【０００３】上記の道路事情の存在下で、選択された目
的地までの最速ルートを提供する１つのアプローチがAy
anoglu et al（以下、「Ayanoglu」と呼ぶ。）への米国
特許第5,689,252号に記載されている。このアプローチ
によれば、ユーザが出発地および目的地を入力すると、
車両ナビゲーションシステムは利用可能な通行ルートを
決定し、その目的地への最速ルートである少なくとも１
つのルートをユーザに提供する。その中から最速ルート
が選択された、利用可能な通行ルートは、車両ナビゲー
ションシステムのデータベースに記憶可能な、考え得る
ルートの規制された速度制限を利用して計算される。車
両が意図した目的地へ向かって最速ルートを進むと、そ
の最速ルートまたは他の隣接ルート上の予期せぬ道路事
情が存在すると交通の流れが妨げられ、最速ルートはも
はや「最速」ではなくなる。そのような道路事情を回避
するために、このアプローチの車両ナビゲーションシス
テムは、以下に説明するようにして新しい最速ルートを
提供しようとする。

【０００４】Ayanogluによれば、利用可能な各通行ルー
トに対する実際の平均速度と規制された速度制限との差
が監視され、中央データベースから車両ナビゲーション
システムへ放送される。利用可能な通行ルートは、ユー
ザが車両ナビゲーションシステムに車両位置および意図
した目的地を与えた時に最初に決定されることを考慮す
ることは重要である。利用可能な通行ルート上の交通の
実際の平均速度を中央データベースへ提供し、人間の観
察または実際の電子道路測定装置を使用して計算するこ
とができる。上述のように、実際の平均速度と公示速度
制限との差を監視することにより、Ayanogluが記載する
車両ナビゲーションシステムは、利用可能な通行ルート
から新たな最速ルートをユーザへ提供しようとする。

【０００５】

【発明が解決しようとする課題】残念なことに、Ayanog
luが記載するもののような従来技術のナビゲーションシ
ステムは、目的地への本当に最速なルートである新たな
最速ルートを提供することはできない。別の言い方をす
れば、従来技術のシステムが提供する新たな最速ルート
は、選択された目的地へ到達するための、（利用可能な
通行ルートから選択された）最小の時間を要するルート
ではない場合がある。例えば上述の車両ナビゲーション
システムは、最初に決定された利用可能な通行ルートか
ら新たな最速ルートを選択するように制限され、予期せ
ぬ道路事情により、これら利用可能なルートは正しい新
たな最速ルートを含まなくなっている場合がある。時々
刻々変化している交通状況は、予期せぬ道路事情の存在
を考慮に入れた利用可能な新たな通行ルートの決定を必
要とし、最初に決定された古い利用可能な通行ルート
は、目的地への全ての利用可能な通行ルートを正確に反
映していない場合がある。詳細には、利用可能な通行ル
ートの古いリストは、目的地への真の最速ルートである
ルートを含んでいない場合がある。

【０００６】さらに、Ayanogluが記載するものの如き従
来技術の車両ナビゲーションシステムは、特定のルート
上の推定到着時刻を正確に決定することもできない。例
えば、Ayanogluは、道路地図を、正確な平均速度と各利
用可能な通行ルートの長さのデータ構造に変換し、次に
実際の平均速度とそのルートの長さを使用して通行ルー
トについての推定到着時刻を計算する。しかし、このア
プローチは、通行ルートを形成するために組み合わされ
る種々の各道路区分上の実際の速度が異なること、なら
びに、ルートの単一の平均速度が、そのルートを形成す
る異なる道路区分上の実際の速度の正確な表示ではない
場合があることを考慮してはいない。１つのリンク上に
予期せぬ道路事情が存在し、別のリンク上にはそのよう
な道路事情が存在しない場合、ルートの実際の速度は道
路区分間で大きく変化するであろう。リンクは、典型的
に道路区分の組み合わせを含み、ルートの一部を構成す
る。

【０００７】したがって、時々刻々変化している交通状
況を考慮した正しい新たな最速ルートを提供し、より正
確かつ効率的な車両ナビゲーションを提供する車両ナビ
ゲーションシステムおよび方法が必要である。

【０００８】

【課題を解決するための手段】本発明は、放送されたリ
アルタイムな交通データを使用して、ある位置から目的
地への最速ルートを提供すると共に、その最速ルートま
たは他のルート上での選択された目的地への推定到着時
刻を提供する車両ナビゲーションシステムおよび方法を
提供する。

【０００９】１つの実施形態では、本発明は、車両ナビ
ゲーションシステムで最速ルートを生成する方法を提供
する。その方法は、複数の道路区分についての実際の速
度データを提供する放送信号を受信する工程であって、
複数の道路区分の各々はある長さを有し、複数の道路区
分のうちの選択された区分は結合してある位置から目的
地への複数のルートの少なくとも一部を構成する工程
と、実際の速度データを使用して複数のルートを生成す
る工程と、実際の速度データを使用して複数のルートの
各々についての通行時間を決定する工程と、通行時間に
少なくとも部分的に基づいて複数のルートから最速ルー
トを選択する工程と、を有する。

【００１０】この実施形態では、本発明は、実際の速度
データまたはリアルタイムな交通データに基づくいくつ
かの通行ルートを生成する柔軟性を提供する。その結
果、そのいくつかの通行ルートから選択される新たな最
速ルートの決定は、交通の現在の状態を正確に考慮して
いる。さらに、新たな最速ルート上の目的地への通行時
間の計算も、実際の速度データを使用して生成されるた
め、正確である。従来技術の方法は、考え得る通行ルー
トを計算するために実際の速度データを使用しないこと
を覚えておくことは重要である。むしろ、従来技術の方
法は、出発地からの出発時またはその付近において最初
に決定された利用可能な通行ルートを使用して新たな最
速ルートを決定しようとする。先に述べたように、時々
刻々変化する交通状況を考慮すると、最初に計算された
利用可能な通行ルートは、目的地への真の最速ルートで
あるルートをもはや含まない場合がある。

【００１１】別の実施形態では、本発明は、車両ナビゲ
ーションシステムにおいて、ある位置から出発して目的
地で終了するルートについての推定到着時刻を生成する
方法を提供する。その方法は、複数の道路区分について
の実際の速度データを提供する放送信号を受信する工程
であって、各道路区分はある長さを有し、複数の道路区
分のうちの選択された区分が結合して前記ルートを形成
する工程と、選択された道路区分に関連する長さおよび
実際の速度データを使用してそのルートについての推定
到着時刻を生成する工程と、を有する。

【００１２】この実施形態によれば、ユーザに推定到着
時刻が提供され、その時刻は実際の速度データを使用し
て計算され、よって目的地への正確な通行時間となる。
先に述べたように、従来技術は、推定到着時刻を計算す
るために実際の速度データを使用しない。むしろ、従来
技術は推定到着時刻を計算するために全ルートの実際の
平均速度を使用する。結果的に、従来技術は、真の最速
通行ルートを誤って除外する場合がある。なぜなら、既
に部分的に通行されたルートの無関係な部分が予期せぬ
道路事情を有し、それが全ルートの実際の平均速度を低
下させるからである。本発明は、車両の現在位置から目
的地への種々の道路区分についての実際の速度データを
使用するので、既に通行した道路区分は考え得る通行ル
ートの生成とはもはや無関係となることを覚えておくべ
きである。

【００１３】さらに別の実施形態では、本発明は、車両
ナビゲーションシステムにおいて初期位置と目的地とを
結ぶルートについての最初の推定到着時刻を更新する方
法を提供する。その方法は、ルートについての最初の推
定到着時刻を提供する工程であって、最初の推定到着時
刻は、初期位置、ならびにそのルートを形成する複数の
道路区分に関連する実際の速度データから導かれる工程
と、前記複数の道路区分の少なくともいくつかについて
の新たな実際の速度データを提供する放送信号を受信す
る工程であって、各道路区分はある長さを有する工程
と、および、現在の車両の位置および新たな実際の速度
データに基づいて推定到着時刻を修正する工程と、を有
する。

【００１４】この実施形態によれば、初期位置からの出
発時またはその付近で最初に決定された推定到着時刻が
リアルタイムな交通データにしたがって更新される。車
両ナビゲーションシステムのユーザは、交通の現在の状
態および／またはそのルート上の道路事情を正確に考慮
した推定到着時刻を知らされる。

【００１５】本発明の特徴および長所のさらなる理解
は、明細書および図面の残りの部分を参照することによ
り実現される。

【００１６】

【発明の実施の形態】上記を実現するため、本発明は、
リアルタイムな交通放送データを使用して、時々刻々変
化する交通状況下で新たな最速ルート提供する車両ナビ
ゲーションシステムおよび方法を提供する。以下の記述
では、本発明の完全な理解をもたらすために、多数の具
体的な詳細を記述する。しかし、そのような具体的な詳
細のいくつかまたは全てを伴わずに、本発明を実施可能
であることは当業者に明らかである。

【００１７】車内ナビゲーション環境 図１は、車両ナビゲーションシステム１０８（図１では
「ＮＡＶＭＡＴＥ」として示す）と通信する交通管理セ
ンタ１０２を示す。交通管理センタ１０２は、送信機１
０４を通じて、リアルタイムな交通データを受信し、ユ
ーザへ広める。いくつかのソースが交通管理センタ１０
２へリアルタイムで交通データを送る。例えば、地域の
警察署、ヘリコプター、および地域のラジオ局が収集し
た交通情報や、ヘリコプター、ループインダクタおよび
緊急電話コールにより収集された実際の高速道路速度お
よび幹線道路交通速度、などが交通管理センタ１０２へ
報告される。

【００１８】交通管理センタ１０２に配置されたインタ
ーフェースコンピュータ（図の簡略化のため図示せず）
は報告されたリアルタイムな交通データを処理し、それ
らをメッセージに形式化し、そのメッセージはダイヤル
アップモデム接続または衛星リンクを通じて送信機１０
４へ通信される。送信機１０４は、例えばＦＭラジオ局
のスタジオまたは送信室のいずれかにある。本発明の１
つの実施形態では、インターフェースコンピュータが形
式化したメッセージはベースバンド信号に符号化され、
それはＦＭラジオ信号のサブキャリアとして変調および
放送される。

【００１９】送信機１０４は、サブキャリア交通情報チ
ャンネル（ＳＴＩＣ）送信機（以下、「ＳＴＩＣ送信
機」と呼ぶ）とすることができる。しかし、重要なこと
は、別の実施形態では送信機１０４はラジオ（放送）デ
ータシステム（ＲＤＳ）または他のプロトコルで通信可
能であることである。ＳＴＩＣ受信機は、約７６００ｂ
ｐｓ〜約９６００ｂｐｓの間のレートでリアルタイムな
交通データを放送可能である。車両１０６内に車両ナビ
ゲーションユニット１０８と共に搭載される受信機１１
０は、アンテナ１１２を通じて送信機１０４からリアル
タイムな交通データを受信するように構成される。例え
ば、受信機１１０は、ＳＴＩＣ送信機から放送データを
受信可能なＳＴＩＣ受信機とすることができる。次に、
リアルタイムな交通データはＦＭデコーダにより復号化
され、シリアルデータリンクを通じて車両ナビゲーショ
ンユニット１０８へ送られる。さらに別の実施形態で
は、送信機の代わりに、リアルタイムな交通データを衛
星またはセルラー技術によってユーザへ伝達することが
できる。車両ナビゲーションユニット１０８は、受信メ
ッセージに含まれるリアルタイムな交通データをメモリ
記憶媒体へ取り込む。さらに、車両ナビゲーションユニ
ット１０８は、車両１０６の運転者または搭乗者に、リ
アルタイムな交通情報を、地図データベース内に記憶さ
れた他の関連データと共に表示することができる。後に
説明されるように、車両ナビゲーションユニット１０８
は、上記のリアルタイムな交通データを使用して、選択
された目的地までの最も迅速なルートを計算し、表示す
ることが可能である。

【００２０】車両ナビゲーションユニット 図２は、本発明で使用する車両ナビゲーションシステム
２００の具体的実施形態のブロック図である。センサ２
１２および２１４、受信機２１６ならびにＧＰＳ受信機
２１８が通信インタフェース２２２を介して計算手段２
２０へ接続されている。典型的な実施形態では、走行距
離センサ２１２は走行距離計を含み、角速度センサ２１
４はジャイロスコープまたは車両のホイールに結合され
た差動走行距離計を含む。例えば衛星をベースとした位
置決めシステムからの信号を受信するために、グローバ
ルポジショニングシステム（ＧＰＳ）データ受信機２１
８が設けられる。通信インターフェース２２２からのデ
ータがＣＰＵ２２４へ送られる。ＣＰＵ２２４は、較
正、信号処理、推測航法、車両位置決定、およびルート
案内機能を実行する。地図情報を含むデータベースは、
データベース媒体２２６へ記憶することができ、ＣＰＵ
２２４による実行のためにメインメモリ２２８に記憶さ
れた、計算手段２２０の動作の指示ソフトウェアもデー
タベース媒体へ記憶することができる。メモリ２２８
は、リードオンリーメモリ（ＲＯＭ）、もしくはフラッ
シュメモリまたはＳＲＡＭなどの再プログラム可能な不
揮発性メモリを含むことができる。システムＲＡＭ２３
０は、そのようなソフトウェアプログラムの実行に必要
な情報の読み書きを可能とする。データベース媒体２２
６は、不揮発性メモリ、ハードディスクドライブ、ＣＤ
−ＲＯＭ、または集積回路を含み、その中にディジタル
化された地図情報が記憶されている。グラフィックスコ
ントローラとすることができる出力コントローラ２３２
は、ＣＰＵ２２４が処理したデータを受信し、そのデー
タをディスプレイコンソール２４０へ送信する。ディス
プレイコンソール２４０は、通常は表示スクリーンを含
む出力連絡機構２３４を含む。ユーザは、希望の目的地
などの入力データをユーザインターフェース２３６を介
して入力することができ、ユーザインターフェース２３
６は典型的にはキーボードである。

【００２１】好ましくは、データベース媒体２２６内に
記憶された地図データベースは、例えば、道路の交差点
またはノード、道路区分、ランドマーク、および関心の
ある地点、ならびに他の地理的情報を記述する緯度およ
び経路の座標などの位置データを含む。さらに、データ
ベースは、道路名および地名、ならびに分岐路、一方通
行制限、路面、速度制限、形状、高度、その他の性質な
どの道路形態など、地図上の道路または地点の特性を示
すデータを含むことができる。本発明の具体的な実施形
態によれば、地図データベースは、個々のノードまたは
道路区分に関連付けられたコスト値を含む。コスト値
は、個々のノードまたは区分を通過するための推定時間
を示す。ノードコスト値は、例えば到来する交通と車両
が遭遇するか否か等の情報を考慮して、左折の操縦指示
を遅らせる。

【００２２】区分コスト値は、いずれも区分に沿った通
行時間に影響を与える速度制限および区分の長さなどの
道路区分の特性を反映する。また、地図データベース内
の道路には階層値が関連付けされ、その階層値は道路の
カテゴリーまたは種類に関係する。例えば、その階層の
最高レベルのカテゴリーはフリーウェイおよび高速道路
を含む。最低レベルは住宅地の通りおよび／または路地
を含む。

【００２３】通信プロトコル 図３は、本発明の１つの実施形態に従うメッセージ層２
５０を示し、それらは図１に示す送信機１０４と車両ナ
ビゲーションユニット１０８の間の通信プロトコルに関
連する。図３に示すように、位置基準（Location Refer
ence: LR）２５８がリアルタイムな交通情報メッセージ
（Traffic Information Message: TIM）２５６内に含め
られ、リアルタイムな交通情報メッセージはＳＴＩＣ送
信メッセージ（STIC Transmission Message: STM）内に
含められ、ＳＴＩＣ送信メッセージはさらにＳＴＩＣス
ーパーフレーム２５２内に含められる。

【００２４】メッセージ層２５０内の種々の層を、既知
または開発中のあらゆる規格にしたがって形式化するこ
とができる。例えば、メッセージ層を、以下に説明する
３つの開発中の国内規格にしたがって形式化することが
できる。交通情報メッセージ２５６（ＴＩＭ）の形式
は、自動車エンジニアソサエティ（Society of Automot
ive Engineers: SAE）のドラフト提案プラクティス（Dr
aft Recommended Practice）J2256およびＩＳＯのドラ
フト提案プラクティスTC 204 WG 11.1に基づくものとす
ることができる。位置基準（ＬＲ）の形式は、オーク・
リッジ国立研究所のＳＡＥドラフトJ-2374の位置参照メ
ッセージ仕様書（Location Referencing Message Speci
fication）で開発された位置参照メッセージ仕様書に基
づくものとすることができる。これら３つの規格全て
を、全ての目的でここに参照文献として取り入れる。

【００２５】ＳＴＩＣスーパーフレーム（以下、「スー
パーフレーム」という。）２５２は６５キロバイトのメ
ッセージとすることができ、それは例えばＦＭ放送局に
配置されるＳＴＩＣメッセージエンコーダにより周期的
に放送され、スーパーフレームの内容は定期的に再放送
される。上述のインターフェースコンピュータはスーパ
ーフレーム中の６５キロバイトの形式および内容を制御
する。例えば、インターフェースコンピュータは、ＳＴ
Ｍ、ＴＩＭ、およびＬＲの形式を使用してスーパーフレ
ーム中のデータを形式化し、交通情報を更新するために
スーパーフレームの内容を定期的に上書きする。

【００２６】スーパーフレームは、上述のように送信機
１０４により放送される前に、ＳＴＩＣメッセージエン
コーダにより符号化される。スーパーフレームの処理
は、例えば、ＳＴＩＣメッセージエンコーダがＳＴＩＣ
スーパーフレーム内のデータを２２８バイトのブロック
に細分化する時に始まる。エンコーダは各ブロックに１
５バイトのリードソロモン前方エラー補正コードを付加
し、次に規定のアルゴリズムを使用してデータおよび前
方エラー補正コードをランダマイズする。最後に、エン
コーダはデータに同期フラグを付加し、パッケージ全体
が放送される。

【００２７】図１に示す受信機１１０は、入力ビットス
トリームの中から同期フラグシーケンスを探す。このシ
ーケンスがデータにより複製される可能性は、ランダマ
イズ(randomization)処理により最小化される。フラグ
を使用して、受信機１１０は入力ビットストリームに同
期し、放送データをデランダマイズ(derandomize)す
る。次に、受信機１１０は前方エラー補正コードを使用
して、あらゆる単一の２２８バイトブロック内の７バイ
トまでのエラーを補正する。最後に、受信機は、スーパ
ーフレームデータを出力する前に、スーパーフレームフ
ラグおよび前方エラー補正コードを除去する。

【００２８】ＳＴＩＣ送信メッセージ（ＳＴＭ）は、交
通情報メッセージ（ＴＩＭ）のためのフレーム構造を提
供する。ＳＴＭは、フラグ、バイトカウント、シーケン
ス番号、交通情報メッセージおよびチェックサムを含む
ことができる。ＳＴＭのフラグ、バイトカウント、シー
ケンス番号、および巡回冗長検査（ＣＲＣ）フィールド
は、各々が２進数値を含むことができる。これら各フィ
ールド内の第１データビットは、示される数の最上位ビ
ットである。ＳＴＭフラグは固定ビットパターンであ
り、それは受信装置を放送データストリームに同期させ
るために使用される。図１を参照すると、車両ナビゲー
ションユニット１０８は受信機１１０から連続的かつ区
切りのない（undelimited）データストリームを受け取
る。次に、車両ナビゲーションユニット１０８はＳＴＭ
フラグパターンを探し、その後にＳＴＭの第１バイトを
識別する。

【００２９】バイトカウントフィールドは、フラグおよ
び巡回冗長検査（ＣＲＣ）を含むＳＴＭ内の総バイト数
を示す。車両ナビゲーションユニット１０８はバイトカ
ウントを使用してＳＴＭの最後の位置を決定すると共に
ＣＲＣを分離する。「通常の」長さを任意に選択するこ
とができ、この長さを使用してバイトカウントが有効で
あることを確認する。バイトカウントが「通常」範囲外
ならば、ＳＴＩＣメッセージを無効とみなし、次の「Ｓ
ＴＩＣ」メッセージの最初をチェックして実際の長さを
決定する。バイトカウントの有効値は、ＳＴＭが９バイ
トの最小長さと６５，５３５バイトの最大長さを有する
ことを示す。９または６５，５３５バイトであるＳＴＭ
長さはＳＴＭフォーマットでは許容されるが、通常の使
用については推奨されない。９バイトの長さのＳＴＭは
情報を含まず、よって無用である。ＳＴＭは好ましくは
少なくとも１つのＴＩＭを含む。６５，５３５バイトの
長さのＳＴＭも望ましくない。なぜなら、ＳＴＭ長さが
増加すると、ＳＴＭ中のエラーの確率および各エラーに
伴うデータ損失量が増加するからである。車両ナビゲー
ションユニット１０８がＳＴＭ中の無効なチェックサム
を受信したならば、車両ナビゲーションユニットはＳＴ
Ｍ内の全てのデータを破棄する。ＳＴＭの長さが増加す
ると、ＳＴＭ中のエラーの確率および各エラーに伴うデ
ータ損失量も増加する。

【００３０】シーケンス番号は、各ＳＴＭを１つに識別
し、車両ナビゲーションユニット１０８により使用され
て以前の受信メッセージを取り除くフィルタリングを行
う。そのようなフィルタリングは、車両ナビゲーション
ユニット１０８が処理ＳＴＭに関連する計算上の費用を
減少させることを助けるので、本発明によって提供され
る多くの長所のうちの１つを与える。

【００３１】ＴＩＭは可変長データフィールドに符号化
され、以下に説明される。データフィールドの長さはＴ
ＩＭの数により決定され、各ＴＩＭの長さはＳＴＭ内に
含められる。上述の理由から、各ＳＴＭに含まれるＴＩ
Ｍの数および長さは、望ましいＳＴＭ長さとなるように
インタフェースコンピュータにより注意深く選択され
る。

【００３２】チェックサムは１６ビットの２進数ＣＲＣ
コードである。ＣＲＣは、エラー補正ではなく、エラー
検出の手段と意図されている。ＳＴＭメッセージフォー
マットは、喪失したデータを回復するためにＳＴＩＣシ
ステムの広範な前方エラー補正に依存する。

【００３３】図３を参照すると、ＴＩＭ２５６は、ＬＲ
２５８と結合されたリアルタイムな交通データを含む。
例を挙げると、インターフェースコンピュータは、リン
クデータＴＩＭ、事情報告ＴＩＭおよび助言ＴＩＭを含
むＴＩＭを発生する。リンクデータＴＩＭのフォーマッ
トは、例えば上述のSAE/ISOメッセージ規格のメッセー
ジ番号１Ｌのフォーマットによる。リンクデータＴＩＭ
は、主として、例えば車道区分についての通行速度、通
行時間、実際の速度と通常速度の比、密集レベル、その
他を含む。

【００３４】事情報告ＴＩＭは、車道上で発生した交通
事情の位置および重大度に関する情報を含む。事情報告
ＴＩＭフォーマットは、例えばSAE/ISOメッセージ規格
のメッセージ番号２４Ｌのフォーマットに基づく。

【００３５】助言ＴＩＭは交通、天気および他の事象に
関する助言メッセージを含む。助言ＴＩＭフォーマット
は、例えばSAE/ISOメッセージ規格のメッセージ番号１
５Ｌのフォーマットに基づく。

【００３６】ＬＲは、２地点を結ぶ車道上の地理的地点
または車道の区分のいずれかを識別する情報を含む。イ
ンターフェースコンピュータにより生成される種々のタ
イプのＬＲは、全体的に参照される地点、全体的に参照
されるリンク、局地的に参照される地点、局地的に参照
されるリンク、位置参照ヘッダを含む。

【００３７】地点を識別するＬＲは１つの座標を含み、
リンクを識別するＬＲは２つの座標を含む。いずれの場
合も、座標は地理的緯度、経度および高度によって示さ
れる。

【００３８】リンクを識別するＬＲの座標の順序は、そ
のリンク上の通行方向を示す。例を挙げれば、２方向に
進む高速道路の１つの区分についての２つのリンクは同
一の端点を共有するが、それら端点の順序が特定のリン
クを１つに識別する。

【００３９】インターフェースコンピュータにより生成
されたＬＲは始点からのデルタ（delta）を含むことが
できる。また、ＬＲを含むＴＩＭも位置基準ヘッダを含
み、それは始点を含む。始点は、測地原点を基準とした
座標（例えば、緯度、経度および高度）である。同一の
ＴＩＭ内の後続の局地的に参照されるＬＲは、同一の測
地原点を基準とした始点からの偏差としての座標を含
む。道路名情報はいずれかのＬＲに含まれる。各位置基
準内のフラグは、道路名の接頭部、道路名、道路の種類
などの名称情報の存在を示す。

【００４０】交通管理センタ１０２から放送された情報
の主要部は、リンク速度データおよび地点（事情）デー
タ（例えば、緊急電話コール、駐車場での警察の行動、
その他）を含む。上述のように、リンク速度データはリ
ンクデータＴＩＭを使用して放送することができる。リ
ンク速度データは、主としてセンサおよび履歴データか
ら得られる。センサは、例えば高速道路および主要幹線
道路上での通行速度データを提供する。非測定道路上で
は、履歴データまたは１日の時間に応じて変化すると共
に予期される通行速度を含む所定の速度データを使用す
ることができる。インターフェースコンピュータにより
生成可能なリンクデータＴＩＭは、メートル毎秒または
フィート毎秒の単位のリンク速度データを含む。本発明
の１つの実施形態では、ＴＩＭは、道路名情報を有しな
い局地的に参照されるリンクＬＲを含む。この実施形態
では、道路名情報は、始点および終点の緯度および経度
が近くのリンクと誤解されるであろうリンクと共にのみ
道路名情報が放送される。また、地点「緯度、経度、高
度」データも放送され、駐車場での窃盗行為等、そのリ
ンク上で生じないリンクには相関付けされない。しか
し、そのような事情は地図表示テーブル内に維持され、
ルート計算に使用しても使用しなくてもよい。

【００４１】本発明は、図１の車両ナビゲーションユニ
ット１０８が多くの異なる方法でリンク速度情報を使用
できることを想定する。例を挙げれば、車両ナビゲーシ
ョンユニット１０８は出発点の座標、終点の座標および
各リンクのリアルタイムな速度を受け取り、それに応じ
て車両ナビゲーションユニットはアルゴリズムを実行
し、そのアルゴリズムは出発点および終点を車両ナビゲ
ーションユニット内に内部的に保持された地図データベ
ースと相関付ける。そのアルゴリズムは道路名情報を使
用して地図の相関のあらゆる不明瞭性を解消する。次
に、車両ナビゲーションユニット１０８はリアルタイム
な速度データを内部地図データベースの相関要素と関連
付ける。最後に、車両ナビゲーションユニット１０８は
リアルタイムな速度情報を表示し、本発明にしたがって
その情報をルート計算中に使用する。

【００４２】別の例として、車両ナビゲーションユニッ
ト１０８は、地図データベース内の要素へリンクを関連
付けするマッピングテーブルを有するように予めプログ
ラムされ、そのマッピングテーブルは車両ナビゲーショ
ンユニット内に内部的に保持される。車両ナビゲーショ
ンユニット１０８は、出発点の座標、終点の座標および
各リンクのリアルタイムな速度を受信し、それに応じ
て、車両ナビゲーションユニットはマッピングを使用し
てリアルタイムな速度データを内部地図データベースの
相関要素と関連付けする。最後に、車両ナビゲーション
ユニットはリアルタイムな速度情報を表示し、本発明に
したがってルート計算中にその情報を使用する。

【００４３】ルート生成 本発明は、出発位置から最終目的地までの最善ルートを
効率的に生成するように地図データベースを組織化する
方法を利用する。図２の車両ナビゲーションシステムを
使用する、出発位置Ａから最終目的地Ｂまでのルートの
決定を図４を参照して説明する。本発明の具体的な実施
形態によれば、車両ナビゲーションシステム２００は２
端点ルート生成アルゴリズムを採用する。すなわち、シ
ステムは、出発点Ａから始まっている経路と、目的点Ｂ
から戻るようにつながっている経路とを探索する。２つ
の検索各々は複数の部分的ルートを生成し、それらのう
ちの２つが最終的に点Ａと点Ｂとの間のどこかで出会っ
て単一のルートを形成する。

【００４４】最初に、円形領域２７２および２７４によ
り示されるように、検索パターンが点ＡおよびＢから全
ての方向へ出発する。図４の線図は、継続するルート探
索のために、点Ａから出発する４つの道路区分のうちの
１つがどのように選択されるかを示す。各道路区分nは
関連する区分コストg(n)を有し、各ノードkは関連する
ノードコストg(k)および発見的コストh(k)をそれぞれ有
する。各区分についての区分コストをその終点について
のノードコストおよび発見的コストに加算して、各々に
ついての総コストを取得する。次に、最小の総コストを
有する道路区分がさらなる生成のために選択される。図
４では、点Ｄで終わる道路区分が最初に選択される。そ
れは、点Ｄに関連付けられた発見的コスト、すなわち点
ＤとＢの間の距離が点Ｃ、ＥおよびＦと関連付けされた
発見的コストよりも小さいからである。次に、このプロ
セスを点Ｄ、およびその後に新たに生成されたルート点
について繰り返す。これは、ルート生成過程にわたって
検索領域を変更および狭めていく効果を有し、それによ
り領域２７６および２７８が示すように点ＡとＢの間の
領域にサーチをより集中させる。

【００４５】ルート計算終了カウント 本発明の具体的な実施形態によると、上述の手法（また
は多種のルート生成方法のうちのいずれか）により第１
のルートが生成された後、システムはルート生成アルゴ
リズムの終了前に２つの事象のうちの１つが起きるのを
待つ。２つの事象のうちの１つは、出発点と目的地の間
にプログラム可能な数のルートが生成されたことであ
る。例えば、１つの具体的実施形態によれば、プログラ
ム可能なルートカウントは４である。この実施形態で
は、４つのルートが生成されると、システムは最小のコ
ストを有するルートをユーザへ伝える。これは、反復終
了カウントと呼ばれる。

【００４６】２つの事象のもう一つは、抑制制限カウン
トと呼ばれるパラメータがゼロに達することである。第
１のルートが生成された後、追加のルートを検索してい
る間に、ルート生成アルゴリズムが実行する各区分延長
について抑制制限カウントが減少される。抑制制限カウ
ントの初期値は、本発明の種々の具体的実施形態に応じ
て種々の方法で設定することができる。１つの実施形態
では、初期の抑制制限カウントは５００区分に固定され
る。すなわち、ルート生成アルゴリズムは、そのサーチ
を終了する前に、少なくとも１つの部分的ルートを追加
の５００区分延長する。しかし、そのような固定の初期
カウントは、ルート長の大きな変化性を考慮していない
ので、全てのルート生成問題について最適であるとは言
えない。例えば、５００である抑制制限カウントは２マ
イル（約３．２ｋｍ）離れた出発点と目的地については
適切であるかもしれないが、２５マイル（約４０ｋｍ）
離れた出発点と目的地については不十分であることはあ
り得る。加えて、粗くディジタル化された領域（例えば
地方）について適切である初期カウントは、密にディジ
タル化された領域（例えば都心部の地域）での延長につ
いては十分な数の付加的区分を与えないことがある。

【００４７】こうして、２つの代替的実施形態によれ
ば、抑制制限カウントの初期値は可変とすることができ
る。第１実施形態では、その初期値は出発地と目的地の
間の距離に依存する。すなわち、出発地と目的地の間の
距離が長いほど、初期カウントは高く設定される。第２
実施形態では、初期カウントは、最初のルートを計算す
るために必要な区分延長の数に依存する。すなわち、第
１の生成ルート内の区分数が大きいほど、初期カウント
は高く設定される。こうして、初期抑制制限カウントを
各具体的ルート生成問題に適合させることができる。

【００４８】上述の実施形態のいずれのルート計算終了
カウントの実施形態も、出発地から目的地への追加のル
ートが生成される度に特別の量だけカウントを減少させ
ることによりさらに高度化することができる。例えば、
各区分の延長についてカウントを１だけ減少させること
に加えて、第１のルートの後に生成された各ルートにつ
いて例えば５０ずつ減少させることもできる。そうし
て、生成されたルートの数が減少し、相関的にさらなる
検索の必要性が減少するにつれて、抑制制限カウントは
これを反映するように調整される。具体的実施形態によ
れば、カウントを調整する特別の量は、出発地と目的地
の間の距離、または第１の生成ルート内の区分数にした
がって変化させることができる。

【００４９】可変区分コスト 上述のルート生成方法は、図５に示す問題に対応するよ
うに高度化することができる。ノード３８１の発見的コ
スト（ベクトルＨ１で示す）はノード３８３の発見的コ
スト（ベクトルＨ２で示す）より小さいので、ルート３
８２が生成される可能性はルート３８４よりも高い。こ
れは、ルート３８４が例えば主としてランク３、すなわ
ちフリーウェイの道路区分を含むために明らかに優勢な
ルートである場合にさえも生じうる。したがって、本発
明の具体的な実施形態によれば、発見的コストは時々刻
々調整され、ルート生成においてより高ランクの道路区
分の使用を優先するように重み付けされる。例えば、１
つの実施形態において、特定のノードの発見的コスト
は、そのノードと目的地との間の距離に、関連する道路
区分のランクに対応する定数を乗算することにより決定
される。ランクに関連する定数は、最高ランクから最低
ランクへと増加し、より高ランクの区分を優先させる。
別の実施形態では、発見的コストは時々刻々調整され、
道路区分の重要度に基づいてその道路区分の使用を優先
するように重み付けされる。

【００５０】発見的またはｈコストの操作は、目的地が
出発地から非常に遠い（例えば３００マイル、約４８０
ｋｍ）場合には特に有益とは言えない。なぜなら、操作
がｈコストにある定数（例えば０．９）を乗算すること
を含む場合、ｇコストと比較したｈコストの大きさ（例
えばｈ＝20,000に対してｇ＝100）は総区分コストｆ、
すなわちｇ＋ｈの調整を不均等化するからである。した
がって、本発明のより具体的な実施形態によれば、区分
コストｆは、その点までのルートのｇコストの割合とし
て計算される割引値の導入により、より高ランクの区分
の使用を優先するように調整される。図６は、出発地Ｓ
から出発する４つの道路区分を示す。より大きい区分２
９２および２９４はフリーウェイの道路区分を示す。よ
り小さい区分２９６および２９８は地上の道路区分を示
す。各区分およびその要素に関連付けられたｆコスト
が、関連する端点ノードと目的地Ｄとを結ぶライン上に
与えられている。よって、例えば、区分２９６のｆコス
トは、ノード２９７と目的地Ｄとの間の距離により決定
されるように、ｇコスト（100）＋ｈコスト（950）であ
る。これは総コスト1050を生じさせる。同様に、区分２
９８とノード２９９について、ｆコストは1100である。
しかし、区分２９２と２９４（および関連するノード３
５３および３５５）はフリーウェイの一部であるので、
ｆコストは５％の割引だけ減少させられる。もちろん、
割引は、本発明の視野から外れることなく、あらゆる範
囲の値とすることができる。いずれにせよ、図６に示す
ように、区分２９２および２９４に関連するｆコストは
それぞれ1095と1200である。図６の例において、ルート
生成アルゴリズムは最低のｆコストを有するので、最初
に区分２９６を優先させることが理解されるであろう。
しかし、アルゴリズムが３方向の各々へ延長すると、そ
のルートの累積ｇコストの増加に伴って、フリーウェイ
ルート（区分２９２および２９４を含む）に関連する割
引は増加するであろう。したがって、アルゴリズムは結
局、フリーウェイルートについてのｆコストが区分２９
６から始まるルートのｆコストより小さくなる点に到達
する。こうして、ルート生成アルゴリズムが出発位置か
ら遠くへ進むにつれて、ルート生成アルゴリズムはより
高いランクの区分を有するルートを優先するようにな
る。ルート生成についてのさらなる情報には、“車両ナ
ビゲーションシステムにおけるルート生成”との名称
で、発明者が玉井治久氏であり、１９９７年１月１５日
に出願された米国特許出願08/784,204、ならびに１９９
５年２月９日に出願された米国特許第5,712,788号の一
部継続出願を参照することができ、両者の全記載をここ
に全ての目的において参考文献として取り入れる。

【００５１】図７は、本発明の１つの実施形態により、
車両ナビゲーションユニットが受信機を通じて送信機か
ら受信したリアルタイムな交通データを更新するプロセ
ス３００を示す。プロセス３００は、車両ナビゲーショ
ンシステム（図７では「NAVMATE」と呼ぶ）と、例えば
ＳＴＩＣ受信機などの受信機がステップ３０２で起動さ
れた時に開始する。このステップで、受信機は、例えば
ＳＴＩＣ送信機などの送信機から放送された交通データ
の受信を開始する。ステップ３０４では、交通データが
受信されているか否かが質問される。１つの実施形態で
は、ステップ３０４でのその質問は定期的に行われる
（例えば、１分に１回など）。次に、交通データが実際
に受信されていると決定したならば、次にステップ３０
６で車両ナビゲーションユニットの表示ユニット上の通
信ステータスが更新される。例を挙げれば、「ＴＩ」
（「Traffic Incident」の短縮形を示す）と表示された
緑色のアイコンを表示ユニット上に示すことにより、交
通データが受信されていることをユーザに通告する。し
かし、交通データが受信されていないと決定された場
合、次にステップ３２２で表示ユニットは交通データが
受信されていないことを表示する。これは、例えば「Ｔ
Ｉ」と示された赤色のアイコンを表示することにより達
成される。所定の閾値の時間が経過し、通信が再度可能
とされない場合、ステップ３２４に示されるように、速
度および事情アイコンが表示からクリアされる。

【００５２】ステップ３０８は交通メッセージのチェッ
クサムの受信およびチェックを含む。ステップ３１０で
は、チェックサムが容認されるか否かが質問される。チ
ェックサムが容認されないことが決定された場合、次に
プロセス３００は上述のステップ３０４へ進む。しか
し、チェックサムが容認されると決定された場合、次に
プロセスはさらにステップ３１２へ進み、そこで交通デ
ータが以前に受信されたか、または交通データが同じで
あるかが質問される。上述のように、ステップ３１２の
質問は、例えば交通データのフレームに関連するシーケ
ンス番号をチェックすることにより行われる。以前に交
通データが受信されている場合、次にステップ３１４に
したがってその交通データは無視され、ステップ３１６
で地図表示テーブル内のタイムスタンプが更新される。
タイムスタンプは、受信機が受信しているデータの各リ
ンクまたはフレームに関連付けされる。ステップ３１６
で、特定のリンクについてのデータを車両ナビゲーショ
ンユニットにより受信することができ、タイムスタンプ
を記録して運転者またはユーザにそのリンクのためのデ
ータが実際に受信されていることを通告する。しかし、
特定のリンクのためのデータが例えば３分間受信されな
い場合、そのデータはテーブルおよび表示から除去され
る。ステップ３１６の結果の後、プロセス３００は上述
のステップ３０４へ戻る。

【００５３】例えば、そのリンクまたはデータのフレー
ムについてのシーケンス番号が新しいために、以前に交
通データが受信されていないと決定された場合、交通デ
ータは図７のステップ３１８に示されるように地図表示
テーブルへ加えられる。また、新しく受信された交通デ
ータは、車両ナビゲーションユニットに接続されたメモ
リ記憶領域にも記憶される。ステップ３２６は任意的フ
ィルタとして実行可能であり、道路上に表示された実際
の速度データおよび道路事情が放送されたリアルタイム
な速度データおよび道路事情と一致するか否かのチェッ
クを含む。例を挙げれば、「１６マイル（約２５．６ｋ
ｍ）のスケール」が描かれ、フリーウェイと高速道路を
表示するがそれより低いクラスの道路は表示しないとす
ると、交通情報はフリーウェイ／高速道路について表示
およびチェックされ、道路が描かれない自由空間には表
示もチェックもされない。このステップにおいて、非常
事態などの交通情報は、その事態が駐車場内であったか
もしれないので、自由空間に描かれ、チェックされるこ
とができる。新しい交通データについてのタイムスタン
プおよびシーケンス番号の付加を含むステップ３２０の
結論によって、プロセス３００はステップ３０４へ戻
り、より多くの交通データを受信する。こうして、新し
い交通データが地図表示テーブルへ追加され、複製交通
データのためのタイムスタンプを更新してリンクが更新
中であることを反映させる。本発明のこの特徴により、
受信機は地図表示上の全てのリンクについての速度情報
を受信可能となり、この大容量のリンク速度データは上
述のプロセスにより容易化される。

【００５４】図８は、本発明の１つの実施形態に従い、
ユーザにリアルタイムな交通データを定期的に通告する
地図表示の生成プロセス４００のフローチャートを示
す。このプロセスから生成される地図表示を、車両ナビ
ゲーションユニットの表示ユニット上に表示することが
できる。本発明の具体的実施形態によれば、車両ナビゲ
ーションシステムの表示装置は、「ダブル・バッファリ
ング」を採用し、それにおいては第１のＧＵＩが背景と
して地図表示を提供する。地図表示情報は例えば、道路
名および高速道路のマーカーに加えて、地図のグリッド
自体を含む。第２のＧＵＩは第１のＧＵＩ上に重ねら
れ、前景の交通データ情報を示す。ダブルバッファリン
グについてのより多くの情報は、Aisin AW Co., LTDに
発行された米国特許第5,371,497号を参照することがで
き、それを全ての目的においてここに完全に取り入れ
る。この実施形態では、第２のＧＵＩをオフにすること
によってリアルタイムな交通データ表示を停止し、それ
により地図表示のよりはっきりした視野を得ることがで
きる。

【００５５】ステップ４０２および４０４はそれぞれ、
道路区分の描画と、道路名またはフリーウェイマーカー
の付加を含む。上述のように、ステップ４０２と４０４
で表示される情報はＣＤ−ＲＯＭに記憶することができ
る。例えば、運転者またはユーザが異なる種類の道路を
相互に区別することを容易にするために、一般道路、主
要道路、フリーウェイおよび提案された道路を全て異な
る色で表示することができる。ステップ４０６では、画
面の境界内のデータについて関連する表示テーブルをチ
ェックする。リアルタイムな交通速度および道路事情は
ステップ４０８で地図表示上に示される。例えば、道路
区分のリアルタイムな速度を、その道路区分に沿って配
置した異なる色のドットにより、もしくはその道路区分
を異なる色で強調することにより示すことができる。異
なる色は、道路区分上の異なる速度範囲を示す。こうし
て、ユーザには道路上での予期せぬ出来事または交通に
よって道路区分上に起きた減速の程度が通告される。表
示された道路上の出来事には、メンテナンス、交通事
故、道路閉鎖、緊急電話コール、道路状況、イベント情
報（例えば、スポーツイベントまたはコンサートに関連
する交通状況）、破損物の存在、天候による道路上の危
険な運転状況等を示すアイコンを含む。１つの実施形態
によれば、プロセス４００はステップ４１０で示される
ように地図表示上に車両アイコンを描くことを含む。上
述のプロセス４００はいずれの具体的な順序にも制限さ
れることはなく、いくつかの異なる順序で実行可能であ
ることを覚えておくべきである。

【００５６】上述のプロセスにより車両ナビゲーション
ユニットの表示ユニット上に生成される地図表示は、上
に述べていないいくつかの特徴を有することができる。
例えば、地図表示テーブルは異なるズームスケール設定
でユーザに示すことができる。例えば最低のズームスケ
ール設定では、地図の最も詳細な視野がユーザに提示さ
れる。地図の最も詳細な視野は、全ての道路をそれらの
道路名とともに、フリーウェイをフリーウェイラベルと
ともに含むことができる。次に高いズームスケール設定
では、地図表示は全ての主要道路を、道路名およびフリ
ーウェイラベルを伴って含む。このズームスケール設定
では、名前がはっきりと表示可能となった時にいくつか
の道路名が現れる。次に高いズームスケール設定では、
フリーウェイラベルを有する全ての道路が地図表示上に
示される。２番目に高いズームスケール設定では、地図
表示は高速道路およびフリーウェイラベルを伴うフリー
ウェイのみを含む。最も高いズームスケール設定は、地
図表示の最も詳細でない視野を提示し、地図表示はフリ
ーウェイラベルを有するフリーウェイのみを含む。

【００５７】別の例として、車両ナビゲーションは、通
行中に異なる段階で地図を再描画する。１つの段階で
は、地図を回転して車両が上および前方へ進んでいるこ
とを車両アイコンが示すようにする。別の段階では、車
両アイコンが現在の地図画面の端に近づいた時に、より
関連の深い道路区分を明確に表示するように地図が再描
画される。さらに別の段階では、車両が９０度回転した
ときに地図表示が再描画される。

【００５８】運転者が出発点を出発して選択された目的
地へ向かう場合、車両ナビゲーションユニットは出発時
またはその付近における交通状況に基づいて最速のルー
トを提供する。しかし、車両がそのルートをある時間に
わたって通行した後、道路事情の発生または解消による
現在ルートまたは隣接ルート上の遅延により、現在のル
ートはもはや選択された目的地への最速ルートでは無く
なることがある。したがって、本発明は１つの実施形態
においてプロセス５００を提供し、図９乃至１１に詳細
に示すように、リアルタイムな交通データに基づいて、
選択された目的地への推定到着時刻を推定する。図９乃
至１１によれば、最速ルート上に遅延があると、プロセ
ス５００はユーザに遅延の原因ならびに遅延の推定時間
を通告する。その代わりに、運転者の道路上で遅延が解
消すると、推定到着時刻が速くなるであろうことを運転
者は知らされる。加えて、車両ナビゲーションユニット
も、放送されたリアルタイムな交通データに基づいて、
選択された目的地への別の最速ルートを選択する選択肢
を与える。

【００５９】プロセス５００はステップ５０２で開始
し、推定到着時刻の計算のために距離と走行速度の決定
に着手したルート上の道路区分を通過することを含む。
着手したルートは、出発時またはその付近の交通状況に
基づく目的地までのルート計算基準（例えば、「フリー
ウェイをなるべく使用しない」、「有料道路を避ける」
など）を使用する最速ルートとすることができる。同時
に実行可能なステップ５０４と５０６は、推定到着時刻
を、地図表示テーブルからのルートに沿った遅延と共に
表示すること、および推定到着時刻、着手ルートについ
ての推定遅延および総推定到着時刻のそれぞれを表示す
ることを含む。ステップ５０６では、推定到着時刻は、
出発時またはその付近での目的地までの交通状況に基づ
いて推定された最速ルート上の到着時間とすることがで
きる。いくつかの実施形態では、ステップ５０６の推定
到着時刻は、道路事情無しにそのルート上の交通の通常
速度を反映し、または、データベース内に記憶された所
定の速度データを使用して計算される。推定遅延は、例
えば道路事情による最速ルートへ遅延を指し、総推定到
着時刻は、推定遅延を推定到着時刻に加算することによ
り計算される。こうして、ルート上の交通の流れが予期
せぬ道路事情により妨げられた場合、そのルートについ
ての総推定遅延および総推定到着時刻も増加する。

【００６０】プロセス５００によれば、ユーザが彼のル
ート上の予期せぬ道路事情を迂回したいと思えば、ユー
ザには新たなルートを選択する選択肢が提供される。ス
テップ５０８では、ユーザが新たなルートを選択したか
否かが質問される。ユーザが新たなルートを選択したこ
とが決定された場合、プロセス５００は図１１のステッ
プ５２６へ進む。ステップ５２６では、リアルタイムな
交通データに基づくルート計算およびコスト計算が上述
のように実行され、目的地への最速ルートに到達する。
リアルタイムな交通データが利用不能であるか、または
速度が監視されていない道路区分については、例えば車
両ナビゲーションユニットのデータベースまたはインタ
フェースコンピュータ中に記憶された所定速度を使用す
る。所定速度は、道路区分上の規制された速度制限と
し、もしくは特定の時刻に終了するスポーツイベントに
起因する交通の如き、既知の道路事情を考慮することが
できる。しかし、図９のステップ５１０においてユーザ
が新たなルートを選択しなかったことが決定された場
合、プロセス５００は図１０に示すようにステップ５１
０へ進む。それは以下に説明される。

【００６１】ステップ５１０は、例えば車両がルート上
を目的地へ向かって進むときの分数を増加することによ
る、車両ナビゲーションユニットの表示画面上の推定到
着時刻のカウントダウンを含む。ステップ５１２は、地
図表示テーブルおよびルートリストを使用して、推定遅
延および新たな推定到着時刻を計算することを含む。ス
テップ５１２は定期的に（例えば１分毎に）実行され
る。ルートリストは主として、所定ルートのリンクの放
送されたリアルタイムな交通データを使用して推定到着
時刻および推定遅延を計算するための所定ルートのリン
クおよび対応情報を含む。結果的に、ステップ５１２で
計算される新たな推定遅延は、ルート上の交通の現在の
状況を反映する。ステップ５１４では、ステップ５１２
で計算された新たな推定到着時刻が、ステップ５１０で
先に計算された推定到着時刻と比較される。

【００６２】ステップ５１６は、新たな推定到着時刻か
らの先の推定到着時刻の減算結果が所定値以上であるか
否かを質問する。新たな推定到着時刻からの先の推定到
着時刻の減算結果が所定値以上でないと決定された場
合、プロセス５００は上述のステップ５１０へ戻る。し
かし、新たな推定到着時刻からの先の推定到着時刻の減
算結果が所定値以上であると決定された場合、プロセス
５００はステップ５２０へ進む。

【００６３】代わりに、ステップ５１６において、新た
な推定到着時刻が所定の閾値を超えているか否かを質問
することができ、プロセス５００をステップ５１６での
決定に基づいて進めることができる。推定到着時刻が大
きく減少するならば、その情報もユーザに提供される。

【００６４】ステップ５２０で、車両ナビゲーションユ
ニットにより、交通事情メッセージを表示することがで
きる。交通事情メッセージは、ルート上の特定数の道路
事情のリストを含むことができる。ステップ５２０で表
示された道路事情のリストは、発生距離および／または
各道路事情の交差点名、もしくは各道路事情の種類に関
連するアイコンを伴うことができる。１つの実施形態で
は、交通事情メッセージは、可聴警告、例えば「ビー
プ」、またはユーザに画面に表示された交通事情メッセ
ージを見るように警報する警報信号を伴うことができ
る。ステップ５１８によれば、ユーザが関心のある道路
事情の位置を決定することにより、交通事情のリストを
通過することができる。ステップ５２２では、交通事情
のリストを更新して、車両が目的地へ進むにつれて放送
されたリアルタイムな交通データを含むようにする。

【００６５】ステップ５２４は、ステップ５２０の交通
事情メッセージを運転者が認めたか否かを質問する。車
両ナビゲーションユニットは例えばボタンを含み、ユー
ザはそのボタンを押して画面上に交通事情メッセージが
あることを認めることができる。ユーザが交通事情メッ
セージを認めない場合、プロセス５００はステップ５２
０へ戻り、システムは交通事情メッセージを表示し続け
る。しかし、ユーザが交通事情メッセージを認めた場
合、プロセスはステップ５０６へ進む。

【００６６】プロセス５００は、上述の実施形態とは異
なる多くの方法で実行することができる。先に述べたよ
うに、最初に決定される推定到着時刻は、車両がルート
上を目的地へ進むのに応じて変化する交通事情に応答し
て、新たな推定到着時刻を生成するように修正される。
別の実施形態によれば、新たな到着時刻または新たな通
行時間が所定の閾値を超えて増加した場合、車両ナビゲ
ーションユニットはユーザに新たな最速ルートを提供す
る。用語「通行時間」は、あるルートを通過するために
必要な時間、例えば１時間を指し、用語「推定到着時
刻」は車両が目的地に到着するおよその時刻、例えば8:
00p.m.を指す。本実施形態では、所定の閾値は、一定値
とし、もしくは最初の推定到着時刻または最初の推定到
着時刻を参照して決定される通行時間に依存して変化す
るようにすることができる。最初の推定到着時刻は、例
えば出発点からの出発時刻においてまたはその付近で計
算される。例を挙げれば、最初の推定到着時刻が8:00p.
m.であり、最初の通行時間が１時間である場合、車両が
最速ルートの半分を走行し、予期せぬ道路事情による新
たな推定到着時刻が8:30p.m.である（推定到着時刻につ
いての）所定の閾値を超えた時、またはそのかわりに新
たな通行時間が１時間である（通行時間についての）所
定の閾値を超えた時、ユーザには複数のルートが提供さ
れる。

【００６７】本発明の少なくともいくつかのステップは
スピーカシステムによる音声信号により実行できること
を覚えておくことは重要である。例を挙げれば、交通事
情メッセージ、推定到着時刻および推定遅延の表示、新
たなルートの選択、その他、をサウンドシステム上で適
切な指示を提供することにより実行することができる。
また、車両ナビゲーションシステムは、ユーザの音声命
令に応答して指示を通信することができる音声起動型シ
ステムとすることができる。

【００６８】本発明をその具体的な実施形態を参照して
特に図示および説明してきたが、本発明の精神および視
野から外れること無く、形態および詳細における上記お
よび他の変更が可能であることが当業者には理解される
であろう。したがって、本発明の範囲は、請求の範囲を
参照して決定されるべきである。

【００６９】

【発明の効果】本発明は、リアルタイムな交通放送デー
タを使用して、動的に変化する交通状況下で新たな最速
ルート提供する車両ナビゲーションシステムおよび方法
を提供する。

【図面の簡単な説明】

【図１】ナビゲーションシステムと通信する交通管理セ
ンタを示す。

【図２】本発明で使用する車両ナビゲーションシステム
のブロック図である。

【図３】図１の交通管理センタとナビゲーションシステ
ムとの間の通信中に通信プロトコルを形成するメッセー
ジの異なる層を示す。

【図４】本発明の具体的な実施形態にしたがって設計さ
れた車両ナビゲーションシステムが採用するルート生成
方法論を示す図である。

【図５】区分コストの時々刻々の調整を示す図である。

【図６】区分コストの時々刻々の調整を示す他の図であ
る。

【図７】本発明の一実施形態に従い、図２の車両ナビゲ
ーションユニットがリアルタイムな交通データを受信し
た時に、リアルタイムな交通データを更新する方法のフ
ローチャートを示す。

【図８】本発明の一実施形態に従い、放送されたリアル
タイムな交通データをユーザに通告する地図表示を生成
する方法のフローチャートを示す。

【図９】本発明の一実施形態に従い、放送されたリアル
タイムな交通データに基づいて、推定到着時刻および遅
延を決定する方法のフローチャートの一部である。

【図１０】本発明の一実施形態に従い、放送リアルタイ
ムな交通データに基づいて、推定到着時刻および遅延を
決定する方法のフローチャートの他の一部である。

【図１１】本発明の一実施形態に従い、放送リアルタイ
ムな交通データに基づいて、推定到着時刻および遅延を
決定する方法のフローチャートの他の一部である。

【符号の説明】

１０２…交通管理センタ １０４…送信機 １０６…車両 １０８…車両ナビゲーションシステム １１０…受信機 １１２…アンテナ ２００…車両ナビゲーションシステム ２１２…走行距離センサ ２１４…各速度センサ ２１６…交通データ受信機 ２１８…ＧＰＳ ２２０…計算手段 ２２２…通信インターフェース ２２４…ＣＰＵ ２２６…記憶媒体 ２２８…ＲＯＭ ２３０…ＲＡＭ ２３２…出力コントローラ ２３４…出力連絡機構 ２３６…ユーザインターフェース

───────────────────────────────────────────────────── フロントページの続き (71)出願人 398072953 5500 Ａｕｔｏ Ｃｌｕｂ Ｄｒｉｖｅ, Ｄｅａｒｂｏｒｎ，Ｍｉｃｈｉｇａｎ 48126Ｕ．Ｓ．Ａ. (72)発明者 ピーター フリヴカ ３世 アメリカ合衆国 カリフォルニア 94805 リッチモンド エスモンド アヴェニュ ー 3911

Claims (14)

【特許請求の範囲】
1. 【請求項１】 車両ナビゲーションシステムで最速ルー
   トを生成する方法において、 複数の道路区分についての実際の速度データを提供する
   放送信号を受信する工程であって、前記複数の道路区分
   の各々はある長さを有し、前記複数の道路区分のうちの
   選択された区分は結合してある位置から目的地への複数
   のルートの少なくとも一部を構成する工程と、 前記実際の速度データを使用して前記複数のルートを生
   成する工程と、 前記実際の速度データを使用して前記複数のルートの各
   々についての通行時間を決定する工程と、および前記通
   行時間に少なくとも部分的に基づいて、前記複数のルー
   トから前記最速ルートを選択する工程と、を有する方
   法。
2. 【請求項２】 前記放送信号を受信する工程は、ＦＭ放
   送信号またはセルラー放送信号のいずれかを受信するこ
   とを含む請求項１に記載の方法。
3. 【請求項３】 前記放送信号を受信する工程は、前記道
   路区分の少なくともいくつかについての道路事情データ
   を受信することを含む請求項１に記載の方法。
4. 【請求項４】 前記道路事情データは、道路の閉鎖、事
   故、迂回、緊急電話コール、イベント情報、駐車場の容
   量、破片の存在、および危険な天候状況に関する情報を
   含む請求項３に記載の方法。
5. 【請求項５】 地図表示テーブルを表示する工程をさら
   に有し、前記地図表示テーブルは前記複数の道路区分の
   サブセットの表示を含み、前記実際の速度データおよび
   道路事情は前記道路区分に関連付けされている請求項３
   に記載の方法。
6. 【請求項６】 前記複数のルートを生成する工程は、前
   記車両ナビゲーションシステムのユーザによる新たなル
   ートの選択に応じて実行される請求項１に記載の方法。
7. 【請求項７】 前記最速ルート上の第１の位置における
   前記最速ルートに関連する通行時間を更新して新たな通
   行時間を生成する工程と、および前記新たな通行時間が
   所定の閾値を超えたときに第２の複数のルートを生成す
   る工程と、をさらに有する請求項１に記載の方法。
8. 【請求項８】 前記所定の閾値は、最初の推定到着時刻
   を参照して決定される請求項７に記載の方法。
9. 【請求項９】 前記所定の閾値は、第１の位置をも参照
   して決定される請求項８に記載の方法。
10. 【請求項１０】 前記新たな通行時間が前記所定の閾値
    を超えた時に交通事情メッセージを提供する工程をさら
    に有し、前記交通事情メッセージは少なくとも１つの交
    通事情の表示を含む請求項８に記載の方法。
11. 【請求項１１】 前記通行時間を決定する工程は、所定
    の実際の速度データを使用することを含み、前記所定の
    実際の速度データは、前記車両ナビゲーションシステム
    に接続されたデータベース内に記憶されると共に、前記
    実際の速度データとは異なる請求項１に記載の方法。
12. 【請求項１２】 前記放送信号中のメッセージが以前に
    受信されたか否かを決定する工程と、 前記メッセージが以前に受信されていた場合には前記メ
    ッセージを破棄する工程と、および前記メッセージが以
    前に受信されていない場合には、前記車両ナビゲーショ
    ンシステムに接続されたメモリ記憶領域に前記メッセー
    ジを保存する工程と、をさらに有する請求項１に記載の
    方法。
13. 【請求項１３】 複数の道路区分についての実際の速度
    データを提供する放送信号を受信する手段であって、前
    記複数の道路区分の各々はある長さを有し、前記複数の
    道路区分のうちの選択された区分は結合してある位置か
    ら目的地への複数のルートの少なくとも一部を構成する
    手段と、 前記実際の速度データを使用して前記複数のルートを生
    成する手段と、 前記実際の速度データを使用して前記複数のルートの各
    々についての通行時間を決定する手段と、および前記通
    行時間上に少なくとも部分的に基づいて、前記複数のル
    ートから前記最速ルートを選択する手段と、を有する車
    両ナビゲーションシステム。
14. 【請求項１４】 受信機と、記憶媒体と、前記受信機お
    よび前記記憶媒体に接続されたプロセッサと、を備え、 前記プロセッサは、複数の道路区分についての実際の速
    度データを提供する放送信号を受信する工程であって、
    前記複数の道路区分の各々はある長さを有し、前記複数
    の道路区分のうちの選択された区分は結合してある位置
    から目的地への複数のルートの少なくとも一部を構成す
    る工程と、 前記実際の速度データを使用して前記複数のルートを生
    成する工程と、 前記実際の速度データを使用して前記複数のルートの各
    々についての通行時間を決定する工程と、および前記通
    行時間に少なくとも部分的に基づいて、前記複数のルー
    トから前記最速ルートを選択する工程と、を実行するよ
    うに構成される車両ナビゲーションユニット。