(57)【要約】【課題】旅行時間が設定されていないリンクを含む道路ネットワークを用いて経路探索を行う際の推定旅行時間の算出精度を向上させることで、経路探索精度を向上させた経路探索方法、経路探索システム及び経路探索サーバを提供すること。【解決手段】メッシュ状に分断された複数のメッシュデータからなる道路ネットワークであって、道路ネットワークはノードとリンクとにより形成され、道路ネットワークを用いて出発地点から目的地点までの旅行時間を含む最適経路を探索する経路探索方法であって、前記リンクには少なくとも距離パラメータと速度パラメータが設定されており、かつリンク毎の旅行時間が設定されていないものを含む場合の経路探索方法において、各リンクの速度パラメータをリンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正した後、補正後の速度パラメータを用いて最適経路の探索を行う。【選択図】  図１
2008122319.tif 000002
【特許請求の範囲】
【請求項１】
メッシュ状に分断された複数のメッシュデータからなる道路ネットワークであって、該道路ネットワークは交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成されており、前記道路ネットワークを用いて出発地点から目的地点までの旅行時間を含む最適経路を探索する経路探索方法であって、前記リンクには少なくとも距離パラメータと速度パラメータが設定されており、かつリンク毎の旅行時間が設定されていないものを含む場合の経路探索方法において、
各リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正した後、該補正後の速度パラメータを用いて最適経路の探索を行うことを特徴とする経路探索方法。
【請求項２】
前記速度パラメータの補正は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを参照することによってなされることを特徴とする請求項１に記載の経路探索方法。
【請求項３】
前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする請求項２に記載の経路探索方法。
【請求項４】
前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする請求項２に記載の経路探索方法。
【請求項５】
要求された経路探索条件に基づいて出発地から目的地までの経路を探索して案内経路を決定する経路探索システムであって、少なくとも、
メッシュ状に分断された複数のメッシュデータからなり、交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成された道路ネットワークを蓄積した道路ネットワークＤＢと、
該道路ネットワークＤＢを参照して、前記経路探索条件に基づく最短経路を探索する経路探索手段と、
前記複数のメッシュデータ内の各リンクのパラメータを補正する補正手段と、
を備え、
前記補正手段は、前記道路ネットワーク内の前記案内経路の属するメッシュデータ内のリンクに少なくとも距離パラメータと速度パラメータが設定されており、かつリンク毎の旅行時間が設定されていないものを含む場合に、各リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正することを特徴とする経路探索システム。
【請求項６】
前記補正手段は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを有し、該速度補正テーブルを参照することによってリンクの速度パラメータを補正することを特徴とする請求項５に記載の経路探索システム。
【請求項７】
前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする請求項６に記載の経路探索システム。
【請求項８】
前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする請求項６に記載の経路探索システム。
【請求項９】
通信手段と操作・表示手段とを備えたナビゲーション端末装置から送信される経路探索条件を含む経路案内要求に基づいて、前記経路探索条件内の出発地から目的地までの経路を探索して案内経路を決定する経路探索サーバであって、少なくとも
メッシュ状に分断された複数のメッシュデータからなり、交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成された道路ネットワークを蓄積した道路ネットワークＤＢと、
該道路ネットワークＤＢを参照して、前記経路探索条件に基づく最短経路を探索する経路探索手段と、
前記複数のメッシュデータ内の各リンクのパラメータを補正する補正手段と、
を備え、
前記補正手段は、前記道路ネットワーク内の前記案内経路の属するメッシュデータ内のリンクに少なくとも距離パラメータと速度パラメータが設定されており、かつリンク毎の旅行時間が設定されていないものを含む場合に、各リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正することを特徴とする経路探索サーバ。
【請求項１０】
前記補正手段は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを有し、該速度補正テーブルを参照することによってリンクの速度パラメータを補正することを特徴とする請求項９に記載の経路探索サーバ。
【請求項１１】
前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする請求項１０に記載の経路探索サーバ。
【請求項１２】
前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする請求項１０に記載の経路探索サーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路探索方法、経路探索システム及び経路探索サーバに関し、特にリンクに旅行時間が設定されていない道路ネットワークを用いて経路探索を行う際の推定旅行時間の算出精度を向上させることが可能な経路探索方法、経路探索システム及び経路探索サーバに関するものである。
【背景技術】
【０００２】
近年、出発地から目的地までの最短経路の探索を行うナビゲーション装置が広く普及しており、車両に搭載されるカーナビゲーション装置に加えて、携帯電話等の携帯通信端末を用いたナビゲーション装置も登場している。
【０００３】
このようなナビゲーション装置に用いられる道路ネットワークのデータは、通常、各道路の交差点等の地点にノードが付され、ノード間を結ぶ道路にはリンクが付され、データは地図をメッシュ単位で複数に分割されたもので構成されている。そして、ナビゲーション装置で最短経路探索を行う場合にはこの道路ネットワークのデータを参照し、ラベル確定法（ダイクストラ法）等を用いて経路探索を行うようになっている。
【０００４】
上に述べたラベル確定法は、現在最短経路探索が行われる際に一般に使用されているものである。以下には、図６に示すような道路ネットワークを仮定したときの出発地から目的地までの最短経路を探索する場合について簡単に説明する。なお、図６はラベル確定法を用いた最短経路探索を説明するための道路ネットワークの模式図であり、出発地のノードをＳとし、目的地のノードをＧとし、ノードＳからノードＧまでの間に存在するノードをＮ１〜Ｎ５とし、これらの各ノードＳ、Ｇ、Ｎ１〜Ｎ５を繋ぐリンクをＲ１〜Ｒ１１として示している。また、各リンクＲ１〜Ｒ１１にかっこ書きで示された数値はリンクコストである。
【０００５】
先ず、出発地のノードＳから直接到達可能なノードＮ１〜Ｎ３までのリンクＲ１〜Ｒ３を参照して仮の最短経路を設定する。このとき、リンクＲ１〜Ｒ３のリンクコストを見ると、出発地のノードＳからノードＮ１までの経路となるリンクＲ１が最小のリンクコスト（リンクコスト：１）であるので、ノードＮ１への最短経路が確定する。次に、最短距離が確定したノードＮ１から直接到達可能なノードを見ると、ノードＮ３とノードＮ４とが該当するので、ノードＮ１からノードＮ３及びノードＮ４へ到達するルートを仮の最短経路に設定する。この仮の最短経路を見ると、ノードＮ１からはノードＮ４が最も小さなリンクコスト（リンクコスト：１＋２＝３）で到達できるので、ノードＮ４への最短経路が確定する。なお、このとき、ノードＮ４へ到達するまでにかかるリンクコストが「３」となるので、このリンクコストよりも小さなリンクコストで到達できることが既に分かっているノードＮ２への最短経路（リンクＲ２、リンクコスト：２）も確定し、加えて、始めにノードＮ３までの仮の最短距離として設定されたリンクＲ３を経由するルートのリンクコスト（リンクコスト：５）よりも、リンクＲ１、Ｒ４を経由するルートのリンクコスト（リンクコスト：１＋３＝４）の方が小さいので、ノードＮ３までの仮の最短経路を更新する。
【０００６】
次に、ノードＮ２及びノードＮ４の最短経路が確定したので、これらのノードＮ２、Ｎ４から直接到達可能なノード（ノードＧ、Ｎ３、Ｎ５）に仮の最短経路を設定する。このとき、ノードＮ３へ到達可能な最小のリンクコストのルート（リンクＲ１、Ｒ４、リンクコスト：１＋３＝４）が確定するので、ノードＮ３への最短経路が確定する。そして、このノードＮ３から直接到達可能なノード（ノードＮ５）に仮の最短経路を設定する。このとき、ノードＮ５には既に仮の最短経路（リンクＲ１、Ｒ６、Ｒ９、リンクコスト：１＋２＋３＝６）が設定されているが、今回設定した仮の最短経路（リンクＲ１、Ｒ４、Ｒ８、リンクコスト：１＋３＋１＝５）の方がリンクコストが小さいので、この仮の最短経路をノードＮ５への最短経路として確定する。最後に、ノードＮ５から直接到達可能なノードを検索し、ノードＧまでの仮の最短経路を設定する。この場合も、ノードＧへの既に設定されている仮の最短経路（リンクＲ１、Ｒ６、Ｒ１０、リンクコスト：１＋２＋６＝９）よりも今回設定された仮の最短経路（リンクＲ１、Ｒ４、Ｒ８、Ｒ１１、リンクコスト：１＋３＋１＋３＝８）の方がリンクコストが小さいので、この仮の最短距離をノードＧへの最短距離として確定する。
【０００７】
上述したように、ラベル確定法（ダイクストラ法）を用いれば、ノードＳからノードＧまでの最短経路（上述の場合は、ノードＳ（出発地）→リンクＲ１→ノードＮ３→リンクＲ８→ノードＮ５→リンクＲ１１→ノードＧ（目的地））が容易に算出でき、全ての経路を探索する場合に比べてはるかに計算回数が少なくて済むので、現在はルート探索方法として一般に広く普及している。
【０００８】
ところで、上述の方法においては、各リンクにリンクコストが設定された道路ネットワークを用いている。このリンクコストとしては、通常、各リンクの旅行時間が設定される。この旅行時間はＶＩＣＳ（道路交通情報通信システム）センターに蓄積された情報を参照して設定されているものである。しかしながら、ＶＩＣＳセンターには道路ネットワーク内の全てのリンクの旅行時間が設定されているわけではない。つまり、旅行時間のデータがＶＩＣＳセンターに情報として蓄積されていないリンクについては、そのリンクの速度パラメータ（規定速度）と距離パラメータとに基づいて計算されている場合が多く、このようなデータを用いると、経路探索の際に誤差が大きくなってしまうという問題点を有している。
【０００９】
上述した問題点を解決する方法は特許文献にもいくつか紹介されており、例えば下記特許文献１には、ナビゲーション装置の発明に関し、信号交差点等の道路上の所定地点に対応するノードとこれらのノード間を道路に対応するリンクとでモデル化された道路網において、所定区域間あるいはノード間の起終点交通量（ＯＤ交通量データ）を交通情報入力手段（ＶＩＣＳ）からの交通情報に基づいて予測することで、ＶＩＣＳ等の外部からの旅行時間関連情報が提供されていないリンクを含む経路の経路探索を行う際のシミュレーション精度を向上させたものが開示されている。
【００１０】
また、下記特許文献２に開示された交通情報提供装置、交通情報提供方法の発明によれば、旅行時間を用いずに、例えば日種で分類された交通情報を用いて経路探索を含む予測を行う際に、ユーザが所定の日種を選択できるようにすることで、過去に蓄積されていない日種の組み合わせであっても好適な区間の所要時間予測が行えるようになり、また、所定区間における遅延リスクをも提供することが可能なものが開示されている。
【００１１】
【特許文献１】特開２０００−２８５３６２号公報（段落［０００４］、［０００５］、［００１５］、［００２１］）
【特許文献２】特開２００６−３９９７８号公報（請求項、段落［０００５］〜［０００９］）
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上記特許文献１及び２に開示された発明は、旅行時間関連情報が更新されないリンクを経由する場合、あるいはリンクの旅行時間を用いることなく所要時間を予測する場合において、その精度を向上させることを目的としているが、上記特許文献１に開示された発明においては、リンクの交通量をシミュレーションするために、各リンクの上流リンク及び下流リンクのデータから流入交通量、流出交通量、停留交通量あるいは発生交通量などの種々の交通量データの算出が必要となり、処理量が増大するため処理能力の高いサーバ等を用いる必要があるほか、処理時間が長くなるという課題が生じる。また、上記特許文献２に開示された発明においては、日種情報を元に経路の所要時間を予測するため、別途日種ごとに蓄積した所要時間予測データを有する必要があり、また、最適な予測時間を割り出すためにユーザの操作を必要とするため、操作が煩雑になってしまう。
【００１３】
また、上記特許文献１及び２に開示された発明において、例えば都心部から郊外部へ向かうような経路を探索した場合、算出された所要時間は現実の走行時間と大きく乖離してしまうという問題点がある。
【００１４】
本発明者は上記問題点に鑑み、リンクに旅行時間情報がない、あるいは更新されない経路を含む経路探索を行う際に、比較的簡単な処理で都心部と郊外部とで生じる走行時間の差異を反映した最適な経路探索方法を種々検討した結果、リンク同士が密な状態で存在している箇所は交差点等も多いため、実際に走行する場合には規定の速度を維持して走ることが難しいことや、反対にリンク同士が疎な状態で存在している箇所は自ずと交差点等が少なく、規定の速度を維持した走行が可能になる点に着目し、経路が通過した道路ネットワークのノードあるいはリンクの密度を元に各リンクの速度パラメータに補正を加えた後に旅行時間を算出し、この補正後の旅行時間を各リンクのリンクコストとして経路探索を行えば現実の走行時間に近い経路探索が実現できることを見出し、本願発明に至ったものである。
【００１５】
すなわち、本発明の目的は、旅行時間が設定されていないリンクを含む道路ネットワークを用いて経路探索を行う際の推定旅行時間の算出精度を向上させることで、経路探索精度を向上させた経路探索方法、経路探索システム及び経路探索サーバを提供することである。
【課題を解決するための手段】
【００１６】
上記目的を達成するために、本願の請求項１に記載の経路探索方法の発明は、メッシュ状に分断された複数のメッシュデータからなる道路ネットワークであって、該道路ネットワークは交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成されており、前記道路ネットワークを用いて出発地点から目的地点までの旅行時間を含む最適経路を探索する経路探索方法であって、前記リンクには少なくとも距離パラメータと速度パラメータが設定されており、かつリンク毎の旅行時間が設定されていないものを含む場合の経路探索方法において、
各リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正した後、該補正後の速度パラメータを用いて最適経路の探索を行うことを特徴とする。
【００１７】
また、請求項２に記載の発明は、請求項１に記載の経路探索方法において、前記速度パラメータの補正は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを参照することによってなされることを特徴とする。
【００１８】
また、請求項３に記載の発明は、請求項２に記載の経路探索方法において、前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする。
【００１９】
また、請求項４に記載の発明は、請求項２に記載の経路探索方法において、前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする。
【００２０】
請求項５に記載の経路探索システムの発明は、要求された経路探索条件に基づいて出発地から目的地までの経路を探索して案内経路を決定する経路探索システムであって、少なくとも、
メッシュ状に分断された複数のメッシュデータからなり、交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成された道路ネットワークを蓄積した道路ネットワークＤＢと、
該道路ネットワークＤＢを参照して、前記経路探索条件に基づく最短経路を探索する経路探索手段と、
前記複数のメッシュデータ内の各リンクのパラメータを補正する補正手段と、
を備え、
前記補正手段は、前記道路ネットワーク内の前記案内経路の属するメッシュデータ内のリンクに少なくとも距離パラメータと速度パラメータが設定されており、かつリンク毎の旅行時間が設定されていないものを含む場合に、各リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正することを特徴とする。
【００２１】
また、請求項６に記載の発明は、請求項５に記載の経路探索システムにおいて、前記補正手段は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを有し、該速度補正テーブルを参照することによってリンクの速度パラメータを補正することを特徴とする。
【００２２】
また、請求項７に記載の発明は、請求項６に記載の経路探索システムにおいて、前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする。
【００２３】
また、請求項８に記載の発明は、請求項６に記載の経路探索システムにおいて、前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする。
【００２４】
請求項９に記載の経路探索サーバの発明は、通信手段と操作・表示手段とを備えたナビゲーション端末装置から送信される経路探索条件を含む経路案内要求に基づいて、前記経路探索条件内の出発地から目的地までの経路を探索して案内経路を決定する経路探索サーバであって、少なくとも
メッシュ状に分断された複数のメッシュデータからなり、交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成された道路ネットワークを蓄積した道路ネットワークＤＢと、
該道路ネットワークＤＢを参照して、前記経路探索条件に基づく最短経路を探索する経路探索手段と、
前記複数のメッシュデータ内の各リンクのパラメータを補正する補正手段と、
を備え、
前記補正手段は、前記道路ネットワーク内の前記案内経路の属するメッシュデータ内のリンクに少なくとも距離パラメータと速度パラメータが設定されており、かつリンク毎の旅行時間が設定されていないものを含む場合に、各リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正することを特徴とする。
【００２５】
また、請求項１０に記載の発明は、請求項９に記載の経路探索サーバにおいて、前記補正手段は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを有し、該速度補正テーブルを参照することによってリンクの速度パラメータを補正することを特徴とする。
【００２６】
また、請求項１１に記載の発明は、請求項１０に記載の経路探索サーバにおいて、前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする。
【００２７】
また、請求項１２に記載の発明は、請求項１０に記載の経路探索サーバにおいて、前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする。
【発明の効果】
【００２８】
本発明は上記構成を備えることにより、以下に示すような優れた効果を奏するものである。すなわち、本発明の第１の態様に係る経路探索方法によれば、道路ネットワーク内のリンクに旅行時間が設定されていないものが存在するとき、従来の方法では単純に距離パラメータと速度パラメータとから旅行時間を算出していたために本来最短となる経路と乖離した最短経路が選択される可能性があったが、本発明ではリンクの速度パラメータをそのリンクの属するメッシュデータ内の総リンク数あるいは総ノード数に基づいて補正するため、例えば比較的速度を上げて走行できるようなリンクの速度パラメータは高く、速度が上げられないようなリンクの速度パラメータは低くそれぞれ補正することが簡単な方法で可能となり、より本来の最短となる経路に近い最短経路の探索を行うことができるようになる。また、従来のように処理回数が大幅に増大することがないので、経路探索時の処理の負荷も抑えることができる。
【００２９】
また、本発明の好ましい態様として、速度パラメータの補正を行う際に、予め設定された速度補正テーブルを用いて、メッシュデータ内の総リンク数あるいは総ノード数から速度補正係数を選択するという簡単な方法でリンクの速度パラメータを補正できるので、処理負荷が増大することなく処理を実現できる。
【００３０】
また、本発明の好ましい態様として、上記速度補正テーブルに設定された速度補正係数を、メッシュデータ内の総リンク数あるいは総ノード数が大きい場合には速度パラメータが小さくなるように、総リンク数あるいは総ノード数が小さい場合には速度パラメータが大きくなるようにそれぞれ補正するので、実際の走行速度に近い速度パラメータに一律に、かつ容易に変更することが可能となる。
【００３１】
また、本発明の好ましい態様として、リンクに道路属性情報、例えば一般道路や高速道路などの情報が設定され、この属性に合わせて速度補正テーブルを変更することにより、異なる道路属性であることに起因する補正後の速度パラメータの誤差も小さくすることができる。
【００３２】
また、本発明の第２の態様に係る経路探索システムによれば、上述した第１の態様に係る経路探索方法が奏する効果と同様の効果が得られる経路探索システムを実現でき、更に、本発明の第３の態様にかかる経路探索サーバによれば、上述した第１の態様に係る経路探索方法が奏する効果と同様の効果が得られる経路探索サーバを実現することができるようになる。
【発明を実施するための最良の形態】
【００３３】
以下、図面を参照して本発明の最良の実施形態を説明する。但し、以下に示す実施形態は、本発明の技術思想を具体化するための経路探索方法、経路探索システム及び経路探索サーバを例示するための経路探索システムの一例について示したものであって、本発明をこの経路探索システムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のものも等しく適応し得るものである。
【実施例１】
【００３４】
図１は本発明の一実施例に係る経路探索システムの構成を示した概略ブロック図、図２及び図３は道路ネットワークを構成するメッシュデータの一例を示した図である。本発明の一実施例に係る経路探索システム１は、インターネット等のネットワーク３０を介して接続される携帯通信端末あるいは車載用の通信型ナビゲーション端末等からなるナビゲーション端末装置１０と、経路探索サーバ２０とから構成されている。
【００３５】
ナビゲーション端末装置１０は、少なくとも制御手段１１と、通信手段１２と、操作・表示手段１３と、経路探索要求編集手段１４と、案内データ記憶手段１５と、位置検出手段と、を備えている。このうち、制御手段１１はＲＡＭ、ＲＯＭ等を有するマイクロプロセッサであって、ＲＯＭ内の制御プログラムに基づいて各種の制御を行う。また、通信手段１２は無線通信ユニットを含み、経路探索サーバ２０等と通信を行うためのものである。
【００３６】
操作・表示手段１３は種々の機能キーあるいは選択キーとＬＣＤ等からなる表示装置とから構成されており、表示装置に表示されるメニュー画面から種々のキーを用いて経路探索条件を入力するものである。また、経路探索要求編集手段１４は操作・表示手段１３により入力された出発地と目的地、及び後述する位置検出手段１６に検出されたナビゲーション端末装置１０の現在位置等に基づいて、経路探索サーバ２０にネットワーク３０を介して送信する経路探索条件データを編集するものである。案内データ記憶手段１５は経路探索サーバ２０から受信した地図データ及び経路探索データからなる案内経路データを記憶する記憶手段である。位置検出手段１６はＧＰＳ受信機を備え、ＧＰＳ衛生信号を受信・処理してナビゲーション端末装置１０の現在位置を測位するものである。
【００３７】
経路探索サーバ２０は、少なくとも制御手段２１と、通信手段２２と、経路探索手段２３と、データ編集手段２４と、速度補正手段２５と、道路ネットワークＤＢ２６と、を備えている。このうち、制御手段２１はマイクロプロセッサを備え、一般的なコンピュータ装置と同様、ＲＯＭ及びＲＡＭ内に格納された制御プログラムを元に経路探索サーバ２０内の種々の制御を実行するものである。通信手段２２はネットワーク３０を介して複数のナビゲーション端末装置１０から送信される経路探索条件を含む経路探索要求を受信し、この要求に基づく経路探索結果を返信するものである。
【００３８】
また、経路探索手段２３はナビゲーション端末装置１０から送信された経路探索要求に基づき、経路探索条件から最短経路を探索するものである。データ編集手段２４は経路探索手段２３によって探索された最短経路情報に基づいて案内経路データを作成し、この案内経路データを通信手段２２を介してナビゲーション端末装置１０に送信するものである。なお、この案内経路データには、経路探索手段２３で探索された案内経路上の出発地、経路の屈曲点、交差点、あるいは目的地などにガイドポイントが付されており、ガイドポイントの位置情報（緯度・経度）や、各ガイドポイントに関連する案内情報（例えば音声ガイダンス）が付加されている。
【００３９】
速度補正手段２５は、複数のメッシュデータから構成される道路ネットワークの各メッシュデータに基づいて経路となるリンクの速度パラメータを補正するものである。なお、詳細については後述する。また、道路ネットワークＤＢ２６は、上述したように、各道路の交差点等の地点にノードが付され、ノード間を結ぶ道路にはリンクが付され、地図をメッシュ単位で複数に分割された道路ネットワークが格納されたデータベースであって、この道路ネットワークＤＢ２６に格納された道路ネットワークは、図２及び図３に示すような所定の領域で分割されたメッシュデータによって構成されている。
【００４０】
そして、道路ネットワーク内のリンクには、法定制限速度からなる速度パラメータと、そのリンクの長さに該当する距離パラメータとが付加されている。そして、都心部など、交通量が多い道路や主要道路のリンクにはＶＩＣＳセンターから送信される道路交通情報により取得された旅行時間情報も付加されている。
【００４１】
次に速度補正手段２５について説明する。なお、図４は速度補正手段内の速度補正テーブルの一例を示す図である。
速度補正手段２５は、道路ネットワーク内のリンクに予め付加されている速度パラメータを補正するものである。詳しくは、この速度補正手段２５は図４に示すような速度補正テーブルＴ１、Ｔ２を有し、この速度補正テーブルＴ１、Ｔ２は、１メッシュデータ内の総リンク本数をレベル別（図４では６段階）に区分し、そのメッシュデータ内の全てのリンクの速度パラメータに補正係数を乗じることによって速度パラメータを補正するようになっている。
【００４２】
すなわち、速度補正手段２５では、経路探索に使用するメッシュデータのそれぞれの総リンク数を算出し、その総リンク数が速度補正パラメータの何れのレベルに該当するかを選定して速度補正係数を決定し、この速度補正係数を各リンクの速度パラメータに乗じることで各リンクの速度パラメータを補正するものである。例えば、図２に示すような道路が互いに密な状態で存在しているメッシュデータに属するリンクにおいては、リンク本数が多い、つまりレベルが高い（例えばレベル６）ものと判断し、補正後に速度パラメータが小さくなるような速度補正係数（例えば０．７）がリンクの規定の速度パラメータに乗じられて、補正後の速度パラメータが算出され、図３に示すような道路間が比較的離れている（疎状態の）メッシュデータに属するリンクにおいては、リンク本数が少ない、つまりレベルが低い（例えばレベル１）ものと判断し、補正後に速度パラメータが大きくなるような速度補正係数（例えば１．２）がリンクの規定の速度パラメータに乗じられて、補正後の速度パラメータが算出されるものである。なお、本実施例においては総リンク数に基づいて速度補正係数を決定したが、総ノード数に基づいて速度補正係数を決定するようにしてもよい。
【００４３】
加えて、図４に示したように、速度補正テーブルＴ１、Ｔ２はリンクの属する道路が高速道路である場合（Ｔ１）と一般道路である場合（Ｔ２）とで異なるものを使用するとより好ましい。これは該当するリンクが高速道路であってメッシュデータ中の総リンク本数が多いときは、それに比例してリンクを通過する車両数が増大する傾向にあることや、周辺にインターチェンジ（ＩＣ）がある場合が多いことなどによって走行時間の変動が一般道路よりも大きいためである。また、一般道路においても、総リンク数が多いことは交差点等の分岐点が多いことに直結し、加えて規定速度よりも遅い速度で走行する場合が多いため、このような速度補正係数を乗じておけば、より実際の走行速度にあった経路探索を実現できる。この速度補正テーブルＴ１、Ｔ２においては、規定の速度パラメータを補正する際に、その速度パラメータを補正によって大きくするか小さくするかの基準となるリンク数の基準値が速度補正テーブルＴ１、Ｔ２のそれぞれに設定されている。詳しくは、図４に示す高速道路の速度補正テーブルＴ１では、レベル４に該当するリンク数が基準値として設定されており、一般道路の速度補正テーブルＴ２では、レベル３に該当するリンク数が基準値として設定されている。なお、各リンクが一般道路であるかあるいは高速道路であるかはリンクに付加された道路属性情報に基づいて設定すればよい。また、道路属性情報は一般道路と高速道路との２つに分類されているものである必要はなく、複数の道路属性毎に速度補正テーブルが用意されていてもよい。
【００４４】
なお、上述の速度補正手段２５による速度パラメータの補正は、道路ネットワーク内の各リンクにおいて、特に旅行時間パラメータが設定されていないリンクや、旅行時間パラメータが設定されていても、その旅行時間が固定的に設定されているリンクに対して行うことが最も効果的である。すなわち、ＶＩＣＳにより最新の旅行時間が随時変更されて設定されているようなリンクにおいてはこの速度補正手段２５による補正を行う必要はなく、設定された旅行時間に基づいて経路探索を行えばよい。
【００４５】
上述した構成からなる経路探索システム１により、経路探索を行う場合について以下に説明する。なお、図５は経路探索サーバにおいて経路探索要求を受信した場合の経路探索工程を示すフローチャートである。
経路探索サーバ２０は、先ず、ステップＳ０１においてナビゲーション端末装置１０から経路探索要求を受信すると、ステップＳ０２において経路探索条件を参照し、ステップＳ０３において、経路探索条件内の出発地、目的地あるいはナビゲーション端末装置１０の現在位置から、経路探索に使用するメッシュデータを道路ネットワークＤＢから特定する。なお、ここで特定されるメッシュデータは後のステップＳ０５において経路探索を行う際に探索対象となる全てのリンクが属するメッシュデータであることが好ましいが、予め出発地、目的地あるいはナビゲーション端末装置１０の現在位置から最短経路となる経路をおおよそ予測することによってより少ないメッシュデータを特定するようにすると、後の処理の時間を短縮することができるので更に好ましい。
【００４６】
次に、ステップＳ０４において、ステップＳ０３で選定された各メッシュデータの総リンク数に基づき、速度補正手段２５によって各リンクの速度パラメータを補正する。この補正の際には、上述したように、リンクの属するメッシュデータの総リンク数及びリンクの道路属性情報を参照することで速度補正テーブルＴ１、Ｔ２より速度補正係数を選択して補正するようになっている。このようにリンクの速度パラメータが補正されると、ステップＳ０５において、経路探索を開始する。この経路探索の際には、例えば上述したラベル確定法を用い、その際のリンクコストには各リンクの旅行時間を採用する。なお、各リンクのリンクコストを旅行時間とする場合、予め旅行時間が設定されていないリンクにおいては、予め設定された距離パラメータと速度補正手段２５により補正された速度パラメータとに基づいて導き出すようにする。
【００４７】
上記ステップＳ０５において経路探索が行われた結果は、ステップＳ０６においてデータ編集手段２４によりナビゲーション端末装置１０で参照が可能なように案内経路データに修正される。そして、ステップＳ０７において、通信手段２２により経路探索要求を送信したナビゲーション端末装置１０に案内経路データを返信し、一連の経路探索工程を終了する。
【００４８】
上述したように、経路探索サーバ１０において経路探索を行う際に旅行時間情報が設定されていないリンクについて速度補正手段２５を用いて速度パラメータを補正すると、従来に比べて実際の旅行時間に合ったリンクの旅行時間を算出することが可能となり、実際の最短経路とほとんど乖離しない最短経路を選び出すことが可能となる。また、この最適な最短経路を選び出すために従来のように膨大なデータを処理する必要はなく、メッシュデータごとに一律に速度補正係数を選択するのみでよいので、経路探索サーバ２０の負荷が増大することなく実現することが可能となる。
【００４９】
また、上記実施例においては経路探索サーバ２０内に道路ネットワークＤＢ２６を備えているものとして説明を行ったが、道路ネットワークＤＢ２６は経路探索サーバ２０とは別個のサーバとして存在していても良い。また、上記実施例においては通信型のナビゲーション端末としてナビゲーション端末装置１０を示しているが、スタンドアロン型、すなわち、例えば車載用ナビゲーション端末装置であって、しかも道路ネットワークＤＢ及び経路探索手段を自身の装置内に有しているものにおいても、上記速度補正手段を有していれば同様に最適な最短経路探索を実現できるようになることは言うまでもない。
【図面の簡単な説明】
【００５０】
【図１】図１は本発明の一実施例に係る経路探索システムの構成を示した概略ブロック図である。
【図２】図２は道路ネットワークを構成するメッシュデータの一例を示した図である。
【図３】図３は道路ネットワークを構成するメッシュデータの他の例を示した図である。
【図４】図４は速度補正手段内の速度補正テーブルの一例を示す図である。
【図５】図５は経路探索サーバにおいて経路探索要求を受信した場合の経路探索工程を示すフローチャートである。
【図６】図６はラベル確定法を用いた最短経路探索を説明するための道路ネットワークの模式図である。
【符号の説明】
【００５１】
１        経路探索システム
１０      ナビゲーション端末装置
１１      制御手段
１２      通信手段
１３      操作・表示手段
１４      経路探索要求編集手段
１５      案内データ記憶手段
１６      位置検出手段
２０      経路探索サーバ
２１      制御手段
２２      通信手段
２３      経路探索手段
２４      データ編集手段
２５      速度補正手段
２６      道路ネットワークＤＢ
３０      ネットワーク
【図１】
2008122319.tif 000003
【図２】
2008122319.tif 000004
【図３】
2008122319.tif 000005
【図４】
2008122319.tif 000006
【図５】
2008122319.tif 000007
【図６】
2008122319.tif 000008
【手続補正書】
【提出日】平成19年11月15日(2007.11.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メッシュ状に分断された複数のメッシュデータからなる道路ネットワークであって、該道路ネットワークは交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成されており、前記道路ネットワークを用いて出発地点から目的地点までの旅行時間を含む最適経路を探索する経路探索方法であって、
前記道路ネットワークは、道路交通情報通信システムの情報に基づいて該当する各々のリンクの旅行時間が設定される道路ネットワークであって、該道路ネットワークの各々のリンクには少なくとも距離パラメータと速度パラメータが設定されており、かつ前記道路交通情報通信システムの情報に基づくリンク毎の旅行時間が設定されていないものを含む場合の経路探索方法において、
前記旅行時間が設定されていないリンクについては、該リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正した後、該補正後の速度パラメータを用いて最適経路の探索を行うことを特徴とする経路探索方法。
【請求項２】
前記速度パラメータの補正は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを参照することによってなされることを特徴とする請求項１に記載の経路探索方法。
【請求項３】
前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする請求項２に記載の経路探索方法。
【請求項４】
前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする請求項２に記載の経路探索方法。
【請求項５】
要求された経路探索条件に基づいて出発地から目的地までの経路を探索して案内経路を決定する経路探索システムであって、少なくとも、
メッシュ状に分断された複数のメッシュデータからなり、交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成された道路ネットワークを蓄積した道路ネットワークＤＢと、
該道路ネットワークＤＢを参照して、前記経路探索条件に基づく最短経路を探索する経路探索手段と、
前記複数のメッシュデータ内の各リンクのパラメータを補正する補正手段と、を備え、
前記道路ネットワークＤＢは、道路交通情報通信システムの情報に基づいて該当する各々のリンクの旅行時間が設定される道路ネットワークであって、該道路ネットワークの各々のリンクには少なくとも距離パラメータと速度パラメータが設定されており、かつ前記道路交通情報通信システムの情報に基づくリンク毎の旅行時間が設定されていないものを含み、
前記補正手段は、前記旅行時間が設定されていないリンクについては、該リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正することを特徴とする経路探索システム。
【請求項６】
前記補正手段は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを有し、該速度補正テーブルを参照することによってリンクの速度パラメータを補正することを特徴とする請求項５に記載の経路探索システム。
【請求項７】
前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする請求項６に記載の経路探索システム。
【請求項８】
前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする請求項６に記載の経路探索システム。
【請求項９】
通信手段と操作・表示手段とを備えたナビゲーション端末装置から送信される経路探索条件を含む経路案内要求に基づいて、前記経路探索条件内の出発地から目的地までの経路を探索して案内経路を決定する経路探索サーバであって、少なくとも
メッシュ状に分断された複数のメッシュデータからなり、交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成された道路ネットワークを蓄積した道路ネットワークＤＢと、
該道路ネットワークＤＢを参照して、前記経路探索条件に基づく最短経路を探索する経路探索手段と、
前記複数のメッシュデータ内の各リンクのパラメータを補正する補正手段と、を備え、
前記道路ネットワークＤＢは、道路交通情報通信システムの情報に基づいて該当する各々のリンクの旅行時間が設定される道路ネットワークであって、該道路ネットワークの各々のリンクには少なくとも距離パラメータと速度パラメータが設定されており、かつ前記道路交通情報通信システムの情報に基づくリンク毎の旅行時間が設定されていないものを含み、
前記補正手段は、前記旅行時間が設定されていないリンクについては、該リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正することを特徴とする経路探索サーバ。
【請求項１０】
前記補正手段は、リンクが該当するメッシュデータ中の総リンク数又は総ノード数に基づいて設定された補正係数情報からなる速度補正テーブルを有し、該速度補正テーブルを参照することによってリンクの速度パラメータを補正することを特徴とする請求項９に記載の経路探索サーバ。
【請求項１１】
前記速度補正テーブル内の補正係数情報は、メッシュデータ中の総リンク数又は総ノード数が予め設定されたリンク数又はノード数の基準値より大きい場合には規定の速度パラメータが小さくなるような補正係数が設定され、メッシュデータ中の総リンク数又は総ノード数が前記基準値より小さい場合には規定の速度パラメータが大きくなるように補正係数が設定されていることを特徴とする請求項１０に記載の経路探索サーバ。
【請求項１２】
前記リンクには更に道路属性情報が付与されており、前記速度補正テーブルは前記道路属性情報毎に設定されていることを特徴とする請求項１０に記載の経路探索サーバ。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
上記目的を達成するために、本願の請求項１に記載の経路探索方法の発明は、
メッシュ状に分断された複数のメッシュデータからなる道路ネットワークであって、該道路ネットワークは交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成されており、前記道路ネットワークを用いて出発地点から目的地点までの旅行時間を含む最適経路を探索する経路探索方法であって、
前記道路ネットワークは、道路交通情報通信システムの情報に基づいて該当する各々のリンクの旅行時間が設定される道路ネットワークであって、該道路ネットワークの各々のリンクには少なくとも距離パラメータと速度パラメータが設定されており、かつ前記道路交通情報通信システムの情報に基づくリンク毎の旅行時間が設定されていないものを含む場合の経路探索方法において、
前記旅行時間が設定されていないリンクについては、該リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正した後、該補正後の速度パラメータを用いて最適経路の探索を行うことを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
請求項５に記載の経路探索システムの発明は、
要求された経路探索条件に基づいて出発地から目的地までの経路を探索して案内経路を決定する経路探索システムであって、少なくとも、
メッシュ状に分断された複数のメッシュデータからなり、交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成された道路ネットワークを蓄積した道路ネットワークＤＢと、
該道路ネットワークＤＢを参照して、前記経路探索条件に基づく最短経路を探索する経路探索手段と、
前記複数のメッシュデータ内の各リンクのパラメータを補正する補正手段と、を備え、
前記道路ネットワークＤＢは、道路交通情報通信システムの情報に基づいて該当する各々のリンクの旅行時間が設定される道路ネットワークであって、該道路ネットワークの各々のリンクには少なくとも距離パラメータと速度パラメータが設定されており、かつ前記道路交通情報通信システムの情報に基づくリンク毎の旅行時間が設定されていないものを含み、
前記補正手段は、前記旅行時間が設定されていないリンクについては、該リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正することを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
請求項９に記載の経路探索サーバの発明は、
通信手段と操作・表示手段とを備えたナビゲーション端末装置から送信される経路探索条件を含む経路案内要求に基づいて、前記経路探索条件内の出発地から目的地までの経路を探索して案内経路を決定する経路探索サーバであって、少なくとも
メッシュ状に分断された複数のメッシュデータからなり、交差点を含む各地点に付与されたノードと該ノード間の道路上に付与されたリンクとにより形成された道路ネットワークを蓄積した道路ネットワークＤＢと、
該道路ネットワークＤＢを参照して、前記経路探索条件に基づく最短経路を探索する経路探索手段と、
前記複数のメッシュデータ内の各リンクのパラメータを補正する補正手段と、を備え、
前記道路ネットワークＤＢは、道路交通情報通信システムの情報に基づいて該当する各々のリンクの旅行時間が設定される道路ネットワークであって、該道路ネットワークの各々のリンクには少なくとも距離パラメータと速度パラメータが設定されており、かつ前記道路交通情報通信システムの情報に基づくリンク毎の旅行時間が設定されていないものを含み、
前記補正手段は、前記旅行時間が設定されていないリンクについては、該リンクの速度パラメータを該リンクが属するメッシュデータ中の総リンク数又は総ノード数に基づいて補正することを特徴とする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
本発明は上記構成を備えることにより、以下に示すような優れた効果を奏するものである。すなわち、本発明の第１の態様に係る経路探索方法によれば、道路ネットワークは、道路交通情報通信システムの情報に基づいて該当する各々のリンクの旅行時間が設定される道路ネットワークであって、該道路ネットワークの各々のリンクには少なくとも距離パラメータと速度パラメータが設定されており、かつ前記道路交通情報通信システムの情報に基づくリンク毎の旅行時間が設定されていないものが存在するとき、従来の方法では単純に距離パラメータと速度パラメータとから旅行時間を算出していたために本来最短となる経路と乖離した最短経路が選択される可能性があったが、本発明では旅行時間が設定されていないリンクについては、該リンクの速度パラメータをそのリンクの属するメッシュデータ内の総リンク数あるいは総ノード数に基づいて補正するため、例えば比較的速度を上げて走行できるようなリンクの速度パラメータは高く、速度が上げられないようなリンクの速度パラメータは低くそれぞれ補正することが簡単な方法で可能となり、より本来の最短となる経路に近い最短経路の探索を行うことができるようになる。また、従来のように処理回数が大幅に増大することがないので、経路探索時の処理の負荷も抑えることができる。