[0001]【発明の属する技術分野】本発明は、出発地から目的地までの最短経路を探索するナビゲーション装置に関する。[0002]【従来の技術】ナビゲーション装置は、地理の不案内な運転者に対して目的地までコース案内を行うものであり、近年、このナビゲーション装置の開発が盛んに行われている。conducted.【0003】ナビゲーション装置は、予め走行前に出発地及び目的地を入力することによって出発地から目的地までのコースを設定し、その設定されたコースに従ってナビゲーションを行うものである。ナビゲーションでは、コースを指示する場合、CRT画面に地図を表示しその上にコースを重ねて表示したり、また、或るものは、予め設定されたコースに従って次に曲がるべき交差点に関する情報として、次に曲がるべき交差点までの距離を数字やグラフ、特徴的な写真で表示したりさらには音声出力も併用するものもある。output.【0004】道路網にあっては、一般に出発地から目的地までの間に複数のコースが存在するのが普通である。destination.そのため、ナビゲーション装置において、出発地及び目的地が入力されると、その間における最短時間或いは最短距離のコース(最短コース)を探索する経路探索の手法を採用する試みがなされている。その1つとして、例えば図12に示すように四叉路の交差点の場合には、右左折、直進、Uターンを表現するために8つのノードと16本の有向リンクで交差点を表し、また、交差点相互を接続する道路枝は2本の有向リンクで表す方法(例えば特開昭62−82316号公報)が報告されている。JP-62-91811号公報)が報告されている。[0005]【発明が解決しようとする課題】しかしながら、上記前者の方法は、交差点での右左折禁止を全て有向リンクで表現しているので、データ量が多くなり記憶容量が多くなるという問題がある。後者の方法は、交差点での右左折禁止をネットワークデータとは別にして交差点番号でもっているので、経路探索時の検索に要する処理が多くなり、処理速度が遅くなるという問題がある。slow.【0006】本発明は、上記の問題点を解決するものであって、記憶データ量を少なくし右左折禁止データや案内不要データの判断も含めて高速に経路探索することができるナビゲーション装置を提供することを目的とするものである。it,該探索した経路に基づき案内情報を出力することを特徴とするものである。前記道路データに格納された経路探索を行うための情報に基づき経路を探索し、該探索された経路と前記道路データに格納された道路を表示するための座標に関する情報に基づき経路を表示することを特徴とするものである。前記道路データに格納された情報に基づき案内情報を出力するので、道路単位で道路における情報、及び始点または終点に接続する道路に関する情報に基づき案内情報の出力を行い、処理を簡素化できる。前記道路データの該道路における情報及び前記接続する道路に関する情報に基づき経路を探索して、該探索した経路に基づき案内情報を出力するので、接続する道路に関する情報として、右左折禁止情報や案内不要情報を設定することにより、経路の探索や案内情報の出力で無駄な探索処理や案内処理をなくすことができ、処理の高速化を図ることができる。前記道路データに格納された経路探索を行うための情報に基づき経路を探索し、該探索された経路と前記道路データに格納された道路を表示するための座標に関する情報に基づき経路を表示することにより、道路データを道路の表示と経路探索に共用することができ、記憶手段に格納するデータの量を大幅に削減することができる。実施の形態を図面を参照しつつ説明する。invention,図2は道路網の例を示す図、図3は交差点データの例を示す図、図4は道路データの例を示す図、図5はノードデータの例を示す図、図6は経路探索処理の流れを説明するための図である。5は交差点列及びノード列生成部、6は交差点列及びノード列データ、7はナビゲーション部を示す。交差点データ1、道路データ2、及びノードデータ3は記憶装置に格納され、経路探索処理部4からナビゲーション部7により案内情報を出力する経路案内処理部を構成している。経路探索処理部4は、右左折禁止等の進入禁止道路を除き交差点から周囲道路を検索する周囲道路検索サブルーチン、道路幅の広狭、案内の要否その他最適経路を演算するのに必要な条件を設定する最適経路条件設定サブルーチン、経路探索の終了を判定する終了条件サブルーチンを有し、指定された出発地から目的地までの最適経路を探索するものである。交差点列及びノード列生成部5は、経路探索処理部4により最適経路が探索されると、その経路に沿った交差点列及びノード列データ6を生成するものであり、この交差点列及びノード列データ6によりナビゲーション(案内情報の出力)を行うのがナビゲーション部7である。従って、ナビゲーション部7は、データ処理手段、表示や音声の出力手段を有し、コース走行の所定の地点で交差点列及びノード列データ6を読み出し、表示出力や音声出力によりコース案内を行う。example,道路番号○1〜○8からなるものとした場合、交差点データについては図3、道路データについては図4、ノードデータについては図5に示すようなデータ構成となっている。終点となっている道路のうち一番番号の小さい道路番号、信号の有無からなる。ノード数、ノード列データの先頭アドレス、長さ等からなる。なり、道路データから明らかなように道路番号の単位は複数個のノードからなる。ノードデータは道路上の1地点に関するデータであり、ノード間を接続するものをアークと呼ぶと、複数のノード列のそれぞれの間をアークで接続することによって道路が表現される。道路番号○1に関して見ると、道路データよりノード数15からなりノードデータの先頭アドレスが100であることから、道路番号○1は、100から114までのアドレスのノードデータで構成されることになる。Become.【0018】これらのネットワークデータによると、例えば交差点番号Iに着目した場合、ここを始点とするコースでは、まず、交差点データの始点情報から道路番号○1、次にこの道路番号○1に関する道路データの「同じ始点を持つ道路のうち番号が次のもの」から道路番号○7が検索される。道路番号○7における同様の情報では、逆に道路番号○1であることから周囲道路として他の道路番号のものはないことが判断できる。これは、終点に関しても同様である。2において、道路番号○5から○6へは右左折禁止等のため進入できず、進入可能な道路は道路番号○8だけとなる。従って、この道路番号○8への進入は案内不要となる。このように特に道路データでは、右左折禁止等の進入禁止の道路番号と案内不要の道路番号をもっていることにより、情報記憶の容量を少なくし、また経路探索を容易に行えるようにしている。ease.【0019】次に上記のネットワークデータにより経路探索する場合の処理の流れを図6により説明する。1は目的地の両隣りの交差点番号である。「0」が未探索、「1」が探索中、「2」が探索終了を示す。この初期設定によりまず全ての交差点が未探索となり、出発地からの距離が無限大となる。出発地からの道路番号をセットする。0を始点とする周囲道路を検索する。周囲道路があるか否かを調べる。NOの場合には処理○11に移る。最適経路条件設定サブルーチンを実行し、最適経路を探索するための道路状況その他の条件を設定する。道路の長さをlとする。その道路の終点の交差点までの距離Pを計算する。