(57)【要約】      （修正有）【課題】道路地図上の出発地から目的地までの経路探索の高速化を図ることができる経路案内方法を提供する。【解決手段】道路地図上の出発地から目的地までの経路を案内する経路案内方法であって、経路案内装置が、道路地図を区分した複数のセル内の交通容量に依存する通過容易性に基づいて、複数のセルを対象として、出発地の属するセルから目的地の属するセルまでを結ぶセルで構成されたメッシュルートを探索するステップＳ４１，Ｓ４２と、経路案内装置が、探索されたメッシュルート内の道路リンクを対象として、出発地から目的地までを結ぶ道路リンクで構成された経路を探索するステップＳ４３，Ｓ４４とを含む。【選択図】図１２
2017219415.tif 000002
【特許請求の範囲】
【請求項１】
道路地図上の出発地から目的地までの経路を案内する経路案内方法であって、
経路案内装置が、前記道路地図をメッシュ状に区分した複数のセル内の交通容量に依存する通過容易性に基づいて、前記複数のセルを対象として、前記出発地の属する前記セルから前記目的地の属する前記セルまでを結ぶ前記セルで構成されたメッシュルートを探索するステップと、
前記経路案内装置が、前記探索されたメッシュルート内の道路リンクを対象として、前記出発地から前記目的地までを結ぶ前記道路リンクで構成された経路を探索するステップ
とを含むことを特徴とする経路案内方法。
【請求項２】
前記メッシュルートを探索するステップは、隣接する前記セル間の交通容量に依存する通過容易性に更に基づいて前記メッシュルートを探索することを特徴とする請求項１に記載の経路案内方法。
【請求項３】
前記メッシュルートを探索するステップは、前記出発地から前記目的地までの距離が近いほど、前記複数のセルのサイズを小さく設定することを特徴とする請求項１又は２に記載の経路案内方法。
【請求項４】
前記メッシュルートを探索するステップは、前記メッシュルートを探索した後に、前記１次メッシュルート内を前記セルよりも細かくメッシュ状に区分した複数の２次セル毎の通過容易性に基づいて、前記複数の２次セルを対象として、前記出発地の属する前記２次セルから前記目的地の属する前記２次セルまでを結ぶ前記２次セルで構成された２次メッシュルートを探索することを特徴とする請求項１〜３のいずれか１項に記載の経路案内方法。
【請求項５】
前記メッシュルートを探索するステップは、前記道路地図上の前記道路リンクの密度が相対的に高い領域に対応する前記セルが、前記道路リンクの密度が相対的に低い領域に対応する前記セルよりも小さくなるように前記セルのサイズを異ならせることを特徴とする請求項１〜３のいずれか１項に記載の経路案内方法。
【請求項６】
道路地図上の出発地から目的地までの経路を案内する経路案内システムであって、
前記道路地図をメッシュ状に区分した複数のセルで構成されるメッシュマップを記憶するメモリと、
前記メモリから前記メッシュマップを読み出して、前記複数のセル内の通過容易性に基づいて、前記複数のセルを対象として、前記出発地の属する前記セルから前記目的地の属する前記セルまでを結ぶ前記セルで構成されたメッシュルートを探索し、前記探索されたメッシュルート内の道路リンクを対象として、前記出発地から前記目的地までを結ぶ前記道路リンクで構成された経路を探索するマイクロコンピュータ
とを備えることを特徴とする経路案内システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路案内方法及び経路案内システムに関する。
【背景技術】
【０００２】
従来、渋滞や混雑を回避するように出発地から目的地までの最適経路を探索する車両経路誘導装置が提案されている（特許文献１参照）。特許文献１に記載の車両経路誘導装置は、道路地図をメッシュ状に分割した領域毎に、交通情報提供の対象となる総リンク数に対する渋滞発生リンク数の比率を算出し、算出した比率に応じて領域内における交通情報の対象外道路のリンクコストを修正する。その後、出発地から目的地までの経路を最小コストとなるように探索する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１０−３８５９７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に記載された車両経路誘導装置では、対象外道路のリンクコストの修正後に行う経路探索を、道路地図上の道路リンクを対象として行うため、探索には一定時間を要するという課題がある。
【０００５】
上記課題に鑑み、本発明は、道路地図上の出発地から目的地までの経路探索の高速化を図ることができる経路案内方法及び経路案内システムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一態様によれば、道路地図上の出発地から目的地までの経路を案内するときに、道路地図をメッシュ状に区分した複数のセル内の交通容量に依存する通過容易性に基づいて、複数のセルを対象として、出発地の属するセルから目的地の属するセルまでを結ぶセルで構成されたメッシュルートを探索する。そして、探索されたメッシュルート内の道路リンクを対象として、出発地から目的地までを結ぶ道路リンクで構成された経路を探索することを特徴とする経路案内方法及び経路案内システムが提供される。
【発明の効果】
【０００７】
本発明によれば、道路地図上の出発地から目的地までの経路探索の高速化を図ることができる経路案内方法及び経路案内システムを提供することができる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態に係る経路案内システムの一例を示すブロック図である。
【図２】本発明の実施形態に係る道路リンクマップを複数のセルで区分した一例を示す概略図である。
【図３】本発明の実施形態に係るメッシュマップの一例を示す概略図である。
【図４】本発明の実施形態に係る通過コストの変更処理の一例を示す概略図である。
【図５】本発明の実施形態に係る通過コストの変更処理の一例を示す概略図である。
【図６】本発明の実施形態に係る通過コストの変更処理の一例を示す概略図である。
【図７】図７Ａ〜図７Ｄは、本発明の実施形態に係る経路探索処理の一例を順次示す概略図である。
【図８】図８Ａ及び図８Ｂは、本発明の実施形態に係る経路案内画面の一例をそれぞれ示す概略図である。
【図９】本発明の実施形態に係る経路案内方法の一例を示すフローチャートである。
【図１０】本発明の実施形態に係るメッシュマップ作成処理の一例を示すフローチャートである。
【図１１】本発明の実施形態に係るセルに混雑度に応じた通過コストの変更処理の一例を示すフローチャートである。
【図１２】本発明の実施形態に係るメッシュルートの探索処理の一例を示すフローチャートである。
【図１３】図１３Ａは、第１の変形例に係るセル境界距離当たりの道路リンク本数と係数との関係を示すグラフであり、図１３Ｂは、第２の変形例に係るセル内の道路リンク密度と係数との関係を示すグラフであり、図１３Ｃは、第３の変形例に係るセル内の混雑度の空間的偏りの大きさと、混雑度の偏りの係数との関係を示すグラフである。
【図１４】図１４Ａ及び図１４Ｂは、第４の変形例に係る互いにメッシュサイズの異なるメッシュマップの一例を示す概略図である。
【図１５】第５の変形例に係るメッシュマップの一例を示す概略図である。
【図１６】図１６Ａ〜図１６Ｄは、第６の変形例に係るメッシュルートの探索処理の一例を順次示す概略図である。
【発明を実施するための形態】
【０００９】
以下において、図面を参照して、本発明の実施形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を貼付している。但し、図面は模式的なものであり、厚みと平面寸法との関係、厚みの比率等は現実のものとは異なることに留意すべきである。また、図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることは勿論である。また、以下に示す実施形態は、本発明の技術的思想を具体化するための装置や方法を例示するものであって、本発明の技術的思想は、構成部品の材質、形状、構造、配置等を下記のものに特定するものではない。本発明の技術的思想は、特許請求の範囲に記載された請求項が規定する技術的範囲内において、種々の変更を加えることができる。
【００１０】
＜経路案内システムの構成＞
本発明の実施形態に係る経路案内システムは、図１に示すように、交通管理センター１、交通情報収集装置２及び車両Ｖ１，Ｖ２，Ｖ３，…，Ｖｎ（ｎは４以上の正の整数である。）で構成されている。なお、車両Ｖ１〜Ｖｎの台数は特に限定されるものではない。交通情報収集装置２は、例えば道路上に設置された車両感知器であり、単位時間当たりに道路を通過した車両台数等の道路交通情報を収集する。交通情報収集装置２は、収集した道路交通情報を交通管理センター１及び車両Ｖ１〜Ｖｎに送信する。
【００１１】
車両Ｖ１は、車両側通信装置１０、車載装置１１、地図情報記憶装置１２及び表示装置１３を搭載している。車両側通信装置１０、車載装置１１、地図情報記憶装置１２及び表示装置１３は、例えばナビゲーション装置等で構成することができる。車両側通信装置１０は、交通情報収集装置２から道路交通情報を受信するとともに、交通管理センター１に対して各種情報を送受信する。地図情報記憶装置１２は、半導体記憶装置、磁気記憶装置又は光学記憶装置等のメモリであり、道路地図情報を記憶する。
【００１２】
車載装置１１は、例えば中央演算処理装置（ＣＰＵ）や記憶装置（レジスタ、キャッシュメモリ、主記憶装置）等を含むマイクロコンピュータやマイクロコンピュータに等価なプロセッサ等で構成することができる。車載装置１１は、目的地設定部２１、車両情報取得部２２及び表示制御部２３を備える。目的地設定部２１は、乗員の入力情報等に基づいて、地図情報記憶装置１２に記憶された道路地図上に車両Ｖ１の目的地を設定する。乗員の入力情報は、例えば表示装置１３のタッチパネルや車室内のスイッチ等のユーザインターフェースを介して入力される。目的地設定部２１により設定された目的地の情報は、車両側通信装置１０を介して交通管理センター１に送信される。
【００１３】
車両情報取得部２２は、車両Ｖ１の現在位置及び車両Ｖ１の走行状態を含む車両情報を取得する。車両Ｖ１の現在位置は、例えば全地球測位システム（ＧＰＳ）等から取得可能である。車両Ｖ１の走行状態は例えば車速であり、車両Ｖ１に取り付けた車速センサにより検出可能である。車両情報取得部２２により取得した車両情報は、車両側通信装置１０を介して交通管理センター１に送信される。なお、車両情報取得部２２は、乗員の入力情報等に基づいて、地図情報記憶装置１２に記憶された道路地図上に車両Ｖ１の現在地とは異なる位置に出発地を設定し、設定された出発地を車両情報に含めてもよい。
【００１４】
表示制御部２３は、交通管理センター１から車両側通信装置１０を介して受信した経路案内情報に基づいて、車両Ｖ１の現在位置等の出発地から目的地までの推奨経路等を表示するように表示装置１３を制御する。表示装置１３としては、例えばディスプレイ等の出力装置が使用可能である。なお、表示装置１３の代わりに、図示を省略した音声出力装置を用いて、音声により推奨経路等を乗員に対して提示してもよい。なお、他の車両Ｖ２〜Ｖｎも、車両Ｖ１と同様の構成を有するものとする。
【００１５】
交通管理センター１は、センター側通信装置３０、経路案内装置３１、地図情報記憶装置３２及びメッシュマップ作成装置３４を備える。なお、交通管理センター１は、メッシュマップ作成装置３４を有していなくても構わない。センター側通信装置３０は、交通情報収集装置２から道路交通情報を受信するとともに、車両Ｖ１〜Ｖｎに対して各種情報を送受信する。
【００１６】
地図情報記憶装置３２は、半導体記憶装置、磁気記憶装置又は光学記憶装置等のメモリであり、道路リンクマップ記憶部５１及びメッシュマップ記憶部５２を有する。道路リンクマップ記憶部５１は、道路地図上の道路リンクの接続関係を示す道路リンクマップを記憶している。道路リンクは、道路地図を交差点等の結節点（ノード）間で区切った道路区間である。道路リンクマップは、道路リンク毎に、道路地図上の位置座標、道路規格、リンク長、車線幅、車線数及び工事状況等の属性情報を含む。
【００１７】
メッシュマップ記憶部５２は、道路リンクマップをメッシュ状に複数のセルに区分し、道路リンクマップをメッシュ単位（セル単位）で管理するメッシュマップを記憶している。メッシュマップは、メッシュマップ記憶部５２に予め記憶されている場合を例示するが、メッシュマップ作成装置３４が経路探索時に作成することもできる。
【００１８】
図２は、道路リンクマップ記憶部５１に記憶されている道路リンクマップを、メッシュマップ記憶部５２に記憶されているメッシュマップが管理する複数のセルＡｉｊ（ｉ＝１〜ｎ；ｊ＝１〜ｍ：ｎ，ｍは２以上の正の整数である。図２〜図６ではｎ＝ｍ＝４の場合を例示する。）で区分した一例を示す。メッシュマップには、道路リンクマップを構成する複数の道路リンクＲ０と、複数のセルＡｉｊとの接続関係が記述されている。
【００１９】
図３は、メッシュマップの基本的な構成を模式的に示す。メッシュマップにより管理される各セルＡｉｊの中心には白丸で示すメッシュノードＮｉｊ（ｉ＝１〜ｎ；ｊ＝１〜ｍ：ｎ，ｍは２以上の正の整数である。図３、図４、図６ではｎ＝ｍ＝４の場合を例示する。）が設定されている。各メッシュノードＮｉｊ間は、線分で示すメッシュリンクＬで接続されている。
【００２０】
メッシュリンクＬは、隣接するセルＡｉｊ間の道路リンクの接続関係を表す。隣接するセルＡｉｊ間を跨ぐ道路リンクが有る場合には、その領接続関係が有ると定義して、メッシュリンクＬが設定されている。一方、隣接するセルＡｉｊ間を跨ぐ道路リンクが無い場合には、そのセルＡｉｊ間には接続関係が無いと定義して、メッシュリンクＬは設定されていない。図３に示すメッシュリンクＬは、図２に示した道路リンクマップを構成する道路リンクＲ０に対応している。例えば、図２に示したセルＡ１１には、隣接するセルＡ１２，Ａ２１と間を跨ぐ道路リンクＲ０が無いので、図３に示すようにメッシュノードＮ１１と、隣接するメッシュノードＮ１２，Ｎ２１との間にはメッシュリンクＬが設定されていない。
【００２１】
更に、メッシュリンクＬには、隣接するセルＡｉｊ間の通過コスト（以下、「セル間コスト」という。）が付与されている。セル間コストは、隣接するセルＡｉｊ間の交通容量に依存する通過容易性の度合いを数値化したものである。セルＡｉｊ間の交通容量に依存する通過容易性は、セルＡｉｊ間を移動するときの車両の通過しやすさを表す指標であり、セルＡｉｊ間を跨ぐ道路リンクの車線数、車線幅等を考慮して規定することができる。セルＡｉｊ間の通過容易性が高いほど、セルＡｉｊ間を通過しやすいことを意味しており、セル間コストは小さく設定される。逆に、セルＡｉｊ間の通過容易性が低いほど、セルＡｉｊ間を通過しにくいことを意味しており、セル間コストが大きく設定される。例えば、隣接するセルＡｉｊ間を跨ぐ道路リンクの交通容量の合計値が大きいほど、セルＡｉｊ間の通過容易性が高く規定され、セル間コストが小さく設定される。なお、道路リンクの交通容量は、道路リンクの幾何形状、道路属性等に基づいて求めることができる。
【００２２】
図３では直感的に理解しやすいように、セル間コストに対応してメッシュリンクＬの太さを変化させて示している。即ち、メッシュリンクＬが太いほど、そのメッシュリンクＬに付与されたセル間コストが小さいことを示している。例えば、図２に示したセルＡ３１と、その右側に隣接するセルＡ３２と間を跨ぐ道路リンクＲ０が３本と相対的に多いので、図３に示したメッシュノードＮ３１，Ｎ３２間のメッシュリンクＬが相対的に太く設定されている。一方、図２に示したセルＡ１４と、その左側及び下側に隣接するセルＡ１３，Ａ２４と間を跨ぐ道路リンクＲ０が１本と相対的に少ないので、図３に示したメッシュノードＮ１３，Ｎ１４の間及びメッシュノードＮ１４，Ｎ２４の間のメッシュリンクＬが相対的に細く設定されている。
【００２３】
また、メッシュノードＮｉｊは、セルＡｉｊに属する道路リンクの接続関係を示す。図３では、メッシュノードＮｉｊは全てのセルＡｉｊに設定されている場合を例示しているが、セルＡｉｊに属する道路リンクが有る場合には接続関係が有ると定義して、そのセルＡｉｊにメッシュノードＮｉｊが設定される。一方、セルＡｉｊに属する道路リンクが無い場合には接続関係が無いと定義して、そのセルＡｉｊにはメッシュノードＮｉｊが設定されない。図４に示すメッシュノードＮｉｊは、図２に示した道路リンクマップを構成する道路リンクＲ０に対応している。例えば、図２に示したセルＡ１１に属する道路リンクＲ０が無いので、図４に示すようにセルＡ１１にはメッシュノードが設定されていない。
【００２４】
メッシュノードＮｉｊには、セルＡｉｊ内の通過コスト（以下、「セル内コスト」という。）が付与されている。セル内コストは、セルＡｉｊ内の交通容量に依存する通過容易性の度合いを数値化したものである。セルＡｉｊ内の交通容量に依存する通過容易性は、セルＡｉｊ内の車両の通り易さを表す指標であり、セルＡｉｊ内の渋滞の頻度、車線数、車線幅、工事状況等を考慮して規定することができる。セルＡｉｊ内の通過容易性が高いほど、セルＡｉｊ内を通過しやすいことを意味しており、セル内コストは小さく設定される。逆に、セルＡｉｊ内の通過容易性が低いほど、セルＡｉｊ内を通過しにくいことを意味しており、セル内コストが大きく設定される。例えば、セルＡｉｊ内の道路リンクの交通容量の合計値が大きいほど、セルＡｉｊ内の通過容易性が高く規定され、セル内コストが小さく設定される。
【００２５】
図４では直感的に理解しやすいように、セル内コストに対応してメッシュノードＮｉｊの大きさを変化させて示している。即ち、メッシュノードＮｉｊが大きいほど、そのメッシュノードＮｉｊに付与されたセル内コストが小さいことを示している。例えば、図２に示したセルＡ３１，Ａ３２に属する道路リンクＲ０の密度が相対的に高く、交通容量の合計値が相対的に大きいので、図４に示すように、メッシュノードＮ３１，Ｎ３２が相対的に大きく設定されている。一方、図２に示したセルＡ２４，Ａ３３，Ａ３４，Ａ４３，Ａ４４に属する道路リンクＲ０の密度が相対的に低く、交通容量の合計値が相対的に小さいので、図４に示すように、メッシュノードＮ２４，Ｎ３３，Ｎ３４，Ｎ４３，Ｎ４４が相対的に小さく設定されている。
【００２６】
図１に示した経路案内装置３１は、経路案内機能を有するコントローラである。経路案内装置３１は、例えばＣＰＵや記憶装置（レジスタ、キャッシュメモリ、主記憶装置）等を含むマイクロコンピュータやマイクロコンピュータに等価なプロセッサ等で構成することができる。経路案内装置３１は、交通需要予測部４１、交通量予測部４２及び経路探索部４３を備える。交通需要予測部４１は、交通情報収集装置２からセンター側通信装置３０を介して受信した道路交通情報等に基づいて、現在及び将来の所定の時間帯における所定の地域で発生する交通需要を予測する。交通量予測部４２は、交通需要予測部４１により予測された交通需要や、車両Ｖ１〜Ｖｎからセンター側通信装置３０を介して受信した車両Ｖ１〜Ｖｎの出発地、目的地、走行状況等に基づいて、現在及び将来の所定の時間帯における各道路リンクの交通量を予測する。
【００２７】
交通量予測部４２は更に、予測した各道路リンクの交通量に基づいて、各道路リンクの混雑度を算出（予測）する。混雑度は、道路リンクでの渋滞又は混雑の度合いを示す指標である。混雑度が高いほど、道路リンクが渋滞又は混雑することを意味する。混雑度は、例えば、道路リンクの交通容量に対する交通量の比として算出してもよい。或いは、道路リンクでの車両の平均速度や通行台数等を混雑度として代用してもよい。例えば、道路リンクの交通容量に対する交通量の比を混雑度とする場合、混雑度が所定の閾値を超えると渋滞と判定し、混雑度が所定の閾値以下のときは非渋滞と判定してもよい。
【００２８】
交通量予測部４２は、各道路リンクの混雑度に基づいて、セルＡｉｊ毎に、セルＡｉｊ内の道路リンクの混雑度の代表値を算出する。混雑度の代表値としては、例えば、セルＡｉｊ内の道路リンクの混雑度の単純平均値、道路リンク長を重みとした加重平均値、又は最大値等を採用可能である。
【００２９】
図５では、セルＡｉｊ毎の混雑度（代表値）を３段階で色（ハッチング）の濃淡により示している。濃い色のセルＡ３１，Ａ３２は混雑度が相対的に高いことを示す。即ち、セルＡ３１，Ａ３２では、渋滞又は強い混雑が生じ、著しく通過しにくい状況であることを示す。薄い色のセルＡ１３，Ａ２２は混雑度が相対的に中程度であることを示す。即ち、セルＡ１３，Ａ２２では中程度の混雑が生じており、通過しやすさは中程度であることを示す。着色無しのセルＡ１１，Ａ１２，Ａ１４，Ａ２１，Ａ２３，Ａ２４，Ａ３３，Ａ３４，Ａ４１，Ａ４２，Ａ４３，Ａ４４は、混雑度が相対的に低いことを示す。即ち、セルＡ１１，Ａ１２，Ａ１４，Ａ２１，Ａ２３，Ａ２４，Ａ３３，Ａ３４，Ａ４１，Ａ４２，Ａ４３，Ａ４４では混雑が生じておらず、通過しやすい状況であることを示す。交通量予測部４２により算出されたセルＡｉｊ毎の混雑度は、経路案内情報の一部としてセンター側通信装置３０を介して車両Ｖ１〜Ｖｎに送信してもよい。
【００３０】
交通量予測部４２は、算出したセルＡｉｊ毎の混雑度（代表値）に基づいて、メッシュマップ記憶部５２に記憶されているセルＡｉｊ毎のセル内コストを修正する。例えば、図５に示したように混雑度が相対的に高いセルＡ３１，Ａ３２のセル内コストを著しく大きくする。これにより、図４に示したメッシュノードＮ３１，Ｎ３２が、図６に示すように著しく小さくなる。また、図５に示したように混雑度が中程度のセルＡ１３，Ａ２２のセル内コストを中程度で大きくする。これにより、図４に示したメッシュノードＮ１３，Ｎ２２が、図６に示すように中程度で小さくなる。また、図５に示したように混雑度が相対的に低いセルＡ１１，Ａ１２，Ａ１４，Ａ２１，Ａ２３，Ａ２４，Ａ３３，Ａ３４，Ａ４１，Ａ４２，Ａ４３，Ａ４４ではセル内コストを修正せず、図４に示したメッシュノードメッシュノードＮ１１，Ｎ１２，Ｎ１４，Ｎ２１，Ｎ２３，Ｎ２４，Ｎ３３，Ｎ３４，Ｎ４１，Ｎ４２，Ｎ４３，Ｎ４４の大きさが図６に示すように維持される。
【００３１】
経路探索部４３は、車両Ｖ１〜Ｖｎからセンター側通信装置３０を介して受信した車両Ｖ１〜Ｖｎの出発地及び目的地の情報や、メッシュマップ記憶部５２に記憶されたメッシュマップ等を用いて、車両Ｖ１〜Ｖｎ毎に出発地から目的地までの経路を探索する。経路探索部４３は、複数のセルＡｉｊを対象として、出発地の属するセルＡｉｊから目的地の属するセルＡｉｊまでを結ぶセルＡｉｊで構成されたメッシュルートを探索する第１の探索部４４と、探索されたメッシュルート内の道路リンクを対象として、出発地から目的地までを結ぶ道路リンクで構成された経路を探索する第２の探索部４５を備える。
【００３２】
例えば、図７Ａに示すように、道路マップがセルＡｉｊ（ｉ＝１〜ｎ；ｊ＝１〜ｍ：ｎ，ｍは２以上の正の整数である。図７Ａ〜図７Ｄではｎ＝４，ｍ＝８の場合を例示する。）に区分された場合を考える。図７Ａにおいて色（ハッチング）の濃淡で示すようにセルＡｉｊ毎に段階的に（４段階で）混雑度が算出されている。セルＡ２３の混雑度が最も高く、渋滞が生じた状況である。セルＡ２３の周辺のセルＡ１２，Ａ１３，Ａ１４，Ａ１５，Ａ２２，Ａ２４，Ａ２５，Ａ３１，Ａ３２，Ａ３３では２番目に混雑度が高い。セルＡ２１，Ａ３４，Ａ３５，Ａ４１，Ａ４４，Ａ４７では３番目に混雑度が高い。セルＡ１１，Ａ１６，Ａ１７，Ａ１８，Ａ２６，Ａ２７，Ａ３６，Ａ３７，Ａ３８，Ａ４２，Ａ４３，Ａ４５，Ａ４６，Ａ４８では混雑度が最も低く、混雑が生じていない状況である。交通量予測部４２により、この混雑度を用いて各セルＡｉｊのセル内コストが修正されたとする。
【００３３】
第１の探索部４４は、メッシュマップ記憶部５２に記憶されたメッシュマップを読み出して、各セルＡｉｊのセル間コスト及びセル内コストに基づいて、ダイクストラ法等の経路探索アルゴリズムを用いて、図７Ｂに示すように、出発地Ｏの属するセルＡ３１から目的地Ｄの属するセルＡ１７までを結ぶセルＡ３１，Ａ４１，Ａ４２，Ａ４３，Ａ４４，Ａ４５，Ａ４６，Ａ３６，Ａ３７，Ａ２７，Ａ１７で構成されたメッシュルートＲ１を探索する。具体的には、出発地Ｏの属するセルＡ３１から目的地Ｄの属するセルＡ１７までを結ぶ任意のメッシュルートのうち、セル間コストとセル内コストの合計が最小となるメッシュルートが選択される。即ち、図７Ｂに示したメッシュルートＲ１は、メッシュルートＲ１を構成するセルＡ３１，Ａ４１，Ａ４２，Ａ４３，Ａ４４，Ａ４５，Ａ４６，Ａ３６，Ａ３７，Ａ２７，Ａ１７のそれぞれのセル間コストと、メッシュルートＲ１内で隣接するセルＡ３１，Ａ４１の間、セルＡ４１，Ａ４２の間、セルＡ４２，Ａ４３の間、セルＡ４３，Ａ４４の間、セルＡ４４，Ａ４５の間、セルＡ４５，Ａ４６の間、セルＡ４６，Ａ３６の間、セルＡ３６，Ａ３７の間、セルＡ３７，Ａ２７の間、セルＡ２７，Ａ１７の間のそれぞれのセル間コストとの合計値が最小であるため選択されている。
【００３４】
なお、図７Ａ及び図７Ｂを参照して、混雑度を加味して修正されたセル内コストを用いてメッシュルートＲ１を探索する場合を例示したが、第１の探索部４４は、混雑度を加味していない修正前のセル内コストを用いてメッシュルートＲ１を探索することもできる。
【００３５】
なお、道路リンクの疎密の関係等から、必ずしも混雑箇所を回避するようにメッシュルートＲ１を探索できない場合（例えば、一本道の主要道路上に出発地、混雑箇所、目的地が並ぶ場合等）が想定される。これについては、混雑箇所のセルＡｉｊのセル内コストが混雑度に応じて大きく修正されていても、そのメッシュルートＲ１しか取りえない場合には、第１の探索部４４は、高いコストであってもそのメッシュルートＲ１を探索する。したがって、メッシュルートＲ１を探索できないという不都合は発生しない。
【００３６】
第２の探索部４５は、図７Ｃに示すように、第１の探索部４４により探索されたメッシュルートＲ１に属する道路リンクＲ０を抽出する。第２の探索部４５は、図７Ｄに示すように、抽出した道路リンクＲ０を対象として、ダイクストラ法等の経路探索アルゴリズムを用いて、出発地Ｏから目的地Ｄまでを結ぶ道路リンクＲ０で構成される経路（リンクルート）Ｒ２を探索する。第２の探索部４５により探索されたリンクルートＲ２の情報は、経路案内情報として車両Ｖ１〜Ｖｎに送信される。
【００３７】
図１に示した車両Ｖ１において、表示制御部２３は、交通管理センター１から車両側通信装置１０を介して受信した経路案内情報に基づいて、図８Ａに示すように、表示装置１３の表示画面に、セルＡｉｊ単位で区分された道路地図を表示させる。図８Ａでは、例えば通常のナビゲーション装置と同様に、現在地Ｏと、現在地Ｏの周辺の道路リンク等を表示している。更に、表示制御部２３は、表示装置１３の表示画面に、セルＡｉｊ毎の混雑度を色分けや濃淡等により表示させる。
【００３８】
ここで、通常のナビゲーション装置では、渋滞・混雑箇所の情報を道路リンク単位で色分け等によって表示するため、渋滞・混雑箇所の位置は明確であるが、当該渋滞・混雑箇所周辺の混雑の程度は把握しにくい。これに対して、本発明の実施形態によれば、セルＡｉｊ単位で混雑度を色分けや濃淡等で示すことにより、乗員に対してセルＡｉｊ単位で広範囲の混雑の分布を認識させやすくなり、概略の進路を容易に想起させやすくなる。
【００３９】
更に、図７ＤのリンクルートＲ２が探索されたとした場合に、図８Ｂに示すように、表示装置１３は、現在地Ｏから目的地ＤまでのリンクルートＲ２を推奨経路として表示する。図８Ｂに示すように、セルＡｉｊ毎の混雑度も重畳して表示することにより、リンクルートＲ２が混雑度の高いセルＡｉｊを回避して探索されたことを乗員に対して直感的に理解させることができる。したがって、乗員の推奨経路に対する納得性、受容性を高めることができる。また、渋滞・混雑が発生していない時等には、表示装置１３は、セルＡｉｊ毎に混雑度の代わりにセル内コストを表示することにより、乗員に対してセルＡｉｊ毎に道路分布の様子を直感的に理解させることもできる。
【００４０】
＜経路案内方法＞
次に、図９のフローチャートを参照しながら、本発明の実施形態に係る経路案内方法の一例を説明する。
【００４１】
ステップＳ１０において、交通需要予測部４１は、交通情報収集装置２により収集された道路交通情報等から、所定の地域における現在の交通需要を取得する。ステップＳ１１において、交通需要予測部４１は、交通情報収集装置２により収集された道路交通情報等に基づいて、所定の地域における将来の交通需要を予測する。
【００４２】
ステップＳ１２において、交通量予測部４２が、交通需要予測部４１により取得された現在の交通需要と、交通需要予測部４１により予測された将来の交通需要に基づいて、渋滞・混雑箇所と渋滞・混雑の発生時刻を特定する。ステップＳ１３において、交通量予測部４２が、メッシュマップ記憶部５２に記憶されているメッシュマップの複数のセルＡｉｊのうち、特定した渋滞・混雑箇所が含まれるセルＡｉｊのセル内コストを修正する。
【００４３】
以降のステップＳ１４〜Ｓ１６の手順は、交通管理センター１の管理対象の全車両Ｖ１〜Ｖｎについて一台ずつ行う。ステップＳ１４において、例えば車両Ｖ１を処理対象として、経路探索部４３が、センター側通信装置３０を介して受信された車両Ｖ１の出発地及び目的地の位置情報等を取得する。
【００４４】
ステップＳ１５において、経路探索部４３が、車両Ｖ１の出発地及び目的地の位置情報等に基づいて、メッシュマップ記憶部５２に記憶されているメッシュマップを用いて、渋滞・混雑を回避するように出発地から目的地までの経路を探索する。なお、対象地域内に渋滞・混雑が発生しない場合であっても同様に経路探索を行う。
【００４５】
ステップＳ１６において、経路探索部４３により探索された経路の情報を含む経路案内情報を、センター側通信装置３０を介して車両Ｖ１に送信する。車両Ｖ１側では、経路案内情報に基づいて、表示装置１３の表示画面に道路地図上に推奨経路等を表示する。
【００４６】
ステップＳ１７において、ステップＳ１４〜Ｓ１６の処理を管理対象の全車両Ｖ１〜Ｖｎに対して行われたか否かを判定する。全車両Ｖ１〜Ｖｎに対して行われたと判定された場合には処理を完了する。一方、全車両Ｖ１〜Ｖｎに対して行われていないと判定された場合には、残りの車両についてステップＳ１４〜Ｓ１６の処理を繰り返す。
【００４７】
次に、図１０のフローチャートを参照しながら、図１に示したメッシュマップ記憶部５２に記憶されるメッシュマップの作成手法の一例を説明する。
【００４８】
ステップＳ２０において、メッシュマップ作成装置３４は、道路リンクマップ記憶部５１に記憶されている道路リンクマップを用いて、道路リンクマップ上に所定のメッシュサイズのセルＡｉｊを敷きつめて、道路リンクマップを複数のセルＡｉｊに区分する。
【００４９】
ステップＳ２１において、メッシュマップ作成装置３４は、セルＡｉｊ毎にＩＤ（ｉ，ｊ）を付与する。ここでは、２次元構造系のセルＡｉｊを想定し、二次元インデックス（ｉ，ｊ）を付与する場合を例示する。なお、セルＡｉｊの形状や構造は任意であるので、ＩＤの付与の仕方はセルＡｉｊの形態に適合したものを用いればよい。
【００５０】
ステップＳ２２において、メッシュマップ作成装置３４は、各セルＡｉｊに属する道路リンクをそれぞれ抽出する。ステップＳ２３において、メッシュマップ作成装置３４は、抽出した道路リンクが当該セルＡｉｊに所属することを示す情報を、道路リンクにそれぞれ付与する。
【００５１】
ステップＳ２４において、メッシュマップ作成装置３４は、複数のセルＡｉｊのうち、（ｉ，ｊ）番目のセルについて、（ｉ，ｊ）番目のセル内の道路リンクの道路規格、道路リンク長、道路幅、車線数等の属性情報を参照して、（ｉ，ｊ）番目のセル内の道路リンクの交通容量をそれぞれ算出する。更に、メッシュマップ作成装置３４は、各道路リンクの交通容量の合計値を算出する。
【００５２】
ステップＳ２５において、メッシュマップ作成装置３４は、算出した（ｉ，ｊ）番目のセル内の道路リンクの交通容量の合計値に基づいて、（ｉ，ｊ）番目のセルのセル内コストを設定し、メッシュノードに付与する。メッシュマップ作成装置３４は、交通容量の合計値が大きいほど、セル内コストを小さく設定する。
【００５３】
ステップＳ２６において、メッシュマップ作成装置３４は、ステップＳ２５及びＳ２６の処理が全セルＡｉｊに対して行われたか否かを判定する。全セルＡｉｊに対して行われていないと判定された場合には、残りのセルについて、ステップＳ２５及びＳ２６の処理を繰り返す。一方、ステップＳ２６において全セルＡｉｊに対して行われたと判定された場合には、ステップＳ２７に移行する。
【００５４】
ステップＳ２７において、メッシュマップ作成装置３４は、（ｉ，ｊ）番目のセルと、（ｉ，ｊ）番目のセルに隣接する（ｉ−１，ｊ）番目、（ｉ，ｊ−１）番目、（ｉ，ｊ＋１）番目、（ｉ＋１，ｊ）番目の４つのセルとの４つの境界に着目し、４つの境界を跨ぐ道路リンクをそれぞれ抽出する。メッシュマップ作成装置３４は、抽出した道路リンクの道路規格、道路リンク長、道路幅、車線数等の属性情報を参照して、各道路リンクの交通容量を算出する。更に、メッシュマップ作成装置３４は、４つの境界毎に、道路リンクの交通容量の合計値を算出する。
【００５５】
ステップＳ２８において、メッシュマップ作成装置３４は、４つの境界毎の交通容量の合計値に基づいて、（ｉ，ｊ）番目のセルと（ｉ−１，ｊ）番目のセルとの間、（ｉ，ｊ）番目のセルと（ｉ，ｊ−１）番目のセルとの間、（ｉ，ｊ）番目のセルと（ｉ，ｊ＋１）番目のセルとの間、（ｉ，ｊ）番目のセルと（ｉ＋１，ｊ）番目のセルとの間のセル間コストをそれぞれ設定し、対応するメッシュリンクＬにセル間コストをそれぞれ付与する。メッシュマップ作成装置３４は、交通容量の合計値が大きいほど、セル間コストを小さく設定する。
【００５６】
ステップＳ２９において、メッシュマップ作成装置３４は、ステップＳ２７及びＳ２８の処理が全セルＡｉｊ間に対して行われたか否かを判定する。全セルＡｉｊ間に対して行われたと判定された場合には処理を完了する。一方、全セルＡｉｊ間に対して行われていないと判定された場合には、残りのセルに対してステップＳ２７及びＳ２８の処理を繰り返す。この結果、全セルＡｉｊ内のセル内コスト及び全セルＡｉｊ間のセル間コストの情報を含むメッシュマップが生成され、メッシュマップ記憶部５２に記憶される。
【００５７】
次に、図１１のフローチャートを参照しながら、図９のフローチャートのステップＳ１２の渋滞・混雑箇所を特定する処理と、ステップＳ１３の渋滞・混雑箇所が含まれるセルのセル内コストを変更する処理の一例を説明する。
【００５８】
ステップＳ３１において、交通量予測部４２は、交通量予測部４２により予測された現在及び将来の各道路リンクの交通量に基づいて、各道路リンクの混雑度を算出する。各道路リンクの混雑度は、道路リンクの交通容量に対する交通量の比を採用してもよく、道路リンクを走行する車両の平均速度や通行台数等を代用してもよい。
【００５９】
ステップＳ３２において、交通量予測部４２は、ステップＳ３１で算出したセルＡｉｊ内の道路リンクの混雑度に基づいて、セルＡｉｊ毎に混雑度の代表値を算出する。混雑度の代表値としては、例えば単純平均値、道路リンク長を重みとした加重平均値、最大値等を採用可能である。
【００６０】
ステップＳ３３において、交通量予測部４２は、図１０のステップＳ２５でメッシュノードＮｉｊに付与した全セル内コストに、ステップＳ３２で算出した混雑度の代表値に応じた係数（ファクター）を乗じて、全セル内コストを修正する。ここで係数は１以上の値をとるとする。混雑度が相対的に高い場合には、係数を相対的に大きく設定することにより、修正されたセル内コストは修正前の値よりも増大する。混雑度が相対的に低い場合には、係数を小さく設定することにより、修正されたセル内コストは、修正前の値に近い値とする。混雑が生じておらず、混雑度が所定の閾値未満の場合には、係数を１として、修正前のセル内コストの値を維持する。
【００６１】
ステップＳ３４において、交通量予測部４２は、全セルＡｉｊに対してセル内コストを修正したか否かを判定する。全セルＡｉｊに対してセル内コストを修正したと判定された場合、処理を完了する。一方、全セルＡｉｊに対してセル内コストを修正していないと判定された場合、残りのセルに対してステップＳ３１〜Ｓ３３の処理を繰り返す。
【００６２】
次に、図１２のフローチャートを参照しながら、図９のフローチャートのステップＳ１５の渋滞・混雑箇所を回避するための経路探索処理の一例を説明する。
【００６３】
ステップＳ４１において、第１の探索部４４は、車両Ｖ１の出発地及び目的地の位置情報から、メッシュマップ記憶部５２に記憶されたメッシュマップを参照して、図７Ａに示すように、複数のセルＡｉｊのうち、出発地Ｏの属するセルＡ３１と、目的地Ｄの属するセルＡ１７をそれぞれ特定する。
【００６４】
ステップＳ４２において、第１の探索部４４は、複数のセルＡｉｊのセル内コスト及びセル間コストに基づいて、ダイクストラ法等の経路探索アルゴリズムを用いて、複数のセルＡｉｊを対象として、図７Ｂに示すようにメッシュルートＲ１を探索する。メッシュルートＲ１は、出発地Ｏの属するセルＡ３１から目的地の属するセルＡ１７までを繋ぐセルＡ３１，Ａ４１，Ａ４２，Ａ４３，Ａ４４，Ａ４５，Ａ４６，Ａ３６，Ａ３７，Ａ２７，Ａ１７で構成される。
【００６５】
ステップＳ４３において、第２の探索部４５は、図７Ｃに示すように、メッシュルートＲ１に含まれる各セルＡｉｊに属する道路リンクＲ０を抽出する。ステップＳ４４において、第２の探索部４５は、ステップＳ４３で抽出された道路リンクＲ０に対して、ダイクストラ法等の経路探索アルゴリズムを用いて、図７Ｄに示すように、出発地Ｏから目的地Ｄまでを繋ぐ道路リンクＲ０で構成するリンクルートＲ２を探索する。
【００６６】
なお、本発明の実施形態に係る経路案内プログラムは、図９に示した経路案内方法の一連の処理を、経路案内システムを構成する経路案内装置３１等のコンピュータに実行させることができる。本発明の実施形態に係る経路案内プログラムは、例えば経路案内装置３１の記憶装置等に格納可能である。
【００６７】
以上説明したように、本発明の実施形態によれば、出発地Ｏから目的地Ｄまでの経路探索を行う際に、道路地図を区分した複数のセルＡｉｊ毎の通過容易性に基づいて、複数のセルＡｉｊを対象として、出発地Ｏの属するセルから目的地Ｄの属するセルまでを結ぶセルで構成されたメッシュルートＲ１を探索する。即ち、ある道路リンクが渋滞・混雑箇所である場合にはその周辺の道路リンクも渋滞・混雑箇所である可能性が高い。これに対して、道路リンクと対象として経路探索を行う前に複数のセルＡｉｊ単位で道路メッシュルートＲ１を探索するので、渋滞・混雑箇所の可能性の高い道路リンクを複数のセルＡｉｊ単位でまとめて回避することができる。
【００６８】
そして、探索されたメッシュルートＲ１内の道路リンクを対象として、出発地Ｏから目的地Ｄまでを結ぶ道路リンクで構成された経路（リンクルート）Ｒ２を探索する。これにより、メッシュルートＲ１外の渋滞・混雑箇所の可能性の高い道路リンクをまとめて除外してから、道路リンクを対象とした経路探索を行うことができる。したがって、出発地Ｏから目的地Ｄまでの経路探索を最初から道路リンクを対象として行う場合と比較して、渋滞・混雑箇所である可能性が高い道路リンクに対して探索するための計算負荷を低減することができ、経路探索の高速化を図ることができる。特に、プローブ情報やビックデータを使った情報負荷が高い経路探索を行う際に有効である。
【００６９】
更に、複数のセルＡｉｊのセル内コストに加えて、複数のセルＡｉｊのセル間コストに基づいてメッシュルートＲ１を探索することにより、複数のセルＡｉｊのセル内コストのみに基づいてメッシュルートＲ１を探索する場合と比較して、渋滞・混雑箇所を回避するために使用する情報が増えるので、実際の渋滞・混雑箇所により即して渋滞・混雑箇所を回避しやすい経路を探索することができる。更に、セルＡｉｊ内の道路リンクの混雑度に応じて、複数のセルＡｉｊのセル内コストを修正することにより、セルＡｉｊ単位の渋滞・混雑状況を加味して経路を探索することができる。
【００７０】
（第１の変形例）
本発明の実施形態では、図１０のステップＳ２７及びＳ２８において、複数のセルＡｉｊのセル間コストを設定する際に、隣接するセルＡｉｊ間の境界を跨ぐ道路リンクの交通容量の合計値を算出して、算出した交通容量の合計値に応じてセル間コストを設定する場合を例示した。これに対して、第１の変形例では、セル間コストを設定する際に、隣接するセル間の境界を跨ぐ道路リンクの交通容量に加えて、隣接するセル間の境界を跨ぐ道路リンクの本数についても考慮する場合を例示する。
【００７１】
例えば、２０ｋｍ四方のセルを想定した場合、隣接するセル間の境界線の中央に広く交通容量の大きな道路リンクが一本ある場合には、隣接するセル間の境界線の端からこの道路リンクまで最大１０ｋｍの移動が必要となる。一方、半分の交通容量の道路リンクが２本、セル間の境界線上に所定の間隔で存在している場合には、これらの道路リンクに到達するのに要する距離は小さくてすみ、通過しやすさは向上すると考えられる。但し、道路リンクの本数が多くなりすぎて、細い道路リンクが多数ある状況では、車速の低下等から、通過しやすさは低減することが考えられる。つまり、隣接するセル間の境界を跨ぐ道路リンクは、ある程度の距離当たりの本数があると通過容易性は高く、少なすぎても多すぎても低減すると考えられる。
【００７２】
そこで、第１の変形例では、この状況をセル間コストに反映するように、図１３Ａに示すように、隣接するセル間の境界距離当たりの道路リンクの本数に応じた係数（ファクター）を設定する。この係数は、セル境界距離当たりの道路リンクの本数が大きくても、或いは小さくても高い値となる（即ち、通過コストが大きくなる）ように設定され、その間の適切な範囲の本数が通過しやすいことを示している。第１の変形例では、図１３Ａに示した係数を、道路リンクの交通容量の合計に乗じることによりセル間コストを修正する。即ち、セル間コストをＣ１、図１３Ａに示した係数をｆ１、隣接するセル間を跨ぐ道路リンクの交通容量をＣＬとして、セル間コストＣ１は式（１）で求めることができる。
Ｃ１＝ｆ１×ΣＣＬ   …（１）
【００７３】
第１の変形例によれば、セル間を跨ぐ道路リンクの交通容量及び道路リンクの本数密度によってセル間コストを評価することで、より実態に即した経路案内が可能となる。
【００７４】
（第２の変形例）
本発明の実施形態では、図１０のステップＳ２４及びＳ２５において、セルＡｉｊのセル内コストを設定する際に、セルＡｉｊに属する道路リンクの交通容量の合計値を算出し、算出した交通容量の合計値に応じてセル内コストを設定する場合を例示した。これに対して、第２の変形例では、セル内コストを設定する際に、セルに属する道路リンクの交通容量に加えて、セルに属する道路リンクの本数自体についても考慮する場合を例示する。
【００７５】
例えば、２０ｋｍ四方のセルを想定した場合、セル内の中央に広く交通容量の大きな道路リンクが２本、十字状に交差している場合には、セルの各辺の中央位置からこの道路リンクまで最大１０ｋｍの移動が必要であるが、その半分の交通容量の道路リンクが４本、所定の間隔をもって井字状に交差するように存在している場合には、これらの道路リンクに到達するのに要する距離は小さくてすむことが考えられる。即ち、セル内には、ある程度の本数の道路リンクがある方が通過しやすいと考えられる。但し、細い道路リンクが張り巡らされた状況では、交差点等により速度が上がらず、通過しやすさは低減することが考えられる。したがって、セル内の道路リンクは、ある程度の面積密度があると通過しやすいが、道路リンクの面積密度が過少又は過多となると通過しにくくなると考えられる。
【００７６】
そこで、第２の変形例では、この状況をセル内コストに反映するように、図１３Ｂに示すように、セル内の道路リンク密度（面積当たりの道路リンク本数）に応じた係数を設定する。この係数は、道路リンク密度が大きくても小さくても高い値となる（通過コストが大きくなる）ように設定され、その間の適切な道路リンク密度が通過しやすいことを示している。
【００７７】
第２の変形例では、図１３Ｂに示した係数を、道路リンクの交通容量の合計値に乗じることで、セル内コストを修正する。即ち、セル内コストをＣ２、図１３Ｂに示した係数をｆ２、セル内の道路リンクの交通容量をＣＬとして、セル内コストをＣ２は、式（２）で求めることができる。
Ｃ２＝ｆ２×ΣＣＬ   …（２）
【００７８】
第２の変形例によれば、セル内の道路リンクの交通容量及び道路リンク密度によってセル内コストを評価することによって、より実態に即した経路案内が可能となる。
【００７９】
（第３の変形例）
本発明の実施形態では、図１１のステップＳ３１〜Ｓ３３においてセル内コストを修正する際に、セルＡｉｊ内の混雑度の代表値を算出し、算出した混雑度の代表値に応じてセル内コストを修正する場合を例示した。これに対して、第３の変形例では、セル内コストを修正する際に、セル内の混雑リンクの空間的な偏りについて考慮する場合を例示する。
【００８０】
混雑の空間的な偏りが大きい場合には、混雑がある箇所に集中しており、セル内のそれ以外の箇所は混雑が少なく、通過が容易であることが考えられる。一方、混雑の空間的な偏りが少ない場合には、セル内の全域で混雑が広がっており、全域で通過の容易性が低いことが考えられる。
【００８１】
そこで、混雑の空間的な偏りを評価するために、図１３Ｃに示すように、偏りが相対的に小さい場合にセル内コストを相対的に大きくし、偏りが相対的に小さい場合にセル内コストを相対的に小さくするように混雑の偏り係数を設定する。
【００８２】
第３の変形例では、非渋滞時のセル内コストに対して、混雑度の係数と、図１３Ｃに示した混雑の偏り係数とを乗じることにより、セル内コストを修正する。即ち、セル内コストをＣ３、非渋滞時のセル内コストをＣ０、混雑度の係数をｆ３、図１３Ｃに示した混雑の偏り係数をｆ４として、セル内コストＣ３は、式（３）で求めることができる。
Ｃ３＝Ｃ０×ｆ３×ｆ４      …（３）
【００８３】
第３の変形例によれば、セル内の道路リンクの混雑状況を、セル内の混雑度に加えて、混雑の空間的偏りによって評価することで、渋滞・混雑をより有効に回避・低減するような経路案内が可能となる。
【００８４】
（第４の変形例）
本発明の実施形態においては、１つのメッシュマップを使用する場合を例示したが、出発地から目的地までの距離が長くなると、メッシュルートの探索対象となるセルの数が多くなり、メッシュルートの探索に時間を要する。また、出発地から目的地までの距離がメッシュサイズと同程度に短い場合には、１つのセルに出発地及び目的地のいずれもが属する場合や、隣接するセルに出発地及び目的地がそれぞれ属する場合が想定され、メッシュルートの探索が適切に機能しないことが考えられる。
【００８５】
例えば、図１４Ａ及び図１４Ｂに、互いに異なるメッシュサイズの２つのメッシュマップを示す。図１４Ａに示すメッシュマップのセルＡ１の大きさは、図１４Ｂに示すメッシュマップのセルＡ２の４倍である。図１４Ａに示すように、メッシュマップの左下端及び右上端部に出発地Ｏ及び目的地Ｄがそれぞれ存在する場合、４×４個のセルＡ１でカバーされる。これに対して、図１４Ａに示す出発地Ｏ及び目的地Ｄの位置を同じくして、図１４Ｂに示すセルＡ２を適用すると、１６×１６個のセルＡ２となり、探索対象となるセルＡ２の数が、図１４Ａに示すセルＡ１の場合に対して１６倍に増大し、算出時間もこれに準じて増大する。
【００８６】
また、図１４Ｂに示すように出発地Ｏから目的地Ｄまでの距離が短い場合には、図１４Ａに示した相対的に大きなメッシュサイズのメッシュマップを適用すると、隣接する２つのセルＡ１に出発地Ｏ及び目的地Ｄがそれぞれ位置することになり、適切なメッシュルートＲ１の探索が行えない。そこで、第４の変形例では、メッシュマップ記憶部５２に互いに異なるメッシュサイズの複数のメッシュマップを記憶させておき、出発地Ｏから目的地Ｄまでの距離に応じて選択的に使用する。
【００８７】
経路探索部４３は、経路探索対象である車両の出発地から目的地までの距離に応じて、適用するマップのメッシュサイズを選択する。メッシュサイズは、出発地から目的地までの距離を数分割する程度の大きさ（例えば、図１４Ａに示すように４×４分割）であることが、セル内コスト及びセル間コストの設定状況に応じて幾つかのメッシュルートを探索できるための１つの目安である。したがって、出発地から目的地までの距離を数分割する程度の大きさに準じるメッシュサイズのメッシュマップを適用することが適切と考えられる。しかし、用意するメッシュサイズには制限があることが考えられる。したがって、用意したメッシュサイズのメッシュマップのうちから、出発地から目的地までの距離を数分割する程度の大きさに近いサイズのメッシュマップを選択的に使用することが好ましい。
【００８８】
また、出発地から目的地までの距離が相対的に大きい場合に、複数のメッシュマップのうち、メッシュが相対的に粗いセルのメッシュマップを適用すると、混雑発生時に混雑箇所から大きく離れた経路を探索する可能性が高い。その場合には、全体的な渋滞・混雑の低減・回避の効果は大きくなる。
【００８９】
第４の変形例によれば、互いに異なるメッシュサイズの複数のメッシュマップを用意しておき、出発地から目的地までの距離に応じて複数のメッシュマップを選択的に使用することにより、距離に応じた適切なサイズのセルを使用することができる。更に、出発地から目的地までの距離が近いほど、複数のセルのサイズを小さく設定することにより、出発地から目的地までの距離が相対的に近い場合に、経路探索の自由度を確保することができる。一方、出発地から目的地までの距離が相対的に遠い場合に、探索対象となるセルの数が過剰となって計算負荷が増大することを抑制することができる。
【００９０】
（第５の変形例）
本発明の実施形態においては、図２に示すように、道路リンクマップを同一サイズの正方形のセルＡｉｊで区分する場合を例示した。しかしながら、地域によって道路リンクの密度は異なるため、同一サイズのセルＡｉｊのみを全域に用いると、道路リンクを含まないセルＡｉｊが多数個発生することが考えられる。そこで、第５の変形例では、道路リンクを含まないセルの数を低減させるべく、１つのメッシュマップ中に互いに異なるサイズのセルを設定する。
【００９１】
例えば、図１５に示すように、３段階のサイズのセルＡ１〜Ａ３を有するメッシュマップを使用する。図１５においては、セルＡ１のサイズが最も大きく、セルＡ２はセルＡ１の１／４のサイズであり、セルＡ３はセルＡ２の１／４のサイズである。セルＡ１〜Ａ３は、道路地図を構成する道路リンクの本数密度に応じてそれぞれ配置されている。即ち、道路リンクの本数密度が相対的に低い領域には、相対的にサイズの大きいセルＡ１が設定されている。道路リンクの本数密度が相対的に中程度の領域には、相対的なサイズが中程度のセルＡ２が設定されている。道路リンクの本数密度が相対的に高い領域には、相対的にサイズの小さいセルＡ３が設定されている。
【００９２】
第５の変形例によれば、１つのメッシュマップ中に互いに異なるサイズのセルＡ１〜Ａ３を設定し、道路地図上の道路リンクの密度が相対的に高い領域に対応するセルが、道路リンクの密度が相対的に低い領域に対応するセルよりも小さくなるように、セルＡ１〜Ａ３のサイズを異ならせる。これにより、特に道路リンクの疎密の分布が大きい地域等において、道路リンクの密度が相対的に高い領域ではメッシュルートの探索の自由度を確保しつつ、道路リンクの密度が相対的に低い領域を対象として探索する計算負荷を削減することができ、経路探索の高速化を図ることができる。なお、第５の変形例では、セルＡ１〜Ａ３の構造が非構造系となるため、セルＡ１〜Ａ３のＩＤや接続関係の記述が本発明の実施形態とは異なるが、セルＡ１〜Ａ３の構造に応じた管理手法を適用すればよい。
【００９３】
また、第５の変形例においては、セルＡ１〜Ａ３が正方形である場合を例示したが、セルＡ１〜Ａ３の形状は特に限定されない。例えば、正方形のセルＡ１〜Ａ３を複数個連ねたような長方形であってもよい。更に、セルＡ１〜Ａ３の形状は矩形に限定されず、三角形、長方形、六角形であってもよい。更には、例えば市区町村境界に沿うような不定形のセルであってもよい。その場合には、市区町村の境界等の既存の地域区分のデータを援用することも可能となる。
【００９４】
（第６の変形例）
本発明の実施形態では、メッシュルートＲ１の探索を１回のみ行い、後に、メッシュルートＲ１内のセルＡｉｊに属する道路リンクを抽出し、抽出した道路リンクから出発地及び目的地を繋ぐリンクルートＲ２を探索する場合を例示した。これに対して、第６の変形例では、メッシュマップ記憶部５２に互いに異なるサイズの複数のメッシュマップが記憶されており、複数のメッシュマップを順次用いてメッシュルートを多段階で探索する場合を例示する。
【００９５】
第１の探索部４４は、メッシュマップ記憶部５２に記憶された複数のメッシュマップのうち、図１６Ａに示すように、相対的に大きいメッシュサイズの複数のセル（１次セル）Ａ１で分割されたメッシュマップを抽出する。第１の探索部４４は、図１６Ｂに示すように、出発地Ｏの属するセルＡ１から目的地Ｄの属するセルＡ１までを結ぶセルＡ１で構成されたメッシュルート（１次メッシュルート）Ｒ１１を探索する。
【００９６】
更に、第１の探索部４４は、メッシュマップ記憶部５２に記憶された複数のメッシュマップのうち、相対的に小さいメッシュサイズの複数のセル（２次セル）Ａ２で区分されたメッシュマップを抽出する。そして、第１の探索部４４は、抽出したメッシュマップの複数のセルＡ２のうち、図１６Ｃに示すように、メッシュルートＲ１１に相当する位置座標のセルＡ２を抽出する。更に、第１の探索部４４は、抽出したセルＡ２のセル間コスト及びセル内コストに基づいて、図１６Ｄに示すように、出発地Ｏを含むセルＡ２から目的地Ｄを含むセルＡ２までを結ぶセルＡ２で構成されたメッシュルート（２次メッシュルート）Ｒ１２を探索する。
【００９７】
第２の探索部４５は、第１の探索部４４により探索されたメッシュルートＲ１２内の道路リンクを抽出する。第２の探索部４５は、抽出した道路リンクを対象として、出発地Ｏから目的地Ｄまでの結ぶ道路リンクで構成されたリンクルートを探索する。
【００９８】
第６の変形例によれば、セルＡ１で構成されたメッシュルートＲ１１を探索した後に、メッシュルートＲ１１内をセルＡ１よりも細かく区分した複数のセルＡ２毎の通過容易性に基づいて、セルＡ２で構成されたメッシュルートＲ１２を探索する。このように、同一の出発地Ｏ及び目的地Ｄに対して、セルＡ１，Ａ２のサイズを小さくしながら、多段階でメッシュルートＲ１１，Ｒ１２の探索を行っていくことにより、渋滞・混雑箇所の可能性が高い道路リンクをセルＡ１，Ａ２単位で段階的に除外していくことができる。したがって、メッシュルートの探索を１回のみ行う場合と比較して、道路リンクを対象とした検索を開始する前に、渋滞・混雑箇所の可能性が高い道路リンクをより多く除外することができるので、経路探索に要する時間を更に短縮することができる。なお、第６の変形例では、メッシュルートＲ１１，Ｒ１２を２段階で探索する場合を例示したが、更に他の異なるメッシュサイズのメッシュマップを用いて、メッシュルートを３段階以上の多段階で探索してもよい。
【００９９】
（その他の実施形態）
上記のように、本発明は実施形態及び第１〜第６の変形例によって記載したが、この開示の一部をなす論述及び図面は本発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施形態、実施例及び運用技術が明らかとなろう。本発明はここでは記載していない様々な実施形態等を含むことは勿論である。したがって、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【符号の説明】
【０１００】
１…交通管理センター
２…交通情報収集装置
１０…車両側通信装置
１１…車載装置
１２…地図情報記憶装置
１３…表示装置
２１…目的地設定部
２２…車両情報取得部
２３…表示制御部
３０…センター側通信装置
３１…経路案内装置
３２…地図情報記憶装置
３３…メッシュマップ作成装置
４１…交通需要予測部
４２…交通量予測部
４３…経路探索部
４４…第１の探索部
４５…第２の探索部
５１…道路リンクマップ記憶部
５２…メッシュマップ記憶部
Ｖ１〜Ｖｎ…全車両
【図１】
2017219415.tif 000003
【図２】
2017219415.tif 000004
【図３】
2017219415.tif 000005
【図４】
2017219415.tif 000006
【図５】
2017219415.tif 000007
【図６】
2017219415.tif 000008
【図７】
2017219415.tif 000009
【図８】
2017219415.tif 000010
【図９】
2017219415.tif 000011
【図１０】
2017219415.tif 000012
【図１１】
2017219415.tif 000013
【図１２】
2017219415.tif 000014
【図１３】
2017219415.tif 000015
【図１４】
2017219415.tif 000016
【図１５】
2017219415.tif 000017
【図１６】
2017219415.tif 000018