図面 (/)

技術 路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法

出願人 日本電気株式会社
発明者 寺本幸生
出願日 2009年3月17日 (10年4ヶ月経過) 出願番号 2009-063719
公開日 2010年9月30日 (8年9ヶ月経過) 公開番号 2010-217459
状態 未査定
技術分野 教示用装置 航行(Navigation) 特定用途計算機 交通制御システム 交通制御システム
主要キーワード 分割網 分割辺 一段下位 一段上位 部分網 許容値ε 各折れ線 分割経路
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2010年9月30日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

装置は、ある場所の状況に応じて当該場所を経由する経路検索されやすくしつつ、効率よい経路探索をすることが出来ない。

解決手段

路網図管理装置は、階層化され、各層において一段上位層の路の閉路で囲まれた領域ごとに分割されている路網図が、閉路を構成する上位層の各路の両側に当該路を境界とする分割網が関連付けられて格納された路記憶部と、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている注目位置側の分割網Gを、当該Gに注目位置を含む路が存在まで一段下位層から取得して、各層に於いて、当該Gの境界を構成する路と注目位置間の分割経路をGd内で探索して、Gdを分割経路で複数の分割網gに分割して、各gを路記憶部に記憶し、分割経路を1段上位の層に追加する分割手段を備える。

概要

背景

特許文献1は、道路を複数の階層に分類し、各階層データ階層内交差点及び上位階層の道路との交差点に関する情報、交差点間の道路に関する情報を備える地図データを用いたナビゲーションシステムを開示する。このシステムは、出発地目的地からそれぞれ上位の所定の階層の道路の交差点までの経路探査を行い、その後所定階層内での経路探査を行う。この地図データに於いて、下位の階層は、例えば上位の階層の道路により囲まれた範囲毎に分けて記憶される。

特許文献2は、適切な経路を探索する為に、階層化された地図情報更新する地図情報生成装置を開示する。この装置は、下位の階層に属す道路の移動コストが上位の階層に属す道路を利用するよりも低コストであるとき、この下位の階層に属す道路を上位の階層の地図情報へ追加する。この装置は、例えば県道であっても空いていて快適に走れるならば、国道と同じ階層の地図情報にこの県道を追加する。

特許文献3は、全国の地図データを読み込み、最上段階の選択基準の道路(例えば国道)を境界としてエリア分割する地図データ作成装置を開示する。この装置は、分割エリアナビ用データに変換した状態でのデータサイズが上限値を超えている場合は、次段階の選択基準道路(例えば県道・市町村道)を境界として再分割する。

非特許文献1は、空間インデックスを管理する一般的なデータ構造の例であるR-Treesを開示する。

概要

装置は、ある場所の状況に応じて当該場所を経由する経路を検索されやすくしつつ、効率よい経路探索をすることが出来ない。路網管理装置は、階層化され、各層において一段上位層の路の閉路で囲まれた領域ごとに分割されている路網が、閉路を構成する上位層の各路の両側に当該路を境界とする分割網が関連付けられて格納された路記憶部と、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている注目位置側の分割網Gを、当該Gに注目位置を含む路が存在まで一段下位層から取得して、各層に於いて、当該Gの境界を構成する路と注目位置間の分割経路をGd内で探索して、Gdを分割経路で複数の分割網gに分割して、各gを路記憶部に記憶し、分割経路を1段上位の層に追加する分割手段を備える。

目的

本願発明の目的は、上記課題を解決する路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

路網の詳細度に基づいて複数の層(2つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ)に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする2つの分割網を関連付けて格納された路記憶部と、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網(Gd)を、当該Gdに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Gdが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Gdの前記境界を構成する前記路の少なくとも2つと前記注目位置間の経路分割経路)を前記Gd内で探索して、前記Gdを前記分割経路で複数の分割網(gd)に分割して、前記Gdを前記路記憶部から削除して、各前記gdを前記路記憶部に記憶し、前記分割経路を1段上位の層に追加する分割手段を備える路網図管理装置

請求項2

当該Gdの前記境界を構成する前記路のおのおのと前記注目位置間の経路(分割経路)を前記Gd内で探索する前記分割手段を備える請求項1の路網図管理装置。

請求項3

最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網(Gs)および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網(Gt)を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索手段を備える請求項1または2の路網図管理装置。

請求項4

前記Gsと前記Gtが同一(G)であって、当該G内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網(Gt)を下位層から取得し、前記一方の位置と前記Gt間の経路(第4の経路)を前記G内で探索し、その後、前記Gtと当該第4の経路の交点と前記他方位置の経路(第5の経路)を当該下位層以下の層から探索し、前記第4の経路、および、前記第5の経路を直列に結合した移動経路を出力する前記探索手段を備える請求項3の路網図管理装置。

請求項5

同一層に於いて前記Gsと前記Gtが異なる場合に、前記Gsと前記Gt間の経路(第1の経路)を当該層の1段上位の層内で探索し、その後、前記Gsと当該第1の経路の交点と前記出発位置間の経路(第2の経路)と前記Gtと当該第1の経路の交点と前記目的位置間の経路(第3の経路)を当該層以下の層から探索し、前記第2の経路、前記第1の経路、および、前記第3の経路を直列に結合した移動経路を出力する前記探索手段を備える請求項3または4の路網図管理装置。

請求項6

イベント属性対応付けられた前記更新層の指定を格納する利用者情報記憶部と、前記注目位置、前記イベント属性を受信する受信手段と、前記出発位置と前記目的位置を入力する入力手段と、前記移動経路を表示する表示手段と、前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割手段を備える請求項3乃至5の何れかの路網図管理装置。

請求項7

前記注目位置、前記イベント属性を送信するする送信装置と、請求項6の路網図管理装置を包含する路網図管理システム

請求項8

