(57)【要約】【課題】車両の案内経路の決定にあたり、渋滞コストをできる限り実際の渋滞コストに近づけるようにして、自動車の案内経路を探索する自動車用ナビゲーションシステム及びナビゲーション方法を提供する。【解決手段】現在位置Ｓからある交差点までの経路において、当該経路上の各交差点に接続する全リンクの重み付けした渋滞コストＢの総和としてエリア渋滞コストＣｉｊｋを算出する。探索経路上の各交差点のエリア渋滞コストＣｉｊｋを含めた各経路のノードコストの相互比較及び算出を繰り返し、目的地Ｇに到達した経路のうちノードコストが最小となる経路を案内経路として探索する。【選択図】    図３
2005055193.tif 000002
【特許請求の範囲】
【請求項１】
自動車の現在位置を検出する現在位置検出手段と、
目的地を入力操作する入力手段と、
複数のリンク及びノードを有する地図データを記憶してなる記憶手段と、
前記地図データの各リンクに対して、交通情報システムより送信される交通情報に基づき渋滞コストを設定する渋滞コスト設定手段と、
前記地図データの各ノードに対して、該ノードに接続する複数のリンクの前記渋滞コストに基づくエリア渋滞コストを設定するエリア渋滞コスト設定手段と、
前記渋滞コスト及び前記エリア渋滞コストに基づき、前記現在位置から前記目的地までの経路を探索する経路探索手段とを備える自動車用ナビゲーションシステム。
【請求項２】
前記エリア渋滞コスト設定手段は、ノードに進入するリンクの渋滞コスト、又は該ノードから退出するリンクの渋滞コストに基づくエリア渋滞コストを設定することを特徴とする請求項１に記載の自動車用ナビゲーションシステム。
【請求項３】
前記エリア渋滞コスト設定手段は、ノードに進入する全てのリンクの渋滞コスト及び該ノードから退出する１つのリンクの渋滞コストに基づくエリア渋滞コストを設定することを特徴とする請求項１に記載の自動車用ナビゲーションシステム。
【請求項４】
前記エリア渋滞コスト設定手段は、ノードに接続する複数のリンクの前記渋滞コストそれぞれに影響係数を乗算しそれらを総和した値を、該ノードのエリア渋滞コストとして設定することを特徴とする請求項１乃至３のいずれか一つに記載の自動車用ナビゲーションシステム。
【請求項５】
前記エリア渋滞コスト設定手段は、ノードに接続するリンクの他のノードに設定されたエリア渋滞コストを全て相加平均した値を、前記ノードの広域エリア渋滞コストとして設定し、
前記経路探索手段は、前記渋滞コスト、前記エリア渋滞コスト及び前記広域エリア渋滞コストに基づき、経路を探索することを特徴とする請求項１乃至４のいずれか一つに記載の自動車用ナビゲーションシステム。
【請求項６】
自動車に設置されるナビゲーション装置と、自動車とは別に設置される情報センターとを備え、
前記ナビゲーション装置は、
自動車の現在位置を検出する現在位置検出手段と、
目的地を入力操作する入力手段と、
複数のリンク及びノードを有する地図データを記憶してなる記憶手段と、
経路探索手段と、通信手段とを備え、
前記情報センターは、
交通情報システムより送信される交通情報を受信する通信部と、
前記地図データを記憶し、また、前記通信部の受信交通情報を記憶する情報記憶部と、
前記地図データの各リンクに対して、前記情報記憶部からの前記交通情報に基づき渋滞コストを設定する渋滞コスト設定手段と、
前記地図データの各ノードに対して、該ノードに接続する複数のリンクの前記渋滞コストに基づくエリア渋滞コストを設定するエリア渋滞コスト設定手段とを備え、
前記情報センターは、前記通信部により前記渋滞コスト及び前記エリア渋滞コストを送信し、
前記ナビゲーション装置では、前記通信手段は、前記通信部からの前記渋滞コスト及び前記エリア渋滞コストを受信し、
前記経路探索手段は、前記通信手段からの前記渋滞コスト及び前記エリア渋滞コストに基づき、前記現在位置から前記目的地までの経路を探索する自動車用ナビゲーションシステム。
【請求項７】
交通情報システムより送信される交通情報に基づき渋滞コストを設定し、
地図データの各ノードに対して、該ノードに接続する複数のリンクの渋滞コストに基づくエリア渋滞コストを設定し、
前記渋滞コスト及び前記エリア渋滞コストに基づき、自動車の現在位置から目的地までの経路を探索するようにしたことを特徴とする自動車用ナビゲーション方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、自動車用ナビゲーションシステム及びナビゲーション方法に関する。
【０００２】
【従来の技術】
従来、この種のナビゲーションシステムでは、道路交通情報（ＶＩＣＳ情報）を利用して、経路案内のための交通情報を提供するようにしている。このＶＩＣＳ情報によれば、渋滞コストとして、「渋滞情報なし」、「空いている」、「混雑」及び「渋滞」の４状態が提供されるようになっている。
【０００３】
このような交通情報を用いて、案内経路を計算するにあたっては、例えば、下記特許文献１に開示されたナビゲーションシステムのように、渋滞度に応じた重み係数でもって重み付けしたリンクコストを用いて距離的最短経路を計算するようにしたものがある。
【０００４】
【特許文献１】
特開平８−３１３２８５号公報
【０００５】
【発明が解決しようとする課題】
ところで、上記ナビゲーションシステムでは、リンクコストが、リンク単体にのみ渋滞コストを重み付けを付して計算されているにすぎず、周辺のリンク情報までは考慮されていない。従って、上記４状態の渋滞コストに単に重み付けしたにすぎず、４状態であることに変わりがない。
【０００６】
しかし、実際の渋滞は、連続的に変化するため、上述のようなリンク単位の渋滞コストでは実際の渋滞コストからは大きく外れることとなり、渋滞コストとしては適切でない。従って、このような渋滞コストを用いて上記案内経路の計算をしても、適切な案内経路は決定し得ないという不具合がある。
【０００７】
そこで、本発明は、以上のようなことに対処するため、渋滞コストをできる限り実際の渋滞コストに近づけるようにして、自動車の案内経路を探索する自動車用ナビゲーションシステム及びナビゲーション方法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
上記課題の解決にあたり、本発明に係る自動車用ナビゲーションシステムは、請求項１の記載によれば、
自動車の現在位置を検出する現在位置検出手段（１０）と、
目的地を入力操作する入力手段（２０、１００）と、
複数のリンク及びノードを有する地図データを記憶してなる記憶手段（４０）と、
地図データの各リンクに対して、交通情報システム（７０）より送信される交通情報に基づき渋滞コスト（Ｂ）を設定する渋滞コスト設定手段（５０、１０１、１１０、１３０）と、
地図データの各ノードに対して、該ノードに接続する複数のリンクの渋滞コストに基づくエリア渋滞コスト（Ｃｉｊｋ）を設定するエリア渋滞コスト設定手段（１４０）と、
渋滞コスト及びエリア渋滞コストに基づき、現在位置から目的地までの経路を探索する経路探索手段（１６０）とを備える。
【０００９】
これによれば、各ノードに対して、そのノードに接続しているリンクの渋滞コストに基づくエリア渋滞コストが付与されているので、複数のリンクの交通情報を考慮した渋滞コストを新たに設定することが出来る。
【００１０】
また、渋滞コスト、エリア渋滞コストを使って最適経路を探索するので、例えば、交通情報が送信されないリンクがあっても、そのリンクの端点のノードに設定されたエリア渋滞コストを使って最適経路を探索することができる。
【００１１】
従って、このようなコストを用いて、渋滞しているリンクが接続しているノードをできるだけ通らない経路を探索することができる。
【００１２】
また、本発明に係る自動車用ナビゲーションシステムは、請求項２の記載によれば、請求項１に記載の発明において、
エリア渋滞コスト設定手段は、ノードに進入するリンクの渋滞コスト、又は該ノードから退出するリンクの渋滞コストに基づくエリア渋滞コストを設定する。
【００１３】
これによれば、探索経路上のエリア渋滞コストは、進入及び退出の方向を考慮した渋滞コストに基づき設定される。従って、経路探索の精度がさらに向上し、その結果、請求項１に記載の発明の作用効果をより一層向上できる。
【００１４】
また、本発明に係る自動車用ナビゲーションシステムは、請求項３の記載によれば、請求項１に記載の発明において、
エリア渋滞コスト設定手段は、ノードに進入する全てのリンクの渋滞コスト及び該ノードから退出する１つのリンクの渋滞コストに基づくエリア渋滞コストを設定する。
【００１５】
これによれば、探索経路上のエリア渋滞コストは、各ノードに進入する全てのリンクの渋滞コスト及び１方向に退出するリンクの渋滞コストに基づき設定される。その結果、請求項２に記載の発明と同様の作用効果を得ることができる。
【００１６】
また、本発明に係る自動車用ナビゲーションシステムは、請求項４の記載によれば、請求項１乃至３のいずれか一つに記載の発明において、
エリア渋滞コスト設定手段は、ノードに接続する複数のリンクの渋滞コストそれぞれに影響係数を乗算しそれらを総和した値を、該ノードのエリア渋滞コストとして設定する。
【００１７】
これによれば、探索経路上のエリア渋滞コストは、ノードに接続する複数のリンクの渋滞コストに影響係数でもって重み付けをして、この重み付けをした渋滞コストの総和を用いて算出される。従って、経路探索の精度がさらに向上し、その結果、請求項１乃至３のいずれか一つに記載の発明の作用効果をより一層向上できる。
【００１８】
また、本発明に係る自動車用ナビゲーションシステムは、請求項５の記載によれば、請求項１乃至４のいずれか一つに記載の発明において、
エリア渋滞コスト設定手段は、ノードに接続するリンクの他のノードに設定されたエリア渋滞コストを全て相加平均した値を、ノードの広域エリア渋滞コストとして設定し、
経路探索手段は、渋滞コスト、エリア渋滞コスト及び広域エリア渋滞コストに基づき、経路を探索する。
【００１９】
これによれば、渋滞コスト、エリア渋滞コストに加え、広域エリア渋滞コストを加味することで、より広い範囲の交通情報を考慮することとなる。従って、経路探索の精度がさらに向上し、その結果、請求項１乃至４のいずれか一つに記載の発明の作用効果をより一層向上できる。
【００２０】
また、本発明に係る自動車用ナビゲーションシステムは、請求項６の記載によれば、
自動車に設置するナビゲーション装置と、自動車とは別に設置される情報センター（８０）とを備え、
ナビゲーション装置は、
自動車の現在位置を検出する現在位置検出手段（１０）と、
目的地を入力操作する入力手段（２０、１００）と、
複数のリンク及びノードを有する地図データを記憶してなる記憶手段（４０）と、
経路探索手段（１６０）と、通信手段（５０）とを備え、
情報センターは、
交通情報システム（７０）より送信される交通情報を受信する通信部と、
地図データを記憶し、また、通信部の受信交通情報を記憶する情報記憶部（８２）と、
地図データの各リンクに対して、情報記憶部からの交通情報に基づき渋滞コスト（Ｂ）を設定する渋滞コスト設定手段（１１１、１３０）と、
地図データの各ノードに対して、該ノードに接続する複数のリンクの渋滞コストに基づくエリア渋滞コスト（Ｃｉｊｋ）を設定するエリア渋滞コスト設定手段（１４０）とを備え、
情報センターは、通信部により渋滞コスト及びエリア渋滞コストを送信し、
ナビゲーション装置では、通信手段は、通信部からの渋滞コスト及びエリア渋滞コストを受信し、
経路探索手段は、通信手段からの渋滞コスト及びエリア渋滞コストに基づき、現在位置から目的地までの経路を探索する。
【００２１】
これによれば、ナビゲーションシステムとは別に情報センターが設けられている。当該情報センターでは、請求項１乃至５のいずれか一つに記載のナビゲーションシステムから交通情報システムへの交通情報要求処理及び渋滞コストの設定処理及びエリア渋滞コストの算出処理が、情報センターでなされる。従って、ナビゲーションシステムの処理能力に余裕をもたせることができつつ、請求項１乃至５のいずれか一つに記載の発明と同様の作用効果を得ることができる。
【００２２】
また、本発明に係る自動車用ナビゲーション方法は、請求項７の記載によれば、
交通情報システム（７０）より送信される交通情報に基づき渋滞コスト（Ｂ）を設定し、
地図データの各ノードに対して、該ノードに接続する複数のリンクの渋滞コストに基づくエリア渋滞コスト（Ｃｉｊｋ）を設定し、
前記渋滞コスト及びエリア渋滞コストに基づき、自動車の現在位置から目的地までの経路を探索する。
【００２３】
これによれば、探索経路上の渋滞コストに対し、上述した従来技術における４状態の渋滞コストに加え、探索経路上の各交差点に接続する全リンクの渋滞コストを考慮したエリア渋滞コストを加味しているので、連続的に変化する実際の渋滞コストにより近づけるようにした当該経路のコストを算出するとともに、この渋滞コストに基づき案内経路を探索することができる。
【００２４】
なお、上記各手段の括弧内の符号は、後述する実施形態に記載の具体的手段との対応関係を示すものである。
【００２５】
【発明の実施の形態】
以下、本発明の各実施形態を図面により説明する。
（第１実施形態）
図１は、本発明が自動車用ナビゲーションシステムに適用される例を示している。当該ナビゲーションシステムは、現在位置検出装置１０を備えており、この現在位置検出装置１０は、ＧＰＳ受信装置であって、衛星航法システム（ＧＰＳともいう）の人工衛星から送信される電波を受信して、当該自動車の現在位置を現在時刻と共に検出する。
【００２６】
また、当該ナビゲーションシステムは、入力装置２０を備えており、この入力装置２０は、携帯用リモートコントローラであって、その操作により、必要な情報をマイクロコンピュータ３０（後述する）の受信部（図示しない）に送信により入力する。なお、リモートコントローラに代えて、出力装置６０の液晶パネル（後述する）にその表示面側から添着したタッチパネルを入力装置２０としてもよい。
【００２７】
また、当該ナビゲーションシステムは、マイクロコンピュータ３０、記憶装置４０、無線通信装置５０及び出力装置６０を備えている。マイクロコンピュータ３０は、上記受信部の他、ＣＰＵ、ＲＡＭ及びＲＯＭ等をバスラインで接続して構成されており、当該マイクロコンピュータ３０は、そのＣＰＵにより、図２及び図３にて示すフローチャートに従いコンピュータプログラムを実行する。
【００２８】
当該マイクロコンピュータ３０は、上記コンピュータプログラムの実行中において、現在位置検出装置１０の検出出力、入力装置２０の操作出力、記憶装置４０の出力、無線通信装置５０の出力や道路交通情報システム７０の出力に基づき、当該自動車の地図表示、リンクコストＡ、渋滞コストＢの設定、エリア渋滞コストの算出、案内経路探索や経路案内等の種々の処理を行う。
【００２９】
本実施形態において、上記受信部は、マイクロコンピュータ３０に内蔵のものに限らず当該マイクロコンピュータ３０に外付けしたものであってもよい。当該マイクロコンピュータ３０は、当該自動車のイグニッションスイッチを介しバッテリから給電されて作動して、上記コンピュータプログラムの実行を開始する。なお、上記コンピュータプログラムは、マイクロコンピュータ３０のＲＯＭに、当該マイクロコンピュータ３０により読み出し可能に予め書き込まれている。
【００３０】
記憶装置４０は、ハードディスクであって、この記憶装置４０には、一連の地図データ、交通情報データ、リンクコストデータ及び右左折コストデータがマイクロコンピュータ３０により読み出し可能にデータベースとして記憶されている。無線通信装置５０は、道路交通情報システム７０（以下、ＶＩＣＳ７０という）からの道路交通情報を受信してマイクロコンピュータ３０に出力する。なお、ＶＩＣＳ７０は、各種の渋滞情報を、交通情報として、送信するようになっている。
【００３１】
出力装置６０は、表示装置であって、マイクロコンピュータ３０による制御のもと、当該自動車において必要なデータを情報として表示する。なお、出力装置６０は、その液晶パネル等の表示パネルにて、当該自動車の車室内前壁に設けたインストルメントパネルに配設されている。
【００３２】
以上のように構成した本第１実施形態において、当該自動車が走行を開始したものとする。これに伴い、マイクロコンピュータ３０が、図２及び図３のフローチャートに従い、コンピュータプログラムの実行を開始する。現段階において入力装置２０による表示要求がなければ、図２のステップ１００においてＮＯとの判定が繰り返される。
【００３３】
このような状態において、入力装置２０による所望の地図の表示要求があれば、ステップ１００においてＹＥＳと判定される。然る後、ステップ１０１において、上記所望の地図を表す地図データ（以下、所望地図データともいう）の記憶装置４０からの読み出し処理がなされる。これに伴い、上記所望地図データが記憶装置４０のデータベースから読み出される。すると、ステップ１０２において、上記所望の地図の表示処理がなされる。このため、出力装置６０が、その表示パネルにて、上記所望の地図データに基づき所望の地図を表示する。
【００３４】
上述のように図２のステップ１０２での処理が終了すると、ステップ１１０において、目的地の選定の有無が判定される。現段階にて、入力装置２０の操作により目的地がマイクロコンピュータ３０に入力されていれば、目的地の選定ありとして、ステップ１１０での判定がＹＥＳとなる。
【００３５】
然る後、ステップ１１１において、ＶＩＣＳ７０に対する交通情報の要求処理がなされる。これに伴い、ステップ１２０でＮＯとの判定の繰り返し中に、無線通信装置５０が、ステップ１１０において、交通情報をＶＩＣＳ７０から受信し、マイクロコンピュータ３０に出力すると、交通情報ありとしてステップ１２０においてＹＥＳと判定される。然る後、図２のステップ１２１において、交通情報の記憶処理がなされる。これに伴い、交通情報が記憶装置４０にデータベースの一部として記憶される。
【００３６】
ついで、図３のステップ１３０において、各リンクにおけるリンクコストＡ及び渋滞コストＢの設定処理がなされる。例えば、図４にて示すごとく、各リンクには、それぞれリンクコストＡ及び進行方向を考慮した渋滞コストＢの設定処理がなされる。
【００３７】
これに伴い、各リンクコストＡは、記憶装置４０のデータベースから読み出されて設定され、進行方向を考慮した各渋滞コストＢは、記憶装置４０に入力されている交通情報から各リンク毎に読み出されて設定される。
【００３８】
例えば、図４にて示すごとく、当該自動車が交差点２から交差点５に向かって進行する場合のリンクコストＡは、Ａ＝１と設定され、当該自動車の進行方向の渋滞コストＢは、Ｂ＝２と設定される。
【００３９】
ついで、図３のステップ１４０において、各交差点毎にエリア渋滞コストＣｉｊｋの算出処理がなされる。これに伴い、例えば、各交差点におけるエリア渋滞コストＣｉｊｋは、次の数１の式により、それぞれ算出される。
【００４０】
【数１】
Ｃｉｊｋ＝Σ（Ｂ・Ｘ）＝Σ（Ｂ・Ｘｉｎ）＋Σ（Ｂ・Ｘｏｕｔ）
ここで、Ｃｉｊｋにおいて、サフィックスｉは当該交差点に進入するリンクが接続する他方の交差点の符号を示し、サフィックスｊは当該交差点の符号を示し、サフィックスｋは当該交差点から退出するリンクが接続する他方の交差点の符号を示す。例えば、図４にて示すごとく、交差点１（ｉ＝１）から交差点４（ｊ＝４）を通り交差点５（ｋ＝５）に向かう場合における交差点４のエリア渋滞コストＣｉｊｋは、Ｃ１４５となる。また、Ｘは、交差点に接続された各リンクにおける渋滞コストＢに対する影響係数を示しており、ＸｏｕｔとＸｉｎからなる。
【００４１】
ここで、影響係数Ｘｏｕｔ及びＸｉｎについて一例をあげて説明する。各リンクｂ〜ｅは、図５にて示すごとく、交差点ａに十字状に接続されているものとする。当該自動車は、矢印Ｙ（以下、進行方向Ｙという）で示すごとく、リンクｄから交差点ａを通りリンクｂへ進行するものとする。
【００４２】
このような前提のもと、影響係数Ｘｏｕｔとは、交差点ａから進行方向Ｙと同じ方向に退出するリンクｂでの渋滞コストＢに対する影響係数をいう。また、影響係数Ｘｉｎとは、交差点ａに進入するリンクｃ〜ｅでの渋滞コストＢに対する影響係数をいう。
【００４３】
次に、図４にて示すような、各交差点毎のエリア渋滞コストＣｉｊｋを影響係数Ｘｉｎ＝０．２５、影響係数Ｘｏｕｔ＝０．２５として、数１の式によりそれぞれ算出してみると、以下のようになる。
【００４４】
Ｃ１２３＝（０＋３＋０）×０．２５＋３×０．２５＝１．５
Ｃ１２５＝（３＋０＋３）×０．２５＋２×０．２５＝２
Ｃ１４５＝（０＋３＋２）×０．２５＋３×０．２５＝２
Ｃ２３６＝（０＋１＋３）×０．２５＋０×０．２５＝１
Ｃ２５６＝（２＋３＋３）×０．２５＋１×０．２５＝２．２５
Ｃ４５６＝（２＋３＋３）×０．２５＋１×０．２５＝２．２５
上述のようにステップ１４０（図３参照）において、各交差点毎のエリア渋滞コストＣｉｊｋが処理された後、ステップ１４１において、当該エリア渋滞コストＣｉｊｋの設定処理が図４にて示すごとくなされる。
【００４５】
ついで、広域エリア渋滞コスト（後述する）を考慮する要求がなければ、図３のステップ１５０においてＮＯと判定され、ステップ１６０において、現在位置から目的地までの案内経路探索処理がなされる。
【００４６】
この案内経路探索処理では、現在位置Ｓからある交差点までの経路において、当該経路上の各リンク毎のリンクコストＡ、渋滞コストＢ及び各交差点（現在位置Ｓと上記ある交差点を除く）毎のエリア渋滞コストＣｉｊｋ、右折コストＲ、左折コストＬの総和を当該経路のノードコストと定義する。このノードコストを用いた算出方法により、以下のように案内経路の探索がなされる。
【００４７】
現在位置Ｓに接続する各経路のノードコストが最小となる経路が探索される。ついで、探索された経路につながる交差点に接続してなる各リンクを通る各経路のノードコストが算出される。
【００４８】
算出後の各経路のノードコストを相互に比較し、最小のノードコストをもつ経路を決定する。その経路につながる交差点に接続してなる各リンクを通る各経路のノードコストが算出される。いずれかの経路が目的地Ｇに到達するまで各経路のノードコストの比較及び算出を繰り返す。
【００４９】
ある経路が最初に目的地Ｇに到達すると、その経路を暫定案内経路と定義し、その暫定案内経路のノードコストを暫定コストと定義する。暫定コストより大きなノードコストをもつ経路は、この時点で削除される。削除されなかった経路は、算出過程でのノードコストの加算により、暫定コストよりもその経路のノードコストが大きくなった時点で削除される。ノードコストが暫定コストを超えず目的地Ｇに到達した経路は、そのノードコストと暫定コストとを比較し、小さな方の経路を暫定案内経路とし、大きな方の経路は削除される。このようにして最後まで残った暫定案内経路が案内経路として探索される。
【００５０】
上述した案内経路の探索の仕方につき、図４を用いて例示的に説明する。
【００５１】
現在位置Ｓに接続する経路のノードコストが最小と判定された経路が交差点１から交差点４に接続する経路とする。交差点１から交差点４を介し交差点４につながる他の交差点に接続してなる各経路のノードコストは、交差点１から交差点４に接続する経路のノードコストに、交差点４につながる他の交差点に接続してなる各経路の各リンクコストＡ及び各渋滞コストＢを加算する。さらに、当該経路のノードコストは、その経路が交差点４を右折する場合には右折コストＲが、左折する場合には左折コストＬが加算され、その経路が交差点４を通過する方向を考慮した各エリア渋滞コストＣｉｊｋが加算される。
【００５２】
次の算出段階として、上述した交差点１から交差点４に接続する経路以外で交差点１につながる他の交差点に接続してなる各経路のノードコストと、上述した交差点４につながる他の交差点に接続してなる各経路のノードコストとを比較し、ノードコストが最小となる経路が判定される。
【００５３】
現段階において、ノードコストが最小となる経路が交差点１から交差点２に接続する経路とすると、次に交差点２につながる他の交差点に接続してなる各経路のノードコストが算出される。
【００５４】
次の算出段階として、交差点２につながる他の交差点に接続してなる各経路のノードコストと、交差点１から交差点４及び交差点２以外に接続する各経路のノードコストと、交差点４につながる他の交差点に接続してなる各経路のノードコストとを比較し、ノードコストが最小となる経路が判定される。
【００５５】
現段階において、ノードコストが最小となる経路が交差点４から交差点５に接続する経路とすると、次に交差点５につながる他の交差点に接続してなる各経路のノードコストが算出される。
【００５６】
ここで交差点５に接続する他の交差点に目的地Ｇが含まれているため、この時点で交差点１→交差点４→交差点５→交差点６という暫定案内経路が設定され、その暫定案内経路のノードコストが暫定コストとして設定される。
【００５７】
この時点で暫定コストよりも小さいノードコストをもつ経路が交差点１→交差点２→交差点３のみとすると、当該経路に関し、目的地Ｇに到達するか、もしくは、その経路のノードコストが暫定コストを超えるまで上述した算出を繰り返す。交差点１→交差点２→交差点３→交差点６のみが目的地Ｇに到達した場合、その経路におけるノードコストと暫定コストとを比較し、小さい方が案内経路として探索される。
【００５８】
上述のようにステップ１６０にて案内経路の探索がなされると、ステップ１７０において、暫定案内経路が一つに決まったかどうか判定される。
【００５９】
例えば、暫定案内経路が、図４にて示すごとく、一つに決定されれば、図３のステップ１７０においてＹＥＳと判定される。ついで、ステップ１７１にて、上述した暫定案内経路が案内経路として決定される。
【００６０】
また、上述したステップ１７０において、暫定案内経路が複数経路存在すればＮＯと判定され、ステップ１５１において、各交差点毎に広域エリア渋滞コストの算出がなされる。
【００６１】
ここで、広域エリア渋滞コストについて一例をあげて説明する。各リンクｆ〜ｈ及びｍは、図６にて示すごとく、黒点で示す交差点ｏに十字状に接続されており、交差点ｆ１〜ｈ１及びｍ１は、各リンクｆ〜ｈ及びｍに接続されているものとする。このような前提のもと、交差点ｏにおける広域エリア渋滞コストとは、交差点ｆ１〜ｈ１及びｍ１のエリア渋滞コストＣｉｊｋの相加平均値をいう。但し、交差点ｆ１〜ｈ１及びｍ１の各エリア渋滞コストＣｉｊｋが、その交差点において複数の異なる値を有する場合は、それらの値を相加平均した計算値がその交差点のエリア渋滞コストＣｉｊｋとみなされる。
【００６２】
ついで、ステップ１５２において、当該交差点の広域エリア渋滞コストが設定された後、ステップ１６０において、上述したノードコストにさらに広域エリア渋滞コストを加味したノードコストを用いた計算方法より案内経路探索処理がなされる。
【００６３】
また、上述した図３のステップ１５０においてＹＥＳと判定されると、ステップ１５１において、各交差点毎に広域エリア渋滞コストの算出がなされ、ステップ１５２において、広域エリア渋滞コストが設定された後、ステップ１６０において、上述したノードコストにさらに広域エリア渋滞コストを加味したノードコストを用いた計算方法より案内経路探索処理がなされる。
【００６４】
上述したようにステップ１７１にて決定された案内経路に基づき、ステップ１８０にて、経路案内処理のもとに当該乗員は当該自動車を目的地に向けて走行させる。
【００６５】
以上説明したように、本第１実施形態では、経路を探索する際、渋滞コストＢに加え、各交差点に接続する全リンクの渋滞コストＢを考慮したエリア渋滞コストＣｉｊｋを加味しているので、連続的に変化する実際の渋滞を考慮した経路を求めることができ、最適の経路案内を行うことができる。
【００６６】
また、渋滞コストＢ、エリア渋滞コストＣｉｊｋを使って最適経路を探索するので、例えば、交通情報が送信されないリンクがあっても、そのリンクの端点のノードに設定されたエリア渋滞コストを使って最適経路を探索することができる。
【００６７】
また、エリア渋滞コストＣｉｊｋとともに広域エリア渋滞コストを適用すれば、より広域の渋滞コストＢを加味することができるので、経路探索の精度がさらに向上し、より最適な経路案内を行うことができる。
（第２実施形態）
図７及び図８は、本発明の第２実施形態の要部を示している。この第２実施形態では、上記第１実施形態にて述べたフローチャートにおいて、図３のフローチャートを図７にて示すフローチャートに変更した構成となっている。その他の構成は、上記第１実施形態にて述べたものと同様の構成となっている。
【００６８】
このように構成された本第２実施形態において、図２のステップ１００からステップ１２１までの処理が終了した後、図７のステップ１３０ａにおいてリンクコストＡが設定される。一方、渋滞コストＢは、上記第１実施形態とは異なり、進入及び退出の方向に同一値を有するようにリンクに設定される。
【００６９】
ついで、ステップ１４０ａにおいて、各交差点毎にエリア渋滞コストＣｉｊｋの算出処理がなされる。エリア渋滞コストＣｉｊｋは、上記第１実施形態とは異なり、交差点に接続する全ての進入方向及び退出方向のリンクの渋滞コストＢが加味される（以下、進入方向及び退出方向をあわせて往復方向という）。
【００７０】
例えば、図８にて示すような、各交差点毎のエリア渋滞コストＣｉｊｋを影響係数Ｘｉｎ＝０．２、影響係数Ｘｏｕｔ＝０．２として、上述した数１の式によりそれぞれ算出してみると、以下のようになる。
【００７１】
2005055193.tif 000003
上述のようにステップ１４０ａ（図７参照）において、各交差点毎のエリア渋滞コストＣｉｊｋが処理された後、ステップ１４１ａにおいて、当該エリア渋滞コストＣｉｊｋの設定処理が図８にて示すごとくなされる。
【００７２】
ついで、広域エリア渋滞コストを考慮する要求がなければ、図７のステップ１５０においてＮＯと判定され、ステップ１６０において、現在位置から目的地までの案内経路探索処理がなされる。
【００７３】
ステップ１６０にて案内経路の探索がなされると、上記第１実施形態と同様の算出方法により暫定案内経路が探索され、ステップ１７０において、暫定案内経路が一つに決まったかどうか判定される。
【００７４】
例えば、暫定案内経路が、図８にて示すごとく、一つに決定されれば、図３のステップ１７０においてＹＥＳと判定される。ついで、ステップ１７１にて、上述した暫定案内経路が案内経路として決定される。
【００７５】
また、上述したステップ１７０において、暫定案内経路が複数経路存在すればＮＯと判定され、上記第１実施形態と同様に、ステップ１５１及びステップ１５２において、各交差点毎に広域エリア渋滞コストが設定された後、ステップ１６０において、案内経路探索処理がなされ、ステップ１７１にて、暫定案内経路が案内経路として決定される。
【００７６】
上述したようにステップ１７１にて決定された案内経路に基づき、ステップ１８０にて、経路案内処理のもとに当該乗員は当該自動車を目的地に向けて走行させる。
【００７７】
以上説明したように、本第２実施形態では、上記第１実施形態と異なり、渋滞コストＢは、進入及び退出の方向それぞれリンクに設定されており、エリア渋滞コストＣｉｊｋは、交差点に接続する全ての進入及び退出のリンクの渋滞コストＢより算出されている。従って、案内経路の探索は、これらの渋滞コストＢ及びエリア渋滞コストＣｉｊｋを加味することで探索されることとなり、上記第１実施形態と同様の作用効果を達成することできる。
（第３実施形態）
図９〜図１２は、本発明の第３実施形態を示している。この第３実施形態では、上記第１実施形態にて示したフローチャートにおいて、図２及び図３のフローチャートを図１０及び図１１にて示すフローチャートに変更した構成になっている。
【００７８】
本第３実施形態において、図９にて示すごとく、記憶装置４０は、地図データのみを有している。また、本第３実施形態において、情報センター８０を新たに採用しており、この情報センター８０は、無線通信装置５０とＶＩＣＳ７０との無線通信を行う。また、当該情報センター８０は、サーバ８１及び記憶装置８２により構成されている。
【００７９】
サーバ８１は、図１２にて示すフローチャートに従いサーバプログラムを実行する。当該サーバ８１は、上記サーバプログラムの実行中において、無線通信装置５０及びＶＩＣＳ７０との間で送受信処理をする。なお、上記サーバプログラムは、サーバ８１のＲＯＭに、当該サーバ８１により読み出し可能に予め書き込まれている。
【００８０】
記憶装置８２には、地図データ（図示しない）、ＶＩＣＳ７０からの交通情報データ、リンクコストデータ及び右左折コストデータが、データベースとして記憶される。その他の構成は、第１実施形態と同様である。
【００８１】
このように構成された本第３実施形態において、上記第１実施形態と同様に、目的地の選定ありとして、図１０のステップ１１０において、ＹＥＳと判定されると、ステップ１１２において、現在位置検出装置１０により検出された現在位置及び目的地の情報センター８０への送信処理がなされる。これに伴い、上記現在位置及び目的地のデータは、マイクロコンピュータ３０から無線通信装置５０を介し、情報センター８０へ送信される。
【００８２】
一方、情報センター８０では、サーバ８１が図１２のステップ１２０ａでＮＯとの判定を繰り返している。このような状態において、サーバ８１は、無線通信装置５０から現在位置及び目的地のデータを受信すると、ステップ１２０ａにおいて、ＹＥＳと判定される。
【００８３】
然る後、図１２のステップ１１１において、サーバ８１からＶＩＣＳ７０に対する交通情報の要求処理がなされる。これに伴い、ステップ１２０でＮＯとの判定の繰り返し中に、サーバ８１が、交通情報をＶＩＣＳ７０から受信すると、ステップ１２０においてＹＥＳと判定される。すると、ステップ１２１において、交通情報の記憶処理がなされる。これに伴い、交通情報が記憶装置８２にデータベースの一部として記憶される。
【００８４】
ついで、ステップ１３０において、各リンクにおけるリンクコストＡ及び進行方向を考慮した渋滞コストＢの設定処理がなされる。
【００８５】
これに伴い、各リンクコストＡは、記憶装置８２から読み出されて設定され、進行方向を考慮した各渋滞コストＢは、記憶装置８２に記憶されている交通情報から各リンク毎に読み出されて設定される。
【００８６】
ついでステップ１４０において、各交差点毎にエリア渋滞コストＣｉｊｋが算出される。エリア渋滞コストＣｉｊｋは、記憶装置８２に入力済のリンクコストＡ、渋滞コストＢ、影響係数Ｘｏｕｔ及びＸｉｎから上記第１実施形態と同様に数１の式を用いることにより算出される。然る後、ステップ１４１において、各交差点毎のエリア渋滞コストＣｉｊｋの設定処理がなされる。
【００８７】
ついで、広域エリア渋滞コストを考慮する要求がなければ、図１２のステップ１５０においてＮＯと判定され、ステップ１５３にて、コスト送信データ処理がなされる。これに伴い、コストデータが、サーバ８１から無線通信装置５０を介しマイクロコンピュータ３０へ送信される。
【００８８】
一方、マイクロコンピュータ３０では、図１０のステップ１１２での処理が終了すると、図１０のステップ１１３において、当該コストデータ受信の有無が判定される。現段階にて、当該コストデータがマイクロコンピュータ３０に入力されていれば、ステップ１１３においてＹＥＳと判定され、図１１のステップ１６０において、案内経路探索処理がなされる。
【００８９】
ステップ１６０にて案内経路の探索がなされると、上記第１実施形態と同様の算出方法により暫定案内経路が探索され、ステップ１７０において、暫定案内経路が一つに決まったかどうか判定される。暫定案内経路が一つに決定されれば、図１１のステップ１７０においてＹＥＳと判定され、ステップ１７１にて案内経路決定処理がなされ、上述した暫定案内経路を案内経路として決定する。その後、ステップ１７１にて決定された案内経路に基づきステップ１８０にて経路案内処理を開始する。
【００９０】
また、上述したステップ１７０において、暫定案内経路が複数経路存在すればＮＯと判定され、ステップ１９０において、案内経路決定不可情報送信処理がなされる。これに伴い、マイクロコンピュータ３０から無線通信装置５０を介しサーバ８１へ、案内経路が一つに決定されていないことを示す案内経路決定不可情報が送信される。
【００９１】
一方、サーバ８１では、図１２のステップ１５０ａにて、無線通信装置５０からの案内経路決定不可情報を受信すれば、ステップ１５１において、上述した第１実施形態における図３のステップ１５１と同様に、各交差点毎に広域エリア渋滞コストの算出がなされ、ついで、ステップ１５２において、各交差点毎に算出された広域エリア渋滞コストとして設定され、ステップ１５３にて、コスト送信データ処理がなされる。これに伴い、コストデータが、サーバ８１から無線通信装置５０を介しマイクロコンピュータ３０へ送信される。
【００９２】
また、上述した図１２のステップ１５０においてＹＥＳと判定されると、ステップ１５１において、上述したように、各交差点毎に広域エリア渋滞コストの算出がなされ、ステップ１５２において、広域エリア渋滞コストが設定された後、ステップ１５３にて、コスト送信データ処理がなされる。
【００９３】
上述のように、マイクロコンピュータ３０では、図１１のステップ１９０での処理が終了すると、ステップ１９０ａにおいて、当該広域エリアコストデータ受信の有無が判定される。現段階にて、無線通信装置５０からの出力により当該広域エリアコストデータがマイクロコンピュータ３０に入力されていれば、広域エリアコストデータありとして、ステップ１９０ａでの判定がＹＥＳとなり、ステップ１６０において、案内経路探索処理がなされる。
【００９４】
暫定案内経路が一つに決定されれば、図１１のステップ１７０においてＹＥＳと判定され、ステップ１７１にて案内経路決定処理がなされ、上述した暫定案内経路を案内経路として決定する。その後、ステップ１７１にて決定された案内経路に基づきステップ１８０にて経路案内処理を開始する。
【００９５】
以上説明したように、本第３実施形態では、上記第１実施形態にて述べた、ナビゲーションシステムに加え、情報センター８０が採用されている。当該情報センター８０では、上記第１実施形態においてナビゲーションシステムのマイクロコンピュータ３０でなされるＶＩＣＳ７０への交通情報要求処理及びコストデータの算出処理（図２のステップ１１１〜１２１及び図３のステップ１３０〜１５２参照）が、サーバ８１でなされる。従って、ナビゲーションシステムの処理能力に余裕をもたせつつ、上記第１実施形態と同様の作用効果を達成することできる。
【図面の簡単な説明】
【図１】本発明に係る自動車用ナビゲーションシステムの第１実施形態の概略構成図を示す。
【図２】図１のマイクロコンピュータにて実行されるコンピュータプログラムを表すフローチャートの一部である。
【図３】図１のマイクロコンピュータにて実行されるコンピュータプログラムを表すフローチャートの一部である。
【図４】上記第１実施形態において、探索経路における地図データ上のコストデータを表す図である。
【図５】上記第１実施形態において、探索経路上の進行方向を考慮した交差点のエリア渋滞コストを考慮する際のリンク接続図である。
【図６】上記第１実施形態において、広域エリア渋滞コストを定義するための図である。
【図７】本発明の第２実施形態において、マイクロコンピュータにて実行されるコンピュータプログラムを表すフローチャートの要部である。
【図８】上記第２実施形態において、探索経路における地図データ上のコストデータを表す図である。
【図９】本発明の第３実施形態の概略構成図である。
【図１０】図９のマイクロコンピュータにて実行されるコンピュータプログラムを表すフローチャートの一部である。
【図１１】図９のマイクロコンピュータにて実行されるコンピュータプログラムを表すフローチャートの一部である。
【図１２】図９のサーバにて実行されるサーバプログラムを表すフローチャートである。
【符号の説明】
Ｂ…渋滞コスト、Ｃｉｊｋ…エリア渋滞コスト、１０…現在位置検出装置、２０…入力装置、４０…記憶装置、５０…無線通信装置、７０…道路交通情報システム、８０…情報センター。
【図１】
2005055193.tif 000004
【図２】
2005055193.tif 000005
【図３】
2005055193.tif 000006
【図４】
2005055193.tif 000007
【図５】
2005055193.tif 000008
【図６】
2005055193.tif 000009
【図７】
2005055193.tif 000010
【図８】
2005055193.tif 000011
【図９】
2005055193.tif 000012
【図１０】
2005055193.tif 000013
【図１１】
2005055193.tif 000014
【図１２】
2005055193.tif 000015