ナビゲーション装置、ナビゲーション方法及びプログラム
【課題】巡回経路のコストに対する影響が大きい巡回地点を変更して経路を探索することができるナビゲーション装置、ナビゲーション方法及びプログラムを提供する。
【解決手段】ＣＰＵ４１は、出発地から送迎する各メンバーの自宅位置を巡回して目的地に至る通常巡回経路のコストが、出発地から各巡回地点を経由しないで直接、目的地に至る基準経路から算出したコスト上限値を超える場合には、送迎する各メンバーの自宅位置のそれぞれについて、変更巡回経路探索処理のサブ処理を実行して、通常巡回経路のコストよりも低いコストの経路を探索する。
【解決手段】ＣＰＵ４１は、出発地から送迎する各メンバーの自宅位置を巡回して目的地に至る通常巡回経路のコストが、出発地から各巡回地点を経由しないで直接、目的地に至る基準経路から算出したコスト上限値を超える場合には、送迎する各メンバーの自宅位置のそれぞれについて、変更巡回経路探索処理のサブ処理を実行して、通常巡回経路のコストよりも低いコストの経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地までの経路を探索するナビゲーション装置、ナビゲーション方法及びプログラムに関するものである。
【背景技術】
【０００２】
従来より、出発地から複数の巡回地点を巡回して目的地までの経路を探索する技術に関して種々提案されている。
例えば、出発地、目的地、及び各巡回地点を選択することにより、各巡回地点間の最小コスト経路を求める地点間経路計算処理を実行後、各巡回地点をどのような順序で通過するのが最適かを決定する巡回順序決定処理を実行する。そして、得られた巡回順序に従って地点間経路計算処理で求められた経路データをつなぎ合わせて、出発地から目的地までの一本の巡回経路を構成する巡回経路選出方法がある（例えば、特許文献１参照。）。
【特許文献１】特開２００１−９１２８４号公報（段落（００５３）〜（０１５５）、図１〜図３６）
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、前記した特許文献１に記載された巡回経路選出方法では、巡回地点としてグループメンバー全員の自宅を設定した場合に、出発地から遠いメンバーの自宅があったとしても、そのメンバーの自宅を通る巡回経路を選出する。このとき、当該メンバーの自宅を通ることによって巡回経路のコストが大きくなるという問題がある。
尚、コストとは、経路の出発地から目的地までの走行距離、又は、旅行時間をいう。
【０００４】
そこで、本発明は、上述した問題点を解決するためになされたものであり、巡回経路のコストに対する影響が大きい巡回地点を変更して経路を探索することができるナビゲーション装置、ナビゲーション方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
前記目的を達成するため請求項１に係るナビゲーション装置は、地図情報を記憶する地図情報記憶手段（２５）と、出発地と目的地と複数の巡回地点とを入力する地点入力手段（１４）と、前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を前記地図情報に基づいて探索する巡回経路探索手段（１３）と、前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を前記地図情報に基づいて探索する基準経路探索手段（１３）と、前記基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定手段（１３）と、前記巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を前記地図情報に基づいて検索する変更巡回地点検索手段（１３）と、前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を前記地図情報に基づいて探索する変更巡回経路探索手段（１３）と、を備えたことを特徴とする。
尚、コストとは、経路の出発地から目的地までの走行距離、又は、旅行時間をいう。
【０００６】
また、請求項２に係るナビゲーション装置は、請求項１に記載のナビゲーション装置（１）において、前記変更巡回経路のコストが前記巡回経路のコストよりも減少するか否かを判定するコスト判定手段（１３）を備え、前記変更巡回経路のコストが前記巡回経路のコストよりも減少しない場合には、当該変更巡回経路を前記出発地から前記目的地に至る案内経路として選択しないことを特徴とする。
【０００７】
また、請求項３に係るナビゲーション装置は、請求項１又は請求項２に記載のナビゲーション装置（１）において、前記変更巡回経路が複数個探索された場合には、当該複数個の変更巡回経路の中で最もコストの低い経路を前記出発地から前記目的地に至る案内経路として選択することを特徴とする。
【０００８】
また、請求項４に係るナビゲーション方法は、出発地と目的地と複数の巡回地点とを入力する地点入力工程と、前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を地図情報に基づいて探索する巡回経路探索工程と、前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を地図情報に基づいて探索する基準経路探索工程と、前記基準経路探索工程で探索した基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定工程と、前記巡回経路探索工程で探索した巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を地図情報に基づいて検索する変更巡回地点検索工程と、前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を地図情報に基づいて探索する変更巡回経路探索工程と、を備えたことを特徴とする。
【０００９】
更に、請求項５に係るプログラムは、コンピュータに、出発地と目的地と複数の巡回地点とを入力する地点入力工程と、前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を地図情報に基づいて探索する巡回経路探索工程と、前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を地図情報に基づいて探索する基準経路探索工程と、前記基準経路探索工程で探索した基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定工程と、前記巡回経路探索工程で探索した巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を地図情報に基づいて検索する変更巡回地点検索工程と、前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を地図情報に基づいて探索する変更巡回経路探索工程と、を実行させるためのプログラムである。
【発明の効果】
【００１０】
前記構成を有する請求項１に係るナビゲーション装置では、巡回経路のコストがコスト上限値を超えた場合には、巡回地点毎に、当該巡回地点を変更した変更巡回地点を検索し、出発地から変更巡回地点と、当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して目的地に至る変更巡回経路を探索することが可能となる。このため、巡回経路のコストに対する影響の大きい巡回地点を変更して変更巡回経路を探索し、適切な巡回経路を案内することが可能となる。
【００１１】
例えば、巡回地点として送迎のためのグループメンバー全員の自宅を設定した際に、出発地から遠いメンバーがいたとしても、巡回経路のコストが、コスト上限値を超えた場合には、当該メンバーの自宅位置を変更した変更巡回地点を検索することが可能となる。そして、出発地から変更巡回地点と他のメンバーの各自宅とを巡回して目的地に至る変更巡回経路を探索して、適切な巡回経路を案内することが可能となる。
【００１２】
また、請求項２に係るナビゲーション装置では、変更巡回経路のコストが、巡回経路のコストよりも減少しない場合には、当該変更巡回経路を出発地から目的地に至る案内経路として選択しないため、巡回地点の変更によってコストが増加する経路を選択せず、巡回経路のコスト以下の案内経路を確実に選択することが可能となる。
【００１３】
また、請求項３に係るナビゲーション装置では、巡回経路と複数個の変更巡回経路との中で最もコストの低い経路を出発地から目的地に至る案内経路として選択するため、ユーザに最もコストの低い案内経路による経路案内を行うことが可能となる。
【００１４】
また、請求項４に係るナビゲーション方法では、巡回経路のコストがコスト上限値を超えた場合には、巡回地点毎に、当該巡回地点を変更した変更巡回地点を検索し、出発地から変更巡回地点と、当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して目的地に至る変更巡回経路を探索することが可能となる。このため、巡回経路のコストに対する影響の大きい巡回地点を変更して変更巡回経路を探索し、適切な巡回経路を案内することが可能となる。
【００１５】
更に、請求項５に係るプログラムでは、コンピュータは当該プログラムを読み込むことによって、巡回経路のコストがコスト上限値を超えた場合には、巡回地点毎に、当該巡回地点を変更した変更巡回地点を検索し、出発地から変更巡回地点と、当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して目的地に至る変更巡回経路を探索することが可能となる。このため、コンピュータは、巡回経路のコストに対する影響の大きい巡回地点を変更して変更巡回経路を探索し、適切な巡回経路を案内することが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明に係るナビゲーション装置、ナビゲーション方法及びプログラムを車載用ナビゲーション装置について具体化した一実施例に基づき図面を参照しつつ詳細に説明する。
【実施例】
【００１７】
［車載用ナビゲーション装置の概略構成］
先ず、本実施例に係る車載用ナビゲーション装置（以下、「ナビゲーション装置」という。）の概略構成について図１に基づいて説明する。図１は本実施例に係るナビゲーション装置１を示したブロック図である。
図１に示すように、本実施例に係るナビゲーション装置１は、自車の現在位置を検出する現在地検出処理部１１と、各種のデータが記録されたデータ記録部１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーション制御部１３と、操作者からの操作を受け付ける操作部１４と、操作者に対して地図等の情報を表示する液晶ディスプレイ１５と、経路案内等に関する音声ガイダンスを出力するスピーカ１６と、不図示の道路交通情報センタや地図情報配信センタ等との間で携帯電話網等を介して通信を行う通信装置１７とから構成されている。また、ナビゲーション制御部１３には自車の走行速度を検出する車速センサ２１が接続されている。
【００１８】
以下に、ナビゲーション装置１を構成する各構成要素について説明すると、現在地検出処理部１１は、ＧＰＳ３１、方位センサ３２、距離センサ３３等からなり、現在の自車の位置、方位、走行距離等を検出することが可能となっている。
【００１９】
また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記憶された地図情報データベース（地図情報ＤＢ）２５、時刻表データベース（時刻表ＤＢ）２７及び所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。
【００２０】
また、地図情報ＤＢ２５には、ナビゲーション装置１の走行案内や経路探索に使用されるナビ地図情報２６が格納されている。ここで、ナビ地図情報２６は、経路案内及び地図表示に必要な各種情報から構成されており、例えば、各新設道路を特定するための新設道路情報、地図を表示するための地図表示データ、各交差点に関する交差点データ、ノード点に関するノードデータ、道路（リンク）に関するリンクデータ、経路を探索するための探索データ、施設の一種である店舗等のＰＯＩ（Pointof Interest）に関する店舗データ、地点を検索するための検索データ、公共交通機関の路線に関する路線情報等から構成されている。また、店舗データとしては、各地域のホテル、病院、ガソリンスタンド、駐車場、駅、空港、バス停、フェリー乗り場等のＰＯＩに関するデータがＰＯＩを特定するＩＤとともに記憶されている。
また、地図情報ＤＢ２５の内容は、不図示の地図情報配信センタから通信装置１７を介して配信された更新情報をダウンロードすることによって更新される。
【００２１】
ここで、特に地図表示データとしては、約１０ｋｍ×１０ｋｍで区画された２次メッシュをベースに４分割（長さ１／２）、１６分割（１／４）、６４分割（１／８）されたユニットで構成されており、各ユニットのデータ量が略同レベルになるように、各地のユニットが設定されている。最も小さい６４分割サイズのユニットは、約１．２５ｋｍ四方の大きさである。また、約１０ｋｍ×１０ｋｍで区画された各２次メッシュ（以下、「メッシュ」という。）には、各メッシュを識別するメッシュＩＤがそれぞれ付されている。
【００２２】
また、探索データとしては、設定された目的地までの経路を周知のダイクストラ法等により探索及び表示する際に使用されるデータについて記録されており、ノードを通過する際の右左折や道路を構成するリンクの距離、旅行時間、道幅、道路種別等によって決定される各ノードの重み付け（以下、「コスト」という。）を算出する為に使用するコストデータ、経路探索により選択された経路を液晶ディスプレイ２５の地図上に表示するための経路表示データ等から構成されている。尚、本実施例では、コストとしてリンクの距離を採用し、探索された経路を評価するコストの一例として出発地から目的地までの走行距離を採用する。
【００２３】
また、時刻表ＤＢ２７には、鉄道、バス、地下鉄等の公共交通機関の各路線における最新の時刻表が格納されている。また、時刻表ＤＢ２７の内容は、不図示の地図情報配信センタから通信装置１７を介して配信された更新情報をダウンロードすることによって更新される。
【００２４】
また、図１に示すように、ナビゲーション装置１を構成するナビゲーション制御部１３は、ナビゲーション装置１の全体の制御を行う演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うに当たってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、後述の複数の地点を巡回地点として、出発地から目的地までの巡回経路を設定する巡回経路設定処理のプログラム（図２参照）等が記憶されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記憶するフラッシュメモリ４４等の内部記憶装置や、時間を計測するタイマ４５等を備えている。
【００２５】
更に、前記ナビゲーション制御部１３には、操作部１４、液晶ディスプレイ１５、スピーカ１６、通信装置１７の各周辺装置（アクチュエータ）が電気的に接続されている。
【００２６】
この操作部１４は、案内開始地点としての出発地、巡回地点としての各メンバーの自宅位置及び案内終了地点としての目的地を入力する際や施設に関する情報の検索を行う場合等に操作され、各種のキーや複数の操作スイッチから構成される。そして、ナビゲーション制御部１３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。更に、液晶ディスプレイ１５の前面部には、タッチパネルが設けられ、画面に表示されたボタンや地図上を押下することによって各種指示コマンドを入力することが可能に構成されている。
【００２７】
また、液晶ディスプレイ１５には、現在走行中の地図情報、操作案内、操作メニュー、キーの案内、現在地から各巡回地点を経由して目的地に至る推奨経路、推奨経路に沿った案内情報、交通情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。
【００２８】
また、スピーカ１６は、ナビゲーション制御部１３からの指示に基づいて、推奨経路に沿った走行を案内する音声ガイダンス等を出力する。ここで、案内される音声ガイダンスとしては、例えば、「２００ｍ先、○○交差点を右方向です。」等がある。
【００２９】
また、通信装置１７は、地図情報配信センタと通信を行う携帯電話網等による通信手段であり、地図情報配信センタとの間で最もバージョンの新しい更新地図情報や各公共交通機関の最新の時刻表等の送受信を行う。また、通信装置１７は地図情報配信センタに加えて、道路交通情報センタ等から送信された渋滞情報やサービスエリアの混雑状況等の各情報から成る交通情報を受信する。
【００３０】
［巡回経路設定処理］
次に、上記のように構成されたナビゲーション装置１のＣＰＵ４１が実行する処理であって、複数の地点を巡回地点として、出発地から目的地までの巡回経路を設定する巡回経路設定処理をグループメンバー全員の自宅を巡回地点として、出発地から目的地までの送迎経路を設定する場合について実行した一例を図２乃至図５に基づいて説明する。
【００３１】
図２は本実施例に係るナビゲーション装置１のＣＰＵ４１が実行する処理であって、グループメンバー全員の自宅を巡回地点として、出発地から目的地までの送迎経路を設定する送迎経路設定処理を示すメインフローチャートである。
尚、図２にフローチャートで示されるプログラムはナビゲーション装置１のナビゲーション制御部１３が備えているＲＯＭ４３に記憶されており、ＣＰＵ４１により出発地、巡回地点としての各メンバーの自宅位置及び目的地を操作部１４を介して入力された場合に実行される。
【００３２】
図２に示すように、先ず、ステップ（以下、Ｓと略記する）１１において、ＣＰＵ４１は、タッチパネル、操作スイッチ等の操作部１４の入力操作等によって、出発地、巡回地点としての送迎する各メンバーの自宅位置及び目的地が入力された場合には、各座標位置（例えば、緯度と経度である。）をナビ地図情報２６から取得してＲＡＭ４２に記憶する。
【００３３】
そして、Ｓ１２において、ＣＰＵ４１は、出発地から各巡回地点を経由して目的地に至る最小コストの巡回経路、つまり、最短走行距離の巡回経路を公知の巡回経路探索方法（例えば、特開平３−１９１４６４号公報参照）により探索して、「通常巡回経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この通常巡回経路の出発地から目的地に至る走行距離を通常巡回経路のコスト（以下、「通常巡回コスト」という。）としてＲＡＭ４２に記憶する。
【００３４】
続いて、Ｓ１３において、ＣＰＵ４１は、各巡回地点を経由しないで、出発地から直接目的地に至る経路をダイクストラ法等により探索して、「基準経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この基準経路の出発地から目的地に至る走行距離を基準経路のコスト（以下、「基準コスト」という。）として記憶する。そして、ＣＰＵ４１は、基準コストから「コスト上限値」を算出して、ＲＡＭ４２に記憶する。
【００３５】
例えば、ＣＰＵ４１は、予めＲＯＭ４３に記憶されるコスト上限係数（例えば、「１．２」等である。）を基準コストに積算した値を「コスト上限値」として、ＲＡＭ４２に記憶する。
尚、ＣＰＵ４１は、予めＲＯＭ４３に記憶される最大加算コスト（例えば、「２０ｋｍ」等である。）を基準コストに加算した値を「コスト上限値」として、ＲＡＭ４２に記憶するようにしてもよい。
【００３６】
ここで、通常巡回経路と基準経路の一例について図４に基づいて説明する。図４は通常巡回経路と基準経路の一例を示す説明図である。
図４に示すように、先ず、ＣＰＵ４１は、操作部１４を介して、当該ナビゲーション装置１が搭載された６人乗りの車両２を所有するメンバー１０１の自宅１０１Ａを出発地として入力される。また、ＣＰＵ４１は、操作部１４を介して、他の５人の各メンバー１０２〜１０６の各自宅１０２Ａ〜１０６Ａを各巡回地点として入力される。そして、ＣＰＵ４１は、操作部１４を介して、目的地１０７を入力された場合には、公知の巡回経路探索方法により自宅１０１Ａから各自宅１０２Ａ〜１０６Ａを巡回して目的地１０７に至る通常巡回経路１１０を探索して、ＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この通常巡回経路１１０の自宅１０１Ａから目的地１０７に至る走行距離を「通常巡回コスト」として記憶する。
【００３７】
また、ＣＰＵ４１は、ダイクストラ法等により各自宅１０２Ａ〜１０６Ａを経由しないで、自宅１０１Ａから直接目的地１０７に至る基準経路１１２を探索して、ＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この基準経路１１２の自宅１０１Ａから目的地に至る走行距離を「基準コスト」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、基準経路１１２の基準コストをＲＡＭ４２から、再度読み出し、予めＲＯＭ４３に記憶されるコスト上限係数（例えば、「１．２」等である。）を当該基準コストに積算した値を「コスト上限値」として、ＲＡＭ４２に記憶する。
尚、ＣＰＵ４１は、予めＲＯＭ４３に記憶される最大加算コスト（例えば、「２０ｋｍ」等である。）を当該基準コストに加算した値を「コスト上限値」として、ＲＡＭ４２に記憶するようにしてもよい。
【００３８】
続いて、図２に示すように、Ｓ１４において、ＣＰＵ４１は、ＲＡＭ４２から通常巡回コストとコスト上限値とを読み出し、当該通常巡回コストがコスト上限値よりも大きいか否か、つまり、当該通常巡回コストがコスト上限値を超えるか否かを判定する判定処理を実行する。
そして、当該通常巡回コストがコスト上限値を超えない場合には（Ｓ１４：ＮＯ）、ＣＰＵ４１は、Ｓ１５の処理に移行する。Ｓ１５において、ＣＰＵ４１は、ＲＡＭ４２から通常巡回経路を読み出して、提示する「巡回経路」としてＲＡＭ４２に再度記憶後、Ｓ２２の処理に移行する。
【００３９】
一方、当該通常巡回コストがコスト上限値を超える場合には（Ｓ１４：ＹＥＳ）、ＣＰＵ４１は、Ｓ１６の処理に移行する。Ｓ１６において、ＣＰＵ４１は、巡回地点としての送迎する各メンバーの自宅位置の座標位置を、出発地から遠い順に抽出して、つまり、出発地の座標位置から各メンバーの自宅位置の座標位置までの道なり距離の長い順に抽出して、順番に「巡回地点」としてＲＡＭ４２に記憶する。
尚、ＣＰＵ４１は、巡回地点としての送迎する各メンバーの自宅位置の座標位置を、出発地の座標位置から各メンバーの自宅位置の座標位置までの直線距離の長い順に抽出して、順番に「巡回地点」としてＲＡＭ４２に記憶するようにしてもよい。
【００４０】
続いて、Ｓ１７において、ＣＰＵ４１は、上記Ｓ１６で抽出して一番目に記憶した巡回地点から各巡回地点を順番に読み出し、つまり、出発地から最も遠い巡回地点から遠い順に各巡回地点を順番に読み出し、当該各巡回地点について、後述の通常巡回経路よりもコストが低い巡回経路を探索する「変更巡回経路探索処理」のサブ処理（図３参照）を実行する。
そして、上記Ｓ１６で抽出した全巡回地点について、後述の「変更巡回経路探索処理」のサブ処理を実行した場合には、ＣＰＵ４１は、Ｓ１８の処理に移行する。
【００４１】
Ｓ１８において、ＣＰＵ４１は、コストがコスト上限値以下の巡回経路である「候補巡回経路」があるか否か、つまり、「候補巡回経路」がＲＡＭ４２に記憶されているか否かを判定する判定処理を実行する。そして、コストがコスト上限値以下の巡回経路である「候補巡回経路」がＲＡＭ４２に記憶されている場合には（Ｓ１８：ＹＥＳ）、ＣＰＵ４１は、Ｓ１９の処理に移行する。
Ｓ１９において、ＣＰＵ４１は、ＲＡＭ４２に記憶されている各「候補巡回経路」のコストを抽出して、各「候補巡回経路」の中から最もコストの低い「候補巡回経路」を選択して、当該「候補巡回経路」を提示する「巡回経路」としてＲＡＭ４２に記憶後、Ｓ２１の処理に移行する。
【００４２】
一方、コストがコスト上限値以下の巡回経路である「候補巡回経路」がＲＡＭ４２に記憶されていない場合には（Ｓ１８：ＮＯ）、ＣＰＵ４１は、Ｓ２０の処理に移行する。Ｓ２０において、ＣＰＵ４１は、コストがコスト上限値を超えるが、通常巡回経路のコストよりも低い巡回経路である「予備巡回経路」があるか否か、つまり、「予備巡回経路」がＲＡＭ４２に記憶されているか否かを判定する判定処理を実行する。
【００４３】
そして、コストがコスト上限値を超えるが、通常巡回経路のコストよりも低い巡回経路である「予備巡回経路」がＲＡＭ４２に記憶されていない場合には（Ｓ２０：ＮＯ）、ＣＰＵ４１は、上記Ｓ１５の処理に移行する。
【００４４】
一方、コストがコスト上限値を超えるが、通常巡回経路のコストよりも低い巡回経路である「予備巡回経路」がＲＡＭ４２に記憶されている場合には（Ｓ２０：ＹＥＳ）、ＣＰＵ４１は、上記Ｓ１９の処理に移行する。Ｓ１９において、ＣＰＵ４１は、ＲＡＭ４２に記憶されている各「予備巡回経路」のコストを抽出して、各「予備巡回経路」の中から最もコストの低い「予備巡回経路」を選択して、当該「予備巡回経路」を提示する「巡回経路」としてＲＡＭ４２に記憶後、Ｓ２１の処理に移行する。
【００４５】
Ｓ２１において、ＣＰＵ４１は、ＲＡＭ４２に記憶されている「巡回経路」を、出発地から各メンバーが途中で乗る巡回地点を経由して目的地に至る巡回経路として確定し、当該巡回経路を液晶ディスプレイ１５に表示してユーザに案内経路として提示後、当該処理を終了する。
【００４６】
［変更巡回経路探索処理］
次に、ＣＰＵ４１が上記Ｓ１７において実行する「変更巡回経路探索処理」のサブ処理について図３に基づいて説明する。図３は図２の「変更巡回経路探索処理」のサブ処理を示すサブフローチャートである。
図３に示すように、Ｓ１１１において、ＣＰＵ４１は、ＲＡＭ４２から読み出した巡回地点を中心とした所定範囲内（例えば、半径２ｋｍ以内の範囲である。）における鉄道やバス、地下鉄等の公共交通機関の駅やバス停等の乗り場をナビ地図情報２６から抽出して、これらを特定する施設ＩＤをＲＡＭ４２に記憶する。一方、ＣＰＵ４１は、ＲＡＭ４２から読み出した巡回地点を中心とした所定範囲内に公共交通機関の駅やバス停等の乗り場が無い場合には、これらを特定する施設ＩＤをＲＡＭ４２に記憶しない。
【００４７】
続いて、Ｓ１１２において、ＣＰＵ４１は、当該巡回地点を中心とした所定範囲内に公共交通機関の駅やバス停等の乗り場があるか否か、つまり、公共交通機関の駅やバス停等を特定する施設ＩＤをＲＡＭ４２に記憶しているか否かを判定する判定処理を実行する。
そして、当該巡回地点を中心とした所定範囲内に公共交通機関の駅やバス停等の乗り場が無い場合、つまり、公共交通機関の駅やバス停等を特定する施設ＩＤをＲＡＭ４２に記憶していない場合には（Ｓ１１２：ＮＯ）、ＣＰＵ４１は、当該サブ処理を終了してメインフローチャートに戻る。
【００４８】
一方、当該巡回地点を中心とした所定範囲内に公共交通機関の駅やバス停等の乗り場がある場合、つまり、公共交通機関の駅やバス停等を特定する施設ＩＤをＲＡＭ４２に記憶している場合には（Ｓ１１２：ＹＥＳ）、ＣＰＵ４１は、Ｓ１１３の処理に移行する。Ｓ１１３において、ＣＰＵ４１は、この公共交通機関の駅やバス停を利用して到達可能な送迎可能地点を時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６から検索する。
【００４９】
具体的には、ＣＰＵ４１は、先ず、タイマ４５から現在の時刻を取得する。そして、ＣＰＵ４１は、ＲＡＭ４２に記憶されている利用可能な公共交通機関について、公共交通機関の駅やバス停等を特定する施設ＩＤを順番に読出し、それぞれについて、現在の時刻から当該巡回地点に到達する到達時刻を推定し、この到達時刻に基づいて当該駅やバス停等から乗ることが可能な路線上にあり、且つ、上記Ｓ１３で探索した「基準経路」に最も近い距離で降りることが可能な駅やバス停等の乗り場を時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６とから検索する。
【００５０】
例えば、ＣＰＵ４１は、当該駅やバス停等から乗ることが可能な路線上にあって、降りることが可能な駅やバス停の乗り場から上記Ｓ１３で探索した「基準経路」に対して垂線を引き、当該垂線の距離が最も短いものを、「基準経路」に最も近い距離で降りることが可能な駅やバス停等の乗り場とする。
【００５１】
そして、ＣＰＵ４１は、この各公共交通機関の時刻表とナビ地図情報２６から検索した駅やバス停等の各乗り場を特定する施設ＩＤと座標位置（例えば、緯度と経度である。）をナビ地図情報２６から読み出し、それぞれを「送迎可能地点」としてＲＡＭ４２に順次記憶する。
【００５２】
続いて、ＣＰＵ４１は、ＲＡＭ４２から各「送迎可能地点」の座標位置を読み出し、それぞれの「基準経路」までの距離を算出して、当該距離の短い順に各「送迎可能地点」の施設ＩＤと座標位置とを再度、ＲＡＭ４２に記憶する。そして、ＣＰＵ４１は、このＲＡＭ４２に記憶した「送迎可能地点」から、一番目に記憶した送迎可能地点から各送迎可能地点を順番に読み出し、つまり、基準経路に最も近い送迎可能地点から近い順に各送迎可能地点を順番に読み出し、各送迎可能地点についてＳ１１４〜Ｓ１１８の処理を実行する。
【００５３】
先ず、Ｓ１１４において、ＣＰＵ４１は、当該送迎可能地点とこの送迎可能地点に対応するメンバーを除いた他の送迎する各メンバーの自宅位置の座標位置をＲＡＭ４２から読み出して、各巡回地点の座標位置として再度ＲＡＭ４２に記憶する。そして、ＣＰＵ４１は、出発地から当該各巡回地点を経由して目的地に至る最小コストの経路、つまり、最短走行距離の経路を公知の巡回経路探索方法（例えば、特開平３−１９１４６４号公報参照）により探索して、「送迎可能巡回経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この送迎可能巡回経路の出発地から目的地に至る走行距離を算出して、送迎可能巡回経路のコスト（以下、「送迎可能巡回コスト」という。）としてＲＡＭ４２に記憶する。
【００５４】
続いて、Ｓ１１５において、ＣＰＵ４１は、ＲＡＭ４２から送迎可能巡回コストと通常巡回コストとを読み出し、当該送迎可能巡回コストが通常巡回コストよりも減少しているか否か、即ち、当該送迎可能巡回コストが通常巡回コスト未満であるか否かを判定する判定処理を実行する。
そして、当該送迎可能巡回コストが通常巡回コストよりも減少していない場合、即ち、当該送迎可能巡回コストが通常巡回コスト以上の場合には（Ｓ１１５：ＮＯ）、ＣＰＵ４１は、次の送迎可能地点をＲＡＭ４２から読み出し、この次の送迎可能地点についてＳ１１４以降の処理を再度実行する。一方、次の送迎可能地点がＲＡＭ４２に記憶されていない場合には、ＣＰＵ４１は、当該サブ処理を終了してメインフローチャートに戻る。
【００５５】
一方、当該送迎可能巡回コストが通常巡回コストよりも減少している場合、即ち、当該送迎可能巡回コストが通常巡回コスト未満の場合には（Ｓ１１５：ＹＥＳ）、ＣＰＵ４１は、Ｓ１１６の処理に移行する。
Ｓ１１６において、ＣＰＵ４１は、ＲＡＭ４２から送迎可能巡回コストとコスト上限値とを読み出し、当該送迎可能巡回コストがコスト上限値以下か否かを判定する判定処理を実行する。
【００５６】
そして、当該送迎可能巡回コストがコスト上限値以下の場合には（Ｓ１１６：ＹＥＳ）、ＣＰＵ４１は、Ｓ１１７の処理に移行する。Ｓ１１７において、ＣＰＵ４１は、当該送迎可能巡回経路をＲＡＭ４２から読み出し、「候補巡回経路」としてＲＡＭ４２に記憶する。その後、ＣＰＵ４１は、次の送迎可能地点をＲＡＭ４２から読み出し、この次の送迎可能地点についてＳ１１４以降の処理を再度実行する。一方、次の送迎可能地点がＲＡＭ４２に記憶されていない場合には、ＣＰＵ４１は、当該サブ処理を終了してメインフローチャートに戻る。
【００５７】
一方、当該送迎可能巡回コストがコスト上限値より大きい場合には（Ｓ１１６：ＮＯ）、ＣＰＵ４１は、Ｓ１１８の処理に移行する。Ｓ１１８において、ＣＰＵ４１は、当該送迎可能巡回経路をＲＡＭ４２から読み出し、「予備巡回経路」としてＲＡＭ４２に記憶する。その後、ＣＰＵ４１は、次の送迎可能地点をＲＡＭ４２から読み出し、この次の送迎可能地点についてＳ１１４以降の処理を再度実行する。一方、次の送迎可能地点がＲＡＭ４２に記憶されていない場合には、ＣＰＵ４１は、当該サブ処理を終了してメインフローチャートに戻る。
【００５８】
ここで、上記Ｓ１１４〜Ｓ１１８において、ＣＰＵ４１が探索した候補巡回経路と予備巡回経路の一例について図５に基づいて説明する。図５は候補巡回経路と予備巡回経路の一例を示す説明図である。
尚、図５においては、上記図４に示す各メンバー１０２〜１０６の中のメンバー１０６の自宅１０６Ａについて、ＣＰＵ４１は、上記Ｓ１１１〜Ｓ１１３の処理を実行した結果、当該自宅１０６Ａを中心とした半径約２ｋｍ以内の範囲１１５において、鉄道１１７のＸ駅１１８とＰバス停１２０とをナビ地図情報２６から抽出する。
【００５９】
また、ＣＰＵ４１は、現在時刻からＸ駅１１８に到達する到達時刻を推定し、この到達時刻に当該Ｘ駅１１８から乗車して降りることが可能な各駅から、基準経路１１２に垂線を引き、当該垂線の距離が最も短いＹ駅１２２を、時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６から検索する。また、ＣＰＵ４１は、現在時刻からＰバス停１２０に到達する到達時刻を推定し、この到達時刻に当該Ｐバス停１２０から乗車して降りることが可能な各バス停から、基準経路１１２に垂線を引き、当該垂線の距離が最も短いＱバス停１２４を、時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６から検索する。そして、ＣＰＵ４１は、この時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６から検索したＹ駅１２２とＱバス停１２４のそれぞれを特定する施設ＩＤと座標位置（例えば、緯度と経度である。）をナビ地図情報２６から読み出し、それぞれを「送迎可能地点」としてＲＡＭ４２に記憶した一例について説明する。
【００６０】
図５に示すように、ＣＰＵ４１は、メンバー１０１の自宅１０１Ａを出発地とし、各メンバー１０２〜１０５の各自宅１０２Ａ〜１０５ＡとＹ駅１２２とを経由して目的地１０７に至る巡回経路を公知の巡回経路探索方法により探索して、「送迎可能巡回経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この「送迎可能巡回経路」のコスト、つまり、「送迎可能巡回コスト」を算出してＲＡＭ４２に記憶する（Ｓ１１４）。
【００６１】
そして、ＣＰＵ４１は、この送迎可能巡回コストと、通常巡回経路１１０のコストである通常巡回コストと、基準経路１１２のコストから計算したコスト上限値とをＲＡＭ４２から読み出し、この送迎可能巡回コストがコスト上限値以下であるため、当該送迎可能巡回経路を候補巡回経路１３１としてＲＡＭ４２に記憶する（Ｓ１１５：ＹＥＳ〜Ｓ１１６：ＹＥＳ〜Ｓ１１７）。
【００６２】
また、ＣＰＵ４１は、メンバー１０１の自宅１０１Ａを出発地とし、各メンバー１０２〜１０５の各自宅１０２Ａ〜１０５ＡとＱバス停１２４とを経由して目的地１０７に至る巡回経路を公知の巡回経路探索方法により探索して、「送迎可能巡回経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この「送迎可能巡回経路」のコスト、つまり、「送迎可能巡回コスト」を算出してＲＡＭ４２に記憶する（Ｓ１１４）。
【００６３】
そして、ＣＰＵ４１は、この送迎可能巡回コストと、通常巡回経路１１０のコストである通常巡回コストと、基準経路１１２のコストから計算したコスト上限値とをＲＡＭ４２から読み出し、送迎可能巡回コストが通常巡回コストよりも低く、コスト上限値よりも大きいため、当該送迎可能巡回経路を予備巡回経路１３２としてＲＡＭ４２に記憶後、当該サブ処理を終了してメインフローチャートに戻る。（Ｓ１１５：ＹＥＳ〜Ｓ１１６：ＮＯ〜Ｓ１１８）。
【００６４】
［上記実施例の効果］
以上詳細に説明した通り、本実施例に係るナビゲーション装置１では、巡回地点として送迎する各メンバーの自宅位置を設定した際に、出発地から遠いメンバーがいたとしても、ＣＰＵ４１は、通常巡回経路のコストが、コスト上限値を超えた場合には、当該メンバーの自宅位置から公共交通機関を使用して移動可能な「送迎可能地点」を検索することが可能となる。
【００６５】
そして、ＣＰＵ４１は、当該送迎可能地点とこの送迎可能地点に対応するメンバーを除いた他の送迎する各メンバーの自宅位置を巡回地点として、出発地から当該各巡回地点を経由して目的地に至る、コスト上限値以下の候補巡回経路又は通常巡回経路よりもコストが減少した予備巡回経路を探索することが可能となる。このため、出発地から遠いメンバーがいたとしても、ＣＰＵ４１は、当該メンバーの送迎地点を公共交通機関を利用可能で基準経路に近い送迎地点に変更し、候補巡回経路又は予備巡回経路を探索して、コストの低い適切な巡回経路を案内することが可能となる。
【００６６】
また、ＣＰＵ４１は、当該送迎可能地点とこの送迎可能地点に対応するメンバーを除いた他の送迎する各メンバーの自宅位置を巡回地点として、出発地から当該各巡回地点を経由して目的地に至る巡回経路のコストが通常巡回経路のコスト以上になる場合には、当該巡回経路を選択しないため、通常巡回経路のコスト以下の案内経路を確実に選択することが可能となる。
【００６７】
また、ＣＰＵ４１は、通常巡回経路がコスト上限値を超える場合には、複数の候補巡回経路と予備巡回経路との中で最もコストの低い経路を出発地から目的地に至る案内経路として選択するため、最もコストの低い案内経路について経路案内を行うことが可能となる。
【００６８】
尚、本発明は前記実施例に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。例えば、以下のようにしてもよい。
【００６９】
（Ａ）上記Ｓ１１３において、巡回地点を中心とした所定範囲内にある公共交通機関の駅やバス停等の乗り場から、乗り換えを行って「基準経路」に近い距離で降りることが可能な駅やバス停等を時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６とから検索して、送迎可能地点としてもよい。
【００７０】
また、巡回地点を中心とした所定範囲内にある公共交通機関を使用する条件を指定するようにしてもよい。例えば、公共交通機関の特急や急行を利用するように指定してもよい。これにより、巡回地点を中心とした所定範囲内にある公共交通機関の駅やバス停等の乗り場から、特急や急行を利用して到達可能な「基準経路」に近い駅やバス停等を時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６とから検索して、送迎可能地点とすることができる。つまり、ユーザの希望に沿った条件で送迎可能地点を検索することが可能となる。
【００７１】
（Ｂ）また、上記Ｓ１１３において、検索した送迎可能地点に対応するメンバーは、当該送迎可能地点や基準経路から所定距離以内（例えば、約５００ｍ以内である。）の施設や地点等（例えば、駐車場や他の路線の駅やバス停等、または、交差点等である。）まで、タクシーや自家用車で行くようにしてもよい。これにより、公共交通機関の運転時刻に拘束されず、自由な時刻に候補巡回経路又は予備巡回経路に従って送迎を行うことが可能となる。
【図面の簡単な説明】
【００７２】
【図１】本実施例に係るナビゲーション装置を示したブロック図である。
【図２】ナビゲーション装置のＣＰＵが実行する処理であって、グループメンバー全員の自宅を巡回地点として、出発地から目的地までの送迎経路を設定する送迎経路設定処理を示すメインフローチャートである。
【図３】図２の「変更巡回経路探索処理」のサブ処理を示すサブフローチャートである。
【図４】通常巡回経路と基準経路の一例を示す説明図である。
【図５】候補巡回経路と予備巡回経路の一例を示す説明図である。
【符号の説明】
【００７３】
１ ナビゲーション装置
１１ 現在地検出処理部
１２ データ記録部
１３ ナビゲーション制御部
１４ 操作部
１５ 液晶ディスプレイ
２５ 地図情報ＤＢ
２６ ナビ地図情報
２７ 時刻表ＤＢ
４１ ＣＰＵ
４２ ＲＡＭ
４３ ＲＯＭ
１０１〜１０６ メンバー
１０１Ａ〜１０６Ａ 自宅
１０７ 目的地
１１０ 通常巡回経路
１１２ 基準経路
１３１ 候補巡回経路
１３２ 予備巡回経路
【技術分野】
【０００１】
本発明は、目的地までの経路を探索するナビゲーション装置、ナビゲーション方法及びプログラムに関するものである。
【背景技術】
【０００２】
従来より、出発地から複数の巡回地点を巡回して目的地までの経路を探索する技術に関して種々提案されている。
例えば、出発地、目的地、及び各巡回地点を選択することにより、各巡回地点間の最小コスト経路を求める地点間経路計算処理を実行後、各巡回地点をどのような順序で通過するのが最適かを決定する巡回順序決定処理を実行する。そして、得られた巡回順序に従って地点間経路計算処理で求められた経路データをつなぎ合わせて、出発地から目的地までの一本の巡回経路を構成する巡回経路選出方法がある（例えば、特許文献１参照。）。
【特許文献１】特開２００１−９１２８４号公報（段落（００５３）〜（０１５５）、図１〜図３６）
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、前記した特許文献１に記載された巡回経路選出方法では、巡回地点としてグループメンバー全員の自宅を設定した場合に、出発地から遠いメンバーの自宅があったとしても、そのメンバーの自宅を通る巡回経路を選出する。このとき、当該メンバーの自宅を通ることによって巡回経路のコストが大きくなるという問題がある。
尚、コストとは、経路の出発地から目的地までの走行距離、又は、旅行時間をいう。
【０００４】
そこで、本発明は、上述した問題点を解決するためになされたものであり、巡回経路のコストに対する影響が大きい巡回地点を変更して経路を探索することができるナビゲーション装置、ナビゲーション方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
前記目的を達成するため請求項１に係るナビゲーション装置は、地図情報を記憶する地図情報記憶手段（２５）と、出発地と目的地と複数の巡回地点とを入力する地点入力手段（１４）と、前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を前記地図情報に基づいて探索する巡回経路探索手段（１３）と、前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を前記地図情報に基づいて探索する基準経路探索手段（１３）と、前記基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定手段（１３）と、前記巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を前記地図情報に基づいて検索する変更巡回地点検索手段（１３）と、前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を前記地図情報に基づいて探索する変更巡回経路探索手段（１３）と、を備えたことを特徴とする。
尚、コストとは、経路の出発地から目的地までの走行距離、又は、旅行時間をいう。
【０００６】
また、請求項２に係るナビゲーション装置は、請求項１に記載のナビゲーション装置（１）において、前記変更巡回経路のコストが前記巡回経路のコストよりも減少するか否かを判定するコスト判定手段（１３）を備え、前記変更巡回経路のコストが前記巡回経路のコストよりも減少しない場合には、当該変更巡回経路を前記出発地から前記目的地に至る案内経路として選択しないことを特徴とする。
【０００７】
また、請求項３に係るナビゲーション装置は、請求項１又は請求項２に記載のナビゲーション装置（１）において、前記変更巡回経路が複数個探索された場合には、当該複数個の変更巡回経路の中で最もコストの低い経路を前記出発地から前記目的地に至る案内経路として選択することを特徴とする。
【０００８】
また、請求項４に係るナビゲーション方法は、出発地と目的地と複数の巡回地点とを入力する地点入力工程と、前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を地図情報に基づいて探索する巡回経路探索工程と、前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を地図情報に基づいて探索する基準経路探索工程と、前記基準経路探索工程で探索した基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定工程と、前記巡回経路探索工程で探索した巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を地図情報に基づいて検索する変更巡回地点検索工程と、前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を地図情報に基づいて探索する変更巡回経路探索工程と、を備えたことを特徴とする。
【０００９】
更に、請求項５に係るプログラムは、コンピュータに、出発地と目的地と複数の巡回地点とを入力する地点入力工程と、前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を地図情報に基づいて探索する巡回経路探索工程と、前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を地図情報に基づいて探索する基準経路探索工程と、前記基準経路探索工程で探索した基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定工程と、前記巡回経路探索工程で探索した巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を地図情報に基づいて検索する変更巡回地点検索工程と、前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を地図情報に基づいて探索する変更巡回経路探索工程と、を実行させるためのプログラムである。
【発明の効果】
【００１０】
前記構成を有する請求項１に係るナビゲーション装置では、巡回経路のコストがコスト上限値を超えた場合には、巡回地点毎に、当該巡回地点を変更した変更巡回地点を検索し、出発地から変更巡回地点と、当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して目的地に至る変更巡回経路を探索することが可能となる。このため、巡回経路のコストに対する影響の大きい巡回地点を変更して変更巡回経路を探索し、適切な巡回経路を案内することが可能となる。
【００１１】
例えば、巡回地点として送迎のためのグループメンバー全員の自宅を設定した際に、出発地から遠いメンバーがいたとしても、巡回経路のコストが、コスト上限値を超えた場合には、当該メンバーの自宅位置を変更した変更巡回地点を検索することが可能となる。そして、出発地から変更巡回地点と他のメンバーの各自宅とを巡回して目的地に至る変更巡回経路を探索して、適切な巡回経路を案内することが可能となる。
【００１２】
また、請求項２に係るナビゲーション装置では、変更巡回経路のコストが、巡回経路のコストよりも減少しない場合には、当該変更巡回経路を出発地から目的地に至る案内経路として選択しないため、巡回地点の変更によってコストが増加する経路を選択せず、巡回経路のコスト以下の案内経路を確実に選択することが可能となる。
【００１３】
また、請求項３に係るナビゲーション装置では、巡回経路と複数個の変更巡回経路との中で最もコストの低い経路を出発地から目的地に至る案内経路として選択するため、ユーザに最もコストの低い案内経路による経路案内を行うことが可能となる。
【００１４】
また、請求項４に係るナビゲーション方法では、巡回経路のコストがコスト上限値を超えた場合には、巡回地点毎に、当該巡回地点を変更した変更巡回地点を検索し、出発地から変更巡回地点と、当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して目的地に至る変更巡回経路を探索することが可能となる。このため、巡回経路のコストに対する影響の大きい巡回地点を変更して変更巡回経路を探索し、適切な巡回経路を案内することが可能となる。
【００１５】
更に、請求項５に係るプログラムでは、コンピュータは当該プログラムを読み込むことによって、巡回経路のコストがコスト上限値を超えた場合には、巡回地点毎に、当該巡回地点を変更した変更巡回地点を検索し、出発地から変更巡回地点と、当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して目的地に至る変更巡回経路を探索することが可能となる。このため、コンピュータは、巡回経路のコストに対する影響の大きい巡回地点を変更して変更巡回経路を探索し、適切な巡回経路を案内することが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明に係るナビゲーション装置、ナビゲーション方法及びプログラムを車載用ナビゲーション装置について具体化した一実施例に基づき図面を参照しつつ詳細に説明する。
【実施例】
【００１７】
［車載用ナビゲーション装置の概略構成］
先ず、本実施例に係る車載用ナビゲーション装置（以下、「ナビゲーション装置」という。）の概略構成について図１に基づいて説明する。図１は本実施例に係るナビゲーション装置１を示したブロック図である。
図１に示すように、本実施例に係るナビゲーション装置１は、自車の現在位置を検出する現在地検出処理部１１と、各種のデータが記録されたデータ記録部１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーション制御部１３と、操作者からの操作を受け付ける操作部１４と、操作者に対して地図等の情報を表示する液晶ディスプレイ１５と、経路案内等に関する音声ガイダンスを出力するスピーカ１６と、不図示の道路交通情報センタや地図情報配信センタ等との間で携帯電話網等を介して通信を行う通信装置１７とから構成されている。また、ナビゲーション制御部１３には自車の走行速度を検出する車速センサ２１が接続されている。
【００１８】
以下に、ナビゲーション装置１を構成する各構成要素について説明すると、現在地検出処理部１１は、ＧＰＳ３１、方位センサ３２、距離センサ３３等からなり、現在の自車の位置、方位、走行距離等を検出することが可能となっている。
【００１９】
また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記憶された地図情報データベース（地図情報ＤＢ）２５、時刻表データベース（時刻表ＤＢ）２７及び所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。
【００２０】
また、地図情報ＤＢ２５には、ナビゲーション装置１の走行案内や経路探索に使用されるナビ地図情報２６が格納されている。ここで、ナビ地図情報２６は、経路案内及び地図表示に必要な各種情報から構成されており、例えば、各新設道路を特定するための新設道路情報、地図を表示するための地図表示データ、各交差点に関する交差点データ、ノード点に関するノードデータ、道路（リンク）に関するリンクデータ、経路を探索するための探索データ、施設の一種である店舗等のＰＯＩ（Pointof Interest）に関する店舗データ、地点を検索するための検索データ、公共交通機関の路線に関する路線情報等から構成されている。また、店舗データとしては、各地域のホテル、病院、ガソリンスタンド、駐車場、駅、空港、バス停、フェリー乗り場等のＰＯＩに関するデータがＰＯＩを特定するＩＤとともに記憶されている。
また、地図情報ＤＢ２５の内容は、不図示の地図情報配信センタから通信装置１７を介して配信された更新情報をダウンロードすることによって更新される。
【００２１】
ここで、特に地図表示データとしては、約１０ｋｍ×１０ｋｍで区画された２次メッシュをベースに４分割（長さ１／２）、１６分割（１／４）、６４分割（１／８）されたユニットで構成されており、各ユニットのデータ量が略同レベルになるように、各地のユニットが設定されている。最も小さい６４分割サイズのユニットは、約１．２５ｋｍ四方の大きさである。また、約１０ｋｍ×１０ｋｍで区画された各２次メッシュ（以下、「メッシュ」という。）には、各メッシュを識別するメッシュＩＤがそれぞれ付されている。
【００２２】
また、探索データとしては、設定された目的地までの経路を周知のダイクストラ法等により探索及び表示する際に使用されるデータについて記録されており、ノードを通過する際の右左折や道路を構成するリンクの距離、旅行時間、道幅、道路種別等によって決定される各ノードの重み付け（以下、「コスト」という。）を算出する為に使用するコストデータ、経路探索により選択された経路を液晶ディスプレイ２５の地図上に表示するための経路表示データ等から構成されている。尚、本実施例では、コストとしてリンクの距離を採用し、探索された経路を評価するコストの一例として出発地から目的地までの走行距離を採用する。
【００２３】
また、時刻表ＤＢ２７には、鉄道、バス、地下鉄等の公共交通機関の各路線における最新の時刻表が格納されている。また、時刻表ＤＢ２７の内容は、不図示の地図情報配信センタから通信装置１７を介して配信された更新情報をダウンロードすることによって更新される。
【００２４】
また、図１に示すように、ナビゲーション装置１を構成するナビゲーション制御部１３は、ナビゲーション装置１の全体の制御を行う演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うに当たってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、後述の複数の地点を巡回地点として、出発地から目的地までの巡回経路を設定する巡回経路設定処理のプログラム（図２参照）等が記憶されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記憶するフラッシュメモリ４４等の内部記憶装置や、時間を計測するタイマ４５等を備えている。
【００２５】
更に、前記ナビゲーション制御部１３には、操作部１４、液晶ディスプレイ１５、スピーカ１６、通信装置１７の各周辺装置（アクチュエータ）が電気的に接続されている。
【００２６】
この操作部１４は、案内開始地点としての出発地、巡回地点としての各メンバーの自宅位置及び案内終了地点としての目的地を入力する際や施設に関する情報の検索を行う場合等に操作され、各種のキーや複数の操作スイッチから構成される。そして、ナビゲーション制御部１３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。更に、液晶ディスプレイ１５の前面部には、タッチパネルが設けられ、画面に表示されたボタンや地図上を押下することによって各種指示コマンドを入力することが可能に構成されている。
【００２７】
また、液晶ディスプレイ１５には、現在走行中の地図情報、操作案内、操作メニュー、キーの案内、現在地から各巡回地点を経由して目的地に至る推奨経路、推奨経路に沿った案内情報、交通情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。
【００２８】
また、スピーカ１６は、ナビゲーション制御部１３からの指示に基づいて、推奨経路に沿った走行を案内する音声ガイダンス等を出力する。ここで、案内される音声ガイダンスとしては、例えば、「２００ｍ先、○○交差点を右方向です。」等がある。
【００２９】
また、通信装置１７は、地図情報配信センタと通信を行う携帯電話網等による通信手段であり、地図情報配信センタとの間で最もバージョンの新しい更新地図情報や各公共交通機関の最新の時刻表等の送受信を行う。また、通信装置１７は地図情報配信センタに加えて、道路交通情報センタ等から送信された渋滞情報やサービスエリアの混雑状況等の各情報から成る交通情報を受信する。
【００３０】
［巡回経路設定処理］
次に、上記のように構成されたナビゲーション装置１のＣＰＵ４１が実行する処理であって、複数の地点を巡回地点として、出発地から目的地までの巡回経路を設定する巡回経路設定処理をグループメンバー全員の自宅を巡回地点として、出発地から目的地までの送迎経路を設定する場合について実行した一例を図２乃至図５に基づいて説明する。
【００３１】
図２は本実施例に係るナビゲーション装置１のＣＰＵ４１が実行する処理であって、グループメンバー全員の自宅を巡回地点として、出発地から目的地までの送迎経路を設定する送迎経路設定処理を示すメインフローチャートである。
尚、図２にフローチャートで示されるプログラムはナビゲーション装置１のナビゲーション制御部１３が備えているＲＯＭ４３に記憶されており、ＣＰＵ４１により出発地、巡回地点としての各メンバーの自宅位置及び目的地を操作部１４を介して入力された場合に実行される。
【００３２】
図２に示すように、先ず、ステップ（以下、Ｓと略記する）１１において、ＣＰＵ４１は、タッチパネル、操作スイッチ等の操作部１４の入力操作等によって、出発地、巡回地点としての送迎する各メンバーの自宅位置及び目的地が入力された場合には、各座標位置（例えば、緯度と経度である。）をナビ地図情報２６から取得してＲＡＭ４２に記憶する。
【００３３】
そして、Ｓ１２において、ＣＰＵ４１は、出発地から各巡回地点を経由して目的地に至る最小コストの巡回経路、つまり、最短走行距離の巡回経路を公知の巡回経路探索方法（例えば、特開平３−１９１４６４号公報参照）により探索して、「通常巡回経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この通常巡回経路の出発地から目的地に至る走行距離を通常巡回経路のコスト（以下、「通常巡回コスト」という。）としてＲＡＭ４２に記憶する。
【００３４】
続いて、Ｓ１３において、ＣＰＵ４１は、各巡回地点を経由しないで、出発地から直接目的地に至る経路をダイクストラ法等により探索して、「基準経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この基準経路の出発地から目的地に至る走行距離を基準経路のコスト（以下、「基準コスト」という。）として記憶する。そして、ＣＰＵ４１は、基準コストから「コスト上限値」を算出して、ＲＡＭ４２に記憶する。
【００３５】
例えば、ＣＰＵ４１は、予めＲＯＭ４３に記憶されるコスト上限係数（例えば、「１．２」等である。）を基準コストに積算した値を「コスト上限値」として、ＲＡＭ４２に記憶する。
尚、ＣＰＵ４１は、予めＲＯＭ４３に記憶される最大加算コスト（例えば、「２０ｋｍ」等である。）を基準コストに加算した値を「コスト上限値」として、ＲＡＭ４２に記憶するようにしてもよい。
【００３６】
ここで、通常巡回経路と基準経路の一例について図４に基づいて説明する。図４は通常巡回経路と基準経路の一例を示す説明図である。
図４に示すように、先ず、ＣＰＵ４１は、操作部１４を介して、当該ナビゲーション装置１が搭載された６人乗りの車両２を所有するメンバー１０１の自宅１０１Ａを出発地として入力される。また、ＣＰＵ４１は、操作部１４を介して、他の５人の各メンバー１０２〜１０６の各自宅１０２Ａ〜１０６Ａを各巡回地点として入力される。そして、ＣＰＵ４１は、操作部１４を介して、目的地１０７を入力された場合には、公知の巡回経路探索方法により自宅１０１Ａから各自宅１０２Ａ〜１０６Ａを巡回して目的地１０７に至る通常巡回経路１１０を探索して、ＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この通常巡回経路１１０の自宅１０１Ａから目的地１０７に至る走行距離を「通常巡回コスト」として記憶する。
【００３７】
また、ＣＰＵ４１は、ダイクストラ法等により各自宅１０２Ａ〜１０６Ａを経由しないで、自宅１０１Ａから直接目的地１０７に至る基準経路１１２を探索して、ＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この基準経路１１２の自宅１０１Ａから目的地に至る走行距離を「基準コスト」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、基準経路１１２の基準コストをＲＡＭ４２から、再度読み出し、予めＲＯＭ４３に記憶されるコスト上限係数（例えば、「１．２」等である。）を当該基準コストに積算した値を「コスト上限値」として、ＲＡＭ４２に記憶する。
尚、ＣＰＵ４１は、予めＲＯＭ４３に記憶される最大加算コスト（例えば、「２０ｋｍ」等である。）を当該基準コストに加算した値を「コスト上限値」として、ＲＡＭ４２に記憶するようにしてもよい。
【００３８】
続いて、図２に示すように、Ｓ１４において、ＣＰＵ４１は、ＲＡＭ４２から通常巡回コストとコスト上限値とを読み出し、当該通常巡回コストがコスト上限値よりも大きいか否か、つまり、当該通常巡回コストがコスト上限値を超えるか否かを判定する判定処理を実行する。
そして、当該通常巡回コストがコスト上限値を超えない場合には（Ｓ１４：ＮＯ）、ＣＰＵ４１は、Ｓ１５の処理に移行する。Ｓ１５において、ＣＰＵ４１は、ＲＡＭ４２から通常巡回経路を読み出して、提示する「巡回経路」としてＲＡＭ４２に再度記憶後、Ｓ２２の処理に移行する。
【００３９】
一方、当該通常巡回コストがコスト上限値を超える場合には（Ｓ１４：ＹＥＳ）、ＣＰＵ４１は、Ｓ１６の処理に移行する。Ｓ１６において、ＣＰＵ４１は、巡回地点としての送迎する各メンバーの自宅位置の座標位置を、出発地から遠い順に抽出して、つまり、出発地の座標位置から各メンバーの自宅位置の座標位置までの道なり距離の長い順に抽出して、順番に「巡回地点」としてＲＡＭ４２に記憶する。
尚、ＣＰＵ４１は、巡回地点としての送迎する各メンバーの自宅位置の座標位置を、出発地の座標位置から各メンバーの自宅位置の座標位置までの直線距離の長い順に抽出して、順番に「巡回地点」としてＲＡＭ４２に記憶するようにしてもよい。
【００４０】
続いて、Ｓ１７において、ＣＰＵ４１は、上記Ｓ１６で抽出して一番目に記憶した巡回地点から各巡回地点を順番に読み出し、つまり、出発地から最も遠い巡回地点から遠い順に各巡回地点を順番に読み出し、当該各巡回地点について、後述の通常巡回経路よりもコストが低い巡回経路を探索する「変更巡回経路探索処理」のサブ処理（図３参照）を実行する。
そして、上記Ｓ１６で抽出した全巡回地点について、後述の「変更巡回経路探索処理」のサブ処理を実行した場合には、ＣＰＵ４１は、Ｓ１８の処理に移行する。
【００４１】
Ｓ１８において、ＣＰＵ４１は、コストがコスト上限値以下の巡回経路である「候補巡回経路」があるか否か、つまり、「候補巡回経路」がＲＡＭ４２に記憶されているか否かを判定する判定処理を実行する。そして、コストがコスト上限値以下の巡回経路である「候補巡回経路」がＲＡＭ４２に記憶されている場合には（Ｓ１８：ＹＥＳ）、ＣＰＵ４１は、Ｓ１９の処理に移行する。
Ｓ１９において、ＣＰＵ４１は、ＲＡＭ４２に記憶されている各「候補巡回経路」のコストを抽出して、各「候補巡回経路」の中から最もコストの低い「候補巡回経路」を選択して、当該「候補巡回経路」を提示する「巡回経路」としてＲＡＭ４２に記憶後、Ｓ２１の処理に移行する。
【００４２】
一方、コストがコスト上限値以下の巡回経路である「候補巡回経路」がＲＡＭ４２に記憶されていない場合には（Ｓ１８：ＮＯ）、ＣＰＵ４１は、Ｓ２０の処理に移行する。Ｓ２０において、ＣＰＵ４１は、コストがコスト上限値を超えるが、通常巡回経路のコストよりも低い巡回経路である「予備巡回経路」があるか否か、つまり、「予備巡回経路」がＲＡＭ４２に記憶されているか否かを判定する判定処理を実行する。
【００４３】
そして、コストがコスト上限値を超えるが、通常巡回経路のコストよりも低い巡回経路である「予備巡回経路」がＲＡＭ４２に記憶されていない場合には（Ｓ２０：ＮＯ）、ＣＰＵ４１は、上記Ｓ１５の処理に移行する。
【００４４】
一方、コストがコスト上限値を超えるが、通常巡回経路のコストよりも低い巡回経路である「予備巡回経路」がＲＡＭ４２に記憶されている場合には（Ｓ２０：ＹＥＳ）、ＣＰＵ４１は、上記Ｓ１９の処理に移行する。Ｓ１９において、ＣＰＵ４１は、ＲＡＭ４２に記憶されている各「予備巡回経路」のコストを抽出して、各「予備巡回経路」の中から最もコストの低い「予備巡回経路」を選択して、当該「予備巡回経路」を提示する「巡回経路」としてＲＡＭ４２に記憶後、Ｓ２１の処理に移行する。
【００４５】
Ｓ２１において、ＣＰＵ４１は、ＲＡＭ４２に記憶されている「巡回経路」を、出発地から各メンバーが途中で乗る巡回地点を経由して目的地に至る巡回経路として確定し、当該巡回経路を液晶ディスプレイ１５に表示してユーザに案内経路として提示後、当該処理を終了する。
【００４６】
［変更巡回経路探索処理］
次に、ＣＰＵ４１が上記Ｓ１７において実行する「変更巡回経路探索処理」のサブ処理について図３に基づいて説明する。図３は図２の「変更巡回経路探索処理」のサブ処理を示すサブフローチャートである。
図３に示すように、Ｓ１１１において、ＣＰＵ４１は、ＲＡＭ４２から読み出した巡回地点を中心とした所定範囲内（例えば、半径２ｋｍ以内の範囲である。）における鉄道やバス、地下鉄等の公共交通機関の駅やバス停等の乗り場をナビ地図情報２６から抽出して、これらを特定する施設ＩＤをＲＡＭ４２に記憶する。一方、ＣＰＵ４１は、ＲＡＭ４２から読み出した巡回地点を中心とした所定範囲内に公共交通機関の駅やバス停等の乗り場が無い場合には、これらを特定する施設ＩＤをＲＡＭ４２に記憶しない。
【００４７】
続いて、Ｓ１１２において、ＣＰＵ４１は、当該巡回地点を中心とした所定範囲内に公共交通機関の駅やバス停等の乗り場があるか否か、つまり、公共交通機関の駅やバス停等を特定する施設ＩＤをＲＡＭ４２に記憶しているか否かを判定する判定処理を実行する。
そして、当該巡回地点を中心とした所定範囲内に公共交通機関の駅やバス停等の乗り場が無い場合、つまり、公共交通機関の駅やバス停等を特定する施設ＩＤをＲＡＭ４２に記憶していない場合には（Ｓ１１２：ＮＯ）、ＣＰＵ４１は、当該サブ処理を終了してメインフローチャートに戻る。
【００４８】
一方、当該巡回地点を中心とした所定範囲内に公共交通機関の駅やバス停等の乗り場がある場合、つまり、公共交通機関の駅やバス停等を特定する施設ＩＤをＲＡＭ４２に記憶している場合には（Ｓ１１２：ＹＥＳ）、ＣＰＵ４１は、Ｓ１１３の処理に移行する。Ｓ１１３において、ＣＰＵ４１は、この公共交通機関の駅やバス停を利用して到達可能な送迎可能地点を時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６から検索する。
【００４９】
具体的には、ＣＰＵ４１は、先ず、タイマ４５から現在の時刻を取得する。そして、ＣＰＵ４１は、ＲＡＭ４２に記憶されている利用可能な公共交通機関について、公共交通機関の駅やバス停等を特定する施設ＩＤを順番に読出し、それぞれについて、現在の時刻から当該巡回地点に到達する到達時刻を推定し、この到達時刻に基づいて当該駅やバス停等から乗ることが可能な路線上にあり、且つ、上記Ｓ１３で探索した「基準経路」に最も近い距離で降りることが可能な駅やバス停等の乗り場を時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６とから検索する。
【００５０】
例えば、ＣＰＵ４１は、当該駅やバス停等から乗ることが可能な路線上にあって、降りることが可能な駅やバス停の乗り場から上記Ｓ１３で探索した「基準経路」に対して垂線を引き、当該垂線の距離が最も短いものを、「基準経路」に最も近い距離で降りることが可能な駅やバス停等の乗り場とする。
【００５１】
そして、ＣＰＵ４１は、この各公共交通機関の時刻表とナビ地図情報２６から検索した駅やバス停等の各乗り場を特定する施設ＩＤと座標位置（例えば、緯度と経度である。）をナビ地図情報２６から読み出し、それぞれを「送迎可能地点」としてＲＡＭ４２に順次記憶する。
【００５２】
続いて、ＣＰＵ４１は、ＲＡＭ４２から各「送迎可能地点」の座標位置を読み出し、それぞれの「基準経路」までの距離を算出して、当該距離の短い順に各「送迎可能地点」の施設ＩＤと座標位置とを再度、ＲＡＭ４２に記憶する。そして、ＣＰＵ４１は、このＲＡＭ４２に記憶した「送迎可能地点」から、一番目に記憶した送迎可能地点から各送迎可能地点を順番に読み出し、つまり、基準経路に最も近い送迎可能地点から近い順に各送迎可能地点を順番に読み出し、各送迎可能地点についてＳ１１４〜Ｓ１１８の処理を実行する。
【００５３】
先ず、Ｓ１１４において、ＣＰＵ４１は、当該送迎可能地点とこの送迎可能地点に対応するメンバーを除いた他の送迎する各メンバーの自宅位置の座標位置をＲＡＭ４２から読み出して、各巡回地点の座標位置として再度ＲＡＭ４２に記憶する。そして、ＣＰＵ４１は、出発地から当該各巡回地点を経由して目的地に至る最小コストの経路、つまり、最短走行距離の経路を公知の巡回経路探索方法（例えば、特開平３−１９１４６４号公報参照）により探索して、「送迎可能巡回経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この送迎可能巡回経路の出発地から目的地に至る走行距離を算出して、送迎可能巡回経路のコスト（以下、「送迎可能巡回コスト」という。）としてＲＡＭ４２に記憶する。
【００５４】
続いて、Ｓ１１５において、ＣＰＵ４１は、ＲＡＭ４２から送迎可能巡回コストと通常巡回コストとを読み出し、当該送迎可能巡回コストが通常巡回コストよりも減少しているか否か、即ち、当該送迎可能巡回コストが通常巡回コスト未満であるか否かを判定する判定処理を実行する。
そして、当該送迎可能巡回コストが通常巡回コストよりも減少していない場合、即ち、当該送迎可能巡回コストが通常巡回コスト以上の場合には（Ｓ１１５：ＮＯ）、ＣＰＵ４１は、次の送迎可能地点をＲＡＭ４２から読み出し、この次の送迎可能地点についてＳ１１４以降の処理を再度実行する。一方、次の送迎可能地点がＲＡＭ４２に記憶されていない場合には、ＣＰＵ４１は、当該サブ処理を終了してメインフローチャートに戻る。
【００５５】
一方、当該送迎可能巡回コストが通常巡回コストよりも減少している場合、即ち、当該送迎可能巡回コストが通常巡回コスト未満の場合には（Ｓ１１５：ＹＥＳ）、ＣＰＵ４１は、Ｓ１１６の処理に移行する。
Ｓ１１６において、ＣＰＵ４１は、ＲＡＭ４２から送迎可能巡回コストとコスト上限値とを読み出し、当該送迎可能巡回コストがコスト上限値以下か否かを判定する判定処理を実行する。
【００５６】
そして、当該送迎可能巡回コストがコスト上限値以下の場合には（Ｓ１１６：ＹＥＳ）、ＣＰＵ４１は、Ｓ１１７の処理に移行する。Ｓ１１７において、ＣＰＵ４１は、当該送迎可能巡回経路をＲＡＭ４２から読み出し、「候補巡回経路」としてＲＡＭ４２に記憶する。その後、ＣＰＵ４１は、次の送迎可能地点をＲＡＭ４２から読み出し、この次の送迎可能地点についてＳ１１４以降の処理を再度実行する。一方、次の送迎可能地点がＲＡＭ４２に記憶されていない場合には、ＣＰＵ４１は、当該サブ処理を終了してメインフローチャートに戻る。
【００５７】
一方、当該送迎可能巡回コストがコスト上限値より大きい場合には（Ｓ１１６：ＮＯ）、ＣＰＵ４１は、Ｓ１１８の処理に移行する。Ｓ１１８において、ＣＰＵ４１は、当該送迎可能巡回経路をＲＡＭ４２から読み出し、「予備巡回経路」としてＲＡＭ４２に記憶する。その後、ＣＰＵ４１は、次の送迎可能地点をＲＡＭ４２から読み出し、この次の送迎可能地点についてＳ１１４以降の処理を再度実行する。一方、次の送迎可能地点がＲＡＭ４２に記憶されていない場合には、ＣＰＵ４１は、当該サブ処理を終了してメインフローチャートに戻る。
【００５８】
ここで、上記Ｓ１１４〜Ｓ１１８において、ＣＰＵ４１が探索した候補巡回経路と予備巡回経路の一例について図５に基づいて説明する。図５は候補巡回経路と予備巡回経路の一例を示す説明図である。
尚、図５においては、上記図４に示す各メンバー１０２〜１０６の中のメンバー１０６の自宅１０６Ａについて、ＣＰＵ４１は、上記Ｓ１１１〜Ｓ１１３の処理を実行した結果、当該自宅１０６Ａを中心とした半径約２ｋｍ以内の範囲１１５において、鉄道１１７のＸ駅１１８とＰバス停１２０とをナビ地図情報２６から抽出する。
【００５９】
また、ＣＰＵ４１は、現在時刻からＸ駅１１８に到達する到達時刻を推定し、この到達時刻に当該Ｘ駅１１８から乗車して降りることが可能な各駅から、基準経路１１２に垂線を引き、当該垂線の距離が最も短いＹ駅１２２を、時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６から検索する。また、ＣＰＵ４１は、現在時刻からＰバス停１２０に到達する到達時刻を推定し、この到達時刻に当該Ｐバス停１２０から乗車して降りることが可能な各バス停から、基準経路１１２に垂線を引き、当該垂線の距離が最も短いＱバス停１２４を、時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６から検索する。そして、ＣＰＵ４１は、この時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６から検索したＹ駅１２２とＱバス停１２４のそれぞれを特定する施設ＩＤと座標位置（例えば、緯度と経度である。）をナビ地図情報２６から読み出し、それぞれを「送迎可能地点」としてＲＡＭ４２に記憶した一例について説明する。
【００６０】
図５に示すように、ＣＰＵ４１は、メンバー１０１の自宅１０１Ａを出発地とし、各メンバー１０２〜１０５の各自宅１０２Ａ〜１０５ＡとＹ駅１２２とを経由して目的地１０７に至る巡回経路を公知の巡回経路探索方法により探索して、「送迎可能巡回経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この「送迎可能巡回経路」のコスト、つまり、「送迎可能巡回コスト」を算出してＲＡＭ４２に記憶する（Ｓ１１４）。
【００６１】
そして、ＣＰＵ４１は、この送迎可能巡回コストと、通常巡回経路１１０のコストである通常巡回コストと、基準経路１１２のコストから計算したコスト上限値とをＲＡＭ４２から読み出し、この送迎可能巡回コストがコスト上限値以下であるため、当該送迎可能巡回経路を候補巡回経路１３１としてＲＡＭ４２に記憶する（Ｓ１１５：ＹＥＳ〜Ｓ１１６：ＹＥＳ〜Ｓ１１７）。
【００６２】
また、ＣＰＵ４１は、メンバー１０１の自宅１０１Ａを出発地とし、各メンバー１０２〜１０５の各自宅１０２Ａ〜１０５ＡとＱバス停１２４とを経由して目的地１０７に至る巡回経路を公知の巡回経路探索方法により探索して、「送迎可能巡回経路」としてＲＡＭ４２に記憶する。また、ＣＰＵ４１は、この「送迎可能巡回経路」のコスト、つまり、「送迎可能巡回コスト」を算出してＲＡＭ４２に記憶する（Ｓ１１４）。
【００６３】
そして、ＣＰＵ４１は、この送迎可能巡回コストと、通常巡回経路１１０のコストである通常巡回コストと、基準経路１１２のコストから計算したコスト上限値とをＲＡＭ４２から読み出し、送迎可能巡回コストが通常巡回コストよりも低く、コスト上限値よりも大きいため、当該送迎可能巡回経路を予備巡回経路１３２としてＲＡＭ４２に記憶後、当該サブ処理を終了してメインフローチャートに戻る。（Ｓ１１５：ＹＥＳ〜Ｓ１１６：ＮＯ〜Ｓ１１８）。
【００６４】
［上記実施例の効果］
以上詳細に説明した通り、本実施例に係るナビゲーション装置１では、巡回地点として送迎する各メンバーの自宅位置を設定した際に、出発地から遠いメンバーがいたとしても、ＣＰＵ４１は、通常巡回経路のコストが、コスト上限値を超えた場合には、当該メンバーの自宅位置から公共交通機関を使用して移動可能な「送迎可能地点」を検索することが可能となる。
【００６５】
そして、ＣＰＵ４１は、当該送迎可能地点とこの送迎可能地点に対応するメンバーを除いた他の送迎する各メンバーの自宅位置を巡回地点として、出発地から当該各巡回地点を経由して目的地に至る、コスト上限値以下の候補巡回経路又は通常巡回経路よりもコストが減少した予備巡回経路を探索することが可能となる。このため、出発地から遠いメンバーがいたとしても、ＣＰＵ４１は、当該メンバーの送迎地点を公共交通機関を利用可能で基準経路に近い送迎地点に変更し、候補巡回経路又は予備巡回経路を探索して、コストの低い適切な巡回経路を案内することが可能となる。
【００６６】
また、ＣＰＵ４１は、当該送迎可能地点とこの送迎可能地点に対応するメンバーを除いた他の送迎する各メンバーの自宅位置を巡回地点として、出発地から当該各巡回地点を経由して目的地に至る巡回経路のコストが通常巡回経路のコスト以上になる場合には、当該巡回経路を選択しないため、通常巡回経路のコスト以下の案内経路を確実に選択することが可能となる。
【００６７】
また、ＣＰＵ４１は、通常巡回経路がコスト上限値を超える場合には、複数の候補巡回経路と予備巡回経路との中で最もコストの低い経路を出発地から目的地に至る案内経路として選択するため、最もコストの低い案内経路について経路案内を行うことが可能となる。
【００６８】
尚、本発明は前記実施例に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。例えば、以下のようにしてもよい。
【００６９】
（Ａ）上記Ｓ１１３において、巡回地点を中心とした所定範囲内にある公共交通機関の駅やバス停等の乗り場から、乗り換えを行って「基準経路」に近い距離で降りることが可能な駅やバス停等を時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６とから検索して、送迎可能地点としてもよい。
【００７０】
また、巡回地点を中心とした所定範囲内にある公共交通機関を使用する条件を指定するようにしてもよい。例えば、公共交通機関の特急や急行を利用するように指定してもよい。これにより、巡回地点を中心とした所定範囲内にある公共交通機関の駅やバス停等の乗り場から、特急や急行を利用して到達可能な「基準経路」に近い駅やバス停等を時刻表ＤＢ２７に記憶される各公共交通機関の時刻表とナビ地図情報２６とから検索して、送迎可能地点とすることができる。つまり、ユーザの希望に沿った条件で送迎可能地点を検索することが可能となる。
【００７１】
（Ｂ）また、上記Ｓ１１３において、検索した送迎可能地点に対応するメンバーは、当該送迎可能地点や基準経路から所定距離以内（例えば、約５００ｍ以内である。）の施設や地点等（例えば、駐車場や他の路線の駅やバス停等、または、交差点等である。）まで、タクシーや自家用車で行くようにしてもよい。これにより、公共交通機関の運転時刻に拘束されず、自由な時刻に候補巡回経路又は予備巡回経路に従って送迎を行うことが可能となる。
【図面の簡単な説明】
【００７２】
【図１】本実施例に係るナビゲーション装置を示したブロック図である。
【図２】ナビゲーション装置のＣＰＵが実行する処理であって、グループメンバー全員の自宅を巡回地点として、出発地から目的地までの送迎経路を設定する送迎経路設定処理を示すメインフローチャートである。
【図３】図２の「変更巡回経路探索処理」のサブ処理を示すサブフローチャートである。
【図４】通常巡回経路と基準経路の一例を示す説明図である。
【図５】候補巡回経路と予備巡回経路の一例を示す説明図である。
【符号の説明】
【００７３】
１ ナビゲーション装置
１１ 現在地検出処理部
１２ データ記録部
１３ ナビゲーション制御部
１４ 操作部
１５ 液晶ディスプレイ
２５ 地図情報ＤＢ
２６ ナビ地図情報
２７ 時刻表ＤＢ
４１ ＣＰＵ
４２ ＲＡＭ
４３ ＲＯＭ
１０１〜１０６ メンバー
１０１Ａ〜１０６Ａ 自宅
１０７ 目的地
１１０ 通常巡回経路
１１２ 基準経路
１３１ 候補巡回経路
１３２ 予備巡回経路
【特許請求の範囲】
【請求項１】
地図情報を記憶する地図情報記憶手段と、
出発地と目的地と複数の巡回地点とを入力する地点入力手段と、
前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を前記地図情報に基づいて探索する巡回経路探索手段と、
前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を前記地図情報に基づいて探索する基準経路探索手段と、
前記基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定手段と、
前記巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を前記地図情報に基づいて検索する変更巡回地点検索手段と、
前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を前記地図情報に基づいて探索する変更巡回経路探索手段と、
を備えたことを特徴とするナビゲーション装置。
【請求項２】
前記変更巡回経路のコストが前記巡回経路のコストよりも減少するか否かを判定するコスト判定手段を備え、
前記変更巡回経路のコストが前記巡回経路のコストよりも減少しない場合には、当該変更巡回経路を前記出発地から前記目的地に至る案内経路として選択しないことを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
前記変更巡回経路が複数個探索された場合には、当該複数個の変更巡回経路の中で最もコストの低い経路を前記出発地から前記目的地に至る案内経路として選択することを特徴とする請求項１又は請求項２に記載のナビゲーション装置。
【請求項４】
出発地と目的地と複数の巡回地点とを入力する地点入力工程と、
前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を地図情報に基づいて探索する巡回経路探索工程と、
前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を地図情報に基づいて探索する基準経路探索工程と、
前記基準経路探索工程で探索した基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定工程と、
前記巡回経路探索工程で探索した巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を地図情報に基づいて検索する変更巡回地点検索工程と、
前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を地図情報に基づいて探索する変更巡回経路探索工程と、
を備えたことを特徴とするナビゲーション方法。
【請求項５】
コンピュータに、
出発地と目的地と複数の巡回地点とを入力する地点入力工程と、
前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を地図情報に基づいて探索する巡回経路探索工程と、
前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を地図情報に基づいて探索する基準経路探索工程と、
前記基準経路探索工程で探索した基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定工程と、
前記巡回経路探索工程で探索した巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を地図情報に基づいて検索する変更巡回地点検索工程と、
前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を地図情報に基づいて探索する変更巡回経路探索工程と、
を実行させるためのプログラム。
【請求項１】
地図情報を記憶する地図情報記憶手段と、
出発地と目的地と複数の巡回地点とを入力する地点入力手段と、
前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を前記地図情報に基づいて探索する巡回経路探索手段と、
前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を前記地図情報に基づいて探索する基準経路探索手段と、
前記基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定手段と、
前記巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を前記地図情報に基づいて検索する変更巡回地点検索手段と、
前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を前記地図情報に基づいて探索する変更巡回経路探索手段と、
を備えたことを特徴とするナビゲーション装置。
【請求項２】
前記変更巡回経路のコストが前記巡回経路のコストよりも減少するか否かを判定するコスト判定手段を備え、
前記変更巡回経路のコストが前記巡回経路のコストよりも減少しない場合には、当該変更巡回経路を前記出発地から前記目的地に至る案内経路として選択しないことを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
前記変更巡回経路が複数個探索された場合には、当該複数個の変更巡回経路の中で最もコストの低い経路を前記出発地から前記目的地に至る案内経路として選択することを特徴とする請求項１又は請求項２に記載のナビゲーション装置。
【請求項４】
出発地と目的地と複数の巡回地点とを入力する地点入力工程と、
前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を地図情報に基づいて探索する巡回経路探索工程と、
前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を地図情報に基づいて探索する基準経路探索工程と、
前記基準経路探索工程で探索した基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定工程と、
前記巡回経路探索工程で探索した巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を地図情報に基づいて検索する変更巡回地点検索工程と、
前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を地図情報に基づいて探索する変更巡回経路探索工程と、
を備えたことを特徴とするナビゲーション方法。
【請求項５】
コンピュータに、
出発地と目的地と複数の巡回地点とを入力する地点入力工程と、
前記出発地から前記複数の巡回地点を巡回して前記目的地に至る巡回経路を地図情報に基づいて探索する巡回経路探索工程と、
前記複数の巡回地点を経由しないで、前記出発地から直接前記目的地に至る基準経路を地図情報に基づいて探索する基準経路探索工程と、
前記基準経路探索工程で探索した基準経路のコストに基づいて前記巡回経路のコスト上限値を設定する上限値設定工程と、
前記巡回経路探索工程で探索した巡回経路のコストが前記コスト上限値を超える場合には、前記巡回地点毎に、当該巡回地点を変更した変更巡回地点を地図情報に基づいて検索する変更巡回地点検索工程と、
前記出発地から前記変更巡回地点と当該変更巡回地点に対応する巡回地点を除いた各巡回地点とを巡回して前記目的地に至る変更巡回経路を地図情報に基づいて探索する変更巡回経路探索工程と、
を実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００９−２８８１８３（Ｐ２００９−２８８１８３Ａ）
【公開日】平成２１年１２月１０日（２００９．１２．１０）
【国際特許分類】
【出願番号】特願２００８−１４３５１３（Ｐ２００８−１４３５１３）
【出願日】平成２０年５月３０日（２００８．５．３０）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
【公開日】平成２１年１２月１０日（２００９．１２．１０）
【国際特許分類】
【出願日】平成２０年５月３０日（２００８．５．３０）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
[ Back to top ]