路網の詳細度に基づいて複数の層(2つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ)に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする2つの分割網を関連付けて格納された路記憶部を備えたコンピュータに、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網(Gd)を、当該Gdに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Gdが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Gdの前記境界を構成する前記路の少なくとも2つと前記注目位置間の経路(分割経路)を前記Gd内で探索して、前記Gdを前記分割経路で複数の分割網(gd)に分割して、前記Gdを前記路記憶部から削除して、各前記gdを前記路記憶部に記憶し、前記分割経路を1段上位の層に追加する分割処理を実行させる路網図管理プログラム

請求項9

前記コンピュータに、当該Gdの前記境界を構成する前記路のおのおのと前記注目位置間の経路(分割経路)を前記Gd内で探索する前記分割処理を実行させる請求項8の路網図管理プログラム。

請求項10

前記コンピュータに、最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網(Gs)および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網(Gt)を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索処理を実行させる請求項8または9の路網図管理プログラム。

請求項11

前記コンピュータに、前記Gsと前記Gtが同一(G)であって、当該G内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網(Gt)を下位層から取得し、前記一方の位置と前記Gt間の経路(第4の経路)を前記G内で探索し、その後、前記Gtと当該第4の経路の交点と前記他方位置の経路(第5の経路)を当該下位層以下の層から探索し、前記第4の経路、および、前記第5の経路を直列に結合した移動経路を出力する前記探索処理を実行させる請求項10の路網図管理プログラム。

請求項12

前記コンピュータに、同一層に於いて前記Gsと前記Gtが異なる場合に、前記Gsと前記Gt間の経路(第1の経路)を当該層の1段上位の層内で探索し、その後、前記Gsと当該第1の経路の交点と前記出発位置間の経路(第2の経路)と前記Gtと当該第1の経路の交点と前記目的位置間の経路(第3の経路)を当該層以下の層から探索し、前記第2の経路、前記第1の経路、および、前記第3の経路を直列に結合した移動経路を出力する前記探索処理を実行させる、請求項10または11の路網図管理プログラム。

請求項13

イベント属性に対応付けられた前記更新層の指定を格納する利用者情報記憶部を備えた前記コンピュータに、前記注目位置、前記イベント属性を受信する受信処理と、前記出発位置と前記目的位置を入力する入力処理と、前記移動経路を表示する表示処理と、前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割処理を実行させる請求項10乃至12の何れかの路網図管理プログラム。

請求項14

路網の詳細度に基づいて複数の層(2つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ)に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする2つの分割網を関連付けて格納された路記憶部を備えたコンピュータが、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網(Gd)を、当該Gdに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Gdが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Gdの前記境界を構成する前記路の少なくとも2つと前記注目位置間の経路(分割経路)を前記Gd内で探索して、前記Gdを前記分割経路で複数の分割網(gd)に分割して、前記Gdを前記路記憶部から削除して、各前記gdを前記路記憶部に記憶し、前記分割経路を1段上位の層に追加する分割工程を有する路網図管理方法

請求項15

前記コンピュータが、当該Gdの前記境界を構成する前記路のおのおのと前記注目位置間の経路(分割経路)を前記Gd内で探索する前記分割工程を有する請求項14の路網図管理方法。

請求項16

前記コンピュータが、最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網(Gs)および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網(Gt)を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索工程を有する請求項14または15の路網図管理方法。

請求項17

前記コンピュータが、前記Gsと前記Gtが同一(G)であって、当該G内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網(Gt)を下位層から取得し、前記一方の位置と前記Gt間の経路(第4の経路)を前記G内で探索し、その後、前記Gtと当該第4の経路の交点と前記他方位置の経路(第5の経路)を当該下位層以下の層から探索し、前記第4の経路、および、前記第5の経路を直列に結合した移動経路を出力する前記探索工程を有する請求項16の路網図管理方法。

請求項18

前記コンピュータが、同一層に於いて前記Gsと前記Gtが異なる場合に、前記Gsと前記Gt間の経路(第1の経路)を当該層の1段上位の層内で探索し、その後、前記Gsと当該第1の経路の交点と前記出発位置間の経路(第2の経路)と前記Gtと当該第1の経路の交点と前記目的位置間の経路(第3の経路)を当該層以下の層から探索し、前記第2の経路、前記第1の経路、および、前記第3の経路を直列に結合した移動経路を出力する前記探索工程を有する、請求項16または17の路網図管理方法。

請求項19

イベント属性に対応付けられた前記更新層の指定を格納する利用者情報記憶部を備えた前記コンピュータが、前記注目位置、前記イベント属性を受信する受信工程と、前記出発位置と前記目的位置を入力する入力工程と、前記移動経路を表示する表示工程と、前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割工程を有する請求項16乃至18の何れかの路網図管理方法。

技術分野

0001

本発明は、路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法に関する。

背景技術

0002

特許文献1は、道路を複数の階層に分類し、各階層データ階層内交差点及び上位階層の道路との交差点に関する情報、交差点間の道路に関する情報を備える地図データを用いたナビゲーションシステムを開示する。このシステムは、出発地目的地からそれぞれ上位の所定の階層の道路の交差点までの経路探査を行い、その後所定階層内での経路探査を行う。この地図データに於いて、下位の階層は、例えば上位の階層の道路により囲まれた範囲毎に分けて記憶される。

0003

特許文献2は、適切な経路を探索する為に、階層化された地図情報更新する地図情報生成装置を開示する。この装置は、下位の階層に属す道路の移動コストが上位の階層に属す道路を利用するよりも低コストであるとき、この下位の階層に属す道路を上位の階層の地図情報へ追加する。この装置は、例えば県道であっても空いていて快適に走れるならば、国道と同じ階層の地図情報にこの県道を追加する。

0004

