JP5396164B2 - 経路探索装置、および、経路探索方法 - Google Patents

Description

本発明は、経路探索装置、および、経路探索方法に関する。

推奨経路から逸れて走行した区間の経路を学習経路として登録しておくナビゲーション装置がある（例えば、特許文献１）。このようなナビゲーション装置では、経路探索した推奨経路について部分的に学習経路による置き換えを行う。

特開２００１−１７４２８０号

ところで、上記のナビゲーション装置では、学習経路の道路種別（有料道路、一般道路、細道路、など）について区別していない。そのため、例えば、一般道路に限定した経路探索が要求されているにもかかわらず、有料道路を含む学習経路を用いてしまう場合がある。そうすると、ユーザに指定された探索条件に合わない推奨経路が探索されてしまう。

本発明は、学習経路による置き換えを行う経路探索において、探索条件に応じた推奨経路を探索する技術を提供することを目的とする。

上記課題を解決するための本願発明は、ナビゲーション装置などの経路探索装置であって、推奨経路から逸れて移動した区間の経路を学習経路として記憶しておく記憶手段と、推奨経路の探索条件を設定する設定手段と、前記探索条件に基づいて推奨経路を探索する推奨経路探索手段と、探索された推奨経路に対して適用可能な学習経路を前記記憶手段から選び出し、当該推奨経路に適用する適用手段と、前記学習経路が適用された推奨経路を表示する表示手段と、を備え、前記記憶手段は、前記学習経路とともに、当該学習経路の種別情報を記憶しておき、前記適用手段は、前記探索条件に応じた種別情報を有する学習経路を前記記憶手段から選び出す。

また、前記記憶手段は、前記学習経路と、前記種別情報と、当該学習経路の優先順位と、を対応付けて記憶しており、前記適用手段は、前記探索条件に応じた種別情報を有する学習経路のうち、前記優先順位に基づいて学習経路を前記記憶手段から選び出す。

本発明の一実施形態が適用されたナビゲーション装置の概略構成図である。 地図データの概略データ構造を示す図である。 学習経路情報の概略データ構造を示す図である。 演算処理部の機能ブロック図である。 学習経路登録処理を示すフロー図である。 経路探索処理を示すフロー図である。 （Ａ）本願における推奨経路の表示例を示す図である。（Ｂ）探索条件に応じた学習経路を適用できない場合における推奨経路の表示例を示す図である。 学習経路適用処理を示すフロー図である。 探索条件と、学習経路の種別情報と、の対応関係の一例を示す図である。 （Ａ）本願における、複数ルート探索により探索された推奨経路の表示例を示す図である。（Ｂ）探索条件に応じた学習経路を適用できない場合における、複数ルート探索により探索された推奨経路の表示例を示す図である。

以下、本発明の実施形態の一例を図面を参照して説明する。

図１は、本発明の一実施形態が適用されたナビゲーション装置１００の概略構成図である。図示するように、ナビゲーション装置１００は、演算処理部１と、ディスプレイ２と、記憶装置３と、音声入出力装置４（マイクロフォン４１、スピーカ４２）と、入力装置５（タッチパネル５１、ダイヤルスイッチ５２）と、車速センサ６と、ジャイロセンサ７と、ＧＰＳ受信装置８と、ＦＭ多重放送受信装置９と、ビーコン受信装置１０と、を備えている。ナビゲーション装置１００は、車両に載置されている車載用ナビゲーション装置としてもよいし、携帯電話やＰＤＡなどの携帯端末としてもよい。

演算処理部１は、様々な処理を行う中心的ユニットである。例えば、演算処理部１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ（Central Processing Unit）２１と、記憶装置３から読み出した地図データ、演算データなどを格納するＲＡＭ（Random Access Memory）２２と、プログラムやデータを格納するＲＯＭ（Read Only Memory）２３と、各種ハードウェアを演算処理部１に接続するためのＩ／Ｆ（インターフェイス）２４と、を有する。そして、演算処理部１は、各デバイスをバス２５で相互に接続した構成からなる。そして、後述する各機能部（１０１〜１０７）は、ＣＰＵ２１がＲＡＭ２２などのメモリに読み出したプログラムを実行することで実現される。

例えば、演算処理部１は、各種センサ（６、７）やＧＰＳ受信装置８から出力される情報を基にして現在地を検出する。また、得られた現在地情報に基づいて、表示に必要な地図データを記憶装置３から読み出す。また、読み出した地図データをグラフィック展開し、そこに現在地マーク（或いは、移動体の位置を示す移動体マーク）を重ねてディスプレイ２に表示する。また、記憶装置３に記憶されている地図データを用いて、ユーザから指示された出発地（現在地）と目的地とを結ぶ最適な経路（以下では「推奨経路」という）を探索する。また、音声入出力装置４のスピーカ４２やディスプレイ２を用いてユーザを誘導する。

ディスプレイ２は、演算処理部１で生成されたグラフィックス情報を表示するユニットである。ディスプレイ２は、液晶ディスプレイや有機ＥＬ（Electro-Luminescence）ディスプレイなどで構成される。

記憶装置３は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成される。この記憶媒体には、例えば、地図データ３１０、学習経路情報４００、音声データ、動画データ、等が記憶されている。

図２は、地図データ３１０の概略データ構造を示す図である。図示するように、地図データ３１０は、地図上の区画された領域であるメッシュの識別コード（メッシュＩＤ）３１１ごとに、そのメッシュ領域に含まれている道路を構成する各リンクのリンクデータ３２０を含んでいる。

リンクデータ３２０は、リンクの識別コード（リンクＩＤ）３２１ごとに、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３２２、リンクを含む道路の種別情報を示す道路種別３２３、リンクの長さを示すリンク長情報３２４、リンク旅行時間３２５、２つのノードにそれぞれ接続するリンクの識別コード（接続リンクＩＤ）３２６、などを含んでいる。なお、ここでは、リンクを構成する２つのノードについて開始ノードと終了ノードを区別することで、道路の上り方向と下り方向を、それぞれ別のリンクとして管理することができる。なお、道路種別３２３には、「有料道路」、「一般道路」、「細道路」といった情報が含まれる。また、道路種別３２３には、有料道路の利用料金や、道路幅などの情報も付加されている。

