JP5856813B2 - ナビゲーションシステム、端末装置 - Google Patents

Description

本発明は、ナビゲーションシステムおよび端末装置に関する。

特許文献１には、地図データをレベル０からレベル３までの四つのレベルに階層化し、出発地からレベル３の道路上の地点Ａまでの経路と、目的地からレベル３の道路上の地点Ｂまでの経路と、地点Ａから地点Ｂまでの経路とを探索する探索処理が記載されている。レベル３の地図データには、高速道路や国道などの主要道路だけが含まれており、地点Ａから地点Ｂまでの経路についてはレベル３の道路だけを利用している。

特開２００４−２８６５２４号公報

出発地から目的地までの経路を探索するとき、必ずしも主要道路を主に利用した経路が最適な誘導経路となるとは限らない。特許文献１に記載の経路探索処理は、その点で必ずしも最適な誘導経路を与えるものとは言えなかった。本発明は、誘導経路を探索する処理の実行中に記憶するデータを抑制しつつ、適切な誘導経路を探索することができるナビゲーションシステムを提案することを目的とする。

本発明に係るナビゲーションシステムは、出発地から目的地に至る誘導経路を探索するナビゲーションシステムであって、道路地図上における複数のノードの位置情報と、前記ノードの通過頻度とに関する情報とを少なくとも含む地図データを記憶する地図データ記憶手段と、前記出発地と前記目的地と前記通過頻度とに基づいて、経由地を選択する経由地選択手段と、前記経由地選択手段により選択された経由地を経由して、前記出発地から前記目的地までの誘導経路を探索する探索手段とを有しており、前記経由地選択手段は、前記出発地の位置に最も近いノードと前記目的地の位置に最も近いノードとに基づいて定められる所定の領域内のノードを複数抽出する地点抽出手段と、前記地点抽出手段により抽出された複数のノードの中から、前記通過頻度の値が大きいノードを経由地候補として１以上抽出する経由地候補抽出手段とを備え、前記１以上の経由地候補の中から１以上の経由地を選択するに際して、前記通過頻度は、前記地図データに位置情報が含まれる複数のノードの中から互いに異なる二つのノードをそれぞれ出発地と目的地に設定して経路を探索することを、出発地と目的地に設定するノードの組み合わせを変えて複数回実行し、探索された複数の推奨経路に当該複数のノードのそれぞれが含まれる回数を予め算出したものである、ことを特徴とする。
本発明に係る端末装置は、出発地から目的地に至る誘導経路を探索する端末装置であって、道路地図上における複数のノードの位置情報と、前記ノードの通過頻度とに関する情報とを少なくとも含む地図データを記憶する地図データ記憶手段と、前記出発地と前記目的地と前記通過頻度とに基づいて、経由地を選択する経由地選択手段と、前記経由地選択手段により選択された経由地を経由して、前記出発地から前記目的地までの誘導経路を探索する探索手段とを有しており、前記経由地選択手段は、前記出発地の位置に最も近いノードと前記目的地の位置に最も近いノードとに基づいて定められる所定の領域内のノードを複数抽出する地点抽出手段と、前記地点抽出手段により抽出された複数のノードの中から、前記通過頻度の値が大きいノードを経由地候補として１以上抽出する経由地候補抽出手段とを備え、前記１以上の経由地候補の中から１以上の経由地を選択するに際して、前記通過頻度は、前記地図データに位置情報が含まれる複数のノードの中から互いに異なる二つのノードをそれぞれ出発地と目的地に設定して経路を探索することを、出発地と目的地に設定するノードの組み合わせを変えて複数回実行し、探索された複数の推奨経路に当該複数のノードのそれぞれが含まれる回数を予め算出したものである、ことを特徴とする。

本発明によれば、誘導経路を探索する処理の実行中に記憶するデータを抑制しつつ、適切な誘導経路を探索することができる。

本発明の第１の実施の形態に係るナビゲーションシステムの全体構成を示すブロック図の一例である。 ＯＤ候補グループデータの一例を示す図である。 地図データのフォーマットの一例である。 地図データのフォーマットの一例である。 地図データのフォーマットの一例である。 地図データのフォーマットに含まれるＯＤ候補グループデータを算出する処理に関するフローチャートの一例である。 地図データのフォーマットに含まれる頻度情報を算出する処理に関するフローチャートの一例である。 図７の処理の過程で算出されるデータのフォーマットの一例である。 図７の処理について説明するための具体例である。 探索判定手段の処理に関するフローチャートの一例である。 探索判定手段の処理時の表示画面の一例である。 経由地選択手段の処理に関するフローチャートの一例である。 探索判定手段の処理の出発地側と目的地側のＯＤ候補グループを決定する処理に関するフローチャートの一例である。 探索判定手段の処理において出発地側のＯＤ候補グループを決定する処理について説明するための図である。 探索判定手段の処理の複数の経由地候補を抽出する処理に関するフローチャートの一例である。 経由地候補として選択する条件を説明するための地図の一例である。 経由地選択手段の処理時の表示画面の一例である。 誘導経路探索後の表示画面の一例である。 本発明の第２の実施の形態に係るナビゲーションシステムを含むとセンタ装置の全体構成を示すブロック図の一例である。 データ蓄積手段が蓄積する走行履歴データのフォーマットの一例である。 経由地頻度更新手段の処理に関するフローチャートの一例である。 経由地頻度更新手段の実行例を示す図である。 本発明の第３の実施の形態に係るナビゲーションシステムの全体構成を示すブロック図の一例である。 経路選択手段の処理に関するフローチャートの一例である。 経由地学習手段の処理に関するフローチャートの一例である。 経由地学習手段の処理時の画面表示の一例である。 経由地学習手段の処理に関するフローチャートの一例である。

本発明に係るナビゲーションシステムの実施の形態について、図面を参照して説明する。

―第１の実施の形態―
本発明の第１の実施の形態に係るナビゲーションシステムの全体構成を図１に示す。図１のナビゲーションシステム１００は、入力手段１１０、地図データ記憶手段１２０、探索判定手段１３０、経由地選択手段１４０、表示手段１５０、および探索手段１６０を備える。以降の説明では、ナビゲーションシステム１００は車両用のカーナビゲーションシステム、またはカーナビゲーション用の端末装置であるものとして説明する。

入力手段１１０は、ナビゲーションシステム１００に対して、経路の出発地と目的地を入力する手段であって、タッチパネルや、ダイアル、各種スイッチなどのユーザインターフェースと、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）受信器や、角速度センサなど、車両の位置情報を検出するためのセンサ類とによって構成される。目的地は、ユーザインターフェースを介して入力される。出発地は、ユーザインターフェースまたはセンサ類を介して入力される。入力手段１１０を介して入力された出発地と目的地は、経由地選択手段１４０と、表示手段１５０と、探索手段１６０とへ提供される。

センサ類を用いた出発地の入力方法について説明する。入力手段１１０を構成するセンサ類からの出力信号は、車両の位置や、角速度などを計測したものである。ナビゲーションシステム１００は、これらの出力信号に対して公知の技術であるカルマンフィルタやデットレコニングを用いることにより、車両の位置情報を算出することができる。

