JPH1019587A - ベクトル地図における所定時間内到達可能範囲算出方法 - Google Patents

Abstract

(57)【要約】 【課題】 ベクトル地図において、指定したノードから
指定した時間で到達可能な範囲を高速かつ高精度に算出
できる到達可能範囲算出方法を提供する。 【解決手段】 複数のノード間を接続するリンクからな
るベクトル地図上で、指定ノードから指定時間で到達可
能な範囲を算出する到達可能範囲算出方法において、ベ
クトル地図データ４と、各ノードの到達時間探索履歴を
記録する探索履歴テーブル６と、探索したノードを格納
する探索ノードテーブル７を用いて、各ノードに対して
高精度探索方法または高速探索方法のどちらを適用する
かを切替パラメータ８をしきい値として各ノードにおけ
る接続リンク数によって判定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ディジタル地図を
用いた経路シミュレーションなどに用いられるベクトル
地図における所定時間内到達可能範囲算出方法に関し、
特に、計算速度と解の精度がともに要求されるベクトル
地図データを用いた経路シミュレーションに適用可能な
ベクトル地図における所定時間内到達可能範囲算出方法
に関する。

【０００２】

【従来の技術】例えば、レンタカー店頭などで所望の時
間内に到達できる観光地などを検索するシステムにおい
て、到達経路をディジタル地図を用いた経路シミュレー
ションによって予測する場合に、高速化および高精度化
が課題となっている。ベクトル地図上のある地点から所
定時間内に到達することのできる範囲を求めるには、ベ
クトル地図データを用いて最短路探索をおこなえばよ
い。リンクコストとしてそのリンクの通行時間をとれ
ば、ベクトル地図上のある地点から所定時間内に到達す
ることのできるすべての地点は、各ノードへの出発点ノ
ードからのリンクコストの総和が最小の経路（最短路と
呼ぶ）を、出発点ノードからのリンクコストの総和が制
限内で小さいノードから順次求めていく問題を解いた際
に探索したノードとして求められる。この問題はグラフ
の最短路問題の一種であり、最短路探索方法によって解
くことができる。

【０００３】公知の最短路探索方法として、石畑清著
「アルゴリズムとデータ構造」（岩波書店、１９８９年
３月３０日発行）に記載のダイクストラ法がある。ダイ
クストラ法の概略を以下に記す。以後、出発点ノードか
らあるノードへ至る一つの経路上のリンクコストの総和
を、そのノードの経路コストと呼ぶことにする。また、
リンクコストは非負の実数値とする。ステップ１．ま
ず、経路コストが計算されていないノードの集合Ｕ、経
路コストが計算されたが最短路は未確定のノードの集合
Ｖ、最短路が確定しているノードの集合Ｗをすべて空に
しておく。すべてのリンクに対してリンクコストを設定
する。ステップ２．出発点ノードについて、経路コスト
を０に設定し、集合Ｖに加える。また、出発点ノード以
外のすべてのノードについて、経路コストを無限大（あ
らゆる経路コストより大きい値）に設定し、集合Ｕに加
える。ステップ３．集合Ｖの要素で経路コストが最も小
さいノード（注目ノード）ｐを集合Ｖから除き集合Ｗに
加える。ステップ４．注目ノードｐに接続しているリン
ク（接続リンク）が向かうノード（接続ノード）ｑのす
べてについて、ノードｐとノードｑを結ぶリンクのリン
クコストとノードｐの経路コストの和を求める。その値
がノードｑの経路コストより小さいならば、それを新た
な経路コストとし、以下の処理をおこなう。４−１）ノ
ードｑが集合Ｕに属していれば、ノードｑを集合Ｕから
除き集合Ｖに加え、ノードｑからノードｐへ向かうポイ
ンタを付ける。４−２）ノードｑが集合Ｖに属していれ
ば、ノードｑの親ノードを示すポインタをノードｐへ付
け替える。ステップ５．集合Ｖが空集合でなければ、ス
テップ３．に戻る。集合Ｖが空集合であれば、探索は終
了する。このとき、集合Ｗに属する各ノードのポインタ
をたどれば、出発点ノードからそのノードへの最短路が
求められる。以上がダイクストラ法の概略である。

【０００４】このダイクストラ法では、集合Ｖから最小
の経路コストをもつノードｐを取り出して注目ノードと
するので、ノードｐの接続ノードｑの処理（集合Ｖへの
移動、あるいは集合Ｖに属するものの経路コストの更
新）によって集合Ｖに含まれているノードの経路コスト
の最小値が減少することはない。すなわち、ノードｐが
集合Ｖから除かれ集合Ｗに加えられたということは、そ
のときのノードｐの経路コストが将来減少することはな
く、出発点ノードからノードｐへ至る最短路が求められ
たということを意味している。したがって、ダイクスト
ラ法による解の精度は完全である。

【０００５】また、別の公知の最短路探索方法として、
浜田ほか「ディジタル地図における経路探索法の高速化
の検討と評価」（情報処理学会第４８回全国大会講演論
文集（分冊１）、ｐｐ．１−３５５、１−３５６、１９
９４年）に記載の優先リンク法がある。優先リンク法の
概略を以下に記す。 ステップ１．まず、経路コストが計算されていないノー
ドの集合Ｕ、経路コストは計算されたが接続ノードが探
索されていないノードの待ち行列Ｑ、経路コストが計算
され接続ノードの探索もなされたノードの集合Ｗをすべ
て空にしておく。すべてのリンクに対してリンクコスト
を設定する。 ステップ２．出発点ノードについて、経路コストを０に
設定し、待ち行列Ｑに加える。また、出発点ノード以外
のすべてのノードを集合Ｕに加える。 ステップ３．待ち行列Ｑの先頭のノード（注目ノード）
ｐを待ち行列Ｑから取り出し集合Ｗに加える。 ステップ４．注目ノードｐの接続ノードで集合Ｕに属し
ているノードｑのすべてについて、ノードｐとノードｑ
を結ぶリンクのリンクコストとノードｐの経路コストの
和をノードｑの経路コストとし、ノードｑからノードｐ
へ向かうポインタを付け、さらにノードｐとノードｑを
結ぶリンクのうちリンクコストが小さいものから優先し
て、ノードｑを集合Ｕから除き待ち行列Ｑに加える。 ステップ５．待ち行列Ｑが空でなければ、ステップ３．
に戻る。待ち行列Ｑが空であれば、探索は終了する。こ
のとき、集合Ｗに属する各ノードのポインタをたどれば
解が得られる。

【０００６】以上が優先リンク法の概略である。すでに
経路コストが求められているノードについては、別の経
路に対する計算を新たにおこなわない。注目ノードの選
択は待ち行列Ｑの先頭から取り出すだけでよい。また、
注目ノードの経路コストと接続リンクのリンクコストの
和の計算は、集合Ｕに属している接続ノードについてだ
けでよく、その結果と経路コストとの比較もなく、経路
コストとポインタを更新することもない。したがって、
優先リンク法によればダイクストラ法にくらべて計算時
間を短くすることができる。

【０００７】

【発明が解決しようとする課題】ベクトル地図上で、指
定した地点から指定した時間で到達可能な範囲をダイク
ストラ法を用いて求める場合、次のような課題がある。 （１）ダイクストラ法では、注目ノードを選択する処理
や、注目ノードにおける接続ノードのすべてについて、
注目ノードの経路コストと接続リンクのリンクコストの
和を計算して、それを接続ノードの経路コストと比較
し、その結果によって接続ノードの経路コストとポイン
タを更新するといった処理をおこなうため、一般に計算
時間が長くなる。 （２）上記（１）に示したように、ダイクストラ法は計
算時間がかかる。リンク数が大きいほど特にその傾向は
顕著に現れる。この課題の解決法として、高速な探索方
法である優先リンク法を用いることが考えられる。しか
し優先リンク法では、出発点ノードから順次機械的に経
路コストを確定していくので、先に求めた経路コストが
優先され、解の精度の劣化が生じる。すなわち、優先リ
ンク法では、一つのノードに注目して局所的に最短路を
求めているため、計算を進めるにしたがって誤差が累積
し、その結果、かなり解の精度が低いという課題があ
る。特に接続リンクの通行時間が大きい接続ノードへの
探索では、誤差が生じた場合その値は大きくなる。

【０００８】そこで本発明の目的は、ベクトル地図にお
いて、指定した地点から指定した時間で到達可能な範囲
を高速かつ高精度に算出する方法を提供することにあ
る。

【０００９】

【課題を解決するための手段】上記従来技術の問題点を
解決するため、以下の手段を考案した。 （１）ダイクストラ法のような高精度探索方法におい
て、注目ノードを選択する処理や、接続ノードの到達時
間と親ノードの更新チェックに制約を設ける。これによ
って従来よりも、精度を保ちながら高速化することがで
きる。また、必要に応じて計算時間あるいは解の精度を
調節することも可能となる。 （２）各ノードにおいて優先リンク法のような高速探索
方法とダイクストラ法のような高精度探索方法のどちら
を適用するかを、注目ノードにおける接続リンク条件と
所定のしきい値を比較することによって判定する。この
とき、接続リンク条件として接続リンク数、全接続リン
クの平均通行時間がある。これによって、両探索方法の
組み合わせによる相乗効果がより充分に得られ、計算時
間および解の精度に関して効率的な算出が可能となる。

【００１０】ここで、本願明細書で用いる言葉を、以下
のとおり定義する。「接続ノード」とは、ベクトル地図
において、あるノードからリンクを介して接続している
ノードをいう。「注目ノード」とは、接続ノードを探索
すべきノードである。「到達時間」とは、各ノードにお
ける指定地点からの最短路上の通行時間の総和をいう。
「親ノード」とは、ノードｐから接続ノードｑを探索す
るときの、ノードｑにおけるノードｐのことである。
「計算状況」とは、各ノードにおける、ある時点での計
算過程フラグをいう。「チェックカウント」とは、各ノ
ードに対する、到達時間と親ノードの更新判定を実行す
るか否かの判定をおこなった回数をいう。「探索履歴テ
ーブル」とは、ノード番号と該ノード番号に対する到達
時間と該ノード番号に対する親ノード番号と該ノード番
号に対する計算状況と該ノード番号に対するチェックカ
ウントから構成されるテーブルをいう。「探索ノードテ
ーブル」とは、注目ノードになり得るノードのノード番
号を格納しておくためのテーブルをいう。「候補制約パ
ラメータ」とは、探索ノードテーブルに格納されている
ノード番号の注目ノードの選択範囲を決定するための割
合をいう。「更新制約パラメータ」とは、注目ノードに
おける接続ノードに対して到達時間と親ノードの更新判
定を実行するか否かを、接続ノードにおけるチェックカ
ウントによって判定するためのしきい値をいう。「切替
パラメータ」とは、注目ノードにおいて高精度探索方法
と高速探索方法のどちらを適用するかを判定するための
しきい値をいう。