特許文献3は、全国の地図データを読み込み、最上段階の選択基準の道路(例えば国道)を境界としてエリア分割する地図データ作成装置を開示する。この装置は、分割エリアナビ用データに変換した状態でのデータサイズが上限値を超えている場合は、次段階の選択基準道路(例えば県道・市町村道)を境界として再分割する。

0005

非特許文献1は、空間インデックスを管理する一般的なデータ構造の例であるR-Treesを開示する。

0006

特開平5−27679号公報
特開2007−24515号公報
特開2004−226730号公報

先行技術

0007

2006年、シュプリンガー、アールツリーセオリー・アンドアプリケーション(R-Trees: Theory and Applications, Springer, 2006)

発明が解決しようとする課題

0008

カーナビゲーション装置などの経路探索において、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくすることが好ましい場合がある。例えば、或る場所でユーザの関心が高いイベントが発生(祭りや博覧会開催等)している期間中、移動途中のユーザが当該イベント会場寄り道できるような経路を優先して探索出来れば好ましい。

0009

階層構造を有する地図情報を利用して経路探索を行う装置がこのような探索を行う為には、当該イベント会場を経由する経路が上位層の地図情報に登録されていると良い。当該経路が主要でない経路であって、通常は下位層の地図情報にしか登録されていない場合は、イベントの開催に合わせて、カーナビゲーション装置などが動的に当該経路を上位層の地図情報に追加すると良い。

0010

ところで、特許文献1に開示されるナビゲーションシステムのように、階層化された地図情報の下位層を上位層の道路により囲まれた範囲に分割して記憶している経路探索装置が存在する。このような経路探索装置は、経路探索に於いてメモリ上に読み込む下位層の地図情報のデータ量を減らすことが出来る為、効率的な経路探索が可能である。

0011

しかしながら、このような装置は、特許文献2に開示されている装置のように、簡単に新たな経路を上位層に追加できない。その理由は、下位層が新たな経路に基づいて分割されていないからである。一方、特許文献2に開示された装置は、効率的な経路探索が出来ない。その理由は、下位層の分割が考慮されていないからである。

0012

即ち、特許文献1と特許文献2に開示された装置は、何れも、経路探索において、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくすることと、効率よい経路探索を両立することが出来ないという課題がある。特許文献3および非特許文献1に開示された技術もこの課題を解決しない。

0013

本願発明の目的は、上記課題を解決する路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法を提供することにある。

課題を解決するための手段

0014

本発明の一実施形態の路網図管理装置は、路網の詳細度に基づいて複数の層(2つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ)に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする2つの分割網を関連付けて格納された路記憶部と、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網(Gd)を、当該Gdに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Gdが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Gdの前記境界を構成する前記路の少なくとも2つと前記注目位置間の経路(分割経路)を前記Gd内で探索して、前記Gdを前記分割経路で複数の分割網(gd)に分割して、前記Gdを前記路記憶部から削除して、各前記gdを前記路記憶部に記憶し、前記分割経路を1段上位の層に追加する分割手段を備える。

0015

本発明の一実施形態の路網図管理プログラムは、路網の詳細度に基づいて複数の層(2つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ)に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする2つの分割網を関連付けて格納された路記憶部を備えたコンピュータに、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網(Gd)を、当該Gdに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Gdが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Gdの前記境界を構成する前記路の少なくとも2つと前記注目位置間の経路(分割経路)を前記Gd内で探索して、前記Gdを前記分割経路で複数の分割網(gd)に分割して、前記Gdを前記路記憶部から削除して、各前記gdを前記路記憶部に記憶し、前記分割経路を1段上位の層に追加する分割処理を実行させる。

0016

本発明の一実施形態の路網図管理方法は、路網の詳細度に基づいて複数の層(2つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ)に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする2つの分割網を関連付けて格納された路記憶部を備えたコンピュータが、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網(Gd)を、当該Gdに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Gdが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Gdの前記境界を構成する前記路の少なくとも2つと前記注目位置間の経路(分割経路)を前記Gd内で探索して、前記Gdを前記分割経路で複数の分割網(gd)に分割して、前記Gdを前記路記憶部から削除して、各前記gdを前記路記憶部に記憶し、前記分割経路を1段上位の層に追加する分割工程を有する。

発明の効果

0017

本発明にかかる路網図管理装置は、ある場所の状況に応じて当該場所を経由する経路が検索されやすく、かつ、効率的な経路探索を可能とする。

図面の簡単な説明

0018

路網図管理システム10の構成図である。
層表30の構成図である。
網表40の構成図である。
曲形状45の説明図である。
頂点表50の構成図である。
路網例2(層1)の説明図である。
路網例2(層2)の説明図である。
路網例2の層表30の構成図である。
路網例2の網表40の構成図である。
路網例2の頂点表50の構成図である。
利用者情報記憶部27に格納されるデータの構成図である。
分割手段25の動作フローチャートである。
路網例2(層1)の経路追加の説明図である。
路網例2(層2)の分割の説明図である。
路網例2の層表30の経路追加・分割後の構成図である。
路網例2の網表40の経路追加・分割後の構成図である。
路網例2の頂点表50の経路追加・分割後の構成図である。
探索手段26の動作フローチャートである。
探索手段26の再帰探査の動作フローチャートである。
路網例1(層1)の説明図である。
路網例1(層2)の説明図である。
路網例1(層3)の説明図である。
路網例1(層1)の分割経路探査の説明図である。
路網例1(層2)の分割経路探査の説明図である。
路網例1(層3)の分割経路探査の説明図である。
路網例1(層2)の経路追加の説明図である。
路網例1(層3)の分割の説明図である。
路網例1(層1)の経路追加の説明図である。
本発明にかかる路網図管理装置20の基本的構成を示す。

実施例

0019

図1は、路網図管理システム10の構成図である。路網図管理システム10は、1つ又は複数の路網図管理装置20と1つ又は複数の送信装置11を包含する。送信装置11は端末12を備えていても良い。

