(57)【要約】【課題】特定地域を特定の時間帯のみ回避して目的地に至る経路を探索する。【解決手段】走行を回避する回避領域を設定するための回避領域設定手段と、該回避領域設定手段にて設定された回避領域の回避時間帯を設定するための回避時間帯設定手段とを設け、経路探索手段は回避領域設定手段にて設定された回避領域を回避時間帯設定手段にて設定された回避時間帯に通過しないように経路探索を行なう。【選択図】図１１
2006226997.tif 000002
【特許請求の範囲】
【請求項１】
指定された目的地までの走行経路を探索する経路探索手段を備えたナビゲーション装置であって、
走行を回避する回避領域を設定するための回避領域設定手段と、該回避領域設定手段にて設定された回避領域の回避時間帯を設定するための回避時間帯設定手段とを備え、前記経路探索手段は前記回避領域設定手段にて設定された回避領域を前記回避時間帯設定手段にて設定された回避時間帯に通過しないように経路探索を行なうことを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置において、前記回避領域設定手段は複数の回避領域が設定可能であり、前記回避時間帯設定手段は設定された回避領域毎に回避時間帯が設定可能であり、前記経路探索手段は前記回避領域設定手段にて設定された何れの回避領域をも前記回避時間帯設定手段にて設定された対応する回避時間帯に通過しないように経路探索を行なうことを特徴とするナビゲーション装置。
【請求項３】
請求項１に記載のナビゲーション装置において、前記経路探索手段は、最初は回避領域が設定されていないものとして経路探索を行ない、次に該経路探索により探索した走行経路が設定された回避領域をその回避時間帯に通過するか否かを判定し、通過しないと判定した場合には該走行経路を探索した走行経路として確定し、通過すると判定した場合には該回避領域を通行禁止扱いにして再度の経路探索を行なうことを特徴とするナビゲーション装置。
【請求項４】
請求項３に記載のナビゲーション装置において、前記回避領域が複数設定され且つ各回避領域毎の回避時間帯が設定された場合には、前記経路探索手段は、設定された何れの回避領域をもその回避時間帯に通過しない走行経路を探索するまで前記再度の経路探索を繰り返し実行することを特徴とするナビゲーション装置。
【請求項５】
請求項１ないし４の何れかに記載のナビゲーション装置において、前記回避時間帯設定手段は、日付、曜日および時間からなる要素のうち少なくとも１つ以上の要素を組み合わせて前記回避時間帯を設定可能に構成されていることを特徴とするナビゲーション装置。
【請求項６】
目的地までの車両の走行経路を探索する経路探索方法であって、経路探索前に走行を回避する回避領域の設定が行なわれる第１のステップと、該回避領域の回避時間帯の設定を受ける第２のステップとを含み、第１のステップにて設定された回避領域を第２のステップにて設定された回避時間帯に通過しないように経路探索を行なうことを特徴とする経路探索方法。
【請求項７】
請求項６に記載の経路探索方法において、前記第１のステップにおいては複数の回避領域が設定可能であり、前記第２のステップにおいては第１のステップにおいて設定された回避領域毎にその回避時間帯が設定可能であり、第１のステップにて設定された何れの回避領域をも第２のステップにて設定された対応する回避時間帯に通過しないように経路探索を行なうことを特徴とする経路探索方法。
【請求項８】
請求項６に記載の経路探索方法において、回避領域とその回避時間帯が設定された場合には、最初は回避領域が設定されていないものとして経路探索を行ない、次に該経路探索により探索した走行経路が設定された回避領域をその回避時間帯に通過するか否かを判定し、通過しないと判定した場合には該走行経路を探索した走行経路として確定し、通過すると判定した場合には該回避領域を通行禁止扱いにして再度の経路探索を行なうことを特徴とする経路探索方法。
【請求項９】
請求項８に記載の経路探索方法において、前記回避領域が複数設定され且つ各回避領域毎の回避時間帯が設定された場合には、前記経路探索手段は、設定された何れの回避領域をもその回避時間帯に通過しない走行経路を探索するまで前記再度の経路探索を繰り返し実行することを特徴とする経路探索方法。
【請求項１０】
請求項６ないし９の何れかに記載の経路探索方法において、前記第２のステップにおいては日付、曜日および時間からなる要素のうち少なくとも１つ以上の要素を組み合わせて前記回避時間帯を設定可能であることを特徴とする経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特には特定地域を特定時間帯のみ回避した経路設定を行なうナビゲーション装置及びその経路探索方法に関する。
【背景技術】
【０００２】
近年、車両に搭載されＧＰＳ（Global Positioning System、全地球的測位システム）などにより検出した車両位置を地図画面上に表示し、目的地までの経路探索をして誘導するナビゲーション装置が広く普及してきている。このナビゲーション装置における経路探索では、地図データベースに納められた道路地図を使用して出発地から目的地に至る走行経路がダイクストラ法あるいはそれに準じた手法を用いて探索される。
【０００３】
ダイクストラ法では各道路の交差点、曲がり点等をノード、それらノード間の道路をリンクと定義しそのリンクを接続して構成した道路地図が用いられる。そして、リンク相互間の接続情報と、リンク毎の道路情報、通行規制等のリンク情報とを用いて経路コスト（経路に対する評価値）の算出を行ない、算出した経路コストが最小となるリンクの接続により目的地までの経路が設定される。
【０００４】
経路コストが最小となるリンクの接続により経路が設定されるので、ユーザが回避したい交差点、道路、領域については該当するリンクの経路コストを高く設定しておく。そうすることにより回避領域を迂回した経路を探索させることができる（例えば、特許文献１参照）。
【０００５】
しかし、回避させ方として恒常的な回避でなく、ある時間帯に限って回避したい場合がある。例えば、特定の交差点や踏切を朝のラッシュ時間帯のみ回避したい場合、特定施設の周辺を混雑する特定時間帯のみ回避したい場合である。こうした特定時間帯のみ回避したい回避領域が存在する場合の経路探索は、上記のような経路コストを恒常的に高く設定する方法では行なうことができない。
【特許文献１】特開平１１−８３５１９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明はこのような従来技術の問題点を解決するためになされたもので、その課題は、特定地域を特定の時間帯のみ回避して目的地に至る経路を探索することのできる経路探索方法、及びその経路探索方法を使用したナビゲーション装置を提供することにある。
【課題を解決するための手段】
【０００７】
前記課題を解決するための請求項１に記載の発明は、指定された目的地までの走行経路を探索する経路探索手段を備えたナビゲーション装置であって、走行を回避する回避領域を設定するための回避領域設定手段と、該回避領域設定手段にて設定された回避領域の回避時間帯を設定するための回避時間帯設定手段とを備え、前記経路探索手段は前記回避領域設定手段にて設定された回避領域を前記回避時間帯設定手段にて設定された回避時間帯に通過しないように経路探索を行なうことを特徴とするナビゲーション装置である。
【０００８】
このような構成のナビゲーション装置によれば、ラッシュアワーなどの特定時間帯のみ混雑する交差点、道路等を随時、回避領域として設定することができ、その回避領域を回避した走行経路を求めることができる。
【０００９】
また請求項２に記載の発明は、請求項１に記載のナビゲーション装置において、前記回避領域設定手段は複数の回避領域が設定可能であり、前記回避時間帯設定手段は設定された回避領域毎に回避時間帯が設定可能であり、前記経路探索手段は前記回避領域設定手段にて設定された何れの回避領域をも前記回避時間帯設定手段にて設定された対応する回避時間帯に通過しないように経路探索を行なうことを特徴とする。
このように複数の回避領域とそれぞれの回避時間帯を随時、設定できれば混雑する地域を混雑する時間帯のみ回避した走行経路を求めることができる。
【００１０】
また請求項３に記載の発明は、請求項１に記載のナビゲーション装置において、前記経路探索手段は、最初は回避領域が設定されていないものとして経路探索を行ない、次に該経路探索により探索した走行経路が設定された回避領域をその回避時間帯に通過するか否かを判定し、通過しないと判定した場合には該走行経路を探索した走行経路として確定し、通過すると判定した場合には該回避領域を通行禁止扱いにして再度の経路探索を行なうことを特徴とする。
このような経路探索を行なうナビゲーション装置によれば、比較的少ない計算量で回避領域をその回避時間帯に回避した走行経路を求めることができる。
【００１１】
また請求項４に記載の発明は、請求項３に記載のナビゲーション装置において、前記回避領域が複数設定され且つ各回避領域毎の回避時間帯が設定された場合には、前記経路探索手段は、設定された何れの回避領域をもその回避時間帯に通過しない走行経路を探索するまで前記再度の経路探索を繰り返し実行することを特徴とする。
このような経路探索を行なうナビゲーション装置によれば、複数存在する全ての回避領域をそれぞれ回避時間帯に回避した走行経路を比較的少ない計算量で求めることができる。
【００１２】
また請求項５に記載の発明は、回避時間帯設定手段により、日付、曜日および時間からなる要素のうち少なくとも１つ以上の要素を組み合わせて回避時間帯を設定可能である。これにより、平日、土日、特定の日（一例として祝日）などを指定した詳細な時間帯設定が可能となり、ユーザの生活状況等に合致した走行経路を求めることができる。
【００１３】
また請求項６に記載の発明は、目的地までの車両の走行経路を探索する経路探索方法であって、経路探索前に走行を回避する回避領域の設定が行なわれる第１のステップと、該回避領域の回避時間帯の設定を受ける第２のステップとを含み、第１のステップにて設定された回避領域を第２のステップにて設定された回避時間帯に通過しないように経路探索を行なうことを特徴とする経路探索方法である。
このような経路探索方法は、請求項１に記載の発明と同様の効果を奏する。
【００１４】
また請求項７に記載の発明は、請求項６に記載の経路探索方法において、前記第１のステップにおいては複数の回避領域が設定可能であり、前記第２のステップにおいては第１のステップにおいて設定された回避領域毎にその回避時間帯が設定可能であり、第１のステップにて設定された何れの回避領域をも第２のステップにて設定された対応する回避時間帯に通過しないように経路探索を行なうことを特徴とする。
このような経路探索方法は、請求項２に記載の発明と同様の効果を奏する。
【００１５】
また請求項８に記載の発明は、請求項６に記載の経路探索方法において、回避領域とその回避時間帯が設定された場合には、最初は回避領域が設定されていないものとして経路探索を行ない、次に該経路探索により探索した走行経路が設定された回避領域をその回避時間帯に通過するか否かを判定し、通過しないと判定した場合には該走行経路を探索した走行経路として確定し、通過すると判定した場合には該回避領域を通行禁止扱いにして再度の経路探索を行なうことを特徴とする特徴とする。
このような経路探索方法は、請求項３に記載の発明と同様の効果を奏する。
【００１６】
また請求項９に記載の発明は、請求項８に記載の経路探索方法において、前記回避領域が複数設定され且つ各回避領域毎の回避時間帯が設定された場合には、前記経路探索手段は、設定された何れの回避領域をもその回避時間帯に通過しない走行経路を探索するまで前記再度の経路探索を繰り返し実行することを特徴とする特徴とする。
このような経路探索方法は、請求項４に記載の発明と同様の効果を奏する。
【００１７】
また請求項１０に記載の発明は、第２のステップにおいて日付、曜日および時間からなる要素のうち少なくとも１つ以上の要素を組み合わせて回避時間帯を設定可能である。
このような経路探索方法は、請求項５に記載の発明と同様の効果を奏する。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照して本発明の一実施形態を説明する。図１は、その実施形態に係るナビゲーション装置の構成をブロック図で表わしたものである。ナビゲーション装置１は、制御回路２、ＧＰＳ受信機３、距離センサ４、車体方位センサ５、操作スイッチ群６、表示装置８、音声出力装置９、磁気ディスク装置（以下、ＨＤＤという。）１０を備えて構成される。
【００１９】
制御回路２は、ナビゲーション装置１の動作全般を制御する機能を有するものでマイクロコンピュータを主体に構成されており、内部にはＣＰＵ１１、ＲＡＭ１２、ＲＯＭ１３、それらを接続する図示しないバスライン、Ｉ／Ｏインターフェイス、電源装置などを備える。
【００２０】
ＧＰＳ受信機３は複数のＧＰＳ用人工衛星からの電波を受信して車両の現在位置を算出し制御回路２に伝えるものである。距離センサ４は走行距離を計測するセンサで、例えばフロントホイ−ルの回転数を計数して走行距離を計測する。車体方位センサ５は、ジャイロスコープ、地磁気センサ等で構成され車体の方位を検出するものである。距離センサ４、車体方位センサ５の計測値は、ＧＰＳ受信機３により算出された現在位置座標の補正に使用される他、目的地までの経路誘導の際にも利用される。
【００２１】
操作スイッチ群６は、制御回路２にコマンドやデータを入力するためのもので、例えばカラー液晶ディスプレイ上に形成されたタッチスイッチ、リモコンスイッチ等で構成される。表示装置８は、道路地図、車両の現在位置、目的地までの推奨経路、経路誘導案内等を表示するためのもので、例えばカラー液晶ディスプレイで構成される。音声出力装置９は、制御回路２からの出力情報を人工音声に変えて運転者に伝えるためのもので、目的地までの経路誘導の際などに使用される。
【００２２】
ＨＤＤ１０内には、道路地図を含む地図データと、ナビゲーション装置１の各種機能を発揮させるために必要なプログラムが予め格納されている。このプログラムには、後述する本発明特有の機能を発揮させるためのプログラムの他に一般的なナビゲーション機能を実行するためのプログラム、例えばＧＰＳ受信機３により算出された位置座標を距離センサ４、車体方位センサ５等の検出値で補正する機能、補正した位置座標を地図上に位置付けて車両の現在位置を確定するマップマッチング処理機能、目的地や経由地の指定を受けて現在位置から目的地までの経路を探索する経路探索機能、その経路探索結果に応じた走行経路を地図画面上に表示して誘導する経路誘導機能などを実行するプログラムが含まれる。
【００２３】
以上のような装置の他にもナビゲーション装置１には、車両の上下／前後／左右方向の加速度を検出するための加速度センサ、車体の傾斜角を検出する車体傾斜角センサ、ＶＩＣＳ（Vehicle Information & Communication System）からの道路交通情報を受信するための通信装置等が必要により取り付けられる。
【００２４】
次に、このような構成の下での本発明の経路探索方法について、図２ないし図１１を参照して説明する。図２は、制御回路２が行なう経路探索のフローを表わしたものである。最初のステップＳ１では、走行を回避したい回避領域とその回避時間帯の指定をユーザによって受ける。なお、枠外の指差しマークはユーザの操作を受けることを表わしている（以下、同様。）。
【００２５】
回避領域と回避時間帯の指定は、表示装置８に図３に例示したような回避領域設定画面２０を表示して受ける。画面中には、ＨＤＤ１０に記憶してある地図データ中の道路地図２１を表示する。ユーザは画面中に設けてあるスクロールボタン２２、拡大ボタン２３、縮小ボタン２４を操作して希望する部分の道路地図を画面表示させ、その上で回避領域２５を指定する（第１のステップ）。
【００２６】
回避領域は、カーソル操作により画面に示すような矩形範囲で指定してもよいし、カーソルで入力した多数の点を結ぶ多角形で指定してもよい。また、回避領域の指定はこのような面積を持つ範囲で指定する他に、点又は線分で指定してもよい。点での指定は、例えば図中の交差点Ａの通過のみを回避したい場合、線分での指定は例えば図中の交差点Ａ、Ｂを結ぶ道路区間のみを回避したい場合などに使用する。点での指定は、カーソルでその点の近傍を指定して行なう。線分での指定は、両端の点近傍をカーソルで指定して行なう。
【００２７】
このように回避領域を指定したならば、次にその回避時間帯を回避時間帯入力欄２６に設定する（第２のステップ）。そして、回避領域確定ボタン２７を押す。回避領域は複数指定することができ、回避時間帯は回避領域毎に設定する。図３では、回避領域に対し毎日７時３０分〜９時００分の回避時間帯を設定する場合を示しているが、この回避時間帯は、日付（年月日、月日）、曜日および時間からなる要素のうち少なくとも１つ以上の要素を任意に組み合わせて設定できる。
【００２８】
具体的には、事業所の密集地付近に設定した回避領域に対しては通勤で渋滞する平日（つまり月曜日から金曜日）の７時００分〜８時００分、ショッピングセンター付近に設定した回避領域に対しては買物客で混雑する土日の１０時００分〜１７時００分、神社付近に設定した回避領域に対しては初詣客で混雑する１月１日の終日というように、ユーザの生活状況等に合致した詳細な回避時間帯を設定できる。
【００２９】
さらに、日付、曜日および時間は、それぞれ複数日、複数曜日、複数時間幅を設定することもできる。例えば、平日の７時００分〜８時００分と１７時００分〜１８時００分、１月１日と２日と３日の終日、毎月１日の７時００分〜８時００分などの設定も可能である。同様に、祝祭日、毎月の最終稼働日なども設定できる。これらの設定内容は、回避時間帯入力欄２６に表示される。
【００３０】
回避領域確定ボタン２７が押される度に、制御回路２は指定された回避領域とその回避時間帯を読み取ってＨＤＤ１０内に記憶する（ステップＳ２）。回避領域を記憶する際には回避領域を囲む境界線の位置を記憶すると同時に、その回避領域に含まれる道路区間も記憶しておく。この回避領域に含まれる道路区間の記憶について図４を参照して説明する。
【００３１】
経路探索に用いられる道路地図は、各道路の交差点、曲がり点、行き止まり等をノード、それぞれのノード間をリンク（道路区間）と定義し、そのリンクを接続することにより道路地図を構成したものである。図３中に示した道路地図２１は、地図データ中には図４に示したようなノードとリンクの結合として記憶されている。図中の線分の交点がノードであり、Ｎ１〜Ｎ１０はその一部ノードに対して付したノード番号である。交差点ＡはノードＮ８、交差点ＢはノードＮ４、交差点ＣはノードＮ５に対応させてある。また、各ノード間を結ぶ線分がリンクで、Ｌ１〜Ｌ１０はその一部リンクに対して付したリンク番号である。交差点Ａ、Ｂを結ぶ道路区間はリンクＬ６、交差点Ｂ、Ｃを結ぶ道路区間はリンクＬ４、交差点Ｃ、Ａを結ぶ道路区間はリンクＬ７に対応させてある。
【００３２】
回避領域を囲む境界線の位置を記憶するには、境界を規定する多角形の角の座標を記憶しておけばよい。図３、図４に例示した回避領域２５の場合には図４中の回避領域２５の四隅、ａ、ｂ、ｃ、ｄの座標を記憶しておけばよい。
【００３３】
一方、回避領域に含まれるリンクについては、該回避領域周囲の境界線と交わるリンク、及び少なくとも何れか一方の端（ノード）が該境界線上に位置するリンクを記憶しておく。両端を含むリンク全体が回避領域の内側に含まれてしまうリンクについては、後で説明するようにそのようなリンクは経路探索の際に参照されることがないので記憶を省略してもよい。従って、図３、図４に例示した回避領域２５については、図５中に点線で示したリンクＬ１、Ｌ２、Ｌ３、Ｌ５、Ｌ８、Ｌ９、Ｌ１０の７本のリンクを記憶しておく。リンクＬ４、Ｌ６、Ｌ７については記憶を省略してもよい。
【００３４】
回避領域に含まれるリンクの特定は次のようにして行なう。即ち、道路地図に含まれる各ノードについては、その位置座標（緯度、経度）とそのノードに接続されているリンクの番号がノード属性データとして記憶されている。リンクについてもその両端のノードの番号、リンクの形状（道路区間の長さ、道路の幅、方向、曲がり具合、勾配等）、道路種別、交通規制等がリンク属性データとして記憶されている。回避領域は指定により既に特定されているので、その回避領域の境界線の内側又はその境界線上に存在するノードをノード属性データを参照して特定する。次に、その特定したノードからリンク属性データを参照することで回避領域に含まれるリンクを特定する。
【００３５】
回避領域が点で指定された場合、例えば図３の道路地図２１中の交差点Ａ近傍の１点がカーソルにより回避領域として指定された場合には、カーソルにより指定された地点に一番近いノードをノード属性データを参照して探し、そのノードが交差点Ａを表わすノードＮ８であることを特定する。そしてノードＮ８を回避領域として扱う。この場合の回避領域に含まれるリンクとしては、図６中に点線で示したノードＮ８につながるリンクＬ６〜Ｌ１０の５本のリンクを記憶しておく。
【００３６】
回避領域が線分で指定された場合、例えば図３の道路地図２１中の交差点Ａ、Ｂ間の道路区間（リンクＮ６）を指定された場合には、図７中に点線で示したリンクＮ６の両端のノードＮ４、Ｎ８につながるリンクＬ１、Ｌ３、Ｌ４、Ｌ７、Ｌ８、Ｌ９、Ｌ１０の７本のリンクを記憶しておく。
【００３７】
このようにして回避領域の境界線位置、その回避領域に含まれるリンク（道路区間）、その回避時間帯を記憶したならば、次のステップＳ３に移る。ステップＳ３では出発地、出発時刻、目的地の指定をユーザによって受ける。指定には操作スイッチ群６と表示装置８を使用する。これらの項目の指定の仕方は従来と同じである。出発地、目的地は、施設の名称や電話番号で指定してもよいし、表示装置８の画面上に表示された地図上の位置をカーソルで指定する方法で行なってもよい。なお、出発地の指定がない場合には車両の現在位置を出発地とし、出発時刻の指定がない場合は現在時刻を出発時刻とみなす。
【００３８】
目的地の指定が終わったならばステップＳ４に移る。ステップＳ４では目的地までの経路探索を行なう。以下、道路地図が図８のようになっていて出発地Ｓから目的地Ｄまでの経路探索をする場合を例に挙げて説明する。回避領域として回避領域２５、回避領域３０の２個所が指定してあり、回避領域２５の回避時間帯は７時３０分〜８時３０分、回避領域３０の回避時間帯は７時４５分〜８時４５分に指定されているとする。
【００３９】
ステップＳ４の経路探索では、２個所の回避領域を無視して、即ち、回避領域は設定されていないものとして経路探索を実行する。経路探索の手法としては従来と同じダイクストラ法又はこれに準ずる手法を用い、リンク情報に基づいて計算した経路コストが最小となるリンクを接続した経路を探索経路とする。
そのような経路探索の結果として図８の例の場合には、図９中に太線で示したような出発地ＳよりノードＮ２０、Ｎ２１を通って目的地Ｄに至る最短距離の走行経路４０が探索される。走行経路を算出したならばステップＳ５に移る。
【００４０】
ステップＳ５では、算出した走行経路４０が設定されている回避領域を通過するか否かを判定する。回避領域を通過するか否かは、算出した走行経路４０の中にステップＳ２で記憶した回避領域に属する何れかのリンクが含まれているか否かで判定できる。何れの回避領域も通過しない場合はステップＳ８に移り、ステップＳ４で求めた経路を走行経路として確定する。
【００４１】
図９の例では求めた走行経路４０が回避領域２５を通過する。従って、この場合はステップＳ６に移り、回避領域２５に進入してから退出するまでの通過時間帯が回避領域２５の回避時間帯である７時３０分〜８時３０分と重なるか否かを判定する。通過時間帯は回避領域２５に進入するまでの所要時間、退出するまでの所要時間と出発時刻とから計算できる。所要時間は各リンクの長さと、各リンクの道路種別、速度規制に応じた平均走行速度から算出する。
【００４２】
走行経路が回避領域を通過しても、通過時間帯がその回避領域の回避時間帯と重ならなければ問題はない。その場合にはステップＳ８に移り、ステップＳ４で求めた経路を走行経路として確定する。図９の例において走行経路４０による回避領域２５の通過時間帯が回避領域２５の回避時間帯に重なったとする。その場合はステップＳ７に移る。
【００４３】
ステップＳ７では、回避領域２５を通行禁止扱いとする。そしてステップＳ４に戻り、再度、経路探索の計算を実行する。この場合の計算では回避領域２５内は全面通行禁止、回避領域３０は通行可として行なう。
【００４４】
ダイクストラ法では経路コストが最小となるリンクの接続を探索する。即ち、走行経路として採用するのに好ましいリンクの経路コストは低い値に、好ましくないリンク、例えば道幅が狭い、最高速度の制限値が低い等のリンクの経路コストは高い値にして探索が行なわれる。従って、通行禁止のリンクに対しては走行経路として採用されないように非常に高い経路コストを付けることになるが、そのような通行禁止リンクは結局は採用されないのでダイクストラ法による計算ではそうしたリンクは存在しないものとして扱えば済む。
【００４５】
このような理由で、回避領域２５を通行禁止としてダイクストラ法による計算を行なう場合には、回避領域２５の境界線と交わるリンクである図５中に点線で示したリンクＬ１、Ｌ２、Ｌ３、Ｌ５、Ｌ８、Ｌ９、Ｌ１０の７本のリンクは存在しないものとして扱えばよい。この７本のリンクが存在しなければ、回避領域２５に完全に含まれるリンクＬ４、Ｌ６、Ｌ７が走行経路として選択されることはあり得ない。図５の説明の際に、回避領域２５に含まれるリンクとしてリンクＬ４、Ｌ６、Ｌ７を記憶する必要はないと説明したのはこのような理由による。
【００４６】
ステップＳ４に戻って回避領域２５を通行禁止とした経路探索を行なうと、今度は図１０中に太線で示したような出発地ＳよりノードＮ３、Ｎ２２を通って目的地Ｄに至る走行経路４１が探索される。走行経路を算出したならば再びステップＳ５に移る。
【００４７】
ステップＳ５では、算出した走行経路４１が設定されている回避領域を通過するか否かを判定する。回避領域を通過するか否かは、前と同様に算出した走行経路４１の中にステップＳ２で記憶した回避領域に属する何れかのリンクが含まれているか否かで判定する。何れの回避領域も通過しない場合はステップＳ８に移り、ステップＳ４で求めた走行経路４１を探索した走行経路として確定する。
【００４８】
図１０の走行経路４１は、回避領域３０を通過する。従って、ステップＳ６に移り、回避領域３０に進入してから退出するまでの通過時間帯が回避領域３０の回避時間帯である７時４５分〜８時４５分と重なるか否かを前と同様に判定する。
走行経路４１が回避領域３０を通過しない場合、通過してもその通過時間帯が回避領域３０の回避時間帯である７時４５分〜８時４５分と重ならなければ問題はないのでステップＳ８に移り、ステップＳ４で求めた走行経路４１を探索した走行経路として確定する。
【００４９】
図１０の走行経路４１による回避領域３０の通過時間帯が回避領域３０の回避時間帯に重なったとする。その場合はステップＳ７に移る。ステップＳ７では、回避領域３０も通行禁止とする。そしてステップＳ４に戻り再び経路探索を実行する。
【００５０】
この場合の経路探索では、回避領域２５と回避領域３０の双方が通行禁止として計算される。その計算結果として図１１中に太線で示したように出発地ＳよりノードＮ３、Ｎ２６、Ｎ２７、Ｎ６、Ｎ２０、Ｎ２１を経由して目的地Ｄに至る走行経路４２が探索される。この走行経路４２は何れの回避領域も通過していない。従って、ステップＳ５からステップＳ８に移行して走行経路４２を探索した経路として確定する。
【００５１】
このようにして走行経路が確定したならば、ステップＳ９にてユーザによる経路誘導開始の指示を受ける。そして、ステップＳ１０に移って経路誘導を開始する。経路誘導の仕方は従来から行なわれている方法と同じである。即ち、ＧＰＳ受信機３にて自車位置を検出し、検出した位置を距離センサ４、車体方位センサ５等の検出値で補正する。次に車両が道路上を走行しているとの前提で補正した位置を地図の道路上に位置付けるマップマッチング処理を行なって車両位置を確定する。確定した位置を表示装置８上の地図に重ねて表示すると同時に確定している走行経路と対照して左右折案内をすべき地点か否かを判定する。案内すべき地点であった場合には表示装置８及び音声出力装置９にて案内を行なう。こうした処理の繰り返しにより車両を目的地に誘導する。
【００５２】
以上、説明したように本実施形態のナビゲーション装置１では、最初に回避領域とその回避時間帯の登録を受ける。目的地に至る経路探索の計算では、最初は回避領域を無視して経路を探索する。探索した経路に従った走行が回避領域をその回避時間帯に通過するか否か判定し、通過しなければ探索した経路を走行経路として確定する。回避領域をその回避時間帯に通過する場合には、次にその回避領域を通行禁止にして再度、経路探索を実行する。
【００５３】
このような処理を探索した経路に従った走行が回避領域をその回避時間帯に通過することがなくなるまで繰り返す。そして、何れの回避領域をもその回避時間帯に通過しなくなった場合に、その探索経路を走行経路として確定する。従って、このような経路探索によれば、何れの回避領域をもその回避時間帯に通過することのない走行経路を探索することができる。また、上記経路探索方法によれば、ＣＰＵ１１の計算量が比較的少なくなるので処理時間を短縮できる。
【００５４】
さらに、日付、曜日および時間からなる要素のうち少なくとも１つ以上の要素を組み合わせて回避時間帯を設定できるので、ユーザの生活状況等に合致した適切な回避時間帯を設定でき使い勝手が向上する。
【００５５】
なお、前記実施形態の説明では、車両用のナビゲーション装置を対象に説明をしたが、本発明のナビゲーション装置及びその経路探索方法は車両用以外、例えば、モバイル端末などにおいても適用可能である。
【図面の簡単な説明】
【００５６】
【図１】本発明の一実施形態に係るナビゲーション装置の構成を示すブロック図である。
【図２】経路探索の制御フローである。
【図３】回避領域設定画面の例である。
【図４】ノードとリンクの接続で表わした道路地図の例である。
【図５】回避領域が面積を持つ範囲で指定された場合における回避領域の記憶の仕方を説明する図である。
【図６】回避領域が点で指定された場合における回避領域の記憶の仕方を説明する図である。
【図７】回避領域が線分で指定された場合における回避領域の記憶の仕方を説明する図である。
【図８】経路探索方法を説明するための道路地図の例である。
【図９】探索された経路と回避領域との関係を説明するための図である。
【図１０】探索された経路と回避領域との関係を説明するための他の図である。
【図１１】探索された経路と回避領域との関係を説明するための他の図である。
【符号の説明】
【００５７】
図面中、１はナビゲーション装置、２は制御装置（経路探索手段、回避領域設定手段、回避時間帯設定手段）、３はＧＰＳ受信機、８は表示装置、９は音声出力装置、１０はＨＤＤを示す。
【図１】
2006226997.tif 000003
【図２】
2006226997.tif 000004
【図３】
2006226997.tif 000005
【図４】
2006226997.tif 000006
【図５】
2006226997.tif 000007
【図６】
2006226997.tif 000008
【図７】
2006226997.tif 000009
【図８】
2006226997.tif 000010
【図９】
2006226997.tif 000011
【図１０】
2006226997.tif 000012
【図１１】
2006226997.tif 000013