JPH04301515A - 経路探索装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、車両の走行経路を案内
する車両用走行案内装置（ナビゲーション装置）に設け
られ、予め記憶された階層構造の地図データに基づき、
出発地と目的地とを結ぶ走行経路を探索する経路探索装
置に関する。

【０００２】

【従来の技術】従来より、この種の経路探索装置として
、特開平２−５６５９１号公報に開示されている如く、
道路地図を複数に分割した各ブロックの道路情報を、一
ブロックの大きさの異なる各階層毎に作成しておき、出
発地及び目的地が指定されると、まず一ブロックの大き
さが最も小さい下位の階層にて、同一ブロック内に出発
地及び目的地を含む道路情報があるかどうかを判断し、
同一ブロック内に出発地及び目的地を含む道路情報があ
れば該道路情報に基づき出発地から目的地までの経路を
探索し、同一ブロック内に出発地及び目的地を含む道路
情報がなければ、出発地及び目的地をそれぞれ含む２つ
のブロックの道路情報に基づき、各ブロック内の出発地
及び目的地から隣接ブロック内の道路網に連結している
連結地点までの経路を探索し、この探索により出発地及
び目的地をそれぞれ含む各ブロックの連結地点が一致す
れば（即ち各ブロックが隣接していれば）、この連結地
点を介して各ブロック内での探索結果を連結して出発地
から目的地までの経路を決定し、逆に各ブロックの連結
地点が一致しなければ（即ち各ブロックが隣接していな
ければ）、探索を行なう道路情報の階層を上位の階層に
変更して、上記と同様に経路探索を行なう、というよう
に、階層化した道路情報の下位階層から上位階層へと順
次経路探索を行なうことにより、出発地から目的地まで
の経路を決定するものが知られている。

【０００３】

【発明が解決しようとする課題】しかし上記従来の装置
においては、道路地図を複数に分割した各ブロックの道
路情報を一単位として探索を行ない、この探索ブロック
内での道路網と隣接ブロックの道路網との接続は、道路
地図をブロック分割した際に分断された道路の地点を表
す連結地点に基づき行っているため、各ブロック毎の道
路情報には、実際の道路に存在する交差点情報とは別に
、実際の道路には存在しない連結地点情報をも記憶して
おく必要があり、地図データの作成が面倒で、しかもそ
のデータ量が多くなるため経路探索に時間がかかるとい
った問題があった。また上記従来の装置においては、出
発地側からの探索ブロックと目的地側からの探索ブロッ
クが同一であるか隣接しているかによって探索処理が異
なるため、探索処理を行なうマイクロコンピュータのプ
ログラム容量が多くなり、これによっても経路探索に時
間がかかるといった問題があった。

【０００４】本発明はこうした問題に鑑みなされたもの
で、少ないデータ量にて、経路探索を速やかに且つ正確
に行なうことができる経路探索装置を提供することを目
的としている。

【０００５】

【課題を解決するための手段】即ち、上記目的を達成す
るためになされた本発明は、図１に例示する如く、道路
地図を所定の大きさで複数に分割した各ブロック毎に作
成され、当該ブロックを囲む周囲のブロックとのオーバ
ラップ領域を含む所定領域を一区画とする複数の道路情
報が、一ブロックの大きさが異なる各階層毎に記憶され
た地図データ記憶手段と、外部から上記道路地図上の２
つの地点が指定されると、上記地図データ記憶手段に記
憶された一ブロックの大きさが小さい下位の階層の道路
情報から順に、少なくとも上記指定された２地点のいず
れか一つを含む道路情報，及び該２地点を含む一つの道
路情報又は上記オーバラップ領域により該２地点を接続
可能な２つの道路情報を選択してゆき、該２地点を接続
するのに必要な道路情報を決定する道路情報決定手段と
、該道路情報決定手段により決定された道路情報に基づ
き、上記２地点の内の一方の地点から他方の地点に至る
経路を探索する経路探索手段と、を備えたことを特徴と
する経路探索装置を要旨としている。

【０００６】

