(57)【要約】【課題】複数の経由地を案内する案内スケジュールを、それぞれの経由地での滞在時間を考慮して生成すること。【解決手段】経由地指定手段２２は、目的地に到達するまでに案内する複数の経由地を指定する。選択手段２４は、事前に設定された目的地への到達時間までに複数の経由地を経由し、かつ、経由地に対して事前に設定された最大滞在時間以内で複数の経由地での滞在時間が最大となる案内スケジュールを選択する。【選択図】図６
2010204111.tif 000002
【特許請求の範囲】
【請求項１】
目的地に到達するまでに案内する複数の経由地を指定する経由地指定手段と、 
事前に設定された目的地への到達時刻までに上記複数の経由地を経由し、かつ、上記経由地に対して事前に設定された最大滞在時間以内で上記複数の経由地での滞在時間が最大となる案内スケジュールを選択する選択手段と、 
を有することを特徴とする案内経路探索装置。
【請求項２】
目的地に到達するまでに案内する複数の経由地を指定する経由地指定手段と、 
複数の経由地の滞在時間帯を、それぞれの経由地について事前に指定される滞在時刻および滞在時間に基づいて決定する仮決定手段と、 
上記複数の経由地の滞在時間帯および経由地間の移動時間に基づいてその複数の経由地を経由する案内スケジュールが成立するか否かを判定する判定手段と、 
上記判定手段において複数の経由地を経由する案内スケジュールが成立しないと判断された場合に、少なくとも１つの経由地の滞在時間を減らす調整手段と、 
を有することを特徴とする案内経路探索装置。
【請求項３】
目的地に到達するまでに案内する複数の経由地を指定する経由地指定手段と、 
複数の経由地を回る旅行の出発時刻から目的地への到着時刻までの旅行時間帯の範囲内においてそれぞれの経由地について事前に指定される滞在時間に基づいて、複数の経由地の滞在時間帯を決定する仮決定手段と、 
上記複数の経由地の滞在時間帯および経由地間の移動時間に基づいてその複数の経由地を経由する案内スケジュールが成立するか否かを判定する判定手段と、 
上記判定手段において複数の経由地を経由する案内スケジュールが成立しないと判断された場合に、少なくとも１つの経由地の滞在時間を減らす調整手段と、 
を有することを特徴とする案内経路探索装置。
【請求項４】
目的地に到達するまでに案内する複数の経由地を指定する経由地指定手段と、 
複数の経由地を回る旅行の出発時刻から到着時刻までの旅行時間帯の範囲内においてそれぞれの経由地について事前に指定される滞在時間に基づいて、複数の経由地の滞在時間帯を決定する仮決定手段と、 
上記旅行時間帯の範囲内において経由地での滞在時間帯と経由地間の移動時間の他に空き時間があるか否かを判定する判定手段と、 
上記判定手段において空き時間があると判定された場合に、その空き時間の一部または全部を少なくとも１つの経由地の上記滞在時間に加算する調整手段と、 
を有することを特徴とする案内経路探索装置。
【請求項５】
前記調整手段によって調整された複数の経由地の案内スケジュールを表示する表示手段と、 
上記表示手段に表示されている上記案内スケジュールを変更するために操作される入力手段と、 
上記入力手段での変更操作に応じて上記案内スケジュールを変更し、その変更した案内スケジュールを上記表示手段に表示させる変更手段と、 
を有することを特徴とする請求項１から４の中のいずれか１項記載の案内経路探索装置。
【請求項６】
前記それぞれの経由地について事前に指定される前記滞在時刻および／または前記滞在時間は、経由地、経由地の種類、利用者、利用グループ、利用時期、および利用年齢のうちの少なくとも１つに応じて指定されていることを特徴とする請求項２から４の中のいずれか１項記載の案内経路探索装置。
【請求項７】
現在の地点を示す値を繰り返し出力する現地位置更新手段と、 
上記現在の地点を示す値の地点を含む地図を、請求項１から６の中のいずれか１項記載の案内経路探索装置にて生成された複数の経由地を含む案内スケジュールに基づく案内経路とともに表示する表示手段と、 
を有することを特徴とするナビゲーション装置。
【請求項８】
目的地に到達するまでに案内する複数の経由地を指定するステップと、 
事前に設定された目的地への到達時刻までに上記複数の経由地を経由し、かつ、上記経由地に対して事前に設定された最大滞在時間以内で上記複数の経由地での滞在時間が最大となる案内スケジュールを選択するステップと、 
を有することを特徴とする案内経路の探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、案内経路探索装置、ナビゲーション装置および案内経路の探索方法に関する。
【背景技術】
【０００２】
特許文献１には、複数の経由地を経由する案内経路を探索する経路探索の方法が開示されている。この特許文献１に開示される従来の経路探索の方法では、経路を探索するために設定された探索条件と、特定の経由地同士の依存関係とに基づいて複数の経由地の通過順序を決定し、その通過順序で複数の経由地を通過して目的地に至る経路を探索する。また、この特許文献１は、経路を探索するために設定される探索条件が、時間（所要時間の短さ）と、距離（走行距離の短さ）と、料金（通行料金の低さ）との中から選択される例を開示している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００１−２２１６４７号公報（特許請求の範囲、段落００３３〜００５２など）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、この特許文献１に開示される従来の経路探索の方法を使用して探索された案内経路では、各経由地での滞在時間を考慮したプランを作成することは困難である。
【０００５】
そのため、特許文献１に開示される従来の経路探索の方法を用いて多くの経由地を経由する案内経路を作成し、その案内経路にて誘導される場合には、ユーザは、各経由地で滞在時間を気にしなければならない。そのため、ユーザは、時間に追われるようにして各経由地において早目に出発することになる。また、ユーザは、各経由地において早目に出発する結果として、たとえばホテルなどの目的地に予定した到着時刻より早く到着してしまうことも有りえる。
【０００６】
他にもたとえば、特許文献１に開示される従来の経路探索の方法を用いて余裕を見越して経由地を少なめに設定し、その案内経路にて誘導される場合には、ユーザは、各経由地において早目に出発する必要は無くなる。しかしながら、各経由地での適切な出発時刻などが解らないため、各経由地においてゆっくりと過ごしすぎて、経由地を少なめに設定したにもかかわらずホテルなどの目的地に予定よりも遅れて到着してしまうことが有りえる。
【０００７】
本発明は、複数の経由地を回る案内スケジュールを、それぞれの経由地での滞在時間を考慮して生成する案内経路探索装置および案内経路の探索方法を得ることを目的とする。
【０００８】
また、本発明は、複数の経由地での滞在時間を考慮して生成された案内スケジュールにて経路案内を行うナビゲーション装置を得ることを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係る案内経路探索装置は、目的地に到達するまでに案内する複数の経由地を指定する経由地指定手段と、事前に設定された目的地への到達時刻までに複数の経由地を経由し、かつ、経由地に対して事前に設定された最大滞在時間以内で複数の経由地での滞在時間が最大となる案内スケジュールを選択する選択手段と、を有するものである。
【００１０】
本発明に係る第二の案内経路探索装置は、目的地に到達するまでに案内する複数の経由地を指定する経由地指定手段と、複数の経由地の滞在時間帯を、それぞれの経由地について事前に指定される滞在時刻および滞在時間に基づいて決定する仮決定手段と、複数の経由地の滞在時間帯および経由地間の移動時間に基づいてその複数の経由地を経由する案内スケジュールが成立するか否かを判定する判定手段と、判定手段において複数の経由地を経由する案内スケジュールが成立しないと判断された場合に、少なくとも１つの経由地の滞在時間を減らす調整手段と、を有するものである。
【００１１】
本発明に係る第三の案内経路探索装置は、目的地に到達するまでに案内する複数の経由地を指定する経由地指定手段と、複数の経由地を回る旅行の出発時刻から目的地への到着時刻までの旅行時間帯の範囲内においてそれぞれの経由地について事前に指定される滞在時間に基づいて、複数の経由地の滞在時間帯を決定する仮決定手段と、複数の経由地の滞在時間帯および経由地間の移動時間に基づいてその複数の経由地を経由する案内スケジュールが成立するか否かを判定する判定手段と、判定手段において複数の経由地を経由する案内スケジュールが成立しないと判断された場合に、少なくとも１つの経由地の滞在時間を減らす調整手段と、を有するものである。
【００１２】
本発明に係る第四の案内経路探索装置は、目的地に到達するまでに案内する複数の経由地を指定する経由地指定手段と、複数の経由地を回る旅行の出発時刻から到着時刻までの旅行時間帯の範囲内においてそれぞれの経由地について事前に指定される滞在時間に基づいて、複数の経由地の滞在時間帯を決定する仮決定手段と、旅行時間帯の範囲内において経由地での滞在時間帯と経由地間の移動時間の他に空き時間があるか否かを判定する判定手段と、判定手段において空き時間があると判定された場合に、その空き時間の一部または全部を少なくとも１つの経由地の滞在時間に加算する調整手段と、を有するものである。
【００１３】
本発明に係る上述した各案内経路探索装置は、上述したそれぞれの構成に加えて、調整手段によって調整された複数の経由地の案内スケジュールを表示する表示手段と、表示手段に表示されている案内スケジュールを変更するために操作される入力手段と、入力手段での変更操作に応じて案内スケジュールを変更し、その変更した案内スケジュールを表示手段に表示させる変更手段と、を有するものである。
【００１４】
本発明に係る上述した各案内経路探索装置は、上述したそれぞれの構成に加えて、それぞれの経由地について事前に指定される滞在時刻および／または滞在時間は、経由地、経由地の種類、利用者、利用グループ、利用時期、および利用年齢のうちの少なくとも１つに応じて指定されているものである。
【００１５】
本発明に係るナビゲーション装置は、現在の地点を示す値を繰り返し出力する現地位置更新手段と、現在の地点を示す値の地点を含む地図を、上述したいずれかの発明に係る案内経路探索装置にて生成された複数の経由地を含む案内スケジュールに基づく案内経路とともに表示する表示手段と、を有するものである。
【００１６】
本発明に係る案内経路の探索方法は、目的地に到達するまでに案内する複数の経由地を指定するステップと、事前に設定された目的地への到達時刻までに複数の経由地を経由し、かつ、経由地に対して事前に設定された最大滞在時間以内で複数の経由地での滞在時間が最大となる案内スケジュールを選択するステップと、を有するものである。
【発明の効果】
【００１７】
本発明では、複数の経由地を回る案内スケジュールを、それぞれの経由地での滞在時間を考慮して生成することができる。
【００１８】
また、本発明では、複数の経由地での滞在時間を考慮して生成された案内スケジュールにて経路案内を行うことができる。
【図面の簡単な説明】
【００１９】
【図１】図１は、本発明の実施の形態１に係る車載ナビゲーション装置のハードウェア構成を示すブロック図である。
【図２】図２は、図１中のハードディスクドライブの記憶内容の説明図である。
【図３】図３は、図２中の経由候補地探索データの一例を示す説明図である。
【図４】図４は、図２中のジャンル別経由地条件テーブルの一例を示す説明図である。
【図５】図５は、図１の車載ナビゲーション装置に実現される案内経路生成のための機能ブロックを示すブロック図である。
【図６】図６は、図５中の推奨経路生成部が実行する探索処理の流れを示すフローチャートである。
【図７】図７は、本発明の実施の形態１における複数の経由地の組み合わせ例を示す図である。
【図８】図８は、本発明の実施の形態１においてユーザが入力した発着条件に基づく時間軸を示す図である
【図９】図９は、図７に示す複数の経由地の中の案内時刻が指定されている経由地Ａおよび経由地Ｂを発着条件に基づく時間軸上に載せた状態を示す図である。
【図１０】図１０は、図７に示すすべての経由地を、発着条件に基づく時間軸に載せた状態を示す図である。
【図１１】図１１は、図１０に示す状態の後に、すべての経由地の滞在時間を減らした状態を示す図である。
【図１２】図１２は、図１１に示す状態の後に、滞在時間同士が重なったままになっている経由地および経由地の滞在時間を減らした状態を示す図である。
【図１３】図１３は、実施の形態１における案内スケジュールの計算の一例を示す図である。
【図１４】図１４は、本発明の実施の形態２に係る車載ナビゲーション装置に実現される案内経路生成のための機能ブロックを示すブロック図である。
【図１５】図１５は、推奨経路生成部が生成した推奨経路を表示する表示画面の一例を示す画面説明図である。
【図１６】図１６は、推奨経路生成部が生成した図１５に示す推奨経路に喫茶店が経由地として追加された場合の、変更された推奨経路を表示する表示画面の一例を示す画面説明図である。
【図１７】図１７は、図１６に示す推奨経路において喫茶店が滝に変更された場合の、変更された推奨経路を表示する表示画面の一例を示す画面説明図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態に係る案内経路探索装置、ナビゲーション装置および案内経路の探索方法を、図面に基づいて説明する。ナビゲーション装置は、自動車、自動二輪、航空機などの車両に搭載する車載ナビゲーション装置を例として説明する。案内経路探索装置は、この車載ナビゲーション装置の構成の一部として説明する。案内経路の探索方法は、この車載ナビゲーション装置の動作の一部として説明する。 
【００２１】
実施の形態１． 
図１は、本発明の実施の形態１に係る車載ナビゲーション装置１のハードウェア構成を示すブロック図である。 
【００２２】
車載ナビゲーション装置１は、プログラムを実行する中央処理装置（ＣＰＵ：Central Processing
Unit）２と、実行中のプログラムやデータを記憶するＲＡＭ（Random Access Memory）３と、プログラムなどを記憶するハードディスクドライブ４と、表示データを表示する液晶モニタ５と、周辺機器が接続されるＩ／Ｏ（Input/Output）ポート６と、これらを接続するシステムバス７と、を有する。 
【００２３】
Ｉ／Ｏポート６には、液晶モニタ５の表示画面に重ねて配設され、押圧された部位を示す信号を出力するタッチパネル８と、ＧＰＳ（Global Positioning System）衛星からの電波を受信して現在の緯度経度の値を出力する現地位置更新手段としてのＧＰＳ受信機９と、ＦＭ波、光ビーコンあるいは電波ビーコンを受信してそれに含まれるＶＩＣＳ（Vehicle Information and Communication System）情報を出力するＶＩＣＳ受信機１０とが接続される。ＶＩＣＳ情報には、交通規制情報や渋滞情報などが含まれる。 
【００２４】
なお、液晶モニタ５は、Ｉ／Ｏポート６を介してシステムバス７に接続されていてもよい。また、Ｉ／Ｏポート６には、車両の速度に応じたパルスを出力する車速パルス発生器や、車両の移動方向を示すジャイロセンサなどが接続されていてもよい。 
【００２５】
図２は、図１中のハードディスクドライブ４の記憶内容の説明図である。 
【００２６】
ハードディスクドライブ４には、プログラム群と、データ群とが記憶される。ハードディスクドライブ４のプログラム群には、案内経路生成プログラム１１と、経路誘導プログラム１２とが含まれる。ハードディスクドライブ４のデータ群には、経由候補地探索データ１３と、経由候補地登録データ１４と、ジャンル別経由地条件テーブル１５と、経路探索データ１６と、経路探索条件データ１７と、地図データ１８とが含まれる。 
【００２７】
なお、経由候補地探索データ１３、ジャンル別経由地条件テーブル１５、経路探索データ１６、地図データ１８などは、車載ナビゲーション装置１に挿抜可能なコンピュータ読取可能な記録媒体に記録され、車載ナビゲーション装置１はこの記録媒体からこれらのデータを読み込むようにしてもよい。また、プログラム群とデータ群は、別々の記録媒体に記録されるようにしてもよい。 
【００２８】
経由候補地探索データ１３は、経由候補地毎のレコードを有する。経由候補地探索データ１３の経由候補地は、車載ナビゲーション装置１の出荷前などにおいて事前に登録されているものであり、たとえばレストラン、遊戯施設などが含まれる。 
【００２９】
図３は、図２中の経由候補地探索データ１３の一例を示す説明図である。図３では、１行毎に各レコードの登録情報が示される。各経由候補地のレコードには、経由候補地の名称、ジャンル、休業日、営業時間などの経由候補地の属性情報、経由候補地の地点を示す値などが含まれる。たとえば、「○○デパート」という名称の宿泊施設には、ジャンルとして「デパート」が対応付けられ、休業日として「水」曜日が対応付けられ、営業時間として「１０：００〜２０：００」が対応付けられ、地点を示す値として「１２２４」が対応付けられる。 
【００３０】
なお、経由候補地探索データ１３に登録される経由候補地の地点を示す値は、その経由候補地の緯度経度に基づく値であってもよいが、その緯度経度に基づく値と対応付けられている別の値、たとえばマップコード（登録商標）の値などであってもよい。また、経由候補地そのものの緯度経度に基づく値であってもよいが、たとえばその経由候補地と提携している駐車場などの経由候補地に関連する地点の緯度経度に基づく値であってもよい。 
【００３１】
経由候補地登録データ１４は、ユーザにより登録された経由候補地毎の複数のレコードを有する。各経由候補地のレコードには、たとえば経由候補地の名称、ジャンル、休業日、営業時間などの登録された経由候補地の属性情報、登録された経由候補地の地点を示す値などが含まれる。 
【００３２】
ジャンル別経由地条件テーブル１５は、ジャンル毎の複数のレコードを有する。ジャンルは、各経由候補地の属性情報の中の１つの情報である。ジャンルには、たとえばレストラン、名所、ホテルなどがある。 
【００３３】
図４は、図２中のジャンル別経由地条件テーブル１５の一例を示す説明図である。図４では、１行毎に各レコードの登録情報が示される。各ジャンルのレコードには、ジャンルの名称、案内時刻、滞在可能時間などのジャンルの属性情報が含まれる。たとえば、ジャンル「レストラン」には、案内時刻として「１３：００」が対応付けられ、滞在可能時間として「２時間」が対応付けられる。このジャンル毎の案内時刻および滞在可能時間が、この実施の形態１の各経由地について滞在条件となる。 
【００３４】
経路探索データ１６は、複数のノード情報と、複数のリンク情報を有する。ノード情報は、交差点などの地点に関する情報であり、その地点の識別情報、その地点を示す値、そのノードに接続されているリンクの識別番号のリストなどで構成される。リンク情報は、ノード間を接続する道路などの経路に関する情報であり、その経路の識別情報、接続されるノードの識別番号のリストなどで構成される。 
【００３５】
経路探索条件データ１７は、推奨経路を探索する際の探索条件を示すデータであり、たとえば最短距離、最短移動時間、一般道路優先、有料道路優先などの、複数の経路の中から１つを選択するための選択基準を示すデータである。なお、選択基準は、１つの基準項目のものに限定されるものではなく、複数の基準項目が組み合わされたものであってもよい。 
【００３６】
地図データ１８は、たとえば日本全国、関東地方、東京都などの所定の地域の地図を、複数のドットからなる画像データにデータ化したものである。各ドットは輝度情報を有する。地図には、道路地図、住宅地図などがある。また、地図データ１８は、地図データ１８の各ドットの地点を示す値を有する。 
【００３７】
次に、以上のような構成を有する実施の形態１に係る車載ナビゲーション装置１の動作を説明する。 
【００３８】
車載ナビゲーション装置１が起動されると、中央処理装置２は、ハードディスクドライブ４に記憶されているプログラムをＲＡＭ３に読み込んで実行する。 
【００３９】
中央処理装置２が案内経路生成プログラム１１を実行すると、車載ナビゲーション装置１には、案内経路を生成するための各種の機能ブロックが実現される。図５は、図１の車載ナビゲーション装置１に実現される案内経路生成のための機能ブロックを示すブロック図である。中央処理装置２が案内経路生成プログラム１１を実行することで、車載ナビゲーション装置１には、経由候補地登録部２１と、経由地選択部２２と、発着条件設定部２３と、推奨経路生成部２４と、推奨経路保存部２５とが実現される。 
【００４０】
経由候補地登録部２１は、経由候補地を登録、修正あるいは削除するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、経由候補地を登録、修正あるいは削除するための画面が表示される。そして、ユーザの操作に応じてタッチパネル８が生成する情報に基づいて、経由候補地登録部２１は、新たな経由候補地を経由候補地登録データ１４に登録したり、経由候補地登録データ１４に登録されている経由候補地の情報を変更したり、登録されている経由候補地を経由候補地登録データ１４から削除したりする。 
【００４１】
具体的にはたとえば、登録する経由候補地の名称、ジャンル、休業日、営業時間などの属性情報や、経由候補地の地点を示す画像が液晶モニタ５に表示され、ユーザの操作に応じてタッチパネル８から出力される画像上の操作位置情報に基づいて、経由候補地登録部２１は、経由候補地の属性情報などを特定し、経由候補地登録データ１４に新たなレコードを追加し、この追加したレコードにそれらの情報を格納する。なお、経由候補地登録データ１４に登録される経由候補地の地点を示す値は、ユーザが直接その値を入力するようにしてもよいが、他にもたとえば、地図データ１８をスクロール可能に液晶モニタ５に表示し、タッチパネル８から出力される操作情報に基づいてユーザが選択した地点を特定し、この特定した地点の地点を示す値で代用するようにしてもよい。 
【００４２】
経由地選択部２２は、経由地指定手段として機能し、経由候補地探索データ１３に予め登録されている経由候補地と経由候補地登録データ１４にユーザが登録した経由候補地との中から、経由候補地を選択するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、経由候補地を選択するための画面が表示される。 
【００４３】
そして、ユーザは、この液晶モニタ５の画面に応じてタッチパネル８を操作して所望の経由候補地を液晶モニタ５に表示させ、その所望の経由候補地を選択する。ユーザにより経由候補地が選択されると、経由地選択部２２は、その経由候補地を経由地としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。 
【００４４】
なお、経由候補地は、複数選択することができる。複数の経由候補地が選択された場合には、ＲＡＭ３あるいはハードディスクドライブ４には、その選択された複数の経由候補地が複数の経由地として記憶されることになる。 
【００４５】
経由地選択部２２での経由地の選択が完了すると、発着条件設定部２３は、出発地の地点および出発時刻、並びに、目的地の地点および到達時刻を入力するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、これらを入力するための画面が表示される。そして、ユーザは、この液晶モニタ５の画面に応じてタッチパネル８を操作して、出発地の地点、出発時刻、目的地の地点および到達時刻を入力する。 
【００４６】
なお、この出発地の地点、出発時刻、目的地の地点および到達時刻が、この実施の形態１に係る発着条件となる。また、出発地の出発時刻から目的地への到達時刻が、複数の経由地を回る旅行の出発時刻から到着時刻までの旅行時間帯となる。 
【００４７】
なお、出発地の地点を示す値および目的地の地点を示す値は、ユーザが直接その値を入力するようにしてもよいが、他にもたとえば、地図データ１８をスクロール可能に液晶モニタ５に表示し、タッチパネル８から出力される操作情報に基づいてユーザが選択した地点を特定し、この特定した地点の地点を示す値で代用するようにしてもよい。 
【００４８】
このように発着条件が指定されると、発着条件設定部２３は、出発地の地点、出発時刻、目的地の地点および到達時刻を、発着条件としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。 
【００４９】
発着条件設定部２３での発着条件の入力が完了すると、推奨経路生成部２４は、ユーザにより選択された経由地を経由して、ユーザが入力した出発地から目的地に至る推奨経路の探索処理を開始する。図６は、図５中の推奨経路生成部２４が実行する探索処理の流れを示すフローチャートである。 
【００５０】
推奨経路生成部２４は、まず、仮決定手段として機能して、ユーザにより選択された経由地の中から、案内時刻が指定されている経由地（以下、案内時刻指定経由地と記載する。）を抽出し、時間軸上においてその案内時刻指定経由地の滞在時間帯を、出発地の出発時刻から目的地への到着時刻までの旅行時間帯上に載せる。このとき、各案内時刻指定経由地の滞在時間は、滞在可能時間とする。これにより、案内時刻指定経由地の滞在時間帯が仮に決定される（ステップＳ１）。なお、滞在時間帯とは、滞在開始時刻から滞在終了時刻までの期間のことをいう。 
【００５１】
次に、推奨経路生成部２４は、判定手段として機能して、複数の案内時刻指定経由地の滞在時間帯同士が重なるか否かを判定する（ステップＳ２）。 
【００５２】
複数の案内時刻指定経由地の滞在時間帯同士が重なる場合には、推奨経路生成部２４は、調整手段として機能して、案内時刻指定経由地の滞在時間を所定の割合あるいは所定の時間だけ減らす（ステップＳ３）。 
【００５３】
続けて、推奨経路生成部２４は、滞在時間帯の重なりが解消されるか否かの判定を行う。滞在時間帯の重なりが解消されるか否かの判定は、たとえば削減処理の回数が所定の回数を超えたか否かに基づいて判定しても、十分な滞在時間を確保できなくなっているか否かに基づいて判定してもよい（ステップＳ４）。 
【００５４】
ステップＳ４において滞在時間帯の重なりが解消されないと判定した場合には、推奨経路生成部２４は、現状では立ち寄れない案内時刻指定経由地があることをユーザに警告を行う。この警告は、たとえば液晶モニタ５に表示すればよい（ステップＳ５）。 
【００５５】
ステップＳ２の判断において、複数の案内時刻指定経由地の滞在時間同士が重ならない場合には、推奨経路生成部２４は、仮決定手段として機能して、残りの経由地、すなわち案内時刻が指定されていない経由地（以下、案内時刻否指定経由地と記載する。）の滞在時間帯を、旅行時間帯上に載せる。このとき、各案内時刻否指定経由地の滞在時間は、滞在可能時間とする。これにより、案内時刻否指定経由地を含めたすべての経由地の滞在時間帯が仮に決定される。 
【００５６】
また、推奨経路生成部２４は、経由地間の移動時間（つまり、移動の時間帯）を、旅行時間帯上に載せる。この経由地間の移動時間は、固定的な移動時間であっても、単に経由地間の距離のみに応じた移動時間であっても、経路探索データ１６および経路探索条件データ１７に基づいて探索した実際の案内経路での移動時間であってもよい（ステップＳ６）。 
【００５７】
そして、推奨経路生成部２４は、判定手段として機能して、複数の経由地の滞在時間帯同士が重なるか否かを判定する（ステップＳ７）。 
【００５８】
複数の経由地の滞在時間帯同士が重なる場合には、推奨経路生成部２４は、調整手段として機能して、すべての経由地の滞在時間を所定の割合あるいは所定の時間だけ減らしたり、重なっている経由地の滞在時間のみを所定の割合あるいは所定の時間だけ減らしたりする（ステップＳ８）。 
【００５９】
なお、推奨経路生成部２４は、ステップＳ７において、複数の経由地の滞在時間帯同士が重なるか否かに替えて、複数の経由地を回ることができるか否かを判断し、回ることができないと判断した場合にステップＳ８へ進むようにしてもよい。 
【００６０】
その後、推奨経路生成部２４は、滞在時間帯の重なりが解消されるか否かの判定を行う。滞在時間帯の重なりが解消されるか否かの判定は、たとえば削減処理の回数が所定の回数を超えたか否かに基づいて判定しても、十分な滞在時間を確保できなくなっているか否かに基づいて判定してもよい（ステップＳ９）。 
【００６１】
そして、ステップＳ９において滞在時間帯の重なりが解消されないと判定した場合には、推奨経路生成部２４は、現状では立ち寄れない経由地があることをユーザに警告を行う。この警告は、たとえば液晶モニタ５に表示すればよい（ステップＳ１０）。 
【００６２】
ステップＳ７の判断において、すべての経由地の滞在時間帯が重ならないと判断した場合には、推奨経路生成部２４は、その経路を推奨経路とし、その推奨経路と各経由地での滞在時間帯を含めた案内スケジュールを生成する。推奨経路保存部２５は、この推奨経路を含む案内スケジュールを、その推奨経路での経由地間の実際の案内経路とともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。 
【００６３】
このように、推奨経路生成部２４は、事前に設定された目的地への到達時刻までに複数の経由地を経由し、かつ、経由地に対して事前に設定された最大滞在時間以内で複数の経由地での滞在時間が最大となる案内スケジュールを選択する選択手段として機能する。 
【００６４】
なお、推奨経路の生成処理において経由地間の実際の案内経路の探索処理が完了していない場合には、推奨経路保存部２５は、経路探索データ１６および経路探索条件データ１７に基づいて、経由地間の実際の案内経路を探索する。また、経路探索データ１６および経路探索条件データ１７などともに、ＶＩＣＳ受信機１０が受信した交通情報を利用してもよい。 
【００６５】
ところで、少なくとも１つの案内時刻否指定経由地を含む複数の経由地がユーザにより指定された場合、それら複数の経由地の経由順が互いに異なる複数の経由パターンが考えられる。そのような場合には、推奨経路生成部２４は、たとえば、ステップＳ６においてそのすべての組み合わせの経由順の経由パターンについて案内スケジュールを生成し、ステップＳ７において複数の経由地の滞在時間同士の重なり時間が最も小さいものを１つ選択したり、最も経由地間の総移動時間あるいは出発時刻から到着時刻までの総旅行距離が短いものを１つ選択したり、ユーザに１つを選択させたりすればよい。 
【００６６】
複数の経由パターンが考えられる場合の他の処理としては、たとえば、推奨経路生成部２４は、ステップＳ６においてはいずれか１つの経由順の経由パターンについての案内スケジュールを生成し、ステップＳ７〜Ｓ９の処理を所定回繰り返した後のステップＳ９の判断において複数の経由地の滞在時間帯同士が重なったままであると判断した場合には、他の経由順の経由パターンについての仮の案内スケジュールを生成し、その別の仮の案内スケジュールについてステップＳ７〜Ｓ９の処理を繰り返すようにしてもよい。この処理の場合、推奨経路生成部２４は、経由地のすべての組み合わせについての仮案内スケジュールにおいて複数の経由地の滞在時間帯同士が重なったままであると判断したら、ステップＳ１０の警告を行えばよい。なお、ステップＳ６において１つの経由順の経由パターンを選択する場合、たとえば出発地を出発してから複数の経由地を経由して目的地までに移動する総移動時間、総旅行距離などが短いものから順番に選択するようにすればよい。 
【００６７】
図７から図１２は、以上の推奨経路生成部２４による推奨経路の探索処理の一例を説明するための図である。 
【００６８】
図７は、本発明の実施の形態１における複数の経由地の組み合わせ例を示す図である。図７には、ユーザにより選択された４つの経由地Ａ３１，経由地Ｂ３２，経由地Ｃ３３，経由地Ｄ３４が示される。経由地Ａ３１の案内時刻は、１３：００であり、経由地Ａ３１の滞在可能時間は、２時間である。経由地Ｂ３２の案内時刻は、１５：００であり、経由地Ｂ３２の滞在可能時間は、２時間である。経由地Ｃ３３の案内時刻は、ジャンル別経由地条件テーブル１５において未定義であり、経由地Ｃ３３の滞在可能時間は、３時間である。経由地Ｄ３４の案内時刻は、ジャンル別経由地条件テーブル１５において未定義であり、経由地Ｄ３４の滞在可能時間は、４時間である。したがって、経由地Ａ３１と経由地Ｂ３２は、案内時刻指定経由地である。経由地Ｃ３３と経由地Ｄ３４は、案内時刻否指定経由地である。 
【００６９】
図８は、本発明の実施の形態１においてユーザが入力した発着条件に基づく旅行時間帯３５を示す図である。出発地は自宅であり、出発時刻は９：００である。目的地はホテルであり、到着時刻は１７：００である。 
【００７０】
このような４つの経由地Ａ，Ｂ，Ｃ，Ｄおよび発着条件がユーザにより入力されると、推奨経路生成部２４は、案内時刻指定経由地である経由地Ａ３１および経由地Ｂ３２を、９：００から１７：００までの旅行時間帯３５上に載せる（図６のステップＳ１）。図９は、図７に示す複数の経由地の中の案内時刻が指定されている経由地Ａ３１および経由地Ｂ３２の滞在時間帯を発着条件に基づく旅行時間帯３５上に載せた状態を示す図である。この場合、経由地Ａ３１には１２：００から１４：００まで滞在し、且つ、経由地Ｂ３２には１４：００から１６：００まで滞在することになるので、推奨経路生成部２４は、２つの案内時刻指定経由地の滞在時間帯同士は重ならないと判断する（図６のステップＳ２）。 
【００７１】
ステップＳ２の判断において、２つの案内時刻指定経由地の滞在時間帯同士が重ならないので、推奨経路生成部２４は、残りの２つ経由地、すなわち経由地Ｃ３３および経由地Ｄ３４の滞在時間帯を、旅行時間帯３５上に載せる（図６のステップＳ６）。
【００７２】
図１０は、図７に示すすべての経由地３１，３２，３３，３４を、発着条件に基づく旅行時間帯３５に載せた状態を示す図である。なお、図１０は、経由地間の移動時間を考慮した図とはなっていない。図１０の場合、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とが重なっている。また、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重なっている。 
【００７３】
図１０の状態である場合には、図６のステップＳ７において複数の経由地の滞在時間帯同士が重なっていると判断されるので、推奨経路生成部２４は、まず、すべての経由地３１，３２，３３，３４の滞在時間帯を所定の一定割合で減らす処理を行う（図６のステップＳ８）。 
【００７４】
図１１は、図１０に示す状態の後に、すべての経由地３１，３２，３３，３４の滞在時間を減らした状態を示す図である。図１１では、４つの経由地３１，３２，３３，３４の滞在時間を４分の３に減らしている。ただし、減少後の滞在時間は、０．５時間未満の端数を切り捨てた値（０．５の整数倍）とされる。図１１の場合、この処理によって、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とは、重ならなくなる。ただし、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とは重なったままである。 
【００７５】
その後、推奨経路生成部２４は、図６のステップＳ７において、再度、複数の経由地の滞在時間帯同士が重なっているか否かの判定を行う。そして、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重なったままであるので、推奨経路生成部２４は、再び、経由地の滞在時間を減らす処理を行う（図６のステップＳ８）。 
【００７６】
この場合、前回の滞在時間の減算処理によって、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とが重ならなくなっているので、推奨経路生成部２４は、経由地Ｂ３２の滞在時間および経由地Ｃ３３の滞在時間のみを減らす。 
【００７７】
図１２は、図１１に示す状態の後に、経由地Ｂ３２および経由地Ｃ３３の滞在時間を減らした状態を示す図である。図１２では、経由地Ｂ３２の滞在時間および経由地Ｃ３３の滞在時間を減らしている。図１２の場合、この処理によって、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重ならなくなる。 
【００７８】
そして、推奨経路生成部２４は、すべての経由地３１，３２，３３，３４の滞在時間同士が重なっていないので、再度、ステップＳ９およびステップＳ７の判断を繰り返し、生成した経路を推奨経路とする。 
【００７９】
なお、上述の説明では、出発地、経由地および目的地のうちの２地点間の移動時間帯を考慮していないが、地点間の移動時間帯については、上述の案内時間否指定経由地の滞在時間帯と同様にして旅行時間帯に載せるようにすればよい。ただし、経由地の滞在時間を短縮する場合には、地点間の移動時間は、予め計算などで得られたものであり、短縮できないので、経由地の滞在時間のみが短縮される。 
【００８０】
たとえば、経由地Ａの案内時刻が１３：００であり、経由地Ａの滞在可能時間が２時間であり、経由地Ｂの案内時刻が１５：００であり、経由地Ｂの滞在可能時間が２時間であり、経由地Ｃの滞在可能時間が１．５時間であり、経由地Ｄの滞在可能時間が１時間である場合において、経路パターンが経由地Ｄ−経由地Ａ−経由地Ｂ−経由地Ｃであり、かつ、出発地−経由地Ｄ間の移動時間が１時間であり、経由地Ｄ−経由地Ａ間の移動時間が１．５時間であり、経由地Ａ−経由地Ｂ間の移動時間が１時間であり、経由地Ｂ−経由地Ｃ間の移動時間が０．５時間であり、経由地Ｃ−目的地間の移動時間が０．５時間であるときについて説明する。図１３は、実施の形態１における案内スケジュールの計算の一例を示す図である。 
【００８１】
まず、図１３（Ａ）に示すように、推奨経路生成部２４は、案内時刻を中心とした滞在時間分の長さで定められる案内時刻指定経由地の経由地Ａ，Ｂの滞在時間帯を、仮に旅行時間帯に載せる。推奨経路生成部２４は、これらの滞在時間帯は重ならないと判断し、経由地Ａ，Ｂの滞在時間を短縮する処理をせずに次の処理に進む。 
【００８２】
次に、推奨経路生成部２４は、図１３（Ｂ）に示すように、案内時刻否指定経由地の経由地Ｃ，Ｄの滞在時間帯および各地点間の移動についての移動時間帯を、仮に旅行時間帯に載せる。なお、以下、出発地−経由地Ｄ間の移動をＭ１とし、経由地Ｄ−経由地Ａ間の移動をＭ２とし、経由地Ａ−経由地Ｂ間の移動をＭ３とし、経由地Ｂ−経由地Ｃ間の移動をＭ４とし、経由地Ｃ−目的地間の移動をＭ５とする。 
【００８３】
ここで、推奨経路生成部２４は、連続する移動時間帯および案内時刻否指定経由地の滞在時間帯を１つの時間帯にして、仮に旅行時間帯に載せる。この例では、Ｍ１とＤとＭ２の時間帯を１つの時間帯Ｎ１とし、Ｍ４とＣとＭ５の時間帯を１つの時間帯Ｎ２とする。 
【００８４】
推奨経路生成部２４は、出発時刻（＝９時）と時間帯Ｎ１の長さ３．５時間とに基づき、時間帯Ｎ１と経由地Ａの滞在時間帯ＮＡとが重なると判断し、また、滞在時間帯ＮＡの終了時刻と滞在時間帯ＮＢの開始時刻とに基づき、滞在時間帯ＮＡとＭ３の移動時間帯とが重なり、また、経由地Ｂの時間帯ＮＢとＭ３の移動時間帯とが重なると判断し、滞在時間帯ＮＢの終了時刻と目的地への到達時刻（＝１７時）とに基づき、滞在時間帯ＮＢと時間帯Ｎ２が重なると判断する。 
【００８５】
そこで、推奨経路生成部２４は、経由地Ａ，Ｂ，Ｃ，Ｄでの滞在時間を４分の３に短縮する（ただし、０．５時間未満は切り捨てとし、短縮後の滞在時間は０．５時間の整数倍とする）。これにより、経由地Ａの滞在時間は１．５時間とされ、経由地Ｂの滞在時間は１．５時間とされ、経由地Ｃの滞在時間は１時間とされ、経由地Ｄの滞在時間は１時間とされる。 
【００８６】
推奨経路生成部２４は、図１３（Ｃ）に示すように、経由地Ａの滞在時間帯ＮＡに案内時刻１３：００が含まれる範囲内で経由地Ａの滞在時間帯ＮＡをスライドし、経由地Ｂの滞在時間帯ＮＢに案内時刻１５：００が含まれる範囲内で経由地Ｂの滞在時間帯ＮＢをスライドする。これにより、時間帯Ｎ１と滞在時間帯ＮＡとが重ならなくなり、滞在時間帯ＮＡとＭ３の移動時間帯とが重ならなくなり、経由地Ｂの時間帯ＮＢとＭ３の移動時間帯とが重ならなくなる。 
【００８７】
しかしながら、この状態でも、滞在時間帯ＮＢの終了時刻と目的地への到達時刻と時間帯Ｎ２の長さとに基づき、滞在時間帯ＮＢと時間帯Ｎ２が重なると判断される。このため、推奨経路生成部２４は、図１３（Ｄ）に示すように、関連する経由地Ｂ，Ｃでの滞在時間を４分の３に短縮する（ただし、０．５時間未満は切り捨てとし、短縮後の滞在時間は０．５時間の整数倍とする）。これにより、経由地Ｂの滞在時間は１時間とされ、経由地Ｃの滞在時間は０．５時間とされ、滞在時間帯ＮＢと時間帯Ｎ２が重ならなくなる。 
【００８８】
このようにして、推奨経路生成部２４は、地点間の移動時間帯を含めて、経由地での滞在時間帯を決定し、推奨経路保存部２５は、これらの経由地に関する経路パターンおよび各時間帯を含む案内スケジュールをその経路パターンでの経由地間の案内経路データとともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。 
【００８９】
以上の処理により、案内経路が生成される。中央処理装置２が経路誘導プログラム１２を実行すると、車載ナビゲーション装置１には、経路誘導部が実現される。 
【００９０】
経路誘導部は、ＧＰＳ受信機９から出力される現在の緯度経度の値を周期的に読み取る。そして、経路誘導部は、読み取った現在の緯度経度の値に基づいて、現在位置を含む所定のエリアの画像データを地図データ１８から読み込み、この所定のエリアの画像データに現在位置のマークを重ねた画像データを液晶モニタ５へ出力する。液晶モニタ５には、現在位置のマークとその周辺の地図とが表示される。 
【００９１】
また、経路誘導部は、その表示エリア内となる案内経路が存在する場合には、その表示エリア内の部位を画像データに重ねる。これにより、液晶モニタ５には現在位置とともに案内経路が表示され、ユーザは、地図上で現在位置および案内経路を把握することができる。 
【００９２】
車両が移動すると、その移動に応じてＧＰＳ受信機９から出力される現在の緯度経度の値も変化する。経路誘導部は、現在位置のマークが液晶モニタ５に表示されつづけるように、上述の案内スケジュールおよび推奨経路のデータに基づいて、地図データ１８から読み込むエリアを切り替える。また、経路誘導部は、この切り替えたエリア内の案内経路を液晶モニタ５に表示させる。 
【００９３】
したがって、ユーザは、現在位置のマークが案内経路上を移動するように車両を移動させることで、出発地から各経由地を経由して目的地まで到達する。なお、上述の例では、ユーザは、出発地の自宅から経由地Ｄ、経由地Ａ、経由地Ｂおよび経由地Ｃをその順番に経由して目的地のホテルまで移動することができる。 
【００９４】
以上のように、この実施の形態１に係る車載ナビゲーション装置１では、ユーザが指定した発着条件の下で各経由地での滞在時間を最大限に確保した案内経路を生成し、この案内経路でユーザを誘導することができる。したがって、ユーザは、各経由地にできる限り長く滞在することができ、経由地での観光や食事などを満喫して一日を過ごすことができる。 
【００９５】
なお、この実施の形態１では、ジャンル別経由地条件テーブル１５では、各経由地での滞在可能時間が各経由地での最長の滞在時間として設定され、推奨経路生成部２４は、複数の経由地での滞在時間帯や経由地間の移動時間帯が重なったら経由地の滞在時間を減らしている。この他にもたとえば、ジャンル別経由地条件テーブル１５に各経由地での最短の滞在時間を別途設定し、推奨経路生成部２４は、各経由地での滞在時間がこの最短の滞在時間を下回らないように経由地の滞在時間を減らすようにしてもよい。これにより、各経由地での滞在時間が極端に短くなってしまうことを防止することができる。 
【００９６】
更に他にもたとえば、ジャンル別経由地条件テーブル１５に各経由地での最短の滞在時間のみを設定し、推奨経路生成部２４は、複数の経由地を経由しても余る空き時間を、少なくとも１つの経由地の滞在時間に加算するようにしてもよい。これにより、多くの経由地を回る案内経路を簡単な処理にて生成することができる。 
【００９７】
更に他にもたとえば、ジャンル別経由地条件テーブル１５などに経由地の滞在時間を固定要否するフラグを設定し、推奨経路生成部２４は、固定不要のフラグがついている経由地の滞在時間のみを調整するようにしてもよい。 
【００９８】
この実施の形態１では、ジャンル別経由地条件テーブル１５において各経由地について１つの案内時刻が設定されている。この他にもたとえば、ジャンル別経由地条件テーブル１５などにおいて各経由地について複数の案内時刻を設定できるようにしてもよい。これにより、案内時刻が指定されている経由地の案内時刻に自由度を持たせることができる。 
【００９９】
この実施の形態１では、推奨経路生成部２４は、各経由地を仮に旅行時間帯に載せる場合に、案内時刻が滞在可能時間の真中の時刻となるようにしている。この他にもたとえば、推奨経路生成部２４は、案内時刻から滞在が開始されるように、案内時刻が滞在可能時間の滞在開始時刻となるようにしてもよい。また、ジャンル別経由地条件テーブル１５などにおいて案内時刻の替わりに各経由地の出発時刻を設定し、推奨経路生成部２４は、この出発時刻に経由地から出発するように、出発時刻が滞在可能時間の滞在終了時刻となるようにしてもよい。 
【０１００】
この実施の形態１では、案内時刻および滞在可能時間は、ジャンル別経由地条件テーブル１５においてジャンル毎に１組ずつ設定されている。この他にもたとえば、案内時刻および滞在可能時間は、運転手毎に１組ずつ設定されていても、乗員構成毎に１組ずつ設定されていても、季節毎に１組ずつ設定されていても、年齢毎に１組ずつ設定されていてもよい。また、それらの組み合わせ毎に１組ずつ設定されていてもよい。また、ジャンル別経由地条件テーブル１５の案内時刻および滞在可能時間を、ユーザが更新できるようにしてもよい。 
【０１０１】
この実施の形態１では、各経由地での案内時刻および滞在可能時間は、ジャンル別経由地条件テーブル１５においてジャンル毎に設定されている。この他にもたとえば、経由候補地探索データ１３などにおいて、経由地毎に案内時刻および滞在可能時間が設定されていてもよい。これにより、ジャンル単位ではなく、経由候補地単位で個別に案内時刻および滞在可能時間を設定することができる。また、ユーザが経由地毎に案内時刻および滞在可能時間を入力するようにしてもよい。 
【０１０２】
実施の形態２． 
本発明の実施の形態２に係る車載ナビゲーション装置１のハードウェア構成、ハードディスクドライブ４の記憶内容は、実施の形態１に係る車載ナビゲーション装置１と同様である。ただし、案内経路生成プログラム１１の一部が変更されている。したがって、これらの構成については、実施の形態１と同じ符号を使用し、その説明を省略する。 
【０１０３】
次に、以上のような構成を有する実施の形態２に係る車載ナビゲーション装置１の動作を説明する。 
【０１０４】
中央処理装置２が案内経路生成プログラム１１を実行すると、車載ナビゲーション装置１には、案内経路を生成するための各種の機能ブロックが実現される。 
【０１０５】
図１４は、本発明の実施の形態２に係る車載ナビゲーション装置１に実現される案内経路生成のための機能ブロックを示すブロック図である。中央処理装置２が案内経路生成プログラム１１を実行することで、車載ナビゲーション装置１には、経由候補地登録部２１と、経由地選択部２２と、発着条件設定部２３と、推奨経路生成部２４と、経路修正部４１と、推奨経路保存部２５とが実現される。 
【０１０６】
経由候補地登録部２１は、経由候補地登録データ１４を更新する。経由地選択部２２は、経由候補地探索データ１３および経由候補地登録データ１４に基づいて、ユーザにより選択された複数の経由候補地を、複数の経由地としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。 
【０１０７】
発着条件設定部２３は、ユーザにより入力された出発地の地点および出発時刻、並びに、目的地の地点および到達時刻を発着条件としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。 
【０１０８】
推奨経路生成部２４は、ユーザにより選択された経由地を経由して、ユーザが入力した出発地から目的地に至る推奨経路を探索する。 
【０１０９】
経路修正部４１は、まず、推奨経路生成部２４が生成した推奨経路を表示手段としての液晶モニタ５に表示させる。そして、ユーザがこの液晶モニタ５の画面に応じてタッチパネル８を操作すると、変更手段としての経路修正部４１は、推奨経路生成部２４が生成した推奨経路を、その操作に応じた経路へ更新する。また、推奨経路保存部２５は、経路修正部４１によって更新された推奨経路と、その推奨経路での経由地間の実際の案内経路とを、表示手段としての液晶モニタ５に表示させるとともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。なお、この推奨経路に基づく経路誘導部の案内動作は、実施の形態１の経路誘導部の案内動作と同じであり、その説明を省略する。 
【０１１０】
図１５は、推奨経路生成部２４が生成した推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。この推奨経路生成部２４が生成した推奨経路では、出発地を９：００に出発した後、９：３０から１.５時間、公園（第一経由地）に滞在し、１１：５０から１．５時間、レストラン（第二経由地）で昼食をとり、１４：２０から２時間、動物園（第三経由地）に滞在し、１６：５０に目的地に到着する。 
【０１１１】
このような推奨経路が液晶モニタ５に表示されている状態で、ユーザが公園（第一経由地）とレストラン（第二経由地）との間に新たな経由地として喫茶店を追加すると、経路修正部４１は、第一経由地を公園、第二経由地を喫茶店、第三経由地をレストラン、第四経由地を動物園とする新たな推奨経路を生成する。また、経路修正部４１は、この新たな推奨経路での経由地間の移動時間を計算するとともに、ユーザが入力した発着条件を満たすように各経由地での滞在時間を見直して、新たな推奨経路を生成する。 
【０１１２】
図１６は、推奨経路生成部２４が生成した図１５に示す推奨経路に、喫茶店が経由地として追加された場合の、変更された推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。図１６の例では、公園とレストランの間に喫茶店が追加されることで、公園での滞在時間が１.５時間から１時間に短縮され、レストランでの滞在時間が１.５時間から１時間に短縮され、動物園への到着時刻が１４：２０から１４：３０へ変更されている。 
【０１１３】
また、図１６に示す推奨経路が液晶モニタ５に表示されている状態で、ユーザが公園（第一経由地）とレストラン（第二経由地）との間から、喫茶店を削除すると、経路修正部４１は、第一経由地を公園、第二経由地をレストラン、第三経由地を動物園とする新たな推奨経路を生成する。この経路は、図１５に例示する推奨経路と同じものとなる。 
【０１１４】
また、図１６に示す推奨経路が液晶モニタ５に表示されている状態で、ユーザが第二経由地の喫茶店を滝へ変更すると、経路修正部４１は、第一経由地を公園、第二経由地を滝、第三経由地をレストラン、第四経由地を動物園とする新たな推奨経路を生成する。 
【０１１５】
図１７は、図１６に示す推奨経路において喫茶店が滝へ変更された場合の、変更された推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。図１７の例では、喫茶店が滝へ変更されることで、レストランでの滞在時間が１時間から５０分へ短縮され、動物園への到着時刻が１４：３０から１４：４０へ変更されている。 
【０１１６】
以上のように、この実施の形態２に係る車載ナビゲーション装置１では、ユーザが指定した発着条件の下で各経由地での滞在時間を最大限に確保した案内経路を生成し、さらにその案内経路を適宜変更することができる。 
【０１１７】
したがって、ユーザは、単に車載ナビゲーション装置１が探索した案内経路ではなく、自分でカスタマイズした納得のいく案内経路にて誘導されることになる。 
【０１１８】
以上の各実施の形態は、本発明の好適な実施の形態の例であるが、本発明はこれに限定されるものではなく、種々の変形、変更が可能である。 
【０１１９】
たとえば、上記各実施の形態において、案内時刻は、その店舗などのジャンルの営業時間の典型値に基づいて設定されるようにしてもよい。また、案内時刻の設定がある場合、案内時刻の後の所定の時間は少なくとも滞在させる拘束条件を設けるようにしてもよい。 
【０１２０】
上記各実施の形態では、案内経路を生成する案内経路探索装置は、それが生成した案内経路で誘導を行う車載ナビゲーション装置１に組み込まれている。この他にもたとえば、案内経路探索装置は、車載ナビゲーション装置とは別体のコンピュータ装置などにおいて実現されてもよい。さらにたとえば、その車載ナビゲーション装置と、それとは別体のコンピュータ装置とは、インターネット、無線通信網などのデータ通信網を介してデータ通信可能に接続されていてもよい。さらにたとえば、車載ナビゲーション装置とは別体のコンピュータ装置は、データ通信網を介して、車載ナビゲーション装置において選択された複数の経由地に関する情報を受信し、且つ、生成した案内経路を車載ナビゲーション装置へ送信するように構成されていてもよい。 
【０１２１】
上記各実施の形態は、車載ナビゲーション装置１を例とするものである。本発明に係る案内経路探索装置、案内経路の探索方法およびナビゲーション装置は、この他にもたとえば、携帯電話端末、小型ノートコンピュータ装置、ＰＤＡ（Personal Digital Assistants）装置などのポータブル情報装置などに適用することができる。さらに、本発明に係る案内経路探索装置および案内経路の探索方法については、デスクトップコンピュータなどの情報装置などに適用することができる。 
【産業上の利用可能性】
【０１２２】
本発明に係る案内経路探索装置、ナビゲーション装置および案内経路の探索方法は、たとえば、自動車などの車両に搭載する車載ナビゲーション装置、歩行者用ナビゲーション装置、その他のナビゲーション装置などに利用することができる。
【符号の説明】
【０１２３】
１ 車載ナビゲーション装置（ナビゲーション装置） 
５ 液晶モニタ（表示手段） 
９ ＧＰＳ受信機（現地位置更新手段） 
１５ ジャンル別経由地条件テーブル（滞在時刻、滞在時間、滞在条件） 
２２ 経由地選択部（経由地指定手段） 
２４ 推奨経路生成部（選択手段、仮決定手段、判定手段、調整手段） 
４１ 経路修正部（変更手段）
【図１】
2010204111.tif 000003
【図２】
2010204111.tif 000004
【図３】
2010204111.tif 000005
【図４】
2010204111.tif 000006
【図５】
2010204111.tif 000007
【図６】
2010204111.tif 000008
【図７】
2010204111.tif 000009
【図８】
2010204111.tif 000010
【図９】
2010204111.tif 000011
【図１０】
2010204111.tif 000012
【図１１】
2010204111.tif 000013
【図１２】
2010204111.tif 000014
【図１３】
2010204111.tif 000015
【図１４】
2010204111.tif 000016
【図１５】
2010204111.tif 000017
【図１６】
2010204111.tif 000018
【図１７】
2010204111.tif 000019
【手続補正書】
【提出日】平成22年5月19日(2010.5.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻否指定経由地とを含む複数の経由地を設定する経由地指定手段と、
前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて経路を仮決定する第１の仮決定手段と、
前記第１の仮決定手段で仮決定した経路に前記複数の案内時刻指定経由地の滞在時間の重なりの有無を判定する第１の判定手段と、
前記第１の判定手段によって滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整手段と、
前記第１の調整手段で調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻否指定経由地を載せて経路を仮決定する第２の仮決定手段と、
前記第２の仮決定手段で仮決定した経路に前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりの有無を判定する第２の判定手段と、
前記第２の判定手段によって滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりを解消するよう滞在時間を調整して推奨経路とする第２の調整手段と、
を備えることを特徴とする案内経路探索装置。
【請求項２】
前記案内経路探索装置は複数の推奨経路を生成し、
前記複数の推奨経路の内の１つを選択する選択手段をさらに備える
ことを特徴とする請求項１記載の案内経路探索装置。
【請求項３】
前記第１及び第２の判定手段は、前記複数の案内時刻指定経由地間、前記案内時刻指定経由地と前記案内時刻否指定経由地との間の移動時間を考慮して滞在時間の重なりの有無を判定し、
前記第１及び第２の調整手段は、移動時間を考慮した滞在時間の重なりを解消するよう滞在時間を調整する
ことを特徴とする請求項１または２に記載の案内経路探索装置。
【請求項４】
所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻否指定経由地とを含む複数の経由地を設定する経由地指定ステップと、
前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて経路を仮決定する第１の仮決定ステップと、
前記第１の仮決定ステップにて仮決定した経路に前記複数の案内時刻指定経由地の滞在時間の重なりの有無を判定する第１の判定ステップと、
前記第１の判定ステップにて滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整ステップと、
前記第１の調整ステップにて調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻否指定経由地を載せて経路を仮決定する第２の仮決定ステップと、
前記第２の仮決定ステップにて仮決定した経路に前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりの有無を判定する第２の判定ステップと、
前記第２の判定ステップにて滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりを解消するよう滞在時間を調整して推奨経路とする第２の調整ステップと、
を含むことを特徴とする案内経路探索方法。
【請求項５】
複数の推奨経路を生成し、
前記複数の推奨経路の内の１つを選択する選択ステップをさらに含む
ことを特徴とする請求項４記載の案内経路探索方法。
【請求項６】
前記第１及び第２の判定ステップは、前記複数の案内時刻指定経由地間、前記案内時刻指定経由地と前記案内時刻否指定経由地との間の移動時間を考慮して滞在時間の重なりの有無を判定し、
前記第１及び第２の調整ステップは、移動時間を考慮した滞在時間の重なりを解消するよう滞在時間を調整する
ことを特徴とする請求項４または５に記載の案内経路探索方法。
【請求項７】
コンピュータに、
所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻否指定経由地とを含む複数の経由地を設定する経由地指定ステップと、
前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて経路を仮決定する第１の仮決定ステップと、
前記第１の仮決定ステップにて仮決定した経路に前記複数の案内時刻指定経由地の滞在時間の重なりの有無を判定する第１の判定ステップと、
前記第１の判定ステップにて滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整ステップと、
前記第１の調整ステップにて調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻否指定経由地を載せて経路を仮決定する第２の仮決定ステップと、
前記第２の仮決定ステップにて仮決定した経路に前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりの有無を判定する第２の判定ステップと、
前記第２の判定ステップにて滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりを解消するよう滞在時間を調整して推奨経路とする第２の調整ステップと、
を実行させることを特徴とする案内経路探索プログラム。
【請求項８】
請求項１〜３のいずれか１項に記載の案内経路探索装置で生成された推奨経路を案内経路として経路を誘導する経路誘導手段を備える
ことを特徴とするナビゲーション装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、案内経路探索装置、案内経路探索方法、案内経路探索プログラム、ナビゲーション装置に関する。
【背景技術】
【０００２】
特許文献１には、複数の経由地を経由する案内経路を探索する経路探索の方法が開示されている。この特許文献１に開示される従来の経路探索の方法では、経路を探索するために設定された探索条件と、特定の経由地同士の依存関係とに基づいて複数の経由地の通過順序を決定し、その通過順序で複数の経由地を通過して目的地に至る経路を探索する。また、この特許文献１は、経路を探索するために設定される探索条件が、時間（所要時間の短さ）と、距離（走行距離の短さ）と、料金（通行料金の低さ）との中から選択される例を開示している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００１−２２１６４７号公報（特許請求の範囲、段落００３３〜００５２など）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、この特許文献１に開示される従来の経路探索の方法を使用して探索された案内経路では、各経由地での滞在時間を考慮したプランを作成することは困難である。
【０００５】
そのため、特許文献１に開示される従来の経路探索の方法を用いて多くの経由地を経由する案内経路を作成し、その案内経路にて誘導される場合には、ユーザは、各経由地で滞在時間を気にしなければならない。そのため、ユーザは、時間に追われるようにして各経由地において早目に出発することになる。また、ユーザは、各経由地において早目に出発する結果として、たとえばホテルなどの目的地に予定した到着時刻より早く到着してしまうこともありえる。
【０００６】
他にもたとえば、特許文献１に開示される従来の経路探索の方法を用いて余裕を見越して経由地を少なめに設定し、その案内経路にて誘導される場合には、ユーザは、各経由地において早目に出発する必要はなくなる。しかしながら、各経由地での適切な出発時刻などが解らないため、各経由地においてゆっくりと過ごしすぎて、経由地を少なめに設定したにもかかわらずホテルなどの目的地に予定よりも遅れて到着してしまうことがありえる。
【０００７】
本発明は、複数の経由地を回る案内スケジュールを、それぞれの経由地での滞在時間を考慮して生成する案内経路探索装置、案内経路探索方法、案内経路探索プログラムを提供することを目的とする。
【０００８】
また、本発明は、複数の経由地での滞在時間を考慮して生成された案内スケジュールにて経路案内を行うナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の案内経路探索装置は、所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻否指定経由地とを含む複数の経由地を設定する経由地指定手段と、前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて経路を仮決定する第１の仮決定手段と、前記第１の仮決定手段で仮決定した経路に前記複数の案内時刻指定経由地の滞在時間の重なりの有無を判定する第１の判定手段と、前記第１の判定手段によって滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整手段と、前記第１の調整手段で調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻否指定経由地を載せて経路を仮決定する第２の仮決定手段と、前記第２の仮決定手段で仮決定した経路に前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりの有無を判定する第２の判定手段と、前記第２の判定手段によって滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりを解消するよう滞在時間を調整して推奨経路とする第２の調整手段と、を備えることを特徴とする。
【００１０】
前記案内経路探索装置は複数の推奨経路を生成し、前記複数の推奨経路の内の１つを選択する選択手段をさらに備えることを特徴とする。
【００１１】
前記第１及び第２の判定手段は、前記複数の案内時刻指定経由地間、前記案内時刻指定経由地と前記案内時刻否指定経由地との間の移動時間を考慮して滞在時間の重なりの有無を判定し、前記第１及び第２の調整手段は、移動時間を考慮した滞在時間の重なりを解消するよう滞在時間を調整することを特徴とする。
【００１２】
本発明の案内経路探索方法は、所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻否指定経由地とを含む複数の経由地を設定する経由地指定ステップと、前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて経路を仮決定する第１の仮決定ステップと、前記第１の仮決定ステップにて仮決定した経路に前記複数の案内時刻指定経由地の滞在時間の重なりの有無を判定する第１の判定ステップと、前記第１の判定ステップにて滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整ステップと、前記第１の調整ステップにて調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻否指定経由地を載せて経路を仮決定する第２の仮決定ステップと、前記第２の仮決定ステップにて仮決定した経路に前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりの有無を判定する第２の判定ステップと、前記第２の判定ステップにて滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりを解消するよう滞在時間を調整して推奨経路とする第２の調整ステップと、を含むことを特徴とする。
【００１３】
複数の推奨経路を生成し、前記複数の推奨経路の内の１つを選択する選択ステップをさらに含むことを特徴とする。
【００１４】
前記第１及び第２の判定ステップは、前記複数の案内時刻指定経由地間、前記案内時刻指定経由地と前記案内時刻否指定経由地との間の移動時間を考慮して滞在時間の重なりの有無を判定し、前記第１及び第２の調整ステップは、移動時間を考慮した滞在時間の重なりを解消するよう滞在時間を調整することを特徴とする。
【００１５】
本発明の案内経路探索プログラムは、コンピュータに、所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻否指定経由地とを含む複数の経由地を設定する経由地指定ステップと、前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて経路を仮決定する第１の仮決定ステップと、前記第１の仮決定ステップにて仮決定した経路に前記複数の案内時刻指定経由地の滞在時間の重なりの有無を判定する第１の判定ステップと、前記第１の判定ステップにて滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整ステップと、前記第１の調整ステップにて調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻否指定経由地を載せて経路を仮決定する第２の仮決定ステップと、前記第２の仮決定ステップにて仮決定した経路に前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりの有無を判定する第２の判定ステップと、前記第２の判定ステップにて滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻否指定経由地との滞在時間の重なりを解消するよう滞在時間を調整して推奨経路とする第２の調整ステップと、を実行させることを特徴とする。
【００１６】
本発明のナビゲーション装置は、上記の案内経路探索装置で生成された推奨経路を案内経路として経路を誘導する経路誘導手段を備えることを特徴とする。
【発明の効果】
【００１７】
本発明では、複数の経由地を回る案内スケジュールを、それぞれの経由地での滞在時間を考慮して生成することができる。
【００１８】
また、本発明では、複数の経由地での滞在時間を考慮して生成された案内スケジュールにて経路案内を行うことができる。
【図面の簡単な説明】
【００１９】
【図１】図１は、本発明の実施の形態１に係る車載ナビゲーション装置のハードウェア構成を示すブロック図である。
【図２】図２は、図１中のハードディスクドライブの記憶内容の説明図である。
【図３】図３は、図２中の経由候補地探索データの一例を示す説明図である。
【図４】図４は、図２中のジャンル別経由地条件テーブルの一例を示す説明図である。
【図５】図５は、図１の車載ナビゲーション装置に実現される案内経路生成のための機能ブロックを示すブロック図である。
【図６】図６は、図５中の推奨経路生成部が実行する探索処理の流れを示すフローチャートである。
【図７】図７は、本発明の実施の形態１における複数の経由地の組み合わせ例を示す図である。
【図８】図８は、本発明の実施の形態１においてユーザが入力した発着条件に基づく時間軸を示す図である
【図９】図９は、図７に示す複数の経由地の中の案内時刻が指定されている経由地Ａおよび経由地Ｂを発着条件に基づく時間軸上に載せた状態を示す図である。
【図１０】図１０は、図７に示すすべての経由地を、発着条件に基づく時間軸に載せた状態を示す図である。
【図１１】図１１は、図１０に示す状態の後に、すべての経由地の滞在時間を減らした状態を示す図である。
【図１２】図１２は、図１１に示す状態の後に、滞在時間同士が重なったままになっている経由地および経由地の滞在時間を減らした状態を示す図である。
【図１３】図１３は、実施の形態１における案内スケジュールの計算の一例を示す図である。
【図１４】図１４は、本発明の実施の形態２に係る車載ナビゲーション装置に実現される案内経路生成のための機能ブロックを示すブロック図である。
【図１５】図１５は、推奨経路生成部が生成した推奨経路を表示する表示画面の一例を示す画面説明図である。
【図１６】図１６は、推奨経路生成部が生成した図１５に示す推奨経路に喫茶店が経由地として追加された場合の、変更された推奨経路を表示する表示画面の一例を示す画面説明図である。
【図１７】図１７は、図１６に示す推奨経路において喫茶店が滝に変更された場合の、変更された推奨経路を表示する表示画面の一例を示す画面説明図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態に係る案内経路探索装置、案内経路探索方法、案内経路探索プログラム、ナビゲーション装置を、図面に基づいて説明する。ナビゲーション装置は、自動車、自動二輪、航空機などの車両に搭載する車載ナビゲーション装置を例として説明する。案内経路探索装置は、この車載ナビゲーション装置の構成の一部として説明する。案内経路の探索方法は、この車載ナビゲーション装置の動作の一部として説明する。
【００２１】
実施の形態１．
図１は、本発明の実施の形態１に係る車載ナビゲーション装置１のハードウェア構成を示すブロック図である。
【００２２】
車載ナビゲーション装置１は、プログラムを実行する中央処理装置（ＣＰＵ：Central Processing Unit）２と、実行中のプログラムやデータを記憶するＲＡＭ（Random Access Memory）３と、プログラムなどを記憶するハードディスクドライブ４と、表示データを表示する液晶モニタ５と、周辺機器が接続されるＩ／Ｏ（Input/Output）ポート６と、これらを接続するシステムバス７と、を有する。
【００２３】
Ｉ／Ｏポート６には、液晶モニタ５の表示画面に重ねて配設され、押圧された部位を示す信号を出力するタッチパネル８と、ＧＰＳ（Global Positioning System）衛星からの電波を受信して現在の緯度経度の値を出力する現地位置更新手段としてのＧＰＳ受信機９と、ＦＭ波、光ビーコンあるいは電波ビーコンを受信してそれに含まれるＶＩＣＳ（Vehicle Information and Communication System）情報を出力するＶＩＣＳ受信機１０とが接続される。ＶＩＣＳ情報には、交通規制情報や渋滞情報などが含まれる。
【００２４】
なお、液晶モニタ５は、Ｉ／Ｏポート６を介してシステムバス７に接続されていてもよい。また、Ｉ／Ｏポート６には、車両の速度に応じたパルスを出力する車速パルス発生器や、車両の移動方向を示すジャイロセンサなどが接続されていてもよい。
【００２５】
図２は、図１中のハードディスクドライブ４の記憶内容の説明図である。
【００２６】
ハードディスクドライブ４には、プログラム群と、データ群とが記憶される。ハードディスクドライブ４のプログラム群には、案内経路生成プログラム１１と、経路誘導プログラム１２とが含まれる。ハードディスクドライブ４のデータ群には、経由候補地探索データ１３と、経由候補地登録データ１４と、ジャンル別経由地条件テーブル１５と、経路探索データ１６と、経路探索条件データ１７と、地図データ１８とが含まれる。
【００２７】
なお、経由候補地探索データ１３、ジャンル別経由地条件テーブル１５、経路探索データ１６、地図データ１８などは、車載ナビゲーション装置１に挿抜可能なコンピュータ読取可能な記録媒体に記録され、車載ナビゲーション装置１はこの記録媒体からこれらのデータを読み込むようにしてもよい。また、プログラム群とデータ群は、別々の記録媒体に記録されるようにしてもよい。
【００２８】
経由候補地探索データ１３は、経由候補地毎のレコードを有する。経由候補地探索データ１３の経由候補地は、車載ナビゲーション装置１の出荷前などにおいて事前に登録されているものであり、たとえばレストラン、遊戯施設などが含まれる。
【００２９】
図３は、図２中の経由候補地探索データ１３の一例を示す説明図である。図３では、１行毎に各レコードの登録情報が示される。各経由候補地のレコードには、経由候補地の名称、ジャンル、休業日、営業時間などの経由候補地の属性情報、経由候補地の地点を示す値などが含まれる。たとえば、「○○デパート」という名称の宿泊施設には、ジャンルとして「デパート」が対応付けられ、休業日として「水」曜日が対応付けられ、営業時間として「１０：００〜２０：００」が対応付けられ、地点を示す値として「１２２４」が対応付けられる。
【００３０】
なお、経由候補地探索データ１３に登録される経由候補地の地点を示す値は、その経由候補地の緯度経度に基づく値であってもよいが、その緯度経度に基づく値と対応付けられている別の値、たとえばマップコード（登録商標）の値などであってもよい。また、経由候補地そのものの緯度経度に基づく値であってもよいが、たとえばその経由候補地と提携している駐車場などの経由候補地に関連する地点の緯度経度に基づく値であってもよい。
【００３１】
経由候補地登録データ１４は、ユーザにより登録された経由候補地毎の複数のレコードを有する。各経由候補地のレコードには、たとえば経由候補地の名称、ジャンル、休業日、営業時間などの登録された経由候補地の属性情報、登録された経由候補地の地点を示す値などが含まれる。
【００３２】
ジャンル別経由地条件テーブル１５は、ジャンル毎の複数のレコードを有する。ジャンルは、各経由候補地の属性情報の中の１つの情報である。ジャンルには、たとえばレストラン、名所、ホテルなどがある。
【００３３】
図４は、図２中のジャンル別経由地条件テーブル１５の一例を示す説明図である。図４では、１行毎に各レコードの登録情報が示される。各ジャンルのレコードには、ジャンルの名称、案内時刻、滞在可能時間などのジャンルの属性情報が含まれる。たとえば、ジャンル「レストラン」には、案内時刻として「１３：００」が対応付けられ、滞在可能時間として「２時間」が対応付けられる。このジャンル毎の案内時刻および滞在可能時間が、この実施の形態１の各経由地について滞在条件となる。
【００３４】
経路探索データ１６は、複数のノード情報と、複数のリンク情報を有する。ノード情報は、交差点などの地点に関する情報であり、その地点の識別情報、その地点を示す値、そのノードに接続されているリンクの識別番号のリストなどで構成される。リンク情報は、ノード間を接続する道路などの経路に関する情報であり、その経路の識別情報、接続されるノードの識別番号のリストなどで構成される。
【００３５】
経路探索条件データ１７は、推奨経路を探索する際の探索条件を示すデータであり、たとえば最短距離、最短移動時間、一般道路優先、有料道路優先などの、複数の経路の中から１つを選択するための選択基準を示すデータである。なお、選択基準は、１つの基準項目のものに限定されるものではなく、複数の基準項目が組み合わされたものであってもよい。
【００３６】
地図データ１８は、たとえば日本全国、関東地方、東京都などの所定の地域の地図を、複数のドットからなる画像データにデータ化したものである。各ドットは輝度情報を有する。地図には、道路地図、住宅地図などがある。また、地図データ１８は、地図データ１８の各ドットの地点を示す値を有する。
【００３７】
次に、以上のような構成を有する実施の形態１に係る車載ナビゲーション装置１の動作を説明する。
【００３８】
車載ナビゲーション装置１が起動されると、中央処理装置２は、ハードディスクドライブ４に記憶されているプログラムをＲＡＭ３に読み込んで実行する。
【００３９】
中央処理装置２が案内経路生成プログラム１１を実行すると、車載ナビゲーション装置１には、案内経路を生成するための各種の機能ブロックが実現される。図５は、図１の車載ナビゲーション装置１に実現される案内経路生成のための機能ブロックを示すブロック図である。中央処理装置２が案内経路生成プログラム１１を実行することで、車載ナビゲーション装置１には、経由候補地登録部２１と、経由地選択部２２と、発着条件設定部２３と、推奨経路生成部２４と、推奨経路保存部２５とが実現される。
【００４０】
経由候補地登録部２１は、経由候補地を登録、修正あるいは削除するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、経由候補地を登録、修正あるいは削除するための画面が表示される。そして、ユーザの操作に応じてタッチパネル８が生成する情報に基づいて、経由候補地登録部２１は、新たな経由候補地を経由候補地登録データ１４に登録したり、経由候補地登録データ１４に登録されている経由候補地の情報を変更したり、登録されている経由候補地を経由候補地登録データ１４から削除したりする。
【００４１】
具体的にはたとえば、登録する経由候補地の名称、ジャンル、休業日、営業時間などの属性情報や、経由候補地の地点を示す画像が液晶モニタ５に表示され、ユーザの操作に応じてタッチパネル８から出力される画像上の操作位置情報に基づいて、経由候補地登録部２１は、経由候補地の属性情報などを特定し、経由候補地登録データ１４に新たなレコードを追加し、この追加したレコードにそれらの情報を格納する。なお、経由候補地登録データ１４に登録される経由候補地の地点を示す値は、ユーザが直接その値を入力するようにしてもよいが、他にもたとえば、地図データ１８をスクロール可能に液晶モニタ５に表示し、タッチパネル８から出力される操作情報に基づいてユーザが選択した地点を特定し、この特定した地点の地点を示す値で代用するようにしてもよい。
【００４２】
経由地選択部２２は、経由地指定手段として機能し、経由候補地探索データ１３に予め登録されている経由候補地と経由候補地登録データ１４にユーザが登録した経由候補地との中から、経由候補地を選択するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、経由候補地を選択するための画面が表示される。
【００４３】
そして、ユーザは、この液晶モニタ５の画面に応じてタッチパネル８を操作して所望の経由候補地を液晶モニタ５に表示させ、その所望の経由候補地を選択する。ユーザにより経由候補地が選択されると、経由地選択部２２は、その経由候補地を経由地としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【００４４】
なお、経由候補地は、複数選択することができる。複数の経由候補地が選択された場合には、ＲＡＭ３あるいはハードディスクドライブ４には、その選択された複数の経由候補地が複数の経由地として記憶されることになる。
【００４５】
経由地選択部２２での経由地の選択が完了すると、発着条件設定部２３は、出発地の地点および出発時刻、並びに、目的地の地点および到達時刻を入力するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、これらを入力するための画面が表示される。そして、ユーザは、この液晶モニタ５の画面に応じてタッチパネル８を操作して、出発地の地点、出発時刻、目的地の地点および到達時刻を入力する。
【００４６】
なお、この出発地の地点、出発時刻、目的地の地点および到達時刻が、この実施の形態１に係る発着条件となる。また、出発地の出発時刻から目的地への到達時刻が、複数の経由地を回る旅行の出発時刻から到着時刻までの旅行時間帯となる。
【００４７】
なお、出発地の地点を示す値および目的地の地点を示す値は、ユーザが直接その値を入力するようにしてもよいが、他にもたとえば、地図データ１８をスクロール可能に液晶モニタ５に表示し、タッチパネル８から出力される操作情報に基づいてユーザが選択した地点を特定し、この特定した地点の地点を示す値で代用するようにしてもよい。
【００４８】
このように発着条件が指定されると、発着条件設定部２３は、出発地の地点、出発時刻、目的地の地点および到達時刻を、発着条件としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【００４９】
発着条件設定部２３での発着条件の入力が完了すると、推奨経路生成部２４は、ユーザにより選択された経由地を経由して、ユーザが入力した出発地から目的地に至る推奨経路の探索処理を開始する。図６は、図５中の推奨経路生成部２４が実行する探索処理の流れを示すフローチャートである。
【００５０】
推奨経路生成部２４は、まず、仮決定手段として機能して、ユーザにより選択された経由地の中から、案内時刻が指定されている経由地（以下、案内時刻指定経由地と記載する。）を抽出し、時間軸上においてその案内時刻指定経由地の滞在時間帯を、出発地の出発時刻から目的地への到着時刻までの旅行時間帯上に載せる。このとき、各案内時刻指定経由地の滞在時間は、滞在可能時間とする。これにより、案内時刻指定経由地の滞在時間帯が仮に決定される（ステップＳ１）。なお、滞在時間帯とは、滞在開始時刻から滞在終了時刻までの期間のことをいう。
【００５１】
次に、推奨経路生成部２４は、判定手段として機能して、複数の案内時刻指定経由地の滞在時間帯同士が重なるか否かを判定する（ステップＳ２）。
【００５２】
複数の案内時刻指定経由地の滞在時間帯同士が重なる場合には、推奨経路生成部２４は、調整手段として機能して、案内時刻指定経由地の滞在時間を所定の割合あるいは所定の時間だけ減らす（ステップＳ３）。
【００５３】
続けて、推奨経路生成部２４は、滞在時間帯の重なりが解消されるか否かの判定を行う。滞在時間帯の重なりが解消されるか否かの判定は、たとえば削減処理の回数が所定の回数を超えたか否かに基づいて判定しても、十分な滞在時間を確保できなくなっているか否かに基づいて判定してもよい（ステップＳ４）。
【００５４】
ステップＳ４において滞在時間帯の重なりが解消されないと判定した場合には、推奨経路生成部２４は、現状では立ち寄れない案内時刻指定経由地があることをユーザに警告を行う。この警告は、たとえば液晶モニタ５に表示すればよい（ステップＳ５）。
【００５５】
ステップＳ２の判断において、複数の案内時刻指定経由地の滞在時間同士が重ならない場合には、推奨経路生成部２４は、仮決定手段として機能して、残りの経由地、すなわち案内時刻が指定されていない経由地（以下、案内時刻否指定経由地と記載する。）の滞在時間帯を、旅行時間帯上に載せる。このとき、各案内時刻否指定経由地の滞在時間は、滞在可能時間とする。これにより、案内時刻否指定経由地を含めたすべての経由地の滞在時間帯が仮に決定される。
【００５６】
また、推奨経路生成部２４は、経由地間の移動時間（つまり、移動の時間帯）を、旅行時間帯上に載せる。この経由地間の移動時間は、固定的な移動時間であっても、単に経由地間の距離のみに応じた移動時間であっても、経路探索データ１６および経路探索条件データ１７に基づいて探索した実際の案内経路での移動時間であってもよい（ステップＳ６）。
【００５７】
そして、推奨経路生成部２４は、判定手段として機能して、複数の経由地の滞在時間帯同士が重なるか否かを判定する（ステップＳ７）。
【００５８】
複数の経由地の滞在時間帯同士が重なる場合には、推奨経路生成部２４は、調整手段として機能して、すべての経由地の滞在時間を所定の割合あるいは所定の時間だけ減らしたり、重なっている経由地の滞在時間のみを所定の割合あるいは所定の時間だけ減らしたりする（ステップＳ８）。
【００５９】
なお、推奨経路生成部２４は、ステップＳ７において、複数の経由地の滞在時間帯同士が重なるか否かに替えて、複数の経由地を回ることができるか否かを判断し、回ることができないと判断した場合にステップＳ８へ進むようにしてもよい。
【００６０】
その後、推奨経路生成部２４は、滞在時間帯の重なりが解消されるか否かの判定を行う。滞在時間帯の重なりが解消されるか否かの判定は、たとえば削減処理の回数が所定の回数を超えたか否かに基づいて判定しても、十分な滞在時間を確保できなくなっているか否かに基づいて判定してもよい（ステップＳ９）。
【００６１】
そして、ステップＳ９において滞在時間帯の重なりが解消されないと判定した場合には、推奨経路生成部２４は、現状では立ち寄れない経由地があることをユーザに警告を行う。この警告は、たとえば液晶モニタ５に表示すればよい（ステップＳ１０）。
【００６２】
ステップＳ７の判断において、すべての経由地の滞在時間帯が重ならないと判断した場合には、推奨経路生成部２４は、その経路を推奨経路とし、その推奨経路と各経由地での滞在時間帯を含めた案内スケジュールを生成する。推奨経路保存部２５は、この推奨経路を含む案内スケジュールを、その推奨経路での経由地間の実際の案内経路とともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【００６３】
このように、推奨経路生成部２４は、事前に設定された目的地への到達時刻までに複数の経由地を経由し、かつ、経由地に対して事前に設定された最大滞在時間以内で複数の経由地での滞在時間が最大となる案内スケジュールを選択する選択手段として機能する。
【００６４】
なお、推奨経路の生成処理において経由地間の実際の案内経路の探索処理が完了していない場合には、推奨経路保存部２５は、経路探索データ１６および経路探索条件データ１７に基づいて、経由地間の実際の案内経路を探索する。また、経路探索データ１６および経路探索条件データ１７などともに、ＶＩＣＳ受信機１０が受信した交通情報を利用してもよい。
【００６５】
ところで、少なくとも１つの案内時刻否指定経由地を含む複数の経由地がユーザにより指定された場合、それら複数の経由地の経由順が互いに異なる複数の経由パターンが考えられる。そのような場合には、推奨経路生成部２４は、たとえば、ステップＳ６においてそのすべての組み合わせの経由順の経由パターンについて案内スケジュールを生成し、ステップＳ７において複数の経由地の滞在時間同士の重なり時間が最も小さいものを１つ選択したり、最も経由地間の総移動時間あるいは出発時刻から到着時刻までの総旅行距離が短いものを１つ選択したり、ユーザに１つを選択させたりすればよい。
【００６６】
複数の経由パターンが考えられる場合の他の処理としては、たとえば、推奨経路生成部２４は、ステップＳ６においてはいずれか１つの経由順の経由パターンについての案内スケジュールを生成し、ステップＳ７〜Ｓ９の処理を所定回繰り返した後のステップＳ９の判断において複数の経由地の滞在時間帯同士が重なったままであると判断した場合には、他の経由順の経由パターンについての仮の案内スケジュールを生成し、その別の仮の案内スケジュールについてステップＳ７〜Ｓ９の処理を繰り返すようにしてもよい。この処理の場合、推奨経路生成部２４は、経由地のすべての組み合わせについての仮案内スケジュールにおいて複数の経由地の滞在時間帯同士が重なったままであると判断したら、ステップＳ１０の警告を行えばよい。なお、ステップＳ６において１つの経由順の経由パターンを選択する場合、たとえば出発地を出発してから複数の経由地を経由して目的地までに移動する総移動時間、総旅行距離などが短いものから順番に選択するようにすればよい。
【００６７】
図７から図１２は、以上の推奨経路生成部２４による推奨経路の探索処理の一例を説明するための図である。
【００６８】
図７は、本発明の実施の形態１における複数の経由地の組み合わせ例を示す図である。図７には、ユーザにより選択された４つの経由地Ａ３１，経由地Ｂ３２，経由地Ｃ３３，経由地Ｄ３４が示される。経由地Ａ３１の案内時刻は、１３：００であり、経由地Ａ３１の滞在可能時間は、２時間である。経由地Ｂ３２の案内時刻は、１５：００であり、経由地Ｂ３２の滞在可能時間は、２時間である。経由地Ｃ３３の案内時刻は、ジャンル別経由地条件テーブル１５において未定義であり、経由地Ｃ３３の滞在可能時間は、３時間である。経由地Ｄ３４の案内時刻は、ジャンル別経由地条件テーブル１５において未定義であり、経由地Ｄ３４の滞在可能時間は、４時間である。したがって、経由地Ａ３１と経由地Ｂ３２は、案内時刻指定経由地である。経由地Ｃ３３と経由地Ｄ３４は、案内時刻否指定経由地である。
【００６９】
図８は、本発明の実施の形態１においてユーザが入力した発着条件に基づく旅行時間帯３５を示す図である。出発地は自宅であり、出発時刻は９：００である。目的地はホテルであり、到着時刻は１７：００である。
【００７０】
このような４つの経由地Ａ，Ｂ，Ｃ，Ｄおよび発着条件がユーザにより入力されると、推奨経路生成部２４は、案内時刻指定経由地である経由地Ａ３１および経由地Ｂ３２を、９：００から１７：００までの旅行時間帯３５上に載せる（図６のステップＳ１）。図９は、図７に示す複数の経由地の中の案内時刻が指定されている経由地Ａ３１および経由地Ｂ３２の滞在時間帯を発着条件に基づく旅行時間帯３５上に載せた状態を示す図である。この場合、経由地Ａ３１には１２：００から１４：００まで滞在し、且つ、経由地Ｂ３２には１４：００から１６：００まで滞在することになるので、推奨経路生成部２４は、２つの案内時刻指定経由地の滞在時間帯同士は重ならないと判断する（図６のステップＳ２）。
【００７１】
ステップＳ２の判断において、２つの案内時刻指定経由地の滞在時間帯同士が重ならないので、推奨経路生成部２４は、残りの２つ経由地、すなわち経由地Ｃ３３および経由地Ｄ３４の滞在時間帯を、旅行時間帯３５上に載せる（図６のステップＳ６）。
【００７２】
図１０は、図７に示すすべての経由地３１，３２，３３，３４を、発着条件に基づく旅行時間帯３５に載せた状態を示す図である。なお、図１０は、経由地間の移動時間を考慮した図とはなっていない。図１０の場合、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とが重なっている。また、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重なっている。
【００７３】
図１０の状態である場合には、図６のステップＳ７において複数の経由地の滞在時間帯同士が重なっていると判断されるので、推奨経路生成部２４は、まず、すべての経由地３１，３２，３３，３４の滞在時間帯を所定の一定割合で減らす処理を行う（図６のステップＳ８）。
【００７４】
図１１は、図１０に示す状態の後に、すべての経由地３１，３２，３３，３４の滞在時間を減らした状態を示す図である。図１１では、４つの経由地３１，３２，３３，３４の滞在時間を４分の３に減らしている。ただし、減少後の滞在時間は、０．５時間未満の端数を切り捨てた値（０．５の整数倍）とされる。図１１の場合、この処理によって、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とは、重ならなくなる。ただし、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とは重なったままである。
【００７５】
その後、推奨経路生成部２４は、図６のステップＳ７において、再度、複数の経由地の滞在時間帯同士が重なっているか否かの判定を行う。そして、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重なったままであるので、推奨経路生成部２４は、再び、経由地の滞在時間を減らす処理を行う（図６のステップＳ８）。
【００７６】
この場合、前回の滞在時間の減算処理によって、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とが重ならなくなっているので、推奨経路生成部２４は、経由地Ｂ３２の滞在時間および経由地Ｃ３３の滞在時間のみを減らす。
【００７７】
図１２は、図１１に示す状態の後に、経由地Ｂ３２および経由地Ｃ３３の滞在時間を減らした状態を示す図である。図１２では、経由地Ｂ３２の滞在時間および経由地Ｃ３３の滞在時間を減らしている。図１２の場合、この処理によって、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重ならなくなる。
【００７８】
そして、推奨経路生成部２４は、すべての経由地３１，３２，３３，３４の滞在時間同士が重なっていないので、再度、ステップＳ９およびステップＳ７の判断を繰り返し、生成した経路を推奨経路とする。
【００７９】
なお、上述の説明では、出発地、経由地および目的地のうちの２地点間の移動時間帯を考慮していないが、地点間の移動時間帯については、上述の案内時間否指定経由地の滞在時間帯と同様にして旅行時間帯に載せるようにすればよい。ただし、経由地の滞在時間を短縮する場合には、地点間の移動時間は、予め計算などで得られたものであり、短縮できないので、経由地の滞在時間のみが短縮される。
【００８０】
たとえば、経由地Ａの案内時刻が１３：００であり、経由地Ａの滞在可能時間が２時間であり、経由地Ｂの案内時刻が１５：００であり、経由地Ｂの滞在可能時間が２時間であり、経由地Ｃの滞在可能時間が１．５時間であり、経由地Ｄの滞在可能時間が１時間である場合において、経路パターンが経由地Ｄ−経由地Ａ−経由地Ｂ−経由地Ｃであり、かつ、出発地−経由地Ｄ間の移動時間が１時間であり、経由地Ｄ−経由地Ａ間の移動時間が１．５時間であり、経由地Ａ−経由地Ｂ間の移動時間が１時間であり、経由地Ｂ−経由地Ｃ間の移動時間が０．５時間であり、経由地Ｃ−目的地間の移動時間が０．５時間であるときについて説明する。図１３は、実施の形態１における案内スケジュールの計算の一例を示す図である。
【００８１】
まず、図１３（Ａ）に示すように、推奨経路生成部２４は、案内時刻を中心とした滞在時間分の長さで定められる案内時刻指定経由地の経由地Ａ，Ｂの滞在時間帯を、仮に旅行時間帯に載せる。推奨経路生成部２４は、これらの滞在時間帯は重ならないと判断し、経由地Ａ，Ｂの滞在時間を短縮する処理をせずに次の処理に進む。
【００８２】
次に、推奨経路生成部２４は、図１３（Ｂ）に示すように、案内時刻否指定経由地の経由地Ｃ，Ｄの滞在時間帯および各地点間の移動についての移動時間帯を、仮に旅行時間帯に載せる。なお、以下、出発地−経由地Ｄ間の移動をＭ１とし、経由地Ｄ−経由地Ａ間の移動をＭ２とし、経由地Ａ−経由地Ｂ間の移動をＭ３とし、経由地Ｂ−経由地Ｃ間の移動をＭ４とし、経由地Ｃ−目的地間の移動をＭ５とする。
【００８３】
ここで、推奨経路生成部２４は、連続する移動時間帯および案内時刻否指定経由地の滞在時間帯を１つの時間帯にして、仮に旅行時間帯に載せる。この例では、Ｍ１とＤとＭ２の時間帯を１つの時間帯Ｎ１とし、Ｍ４とＣとＭ５の時間帯を１つの時間帯Ｎ２とする。
【００８４】
推奨経路生成部２４は、出発時刻（＝９時）と時間帯Ｎ１の長さ３．５時間とに基づき、時間帯Ｎ１と経由地Ａの滞在時間帯ＮＡとが重なると判断し、また、滞在時間帯ＮＡの終了時刻と滞在時間帯ＮＢの開始時刻とに基づき、滞在時間帯ＮＡとＭ３の移動時間帯とが重なり、また、経由地Ｂの時間帯ＮＢとＭ３の移動時間帯とが重なると判断し、滞在時間帯ＮＢの終了時刻と目的地への到達時刻（＝１７時）とに基づき、滞在時間帯ＮＢと時間帯Ｎ２が重なると判断する。
【００８５】
そこで、推奨経路生成部２４は、経由地Ａ，Ｂ，Ｃ，Ｄでの滞在時間を４分の３に短縮する（ただし、０．５時間未満は切り捨てとし、短縮後の滞在時間は０．５時間の整数倍とする）。これにより、経由地Ａの滞在時間は１．５時間とされ、経由地Ｂの滞在時間は１．５時間とされ、経由地Ｃの滞在時間は１時間とされ、経由地Ｄの滞在時間は１時間とされる。
【００８６】
推奨経路生成部２４は、図１３（Ｃ）に示すように、経由地Ａの滞在時間帯ＮＡに案内時刻１３：００が含まれる範囲内で経由地Ａの滞在時間帯ＮＡをスライドし、経由地Ｂの滞在時間帯ＮＢに案内時刻１５：００が含まれる範囲内で経由地Ｂの滞在時間帯ＮＢをスライドする。これにより、時間帯Ｎ１と滞在時間帯ＮＡとが重ならなくなり、滞在時間帯ＮＡとＭ３の移動時間帯とが重ならなくなり、経由地Ｂの時間帯ＮＢとＭ３の移動時間帯とが重ならなくなる。
【００８７】
しかしながら、この状態でも、滞在時間帯ＮＢの終了時刻と目的地への到達時刻と時間帯Ｎ２の長さとに基づき、滞在時間帯ＮＢと時間帯Ｎ２が重なると判断される。このため、推奨経路生成部２４は、図１３（Ｄ）に示すように、関連する経由地Ｂ，Ｃでの滞在時間を４分の３に短縮する（ただし、０．５時間未満は切り捨てとし、短縮後の滞在時間は０．５時間の整数倍とする）。これにより、経由地Ｂの滞在時間は１時間とされ、経由地Ｃの滞在時間は０．５時間とされ、滞在時間帯ＮＢと時間帯Ｎ２が重ならなくなる。
【００８８】
このようにして、推奨経路生成部２４は、地点間の移動時間帯を含めて、経由地での滞在時間帯を決定し、推奨経路保存部２５は、これらの経由地に関する経路パターンおよび各時間帯を含む案内スケジュールをその経路パターンでの経由地間の案内経路データとともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【００８９】
以上の処理により、案内経路が生成される。中央処理装置２が経路誘導プログラム１２を実行すると、車載ナビゲーション装置１には、経路誘導部が実現される。
【００９０】
経路誘導部は、ＧＰＳ受信機９から出力される現在の緯度経度の値を周期的に読み取る。そして、経路誘導部は、読み取った現在の緯度経度の値に基づいて、現在位置を含む所定のエリアの画像データを地図データ１８から読み込み、この所定のエリアの画像データに現在位置のマークを重ねた画像データを液晶モニタ５へ出力する。液晶モニタ５には、現在位置のマークとその周辺の地図とが表示される。
【００９１】
また、経路誘導部は、その表示エリア内となる案内経路が存在する場合には、その表示エリア内の部位を画像データに重ねる。これにより、液晶モニタ５には現在位置とともに案内経路が表示され、ユーザは、地図上で現在位置および案内経路を把握することができる。
【００９２】
車両が移動すると、その移動に応じてＧＰＳ受信機９から出力される現在の緯度経度の値も変化する。経路誘導部は、現在位置のマークが液晶モニタ５に表示されつづけるように、上述の案内スケジュールおよび推奨経路のデータに基づいて、地図データ１８から読み込むエリアを切り替える。また、経路誘導部は、この切り替えたエリア内の案内経路を液晶モニタ５に表示させる。
【００９３】
したがって、ユーザは、現在位置のマークが案内経路上を移動するように車両を移動させることで、出発地から各経由地を経由して目的地まで到達する。なお、上述の例では、ユーザは、出発地の自宅から経由地Ｄ、経由地Ａ、経由地Ｂおよび経由地Ｃをその順番に経由して目的地のホテルまで移動することができる。
【００９４】
以上のように、この実施の形態１に係る車載ナビゲーション装置１では、ユーザが指定した発着条件の下で各経由地での滞在時間を最大限に確保した案内経路を生成し、この案内経路でユーザを誘導することができる。したがって、ユーザは、各経由地にできる限り長く滞在することができ、経由地での観光や食事などを満喫して一日を過ごすことができる。
【００９５】
なお、この実施の形態１では、ジャンル別経由地条件テーブル１５では、各経由地での滞在可能時間が各経由地での最長の滞在時間として設定され、推奨経路生成部２４は、複数の経由地での滞在時間帯や経由地間の移動時間帯が重なったら経由地の滞在時間を減らしている。この他にもたとえば、ジャンル別経由地条件テーブル１５に各経由地での最短の滞在時間を別途設定し、推奨経路生成部２４は、各経由地での滞在時間がこの最短の滞在時間を下回らないように経由地の滞在時間を減らすようにしてもよい。これにより、各経由地での滞在時間が極端に短くなってしまうことを防止することができる。
【００９６】
さらに他にもたとえば、ジャンル別経由地条件テーブル１５に各経由地での最短の滞在時間のみを設定し、推奨経路生成部２４は、複数の経由地を経由しても余る空き時間を、少なくとも１つの経由地の滞在時間に加算するようにしてもよい。これにより、多くの経由地を回る案内経路を簡単な処理にて生成することができる。
【００９７】
さらに他にもたとえば、ジャンル別経由地条件テーブル１５などに経由地の滞在時間を固定要否するフラグを設定し、推奨経路生成部２４は、固定不要のフラグがついている経由地の滞在時間のみを調整するようにしてもよい。
【００９８】
この実施の形態１では、ジャンル別経由地条件テーブル１５において各経由地について１つの案内時刻が設定されている。この他にもたとえば、ジャンル別経由地条件テーブル１５などにおいて各経由地について複数の案内時刻を設定できるようにしてもよい。これにより、案内時刻が指定されている経由地の案内時刻に自由度を持たせることができる。
【００９９】
この実施の形態１では、推奨経路生成部２４は、各経由地を仮に旅行時間帯に載せる場合に、案内時刻が滞在可能時間の真中の時刻となるようにしている。この他にもたとえば、推奨経路生成部２４は、案内時刻から滞在が開始されるように、案内時刻が滞在可能時間の滞在開始時刻となるようにしてもよい。また、ジャンル別経由地条件テーブル１５などにおいて案内時刻の替わりに各経由地の出発時刻を設定し、推奨経路生成部２４は、この出発時刻に経由地から出発するように、出発時刻が滞在可能時間の滞在終了時刻となるようにしてもよい。
【０１００】
この実施の形態１では、案内時刻および滞在可能時間は、ジャンル別経由地条件テーブル１５においてジャンル毎に１組ずつ設定されている。この他にもたとえば、案内時刻および滞在可能時間は、運転手毎に１組ずつ設定されていても、乗員構成毎に１組ずつ設定されていても、季節毎に１組ずつ設定されていても、年齢毎に１組ずつ設定されていてもよい。また、それらの組み合わせ毎に１組ずつ設定されていてもよい。また、ジャンル別経由地条件テーブル１５の案内時刻および滞在可能時間を、ユーザが更新できるようにしてもよい。
【０１０１】
この実施の形態１では、各経由地での案内時刻および滞在可能時間は、ジャンル別経由地条件テーブル１５においてジャンル毎に設定されている。この他にもたとえば、経由候補地探索データ１３などにおいて、経由地毎に案内時刻および滞在可能時間が設定されていてもよい。これにより、ジャンル単位ではなく、経由候補地単位で個別に案内時刻および滞在可能時間を設定することができる。また、ユーザが経由地毎に案内時刻および滞在可能時間を入力するようにしてもよい。
【０１０２】
実施の形態２．
本発明の実施の形態２に係る車載ナビゲーション装置１のハードウェア構成、ハードディスクドライブ４の記憶内容は、実施の形態１に係る車載ナビゲーション装置１と同様である。ただし、案内経路生成プログラム１１の一部が変更されている。したがって、これらの構成については、実施の形態１と同じ符号を使用し、その説明を省略する。
【０１０３】
次に、以上のような構成を有する実施の形態２に係る車載ナビゲーション装置１の動作を説明する。
【０１０４】
中央処理装置２が案内経路生成プログラム１１を実行すると、車載ナビゲーション装置１には、案内経路を生成するための各種の機能ブロックが実現される。
【０１０５】
図１４は、本発明の実施の形態２に係る車載ナビゲーション装置１に実現される案内経路生成のための機能ブロックを示すブロック図である。中央処理装置２が案内経路生成プログラム１１を実行することで、車載ナビゲーション装置１には、経由候補地登録部２１と、経由地選択部２２と、発着条件設定部２３と、推奨経路生成部２４と、経路修正部４１と、推奨経路保存部２５とが実現される。
【０１０６】
経由候補地登録部２１は、経由候補地登録データ１４を更新する。経由地選択部２２は、経由候補地探索データ１３および経由候補地登録データ１４に基づいて、ユーザにより選択された複数の経由候補地を、複数の経由地としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【０１０７】
発着条件設定部２３は、ユーザにより入力された出発地の地点および出発時刻、並びに、目的地の地点および到達時刻を発着条件としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【０１０８】
推奨経路生成部２４は、ユーザにより選択された経由地を経由して、ユーザが入力した出発地から目的地に至る推奨経路を探索する。
【０１０９】
経路修正部４１は、まず、推奨経路生成部２４が生成した推奨経路を表示手段としての液晶モニタ５に表示させる。そして、ユーザがこの液晶モニタ５の画面に応じてタッチパネル８を操作すると、変更手段としての経路修正部４１は、推奨経路生成部２４が生成した推奨経路を、その操作に応じた経路へ更新する。また、推奨経路保存部２５は、経路修正部４１によって更新された推奨経路と、その推奨経路での経由地間の実際の案内経路とを、表示手段としての液晶モニタ５に表示させるとともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。なお、この推奨経路に基づく経路誘導部の案内動作は、実施の形態１の経路誘導部の案内動作と同じであり、その説明を省略する。
【０１１０】
図１５は、推奨経路生成部２４が生成した推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。この推奨経路生成部２４が生成した推奨経路では、出発地を９：００に出発した後、９：３０から１.５時間、公園（第一経由地）に滞在し、１１：５０から１．５時間、レストラン（第二経由地）で昼食をとり、１４：２０から２時間、動物園（第三経由地）に滞在し、１６：５０に目的地に到着する。
【０１１１】
このような推奨経路が液晶モニタ５に表示されている状態で、ユーザが公園（第一経由地）とレストラン（第二経由地）との間に新たな経由地として喫茶店を追加すると、経路修正部４１は、第一経由地を公園、第二経由地を喫茶店、第三経由地をレストラン、第四経由地を動物園とする新たな推奨経路を生成する。また、経路修正部４１は、この新たな推奨経路での経由地間の移動時間を計算するとともに、ユーザが入力した発着条件を満たすように各経由地での滞在時間を見直して、新たな推奨経路を生成する。
【０１１２】
図１６は、推奨経路生成部２４が生成した図１５に示す推奨経路に、喫茶店が経由地として追加された場合の、変更された推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。図１６の例では、公園とレストランの間に喫茶店が追加されることで、公園での滞在時間が１.５時間から１時間に短縮され、レストランでの滞在時間が１.５時間から１時間に短縮され、動物園への到着時刻が１４：２０から１４：３０へ変更されている。
【０１１３】
また、図１６に示す推奨経路が液晶モニタ５に表示されている状態で、ユーザが公園（第一経由地）とレストラン（第二経由地）との間から、喫茶店を削除すると、経路修正部４１は、第一経由地を公園、第二経由地をレストラン、第三経由地を動物園とする新たな推奨経路を生成する。この経路は、図１５に例示する推奨経路と同じものとなる。
【０１１４】
また、図１６に示す推奨経路が液晶モニタ５に表示されている状態で、ユーザが第二経由地の喫茶店を滝へ変更すると、経路修正部４１は、第一経由地を公園、第二経由地を滝、第三経由地をレストラン、第四経由地を動物園とする新たな推奨経路を生成する。
【０１１５】
図１７は、図１６に示す推奨経路において喫茶店が滝へ変更された場合の、変更された推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。図１７の例では、喫茶店が滝へ変更されることで、レストランでの滞在時間が１時間から５０分へ短縮され、動物園への到着時刻が１４：３０から１４：４０へ変更されている。
【０１１６】
以上のように、この実施の形態２に係る車載ナビゲーション装置１では、ユーザが指定した発着条件の下で各経由地での滞在時間を最大限に確保した案内経路を生成し、さらにその案内経路を適宜変更することができる。
【０１１７】
したがって、ユーザは、単に車載ナビゲーション装置１が探索した案内経路ではなく、自分でカスタマイズした納得のいく案内経路にて誘導されることになる。
【０１１８】
以上の各実施の形態は、本発明の好適な実施の形態の例であるが、本発明はこれに限定されるものではなく、種々の変形、変更が可能である。
【０１１９】
たとえば、上記各実施の形態において、案内時刻は、その店舗などのジャンルの営業時間の典型値に基づいて設定されるようにしてもよい。また、案内時刻の設定がある場合、案内時刻の後の所定の時間は少なくとも滞在させる拘束条件を設けるようにしてもよい。
【０１２０】
上記各実施の形態では、案内経路を生成する案内経路探索装置は、それが生成した案内経路で誘導を行う車載ナビゲーション装置１に組み込まれている。この他にもたとえば、案内経路探索装置は、車載ナビゲーション装置とは別体のコンピュータ装置などにおいて実現されてもよい。さらにたとえば、その車載ナビゲーション装置と、それとは別体のコンピュータ装置とは、インターネット、無線通信網などのデータ通信網を介してデータ通信可能に接続されていてもよい。さらにたとえば、車載ナビゲーション装置とは別体のコンピュータ装置は、データ通信網を介して、車載ナビゲーション装置において選択された複数の経由地に関する情報を受信し、且つ、生成した案内経路を車載ナビゲーション装置へ送信するように構成されていてもよい。
【０１２１】
上記各実施の形態は、車載ナビゲーション装置１を例とするものである。本発明に係る案内経路探索装置、案内経路の探索方法およびナビゲーション装置は、この他にもたとえば、携帯電話端末、小型ノートコンピュータ装置、ＰＤＡ（Personal Digital Assistants）装置などのポータブル情報装置などに適用することができる。さらに、本発明に係る案内経路探索装置および案内経路の探索方法については、デスクトップコンピュータなどの情報装置などに適用することができる。
【産業上の利用可能性】
【０１２２】
本発明に係る案内経路探索装置、ナビゲーション装置および案内経路の探索方法は、たとえば、自動車などの車両に搭載する車載ナビゲーション装置、歩行者用ナビゲーション装置、その他のナビゲーション装置などに利用することができる。
【符号の説明】
【０１２３】
１  車載ナビゲーション装置（ナビゲーション装置）
２  中央処理装置（経路誘導手段）
５  液晶モニタ（表示手段）
９  ＧＰＳ受信機（現地位置更新手段）
１５  ジャンル別経由地条件テーブル（滞在時刻、滞在時間、滞在条件）
２２  経由地選択部（経由地指定手段）
２４  推奨経路生成部（選択手段、仮決定手段、判定手段、調整手段）
４１  経路修正部（変更手段）
【手続補正書】
【提出日】平成22年6月22日(2010.6.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻非指定経由地とを含む複数の経由地を設定する経由地指定手段と、
前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて、前記案内時刻指定経由地のみを含む案内スケジュールを仮決定する第１の仮決定手段と、
前記第１の仮決定手段で仮決定した案内スケジュールに前記複数の案内時刻指定経由地の滞在時間の重なりがあるか否かを判定する第１の判定手段と、
前記第１の判定手段によって滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整手段と、
前記第１の調整手段で調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻非指定経由地を載せて、前記案内時刻指定経由地及び前記案内時刻非指定経由地を含む案内スケジュールを仮決定する第２の仮決定手段と、
前記第２の仮決定手段で仮決定した案内スケジュールに前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりがあるか否かを判定する第２の判定手段と、
前記第２の判定手段によって滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりを解消するよう滞在時間を調整する第２の調整手段と、
を備えることを特徴とする案内経路探索装置。
【請求項２】
前記案内経路探索装置は複数の案内スケジュールを生成し、
前記複数の案内スケジュールの内の１つを選択する選択手段をさらに備える
ことを特徴とする請求項１記載の案内経路探索装置。
【請求項３】
前記第１及び第２の判定手段は、前記複数の案内時刻指定経由地間、前記案内時刻指定経由地と前記案内時刻非指定経由地との間の移動時間を考慮して滞在時間の重なりがあるか否かを判定し、
前記第１及び第２の調整手段は、移動時間を考慮した滞在時間の重なりを解消するよう滞在時間を調整する
ことを特徴とする請求項１または２に記載の案内経路探索装置。
【請求項４】
ナビゲーション装置に設けられた中央処理装置が、所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻非指定経由地とを含む複数の経由地を設定する経由地指定ステップと、
前記中央処理装置が、前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて、前記案内時刻指定経由地のみを含む案内スケジュールを仮決定する第１の仮決定ステップと、
前記中央処理装置が、前記第１の仮決定ステップにて仮決定した案内スケジュールに前記複数の案内時刻指定経由地の滞在時間の重なりがあるか否かを判定する第１の判定ステップと、
前記中央処理装置が、前記第１の判定ステップにて滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整ステップと、
前記中央処理装置が、前記第１の調整ステップにて調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻非指定経由地を載せて、前記案内時刻指定経由地及び前記案内時刻非指定経由地を含む案内スケジュールを仮決定する第２の仮決定ステップと、
前記中央処理装置が、前記第２の仮決定ステップにて仮決定した案内スケジュールに前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりがあるか否かを判定する第２の判定ステップと、
前記中央処理装置が、前記第２の判定ステップにて滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりを解消するよう滞在時間を調整する第２の調整ステップと、
を含むことを特徴とする案内経路探索方法。
【請求項５】
複数の案内スケジュールを生成し、
前記複数の案内スケジュールの内の１つを選択する選択ステップをさらに含む
ことを特徴とする請求項４記載の案内経路探索方法。
【請求項６】
前記第１及び第２の判定ステップは、前記複数の案内時刻指定経由地間、前記案内時刻指定経由地と前記案内時刻非指定経由地との間の移動時間を考慮して滞在時間の重なりがあるか否かを判定し、
前記第１及び第２の調整ステップは、移動時間を考慮した滞在時間の重なりを解消するよう滞在時間を調整する
ことを特徴とする請求項４または５に記載の案内経路探索方法。
【請求項７】
コンピュータに、
所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻非指定経由地とを含む複数の経由地を設定する経由地指定ステップと、
前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて、前記案内時刻指定経由地のみを含む案内スケジュールを仮決定する第１の仮決定ステップと、
前記第１の仮決定ステップにて仮決定した案内スケジュールに前記複数の案内時刻指定経由地の滞在時間の重なりがあるか否かを判定する第１の判定ステップと、
前記第１の判定ステップにて滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整ステップと、
前記第１の調整ステップにて調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻非指定経由地を載せて、前記案内時刻指定経由地及び前記案内時刻非指定経由地を含む案内スケジュールを仮決定する第２の仮決定ステップと、
前記第２の仮決定ステップにて仮決定した案内スケジュールに前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりがあるか否かを判定する第２の判定ステップと、
前記第２の判定ステップにて滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりを解消するよう滞在時間を調整する第２の調整ステップと、
を実行させることを特徴とする案内経路探索プログラム。
【請求項８】
請求項１〜３のいずれか１項に記載の案内経路探索装置で生成された案内スケジュールを用いて経路を誘導する経路誘導手段を備える
ことを特徴とするナビゲーション装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、案内経路探索装置、案内経路探索方法、案内経路探索プログラム、ナビゲーション装置に関する。
【背景技術】
【０００２】
特許文献１には、複数の経由地を経由する案内経路を探索する経路探索の方法が開示されている。この特許文献１に開示される従来の経路探索の方法では、経路を探索するために設定された探索条件と、特定の経由地同士の依存関係とに基づいて複数の経由地の通過順序を決定し、その通過順序で複数の経由地を通過して目的地に至る経路を探索する。また、この特許文献１は、経路を探索するために設定される探索条件が、時間（所要時間の短さ）と、距離（走行距離の短さ）と、料金（通行料金の低さ）との中から選択される例を開示している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００１−２２１６４７号公報（特許請求の範囲、段落００３３〜００５２など）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、この特許文献１に開示される従来の経路探索の方法を使用して探索された案内経路では、各経由地での滞在時間を考慮したプランを作成することは困難である。
【０００５】
そのため、特許文献１に開示される従来の経路探索の方法を用いて多くの経由地を経由する案内経路を作成し、その案内経路にて誘導される場合には、ユーザは、各経由地で滞在時間を気にしなければならない。そのため、ユーザは、時間に追われるようにして各経由地において早目に出発することになる。また、ユーザは、各経由地において早目に出発する結果として、たとえばホテルなどの目的地に予定した到着時刻より早く到着してしまうこともありえる。
【０００６】
他にもたとえば、特許文献１に開示される従来の経路探索の方法を用いて余裕を見越して経由地を少なめに設定し、その案内経路にて誘導される場合には、ユーザは、各経由地において早目に出発する必要はなくなる。しかしながら、各経由地での適切な出発時刻などが解らないため、各経由地においてゆっくりと過ごしすぎて、経由地を少なめに設定したにもかかわらずホテルなどの目的地に予定よりも遅れて到着してしまうことがありえる。
【０００７】
本発明は、複数の経由地を回る案内スケジュールを、それぞれの経由地での滞在時間を考慮して生成する案内経路探索装置、案内経路探索方法、案内経路探索プログラムを提供することを目的とする。
【０００８】
また、本発明は、複数の経由地での滞在時間を考慮して生成された案内スケジュールにて経路案内を行うナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の案内経路探索装置は、所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻非指定経由地とを含む複数の経由地を設定する経由地指定手段と、前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて、前記案内時刻指定経由地のみを含む案内スケジュールを仮決定する第１の仮決定手段と、前記第１の仮決定手段で仮決定した案内スケジュールに前記複数の案内時刻指定経由地の滞在時間の重なりがあるか否かを判定する第１の判定手段と、前記第１の判定手段によって滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整手段と、前記第１の調整手段で調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻非指定経由地を載せて、前記案内時刻指定経由地及び前記案内時刻非指定経由地を含む案内スケジュールを仮決定する第２の仮決定手段と、前記第２の仮決定手段で仮決定した案内スケジュールに前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりがあるか否かを判定する第２の判定手段と、前記第２の判定手段によって滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりを解消するよう滞在時間を調整する第２の調整手段と、を備えることを特徴とする。
【００１０】
前記案内経路探索装置は複数の案内スケジュールを生成し、前記複数の案内スケジュールの内の１つを選択する選択手段をさらに備えることを特徴とする。
【００１１】
前記第１及び第２の判定手段は、前記複数の案内時刻指定経由地間、前記案内時刻指定経由地と前記案内時刻非指定経由地との間の移動時間を考慮して滞在時間の重なりがあるか否かを判定し、前記第１及び第２の調整手段は、移動時間を考慮した滞在時間の重なりを解消するよう滞在時間を調整することを特徴とする。
【００１２】
本発明の案内経路探索方法は、ナビゲーション装置に設けられた中央処理装置が、所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻非指定経由地とを含む複数の経由地を設定する経由地指定ステップと、前記中央処理装置が、前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて、前記案内時刻指定経由地のみを含む案内スケジュールを仮決定する第１の仮決定ステップと、前記中央処理装置が、前記第１の仮決定ステップにて仮決定した案内スケジュールに前記複数の案内時刻指定経由地の滞在時間の重なりがあるか否かを判定する第１の判定ステップと、前記中央処理装置が、前記第１の判定ステップにて滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整ステップと、前記中央処理装置が、前記第１の調整ステップにて調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻非指定経由地を載せて、前記案内時刻指定経由地及び前記案内時刻非指定経由地を含む案内スケジュールを仮決定する第２の仮決定ステップと、前記中央処理装置が、前記第２の仮決定ステップにて仮決定した案内スケジュールに前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりがあるか否かを判定する第２の判定ステップと、前記中央処理装置が、前記第２の判定ステップにて滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりを解消するよう滞在時間を調整する第２の調整ステップと、を含むことを特徴とする。
【００１３】
複数の案内スケジュールを生成し、前記複数の案内スケジュールの内の１つを選択する選択ステップをさらに含むことを特徴とする複数の推奨経路を生成し、前記複数の推奨経路の内の１つを選択する選択ステップをさらに含むことを特徴とする。
【００１４】
前記第１及び第２の判定ステップは、前記複数の案内時刻指定経由地間、前記案内時刻指定経由地と前記案内時刻非指定経由地との間の移動時間を考慮して滞在時間の重なりがあるか否かを判定し、前記第１及び第２の調整ステップは、移動時間を考慮した滞在時間の重なりを解消するよう滞在時間を調整することを特徴とする。
【００１５】
本発明の案内経路探索プログラムは、コンピュータに、所定の出発時刻に出発する出発地から所定の到達時刻に到達する目的地までの経路の途中で経由すべき、案内時刻と滞在時間とが指定された複数の案内時刻指定経由地と、案内時刻が指定されず滞在時間が指定された案内時刻非指定経由地とを含む複数の経由地を設定する経由地指定ステップと、前記複数の経由地の内の前記案内時刻指定経由地のみを、前記案内時刻及び前記滞在時間に基づいて前記出発時刻から前記到達時刻までの時間帯内に載せて、前記案内時刻指定経由地のみを含む案内スケジュールを仮決定する第１の仮決定ステップと、前記第１の仮決定ステップにて仮決定した案内スケジュールに前記複数の案内時刻指定経由地の滞在時間の重なりがあるか否かを判定する第１の判定ステップと、前記第１の判定ステップにて滞在時間の重なりがあると判定された場合、前記複数の案内時刻指定経由地の滞在時間の重なりを解消するよう滞在時間を調整する第１の調整ステップと、前記第１の調整ステップにて調整した前記複数の案内時刻指定経由地を載せた前記出発時刻から前記到達時刻までの時間帯内に、前記複数の経由地の内の前記案内時刻非指定経由地を載せて、前記案内時刻指定経由地及び前記案内時刻非指定経由地を含む案内スケジュールを仮決定する第２の仮決定ステップと、前記第２の仮決定ステップにて仮決定した案内スケジュールに前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりがあるか否かを判定する第２の判定ステップと、前記第２の判定ステップにて滞在時間の重なりがあると判定された場合、前記案内時刻指定経由地と前記案内時刻非指定経由地との滞在時間の重なりを解消するよう滞在時間を調整する第２の調整ステップと、を実行させることを特徴とする。
【００１６】
本発明のナビゲーション装置は、上記の案内経路探索装置で生成された案内スケジュールを用いて経路を誘導する経路誘導手段を備えることを特徴とする。
【発明の効果】
【００１７】
本発明では、複数の経由地を回る案内スケジュールを、それぞれの経由地での滞在時間を考慮して生成することができる。
【００１８】
また、本発明では、複数の経由地での滞在時間を考慮して生成された案内スケジュールにて経路案内を行うことができる。
【図面の簡単な説明】
【００１９】
【図１】図１は、本発明の実施の形態１に係る車載ナビゲーション装置のハードウェア構成を示すブロック図である。
【図２】図２は、図１中のハードディスクドライブの記憶内容の説明図である。
【図３】図３は、図２中の経由候補地探索データの一例を示す説明図である。
【図４】図４は、図２中のジャンル別経由地条件テーブルの一例を示す説明図である。
【図５】図５は、図１の車載ナビゲーション装置に実現される案内経路生成のための機能ブロックを示すブロック図である。
【図６】図６は、図５中の推奨経路生成部が実行する探索処理の流れを示すフローチャートである。
【図７】図７は、本発明の実施の形態１における複数の経由地の組み合わせ例を示す図である。
【図８】図８は、本発明の実施の形態１においてユーザが入力した発着条件に基づく時間軸を示す図である。
【図９】図９は、図７に示す複数の経由地の中の案内時刻が指定されている経由地Ａおよび経由地Ｂを発着条件に基づく時間軸上に載せた状態を示す図である。
【図１０】図１０は、図７に示すすべての経由地を、発着条件に基づく時間軸に載せた状態を示す図である。
【図１１】図１１は、図１０に示す状態の後に、すべての経由地の滞在時間を減らした状態を示す図である。
【図１２】図１２は、図１１に示す状態の後に、滞在時間同士が重なったままになっている経由地および経由地の滞在時間を減らした状態を示す図である。
【図１３】図１３は、実施の形態１における案内スケジュールの計算の一例を示す図である。
【図１４】図１４は、本発明の実施の形態２に係る車載ナビゲーション装置に実現される案内経路生成のための機能ブロックを示すブロック図である。
【図１５】図１５は、推奨経路生成部が生成した推奨経路を表示する表示画面の一例を示す画面説明図である。
【図１６】図１６は、推奨経路生成部が生成した図１５に示す推奨経路に喫茶店が経由地として追加された場合の、変更された推奨経路を表示する表示画面の一例を示す画面説明図である。
【図１７】図１７は、図１６に示す推奨経路において喫茶店が滝に変更された場合の、変更された推奨経路を表示する表示画面の一例を示す画面説明図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態に係る案内経路探索装置、案内経路探索方法、案内経路探索プログラム、ナビゲーション装置を、図面に基づいて説明する。ナビゲーション装置は、自動車、自動二輪、航空機などの車両に搭載する車載ナビゲーション装置を例として説明する。案内経路探索装置は、この車載ナビゲーション装置の構成の一部として説明する。案内経路の探索方法は、この車載ナビゲーション装置の動作の一部として説明する。
【００２１】
実施の形態１．
図１は、本発明の実施の形態１に係る車載ナビゲーション装置１のハードウェア構成を示すブロック図である。
【００２２】
車載ナビゲーション装置１は、プログラムを実行する中央処理装置（ＣＰＵ：Central Processing Unit）２と、実行中のプログラムやデータを記憶するＲＡＭ（Random Access Memory）３と、プログラムなどを記憶するハードディスクドライブ４と、表示データを表示する液晶モニタ５と、周辺機器が接続されるＩ／Ｏ（Input/Output）ポート６と、これらを接続するシステムバス７と、を有する。
【００２３】
Ｉ／Ｏポート６には、液晶モニタ５の表示画面に重ねて配設され、押圧された部位を示す信号を出力するタッチパネル８と、ＧＰＳ（Global Positioning System）衛星からの電波を受信して現在の緯度経度の値を出力する現地位置更新手段としてのＧＰＳ受信機９と、ＦＭ波、光ビーコンあるいは電波ビーコンを受信してそれに含まれるＶＩＣＳ（Vehicle Information and Communication System）情報を出力するＶＩＣＳ受信機１０とが接続される。ＶＩＣＳ情報には、交通規制情報や渋滞情報などが含まれる。
【００２４】
なお、液晶モニタ５は、Ｉ／Ｏポート６を介してシステムバス７に接続されていてもよい。また、Ｉ／Ｏポート６には、車両の速度に応じたパルスを出力する車速パルス発生器や、車両の移動方向を示すジャイロセンサなどが接続されていてもよい。
【００２５】
図２は、図１中のハードディスクドライブ４の記憶内容の説明図である。
【００２６】
ハードディスクドライブ４には、プログラム群と、データ群とが記憶される。ハードディスクドライブ４のプログラム群には、案内経路生成プログラム１１と、経路誘導プログラム１２とが含まれる。ハードディスクドライブ４のデータ群には、経由候補地探索データ１３と、経由候補地登録データ１４と、ジャンル別経由地条件テーブル１５と、経路探索データ１６と、経路探索条件データ１７と、地図データ１８とが含まれる。
【００２７】
なお、経由候補地探索データ１３、ジャンル別経由地条件テーブル１５、経路探索データ１６、地図データ１８などは、車載ナビゲーション装置１に挿抜可能なコンピュータ読取可能な記録媒体に記録され、車載ナビゲーション装置１はこの記録媒体からこれらのデータを読み込むようにしてもよい。また、プログラム群とデータ群は、別々の記録媒体に記録されるようにしてもよい。
【００２８】
経由候補地探索データ１３は、経由候補地毎のレコードを有する。経由候補地探索データ１３の経由候補地は、車載ナビゲーション装置１の出荷前などにおいて事前に登録されているものであり、たとえばレストラン、遊戯施設などが含まれる。
【００２９】
図３は、図２中の経由候補地探索データ１３の一例を示す説明図である。図３では、１行毎に各レコードの登録情報が示される。各経由候補地のレコードには、経由候補地の名称、ジャンル、休業日、営業時間などの経由候補地の属性情報、経由候補地の地点を示す値などが含まれる。たとえば、「○○デパート」という名称の宿泊施設には、ジャンルとして「デパート」が対応付けられ、休業日として「水」曜日が対応付けられ、営業時間として「１０：００〜２０：００」が対応付けられ、地点を示す値として「１２２４」が対応付けられる。
【００３０】
なお、経由候補地探索データ１３に登録される経由候補地の地点を示す値は、その経由候補地の緯度経度に基づく値であってもよいが、その緯度経度に基づく値と対応付けられている別の値、たとえばマップコード（登録商標）の値などであってもよい。また、経由候補地そのものの緯度経度に基づく値であってもよいが、たとえばその経由候補地と提携している駐車場などの経由候補地に関連する地点の緯度経度に基づく値であってもよい。
【００３１】
経由候補地登録データ１４は、ユーザにより登録された経由候補地毎の複数のレコードを有する。各経由候補地のレコードには、たとえば経由候補地の名称、ジャンル、休業日、営業時間などの登録された経由候補地の属性情報、登録された経由候補地の地点を示す値などが含まれる。
【００３２】
ジャンル別経由地条件テーブル１５は、ジャンル毎の複数のレコードを有する。ジャンルは、各経由候補地の属性情報の中の１つの情報である。ジャンルには、たとえばレストラン、名所、ホテルなどがある。
【００３３】
図４は、図２中のジャンル別経由地条件テーブル１５の一例を示す説明図である。図４では、１行毎に各レコードの登録情報が示される。各ジャンルのレコードには、ジャンルの名称、案内時刻、滞在可能時間などのジャンルの属性情報が含まれる。たとえば、ジャンル「レストラン」には、案内時刻として「１３：００」が対応付けられ、滞在可能時間として「２時間」が対応付けられる。このジャンル毎の案内時刻および滞在可能時間が、この実施の形態１の各経由地について滞在条件となる。
【００３４】
経路探索データ１６は、複数のノード情報と、複数のリンク情報を有する。ノード情報は、交差点などの地点に関する情報であり、その地点の識別情報、その地点を示す値、そのノードに接続されているリンクの識別番号のリストなどで構成される。リンク情報は、ノード間を接続する道路などの経路に関する情報であり、その経路の識別情報、接続されるノードの識別番号のリストなどで構成される。
【００３５】
経路探索条件データ１７は、推奨経路を探索する際の探索条件を示すデータであり、たとえば最短距離、最短移動時間、一般道路優先、有料道路優先などの、複数の経路の中から１つを選択するための選択基準を示すデータである。なお、選択基準は、１つの基準項目のものに限定されるものではなく、複数の基準項目が組み合わされたものであってもよい。
【００３６】
地図データ１８は、たとえば日本全国、関東地方、東京都などの所定の地域の地図を、複数のドットからなる画像データにデータ化したものである。各ドットは輝度情報を有する。地図には、道路地図、住宅地図などがある。また、地図データ１８は、地図データ１８の各ドットの地点を示す値を有する。
【００３７】
次に、以上のような構成を有する実施の形態１に係る車載ナビゲーション装置１の動作を説明する。
【００３８】
車載ナビゲーション装置１が起動されると、中央処理装置２は、ハードディスクドライブ４に記憶されているプログラムをＲＡＭ３に読み込んで実行する。
【００３９】
中央処理装置２が案内経路生成プログラム１１を実行すると、車載ナビゲーション装置１には、案内経路を生成するための各種の機能ブロックが実現される。図５は、図１の車載ナビゲーション装置１に実現される案内経路生成のための機能ブロックを示すブロック図である。中央処理装置２が案内経路生成プログラム１１を実行することで、車載ナビゲーション装置１には、経由候補地登録部２１と、経由地選択部２２と、発着条件設定部２３と、推奨経路生成部２４と、推奨経路保存部２５とが実現される。
【００４０】
経由候補地登録部２１は、経由候補地を登録、修正あるいは削除するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、経由候補地を登録、修正あるいは削除するための画面が表示される。そして、ユーザの操作に応じてタッチパネル８が生成する情報に基づいて、経由候補地登録部２１は、新たな経由候補地を経由候補地登録データ１４に登録したり、経由候補地登録データ１４に登録されている経由候補地の情報を変更したり、登録されている経由候補地を経由候補地登録データ１４から削除したりする。
【００４１】
具体的にはたとえば、登録する経由候補地の名称、ジャンル、休業日、営業時間などの属性情報や、経由候補地の地点を示す画像が液晶モニタ５に表示され、ユーザの操作に応じてタッチパネル８から出力される画像上の操作位置情報に基づいて、経由候補地登録部２１は、経由候補地の属性情報などを特定し、経由候補地登録データ１４に新たなレコードを追加し、この追加したレコードにそれらの情報を格納する。なお、経由候補地登録データ１４に登録される経由候補地の地点を示す値は、ユーザが直接その値を入力するようにしてもよいが、他にもたとえば、地図データ１８をスクロール可能に液晶モニタ５に表示し、タッチパネル８から出力される操作情報に基づいてユーザが選択した地点を特定し、この特定した地点の地点を示す値で代用するようにしてもよい。
【００４２】
経由地選択部２２は、経由地指定手段として機能し、経由候補地探索データ１３に予め登録されている経由候補地と経由候補地登録データ１４にユーザが登録した経由候補地との中から、経由候補地を選択するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、経由候補地を選択するための画面が表示される。
【００４３】
そして、ユーザは、この液晶モニタ５の画面に応じてタッチパネル８を操作して所望の経由候補地を液晶モニタ５に表示させ、その所望の経由候補地を選択する。ユーザにより経由候補地が選択されると、経由地選択部２２は、その経由候補地を経由地としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【００４４】
なお、経由候補地は、複数選択することができる。複数の経由候補地が選択された場合には、ＲＡＭ３あるいはハードディスクドライブ４には、その選択された複数の経由候補地が複数の経由地として記憶されることになる。
【００４５】
経由地選択部２２での経由地の選択が完了すると、発着条件設定部２３は、出発地の地点および出発時刻、並びに、目的地の地点および到達時刻を入力するための表示データを液晶モニタ５へ出力する。これにより、液晶モニタ５には、これらを入力するための画面が表示される。そして、ユーザは、この液晶モニタ５の画面に応じてタッチパネル８を操作して、出発地の地点、出発時刻、目的地の地点および到達時刻を入力する。
【００４６】
なお、この出発地の地点、出発時刻、目的地の地点および到達時刻が、この実施の形態１に係る発着条件となる。また、出発地の出発時刻から目的地への到達時刻が、複数の経由地を回る旅行の出発時刻から到着時刻までの旅行時間帯となる。
【００４７】
なお、出発地の地点を示す値および目的地の地点を示す値は、ユーザが直接その値を入力するようにしてもよいが、他にもたとえば、地図データ１８をスクロール可能に液晶モニタ５に表示し、タッチパネル８から出力される操作情報に基づいてユーザが選択した地点を特定し、この特定した地点の地点を示す値で代用するようにしてもよい。
【００４８】
このように発着条件が指定されると、発着条件設定部２３は、出発地の地点、出発時刻、目的地の地点および到達時刻を、発着条件としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【００４９】
発着条件設定部２３での発着条件の入力が完了すると、推奨経路生成部２４は、ユーザにより選択された経由地を経由して、ユーザが入力した出発地から目的地に至る推奨経路の探索処理を開始する。図６は、図５中の推奨経路生成部２４が実行する探索処理の流れを示すフローチャートである。
【００５０】
推奨経路生成部２４は、まず、仮決定手段として機能して、ユーザにより選択された経由地の中から、案内時刻が指定されている経由地（以下、案内時刻指定経由地と記載する。）を抽出し、時間軸上においてその案内時刻指定経由地の滞在時間帯を、出発地の出発時刻から目的地への到着時刻までの旅行時間帯上に載せる。このとき、各案内時刻指定経由地の滞在時間は、滞在可能時間とする。これにより、案内時刻指定経由地の滞在時間帯が仮に決定される（ステップＳ１）。なお、滞在時間帯とは、滞在開始時刻から滞在終了時刻までの期間のことをいう。
【００５１】
次に、推奨経路生成部２４は、判定手段として機能して、複数の案内時刻指定経由地の滞在時間帯同士が重なるか否かを判定する（ステップＳ２）。
【００５２】
複数の案内時刻指定経由地の滞在時間帯同士が重なる場合には、推奨経路生成部２４は、調整手段として機能して、案内時刻指定経由地の滞在時間を所定の割合あるいは所定の時間だけ減らす（ステップＳ３）。
【００５３】
続けて、推奨経路生成部２４は、滞在時間帯の重なりが解消されるか否かの判定を行う。滞在時間帯の重なりが解消されるか否かの判定は、たとえば削減処理の回数が所定の回数を超えたか否かに基づいて判定しても、十分な滞在時間を確保できなくなっているか否かに基づいて判定してもよい（ステップＳ４）。
【００５４】
ステップＳ４において滞在時間帯の重なりが解消されないと判定した場合には、推奨経路生成部２４は、現状では立ち寄れない案内時刻指定経由地があることをユーザに警告を行う。この警告は、たとえば液晶モニタ５に表示すればよい（ステップＳ５）。
【００５５】
ステップＳ２の判断において、複数の案内時刻指定経由地の滞在時間同士が重ならない場合には、推奨経路生成部２４は、仮決定手段として機能して、残りの経由地、すなわち案内時刻が指定されていない経由地（以下、案内時刻非指定経由地と記載する。）の滞在時間帯を、旅行時間帯上に載せる。このとき、各案内時刻非指定経由地の滞在時間は、滞在可能時間とする。これにより、案内時刻非指定経由地を含めたすべての経由地の滞在時間帯が仮に決定される。
【００５６】
また、推奨経路生成部２４は、経由地間の移動時間（つまり、移動の時間帯）を、旅行時間帯上に載せる。この経由地間の移動時間は、固定的な移動時間であっても、単に経由地間の距離のみに応じた移動時間であっても、経路探索データ１６および経路探索条件データ１７に基づいて探索した実際の案内経路での移動時間であってもよい（ステップＳ６）。
【００５７】
そして、推奨経路生成部２４は、判定手段として機能して、複数の経由地の滞在時間帯同士が重なるか否かを判定する（ステップＳ７）。
【００５８】
複数の経由地の滞在時間帯同士が重なる場合には、推奨経路生成部２４は、調整手段として機能して、すべての経由地の滞在時間を所定の割合あるいは所定の時間だけ減らしたり、重なっている経由地の滞在時間のみを所定の割合あるいは所定の時間だけ減らしたりする（ステップＳ８）。
【００５９】
なお、推奨経路生成部２４は、ステップＳ７において、複数の経由地の滞在時間帯同士が重なるか否かに替えて、複数の経由地を回ることができるか否かを判断し、回ることができないと判断した場合にステップＳ８へ進むようにしてもよい。
【００６０】
その後、推奨経路生成部２４は、滞在時間帯の重なりが解消されるか否かの判定を行う。滞在時間帯の重なりが解消されるか否かの判定は、たとえば削減処理の回数が所定の回数を超えたか否かに基づいて判定しても、十分な滞在時間を確保できなくなっているか否かに基づいて判定してもよい（ステップＳ９）。
【００６１】
そして、ステップＳ９において滞在時間帯の重なりが解消されないと判定した場合には、推奨経路生成部２４は、現状では立ち寄れない経由地があることをユーザに警告を行う。この警告は、たとえば液晶モニタ５に表示すればよい（ステップＳ１０）。
【００６２】
ステップＳ７の判断において、すべての経由地の滞在時間帯が重ならないと判断した場合には、推奨経路生成部２４は、完成した推奨経路と各経由地での滞在時間帯を含めた案内スケジュールを生成する。推奨経路保存部２５は、この推奨経路を含む案内スケジュールを、その推奨経路での経由地間の実際の案内経路とともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【００６３】
このように、推奨経路生成部２４は、事前に設定された目的地への到達時刻までに複数の経由地を経由し、かつ、経由地に対して事前に設定された最大滞在時間以内で複数の経由地での滞在時間が最大となる案内スケジュールを選択する選択手段として機能する。
【００６４】
なお、推奨経路の生成処理において経由地間の実際の案内経路の探索処理が完了していない場合には、推奨経路保存部２５は、経路探索データ１６および経路探索条件データ１７に基づいて、経由地間の実際の案内経路を探索する。また、経路探索データ１６および経路探索条件データ１７などともに、ＶＩＣＳ受信機１０が受信した交通情報を利用してもよい。
【００６５】
ところで、少なくとも１つの案内時刻非指定経由地を含む複数の経由地がユーザにより指定された場合、それら複数の経由地の経由順が互いに異なる複数の経由パターンが考えられる。そのような場合には、推奨経路生成部２４は、たとえば、ステップＳ６においてそのすべての組み合わせの経由順の経由パターンについて案内スケジュールを生成し、ステップＳ７において複数の経由地の滞在時間同士の重なり時間が最も小さいものを１つ選択したり、最も経由地間の総移動時間あるいは出発時刻から到着時刻までの総旅行距離が短いものを１つ選択したり、ユーザに１つを選択させたりすればよい。
【００６６】
複数の経由パターンが考えられる場合の他の処理としては、たとえば、推奨経路生成部２４は、ステップＳ６においてはいずれか１つの経由順の経由パターンについての案内スケジュールを生成し、ステップＳ７〜Ｓ９の処理を所定回繰り返した後のステップＳ９の判断において複数の経由地の滞在時間帯同士が重なったままであると判断した場合には、他の経由順の経由パターンについての仮の案内スケジュールを生成し、その別の仮の案内スケジュールについてステップＳ７〜Ｓ９の処理を繰り返すようにしてもよい。この処理の場合、推奨経路生成部２４は、経由地のすべての組み合わせについての仮案内スケジュールにおいて複数の経由地の滞在時間帯同士が重なったままであると判断したら、ステップＳ１０の警告を行えばよい。なお、ステップＳ６において１つの経由順の経由パターンを選択する場合、たとえば出発地を出発してから複数の経由地を経由して目的地までに移動する総移動時間、総旅行距離などが短いものから順番に選択するようにすればよい。
【００６７】
図７から図１２は、以上の推奨経路生成部２４による推奨経路の探索処理の一例を説明するための図である。
【００６８】
図７は、本発明の実施の形態１における複数の経由地の組み合わせ例を示す図である。図７には、ユーザにより選択された４つの経由地Ａ３１，経由地Ｂ３２，経由地Ｃ３３，経由地Ｄ３４が示される。経由地Ａ３１の案内時刻は、１３：００であり、経由地Ａ３１の滞在可能時間は、２時間である。経由地Ｂ３２の案内時刻は、１５：００であり、経由地Ｂ３２の滞在可能時間は、２時間である。経由地Ｃ３３の案内時刻は、ジャンル別経由地条件テーブル１５において未定義であり、経由地Ｃ３３の滞在可能時間は、３時間である。経由地Ｄ３４の案内時刻は、ジャンル別経由地条件テーブル１５において未定義であり、経由地Ｄ３４の滞在可能時間は、４時間である。したがって、経由地Ａ３１と経由地Ｂ３２は、案内時刻指定経由地である。経由地Ｃ３３と経由地Ｄ３４は、案内時刻非指定経由地である。
【００６９】
図８は、本発明の実施の形態１においてユーザが入力した発着条件に基づく旅行時間帯３５を示す図である。出発地は自宅であり、出発時刻は９：００である。目的地はホテルであり、到着時刻は１７：００である。
【００７０】
このような４つの経由地Ａ，Ｂ，Ｃ，Ｄおよび発着条件がユーザにより入力されると、推奨経路生成部２４は、案内時刻指定経由地である経由地Ａ３１および経由地Ｂ３２を、９：００から１７：００までの旅行時間帯３５上に載せる（図６のステップＳ１）。図９は、図７に示す複数の経由地の中の案内時刻が指定されている経由地Ａ３１および経由地Ｂ３２の滞在時間帯を発着条件に基づく旅行時間帯３５上に載せた状態を示す図である。この場合、経由地Ａ３１には１２：００から１４：００まで滞在し、且つ、経由地Ｂ３２には１４：００から１６：００まで滞在することになるので、推奨経路生成部２４は、２つの案内時刻指定経由地の滞在時間帯同士は重ならないと判断する（図６のステップＳ２）。
【００７１】
ステップＳ２の判断において、２つの案内時刻指定経由地の滞在時間帯同士が重ならないので、推奨経路生成部２４は、残りの２つ経由地、すなわち経由地Ｃ３３および経由地Ｄ３４の滞在時間帯を、旅行時間帯３５上に載せる（図６のステップＳ６）。
【００７２】
図１０は、図７に示すすべての経由地３１，３２，３３，３４を、発着条件に基づく旅行時間帯３５に載せた状態を示す図である。なお、図１０は、経由地間の移動時間を考慮した図とはなっていない。図１０の場合、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とが重なっている。また、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重なっている。
【００７３】
図１０の状態である場合には、図６のステップＳ７において複数の経由地の滞在時間帯同士が重なっていると判断されるので、推奨経路生成部２４は、まず、すべての経由地３１，３２，３３，３４の滞在時間帯を所定の一定割合で減らす処理を行う（図６のステップＳ８）。
【００７４】
図１１は、図１０に示す状態の後に、すべての経由地３１，３２，３３，３４の滞在時間を減らした状態を示す図である。図１１では、４つの経由地３１，３２，３３，３４の滞在時間を４分の３に減らしている。ただし、減少後の滞在時間は、０．５時間未満の端数を切り捨てた値（０．５の整数倍）とされる。図１１の場合、この処理によって、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とは、重ならなくなる。ただし、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とは重なったままである。
【００７５】
その後、推奨経路生成部２４は、図６のステップＳ７において、再度、複数の経由地の滞在時間帯同士が重なっているか否かの判定を行う。そして、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重なったままであるので、推奨経路生成部２４は、再び、経由地の滞在時間を減らす処理を行う（図６のステップＳ８）。
【００７６】
この場合、前回の滞在時間の減算処理によって、経由地Ｄ３４の滞在時間帯と経由地Ａ３１の滞在時間帯とが重ならなくなっているので、推奨経路生成部２４は、経由地Ｂ３２の滞在時間および経由地Ｃ３３の滞在時間のみを減らす。
【００７７】
図１２は、図１１に示す状態の後に、経由地Ｂ３２および経由地Ｃ３３の滞在時間を減らした状態を示す図である。図１２では、経由地Ｂ３２の滞在時間および経由地Ｃ３３の滞在時間を減らしている。図１２の場合、この処理によって、経由地Ｂ３２の滞在時間帯と経由地Ｃ３３の滞在時間帯とが重ならなくなる。
【００７８】
そして、推奨経路生成部２４は、すべての経由地３１，３２，３３，３４の滞在時間同士が重なっていないので、再度、ステップＳ９およびステップＳ７の判断を繰り返し、生成した経路を推奨経路とする。
【００７９】
なお、上述の説明では、出発地、経由地および目的地のうちの２地点間の移動時間帯を考慮していないが、地点間の移動時間帯については、上述の案内時間非指定経由地の滞在時間帯と同様にして旅行時間帯に載せるようにすればよい。ただし、経由地の滞在時間を短縮する場合には、地点間の移動時間は、予め計算などで得られたものであり、短縮できないので、経由地の滞在時間のみが短縮される。
【００８０】
たとえば、経由地Ａの案内時刻が１３：００であり、経由地Ａの滞在可能時間が２時間であり、経由地Ｂの案内時刻が１５：００であり、経由地Ｂの滞在可能時間が２時間であり、経由地Ｃの滞在可能時間が１．５時間であり、経由地Ｄの滞在可能時間が１時間である場合において、経路パターンが経由地Ｄ−経由地Ａ−経由地Ｂ−経由地Ｃであり、かつ、出発地−経由地Ｄ間の移動時間が１時間であり、経由地Ｄ−経由地Ａ間の移動時間が１．５時間であり、経由地Ａ−経由地Ｂ間の移動時間が１時間であり、経由地Ｂ−経由地Ｃ間の移動時間が０．５時間であり、経由地Ｃ−目的地間の移動時間が０．５時間であるときについて説明する。図１３は、実施の形態１における案内スケジュールの計算の一例を示す図である。
【００８１】
まず、図１３（Ａ）に示すように、推奨経路生成部２４は、案内時刻を中心とした滞在時間分の長さで定められる案内時刻指定経由地の経由地Ａ，Ｂの滞在時間帯を、仮に旅行時間帯に載せる。推奨経路生成部２４は、これらの滞在時間帯は重ならないと判断し、経由地Ａ，Ｂの滞在時間を短縮する処理をせずに次の処理に進む。
【００８２】
次に、推奨経路生成部２４は、図１３（Ｂ）に示すように、案内時刻非指定経由地の経由地Ｃ，Ｄの滞在時間帯および各地点間の移動についての移動時間帯を、仮に旅行時間帯に載せる。なお、以下、出発地−経由地Ｄ間の移動をＭ１とし、経由地Ｄ−経由地Ａ間の移動をＭ２とし、経由地Ａ−経由地Ｂ間の移動をＭ３とし、経由地Ｂ−経由地Ｃ間の移動をＭ４とし、経由地Ｃ−目的地間の移動をＭ５とする。
【００８３】
ここで、推奨経路生成部２４は、連続する移動時間帯および案内時刻非指定経由地の滞在時間帯を１つの時間帯にして、仮に旅行時間帯に載せる。この例では、Ｍ１とＤとＭ２の時間帯を１つの時間帯Ｎ１とし、Ｍ４とＣとＭ５の時間帯を１つの時間帯Ｎ２とする。
【００８４】
推奨経路生成部２４は、出発時刻（＝９時）と時間帯Ｎ１の長さ３．５時間とに基づき、時間帯Ｎ１と経由地Ａの滞在時間帯ＮＡとが重なると判断し、また、滞在時間帯ＮＡの終了時刻と滞在時間帯ＮＢの開始時刻とに基づき、滞在時間帯ＮＡとＭ３の移動時間帯とが重なり、また、経由地Ｂの時間帯ＮＢとＭ３の移動時間帯とが重なると判断し、滞在時間帯ＮＢの終了時刻と目的地への到達時刻（＝１７時）とに基づき、滞在時間帯ＮＢと時間帯Ｎ２が重なると判断する。
【００８５】
そこで、推奨経路生成部２４は、経由地Ａ，Ｂ，Ｃ，Ｄでの滞在時間を４分の３に短縮する（ただし、０．５時間未満は切り捨てとし、短縮後の滞在時間は０．５時間の整数倍とする）。これにより、経由地Ａの滞在時間は１．５時間とされ、経由地Ｂの滞在時間は１．５時間とされ、経由地Ｃの滞在時間は１時間とされ、経由地Ｄの滞在時間は１時間とされる。
【００８６】
推奨経路生成部２４は、図１３（Ｃ）に示すように、経由地Ａの滞在時間帯ＮＡに案内時刻１３：００が含まれる範囲内で経由地Ａの滞在時間帯ＮＡをスライドし、経由地Ｂの滞在時間帯ＮＢに案内時刻１５：００が含まれる範囲内で経由地Ｂの滞在時間帯ＮＢをスライドする。これにより、時間帯Ｎ１と滞在時間帯ＮＡとが重ならなくなり、滞在時間帯ＮＡとＭ３の移動時間帯とが重ならなくなり、経由地Ｂの時間帯ＮＢとＭ３の移動時間帯とが重ならなくなる。
【００８７】
しかしながら、この状態でも、滞在時間帯ＮＢの終了時刻と目的地への到達時刻と時間帯Ｎ２の長さとに基づき、滞在時間帯ＮＢと時間帯Ｎ２が重なると判断される。このため、推奨経路生成部２４は、図１３（Ｄ）に示すように、関連する経由地Ｂ，Ｃでの滞在時間を４分の３に短縮する（ただし、０．５時間未満は切り捨てとし、短縮後の滞在時間は０．５時間の整数倍とする）。これにより、経由地Ｂの滞在時間は１時間とされ、経由地Ｃの滞在時間は０．５時間とされ、滞在時間帯ＮＢと時間帯Ｎ２が重ならなくなる。
【００８８】
このようにして、推奨経路生成部２４は、地点間の移動時間帯を含めて、経由地での滞在時間帯を決定し、推奨経路保存部２５は、これらの経由地に関する経路パターンおよび各時間帯を含む案内スケジュールをその経路パターンでの経由地間の案内経路データとともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【００８９】
以上の処理により、案内経路が生成される。中央処理装置２が経路誘導プログラム１２を実行すると、車載ナビゲーション装置１には、経路誘導部が実現される。
【００９０】
経路誘導部は、ＧＰＳ受信機９から出力される現在の緯度経度の値を周期的に読み取る。そして、経路誘導部は、読み取った現在の緯度経度の値に基づいて、現在位置を含む所定のエリアの画像データを地図データ１８から読み込み、この所定のエリアの画像データに現在位置のマークを重ねた画像データを液晶モニタ５へ出力する。液晶モニタ５には、現在位置のマークとその周辺の地図とが表示される。
【００９１】
また、経路誘導部は、その表示エリア内となる案内経路が存在する場合には、その表示エリア内の部位を画像データに重ねる。これにより、液晶モニタ５には現在位置とともに案内経路が表示され、ユーザは、地図上で現在位置および案内経路を把握することができる。
【００９２】
車両が移動すると、その移動に応じてＧＰＳ受信機９から出力される現在の緯度経度の値も変化する。経路誘導部は、現在位置のマークが液晶モニタ５に表示されつづけるように、上述の案内スケジュールおよび推奨経路のデータに基づいて、地図データ１８から読み込むエリアを切り替える。また、経路誘導部は、この切り替えたエリア内の案内経路を液晶モニタ５に表示させる。
【００９３】
したがって、ユーザは、現在位置のマークが案内経路上を移動するように車両を移動させることで、出発地から各経由地を経由して目的地まで到達する。なお、上述の例では、ユーザは、出発地の自宅から経由地Ｄ、経由地Ａ、経由地Ｂおよび経由地Ｃをその順番に経由して目的地のホテルまで移動することができる。
【００９４】
以上のように、この実施の形態１に係る車載ナビゲーション装置１では、ユーザが指定した発着条件の下で各経由地での滞在時間を最大限に確保した案内経路を生成し、この案内経路でユーザを誘導することができる。したがって、ユーザは、各経由地にできる限り長く滞在することができ、経由地での観光や食事などを満喫して一日を過ごすことができる。
【００９５】
なお、この実施の形態１では、ジャンル別経由地条件テーブル１５では、各経由地での滞在可能時間が各経由地での最長の滞在時間として設定され、推奨経路生成部２４は、複数の経由地での滞在時間帯や経由地間の移動時間帯が重なったら経由地の滞在時間を減らしている。この他にもたとえば、ジャンル別経由地条件テーブル１５に各経由地での最短の滞在時間を別途設定し、推奨経路生成部２４は、各経由地での滞在時間がこの最短の滞在時間を下回らないように経由地の滞在時間を減らすようにしてもよい。これにより、各経由地での滞在時間が極端に短くなってしまうことを防止することができる。
【００９６】
さらに他にもたとえば、ジャンル別経由地条件テーブル１５に各経由地での最短の滞在時間のみを設定し、推奨経路生成部２４は、複数の経由地を経由しても余る空き時間を、少なくとも１つの経由地の滞在時間に加算するようにしてもよい。これにより、多くの経由地を回る案内経路を簡単な処理にて生成することができる。
【００９７】
さらに他にもたとえば、ジャンル別経由地条件テーブル１５などに経由地の滞在時間を固定要否するフラグを設定し、推奨経路生成部２４は、固定不要のフラグがついている経由地の滞在時間のみを調整するようにしてもよい。
【００９８】
この実施の形態１では、ジャンル別経由地条件テーブル１５において各経由地について１つの案内時刻が設定されている。この他にもたとえば、ジャンル別経由地条件テーブル１５などにおいて各経由地について複数の案内時刻を設定できるようにしてもよい。これにより、案内時刻が指定されている経由地の案内時刻に自由度を持たせることができる。
【００９９】
この実施の形態１では、推奨経路生成部２４は、各経由地を仮に旅行時間帯に載せる場合に、案内時刻が滞在可能時間の真中の時刻となるようにしている。この他にもたとえば、推奨経路生成部２４は、案内時刻から滞在が開始されるように、案内時刻が滞在可能時間の滞在開始時刻となるようにしてもよい。また、ジャンル別経由地条件テーブル１５などにおいて案内時刻の替わりに各経由地の出発時刻を設定し、推奨経路生成部２４は、この出発時刻に経由地から出発するように、出発時刻が滞在可能時間の滞在終了時刻となるようにしてもよい。
【０１００】
この実施の形態１では、案内時刻および滞在可能時間は、ジャンル別経由地条件テーブル１５においてジャンル毎に１組ずつ設定されている。この他にもたとえば、案内時刻および滞在可能時間は、運転手毎に１組ずつ設定されていても、乗員構成毎に１組ずつ設定されていても、季節毎に１組ずつ設定されていても、年齢毎に１組ずつ設定されていてもよい。また、それらの組み合わせ毎に１組ずつ設定されていてもよい。また、ジャンル別経由地条件テーブル１５の案内時刻および滞在可能時間を、ユーザが更新できるようにしてもよい。
【０１０１】
この実施の形態１では、各経由地での案内時刻および滞在可能時間は、ジャンル別経由地条件テーブル１５においてジャンル毎に設定されている。この他にもたとえば、経由候補地探索データ１３などにおいて、経由地毎に案内時刻および滞在可能時間が設定されていてもよい。これにより、ジャンル単位ではなく、経由候補地単位で個別に案内時刻および滞在可能時間を設定することができる。また、ユーザが経由地毎に案内時刻および滞在可能時間を入力するようにしてもよい。
【０１０２】
実施の形態２．
本発明の実施の形態２に係る車載ナビゲーション装置１のハードウェア構成、ハードディスクドライブ４の記憶内容は、実施の形態１に係る車載ナビゲーション装置１と同様である。ただし、案内経路生成プログラム１１の一部が変更されている。したがって、これらの構成については、実施の形態１と同じ符号を使用し、その説明を省略する。
【０１０３】
次に、以上のような構成を有する実施の形態２に係る車載ナビゲーション装置１の動作を説明する。
【０１０４】
中央処理装置２が案内経路生成プログラム１１を実行すると、車載ナビゲーション装置１には、案内経路を生成するための各種の機能ブロックが実現される。
【０１０５】
図１４は、本発明の実施の形態２に係る車載ナビゲーション装置１に実現される案内経路生成のための機能ブロックを示すブロック図である。中央処理装置２が案内経路生成プログラム１１を実行することで、車載ナビゲーション装置１には、経由候補地登録部２１と、経由地選択部２２と、発着条件設定部２３と、推奨経路生成部２４と、経路修正部４１と、推奨経路保存部２５とが実現される。
【０１０６】
経由候補地登録部２１は、経由候補地登録データ１４を更新する。経由地選択部２２は、経由候補地探索データ１３および経由候補地登録データ１４に基づいて、ユーザにより選択された複数の経由候補地を、複数の経由地としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【０１０７】
発着条件設定部２３は、ユーザにより入力された出発地の地点および出発時刻、並びに、目的地の地点および到達時刻を発着条件としてＲＡＭ３あるいはハードディスクドライブ４に記憶させる。
【０１０８】
推奨経路生成部２４は、ユーザにより選択された経由地を経由して、ユーザが入力した出発地から目的地に至る推奨経路を探索する。
【０１０９】
経路修正部４１は、まず、推奨経路生成部２４が生成した推奨経路を表示手段としての液晶モニタ５に表示させる。そして、ユーザがこの液晶モニタ５の画面に応じてタッチパネル８を操作すると、変更手段としての経路修正部４１は、推奨経路生成部２４が生成した推奨経路を、その操作に応じた経路へ更新する。また、推奨経路保存部２５は、経路修正部４１によって更新された推奨経路と、その推奨経路での経由地間の実際の案内経路とを、表示手段としての液晶モニタ５に表示させるとともに、ＲＡＭ３あるいはハードディスクドライブ４に記憶させる。なお、この推奨経路に基づく経路誘導部の案内動作は、実施の形態１の経路誘導部の案内動作と同じであり、その説明を省略する。
【０１１０】
図１５は、推奨経路生成部２４が生成した推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。この推奨経路生成部２４が生成した推奨経路では、出発地を９：００に出発した後、９：３０から１.５時間、公園（第一経由地）に滞在し、１１：５０から１．５時間、レストラン（第二経由地）で昼食をとり、１４：２０から２時間、動物園（第三経由地）に滞在し、１６：５０に目的地に到着する。
【０１１１】
このような推奨経路が液晶モニタ５に表示されている状態で、ユーザが公園（第一経由地）とレストラン（第二経由地）との間に新たな経由地として喫茶店を追加すると、経路修正部４１は、第一経由地を公園、第二経由地を喫茶店、第三経由地をレストラン、第四経由地を動物園とする新たな推奨経路を生成する。また、経路修正部４１は、この新たな推奨経路での経由地間の移動時間を計算するとともに、ユーザが入力した発着条件を満たすように各経由地での滞在時間を見直して、新たな推奨経路を生成する。
【０１１２】
図１６は、推奨経路生成部２４が生成した図１５に示す推奨経路に、喫茶店が経由地として追加された場合の、変更された推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。図１６の例では、公園とレストランの間に喫茶店が追加されることで、公園での滞在時間が１.５時間から１時間に短縮され、レストランでの滞在時間が１.５時間から１時間に短縮され、動物園への到着時刻が１４：２０から１４：３０へ変更されている。
【０１１３】
また、図１６に示す推奨経路が液晶モニタ５に表示されている状態で、ユーザが公園（第一経由地）とレストラン（第二経由地）との間から、喫茶店を削除すると、経路修正部４１は、第一経由地を公園、第二経由地をレストラン、第三経由地を動物園とする新たな推奨経路を生成する。この経路は、図１５に例示する推奨経路と同じものとなる。
【０１１４】
また、図１６に示す推奨経路が液晶モニタ５に表示されている状態で、ユーザが第二経由地の喫茶店を滝へ変更すると、経路修正部４１は、第一経由地を公園、第二経由地を滝、第三経由地をレストラン、第四経由地を動物園とする新たな推奨経路を生成する。
【０１１５】
図１７は、図１６に示す推奨経路において喫茶店が滝へ変更された場合の、変更された推奨経路（経由パターン）を表示する表示画面の一例を示す画面説明図である。図１７の例では、喫茶店が滝へ変更されることで、レストランでの滞在時間が１時間から５０分へ短縮され、動物園への到着時刻が１４：３０から１４：４０へ変更されている。
【０１１６】
以上のように、この実施の形態２に係る車載ナビゲーション装置１では、ユーザが指定した発着条件の下で各経由地での滞在時間を最大限に確保した案内経路を生成し、さらにその案内経路を適宜変更することができる。
【０１１７】
したがって、ユーザは、単に車載ナビゲーション装置１が探索した案内経路ではなく、自分でカスタマイズした納得のいく案内経路にて誘導されることになる。
【０１１８】
以上の各実施の形態は、本発明の好適な実施の形態の例であるが、本発明はこれに限定されるものではなく、種々の変形、変更が可能である。
【０１１９】
たとえば、上記各実施の形態において、案内時刻は、その店舗などのジャンルの営業時間の典型値に基づいて設定されるようにしてもよい。また、案内時刻の設定がある場合、案内時刻の後の所定の時間は少なくとも滞在させる拘束条件を設けるようにしてもよい。
【０１２０】
上記各実施の形態では、案内経路を生成する案内経路探索装置は、それが生成した案内経路で誘導を行う車載ナビゲーション装置１に組み込まれている。この他にもたとえば、案内経路探索装置は、車載ナビゲーション装置とは別体のコンピュータ装置などにおいて実現されてもよい。さらにたとえば、その車載ナビゲーション装置と、それとは別体のコンピュータ装置とは、インターネット、無線通信網などのデータ通信網を介してデータ通信可能に接続されていてもよい。さらにたとえば、車載ナビゲーション装置とは別体のコンピュータ装置は、データ通信網を介して、車載ナビゲーション装置において選択された複数の経由地に関する情報を受信し、且つ、生成した案内経路を車載ナビゲーション装置へ送信するように構成されていてもよい。
【０１２１】
上記各実施の形態は、車載ナビゲーション装置１を例とするものである。本発明に係る案内経路探索装置、案内経路の探索方法およびナビゲーション装置は、この他にもたとえば、携帯電話端末、小型ノートコンピュータ装置、ＰＤＡ（Personal Digital Assistants）装置などのポータブル情報装置などに適用することができる。さらに、本発明に係る案内経路探索装置および案内経路の探索方法については、デスクトップコンピュータなどの情報装置などに適用することができる。
【産業上の利用可能性】
【０１２２】
本発明に係る案内経路探索装置、ナビゲーション装置および案内経路の探索方法は、たとえば、自動車などの車両に搭載する車載ナビゲーション装置、歩行者用ナビゲーション装置、その他のナビゲーション装置などに利用することができる。
【符号の説明】
【０１２３】
１  車載ナビゲーション装置（ナビゲーション装置）
２  中央処理装置（経路誘導手段）
５  液晶モニタ（表示手段）
９  ＧＰＳ受信機（現地位置更新手段）
１５  ジャンル別経由地条件テーブル（滞在時刻、滞在時間、滞在条件）
２２  経由地選択部（経由地指定手段）
２４  推奨経路生成部（選択手段、仮決定手段、判定手段、調整手段）
４１  経路修正部（変更手段）
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
【図６】
2010204111.tif 000020