JPH02172000A - 最短経路探索装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 【産業上の利用分野】

本発明は、ネットワークにおいて、探索開始位置から探
索終了位置へ至る最短経路を自動探索する装置に関する
。例えば、移動体の現在位置からこれから行こうとする
目的位置までの最短経路を道路地図上において探索する
ナビゲーション装置等に応用される。

【従来技術】

移動体の現在位置から目的位置へ至る最短経路を探索し
、その経路を表示する車載ナビゲーション装置は多数開
発され公開されている。 これらの装置に要請されることは、探索開始位置と探索
終了位置のノード対が特定されたとき、そのノード対間
の最短経路を高速に探索して表示することである。 従来から、最短経路の探索手法はネットワーク管理や電
気回路の分野においても必要であり研究されている。 例えば、ラベル確定法、行列法、ダイナミックプログラ
ム法等がある。なかでも、ラベルは定法は探索効率が良
くディジタル演算に適していることから多くの研究がな
されている。その中では、ポテンシャル法、ダイキスト
ラ法、ニコルフン法等が代表的な解決として知られてお
り、特に最近では、探索中の状態ファイルを更新する効
率のよい方法として、ヒープ法やパケット法等の改良ア
ルゴリズムが発表されている。

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

しかし、上記のラベル確定法は、探索開始位置から経路
距離が最短な探索枝を順次延ばして行く手法のため、最
先端のノードは概念的には探索開始位置から等距離の位
置にある。したがって、探索は探索開始位置を中心とし
て同心円状に拡大して行くことになり、探索終了位置が
その円上にくる時に探索終了となる。このため、探索開
始位置に対して探索終了位置と反対側の半円内部に最短
経路が存在する確率は低く、その半円領域の探索は無駄
な探索となる。 それに対し、ニコルフン法は１つの探索開始位置と探索
終了位置間における最短経路を求める問題を対象にして
いる。ニコルフン法は探索開始位置と探索終了位置の双
方向からラベル確定法と同様な探索を行うものである。 したがって、探索は探索開始位置と探索終了位置とをそ
れぞれ中心として同心円状に等半径で拡大して行くこと
になり、双方向からの円が交差する時に探索終了となる
。 このため、一方向から探索するラベル確定法に比べて探
索領域は約１／２となる。 しかし、ニコルラン法においても、探索開始位置と探索
終了位置とを中心とする各回の相互に遠い側の半円領域
も探索していることになり、最短経路の存在確率の低い
範囲を；ｌに駄に探索している。 このため、探索時間がかかり車載ナビゲーション装置に
要求される応答時間を確保するには不十分である。 又、探索開始位置と探索終了位置とをそれぞれ中心とす
る２つの円が等半径となるように、双方向からの探索順
序を交互に切り換えている。しかし、探索時間は探索す
るノード数で決定されるため、ノード密度が異なれば双
方向から等距離で探索する場合が最も探索ノード数が少
ないとは限らない。このように、ニコルラン法でも最も
効率的な探索が実行されているとは言い難い。 更に、車両が最短経路に従って移動している時、何らか
の原因で最短経路から外れる場合など、同一目的位置に
向けて再び最短経路を求め表示したい場合がある。しか
し、改めて新たな現在位置と目的位置とに対して両位置
の最短経路を求めていたのでは、経路探索の効率が良く
なく、やはり動作速度上問題がある。

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

第１発明は、第１図（ａ）に示すように、径路データ記
憶手段、位置入力手役、双方向探索手役、探索順序ｍ＋
制御手段、最短経路決定手段、表示手段とで構成されて
いる。 経路データ記憶手段は、ノード及び枝で構成される、例
えば、道路地図、回路等の最短径路検索の対象となる経
路データを記憶する手段である。 位置入力手役は、探索開始位置及び探索終了位置を入力
する手段である。例えば、移動体の地図上の現在位置及
び目的位置を入力する手段である。 双方向探索手役は、位置入力手役により入力された探索
開始位置及び探索終了位置の双方向から経路データを用
いて順次ノード又は枝を探索して最短経路を探索する手
段である。最短経路は経路長、所要時間、費用等やこれ
らの潰を総合評価した評価値が最小となる経路として定
義される。そして、各方向からの探索は、例えば、この
評価値が小さいものから順にノード又は枝を選択して、
探索ネットワークを拡張する手順で実行される。 探索順序制御手段は、双方向探索手役による探索順序を
制御する手段である。探索順序は、双方向探索過程にお
いて、各方向から順次探索される探索ノード又は探索枝
の数が略均衡するような順序とされる。即ち、探索の進
行速度が双方向探索で均衡するように制御される。 最短経路決定手段は、双方向からの探索ノード又は探索
枝が接続された経路の中から、探索開始位置から探索終
了位置に至る最短経路を決定する手段である。例えば、
探索過程において探索開始位置への最短経路の確定され
たノードと探索終了位置への最短経路の確定されたノー
ドが最先に一致した時には、そのノードが存在する経路
が最短経路とされる。 表示手段は、その最短経路を表示する手段である。例え
ば、道路地図を表示すると共に、その道路地図上に探索
開始位置である現在位置と探索終了位置である目的位置
と、その両位置を結ぶ最短経路とを表示する手段である
。 第２発明は、ｍ１図（ｂ）に示すように、経路データ記
憶手段、位置入力手役、双方向探索手役、探索領域制限
手段、最短経路決定手段、表示手段とで構成されている
。経路データ記憶手段、位置入力手役、双方向探索手役
、最短経路決定手段、表示手段は第１発明と同一の構成
である。 探索領域制限手段は、双方向探索手役による探索領域を
制限するものである。探索領域は、探索開始位置及び探
索終了位置を焦点付近としそれらの両位置を結ぶ線分を
長袖とする楕円又はその楕円に近似される形状の内部領
域に限定される。焦点位置や楕円形状を特定する離心率
は探索開始位置と探索終了位置との距離に応じて変化さ
せても良い。即ち、探索開始位置と探索終了位置との位
置関係により、最短経路が存在する確率の高い領域を広
くし、存在する確率の低い領域を狭くするようにしても
良い。又、探索領域は、−船釣には、上記楕円の内部の
他、幾何学的に最短経路が存在する確率の高い領域は内
部とし、最短経路の存在する確率の低い領域は外部とす
るような形状の内部であれば良い。したがって、探索領
域は、上記楕円内部の他、楕円様の曲線の内部、その楕
円に内接又は外接する長方形の内部、探索開始位置と探
索終了位置を焦点とする相互に向かいあう２つの放物線
で囲まれた領域等であっても良い。 第３発明は、′ｆ５１図（Ｃ）に示すように、経路デー
タ記憶手段、位置入力手役、双方向探索手役、縮退探索
手段、最短経路決定手段、表示手段とで構成されている
。位置入力手役、双方向探索手役、最短経路決定手段、
表示手段は第１発明と同一の構成である。 経路データ記ｔα手役はノード及び枝の情報及び枝の優
先度を示す等級データを記憶するものである。 又、縮退探索手段は、順次探索される探索ノード又は探
索枝を、その等級データにより制限する手段である。こ
の等級は、例えば、道幅や車線数及び高速道路、国道、
県市町村道などの道路等級等で区別されるような枝の優
先度を示すものである。したがって、選択枝の等級を所
定の条件で制限するということは、例えば、広い国道に
沿って１つの経路が探索されている場合に、その国道に
接続されている狭い脇道等は探索の対象から除外され、
その脇道に接続される枝はそれ以上探索されないことを
意味しており、探索速度が向上する。 又、第４発明は、第１図（ｄ）に示すように、上記第１
発明乃至第３発明において、更に、探索開始位置判定手
段、第２最短経路決定手段、片方向探索手段、第３最短
経路決定手役を付加したものである。 この第４発明は、探索終了位置が不変で探索開始位置が
変化した２回目以後の探索に有効である。 探索開始位置判定手段は、探索開始位置が既に決定され
ている最短経路上又は探索終了位置からの探索領域内に
存在するか否かを判定する手段である。 第２最短経路決定手段は、探索開始位置判定手段の判定
結果が肯定的である時に、探索終了位置からの探索結果
データによって探索開始位置から探索終了位置までの最
短経路を決定する手段である。 片方向探索手段は、探索開始位置判定手段の判定結果が
否定的である時に、探索開始位置からのみ順次ノード又
は枝を探索して最短経路を探索する手段である。即ち、
探索終了位置からの探索結果は前回までの探索で既に得
られているので、それを利用するようにしている。 第３最短経路決定手段は、その片方向探索からの探索ノ
ード又は探索枝が探索結果データに含まれる探索ノード
又は探索枝に接続された経路の中から最短経路を決定す
る手段である。即ち、片方向探索が進行すると探索終了
位置から探索されたノード又は探索枝に接続されるよう
になる。しかし、この場合には、最先に接続される経路
が最短経路になるとは限らないので、接続された幾つか
の経路の中から、経路の評価値が最小のものが最短経路
として決定される。

