JPH0652237A - 経路探索装置 - Google Patents

Abstract

(57)【要約】 【目的】 記録媒体に記録された地図情報を用いて、入
力された出発地点より目的地点までの経路を探索し、表
示する経路探索装置に関するもので、経路探索時間を短
縮するとともに、非実用的な経路を求める可能性を減少
させることを目的とする。 【構成】 交差点、交差点の地図上の位置座標、交差点
に接続する道路と隣接する交差点、及び隣接交差点間の
道路距離が記録された道路網を複数段に階層化すること
により構成された地図情報を、地図情報記憶媒体２に記
録しておき、信号処理装置５は、端末装置１から入力さ
れた出発地点と目的地点との関係から適当なレベルの道
路網を選択し、選択された道路網上での仮の出発地点と
出発地点からの接続経路、および仮の目的地点と目的地
点からの接続経路を求め、選択された道路網上における
大域的な最短経路と、各接続経路を組み合わせ、出発地
点から目的地点までの経路を求める。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、記録媒体に記録された
地図情報を用いて、入力された出発地点より目的地点ま
での経路を探索し、表示する経路探索装置に関するもの
である。

【０００２】

【従来の技術】最近のカーエレクトロニクスの発展にと
もない、出発地点となる交差点と目的地点となる交差点
とを指定することにより、その２点間の最短経路を、予
め道路情報などが記録されている地図情報を用いて探索
し、表示装置に表示する、いわゆる経路探索装置が開発
されている。ここで、一般に用いられる経路探索手段
は、地図情報記録媒体に道路地図上のすべての交差点の
位置座標と、交差点間の接続情報、及び交差点名などの
情報を記録しておき、出発地点となる交差点と目的地点
となる交差点を入力すると、出発地点となる交差点から
順に連接した交差点を探索する演算を、目的地点となる
交差点に到達するまで繰り返すことにより最短距離の経
路を求めるダイクストラ法が知られている。

【０００３】

【発明が解決しようとする課題】しかしながら上記の従
来の手段を用いるのでは、例えば日本地図のように、探
索に用いる地図情報の交差点数が膨大な場合、もしくは
出発地点と目的地点との直線距離が離れるにつれて、一
般に経路探索に必要な時間が長くなり、実用的な時間内
で探索を終了できない場合がある。また、探索する道路
や交差点の属性、例えば、国道か私道か、もしくは地理
上重要な交差点か否か、などを考慮せずにダイクストラ
法による経路探索を行って求めた経路は、現実の道路状
況から考えて、裏道を縫うような非現実的な経路である
可能性がある。

【０００４】本発明は上記の従来の課題を解決するもの
で、経路探索時間を短縮するとともに、非実用的な経路
を求める可能性を減少させた経路探索装置を提供するこ
とを目的とする。

【０００５】

【課題を解決するための手段】この目的を達成するた
め、本発明の技術的解決手段は、地図上の交差点とその
位置座標、交差点に接続する道路と隣接する交差点、及
び隣接交差点間の道路距離を記録した道路網を、複数段
に階層化することにより構成した地図情報、並びにその
地図情報を記録した地図情報記憶媒体と、前記地図情報
記録媒体から前記地図情報を取り出す再生手段と、出発
地点と目的地点となる交差点を入力する端末手段と、そ
の入力された出発地点、及び目的地点との位置関係から
経路探索に用いる地図情報中の道路網を選択する道路網
選択手段と、その選択された道路網上で最短経路を求め
る際の出発地点となる仮の出発地点、目的地点となる仮
の目的地点、入力された出発地点と仮の出発地点間の接
続経路、及び目的地点と仮の目的地点間の接続経路を求
める接続経路探索手段と、その仮の出発地点と仮の目的
地点との最短経路を求める最短経路探索手段と、前記出
発地点から仮の出発地点の接続経路と、前記仮の出発地
点と仮の目的地点との最短経路と、目的地点と目的地点
の接続経路を組み合わせる組合手段と、出発地点、また
は目的地点となる交差点から順次、連接した交差点を順
次探索する際の交差点の評価値として、出発地点、また
は目的地点からその交差点までの距離と、目的地点また
は出発地点からその交差点までの直線距離を加えたもの
を用い、選択された道路網に含まれる交差点を見つけだ
したときにその交差点を、仮の出発地点、または仮の目
的地点とする地点設定手段とを設けたものである。