地図データ記憶手段１２０は、ハードディスク、フラッシュメモリ等の記憶手段で、道路情報と、ＰＯＩ（Ｐｏｉｎｔ Ｏｆ Ｉｎｔｅｒｅｓｔ）の情報と、各種アイコンなどの画像データとを記憶している。道路情報は道路データと、経由地データとＯＤ候補グループデータで構成され、経由地選択手段１４０、表示手段１５０、探索手段１６０へ提供される。ＰＯＩとは、店舗情報などの地点に関する情報である。ユーザは、入力手段１１０に含まれるユーザインターフェースを介して、住所、カテゴリ、電話番号等をキーとして目的地のＰＯＩを地図データから検索し、目的地または出発地を入力することができる。道路情報については、その詳細を後述する。

経由地選択手段１４０は、ナビゲーションシステム１００に搭載されている不図示のマイクロプロセッサや、ＲＡＭ、ＲＯＭなどによって実行されるソフトウェアである。経由地選択手段１４０は、入力手段１１０によって入力された出発地および目的地に基づいて、地図データ記憶手段１２０に記憶される複数のＯＤ候補グループの中から、出発地および目的地から近いＯＤ候補グループを選択し、選択したＯＤ候補グループの中から経由地の候補を一つ以上（好ましくは二つ以上）選択し、選択した経由地の候補についての情報を表示手段１５０と探索手段１６０へ提供する。以下、経由地選択手段１４０より選択される経由地の候補のことを経由地候補と称する。

ＯＤ候補グループとは、道路データに含まれる複数ノードを、それらのノード同士の距離でクラスタリング処理したときの集合体である。図２は、ＯＤ候補グループの一例を示す図である。図２中に実線で描かれている小円は道路データに含まれるノードを表す。図２中に点線で描かれている四つの円は、クラスタリング処理により得られたＯＤ候補グループであり、それぞれＧ１〜Ｇ４というＯＤ候補グループＩＤを有する。

経由地選択手段１４０が選択した複数の経由地候補は、後述の表示手段１５０に表示される。経由地選択手段１４０はユーザインターフェースを含み、ユーザはユーザインターフェースを介して表示手段１５０に表示された複数の経由地候補の中から所望の経由地を一つまたは複数選択する。選択された経由地の情報は、探索手段１６０へ提供される。

表示手段１５０は、液晶ディスプレイなどで構成され、二つの機能を備える。一つ目の機能は、経由地選択手段１４０による経由地の選択のため、地図データ記憶手段１２０に記憶されている道路情報と、経由地選択手段１４０からの経由地候補を表示する機能である。二つ目の機能は、地図データ記憶手段１２０の道路情報と、探索手段１６０から入力される誘導経路に関する情報とを入力とし、地図上に誘導経路を重ねて表示する機能である。

探索手段１６０は、マイクロプロセッサや、ＲＡＭ、ＲＯＭなどによって構成される。探索手段は二つの機能を備える。一つ目の機能（第１の経路探索）は、地図データ記憶手段１２０に記憶されている情報と、入力手段１１０から提供される目的地および出発地に基づいて、出発地から目的地までの誘導経路を公知なダイクストラ法により決定する。二つ目の機能（第２の経路探索）は、さらに経由地選択手段１４０から提供される一つ以上の経由地とに基づいて、出発地から経由地を経由して目的地に至るまでの誘導経路を公知なダイクストラ法などにより決定する。第１の経路探索は、その誘導経路に関する情報を探索判定手段１３０および表示手段１５０に提供する。第２の経路探索は、その誘導経路に関する情報を表示手段１５０に提供する。

探索判定手段１３０は、ナビゲーションシステム１００に搭載されている不図示のマイクロプロセッサや、ＲＡＭ、ＲＯＭなどによって実行されるソフトウェアである。探索判定手段１３０は、探索手段１６０の第１の経路探索によって入力された経路に基づいて、経路が妥当かどうかを判定する。経路が妥当だと判定した場合、経路を表示手段１５０へ提供する。経路が妥当でないと判定した場合、経由地を選択するように経由地選択手段１４０へ命令する。また、経路が妥当かどうかを判定する処理は、ユーザが行ってもよい。この場合、探索判定手段１３０は、ユーザインターフェースを含み、ユーザはユーザインターフェースを介して表示手段１５０に表示された経路を見て、経路が妥当かどうかを判定する。

次に、地図データ記憶手段１２０に記憶されている道路情報について図３〜５を用いて説明する。図３は、道路情報を構成する道路データのフォーマットの一例である。図４は、道路情報を構成するＯＤ候補グループ毎の経由地データのフォーマットの一例である。図５は、ＯＤ候補グループデータのフォーマットの一例である。

図３に示す道路データは、地図の区画であるメッシュ単位に分けられて地図データ記憶手段１２０に記憶されている。メッシュとは、地図を緯度・経度に基づいて網の目状に区画したものである。各メッシュを表す情報２０は、それぞれを識別するためのメッシュＩＤと、そのメッシュに含まれる道路に関する道路に関する情報とで構成される。

各メッシュに含まれる道路は、道路リンク単位で地図データ記憶手段１２０に記憶されている。各道路リンクを表す道路リンク情報２１は、それぞれを識別するためのリンクＩＤと、各道路リンクの始点および終点の情報と、道路種別と、コストデータとで構成される。

各道路リンクは方向を持っており、道路リンクの始点および終点の情報によってその方向と地図上の位置が特定できる。道路リンクの始点および終点には、それぞれが地点を表すノードがあり、始点および終点の情報は、それぞれノードを識別するノードＩＤと、ノードの位置を表す緯度および経度の情報で構成される。

道路種別とは、各道路リンクが表す道路の種類を表す情報である。たとえば、道路リンクが表す道路が都市間高速道の場合は「０」、都市内高速道の場合は「１」、国道の場合は「２」、そのほかの道路の場合は「３」といったように定義される。そのほかの道路とは、たとえば細街路である。

コストデータとは、探索手段１６０が経路探索時に使用する道路リンクの重みであり、始点から終点までの移動に要するコストを表す。コストデータには、統計交通情報や、リンク長、旅行時間など、様々な種類がある。以下の説明では、コストデータはリンク長があるものとして説明する。探索手段１６０がリンク長をコストデータとして経路探索する場合、探索される誘導経路は出発地から目的地までの走行距離が最小の経路となる。

図４に示す経由地データは、出発地側のＯＤ候補グループ単位に分けられて地図データ記憶手段１２０に記憶されている。出発地側のＯＤ候補グループ、目的地側のＯＤ候補グループについては、図７のフローチャートの説明時に説明する。各ＯＤ候補グループを表す情報２２は、それぞれを識別するためのＯＤ候補グループＩＤを持つ。このＯＤ候補グループＩＤは、出発地側のＯＤ候補グループＩＤである。さらに、情報２２は、出発地側のＯＤ候補グループと目的地側のＯＤ候補グループとの組み合わせで決まる経由地に関するノード情報２３の集合として構成される。

ノード情報２３は、各ノードを識別するためのノードＩＤと、各ノードに対応する地点の緯度および経度と、各ノードに対応する地点にある交差点の交差点名称と、各ノードを通過する頻度の高低を表す頻度情報とで構成される。頻度情報は、予め道路データを使用して算出されたデータであって、後述する経由地選択手段１４０の処理に用いられる。

図５に示すＯＤ候補グループデータは、ＯＤ候補グループ単位に分けられて地図データ記憶手段１２０に記憶されている。各ＯＤ候補グループを表す情報２４は、それぞれを識別するためのＯＤ候補グループＩＤと、そのＯＤ候補グループを構成するノードに関するノード情報２５で構成される。ノード情報２５は、各ノードを識別するためのノードＩＤで構成される。