【作用】

第１発明では、位置入力手役により探索開始位置と探索
終了位置が指定されると、双方向探索手役により探索開
始位置と探索終了位置の双方向から順次探索される。探
索順序制御手段により、その双方向探索過程における探
索順序は探索されるノード又は枝の数が等しくなる順序
に制御される。 そして、最短経路決定手段により、探索が進行して双方
向から探索枝又は探索ノードが一致した経路の中から最
短経路が決定され、表示手段によりその最短経路が表示
される。 又、第２発明では、第１発明の探索順序制御手段に換わ
る探索領域制限手段により、双方向探索過程において、
探索されるノード又は枝が上記の所定の最短経路の存在
する確率の高い楕円等の領域内に制限される。 又、第３発明では、第１発明の探索順序制御手段に換わ
る縮退探索手段により、双方向探索過程において、更に
、枝の等級データにより、探索される探索ノード又は探
索枝が制限される。 又、第４発明では、２回目以後の探索において、探索開
始位置判定手段により、探索開始位置が既に決定されて
いる最短経路上又は探索終了位置からの探索領域内に存
在すると判定されると、第２最短経路決定手段により、
探索終了位置からの探索結果データによって探索開始位
置から探索終了位置までの最短経路が直ちに決定される
。又、探索開始位置判定手段により探索開始位置が既に
決定されている最短経路上又は探索終了位置からの探索
領域内に存在しないと判定されると、片方向探索手段に
より、探索開始位置からのみ順次最短経路が探索される
。そして、第３最短経路決定手段により、探索が進行し
その片方向探索からの探索ノード又は探索枝が探索結果
データの探索ノード又は探索枝に接続されたと判定され
ると、その接続された経路の中から最短経路が決定され
る。

【実施例】