0020

路網図管理装置20は、例えば、カーナビゲーション装置、ウォーキング道案内装置海路案内装置、空路案内装置である。路網図管理装置20は分割手段25、路記憶部28を備える。路網図管理装置20は、受信手段22、入力手段23、表示手段24、探索手段26、利用者情報記憶部27を備えていても良い。

0021

路記憶部28はディスク装置等の記憶装置である。路記憶部28は、道路、山道、海路、空路等のネットワーク図(路網図)を階層化して記憶する。上位のネットワーク図は、主要な路(高速道路幹線国道等)だけのネットワーク記述しており、その詳細度は低い(記述が粗い)。下位のネットワーク図は、主要でない道路(小さな市町村道等)のネットワークも記述しており、その詳細度は高い。

0022

図12図13図14は路記億部28に記憶されている路網図の例(路網例1)である。これらの図は、周辺の階層化された道路網図である。図12は最上位層(例えば層1)の道路網図である。図12は、通り名のつくような大きな国道を記述している。図13は中間層(層2)の道路網図である。図13は、図12の道路網図に、やや道幅の狭い国道や県道、それらの交差点等の情報を追加したものとなっている。図14は下位層(層3)の道路網図である。図14は、図13の道路網図に市道ベルの道路を追加し、更に詳細なものになっている。なお、層の識別子付けは、上例と異なっていても良い(例えば、最下位層を層1とする)。また、本発明に於いて、階層の数は2以上であればよく、本例の如く3層に限定されない。

0023

送信装置11は、端末12等から入力した、ある地点に於ける祭りや博覧会開催等の状況情報を路網図管理装置20に送信する。状況情報は、発生しているイベントの種類等(イベント属性61)とその発生位置(注目位置13)等である。受信手段22は受信機等であり、送信装置11から送信された状況情報を受信する。

0024

分割手段25は、注目位置13が探索されやすいように、路記憶部28の路網図(道路網図等)を更新する。

0025

入力手段23はタッチパネルキーボード等であり、出発位置目的位置を包含する経路探索要求を入力する。

0026

探索手段26は、入力手段23から入力された出発位置から目的位置迄の移動経路を、路記憶部28の路網図から検索する。但し、出発位置は、路網図管理装置20等が備えたGPS装置(Global Positioning System)(図示されない)から取得しても良い。探索手段26は探索した移動経路を表示手段24に出力する。表示手段24はディスプレイ装置等である。探索手段26は、移動経路を地図上にオーバーラップ等させて表示しても良い。

0027

利用者情報記憶部27はディスク装置等の記憶装置である。利用者情報記憶部27は路網図管理装置20の利用者の情報を格納する。

0028

分割手段25及び探索手段26は、その機能を果たす専用ハードウェアとして実装されても良いし、路網図管理プログラム29がメモリに格納されてコンピュータ21のプロセッサで実行されることにより、その機能を果たすように実装されても良い。

0029

路記憶部28は、階層化された路網図の各層を、頂点と頂点間の辺から構成される網として格納する。頂点は道路等の交差点をモデル化したものである。頂点は道路等の端点行き止まり等)を表す場合もある。辺は道路等の交差点間等の区間をモデル化したものである。具体的に、路記憶部28は階層化された路網図を、例えば、層表30、網表40および頂点表50という形式で格納する。

0030

図2は層表30の構成図である。層表30は路網図の各層対応にエントリを有する。例えば最上段(第1エントリ)が最上位層に対応し、その下の第2エントリが最上層の1段下の層に対応する。第3エントリ以降、各エントリは順に下位の層に対応する。各エントリは対応する層に属する網の識別子である網ID32を格納する。網ID32は、例えばGhnという形式である。ここで、hは層の識別子(h=1以上)でありnは層h内の通し番号である。hnは網番号である。

0031

路網図の下位の層は、1段上位の層における辺の閉路で囲まれた領域ごとの分割網に分割されて格納されている。ここで、閉路はコード(chord)を含まない閉路である。分割手段25や探索手段26は、網の分割や経路探索に於いて、閉路に含まれる辺や当該辺の端点を介して、層間の遷移を行う。

0032

なお、下位の層に属する網の数は、上位の層に属する網の数より大きい。最上位層に属する網の数は通常1である。路網図は、経路探索やアクセス効率化のために分割されている。

0033

図5は頂点表50の構成図である。頂点表50は網ごとに分割されて存在する。頂点表50は、網ID32と当該網に属する頂点ごとのエントリから構成される。各エントリは、頂点ID51と座標52を包含する。頂点ID51は頂点の識別子であり、例えばv(g、n)という形式である。gは当該頂点が属する網の網番号である。nは網Gg内の通し番号である。座標52は当該頂点の位置を表す。位置は、例えば緯度経度の対である。位置は他の座標系に基づく値であっても良い。

0034

図3は網表40の構成図である。網表40は網ごとに分割されて存在する。網表40は、網ID32と当該網に属する辺ごとのエントリから構成される。各エントリは、辺ID41、始点42、終点43、上位辺44、曲形状45、長さ46、左網47、右網48等を包含する。

0035

辺ID41は、エントリに対応した辺(以下、対応辺)の識別子である。辺ID41は、例えばe(g、n)という形式である。ここで、gは対応辺が属する網の網番号である。nは網Gg内の通し番号である。

0036

始点42と終点43は、対応辺の両端の頂点の頂点ID51を示す。上位辺44は、対応辺がモデル化する道路等の区間をモデル化する1段上位層の辺の辺ID41である。例えば、図13における辺e1乃至e8のおのおのの上位辺44は図12に於ける辺Eである。このように層hの辺(E、等)は、下位の層h+1においていくつかの辺(e1、等)に分割されて表現される。

0037