図４の経由地データのノードＩＤと図５のＯＤ候補グループデータのノードＩＤは、図３の道路データのノードＩＤと対応している。このため、道路データのノードＩＤをキーに、経由地データ内の対応するノード情報２３や、ＯＤ候補グループデータ内の対応するノード情報２５を検索することができる。

ＯＤ候補グループデータに含まれるＯＤ候補グループを作成する方法について図６に示すフローチャートを用いて説明する。図６は、ナビゲーションシステムの製造メーカや地図データベンダなどがナビゲーションシステムの工場出荷前などにサーバを用いて実行する処理である。図６の処理を行うサーバは、地図データ記憶手段１２０と、二つのノード間の推奨経路を公知なダイクストラ法などで探索する推奨経路探索手段と、ノード間の距離の短いノードの組み合わせを探して複数のクラスタにまとめる公知なクラスタリングと、ナビゲーションシステム１００の地図データ記憶手段１２０に記憶されているＯＤ候補グループデータにＯＤ候補グループを構成するノードＩＤを書き込む書込手段とを備える。

図６の処理では、サーバは、道路データの道路リンク情報２１に含まれる、特定の道路種別の始点のノードと終点のノードのすべての組み合わせについて経路探索処理を行い、ノード間の経路長を使ってノードをクラスタリングして、ＯＤ候補グループに関する情報を算出する。

図６のステップＳ００１では、サーバは、地図データ記憶手段１２０に記憶されている道路データに含まれる道路リンクの道路リンク情報２１の始点の情報と、終点の情報から、特定の道路種別のノードを抽出する。このとき、特定の道路種別とは、高速道や国道などの主要な道路の種別を指す。この主要な道路が接続しているノードを抽出することで、図６の処理の効率化を図ることができる。この道路種別は、メッシュ毎に決められる。主要なノードを抽出した後、ステップＳ００２に進む。

図６のステップＳ００２では、サーバは、ステップＳ００１で抽出された主要なノード間の経路長を用いて、主要なノードをクラスタリングする。このクラスタリング処理によって、生成されるノードの集合がＯＤ候補グループとなる（たとえば、図２のＯＤ候補グループＧ１〜Ｇ４）。サーバは、これらのＯＤ候補グループを識別するためにＯＤ候補グループＩＤを設定する。そして、サーバは、ＯＤ候補グループを表す情報２４として、クラスタに設定されたＯＤ候補グループＩＤと、そのクラスタを構成するノードＩＤのノード情報２５を地図データ記憶手段１２０のＯＤ候補グループデータへ書き込む。サーバは、算出したＯＤ候補グループデータを格納したら、図６の処理を終了する。また、ステップＳ００２のクラスタリングは、主要なノード間の経路長の代わりに主要なノード間の直線距離を使用してクラスタリングすることにしてもよい。

経由地データに含まれる頻度情報を算出する方法について図７に示すフローチャートを用いて説明する。図７は、ナビゲーションシステムの製造メーカや地図データベンダなどがナビゲーションシステムの工場出荷前などにサーバを用いて実行する処理である。図７の処理を行うサーバは、地図データ記憶手段１２０と、二つのノード間の推奨経路を公知なダイクストラ法などで探索する推奨経路探索手段と、ナビゲーションシステム１００の地図データ記憶手段１２０に記憶されている経由地データに頻度情報を書き込む書込手段とを備える。書込手段は、有線通信や、無線通信、各種記録メディアなどにより、ナビゲーションシステム１００の地図データ記憶手段１２０の経由地データに頻度情報をアップロードする。

図７の処理では、サーバは、ＯＤ候補グループデータのＯＤ候補グループ情報２４に含まれるノードのすべての組み合わせについて経路探索処理を行い、探索の結果得られた複数の経路を統計処理し、経由地データに含まれる各ノードに関する頻度情報を算出する。

図７のステップＳ８０では、サーバは、地図データ記憶手段１２０に記憶されているＯＤ候補グループデータに含まれているＯＤ候補グループ情報２４のすべてについて、ステップＳ９０からステップＳ１４０の処理を終了したか否かを判定する。図７の処理は、ステップＳ８０の処理が肯定判定された場合はステップＳ１５０に進み、否定判定された場合はステップＳ９０に進む。

図７のステップＳ９０では、サーバは、地図データ記憶手段１２０に記憶されているＯＤ候補グループデータに含まれているＯＤ候補グループ情報２４を一つ選択し、出発地側のＯＤ候補グループとする。さらに、地図データ記憶手段１２０に記憶されているＯＤ候補グループデータに含まれているＯＤ候補グループ情報２４について、出発地側のＯＤ候補グループ以外から一つ選択し、目的地側のＯＤ候補グループとする。

図７のステップＳ１００では、サーバは、地図データ記憶手段１２０に記憶されている出発地側のＯＤ候補グループに含まれているノード情報２５のすべてについて、ステップＳ１４０の処理を終了したか否かを判定する。図７の処理は、ステップＳ１００の処理が肯定判定された場合はステップＳ８０に進み、否定判定された場合はステップＳ１１０に進む。

図７のステップＳ１１０では、サーバは、出発地側のＯＤ候補グループからノード情報２５を一つ選択し、選択されたノード情報２５のノードＩＤを用いて、道路リンクの道路リンク情報２１からノードの情報を取得する。以降、ステップＳ１１０で抽出されたノードの情報を出発地側のノードと称する。図７の処理は、出発地側のノードとする始点の情報を取得したらステップＳ１２０に進む。

図７のステップＳ１２０では、サーバは、目的地側のＯＤ候補グループに含まれているノード情報２５のすべてについて、ステップＳ１３０からＳ１４０の処理を終了したか否かを判定する。図７の処理は、ステップＳ１２０が肯定判定された場合はステップＳ１００に戻り、否定判定された場合はステップＳ１３０に進む。

図７のステップＳ１３０では、サーバは、目的地側のＯＤ候補グループからノード情報２５を一つ選択し、選択されたノード情報２５のノードＩＤを用いて、道路リンクの道路リンク情報２１からノードの情報を取得する。以降、ステップＳ１２０で抽出されたノードの情報を目的地側のノードと称する。図７の処理は、目的地側のノードとする終点の情報を取得したらステップＳ１４０に進む。

図７のステップＳ１４０では、サーバは、出発地側のノードから目的地側のノードまでの経路を、公知のダイクストラ法などを用いて一つ探索し、探索した経路に関する経路情報をサーバに備えられたＲＡＭなどの記憶領域に蓄積する。経路情報は、図８のフォーマットで蓄積される。図８のフォーマットは、出発地側のＯＤ候補グループのＯＤ候補グループＩＤ４５と目的地側のＯＤ候補グループのＯＤ候補グループＩＤ４６と、出発地側のノードのノードＩＤ４１と、目的地側のノードのノードＩＤ４２と、経路に含まるノード数４３と、出発地側のノードから目的地側のノードまでの間に通過する通過ノード４４とからなる。図７の処理は、探索した経路の経路情報をＲＡＭなどに蓄積したらステップＳ１２０に戻る。ステップＳ１２０に戻ると、サーバはステップＳ１１０で取得された出発地側のノードに対して、目的地側のノードとする次の終点の情報を取得する。このような処理を繰り返して、始点の情報と終点の情報とのすべての組み合わせについて経路を探索し、探索された経路の経路情報を蓄積する。

