経路算出装置、経路算出システム、および経路算出方法
【課題】経路算出時の計算量を抑制しながら、ユーザにとって利便性の高い経路情報を提供する。
【解決手段】本発明の実施形態の経路算出装置１０００は、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部５０と、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部１０６０と、地図情報記憶部５０を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部７０と、第１エリアと第２エリアを結ぶ経路情報を、エリア間経路記憶部１０６０より取得して、始点と終点を結ぶ経路を導出する経路導出部１０８０とを備える。
【解決手段】本発明の実施形態の経路算出装置１０００は、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部５０と、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部１０６０と、地図情報記憶部５０を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部７０と、第１エリアと第２エリアを結ぶ経路情報を、エリア間経路記憶部１０６０より取得して、始点と終点を結ぶ経路を導出する経路導出部１０８０とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路を算出する技術に関し、特に、地図情報をもとに経路を算出する経路算出装置、経路算出システム、および経路算出方法に関する。
【背景技術】
【０００２】
従来、経路算出装置においては、例えばダイクストラ法を用いて経路計算を行う手法が知られているが、経路計算の対象となる領域が広い場合には、経路計算に長い時間がかかるという課題がある。この課題を解決するために、本出願人は以下で示す特許文献に係る経路算出装置を開示している。
【０００３】
この経路算出装置では、地図を所定のメッシュに分割し、主要幹線道路がそのメッシュに出入りする箇所を境界ノードとする。そして、その境界ノード間の移動コストを、メッシュに対応付けて、あらかじめ記憶しておく。一方で、メッシュ内部をさらに細メッシュに分割し、メッシュ内部のノード間の移動コストを、細メッシュに対応付けて、あらかじめ記憶しておく。始点と終点が指定されると、始点が存在するメッシュと終点が存在するメッシュとの間の移動コストは、これらの間に存在するメッシュ（以下、「中間メッシュ」と呼ぶ。）の境界ノード間の移動コストを和算して算出される。また、始点とそのメッシュの境界ノード間、終点とそのメッシュの境界ノード間の移動コストは、細メッシュに含まれるノード間の移動コストをもとに、ダイクストラ法を用いて算出される。そして、これらの移動コストを和算して、始点から終点までの最終的な移動コストが算出される。
【特許文献１】特開２００５−２２８０１１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
経路算出装置においては、経路算出に要する時間は短いことが望ましく、そのためには、経路算出時の計算量は抑制されることが望ましい。
【０００５】
本発明はこうした状況を鑑みてなされたものであり、その目的は、経路算出時の計算量を抑制しながら、ユーザにとって利便性の高い経路情報を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は、経路算出装置に関する。この経路算出装置は、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部と、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部と、地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部と、第１エリアと第２エリアを結ぶ経路情報を、エリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出部と、を備える。
【０００７】
本明細書の「ノード」とは、地図のデータ内で決定された特定の地点であり、例えば、道路の交差点、道路のエリアへの出入り口、道路の行き止まり、主要な建造物の前等である。また、「リンク」とは、ノード間を結ぶ経路であり、物理的な道路そのものであってもよいが、物理的な道路の形状とは異なり、論理的にノード間の結びつきを示すものであってもよい。
【０００８】
本発明の別の態様は、経路算出システムに関する。この経路算出システムは、経路算出サーバと、経路表示端末と、を備える。この経路算出サーバは、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部と、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部と、経路を算出する始点および終点を指定する経路算出要求情報をもとに、地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部と、第１エリアと第２エリアを結ぶ経路情報を、エリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出部と、経路表示端末から前記経路算出要求情報を受け付け、また、前記経路表示端末に導出した経路を出力する通信部と、を有する。また、経路表示端末は、ユーザから、経路算出要求情報の指定入力を検出する受付部と、経路算出要求情報を経路算出サーバに出力し、また、経路算出サーバにより導出された経路を取得する通信部と、取得した経路を画面表示させる表示部と、を有する。
【０００９】
本発明のさらに別の態様は、経路算出方法に関する。この経路算出方法は、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定ステップと、第１エリアと第２エリアを結ぶ経路情報を、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出ステップと、を備える。
【００１０】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、システム、プログラム、プログラムを格納した記憶媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１１】
本発明によれば、経路算出時の計算量を抑制しながら、ユーザにとって利便性の高い経路情報を提供できる。
【発明を実施するための最良の形態】
【００１２】
従来、最短経路を求める方法として、例えばダイクストラ法を用いて経路計算を行う手法が知られている。ダイクストラ法とは、ある領域が与えられているときに、領域中の任意のノードから他の全てのノードまでの最短経路を決定する計算方法である。計算の初期状態では始点ノードの最短路のみが確定している状態から始まり、最短路が確定したノードを順次最短経路木、つまり、あるノードから他のノードへの最短路で使われているノード・リンクからなる木構造のデータに加えていく。これにより、最終的に、始点ノードから他の全てのノードに対する最短路が決定する。ダイクストラ法を用いた場合の計算量は、Ｏ記法で示すと、一般にＯ（ｎ＾２）となる。ここで、ｎは領域内の全ノード数、＾はベキ乗を表す。
【００１３】
前述の計算量から明らかなように、ダイクストラ法を用いて経路計算を行うとき、経路計算の対象となる領域が広い、つまり多数のノードが含まれる場合には、経路計算に長い時間がかかるという課題がある。したがって、例えば、ユーザがカーナビゲーション装置に対して、現在位置から離れた目標地点までの経路設定を要求した場合に、長時間の待ち時間が発生する可能性がある。
【００１４】
本発明者は、事前にノード間の最短経路（以下、「ノード間経路」と呼ぶ。）を計算しておき、カーナビゲーション装置のような経路算出装置に、このノード間経路を記憶させておくことで、経路計算の時間を短縮できると考えた。経路算出装置に記憶されたノード間経路のことを、以下、「学習経路」と呼ぶことにする。全てのノードについて、学習経路を作成できれば、学習経路を用いる場合の計算量はＯ（１）であるため、大幅な計算量の削減となり、その結果、ユーザの要求に対するレスポンスタイムの向上も実現できる。
【００１５】
本発明者は、全ノードの学習経路の作成にあたり、以下の３つの課題の存在を知見した。
（１）膨大な記憶容量の必要性
領域内のノード数をｎとすると、単純に全てのノード間経路を算出した場合、ノード間経路数は（ｎ＾２）本存在する。例えば、日本全国の地図の場合、ノード数（ｎ）は、約８００万個存在するため、膨大な数のノード間経路が存在し、現実的な記憶容量を遙かに上回ってしまう。
（２）膨大な事前計算量の必要性
ダイクストラ法で計算した場合、あるノードから他の全てのノードまでの最短経路が１回の計算で求まり、この所要時間は５〜６分である。前述のように、日本全国の地図の場合、ノード数は約８００万個存在するため、単純にノード数を積算すると、事前計算に要する時間は非常に長期間となり、現実的に可能な事前計算量を遙かに上回ってしまう。
（３）事前に固定的な学習経路を持つことによる弊害
実際の交通状況には、事故渋滞や工事による通行止めの発生など、事前に算出した学習経路をそのまま適用することが妥当でない場合がある。
以下、本発明の実施形態として、これらの課題を解決する経路算出装置、および経路算出システムを説明する。
【００１６】
（第１の実施形態）
図１は、本発明の第１の実施形態に係る経路算出装置１０の構成例を示す機能ブロック図である。経路算出装置１０は、ユーザインタフェイス部２０と、受信部３０と、現在位置導出部４０と、地図情報記憶部５０と、エリア間経路記憶部６０と、エリア特定部７０と、経路導出部８０と、移動コスト調整部９０とを備える。これらの構成は、ハードウェアコンポーネントでいえば、任意のコンピュータのＣＰＵ、メモリ、メモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。図１１および図２０の機能ブロック図においても同様である。
【００１７】
ユーザインタフェイス部２０は、ユーザからの、経路を算出する終点の指定情報を含む経路算出要求情報の入力を受け付ける。経路算出要求情報には、経路を算出する始点の指定情報は必須ではない。始点がユーザにより明示的に指定された場合には、経路算出装置１０は、ユーザの現在位置にかかわらず、指定された始点から終点までの経路を算出する。始点が明示的に指定されない場合には、経路算出装置１０は、ユーザの現在位置を始点として指定された終点までの経路を算出する。
【００１８】
受信部３０は、ＧＰＳ（Global Positioning System）や、ＶＩＣＳ（Vehicle Information and Communication System）（登録商標）といった交通情報提供システムからの情報を受け付ける。例えば、複数のＧＰＳ衛星から時刻情報を含む電波信号を受け付ける。また、交通情報提供システムからは、渋滞、所要時間、事故・故障車・工事、速度規制・車線規制等の交通情報を受け付ける。
現在位置導出部４０は、複数のＧＰＳ衛星からの電波信号をもとに、現在位置を導出する。現在位置を導出する方法は、既知の測位方法を用いてよい。また現在位置導出部４０が導出した現在位置を、経路を算出する始点としてもよい。
移動コスト調整部９０については、後述する。
【００１９】
地図情報記憶部５０は、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報（以下、「リンク情報」と呼ぶ。）とを、それぞれのエリアに対応付けて格納する。なお、リンク情報には少なくともノード間の距離が含まれることとする。図２は、地図のイメージ図である。同図では、地図の全体領域２０２の中に、ノード２０４と、ノード間の経路であるリンク２０６が存在することを示している。地図情報記憶部５０は、全体領域２０２を分割したエリアを特定する座標情報、例えば経度情報や緯度情報を保持する。
【００２０】
図３は、地図情報記憶部５０が格納する複数のエリアに分割された地図情報のイメージ図である。同図では、地図の全体領域が複数のエリア、例えばエリア３０２、エリア３０４等に分割された状態を示している。各エリアのノードには、地図全体における一意の識別番号が振られており、さらに、エリアの境界に位置する境界ノード、例えば境界ノード３０６が決められている。なお、図３は、理解の便宜のためのイメージであり、地図情報記憶部５０は、実際には、テーブル等でこれらのエリア情報・ノード情報・境界ノード情報を管理してもよい。
【００２１】
図４は、地図情報記憶部５０が格納するリンク情報のデータ構造を示す。図３のエリア３０２については、そのエリアにおいてリンクで接続されたノードの組み合わせ数分のレコードが存在する。移動コストは、ノード間の単なる距離でもよいが、ノード間の移動時間、通行のための費用等、またはそれらの組み合わせに基づいて重み付けされたものであってもよい。さらに、車幅や車線数、信号の数、天候など通行のしやすさに応じて調整されてもよい。本明細書の以下においても同様である。
なお、同図では、出発ノードと目標ノードが入れ替わっただけの組、例えば、出発ノード番号Ｘ０１０１・目標ノード番号Ｘ０１０３と、出発ノード番号Ｘ０１０３・目標ノード番号Ｘ０１０１とは別のものとして移動コストを格納している。これらのノードの組について別のものとして取り扱うことで、車線数の違いや、方向による混雑の違いなど、より現実の交通事情に即した移動コストの設定が可能になる。変形例として、出発ノードと目標ノードが入れ替わっただけの、これらのノードの組については、同一のものと取り扱ってもよい。この場合、地図情報記憶部５０が格納するデータ量が削減されるという効果がある。
【００２２】
エリア間経路記憶部６０は、異なるエリアの境界ノード間の経路（以下、「エリア間経路情報」と呼ぶ。）をリンクの組み合わせとして格納する。このエリア間経路は、あるエリアの１つの境界ノードと他のエリアの１つの境界ノードとの間の経路を特定するものであってもよい。さらに、あるエリアの１つの境界ノードと他のエリアとの組み合わせ毎に、所定の条件に基づいて１つの経路が決定されてもよい。ここで、所定の条件は、距離・移動時間・通行のための費用等、つまり移動コストに基づく条件であってもよい。具体的には、移動コストが、特定のエリアの１つの境界ノードと他のエリアとの組み合わせにおいて、最も小さいという条件であってもよく、また所定の閾値よりも小さいという条件であってもよい。以下では、例示として、移動コストが最も小さいエリア間経路が選定されるものとする。
【００２３】
図５は、エリア間経路のイメージ図である。エリア３０２からエリア３０４へのエリア間経路はエリア３０２の境界ノード数分、つまり３本、存在する。同図において、境界ノードＹ０１１とエリア３０４については、エリア間経路５０２で示している。同様に、境界ノードＹ１０２とエリア３０４については、エリア間経路５０４で、境界ノードＹ１０１とエリア３０４については、エリア間経路５０６で示している。
【００２４】
図６は、エリア間経路記憶部６０が格納するエリア間経路のデータ構造を例示する。同図は、例えば図５のエリア間経路５０２の場合、境界ノード番号がＹ０１１のレコードで示されるエリア間経路として保持されることを示している。なお、エリア間経路は、リンクの組み合わせとして格納されている。つまり、図５のエリア間経路５０２の場合、境界ノードＹ０１１とノードＸ０２０１のリンク、ノードＸ０２０１とノードＸ０２０２のリンク・・・、という具合に個々のリンクの組み合わせとなっている。これによる効果は後述する。
【００２５】
エリア間経路は、学習経路として事前に算出して、エリア間経路記憶部６０が記憶しておく。エリア間経路の算出例を以下示す。まず、特定のエリアＡの１つの境界ノードａから、他のエリアＢの全境界ノードまでの移動コストを、ダイクストラ法を用いて算出する。そして、最も移動コストが小さくなるエリアＢの境界ノードまでのリンクの組み合わせを、境界ノードａからエリアＢまでのエリア間経路として決定することにより算出できる。
【００２６】
具体例を図５で示す。エリア３０２の境界ノードＹ０１１からエリア３０４までのエリア間経路を求めるとする。この場合、境界ノードＹ０１１からエリア３０４の全境界ノード、つまり境界ノードＹ２０７・Ｙ２０８・Ｙ０３５・Ｙ０３６への移動コストを、ダイクストラ法を用いて算出する。この例ではエリア３０４の境界ノードＹ２０８への移動コストが最も小さくなるため、境界ノードＹ０１１から境界ノードＹ２０８までのリンクの組み合わせであるエリア間経路５０２が選択された。なお、前述したように、このエリア間経路５０２は、学習経路としてエリア間経路記憶部６０に、図６の境界ノード番号がＹ０１１のレコードとして格納される。エリア間経路５０４、エリア間経路５０６についても同様である。
【００２７】
エリア特定部７０は、地図情報記憶部５０を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定する。図７は、始点７０２と終点７０４とが、地図上に指定された状態を表す図である。このとき、エリア特定部７０は、始点７０２を含む第１エリアとしてエリア３０２を、終点７０４を含む第２エリアとしてエリア３０４を特定する。具体的には、エリアの範囲は経度および緯度の座標情報で特定できるため、始点・終点の経度および緯度等の座標情報をもとに、エリア特定部７０は、始点または終点を含むエリアを特定することができる。
【００２８】
経路導出部８０は、第１エリアと第２エリアを結ぶ経路情報を、エリア間経路記憶部６０より取得して、始点と終点を結ぶ経路を導出する。本実施の形態に係る経路算出装置１０では、経路導出部８０は、始点７０２から第１エリアの各境界ノードまでの移動コストと、第１エリアと第２エリア間の移動コストと、第２エリア内の各境界ノードから終点７０４までの移動コストとを考慮して、ダイクストラ法を用いて始点と終点との経路を導出する。
【００２９】
図８は、経路導出部８０が経路を導出するときの考え方を示す。同図では、図７の始点７０２と終点７０４間に存在するリンクを示している。本実施の形態において、それぞれのエリア間経路は事前に算出されているため、同図では、エリア間経路は一つのリンクとして考えればよいことを示している。この例のエリア間経路は、図６で示したように３つに限定され、エリア間経路記憶部６０に格納されている。エリア間経路は、リンクの組み合わせとして格納されているため、経路導出部８０は、それぞれのリンクの移動コストを地図情報記憶部５０より取得して和算することで、エリア間経路全体の移動コストを算出できる。また、第１エリア内および第２エリア内の各リンクの移動コストは図４で示したように地図情報記憶部５０に格納されているため、経路導出部８０はそれぞれのリンクの移動コストを取得できる。始点から第１エリア内の近くのノード（以下、「近傍ノード」と呼ぶ。）への移動コストは、始点（現在位置）から第１エリア内のノードへの距離等に基づき算出できる。終点から第２エリア内の近傍ノードへの移動コストを算出する場合も同様である。
【００３０】
図９は、経路導出部８０が経路を導出する手順の一例を示すフローチャートである。経路導出部８０は、まず、始点から第１エリアの近傍ノードまでの移動コストを算出する（Ｓ２）。次に、終点から第２エリアの近傍ノードまでの移動コストを算出する（Ｓ４）。そして、第１エリア内の各リンクの移動コストを、地図情報記憶部５０から取得する（Ｓ６）。ここで、エリア特定部７０の出力結果に基づき、第１エリアと第２エリアは同一か、つまり始点と終点が同一のエリアに存在するかを判定する（Ｓ８）。同一の場合（Ｓ８のＹ）、エリア内のリンクと各リンクの移動コストは既に取得済みであるため、ダイクストラ法を用いて、始点から終点までの最小の移動コストとなる経路を算出する（Ｓ１６）。第１エリアと第２エリアとが異なる場合（Ｓ８のＮ）、第２エリア内の各リンクの移動コストを、地図情報記憶部５０から取得する（Ｓ１０）。次に、第１エリアと第２エリアのエリア間経路を、エリア間経路記憶部６０から取得する（Ｓ１２）。そして、エリア間経路に含まれるそれぞれのリンクの移動コストを、地図情報記憶部５０から取得し、移動コストを和算して、エリア間経路全体の移動コストを算出する（Ｓ１４）。これで、始点から終点までに存在するリンクと各リンクの移動コストが求まったため、最後に、ダイクストラ法を用いて、始点から終点までの最小の移動コストとなる経路を算出する（Ｓ１６）。
【００３１】
一般にダイクストラ法を用いた場合、その計算量はノード数をｎとするとＯ（ｎ＾２）であることが知られている。本実施の形態に係る経路算出装置１０では、エリア間経路を事前に学習経路として記憶しておくことで、図８で示すように実質的にノード数が大幅に削減され、ダイクストラ法を用いた経路計算の時間が大幅に短縮される。その結果、例えばユーザからの経路算出要求に対して、迅速なレスポンスが可能となる。
ここでさらに、前述した学習経路を作成する上での課題（１）および（２）の解決について考察する。
【００３２】
（１）膨大な記憶容量の必要性
ノード間経路は全てのノード間について持つわけではなく境界ノード間のみ、しかも特定のエリアの１つの境界ノードと他のエリアの全境界ノードのうち最小の移動コストとなる組み合わせのみエリア間経路として保持するため、必要な記憶容量は大幅に削減される。
（２）膨大な事前計算量の必要性
エリア間経路の計算は全てのノード間について行うわけではなく、特定のエリアの境界ノード毎に、他の特定のエリアの境界ノードについて、１度ダイクストラ法での経路計算を行い、それを他のエリアとの組み合わせ数分繰り返すに過ぎない。したがって、全ノード間の経路を計算するのと比較して、必要な事前計算量も大幅に削減される。
このように、本実施の形態に係る経路算出装置１０では、学習経路の事前計算により、経路の算出時間を大幅に短縮するとともに、学習経路を作成する上での課題を解決している。なお、課題（３）の解決については後述する。
【００３３】
本実施の形態にかかる経路算出装置１０は、さらに、移動コスト調整部９０を備えてもよい。前述した受信部３０が交通情報提供システムから交通情報を受け付けると、移動コスト調整部９０は、地図情報記憶部５０が格納するリンクのうち、その交通情報の影響を受けるリンクの移動コストを変更する。例えば、渋滞が発生した場合には、その渋滞により影響を受けるリンクの移動コストを大きくし、渋滞が解消した場合には逆に、移動コストを小さくする。次回経路算出を行うときには、最新の交通情報が移動コストとして反映されているため、最新の交通事情を加味した上で、最小の移動コストとなる経路の算出ができ、ユーザの利便性の向上を実現する。
【００３４】
経路算出装置１０は、さらに、移動コスト調整部９０が、交通情報に基づき各リンクの移動コストを変更した後で、ユーザの現在位置から終点までの経路を再度算出してもよい。経路の再算出は、ユーザからの明示的な指示を受けて行ってもよいし、経路算出装置１０が自律的に行ってもよい。経路算出装置１０が自律的に経路を再算出する例として、経路算出装置１０は、経路の再算出の要否を判定するための閾値を予め用意し、移動コスト調整部９０により調整された移動コストの変動の幅がこの閾値を上回る場合に、経路を再算出してもよい。これにより、最新の交通情報を加味した上で、最小の移動コストとなる経路をユーザに対し提示することができる。
【００３５】
図１０は、交通情報に基づく経路の変更例を示す。例えば、ユーザがエリア間経路５０２にしたがって境界ノードＹ１０６・ノードＸ０７０３間を移動中に、将来通行予定の境界ノードＹ０３３・ノードＸ０８０３間に渋滞が発生したとする。このとき、その渋滞情報を受信部３０が受け付け、移動コスト調整部９０は、境界ノードＹ０３３・ノードＸ０８０３間のリンクの移動コストを大きくする。
【００３６】
次に、エリア特定部７０は、現在位置を含む第１エリア、つまり図１０のエリア３０８と、終点を含む第２エリア、つまりエリア３０４を、特定する。そして、経路導出部８０は、前述したように、エリア間経路記憶部６０からエリア３０８とエリア３０４間のエリア間経路を取得する。ここで、エリア間経路の一つが境界ノードＹ０３３・ノードＸ０８０３・ノードＸ０８０６・境界ノードＹ２０８だったとする。この場合、このエリア間経路は一部のリンクの移動コストが大きくなっているため、経路導出部８０は、ダイクストラ法を用い、代替の経路を算出してもよい。例えば、経路導出部８０は、移動コストが調整されたリンクを含むエリアでは、エリア間経路記憶部６０から取得したエリア間経路を使わずに、そのエリアに含まれる全リンクの移動コストを考慮して、ダイクストラ法により経路を導出してもよい。図１０では、代替の経路として、境界ノードＹ０３３・ノードＸ０８０１・ノードＸ０８０４・境界ノードＹ２０８が選択されたイメージを示している。
【００３７】
この例で示したように、代替の経路を算出可能であるのは、エリア間経路記憶部６０が、エリア間経路をリンクの組み合わせとして記憶しているからである。前述したように、移動コスト調整部９０は、交通情報に基づき影響を受ける個々のリンクの移動コストを変更し、経路導出部８０はダイクストラ法を用いて最小の移動コストとなる経路をユーザに再度提示することができる。これに対して、エリア間経路情報を、境界ノードから境界ノードまで固定的に保持していた場合には、ここで示したような最新の交通情報の反映は困難であるし、代替経路の算出も困難である。本実施の形態にかかる経路算出装置１０は、エリア間経路情報をリンクの組み合わせとして持つことで、前述した課題（３）、つまり事前に固定的な学習経路を持つことによる弊害を解決している。
【００３８】
なお、経路算出装置１０が、移動コスト調整部９０を備えない場合にも、エリア間経路記憶部６０が、エリア間経路をリンクの組み合わせとして保持することによって、より柔軟な経路算出を実現し、ユーザの利便性を高めるという効果がある。例えば、ユーザが学習経路の一部を何らかの事情により通行したくない、もしくは通行できない、迂回したい場合や、通行止め等の交通事情により迂回せざるを得ない場合を考える。このとき、経路導出部８０は、特定のリンクが無いものとして、その他のノード間のリンクの移動コストをもとに、ダイクストラ法を用いて次善の経路をユーザに提示することができる。または、経路算出装置１０が提示した経路をユーザがはずれてしまった場合に、ユーザの現在位置から終点までの経路を再度算出して提示することもできる。
このように、エリア間経路記憶部６０が、エリア間経路をリンクの組み合わせとして保持することによって、経路算出時の計算量を減らして迅速に経路算出を行うことと、柔軟な経路算出を実現することとを両立して、ユーザの利便性を高める。さらに、移動コスト調整部９０を備えることで、最新の交通情報を経路の導出に反映できるため、ユーザに対しより適切な経路の提示を可能とし、ユーザの利便性のさらなる向上を実現する。
【００３９】
また、本実施形態の説明において、学習経路として事前に算出されるエリア間経路は、あるエリアＡの１つの境界ノードａから、他のエリアＢの全境界ノードまでの移動コストを、ダイクストラ法を用いて算出して、最も移動コストが小さくなるエリアＢの境界ノードまでのリンクの組み合わせを、境界ノードａからエリアＢまでのエリア間経路とした。変形例として、ダイクストラ法を用いて算出した、エリアＡの１つの境界ノードａから、他のエリアＢの全境界ノードまでの移動コストの、全てのリンクの組み合わせを、学習経路として保持してもよい。こうすることにより、エリアＡの始点または終点と、エリアＢの始点または終点の位置に応じて、より移動コストの小さなエリア間経路を選択しやすくなる。例えば、図５において、エリア３０２のノードＸ０１０２から、エリア３０４のＸ１２０１までの経路を算出する場合を考える。このとき、エリア３０４内部での移動コストを考慮すると、Ｙ０１１からＹ２０８のエリア間経路を使うよりも、Ｙ０１１からＹ２０７のエリア間経路を使った方が、全体としての移動コストは小さくなる可能性がある。本変形例によれば、境界ノードの組み合わせ毎に、エリア間経路を保持するため、より移動コストの小さな経路を導出しやすくなる。
【００４０】
（第２の実施形態）
本発明の第２の実施形態にかかる経路算出装置は、前述の第１の実施形態にかかる経路算出装置と、記憶されるエリア間経路のデータ構造の点、および、経路導出の点において異なる。本実施形態の説明において、第１の実施形態と同じものには、第１の実施形態の説明において付与した符号と同じ符号を付与している。また、同一の符号が付与されたものに関する詳細な説明は省略する。
【００４１】
図１１は、本発明の第２の実施形態にかかる経路算出装置の構成例を示す機能ブロック図である。経路算出装置１０００は、ユーザインタフェイス部２０と、受信部３０と、現在位置導出部４０と、地図情報記憶部５０と、エリア特定部７０と、移動コスト調整部９０と、エリア間経路記憶部１０６０と、経路導出部１０８０とを備える。以下、エリア間経路記憶部１０６０と、経路導出部１０８０とについて説明する。
【００４２】
エリア間経路記憶部１０６０は、エリア間経路記憶部６０と同様に、エリア間経路をリンクの組み合わせとして格納する。エリア間経路記憶部１０６０は、特定のエリアの１つの境界ノードと他のエリアの全ての境界ノードとの組み合わせ毎に、所定の条件に基づいて１つの経路が決定されてもよい。ここで、所定の条件は、距離・移動時間・通行のための費用等、つまり移動コストに基づく条件であってもよい。以下では、例示として、移動コストが最も小さいエリア間経路が選定されるものとする。
【００４３】
図１２は、エリア間経路のイメージ図である。同図において、エリア３０２の境界ノードＹ０１１から、エリア３０４の各境界ノードへのエリア間経路は、Ｙ０１１からＹ２０７まで、Ｙ０１１からＹ２０８まで、Ｙ０１１からＹ０３５まで、Ｙ０１１からＹ０３６までの、４本が導出されている。これらのエリア間経路は、境界ノードＹ０１１から、境界ノードＹ２０７・Ｙ２０８・Ｙ０３５・Ｙ０３６までの、リンクの組み合わせに対してダイクストラ法を用いることで、移動コストの合計が相対的に小さくなるリンクの組み合わせとして導出されたものである。
【００４４】
同様に、図１３も、エリア間経路のイメージ図である。同図において、エリア３０２の境界ノードＹ１０２から、エリア３０４の各境界ノードへのエリア間経路は、前述の方法により算出され、Ｙ１０２からＹ２０７まで、Ｙ１０２からＹ２０８まで、Ｙ１０２からＹ０３５まで、Ｙ１０２からＹ０３６までの、４本が導出されている。さらに、図１４も、エリア間経路のイメージ図である。同図において、エリア３０２の境界ノードＹ１０１から、エリア３０４の各境界ノードへのエリア間経路は、前述の方法により算出され、Ｙ１０１からＹ２０７まで、Ｙ１０１からＹ２０８まで、Ｙ１０１からＹ０３５まで、Ｙ１０１からＹ０３６までの、４本が導出されている。
【００４５】
図１５も、エリア間経路のイメージ図である。同図では、図１２から図１４まで説明した、エリア３０２からエリア３０４までの、エリア間経路が組み合わされた状態を示している。エリア間経路記憶部１０６０は、各エリアの組み合わせ毎に、図１５で例示したリンクの組み合わせを、ネットワーク型データモデルとして記憶する。
【００４６】
図１６は、エリア間経路記憶部１０６０が格納するエリア間経路のデータ構造を例示する。同図では、図１５で示したエリア間経路が、出発エリア番号が３０２で、目標エリア番号が３０４の組み合わせで特定されるレコードとして保持されることを示している。エリア間経路、つまりリンクの組み合わせは、ネットワーク型データモデルとして保持される。図１６はデータ構造を模式的に示したものであり、実際には、個々のノードをレコードとし、そのノードと接続されるノードのポインタを、レコードに埋め込むことで実現されてもよい。また、ＤＢＭＳ（database management system）に保持させることで実現されてもよく、その他の公知の技術により実現されてもよい。なお、エリア間経路記憶部１０６０は、出発エリアと目標エリアとの組み合わせ毎に、図１６で示したようなエリア間経路を保持する。図１１に戻る。
【００４７】
経路導出部１０８０は、経路導出部８０と同様に、始点を含む第１エリアと、終点を含む第２エリアを結ぶ経路情報を、エリア間経路記憶部１０６０より取得して、始点と終点とを結ぶ経路を導出する。図１７は、始点７０２と終点７０４とが、地図上に指定された状態を表す。経路導出部１０８０は、始点７０２から第１エリアの各境界ノードまでの移動コストと、第１エリアと第２エリア間の移動コストと、第２エリア内の各境界ノードから終点７０４までの移動コストとを考慮して、ダイクストラ法を用いて始点と終点との経路を導出する。
【００４８】
図１８は、経路導出部１０８０が経路を導出するときの考え方を示す。同図では、図１７の始点７０２と終点７０４間に存在するリンクを示している。同図において、エリア間のノードは模式的に示しているが、実際には、経路導出部１０８０は、エリア間経路記憶部１０６０から、出発エリア番号と目標エリア番号をキーにして、エリア間経路であるリンクの組み合わせを取得する。この例では、出発エリアはエリア３０２であり、目標エリアはエリア３０４であるため、図１６で示したエリア間経路を取得する。エリア間経路は、リンクの組み合わせとして格納されているため、経路導出部１０８０は、それぞれのリンクの移動コストを地図情報記憶部５０より取得して、各リンクに設定する。また、第１エリア内、第２エリア内の各リンクの移動コスト、および、始点または終点から近傍ノードへの移動コストについては、第１の実施形態と同様である。
【００４９】
図１９は、経路導出部１０８０が経路を導出する手順の一例を示すフローチャートである。なお、同図において、Ｓ２２からＳ３０までは、図９で説明したＳ２からＳ１０までと、それぞれ同様であるため、同図のＳ３２以降について説明する。経路導出部１０８０は、第１エリアと第２エリアのエリア間経路を、エリア間経路記憶部１０６０から取得する（Ｓ３２）。次に、エリア間経路のそれぞれリンクの移動コストを、地図情報記憶部５０から取得する（Ｓ３４）。これで、始点から終点までに存在するリンクと各リンクの移動コストが求まったため、最後に、ダイクストラ法を用いて、始点から終点までの最小の移動コストとなる経路を算出する（Ｓ３６）。
【００５０】
本実施の形態に係る経路算出装置１０００でも、第１の実施形態と同様に、エリア間経路を事前に学習経路として記憶しておくことで、図１６および図１８で示すように実質的にノード数が大幅に削減され、ダイクストラ法を用いた経路計算の時間が大幅に短縮される。その結果、例えばユーザからの経路算出要求に対して、迅速なレスポンスが可能となる。また、本実施形態では、特定のエリアＡの１つの境界ノードから、他のエリアＢの全境界ノードまでの移動コストを、ダイクストラ法を用いて算出して、その全てのリンクの組み合わせを学習経路として保持する。したがって、第１の実施形態の変形例において説明したように、エリアＡの始点または終点と、エリアＢの始点または終点の位置に応じて、より移動コストの小さなエリア間経路を選択しやすくなっている。
【００５１】
ここでさらに、前述した学習経路を作成する上での課題（１）および（２）の解決について考察する。
（１）膨大な記憶容量の必要性
ノード間経路は全てのノード間について持つわけではなく、境界ノード間のみのリンクの組み合わせをエリア間経路として保持するため、必要な記憶容量は大幅に削減される。境界ノード間のみで、かつ、特定のエリアの１つの境界ノードと他のエリアの全境界ノードのうち最小の移動コストとなる組み合わせのみエリア間経路として保持する第１の実施形態と比べると必要な記憶容量は大きく増加するようにも思われる。図５において、エリア３０２からエリア３０４間のエリア間経路として、３本のエリア間経路を記憶していた第１の実施形態と比較すると、第２の実施形態は図１５で示すように、境界ノード数分の組み合わせである１２本分、つまり４倍のエリア間経路を記憶するようにも思われるからである。しかし、図５と図１５を対比すれば明らかなように、記憶すべきリンクの組み合わせは、４倍にはならない。これは、移動コストが小さい経路、例えば移動時間が短い経路は、道幅の広い主要幹線道路等であるため、それぞれのエリア間経路におけるリンクの多くが共通するからである。そのため、将来的に境界ノードが増えた場合にも、追加して記憶すべきリンク数は最小限となる。したがって、本実施形態の経路算出装置は記憶容量の課題を解決している。
【００５２】
（２）膨大な事前計算量の必要性
エリア間経路の計算は全てのノード間について行うわけではなく、特定のエリアの境界ノード毎に、他の特定のエリアの境界ノードについて、１度ダイクストラ法での経路計算を行い、それを他のエリアとの組み合わせ数分繰り返すに過ぎない。したがって、全ノード間の経路を計算するのと比較して、必要な事前計算量も大幅に削減される。なお、１度ダイクストラ法での経路計算を行えば、特定のエリアの特定の境界ノードから、他の特定のエリアの全ての境界ノードまでの経路が算出できるため、事前計算量については、第１の実施形態と本実施形態とは同じである。
このように、本実施の形態に係る経路算出装置１０００でも、学習経路の事前計算により、経路の算出時間を大幅に短縮するとともに、学習経路を作成する上での課題を解決している。
【００５３】
また、本実施の形態にかかる経路算出装置１０００も、第１の実施形態と同様に、移動コスト調整部９０を備えてもよい。移動コスト調整部９０を備えることによる、構成、効果、および課題（３）の解決については、第１の実施形態と同様である。また、経路算出装置１０が、移動コスト調整部９０を備えない場合にも、エリア間経路記憶部６０が、エリア間経路をリンクの組み合わせとして保持することによって、より柔軟な経路算出を実現し、ユーザの利便性を高めるという効果についても、第１の実施形態と同様である。特に、本実施形態の場合には、特定のエリアの境界ノードから他のエリアの全ての境界ノードまでのエリア間経路を、学習経路として事前に記憶している。これにより、学習経路の１つが、例えば通行止めにより通行できなくなった場合でも、他の学習経路を使うことで迂回路算出のためのノード数を低減でき、より迅速に迂回路を導出できる。
【００５４】
（第３の実施形態）
これまでは、第１および第２の実施形態として、現在主流のカーナビゲーション装置のような、記憶部や経路導出部を含んだ経路算出装置について説明した。以下、本発明の第３の実施形態として、経路算出システムについて説明する。経路を一元的に算出するサーバが、ＡＳＰ（Application Service Provider）として、ユーザに対し経路算出サービスを提供する形態である。
【００５５】
図２０は、本発明の第３の実施形態に係る経路算出システムの構成例を示す機能ブロック図である。経路算出システムは、経路算出サーバ１００、および経路表示端末１２０、を備える。経路算出サーバ１００と経路表示端末１２０は、インターネット・ＷＡＮ・ＬＡＮ・携帯電話ネットワーク等を含む通信ネットワーク１９０を介して接続される。なお、同図において、第１および第２の実施形態と同じ機能ブロックについては、同一の符号を使用している。以下、第１および第２の実施形態と同じ機能ブロックについての説明は省略し、第１および第２の実施形態との違いについて主に説明する。
【００５６】
経路算出サーバ１００は、経路算出サービスを提供するサーバであり、受信部３０、地図情報記憶部５０、エリア間経路記憶部１０６０、エリア特定部７０、経路導出部１０８０、移動コスト調整部９０、通信部１１０を有する。通信部１１０は、通信ネットワーク１９０を介して経路表示端末１２０からの経路算出要求情報を受け付ける。経路算出サーバ１００は、その要求に基づき経路を算出し、経路情報を経路表示端末１２０に出力する。他の機能ブロックについては、第１および第２の実施形態の経路算出装置と同様である。なお、エリア間経路記憶部１０６０は、第１の実施形態のエリア間経路記憶部６０でもよく、経路導出部１０８０は、第１の実施形態の経路導出部８０でもよい。
【００５７】
経路表示端末１２０は、主にユーザインタフェイスを担当する端末であり、受信部３０、現在位置導出部４０、受付部１３０、表示部１４０、通信部１５０、を有する。受付部１３０は、ユーザからの経路を算出する始点・終点等の入力を受け付け、経路算出要求情報を作成する。始点については、第１および第２の実施形態と同様に、ＧＰＳ衛星からの信号を受信部３０が受け付け、現在位置導出部４０が現在位置を導出して始点としてもよい。通信部１５０は、通信ネットワーク１９０を介して、経路算出要求情報を経路算出サーバ１００に出力し、算出された経路情報を経路算出サーバ１００から受け取る。表示部１４０は、経路情報を画面に表示させる。
【００５８】
通信ネットワーク１９０のブロードバンド化が進む現在では、機器間の物理的な位置の影響をほとんど受けず、通信ネットワーク１９０を介して大量の情報を高速にやりとりできる。そのため、ユーザインタフェイスを担当する経路表示端末１２０と、経路算出を担当する経路算出サーバ１００が離れた場所に存在しても、通信のための待ち時間の発生は少なく、ユーザの利便性を損なうことは少ない。経路表示端末１２０側では、地図情報記憶部５０やエリア間経路記憶部６０等を保持する必要が無く、自ら経路算出を行わないため、高性能のハードウェアを必要としない。一方で、一元的に経路算出を担当する経路算出サーバ１００側では、経路表示端末１２０とは異なりハードウェアの物理的な制限を受けにくいため、経路算出の性能向上も図りやすい。このように、第３の実施形態においては、通信ネットワーク１９０を仲介として、経路表示端末１２０と経路算出サーバ１００との最適な役割分担を実現する。
【００５９】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００６０】
本発明の実施形態の説明においては、地図を分割するエリアの大きさは全て同じ長方形状であったが、変形例として、交通量がより大きい都市部におけるエリアの大きさは、他の地域におけるエリアの大きさより小さくてもよい。あるいは、道路の密度が高い都市部におけるエリアの大きさは、他の地域におけるエリアの大きさより小さくてもよい。
【００６１】
エリアの大きさが一定である場合、交通量が多い都市部や道路密度が高い都市部におけるエリアの境界ノードの個数は、他の地域におけるエリアの境界ノードの個数よりも相対的に多くなる。しかし、始点から終点への経路を求める場合、境界ノードの個数は、すなわちエリア間経路の個数となるため、経路算出においては境界ノードの個数は少ない方が望ましい。したがって、都市部におけるエリアの大きさを、他の地域におけるエリアの大きさよりも小さくすることで、都市部におけるエリアの境界ノード数を減らすことができ、経路算出の時間を短縮することができる。
【００６２】
また、本実施の形態に係る経路算出装置１０、または経路算出装置１０００では、ダイクストラ法を用いて、最小の移動コストとなる経路を算出しているが、これは例示であり、最短経路問題を解く他のアルゴリズム、例えばワーシャル−フロイド法等、を用いてもよい。この場合にも、前述の実施の形態と同様の効果を得ることができる。
【図面の簡単な説明】
【００６３】
【図１】本発明の第１の実施形態に係る経路算出装置の構成例を示す機能ブロック図である。
【図２】地図のイメージ図である。
【図３】複数のエリアに分割された地図情報のイメージ図である。
【図４】リンク情報のデータ構造を示す図である。
【図５】エリア間経路のイメージ図である。
【図６】エリア間経路のデータ構造を例示する図である。
【図７】始点と終点とが地図上に指定された状態を示す図である。
【図８】経路導出部が経路を導出するときの考え方を示す図である。
【図９】経路導出部が経路を導出する手順の一例を示すフローチャートである。
【図１０】交通情報に基づく経路の変更例を示す図である。
【図１１】本発明の第２の実施形態に係る経路算出装置の構成例を示す機能ブロック図である。
【図１２】エリア間経路のイメージ図である。
【図１３】エリア間経路のイメージ図である。
【図１４】エリア間経路のイメージ図である。
【図１５】エリア間経路のイメージ図である。
【図１６】エリア間経路記憶部が格納するエリア間経路のデータ構造を例示する図である。
【図１７】始点と終点とが地図上に指定された状態を示す図である。
【図１８】経路導出部が経路を導出するときの考え方を示す図である。
【図１９】経路導出部が経路を導出する手順の一例を示すフローチャートである。
【図２０】本発明の第３の実施形態に係る経路算出システムの構成例を示す機能ブロック図である。
【符号の説明】
【００６４】
１０ 経路算出装置、２０ ユーザインタフェイス部、３０ 受信部、４０ 現在位置導出部、５０ 地図情報記憶部、６０ エリア間経路記憶部、７０ エリア特定部、８０ 経路導出部、９０ 移動コスト調整部、１００ 経路算出サーバ、１１０ 通信部、１２０ 経路表示端末、１３０ 受付部、１４０ 表示部、１５０ 通信部、１９０ 通信ネットワーク、２０２ 地図の全体領域、２０４ ノード、２０６ リンク、３０２ エリア、３０４ エリア、３０６ 境界ノード、３０８ エリア、５０２ エリア間経路、５０４ エリア間経路、５０６ エリア間経路、７０２ 始点、７０４ 終点、１０００ 経路算出装置、１０６０ エリア間経路記憶部、１０８０ 経路導出部。
【技術分野】
【０００１】
本発明は、経路を算出する技術に関し、特に、地図情報をもとに経路を算出する経路算出装置、経路算出システム、および経路算出方法に関する。
【背景技術】
【０００２】
従来、経路算出装置においては、例えばダイクストラ法を用いて経路計算を行う手法が知られているが、経路計算の対象となる領域が広い場合には、経路計算に長い時間がかかるという課題がある。この課題を解決するために、本出願人は以下で示す特許文献に係る経路算出装置を開示している。
【０００３】
この経路算出装置では、地図を所定のメッシュに分割し、主要幹線道路がそのメッシュに出入りする箇所を境界ノードとする。そして、その境界ノード間の移動コストを、メッシュに対応付けて、あらかじめ記憶しておく。一方で、メッシュ内部をさらに細メッシュに分割し、メッシュ内部のノード間の移動コストを、細メッシュに対応付けて、あらかじめ記憶しておく。始点と終点が指定されると、始点が存在するメッシュと終点が存在するメッシュとの間の移動コストは、これらの間に存在するメッシュ（以下、「中間メッシュ」と呼ぶ。）の境界ノード間の移動コストを和算して算出される。また、始点とそのメッシュの境界ノード間、終点とそのメッシュの境界ノード間の移動コストは、細メッシュに含まれるノード間の移動コストをもとに、ダイクストラ法を用いて算出される。そして、これらの移動コストを和算して、始点から終点までの最終的な移動コストが算出される。
【特許文献１】特開２００５−２２８０１１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
経路算出装置においては、経路算出に要する時間は短いことが望ましく、そのためには、経路算出時の計算量は抑制されることが望ましい。
【０００５】
本発明はこうした状況を鑑みてなされたものであり、その目的は、経路算出時の計算量を抑制しながら、ユーザにとって利便性の高い経路情報を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は、経路算出装置に関する。この経路算出装置は、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部と、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部と、地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部と、第１エリアと第２エリアを結ぶ経路情報を、エリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出部と、を備える。
【０００７】
本明細書の「ノード」とは、地図のデータ内で決定された特定の地点であり、例えば、道路の交差点、道路のエリアへの出入り口、道路の行き止まり、主要な建造物の前等である。また、「リンク」とは、ノード間を結ぶ経路であり、物理的な道路そのものであってもよいが、物理的な道路の形状とは異なり、論理的にノード間の結びつきを示すものであってもよい。
【０００８】
本発明の別の態様は、経路算出システムに関する。この経路算出システムは、経路算出サーバと、経路表示端末と、を備える。この経路算出サーバは、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部と、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部と、経路を算出する始点および終点を指定する経路算出要求情報をもとに、地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部と、第１エリアと第２エリアを結ぶ経路情報を、エリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出部と、経路表示端末から前記経路算出要求情報を受け付け、また、前記経路表示端末に導出した経路を出力する通信部と、を有する。また、経路表示端末は、ユーザから、経路算出要求情報の指定入力を検出する受付部と、経路算出要求情報を経路算出サーバに出力し、また、経路算出サーバにより導出された経路を取得する通信部と、取得した経路を画面表示させる表示部と、を有する。
【０００９】
本発明のさらに別の態様は、経路算出方法に関する。この経路算出方法は、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定ステップと、第１エリアと第２エリアを結ぶ経路情報を、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出ステップと、を備える。
【００１０】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、システム、プログラム、プログラムを格納した記憶媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１１】
本発明によれば、経路算出時の計算量を抑制しながら、ユーザにとって利便性の高い経路情報を提供できる。
【発明を実施するための最良の形態】
【００１２】
従来、最短経路を求める方法として、例えばダイクストラ法を用いて経路計算を行う手法が知られている。ダイクストラ法とは、ある領域が与えられているときに、領域中の任意のノードから他の全てのノードまでの最短経路を決定する計算方法である。計算の初期状態では始点ノードの最短路のみが確定している状態から始まり、最短路が確定したノードを順次最短経路木、つまり、あるノードから他のノードへの最短路で使われているノード・リンクからなる木構造のデータに加えていく。これにより、最終的に、始点ノードから他の全てのノードに対する最短路が決定する。ダイクストラ法を用いた場合の計算量は、Ｏ記法で示すと、一般にＯ（ｎ＾２）となる。ここで、ｎは領域内の全ノード数、＾はベキ乗を表す。
【００１３】
前述の計算量から明らかなように、ダイクストラ法を用いて経路計算を行うとき、経路計算の対象となる領域が広い、つまり多数のノードが含まれる場合には、経路計算に長い時間がかかるという課題がある。したがって、例えば、ユーザがカーナビゲーション装置に対して、現在位置から離れた目標地点までの経路設定を要求した場合に、長時間の待ち時間が発生する可能性がある。
【００１４】
本発明者は、事前にノード間の最短経路（以下、「ノード間経路」と呼ぶ。）を計算しておき、カーナビゲーション装置のような経路算出装置に、このノード間経路を記憶させておくことで、経路計算の時間を短縮できると考えた。経路算出装置に記憶されたノード間経路のことを、以下、「学習経路」と呼ぶことにする。全てのノードについて、学習経路を作成できれば、学習経路を用いる場合の計算量はＯ（１）であるため、大幅な計算量の削減となり、その結果、ユーザの要求に対するレスポンスタイムの向上も実現できる。
【００１５】
本発明者は、全ノードの学習経路の作成にあたり、以下の３つの課題の存在を知見した。
（１）膨大な記憶容量の必要性
領域内のノード数をｎとすると、単純に全てのノード間経路を算出した場合、ノード間経路数は（ｎ＾２）本存在する。例えば、日本全国の地図の場合、ノード数（ｎ）は、約８００万個存在するため、膨大な数のノード間経路が存在し、現実的な記憶容量を遙かに上回ってしまう。
（２）膨大な事前計算量の必要性
ダイクストラ法で計算した場合、あるノードから他の全てのノードまでの最短経路が１回の計算で求まり、この所要時間は５〜６分である。前述のように、日本全国の地図の場合、ノード数は約８００万個存在するため、単純にノード数を積算すると、事前計算に要する時間は非常に長期間となり、現実的に可能な事前計算量を遙かに上回ってしまう。
（３）事前に固定的な学習経路を持つことによる弊害
実際の交通状況には、事故渋滞や工事による通行止めの発生など、事前に算出した学習経路をそのまま適用することが妥当でない場合がある。
以下、本発明の実施形態として、これらの課題を解決する経路算出装置、および経路算出システムを説明する。
【００１６】
（第１の実施形態）
図１は、本発明の第１の実施形態に係る経路算出装置１０の構成例を示す機能ブロック図である。経路算出装置１０は、ユーザインタフェイス部２０と、受信部３０と、現在位置導出部４０と、地図情報記憶部５０と、エリア間経路記憶部６０と、エリア特定部７０と、経路導出部８０と、移動コスト調整部９０とを備える。これらの構成は、ハードウェアコンポーネントでいえば、任意のコンピュータのＣＰＵ、メモリ、メモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。図１１および図２０の機能ブロック図においても同様である。
【００１７】
ユーザインタフェイス部２０は、ユーザからの、経路を算出する終点の指定情報を含む経路算出要求情報の入力を受け付ける。経路算出要求情報には、経路を算出する始点の指定情報は必須ではない。始点がユーザにより明示的に指定された場合には、経路算出装置１０は、ユーザの現在位置にかかわらず、指定された始点から終点までの経路を算出する。始点が明示的に指定されない場合には、経路算出装置１０は、ユーザの現在位置を始点として指定された終点までの経路を算出する。
【００１８】
受信部３０は、ＧＰＳ（Global Positioning System）や、ＶＩＣＳ（Vehicle Information and Communication System）（登録商標）といった交通情報提供システムからの情報を受け付ける。例えば、複数のＧＰＳ衛星から時刻情報を含む電波信号を受け付ける。また、交通情報提供システムからは、渋滞、所要時間、事故・故障車・工事、速度規制・車線規制等の交通情報を受け付ける。
現在位置導出部４０は、複数のＧＰＳ衛星からの電波信号をもとに、現在位置を導出する。現在位置を導出する方法は、既知の測位方法を用いてよい。また現在位置導出部４０が導出した現在位置を、経路を算出する始点としてもよい。
移動コスト調整部９０については、後述する。
【００１９】
地図情報記憶部５０は、地図を、それぞれが座標情報で特定される複数のエリアに分割し、複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報（以下、「リンク情報」と呼ぶ。）とを、それぞれのエリアに対応付けて格納する。なお、リンク情報には少なくともノード間の距離が含まれることとする。図２は、地図のイメージ図である。同図では、地図の全体領域２０２の中に、ノード２０４と、ノード間の経路であるリンク２０６が存在することを示している。地図情報記憶部５０は、全体領域２０２を分割したエリアを特定する座標情報、例えば経度情報や緯度情報を保持する。
【００２０】
図３は、地図情報記憶部５０が格納する複数のエリアに分割された地図情報のイメージ図である。同図では、地図の全体領域が複数のエリア、例えばエリア３０２、エリア３０４等に分割された状態を示している。各エリアのノードには、地図全体における一意の識別番号が振られており、さらに、エリアの境界に位置する境界ノード、例えば境界ノード３０６が決められている。なお、図３は、理解の便宜のためのイメージであり、地図情報記憶部５０は、実際には、テーブル等でこれらのエリア情報・ノード情報・境界ノード情報を管理してもよい。
【００２１】
図４は、地図情報記憶部５０が格納するリンク情報のデータ構造を示す。図３のエリア３０２については、そのエリアにおいてリンクで接続されたノードの組み合わせ数分のレコードが存在する。移動コストは、ノード間の単なる距離でもよいが、ノード間の移動時間、通行のための費用等、またはそれらの組み合わせに基づいて重み付けされたものであってもよい。さらに、車幅や車線数、信号の数、天候など通行のしやすさに応じて調整されてもよい。本明細書の以下においても同様である。
なお、同図では、出発ノードと目標ノードが入れ替わっただけの組、例えば、出発ノード番号Ｘ０１０１・目標ノード番号Ｘ０１０３と、出発ノード番号Ｘ０１０３・目標ノード番号Ｘ０１０１とは別のものとして移動コストを格納している。これらのノードの組について別のものとして取り扱うことで、車線数の違いや、方向による混雑の違いなど、より現実の交通事情に即した移動コストの設定が可能になる。変形例として、出発ノードと目標ノードが入れ替わっただけの、これらのノードの組については、同一のものと取り扱ってもよい。この場合、地図情報記憶部５０が格納するデータ量が削減されるという効果がある。
【００２２】
エリア間経路記憶部６０は、異なるエリアの境界ノード間の経路（以下、「エリア間経路情報」と呼ぶ。）をリンクの組み合わせとして格納する。このエリア間経路は、あるエリアの１つの境界ノードと他のエリアの１つの境界ノードとの間の経路を特定するものであってもよい。さらに、あるエリアの１つの境界ノードと他のエリアとの組み合わせ毎に、所定の条件に基づいて１つの経路が決定されてもよい。ここで、所定の条件は、距離・移動時間・通行のための費用等、つまり移動コストに基づく条件であってもよい。具体的には、移動コストが、特定のエリアの１つの境界ノードと他のエリアとの組み合わせにおいて、最も小さいという条件であってもよく、また所定の閾値よりも小さいという条件であってもよい。以下では、例示として、移動コストが最も小さいエリア間経路が選定されるものとする。
【００２３】
図５は、エリア間経路のイメージ図である。エリア３０２からエリア３０４へのエリア間経路はエリア３０２の境界ノード数分、つまり３本、存在する。同図において、境界ノードＹ０１１とエリア３０４については、エリア間経路５０２で示している。同様に、境界ノードＹ１０２とエリア３０４については、エリア間経路５０４で、境界ノードＹ１０１とエリア３０４については、エリア間経路５０６で示している。
【００２４】
図６は、エリア間経路記憶部６０が格納するエリア間経路のデータ構造を例示する。同図は、例えば図５のエリア間経路５０２の場合、境界ノード番号がＹ０１１のレコードで示されるエリア間経路として保持されることを示している。なお、エリア間経路は、リンクの組み合わせとして格納されている。つまり、図５のエリア間経路５０２の場合、境界ノードＹ０１１とノードＸ０２０１のリンク、ノードＸ０２０１とノードＸ０２０２のリンク・・・、という具合に個々のリンクの組み合わせとなっている。これによる効果は後述する。
【００２５】
エリア間経路は、学習経路として事前に算出して、エリア間経路記憶部６０が記憶しておく。エリア間経路の算出例を以下示す。まず、特定のエリアＡの１つの境界ノードａから、他のエリアＢの全境界ノードまでの移動コストを、ダイクストラ法を用いて算出する。そして、最も移動コストが小さくなるエリアＢの境界ノードまでのリンクの組み合わせを、境界ノードａからエリアＢまでのエリア間経路として決定することにより算出できる。
【００２６】
具体例を図５で示す。エリア３０２の境界ノードＹ０１１からエリア３０４までのエリア間経路を求めるとする。この場合、境界ノードＹ０１１からエリア３０４の全境界ノード、つまり境界ノードＹ２０７・Ｙ２０８・Ｙ０３５・Ｙ０３６への移動コストを、ダイクストラ法を用いて算出する。この例ではエリア３０４の境界ノードＹ２０８への移動コストが最も小さくなるため、境界ノードＹ０１１から境界ノードＹ２０８までのリンクの組み合わせであるエリア間経路５０２が選択された。なお、前述したように、このエリア間経路５０２は、学習経路としてエリア間経路記憶部６０に、図６の境界ノード番号がＹ０１１のレコードとして格納される。エリア間経路５０４、エリア間経路５０６についても同様である。
【００２７】
エリア特定部７０は、地図情報記憶部５０を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定する。図７は、始点７０２と終点７０４とが、地図上に指定された状態を表す図である。このとき、エリア特定部７０は、始点７０２を含む第１エリアとしてエリア３０２を、終点７０４を含む第２エリアとしてエリア３０４を特定する。具体的には、エリアの範囲は経度および緯度の座標情報で特定できるため、始点・終点の経度および緯度等の座標情報をもとに、エリア特定部７０は、始点または終点を含むエリアを特定することができる。
【００２８】
経路導出部８０は、第１エリアと第２エリアを結ぶ経路情報を、エリア間経路記憶部６０より取得して、始点と終点を結ぶ経路を導出する。本実施の形態に係る経路算出装置１０では、経路導出部８０は、始点７０２から第１エリアの各境界ノードまでの移動コストと、第１エリアと第２エリア間の移動コストと、第２エリア内の各境界ノードから終点７０４までの移動コストとを考慮して、ダイクストラ法を用いて始点と終点との経路を導出する。
【００２９】
図８は、経路導出部８０が経路を導出するときの考え方を示す。同図では、図７の始点７０２と終点７０４間に存在するリンクを示している。本実施の形態において、それぞれのエリア間経路は事前に算出されているため、同図では、エリア間経路は一つのリンクとして考えればよいことを示している。この例のエリア間経路は、図６で示したように３つに限定され、エリア間経路記憶部６０に格納されている。エリア間経路は、リンクの組み合わせとして格納されているため、経路導出部８０は、それぞれのリンクの移動コストを地図情報記憶部５０より取得して和算することで、エリア間経路全体の移動コストを算出できる。また、第１エリア内および第２エリア内の各リンクの移動コストは図４で示したように地図情報記憶部５０に格納されているため、経路導出部８０はそれぞれのリンクの移動コストを取得できる。始点から第１エリア内の近くのノード（以下、「近傍ノード」と呼ぶ。）への移動コストは、始点（現在位置）から第１エリア内のノードへの距離等に基づき算出できる。終点から第２エリア内の近傍ノードへの移動コストを算出する場合も同様である。
【００３０】
図９は、経路導出部８０が経路を導出する手順の一例を示すフローチャートである。経路導出部８０は、まず、始点から第１エリアの近傍ノードまでの移動コストを算出する（Ｓ２）。次に、終点から第２エリアの近傍ノードまでの移動コストを算出する（Ｓ４）。そして、第１エリア内の各リンクの移動コストを、地図情報記憶部５０から取得する（Ｓ６）。ここで、エリア特定部７０の出力結果に基づき、第１エリアと第２エリアは同一か、つまり始点と終点が同一のエリアに存在するかを判定する（Ｓ８）。同一の場合（Ｓ８のＹ）、エリア内のリンクと各リンクの移動コストは既に取得済みであるため、ダイクストラ法を用いて、始点から終点までの最小の移動コストとなる経路を算出する（Ｓ１６）。第１エリアと第２エリアとが異なる場合（Ｓ８のＮ）、第２エリア内の各リンクの移動コストを、地図情報記憶部５０から取得する（Ｓ１０）。次に、第１エリアと第２エリアのエリア間経路を、エリア間経路記憶部６０から取得する（Ｓ１２）。そして、エリア間経路に含まれるそれぞれのリンクの移動コストを、地図情報記憶部５０から取得し、移動コストを和算して、エリア間経路全体の移動コストを算出する（Ｓ１４）。これで、始点から終点までに存在するリンクと各リンクの移動コストが求まったため、最後に、ダイクストラ法を用いて、始点から終点までの最小の移動コストとなる経路を算出する（Ｓ１６）。
【００３１】
一般にダイクストラ法を用いた場合、その計算量はノード数をｎとするとＯ（ｎ＾２）であることが知られている。本実施の形態に係る経路算出装置１０では、エリア間経路を事前に学習経路として記憶しておくことで、図８で示すように実質的にノード数が大幅に削減され、ダイクストラ法を用いた経路計算の時間が大幅に短縮される。その結果、例えばユーザからの経路算出要求に対して、迅速なレスポンスが可能となる。
ここでさらに、前述した学習経路を作成する上での課題（１）および（２）の解決について考察する。
【００３２】
（１）膨大な記憶容量の必要性
ノード間経路は全てのノード間について持つわけではなく境界ノード間のみ、しかも特定のエリアの１つの境界ノードと他のエリアの全境界ノードのうち最小の移動コストとなる組み合わせのみエリア間経路として保持するため、必要な記憶容量は大幅に削減される。
（２）膨大な事前計算量の必要性
エリア間経路の計算は全てのノード間について行うわけではなく、特定のエリアの境界ノード毎に、他の特定のエリアの境界ノードについて、１度ダイクストラ法での経路計算を行い、それを他のエリアとの組み合わせ数分繰り返すに過ぎない。したがって、全ノード間の経路を計算するのと比較して、必要な事前計算量も大幅に削減される。
このように、本実施の形態に係る経路算出装置１０では、学習経路の事前計算により、経路の算出時間を大幅に短縮するとともに、学習経路を作成する上での課題を解決している。なお、課題（３）の解決については後述する。
【００３３】
本実施の形態にかかる経路算出装置１０は、さらに、移動コスト調整部９０を備えてもよい。前述した受信部３０が交通情報提供システムから交通情報を受け付けると、移動コスト調整部９０は、地図情報記憶部５０が格納するリンクのうち、その交通情報の影響を受けるリンクの移動コストを変更する。例えば、渋滞が発生した場合には、その渋滞により影響を受けるリンクの移動コストを大きくし、渋滞が解消した場合には逆に、移動コストを小さくする。次回経路算出を行うときには、最新の交通情報が移動コストとして反映されているため、最新の交通事情を加味した上で、最小の移動コストとなる経路の算出ができ、ユーザの利便性の向上を実現する。
【００３４】
経路算出装置１０は、さらに、移動コスト調整部９０が、交通情報に基づき各リンクの移動コストを変更した後で、ユーザの現在位置から終点までの経路を再度算出してもよい。経路の再算出は、ユーザからの明示的な指示を受けて行ってもよいし、経路算出装置１０が自律的に行ってもよい。経路算出装置１０が自律的に経路を再算出する例として、経路算出装置１０は、経路の再算出の要否を判定するための閾値を予め用意し、移動コスト調整部９０により調整された移動コストの変動の幅がこの閾値を上回る場合に、経路を再算出してもよい。これにより、最新の交通情報を加味した上で、最小の移動コストとなる経路をユーザに対し提示することができる。
【００３５】
図１０は、交通情報に基づく経路の変更例を示す。例えば、ユーザがエリア間経路５０２にしたがって境界ノードＹ１０６・ノードＸ０７０３間を移動中に、将来通行予定の境界ノードＹ０３３・ノードＸ０８０３間に渋滞が発生したとする。このとき、その渋滞情報を受信部３０が受け付け、移動コスト調整部９０は、境界ノードＹ０３３・ノードＸ０８０３間のリンクの移動コストを大きくする。
【００３６】
次に、エリア特定部７０は、現在位置を含む第１エリア、つまり図１０のエリア３０８と、終点を含む第２エリア、つまりエリア３０４を、特定する。そして、経路導出部８０は、前述したように、エリア間経路記憶部６０からエリア３０８とエリア３０４間のエリア間経路を取得する。ここで、エリア間経路の一つが境界ノードＹ０３３・ノードＸ０８０３・ノードＸ０８０６・境界ノードＹ２０８だったとする。この場合、このエリア間経路は一部のリンクの移動コストが大きくなっているため、経路導出部８０は、ダイクストラ法を用い、代替の経路を算出してもよい。例えば、経路導出部８０は、移動コストが調整されたリンクを含むエリアでは、エリア間経路記憶部６０から取得したエリア間経路を使わずに、そのエリアに含まれる全リンクの移動コストを考慮して、ダイクストラ法により経路を導出してもよい。図１０では、代替の経路として、境界ノードＹ０３３・ノードＸ０８０１・ノードＸ０８０４・境界ノードＹ２０８が選択されたイメージを示している。
【００３７】
この例で示したように、代替の経路を算出可能であるのは、エリア間経路記憶部６０が、エリア間経路をリンクの組み合わせとして記憶しているからである。前述したように、移動コスト調整部９０は、交通情報に基づき影響を受ける個々のリンクの移動コストを変更し、経路導出部８０はダイクストラ法を用いて最小の移動コストとなる経路をユーザに再度提示することができる。これに対して、エリア間経路情報を、境界ノードから境界ノードまで固定的に保持していた場合には、ここで示したような最新の交通情報の反映は困難であるし、代替経路の算出も困難である。本実施の形態にかかる経路算出装置１０は、エリア間経路情報をリンクの組み合わせとして持つことで、前述した課題（３）、つまり事前に固定的な学習経路を持つことによる弊害を解決している。
【００３８】
なお、経路算出装置１０が、移動コスト調整部９０を備えない場合にも、エリア間経路記憶部６０が、エリア間経路をリンクの組み合わせとして保持することによって、より柔軟な経路算出を実現し、ユーザの利便性を高めるという効果がある。例えば、ユーザが学習経路の一部を何らかの事情により通行したくない、もしくは通行できない、迂回したい場合や、通行止め等の交通事情により迂回せざるを得ない場合を考える。このとき、経路導出部８０は、特定のリンクが無いものとして、その他のノード間のリンクの移動コストをもとに、ダイクストラ法を用いて次善の経路をユーザに提示することができる。または、経路算出装置１０が提示した経路をユーザがはずれてしまった場合に、ユーザの現在位置から終点までの経路を再度算出して提示することもできる。
このように、エリア間経路記憶部６０が、エリア間経路をリンクの組み合わせとして保持することによって、経路算出時の計算量を減らして迅速に経路算出を行うことと、柔軟な経路算出を実現することとを両立して、ユーザの利便性を高める。さらに、移動コスト調整部９０を備えることで、最新の交通情報を経路の導出に反映できるため、ユーザに対しより適切な経路の提示を可能とし、ユーザの利便性のさらなる向上を実現する。
【００３９】
また、本実施形態の説明において、学習経路として事前に算出されるエリア間経路は、あるエリアＡの１つの境界ノードａから、他のエリアＢの全境界ノードまでの移動コストを、ダイクストラ法を用いて算出して、最も移動コストが小さくなるエリアＢの境界ノードまでのリンクの組み合わせを、境界ノードａからエリアＢまでのエリア間経路とした。変形例として、ダイクストラ法を用いて算出した、エリアＡの１つの境界ノードａから、他のエリアＢの全境界ノードまでの移動コストの、全てのリンクの組み合わせを、学習経路として保持してもよい。こうすることにより、エリアＡの始点または終点と、エリアＢの始点または終点の位置に応じて、より移動コストの小さなエリア間経路を選択しやすくなる。例えば、図５において、エリア３０２のノードＸ０１０２から、エリア３０４のＸ１２０１までの経路を算出する場合を考える。このとき、エリア３０４内部での移動コストを考慮すると、Ｙ０１１からＹ２０８のエリア間経路を使うよりも、Ｙ０１１からＹ２０７のエリア間経路を使った方が、全体としての移動コストは小さくなる可能性がある。本変形例によれば、境界ノードの組み合わせ毎に、エリア間経路を保持するため、より移動コストの小さな経路を導出しやすくなる。
【００４０】
（第２の実施形態）
本発明の第２の実施形態にかかる経路算出装置は、前述の第１の実施形態にかかる経路算出装置と、記憶されるエリア間経路のデータ構造の点、および、経路導出の点において異なる。本実施形態の説明において、第１の実施形態と同じものには、第１の実施形態の説明において付与した符号と同じ符号を付与している。また、同一の符号が付与されたものに関する詳細な説明は省略する。
【００４１】
図１１は、本発明の第２の実施形態にかかる経路算出装置の構成例を示す機能ブロック図である。経路算出装置１０００は、ユーザインタフェイス部２０と、受信部３０と、現在位置導出部４０と、地図情報記憶部５０と、エリア特定部７０と、移動コスト調整部９０と、エリア間経路記憶部１０６０と、経路導出部１０８０とを備える。以下、エリア間経路記憶部１０６０と、経路導出部１０８０とについて説明する。
【００４２】
エリア間経路記憶部１０６０は、エリア間経路記憶部６０と同様に、エリア間経路をリンクの組み合わせとして格納する。エリア間経路記憶部１０６０は、特定のエリアの１つの境界ノードと他のエリアの全ての境界ノードとの組み合わせ毎に、所定の条件に基づいて１つの経路が決定されてもよい。ここで、所定の条件は、距離・移動時間・通行のための費用等、つまり移動コストに基づく条件であってもよい。以下では、例示として、移動コストが最も小さいエリア間経路が選定されるものとする。
【００４３】
図１２は、エリア間経路のイメージ図である。同図において、エリア３０２の境界ノードＹ０１１から、エリア３０４の各境界ノードへのエリア間経路は、Ｙ０１１からＹ２０７まで、Ｙ０１１からＹ２０８まで、Ｙ０１１からＹ０３５まで、Ｙ０１１からＹ０３６までの、４本が導出されている。これらのエリア間経路は、境界ノードＹ０１１から、境界ノードＹ２０７・Ｙ２０８・Ｙ０３５・Ｙ０３６までの、リンクの組み合わせに対してダイクストラ法を用いることで、移動コストの合計が相対的に小さくなるリンクの組み合わせとして導出されたものである。
【００４４】
同様に、図１３も、エリア間経路のイメージ図である。同図において、エリア３０２の境界ノードＹ１０２から、エリア３０４の各境界ノードへのエリア間経路は、前述の方法により算出され、Ｙ１０２からＹ２０７まで、Ｙ１０２からＹ２０８まで、Ｙ１０２からＹ０３５まで、Ｙ１０２からＹ０３６までの、４本が導出されている。さらに、図１４も、エリア間経路のイメージ図である。同図において、エリア３０２の境界ノードＹ１０１から、エリア３０４の各境界ノードへのエリア間経路は、前述の方法により算出され、Ｙ１０１からＹ２０７まで、Ｙ１０１からＹ２０８まで、Ｙ１０１からＹ０３５まで、Ｙ１０１からＹ０３６までの、４本が導出されている。
【００４５】
図１５も、エリア間経路のイメージ図である。同図では、図１２から図１４まで説明した、エリア３０２からエリア３０４までの、エリア間経路が組み合わされた状態を示している。エリア間経路記憶部１０６０は、各エリアの組み合わせ毎に、図１５で例示したリンクの組み合わせを、ネットワーク型データモデルとして記憶する。
【００４６】
図１６は、エリア間経路記憶部１０６０が格納するエリア間経路のデータ構造を例示する。同図では、図１５で示したエリア間経路が、出発エリア番号が３０２で、目標エリア番号が３０４の組み合わせで特定されるレコードとして保持されることを示している。エリア間経路、つまりリンクの組み合わせは、ネットワーク型データモデルとして保持される。図１６はデータ構造を模式的に示したものであり、実際には、個々のノードをレコードとし、そのノードと接続されるノードのポインタを、レコードに埋め込むことで実現されてもよい。また、ＤＢＭＳ（database management system）に保持させることで実現されてもよく、その他の公知の技術により実現されてもよい。なお、エリア間経路記憶部１０６０は、出発エリアと目標エリアとの組み合わせ毎に、図１６で示したようなエリア間経路を保持する。図１１に戻る。
【００４７】
経路導出部１０８０は、経路導出部８０と同様に、始点を含む第１エリアと、終点を含む第２エリアを結ぶ経路情報を、エリア間経路記憶部１０６０より取得して、始点と終点とを結ぶ経路を導出する。図１７は、始点７０２と終点７０４とが、地図上に指定された状態を表す。経路導出部１０８０は、始点７０２から第１エリアの各境界ノードまでの移動コストと、第１エリアと第２エリア間の移動コストと、第２エリア内の各境界ノードから終点７０４までの移動コストとを考慮して、ダイクストラ法を用いて始点と終点との経路を導出する。
【００４８】
図１８は、経路導出部１０８０が経路を導出するときの考え方を示す。同図では、図１７の始点７０２と終点７０４間に存在するリンクを示している。同図において、エリア間のノードは模式的に示しているが、実際には、経路導出部１０８０は、エリア間経路記憶部１０６０から、出発エリア番号と目標エリア番号をキーにして、エリア間経路であるリンクの組み合わせを取得する。この例では、出発エリアはエリア３０２であり、目標エリアはエリア３０４であるため、図１６で示したエリア間経路を取得する。エリア間経路は、リンクの組み合わせとして格納されているため、経路導出部１０８０は、それぞれのリンクの移動コストを地図情報記憶部５０より取得して、各リンクに設定する。また、第１エリア内、第２エリア内の各リンクの移動コスト、および、始点または終点から近傍ノードへの移動コストについては、第１の実施形態と同様である。
【００４９】
図１９は、経路導出部１０８０が経路を導出する手順の一例を示すフローチャートである。なお、同図において、Ｓ２２からＳ３０までは、図９で説明したＳ２からＳ１０までと、それぞれ同様であるため、同図のＳ３２以降について説明する。経路導出部１０８０は、第１エリアと第２エリアのエリア間経路を、エリア間経路記憶部１０６０から取得する（Ｓ３２）。次に、エリア間経路のそれぞれリンクの移動コストを、地図情報記憶部５０から取得する（Ｓ３４）。これで、始点から終点までに存在するリンクと各リンクの移動コストが求まったため、最後に、ダイクストラ法を用いて、始点から終点までの最小の移動コストとなる経路を算出する（Ｓ３６）。
【００５０】
本実施の形態に係る経路算出装置１０００でも、第１の実施形態と同様に、エリア間経路を事前に学習経路として記憶しておくことで、図１６および図１８で示すように実質的にノード数が大幅に削減され、ダイクストラ法を用いた経路計算の時間が大幅に短縮される。その結果、例えばユーザからの経路算出要求に対して、迅速なレスポンスが可能となる。また、本実施形態では、特定のエリアＡの１つの境界ノードから、他のエリアＢの全境界ノードまでの移動コストを、ダイクストラ法を用いて算出して、その全てのリンクの組み合わせを学習経路として保持する。したがって、第１の実施形態の変形例において説明したように、エリアＡの始点または終点と、エリアＢの始点または終点の位置に応じて、より移動コストの小さなエリア間経路を選択しやすくなっている。
【００５１】
ここでさらに、前述した学習経路を作成する上での課題（１）および（２）の解決について考察する。
（１）膨大な記憶容量の必要性
ノード間経路は全てのノード間について持つわけではなく、境界ノード間のみのリンクの組み合わせをエリア間経路として保持するため、必要な記憶容量は大幅に削減される。境界ノード間のみで、かつ、特定のエリアの１つの境界ノードと他のエリアの全境界ノードのうち最小の移動コストとなる組み合わせのみエリア間経路として保持する第１の実施形態と比べると必要な記憶容量は大きく増加するようにも思われる。図５において、エリア３０２からエリア３０４間のエリア間経路として、３本のエリア間経路を記憶していた第１の実施形態と比較すると、第２の実施形態は図１５で示すように、境界ノード数分の組み合わせである１２本分、つまり４倍のエリア間経路を記憶するようにも思われるからである。しかし、図５と図１５を対比すれば明らかなように、記憶すべきリンクの組み合わせは、４倍にはならない。これは、移動コストが小さい経路、例えば移動時間が短い経路は、道幅の広い主要幹線道路等であるため、それぞれのエリア間経路におけるリンクの多くが共通するからである。そのため、将来的に境界ノードが増えた場合にも、追加して記憶すべきリンク数は最小限となる。したがって、本実施形態の経路算出装置は記憶容量の課題を解決している。
【００５２】
（２）膨大な事前計算量の必要性
エリア間経路の計算は全てのノード間について行うわけではなく、特定のエリアの境界ノード毎に、他の特定のエリアの境界ノードについて、１度ダイクストラ法での経路計算を行い、それを他のエリアとの組み合わせ数分繰り返すに過ぎない。したがって、全ノード間の経路を計算するのと比較して、必要な事前計算量も大幅に削減される。なお、１度ダイクストラ法での経路計算を行えば、特定のエリアの特定の境界ノードから、他の特定のエリアの全ての境界ノードまでの経路が算出できるため、事前計算量については、第１の実施形態と本実施形態とは同じである。
このように、本実施の形態に係る経路算出装置１０００でも、学習経路の事前計算により、経路の算出時間を大幅に短縮するとともに、学習経路を作成する上での課題を解決している。
【００５３】
また、本実施の形態にかかる経路算出装置１０００も、第１の実施形態と同様に、移動コスト調整部９０を備えてもよい。移動コスト調整部９０を備えることによる、構成、効果、および課題（３）の解決については、第１の実施形態と同様である。また、経路算出装置１０が、移動コスト調整部９０を備えない場合にも、エリア間経路記憶部６０が、エリア間経路をリンクの組み合わせとして保持することによって、より柔軟な経路算出を実現し、ユーザの利便性を高めるという効果についても、第１の実施形態と同様である。特に、本実施形態の場合には、特定のエリアの境界ノードから他のエリアの全ての境界ノードまでのエリア間経路を、学習経路として事前に記憶している。これにより、学習経路の１つが、例えば通行止めにより通行できなくなった場合でも、他の学習経路を使うことで迂回路算出のためのノード数を低減でき、より迅速に迂回路を導出できる。
【００５４】
（第３の実施形態）
これまでは、第１および第２の実施形態として、現在主流のカーナビゲーション装置のような、記憶部や経路導出部を含んだ経路算出装置について説明した。以下、本発明の第３の実施形態として、経路算出システムについて説明する。経路を一元的に算出するサーバが、ＡＳＰ（Application Service Provider）として、ユーザに対し経路算出サービスを提供する形態である。
【００５５】
図２０は、本発明の第３の実施形態に係る経路算出システムの構成例を示す機能ブロック図である。経路算出システムは、経路算出サーバ１００、および経路表示端末１２０、を備える。経路算出サーバ１００と経路表示端末１２０は、インターネット・ＷＡＮ・ＬＡＮ・携帯電話ネットワーク等を含む通信ネットワーク１９０を介して接続される。なお、同図において、第１および第２の実施形態と同じ機能ブロックについては、同一の符号を使用している。以下、第１および第２の実施形態と同じ機能ブロックについての説明は省略し、第１および第２の実施形態との違いについて主に説明する。
【００５６】
経路算出サーバ１００は、経路算出サービスを提供するサーバであり、受信部３０、地図情報記憶部５０、エリア間経路記憶部１０６０、エリア特定部７０、経路導出部１０８０、移動コスト調整部９０、通信部１１０を有する。通信部１１０は、通信ネットワーク１９０を介して経路表示端末１２０からの経路算出要求情報を受け付ける。経路算出サーバ１００は、その要求に基づき経路を算出し、経路情報を経路表示端末１２０に出力する。他の機能ブロックについては、第１および第２の実施形態の経路算出装置と同様である。なお、エリア間経路記憶部１０６０は、第１の実施形態のエリア間経路記憶部６０でもよく、経路導出部１０８０は、第１の実施形態の経路導出部８０でもよい。
【００５７】
経路表示端末１２０は、主にユーザインタフェイスを担当する端末であり、受信部３０、現在位置導出部４０、受付部１３０、表示部１４０、通信部１５０、を有する。受付部１３０は、ユーザからの経路を算出する始点・終点等の入力を受け付け、経路算出要求情報を作成する。始点については、第１および第２の実施形態と同様に、ＧＰＳ衛星からの信号を受信部３０が受け付け、現在位置導出部４０が現在位置を導出して始点としてもよい。通信部１５０は、通信ネットワーク１９０を介して、経路算出要求情報を経路算出サーバ１００に出力し、算出された経路情報を経路算出サーバ１００から受け取る。表示部１４０は、経路情報を画面に表示させる。
【００５８】
通信ネットワーク１９０のブロードバンド化が進む現在では、機器間の物理的な位置の影響をほとんど受けず、通信ネットワーク１９０を介して大量の情報を高速にやりとりできる。そのため、ユーザインタフェイスを担当する経路表示端末１２０と、経路算出を担当する経路算出サーバ１００が離れた場所に存在しても、通信のための待ち時間の発生は少なく、ユーザの利便性を損なうことは少ない。経路表示端末１２０側では、地図情報記憶部５０やエリア間経路記憶部６０等を保持する必要が無く、自ら経路算出を行わないため、高性能のハードウェアを必要としない。一方で、一元的に経路算出を担当する経路算出サーバ１００側では、経路表示端末１２０とは異なりハードウェアの物理的な制限を受けにくいため、経路算出の性能向上も図りやすい。このように、第３の実施形態においては、通信ネットワーク１９０を仲介として、経路表示端末１２０と経路算出サーバ１００との最適な役割分担を実現する。
【００５９】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００６０】
本発明の実施形態の説明においては、地図を分割するエリアの大きさは全て同じ長方形状であったが、変形例として、交通量がより大きい都市部におけるエリアの大きさは、他の地域におけるエリアの大きさより小さくてもよい。あるいは、道路の密度が高い都市部におけるエリアの大きさは、他の地域におけるエリアの大きさより小さくてもよい。
【００６１】
エリアの大きさが一定である場合、交通量が多い都市部や道路密度が高い都市部におけるエリアの境界ノードの個数は、他の地域におけるエリアの境界ノードの個数よりも相対的に多くなる。しかし、始点から終点への経路を求める場合、境界ノードの個数は、すなわちエリア間経路の個数となるため、経路算出においては境界ノードの個数は少ない方が望ましい。したがって、都市部におけるエリアの大きさを、他の地域におけるエリアの大きさよりも小さくすることで、都市部におけるエリアの境界ノード数を減らすことができ、経路算出の時間を短縮することができる。
【００６２】
また、本実施の形態に係る経路算出装置１０、または経路算出装置１０００では、ダイクストラ法を用いて、最小の移動コストとなる経路を算出しているが、これは例示であり、最短経路問題を解く他のアルゴリズム、例えばワーシャル−フロイド法等、を用いてもよい。この場合にも、前述の実施の形態と同様の効果を得ることができる。
【図面の簡単な説明】
【００６３】
【図１】本発明の第１の実施形態に係る経路算出装置の構成例を示す機能ブロック図である。
【図２】地図のイメージ図である。
【図３】複数のエリアに分割された地図情報のイメージ図である。
【図４】リンク情報のデータ構造を示す図である。
【図５】エリア間経路のイメージ図である。
【図６】エリア間経路のデータ構造を例示する図である。
【図７】始点と終点とが地図上に指定された状態を示す図である。
【図８】経路導出部が経路を導出するときの考え方を示す図である。
【図９】経路導出部が経路を導出する手順の一例を示すフローチャートである。
【図１０】交通情報に基づく経路の変更例を示す図である。
【図１１】本発明の第２の実施形態に係る経路算出装置の構成例を示す機能ブロック図である。
【図１２】エリア間経路のイメージ図である。
【図１３】エリア間経路のイメージ図である。
【図１４】エリア間経路のイメージ図である。
【図１５】エリア間経路のイメージ図である。
【図１６】エリア間経路記憶部が格納するエリア間経路のデータ構造を例示する図である。
【図１７】始点と終点とが地図上に指定された状態を示す図である。
【図１８】経路導出部が経路を導出するときの考え方を示す図である。
【図１９】経路導出部が経路を導出する手順の一例を示すフローチャートである。
【図２０】本発明の第３の実施形態に係る経路算出システムの構成例を示す機能ブロック図である。
【符号の説明】
【００６４】
１０ 経路算出装置、２０ ユーザインタフェイス部、３０ 受信部、４０ 現在位置導出部、５０ 地図情報記憶部、６０ エリア間経路記憶部、７０ エリア特定部、８０ 経路導出部、９０ 移動コスト調整部、１００ 経路算出サーバ、１１０ 通信部、１２０ 経路表示端末、１３０ 受付部、１４０ 表示部、１５０ 通信部、１９０ 通信ネットワーク、２０２ 地図の全体領域、２０４ ノード、２０６ リンク、３０２ エリア、３０４ エリア、３０６ 境界ノード、３０８ エリア、５０２ エリア間経路、５０４ エリア間経路、５０６ エリア間経路、７０２ 始点、７０４ 終点、１０００ 経路算出装置、１０６０ エリア間経路記憶部、１０８０ 経路導出部。
【特許請求の範囲】
【請求項１】
地図を、それぞれが座標情報で特定される複数のエリアに分割し、前記複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部と、
異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部と、
前記地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部と、
第１エリアと第２エリアを結ぶ経路情報を、前記エリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出部と、
を備えることを特徴とする経路算出装置。
【請求項２】
前記リンクの情報には、各リンクの移動コストが含まれることを特徴とする請求項１に記載の経路算出装置。
【請求項３】
前記エリア間経路記憶部が格納する境界ノード間の経路情報は、あるエリアの境界ノードと他のエリアの境界ノードとの間のリンクの組み合わせであって、各リンクの移動コストの合計が相対的に小さくなるものであることを特徴とする請求項２に記載の経路算出装置。
【請求項４】
前記経路導出部は、前記地図情報記憶部を参照して、始点と第１エリアの境界ノードとを結ぶリンクの組み合わせと、第２エリアの境界ノードと終点とを結ぶリンクの組み合わせとを取得し、前記エリア間経路記憶部を参照して、第１エリアの境界ノードと第２エリアの境界ノードとを結ぶリンクの組み合わせを取得することにより、始点と終点とを結ぶリンクの組み合わせを導出することを特徴とする請求項２または３に記載の経路算出装置。
【請求項５】
前記経路導出部は、前記地図情報記憶部を参照して、始点と第１エリアの境界ノードとを結ぶリンクの組み合わせと、第２エリアの境界ノードと終点とを結ぶリンクの組み合わせとを取得し、前記エリア間経路記憶部を参照して、第１エリアの境界ノードと第２エリアの境界ノードとを結ぶリンクの組み合わせを取得することにより、始点と終点とを結ぶリンクの組み合わせを作成し、前記地図情報記憶部により保持される各リンクの移動コストを参照して、ダイクストラ法を用いることにより、各リンクの移動コストの合計が相対的に小さくなるように、始点と終点とを結ぶリンクの組み合わせを導出することを特徴とする請求項４に記載の経路算出装置。
【請求項６】
交通情報の入力を受け付けたときに、前記地図情報記憶部が格納するリンクの移動コストを調整する移動コスト調整部を、さらに備えることを特徴とする請求項２から５のいずれかに記載の経路算出装置。
【請求項７】
交通情報の入力を受け付けたときに、
前記移動コスト調整部は、前記地図情報記憶部が格納するリンクの移動コストを調整し、
前記エリア特定部は、前記地図情報記憶部を参照して、現在位置を含む第１エリアと、終点を含む第２エリアとを特定し、
前記経路導出部は、前記地図情報記憶部を参照して、現在位置と第１エリアの境界ノードとを結ぶリンクの組み合わせと、第２エリアの境界ノードと終点とを結ぶリンクの組み合わせとを取得し、前記エリア間経路記憶部を参照して、第１エリアの境界ノードと第２エリアの境界ノードとを結ぶリンクの組み合わせを取得することにより、現在位置と終点とを結ぶリンクの組み合わせを作成し、前記移動コスト調整部により調整されたリンクの移動コストを参照して、ダイクストラ法を用いることにより、各リンクの移動コストの合計が相対的に小さくなるように、現在位置と終点とを結ぶリンクの組み合わせを導出することを特徴とする請求項６に記載の経路算出装置。
【請求項８】
前記エリア間経路記憶部が格納する境界ノード間の経路情報は、あるエリアの１つの境界ノードと他のエリアの１つの境界ノードとの間の経路を特定するものであることを特徴とする請求項１から７のいずれかに記載の経路算出装置。
【請求項９】
経路算出サーバと、経路表示端末と、を備える経路算出システムであって、
前記経路算出サーバは、
地図を、それぞれが座標情報で特定される複数のエリアに分割し、前記複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部と、
異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部と、
経路を算出する始点および終点を指定する経路算出要求情報をもとに、前記地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部と、
第１エリアと第２エリアを結ぶ経路情報を、前記エリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出部と、
前記経路表示端末から前記経路算出要求情報を受け付け、また、前記経路表示端末に導出した経路を出力する通信部と、
を有し、
前記経路表示端末は、
ユーザから、前記経路算出要求情報の指定入力を検出する受付部と、
前記経路算出要求情報を前記経路算出サーバに出力し、また、前記経路算出サーバにより導出された経路を取得する通信部と、
取得した経路を画面表示させる表示部と、
を有することを特徴とする経路算出システム。
【請求項１０】
地図を、それぞれが座標情報で特定される複数のエリアに分割し、前記複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定ステップと、
第１エリアと第２エリアを結ぶ経路情報を、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出ステップと、
を備えることを特徴とする経路算出方法。
【請求項１１】
地図を、それぞれが座標情報で特定される複数のエリアに分割し、前記複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定機能と、
第１エリアと第２エリアを結ぶ経路情報を、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出機能と、
をコンピュータに実現させることを特徴とするコンピュータプログラム。
【請求項１】
地図を、それぞれが座標情報で特定される複数のエリアに分割し、前記複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部と、
異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部と、
前記地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部と、
第１エリアと第２エリアを結ぶ経路情報を、前記エリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出部と、
を備えることを特徴とする経路算出装置。
【請求項２】
前記リンクの情報には、各リンクの移動コストが含まれることを特徴とする請求項１に記載の経路算出装置。
【請求項３】
前記エリア間経路記憶部が格納する境界ノード間の経路情報は、あるエリアの境界ノードと他のエリアの境界ノードとの間のリンクの組み合わせであって、各リンクの移動コストの合計が相対的に小さくなるものであることを特徴とする請求項２に記載の経路算出装置。
【請求項４】
前記経路導出部は、前記地図情報記憶部を参照して、始点と第１エリアの境界ノードとを結ぶリンクの組み合わせと、第２エリアの境界ノードと終点とを結ぶリンクの組み合わせとを取得し、前記エリア間経路記憶部を参照して、第１エリアの境界ノードと第２エリアの境界ノードとを結ぶリンクの組み合わせを取得することにより、始点と終点とを結ぶリンクの組み合わせを導出することを特徴とする請求項２または３に記載の経路算出装置。
【請求項５】
前記経路導出部は、前記地図情報記憶部を参照して、始点と第１エリアの境界ノードとを結ぶリンクの組み合わせと、第２エリアの境界ノードと終点とを結ぶリンクの組み合わせとを取得し、前記エリア間経路記憶部を参照して、第１エリアの境界ノードと第２エリアの境界ノードとを結ぶリンクの組み合わせを取得することにより、始点と終点とを結ぶリンクの組み合わせを作成し、前記地図情報記憶部により保持される各リンクの移動コストを参照して、ダイクストラ法を用いることにより、各リンクの移動コストの合計が相対的に小さくなるように、始点と終点とを結ぶリンクの組み合わせを導出することを特徴とする請求項４に記載の経路算出装置。
【請求項６】
交通情報の入力を受け付けたときに、前記地図情報記憶部が格納するリンクの移動コストを調整する移動コスト調整部を、さらに備えることを特徴とする請求項２から５のいずれかに記載の経路算出装置。
【請求項７】
交通情報の入力を受け付けたときに、
前記移動コスト調整部は、前記地図情報記憶部が格納するリンクの移動コストを調整し、
前記エリア特定部は、前記地図情報記憶部を参照して、現在位置を含む第１エリアと、終点を含む第２エリアとを特定し、
前記経路導出部は、前記地図情報記憶部を参照して、現在位置と第１エリアの境界ノードとを結ぶリンクの組み合わせと、第２エリアの境界ノードと終点とを結ぶリンクの組み合わせとを取得し、前記エリア間経路記憶部を参照して、第１エリアの境界ノードと第２エリアの境界ノードとを結ぶリンクの組み合わせを取得することにより、現在位置と終点とを結ぶリンクの組み合わせを作成し、前記移動コスト調整部により調整されたリンクの移動コストを参照して、ダイクストラ法を用いることにより、各リンクの移動コストの合計が相対的に小さくなるように、現在位置と終点とを結ぶリンクの組み合わせを導出することを特徴とする請求項６に記載の経路算出装置。
【請求項８】
前記エリア間経路記憶部が格納する境界ノード間の経路情報は、あるエリアの１つの境界ノードと他のエリアの１つの境界ノードとの間の経路を特定するものであることを特徴とする請求項１から７のいずれかに記載の経路算出装置。
【請求項９】
経路算出サーバと、経路表示端末と、を備える経路算出システムであって、
前記経路算出サーバは、
地図を、それぞれが座標情報で特定される複数のエリアに分割し、前記複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部と、
異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部と、
経路を算出する始点および終点を指定する経路算出要求情報をもとに、前記地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定部と、
第１エリアと第２エリアを結ぶ経路情報を、前記エリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出部と、
前記経路表示端末から前記経路算出要求情報を受け付け、また、前記経路表示端末に導出した経路を出力する通信部と、
を有し、
前記経路表示端末は、
ユーザから、前記経路算出要求情報の指定入力を検出する受付部と、
前記経路算出要求情報を前記経路算出サーバに出力し、また、前記経路算出サーバにより導出された経路を取得する通信部と、
取得した経路を画面表示させる表示部と、
を有することを特徴とする経路算出システム。
【請求項１０】
地図を、それぞれが座標情報で特定される複数のエリアに分割し、前記複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定ステップと、
第１エリアと第２エリアを結ぶ経路情報を、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出ステップと、
を備えることを特徴とする経路算出方法。
【請求項１１】
地図を、それぞれが座標情報で特定される複数のエリアに分割し、前記複数のエリアのそれぞれに含まれるノードの座標情報と、ノード間を結ぶリンクの情報とを、それぞれのエリアに対応付けて格納する地図情報記憶部を参照して、始点を含む第１エリアと、終点を含む第２エリアを特定するエリア特定機能と、
第１エリアと第２エリアを結ぶ経路情報を、異なるエリアのそれぞれの境界に位置する境界ノード間の経路情報をリンクの組み合わせとして格納するエリア間経路記憶部より取得して、始点と終点を結ぶ経路を導出する経路導出機能と、
をコンピュータに実現させることを特徴とするコンピュータプログラム。
【図１】
【図４】
【図６】
【図８】
【図９】
【図１１】
【図１６】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図５】
【図７】
【図１０】
【図１２】
【図１３】
【図１４】
【図１５】
【図１７】
【図４】
【図６】
【図８】
【図９】
【図１１】
【図１６】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図５】
【図７】
【図１０】
【図１２】
【図１３】
【図１４】
【図１５】
【図１７】
【公開番号】特開２００９−２８９６（Ｐ２００９−２８９６Ａ）
【公開日】平成２１年１月８日（２００９．１．８）
【国際特許分類】
【出願番号】特願２００７−１６６２１７（Ｐ２００７−１６６２１７）
【出願日】平成１９年６月２５日（２００７．６．２５）
【出願人】（３０２０４９３３４）ジクー・データシステムズ株式会社 (9)
【Ｆターム（参考）】
【公開日】平成２１年１月８日（２００９．１．８）
【国際特許分類】
【出願日】平成１９年６月２５日（２００７．６．２５）
【出願人】（３０２０４９３３４）ジクー・データシステムズ株式会社 (9)
【Ｆターム（参考）】
[ Back to top ]