(57)【特許請求の範囲】
【請求項１】
道路地図データが記憶された道路地図メモリと、
各リンクに対応付けられた過去の交通情報を所定の時間要素ごとに統計的に処理することにより得られた統計リンクコスト情報を記憶した交通情報メモリと、
道路地図データを構成するリンクごとに、複数の時間帯が指定された利用テーブルと、
計算開始リンクが特定されると、当該計算開始リンクについてこの利用テーブルで指定された複数の時間帯を取得し、それぞれ取得された時間帯又はそれぞれ取得された時間帯以後の時間帯に係る統計リンクコスト情報を前記交通情報メモリの記憶内容からそれぞれ参照し、これらの統計リンクコスト情報に基づいて当該計算開始リンクからユーザにより設定された目的地等までの複数本の経路を計算する経路計算手段と、
経路計算手段によって計算された経路のいずれか又は全てを出力する出力手段とを有することを特徴とする経路算出装置。
【請求項２】
道路地図データが記憶された道路地図メモリと、
外部からの最新のリンクコスト情報を取得する通信手段と、
通信手段により取得される最新のリンクコスト情報、及び各リンクに対応付けられた過去の交通情報を所定の時間要素ごとに統計的に処理することにより得られた統計リンクコスト情報を記憶した交通情報メモリと、
道路地図データを構成するリンクごとに、複数の時間帯が指定された利用テーブルと、
計算開始リンクが特定されると、当該計算開始リンクについてこの利用テーブルで指定された複数の時間帯を取得し、それぞれ取得された時間帯又はそれぞれ取得された時間帯以後の時間帯に係る統計リンクコスト情報又は最新のリンクコスト情報を前記交通情報メモリの記憶内容からそれぞれ参照し、これらの統計リンクコスト情報又は最新のリンクコスト情報に基づいて当該計算開始リンクからユーザにより設定された目的地等までの複数本の経路を計算する経路計算手段と、
経路計算手段によって計算された経路のいずれか又は全てを出力する出力手段とを有することを特徴とする経路算出装置。
【請求項３】
前記経路計算手段によって複数の経路が計算されると、経路の差異率をチェックし、差異率がしきい値より大きな経路のみを選定する選定手段をさらに備え、前記出力手段は、選定手段によって選定された経路を出力することを特徴とする請求項１又は２記載の経路算出装置。
【請求項４】
経路計算手段によって計算された経路に沿った、統計リンクコスト情報を参照して、経路旅行時間を算出する旅行時間算出手段をさらに有し、
前記出力手段は、経路旅行時間をも出力するものであることを特徴とする請求項１記載の経路算出装置。
【請求項５】
外部からの最新のリンクコスト情報を取得する通信手段と、
経路計算手段によって計算された経路に沿った、統計リンクコスト情報と通信手段を通して得られた最新のリンクコスト情報とを参照して、経路旅行時間を算出する旅行時間算出手段とをさらに有し、
前記出力手段は、経路旅行時間をも出力するものであることを特徴とする請求項１記載の経路算出装置。
【請求項６】
経路計算手段によって計算された経路に沿った、統計リンクコスト情報と前記最新のリンクコスト情報とを参照して、経路旅行時間を算出する旅行時間算出手段をさらに有し、
前記出力手段は、経路旅行時間をも出力するものであることを特徴とする請求項２記載の経路算出装置。
【請求項７】
旅行時間算出手段によって算出された経路旅行時間に一定数（１＋ｂ）（ｂは正の実数）を乗じた経路最大旅行時間を算出する経路最大旅行時間算出手段をさらに有し、
前記出力手段は、経路最大旅行時間をも出力するものであることを特徴とする請求項４記載の経路算出装置。
【請求項８】
旅行時間算出手段によって算出された経路旅行時間に一定数（１＋ａ）（ａは正の実数）を乗じた経路最大旅行時間を算出する経路最大旅行時間算出手段をさらに有し、
前記出力手段は、経路最大旅行時間をも出力するものであることを特徴とする請求項５又は６記載の経路算出装置。
【請求項９】
道路地図データが記憶された道路地図メモリと、
各リンクに対応付けられた過去の交通情報を所定の時間要素ごとに統計的に処理することにより得られた統計リンクコスト情報を記憶した交通情報メモリと、 道路地図データを構成するリンクごとに、複数の時間帯が指定された利用テーブルとを用い、
計算開始リンクを特定し、
当該計算開始リンクについてこの利用テーブルで指定された複数の時間帯を取得し、
それぞれ取得された時間帯又はそれぞれ取得された時間帯以後の時間帯に係る統計リンクコスト情報を前記交通情報メモリの記憶内容からそれぞれ参照し、
これらの統計リンクコスト情報に基づいて当該計算開始リンクからユーザにより設定された目的地等までの複数本の経路を計算することを特徴とする経路算出方法。
【請求項１０】
道路地図データが記憶された道路地図メモリと、
外部からの最新のリンクコスト情報を取得する通信手段と、
通信手段により取得される最新のリンクコスト情報、及び各リンクに対応付けられた過去の交通情報を所定の時間要素ごとに統計的に処理することにより得られた統計リンクコスト情報を記憶した交通情報メモリと、
道路地図データを構成するリンクごとに、複数の時間帯が指定された利用テーブルとを用い、
計算開始リンクを特定し、
当該計算開始リンクについてこの利用テーブルで指定された複数の時間帯を取得し、
それぞれ取得された時間帯又はそれぞれ取得された時間帯以後の時間帯に係る統計リンクコスト情報又は最新のリンクコスト情報を前記交通情報メモリの記憶内容からそれぞれ参照し、
これらの統計リンクコスト情報又は最新のリンクコスト情報に基づいて当該計算開始リンクからユーザにより設定された目的地等までの複数本の経路を計算することを特徴とする経路算出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路提供エリアの経路ネットワークデータを構成するいずれかのリンクから同エリア内の他のいずれかのリンクに到る経路を複数本算出する経路算出装置及び方法に関するものである。
【０００２】
【従来の技術】
従来より画面上に車両の位置方位を表示し、車両の走行の便宜を図るために開発された車載ナビゲーション装置が広く利用されている。前記車載ナビゲーション装置は、ディスプレイ、各種センサ又はＧＰＳ受信機（以下「各種センサ等」という）、道路地図メモリ、コンピュータ等を車両に搭載し、各種センサ等から入力される位置データ及び道路地図メモリに格納されている道路との関係に基づいて車両位置を検出し、この車両位置を道路地図とともにディスプレイに表示するものである。
【０００３】
ところで、このような車載ナビゲーション装置において、自車位置および道路地図の表示だけでなく、種々の交通情報も運転者または搭乗者（以下総称して「ユーザ」という）に提供できるようにすれば、ユーザに一層快適なドライビング環境を提供することができる。
そこで、交通情報を車載ナビゲーション装置に提供するため、路上の各所に設置される路上ビーコンや通信回線（自動車電話回線等）を通して、交通情報を車両に搭載されている車載ナビゲーション装置に提供することが行われている。車載ナビゲーション装置では、前記交通情報を受信すると、当該交通情報を表示画面に表示したり音声出力する。これにより、最新の交通情報をユーザに提供することができる。
【０００４】
一方、出発地から目的地に至る走行経路の選択をするために、ユーザによる目的地の設定入力に応じて車両の現在地（出発地とみなす）から目的地までの経路をコンピュータにより自動的に計算する方法が提案されている（特開平５−53504 号公報参照）。この方法は計算の対象となる道路又は車線を一連のベクトルとして表し（このベクトルを「リンク」という）、出発地（目的地でもよい）に近いリンクを計算開始リンクとし、目的地（出発地でもよい）に近いリンクを計算終了リンクとし、これらの間の道路地図メモリに記憶された道路地図データを読み出して作業領域に移し、作業領域において計算開始リンクから始まるリンクのトリーを全て探索し、最短リンクコストのトリーを得、このトリーを構成する経路のリンクコストを順次つないで、計算終了リンクに到達する経路を選択する方法である。
【０００５】
各リンクのリンクコストは、道路の渋滞状況、道路工事等による通行制限、事故の有無等によって時々刻々変動するものであるため、路上の各所に設置される路上ビーコンや通信回線（自動車電話回線等）を通して、車両に最新リンクコスト情報を提供することも現在検討されている。この地上システムによれば、道路の渋滞状況、通行制限、事故情報を含む最新のリンクコスト情報を地上システム側で用意しておき、路上ビーコンや自動車電話を通じて、リンクコスト情報を車両に送信する。これにより、車両が最適な経路を算出したり、旅行時間を算出したりするのを援助することができる。
【０００６】
【発明が解決しようとする課題】
ところが、複数の車両の車載ナビゲーション装置がそれぞれ最適経路を計算する場合には、路上ビーコンを通じて取得されるリンクコスト情報や、各車両の持っているリンクコストは、装置により大きな差はないので、同一方面に行く複数の車両が、同じような経路を計算してしまい、特定の経路のみ混雑し、最短時間で目的地に到達できないという現象が起こることが予想される。
【０００７】
したがって、車載ナビゲーション装置では、同じ目的地まで行くのに、できるだけ差のある複数の経路を計算して、複数の経路をユーザに示して選択させることが望ましい。
このような課題を解決するために、ネットワーク上の任意の点と終点との最短コストを算出し、始点からの部分経路を始点からのコストの累積と残りの経路の最短コストとの和に基づき、解析条件に従い複数の経路について展開する手法が提案されている（特開平５−４６５９０号公報参照）。この提案によれば、大きく迂回する経路は排除できるが、最短経路とほとんど差のない多数の経路が求まるだけで、できるだけ差のある複数の経路を得ることは難しい。
【０００８】
本発明の目的は、複数の経路を簡単に算出することができる経路算出装置及び方法を提供することである。
本発明の他の目的は、できるだけ差のある複数の経路を簡単に算出することができる経路算出装置及び方法を提供することである。
【０００９】
【課題を解決するための手段】
本発明の経路算出装置は、道路地図データが記憶された道路地図メモリと、各リンクに対応付けられた過去の交通情報を所定の時間要素ごとに統計的に処理することにより得られた統計リンクコスト情報を記憶した交通情報メモリと、道路地図データを構成するリンクごとに、複数の時間帯が指定された利用テーブルと、計算開始リンクが特定されると、当該計算開始リンクについてこの利用テーブルで指定された複数の時間帯を取得し、それぞれ取得された時間帯又はそれぞれ取得された時間帯以後の時間帯に係る統計リンクコスト情報を前記交通情報メモリの記憶内容からそれぞれ参照し、これらの統計リンクコスト情報に基づいて当該計算開始リンクからユーザにより設定された目的地等までの複数本の経路を計算する経路計算手段と、経路計算手段によって計算された経路のいずれか又は全てを出力する出力手段とを有するものである（請求項１）。
【００１０】
この発明によれば、まず利用テーブルに、道路地図データを構成するリンクごとに、複数の時間帯を記録しておく。
計算開始リンクが決まると、利用テーブルで指定された複数の時間帯を取得し、それぞれ取得された時間帯に関連した統計リンクコスト情報を前記交通情報メモリの記憶内容からそれぞれ参照し、当該計算開始リンクからユーザにより設定された目的地等までの複数本の経路を算出することができる。
【００１１】
この利用テーブルに記録する複数の時間帯は、例えば一日の中で区切られた時間帯からランダムに若しくは一定の約束で複数個選び出し記録した時間帯でもよい。この時間帯は一日の中で偏らないでなるべく散らばるほうがよい。１本のリンクに対応する複数の時間帯は、季節、月、曜日、平日／休日が異なるごとに異なる時間帯であってもよく、季節、月、曜日、平日／休日が異っても同じ時間帯であってもよい。
【００１２】
本発明の経路算出装置は、道路地図データが記憶された道路地図メモリと、外部からの最新のリンクコスト情報を取得する通信手段と、通信手段により取得される最新のリンクコスト情報、及び各リンクに対応付けられた過去の交通情報を所定の時間要素ごとに統計的に処理することにより得られた統計リンクコスト情報を記憶した交通情報メモリと、道路地図データを構成するリンクごとに、複数の時間帯が指定された利用テーブルと、計算開始リンクが特定されると、当該計算開始リンクについてこの利用テーブルで指定された複数の時間帯を取得し、それぞれ取得された時間帯又はそれぞれ取得された時間帯以後の時間帯に係る統計リンクコスト情報又は最新のリンクコスト情報を前記交通情報メモリの記憶内容からそれぞれ参照し、これらの統計リンクコスト情報又は最新のリンクコスト情報に基づいて当該計算開始リンクからユーザにより設定された目的地等までの複数本の経路を計算する経路計算手段と、経路計算手段によって計算された経路のいずれか又は全てを出力する出力手段とを有するものである（請求項２）。
【００１３】
この発明によれば、経路を計算する場合に、外部からの最新のリンクコスト情報等に基づいた旅行時間を使って、複数の経路を提供することができる。
本発明の経路算出装置は、請求項１又は２記載の経路算出装置であって、前記経路計算手段によって複数の経路が計算されると、経路の差異率をチェックし、差異率がしきい値より大きな経路のみを選定し、選定された経路を表示の対象とするものである（請求項３）。
【００１４】
ユーザに提供する複数の経路は、似通った経路であると、複数提供する意味がなくなるからである。
本発明の経路算出装置は、請求項１記載の経路算出装置であって、経路計算手段によって計算された経路に沿った、統計リンクコスト情報を参照して、経路旅行時間を算出する旅行時間算出手段をさらに有し、前記出力手段は、経路旅行時間をも出力するものである（請求項４）。
【００１５】
ユーザに経路とともに旅行時間を提供する場合に、統計リンクコスト情報に基づいた旅行時間を提供することができるので、過去の実績に基づいた、信頼度の高い旅行時間を提供することができる。
本発明の経路算出装置は、請求項１記載の経路算出装置であって、外部からの最新のリンクコスト情報を取得する通信手段と、経路計算手段によって計算された経路に沿った、統計リンクコスト情報と通信手段を通して得られた最新のリンクコスト情報とを参照して、経路旅行時間を算出する旅行時間算出手段とをさらに有し、前記出力手段は経路旅行時間をも出力するものである（請求項５）。
【００１６】
ユーザに経路とともに旅行時間を提供する場合に、外部からの最新のリンクコスト情報等に基づいた旅行時間を提供することができるので、現状を加味した旅行時間を提供することができる。
本発明の経路算出装置は、請求項２記載の経路算出装置であって、経路計算手段によって計算された経路に沿った、統計リンクコスト情報と前記最新のリンクコスト情報とを参照して、経路旅行時間を算出する旅行時間算出手段をさらに有し、前記出力手段は、経路旅行時間をも出力するものである（請求項６）。
【００１７】
ユーザに経路とともに旅行時間を提供する場合に、外部からの最新のリンクコスト情報等に基づいた旅行時間を提供することができるので、現状を加味した旅行時間を提供することができる。
本発明の経路算出装置は、請求項４記載の経路算出装置であって、旅行時間算出手段によって算出された経路旅行時間に一定数（１＋ｂ）（ｂは正の実数）を乗じた経路最大旅行時間を算出する経路最大旅行時間算出手段をさらに有し、前記出力手段は、経路最大旅行時間をも出力するものである（請求項７）。
【００１８】
本発明の経路算出装置は、請求項５又は６記載の経路算出装置であって、旅行時間算出手段によって算出された経路旅行時間に一定数（１＋ａ）（ａは正の実数）を乗じた経路最大旅行時間を算出する経路最大旅行時間算出手段をさらに有し、前記出力手段は、経路最大旅行時間をも出力するものである（請求項８）。
これらの発明によれば、通常よりも多めに見積もった最大旅行時間を表示することにより、ユーザに、最大これ位の時間がかかることを示すことができる。
【００１９】
また、本発明の経路算出方法は、請求項１又は請求項２記載の経路算出装置と同一の発明に係る経路算出方法である（請求項９，請求項１０）。
【００２０】
【発明の実施の形態】
以下、本発明の実施の形態を、添付図面を参照しながら詳細に説明する。
図１は、本発明の経路算出装置を適用した車載ナビゲーション装置に交通情報を提供するためのシステムの概略図である。この交通情報提供システムは、交通情報提供エリア内の各路上に設置された路上ビーコンＡと、この路上ビーコンＡに通信回線（公衆回線又は専用回線）Ｂを介して接続された情報センターＣとを含むものである。
【００２１】
なお、前記路上ビーコンＡは電波ビーコン、光ビーコンのいずれであってもよく、路上ビーコンＡに代えて、例えば自動車／携帯電話網やＦＭ多重放送網に用いられる通信装置又は送信装置を適用してもよい。
前記情報センターＣには、交通情報提供エリア内の主要交差点同士をつなぐリンクを構成単位とする相対的に粗い第１経路ネットワークに対応するリンク交通情報が記憶されている。このリンク交通情報は、例えば車両感知器、カメラ、上空を航行するヘリコプター、又は実際に道路を走行している交通情報収集車両で取得された時々刻々変化する最新の交通情報が各リンクに対応付けられて作成されたものである。
【００２２】
リンク交通情報は、例えばリンクに相当する道路を車両が走行するのに要する時間である旅行時間、渋滞度又は渋滞長に相当する内容を含むものである。例えば渋滞が発生すると、前記旅行時間又は渋滞長は相対的に長く、また渋滞度は相対的に大きくされ、渋滞が解消すると、前記旅行時間又は渋滞長は相対的に短く、また渋滞度は相対的に小さくされる。また、事故等が発生して通行不能になると、前記旅行時間は無限大にされる。通行規制がある場合も同様である。このリンク交通情報は、通信回線Ｂを介して路上ビーコンＡに一定時間（例えば５分）ごとに与えられる。この区切られた一定時間をそれぞれ「時間帯」という。例えば５分ごとに区切られるのであれば、１日あたり２８８の時間帯がある。
【００２３】
路上ビーコンＡは、前記リンク交通情報が通信回線Ｂを介して与えられると、当該リンク交通情報を車両に対して送信する。
図２は、車両に搭載される車載ナビゲーション装置の電気的構成を示すブロック図である。この車載ナビゲーション装置１には、車両の方位変化量を検出する方位センサ５及び車両の移動量を検出する距離センサ６が備えられている。方位センサ５としては、例えば光ファイバジャイロ、振動ジャイロ、ガスレートジャイロ等のジャイロ、又は地磁気センサが適用可能である。また、距離センサ６としては、例えばタイヤホイール又はロータの回転数を検出する回転数センサが適用可能である。前記方位センサ５及び距離センサ６の各出力は、車載ナビゲーション装置本体１内の車両位置検出部１４に与えられる。
【００２４】
車両位置検出部１４では、方位センサ５の出力に基づいて車両の進行方位が求められるとともに、距離センサ６の出力に基づいて車両の走行距離が求められる。車両位置検出部１４には、車両が発進する前に車両の正確な初期位置データがユーザによって与えられており、車両位置検出部１４では、この予め与えられている初期位置データと、前記車両の進行方位及び走行距離との累積に基づいて車両の現在地を検出する。この車両の現在地の検出は、一定周期（例えば１秒）ごとに繰り返される。
【００２５】
なお、前記方位センサ５、距離センサ６及び車両位置検出部１４の代わりに、又は方位センサ５、距離センサ６及び車両位置検出部１４とともに、地球の周回軌道を航行するＧＰＳ（Global Posioning System ）衛星から送信されるＧＰＳ電波の伝搬遅延時間に基づいて車両の現在地を検出するＧＰＳ受信機を採用してもよい。
【００２６】
車両位置検出部１４ではまた、前記検出された車両の現在地をいわゆるマップマッチング処理（例えば特開昭63-148115 号公報参照）により補正する。すなわち、前記方位センサ５及び距離センサ６の各出力に基づいて検出された車両の走行軌跡と、車載用地図専用ディスクＤに格納されている道路との類似度が照合され、その結果に応じて車両の走行軌跡が道路上に修正される。
【００２７】
マップマッチング処理により補正された車両の現在地データはコントローラ１６に与えられる。
コントローラ１６は、車載ナビゲーション装置本体１の制御中枢であって、ＣＰＵ１６１，ＳＲＡＭ１６２，及びＤＲＡＭ１６３を含むものである。コントローラ１６は、車両位置検出部１４から車両の現在地データが与えられると、メモリ制御部１１及びＣＤドライブ２を介して車載用地図専用ディスクＤから表示用道路地図データを読出す。読出された表示用道路地図データ及び前記現在地データは表示制御部１２に与えられる。表示制御部１２では、前記表示用道路地図データ及び現在地データが与えられると、車両の現在地を表すカーマークを道路地図に重畳して液晶表示素子，プラズマ表示素子又はＣＲＴで構成されたディスプレイ３に表示させる。また、経路に沿った誘導情報をスピーカＭを通して音声で提供する。
【００２８】
前記車載地図専用ディスクＤには、前記表示用道路地図データの他に、経路計算用道路地図データ、対応テーブル、利用テーブルが格納されている。
経路計算用道路地図データは、道路地図（高速自動車国道，自動車専用道路，その他の国道，都道府県道，政令指定都市の市道，その他の生活道路を含む）をメッシュ状に分割し、各メッシュ単位で道路の交差点等に相当するノードと各ノードをつなぐベクトルであるリンクとの組合わせからなる相対的に細かい第２経路ネットワークを、高速道路・国道対応地図と一般道路対応地図と詳細地図との３階層に分け、かつ時間帯ごとに分けて記憶している。その記憶内容は、固定リンクコスト、時間帯ごとの統計リンクコストＴS (t) 、各リンクごとのリンク長、そのリンクの始点ノード及び終点ノードの座標等が対応付けられたものとなっている。
【００２９】
前記統計リンクコストＴS (t) は、予め作成されたものであって、前記路上ビーコンＡを通じて過去一定期間に、当該交通情報提供エリア内で提供された時間帯ごとのリンク交通情報に基づいて、季節、月、曜日、平日／休日の別等（これらを時間要素という）のいずれか１つ又は複数の組合せごとに平均をとって記憶し、車載地図専用ディスクＤに書き込んだ値である。
【００３０】
統計リンクコストＴS (t) の作成方法について詳述すると、過去のリンク交通情報の収集は、たとえば交通情報ファクシミリサービスを利用して行うことが考えられる。また、この交通情報ファクシミリサービスの他に、道路交通情報センターが実施しているラジオ放送による交通情報提供サービス、またはケーブルテレビ（ＣＡＴＶ）による交通情報提供サービスを利用することもできる。
【００３１】
交通情報ファクシミリサービスを利用する場合について詳述すると、交通情報ファクシミリサービスは、文字や地図上に示された渋滞情報，旅行時間，通行禁止区間等の交通情報をファクシミリで提供するものである。作成者は、ファクシミリで提供された交通情報を時間帯、季節、月、曜日、平日／休日、ごとに分類し、統計的に整理する。たとえば、交通情報として渋滞情報を例にとった場合、渋滞情報を統計処理し、その結果を統計渋滞情報データとして整理する。
【００３２】
また、地図専用ディスクＤには、前記道路地図データの他、路上ビーコンＡから送信される交通情報が対応付けられたリンクと前記道路地図データのリンクとの対応関係を表す対応テーブルが格納されている（図４参照）。
この対応関係は、路上ビーコンＡから送信される交通情報が対応付けられたリンクが道路地図データのリンクよりも一般に粗い経路ネットワークの構成単位であるので、次のように分類できる。図３(a) は、路上ビーコンＡから送信されるリンクＬKaと道路地図データのリンクＬNaとが１対１に対応する場合を示す。図３(b) は、路上ビーコンＡから送信される１つのリンクＬKbに複数の道路地図データのリンクＬNb1 ，ＬNb2 ，・・・，ＬNbi が含まれている場合、図３(c) は、路上ビーコンＡから送信されるリンクＬK にうまく対応しない道路地図データのリンクＬN が存在する場合を示す。このうち、図３(a) ，(b) の場合の対応関係を表すのが対応テーブルであり、図４に対応テーブルの具体例をそれぞれ示す。図３(c) の場合には直接の対応関係がないので、本実施例では、対応テーブルの説明は省略する。
【００３３】
利用テーブルは、道路地図データのリンクに対応付けて、有効時間帯Ｚk の番号を記録している。
【００３４】
【表１】
0003709008.tif 000002
【００３５】
有効時間帯Ｚk とは、１日あたり多数に区切られた「時間帯」のうちから複数選ばれたもので、計算開始リンクのリンクコストとして、この有効時間帯Ｚk の統計リンクコストＴS (t) を採用し、それからつながるリンクについて経路探索を行う。
例えば２５１番目のリンクについては、番号２，９，１４，３２等の時間帯が記録されているので、経路探索にあたっては、計算開始リンクの統計リンクコストＴS (t) として、番号２の時間帯の統計リンクコストＴS (t) を採用して、それからつながるリンクについて経路探索を行い、番号９の時間帯の統計リンクコストＴS (t) を採用して、それからつながるリンクについて経路探索を行い、番号１４の時間帯の統計リンクコストＴS (t) を採用して、それからつながるリンクについて経路探索を行い、以下同様に続ける。
【００３６】
コントローラ１６には、目的地及び各種計算条件を入力するためのリモートコントローラキー（以下単に「リモコンキー」という）４が入力制御部１３を介して接続されている。リモコンキー４には、例えば地図のスクロール、位置の設定、メニューの選択を行う「ジョイスティック／セットキー」、現在地を表すカーマークを中心とする道路地図画面を表示させる「地図キー」、道路地図の表示スケールを拡大縮小する「縮尺キー」、車両の進行方向を上に表示するか、地図の北を上に表示するかを選択する「回転キー」、車両の走行軌跡を表示するかしないかを切換える「軌跡キー」、現在地から目的地までの最短時間経路を算出させたいときにワンタッチで経路計算指示信号を入力できる「ルートキー」、「目的地設定」，「ルート設定」などのメニュー画面を表示させる「メニューキー」、メニュー操作時１つ前の画面に戻す「リターンキー」等の各種のキー（いずれも図示せず）が備えられている。
【００３７】
コントローラ１６は、ユーザによりリモコンキー４を介して目的地及び各種計算条件（有料道路を優先するか否か、フェリー利用を優先するか否か、又は経由地を経由するか否か、など）が入力されると、この入力された目的地データ等をＳＲＡＭ１６２に記憶するとともに、車載地図専用ディスクＤから経路計算用道路地図データを読出し、目的地及び車両位置検出部１４で検出された現在地にそれぞれ近いリンク間の最短時間経路を例えばダイクストラ法又はポテンシャル法を用いて算出する。算出された最短時間経路は、ディスプレイ３に表示されている道路地図上に例えば破線で重畳表示される。
【００３８】
ここで、前記ポテンシャル法とは次のような方法である。すなわち、出発地（目的地でもよい）に近いリンクを計算開始リンクとし、目的地（出発地でもよい）に最も近いリンクを計算終了リンクとし、ユーザにより入力された各種計算条件に基づいて、計算開始リンクから始まる所定地図領域内のリンクをすべて探索する。このとき、各リンクの統計リンクコストＴS (t) 又は旅行時間予測値ＴP (t) （後述する）を順次加算し、最短でない経路は切捨て、最短経路を実現する経路のみを残すという処理を繰り返す。その結果、最終的に、最短経路のみからなる経路のトリーが得られるので、計算終了リンクから計算開始リンクまでの経路を逆に辿っていけば、最短時間経路を得ることができる。
【００３９】
コントローラ１６にはまた、ビーコン受信機７が接続されている。ＣＰＵ１６１は、車両が路上ビーコンＡの送信エリア内に進入して（図１参照）、路上ビーコンＡから送信されている一連の最新のリンク交通情報がビーコン受信機７で受信されると、当該リンク交通情報をＳＲＡＭ１６２に与えて保持させる。ＣＰＵ１６１では、前記方法によって最短時間経路を算出する際、ＳＲＡＭ１６２にリンク交通情報が保持されている場合には、前記経路計算用道路地図データに含まれている統計リンクコストＴS (t) に、当該リンク交通情報を利用して求めたリンクコスト（以下「リアルタイムリンクコスト」という）を加味して予測リンクコストＴP (t) を求め、この予測リンクコストＴP (t) に基づいて複数の経路を算出する。ＳＲＡＭ１６２にリンク交通情報が保持されていない場合には、統計リンクコストＴS (t) をそのまま用いて複数の経路を算出する。
【００４０】
図５から図８は、前記車載ナビゲーション装置１における複数の経路の算出処理を説明するためのフローチャートである。
ユーザは、走行前又は走行中に、リモコンキー４を操作して目的地や経由地（以下代表して「目的地」という）を入力する。コントローラ１６は、車両位置検出部１４で検出された現在地に最も近いリンクを計算開始リンクとし、目的地に最も近いリンクを計算終了リンクとする（図５のステップＳ１）。
【００４１】
次に、現在時刻を参照して、現在時刻の属する出発時間帯Ｚ0 を特定する（ステップＳ２）。そして、前述した利用テーブルを参照して、計算開始リンクに対応する、現在時刻の属する出発時間帯Ｚ0 以後の時間帯を順にチェックし（ステップＳ３）、ヒットした時間帯すなわち有効時間帯Ｚk を複数特定する（ステップＳ４）。
【００４２】
そしてコントローラ１６は、計算開始リンクから始まる所定地図領域内のリンクをすべて探索する。
この探索にあたり、まず初めに統計リンクコストＴS (t) をそのまま用いて複数の経路を算出する方法を説明し、その後ＳＲＡＭ１６２にリンク交通情報が保持されていて、当該リンク交通情報を利用して求めたリンクのリアルタイムリンクコストを加味して予測リンクコストＴP (t) を求め、この予測リンクコストＴP (t) に基づいて複数の経路を算出する方法を説明する。
＜統計リンクコストＴS (t) をそのまま用いて複数の経路を算出する方法＞
この方法では、所定地図領域内のリンクのリンクコストとして、リンクごとにそれぞれ異なった時間帯に属する統計リンクコストＴS (t) を用いる。
【００４３】
詳しく説明すると、有効時間帯Ｚk のうち、時間の最も早い有効時間帯Ｚ1 をまず選定して、計算開始リンクのリンクコストを、有効時間帯Ｚ1 の統計リンクコストＴS (t) とする。
次に、この計算開始リンクに続くリンクについては、計算開始リンクの有効時間帯Ｚ1 よりも計算開始リンクのリンクコスト分だけ遅い有効時間帯、すなわち車両が当該リンクに到達するであろうと考えられる時間帯を決定し、当該有効時間帯に属する統計リンクコストＴS (t) をリンクコストとして用いる。
【００４４】
これにつながるリンクについても、同様にして、リンクコストを加算していって、車両が当該リンクに到達するであろうと考えられる時間帯の統計リンクコストＴS (t) をリンクコストとして用いて、経路を探索する（ステップＳ５）。
なお、車両が当該リンクに到達するであろうと考えられる時間帯の統計リンクコストＴS (t) をリンクコストとして用いる代わりに、所定地図領域内の全てのリンクについて、一様に、計算開始リンクの有効時間帯Ｚ1 と同一の時間帯Ｚ1 の統計リンクコストＴS (t) をリンクコストとして用いてもよい。
＜リアルタイムリンクコストと統計リンクコストＴS (t) を併用して複数の経路を算出する方法＞
リアルタイムリンクコストをそのまま用いて経路を求めるのでは、リアルタイムリンクコストの瞬時的変動が激しすぎるので、この方法では、これを平滑化するため、統計リンクコストＴS (t) を加味した指数平滑手法を用いて予測リンクコストＴP (t) を求め、この予測リンクコストＴP (t) をリンクコストとして用いて所定地図領域内の経路を探索する。
【００４５】
この指数平滑手法では、当該経路計算対象リンクと外部から得られたリンクとが図３(a) に示すように１対１に対応している場合、前記外部から得られたリンクに対応する統計リンクコストＴS (t) をＳＲＡＭ１６２から読出すとともに、統計リンクコストＴS (t) を修正するために必要な誤差予測値ｅt を求める。
前記誤差予測値ｅt は、その初期値は０とするが、リアルタイムリンクコストの瞬時的変動が激しすぎるのでこれを平滑化して用いるという目的を考慮すると、予測リンクコストＴP (t) の瞬時的変動を吸収する必要がある。このため、同一の外部から得られたリンクのリアルタイムリンクコストに基づいて採用した誤差予測値ｅt-1 を考慮して重み付けした平均をとって誤差予測値ｅt とする。
【００４６】
より具体的に説明すると、予測リンクコストＴP (t) が得られると、予測リンクコストＴP (t) と、当該外部から得られたリンクの統計リンクコストＴS (t) との差を求める。
次に、メモリに保持されている、同一リンクの前の時点の予測リンクコストＴP (t−1)を読み出し、このリンクの統計リンクコストＴS (t) との差をとり、誤差予測値ｅt-1 を求め、下記(1) 式のようにして新たな誤差予測値ｅt に更新する。
【００４７】
ｅt ＝α（ＴP (t) −ＴS (t) ）＋（１−α）ｅt-1             ‥‥(1)
ただし、前記(1) 式において、α（０＜α＜１）は平滑指数であって、０に近ければ、過去の誤差予測値ｅt-1 に重みをおき、１に近ければ、現在の予測リンクコストＴP (t) に重みをおいている。例えばα＝０．８にとっている。
このようにして求められた誤差予測値ｅt を使って、下記(2) 式のようにして当該経路計算対象リンクに対応する予測リンクコストＴP (t) を算出する。
【００４８】
ＴP (t) ＝ｅt ＋ＴS (t)                                     ‥‥(2)
なお、前記の説明では、予測リンクコストと統計リンクコストとの差に着目していたが、予測リンクコストと統計リンクコストとの比に着目してもよい。この場合は前記(3) 式(4) 式は、それぞれ次のようになる（ｅt の初期値は１）。
【００４９】
ｅt ＝α（ＴP (t) ／ＴS (t) ）＋（１−α）ｅt-1             ‥‥(3)
ＴP (t) ＝ｅt ・ＴS (t)                                     ‥‥(4)
また、図３(b) に示すように、当該リンクが外部から得られたリンクの一部として含まれている場合には、前記(2) 式又は(4) 式に基づいて予測リンクコストＴP (t) が算出された後、下記(5) 式の演算が行われ、当該経路計算対象リンクに対応する予測リンクコストＴP (t) が算出される。ただし、下記(5) 式において、ｄNiは当該リンクi のリンク長、ｄK は前記外部から得られたリンクのリンク長を表す。
【００５０】
（ｄNi／ｄK ）×ＴP (t) →ＴP (t)                         ‥‥(5)
前記(2) 式若しくは(4) 式又は(5) 式で算出された予測リンクコストＴP (t) は不揮発性メモリに保持される。
このように、誤差予測値ｅt は、リアルタイムリンクコストの瞬時的変動を吸収するために求められるので、誤差予測値ｅt を用いて得られた予測リンクコストＴP (t) は、現在の交通状況を反映するとともに、実際の交通状況の極端な変動を抑えた値となっている。したがって、この予測リンクコストＴP (t) を用いて所定地図領域内の経路を探索する（ステップＳ５）。
【００５１】
経路の探索が終わると、計算終了リンクから計算開始リンクまでの経路を逆に辿っていき、経路Ｌ1 を特定し記憶する（ステップＳ６）。
さらに、利用テーブルにヒットした有効時間帯Ｚk のうち、次に時間の早い有効時間帯Ｚ2 を選定して、前記＜統計リンクコストＴS (t) をそのまま用いて複数の経路を算出する方法＞又は＜リアルタイムリンクコストと統計リンクコストＴS (t) を併用して複数の経路を算出する方法＞を用いて経路探索を行い、経路Ｌ2 を特定し記憶する。このようなことを繰り返して、有効時間帯Ｚn (n=1,2,3, ‥‥,m) に対応する複数の経路Ｌn (n=1,2,3, ‥‥,m) を特定する。全有効時間帯Ｚk のチェックが終了すると、ステップＳ７からステップＳ１１（図６）に移り、記憶された複数の経路Ｌn (n=1,2,3, ‥‥,m) を順に取り出し、差異率Ｄをチェックする。
【００５２】
この差異率Ｄというのは、各経路Ｌn (n=1,2,3, ‥‥,m) から任意の２つの経路Ｌi ，Ｌj を取り出し、それらについてリンクコスト（例えば統計リンクコストＴS (t) ）を総和して経路旅行時間Ｔi ，Ｔj を求め、さらに経路Ｌi ，Ｌj の重なり部分の経路旅行時間Ｔijを求め、これらを使って、
Ｄij＝１−２Ｔij／（Ｔi ＋Ｔj ）
で表される関数である。この差異率Ｄijをしきい値と比較し（ステップＳ１２）、差異率Ｄijがしきい値よりも小さければ（ステップＳ１３）、経路旅行時間の長いほうの経路を抹消して、ステップＳ１１に戻り、他の経路について処理を繰り返す。このようにして、差異率Ｄijがしきい値より大きな経路のみが選定される（ステップＳ１４）。記憶した全ての経路Ｌn (n=1,2,3, ‥‥,m) について処理が終了すると（ステップＳ１５）、ステップＳ２１（図７）に進む。
【００５３】
なお、上の説明では、差異率Ｄは経路旅行時間Ｔi ，Ｔj ，Ｔijに基づいて算出したが、経路距離に基づいてもよい。また、差異率Ｄを計算する代わりに絶対的な差異（Ｔi ＋Ｔj ）／２−Ｔijを計算し、しきい値と比較してもよい。
ステップＳ２１以後では、選定した各経路（これを経路Ｌp と書く）を構成するリンクについて、リンク旅行時間を計算する。このリンク旅行時間の計算にあたっては、車両が当該リンクに到達するであろうと考えられる時間を決定してリンク旅行時間を求め、このリンクにつながるリンクについては、時間をずらしながら、一連のリンクのリンクコストの加算を行う（この考え方は、経路探索のときと同じである）。
【００５４】
まず、１つの経路について、計算開始リンクから順に処理を進める（ステップＳ２２）。
当該リンクについて、予測リンクコストＴP (t) が得られているかどうかをチェックする（ステップＳ２３）。
得られていなければ、統計リンクコストＴS (t) を採用して、これを通常旅行時間とする（ステップＳ２４）。さらに、通常旅行時間に（１＋ｂ）をかけて、これを最大旅行時間とする（ステップＳ２５）。最大旅行時間は、通常よりも多めに見積もってこれ位の時間がかかることをユーザに示すために計算するものである。ｂは、統計リンクコストＴS (t) の信頼性が高いほど小さくし、統計リンクコストＴS (t) の信頼性が低い程大きくする。通常ｂ＝０．１から０．２程度にとる。
【００５５】
当該リンクについて、予測リンクコストＴP (t) が得られていれば、予測リンクコストＴP (t) を採用して、これを通常旅行時間とする（ステップＳ２６）。さらに、通常旅行時間に（１＋ａ）をかけて、これを最大旅行時間とする（ステップＳ２７）。ａは、予測リンクコストＴP (t) の信頼性が高いほど小さくし、予測リンクコストＴP (t) の信頼性が低い程大きくする。通常ａ＝０．１から０．２程度にとる。
【００５６】
１つの経路ＬP を構成するすべてのリンクについて処理が終われば（ステップＳ２８）、ステップＳ３１（図８）に進む。
ステップＳ３１では、当該経路Ｌp について、通常旅行時間を合計し、これを経路旅行時間とする（ステップＳ３１）。また最大旅行時間を合計し、これを経路最大旅行時間とする（ステップＳ３２）。
【００５７】
なお、前述の予測リンクコストＴP (t) を主体として旅行時間を求める方法以外に、予測リンクコストＴP (t) は無視して、統計リンクコストＴS (t) のみに基づいて旅行時間を計算することもできる。
他の経路Ｌp についてもステップＳ２１以下の処理をし、すべての経路Ｌp について処理が終われば（ステップＳ３３）、得られた経路ＬP の個数が一定個数ｃを超えるかどうか判定する（ステップＳ３４）。一定個数ｃを超えていれば、経路旅行時間の小さい順にｃ個の経路（これを経路ＬQ と書く）を最終選定する（ステップＳ３６）。一定個数ｃを超えていなければ、全部の経路ＬP を経路ＬQ として最終選定する（ステップＳ３５）。
【００５８】
そして、最終選定した経路ＬQ を表示する（ステップＳ３７）。この表示は、最終選定した経路ＬQ を一度に全部表示してもよいし、いずれか１本の経路ＬQ を表示して、ユーザの要求があれば他の経路ＬQ に切り換えるようにしてもよい。
また、経路旅行時間と、経路最大旅行時間も表示する（ステップＳ３８）。この表示をする場合は、単なる経路旅行時間であるか、経路最大旅行時間であるかに応じて表示の仕方を変えることが望ましいのは、勿論のことである。
【００５９】
そして、当該経路に対応する誘導指示情報を作成する。この経路に対応する誘導指示情報の内容としては、目的地までの方向、目的地までの直線距離、経路に沿った経路距離、交差点模式図等、従来より知られている色々なものがあり、これらのいずれか又はすべての情報がユーザに提供される。提供の方法は、ディスプレイ３に文字や矢印を表示させてもよく、スピーカＭから音声で誘導させてもよい。
【００６０】
本発明の実施例の説明は以上のとおりであるが、本発明は上述の実施例に限定されるものではない。例えば前記実施例では、複数経路の算出を車載ナビゲーション装置で行っていた。しかし、情報センターＣ等の地上系のシステムで複数経路の算出を行い、路上ビーコンＡを通して各車両に提供するものであってもよく、また、ユーザがオフィス等に設置されたパーソナルコンピュータを使って複数経路の算出を行ってもよい。
【００６１】
その他本発明の範囲内において種々の設計変更を施すことは可能である。
【００６２】
【発明の効果】
以上のように請求項１又は請求項９記載の発明によれば、利用テーブルを用いて、利用テーブルで指定された複数の時間帯を取得し、それぞれ取得された時間帯に関連した統計リンクコスト情報を使って、当該計算開始リンクから目的地等までの複数本の経路を、簡単に算出することができる。ユーザは、これらの複数本の経路の中からいずれかを任意に選択して旅行をすることができる。
【００６３】
請求項２又は請求項１０記載の発明によれば、外部からの最新のリンクコスト情報を取得し、統計リンクコスト情報又は最新のリンクコスト情報に基づいて、現状の交通状況に基づいた複数本の経路を得ることができる。
請求項３記載の発明によれば、できるだけ差のある複数の経路を得ることができる。
【００６４】
請求項４記載の発明によれば、過去の実績に基づいた、信頼度の高い旅行時間を提供することができる。
請求項５又は６記載の発明によれば、外部からの最新のリンクコスト情報等に基づいた、実際の交通状況を反映した旅行時間を提供することができる。
請求項７又は８記載の発明によれば、通常よりも多めに見積もった最大旅行時間を表示することにより、ユーザに、最大これ位の時間がかかることを示すことができる。
【図面の簡単な説明】
【図１】本発明の経路算出装置を使用した車載ナビゲーション装置に交通情報を提供するシステムの概略図である。
【図２】車両に搭載される車載ナビゲーション装置の電気的構成を示すブロック図である。
【図３】外部から得られたリンクＬKaとリンクＬNaとの対応関係を示す図であり、図３(a) は、外部から得られたリンクＬKaとリンクＬNaとが１対１に対応する場合、図３(b) は、１つの外部から得られたリンクＬKbに複数のリンクＬNb1 ，ＬNb2 ，・・・，ＬNbi が含まれている場合、図３(c) は、外部から得られたリンクＬK にうまく対応しないリンクＬN が存在する場合を示す。
【図４】外部から得られたリンクと前記リンクとの対応関係を表す対応テーブルを示す図である。
【図５】車載ナビゲーション装置における複数経路の算出処理を説明するためのフローチャートである。
【図６】車載ナビゲーション装置における複数経路の算出処理を説明するためのフローチャートである（図５の続き）。
【図７】車載ナビゲーション装置における複数経路の算出処理を説明するためのフローチャートである（図６の続き）。
【図８】車載ナビゲーション装置における複数経路の算出処理を説明するためのフローチャートである（図７の続き）。
【符号の説明】
Ａ  路上ビーコン
Ｂ  通信回線
Ｃ  情報センター
Ｄ  車載地図専用ディスク
１  車載ナビゲーション装置
２  ＣＤドライブ
３  ディスプレイ
４  リモコンキー
５  方位センサ
６  距離センサ
７  ビーコン受信機
１１  メモリ制御部
１２  表示制御部
１３  入力処理部
１４  車両位置検出部
１６  コントローラ
１６１  ＣＰＵ
１６２  ＳＲＡＭ
１６３  ＤＲＡＭ
１８  音声制御部
【図１】
0003709008.tif 000003
【図２】
0003709008.tif 000004
【図３】
0003709008.tif 000005
【図４】
0003709008.tif 000006
【図５】
0003709008.tif 000007
【図６】
0003709008.tif 000008
【図７】
0003709008.tif 000009
【図８】
0003709008.tif 000010