また、図３は、学習経路情報４００の概略データ構造を示す図である。学習経路情報４００には、推奨経路から逸れて走行した区間の経路（以下では、「学習経路」という）が登録されている。例えば、学習経路情報４００は、図示するように、学習経路の識別コード（学習経路ＩＤ）４１１ごとのレコード４１５からなる。各レコード４１５には、学習経路を構成する各リンクの識別コード（リンクＩＤ）４１２と、当該学習経路の走行回数４１３と、当該学習経路の種別情報４１４と、が対応付けて格納されている。ここで、学習経路を構成する各リンクのリンクＩＤ４１２については、推奨経路を逸脱した地点（逸脱地点）のリンクから、推奨経路に復帰した地点（復帰地点）のリンクまでのリンクＩＤが、走行した順序で登録されている。走行回数４１３は、当該学習経路の優先順位を示す値として、例えば、「Ｘ回」、「Ｙ回」などの走行回数が登録されている。また、種別情報４１４は、当該学習経路の種別情報として、例えば、「有料道路」、「一般道路」、「細道路」などの文字列が登録されている。

図１に戻り、音声入出力装置４は、音声入力装置としてマイクロフォン４１と、音声出力装置としてスピーカ４２と、を備える。マイクロフォン４１は、運転手やその他の搭乗者から発された音声などの、ナビゲーション装置１００の外部の音声を取得する。スピーカ４２は、演算処理部１で生成された音声信号を出力する。これらのマイクロフォン４１とスピーカ４２は、車両の所定の部位に、別個に配置されている。

入力装置５は、ユーザからの指示を受け付けるユニットである。入力装置５は、タッチパネル５１と、ダイヤルスイッチ５２と、その他のハードスイッチ（図示せず）であるスクロールキー、縮尺変更キーなどで構成される。

タッチパネル５１は、ディスプレイ２の表示面に貼られた透過性のある操作パネルである。タッチパネル５１は、ディスプレイ２に表示された画像のＸＹ座標と対応したタッチ位置を特定し、タッチ位置を座標に変換して出力する。タッチパネル５１は、感圧式または静電式の入力検出素子などにより構成される。

ダイヤルスイッチ５２は、時計回り及び反時計回りに回転可能に構成され、所定の角度の回転ごとにパルス信号を発生し、演算処理部１に出力する。演算処理部１では、パルス信号の数から、ダイヤルスイッチ５２の回転角度を求める。

車速センサ５、ジャイロセンサ７、及び、ＧＰＳ受信装置８は、移動体（ナビゲーション装置１００）の現在位置（自車位置）などを検出するために使用される。車速センサ６は、車速を算出するために用いる車速データを出力するセンサである。ジャイロセンサ７は、光ファイバジャイロや振動ジャイロ等で構成され、移動体の回転による角速度を検出するものである。ＧＰＳ受信装置８は、ＧＰＳ衛星からの信号を受信し、移動体とＧＰＳ衛星間の距離とその距離の変化率を３個以上の衛星に対して測定することで、移動体の現在位置や進行速度を測定する。

ＦＭ多重放送受信装置９は、ＦＭ多重放送局から送られてくるＦＭ多重放送信号を受信する。ＦＭ多重放送には、ＶＩＣＳ（Vehicle Infomation Communication System：登録商標）情報の概略現況交通情報、規制情報、ＳＡ／ＰＡ（サービスエリア／パーキングエリア）情報、駐車場情報、天気情報などのＦＭ多重一般情報としてラジオ局が提供する文字情報などがある。

ビーコン受信装置１０は、ビーコンから送られてくる渋滞情報、規制情報、ＳＡ／ＰＡ情報、駐車場情報などを受信する。

図４は、演算処理部１の機能ブロック図である。図示するように、演算処理部１は、主制御部１０１と、入力受付部１０２と、表示処理部１０３と、経路探索部１０４と、経路誘導部１０５と、学習経路登録部１０６と、学習経路適用部１０７と、を有する。

主制御部１０１は、演算処理部１の各部を統括して制御する処理を行う。

入力受付部１０２は、入力装置５に入力されたユーザからの要求を受け付け、その要求内容を解析する。入力受付部１０２は、解析結果に応じたデータを主制御部１０１に通知する。例えば、入力受付部１０２は、ナビゲーション装置１００に、電源の投入、切断を指示する要求、等を受け付け、主制御部１０１に通知する。また、入力受付部１０２は、ナビゲーション装置１００が有する各種機能の設定（例えば、探索条件の設定）に関する入力データを受け付け、主制御部１０１に通知する。

表示処理部１０３は、ディスプレイ２に、地図、探索した推奨経路、学習経路、ユーザに通知する各種メッセージ、等を表示させる。具体的には、表示処理部１０３は、ディスプレイ２に表示させるための描画コマンドを生成して通知する。なお、表示処理部１０３は、地図をディスプレイ２に表示させる際には、表示が要求された領域（例えば、推奨経路全体を表示するのに必要な領域）にある地図データを記憶装置３から抽出し、指定された描画方式で、道路、その他の地図構造物、現在位置、目的地、推奨経路、学習経路、等を描画するように地図描画コマンドを生成する。また、表示処理部１０３は、ディスプレイ２に表示させた地図上に、車両の位置を示す車両マークや各種設定画面などを表示させる。

経路探索部１０４は、推奨経路を探索する処理（経路探索処理）を行う。具体的には、経路探索部１０４は、出発地、目的地、探索条件などについて設定を行う。そして、設定された探索条件に基づいて、ダイクストラ法等を用い、指定された２地点（出発地、目的地）間を結ぶ経路のコスト（例えば、総距離や総旅行時間）が最小となる経路を探索する。このとき、経路探索部１０４は、探索した推奨経路を構成する各リンクの識別コード（リンクＩＤ）３２１を、それぞれ対応付けてＲＡＭ２２等のメモリに記憶しておく。