【作用】このように本発明の経路探索装置においては、
従来と同様、地図データ記憶手段には各階層毎に複数の
道路情報が記憶されているが、一つの道路情報には、道
路地図を分割したブロック内の道路情報だけでなく、そ
のブロックを囲む周囲のブロックとのオーバラップ領域
の道路情報が含まれている。そして外部から道路地図上
の２つの地点が指定されると、道路情報決定手段が、地
図データ記憶手段に記憶された下位の階層の道路情報か
ら順に、少なくとも外部から指定された２地点のいずれ
か一つを含む道路情報，及びその２地点を含む一つの道
路情報又はオーバラップ領域によりその２地点を接続可
能な２つの道路情報を選択してゆき、その２地点を接続
するのに必要な道路情報を決定する。すると経路探索手
段が、その決定された道路情報に基づき、外部から指定
された２地点の内の一方の地点から他方の地点に至る経
路を探索する。

【０００７】

【実施例】以下に本発明の実施例を図面と共に説明する
。まず図２は、本発明が適用された車両用のナビゲーシ
ョン装置の概略構成を表すブロック図である。図に示す
如く本実施例のナビゲーション装置は、出発地，目的地
等を入力するためのスイッチ，車両の走行により変化す
る車両の現在位置を検出するための方位や車速等を検出
するセンサ等からなる入力装置２と、走行経路案内用の
道路地図や車両の現在位置等を表示する表示装置４と、
予め地図データが格納された地図データ記憶手段として
の外部記憶装置６と、入力装置２からの入力信号に基づ
き車両の走行経路を探索して表示装置４に地図表示を行
なう制御装置８とから構成されている。

【０００８】外部記憶装置６には、第１レベルから第３
レベルまでの階層化した道路情報が地図データとして記
憶されている。ここで第１レベルの道路情報は、全国を
関東，東海，近畿，北陸，中国…というように大きな地
区（以下，第１ブロックという）毎に分割して、例えば
関東−東海，関東−近畿，関東−中国，…というように
第１ブロックの各々を結ぶ（即ち、少なくとも２つの第
１ブロックを含む）広域の領域を一区画として作成され
た、国道，高速道路等の幹線道路のみからなる道路情報
である。

【０００９】また第２レベルの道路情報は、全国をある
一定の大きさ（例えば１６ｋｍ四方）のブロック（以下
，第２ブロックという）に分割し、各第２ブロック毎に
、当該第２ブロックを中心とするｘ×ｘ（但し、ｘ＞１
であり、本実施例ではｘ＝５）個の第２ブロックからな
る領域を一区画として作成された、上記幹線道路と県道
等の各地の主要道路とからなる道路情報である。

【００１０】また更に第３レベルの道路情報は、第２レ
ベルの道路情報を作成した際の一つのブロック（即ち第
２ブロック）を更にｙ×ｙ（但し、ｙ＞１であり、本実
施例ではｙ＝４）個のブロック（以下，第３ブロックと
いう）に分割し、各第３ブロック毎に、当該第３ブロッ
クを中心とするｚ×ｚ（但し、ｚ＞１であり、本実施例
ではｚ＝３）個の第３ブロックからなる領域を一区画と
して作成された、上記幹線道路及び主要道路と、市町村
道等の地方道路とからなる道路情報である。

【００１１】つまり外部記憶装置６に記憶されている第
１レベルから第３レベルまでの階層化した道路情報のそ
れぞれには、道路地図を分割した各ブロック毎に、その
ブロックの周囲の領域（即ち他のブロックとのオーバラ
ップ領域）を含む道路情報が記憶されている。なお第２
レベル及び第３レベルの道路情報において、道路情報を
作成すべき区画が山岳地等であり、区画内に表示すべき
道路がないような場合には、道路情報は作成されない。

【００１２】また次に上記各道路情報は、当該区画内の
道路網が例えば図３（ａ）に示す如き道路網であれば、
その道路網を構成する各交差点（ノード）毎に、図３（
ｂ）に示す如く作成されている。つまり各道路情報は、
各ノード毎に、各ノードに順に付されたノード番号情報
と、各ノードに接続された道路（リンク）の数を表す接
続リンク数情報と、各ノードに接続されたリンクに順に
付されたリンク番号情報と、各ノードに接続されたリン
クを特定するためのリンク標準コード情報と、各ノード
に接続されたリンクの距離を表すリンク距離情報とによ
り構成されている。

