(57)【特許請求の範囲】
【請求項１】
出発地から設定された目的地に到達するための経路を検索する機能を有するナビゲーション装置において、
車が通行可能な道路に関する情報と、車が通行不可能なダミー道路に関する情報とを格納した道路情報格納手段と、
前記道路情報格納手段に格納されている情報に基づいて出発地から目的地への経路を検索する経路探索手段と、
前記経路探索手段によって探索された出発地から目的地への経路に前記ダミー道路が含まれる場合には、前記ダミー道路を除いた経路を表示する経路表示手段と、
を備えたことを特徴とするナビゲーション装置。
【請求項２】
前記道路情報格納手段は、前記ダミー道路の両端に位置するダミーノードを示す情報と、これらダミーノード間を結ぶリンクを示す情報とを含む情報を格納したこと、
を特徴とする請求項１記載のナビゲーション装置。
【請求項３】
前記道路情報格納手段に格納された前記ダミーノードを示す情報は、当該ノードがダミーノードであることを示す識別情報を含み、
前記経路表示手段は、前記ダミーノード間のリンクとしてのダミー道路を除いた経路を表示すること、
を特徴とする請求項２記載のナビゲーション装置。
【請求項４】
出発地から設定された目的地に到達するための経路を検索する経路検索方法であって、
車が通行可能な道路に関する情報と、車が通行不可能なダミー道路に関する情報とを道路情報格納部に格納し、
前記道路情報格納部に格納されている情報に基づいて出発地から目的地への経路を検索し、
経路検索の結果としての経路に前記ダミー道路が含まれる場合には、前記ダミー道路を除いて経路探索結果とすること、
を特徴とする経路検索方法。
【請求項５】
請求項４記載の経路探索方法による経路探索結果を表示すること、
を特徴とする情報端末装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は車載ナビゲーション装置に関し、特に、出発地又は目的地に見合う実質的に最適な経路誘導を行い得る経路探索技術に関する。
【０００２】
【従来の技術】
車の現在位置から目的地までの経路を地図上に示して表示し、走行補助をなすナビゲーション装置の経路誘導方法として、従来、地図上の道路や地名、建物等を数値化して作られたデータベース（デジタル地図データベース)をＣＤ−ＲＯＭ等の記録媒体に保持させ、それらデータベースに基づいてユーザが出発地及び目的地を入力（設定)すると予め装置が保持している道路データベースを基に誘導路を探索・計算し、得られた誘導路と、ジャイロスコープや車速パルスを用いた自立航法およびＧＰＳやＦＭ多重を用いた電波航法から推定した自車位置とをマップマッチングしながら画面上に表示して経路誘導する方法がよく知られている。
【０００３】
この場合、ユーザによって出発地および目的地が設定されると、ナビゲーション装置は出発地と目的地間の経路探索を実行して誘導経路を決定するが、このとき、出発地或いは目的地から、経路対象道路及び走行状況の上から出発地可（出発地とすることが可能）或いは目的地可（目的地とすることが可能）と推定される道路から最も近い道路を選択し、選択された道路からよく知られた経路探索方法（例えば、ダイクストラ法或いはその応用)により経路探索を行っていた。
【０００４】
なお、出発地可の道路か否かは、例えば、現在走行中の道路が従来技術のマップマッチングで高速道路と認識（推定)される場合にはその道路を出発地可とする（その高速道路上で現在位置から最も近いノードを出発地点とすることができる）など、車の走行状況で決定される。また、目的地可の道路とは案内をその道路で終了する道路（例えば、目的地のそばを通る道路で案内を終了する場合）をいい、目的地不可の道路とは、例えば、案内を高速道路上で終了しないとしている場合のその高速道路をいう。
【０００５】
【発明が解決しようとする課題】
しかしながら、従来の経路誘導方法では経路対象道路及び走行状況の上から出発地可或いは目的地可と推定される道路から距離的に最も近い道路を選択するので、目的地や出発地の立地条件によっては一番近い道路として誘導（表示）された道路からは目的地に車で到達できなかったり、出発地から一番近い道路として誘導された道路に行くことができないといった現象が生ずることがあるという問題点があった。
【０００６】
例えば、図８（ａ）に示すようにユーザが設定した目的地６１が観光地（××寺）であり、距離的には観光地６１に近いが（観光地６１との間には深い谷川６７（或いは、山など)のような障害があるので）車ではもちろん、徒歩でも観光地６１にアクセスできない道路６５と、距離的には道路６５よりも観光地６１に遠くまた車道がないので車では直接行けないが、駐車場６２に駐車させて駐車場６２からロープウエイか徒歩で行くことができる道路６３がある場合に、前記従来技術では観光地６１を目的地として設定すると道路６３より道路６５の方が観光地６１に近いと判断して道路６５上の案内ポイント６６まで誘導してしまうので、着いてみて道路６５の案内ポイント６６からは観光地６１に行けないことを知ったユーザにとって腹立たしい結果になるという問題点があった。
【０００７】
また、例えば、ユーザが設定した目的地が図９（ａ）に示すようなホテル７１であり、正面側には道路７５が通っているが、駐車場７２と道路７５の間に障害（例えば、大きな段差或いは崖）があって車を駐車場７２に駐車させることができないような場合、駐車場７２に行ける道路７３があっても前記従来技術ではこのホテル７１を目的地として設定すると（データベースではホテル等の建物では正面を基点とすることが多いので）道路７５のホテル正面７１’付近を案内ポイントと判断して誘導してしまうので、直接的に駐車場７２に行けないという不都合があった。
【０００８】
また、例えば、ユーザが図１０（ａ）に示すように柵８６又は塀等で区切られていてすぐ傍を通る道路８５には出られず、出入り口が道路８５とは反対の道路８３側にしかない大きな駐車場８１に車を駐車させているような場合に、道路８３と駐車場８１との距離が大きいときには、車８２−１〜８１−ｎのいずれのユーザが従来技術のナビゲーション装置を起動させてもナビゲーション装置は駐車場８１に近い道路８５を目的地可の道路として決定して案内するのでユーザは戸惑ってしまうという問題点があり、道路８３と駐車場８１との距離が短くても車８２−１のユーザが従来技術のナビゲーション装置を起動させたときには駐車場８１と接続している道路８３を出発可の道路として決定するが、車８２−ｎのユーザが従来技術のナビゲーション装置を起動させると車８２−ｎに近い道路８５を出発可の道路として決定してしまうといった問題点があった。
【０００９】
本発明は上記従来技術に基づくナビゲーション装置の問題点を解決するためになされたものであり、現在位置から実質的にアクセスできる道路又は（及び）目的地に実質的にアクセス可能なポイントまで案内できるナビゲーション装置の提供を目的とする。
【００１０】
【課題を解決するための手段】
上記課題を解決するために、第１の発明のナビゲーション装置は、車の現在位置から目的地までの経路を地図上に示して表示し、走行補助をなすナビゲーション装置において、車が通行可能な道路に関する経路情報と、車が通行可能な道路と車が通行不可能な出発地または目的地の間に設定したダミー道路に関する経路情報とを道路データとして格納した道路情報格納手段と、出発地及び目的地を設定する設定手段と、この設定手段によって設定された出発地及び目的地と道路情報格納手段に格納されている道路データから該出発地及び目的地に最も近い道路をそれぞれ決定すると共に、決定されたそれぞれの道路上での探索開始地点を決定する探索開始地点決定手段と、この探索開始地点決定手段によって決定された探索開始地点から経路探索を実行する経路探索手段と、この経路探索手段によって探索された経路から前記ダミー道路を取り除いて表示する経路表示手段と、を備えたことを特徴とする。
【００１１】
また、第２の発明は上記第１の発明のナビゲーション装置において、経路探索手段はダミー道路のコストを計算しないことを特徴とする。
【００１２】
また、第３の発明は上記第１の発明のナビゲーション装置において、経路探索手段はダミー道路のコストをゼロとして計算することを特徴とする。
【００１３】
【発明の実施の形態】
［発明の概要］
図８の例で、（ｂ）に示すように道路６３に接続して観光地６１に向かうダミー道路６４及び始端（ダミーノード)６４’及び終端（ダミーノード）６１’を予めデータベースに登録しておく。ユーザが目的地として観光地６１を入力（設定）すると、このダミー道路６４から経路探索を開始し、経路探索を終了した時点でこのダミー道路６４を取り除いて表示する。また、経路探索開始時点でこのダミー道路６４に最も近い経路対象道路６３から経路探索を開始することにより従来例のように距離的には近いが実質的にアクセス不可能な道路６５上のポイント６６に案内するようなことがなく、観光地６１に実質的にアクセス可能な地点（ダミーノード６４’）まで案内する（この場合、ダミーノード６４’を駐車場６２の近くに設定しておけばより便利となる）。
【００１４】
また、図９の場合にも（ｂ）に示すようにダミー道路７４及びダミーノード７４’〜７９’をデータベースに登録しておくことにより同様に経路探索を行って案内ポイント（ダミーノード）７４’に案内することができる。また、図１０の場合にも（ｂ）に示すようにダミー道路８４及びダミーノード８４’〜９０’をデータベースに登録しておくことにより出発可の道路のうち実質的に最も近い道路８３の出発地点（ダミーノード８４’）に案内できる。
【００１５】
［ナビゲーション装置の構成例］
図１は本発明に基づく経路探索方法を適用可能なナビゲーション装置の一実施例を示すブロック図であり、ナビゲーション装置１００は、絶対位置・方位検出部１、相対方位検出部２、車速検出部３、制御部４、メモリ５〜８、ユーザインターフェイス部９、表示部１０、入力部１１、ＣＤ−ＲＯＭ制御部１２及びＦＭ多重受信及び処理部１３を備えている。
【００１６】
絶対位置・方位検出部１はアンテナ１ａを有し、ＧＰＳ（Glowbal Positioning System）からの電波をアンテナ１ａで受信して絶対位置（絶対座標)及び方位を検出して制御部４に送出する。
【００１７】
相対方位検出部２はジャイロ等の方位検出装置を備え、検出した方位を制御部４に送出する。また、車速検出部３は車の走行に伴って得る回転パルスから車速を得て制御部４に送出する。これらの検出値（方位及び速度)はＧＰＳから得た絶対位置及び方向を補正し車の現在位置を決定するために制御部４で用いられる。
【００１８】
制御部４はＣＰＵとタイマやＣＰＵ周辺回路を備えたマイクロプロセッサ構成を有しており、ＣＰＵは上述の各回路等にバスラインを介して接続し、メモリ（プログラム格納用ＲＯＭ）５に格納されているナビゲーション制御プログラムによりナビゲーション装置１００全体の制御を行なうと共に、入力部１０からの入力信号に対応してナビゲーション装置１００の各機能の実行制御等（例えば、マップマッチングの実行制御、地図及び経路等の表示制御、本発明に基づく経路探索の実行制御等）を行なう。
【００１９】
メモリ５はプログラム格納用ＲＯＭであり、プログラム格納用ＲＯＭ５はＰＲＯＭやＦＲＯＭ（フラッシュＲＯＭ）等が用いられ、制御プログラムや、マップマッチングプログラム、地図及び経路等の表示プログラム、経路探索プログラムを格納する。また、プログラム格納用ＲＯＭに表示部１０に表示するアイコンやメニュー及び図形パターン及び定数を格納することもできる。
【００２０】
メモリ６はＤＲＡＭ（Dynamic RAM）からなり、制御部４の制御下でＣＤ−ＲＯＭ制御部１２を介してＣＤ−ＲＯＭに格納された地図のうちの所要の地図及びその広域隣接エリアの地図を取り込む。また、メモリ７はＳＲＡＭ（Static RAM）のような高速メモリからなり、ナビゲーション装置１００の起動時に制御部４のプログラム格納用ＲＯＭから制御プログラムを取り込むと共に、制御プログラムの制御シーケンスに従ってマップマッチングプログラム、地図及び経路等の表示プログラム、経路探索プログラム等を適時取り込み、マップマッチング処理や経路探索処理等のナビゲーション処理の実行に用いられる。また、メモリ８は表示メモリであってＶＲＡＭからなり、制御部４の制御下でＤＲＡＭ６から取り出された１画面分の地図や、経路探索により探索された誘導路や、名称やメニュー等のビットマップイメージを保持する。
【００２１】
ユーザインターフェイス部９は表示部１０や入力部１１と制御部４を結ぶインターフェイスであり、表示部１０は表示メモリ８に保持された地図や誘導路や、名称やメニュー等を表示する。
【００２２】
入力部１１はユーザによる出発地及び目的地の設定入力や地図の選定その他必要な情報入力手段であり、入力用のキーやボタン或いはカーソル移動やポイント（指示)用のキーを備えておりそれらのキーやボタンが操作されると状態信号がユーザインターフェイス部９を介して制御部４に送られる。
【００２３】
ＣＤ−ＲＯＭ制御部１２はナビゲーション用の情報を効率的に取り出すように構築されたデータベースを格納したＣＤ−ＲＯＭから必要な情報を読み出す。また、実施例では読み出し制御されるＣＤ−ＲＯＭを（地図・道路情報と目的地や経路情報等を含むもの）２枚としたが、（地図・道路情報と目的地や経路情報を一括して含む）１枚のＣＤ−ＲＯＭを読み出し制御するようにしてもよく、また、３枚以上のＣＤ−ＲＯＭの読み出し制御を行うようにしてもよい。また、実施例ではナビゲーション用の情報を効率的に取り出すように構築されたデータベースをＣＤ−ＲＯＭに格納したが、これに限定されず、大容量で且つコンパクトであって、ユーザがナビゲーション装置本体に着脱容易な記録媒体であればよい（この場合は、ＣＤ−ＲＯＭ制御部１２は当該記録媒体用の読み出し制御部に置換される)。
【００２４】
ＦＭ多重受信及び処理部１３はアンテナ１３ａを有し、ＦＭ多重波をアンテナ１３ａで受信して高速道路等での自車位置情報等を検出して制御部４に送出する。検出値はＧＰＳから得た絶対位置及び方向を補正して自車位置を決定するために制御部４で用いられる。
【００２５】
［ナビゲーション用データベース］
ナビゲーション用データベースは、本実施例では、道路地図情報を取り出しやすいように構築して格納した道路地図データベース及び経路情報を取り出しやすいように格納した経路データベース等（共に公知の構造でよい）をＣＤ−ＲＯＭに格納している（地図情報データベースは、対象国全体分の地図の枚数が１枚のＣＤ−ＲＯＭに入りきらない場合には複数のＣＤ−ＲＯＭに格納される。また、経路データベースは観光、スポーツ、レジャーといったような目的別に分けられてＣＤ−ＲＯＭに格納されることもある)。
【００２６】
道路地図情報は、地図データ（道路、建物、地形等の図形情報及びそれらを意味付ける文字や記号）と、道路上のノード（交叉点、コーナー、始端及び終端）とノード間を関係付けるリンク情報（方向性を有する）と地名等を表現する文字情報からなる。実施例では、道路、建物、地形等の画像情報等を予め地図ファイル（図示せず)に登録し、道路上のノード及びノード間を関係付けるリンク情報を予め道路情報ファイル（図２）に登録し、地名等を表現する文字コード等を地図ファイル及び道路情報ファイルと関連付けて予め名称ファイル（図示せず)に登録している。
【００２７】
また、経路情報は経路及び主要ノードと地図を関連付けるリンク情報と目的地点の名称からなる。実施例ではノードと地図を関連付けるリンク情報を予め経路ファイル（図３（ａ））に登録し、目的地点（或いは出発地点)名を地図ファイル及び経路ファイルに関連付けて名称ファイル（図３（ｂ））に登録している。地図データは日本（又は諸外国）の公的機関の発行する縮尺の地図（日本なら国土地理院発行の２５，０００分の１の縮尺の地図)に相当する内容であり、当該国全体を覆う枚数分の地図データが地図番号と共にそれぞれ地図ファイルに登録されている（１枚の記録媒体に登録しきれない場合には複数枚の記録媒体に分割されて登録されている)。
【００２８】
また、道路は高速道路、有料道路、国道、県道、主要一般道、一般道などに分類されそれぞれに経路のコスト計算時に用いる重み係数が与えられているが、本発明では道路の分類中にダミー道路（仮道路)を付加し、図８、図９の例に示すように目的地に最も近い道路からは直接目的地にアクセスできない場合に、車は通行できないがアクセスする手段のある道路の中で最も目的地に近い道路上の一点（通常は目的地に徒歩や車以外の手段でアクセスしやすい位置（ダミーノード））からダミー道路を設定して道路情報ファイルおよび道順ファイルに予め登録する（実施例ではダミー道路の重み係数＝０としている)。
【００２９】
図２は道路情報ファイルの一実施例を示す図であり、道路情報ファイル２１０はリンク情報、すなわち、地図ファイルに格納されている各地図データの地図番号を記録した地図番号欄（領域）２１１と、道路上のノード番号を順番に登録したノード登録欄２１２と、ノードの座標データを登録した座標欄２１３と、そのノードに隣接するノードを登録した隣接ノード欄２１４を有している。
【００３０】
また、図２で、（ａ）の例は図８の道路６３のリンク情報を示し、ノード欄２１２には地図番号「１５５」の地図上にある道路６３の各ノード番号が登録され、ノード表示位置欄２１３には各ノードの画面上の座標が登録され、隣接ノード欄２１４にはそれぞれのノードに最も近いノードの番号が登録されている。なお、４行目のノード「１５」と６行目のノード「１６」の隣接ノードとして図８（ｂ）で設定したダミー道路６４との接点であるダミーノード６４’が登録され、ノード欄２１２の５行目にダミーノード６４’が登録されている。
【００３１】
また、図２で、（ｂ）の登録例は説明上他の道路のリンク情報を省略し、図８（ｂ）、図９（ｂ）、図１０（ｂ）のダミー道路（６４、７４、８４）のリンク情報のみを示した例であり、地図番号欄２１１にはダミー道路６４と目的地６１を含む地図番号「１５５」と「１５７」が登録され、地図番号「１５５」にはダミーノード６４’とその表示位置及び隣接ノードが対応付けられて登録され、地図番号「１５７」には終端のダミーノード６１’とその表示位置及び隣接ノードが対応付けられて登録される。
【００３２】
なお、図８（ｂ）の例では道路６３のダミーノード６４’から目的地近傍まで直線的にダミー道路６４を設定したが、図９（ｂ）や図１０（ｂ）に示すようなコーナーのあるダミー道路７４，７８を設定してもよい。
【００３３】
すなわち、図９（ｂ）の例のように道路７３のダミーノード７４’から駐車場７１に沿って正面玄関７１’の近傍７９’までダミーノード７４’、７７’、７８’、７９’を持つダミー道路７４を設定して図２（ｂ）の地図番号「２９９」の部分に示すように登録してもよく、また、図１０（ｂ）の例のように道路８３のダミーノード８４’から駐車場８１のコーナーに沿うダミーノード８６’、８７’、８８’、８９’、９０’を持つダミー道路８４４を設定して図２（ｂ）の地図番号「５２３」の部分に示すように登録してもよい。この図９（ｂ）の例では、ダミー道路７４が駐車場７２からホテル７１の建物の中を通り、ホテル正面７１’側のダミーノード７９’に達している。このように、ダミー道路は、道路そのものが存在しないところに位置するものとして設定されることもある。
【００３４】
また、図２の例では道路情報ファイル２１０にダミー道路を登録したが、道路情報ファイル２１０には道路がダミー道路と接している場合にその接している点のダミーノードだけを登録し（図２（ａ））、ダミー道路を経路ファイル（図３）に登録するようにしてもよい。
【００３５】
上記構成のファイルを含むデータベースを用いてユーザが出発地および目的地を設定したとき、ナビゲーション装置１００は後述（図４、図６)するように目的地（又は出発地）の最も近くにダミー道路が設定されていると、そのダミー道路に接続する道路から経路探索を開始し、実質的に目的地（又は出発道路)に最も近いポイント（＝始端として登録されたダミーポイント)に案内する。
【００３６】
図３は経路ファイルにダミー道路を登録した例を示す図である。図３で、（ａ）は経路ファイルの一実施例を示し、経路ファイル３１０はダミー道路のノードを順路にあわせて並べたノードの組み番号を登録したデータ番号欄３１１と、その順路を含む地図（目的地点と順路が１枚の地図でカバーできない場合には複数の地図）の番号を登録した地図番号欄３１２と、順路上のノード番号を登録した順路欄３１３を有している。
【００３７】
また、図３（ｂ）は目的地名称ファイルの一実施例を示す図であり、目的地名称ファイル３２０は図３（ａ）の地図番号を登録した地図番号欄３２１と、図３（ａ）で地図番号に対応付けられたデータ番号を登録したデータ番号欄３２２と、目的地名の表示位置（座標）を登録する座標欄３２３と、目的地（又は出発地）の名称（文字コード）を登録した名称欄３２４を有している。
【００３８】
すなわち、図３（ａ）の登録例のうちデータ番号「３５」の順路は図８のダミー道路６４の始端（ダミーノード）「６４’」から目的地点６１までの最適経路を示し、地図番号欄３１２にはノード６４’を含む地図の地図番号「１５５」とダミー道路６４の終端（ダミーノード）６１’及び目的地６１を含む地図の番号「１５７」が登録され、順路欄３１３にはノード「６４’」、「６１’」が登録されている。同様に、データ番号「１２１」の順路は図９のダミー道路７４の始端（ダミーノード）「７４’」から目的地（ホテルの駐車場７２)までの最適経路を示し、地図番号欄３１２にはノード７４’とダミー道路７４の終端（ダミーノード）７１’及び目的地（ホテル)７１を含む地図の番号「２９９」が登録され、順路欄３１３にはノード「７４’」、「７７’」、「７８’」、「７９’」が登録されている。同様に、データ番号「１７１」の順路は図１０のダミー道路８４の終端（ダミーノード）「９０’」から出発地点８４’までの最適経路を示し、地図番号欄３１２には駐車場８１と出発道路８３を含む地図の番号「５２３」が登録され、順路欄３１３にはノード「８４’」、「８７’」、「８８’」、「８９’」、「９０’」が登録されている。
【００３９】
また、図３（ｂ）で、地図番号「１５７」のデータ「３５」に対応付けられてダミー道路６４の終端６１’近傍の目的地名称（××寺)の文字コードが地名欄３２４に登録され、座標欄３１３には××寺の位置が登録されている。同様に、地図番号「２９９」のデータ「１２１」に対応付けられてダミー道路７４の終端６１’近傍の目的地（○○ホテル)の文字コードが地名欄３２４に登録され、座標欄３１３には○○ホテルの位置が登録されている。同様に、地図番号「１７５」のデータ「１７５」に対応付けられてダミー道路８４の始端８４’のある駐車場の文字コードが地名欄３２４に登録され、座標欄３１３にはその駐車場の位置が登録されている。
【００４０】
上記構成のファイルを含むデータベースを用いてユーザが出発地および目的地を設定したとき、ナビゲーション装置１００は図２の場合と同様に目的地（又は出発地）の最も近くにダミー道路が設定されていると、そのダミー道路に接続する道路から経路探索を開始し、実質的に目的地（又は出発道路)に最も近いポイント（＝始端として登録されたダミーポイント)に案内する。
【００４１】
［ナビゲーションシステムの構成］
図４はナビゲーション装置１００のナビゲーション動作を実行するナビゲーションシステムの構成例を示すブロック図であり、ナビゲーションシステム４００は実施例ではプログラムで構成され、制御部４のＣＰＵによって実行制御される。
【００４２】
図４で、ナビゲーションシステム４００は、画面上に出発地名、目的地名等を表示しユーザの選択（指定)操作により出発地及び目的地を設定する設定手段４１１（図７（Ｓ１））と、絶対位置方位検索部１、相対方位検出部２、車速検出部３、ＦＭ多重受信及び処理部１３で得た位置情報や方位情報を基に自車の現在位置を決定（例えば、マップマッチング処理により現在位置を決定)する現在位置決定手段４１２（図７（Ｓ３））と、現在位置（出発地）から最も近い出発道路を得て出発地点を決定する出発道路決定手段４１３（図７（Ｓ４、Ｓ５））と、設定した目的地に最も近い目的地道路を得て出発地点を決定する目的地決定手段４１４（図７（Ｓ６））と、経路検索アルゴリズム（例えば、後述のダイクストラ法）により出発地から目的地までの経路探索を行う経路探索手段４１５（図７（Ｓ７））と、経路探索の結果にダミー道路が含まれる場合にはそのダミー道路を取り除くオフセット手段４１６（図７（Ｓ８））及び探索された経路を表示部１０に表示する経路表示手段４１７（図７（Ｓ９））を有している。なお、本実施例ではナビゲーションシステム４００を上述の設定手段４１１〜経路表示手段４１７の７つのモジュールを含むように構成したが、これらをさらに細分してもよく、また、その一部又は全部をハードウエアで構成するようにしてもよい。
【００４３】
［経路検索アルゴリズム］
本実施例では経路検索アルゴリズムとして両方向探索のダイクストラ法を用いたがこれに限定されない。ダイクストラ法では、出発地と目的地の双方から経路探索を開始し、双方から求めてきた経路がつながった場合にそのつながった経路を最適経路として決定する。なお、経路（リンク)のコストは道路の種類、ノード間の距離、傾斜等に所定の重み付けをして得た値である。
【００４４】
すなわち、図５のネットワークを例とするとダイクストラ法による経路決定は下記▲１▼〜▲５▼の手順により行われる。
▲１▼  出発地可のリンクで最も出発地（Ｓ）に近いリンクを探し、そのリンクのコストを計算し、メモリに格納する。
▲２▼  目的地可のリンクで最も目的地に近いリンクを探し、そのリンクのコストを計算し、メモリに格納する。
▲３▼  メモリに格納されているリンクの中で最も小さいコストを持つリンクを抽出する。
▲４▼  選択されたリンクの先（次）のノードから次のリンクを探す。図５の例では、リンクＳ→Ａが抽出された場合にはノードＡから進むことのできるリンク（Ａ→Ｂ、Ａ→Ｄ又はＡ→Ｃ）を探す。また、これらリンク（Ａ→Ｂ、Ａ→Ｄ又はＡ→Ｃ）のコストにはリンクＳ→Ａのコストを加算し、更に、計算開始時点で進行不可能（例えば、通行禁止時間帯、通行禁止期間のリンク)か否かを判定して、通行付加のリンクに付いてはメモリに格納しない。
なお、本発明のダミー道路をネットワークを構成するリンクとして経路探索する場合（仮にリンクＡ→Ｂが本発明のダミー道路の場合）にはダミー道路に相当するリンク（リンクＡ→Ｂ）を除いたリンク（Ａ→Ｄ又はＡ→Ｃ）をメモリに格納するようにする必要がある（本実施例では、前述したようにダミー道路の重み係数を０（ゼロ)としているので、ダイクストラ法によるコスト加算を行っても実際にはリンクがダミー道路の場合にはそれを除いたと同様の結果となる)。  ▲５▼  上記手順▲３▼、▲４▼を繰り返して得た出発地Ｓからの経路と、目的地Ｔから上記手順▲１▼〜▲４▼と同様にして求められた経路とが接続したか否かを判定し、つながった場合にそのつながった経路を求める経路とする。
【００４５】
すなわち、図５で、出発地Ｓからの探索がノードＤに到達（例えば、経路Ｓ→Ａ→Ｄ）していて、目的地Ｔ側からの探索がノードＤに到達（例えば、Ｔ→Ｈ→Ｆ→Ｄ）した時点で経路（Ｓ→Ａ→Ｄ→Ｔ→Ｈ→Ｆ→Ｄ）を得る。
【００４６】
［経路探索動作例］
図６は、本発明に基づくダミー道路をリンクとしたネットワークの一実施例を示す図であり、図１０の駐車場８１を出発地とし、図８の観光地６１を目的地とした場合のネットワークを示す図である。また、図７は経路検索時の制御部４（ＣＰＵ）の動作例を示すフローチャートである。
【００４７】
ステップＳ１：（出発地及び目的地の指示入力）
表示部１０の画面上に目的地及び出発地を表示した選択画面（図示せず)が表示されるので、ユーザが入力部１１の操作キー（ボタン)を操作して出発地及び目的地を選択（設定）すると、対応する入力信号（データ）が制御部４に送られる（図６の例では出発地として「駐車場８１」、目的地として「××寺６１」を選択する）。
【００４８】
ステップＳ２：（出発地道路決定の方法判定)
制御部４はユーザの設定した出発地が「現在位置」の場合（或いは、出発地を設定しなかった場合)には車の現在位置の決定を要するものとしてＳ３に遷移し、特定の「出発地」（例えば、駅、インター入り口、ドライブイン等データベースに登録されている場所）の場合にはＳ４に遷移する（図６の例では「駐車場６１」はデータベースに登録されている（図３）ので特定の「出発地」となり、Ｓ４に遷移する)。
【００４９】
ステップＳ３：（現在位置の決定)
制御部４は、絶対位置方位検索部１、相対方位検出部２、車速検出部３、ＦＭ多重受信及び処理部１３で得た位置情報や方位情報を基に自車の現在位置を（例えば、マップマッチング処理により）決定し、結果をメモリ６に保持（記憶)してＳ５に遷移する。
【００５０】
ステップＳ４：（登録された「出発地」の位置取得）
制御部４はデータベースからその特定の「出発地」の位置（座標）を現在位置として取得し、メモリ６に保持してＳ５に遷移する（図６の例では、制御部４はデータベースに登録されている「駐車場８１」の座標を現在位置の座標としてメモリ６に保持してＳ５に遷移する)。
【００５１】
ステップＳ５：（出発地道路および出発地点の決定)
制御部４は、上記ステップＳ３で取得した車の現在位置または上記ステップＳ５で取得した現在地（＝「出発地」）に最も近い道路をデータベースから探して出発地道路とし、車の進行方向上で現在地に最も近いノード（決定された出発地道路がダミーデータの場合は始端となるダミーノード）を出発地として決定し、メモリ６に保持する（図６の例では、現在位置（＝駐車場８１）の近傍に設定されたダミー道路８４が出発道路として決定され、ダミー道路８４の始端であるダミーノード８４’が出発地として決定される。すなわち、ダミー道路８４を設定したことにより経路探索対象道路８３のリンクを得ることができる）。
【００５２】
ステップＳ６：（目的地道路及び目的地点の決定)
制御部４は、上記ステップＳ１で設定された目的地を基に目的地に最も近い道路をデーターベースから探し出して目的地道路とし、目的地道路上で最も目的地に近いノード（目的地道路がダミー道路の場合にはダミー道路の始端となるダミーノード）を目的地点として決定し、メモリ６に保持する（図６の例では、目的地（××寺）６１の近傍に設定されたダミー道路６４が目的地道路として決定され、ダミー道路６４の始端であるダミーノード６４’が目的地点として決定される。すなわち、ダミー道路６４を設定したことにより目的地６１にアクセス可能な探索対象道路６３のうちで目的地６１に最も近い地点が探索される)。
【００５３】
ステップＳ７：（経路探索処理)
制御部４は上記ステップＳ６で得た出発地点及び目的地点をメモリ６から取り出して経路探索アルゴリズム（実施例では、前述したダイクストラ法による両方向からの経路探索処理）を実行し、最適経路を得る（図６の例で、ノード８４’→ノード１２２→ノード１５→ノード６４’を通る経路を最適経路とした場合、ダミー道路であるリンク「８９’」→「８４’」、リンク「６４’」→「６１’」のコストはダミー道路の重み係数を０としているため加算されない。すなわち、駐車場８１に最も近い道路８３上の地点８４’から最適経路を得て目的地（××寺）６１に実質的にアクセスできる道路６３上の地点６４’までの経路誘導がなされる）。
【００５４】
ステップＳ８：（ダミー道路の表示除外処理)
制御部４は上記ステップＳ７で得た最適経路にダミー道路が含まれているか否かを判定して含まれていない場合にはＳ９に遷移し、含まれている場合にはそのダミー道路を表示しないようにメモリ６に保持されているダミーノードのうち始端のダミーノード以外のノードの位置座標をメモリ６から消去し、ダミーノード間をつなぐ道路（＝ダミー道路）が作成されないようにする（図６の例で、ダミー道路８４，６４を表示しないように始端のダミーノードを除くダミーノード８９’、６１’等を消去する)。
【００５５】
ステップＳ９：（経路の表示）
制御部４は表示部１０の画面上に出発地及び又は目的地を含む地図と出発地および目的地を結ぶ最適経路およびノードを表示すると共に、車の現在位置と目的地点（案内ポイント）をユーザにわかりやすいように差別表示する。
【００５６】
以上本発明の一実施例について説明したが本発明は上記実施例に限定されるものではなく、種々の変形実施が可能であることはいうまでもない。
【００５７】
【発明の効果】
以上説明したように、本発明によればダミー道路を予め登録したファイルを含むデータベースを用いてナビゲーションを行うことができる。従って、ダミー道路を設定（登録）しておけば、従来技術のように目的地（又は出発地）に距離的には最も近いが環境条件により目的地には到達できない道路を探索対象として目的地にアクセス不能なポイントに案内するようなことが生じない。
【図面の簡単な説明】
【図１】本発明に基づく経路探索方法を適用可能なナビゲーション装置の一実施例を示すブロック図である。
【図２】道路情報ファイルの一実施例を示す図である。
【図３】経路ファイルにダミー道路を登録した例を示す図である。
【図４】ナビゲーションシステムの構成例を示すブロック図である。
【図５】道路探索時に用いられる各ノード間を結ぶネットワークの一例を示す図である。
【図６】本発明に基づくダミー道路をリンクとしたネットワークの一実施例を示す図である。
【図７】経路検索時の制御部の動作例を示すフローチャートである。
【図８】ダミー道路の一実施例を示す説明図である。
【図９】ダミー道路の一実施例を示す説明図である。
【図１０】ダミー道路の一実施例を示す説明図である。
【符号の説明】
１  絶対位置・方位検出部（探索開始地点決定手段）
２  相対方位検出部（探索開始地点決定手段）
３  車速検出部（探索開始地点決定手段）
４  制御部（設定手段、探索開始地点決定手段、経路探索手段、経路探索手段、経路表示手段）
１０  表示部（経路表示手段）
１１  入力装置（設定手段）
１００  ナビゲーション装置
２１０  道路情報ファイル（道路情報格納手段)
３１０  経路情報ファイル（道路情報格納手段)
４１１  設定手段
４１２  現在位置決定手段（探索開始地点決定手段）
４１３  出発地道路決定手段（探索開始地点決定手段）
４１４  目的地道路決定手段（探索開始地点決定手段）
４１５  経路探索手段
４１６  オフセット手段（経路表示手段)
４１７  経路表示手段
【図１】
0004355048.tif 000002
【図２】
0004355048.tif 000003
【図３】
0004355048.tif 000004
【図４】
0004355048.tif 000005
【図５】
0004355048.tif 000006
【図６】
0004355048.tif 000007
【図７】
0004355048.tif 000008
【図８】
0004355048.tif 000009
【図９】
0004355048.tif 000010
【図１０】
0004355048.tif 000011