【００１１】

【発明の実施の形態】以下、本発明の実施の形態を図面
に基づいて詳細に説明する。

【００１２】＜実施形態１＞本発明の第１の実施の形態
を、図１から図１０を用いて説明する。本実施形態は、
レンタカー店などにおける旅行先決定支援システムでの
使用例である。すなわち、本実施形態は、レンタカー店
において顧客が旅行先である観光地を決定する際に、道
路状況を考慮して、ある設定時間内に移動可能な観光地
を選定することを支援するシステムの例である。

【００１３】図１に本システムの画面イメージを示す。
本システムが適用される旅行先決定支援システムにおい
ては、利用者が画面を参照しながら旅行時間１０１を入
力し、旅行開始地点１０２を地図画面１０３上でマウス
クリックすると、旅行開始地点１０２から旅行時間１０
１（２２分）以内に車で行くことのできる範囲１０４が
表示される。さらに、到達可能範囲内には地図画面１０
３のように複数の観光地１０５が表示されるので、利用
者がそれらの中から一つをマウスクリックにより選択す
ると、その観光地の詳細情報１０６が表示される。

【００１４】図２を用いて本発明を適用するシステムの
構成とデータの流れの概略を述べる。本システムは、入
出力用端末装置１００と、演算装置（コンピュータ）２
００と、ハードディスク３００と、メインメモリ４００
とから構成される。入出力用端末装置１００は、入力装
置１０と、ディスプレイ１１とから構成され、ディスプ
レイ１１には、図１に示す画面が表示される。演算装置
２００は、表示処理機能１と、観光地検索処理機能２
と、到達可能範囲算出機能３とを有している。ハードデ
ィスク３００には、リンクテーブルおよびノードテーブ
ルとを含むベクトル地図データ４と、画面上に表示され
る詳細情報などが格納された観光地データ５が格納され
ている。メインメモリ４００には、探索履歴テーブル６
と、探索ノードテーブル７と、切替パラメータ８とが格
納されている。

【００１５】本発明におけるベクトル地図は、図３に示
すように○で囲まれたノード番号で表される複数のノー
ドＮと、視覚でか込まれたリンク番号で表されるノード
感を結ぶ道路を意味するリンクＬと、各リンクの通行時
分で構成されている。

【００１６】本システムは、利用者９がディスプレイ１
１に表示されている地図に対して旅行時間１０１と旅行
開始地点１０２を入力すると、旅行時間１０１内に行く
ことのできる観光地を地図上に表示するものである。こ
のためには、まず、表示処理機能１がベクトル地図デー
タ４を用いて道路網を表現するための処理を実行し、デ
ィスプレイ１１に地図画面１０３を表示する。ベクトル
地図データ４は、リンクテーブルとノードテーブルから
成る。リンクテーブルとノードテーブルの詳細は後述す
る。

【００１７】利用者９はこの地図に対して、旅行時間１
０１と旅行開始地点１０２のシミュレーション条件を入
力装置１０を介して入力する。本実施形態では、図３の
地図を使い、ノード番号３２のノードを旅行開始地点１
０２とし、旅行時間は２２分として以下の説明を行な
う。

【００１８】次に、到達可能範囲算出処理機能３は、シ
ミュレーション条件入力で入力された旅行時間１０１お
よび旅行開始地点１０２と、道路網を表すベクトル地図
データ４と、各ノードの探索履歴を記録しておく探索履
歴テーブル６と、探索されたノードを格納しておく探索
ノードテーブル７と、各ノードに対する適用探索方法を
判定するための基準となる切替パラメータ８を用いて、
旅行開始地点１０２から旅行時間１０１内に車で行くこ
とのできる範囲を求める到達可能範囲を算出する処理を
行なう。

【００１９】最後に、到達可能範囲算出処理の結果と、
到達可能範囲算出処理で求めた到達可能範囲内の観光地
を観光地データ５（例えば観光地の位置、観光地名称、
観光地案内情報から構成されている）を観光地検索処理
機能２が検索した結果を、表示処理機能１が処理して、
地図が面１０３と詳細情報１０６をディスプレイ１１に
表示する。

【００２０】図３に示した地図に対応するリンクテーブ
ルを図４に示す。リンクテーブル４０は、地図に示され
るリンク番号Ｌを表すリンク番号４１と、リンクの長さ
を表す道路長４２と、国道または市道もしくは高速道路
などの道路の種別を表す道路種別４３と、国道や市道の
名称に相当する道路番号４４と、制限速度などの通行速
度４５と、リンクを通過するに必要な時間を表す通行時
間４６で構成される。例えば、図３に示す地図におい
て、リンク番号２１２のリンクは通行時間が５分である
ので、リンクテーブル４０において通行時間４６に
「５」を設定する。これは、リンク番号２１２のリンク
の両端ノードの間を車で走行するのに５分かかるという
ことを意味する。

【００２１】図３に示す地図に対応するノードテーブル
を図５に示す。ノードテーブル５０は、地図に示される
ノード番号Ｎを表すノード番号５１と、当該ノードの地
図上の位置を表す座標５２と、当該ノードに接続される
リンクの数を表す接続リンク数５３と、接続ノード番号
５４とそれに対応する接続リンク番号５５から成る接続
情報５６で構成される。接続情報５６においては、接続
リンク番号５５に対応するリンクの通行時間が小さい順
に、接続リンク番号５５とそれに対応する接続ノード番
号５４がソーティングされている。例えば、図３に示す
地図において、ノード番号５５のノードについて、接続
ノードはノード番号５４、５３、３２の三つがある。ノ
ード番号５４の接続ノードへ到達するための接続リンク
はリンク番号２１２である。接続リンクの３本は、リン
クの通行時間４６の小さい順にソーティングし、リンク
番号２１２、２１１、２０２の順に構成する。ちなみ
に、道路網を表すベクトル地図におけるノードは、交差
点ばかりでなく、曲点や行き止まりを意味することもあ
るので、接続リンク数が「２」や「１」のノードも存在
する。

【００２２】リンクテーブル４０とノードテーブル５０
は、リンクの向きを特定しない無向リンクのベクトル地
図データを示しているが、以下に述べる発明では、リン
クの向きを特定した有向リンクのベクトル地図データも
同様に扱える。また、表示処理が行なわれる地図データ
はイメージ地図データであってもよい。なお、本実施形
態では、表示処理機能１と到達可能範囲算出処理機能３
と観光地検索処理機能２は、コンピュータ２００によっ
て実現され、ベクトル地図データ４と観光地データ５
は、ハードディスク３００に格納され、探索履歴テーブ
ル６と探索ノードテーブル７と切替パラメータ８は、メ
インメモリ４００格納されてそれぞれ実現することがで
きる。

【００２３】以下、本発明の主要な処理である到達可能
範囲算出処理について、図６の処理フローに基づいて説
明する。本実施形態では、注目ノードに対して高精度探
索方法と高速探索方法のどちらを適用するかを、切替パ
ラメータ８をしきい値として、注目ノードにおける接続
リンク数によって判定する。

【００２４】（１）初期設定処理（Ｓ１） まず、探索履歴テーブル６と探索ノードテーブル７の初
期化を行なう。探索履歴テーブル６は、図７に示すよう
に、ノード番号６１と到達時間６２と親ノード番号６３
と計算状況６４から構成される。ここで、到達時間は、
各ノードにおける旅行開始地点からの最短路上の通行時
間の総和である。親ノードとは、ノードｐとその接続ノ
ードであるノードｑを結ぶリンクが最短路を成すとき
の、ノードｑにおけるノードｐのことをいう。計算状況
は、旅行開始地点のノードを”開始ノード”、到達時間
が計算されず初期値の状態を”未計算”、到達時間が計
算されたが最短路は未確定の状態を”未確定”、最短路
が確定した状態を”確定”、最短路が確定していて到達
時間が旅行時間１０１より大きい場合は”超過”とす
る。例えば、図７において、ノード番号５３の地点へ
は、ノード番号５５の地点を経由した経路が最短であ
り、旅行開始地点から２１分の時間を要することを示
す。また、ノード番号７７の地点へは、ノード番号５３
の地点を経由した経路が最短であり、２９分の旅行時間
を要し、旅行時間１０１の２２分を超えていることを示
す。

【００２５】探索履歴テーブル６と探索ノードテーブル
７の初期化では、旅行開始地点のノードに対しては、到
達時間６２を「０」、親ノード番号６３をヌル（図では
ハイフンで表されるダミー番号）、計算状況６４を”開
始ノード”とする。ほかのすべてのノードに対しては、
到達時間６２をあらゆる到達時間より大きい値にする。
例えば、到達時間の最大値が「９９９９９」未満ならば
「９９９９９」をセットする。親ノード番号６３はヌル
に、計算状況６４は”未計算”とする。

【００２６】図８に示す探索ノードテーブル７は、高精
度探索方法および高速探索方法によって探索され、注目
ノードになり得るノードのノード番号７１を格納してお
くテーブルである。リードポインタ７２は、探索ノード
テーブル７において注目ノードを次に読み出す位置を示
す。ライトポインタ７３は、探索ノードテーブル７にお
いて探索ノードを次に書き込む位置を示す。初期化で
は、探索ノードテーブル７は、なにも格納されていない
状態にされ、リードポインタ７２とライトポインタ７３
をともに１レコード目に設定する。旅行開始地点１０２
であるノード番号３２のノードを到達可能範囲算出処理
３における最初の注目ノードとする。

【００２７】（２）切替パラメータ設定処理（Ｓ２） 適用探索方法判定Ｓ３で、注目ノードにおいて高精度探
索方法と高速探索方法のどちらを適用するかを、接続リ
ンク条件によって判定するためのしきい値である切替パ
ラメータ８の値を設定する。本実施形態では、接続リン
ク条件として接続リンク数を考える。ここで使っている
ベクトル地図データ３において、ノードテーブル上のす
べてのノード番号に対する平均接続リンク数が「３」か
ら「４」の間であるので、切替パラメータ８の値を
「３」に設定する。