【０００６】

【作用】本発明は、入力された出発地点と目的地点間の
経路探索に用いる地図情報が複数段に階層化された道路
網から構成されており、道路網には交差点名、交差点の
地図上の位置座標、交差点に接続する道路と隣接する交
差点、及び隣接交差点間の道路距離が記録され、例え
ば、最上位レベルの道路網は高速道路や国道に相当する
道路の道路網、その下位のレベルの道路網は高速道路や
国道を含む県道路以上の道路網、その下位のレベルの道
路網は高速道路、国道、及び県道を含む市町村道路以上
の道路網、最下位レベルの道路網には全ての道路が含ま
れる道路網から構成された地図情報を用い、経路探索を
行う場合は、先ず出発地点及び目的地点の各交差点の位
置関係から経路探索に適したレベルの道路網を選択し、
次に、選択されたレベルの道路網上で大域的な最短経路
探索を行うための出発地点と目的地点となる、仮の出発
地点と仮の目的地点を求め、仮の出発地点と仮の目的地
点間の最短経路と、入力された出発地点から仮の出発地
点までの接続経路、及び仮の目的地点から入力された目
的地点までの接続経路を求め、それらの結果を組み合わ
せ、出発地点から目的地点までの経路とする。

【０００７】

【実施例】以下、図１を参照して本発明の一実施例につ
いて説明する。図１は本発明の一実施例における経路探
索装置のブロック結線図を示すものである。図１におい
て、１は出発地点及び目的地点となる交差点を入力する
端末装置、２は階層化された道路網から構成された地図
情報が記憶されている地図情報記憶媒体、３は後述する
信号処理装置５の命令により地図情報記憶媒体２から必
要な地図情報を読み出す記憶媒体再生装置、４は後述す
る信号処理装置５から送られた経路及び道路網を表示す
る表示装置である。５は端末装置１から入力された出発
地点となる交差点と目的地点となる交差点とからその間
の経路探索を行い、求めた経路及び必要に応じて道路網
を表示装置４に出力する信号処理装置である。さらに、
この信号処理装置５において、５１は端末装置１から出
発地点及び目的地点となる交差点が入力されると、記憶
媒体再生装置３を用いて一時記憶装置５３に地図情報を
読み込み、一時記憶装置５３を利用しながら、読みとり
専用記憶装置５２に記憶されている経路探索プログラム
を実行する中央演算装置である。５２は経路探索プログ
ラムと、道路網選択のための対応表が記憶されている読
みとり専用記憶装置である。５３は中央演算装置５１が
経路探索を実行する際に一時記憶装置として利用する、
交差点記憶領域、確定交差点記憶領域、及び道路網記憶
領域を含む一時記憶装置である。

【０００８】なお、上述の道路網及び階層化された道路
網から構成された地図情報について図２及び図３を参照
しながら説明しておく。

【０００９】道路網は各交差点ｖについて、交差点名、
交差点の地図上の座標、交差点ｖに接続道路と接続する
交差点ｗ、及び接続する道路の距離ｄ_vwが記録されてい
る。図２（ａ）に道路網の実施例を示す。また、図２
（ｂ）は、図２（ａ）の道路網が表示装置４に表示され
た図である。以下では説明の簡略化のため、図２（ｂ）
のように、交差点と接続する道路による道路網地図を道
路網と同一視するが、本実施例の経路探索装置内部では
図２（ａ）のような道路網に記録されているデータを用
いて処理を行っているものとする。