図７のステップＳ１５０では、サーバは、図８の経路情報の中の出発地側のＯＤ候補グループの同一のＯＤ候補グループＩＤと、目的地側のＯＤ候補グループの同一のＯＤ候補グループＩＤが含まれるものを抽出し、その通過ノードのノードＩＤについて、通過ノードとして現れる同一のノードＩＤの個数をそれぞれ算出する。そして、サーバは、算出されたノードＩＤの個数を図４の経由地データの対応する出発地側のＯＤ候補グループのＯＤ候補グループＩＤと目的地側のＯＤ候補グループのＯＤ候補グループＩＤとノードＩＤの頻度情報へ書き込む。サーバは、算出されたノードＩＤの個数を経由地データの頻度情報として格納したら、図７の処理を終了する。

図９は、図７のフローチャートの実行例を示す図である。サーバの地図データ記憶手段１２０に図９（ａ）に示す地図についての道路データと経由地データが記憶されているものとする。図９ではＯＤ候補グループを二つ想定し、それぞれのＯＤ候補グループＩＤはＧ５とＧ６とする。ＯＤ候補グループＧ５にはノードＮ１とノードＮ２が含まれ、ＯＤ候補グループＧ６にはノードＮ３とノードＮ４が含まれる。道路データには、道路リンクＬ１と道路リンクＬ２と道路リンクＬ３と道路リンクＬ４と道路リンクＬ５に関する道路リンク情報２１が記憶されている。道路リンクＬ１は、ノードＮ１を始点としノードＮ２を終点とする。道路リンクＬ２は、ノードＮ２を始点としノードＮ３を終点とする。道路リンクＬ３は、ノードＮ２を始点としノードＮ４を終点とする。道路リンクＬ４は、ノードＮ３を始点としノードＮ４を終点とする。道路リンクＬ５は、ノードＮ４を始点としノードＮ１を終点とする。図９（ａ）の地図では、説明の簡略化のため、すべての道路リンクを一方通行の道路としている。図９（ａ）の地図に対して、図７の処理を行うと、出発地側のノードと目的地側のノードとの組み合わせは、４ｘ３＝１２通りある。ＯＤ候補グループＧ５を出発地側のＯＤ候補グループとし、ＯＤ候補グループＧ６を目的地側のＯＤ候補グループとした場合、ノードＮ１とノードＮ２が出発地側のノード、ノードＮ３とノードＮ４が目的地側のノードとなる。また、ＯＤ候補グループＧ６を出発地側のＯＤ候補グループとし、ＯＤ候補グループＧ５を目的地側のＯＤ候補グループとした場合、ノードＮ３とノードＮ４が出発地側のノード、ノードＮ１とノードＮ２が目的地側のノードとなる。各ノードの組み合わせに対して探索した経路の経路情報を図９（ｂ）に示す。図９（ｂ）に示す経路情報には、通過ノード４４としてノードＮ１は３個存在する。したがって、ノードＮ１の頻度情報は「３」となる。同様にノードＮ２〜Ｎ４の頻度情報は、それぞれ「３」、「０」、「３」となる。

次に、探索判定手段１３０の処理について、図１０に示すフローチャートを用いて説明する。図１０の処理は、ナビゲーションシステム１００のマイクロプロセッサによって実行され、探索手段１６０の第１の経路探索を介して、経路情報が入力されたとき処理を開始する。

図１０のステップＳ３０１では、マイクロプロセッサは、入力された経路情報に対応する経路のコストが所定の閾値以下か否かを判定する。この処理は、後述する図１５のステップＳ２０２３と同様の処理である。マイクロプロセッサは、経路のコストが所定の閾値以下の場合、適切な経路が計算されたと判断して、ステップＳ３０１の処理を肯定判定する。そして、マイクロプロセッサは、処理をステップＳ３０３に進め、入力された経路情報を表示手段１５０へ提供し、図１０の処理を終了する。一方、経路のコストが所定の閾値より大きい場合、マイクロプロセッサは、適切な経路が計算されなかったと判断して、ステップＳ３０１の処理を否定判定し、ステップＳ３０２に処理を進める。なお、ステップＳ３０１では、第１の経路探索が経路を計算できない場合についても、否定判定することにしてもよい。ステップＳ３０２では、マイクロプロセッサは、経由地選択手段１４０へ経由地を設定するように命令する。

なお、図１０のフローチャートでは、マイクロプロセッサが、経由地選択手段１４０による経由地の設定の必要性を判断していたが、探索判定手段１３０に含まれるユーザインターフェースを介して、ユーザに経路が適切か否かを判定させることで、経由地の設定の必要性を判断してもよい。この経路が適切か否かを判断する方法を、図１１を用いて説明する。

表示手段１５０は、探索手段１６０の第１の経路探索の出力結果の経路と、入力手段１１０を介して入力された出発地および目的地とに基づいて、出発地と目的地と経路とを表示可能な道路地図の描画用のデータを地図データ記憶手段１２０から取得する。そして、取得したデータに基づいて図１１のような画面を表示する。図１１には、道路地図と共に、出発地Ｓおよび目的地Ｇと、経路Ｋと、この経路でよいか否かを問うウィンドウＷ１が表示されている。探索判定手段１３０は、図１１に示すように表示されたウィンドウＷ１の「Ｙｅｓ」ボタンおよび「Ｎｏ」ボタンから、入力手段１１０に含まれるユーザインターフェースを介して、経路が適切か否かを選択させる。ウィンドウＷ１の「Ｙｅｓ」ボタンが選択された場合、表示されている最適経路Ｋが適切なものとして最適経路Ｋをそのまま使用する。ウィンドウＷ１の「Ｎｏ」ボタンが選択された場合、図１０のステップＳ３０２と同様に、マイクロプロセッサは、経由地選択手段１４０へ経由地を設定するように命令する。

次に、経由地選択手段１４０の処理について、図１２に示すフローチャートを用いて説明する。図１２の処理は、ナビゲーションシステム１００のマイクロプロセッサによって実行され経路判定手段１３０にて経由地の設定が必要であると判断されたときに処理を開始する。

図１２のステップＳ２００では、マイクロプロセッサは、入力手段１１０により入力された出発地および目的地の位置に基づいて、出発地側のＯＤ候補グループと目的地側のＯＤ候補グループを決定する。ステップＳ２００の詳細な処理を、図１３に示すフローチャートを用いて説明する。さらに図１３の処理の例を図１４に示す。なお、図１３の説明では、出発地側のＯＤ候補グループを決定する処理について説明するが、目的地側のＯＤ候補グループを決定する処理も図１３のフローチャート中の「出発地側のＯＤ候補グループ」を「目的地側のＯＤ候補グループ」に置き換えることで実現できる。

図１３に示す処理を初めて実行するとき、マイクロプロセッサは、入力手段１１０により入力された出発地の位置に最も近いノードを開始点（図１４のノードＮ１１）に設定して、図３の道路データに基づいて公知のダイクストラ法を実行する。ダイクストラ法は、開始点となるノードから道路データに含まれる各ノードへの最小コストを算出する貪欲アルゴリズムである。ダイクストラ法では、最小コストが確定したノードの集合である確定集合と、最小コストが確定していないノードの集合である未確定集合とを変数として用いる。図１４の例では、点線の楕円領域Ａ１内のノードが確定集合に含まれ、実線の楕円領域Ａ２内のノードＮ１２〜Ｎ１４が未確定集合に含まれるものとする。