【００２８】（３）適用探索方法判定（Ｓ３） 注目ノードに対して高精度探索方法と高速探索方法のど
ちらを適用するかを、切替パラメータ設定処理Ｓ２で設
定した切替パラメータ８の値を基準として、注目ノード
における接続リンク条件によって判定する。本実施形態
では接続リンク条件として接続リンク数を考える。接続
リンク数が小さければ、比較的計算時間が長い高精度な
探索方法を適用してもそれほど計算時間がかからないの
で、解の精度を高くするために、接続リンク数が切替パ
ラメータ８以下であれば高精度な探索方法を適用する。
一方、接続リンク数が大きいほど計算時間がかかるの
で、計算時間を短くするために、接続リンク数が切替パ
ラメータ８の値より大きければ高速な探索方法を適用す
る。ここでは、切替パラメータ設定処理Ｓ２において切
替パラメータ８の値は「３」に設定されているので、注
目ノードの接続リンク数が「３」以下のノードには高精
度探索方法を適用し、注目ノードの接続リンク数が
「３」より大きい、すなわち「４」以上のノードには高
速探索方法を適用する。このときの、図３に示す各ノー
ドにおける適用探索方法は図９に示すようになる。すな
わち、高精度探索方法が適用されるノードを水平に配置
した矩形で表し、高速探索方法が適用されるノードを斜
めに配置した矩形で表す。いま、注目ノードである旅行
開始地点１０２のノード番号３２のノードにおいては、
ノードテーブル５０の接続リンク数５３の欄を参照する
と、接続リンク数が「４」であるので、高速探索方法を
適用する。すなわち、高速探索処理Ｓ５を行なう。

【００２９】（４）高速探索処理（Ｓ５） 本処理の手順は、優先リンク法に似ている。

【００３０】（４−１）接続ノード探索処理 注目ノードにおける接続ノードをすべて探索したら後述
する注目ノード選択処理（４−３）へ進む。それまで
は、ノードテーブル５０を参照して、注目ノードの接続
情報を順次得ていく。探索履歴テーブル６を参照して、
接続ノードの計算状況６４が”未計算”であれば、後述
する到達時間計算処理（４−２）を行なってから接続ノ
ード探索処理（４−１）の始めに戻る。探索履歴テーブ
ル６を参照して、もし接続ノードの計算状況６４が”未
計算”でなければすぐに接続ノード探索処理（４−１）
の始めに戻り、次の接続情報を得る

【００３１】いま、ノード番号３２のノードが注目ノー
ドであるので、最初の接続ノードはノード番号５５のノ
ードで、接続リンクはリンク番号２０２のリンクである
といった接続情報が得られる。ノード番号５５のノード
の計算状況は現時点では”未計算”であるので、到達時
間計算処理（４−２）の処理を行なう。

【００３２】（４−２）到達時間計算処理 （ａ）接続ノードの到達時間を、探索履歴テーブル６か
ら得られる注目ノードの到達時間と、リンクテーブル４
０から得られる接続リンクの通行時間の和として計算
し、探索履歴テーブル６の、接続ノードのノード番号に
おける到達時間６２の項に書き込む。探索履歴テーブル
６の、接続ノードのノード番号における親ノード番号６
３の項には、注目ノードのノード番号を書き込む。も
し、接続ノードの到達時間が旅行時間１０１より大きい
ならば、探索履歴テーブル６において、この接続ノード
に対する計算状況を”超過”として、接続ノード探索処
理（４−１）に戻る。もし接続ノードの到達時間が旅行
時間１０１以下ならば次の処理を行なう。

【００３３】（ｂ）探索ノードテーブル７においてライ
トポインタ７３が指しているレコードに、その接続ノー
ドのノード番号を書き込み、ライトポインタ７３を１レ
コード進める。また、探索履歴テーブル６において、こ
の接続ノードに対する計算状況を”確定”として、接続
ノード探索処理（４−１）に戻る。いま、注目ノードの
到達時間は０（分）、リンク番号２０２の接続リンクの
通行時間は１３（分）であるので、ノード番号５５の接
続ノードの到達時間は０＋１３で１３（分）となる。探
索履歴テーブル６に対して、ノード番号５５の到達時間
６２の項にこれを書き込み、親ノード番号６３の項には
注目ノードのノード番号である３２を書き込む。接続ノ
ードの到達時間である１３（分）は、旅行時間１０１で
ある２２（分）以下であるので、探索ノードテーブル７
において、ライトポインタ７３が指している１レコード
目に接続ノードのノード番号である５５を書き込み、ラ
イトポインタ７３を１レコード進め、２レコード目を指
すようにする。また、探索履歴テーブル６において、ノ
ード番号５５のノードの計算状況を”確定”とする。残
りの接続ノードに対しても同様なことを繰り返す。

【００３４】（４−３）注目ノード選択処理 探索ノードテーブル７において、リードポインタ７２が
指しているレコードにノード番号が格納されていれば、
そのノードを次の注目ノードとし、リードポインタ７２
を１レコード進め、高速探索処理Ｓ５を終了する。も
し、注目ノード選択処理（４−３）の始めでリードポイ
ンタ７２が指しているレコードのノード番号がヌルであ
れば、ノード番号が見つかるまでリードポインタ７２を
１レコードずつ進めていく。そして見つかったところで
そのノードを次の注目ノードとし、リードポインタ７２
をさらに１レコード進め、高速探索処理Ｓ５を終了す
る。もし、リードポインタ７２がライトポインタ７３と
同じレコードを指すようになるまでリードポインタ７２
を１レコードずつ進めていってもノード番号が見つから
ない、すなわち、注目ノード選択処理（４−３）の始め
でリードポインタ７２の指すレコードからライトポイン
タ７３の指すレコードの一つ前までのすべてのノード番
号がヌルであるならば、注目ノードはヌルとして、高速
探索処理Ｓ５を終了する。

【００３５】いま、探索ノードテーブル７において、リ
ードポインタ７２は到達時間計算処理（４−２）で書き
込んだノード番号５５がある１レコード目を指してお
り、このノードを次の注目ノードとする。リードポイン
タ７２を１レコード進め、２レコード目を指すようにす
る。

【００３６】（５）終了判定（Ｓ６） 高精度探索処理Ｓ４あるいは高速探索処理Ｓ５におい
て、次の注目ノードが選択できた場合は、それを新たな
注目ノードとして、適用探索方法判定Ｓ３に戻る。注目
ノードがヌルの場合は、到達可能範囲算出処理３を終了
する。いま、（４）の高速探索処理Ｓ５においてノード
番号５５のノードが次の注目ノードに選ばれたので、ノ
ード番号５５のノードを新たな注目ノードとして、再び
適用探索方法判定Ｓ３を行なう。 （６）適用探索方法判定（Ｓ３） いま、注目ノードであるノード番号５５のノードにおい
ては、ノードテーブル５０の接続リンク数５３の項か
ら、接続リンク数が３であるので、高精度探索方法を適
用する。すなわち、高精度探索処理Ｓ４を行なう。

【００３７】（７）高精度探索処理（Ｓ４） 本処理の手順は、ダイクストラ法に近い。

【００３８】（７−１）接続ノード探索処理 注目ノードにおける接続ノードをすべて探索したら注目
ノード選択処理（７−３）へ進む。それまでは、ノード
テーブル５０を参照して、注目ノードの接続情報を順次
得ていく。探索履歴テーブル６を参照して接続ノードの
計算状況６４が”開始ノード”あるいは”確定”であれ
ばすぐに接続ノード探索処理（７−１）の始めに戻り、
次の接続情報を得る。探索履歴テーブル６を参照して接
続ノードの計算状況６４が”開始ノード”あるいは”確
定”でなければ到達時間計算処理（７−２）を行なって
から接続ノード探索処理（７−１）に戻る。いま、ノー
ド番号５５のノードが注目ノードであるので、最初の接
続ノードはノード番号５４のノードで、接続リンクは、
リンク番号２１２のリンクであるといった接続情報が得
られる。ノード番号５４のノードの計算状況は現時点で
は”未計算”であるので、到達時間計算処理（７−２）
を行なう。

【００３９】（７−２）到達時間計算処理 （ａ）接続ノードの到達時間を、探索履歴テーブル６か
ら得られる注目ノードの到達時間と、リンクテーブル４
０から得られる接続リンクの通行時間の和として計算す
る。この値が現時点の探索履歴テーブル６から得られる
接続ノードの到達時間以上であれば接続ノード探索処理
（７−１）に戻る。この値が現時点の探索履歴テーブル
６から得られる接続ノードの到達時間以上でなければ次
の処理を行なう。

【００４０】（ｂ）探索履歴テーブル６の、接続ノード
のノード番号における到達時間６２の項に、この新たに
計算した到達時間を書き込み、探索履歴テーブル６の、
接続ノードのノード番号における親ノード番号６３の項
には、注目ノードのノード番号を書き込む。もし、接続
ノードの新たな到達時間が旅行時間１０１より大きいな
らば、探索履歴テーブル６において、この接続ノードに
対する計算状況を”超過”として、接続ノード探索処理
（７−１）に戻る。もし、接続ノードの新たな到達時間
が旅行時間１０１以下ならば次の処理を行なう。

【００４１】（ｃ）もし、探索履歴テーブル６を参照し
て接続ノードの計算状況が”未確定”であれば接続ノー
ド探索処理（７−１）に戻る。探索履歴テーブル６を参
照して接続ノードの計算状況が”未確定”でなければ次
の処理を行なう。

【００４２】（ｄ）探索ノードテーブル７においてライ
トポインタ７３が指しているレコードに、その接続ノー
ドのノード番号を書き込み、ライトポインタ７３を１レ
コード進める。また、探索履歴テーブル６において、こ
の接続ノードに対する計算状況を”未確定”として、接
続ノード探索処理（７−１）に戻る。いま、注目ノード
の到達時間は１３（分）、リンク番号２１２の接続リン
クの通行時間は５（分）であるので、ノード番号５４の
接続ノードの到達時間は１３＋５で１８（分）と計算さ
れる。この値は現時点の探索履歴テーブル６から得られ
るノード番号５４の接続ノードの到達時間である「９９
９９９」（分）より小さいので、探索履歴テーブル６に
対して、ノード番号５４の到達時間６２の項にこの値を
書き込み、親ノード番号６３の項には注目ノードのノー
ド番号である「５５」を書き込む。接続ノードの新たな
到達時間である１８（分）は、旅行時間１０１である２
２（分）以下であり、かつ、接続ノードの計算状況６４
は現時点では”未計算”であるので、ノード番号３２の
ノードの接続ノード番号の四つだけが前記（４）高速検
索処理により現時点で格納されている探索ノードテーブ
ル７において、ライトポインタ７３が指している５レコ
ード目に接続ノードのノード番号である５４を書き込
み、ライトポインタ７３を１レコード進め、６レコード
目を指すようにする。また、探索履歴テーブル６におい
て、ノード番号５４のノードの計算状況を”未確定”と
する。残りの接続ノードに対しても同様なことを繰り返
す。