経路誘導部１０５は、経路探索部１０４によって探索された推奨経路を用いて経路誘導を行う。また、詳細については後述するが、学習経路適用部１０７は、経路探索部１０４によって探索された推奨経路に学習経路を適用する（推奨経路の一部区間を学習経路で置き換える）場合がある。この場合、経路誘導部１０５は、学習経路が適用された後の推奨経路を用いて経路誘導を行う。

具体的には、経路誘導部１０５は、表示処理部１０３を介して、ディスプレイ２に表示された地図の範囲に含まれている推奨経路を表示（強調表示）する。このとき、経路誘導部１０５は、移動体（車両）の現在位置を示す移動体マーク（カーマーク）を推奨経路上に表示する。また、経路誘導部１０５は、推奨経路の情報と、現在位置とを比較し、主要な交差点等を通過する前に直進すべきか、右左折すべきかを、ディスプレイ２に表示させるとともに、音声入出力装置４のスピーカ４２を用いて音声でユーザに知らせる。

学習経路登録部１０６は、学習経路に関する情報を登録する処理（学習経路登録処理）を行う。

具体的には、学習経路登録部１０６は、推奨経路から逸れて走行した経路（学習経路）を構成するリンクＩＤ３２１を、学習経路情報４００に格納する。例えば、学習経路登録部１０６は、推奨経路を逸脱した地点のリンクから、推奨経路に復帰した地点のリンクまでのリンクＩＤ３２１を、走行した順序で格納していく。

また、学習経路登録部１０６は、学習経路の走行実績を学習経路情報４００に格納しておく。例えば、学習経路登録部１０６は、推奨経路から逸れて走行した経路が学習経路情報４００に既に格納されている場合には、当該経路（学習経路）に対応付けられている走行回数４１３をカウントアップする。なお、学習経路登録部１０６は、推奨経路から逸れて走行した経路でなくても、走行した経路が学習経路情報４００に既に格納されている場合には、当該経路（学習経路）に対応付けられている走行回数４１３をカウントアップするようにしてもよい。さらに、推奨経路が設定されていない場合にも、上記のカウントアップをするようにしてもよい。

また、学習経路登録部１０６は、学習経路の種別情報４１４を格納する。ここで、種別情報４１４には、「有料道路」、「一般道路」、「細道路」などの情報を含む。

学習経路適用部１０７は、経路探索部１０４によって探索された推奨経路に学習経路を適用する処理（学習経路適用処理）を行う。具体的には、学習経路適用部１０７は、経路探索部１０４によって探索された推奨経路に適用可能な学習経路を、学習経路情報４００から抽出する。ここで抽出される学習経路は、推奨経路の探索条件に応じた種別情報４１４を有している学習経路である。そして、学習経路適用部１０７は、推奨経路の一部区間を、抽出した当該学習経路で置き換える。学習経路適用処理の詳細については後述する。

なお、上記した各構成要素は、ナビゲーション装置１００の構成を理解容易にするために、主な処理内容に応じて分類したものである。構成要素の分類や仕方やその名称によって、本願発明が制限されることはない。ナビゲーション装置１００の構成は、処理内容に応じて、さらに多くの構成要素に分類することもできる。また、１つの構成要素がさらに多くの処理を実行するように分類することもできる。

また、各機能部は、ハードウェア（ＡＳＩＣなど）により構築されてもよい。また、各機能部の処理が一つのハードウェアで実行されてもよいし、複数のハードウェアで実行されてもよい。

次に、上記構成からなるナビゲーション装置１００の特徴的な動作について説明する。

＜学習経路登録処理＞
図５は、ナビゲーション装置１００が行う学習経路登録処理を示すフローチャートである。

演算処理部１の学習経路登録部１０６は、経路誘導部１０５により経路誘導が開始されるタイミングで、学習経路登録処理を開始する。

学習経路登録処理を開始すると、経路誘導部１０５は、移動体（車両）の現在位置を算出する（ステップＳ１０１）。例えば、経路誘導部１０５は、車速センサ６で出力された車速データや、ジャイロセンサ７で検出した角速度データなどを用いて、移動体の現在位置を算出する。また、経路誘導部１０５は、ＧＰＳ受信装置８の出力データを用いて現在位置を修正する。

そして、経路誘導部１０５は、移動体が目的地に到達したか否か判定する（ステップＳ１０２）。例えば、経路誘導部１０５は、ステップＳ１０１で算出した現在位置と、推奨経路の目的地として設定されている位置と、を比較する。そして、現在位置が目的地と一致（ほぼ一致）している場合に、移動体が目的地に到達したと判定する。一方、現在位置が目的地と一致していない場合には、移動体は目的地に到達していないと判定する。

経路誘導部１０５は、移動体が目的地に到達したと判定した場合には（ステップＳ１０２；Ｙｅｓ）、経路誘導を終了する。これに伴い、学習経路登録部１０６は、本フロー（学習経路登録処理）を終了する。

一方、経路誘導部１０５は、移動体が目的地に到達していないと判定した場合には（ステップＳ１０２；Ｎｏ）、処理をステップＳ１０３に移行する。

処理がステップＳ１０３に移行すると、経路誘導部１０５は、移動体が推奨経路から逸れているか否か判定する（ステップＳ１０３）。例えば、経路誘導部１０５は、ステップＳ１０１で算出した現在位置と、推奨経路と、を比較する。そして、現在位置が推奨経路上にない場合に、移動体が推奨経路から逸れていると判定する。一方、現在位置が推奨経路上にある場合には、移動体は推奨経路から逸れていないと判定する。

経路誘導部１０５は、移動体が推奨経路から逸れていると判定した場合には（ステップＳ１０３；Ｙｅｓ）、ステップＳ１０１で算出した現在位置に基づいて、移動体が走行しているリンクを地図データ３１０から特定する。そして、特定したリンクのリンクＩＤ３２１を、学習経路の候補としてＲＡＭ２２などのメモリに一時的に記憶しておく。その後、経路誘導部１０５は、処理をステップＳ１０１に戻す。従って、移動体が推奨経路から逸れて走行している間に、ステップＳ１０１からステップＳ１０３の処理を繰り返し実行することにより、学習経路の候補となるリンクＩＤ３２１を蓄積することができる。

