JPH08178682A - 経路探索方法及び経路探索装置 - Google Patents

Abstract

(57)【要約】 【目的】リンクとノードからなる経路ネットワークデー
タ上で、現在地と目的地とを結ぶ最短経路をより短時間
で探索する。 【構成】想定される経路コストを複数範囲に区分して、
各区分に対応して、探索中のノードを記入する欄を有す
る複数の探索用ワークメモリを予め用意しておき、経路
の探索に連れて、探索用ワークメモリの中に格納されて
いるノードを、より経路コストの大きな探索用ワークメ
モリに移しかえていく。目的地までの経路が少なくとも
１本探索できた時点で、当該目的地までの経路コスト
が、空になったワークメモリに対応する経路コスト未満
のものであれば、これ以上探索をすることなく、当該目
的地に至る今まで探索してきた経路を最短経路と決定す
る。 【効果】探索する経路の数を抑えることができ、経路探
索に要する時間を短縮することができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、現在地と目的地とを結
ぶ最短経路を計算する機能を備えた経路探索装置に関す
るものである。

【０００２】

【従来の技術】従来から、現在地と目的地とを結ぶ最短
経路を短時間で計算する経路探索装置が開発されてい
る。例えば、不案内な土地における車両での走行を支援
するため、検出された車両の現在地をその周辺の道路地
図とともに表示するようにしたナビゲーション装置が、
車両に搭載されたり、地上の交通情報センターに設置さ
れたりして、用いられている。

【０００３】このようなナビゲーション装置では、運転
者の負担を軽減するため、目的地まで車両を誘導するた
めの経路計算機能を備えているものがある（例えば柴
田、天目、下浦「ストカスティック経路探索アルゴリズ
ムの開発」住友電気第１４３号, p.165,1993年９月）。
前記の経路計算を実行するためには、ネットワークメモ
リに記憶された経路ネットワークデータを読み出して作
業領域に移し、作業領域においてダイクストラ法又はポ
テンシャル法に基づいて経路計算を行う。

【０００４】このダイクストラ法又はポテンシャル法と
は、現在地から目的地までの最短経路を計算する場合
に、目的地（現在地）に最も近いリンク又はノード（以
下「リンク」で代表する）を探索開始リンクとし、目的
地（現在地）に最も近いリンクを探索終了リンクとし、
探索開始リンクから探索終了リンクまでを含む経路ネッ
トワークデータを取得し、この道路ネットワーク内にお
ける探索開始リンクと探索終了リンクの間の最短経路を
計算する方法である。このためには、探索開始リンクか
ら探索終了リンクに至るコスト（道路の実長と道路種別
（高速道路又は国道などの分類）に対応した車両の標準
速度とから得られる走行時間のこと）を順次加算してリ
ンクのツリーを構成していき、探索終了リンクに到達す
る最もコストの少ない経路のみを選択する。そして、こ
のようにして求められた経路が最短経路として表示され
る。そのため、この表示されている最短経路に沿って走
行すれば、確実に目的地に到達することができる。

【０００５】前記ダイクストラ法及びポテンシャル法に
ついて、さらに詳細に説明する。ダイクストラ法は、探
索開始リンクから始まるリンクのツリーを構成していく
とき、あるリンクから複数のリンクに枝分かれする場合
に、各枝のリンクの経路コスト（探索開始リンクから当
該リンクに至るコストの総和のこと）の大小を比較し
て、経路コストの小さい順に並べ変え、経路コストの小
さいリンクからさらに探索を続けていくという方法をと
る。そして、最初に探索終了リンクに到達すれば、その
時点で、探索終了リンクに到達する最もコストの少ない
経路を決定する。経路コストの小さいリンクから順に探
索を続けていくので、真先に探索終了リンクに到達した
経路がそのまま最短経路となるからである。

【０００６】一方、ポテンシャル法では、あるリンクか
ら複数のリンクに枝分かれする場合に、各枝のリンクの
経路コストの大小の比較をせずに、すべてのリンクを同
等に扱い、各枝のリンクからさらに探索を続けていくと
いう方法をとる。したがって、最初に探索終了リンクに
到達しても、その時点では、他の経路を通って探索終了
リンクに到達する可能性が残されているため、道路ネッ
トワークにあるすべてのリンクを探索し終わった時点で
初めて、探索終了リンクに到達する最もコストの少ない
経路を決定する。

【０００７】ダイクストラ法では、真先に探索終了リン
クに到達した経路がそのまま最短経路となるので探索回
数は少ないが、探索のたびに経路コストの小さい順にリ
ンクを並べ変えなければならないので、それに計算時間
を費やす。ポテンシャル法では、道路ネットワークにあ
るすべてのリンクを探索しなければならないので、探索
回数は多いが、リンクを並べ変えるという処理は不要で
ある。