【００１３】なおリンク標準コードは、あるノードに接
続する最大リンク数を上限として１から付けたもので、
上位階層の道路情報にてノードに接続されるリンク数が
減少してもその番号は変わらない。つまり最下位の階層
（本実施例では第３レベル）の道路情報において、特定
ノードに１，２，３，４のリンクが接続されていた場合
、その上位階層（つまり第２或いは第１レベル）の道路
情報の特定ノードに接続されるリンクの標準コードは１
，３，４というようになる。

【００１４】また図には示さないが、上記道路網を構成
する各リンクには、後述の経路探索時に各ノードに重み
を付けるために、リンク標準コードに対応して、国道，
県道等の道路種別を表す種別情報，道路幅を表す幅員情
報，有料道路であるか否かを表す識別情報，右左折や一
方通行等の通行規則を表す規則情報等も付されており、
更に各ノードには、その位置を特定するための座標情報
，例えば接続される道路（リンク）が一方通行であると
いうように、探索の始点或いは終点としては適当でない
ノードである旨を表す識別情報，ノードを特定するため
のノード標準コード情報等が付されている。

【００１５】このように構成された本実施例のナビゲー
ション装置においては、入力装置２を介して外部から出
発地及び目的地が入力されると、制御装置８が、上記外
部記憶装置６に記憶された地図データに基づき、出発地
点と目的地点とを結ぶ経路を探索する。以下、この探索
処理について、図４〜図６に示すフローチャートに基づ
き説明する。

【００１６】図４に示す如く、探索処理が開始されると
、ステップ１００にて、図５に示す手順で、経路の探索
に必要な探索区画を決定する。なおこのステップ１００
の処理は、道路情報決定手段に相当する。

【００１７】即ち、図５に示す如く、まずステップ３１
０にて出発地の座標（始点座標）Ｏを含む第３レベルの
区画（始点第３区画）Ｋ３１と目的地の座標（終点座標
）Ｄを含む第３レベルの区画（終点第３区画）Ｋ３２を
算出し、続くステップ３２０にて、この算出した始点第
３区画Ｋ３１及び終点第３区画Ｋ３２は、同一区画であ
るか否かを判断する。そして図７（ａ）に示す如く、始
点第３区画Ｋ３１及び終点第３区画Ｋ３２が同一区画で
あれば、この区画の道路情報に基づき出発地から目的地
までの経路を探索できるので、ステップ３３０に移行し
て、探索区画はこの第３レベルの区画１個である旨を決
定して、後述ステップ４４０に移行する。

【００１８】一方ステップ３２０にて始点第３区画Ｋ３
１と終点第３区画Ｋ３２とが同一区画ではないと判断さ
れると、今度はステップ３４０に移行して、図７（ｂ）
に示す如く、始点第３区画Ｋ３１と終点第３区画Ｋ３２
とが隣接しており、そのオーバラップ領域が重複してい
るか否かによって、その２区画で経路探索が可能である
か否かを判断する。そして図７（ｂ）に示す如く、始点
第３区画Ｋ３１と終点第３区画Ｋ３２との２区画により
経路探索が可能であれば、ステップ３５０に移行して、
探索区画はこの第３レベルの２区画である旨を決定して
、後述ステップ４４０に移行する。

【００１９】また次にステップ３４０にて、始点第３区
画Ｋ３１と終点第３区画Ｋ３２との２区画では経路探索
ができないと判断されると、今度はステップ３６０に移
行して、図７（ｃ）に示す如く、始点第３区画Ｋ３１と
終点第３区画Ｋ３２とが、隣接するもう一つの第３レベ
ルの区画Ｋ３３によりオーバラップ状態で接続可能であ
るか否かによって、その３区画で経路探索が可能となる
かどうかを判断する。そして図７（ｃ）に示す如く、始
点第３区画Ｋ３１と、終点第３区画Ｋ３２と、隣接区画
Ｋ３３との３区画により経路探索が可能であれば、ステ
ップ３７０に移行して、探索区画はこの第３レベルの３
区画である旨を決定し、後述ステップ４４０に移行する
。

