経路探索装置
【課題】予め登録された目的地と経由地を読み出して、前回と同じ目的地へ向かう経路を探索する場合、出発地が前回と異なる場合にも最適な経路を探索することができる経路探索装置を提供する。
【解決手段】外部メモリに目的地Ｇａとその目的地Ｇａに関連付けた優先ポイントｕ１〜ｕ７を登録し、その登録した目的地Ｇａを外部メモリから読み出して経路探索する場合、経路の出発地（自車位置）によって、目的地Ｇａに関連付けられた優先ポイントｕ１〜ｕ７のうち、経由地とすべき優先ポイントを変更する。
【解決手段】外部メモリに目的地Ｇａとその目的地Ｇａに関連付けた優先ポイントｕ１〜ｕ７を登録し、その登録した目的地Ｇａを外部メモリから読み出して経路探索する場合、経路の出発地（自車位置）によって、目的地Ｇａに関連付けられた優先ポイントｕ１〜ｕ７のうち、経由地とすべき優先ポイントを変更する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カーナビゲーションシステムに好適な経路探索装置に関するものである。
【背景技術】
【０００２】
従来、特許文献１に記載の走行位置表示装置では、経路検索処理において入力した目的地や経由地をメモリに登録する際、地点登録キーを押した場合には、当該キーを押した際のその地点を中心とした地図データを画像メモリに登録することで、当該キーを押さなかった場合と区別して登録する。
【０００３】
また、特許文献２に記載の車載用ナビゲーション装置では、ユーザが経由地として望む特定の複数の地点を１グループとして登録しておき、目的地が設定されている状態で、予め登録されている経由地グループが指定された場合には、その指定されたグループに含まれる各経由地を通る誘導経路を探索する。この誘導経路の探索処理では、自車位置と目的地の位置関係を考慮した最適な誘導経路（例えば、指定された経由地グループに含まれる各経由地を自車位置から近い順番に設定して目的地まで探索した誘導経路、あるいは、目的地までのトータルの距離又は所要時間が最短となるように各経由地の順番を設定して探索した誘導経路）を探索する。
【特許文献１】特開平７−１３４７９８号公報
【特許文献２】特開２００６−１７７７９２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ユーザは、経路探索装置が探索した経路よりも有益な経路を知っている場合、経路の途中に経由地を設定することでカスタマイズが可能となるが、次回も同じ経路とする場合、目的地と経由地の設定について、同じ手順を踏んで設定しなければならない。この場合、上記特許文献２に記載の技術を発展させ、経由地を目的地と関連付けて予め登録しておけば、次回に経路探索を行う場合、登録済みの目的地とそれに関連付けられた経由地を読み出して設定することで、目的地と経由地の設定が容易になる。
【０００５】
しかしながら、次回に経路探索を行う場合、出発地（自車位置）が前回と異なるとき、登録された全ての経由地を再度経由地として設定した場合には遠回りになる経路を探索することがある。
【０００６】
本発明は、上記の問題を鑑みてなされたもので、予め登録された目的地と経由地を読み出して、前回と同じ目的地へ向かう経路を探索する場合、出発地が前回と異なる場合にも最適な経路を探索することができる経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するためになされた請求項１記載の経路探索装置は、
経路の目的地と、その目的地へ向かう経路の経由地とされた地点とを関連付けて登録する地点登録手段と、
地点登録手段が登録した目的地、及びその目的地に関連付けられた地点を読み出す地点読出し手段と、
地点読出し手段の読み出した目的地への経路を探索する経路探索手段を備えるものであって、
経路探索手段は、
出発地から地点読み出し手段が読み出した目的地へ向かう経路を探索する第１経路探索手段と、
目的地に関連付けて登録された地点のうち、第１経路探索手段の探索した経路の付近に存在する地点を経由地としたうえで、出発地から目的地へ向かう経路を探索する第２経路探索手段と、を備えることを特徴とする。
【０００８】
これにより、第１経路探索手段の探索した経路の付近に存在せず、その経路から離れた地点については、経由地として含めないようにすることができるので、出発地が前回と異なる場合にも、遠回りになることのない最適な経路を探索することが可能となる。
【０００９】
請求項２に記載の経路探索装置では、経路探索手段は、
目的地に関連付けて登録された地点と、第１経路探索手段の探索した経路との距離が所定距離以内であるかどうかを判定する距離判定手段を備え、
第２経路探索手段は、距離判定手段が所定距離以内であると判定した地点を経由地としたうえで探索することを特徴とする。
【００１０】
これにより、第１経路探索手段の探索した経路との距離が所定距離以内である地点を経由地とすることができる。
【００１１】
請求項３に記載の経路探索装置によれば、距離判定手段は、地点登録手段に目的地とは異なる他の目的地に関連付けられた地点が登録されている場合、その登録されている地点と第１経路探索手段の探索した経路との距離が所定距離以内であるかどうかについても判定することを特徴する。
【００１２】
これにより、他の目的地に関連付けられた地点と第１経路探索手段の探索した経路との距離が所定距離以内である場合には、その地点を経路の経由地に含めることが可能となる。
【００１３】
請求項４に記載の経路探索装置は、
地点読出し手段が地点登録手段から目的地、及びその目的地に関連付けられた地点を読み出した際に、当該目的地に対する新たな地点を追加する地点追加手段を備え、
地点登録手段は、地点追加手段の追加した新たな地点を目的地に関連付けて登録することを特徴とする。
【００１４】
これにより、新たな地点を追加した場合、その新たな地点を目的地に関連付けて登録することができる。
【００１５】
請求項５に記載の経路探索装置によれば、第１経路探索手段、及び第２経路探索手段は、目的地へ向かう複数の経路を探索するものであり、
第１経路探索手段、及び第２経路探索手段の少なくとも一方が探索した複数の経路について、１つの経路毎に経路の行程を順次画面に表示する表示制御手段を備えることを特徴とする。これにより、経路毎の行程をユーザに提供することができるようになる。
【００１６】
なお、請求項６に記載のように、表示制御手段は、第１経路探索手段の探索した各々の経路と、その各々の経路の経由地とした地点との距離の長短に基づいて、画面に表示する際の順序を決定する表示順序決定手段を備えることが好ましい。これにより、各々の経路と、各々の経路の経由地とした地点との距離が短い順に、順次画面に表示することが可能となるからである。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施形態について図面を用いて説明する。本実施形態では、本発明の経路探索装置の機能をカーナビゲーションシステムの機能として採用した場合について説明する。図１におけるカーナビゲーションシステムは、位置検出器１、地図データ入力装置６、操作スイッチ群７、リモコンセンサ８、リモートコントローラ（リモコン）９、外部メモリ１１、表示装置１２、及び、これら各装置が接続された制御装置１０から構成されている。
【００１８】
地図データ入力装置６は、ＨＤＤ（Hard Disk Drive）、ＤＶＤ−ＲＯＭ（Digital Versatile Disk−Read Only Memory）、ＣＤ（Compact Disc）−ＲＯＭ等のドライブ装置であり、ハードディスクやＤＶＤ−ＲＯＭメディア、ＣＤ−ＲＯＭメディア等の地図データソース（図示せず）から地図データを読取可能に構成されている。
【００１９】
地図データソースには、道路地図データや位置検出精度向上のためのマップマッチング用データを含む各種データが記憶されている。ここで、道路地図データを構成するリンクデータ、ノードデータ、索引データ、描画データについて説明する。先ず、リンクとは、地図上の各道路を交差・分岐・合流する点等の複数のノードにて分割し、それぞれのノード間をリンクとして規定されるものであり、リンクを接続することにより道路が構成される。
【００２０】
リンクデータは、リンクを特定する固有番号（リンクＩＤ）、リンクの長さを示すリンク長、リンクの始端及び終端ノード座標（緯経度）、道路名称、道路種別、道路幅員、車線数等の各データから構成されている。ノードデータは、地図上の各道路が交差・分岐・合流するノード毎に固有の番号を付したノードＩＤ、ノード座標（緯経度）、ノードに接続する全てのリンクのリンクＩＤが記述される接続リンクＩＤ等の各データから構成されている。
【００２１】
索引データは、施設等の検索に用いられるデータであり、施設、道路、道路の分岐・合流・交差する地点等の名称、施設種別、住所、電話番号、位置座標（緯経度）等の情報で構成されている。描画データは、地図表示に用いられるデータであり、海（湖、池等も含む）や山等の地形、施設、道路、道路の分岐地点、道路の合流地点、道路の交差点等の表示文字、表示位置（緯経度）、ポリゴン、目印（ランドマーク等）の情報で構成されている。
【００２２】
操作スイッチ群７は、例えば、表示装置１２と一体になったタッチスイッチもしくはメカニカルなスイッチ等が用いられ、表示装置１２の画面に表示される道路地図のスクロール操作や文字入力等の各種入力に使用される。
【００２３】
外部メモリ１１は、経路の目的地、及びその経路の経由地とされた地点（以下、優先ポイント）の履歴の登録（書き込み）や、登録した情報を読み出すためのメモリであり、経路の目的地と、その目的地へ向かう経路上の優先ポイントとを関連付けて（セットで）登録する。外部メモリ１１は、グループ番号、地点の種別（目的地／優先ポイント）、名称、座標（緯経度）を登録情報とし、地点種別が目的地である１つの地点に対し、地点種別が優先ポイントである１つ以上の地点を関連付けて（セットで）、１つのグループとして登録する。
【００２４】
表示装置１２は、例えば液晶ディスプレイによって構成され、表示装置１２の画面には位置検出器１から入力された自車位置に対応する自車位置マークと、地図データ入力装置６より入力された道路地図データによって生成される自車周辺の道路地図を表示することができる。
【００２５】
本カーナビゲーションシステムは、操作スイッチ群７やリモコンセンサ８を介してリモコン９等から目的地が設定されると、自車位置（若しくは任意の地点）を出発地とする目的地へ向かう最適な経路を自動的に計算し、案内すべき経路を形成し表示する、いわゆる経路設定機能を備えている。このような自動的に最適な経路を計算する手法は、例えば、周知のダイクストラ法によるコスト計算、すなわち、リンクのリンク長、車線数、道路幅員等を考慮してリンク毎に付されるコストを用いて、最小のコストで目的地に到達する経路を計算する方法が採用される。
【００２６】
これらの機能は、主に制御装置１０によって各種の演算処理がなされることによって実行される。すなわち、制御装置１０は目的地が設定されると、地図データ入力装置６の道路地図データを用いて複数の経路（本実施形態では５つの経路）を計算し、その５つの経路を表示装置１２へ表示させる。そして、５つの経路の中からユーザが所望する１つの経路が選択されると、その選択された経路の分岐地点や右左折すべき交差点において道路地図の拡大や音声案内を行う。
【００２７】
次に、本カーナビゲーションシステムにおける経路設定機能の動作について、図２に示すフローチャートを参照しながら説明する。先ず、図２に示すステップＳ１では、図３に示す目的地・優先ポイント入力処理を実行する。図３のステップＳ１１では、目的地を外部メモリ１１から選択するかどうかを判定する。このステップＳ１１で肯定判断した場合にはステップＳ１３へ処理を進め、否定判断した場合にはステップＳ１２へ処理を進める。
【００２８】
ステップＳ１２では、操作スイッチ群７やリモコン９等からの目的地とすべき地点の入力を行い、この入力された地点を目的地に設定する。ステップＳ１３では、外部メモリ１１に登録されている目的地の読み出しを行うとともに、その読み出した全ての目的地の名称を示すリストを表示装置１２の画面に表示して、ユーザが希望する目的地を選択させる。ここで、選択された目的地に関連付けられた優先ポイントが有る（登録されている）場合には、その目的地と優先ポイントの位置を示す道路地図を表示するようにしてもよい。ユーザが希望する目的地が選択されると、この選択された目的地を新たな目的地として設定する。
【００２９】
ステップＳ１４では、ステップＳ１２又はステップＳ１３にて設定した目的地へ向かう際の優先ポイントを設定するかどうかを判定する。このステップＳ１４にて優先ポイントを設定する旨の入力操作をユーザが行った場合（肯定判断の場合）にはステップＳ１５へ処理を進め、優先ポイントを設定しない旨の入力操作をユーザが行った場合（否定判断の場合）には本処理を終了する。
【００３０】
ステップＳ１５では、設定した目的地に関連付けて登録された優先ポイントが有るかどうかを判断する。このステップＳ１５にて肯定判断した場合にはステップＳ１６へ処理を進め、否定判断した場合にはステップＳ１７へ処理を進める。ステップＳ１６では、設定した目的地に関連付けて登録された全ての優先ポイントを読み出して、設定した目的地に対応する優先ポイントとして設定する。ステップＳ１７では、目的地付近の道路地図を表示するとともに、優先ポイントの入力をユーザに促して、操作スイッチ群７やリモコン９等からの優先ポイントの入力を待つ。
【００３１】
ステップＳ１８では、優先ポイントを追加するかどうかを判断する。このステップＳ１８にて優先ポイントを追加する旨の入力操作をユーザが行った場合（肯定判断の場合）にはステップＳ１７へ処理を進め、上述した処理を繰り返す。一方、ステップＳ１８にて優先ポイントを追加しない旨の入力操作をユーザが行った場合（否定判断の場合）には本処理を終了する。
【００３２】
図２のステップＳ２では、図３の目的地・優先ポイント入力処理にて設定された目的地と、優先ポイントとを関連付けて外部メモリ１１に登録する。これにより、図３の目的地・優先ポイント入力処理にて目的地とその目的地に関連付けられた優先ポイントを読み出した際に、目的地に対する新たな優先ポイントを追加した場合、その新たな優先ポイントを目的地に関連付けて外部メモリ１１に登録することができる。
【００３３】
図２のステップＳ３では、図４に示す経路探索処理を実行する。図４のステップＳ３１では、現在の自車位置（若しくは、任意の地点）を出発地とし、図３の目的地・優先ポイント入力処理にて設定した目的地へ向かう５つの経路を計算する（第１経路探索手段）。ステップＳ３２では、ステップＳ２にて目的地に関連付けて登録された優先ポイントと、ステップＳ３１にて計算した各々の経路との（直線）距離が所定距離（例えば、１００ｍ）以内であるかどうかを判定する。
【００３４】
このステップＳ３２では、図５に示す三角法によって直線距離を算出する。なお、以下の算出方法はその一例であるので、その他の手法を採用してもよい。先ず、優先ポイントｕ２と経路との直線距離Ｌｄを算出する際、座標値が既知である出発地Ｐｐ、ノードｎｄ１、ノードｎｄ２、目的地Ｇｐのうち、狭角θ１、θ２が共に９０度以下となる地点を特定する。この狭角θ１、θ２は、優先ポイントｕ２の座標値と、出発地Ｐｐ、ノードｎｄ１、ノードｎｄ２、目的地Ｇｐの座標値から算出できる。図５の場合、優先ポイントｕ２に対してはノードｎｄ１、ノードｎｄ２が特定される。
【００３５】
すると、直線距離Ｌｄは数式１で算出されることから、この直線距離Ｌｄが所定距離以内であるかどうか判定できる。なお、ノードｎｄ１と優先ポイントｕ２との距離Ｌ１、ノードｎｄ２と優先ポイントｕ２との距離Ｌ２は、各々の地点の座標値から算出できる。
【００３６】
（数１）
Ｌｄ＝Ｌ１×ｓｉｎθ１＝Ｌ２×ｓｉｎθ２
なお、図４の優先ポイントｕ１は、狭角θ１、θ２が共に９０度以下となる地点が特定されないため、座標値が既知である出発地Ｐｐ、ノードｎｄ１、ノードｎｄ２、目的地Ｇｐとの距離を各々算出し、その最小距離が所定距離以下であるかどうか判定すればよい。
【００３７】
このステップＳ３２にて肯定判断した場合にはステップＳ３３へ処理を進め、否定判断した場合には本処理を終了する。ステップＳ３３では、該当する優先ポイントを出発地から目的地へ向かう経路の経由地として設定し、ステップＳ３４では、ステップＳ３３で設定した経由地を通過する５つの経路を再度計算する（第２経路探索手段）。
【００３８】
このように、図４の経路探索処理では、ステップＳ３１にて計算した各経路について、その経路の付近に存在する優先ポイントを経由地として設定して、ステップＳ３４にて再度経路計算を行う。これにより、ステップＳ３１にて計算した各経路の付近に存在せず、その各経路から離れた優先ポイントについては、経由地として含めないようにすることができるので、出発地が前回と異なる場合にも、遠回りになることのない最適な５つの経路を探索することが可能となる。
【００３９】
すなわち、図６に示すように、目的地Ｇａに対して優先ポイントｕ１〜ｕ７が関連付けて外部メモリ１１に登録されている場合には、出発地Ｐａから目的地Ｇａへ向かう経路の経由地として優先ポイントｕ３〜ｕ５が設定されるようになるため、優先ポイントｕ１、ｕ２、ｕ４〜ｕ７は経由地として含まないようにすることができる。また、前回の出発地Ｐａとは場所が大きく異なる出発地Ｐｂから目的地Ｇａへ向かう経路の経由地には優先ポイントｕ１、ｕ２が設定され、優先ポイントｕ３〜ｕ７は経由地として含めないようにすることができるので、出発地が異なっても、遠回りになることのない最適な経路が探索できる。
【００４０】
図２のステップＳ４では、図４の経路探索処理にて探索した５つの経路について、１つの経路毎に経路の行程を順次、表示装置１２の画面に表示する。これにより、経路毎の行程をユーザに提供することができるようになるため、ユーザは所望の経路を選択することができる。なお、表示装置１２の画面に表示する経路の順序については、ステップＳ３１にて計算した各々の経路と、ステップＳ３３にて経由地とした優先ポイントとの距離の長短に基づいて決定するとよい。これにより、各々の経路と、各々の経路の経由地とした優先ポイントとの距離が短い順に、順次画面に表示することが可能となる。
【００４１】
ステップＳ５にて、ユーザの所望する１つの経路が選択されると、ステップＳ６では、優先ポイントを追加するかどうかを判断する。このステップＳ６にて、優先ポイントを追加する旨の入力操作をユーザが行った場合（肯定判断の場合）にはステップＳ７へ処理を進め、一方、優先ポイントを追加しない旨の入力操作をユーザが行った場合（否定判断の場合）には本処理を終了する。
【００４２】
ステップＳ７では、出発地から目的地までの経路の行程を示す道路地図を表示装置１２の画面に表示するとともに、優先ポイントの入力をユーザに促して、操作スイッチ群７やリモコン９等からの優先ポイントの入力を待つ。ステップＳ８では、入力された優先ポイントを経路の目的地に関連付けて外部メモリ１１に追加登録する。
【００４３】
ステップＳ９では、ステップＳ７にて入力した優先ポイントを経由地として含む経路を計算し、ステップＳ１０では、ステップＳ９にて計算した経路の行程を表示装置１２の画面に表示して、経路設定機能が終了する。この経路設定機能が終了すると、ユーザの指示、若しくは、自車位置が経路上に移動することで経路案内を開始する。
【００４４】
このように、本実施形態のカーナビゲーションシステムでは、外部メモリ１１に目的地とその目的地に関連付けた経由地を登録し、その登録した目的地を外部メモリ１１から読み出して経路探索する場合、経路の出発地（自車位置）によって、目的地に関連付けられた優先ポイントのうち、経由地とすべき優先ポイントを変更する。これにより、経路から離れた優先ポイントについては、経由地として含めないようにすることができるので、出発地が前回と異なる場合にも、遠回りになることのない最適な経路を探索することが可能となる。
【００４５】
以上、本発明の好ましい実施形態について説明したが、本発明は上述した実施形態に何ら制限されることなく、本発明の主旨を逸脱しない範囲において、種々変形して実施することができる。
【００４６】
例えば、本実施形態の経路探索処理（図４）では、経由地に設定する優先ポイントの対象を、経路の目的地に関連付けられた優先ポイントに限定しているが、図７に示すように、他の目的地Ｇｂに関連付けられた優先ポイントｕ１１〜ｕ１５が外部メモリ１１に登録されている場合には、その優先ポイントｕ１１〜ｕ１５についても、図４のステップＳ３２の処理を実行してもよい。これにより、他の目的地Ｇｂに関連付けられた優先ポイントｕ１１〜ｕ１５と、ステップＳ３１にて計算した経路との距離が所定距離以内である場合には、その優先ポイントを経路の経由地に含めることが可能となる。
【図面の簡単な説明】
【００４７】
【図１】カーナビゲーションシステムの全体構成図である。
【図２】カーナビゲーションシステムによる経路設定機能の動作を説明するためのフローチャートである。
【図３】目的地・優先ポイント入力処理のフローチャートである。
【図４】経路探索処理のフローチャートである。
【図５】直線距離Ｌｄの算出方法を説明するための図である。
【図６】出発地Ｐａ、Ｐｂによって経由地に設定される優先ポイントが異なることを説明するための図である。
【図７】今回の目的地Ｇａ、他の目的地Ｇｂに関連付けられた優先ポイントｕ１１〜ｕ１５を示す図である。
【符号の説明】
【００４８】
１ 位置検出器
６ 地図データ入力装置
７ 操作スイッチ群
８ リモコンセンサ
９ リモートコントローラ（リモコン）
１０ 制御装置
１１ 外部メモリ
１２ 表示装置
【技術分野】
【０００１】
本発明は、カーナビゲーションシステムに好適な経路探索装置に関するものである。
【背景技術】
【０００２】
従来、特許文献１に記載の走行位置表示装置では、経路検索処理において入力した目的地や経由地をメモリに登録する際、地点登録キーを押した場合には、当該キーを押した際のその地点を中心とした地図データを画像メモリに登録することで、当該キーを押さなかった場合と区別して登録する。
【０００３】
また、特許文献２に記載の車載用ナビゲーション装置では、ユーザが経由地として望む特定の複数の地点を１グループとして登録しておき、目的地が設定されている状態で、予め登録されている経由地グループが指定された場合には、その指定されたグループに含まれる各経由地を通る誘導経路を探索する。この誘導経路の探索処理では、自車位置と目的地の位置関係を考慮した最適な誘導経路（例えば、指定された経由地グループに含まれる各経由地を自車位置から近い順番に設定して目的地まで探索した誘導経路、あるいは、目的地までのトータルの距離又は所要時間が最短となるように各経由地の順番を設定して探索した誘導経路）を探索する。
【特許文献１】特開平７−１３４７９８号公報
【特許文献２】特開２００６−１７７７９２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ユーザは、経路探索装置が探索した経路よりも有益な経路を知っている場合、経路の途中に経由地を設定することでカスタマイズが可能となるが、次回も同じ経路とする場合、目的地と経由地の設定について、同じ手順を踏んで設定しなければならない。この場合、上記特許文献２に記載の技術を発展させ、経由地を目的地と関連付けて予め登録しておけば、次回に経路探索を行う場合、登録済みの目的地とそれに関連付けられた経由地を読み出して設定することで、目的地と経由地の設定が容易になる。
【０００５】
しかしながら、次回に経路探索を行う場合、出発地（自車位置）が前回と異なるとき、登録された全ての経由地を再度経由地として設定した場合には遠回りになる経路を探索することがある。
【０００６】
本発明は、上記の問題を鑑みてなされたもので、予め登録された目的地と経由地を読み出して、前回と同じ目的地へ向かう経路を探索する場合、出発地が前回と異なる場合にも最適な経路を探索することができる経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するためになされた請求項１記載の経路探索装置は、
経路の目的地と、その目的地へ向かう経路の経由地とされた地点とを関連付けて登録する地点登録手段と、
地点登録手段が登録した目的地、及びその目的地に関連付けられた地点を読み出す地点読出し手段と、
地点読出し手段の読み出した目的地への経路を探索する経路探索手段を備えるものであって、
経路探索手段は、
出発地から地点読み出し手段が読み出した目的地へ向かう経路を探索する第１経路探索手段と、
目的地に関連付けて登録された地点のうち、第１経路探索手段の探索した経路の付近に存在する地点を経由地としたうえで、出発地から目的地へ向かう経路を探索する第２経路探索手段と、を備えることを特徴とする。
【０００８】
これにより、第１経路探索手段の探索した経路の付近に存在せず、その経路から離れた地点については、経由地として含めないようにすることができるので、出発地が前回と異なる場合にも、遠回りになることのない最適な経路を探索することが可能となる。
【０００９】
請求項２に記載の経路探索装置では、経路探索手段は、
目的地に関連付けて登録された地点と、第１経路探索手段の探索した経路との距離が所定距離以内であるかどうかを判定する距離判定手段を備え、
第２経路探索手段は、距離判定手段が所定距離以内であると判定した地点を経由地としたうえで探索することを特徴とする。
【００１０】
これにより、第１経路探索手段の探索した経路との距離が所定距離以内である地点を経由地とすることができる。
【００１１】
請求項３に記載の経路探索装置によれば、距離判定手段は、地点登録手段に目的地とは異なる他の目的地に関連付けられた地点が登録されている場合、その登録されている地点と第１経路探索手段の探索した経路との距離が所定距離以内であるかどうかについても判定することを特徴する。
【００１２】
これにより、他の目的地に関連付けられた地点と第１経路探索手段の探索した経路との距離が所定距離以内である場合には、その地点を経路の経由地に含めることが可能となる。
【００１３】
請求項４に記載の経路探索装置は、
地点読出し手段が地点登録手段から目的地、及びその目的地に関連付けられた地点を読み出した際に、当該目的地に対する新たな地点を追加する地点追加手段を備え、
地点登録手段は、地点追加手段の追加した新たな地点を目的地に関連付けて登録することを特徴とする。
【００１４】
これにより、新たな地点を追加した場合、その新たな地点を目的地に関連付けて登録することができる。
【００１５】
請求項５に記載の経路探索装置によれば、第１経路探索手段、及び第２経路探索手段は、目的地へ向かう複数の経路を探索するものであり、
第１経路探索手段、及び第２経路探索手段の少なくとも一方が探索した複数の経路について、１つの経路毎に経路の行程を順次画面に表示する表示制御手段を備えることを特徴とする。これにより、経路毎の行程をユーザに提供することができるようになる。
【００１６】
なお、請求項６に記載のように、表示制御手段は、第１経路探索手段の探索した各々の経路と、その各々の経路の経由地とした地点との距離の長短に基づいて、画面に表示する際の順序を決定する表示順序決定手段を備えることが好ましい。これにより、各々の経路と、各々の経路の経由地とした地点との距離が短い順に、順次画面に表示することが可能となるからである。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施形態について図面を用いて説明する。本実施形態では、本発明の経路探索装置の機能をカーナビゲーションシステムの機能として採用した場合について説明する。図１におけるカーナビゲーションシステムは、位置検出器１、地図データ入力装置６、操作スイッチ群７、リモコンセンサ８、リモートコントローラ（リモコン）９、外部メモリ１１、表示装置１２、及び、これら各装置が接続された制御装置１０から構成されている。
【００１８】
地図データ入力装置６は、ＨＤＤ（Hard Disk Drive）、ＤＶＤ−ＲＯＭ（Digital Versatile Disk−Read Only Memory）、ＣＤ（Compact Disc）−ＲＯＭ等のドライブ装置であり、ハードディスクやＤＶＤ−ＲＯＭメディア、ＣＤ−ＲＯＭメディア等の地図データソース（図示せず）から地図データを読取可能に構成されている。
【００１９】
地図データソースには、道路地図データや位置検出精度向上のためのマップマッチング用データを含む各種データが記憶されている。ここで、道路地図データを構成するリンクデータ、ノードデータ、索引データ、描画データについて説明する。先ず、リンクとは、地図上の各道路を交差・分岐・合流する点等の複数のノードにて分割し、それぞれのノード間をリンクとして規定されるものであり、リンクを接続することにより道路が構成される。
【００２０】
リンクデータは、リンクを特定する固有番号（リンクＩＤ）、リンクの長さを示すリンク長、リンクの始端及び終端ノード座標（緯経度）、道路名称、道路種別、道路幅員、車線数等の各データから構成されている。ノードデータは、地図上の各道路が交差・分岐・合流するノード毎に固有の番号を付したノードＩＤ、ノード座標（緯経度）、ノードに接続する全てのリンクのリンクＩＤが記述される接続リンクＩＤ等の各データから構成されている。
【００２１】
索引データは、施設等の検索に用いられるデータであり、施設、道路、道路の分岐・合流・交差する地点等の名称、施設種別、住所、電話番号、位置座標（緯経度）等の情報で構成されている。描画データは、地図表示に用いられるデータであり、海（湖、池等も含む）や山等の地形、施設、道路、道路の分岐地点、道路の合流地点、道路の交差点等の表示文字、表示位置（緯経度）、ポリゴン、目印（ランドマーク等）の情報で構成されている。
【００２２】
操作スイッチ群７は、例えば、表示装置１２と一体になったタッチスイッチもしくはメカニカルなスイッチ等が用いられ、表示装置１２の画面に表示される道路地図のスクロール操作や文字入力等の各種入力に使用される。
【００２３】
外部メモリ１１は、経路の目的地、及びその経路の経由地とされた地点（以下、優先ポイント）の履歴の登録（書き込み）や、登録した情報を読み出すためのメモリであり、経路の目的地と、その目的地へ向かう経路上の優先ポイントとを関連付けて（セットで）登録する。外部メモリ１１は、グループ番号、地点の種別（目的地／優先ポイント）、名称、座標（緯経度）を登録情報とし、地点種別が目的地である１つの地点に対し、地点種別が優先ポイントである１つ以上の地点を関連付けて（セットで）、１つのグループとして登録する。
【００２４】
表示装置１２は、例えば液晶ディスプレイによって構成され、表示装置１２の画面には位置検出器１から入力された自車位置に対応する自車位置マークと、地図データ入力装置６より入力された道路地図データによって生成される自車周辺の道路地図を表示することができる。
【００２５】
本カーナビゲーションシステムは、操作スイッチ群７やリモコンセンサ８を介してリモコン９等から目的地が設定されると、自車位置（若しくは任意の地点）を出発地とする目的地へ向かう最適な経路を自動的に計算し、案内すべき経路を形成し表示する、いわゆる経路設定機能を備えている。このような自動的に最適な経路を計算する手法は、例えば、周知のダイクストラ法によるコスト計算、すなわち、リンクのリンク長、車線数、道路幅員等を考慮してリンク毎に付されるコストを用いて、最小のコストで目的地に到達する経路を計算する方法が採用される。
【００２６】
これらの機能は、主に制御装置１０によって各種の演算処理がなされることによって実行される。すなわち、制御装置１０は目的地が設定されると、地図データ入力装置６の道路地図データを用いて複数の経路（本実施形態では５つの経路）を計算し、その５つの経路を表示装置１２へ表示させる。そして、５つの経路の中からユーザが所望する１つの経路が選択されると、その選択された経路の分岐地点や右左折すべき交差点において道路地図の拡大や音声案内を行う。
【００２７】
次に、本カーナビゲーションシステムにおける経路設定機能の動作について、図２に示すフローチャートを参照しながら説明する。先ず、図２に示すステップＳ１では、図３に示す目的地・優先ポイント入力処理を実行する。図３のステップＳ１１では、目的地を外部メモリ１１から選択するかどうかを判定する。このステップＳ１１で肯定判断した場合にはステップＳ１３へ処理を進め、否定判断した場合にはステップＳ１２へ処理を進める。
【００２８】
ステップＳ１２では、操作スイッチ群７やリモコン９等からの目的地とすべき地点の入力を行い、この入力された地点を目的地に設定する。ステップＳ１３では、外部メモリ１１に登録されている目的地の読み出しを行うとともに、その読み出した全ての目的地の名称を示すリストを表示装置１２の画面に表示して、ユーザが希望する目的地を選択させる。ここで、選択された目的地に関連付けられた優先ポイントが有る（登録されている）場合には、その目的地と優先ポイントの位置を示す道路地図を表示するようにしてもよい。ユーザが希望する目的地が選択されると、この選択された目的地を新たな目的地として設定する。
【００２９】
ステップＳ１４では、ステップＳ１２又はステップＳ１３にて設定した目的地へ向かう際の優先ポイントを設定するかどうかを判定する。このステップＳ１４にて優先ポイントを設定する旨の入力操作をユーザが行った場合（肯定判断の場合）にはステップＳ１５へ処理を進め、優先ポイントを設定しない旨の入力操作をユーザが行った場合（否定判断の場合）には本処理を終了する。
【００３０】
ステップＳ１５では、設定した目的地に関連付けて登録された優先ポイントが有るかどうかを判断する。このステップＳ１５にて肯定判断した場合にはステップＳ１６へ処理を進め、否定判断した場合にはステップＳ１７へ処理を進める。ステップＳ１６では、設定した目的地に関連付けて登録された全ての優先ポイントを読み出して、設定した目的地に対応する優先ポイントとして設定する。ステップＳ１７では、目的地付近の道路地図を表示するとともに、優先ポイントの入力をユーザに促して、操作スイッチ群７やリモコン９等からの優先ポイントの入力を待つ。
【００３１】
ステップＳ１８では、優先ポイントを追加するかどうかを判断する。このステップＳ１８にて優先ポイントを追加する旨の入力操作をユーザが行った場合（肯定判断の場合）にはステップＳ１７へ処理を進め、上述した処理を繰り返す。一方、ステップＳ１８にて優先ポイントを追加しない旨の入力操作をユーザが行った場合（否定判断の場合）には本処理を終了する。
【００３２】
図２のステップＳ２では、図３の目的地・優先ポイント入力処理にて設定された目的地と、優先ポイントとを関連付けて外部メモリ１１に登録する。これにより、図３の目的地・優先ポイント入力処理にて目的地とその目的地に関連付けられた優先ポイントを読み出した際に、目的地に対する新たな優先ポイントを追加した場合、その新たな優先ポイントを目的地に関連付けて外部メモリ１１に登録することができる。
【００３３】
図２のステップＳ３では、図４に示す経路探索処理を実行する。図４のステップＳ３１では、現在の自車位置（若しくは、任意の地点）を出発地とし、図３の目的地・優先ポイント入力処理にて設定した目的地へ向かう５つの経路を計算する（第１経路探索手段）。ステップＳ３２では、ステップＳ２にて目的地に関連付けて登録された優先ポイントと、ステップＳ３１にて計算した各々の経路との（直線）距離が所定距離（例えば、１００ｍ）以内であるかどうかを判定する。
【００３４】
このステップＳ３２では、図５に示す三角法によって直線距離を算出する。なお、以下の算出方法はその一例であるので、その他の手法を採用してもよい。先ず、優先ポイントｕ２と経路との直線距離Ｌｄを算出する際、座標値が既知である出発地Ｐｐ、ノードｎｄ１、ノードｎｄ２、目的地Ｇｐのうち、狭角θ１、θ２が共に９０度以下となる地点を特定する。この狭角θ１、θ２は、優先ポイントｕ２の座標値と、出発地Ｐｐ、ノードｎｄ１、ノードｎｄ２、目的地Ｇｐの座標値から算出できる。図５の場合、優先ポイントｕ２に対してはノードｎｄ１、ノードｎｄ２が特定される。
【００３５】
すると、直線距離Ｌｄは数式１で算出されることから、この直線距離Ｌｄが所定距離以内であるかどうか判定できる。なお、ノードｎｄ１と優先ポイントｕ２との距離Ｌ１、ノードｎｄ２と優先ポイントｕ２との距離Ｌ２は、各々の地点の座標値から算出できる。
【００３６】
（数１）
Ｌｄ＝Ｌ１×ｓｉｎθ１＝Ｌ２×ｓｉｎθ２
なお、図４の優先ポイントｕ１は、狭角θ１、θ２が共に９０度以下となる地点が特定されないため、座標値が既知である出発地Ｐｐ、ノードｎｄ１、ノードｎｄ２、目的地Ｇｐとの距離を各々算出し、その最小距離が所定距離以下であるかどうか判定すればよい。
【００３７】
このステップＳ３２にて肯定判断した場合にはステップＳ３３へ処理を進め、否定判断した場合には本処理を終了する。ステップＳ３３では、該当する優先ポイントを出発地から目的地へ向かう経路の経由地として設定し、ステップＳ３４では、ステップＳ３３で設定した経由地を通過する５つの経路を再度計算する（第２経路探索手段）。
【００３８】
このように、図４の経路探索処理では、ステップＳ３１にて計算した各経路について、その経路の付近に存在する優先ポイントを経由地として設定して、ステップＳ３４にて再度経路計算を行う。これにより、ステップＳ３１にて計算した各経路の付近に存在せず、その各経路から離れた優先ポイントについては、経由地として含めないようにすることができるので、出発地が前回と異なる場合にも、遠回りになることのない最適な５つの経路を探索することが可能となる。
【００３９】
すなわち、図６に示すように、目的地Ｇａに対して優先ポイントｕ１〜ｕ７が関連付けて外部メモリ１１に登録されている場合には、出発地Ｐａから目的地Ｇａへ向かう経路の経由地として優先ポイントｕ３〜ｕ５が設定されるようになるため、優先ポイントｕ１、ｕ２、ｕ４〜ｕ７は経由地として含まないようにすることができる。また、前回の出発地Ｐａとは場所が大きく異なる出発地Ｐｂから目的地Ｇａへ向かう経路の経由地には優先ポイントｕ１、ｕ２が設定され、優先ポイントｕ３〜ｕ７は経由地として含めないようにすることができるので、出発地が異なっても、遠回りになることのない最適な経路が探索できる。
【００４０】
図２のステップＳ４では、図４の経路探索処理にて探索した５つの経路について、１つの経路毎に経路の行程を順次、表示装置１２の画面に表示する。これにより、経路毎の行程をユーザに提供することができるようになるため、ユーザは所望の経路を選択することができる。なお、表示装置１２の画面に表示する経路の順序については、ステップＳ３１にて計算した各々の経路と、ステップＳ３３にて経由地とした優先ポイントとの距離の長短に基づいて決定するとよい。これにより、各々の経路と、各々の経路の経由地とした優先ポイントとの距離が短い順に、順次画面に表示することが可能となる。
【００４１】
ステップＳ５にて、ユーザの所望する１つの経路が選択されると、ステップＳ６では、優先ポイントを追加するかどうかを判断する。このステップＳ６にて、優先ポイントを追加する旨の入力操作をユーザが行った場合（肯定判断の場合）にはステップＳ７へ処理を進め、一方、優先ポイントを追加しない旨の入力操作をユーザが行った場合（否定判断の場合）には本処理を終了する。
【００４２】
ステップＳ７では、出発地から目的地までの経路の行程を示す道路地図を表示装置１２の画面に表示するとともに、優先ポイントの入力をユーザに促して、操作スイッチ群７やリモコン９等からの優先ポイントの入力を待つ。ステップＳ８では、入力された優先ポイントを経路の目的地に関連付けて外部メモリ１１に追加登録する。
【００４３】
ステップＳ９では、ステップＳ７にて入力した優先ポイントを経由地として含む経路を計算し、ステップＳ１０では、ステップＳ９にて計算した経路の行程を表示装置１２の画面に表示して、経路設定機能が終了する。この経路設定機能が終了すると、ユーザの指示、若しくは、自車位置が経路上に移動することで経路案内を開始する。
【００４４】
このように、本実施形態のカーナビゲーションシステムでは、外部メモリ１１に目的地とその目的地に関連付けた経由地を登録し、その登録した目的地を外部メモリ１１から読み出して経路探索する場合、経路の出発地（自車位置）によって、目的地に関連付けられた優先ポイントのうち、経由地とすべき優先ポイントを変更する。これにより、経路から離れた優先ポイントについては、経由地として含めないようにすることができるので、出発地が前回と異なる場合にも、遠回りになることのない最適な経路を探索することが可能となる。
【００４５】
以上、本発明の好ましい実施形態について説明したが、本発明は上述した実施形態に何ら制限されることなく、本発明の主旨を逸脱しない範囲において、種々変形して実施することができる。
【００４６】
例えば、本実施形態の経路探索処理（図４）では、経由地に設定する優先ポイントの対象を、経路の目的地に関連付けられた優先ポイントに限定しているが、図７に示すように、他の目的地Ｇｂに関連付けられた優先ポイントｕ１１〜ｕ１５が外部メモリ１１に登録されている場合には、その優先ポイントｕ１１〜ｕ１５についても、図４のステップＳ３２の処理を実行してもよい。これにより、他の目的地Ｇｂに関連付けられた優先ポイントｕ１１〜ｕ１５と、ステップＳ３１にて計算した経路との距離が所定距離以内である場合には、その優先ポイントを経路の経由地に含めることが可能となる。
【図面の簡単な説明】
【００４７】
【図１】カーナビゲーションシステムの全体構成図である。
【図２】カーナビゲーションシステムによる経路設定機能の動作を説明するためのフローチャートである。
【図３】目的地・優先ポイント入力処理のフローチャートである。
【図４】経路探索処理のフローチャートである。
【図５】直線距離Ｌｄの算出方法を説明するための図である。
【図６】出発地Ｐａ、Ｐｂによって経由地に設定される優先ポイントが異なることを説明するための図である。
【図７】今回の目的地Ｇａ、他の目的地Ｇｂに関連付けられた優先ポイントｕ１１〜ｕ１５を示す図である。
【符号の説明】
【００４８】
１ 位置検出器
６ 地図データ入力装置
７ 操作スイッチ群
８ リモコンセンサ
９ リモートコントローラ（リモコン）
１０ 制御装置
１１ 外部メモリ
１２ 表示装置
【特許請求の範囲】
【請求項１】
経路の目的地と、その目的地へ向かう経路の経由地とされた地点とを関連付けて登録する地点登録手段と、
前記地点登録手段が登録した目的地、及びその目的地に関連付けられた地点を読み出す地点読出し手段と、
前記地点読出し手段の読み出した目的地への経路を探索する経路探索手段を備える経路探索装置であって、
前記経路探索手段は、
出発地から前記地点読出し手段が読み出した目的地へ向かう経路を探索する第１経路探索手段と、
前記目的地に関連付けて登録された地点のうち、前記第１経路探索手段の探索した経路の付近に存在する地点を経由地としたうえで、前記出発地から前記目的地へ向かう経路を探索する第２経路探索手段と、を備えることを特徴とする経路探索装置。
【請求項２】
前記経路探索手段は、
前記目的地に関連付けて登録された地点と、前記第１経路探索手段の探索した経路との距離が所定距離以内であるかどうかを判定する距離判定手段を備え、
前記第２経路探索手段は、前記距離判定手段が所定距離以内であると判定した地点を経由地としたうえで探索することを特徴とする請求項１記載の経路探索装置。
【請求項３】
前記距離判定手段は、前記地点登録手段に前記目的地とは異なる他の目的地に関連付けられた地点が登録されている場合、その登録されている地点と前記第１経路探索手段の探索した経路との距離が所定距離以内であるかどうかについても判定することを特徴する請求項２記載の経路探索装置。
【請求項４】
前記地点読出し手段が前記地点登録手段から目的地、及びその目的地に関連付けられた地点を読み出した際に、当該目的地に対する新たな地点を追加する地点追加手段を備え、
前記地点登録手段は、前記地点追加手段の追加した新たな地点を前記目的地に関連付けて登録することを特徴とする請求項１〜３の何れか１項に記載の経路探索装置。
【請求項５】
前記第１経路探索手段、及び前記第２経路探索手段は、前記目的地へ向かう複数の経路を探索するものであり、
前記第１経路探索手段、及び前記第２経路探索手段の少なくとも一方が探索した複数の経路について、１つの経路毎に経路の行程を順次画面に表示する表示制御手段を備えることを特徴とする請求項１〜４の何れか１項に記載の経路探索装置。
【請求項６】
前記表示制御手段は、前記第１経路探索手段の探索した各々の経路と、その各々の経路の経由地とした地点との距離の長短に基づいて、前記画面に表示する際の順序を決定する表示順序決定手段を備えることを特徴とする請求項５記載の経路探索装置。
【請求項１】
経路の目的地と、その目的地へ向かう経路の経由地とされた地点とを関連付けて登録する地点登録手段と、
前記地点登録手段が登録した目的地、及びその目的地に関連付けられた地点を読み出す地点読出し手段と、
前記地点読出し手段の読み出した目的地への経路を探索する経路探索手段を備える経路探索装置であって、
前記経路探索手段は、
出発地から前記地点読出し手段が読み出した目的地へ向かう経路を探索する第１経路探索手段と、
前記目的地に関連付けて登録された地点のうち、前記第１経路探索手段の探索した経路の付近に存在する地点を経由地としたうえで、前記出発地から前記目的地へ向かう経路を探索する第２経路探索手段と、を備えることを特徴とする経路探索装置。
【請求項２】
前記経路探索手段は、
前記目的地に関連付けて登録された地点と、前記第１経路探索手段の探索した経路との距離が所定距離以内であるかどうかを判定する距離判定手段を備え、
前記第２経路探索手段は、前記距離判定手段が所定距離以内であると判定した地点を経由地としたうえで探索することを特徴とする請求項１記載の経路探索装置。
【請求項３】
前記距離判定手段は、前記地点登録手段に前記目的地とは異なる他の目的地に関連付けられた地点が登録されている場合、その登録されている地点と前記第１経路探索手段の探索した経路との距離が所定距離以内であるかどうかについても判定することを特徴する請求項２記載の経路探索装置。
【請求項４】
前記地点読出し手段が前記地点登録手段から目的地、及びその目的地に関連付けられた地点を読み出した際に、当該目的地に対する新たな地点を追加する地点追加手段を備え、
前記地点登録手段は、前記地点追加手段の追加した新たな地点を前記目的地に関連付けて登録することを特徴とする請求項１〜３の何れか１項に記載の経路探索装置。
【請求項５】
前記第１経路探索手段、及び前記第２経路探索手段は、前記目的地へ向かう複数の経路を探索するものであり、
前記第１経路探索手段、及び前記第２経路探索手段の少なくとも一方が探索した複数の経路について、１つの経路毎に経路の行程を順次画面に表示する表示制御手段を備えることを特徴とする請求項１〜４の何れか１項に記載の経路探索装置。
【請求項６】
前記表示制御手段は、前記第１経路探索手段の探索した各々の経路と、その各々の経路の経由地とした地点との距離の長短に基づいて、前記画面に表示する際の順序を決定する表示順序決定手段を備えることを特徴とする請求項５記載の経路探索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００８−１３９１７４（Ｐ２００８−１３９１７４Ａ）
【公開日】平成２０年６月１９日（２００８．６．１９）
【国際特許分類】
【出願番号】特願２００６−３２６１５１（Ｐ２００６−３２６１５１）
【出願日】平成１８年１２月１日（２００６．１２．１）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
【公開日】平成２０年６月１９日（２００８．６．１９）
【国際特許分類】
【出願日】平成１８年１２月１日（２００６．１２．１）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
[ Back to top ]