【０００８】実際には、リンク数が少ないときにはポテ
ンシャル法が時間の点で有利、リンク数が多いときには
ダイクストラ法が有利とされている。

【０００９】

【発明が解決しようとする課題】ところで、この最短経
路の計算において、ダイクストラ法、ポテンシャル法の
いずれを採用するにしても、計算時間の短縮が望まれて
いる。例えばナビゲーション装置においては、本件特許
出願人の製品ではポテンシャル法が使用されているが、
それでも大阪から京都までの道路ネットワークの走査し
たリンク数は、のべ約１万７千本にのぼり、経路ネット
ワークデータの読み込み時間や表示データの作成時間等
を除いた正味の計算時間は約５．７秒かかっている。東
京から広島までの道路ネットワークの走査したリンク数
は、のべ約５万本になり、正味の計算時間は約１５秒と
なる。

【００１０】そこで、本発明の目的は、現在地と目的地
とを結ぶ最短経路を計算する場合に、より短時間で最短
経路を見つけ出すことのできる経路探索方法及び経路探
索装置を実現することである。

【００１１】

【課題を解決するための手段及び作用】前記目的を達成
するための請求項１にかかる経路探索方法では、経路コ
ストを複数範囲に区分して、各区分に対応して、探索中
のリンク又はノードを記入する欄を有する複数の探索用
ワークメモリを用意する。従来のダイクストラ法又はポ
テンシャル法では、用意する探索用ワークメモリ（ピボ
ットテーブルともいう）は単数であったのに対して、経
路コストの区分に応じて複数であるところに１つの特徴
がある。

【００１２】まず、探索開始リンク又はノードを、最も
経路コストの低い区分の探索用ワークメモリに格納す
る。そして、探索用ワークメモリの中に格納されている
１つのリンク又はノードに注目し、当該リンク又はノー
ドに基づいて経路探索を続けていき、それに接続される
リンク又はノードの経路コストを計算する。この計算結
果は、通常の方法どおり経路探索用のリザルトテーブル
に書き込んでいく。さらに、それぞれ該当する区分の探
索用ワークメモリに、接続されたリンク又はノードを書
入れる。さらに探索済の当該リンク又はノードを探索用
ワークメモリから消去するという手順を、探索用ワーク
メモリの中に格納されているリンク又はノードについ
て、繰り返していく。

【００１３】格納したリンク又はノードが空になった探
索用ワークメモリがあり、かつ、探索済のリンク又はノ
ードの中に探索終了リンク又は探索終了ノードが含まれ
ていれば、リンク又はノードのコストがすべて負でない
という前提に立てば、それ以後に探索されるリンク又は
ノードの経路コストは、すべて当該空になった探索用ワ
ークメモリに対応する経路コスト以上のものとなる。し
たがって、これ以上探索をすることなく、当該探索終了
リンク又はノードに至る今まで探索してきた経路を最短
経路として選択することが可能となる。

【００１４】探索済のリンク又はノードの中に探索終了
リンク又は探索終了ノードが含まれているかどうか判定
する方法の１つは、リザルトテーブル上で探索終了リン
ク又はノードを見て、それまでの経路が少なくとも１本
探索済みであり、探索終了リンク又はノードの経路コス
トが、当該空になった探索用ワークメモリに対応する経
路コスト未満のものであるかどうかを判定することであ
る。

【００１５】請求項２記載の経路探索方法では、該当す
る区分の探索用ワークメモリに接続されるリンク又はノ
ードを書入れた場合に、経路コストに応じた並べ替えは
しない。従来のダイクストラ法では、経路コストに応じ
た並べ替えをし、最も経路コストの低いリンク又はノー
ドから順に次の探索をしていくが、本発明では、経路コ
ストの区分に応じた複数の探索用ワークメモリを用意し
ているので、経路コストに応じた並べ替えをする必要が
ない。

【００１６】請求項３記載の経路探索方法では、探索の
順番として、リンク又はノードを少なくとも１つ格納し
ている最も経路コストの低い区分の探索用ワークメモリ
の中に格納されているものの中から探索することにして
いる。従来のポテンシャル法では、経路コストとかかわ
りなく、ピボットテーブルの中に格納されている全ての
リンク又はノードを対象として探索を進めていくが、本
発明では、経路コストの区分に応じた複数の探索用ワー
クメモリを用意しているので、最も経路コストの低い区
分の探索用ワークメモリの中に格納されているものの中
から探索する。したがって、経路コストの大きなリンク
又はノードを必要もないのにやみくもに探索して、時間
を消費するというおそれがなくなる。