【００２０】なお図７において、破線で区切られた各ブ
ロックは、前述の第３ブロックを表し、第３レベルの道
路情報の一区画は、前述したように３×３個の第３ブロ
ックからなる領域であることを示している。また上記ス
テップ３１０では、第３レベルの区画の中心に位置する
第３ブロック内に始点座標Ｏ又は終点座標Ｄが存在する
区画を、始点第３区画Ｋ３１又は終点第３区画Ｋ３２と
して求める。

【００２１】次に上記ステップ３６０にて、第３レベル
の３区画を用いて経路探索を行なうことができないと判
断されると、ステップ３８０に移行して、探索範囲を第
２レベルの道路情報まで拡大すべく、出発地の座標（始
点座標）Ｏを含む第２レベルの区画（始点第２区画）Ｋ
２１と目的地の座標（終点座標）Ｄを含む第２レベルの
区画（終点第２区画）Ｋ２２を算出する。そして続くス
テップ３９０にて、この算出した始点第２区画Ｋ２１及
び終点第２区画Ｋ２２は、同一区画であるか否かを判断
し、図８（ａ）に示す如く、始点第２区画Ｋ２１と終点
第２区画Ｋ２２が同一区画であれば、この区画の道路情
報と、これより下位の始点第３区画Ｋ３１及び終点第３
区画Ｋ３２の道路情報に基づき、出発地から目的地まで
の経路を探索できるので、ステップ４００に移行して、
探索区画は始点第３区画Ｋ３１，この第２レベルの区画
，及び終点第３区画Ｋ３２の合計３区画である旨を決定
して、後述ステップ４４０に移行する。

【００２２】一方ステップ３９０にて始点第２区画Ｋ２
１と終点第２区画Ｋ２２とが同一区画ではないと判断さ
れると、今度はステップ４１０に移行して、図８（ｂ）
に示す如く、始点第２区画Ｋ２１と終点第２区画Ｋ２２
とが隣接しており、そのオーバラップ領域が重複してい
るか否かによって、その２区画で経路探索が可能である
か否かを判断する。そして図７（ｂ）に示す如く、始点
第２区画Ｋ２１と終点第２区画Ｋ２２との２区画により
経路探索が可能であれば、ステップ４２０に移行して、
探索区画は、始点第３区画Ｋ３１，始点第２区画Ｋ２１
，終点第２区画Ｋ２２，及び終点第３区画Ｋ３２の合計
４区画である旨を決定して、後述ステップ４４０に移行
する。

【００２３】また次にステップ４１０にて、始点第２区
画Ｋ２１と終点第２区画Ｋ２２とでは経路探索ができな
いと判断されると、今度はステップ４３０に移行して、
図９に示す如く、始点第２区画Ｋ２１と終点第２区画Ｋ
２２とを含む第１レベルの区画（第１区画）Ｋ１を求め
、探索区画は、始点第３区画Ｋ３１，始点第２区画Ｋ２
１，第１区画Ｋ１，終点第２区画Ｋ２２，及び終点第３
区画Ｋ３２の合計５区画である旨を決定して、ステップ
４４０に移行する。

【００２４】なお図８及び図９において、破線で区切ら
れた各ブロックは、前述の第２ブロックを表し、第２レ
ベルの道路情報の一区画は、前述したように５×５個の
第２ブロックからなる領域であることを示している。

【００２５】このように探索区画が決定されると、今度
はステップ４４０に移行して、その決定した探索区画全
てに区画データ（即ち道路情報）があるか否かを判断す
る。つまり上述したように、第２レベル及び第３レベル
の道路情報において、道路情報を作成すべき区画が山岳
地等であり、区画内に表示すべき道路がないような場合
には、道路情報は作成されていないため、ここでは、上
記決定した探索区画全てにデータが存在するかどうかを
判断するのである。