一方、経路誘導部１０５は、移動体が推奨経路から逸れていないと判定した場合には（ステップＳ１０３；Ｎｏ）、処理をステップＳ１０４に移行する。

処理がステップＳ１０４に移行すると、経路誘導部１０５は、移動体が推奨経路に復帰したのか否か判定する（ステップＳ１０４）。すなわち、移動体が推奨経路ではない経路から推奨経路に戻ってきたのか否か判定する。

具体的には、経路誘導部１０５は、直前のステップＳ１０１で算出した現在位置と、前々回のステップＳ１０１で算出した現在位置と、を比較する。そして、前々回のステップＳ１０１で算出した現在位置が推奨経路上にはなく、直前のステップＳ１０１で算出した現在位置が推奨経路上にある場合に、推奨経路に復帰したと判定する。一方、前々回のステップＳ１０１で算出した現在位置と、直前のステップＳ１０１で算出した現在位置と、がともに推奨経路上にある場合には、推奨経路に復帰したのではないと判定する。なお、前々回のステップＳ１０１で算出した現在位置が存在しない場合には、推奨経路に復帰したのではないと判定する。

経路誘導部１０５は、移動体が推奨経路に復帰したと判定した場合には（ステップＳ１０４；Ｙｅｓ）、処理をステップＳ１０５に移行する。

一方、経路誘導部１０５は、移動体が推奨経路に復帰したのではない（推奨経路に従って走行し続けている）と判定した場合には（ステップＳ１０４；Ｎｏ）、処理をステップＳ１０１に戻す。従って、移動体が推奨経路上を走行し続けている間は、経路誘導部１０５は、ステップＳ１０１からステップＳ１０４の処理を繰り返し実行する。

処理がステップＳ１０５に移行すると、学習経路登録部１０６は、推奨経路から逸れて走行した経路を学習経路として登録する（ステップＳ１０５）。

具体的には、学習経路登録部１０６は、まず、ステップＳ１０３においてメモリに記憶していた学習経路の候補となるリンクＩＤ３２１を読み出す。そして、読み出した学習経路の候補が、学習経路情報４００に既に登録されている学習経路であるか調べる。

ここで、学習経路の候補が既に登録されている場合には、学習経路登録部１０６は、その学習経路の学習経路ＩＤ４１１に対応付けられている走行回数４１３をカウントアップする（すなわち「１」加えた値に変更する）。

一方、学習経路の候補が未だ登録されていない場合には、学習経路登録部１０６は、その候補を学習経路として学習経路情報４００に追加する。

例えば、学習経路登録部１０６は、学習経路情報４００にレコード４１５を追加し、学習経路ＩＤ４１１、学習経路を構成するリンクのリンクＩＤ４１２、走行回数４１３、種別情報４１４を対応付けて格納する。

ここで、学習経路を構成するリンクのリンクＩＤ４１２には、ステップＳ１０３においてメモリに蓄積しておいたリンクＩＤ３２１が、走行した順序で格納される。また、走行回数４１３には、「１回」を示すデータが格納される。なお、学習経路登録部１０６は、逸脱地点のリンクＩＤ４１２については、逸脱地点の座標を対応付けて格納するようにしてもよい。また、復帰地点のリンクＩＤ４１２についても同様に、復帰地点の座標を対応付けて格納するようにしてもよい。

また、種別情報４１４には、「有料道路」、「一般道路」、「細道路」などを示すデータが格納される。ここで、種別情報４１４は、リンクＩＤ３２１に対応付けられている道路種別３２３を用いて決定される。具体的には、学習経路登録部１０６は、学習経路を構成するリンクに１つでも有料道路が含まれている場合には、当該学習経路を「有料道路」として格納する。また、学習経路を構成するリンクに有料道路も細道路も含まれていない場合には、当該学習経路を「一般道路」として格納する。また、それ以外の場合（学習経路を構成するリンクに有料道路は含まれておらず、細道路が１つでも含まれている場合）には、「細道路」として格納する。

このようなステップＳ１０５における学習経路の登録は、移動体が推奨経路に復帰する毎に行われる。そのため、出発地から目的地までの間で、複数回、推奨経路から逸れて走行することがある場合でも、各学習経路を学習経路情報４００に登録することができる。

学習経路の登録後、学習経路登録部１０６は、処理をステップＳ１０１に戻す。

＜経路探索処理＞
図６は、ナビゲーション装置１００が行う経路探索処理を示すフローチャートである。

演算処理部１の経路探索部１０４は、例えば、ユーザからの指示に基づいて経路探索処理を開始する。

経路探索処理を開始すると、経路探索部１０４は、出発地、目的地の設定を行う（ステップＳ２０１）。例えば、経路探索部１０４は、所定の設定画面を表示して、ユーザから出発地、目的地の指定を受け付ける。

次に、経路探索部１０４は、推奨経路の探索条件を設定する（ステップＳ２０２）。例えば、経路探索部１０４は、所定の設定画面を表示して、ユーザから探索条件の入力を受け付ける。

ここで、設定可能な探索条件には、例えば、有料道路を優先して探索する「第１の有料優先」、「第１の有料優先」の探索条件に基づいて探索された推奨経路とは別の経路を探索する「第２の有料優先」、有料道路を優先し、かつ、料金を考慮して探索する「第３の有料優先」、一般道路を優先して探索する「第１の一般優先」、道幅の広い道路を優先し、かつ、「第１の一般優先」の探索条件に基づいて探索された推奨経路とは別の経路を探索する「第２の一般優先」、出発地から目的地までの距離が最短となるように探索する「距離優先」、などが含まれる。

次に、経路探索部１０４は、渋滞情報を取得する（ステップＳ２０３）。具体的には、経路探索部１０４は、ＦＭ多重放送受信装置９やビーコン受信装置１０などを用いて、経路探索対象のエリア（例えば、出発地から目的地までを含むエリア）の渋滞情報（規制情報なども含む）を取得する。

続いて、経路探索部１０４は、経路探索を行う（ステップＳ２０４）。具体的には、経路探索部１０４は、ステップＳ２０１で設定された出発地から目的地までの推奨経路を、ステップＳ２０２で設定された探索条件に基づいて探索する。