【００４３】（７−３）注目ノード選択処理 探索ノードテーブル７において、リードポインタ７２が
指しているレコードからライトポインタ７３の指してい
るレコードの直前のレコードまでに格納されているノー
ド番号のノードのうち、その到達時間が最小のノードの
一つを次の注目ノードとする。そして、探索ノードテー
ブル７において、この新たな注目ノードのノード番号を
ヌルとし、探索履歴テーブル６において、このノードの
計算状況を”確定”として、高精度探索処理Ｓ４を終了
する。もし、リードポインタ７２の指すレコードからラ
イトポインタ７３の指すレコードの一つ前までのすべて
のノード番号がヌルであるならば、注目ノードはヌルと
して、高精度探索処理Ｓ４を終了する。探索ノードテー
ブル７の実現には、例えば、基本的なデータ構造である
リストを使う。いま、注目ノードであるノード番号５５
のノードの接続ノードをすべて探索した結果、探索ノー
ドテーブル７上に格納されているノード番号は六つあ
り、１レコード目から順番に、５５、３３、３１、３
０、５４、５３となっている。

【００４４】リードポインタ７２は、２レコード目を指
しており、探索履歴テーブル６において、探索ノードテ
ーブル７の２レコード目以降に格納されているノード番
号に対応する到達時間のうち、ノード番号５４に対応す
る到達時間の１８（分）が最小であるので、ノード番号
５４のノードを次の注目ノードとする。そして探索ノー
ドテーブル７において、ノード番号５４が格納されてい
る５レコード目のノード番号をヌルとし、探索履歴テー
ブル６において、ノード番号５４に対応する計算状況６
４を”確定”とする。

【００４５】（８）終了判定（Ｓ６） いま、（７）の高精度探索処理Ｓ４においてノード番号
５４のノードが次の注目ノードに選ばれたので、ノード
番号５４のノードを新たな注目ノードとして、適用探索
方法判定Ｓ３を行なう。以下、注目ノードがヌルになる
まで同様に繰り返す。

【００４６】図３に示す地図に対して本発明における到
達可能範囲算出処理を最後まで行なった結果を図１０に
示す。図において、旅行時間１０１以内に到達可能なノ
ードは一つの頂点が上にある三角として、到達不可能な
ノードは一つの頂点が下にある三角として示される。図
７に示す探索履歴テーブル６、図８に示す探索ノードテ
ーブル７の内容は、ノード番号５３のノードが注目ノー
ドのときに、高速探索処理Ｓ５において注目ノード選択
処理に移る手前の状態に対応している。到達可能範囲算
出処理が終了した時点で、探索履歴テーブル６の計算状
況６４が”開始ノード”あるいは”確定”であるノード
が、旅行時間１０１内に到達可能なノードである。ま
た、各ノードの親ノードを旅行開始地点のノードまでた
どっていくことによって、旅行開始地点のノードからそ
のノードへの最短路を求めることができる。

【００４７】上述の実施の形態においては、各リンクの
通行時間４６は始めから与えられているものとしたが、
制限通行速度や道幅から決定してもよいし、刻々と変わ
る道路の混雑状況や平均車両速度といった道路情報から
リアルタイムで設定するようにしてもよい。

【００４８】また、注目ノードに対する適用探索方法の
判定に使われる接続リンク条件として、注目ノードにお
ける接続リンク数を考えたが、注目ノードにおける全接
続リンクの平均通行時間を接続リンク条件としてもよ
い。このときは、高精度探索方法と高速探索方法のどち
らを適用するかを次のように判定する。全接続リンクの
平均通行時間が大きければ、誤差が生じたときにその値
が大きくなってしまうので、全接続リンクの平均通行時
間が切替パラメータ８の値より大きければ高精度探索方
法を適用する。一方、全接続リンクの平均通行時間が小
さければ、誤差が生じてもその値は小さいので、計算時
間を短くするために、全接続リンクの平均通行時間が切
替パラメータ８の値以下であれば高速探索方法を適用す
る。

【００４９】さらに、適用探索方法判定Ｓ３において注
目ノードに対する適用探索方法の判定に接続リンク条件
を使う代わりに、注目ノードにおける到達時間を使うよ
うにしてもよい。このときは、切替パラメータ設定処理
Ｓ２で、旅行時間１０１以内の到達時間として切替パラ
メータ８の値を設定する。そして、例えば、適用探索方
法判定Ｓ３では、注目ノードの到達時間が切替パラメー
タ８の値以下であれば高精度探索方法を適用し、切替パ
ラメータ８の値より大きければ高速探索方法を適用す
る。このようにする理由は次のとおりである。旅行開始
地点１０２付近に高精度探索方法を用いることによっ
て、周辺部に波及する精度誤差はなくなる。このとき、
高精度探索方法によって探索されるノードの数は比較的
少ないので、計算時間はそれほど長くならない。逆に、
旅行開始地点１０２付近にくらべてノードの数が多くな
る周辺部には、計算時間が短い高速探索方法を用いるこ
とによって、探索に要する時間は抑えられる。そして、
ここで生じる精度誤差はほかに大きく影響しない。した
がって、計算時間を比較的増加させずに精度の向上が可
能になり、精度を比較的劣化させずに計算時間の短縮が
可能になる。

【００５０】さらにまた、到達可能範囲算出処理に対す
る制限計算時間を考慮して高精度探索方法から高速探索
方法への切り替えを行なうようにしてもよい。このとき
の切替パラメータ８の値は制限計算時間以内の計算時間
として設定し、適用探索方法判定Ｓ３では、到達可能範
囲算出処理におけるその時点までの経過計算時間が切替
パラメータ８の値以下であれば高精度探索方法を適用
し、切替パラメータ８の値より大きければ高速探索方法
を適用する。

【００５１】本実施形態の効果として、ダイクストラ法
や優先リンク法を単独で用いるのではなく、高精度探索
方法と高速探索方法のそれぞれの特性を考慮して両探索
方法を使い分けることによって、相乗効果が得られ、計
算時間および解の精度の両方に関して効率的な所定時間
内到達可能範囲の算出が可能となる。また、切替パラメ
ータ８の値によって計算時間や解の精度が変化するの
で、必要に応じて計算時間あるいは解の精度を調節する
ことも可能である。したがって、本システムは旅行時間
内に移動可能な観光地を高速高精度に算出でき、その利
用者は速く正確に観光地を選定することができる。

【００５２】＜実施形態２＞本発明の第２の実施の形態
を、第１の実施の形態における図面とともに、新たに図
１１から図１５を用いて説明する。本実施形態でも前実
施形態と同様なの旅行先決定支援システムを考える。た
だし、図２に示す到達可能範囲算出処理の処理フローと
して、図６に示すフローに代わり図１１に示すフローを
用いる。また、図２に示す切替パラメータ８の代わりに
制約パラメータ８０を用いる。すなわち、高精度探索方
法における到達時間と親ノードの更新判定の実行や注目
ノードの候補に制約を与える制約パラメータ８０を、注
目ノードにおける到達時間によって段階的に変化させな
がら、旅行時間１０１内に到達可能なノードを求める。

【００５３】本実施形態では、図１２に示す地図を使
い、ノード番号１のノードを旅行開始地点１０２とし、
旅行時間を２２分とする。図１２に示す地図に対応する
リンクテーブルは、図４のリンクテーブル４０と同様
に、各リンク番号について、道路長、道路種別、道路番
号、通行速度、通行時間で構成されているものとする。
図１２に示す地図に対応するノードテーブルは、図５に
示すノードテーブル５０と同様に、各ノード番号につい
て、座標、接続リンク数、接続ノード番号とそれに対応
する接続リンク番号から成る接続情報で構成され、接続
情報においては、接続リンク番号に対応するリンクの通
行時間が小さい順に、接続リンク番号とそれに対応する
接続ノード番号がソーティングされているものとする。

【００５４】以下、図１１に示す到達可能範囲算出処理
フローに基づいて、この実施の態様を説明する。

【００５５】（１）初期設定処理（Ｓ１１） 探索履歴テーブル６０と探索ノードテーブル７の初期化
を行なう。探索履歴テーブル６０は、図１３に示すよう
に、ノード番号６１、到達時間６２、親ノード番号６
３、計算状況６４、チェックカウント６５で構成され
る。チェックカウント６５以外の項目は図７に示す探索
履歴テーブル６の項目と同じ意味をもつ。チェックカウ
ント６５は、各ノードに対して、到達時間と親ノードの
更新判定を実行するか否かの判定を行なった回数であ
り、これが制約パラメータ８０の値と比較され、更新判
定を実行するか否かが判定される。例えば、図１３にお
いて、ノード番号１２のノードに対する到達時間と親ノ
ードの更新判定の実行の判定は、その時点で３回おこな
われていることになる。探索履歴テーブル６０の初期化
では、旅行開始地点１０２のノード１に対しては、到達
時間６２を「０」、親ノード番号６３をヌル、計算状況
６４を”開始ノード”、チェックカウント６５を「０」
とする。ほかの全てのノードに対しては、到達時間６２
をあらゆる到達時間より大きい値にする。例えば、到達
時間の最大値が「９９９９９」未満ならば「９９９９
９」をセットする。親ノード番号６３はヌルに、計算状
況６４は”未計算”に、チェックカウント６５は「０」
にする。

【００５６】探索ノードテーブル７は、図１４に示すよ
うな、注目ノードになり得るノードのノード番号７１を
格納しておくためのテーブルである。探索ノードテーブ
ル７の初期化ではなにも格納されていない状態にする。
旅行開始地点１０２を最初の注目ノードとする。

