(57)【要約】【課題】探索時間をなるべく抑えて、最適な推奨経路をユーザに提供する技術を提供する。【解決手段】ナビゲーション装置１００は、推奨経路を探索するために出発地及び目的地を受け付ける受付手段と、推奨経路についての探索エリアを設定する探索エリア設定手段と、探索エリア内から推奨経路を探索する経路探索手段と、を備える。ここで、探索エリア設定手段は、出発地から目的地までの連続するメッシュで構成されるメッシュ経路の探索を行い、探索されたメッシュ経路を構成するメッシュを探索エリアに含める。【選択図】図３
2011145189.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーション装置であって、
推奨経路を探索するために出発地及び目的地を受け付ける受付手段と、
前記推奨経路についての探索エリアを設定する探索エリア設定手段と、
前記探索エリア内から前記推奨経路を探索する経路探索手段と、を備え、
前記探索エリア設定手段は、
前記出発地から前記目的地までの連続するメッシュで構成されるメッシュ経路の探索を行い、探索されたメッシュ経路を構成するメッシュを前記探索エリアに含める、
ことを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置であって、
メッシュごとに代表値が定められており、
前記探索エリア設定手段は、
前記代表値をコストとして、前記メッシュ経路の探索を行う、
ことを特徴とするナビゲーション装置。
【請求項３】
請求項２に記載のナビゲーション装置であって、
メッシュごとに、一般道路についての第１の代表値と、有料道路についての第２の代表値と、が定められており、
前記受付手段は、
前記推奨経路を探索する探索条件をさらに受け付け、
前記探索エリア設定手段は、
前記受付手段で有料道路を優先する探索条件を受け付けている場合には、前記第１の代表値と、前記第２の代表値と、を用いて、前記メッシュ経路の探索を行い、
前記受付手段で一般道路を優先する探索条件を受け付けている場合には、前記第１の代表値のみ、を用いて、前記メッシュ経路の探索を行う、
ことを特徴とするナビゲーション装置。
【請求項４】
ナビゲーション装置における経路探索方法であって、
推奨経路を探索するために出発地及び目的地を受け付ける受付ステップと、
前記推奨経路についての探索エリアを設定する探索エリア設定ステップと、
前記探索エリア内から前記推奨経路を探索する経路探索ステップと、を有し、
前記探索エリア設定ステップでは、
前記出発地から前記目的地までの連続するメッシュで構成されるメッシュ経路の探索を行い、探索されたメッシュ経路を前記探索エリアに含める、
ことを特徴とする経路探索方法。
【請求項５】
コンピューターを、ナビゲーション装置として機能させるプログラムであって、
推奨経路を探索するために出発地及び目的地を受け付ける受付ステップと、
前記推奨経路についての探索エリアを設定する探索エリア設定ステップと、
前記探索エリア内から前記推奨経路を探索する経路探索ステップと、を前記コンピューターに実行させ、
前記探索エリア設定ステップでは、
前記出発地から前記目的地までの連続するメッシュで構成されるメッシュ経路の探索を行い、探索されたメッシュ経路を前記探索エリアに含める、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置、経路探索方法、および、プログラムに関する。
【背景技術】
【０００２】
一般的に、ナビゲーション装置では、ダイクストラ法等を用いて推奨経路が探索される。その際、２地点（例えば、出発地と目的地）の位置的関係から、推奨経路の探索範囲（以下では「探索エリア」という）は決定される。そして、決定された探索エリアに含まれているリンクの中から推奨経路が探索される（例えば、特許文献１）。このような探索方法を用いれば、地図データの全リンクから推奨経路を探索する場合と比較して、探索時間を短縮することができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平７−１７４５７２号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、探索エリア外に、最適な経路（例えば、最速の経路）が存在する場合もある。かかる場合には、最適な経路を推奨経路としてユーザに提供できない。
【０００５】
本発明は、探索時間をなるべく抑えて、最適な推奨経路をユーザに提供する技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を解決するための本願発明は、ナビゲーション装置であって、推奨経路を探索するために出発地及び目的地を受け付ける受付手段と、前記推奨経路についての探索エリアを設定する探索エリア設定手段と、前記探索エリア内から前記推奨経路を探索する経路探索手段と、を備え、前記探索エリア設定手段は、前記出発地から前記目的地までの連続するメッシュで構成されるメッシュ経路の探索を行い、探索されたメッシュ経路を構成するメッシュを前記探索エリアに含める。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態が適用されたナビゲーション装置の概略構成図である。
【図２】地図データの概略データ構造を示す図である。
【図３】演算処理部の機能ブロック図である。
【図４】（Ａ）基準探索エリアの一例を示す図である。（Ｂ）探索されたメッシュ経路の一例を示す図である。
【図５】（Ａ）基準探索エリアとメッシュ経路（拡張探索エリア）が合成されたエリアの一例を示す図である。（Ｂ）設定される探索エリアの一例を示す図である。
【図６】経路探索処理を示すフロー図である。
【発明を実施するための形態】
【０００８】
以下、本発明の実施形態の一例を図面を参照して説明する。
【０００９】
図１は、本発明の一実施形態が適用されたナビゲーション装置１００の概略構成図である。図示するように、ナビゲーション装置１００は、演算処理部１と、ディスプレイ２と、記憶装置３と、音声入出力装置４（マイクロフォン４１、スピーカ４２）と、入力装置５（タッチパネル５１、ダイヤルスイッチ５２）と、車速センサ６と、ジャイロセンサ７と、ＧＰＳ受信装置８と、を備えている。なお、ナビゲーション装置１００は、車両に載置されている車載用ナビゲーション装置としてもよいし、携帯電話やＰＤＡなどの携帯端末としてもよい。
【００１０】
演算処理部１は、様々な処理を行う中心的ユニットである。例えば、演算処理部１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ（Central Processing Unit）２１と、記憶装置３から読み出した地図データ、演算データなどを格納するＲＡＭ（Random Access Memory）２２と、プログラムやデータを格納するＲＯＭ（Read Only Memory）２３と、各種ハードウェアを演算処理部１に接続するためのＩ／Ｆ（インタフェース）２４と、を有する。そして、演算処理部１は、各デバイスをバス２５で相互に接続した構成からなる。そして、後述する各機能部（１０１〜１０５）は、ＣＰＵ２１がＲＡＭ２２などのメモリに読み出したプログラムを実行することで実現される。
【００１１】
例えば、演算処理部１は、各種センサ（６、７）やＧＰＳ受信装置８から出力される情報を基にして現在地を算出する。また、得られた現在地情報などに基づいて、表示に必要な地図データを記憶装置３から読み出す。また、読み出した地図データをグラフィック展開し、そこに現在地マーク（或いは、移動体の位置を示す移動体マーク）を重ねてディスプレイ２に表示する。
【００１２】
また、演算処理部１は、記憶装置３に記憶されている地図データの中から、推奨経路の探索範囲となる探索エリアを設定する。そして、演算処理部１は、設定された探索エリアに含まれている地図データを用いて、ユーザーから指示された出発地（又は演算処理部１で算出された現在地）と、目的地と、を結ぶ推奨経路を探索する。なお、演算処理部１は、上述した探索エリアを、必要に応じて拡張することができる。また、演算処理部１は、音声入出力装置４のスピーカ４２やディスプレイ２を用いてユーザーを誘導する。
【００１３】
ディスプレイ２は、演算処理部１で生成されたグラフィックス情報を表示するユニットである。ディスプレイ２は、液晶ディスプレイや有機ＥＬ（Electro-Luminescence）ディスプレイなどで構成される。
【００１４】
記憶装置３は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成される。この記憶媒体には、例えば、地図データ３１０、音声データ、動画データ、等が記憶されている。
【００１５】
図２は、地図データ３１０の概略データ構造を示す図である。図示するように、地図データ３１０は、地図上の区画された領域であるメッシュの識別コード（メッシュＩＤ）３１１ごとに、そのメッシュ領域に含まれている道路を構成する各リンクのリンクデータ３２０を含んでいる。
【００１６】
また、メッシュＩＤ３１１には、図示するように、各メッシュの代表値として、一般道路の平均旅行時間３１２と、有料道路の平均旅行時間３１３と、が対応付けて格納されている。ここで、一般道路の平均時間３１２は、例えば、メッシュ内に含まれている一般道路の各リンクに与えられた旅行時間（後述するリンク旅行時間３２５）を平均した値である。また、有料道路の平均時間３１３は、例えば、メッシュ内に含まれている有料道路の各リンクに与えられた旅行時間（リンク旅行時間３２５）を平均した値である。
【００１７】
リンクデータ３２０は、リンクの識別コード（リンクＩＤ）３２１ごとに、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３２２、リンクを含む道路の種別情報（例えば、一般道路、有料道路）を示す道路種別３２３、リンクの長さを示すリンク長情報３２４、リンク旅行時間３２５、２つのノードにそれぞれ接続するリンクの識別コード（接続リンクＩＤ）３２６、などを含んでいる。なお、ここでは、リンクを構成する２つのノードについて開始ノードと終了ノードを区別することで、道路の上り方向と下り方向を、それぞれ別のリンクとして管理することができる。
【００１８】
図１に戻り、音声入出力装置４は、音声入力装置としてマイクロフォン４１と、音声出力装置としてスピーカ４２と、を備える。マイクロフォン４１は、運転手やその他の搭乗者から発された音声などを取得する。スピーカ４２は、演算処理部１で生成された音声信号を出力する。これらのマイクロフォン４１とスピーカ４２は、車両の所定の部位に、別個に配置されている。
【００１９】
入力装置５は、ユーザーからの指示を受け付けるユニットである。入力装置５は、タッチパネル５１と、ダイヤルスイッチ５２と、その他のハードスイッチ（図示せず）であるスクロールキー、縮尺変更キーなどで構成される。また、入力装置５には、ナビゲーション装置１００に対して遠隔で操作指示を行うことができるリモートコントローラが含まれる。リモートコントローラは、ダイヤルスイッチやスクロールキー、縮尺変更キーなどを備え、各キーやスイッチが操作された情報をナビゲーション装置１００に送出することができる。
【００２０】
タッチパネル５１は、ディスプレイ２の表示面に貼られた透過性のある操作パネルである。タッチパネル５１は、ディスプレイ２に表示された画像のＸＹ座標と対応したタッチ位置を特定し、タッチ位置を座標に変換して出力する。タッチパネル５１は、感圧式または静電式の入力検出素子などにより構成される。
【００２１】
ダイヤルスイッチ５２は、時計回り及び反時計回りに回転可能に構成され、所定の角度の回転ごとにパルス信号を発生し、演算処理部１に出力する。演算処理部１では、パルス信号の数から、ダイヤルスイッチ５２の回転角度を求める。
【００２２】
車速センサ５、ジャイロセンサ７、及び、ＧＰＳ受信装置８は、移動体（ナビゲーション装置１００）の現在地（自車位置）などを算出するために使用される。車速センサ６は、車速を算出するために用いる車速データを出力するセンサである。ジャイロセンサ７は、光ファイバジャイロや振動ジャイロ等で構成され、移動体の回転による角速度を検出するものである。ＧＰＳ受信装置８は、ＧＰＳ衛星からの信号を受信し、移動体とＧＰＳ衛星間の距離とその距離の変化率を３個以上の衛星に対して測定することで、移動体の現在地や進行速度を測定する。
【００２３】
図３は、演算処理部１の機能ブロック図である。図示するように、演算処理部１は、主制御部１０１と、入力受付部１０２と、表示処理部１０３と、経路探索部１０４と、探索エリア設定部１０５と、を有する。
【００２４】
主制御部１０１は、演算処理部１の各部を統括して制御する処理を行う。
【００２５】
入力受付部１０２は、入力装置５に入力されたユーザーからの要求を受け付け、その要求内容を解析し、解析結果に応じたデータを主制御部１０１に通知する。例えば、入力受付部１０２は、ナビゲーション装置１００に、電源の投入、切断を指示する要求を受け付け、主制御部１０１に通知する。また、入力受付部１０２は、ナビゲーション装置１００が有する各種機能の設定（例えば、出発地、目的地の設定）に関する入力データを受け付け、主制御部１０１に通知する。
【００２６】
表示処理部１０３は、ディスプレイ２に、地図、探索された推奨経路、ユーザーに通知する各種メッセージ、等を表示させる。具体的には、表示処理部１０３は、ディスプレイ２に表示させるための描画コマンドを生成して通知する。なお、表示処理部１０３は、地図をディスプレイ２に表示させる際には、表示が要求された領域（例えば、推奨経路全体を表示するのに必要な領域）にある地図データを記憶装置３から抽出し、指定された描画方式で、道路、その他の地図構造物、現在地、目的地、推奨経路、等を描画するように地図コマンドを生成して主制御部１０１へ通知する。また、表示処理部１０３は、ディスプレイ２に表示させた地図上に、車両の位置を示す車両マークや各種設定画面などを表示するコマンドを生成して主制御部１０１へ通知する。
【００２７】
経路探索部１０４は、設定されている探索エリア内から、推奨経路を探索する処理を行う。具体的には、経路探索部１０４は、後述する探索エリア設定部１０５で設定された探索エリアの地図データ３１０を読み出す。そして、ダイクストラ法等を用いて、指定された２地点（出発地や現在地、目的地）間を結ぶ経路のコスト（例えば、総距離や総旅行時間）が最小となる経路を探索する。このとき、経路探索部１０４は、探索した推奨経路を構成する各リンクの識別コード（リンクＩＤ）３２１を、それぞれ対応付けてＲＡＭ２２等のメモリに記憶しておく。
【００２８】
探索エリア設定部１０５は、推奨経路の検索範囲となる探索エリアを設定する。
【００２９】
例えば、探索エリア設定部１０５は、探索エリアの設定に先立ち、指定された２地点（出発地、目的地）が含まれるエリア（以下では「基準探索エリア」という）を特定する。
【００３０】
図４（Ａ）は、基準探索エリアの一例を示す図である。図示するように、探索エリア設定部１０５は、例えば、出発地Ｓと目的地Ｇを結ぶ線分から所定距離内にあるメッシュを、基準探索エリアとして特定する。
【００３１】
また、探索エリア設定部１０５は、出発地から目的地までの連続するメッシュで構成されるメッシュ経路の探索（以下では、「メッシュ経路探索」という）を行う。
【００３２】
図４（Ｂ）は、探索されたメッシュ経路の一例を示す図である。探索エリア設定部１０５は、メッシュごとに与えられた平均旅行時間（３１２、３１３）を用いて、例えば、図示するような、出発地Ｓから目的地Ｇまでの連続するメッシュ経路（例えば、図中の１から１２までのメッシュ）を探索する。そして、探索エリア設定部１０５は、探索したメッシュ経路を拡張探索エリアとして特定する。なお、メッシュ経路の具体的な探索方法については後述する。
【００３３】
ここで、探索エリア設定部１０５は、基準探索エリアに、メッシュ経路（すなわち、拡張探索エリア）を含めたエリア（合成したエリア）を、探索エリアとして設定する。ただし、合成したエリアの外縁（最太線）より内側に、探索エリアとして設定されていないメッシュが存在する場合には、当該メッシュを探索エリアに含める。
【００３４】
図５（Ａ）は、基準探索エリアとメッシュ経路（拡張探索エリア）が合成されたエリアの一例を示す図である。図示するように、合成したエリアの外縁より内側に、探索エリアとして設定されていないメッシュが存在する場合がある。
【００３５】
図５（Ｂ）は、設定される探索エリアの一例を示す図である。図示するように、探索エリサ設定部１０５は、基準探索エリアを拡張したエリアを、探索エリアとして設定することができる。
【００３６】
また、図３には示していないが、演算処理部１は、経路誘導部を有していてもよい。例えば、経路誘導部は、経路探索部１０４によって探索された推奨経路を用いて経路誘導を行う。具体的には、経路誘導部は、表示処理部１０３を介して、ディスプレイ２に表示された地図の範囲に含まれている推奨経路を表示（強調表示）する。このとき、経路誘導部は、主制御部１０１で算出された現在地の情報に基づいて、移動体（車両）の現在地を示す移動体マーク（カーマーク）を推奨経路上に表示する。また、経路誘導部は、経路の情報と、主制御部１０１で算出された現在地の情報とを比較し、交差点等を通過する前に直進すべきか、右左折すべきかを、ディスプレイ２に表示させるとともに、音声入出力装置４のスピーカ４２を用いて音声でユーザに知らせる。
【００３７】
次に、上記構成からなるナビゲーション装置１００の特徴的な動作について説明する。
【００３８】
＜特徴的な動作＞
図６は、ナビゲーション装置１００が行う処理を示すフローチャートである。
【００３９】
演算処理部１の主制御部１０１は、例えば、ユーザからの指示（入力受付部１０２で受け付けた指示）に基づいて、本処理を開始する。
【００４０】
主制御部１０１によって本処理が開始されると、入力受付部１０２は、経路探索のための設定を受け付ける（ステップＳ１０１）。具体的には、入力受付部１０２は、表示処理部１０３に設定画面をディスプレイ２に表示させ、出発地、目的地、探索条件、等の入力を受け付ける。
【００４１】
そして、入力受付部１０２は、受け付けた各データを解析し、解析結果に応じたデータを主制御部１０１に通知する。このとき、主制御部１０１は、入力受付部１０２から通知されたデータを設定値として登録する（ＲＡＭ２２等のメモリに格納する）。なお、出発地については、各種センサ（６、７）やＧＰＳ受信装置８から出力される情報を基にして検出された現在地を設定値として登録してもよい。
【００４２】
次に、探索エリア設定部１０５は、ステップＳ１０１で主制御部１０１によって登録された設定値に基づいて、メッシュ経路探索を行う（ステップＳ１０２）。
【００４３】
このメッシュ経路探索の処理において、探索エリア設定部１０５は、まず、ステップＳ１０１で登録された出発地と目的地が含まれるエリア（図４Ａ：基準探索エリア）の地図データ３１０を読み出す。
【００４４】
そして、探索エリア設定部１０５は、ステップＳ１０１で主制御部１０１によって登録された探索条件に基づいて、「有料道路」を優先して経路探索を行うのか、「一般道路」を優先して経路探索を行うのか判定する。
【００４５】
探索エリア設定部１０５は、「有料道路」を優先して経路探索を行うと判定した場合には、「有料道路」と「一般道路」の平均旅行時間（３１２、３１３）を用いて、メッシュ経路を探索する。具体的には、探索エリア設定部１０５は、基準探索エリアのメッシュ（メッシュＩＤ３１１）に対応付けられている、「一般道路」の平均旅行時間３１２と、「有料道路」の平均旅行時間３１３と、を特定する。そして、探索エリア設定部１０５は、メッシュごとに特定した２つの平均旅行時間（３１２、３１３）のうち、小さい値の平均旅行時間（３１２又は３１３）を読み出す。ここで、どちらかの平均旅行時間が存在しない場合には、存在する平均旅行時間を読み出す。その後、探索エリア設定部１０５は、メッシュごとに読み出した平均旅行時間（３１２又は３１３）をコストとし、ダイクストラ法などを用いて、その総和が最小となるメッシュ経路を探索する。すなわち、探索エリア設定部１０５は、「出発地が存在するメッシュ」から「目的地が存在するメッシュ」まで連続するメッシュのうち、平均旅行時間（３１２又は３１３）の総和が最小となるメッシュ経路（例えば、図４Ｂ）を探索する。
【００４６】
一方、探索エリア設定部１０５は、「一般道路」を優先して経路探索を行うと判定した場合には、「一般道路」の平均旅行時間３１２を用いて、メッシュ経路を探索する。具体的には、探索エリア設定部１０５は、基準探索エリアのメッシュ（メッシュＩＤ３１１）に対応付けられている、「一般道路」の平均旅行時間３１２のみを特定する。そして、探索エリア設定部１０５は、メッシュごとに特定した平均旅行時間３１２を読み出す。その後、探索エリア設定部１０５は、メッシュごとに読み出した平均旅行時間３１２の総和が最小となるメッシュ経路を探索する。すなわち、探索エリア設定部１０５は、「出発地が存在するメッシュ」から「目的地が存在するメッシュ」まで連続するメッシュのうち、平均旅行時間３１２の総和が最小となるメッシュ経路（例えば、図４Ｂ）を探索する。
【００４７】
続いて、探索エリア設定部１０５は、ステップＳ１０２で探索したメッシュ経路を用いて、探索エリアを設定する（ステップＳ１０３）。
【００４８】
具体的には、探索エリア設定部１０５は、ステップＳ１０２で読み出した基準探索エリアと、ステップＳ１０２で探索したメッシュ経路（拡張探索エリア）を合成する。そして、合成したエリア（例えば、図５Ａ、図５Ｂに示すエリア）を探索エリアとして設定する（具体的には、探索エリア設定部１０５は、合成したエリアを主制御部１０１に通知し、主制御部１０１は、通知されたエリアを探索エリアとしてＲＡＭ２２等のメモリに登録する）。
【００４９】
ただし、探索エリア設定部１０５は、図５Ａに示すように、合成したエリアの外縁（最太線）より内側に、探索エリアとして設定されていないメッシュ（無地のメッシュ）が存在するか否か判定する。
【００５０】
ここで、探索エリアとして設定されていないメッシュが、合成したエリア内に存在すると判定した場合には、探索エリア設定部１０５は、図５Ｂに示すように、探索エリアとして設定されていないメッシュを、探索エリアに含める。
【００５１】
一方、探索エリアとして設定されていないメッシュが、合成したエリア内に存在しないと判定した場合には、探索エリア設定部１０５は、合成したエリアをそのまま探索エリアとして設定する（具体的には、探索エリア設定部１０５は、合成したエリアを主制御部１０１に通知し、主制御部１０１は、通知されたエリアを探索エリアとしてＲＡＭ２２等のメモリに登録する）。
【００５２】
そして、探索エリア設定部１０５は、設定した探索エリア（例えば、探索エリアを構成するメッシュＩＤ３１１）を、メモリから読み出し、経路探索部１０４に通知する。
【００５３】
探索エリアが通知された経路探索部１０４は、通知された探索エリア内から、推奨経路を探索する（ステップＳ１０４）。その後、経路探索部１０４は、探索した推奨経路を主制御部１０１に通知する。このとき、主制御部１０１は、通知された推奨経路をＲＡＭ２２等のメモリに記憶し、本フローを終了する。
【００５４】
以上の処理を演算処理部１が行うことにより、本実施形態のナビゲーション装置１００は、従来の基準探索エリアよりも広域なエリアから、推奨経路を探索することができる。これにより、本実施形態のナビゲーション装置１００は、推奨経路の探索時間を抑えながらも、基準探索エリア外に存在する最適な推奨経路をユーザに提供することができるようになる。
【００５５】
なお、本発明は、上記実施形態に限定されず、種々の変形、応用が可能である。
【００５６】
例えば、上記実施形態では、推奨経路の探索に用いる地図データ３１０の縮尺については記載していない。本ナビゲーション装置１００は、推奨経路の探索時間をさらに低減させるために、ステップＳ１０３で設定する探索エリアが広域となる場合には、用いる地図データ３１０の縮尺レベルを変更（広域地図に変更）してもよい。この場合、経路探索部１０４は、変更された地図データ３１０を用いて、経路探索を行う。
【００５７】
また、上記実施形態では、「一般道路」を優先する探索条件と、「有料道路」を優先する探索条件が設定される場合について記載している。しかし、本発明で設定され得る探索条件は、これに限定されない。例えば、交通渋滞の程度を示す混雑度を探索条件として設定するようにしてもよい。この場合、演算処理部１は、混雑度を用いて、メッシュ経路の探索、推奨経路の探索を行うようにしてもよい。具体的には、混雑度を用いてメッシュ経路の探索を行う場合、探索エリア設定部１０５は、メッシュ経路の探索に先だち、上述した平均旅行時間（３１２、３１３）に、混雑度を乗算すればよい。そして、探索エリア設定部１０５は、混雑度が乗算された平均旅行時間（３１２、３１３）を用いて、メッシュ経路を探索する。これにより、本ナビゲーション装置１００は、交通渋滞が発生していないメッシュ経路を探索することができる。
【００５８】
また、上記実施形態では、「一般道路」の平均旅行時間３１２と、「有料道路」の平均旅行時間３１３を用いて、メッシュ経路の探索をしている。しかし、本発明は、これに限定されない。本発明の探索エリア設定部１０５は、メッシュごとに定められている代表値をコストとして用い、メッシュ経路の探索を行う。従って、当該代表値には、上述した平均旅行時間（３１２、３１３）の代わりに、例えば、平均リンク長が用いられてもよい。ここで、平均リンク長とは、メッシュ内に含まれている各リンクに与えられたリンク長３２４を平均した値である。
【符号の説明】
【００５９】
１・・・演算処理部、２・・・ディスプレイ、３・・・記憶装置、４・・・音声入出力装置、５・・・入力装置、６・・・車速センサ、７・・・ジャイロセンサ、８・・・ＧＰＳ受信装置、２１・・・ＣＰＵ、２２・・・ＲＡＭ、２３・・・ＲＯＭ、２４・・・インターフェイス（Ｉ／Ｆ）、４１・・・マイクロフォン、４２・・・スピーカ、５１・・・タッチパネル、５２・・・ダイヤルスイッチ、１００・・・ナビゲーション装置、１０１・・・主制御部、１０２・・・入力受付部、１０３・・・表示処理部、１０４・・・経路探索部、１０５・・・探索エリア設定部、３１０・・・地図データ、３１１・・・メッシュＩＤ、３１２・・・平均旅行時間（一般道路）、３１３・・・平均旅行時間（有料道路）、３２０・・・リンクデータ、３２１・・・リンクＩＤ、３２２・・・開始ノード・終了ノード、３２３・・・道路種別、３２４・・・リンク長、３２５・・・リンク旅行時間、３２６・・・開始接続リンク・終了接続リンク
【図１】
2011145189.tif 000003
【図２】
2011145189.tif 000004
【図３】
2011145189.tif 000005
【図４】
2011145189.tif 000006
【図５】
2011145189.tif 000007
【図６】
2011145189.tif 000008