準車両道路リンク抽出装置および方法
【課題】実際の使用状況に適した細街路を抽出する方法を提供する。
【解決手段】 本発明の準車両道路リンク抽出装置は、中長距離の車両通行に適している車両道路リンクと短距離の車両通行に適している準車両道路リンクとを有する道路ネットワークデータにおいて、所定範囲内に始点と到達点とを設定し、前記車両道路リンクと前記準車両道路リンクとに付与された通行コストおよびその接続関係に応じた接続コストに基づき、前記始点から前記到達点までの車両通行に最も適していると判断された最適経路を選択し、経路に含まれた準車両道路リンクを抽出することを特徴とする。
【解決手段】 本発明の準車両道路リンク抽出装置は、中長距離の車両通行に適している車両道路リンクと短距離の車両通行に適している準車両道路リンクとを有する道路ネットワークデータにおいて、所定範囲内に始点と到達点とを設定し、前記車両道路リンクと前記準車両道路リンクとに付与された通行コストおよびその接続関係に応じた接続コストに基づき、前記始点から前記到達点までの車両通行に最も適していると判断された最適経路を選択し、経路に含まれた準車両道路リンクを抽出することを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、実際の使用状況に適した細街路を抽出する技術に関する。
【背景技術】
【０００２】
電子地図データは、例えば、ユーザに指定された出発地から目的地までの経路を探索する経路探索や、経路案内に利用されている。この電子地図データは、道路をリンク、ノードで表現した道路ネットワークデータと、地図表示用の描画データとを含んで構成されている。リンクおよびノードには、それぞれ道路の通過点に対応する緯度、経度などの位置情報が付与されている。
【０００３】
道路ネットワークデータには、交通規制情報（左折／右折禁止、進入禁止等）、距離や時間等の推奨経路探索用コストデータ等が属性情報として付加された状態でハードディスク等に格納されている。しかしながら、例えば、生活道路等をはじめとする幅員の狭い細街路のデータについては、交通規制情報が一部調査されていない箇所も存在するため、経路案内用の道路ネットワークデータには含められていなかった。
【０００４】
そのため、細街路については、描画データに基づいて地図表示はされるものの、実際の経路探索時には探索の対象とはされていないが、ユーザが経路から外れて案内の対象ではない細街路へ進入する場合もある。また、短距離の移動を行う場合は、整備されている道路よりも細街路を用いたショートカットが最短経路である場合も多く、細街路を用いた経路の案内が必要とされている。
【０００５】
そこで、細街路にユーザが進入した場合を考慮して、別画面で細街路を拡大表示する方法が提案されている（特許文献１）。この方法では、経路探索用の道路データに基づいてディスプレイ装置の画面上で目的地までの経路案内中に、地図データを参照して自車が細街路に進入したか否かを判定する。そして、細街路に進入したと判定した場合には、当該進入点を新たな出発地として前記目的地に至る経路の再探索を行う。さらに、ディスプレイ装置の画面を２つの画面に分割し、再探索の結果及び細街路に関する道路データに基づいて、一方の画面に案内経路を表示すると共に、他方の画面に一方の画面よりも拡大した表示態様で細街路を表示するという手法を用いている。
【０００６】
また、他の車両の位置情報を利用することによって、当該他の車両の通過が確認された細街路は、車両通過可能な道路であると判断し、この車両の通過が確認された細街路を迂回路の決定に利用する技術も提案されている（特許文献２）。この技術によれば、他の車両から送られてくる位置情報に基づいて、他の車両が細街路を通過したか否かが確認され、他の車両が通過した細街路については、車両の通過が可能な道路であると判断される。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−３３３３３６号公報
【特許文献２】特開２００４−５３４６１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述の従来技術はいずれも、整備が不十分な情報精度の低い道路ネットワークデータを用いているため、案内の信頼性が低いという問題は依然残されている。従って、細街路の道路ネットワークデータの整備が望まれているが、全ての細街路の道路ネットワークデータを整備するとなると、ほとんど利用されていない道路も整備の対象となってしまい、整備負荷やコストが増大するという問題が生じる。
【０００９】
そこで、本発明は、実際の使用状況に適した細街路を抽出することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の準車両道路リンク抽出装置は、車両走行の適合度に応じた通行コストを付与した道路リンクとノードとで表現された道路ネットワークを利用して、任意の始点から任意の到達点までに通行する前記道路リンクの総コストを算出することで、車両通行に適していると推測される道路リンクである準車両道路リンクを抽出する準車両道路リンク抽出装置において、前記道路ネットワークデータにおいて、車両通行に適している道路リンクである車両道路リンク３本以上に接続しているノードのうち所定の領域内の任意の２地点をそれぞれ始点および到達点として設定する地点設定部と、前記車両道路リンクと前記準車両道路リンクとに付与された通行コストおよびその接続関係に応じた接続コストに基づき、前記始点から前記到達点までの車両通行に最も適していると判断された最適経路を抽出する経路抽出部と、前記抽出された最適経路に含まれる前記準車両道路リンクを抽出するリンク抽出部とを備えることを特徴とする。
【発明の効果】
【００１１】
本発明の準車両道路リンク抽出装置によれば、始点から終点までの最適経路を選定し、準車両道路リンク（細街路）が最適経路に含まれた場合は当該準車両道路リンクを抽出する。そのため、実際の通行に必要な準車両道路リンクのみを抽出することができると共に、最適経路に用いられなかった準車両道路リンクを実際上使用頻度が低い道路リンクと判断することが可能となる。したがって、実際の使用状況に適した道路ネットワークデータを作成することが可能となる。
【図面の簡単な説明】
【００１２】
【図１】本発明の装置の構成を示す概要図。
【図２】道路ネットワークの一例を示す図。
【図３】本発明の全体処理のフローチャート。
【図４】対象リンク抽出処理の一例を示すフローチャート。
【図５】道路ネットワークの他の一例を示す図。
【図６】対象リンク抽出処理の他の一例を示すフローチャート。
【図７】実施例における処理の結果を示す図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施形態について、図面を参照しながら説明する。
（実施例１）
図１に示すように、準車両道路リンク抽出装置１は、道路ネットワークデータ記憶部２、地点設定部３、経路抽出部４およびリンク抽出部５を備えている。なお、地点設定部３、経路抽出部４およびリンク抽出部５については、ＣＰＵ６によって実現される。ＣＰＵ６は、所定のプログラムに応じて各種処理を実行する。
【００１４】
道路ネットワークデータ記憶部２には、道路ネットワークデータが記憶されている。道路ネットワークデータにおいて、各道路は、その通過点の位置座標で定義される道路リンクで表される。また各道路リンクの交点は、その位置座標で定義されるノードで表される。位置座標は、緯度、経度を用いることも、地図の左下を原点Ｏとする直交座標Ｘ，Ｙを用いることも可能である。
【００１５】
道路ネットワークデータは種々の構造を採ることができ、例えば、テーブル形式としてよい。道路リンクデータは、地図上の各道路を、交差・分岐・合流する点など複数の地点で分割したときの地点間を結んだリンクに関するデータである。リンクデータは、リンクを特定する固有のＩＤ番号、リンクの長さを示すリンク長、リンクの始端及び終端に存在するノードの緯度・経度座標、リンクにおける複数地点の緯度・経度座標、道路名称、道路種別、道路幅員、車線数、右折・左折専用車線の有無とその専用車線の数、車両走行の通行コスト、及び制限速度等の各種データを属性情報として有する。一方、ノードデータは、地図上の各道路が交差、合流、分岐する地点や、道路の属性が変更される地点等に付されるノードに関するデータである。ノードデータは、ノードを特定する固有のＩＤ番号、ノード座標、ノード名称、ノードに接続するリンクのリンクＩＤが記述される接続リンクＩＤ、交差点種類等の各種データを属性情報として有する。
【００１６】
本発明の道路ネットワークデータにおける道路リンクには、情報精度が高く車両走行に適している車両道路を表現する車両道路リンク、情報精度は低いが車両走行に適していると推測される準車両道路を表現する準車両道路リンク、または、車両走行には適さない非車両道路を表現する非車両道路リンクのいずれかのリンク種別が属性情報として付与されている。道路リンクにいずれのリンク種別を付与するかの基準は任意に設定できる。例えば、幅員を基準に設定する場合は、道路の幅員が一定範囲以上の道路リンクを車両道路リンク、一定範囲以下の道路リンクを非車両道路リンク、および、両者のいずれにも含まれない道路リンクを準車両道路リンクとしてリンク種別を付与できる。
【００１７】
地点設定部３は、道路ネットワークデータにおいて、車両道路リンク３本以上に接続しているノードのうち所定領域内の任意の２地点をそれぞれ始点および到達点として設定する。領域の設定は任意に行うことができ、例えば、処理対象がノード数の多い都市部の場合は比較的狭い範囲とし、ノード数の少ない山間部等であれば比較的広い範囲に設定することができる。このように領域を設定して経路を抽出することによって、必要な準車両道路リンクの抽出をより確実に行うことが可能となる。
【００１８】
また、地点設定部３は、到達点を設定する際に、任意の点を通る線分により分割されるそれぞれの領域から設定する領域分割手段を備えていてもよい。このように分割された複数の領域から到達点を複数設定することによって、後述の経路抽出部４は、経路抽出を一方向に偏ることなく満遍なく行うことができる。任意の点は、特に限定されず、例えば、始点であってもよいし、その他の地点であってもよい。また、分割される領域の数は特に限定されず、例えば、４分割または８分割等、任意の数に分割してよい。
【００１９】
経路抽出部４は、車両道路リンクと準車両道路リンクとに付与された通行コストおよび車両道路リンクと準車両道路リンクとの接続関係に応じた接続コストに基づき、始点から到達点までの車両通行に最も適していると判断された最適経路を抽出する。例えば、経路抽出部４は、始点から到達点までの各経路の総コストとして、上記の通行コストと接続コストとの総和を求め、総コストが最小値の経路を最適経路として抽出することができる。通行コストは、例えば、表１に示すように道路リンクのリンク長、幅員、情報精度等に応じて付与することができる。また、接続コストは、表２に示すように車両道路リンクと準車両道路リンクとの接続関係に応じて付与することができる。
【００２０】
【表１】
【００２１】
【表２】
【００２２】
リンク抽出部５は、経路抽出部４によって抽出された最適経路に含まれる準車両道路リンクを抽出する。
【００２３】
次に、以上の構成を有する準車両道路リンク抽出装置１の動作を説明する。実施例１では、図２に示す道路ネットワークならびに表１〜２に示す通行コストおよび接続コストを用いる。任意のノードを始点ＳＴ１とし、始点ＳＴ１を中心に通行可能な全経路へ探索の枝を広げ、たどり着いたノードを順次到達点に設定する手法によって通行リンクを決定する方法を説明する。図３は、本実施例における図１に示す準車両道路リンク抽出装置によって実現される準車両道路リンク抽出処理を示すフローチャートであり、図４は、図３中の対象リンク抽出処理（ステップＳ１２０）の詳細を示したフローチャートである。
【００２４】
まず、図３および図４に示す処理の概要を説明する。はじめに、地点設定部３は、車両道路リンク３本以上に接続しているノード（以下、「対象ノード」という。）から任意の点を始点に設定する（ステップＳ１１０）。始点の設定が完了したら、次に、後述する対象リンク抽出処理を実行する（ステップＳ１２０）。
【００２５】
次に、地点設定部３は、未処理の対象ノードが存在するかを確認する（ステップＳ１３０）。未処理の対象ノードが存在する場合、地点設定部３は当該対象ノードについて同様に始点設定処理（ステップＳ１１０）および対象リンク抽出処理（ステップＳ１２０）を行う。全ての対象ノードにおいて、始点設定処理（ステップＳ１１０）および対象リンク抽出処理（ステップＳ１２０）が終了したら、準車両道路リンク抽出処理を終了する。
【００２６】
さらに、対象リンク抽出処理（ステップＳ１２０）にて抽出された準車両道路リンクを一時的に車両道路リンクとみなし（ステップＳ１５０）、再度ステップＳ１１０〜ステップＳ１３０の処理を繰り返し行うこともできる。このように本実施例の処理を繰り返し行うことで、さらに精度よく準車両道路リンクから車両道路リンクへの変更を行うことができる。
【００２７】
次に、対象リンク抽出処理について説明する。まず、地点設定部３は、探索コストの上限値および記憶する到達点数の上限値を設定する（ステップＳ２２０）。経路抽出部４は、地点設定部３によって設定された始点を中心に通行可能な全経路へ探索の枝を広げる（ステップＳ２３０）。道路リンクに探索枝が到達したら、経路抽出部４は、その道路リンクのリンク種別を判断する（ステップＳ２３１）。対象道路リンクのリンク種別が非車両道路リンクの場合は、通行できない経路としてそれ以上枝を伸ばさない。対象道路リンクのリンク種別が車両道路リンクまたは準車両道路リンクの場合、経路抽出部４は、対象の道路リンクに付与された通行コストおよび接続コストを取得するとともに、始点からの総コストを算出する（ステップＳ２３２）。経路抽出部４は、算出した総コストが上限コスト未満であるか否かを判定し（ステップＳ２３３）、総コストが上限値に達していればこの枝の探索を終了してステップＳ２４０へと進む。
【００２８】
総コストがコスト上限値未満であれば、地点設定部３は、探索枝の先にあるノード（以下、到達ノードという。）が存在する領域を確認する（ステップＳ２３４）。地点設定部３は、確認した領域内にすでに設定された到達点の数および到達ノードに接続するリンクのリンク種別を確認する（ステップＳ２３５）。そして、地点設定部３は、設定した到達点数の上限値未満かつ到達ノードが対象ノードである場合、到達ノードを到達点として設定する（ステップＳ２３６）。その一方で、設定した到達点数の上限値未満または到達ノードが対象ノードであるかのいずれかの条件を満たさない場合は、地点設定部３は、到達ノードを到達点として設定せず、ステップＳ２３７へ進む。
【００２９】
経路抽出部４は、到達ノードへの他の経路の存在を確認する（ステップＳ２３７）。他の経路が存在しない場合、経路抽出部４は、始点から到達点までの経路として、今回のルートを設定する（ステップＳ２３８）。到達ノードへのルートが他に存在する場合、経路抽出部４は、それぞれのルートの始点からの総コストを比較し、最小コストであるルートを経路として設定する（ステップＳ２３９）。
【００３０】
ステップＳ２３８またはステップＳ２３９の後、到達点数が上限値に達していないことを確認すると（ステップＳ２４０）、ステップＳ２３０へ戻りさらに経路の抽出を行う。このように、経路抽出部４および地点設定部３は、総コスト値または到達点数が設定された上限値に達するまでステップＳ２３０〜ステップＳ２４０の処理を行う。総コストの値または全ての領域における到達点数が上限値に達すると、リンク抽出部５は、ステップＳ２３８およびＳ２３９にて設定された全経路に含まれる準車両道路リンクを抽出し、（ステップＳ２４１）、始点に対する対象リンク抽出処理（ステップＳ１２０）を終了する。
【００３１】
次に、図３および図４に示す本実施例の具体的な処理手順を、図２を用いて説明する。図２に示すように、地点設定部３は、対象ノードから任意の点Ｎ８を始点ＳＴ１に設定する（ステップＳ１１０）。次に、ＣＰＵ６は、互いに直交する直線Ｔ１および直線Ｔ２によって始点ＳＴ１を中心に領域を領域Ａ１〜Ａ４に４分割する。なお、領域Ａ１〜Ａ４それぞれに、探索コスト上限値は５０に設定されるとともに、到達点数上限値が４に設定される（ステップＳ２２０）。ＣＰＵ６は、全経路へ探索の枝を伸ばす。例えば、始点ＳＴ１から出発した探索枝は、図２に示すように道路リンクＬ１２へと伸びる。ＣＰＵ６は、始点ＳＴ１から道路リンクＬ１２までの総コストを算出する（ステップＳ２３２）。道路リンクＬ１２の通行コストは２２．５であり、接続コストはゼロなので、始点ＳＴ１から道路リンクＬ１２までの総コストは２２．５となる。
【００３２】
経路抽出部４は、算出した総コストが上限コスト以下であるか否かを判定する（ステップＳ２３３）。始点ＳＴ１から道路リンクＬ１２までの総コストは２２．５であり、上述で設定したコスト上限値の５０未満であるので、ＣＰＵ６は、道路リンクＬ１２の先にある到達ノードＮ７が存在する領域を確認する（ステップＳ２３４）。地点設定部３は、確認した領域２内にすでに設定された到達点の数および到達ノードに接続するリンクのリンク種別を確認する（ステップＳ２３５）。ここでは、ノードＮ７は対象ノードではないので、地点設定部３は、ノードＮ７を到着点として記憶せずにステップＳ２４０へ進む。
【００３３】
一方、始点ＳＴ１から出発した探索枝は、道路リンクＬ９へも伸びる。道路リンクＬ９の通行コストおよび接続コストはそれぞれ７およびゼロなので、道路リンクＬ９への総コストは７となる。ＣＰＵ６によって算出された総コストはコスト上限値が５０未満であるので、ＣＰＵ６は続くノードＮ４に着目する（ステップＳ２３３）。ノードＮ４が存在する領域２において設定された到達点数はゼロであり、ノードＮ４は対象ノードであるので、ＣＰＵ６は、ノードＮ４を到着点として記憶する（ステップＳ２３６）。そして、経路抽出部４はノードＮ４への他の経路の存在を確認する（ステップＳ２３７）。ノードＮ４に到達した他の経路は存在しないので、経路抽出部４は、始点ＳＴ１から到達点Ｎ４までの経路として、ＳＴ１→Ｌ９→Ｎ４（経路Ｒ２）を設定する（ステップＳ２３８）。
【００３４】
ステップＳ２３８の後、到達点数が上限値に達していないことを確認すると（ステップＳ２４０）、ステップＳ２３０へ戻り、ＣＰＵ６は、ノードＮ４およびＮ７からさらに探索枝を伸ばす。ノードＮ４から伸びる経路は道路リンクＬ１、Ｌ４およびＬ５が存在し、また、ノードＮ７から伸びる経路は道路リンクＬ８、Ｌ１１およびＬ１６が存在する。しかし、道路リンクＬ１およびＬ８は非車両道路リンクであるため、ＣＰＵ６はこれらのリンクに延びる経路の探索を行わない（ステップＳ２３１）。また、道路リンクＬ５およびＬ１６は車両道路リンクであるので、ステップＳ２３２以降の処理は行われるが、ここでは説明を割愛し、道路リンクＬ４およびＬ１１について説明を行う。
【００３５】
ＣＰＵ６は、始点ＳＴ１から道路リンクＬ４およびＬ１１それぞれへの総コストを算出する（ステップＳ２３２）。道路リンクＬ４の通行コストは１２、Ｌ９→Ｌ４への接続コストは２となり、道路リンクＬ１１の通行コストは９、Ｌ１２→Ｌ１１への接続コストは６となる。したがって、始点ＳＴ１から道路リンクＬ４までの総コストは７＋１２＋２＝２１となり、また、始点ＳＴ１から道路リンクＬ１１までの総コストは２２．５＋９＋６＝３７．５となる。始点ＳＴ１から道路リンクＬ４および道路リンクＬ１１までのそれぞれの総コストは上限値の５０未満であるので、ステップＳ２３４へと進む。
【００３６】
ＣＰＵ６は、道路リンクＬ４およびＬ１１がそれぞれ接続するノードＮ３およびＮ６の領域を判定し、該当領域の到達点数が上限値に達していないことを確認する（ステップＳ２３４）。また、ノードＮ３およびＮ６がそれぞれ対象ノードであるかを判定し、対象ノードであるので、地点設定部３は、それぞれ到着点として記憶する（ステップＳ２３６）。経路抽出部４は、ノードＮ３およびＮ６への他の経路を判定し（ステップＳ２３７）、他の経路が存在しないので、始点ＳＴ１からノードＮ３およびＮ６への経路として、ＳＴ１→Ｌ９→Ｎ４→Ｌ４→Ｎ３（経路Ｒ３）およびＳＴ１→Ｌ１２→Ｎ７→Ｌ１１→Ｎ６（経路Ｒ１）をそれぞれ設定する（ステップＳ２３８）。
【００３７】
続いて、ＣＰＵ６は、ノードＮ３およびＮ６からさらに探索枝を伸ばす（ステップＳ２３０）。ノードＮ３から伸びる経路は道路リンクＬ３およびＬ８が、また、ノードＮ６から伸びる経路は道路リンクＬ７およびＬ１５が存在するが、道路リンクＬ８は非車両道路リンクであるため探索は行わない（ステップＳ２３１）。また、Ｌ１５への探索および到達点の判定は行われるが、ここでは説明を割愛する。
【００３８】
ＣＰＵ６は、始点ＳＴ１から道路リンクＬ３およびＬ７それぞれへの総コストを算出する（ステップＳ２３２）。道路リンクＬ３の通行コストは１２、Ｌ４→Ｌ３の接続コストはゼロとなり、道路リンクＬ７の通行コストは７、Ｌ１１→Ｌ７の接続コストは４となる。したがって、始点ＳＴ１から道路リンクＬ３までの総コストは２１＋１２＋０＝３３となり、始点ＳＴ１からリンクＬ７までの総コストは３７．５＋７＋４＝４８．５となる。始点ＳＴ１から道路リンクＬ３およびＬ７までのそれぞれの総コストは上限値の５０未満であるので、ステップＳ２３４へと進む。
【００３９】
ＣＰＵ６は、道路リンクＬ３およびＬ７がそれぞれ接続するノードＮ２の存在する領域が領域２であることを確認する（ステップＳ２３４）。領域２の到達点数が上限値未満であり、ノードＮ２が対象ノードであるため、地点設定部３は、ノードＮ２を到着点として設定する（ステップＳ２３５〜Ｓ２３６）。
【００４０】
次に、経路抽出部４は、始点ＳＴ１からノードＮ２のへ最小コストの経路を抽出するが、ノードＮ２への経路は、道路リンクＬ３経由および道路リンクＬ７経由の２通りが存在する（ステップＳ２３７）。そこで、それぞれの経路の始点ＳＴ１からの総コストを比較すると、道路リンクＬ３を通過する経路の総コストは３３、道路リンクＬ７を通過する経路の総コストは４７．５となる。したがって、経路抽出部４は、最小コストであるＳＴ１→Ｌ９→Ｎ４→Ｌ４→Ｎ３→Ｌ３→Ｎ２（経路Ｒ４）を設定する（ステップＳ２３９）。
【００４１】
このように、ＣＰＵ６は、総コスト値または到達点数が設定された上限値に達するまでステップＳ２３０〜ステップＳ２４０の処理を行う。総コストの値または全ての領域における到達点数が上限値に達すると、リンク抽出部５は、ステップＳ２３８および２３９にて設定された全経路に含まれる準車両道路リンクを抽出し、（ステップＳ２４１）、始点ＳＴ１に対する対象リンク抽出処理（ステップＳ１２０）を終了する。
【００４２】
始点ＳＴ１に対する対象リンク抽出処理が終了すると、地点設定部３は、未処理の対象ノードを始点ＳＴ２として設定し、同様に地点設定工程および経路抽出工程を行う（ステップＳ１３０）。全ての対象ノードにおいて、ステップＳ１１０〜ステップＳ１２０の工程が終了したら、本実施例の抽出処理を終了する。
【００４３】
このように実施例１の処理を行い、始点から終点までの最適経路を選定し、最適経路に含まれる当該準車両道路リンクを抽出することによって、実際の通行に必要な準車両道路リンクのみを抽出することができると共に、最適経路に用いられなかった準車両道路リンクを実際上使用頻度が低い道路リンクと判断することが可能となる。したがって、実施例１によれば、実際の使用状況に適した道路ネットワークデータを作成することが可能となる。また、実施例１では、始点から全方向へ経路を延ばし、到達したノードを順次到達点と設定することによって、始点から到達点まで短距離の経路を抽出することができ、短距離の通行に必要な準車両道路リンクをより精度よく抽出可能となる。
【００４４】
（実施例２）
実施例２では、対象リンク抽出処理（ステップＳ１２０）の他の形態について説明する。本実施例における対象リンク抽出処理（ステップＳ１２０）は、図５に示す道路ネットワークと、表１〜２に示す通行コストおよび接続コストとを用い、始点から一定の範囲内に存在するノードから任意の数の到達点を選択して記憶した後に、始点からそれぞれの到達点への経路探索を行う手法を用いる。図６は、図３に示すフローチャート中の対象リンク抽出処理（ステップＳ１２０）の詳細を示したフローチャートである。
【００４５】
まず、図６に示す処理の概要を説明する。地点設定部３がステップＳ１１０にて始点を設定した後、ＣＰＵ６は、始点から所定の範囲内に存在する対象ノードのうち任意の複数点を到達点として設定し、上限コスト値を設定する（ステップＳ３２０）。本実施例では始点を通る直線Ｔ３によって領域Ａ２１〜Ａ２２に２分割し、領域Ａ２１およびＡ２２それぞれに、上限コスト値を５０、到達点数を４とした。またノードＮ９を始点ＳＴ２１とし、ノードＮ３、Ｎ６、Ｎ８およびＮ１２をそれぞれ到達点Ｇ２１〜Ｇ２４として設定した。ＣＰＵ６は、通行コストおよび接続コストに基づいて、設定された始点からそれぞれの到達点までの経路探索を行う（ステップＳ３３０）。ＣＰＵ６は、地点設定部３によって設定された始点を中心に通行可能な全経路へ探索の枝を広げる（ステップＳ３３１）。
【００４６】
道路リンクに探索枝が到達したら、ＣＰＵ６は、その道路リンクのリンク種別を判断する（ステップＳ３３２）。対象道路リンクのリンク種別が非車両道路リンクの場合は、通行できない経路としてそれ以上枝を伸ばさない。対象道路リンクのリンク種別が車両道路リンクまたは準車両道路リンクの場合、ＣＰＵ６は、対象の道路リンクに付与された通行コストおよび接続コストを取得し、始点からの総コストを算出する（ステップＳ３３３）。経路抽出部４は、算出した総コストが上限コスト未満であるか否かを判定し（ステップＳ３３４）、上限値に達していればこの枝の探索を終了してステップＳ３３７へと進む。
【００４７】
総コストがコスト上限値未満であれば、ＣＰＵ６は探索枝の先にある到達ノードが到達点であるかを確認する（ステップＳ３３５）。到達ノードが到達点であれば、リンク抽出部５は、始点から到達点までの経路に含まれる準車両道路リンクを抽出する（ステップＳ３３６）。経路抽出部４は、枝が到達していない到達点が存在するかを確認し（ステップＳ３３７）、存在する場合はステップＳ３３０に戻り経路探索を行う。未到達の到達点が存在しない場合は、対象リンク抽出処理（ステップＳ１２０）を終了し、ステップＳ１２０へと進む。
【００４８】
到達点Ｇ２１〜Ｇ２４について、ＣＰＵ６によってステップ３３１〜３３５の処理が行われた結果、ステップＳ３３６にて図７に示す経路Ｒ２１〜Ｒ２４が最小コストの経路として記憶さる。リンク抽出部５は、記憶された経路Ｒ２１〜Ｒ２４に含まれる準車両道路リンクＬ１２およびＬ１１を抽出する。
【００４９】
このように実施例２の処理を行い、始点から終点までの最適経路を選定し、最適経路に含まれる当該準車両道路リンクを抽出することによって、実際の通行に必要な準車両道路リンクのみを抽出することができると共に、最適経路に用いられなかった準車両道路リンクを実際上使用頻度が低い道路リンクと判断することが可能となる。したがって、実施例２によれば、実際の使用状況に適した道路ネットワークデータを作成することが可能となる。
【符号の説明】
【００５０】
１ 準車両道路リンク抽出装置
２ 道路ネットワーク記憶部
３ 地点設定部
４ 経路抽出部
５ リンク抽出部
６ ＣＰＵ
【技術分野】
【０００１】
本発明は、実際の使用状況に適した細街路を抽出する技術に関する。
【背景技術】
【０００２】
電子地図データは、例えば、ユーザに指定された出発地から目的地までの経路を探索する経路探索や、経路案内に利用されている。この電子地図データは、道路をリンク、ノードで表現した道路ネットワークデータと、地図表示用の描画データとを含んで構成されている。リンクおよびノードには、それぞれ道路の通過点に対応する緯度、経度などの位置情報が付与されている。
【０００３】
道路ネットワークデータには、交通規制情報（左折／右折禁止、進入禁止等）、距離や時間等の推奨経路探索用コストデータ等が属性情報として付加された状態でハードディスク等に格納されている。しかしながら、例えば、生活道路等をはじめとする幅員の狭い細街路のデータについては、交通規制情報が一部調査されていない箇所も存在するため、経路案内用の道路ネットワークデータには含められていなかった。
【０００４】
そのため、細街路については、描画データに基づいて地図表示はされるものの、実際の経路探索時には探索の対象とはされていないが、ユーザが経路から外れて案内の対象ではない細街路へ進入する場合もある。また、短距離の移動を行う場合は、整備されている道路よりも細街路を用いたショートカットが最短経路である場合も多く、細街路を用いた経路の案内が必要とされている。
【０００５】
そこで、細街路にユーザが進入した場合を考慮して、別画面で細街路を拡大表示する方法が提案されている（特許文献１）。この方法では、経路探索用の道路データに基づいてディスプレイ装置の画面上で目的地までの経路案内中に、地図データを参照して自車が細街路に進入したか否かを判定する。そして、細街路に進入したと判定した場合には、当該進入点を新たな出発地として前記目的地に至る経路の再探索を行う。さらに、ディスプレイ装置の画面を２つの画面に分割し、再探索の結果及び細街路に関する道路データに基づいて、一方の画面に案内経路を表示すると共に、他方の画面に一方の画面よりも拡大した表示態様で細街路を表示するという手法を用いている。
【０００６】
また、他の車両の位置情報を利用することによって、当該他の車両の通過が確認された細街路は、車両通過可能な道路であると判断し、この車両の通過が確認された細街路を迂回路の決定に利用する技術も提案されている（特許文献２）。この技術によれば、他の車両から送られてくる位置情報に基づいて、他の車両が細街路を通過したか否かが確認され、他の車両が通過した細街路については、車両の通過が可能な道路であると判断される。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−３３３３３６号公報
【特許文献２】特開２００４−５３４６１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述の従来技術はいずれも、整備が不十分な情報精度の低い道路ネットワークデータを用いているため、案内の信頼性が低いという問題は依然残されている。従って、細街路の道路ネットワークデータの整備が望まれているが、全ての細街路の道路ネットワークデータを整備するとなると、ほとんど利用されていない道路も整備の対象となってしまい、整備負荷やコストが増大するという問題が生じる。
【０００９】
そこで、本発明は、実際の使用状況に適した細街路を抽出することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の準車両道路リンク抽出装置は、車両走行の適合度に応じた通行コストを付与した道路リンクとノードとで表現された道路ネットワークを利用して、任意の始点から任意の到達点までに通行する前記道路リンクの総コストを算出することで、車両通行に適していると推測される道路リンクである準車両道路リンクを抽出する準車両道路リンク抽出装置において、前記道路ネットワークデータにおいて、車両通行に適している道路リンクである車両道路リンク３本以上に接続しているノードのうち所定の領域内の任意の２地点をそれぞれ始点および到達点として設定する地点設定部と、前記車両道路リンクと前記準車両道路リンクとに付与された通行コストおよびその接続関係に応じた接続コストに基づき、前記始点から前記到達点までの車両通行に最も適していると判断された最適経路を抽出する経路抽出部と、前記抽出された最適経路に含まれる前記準車両道路リンクを抽出するリンク抽出部とを備えることを特徴とする。
【発明の効果】
【００１１】
本発明の準車両道路リンク抽出装置によれば、始点から終点までの最適経路を選定し、準車両道路リンク（細街路）が最適経路に含まれた場合は当該準車両道路リンクを抽出する。そのため、実際の通行に必要な準車両道路リンクのみを抽出することができると共に、最適経路に用いられなかった準車両道路リンクを実際上使用頻度が低い道路リンクと判断することが可能となる。したがって、実際の使用状況に適した道路ネットワークデータを作成することが可能となる。
【図面の簡単な説明】
【００１２】
【図１】本発明の装置の構成を示す概要図。
【図２】道路ネットワークの一例を示す図。
【図３】本発明の全体処理のフローチャート。
【図４】対象リンク抽出処理の一例を示すフローチャート。
【図５】道路ネットワークの他の一例を示す図。
【図６】対象リンク抽出処理の他の一例を示すフローチャート。
【図７】実施例における処理の結果を示す図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施形態について、図面を参照しながら説明する。
（実施例１）
図１に示すように、準車両道路リンク抽出装置１は、道路ネットワークデータ記憶部２、地点設定部３、経路抽出部４およびリンク抽出部５を備えている。なお、地点設定部３、経路抽出部４およびリンク抽出部５については、ＣＰＵ６によって実現される。ＣＰＵ６は、所定のプログラムに応じて各種処理を実行する。
【００１４】
道路ネットワークデータ記憶部２には、道路ネットワークデータが記憶されている。道路ネットワークデータにおいて、各道路は、その通過点の位置座標で定義される道路リンクで表される。また各道路リンクの交点は、その位置座標で定義されるノードで表される。位置座標は、緯度、経度を用いることも、地図の左下を原点Ｏとする直交座標Ｘ，Ｙを用いることも可能である。
【００１５】
道路ネットワークデータは種々の構造を採ることができ、例えば、テーブル形式としてよい。道路リンクデータは、地図上の各道路を、交差・分岐・合流する点など複数の地点で分割したときの地点間を結んだリンクに関するデータである。リンクデータは、リンクを特定する固有のＩＤ番号、リンクの長さを示すリンク長、リンクの始端及び終端に存在するノードの緯度・経度座標、リンクにおける複数地点の緯度・経度座標、道路名称、道路種別、道路幅員、車線数、右折・左折専用車線の有無とその専用車線の数、車両走行の通行コスト、及び制限速度等の各種データを属性情報として有する。一方、ノードデータは、地図上の各道路が交差、合流、分岐する地点や、道路の属性が変更される地点等に付されるノードに関するデータである。ノードデータは、ノードを特定する固有のＩＤ番号、ノード座標、ノード名称、ノードに接続するリンクのリンクＩＤが記述される接続リンクＩＤ、交差点種類等の各種データを属性情報として有する。
【００１６】
本発明の道路ネットワークデータにおける道路リンクには、情報精度が高く車両走行に適している車両道路を表現する車両道路リンク、情報精度は低いが車両走行に適していると推測される準車両道路を表現する準車両道路リンク、または、車両走行には適さない非車両道路を表現する非車両道路リンクのいずれかのリンク種別が属性情報として付与されている。道路リンクにいずれのリンク種別を付与するかの基準は任意に設定できる。例えば、幅員を基準に設定する場合は、道路の幅員が一定範囲以上の道路リンクを車両道路リンク、一定範囲以下の道路リンクを非車両道路リンク、および、両者のいずれにも含まれない道路リンクを準車両道路リンクとしてリンク種別を付与できる。
【００１７】
地点設定部３は、道路ネットワークデータにおいて、車両道路リンク３本以上に接続しているノードのうち所定領域内の任意の２地点をそれぞれ始点および到達点として設定する。領域の設定は任意に行うことができ、例えば、処理対象がノード数の多い都市部の場合は比較的狭い範囲とし、ノード数の少ない山間部等であれば比較的広い範囲に設定することができる。このように領域を設定して経路を抽出することによって、必要な準車両道路リンクの抽出をより確実に行うことが可能となる。
【００１８】
また、地点設定部３は、到達点を設定する際に、任意の点を通る線分により分割されるそれぞれの領域から設定する領域分割手段を備えていてもよい。このように分割された複数の領域から到達点を複数設定することによって、後述の経路抽出部４は、経路抽出を一方向に偏ることなく満遍なく行うことができる。任意の点は、特に限定されず、例えば、始点であってもよいし、その他の地点であってもよい。また、分割される領域の数は特に限定されず、例えば、４分割または８分割等、任意の数に分割してよい。
【００１９】
経路抽出部４は、車両道路リンクと準車両道路リンクとに付与された通行コストおよび車両道路リンクと準車両道路リンクとの接続関係に応じた接続コストに基づき、始点から到達点までの車両通行に最も適していると判断された最適経路を抽出する。例えば、経路抽出部４は、始点から到達点までの各経路の総コストとして、上記の通行コストと接続コストとの総和を求め、総コストが最小値の経路を最適経路として抽出することができる。通行コストは、例えば、表１に示すように道路リンクのリンク長、幅員、情報精度等に応じて付与することができる。また、接続コストは、表２に示すように車両道路リンクと準車両道路リンクとの接続関係に応じて付与することができる。
【００２０】
【表１】
【００２１】
【表２】
【００２２】
リンク抽出部５は、経路抽出部４によって抽出された最適経路に含まれる準車両道路リンクを抽出する。
【００２３】
次に、以上の構成を有する準車両道路リンク抽出装置１の動作を説明する。実施例１では、図２に示す道路ネットワークならびに表１〜２に示す通行コストおよび接続コストを用いる。任意のノードを始点ＳＴ１とし、始点ＳＴ１を中心に通行可能な全経路へ探索の枝を広げ、たどり着いたノードを順次到達点に設定する手法によって通行リンクを決定する方法を説明する。図３は、本実施例における図１に示す準車両道路リンク抽出装置によって実現される準車両道路リンク抽出処理を示すフローチャートであり、図４は、図３中の対象リンク抽出処理（ステップＳ１２０）の詳細を示したフローチャートである。
【００２４】
まず、図３および図４に示す処理の概要を説明する。はじめに、地点設定部３は、車両道路リンク３本以上に接続しているノード（以下、「対象ノード」という。）から任意の点を始点に設定する（ステップＳ１１０）。始点の設定が完了したら、次に、後述する対象リンク抽出処理を実行する（ステップＳ１２０）。
【００２５】
次に、地点設定部３は、未処理の対象ノードが存在するかを確認する（ステップＳ１３０）。未処理の対象ノードが存在する場合、地点設定部３は当該対象ノードについて同様に始点設定処理（ステップＳ１１０）および対象リンク抽出処理（ステップＳ１２０）を行う。全ての対象ノードにおいて、始点設定処理（ステップＳ１１０）および対象リンク抽出処理（ステップＳ１２０）が終了したら、準車両道路リンク抽出処理を終了する。
【００２６】
さらに、対象リンク抽出処理（ステップＳ１２０）にて抽出された準車両道路リンクを一時的に車両道路リンクとみなし（ステップＳ１５０）、再度ステップＳ１１０〜ステップＳ１３０の処理を繰り返し行うこともできる。このように本実施例の処理を繰り返し行うことで、さらに精度よく準車両道路リンクから車両道路リンクへの変更を行うことができる。
【００２７】
次に、対象リンク抽出処理について説明する。まず、地点設定部３は、探索コストの上限値および記憶する到達点数の上限値を設定する（ステップＳ２２０）。経路抽出部４は、地点設定部３によって設定された始点を中心に通行可能な全経路へ探索の枝を広げる（ステップＳ２３０）。道路リンクに探索枝が到達したら、経路抽出部４は、その道路リンクのリンク種別を判断する（ステップＳ２３１）。対象道路リンクのリンク種別が非車両道路リンクの場合は、通行できない経路としてそれ以上枝を伸ばさない。対象道路リンクのリンク種別が車両道路リンクまたは準車両道路リンクの場合、経路抽出部４は、対象の道路リンクに付与された通行コストおよび接続コストを取得するとともに、始点からの総コストを算出する（ステップＳ２３２）。経路抽出部４は、算出した総コストが上限コスト未満であるか否かを判定し（ステップＳ２３３）、総コストが上限値に達していればこの枝の探索を終了してステップＳ２４０へと進む。
【００２８】
総コストがコスト上限値未満であれば、地点設定部３は、探索枝の先にあるノード（以下、到達ノードという。）が存在する領域を確認する（ステップＳ２３４）。地点設定部３は、確認した領域内にすでに設定された到達点の数および到達ノードに接続するリンクのリンク種別を確認する（ステップＳ２３５）。そして、地点設定部３は、設定した到達点数の上限値未満かつ到達ノードが対象ノードである場合、到達ノードを到達点として設定する（ステップＳ２３６）。その一方で、設定した到達点数の上限値未満または到達ノードが対象ノードであるかのいずれかの条件を満たさない場合は、地点設定部３は、到達ノードを到達点として設定せず、ステップＳ２３７へ進む。
【００２９】
経路抽出部４は、到達ノードへの他の経路の存在を確認する（ステップＳ２３７）。他の経路が存在しない場合、経路抽出部４は、始点から到達点までの経路として、今回のルートを設定する（ステップＳ２３８）。到達ノードへのルートが他に存在する場合、経路抽出部４は、それぞれのルートの始点からの総コストを比較し、最小コストであるルートを経路として設定する（ステップＳ２３９）。
【００３０】
ステップＳ２３８またはステップＳ２３９の後、到達点数が上限値に達していないことを確認すると（ステップＳ２４０）、ステップＳ２３０へ戻りさらに経路の抽出を行う。このように、経路抽出部４および地点設定部３は、総コスト値または到達点数が設定された上限値に達するまでステップＳ２３０〜ステップＳ２４０の処理を行う。総コストの値または全ての領域における到達点数が上限値に達すると、リンク抽出部５は、ステップＳ２３８およびＳ２３９にて設定された全経路に含まれる準車両道路リンクを抽出し、（ステップＳ２４１）、始点に対する対象リンク抽出処理（ステップＳ１２０）を終了する。
【００３１】
次に、図３および図４に示す本実施例の具体的な処理手順を、図２を用いて説明する。図２に示すように、地点設定部３は、対象ノードから任意の点Ｎ８を始点ＳＴ１に設定する（ステップＳ１１０）。次に、ＣＰＵ６は、互いに直交する直線Ｔ１および直線Ｔ２によって始点ＳＴ１を中心に領域を領域Ａ１〜Ａ４に４分割する。なお、領域Ａ１〜Ａ４それぞれに、探索コスト上限値は５０に設定されるとともに、到達点数上限値が４に設定される（ステップＳ２２０）。ＣＰＵ６は、全経路へ探索の枝を伸ばす。例えば、始点ＳＴ１から出発した探索枝は、図２に示すように道路リンクＬ１２へと伸びる。ＣＰＵ６は、始点ＳＴ１から道路リンクＬ１２までの総コストを算出する（ステップＳ２３２）。道路リンクＬ１２の通行コストは２２．５であり、接続コストはゼロなので、始点ＳＴ１から道路リンクＬ１２までの総コストは２２．５となる。
【００３２】
経路抽出部４は、算出した総コストが上限コスト以下であるか否かを判定する（ステップＳ２３３）。始点ＳＴ１から道路リンクＬ１２までの総コストは２２．５であり、上述で設定したコスト上限値の５０未満であるので、ＣＰＵ６は、道路リンクＬ１２の先にある到達ノードＮ７が存在する領域を確認する（ステップＳ２３４）。地点設定部３は、確認した領域２内にすでに設定された到達点の数および到達ノードに接続するリンクのリンク種別を確認する（ステップＳ２３５）。ここでは、ノードＮ７は対象ノードではないので、地点設定部３は、ノードＮ７を到着点として記憶せずにステップＳ２４０へ進む。
【００３３】
一方、始点ＳＴ１から出発した探索枝は、道路リンクＬ９へも伸びる。道路リンクＬ９の通行コストおよび接続コストはそれぞれ７およびゼロなので、道路リンクＬ９への総コストは７となる。ＣＰＵ６によって算出された総コストはコスト上限値が５０未満であるので、ＣＰＵ６は続くノードＮ４に着目する（ステップＳ２３３）。ノードＮ４が存在する領域２において設定された到達点数はゼロであり、ノードＮ４は対象ノードであるので、ＣＰＵ６は、ノードＮ４を到着点として記憶する（ステップＳ２３６）。そして、経路抽出部４はノードＮ４への他の経路の存在を確認する（ステップＳ２３７）。ノードＮ４に到達した他の経路は存在しないので、経路抽出部４は、始点ＳＴ１から到達点Ｎ４までの経路として、ＳＴ１→Ｌ９→Ｎ４（経路Ｒ２）を設定する（ステップＳ２３８）。
【００３４】
ステップＳ２３８の後、到達点数が上限値に達していないことを確認すると（ステップＳ２４０）、ステップＳ２３０へ戻り、ＣＰＵ６は、ノードＮ４およびＮ７からさらに探索枝を伸ばす。ノードＮ４から伸びる経路は道路リンクＬ１、Ｌ４およびＬ５が存在し、また、ノードＮ７から伸びる経路は道路リンクＬ８、Ｌ１１およびＬ１６が存在する。しかし、道路リンクＬ１およびＬ８は非車両道路リンクであるため、ＣＰＵ６はこれらのリンクに延びる経路の探索を行わない（ステップＳ２３１）。また、道路リンクＬ５およびＬ１６は車両道路リンクであるので、ステップＳ２３２以降の処理は行われるが、ここでは説明を割愛し、道路リンクＬ４およびＬ１１について説明を行う。
【００３５】
ＣＰＵ６は、始点ＳＴ１から道路リンクＬ４およびＬ１１それぞれへの総コストを算出する（ステップＳ２３２）。道路リンクＬ４の通行コストは１２、Ｌ９→Ｌ４への接続コストは２となり、道路リンクＬ１１の通行コストは９、Ｌ１２→Ｌ１１への接続コストは６となる。したがって、始点ＳＴ１から道路リンクＬ４までの総コストは７＋１２＋２＝２１となり、また、始点ＳＴ１から道路リンクＬ１１までの総コストは２２．５＋９＋６＝３７．５となる。始点ＳＴ１から道路リンクＬ４および道路リンクＬ１１までのそれぞれの総コストは上限値の５０未満であるので、ステップＳ２３４へと進む。
【００３６】
ＣＰＵ６は、道路リンクＬ４およびＬ１１がそれぞれ接続するノードＮ３およびＮ６の領域を判定し、該当領域の到達点数が上限値に達していないことを確認する（ステップＳ２３４）。また、ノードＮ３およびＮ６がそれぞれ対象ノードであるかを判定し、対象ノードであるので、地点設定部３は、それぞれ到着点として記憶する（ステップＳ２３６）。経路抽出部４は、ノードＮ３およびＮ６への他の経路を判定し（ステップＳ２３７）、他の経路が存在しないので、始点ＳＴ１からノードＮ３およびＮ６への経路として、ＳＴ１→Ｌ９→Ｎ４→Ｌ４→Ｎ３（経路Ｒ３）およびＳＴ１→Ｌ１２→Ｎ７→Ｌ１１→Ｎ６（経路Ｒ１）をそれぞれ設定する（ステップＳ２３８）。
【００３７】
続いて、ＣＰＵ６は、ノードＮ３およびＮ６からさらに探索枝を伸ばす（ステップＳ２３０）。ノードＮ３から伸びる経路は道路リンクＬ３およびＬ８が、また、ノードＮ６から伸びる経路は道路リンクＬ７およびＬ１５が存在するが、道路リンクＬ８は非車両道路リンクであるため探索は行わない（ステップＳ２３１）。また、Ｌ１５への探索および到達点の判定は行われるが、ここでは説明を割愛する。
【００３８】
ＣＰＵ６は、始点ＳＴ１から道路リンクＬ３およびＬ７それぞれへの総コストを算出する（ステップＳ２３２）。道路リンクＬ３の通行コストは１２、Ｌ４→Ｌ３の接続コストはゼロとなり、道路リンクＬ７の通行コストは７、Ｌ１１→Ｌ７の接続コストは４となる。したがって、始点ＳＴ１から道路リンクＬ３までの総コストは２１＋１２＋０＝３３となり、始点ＳＴ１からリンクＬ７までの総コストは３７．５＋７＋４＝４８．５となる。始点ＳＴ１から道路リンクＬ３およびＬ７までのそれぞれの総コストは上限値の５０未満であるので、ステップＳ２３４へと進む。
【００３９】
ＣＰＵ６は、道路リンクＬ３およびＬ７がそれぞれ接続するノードＮ２の存在する領域が領域２であることを確認する（ステップＳ２３４）。領域２の到達点数が上限値未満であり、ノードＮ２が対象ノードであるため、地点設定部３は、ノードＮ２を到着点として設定する（ステップＳ２３５〜Ｓ２３６）。
【００４０】
次に、経路抽出部４は、始点ＳＴ１からノードＮ２のへ最小コストの経路を抽出するが、ノードＮ２への経路は、道路リンクＬ３経由および道路リンクＬ７経由の２通りが存在する（ステップＳ２３７）。そこで、それぞれの経路の始点ＳＴ１からの総コストを比較すると、道路リンクＬ３を通過する経路の総コストは３３、道路リンクＬ７を通過する経路の総コストは４７．５となる。したがって、経路抽出部４は、最小コストであるＳＴ１→Ｌ９→Ｎ４→Ｌ４→Ｎ３→Ｌ３→Ｎ２（経路Ｒ４）を設定する（ステップＳ２３９）。
【００４１】
このように、ＣＰＵ６は、総コスト値または到達点数が設定された上限値に達するまでステップＳ２３０〜ステップＳ２４０の処理を行う。総コストの値または全ての領域における到達点数が上限値に達すると、リンク抽出部５は、ステップＳ２３８および２３９にて設定された全経路に含まれる準車両道路リンクを抽出し、（ステップＳ２４１）、始点ＳＴ１に対する対象リンク抽出処理（ステップＳ１２０）を終了する。
【００４２】
始点ＳＴ１に対する対象リンク抽出処理が終了すると、地点設定部３は、未処理の対象ノードを始点ＳＴ２として設定し、同様に地点設定工程および経路抽出工程を行う（ステップＳ１３０）。全ての対象ノードにおいて、ステップＳ１１０〜ステップＳ１２０の工程が終了したら、本実施例の抽出処理を終了する。
【００４３】
このように実施例１の処理を行い、始点から終点までの最適経路を選定し、最適経路に含まれる当該準車両道路リンクを抽出することによって、実際の通行に必要な準車両道路リンクのみを抽出することができると共に、最適経路に用いられなかった準車両道路リンクを実際上使用頻度が低い道路リンクと判断することが可能となる。したがって、実施例１によれば、実際の使用状況に適した道路ネットワークデータを作成することが可能となる。また、実施例１では、始点から全方向へ経路を延ばし、到達したノードを順次到達点と設定することによって、始点から到達点まで短距離の経路を抽出することができ、短距離の通行に必要な準車両道路リンクをより精度よく抽出可能となる。
【００４４】
（実施例２）
実施例２では、対象リンク抽出処理（ステップＳ１２０）の他の形態について説明する。本実施例における対象リンク抽出処理（ステップＳ１２０）は、図５に示す道路ネットワークと、表１〜２に示す通行コストおよび接続コストとを用い、始点から一定の範囲内に存在するノードから任意の数の到達点を選択して記憶した後に、始点からそれぞれの到達点への経路探索を行う手法を用いる。図６は、図３に示すフローチャート中の対象リンク抽出処理（ステップＳ１２０）の詳細を示したフローチャートである。
【００４５】
まず、図６に示す処理の概要を説明する。地点設定部３がステップＳ１１０にて始点を設定した後、ＣＰＵ６は、始点から所定の範囲内に存在する対象ノードのうち任意の複数点を到達点として設定し、上限コスト値を設定する（ステップＳ３２０）。本実施例では始点を通る直線Ｔ３によって領域Ａ２１〜Ａ２２に２分割し、領域Ａ２１およびＡ２２それぞれに、上限コスト値を５０、到達点数を４とした。またノードＮ９を始点ＳＴ２１とし、ノードＮ３、Ｎ６、Ｎ８およびＮ１２をそれぞれ到達点Ｇ２１〜Ｇ２４として設定した。ＣＰＵ６は、通行コストおよび接続コストに基づいて、設定された始点からそれぞれの到達点までの経路探索を行う（ステップＳ３３０）。ＣＰＵ６は、地点設定部３によって設定された始点を中心に通行可能な全経路へ探索の枝を広げる（ステップＳ３３１）。
【００４６】
道路リンクに探索枝が到達したら、ＣＰＵ６は、その道路リンクのリンク種別を判断する（ステップＳ３３２）。対象道路リンクのリンク種別が非車両道路リンクの場合は、通行できない経路としてそれ以上枝を伸ばさない。対象道路リンクのリンク種別が車両道路リンクまたは準車両道路リンクの場合、ＣＰＵ６は、対象の道路リンクに付与された通行コストおよび接続コストを取得し、始点からの総コストを算出する（ステップＳ３３３）。経路抽出部４は、算出した総コストが上限コスト未満であるか否かを判定し（ステップＳ３３４）、上限値に達していればこの枝の探索を終了してステップＳ３３７へと進む。
【００４７】
総コストがコスト上限値未満であれば、ＣＰＵ６は探索枝の先にある到達ノードが到達点であるかを確認する（ステップＳ３３５）。到達ノードが到達点であれば、リンク抽出部５は、始点から到達点までの経路に含まれる準車両道路リンクを抽出する（ステップＳ３３６）。経路抽出部４は、枝が到達していない到達点が存在するかを確認し（ステップＳ３３７）、存在する場合はステップＳ３３０に戻り経路探索を行う。未到達の到達点が存在しない場合は、対象リンク抽出処理（ステップＳ１２０）を終了し、ステップＳ１２０へと進む。
【００４８】
到達点Ｇ２１〜Ｇ２４について、ＣＰＵ６によってステップ３３１〜３３５の処理が行われた結果、ステップＳ３３６にて図７に示す経路Ｒ２１〜Ｒ２４が最小コストの経路として記憶さる。リンク抽出部５は、記憶された経路Ｒ２１〜Ｒ２４に含まれる準車両道路リンクＬ１２およびＬ１１を抽出する。
【００４９】
このように実施例２の処理を行い、始点から終点までの最適経路を選定し、最適経路に含まれる当該準車両道路リンクを抽出することによって、実際の通行に必要な準車両道路リンクのみを抽出することができると共に、最適経路に用いられなかった準車両道路リンクを実際上使用頻度が低い道路リンクと判断することが可能となる。したがって、実施例２によれば、実際の使用状況に適した道路ネットワークデータを作成することが可能となる。
【符号の説明】
【００５０】
１ 準車両道路リンク抽出装置
２ 道路ネットワーク記憶部
３ 地点設定部
４ 経路抽出部
５ リンク抽出部
６ ＣＰＵ
【特許請求の範囲】
【請求項１】
車両走行の適合度に応じた通行コストを付与した道路リンクとノードとで表現された道路ネットワークを利用して、任意の始点から任意の到達点までに通行する前記道路リンクの総コストを算出することで、車両通行に適していると推測される道路リンクである準車両道路リンクを抽出する準車両道路リンク抽出装置において、
前記道路ネットワークデータにおいて、車両通行に適している道路リンクである車両道路リンク３本以上に接続しているノードのうち所定の領域内の任意の２地点をそれぞれ始点および到達点として設定する地点設定部と、
前記車両道路リンクと前記準車両道路リンクとに付与された通行コストおよびその接続関係に応じた接続コストに基づき、前記始点から前記到達点までの車両通行に最も適していると判断された最適経路を抽出する経路抽出部と、
前記抽出された最適経路に含まれる前記準車両道路リンクを抽出するリンク抽出部と、
を備えることを特徴とする準車両道路リンク抽出装置。
【請求項２】
前記地点設定部において、任意の点を通る線分により分割されるそれぞれの領域から到達点を複数設定することを特徴とする請求項１に記載の準車両道路リンク抽出装置。
【請求項３】
車両走行の適合度に応じた通行コストを付与した道路リンクとノードとで表現された道路ネットワークを利用して、任意の始点から任意の到達点までに通行する前記道路リンクの総コストを算出することで、車両通行に適していると推測される道路リンクである準車両道路リンクを抽出する準車両道路リンク抽出方法において、
前記道路ネットワークデータにおいて、車両通行に適している道路リンクである車両道路リンク３本以上に接続しているノードのうち所定の領域内の任意の２地点をそれぞれ始点および到達点として設定する地点設定工程と、
前記車両道路リンクと前記準車両道路リンクとに付与された通行コストおよびその接続関係に応じた接続コストに基づき、前記始点から前記到達点までの車両通行に最も適していると判断された最適経路を抽出する経路抽出工程と、
前記抽出された最適経路に含まれる前記準車両道路リンクを抽出する準車両道路リンク抽出工程と、
をコンピュータが実行することを特徴とする準車両道路リンク抽出方法。
【請求項４】
前記準車両道路リンク抽出工程が終了した後、他の始点を設定して前記処理を繰り返し行うことを特徴とする請求項３に記載の準車両道路リンク抽出方法。
【請求項５】
前記準車両道路リンク抽出工程が終了した後、準車両道路リンクを車両道路リンクとみなして前記処理を繰り返し行うことを特徴とする請求項３または４に記載の準車両道路リンク抽出装置。
【請求項１】
車両走行の適合度に応じた通行コストを付与した道路リンクとノードとで表現された道路ネットワークを利用して、任意の始点から任意の到達点までに通行する前記道路リンクの総コストを算出することで、車両通行に適していると推測される道路リンクである準車両道路リンクを抽出する準車両道路リンク抽出装置において、
前記道路ネットワークデータにおいて、車両通行に適している道路リンクである車両道路リンク３本以上に接続しているノードのうち所定の領域内の任意の２地点をそれぞれ始点および到達点として設定する地点設定部と、
前記車両道路リンクと前記準車両道路リンクとに付与された通行コストおよびその接続関係に応じた接続コストに基づき、前記始点から前記到達点までの車両通行に最も適していると判断された最適経路を抽出する経路抽出部と、
前記抽出された最適経路に含まれる前記準車両道路リンクを抽出するリンク抽出部と、
を備えることを特徴とする準車両道路リンク抽出装置。
【請求項２】
前記地点設定部において、任意の点を通る線分により分割されるそれぞれの領域から到達点を複数設定することを特徴とする請求項１に記載の準車両道路リンク抽出装置。
【請求項３】
車両走行の適合度に応じた通行コストを付与した道路リンクとノードとで表現された道路ネットワークを利用して、任意の始点から任意の到達点までに通行する前記道路リンクの総コストを算出することで、車両通行に適していると推測される道路リンクである準車両道路リンクを抽出する準車両道路リンク抽出方法において、
前記道路ネットワークデータにおいて、車両通行に適している道路リンクである車両道路リンク３本以上に接続しているノードのうち所定の領域内の任意の２地点をそれぞれ始点および到達点として設定する地点設定工程と、
前記車両道路リンクと前記準車両道路リンクとに付与された通行コストおよびその接続関係に応じた接続コストに基づき、前記始点から前記到達点までの車両通行に最も適していると判断された最適経路を抽出する経路抽出工程と、
前記抽出された最適経路に含まれる前記準車両道路リンクを抽出する準車両道路リンク抽出工程と、
をコンピュータが実行することを特徴とする準車両道路リンク抽出方法。
【請求項４】
前記準車両道路リンク抽出工程が終了した後、他の始点を設定して前記処理を繰り返し行うことを特徴とする請求項３に記載の準車両道路リンク抽出方法。
【請求項５】
前記準車両道路リンク抽出工程が終了した後、準車両道路リンクを車両道路リンクとみなして前記処理を繰り返し行うことを特徴とする請求項３または４に記載の準車両道路リンク抽出装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１０−２３０５３１（Ｐ２０１０−２３０５３１Ａ）
【公開日】平成２２年１０月１４日（２０１０．１０．１４）
【国際特許分類】
【出願番号】特願２００９−７９１３０（Ｐ２００９−７９１３０）
【出願日】平成２１年３月２７日（２００９．３．２７）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２２年１０月１４日（２０１０．１０．１４）
【国際特許分類】
【出願日】平成２１年３月２７日（２００９．３．２７）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]