【００１０】図３は、複数段に階層化された道路網から
構成された地図情報を図示したものである。図３におい
て地図情報を図示するため、地図情報を構成する各道路
網は図２（ｂ）のような道路網地図を用いているが、地
図情報記憶媒体には、図２（ａ）のような道路網が複数
記録されている。

【００１１】地図情報に含まれる各道路網の関係につい
てさらに述べると、下位レベルの道路網は、上位レベル
の道路網に含まれる交差点の情報を含んでいる。例え
ば、最上位レベルの道路網に含まれる交差点は、下位の
道路網に記録されている。また、最下位レベルの道路網
は上位の道路網に含まれる交差点の情報を記録してい
る。

【００１２】実際には、最下位レベルの道路網以外の道
路網は、交差点名、地図上の位置座標、接続された道路
の距離を記録していなくともよい。この場合には必要に
応じて、最下位レベルの道路網を参照すればよい。

【００１３】このように構成されたものでは、信号処理
装置５は、端末装置１から入力された出発地点と目的地
点との関係から適当なレベルの道路網を選択し、選択さ
れた道路網上での仮の出発地点と出発地点からの接続経
路、および仮の目的地点と目的地点からの接続経路を求
め、選択された道路網上における大域的な最短経路と、
各接続経路を組み合わせ、出発地点から目的地点までの
経路を求める。

【００１４】以下、読みとり専用記憶装置５２に記憶さ
れている経路探索プログラムを実行した際の動作につい
て、図４のフローチャートを参照しながら説明する。上
述の地図情報を用いた経路探索は、以下の手順で行われ
る。

【００１５】図４のフローチャートのステップ１では、
端末装置１から出発地点、及び目的地点となる地図情報
上の交差点を入力する。このとき端末装置１から入力さ
れる情報は地図情報に記録されている交差点名、もしく
は出発地点及び目的地点の座標のどちらでもよい。座標
を入力された場合、地図情報を用いて対応する交差点を
定める。

【００１６】ステップ２では、ステップ１で入力された
出発地点、及び目的地点とを用いて、大域的に経路探索
に用いる道路網を選択し、記憶媒体再生装置３を用いて
最下位レベルの道路網と選択された道路網を、一時記憶
装置５３に読み込む。道路網の選択には、具体的には、
以下のように行う。出発地点、及び目的地点の位置座標
を地図情報から求め、それらから出発地点と目的地点と
の間の直線距離を計算する。その直線距離を用いて、読
みとり専用記憶装置５２に記憶している地図情報中の道
路網と直線距離との対応表から、経路探索に用いる道路
網を選択する。対応表の具体例として、例えば出発地点
と目的地点との直線距離が０キロメートル以上５キロメ
ートル未満ならば最下位レベルの道路網、５キロメート
ル以上１５キロメートル未満ならばその上のレベルの道
路網、１５キロメートル以上３０キロメートル未満なら
ばその上のレベルの道路網、３０キロメートル以上５０
キロメートル未満ならばその上のレベルの道路網、５０
キロメートル以上ならば、最上位レベルの道路網を用い
る、などが考えられる。

【００１７】ステップ３では、ステップ２において選択
された道路網上での仮の出発地点と仮の目的地点、及び
各地点までの接続経路を求める。具体的には、以下のよ
うに行う。図５のフローチャートを参照しながら説明す
る。図５（ａ）のステップ３１では、入力された出発地
点と目的地点とから仮の出発地点、及び出発地点から仮
の出発地点までの接続経路を求め、ステップ３２では、
入力された出発地点と目的地点とから仮の目的地点、及
び目的地点から仮の目的地点までの接続経路を求める。

【００１８】図５（ｂ）、及び図６を参照しながらステ
ップ３１についてさらに詳細説明する。

【００１９】ステップ３１１では、入力された出発地点
ｓに接続する各交差点ｖを最下位レベルの道路網から抽
出し、出発地点ｓからの距離Ｄ_v、直前の交差点Ｐ_vとと
もに、一時記憶装置５３の交差点記憶領域に記録する。

