Notice: Undefined variable: fterm_desc_sub in /mnt/www/biblio_conv.php on line 353
ナビゲーションシステム、端末装置
説明

ナビゲーションシステム、端末装置

【課題】処理時間を抑制しながら適切な誘導経路を探索することができるナビゲーションシステムおよび端末装置を提案する。
【解決手段】地図データに通過頻度が高い地点についての情報を登録しておき、その地点の中から経由地を選択する。そして、選択された経由地を経由する出発地から目的地までの誘導経路を探索する。地点の通過頻度は、予め経路探索することによって得られた経路に含まれる回数および/または車両の走行履歴に基づいて設定する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ナビゲーションシステムおよび端末装置に関する。
【背景技術】
【0002】
特許文献1には、地図データをレベル0からレベル3までの四つのレベルに階層化し、出発地からレベル3の道路上の地点Aまでの経路と、目的地からレベル3の道路上の地点Bまでの経路と、地点Aから地点Bまでの経路とを探索する探索処理が記載されている。レベル3の地図データには、高速道路や国道などの主要道路だけが含まれており、地点Aから地点Bまでの経路についてはレベル3の道路だけを利用している。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2004−286524号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
出発地から目的地までの経路を探索するとき、必ずしも主要道路を主に利用した経路が最適な誘導経路となるとは限らない。特許文献1に記載の経路探索処理は、その点で必ずしも最適な誘導経路を与えるものとは言えなかった。本発明は、誘導経路を探索する処理の実行中に記憶するデータを抑制しつつ、適切な誘導経路を探索することができるナビゲーションシステムを提案することを目的とする。
【課題を解決するための手段】
【0005】
本発明のナビゲーションシステムは、出発地から目的地に至る誘導経路を探索するナビゲーションシステムであって、道路地図上の複数の地点の各々の位置情報と通過頻度とに関する情報とを少なくとも含む地図データを記憶する地図データ記憶手段と、出発地と目的地と通過頻度とに基づいて、経由地を選択する経由地選択手段と、経由地選択手段により選択された経由地を経由して、出発地から目的地までの誘導経路を探索する探索手段と、を備えることを特徴とする。
【発明の効果】
【0006】
本発明によれば、誘導経路を探索する処理の実行中に記憶するデータを抑制しつつ、適切な誘導経路を探索することができる。
【図面の簡単な説明】
【0007】
【図1】本発明の第1の実施の形態に係るナビゲーションシステムの全体構成を示すブロック図の一例である。
【図2】OD候補グループデータの一例を示す図である。
【図3】地図データのフォーマットの一例である。
【図4】地図データのフォーマットの一例である。
【図5】地図データのフォーマットの一例である。
【図6】地図データのフォーマットに含まれるOD候補グループデータを算出する処理に関するフローチャートの一例である。
【図7】地図データのフォーマットに含まれる頻度情報を算出する処理に関するフローチャートの一例である。
【図8】図7の処理の過程で算出されるデータのフォーマットの一例である。
【図9】図7の処理について説明するための具体例である。
【図10】探索判定手段の処理に関するフローチャートの一例である。
【図11】探索判定手段の処理時の表示画面の一例である。
【図12】経由地選択手段の処理に関するフローチャートの一例である。
【図13】探索判定手段の処理の出発地側と目的地側のOD候補グループを決定する処理に関するフローチャートの一例である。
【図14】探索判定手段の処理において出発地側のOD候補グループを決定する処理について説明するための図である。
【図15】探索判定手段の処理の複数の経由地候補を抽出する処理に関するフローチャートの一例である。
【図16】経由地候補として選択する条件を説明するための地図の一例である。
【図17】経由地選択手段の処理時の表示画面の一例である。
【図18】誘導経路探索後の表示画面の一例である。
【図19】本発明の第2の実施の形態に係るナビゲーションシステムを含むとセンタ装置の全体構成を示すブロック図の一例である。
【図20】データ蓄積手段が蓄積する走行履歴データのフォーマットの一例である。
【図21】経由地頻度更新手段の処理に関するフローチャートの一例である。
【図22】経由地頻度更新手段の実行例を示す図である。
【図23】本発明の第3の実施の形態に係るナビゲーションシステムの全体構成を示すブロック図の一例である。
【図24】経路選択手段の処理に関するフローチャートの一例である。
【図25】経由地学習手段の処理に関するフローチャートの一例である。
【図26】経由地学習手段の処理時の画面表示の一例である。
【図27】経由地学習手段の処理に関するフローチャートの一例である。
【発明を実施するための形態】
【0008】
本発明に係るナビゲーションシステムの実施の形態について、図面を参照して説明する。
【0009】
―第1の実施の形態―
本発明の第1の実施の形態に係るナビゲーションシステムの全体構成を図1に示す。図1のナビゲーションシステム100は、入力手段110、地図データ記憶手段120、探索判定手段130、経由地選択手段140、表示手段150、および探索手段160を備える。以降の説明では、ナビゲーションシステム100は車両用のカーナビゲーションシステム、またはカーナビゲーション用の端末装置であるものとして説明する。
【0010】
入力手段110は、ナビゲーションシステム100に対して、経路の出発地と目的地を入力する手段であって、タッチパネルや、ダイアル、各種スイッチなどのユーザインターフェースと、GPS(Global Positioning System)受信器や、角速度センサなど、車両の位置情報を検出するためのセンサ類とによって構成される。目的地は、ユーザインターフェースを介して入力される。出発地は、ユーザインターフェースまたはセンサ類を介して入力される。入力手段110を介して入力された出発地と目的地は、経由地選択手段140と、表示手段150と、探索手段160とへ提供される。
【0011】
センサ類を用いた出発地の入力方法について説明する。入力手段110を構成するセンサ類からの出力信号は、車両の位置や、角速度などを計測したものである。ナビゲーションシステム100は、これらの出力信号に対して公知の技術であるカルマンフィルタやデットレコニングを用いることにより、車両の位置情報を算出することができる。
【0012】
地図データ記憶手段120は、ハードディスク、フラッシュメモリ等の記憶手段で、道路情報と、POI(Point Of Interest)の情報と、各種アイコンなどの画像データとを記憶している。道路情報は道路データと、経由地データとOD候補グループデータで構成され、経由地選択手段140、表示手段150、探索手段160へ提供される。POIとは、店舗情報などの地点に関する情報である。ユーザは、入力手段110に含まれるユーザインターフェースを介して、住所、カテゴリ、電話番号等をキーとして目的地のPOIを地図データから検索し、目的地または出発地を入力することができる。道路情報については、その詳細を後述する。
【0013】
経由地選択手段140は、ナビゲーションシステム100に搭載されている不図示のマイクロプロセッサや、RAM、ROMなどによって実行されるソフトウェアである。経由地選択手段140は、入力手段110によって入力された出発地および目的地に基づいて、地図データ記憶手段120に記憶される複数のOD候補グループの中から、出発地および目的地から近いOD候補グループを選択し、選択したOD候補グループの中から経由地の候補を一つ以上(好ましくは二つ以上)選択し、選択した経由地の候補についての情報を表示手段150と探索手段160へ提供する。以下、経由地選択手段140より選択される経由地の候補のことを経由地候補と称する。
【0014】
OD候補グループとは、道路データに含まれる複数ノードを、それらのノード同士の距離でクラスタリング処理したときの集合体である。図2は、OD候補グループの一例を示す図である。図2中に実線で描かれている小円は道路データに含まれるノードを表す。図2中に点線で描かれている四つの円は、クラスタリング処理により得られたOD候補グループであり、それぞれG1〜G4というOD候補グループIDを有する。
【0015】
経由地選択手段140が選択した複数の経由地候補は、後述の表示手段150に表示される。経由地選択手段140はユーザインターフェースを含み、ユーザはユーザインターフェースを介して表示手段150に表示された複数の経由地候補の中から所望の経由地を一つまたは複数選択する。選択された経由地の情報は、探索手段160へ提供される。
【0016】
表示手段150は、液晶ディスプレイなどで構成され、二つの機能を備える。一つ目の機能は、経由地選択手段140による経由地の選択のため、地図データ記憶手段120に記憶されている道路情報と、経由地選択手段140からの経由地候補を表示する機能である。二つ目の機能は、地図データ記憶手段120の道路情報と、探索手段160から入力される誘導経路に関する情報とを入力とし、地図上に誘導経路を重ねて表示する機能である。
【0017】
探索手段160は、マイクロプロセッサや、RAM、ROMなどによって構成される。探索手段は二つの機能を備える。一つ目の機能(第1の経路探索)は、地図データ記憶手段120に記憶されている情報と、入力手段110から提供される目的地および出発地に基づいて、出発地から目的地までの誘導経路を公知なダイクストラ法により決定する。二つ目の機能(第2の経路探索)は、さらに経由地選択手段140から提供される一つ以上の経由地とに基づいて、出発地から経由地を経由して目的地に至るまでの誘導経路を公知なダイクストラ法などにより決定する。第1の経路探索は、その誘導経路に関する情報を探索判定手段130および表示手段150に提供する。第2の経路探索は、その誘導経路に関する情報を表示手段150に提供する。
【0018】
探索判定手段130は、ナビゲーションシステム100に搭載されている不図示のマイクロプロセッサや、RAM、ROMなどによって実行されるソフトウェアである。探索判定手段130は、探索手段160の第1の経路探索によって入力された経路に基づいて、経路が妥当かどうかを判定する。経路が妥当だと判定した場合、経路を表示手段150へ提供する。経路が妥当でないと判定した場合、経由地を選択するように経由地選択手段140へ命令する。また、経路が妥当かどうかを判定する処理は、ユーザが行ってもよい。この場合、探索判定手段130は、ユーザインターフェースを含み、ユーザはユーザインターフェースを介して表示手段150に表示された経路を見て、経路が妥当かどうかを判定する。
【0019】
次に、地図データ記憶手段120に記憶されている道路情報について図3〜5を用いて説明する。図3は、道路情報を構成する道路データのフォーマットの一例である。図4は、道路情報を構成するOD候補グループ毎の経由地データのフォーマットの一例である。図5は、OD候補グループデータのフォーマットの一例である。
【0020】
図3に示す道路データは、地図の区画であるメッシュ単位に分けられて地図データ記憶手段120に記憶されている。メッシュとは、地図を緯度・経度に基づいて網の目状に区画したものである。各メッシュを表す情報20は、それぞれを識別するためのメッシュIDと、そのメッシュに含まれる道路に関する道路に関する情報とで構成される。
【0021】
各メッシュに含まれる道路は、道路リンク単位で地図データ記憶手段120に記憶されている。各道路リンクを表す道路リンク情報21は、それぞれを識別するためのリンクIDと、各道路リンクの始点および終点の情報と、道路種別と、コストデータとで構成される。
【0022】
各道路リンクは方向を持っており、道路リンクの始点および終点の情報によってその方向と地図上の位置が特定できる。道路リンクの始点および終点には、それぞれが地点を表すノードがあり、始点および終点の情報は、それぞれノードを識別するノードIDと、ノードの位置を表す緯度および経度の情報で構成される。
【0023】
道路種別とは、各道路リンクが表す道路の種類を表す情報である。たとえば、道路リンクが表す道路が都市間高速道の場合は「0」、都市内高速道の場合は「1」、国道の場合は「2」、そのほかの道路の場合は「3」といったように定義される。そのほかの道路とは、たとえば細街路である。
【0024】
コストデータとは、探索手段160が経路探索時に使用する道路リンクの重みであり、始点から終点までの移動に要するコストを表す。コストデータには、統計交通情報や、リンク長、旅行時間など、様々な種類がある。以下の説明では、コストデータはリンク長があるものとして説明する。探索手段160がリンク長をコストデータとして経路探索する場合、探索される誘導経路は出発地から目的地までの走行距離が最小の経路となる。
【0025】
図4に示す経由地データは、出発地側のOD候補グループ単位に分けられて地図データ記憶手段120に記憶されている。出発地側のOD候補グループ、目的地側のOD候補グループについては、図7のフローチャートの説明時に説明する。各OD候補グループを表す情報22は、それぞれを識別するためのOD候補グループIDを持つ。このOD候補グループIDは、出発地側のOD候補グループIDである。さらに、情報22は、出発地側のOD候補グループと目的地側のOD候補グループとの組み合わせで決まる経由地に関するノード情報23の集合として構成される。
【0026】
ノード情報23は、各ノードを識別するためのノードIDと、各ノードに対応する地点の緯度および経度と、各ノードに対応する地点にある交差点の交差点名称と、各ノードを通過する頻度の高低を表す頻度情報とで構成される。頻度情報は、予め道路データを使用して算出されたデータであって、後述する経由地選択手段140の処理に用いられる。
【0027】
図5に示すOD候補グループデータは、OD候補グループ単位に分けられて地図データ記憶手段120に記憶されている。各OD候補グループを表す情報24は、それぞれを識別するためのOD候補グループIDと、そのOD候補グループを構成するノードに関するノード情報25で構成される。ノード情報25は、各ノードを識別するためのノードIDで構成される。
【0028】
図4の経由地データのノードIDと図5のOD候補グループデータのノードIDは、図3の道路データのノードIDと対応している。このため、道路データのノードIDをキーに、経由地データ内の対応するノード情報23や、OD候補グループデータ内の対応するノード情報25を検索することができる。
【0029】
OD候補グループデータに含まれるOD候補グループを作成する方法について図6に示すフローチャートを用いて説明する。図6は、ナビゲーションシステムの製造メーカや地図データベンダなどがナビゲーションシステムの工場出荷前などにサーバを用いて実行する処理である。図6の処理を行うサーバは、地図データ記憶手段120と、二つのノード間の推奨経路を公知なダイクストラ法などで探索する推奨経路探索手段と、ノード間の距離の短いノードの組み合わせを探して複数のクラスタにまとめる公知なクラスタリングと、ナビゲーションシステム100の地図データ記憶手段120に記憶されているOD候補グループデータにOD候補グループを構成するノードIDを書き込む書込手段とを備える。
【0030】
図6の処理では、サーバは、道路データの道路リンク情報21に含まれる、特定の道路種別の始点のノードと終点のノードのすべての組み合わせについて経路探索処理を行い、ノード間の経路長を使ってノードをクラスタリングして、OD候補グループに関する情報を算出する。
【0031】
図6のステップS001では、サーバは、地図データ記憶手段120に記憶されている道路データに含まれる道路リンクの道路リンク情報21の始点の情報と、終点の情報から、特定の道路種別のノードを抽出する。このとき、特定の道路種別とは、高速道や国道などの主要な道路の種別を指す。この主要な道路が接続しているノードを抽出することで、図6の処理の効率化を図ることができる。この道路種別は、メッシュ毎に決められる。主要なノードを抽出した後、ステップS002に進む。
【0032】
図6のステップS002では、サーバは、ステップS001で抽出された主要なノード間の経路長を用いて、主要なノードをクラスタリングする。このクラスタリング処理によって、生成されるノードの集合がOD候補グループとなる(たとえば、図2のOD候補グループG1〜G4)。サーバは、これらのOD候補グループを識別するためにOD候補グループIDを設定する。そして、サーバは、OD候補グループを表す情報24として、クラスタに設定されたOD候補グループIDと、そのクラスタを構成するノードIDのノード情報25を地図データ記憶手段120のOD候補グループデータへ書き込む。サーバは、算出したOD候補グループデータを格納したら、図6の処理を終了する。また、ステップS002のクラスタリングは、主要なノード間の経路長の代わりに主要なノード間の直線距離を使用してクラスタリングすることにしてもよい。
【0033】
経由地データに含まれる頻度情報を算出する方法について図7に示すフローチャートを用いて説明する。図7は、ナビゲーションシステムの製造メーカや地図データベンダなどがナビゲーションシステムの工場出荷前などにサーバを用いて実行する処理である。図7の処理を行うサーバは、地図データ記憶手段120と、二つのノード間の推奨経路を公知なダイクストラ法などで探索する推奨経路探索手段と、ナビゲーションシステム100の地図データ記憶手段120に記憶されている経由地データに頻度情報を書き込む書込手段とを備える。書込手段は、有線通信や、無線通信、各種記録メディアなどにより、ナビゲーションシステム100の地図データ記憶手段120の経由地データに頻度情報をアップロードする。
【0034】
図7の処理では、サーバは、OD候補グループデータのOD候補グループ情報24に含まれるノードのすべての組み合わせについて経路探索処理を行い、探索の結果得られた複数の経路を統計処理し、経由地データに含まれる各ノードに関する頻度情報を算出する。
【0035】
図7のステップS80では、サーバは、地図データ記憶手段120に記憶されているOD候補グループデータに含まれているOD候補グループ情報24のすべてについて、ステップS90からステップS140の処理を終了したか否かを判定する。図7の処理は、ステップS80の処理が肯定判定された場合はステップS150に進み、否定判定された場合はステップS90に進む。
【0036】
図7のステップS90では、サーバは、地図データ記憶手段120に記憶されているOD候補グループデータに含まれているOD候補グループ情報24を一つ選択し、出発地側のOD候補グループとする。さらに、地図データ記憶手段120に記憶されているOD候補グループデータに含まれているOD候補グループ情報24について、出発地側のOD候補グループ以外から一つ選択し、目的地側のOD候補グループとする。
【0037】
図7のステップS100では、サーバは、地図データ記憶手段120に記憶されている出発地側のOD候補グループに含まれているノード情報25のすべてについて、ステップS140の処理を終了したか否かを判定する。図7の処理は、ステップS100の処理が肯定判定された場合はステップS80に進み、否定判定された場合はステップS110に進む。
【0038】
図7のステップS110では、サーバは、出発地側のOD候補グループからノード情報25を一つ選択し、選択されたノード情報25のノードIDを用いて、道路リンクの道路リンク情報21からノードの情報を取得する。以降、ステップS110で抽出されたノードの情報を出発地側のノードと称する。図7の処理は、出発地側のノードとする始点の情報を取得したらステップS120に進む。
【0039】
図7のステップS120では、サーバは、目的地側のOD候補グループに含まれているノード情報25のすべてについて、ステップS130からS140の処理を終了したか否かを判定する。図7の処理は、ステップS120が肯定判定された場合はステップS100に戻り、否定判定された場合はステップS130に進む。
【0040】
図7のステップS130では、サーバは、目的地側のOD候補グループからノード情報25を一つ選択し、選択されたノード情報25のノードIDを用いて、道路リンクの道路リンク情報21からノードの情報を取得する。以降、ステップS120で抽出されたノードの情報を目的地側のノードと称する。図7の処理は、目的地側のノードとする終点の情報を取得したらステップS140に進む。
【0041】
図7のステップS140では、サーバは、出発地側のノードから目的地側のノードまでの経路を、公知のダイクストラ法などを用いて一つ探索し、探索した経路に関する経路情報をサーバに備えられたRAMなどの記憶領域に蓄積する。経路情報は、図8のフォーマットで蓄積される。図8のフォーマットは、出発地側のOD候補グループのOD候補グループID45と目的地側のOD候補グループのOD候補グループID46と、出発地側のノードのノードID41と、目的地側のノードのノードID42と、経路に含まるノード数43と、出発地側のノードから目的地側のノードまでの間に通過する通過ノード44とからなる。図7の処理は、探索した経路の経路情報をRAMなどに蓄積したらステップS120に戻る。ステップS120に戻ると、サーバはステップS110で取得された出発地側のノードに対して、目的地側のノードとする次の終点の情報を取得する。このような処理を繰り返して、始点の情報と終点の情報とのすべての組み合わせについて経路を探索し、探索された経路の経路情報を蓄積する。
【0042】
図7のステップS150では、サーバは、図8の経路情報の中の出発地側のOD候補グループの同一のOD候補グループIDと、目的地側のOD候補グループの同一のOD候補グループIDが含まれるものを抽出し、その通過ノードのノードIDについて、通過ノードとして現れる同一のノードIDの個数をそれぞれ算出する。そして、サーバは、算出されたノードIDの個数を図4の経由地データの対応する出発地側のOD候補グループのOD候補グループIDと目的地側のOD候補グループのOD候補グループIDとノードIDの頻度情報へ書き込む。サーバは、算出されたノードIDの個数を経由地データの頻度情報として格納したら、図7の処理を終了する。
【0043】
図9は、図7のフローチャートの実行例を示す図である。サーバの地図データ記憶手段120に図9(a)に示す地図についての道路データと経由地データが記憶されているものとする。図9ではOD候補グループを二つ想定し、それぞれのOD候補グループIDはG5とG6とする。OD候補グループG5にはノードN1とノードN2が含まれ、OD候補グループG6にはノードN3とノードN4が含まれる。道路データには、道路リンクL1と道路リンクL2と道路リンクL3と道路リンクL4と道路リンクL5に関する道路リンク情報21が記憶されている。道路リンクL1は、ノードN1を始点としノードN2を終点とする。道路リンクL2は、ノードN2を始点としノードN3を終点とする。道路リンクL3は、ノードN2を始点としノードN4を終点とする。道路リンクL4は、ノードN3を始点としノードN4を終点とする。道路リンクL5は、ノードN4を始点としノードN1を終点とする。図9(a)の地図では、説明の簡略化のため、すべての道路リンクを一方通行の道路としている。図9(a)の地図に対して、図7の処理を行うと、出発地側のノードと目的地側のノードとの組み合わせは、4x3=12通りある。OD候補グループG5を出発地側のOD候補グループとし、OD候補グループG6を目的地側のOD候補グループとした場合、ノードN1とノードN2が出発地側のノード、ノードN3とノードN4が目的地側のノードとなる。また、OD候補グループG6を出発地側のOD候補グループとし、OD候補グループG5を目的地側のOD候補グループとした場合、ノードN3とノードN4が出発地側のノード、ノードN1とノードN2が目的地側のノードとなる。各ノードの組み合わせに対して探索した経路の経路情報を図9(b)に示す。図9(b)に示す経路情報には、通過ノード44としてノードN1は3個存在する。したがって、ノードN1の頻度情報は「3」となる。同様にノードN2〜N4の頻度情報は、それぞれ「3」、「0」、「3」となる。
【0044】
次に、探索判定手段130の処理について、図10に示すフローチャートを用いて説明する。図10の処理は、ナビゲーションシステム100のマイクロプロセッサによって実行され、探索手段160の第1の経路探索を介して、経路情報が入力されたとき処理を開始する。
【0045】
図10のステップS301では、マイクロプロセッサは、入力された経路情報に対応する経路のコストが所定の閾値以下か否かを判定する。この処理は、後述する図15のステップS2023と同様の処理である。マイクロプロセッサは、経路のコストが所定の閾値以下の場合、適切な経路が計算されたと判断して、ステップS301の処理を肯定判定する。そして、マイクロプロセッサは、処理をステップS303に進め、入力された経路情報を表示手段150へ提供し、図10の処理を終了する。一方、経路のコストが所定の閾値より大きい場合、マイクロプロセッサは、適切な経路が計算されなかったと判断して、ステップS301の処理を否定判定し、ステップS302に処理を進める。なお、ステップS301では、第1の経路探索が経路を計算できない場合についても、否定判定することにしてもよい。ステップS302では、マイクロプロセッサは、経由地選択手段140へ経由地を設定するように命令する。
【0046】
なお、図10のフローチャートでは、マイクロプロセッサが、経由地選択手段140による経由地の設定の必要性を判断していたが、探索判定手段130に含まれるユーザインターフェースを介して、ユーザに経路が適切か否かを判定させることで、経由地の設定の必要性を判断してもよい。この経路が適切か否かを判断する方法を、図11を用いて説明する。
【0047】
表示手段150は、探索手段160の第1の経路探索の出力結果の経路と、入力手段110を介して入力された出発地および目的地とに基づいて、出発地と目的地と経路とを表示可能な道路地図の描画用のデータを地図データ記憶手段120から取得する。そして、取得したデータに基づいて図11のような画面を表示する。図11には、道路地図と共に、出発地Sおよび目的地Gと、経路Kと、この経路でよいか否かを問うウィンドウW1が表示されている。探索判定手段130は、図11に示すように表示されたウィンドウW1の「Yes」ボタンおよび「No」ボタンから、入力手段110に含まれるユーザインターフェースを介して、経路が適切か否かを選択させる。ウィンドウW1の「Yes」ボタンが選択された場合、表示されている最適経路Kが適切なものとして最適経路Kをそのまま使用する。ウィンドウW1の「No」ボタンが選択された場合、図10のステップS302と同様に、マイクロプロセッサは、経由地選択手段140へ経由地を設定するように命令する。
【0048】
次に、経由地選択手段140の処理について、図12に示すフローチャートを用いて説明する。図12の処理は、ナビゲーションシステム100のマイクロプロセッサによって実行され経路判定手段130にて経由地の設定が必要であると判断されたときに処理を開始する。
【0049】
図12のステップS200では、マイクロプロセッサは、入力手段110により入力された出発地および目的地の位置に基づいて、出発地側のOD候補グループと目的地側のOD候補グループを決定する。ステップS200の詳細な処理を、図13に示すフローチャートを用いて説明する。さらに図13の処理の例を図14に示す。なお、図13の説明では、出発地側のOD候補グループを決定する処理について説明するが、目的地側のOD候補グループを決定する処理も図13のフローチャート中の「出発地側のOD候補グループ」を「目的地側のOD候補グループ」に置き換えることで実現できる。
【0050】
図13に示す処理を初めて実行するとき、マイクロプロセッサは、入力手段110により入力された出発地の位置に最も近いノードを開始点(図14のノードN11)に設定して、図3の道路データに基づいて公知のダイクストラ法を実行する。ダイクストラ法は、開始点となるノードから道路データに含まれる各ノードへの最小コストを算出する貪欲アルゴリズムである。ダイクストラ法では、最小コストが確定したノードの集合である確定集合と、最小コストが確定していないノードの集合である未確定集合とを変数として用いる。図14の例では、点線の楕円領域A1内のノードが確定集合に含まれ、実線の楕円領域A2内のノードN12〜N14が未確定集合に含まれるものとする。
【0051】
マイクロプロセッサは、開始点に設定されたノードの最小コストをゼロに設定し、開始点に設定されなかったノードについては各ノードの最小コストの初期値を無限大に設定する。そして、すべてのノードを未確定集合に含め、確定集合を空集合とする。ダイクストラ法では、未確定集合が空集合になるまで以下の処理を繰り返す。
(1)未確定集合に含まれるノードのうち、最小コストが最小のノードを検索する。
(2)(1)で検索されたノードを確定集合に含める。
(3)(1)で検索されたノードを始点とする各リンクについて、それらの終点のノードが未確定集合に含まれるとき、当該終点のノードの最小コストを当該リンクのコストデータと(1)で検索されたノードの最小コストとの和に変更する。
【0052】
以降、(2)で確定集合に含められたノードのことを確定ノードと称する。確定ノードは、(2)でノードが確定集合に含められるたびに更新され、最初は設定されていない。たとえば、図14において未確定集合に楕円領域A2内にあるノードN12〜ノードN14だけが含まれるとして、ノードN12の最小コストが未確定集合に含まれるノードの中で最小とする場合を例に用いて説明する。まず(1)においてノードN12が検索され、(2)においてノードN12が確定集合に含められる。そして、(3)においてノードN12を始点とするリンクL6およびL7について、それらのリンクの終点N13およびN14が未確定集合に含まれるため、ノードN13の最小コストはノードN12の最小コストとリンクL6のコストの和に更新され、ノードN14の最小コストはノードN12の最小コストとリンクL7のコストの和に更新される。
【0053】
図13のステップS2001では、マイクロプロセッサは、確定ノードを含むOD候補グループが、図5のOD候補グループデータのノード情報25に存在するか否かを判定する。図13の処理は、ステップ2001が肯定判定された場合はステップS2003へ進み、否定判定された場合はステップS2002へ進む。図13の処理が開始されてから一度も上記(2)の処理が実行されていないときも否定判定される。
【0054】
図13のステップS2002では、マイクロプロセッサは、上記(1)の処理を実行した後、(2)の処理を実行し、確定ノードを更新する。
【0055】
図13のステップS2003では、マイクロプロセッサは、図13のステップ2001で、図5のOD候補グループデータのノード情報25に存在すると判定した確定ノードを含むOD候補グループを、出発地側のOD候補グループに設定する。図14の例では、ノードN12を含むOD候補グループが出発地側のOD候補グループに設定される。
【0056】
図13のステップS2004では、確定集合と未確定集合とをRAMに一時記憶し、図13の処理を終了する。ステップS2004で記憶されたデータは、図10のステップS302で探索判定手段から経由地の設定命令があったときに使用される。
【0057】
図12のステップS201では、マイクロプロセッサは、図12のステップS200で決定した出発地側のOD候補グループと目的地側のOD候補グループのそれぞれのIDを使って、図4の経由地データから、該当する出発地側のOD候補グループと目的地側のOD候補グループとの組み合わせに対応するノード情報23の集合を抽出する。
【0058】
図12のステップS202は、図12のステップS201で抽出したノード情報23の集合の中から、探索手段160の第2の経路探索で使用する経由地を選択する。図12のステップS201で抽出した経由地データのノード情報23が一つしかない場合は、その経由地データを経由地として探索手段160の第2の経路探索へ提供する。図12のステップS201で抽出した経由地データのノード情報23が複数個ある場合は、たとえばノード情報23の頻度が最も高いノードを経由地として、探索手段160の第2の経路探索へ提供する。また、図15にフローチャートを示す処理により、実際に経路探索をして複数個の経由地候補を選定し、経由地候補の中から、入力手段110に含まれるユーザインターフェースを介して、経由地を選択させてもよい。
【0059】
図15のステップS2021では、マイクロプロセッサは、図12のステップ201で抽出したノードのうち、ステップS2022およびS2023の処理が行われていないノードから、最も頻度情報(図4)の値が大きいノードを一つ抽出する。図15の処理は、最も頻度情報の大きいノードを抽出したら、ステップS2022に進む。
【0060】
図15のステップS2022では、マイクロプロセッサは、ステップS2021で抽出したノードを経由地として設定し、出発地から経由地を経由して目的地に至る経路をダイクストラ法などに基づいて一つ探索する。図15の処理は、ステップS2021で抽出したノードを経由地とした経路探索が終わったらステップS2023に進む。
【0061】
図15のステップS2023では、マイクロプロセッサは、ステップS2022で探索した経路のコストが所定の閾値以下であるか否かを判定する。閾値の値は、たとえば、出発地と目的地との間の直線距離の定数倍(たとえば、3倍)とすればよい。図15の処理は、ステップS2022で探索した経路のコストが所定の閾値以下の場合はステップS2024に進み、ステップS2022で探索した経路のコストが所定の閾値より大きい場合はステップS2021に戻る。
【0062】
図15のステップS2024では、マイクロプロセッサは、ステップS2021で抽出したノードを経由地候補として選択する。図15の処理は、ステップS2021で抽出したノードを経由地候補として選択したらステップS2025に進む。
【0063】
図15のステップS2025では、マイクロプロセッサは、経由地候補として所定の個数(たとえば、3個)のノードが選択されたか否かを判定する。マイクロプロセッサは、所定の個数のノードが抽出されているときは図15の処理を終了し、所定の個数未満のときはステップS2026に進む。
【0064】
図15のステップS2026では、マイクロプロセッサは、ステップS2021で抽出したノードがすべて処理された否かを判定する。マイクロプロセッサは、全てのノードが処理されたとき、図15の処理を終了し、まだ処理されていないノードがあるときは、ステップS2021へ戻る。
【0065】
図15のステップS2021からS2026までの処理について、図16の例を用いて説明する。図16には、出発地のノードNSおよび目的地のノードNGのほかにノードN5〜N10が示されている。図16では、ノードNSとノードNGとの間の直線距離が5L、ノードN5とノードN8との間のリンク長が4L、それ以外の図中のリンクのリンク長が3Lである。図16のノードN5〜N10のうち、ノードN5とノードN6の頻度情報が他のノードより大きい。ノードN6の位置は、ノードN5よりもノードNGに近いが、ノードN6とノードNGとの間に河川81などを挟んでおり、ノードN6からノードNGの地点に直接行くことはできない。
【0066】
ステップS2021においてノードN5が抽出されると、ステップS2022では、ノードNSから、ノードN5、ノードN8、ノードN9の順番にノードを通過してノードNGに至る経路が探索される。このとき、経路のコストは13Lとなる。ステップS2023において出発地と目的地との間の直線距離の3倍を閾値としている場合、経路のコスト「13L」はノードNSとノードNGとの間の直線距離「5L」の3倍以下であるため、ステップS205においてノードN5は経由地候補として選択される。
【0067】
ステップS2021においてノードN6が抽出されると、ステップS2022では、ノードNSから、ノードN6、ノードNS、ノードN5、ノードN8、ノードN9の順番にノードを通過してノードNGに至る経路が探索される。このとき、経路のコストは19Lとなる。ステップS204において出発地と目的地との間の距離の3倍を閾値としている場合、経路のコスト「19L」はノードNSとノードNGとの間の直線距離「5L」の3倍より大きいため、ステップS2024においてノードN6は経由地候補として選択されない。このように、実際に出発地から目的地までの経路を探索することにより、ノードN6のように遠回りする必要があるものを経由地候補として選択しないようにできる。
【0068】
なお、マイクロプロセッサは、図15のフローチャートを使用せずに、図4に示す経由地データのノード情報23の通過頻度の高い順に、複数の経由地候補を選んでもよい。
【0069】
次に、経由地選択手段140で複数個の経由地候補から、入力手段110に含まれるユーザインターフェースを介して、経由地を選択させる方法について図17を用いて説明する。図17は、経由地選択手段140で選択された複数の経由地候補を表示手段150に表示した例である。表示手段150は、経由地選択手段140で選択された経由地候補と、入力手段110を介して入力された出発地および目的地とに基づいて、出発地と、目的地と、経由地候補とを表示できる道路地図を描画するためのデータを地図データ記憶手段120から取得し、図17のように表示する。図17には、道路地図と共に、出発地Sおよび目的地Gと、経由地候補選択手段により選択された経由地候補K1と、経由地候補K2と、経由地候補K3とがアイコン付で表示されている。経由地候補K1〜K3の表示位置は、経由地データに含まれる緯度および経度によって特定する。アイコンの画像データなどは、地図データ記憶手段120から取得する。経由地選択手段140は、図17のように表示された経由地候補の中から、入力手段110に含まれるユーザインターフェースを介して、経由地を選択させる。なお、図17の例では、地図の下に経由地K1〜K3の交差点名称が経由地データに基づいて表示されている。これらの情報は、ポップアップなどによって強調する表示を行ってもよい。
【0070】
経由地選択手段140が行う処理を通して経由地が選択されると、探索手段160の第2の経路探索により出発地から経由地までの経路と、経由地から目的地までの経路が探索される。図18は、経由地選択手段140が行う処理を通して選択された経由地と、その経由地を経由する誘導経路を地図上に重ねて表示手段150に表示したものである。誘導経路は、探索手段160により探索される。なお、図18では誘導経路に加えて、目的地までのコストの情報と使用した経由地の情報を強調して表示している。
【0071】
なお、経由地選択手段140では、経由地を複数選択してもよい。経由地が複数選択された場合は、経由地間の経路も探索される。この場合、探索手段160の第2の経路探索は、探索された経路を出発地から経由地の経路、経由地から経由地の経路、経由地から目的地までの経路の順番に繋げることにより誘導経路を得る。
【0072】
―第2の実施の形態―
本発明の第2の実施の形態に係るナビゲーションシステムについて説明する。第2の実施の形態では、車両の走行履歴に基づいて頻度情報を決定する点が第1の実施の形態と大きく異なる。
【0073】
図19は、第2の実施の形態に係るナビゲーションシステムとセンタ装置からなる通信型ナビゲーションシステムのブロック図である。図19の通信型ナビゲーションシステム500は、センタ装置200とナビゲーションシステム300と通信回線網400とからなる。通信回線網400は、たとえばインターネット回線や携帯電話網などで構成される。
【0074】
センタ装置200は、複数の車両から送信される情報を収集して、収集した情報に基づいて経由地データの更新処理を行うサーバを備える設備である。図19のセンタ装置200は、データ収集手段210と、データ蓄積手段220と、経由地頻度更新手段230と、地図データ記憶手段120と、送信手段240とを備える。
【0075】
データ収集手段210は、通信回線網400を介して複数の車両の走行履歴の情報を収集し、データ蓄積手段220へ格納する。車両の走行履歴とは、車両が通過した地点に対応するノードに関するデータである。走行履歴の収集対象の車両は、通信装置(不図示)によってセンタ装置200と接続されている。この通信装置とは、携帯電話機や、無線LANモジュールなどであり、通信回線網400と接続する機能を有する。
【0076】
データ蓄積手段220は、ハードディスクや、フラッシュメモリなどの記憶手段であり、データ収集手段210で収集した車両の走行履歴を走行履歴データとして蓄積する。走行履歴データについては、その詳細を後述する。
【0077】
経由地頻度更新手段230は、サーバによって実行されるソフトウェアである。データ蓄積手段220に蓄積されている車両の走行履歴の情報を入力として、地図データ記憶手段120における経由地データの頻度情報を更新する。頻度情報を更新する更新タイミングは、所定の時間間隔で行う。たとえば、毎日0:00に1日おきに更新する場合、前日の0:00から新しく収集した走行履歴データを、データ蓄積手段220から抽出し、抽出した走行履歴データを使用して地図データ記憶手段120の経由地データの頻度情報を更新する。また、地図データ記憶手段120のバージョンが年度更新で新しくなった場合は、データ蓄積手段220に蓄積されているこれまでのデータを利用して、経由地データの頻度情報を計算する。
【0078】
送信手段240は、通信回線網400と有線または無線で接続しており、経由地頻度更新手段230によって更新された経由地データをナビゲーションシステム300へ送信する。送信するデータの構成は、地図データ記憶手段120の経由地データに準ずる。
【0079】
ナビゲーションシステム300は、入力手段110と、地図データ記憶手段120と、経由地選択手段140と、探索判定手段130と、表示手段150と、探索手段160と、受信手段260を備える。ナビゲーションシステム300の構成のうち、第1の実施の形態のナビゲーションシステム100と同じの符号の構成は、第1の実施の形態と同じものであり、その説明を省略する。
【0080】
受信手段260は、通信回線網400と無線で接続しており、センタ装置200の送信手段240が送信する更新後の経由地データを受信する。受信した経由地データは、地図データ記憶手段120に格納される。多くの車両の走行履歴に基づいて更新した最新の経由地データをセンタ装置200から取得することで、ナビゲーションシステム300は、信頼性の高い経由地データを使用できる。
【0081】
データ蓄積手段220が蓄積する走行履歴データについて、図20を用いて説明する。図20は、車両ごとの走行履歴データのフォーマットであり、このフォーマットに記載されるデータが各車両からセンタ装置200へ送信される。図20の走行履歴データは、車両を識別する車両ID121,車両が通過したノード数122、車両が通過した地点のノードのID123、そのノードID123の地点を通過した日時124で構成されている。このノードID123は、時系列順に並べられ記憶されており、通過日時が新しいノードID123ほど、後ろに記憶される。また、走行履歴データは、車両の1トリップ単位で記憶されている。この1トリップとは、車両がエンジンを掛けて、出発した地点から、目的地までの走行履歴をいう。
【0082】
以下、経由地頻度更新手段230の詳細について説明する。
【0083】
経由地頻度更新手段230の処理について、図21に示すフローチャートを用いて説明する。図21の処理は、所定の更新タイミングになったらセンタ装置200のサーバにより実行される。
【0084】
図21のステップS400では、センタ装置200のサーバは、前回の更新タイミング以降に新しくデータ蓄積手段220に蓄積された走行履歴データをすべて抽出する。走行履歴データの抽出処理が終了したらステップS401に進む。
【0085】
図21のステップS401では、センタ装置200のサーバは、ステップS400で抽出したすべての走行履歴データについて、経由地データの頻度情報を更新したか否かを判定する。センタ装置200は、ステップS400で抽出した走行履歴データについて経由地データの頻度情報を更新した場合は図21の処理を終了し、処理していない走行履歴データがある場合はステップS402に進む。
【0086】
図21のステップS402では、センタ装置200のサーバは、ステップS400で抽出した走行履歴データの中から一つの走行履歴データを選択する。図21の処理は、ステップS400で抽出した走行履歴データの中から一つ選択したらステップS403に進む。
【0087】
図21のステップS403では、センタ装置200のサーバは、ステップS402で選択した走行履歴データに含まれるノードIDをキーとして地図データ記憶手段120の経由地データを検索し、対応するノードIDの経由地データの頻度情報の値に「1」を加算することにより更新する。図21の処理は、頻度情報の更新が終了したらステップS401に戻る。
【0088】
図21の処理を図22に示す具体例を用いて説明する。図22の例では、図22(a)に示す走行履歴データに基づいて、経由地データの頻度情報を更新する。図22(a)の走行履歴データは、車両XがノードN1と、ノードN2と、ノードN3との三つのノードを通過したことを表している。図22(b)は、図22(a)の走行履歴データに基づいて、経由地データのノードN1と、ノードN2と、ノードN3の頻度情報に1が加算されることを示している。更新前のノードID「N1」の頻度情報は「10」であるのに対して、更新後のノードID「N1」の頻度情報は「11」になっている。ノードID「N2」と「N3」とについても同様である。ノードID「N4」の頻度情報は、図22(a)の走行履歴データに含まれていないため、更新されない。
【0089】
―第3の実施の形態―
本発明の第3の実施の形態に係るナビゲーションシステムについて説明する。第3の実施の形態では、ユーザインターフェースを介して入力された経由地の情報を学習することで、地図データの経由地データを更新していく点が第1の実施の形態、第2の実施の形態と大きく異なる。
【0090】
図23は、第3の実施の形態に係るナビゲーションシステムのブロック図である。図23のナビゲーションシステム600は、入力手段110、地図データ記憶手段120、探索判定手段130、経由地選択手段140、表示手段150、探索手段160、および経由地学習手段170を備える。ナビゲーションシステム400の構成のうち、第1の実施の形態のナビゲーションシステム100と同じの符号の構成の内、入力手段110、探索判定手段130、表示手段150、探索手段160は、第1の実施の形態と同じものであり、その説明を省略する。地図データ記憶手段120と経由地選択手段140は、第1の実施の形態と異なる点を説明する。
【0091】
地図データ記憶手段120のフォーマットは、図3〜図5と同様である。しかし、経由地学習手段170により経由地データが作成されるため、経由地学習手段170により、経由地データが追加されない限り、図4の経由地データのノード情報23は空である。ただし、図3の道路データおよび図5のOD候補グループデータは実施例1と同じである。
【0092】
経由地選択手段140は、ナビゲーションシステム600に搭載されている不図示のマイクロプロセッサや、RAM、ROMなどによって実行されるソフトウェアである。経由地選択手段140は、入力手段110によって入力された出発地および目的地に基づいて、地図データ記憶手段120に記憶される複数のOD候補グループの中から、出発地および目的地から近いOD候補グループを選択し、選択したOD候補グループの中から経由地の候補を一つ以上(好ましくは二つ以上)選択し、選択した経由地の候補についての情報を表示手段150と探索手段160へ提供する。このとき、地図データ記憶手段120の経由地データの該当するOD候補グループのノード情報23が存在しない場合、経由地学習手段170に、経由地を学習するように命じる。
【0093】
経由地選択手段140の処理について、図24に示すフローチャートを用いて説明する。図24の処理は、ナビゲーションシステム600のマイクロプロセッサによって実行される。図24のステップS200、ステップS201、ステップS202は、図12の同じ符号の処理と同様の処理であるため、説明を省略する。
【0094】
図24のステップS203では、マイクロプロセッサは、地図データ記憶手段120の経由地データ内に、出発地側のOD候補グループと目的地側のOD候補グループとの組み合わせに対応したノード情報23の集合があるか否かを判定する。図24の処理は、ステップS203で肯定判定された場合は、ステップS201へ進み、否定判定された場合はステップS204へ進む。
【0095】
図24のステップS204では、マイクロプロセッサは、経由地学習手段170へ、経由地データを学習するように命令し、出発地側のOD候補グループと、目的地側のOD候補グループのIDを経由地学習手段170へ提供し、処理を終了する。
【0096】
経由地学習手段170は、ナビゲーションシステム600に搭載されている不図示のマイクロプロセッサや、RAM、ROMなどによって実行されるソフトウェアである。経由地学習手段170は、ユーザインターフェースを含み、ユーザはユーザインターフェースを介して入力された経由地の情報を、地図データ記憶手段120の経由地データに書き込む。
【0097】
経由地学習手段170の処理について、図25に示すフローチャートを用いて説明する。図25の処理は、ナビゲーションシステム400のマイクロプロセッサによって実行される。
【0098】
図25のステップS500では、マイクロプロセッサは、ユーザインターフェースを介してユーザに経由地を入力させ、経由地に関する情報を取得する。以降、入力された経由地に関する情報のことを経由地情報と称し、その設定方法を、図26を用いて説明する。
【0099】
図26は、ユーザインターフェースを介してユーザに経由地を指定させるために表示手段150に表示させる画面の一例である。表示手段150は、入力手段110を介して入力された出発地および目的地に基づいて、出発地とおよび目的地を表示できる道路地図を描画するためのデータを地図データ記憶手段120から取得し、図26のような画面を表示する。図26には、道路地図と共に、出発地Sおよび目的地Gと、ユーザに経由地の設定を促すウィンドウW2が表示されている。ユーザがユーザインターフェースを介して、道路地図上の交差点を経由地として指定すると、マイクロプロセッサは、指定された交差点に対応するノードに関してノードID等の情報を道路データから取得する。こうして取得されたノードID等の情報が経由地情報となる。
【0100】
図25のステップS501では、マイクロプロセッサは、経由地選択手段140から入力された出発地側のOD候補グループIDおよび目的地側のOD候補グループIDと、経由地情報に含まれるノードIDとに基づいて、地図データ記憶手段120の経由地データのノード情報23を更新し、学習する。すなわち、経由地選択手段140から入力された出発地側のOD候補グループIDおよび目的地側のOD候補グループIDに対応する経由地データ22に新たにノード情報23を追加したり、既に記憶されているノード情報23の頻度情報に所定値(たとえば1)を加算したりする。この追加処理や加算処理等により、ユーザが経由地として設定した結果が経由地データの頻度情報として学習される。
【0101】
図25のステップS501における学習の詳細な処理フローを図27に示す。ステップS5011aでは、マイクロプロセッサは、経由地選択手段140により決定された出発地側のOD候補グループIDに対応するOD候補グループを表す情報22の中に、経由地選択手段により決定された目的地側のOD候補グループに対応するノード情報23の集合が存在するか否かを判定する。ステップS5011aが肯定判定された場合はステップS5011bに進み、ステップS5011aが否定判定された場合はステップS5013aに進む。
【0102】
ステップS5011bでは、マイクロプロセッサは、ステップS5011aで存在を確認したノード情報23の集合の中にステップS500で取得された経由地情報に含まれる
各ノードIDのノード情報23が存在するか否かを判定する。マイクロプロセッサは、そのノード情報23の集合の中に存在するノード情報23についてはステップS5012の処理を行い、そのノード情報23の集合の中に存在しないノード情報23についてはステップS5013bの処理を行う。
【0103】
ステップS5012では、マイクロプロセッサは、ステップS5011bにおいて存在が確認されたノード情報23の頻度情報を更新する。ノード情報23の頻度情報の更新は、たとえばそのノード情報23の頻度情報に所定値(たとえば1)を加算することで行う。
【0104】
ステップS5013aでは、マイクロプロセッサは、経由地選択手段140により決定された目的地側のOD候補グループのグループIDと、ステップS500で取得された経由地情報に含まれる各ノードIDにそれぞれ対応したノード情報23とを組み合わせて、経由地選択手段140により決定された出発地側のOD候補グループIDに対応するOD候補グループを表す情報22の中に追加する。
【0105】
ステップS5013bでは、マイクロプロセッサは、ステップS5011bにおいて存在しないと判定された経由地情報に含まれるノードIDのノード情報23を、経由地選択手段140により決定された目的地側のOD候補グループに対応するノード情報23の集合の中に追加する。
【0106】
以上で説明した各実施の形態によれば、次の作用効果を奏する。
【0107】
ナビゲーションシステム100、ナビゲーションシステム300、ナビゲーションシステム600は、地図データ記憶手段120に基づいて、出発地から1以上の経由地を経由して目的地に至る誘導経路を探索手段160が探索する。誘導経路を探索するための経由地は、地図データ記憶手段120に経由地データとして予め記憶されているノードに関するノード情報23のうち、頻度情報の値が大きいものが選択される。第1の実施の形態、第2の実施の形態、および第3の実施の形態では、探索判定手段130と、経由地選択手段140とにより経由地が選択される。これにより、ナビゲーションシステム100、ナビゲーションシステム300、およびナビゲーションシステム600は、誘導経路を探索する処理の実行中に記憶するデータを抑制しつつ、適切な誘導経路を探索することができる。ダイクストラ法などの経路探索方法では、処理の実行中に処理対象となるノードの数に依存したデータをRAMなどに記憶する必要がある。処理対象となるノードの数は出発地と目的地との間の距離が離れれば離れるほど増加する。各実施の形態のように、適切な経由地を出発地と目的地との間に挟むと、出発地と経由地までの距離や経由地と目的地までの距離は、出発地から目的地までの距離よりも短くなる。そのため、一度の経路探索(出発地から経由地や、経由地から目的地)における処理対象のノードの数は少なくなり、RAMなどに記憶するデータ量を低減できる。また、実際にすべてのノードについて経路探索した結果または走行履歴に基づいて、通過された頻度が高かったノードを経由地として設定するため、確実に適切な誘導経路を探索できる。
【0108】
頻度情報は、第1の実施形態では、図7に示すように、工場出荷前等に予め経路探索された結果に基づいて決定される。第2の実施形態では、経由地頻度更新手段230により車両の走行履歴に基づいて決定される。第3の実施形態では、ユーザがユーザインターフェースを介して設定した経由地に関する経由地情報に基づいて、経由地学習手段170が経由地データを更新し、頻度情報の学習を行う。
【0109】
以上で説明した各実施の形態は、次のように変形して実施できる。
【0110】
探索手段160などが経路を探索する方法は、ダイクストラ法だけに限定しない。たとえば、ベルマン・フォード法などを用いて経路を探索してもよい。
【0111】
探索手段160による誘導経路の探索の代わりに、図15のステップS2022で探索した経路の情報をRAMなどに記憶しておき、経由地が選択されたときにRAMから対応する経路の情報を読み出すことにしてもよい。また、探索手段160により誘導経路を探索する方法と、RAMに記憶した経路を読み出す方法とを併用してもよい。いずれの方法を採用するかは、経由地が二つ以上選択されたか否かに基づいて決定すればよい。ステップS2022で探索された経路は、経由地を一つ選択した場合であるため、二つ以上選択された場合には対応できないためである。
【0112】
図7のステップS110およびS130で始点の情報や終点の情報を取得する道路リンクを表す道路リンク情報21は、道路種別により限定してよい。たとえば、道路種別が「3」でないものに限定してよい。これにより、細街路など経路に含まれる可能性が極めて低い道路にしか繋がっていないノードについては、算出する必要がなくなるため、図3の処理を高速することができる。
【0113】
上記の各実施の形態および各変形例は、任意に組み合わせて実施してもよい。
【0114】
ナビゲーションシステム100およびナビゲーションシステム300およびナビゲーションシステム600は、車両用のものに限定しない。たとえば、携帯端末に徒歩用地図を表示する歩行者用のナビゲーションシステムやナビゲーション用の端末装置にも利用できる。第2の実施の形態の場合、GPS付の携帯端末であれば、車両ID121をユーザIDなどに変更した上で、走行履歴を送信することは可能である。
【0115】
以上で説明した各実施の形態や各種の変形例はあくまで一例であり、発明の特徴が損なわれない限り、本発明はこれらの内容に限定されない。
【符号の説明】
【0116】
100,300,600 ナビゲーションシステム
110 入力手段
120 地図データ記憶手段
130 探索判定手段
140 経由地選択手段
150 表示手段
160 探索手段
170 経由地学習手段
200 センタ装置
210 データ収集手段
220 データ蓄積手段
230 経由地頻度更新手段
240 送信手段
260 受信手段
400 通信回線網
500 通信型ナビゲーションシステム