例えば、経路探索部１０４は、探索条件として「第１の有料優先」が設定されている場合には、「有料道路」、「一般道路」、又は、「細道路」の道路種別３２３を有しているリンク（リンクＩＤ３２１）を用いて、推奨経路を探索する。

また、経路探索部１０４は、探索条件として「第２の有料優先」が設定されている場合には、「有料道路」、「一般道路」、又は、「細道路」の道路種別３２３を有しているリンクを用いて、推奨経路を探索する。ただし、「有料道路」の道路種別３２３を有していても、「第１の有料優先」の探索条件に基づいて探索された推奨経路に使用されているリンクについては除外する。すなわち、「第２の有料優先」の探索条件に基づいて探索される推奨経路は、「第１の有料優先」の探索条件に基づいて探索される推奨経路とは、使用される有料道路が少なくとも異なる。

また、経路探索部１０４は、探索条件として「第３の有料優先」が設定されている場合には、「有料道路」、「一般道路」、又は、「細道路」の道路種別３２３を有しているリンクを用いて、推奨経路を探索する。ただし、「有料道路」の道路種別３２３を有しているリンクのうち、利用料金が低料金（例えば、最低料金）の道路種別３２３を有しているリンクが優先して用いられる。

また、経路探索部１０４は、探索条件として「第１の一般優先」が設定されている場合には、「一般道路」又は「細道路」の道路種別３２３を有しているリンクを用いて、推奨経路を探索する。

また、経路探索部１０４は、探索条件として「第２の一般優先」が設定されている場合には、「一般道路」の道路種別３２３を有しているリンクを用いて、推奨経路を探索する。ただし、「一般道路」の道路種別３２３を有していても、「第１の一般優先」の探索条件に基づいて探索された推奨経路に使用されているリンクについては除外する。そして、ここで除外されないリンクの中でも、道路幅が広い道路（例えば、最も道路幅の広い道路）の道路種別３２３を有しているリンクが優先して用いられる。

また、経路探索部１０４は、探索条件として「距離優先」が設定されている場合には、「有料道路」又は「一般道路」の道路種別３２３を有しているリンクを用いて、推奨経路を探索する。ただし、「有料道路」又は「一般道路」の道路種別３２３を有しているリンクのうち、出発地から目的地までの総延べ距離が短距離（例えば、最短距離）となるリンクが用いられる。

また、経路探索部１０４は、上記の探索条件のうち、「第１の有料優先」、「第２の有料優先」、「第３の有料優先」、又は、「第１の一般優先」が設定されている場合には、渋滞情報を考慮して経路探索を行う。具体的には、経路探索部１０４は、ステップＳ２０３で取得した渋滞情報を読み出し、渋滞しているリンクについては、推奨経路の探索対象から除外、或いは、優先順位を下位にする。一方、上記の探索条件のうち、「第２の一般優先」が設定されている場合には、道幅を最優先して推奨経路を探索するため、渋滞情報を考慮しない。同様に、「距離優先」が設定されている場合には、出発地から目的地までの距離を最優先して推奨経路を探索するため、渋滞情報を考慮しない。

以上のような探索条件に基づいて推奨経路を探索後、経路探索部１０４は、探索した推奨経路を構成する各リンクのリンクＩＤ３２１を、ＲＡＭ２２等のメモリに記憶する。

次に、学習経路適用部１０７は、学習経路適用処理を行う（ステップＳ２０５）。すなわち、学習経路適用部１０７は、探索条件に応じた種別情報４１４を有する学習経路を選び出し、ステップＳ２０４で探索した推奨経路に対して、当該学習経路を適用する（学習経路で置き換える）処理を行う。学習経路適用処理の詳細については後述する。

そして、経路誘導部１０５は、ステップＳ２０５で得られた結果（学習経路が適用された後の推奨経路など）を、ディスプレイ２に表示する（ステップＳ２０６）。

図７（Ａ）は、探索条件に基づいて探索された推奨経路とともに、学習経路が適用された後の推奨経路を表示したときの表示例を示す図である。図示するように、推奨経路の探索条件が「第１の一般優先」である場合には、種別情報４１４が「一般道路」（或いは「細道路」）である学習経路が選ばれて表示される。すなわち、探索条件に応じた種別情報４１４を有する学習経路が表示される。また、経路誘導部１０５は、学習経路の区間（点線）については、他の経路と異なる色で表示するなどして強調表示する。

これに対し、探索条件に応じた種別情報を有する学習経路を適用できない場合には、図７（Ａ）に示すような推奨経路を表示することはできない。

図７（Ｂ）は、探索条件に応じた種別情報を有する学習経路を適用できないときの表示例を示す図である。図示するように、推奨経路の探索条件が「第１の一般優先」であるにもかかわらず、有料道路を含む学習経路が表示されてしまう場合がある。これでは、ユーザにとって必要な推奨経路が表示されているとはいえない。

図６に戻り、経路探索部１０４は、ステップＳ２０６の処理後、本フローを終了する。

次に、学習経路適用処理（ステップＳ２０５）の詳細について説明する。

＜学習経路適用処理＞
図８は、ナビゲーション装置１００が行う学習経路適用処理を示すフローチャートである。

演算処理部１の学習経路適用部１０７は、処理が上記のステップＳ２０５に移行すると、適用候補となる学習経路を学習経路情報４００から抽出する（ステップＳ３０１）。具体的には、学習経路適用部１０７は、ステップＳ２０２で設定された探索条件に応じた種別情報４１４を有する学習経路を、学習経路情報４００から抽出する。ただし、ステップＳ２０４で探索された推奨経路上に、逸脱地点および復帰地点がない学習経路については、抽出しない。従って、学習経路適用部１０７は、例えば、逸脱地点のリンクおよび復帰地点のリンクが推奨経路を構成するリンクに含まれている学習経路（レコード４１５）のうち、探索条件に応じた種別情報４１４を有する学習経路を、学習経路情報４００から抽出する。

図９は、探索条件と、学習経路の種別情報４１４と、の対応関係の一例を示す図である。