【００２６】そしてこのステップ４４０にて、探索区画
全てにデータが存在すると判断されると、当該ステップ
１００の処理を終了し、決定した探索区画の内、データ
が存在しない区画が存在する場合には、ステップ４５０
に移行して、その区画を除去することにより探索区画を
変更し、当該ステップ１００の処理を終了する。

【００２７】即ち、ステップ４５０において、例えば決
定された探索区画が、図８（ｂ）に示すように「Ｋ３１
，Ｋ２１，Ｋ２２，Ｋ３２」である場合に、終点第３区
画Ｋ３２のデータが存在しないときには、図１０（ａ）
に示す如く、探索区画が「Ｋ３１，Ｋ２１，Ｋ２２」に
変更され、また始点第３区画Ｋ３１のデータが存在しな
いときには、図１０（ｂ）に示す如く、探索区画が「Ｋ
２１，Ｋ２２，Ｋ３２」に変更される。また例えば決定
された探索区画が、図９に示すように「Ｋ３１，Ｋ２１
，Ｋ１，Ｋ２２，Ｋ３２」である場合に、終点第３区画
Ｋ３２及び終点第２区画Ｋ２２のデータが存在しないと
きには、図１０（ｃ）に示す如く、探索区画が「Ｋ３１
，Ｋ２１，Ｋ１」に変更され、また始点第３区画Ｋ３１
及び始点第３区画Ｋ２１のデータが存在しないときには
、図１０（ｄ）に示す如く、探索区画が「Ｋ１，Ｋ２２
，Ｋ３２」に変更される。

【００２８】図４に戻り、上記のようにステップ１００
にて探索区画が決定されると、今度はステップ１１０に
て、上記決定した探索区画の最後の区画（探索最終区画
）の探索は終了したか否かを判断する。

【００２９】現時点では探索区画を決定した直後であり
、まだ探索を実行していないので、このステップ１１０
では否定判断されて、ステップ１２０に移行し、上記決
定した探索区画の道路情報を読み込む。なおこのステッ
プ１２０の道路情報の読み込み処理は、上記決定した探
索区画の最初の区画（探索開始区画）から順に一区画毎
に行なわれ、例えば探索区画が図７（ｃ）に示す３つの
区画からなる場合には、当該ステップ１２０の処理の実
行毎に、始点第３区画Ｋ３１，隣接区画Ｋ３３，終点第
３区画Ｋ３３といった順に道路情報が読み込まれる。

【００３０】こうしてステップ１２０にて道路情報が読
み込まれると、続くステップ１３０に移行して、上記道
路情報を読み込んだ現在の探索区画が最終区画であるか
否かを判断し、探索区画が最終区画であれば、ステップ
１４０に移行して、その区画内の各ノードの座標（ノー
ド座標）から目的地に最も近いノードを求め、これを目
的ノードとして決定する。

【００３１】一方ステップ１３０にて探索区画が最終区
画でないと判断された場合、或いはステップ１４０にて
目的ノードが決定された場合には、ステップ１５０に移
行して、今度は現在の探索区画が探索開始区画であるか
否かを判断する。そして探索区画が探索開始区画であれ
ば、ステップ１６０に移行して、その区画内のノード座
標から出発地に最も近いノードを求め、これを開始ノー
ドとして決定する。

【００３２】なおステップ１４０及びステップ１６０に
て、それぞれ目的ノード及び開始ノードを決定するに当
たっては、各ノードに付された前述の識別情報が使用さ
れ、たとえ目的地（或いは出発地）に最も近いノードで
あっても、そのノードが探索の終点（或いは始点）とし
て適当でない場合には、そのノードを目的ノード（或い
は開始ノード）として設定しないようにされている。