【００１７】なお、探索するリンク又はノードを選定す
る順位は、当該探索用ワークメモリの中ではランダムで
もよいが、先入れ先出し規則、後入れ先出し規則、これ
らの２つの規則を混合させたtwo-way sequence規則、あ
るいは常に経路コストが最小のリンク又はノードを取り
出す最良優先規則のいずれかに従うこととしてもよい。

【００１８】請求項４記載の経路探索方法では、前記探
索用ワークメモリの、経路コストを区分する範囲は一定
である。このようにすれば、探索開始位置のリンク又は
ノードからの経路コストが小さな経路も大きな経路も均
等に効率よく探索することができる。請求項５記載の経
路探索方法では、前記探索用ワークメモリの、経路コス
トを区分する範囲は経路コストに応じて漸増している。

【００１９】このようにすれば、探索開始位置のリンク
又はノードからの経路コストが比較的小さい経路を特に
効率よく短時間で探索することができる。請求項６記載
の経路探索方法では、前記探索用ワークメモリの、経路
コストを区分する範囲は経路コストに応じて漸減してい
る。このようにすれば、探索開始位置のリンク又はノー
ドからの経路コストが比較的大きな経路を特に効率よく
短時間で探索することができる。

【００２０】請求項７記載の経路探索方法は、請求項１
記載の発明と同一発明を装置形式で表現したものであ
る。

【００２１】

【実施例】以下では、本発明の実施例を、添付図面を参
照して詳細に説明する。図３は、本発明の経路探索装置
が適用されたナビゲーション装置を示すブロック図であ
る。このナビゲーション装置１は、車両に搭載されて車
両の走行を支援するために用いられるものである。この
ナビゲーション装置本体１には、予め経路ネットワーク
データを格納したディスクＤから記憶データを読み出す
ＣＤドライブ２と、ＧＰＳ受信機５と、車速センサ６
と、地磁気センサやジャイロ等の方位センサ８と、地図
や車両の表示を行うディスプレィ３と、さらに初期デー
タ等を設定するためのジョイスティックリモコンキー
（以下「リモコンキー」という）４等とが接続される。

【００２２】また、ナビゲーション装置本体１内部に
は、所定範囲の経路ネットワークデータの読み出し、経
路ネットワークデータを利用した最短経路の計算、車両
の誘導をするための表示用データの作成、及びＧＰＳ受
信機５の制御や、車速センサ６、方位センサ８のデータ
処理等の種々の処理を行うコントローラ１６を有する。
本コントローラ１６は、本装置の制御を統制するＣＰＵ
１６１（中央処理装置）と、ワークエリアを確保するＳ
ＲＡＭ１６２及びＤＲＡＭ１６３が備えられている。

【００２３】また、コントローラ部１６の周辺は、ディ
スクＤからＣＤドライブ２を経由して地図データが入力
されるメモリ制御部１１と、地図や車両の表示を行うデ
ィスプレィ３にその表示データを出力する表示制御部１
２と、リモコンキー４からの信号を入力する入力処理部
１３と、車両の位置を検出を行うＧＰＳ受信機５、方位
センサ６、車速センサ８より方位、車速情報を入力する
車両位置検出部１４と、音声出力装置７へ音声信号を出
力する音声制御部１５とから構成される。これら各処理
部への信号、又は各処理部からの信号は全てコントロー
ラ１６内のＣＰＵ１６１によって制御される。

【００２４】ディスクＤは、ＣＤ−ＲＯＭ、フロッピー
ディスク、ミニディスク、ＩＣカード又は光磁気ディス
ク等で構成される。ディスクＤは、道路地図（高速自動
車国道、都市高速道路、一般国道、主要地方道、一般都
道府県道、指定都市の一般市道、その他の生活道路を含
む）をメッシュ状に分割し、各メッシュ単位でノードと
リンクとを組み合わせたデータ（地図データベースとい
う）を記憶している。その他、鉄道、川、地名欄、有名
施設、運転者が予め登録した地点、等高線等の表示用の
背景データを含んでいてもよい。

【００２５】地図データベースは、それぞれの主要交差
点同士を結んだリンクとノードに関する経路ネットワー
クデータを記憶している。経路ネットワークデータは、
経路ネットワークメモリの形で記憶されている。経路ネ
ットワークメモリには、各ノードの識別番号（ノード番
号）、ノードの座標、１又は複数の隣接ノードの番号、
当該ノードと隣接ノードとを結ぶ退出リンクの数、退出
リンクのコスト、リンク距離、高速道路一般道路等の道
路種別等が含まれている。

【００２６】ここで、「ノード」とは、一般に道路の交
差点や折曲点を特定するための座標位置のことであり、
交差点を表すノードを交差点ノード、道路の折曲点（交
差点を除く）を表すノードを補間点ノードという。「リ
ンク」はノードどうしをつないだものであって、道路の
形に沿った折れ線ベクトルと理解できる。ノードと、こ
のノードの隣接ノードとを結ぶリンクを「退出リン
ク」、このノードに入ってくるリンクを「進入リンク」
という。