図示するように、学習経路適用部１０７は、探索条件として「第１の有料優先」が設定されている場合には、「有料道路」、「一般道路」、又は、「細道路」の種別情報４１４を有している学習経路を抽出する。

また、学習経路適用部１０７は、探索条件として「第２の有料優先」が設定されている場合には、「有料道路」、「一般道路」、又は、「細道路」の種別情報４１４を有している学習経路を抽出する。ただし、「有料道路」の種別情報４１４を有していても、「第１の有料優先」の探索条件に基づいて探索された推奨経路に適用済みの学習経路については除外する。これにより、「第１の有料優先」の探索条件に基づいて探索される推奨経路に適用済みの学習経路と同一の学習経路を抽出することはない。また、「一般道路」の種別情報４１４を有していても、適用対象（置き換え対象）の区間（推奨経路上）が「有料道路」である場合には、当該学習経路については抽出しない。すなわち、有料道路の区間に対して、一般道路の学習経路で置き換えることはない。

また、学習経路適用部１０７は、探索条件として「第３の有料優先」が設定されている場合には、「一般道路」又は「細道路」の種別情報４１４を有している学習経路を抽出する。ただし、「一般道路」の種別情報４１４を有していても、適用対象（置き換え対象）の区間（推奨経路上）が「有料道路」である場合には、当該学習経路については抽出しない。すなわち、有料道路の区間に対して、一般道路の学習経路で置き換えることはない。なお、「有料道路」の種別情報４１４を有している学習経路を抽出しないのは、ステップＳ２０４で探索された推奨経路は、低料金の有料道路（リンク）が優先して選択されているためである。仮に、他の有料道路（学習経路）で置き換えてしまうと、利用料金が低料金とならなくなる。

また、学習経路適用部１０７は、探索条件として「第１の一般優先」が設定されている場合には、「一般道路」又は「細道路」の種別情報４１４を有している学習経路を抽出する。

また、学習経路適用部１０７は、探索条件として「第２の一般優先」が設定されている場合には、「一般道路」の種別情報４１４を有している学習経路を抽出する。ただし、「一般道路」の種別情報４１４を有していても、「第１の一般優先」の探索条件に基づいて探索された推奨経路に適用済みの学習経路については除外する。これにより、「第１の一般優先」の探索条件に基づいて探索される推奨経路に適用済みの学習経路と同一の学習経路を抽出することはない。なお、「細道路」の種別情報４１４を有している学習経路を抽出しないのは、ステップＳ２０４で探索された推奨経路は、広い道路幅の道路（リンク）が優先して選択されているためである。仮に、「細道路」の学習経路で置き換えてしまうと、推奨経路は広い道路幅の道路とならなくなる。

また、学習経路適用部１０７は、探索条件として「距離優先」が設定されている場合には、いずれの学習経路も抽出しない。これは、ステップＳ２０４で探索された推奨経路は、出発地から目的地までの距離が短距離（例えば、最短距離）となる道路（リンク）が優先して選択されているためである。仮に、学習経路で置き換えてしまうと、推奨経路は目的地まで短距離とならなくなる。

以上のように、学習経路適用部１０７は、探索条件に応じた種別情報４１４を有する学習経路（レコード４１５）を適用候補の学習経路として抽出する。もちろん、探索条件に応じた種別情報４１４を有する学習経路が、複数存在する場合には、複数の学習経路を抽出する。そして、抽出した学習経路をＲＡＭ２２等のメモリに記憶する。

図８に戻り、学習経路適用部１０７は、ステップＳ３０１で抽出した学習経路のうち、１つの学習経路を優先順位（例えば、走行回数）に基づいて選び出す（ステップＳ３０２）。例えば、学習経路適用部１０７は、最高回数である走行回数４１３を有するレコード４１５に対応する１つの学習経路を、適用候補の学習経路として特定する。

そして、学習経路適用部１０７は、ステップＳ３０１で抽出した学習経路から、適用不可の学習経路を削除する（ステップＳ３０３）。具体的には、学習経路適用部１０７は、ステップＳ３０２で特定した学習経路と同時には、同一の推奨経路に適用できない学習経路を削除する。つまり、学習経路適用部１０７は、逸脱地点または復帰地点の少なくとも１つが、ステップＳ３０２で特定した学習経路ａの逸脱地点から復帰地点までの間にある学習経路（ｂ、ｃ、ｄ）を削除する。さらに、ステップＳ３０２で特定した学習経路ａの逸脱地点と復帰地点の両方が、逸脱地点から復帰地点までの間にあるような学習経路ｅも削除する。ここで、逸脱地点の特定には、逸脱地点のリンクの開始ノード３２２や逸脱地点の座標などが用いられる。また、復帰地点の特定には、復帰地点のリンクの終了ノード３２２や復帰地点の座標などが用いられる。

続いて、学習経路適用部１０７は、他の適用候補となる学習経路が存在するか否か判定する（ステップＳ３０４）。具体的には、学習経路適用部１０７は、ステップＳ３０１で抽出した学習経路のうち、ステップ３０２で特定した学習経路とステップＳ３０３で削除された学習経路を除いて、なお残っている学習経路が存在するか否か調べる。そして、残っている学習経路が存在する場合に、他の適用候補となる学習経路が存在すると判定する。一方、残っている学習経路が存在しない場合に、他の適用候補となる学習経路は存在しないと判定する。

学習経路適用部１０７は、他の適用候補となる学習経路が存在すると判定した場合には（ステップＳ３０４；Ｙｅｓ）、処理をステップＳ３０２に戻す。そして、他の適用候補となる学習経路が無くなるまで、ステップＳ３０２からステップＳ３０４までの処理を繰り返し実行する。これにより、ステップＳ２０４で探索された１つの推奨経路に対して、適用可能な複数の学習経路を適用することができるようになる。

一方、学習経路適用部１０７は、他の適用候補となる学習経路が存在しないと判定した場合には（ステップＳ３０４；Ｎｏ）、処理をステップＳ３０５に移行する。

