JPH09280880A - 経路算出装置及び経路算出方法 - Google Patents

Abstract

(57)【要約】 【課題】できるだけ差のある複数の経路を簡単に算出す
ることができる経路算出装置を提供すること。 【解決手段】利用テーブルに、道路地図データを構成す
るリンクごとに、複数の時間帯を記憶しておき、計算開
始リンクガ決まると（ステップＳ１）、利用テーブルで
指定された複数の時間帯を取得し（ステップＳ２）、そ
れぞれ取得された時間帯に関連した統計リンクコスト情
報をメモリの記憶内容からそれぞれ参照し、当該計算開
始リンクからユーザにより設定された目的地等までの複
数本の経路を算出する（ステップＳ５）。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、経路提供エリアの
経路ネットワークデータを構成するいずれかのリンクか
ら同エリア内の他のいずれかのリンクに到る経路を複数
本算出する経路算出装置及び方法に関するものである。

【０００２】

【従来の技術】従来より画面上に車両の位置方位を表示
し、車両の走行の便宜を図るために開発された車載ナビ
ゲーション装置が広く利用されている。前記車載ナビゲ
ーション装置は、ディスプレイ、各種センサ又はＧＰＳ
受信機（以下「各種センサ等」という）、道路地図メモ
リ、コンピュータ等を車両に搭載し、各種センサ等から
入力される位置データ及び道路地図メモリに格納されて
いる道路との関係に基づいて車両位置を検出し、この車
両位置を道路地図とともにディスプレイに表示するもの
である。

【０００３】ところで、このような車載ナビゲーション
装置において、自車位置および道路地図の表示だけでな
く、種々の交通情報も運転者または搭乗者（以下総称し
て「ユーザ」という）に提供できるようにすれば、ユー
ザに一層快適なドライビング環境を提供することができ
る。そこで、交通情報を車載ナビゲーション装置に提供
するため、路上の各所に設置される路上ビーコンや通信
回線（自動車電話回線等）を通して、交通情報を車両に
搭載されている車載ナビゲーション装置に提供すること
が行われている。車載ナビゲーション装置では、前記交
通情報を受信すると、当該交通情報を表示画面に表示し
たり音声出力する。これにより、最新の交通情報をユー
ザに提供することができる。

【０００４】一方、出発地から目的地に至る走行経路の
選択をするために、ユーザによる目的地の設定入力に応
じて車両の現在地（出発地とみなす）から目的地までの
経路をコンピュータにより自動的に計算する方法が提案
されている（特開平５−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 の番号を記録している。

【００３４】

【表１】

【００３５】有効時間帯Ｚ_k とは、１日あたり多数に区
切られた「時間帯」のうちから複数選ばれたもので、計
算開始リンクのリンクコストとして、この有効時間帯Ｚ
_k の統計リンクコストＴ_S (t) を採用し、それからつな
がるリンクについて経路探索を行う。例えば２５１番目
のリンクについては、番号２，９，１４，３２等の時間
帯が記録されているので、経路探索にあたっては、計算
開始リンクの統計リンクコストＴ_S (t) として、番号２
の時間帯の統計リンクコストＴ_S (t) を採用して、それ
からつながるリンクについて経路探索を行い、番号９の
時間帯の統計リンクコストＴ_S (t) を採用して、それか
らつながるリンクについて経路探索を行い、番号１４の
時間帯の統計リンクコストＴ_S (t) を採用して、それか
らつながるリンクについて経路探索を行い、以下同様に
続ける。

【００３６】コントローラ１６には、目的地及び各種計
算条件を入力するためのリモートコントローラキー（以
下単に「リモコンキー」という）４が入力制御部１３を
介して接続されている。リモコンキー４には、例えば地
図のスクロール、位置の設定、メニューの選択を行う
「ジョイスティック／セットキー」、現在地を表すカー
マークを中心とする道路地図画面を表示させる「地図キ
ー」、道路地図の表示スケールを拡大縮小する「縮尺キ
ー」、車両の進行方向を上に表示するか、地図の北を上
に表示するかを選択する「回転キー」、車両の走行軌跡
を表示するかしないかを切換える「軌跡キー」、現在地
から目的地までの最短時間経路を算出させたいときにワ
ンタッチで経路計算指示信号を入力できる「ルートキ
ー」、「目的地設定」，「ルート設定」などのメニュー
画面を表示させる「メニューキー」、メニュー操作時１
つ前の画面に戻す「リターンキー」等の各種のキー（い
ずれも図示せず）が備えられている。