マイクロプロセッサは、開始点に設定されたノードの最小コストをゼロに設定し、開始点に設定されなかったノードについては各ノードの最小コストの初期値を無限大に設定する。そして、すべてのノードを未確定集合に含め、確定集合を空集合とする。ダイクストラ法では、未確定集合が空集合になるまで以下の処理を繰り返す。
（１）未確定集合に含まれるノードのうち、最小コストが最小のノードを検索する。
（２）（１）で検索されたノードを確定集合に含める。
（３）（１）で検索されたノードを始点とする各リンクについて、それらの終点のノードが未確定集合に含まれるとき、当該終点のノードの最小コストを当該リンクのコストデータと（１）で検索されたノードの最小コストとの和に変更する。

以降、（２）で確定集合に含められたノードのことを確定ノードと称する。確定ノードは、（２）でノードが確定集合に含められるたびに更新され、最初は設定されていない。たとえば、図１４において未確定集合に楕円領域Ａ２内にあるノードＮ１２〜ノードＮ１４だけが含まれるとして、ノードＮ１２の最小コストが未確定集合に含まれるノードの中で最小とする場合を例に用いて説明する。まず（１）においてノードＮ１２が検索され、（２）においてノードＮ１２が確定集合に含められる。そして、（３）においてノードＮ１２を始点とするリンクＬ６およびＬ７について、それらのリンクの終点Ｎ１３およびＮ１４が未確定集合に含まれるため、ノードＮ１３の最小コストはノードＮ１２の最小コストとリンクＬ６のコストの和に更新され、ノードＮ１４の最小コストはノードＮ１２の最小コストとリンクＬ７のコストの和に更新される。

図１３のステップＳ２００１では、マイクロプロセッサは、確定ノードを含むＯＤ候補グループが、図５のＯＤ候補グループデータのノード情報２５に存在するか否かを判定する。図１３の処理は、ステップ２００１が肯定判定された場合はステップＳ２００３へ進み、否定判定された場合はステップＳ２００２へ進む。図１３の処理が開始されてから一度も上記（２）の処理が実行されていないときも否定判定される。

図１３のステップＳ２００２では、マイクロプロセッサは、上記（１）の処理を実行した後、（２）の処理を実行し、確定ノードを更新する。

図１３のステップＳ２００３では、マイクロプロセッサは、図１３のステップ２００１で、図５のＯＤ候補グループデータのノード情報２５に存在すると判定した確定ノードを含むＯＤ候補グループを、出発地側のＯＤ候補グループに設定する。図１４の例では、ノードＮ１２を含むＯＤ候補グループが出発地側のＯＤ候補グループに設定される。

図１３のステップＳ２００４では、確定集合と未確定集合とをＲＡＭに一時記憶し、図１３の処理を終了する。ステップＳ２００４で記憶されたデータは、図１０のステップＳ３０２で探索判定手段から経由地の設定命令があったときに使用される。

図１２のステップＳ２０１では、マイクロプロセッサは、図１２のステップＳ２００で決定した出発地側のＯＤ候補グループと目的地側のＯＤ候補グループのそれぞれのＩＤを使って、図４の経由地データから、該当する出発地側のＯＤ候補グループと目的地側のＯＤ候補グループとの組み合わせに対応するノード情報２３の集合を抽出する。

図１２のステップＳ２０２は、図１２のステップＳ２０１で抽出したノード情報２３の集合の中から、探索手段１６０の第２の経路探索で使用する経由地を選択する。図１２のステップＳ２０１で抽出した経由地データのノード情報２３が一つしかない場合は、その経由地データを経由地として探索手段１６０の第２の経路探索へ提供する。図１２のステップＳ２０１で抽出した経由地データのノード情報２３が複数個ある場合は、たとえばノード情報２３の頻度が最も高いノードを経由地として、探索手段１６０の第２の経路探索へ提供する。また、図１５にフローチャートを示す処理により、実際に経路探索をして複数個の経由地候補を選定し、経由地候補の中から、入力手段１１０に含まれるユーザインターフェースを介して、経由地を選択させてもよい。

図１５のステップＳ２０２1では、マイクロプロセッサは、図１２のステップ２０１で抽出したノードのうち、ステップＳ２０２２およびＳ２０２３の処理が行われていないノードから、最も頻度情報（図４）の値が大きいノードを一つ抽出する。図１５の処理は、最も頻度情報の大きいノードを抽出したら、ステップＳ２０２２に進む。

図１５のステップＳ２０２２では、マイクロプロセッサは、ステップＳ２０２１で抽出したノードを経由地として設定し、出発地から経由地を経由して目的地に至る経路をダイクストラ法などに基づいて一つ探索する。図１５の処理は、ステップＳ２０２１で抽出したノードを経由地とした経路探索が終わったらステップＳ２０２３に進む。

図１５のステップＳ２０２３では、マイクロプロセッサは、ステップＳ２０２２で探索した経路のコストが所定の閾値以下であるか否かを判定する。閾値の値は、たとえば、出発地と目的地との間の直線距離の定数倍（たとえば、３倍）とすればよい。図１５の処理は、ステップＳ２０２２で探索した経路のコストが所定の閾値以下の場合はステップＳ２０２４に進み、ステップＳ２０２２で探索した経路のコストが所定の閾値より大きい場合はステップＳ２０２１に戻る。

図１５のステップＳ２０２４では、マイクロプロセッサは、ステップＳ２０２１で抽出したノードを経由地候補として選択する。図１５の処理は、ステップＳ２０２１で抽出したノードを経由地候補として選択したらステップＳ２０２５に進む。

図１５のステップＳ２０２５では、マイクロプロセッサは、経由地候補として所定の個数（たとえば、３個）のノードが選択されたか否かを判定する。マイクロプロセッサは、所定の個数のノードが抽出されているときは図１５の処理を終了し、所定の個数未満のときはステップＳ２０２６に進む。

図１５のステップＳ２０２６では、マイクロプロセッサは、ステップＳ２０２１で抽出したノードがすべて処理された否かを判定する。マイクロプロセッサは、全てのノードが処理されたとき、図１５の処理を終了し、まだ処理されていないノードがあるときは、ステップＳ２０２１へ戻る。

図１５のステップＳ２０２１からＳ２０２６までの処理について、図１６の例を用いて説明する。図１６には、出発地のノードＮＳおよび目的地のノードＮＧのほかにノードＮ５〜Ｎ１０が示されている。図１６では、ノードＮＳとノードＮＧとの間の直線距離が５Ｌ、ノードＮ５とノードＮ８との間のリンク長が４Ｌ、それ以外の図中のリンクのリンク長が３Ｌである。図１６のノードＮ５〜Ｎ１０のうち、ノードＮ５とノードＮ６の頻度情報が他のノードより大きい。ノードＮ６の位置は、ノードＮ５よりもノードＮＧに近いが、ノードＮ６とノードＮＧとの間に河川８１などを挟んでおり、ノードＮ６からノードＮＧの地点に直接行くことはできない。

ステップＳ２０２１においてノードＮ５が抽出されると、ステップＳ２０２２では、ノードＮＳから、ノードＮ５、ノードＮ８、ノードＮ９の順番にノードを通過してノードＮＧに至る経路が探索される。このとき、経路のコストは１３Ｌとなる。ステップＳ２０２３において出発地と目的地との間の直線距離の３倍を閾値としている場合、経路のコスト「１３Ｌ」はノードＮＳとノードＮＧとの間の直線距離「５Ｌ」の３倍以下であるため、ステップＳ２０５においてノードＮ５は経由地候補として選択される。

