(57)【特許請求の範囲】
【請求項１】
道路の車線数を含む道路網情報を記憶する情報記憶手段と、
渋滞が発生した渋滞道路を規定する渋滞情報を取得する情報取得手段と、
前記情報記憶手段に記憶された道路網情報及び、前記情報取得手段により取得された渋滞情報に従って、複数車線の渋滞道路を特定し、他の渋滞道路との配置関係により、複数車線の渋滞道路における車線単位の渋滞状況を判別する判別手段と、
前記判別手段により判別された車線単位の渋滞状況に従って、渋滞車線を回避する経路を前記情報記憶手段に記憶された道路網情報から探索する経路探索手段と、
を備えることを特徴とするナビゲーションシステム。
【請求項２】
道路網を構成する複数のリンク及びノードを規定し、少なくともリンクの車線数を管理するための道路網情報を記憶する情報記憶手段と、
道路上に発生した渋滞箇所を規定する渋滞情報を取得する情報取得手段と、
前記情報記憶手段に記憶された道路網情報及び、前記情報取得手段により取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する配置特定手段と、
前記配置特定手段により特定された配置関係に従って、複数車線のリンクにおいて渋滞が発生した車線を判別する車線判別手段と、
前記車線判別手段により判別された渋滞車線を回避する経路を前記情報記憶手段に記憶された道路網情報から探索する経路探索手段と、
を備えることを特徴とするナビゲーションシステム。
【請求項３】
道路網を構成する複数のリンク及びノードを規定し、少なくともリンクコスト及びリンクの車線数を管理するための道路網情報を記憶する情報記憶手段と、
道路上に発生した渋滞箇所を規定する渋滞情報を取得する情報取得手段と、
前記情報記憶手段に記憶された道路網情報及び、前記情報取得手段により取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する配置特定手段と、
前記配置特定手段により特定された配置関係に従って、渋滞の生じた複数車線のリンクのリンクコストに、進行方向に応じた異なる加重値を設定する加重値設定手段と、
前記加重値設定手段により加重値が設定されたリンクコストを含む道路網情報から自車が進むべき誘導経路を探索する経路探索手段と、
を備えることを特徴とするナビゲーションシステム。
【請求項４】
道路網を構成する複数のリンク及びノードを規定し、少なくともリンクの車線数を管理するための道路網情報を記憶する所定の記憶部から道路網情報を取得する道路網情報取得ステップと、
道路上に発生した渋滞箇所を規定する渋滞情報を取得する渋滞情報取得ステップと、
前記道路網情報取得ステップにて取得された道路網情報及び、前記渋滞情報取得ステップにて取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する配置特定ステップと、
前記配置特定ステップにて特定された配置関係に従って、複数車線のリンクにおいて渋滞が発生した車線を判別する車線判別ステップと、
前記車線判別ステップにて判別された渋滞車線を回避する経路を道路網情報から探索する経路探索ステップと、
を備えることを特徴とする経路探索方法。
【請求項５】
コンピュータに、道路網を構成する複数のリンク及びノードを規定し、少なくともリンクの車線数を管理するための道路網情報を記憶する所定の記憶部から道路網情報を取得する道路網情報取得ステップと、道路上に発生した渋滞箇所を規定する渋滞情報を取得する渋滞情報取得ステップと、前記道路網情報取得ステップにて取得された道路網情報及び、前記渋滞情報取得ステップにて取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する配置特定ステップと、前記配置特定ステップにて特定された配置関係に従って、複数車線のリンクにおいて渋滞が発生した車線を判別する車線判別ステップと、前記車線判別ステップにて判別された渋滞車線を回避する経路を道路網情報から探索する経路探索ステップとを実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、車線単位の渋滞を考慮して適切な経路を探索することのできるナビゲーションシステム、経路探索方法及びプログラムに関する。
【０００２】
【従来の技術】
従来のナビゲーションシステムは、例えば、ナビゲーションシステムを搭載した車両（以下、「自車」という。）の出発地から目的地までの誘導経路を所定の道路網情報から探索する。そして、自車の現在位置を所定のＧＰＳ（Global Positioning System）ユニット等により順次取得し、自車位置を示すシンボル及び誘導経路を地図画像に合成したナビゲーション画像（案内画像）を生成する。
ナビゲーションシステムは、このように生成したナビゲーション画像を所定の表示装置に表示しつつ、自車が誘導経路に沿って走行できるように、表示や音声にて逐次誘導する。
これにより、利用者は、表示されるナビゲーション画像や、出力される音声に従って自車を進めることにより、容易に目的地まで到達することができる。
【０００３】
近年では、渋滞情報や交通規制情報等を光・電波ビーコンやＦＭ多重放送により利用者に提供するＶＩＣＳ（Vehicle Information Communication System）が実用化されている。
このようなＶＩＣＳに対応した従来のナビゲーションシステムは、光・電波ビーコン受信ユニット等を介してＶＩＣＳ情報（渋滞情報）を取得すると、取得した渋滞情報に従って渋滞箇所を特定し、特定した渋滞箇所を示すシンボルをナビゲーション画像に合成して表示する。
また、取得した渋滞情報に従って、ナビゲーションシステムは、渋滞箇所を回避する誘導経路を探索する。すなわち、誘導経路を探索する際に、取得した渋滞情報を有効に活用することができる。
【０００４】
以下、渋滞情報を活用して誘導経路の探索を行う従来のナビゲーションシステムの動作について図６を参照して具体的に説明する。
なお、渋滞が発生していない状況において、図６（ａ）に示すように、ノード（交差点）Ｎ１、リンク（区間経路）Ｌ１、そして、ノードＮ２を通る誘導経路Ｙ１が最短距離（又は、最短時間等）のルートであるものとする。
【０００５】
まず、ナビゲーションシステムは、取得した渋滞情報に従って、図６（ｂ）に示すような渋滞箇所Ｊ１，Ｊ２を特定する。そして、これらの渋滞箇所Ｊ１，Ｊ２に対応するリンク（渋滞が発生しているリンク）を特定する。この場合、ナビゲーションシステムは、リンクＬ１，Ｌ２を特定する。
ナビゲーションシステムは、特定したリンクＬ１等を回避する誘導経路を探索する。この場合、ナビゲーションシステムは、図６（ｃ）に示すようなリンクＬ１を通らない誘導経路Ｙ２を探索する。
このように、ナビゲーションシステムは、取得した渋滞情報に従って、渋滞箇所を回避する誘導経路を探索することができる。
【０００６】
【発明が解決しようとする課題】
しかし、従来のナビゲーションシステムは、取得した渋滞情報を活用して誘導経路を探索しても、適切な誘導経路を探索できない場合があった。これは、渋滞箇所に対応するリンクが、複数車線（片側）であっても、１車線（片側）であっても、同一に扱ってしまうことに起因している。
例えば、上述の図６（ｂ）に示すリンクＬ１が、そもそも２車線（片側）であり、実際には、図６（ｄ）に示すように、右折車線（右側車線）にだけ渋滞箇所Ｊ１が発生しているような場合がある。
このような場合に、現実には、リンクＬ１からノードＮ２を直進する際に直進車線を走行するため、渋滞箇所Ｊ１の影響をほとんど受けることがない。すなわち、この場合、渋滞が発生していない状況である図６（ａ）と同様に、リンクＬ１を通る誘導経路Ｙ１の方が適切な経路となる。
【０００７】
しかしながら、従来のナビゲーションシステムは、このような場合でも、リンクＬ１全体に渋滞箇所Ｊ１が発生しているものとして扱うため、リンクＬ１からノードＮ２を直進する経路が探索されず、図６（ｃ）に示すような、リンクＬ１を回避する誘導経路Ｙ２を探索してしまう。
つまり、従来のナビゲーションシステムは、渋滞箇所に対応したリンクが複数車線である場合に、渋滞の判別を車線単位に行えないため、適切な経路を探索することができないという問題があった。
【０００８】
本発明は、上記実状に鑑みてなされたもので、車線単位の渋滞を考慮して適切な経路を探索することのできるナビゲーションシステム、経路探索方法及びプログラムを提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記目的を達成するため、本発明の第１の観点に係るナビゲーションシステムは、
道路の車線数を含む道路網情報を記憶する情報記憶手段と、
渋滞が発生した渋滞道路を規定する渋滞情報を取得する情報取得手段と、
前記情報記憶手段に記憶された道路網情報及び、前記情報取得手段により取得された渋滞情報に従って、複数車線の渋滞道路を特定し、他の渋滞道路との配置関係により、複数車線の渋滞道路における車線単位の渋滞状況を判別する判別手段と、
前記判別手段により判別された車線単位の渋滞状況に従って、渋滞車線を回避する経路を前記情報記憶手段に記憶された道路網情報から探索する経路探索手段と、
を備えることを特徴とする。
【００１０】
この発明によれば、情報記憶手段は、道路の車線数を含む道路網情報を記憶する。情報取得手段は、例えば、ＶＩＣＳを利用して、渋滞が発生した渋滞道路を規定する渋滞情報を取得する。判別手段は、情報記憶手段に記憶された道路網情報及び、情報取得手段により取得された渋滞情報に従って、複数車線の渋滞道路を特定し、他の渋滞道路との配置関係により、複数車線の渋滞道路における車線単位の渋滞状況を判別する。経路探索手段は、判別手段により判別された車線単位の渋滞状況に従って、渋滞車線を回避する経路を情報記憶手段に記憶された道路網情報から探索する。この結果、車線単位の渋滞を考慮して適切な経路を探索することができる。
【００１１】
上記目的を達成するため、本発明の第２の観点に係るナビゲーションシステムは、
道路網を構成する複数のリンク及びノードを規定し、少なくともリンクの車線数を管理するための道路網情報を記憶する情報記憶手段と、
道路上に発生した渋滞箇所を規定する渋滞情報を取得する情報取得手段と、
前記情報記憶手段に記憶された道路網情報及び、前記情報取得手段により取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する配置特定手段と、
前記配置特定手段により特定された配置関係に従って、複数車線のリンクにおいて渋滞が発生した車線を判別する車線判別手段と、
前記車線判別手段により判別された渋滞車線を回避する経路を前記情報記憶手段に記憶された道路網情報から探索する経路探索手段と、
を備えることを特徴とする。
【００１２】
この発明によれば、情報記憶手段は、道路網を構成する複数のリンク及びノードを規定し、少なくともリンクの車線数を管理するための道路網情報を記憶する。情報取得手段は、例えば、ＶＩＣＳを利用して、道路上に発生した渋滞箇所を規定する渋滞情報を取得する。配置特定手段は、情報記憶手段に記憶された道路網情報及び、情報取得手段により取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する。車線判別手段は、配置特定手段により特定された配置関係に従って、複数車線のリンクにおいて渋滞が発生した車線を判別する。経路探索手段は、車線判別手段により判別された渋滞車線を回避する経路を情報記憶手段に記憶された道路網情報から探索する。この結果、車線単位の渋滞を考慮して適切な経路を探索することができる。
【００１３】
上記目的を達成するため、本発明の第３の観点に係るナビゲーションシステムは、
道路網を構成する複数のリンク及びノードを規定し、少なくともリンクコスト及びリンクの車線数を管理するための道路網情報を記憶する情報記憶手段と、
道路上に発生した渋滞箇所を規定する渋滞情報を取得する情報取得手段と、
前記情報記憶手段に記憶された道路網情報及び、前記情報取得手段により取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する配置特定手段と、
前記配置特定手段により特定された配置関係に従って、渋滞の生じた複数車線のリンクのリンクコストに、進行方向に応じた異なる加重値を設定する加重値設定手段と、
前記加重値設定手段により加重値が設定されたリンクコストを含む道路網情報から自車が進むべき誘導経路を探索する経路探索手段と、
を備えることを特徴とする。
【００１４】
この発明によれば、情報記憶手段は、道路網を構成する複数のリンク及びノードを規定し、少なくともリンクコスト及びリンクの車線数を管理するための道路網情報を記憶する。情報取得手段は、例えば、ＶＩＣＳを利用して、道路上に発生した渋滞箇所を規定する渋滞情報を取得する。配置特定手段は、情報記憶手段に記憶された道路網情報及び、情報取得手段により取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する。加重値設定手段は、配置特定手段により特定された配置関係に従って、渋滞の生じた複数車線のリンクのリンクコストに、進行方向に応じた異なる加重値を設定する。経路探索手段は、加重値設定手段により加重値が設定されたリンクコストを含む道路網情報から自車が進むべき誘導経路を探索する。この結果、車線単位の渋滞を考慮して適切な経路を探索することができる。
【００１５】
上記目的を達成するため、本発明の第４の観点に係る経路探索方法は、
道路網を構成する複数のリンク及びノードを規定し、少なくともリンクの車線数を管理するための道路網情報を記憶する所定の記憶部から道路網情報を取得する道路網情報取得ステップと、
道路上に発生した渋滞箇所を規定する渋滞情報を取得する渋滞情報取得ステップと、
前記道路網情報取得ステップにて取得された道路網情報及び、前記渋滞情報取得ステップにて取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する配置特定ステップと、
前記配置特定ステップにて特定された配置関係に従って、複数車線のリンクにおいて渋滞が発生した車線を判別する車線判別ステップと、
前記車線判別ステップにて判別された渋滞車線を回避する経路を道路網情報から探索する経路探索ステップと、
を備えることを特徴とする。
【００１６】
この発明によれば、道路網情報取得ステップは、道路網を構成する複数のリンク及びノードを規定し、少なくともリンクの車線数を管理するための道路網情報を記憶する所定の記憶部から道路網情報を取得する。渋滞情報取得ステップは、例えば、ＶＩＣＳを利用して、道路上に発生した渋滞箇所を規定する渋滞情報を取得する。配置特定ステップは、道路網情報取得ステップにて取得された道路網情報及び、渋滞情報取得ステップにて取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する。車線判別ステップは、配置特定ステップにて特定された配置関係に従って、複数車線のリンクにおいて渋滞が発生した車線を判別する。経路探索ステップは、車線判別ステップにて判別された渋滞車線を回避する経路を道路網情報から探索する。この結果、車線単位の渋滞を考慮して適切な経路を探索することができる。
【００１７】
上記目的を達成するため、本発明の第５の観点に係るプログラムは、
コンピュータに、道路網を構成する複数のリンク及びノードを規定し、少なくともリンクの車線数を管理するための道路網情報を記憶する所定の記憶部から道路網情報を取得する道路網情報取得ステップと、道路上に発生した渋滞箇所を規定する渋滞情報を取得する渋滞情報取得ステップと、前記道路網情報取得ステップにて取得された道路網情報及び、前記渋滞情報取得ステップにて取得された渋滞情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係を特定する配置特定ステップと、前記配置特定ステップにて特定された配置関係に従って、複数車線のリンクにおいて渋滞が発生した車線を判別する車線判別ステップと、前記車線判別ステップにて判別された渋滞車線を回避する経路を道路網情報から探索する経路探索ステップとを実行させることを特徴とする。
【００１８】
【発明の実施の形態】
本発明の実施の形態にかかるナビゲーションシステムについて、以下図面を参照して説明する。
【００１９】
図１は、この発明の実施の形態に適用されるナビゲーションシステムの一例を示す模式図である。このシステムは、ＧＰＳアンテナ１と、ＧＰＳモジュール２と、ＶＩＣＳアンテナ３と、ＶＩＣＳモジュール４と、ＣＤ−ＲＯＭ５と、処理制御部６と、表示部７と、操作部８と、記憶部９とを備えて構成される。
【００２０】
ＧＰＳ（Global Positioning System）アンテナ１は、ヘリカル型アンテナ、誘電体アンテナ、パッチ型平面アンテナ等からなり、所定のＧＰＳ衛星が発信するスペクトラム拡散変調された衛星電波を受信する。
【００２１】
ＧＰＳモジュール２は、複数のＧＰＳ衛星から送信され、ＧＰＳアンテナ１が受信した衛星電波に同調し、各衛星電波をそれぞれ逆拡散復調して複数の衛星受信信号を取得する。ＧＰＳモジュール２は、取得したそれぞれの衛星受信信号に従って算出した各衛星電波の到達時間の差に基づいて、緯度、経度及び高度等からなる位置情報を生成する。
ＧＰＳモジュール２は、生成した位置情報を処理制御部６に順次供給する。
【００２２】
ＶＩＣＳ（Vehicle Information Communication System）アンテナ３は、所定のロッドアンテナ等からなり、沿道に設けられた所定のＶＩＣＳ情報送信装置から送られたＦＭ多重信号等を受信する。
【００２３】
ＶＩＣＳモジュール４は、ＶＩＣＳアンテナ３が受信したＦＭ多重信号等を復調することによりＶＩＣＳ情報（渋滞情報）を取得する。なお、ＶＩＣＳ情報は、例えば、渋滞種別、渋滞位置、及び、渋滞距離等の情報からなる。
なお、ＶＩＣＳモジュール４は、光・電波ビーコンにより送られたＶＩＣＳ情報を取得してもよい。
ＶＩＣＳモジュール４は、取得したＶＩＣＳ情報を処理制御部６に順次供給する。
【００２４】
ＣＤ−ＲＯＭ５は、表示用の地図情報を記憶すると共に、所定の道路網情報を記憶する。この道路網情報は、所定単位に区分された区間経路（リンク）を規定するリンク情報及び、交差点（ノード）を規定するノード情報等から構成される。
なお、リンク情報には、各リンクにおける車線数を規定する情報も含まれているものとする。
また、ＣＤ−ＲＯＭ５に記憶されるこれらの道路網情報等は、図示せぬ再生ユニットにより適宜読み出され、処理制御部６に供給される。
【００２５】
処理制御部６は、例えば、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、及びＣＰＵ（Central Processing Unit）を備えた１チップマイコン等からなり、ナビゲーションシステム全体を制御する。
なお、ＲＯＭには、後述する経路探索処理をＣＰＵに実行させるためのプログラムが予め記憶されている。また、ＲＡＭには、所定のワーク領域が確保される。つまり、処理制御部６は、ＲＯＭに記憶されているプログラムがＣＰＵにて実行されることにより、後述する経路探索処理を行うものとする。
【００２６】
具体的に処理制御部６は、ＶＩＣＳモジュール４から供給されるＶＩＣＳ情報を取得すると、渋滞に関する渋滞情報を抽出して記憶部９に記憶する。
そして、処理制御部６は、操作部８を介して利用者により指示された所定の出発地から目的地までの誘導経路をＣＤ−ＲＯＭ５等（道路網情報）から探索する。その際、記憶部９に記憶した渋滞情報及び、ＣＤ−ＲＯＭ５に記憶される道路網情報に従って、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係に従って、渋滞の生じた車線を判別する。そして、複数車線のリンクコストに、進行方向に応じた異なる加重値を設定し、車線単位の渋滞を考慮した誘導経路を探索する。
処理制御部６は、探索した誘導経路を地図画像に合成したナビゲーション画像を生成し、表示部７に表示する。
【００２７】
表示部７は、ＬＣＤ（Liquid Crystal Display）又はＣＲＴ（Cathode Ray Tube）等からなり、処理制御部６が生成したナビゲーション画像等を表示する。
【００２８】
操作部８は、例えば、複数の入力キー等からなり、利用者による入力操作に従って、種々の指示情報を処理制御部６に供給する。例えば、操作部８は、利用者の操作に従って、出発地及び目的地等を指し示す座標情報等を入力し、処理制御部６に供給する。
【００２９】
記憶部９は、ＲＡＭや磁気ディスク等の情報記憶デバイスからなり、ＶＩＣＳモジュール４が受信したＶＩＣＳ情報（渋滞情報）等を記憶する。
【００３０】
以下、この実施の形態に係るナビゲーションシステムの動作について図面を参照して説明する。図２は、処理制御部６が実行する経路探索処理を説明するためのフローチャートである。図２に示す経路探索処理は、例えば、操作部８を介して利用者から出発地及び目的地等が入力された後に、更に操作部８を介して入力された誘導経路の探索を指示する指示情報に応答して開始する。
【００３１】
まず、処理制御部６は、受信済みの渋滞情報に従って、渋滞箇所に対応するリンクを特定する（ステップＳ１１）。すなわち、処理制御部６は、記憶部９に格納された渋滞情報に従って、渋滞が発生している区間経路を特定する。
【００３２】
処理制御部６は、特定したリンクが複数車線（片側）であるか否かを判別する（ステップＳ１２）。すなわち、処理制御部６は、ＣＤ−ＲＯＭ５の道路網情報に含まれる車線数を規定する情報に従って、特定したリンクが片側複数車線であるか否かを判別する。
【００３３】
処理制御部６は、複数車線でない（１車線である）と判別すると、後述するステップＳ１５に処理を進める。一方、複数車線であると判別した場合に、処理制御部６は、この複数車線のリンクとノードを介して接する渋滞リンクの有無を記憶部９の渋滞情報からサーチする（ステップＳ１３）。すなわち、処理制御部６は、渋滞が発生している複数車線のリンクと進行先の交差点等を介して接する何れかのリンクに渋滞箇所が発生しているかを渋滞情報からサーチする。
【００３４】
処理制御部６は、サーチにより渋滞リンクが存在するか否かを判別する（ステップＳ１４）。
なお、ノードを介して直接に接していなくとも、ノードを介した延長線上の所定距離内（他のリンクを介して接する場合等）に渋滞リンクがある場合に、ノードを介して接する渋滞リンクが存在するものと判別してもよい。
【００３５】
処理制御部６は、渋滞リンクが存在しないと判別した場合（また、ステップＳ１２にて片側１車線であると判別した場合）に、リンクコストに渋滞用の規定値となる加重値を設定する（ステップＳ１５）。すなわち、処理制御部６は、経路探索に使用されるリンクコストの加重値に、渋滞時に適用される規定値をセットする。
【００３６】
一方、渋滞リンクがサーチできたと判別した場合に、処理制御部６は、両リンクの配置関係を判別し、複数車線のリンクコストに、進行方向に応じた異なる加重値を設定する（ステップＳ１６）。
すなわち、処理制御部６は、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係に従って、渋滞の生じた車線を判別する。そして、判別した渋滞車線を通る進行方向及び、渋滞車線を通らない進行方向に応じて、複数車線のリンクコストに異なる加重値を設定する。
【００３７】
具体的に説明すると、図３（ａ）に示すように、複数車線（３車線）であるリンクＬ１に渋滞箇所Ｊ１が発生しており、ノードＮを介して右折方向に接する１車線であるリンクＬ２に渋滞箇所Ｊ２が発生している場合に、処理制御部６は、図３（ｂ）に示すように、リンクＬ１の右折車線に渋滞箇所Ｊ１が発生していると判別する。
この場合、処理制御部６は、リンクＬ１からノードＮを右折する方向（右折方向）のリンクコストに大きな加重値（例えば、１車線の渋滞時と同様に規定値の１００％）を設定する。一方、直進方向や左折方向のリンクコストに小さな加重値（例えば、渋滞の規定値の１０％）を設定する。
【００３８】
また、図３（ｃ）に示すように、複数車線であるリンクＬ１に渋滞箇所Ｊ１が発生しており、ノードＮを介して左折方向に接する１車線であるリンクＬ３に渋滞箇所Ｊ３が発生している場合に、処理制御部６は、図３（ｄ）に示すように、リンクＬ１の左折（及び直線）車線に渋滞箇所Ｊ１が発生していると判別する。この場合、処理制御部６は、左折方向のリンクコストに大きな加重値（例えば、渋滞の規定値の１００％）を設定する。一方、右折方向のリンクコストに小さな加重値（例えば、渋滞の規定値の１０％）を設定し、直進方向のリンクコストに左折車線の影響を考慮して中くらいの加重値（例えば、渋滞の規定値の４０％）を設定する。
【００３９】
そして、図３（ｅ）に示すように、複数車線であるリンクＬ１に渋滞箇所Ｊ１が発生しており、ノードＮを介して直進方向に接するリンクＬ４に渋滞箇所Ｊ４が発生している場合に、処理制御部６は、図３（ｆ）に示すように、リンクＬ１の直線車線に渋滞箇所Ｊ１が発生していると判別する。
この場合、処理制御部６は、直進方向のリンクコストに大きな加重値（例えば、渋滞の規定値の１００％）を設定する。一方、右折方向のリンクコストに小さな加重値（例えば、渋滞の規定値の１０％）を設定し、左折方向のリンクコストに直進車線の影響を考慮して中くらいの加重値（例えば、渋滞の規定値の５０％）を設定する。
【００４０】
図２に戻って、処理制御部６は、設定したリンクコストを使用して誘導経路を探索する（ステップＳ１７）。すなわち、処理制御部６は、ステップＳ１６等にて加重値が設定されたリンクコストを含む道路網情報から自車が進むべき誘導経路を探索する。
例えば、上述のステップＳ１１にて、図４（ａ）に示すような渋滞箇所Ｊ１，Ｊ２に対応するリンクＬ１（複数車線），Ｌ２が特定され、ステップＳ１６にて、右折車線に渋滞箇所Ｊ１が発生したと判別されて、リンクＬ１のリンクコストに、進行方向に応じた異なる加重値が設定されたものとする。
この場合、処理制御部６は、図４（ｃ）に示すように、ノードＮ１、リンクＬ１、そして、ノードＮ２を通る誘導経路Ｙ１を探索する。すなわち、リンクＬ１からノードＮ２を直進する直進方向のリンクコストに小さな加重値（例えば、渋滞の規定値の１０％）が設定されているため、リンクＬ１を迂回する他の経路のリンクコストより小さくなり、結果として、現実に沿った適切な誘導経路Ｙ１が検索される。
【００４１】
このように、経路探索処理によって、渋滞が発生した複数車線のリンクと渋滞が発生した他のリンクとのノードを介した配置関係から、複数車線のリンクにおいて渋滞が発生した車線が判別される。そして、渋滞の生じた複数車線のリンクコストに、進行方向に応じた異なる加重値が設定される。
この結果、車線単位の渋滞を考慮して適切な経路を探索することができる。
【００４２】
上記の実施の形態では、最初に目的地等までの誘導経路を探索する場合について説明したが、探索した誘導経路に従って自車を案内中に、新たな渋滞情報を取得することにより、迂回経路等を再探索する際にも適宜適用可能である。
例えば、処理制御部６は、誘導経路上に新たに発生した渋滞箇所を特定すると、特定した渋滞箇所に対応するリンクが複数車線であるか否かを判別する。そして、複数車線であると判別した場合に、処理制御部６は、他の渋滞リンクとのノードを介した配置関係から、複数車線のリンクにおいて渋滞が発生した車線を判別する。そして、渋滞の生じた複数車線のリンクコストに、進行方向に応じた異なる加重値を設定した後に、迂回経路等を再探索する。
この場合も、車線単位の渋滞を考慮して適切な経路を探索することができる。
【００４３】
上記の実施の形態では、リンクにおける車線数が固定とした場合について説明したが、リンクにおける現実の車線数の増減を考慮して、リンクコストの加重値等を設定してもよい。
例えば、図５に示すように、ノード（交差点）の手前の距離ｄからリンクの車線が増加している場合に、リンク上の渋滞箇所の距離と、この距離ｄとの関係から、リンクコストの加重値を可変的に設定してもよい。
【００４４】
なお、この発明の実施の形態にかかるナビゲーションシステムは、専用のシステムによらず、通常のコンピュータシステムを用いて実現可能である。例えば、ＧＰＳ受信機能を備えたコンピュータに上述のいずれかを実行するためのプログラムを格納した媒体（フロッピーディスク、ＣＤ−ＲＯＭ等）から当該プログラムをインストールすることにより、上述の処理を実行するナビゲーションシステムを構成することができる。
【００４５】
また、コンピュータにプログラムを供給するための手法は、任意である。例えば、通信回線、通信ネットワーク、通信システム等を介して供給してもよい。一例を挙げると、通信ネットワークの掲示板（ＢＢＳ）に当該プログラムを掲示し、これをネットワークを介して搬送波に重畳して配信する。
そして、このプログラムを起動し、ＯＳの制御下で、他のアプリケーションプログラムと同様に実行することにより、上述の処理を実行することができる。
【００４６】
【発明の効果】
以上説明したように、本発明によれば、車線単位の渋滞を考慮して適切な経路を探索することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係るナビゲーションシステムの構成の一例を示すブロック図である。
【図２】本発明の実施の形態に係る経路探索処理を説明するためのフローチャートである。
【図３】複数車線における渋滞を説明するための模式図であり、（ａ），（ｂ）が右折車線の渋滞を示す図であり、（ｃ），（ｄ）が左折車線の渋滞を示す図であり、（ｅ），（ｆ）が直進車線の渋滞を示す図である。
【図４】（ａ）〜（ｃ）共に、複数車線における渋滞車線が判別され、誘導経路が探索される様子を説明するための模式図である。
【図５】ノード手前で車線が増加するリンクの一例を説明する模式図である。
【図６】（ａ）〜（ｄ）共に、従来のナビゲーションシステムにおいて、誘導経路が探索される様子等を説明するための模式図である。
【符号の説明】
１  ＧＰＳアンテナ
２  ＧＰＳモジュール
３  ＶＩＣＳアンテナ
４  ＶＩＣＳモジュール
５  ＣＤ−ＲＯＭ
６  処理制御部
７  表示部
８  操作部
９  記憶部
【図１】
0003751207.tif 000002
【図２】
0003751207.tif 000003
【図３】
0003751207.tif 000004
【図４】
0003751207.tif 000005
【図５】
0003751207.tif 000006
【図６】
0003751207.tif 000007