【００２７】以下に、車載のナビゲーション装置で行う
概略制御手順をフローチャートを用いて説明する（図４
参照）。まず、リモコンキー４から入力される目的地情
報に基づいて目的地が設定された後（ステップＳ１）、
ＣＰＵ１６１は経路計算の要求がなされたか否かの判別
をする（ステップＳ２）。

【００２８】経路計算の要求がありと判別されると、Ｃ
ＰＵ１６１はメモリ制御部１１へその旨を伝えメモリ制
御部１１は、ＣＤドライブ２を作動させ、経路計算プロ
グラム及び経路ネットワークデータをディスクＤより読
み出し、コントローラ部１６内のＳＲＡＭ１６２へロー
ドする（ステップＳ３）。ＳＲＡＭ１６２は、ロードさ
れた経路ネットワークデータを格納する、図５に示すよ
うなテーブル（このテーブルをリザルトテーブルとい
う。）を持っている。リザルトテーブルへの格納内容
は、ノード番号、格納メモリ番号、経路コスト、当該ノ
ードにつながる探索経路上の直前ノード番号、当該ノー
ドからの退出リンク数、及び退出リンクの終端に位置す
る隣接ノードの番号（その数は退出リンク数だけある）
とリンクコストである。なお、リンクコストは、正又は
０であり負になることはないものとする。また、退出リ
ンクは、経路計算上は接続リンクともいう。

【００２９】具体例で説明すると、図６に示すような経
路ネットワークの一部を想定し、ノードｖに注目する
と、前記ノード番号はノードｖの識別番号のことであり
（簡単のためｖと書く）、格納メモリ番号はノードｖを
格納する探索用ワークメモリの番号、経路コストは探索
開始ノードからノードｖまでつながった経路上のコスト
を総和したもの、直前ノード番号は探索経路に沿ったノ
ードｖの直前のノードｕの識別番号、接続リンク数はノ
ードｖの退出リンクの数（２本）、隣接ノード番号は退
出リンクの終端のノードの番号ｗ，ｘ、リンクコストは
各退出リンクのリンクコストＬ₂ ，Ｌ₃ となる。

【００３０】前記リザルトテーブル（図５）の格納デー
タのうち、接続リンク数、接続リンクの終端の隣接ノー
ド番号及びリンクコストは、ディスクＤより読み出した
経路ネットワークデータから引用してくるデータであ
る。それ以外の格納データは、初期値を設定し、探索ツ
リーを延ばしながら更新していくデータである。図４に
戻り、次にＣＰＵ１６１は、現在車両位置と目的地位置
より探索開始ノードと探索終了ノードを決定する（ステ
ップＳ４）。決定した後、経路ネットワークデータに基
づき本発明の経路探索によって現在位置から目的地まで
の最短経路計算を行う（ステップＳ５）。すなわち、探
索開始ノードから始まるトリーを探索し、探索終了ノー
ドに到れば、探索終了ノードから探索開始ノードに至る
までのリンクを逆に辿って、最短経路を求める。

【００３１】次にステップＳ６において、ＣＰＵ１６１
は、求められた最短経路について対応する座標列に変換
する。そして、最短経路表示の要求の有無を判別し（ス
テップＳ７）、地図表示の要求がある場合、座標列に基
づいて最短経路をディスプレィ３に表示する（ステップ
Ｓ８）。ここに、ステップＳ５の最短経路計算処理を図
１及び図２にしたがって詳細に説明する。

【００３２】まず、図１のステップＳ１１では、経路ネ
ットワークデータの一部をリザルトテーブルへ格納し、
ステップＳ１２でリザルトテーブルの所定のデータを初
期化する。すなわち、探索開始ノードについては、格納
メモリ番号を１、経路コストを有限値（例えば０）、直
前ノード番号を無限大（実際には、メモリのビット数で
決まる最大値）とし、探索開始ノード以外のノードにつ
いては、そのノードの格納メモリ番号を０、経路コスト
を無限大、直前ノード番号を無限大にする。そして、メ
モリ番号１の探索用ワークメモリ（以下「探索用ワーク
メモリ」という）に探索開始ノードを格納する。

【００３３】探索用ワークメモリは、図７に示すよう
に、ＳＲＡＭ１６２の中に複数個（例えば５１２個とす
る）用意されており、１番目の探索用ワークメモリは経
路コスト０からｔ（ｔは一定数であり、例えば３２秒と
する。）、２番目の探索用ワークメモリは経路コストｔ
から２ｔ、…ｊ番目の探索用ワークメモリは経路コスト
（ｊ−１）ｔからｊｔ、のノードの番号を格納できるよ
うになっている。格納するのは、ノード番号のみであっ
て、それ以外の情報を格納する必要はない。

