(57)【要約】【課題】経由地での滞在時間を確実に確保し、経由地での滞在時間による交通状況を推定する時刻のずれを防ぎ、出発地から目的地までの最適な経路の経路探索と所要時間の算出精度の向上を図ることのできる巡回経路探索装置を提供すること。【解決手段】経路探索手段１において、経路探索条件設定部１１は、経路探索条件入力手段２から入力された経由地の位置座標から経由地に該当する施設を経由地点情報蓄積ＤＢ１６から検索し、該当する施設の滞在時間を含んだ経由地情報を経路探索条件として設定し、経路パターン算出部１２は、経路探索条件に基づき、出発地から全ての経由地を経由して出発地に戻る経由地の経由順序の全ての組合せを算出し、経路探索部１３は、算出された全ての組合せについて、経由地の滞在時間を含む累計の所要時間に基づいて、交通状況推定部１４により推定された交通状況による道路区間の通過所要時間を使って最適な経路を探索する。【選択図】図１
2007218742.tif 000002
【特許請求の範囲】
【請求項１】
出発地、経由地、出発予定時刻または到着予定時刻を含む経路探索条件を入力される経路探索条件入力手段と、前記出発地と目的地を同一とし、前記経由地に対応する施設が登録されているとき、この施設に設定された滞在時間をこの経由地の滞在時間とし、前記出発地から前記目的地の間に全ての前記経由地を経由する全経路において、前記出発予定時刻または到着予定時刻を基準として、前記経路上の各道路区間に至る時刻を、前記道路区間に至るまでに通過した各道路区間の推定された通過所要時間と通過した前記経由地での滞在時間を累計した所要時間から算出し、この時刻から推定した前記道路区間の交通状況によりこの道路区間の通過所要時間を求め、求めた各道路区間の通過所要時間と前記各経由地の滞在時間を累計した所要時間が最小となる経路を探索する経路探索手段とを備えることを特徴とする経路探索装置。
【請求項２】
前記経路探索条件に出発予定時刻が入力された場合、前記経路探索手段は、前記出発予定時刻を基準にして、出発地から順次、前記経路上の道路区間の通過所要時間を求め、求めた通過所要時間を累計の所要時間に加算し、前記出発予定時刻に前記累計の所要時間を加算した時刻を次の道路区間の到着時刻として交通状況を推定して通過所要時間を求め、これを繰り返して前記経路の所要時間を算出することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記経路探索条件に到着予定時刻が入力された場合、前記経路探索手段は、前記到着予定時刻を基準にして、目的地から順次、前記経路上の道路区間の通過所要時間を求め、求めた通過所要時間を累計の所要時間に加算し、前記到着予定時刻から前記累計の所要時間を減算した時刻を次の道路区間の通過時刻として交通状況を推定して通過所要時間を求め、これを繰り返して前記経路の所要時間を算出することを特徴とする請求項１に記載の経路探索装置。
【請求項４】
現在位置および現在時刻を算出する現在位置算出手段を備え、前記経路探索手段は、出発地および出発予定時刻として現在位置および現在時刻を使うことを指定された場合、前記現在位置算出手段から現在位置および現在時刻を取得し、現在位置を出発地とし、現在時刻を出発予定時刻とすることを特徴とする請求項１または請求項２に記載の経路探索装置。
【請求項５】
経由地の候補となる施設の位置情報と種別と滞在時間とを含む経由地点情報を蓄積する経由地点情報蓄積手段を備え、前記経路探索手段は、入力された経由地に該当する施設を前記経由地点情報蓄積手段から検索し、該当する施設がある場合は当該施設の滞在時間を前記経由地の滞在時間とし、該当する施設がない場合は滞在時間を無しとすることを特徴とする請求項１から請求項４までのいずれかに記載の経路探索装置。
【請求項６】
前記経由地点情報蓄積手段は、施設の種別毎の滞在時間を含む施設別情報を蓄積し、前記経路探索手段は、前記経由地に該当する施設の種別が前記施設別情報にある場合、前記施設情報の当該種別の滞在時間を前記経由地の滞在時間とすることを特徴とする請求項５に記載の経路探索装置。
【請求項７】
前記経由地点情報蓄積手段の情報を設定変更する経由地点情報設定手段を備えることを特徴とする請求項５または請求項６に記載の経路探索装置。
【請求項８】
前記経路探索手段は、設定された距離内に複数の前記経由地がある場合、この複数の経由地を１つの経由地とみなして経由地の経由順序を算出することを特徴とする請求項１から請求項７までのいずれかに記載の経路探索装置。
【請求項９】
経路探索の情報の入力を受け付けるとともに経路探索結果を表示する端末装置と、前記端末装置からの要求により経路探索を行い探索結果を返すセンタ装置とを備え、前記端末装置は、入力された出発地、経由地、出発予定時刻または到着予定時刻を含む情報から出発地を目的地とする経路探索条件を作成する経路探索条件作成手段と、前記経路探索条件を前記センタ装置に送信する経路探索条件送信手段と、前記センタ装置から経路探索結果を受信する経路探索結果受信手段と、前記経路探索結果を表示する画面表示手段とを有し、前記センタ装置は、前記端末装置から経路探索条件を受信する経路探索条件受信手段と、前記経由地に対応する施設が登録されているとき、この施設に設定された滞在時間をこの経由地の滞在時間とし、前記出発地から前記目的地の間に全ての前記経由地を経由する全経路において、前記出発予定時刻または到着予定時刻を基準として、前記経路上の各道路区間に至る時刻を、前記道路区間に至るまでに通過した各道路区間の推定された通過所要時間と通過した前記経由地での滞在時間を累計した所要時間から算出し、この時刻から推定した前記道路区間の交通状況によりこの道路区間の通過所要時間を求め、求めた各道路区間の通過所要時間と前記各経由地の滞在時間を累計した所要時間が最小となる経路を探索し、探索された経路の情報を経路探索結果とする経路探索手段と、前記経路探索結果を前記端末装置に送信する経路探索結果送信手段とを有することを特徴とする経路探索システム。
【請求項１０】
出発地、目的地、経由地、出発予定時刻または到着予定時刻を含む経路探索条件を受信する経路探索条件受信手段と、前記経由地に対応する施設が登録されているとき、この施設に設定された滞在時間をこの経由地の滞在時間とし、前記出発地から前記目的地の間に全ての前記経由地を経由する全経路において、前記出発予定時刻または到着予定時刻を基準として、前記経路上の各道路区間に至る時刻を、前記道路区間に至るまでに通過した各道路区間の推定された通過所要時間と通過した前記経由地での滞在時間を累計した所要時間から算出し、この時刻から推定した前記道路区間の交通状況によりこの道路区間の通過所要時間を求め、求めた各道路区間の通過所要時間と前記各経由地の滞在時間を累計した所要時間が最小となる経路を探索し、探索された経路の情報を経路探索結果とする経路探索手段と、前記経路探索結果を前記経路探索条件の送信元に送信する経路探索結果送信手段とを備えることを特徴とするセンタ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から途中の経由地を経由し、元の出発地まで戻る移動経路において、途中の経由地の滞在時間と交通状況の時間変化を考慮し、推奨経路を提示する経路探索装置および経路探索システムに関する。
【背景技術】
【０００２】
従来のカーナビゲーションシステム等に搭載されている経路探索装置では、過去の交通状況に基づき、通過時間に該当する交通状況を推測し、交通状況の時刻変化を考慮した上で出発地から目的地までの所要時間が最小になる移動経路を探索して、その結果を利用者に提示している。
【０００３】
また、目的地と目的地への到着予定時刻と経由地を設定し、現状の交通状況から経路探索を行い、経由地に滞在できる時間を案内し、走行中に、随時、交通状況を取得し、交通状況に変化があった場合には、経由地に滞在できる時間を更新した上で利用者に案内するもの（例えば、特許文献１参照）や、訪問先毎に滞在時間を共通のデータベース上に記憶しておき、複数の訪問先の訪問時間と滞在時間から、最適な巡回経路を探索し、案内時は、経路探索結果と訪問予定時刻と訪問時間から訪問先到着後の予測待ち時間を提供するもの（例えば、特許文献２参照）などもある。
【特許文献１】特開２００２−３６５０７６号公報
【特許文献２】特開２００４−７８４１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に記載されたようなものの場合、経路探索後に経由地での滞在時間を算出しているため、交通状況によっては経由地に滞在する時間がなく、滞在目的で設定した経由地を利用できない場合が発生する可能性があるという課題があった。
【０００５】
また、特許文献２に記載されたようなものの場合、訪問先毎に利用者共通の滞在時間としているため、利用者個人の要望や用件による滞在時間の違いが考慮されていないという課題や、訪問先の移動時間に経時変化する交通状況を反映していないため、実際に移動するときに交通状況が変化した場合、計画通りの移動ができない可能性があるという課題がある。
【０００６】
本発明は、従来の課題を解決するためになされたもので、経由地での滞在時間を確実に確保し、経由地での滞在時間による交通状況を推定する時刻のずれを防ぎ、出発地から目的地までの最適な経路の経路探索と所要時間の算出精度の向上を図ることのできる巡回経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の経路探索装置は、出発地、経由地、出発予定時刻または到着予定時刻を含む経路探索条件を入力される経路探索条件入力手段と、前記出発地と目的地を同一とし、前記経由地に対応する施設が登録されているとき、この施設に設定された滞在時間をこの経由地の滞在時間とし、前記出発地から前記目的地の間に全ての前記経由地を経由する全経路において、前記出発予定時刻または到着予定時刻を基準として、前記経路上の各道路区間に至る時刻を、前記道路区間に至るまでに通過した各道路区間の推定された通過所要時間と通過した前記経由地での滞在時間を累計した所要時間から算出し、この時刻から推定した前記道路区間の交通状況によりこの道路区間の通過所要時間を求め、求めた各道路区間の通過所要時間と前記各経由地の滞在時間を累計した所要時間が最小となる経路を探索する経路探索手段とを備える構成を有している。
【０００８】
この構成により、入力された経由地に対応する施設の滞在時間が経由地の滞在時間とされ、出発予定時刻または到着予定時刻を基準に、道路区間に至るまでの経路の道路区間の推定された通過所要時間と経由地の滞在時間との累計の所要時間から求められた時刻により交通状況が推定され道路区間の通過所要時間が求められる。したがって、経由地での滞在時間を確実に確保し、経由地での滞在時間による交通状況を推定する時刻のずれを防ぐことができる。
【０００９】
ここで、前記経路探索条件に出発予定時刻が入力された場合、前記経路探索手段は、前記出発予定時刻を基準にして、出発地から順次、前記経路上の道路区間の通過所要時間を求め、求めた通過所要時間を累計の所要時間に加算し、前記出発予定時刻に前記累計の所要時間を加算した時刻を次の道路区間の到着時刻として交通状況を推定して通過所要時間を求め、これを繰り返して前記経路の所要時間を算出する構成とした。
【００１０】
この構成により、出発予定時刻を基準にして、出発地から順次、経路上の道路区間の通過所要時間が推定され、推定された通過所要時間を使って次の道路区間の到着時刻が求められ、その時刻の推定された交通状況により通過所要時間が求められる。
【００１１】
また、前記経路探索条件に到着予定時刻が入力された場合、前記経路探索手段は、前記到着予定時刻を基準にして、目的地から順次、前記経路上の道路区間の通過所要時間を求め、求めた通過所要時間を累計の所要時間に加算し、前記到着予定時刻から前記累計の所要時間を減算した時刻を次の道路区間の通過時刻として交通状況を推定して通過所要時間を求め、これを繰り返して前記経路の所要時間を算出する構成とした。
【００１２】
この構成により、到着予定時刻を基準にして、目的地から順次、経路上の道路区間の通過所要時間が推定され、推定された通過所要時間を使って次の道路区間の通過時刻が求められ、その時刻の推定された交通状況により通過所要時間が求められる。
【００１３】
さらに、現在位置および現在時刻を算出する現在位置算出手段を備え、前記経路探索手段は、出発地および出発予定時刻として現在位置および現在時刻を使うことを指定された場合、前記現在位置算出手段から現在位置および現在時刻を取得し、現在位置を出発地とし、現在時刻を出発予定時刻とする構成とした。
【００１４】
この構成により、出発地および出発予定時刻として現在位置および現在時刻を使うことを指定されると、現在位置取得手段から現在位置と現在時刻が取得されて経路探索が行われ、入力の手間を削減することができる。
【００１５】
また、経由地の候補となる施設の位置情報と種別と滞在時間とを含む経由地点情報を蓄積する経由地点情報蓄積手段を備え、前記経路探索手段は、入力された経由地に該当する施設を前記経由地点情報蓄積手段から検索し、該当する施設がある場合は当該施設の滞在時間を前記経由地の滞在時間とし、該当する施設がない場合は滞在時間を無しとする構成とした。
【００１６】
この構成により、経由地が施設であるか道路上の通過点であるかが判定され、施設であれば、該当する施設に設定された滞在時間が使われて経路探索される。
【００１７】
また、前記経由地点情報蓄積手段は、施設の種別毎の滞在時間を含む施設別情報を蓄積し、前記経路探索手段は、前記経由地に該当する施設の種別が前記施設別情報にある場合、前記施設情報の当該種別の滞在時間を前記経由地の滞在時間とする構成とした。
【００１８】
この構成により、施設の種別により滞在時間が選択され、個別の施設に対し滞在時間を設定する手間を削減することができる。
【００１９】
また、前記経由地点情報蓄積手段の情報を設定変更する経由地点情報設定手段を備える構成とした。
【００２０】
この構成により、経由地点情報蓄積手段の情報を、利用者の好み、利用状況などに応じて変更することができる。
【００２１】
また、前記経路探索手段は、設定された距離内に複数の前記経由地がある場合、この複数の経由地を１つの経由地とみなして経由地の経由順序を算出する構成とした。
【００２２】
この構成により、経由地の組合せ数を削減することができ、経路探索に必要な処理量や処理時間を削減することができる。
【００２３】
本発明の経路探索システムは、経路探索の情報の入力を受け付けるとともに経路探索結果を表示する端末装置と、前記端末装置からの要求により経路探索を行い探索結果を返すセンタ装置とを備え、前記端末装置は、入力された出発地、経由地、出発予定時刻または到着予定時刻を含む情報から出発地を目的地とする経路探索条件を作成する経路探索条件作成手段と、前記経路探索条件を前記センタ装置に送信する経路探索条件送信手段と、前記センタ装置から経路探索結果を受信する経路探索結果受信手段と、前記経路探索結果を表示する画面表示手段とを有し、前記センタ装置は、前記端末装置から経路探索条件を受信する経路探索条件受信手段と、前記経由地に対応する施設が登録されているとき、この施設に設定された滞在時間をこの経由地の滞在時間とし、前記出発地から前記目的地の間に全ての前記経由地を経由する全経路において、前記出発予定時刻または到着予定時刻を基準として、前記経路上の各道路区間に至る時刻を、前記道路区間に至るまでに通過した各道路区間の推定された通過所要時間と通過した前記経由地での滞在時間を累計した所要時間から算出し、この時刻から推定した前記道路区間の交通状況によりこの道路区間の通過所要時間を求め、求めた各道路区間の通過所要時間と前記各経由地の滞在時間を累計した所要時間が最小となる経路を探索し、探索された経路の情報を経路探索結果とする経路探索手段と、前記経路探索結果を前記端末装置に送信する経路探索結果送信手段とを有する構成を有している。
【００２４】
この構成により、センタ装置と端末装置で機能が分割され、端末装置を軽量化することができ、利便性を向上させることができる。
【００２５】
本発明のセンタ装置は、出発地、目的地、経由地、出発予定時刻または到着予定時刻を含む経路探索条件を受信する経路探索条件受信手段と、前記経由地に対応する施設が登録されているとき、この施設に設定された滞在時間をこの経由地の滞在時間とし、前記出発地から前記目的地の間に全ての前記経由地を経由する全経路において、前記出発予定時刻または到着予定時刻を基準として、前記経路上の各道路区間に至る時刻を、前記道路区間に至るまでに通過した各道路区間の推定された通過所要時間と通過した前記経由地での滞在時間を累計した所要時間から算出し、この時刻から推定した前記道路区間の交通状況によりこの道路区間の通過所要時間を求め、求めた各道路区間の通過所要時間と前記各経由地の滞在時間を累計した所要時間が最小となる経路を探索し、探索された経路の情報を経路探索結果とする経路探索手段と、前記経路探索結果を前記経路探索条件の送信元に送信する経路探索結果送信手段とを備える構成を有している。
【００２６】
この構成により、処理の重い機能をセンタ装置に分担させているので、経路探索条件を送信し、経路探索結果を受信する装置を軽量化することができ、利便性を向上させることができる。
【発明の効果】
【００２７】
本発明によれば、入力された経由地に対応する施設の滞在時間を経由地の滞在時間とし、出発予定時刻または到着予定時刻を基準に、道路区間に至るまでの経路の道路区間の推定された通過所要時間と経由地の滞在時間との累計の所要時間から求められた時刻により交通状況を推定し道路区間の通過所要時間を求めているので、経由地での滞在時間を確実に確保し、経由地での滞在時間による交通状況を推定する時刻のずれを防ぐことができる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施の形態について、図面を参照して説明する。
【００２９】
（第１の実施の形態）
図１は本発明の第１の実施の形態の経路探索装置を示す図である。
【００３０】
図１において、本実施の形態の経路探索装置は、巡回経路探索の指定や出発地や経由地や出発予定時刻あるいは到着予定時刻等の経路探索の条件の入力を受け付ける、例えばタッチパネルやキーボードやリモコン等を有した経路探索条件入力手段２と、経路探索条件入力手段２から入力された経路探索条件に基づいて経路探索を行う経路探索手段１と、経路探索手段１が作成した経路探索結果の画面表示情報を画面上に表示する画面表示手段３とを備えている。
【００３１】
経路探索手段１は、経路探索条件入力手段２に入力された経路探索条件に基づいて経由地情報を作成し経路探索条件の設定を行う経路探索条件設定部１１と、経路探索条件設定部１１が設定した経路探索条件に基づき出発地から経由地を経由して出発地に戻る経由地の経由順の全ての組合せを算出する経路パターン算出部１２と、経路探索条件設定部１１が設定した経路探索条件に基づき経路パターン算出部１２が算出した経路地の組合せについて所要時間が最小になる経路探索を行う経路探索部１３と、経路探索部１３の要求により交通状況を推定して通知する交通状況推定部１４と、経路探索部１３の経路探索結果に基づき経路探索結果の画面表示情報を作成する画面表示処理部１５と、経由地の施設名称、施設の種別、施設の位置座標、滞在時間等の経由地点情報を蓄積する経由地点情報蓄積データベース（ＤＢ）１６と、交差点間の道路である道路区間の通過時間に基づく走行コスト情報と道路区間毎の接続情報を蓄積する道路ネットワークデータベース（ＤＢ）１７と、過去の交通情報を道路区間毎に時刻、曜日、天気等で分類して記録している交通情報蓄積データベース（ＤＢ）１８とを備えている。
【００３２】
経路探索条件設定部１１は、経路探索条件入力手段２により入力された出発地と経由地、および出発予定時刻または到着予定時刻等と、指定された経由地に該当する施設を経由地点情報蓄積ＤＢ１６から経由地の位置座標に基づいて経由地に該当する施設を検索し、経由地に該当する施設がある場合には、該当する施設の滞在時間と施設種別を取得し、該当する施設がない場合には、滞在時間がないと設定して作成した経由情報とを経路探索部１３に対する経路探索条件として経路パターン算出部１２に出力する。
【００３３】
経路パターン算出部１２は、経路探索条件設定部１１が設定した経路探索条件に基づき、出発地から全ての経由地を経由し、出発地に戻るための経由地の経由順の全ての組合せを算出する。このとき、出発地と全ての経由地の位置を比較し、設定された距離以内にある場合には、一つの経由地と見なして連続して経由するように組合せを作成する。
【００３４】
経路探索部１３は、経路探索条件設定部１１が設定した経路探索条件に基づき、経路パターン算出部１２で算出した経由地の経由順の全ての組合せに対して、道路ネットワークＤＢ１７から道路区間の接続関係情報と道路区間の通過時間に基づく道路の走行コスト情報を取得して経路探索ネットワークを構築し、出発地からの累積所要時間に経由地に設定された滞在時間を反映し、滞在時間を反映した累積の所要時間に対応する時刻の道路区間の交通状況の推定結果を交通状況推定部１４から取得して経路探索ネットワーク内の道路区間の走行コストを更新した上で、出発地から経由地を経由し出発地に戻るまでの所要時間が最小になる経路を求める。
【００３５】
交通状況推定部１４は、経路探索部１３が要求する道路区間と交通状況を推定する時刻に従い、交通情報蓄積ＤＢ１８から該当する道路区間と時刻の過去の交通状況を取得して交通状況の推定を行い、経路探索部１３に交通状況の推定結果を通知する。
【００３６】
図２と図３は、経由地点情報蓄積ＤＢ１６に蓄積する経由地点情報の例を示す図である。
【００３７】
図２は、経由地の施設情報を記憶したものであり、経由地点の施設の名称とファーストフードやコンビニエンスストア等の施設種別と施設毎の位置座標と施設毎に想定される通常滞在時間と宿泊の可・不可を記憶している。
【００３８】
また、ホテルや旅館のように宿泊が可能である施設の場合、想定される到着時刻や出発時刻を設定する。
【００３９】
経由地を検索する場合、利用者に施設の種別も指定させ、位置座標に加え施設の種別が一致するものを検索するようにしてもよい。
【００４０】
図３は、図２の施設情報に加え、施設の種別毎の共通の設定を行う場合であり、ファーストフードやコンビニエンスストア等の施設種別と滞在時間と宿泊の可・不可、ホテルや旅館のように宿泊が可能である施設の場合、想定される到着時刻や出発時刻を設定する。
【００４１】
なお、経由地点情報蓄積ＤＢ１６の情報が、書換可能なＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disk）のような記憶媒体に記録されている場合、経由地点情報を利用者が実際に経由地で滞在した時間や利用者が滞在したい時間や各施設で調査した結果、あるいは宿泊可能な場合には到着したい時刻や出発したい時刻等を記録するようにすると、利用者の好みに応じて設定することができ、利便性を向上させることができる。
【００４２】
このような経路探索装置の経路探索方法について説明する。
【００４３】
図４は、本実施の形態の経路探索装置の経路探索方法を示すフローチャートである。
【００４４】
利用者が、経路探索条件入力手段２により、巡回経路探索の実行を指示すると、図４のフローチャートに示すように、経路探索条件入力手段２は、利用者に対し経路探索条件の入力を要求する（Ｓ１１）。この利用者への要求は、案内音声の出力や画面への表示により利用者に通知する。
【００４５】
経路探索条件の入力を要求された利用者は、経路探索条件入力手段２のタッチパネルやキーボードやリモコン等から、出発地や経由地や出発予定時刻または到着予定時刻等を入力し、経路探索条件を設定する。ここで、経路探索条件として、経由地が宿泊可能な施設である場合、経路探索結果の到着時刻が設定された時刻を過ぎた場合、または経路探索結果の出発時刻が設定された時刻より前になった場合の宿泊可否を入力できるようにしてもよい。
【００４６】
経路探索条件入力手段２は、利用者からの経路探索条件の入力を受け付けると、経路探索条件を経路探索手段１の経路探索条件設定部１１に通知し、経路探索条件設定部１１は、まず設定された経路探索条件の出発地を目的地とする（Ｓ１２）。
【００４７】
次に、全ての経由地について、経由地点情報蓄積ＤＢ１６から経由地に該当する施設の検索を位置座標の比較により行い、経由地に一致する施設がある場合、該当する施設の滞在時間情報や施設種別等を取得し、滞在時間情報を当該経由地の滞在時間とし、一致する施設が無い場合、当該経由地の滞在時間は無しとし、通過のみとして、経由地の滞在時間の設定を行い（Ｓ１３）、経路探索条件として経路パターン算出部１２に通知する。
【００４８】
例えば、経由地点情報蓄積ＤＢ１６に図３に示すように施設の種別毎に滞在時間が設定されている場合、経由地に該当する施設の施設種別に対応する滞在時間を当該経由地の滞在時間とする。
【００４９】
次に、経路パターン算出部１２は、出発地から目的地である出発地までに通過する全ての経由地について、図５に示すように、まず出発地と全ての経由地のそれぞれの間の距離を算出し、規定された距離以内の経由地は連続して通過する経由地として一つの通過単位（経由地群）として設定する。ここで、規定距離以内の経由地が複数存在する場合には、最も距離が近い経由地同士を一つの経由地群とする。そして、この経由地群と他の経由地や経由地群との距離を算出し、規定距離以内の経由地や経由地群を、この経由地群に追加する。このような処理を全ての経由地に対して行い、経由地群に含まれずに残った経由地は単独で経由地群として経由地群を構成し（Ｓ１４）、構成した全ての経由地群について通過順序の組合せの算出を行い（Ｓ１５）、算出した通過順序の組合せを経路探索部１３に通知する。
【００５０】
なお、経由地群を構成せず、個々の経由地に関する経路組合せにより経路探索を行ってもよい。
【００５１】
また、経路組合せにおける経由地群あるいは経由地間の距離、例えば直線距離を経由地順に算出し、全ての経由地組合せについて経由地群あるいは経由地間の距離の合計値が少ないものから数個の組合せ、または距離の合計値が距離の合計値の最小の値から規定の比率内の経路組合せのみについて巡回経路探索を行うようにすれば、巡回経路探索の経路探索処理時間を削減することができる。
【００５２】
次に、経路探索部１３は、算出された経由地群の通過順序に従って経由地の通過順序を設定する（Ｓ１６）。ここで、複数の経由地を含む経由地群における経由地の設定順序は、一つ前に設定された経由地に距離が近い経由地から設定する。
【００５３】
そして、通過順序に従って次の経由地までの経路について、道路ネットワークＤＢ１７に蓄積されている道路ネットワーク情報から、道路区間毎の接続情報と道路区間の走行コストから構成される経路探索ネットワークを構築する（Ｓ１７）。
【００５４】
経路探索ネットワーク構築後、構築した経路探索ネットワークの道路区間について、出発予定時刻が設定されている場合、出発地から目的地に向かって、到着予定時刻が設定されている場合、目的地から出発地に向かって、出発地の出発予定時刻、あるいは目的地の到着予定時刻からの累計の所要時間より算出した道路区間入口の到達時刻に基づき、道路区間に該当する時刻の交通状況を交通状況推定部１４で実施し、推定した交通状況に基づく道路区間の走行コストを算出し、算出した走行コストを構築した経路探索ネットワークの走行コストと置き換え、この結果を用いて次の道路区間も同様に到着時刻に基づき推定した交通状況による走行コストを算出し、算出した走行コストを構築した経路探索ネットワークの走行コストと置き換え、これを繰り返して次の経由地までの経路探索ネットワークを更新し、更新した経路探索ネットワークから走行コストが最小となる経路を探索する（Ｓ１８）。
【００５５】
ここで、交通状況推定部１４で使用する交通情報蓄積ＤＢ１８は、過去の交通状況から交通情報蓄積ＤＢ１８を一括して作成する方法と、随時最新の交通情報を受信し、随時交通情報蓄積ＤＢ１８を更新する方法が考えられる。
【００５６】
そして、次の経由地の滞在時間に基づき、累積の所要時間を更新する（Ｓ１９）。ここで、経由地が宿泊可能な施設である場合、経路探索条件設定時に宿泊可と設定されていれば、出発地からの経路探索時に経路探索結果の到着時刻が設定された到着時刻（例えば、１８時）を過ぎているとき、宿泊とし、次の経由地までの経路探索はこの経由地の経由地点情報蓄積ＤＢ１６に設定されている出発時刻からの累積の所要時間により行い、目的地からの経路探索時に経路探索結果の出発時刻が設定されている出発時刻（例えば、８時）より前になったとき、宿泊とし、次の経由地までの経路探索はこの経由地の経由地点情報蓄積ＤＢ１６に設定されている到着時刻からの累積の所要時間により行う。
【００５７】
次に、全ての経由地を経由して経路探索を行ったかを判定し（Ｓ２０）、経由しない経由地が残っていれば、Ｓ１７に戻り、次の経由地までの経路探索ネットワークの構築から繰り返す。
【００５８】
全ての経由地を経由していれば、Ｓ１７と同様にして、最後の経由地から目的地（＝出発地）までの経路探索ネットワークを構築し（Ｓ２１）、Ｓ１８と同様にして、経路探索ネットワークを到着時刻に基づいて推定した走行コストにより更新し、更新した経路探索ネットワークから走行コストが最小となる経路を探索する（Ｓ２２）。
【００５９】
Ｓ１５で算出した全ての組合せについて経路探索が終了したか判定し（Ｓ２３）、全ての組合せについて経路探索が終了していなければ、Ｓ１６に戻り、経由地の通過順序の設定から繰り返す。
【００６０】
全ての組合せについて経路探索が終了したら、経路探索部１３は、全ての組合せの経路を比較し、走行コストが最小の経路、例えば、最小の所要時間の経路を選択し、巡回経路探索結果として画面表示処理部１５において表示情報を作成し、画面表示手段に表示して利用者に提示する（Ｓ２４）。
【００６１】
ここで、経路組合せの経路探索結果のうち、一部の経路探索結果、あるいは、全ての経路探索結果を利用者に提示し、利用者が経路を選択するようにしてもよい。そのとき、各経路の走行距離などを同時に提示するようにしてもよい。
【００６２】
図６は、経由地での滞在時間を考慮しなかった場合の例を示す図、図７は、経由地での滞在時間を考慮した場合の例を示す図、図８は、推定した交通状況から導いた道路区間での時刻毎の所要時間の例を示す図である。
【００６３】
図６に示すように、経由地での滞在時間を考慮しなかった場合、経由地への到着時刻Ｔ＋ｔ1が出発時刻となり、次の道路区間の通過時刻はＴ＋ｔ1となり、推定した交通状況から導いた次の道路区間の所要時間は、図８で示すようにｔ2’となる。
【００６４】
しかし、図７に示すように、経由地での滞在時間を考慮した場合、経由地での滞在時間をｔviaとすると、次の道路区間の通過時刻はＴ＋ｔ1＋ｔviaとなり、推定した交通状況から導いた次の道路区間の所要時間は、図８で示すようにｔ2となる。
【００６５】
このように、図８に示すような交通状況の変化を示す道路区間の場合、滞在時間を考慮した場合としない場合では、通過時間にｔ2−ｔ2’の差が発生してしまい、滞在時間を考慮しない場合、経路探索結果の出発地から目的地までの所要時間と実際に走行した場合の所要時間に差が生じてしまう。
【００６６】
このように本実施の形態においては、経由地点情報蓄積ＤＢ１６に設定された経由地の滞在時間を考慮し、指定された出発予定時刻または到着予定時刻から累積の所要時間（経由地の滞在時間を含んだ）により算出した時刻の交通状況を推定し、推定した交通状況により道路区間の通過時間を求めているので、確実に経由地での滞在時間を確保し、実際の交通状況に合った経路探索を行うことができ、経由地での滞在時間による交通状況を推定する時刻のずれを防ぎ、出発地から目的地までの最適な経路の経路探索と所要時間の算出精度の向上を図ることができる。
【００６７】
（第２の実施の形態）
次に、図９は本発明の第２の実施の形態の経路探索装置を示すブロック図である。なお、本実施の形態は、上述の第１の実施の形態と略同様に構成されているので、同様な構成には同一の符号を付して特徴部分のみ説明する。
【００６８】
本実施の形態の経路探索装置は、車両センサ５を備え、経路探索手段４の現在地算出部４２が車両センサ５から取得した情報に基づき、現在地の座標と現在時刻を算出して、現在地および現在時刻を出発地の位置および出発予定時刻として設定できるようにしたことを特徴とする。
【００６９】
車両センサ５は、ＧＰＳ（Global Positioning System）衛星から位置座標や現在時刻等から構成されるＧＰＳ情報を取得するＧＰＳ受信部５１と、ジャイロから車両の走行方向の変化を検出する角速度センサ５２と、車両の速度を取得する車速センサ５３とを備え、各々の取得情報を車両センサ情報として現在地算出部４２に通知する。
【００７０】
現在地算出部４２は、車両センサ５から取得したＧＰＳ（Global Positioning System）情報と角速度センサ情報および車速センサ情報に基づき、現在地の座標と現在時刻を算出して経路探索条件設定部４１に通知する。
【００７１】
このような経路探索装置において、経路探索条件入力手段２は、出発地および出発予定時刻として現在地および現在時刻を使用するように指定できるようになっていて、経路探索手段４の経路探索条件設定部４１は、出発地および出発予定時刻として現在地および現在時刻を使用するように指定されていると、現在地算出部４２から現在地の座標と現在時刻を取得し、経路探索条件の出発地および出発予定時刻として設定し、以降上述の実施の形態と同様、経由地に該当する施設を検索し、経由地の滞在時間の設定を行い、経路探索条件として経路パターン算出部１２に通知する。
【００７２】
以降、上述の実施の形態と同様にして経路探索を行い、探索結果を画面表示手段３に提示する。
【００７３】
このように本実施の形態においては、車両センサ５から取得した情報により現在地および現在時刻を算出し、経路探索の出発地および出発予定時刻として設定できるようにしたので、出発地および出発予定時刻を現在地および現在時刻としたい場合に、現在地および現在時刻を入力する手間を省くことができる。
【００７４】
（第３の実施の形態）
次に、図１０は本発明の第３の実施の形態の経路探索装置を示すブロック図である。なお、本実施の形態は、上述の第１の実施の形態と略同様に構成されているので、同様な構成には同一の符号を付して特徴部分のみ説明する。
【００７５】
本実施の形態の経路探索装置は、タッチパネルやキーボードやリモコン等から入力された経由地の施設の種類に対する滞在時間等の情報を経由地点情報蓄積ＤＢ６１に記録する経由地点情報設定手段７を備え、経由地点情報設定手段７から経由地点情報蓄積ＤＢ６１の施設の種類に対応した情報を追加・変更することができるようにしたことを特徴とする。
【００７６】
経由地点情報設定手段７は、利用者からの経由地情報の設定の指示を受けると、新しい施設の種類の追加か、既にある施設の種類の情報の変更かの入力を要求し、新しい施設の種類の追加であれば、施設の種類、滞在時間、宿泊条件、宿泊条件が可であれば到着時刻、出発時刻等の入力を要求する。
【００７７】
既にある施設の種類の情報の変更であれば、経由地点情報蓄積ＤＢ６１に蓄積されている施設の種類の一覧を表示し、変更する施設の種類を選択させ、経由地点情報蓄積ＤＢ６１に蓄積されている選択された施設の種類の情報を表示し、変更を要求する。
【００７８】
そして、利用者が入力を終了し、蓄積の指示を受けると、入力された情報を経由地点情報蓄積ＤＢ６１に蓄積する。
【００７９】
このように本実施の形態においては、経由地点情報設定手段７で経由地点情報蓄積ＤＢ６１の施設の種別毎の情報を変更できるようにしたので、施設の種別毎の滞在時間や宿泊条件などを利用者の好みに応じて設定することができ、利便性を向上させることができる。
【００８０】
（第４の実施の形態）
次に、図１１は本発明の第４の実施の形態の経路探索装置を示すブロック図である。なお、本実施の形態は、上述の第２および第３の実施の形態と略同様に構成されているので、同様な構成には同一の符号を付して特徴部分のみ説明する。
【００８１】
本実施の形態の経路探索装置は、車両センサ５および経由地点情報設定手段７を備え、経路探索手段４の現在地算出部４２が車両センサ５から取得した情報に基づき、現在地の座標と現在時刻を算出して、現在地および現在時刻を出発地の位置および出発予定時刻として設定できるようにするとともに、経由地点情報設定手段７から経由地点情報蓄積ＤＢ６１の施設の種類に対応した情報を追加・変更することができるようにしたことを特徴とする。
【００８２】
このように本実施の形態においては、車両センサ５から取得した情報により現在地および現在時刻を算出し、経路探索の出発地および出発予定時刻として設定できるようにするとともに、経由地点情報設定手段７で経由地点情報蓄積ＤＢ６１の施設の種別毎の情報を変更できるようにしたので、利便性を向上させることができる。
【００８３】
（第５の実施の形態）
次に、図１２は本発明の第５の実施の形態の経路探索システムを示すブロック図である。なお、本実施の形態は、上述の第２の実施の形態と略同様に構成されているので、同様な構成には同一の符号を付して特徴部分のみ説明する。
【００８４】
本実施の形態の経路探索システムは、上述の第２の実施の形態の経路探索装置を、経路探索条件を入力させるとともに経路探索結果を表示する端末装置１００と、端末装置１００に入力された経路探索条件に基づいて経路探索を行うセンタ装置１１０とに機能を分割したことを特徴としている。
【００８５】
このため、端末装置１００は、経路探索条件をセンタ装置１１０に送信する経路探索条件送信手段１０１と、センタ装置１１０から経路探索結果を受信する経路探索結果受信手段１０２とを備え、センタ装置１１０は、端末装置１００から経路探索条件を受信する経路探索条件受信手段１１１と、経路探索結果を端末装置１００に送信する経路探索結果送信手段１１２とを備えている。
【００８６】
また、端末装置１００は、車両センサ５と現在地算出部４２とを有し、経路探索条件入力手段２に入力された経路探索条件の出発地に現在地が設定されていた場合、現在地算出部４２から現在地の位置座標と現在時刻を取得して経路探索条件の出発地に現在地を、出発予定時刻に現在時刻を設定する経路探索条件作成部１０３も備えている。
【００８７】
経路探索条件送信手段１０１、経路探索結果受信手段１０２、経路探索条件受信手段１１１および経路探索結果送信手段１１２は、インターネットや電話回線等の有線回線、あるいは携帯電話回線やディジタルＭＣＡ（Multi Channel Access）無線等の無線回線を介して通信を行う。
【００８８】
このような経路探索システムにおいて、利用者が、端末装置１００の経路探索条件入力手段２により、巡回経路探索の実行を指示すると、経路探索条件入力手段２は、利用者に対し経路探索条件の入力を要求する。この利用者への要求は、案内音声の出力や画面への表示により利用者に通知する。
【００８９】
経路探索条件の入力を要求された利用者は、経路探索条件入力手段２のタッチパネルやキーボードやリモコン等から、出発地や経由地や出発予定時刻または到着予定時刻等を入力し、経路探索条件を設定する。ここで、出発地および出発予定時刻として現在地および現在時刻を選択できるようになっている。
【００９０】
また、経路探索条件として、経由地が宿泊可能な施設である場合、経路探索結果の到着時刻が設定された時刻を過ぎた場合、または経路探索結果の出発時刻が設定された時刻より前になった場合の宿泊可否を入力できるようにしてもよい。
【００９１】
経路探索条件入力手段２は、利用者からの経路探索条件の入力を受け付けると、経路探索条件を経路探索条件作成部１０３に通知する。
【００９２】
経路探索条件作成部１０３は、受信した経路探索条件の出発地に現在地が設定されていた場合、現在地算出部４２から現在地の位置座標と現在時刻を取得して経路探索条件の出発地に現在地を、出発予定時刻に現在時刻を設定し、作成した経路探索条件を経路探索条件送信手段１０１によりセンタ装置１１０に送信する。
【００９３】
センタ装置１１０の経路探索条件受信手段１１１は、受信した経路探索条件を経路探索条件設定部１１に設定する。
【００９４】
以降、上述の第１の実施の形態と同様、経路探索条件設定部１１は、まず設定された経路探索条件の出発地を目的地とし、全ての経由地について、経由地の滞在時間の設定を行い、経路探索条件として経路パターン算出部１２に通知する。
【００９５】
次に、経路パターン算出部１２は、出発地から目的地である出発地までに通過する全ての経由地について経由地群を構成し、構成した全ての経由地群について通過順序の組合せの算出を行い、算出した通過順序の組合せを経路探索部１３に通知する。
【００９６】
次に、経路探索部１３は、算出された経由地群の通過順序に従って経由地の通過順序を設定し、通過順序に従って経由地間の道路区間について、経由地の滞在時間を含んだ累計の所要時間より算出した道路区間入口の到達時刻に基づき、推定した交通状況に基づく道路区間の走行コストを算出し、算出した走行コストを用いて走行コストが最小となる経路を全ての通過順序の組合せについて経路探索する（Ｓ１２〜Ｓ２３）。
【００９７】
そして、経路探索部１３は、全ての組合せの経路の走行コストが最小の経路を選択し、経路探索結果として経路探索結果送信手段１１２に通知し、経路探索結果送信手段は受け取った経路探索結果を端末装置１００に送信する。
【００９８】
端末装置１００の経路探索結果受信手段１０２は、受信した経路探索結果を画面表示処理部１５に送信し、画面表示処理部１５で画面に表示する経路案内情報を生成し、画面表示手段３により、経路探索結果を画面に表示する。
【００９９】
このように本実施の形態においては、端末装置１００とセンタ装置１１０に機能を分けたので、端末装置１００を軽量化することができ、利便性を向上させることができる。
【産業上の利用可能性】
【０１００】
以上のように、本発明にかかる経路探索装置および経路探索システムは、経由地での滞在時間を確実に確保し、経由地での滞在時間による交通状況を推定する時刻のずれを防ぐことができるという効果を有し出発地から途中の経由地を経由し、元の出発地まで戻る移動経路において、途中の経由地の滞在時間と交通状況の時間変化を考慮し、推奨経路を提示する巡回経路探索装置および経路探索システム等として有用である。
【図面の簡単な説明】
【０１０１】
【図１】本発明の第１の実施の形態における経路探索装置のブロック図
【図２】本発明の第１の実施の形態における経路探索装置の経由地の施設情報の例を示す図
【図３】本発明の第１の実施の形態における経路探索装置の施設の種別毎の共通の設定の例を示す図
【図４】本発明の第１の実施の形態における経路探索装置の処理を説明するためのフローチャート
【図５】本発明の第１の実施の形態における経路探索装置の経由地の集約方法を説明するための図
【図６】本発明の第１の実施の形態における経路探索装置の経由地の滞在時間を考慮しなかった場合の例を示す図
【図７】本発明の第１の実施の形態における経路探索装置の経由地の滞在時間を考慮した場合の例を示す図
【図８】本発明の第１の実施の形態における経路探索装置の推定した交通状況から導いた道路区間での時刻毎の所要時間の例を示す図
【図９】本発明の第２の実施の形態における経路探索装置のブロック図
【図１０】本発明の第３の実施の形態における経路探索装置のブロック図
【図１１】本発明の第４の実施の形態における経路探索装置のブロック図
【図１２】本発明の第５の実施の形態における経路探索システムのブロック図
【符号の説明】
【０１０２】
１  経路探索手段
１１  経路探索条件設定部
１２  経路パターン算出部
１３  経路探索部
１４  交通状況推定部
１５  画面表示処理部
１６  経由地点情報蓄積データベース（ＤＢ）
１７  道路ネットワークデータベース（ＤＢ）
１８  交通情報蓄積データベース（ＤＢ）
２  経路探索条件入力手段
３  画面表示手段
４  経路探索手段
４１  経路探索条件設定部
４２  現在地算出部
５  車両センサ
５１  ＧＰＳ受信部
５２  角速度センサ
５３  車速センサ
６  経路探索手段
６１  経由地点情報蓄積ＤＢ
７  経由地点情報設定手段
８  経路探索手段
１００  端末装置
１０１  経路探索条件送信手段
１０２  経路探索結果受信手段
１０３  経路探索条件作成部
１１０  センタ装置
１１１  経路探索条件受信手段
１１２  経路探索結果送信手段
【図１】
2007218742.tif 000003
【図２】
2007218742.tif 000004
【図３】
2007218742.tif 000005
【図４】
2007218742.tif 000006
【図５】
2007218742.tif 000007
【図６】
2007218742.tif 000008
【図７】
2007218742.tif 000009
【図８】
2007218742.tif 000010
【図９】
2007218742.tif 000011
【図１０】
2007218742.tif 000012
【図１１】
2007218742.tif 000013
【図１２】
2007218742.tif 000014