【００５７】（２）制約パラメータ設定処理（Ｓ１２） 注目ノードにおける接続ノードに対して到達時間と親ノ
ードの更新判定を実行するか否かを、接続ノードにおけ
るチェックカウント６５によって判定するためのしきい
値となる制約パラメータである更新制約パラメータ８１
と、探索ノードテーブル７に格納されているノード番号
のノードのうち、注目ノードの候補とする割合を示す制
約パラメータである候補制約パラメータ８２を設定す
る。この実施形態では、注目ノードにおける到達時間に
よって制約パラメータ８０を段階的に変化させる。接続
ノードにおける到達時間と親ノードの更新判定の実行に
ついては、接続ノードにおけるチェックカウント６５が
更新制約パラメータ８１以下であれば更新判定を実行
し、更新制約パラメータ８１より大きければ更新判定を
実行しない。また、注目ノードの候補の決定に関して
は、その時点での探索ノードテーブル７上のノード番号
に対して、最も早くに書き込まれたノード番号のノード
と、残りのノード番号のノードのうちその個数に候補制
約パラメータ８２をかけた個数だけのノードを注目ノー
ドの候補とする。

【００５８】以上のようにするとき、更新制約パラメー
タ８１も候補制約パラメータ８２もともに、注目ノード
における到達時間が大きいほど、小さく設定する。この
理由は次のとおりである。旅行開始地点１０２付近で
は、探索ノード数は比較的少なく、比較的計算時間が長
い高精度な探索を行なってもそれほど計算時間はかから
ないので、周辺部に波及する精度誤差をなくすために、
解の精度を高くするような探索を行ない、周辺部では、
精度誤差を生みやすい高速な探索を行なってもここで生
じた精度誤差はほかに大きく影響しないので、探索ノー
ド数が比較的多く、比較的長い探索時間を抑えるため
に、計算時間を短くするような探索を行なうことによっ
て、計算時間を比較的増加させずに精度の向上が可能に
なり、精度を比較的劣化させずに計算時間の短縮が可能
になる。

【００５９】上記の更新判定の実行についての記述によ
って、更新制約パラメータ８１は「１」から最大接続リ
ンク数の間で設定する。最大接続リンク数とはベクトル
地図データ４におけるすべてのノードの接続リンク数に
対する最大値のことであり、本実施形態では「４」とす
る。また、上記の注目ノードの候補の決定に関する記述
によって、候補制約パラメータ８２は「０」から「１」
の間で設定する。なお、本実施形態における探索方法
は、更新判定の実行に関しては、更新制約パラメータ８
１が最大接続リンク数のとき高精度探索方法に相当し、
「１」のときは高速探索方法に相当する。注目ノードの
候補の決定に関しては、候補制約パラメータ８２が
「１」のとき高精度探索方法に相当し、「０」のときは
高速探索方法に相当する。

【００６０】ここでは、注目ノードにおける到達時間が
０（分）に近いときは高精度探索方法に相当する探索方
法を用い、旅行時間１０１に近いときは高速探索方法に
相当する探索方法を用い、その中間では高精度探索方法
と高速探索方法の中間的な探索方法を用いるように、注
目ノードにおける到達時間がとり得る範囲を３段階にほ
ぼ等分して、それぞれに対して更新制約パラメータ８１
と候補制約パラメータ８２を設定する。なお、今後の説
明からわかることであるが、到達時間が０（分）以上旅
行時間１０１以下のノードだけが注目ノードになり得
る。すなわち、注目ノードにおける到達時間がとり得る
範囲は０（分）以上旅行時間１０１以下である。旅行時
間１０１は２２（分）であるので、更新制約パラメータ
８１と候補制約パラメータ８２を、 （ａ）注目ノードにおける到達時間が０（分）以上８
（分）未満であれば、更新制約パラメータ８１を「４」
に設定し、候補制約パラメータ８２を「１」に設定す
る。 （ｂ）注目ノードにおける到達時間が８（分）以上１６
（分）未満であれば、更新制約パラメータ８１を「２」
に設定し、候補制約パラメータ８２を「０．７」に設定
する。 （ｃ）注目ノードにおける到達時間が１６（分）以上２
２（分）以下であれば、更新制約パラメータ８１を
「１」に設定し、候補制約パラメータ８２を「０」に設
定する。 いま、注目ノードである旅行開始地点の到達時間は０
（分）であるので、更新制約パラメータ８１を「４」
に、候補制約パラメータ８２を「１」に設定する。

【００６１】（３）制約探索処理（Ｓ１３） 制約探索処理Ｓ１３は、図６に示した高精度探索処理Ｓ
４において、制約パラメータ設定処理Ｓ１２で設定した
更新制約パラメータ８１と探索履歴テーブル６０におけ
るチェックカウント６５を用いた、到達時間と親ノード
の更新判定の実行判定を行なうことによって、到達時間
計算や更新判定の実行に制約を与え、また、制約パラメ
ータ設定処理Ｓ１２で設定した候補制約パラメータ８２
を用いた注目ノードの候補決定処理を設けることによっ
て、注目ノードの候補に制約を与えた探索処理である。
制約探索処理Ｓ１３の詳細を図１５に示す処理フローに
基づいて説明する。

【００６２】（３−１）接続ノード探索終了判定処理
（Ｓ２１） 注目ノードにおける接続ノードをすべて探索し終えたら
注目ノード候補決定処理（３−９）へ進む。そうでなけ
れば接続ノード探索処理（３−２）を行なう。いま、注
目ノードである旅行開始地点のノード番号１のノードに
おいて、接続ノードは全部で四つあるが、まだ一つも探
索されていない。したがって接続ノード探索処理（３−
２）を行なう。

【００６３】（３−２）接続ノード探索処理（Ｓ２２） ノードテーブルを参照して、注目ノードにおける次の接
続情報を得て計算状況判定処理（３−３）へ進む。い
ま、ノード番号１のノードが注目ノードである。最初の
接続ノードはノード番号２のノードであり、接続リンク
はリンク番号１のリンクである。

【００６４】（３−３）計算状況判定処理（Ｓ２３） 探索履歴テーブル６０を参照して、接続ノードの計算状
況６４が、”開始ノード”あるいは”確定”であれば接
続ノード探索終了判定処理（３−１）に戻る。接続ノー
ドの計算状況６４が、”開始ノード”あるいは”確定”
でなければチェックカウントインクリメント処理（３−
４）の処理を行なう。いま、ノード番号２のノードの計
算状況は現時点では”未計算”であるので、チェックカ
ウントインクリメント処理（３−４）を行なう。

【００６５】（３−４）チェックカウントインクリメン
ト処理（Ｓ２４） 探索履歴テーブル６０において、接続ノードのノード番
号に対応するチェックカウント６５の項の値に「１」を
たし、その結果を上書きする、すなわち、接続ノードの
チェックカウント６５をインクリメントする。次いで、
更新判定の実行判定処理（３−５）へ進む。いま、現時
点では「０」であるノード番号２のノードのチェックカ
ウントを「１」とする。

【００６６】（３−５）更新判定の実行判定処理（Ｓ２
５） 接続ノードのチェックカウント６５が、更新制約パラメ
ータ８１の値より大きければ接続ノード探索終了判定処
理（３−１）に戻り、更新制約パラメータ８１の値以下
であれば到達時間計算処理（３−６）を行なう。いま、
ノード番号２のノードのチェックカウントは「１」であ
り、更新制約パラメータ８１の値は「４」であるので、
接続ノードのチェックカウントが更新制約パラメータ８
１の値以下である。したがって到達時間計算処理（３−
６）を行なう。

【００６７】（３−６）到達時間計算処理（Ｓ２６） 接続ノードの到達時間を、探索履歴テーブル６０から得
られる注目ノードの到達時間と、リンクテーブルから得
られる接続リンクの通行時間の和として計算する。その
後、更新判定処理（３−７）へ進む。いま、注目ノード
の到達時間は０（分）、リンク番号１のリンクの通行時
間は４（分）であるので、ノード番号２のノードの到達
時間は０＋４で４（分）と計算される。

【００６８】（３−７）更新判定処理（Ｓ２７） 到達時間計算処理（３−６）で計算した到達時間が、現
時点の探索履歴テーブル６０から得られる接続ノードの
到達時間以上であれば接続ノード探索終了判定処理（３
−１）に戻り、到達時間計算処理（３−６）で計算した
到達時間が、現時点の探索履歴テーブル６０から得られ
る接続ノードの到達時間以上でなければ到達時間と親ノ
ードの更新処理（３−８）を行なう。いま、到達時間計
算処理（３−６）で求めた到達時間である４（分）は、
現時点の探索履歴テーブル６０から得られるノード番号
２のノードの到達時間である「９９９９９」（分）より
小さいので、到達時間と親ノードの更新処理（３−８）
を行なう。

【００６９】（３−８）到達時間と親ノードの更新処理
（Ｓ２８） （ａ）探索履歴テーブル６０の、接続ノードのノード番
号における到達時間６２の項に、到達時間計算処理（３
−６）で計算した到達時間を上書きし、探索履歴テーブ
ル６０の、接続ノードのノード番号における親ノード番
号６３の項には、注目ノードのノード番号を上書きす
る。もし、接続ノードの新たな到達時間が旅行時間１０
１より大きいならば、探索履歴テーブル６０において、
この接続ノードに対する計算状況を”超過”として、接
続ノード探索終了判定処理（３−１）に戻る。もし接続
ノードの新たな到達時間が旅行時間１０１以下ならば次
の処理を行なう。

【００７０】（ｂ）探索履歴テーブル６０を参照しても
し接続ノードの計算状況６４が”未確定”であれば接続
ノード探索終了判定処理（３−１）に戻る。接続ノード
の計算状況６４が”未確定”でなければ次の処理を行な
う。

【００７１】（ｃ）探索ノードテーブル７において、現
時点でテーブル上に存在するノード番号のうちで最後に
書き込まれたものが格納されているレコードの次のレコ
ードに、その接続ノードのノード番号を書き込む。ま
た、探索履歴テーブル６０において、この接続ノードに
対する計算状況を”未確定”として、接続ノード探索終
了判定処理（３−１）に戻る。いま、探索履歴テーブル
６０に対して、ノード番号２の到達時間６２の項に到達
時間計算処理（３−６）で求めた到達時間である４
（分）を上書きし、親ノード番号６３の項には注目ノー
ドのノード番号である１を上書きする。接続ノードの新
たな到達時間である４（分）は、旅行時間１０１である
２２（分）以下であり、かつ、接続ノードの計算状況は
現時点では”未計算”であるので、まだなにも格納され
ていない探索ノードテーブル７において、１レコード目
に接続ノードのノード番号である２を書き込む。また、
探索履歴テーブル６０において、ノード番号２のノード
の計算状況を”未確定”とする。