以下、本発明を具体的な実施例に基づいて説明する。 第２図は本発明の実施例に係る車載ナビゲーション装置
１０の構成を示すものである。 尚、本実施例では探索開始位置は現在位置に、探索終了
位置は目的位置として具体化されている。 図において、コンピュータ２０はデータ記憶媒体２１を
アクセスして、最短経路探索演算等を実行する装置であ
る。コンピュータ２０は専用のマイクロプロセッサか、
或いは汎用性のパーソナルコンピュータで構成され、記
ｔａ媒体２１は、フロッピィディスク、ハードディスク
若しくはＲＡＭディスク等で構成される。その記憶媒体
２１には地図データベースと探索プログラムが記憶され
、探索過程データや探索結果データを記ｔａする探索デ
ータファイルが形成されている。 又、車載ナビゲーション装置ｌＯは、車両の現在位置を
受信する受信手段５０を備えている。その受信手段５０
は車載アンテナ５１と受信機５２で構成され、車外に設
置された送信手段６０から現在位置を表す地点コードデ
ータを受信し、そのデータをコンピュータ２０に回線８
４を介して出力する手段である。送信手段６０は送信ア
ンテナ６１と送信機６２で構成され、一般に路側に設置
されており、その設置位置の地点コードデータを発信す
る手段である。 尚、現在位置を与える方法は、上記方法の他、公知の車
載センサにより方位と移動距離を計測して推測する方法
か、通信衛星から測位データを受信して現在位置を知る
位置標定法であっても良い。 車載ナビゲーション装＋ｊｆ１１０は、ＣＲＴデイスプ
レィ４１若しくはＸ′ＹＺモニタで構成されるデイスプ
レィ手段４０を有している。デイスプレィ手段４０は、
幾つかの街路、車両の記号、現在位置と目的位置とを結
ぶ最短経路等の地図を表示する。又、デイスプレィ手Ｒ
４０は更にパネルスイッチ４３及び画面上に設けたタッ
チスイッチ４４を備えており、制御コンソール３０に替
えてオペレータｎＡ御コマンドを入力できる。例えば、
目的位置は、画面上の地図において目的位置に対応する
地点を上記スイッチの操作により直接指定することによ
り入力できる。この他、オペレータはパネルスイッチ４
３とタッチスイッチ４４の操作手順を交互に組み合わせ
て種々のコマンドを発生できる。デイスプレィ手段４０
は切替スイッチ４５を介して制御コンソール３０とコン
ピュータ２０に接続されている。 制御コンソール３０はデイスプレィ手段４０の画面を制
御すると共に回線８１を介してコンピュータ２０と接続
され、コマンドデータをコンピュータ２０へ出力する。 コンピュータ２０は回線８３を介してデイスプレィ手段
４０へ映像信号、例えばＲＧＢ信号を送り、地図等を画
面に表示する１゜スイッチ回路７１はエンジンキースイ
ッチ７２と連動してオン、オフ信号を発生し、回線８２
を介してコンピュータ２０へその信号を出力する。 コンピュータ２０はこのオン信号を入力した時は、経路
探索が１回も実行されていないことを記憶するため、再
探索フラグをＯにリセットする。 本装置の電源が入れられると、後述の方法で入力される
現在位置を中心とする地図がデイスプレィ手段４０に表
示される。その後オペレータは、上述したように制御コ
ンソール３０又はデイスプレィ手段４０のスイッチ類４
３．４４を操作して、目的位置を指定する。この指定に
より得られた目的位置データはコンピュータ２０に入力
され記憶媒体２１に記憶される。又、車両が所与の領域
の街路を走行中、路側に設置されている送信手段６０の
横を通ると、送信機６２で発信された現在位置を示すデ
ータは受信機５２で受信され、コンピュータ２０はこの
データを受４８１１５２から入力し、現在位置データと
し記ｉ、α媒体２１に記憶する。 地図はノードを中心に構成しても枝（リンク）を中心に
構成しても良い。ノードを中心として１１１４成される
地図データベースは次の情報で構成されている。 （１）街路を規定するノードのコード番号（２）直進、
右左折などの通行規１１１を規定する通行フラグ （３）車種規制、時間帯規制などリンクの通行現ｉ１ｒ
！１を規定するリンク通行フラグ （４）リンク距離、旅行時間又は速度等のリンク属性値 （５）道路種別、道路等級等のリンク属性値（６）ノー
ドのＸ％　Ｙ座標 更に、行政区界、港湾、川、施設、鉄道及びそれらの名
前、座標等のｔｉ７報が含まれる。この記憶された地図
データベースは地理的に所与の領域を移動するときに使
用される。 車両が、ある地点からある地点へ移動する時、コンピュ
ータ２０が適切な地図を呼び出し、ＣＲＴデイスプレィ
４１に表示することができる。推測航法を備えた車載ナ
ビゲーション装置では車両の移動軌跡を推測でき、これ
を表示中の地図に重ね書きすることができる。又、後に
述べる経路探索アルゴリズムによって得られる最短経路
を表示中の地図に重ね書きすることができる。 経路探索アルゴリズムによって得られる最短径路は、経
路を構成するノード番号の並びとして記憶媒体２１の探
索データファイルに記憶される。 経路探索が終了した時点の探索結果データはトランジェ
ントな探索データファイルとして記憶媒体２１に記憶さ
れる。そして、探索データファイルは探索枝を展開する
カレントファイルと、探索ノードを展開するノードファ
イル出で構成される。 カレントファイルには次のデータが展開される。 （１）経路探索の開始と共に順次開かれる探索枝の並び （２）探索枝を開き終わったか、まだ開き終わっていな
いかを示すフラグ （３）探索枝までの経路コスト。例えば経路距離、又は
旅行時間 （４）探索枝へ最短経路で連続する一つ手前のノード番
号 （１）の探索枝の並びは、（３）の経路コストを属性値
とし、その経路コストが最小となる探索枝の抽出に用い
られる。（２）のフラグは最短経路の確定された探索枝
（永久技）の集合と、未だ、最短経路が確定していない
が探索枝により次のノードを探索している過程の枝（活
性技）の集合を区別するために用いられる。 上記のデータで構成されるカレントファイルはヒープ法
かパケット法によるデータ構造を持たせると、次に開く
枝の集合を限定でき、且つ、評価値が最小な枝の抽出が
効率的となる。このカレントファイルは探索枝の一つを
ルーコード単位とするもので、探索の進行と共にファイ
ルの大きさが増大する。このカレントファイルは、現在
位置及び目的位置からの探索過程でそれぞれ展開される
２つのサブファイルで構成されている。 又、ノードファイルは探索中のノード（活性ノード）と
最短経路の確定されたノード（永久ノード）と探索枝が
未だ延びていないノード（休眠ノード）とを区別して記
憶するものである。そして、このノードファイルも現在
位置からの探索と目的位置からの探索とで展開される２
つのサブファイルに分かれている。又、目的位置からの
探索に使用されるノードファイルには、探索終了時、２
回目量後の探索過程で使用される探索結果データが記憶
されていることになる。 次に、最短経路探索手順をコンピュータ２０の処理手順
を示したフローチャートに従って説明する。 プログラムは第３図に示すように、大きく３つに分類さ
れる。 第１は画面表示や目的位置、現在位置の入力を制御し全
体を監視するメインプログラムであり、第２はＣＲＴデ
イスプレィ４１をリフレッシュし、制御コンソール３０
からの操作データ等の入力を行うプログラムであり、第
３は最短経路探索を実行するためのプログラムである。 このうち、第２のプログラムはリフレッシュ時又はデー
タ入力が発生する毎にメインプログラム及び第３の最短
経路探索プログラムをインタラブドし、第３の最短経路
探索プログラムは現在位置が入力され最短経路探索の実
行要求が発生する毎に、メインプログラムをインタラブ
ドするように構成されている。 メインプログラムはコンピュータによって処理される全
ての情報に応答して、必要なデータを計算しフォーマッ
ト化する。例えば、ＣＲＴデイスプレィ４Ｉに表示され
選択される地図のデータ、現在位置及び目的位置のコマ
ンドデータ、最短経路探索プログラムに与える現在位置
と目的位置を示す地点コードと探索モード等を計算し処
理する。 又、目的位置が更新される毎に、再探索フラグは０にリ
セットされる。 次に、最短経路探索手順について説明する。 第４図において、ステップ１００では、再探索フラグを
照合することにより初回探索であるか否かが判定される
。再探索フラグが０のリセット状態であれば、初回探索
であることを意味しており、ステップ１０２で探索実行
プログラムが実行され、探索実行後、既に初回探索が完
了したことを示すために再探索フラグが１にセットされ
、ステップ１０４で最短経路が更新される。又、初回探
索でない場合には、ステップ１０６へ移行して現在位置
が既に求められている最短経路上に存在するか否かが判
定され、最短経路上に存在する場合には、最短経路を更
新することなく、本プログラムは終了される。即ち、地
図上の現在位置を更新するだけで良い。又、現在位置が
最短経路上に存在しない場合には、ステップ１０２へ移
行して最短経路の再探索が実行される。 そして、本プログラムによる探索結果に基づいて、メイ
ンプログラムが実行され、求められた最短経路はＣＲＴ
デイスプレィ４１に表示される。 次に、ステップ１０２で実行される探索実行手順につい
て説明する。 第５図において、ステップ２００では、再探索フラグを
照合することにより初回探索であるか否かが判定される
。初回探索であると判定された場合には、ステップ２０
２へ移行して初回探索実行プログラムが実行され、初回
探索でないと判定された場合には、ステップ２０４へ移
行して再探索実行プログラムが実行される。そして、探
索実行後、ステップ２０６にて探索成功か否かが判定さ
れ、探索成功であれば、そのまま終了し、探索成功でな
い場合には、ステップ２０８で等ノードによる探索が実
行される。即ち、ステップ２０２．２０４の探索では探
索領域を楕円領域に制限しているので、現在位置と目的
位置とを結ぶ経路がその楕円領域に存在しない場合が考
えられるので、その場合には探索領域を制限しない双方
向の等ノード探索が実行される。 次に、ステップ２０２で実行される初回探索手順につい
て説明する。 処理手順を詳細に説明する前に、探索概念について次に
説明する。 初回探索手順は、現在位置と目的位置の双方向から探索
する方法（双方向探索）、探索領域を楕円内部に制限す
る探索方法（楕円探索）、双方向探索の探索過程におい
て探索されるノード又は枝の数が均衡するような探索方
法（等ノード探索）、最短経路を評価する経路長、所要
時間、費用等又はこれらを総合評価した評価値（以下、
この評価値を「コスト」という）の小さいものから順に
探索する方法（等コスト探索）、探索枝をその等級に応
じて制限する探索方法（縮退探索）の全てのＡＮＤ条件
により実行される。 双方向探索、等ノード探索、等コスト探索を実行すると
、探索領域は概念的には、第８図に示すように、現在位
［０及び目的位ｉｄＤを中心とする探索の進行に伴って
拡大していく等半径の円となる。そして、その２つの円
が交差し両方向から延びた永久ノードが最初に接続され
たとき、そのノードの存在する経路が現在位置と目的位
置とを結ぶ最短経路となる。 又、楕円探索は、探索領域を現在位置と目的位置とを原
則的に焦点とし、その焦点を結ぶ軸を長軸とする楕円の
内部に限定する探索手法である。 そして、楕円探索を上記の双方向探索、等ノード探索、
等コスト探索と組み合わせると、第９図に示すような、
探索モデルとなる。 このような楕円内部に探索領域を限定することで、現在
位ｔｆｆｏからの探索においては目的位１ｆｔＤから遠
ざかる方向Ｘ、目的位置りからの探索においては現在位
置Ｏから遠ざかる方向Ｙへの探索枝の展開が制限される
ことになり、最短経路が存在する可能性の少ない領域Ａ
、Ｂでの探索は制限される。したがって、高速探索が可
能となる。 又、楕円は長径と短径の比Ｆ（０＜Ｆ＜１）を変えるこ
とにより、その形状をパラメトリックに制御できる。Ｆ
を大きくすると円に近づき、Ｐを小さくすると細長い楕
円となる。現在位置と目的位置とを焦点とした場合には
、現在位置と目的位置との距離、つまり焦点１１０の距
離（２Ｃ）が短いとネットワークの粗さが相対的に大き
くなり、楕円内に最短経路が入らない場合が発生する。 この弊害を避けるため、現在位置Ｏと目的位置りとの距
離（ＯＤ間距離）が短い時は円に近づけ、長い時は探索
効率を上げるため細長い楕円とする。 方、円に近づけると離率が小さくなり後退方向の最短経
路をカットしてしまう場合が発生するので、焦点を現在
位置と目的位置の外側１７位置するように、焦点間距離
をオフセットしてＯＤ間距離よりも大きくした楕円とす
る。つまりＣ０をオフセットとし、Ｃ＝Ｃ＋ＣＧを新し
い焦点と楕円中心との距離Ｃとする。 ＦはＯＤ距離の長短に応じ、パラメトリックに変化させ
る。つまりＣが小さい時はＦを大きくし、Ｃが大きくな
るに従いＦを小さくし楕円ｅを細長くする。実施例では
Ｃ＋　＜　Ｃｚ　＜　Ｃｓなる閾値を設定し、Ｃ＜ＣＩ
なら　＋？＝Ｆ、、Ｃ１≦Ｃ＜Ｃ２なら　Ｆ＝　Ｆ２、
Ｃ３≦ｃ＜　Ｃ３ならｒ＝　ｒ’、、Ｃ３＜Ｃならｒ’
＝　ｒ’、であるステップ関数とする。ただしＦ、−１
’４は１　＞Ｆ＋＞Ｆｉ＞ｌ？３＞Ｌ＞　Ｏなる定数で
ある。 縮退探索は、探索の際、探索枝を順次道路等級の等しい
か、又は高い方へ上げながら、優先順位の低い道路技を
カットし、縮退した道路網により探索を行うものである
。これにより、例えば、道幅の広い国道等に沿って探索
が実行されている時、その国道に接続される道幅の狭い
脇道等−・探索枝が延びることが防止され、効率の良い
探索が行われる。道路等級は任意に設定でき、例えば市
町村道、県道、国道、高速道路の順に等級を設定するこ
とでも良い。この他の、道路中の大小、設計交通容量、
設計速度、有料道路と；１１料道路の違いによって等級
を設定することもできる。道路等級により縮退を行うと
、等級が上がるに従いネットワークが粗となり、経路の
跡切れを生じる場合があるので、跡切れを避けるため、
前の探索枝の１ランク下位の等級まで接続を認めるよう
にする。 結局、上記の探索を全て実行すると極めて効率の良い探
索が実行されることになり、その探索の概念は、第１Ｏ
図に示される。 次に、初回探索手順を第６図に従って詳細、に説明する
が、各記号及び用語を次のように定義する。 Ｓ　：現在位置のノード番号 その座標（ＸＳ、、　ＹＳ、） Ｔ　：目的位置のノード番号 その座標（ＸＴ、、　ＹＴ、） ｉ　：任意の活性ノードの番号 に：＊たに発生された活性ノードの番号活性ノードは前
に定義したように、最短経路は未だ確定していないが、
永久ノードから探索枝（活性技）が延び、現在開かれて
いるノードをいう。 ｍ：任意の永久ノードの番号 永久ノードは前に定義したように、Ｓノード又はＴノー
ドまでの最短経路が確定しているノードをいう。 又、現在位置からの探索をＳ探索、目的位置からの探索
をＴ探索、Ｓ探索による永久ノードをＳ永久ノード、Ｔ
探索による永久ノードをＴ永久ノードという。 ｊ　：任意の接続ノードの番号 接続ノードは、Ｓ探索又はＴ探索における活性ノード又
は永久ノードが相手のＴ探索又はＳ探索における活性ノ
ード又は永久ノードと一致したノードをいう。 Ｖ　：全てのノードを含む一般的なノードの番号５（ｖ
）　：　ＳノードからＶノードへ至る探索現在時点での
最小コストを意味し、これをノードコストという。 ＳＰ（ｍ）　　：永久ノードｌのツートコトスで永久ノ
ードコストという。 又、コストとは前に定義したように、距離、所要時間等
を含めた最短経路の評価値であり、そのコストが最小と
なる経路が最短経路となる。したがって、コストは探索
枝を展開するためのパラメータであり、そのノードまで
のコトスや、探索枝のコスト、経路のコストという概念
が存在する。 Ｔ（ｖ）　：　ｖノードからＴノードへ至る探索現在時
点の最小コストを意味し、これをノードコストという。 ＳＴ（ｍ）　　：永久ノードｍのツートコトスで永久ノ
ードコストという。 Ｒ（ｊ）：探索現在時点での接続ノードｊの存在する経
路（現在位置から目的位置に至る経路）のコストを意味
し、これを経路コストという。 Ｕ：探索現在時点での経路コス）ＲＵ）の最小な接続ノ
ードの番号 Ｓ探索、Ｔ探索にかかわらず、ＳノードからＴノードへ
向かう経路上において、Ｔノード側を前方といい、その
経路上の２つのノードにおいて、Ｔノードに近いノード
を他のノードに対して前方ノードという。又、逆に、Ｓ
ノード側を後方といい、Ｓノードに近いノードを他のノ
ードに対して後方ノードという。 Ｐ（ｉ）　：探索現在時点において、活性ノードｉに接
続される最短経路上の最近接の後方永久ノードの番号 Ｑ（ｉ）　　：探索現在時点において、活性ノード１に
接続される最短経路上の最近接の前方永久ノードの番号 α：探索現在時点におけるＳ探索の活性ノードのノード
コストの中の最小値をいい、この値を探索コストという
。この探索コストはＳ探索において活性ノードのなかか
ら永久ノードを選択するパラメータとなる。 β：探索現在時点におけるＴ探索の活性ノードのノード
コストの中の最小値をいい、この値を探索コストという
。この探索コストはＴ探索において活性ノードのなかか
ら永久ノードを選択するパラメータとなる。 ｄｍ、　ｉ　：永久ノードｍと活性ノード１間の探索枝
のコストを意味し、これを探索枝コストという。 ａ、ｂ：楕円の長径、短径、ａ＝　Ｃ／　１−　Ｐ’、
　ｂ＝　ａＰＣ：楕円の中心と焦点間の距離 ＣＩＩ　ＣＩ　Ｃ−：閾値、Ｏ＜　ＣＩ＜　Ｃ２＜　Ｃ
３Ｆ１−、Ｆｉ、Ｆｓ、Ｆ４：定数、１　＞Ｆ＋＞Ｆｚ
＞Ｕｓ＞Ｐａ＞Ｆ：楕円の長径と短径の比Ｉ’＝ｂ／ａ
Ｃ≦Ｃ１ならｐ−ｐ。 ＣＩ＜Ｃ≦Ｃ３なら　Ｐ　＝　Ｐ　２ Ｃｉ＜Ｃ≦Ｃ５なら　Ｉ？＝　Ｆ。 Ｃ’ｓ＜ＣならＩ’＝　Ｆ。 ×。、ｙｏ：楕円の中心座標 θ：楕円の傾き　θ＝　５ｉｎ ｘｌ＋ｙｌ’活性ノードｉの座標 ｆ（ｘ、ｙ）：楕円の内外判定関数 （（ＹＴ＠−ＹＳ、）／２Ｃ ｆ　（Ｘ、　ｙ＞≧０なら（Ｘ、　ｙ）は楕円の内側に
ある。 ｆ　（Ｘ、　ｙ）　＜　Ｏなら（Ｘ、　ｙ）は楕円の外
側にある。 Ａ’５（Ｖ）：後方ノードＰ（ｖ）とノードＶ間の探索
枝の道路等級をいい、大きい程等級が上である。 ＡＴ（ｖ）　：ノードＶと前方ノード０（ｖ）間の探索
枝の道路等級をいい、大きい程等級が上である。 次に、第６図のフローチャートに従って、探索手順を説
明する。 ステップ３００では探索データファイルの初期化が実行
される。即ち、ＳノードとＴノードが最初の活性ノード
として探索データファイルの中のノードファイルに展開
され、それらのノードのノードコストは、５（ｉ）＝０
゜ Ｔ（ｉ）＝Ｏに、後方ノード及び前方ノードは、Ｉ’（
ｉ）＝Ｓ、Ω（ｉ）　−Ｔに設定される。 次に、ステップ３０２にて、ＳノードとＴノードとの座
標から、上記した定義に従って楕円の各パラメータが演
算され、楕円関数が決定される。 次に、ステップ３０４で探索コストα、βがＯに初期設
定される。即ち、現時点では活性ノードのノードコスト
の最小値はＯである。 次に、ステップ３０６へ移行して、Ｓ永久ノード数はＴ
永久ノード数以下か否かが判定される。そして、Ｓ永久
ノード数がＴ永久ノード数以下の場合にはステップ３０
８〜３２２のＳ探索が実行され、そうでない場合にはス
テップ３３２〜３４６のＴノード探索が実行される。こ
のステップ３０６の処理により等ノード探索が実行され
る。即ち、探索現在時点において、Ｓ探索とＴ探索とに
おいて永久ノードの数が均衡するように、交互に永久ノ
ードが展開される。 Ｓ探索の場合には、ステップ３０８にてＳ探索の全活性
ノードの中からノードコスト５（１）が探索コトスα以
上で最小値をとるノードが選択され、ぞのノードが永久
ノードｍとして選択される。 次に、ステップ３１０へ移行して、その永久ノードｍは
楕円内に存在するか否かが判定され、存在しない場合に
は、その永久ノードｍは捨て去られ、ステップ３０６へ
戻り、次の探索処理が実行される。 又、永久ノードｍが楕円内に存在すると判定された場合
には、ステップ３１２へ移行して、その永久ノードｍの
後方探索枝の等級ｆＳ　（ｍ）がさらに１つ後方の後方
探索枝の等級１ｓ（１’（ｍ））−ｎ以上か否かが判定
される。そして、判定結果がＮＯの場合にはその永久ノ
ードｍは捨て去られ、ステップ３０６へ戻り、次の探索
処理が実行される。即ち、１つ後方の後方探索枝の等級
よりｎ等級を越える下位等級の探索枝は選択されないこ
とを意味しており、探索枝の選択が制限されたことにな
る。このステップにより縮退探索が行われる。 ステップ３１４は、ステップ３１０の楕円探索条件とス
テップ３１２の縮退探索条件とを満たす場合に実行され
、その選択されたノードは有効な永久ノードｍとし、そ
のノードコストＳ　（ｍ）は永久ノ・−トコストＳＰ（
ｍ）としてノードファイルに登録される。 次に、ステップ３１６でその永久ノードｍに接続される
探索枝を地図データベースから検索し、次に接続される
全ての活性ノードｋが決定される。 そして、次のステップ３１８で活性ノードｋがカレント
ファイルに初めて展開される場合には、その永久ノード
コストに展開された探索枝コストを加えた値、即ち、Ｓ
Ｐ　（ｍ）＋ｄｍ、　ｋ　　が活性ノードにのノードコ
ストＳ　（ｋ）として登録される。又、展開された活性
ノードｋが既にカレントファイルに展開されている活性
ノードである場合には、登録されているノードコストＳ
　（ｋ）とＳＰ　（０１）　＋ｄｍ、　ｋ　　との大き
さが比較され、ＳＰ　（ｍ＞　＋ｄｍ、　ｋの方が小さ
い場合には活性ノードにへ至るよりコストの低い経路が
発見されたことを意味しており、その場合には、その活
性ノードにのノードコストＳ　（ｋ）はその値ＳＰ　（
ｍ）→ｄｍ、　ｋに再登録される。又、その活性ノード
にの後方ノードＩ’（ｋ）をｍに再登録する。以上の処
理が新しく展開された全ての活性ノードｋについて実行
される。 次に、ステップ３２２では、新しく展開された全活性ノ
ードにのうぢＴ探索の活性ノード又は永久ノードに該当
するものが有るか否かが判定される。 なければ、接続ノードは発生しなかったことを、意味し
ており、ステップ３０６に戻り、次の探索処理が実行さ
れる。 又、ステップ３０６でＳ永久ノード数はＴ永久ノード数
以下でないと判断された場合には、ステップ３３２〜ス
テツプ３４６のＴ探索がＳ探索と全く同様に実行される
。 ところで、上記の処理内容を図示すると、￥Ｊ１１図に
示すようになる。 第１回目の実行サイクルでは、ステップ３０６の判断が
ＹＩＥＳとなり、ステップ３０８でＳノードが永久ノー
ドとして選択され、ステップ３１０．３１２の判定がＹ
ＩＥＳとなり、ステップ３１４で永久ノードコスト５Ｐ
（Ｓ）＝Ｏが確定される。 尚、Ｊｓ＜Ｓ）＝　６ｓ（１’（Ｓ））＝ｎに初期設定
されているので、最初の実行サイクルでは、ステップ３
１０の判定は当然Ｙ［ｉＳとなる。第１１図（ａ）で示
すように、ステップ３１６でノードＳに接続される探索
枝が選択され、次に展開される活性ノードに１〜に４が
決定される。そして、ステップ３１８では既に展開され
ている活性ノードは存在しないので、新しい４つの活性
ノードについてノードコストＳ　（ｋ）が求められる。 永久ノードコストＳＰ　（Ｓ）はＯであるのでノードコ
スト５（ｋ）は探索枝コストｄｓ、　ｋに等しくなる、
。 又、各活性ノードにの後方ノードＰ　（ｋ）はＳノード
に登録される。又、ステップ３２０で探索コストαはそ
の時の全ソードコスト５（ｉ）の中の最小値に更新され
ろ。 又、ステップ３２２で、ｉｓ　ｉ　ｏ図（ｂ）に示すよ
うに、活性ノードにのうちで、Ｔ探索の活性ノード、即
ち、ノードＴ（現時点ではＴノードしか展開されていな
い）に一致するものがあれば、そのノード、例えばノー
ドに、は接続ノードとされ、一応、経路が構成されたの
であるから、ステップ３２４以下でその経路が本当に最
短経路になるか否かの判定が行われる。その処理につい
ては後述する。 １回目の実行サイクルで接続ノードが発生しない場合に
ついて説明を続ける。 第２回目の実行サイクルではＴ探索となり、同様な処理
により、ステップ３４６の実行終了時には探索状態は、
第１１図（Ｃ）に示すようになる。 第３回目の実行サイクルはＳ探索となり、ステップ３０
８で現時点での活性ノードｉ（即ち、ｋ、〜に４）のう
ちで、ノードコスト５（ｉ）が探索コストα以上で最小
値をとるノード、例えば、ノードに、が選択される。そ
のノードが楕円内に存在すれば、ｉｓ　（Ｓ）がｎに初
期設定されていることから、探索枝し、は等級に関係な
く選択されるので、ステップ３１４にてノードに、が永
久ノードｍ１として登録され、そのノードコストＳ（ｍ
、）　　も永久ノードコストＳＰ＜ｍＩ）としてノード
ファイルに登録される。次に、ステップ３１６にて、第
１１図（ｄ）に示すように、永久ノード１ＴＩＩに接続
される活性ノードＬ、ｋａが展開される。このうち、活
性ノードに、は新規な活性ノードであるので、ステップ
３１８にて探索枝り、の探索枝コストｄｍ、ｋｓ十永久
ノードｍ、の永久ノードコス）ＳＰ（ｍＩ）が活性ノー
ドに、のノードコスト５（ｋｓ）　としてカレントファ
イルに登録される。 一方、活性ノードに２は既に展開された既活性ノードで
あるので、その時の既登録のノードコスト５（ｋｚ＞よ
り、新しく求められた探索枝Ｌ１゜の探索枝コスト’　
ｍｌ　Ｔ　’　Ｉ　Ｏ＋永久ノードｆｆ１１の永久ノー
ドコス）ＳＰ（ｍＩ）の方が小さい場合には、ノードコ
スト５（ｋｉ）はその値にＰ１替えられる。又、その活
性ノードに２の後方ノードｉ’（ｋ、）　はノードＳか
らノードｌ、に書替えられる。即ち、ノードＳから活性
ノードに２へ行くには、探索枝１，２を通るより、永久
ノード１１＋１と探索枝１．１゜を通る経路の方がコス
トが低いことになり、その経路が最短経路となる。その
時の探索ネットワークは第１１図（ｅ）に示すようにな
り、ステップ３２０でその状態での全活性ノード（Ｊ、
　ｋｓ、　Ｌ、　ｋｓ）のうらで、ノードコストＳ　（
ｋ）の最小値、例えば、５（ｋｓ）が探索コストαの新
しい値となる。 このようにして、多数回の探索が実行されていくと、第
１１図（「）に示すようになり、楕円内で且つ探索枝の
等級が１つ後方又は前方の探索枝の等級よりｎ等級を越
える下位等級の選択枝は捨て去られた状態で永久ノード
が次々と生成される。 そして、ステップ３２２又はステップ３４６の判定がＹ
ＥＳとなると、接続ノードが発生されたことになる。 次に、接続ノードが発生した後の最短経路探索手順につ
いて説明する。 初めて接続ノードが発生した状態では、第１１図（匂に
示ずように、その接続ノードはＳ探索及びＴ探索におい
ても、活性ノードである。従って、ステップ３２４でそ
の接続ノード」ＩにおけるノードＳに対するノードコス
ト５（Ｊｌ）とノート′Ｔに対するノードコストＴ（Ｊ
ｌ）との和で経路コストＲ（Ｌ）が演算される。そして
、最初の実行サイクルでのステップ３２６での最小値Ｉ
ＪＲは、その経路コス１−Ｒ（Ｊｌ）となり、ステップ
３２８にて、その最小値ＭＲが探索コストα十探索コス
トβ以下か否かが判定される。最初に現れた接続ノード
Ｊ＋で条件が設立する場合は等号に限られ、ノードコス
）Ｓ（」＋）は探索コストαにノードコストＴ（Ｊｌ）
は探索コストβに等しくなる。このことは、次回と次次
回の探索で必ず接続ノード」１はＳ探索及びＴ探索で永
久ノードとされる。即ち、この経路はＳ探索とＴ探索が
永久ノードで接続された最初の経路となり、最小コスト
経路となる。したがって、ステップ３３０でその接続ノ
ード」、が存在する経路が最小コスト経路と決定される
。 一方、ステップ３２８の判定がＮＯの場合には、その後
の探索において、接続ノードｊ、が永久ノードとされる
前に他の経路で接続ノードが発生されたり、その接続ノ
ードＪ、の後方ノードＩ’（ｊＩ）や前方ノー１’ｏ（
ｊＩ）が古き換えられる、即ち、最小コスト経路が変更
される可能性がある。従って、ステップ３０６へ移行し
て次の探索を継続する必要がある。 又、探索が進行するに連れ、接続ノードが発生する毎に
、ステップ３２４以下が実行される。ステップ３２４で
は、発生した接続ノード」に対して経路コストＲ（」）
が演算される。そして、ステップ３２６で今までに発生
している全接続ノードＪのうちで、経路コストＲ（」）
が最小となるものをノードＵとし、最小値ＭＲが選択さ
れる。尚、ある経路に注目したとき、その経路上の最初
の接続ノード」は必ずＳ探索及びＴ探索の活性ノードで
あり、その後、探索が進行するに連れ、その接続ノード
はＳ探索の永久ノード又はＴ探索の永久ノードとなり、
最後に両探索での永久ノードとなる。この永久ノードに
なった時、必ず、コストＲ（」）＜α＋βが満たされる
。しかし、コストＲ（ｊ）＜α＋βの条件を満たしても
、そのノードは両探索での永久ノードとは言えないが、
その後の探索で初めての接続ノードが現れる経路の経路
コストは必ず現在のα＋βを越えるため、それらの経路
からは最小コスト経路は発見されない。したがって、既
に接続されたＲ（ｊ）＜α＋βを６４たず経路の中に最
小コスト経路が存在する。したがって、全接続ノード」
に対して経路コスｔ−Ｒ（ｊ）の最小値ＭＲが最初にＭ
Ｒ≦α＋βを満たす経路が最小コスト経路、即ち、最短
経路となる。 上記の最短経路上の任意のノードＶはＳ探索において後
方ノードＰ（Ｖ）が、又、Ｔ探索において前方ノード０
（ｖ）が明らかにされているので、接続ノードＵから順
にＳ探索に対して１つづつ後方ノードをＳノードまで探
り、Ｔ探索に対して１つづつ前方ノードをＴノードまで
探ることによって最短経路上の全ノードを知ることがで
きる。 次に、目的位置が変わらず現在位置が変化した時の再探
索の処理手順を第７図を参照して説明する。 ステップ４００で新しい現在位置に対応するＳノードが
探索結果データのＴ永久ノードに一致するか否かが判定
される。一致すればそのＳノードは前回のＴ探索領域に
存在することになり、ステップ４３４へ移行して、探索
結果データに基づいて前方ノード０（ｖ）を順次たどる
ことによりＴノードに至る最短経路を求めることができ
る。 又、そのＳノードがＴ探索領域に存在しない場合には、
ステップ４０１以下の処理が実行される。 ステップ４０１でステップ３００と同様な初期設定が行
われる。但し、目的位置からの探索結果データは消去さ
れない。又、ステップ４０２で新しい現在位置と不変な
目的位置とを焦点とする楕円関数が演算され、ステップ
４０４で探索コストαが０に初期設定される。又、探索
コストβは前回のＴ探索の最終値に保存される。そして
、ステップ４０６〜４２０のＳ探索が実行される。この
Ｓ探索は第６図のステップ３０８〜３２２のＳ探索と同
様である。 但し、ステップ４２０ではＳ探索による活性ノードｋが
ノードファイルに探索結果データとして記憶されている
Ｔ永久ノードか否かが判定される。 判定結果がＮＯの場合には、ステップ４０６へ戻りＳ探
索が継続される。 又、判定結果がＹＥＳの場合には、ステップ４２２へ移
行して、ステップ４２２〜４２Ｇが実行される。 この処理はステップ３２４〜３２８と同様で５ある。そ
して、ステップ４２６の判定がＹＩＥＳとなると、ステ
ップ４２Ｇで、ステップ４２６の条件を満たす経路の発
生回数が計数される。そして、次のステップ４３０でそ
の発生回数Ｚが所定回数Ｗ以上か否かが判定され、所定
回数以上となるまで、ステップ４０６へ戻りＳ探索が実
行される。即ち、接続ノードｊはＴ永久ノードであるの
で、ノードコストＴ（ｊ）は探索コストβより小さい。 このため、最初にステップ４２６の条件を満たす接続ノ
ードＪであっても、ノードコストＳ　（ｊ）は最小値即
ち探索コストαに等しいとは限らない。したがって、そ
の後のＳ探索にｉｉいて接続ノードＪが発生し経路コト
スＲ（ｊ）が】１小値をとる経路が発生ずる可能性があ
る。そこで、所定の回数Ｗまで、ステップ４２６の条件
を？１ｊ４だす経路を検出し、その経路の中で経路コス
）Ｒ（」）が最小値をとる経路を最短経路とする必要が
ある。即ち、所定回数Ｗ以内に最短経路の接続が完了す
ると見做され、所定回数Ｗを越えてＳ探索を継続しても
、最短経路が発見される可能性は少ないといえる。 上記実施例ではステップ４２０のＳ探索の活性ノードが
Ｔ探索の永久ノードと一致するか否かを判定したが、探
索結果データをＴ探索の活性ノードを含めた探索最終状
態のデータとし、Ｓ探索の活性ノードがＴ探索の永久ノ
ード又は活性ノードと一致する接続ノードが検出された
後は、ステップ４２６の条件が満たされるまで、Ｔ探索
とＳ探索とを同時に実行するようにすれば、ステップ４
２８とステップ４３０は不要となり、ステップ４２６が
初めて満たされた時に、最短経路が検出されることにな
る。但し、Ｔ探索は探索コストβから継続する探索とな
る。 又、第５図のステップ２０８における双方向等ノード探
索は、楕円探索又は、縮退探索を組み合わせた探索を行
った場合、ネットワークの限定又は縮退により現在位置
と目的位置とを結ぶ経路を消失し、最短経路を求められ
ない時に、補間的に用いられる。等ノード探索だけなら
、範囲を限定しないので最短経路を失うことはなく、必
ず最短経路を求めるこきができる。 双方向等ノード探索は道路網に粗密がある時、双方向等
コスト探索と比べて探索時間が短縮される。これは双方
向等ノード探索を行った時の探索ノード数は、双方向等
コスト探索のそれに比べて少なくなることによる。その
証明は、Ｓ探索側のノード密度とＴ探索側のそれを、そ
れぞれの探索範囲内で一定であるとする時、ノード数は
探索面’ｈＩ　Ｘノード密度であるとして求め、双方向
等ノード探索を行った時の探索ノード数と双方向等コス
ト探索のそれと差を取り、シュワルツの不等式を用いて
、その差がいつも負となることから示される。 上記実施例装置による探索結果を次に示す。所与の領域
の街路ノード数が約２８００、リンク数が約４２００の
地図データベース上で複数のＳノードとＴノード対を選
定し、探索を実行した。従来法の一方向探索のラベル確
定法による探索結果に比べて双方同等ノード探索は最大
約５倍、更に楕円探索を加えると最大約５０倍の時間短
縮が得られた。更に、縮退探索を行うと楕円探索の更に
数倍の時間短縮となった。 ２回目以降の探索においては、初回の探索結果データを
利用しない探索に比べて２倍以上の時間短縮が得られた
。 尚、探索１１ａ囲の限定は、楕円を用いる以外に現在位
置と目的位置とを中に含む矩形、或いは現在位置と目的
位置を焦点とする二つの放物線で囲まれる領域でも良い
。そして、現在位置と目的位：ｄとの距離の長短に応じ
、これらの形状をパラメトリックに、１．ｌｊ　ｕｌ＋
しても良い。 又、ネットワークの縮退は、道路等級を設定する以外に
、リンク属性値である距離、旅行時間にペナルティコス
トを付けることでも良い。例えば、右、左折に対しペナ
ルティを付け、距離、旅行時間に加えることにより、右
、左折方向への経路は通り難くなり、直進する方向へ探
索が進み、縮退を行うと同様な効果が得られる。 又、本発明は上記のような道路地図での最短経路探索の
他、任意のネットワークにおいて、任意の評価値が最小
となる経路を求める全ての装置にも応用できる。