【００３４】次に、ノードを少なくとも１つ格納してい
る、番号が最小の探索用ワークメモリｊを見つける（ス
テップＳ１３）。最初は、探索開始ノードを格納してい
る探索用ワークメモリ１が見出される。そして探索用ワ
ークメモリｊは空かどうか調べ（ステップＳ１４）、空
でなければ、探索用ワークメモリｊに格納されているノ
ードを取り出す（ステップＳ１５）。取り出しの順番は
任意でよいが、例えば、常に最も早く格納されたノード
番号を取り出す先入れ先出し規則や、常に最も遅く格納
されたノード番号を取り出す後入れ先出し規則や、これ
らの２つの規則を混合させたtwo-way sequence規則、あ
るいは常に経路コストが最小のノード番号を取り出す最
良優先規則を用いることができる。あるノードを取り出
したときには、取り出した探索用ワークメモリの中のそ
のノード番号を消去する。つまり、取り出されたノード
は基に戻さないものとする。さらに、そのノードのリザ
ルトテーブルの格納メモリ番号を０にする。

【００３５】このノード番号がｖであったとする（ステ
ップＳ１６）。リザルトテーブルを用いてノードｖの退
出リンクを探索する（ステップＳ１７）。まず、ノード
ｖの退出リンクを１つ選び，その隣接ノードがｗであっ
たとする（ステップＳ１８）。図２のステップＳ３１に
おいて、ノードｖの経路コストとｖからｗを結ぶリンク
ｖ→ｗのリンクコストとの和を求め、隣接ノードｗの経
路コストと比較し、隣接ノードｗの経路コストより小さ
ければ、リザルトテーブル上でノードｗの経路コストを
この小さい方の値に書き替え、ノードｗの直前ノードを
ｖに書き替える（ステップＳ３２）。なお、隣接ノード
ｗの経路コストと比較するという意味は、過去に探索し
たツリーの別の枝に沿ってノードｗに到達した後、ツリ
ーの現在探索中の枝が延びてきてノードｗに再度到達し
た場合に、コストの少ない経路を選択する、という意味
である。１つのノードｗに到達する経路は１本しか許さ
れないので、このような競合を解消するためにステップ
Ｓ３２の書き替え処理をするのである。

【００３６】なお、ｖが最初の探索開始ノードであり、
ｗがこれに初めてつながるノードであるとすれば、隣接
ノードｗの経路コストは初期値（無限大）となっている
ので、ステップＳ３１において、ノードｖの経路コスト
０とリンクｖ→ｗのリンクコスト（一定値）との和を求
め、隣接ノードｗの経路コストと比較すれば、前者のほ
うが小さいので、リザルトテーブル上でノードｗの経路
コストをこの小さい方の値に更新し、ノードｗの直前ノ
ードをｖに書き替えることになる（ステップＳ３２）。

【００３７】次に、ノードｗの新しい経路コストをｔで
割った商ｑ′（小数は切り捨てる）を求め（ステップＳ
３３）、ノードｗの現在の格納メモリ番号を調べる（ス
テップＳ３４）。ここで、ノードｗの経路コストをｔで
割った商がｑ′であれば、そのノードｗは、商ｑ′の小
数以下を切り捨てているので、本来探索用ワークメモリ
ｑ′＋１に格納されるべきものであることを前もって述
べておく。

【００３８】ノードｗの現在の格納メモリ番号を調べた
結果、ノードｗがどのワークメモリにも格納されていな
いノードであれば、ノードｗは現在、格納メモリ番号が
０となっている。ノードｗがいずれかのワークメモリに
格納されているノードであれば、０以外の何らかの格納
メモリ番号が与えられている。その場合には、格納メモ
リ番号はｑ′＋１であるか、ｑ′＋１より大きいかのい
ずれかである。前記ステップＳ３１からステップＳ３２
のところで説明したように、経路コストの比較を行っ
て、経路コストの少ない方を選択する操作が行われてい
るので、ｑ′＋１より小さい番号は生じない。

【００３９】ノードｗの格納メモリ番号が０であれば、
ノードｗを探索用ワークメモリｑ′＋１に格納し、リザ
ルトテーブル上の格納メモリ番号をｑ′＋１とする（ス
テップＳ３５）。格納メモリ番号がｑ′＋１であれば、
ノードｗの格納メモリ番号をそのままとする。それ以
外、すなわちｑ′＋１よりも大きな番号であるとすれ
ば、ノードｗを現在格納されているワークメモリから除
去して（ステップＳ３６）、ステップＳ３５の処理をす
る。