ステップＳ２０２１においてノードＮ６が抽出されると、ステップＳ２０２２では、ノードＮＳから、ノードＮ６、ノードＮＳ、ノードＮ５、ノードＮ８、ノードＮ９の順番にノードを通過してノードＮＧに至る経路が探索される。このとき、経路のコストは１９Ｌとなる。ステップＳ２０４において出発地と目的地との間の距離の３倍を閾値としている場合、経路のコスト「１９Ｌ」はノードＮＳとノードＮＧとの間の直線距離「５Ｌ」の３倍より大きいため、ステップＳ２０２４においてノードＮ６は経由地候補として選択されない。このように、実際に出発地から目的地までの経路を探索することにより、ノードＮ６のように遠回りする必要があるものを経由地候補として選択しないようにできる。

なお、マイクロプロセッサは、図１５のフローチャートを使用せずに、図４に示す経由地データのノード情報２３の通過頻度の高い順に、複数の経由地候補を選んでもよい。

次に、経由地選択手段１４０で複数個の経由地候補から、入力手段１１０に含まれるユーザインターフェースを介して、経由地を選択させる方法について図１７を用いて説明する。図１７は、経由地選択手段１４０で選択された複数の経由地候補を表示手段１５０に表示した例である。表示手段１５０は、経由地選択手段１４０で選択された経由地候補と、入力手段１１０を介して入力された出発地および目的地とに基づいて、出発地と、目的地と、経由地候補とを表示できる道路地図を描画するためのデータを地図データ記憶手段１２０から取得し、図１７のように表示する。図１７には、道路地図と共に、出発地Ｓおよび目的地Ｇと、経由地候補選択手段により選択された経由地候補Ｋ１と、経由地候補Ｋ２と、経由地候補Ｋ３とがアイコン付で表示されている。経由地候補Ｋ１〜Ｋ３の表示位置は、経由地データに含まれる緯度および経度によって特定する。アイコンの画像データなどは、地図データ記憶手段１２０から取得する。経由地選択手段１４０は、図１７のように表示された経由地候補の中から、入力手段１１０に含まれるユーザインターフェースを介して、経由地を選択させる。なお、図１７の例では、地図の下に経由地Ｋ１〜Ｋ３の交差点名称が経由地データに基づいて表示されている。これらの情報は、ポップアップなどによって強調する表示を行ってもよい。

経由地選択手段１４０が行う処理を通して経由地が選択されると、探索手段１６０の第２の経路探索により出発地から経由地までの経路と、経由地から目的地までの経路が探索される。図１８は、経由地選択手段１４０が行う処理を通して選択された経由地と、その経由地を経由する誘導経路を地図上に重ねて表示手段１５０に表示したものである。誘導経路は、探索手段１６０により探索される。なお、図１８では誘導経路に加えて、目的地までのコストの情報と使用した経由地の情報を強調して表示している。

なお、経由地選択手段１４０では、経由地を複数選択してもよい。経由地が複数選択された場合は、経由地間の経路も探索される。この場合、探索手段１６０の第２の経路探索は、探索された経路を出発地から経由地の経路、経由地から経由地の経路、経由地から目的地までの経路の順番に繋げることにより誘導経路を得る。

―第２の実施の形態―
本発明の第２の実施の形態に係るナビゲーションシステムについて説明する。第２の実施の形態では、車両の走行履歴に基づいて頻度情報を決定する点が第１の実施の形態と大きく異なる。

図１９は、第２の実施の形態に係るナビゲーションシステムとセンタ装置からなる通信型ナビゲーションシステムのブロック図である。図１９の通信型ナビゲーションシステム５００は、センタ装置２００とナビゲーションシステム３００と通信回線網４００とからなる。通信回線網４００は、たとえばインターネット回線や携帯電話網などで構成される。

センタ装置２００は、複数の車両から送信される情報を収集して、収集した情報に基づいて経由地データの更新処理を行うサーバを備える設備である。図１９のセンタ装置２００は、データ収集手段２１０と、データ蓄積手段２２０と、経由地頻度更新手段２３０と、地図データ記憶手段１２０と、送信手段２４０とを備える。

データ収集手段２１０は、通信回線網４００を介して複数の車両の走行履歴の情報を収集し、データ蓄積手段２２０へ格納する。車両の走行履歴とは、車両が通過した地点に対応するノードに関するデータである。走行履歴の収集対象の車両は、通信装置（不図示）によってセンタ装置２００と接続されている。この通信装置とは、携帯電話機や、無線ＬＡＮモジュールなどであり、通信回線網４００と接続する機能を有する。

データ蓄積手段２２０は、ハードディスクや、フラッシュメモリなどの記憶手段であり、データ収集手段２１０で収集した車両の走行履歴を走行履歴データとして蓄積する。走行履歴データについては、その詳細を後述する。

経由地頻度更新手段２３０は、サーバによって実行されるソフトウェアである。データ蓄積手段２２０に蓄積されている車両の走行履歴の情報を入力として、地図データ記憶手段１２０における経由地データの頻度情報を更新する。頻度情報を更新する更新タイミングは、所定の時間間隔で行う。たとえば、毎日０：００に１日おきに更新する場合、前日の０：００から新しく収集した走行履歴データを、データ蓄積手段２２０から抽出し、抽出した走行履歴データを使用して地図データ記憶手段１２０の経由地データの頻度情報を更新する。また、地図データ記憶手段１２０のバージョンが年度更新で新しくなった場合は、データ蓄積手段２２０に蓄積されているこれまでのデータを利用して、経由地データの頻度情報を計算する。

送信手段２４０は、通信回線網４００と有線または無線で接続しており、経由地頻度更新手段２３０によって更新された経由地データをナビゲーションシステム３００へ送信する。送信するデータの構成は、地図データ記憶手段１２０の経由地データに準ずる。

ナビゲーションシステム３００は、入力手段１１０と、地図データ記憶手段１２０と、経由地選択手段１４０と、探索判定手段１３０と、表示手段１５０と、探索手段１６０と、受信手段２６０を備える。ナビゲーションシステム３００の構成のうち、第１の実施の形態のナビゲーションシステム１００と同じの符号の構成は、第１の実施の形態と同じものであり、その説明を省略する。

受信手段２６０は、通信回線網４００と無線で接続しており、センタ装置２００の送信手段２４０が送信する更新後の経由地データを受信する。受信した経由地データは、地図データ記憶手段１２０に格納される。多くの車両の走行履歴に基づいて更新した最新の経由地データをセンタ装置２００から取得することで、ナビゲーションシステム３００は、信頼性の高い経由地データを使用できる。

データ蓄積手段２２０が蓄積する走行履歴データについて、図２０を用いて説明する。図２０は、車両ごとの走行履歴データのフォーマットであり、このフォーマットに記載されるデータが各車両からセンタ装置２００へ送信される。図２０の走行履歴データは、車両を識別する車両ＩＤ１２１，車両が通過したノード数１２２、車両が通過した地点のノードのＩＤ１２３、そのノードＩＤ１２３の地点を通過した日時１２４で構成されている。このノードＩＤ１２３は、時系列順に並べられ記憶されており、通過日時が新しいノードＩＤ１２３ほど、後ろに記憶される。また、走行履歴データは、車両の1トリップ単位で記憶されている。この１トリップとは、車両がエンジンを掛けて、出発した地点から、目的地までの走行履歴をいう。