【発明の効果】

第１発明は、双方向探ｚ（ミ手段による双方向探索過程
において、各方向から順次探索される探索ノード又は探
索枝の数が略均衡するように探索順序を制御しているの
で、ノード又は枝の密度が異なる経路データにおいて、
最短経路が発見されるまでに展開されるノード又は枝の
数を最小とすることができる。したがって、最短経路探
索時間を短くすることができる。 又、第２発明は、双方向探索過程において探索される探
索ノード又は探索枝を、探索開始位置及び探索終了位置
を焦点付近としそれらの両位置を結ぶ線分を長軸とする
楕円又はその楕円に近似される形状の内部領域に存在す
るものに限定するように探索領域を制限しているので、
最短経路の存在する確率の高い領域が探索領域となり、
最短経路の存在する確率が低い領域は探索領域から除外
されているため、極めて効率の高い探索が可能となり最
短経路探索時間が短縮される。 又、第３発明は、双方向探索過程において探索される探
索ノード又は探索枝を、枝の優先度を示す等級データに
基づいて制限しているので、経路探索が等級の高い経路
に沿って実行される可能性が高く、等級の高い枝に接続
された等級の低い枝への経路探索が防止されるため、極
めて効率の高い探索が可能となり最短経路探索時間が短
縮される。 又、第４発明は、前回の探索に対して探索終了位置が同
一の場合において、その探索開始位置がその最短経路上
又はその探索領域内に存在するときには、既に求められ
ている探索終了位置からの探索結果データによって探索
開始位置から探索終了位置までの最短経路を決定し、探
索開始位置がその最短経路上又はその探索領域内に存在
しないときには、探索開始位置からのみ順次ノード又は
枝を探索して最短経路を探索し、その片方向探索からの
探索ノード又は探索枝が探索結果データに含まれる探索
ノード又は探索枝に接続された経路の中から、最短経路
を決定するようにしているので、目的位置が不変な場合
の２回目以後の経路探索を効率良く、したがって、最短
経路探索時間を短縮することができる。