辺は道路等の区間をモデル化する。従って、辺は曲線である場合がある。曲形状45はこの曲線の形状を記述する。曲形状45は、例えば図4に示すように、曲線を近似する折れ線中間座標系列として記述したものでも良い。曲形状45は、曲率を用いる等、他の形式の記述データであっても良い。

0038

長さ46は対応辺がモデル化する道路等の距離である。長さ46は、曲形状45を反映した値であることが好ましい。長さ46は、道路等の制限速度高速料金等も反映した移動コストを格納しても良い。

0039

左網47と右網48は対応辺に関連付けられている1段下位層の網ID32を格納する。上述したように、1段下位の層は、対応辺を含む2つの閉路で囲まれた領域ごとに分割されている。従って、1段下位の層には、対応辺(正確には、対応辺がモデル化する道路等の区間をモデル化する下位の層の辺群)を境界とする2つの網が存在する。左網47と右網48はこの2つの網の網ID32を格納する。

0040

辺の両端である始点42と終点43は区別されており辺は方向を持つ。従って、位置qが与えられたとき、分割手段25等は、位置qが対応辺の左右どちら側に位置するかを判別して、qが属する下位層の網ID32を取得できる。例えば、対応辺に関連付けられている折れ線がr=(m1,m2,...,mk)であるとき、分割手段25等は、線分(mi,mi+1),i=1,2,...,k−1のなかからqと最も近い線分(mx,mx+1)を決定して、2つのベクトル(mx,mx+1)と(mx+1,q)の外積を求める。分割手段25等は、例えば符号が正である場合は左網47から、そうでない場合は右網48から、下位層の網ID32を取得する。分割手段25等は、符号の正負と左右の対応付けを逆にしても良い。上記計算の詳細は、Ronald L. Graham: An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. (1972)等の文献に記載されている。

0041

なお、左網47と右網48の一方または両方がNullである場合がある。対応辺が、海岸線の道路等をモデル化している場合、対応辺の海側、例えば左網47はNullとなる。また、対応辺が最下層に属す場合等、左網47と右網48の両方がNullとなる。

0042

なお、頂点表50は、頂点ID51対応に当該頂点に接続されている全ての辺の辺ID41を格納していても良い。

0043

図6−Aと6−Bは路記憶部28に格納されている路網図の例(網路例2)である。図6−Cは本路網図を記述する層表30を例示する。図6−Dは本路網図を記述する網表40を例示する。図6−Eは本路網図を記述する頂点表50を例示する。

0044

本例の路網図は、図6−Aの上位層(層1)と図6−Bの下位層(層2)の2層から構成される。層1は1つの網G11を包含する。網G11は、辺e(11、1)、e(11、2)e(11、3)で構成される閉路で囲まれた領域Aと、辺e(11、3)、e(11、4)、e(11、5)で構成される閉路で囲まれた領域Bを有する。従って、層2は、領域Aに対応する網G21と領域Bに対応する網G22に分割されて記憶される。

0045

上述の辺は例えば全て主要道路をモデル化したものである。層2は、主要道路をモデル化した辺e(21、1)乃至e(21、5)およびe(22、1)乃至e(22、5)に加え、非主要道路をモデル化した辺e(21、6)とe(22、6)を包含する。また、e(21、6)とe(22、6)の始点42と終点43の頂点v(21、3)、v(21、5)、v(22、2)、v(22、4)も追加されている。即ち、層2の方が層1より詳細度が高い。

0046

層1の辺e(11、3)の例えば左側は領域Aである。従って、当該辺の左網47には、層2における領域Aの網の網ID32であるG21が格納されている。層1の辺e(11、3)の右側は領域Bである。従って、当該辺の右網48には、層2における領域Bの網の網ID32であるG22が登録されている。同様に、層1の辺e(11、1)の左側は領域Aである。従って、当該辺の左網47には、層2における領域Aの網の網ID32であるG21が登録されている。

0047

なお、e(11、3)と、e(21、5)およびe(21、4)は同じ道路等の区間をモデル化している。従って、e(21、5)およびe(21、4)の上位辺44はともに、e(11、3)となる(図6−D)。同様に、e(11、3)と、e(22、1)およびe(22、2)は同じ道路等の区間をモデル化している。従って、e(22、1)およびe(22、2)の上位辺44はともに、e(11、3)となる(図6−D)。

0048

また、e(21、6)およびe(22、6)は層2のみでモデル化された非主要道路に対応するため、上位辺44は格納されていない(Null値である)。

0049

図7は、利用者情報記憶部27に格納されるデータの構成図である。利用者情報記憶部27は、イベント属性61と更新層62を対にして記憶している。更新層62は、イベント属性61を持つイベントが発生したとき、当該イベントの発生位置に至る経路を路網図のどの層にまで追加するかを指定する。発生位置への経路が上位の層に追加されるほど、発生位置を通過する経路が探索されやすくなる。従って、利用者の興味が高いイベント属性61に対応する更新層62は上位の層を指定する。

0050

図8は分割手段25の動作フローチャートである。分割手段25は、受信手段22からイベント属性61、注目位置13(q)と誤差を入力する(S1)。分割手段25は、利用者情報記憶部27から入力したイベント属性61に対応する更新層62を取得し(S2)、層表30から最上位層の網ID32を取得する(S3)。

0051

取得した網ID32の網(Ghと略記)の網表40と頂点表50を路記憶部28からメモリに読み込んだ後、分割手段25はGh内でqの最近傍辺を探索して、その辺ID41を取得する(S4)。分割手段25は、各辺の始点42及び終点42の座標52や、曲形状45の折れ線等を参照して最近傍辺を決定する。このとき、分割手段25は非特許文献1に記載されている技術を用いても良い。

0052

例えばqが図6−Aの×印の位置であるとき、分割手段25は最近傍辺の辺ID41としてe(11、3)を取得する。

0053