そして、学習経路適用部１０７は、ステップＳ３０２で特定した学習経路を、ステップＳ２０４で探索された推奨経路に対して適用する（ステップＳ３０５）。具体的には、学習経路適用部１０７は、ステップＳ２０４で探索された推奨経路の一部を、ステップＳ３０２で特定した学習経路で置き換える。そして、置き換え後の推奨経路（推奨経路を構成するリンクＩＤ３２１）をＲＡＭ２２等のメモリに格納する。

その後、学習経路適用部１０７は、本フローを終了し、処理をステップＳ２０６に移行する。

なお、上記したフローの各処理単位は、ナビゲーション装置１００の処理を理解容易にするために、主な処理内容に応じて分類したものである。処理ステップの分類の仕方や名称によって、本願発明が制限されることはない。ナビゲーション装置１００が行う処理は、さらに多くの処理ステップに分割することもできる。また、１つの処理ステップが、さらに多くの処理を実行してもよい。

また、上記の実施形態は、本発明の要旨を例示することを意図し、本発明を限定するものではない。多くの代替物、修正、変形例は当業者にとって明らかである。

例えば、上記実施形態では、経路探索部１０４は、候補となる１つの推奨経路を探索している。しかし、本発明は、これに限定されない。例えば、経路探索部１０４は、複数の推奨経路を探索（いわゆる、「複数ルート探索」）するようにしてもい。

複数ルート探索を行う場合、経路探索部１０４は、上記のステップＳ２０４において、ステップＳ２０２で設定された探索条件を満たす複数の推奨経路を探索する。

例えば、経路探索部１０４は、「第１の有料優先」の探索条件を満たす第１の推奨経路と、「第２の有料優先」の探索条件を満たす第２の推奨経路と、を探索する。

図１０（Ａ）は、２つの探索条件に基づいて探索された２つの推奨経路の例を実線で示す図である。図示するように、「第１の有料優先」の探索条件を満たす第１の推奨経路と、「第２の有料優先」の探索条件を満たす第２の推奨経路と、がそれぞれ表示される。

そして、学習経路適用部１０７は、ステップＳ２０４で探索したそれぞれの推奨経路に対して、ステップＳ２０５の処理（ステップＳ３０１からステップＳ３０５の処理）を施す。これにより、学習経路適用部１０７は、それぞれの推奨経路に対して、探索条件に応じた種別情報４１４を有する学習経路を適用する。

従って、学習経路適用部１０７は、図１０（Ａ）に示すように、それぞれの推奨経路に対して、互いに異なる学習経路（第１の学習経路、第２の学習経路）を適用することができる。

そして、経路誘導部１０５は、１つの学習経路を表示する場合と同様に、複数の学習経路（点線）について、他の経路と異なる色で表示するなどして強調表示する。これによって、ユーザは、どちらの推奨経路に従って目的地まで走行すればよいか、容易に選択することができるようになる。

これに対し、探索条件に応じた種別情報を有する学習経路を適用できない場合には、図１０（Ａ）に示すような推奨経路を表示することはできない。

図１０（Ｂ）は、探索条件に応じた種別情報を有する学習経路を適用できないときの表示例を示す図である。図示するように、それぞれの推奨経路（第１の推奨経路、第２の推奨経路）に対して同一の学習経路が適用されてしまう場合がある。その結果、１つの学習経路しか表示できなくなる。これでは、複数ルート探索を行った意味がなくなってしまう。

なお、複数ルート探索を行わない場合であっても、複数の推奨経路を探索するようにしてもよい。この場合、「第１の有料優先」の探索条件が設定されたときは、ユーザからの設定を受け付けずに「第２の有料優先」の探索条件を満たす第２の推奨経路を探索する。同様に、「第１の一般優先」の探索条件が設定されたときは、ユーザからの設定を受け付けずに「第２の一般優先」の探索条件を満たす第２の推奨経路を探索する。

１・・・演算処理部、２・・・ディスプレイ、３・・・記憶装置、４・・・音声入出力装置、５・・・入力装置、６・・・車速センサ、７・・・ジャイロセンサ、８・・・ＧＰＳ受信装置、９・・・ＦＭ多重放送受信装置、１０・・・ビーコン受信装置、２１・・・ＣＰＵ、２２・・・ＲＡＭ、２３・・・ＲＯＭ、２４・・・インターフェイス（Ｉ／Ｆ）、４１・・・マイクロフォン、４２・・・スピーカ、５１・・・タッチパネル、５２・・・ダイヤルスイッチ、１００・・・ナビゲーション装置、１０１・・・主制御部、１０２・・・入力受付部、１０３・・・表示処理部、１０４・・・経路探索部、１０５・・・経路誘導部、１０６・・・学習経路登録部、１０７・・・学習経路適用部、３１０・・・地図データ、３１１・・・メッシュＩＤ、３２０・・・リンクデータ、３２１・・・リンクＩＤ、３２２・・・開始ノード・終了ノード、３２３・・・道路種別、３２４・・・リンク長、３２５・・・リンク旅行時間、３２６・・・開始接続リンク・終了接続リンク、４００・・・学習経路情報、４１１・・・学習経路ＩＤ、４１２・・・リンクＩＤ、４１３・・・走行回数、４１４・・・種別情報、４１５・・・レコード。

Claims (8)

1. 経路探索装置であって、
   推奨経路から逸れて移動した区間の経路を学習経路として記憶しておく記憶手段と、
   推奨経路の探索条件を設定する設定手段と、
   前記探索条件に基づいて推奨経路を探索する推奨経路探索手段と、
   探索された推奨経路に対して適用可能な学習経路を前記記憶手段から選び出し、当該推奨経路に適用する適用手段と、
   前記学習経路が適用された推奨経路を表示する表示手段と、を備え、
   前記記憶手段は、
   前記学習経路とともに、当該学習経路の種別情報を記憶しておき、
   前記適用手段は、
   前記探索条件に応じた種別情報を有する学習経路を前記記憶手段から選び出す、
   ことを特徴とする経路探索装置。