【図面の簡単な説明】

第１図は本発明の構成を示したブロックダイヤグラム、
第２図は本発明の具体的な一実施例に係る車載ナビゲー
ション装置を示した構成図、第３図乃至第７図は同実施
例に係る装置の処理手順を示したフローチャート、第８
図乃至第１１図は探索手順を示した説明図である。 １０　車載ナビゲーション装δ ２０−コンピュータ 活性ノード　ｍ

Claims (4)

【特許請求の範囲】
1. （１）ノード及び枝で構成される経路データを記憶した
   経路データ記憶手段と、 探索開始位置及び探索終了位置を入力する位置入力手段
   と、 探索開始位置及び探索終了位置の双方向から順次ノード
   又は枝を探索して最短経路を探索する双方向探索手段と
   、 双方向探索手段による双方向探索過程において、各方向
   から順次探索される探索ノード又は探索枝の数が略均衡
   するように探索順序を制御する探索順序制御手段と、 双方向探索手段による双方向探索過程において双方向か
   らの探索ノード又は探索枝が接続された経路の中から、
   探索開始位置から探索終了位置に至る最短経路を決定す
   る最短経路決定手段と、その最短経路を表示する表示手
   段と を有する最短経路探索装置。
2. （２）ノード及び枝で構成される経路データを記憶した
   経路データ記憶手段と、 探索開始位置及び探索終了位置を入力する位置入力手役
   と、 探索開始位置及び探索終了位置の双方向から順次ノード
   又は枝を探索して最短経路を探索する双方向探索手段と
   、 双方向探索手役による双方向探索過程において探索され
   る探索ノード又は探索枝を、探索開始位置及び探索終了
   位置を焦点付近としそれらの両位置を結ぶ線分を長軸と
   する楕円又はその楕円に近似される形状の内部領域に存
   在するものに限定する探索領域制限手段と、 双方向探索手段による双方向探索過程において双方向か
   らの探索ノード又は探索枝が接続された経路の中から、
   探索開始位置から探索終了位置に至る最短経路を決定す
   る最短経路決定手段と、その最短経路を表示する表示手
   段と を有する最短経路探索装置。