次に、分割手段25はqが最近傍辺上に位置しているかを判別する(S5)。このとき、分割手段25は、qと最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。距離は平面上の距離であり、移動経路の長さ46ではない。誤差はq等の位置測定装置測定誤差を示す値である。

0054

qが最近傍辺上に位置していない場合(S5でN)、分割手段25はGhの網ID32をスタックプッシュダウンする(S6)。同手段は、qが最近傍辺の左右の何れに位置するかを判断し、qが左側に位置すれば左網47から、qが右側に位置すれば右網48から、1段下位のh+1層の網ID32(この網ID32の網が新たなGhとなる)を取得する(S7)。

0055

qが図6−Aの×印の位置であるとき、分割手段25は最近傍辺e(11、3)の左網47(図6−D)から網ID32としてG21を取得する。

0056

その後、分割手段25は、取得したh+1層の網ID32がNullでなければ(SGでN)S4のステップに戻る。通常、S7で取得したh+1層の網ID32がNullとなることはない。しかし、qの入力値予想外の誤差が含まれていた場合等で、qが最近傍辺上に位置しているにもかかわらず分割手段25が位置していないと判断(S5でN)をし、かつ、最近傍辺の一方または両方にh+1層の網が無いと、例外的にNullとなり得る。

0057

qが最近傍辺上に位置している場合(S5でY)、分割手段25はGhが最上位の層でないことを、例えば層表30を参照して確認する(S8でN)。Ghが最上位の層であれば(S8でY)、分割手段25は処理を終了する。qが最上位層の辺上に位置するのであれば、経路追加は必要ないからである。

0058

なお、S7で取得したh+1層の網ID32がNullである場合(SGでY)、分割手段25は、スタックの最上段をポップアップして(SH)、S8の処理を行う。

0059

qが最上位層でない最近傍辺上に位置している場合(S5でY、S8でN)、分割手段25は、qから1段上位の層(h−1層)に通じる各辺の頂点への経路(但し、上位層に通じる辺上の経路は除く)(分割経路)を求める(S9)。h−1層に通じる辺とは、Ghの境界を構成する辺であり、網表40において上位辺44に値が設定されている辺である。

0060

例えばqが図6−Bの×印の位置であるとき、qはG21において最近傍辺e(21、6)上に位置している(S5でY)。従って、分割経路は、qとv(21、5)間およびqとv(21、5)間となる。

0061

分割手段25は、Ghを分割経路上の辺を境界とする部分網に分割し、分割して出来た網の網表40および頂点表50を新たに生成する(SA)。分割手段25は、作成された網の網ID32を層表30に追加する。

0062

分割手段25は、例えば図6−BのG21をe(21、6)を境界として分割し、図9−Bに図示する新たな網G23およびG24を生成する。分割手段25は、元のG21の網表40および頂点表50(図6−D、図6−E)を基に、G23およびG24の網表40および頂点表50(図9−D、図9−E)を生成する。

0063

分割手段25は、Ghにおける分割経路上の辺をh−1層に追加する(SB)。分割手段25は、追加対象となる網の網ID32をスタックの最上段から取得する。また、同手段は追加した辺が上位辺44を有する辺と交わっていれば、当該上位辺44を追加された頂点で分割する。

0064

例えば分割手段25は、図9−AのG11に辺e(11、6)を追加して、元の辺e(11、3)を頂点v(11、6)で分割する。分割手段25は、元の辺e(11、2)を頂点v(11、5)で分割する。

0065

分割手段25は、h−1層の辺の左網47と右網48に、分割した網の網ID32を格納する(SC)。具体的に、分割手段25は、先ず追加した辺の左網47と右網48に分割した網の網ID32を格納する。さらに同手段は、h−1層において分割したGhの網ID32を左網47または右網48に有する辺またはその分割辺の左網47と右網48に、分割した網の網ID32を格納する。

0066

例えば、図9−Dにおいて、追加された辺e(11、6)の左網47にはG23が、右網48にはG24が格納される。また、図6−Dにおいて、分割前のG21を左網47に持つe(11、1)の左網47には分割後のG23が格納される。

0067

ついで、分割手段25は分割前の網Ghの網表40および頂点表50を削除する(SD)。分割手段25は、削除された網の網ID32を層表30から削除する。

0068

例えば、分割手段25は、図6−Dにおける網G21の網表40を削除する。

0069

h−1層が更新層62でなければ(SEでN)、分割手段25はスタックの最上段から網ID32を取得した後、スタックをポップアップして(SF)S9に戻る。h−1層が更新層62であれば(SEでY)、分割手段25は処理を終了する。

0070

以上の説明から明らかなように、図9−Cは路網例2の経路追加・分割後の層表30の例である。図9−Dは路網例2の経路追加・分割後の網表40の例である。図9−Eは路網例2の経路追加・分割後の頂点表50の例である。

0071

図15乃至図20は、図12乃至図13に示す階層化された道路網の分割を説明する図である。図15乃至図20は、注目位置13(q)が与えられたとき、分割手段25が地図の更新を行う際の手順の流れを例示する。この例は、qを通過する経路を最上位の層に追加するものである。即ち、更新層62が最上位層である場合の例である。

0072

図15は、図12と同様に最上位(層1)の道路網の一部を抜粋した図である。図15はqの最近傍辺がeであることを示している。また、受信手段22で取得した位置情報は、高々εの誤差を含むとする。ここで、qと辺eの間の距離がある許容値ε以下であることと、qを中心として半径εの円とeの曲形状45で与えられる折れ線が交差することは等価である。図15破線で描かれているqを中心として半径εの円とeの折れ線は交差していないので、qは辺e上に位置しない。従って、分割手段25は、下層の道路網を取得する。具体的に分割手段25は、eのq側(左網47または右網48)に関連付けられている下位の道路網を取得する。

0073