【００７２】（３−９）注目ノード候補決定処理（Ｓ２
９） 現時点での探索ノードテーブル７上のノード番号に対し
て、最も早くに探索ノードテーブル７に書き込まれたノ
ード番号のノードと、残りのノード番号のノードのうち
その個数に候補制約パラメータ８２の値をかけた個数だ
けのノードを注目ノードの候補とする。その後、注目ノ
ード選択処理（３−１０）へ進む。もし探索ノードテー
ブル７上にノード番号が存在しなければ、注目ノードの
候補はないものとして、注目ノード選択処理（３−１
０）へ進む。ここでは、現時点で探索ノードテーブル７
上に存在するノード番号に対して、１レコード目に格納
されている最も早くに書き込まれたノード番号のノード
と、２レコード目からは順に候補制約パラメータ８２の
値の割合による個数のノードを注目ノードの候補とす
る。もし探索ノードテーブル７上にノード番号が存在し
なければ、注目ノードの候補はないものとする。

【００７３】すなわち、現時点で探索ノードテーブル７
上に存在するノード番号の個数をｘ（≧１）、候補制約
パラメータ８２の値をαとしたとき、注目ノードの候補
とするノードのノード番号の、探索ノードテーブル７に
おける１レコード目からの個数ｙを下記の（１）式によ
って求める。

【００７４】ｙ＝［（ｘ−１）×α］＋１……（１） ただし［ｚ］はｚを超えない最大の整数である。

【００７５】したがって、探索ノードテーブル７におい
て、１レコード目からｙレコード目までに格納されてい
るノード番号のノードが注目ノードの候補となる。もし
ｘ＝０のときはｙ＝０とする。

【００７６】いま、注目ノードであるノード番号１のノ
ードの接続ノードをすべて探索した結果、探索ノードテ
ーブル７上に格納されているノード番号は四つあり、１
レコード目から順番に、２、３、４、５となっている。
したがって、前記（１）式を用いてｙを求めると次のよ
うになる。ｘ＝４であり、α＝１であるので、

【００７７】 ｙ＝［（４−１）×１］＋１＝［３］＋１＝３＋１＝４

【００７８】すなわち、探索ノードテーブル７におい
て、１レコード目から４レコード目までのノード番号の
ノードを注目ノードの候補とする。結局、探索ノードテ
ーブル７上にあるノード番号のノードのすべてが注目ノ
ードの候補になる。候補制約パラメータ８２の値が
「１」のときは、探索ノードテーブル７上のノード番号
の個数にかかわらずこのようになるので、注目ノードの
候補とするノードの個数を前記（１）式で計算しなくて
もよい。

【００７９】（３−１０）注目ノード選択処理（Ｓ３
０） 注目ノード候補決定処理（３−９）で決定した注目ノー
ドの候補のうち、探索履歴テーブル６０を参照して、そ
の到達時間が最小のノードの一つを次の注目ノードとす
る。そして探索ノードテーブル７において、このノード
のノード番号を取り除き、それが格納されていたレコー
ドの次以降の内容を１レコードずつ前につめる。さらに
探索履歴テーブル６０において、このノードの計算状況
を”確定”として、制約探索処理Ｓ１３を終了する。も
し注目ノードの候補がないならば、注目ノードはヌルと
して、制約探索処理Ｓ１３を終了する。探索ノードテー
ブル７の実現には、例えば、基本的なデータ構造である
リストを使う。

【００８０】いま、注目ノード候補決定処理（３−９）
で注目ノードの候補として決定したノードのノード番号
２、３、４、５のそれぞれに対応する到達時間のうち、
ノード番号２に対応する到達時間の４（分）が最小であ
るので、ノード番号２のノードを次の注目ノードとす
る。そして、探索ノードテーブル７において、ノード番
号２を１レコード目から取り除き、２レコード目以降の
内容を１レコードずつ前につめ、１レコード目から順番
に、３、４、５の三つが格納されているようにする。さ
らに探索履歴テーブル６０において、ノード番号２に対
応する計算状況を”確定”とする。

【００８１】（４）終了判定処理（Ｓ１４） 制約探索処理Ｓ１３において、次の注目ノードが選択で
きた場合は、それを新たな注目ノードとして、制約パラ
メータ設定処理Ｓ１２に戻る。注目ノードがヌルの場合
は、到達可能範囲算出処理を終了する。いま、（３）の
制約探索処理Ｓ１３においてノード番号２のノードが次
の注目ノードに選ばれたので、ノード番号２のノードを
新たな注目ノードとして、再び制約パラメータ設定処理
Ｓ１２を行なう。以下の（５）から（１３）の処理で
は、接続ノードとしてのノード番号５のノードにおける
更新制約パラメータ８１の効果を把握しやすいように、
ノード番号５のノードが関係することだけを説明する。
説明は省略するが、ほかのノードに関しても同様のこと
を行なう。なお現時点で、ノード番号５のノードは１回
探索されており、到達時間は１５（分）、親ノード番号
は「１」、計算状況は”未確定”、チェックカウント６
５の内容は「１」である。

【００８２】（５）制約パラメータ設定処理（Ｓ１２） 注目ノードであるノード番号２のノードにおける到達時
間は４（分）であるので、更新制約パラメータ８１の値
を「４」に、候補制約パラメータ８２の値を「１」に設
定する。

【００８３】（６）制約探索処理（Ｓ１３） ノード番号２のノードが注目ノードである。その接続情
報として、接続リンク番号に対応するリンクの通行時間
が小さい順に、接続リンク番号とそれに対応する接続ノ
ード番号が得られる。したがって接続ノードはノード番
号がそれぞれ６、１、５、７のノードの順に探索され
る。ここでは接続ノードがノード番号５のノードのとき
だけについて説明する。このときの接続リンクはリンク
番号６のリンクである。ノード番号５のノードの計算状
況６４は”未確定”であるので、チェックカウント６５
をインクリメントして「２」とする。このチェックカウ
ントが更新制約パラメータ８１の値である「４」以下で
あるので、ノード番号５のノードの到達時間が、注目ノ
ードの到達時間である４（分）とリンク番号６のリンク
の通行時間である１０（分）の和として１４（分）と計
算される。この到達時間は現時点の探索履歴テーブル６
０から得られるノード番号５のノードの到達時間である
１５（分）より小さいので、探索履歴テーブル６０に対
して、ノード番号５の到達時間６２の項にこの到達時間
を上書きし、親ノード番号６３の項には注目ノードのノ
ード番号である「２」を上書きする。接続ノードの新た
な到達時間である１４（分）は、旅行時間１０１である
２２（分）以下であり、かつ、接続ノードの計算状況６
４は”未確定”であるので、探索ノードテーブル７への
書き込みも、計算状況の更新もおこなわずに、このまま
次の処理へ進む。

【００８４】注目ノードであるノード番号２のノードの
接続ノードをすべて探索した結果、探索ノードテーブル
７上に格納されているノード番号は五つあり、１レコー
ド目から順番に、３、４、５、６、７となっている。候
補制約パラメータ８２の値は「１」であるので、注目ノ
ード候補決定処理（３−９）と同様に、これらのノード
番号のノードのすべてが注目ノードの候補になる。これ
らのノード番号に対応する到達時間のうち、ノード番号
３に対応する到達時間とノード番号６に対応する到達時
間がともに７（分）で最小であるが、ここでは、最小の
到達時間をもつ候補のノードが複数存在する場合には、
そのなかで最も早くに探索ノードテーブル７に書き込ま
れたノード番号のノードを次の注目ノードとする。した
がって、ノード番号３のノードを次の注目ノードとす
る。そして探索ノードテーブル７において、ノード番号
３を１レコード目から取り除き、２レコード目以降の内
容を１レコードずつ前につめ、１レコード目から順番
に、４、５、６、７の四つが格納されているようにす
る。さらに、探索履歴テーブル６０において、ノード番
号３に対応する計算状況を”確定”とする。

【００８５】（７）終了判定処理（Ｓ１４） （６）の制約探索処理（Ｓ１３）においてノード番号３
のノードが次の注目ノードに選ばれたので、ノード番号
３のノードを新たな注目ノードとして、制約パラメータ
設定処理Ｓ１２を行なう。

【００８６】（８）制約パラメータ設定処理（Ｓ１２） 注目ノードであるノード番号３のノードにおける到達時
間は７（分）であるので、更新制約パラメータ８１の値
を「４」に、候補制約パラメータ８２の値を「１」に設
定する。

【００８７】（９）制約探索処理（Ｓ１３） ノード番号３のノードが注目ノードである。ここでは接
続ノードがノード番号５のノードのときだけについて説
明する。このときの接続リンクはリンク番号８のリンク
である。ノード番号５のノードの計算状況６４は”未確
定”であるので、チェックカウント６５をインクリメン
トして「３」とする。このチェックカウントが更新制約
パラメータ８１の値である「４」以下であるので、ノー
ド番号５のノードの到達時間が、注目ノードの到達時間
である７（分）とリンク番号８のリンクの通行時間であ
る６（分）の和として１３（分）と計算される。この到
達時間は現時点の探索履歴テーブル６０から得られるノ
ード番号５のノードの到達時間である１４（分）より小
さいので、到達時間６２と親ノード６３を再び更新す
る。候補制約パラメータ８２の値は「１」であるので、
接続ノードをすべて探索した後の探索ノードテーブル７
上にあるノード番号のノードのすべてが注目ノードの候
補になる。これらのノード番号に対応する到達時間のう
ち、ノード番号６に対応する到達時間の７（分）が最小
であるので、ノード番号６のノードを次の注目ノードと
する。

【００８８】（１０）終了判定処理（Ｓ１４） ノード番号６のノードを新たな注目ノードとして、制約
パラメータ設定処理Ｓ１２を行なう。

【００８９】（１１）制約パラメータ設定処理（Ｓ１
２） 注目ノードであるノード番号６のノードにおける到達時
間は７（分）であるので、更新制約パラメータ８１の値
を「４」に、候補制約パラメータ８２の値を「１」に設
定する。