【００２０】ここでの距離Ｄ_v、直前の交差点Ｐ_vの具体
的な値は、

【００２１】

【数１】

【００２２】である。ステップ３１２では、交差点記憶
領域に記録された各交差点ｖについて、出発地点ｓから
の距離Ｄ_vと、交差点ｖから目的地点ｇまでの直線距離
Ｈ_vgを加えた評価値ｆ_v（数２）が最小の交差点ｖを選
ぶ。

【００２３】

【数２】

【００２４】ステップ３１３では、ステップ３１２で選
んだ交差点ｖを交差点記憶領域から削除し、一時記憶装
置５３の確定交差点記憶領域に出発地点ｓからの距離Ｄ
_vと直前の交差点名Ｐ_vとともに記録する。

【００２５】ステップ３１４では、ステップ３１３で確
定交差点記憶領域に記録された交差点ｖが、ステップ２
で選択された道路網に属するかどうか調べ、属している
ならばステップ３１１０へ、属していないならばステッ
プ３１５へ行く。

【００２６】ステップ３１５では、ステップ３１２で選
んだ交差点ｖに接続する各交差点ｗを、一時記憶装置５
３に記憶されている最下位レベルの道路網から順次抽出
し、交差点ｗが確定交差点記憶領域に記録されていない
場合のみ、ステップ３１６へ送り、記録されている場合
は、接続する次の交差点を抽出する。交差点ｖに接続す
る交差点が無くなった場合、ステップ３１２へ戻る。

【００２７】ステップ３１６では、交差点ｗが交差点記
憶領域に記録されているか、否かを調べ、記録されてい
る場合にはステップ３１７へ行き、記録されていない場
合にはステップ３１９へ行く。

【００２８】ステップ３１７では、

【００２９】

【数３】

【００３０】を計算し、（数２）が成立している場合に
は、ステップ３１８へ行き、不成立の場合にはステップ
３１５へ戻る。ステップ３１８では、交差点記憶領域に
記憶されている、出発地点ｓから交差点ｗまでの距離Ｄ
_wを

【００３１】

【数４】

【００３２】に、また直前の交差点名Ｐ_wをｖに、それ
ぞれ更新する。ステップ３１５へ戻る。 ステップ３１
９では、出発地点ｓから交差点ｗまでの距離Ｄ_wを（数
４）とし、また直前の交差点名Ｐ_wをｖとし、交差点記
憶領域に記録する。ステップ３１５へ戻る。

【００３３】ステップ３１１０では、ステップ３１３で
記録された交差点ｖを仮の出発地点ｐ_sとして、一時記
憶装置５３に記憶する。また、交差点ｖの直前の交差点
から順次、出発地点ｓに戻るまで、逆にたどり、仮の出
発地点ｐ_sから出発地点ｓまでの交差点の並びを、仮の
出発地点ｐ_sから出発地点ｓの接続経路として、一時記
憶装置５３に記憶する。

【００３４】以上の方法を用いることにより、入力され
た出発地点ｓと目的地点ｇとから、仮の出発地点ｐ_sと
出発地点ｓからの接続経路を求めることが出来る。

【００３５】（数２）のような評価値を使うことにより
探索方向に方向性を持たせ、仮の出発地点ｐ_sを求め
る。このような評価値を用いることで探索領域が狭まる
ことから、仮の出発地点ｐ_s、及び接続経路の探索時間
が短縮される。

【００３６】ステップ３２については、出発地点ｓと目
的地点ｇとを入れ替え、ステップ３１と同様の方法で仮
の目的地点ｐ_gと、目的地点ｇからの接続経路を求める
ことが出来る。

【００３７】ステップ４では、選択された道路網上で、
仮の出発地点ｐ_sと仮の目的地点ｐ_gとの最短経路を求め
る。ここでは一般的な最短経路探索アルゴリズムである
ダイクストラ法を用いる。