図16は、辺eに関連付けられて取得された側の下位の層の道路網の抜粋を示している。分割手段25は、新たに道路網の一部を取得したら、その道路網に対して最近傍辺を求めるために曲形状45等のデータ構造(R-tree)を読み込み、qの最近傍辺を求める。図16では、辺e'が層2におけるqの最近傍辺であることを示している。階層1の場合と同様に、図16の破線で描かれているqを中心として半径εの円とe'の折れ線は交差しないので、qは辺e'上に位置しない。従って、分割手段25は、図17に示すe'のq側に関連付けられている下層(層3)の道路網Gを取得する。

0074

このとき、Gにおけるqの最近傍辺はqから十分近いので、分割手段25はそれ以上層を下る手続きを終了する(図8のS5でY)。分割手段25は、次にこの道路網Gに対して、Gの上位の層2に存在するGを囲む辺への最短経路を求める。

0075

図18はこの手続きの結果を示す。辺e1'は、qから辺e1への最短経路の両端点をつなぐ辺である。分割手段25は、Gを囲むすべての辺に関してqからの最短経路を求めるが、図が煩雑になるため図18には示していない。

0076

分割手段25は、いま求めたqからGを囲む辺への最短経路e1'、e2'、e3'等により、Gをさらに細かく分割する。分割手段25は、Gの上位層2のグラフG'(図16)に各辺e1'、e2'、e3'等を追加するようにG'に対する網表40を更新する。例えば、分割手段25は、曲形状45のR-treeに対して、e1', e2', e3'…の各折れ線を追加する。

0077

そして、分割手段25は、G'のそれぞれの辺と分割された道路網の関連付けを行う。例えば、図19は、Gを分割した結果、e1', e2' および上位の階層2に存在する辺ei乃至ei+5によって囲まれる道路網g1が新たに得られていることを示している。このとき、分割前はei の右網48としてGが関連付けられていたが、分割後の関連付けの更新として、ei の右網48はg1となる。

0078

最終的に、分割手段25は、G'においてG'を囲む最上位のグラフG''の各辺への最短経路を求め、その経路をG''へ追加する(図20)ように網表40および頂点表50の更新を行う。

0079

図10は、探索手段26の動作フローチャートである。探索手段26は、受信手段22から出発位置(s)、目的位置(t)と誤差を入力する(S11)。探索手段26は、出発位置を路網図管理装置20等が備えるGPS装置から取得しても良い。探索手段26は、層表30から最上位層の網ID32を取得する(S12)。

0080

取得した網ID32の網(Ghと略記)の網表40と頂点表50をメモリに読み込んだ後、探索手段26はGh内でsの最近傍辺(最近傍辺s)とtの最近傍辺(最近傍辺t)とを探索して、おのおのの辺ID41を取得する(S13)。次に、探索手段26はsが最近傍辺s上に位置している、または、tが最近傍辺t上に位置しているかを判別する(S14)。このとき、探索手段26は、sまたはtと各々の最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。

0081

sとtの何れもが最近傍辺上に位置していない場合(S5でN)、探索手段26は、sが最近傍辺の左右の何れに位置するかを判断する。そして同手段は、sが左側に位置すれば左網47から、sが右側に位置すれば右網48から、1段下位のh+1層の網ID32(当該網を網Gh+1sと略記)を取得する(S15)。探索手段26は、tが最近傍辺の左右の何れに位置するかを判断し、tが左側に位置すれば左網47から、tが右側に位置すれば右網48から、1段下位のh+1層の網ID32(当該網を網Gh+1tと略記)を取得する(S16)。Gh+1sおよびGh+1tの網ID32が一致すれば(S17でY)、探索手段26はS13に戻る。

0082

Gh+1sおよびGh+1tの網ID32が一致すれば(S17でY)、探索手段26はGh内で、Gh+1sとGh+1t間の経路(経路2)を探索して取得する(S18)。ここで、Gh+1sとGh+1t間の経路とは、Gh+1sを囲む辺上の各頂点からGh+1tを囲む辺上の各頂点への経路の内で距離が最短の経路を指す。Gh+1sを囲む辺とは、左網47または右網48にGh+1sの網ID32が格納されている辺である。また、経路の距離は当該経路に属する辺の長さ46の合計値である。なお、探索手段26は、経路の探索の為に、Dijkstraのアルゴリズム等の一般的な検索アルゴリズムを用いることができる。

0083

図9−AにおいてG24がGh+1sである場合、Gh+1sを囲む辺上の各頂点は、v(11、3)、v(11、5)、v(11、6)となる。

0084

次に、探索手段26はsと経路2のs側の端点(Gh+1sの周辺上の頂点となる。sh+1と略記)の間の経路(経路1)をh+1以下の層から再帰的探索により取得する(S19)。図11は再帰的探索の詳細を示す。更に、探索手段26は経路2のt側の端点(Gh+1tの周辺上の頂点となる。th+1と略記)とtの間の経路(経路3)をh+1以下の層から再帰的探索により取得する(S1A)。

0085

探索手段26は、経路1、経路2、経路3をつなげてsからtへの移動経路を取得する(S1B)。最後に、探索手段26は、sからt移動経路を表示手段24に表示する(S1I)。

0086

探索手段26はsが最近傍辺s上に位置している、かつ、tが最近傍辺t上に位置している場合(S14でY、S1CでY)、Gh内でsからtへの移動経路検索を行う(S1D)。

0087

sまたはtの一方(例えばs)が最近傍辺上に位置しているが、他方(例えばt)が最近傍辺上に位置していない場合(S14でY、S1CでN)、探索手段26は以下の処理を行う。

0088

探索手段26は、tが最近傍辺の左右の何れに位置するかを判断し、tが左側に位置すれば左網47から、tが右側に位置すれば右網48から、1段下位のh+1層の網ID32(当該網を網Gh+1tと略記)を取得する(S1E)。