【００３７】コントローラ１６は、ユーザによりリモコ
ンキー４を介して目的地及び各種計算条件（有料道路を
優先するか否か、フェリー利用を優先するか否か、又は
経由地を経由するか否か、など）が入力されると、この
入力された目的地データ等をＳＲＡＭ１６２に記憶する
とともに、車載地図専用ディスクＤから経路計算用道路
地図データを読出し、目的地及び車両位置検出部１４で
検出された現在地にそれぞれ近いリンク間の最短時間経
路を例えばダイクストラ法又はポテンシャル法を用いて
算出する。算出された最短時間経路は、ディスプレイ３
に表示されている道路地図上に例えば破線で重畳表示さ
れる。

【００３８】ここで、前記ポテンシャル法とは次のよう
な方法である。すなわち、出発地（目的地でもよい）に
近いリンクを計算開始リンクとし、目的地（出発地でも
よい）に最も近いリンクを計算終了リンクとし、ユーザ
により入力された各種計算条件に基づいて、計算開始リ
ンクから始まる所定地図領域内のリンクをすべて探索す
る。このとき、各リンクの統計リンクコストＴ_S (t) 又
は旅行時間予測値Ｔ_P(t) （後述する）を順次加算し、
最短でない経路は切捨て、最短経路を実現する経路のみ
を残すという処理を繰り返す。その結果、最終的に、最
短経路のみからなる経路のトリーが得られるので、計算
終了リンクから計算開始リンクまでの経路を逆に辿って
いけば、最短時間経路を得ることができる。

【００３９】コントローラ１６にはまた、ビーコン受信
機７が接続されている。ＣＰＵ１６１は、車両が路上ビ
ーコンＡの送信エリア内に進入して（図１参照）、路上
ビーコンＡから送信されている一連の最新のリンク交通
情報がビーコン受信機７で受信されると、当該リンク交
通情報をＳＲＡＭ１６２に与えて保持させる。ＣＰＵ１
６１では、前記方法によって最短時間経路を算出する
際、ＳＲＡＭ１６２にリンク交通情報が保持されている
場合には、前記経路計算用道路地図データに含まれてい
る統計リンクコストＴ_S (t) に、当該リンク交通情報を
利用して求めたリンクコスト（以下「リアルタイムリン
クコスト」という）を加味して予測リンクコストＴ
_P (t) を求め、この予測リンクコストＴ_P (t) に基づい
て複数の経路を算出する。ＳＲＡＭ１６２にリンク交通
情報が保持されていない場合には、統計リンクコストＴ
_S (t) をそのまま用いて複数の経路を算出する。

【００４０】図５から図８は、前記車載ナビゲーション
装置１における複数の経路の算出処理を説明するための
フローチャートである。ユーザは、走行前又は走行中
に、リモコンキー４を操作して目的地や経由地（以下代
表して「目的地」という）を入力する。コントローラ１
６は、車両位置検出部１４で検出された現在地に最も近
いリンクを計算開始リンクとし、目的地に最も近いリン
クを計算終了リンクとする（図５のステップＳ１）。

【００４１】次に、現在時刻を参照して、現在時刻の属
する出発時間帯Ｚ₀ を特定する（ステップＳ２）。そし
て、前述した利用テーブルを参照して、計算開始リンク
に対応する、現在時刻の属する出発時間帯Ｚ₀ 以後の時
間帯を順にチェックし（ステップＳ３）、ヒットした時
間帯すなわち有効時間帯Ｚ_k を複数特定する（ステップ
Ｓ４）。

【００４２】そしてコントローラ１６は、計算開始リン
クから始まる所定地図領域内のリンクをすべて探索す
る。この探索にあたり、まず初めに統計リンクコストＴ
_S (t) をそのまま用いて複数の経路を算出する方法を説
明し、その後ＳＲＡＭ１６２にリンク交通情報が保持さ
れていて、当該リンク交通情報を利用して求めたリンク
のリアルタイムリンクコストを加味して予測リンクコス
トＴ_P (t) を求め、この予測リンクコストＴ _P (t) に基
づいて複数の経路を算出する方法を説明する。 ＜統計リンクコストＴ_S (t) をそのまま用いて複数の経
路を算出する方法＞この方法では、所定地図領域内のリ
ンクのリンクコストとして、リンクごとにそれぞれ異な
った時間帯に属する統計リンクコストＴ_S (t) を用い
る。

【００４３】詳しく説明すると、有効時間帯Ｚ_k のう
ち、時間の最も早い有効時間帯Ｚ₁ をまず選定して、計
算開始リンクのリンクコストを、有効時間帯Ｚ₁ の統計
リンクコストＴ_S (t) とする。次に、この計算開始リン
クに続くリンクについては、計算開始リンクの有効時間
帯Ｚ₁ よりも計算開始リンクのリンクコスト分だけ遅い
有効時間帯、すなわち車両が当該リンクに到達するであ
ろうと考えられる時間帯を決定し、当該有効時間帯に属
する統計リンクコストＴ_S (t) をリンクコストとして用
いる。