【００９０】（１２）制約探索処理（Ｓ１３） ノード番号６のノードが注目ノードである。ここでは接
続ノードがノード番号５のノードのときだけについて説
明する。このときの接続リンクはリンク番号１０のリン
クである。ノード番号５のノードの計算状況６４は”未
確定”であるので、チェックカウント６５をインクリメ
ントして「４」とする。このチェックカウント６５が更
新制約パラメータ８１の値である「４」以下であるの
で、ノード番号５のノードの到達時間が、注目ノードの
到達時間である７（分）とリンク番号１０のリンクの通
行時間である５（分）の和として１２（分）と計算され
る。この到達時間は現時点の探索履歴テーブル６０から
得られるノード番号５のノードの到達時間である１３
（分）より小さいので、到達時間６２と親ノード６３を
更新する。候補制約パラメータ８２の値は「１」である
ので、接続ノードをすべて探索した後の探索ノードテー
ブル７上にあるノード番号のノードのすべてが注目ノー
ドの候補になる。これらのノード番号に対応する到達時
間のうち、ノード番号４に対応する到達時間の８（分）
が最小であるので、ノード番号４のノードを次の注目ノ
ードとする。

【００９１】（１３）終了判定処理（Ｓ１４） ノード番号４のノードを新たな注目ノードとして、制約
パラメータ設定処理Ｓ１２を行なう。以上、ノード番号
５のノードにおいて、４回にわたる到達時間の更新によ
り、旅行開始地点からの最小の到達時間を正確に計算す
ることができる。すなわち、到達可能範囲算出処理にお
ける解の精度を高くなることがわかる。

【００９２】以下、処理（１４）から処理（２２）で
は、接続ノードとしてのノード番号１２のノードにおけ
る更新制約パラメータ８１の効果を把握しやすいよう
に、ノード番号１２のノードが関係することだけを説明
する。

【００９３】（１４）制約パラメータ設定処理（Ｓ１
２） 注目ノードであるノード番号４のノードにおける到達時
間は８（分）であるので、更新制約パラメータ８１の値
を「２」に、候補制約パラメータ８２の値を「０．７」
に設定する。

【００９４】（１５）制約探索処理（Ｓ１３） ノード番号４のノードが注目ノードである。その接続情
報として、接続リンク番号に対応するリンクの通行時間
が小さい順に、接続リンク番号とそれに対応する接続ノ
ード番号が得られる。したがって接続ノードはノード番
号がそれぞれ１０、１１、１２、１のノードの順に探索
される。ここでは接続ノードがノード番号１２のノード
のときだけについて説明する。このときの接続リンクは
リンク番号１４のリンクである。ノード番号１２のノー
ドの計算状況６４は”未計算”であるので、チェックカ
ウント６５をインクリメントして「１」とする。このチ
ェックカウントが更新制約パラメータ８１の値である
「２」以下であるので、ノード番号１２のノードの到達
時間が、注目ノードの到達時間である８（分）とリンク
番号１４のリンクの通行時間である７（分）の和として
１５（分）と計算される。この到達時間は現時点の探索
履歴テーブル６０から得られるノード番号１２のノード
の到達時間である「９９９９９」（分）より小さいの
で、探索履歴テーブル６０に対して、ノード番号１２の
到達時間６２の項にこの到達時間を上書きし、親ノード
番号６３の項には注目ノードのノード番号である「４」
を上書きする。接続ノードの新たな到達時間である１５
（分）は、旅行時間１０１である２２（分）以下であ
り、かつ、接続ノードの計算状況６４は”未計算”であ
るので、現時点で格納されているノード番号が１レコー
ド目から順番に、５、７、８、９、１０、１１の六つと
なっている探索ノードテーブル７において、７レコード
目に接続ノードのノード番号である「１２」を書き込
む。また、探索履歴テーブル６０において、ノード番号
１２のノードの計算状況６４を”未確定”とする。

【００９５】注目ノードであるノード番号４のノードの
接続ノードをすべて探索した結果、探索ノードテーブル
７上に格納されているノード番号は七つあり、１レコー
ド目から順番に、５、７、８、９、１０、１１、１２と
なっている。したがって、注目ノードの候補とするノー
ドのノード番号の、探索ノードテーブル７における１レ
コード目からの個数ｙは、前記（１）式を用いて次のよ
うに求めることができる。探索ノードテーブル７上に存
在するノード番号の個数ｘは「７」であり、候補制約パ
ラメータ８２の値αは「０．７」であるので、

【００９６】ｙ＝［（７−１）×０．７］＋１＝［４．
２］＋１＝４＋１＝５

【００９７】すなわち、探索ノードテーブル７におい
て、１レコード目から５レコード目までのノード番号の
ノードを注目ノードの候補とする。このように候補をし
ぼることによって、この候補のなかで最小の到達時間を
もつノードを選択するために必要な計算時間を短縮する
ことができる。これらのノード番号５、７、８、９、１
０のそれぞれに対応する到達時間のうち、ノード番号１
０に対応する到達時間の１０（分）が最小であるので、
ノード番号１０のノードを次の注目ノードとする。そし
て探索ノードテーブル７において、ノード番号１０を５
レコード目から取り除き、６レコード目以降の内容を１
レコードずつ前につめ、１レコード目から順番に、５、
７、８、９、１１、１２の六つが格納されているように
する。さらに探索履歴テーブル６０において、ノード番
号１０に対応する計算状況を”確定”とする。

【００９８】（１６）終了判定（Ｓ１４） （１５）の制約探索処理Ｓ１３においてノード番号１０
のノードが次の注目ノードに選ばれたので、ノード番号
１０のノードを新たな注目ノードとして、制約パラメー
タ設定処理Ｓ１２を行なう。

【００９９】（１７）制約パラメータ設定処理Ｓ１２ 注目ノードであるノード番号１０のノードにおける到達
時間は１０（分）であるので、更新制約パラメータ８１
の値を「２」に、候補制約パラメータ８２の値を「０．
７」に設定する。

【０１００】（１８）制約探索処理Ｓ１３ ノード番号１０のノードが注目ノードである。ここで
は、接続ノードがノード番号１２のノードのときだけに
ついて説明する。このときの接続リンクはリンク番号１
５のリンクである。ノード番号１２のノードの計算状況
６４は”未確定”であるので、チェックカウント６５を
インクリメントして「２」とする。このチェックカウン
トが更新制約パラメータ８１の値である「２」以下であ
るので、ノード番号１２のノードの到達時間が、注目ノ
ードの到達時間である１０（分）とリンク番号１５のリ
ンクの通行時間である３（分）の和として１３（分）と
計算される。この到達時間は現時点の探索履歴テーブル
６０から得られるノード番号１２のノードの到達時間で
ある１５（分）より小さいので、到達時間６２と親ノー
ド６３を再び更新する。次の注目ノードはノード番号１
１のノードになる。

【０１０１】（１９）終了判定Ｓ１４ ノード番号１１のノードを新たな注目ノードとして、制
約パラメータ設定処理Ｓ１２を行なう。

【０１０２】（２０）制約パラメータ設定処理Ｓ１２ 注目ノードであるノード番号１１のノードにおける到達
時間は１１（分）であるので、更新制約パラメータ８１
の値を「２」に、候補制約パラメータ８２の値を「０．
７」に設定する。

【０１０３】（２１）制約探索処理（Ｓ１３） ノード番号１１のノードが注目ノードである。ここでは
接続ノードがノード番号１２のノードのときだけについ
て説明する。ノード番号１２のノードの計算状況６４
は”未確定”であるので、チェックカウント６５をイン
クリメントして「３」とする。このチェックカウント６
５が更新制約パラメータ８１の値である「２」より大き
いので、到達時間の計算も、到達時間６２と親ノード６
３の更新もおこなわずに、このまま次の処理へ進む。次
の注目ノードはノード番号５のノードになる。

【０１０４】（２２）終了判定処理（Ｓ１４） ノード番号５のノードを新たな注目ノードとして、制約
パラメータ設定処理Ｓ１２を行なう。以上の処理（１
４）から処理（２２）で、ノード番号１２のノードにお
ける到達時間６２と親ノード６３の更新判定の実行に対
して、更新制約パラメータ８１の値によって制約を与え
ることの効果を考える。もし、処理（２１）の制約探索
処理Ｓ１３においてノード番号１２のノードの到達時間
６２の計算をおこなったとしても、更新判定Ｓ２７によ
って、結局、到達時間６２の更新はおこなわれず、到達
可能範囲算出処理における解の精度には影響がないの
で、到達時間６２の計算に必要な時間は無駄になる。し
たがって、無駄な計算時間の省略が可能なことがわか
る。

【０１０５】図１３に示す探索履歴テーブル６０と図１
４に示す探索ノードテーブル７の内容は、この時点の状
態に対応している。以下、注目ノードがヌルになるまで
同様に繰り返す。到達可能範囲算出処理が終了した時点
で、探索履歴テーブル６０の計算状況６４が”開始ノー
ド”あるいは”確定”であるノードが、旅行時間１０１
内に到達可能なノードである。また、各ノードの親ノー
ド６３を旅行開始地点のノードまでたどっていくことに
よって、旅行開始地点のノードからそのノードへの最短
路を求めることができる。

【０１０６】（３−９）の注目ノード候補決定処理Ｓ２
９では、候補制約パラメータ８２の値が「１」のとき
は、探索ノードテーブル７上のノード番号の個数にかか
わらず、注目ノードの候補とするノードの個数を前記
（１）式で計算しなくてもよいと述べたが、候補制約パ
ラメータ８２の値が「０」のときも同様である。このと
きは、探索ノードテーブル７において１レコード目に格
納されているノード番号のノードが注目ノードになる。

【０１０７】上述の実施の形態においては、制約パラメ
ータ８０には、更新制約パラメータ８１と候補制約パラ
メータ８２の二つがあるとしたが、どちらか一方だけで
もよい。すなわち、注目ノードの候補には制約を与えず
に、到達時間６２と親ノード６３の更新判定の実行にだ
け制約を与えるようにしてもよいし、到達時間６２と親
ノード６３の更新判定の実行には制約を与えずに、注目
ノードの候補にだけ制約を与えるようにしてもよい。

【０１０８】また、制約パラメータ設定処理Ｓ１２にお
いては、注目ノードにおける到達時間６２によって制約
パラメータ８０を段階的に設定したが、注目ノードにお
ける接続リンク条件によって段階的に設定してもよい。
例えば、接続リンク条件として接続リンク数を考えたと
き、注目ノードにおける接続リンク数が小さいほど、比
較的計算時間が長い高精度な探索方法を適用しても計算
時間がかからないので、解の精度を高くするために、更
新制約パラメータ８１の値も候補制約パラメータ８２の
値もともに大きく設定する。注目ノードにおける接続リ
ンク数が大きいほど計算時間がかかるので、計算時間を
短くするために、更新制約パラメータ８１の値も候補制
約パラメータ８２の値もともに小さく設定する。