0089

その後、探索手段26は、Gh内で、sとGh+1t間の経路(経路4)を探索して取得する(S1F)。ここで、sとGh+1t間の経路とは、sからGh+1tを囲む辺上の各頂点への経路の内で距離が最短の経路を指す。Gh+1tを囲む辺とは、左網47または右網48にGh+1tの網ID32が格納されている辺である。

0090

探索手段26は経路4のt側の端点(Gh+1tの周辺上の頂点となる。th+1と略記)とtの間の経路(経路5)をh+1以下の層から再帰的探索により取得し(S1G)、最後に経路4と5を連結してsからtへの移動経路を取得する(S1H)。

0091

tが最近傍辺上に位置しているがsが最近傍辺上に位置していない場合、探索手段26は、sとtの立場逆転して同様の処理を行う。

0092

図11は、探索手段26の再帰的探査の動作フローチャートである。図11は、th+1とtの間の第5の経路をh+1以下の層から検索する場合(S1G等の詳細)を例示する。

0093

探索手段26は、Gh+1tの網ID32とth+1をスタックの最上段にプッシュダウンする(S21)。探索手段26はtが最近傍辺の左右の何れに位置するかを判断し、tが左側に位置すれば左網47から、右側に位置すれば右網48から、1段下位のh+2層の網ID32(当該網を網Gh+2tと略記)を取得する(S22)。

0094

探索手段26は、Gh+1内で、th+1とGh+2t間の経路を探索して取得する(S23)。なお、当該経路の端点となるGh+2tの周辺上の頂点は、th+2として参照される。
探索手段26は、検索した経路をS22でプッシュダウンしたスタックの最上段に追記する(S24)。

0095

Gh+2tの網表40と頂点表50をメモリに読み込んだ後、探索手段26はGh+2t内でtの最近傍辺を取得する(S25)。探索手段26は、tが最近傍辺上に位置しているかを判別する(S26)。このとき、探索手段26は、tと最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。

0096

tが最近傍辺上に位置しなければ(S26でN)、探索手段26はS21に戻る。このときGh+2tは新たなGh+1となり、th+2は新たなth+1となる。

0097

tが最近傍辺上に位置すれば(S26でY)、探索手段26はGh+2内でth+2とtの間の経路6を求める(S27)。

0098

最後に探索手段26は、スタックを一段ずつポップアップしながら、スタックに記憶していた経路を順次tから遠ざかる方向に経路6と連結して経路5を取得して(S28)、処理を終了する。

0099

本実施形態の路網図管理システム10は、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくする。その理由は、分割手段25が、注目位置13を経由する経路を上位の層に追加するからである。

0100

さらに、本実施形態の路網図管理システム10は、経路検索および経路追加を効率的に行うことが出来る。その理由は、路網図を部分網に分割して路記憶部28に記憶しており、経路検索および経路追加において、必要な部分しかメモリに読み込まず、また、当該部分内でのみ経路探索を行うからである。

0101

さらに、本実施形態の路網図管理システム10は、利用者の嗜好に基づいた経路追加を行うことが出来る。その理由は、利用者情報記憶部27に基づいて、経路追加をする層を決定するからである。

0102

本発明の第2の実施形態の路網図管理装置20の分割手段25は、qから1段上位の層(h−1層)に通じる所定数(2、等)の辺の頂点だけへの経路を求める(図8のS9)。辺の選択は、各辺対応に網表40に登録されている優先度等に基づいて行う。

0103

本実施形態の路網図管理装置20は経路追加を高速に実施できる。その理由は、分割経路の探索数が限定されるからである。

0104

また、路網図管理装置20は、経路追加を常に所定層(例えば最上層)以下の層に行うこととしてもよい。この場合、路網図管理装置20は利用者情報記憶部27、受信手段22を備えなくても良い。

0105

さらに、路網図管理装置20は、入力探索手段26、表示手段24、探索手段26を備え無くても良い。入力探索手段26、表示手段24、探索手段26は、路記憶部28を共有する探索装置(図示されない)が備えても良い。

0106

図21は、本発明にかかる路網図管理装置20の基本的構成を示す。路網図管理装置20は、路記憶部28と分割手段25を備える。

0107

10 路網図管理システム
11送信装置
12端末
13注目位置
20路網図管理装置
21コンピュータ
22 受信手段
23入力手段
24 表示手段
25 分割手段
26 探索手段
27利用者情報記憶部
28 路記憶部
29 路網図管理プログラム
30 層表
32 網ID
40 網表
41 辺ID
42 始点
43終点
44 上位辺
45曲形状
46 長さ
47 左網
48 右網
50頂点表
51 頂点ID
52座標
61イベント属性
62更新層

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 株式会社パークランドの「 レンタル車両管理方法」が 公開されました。( 2019/05/16)

    【課題】レンタル対象をそのレンタル対象のユーザの携帯端末を用いて管理する新規な技術を提供する。【解決手段】固有の信号を発信する発信機32がレンタル車両12に搭載されている。レンタル車両12を借用してい... 詳細

  • 株式会社パークランドの「 フリー・フローティング式レンタル車両管理方法」が 公開されました。( 2019/05/16)

    【課題】ユーザの携帯端末とレンタル車両に搭載された発信機とを用いてフリー・フローティング式レンタル車両管理方法を提供する。【解決手段】固有の信号を発信する発信機32がレンタル車両12に搭載されている。... 詳細

  • 三菱電機株式会社の「 車両用走行支援装置」が 公開されました。( 2019/05/09)

    【課題】確実に障害物の検出を行うことが可能な車両用走行支援装置を提供する。【解決手段】障害物検出位置情報を出力する第1の障害物検出部、障害物大きさ情報を出力する第2の障害物検出部、障害物位置情報を記憶... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