【特許請求の範囲】
【請求項1】
出発地から目的地に至る誘導経路を探索するナビゲーションシステムであって、
道路地図上の複数の地点の各々の位置情報と通過頻度とに関する情報とを少なくとも含む地図データを記憶する地図データ記憶手段と、
前記出発地と前記目的地と前記通過頻度とに基づいて、経由地を選択する経由地選択手段と、
前記経由地選択手段により選択された経由地を経由して、前記出発地から前記目的地までの誘導経路を探索する探索手段と、を備えることを特徴とするナビゲーションシステム。
【請求項2】
請求項1に記載のナビゲーションシステムにおいて、
前記経由地選択手段は、
前記出発地の位置と前記目的地の位置とに基づいて定められる所定の領域内の地点を複数抽出する地点抽出手段と、
前記地点抽出手段により抽出された複数の地点の中から、前記通過頻度の値が大きい地点を経由地候補として1以上抽出する経由地候補抽出手段とを備え、
前記1以上の経由地候補の中から1以上の経由地を選択することを特徴とするナビゲーションシステム。
【請求項3】
請求項2に記載のナビゲーションシステムにおいて、
前記経由地候補抽出手段が抽出した1以上の経由地候補を画面に表示する経由地候補表示手段をさらに備え、
前記経由地選択手段は、前記経由地候補表示手段により前記画面に表示された経由地候補の中から、1以上の経由地を選択することを特徴とするナビゲーションシステム。
【請求項4】
請求項2または3に記載のナビゲーションシステムにおいて、
前記通過頻度は、前記地図データに位置情報が含まれる複数の地点の中から互いに異なる二つのノードをそれぞれ出発地と目的地に設定して経路を探索することを、出発地と目的地に設定する地点の組み合わせを変えて複数回実行し、探索された複数の推奨経路に当該複数のノードのそれぞれが含まれる回数を予め算出したものであることを特徴とするナビゲーションシステム。
【請求項5】
請求項2から4のいずれか一項に記載のナビゲーションシステムにおいて、
前記通過頻度は、前記地図データに位置情報が含まれる複数の地点が車両により通過された回数に基づいて更新されることを特徴とするナビゲーションシステム。
【請求項6】
請求項2から5のいずれか一項に記載のナビゲーションシステムにおいて、
前記通過頻度は、前記出発地から前記目的地までの誘導経路を探索する際に、前記地図データに位置情報が含まれる複数の地点の中から経由地としてユーザが設定した結果を学習することで、算出されることを特徴とするナビゲーションシステム。
【請求項7】
出発地から目的地に至る誘導経路を探索する端末装置であって、
道路地図上の複数の地点の各々の位置情報と通過頻度とに関する情報とを少なくとも含む地図データを記憶する地図データ記憶手段と、
前記出発地と前記目的地と前記通過頻度とに基づいて、経由地を選択する経由地選択手段と、
前記経由地選択手段により選択された経由地を経由して、前記出発地から前記目的地までの誘導経路を探索する探索手段と、を備える端末装置。
【請求項8】
請求項7に記載の端末装置において、
前記経由地選択手段は、
前記出発地の位置と前記目的地の位置とに基づいて定められる所定の領域内の地点を複数抽出する地点抽出手段と、
前記地点抽出手段により抽出された複数の地点の中から、前記通過頻度の値が大きい地点を経由地候補として1以上抽出する経由地候補抽出手段とを備え、
前記1以上の経由地候補の中から1以上の経由地を選択することを特徴とする端末装置。
【請求項9】
請求項8に記載の端末装置において、
前記経由地候補抽出手段が抽出した1以上の経由地候補を画面に表示する経由地候補表示手段をさらに備え、
前記経由地選択手段は、前記経由地候補表示手段により前記画面に表示された経由地候補の中から、1以上の経由地を選択することを特徴とする端末装置。
【請求項10】
請求項8または9に記載の端末装置において、
前記通過頻度は、前記地図データに位置情報が含まれる複数の地点の中から互いに異なる二つのノードをそれぞれ出発地と目的地に設定して経路を探索することを、出発地と目的地に設定する地点の組み合わせを変えて複数回実行し、探索された複数の推奨経路に当該複数のノードのそれぞれが含まれる回数を予め算出したものであることを特徴とする端末装置。
【請求項11】
請求項8から10のいずれか一項に記載の端末装置において、
前記通過頻度は、前記地図データに位置情報が含まれる複数の地点が車両により通過された回数に基づいて更新されることを特徴とする端末装置。
【請求項12】
請求項8から11のいずれか一項に記載の端末装置において、
前記通過頻度は、前記出発地から前記目的地までの誘導経路を探索する際に、前記地図データに位置情報が含まれる複数の地点の中から経由地としてユーザが設定した結果を学習することで、算出されることを特徴とする端末装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate


【公開番号】特開2013−101051(P2013−101051A)
【公開日】平成25年5月23日(2013.5.23)
【国際特許分類】
【出願番号】特願2011−244847(P2011−244847)
【出願日】平成23年11月8日(2011.11.8)
【出願人】(000001487)クラリオン株式会社 (1,722)
【Fターム(参考)】