【００４４】これにつながるリンクについても、同様に
して、リンクコストを加算していって、車両が当該リン
クに到達するであろうと考えられる時間帯の統計リンク
コストＴ_S (t) をリンクコストとして用いて、経路を探
索する（ステップＳ５）。なお、車両が当該リンクに到
達するであろうと考えられる時間帯の統計リンクコスト
Ｔ_S (t) をリンクコストとして用いる代わりに、所定地
図領域内の全てのリンクについて、一様に、計算開始リ
ンクの有効時間帯Ｚ₁ と同一の時間帯Ｚ₁の統計リンク
コストＴ_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) を用いて所定地図
領域内の経路を探索する（ステップＳ５）。

【００５１】経路の探索が終わると、計算終了リンクか
ら計算開始リンクまでの経路を逆に辿っていき、経路Ｌ
₁ を特定し記憶する（ステップＳ６）。さらに、利用テ
ーブルにヒットした有効時間帯Ｚ_k のうち、次に時間の
早い有効時間帯Ｚ₂ を選定して、前記＜統計リンクコス
トＴ_S (t) をそのまま用いて複数の経路を算出する方法
＞又は＜リアルタイムリンクコストと統計リンクコスト
Ｔ_S (t) を併用して複数の経路を算出する方法＞を用い
て経路探索を行い、経路Ｌ₂ を特定し記憶する。このよ
うなことを繰り返して、有効時間帯Ｚ_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 が存在する場合を示す。

【図４】外部から得られたリンクと前記リンクとの対応
関係を表す対応テーブルを示す図である。

【図５】車載ナビゲーション装置における複数経路の算
出処理を説明するためのフローチャートである。

【図６】車載ナビゲーション装置における複数経路の算
出処理を説明するためのフローチャートである（図５の
続き）。

【図７】車載ナビゲーション装置における複数経路の算
出処理を説明するためのフローチャートである（図６の
続き）。

【図８】車載ナビゲーション装置における複数経路の算
出処理を説明するためのフローチャートである（図７の
続き）。

【符号の説明】

Ａ 路上ビーコン Ｂ 通信回線 Ｃ 情報センター Ｄ 車載地図専用ディスク １ 車載ナビゲーション装置 ２ ＣＤドライブ ３ ディスプレイ ４ リモコンキー ５ 方位センサ ６ 距離センサ ７ ビーコン受信機 １１ メモリ制御部 １２ 表示制御部 １３ 入力処理部 １４ 車両位置検出部 １６ コントローラ １６１ ＣＰＵ １６２ ＳＲＡＭ １６３ ＤＲＡＭ １８ 音声制御部

Claims (10)

【特許請求の範囲】
1. 【請求項１】道路地図データが記憶された道路地図メモ
   リと、 各リンクに対応付けられた過去の交通情報を所定の時間
   要素ごとに統計的に処理することにより得られた統計リ
   ンクコスト情報を記憶した交通情報メモリと、 道路地図データを構成するリンクごとに、複数の時間帯
   が指定された利用テーブルと、 計算開始リンクが特定されると、当該計算開始リンクに
   ついてこの利用テーブルで指定された複数の時間帯を取
   得し、それぞれ取得された時間帯又はそれぞれ取得され
   た時間帯以後の時間帯に係る統計リンクコスト情報を前
   記交通情報メモリの記憶内容からそれぞれ参照し、これ
   らの統計リンクコスト情報に基づいて当該計算開始リン
   クからユーザにより設定された目的地等までの複数本の
   経路を計算する経路計算手段と、 経路計算手段によって計算された経路のいずれか又は全
   てを出力する出力手段とを有することを特徴とする経路
   算出装置。
2. 【請求項２】道路地図データが記憶された道路地図メモ
   リと、 外部からの最新のリンクコスト情報を取得する通信手段
   と、 通信手段により取得される最新のリンクコスト情報、及
   び各リンクに対応付けられた過去の交通情報を所定の時
   間要素ごとに統計的に処理することにより得られた統計
   リンクコスト情報を記憶した交通情報メモリと、 道路地図データを構成するリンクごとに、複数の時間帯
   が指定された利用テーブルと、 計算開始リンクが特定されると、当該計算開始リンクに
   ついてこの利用テーブルで指定された複数の時間帯を取
   得し、それぞれ取得された時間帯又はそれぞれ取得され
   た時間帯以後の時間帯に係る統計リンクコスト情報又は
   最新のリンクコスト情報を前記交通情報メモリの記憶内
   容からそれぞれ参照し、これらの統計リンクコスト情報
   又は最新のリンクコスト情報に基づいて当該計算開始リ
   ンクからユーザにより設定された目的地等までの複数本
   の経路を計算する経路計算手段と、 経路計算手段によって計算された経路のいずれか又は全
   てを出力する出力手段とを有することを特徴とする経路
   算出装置。
