ナビゲーション装置および誘導経路探索方法
【課題】遠回りの経路が探索されるのを防止し、かつ、最終的な誘導経路を設定するまでの時間を短縮できるようにすることが可能な「ナビゲーション装置および誘導経路探索方法」を提供する。
【解決手段】道路網の情報量に基づいて３つのレベルに階層化された地図データに基づいて探索した現在位置から目的地までの第１の誘導経路の中から、両端のノード間において直線距離に対する第１の誘導経路に沿った距離の比率が所定値より大きい部分経路を抽出し、その部分経路の両端のノード間の経路探索を、最下位レベルを含む地図データに基づいて行うことによって得た第２の部分経路で、第１の誘導経路に含まれる部分経路を置き換えた第２の誘導経路を最終的な誘導経路として設定することにより、最初に探索された誘導経路の中で部分的に遠回りしている部分について最下位レベルを含む地図データに基づいた再探索が行われるようにする。
【解決手段】道路網の情報量に基づいて３つのレベルに階層化された地図データに基づいて探索した現在位置から目的地までの第１の誘導経路の中から、両端のノード間において直線距離に対する第１の誘導経路に沿った距離の比率が所定値より大きい部分経路を抽出し、その部分経路の両端のノード間の経路探索を、最下位レベルを含む地図データに基づいて行うことによって得た第２の部分経路で、第１の誘導経路に含まれる部分経路を置き換えた第２の誘導経路を最終的な誘導経路として設定することにより、最初に探索された誘導経路の中で部分的に遠回りしている部分について最下位レベルを含む地図データに基づいた再探索が行われるようにする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置および誘導経路探索方法に関し、特に、地図データを用いて現在地から目的地までを結ぶ最もコストが小さな経路を自動探索する経路誘導機能を備えたナビゲーション装置に用いて好適なものである。
【背景技術】
【０００２】
一般に、ナビゲーション装置の殆どには、運転者が所望の目的地に向かって道路を間違うことなく容易に走行できるようにした経路誘導機能が搭載されている。この経路誘導機能では、地図データを用いて現在地から目的地までを結ぶ最もコストが小さな経路を自動探索する。
【０００３】
ところで、経路探索に使用する地図データは、道路網の情報量の差異に基づいて複数のレベルに階層化された構造をしている。例えば、３つのレベルに階層化された地図データには、細街路から高速道路まで全ての道路を格納したレベル０といわれる道路メッシュ、主に市道以上の道路を格納しているレベル１といわれる道路メッシュ、高速道路や有料道路といった道路を格納しているレベル２といわれる道路メッシュがそれぞれ区別されて格納されている。この場合、レベルが上がるにつれて、道路網の情報量が少なく粗い地図データとなっている。
【０００４】
経路探索を実施するにあたっては、経路の探索に係る演算量を抑えるために、現在地と目的地付近の地域では、下位レベル（レベル０）の地図データを使用して詳細に計算し、経路の中間地域では、上位レベル（レベル１以上）の地図データを使用して概略的に計算し、両方の結果を統合して誘導経路として出力する方法が一般的に採用されている。このような方法による経路探索処理について、図９を用いて詳しく説明する。
【０００５】
図９は、図９（ａ）の現在地１０から、図９（ｅ）の目的地２０までの誘導経路を探索する様子を示している。まず、図９（ａ）に示すように、現在地１０の周辺では、全ての道路を含むレベル０の道路メッシュ３０を使用して誘導経路の探索を行う。そして、レベル１の道路メッシュ４０へのアップリンク５０（レベル０の道路メッシュ３０からレベル１の道路メッシュ４０への接続点）に探索枝が到達すると、図９（ｂ）に示すように、アップリンク５０に対応するリンクを含むレベル１の道路メッシュ４０に切り替えて経路探索を行う。同様に、レベル１での経路探索によりレベル２へのアップリンク６０（レベル１の道路メッシュ４０からレベル２の道路メッシュ７０への接続点）に探索枝が到達すると、図９（ｃ）に示すレベル２の道路メッシュ７０に切り替えて経路探索を行う。
【０００６】
一方、図９（ｅ）に示すように、目的地２０の周辺では、全ての道路を含むレベル０の道路メッシュ８０を使用して経路探索を行う。そして、目的地２０から逆に辿っていってレベル１の道路メッシュ９０へのアップリンク１００に探索枝が到達すると、図９（ｄ）に示すように、アップリンク１００に対応するリンクを含むレベル１の道路メッシュ９０に切り替えて経路探索を行う。同様に、レベル１での経路探索によりレベル２へのアップリンク１１０（レベル１の道路メッシュ９０からレベル２の道路メッシュ７０への接続点）に探索枝が到達すると、図９（ｃ）に示すレベル２の道路メッシュ７０に切り替えて経路探索を行う。
【０００７】
最後に、図９（ｃ）に示すように、現在地１０から経路探索により求めたレベル２の道路メッシュ７０上のアップリンク６０と目的地２０から経路探索により求めたレベル２の道路メッシュ７０上のアップリンク１１０とをつなぐ経路を、レベル２の道路メッシュ７０を用いた経路探索を行うことにより求める。これにより、現在地１０から目的地２０に至る経路が全て決定されて、誘導経路の探索処理は終了する。
【０００８】
以上説明したような経路探索を行うことによって、現在地から目的地までの経路を求めるために、細街路から高速道路まで全ての道路が格納されたレベル０の道路メッシュを全区間にわたって使用する必要がなくなる。そのため、経路探索の時間を短縮することができる。この反面、現在地と目的地との間の中間領域の探索にはレベル０の道路メッシュが使用されない。そのため、中間領域では詳細道路が経路探索の対象外とされてしまうことにより、実際には遠回りしない経路があっても探索することができないという問題があった。
【０００９】
上記問題に対するものとしては、現在地と目的地との間の直線距離に対して経路探索により算出された誘導経路の距離が妥当か否かを評価し、妥当でない（遠回りである）と評価した場合には下位レベルの地図データを使用して再探索を行う技術が開示されている（例えば、特許文献１を参照）。具体的には、特許文献１に記載の技術では、経路探索により算出された誘導経路の距離と、現在地と目的地との間の直線距離との比率（誘導経路の距離／直線距離）が大きい場合に、下位レベルの地図データを使用して再探索を行うようにしている。
【００１０】
また、上記問題に対するものではないが、誘導経路上の進行方向と道路種別とが変わる進路変更場所を特定し、その特定した進行変更場所近辺において下位階層の地図データを用いた探索を行うことによって、誘導経路だけではなく、進路変更場所における迂回経路もユーザに提供できるようにした技術が開示されている（例えば、特許文献２を参照）。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開平１０−１５３４７７号公報
【特許文献２】特開２００２−２４３７６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上記特許文献１に記載された技術では、誘導経路の距離と直線距離との比率がしきい値より大きい場合（すなわち、大きく遠回りしている経路が探索された場合）に限り、下位レベルの地図データを使用して再探索が行われる。そのため、図１０（ａ）のように部分的に遠回りしている部分経路１２０、１３０を含む経路が探索されたときのように、誘導経路の距離と直線距離との比率があまり大きくなくてしきい値を超えない場合には、下位レベルの地図データを使用した再探索が行われないこととなる。それ故に、部分的に遠回りする経路が探索された場合にも再探索が行われるようにするためには、再探索が行うか否かの基準となるしきい値を小さくする必要がある。
【００１３】
しかし、そうした場合、誘導経路の距離が直線距離にかなり近い場合を除いて、誘導経路の全体について下位レベルの地図データを使用した再探索が行われることとなる。例えば、図１０（ｂ）のように、さらに再探索を行ってもこれ以上の近道がないような誘導経路が探索された場合であっても、その誘導経路の全体について再探索が行われる。そのため、しきい値を小さくすれば遠回りの経路が探索されるのを確実に防止することができる反面、常に再探索処理に時間がかかってしまい、ひいては最終的な誘導経路を設定するまでに長い時間を要してしまうという問題があった。
【００１４】
なお、上記特許文献２に記載された技術では、上位階層の地図データを用いて探索した誘導経路のうち、進行変更場所近辺では下位階層の地図データを用いた再探索が行われるが、それ以外の場所では再探索が行われない。そのため、誘導経路上の進行変更場所近辺以外のところに遠回りの経路が含まれないという保証はない。すなわち、上記特許文献２に記載された技術はそもそも、遠回りしない経路を探索することを目的とするものではない。
【００１５】
本発明は、このような問題を解決するために成されたものであり、遠回りの経路が探索されるのを防止し、かつ、最終的な誘導経路を設定するまでの時間を短縮できるようにすることを目的とする。
【課題を解決するための手段】
【００１６】
上記した課題を解決するために、本発明では、道路網の情報量に基づいて複数のレベルに階層化された地図データに基づいて探索した出発地から目的地までの第１の誘導経路の中から、両端のノード間において直線距離と第１の誘導経路に沿った距離との差分が所定値より大きい部分経路を抽出し、抽出した部分経路の両端のノード間の経路探索を、最下位レベルを含む地図データに基づいて行うことによって第２の部分経路を得る。そして、第１の誘導経路に含まれる部分経路を、探索した第２の部分経路で置き換えた第２の誘導経路を最終的な誘導経路として設定するようにしている。
【発明の効果】
【００１７】
上記のように構成した本発明によれば、最初に探索された誘導経路の中で部分的に遠回りしている部分が絞り込まれ、その絞り込まれた部分について最下位レベルを含む地図データに基づいた再探索が行われるため、遠回りの経路が誘導経路として設定されにくくなるようにすることができる。さらに、最初に探索された誘導経路の全体ではなく、その一部のみが再探索されるため、最初に探索された誘導経路の全体について再探索する従来技術に比べて、再探索処理に必要な時間を短縮することができ、ひいては最終的な誘導経路を設定するまでの時間を短縮することができる。
【図面の簡単な説明】
【００１８】
【図１】第１の実施形態によるナビゲーション装置の構成例を示すブロック図である。
【図２】第１の実施形態によるナビゲーション装置の主要構成例を示すブロック図である。
【図３】第１の実施形態による誘導経路探索部の処理を説明する図である。
【図４】第１の実施形態によるナビゲーション装置の動作例を示すフローチャートである。
【図５】第１の実施形態による誘導経路探索部の処理を説明する図である。
【図６】第２の実施形態によるナビゲーション装置の主要構成例を示すブロック図である。
【図７】第２の実施形態によるナビゲーション装置の主要構成の変形例を示すブロック図である。
【図８】第３の実施形態によるナビゲーション装置の主要構成例を示すブロック図である。
【図９】従来のナビゲーション装置における誘導経路探索処理の例を示す図である。
【図１０】従来のナビゲーション装置により探索された誘導経路の例を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態を図面に基づいて説明する。図１は、第１の実施形態によるナビゲーション装置２００の構成例を示すブロック図である。図１において、２１０はＤＶＤ−ＲＯＭ等の記録媒体であり、地図表示や経路探索等に必要な各種の地図データを記憶している。
【００２０】
ＤＶＤ−ＲＯＭ２１０に記録された地図データは、道路網の情報量の差異に基づいて３つのレベルに階層化された構造をしている。３つのレベルに階層化された地図データには、細街路から高速道路まで全ての道路を格納したレベル０といわれる道路メッシュ、主に市道以上の道路を格納しているレベル１といわれる道路メッシュ、高速道路や有料道路といった道路を格納しているレベル２といわれる道路メッシュがそれぞれ区別されて格納されている。この場合、レベルが上がるにつれて、道路網の情報量が少なく粗い地図データとなっている。各レベルの地図データには、地図表示に必要な描画ユニットのデータの他に、マップマッチングや経路探索等の各種の処理に必要な道路ユニットのデータが含まれている。
【００２１】
道路ユニットは、道路を細かく分割して複数のベクトルのつながりで表したときの個々のベクトルに相当する道路リンクに関するリンク情報と、個々の道路リンクの両端点に相当するノードに関するノード情報とを含んでいる。ノード情報には、ノードを一意に特定するノードＩＤ、ノードの位置(経緯度)、ノードに接続される道路リンク（リンクＩＤ）および、複数の道路リンクの端点に相当するノード（分岐点）であるか否かを示すフラグなどが含まれる。リンク情報には、道路リンクを一意に特定するリンクＩＤ、道路リンクの両端に接続されるノード（ノードＩＤ）、リンクコスト、道路種別（一般道路または高速道路）および道路属性などが含まれる。なお、ここでは地図データを記憶する記録媒体としてＤＶＤ−ＲＯＭ２１０を用いているが、ＣＤ−ＲＯＭ、ハードディスク、半導体メモリ等の他の記録媒体を用いても良い。
【００２２】
２２０は車両の現在位置を所定間隔毎に検出する車両位置検出部であり、自立航法センサ、ＧＰＳ受信機、位置計算用ＣＰＵ等で構成されている。自立航法センサは、所定走行距離毎に１個のパルスを出力して車両の移動距離を検出する車速センサ（距離センサ）と、車両の回転角度（移動方位）を検出する振動ジャイロ等の角速度センサ（相対方位センサ）とを含む。自立航法センサは、これらの車速センサおよび角速度センサによって車両の相対位置および方位を検出する。
【００２３】
位置計算用ＣＰＵは、自立航法センサから出力される自車両の相対的な位置および方位のデータに基づいて、絶対的な自車装置（推定車両位置）および車両方位を計算する。また、ＧＰＳ受信機は、複数のＧＰＳ衛星から送られてくる電波をＧＰＳアンテナで受信して、３次元測位処理あるいは２次元測位処理を行って車両の絶対位置および方位を計算する（車両方位は、現時点における自車位置と１サンプリング時間ΔＴ前の自車位置とに基づいて計算する）。
【００２４】
２３０はＤＶＤ−ＲＯＭ制御部であり、ＤＶＤ−ＲＯＭ２１０からの地図データの読み出しを制御する。２４０は地図データ記憶部であり、ＤＶＤ−ＲＯＭ制御部２３０の制御によってＤＶＤ−ＲＯＭ２１０から読み出された地図データを一時的に格納する。すなわち、ＤＶＤ−ＲＯＭ制御部２３０は、車両位置検出部２２０から車両現在位置の情報を入力し、その車両現在位置を含む所定範囲の地図データの読み出し指示を出力することにより、地図表示や誘導経路の探索に必要な地図データをＤＶＤ−ＲＯＭ２１０から読み出して地図データ記憶部２４０に格納する。
【００２５】
２５０はリモコン、タッチパネルまたは操作スイッチ等の操作部であり、ユーザがナビゲーション装置２００に対して各種の情報（例えば、経路誘導の目的地や経由地）を設定したり、各種の操作（例えば、メニュー選択操作、地図の拡大／縮小操作、手動地図スクロール、数値入力など）を行ったりするためのものである。
【００２６】
２６０は目的地設定部であり、ディスプレイ２７０に表示されている目的地設定用の操作画面において、ユーザによる操作部２５０の操作を介して指定された地点を目的地として設定する。そして、目的地設定部２６０は、設定した目的地を示す目的地情報を誘導経路探索部２８０に出力する。
【００２７】
誘導経路探索部２８０は、地図データ記憶部２４０に記憶されている地図データに基づいて、車両位置検出部２２０により検出された自車位置（出発地）から、目的地設定部２６０により設定された目的地に至る様々な経路上のリンクコストを順次加算し、リンクコストの合計が最も小さい経路を誘導経路として探索する。
【００２８】
２９０は誘導経路メモリであり、誘導経路探索部２８０により誘導経路が探索された場合、その探索された誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を誘導経路情報として一時的に格納する。
【００２９】
３００は地図表示制御部であり、車両位置検出部２２０により検出された自車位置情報と、地図データ記憶部２４０に記憶されている地図データとに基づいて、自車位置周辺の地図画像データを生成する。そして、地図表示制御部３００は、生成した地図画像データをディスプレイ２７０に出力することにより、自車位置周辺の地図画像をディスプレイ２７０に表示させる。
【００３０】
３１０は誘導経路案内部であり、誘導経路探索部２８０により誘導経路が探索された場合、車両位置検出部２２０により検出された自車位置情報と、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された誘導経路情報とに基づいて誘導経路案内を行う。具体的には、誘導経路案内部３１０は、ディスプレイ２７０に対して、地図表示制御部３００により生成された地図画像に重ねて誘導経路を他の道路とは異なる色で太く表示することにより、誘導経路の目的地までの走行案内を行う。また、誘導経路案内部３１０は、誘導経路上に存在する経路案内すべき分岐点（以下、案内分岐点という）に自車両が近づくたびに、当該案内分岐点に関する経路案内を行う。
【００３１】
次に、第１の実施形態によるナビゲーション装置２００の主要な機能構成について説明する。図２は、第１の実施形態によるナビゲーション装置２００の主要構成例を示すブロック図である。図２に示すように、誘導経路探索部２８０は、第１の誘導経路探索部４００、部分経路抽出部４２０、部分経路メモリ４４０、第２の誘導経路探索部４６０および誘導経路設定部４８０を備えて構成されている。
【００３２】
第１の誘導経路探索部４００は、車両位置検出部２２０により検出された自車位置情報と地図データ記憶部２４０に記憶されている地図データとに基づいて、現在位置（本発明の出発地に対応）から、目的地設定部２６０から出力された目的地情報により示される目的地までの第１の誘導経路を探索する。具体的には、第１の誘導経路探索部４００は、図９で説明した従来のやり方と同様に、現在位置および目的地の付近では最下位レベル（レベル０）の地図データを用いるとともに、出発地および目的地の付近以外の中間領域では最下位レベル以外の上位レベル（レベル１、２）の地図データを用いることによって、現在位置から目的地までの第１の誘導経路を探索する。そして、第１の誘導経路探索部４００は、探索した第１の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第１の誘導経路情報として誘導経路メモリ２９０に格納する。
【００３３】
なお、レベル０からレベル１、レベル１からレベル２への地図データの切り替えのことを以下では「クライミング」という。また、クライミングが実際に行われたノードのことを「クライミングノード」という。第１の誘導経路探索部４００は、第１の誘導経路を探索する際に、クライミングノードを特定するクライミングノード特定情報を誘導経路メモリ２９０に格納する。
【００３４】
部分経路抽出部４２０は、第１の誘導経路探索部４００により探索された第１の誘導経路のうち上位レベル（レベル１、２）の地図データに基づいて探索された誘導経路（以下、「上位探索経路」という）の中から、両端のノード間において直線距離に対する第１の誘導経路に沿った距離の比率が所定値（例えば、１．３）以上である部分経路を抽出する。この部分経路の抽出を行うために、部分経路抽出部４２０は、第１ノード特定部５００、第２ノード特定部５２０、第３ノード特定部５４０および第４ノード特定部５６０を備えて構成されている。
【００３５】
第１ノード特定部５００は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第１の誘導経路を構成するノードのうち、現在位置から最も近いクライミングノードを第１ノードとして特定する。そして、第１ノード特定部５００は、特定した第１ノードを示す第１ノード特定情報を第３ノード特定部５４０および第４ノード特定部５６０に出力する。
【００３６】
なお、最下位レベル（レベル０）の地図データおよび上位レベル（レベル１）の地図データに共通して存在するノードで必ずクライミングが行われるのであれば、当該共通して存在するノードであり、かつ、現在位置から最も近いノードを第１ノードとして特定するようにしても良い。この場合は、クライミングノード特定情報を参照する必要はない。
【００３７】
第２ノード特定部５２０は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第１の誘導経路を構成するノードのうち、目的地から最も近いクライミングノードを第２ノードとして特定する。そして、第２ノード特定部５２０は、特定した第２ノードを示す第２ノード特定情報を第３ノード特定部５４０に出力する。
【００３８】
なお、最下位レベル（レベル０）の地図データおよび上位レベル（レベル１）の地図データに共通して存在するノードで必ずクライミングが行われるのであれば、当該共通して存在するノードであり、かつ、目的地から最も近いノードを第２ノードとして特定するようにしても良い。この場合は、クライミングノード特定情報を参照する必要はない。
【００３９】
本実施形態では、第１ノードから第２ノードの間にある各ノードを第１の判定対象ノードとする。第１の誘導経路に含まれる全ノードを第１の判定対象ノードとしても良いが、第１ノードから第２ノードまでの上位探索経路に範囲を絞ることにより、第３ノード特定部５４０および第４ノード特定部５６０の判定処理の負荷を減らすことができる。
【００４０】
第３ノード特定部５４０は、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された第１の誘導経路情報とに基づいて、第１の誘導経路を構成するノードのうち、第１ノードから第２ノードまでに存在する第１の判定対象ノードの各々について、第１ノードから遠い順に、第１ノードと当該第１の判定対象ノードとの間の直線距離に対する、第１ノードと当該第１の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値より小さい第２の所定値（例えば、１．２）より大きいか否かについて判定を行う。そして、第３ノード特定部５４０は、第２の所定値より大きいと最初に判定した第１の判定対象ノードを第３ノードとして特定し、特定した第３ノードを示す第３ノード特定情報を第４ノード特定部５６０に出力する。第１ノードから第３ノードの間にある各ノードを第２の判定対象ノードとする。第２の判定対象ノードは、第１の判定対象ノードの一部であり、更に範囲が絞り込まれている。
【００４１】
第４ノード特定部５６０は、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された第１の誘導経路情報とに基づいて、第１の誘導経路を構成するノードのうち、第１ノードから第３ノードまでに存在するノードである第２の判定対象ノードの各々について、第３ノードから遠い順に、第３ノードと当該第２の判定対象ノードとの間の直線距離に対する、第３ノードと当該第２の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値（例えば、１．３）より大きいか否かについて判定を行う。そして、第４ノード特定部５６０は、所定値より大きいと最初に判定した第２の判定対象ノードを第４ノードとして特定する。
【００４２】
なお、第３ノード特定部５４０の判定処理で用いる第２の所定値と第４ノード特定部５６０の判定処理で用いる所定値との間で数値を変えているのは、所定値と第２の所定値との間で数値を同じにすると、第１ノードおよび第２ノードの片側からしか絞り込むことができず、第１の誘導経路の中で部分的に遠回りしている部分が第１ノードおよび第２ノードの何れか付近に存在しない限り、精度良く絞り込むことができないからである。
【００４３】
部分経路抽出部４２０は、誘導経路メモリ２９０に格納された第１の誘導経路情報に基づいて、第１の誘導経路のうち、第３ノードから第４ノードまでの経路を部分経路として抽出する。この抽出した部分経路は、範囲が絞り込まれたものになっている。そして、部分経路抽出部４２０は、抽出した部分経路のデータ（第３ノードから第４ノードに至るまでのノードの集合）を部分経路情報として部分経路メモリ４４０に格納する。
【００４４】
第２の誘導経路探索部４６０は、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と、部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。すなわち、部分経路のみを対象として、図９と同様の処理を行う。そして、第２の誘導経路探索部４６０は、生成した第２の部分経路のデータ（第３ノードから第４ノードに至るまでのノードの集合）を第２の部分経路情報として部分経路メモリ４４０に格納する。
【００４５】
誘導経路設定部４８０は、誘導経路メモリ２９０に格納された第１の誘導経路情報と、部分経路メモリ４４０に格納された部分経路情報および第２の部分経路情報とに基づいて、第１の誘導経路に含まれる部分経路を第２の部分経路で置き換えた第２の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第２の誘導経路情報として誘導経路メモリ２９０に格納する。
【００４６】
次に、第１の実施形態による誘導経路探索部２８０の処理について、図３を参照しながら具体例に沿って説明する。図３は、第１の実施形態による誘導経路探索部２８０の処理を説明する図である。図３（ａ）において、ａ１〜ａ３０は、第１の誘導経路探索部４００により探索された第１の誘導経路を構成する全ノードである。この中には、レベル０の地図データで探索されたもの、レベル１の地図データで探索されたもの、レベル２の地図データで探索されたものが混在している。第１の誘導経路において、ノードａ１は現在位置を示すノードであり、ノードａ３０は目的地を示すノードである。
【００４７】
第１ノード特定部５００は、第１の誘導経路を構成するノードａ１〜ａ３０のうち、現在位置から最も近いクライミングノード（レベル０からレベル１に地図データが切り替わったポイント）を第１ノードとして特定する。例えば、これがノードａ５であったとする。また、第２ノード特定部５２０は、第１の誘導経路を構成するノードａ１〜ａ３０のうち、目的地から最も近いクライミングノード（レベル０からレベル１に地図データが切り替わったポイント）を第２ノードとして特定する。例えば、これがノードａ２５であったとする。本実施形態では、図３（ｂ）のように、ノードａ５〜ａ２５を第１の判定対象ノードとする。
【００４８】
次に、第３ノード特定部５４０は、第１の誘導経路を構成するノードのうち、第１ノードから第２ノードまでに存在する第１の判定対象ノード（ノードａ１〜ノードａ２５）の各々について、第１ノードから遠い順に、第１ノードと当該第１の判定対象ノードとの間の直線距離に対する、第１ノードと当該第１の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が第２の所定値（１．２）より大きいか否かについて判定を行う。そして、第３ノード特定部５４０は、第２の所定値より大きいと最初に判定した第１の判定対象ノードを第３ノードとして特定する。例えば、これがノードａ１５であったとする。本実施形態では、図３（ｃ）のように、ノードａ５〜ａ１５を第２の判定対象ノードとする。
【００４９】
第４ノード特定部５６０は、第１の誘導経路を構成するノードのうち、第１ノードから第３ノードまでに存在する第２の判定対象ノード（ノードａ５〜ノードａ１５）の各々について、第３ノードから遠い順に、第３ノードと当該第２の判定対象ノードとの間の直線距離に対する、第３ノードと当該第２の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値（１．３）より大きいか否かについて判定を行う。そして、第４ノード特定部５６０は、所定値より大きいと最初に判定した第２の判定対象ノードを第４ノードとして特定する。例えば、これがノードａ７であったとする。
【００５０】
部分経路抽出部４２０は、図３（ｄ）に示すように、第１の誘導経路のうち、第３ノード（ノードａ１５）から第４ノード（ノードａ７）までの経路を部分経路として抽出する。第２の誘導経路探索部４６０は、最下位レベル（レベル０）を含む地図データを用い、部分経路抽出部４２０により抽出された部分経路の両端のノード（ノードａ７およびノードａ１５）をそれぞれ出発地および目的地として、部分経路間の経路探索を行う。これにより、第２の部分経路１５０を生成する。ここで、第２の部分経路１５０が探索されたのは、部分経路の両端のノードの付近では最下位レベル（レベル０）の地図データを用いて探索が行われ、上位レベル（レベル１、２）の地図データには存在しない経路を探索できたためである。誘導経路設定部４８０は、第１の誘導経路に含まれる部分経路を第２の部分経路１５０で置き換えた第２の誘導経路のデータを第２の誘導経路情報として誘導経路メモリ２９０に格納する。
【００５１】
次に、本実施形態における誘導経路探索部２８０の動作について説明する。図４は、本実施形態における誘導経路探索部２８０の動作例を示すフローチャートである。図４におけるステップＳ１００の処理は、誘導経路探索部２８０が、操作部２５０に対するユーザ操作を介して誘導経路を探索する要求を受け付けることにより開始する。
【００５２】
まず、第１の誘導経路探索部４００は、車両位置検出部２２０により検出された自車位置情報と地図データ記憶部２４０に記憶されている地図データとに基づいて、現在位置から目的地までの第１の誘導経路を探索する（ステップＳ１００）。次に、第１ノード特定部５００は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第１の誘導経路を構成するノードのうち、現在位置から最も近いクライミングノードを第１ノードとして特定する（ステップＳ１２０）。
【００５３】
次に、第２ノード特定部５２０は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第１の誘導経路を構成するノードのうち、目的地から最も近いクライミングノードを第２ノードとして特定する（ステップＳ１４０）。
【００５４】
次に、第３ノード特定部５４０は、第２ノード特定部５２０により特定された第２ノードを第１の判定対象ノードとして設定する（ステップＳ１６０）。次に、第３ノード特定部５４０は、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された第１の誘導経路情報とに基づいて、第１ノードと第１の判定対象ノードとの間の直線距離に対する、第１ノードと当該第１の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が第２の所定値（１．２）より大きいか否かについて判定を行う（ステップＳ１８０）。
【００５５】
もし、第２の所定値より大きくないと第３ノード特定部５４０にて判定した場合（ステップＳ１８０にてＮＯ）、第３ノード特定部５４０は、第１の誘導経路に沿って、第１の判定対象ノードから１つ第１ノード側に移動したノードを新たな第１の判定対象ノードとして設定する（ステップＳ２００）。その後、処理はステップＳ１８０に遷移する。一方、第２の所定値より大きいと第３ノード特定部５４０にて判定した場合（ステップＳ１８０にてＹＥＳ）、第３ノード特定部５４０は、そのときに第１の判定対象ノードとして設定しているノードを第３ノードとして特定する（ステップＳ２２０）。
【００５６】
次に、第４ノード特定部５６０は、第１ノード特定部５００により特定された第１ノードを第２の判定対象ノードとして設定する（ステップＳ２４０）。次に、第４ノード特定部５６０は、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された第１の誘導経路情報とに基づいて、第３ノードと第２の判定対象ノードとの間の直線距離に対する、第３ノードと当該第２の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値（例えば、１．３）より大きいか否かについて判定を行う（ステップＳ２６０）。
【００５７】
もし、所定値より大きくないと第４ノード特定部５６０にて判定した場合（ステップＳ２６０にてＮＯ）、第４ノード特定部５６０は、第１の誘導経路に沿って、第２の判定対象ノードから１つ第３ノード側に移動したノードを新たな第２の判定対象ノードとして設定する（ステップＳ２８０）。その後、処理はステップＳ２６０に遷移する。一方、所定値より大きいと第４ノード特定部５６０にて判定した場合（ステップＳ２６０にてＹＥＳ）、第４ノード特定部５６０は、そのときに第２の判定対象ノードとして設定しているノードを第４ノードとして特定する（ステップＳ３００）。
【００５８】
次に、部分経路抽出部４２０は、誘導経路メモリ２９０に格納された第１の誘導経路情報に基づいて、第１の誘導経路のうち、第３ノード特定部５４０により特定された第３ノードから第４ノード特定部５６０により特定された第４ノードまでの経路を部分経路として抽出する（ステップＳ３２０）。次に、第２の誘導経路探索部４６０は、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）に基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する（ステップＳ３４０）。
【００５９】
最後に、誘導経路設定部４８０は、誘導経路メモリ２９０に格納された第１の誘導経路情報に基づいて、第１の誘導経路に含まれる部分経路を第２の誘導経路探索部４６０によって探索された第２の部分経路で置き換えた第２の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第２の誘導経路情報として誘導経路メモリ２９０に格納する（ステップＳ３６０）。ステップＳ３６０の処理が完了することによって、誘導経路探索部２８０は図４における処理を終了する。
【００６０】
以上詳しく説明したように、第１の実施形態では、レベル０〜２の地図データに基づいて適宜クライミングしながら探索した現在位置（出発地）から目的地までの第１の誘導経路の中から、両端のノード間において直線距離に対する第１の誘導経路に沿った距離の比率が所定値より大きい部分経路を抽出し、抽出した部分経路についてレベル０〜２の地図データに基づいて再探索を行うことによって第２の部分経路を得る。そして、第１の誘導経路に含まれる部分経路を、探索した第２の部分経路で置き換えた第２の誘導経路を最終的な誘導経路として設定するようにしている。
【００６１】
このように構成した第１の実施形態によれば、最初に探索された誘導経路の中で部分的に遠回りしている部分が絞り込まれ、その絞り込まれた部分について最下位レベルを含む地図データに基づいた再探索が行われるため、遠回りの経路が誘導経路として設定されにくくなるようにすることができる。さらに、最初に探索された誘導経路の全体ではなく、その一部のみが再探索されるため、最初に探索された誘導経路の全体について再探索する従来技術に比べて、再探索処理に必要な時間を短縮することができ、ひいては最終的な誘導経路を設定するまでの時間を短縮することができる。
【００６２】
また、第１の実施形態では、第１の誘導経路のうち、上位レベルの地図データに基づいて探索された上位探索経路に範囲を絞り、その中から部分経路を抽出するようにしている。このように構成した第１の実施形態によれば、最下位レベルの地図データに基づいて探索された経路は、部分経路の抽出処理を行う対象から除かれる。この除かれた経路は、再探索を行ってもこれ以上の近道がないので、部分経路の抽出対象から除くことに問題は生じない。以上より、第１の誘導経路の全体を対象として部分経路の抽出処理を行わない分、その抽出処理にかかる時間を短くすることができる。
【００６３】
なお、上記第１の実施形態では、部分経路抽出部４２０にて部分経路を抽出する際、第２ノードを特定した後に第１ノードを特定する例について説明したが、第１ノードを特定した後に第２ノードを特定するようにしても良い。また、上記第１の実施形態では、部分経路抽出部４２０にて部分経路を抽出する際、第３ノードを特定した後に第４ノードを特定する例について説明したが、第４ノードを特定した後に第３ノードを特定するようにしても良い。
【００６４】
また、上記第１の実施形態では、部分経路抽出部４２０が、第１の誘導経路のうち、第３ノードから第４ノードまでの経路を部分経路として抽出する例について説明したが、本発明はこれに限定されない。例えば、部分経路抽出部４２０は、第１の誘導経路のうち、第１ノードから第３ノードからまでの経路を部分経路として抽出するようにしても良い。
【００６５】
上記第１の実施形態では、部分経路について再探索を行うときも、クライミングをしながら経路探索を行っている。そのため、図３（ｄ）のように探索された第２の部分経路１５０の中にも遠回りの経路が含まれている可能性がある。そこで、第２の部分経路１５０を探索するときにクライミングを行った場合には、第２の部分経路１５０を対象として同様の処理を再度行うようにしても良い。
【００６６】
具体的には、第２の誘導経路探索部４６０は、第２の部分経路を探索する際に、クライミングノードを特定するクライミングノード特定情報を誘導経路メモリ２９０に格納する。そして、第２の誘導経路探索部４６０は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第２の部分経路１５０を探索するときにクライミングを行ったか（すなわち、第２の部分経路の中に、部分的に遠回りとなっているところが存在する可能性があるか）否かについて判定する。第２の誘導経路探索部４６０は、第２の部分経路１５０を探索するときにクライミングを行ったと判定した場合、その旨を部分経路抽出部４２０に通知する。
【００６７】
部分経路抽出部４２０は、第２の部分経路１５０を探索するときにクライミングを行った旨の通知を第２の誘導経路探索部４６０から受けた場合、第２の部分経路の中から、両端のノード間において直線距離に対する第２の部分経路に沿った距離の比率が所定値より大きい第３の部分経路を抽出する。その抽出処理の内容は、図３を用いて説明したのと同様である。
【００６８】
第２の誘導経路探索部４６０は、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と、部分経路メモリ４４０に格納された第３の部分経路情報とに基づいて、第３の部分経路の両端のノード間の経路探索を行うことによって第４の部分経路を生成する。そして、第２の誘導経路探索部４６０は、生成した第４の部分経路のデータを第４の部分経路情報として部分経路メモリ４４０に格納する。
【００６９】
誘導経路設定部４８０は、誘導経路メモリ２９０に格納された第２の誘導経路情報と、部分経路メモリ４４０に格納された第３の部分経路情報および第４の部分経路情報とに基づいて、第２の誘導経路に含まれる第３の部分経路を第４の部分経路で置き換えた第３の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第３の誘導経路情報として誘導経路メモリ２９０に格納する。
【００７０】
このように構成した場合、再探索して求めた第２の部分経路１５０が部分的に遠回りする経路を含んでいても、その部分的に遠回りする経路を確実に解消し、より最短の誘導経路を求めることができる。なお、このようにして２回目の再探索によって第４の部分経路を求めるときにもクライミングが発生した場合には、同様の手順で３回目の再探索を行うようにしても良い。
【００７１】
また、上記実施形態では、現在位置から目的地までの第１の誘導経路の中から１ヵ所だけ部分経路を抽出して再探索を行っているが、それ以外の場所にも遠回りの経路が含まれている可能性がある。そこで、１ヶ所の部分経路について再探索が終わった後は、別の場所において部分経路を抽出して再探索するようにしても良い。
【００７２】
具体的には、部分経路抽出部４２０は、第２の誘導経路（更に再探索された場合は第３の誘導経路。以下、同様）から第２の部分経路（図３（ｄ）のノードａ９〜ａ１４の部分）を除いた残りの経路（以下、「残り経路」という）の中から、両端のノード間において直線距離に対する第２の誘導経路に沿った距離の比率が所定値（例えば、１．３）より大きい第５の部分経路を抽出する。そして、部分経路抽出部４２０は、抽出した第５の部分経路のデータを第５の部分経路情報として部分経路メモリ４４０に格納する。なお、残り経路は、第２の誘導経路から第２の部分経路を除いた部分ではなく、第２の誘導経路から部分経路（図３（ｄ）のノードａ７〜ａ１５の部分）を除いたものとしても良い。
【００７３】
第２の誘導経路探索部４６０は、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と、部分経路メモリ４４０に格納された第５の部分経路情報とに基づいて、第５の部分経路の両端のノード間の経路探索を行うことによって第６の部分経路を生成する。そして、第２の誘導経路探索部４６０は、生成した第６の部分経路のデータを第６の部分経路情報として部分経路メモリ４４０に格納する。
【００７４】
誘導経路設定部４８０は、誘導経路メモリ２９０に格納された第２の誘導経路情報と、部分経路メモリ４４０に格納された第５の部分経路情報および第６の部分経路情報とに基づいて、第２の誘導経路に含まれる第５の部分経路を第６の部分経路で置き換えた第４の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第４の誘導経路情報として誘導経路メモリ２９０に格納する。
【００７５】
次に、誘導経路探索部２８０の処理について、図５を参照しながら具体例に沿って説明する。図５は、誘導経路探索部２８０が図３のように第２の部分経路１５０を探索して誘導経路メモリ２９０に格納した後の処理を説明する図である。図５において、ａ１５〜ａ３０は、第２の誘導経路から部分経路１５０を除いた経路のうち、ノードａ１５よりも目的地（ノードａ３０）側の残り経路上に位置するノードである。
【００７６】
第１ノード特定部５００は、残り経路を構成するノードａ１５〜ａ３０のうち、ノードａ１５から最も近いクライミングノードを第１ノードとして特定する。例えば、これがノードａ１５であったとする。なお、第１の誘導経路を探索するときに、ノードａ１５よりも現在位置側で最上位レベル（レベル２）までクライミングしている場合がある。その場合、ノードａ１５〜ａ３０のうち、ノードａ１５から最も近いクライミングノードは存在しない。この場合、ノードａ１５を第１ノードとする。
【００７７】
また、第２ノード特定部５２０は、残り経路を構成するノードａ１５〜ａ３０のうち、目的地から最も近いクライミングノード（レベル０からレベル１に地図データが切り替わったポイント）を第２ノードとして特定する。例えば、これがノードａ２５であったとする。本実施形態では、図５（ｂ）のように、ノードａ１５〜ａ２５を第１の判定対象ノードとする。
【００７８】
次に、第３ノード特定部５４０は、残り経路を構成するノードのうち、第１ノードから第２ノードまでに存在する第１の判定対象ノード（ノードａ１５〜ノードａ２５）の各々について、第１ノードから遠い順に、第１ノードと当該第１の判定対象ノードとの間の直線距離に対する、第１ノードと当該第１の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が第２の所定値（１．２）より大きいか否かについて判定を行う。そして、第３ノード特定部５４０は、第２の所定値より大きいと最初に判定した第１の判定対象ノードを第３ノードとして特定する。例えば、これがノードａ１９であったとする。本実施形態では、図５（ｃ）のように、ノードａ１５〜ａ１９を第２の判定対象ノードとする。
【００７９】
第４ノード特定部５６０は、残り経路を構成するノードのうち、第１ノードから第３ノードまでに存在する第２の判定対象ノード（ノードａ１５〜ノードａ１９）の各々について、第３ノードから遠い順に、第３ノードと当該第２の判定対象ノードとの間の直線距離に対する、第３ノードと当該第２の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値（１．３）より大きいか否かについて判定を行う。そして、第４ノード特定部５６０は、所定値より大きいと最初に判定した第２の判定対象ノードを第４ノードとして特定する。例えば、これがノードａ１６であったとする。
【００８０】
部分経路抽出部４２０は、図５（ｄ）に示すように、残り経路のうち、第３ノード（ノードａ１９）から第４ノード（ノードａ１６）までの経路を第５の部分経路として抽出する。第２の誘導経路探索部４６０は、最下位レベル（レベル０）を含む地図データを用い、部分経路抽出部４２０により抽出された第５の部分経路の両端のノード（ノードａ１６およびノードａ１９）をそれぞれ出発地および目的地として、部分経路間の経路探索を行う。これにより、第６の部分経路１６０を生成する。
【００８１】
なお、残り経路から抽出した第５の部分経路の目的地側の端点である第３ノードが第２ノードの２つ以上手前であれば、同様の処理を繰り返すことにより残り経路の別の位置も再探索する。また、ノードａ７から現在位置側も同様にして行う。このように構成した場合、範囲を絞り込んで再探索した部分を除いた残り経路が部分的に遠回りする経路を含んでいても、その部分的に遠回りする経路を確実に解消し、より最短の誘導経路を求めることができる。
【００８２】
次に、本発明の第２の実施形態を図面に基づいて説明する。図６は、第２の実施形態によるナビゲーション装置２００の主要構成例を示すブロック図である。図６に示すように、誘導経路探索部２８０は、その機能構成として、直線距離判定部６００を更に備えている。また、誘導経路探索部２８０は、その機能構成として、図２の第２の誘導経路探索部４６０の代わりに、第２の誘導経路探索部４６０′を備えている。なお、この図６において、図２に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００８３】
直線距離判定部６００は、地図データ記憶部２４０に記憶されている地図データと、部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード間の直線距離が所定距離未満であるか否かについて判定し、その判定結果を第２の誘導経路探索部４６０′に通知する。
【００８４】
第２の誘導経路探索部４６０′は、部分経路の両端のノード間の直線距離が所定距離未満である旨の通知を直線距離判定部６００から受けた場合、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）のみ）と部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。
【００８５】
また、第２の誘導経路探索部４６０′は、部分経路の両端のノード間の直線距離が所定距離未満でない旨の通知を直線距離判定部６００から受けた場合、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。
【００８６】
部分経路の両端のノード間の直線距離が所定距離未満であれば、部分経路の距離は短いので、最下位レベルの詳細な地図データだけで経路探索を行っても、再探索処理に多くの時間がかかってしまう可能性は少ないと考えられる。そして、全ての道路を網羅した最下位レベルの地図データだけを用いてクライミングすることなく経路探索を行うので、最短の誘導経路が確実に探索される。よって、再探索処理時間を増やすことなく、部分経路について、遠回りのない最短の経路を探索することができる。
【００８７】
なお、部分経路の両端のノード間の直線距離の代わりに部分経路の両端のノード間のノード数で、最下位レベルの詳細な地図データだけで経路探索を行うか否かを判断しても良い。図７は、ノード数で判断する場合のナビゲーション装置２００の主要構成例を示すブロック図である。図７に示すように、誘導経路探索部２８０は、その機能構成として、ノード数判定部６２０を更に備えている。また、誘導経路探索部２８０は、その機能構成として、図２の第２の誘導経路探索部４６０の代わりに、第２の誘導経路探索部４６０′′を備えている。なお、この図７において、図２に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００８８】
ノード数判定部６２０は、部分経路メモリ４４０に格納された部分経路情報に基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード間に存在するノードの数が所定数未満であるか否かについて判定し、その判定結果を第２の誘導経路探索部４６０′′に通知する。
【００８９】
第２の誘導経路探索部４６０′′は、部分経路の両端のノード間に存在するノードの数が所定数未満である旨の通知をノード数判定部６２０から受けた場合、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）のみ）と部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。
【００９０】
また、第２の誘導経路探索部４６０′′は、部分経路の両端のノード間に存在するノードの数が所定数未満でない旨の通知をノード数判定部６２０から受けた場合、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。
【００９１】
このように構成した場合も、図６のように直線距離で判断する場合と同様の効果が得られる。すなわち、部分経路の両端のノード間のノード数が所定数未満であれば、部分経路の距離は短いので、最下位レベルの詳細な地図データだけで経路探索を行っても、再探索処理に多くの時間がかかってしまう可能性は少ないと考えられる。そして、全ての道路を網羅した最下位レベルの地図データだけを用いてクライミングすることなく経路探索を行うので、最短の誘導経路が確実に探索される。よって、再探索処理時間を増やすことなく、部分経路について、遠回りのない最短の経路を探索することができる。
【００９２】
次に、本発明の第３の実施形態を図面に基づいて説明する。図８は、第３の実施形態によるナビゲーション装置２００の主要構成例を示すブロック図である。図８に示すように、誘導経路探索部２８０は、その機能構成として、第１の所要時間算出部７００、第２の所要時間算出部７２０および時間判定部７４０を更に備えている。また、誘導経路探索部２８０は、その機能構成として、図２の第２の誘導経路探索部４６０の代わりに、第２の誘導経路探索部４６０′′′を備えている。なお、この図８において、図２に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００９３】
第１の所要時間算出部７００は、地図データ記憶部２４０に記憶されている地図データ（道路ユニットのリンク情報（リンクコスト））と、部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の所要走行時間を第１の所要時間として算出する。そして、第１の所要時間算出部７００は、算出した第１の所要時間を示す第１の所要時間情報を時間判定部７４０に出力する。
【００９４】
第２の所要時間算出部７２０は、地図データ記憶部２４０に記憶されている地図データ（道路ユニットのノード情報（経緯度））と、部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード間の直線距離を、当該部分経路の探索に使用された地図データの１つ下のレベルの地図データにのみ含まれる道路の道路種別に応じた予測走行速度で除算した時間を第２の所要時間として算出する。そして、第２の所要時間算出部７２０は、算出した第２の所要時間を示す第２の所要時間情報を時間判定部７４０に出力する。
【００９５】
時間判定部７４０は、第２の所要時間算出部７２０から出力された第２の所要時間情報により示される第２の所要時間が第１の所要時間算出部７００から出力された第１の所要時間情報により示される第１の所要時間より大きいか否かについて判定し、その判定結果を第２の誘導経路探索部４６０′′′に通知する。
【００９６】
次に具体例を１つ説明する。部分経路は高速道路であるとする。また、部分経路の探索に使用された地図データの１つ下のレベルの地図データにのみ含まれる道路の道路種別が一般道路であり、その道路種別に応じた予測走行速度が４０［ｋｍ／ｈ］であるとする。この場合、第２の所要時間より第１の所要時間より大きければ、部分経路がたとえ遠回りであったとしても、一般道路を通行するより速い。
【００９７】
第２の誘導経路探索部４６０′′′は、第２の所要時間が第１の所要時間より大きくない旨の通知を受けた場合、最下位レベル（レベル０）を含む地図データを用いることによって、部分経路の両端のノード間の経路探索を行う。また、第２の誘導経路探索部４６０′′′は、第２の所要時間が第１の所要時間より大きい旨の通知を受けた場合、部分経路の両端のノード間の経路探索を行わない。
【００９８】
このように構成した第３の実施形態によれば、部分経路について、最下位レベルの地図データを用いて探索される経路の方が、上位レベルの地図データを用いて既に探索された経路より却って時間がかかると考えられる場合、部分経路について無駄な再探索処理を行わないようにすることができる。
【００９９】
なお、上記第１〜第３の実施形態では、地図データが、道路網の情報量の差異に基づいて３つのレベルに階層化された構造をしている例について説明したが、本発明はこれに限定されない。例えば、地図データが、道路網の情報量の差異に基づいて２つ、または、４つ以上のレベルに階層化された構造をしていても良い。
【０１００】
また、上記第１〜第３の実施形態では、第１の誘導経路の中から、両端のノード間において直線距離に対する第１の誘導経路に沿った距離の比率が所定値以上である部分経路を抽出する例について説明したが、本発明はこれに限定されない。例えば、第１の誘導経路の中から、両端のノード間において第１の誘導経路に沿った距離から直線距離を減算した距離が所定値より大きい部分経路を抽出するようにしても良い。
【０１０１】
その他、上記第１〜第３の実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその精神、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【０１０２】
１５０ 第２の部分経路
１６０ 第６の部分経路
２００ ナビゲーション装置
２４０ 地図データ記憶部
２８０ 誘導経路探索部
４００ 第１の誘導経路探索部
４２０ 部分経路抽出部
４６０，４６０′，４６０′′，４６０′′′ 第２の誘導経路探索部
４８０ 誘導経路設定部
５００ 第１ノード特定部
５２０ 第２ノード特定部
５４０ 第３ノード特定部
５６０ 第４ノード特定部
６００ 直線距離判定部
６２０ ノード数判定部
７００ 第１の所要時間算出部
７２０ 第２の所要時間算出部
７４０ 時間判定部
【技術分野】
【０００１】
本発明は、ナビゲーション装置および誘導経路探索方法に関し、特に、地図データを用いて現在地から目的地までを結ぶ最もコストが小さな経路を自動探索する経路誘導機能を備えたナビゲーション装置に用いて好適なものである。
【背景技術】
【０００２】
一般に、ナビゲーション装置の殆どには、運転者が所望の目的地に向かって道路を間違うことなく容易に走行できるようにした経路誘導機能が搭載されている。この経路誘導機能では、地図データを用いて現在地から目的地までを結ぶ最もコストが小さな経路を自動探索する。
【０００３】
ところで、経路探索に使用する地図データは、道路網の情報量の差異に基づいて複数のレベルに階層化された構造をしている。例えば、３つのレベルに階層化された地図データには、細街路から高速道路まで全ての道路を格納したレベル０といわれる道路メッシュ、主に市道以上の道路を格納しているレベル１といわれる道路メッシュ、高速道路や有料道路といった道路を格納しているレベル２といわれる道路メッシュがそれぞれ区別されて格納されている。この場合、レベルが上がるにつれて、道路網の情報量が少なく粗い地図データとなっている。
【０００４】
経路探索を実施するにあたっては、経路の探索に係る演算量を抑えるために、現在地と目的地付近の地域では、下位レベル（レベル０）の地図データを使用して詳細に計算し、経路の中間地域では、上位レベル（レベル１以上）の地図データを使用して概略的に計算し、両方の結果を統合して誘導経路として出力する方法が一般的に採用されている。このような方法による経路探索処理について、図９を用いて詳しく説明する。
【０００５】
図９は、図９（ａ）の現在地１０から、図９（ｅ）の目的地２０までの誘導経路を探索する様子を示している。まず、図９（ａ）に示すように、現在地１０の周辺では、全ての道路を含むレベル０の道路メッシュ３０を使用して誘導経路の探索を行う。そして、レベル１の道路メッシュ４０へのアップリンク５０（レベル０の道路メッシュ３０からレベル１の道路メッシュ４０への接続点）に探索枝が到達すると、図９（ｂ）に示すように、アップリンク５０に対応するリンクを含むレベル１の道路メッシュ４０に切り替えて経路探索を行う。同様に、レベル１での経路探索によりレベル２へのアップリンク６０（レベル１の道路メッシュ４０からレベル２の道路メッシュ７０への接続点）に探索枝が到達すると、図９（ｃ）に示すレベル２の道路メッシュ７０に切り替えて経路探索を行う。
【０００６】
一方、図９（ｅ）に示すように、目的地２０の周辺では、全ての道路を含むレベル０の道路メッシュ８０を使用して経路探索を行う。そして、目的地２０から逆に辿っていってレベル１の道路メッシュ９０へのアップリンク１００に探索枝が到達すると、図９（ｄ）に示すように、アップリンク１００に対応するリンクを含むレベル１の道路メッシュ９０に切り替えて経路探索を行う。同様に、レベル１での経路探索によりレベル２へのアップリンク１１０（レベル１の道路メッシュ９０からレベル２の道路メッシュ７０への接続点）に探索枝が到達すると、図９（ｃ）に示すレベル２の道路メッシュ７０に切り替えて経路探索を行う。
【０００７】
最後に、図９（ｃ）に示すように、現在地１０から経路探索により求めたレベル２の道路メッシュ７０上のアップリンク６０と目的地２０から経路探索により求めたレベル２の道路メッシュ７０上のアップリンク１１０とをつなぐ経路を、レベル２の道路メッシュ７０を用いた経路探索を行うことにより求める。これにより、現在地１０から目的地２０に至る経路が全て決定されて、誘導経路の探索処理は終了する。
【０００８】
以上説明したような経路探索を行うことによって、現在地から目的地までの経路を求めるために、細街路から高速道路まで全ての道路が格納されたレベル０の道路メッシュを全区間にわたって使用する必要がなくなる。そのため、経路探索の時間を短縮することができる。この反面、現在地と目的地との間の中間領域の探索にはレベル０の道路メッシュが使用されない。そのため、中間領域では詳細道路が経路探索の対象外とされてしまうことにより、実際には遠回りしない経路があっても探索することができないという問題があった。
【０００９】
上記問題に対するものとしては、現在地と目的地との間の直線距離に対して経路探索により算出された誘導経路の距離が妥当か否かを評価し、妥当でない（遠回りである）と評価した場合には下位レベルの地図データを使用して再探索を行う技術が開示されている（例えば、特許文献１を参照）。具体的には、特許文献１に記載の技術では、経路探索により算出された誘導経路の距離と、現在地と目的地との間の直線距離との比率（誘導経路の距離／直線距離）が大きい場合に、下位レベルの地図データを使用して再探索を行うようにしている。
【００１０】
また、上記問題に対するものではないが、誘導経路上の進行方向と道路種別とが変わる進路変更場所を特定し、その特定した進行変更場所近辺において下位階層の地図データを用いた探索を行うことによって、誘導経路だけではなく、進路変更場所における迂回経路もユーザに提供できるようにした技術が開示されている（例えば、特許文献２を参照）。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開平１０−１５３４７７号公報
【特許文献２】特開２００２−２４３７６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上記特許文献１に記載された技術では、誘導経路の距離と直線距離との比率がしきい値より大きい場合（すなわち、大きく遠回りしている経路が探索された場合）に限り、下位レベルの地図データを使用して再探索が行われる。そのため、図１０（ａ）のように部分的に遠回りしている部分経路１２０、１３０を含む経路が探索されたときのように、誘導経路の距離と直線距離との比率があまり大きくなくてしきい値を超えない場合には、下位レベルの地図データを使用した再探索が行われないこととなる。それ故に、部分的に遠回りする経路が探索された場合にも再探索が行われるようにするためには、再探索が行うか否かの基準となるしきい値を小さくする必要がある。
【００１３】
しかし、そうした場合、誘導経路の距離が直線距離にかなり近い場合を除いて、誘導経路の全体について下位レベルの地図データを使用した再探索が行われることとなる。例えば、図１０（ｂ）のように、さらに再探索を行ってもこれ以上の近道がないような誘導経路が探索された場合であっても、その誘導経路の全体について再探索が行われる。そのため、しきい値を小さくすれば遠回りの経路が探索されるのを確実に防止することができる反面、常に再探索処理に時間がかかってしまい、ひいては最終的な誘導経路を設定するまでに長い時間を要してしまうという問題があった。
【００１４】
なお、上記特許文献２に記載された技術では、上位階層の地図データを用いて探索した誘導経路のうち、進行変更場所近辺では下位階層の地図データを用いた再探索が行われるが、それ以外の場所では再探索が行われない。そのため、誘導経路上の進行変更場所近辺以外のところに遠回りの経路が含まれないという保証はない。すなわち、上記特許文献２に記載された技術はそもそも、遠回りしない経路を探索することを目的とするものではない。
【００１５】
本発明は、このような問題を解決するために成されたものであり、遠回りの経路が探索されるのを防止し、かつ、最終的な誘導経路を設定するまでの時間を短縮できるようにすることを目的とする。
【課題を解決するための手段】
【００１６】
上記した課題を解決するために、本発明では、道路網の情報量に基づいて複数のレベルに階層化された地図データに基づいて探索した出発地から目的地までの第１の誘導経路の中から、両端のノード間において直線距離と第１の誘導経路に沿った距離との差分が所定値より大きい部分経路を抽出し、抽出した部分経路の両端のノード間の経路探索を、最下位レベルを含む地図データに基づいて行うことによって第２の部分経路を得る。そして、第１の誘導経路に含まれる部分経路を、探索した第２の部分経路で置き換えた第２の誘導経路を最終的な誘導経路として設定するようにしている。
【発明の効果】
【００１７】
上記のように構成した本発明によれば、最初に探索された誘導経路の中で部分的に遠回りしている部分が絞り込まれ、その絞り込まれた部分について最下位レベルを含む地図データに基づいた再探索が行われるため、遠回りの経路が誘導経路として設定されにくくなるようにすることができる。さらに、最初に探索された誘導経路の全体ではなく、その一部のみが再探索されるため、最初に探索された誘導経路の全体について再探索する従来技術に比べて、再探索処理に必要な時間を短縮することができ、ひいては最終的な誘導経路を設定するまでの時間を短縮することができる。
【図面の簡単な説明】
【００１８】
【図１】第１の実施形態によるナビゲーション装置の構成例を示すブロック図である。
【図２】第１の実施形態によるナビゲーション装置の主要構成例を示すブロック図である。
【図３】第１の実施形態による誘導経路探索部の処理を説明する図である。
【図４】第１の実施形態によるナビゲーション装置の動作例を示すフローチャートである。
【図５】第１の実施形態による誘導経路探索部の処理を説明する図である。
【図６】第２の実施形態によるナビゲーション装置の主要構成例を示すブロック図である。
【図７】第２の実施形態によるナビゲーション装置の主要構成の変形例を示すブロック図である。
【図８】第３の実施形態によるナビゲーション装置の主要構成例を示すブロック図である。
【図９】従来のナビゲーション装置における誘導経路探索処理の例を示す図である。
【図１０】従来のナビゲーション装置により探索された誘導経路の例を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態を図面に基づいて説明する。図１は、第１の実施形態によるナビゲーション装置２００の構成例を示すブロック図である。図１において、２１０はＤＶＤ−ＲＯＭ等の記録媒体であり、地図表示や経路探索等に必要な各種の地図データを記憶している。
【００２０】
ＤＶＤ−ＲＯＭ２１０に記録された地図データは、道路網の情報量の差異に基づいて３つのレベルに階層化された構造をしている。３つのレベルに階層化された地図データには、細街路から高速道路まで全ての道路を格納したレベル０といわれる道路メッシュ、主に市道以上の道路を格納しているレベル１といわれる道路メッシュ、高速道路や有料道路といった道路を格納しているレベル２といわれる道路メッシュがそれぞれ区別されて格納されている。この場合、レベルが上がるにつれて、道路網の情報量が少なく粗い地図データとなっている。各レベルの地図データには、地図表示に必要な描画ユニットのデータの他に、マップマッチングや経路探索等の各種の処理に必要な道路ユニットのデータが含まれている。
【００２１】
道路ユニットは、道路を細かく分割して複数のベクトルのつながりで表したときの個々のベクトルに相当する道路リンクに関するリンク情報と、個々の道路リンクの両端点に相当するノードに関するノード情報とを含んでいる。ノード情報には、ノードを一意に特定するノードＩＤ、ノードの位置(経緯度)、ノードに接続される道路リンク（リンクＩＤ）および、複数の道路リンクの端点に相当するノード（分岐点）であるか否かを示すフラグなどが含まれる。リンク情報には、道路リンクを一意に特定するリンクＩＤ、道路リンクの両端に接続されるノード（ノードＩＤ）、リンクコスト、道路種別（一般道路または高速道路）および道路属性などが含まれる。なお、ここでは地図データを記憶する記録媒体としてＤＶＤ−ＲＯＭ２１０を用いているが、ＣＤ−ＲＯＭ、ハードディスク、半導体メモリ等の他の記録媒体を用いても良い。
【００２２】
２２０は車両の現在位置を所定間隔毎に検出する車両位置検出部であり、自立航法センサ、ＧＰＳ受信機、位置計算用ＣＰＵ等で構成されている。自立航法センサは、所定走行距離毎に１個のパルスを出力して車両の移動距離を検出する車速センサ（距離センサ）と、車両の回転角度（移動方位）を検出する振動ジャイロ等の角速度センサ（相対方位センサ）とを含む。自立航法センサは、これらの車速センサおよび角速度センサによって車両の相対位置および方位を検出する。
【００２３】
位置計算用ＣＰＵは、自立航法センサから出力される自車両の相対的な位置および方位のデータに基づいて、絶対的な自車装置（推定車両位置）および車両方位を計算する。また、ＧＰＳ受信機は、複数のＧＰＳ衛星から送られてくる電波をＧＰＳアンテナで受信して、３次元測位処理あるいは２次元測位処理を行って車両の絶対位置および方位を計算する（車両方位は、現時点における自車位置と１サンプリング時間ΔＴ前の自車位置とに基づいて計算する）。
【００２４】
２３０はＤＶＤ−ＲＯＭ制御部であり、ＤＶＤ−ＲＯＭ２１０からの地図データの読み出しを制御する。２４０は地図データ記憶部であり、ＤＶＤ−ＲＯＭ制御部２３０の制御によってＤＶＤ−ＲＯＭ２１０から読み出された地図データを一時的に格納する。すなわち、ＤＶＤ−ＲＯＭ制御部２３０は、車両位置検出部２２０から車両現在位置の情報を入力し、その車両現在位置を含む所定範囲の地図データの読み出し指示を出力することにより、地図表示や誘導経路の探索に必要な地図データをＤＶＤ−ＲＯＭ２１０から読み出して地図データ記憶部２４０に格納する。
【００２５】
２５０はリモコン、タッチパネルまたは操作スイッチ等の操作部であり、ユーザがナビゲーション装置２００に対して各種の情報（例えば、経路誘導の目的地や経由地）を設定したり、各種の操作（例えば、メニュー選択操作、地図の拡大／縮小操作、手動地図スクロール、数値入力など）を行ったりするためのものである。
【００２６】
２６０は目的地設定部であり、ディスプレイ２７０に表示されている目的地設定用の操作画面において、ユーザによる操作部２５０の操作を介して指定された地点を目的地として設定する。そして、目的地設定部２６０は、設定した目的地を示す目的地情報を誘導経路探索部２８０に出力する。
【００２７】
誘導経路探索部２８０は、地図データ記憶部２４０に記憶されている地図データに基づいて、車両位置検出部２２０により検出された自車位置（出発地）から、目的地設定部２６０により設定された目的地に至る様々な経路上のリンクコストを順次加算し、リンクコストの合計が最も小さい経路を誘導経路として探索する。
【００２８】
２９０は誘導経路メモリであり、誘導経路探索部２８０により誘導経路が探索された場合、その探索された誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を誘導経路情報として一時的に格納する。
【００２９】
３００は地図表示制御部であり、車両位置検出部２２０により検出された自車位置情報と、地図データ記憶部２４０に記憶されている地図データとに基づいて、自車位置周辺の地図画像データを生成する。そして、地図表示制御部３００は、生成した地図画像データをディスプレイ２７０に出力することにより、自車位置周辺の地図画像をディスプレイ２７０に表示させる。
【００３０】
３１０は誘導経路案内部であり、誘導経路探索部２８０により誘導経路が探索された場合、車両位置検出部２２０により検出された自車位置情報と、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された誘導経路情報とに基づいて誘導経路案内を行う。具体的には、誘導経路案内部３１０は、ディスプレイ２７０に対して、地図表示制御部３００により生成された地図画像に重ねて誘導経路を他の道路とは異なる色で太く表示することにより、誘導経路の目的地までの走行案内を行う。また、誘導経路案内部３１０は、誘導経路上に存在する経路案内すべき分岐点（以下、案内分岐点という）に自車両が近づくたびに、当該案内分岐点に関する経路案内を行う。
【００３１】
次に、第１の実施形態によるナビゲーション装置２００の主要な機能構成について説明する。図２は、第１の実施形態によるナビゲーション装置２００の主要構成例を示すブロック図である。図２に示すように、誘導経路探索部２８０は、第１の誘導経路探索部４００、部分経路抽出部４２０、部分経路メモリ４４０、第２の誘導経路探索部４６０および誘導経路設定部４８０を備えて構成されている。
【００３２】
第１の誘導経路探索部４００は、車両位置検出部２２０により検出された自車位置情報と地図データ記憶部２４０に記憶されている地図データとに基づいて、現在位置（本発明の出発地に対応）から、目的地設定部２６０から出力された目的地情報により示される目的地までの第１の誘導経路を探索する。具体的には、第１の誘導経路探索部４００は、図９で説明した従来のやり方と同様に、現在位置および目的地の付近では最下位レベル（レベル０）の地図データを用いるとともに、出発地および目的地の付近以外の中間領域では最下位レベル以外の上位レベル（レベル１、２）の地図データを用いることによって、現在位置から目的地までの第１の誘導経路を探索する。そして、第１の誘導経路探索部４００は、探索した第１の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第１の誘導経路情報として誘導経路メモリ２９０に格納する。
【００３３】
なお、レベル０からレベル１、レベル１からレベル２への地図データの切り替えのことを以下では「クライミング」という。また、クライミングが実際に行われたノードのことを「クライミングノード」という。第１の誘導経路探索部４００は、第１の誘導経路を探索する際に、クライミングノードを特定するクライミングノード特定情報を誘導経路メモリ２９０に格納する。
【００３４】
部分経路抽出部４２０は、第１の誘導経路探索部４００により探索された第１の誘導経路のうち上位レベル（レベル１、２）の地図データに基づいて探索された誘導経路（以下、「上位探索経路」という）の中から、両端のノード間において直線距離に対する第１の誘導経路に沿った距離の比率が所定値（例えば、１．３）以上である部分経路を抽出する。この部分経路の抽出を行うために、部分経路抽出部４２０は、第１ノード特定部５００、第２ノード特定部５２０、第３ノード特定部５４０および第４ノード特定部５６０を備えて構成されている。
【００３５】
第１ノード特定部５００は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第１の誘導経路を構成するノードのうち、現在位置から最も近いクライミングノードを第１ノードとして特定する。そして、第１ノード特定部５００は、特定した第１ノードを示す第１ノード特定情報を第３ノード特定部５４０および第４ノード特定部５６０に出力する。
【００３６】
なお、最下位レベル（レベル０）の地図データおよび上位レベル（レベル１）の地図データに共通して存在するノードで必ずクライミングが行われるのであれば、当該共通して存在するノードであり、かつ、現在位置から最も近いノードを第１ノードとして特定するようにしても良い。この場合は、クライミングノード特定情報を参照する必要はない。
【００３７】
第２ノード特定部５２０は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第１の誘導経路を構成するノードのうち、目的地から最も近いクライミングノードを第２ノードとして特定する。そして、第２ノード特定部５２０は、特定した第２ノードを示す第２ノード特定情報を第３ノード特定部５４０に出力する。
【００３８】
なお、最下位レベル（レベル０）の地図データおよび上位レベル（レベル１）の地図データに共通して存在するノードで必ずクライミングが行われるのであれば、当該共通して存在するノードであり、かつ、目的地から最も近いノードを第２ノードとして特定するようにしても良い。この場合は、クライミングノード特定情報を参照する必要はない。
【００３９】
本実施形態では、第１ノードから第２ノードの間にある各ノードを第１の判定対象ノードとする。第１の誘導経路に含まれる全ノードを第１の判定対象ノードとしても良いが、第１ノードから第２ノードまでの上位探索経路に範囲を絞ることにより、第３ノード特定部５４０および第４ノード特定部５６０の判定処理の負荷を減らすことができる。
【００４０】
第３ノード特定部５４０は、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された第１の誘導経路情報とに基づいて、第１の誘導経路を構成するノードのうち、第１ノードから第２ノードまでに存在する第１の判定対象ノードの各々について、第１ノードから遠い順に、第１ノードと当該第１の判定対象ノードとの間の直線距離に対する、第１ノードと当該第１の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値より小さい第２の所定値（例えば、１．２）より大きいか否かについて判定を行う。そして、第３ノード特定部５４０は、第２の所定値より大きいと最初に判定した第１の判定対象ノードを第３ノードとして特定し、特定した第３ノードを示す第３ノード特定情報を第４ノード特定部５６０に出力する。第１ノードから第３ノードの間にある各ノードを第２の判定対象ノードとする。第２の判定対象ノードは、第１の判定対象ノードの一部であり、更に範囲が絞り込まれている。
【００４１】
第４ノード特定部５６０は、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された第１の誘導経路情報とに基づいて、第１の誘導経路を構成するノードのうち、第１ノードから第３ノードまでに存在するノードである第２の判定対象ノードの各々について、第３ノードから遠い順に、第３ノードと当該第２の判定対象ノードとの間の直線距離に対する、第３ノードと当該第２の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値（例えば、１．３）より大きいか否かについて判定を行う。そして、第４ノード特定部５６０は、所定値より大きいと最初に判定した第２の判定対象ノードを第４ノードとして特定する。
【００４２】
なお、第３ノード特定部５４０の判定処理で用いる第２の所定値と第４ノード特定部５６０の判定処理で用いる所定値との間で数値を変えているのは、所定値と第２の所定値との間で数値を同じにすると、第１ノードおよび第２ノードの片側からしか絞り込むことができず、第１の誘導経路の中で部分的に遠回りしている部分が第１ノードおよび第２ノードの何れか付近に存在しない限り、精度良く絞り込むことができないからである。
【００４３】
部分経路抽出部４２０は、誘導経路メモリ２９０に格納された第１の誘導経路情報に基づいて、第１の誘導経路のうち、第３ノードから第４ノードまでの経路を部分経路として抽出する。この抽出した部分経路は、範囲が絞り込まれたものになっている。そして、部分経路抽出部４２０は、抽出した部分経路のデータ（第３ノードから第４ノードに至るまでのノードの集合）を部分経路情報として部分経路メモリ４４０に格納する。
【００４４】
第２の誘導経路探索部４６０は、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と、部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。すなわち、部分経路のみを対象として、図９と同様の処理を行う。そして、第２の誘導経路探索部４６０は、生成した第２の部分経路のデータ（第３ノードから第４ノードに至るまでのノードの集合）を第２の部分経路情報として部分経路メモリ４４０に格納する。
【００４５】
誘導経路設定部４８０は、誘導経路メモリ２９０に格納された第１の誘導経路情報と、部分経路メモリ４４０に格納された部分経路情報および第２の部分経路情報とに基づいて、第１の誘導経路に含まれる部分経路を第２の部分経路で置き換えた第２の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第２の誘導経路情報として誘導経路メモリ２９０に格納する。
【００４６】
次に、第１の実施形態による誘導経路探索部２８０の処理について、図３を参照しながら具体例に沿って説明する。図３は、第１の実施形態による誘導経路探索部２８０の処理を説明する図である。図３（ａ）において、ａ１〜ａ３０は、第１の誘導経路探索部４００により探索された第１の誘導経路を構成する全ノードである。この中には、レベル０の地図データで探索されたもの、レベル１の地図データで探索されたもの、レベル２の地図データで探索されたものが混在している。第１の誘導経路において、ノードａ１は現在位置を示すノードであり、ノードａ３０は目的地を示すノードである。
【００４７】
第１ノード特定部５００は、第１の誘導経路を構成するノードａ１〜ａ３０のうち、現在位置から最も近いクライミングノード（レベル０からレベル１に地図データが切り替わったポイント）を第１ノードとして特定する。例えば、これがノードａ５であったとする。また、第２ノード特定部５２０は、第１の誘導経路を構成するノードａ１〜ａ３０のうち、目的地から最も近いクライミングノード（レベル０からレベル１に地図データが切り替わったポイント）を第２ノードとして特定する。例えば、これがノードａ２５であったとする。本実施形態では、図３（ｂ）のように、ノードａ５〜ａ２５を第１の判定対象ノードとする。
【００４８】
次に、第３ノード特定部５４０は、第１の誘導経路を構成するノードのうち、第１ノードから第２ノードまでに存在する第１の判定対象ノード（ノードａ１〜ノードａ２５）の各々について、第１ノードから遠い順に、第１ノードと当該第１の判定対象ノードとの間の直線距離に対する、第１ノードと当該第１の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が第２の所定値（１．２）より大きいか否かについて判定を行う。そして、第３ノード特定部５４０は、第２の所定値より大きいと最初に判定した第１の判定対象ノードを第３ノードとして特定する。例えば、これがノードａ１５であったとする。本実施形態では、図３（ｃ）のように、ノードａ５〜ａ１５を第２の判定対象ノードとする。
【００４９】
第４ノード特定部５６０は、第１の誘導経路を構成するノードのうち、第１ノードから第３ノードまでに存在する第２の判定対象ノード（ノードａ５〜ノードａ１５）の各々について、第３ノードから遠い順に、第３ノードと当該第２の判定対象ノードとの間の直線距離に対する、第３ノードと当該第２の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値（１．３）より大きいか否かについて判定を行う。そして、第４ノード特定部５６０は、所定値より大きいと最初に判定した第２の判定対象ノードを第４ノードとして特定する。例えば、これがノードａ７であったとする。
【００５０】
部分経路抽出部４２０は、図３（ｄ）に示すように、第１の誘導経路のうち、第３ノード（ノードａ１５）から第４ノード（ノードａ７）までの経路を部分経路として抽出する。第２の誘導経路探索部４６０は、最下位レベル（レベル０）を含む地図データを用い、部分経路抽出部４２０により抽出された部分経路の両端のノード（ノードａ７およびノードａ１５）をそれぞれ出発地および目的地として、部分経路間の経路探索を行う。これにより、第２の部分経路１５０を生成する。ここで、第２の部分経路１５０が探索されたのは、部分経路の両端のノードの付近では最下位レベル（レベル０）の地図データを用いて探索が行われ、上位レベル（レベル１、２）の地図データには存在しない経路を探索できたためである。誘導経路設定部４８０は、第１の誘導経路に含まれる部分経路を第２の部分経路１５０で置き換えた第２の誘導経路のデータを第２の誘導経路情報として誘導経路メモリ２９０に格納する。
【００５１】
次に、本実施形態における誘導経路探索部２８０の動作について説明する。図４は、本実施形態における誘導経路探索部２８０の動作例を示すフローチャートである。図４におけるステップＳ１００の処理は、誘導経路探索部２８０が、操作部２５０に対するユーザ操作を介して誘導経路を探索する要求を受け付けることにより開始する。
【００５２】
まず、第１の誘導経路探索部４００は、車両位置検出部２２０により検出された自車位置情報と地図データ記憶部２４０に記憶されている地図データとに基づいて、現在位置から目的地までの第１の誘導経路を探索する（ステップＳ１００）。次に、第１ノード特定部５００は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第１の誘導経路を構成するノードのうち、現在位置から最も近いクライミングノードを第１ノードとして特定する（ステップＳ１２０）。
【００５３】
次に、第２ノード特定部５２０は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第１の誘導経路を構成するノードのうち、目的地から最も近いクライミングノードを第２ノードとして特定する（ステップＳ１４０）。
【００５４】
次に、第３ノード特定部５４０は、第２ノード特定部５２０により特定された第２ノードを第１の判定対象ノードとして設定する（ステップＳ１６０）。次に、第３ノード特定部５４０は、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された第１の誘導経路情報とに基づいて、第１ノードと第１の判定対象ノードとの間の直線距離に対する、第１ノードと当該第１の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が第２の所定値（１．２）より大きいか否かについて判定を行う（ステップＳ１８０）。
【００５５】
もし、第２の所定値より大きくないと第３ノード特定部５４０にて判定した場合（ステップＳ１８０にてＮＯ）、第３ノード特定部５４０は、第１の誘導経路に沿って、第１の判定対象ノードから１つ第１ノード側に移動したノードを新たな第１の判定対象ノードとして設定する（ステップＳ２００）。その後、処理はステップＳ１８０に遷移する。一方、第２の所定値より大きいと第３ノード特定部５４０にて判定した場合（ステップＳ１８０にてＹＥＳ）、第３ノード特定部５４０は、そのときに第１の判定対象ノードとして設定しているノードを第３ノードとして特定する（ステップＳ２２０）。
【００５６】
次に、第４ノード特定部５６０は、第１ノード特定部５００により特定された第１ノードを第２の判定対象ノードとして設定する（ステップＳ２４０）。次に、第４ノード特定部５６０は、地図データ記憶部２４０に記憶されている地図データと、誘導経路メモリ２９０に格納された第１の誘導経路情報とに基づいて、第３ノードと第２の判定対象ノードとの間の直線距離に対する、第３ノードと当該第２の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値（例えば、１．３）より大きいか否かについて判定を行う（ステップＳ２６０）。
【００５７】
もし、所定値より大きくないと第４ノード特定部５６０にて判定した場合（ステップＳ２６０にてＮＯ）、第４ノード特定部５６０は、第１の誘導経路に沿って、第２の判定対象ノードから１つ第３ノード側に移動したノードを新たな第２の判定対象ノードとして設定する（ステップＳ２８０）。その後、処理はステップＳ２６０に遷移する。一方、所定値より大きいと第４ノード特定部５６０にて判定した場合（ステップＳ２６０にてＹＥＳ）、第４ノード特定部５６０は、そのときに第２の判定対象ノードとして設定しているノードを第４ノードとして特定する（ステップＳ３００）。
【００５８】
次に、部分経路抽出部４２０は、誘導経路メモリ２９０に格納された第１の誘導経路情報に基づいて、第１の誘導経路のうち、第３ノード特定部５４０により特定された第３ノードから第４ノード特定部５６０により特定された第４ノードまでの経路を部分経路として抽出する（ステップＳ３２０）。次に、第２の誘導経路探索部４６０は、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）に基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する（ステップＳ３４０）。
【００５９】
最後に、誘導経路設定部４８０は、誘導経路メモリ２９０に格納された第１の誘導経路情報に基づいて、第１の誘導経路に含まれる部分経路を第２の誘導経路探索部４６０によって探索された第２の部分経路で置き換えた第２の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第２の誘導経路情報として誘導経路メモリ２９０に格納する（ステップＳ３６０）。ステップＳ３６０の処理が完了することによって、誘導経路探索部２８０は図４における処理を終了する。
【００６０】
以上詳しく説明したように、第１の実施形態では、レベル０〜２の地図データに基づいて適宜クライミングしながら探索した現在位置（出発地）から目的地までの第１の誘導経路の中から、両端のノード間において直線距離に対する第１の誘導経路に沿った距離の比率が所定値より大きい部分経路を抽出し、抽出した部分経路についてレベル０〜２の地図データに基づいて再探索を行うことによって第２の部分経路を得る。そして、第１の誘導経路に含まれる部分経路を、探索した第２の部分経路で置き換えた第２の誘導経路を最終的な誘導経路として設定するようにしている。
【００６１】
このように構成した第１の実施形態によれば、最初に探索された誘導経路の中で部分的に遠回りしている部分が絞り込まれ、その絞り込まれた部分について最下位レベルを含む地図データに基づいた再探索が行われるため、遠回りの経路が誘導経路として設定されにくくなるようにすることができる。さらに、最初に探索された誘導経路の全体ではなく、その一部のみが再探索されるため、最初に探索された誘導経路の全体について再探索する従来技術に比べて、再探索処理に必要な時間を短縮することができ、ひいては最終的な誘導経路を設定するまでの時間を短縮することができる。
【００６２】
また、第１の実施形態では、第１の誘導経路のうち、上位レベルの地図データに基づいて探索された上位探索経路に範囲を絞り、その中から部分経路を抽出するようにしている。このように構成した第１の実施形態によれば、最下位レベルの地図データに基づいて探索された経路は、部分経路の抽出処理を行う対象から除かれる。この除かれた経路は、再探索を行ってもこれ以上の近道がないので、部分経路の抽出対象から除くことに問題は生じない。以上より、第１の誘導経路の全体を対象として部分経路の抽出処理を行わない分、その抽出処理にかかる時間を短くすることができる。
【００６３】
なお、上記第１の実施形態では、部分経路抽出部４２０にて部分経路を抽出する際、第２ノードを特定した後に第１ノードを特定する例について説明したが、第１ノードを特定した後に第２ノードを特定するようにしても良い。また、上記第１の実施形態では、部分経路抽出部４２０にて部分経路を抽出する際、第３ノードを特定した後に第４ノードを特定する例について説明したが、第４ノードを特定した後に第３ノードを特定するようにしても良い。
【００６４】
また、上記第１の実施形態では、部分経路抽出部４２０が、第１の誘導経路のうち、第３ノードから第４ノードまでの経路を部分経路として抽出する例について説明したが、本発明はこれに限定されない。例えば、部分経路抽出部４２０は、第１の誘導経路のうち、第１ノードから第３ノードからまでの経路を部分経路として抽出するようにしても良い。
【００６５】
上記第１の実施形態では、部分経路について再探索を行うときも、クライミングをしながら経路探索を行っている。そのため、図３（ｄ）のように探索された第２の部分経路１５０の中にも遠回りの経路が含まれている可能性がある。そこで、第２の部分経路１５０を探索するときにクライミングを行った場合には、第２の部分経路１５０を対象として同様の処理を再度行うようにしても良い。
【００６６】
具体的には、第２の誘導経路探索部４６０は、第２の部分経路を探索する際に、クライミングノードを特定するクライミングノード特定情報を誘導経路メモリ２９０に格納する。そして、第２の誘導経路探索部４６０は、誘導経路メモリ２９０に格納されたクライミングノード特定情報に基づいて、第２の部分経路１５０を探索するときにクライミングを行ったか（すなわち、第２の部分経路の中に、部分的に遠回りとなっているところが存在する可能性があるか）否かについて判定する。第２の誘導経路探索部４６０は、第２の部分経路１５０を探索するときにクライミングを行ったと判定した場合、その旨を部分経路抽出部４２０に通知する。
【００６７】
部分経路抽出部４２０は、第２の部分経路１５０を探索するときにクライミングを行った旨の通知を第２の誘導経路探索部４６０から受けた場合、第２の部分経路の中から、両端のノード間において直線距離に対する第２の部分経路に沿った距離の比率が所定値より大きい第３の部分経路を抽出する。その抽出処理の内容は、図３を用いて説明したのと同様である。
【００６８】
第２の誘導経路探索部４６０は、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と、部分経路メモリ４４０に格納された第３の部分経路情報とに基づいて、第３の部分経路の両端のノード間の経路探索を行うことによって第４の部分経路を生成する。そして、第２の誘導経路探索部４６０は、生成した第４の部分経路のデータを第４の部分経路情報として部分経路メモリ４４０に格納する。
【００６９】
誘導経路設定部４８０は、誘導経路メモリ２９０に格納された第２の誘導経路情報と、部分経路メモリ４４０に格納された第３の部分経路情報および第４の部分経路情報とに基づいて、第２の誘導経路に含まれる第３の部分経路を第４の部分経路で置き換えた第３の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第３の誘導経路情報として誘導経路メモリ２９０に格納する。
【００７０】
このように構成した場合、再探索して求めた第２の部分経路１５０が部分的に遠回りする経路を含んでいても、その部分的に遠回りする経路を確実に解消し、より最短の誘導経路を求めることができる。なお、このようにして２回目の再探索によって第４の部分経路を求めるときにもクライミングが発生した場合には、同様の手順で３回目の再探索を行うようにしても良い。
【００７１】
また、上記実施形態では、現在位置から目的地までの第１の誘導経路の中から１ヵ所だけ部分経路を抽出して再探索を行っているが、それ以外の場所にも遠回りの経路が含まれている可能性がある。そこで、１ヶ所の部分経路について再探索が終わった後は、別の場所において部分経路を抽出して再探索するようにしても良い。
【００７２】
具体的には、部分経路抽出部４２０は、第２の誘導経路（更に再探索された場合は第３の誘導経路。以下、同様）から第２の部分経路（図３（ｄ）のノードａ９〜ａ１４の部分）を除いた残りの経路（以下、「残り経路」という）の中から、両端のノード間において直線距離に対する第２の誘導経路に沿った距離の比率が所定値（例えば、１．３）より大きい第５の部分経路を抽出する。そして、部分経路抽出部４２０は、抽出した第５の部分経路のデータを第５の部分経路情報として部分経路メモリ４４０に格納する。なお、残り経路は、第２の誘導経路から第２の部分経路を除いた部分ではなく、第２の誘導経路から部分経路（図３（ｄ）のノードａ７〜ａ１５の部分）を除いたものとしても良い。
【００７３】
第２の誘導経路探索部４６０は、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と、部分経路メモリ４４０に格納された第５の部分経路情報とに基づいて、第５の部分経路の両端のノード間の経路探索を行うことによって第６の部分経路を生成する。そして、第２の誘導経路探索部４６０は、生成した第６の部分経路のデータを第６の部分経路情報として部分経路メモリ４４０に格納する。
【００７４】
誘導経路設定部４８０は、誘導経路メモリ２９０に格納された第２の誘導経路情報と、部分経路メモリ４４０に格納された第５の部分経路情報および第６の部分経路情報とに基づいて、第２の誘導経路に含まれる第５の部分経路を第６の部分経路で置き換えた第４の誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を第４の誘導経路情報として誘導経路メモリ２９０に格納する。
【００７５】
次に、誘導経路探索部２８０の処理について、図５を参照しながら具体例に沿って説明する。図５は、誘導経路探索部２８０が図３のように第２の部分経路１５０を探索して誘導経路メモリ２９０に格納した後の処理を説明する図である。図５において、ａ１５〜ａ３０は、第２の誘導経路から部分経路１５０を除いた経路のうち、ノードａ１５よりも目的地（ノードａ３０）側の残り経路上に位置するノードである。
【００７６】
第１ノード特定部５００は、残り経路を構成するノードａ１５〜ａ３０のうち、ノードａ１５から最も近いクライミングノードを第１ノードとして特定する。例えば、これがノードａ１５であったとする。なお、第１の誘導経路を探索するときに、ノードａ１５よりも現在位置側で最上位レベル（レベル２）までクライミングしている場合がある。その場合、ノードａ１５〜ａ３０のうち、ノードａ１５から最も近いクライミングノードは存在しない。この場合、ノードａ１５を第１ノードとする。
【００７７】
また、第２ノード特定部５２０は、残り経路を構成するノードａ１５〜ａ３０のうち、目的地から最も近いクライミングノード（レベル０からレベル１に地図データが切り替わったポイント）を第２ノードとして特定する。例えば、これがノードａ２５であったとする。本実施形態では、図５（ｂ）のように、ノードａ１５〜ａ２５を第１の判定対象ノードとする。
【００７８】
次に、第３ノード特定部５４０は、残り経路を構成するノードのうち、第１ノードから第２ノードまでに存在する第１の判定対象ノード（ノードａ１５〜ノードａ２５）の各々について、第１ノードから遠い順に、第１ノードと当該第１の判定対象ノードとの間の直線距離に対する、第１ノードと当該第１の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が第２の所定値（１．２）より大きいか否かについて判定を行う。そして、第３ノード特定部５４０は、第２の所定値より大きいと最初に判定した第１の判定対象ノードを第３ノードとして特定する。例えば、これがノードａ１９であったとする。本実施形態では、図５（ｃ）のように、ノードａ１５〜ａ１９を第２の判定対象ノードとする。
【００７９】
第４ノード特定部５６０は、残り経路を構成するノードのうち、第１ノードから第３ノードまでに存在する第２の判定対象ノード（ノードａ１５〜ノードａ１９）の各々について、第３ノードから遠い順に、第３ノードと当該第２の判定対象ノードとの間の直線距離に対する、第３ノードと当該第２の判定対象ノードとの間の第１の誘導経路に沿った距離の比率が所定値（１．３）より大きいか否かについて判定を行う。そして、第４ノード特定部５６０は、所定値より大きいと最初に判定した第２の判定対象ノードを第４ノードとして特定する。例えば、これがノードａ１６であったとする。
【００８０】
部分経路抽出部４２０は、図５（ｄ）に示すように、残り経路のうち、第３ノード（ノードａ１９）から第４ノード（ノードａ１６）までの経路を第５の部分経路として抽出する。第２の誘導経路探索部４６０は、最下位レベル（レベル０）を含む地図データを用い、部分経路抽出部４２０により抽出された第５の部分経路の両端のノード（ノードａ１６およびノードａ１９）をそれぞれ出発地および目的地として、部分経路間の経路探索を行う。これにより、第６の部分経路１６０を生成する。
【００８１】
なお、残り経路から抽出した第５の部分経路の目的地側の端点である第３ノードが第２ノードの２つ以上手前であれば、同様の処理を繰り返すことにより残り経路の別の位置も再探索する。また、ノードａ７から現在位置側も同様にして行う。このように構成した場合、範囲を絞り込んで再探索した部分を除いた残り経路が部分的に遠回りする経路を含んでいても、その部分的に遠回りする経路を確実に解消し、より最短の誘導経路を求めることができる。
【００８２】
次に、本発明の第２の実施形態を図面に基づいて説明する。図６は、第２の実施形態によるナビゲーション装置２００の主要構成例を示すブロック図である。図６に示すように、誘導経路探索部２８０は、その機能構成として、直線距離判定部６００を更に備えている。また、誘導経路探索部２８０は、その機能構成として、図２の第２の誘導経路探索部４６０の代わりに、第２の誘導経路探索部４６０′を備えている。なお、この図６において、図２に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００８３】
直線距離判定部６００は、地図データ記憶部２４０に記憶されている地図データと、部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード間の直線距離が所定距離未満であるか否かについて判定し、その判定結果を第２の誘導経路探索部４６０′に通知する。
【００８４】
第２の誘導経路探索部４６０′は、部分経路の両端のノード間の直線距離が所定距離未満である旨の通知を直線距離判定部６００から受けた場合、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）のみ）と部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。
【００８５】
また、第２の誘導経路探索部４６０′は、部分経路の両端のノード間の直線距離が所定距離未満でない旨の通知を直線距離判定部６００から受けた場合、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。
【００８６】
部分経路の両端のノード間の直線距離が所定距離未満であれば、部分経路の距離は短いので、最下位レベルの詳細な地図データだけで経路探索を行っても、再探索処理に多くの時間がかかってしまう可能性は少ないと考えられる。そして、全ての道路を網羅した最下位レベルの地図データだけを用いてクライミングすることなく経路探索を行うので、最短の誘導経路が確実に探索される。よって、再探索処理時間を増やすことなく、部分経路について、遠回りのない最短の経路を探索することができる。
【００８７】
なお、部分経路の両端のノード間の直線距離の代わりに部分経路の両端のノード間のノード数で、最下位レベルの詳細な地図データだけで経路探索を行うか否かを判断しても良い。図７は、ノード数で判断する場合のナビゲーション装置２００の主要構成例を示すブロック図である。図７に示すように、誘導経路探索部２８０は、その機能構成として、ノード数判定部６２０を更に備えている。また、誘導経路探索部２８０は、その機能構成として、図２の第２の誘導経路探索部４６０の代わりに、第２の誘導経路探索部４６０′′を備えている。なお、この図７において、図２に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００８８】
ノード数判定部６２０は、部分経路メモリ４４０に格納された部分経路情報に基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード間に存在するノードの数が所定数未満であるか否かについて判定し、その判定結果を第２の誘導経路探索部４６０′′に通知する。
【００８９】
第２の誘導経路探索部４６０′′は、部分経路の両端のノード間に存在するノードの数が所定数未満である旨の通知をノード数判定部６２０から受けた場合、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）のみ）と部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。
【００９０】
また、第２の誘導経路探索部４６０′′は、部分経路の両端のノード間に存在するノードの数が所定数未満でない旨の通知をノード数判定部６２０から受けた場合、地図データ記憶部２４０に記憶されている地図データ（最下位レベル（レベル０）を含む）と部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード（第３ノードおよび第４ノード）間の経路探索を行うことによって第２の部分経路を生成する。
【００９１】
このように構成した場合も、図６のように直線距離で判断する場合と同様の効果が得られる。すなわち、部分経路の両端のノード間のノード数が所定数未満であれば、部分経路の距離は短いので、最下位レベルの詳細な地図データだけで経路探索を行っても、再探索処理に多くの時間がかかってしまう可能性は少ないと考えられる。そして、全ての道路を網羅した最下位レベルの地図データだけを用いてクライミングすることなく経路探索を行うので、最短の誘導経路が確実に探索される。よって、再探索処理時間を増やすことなく、部分経路について、遠回りのない最短の経路を探索することができる。
【００９２】
次に、本発明の第３の実施形態を図面に基づいて説明する。図８は、第３の実施形態によるナビゲーション装置２００の主要構成例を示すブロック図である。図８に示すように、誘導経路探索部２８０は、その機能構成として、第１の所要時間算出部７００、第２の所要時間算出部７２０および時間判定部７４０を更に備えている。また、誘導経路探索部２８０は、その機能構成として、図２の第２の誘導経路探索部４６０の代わりに、第２の誘導経路探索部４６０′′′を備えている。なお、この図８において、図２に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００９３】
第１の所要時間算出部７００は、地図データ記憶部２４０に記憶されている地図データ（道路ユニットのリンク情報（リンクコスト））と、部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の所要走行時間を第１の所要時間として算出する。そして、第１の所要時間算出部７００は、算出した第１の所要時間を示す第１の所要時間情報を時間判定部７４０に出力する。
【００９４】
第２の所要時間算出部７２０は、地図データ記憶部２４０に記憶されている地図データ（道路ユニットのノード情報（経緯度））と、部分経路メモリ４４０に格納された部分経路情報とに基づいて、部分経路抽出部４２０により抽出された部分経路の両端のノード間の直線距離を、当該部分経路の探索に使用された地図データの１つ下のレベルの地図データにのみ含まれる道路の道路種別に応じた予測走行速度で除算した時間を第２の所要時間として算出する。そして、第２の所要時間算出部７２０は、算出した第２の所要時間を示す第２の所要時間情報を時間判定部７４０に出力する。
【００９５】
時間判定部７４０は、第２の所要時間算出部７２０から出力された第２の所要時間情報により示される第２の所要時間が第１の所要時間算出部７００から出力された第１の所要時間情報により示される第１の所要時間より大きいか否かについて判定し、その判定結果を第２の誘導経路探索部４６０′′′に通知する。
【００９６】
次に具体例を１つ説明する。部分経路は高速道路であるとする。また、部分経路の探索に使用された地図データの１つ下のレベルの地図データにのみ含まれる道路の道路種別が一般道路であり、その道路種別に応じた予測走行速度が４０［ｋｍ／ｈ］であるとする。この場合、第２の所要時間より第１の所要時間より大きければ、部分経路がたとえ遠回りであったとしても、一般道路を通行するより速い。
【００９７】
第２の誘導経路探索部４６０′′′は、第２の所要時間が第１の所要時間より大きくない旨の通知を受けた場合、最下位レベル（レベル０）を含む地図データを用いることによって、部分経路の両端のノード間の経路探索を行う。また、第２の誘導経路探索部４６０′′′は、第２の所要時間が第１の所要時間より大きい旨の通知を受けた場合、部分経路の両端のノード間の経路探索を行わない。
【００９８】
このように構成した第３の実施形態によれば、部分経路について、最下位レベルの地図データを用いて探索される経路の方が、上位レベルの地図データを用いて既に探索された経路より却って時間がかかると考えられる場合、部分経路について無駄な再探索処理を行わないようにすることができる。
【００９９】
なお、上記第１〜第３の実施形態では、地図データが、道路網の情報量の差異に基づいて３つのレベルに階層化された構造をしている例について説明したが、本発明はこれに限定されない。例えば、地図データが、道路網の情報量の差異に基づいて２つ、または、４つ以上のレベルに階層化された構造をしていても良い。
【０１００】
また、上記第１〜第３の実施形態では、第１の誘導経路の中から、両端のノード間において直線距離に対する第１の誘導経路に沿った距離の比率が所定値以上である部分経路を抽出する例について説明したが、本発明はこれに限定されない。例えば、第１の誘導経路の中から、両端のノード間において第１の誘導経路に沿った距離から直線距離を減算した距離が所定値より大きい部分経路を抽出するようにしても良い。
【０１０１】
その他、上記第１〜第３の実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその精神、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【０１０２】
１５０ 第２の部分経路
１６０ 第６の部分経路
２００ ナビゲーション装置
２４０ 地図データ記憶部
２８０ 誘導経路探索部
４００ 第１の誘導経路探索部
４２０ 部分経路抽出部
４６０，４６０′，４６０′′，４６０′′′ 第２の誘導経路探索部
４８０ 誘導経路設定部
５００ 第１ノード特定部
５２０ 第２ノード特定部
５４０ 第３ノード特定部
５６０ 第４ノード特定部
６００ 直線距離判定部
６２０ ノード数判定部
７００ 第１の所要時間算出部
７２０ 第２の所要時間算出部
７４０ 時間判定部
【特許請求の範囲】
【請求項１】
道路網の情報量に基づいて複数のレベルに階層化され、下位のレベルほど道路網の情報量が多い地図データを記憶する地図データ記憶部と、
出発地および目的地の付近では最下位レベルの地図データを用いるとともに、前記出発地および前記目的地の付近以外の中間領域では前記最下位レベル以外の上位レベルの地図データを用いることによって、前記出発地から前記目的地までの第１の誘導経路を探索する第１の誘導経路探索部と、
前記第１の誘導経路探索部により探索された前記第１の誘導経路の中から、両端のノード間において直線距離と前記第１の誘導経路に沿った距離との差分が所定値より大きい部分経路を抽出する部分経路抽出部と、
前記最下位レベルを含む地図データを用いることによって、前記部分経路抽出部により抽出された前記部分経路の両端のノード間の経路探索を行うことによって第２の部分経路を生成する第２の誘導経路探索部と、
前記第１の誘導経路に含まれる前記部分経路を前記第２の誘導経路探索部によって探索された前記第２の部分経路で置き換えた第２の誘導経路を最終的な誘導経路として設定する誘導経路設定部とを備えたことを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部は、前記第１の誘導経路のうち、前記上位レベルの地図データに基づいて探索された上位探索経路の中から前記部分経路を抽出することを特徴とするナビゲーション装置。
【請求項３】
請求項２に記載のナビゲーション装置において、
前記部分経路抽出部は、前記第１の誘導経路を構成するノードのうち、前記第１の誘導経路の一端から最も近く、かつ、使用する地図データのレベルの切り替えが行われたノードを第１ノードとして特定する第１ノード特定部と、
前記第１の誘導経路を構成するノードのうち、前記第１の誘導経路の他端から最も近く、かつ、使用する地図データのレベルの切り替えが行われたノードを第２ノードとして特定する第２ノード特定部とを更に備え、
前記第１の誘導経路を構成するノードのうち、前記第１ノード特定部により特定された前記第１ノードから前記第２ノード特定部により特定された前記第２ノードまでに存在するノードで構成された前記上位探索経路の中から前記部分経路を抽出することを特徴とするナビゲーション装置。
【請求項４】
請求項３に記載のナビゲーション装置において、
前記部分経路抽出部は、前記上位探索経路を構成するノードである判定対象ノードの各々について、前記第１ノードから遠い順に、前記第１ノードと当該判定対象ノードとの間の直線距離と前記第１ノードと当該判定対象ノードとの間の前記上位探索経路に沿った距離との差分が前記所定値より大きいか否かについて判定を行い、当該所定値より大きいと最初に判定した判定対象ノードを第３ノードとして特定する第３ノード特定部を更に備え、前記上位探索経路を構成するノードのうち、前記第１ノードから前記第３ノードまでの経路を前記部分経路として抽出することを特徴とするナビゲーション装置。
【請求項５】
請求項３に記載のナビゲーション装置において、
前記部分経路抽出部は、前記上位探索経路を構成するノードである判定対象ノードの各々について、前記第１ノードから遠い順に、前記第１ノードと当該判定対象ノードとの間の直線距離と前記第１ノードと当該判定対象ノードとの間の前記上位探索経路に沿った距離との差分が前記所定値より小さい第２の所定値より大きいか否かについて判定を行い、当該第２の所定値より大きいと最初に判定した判定対象ノードを第３ノードとして特定する第３ノード特定部と、
前記上位探索経路を構成するノードのうち、前記第１ノードから前記第３ノードまでに存在するノードである判定対象ノードの各々について、前記第３ノードから遠い順に、前記第３ノードと当該判定対象ノードとの間の直線距離と前記第３ノードと当該判定対象ノードとの間の前記上位探索経路に沿った距離との差分が前記所定値より大きいか否かについて判定を行い、当該所定値より大きいと最初に判定した判定対象ノードを第４ノードとして特定する第４ノード特定部とを更に備え、
前記上位探索経路のうち前記第３ノードから前記第４ノードまでの経路を前記部分経路として抽出することを特徴とするナビゲーション装置。
【請求項６】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部により抽出された前記部分経路の両端のノード間の直線距離が所定距離未満であるか否かについて判定する直線距離判定部を更に備え、
前記第２の誘導経路探索部は、前記直線距離判定部により前記部分経路の両端のノード間の直線距離が前記所定距離未満であると判定された場合、前記最下位レベルの地図データのみを用いることによって、前記部分経路の両端のノード間の経路探索を行うことを特徴とするナビゲーション装置。
【請求項７】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部により抽出された前記部分経路の両端のノード間に存在するノードの数が所定数未満であるか否かについて判定するノード数判定部を更に備え、
前記第２の誘導経路探索部は、前記ノード数判定部により前記部分経路の両端のノード間に存在するノードの数が前記所定数未満であると判定された場合、前記最下位レベルの地図データのみを用いることによって、前記部分経路の両端のノード間の経路探索を行うことを特徴とするナビゲーション装置。
【請求項８】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部は、前記第２の誘導経路探索部により前記上位レベルの地図データを用いて前記第２の部分経路が探索された場合、前記第２の部分経路の中から、両端のノード間において直線距離と前記第２の部分経路に沿った距離との差分が前記所定値より大きい第３の部分経路を更に抽出し、
前記第２の誘導経路探索部は、前記最下位レベルを含む地図データを用いることによって、前記第３の部分経路の両端のノード間の経路探索を行うことによって第４の部分経路を生成し、
前記誘導経路設定部は、前記第２の誘導経路に含まれる前記第３の部分経路を前記第４の部分経路で置き換えた第３の誘導経路を最終的な誘導経路として設定することを特徴とするナビゲーション装置。
【請求項９】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部は、前記第２の誘導経路から前記第２の部分経路を除いた経路の中から、両端のノード間において直線距離と前記第２の誘導経路に沿った距離との差分が所定値より大きい第５の部分経路を更に抽出し、
前記第２の誘導経路探索部は、前記最下位レベルを含む地図データを用いることによって、前記部分経路抽出部により抽出された前記第５の部分経路の両端のノード間の経路探索を行うことによって第６の部分経路を生成し、
前記誘導経路設定部は、前記第２の誘導経路に含まれる前記第５の部分経路を前記第６の部分経路で置き換えた第４の誘導経路を最終的な誘導経路として設定することを特徴とするナビゲーション装置。
【請求項１０】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部により抽出された前記部分経路の所要走行時間を第１の所要時間として算出する第１の所要時間算出部と、
前記部分経路の両端のノード間の直線距離を、当該部分経路の探索に使用された地図データの１つ下のレベルの地図データにのみ含まれる道路の道路種別に応じた予測走行速度で除算した時間を第２の所要時間として算出する第２の所要時間算出部と、
前記第２の所要時間が前記第１の所要時間より大きいか否かについて判定する時間判定部とを更に備え、
前記第２の誘導経路探索部は、前記時間判定部により前記第２の所要時間が前記第１の所要時間より大きくないと判定された場合に限り、前記最下位レベルを含む地図データを用いることによって、前記部分経路の両端のノード間の経路探索を行うことを特徴とするナビゲーション装置。
【請求項１１】
道路網の情報量に基づいて複数のレベルに階層化され、下位のレベルほど道路網の情報量が多い地図データを記憶する地図データ記憶部と、出発地および目的地の付近では最下位レベルの地図データを用いるとともに、前記出発地および前記目的地の付近以外の中間地域では前記最下位レベル以外の上位レベルの地図データを用いることによって、前記出発地から前記目的地までの第１の誘導経路を探索する第１の誘導経路探索部とを備えたナビゲーション装置における誘導経路探索方法であって、
前記第１の誘導経路探索部により探索された前記第１の誘導経路の中から、両端のノード間において直線距離と前記第１の誘導経路に沿った距離との差分が所定値より大きい部分経路を抽出する第１のステップと、
前記最下位レベルを含む地図データを用いることによって、前記第１のステップにより抽出された前記部分経路の両端のノード間の経路探索を行うことによって第２の部分経路を生成する第２のステップと、
前記第１の誘導経路に含まれる前記部分経路を前記第２のステップによって探索された前記第２の部分経路で置き換えた第２の誘導経路を最終的な誘導経路として設定する第３のステップとを有することを特徴とする誘導経路探索方法。
【請求項１】
道路網の情報量に基づいて複数のレベルに階層化され、下位のレベルほど道路網の情報量が多い地図データを記憶する地図データ記憶部と、
出発地および目的地の付近では最下位レベルの地図データを用いるとともに、前記出発地および前記目的地の付近以外の中間領域では前記最下位レベル以外の上位レベルの地図データを用いることによって、前記出発地から前記目的地までの第１の誘導経路を探索する第１の誘導経路探索部と、
前記第１の誘導経路探索部により探索された前記第１の誘導経路の中から、両端のノード間において直線距離と前記第１の誘導経路に沿った距離との差分が所定値より大きい部分経路を抽出する部分経路抽出部と、
前記最下位レベルを含む地図データを用いることによって、前記部分経路抽出部により抽出された前記部分経路の両端のノード間の経路探索を行うことによって第２の部分経路を生成する第２の誘導経路探索部と、
前記第１の誘導経路に含まれる前記部分経路を前記第２の誘導経路探索部によって探索された前記第２の部分経路で置き換えた第２の誘導経路を最終的な誘導経路として設定する誘導経路設定部とを備えたことを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部は、前記第１の誘導経路のうち、前記上位レベルの地図データに基づいて探索された上位探索経路の中から前記部分経路を抽出することを特徴とするナビゲーション装置。
【請求項３】
請求項２に記載のナビゲーション装置において、
前記部分経路抽出部は、前記第１の誘導経路を構成するノードのうち、前記第１の誘導経路の一端から最も近く、かつ、使用する地図データのレベルの切り替えが行われたノードを第１ノードとして特定する第１ノード特定部と、
前記第１の誘導経路を構成するノードのうち、前記第１の誘導経路の他端から最も近く、かつ、使用する地図データのレベルの切り替えが行われたノードを第２ノードとして特定する第２ノード特定部とを更に備え、
前記第１の誘導経路を構成するノードのうち、前記第１ノード特定部により特定された前記第１ノードから前記第２ノード特定部により特定された前記第２ノードまでに存在するノードで構成された前記上位探索経路の中から前記部分経路を抽出することを特徴とするナビゲーション装置。
【請求項４】
請求項３に記載のナビゲーション装置において、
前記部分経路抽出部は、前記上位探索経路を構成するノードである判定対象ノードの各々について、前記第１ノードから遠い順に、前記第１ノードと当該判定対象ノードとの間の直線距離と前記第１ノードと当該判定対象ノードとの間の前記上位探索経路に沿った距離との差分が前記所定値より大きいか否かについて判定を行い、当該所定値より大きいと最初に判定した判定対象ノードを第３ノードとして特定する第３ノード特定部を更に備え、前記上位探索経路を構成するノードのうち、前記第１ノードから前記第３ノードまでの経路を前記部分経路として抽出することを特徴とするナビゲーション装置。
【請求項５】
請求項３に記載のナビゲーション装置において、
前記部分経路抽出部は、前記上位探索経路を構成するノードである判定対象ノードの各々について、前記第１ノードから遠い順に、前記第１ノードと当該判定対象ノードとの間の直線距離と前記第１ノードと当該判定対象ノードとの間の前記上位探索経路に沿った距離との差分が前記所定値より小さい第２の所定値より大きいか否かについて判定を行い、当該第２の所定値より大きいと最初に判定した判定対象ノードを第３ノードとして特定する第３ノード特定部と、
前記上位探索経路を構成するノードのうち、前記第１ノードから前記第３ノードまでに存在するノードである判定対象ノードの各々について、前記第３ノードから遠い順に、前記第３ノードと当該判定対象ノードとの間の直線距離と前記第３ノードと当該判定対象ノードとの間の前記上位探索経路に沿った距離との差分が前記所定値より大きいか否かについて判定を行い、当該所定値より大きいと最初に判定した判定対象ノードを第４ノードとして特定する第４ノード特定部とを更に備え、
前記上位探索経路のうち前記第３ノードから前記第４ノードまでの経路を前記部分経路として抽出することを特徴とするナビゲーション装置。
【請求項６】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部により抽出された前記部分経路の両端のノード間の直線距離が所定距離未満であるか否かについて判定する直線距離判定部を更に備え、
前記第２の誘導経路探索部は、前記直線距離判定部により前記部分経路の両端のノード間の直線距離が前記所定距離未満であると判定された場合、前記最下位レベルの地図データのみを用いることによって、前記部分経路の両端のノード間の経路探索を行うことを特徴とするナビゲーション装置。
【請求項７】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部により抽出された前記部分経路の両端のノード間に存在するノードの数が所定数未満であるか否かについて判定するノード数判定部を更に備え、
前記第２の誘導経路探索部は、前記ノード数判定部により前記部分経路の両端のノード間に存在するノードの数が前記所定数未満であると判定された場合、前記最下位レベルの地図データのみを用いることによって、前記部分経路の両端のノード間の経路探索を行うことを特徴とするナビゲーション装置。
【請求項８】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部は、前記第２の誘導経路探索部により前記上位レベルの地図データを用いて前記第２の部分経路が探索された場合、前記第２の部分経路の中から、両端のノード間において直線距離と前記第２の部分経路に沿った距離との差分が前記所定値より大きい第３の部分経路を更に抽出し、
前記第２の誘導経路探索部は、前記最下位レベルを含む地図データを用いることによって、前記第３の部分経路の両端のノード間の経路探索を行うことによって第４の部分経路を生成し、
前記誘導経路設定部は、前記第２の誘導経路に含まれる前記第３の部分経路を前記第４の部分経路で置き換えた第３の誘導経路を最終的な誘導経路として設定することを特徴とするナビゲーション装置。
【請求項９】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部は、前記第２の誘導経路から前記第２の部分経路を除いた経路の中から、両端のノード間において直線距離と前記第２の誘導経路に沿った距離との差分が所定値より大きい第５の部分経路を更に抽出し、
前記第２の誘導経路探索部は、前記最下位レベルを含む地図データを用いることによって、前記部分経路抽出部により抽出された前記第５の部分経路の両端のノード間の経路探索を行うことによって第６の部分経路を生成し、
前記誘導経路設定部は、前記第２の誘導経路に含まれる前記第５の部分経路を前記第６の部分経路で置き換えた第４の誘導経路を最終的な誘導経路として設定することを特徴とするナビゲーション装置。
【請求項１０】
請求項１に記載のナビゲーション装置において、
前記部分経路抽出部により抽出された前記部分経路の所要走行時間を第１の所要時間として算出する第１の所要時間算出部と、
前記部分経路の両端のノード間の直線距離を、当該部分経路の探索に使用された地図データの１つ下のレベルの地図データにのみ含まれる道路の道路種別に応じた予測走行速度で除算した時間を第２の所要時間として算出する第２の所要時間算出部と、
前記第２の所要時間が前記第１の所要時間より大きいか否かについて判定する時間判定部とを更に備え、
前記第２の誘導経路探索部は、前記時間判定部により前記第２の所要時間が前記第１の所要時間より大きくないと判定された場合に限り、前記最下位レベルを含む地図データを用いることによって、前記部分経路の両端のノード間の経路探索を行うことを特徴とするナビゲーション装置。
【請求項１１】
道路網の情報量に基づいて複数のレベルに階層化され、下位のレベルほど道路網の情報量が多い地図データを記憶する地図データ記憶部と、出発地および目的地の付近では最下位レベルの地図データを用いるとともに、前記出発地および前記目的地の付近以外の中間地域では前記最下位レベル以外の上位レベルの地図データを用いることによって、前記出発地から前記目的地までの第１の誘導経路を探索する第１の誘導経路探索部とを備えたナビゲーション装置における誘導経路探索方法であって、
前記第１の誘導経路探索部により探索された前記第１の誘導経路の中から、両端のノード間において直線距離と前記第１の誘導経路に沿った距離との差分が所定値より大きい部分経路を抽出する第１のステップと、
前記最下位レベルを含む地図データを用いることによって、前記第１のステップにより抽出された前記部分経路の両端のノード間の経路探索を行うことによって第２の部分経路を生成する第２のステップと、
前記第１の誘導経路に含まれる前記部分経路を前記第２のステップによって探索された前記第２の部分経路で置き換えた第２の誘導経路を最終的な誘導経路として設定する第３のステップとを有することを特徴とする誘導経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−２２０９０２（Ｐ２０１１−２２０９０２Ａ）
【公開日】平成２３年１１月４日（２０１１．１１．４）
【国際特許分類】
【出願番号】特願２０１０−９１８１７（Ｐ２０１０−９１８１７）
【出願日】平成２２年４月１２日（２０１０．４．１２）
【出願人】（０００１０１７３２）アルパイン株式会社 (2,424)
【Ｆターム（参考）】
【公開日】平成２３年１１月４日（２０１１．１１．４）
【国際特許分類】
【出願日】平成２２年４月１２日（２０１０．４．１２）
【出願人】（０００１０１７３２）アルパイン株式会社 (2,424)
【Ｆターム（参考）】
[ Back to top ]