(57)【要約】【課題】  無駄な経路を削除することによって、経路探索のさらなる適正化を図ることができる「経路探索方法」を提供すること。【解決手段】  複数のレベルのリンクによって構成される誘導経路の経路データを作成した後、この経路データのうちの最下層のレベルのリンク以外のリンクを前記最下層のレベルのリンクに変換した経路データを作成するとともに、この変換後における経路データをたどって同一のリンクが存在する場合に、この同一のリンクのうちのいずれか一方および両リンクの間に存在する他のリンクを削除することによって、経路データの補正を行うこと。【選択図】      図２
2005234041.tif 000002
【特許請求の範囲】
【請求項１】
道路の交点に対応するデータとしてのノードと、前記ノード間を接続する道路等の接続部に対応するデータとしてのリンクとを有し、かつ、前記ノードおよび前記リンクが、上層のレベルほど詳細度が低下し、探索領域範囲が拡大するように複数層のレベルに階層化されて管理されてなる地図データに基づいて、目的地への誘導経路の経路データを作成することによって、目的地への誘導経路の探索を行う経路探索方法であって、
複数のレベルのリンクによって構成される誘導経路の経路データを作成した後、この経路データのうちの最下層のレベルのリンク以外のリンクを前記最下層のレベルのリンクに変換した経路データを作成するとともに、この変換後における経路データをたどって同一のリンクが存在する場合に、この同一のリンクのうちのいずれか一方および両リンクの間に存在する他のリンクを削除することによって、経路データの補正を行うことを特徴とする経路探索方法。
【請求項２】
道路の交点に対応するデータとしてのノードと、前記ノード間を接続する道路等の接続部に対応するデータとしてのリンクとを有し、かつ、前記ノードおよび前記リンクが、上層のレベルほど詳細度が低下し、探索領域範囲が拡大するように複数層のレベルに階層化されて管理されてなる地図データに基づいて、目的地への誘導経路の経路データを作成することによって、目的地への誘導経路の探索を行う経路探索方法であって、
レベルｎ（ｎは整数、以下同様）のリンクとレベルｎ＋１のリンクとによって構成される誘導経路の経路データを作成した後、この経路データのうちのレベルｎ＋１のリンクをレベルｎのリンクに変換した経路データを作成するとともに、この変換後における経路データをたどって同一のリンクが存在する場合に、この同一のリンクのうちのいずれか一方および両リンクの間に存在するリンクを削除することによって、経路データの補正を行うことを特徴とする経路探索方法。
【請求項３】
前記レベルｎ＋１のリンクのうち、レベルｎのリンクの直後の最初のレベルｎ＋１のリンクのみをレベルｎのリンクに変換することを特徴とする請求項２に記載の経路探索方法。
【請求項４】
前記誘導経路の探索を、自車位置側および目的地側の双方から行うことを特徴とする請求項１乃至請求項３のいずれか１項に記載の経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索方法に関し、特に、複数のレベルに階層化されて管理された地図データに基づいて、目的地への誘導経路を探索するのに好適な経路探索方法に関する。
【背景技術】
【０００２】
従来から、車載用のナビゲーション装置においては、地図データに基づいて目的地への誘導経路を探索するようになっていた。
【０００３】
前記地図データは、交差点や分岐等の道路の交点に対応するデータとしてのノードと、前記ノード間を接続する道路や車線等の接続部に対応するデータとしてのリンクとを有している。そして、これらノードおよびリンクは、表示画面上に表示される地図情報の詳細度および探索領域範囲に応じて複数層のレベルに階層化されて管理されている。
【０００４】
なお、現状においては、レベル０、レベル１およびレベル２の三階層のレベルが採用されている。これらのうち、最下層であるレベル０は、狭い領域における道路情報を最も詳しく知ることができる地図データであり、このレベル０の地図には、高速道等の大きな道路だけでなく一般道等の小さな道路も詳細に記述されている。最上層であるレベル２は、粗い記述ながら広い領域を一望することができる地図データであり、このレベル２の地図には、主として高速道や幹線道路等の大きな道路が記述されている。レベル１は、詳細度および探索領域範囲ともにレベル０とレベル２との中間に位置する地図データである。
【０００５】
また、大きな道路の交差点等に対応するノードのように、異なるレベルの双方に存在するノードは、特に、接続ノードと称されており、この接続ノードを介して下層レベルでの探索結果を上層レベルに反映させることができ、探索レベルを複数のレベルによって構成させることができる。
【０００６】
また、各レベルは、さらに区画と称される矩形領域に分割されて管理されている。
【０００７】
このような地図データに基づいて経路を探索する方法としては、通常は、最下層のレベルから探索を開始し、必要に応じて接続ノードにおいて上層のレベルに探索を移行することによって、コストの低い最適な経路を探索するようになっていた。なお、コストとは、距離を基に、道路幅員、道路種別（一般道か高速道か等）および右左折等に応じた定数を乗じることによって算定されたものである。
【０００８】
従って、前述の方法によって探索された誘導経路は、最下層のレベルのリンクから始まり、接続ノードを通じて上層のレベルのリンクへと続くような複数のレベルのリンクによって構成される経路データに対応する誘導経路である場合が通常であった。
【０００９】
その一例として、図９に示す経路データは、レベル０のリンクａ（Ｌｖ０ Ｌｎｋ ａ）、リンクｂ（Ｌｖ０ Ｌｎｋ ｂ）、リンクｃ（Ｌｖ０ Ｌｎｋ ｃ）、リンクｄ（Ｌｖ０ Ｌｎｋ ｄ）と、レベル１のリンクＡ（Ｌｖ１ Ｌｎｋ Ａ）とが、探索された順番に従って順次配列されたリンクの集合データであり、この経路データに対応する誘導経路は、図１０および図１１に示すようになる。
【００１０】
【特許文献１】特開平０９−２５７５０５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、従来の経路探索方法においては、コストのみを主体とした経路の探索を行っていたため、探索された経路の品位が問題となる場合があった。
【００１２】
例えば、図１０および図１１に示したようなレベル０のリンクとレベル１のリンクとで構成される経路データに対応する誘導経路について考えてみる。
【００１３】
ここで、図１０および図１１のように、現在走行しているレベル０のリンクからレベル１のリンクに上がれる接続ノードが、現在走行しているレベル０のリンクａの進行方向における後方すなわち目的地から遠ざかる方向にしか存在しない場合、レベル０の迂回リンクｂ、ｃ、ｄを通って当該接続ノードが存在する後方位置まで戻ることを余儀なくされていた。
【００１４】
このような場合、データの上ではレベルが異なるものであるが、実際は同一である経路を二回通ることになり、極めて効率の悪い経路となってしまっていた。図１０および図１１の例でいえば、レベル０のリンクａと、レベル１のリンクＡの一部（リンクａとの対向部）とは、データ上ではレベルが異なるデータであるが、実際は同一の道路であり、リンクａから迂回リンクｂ、ｃ、ｄを経た後にリンクＡを通ると、同一の道路を二度通ることになる。
【００１５】
このような問題を解決するために、上層に上がれるノードを探索する範囲を広げることが考えられるが、この場合、探索の際に地図データを広範囲に読み込む必要があり、探索時間が長くなってしまう。
【００１６】
また、データベースを改変することによって、上層に上がれる接続ノードを現在進行しているリンクにおける自車位置の進行方向の前方に新たに設けることも考えられる。具体的には、図１０のレベル１のリンクＡにおける自車位置の進行方向の前方位置であって、レベル０固有のノードに対応する位置に、図１０において破線で示す新たなノードを設け、このノードでリンクＡを分断することにより、分断したレベル１のリンクを前記新たなノードを通じてレベル０のリンクａに接続することが考えられる。
【００１７】
しかし、このような場合においても、長い探索時間を要する上に、個別問題として、その後の年次更新にも対応する必要があるため、作業管理工数が増えてしまう。
【００１８】
そこで、本発明は、このような問題点に鑑みなされたものであり、経路データに対して無駄な経路を削除する補正を行うことによって、経路探索のさらなる適正化を図ることができる経路探索方法を提供することを目的とするものである。
【課題を解決するための手段】
【００１９】
前述した目的を達成するため、本発明に係る経路探索方法の特徴は、道路の交点に対応するデータとしてのノードと、前記ノード間を接続する道路等の接続部に対応するデータとしてのリンクとを有し、かつ、前記ノードおよび前記リンクが、上層のレベルほど詳細度が低下し、探索領域範囲が拡大するように複数層のレベルに階層化されて管理されてなる地図データに基づいて、目的地への誘導経路の経路データを作成することによって、目的地への誘導経路の探索を行う経路探索方法であって、複数のレベルのリンクによって構成される誘導経路の経路データを作成した後、この経路データのうちの最下層のレベルのリンク以外のリンクを前記最下層のレベルのリンクに変換した経路データを作成するとともに、この変換後における経路データをたどって同一のリンクが存在する場合に、この同一のリンクのうちのいずれか一方および両リンクの間に存在する他のリンクを削除することによって、経路データの補正を行う点にある。
【００２０】
そして、このような方法によれば、まず、通常通りの探索方法に従って誘導経路を探索した後、この探索された誘導経路の経路データに対して無駄な経路を削除する補正を行うことによって、同一の経路を複数回通ることを回避することができる無駄の少ない誘導経路を適正かつ効率的に探索することがことが可能となる。
【００２１】
また、本発明に係る経路探索方法の特徴は、道路の交点に対応するデータとしてのノードと、前記ノード間を接続する道路等の接続部に対応するデータとしてのリンクとを有し、かつ、前記ノードおよび前記リンクが、上層のレベルほど詳細度が低下し、探索領域範囲が拡大するように複数層のレベルに階層化されて管理されてなる地図データに基づいて、目的地への誘導経路の経路データを作成することによって、目的地への誘導経路の探索を行う経路探索方法であって、レベルｎ（ｎは整数、以下同様）のリンクとレベルｎ＋１のリンクとによって構成される誘導経路の経路データを作成した後、この経路データのうちのレベルｎ＋１のリンクをレベルｎのリンクに変換した経路データを作成するとともに、この変換後における経路データをたどって同一のリンクが存在する場合に、この同一のリンクのうちのいずれか一方および両リンクの間に存在するリンクを削除することによって、経路データの補正を行う点にある。
【００２２】
そして、このような方法によれば、まず、通常通りの探索方法に従って誘導経路を探索した後、この探索された誘導経路の経路データに対して無駄な経路を削除する補正を行うことによって、同一の経路を複数回通ることを回避することができる無駄の少ない誘導経路を適正かつ効率的に探索することがことが可能となる。
【００２３】
さらに、本発明に係る経路探索方法の特徴は、レベルｎ＋１のリンクのうち、レベルｎのリンクの直後の最初のレベルｎ＋１のリンクのみをレベルｎのリンクに変換する点にある。
【００２４】
そして、このような方法によれば、レベルｎ＋１のリンクのうち、経路データの補正を行うために必要最小限とされるリンクのみをレベルｎに変換することによって、探索時間のさらなる短縮化を図ることが可能となる。
【００２５】
さらにまた、本発明に係る経路探索方法の特徴は、前記誘導経路の探索を、自車位置側および目的地側の双方から行う点にある。
【００２６】
そして、このような方法によれば、さらに無駄の少ない誘導経路をより効率的に探索することが可能となる。
【発明の効果】
【００２７】
本発明に係る経路探索方法によれば、簡便な方法によって経路探索の適正化を図ることができる経路探索方法を実現することができる。
【００２８】
また、経路探索のさらなる効率化を実現することができる。
【発明を実施するための最良の形態】
【００２９】
以下、本発明に係る経路探索方法の実施形態について、図１乃至図８を参照して説明する。なお、従来と基本的構成の同一もしくはこれに類する箇所については、同一の符号を用いて説明する。
【００３０】
図１は、本実施形態における経路探索方法を実施するために用いるナビゲーション装置である。
【００３１】
図１に示すように、前記ナビゲーション装置１は、ナビゲーションコントローラ２を有しており、このナビゲーションコントローラ２は、ＣＰＵ、ＲＯＭおよびＲＡＭ等を用いて所定のプログラムを実行することによって、ナビゲーション装置全体の動作を制御するようになっている。
【００３２】
前記ナビゲーションコントローラ２には、ディスク読取装置３が接続されており、このディスク読取装置３には、地図データが格納されたＤＶＤやＣＤ等のディスク４が装填可能とされている。前記ディスク読取装置３は、前記ナビゲーションコントローラ２の制御によって、前記ディスク４から地図データの読み出しを可能とされている。
【００３３】
なお、前記ディスク４に格納された地図データは、前述のように交差点や分岐等の道路の交点に対応するデータとしてのノードと、前記ノード間を接続する道路や車線等の接続部に対応するデータとしてのリンクとを有している。そして、これらノードおよびリンクは、上層のレベルほど詳細度が低下し、探索領域範囲が拡大するように複数のレベルに階層化されて管理されている。
【００３４】
また、前記ナビゲーションコントローラ２には、リモコンユニット５が接続されている。このリモコンユニット５は、上下左右の方向を指定するジョイスティック、テンキー、各種の設定を確定する決定キー等の各種の操作キーを有しており、操作内容に応じた信号をナビゲーションコントローラ２に出力するようになっている。
【００３５】
さらに、前記ナビゲーションコントローラ２には、車両位置検出部７が接続されており、この車両位置検出部７は、例えば、ＧＰＳ受信機、方位センサ、距離センサ等の装備によって所定のタイミングで自車位置（経度、緯度）の検出を行い、検出結果を出力するようになっている。
【００３６】
また、前記ナビゲーションコントローラ２には、ディスプレイ装置８が接続されており、このディスプレイ装置８は、ナビゲーションコントローラ２から出力される描画データに基づいて、自車位置周辺の地図画像等の各種画像を表示するようになっている。
【００３７】
次に、前記ナビゲーションコントローラ２の構成について更に詳述する。
【００３８】
前記ナビゲーションコントローラ２は、前記ディスク読取装置３の出力側に接続された地図バッファ９を有しており、この地図バッファ９には、前記ディスク読取装置３が前記ディスク４から読み取った地図データが一時的に格納されるようになっている。
【００３９】
前記地図バッファ９の出力側には、地図描画部１０および操作画面発生部１２が接続されている。前記地図描画部１０は、前記地図バッファ９に格納された地図データに基づいて、地図画像を表示するための地図描画データを作成するようになっている。また、前記操作画面発生部１２は、ユーザが各種の操作指示を行うために必要な操作画面を表示するための描画データを作成するようになっている。
【００４０】
前記地図描画部１０の出力側には、ＶＲＡＭ１３が接続されており、このＶＲＡＭ１３には、地図描画部１０から出力される地図描画データが一時的に格納されるようになっている。
【００４１】
また、前記ナビゲーションコントローラ２は、前記リモコンユニット５の出力側に接続された入力処理部１４を有しており、この入力処理部１４は、リモコンユニット５を用いて行われる各種操作指示に対応する動作を行うための指令をナビゲーションコントローラ２の各部に向けて出力するようになっている。
【００４２】
さらに、前記ナビゲーションコントローラ２は、前記車両位置検出部７の出力側に接続された車両位置計算部１６を有している。この車両位置計算部１６は、前記車両位置検出部７から出力される検出データに基づいて、車両の現在位置および方位を計算するとともに、計算した車両の現在位置が地図データの道路上にない場合は、これを修正するマップマッチング処理を行うようになっている。
【００４３】
前記入力処理部１４および前記車両位置計算部１６の出力側には、地図読出制御部１７が接続されており、この地図読出制御部１７は、前記車両位置計算部１６により算出される車両の現在位置や、入力処理部１４からの要求等に応じて、所定範囲の地図データの読み出し要求を前記ディスク読取装置３に出力するようになっている。
【００４４】
前記地図バッファ９、前記入力処理部１４および前記車両位置計算部１６の出力側には、経路データ作成処理部１９が接続されており、この経路データ作成処理部１９は、所定の出発地と目的地との間を所定の条件下で結ぶ走行経路の経路データを作成することによって、目的地までの誘導経路の経路探索を行うようになっている。
【００４５】
前記経路データ作成処理部１９の出力側には、経路メモリ２０が接続されており、この経路メモリ２０は、前記経路データ作成処理部１９によって作成された経路データを記憶するようになっている。
【００４６】
前記経路メモリ２０の出力側には、経路データ変換処理部２１が接続されており、この経路データ変換処理部２１は、前記経路データ作成処理部１９によって作成された経路データのうちの最下層のレベルのリンク以外のリンクを前記最下層のレベルのリンクに変換した経路データを作成するようになっている。
【００４７】
前記経路データ変換処理部２１の出力側には、変換経路メモリ２２が接続されており、この変換経路メモリ２２は、前記経路データ変換処理部２１によって作成された変換後の経路データを記憶するようになっている。
【００４８】
前記変換経路メモリ２２の出力側には、経路データ最適化処理部２４が接続されている。この経路データ最適化処理部２４は、前記経路データ変換処理部２１によって作成された経路データをたどって同一のリンクが存在する場合に、この同一のリンクのうちのいずれか一方および両リンクの間に存在する他のリンクを削除することによって、経路データの補正を行うようになっている。
【００４９】
前記経路データ最適化処理部２４の出力側には、最適経路メモリ２５が接続されており、この経路メモリ２５は、前記経路データ最適化処理部２４によって補正された経路データを記憶するようになっている。
【００５０】
前記最適経路メモリ２５には、経路表示処理部２６が接続されており、この経路表示処理部２６は、最適経路メモリ２５に記憶されている最適誘導経路を地図上に重ねて表示するための描画データを生成してＶＲＡＭ１３に出力するようになっている。
【００５１】
また、前記最適経路メモリ２５には、案内データ作成処理部２８が接続されている。この案内データ作成処理部２８は、前記最適経路メモリ２５に記憶されている経路データに基づいて、所定のタイミングで交差点案内表示等の細かな案内処理を行うための描画データを案内データとして作成してＶＲＡＭ１３に出力するようになっている。
【００５２】
そして、前記ＶＲＡＭ１３および前記操作画面発生部１２の出力側には、画像合成部２９が接続されており、この画像合成部２９は、前記ＶＲＡＭ１３から読み出した描画データと、前記操作画面発生部１２から出力される描画データとを重ね合わせて画像合成を行うとともに、合成描画データをディスプレイ装置８に出力するようになっている。
【００５３】
次に、図２は、上記の構成を有するナビゲーション装置１を用いて本実施形態における経路探索方法を実施する場合のフローチャートである。
【００５４】
本実施形態においては、まず、図２のステップ１（ＳＴ１）において経路探索処理を開始するとともに、前記ディスク４から読み出した地図データに基づいて、前記経路データ作成処理部１９によって目的地までの誘導経路の経路データを作成する。
【００５５】
前記経路データ作成処理部１９によって作成される経路データは、コストを主体として従来からなされていた通常の経路データであり、図９に示したような同一の経路を二度通るような複数のレベルのリンクによって構成される経路データが作成される場合がある。
【００５６】
ステップ１（ＳＴ１）において作成した経路データは、ステップ２（ＳＴ２）において前記経路メモリ２０に記憶させる。
【００５７】
次いで、ステップ３（ＳＴ３）においては、前記経路データ変換処理部２１によって、経路データのうちの最下層のレベルのリンク以外の上層のレベルのリンクを最下層のレベルのリンクに変換した経路データを作成する経路データ変換処理を行う。
【００５８】
簡単な例としては、前記経路データ作成処理部１９によって作成された経路データが、図９に示したようなレベル０のリンクａ、ｂ、ｃ、ｄおよびレベル１のリンクＡのデータ配列によって構成される経路データである場合は、変換後の経路データは、図３に示すようなレベル０のリンクａ、ｂ、ｃ、ｄ、ａ、ｅのデータ配列によって構成される経路データとなる。この経路データに対応する誘導経路は、図４に示すようなリンクａに対応する経路を二度通る誘導経路となる。
【００５９】
なお、前記経路データ変換処理部２１によって変換される上層のレベルのリンクは、最下層のレベルのリンクの直後の最初のリンクのみにすることが望ましい。図９の例でいえば、リンクＡの後に、リンクＡと同じレベル１に属するリンクＢ（図示せず）が続く場合においても、レベルＡのみをレベル０のリンクに変換することが望ましい。
【００６０】
そのようにすれば、不要な変換処理を避けることができ、経路探索をさらに迅速に行うことができる。
【００６１】
ステップ３（ＳＴ３）において作成した経路データは、次のステップ４（ＳＴ４）において前記変換経路メモリ２２に記憶させる。
【００６２】
次いで、ステップ５（ＳＴ５）においては、前記経路データ最適化処理部２４によって、経路データの最適化処理を行う。
【００６３】
すなわち、ステップ４（ＳＴ４）において作成した経路データのうちの最下層のレベルのリンクをたどって同一のリンクが存在する場合に、この同一のリンクのうちのいずれか一方および両リンクの間に存在する他の最下層のレベルのリンクを削除することによって、経路データの補正を行う。
【００６４】
簡単な例としては、前記経路データ変換処理部２１によって作成された経路データが、図３に示したようなレベル０のリンクａ、ｂ、ｃ、ｄ、ａ、ｅによって構成される経路データである場合は、リンクｂ、ｃ、ｄ、ａが削除されることによって、補正後の経路データとして図５に示すようなリンクａ、ｅのみからなる経路データが得られる。この経路データに対応する誘導経路は、図６に示すように、同一の経路を二度通ることを回避することができる効率的な誘導経路となる。
【００６５】
そして、ステップ５（ＳＴ５）において作成した経路データは、次のステップ６（ＳＴ６）において前記最適経路メモリ２５に記憶される。
【００６６】
次いで、ステップ７（ＳＴ７）においては、前記案内データ作成処理部２８によって、前記最適経路メモリ２５に記憶されている経路データに基づいて案内処理を行うための案内データを作成する案内データ作成処理を行う。
【００６７】
同時に、ステップ８（ＳＴ８）においては、前記経路表示処理部２６によって前記最適経路メモリ２５に記憶されている最適誘導経路を地図上に重ねて表示するための描画データを生成してＶＲＡＭ１３に出力する経路表示処理を行う。
【００６８】
次いで、ステップ９（ＳＴ９）においては、ステップ７（ＳＴ７）において作成した案内データをＶＲＡＭ１３に記憶させる。
【００６９】
最後に、ステップ１０（ＳＴ１０）において、ＶＲＡＭ１３に記憶させた案内データに基づいた案内処理を行う。
【００７０】
次に、前述した経路探索方法の各工程のうち、経路データ最適化処理工程のさらに詳細な内容について、図７および図８を参照して説明する。
【００７１】
図７の左側に示す最適化処理前の経路データは、レベル０のリンクとレベル１のリンクとによって構成された経路データのうち、レベル０の直後の最初のレベル１のリンクのみがレベル０のリンクに変換された変換処理後の経路データである。
【００７２】
なお、前記最適化処理前の経路データにおいて、レベル０のリンク１１（Ｌｖ０ Ｌｎｋ１１）に続くレベル１のリンク１２（Ｌｖ１ Ｌｎｋ１２）は、前記最初のレベル１のリンクに続く2番目のレベル１のリンクとなる。
【００７３】
そして、前記変換処理後の経路データにおいては、レベル０のリンク１０（Ｌｖ０ Ｌｎｋ１０）が二回登場している。
【００７４】
従って、経路データ最適化処理においては、リンク１０のうちの一方（図において後側のもの）と、両リンク１０の間に存在するレベル０のリンク１１（Ｌｖ０ Ｌｎｋ１１）、リンク１２（Ｌｖ０ Ｌｎｋ１２）、リンク１５（Ｌｖ０ Ｌｎｋ１５）、リンク１４（Ｌｖ０ Ｌｎｋ１４）、リンク１３（Ｌｖ０ Ｌｎｋ１３）を削除する。
【００７５】
この結果、図７の右側に示す最適化処理後の経路データが得られる。
【００７６】
なお、同一のリンクのうち、配列番号が前側のリンクを削除することによって経路データの補正を行うようにしてもよい。
【００７７】
図７の最適化処理をフローチャートとして表すと図８のようになり、この図８のステップ１１（ＳＴ１１）においては、最適化処理前の経路データのリンクについての配列番号をｉと仮定するとともに、最適化処理後の経路データのリンクについての配列番号をｊと仮定し、ｉ、ｊにそれぞれ初期値である０を代入する。
【００７８】
次いで、ステップ１２（ＳＴ１２）においては、ｉ番目のリンクが、最適化処理前の経路データにおける終端のリンクであるか否かを判断し、終端であればステップ１３（ＳＴ１３）に進んで処理を終了し、終端でなければステップ１４（ＳＴ１４）に進む。
【００７９】
ステップ１４（ＳＴ１４）においては、最適化処理前の経路データにおけるｉ番目のリンクを、最適化処理後の経路データにおけるｊ番目のリンクとして確定する処理を行う。
【００８０】
次いで、ステップ１５（ＳＴ１５）において、最適化処理後の経路データにおけるｊ番目のリンクの次のｊ＋１番目のリンクの確定に移行する。
【００８１】
すなわち、まず、ステップ１６（ＳＴ１６）において、最適化処理前の経路データにおけるリンクの配列番号に関与する変数ｘを仮定するとともに、このｘに初期値である１を代入する。
【００８２】
次いで、ステップ１７（ＳＴ１７）において、最適化処理前の経路データにおけるｉ＋ｘ番目のリンクが、経路データ変換処理によって作成されたレベル０のリンク群における終端のリンクであるか否かを判断し、終端であればステップ１８（ＳＴ１８）に進み、終端でなければステップ１９（ＳＴ１９）に進む。
【００８３】
ステップ１８（ＳＴ１８）においては、リンクの番号をｉ＋１にした後に、ステップ１２（ＳＴ１２）に戻る。
【００８４】
ステップ１９（ＳＴ１９）においては、最適化処理前の経路データにおけるｉ＋ｘ番目のリンクが、ｉ番目のリンクと同一であるが否かを判断し、同一である場合はステップ２０（ＳＴ２０）に進み、同一でない場合はステップ２１（ＳＴ２１）に進む。
【００８５】
そして、ステップ２０（ＳＴ２０）においては、リンクの番号をｉ＋ｘ＋１にした後にステップ１２（ＳＴ１２）に戻る。
【００８６】
ステップ２１（ＳＴ２１）においては、リンクの番号を１つ増加させた後にステップ１７（ＳＴ１７）に戻る。
【００８７】
これによって、最適化処理前の経路データにおけるｉ＋ｘ＋１番目のリンクが、最適化処理後の経路データにおけるｊ＋１番目のリンクとして確定する。
【００８８】
この処理は、ｉ番目のリンクと同一のｉ＋ｘ番目のリンクおよびｉ番目のリンクとｉ＋ｘ番目のリンクの間に存在するリンクを削除する処理に相当する。
【００８９】
このようにして、経路データの終端に至るまで各ステップの処理および判断を繰り返すことによって、最適化処理後の経路データにおける各リンクのすべてが確定する。
【００９０】
このフローチャートに、図７の経路データを当てはめると、まず、配列番号ｉ＝０のリンク１０（Ｌｖ０ Ｌｎｋ１０）が、ステップ１４（ＳＴ１４）において配列番号ｊ＝０のリンク１０（Ｌｖ０ Ｌｎｋ１０）として確定する。
【００９１】
次いで、ステップ１５（ＳＴ１５）において、配列番号ｊ＝１のリンクを確定する処理に移行する。
【００９２】
この処理において、配列番号ｉ＝１〜５のリンクであるリンク１１（Ｌｖ０ Ｌｎｋ１１）、リンク１２（Ｌｖ０ Ｌｎｋ１２）、リンク１５（Ｌｖ０ Ｌｎｋ１５）、リンク１４（Ｌｖ０ Ｌｎｋ１４）、リンク１３（Ｌｖ０ Ｌｎｋ１３）は、ともに、ステップ１７（ＳＴ１７）、ステップ１９（ＳＴ１９）、ステップ２１（ＳＴ２１）のループを経るだけで最適化処理後のリンクとしては確定されない。
【００９３】
次いで、配列番号ｉ＝６のリンクであるリンク１０（Ｌｖ０ Ｌｎｋ１０）は、ステップ１９（ＳＴ１９）において、配列番号ｉ＝０のリンク１０（Ｌｖ０ Ｌｎｋ１０）と同一であると判断される。
【００９４】
そして、続くステップ２０（ＳＴ２０）、ステップ１２（ＳＴ１２）を経た後、ステップ１４（ＳＴ１４）において、配列番号ｉ＝７のリンク１１（Ｌｖ０ Ｌｎｋ１１）が、配列番号ｊ＝１のリンクとして確定する。
【００９５】
以上述べたように、本実施形態によれば、経路データに対して無駄なリンクを削除する補正を行うことによって、同一の経路を二度通ることを回避することができる無駄のない誘導経路を簡便に探索することができる。
【００９６】
なお、本発明は、前述した実施の形態に限定されるものではなく、必要に応じて種々の変更が可能である。
【００９７】
例えば、前記実施形態においては、自車位置を誘導経路の探索開始点とした自車位置側からの経路探索について述べているが、目的地を探索開始点とした目的地側からの経路探索を行う場合においても、経路データの補正をともなう本発明の経路探索方法を適用することが好ましい。ここで、目的地側からの経路探索における自車位置側からの経路探索との違いは、経路データの各リンクが目的地側から順次配列される点だけであり、経路データの補正の方法については自車位置側からの探索の場合と全く同じである。
【００９８】
そして、このように自車位置側および目的地側の双方からの経路探索に本発明を適用すれば、さらに無駄の少ない誘導経路をより効率的に探索することが可能となる。
【００９９】
また、前記実施形態においては、レベル０のリンクとレベル１のリンクとによって構成される経路データの補正について述べているが、これに限る必要はない。例えば、経路データがレベル０〜２の3つのレベルのリンクによって構成される場合に、経路データ変換処理によってレベル１のリンクとレベル２のリンクとをレベル０のリンクに変換し、変換後における経路データから無駄なリンクを削除する補正を行うようにしてもよい。
【０１００】
さらに、本実施形態においては、レベル０を最下層としているが、レベル１を最下層とし、レベル３を最上層とする場合にも本発明を有効に適用し得るのは勿論である。
【図面の簡単な説明】
【０１０１】
【図１】本発明に係る経路探索方法を実施するためのナビゲーション装置を示すブロック図
【図２】本発明に係る経路探索方法の実施形態を示すフローチャート
【図３】本発明に係る経路探索方法の実施形態において、経路データ変換処理後における経路データを示す図
【図４】図３の経路データに対応する誘導経路を示す模式図
【図５】本発明に係る経路探索方法の実施形態において、経路データ最適化処理後における経路データを示す図
【図６】図５の経路データに対応する誘導経路を示す模式図
【図７】本発明に係る経路探索方法の実施形態において、経路データ最適化処理をさらに具体的に示す図
【図８】本発明に係る経路探索方法の実施形態において、経路データ最適化処理をさらに具体的に示すフローチャート
【図９】従来から行われていた経路探索方法の一例において、経路データを示す図
【図１０】図９の経路データに対応する誘導経路を立体的に示す模式図
【図１１】図９の経路データに対応する誘導経路を平面的に示す模式図
【符号の説明】
【０１０２】
１  ナビゲーション装置
４  ディスク
１９  経路データ作成処理部
２０  経路データ変換処理部
２４  経路データ最適化処理部
【図１】
2005234041.tif 000003
【図２】
2005234041.tif 000004
【図３】
2005234041.tif 000005
【図４】
2005234041.tif 000006
【図５】
2005234041.tif 000007
【図６】
2005234041.tif 000008
【図７】
2005234041.tif 000009
【図８】
2005234041.tif 000010
【図９】
2005234041.tif 000011
【図１０】
2005234041.tif 000012
【図１１】
2005234041.tif 000013