以下、経由地頻度更新手段２３０の詳細について説明する。

経由地頻度更新手段２３０の処理について、図２１に示すフローチャートを用いて説明する。図２１の処理は、所定の更新タイミングになったらセンタ装置２００のサーバにより実行される。

図２１のステップＳ４００では、センタ装置２００のサーバは、前回の更新タイミング以降に新しくデータ蓄積手段２２０に蓄積された走行履歴データをすべて抽出する。走行履歴データの抽出処理が終了したらステップＳ４０１に進む。

図２１のステップＳ４０１では、センタ装置２００のサーバは、ステップＳ４００で抽出したすべての走行履歴データについて、経由地データの頻度情報を更新したか否かを判定する。センタ装置２００は、ステップＳ４００で抽出した走行履歴データについて経由地データの頻度情報を更新した場合は図２１の処理を終了し、処理していない走行履歴データがある場合はステップＳ４０２に進む。

図２１のステップＳ４０２では、センタ装置２００のサーバは、ステップＳ４００で抽出した走行履歴データの中から一つの走行履歴データを選択する。図２１の処理は、ステップＳ４００で抽出した走行履歴データの中から一つ選択したらステップＳ４０３に進む。

図２１のステップＳ４０３では、センタ装置２００のサーバは、ステップＳ４０２で選択した走行履歴データに含まれるノードＩＤをキーとして地図データ記憶手段１２０の経由地データを検索し、対応するノードＩＤの経由地データの頻度情報の値に「１」を加算することにより更新する。図２１の処理は、頻度情報の更新が終了したらステップＳ４０１に戻る。

図２１の処理を図２２に示す具体例を用いて説明する。図２２の例では、図２２（ａ）に示す走行履歴データに基づいて、経由地データの頻度情報を更新する。図２２（ａ）の走行履歴データは、車両ＸがノードＮ１と、ノードＮ２と、ノードＮ３との三つのノードを通過したことを表している。図２２（ｂ）は、図２２（ａ）の走行履歴データに基づいて、経由地データのノードＮ１と、ノードＮ２と、ノードＮ３の頻度情報に１が加算されることを示している。更新前のノードＩＤ「Ｎ１」の頻度情報は「１０」であるのに対して、更新後のノードＩＤ「Ｎ１」の頻度情報は「１１」になっている。ノードＩＤ「Ｎ２」と「Ｎ３」とについても同様である。ノードＩＤ「Ｎ４」の頻度情報は、図２２（ａ）の走行履歴データに含まれていないため、更新されない。

―第３の実施の形態―
本発明の第３の実施の形態に係るナビゲーションシステムについて説明する。第３の実施の形態では、ユーザインターフェースを介して入力された経由地の情報を学習することで、地図データの経由地データを更新していく点が第１の実施の形態、第２の実施の形態と大きく異なる。

図２３は、第３の実施の形態に係るナビゲーションシステムのブロック図である。図２３のナビゲーションシステム６００は、入力手段１１０、地図データ記憶手段１２０、探索判定手段１３０、経由地選択手段１４０、表示手段１５０、探索手段１６０、および経由地学習手段１７０を備える。ナビゲーションシステム４００の構成のうち、第１の実施の形態のナビゲーションシステム１００と同じの符号の構成の内、入力手段１１０、探索判定手段１３０、表示手段１５０、探索手段１６０は、第１の実施の形態と同じものであり、その説明を省略する。地図データ記憶手段１２０と経由地選択手段１４０は、第１の実施の形態と異なる点を説明する。

地図データ記憶手段１２０のフォーマットは、図３〜図５と同様である。しかし、経由地学習手段１７０により経由地データが作成されるため、経由地学習手段１７０により、経由地データが追加されない限り、図４の経由地データのノード情報２３は空である。ただし、図３の道路データおよび図５のＯＤ候補グループデータは実施例１と同じである。

経由地選択手段１４０は、ナビゲーションシステム６００に搭載されている不図示のマイクロプロセッサや、ＲＡＭ、ＲＯＭなどによって実行されるソフトウェアである。経由地選択手段１４０は、入力手段１１０によって入力された出発地および目的地に基づいて、地図データ記憶手段１２０に記憶される複数のＯＤ候補グループの中から、出発地および目的地から近いＯＤ候補グループを選択し、選択したＯＤ候補グループの中から経由地の候補を一つ以上（好ましくは二つ以上）選択し、選択した経由地の候補についての情報を表示手段１５０と探索手段１６０へ提供する。このとき、地図データ記憶手段１２０の経由地データの該当するＯＤ候補グループのノード情報２３が存在しない場合、経由地学習手段１７０に、経由地を学習するように命じる。

経由地選択手段１４０の処理について、図２４に示すフローチャートを用いて説明する。図２４の処理は、ナビゲーションシステム６００のマイクロプロセッサによって実行される。図２４のステップＳ２００、ステップＳ２０１、ステップＳ２０２は、図１２の同じ符号の処理と同様の処理であるため、説明を省略する。

図２４のステップＳ２０３では、マイクロプロセッサは、地図データ記憶手段１２０の経由地データ内に、出発地側のＯＤ候補グループと目的地側のＯＤ候補グループとの組み合わせに対応したノード情報２３の集合があるか否かを判定する。図２４の処理は、ステップＳ２０３で肯定判定された場合は、ステップＳ２０１へ進み、否定判定された場合はステップＳ２０４へ進む。

図２４のステップＳ２０４では、マイクロプロセッサは、経由地学習手段１７０へ、経由地データを学習するように命令し、出発地側のＯＤ候補グループと、目的地側のＯＤ候補グループのＩＤを経由地学習手段１７０へ提供し、処理を終了する。

経由地学習手段１７０は、ナビゲーションシステム６００に搭載されている不図示のマイクロプロセッサや、ＲＡＭ、ＲＯＭなどによって実行されるソフトウェアである。経由地学習手段１７０は、ユーザインターフェースを含み、ユーザはユーザインターフェースを介して入力された経由地の情報を、地図データ記憶手段１２０の経由地データに書き込む。

経由地学習手段１７０の処理について、図２５に示すフローチャートを用いて説明する。図２５の処理は、ナビゲーションシステム４００のマイクロプロセッサによって実行される。

図２５のステップＳ５００では、マイクロプロセッサは、ユーザインターフェースを介してユーザに経由地を入力させ、経由地に関する情報を取得する。以降、入力された経由地に関する情報のことを経由地情報と称し、その設定方法を、図２６を用いて説明する。

図２６は、ユーザインターフェースを介してユーザに経由地を指定させるために表示手段１５０に表示させる画面の一例である。表示手段１５０は、入力手段１１０を介して入力された出発地および目的地に基づいて、出発地とおよび目的地を表示できる道路地図を描画するためのデータを地図データ記憶手段１２０から取得し、図２６のような画面を表示する。図２６には、道路地図と共に、出発地Ｓおよび目的地Ｇと、ユーザに経由地の設定を促すウィンドウＷ２が表示されている。ユーザがユーザインターフェースを介して、道路地図上の交差点を経由地として指定すると、マイクロプロセッサは、指定された交差点に対応するノードに関してノードＩＤ等の情報を道路データから取得する。こうして取得されたノードＩＤ等の情報が経由地情報となる。

