(57)【要約】【課題】各階層での通行に必要な交差点内リンクを設定する方法および装置を提供する。【解決手段】交差点抽出部は同一交差点を形成しているノードを抽出し、地点設定部は抽出されたノードにそれぞれ接続している道路リンク上に始点および退出リンクを終点と設定し、経路探索部は始点から終点までの全組み合わせの経路探索を行う。階層設定部は経路に含まれた各交差点内リンクに、経路に含む最上位の階層に属することを示す属性情報を付与する。【選択図】図６
2010217710.tif 000002
【特許請求の範囲】
【請求項１】
地図上の道路を表す道路リンクと、これら道路リンクに接続するノードと、ノード間を仮想リンクで結ぶことによって得られる交差点内リンクとを有するとともに、複数の階層構造で規定されている道路ネットワークデータにおける、交差点内リンクに階層情報を設定する階層設定方法であって、
異なる階層の道路リンクが接続されており、１つの交差点を形成する複数のノードを抽出する交差点抽出工程と、
抽出された交差点に対応する全てのノードにそれぞれ接続している道路リンクの進入および退出情報に基づき、前記ノードへの進入リンク上の点を始点および退出リンク上の点を終点として設定する地点設定工程と、
各階層において、始点から終点までの全組み合わせの経路探索を実行する経路探索工程と、
経路探索した結果、各交差点内リンクに、経路に含まれた最上位の階層情報を設定するリンク階層設定工程と、
をコンピュータが実行することを特徴とする階層設定方法。
【請求項２】
前記交差点抽出工程、地点設定工程、経路探索工程およびリンク階層設定工程を前記階層の最下層から順に行うことを特徴とする、請求項１に記載の階層設定方法。
【請求項３】
前記交差点抽出工程において、同一交差点を形成する複数のノードに接続する道路リンクが存在しなくなった階層で処理終了とすることを特徴とする、請求項２に記載の階層設定方法。
【請求項４】
前記交差点抽出工程、地点設定工程、経路探索工程およびリンク階層設定工程を前記階層の最上層から順に行うことを特徴とする、請求項１に記載の階層設定方法。
【請求項５】
前記リンク階層設定工程において階層が未設定である交差点内リンクを前記道路ネットワークデータから削除するリンク削除工程を含むことを特徴とする、請求項１〜４のいずれか１項に記載の階層設定方法。
【請求項６】
地図上の道路を表す道路リンクと、これら道路リンクに接続するノードと、ノード間を仮想リンクで結ぶことによって得られる交差点内リンクとを有するとともに、複数の階層構造で規定されている道路ネットワークデータにおける、交差点内リンクに階層情報を設定する階層設定装置であって、
異なる階層の道路リンクが接続されており、１つの交差点を形成する複数のノードを抽出する交差点抽出部と、
抽出された交差点に対応する全てのノードにそれぞれ接続している道路リンクの進入および退出情報に基づき、前記ノードへの進入リンク上の点を始点および退出リンク上の点を終点として設定する地点設定部と、
各階層において、始点から終点までの全組み合わせの経路探索を実行する経路探索部と、
経路探索した結果、各交差点内リンクに、経路に含まれた最上位の階層情報を設定するリンク階層設定部と、
を備えることを特徴とする階層設定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、交差点内リンクの属する階層を設定する階層設定装置および階層設定方法に関する。
【背景技術】
【０００２】
電子地図データは、例えば、ユーザーに指定された出発地から目的地までの経路を探索する経路探索や、経路を案内する経路案内に利用されている。この電子地図データには、経路探索用に道路をリンク、ノードで表現した道路ネットワークデータと、地図表示用のデータとが用意されている。リンクおよびノードには、それぞれ道路の通過点に対応する緯度、経度などの位置情報が付与されている。
【０００３】
このような経路探索に用いられる道路ネットワークデータは、経路探索対象リンクを網羅した比較的密な下層道路ネットワークデータから、主要道路のみを含む比較的粗い上層道路ネットワークデータまで、道路リンクの属性に応じて複数の階層に分けて記憶されている（特許文献１）。経路計算を行う場合は、出発地ノード付近と目的地ノード付近の経路を下層道路ネットワークデータで計算し、途中の経路は、出発地および目的地それぞれの近傍に存在する遷移ノードを通じて、下層道路ネットワークデータから上層道路ネットワークデータに移動して計算を行う。このように道路ネットワークデータを階層別に記憶することにより、計算速度の高速化が可能となるとともに、メモリの記憶領域を減少させることができる。
【０００４】
また、道路ネットワークデータは、より高精度・高精細に作られることが求められており、地図上の道路に対応する道路リンクも幅を表現する必要がある。そのため、地図上の道路の上下線に対応する道路リンクも上下線分離の形で記憶されている。これに従い、地図上の各交差点に対応するノードも、分離されたそれぞれの道路リンクと接続できるように分割して設定されている。また、この分割されたノードを用いて現実の交通規制情報を表現するために、同一交差点に対応するノード間に交差点内リンクと呼ばれる仮想リンクを設けている（特許文献２）。交差点内リンクには、実際の交通規制に応じた規制が付与されており、このような道路ネットワークデータを用いて経路探索を行うことによって、複雑な交通規制を有する交差点においても、実際の交通規制に則した案内が可能となっている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−２０５９９４号公報
【特許文献２】特開平１０−２７４５４５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記のように、道路リンクには対応する道路の属性に応じた階層が設定されている。階層ごとの道路ネットワークの完成のためには、交差点内リンクにも同一ノードに接続する道路リンクに準じた階層を付与する必要がある。しかし、対応する複数の道路リンクに異なる階層が設定されている場合は、交差点内リンクをどの階層とすべきか単純に決定できないという問題が生じる。さらに、右折やＵターン禁止、左折優先などの交差点に特有の走行規制がある場合、上記の問題はより複雑となる。そこで、交差点内リンクの階層設定は、同一ノードに接続している道路リンクの属性に準じて手動で行っていた。しかし、交差点内リンクの階層設定を手動で行うと、走行規制を加味しながらの対話作業は非常に工数がかかる上、オペレータの判断ミスにより、本来は上層にあるべき交差点内リンクを下層に設定してしまうことによる経路探索の失敗や、本来は上層に必要ない交差点内リンクを設定してしまうことによるデータ容量の増加および経路探索速度の低下などにつながるという問題が生じる。
【０００７】
そこで、本発明は、各階層での通行に必要な交差点内リンクを自動で設定する方法を提供する。
【課題を解決するための手段】
【０００８】
本発明は、地図上の道路を表す道路リンクと、これら道路リンクに接続するノードと、ノード間を仮想リンクで結ぶことによって得られる交差点内リンクとを有するとともに、複数の階層構造で規定されている道路ネットワークデータにおける、交差点内リンクの属する階層を設定する階層設定方法であって、異なる階層の道路リンクが接続されており、交差点を形成しているノードを抽出する交差点抽出工程と、抽出された交差点に対応する全てのノードにそれぞれ接続している道路リンクの進入および退出情報に基づき、前記ノードへの進入リンクを始点および退出リンクを終点と設定する地点設定工程と、各階層において、始点から終点までの全組み合わせの経路探索を実行する経路探索工程と、経路探索した結果、経路に含まれた各交差点内リンクを、経路に含む最上位の階層に定義するリンク階層設定工程と、をコンピュータが実行することを特徴とする。
【発明の効果】
【０００９】
本発明によると、上述のように、階層毎に同一交差点に対応するリンクの経路探索を行うことで、それぞれの階層で必要とされる交差点内リンクが抽出される。その結果、上位階層に設定されるべき交差点内リンクが下位階層に設定されることに伴って生じ得る最適経路が探索されないといった事態を防止することができる。さらに、各階層に不要な交差点内リンクを設定してしまうことによるデータ容量の増大および経路探索速度の低下などを防止することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の構成を示す概略図である。
【図２】道路ネットワークデータの構成の一例を示す図。
【図３】道路ネットワークデータ記憶部２に記憶されている交差点の一例を示す図。
【図４】交通規制を有する交差点の一例を示す図。
【図５】図４に示す道路ネットワークデータに２リンク規制を付した図。
【図６】階層設定装置の全体の動作を示すフローチャート。
【図７】図３に示す交差点における第１階層（最下層）ＮＬ１の道路ネットワークを示す図。
【図８】図３に示す交差点における第２階層ＮＬ２の道路ネットワークを示す図。
【図９】図３に示す交差点における第３階層（最上層）ＮＬ３の道路ネットワークを示す図。
【図１０】道路ネットワークデータ記憶部２に記憶されている交差点の一例を示す図。
【図１１】階層設定装置の全体の動作を示すフローチャート。
【図１２】図１０に示す交差点における第３階層（最上層）ＮＬ３の道路ネットワークを示す図。
【図１３】図１０に示す交差点における第２階層ＮＬ２の道路ネットワークを示す図。
【図１４】図１０に示す交差点における第１階層（最下層）ＮＬ１の道路ネットワークを示す図。
【発明を実施するための形態】
【００１１】
（実施例１）
図１に示すように、階層設定装置１は、道路ネットワークデータ記憶部２、処理階層設定部３、交差点抽出部４、地点設定部５、経路探索部６、リンク階層設定部７およびリンク削除部８を備えている。
【００１２】
道路ネットワークデータ記憶部２には、道路ネットワークデータが記憶されている。道路ネットワークデータにおいて、各道路は、その通過点の位置座標で定義される道路リンクで表される。また各道路リンクの交点は、その位置座標で定義されるノードで表される。位置座標は、緯度、経度を用いることも、地図の左下を原点Ｏとする直交座標Ｘ，Ｙを用いることも可能である。
【００１３】
道路ネットワークデータは種々の構造を採ることができる。道路ネットワークデータは例えば、表１および表２に示すようなテーブル形式を用いることができる。道路リンクデータは、地図上の各道路を、交差・分岐・合流する点など複数の地点で分割したときの地点間を結んだリンクに関するデータである。リンクデータは、リンクを特定する固有のＩＤ番号、リンクの長さを示すリンク長、リンクの始端及び終端に存在するノードの緯度・経度座標、リンクにおける複数地点の緯度・経度座標、道路名称、道路種別、道路幅員、車線数、右折・左折専用車線の有無とその専用車線の数、及び制限速度等の各種データを属性情報として有する。一方、ノードデータは、地図上の各道路が交差、合流、分岐する地点や、道路の属性が変更される地点等に付されるノードに関するデータである。ノードデータは、ノードを特定する固有のＩＤ番号、ノード座標、ノード名称、ノードに接続するリンクのリンクＩＤが記述される接続リンクＩＤ、交差点種類等の各種データを属性情報として有する。
【００１４】
【表１】
2010217710.tif 000003
【００１５】
【表２】
2010217710.tif 000004
【００１６】
道路ネットワークデータは、図２に示すように複数の階層で構成されている。階層は、各リンクに対応する道路の道路幅、道路種別、車線数、通行規制の有無、車両の重量・高さ・車幅等に対する規制情報、特殊車両に対する規制情報、有料・無料の区別・自動車専用道路、異常気象時の走行規制の有無、交通量・走行速度などの属性情報に基づいて決定される。例えば、図２における道路ネットワークデータは、最上層ＮＬ１には高速道路ＨＷのみが、第２階層ＮＬ２には高速道路ＨＷと国道ＲＤ１とが、第３階層ＮＬ３には高速道路ＨＷと国道ＲＤ１と市道ＲＤ２とを記憶している。
【００１７】
地図上の道路が上下線分離道路である場合、対応する道路リンクは、上下線をそれぞれ異なる独立した道路リンクで表現されている。図３において、例えば、道路リンクＬ１およびＬ２は、上下線分離道路における上り線および下り線にそれぞれ対応している。また、これら道路リンクＬ１およびＬ２それぞれの端部に接続されるノードＮ１およびＮ２と、道路リンクＬ５およびＬ６それぞれの端部に接続されるノードＮ３およびＮ４とは同一交差点内に存在している。
【００１８】
また、上述のように同一交差点内に複数のノードＮ１〜Ｎ４が存在する場合、道路リンクの他に、これらのノードＮ１〜Ｎ４をそれぞれ接続するための交差点内リンクＤＬ１〜ＤＬ６が設定されている。また、交差点内リンクＤＬ１〜ＤＬ６は、例えば、３リンク規制を２リンク規制で表現するために使用される。３リンク規制とは、一方通行等の道路交通規制を道路ネットワークデータに記憶させる際に、例えば、「リンクＡ→リンクＢ→リンクＣは通行不可能」等のように３つのリンクを用いて表現する方法である。また、２リンク規制とは、道路交通規制を「リンクＡ→リンクＢは通行不可能」等のように２つのリンクを用いて記憶する方法である。本発明の道路ネットワークデータは交通規制を２リンク規制で記憶している。３リンク規制及び２リンク規制についての詳細は、後述する。なお、本実施例では、交通規制を２リンク規制で表現した道路ネットワークデータを例に説明を行うが、本発明は、２リンク規制で表現された道路ネットワークデータへの適用に限定されない。例えば、３リンク規制や４リンク規制で表現した道路ネットワークデータに適用することもできる。
【００１９】
３リンク規制及び２リンク規制について、図４および図５を用いて説明する。図４において、矢印Ａで示すような通行禁止の３リンク規制を設ける。この場合、図５に示すように、交差点内リンクＤＬ１２およびＤＬ１３を設けた際の２リンク規制は、次の通りである。なお、下記規制において、「→」は左側リンクから右側リンクへの片側のみの通行を許可せず、「←→」は双方向の通行を許可していないことを表す；
道路リンクＬ１１→交差点内リンクＤＬ１１；
交差点内リンクＤＬ１３←→道路リンクＬ１４；
道路リンクＬ１２→交差点内リンクＤＬ１２；
道路リンクＬ１３→交差点内リンクＤＬ１３；
交差点内リンクＤＬ１１←→交差点内リンクＤＬ１２；
交差点内リンクＤＬ１１←→交差点内リンクＤＬ１３；
【００２０】
上記２リンク規制によれば、「リンクＬ１１→ＤＬ１１→Ｌ１４」の３リンク規制またはこれと同等の「リンクＬ１１→ＤＬ１２→ＤＬ１３→Ｌ１４」という経路を探索することは実現し得なくなる。また、それと同時に、交差点内リンクＤＬ１１、ＤＬ１２またはＤＬ１３を探索することにより、上記３リンク規制「リンクＬ１１→ＤＬ１１→Ｌ１４」で禁止された経路以外については、支障なく探索することが可能となる。
【００２１】
このように、３リンク規制が与えられた場合、３リンク規制の内容に応じて、交差点内リンクを追加し、２リンク規制を付すことによって、３リンク規制と同等の内容を２リンク規制のみで実現することが可能となる。
【００２２】
処理階層設定部３は、本発明における交差点抽出処理、地点設定処理、経路探索処理およびリンク階層設定処理を行う階層の設定または変更を行う。
【００２３】
交差点抽出部４は、道路ネットワークデータ記憶部２に記憶されている道路ネットワークデータから、異なる階層の道路リンクが接続されており、交差点を形成しているノードを抽出する。
【００２４】
地点設定部５は、抽出された交差点に対応する全てのノードにそれぞれ接続している道路リンクの進入および退出情報に基づき、前記抽出されたノードへの進入リンク上の所定の一点を始点として設定するとともに、退出リンク上の所定の一点を終点として設定する。
【００２５】
経路探索部６は、各階層において、地点設定部５によって設定された始点から終点までの全組み合わせについてそれぞれ経路探索を実行する。リンク階層設定部７は、経路探索部６にて探索された経路に含まれている交差点内リンクを抽出する。そして、リンク階層設定部７は、抽出された各交差点内リンクに、経路に含まれていた中で最も上位の階層であることを示す属性情報をそれぞれ付与する。
【００２６】
リンク削除部８は、経路探索部６にて経路探索を行った結果、いずれの階層の経路にも含まれなかった交差点内リンクを、道路ネットワークデータ記憶部２に記憶されている道路ネットワークデータから削除する。
【００２７】
次に、以上の構成を有する階層設定装置の動作を説明する。本実施例では、図３の交差点について、最下層ＮＬ１から最上層ＮＬ３へと順に処理を実行する手法を用いて、交差点内リンクの属する階層を設定する方法を説明する。
図６は、本実施例における図１に示す階層設定装置の全体の動作を示すフローチャートである。なお、図３において、各道路リンクの属する階層は、道路リンクＬ３およびＬ４が第１階層（最下層）ＮＬ１、道路リンクＬ１、Ｌ２、Ｌ５およびＬ６が第２階層ＮＬ２、道路リンクＬ７およびＬ８が第３階層（最上層）ＮＬ３である。また、図３における交差点ではＵターン禁止とし、道路リンクＬ１→Ｌ２、Ｌ３→Ｌ４、Ｌ５→Ｌ６、およびＬ７→Ｌ８は経路として選択されることがないように、規制されているものとする。
【００２８】
まず、処理階層設定部３は、処理階層を最下層ＮＬ１に設定する（ステップＳ２０）。次に、交差点抽出部４は図３の同一交差点に接続する道路リンクを抽出する（ステップＳ２１）。本実施例では、図７に示すように、第１階層（最下層）ＮＬ１の道路ネットワークデータに記憶されている全ての道路リンクＬ１〜Ｌ８が検出される（ステップＳ２２）。
【００２９】
次に、地点設定部５は、各道路リンクに付与されている規制情報に基づいて経路探索に使用する始点および終点を設定する（ステップＳ２３）。例えば、図７において、道路リンクＬ１、Ｌ３、Ｌ５およびＬ７は、交差点を形成するノードへの進入リンクなので、地点設定部５は、これら道路リンク上のそれぞれ任意の点に始点Ｓ１〜Ｓ４を設定する。また、道路リンクＬ２、Ｌ４、Ｌ６およびＬ８は、交差点を形成するノードからの脱出リンクなので、地点設定部５は、これら道路リンク上のそれぞれ任意の点に終点Ｇ１〜Ｇ４を設定する。
【００３０】
経路探索部６は、図７で示す始点および終点の全組み合わせの経路探索を実行する（ステップＳ２５）。例えば、始点Ｓ１、終点Ｇ４の経路探索を実行した場合、Ｌ１→ＤＬ６→Ｌ４の経路探索結果が得られる。ここで、経路探索結果に交差点内リンクＬＤ１４が含まれているため、リンク階層設定部７は、交差点内リンクＤＬ６に最下層ＮＬ１に属することを示す属性情報を付与する。（ステップＳ２６）。他の始点および終点の組み合わせについても、同様の処理を実行する。本実施例の場合、交差点内リンクＤＬ１〜ＤＬ６に最下層ＮＬ１に属することを示す属性情報を付与する。
【００３１】
第１階層（最下層）ＮＬ１における全始点と終点との組み合わせによる経路探索処理および階層の設定処理が終了した後、処理階層設定部３は、処理階層を最下層ＮＬ１から１つ上げて第２階層ＮＬ２とする（ステップＳ２８）。第２階層ＮＬ２において、交差点抽出部４は同一交差点に接続する道路リンクを抽出する。例えば、図３に示す交差点の例では、道路リンクＬ１〜Ｌ８のうち、第２階層ＮＬ２に記憶されている道路リンクは、道路リンクＬ１、Ｌ２、Ｌ５、Ｌ６、Ｌ７およびＬ８であり、図８に示すように、これらの道路リンクが抽出される。
【００３２】
続いて、地点設定部５は、経路探索に使用する始点および終点を設定する。地点設定部５は、道路リンクＬ１、Ｌ５およびＬ７上のそれぞれ任意の点に始点Ｓ１〜Ｓ３を設定し、道路リンクＬ２、Ｌ６およびＬ８上のそれぞれ任意の点に終点Ｇ１〜Ｇ３を設定する。
【００３３】
次に、経路探索部６は、図８で示す始点および終点の全組み合わせの経路探索を実行する。例えば、始点Ｓ３、終点Ｇ２の経路探索を実行した場合、Ｌ５→ＤＬ６→Ｌ８の経路探索結果が得られる。ここで、経路探索結果に交差点内リンクＤＬ６が含まれているため、リンク階層設定部７は、最下層ＮＬ１に属するとされていた交差点内リンクＤＬ６の属性情報を、第２階層ＮＬ２へと変更する。本実施例の場合、交差点内リンクＤＬ２、ＤＬ４、ＤＬ５およびＤＬ６が経路に含まれているため、最下層ＮＬ１に属するとされていたこれら交差点内リンクの属性情報を、第２階層ＮＬ２へと変更する。交差点内リンクＤＬ１およびＤＬ３は、第２階層ＮＬ２における経路に含まれなかったため、属性情報の上書きは行わず、第１階層（最下層）ＮＬ１に設定された状態を維持する。
【００３４】
続いて、処理階層設定部３は、処理階層を第２階層ＮＬ２からさらに一つ上げ、第３階層（最上層）ＮＬ３とする。交差点抽出部４は、図３の同一交差点に接続する道路リンクを抽出する。第３階層（最上層）ＮＬ３に記憶されている道路リンクは、Ｌ７およびＬ８であるため、これらの道路リンクが抽出される（図９）。次に、地点設定部５は、規制情報に基づいて、道路リンクＬ７を始点として設定するとともに、道路リンクＬ８を終点として設定する。経路探索部６は、図９で示す始点Ｌ７および終点Ｌ８の組み合わせで経路探索を行うが、Ｕターン規制により、Ｌ７→Ｌ８の経路は存在しない。このため、第３階層で経路に含まれた交差点内リンクは存在せず、交差点内リンクの階層の上書きも行われない。
【００３５】
このようにして、本実施例の方法を用いることで、交差点内リンクＤＬ２、ＤＬ４、ＤＬ５およびＤＬ６第２階層ＮＬ２、ならびに、交差点内リンクＤＬ１およびＤＬ３が第１階層（最下層）ＮＬ１というように、交差点内リンクの属する階層を設定することができる。
【００３６】
本実施例では行われなかったが、リンク削除部８は、最下層ＮＬ１で経路に含まれなかった交差点内リンクを、その交差点には不要な交差点内リンクとして削除することができる。このような工程を入れ、最下層ＮＬ１の検索の段階で不要な交差点内リンクを削除することによって、経路探索の処理数が減少され、その結果、上位階層における処理時間を短縮できる。
【００３７】
なお、本実施例では処理を最上層ＮＬ３まで行ったが、最上層ＮＬ３に到達する前に、同一交差点を形成する複数のノードに接続する道路リンクが存在しなくなった階層で処理を終了してよい。
【００３８】
実施例１によれば、最下層ＮＬ１から順に同一交差点に対応するリンクの経路探索を行うことで、それぞれの階層で必要とされる交差点内リンクが抽出される。その結果、上位階層に設定されるべき交差点内リンクが下位階層に設定されることに伴って生じ得る最適経路が探索されないといった事態や、各階層に不要な交差点内リンクを設定してしまうことによるデータ容量の増大および経路探索速度の低下などを防止することができる。また、実施例１によれば、最上層ＮＬ３に到達する前に、交差点抽出部４が道路リンクを抽出しない階層が存在する場合に処理を終了ようにしたため、階層設定処理の高速化が可能となる。
（実施例２）
【００３９】
本実施例では、図１０の交差点について、最上層ＮＬ３から順に処理を実行する手法を用いて、交差点内リンクの階層を設定する方法を説明する。なお、実施例２の基本的構成は実施例１と同じである。
図１１は、本実施例における図１に示す階層設定装置の全体の動作を示すフローチャートである。なお、図１０における各道路リンクの属する階層は、道路リンクＬ３３およびＬ３４が第１階層（最下層）ＮＬ１、道路リンクＬ３１およびＬ３２が第２階層ＮＬ２、道路リンクＬ３５およびＬ３６が第３階層（最上層）ＮＬ３である。また、図１０における交差点ではＵターン禁止とし、道路リンクＬ３１→Ｌ３２、Ｌ３３→Ｌ３４およびＬ３５→Ｌ３６のルートは規制されているものとする。
【００４０】
図１０の交差点を形成する道路ネットワークデータにおいて、処理階層設定部３は、処理階層を第３階層（最上層）ＮＬ３に設定する（ステップＳ３０）。交差点抽出部４は、第３階層（最上層）ＮＬ３において同一交差点に接続する道路リンクを抽出する（ステップＳ３１）。本実施例では、図１２に示すように、第３階層（最上層）ＮＬ３に属している道路リンクＬ３６およびＬ３７が抽出される。
【００４１】
次に、地点設定部５は、各道路リンクの規制情報から経路探索に使用する始点および終点を設定する（ステップＳ３３）。図１２において、道路リンクＬ３５は、交差点を形成するノードへの進入リンクなので、地点設定部５は、道路リンクＬ３７上の任意の点に始点を設定する。また、道路リンクＬ３６は、交差点を形成するノードからの脱出リンクなので、地点設定部５は、道路リンクＬ３６上の任意の点に終点を設定する。
【００４２】
次に、経路探索部６は、図１２で示す始点および終点の全組み合わせの経路探索を実行する（ステップＳ３５）。経路探索を行うと、Ｕターン規制により、Ｌ３５→Ｌ３６の経路は存在しない。このため、第３階層（最上層）ＮＬ３で経路に含まれる交差点内リンクは存在せず、第３階層においては、交差点内リンクの階層の設定は行われない。
【００４３】
第３階層（最上層）ＮＬ３における全始点と終点との組み合わせによる経路探索処理および階層の設定処理が終了した後、処理階層設定部３は、処理階層を１つ下げて第２階層ＮＬ２とする（ステップＳ３８）。次に、第２階層ＮＬ２において、交差点抽出部４は、図１３の同一交差点に接続する道路リンクを抽出する（ステップＳ３１）。第２階層ＮＬ２に記憶されている道路リンクは、Ｌ３１、Ｌ３２、Ｌ３５およびＬ３６であるため、これらの道路リンクが抽出される。
【００４４】
続いて、地点設定部５は、経路探索に使用する始点および終点を設定する（ステップＳ３３）。図１３において、地点設定部５は、Ｌ３１およびＬ３５上のそれぞれ任意の点に始点を設定し、また、Ｌ３２およびＬ３６上のそれぞれ任意の点に終点を設定する。
【００４５】
経路探索部６は、図１３で示す始点および終点の全組み合わせの経路探索を実行する（ステップＳ３５）。例えば、始点Ｓ３２、終点Ｇ３１の経路探索を実行した場合、Ｌ３５→ＤＬ３２→Ｌ３２の経路探索結果が得られる。ここで、経路探索結果に交差点内リンクＤＬ３２が含まれているため、リンク階層設定部７は、交差点内リンクＤＬ３２の階層を第２階層ＮＬ２に設定する（ステップＳ３６）。本実施例の場合、交差点内リンクＤＬ３２のみが第２階層ＮＬ２における経路に含まれているため、リンク階層設定部７は、交差点内リンクＤＬ３２の階層のみを第２階層ＮＬ２に設定する。
【００４６】
続いて、処理階層設定部３は、処理階層をさらに一つ下げ、第１階層（最下層）ＮＬ１とする（ステップＳ３８）。第１階層（最下層）ＮＬ１において、交差点抽出部４は、図１０の同一交差点に接続する道路リンクを抽出する（ステップＳ３１）。第１階層（最下層）ＮＬ１に記憶されている道路リンクは、Ｌ３１〜Ｌ３６であり、これらの道路リンクが抽出される（図１４）。次に、地点設定部５は、規制情報に基づいて、道路リンクＬ３１、Ｌ３３およびＬ３５上のそれぞれ任意の点に始点を、道路リンクおよびＬ３２、Ｌ３４およびＬ３６上のそれぞれ任意の点に終点を設定する（ステップＳ３３）。
【００４７】
経路探索部６は、図１４で示す始点および終点の全組み合わせの経路探索を実行する（ステップＳ３５）。例えば、始点Ｓ３３、終点Ｇ３２の経路探索を実行した場合、Ｌ３３→ＤＬ３１→Ｌ３６の経路探索結果が得られる。ここで、経路探索結果に交差点内リンクＤＬ３１が含まれているため、リンク階層設定部７は、交差点内リンクＤＬ３１の階層を第１階層（最下層）ＮＬ１に設定する（ステップＳ３６）。本実施例の場合、交差点内リンクＤＬ３１〜ＤＬ３３が第１階層（最下層）ＮＬ１における経路に含まれている。しかし、ＤＬ３２は上述の工程でリンク階層設定部７によって第２階層ＮＬ２に設定されたため、ここでは、ＤＬ３１およびＤＬ３３を第１階層（最下層）ＮＬ１の所属と設定する。ここで、処理階層が最下層ＮＬ１となったため、処理を終了する（ステップＳ３７）。
【００４８】
このように、実施例２では第３階層（最上層）ＮＬ３から第１階層（最下層）ＮＬ１まで順に処理を行うことで、交差点内リンクの属する階層を設定することができる。また、本実施例では行われなかったが、最下層ＮＬ１で経路に含まれなかった交差点内リンクを最終的に削除することで、道路ネットワークデータ量の低減を図ることができる。
【００４９】
実施例２によれば、最上層ＮＬ３から順に同一交差点に対応するリンクの経路探索を行うことで、それぞれの階層で必要とされる交差点内リンクが抽出される。その結果、上位階層に設定されるべき交差点内リンクが下位階層に設定されることに伴って生じ得る最適経路が探索されないといった事態や、各階層に不要な交差点内リンクを設定してしまうことによるデータ容量の増大および経路探索速度の低下などを防止することができる。
【００５０】
なお、本実施例では上下線分離道路からなる交差点に対応する道路ネットワークデータを例に説明を行ったが、本発明はこれに限定されることなく、例えば、上下線分離道路と上下線非分離道路とからなる交差点に対応する道路ネットワークデータにも適用できる。
【符号の説明】
【００５１】
１  階層設定装置、
２  道路ネットワークデータ記憶部、
３  処理階層設定部、
４  交差点抽出部、
５  地点設定部、
６  経路探索部、
７  リンク階層設定部、
８  リンク削除部。
【図１】
2010217710.tif 000005
【図２】
2010217710.tif 000006
【図３】
2010217710.tif 000007
【図４】
2010217710.tif 000008
【図５】
2010217710.tif 000009
【図６】
2010217710.tif 000010
【図７】
2010217710.tif 000011
【図８】
2010217710.tif 000012
【図９】
2010217710.tif 000013
【図１０】
2010217710.tif 000014
【図１１】
2010217710.tif 000015
【図１２】
2010217710.tif 000016
【図１３】
2010217710.tif 000017
【図１４】
2010217710.tif 000018