3. （３）ノード及び枝の情報及び枝の優先度を示す等級デ
   ータとで構成される経路データを記憶した経路データ記
   憶手段と、 探索開始位置及び探索終了位置を入力する位置入力手段
   と、 探索開始位置及び探索終了位置の双方向から順次ノード
   又は枝を探索して最短経路を探索する双方向探索手段と
   、 双方向探索手段による双方向探索過程において探索され
   る探索ノード又は探索枝を、前記経路データに含まれる
   枝の等級データにより制限する縮退探索手段と、 双方向探索手段による双方向探索過程において双方向か
   らの探索ノード又は探索枝が接続された経路の中から、
   探索開始位置から探索終了位置に至る最短経路を決定す
   る最短経路決定手段と、その最短経路を表示する表示手
   段と を有する最短経路探索装置。
4. （４）前回の探索に対して探索終了位置が同一の場合に
   は、探索開始位置が既に決定されている最短経路上又は
   探索終了位置からの探索領域内に存在するか否かを判定
   する探索開始位置判定手段と、その探索開始位置がその
   最短経路上又はその探索領域内に存在する場合には、既
   に求められている探索終了位置からの探索結果データに
   よって探索開始位置から探索終了位置までの最短経路を
   決定する第２最短経路決定手段と、 探索開始位置がその最短経路上又はその探索領域内に存
   在しない場合には、探索開始位置からのみ順次ノード又
   は枝を探索して最短経路を探索する片方向探索手段と、 その片方向探索からの探索ノード又は探索枝が前記探索
   結果データに含まれる探索ノード又は探索枝に接続され
   た経路の中から、探索開始位置から探索終了位置へ至る
   最短経路を決定する第３最短経路決定手段と を更に有することを特徴とする特許請求の範囲第１項乃
   至第３項記載の最短経路探索装置。