図２５のステップＳ５０１では、マイクロプロセッサは、経由地選択手段１４０から入力された出発地側のＯＤ候補グループＩＤおよび目的地側のＯＤ候補グループＩＤと、経由地情報に含まれるノードＩＤとに基づいて、地図データ記憶手段１２０の経由地データのノード情報２３を更新し、学習する。すなわち、経由地選択手段１４０から入力された出発地側のＯＤ候補グループＩＤおよび目的地側のＯＤ候補グループＩＤに対応する経由地データ２２に新たにノード情報２３を追加したり、既に記憶されているノード情報２３の頻度情報に所定値（たとえば１）を加算したりする。この追加処理や加算処理等により、ユーザが経由地として設定した結果が経由地データの頻度情報として学習される。

図２５のステップＳ５０１における学習の詳細な処理フローを図２７に示す。ステップＳ５０１１ａでは、マイクロプロセッサは、経由地選択手段１４０により決定された出発地側のＯＤ候補グループＩＤに対応するＯＤ候補グループを表す情報２２の中に、経由地選択手段により決定された目的地側のＯＤ候補グループに対応するノード情報２３の集合が存在するか否かを判定する。ステップＳ５０１１ａが肯定判定された場合はステップＳ５０１１ｂに進み、ステップＳ５０１１ａが否定判定された場合はステップＳ５０１３ａに進む。

ステップＳ５０１１ｂでは、マイクロプロセッサは、ステップＳ５０１１ａで存在を確認したノード情報２３の集合の中にステップＳ５００で取得された経由地情報に含まれる
各ノードＩＤのノード情報２３が存在するか否かを判定する。マイクロプロセッサは、そのノード情報２３の集合の中に存在するノード情報２３についてはステップＳ５０１２の処理を行い、そのノード情報２３の集合の中に存在しないノード情報２３についてはステップＳ５０１３ｂの処理を行う。

ステップＳ５０１２では、マイクロプロセッサは、ステップＳ５０１１ｂにおいて存在が確認されたノード情報２３の頻度情報を更新する。ノード情報２３の頻度情報の更新は、たとえばそのノード情報２３の頻度情報に所定値（たとえば１）を加算することで行う。

ステップＳ５０１３ａでは、マイクロプロセッサは、経由地選択手段１４０により決定された目的地側のＯＤ候補グループのグループＩＤと、ステップＳ５００で取得された経由地情報に含まれる各ノードＩＤにそれぞれ対応したノード情報２３とを組み合わせて、経由地選択手段１４０により決定された出発地側のＯＤ候補グループＩＤに対応するＯＤ候補グループを表す情報２２の中に追加する。

ステップＳ５０１３ｂでは、マイクロプロセッサは、ステップＳ５０１１ｂにおいて存在しないと判定された経由地情報に含まれるノードＩＤのノード情報２３を、経由地選択手段１４０により決定された目的地側のＯＤ候補グループに対応するノード情報２３の集合の中に追加する。

以上で説明した各実施の形態によれば、次の作用効果を奏する。

ナビゲーションシステム１００、ナビゲーションシステム３００、ナビゲーションシステム６００は、地図データ記憶手段１２０に基づいて、出発地から１以上の経由地を経由して目的地に至る誘導経路を探索手段１６０が探索する。誘導経路を探索するための経由地は、地図データ記憶手段１２０に経由地データとして予め記憶されているノードに関するノード情報２３のうち、頻度情報の値が大きいものが選択される。第１の実施の形態、第２の実施の形態、および第３の実施の形態では、探索判定手段１３０と、経由地選択手段１４０とにより経由地が選択される。これにより、ナビゲーションシステム１００、ナビゲーションシステム３００、およびナビゲーションシステム６００は、誘導経路を探索する処理の実行中に記憶するデータを抑制しつつ、適切な誘導経路を探索することができる。ダイクストラ法などの経路探索方法では、処理の実行中に処理対象となるノードの数に依存したデータをＲＡＭなどに記憶する必要がある。処理対象となるノードの数は出発地と目的地との間の距離が離れれば離れるほど増加する。各実施の形態のように、適切な経由地を出発地と目的地との間に挟むと、出発地と経由地までの距離や経由地と目的地までの距離は、出発地から目的地までの距離よりも短くなる。そのため、一度の経路探索（出発地から経由地や、経由地から目的地）における処理対象のノードの数は少なくなり、ＲＡＭなどに記憶するデータ量を低減できる。また、実際にすべてのノードについて経路探索した結果または走行履歴に基づいて、通過された頻度が高かったノードを経由地として設定するため、確実に適切な誘導経路を探索できる。

頻度情報は、第１の実施形態では、図７に示すように、工場出荷前等に予め経路探索された結果に基づいて決定される。第２の実施形態では、経由地頻度更新手段２３０により車両の走行履歴に基づいて決定される。第３の実施形態では、ユーザがユーザインターフェースを介して設定した経由地に関する経由地情報に基づいて、経由地学習手段１７０が経由地データを更新し、頻度情報の学習を行う。

以上で説明した各実施の形態は、次のように変形して実施できる。

探索手段１６０などが経路を探索する方法は、ダイクストラ法だけに限定しない。たとえば、ベルマン・フォード法などを用いて経路を探索してもよい。

探索手段１６０による誘導経路の探索の代わりに、図１５のステップＳ２０２２で探索した経路の情報をＲＡＭなどに記憶しておき、経由地が選択されたときにＲＡＭから対応する経路の情報を読み出すことにしてもよい。また、探索手段１６０により誘導経路を探索する方法と、ＲＡＭに記憶した経路を読み出す方法とを併用してもよい。いずれの方法を採用するかは、経由地が二つ以上選択されたか否かに基づいて決定すればよい。ステップＳ２０２２で探索された経路は、経由地を一つ選択した場合であるため、二つ以上選択された場合には対応できないためである。

図７のステップＳ１１０およびＳ１３０で始点の情報や終点の情報を取得する道路リンクを表す道路リンク情報２１は、道路種別により限定してよい。たとえば、道路種別が「３」でないものに限定してよい。これにより、細街路など経路に含まれる可能性が極めて低い道路にしか繋がっていないノードについては、算出する必要がなくなるため、図３の処理を高速することができる。

上記の各実施の形態および各変形例は、任意に組み合わせて実施してもよい。

ナビゲーションシステム１００およびナビゲーションシステム３００およびナビゲーションシステム６００は、車両用のものに限定しない。たとえば、携帯端末に徒歩用地図を表示する歩行者用のナビゲーションシステムやナビゲーション用の端末装置にも利用できる。第２の実施の形態の場合、ＧＰＳ付の携帯端末であれば、車両ＩＤ１２１をユーザＩＤなどに変更した上で、走行履歴を送信することは可能である。

以上で説明した各実施の形態や各種の変形例はあくまで一例であり、発明の特徴が損なわれない限り、本発明はこれらの内容に限定されない。

１００，３００，６００ ナビゲーションシステム
１１０ 入力手段
１２０ 地図データ記憶手段
１３０ 探索判定手段
１４０ 経由地選択手段
１５０ 表示手段
１６０ 探索手段
１７０ 経由地学習手段
２００ センタ装置
２１０ データ収集手段
２２０ データ蓄積手段
２３０ 経由地頻度更新手段
２４０ 送信手段
２６０ 受信手段
４００ 通信回線網
５００ 通信型ナビゲーションシステム

Claims (8)

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

Images