【０１０９】または、更新制約パラメータ８１と候補制
約パラメータ８２のうち、一方は注目ノードにおける到
達時間６２によって、もう一方は注目ノードにおける接
続リンク条件によって、段階的に設定するようにしても
よい。

【０１１０】さらに、制約パラメータ設定処理Ｓ１２に
おいて、注目ノードにおける到達時間６２などを考え
ず、制約パラメータ８０は到達可能範囲算出処理の間、
常に一定にしてもよい。

【０１１１】さらにまた、更新制約パラメータ８１と候
補制約パラメータ８２のうちのどちらか一方だけが、注
目ノードにおける到達時間６２などによらず一定として
もよい。

【０１１２】本実施形態の効果として、到達可能範囲算
出処理において、無駄な計算時間を省略するために、到
達時間６２と親ノード６３の更新判定の実行や注目ノー
ドの候補に制約を与える制約パラメータ８０を、注目ノ
ードにおける到達時間６２によって段階的に変化させる
ことによって、必要なところで必要な精度を保ちながら
高速化することができる。これによって従来よりも、計
算時間および解の精度の両方に関して効率的な所定時間
内到達可能範囲の算出が可能となる。また、制約パラメ
ータ８０の設定値により計算時間や解の精度が変化する
ので、必要に応じて計算時間あるいは解の精度を調節す
ることも可能である。したがって、前実施形態と同様、
本システムは旅行時間内に移動可能な観光地を高速高精
度に算出でき、その利用者は速く正確に観光地を選定す
ることができる。

【０１１３】以上が本発明の到達可能範囲算出方法の詳
細実施形態であるが、本方法は、一定時間での行動可能
範囲算出によって、消防車や救急車がサポートできる範
囲と行動時間を決定するシステム、宅配便の集配所やピ
ザ屋、コンビニエンスストアなどのサポート範囲を決定
するシステムにも利用可能である。

【０１１４】

【発明の効果】本発明によれば、ベクトル地図におい
て、指定した地点から指定した時間で到達可能な範囲を
高速かつ高精度に算出することができる。また、ベクト
ル地図において、到達範囲を計算するに当たって、必要
に応じて計算時間あるいは解の精度を調節することがで
きるので、目的に応じた精度と速度の計算方法を得るこ
とができる。

【図面の簡単な説明】

【図１】旅行先決定支援システムの画面イメージ。

【図２】第１の実施の形態における旅行先決定支援シス
テムのシステム構成図。

【図３】第１の実施の形態で用いるベクトル地図の例を
示す図。

【図４】リンクテーブル構成図。

【図５】ノードテーブル構成図。

【図６】第１の実施の形態における到達可能範囲算出処
理フロー図。

【図７】第１の実施の形態における探索履歴テーブル構
成図。

【図８】第１の実施の形態における探索ノードテーブル
構成図。

【図９】図３の各ノードにおける適用探索方法を説明す
る図。

【図１０】図３に対して到達可能範囲を算出した結果を
説明する図。

【図１１】第２の実施の形態における到達可能範囲算出
処理フロー図。

【図１２】第２の実施の形態で用いるベクトル地図の例
を示す図。

【図１３】第２の実施の形態における探索履歴テーブル
構成図。

【図１４】第２の実施の形態における探索ノードテーブ
ル構成図。

【図１５】制約探索処理フロー図。

【符号の説明】

１ 到達可能範囲算出処理機能 ４ ベクトル地図データ ６ 探索履歴テーブル ７ 探索ノードテーブル ８ 切替パラメータ １０ シミュレーション条件入力装置 ８０ 制約パラメータ ８１ 更新制約パラメータ ８２ 候補制約パラメータ ６０ 探索履歴テーブル Ｓ２ 切替パラメータ設定処理 Ｓ３ 適用探索方法判定 Ｓ４ 高精度探索処理 Ｓ５ 高速探索処理 Ｓ１２ 制約パラメータ設定処理 Ｓ１３ 制約探索処理 Ｓ２５ 更新判定の実行判定 Ｓ２９ 注目ノード候補決定処理

───────────────────────────────────────────────────── フロントページの続き (72)発明者 北澤 修司 東京都千代田区神田駿河台四丁目６番地 株式会社日立製作所システム事業部内

Claims (15)

【特許請求の範囲】
1. 【請求項１】 ベクトル地図データと探索履歴テーブル
   と探索ノードテーブルを用いて、指定した地点から指定
   した時間で到達可能な範囲を求める所定時間内到達可能
   範囲算出方法において、候補制約パラメータを固定値と
   して設定する手段と、注目ノードの選択範囲を前記候補
   制約パラメータによって決定する手段を有することを特
   徴とするベクトル地図における所定時間内到達可能範囲
   算出方法。
2. 【請求項２】 ある一つの注目ノードにおける接続ノー
   ドの探索において、探索ノードテーブルに格納すべき接
   続ノードのノード番号を、該接続ノードに対応する接続
   リンクの通行時間が小さい順に該探索ノードテーブルに
   格納していく手段を有することを特徴とする請求項１に
   記載のベクトル地図における所定時間内到達可能範囲算
   出方法。
3. 【請求項３】 ベクトル地図データと探索履歴テーブル
   と探索ノードテーブルを用いて、指定した地点から指定
   した時間で到達可能な範囲を求める所定時間内到達可能
   範囲算出方法において、更新制約パラメータを固定値と
   して設定する手段と、注目ノードにおける接続ノードに
   対して到達時間と親ノードの更新判定を実行するか否か
   を、該接続ノードのチェックカウントと前記更新制約パ
   ラメータを比較することによって判定する手段を有する
   ことを特徴とするベクトル地図における所定時間内到達
   可能範囲算出方法。
4. 【請求項４】 更新制約パラメータを固定値として設定
   する手段と、注目ノードにおける接続ノードに対して到
   達時間と親ノードの更新判定を実行するか否かを、該接
   続ノードのチェックカウントと前記更新制約パラメータ
   を比較することによって判定する手段を有することを特
   徴とする請求項１または２に記載のベクトル地図におけ
   る所定時間内到達可能範囲算出方法。
5. 【請求項５】 候補制約パラメータを固定値として設定
   する手段の代わりに、前記候補制約パラメータを注目ノ
   ードにおける到達時間によって段階的に設定する手段を
   有することを特徴とする請求項１または２または４のい
   ずれかに記載のベクトル地図における所定時間内到達可
   能範囲算出方法。
6. 【請求項６】 更新制約パラメータを固定値として設定
   する手段の代わりに、前記更新制約パラメータを注目ノ
   ードにおける到達時間によって段階的に設定する手段を
   有することを特徴とする請求項３または４に記載のベク
   トル地図における所定時間内到達可能範囲算出方法。
7. 【請求項７】 候補制約パラメータを固定値として設定
   する手段と更新制約パラメータを固定値として設定する
   手段の代わりに、前記候補制約パラメータおよび前記更
   新制約パラメータを注目ノードにおける到達時間によっ
   て段階的に設定する手段を有することを特徴とする請求
   項４に記載のベクトル地図における所定時間内到達可能
   範囲算出方法。
8. 【請求項８】 請求項５から７のいずれかに記載の注目
   ノードにおける到達時間の代わりに、前記注目ノードに
   おける接続リンクに関わるパラメータである接続リンク
   条件を用いることを特徴とするベクトル地図における所
   定時間内到達可能範囲算出方法。
9. 【請求項９】 候補制約パラメータを固定値として設定
   する手段と更新制約パラメータを固定値として設定する
   手段の代わりに、前記候補制約パラメータと前記更新制
   約パラメータのうち、一方は注目ノードにおける到達時
   間によって段階的に設定し、もう一方は前記注目ノード
   における接続リンクに関わるパラメータである接続リン
   ク条件によって段階的に設定する手段を有することを特
   徴とする請求項４に記載のベクトル地図における所定時
   間内到達可能範囲算出方法。
10. 【請求項１０】 ベクトル地図データを用いて、指定し
    た地点から指定した時間で到達可能な範囲を求める所定
    時間内到達可能範囲算出方法において、注目ノードに高
    精度探索方法と高速探索方法のどちらを適用するかを、
    該注目ノードにおける接続リンクに関わるパラメータで
    ある接続リンク条件と切替パラメータを比較することに
    よって判定する手段を有することを特徴とするベクトル
    地図における所定時間内到達可能範囲算出方法。
11. 【請求項１１】 請求項８から１０のいずれかに記載の
    接続リンク条件は、接続リンク数であることを特徴とす
    るベクトル地図における所定時間内到達可能範囲算出方
    法。
12. 【請求項１２】 請求項８から１０のいずれかに記載の
    接続リンク条件は、全接続リンクの平均通行時間である
    ことを特徴とするベクトル地図における所定時間内到達
    可能範囲算出方法。
13. 【請求項１３】 注目ノードに高精度探索方法と高速探
    索方法のどちらを適用するかを、該注目ノードにおける
    接続リンクに関わるパラメータである接続リンク条件と
    切替パラメータを比較することによって判定する手段の
    代わりに、前記注目ノードにおける到達時間と切替パラ
    メータを比較することによって、該注目ノードに高精度
    探索方法と高速探索方法のどちらを適用するかを判定す
    る手段を有することを特徴とする請求項１０に記載のベ
    クトル地図における所定時間内到達可能範囲算出方法。
14. 【請求項１４】 注目ノードに高精度探索方法と高速探
    索方法のどちらを適用するかを、該注目ノードにおける
    接続リンクに関わるパラメータである接続リンク条件と
    切替パラメータを比較することによって判定する手段の
    代わりに、経過計算時間と切替パラメータを比較するこ
    とによって、前記注目ノードに高精度探索方法と高速探
    索方法のどちらを適用するかを判定する手段を有するこ
    とを特徴とする請求項１０に記載のベクトル地図におけ
    る所定時間内到達可能範囲算出方法。
15. 【請求項１５】 到達時間が指定時間以内のノードだけ
    を注目ノードとすることにより、該指定時間以内に到達
    可能なノードに対してだけ接続ノードを探索する手段を
    有することを特徴とする請求項１から１４のいずれかに
    記載のベクトル地図における所定時間内到達可能範囲算
    出方法。