(57)【特許請求の範囲】
【請求項１】
使用者からの命令を入力する入力部と、各リンク毎のリンクコスト情報を含む地図情報および年間の渋滞情報を収納する情報記憶部と、位置情報を取得する位置測位手段と、前記位置測位手段により取得した位置情報から走行中のリンクを特定するリンク特定手段と、走行時点での日時を取得する日時データ取得手段と、前記リンク特定手段で特定されたリンクと前記日時データ取得手段で取得された日時とを関連づけて記憶する記憶部と、前記入力部により経路探索が指示された際には、目的地までの経路を構成するリンクおよび該リンクを走行する時刻と前記記憶部に記憶されたリンクおよび該リンクに関連づけて記憶された時間とをそれぞれ照合し、一致するリンクがあった場合には前記一致するリンクのコストを補正するとともに、一致するリンクが無い場合には前記情報記憶部に含まれる年間の渋滞情報から対応する日時・道路の渋滞情報を読み出してコストの補正を行い、経路探索を行うように制御する制御部を有することを特徴とする経路誘導装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、カーナビゲーション装置等の位置測位手段を用いた経路誘導装置に関するものである。
【０００２】
【従来の技術】
近年発展してきた、カーナビゲーション装置等の経路誘導装置において、始点、終点、中継点の指定により、自動的に最適な走行経路を探索する機能が定着しつつある。しかし、その走行経路探索機能は、ＣＤやＤＶＤ等による地図情報と、外部から電波等を介して入手される現在の渋滞情報のみを基にして計算を行っているため、使用者の好み、使用者の走行経験、道路実状等を無視した画一的な走行経路探索結果となっていた。また、その画一的動作を修正する機能も無かった。
【０００３】
以下に従来の経路誘導装置について、図面を参照しながら説明する。図１２は従来の経路誘導装置のブロック図を示したものである。図１２において、１．使用者からの命令を入力する入力部と、２．地図や各種メニューを表示する表示部と、３．一次記憶部と、４．二次記憶部と、５．経路探索プログラム等のプログラムを記憶するＲＯＭ等のプログラム格納部と、６．地図ＣＤ又はＤＶＤを駆動するＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭドライブ部と、７．位置測定部と、８．中央演算部と、以下の自動経路探索を実現するプログラム記録媒体から構成される９．経路探索手段と、１０．最小木作成手段と、１９．コスト計算手段０と、１３．現在位置取得手段と、１５．コマンド選択手段、を備える構成を有している。
【０００４】
以上のように構成された経路誘導装置について、以下その動作について説明する。図１４は従来の経路誘導装置における経路探索のフローチャートである。図１５は従来の経路誘導装置における最小コストツリー作成のフローチャートである。図１３は、従来の経路誘導装置におけるコスト計算のフローチャートである。
【０００５】
自動経路探索時には、先ず、入力部１を用いてコマンド選択手段１５により自動経路探索コマンドを選択する（Ｓ１）。次に、入力部１を用いて、始点、中継点、終点の指定を行う。この場合、登録地点名の選択、地図上の位置指定、緯度・経度指定等の方法を用いる（Ｓ２）。次に、入力部１を用いて高速道路優先、一般道路優先、おまかせ等の自動経路探索のモード選択を行う（Ｓ３）。次に、入力部１を用いてコマンド選択手段１５により自動経路探索開始コマンドを選択する（Ｓ４）。これにより、経路探索手段９のプログラムがプログラム格納部５から読み出され実行される。ここで、広く知られているダイクストラ法やＡ＊法等により、地図上の適当な範囲のノードについて、最小コストツリーを作成する（Ｓ５）。最後に、始点と終点間を結ぶ木を始点・終点間の最小コストの経路として表示部２に表示する（Ｓ６）。
【０００６】
続いて、最小コストツリー作成（Ｓ５）の詳細について、広く知られているダイクストラ法を用いた場合を例に取って、簡単に図３を用いて説明する。先ず、開始点に一番近い地図上のノードを着目ノードリストに設定する（Ｓ２−１）。次に、複数回計算して全てのノードが処理された場合には処理を終了する（Ｓ２−２）。そうでなければ、着目ノードリストの各々に接続するノードをすべてリストアップする（Ｓ２−３）。次に、もし、全ての接続ノードリスト内のノードが検査済みならループを抜け（Ｓ２−４）、最小コストツリーデータを更新（Ｓ２−７）して（Ｓ２−１）に戻る。もし、そうでなければ、各々の着目ノードから各々の接続ノードまでのコストを計算し（Ｓ２−５）、開始ノードから接続ノードまでのコストの累計値が最小になる物を見つける（Ｓ２−６）。
【０００７】
ここで、コスト計算（Ｓ２−５）の詳細について図１３を用いて説明する。コスト計算時には、着目ノードと接続ノード間を結ぶ道路のリンクＩＤの長さと乗算係数を地図ＣＤまたはＤＶＤから取得し（Ｓ２−５−１）、コストを計算する（Ｓ２−５−２）。
【０００８】
【発明が解決しようとする課題】
しかしながら上記の従来構成では、ＣＤやＤＶＤ等による地図情報と、外部から入手される現在の渋滞情報のみを基にして計算を行っているため、使用者の好み、実際の走行経験、道路実状等を無視した画一的な走行経路探索結果となっていた。また、その画一的動作を修正する機能も無かった。
【０００９】
【課題を解決するための手段】
この課題を解決するために、本発明は使用者からの命令を入力する入力部と、各リンク毎のリンクコスト情報を含む地図情報および年間の渋滞情報を収納する情報記憶部と、位置情報を取得する位置測位手段と、前記位置測位手段により取得した位置情報から走行中のリンクを特定するリンク特定手段と、走行時点での日時を取得する日時データ取得手段と、前記リンク特定手段で特定されたリンクと前記日時データ取得手段で取得された日時とを関連づけて記憶する記憶部と、前記入力部により経路探索が指示された際には、目的地までの経路を構成するリンクおよび該リンクを走行する時刻と前記記憶部に記憶されたリンクおよび該リンクに関連づけて記憶された時間とをそれぞれ照合し、一致するリンクがあった場合には前記一致するリンクのコストを補正するとともに、一致するリンクが無い場合には前記情報記憶部に含まれる年間の渋滞情報から対応する日時・道路の渋滞情報を読み出してコストの補正を行い、経路探索を行うように制御する制御部を有する構成とした。
【００１０】
この発明によれば、使用者が頻繁に使用する道路情報を蓄積し、日時を考慮した上で各道路のコストに反映する、または、蓄積保存されているＶＩＣＳ等の渋滞情報の推移データを読み出し、各道路のコストに反映することにより、実際の渋滞推移に促した最適な経路探索結果を得る事が可能となる。
【００１１】
【発明の実施の形態】
本発明の請求項１に記載の発明は、使用者からの命令を入力する入力部と、各リンク毎のリンクコスト情報を含む地図情報および年間の渋滞情報を収納する情報記憶部と、位置情報を取得する位置測位手段と、前記位置測位手段により取得した位置情報から走行中のリンクを特定するリンク特定手段と、走行時点での日時を取得する日時データ取得手段と、前記リンク特定手段で特定されたリンクと前記日時データ取得手段で取得された日時とを関連づけて記憶する記憶部と、前記入力部により経路探索が指示された際には、目的地までの経路を構成するリンクおよび該リンクを走行する時刻と前記記憶部に記憶されたリンクおよび該リンクに関連づけて記憶された時間とをそれぞれ照合し、一致するリンクがあった場合には前記一致するリンクのコストを補正するとともに、一致するリンクが無い場合には前記情報記憶部に含まれる年間の渋滞情報から対応する日時・道路の渋滞情報を読み出してコストの補正を行い、経路探索を行うように制御する制御部を有するものであり、使用者が頻繁に使用する道路情報を蓄積し、日時を考慮した上で各道路のコストに反映することにより、使用者の嗜好に合った経路探索結果を得る事が可能となるという作用を有する。なお、ＶＩＣＳ等の外部からの渋滞情報が入手可能な場合には、コスト計算手段の中でその渋滞情報を各道路のコストに反映させることで対応する。
【００１５】
（実施の形態１）
以下本発明の実施の形態１における経路誘導装置について、図面を参照しながら説明する。図１は本発明の実施の形態１における経路誘導装置のブロック図を示したものである。図１において、１は使用者からの命令を入力する入力部、２は地図や各種メニューを表示する表示部、３は一次記憶部、４は二次記憶部、５は経路探索プログラム等のプログラムを記憶するＲＯＭ等のプログラム格納部、６は地図ＣＤ又はＤＶＤを駆動するＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭドライブ部、７は位置測定部、８は中央演算部、９は経路探索手段、その中の１０は最小木作成手段、１１はコスト計算手段、１３は現在位置取得手段、１４は緯度経度から最も近いリンクＩＤを取得する対応リンクＩＤ取得手段、１２は現在日時取得手段、１５はコマンド選択手段を備える構成を有している。
【００１６】
以上のように構成された経路誘導装置について、以下その動作について説明する。図２は本発明の経路誘導装置における経路探索のフローチャートである。図３は本発明の経路誘導装置における最小コストツリー作成のフローチャートである。図４は、本発明の経路誘導装置におけるコスト計算のフローチャートである。図５は、本発明の実施の形態１における走行データ蓄積のフローチャートである。
【００１７】
通常の走行時には、日時データ取得手段１２により現在日時を取得する（Ｓ１０）。得られた日時データから走行軌跡点の発生間隔ｔ秒よりも前走行軌跡点の日時と現在日時との差が大きいかどうかの比較を行い（Ｓ１１）、もし大きければ、位置測定部７を介して現在位置取得手段１３により、現在の緯度・経度データを取得する（Ｓ１２）。次に、得られた現在位置データから、対応リンクＩＤ取得手段１４により、地図ＣＤ／ＤＶＤ内の対応する道路の番号（リンクＩＤ）を取得する（Ｓ１３）。事前に一個前のリンクＩＤを保存しておき、この新しいリンクＩＤと比較する（Ｓ１４）。もし、異なっていれば、新しいリンクＩＤと現在の日時情報を二次記憶部４へ保存する（Ｓ１５）。なお、その情報の保存時には、対応する地図パッチＩＤ毎に分けて保存しておくと、後に述べるデータ検索時に高速化を図ることができる。
【００１８】
自動経路探索時には、先ず、入力部１を用いてコマンド選択手段１５により自動経路探索コマンドを選択する（Ｓ１）。次に、入力部１を用いて、始点、中継点、終点の指定を行う。この場合、登録地点名の選択、地図上の位置指定、緯度・経度指定等の方法を用いる（Ｓ２）。次に、入力部１を用いて高速道路優先、一般道路優先、おまかせ等の自動経路探索のモード選択を行う（Ｓ３）。次、入力部１を用いてコマンド選択手段１５により自動経路探索開始コマンドを選択する（Ｓ４）。これにより、経路探索手段９のプログラムがプログラム格納部５から読み出され実行される。ここで、広く知られているダイクストラ法やＡ＊法等により、地図上の適当な範囲のノードについて、最小コストツリーを作成する（Ｓ５）。最後に、始点と終点間を結ぶ木を始点・終点間の最小コストの経路として表示部２に表示する（Ｓ６）。
【００１９】
続いて、最小コストツリー作成（Ｓ５）の詳細について、広く知られているダイクストラ法を用いた場合を例に取って、簡単に図３を用いて説明する。先ず、開始点に一番近い地図上のノードを着目ノードリストに設定する（Ｓ２−１）。次に、複数回計算して全てのノードが処理された場合には処理を終了する（Ｓ２−２）。そうでなければ、着目ノードリストの各々に接続するノードをすべてリストアップする（Ｓ２−３）。次に、もし、全ての接続ノードリスト内のノードが検査済みならループを抜け（Ｓ２−４）、最小コストツリーデータを更新（Ｓ２−７）して（Ｓ２−１）に戻る。もし、そうでなければ、各々の着目ノードから各々の接続ノードまでのコストを計算し（Ｓ２−５）、開始ノードから接続ノードまでのコストの累計値が最小になる物を見つける（Ｓ２−６）。
【００２０】
ここで、コスト計算（Ｓ２−５）の詳細について図４を用いて説明する。上で説明した様に、通常の走行時に走行した道路のリンクＩＤとその日時が記憶媒体に保存されている。コスト計算時には、着目ノードと接続ノード間を結ぶ道路のリンクＩＤの長さと乗算係数を地図ＣＤまたはＤＶＤから取得し（Ｓ２−５−１）、コストを計算する（Ｓ２−５−２）。もし、上記記憶媒体に保存されている走行経験データ内にこのリンクＩＤがあれば（Ｓ２−５−３）、その走行日時を考慮の上、その回数をカウントし、そのリンクＩＤのコストが下がる方向のコスト補正を行う（Ｓ２−５−４）。
【００２１】
これにより、使用者が頻繁に使用する道路情報を蓄積し、自動経路探索時に使用者が過去にその道路を使用した日時を考慮した上で各道路のコストに反映することにより、使用者の嗜好に合った経路探索結果を得る事が可能となる。
【００２２】
（実施の形態２）
以下本発明の実施の形態２における経路誘導装置について、図面を参照しながら説明する。図６は本発明の実施の形態２における経路誘導装置のブロック図を示したものである。図６において、１は使用者からの命令を入力する入力部、２は地図や各種メニューを表示する表示部、３は一次記憶部、４は二次記憶部、５は経路探索プログラム等のプログラムを記憶するＲＯＭ等のプログラム格納部、６は地図ＣＤ又はＤＶＤを駆動するＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭドライブ部、７は位置測定部、８は中央演算部、９は経路探索手段、その中の１０は最小木作成手段、１３は現在位置取得手段、１４は緯度経度から最も近いリンクＩＤを取得する対応リンクＩＤ取得手段、１２は現在日時取得手段、１５はコマンド選択手段、１６はコスト計算手段２、を備える構成を有している。
【００２３】
以上のように構成された経路誘導装置について、以下その動作について説明する。図２は本発明の経路誘導装置における経路探索のフローチャートである。図３は本発明の経路誘導装置における最小コストツリー作成のフローチャートである。図４は、本発明の経路誘導装置におけるコスト計算のフローチャートである。図７は、本発明の経路誘導装置における走行データ蓄積のフローチャートである。
【００２４】
通常の走行時には、日時データ取得手段１２により現在日時を取得する（Ｓ１０）。得られた日時データから走行軌跡点の発生間隔ｔ秒よりも前走行軌跡点の日時と現在日時との差が大きいかどうかの比較を行い（Ｓ１１）、もし大きければ、位置測定部７を介して現在位置取得手段（１３）により、現在の緯度・経度データを取得する（Ｓ１２）。次に、得られた現在位置データから、対応リンクＩＤ取得手段１４により、地図ＣＤ／ＤＶＤ内の対応する道路の番号（リンクＩＤ）を取得する。事前に一個前のリンクＩＤを保存しておき、この新しいリンクＩＤと比較する（Ｓ１４）。もし、異なっていれば、一個前のリンクＩＤの平均速度をリンク長とそのリンク上にプロットされた軌跡点数と軌跡点の時間間隔から算出し（Ｓ１６）、リンクＩＤと平均速度と現在の日時情報を二次記憶部４へ保存する（Ｓ１５）。なお、その情報の保存時には、対応する地図パッチＩＤ毎に分けて保存しておくと、後に述べるデータ検索時に高速化を図ることができる。
【００２５】
自動経路探索時には、先ず、入力部１を用いてコマンド選択手段１５により自動経路探索コマンドを選択する（Ｓ１）。次に、入力部１を用いて、始点、中継点、終点の指定を行う。この場合、登録地点名の選択、地図上の位置指定、緯度・経度指定等の方法を用いる（Ｓ２）。次に、入力部１を用いて高速道路優先、一般道路優先、おまかせ等の自動経路探索のモード選択を行う（Ｓ３）。次、入力部１を用いてコマンド選択手段１５により自動経路探索開始コマンドを選択する（Ｓ４）。これにより、経路探索手段９のプログラムがプログラム格納部５から読み出され実行される。ここで、広く知られているダイクストラ法やＡ＊法等により、地図上の適当な範囲のノードについて、最小コストツリーを作成する（Ｓ５）。最後に、始点と終点間を結ぶ木を始点・終点間の最小コストの経路として表示部２に表示する（Ｓ６）。
【００２６】
続いて、最小コストツリー作成（Ｓ５）の詳細について、広く知られているダイクストラ法を用いた場合を例に取って、簡単に図３を用いて説明する。先ず、開始点に一番近い地図上のノードを着目ノードリストに設定する（Ｓ２−１）。次に、複数回計算して全てのノードが処理された場合には処理を終了する（Ｓ２−２）。そうでなければ、着目ノードリストの各々に接続するノードをすべてリストアップする（Ｓ２−３）。次に、もし、全ての接続ノードリスト内のノードが検査済みならループを抜け（Ｓ２−４）、最小コストツリーデータを更新（Ｓ２−７）して（Ｓ２−１）に戻る。もし、そうでなければ、各々の着目ノードから各々の接続ノードまでのコストを計算し（Ｓ２−５）、開始ノードから接続ノードまでのコストの累計値が最小になる物を見つける（Ｓ２−６）。
【００２７】
ここで、コスト計算（Ｓ２−５）の詳細について図４を用いて説明する。上で説明した様に、通常の走行時に走行した道路のリンクＩＤと、その実走平均速度と、その日時が記憶媒体に保存されている。コスト計算時には、着目ノードと接続ノード間を結ぶ道路のリンクＩＤの長さと乗算係数を地図ＣＤまたはＤＶＤから取得し（Ｓ２−５−１）、コストを計算する（Ｓ２−５−２）。もし、上記記憶媒体に保存されている走行経験データ内にこのリンクＩＤがあれば（Ｓ２−５−３）、その走行日時を考慮の上、その実走平均速度を用いて、そのリンクＩＤのコスト補正を行う（Ｓ２−５−４）。
【００２８】
これにより、使用者が実際に道路を走行したときの道路情報と日時と平均走行速度を蓄積し、自動経路探索時に使用者が過去にその道路を使用した日時を考慮した上で予想平均走行速度を各道路のコストに反映することにより、実際の道路実状に促した最適な経路探索結果を得る事が可能となる。
【００２９】
（実施の形態３）
以下本発明の実施の形態３における経路誘導装置について、図面を参照しながら説明する。図８は本発明の実施の形態３における経路誘導装置のブロック図を示したものである。図８において、１は使用者からの命令を入力する入力部、２は地図や各種メニューを表示する表示部、３は一次記憶部、４は二次記憶部、５は経路探索プログラム等のプログラムを記憶するＲＯＭ等のプログラム格納部、６は地図ＣＤ又はＤＶＤを駆動するＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭドライブ部、７は位置測定部、８は中央演算部、９は経路探索手段、その中の１０は最小木作成手段、１３は現在位置取得手段、１４は緯度経度から最も近いリンクＩＤを取得する対応リンクＩＤ取得手段、１２は現在日時取得手段、１５はコマンド選択手段、１７はコスト計算手段３、を備える構成を有している。
【００３０】
以上のように構成された経路誘導装置について、以下その動作について説明する。図２は本発明の経路誘導装置における経路探索のフローチャートである。図３は本発明の経路誘導装置における最小コストツリー作成のフローチャートである。図９は本発明の実施の形態３におけるコスト計算のフローチャートである。図７は本発明の実施の形態２における経路誘導装置における走行データ蓄積のフローチャートである。
【００３１】
通常の走行時には、日時データ取得手段１２により現在日時を取得する（Ｓ１０）。得られた日時データから走行軌跡点の発生間隔ｔ秒よりも前走行軌跡点の日時と現在日時との差が大きいかどうかの比較を行い（Ｓ１１）、もし大きければ、位置測定部７を介して現在位置取得手段１３により、現在の緯度・経度データを取得する（Ｓ１２）。次に、得られた現在位置データから、対応リンクＩＤ取得手段１４により、地図ＣＤ／ＤＶＤ内の対応する道路の番号（リンクＩＤ）を取得する。事前に一個前のリンクＩＤを保存しておき、この新しいリンクＩＤと比較する（Ｓ１４）。もし、異なっていれば、一個前のリンクＩＤの平均速度をリンク長とそのリンク上にプロットされた軌跡点数と軌跡点の時間間隔から算出し（Ｓ１６）、リンクＩＤと平均速度と現在の日時情報を二次記憶部４へ保存する（Ｓ１５）。なお、その情報の保存時には、対応する地図パッチＩＤ毎に分けて保存しておくと、後に述べるデータ検索時に高速化を図ることができる。
【００３２】
自動経路探索時には、先ず、入力部１を用いてコマンド選択手段１５により自動経路探索コマンドを選択する（Ｓ１）。次に、入力部１を用いて、始点、中継点、終点の指定を行う。この場合、登録地点名の選択、地図上の位置指定、緯度・経度指定等の方法を用いる（Ｓ２）。次に、入力部１を用いて高速道路優先、一般道路優先、おまかせ等の自動経路探索のモード選択を行う（Ｓ３）。次、入力部１を用いてコマンド選択手段１５により自動経路探索開始コマンドを選択する（Ｓ４）。これにより、経路探索手段９のプログラムがプログラム格納部５から読み出され実行される。ここで、広く知られているダイクストラ法やＡ＊法等により、地図上の適当な範囲のノードについて、最小コストツリーを作成する（Ｓ５）。最後に、始点と終点間を結ぶ木を始点・終点間の最小コストの経路として表示部２に表示する（Ｓ６）。
【００３３】
続いて、最小コストツリー作成（Ｓ５）の詳細について、広く知られているダイクストラ法を用いた場合を例に取って、簡単に図３を用いて説明する。先ず、開始点に一番近い地図上のノードを着目ノードリストに設定する（Ｓ２−１）。次に、複数回計算して全てのノードが処理された場合には処理を終了する（Ｓ２−２）。そうでなければ、着目ノードリストの各々に接続するノードをすべてリストアップする（Ｓ２−３）。次に、もし、全ての接続ノードリスト内のノードが検査済みならループを抜け（Ｓ２−４）、最小コストツリーデータを更新（Ｓ２−７）して（Ｓ２−１）に戻る。もし、そうでなければ、各々の着目ノードから各々の接続ノードまでのコストを計算し（Ｓ２−５）、開始ノードから接続ノードまでのコストの累計値が最小になる物を見つける（Ｓ２−６）。最小累計コストが最小になるノードが見つかった場合には、開始点からそのノードまでの予想旅行時間も各道路のリンク長と予想平均速度から算出しておく。
【００３４】
ここで、コスト計算（Ｓ２−５）の詳細について図９を用いて説明する。上で説明した様に、通常の走行時に走行した道路のリンクＩＤと、その実走平均速度と、その日時が記憶媒体に保存されている。コスト計算時には、着目ノードと接続ノード間を結ぶ道路のリンクＩＤの長さと乗算係数と車線数と道路属性（高速道路、国道、県道等）などの情報を地図ＣＤまたはＤＶＤから取得し、その道路の平均速度を予測し（Ｓ２−５−１）、その予測平均速度を元にリンクコストを計算する（Ｓ２−５−２）。もし、上記記憶媒体に保存されている走行経験データ内にこのリンクＩＤがあれば（Ｓ２−５−３）、そのノードへ到達する予測日時と走行経験データの日時を比較・考慮の上、その実走平均速度を用いて、そのリンクＩＤのコスト補正を行う（Ｓ２−５−４）。同時に、実施の形態１のコスト計算手段１１を併用して、道路の頻用度をリンクコストに反映する事も出来る。もし、対応する日時・道路の走行経験データが存在しなければ、年間の渋滞情報を保存してあるＣＤ−ＲＯＭやＤＶＤの記憶メディアから対応する日時・道路の渋滞情報を読み出して、予測平均速度を算出しリンクコストに反映する（Ｓ２−５−５）。
【００３５】
これにより、各道路の予想平均速度を元として経路探索を行う時に、各地点への到達日時を考慮した上で平均速度を予想し各道路のコストに反映することにより、実際の走行時の道路実状に促した最適な経路探索結果を得る事が可能となる。
【００３６】
（実施の形態４）
以下本発明の実施の形態４における経路誘導装置について、図面を参照しながら説明する。図１０は本発明の実施の形態４における経路誘導装置のブロック図を示したものである。図１０において、１は使用者からの命令を入力する入力部、２は地図や各種メニューを表示する表示部、３は一次記憶部、４は二次記憶部、５は経路探索プログラム等のプログラムを記憶するＲＯＭ等のプログラム格納部、６は地図ＣＤ又はＤＶＤを駆動するＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭドライブ部、７は位置測定部、８は中央演算部、９は経路探索手段、その中の１０は最小木作成手段、１３は現在位置取得手段、１４は緯度経度から最も近いリンクＩＤを取得する対応リンクＩＤ取得手段、１２は現在日時取得手段、１５はコマンド選択手段、１７はコスト計算手段３、１８は運転特徴抽出手段、を備える構成を有している。
【００３７】
以上のように構成された経路誘導装置について、以下その動作について説明する。図２は本発明の経路誘導装置における経路探索のフローチャートである。図３は本発明の経路誘導装置における最小コストツリー作成のフローチャートである。図４は、本発明の経路誘導装置におけるコスト計算のフローチャートである。図１１は、本発明の実施の形態４における走行データ蓄積のフローチャートである。
【００３８】
通常の走行時には、日時データ取得手段１２により現在日時を取得する（Ｓ１０）。得られた日時データから走行軌跡点の発生間隔ｔ秒よりも前走行軌跡点の日時と現在日時との差が大きいかどうかの比較を行い（Ｓ１１）、もし大きければ、位置測定部７を介して現在位置取得手段１３により、現在の緯度・経度データを取得する（Ｓ１２）。次に、得られた現在位置データから、対応リンクＩＤ取得手段１４により、地図ＣＤ／ＤＶＤ内の対応する道路の番号（リンクＩＤ）を取得する。事前に一個前のリンクＩＤを保存しておき、この新しいリンクＩＤと比較する（Ｓ１４）。もし、異なっていれば、一個前のリンクＩＤの平均速度をリンク長とそのリンク上にプロットされた軌跡点数と軌跡点の時間間隔から算出し（Ｓ１６）、リンクＩＤと平均速度と現在の日時情報を二次記憶部４へ保存する（Ｓ１５）。なお、その情報の保存時には、対応する地図パッチＩＤ毎に分けて保存しておくと、後に述べるデータ検索時に高速化を図ることができる。次に、そのリンクＩＤの片側車線数、道路属性（国道、県道等）、そのリンクから現在の新しいリンクへの運動方向（道なり、右折、左折）等を逐次積算・保存する。
【００３９】
自動経路探索時には、先ず、入力部１を用いてコマンド選択手段１５により自動経路探索コマンドを選択する（Ｓ１）。次に、入力部１を用いて、始点、中継点、終点の指定を行う。この場合、登録地点名の選択、地図上の位置指定、緯度・経度指定等の方法を用いる（Ｓ２）。次に、入力部１を用いて高速道路優先、一般道路優先、おまかせ等の自動経路探索のモード選択を行う（Ｓ３）。次、入力部１を用いてコマンド選択手段１５により自動経路探索開始コマンドを選択する（Ｓ４）。これにより、経路探索手段９のプログラムがプログラム格納部５から読み出され実行される。ここで、広く知られているダイクストラ法やＡ＊法等により、地図上の適当な範囲のノードについて、最小コストツリーを作成する（Ｓ５）。最後に、始点と終点間を結ぶ木を始点・終点間の最小コストの経路として表示部２に表示する（Ｓ６）。
【００４０】
続いて、最小コストツリー作成（Ｓ５）の詳細について、広く知られているダイクストラ法を用いた場合を例に取って、簡単に図３を用いて説明する。先ず、開始点に一番近い地図上のノードを着目ノードリストに設定する（Ｓ２−１）。次に、複数回計算して全てのノードが処理された場合には処理を終了する（Ｓ２−２）。そうでなければ、着目ノードリストの各々に接続するノードをすべてリストアップする（Ｓ２−３）。次に、もし、全ての接続ノードリスト内のノードが検査済みならループを抜け（Ｓ２−４）、最小コストツリーデータを更新（Ｓ２−７）して（Ｓ２−１）に戻る。もし、そうでなければ、各々の着目ノードから各々の接続ノードまでのコストを計算し（Ｓ２−５）、開始ノードから接続ノードまでのコストの累計値が最小になる物を見つける（Ｓ２−６）。最小累計コストが最小になるノードが見つかった場合には、開始点からそのノードまでの予想旅行時間も各道路のリンク長と予想平均速度から算出しておく。
【００４１】
ここで、コスト計算（Ｓ２−５）の詳細について図９を用いて説明する。上で説明した様に、通常の走行時に走行した道路のリンクＩＤと、その実走平均速度と、その日時が記憶媒体に保存されている。コスト計算時には、着目ノードと接続ノード間を結ぶ道路のリンクＩＤの長さと乗算係数と車線数と道路属性（高速道路、国道、県道等）などの情報を地図ＣＤまたはＤＶＤから取得し、その道路の平均速度を予測し（Ｓ２−５−１）、その予測平均速度を元にリンクコストを計算する（Ｓ２−５−２）。もし、上記記憶媒体に保存されている走行経験データ内にこのリンクＩＤがあれば（Ｓ２−５−３）、そのノードへ到達する予測日時と走行経験データの日時を比較・考慮の上、その実走平均速度と、運転特徴抽出手段１８により得られた道路種別毎使用率、右左折・直進率、片側車線数道路毎使用率と一般平均値との差分を用いて、そのリンクＩＤのコスト補正を行う（Ｓ２−５−４）。同時に、実施の形態１のコスト計算手段１１を併用して、道路の頻用度をリンクコストに反映する事も出来る。もし、対応する日時・道路の走行経験データが存在しなければ、ＣＤ−ＲＯＭやＤＶＤの記憶メディアに年間の渋滞情報を保存しておき、対応する日時・道路の渋滞情報を読み出して、予測平均速度を算出しリンクコストに反映する（Ｓ２−５−５）。
【００４２】
これにより、使用者が実際に道路を走行している時の、使用者の走行パターンを自動的に分析し、自動経路探索時に必要なパラメータを自動抽出し逐次更新することで、明示的なパラメータを使用者に要求せずに、使用者にとって最適な経路探索結果を得る事が可能となる。
【００４３】
【発明の効果】
以上のように本発明によれば、使用者が頻繁に使用する道路情報を蓄積し、日時を考慮した上で各道路のコストに反映する、または、蓄積保存されているＶＩＣＳ等の渋滞情報の推移データを読み出し、各道路のコストに反映することにより、実際の渋滞推移に促した最適な経路探索結果を得る事が可能となる、という有利な効果が得られる。
【図面の簡単な説明】
【図１】本発明の実施の形態１における経路誘導装置のブロック図
【図２】本発明の経路誘導装置における経路探索のフローチャート
【図３】本発明の経路誘導装置における最小コストツリー作成のフローチャート
【図４】本発明の経路誘導装置におけるコスト計算のフローチャート
【図５】本発明の実施の形態１における走行データ蓄積のフローチャート
【図６】本発明の実施の形態２における経路誘導装置のブロック図
【図７】本発明の実施の形態２における走行データ蓄積のフローチャート
【図８】本発明の実施の形態３における経路誘導装置のブロック図
【図９】本発明の実施の形態３におけるコスト計算のフローチャート
【図１０】本発明の実施の形態４における経路誘導装置のブロック図
【図１１】本発明の実施の形態４における走行データ蓄積のフローチャート
【図１２】従来の経路誘導装置のブロック図
【図１３】従来の経路誘導装置におけるコスト計算のフローチャート
【図１４】従来の経路誘導装置における経路探索のフローチャート
【図１５】従来の経路誘導装置における最小コストツリー作成のフローチャート
【符号の説明】
１  入力部
２  表示部
３  一次記憶部
４  二次記憶部
５  プログラム格納部
６  ＣＤ／ＤＶＤ部
７  位置測定部
８  中央演算部
９  経路探索手段
１０  最小木作成手段
１１  コスト計算手段
１２  日時取得手段
１３  現在位置取得手段
１４  対応リンクＩＤ取得手段
１５  コマンド選択手段
１６  コスト計算手段２
１７  コスト計算手段３
１８  運転特徴抽出手段
１９  コスト計算手段０
【図１】
0004048605.tif 000002
【図２】
0004048605.tif 000003
【図３】
0004048605.tif 000004
【図４】
0004048605.tif 000005
【図５】
0004048605.tif 000006
【図６】
0004048605.tif 000007
【図７】
0004048605.tif 000008
【図８】
0004048605.tif 000009
【図９】
0004048605.tif 000010
【図１０】
0004048605.tif 000011
【図１１】
0004048605.tif 000012
【図１２】
0004048605.tif 000013
【図１３】
0004048605.tif 000014
【図１４】
0004048605.tif 000015
【図１５】
0004048605.tif 000016