(57)【要約】【課題】ユーザが目的地を特定して経路を探索する際の経路計算に要する時間を短縮する。【解決手段】ナビゲーション装置に電源が投入され、現在位置の検出が開始されると、予め記憶するメモリ地点や過去に目的地として設定された地点を終点とし、現在位置を始点とする経路を計算し、計算した経路を記憶部に記憶する。一方、ユーザがメモリ地点や過去に目的地として設定した地点を目的地として設定する場合（ステップＳ２００）には、ユーザの設定した目的地を終点とする、既に計算済みの経路を記憶部から読み出し、この読み出した経路を経路案内に利用する。これにより、ユーザによって目的地が設定された場合の経路計算の処理が省略されるため、その結果、経路計算に要する時間を短縮することができる。【選択図】        図３
2004333443.tif 000002
【特許請求の範囲】
【請求項１】
地図データを格納する地図データ格納手段と、
前記地図データ上の地点を記憶する地点記憶手段と、
現在位置を検出する位置検出手段と、
前記現在位置を始点とし、前記地点記憶手段の記憶する地点を終点とする経路を計算する経路計算手段と、
前記経路計算手段の計算した経路を記憶する経路記憶手段と、
経路の目的地を設定する目的地設定手段と、
前記目的地設定手段が前記地点記憶手段の記憶する地点を目的地として設定する場合、前記地点を終点とする経路を前記経路記憶手段から抽出し、この抽出した経路に基づいて最終的な経路を設定する経路設定手段とを備えることを特徴とする経路計算装置。
【請求項２】
前記経路計算手段は、周期的に経路計算を実行し、
前記経路記憶手段は、前記経路計算手段によって計算された最新の経路を記憶することを特徴とする請求項１記載の経路計算装置。
【請求項３】
前記経路設定手段は、前記経路記憶手段から抽出した経路の始点と前記位置検出手段の検出する現在位置とが異なる場合、前記経路計算手段に対して前記現在位置から前記始点までの経路計算を指示し、前記経路計算手段によって計算される前記現在位置から前記始点までの経路と前記経路記憶手段から抽出した経路とによって構成される経路を最終的な経路として設定することを特徴とする請求項１又は２記載の経路計算装置。
【請求項４】
前記地点記憶手段は、前記地図データ上の地点に対し、経路の目的地として設定された回数を前記地点に関連付けて記憶し、
前記地点記憶手段が複数の地点を記憶する場合、前記経路計算手段は、前記経路の目的地として設定された回数に応じて前記地点毎の経路計算の頻度を設定し、この設定された頻度に従って前記各地点を終点とする経路を計算することを特徴とする請求項２又は３記載の経路計算装置。
【請求項５】
前記地点記憶手段が複数の地点を記憶する場合、前記経路計算手段は、前記現在位置から前記各地点までの距離に応じて前記地点毎の経路計算の頻度を設定し、この設定された頻度に従って前記各地点を終点とする経路を計算することを特徴とする請求項２又は３記載の経路計算装置。
【請求項６】
前記地点記憶手段が複数の地点を記憶する場合、前記経路計算手段は、前記現在位置から前記各地点までの経路計算に要した時間に応じて前記地点毎の経路計算の頻度を設定し、この設定された頻度に従って前記各地点を終点とする経路を計算することを特徴とする請求項２又は３記載の経路計算装置。
【請求項７】
前記地点記憶手段は、少なくとも経路の目的地として設定された地点、及び予め登録された地点を記憶することを特徴とする請求項１〜６のいずれかに記載の経路計算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路計算装置に関するものである。
【０００２】
【従来の技術】
従来、出発地や目的地の位置が明確に指定されない場合の経路探索を迅速に行うことを目的とした経路探索方法が提案されている（例えば、特許文献１参照。）。この特許文献１に開示されている経路探索方法によれば、例えば、出発地の候補となるノードが２つ存在する場合、先ず、どちらか１つのノードを出発地として目的地までの最短経路を探索し、この最短経路を構成する各ノードから目的地のノードに至る実距離をノード毎に記憶する。
【０００３】
次に、もう１つのノードを出発地として目的地のノードへ向かって最短経路を探索する場合には、目的地のノードへ向かう先端ノードが記憶されたノードと一致するかどうかを判断する。そして、先端ノードと記憶されたノードとが一致した場合には、そのノードから目的地のノードまでの経路として記憶された経路を利用し、そのノードから目的地のノードまでの経路探索を省略する。
【０００４】
【特許文献１】
特開平２−１０５９７２号公報
【０００５】
【発明が解決しようとする課題】
上述したように、従来の経路探索方法は、出発地や目的地の位置が明確に指定されず、複数の出発地や目的地の候補となるノードが存在する場合に経路探索を迅速に行うものであるが、出発地、あるいは目的地の候補となるノードが１つのノードに特定される場合の経路探索を迅速に行うものではない。従って、例えば、ユーザが目的地を特定して経路を探索する際の経路計算時間を短縮することはできない。
【０００６】
本発明は、かかる問題を鑑みてなされたもので、ユーザが目的地を特定して経路を探索する際の経路計算に要する時間を短縮することができる経路計算装置を提供することを目的とする。
【０００７】
【課題を解決するための手段】
請求項１に記載の経路計算装置は、地図データを格納する地図データ格納手段と、地図データ上の地点を記憶する地点記憶手段と、現在位置を検出する位置検出手段と、現在位置を始点とし、地点記憶手段の記憶する地点を終点とする経路を計算する経路計算手段と、経路計算手段の計算した経路を記憶する経路記憶手段と、経路の目的地を設定する目的地設定手段と、目的地設定手段が地点記憶手段の記憶する地点を目的地として設定する場合、地点を終点とする経路を経路記憶手段から抽出し、この抽出した経路に基づいて最終的な経路を設定する経路設定手段とを備えることを特徴とする。
【０００８】
このように、本発明の経路計算装置は、現在位置を始点とし、地点記憶手段に記憶される、例えば、過去に経路の目的地として設定された地点やユーザによって登録された地点等を終点とする経路を計算し、この計算した経路を経路記憶手段に記憶する。そして、目的地設定手段によって設定される目的地が過去に目的地として設定された地点やユーザによって登録された地点である場合には、その地点を終点とする経路記憶手段に記憶されている経路に基づいて最終的な経路を設定する。
【０００９】
これにより、目的地設定手段によって目的地が設定された場合の経路計算の処理が省略されるため、その結果、経路計算に要する時間を大幅に短縮することができる。
【００１０】
請求項２に記載の経路計算装置では、経路計算手段は、周期的に経路計算を実行し、経路記憶手段は、経路計算手段によって計算された最新の経路を記憶することを特徴とする。これにより、本発明の経路計算装置が車両等の移動体に搭載され、移動中に経路計算をする場合であっても、最新の現在位置を始点とする経路を記憶することができる。
【００１１】
請求項３に記載の経路計算装置によれば、経路設定手段は、経路記憶手段から抽出した経路の始点と位置検出手段の検出する現在位置とが異なる場合、経路計算手段に対して現在位置から始点までの経路計算を指示し、経路計算手段によって計算される現在位置から始点までの経路と経路記憶手段から抽出した経路とによって構成される経路を最終的な経路として設定することを特徴とする。
【００１２】
すなわち、所定時間毎に経路計算を実行していても、経路記憶手段から抽出した経路の始点と現在位置とが異なる場合がある。そこで、位置検出手段の検出する現在位置から経路の始点までの経路を計算し、この計算した経路を経路記憶手段の記憶する経路に含めて最終的な経路とする。これにより、目的地設定手段によって目的地が設定された場合には、現在位置から経路の始点までの経路を計算すればよいため、その結果、経路計算に要する時間を短縮することができる。
【００１３】
請求項４に記載の経路計算装置では、地点記憶手段は、地図データ上の地点に対し、経路の目的地として設定された回数を地点に関連付けて記憶し、地点記憶手段が複数の地点を記憶する場合、経路計算手段は、経路の目的地として設定された回数に応じて地点毎の経路計算の頻度を設定し、この設定された頻度に従って各地点を終点とする経路を計算することを特徴とする。
【００１４】
例えば、経路計算の対象となる地点の数が多い場合、所定時間毎に経路計算を実行すると各地点の経路計算の時間間隔が長くなる。その結果、各経路の始点と現在位置との距離が長くなる。しかしながら、経路計算の対象となる地点のうち、目的地として設定された回数が多い地点ほど、次回に目的地として設定される確率は高いと想定される。
【００１５】
従って、目的地として設定された回数の多い地点ほど頻繁に経路計算を実行することで、次回に目的地として設定される確率の高い地点の経路ほど、その経路の始点と現在位置との距離が短くなる。その結果、次回に目的地として設定される確率の高い地点が目的地として設定された場合には、経路の始点から現在位置までの経路計算の時間を短縮することができる。
【００１６】
請求項５に記載の経路計算装置では、地点記憶手段が複数の地点を記憶する場合、経路計算手段は、現在位置から各地点までの距離に応じて経路計算の繰り返し頻度を設定し、この設定された頻度に従って各地点を終点とする経路を計算することを特徴とする。
【００１７】
一般に、地点記憶手段に記憶される各地点のうち、現在位置からの距離が短い地点ほど目的地として設定される確率は高いと想定される。従って、現在位置からの距離が短い地点ほど頻繁に経路計算を実行することで、次回に目的地として設定される確率の高い地点の経路ほど、その経路の始点と現在位置との距離が短くなる。これにより、現在位置から経路の始点までの経路計算に要する時間を短縮することができるため、その結果、経路計算に要する時間が短縮される。なお、請求項６に記載のように、経路計算手段は、現在位置から各地点までの経路計算に要した時間に応じて経路計算の繰り返し頻度を設定し、この設定された頻度に従って各地点を終点とする経路を計算することで、距離に応じて設定される経路計算の繰り返し頻度と同じような設定とすることができる。その結果、同様な作用効果が期待できる。
【００１８】
請求項７に記載の地点記憶手段は、少なくとも経路の目的地として設定された地点、及び予め登録された地点を記憶することを特徴とする。これらの地点は、経路の目的地として設定されることが多い。そのため、これらの地点を記憶しておくことで、過去に目的地として設定した地点を参照することができる。
【００１９】
【発明の実施の形態】
以下、本発明の実施の形態における経路計算装置に関して、図面に基づいて説明する。なお、本発明の経路計算装置を車両等に搭載されるナビゲーション装置の一機能として実現した例について説明する。
【００２０】
図１は、本実施形態に係わるナビゲーション装置の概略構成を示すブロック図である。同図に示すように、本実施形態のナビゲーション装置１００は、位置検出器１、地図データ入力器６、操作スイッチ群７、外部メモリ９、表示装置１０、音声入出力装置１１、リモコンセンサ１２、及びこれらと接続する制御回路８によって構成される。
【００２１】
制御回路８は、通常のコンピュータとして構成されており、内部には周知のＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれらの構成を接続するバスラインが備えられている。ＲＯＭには、ナビゲーション装置１００が実行するためのプログラムが書き込まれており、このプログラムに従ってＣＰＵ等が所定の演算処理を実行する。
【００２２】
位置検出器１は、いずれも周知の地磁気センサ２、ジャイロスコープ３、距離センサ４、及び衛星からの電波に基づいて車両の位置を検出するＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）のためのＧＰＳ受信機５を有している。これらは、各々が性質の異なる誤差を持っているため、複数のセンサにより各々補完しながら使用するように構成されている。なお、各センサの精度によっては位置検出器１を上述した内の一部で構成してもよく、更に、図示しないステアリングの回転センサ、各転動輪の車速センサ等を用いてもよい。
【００２３】
地図データ入力器６は、地図データ、背景データ、目印データ等を含む各種データを入力するための装置である。各種データを記憶する記憶媒体としては、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の再生専用の記憶媒体が一般に用いられるが、メモリカードやハードディスク等の書き込み可能な記憶媒体を用いてもよい。ここで、地図データを構成するリンクデータ及びノードデータについて説明する。
【００２４】
先ず、リンクとは、地図上の各道路を交差・分岐・合流する点等の複数のノードにて分割し、それぞれのノード間をリンクとして規定されるものであり、リンクを接続することにより道路が構成される。リンクデータは、リンクを特定する固有番号（リンクＩＤ）、リンクの長さを示すリンク長、リンクの始端と終端の座標、道路名称、道路種別、道路幅員、車線数等の各データから構成されている。
【００２５】
また、ノードデータ（図示せず）は、地図上の各道路が交差、合流、分岐するノード毎に固有の番号を付したノードＩＤ、ノード座標、ノード名称、ノードに接続する全てのリンクのリンクＩＤが記述される接続リンクＩＤ、交差点種類等の各データから構成されている。
【００２６】
操作スイッチ群７は、例えば、表示装置１０と一体になったタッチスイッチもしくはメカニカルなスイッチ等が用いられ、表示装置１０の画面に表示される地図のスクロール操作、文字入力、キー選択等の各種入力に使用される。
【００２７】
外部メモリ９は、例えば、メモリカードやＨＤＤ等の大容量の読み書き可能な記憶媒体が用いられる。制御回路８は、この外部メモリ９に計算結果を一時的に記憶する。また、外部メモリ９には、例えば、ユーザによって登録された地点（以下、メモリ地点と呼ぶ）や、後述する経路案内機能において過去に目的地として設定された住所・電話番号・施設等の地点（以下、目的地履歴地点と呼ぶ）を記憶する。さらに、目的地履歴地点には、過去に目的地として設定された回数を関連付けて記憶している。なお、メモリ地点についても、過去に目的地として設定された場合には、その設定された回数が関連付けて記憶されている。
【００２８】
表示装置１０は、例えば液晶ディスプレイによって構成され、表示装置１０の画面には位置検出器１から入力された車両の現在位置に対応する自車位置マークと、地図データ入力器６より入力された地図データ、背景データ、及び目印データによって生成される車両周辺の地図を表示することができる。
【００２９】
音声入出力装置１１は、図示しない入力装置及び出力装置から構成される。入力装置は、ユーザの発話内容を認識して、ナビゲーション装置１００の各種入力に用いるものである。一方、出力装置は、スピーカやオーディオアンプ等から構成されるもので、音声案内等に用いられる。
【００３０】
ナビゲーション装置１００は、操作スイッチ群７やリモコン１３等から目的地設定のメニュー画面を表示させる入力が行われると、図４に示す目的地設定メニューを表示装置１０の画面に表示する。そして、例えば、同図中の「５０音」を選択して、目的地として設定すべき施設名称を入力すると、現在位置を出発地とし、この入力した施設名称の施設が位置する地点を目的地とする最適な経路を自動的に探索して案内経路を計算して表示装置１０へ表示する（経路案内機能）。
【００３１】
このような自動的に最適な経路を設定する手法は、例えば、周知のダイクストラ法によるコスト計算、すなわちリンク長、道路種別、道路幅員等を用いた評価値計算を行って算出する。ここで、本実施形態におけるコスト計算について説明する。
【００３２】
先ず、出発地から目的地までをカバーする地図データを地図データ入力器６から読み出し、制御回路８のＲＡＭ等に記憶する。そして、その記憶された地図データを用いて、出発地から目的地までのコストの合計が最小となる経路を設定する。
【００３３】
例えば、図１１に示すような、出発地３０から目的地４０までの経路を設定する場合、まず、出発地３０のコストをゼロ、その他の交差・分岐・合流地点（ノードｎ１〜ｎ６）についてはコストを未設定とする。そして、出発地３０から進入することのできるノードについて、使用する道路のコストを加算して、それぞれのノードのコストとして設定する（コスト伝播）。
【００３４】
次に、コストが新規に設定されたノードについて、接続する次のノードにコスト伝播を行う。このコスト伝播は、すべてのノードに新規にコスト設定が出来なくなった場合、もしくは、目的地４０のコストに変化がなくなった場合に終了する。
【００３５】
そして、出発地３０から目的地４０までのコストが最小となる経路が案内経路として最終的に設定される。例えば、図１１に示すように、出発地３０からノードｎ４を介して目的地４０へ向かう経路が設定される。この最終的に設定された経路は、複数のリンクＩＤからなる列として特定され、制御回路８のＲＡＭに記憶される。
【００３６】
なお、本実施形態におけるナビゲーション装置１００は、ナビゲーション装置１００に電源が投入され、その後、車両の現在位置の検出が開始されると、この現在位置を始点とし、外部メモリ９に記憶されるメモリ地点や目的地履歴地点を終点とする経路を周期的に計算する。この計算された経路は、外部メモリ９に記憶される。なお、この経路計算は、ナビゲーション装置１００の処理負荷が低い場合に周期的に行ってもよいし、ナビゲーション装置１００の処理能力が高い場合には、所定時間毎に行ってもよい。
【００３７】
そして、図４に示す目的地設定メニューの中から「メモリ地点」や「目的地履歴」が選択されると、サブメニュー画面を表示して、メモリ地点の名称を示すリストや、目的地履歴地点の名称を示すリストを表示する。このサブメニュー画面のリストの中から、ユーザの希望する地点の名称が選択されると、本実施形態のナビゲーション装置１００は、ユーザによって選択された地点を終点とする、既に計算済みの経路を外部メモリ９から読み出し、この読み出した経路を案内経路として画面に表示し、経路案内を開始する。
【００３８】
次に、本実施形態の特徴部分に係わる経路案内機能の処理について、図２及び図３に示すフローチャートを用いて説明する。まず、ナビゲーション装置１００に電源が投入され、位置検出器１によって車両の現在位置の検出が開始されると、図２のステップＳ１００に示すように、外部メモリ９に記憶されるメモリ地点や目的地履歴地点を終点とし、現在位置を始点とする経路を地点毎に順番に計算する。なお、計算する順番は特に限定するものではない。
【００３９】
例えば、図７に示すように、メモリ地点が（ａ）刈谷郵便局、（ｂ）名古屋駅、（ｃ）名古屋市中区栄付近の３つの地点であり、目的地履歴地点が（ｄ）刈谷郵便局、（ｅ）刈谷市昭和町１−１、（ｆ）刈谷市恩田町付近の３つの地点であるとする。
【００４０】
この場合、重複する（ｄ）刈谷郵便局を除く、（ａ）刈谷郵便局、（ｂ）名古屋駅、（ｃ）名古屋市中区栄付近、（ｅ）刈谷市昭和町１−１、（ｆ）刈谷市恩田町付近の５つの地点について、各地点を終点とし、現在位置を始点とする経路を計算して、計算した各経路を外部メモリ９へ記憶する。このメモリ地点や目的地履歴地点に対する経路計算は、所定時間毎に繰り返し実行される。これにより、最新の現在位置を始点とする経路が記憶される。
【００４１】
一方、図３に示すステップＳ２００では、ユーザによって目的地設定のメニュー画面を表示させる入力が行われ、図４に示した目的地設定メニューの中から「メモリ地点」、あるいは、「目的地履歴」が選択されると、ステップＳ２１０へ処理を進める。また、図４中のそれ以外の「５０音」や「施設」等が選択された場合には、ステップＳ２２０にて、ユーザによって指定される地点への通常の経路計算を行う。
【００４２】
また、ステップＳ２００では、図４に示した目的地設定メニューの中から「メモリ地点」が選択されると、図５に示すメモリ地点のリスト画面を表示し、又は、「目的地履歴」が選択されると、図６に示す目的地履歴地点のリスト画面を表示する。
【００４３】
ステップＳ２１０では、図５に示すメモリ地点のリスト、又は、図６に示す目的地履歴のリストの中から目的地として設定すべき地点の名称が選択されると、その選択された名称の地点を終点とする、既に経路計算済みの経路を外部メモリ９から読み出す。
【００４４】
ステップＳ２３０では、ステップＳ２１０で読み出した経路、もしくは、ステップＳ２２０にて計算した経路を案内経路として画面に表示し、ステップＳ２４０では経路案内を開始する。
【００４５】
このように、本実施形態のナビゲーション装置１００は、車両の現在位置を始点とし、外部メモリ９に記憶されるメモリ地点や目的地履歴地点を終点とする経路を周期的に計算し、この計算した経路を外部メモリ９へ記憶する。そして、ユーザがメモリ地点や目的地履歴地点を経路の目的地として設定する場合には、外部メモリ９に記憶される既に計算済みの経路のうち、その目的地の地点を終点とする経路を読み出して経路案内を開始する。これにより、ユーザによって目的地が設定された後の経路計算の処理が省略されるため、その結果、経路計算に要する時間を大幅に短縮することができる。
【００４６】
（変形例１）
例えば、車両が移動している場合には、図２に示したステップＳ１００の処理を周期的に繰り返して実行していても、図３に示したステップＳ２１０にて読み出される経路の始点と車両の現在位置とが異なることがある。すなわち、例えば、図１２のように、車両の現在位置２０と、外部メモリ９から読み出した経路の出発地３０とが異なることがある。
【００４７】
このような場合には、図３に示すステップＳ２１０にて、外部メモリ９から読み出した計算済みの経路の始点と車両の現在位置とが一致するか否かを判定し、両地点が一致しない場合には、図１２に示すように、現在位置２０から出発地３０までの経路を計算し、この計算した経路を外部メモリ９から読み出した経路とを結合させて、最終的な経路とする。
【００４８】
これにより、目的地設定手段によって目的地が設定された場合には、現在位置から経路の始点までの経路を計算すればよいため、その結果、経路計算に要する時間を短縮することができる。
【００４９】
なお、車両の現在位置が計算済みの経路の始点よりも経路の終点に近づいた地点に位置する場合には、車両の現在位置から最短経路で計算済みの経路へ合流することのできる経路を計算し、計算済みの経路へ合流する経路を最終的な経路としてもよい。
【００５０】
（第２の実施形態）
第２の実施形態は、第１の実施形態によるものと共通するところが多いので、以下、共通部分についての詳しい説明は省略し、異なる部分を重点的に説明する。
【００５１】
第１の実施形態では、図２に示したステップＳ１００において、外部メモリ９に記憶されているメモリ地点や目的地履歴地点を終点とする経路計算を地点毎に順番に行っているが、本実施形態では、これら各地点の目的地として設定された回数を参照し、この回数が多い地点ほど頻繁に経路計算を実行する点で異なる。
【００５２】
すなわち、図２に示したステップＳ１００において、経路計算の対象となるメモリ地点や目的地履歴地点の数が多い場合には、各地点の経路計算の時間間隔が長くなる。その結果、各経路の始点と現在位置との距離が長くなる。しかしながら、外部メモリ９に記憶されるメモリ地点や目的地履歴地点のうち、目的地として設定された回数が多い地点ほど、次回に目的地として設定される確率は高いと想定される。
【００５３】
従って、目的地として設定された回数の多い地点ほど頻繁に経路計算を実行することで、次回に目的地として設定される確率の高い地点の経路ほど、その経路の始点と現在位置との距離が短くなる。その結果、次回に目的地として設定される確率の高い地点が目的地として設定された場合には、変形例１にて説明した経路の始点から現在位置までの経路計算の時間を短縮することができる。
【００５４】
次に、本実施形態の特徴部分に係わる経路案内機能の処理について、図１３に示すフローチャートを用いて説明する。なお、目的地設定に係わる処理は第１の実施形態で説明した処理と同一であるため、説明を省略する。
【００５５】
まず、ナビゲーション装置１００に電源が投入され、位置検出器１によって車両の現在位置の検出が開始されると、図１３に示すステップＳ１０では、外部メモリ９に記憶されているメモリ地点や目的地履歴地点の総数が所定数（ｎ）未満であるか否かを判定する。
【００５６】
ここで、肯定判定される場合には、第１の実施形態において説明したステップＳ１００へ処理を進め、否定判定される場合にはステップＳ１１０へ処理を移行する。なお、所定数（ｎ）は、ナビゲーション装置１００の処理能力に基づいて決定されるものである。
【００５７】
外部メモリ９に記憶されているメモリ地点や目的地履歴地点の総数が所定数（ｎ）以上の場合には、ステップＳ１１０において、外部メモリ９に記憶されるメモリ地点や目的地履歴地点の目的地設定回数を参照し、この目的地設定回数の多い地点ほど経路計算を頻繁に行うように経路計算の順序を設定する。そして、この設定された順序に従って経路計算を繰り返し行う。
【００５８】
例えば、図８に示すように、（ａ）刈谷郵便局、（ｂ）名古屋駅、（ｃ）名古屋市中区栄付近、（ｅ）刈谷市昭和町１−１、（ｆ）刈谷市恩田町付近の５つの地点が経路計算の対象となる地点であるとき、各地点の目的地設定回数を抽出する。そして、目的地設定回数の多い地点ほど経路計算を頻繁に行うように経路計算の順序を設定する。
【００５９】
この経路計算の順序の設定については、様々な設定方法が考えられるため、目的地設定回数の多い地点ほど頻繁に経路計算が行われる設定であれば、特にその設定方法を限定するものではない。
【００６０】
なお、本実施形態では、図８に示すように、例えば、経路計算の対象となる地点のうち、目的地設定回数の最も多い地点（ｂ）を経路計算を行う第１番目に設定し、設定した地点（ｂ）の目的地設定回数を１回分差し引いて、地点（ｂ）の目的地設定回数を「５」とする。次に、目的地設定回数の最も多い地点（ｂ）を経路計算を行う第２番目に設定し、設定した地点（ｂ）の目的地設定回数を１回分差し引いて、地点（ｂ）の目的地設定回数を「４」とする。
【００６１】
次いで、目的地設定回数の最も多い地点は、地点（ｂ）と地点（ｃ）であるが、始めて設定される地点（ｃ）を経路計算を行う第３番目に設定し、地点（ｂ）を第４番目に設定する。そして、設定した地点（ｂ）、地点（ｃ）の目的地設定回数を１回分差し引く。以後、経路計算の対象となる全ての地点の目的地設定回数が「０」になるまで、上述の設定を繰り返すことで、図８に示す経路計算の順序が設定される。
【００６２】
そして、ステップＳ１１０では、この設定された経路計算の順序に従って、各地点を終点とし、現在位置を始点とする経路を計算して、計算した各経路を外部メモリ９へ記憶する。
【００６３】
このように、本実施形態におけるナビゲーション装置は、目的地設定回数の多い地点ほど経路計算の繰り返し頻度が高くなるように経路計算の順序を設定し、この設定された順序に従って各地点を終点とする経路を計算する。
【００６４】
これにより、目的地設定回数の多い地点ほど頻繁に経路計算が実行されるため、次回に目的地として設定される確率の高い地点の経路ほど、その経路の始点と現在位置との距離が短くなる。その結果、次回に目的地として設定される確率の高い地点が目的地として設定された場合には、変形例１にて説明した経路の始点から現在位置までの経路計算の時間を短縮することができる。
【００６５】
（変形例２）
本実施形態では、目的地設定回数の多い地点ほど経路計算の繰り返し頻度が高くなるように経路計算の順序を設定しているが、図９に示すように、各地点の現在位置からの距離が短い地点ほど、経路計算の繰り返し頻度が高くなるように経路計算の順序を設定してもよいし、図１０に示すように、各地点の経路計算に要する時間の短い地点ほど、経路計算の繰り返し頻度が高くなるように経路計算の順序を設定してもよい。
【００６６】
一般に、外部メモリ９に記憶されるメモリ地点や目的地履歴地点のうち、現在位置からの距離が短い地点ほど目的地として設定される確率は高いと想定される。従って、現在位置からの距離が短い地点ほど頻繁に経路計算を実行することで、次回に目的地として設定される確率の高い地点の経路ほど、その経路の始点と現在位置との距離が短くなる。これにより、現在位置から経路の始点までの経路計算に要する時間を短縮することができるため、その結果、経路計算に要する時間が短縮される。
【００６７】
また、現在位置から各地点までの経路計算に要した時間が短い地点ほど、現在位置からの距離が短いため、経路計算に要する時間の短い地点ほど経路計算の繰り返し頻度が高くなるように経路計算の順序を設定する。これにより、距離に応じて設定される経路計算の繰り返し頻度と同じような設定とすることができる。
【図面の簡単な説明】
【図１】第１の実施形態に係わる、ナビゲーション装置１００の概略構成を示すブロック図である。
【図２】第１の実施形態に係わる、外部メモリ９に記憶されるメモリ地点や目的地履歴地点を対象として経路計算の処理を示すフローチャートである。
【図３】第１の実施形態に係わる、経路案内機能の処理を示すフローチャートである。
【図４】第１の実施形態に係わる、目的地設定メニューの画面表示を示したイメージ図である。
【図５】第１の実施形態に係わる、メモリ地点名称の画面表示を示したイメージ図である。
【図６】第１の実施形態に係わる、目的地履歴地点名称の画面表示を示したイメージ図である。
【図７】第１の実施形態に係わる、経路計算の対象となるメモリ地点と目的地履歴地点を示す図である。
【図８】第２の実施形態に係わる、経路計算の順序の設定例を示した図である。
【図９】第２の実施形態の変形例２に係わる、現在位置からの距離に応じて経路計算の順序を設定する例を示した図である。
【図１０】第２の実施形態の変形例２に係わる、経路計算時間に応じて経路計算の順序を設定する例を示した図である。
【図１１】第１の実施形態に係わる、コスト計算を説明する図である。
【図１２】第１の実施形態の変形例１に係わる、車両の現在位置２０と、外部メモリ９から読み出した経路の出発地３０とが異なることを示す図である。
【図１３】第２の実施形態に係わる、経路案内機能の処理を示すフローチャートである。
【符号の説明】
１  位置検出器
６  地図データ入力器
７  操作スイッチ群
８  制御回路
９  外部メモリ
１０  表示装置
１１  音声入出力装置
１２  リモコンセンサ
１３  リモコン
１００  ナビゲーション装置
【図１】
2004333443.tif 000003
【図２】
2004333443.tif 000004
【図３】
2004333443.tif 000005
【図４】
2004333443.tif 000006
【図５】
2004333443.tif 000007
【図６】
2004333443.tif 000008
【図７】
2004333443.tif 000009
【図８】
2004333443.tif 000010
【図９】
2004333443.tif 000011
【図１０】
2004333443.tif 000012
【図１１】
2004333443.tif 000013
【図１２】
2004333443.tif 000014
【図１３】
2004333443.tif 000015