【００４０】以上のようにして、ノードを少なくとも１
つ格納している番号が最小の探索用ワークメモリｊから
取り出した注目するノードｖの隣接ノードｗを、経路コ
ストに応じた適正な探索用ワークメモリに格納し又は移
し替えることができる。以上の探索処理をノードｖの他
の隣接ノードについても行い、すべての隣接ノードにつ
いて終了すると、探索用ワークメモリｊに格納されてい
る他のノードについて、同様の探索処理をする。なお、
探索の終わったノードは役目を終えたので、探索用ワー
クメモリから消去される。このとき格納メモリ番号も０
にクリアする。

【００４１】このようにして、１つの探索用ワークメモ
リｊの中が空になることがある。すると、リンクコスト
の非負性により、経路コストは減少することはないの
で、それ以後に探索される経路の経路コストはすべてｔ
_j 以上になることが保証される。この時点では、経路コ
ストがｔ_j 未満になるすべての経路の探索が終了したこ
とを意味する。本願発明の方式では、１つの探索用メモ
リｊの中が空になった時点で、これまで探索済のノード
の中に目的地（探索終了ノード）が存在するかどうかを
調べることとしている。もし探索済のノードの中に目的
地がはいっていなければ、ｔ_j 未満の経路コストで目的
地に達する経路が存在しないことを意味する。一方、あ
るワークメモリｊが空になった時点で探索済みのノード
の中に目的地がはいっていいれば、経路コストがｔ_j-1
からｔ_j までの大きさの経路が存在することになる。こ
れは、本方式ではワークメモリの小さいものから順に調
べるようにしているためである。

【００４２】すなわち、ステップＳ１９の時点で、これ
まで探索したノードの中に目的地が存在すれば、経路コ
ストｔ_j 未満で目的地までの経路が存在し、しかも、今
後探索を続けても経路コストは必ずｔ_j 以上になること
が確定する。そこで、発見した探索終了ノードからリザ
ルトテーブルの直前ノードをたどって探索開始ノードま
でのノード列を取り出せば、これが最適経路となる。

【００４３】ステップＳ１９の時点で、これまで探索し
たノードの中に目的地が存在するかどうかを探す方法の
一つは、リザルトテーブルの探索終了ノードの経路コス
トを見て、これとｔ_j との大小判定をすることである。
ｔ_j 未満のものがあれば、当該探索終了ノードの直前ノ
ードをリザルトテーブル上で逆に辿り、直前ノード番号
が無限大のノード（すなわち探索開始ノード）まで至
る。そしてこれらのノード列を出力する（ステップＳ２
０）。これが最短経路を構成するノード列となる。

【００４４】もし、ステップＳ１９で、経路コストがｔ
_j 未満のものがなければ、まだ探索終了ノードに達して
いないので、ステップＳ１３以下の処理を繰り返す。前
記の実施例により、実際の経路ネットワーク上で、最短
経路を計算させ、従来のポテンシャル法と比べてみたと
ころ、次のような結果が得られた。本発明の場合とし
て、探索用ワークメモリの数を５１２とし、コスト範囲
ｔ＝３２とし、経路コストが５１２×３２＝１６３８４
以上の場合は、最後の探索用ワークメモリに格納するよ
うにした。

【００４５】大阪から京都まで探索したところ、走査し
たリンク数は、のべ約９千百本になり、経路ネットワー
クデータの読み込み時間や表示データの作成時間等を除
いた正味の計算時間は約２．２秒かかった。東京から広
島までの道路ネットワークの走査したリンク数は、のべ
約１万９千本になり、正味の計算時間は約４秒となっ
た。

【００４６】したがって、前述した従来の場合の約半分
程度の時間で探索することができた。以上、実施例に基
づいて本発明の内容を説明してきたが、本発明は前記実
施例に限られるものではない。前記実施例では、探索済
のリンク又はノードの中に探索終了リンク又は探索終了
ノードが含まれているかどうか判定するために、リザル
トテーブル上で探索終了リンク又はノードまでの経路が
少なくとも１本探索済みであり、探索終了リンク又はノ
ードの経路コストが、当該空になった探索用ワークメモ
リに対応する経路コスト未満のものであるかどうかを判
定していた（ステップＳ１９）。しかしこの方法以外
に、リザルトテーブルの記入欄に「探索終了フラグ」の
欄を設けて判定する方法もある。この場合は、図１のフ
ローチャートのステップＳ１２で「リザルトテーブルの
初期化」のときに、「探索終了フラグ」をも０にし、ス
テップＳ１７のＹＥＳの枝の後に「ノードｖの探索終了
フラグを０から１にする」という操作をし、ステップＳ
１９では、「リザルトテーブルの探索終了フラグが１の
ノードをすべて取り出してその中に探索終了ノードが含
まれているかどうか調べる」という内容にすればよい。