3. 【請求項３】前記経路計算手段によって複数の経路が計
   算されると、経路の差をチェックし、互いに差の大きな
   経路のみを選定する選定手段をさらに備え、前記出力手
   段は、選定手段によって選定された経路を出力すること
   を特徴とする請求項１又は２記載の経路算出装置。
4. 【請求項４】経路計算手段によって計算された経路に沿
   った、統計リンクコスト情報を参照して、経路旅行時間
   を算出する旅行時間算出手段をさらに有し、 前記出力手段は、経路旅行時間をも出力するものである
   ことを特徴とする請求項１記載の経路算出装置。
5. 【請求項５】外部からの最新のリンクコスト情報を取得
   する通信手段と、 経路計算手段によって計算された経路に沿った、統計リ
   ンクコスト情報と通信手段を通して得られた最新のリン
   クコスト情報とを参照して、経路旅行時間を算出する旅
   行時間算出手段とをさらに有し、 前記出力手段は、経路旅行時間をも出力するものである
   ことを特徴とする請求項１記載の経路算出装置。
6. 【請求項６】経路計算手段によって計算された経路に沿
   った、統計リンクコスト情報と前記最新のリンクコスト
   情報とを参照して、経路旅行時間を算出する旅行時間算
   出手段をさらに有し、 前記出力手段は、経路旅行時間をも出力するものである
   ことを特徴とする請求項２記載の経路算出装置。
7. 【請求項７】旅行時間算出手段によって算出された経路
   旅行時間に一定数（１＋ｂ）（ｂは正の実数）を乗じた
   経路最大旅行時間を算出する経路最大旅行時間算出手段
   をさらに有し、 前記出力手段は、経路最大旅行時間をも出力するもので
   あることを特徴とする請求項４記載の経路算出装置。
8. 【請求項８】旅行時間算出手段によって算出された経路
   旅行時間に一定数（１＋ａ）（ａは正の実数）を乗じた
   経路最大旅行時間を算出する経路最大旅行時間算出手段
   をさらに有し、 前記出力手段は、経路最大旅行時間をも出力するもので
   あることを特徴とする請求項５又は６記載の経路算出装
   置。
9. 【請求項９】道路地図データが記憶された道路地図メモ
   リと、 各リンクに対応付けられた過去の交通情報を所定の時間
   要素ごとに統計的に処理することにより得られた統計リ
   ンクコスト情報を記憶した交通情報メモリと、 道路地図データを構成するリンクごとに、複数の時間帯
   が指定された利用テーブルとを用い、 計算開始リンクを特定し、 当該計算開始リンクについてこの利用テーブルで指定さ
   れた複数の時間帯を取得し、 それぞれ取得された時間帯又はそれぞれ取得された時間
   帯以後の時間帯に係る統計リンクコスト情報を前記交通
   情報メモリの記憶内容からそれぞれ参照し、 これらの統計リンクコスト情報に基づいて当該計算開始
   リンクからユーザにより設定された目的地等までの複数
   本の経路を計算することを特徴とする経路算出方法。
10. 【請求項１０】道路地図データが記憶された道路地図メ
    モリと、 外部からの最新のリンクコスト情報を取得する通信手段
    と、 通信手段により取得される最新のリンクコスト情報、及
    び各リンクに対応付けられた過去の交通情報を所定の時
    間要素ごとに統計的に処理することにより得られた統計
    リンクコスト情報を記憶した交通情報メモリと、 道路地図データを構成するリンクごとに、複数の時間帯
    が指定された利用テーブルとを用い、 計算開始リンクを特定し、 当該計算開始リンクについてこの利用テーブルで指定さ
    れた複数の時間帯を取得し、 それぞれ取得された時間帯又はそれぞれ取得された時間
    帯以後の時間帯に係る統計リンクコスト情報又は最新の
    リンクコスト情報を前記交通情報メモリの記憶内容から
    それぞれ参照し、 これらの統計リンクコスト情報又は最新のリンクコスト
    情報に基づいて当該計算開始リンクからユーザにより設
    定された目的地等までの複数本の経路を計算することを
    特徴とする経路算出方法。