経路探索装置、ネットワークデータのデータ構造、およびネットワークデータ生成装置
【課題】出発地および目的地の位置に応じて経路を検索する範囲を限定することにより、経路を探索する処理の高速化を図ることを可能とした経路探索装置、ネットワークデータおよびネットワークデータ生成装置を提供する。
【解決手段】ネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されているネットワークデータを参照し、出発地および目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、出発地および目的地のいずれも含まないネットワーク領域を除いた探索領域を設定し、出発地付近領域および目的地付近領域の包含関係に応じて設定した探索領域内に限定して出発地から目的地への経路を探索する。
【解決手段】ネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されているネットワークデータを参照し、出発地および目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、出発地および目的地のいずれも含まないネットワーク領域を除いた探索領域を設定し、出発地付近領域および目的地付近領域の包含関係に応じて設定した探索領域内に限定して出発地から目的地への経路を探索する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、出発地から目的地までの経路を探索する経路探索装置、ネットワークデータのデータ構造、およびネットワークデータ生成装置に関するものである。
【背景技術】
【0002】
従来から、カーナビゲーションデバイスや、携帯して持ち運びすることが可能な、例えばPND(Personal Navigation Device)等に経路探索装置が利用されている。
従来の経路探索装置としては、例えば、道路のネットワークデータを含む地図情報が記憶されているハードディスク等の記憶媒体にアクセスし、所望の地図情報を取得して画面に表示するとともに、出発地から目的地への経路探索・案内を行なうナビゲーション機能を有するものが広く用いられている。また、行き止まりや袋小路等のリンクに行き止まり属性フラグを付与し、この行き止まり属性フラグを参照し、行き止まり属性フラグを有するリンクの先の経路を探索しないようにした経路探索装置も知られている(例えば、特許文献1を参照。)。
上記特許文献1に記載の経路探索装置によれば、出発地から目的地への通行経路になり得ないリンクに探索の枝を伸ばさないようにしているので、経路を探索する処理の時間の短縮を図ることが可能となる。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2000−18958号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、上記特許文献1に記載の経路探索装置は、出発地および目的地を含むパーセル内では行き止まり属性フラグを参照しないことにしているので、出発地および目的地がいずれも袋小路内にある場合であっても、袋小路外の広い領域に経路を探索する枝が伸びることがあり、このような場合には経路を探索する処理の時間が効果的に短縮されないという問題がある。また、上記特許文献1に記載の経路探索装置によれば、目的地が袋小路内にある場合には経路を探索することができないという問題がある。
すなわち、上記特許文献1に記載の経路探索装置は、袋小路の内側に出発地や目的地がある場合に経路を探索する処理において課題を有している。
本発明は、出発地および目的地の位置に応じて経路を検索する範囲を限定することにより、経路を探索する処理の高速化を図ることを可能とした経路探索装置およびネットワークデータを提供することを目的とする。
【課題を解決するための手段】
【0005】
上記課題を解決するために、本発明の経路探索装置は、複数のリンクおよびノードを含むネットワーク領域であって該ネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および該下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されている複数のネットワーク領域からなるネットワークデータを参照するネットワークデータ参照部と、前記ネットワークデータに含まれるリンクまたはノード上に出発地および目的地をそれぞれ設定する地点設定部と、前記出発地および前記目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、前記出発地および前記目的地のいずれも含まないネットワーク領域を除いた探索領域を設定する探索領域設定部と、前記探索領域内に限定して前記出発地から前記目的地への経路を探索する経路探索部とを備えることを特徴とするものである。
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成(または方法)もまた発明となり得る。
【発明の効果】
【0006】
本発明の経路探索装置は、複数のリンクおよびノードを含むネットワーク領域であってネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されたネットワークデータを参照し、出発地および目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、出発地および目的地のいずれも含まないネットワーク領域を除いた探索領域を設定して経路を探索している。従って、本発明の経路探索装置によれば、出発地および目的地の位置に応じて経路を検索する範囲を限定することによって、不必要なリンクに向けた探索の枝が伸びなくなるので、経路を探索する処理の高速化を図ることが可能となる。
【図面の簡単な説明】
【0007】
【図1】本実施例の経路探索装置の構成を示すブロック図である。
【図2】(a)は本実施例の経路探索装置に用いるネットワークのネットワーク領域の包含関係を示す図であり、(b)は本実施例の経路探索装置に用いるネットワークのネットワーク領域をレベル毎に示す図である。
【図3】本実施例の経路探索装置1における処理を示すフローチャートである。
【図4】(a)は本実施例の経路探索装置1における処理を説明するネットワーク領域の包含関係の例を示す図であり、(b)は(a)のネットワーク領域をレベル毎に示す図である。
【図5】本実施例の経路探索装置における処理の第1の例における経路をネットワーク領域の包含関係とともに示す図である。
【図6】本実施例の経路探索装置における処理の第2の例における経路をネットワーク領域の包含関係とともに示す図である。
【図7】本実施例の経路探索装置における処理の第3の例における経路をネットワーク領域の包含関係とともに示す図である。
【図8】本実施例の経路探索装置の構成を示すブロック図である。
【図9】本実施例のネットワークデータ生成装置における処理を示すフローチャートである。
【図10】行き止まり道路領域を設定する処理を説明する図である。
【図11】行き止まり道路領域を設定する処理を説明する図である。
【図12】(a)は各袋小路道路領域の関係を説明する図であり、(b)は(a)のネットワーク領域をレベル毎に示す図である。
【図13】(a)はネットワーク領域を設定する処理を説明する図であり、(b)は(a)のネットワーク領域をレベル毎に示す図である。
【発明を実施するための形態】
【0008】
<本実施例の経路探索装置の構成>
以下、本発明を具体化した実施形態を説明する。まずは、経路探索装置が経路探索する処理について説明する。図1は、本実施例の経路探索装置の構成の一例を示すブロック図である。本実施例における経路探索装置1は、車両に搭載されたカーナビゲーションであり、表示部11、入力器12、計算機13、および地図情報記憶部14を備えている。
【0009】
表示11は、画像表示器のLCDであり、入力器12は、LCDの表示面に設けられた入力デバイスのタッチパネルであり、地図情報記憶部14は、地図情報を記憶した外部記憶装置としてのフラッシュメモリである。
【0010】
地図情報記憶部14が記憶している地図情報は、行政界図、道路図および家形図等を生成するための地図描画用データ、経路探索に利用されるリンクやノード等のネットワークデータ等を含むものである。
【0011】
本実施例のネットワークデータは、リンクおよびノードのデータ、それぞれのリンクおよびノードが属するネットワーク領域の情報、ならびに領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を認識するための情報を含むものである。
【0012】
図2(a)は、本実施例の経路探索装置に用いるネットワークのネットワーク領域の包含関係を示す図である。A,B,C,D,E,F,G,H,Iは、それぞれ複数のリンクおよびノードを含むネットワーク領域を特定する情報を示している。直接の下位レベルのネットワーク領域は上位レベルのネットワーク領域の中に含まれ、同じネットワーク領域を上位レベルとしていても、レベルが同じである下位レベルのネットワーク領域同士は、お互いに重複するリンクおよびノードは存在しない。
【0013】
具体的には、例えば、図2(a)においては、ネットワーク領域Aには、直接の下位レベルにネットワーク領域B,C,D,Eが含まれており、ネットワーク領域B,C,D,Eはお互いに重複するリンクおよびノードは存在しない。さらに、ネットワーク領域Bには、直接の下位レベルにネットワーク領域F,Gが含まれており、ネットワーク領域F,Gはお互いに重複するリンクおよびノードは存在しない。さらにまた、ネットワーク領域Dには、直接の下位レベルにネットワーク領域H,Iが含まれており、ネットワーク領域H,Iはお互いに重複するリンクおよびノードは存在しない。なお、ネットワーク領域F,Gはネットワーク領域Bを介して間接的にネットワーク領域Aの下位レベルに含まれ、ネットワーク領域H,Iはネットワーク領域Dを介して間接的にネットワーク領域Aの下位レベルに含まれている。
【0014】
そして、図2(a)に示されるネットワーク領域A〜Iのうち、ネットワーク領域Aを除くネットワーク領域B〜Iは、ネットワーク領域の外に接続するリンクが1つだけの局所的なネットワーク領域となっている。具体的には、進入リンクが一つしかない袋小路や、先が行き止まりの一本道等のことである。なお、ネットワーク領域の外に接続するリンクが1つだけの状態は、往復可能な1本のリンクに限定するものではなく、一般道を往路および復路に別々に2つのリンクの対として表現したものも含まれる。また、往路の一方通行路と復路の一方通行路とをそれぞれ表現するリンクが対になっているものも含まれる。
【0015】
図2(b)は、本実施例の経路探索装置に用いるネットワークのネットワーク領域をレベル毎に示す図であり、Lv0,Lv1,Lv2は、それぞれのネットワーク領域のレベルの情報を示している。図2(b)に示すように、本例におけるネットワークデータは、ネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されている複数のネットワーク領域からなるものである。そして、各リンクには、ネットワーク領域を特定する情報およびネットワーク領域のレベルの情報がそれぞれ付与されており、下位レベルのネットワーク領域のリンクには直接の上位レベルのネットワーク領域を特定する情報が付与されている。なお、このようなネットワークデータにおけるネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を認識するための情報を含むネットワークデータの更新は、該当するネットワーク領域に限定した範囲で行なえばよい。
【0016】
計算機13は、コンピュータプログラムや処理条件等が予め記憶されているROMやRAM等の内部記憶装置、このコンピュータプログラムを実行するCPU、およびデータの読み書きが可能な小型のハードディスクやフラッシュメモリ等の外部記憶装置を備えた小型のコンピュータである。本例の経路探索装置1における計算機13は、コンピュータプログラムを実行することにより実現される所定の機能を有するユニットを複数備えている。具体的には、計算機13は、地図情報記憶部14に記憶されている地図情報を参照するネットワークデータ参照部131、出発地および目的地を設定する地点設定部132、後述する出発地付近領域および目的地付近領域を設定する地点付近領域設定部133、出発地付近領域および目的地付近領域の包含関係に応じて探索領域を設定する探索領域設定部134、探索領域内に限定して出発地から目的地への経路を探索する経路探索部135を備えている。
【0017】
次に、経路探索装置1が、出発地から目的地までの経路を探索する処理について説明する。
【0018】
<経路探索装置の処理の第1の例>
図3は、本実施例の経路探索装置1における処理を示すフローチャートであり、図4(a)は、本実施例の経路探索装置1における処理を説明するネットワーク領域の包含関係の例を示す図であり、図4(b)は図4(a)のネットワーク領域をレベル毎に示す図であり、図5は、本実施例の経路探索装置1における処理の第1の例における経路をネットワーク領域の包含関係とともに示す図である。
【0019】
図4に示すネットワークデータは、複数のリンクLKおよびノードKNを含む複数のネットワーク領域N11,N21,N22,N23,N31,N32,N33,N34,N35,N36,N41からなるものである。N11,N21,N22,N23,N31,N32,N33,N34,N35,N36,N41はネットワーク領域を特定する情報を示し、Lv0,Lv1,Lv2,Lv3はネットワーク領域のレベルの情報を示す。図4(b)に示すように、最も上位レベルのネットワーク領域N11には、直接の下位レベルにネットワーク領域N21,N22,N23が含まれている。また、ネットワーク領域N21には直接の下位レベルにネットワーク領域N31が含まれ、ネットワーク領域N22には直接の下位レベルにネットワーク領域N32,N33が含まれ、ネットワーク領域N23には直接の下位レベルにネットワーク領域N34,N35,N36が含まれている。さらに、ネットワーク領域N36には直接の下位レベルにネットワーク領域N41が含まれている。なお、ネットワーク領域を特定する情報およびネットワーク領域のレベルの情報は各リンクに属性情報として付与されており、下位レベルのネットワーク領域のリンクには直接の上位レベルのネットワーク領域を特定する情報が付与されている。
【0020】
まず、計算機13は、ネットワークデータ参照部131により、外部記憶装置に記憶されている地図情報のデータベースを参照し、現在地付近の領域に対応する地図描画用データおよびネットワークデータを参照する処理を実行する(ステップS101)。計算機13は、ステップS101が終了すると、参照した地図描画用データに基づいて画面11に地図を表示させておき、タッチパネルにユーザーの指が接触した点の指定を受付ける。しかる後に、計算機13は、地点設定部132により、参照したネットワークデータに含まれるリンク上に、ユーザーが指定した点に対応する出発地SPおよび目的地EPをそれぞれ設定する処理を実行する(ステップS102)。
【0021】
計算機13は、ステップS102が終了すると、地点付近領域設定部133により、出発地SPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、出発地SPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N21から出発地SPを含まないさらに下位レベルのネットワーク領域N31を除いた領域A1を出発地付近領域A1として設定するとともに、目的地EPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、目的地EPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N21からさらに下位レベルのネットワーク領域N31を除いた領域A1を目的地付近領域A1として設定する処理を実行する(ステップS103)。
【0022】
計算機13は、ステップS103が終了すると、探索領域設定部134により、出発地付近領域A1および目的地付近領域A1の包含関係を把握し、把握した包含関係に応じて探索領域を設定する処理を実行する(ステップS104)。具体的には、本例における計算機13は、出発地付近領域A1と目的地付近領域A1とがいずれも同じ領域A1であるため、出発地付近領域A1および目的地付近領域A1に対応する領域A1を探索領域A1として設定する。すなわち、本実施例の経路探索装置1の計算機13は、出発地SPおよび目的地EPをともに含むネットワーク領域のうち最も下位レベルのネットワーク領域N21から、出発地SPおよび目的地EPのいずれも含まないネットワーク領域N31を除いた探索領域A1を設定するものである。
【0023】
計算機13は、ステップS104が終了すると、経路探索部135により、探索領域A1内に限定して出発地SPから目的地EPへ到る経路を、ダイクストラ法をベースにした探索手法により探索し、探索結果として得られた経路R1を設定する処理を実行する(ステップS105)。
【0024】
本実施例の経路探索装置1における処理の第1の例によれば、経路を検索する範囲を、図5に示すように、ネットワーク領域N21から下位レベルのネットワーク領域N31を除いた領域A1に限定することによって、不必要なリンクに向けた探索の枝が伸びなくなるので、経路を探索する処理の高速化を図ることが可能となっている。
【0025】
<経路探索装置の処理の第2の例>
図6は、本実施例の経路探索装置1における処理の第2の例における経路探索をネットワーク領域の包含関係とともに示す図である。本例については、上述した処理の第1の例と異なる点についてのみ説明し、同様の構成要素については同一の参照符を用いて重複する説明を省略するものとする。
【0026】
まず、計算機13は、処理の第2の例においても、処理の第1の例と同様の手順で、ステップS101〜S103の処理を実行する。本例においては、出発地SPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、出発地SPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N41を出発地付近領域N41として設定するとともに、目的地EPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、目的地EPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N23から目的地EPを含まないさらに下位レベルのネットワーク領域N34、N35、N36を除いた領域A21を目的地付近領域A21として設定する。
【0027】
計算機13は、ステップS103が終了すると、探索領域設定部134により、出発地付近領域N41および目的地付近領域A21の包含関係を把握し、把握した包含関係に応じて探索領域を設定する処理を実行する(ステップS104)。具体的には、本例において、出発地付近領域N41および目的地付近領域A21は、互いに異なる領域であるとともに、ネットワーク領域N36のうちネットワーク領域N41を除いた領域A22を介して間接的に包含関係にある。このため、計算機13は、出発地付近領域N41、目的地付近領域A21、ならびに出発地付近領域N41および目的地付近領域A21のうち一方とは上位レベルにあるとともに他方とは下位レベルにあるネットワーク領域A22からなる領域A2を探索領域A2として設定する。別の見方をすると、計算機13は、出発地SPおよび目的地EPを含む最も下位レベルのネットワーク領域N23のうち出発地付近領域N41と目的地付近領域A21との間で直接的にも間接的にも包含関係にないネットワーク領域N34,N35を除く領域A2を探索領域A2として設定する。さらに別の見方をすると、本実施例の経路探索装置1の計算機13は、出発地SPおよび目的地EPをともに含むネットワーク領域のうち最も下位レベルのネットワーク領域N23から、出発地SPおよび目的地EPのいずれも含まないネットワーク領域N34,N35を除いた探索領域A2を設定するものである。
【0028】
計算機13は、ステップS104が終了すると、経路探索部135により、探索領域A2内に限定して出発地SPから目的地EPへの経路R2を探索する処理を実行する(ステップS105)。
【0029】
本実施例の経路探索装置1の処理の第2の例によれば、経路を検索する範囲を、図6に示すように、ネットワーク領域N23から下位レベルのネットワーク領域N34,N35を除いた領域A2に限定することによって、不必要なリンクに向けた探索の枝が伸びなくなるので、経路を探索する処理の高速化を図ることが可能となっている。
【0030】
<経路探索装置の処理の第3の例>
図7は、本実施例の経路探索装置1における処理の第3の例における経路をネットワーク領域の包含関係とともに示す図である。本例については、上述した処理の第1、第2の例と異なる点についてのみ説明し、同様の構成要素については同一の参照符を用いて重複する説明を省略するものとする。
【0031】
まず、計算機13は、処理の第3の例においても、処理の第1、第2の例と同様の手順で、ステップS101〜S103の処理を実行する。本例においては、出発地SPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、出発地SPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N36から出発地SPを含まないさらに下位レベルのネットワーク領域N41を除いた領域A22を出発地付近領域A22として設定するとともに、目的地EPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、目的地EPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N34を目的地付近領域N34として設定する。
【0032】
計算機13は、ステップS103が終了すると、探索領域設定部134により、出発地付近領域A22および目的地付近領域N34の包含関係を把握し、把握した包含関係に応じて探索領域を設定する処理を実行する(ステップS104)。具体的には、本例において、出発地付近領域A22と目的地付近領域N34とは、互いに異なる領域であるとともに、直接的にも間接的にも包含関係にはない。このため、計算機13は、出発地付近領域A22、目的地付近領域N34、ならびに出発地および目的地を含む最も下位レベルのネットワーク領域N23からさらに下位レベルのネットワーク領域N34,N35,N36を除いた領域A21からなる領域A3を探索領域A3として設定する。別の見方をすると、計算機13は、出発地SPおよび目的地EPを含む最も下位レベルのネットワーク領域N23のうちこのネットワーク領域N23と出発地付近領域A22および目的地付近領域N34のそれぞれとの間で直接的にも間接的にも包含関係にないネットワーク領域N35,N41を除く領域A3を探索領域A3として設定する。さらに別の見方をすると、本実施例の経路探索装置1の計算機13は、出発地SPおよび目的地EPをともに含むネットワーク領域のうち最も下位レベルのネットワーク領域N23から、出発地SPおよび目的地EPのいずれも含まないネットワーク領域N35,N41を除いた探索領域A2を設定するものである。
【0033】
計算機13は、ステップS104が終了すると、経路探索部135により、探索領域A3内に限定して出発地SPから目的地EPへの経路R3を探索する処理を実行する(ステップS105)。
【0034】
本実施例の経路探索装置1の処理の第3の例によれば、経路を検索する範囲を、図7に示すように、ネットワーク領域N23から下位レベルのネットワーク領域N35,N41を除いた領域A3に限定することによって、不必要なリンクに向けた探索の枝が伸びなくなるので、経路を探索する処理の高速化を図ることが可能となっている。
【0035】
<ネットワークデータ生成装置の構成>
次に、ネットワークデータ生成装置がネットワークデータを生成する処理について説明する。図8は、本実施例のネットワークデータ生成システムの構成を示すブロック図である。本実施例におけるネットワークデータ生成システム20は、ネットワークデータ生成装置21、原地図情報記憶装置22および生成地図情報記憶装置23を備える。
【0036】
ネットワークデータ生成装置21は、コンピュータプログラムや処理条件等が予め記憶されているROMやRAM等の内部記憶装置、およびこのコンピュータプログラムを実行するCPU等を備えた小型のコンピュータである。原地図情報記憶装置22および生成地図情報記憶装置23は、フラッシュメモリ、ハードディスク、DVDまたはブルーレイディスク等の外部記憶装置である。
【0037】
原地図情報記憶装置22が記憶している原地図情報は、経路探索等に利用されるリンクやノード等のデータを含むネットワークデータであって、ネットワークデータ生成装置21によるネットワークデータの生成に用いられるネットワークデータである。生成地図情報記憶装置23が記憶している生成地図情報は、ネットワークデータ生成装置21が生成したネットワークデータである。
【0038】
また、ネットワークデータ生成装置21は、コンピュータプログラムを実行することにより実現される所定の機能を複数有しており、それぞれの機能に対応するユニットをそれぞれ備えている。具体的には、ネットワークデータ生成装置21は、ネットワークデータ参照部211、局所領域設定部212、基準根設定部213、レベル設定部214を備えている。
【0039】
ネットワークデータ参照部211は、原地図情報記憶装置22に記憶されている地図情報を参照する機能を有している。局所領域設定部212は、ネットワークを構成するリンクおよびノードを含むネットワーク領域であってこのネットワーク領域の外に存在するネットワークに接続するリンクが1つだけの局所的なネットワーク領域およびその局所的なネットワーク領域における出入口リンクまたは出入口ノードを設定する機能を有している。基準根設定部213は、すべてのリンクおよびノードを含む最上位のレベルのネットワーク領域に含まれるネットワークを構成するリンクまたはノードのうち局所的なネットワーク領域を含まないいずれかのリンクまたはノードを選択しネットワーク領域の包含関係を設定するための基準の根として設定する機能を有している。レベル設定部214は、各ネットワーク領域に含まれるネットワークを構成するリンクまたはノードと基準の根との接続状態に基づいて下位レベルのネットワーク領域およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を設定して木構造化されたネットワークデータを生成する機能を有する。
【0040】
このような本実施例のネットワークデータ生成装置21によれば、局所的なネットワーク領域の出入口を設定し、各ネットワーク領域に含まれるネットワークを構成するリンクまたはノードと基準の根との接続状態に基づいてネットワーク領域の包含関係を設定するので、ネットワーク領域の包含関係が漏れなく設定されたネットワークデータを生成することができる。
【0041】
<ネットワークデータ生成装置の処理の例>
図9は、本実施例のネットワークデータ生成装置21の処理を示すフローチャートであり、図10および図11は、行き止まり道路領域を設定する処理を説明する図である。
【0042】
まず、ネットワークデータ生成装置21は、局所領域設定部212により、先が行き止まりの一本道の区間である行き止まり道路領域、およびこの行き止まり道路領域における出入口リンクを設定する処理を実行する(ステップS201)。具体的には、まず、ネットワークデータ生成装置21は、局所領域設定部212により、接続するリンクが1つしかない行き止まりノードを検出し、検出した行き止まりノードを一端として分岐点のノードを他端とする区間のリンクを選択し、この区間のリンクを1つの行き止まり道路領域として検出する。次に、検出した行き止まり道路領域のリンクのうち分岐点のノードに接続するリンクをこの行き止まり道路領域の出入口リンクに設定する。例えば、図10に示すように、リンクL33が行き止まり道路領域N33の出入口リンクL33に設定され、リンクL42が行き止まり道路領域N42の出入口リンクL42に設定され、リンクL43が行き止まり道路領域N43の出入口リンクL43に設定される。
【0043】
検出した行き止まり道路領域は、行き止まり道路領域を検出する対象から除外する。なお、図10に示す、検出した行き止まり道路領域N33,N42,N43を除外すると、図11に示すように、残ったリンクのうち、ノードK55が、接続するリンクが1つの行き止まりノードK55となる。このような場合には、新たに発生した行き止まりノードK55を一端とする行き止まり道路領域N55を検出し、検出する対象から除外する。ネットワークデータ生成装置21は、行き止まりノードが検出されなくなると、ステップS201を終了させる。
【0044】
ネットワークデータ生成装置21は、ステップS201が終了すると、局所領域設定部212により、進入リンクが1つしかない道路網である袋小路道路領域およびこの袋小路道路領域における出入口リンクを設定する処理を実行する(ステップS202)。具体的には、まず、ステップS201で検出した行き止まり道路領域を除外した状態で、袋小路道路領域を設定するための基点となる基点ノードを1つ設定しておいて、基点ノードを出発地とし、基点ノードを目的地とする経路をすべて探索する。
【0045】
図12(a)は、各袋小路道路領域の関係を説明する図である。図12(a)において、行き止まり道路領域は除外されており、ノードKKが基点ノードとして設定されている。図12(a)に示すように、リンクL23を通過した後、もう一度そのリンクL23を通過しないと基点ノードKKに戻れない特定のリンクL23がある場合には、基点ノードKKからみてこの特定のリンクL23から先を袋小路領域N23として検出し、特定のリンクL23を袋小路領域N23の出入口リンクL23に設定する。また、設定した出入口リンクL23の先をさらにたどっていき、基点ノードKKからみて1つの出入口リンクL23を通過した先に、出入口リンクとすべき別の特定のリンクL36が存在する場合は、この出入口リンクから先を新たに1つの袋小路領域N36として検出し、その特定のリンクL36を新たに検出した袋小路領域N36の出入口リンクL36に設定する。図12に示す例においては、袋小路領域N21,N22,N23,N31,N32,N34,N36,N41が検出されている。
【0046】
ネットワークデータ生成装置21は、出入口リンクとすべき特定のリンクが検出されなくなると、ステップS202を終了させる。
【0047】
なお、ステップS201およびステップS202で検出された行き止まり道路領域および袋小路領域はいずれも、全てのリンクおよびノードを含む最上位のレベルのネットワーク領域に対して局所的なネットワーク領域として区別される。
【0048】
以上のように、ステップS201およびステップS202において、ネットワークデータ生成装置21は、局所領域設定部212により、ネットワークを構成するリンクおよびノードを含むネットワーク領域であってこのネットワーク領域の外に存在するネットワークに接続するリンクが1つだけの局所的なネットワーク領域およびその局所的なネットワーク領域における出入口リンクまたは出入口ノードを設定する処理を実行する。
【0049】
ネットワークデータ生成装置21は、ステップS202が終了すると、基準根設定部213により、ネットワークを構成するノードのうちいずれかのノードを選択しネットワーク領域の包含関係を設定するための基準の根として設定する処理を実行する(ステップS203)。具体的には、行き止まり道路領域を除外した状態のネットワークを構成するノードのうちのいずれかのノードを基準の根として設定する。
【0050】
また、本実施例においては、図12(a)に示すように、全てのリンクLKおよびノードKNを含む最上位のレベルのネットワーク領域N11に含まれるネットワークを構成するリンクまたはノードのうち、袋小路道路領域N21,N23,N31,N32,N34,N36,N41を含まないノードのうちの1つのノードKKを基準の根KKとして設定しており、これにより基準の根を選定する範囲がさらに限定されるので、ステップS203の処理がより簡略化されて効率がよくなる。
【0051】
ネットワークデータ生成装置21は、ステップS203が終了すると、レベル設定部214により、行き止まり道路領域として検出された局所的なネットワーク領域を除くネットワークにおいて、各ネットワーク領域に含まれるネットワークを構成するリンクまたはノードと基準の根との接続状態に基づいて下位レベルのネットワーク領域およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を設定する(ステップS204)。具体的には、図12(a)に示すように、袋小路道路領域として検出された局所的なネットワーク領域N23を構成するリンクおよびノードについては、基準の根KKとの接続においては出入口リンクL23を介さなければ基準の根KKと接続しないので、ネットワーク領域N23のレベルを出入口リンクL23よりも基準の根KK側のネットワーク領域に対して格下げする。また、袋小路道路領域として検出された局所的なネットワーク領域N36を構成するリンクおよびノードについては、基準の根KKとの接続においては出入口リンクL36を介さなければ基準の根KKと接続しないので、ネットワーク領域N36のレベルを出入口リンクL36よりも基準の根KK側のネットワーク領域に対して格下げする。
【0052】
図12(b)は(a)のネットワーク領域をレベル毎に示す図である。図12(a)および図12(b)に示す例においては、まず、全てのリンクLKおよびノードKNを含む最上位のレベルのネットワーク領域N11の直接的な下位レベルのネットワーク領域として局所的なネットワーク領域N21,N22,N23が設定されている。また、ネットワーク領域N21の直接的な下位レベルのネットワーク領域として局所的なネットワーク領域N31が設定されている。また、ネットワーク領域N23の直接的な下位レベルのネットワーク領域として局所的なネットワーク領域N34、N36が設定されており、さらに、ネットワーク領域N36の直接的な下位レベルのネットワーク領域として局所的なネットワーク領域N41が設定されている。
【0053】
ネットワークデータ生成装置21は、ステップS204が終了すると、レベル設定部214により、ステップS201において除外されている行き止まり道路領域として検出された局所的なネットワーク領域を、ステップS204までに生成したネットワークに加え、各ネットワーク領域を構成するリンクまたはノードと出入口リンクまたは出入口ノードと基準の根との接続状態に基づいて各ネットワーク領域の包含関係を設定する(ステップS205)。
【0054】
図13(a)はネットワーク領域を設定する処理を説明する図であり、図13(b)は図13(a)のネットワーク領域をレベル毎に示す図である。図13(a)および図13(b)に示すように、行き止まり道路領域として検出された局所的なネットワーク領域N35を構成するリンクおよびノードについては、基準の根KKとの接続においては出入口リンクL35を介さなければ基準の根KKと接続していないので、ネットワーク領域N35のレベルを出入口リンクL35よりも基準の根KK側のネットワーク領域に対して格下げする。なお、本実施例においては、行き止まり道路領域同士が接続する場合は、ネットワーク領域N35のように1つのネットワーク領域としてまとめる処理を実行することにしている。
【0055】
また、行き止まり道路領域として検出された局所的なネットワーク領域N33を構成するリンクおよびノードについては、基準の根KKとの接続においては出入口リンクL33を介さなければ基準の根KKと接続していないので、ネットワーク領域N33のレベルを出入口リンクL33よりも基準の根KK側のネットワーク領域に対して格下げする。なお、この場合、設定したネットワーク領域N33の出入口リンクは、ステップS204で設定したネットワーク領域N22の出入口リンクに接続されている。このため、ネットワーク領域N33をネットワーク領域N22に含めるように設定し、ネットワーク領域N22の下位レベルのネットワーク領域N32を新たに設定する。
【0056】
ステップS204およびステップS205において、ネットワークデータ生成装置21は、レベル設定部214により、各ネットワーク領域に含まれるネットワークを構成するリンクまたはノードと基準の根との接続状態に基づいて下位レベルのネットワーク領域およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を設定して木構造化されたネットワークデータを生成する処理を実行することにより、ネットワークデータを生成する処理が完了する。
【0057】
本実施例のネットワークデータ生成装置21は、レベル設定部214は、基準の根との接続において、特定の出入口リンクまたは出入口ノードを介さなければ基準の根と接続しないリンクおよびノードが属するネットワーク領域のレベルを、特定の出入口リンクまたは出入口ノードよりも基準の根側のネットワーク領域に対して格下げすることによりネットワーク領域同士の包含関係を設定している。したがって、本実施例の経路探索装置のように探索範囲を限定する経路探索に適する、ネットワーク領域の包含関係が木構造化されたネットワークデータが生成されることとなる。
【0058】
<その他の例>
なお、本発明は上述の実施形態の例に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変更、改良が可能である。例えば、上述した実施形態の例においては、経路探索装置1をカーナビゲーションとしているが、このような形態に限定するものではなく、例えば、PND、携帯電話またはPCとすることも可能である。
【0059】
また、上述した実施形態の例においては、入力器12をタッチパネルとしているが、このような形態に限定するものではなく、例えば、キーボードやマウスとすることも可能である。さらに、入力器12をキーボードとした場合、ステップS102において、出発地および目的地をキーボードで入力した後に出発地および目的地を含む範囲の地図を表示させるようにすることも可能である。
【0060】
また、上述した実施形態の例においては、出発地および目的地をリンク上に設定しているが、ノード等の他のネットワークデータ要素に関連させて設定することも可能である。
【0061】
ステップS201の処理においては行き止まり道路領域に出入口リンクを設定する例を示しているが、行き止まり道路領域に出入口ノードを設定することにしてもよい。この場合、出入口リンクに対応するリンクが接続する2つのノードのうち、行き止まりノード側のノードを出入口ノードとして設定する。
【0062】
ステップS202の処理においては袋小路道路領域に出入口リンクを設定する例を示しているが、袋小路道路領域に出入口ノードを設定することにしてもよい。この場合、出入口リンクに対応するリンクが接続する2つのノードのうち、基点ノードから遠い方のノードを出入口ノードとして設定する。
【0063】
ステップS203の処理においてはノードを基準の根として設定しているが、リンクを基準の根に設定することにしてもよい。
【符号の説明】
【0064】
1…経路探索装置
11…表示部
12…入力器
13…計算機
131…ネットワークデータ参照部
132…地点設定部
133…地点付近領域設定部
134…探索領域設定部
135…経路探索部
【技術分野】
【0001】
本発明は、出発地から目的地までの経路を探索する経路探索装置、ネットワークデータのデータ構造、およびネットワークデータ生成装置に関するものである。
【背景技術】
【0002】
従来から、カーナビゲーションデバイスや、携帯して持ち運びすることが可能な、例えばPND(Personal Navigation Device)等に経路探索装置が利用されている。
従来の経路探索装置としては、例えば、道路のネットワークデータを含む地図情報が記憶されているハードディスク等の記憶媒体にアクセスし、所望の地図情報を取得して画面に表示するとともに、出発地から目的地への経路探索・案内を行なうナビゲーション機能を有するものが広く用いられている。また、行き止まりや袋小路等のリンクに行き止まり属性フラグを付与し、この行き止まり属性フラグを参照し、行き止まり属性フラグを有するリンクの先の経路を探索しないようにした経路探索装置も知られている(例えば、特許文献1を参照。)。
上記特許文献1に記載の経路探索装置によれば、出発地から目的地への通行経路になり得ないリンクに探索の枝を伸ばさないようにしているので、経路を探索する処理の時間の短縮を図ることが可能となる。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2000−18958号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、上記特許文献1に記載の経路探索装置は、出発地および目的地を含むパーセル内では行き止まり属性フラグを参照しないことにしているので、出発地および目的地がいずれも袋小路内にある場合であっても、袋小路外の広い領域に経路を探索する枝が伸びることがあり、このような場合には経路を探索する処理の時間が効果的に短縮されないという問題がある。また、上記特許文献1に記載の経路探索装置によれば、目的地が袋小路内にある場合には経路を探索することができないという問題がある。
すなわち、上記特許文献1に記載の経路探索装置は、袋小路の内側に出発地や目的地がある場合に経路を探索する処理において課題を有している。
本発明は、出発地および目的地の位置に応じて経路を検索する範囲を限定することにより、経路を探索する処理の高速化を図ることを可能とした経路探索装置およびネットワークデータを提供することを目的とする。
【課題を解決するための手段】
【0005】
上記課題を解決するために、本発明の経路探索装置は、複数のリンクおよびノードを含むネットワーク領域であって該ネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および該下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されている複数のネットワーク領域からなるネットワークデータを参照するネットワークデータ参照部と、前記ネットワークデータに含まれるリンクまたはノード上に出発地および目的地をそれぞれ設定する地点設定部と、前記出発地および前記目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、前記出発地および前記目的地のいずれも含まないネットワーク領域を除いた探索領域を設定する探索領域設定部と、前記探索領域内に限定して前記出発地から前記目的地への経路を探索する経路探索部とを備えることを特徴とするものである。
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成(または方法)もまた発明となり得る。
【発明の効果】
【0006】
本発明の経路探索装置は、複数のリンクおよびノードを含むネットワーク領域であってネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されたネットワークデータを参照し、出発地および目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、出発地および目的地のいずれも含まないネットワーク領域を除いた探索領域を設定して経路を探索している。従って、本発明の経路探索装置によれば、出発地および目的地の位置に応じて経路を検索する範囲を限定することによって、不必要なリンクに向けた探索の枝が伸びなくなるので、経路を探索する処理の高速化を図ることが可能となる。
【図面の簡単な説明】
【0007】
【図1】本実施例の経路探索装置の構成を示すブロック図である。
【図2】(a)は本実施例の経路探索装置に用いるネットワークのネットワーク領域の包含関係を示す図であり、(b)は本実施例の経路探索装置に用いるネットワークのネットワーク領域をレベル毎に示す図である。
【図3】本実施例の経路探索装置1における処理を示すフローチャートである。
【図4】(a)は本実施例の経路探索装置1における処理を説明するネットワーク領域の包含関係の例を示す図であり、(b)は(a)のネットワーク領域をレベル毎に示す図である。
【図5】本実施例の経路探索装置における処理の第1の例における経路をネットワーク領域の包含関係とともに示す図である。
【図6】本実施例の経路探索装置における処理の第2の例における経路をネットワーク領域の包含関係とともに示す図である。
【図7】本実施例の経路探索装置における処理の第3の例における経路をネットワーク領域の包含関係とともに示す図である。
【図8】本実施例の経路探索装置の構成を示すブロック図である。
【図9】本実施例のネットワークデータ生成装置における処理を示すフローチャートである。
【図10】行き止まり道路領域を設定する処理を説明する図である。
【図11】行き止まり道路領域を設定する処理を説明する図である。
【図12】(a)は各袋小路道路領域の関係を説明する図であり、(b)は(a)のネットワーク領域をレベル毎に示す図である。
【図13】(a)はネットワーク領域を設定する処理を説明する図であり、(b)は(a)のネットワーク領域をレベル毎に示す図である。
【発明を実施するための形態】
【0008】
<本実施例の経路探索装置の構成>
以下、本発明を具体化した実施形態を説明する。まずは、経路探索装置が経路探索する処理について説明する。図1は、本実施例の経路探索装置の構成の一例を示すブロック図である。本実施例における経路探索装置1は、車両に搭載されたカーナビゲーションであり、表示部11、入力器12、計算機13、および地図情報記憶部14を備えている。
【0009】
表示11は、画像表示器のLCDであり、入力器12は、LCDの表示面に設けられた入力デバイスのタッチパネルであり、地図情報記憶部14は、地図情報を記憶した外部記憶装置としてのフラッシュメモリである。
【0010】
地図情報記憶部14が記憶している地図情報は、行政界図、道路図および家形図等を生成するための地図描画用データ、経路探索に利用されるリンクやノード等のネットワークデータ等を含むものである。
【0011】
本実施例のネットワークデータは、リンクおよびノードのデータ、それぞれのリンクおよびノードが属するネットワーク領域の情報、ならびに領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を認識するための情報を含むものである。
【0012】
図2(a)は、本実施例の経路探索装置に用いるネットワークのネットワーク領域の包含関係を示す図である。A,B,C,D,E,F,G,H,Iは、それぞれ複数のリンクおよびノードを含むネットワーク領域を特定する情報を示している。直接の下位レベルのネットワーク領域は上位レベルのネットワーク領域の中に含まれ、同じネットワーク領域を上位レベルとしていても、レベルが同じである下位レベルのネットワーク領域同士は、お互いに重複するリンクおよびノードは存在しない。
【0013】
具体的には、例えば、図2(a)においては、ネットワーク領域Aには、直接の下位レベルにネットワーク領域B,C,D,Eが含まれており、ネットワーク領域B,C,D,Eはお互いに重複するリンクおよびノードは存在しない。さらに、ネットワーク領域Bには、直接の下位レベルにネットワーク領域F,Gが含まれており、ネットワーク領域F,Gはお互いに重複するリンクおよびノードは存在しない。さらにまた、ネットワーク領域Dには、直接の下位レベルにネットワーク領域H,Iが含まれており、ネットワーク領域H,Iはお互いに重複するリンクおよびノードは存在しない。なお、ネットワーク領域F,Gはネットワーク領域Bを介して間接的にネットワーク領域Aの下位レベルに含まれ、ネットワーク領域H,Iはネットワーク領域Dを介して間接的にネットワーク領域Aの下位レベルに含まれている。
【0014】
そして、図2(a)に示されるネットワーク領域A〜Iのうち、ネットワーク領域Aを除くネットワーク領域B〜Iは、ネットワーク領域の外に接続するリンクが1つだけの局所的なネットワーク領域となっている。具体的には、進入リンクが一つしかない袋小路や、先が行き止まりの一本道等のことである。なお、ネットワーク領域の外に接続するリンクが1つだけの状態は、往復可能な1本のリンクに限定するものではなく、一般道を往路および復路に別々に2つのリンクの対として表現したものも含まれる。また、往路の一方通行路と復路の一方通行路とをそれぞれ表現するリンクが対になっているものも含まれる。
【0015】
図2(b)は、本実施例の経路探索装置に用いるネットワークのネットワーク領域をレベル毎に示す図であり、Lv0,Lv1,Lv2は、それぞれのネットワーク領域のレベルの情報を示している。図2(b)に示すように、本例におけるネットワークデータは、ネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されている複数のネットワーク領域からなるものである。そして、各リンクには、ネットワーク領域を特定する情報およびネットワーク領域のレベルの情報がそれぞれ付与されており、下位レベルのネットワーク領域のリンクには直接の上位レベルのネットワーク領域を特定する情報が付与されている。なお、このようなネットワークデータにおけるネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を認識するための情報を含むネットワークデータの更新は、該当するネットワーク領域に限定した範囲で行なえばよい。
【0016】
計算機13は、コンピュータプログラムや処理条件等が予め記憶されているROMやRAM等の内部記憶装置、このコンピュータプログラムを実行するCPU、およびデータの読み書きが可能な小型のハードディスクやフラッシュメモリ等の外部記憶装置を備えた小型のコンピュータである。本例の経路探索装置1における計算機13は、コンピュータプログラムを実行することにより実現される所定の機能を有するユニットを複数備えている。具体的には、計算機13は、地図情報記憶部14に記憶されている地図情報を参照するネットワークデータ参照部131、出発地および目的地を設定する地点設定部132、後述する出発地付近領域および目的地付近領域を設定する地点付近領域設定部133、出発地付近領域および目的地付近領域の包含関係に応じて探索領域を設定する探索領域設定部134、探索領域内に限定して出発地から目的地への経路を探索する経路探索部135を備えている。
【0017】
次に、経路探索装置1が、出発地から目的地までの経路を探索する処理について説明する。
【0018】
<経路探索装置の処理の第1の例>
図3は、本実施例の経路探索装置1における処理を示すフローチャートであり、図4(a)は、本実施例の経路探索装置1における処理を説明するネットワーク領域の包含関係の例を示す図であり、図4(b)は図4(a)のネットワーク領域をレベル毎に示す図であり、図5は、本実施例の経路探索装置1における処理の第1の例における経路をネットワーク領域の包含関係とともに示す図である。
【0019】
図4に示すネットワークデータは、複数のリンクLKおよびノードKNを含む複数のネットワーク領域N11,N21,N22,N23,N31,N32,N33,N34,N35,N36,N41からなるものである。N11,N21,N22,N23,N31,N32,N33,N34,N35,N36,N41はネットワーク領域を特定する情報を示し、Lv0,Lv1,Lv2,Lv3はネットワーク領域のレベルの情報を示す。図4(b)に示すように、最も上位レベルのネットワーク領域N11には、直接の下位レベルにネットワーク領域N21,N22,N23が含まれている。また、ネットワーク領域N21には直接の下位レベルにネットワーク領域N31が含まれ、ネットワーク領域N22には直接の下位レベルにネットワーク領域N32,N33が含まれ、ネットワーク領域N23には直接の下位レベルにネットワーク領域N34,N35,N36が含まれている。さらに、ネットワーク領域N36には直接の下位レベルにネットワーク領域N41が含まれている。なお、ネットワーク領域を特定する情報およびネットワーク領域のレベルの情報は各リンクに属性情報として付与されており、下位レベルのネットワーク領域のリンクには直接の上位レベルのネットワーク領域を特定する情報が付与されている。
【0020】
まず、計算機13は、ネットワークデータ参照部131により、外部記憶装置に記憶されている地図情報のデータベースを参照し、現在地付近の領域に対応する地図描画用データおよびネットワークデータを参照する処理を実行する(ステップS101)。計算機13は、ステップS101が終了すると、参照した地図描画用データに基づいて画面11に地図を表示させておき、タッチパネルにユーザーの指が接触した点の指定を受付ける。しかる後に、計算機13は、地点設定部132により、参照したネットワークデータに含まれるリンク上に、ユーザーが指定した点に対応する出発地SPおよび目的地EPをそれぞれ設定する処理を実行する(ステップS102)。
【0021】
計算機13は、ステップS102が終了すると、地点付近領域設定部133により、出発地SPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、出発地SPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N21から出発地SPを含まないさらに下位レベルのネットワーク領域N31を除いた領域A1を出発地付近領域A1として設定するとともに、目的地EPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、目的地EPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N21からさらに下位レベルのネットワーク領域N31を除いた領域A1を目的地付近領域A1として設定する処理を実行する(ステップS103)。
【0022】
計算機13は、ステップS103が終了すると、探索領域設定部134により、出発地付近領域A1および目的地付近領域A1の包含関係を把握し、把握した包含関係に応じて探索領域を設定する処理を実行する(ステップS104)。具体的には、本例における計算機13は、出発地付近領域A1と目的地付近領域A1とがいずれも同じ領域A1であるため、出発地付近領域A1および目的地付近領域A1に対応する領域A1を探索領域A1として設定する。すなわち、本実施例の経路探索装置1の計算機13は、出発地SPおよび目的地EPをともに含むネットワーク領域のうち最も下位レベルのネットワーク領域N21から、出発地SPおよび目的地EPのいずれも含まないネットワーク領域N31を除いた探索領域A1を設定するものである。
【0023】
計算機13は、ステップS104が終了すると、経路探索部135により、探索領域A1内に限定して出発地SPから目的地EPへ到る経路を、ダイクストラ法をベースにした探索手法により探索し、探索結果として得られた経路R1を設定する処理を実行する(ステップS105)。
【0024】
本実施例の経路探索装置1における処理の第1の例によれば、経路を検索する範囲を、図5に示すように、ネットワーク領域N21から下位レベルのネットワーク領域N31を除いた領域A1に限定することによって、不必要なリンクに向けた探索の枝が伸びなくなるので、経路を探索する処理の高速化を図ることが可能となっている。
【0025】
<経路探索装置の処理の第2の例>
図6は、本実施例の経路探索装置1における処理の第2の例における経路探索をネットワーク領域の包含関係とともに示す図である。本例については、上述した処理の第1の例と異なる点についてのみ説明し、同様の構成要素については同一の参照符を用いて重複する説明を省略するものとする。
【0026】
まず、計算機13は、処理の第2の例においても、処理の第1の例と同様の手順で、ステップS101〜S103の処理を実行する。本例においては、出発地SPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、出発地SPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N41を出発地付近領域N41として設定するとともに、目的地EPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、目的地EPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N23から目的地EPを含まないさらに下位レベルのネットワーク領域N34、N35、N36を除いた領域A21を目的地付近領域A21として設定する。
【0027】
計算機13は、ステップS103が終了すると、探索領域設定部134により、出発地付近領域N41および目的地付近領域A21の包含関係を把握し、把握した包含関係に応じて探索領域を設定する処理を実行する(ステップS104)。具体的には、本例において、出発地付近領域N41および目的地付近領域A21は、互いに異なる領域であるとともに、ネットワーク領域N36のうちネットワーク領域N41を除いた領域A22を介して間接的に包含関係にある。このため、計算機13は、出発地付近領域N41、目的地付近領域A21、ならびに出発地付近領域N41および目的地付近領域A21のうち一方とは上位レベルにあるとともに他方とは下位レベルにあるネットワーク領域A22からなる領域A2を探索領域A2として設定する。別の見方をすると、計算機13は、出発地SPおよび目的地EPを含む最も下位レベルのネットワーク領域N23のうち出発地付近領域N41と目的地付近領域A21との間で直接的にも間接的にも包含関係にないネットワーク領域N34,N35を除く領域A2を探索領域A2として設定する。さらに別の見方をすると、本実施例の経路探索装置1の計算機13は、出発地SPおよび目的地EPをともに含むネットワーク領域のうち最も下位レベルのネットワーク領域N23から、出発地SPおよび目的地EPのいずれも含まないネットワーク領域N34,N35を除いた探索領域A2を設定するものである。
【0028】
計算機13は、ステップS104が終了すると、経路探索部135により、探索領域A2内に限定して出発地SPから目的地EPへの経路R2を探索する処理を実行する(ステップS105)。
【0029】
本実施例の経路探索装置1の処理の第2の例によれば、経路を検索する範囲を、図6に示すように、ネットワーク領域N23から下位レベルのネットワーク領域N34,N35を除いた領域A2に限定することによって、不必要なリンクに向けた探索の枝が伸びなくなるので、経路を探索する処理の高速化を図ることが可能となっている。
【0030】
<経路探索装置の処理の第3の例>
図7は、本実施例の経路探索装置1における処理の第3の例における経路をネットワーク領域の包含関係とともに示す図である。本例については、上述した処理の第1、第2の例と異なる点についてのみ説明し、同様の構成要素については同一の参照符を用いて重複する説明を省略するものとする。
【0031】
まず、計算機13は、処理の第3の例においても、処理の第1、第2の例と同様の手順で、ステップS101〜S103の処理を実行する。本例においては、出発地SPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、出発地SPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N36から出発地SPを含まないさらに下位レベルのネットワーク領域N41を除いた領域A22を出発地付近領域A22として設定するとともに、目的地EPが設定されているリンクに付与されているネットワーク領域を特定する情報およびネットワーク領域のレベルの情報に基づいて、目的地EPを含むネットワーク領域のうち最も下位レベルのネットワーク領域N34を目的地付近領域N34として設定する。
【0032】
計算機13は、ステップS103が終了すると、探索領域設定部134により、出発地付近領域A22および目的地付近領域N34の包含関係を把握し、把握した包含関係に応じて探索領域を設定する処理を実行する(ステップS104)。具体的には、本例において、出発地付近領域A22と目的地付近領域N34とは、互いに異なる領域であるとともに、直接的にも間接的にも包含関係にはない。このため、計算機13は、出発地付近領域A22、目的地付近領域N34、ならびに出発地および目的地を含む最も下位レベルのネットワーク領域N23からさらに下位レベルのネットワーク領域N34,N35,N36を除いた領域A21からなる領域A3を探索領域A3として設定する。別の見方をすると、計算機13は、出発地SPおよび目的地EPを含む最も下位レベルのネットワーク領域N23のうちこのネットワーク領域N23と出発地付近領域A22および目的地付近領域N34のそれぞれとの間で直接的にも間接的にも包含関係にないネットワーク領域N35,N41を除く領域A3を探索領域A3として設定する。さらに別の見方をすると、本実施例の経路探索装置1の計算機13は、出発地SPおよび目的地EPをともに含むネットワーク領域のうち最も下位レベルのネットワーク領域N23から、出発地SPおよび目的地EPのいずれも含まないネットワーク領域N35,N41を除いた探索領域A2を設定するものである。
【0033】
計算機13は、ステップS104が終了すると、経路探索部135により、探索領域A3内に限定して出発地SPから目的地EPへの経路R3を探索する処理を実行する(ステップS105)。
【0034】
本実施例の経路探索装置1の処理の第3の例によれば、経路を検索する範囲を、図7に示すように、ネットワーク領域N23から下位レベルのネットワーク領域N35,N41を除いた領域A3に限定することによって、不必要なリンクに向けた探索の枝が伸びなくなるので、経路を探索する処理の高速化を図ることが可能となっている。
【0035】
<ネットワークデータ生成装置の構成>
次に、ネットワークデータ生成装置がネットワークデータを生成する処理について説明する。図8は、本実施例のネットワークデータ生成システムの構成を示すブロック図である。本実施例におけるネットワークデータ生成システム20は、ネットワークデータ生成装置21、原地図情報記憶装置22および生成地図情報記憶装置23を備える。
【0036】
ネットワークデータ生成装置21は、コンピュータプログラムや処理条件等が予め記憶されているROMやRAM等の内部記憶装置、およびこのコンピュータプログラムを実行するCPU等を備えた小型のコンピュータである。原地図情報記憶装置22および生成地図情報記憶装置23は、フラッシュメモリ、ハードディスク、DVDまたはブルーレイディスク等の外部記憶装置である。
【0037】
原地図情報記憶装置22が記憶している原地図情報は、経路探索等に利用されるリンクやノード等のデータを含むネットワークデータであって、ネットワークデータ生成装置21によるネットワークデータの生成に用いられるネットワークデータである。生成地図情報記憶装置23が記憶している生成地図情報は、ネットワークデータ生成装置21が生成したネットワークデータである。
【0038】
また、ネットワークデータ生成装置21は、コンピュータプログラムを実行することにより実現される所定の機能を複数有しており、それぞれの機能に対応するユニットをそれぞれ備えている。具体的には、ネットワークデータ生成装置21は、ネットワークデータ参照部211、局所領域設定部212、基準根設定部213、レベル設定部214を備えている。
【0039】
ネットワークデータ参照部211は、原地図情報記憶装置22に記憶されている地図情報を参照する機能を有している。局所領域設定部212は、ネットワークを構成するリンクおよびノードを含むネットワーク領域であってこのネットワーク領域の外に存在するネットワークに接続するリンクが1つだけの局所的なネットワーク領域およびその局所的なネットワーク領域における出入口リンクまたは出入口ノードを設定する機能を有している。基準根設定部213は、すべてのリンクおよびノードを含む最上位のレベルのネットワーク領域に含まれるネットワークを構成するリンクまたはノードのうち局所的なネットワーク領域を含まないいずれかのリンクまたはノードを選択しネットワーク領域の包含関係を設定するための基準の根として設定する機能を有している。レベル設定部214は、各ネットワーク領域に含まれるネットワークを構成するリンクまたはノードと基準の根との接続状態に基づいて下位レベルのネットワーク領域およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を設定して木構造化されたネットワークデータを生成する機能を有する。
【0040】
このような本実施例のネットワークデータ生成装置21によれば、局所的なネットワーク領域の出入口を設定し、各ネットワーク領域に含まれるネットワークを構成するリンクまたはノードと基準の根との接続状態に基づいてネットワーク領域の包含関係を設定するので、ネットワーク領域の包含関係が漏れなく設定されたネットワークデータを生成することができる。
【0041】
<ネットワークデータ生成装置の処理の例>
図9は、本実施例のネットワークデータ生成装置21の処理を示すフローチャートであり、図10および図11は、行き止まり道路領域を設定する処理を説明する図である。
【0042】
まず、ネットワークデータ生成装置21は、局所領域設定部212により、先が行き止まりの一本道の区間である行き止まり道路領域、およびこの行き止まり道路領域における出入口リンクを設定する処理を実行する(ステップS201)。具体的には、まず、ネットワークデータ生成装置21は、局所領域設定部212により、接続するリンクが1つしかない行き止まりノードを検出し、検出した行き止まりノードを一端として分岐点のノードを他端とする区間のリンクを選択し、この区間のリンクを1つの行き止まり道路領域として検出する。次に、検出した行き止まり道路領域のリンクのうち分岐点のノードに接続するリンクをこの行き止まり道路領域の出入口リンクに設定する。例えば、図10に示すように、リンクL33が行き止まり道路領域N33の出入口リンクL33に設定され、リンクL42が行き止まり道路領域N42の出入口リンクL42に設定され、リンクL43が行き止まり道路領域N43の出入口リンクL43に設定される。
【0043】
検出した行き止まり道路領域は、行き止まり道路領域を検出する対象から除外する。なお、図10に示す、検出した行き止まり道路領域N33,N42,N43を除外すると、図11に示すように、残ったリンクのうち、ノードK55が、接続するリンクが1つの行き止まりノードK55となる。このような場合には、新たに発生した行き止まりノードK55を一端とする行き止まり道路領域N55を検出し、検出する対象から除外する。ネットワークデータ生成装置21は、行き止まりノードが検出されなくなると、ステップS201を終了させる。
【0044】
ネットワークデータ生成装置21は、ステップS201が終了すると、局所領域設定部212により、進入リンクが1つしかない道路網である袋小路道路領域およびこの袋小路道路領域における出入口リンクを設定する処理を実行する(ステップS202)。具体的には、まず、ステップS201で検出した行き止まり道路領域を除外した状態で、袋小路道路領域を設定するための基点となる基点ノードを1つ設定しておいて、基点ノードを出発地とし、基点ノードを目的地とする経路をすべて探索する。
【0045】
図12(a)は、各袋小路道路領域の関係を説明する図である。図12(a)において、行き止まり道路領域は除外されており、ノードKKが基点ノードとして設定されている。図12(a)に示すように、リンクL23を通過した後、もう一度そのリンクL23を通過しないと基点ノードKKに戻れない特定のリンクL23がある場合には、基点ノードKKからみてこの特定のリンクL23から先を袋小路領域N23として検出し、特定のリンクL23を袋小路領域N23の出入口リンクL23に設定する。また、設定した出入口リンクL23の先をさらにたどっていき、基点ノードKKからみて1つの出入口リンクL23を通過した先に、出入口リンクとすべき別の特定のリンクL36が存在する場合は、この出入口リンクから先を新たに1つの袋小路領域N36として検出し、その特定のリンクL36を新たに検出した袋小路領域N36の出入口リンクL36に設定する。図12に示す例においては、袋小路領域N21,N22,N23,N31,N32,N34,N36,N41が検出されている。
【0046】
ネットワークデータ生成装置21は、出入口リンクとすべき特定のリンクが検出されなくなると、ステップS202を終了させる。
【0047】
なお、ステップS201およびステップS202で検出された行き止まり道路領域および袋小路領域はいずれも、全てのリンクおよびノードを含む最上位のレベルのネットワーク領域に対して局所的なネットワーク領域として区別される。
【0048】
以上のように、ステップS201およびステップS202において、ネットワークデータ生成装置21は、局所領域設定部212により、ネットワークを構成するリンクおよびノードを含むネットワーク領域であってこのネットワーク領域の外に存在するネットワークに接続するリンクが1つだけの局所的なネットワーク領域およびその局所的なネットワーク領域における出入口リンクまたは出入口ノードを設定する処理を実行する。
【0049】
ネットワークデータ生成装置21は、ステップS202が終了すると、基準根設定部213により、ネットワークを構成するノードのうちいずれかのノードを選択しネットワーク領域の包含関係を設定するための基準の根として設定する処理を実行する(ステップS203)。具体的には、行き止まり道路領域を除外した状態のネットワークを構成するノードのうちのいずれかのノードを基準の根として設定する。
【0050】
また、本実施例においては、図12(a)に示すように、全てのリンクLKおよびノードKNを含む最上位のレベルのネットワーク領域N11に含まれるネットワークを構成するリンクまたはノードのうち、袋小路道路領域N21,N23,N31,N32,N34,N36,N41を含まないノードのうちの1つのノードKKを基準の根KKとして設定しており、これにより基準の根を選定する範囲がさらに限定されるので、ステップS203の処理がより簡略化されて効率がよくなる。
【0051】
ネットワークデータ生成装置21は、ステップS203が終了すると、レベル設定部214により、行き止まり道路領域として検出された局所的なネットワーク領域を除くネットワークにおいて、各ネットワーク領域に含まれるネットワークを構成するリンクまたはノードと基準の根との接続状態に基づいて下位レベルのネットワーク領域およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を設定する(ステップS204)。具体的には、図12(a)に示すように、袋小路道路領域として検出された局所的なネットワーク領域N23を構成するリンクおよびノードについては、基準の根KKとの接続においては出入口リンクL23を介さなければ基準の根KKと接続しないので、ネットワーク領域N23のレベルを出入口リンクL23よりも基準の根KK側のネットワーク領域に対して格下げする。また、袋小路道路領域として検出された局所的なネットワーク領域N36を構成するリンクおよびノードについては、基準の根KKとの接続においては出入口リンクL36を介さなければ基準の根KKと接続しないので、ネットワーク領域N36のレベルを出入口リンクL36よりも基準の根KK側のネットワーク領域に対して格下げする。
【0052】
図12(b)は(a)のネットワーク領域をレベル毎に示す図である。図12(a)および図12(b)に示す例においては、まず、全てのリンクLKおよびノードKNを含む最上位のレベルのネットワーク領域N11の直接的な下位レベルのネットワーク領域として局所的なネットワーク領域N21,N22,N23が設定されている。また、ネットワーク領域N21の直接的な下位レベルのネットワーク領域として局所的なネットワーク領域N31が設定されている。また、ネットワーク領域N23の直接的な下位レベルのネットワーク領域として局所的なネットワーク領域N34、N36が設定されており、さらに、ネットワーク領域N36の直接的な下位レベルのネットワーク領域として局所的なネットワーク領域N41が設定されている。
【0053】
ネットワークデータ生成装置21は、ステップS204が終了すると、レベル設定部214により、ステップS201において除外されている行き止まり道路領域として検出された局所的なネットワーク領域を、ステップS204までに生成したネットワークに加え、各ネットワーク領域を構成するリンクまたはノードと出入口リンクまたは出入口ノードと基準の根との接続状態に基づいて各ネットワーク領域の包含関係を設定する(ステップS205)。
【0054】
図13(a)はネットワーク領域を設定する処理を説明する図であり、図13(b)は図13(a)のネットワーク領域をレベル毎に示す図である。図13(a)および図13(b)に示すように、行き止まり道路領域として検出された局所的なネットワーク領域N35を構成するリンクおよびノードについては、基準の根KKとの接続においては出入口リンクL35を介さなければ基準の根KKと接続していないので、ネットワーク領域N35のレベルを出入口リンクL35よりも基準の根KK側のネットワーク領域に対して格下げする。なお、本実施例においては、行き止まり道路領域同士が接続する場合は、ネットワーク領域N35のように1つのネットワーク領域としてまとめる処理を実行することにしている。
【0055】
また、行き止まり道路領域として検出された局所的なネットワーク領域N33を構成するリンクおよびノードについては、基準の根KKとの接続においては出入口リンクL33を介さなければ基準の根KKと接続していないので、ネットワーク領域N33のレベルを出入口リンクL33よりも基準の根KK側のネットワーク領域に対して格下げする。なお、この場合、設定したネットワーク領域N33の出入口リンクは、ステップS204で設定したネットワーク領域N22の出入口リンクに接続されている。このため、ネットワーク領域N33をネットワーク領域N22に含めるように設定し、ネットワーク領域N22の下位レベルのネットワーク領域N32を新たに設定する。
【0056】
ステップS204およびステップS205において、ネットワークデータ生成装置21は、レベル設定部214により、各ネットワーク領域に含まれるネットワークを構成するリンクまたはノードと基準の根との接続状態に基づいて下位レベルのネットワーク領域およびこの下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を設定して木構造化されたネットワークデータを生成する処理を実行することにより、ネットワークデータを生成する処理が完了する。
【0057】
本実施例のネットワークデータ生成装置21は、レベル設定部214は、基準の根との接続において、特定の出入口リンクまたは出入口ノードを介さなければ基準の根と接続しないリンクおよびノードが属するネットワーク領域のレベルを、特定の出入口リンクまたは出入口ノードよりも基準の根側のネットワーク領域に対して格下げすることによりネットワーク領域同士の包含関係を設定している。したがって、本実施例の経路探索装置のように探索範囲を限定する経路探索に適する、ネットワーク領域の包含関係が木構造化されたネットワークデータが生成されることとなる。
【0058】
<その他の例>
なお、本発明は上述の実施形態の例に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変更、改良が可能である。例えば、上述した実施形態の例においては、経路探索装置1をカーナビゲーションとしているが、このような形態に限定するものではなく、例えば、PND、携帯電話またはPCとすることも可能である。
【0059】
また、上述した実施形態の例においては、入力器12をタッチパネルとしているが、このような形態に限定するものではなく、例えば、キーボードやマウスとすることも可能である。さらに、入力器12をキーボードとした場合、ステップS102において、出発地および目的地をキーボードで入力した後に出発地および目的地を含む範囲の地図を表示させるようにすることも可能である。
【0060】
また、上述した実施形態の例においては、出発地および目的地をリンク上に設定しているが、ノード等の他のネットワークデータ要素に関連させて設定することも可能である。
【0061】
ステップS201の処理においては行き止まり道路領域に出入口リンクを設定する例を示しているが、行き止まり道路領域に出入口ノードを設定することにしてもよい。この場合、出入口リンクに対応するリンクが接続する2つのノードのうち、行き止まりノード側のノードを出入口ノードとして設定する。
【0062】
ステップS202の処理においては袋小路道路領域に出入口リンクを設定する例を示しているが、袋小路道路領域に出入口ノードを設定することにしてもよい。この場合、出入口リンクに対応するリンクが接続する2つのノードのうち、基点ノードから遠い方のノードを出入口ノードとして設定する。
【0063】
ステップS203の処理においてはノードを基準の根として設定しているが、リンクを基準の根に設定することにしてもよい。
【符号の説明】
【0064】
1…経路探索装置
11…表示部
12…入力器
13…計算機
131…ネットワークデータ参照部
132…地点設定部
133…地点付近領域設定部
134…探索領域設定部
135…経路探索部
【特許請求の範囲】
【請求項1】
複数のリンクおよびノードを含むネットワーク領域であって該ネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および該下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されている複数のネットワーク領域からなるネットワークデータを参照するネットワークデータ参照部と、
前記ネットワークデータに含まれるリンクまたはノード上に出発地および目的地をそれぞれ設定する地点設定部と、
前記出発地および前記目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、前記出発地および前記目的地のいずれも含まないネットワーク領域を除いた探索領域を設定する探索領域設定部と、
前記探索領域内に限定して前記出発地から前記目的地への経路を探索する経路探索部と
を備える経路探索装置。
【請求項2】
コンピュータが経路を探索する処理を実行する際に用いられるネットワークデータのデータ構造であって、
前記ネットワークデータに含まれるリンクおよびノードのデータ、それぞれの前記リンクおよび前記ノードが属するネットワーク領域の情報、ならびに領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および該下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を認識するための情報を含み、
前記ネットワーク領域の包含関係を認識するための情報は、
コンピュータが、出発地および目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、前記出発地および前記目的地のいずれも含まないネットワーク領域を除いた探索領域を設定し、
前記コンピュータが前記探索領域内に限定して前記出発地から前記目的地への経路を探索する経路探索処理に用いられるネットワークデータのデータ構造。
【請求項3】
ネットワークを構成するリンクおよびノードを含むネットワーク領域であって該ネットワーク領域の外に存在するネットワークに接続するリンクが1つだけの局所的なネットワーク領域における出入口リンクまたは出入口ノードを設定する局所領域設定部と、
すべてのリンクおよびノードを含む最上位のレベルのネットワーク領域に含まれるネットワークを構成するリンクまたはノードのうちいずれかのリンクまたはノードを選択しネットワーク領域の包含関係を設定するための基準の根として設定する基準根設定部と、
各ネットワーク領域を構成するリンクまたはノードと出入口リンクまたは出入口ノードと前記基準の根との接続状態に基づいて各ネットワーク領域の包含関係を設定して木構造化されたネットワークデータを生成するレベル設定部と
を備えるネットワークデータ生成装置。
【請求項4】
前記レベル設定部は、前記基準の根との接続において、特定の出入口リンクまたは出入口ノードを介さなければ前記基準の根と接続しないリンクおよびノードが属するネットワーク領域のレベルを、前記特定の出入口リンクまたは出入口ノードよりも前記基準の根側のネットワーク領域に対して格下げすることによりネットワーク領域同士の包含関係を設定することを特徴とする請求項3に記載のネットワークデータ生成装置。
【請求項1】
複数のリンクおよびノードを含むネットワーク領域であって該ネットワーク領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および該下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係が木構造化されている複数のネットワーク領域からなるネットワークデータを参照するネットワークデータ参照部と、
前記ネットワークデータに含まれるリンクまたはノード上に出発地および目的地をそれぞれ設定する地点設定部と、
前記出発地および前記目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、前記出発地および前記目的地のいずれも含まないネットワーク領域を除いた探索領域を設定する探索領域設定部と、
前記探索領域内に限定して前記出発地から前記目的地への経路を探索する経路探索部と
を備える経路探索装置。
【請求項2】
コンピュータが経路を探索する処理を実行する際に用いられるネットワークデータのデータ構造であって、
前記ネットワークデータに含まれるリンクおよびノードのデータ、それぞれの前記リンクおよび前記ノードが属するネットワーク領域の情報、ならびに領域の外に接続するリンクが1つだけの下位レベルのネットワーク領域、および該下位レベルのネットワーク領域を含む上位レベルのネットワーク領域の包含関係を認識するための情報を含み、
前記ネットワーク領域の包含関係を認識するための情報は、
コンピュータが、出発地および目的地をともに含むネットワーク領域のうち最も下位レベルのネットワーク領域から、前記出発地および前記目的地のいずれも含まないネットワーク領域を除いた探索領域を設定し、
前記コンピュータが前記探索領域内に限定して前記出発地から前記目的地への経路を探索する経路探索処理に用いられるネットワークデータのデータ構造。
【請求項3】
ネットワークを構成するリンクおよびノードを含むネットワーク領域であって該ネットワーク領域の外に存在するネットワークに接続するリンクが1つだけの局所的なネットワーク領域における出入口リンクまたは出入口ノードを設定する局所領域設定部と、
すべてのリンクおよびノードを含む最上位のレベルのネットワーク領域に含まれるネットワークを構成するリンクまたはノードのうちいずれかのリンクまたはノードを選択しネットワーク領域の包含関係を設定するための基準の根として設定する基準根設定部と、
各ネットワーク領域を構成するリンクまたはノードと出入口リンクまたは出入口ノードと前記基準の根との接続状態に基づいて各ネットワーク領域の包含関係を設定して木構造化されたネットワークデータを生成するレベル設定部と
を備えるネットワークデータ生成装置。
【請求項4】
前記レベル設定部は、前記基準の根との接続において、特定の出入口リンクまたは出入口ノードを介さなければ前記基準の根と接続しないリンクおよびノードが属するネットワーク領域のレベルを、前記特定の出入口リンクまたは出入口ノードよりも前記基準の根側のネットワーク領域に対して格下げすることによりネットワーク領域同士の包含関係を設定することを特徴とする請求項3に記載のネットワークデータ生成装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2010−256350(P2010−256350A)
【公開日】平成22年11月11日(2010.11.11)
【国際特許分類】
【出願番号】特願2010−81084(P2010−81084)
【出願日】平成22年3月31日(2010.3.31)
【出願人】(597151563)株式会社ゼンリン (155)
【Fターム(参考)】
【公開日】平成22年11月11日(2010.11.11)
【国際特許分類】
【出願日】平成22年3月31日(2010.3.31)
【出願人】(597151563)株式会社ゼンリン (155)
【Fターム(参考)】
[ Back to top ]