【００４７】また、前記実施例では、探索開始ノード・
探索終了ノード間の経路を探索する例を示したが、ノー
ドの代わりにリンクを用いて、探索開始リンク・探索終
了リンク間の経路を探索するようにしてもよい。また、
探索用ワークメモリの経路コストを区分する範囲の配列
は、コストｔ（一定値）ごととなっていたが、漸増して
いてもよい。例えば、 ｊｔ（ｊ＝１，２，３，…） のように漸増する等差数列になっていてもよく、 ｔ・ｒ^j-1 （ｊ＝１，２，３，…；ｒ＞１） のように漸増する等比数列になっていてもよい。このよ
うにすれば、探索開始位置のリンク又はノードからの経
路コストが比較的小さい経路を特に効率よく短時間で探
索することができる。また、 ｔ・ｒ^j-1 （ｊ＝１，２，３，…；ｒ＜１） のように漸減する等比数列になっていてもよい。

【００４８】このようにすれば、探索開始位置のリンク
又はノードからの経路コストが比較的大きな経路を特に
効率よく短時間で探索することができる。また、前記の
実施例では、車載装置による経路計算について説明した
が、一般家庭やオフィス内の装置（例えばパソコン）を
使って同様に最短経路計算を実施し、結果として得られ
た経路データのみを車載装置に渡し、車両の走行に利用
しても構わない。

【００４９】また、前記の実施例では、車両の位置検出
装置として、ＧＰＳ受信機５と車速センサ６、方位セン
サ８を示したが、ＧＰＳ受信機５単独で位置検出しても
よく、方位センサとＧＰＳ受信機５とを併用して位置を
検出してもよい。その他、本発明の範囲内で種々の変更
を施すことが可能である。

【００５０】

【発明の効果】以上のように本発明によれば、経路コス
トを複数範囲に区分して、各区分に対応して、探索中の
リンク又はノードを記入する欄を有する複数の探索用ワ
ークメモリを予め用意しておき、経路の探索に連れて、
探索用ワークメモリの中に格納されているリンク又はノ
ードを、より経路コストの大きな探索用ワークメモリに
移しかえていくので、探索終了ノードまでの経路が少な
くとも１本探索できた時点で、当該探索終了ノードの経
路コストが、空になったワークメモリに対応する経路コ
スト未満のものであれば、これ以上探索をすることな
く、当該探索終了ノードに至る今まで探索してきた経路
を最短経路として決定することができる。

【００５１】したがって、探索する経路の数を抑えるこ
とができ、経路探索に要する時間を短縮することができ
る。

【図面の簡単な説明】

【図１】ナビゲーション装置で行う最短経路計算を示す
フローチャート図である。

【図２】ナビゲーション装置で行う最短経路計算を示す
フローチャート図である。（図１の続き）

【図３】本発明の一実施例にかかるナビゲーション装置
の構成を示すブロック図である。

【図４】ナビゲーション装置で行う概略経路計算手順を
示すフローチャート図である。

【図５】ノードごとに、このノードの前に接続される計
算済の経路上のノードを特定する情報と、前記計算済の
経路に沿った探索開始ノードからこのノードまでのコス
トを総和した経路コストとを記入する欄を有するリザル
トテーブルの具体例を示す図である。

【図６】経路ネットワークの一部を構成するノード及び
リンクの接続関係を示す図である。

【図７】経路コストを複数範囲に区分して、各区分に対
応して、探索中のノードを記入する欄を有する複数の探
索用ワークメモリの具体例を示す図である。

【符号の説明】

Ｄ ディスク １ ナビゲーション装置本体 ２ ＣＤドライブ ３ ディスプレィ ４ リモコンキー ５ ＧＰＳ受信機 ６ 車速センサ ８ 方位センサ １１ メモリ制御部 １２ 表示制御部 １４ 車両位置検出部 １６ コントローラ １６１ ＣＰＵ １６３ ＤＲＡＭ

Claims (7)