2. 請求項１に記載の経路探索装置であって、
   前記記憶手段は、
   前記学習経路と、前記種別情報と、当該学習経路の優先順位と、を対応付けて記憶しており、
   前記適用手段は、
   前記探索条件に応じた種別情報を有する学習経路のうち、前記優先順位に基づいて学習経路を前記記憶手段から選び出す、
   ことを特徴とする経路探索装置。
3. 請求項１又は２に記載の経路探索装置であって、
   前記設定手段は、
   有料道路を優先して推奨経路を探索するための第１の条件、又は、一般道路を優先して推奨経路を探索するための第２の条件を、前記探索条件として設定し、
   前記記憶手段は、
   少なくとも有料道路、一般道路を示す情報を前記種別情報として記憶し、
   前記適用手段は、
   前記第１の条件が探索条件として設定されている場合には、有料道路又は一般道路の種別情報を有する学習経路を前記記憶手段から選び出し、
   前記第２の条件が探索条件として設定されている場合には、一般道路の種別情報を有する学習経路を前記記憶手段から選び出す、
   ことを特徴とする経路探索装置。
4. 請求項３に記載の経路探索装置であって、
   前記記憶手段は、
   少なくとも有料道路、一般道路、細道路を示す情報を前記種別情報として記憶し、
   前記適用手段は、
   前記第１の条件が探索条件として設定されている場合には、有料道路、一般道路、又は、細道路の種別情報を有する学習経路を前記記憶手段から選び出し、当該学習経路を、前記推奨経路探索手段で探索されている推奨経路に適用して第１の推奨経路を決定し、さらに、有料道路、一般道路、又は、細道路の種別情報を有する学習経路のうち、前記第１の推奨経路に適用していない学習経路を前記記憶手段から選び出し、当該学習経路を、前記推奨経路に適用して第２の推奨経路を決定し、
   前記第２の条件が探索条件として設定されている場合には、一般道路又は細道路の種別情報を有する学習経路を前記記憶手段から選び出し、当該学習経路を、前記推奨経路探索手段で探索されている推奨経路に適用して第３の推奨経路を決定し、さらに、一般道路の種別情報を有する学習経路のうち、前記第３の推奨経路に適用していない学習経路を前記記憶手段から選び出し、当該学習経路を、前記推奨経路に適用して第４の推奨経路を決定し、
   前記表示手段は、
   前記第１の条件が探索条件として設定されている場合には、前記第１の推奨経路とともに前記第２の推奨経路を表示し、
   前記第２の条件が探索条件として設定されている場合には、前記第３の推奨経路とともに前記第４の推奨経路を表示する、
   ことを特徴とする経路探索装置。
5. 経路探索方法であって、
   演算処理装置が、推奨経路から逸れて移動した区間の経路を学習経路として記憶媒体に記憶しておく記憶ステップと、
   演算処理装置が、推奨経路の探索条件を設定する設定ステップと、
   演算処理装置が、前記探索条件に基づいて推奨経路を探索する推奨経路探索ステップと、
   演算処理装置が、探索された推奨経路に対して適用可能な学習経路を前記記憶媒体から選び出し、当該推奨経路に適用する適用ステップと、
   演算処理装置が、前記学習経路が適用された推奨経路を表示する表示ステップと、を有し、
   前記記憶ステップでは、
   前記学習経路とともに、当該学習経路の種別情報を記憶しておき、
   前記適用ステップでは、
   前記探索条件に応じた種別情報を有する学習経路を前記記憶媒体から選び出す、
   ことを特徴とする経路探索方法。
6. 請求項５に記載の経路探索方法であって、
   前記記憶ステップでは、
   前記学習経路と、前記種別情報と、当該学習経路の優先順位と、を対応付けて前記記憶媒体に記憶しており、
   前記適用ステップでは、
   前記探索条件に応じた種別情報を有する学習経路のうち、前記優先順位に基づいて学習経路を前記記憶媒体から選び出す、
   ことを特徴とする経路探索方法。
7. 請求項５又は６に記載の経路探索方法であって、
   前記設定ステップでは、
   有料道路を優先して推奨経路を探索するための第１の条件、又は、一般道路を優先して推奨経路を探索するための第２の条件を、前記探索条件として設定し、
   前記記憶ステップでは、
   少なくとも有料道路、一般道路を示す情報を前記種別情報として前記記憶媒体に記憶し、
   前記適用ステップでは、
   前記第１の条件が探索条件として設定されている場合には、有料道路又は一般道路の種別情報を有する学習経路を前記記憶媒体から選び出し、
   前記第２の条件が探索条件として設定されている場合には、一般道路の種別情報を有する学習経路を前記記憶媒体から選び出す、
   ことを特徴とする経路探索方法。
8. 請求項７に記載の経路探索方法であって、
   前記記憶ステップでは、
   少なくとも有料道路、一般道路、細道路を示す情報を前記種別情報として前記記憶媒体に記憶し、
   前記適用ステップでは、
   前記第１の条件が探索条件として設定されている場合には、有料道路、一般道路、又は、細道路の種別情報を有する学習経路を前記記憶媒体から選び出し、当該学習経路を、前記推奨経路探索手段で探索されている推奨経路に適用して第１の推奨経路を決定し、さらに、有料道路、一般道路、又は、細道路の種別情報を有する学習経路のうち、前記第１の推奨経路に適用していない学習経路を前記記憶媒体から選び出し、当該学習経路を、前記推奨経路に適用して第２の推奨経路を決定し、
   前記第２の条件が探索条件として設定されている場合には、一般道路又は細道路の種別情報を有する学習経路を前記記憶媒体から選び出し、当該学習経路を、前記推奨経路探索手段で探索されている推奨経路に適用して第３の推奨経路を決定し、さらに、一般道路の種別情報を有する学習経路のうち、前記第３の推奨経路に適用していない学習経路を前記記憶媒体から選び出し、当該学習経路を、前記推奨経路に適用して第４の推奨経路を決定し、
   前記表示ステップでは、
   前記第１の条件が探索条件として設定されている場合には、前記第１の推奨経路とともに前記第２の推奨経路を表示し、
   前記第２の条件が探索条件として設定されている場合には、前記第３の推奨経路とともに前記第４の推奨経路を表示する、
   ことを特徴とする経路探索方法。

Images