【００３８】ステップ５では、出発地点ｓから仮の出発
地点ｐ_sまでの接続経路と、仮の出発地点ｐ_sと仮の目的
地点ｐ_gとの最短経路と、仮の目的地点ｐ_gと目的地点ｇ
までの接続経路を組み合わせ、表示装置４に表示する。

【００３９】以上のように、出発地点と目的地点との関
係から、適当なレベルの道路網を選択し、選択された道
路網上で大域的な最短経路と、出発地点、目的地点から
選択された道路網までの接続経路を求め、それらの結果
を組み合わせ、最終的な経路を求める。

【００４０】

【発明の効果】以上のように本発明は、第１に、入力さ
れた出発地点と目的地点との位置関係から、経路探索に
用いる道路網を選択することにより、２点間が地理的に
遠い位置関係にある場合には、交差点の比較的疎な道路
網を用いることで、探索する交差点数が少なくなり、結
果的に経路探索時間を短縮できる。

【００４１】第２に、入力された出発地点と目的地点と
の位置関係から、経路探索に用いる道路網を選択するこ
とにより、２点間が地理的に遠い位置関係にある場合に
は、国道や県道に相当する道路網を利用することによ
り、裏道を縫うような非現実的な経路を求める危険性が
減少させることができる。

【図面の簡単な説明】

【図１】本発明の一実施例における経路探索装置のブロ
ック構成図

【図２】（ａ）同経路探索装置の要部の地図情報に記録
されている道路網の概念図 （ｂ）同道路網を表示した概念図

【図３】同経路探索装置の要部の階層化された道路網よ
りなる地図情報の概念図

【図４】同経路探索装置の動作フローチャート

【図５】（ａ）同経路探索装置の動作フローチャート （ｂ）同経路探索装置の動作フローチャート

【図６】同経路探索装置による経路探索の概念図

【符号の説明】

１ 端末装置 ２ 地図情報記憶媒体 ３ 記憶媒体再生装置 ４ 表示装置 ５ 信号処理装置

Claims (2)

【特許請求の範囲】
1. 【請求項１】 地図上の交差点とその位置座標、交差点
   に接続する道路と隣接する交差点、及び隣接交差点間の
   道路距離を記録した道路網を、複数段に階層化すること
   により構成した地図情報、並びにその地図情報を記録し
   た地図情報記憶媒体と、前記地図情報記録媒体から前記
   地図情報を取り出す再生手段と、出発地点と目的地点と
   なる交差点を入力する端末手段と、その入力された出発
   地点、及び目的地点との位置関係から経路探索に用いる
   地図情報中の道路網を選択する道路網選択手段と、その
   選択された道路網上で最短経路を求める際の出発地点と
   なる仮の出発地点、目的地点となる仮の目的地点、入力
   された出発地点と仮の出発地点間の接続経路、及び目的
   地点と仮の目的地点間の接続経路を求める接続経路探索
   手段と、その仮の出発地点と仮の目的地点との最短経路
   を求める最短経路探索手段と、前記出発地点から仮の出
   発地点の接続経路と、前記仮の出発地点と仮の目的地点
   との最短経路と、目的地点と目的地点の接続経路を組み
   合わせる組合手段と、出発地点、または目的地点となる
   交差点から順次、連接した交差点を順次探索する際の交
   差点の評価値として、出発地点、または目的地点からそ
   の交差点までの距離と、目的地点または出発地点からそ
   の交差点までの直線距離を加えたものを用い、選択され
   た道路網に含まれる交差点を見つけだしたときにその交
   差点を、仮の出発地点、または仮の目的地点とする地点
   設定手段とを具備する経路探索装置。
2. 【請求項２】 道路網選択手段、接続経路探索手段、最
   短経路探索手段、組合手段、及び地点設定手段は信号処
   理装置により構成されている請求項１記載の経路探索装
   置。