【特許請求の範囲】
1. 【請求項１】地図上の２つの位置の間の最短経路を計算
   する場合に、一方の位置に最も近いリンク又はノードを
   探索開始リンク又はノードとし、他方の位置に最も近い
   リンク又はノードを探索終了リンク又はノードとし、探
   索開始リンク又はノードから探索終了リンク又はノード
   までを含む経路ネットワークデータを取得し、この道路
   ネットワーク内において、探索開始リンク又はノードか
   ら始まるリンク又はノードを、コストを順次加算しなが
   ら接続していって（この加算されたコストを当該リンク
   又はノードの「経路コスト」という）、リンク又はノー
   ドのツリーを構成していき、探索終了リンク又はノード
   に到達する最もコストの少ない経路を選択する方法であ
   って、 (a) 想定される最大の経路コストを複数範囲に区分し、
   各区分に対応した、探索中のリンク又はノードを記入す
   る欄を有する複数の探索用ワークメモリを用いて、 (b) 探索開始リンク又はノードを、最も経路コストの低
   い区分の探索用ワークメモリに格納し、 (c) 探索用ワークメモリの中に格納されている当該リン
   ク又はノードに着目し、当該リンク又はノードから接続
   されるリンク又はノードの経路コストを求めて、接続さ
   れたリンク又はノードをそれぞれ該当する区分の探索用
   ワークメモリに書入れるとともに探索済の当該リンク又
   はノードを探索用ワークメモリから消去するという手順
   を繰り返し、 (d) 格納したリンク又はノードが空になった探索用ワー
   クメモリがあり、かつ、探索済のリンク又はノードの中
   に探索終了リンク又は探索終了ノードが含まれているか
   どうかを判定し、探索終了リンク又は探索終了ノードが
   含まれていれば、これ以上探索をすることなく、当該探
   索終了リンク又はノードに至る今まで探索してきた経路
   を最短経路として選択することを特徴とする経路探索方
   法。
2. 【請求項２】前記手順(c) で、接続されるリンク又はノ
   ードを該当する区分の探索用ワークメモリに書入れた場
   合に、経路コストに応じた並べ替えはしないことを特徴
   とする請求項１記載の経路探索方法。
3. 【請求項３】前記手順(c) の、当該リンク又はノード
   は、リンク又はノードを少なくとも１つ格納している最
   も経路コストの低い区分の探索用ワークメモリの中に格
   納されているものの中から選定することを特徴とする請
   求項１記載の経路探索方法。
4. 【請求項４】前記探索用ワークメモリの、経路コストを
   区分する範囲は、それぞれ一定になっていることを特徴
   とする請求項１記載の経路探索方法。
5. 【請求項５】前記探索用ワークメモリの、経路コストを
   区分する範囲は、経路コストとともに漸増していること
   を特徴とする請求項１記載の経路探索方法。
6. 【請求項６】前記探索用ワークメモリの、経路コストを
   区分する範囲は、経路コストとともに漸減していること
   を特徴とする請求項１記載の経路探索方法。
7. 【請求項７】地図上の２つの位置の間の最短経路を計算
   する場合に、一方の位置に最も近いリンク又はノードを
   探索開始リンク又はノードとし、他方の位置に最も近い
   リンク又はノードを探索終了リンク又はノードとし、探
   索開始リンク又はノードから探索終了リンク又はノード
   までを含む経路ネットワークデータを取得し、この道路
   ネットワーク内において、探索開始リンク又はノードか
   ら始まるリンク又はノードを、コストを順次加算しなが
   ら接続していって、リンク又はノードのツリーを構成し
   ていき、探索終了リンク又はノードに到達する最もコス
   トの少ない経路を選択する経路探索装置であって、 経路ネットワークデータが予め記憶された地図記憶手段
   と、 探索開始リンク又はノード、探索終了リンク又はノード
   のいずれか一方又は双方を設定入力する入力手段と、 リンク又はノードごとに、このリンク又はノードの前に
   接続される計算済の経路上のリンク又はノードを特定す
   る情報と、前記計算済の経路に沿った探索開始リンク又
   はノードからこのリンク又はノードまでのコストを総和
   した経路コストとを記入する欄を有するリザルトテーブ
   ルと、 想定される最大の経路コストを複数範囲に区分し、各区
   分に対応した、探索中のリンク又はノードを記入する欄
   を有する複数の探索用ワークメモリと、 探索開始リンク又はノードを、最も経路コストの低い区
   分の探索用ワークメモリに格納し、探索用ワークメモリ
   の中に格納されている当該リンク又はノードに着目し、
   当該リンク又はノードから接続されるリンク又はノード
   の経路コストを求めてリザルトテーブルに書入れ、接続
   されたリンク又はノードをそれぞれ該当する区分の探索
   用ワークメモリに書入れるとともに探索済の当該リンク
   又はノードを探索用ワークメモリから消去するという手
   順を繰り返し、格納したリンク又はノードが空になった
   探索用ワークメモリがあり、かつ、探索済のリンク又は
   ノードの中に探索終了リンク又は探索終了ノードが含ま
   れているかどうかを判定し、探索終了リンク又は探索終
   了ノードが含まれていれば、これ以上探索をすることな
   く、当該探索終了リンク又はノードに至る今まで探索し
   てきた経路を最短経路として選択する経路計算手段とを
   備えることを特徴とする経路探索装置。