【００３３】次にステップ１５０にて、探索区画が探索
開始区画でないと判断された場合には、ステップ１７０
に移行して、前回の区画探索の結果を今回の探索区画に
反映させる。つまり探索区画が複数である場合、少なく
とも連続する２つの探索区画にはオーバラップ領域が存
在し、前回の区画結果の中には今回の探索区画の探索結
果としてそのまま利用できる情報があるため、ステップ
１７０においては、図６に示す如く、前回の区画探索の
結果を各ノード毎に読み出し、その読み出したノードの
標準コードが今回の探索区画内のノード標準コードと一
致するか否かを判断し（ステップ５１０）、ノード標準
コードが一致すれば、前回の区画探索時にそのノードに
付けた重み等の情報を今回の探索区画の探索結果として
移す（ステップ５２０）、といった処理を、前区画のノ
ード全てについて行ない、前区画のノード全てについて
この処理を行なうと（ステップ５００−ＹＥＳ）、上記
移したノード情報の内、重みの最も小さいノードを今回
の探索区画の開始ノードとして設定する（ステップ５３
０）。

【００３４】こうして今回の探索区画の開始ノードが設
定されると、今度はステップ１８０に移行して、探索区
画内全てのノードを探索したか否かを判断する。現時点
では探索を開始した直後であることから、ステップ１８
０にて否定判断されて、ステップ１９０に移行する。そ
してステップ１９０にて、開始ノードから順に１ノード
づつ重み計算を行ない、ステップ２００にて目的ノード
に達したか否かを判断し、目的ノードに達していなけれ
ば再度ステップ１８０に移行する、といった手順で、区
画内全てのノードを探索するか、或いは探索ノードが目
的ノードに達するまでの間重み計算を繰り返す。

【００３５】そして例えばステップ２００にて探索ノー
ドが目的ノードに達したと判断されると、ステップ２１
０にて、探索が成功したと判断して、経路を確定した後
、当該処理を終了する。また区画内全てのノードについ
てステップ１９０にて重み計算を行ない、ステップ１８
０にて区画内全てのノードの探索が終了したと判断され
ると、再度ステップ１１０に移行して、探索最終区画の
探索が終了したかどうかを判断し、探索最終区画の探索
が終了していなければ、ステップ１２０に移行して、次
の探索区画の道路情報を読み込み、上記ステップ１３０
以降の処理を実行し、ステップ１１０にて探索最終区画
の探索が終了したと判断された場合には、探索最終区画
の探索が終了したにもかかわらず、ステップ２００にて
目的ノードに達した旨が判定されていないことから、ス
テップ２２０に移行して探索は失敗したと判断して、そ
の旨を表示装置４に表示し、当該処理を終了する。

【００３６】ここで本実施例の経路探索は、周知のダイ
クストラのアルゴリズムを応用して実行される。即ち、
本実施例では、始点ノードから順に、ノード情報、リン
ク情報を外部記憶装置６から読み込み、当該ノードに接
続されたリンクの距離，種別，幅員，有料・無料の種別
，通行規則等の情報に係数を乗じて重みを求め、その和
を始点ノードから当該ノードへの重みとして確定し（ス
テップ１９０）、最小の重みのノードから順次確定して
ゆくことにより、経路を決定する（ステップ２１０）。 例えば、探索区画が図３（ａ）に示した第３レベルの区
画一つであり、始点ノードがノード番号ｎ１−１のノー
ドで、終点ノードがノード番号ｎ１−７のノードである
場合、探索結果は図３（ｃ）に示す如くなり、経路は、
図に矢印で示す如く、ノード番号ｎ１−７のノードから
、ノード番号ｎ１−４のノード，ノード番号ｎ１−２の
ノード，ノード番号ｎ１−１のノードへと順に確定され
ることとなる。

【００３７】なおこうした経路探索のための重み計算等
については、従来より周知であるので、詳細については
説明を省略する。また本実施例においては、ステップ１
００にて決定された探索区画に沿って経路探索を行なう
上記ステップ１１０〜ステップ２２０の処理が、経路探
索手段に相当する。

【００３８】以上説明したように、本実施例では、道路
情報を単に階層化するだけでなく、各階層（第１，第２
，第３レベル）の道路情報を、道路地図を分割した各ブ
ロック毎に、その周囲のブロックとのオーバラップ領域
を含めた形で作成しているため、隣接する区画を利用し
て経路探索を行うために、従来のように道路上には実際
に存在しない連結地点情報を作成する必要がなく、外部
記憶装置６に格納する地図データを道路地図を用いて簡
単に作成することができる。また２個以上の区画を用い
て経路探索を行なう場合、従来のように連結地点の重み
計算等を行なう必要がなく、しかもオーバラップ領域内
でのノードについては前回の探索結果を利用できるため
、探索に要する時間が短くなり、そのデータ量も少なく
することができる。

