(57)【特許請求の範囲】
【請求項１】
探索された経路に対し、回避部分を指示する迂回指示手段を有し、この迂回指示手段の指示に従って一つの連続するリンクを被迂回経路とするナビゲーション装置において、前記被迂回経路に続く連続する２つ以上のリンクを、それぞれ迂回後の復帰候補として、上記経路の出発リンクから各々の復帰候補に至る経路計算を復帰候補の数だけ繰り返して行って迂回経路候補を探索し、探索された迂回経路候補から最小コストの迂回経路候補を迂回経路として選択する迂回経路探索手段を有することを特徴とするナビゲーション装置。
【請求項２】
探索された経路に対し、回避部分を指示する迂回指示手段を有し、この迂回指示手段の指示に従って一つの連続するリンクを被迂回経路とするナビゲーション装置の制御方法において、
前記被迂回経路に続く連続する２つ以上のリンクを、それぞれ迂回後の復帰候補として、上記経路の出発リンクから各々の復帰候補に至る経路計算を復帰候補の数だけ繰り返して行って迂回経路候補を探索し、探索された迂回経路候補から最小コストの迂回経路候補を迂回経路として選択することを特徴とするナビゲーション装置の制御方法。
【請求項３】
探索された経路に対し、回避部分を指示する迂回指示手段を有し、この迂回指示手段の指示に従って一つの連続するリンクを被迂回経路とするナビゲーション装置により実行される経路探索用プログラムであって、
前記ナビゲーション装置を、前記被迂回経路に続く連続する２つ以上のリンクを、それぞれ迂回後の復帰候補として、上記経路の出発リンクから各々の復帰候補に至る経路計算を復帰候補の数だけ繰り返して行って迂回経路候補を探索し、探索された迂回経路候補から最小コストの迂回経路候補を迂回経路として選択する手段として機能させることを特徴とする経路探索用プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は車載ナビゲーション装置による経路誘導中に誘導経路上のある区間を迂回しようとする場合の迂回経路の探索技術に関する。
【０００２】
【従来の技術】
車載ナビゲーション装置（以下、単にナビゲーションシステムと記す）において、地図上の道路や地名、建物などを数値化して作られたデータベースをＣＤ−ＲＯＭ等の記憶媒体に保持させ、それらデジタル地図データベースに基づいて目的地を設定し、予め装置が保持している経路探索用データベースにしたがって誘導路を設定し、得られた誘導路と、ジャイロスコープや車速パルスを用いた自立航法及びＧＰＳやＦＭ多重を用いた電波航法から推定した自車位置とをマップマッチングしながら画面上に表示し、経路誘導する方法が一般的に知られている。
【０００３】
経路探索用データベースは、道路の交差点をノード、その交差点間をリンクとして、道路のネットワーク情報として構成されている。
【０００４】
また、ナビゲーション装置の経路探索機能には、例えば、有料道路優先、一般道路優先などの計算条件や、複数経路などの機能がある。さらに、道路幅、平均走行時間などをデータベースに記憶し、道路幅が広い道路優先、平均走行時間優先などの計算条件などもある。また、外部からの情報（ＶＩＣＳ）より規制情報、渋滞情報をオンラインでキャッチし、規制のある道路や渋滞している道路を避ける機能もある。
また、経路探索の条件、例えば、一般道路優先で、道路幅優先などの組み合わせ、更には、複数経路などの組み合わせで計算することで、ユーザがいろいろな経路を選定できる。
また、逆の場合、つまり、ユーザが通りたくない道路の選定は、例えば、現在走行中は国道１７号線であり、この道路は今の時間は混雑しそうなので迂回したいとユーザが判断した場合に、国道１７号線を避ける方法などがある。
【０００５】
【発明が解決しようとする課題】
しかし、上述したような迂回方法はユーザが国道１７号線といったように現在走行中（ナビゲーション装置による経路誘導中）の道路名を憶えていることが必須条件であるといった問題点があった（つまり、走行中の道路は国道のように道路表示標識がある道路ばかりではなく、道路名がわからない道路が多く存在するので、このような道路を走行中の場合には上記従来方式ではその道路を迂回することができない）。
【０００６】
また、知らない土地で、ＦＭ多重のユニット等を装着してなく渋滞に巻き込まれたようなときには、新たに経路探索の条件を変更して（設定しなおして）異なった経路を算出させるといった方法でしか現在走行中の経路を変更するしかないといった不都合があった。
【０００７】
上述のような問題点や不都合がある従来の経路迂回方法では、現在誘導中の経路がユーザにとって満足している経路なので渋滞部分を迂回して同じ経路（現在誘導中の経路であって、回避した渋滞部分の先の経路）に戻って走行したいといった場合に、渋滞を回避して元の経路に戻るように経路探索を行うよう設定を行うことはユーザにとって困難であり、且つ煩わしいといった問題点があった。
【０００８】
本発明は、上記従来技術の問題点及び不都合に鑑みてなされたものであり、ナビゲーション装置を搭載した車で、現在誘導中の経路の一部区間の走行を回避したい場合に、その区間を迂回してもとの経路に戻るような経路探索を行い得るナビゲーション装置及び迂回経路探索用プログラムの記録媒体の提供を目的とする。
【０００９】
【課題を解決するための手段】
上記課題を解決するために、第１の発明のナビゲーション装置は、車の現在位置から目的地までの誘導経路を地図上に表示し、走行補助をなすナビゲーション装置において、誘導経路の設定がなされているか否かを判定する経路設定判定手段と、誘導経路の設定がなされているとき、現在走行中の第１のリンク、及び第１のリンクには隣接しない前方で、且つ誘導経路中の第２のリンク、並びに第２のリンク以降の経路を保存する経路保存手段と、第１のリンクから第２のリンクに至る迂回経路を探索する迂回経路探索手段と、この迂回経路探索手段によって探索された迂回経路と経路保存手段に保存されている経路とを結合して新たな誘導経路を設定する経路設定制御手段と、を備えたことを特徴とする。
【００１０】
また、第２の発明は上記第１の発明のナビゲーション装置において、第１のリンクには隣接しない前方で、且つ誘導経路中の連続した複数のリンクを第２のリンク候補として設定する第２リンク候補設定手段を備え、迂回経路探索手段は、この第２リンク候補設定手段により設定された第２のリンク候補毎に第１のリンクからの迂回経路を探索し、探索された迂回経路中最適な経路を迂回経路とする手段を含む、ことを特徴とする。
【００１１】
また、第３の発明は上記第１又は第２の発明のナビゲーション装置において、迂回経路探索手段は、誘導経路上の第１のリンクから第２のリンクに至る経路の各リンクのコストを増加して経路計算する手段を含むことを特徴とする。
また、第４の発明は上記第１又は第２の発明のナビゲーション装置において、第２のリンクは誘導経路上における車の現在位置、或いは第１のリンクから所定距離離れたリンクであることを特徴とする。
【００１２】
【発明の実施の形態】
[本発明の概要]
ナビゲーション装置で経路誘導中に、誘導中の経路を通りたくないような状況、例えば、現在走行中の道路から少し先の道路まではユーザがよく走行する道路であり、現在の時間は混雑しているとユーザが判断した場合に、現在走行中の経路から少し外れて混雑を回避し、少し先でまた同じ経路に戻って（迂回して）走行したいといったような場合に、本発明のナビゲーション装置は下記（１）、（２）の方法で迂回経路を得て同じ経路（現在誘導中の経路であって、回避した渋滞部分の先の経路）に合流するように経路探索を行う。
【００１３】
（１）  出発リンクＬ１（経路はリンクの配列であらわされる、出発リンクＬ１は現在走行中のリンクまたは現在位置）を走行中の車Ｐを図１に示すようなノード１６〜２４を通る経路Ｒ（Ｒ＝Ｌ１＋Ｒ１＋Ｒ２）を誘導中の場合、走行中のリンクＬ１の次のリンクＬａから迂回したい距離Ｘだけ先のリンクＬ２をメモリに保存（リンクＬ１＋経路Ｒ１）し、更に、その先のリンクＬｂ（目的リンク）から目的地までのリンク（経路Ｒ２）も同じメモリに保存する。
【００１４】
迂回経路は、目的リンクＬｂを目的地として迂回なためのリンク（Ｌａ）から経路探索を行うことにより求める。
このとき、経路Ｒ１の通常のコスト計算で得られるコストに重み係数β（＞１）を乗じて経路Ｒ１を通りにくくしてから経路探索を行う。そして、この経路探索で得られた最も低コストの結果（ノード１６からノード４５、４６、５９、７２を通る迂回経路Ｒ１’）とリンクＬ２の次のリンクＬｂ（つまり、目的リンク）を結ぶことで迂回計算後の誘導経路Ｒ’（＝Ｌ１＋Ｒ１’＋Ｒ２）を得ることができる。なお、経路Ｒ１のコストに重み係数βを乗ずる代わりに重みβ’を加えるようにしてもよい（つまり、迂回経路探索時に迂回したい経路Ｒ１を通りにくくするように経路Ｒ１を増加させるようにすればよい）。
【００１５】
（２）  上記（１）の方法の応用であり、上記（１）の方法では図１の例に示すようにノード２１、２２の間にノード２１と２２を結ぶリンクＬ１以外の周り道ｒがあるような場合、最も低コストな経路として得られた経路Ｒ１’のうちノード７２とノード２１を結ぶ区間が回り道ｒの長さ｜ｒ｜からリンクＬ２の長さ｜Ｌ２｜を差し引いた分だけ余計となる場合が生じ得る。つまり、目的リンクを一つ設定した場合、経路計算で得る迂回経路が必ずしも最適経路とは限らない場合がある（経路Ｒ１への重みβ（β’）が大きければ大きいほどこのような現象が生ずる可能性が高い）。
【００１６】
そこで、図２に示すように迂回経路探索の目的リンクを経路Ｒ２（図１）の先頭リンクＬｂから数個先のリンク（或いは先頭リンクＬ２からある距離だけ先のリンク）をＬｃとし、リンクＬｂ〜リンクＬｃ間（リンクＬｂ及びリンクＬｃも含む）の各リンクを目的リンク候補としてリンクＬａから目的リンク候補までの各経路[Ｒ１]に通常の計算で得られたコストに重み係数β（＞１）を乗じて経路[Ｒ１]を通りにくくしてから各経路[Ｒ１]毎に経路探索を行う。そして、この経路探索で得られた迂回経路の中で最も低コストの結果（ノード１６からノード４５、４６、５９、７２を通る経路Ｒ１”）と経路Ｒ３”、Ｒ２”を結ぶことで最適な迂回経路と結合した誘導経路Ｒ”（＝Ｌ１＋Ｒ１”＋Ｒ３”＋Ｒ２”）を得ることができる。
【００１７】
［ナビゲーション装置の構成例］
図３は、本発明の迂回経路探索方法を適用可能なナビゲーション装置の一実施例を示すブロック図であり、ナビゲーション装置１００は、絶対位置・方位検出部１、相対方位検出部２、車速検出部３、制御部４、メモリ５〜８、ユーザインターフェイス部９、表示部１０、入力部１１、ＣＤ−ＲＯＭ制御部１２及びＦＭ多重受信及び処理部１３を備えている。
【００１８】
絶対位置・方位検出部１はアンテナ１ａを有し、ＧＰＳ（Global Positioning System）衛星からの電波をアンテナ１ａで受信して絶対位置（絶対座標)及び方位を検出して制御部４に送出する。
【００１９】
相対方位検出部２はジャイロ等の方位検出装置を備え、検出した方位を制御部４に送出する。また、車速検出部３は車の走行に伴って得る回転パルスから車側を得て制御部４に送出する。これらの検出値（方位及び速度)はＧＰＳ衛星から得た絶対位置及び方向を補正し、自車の現在位置を決定するために制御部４で用いられる。
【００２０】
制御部４はＣＰＵとタイマやＣＰＵ周辺回路を備えたマイクロプロセッサ構成を有しており、ＣＰＵは上述の各回路等にバスラインを介して接続し、メモリ（プログラム格納用ＲＯＭ）５に格納されているナビゲーション制御プログラムによりナビゲーション装置１００全体の制御を行なうと共に、入力部１０からの入力信号に対応してナビゲーション装置１００の各機能の実行制御等（例えば、マップマッチングの実行制御、地図及び経路等の表示制御、本発明に基づく迂回経路探索の実行制御等）を行なう。
【００２１】
メモリ５はプログラム格納用ＲＯＭであり、プログラム格納用ＲＯＭ５はＰＲＯＭやＦＲＯＭ（フラッシュＲＯＭ）等が用いられ、制御プログラムや、マップマッチングプログラム、地図及び経路等の表示プログラム、経路探索プログラム（本発明の迂回経路探索機能（プログラム）を含む）等を格納する。また、プログラム格納用ＲＯＭに表示部１０に表示するアイコンやメニュー及び図形パターン及び定数を格納することもできる。
【００２２】
メモリ６はＤＲＡＭ（Dynamic RAM）からなり、制御部４の制御下でＣＤ−ＲＯＭ制御部１２を介してＣＤ−ＲＯＭに格納された地図のうちの所要の地図及びその広域隣接エリアの地図を取り込む。また、経路探索結果や中間結果を一次的に記憶する領域が確保されている。
【００２３】
また、メモリ７はＳＲＡＭ（Static RAM）のような高速メモリからなり、ナビゲーション装置１００の起動時に制御部４のプログラム格納用ＲＯＭから制御プログラムを取り込むと共に、制御プログラムの制御シーケンスに従ってマップマッチングプログラム、地図及び経路等の表示プログラム、経路探索プログラム等を適時取り込み、マップマッチング処理や経路探索処理（本発明の迂回経路探索機能を含む）等のナビゲーション処理の実行に用いられる。
【００２４】
また、メモリ８は表示メモリであってＶＲＡＭからなり、制御部４の制御下でＤＲＡＭ６から取り出された１画面分の地図や、経路探索により探索された誘導路や迂回経路、名称やメニュー等のビットマップイメージを保持する。
【００２５】
ユーザインターフェイス部９は表示部１０や入力部１１と制御部４を結ぶインターフェイスであり、表示部１０は表示メモリ８に保持された地図や誘導路や迂回経路、名称やメニュー等を表示する。
【００２６】
入力部１１はユーザによる出発地及び目的地或いは迂回距離の設定（又は選択）入力、地図の選定及び迂回モード指定等や、その他必要な情報入力手段であり、入力用のキーやボタン或いはカーソル移動やポイント（指示)用のキーを備えている。
【００２７】
ＣＤ−ＲＯＭ制御部１２はナビゲーション用の情報を効率的に取り出すように構築されたデータベースを格納したＣＤ−ＲＯＭから必要な情報を読み出す。また、実施例ではナビゲーション用の情報を効率的に取り出すように構築されたデータベースをＣＤ−ＲＯＭに格納したが、これに限定されず、大容量で且つコンパクトであって、ユーザがナビゲーション装置本体に着脱容易な記録媒体であればよい。
【００２８】
ＦＭ多重受信及び処理部１３はアンテナ１３ａを有し、ＦＭ多重波をアンテナ１３ａで受信して高速道路等での自車位置情報等を検出して制御部４に送出する。検出値はＧＰＳから得た絶対位置及び方向を補正して自車位置を決定するために制御部４で用いられる。
【００２９】
[データベース]
経路探索用データベースは、図４に示すようにノード（交差点）及びリンク（交差点間の道路）からなっている。また、ノードにはＩＤとその座標及び接続するリンクＩＤ等の情報を持ち、リンクはユニークなＩＤ、属性、距離（リンクの長さ）、道幅などの情報を持っている。経路探索プログラムはそれらの情報を元にコスト（その道路の通りにくさ（コストが低いほど通りやすい））を計算し、出発地から目的地までの評価コストが最も低いリンクの列を経路探索の解とする。また、経路探索のアルゴリズムにはダイクストラ法やそれを応用した方法が用いられている。
【００３０】
[迂回経路探索動作（１）]
図５は現在誘導中の経路及びその迂回路の説明図であり、図６は本発明の迂回経路探索方法を適用したナビゲーション装置１００の迂回経路探索時の動作例を示す図である。
図５で、現在誘導中の経路上で車Ｐが走行しているリンクをｎ番目のリンク（リンクＬ１）、迂回したい経路をＲ１、経路Ｒ１を迂回後戻りたい元の続きの経路をＲ２、経路Ｒ１の最終リンクをｎ＋ｍ番目のリンク（リンクＬ２）、リンクＬ２の次のリンク（ｎ＋ｍ＋１番目のリンク）を目的リンクＬｂとすると誘導中の経路Ｒ＝Ｌ１＋Ｒ１＋Ｒ２（Ｒ２は目的リンクＬｂから目的地までを結ぶリンクの和））となる。
また、迂回経路Ｒ１’は経路Ｒ１に重み付けを行った後、経路探索を行って得たｎ＋１番目のリンク（リンクＬａ）とｎ＋ｍ＋１番目のリンク（リンクＬｂ）を結ぶ経路であり、迂回計算後の経路Ｒ”＝Ｌ１＋Ｒ１’＋Ｒ２（Ｒ２はリンクＬｂから目的とを結ぶリンクの和）となる。
【００３１】
ステップＳ０：（地図の表示）
目的地が設定されている場合、ナビゲーション装置１００が起動中は絶対位置・方位検出部１はＧＰＳ衛星からの電波を受信して車Ｐの絶対位置及び方位を取得し制御部４に送出するので、制御部４は（車Ｐが走行中は相対方位検出部２によって得られた相対方位で絶対位置・方位検出部１から受け取った方位を修正してから）、ＣＤ−ＲＯＭから取り込まれたメモリ６（ＤＲＡＭ）上の地図データのうち車Ｐの位置を含む地図を表示部１０に表示する。
【００３２】
ステップＳ１：（経路誘導中か否かの判定）
制御部４はナビゲーション装置１００が車Ｐの経路誘導中か否かを判定し、誘導中の場合にはＳ２に遷移し、そうでない場合には迂回処理を行わない（つまり、迂回処理プログラム終了に遷移する）。
【００３３】
ステップＳ２：（走行中のリンクの格納）
制御部２は現在走行中のリンクＬ１が誘導経路Ｒの何番目のリンクかを、上記ステップＳ０で取得した車Ｐの現在位置から判定し、そのリンクを出発リンクとしてその番号（この例ではリンク番号ｎ）をメモリ６（ＤＲＡＭ）に一時記憶する。なお、走行中のリンクは上記ステップＳ０で取得された車Ｐの現在位置（座標）を基に算出することができる（つまり、経路Ｒ上の２つのノードＡ、Ｂ（ノードの座標）をつなぐ直線上の座標と取得した車Ｐの座標が一致（所定閾値の範囲内で一致）すればノードＡ、Ｂ間のリンク上に車Ｐがあることとなるのでデータベースからそのリンク番号（ＩＤ）を得ることができる）。
【００３４】
ステップＳ３：（迂回入力指示の有無判定）
車Ｐが誘導中の場合には表示部１０の画面の一部に「迂回」を意味する表示（「迂回」ボタン）がなされ、「迂回」ボタンをポイント（指定）すると迂回距離の選択を行うように構成されているので、ユーザは入力部１１のポインテングデバイスを操作して表示された距離の中から所望の選択をすることができる。そこで、制御部４は入力部１１からの状態信号を調べ、「迂回」ボタンがポイントされた場合には表示部１０に迂回距離選択表示用データを送って表示させ、ユーザによって選択された距離αをメモリ６に保持（上書き記憶、保存）する（例えば、１０Ｋｍ先まで渋滞が見込まれる場合にはユーザは迂回距離として１０Ｋｍを選択するので、制御部４はその距離「１０Ｋｍ」をメモリ６に保持する）。なお、迂回距離の入力方法は上記の例に限定されない（例えば、迂回したい距離を入力部１１から直接入力するように構成してもよい）。
【００３５】
ステップＳ４：（迂回したい経路の保持）
制御部４は走行中のリンクＬ１の次のリンクＬａから迂回距離αを超えるリンクＬ２までのリンクからなる経路（迂回したい経路Ｒ１を構成するリンク番号（つまり、図４でｎ＋１番目からｎ＋ｍ番目のリンク））をメモリ６の回避リンク記憶エリアに保持（上書き記憶：保存）する。迂回したいリンクの設定は例えばリンクＬ１から順に目的値に向かって各リンクの長さを加算し、加算値＞αとなった最初のリンクをリンクＬ２とすることにより求めることができる。
【００３６】
ステップＳ５：（目的リンク以降の経路の保持）
また、制御部４は誘導中の経路Ｒ上で迂回したい経路Ｒ１に続く目的リンクＬｂから目的地までの経路（つまり、図５の経路Ｒ２）を構成するリンクをメモリ６の結合経路記憶エリアに保持する。
【００３７】
ステップＳ６：（迂回したい経路の重み付け）
次に、制御部４は回避リンク記憶エリアに記憶した各リンク（つまり、図４５経路Ｒ１）のコストを通常の経路計算でのコスト算出法により算出し、それに重み付けを行なう。コストの重み付けは実施例ではコストＣに重み係数β（＞１）を乗じることにより行っているが、これに限定されない（つまり、経路Ｒ１を通りにくくするように経路Ｒ１の評価コストを増加させる方法であればよい）。
【００３８】
ステップＳ７：（経路探索処理）
制御部４は通常の経路探索処理と同様の計算方法により出発リンクＬ１（ｎ番目のリンク）から目的リンクＬｂ（ｎ＋ｍ＋１番目のリンク）に至る経路計算を行い、得られた経路のうち最小コストの経路を迂回経路とする。これにより迂回したい経路Ｒ１とは異なる迂回経路Ｒ１’を得ることができる。
【００３９】
ステップＳ８：（最適経路（迂回経路）と結合経路との結合）
最後に、制御部４は上記ステップＳ７で得た迂回経路Ｒ１’と結合経路記憶エリアに記憶した結合経路Ｒ２（つまり、出発リンクＬ１からみて距離α以降の経路Ｒ２を結合して新たな誘導経路Ｒ’（＝Ｒ１’＋Ｒ２））を得る。
【００４０】
なお、上記フローチャートでＳ１の「経路誘導中か否かの判定」動作をＳ０の「地図表示」動作の前段で行うようにしてもよい。
【００４１】
[迂回経路探索動作（２）]
図７は現在誘導中の経路及びその迂回路の説明図であり、図８は本発明の他の迂回経路探索方法を適用したナビゲーション装置１００の迂回経路探索時の動作例を示す図である。なお、図８で、Ｓ１〜Ｓ４の動作はＳ６の動作と同様である。
図７で、現在誘導中の経路上で車Ｐが走行しているリンクをｎ番目のリンク（リンクＬ１）、迂回したい経路（ｎ番目のリンクからｍ＋ｎ番目のリンクまで）をＲ１、目的リンク（迂回経路計算で決定される最適経路の終点（ｎ＋ｍ＋１番目のリンクＬｂからｎ＋ｍ＋ｋ番目のリンクＬｃの間（リンクＬｂ、Ｌｃも含む）の各目的リンク候補の中から決定される１つのリンク））までの経路をＲ３”、目的リンクの次のリンクから目的地までの経路（つまり、迂回後戻りたい元の続きの経路）をＲ２”とすると誘導中の経路Ｒ＝Ｌ１＋Ｒ１＋Ｒ３”＋Ｒ２”（Ｒ２”は目的リンクの次のリンクから目的地までを結ぶリンクの和））となる。
また、迂回経路Ｒ１’は経路Ｒ１に重み付けを行った後、経路探索を行って得たｎ＋１番目のリンク（リンクＬａ）と目的リンクを結ぶ経路であり、迂回計算後の経路Ｒ”＝Ｌ１＋Ｒ１’＋Ｒ３”＋Ｒ２”（Ｒ２は目的リンクから目的地に至る各リンクの和）となる。
【００４２】
図６のフローチャートのＳ１（地図の表示）、Ｓ２（走行中のリンクＬ１の格納）、Ｓ３（迂回入力指示の有無判定）、Ｓ４（迂回したい経路Ｒ１の設定及び保持）と同様の動作の後、
ステップＳ５’：（目的リンク候補の設定・保持）
図８で、制御部４は、迂回経路探索の目的候補リンクとしてリンクＬ２の直後のリンクＬｂではなく、リンクＬｂからリンクＬｃまでの数リンク（又はリンクリンクＬｃから所定距離内の各リンク）を設定する。
【００４３】
ステップＳ６’：（目的リンク候補を含む経路の保持）
また、制御部４は誘導中の経路Ｒ上の迂回したい経路Ｒ１に続くリンクＬｂからリンクＬｃまでのリンク（リンクＬｂ、Ｌｃも含む）を目的リンク候補とし、リンクＬａから各目的リンク候補を結ぶ経路（つまり、図７の経路Ｒ３”）を構成するリンクをそれぞれメモリ６の第１の結合経路記憶エリア（複数）に保持する。
【００４４】
ステップＳ７’：（目的リンク以降の経路の保持）
また、制御部４は誘導中の経路Ｒ上の各目的リンクから目的地までの経路（つまり、図７の経路Ｒ２”）を構成するリンクをそれぞれメモリ６の第２の結合経路記憶エリア（複数）に保持する。
【００４５】
ステップＳ８’：（迂回したい経路の重み付け）
次に、制御部４はステップＳ４で回避リンク記憶エリアに記憶した経路（つまり、図７の経路[Ｒ１]）のコストを通常の経路計算でのコスト算出法により算出し、それに重み付けを行なう。コストの重み付けは実施例ではコストＣに重み係数β（＞１）を乗じることにより行っているが、これに限定されない（つまり、経路Ｒ１を通りにくくするように経路Ｒ１の評価コストを増加させる方法であればよい）。
【００４６】
ステップＳ９’：（経路探索処理）
制御部４は通常の経路計算方法により出発リンクＬ１（ｎ番目のリンク）から目的リンク候補に至る経路計算を目的リンク候補の数だけ繰り返して行い、各経路をメモリ６に保持して、経路計算終了後、得られた経路のコストを比較し最小コストの経路を選択して、その経路を経路Ｒ１の迂回経路Ｒ１”とする。これにより迂回したい経路Ｒ１とは異なる迂回経路Ｒ１”を得ることができる。
【００４７】
ステップＳ１０：（最適経路（迂回経路）と第１の結合経路との結合）
制御部４は上記ステップＳ９で得た迂回経路Ｒ１”と第１の結合経路記憶エリアに記憶した結合経路Ｒ３”を加算し、出発リンクＬ１から目的リンクまでの経路を得る。
【００４８】
ステップＳ１１’：（第２の結合経路との結合）
最後に、制御部４は上記ステップＳ１０で得た経路Ｒ１”と結合経路Ｒ３”の和に第２の結合経路記憶エリアに記憶した結合経路Ｒ２”を加算し、出発リンクＬ１から目的リンクまでの経路を得る。
【００４９】
以上、本発明の一実施例について説明したが本発明は上記実施例に限定されるものではなく、種々の変形実施が可能であることはいうまでもない。
【００５０】
【発明の効果】
上記説明したように、第１〜第４の発明のナビゲーション装置及び迂回経路探索方法によれば、ナビゲーション装置の案内による走行予定の経路（誘導経路）についてその道路の名称を知っていなくても現在走行中の経路からユーザの所望する距離を迂回した迂回経路を探索して提供（画面上に誘導路として表示）することができる。また、この際、迂回部分（探索された迂回経路）と元の経路の結合設定を自動的に行うので、ユーザは迂回距離を指定（選択）するだけでよく操作が極めて簡単になる。
【００５１】
また、第２の発明のナビゲーション装置によれば、第２のリンク（迂回したい経路の終点）を幾つか設定して経路計算を行い最適な迂回経路とすることができるので、第２のリンクを一つとした場合より最適な迂回経路及び誘導経路を得ることができる。
【図面の簡単な説明】
【図１】迂回経路探索方法の説明図である。
【図２】他の迂回経路探索方法の説明図である。
【図３】本発明の迂回経路探索方法を適用可能なナビゲーション装置の一実施例を示すブロック図である。
【図４】経路探索用データベースの説明図である。
【図５】現在誘導中の経路及びその迂回路等の説明図である。
【図６】本発明の迂回経路探索方法を適用したナビゲーション装置の迂回経路探索時の動作例を示すフローチャートである。
【図７】現在誘導中の経路及びその迂回路等の説明図である。
【図８】本発明の他の迂回経路探索方法を適用したナビゲーション装置の迂回経路探索時の動作例を示す図である。
【符号の説明】
４  制御部（経路設定判定手段、迂回経路探索手段、経路設定制御手段、第２リンク候補設定手段）
６  メモリ（経路保存手段）
１００  ナビゲーション装置
Ｐ  車の現在位置
Ｌ１  第１のリンク
Ｌａ  第２のリンク
Ｌｂ  目的リンク
【図１】
0004524017.tif 000002
【図２】
0004524017.tif 000003
【図３】
0004524017.tif 000004
【図４】
0004524017.tif 000005
【図５】
0004524017.tif 000006
【図６】
0004524017.tif 000007
【図７】
0004524017.tif 000008
【図８】
0004524017.tif 000009