【００３９】また本実施例では、最上位の階層（即ち第
１レベル）の道路情報は、全国を関東，東海，近畿…と
いった大きな地区毎に分割し、その分割した第１ブロッ
クの２つを各々結ぶ広域の地域を移築閣として位置区画
としていることから、例えば東京から広島といった離隔
距離の大きな地点間の経路を探索する場合にも、この第
１レベルの区画を利用することにより、図９に示したよ
うに最大５個の区画によって経路探索を行なうことが可
能となり、これによっても経路の探索時間を短縮できる
と共に、そのデータ量を少なくすることができる。

【００４０】また更に本実施例では、経路探索を開始す
る前に探索区画を決定するため、経路探索に要するより
大まかな計算量を前もって推定することができる。この
ため使用者に対して予想探索時間を提示することができ
る。また出発地側の区画と目的地側の区画とを探索した
後、区画判定を行ない、次の探索区画を決定して、再度
経路探索を行なう従来装置のように、経路探索中に無駄
な判定処理を実行する必要がないため、これによっても
探索時間を短縮できる。

【００４１】また上記のように本実施例によれば、経路
の探索時間を短縮することができると共に、経路探索の
データ量を少なくすることができるため、探索結果を格
納しておくメモリの容量を小さくすることができる。ま
たメモリ容量に余裕があれば、探索区画の大きさを広げ
て、経路の最適性を向上させることもできる。

【００４２】なお上記実施例では、出発地と目的地との
２地点の位置関係がどのようなときに、どのような探索
区画の限定を行なうかについては詳しく説明しなかった
が、こうした探索区画の決定に際しては、予め２地点の
位置関係に対応する探索区画パターンを作成しておき、
これを地図データと共に外部記憶装置に格納しておけば
よい。そしてこうすれば、地図データの更新時に、その
データに対応して探索区画パターンを変更することも可
能となる。

【００４３】また重み計算に用いる係数を各区画毎に設
定し、これを地図データと共に外部記憶装置に格納して
おき、重み計算を行なう際には、各区画毎に係数を変更
するようにすれば、経路の最適性をより向上させること
もできる。

【００４４】また次に上記実施例では、第２レベルの道
路情報の一区画は５×５個の第２ブロックからなり、第
３レベルの道路情報の一区画は３×３個の第３ブロック
からなるものとして説明したが、これら各レベルの道路
情報の一区画の領域は、他のブロックとのオーバラップ
領域を有する領域であれば同一ブロック数でなくてもよ
く、例えば道路の粗密等に応じて、第２レベルの道路情
報を、第２ブロック５×５個の区画と，８×８個の区画
との２種類とし、第３レベルの道路情報を、第３ブロッ
ク３×３個の区画と，６×６個の区画と，１２×１２個
の区画との３種類としてもよい。

【００４５】そしてこのように一区画のブロック数を種
々設定するようにした場合、ブロック数の少ない区画の
道路情報には、その区画を含む道路情報を有するブロッ
ク数の多い区画を表すデータだけを入れておき、実際の
検索はそのブロック数の多い区画の道路情報を用いて行
うようにすれば、地図データをより少なくすることがで
きる。

【００４６】つまり例えば図１１に示す０から１５のブ
ロックの道路情報のうち、０のブロックに対する道路情
報には、６×６個のブロックからなる区画（図１１に示
す全区画）を設定して、実際の地図データを格納し、１
〜１５の各ブロックに対する道路情報には、そのブロッ
クを中心とする３×３個のブロックからなる区画を設定
して、実際の地図データは０のブロックに対する道路情
報に含まれている旨を表すデータを格納するようにすれ
ば、１〜１５の各ブロックの道路情報には実際の地図デ
ータを入れる必要がないので、データ量を少なくするこ
とができる。またこの場合、経路探索時に探索区画とし
て１〜１５のブロックの区画が決定されたときには、０
のブロックに対する道路情報を使用する必要があり、探
索範囲が増加するが、探索区画として、例えば９，１０
，１１のブロックに対応する３つの区画が決定されたと
きであっても、０のブロックに対する一つの道路情報の
みで経路探索を行なうことができるため、結果的には探
索速度を向上することが可能となる。

【００４７】

【発明の効果】以上詳述したように、本発明の経路探索
装置においては、道路情報が単に階層化されているだけ
でなく、各階層の道路情報は、道路地図を分割した各ブ
ロック毎に、その周囲のブロックとのオーバラップ領域
を含めた形で作成されているため、隣接する２つの道路
情報を利用して経路探索を行うために、従来のように道
路上には実際に存在しない連結地点情報を作成しておく
必要がなく、地図データを道路地図から簡単に作成する
ことができる。また複数の道路情報を用いて経路探索を
行なう場合、従来のように連結地点の重み計算等を行な
う必要がなく、しかもオーバラップ領域内での経路探索
には先に探索を行った他の道路情報の探索結果を利用で
きるため、探索に要する時間が短くなり、その探索結果
のデータ量も少なくすることができる。

【００４８】また本発明では、経路探索を開始する前に
経路探索に使用する道路情報を決定するため、経路探索
に要するより大まかな計算量を前もって推定することが
できる。このため使用者に対して予想探索時間を提示す
ることもできる。また出発地側の区画と目的地側の区画
とを探索した後、区画判定を行ない、次の探索区画を決
定して、再度経路探索を行なう従来装置のように、経路
探索中に無駄な判定処理を実行する必要がないため、こ
れによっても探索時間を短縮できる。

【図面の簡単な説明】

【図１】本発明の構成を例示するブロック図である。

【図２】実施例のナビゲーション装置の概略構成を表す
ブロック図である。

【図３】実施例の道路情報の構成及びこの道路情報に基
づく経路の探索結果を表す説明図である。

【図４】実施例の制御装置にて実行される探索処理を表
すフローチャートである。

【図５】実施例の探索処理において探索区画を決定する
際の手順を説明するフローチャートである。

【図６】実施例の探索処理において前回の区画探索結果
を今回の探索区画に反映する際の手順を説明するフロー
チャートである。

【図７】第３レベルの区画のみにより探索区画が決定さ
れた場合の説明図である。

【図８】第２及び第３レベルの区画により探索区画が決
定された場合の説明図である。

【図９】第１〜第３レベルの区画により探索区画が決定
された場合の説明図である。

【図１０】決定した探索区画の中にデータが存在しない
区画がある場合の探索区画を説明する説明図である。

【図１１】第２及び第３レベルの区画の設定方法の一例
を説明する説明図である。

【符号の説明】

２…入力装置　　　　４…表示装置　　　　６…外部記
憶装置　　　　８…制御装置 Ｋ１…第１区画　　　　Ｋ２１…始点第２区画　　　　
Ｋ２２…終点第２区画 Ｋ３１…始点第３区画　　　　Ｋ３２…終点第３区画　
　　　Ｋ３３…隣接区画

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　道路地図を所定の大きさで複数に分割
   した各ブロック毎に作成され、当該ブロックを囲む周囲
   のブロックとのオーバラップ領域を含む所定領域を一区
   画とする複数の道路情報が、一ブロックの大きさが異な
   る各階層毎に記憶された地図データ記憶手段と、外部か
   ら上記道路地図上の２つの地点が指定されると、上記地
   図データ記憶手段に記憶された一ブロックの大きさが小
   さい下位の階層の道路情報から順に、少なくとも上記指
   定された２地点のいずれか一つを含む道路情報，及び該
   ２地点を含む一つの道路情報又は上記オーバラップ領域
   により該２地点を接続可能な２つの道路情報を選択して
   ゆき、該２地点を接続するのに必要な道路情報を決定す
   る道路情報決定手段と、該道路情報決定手段により決定
   された道路情報に基づき、上記２地点の内の一方の地点
   から他方の地点に至る経路を探索する経路探索手段と、
   を備えたことを特徴とする経路探索装置。