(57)【要約】【課題】ユーザのスケジュールの遅れに応じて、経由地を削減または変更した新たな経路を探索する経路探索装置を提供する。【解決手段】経路探索装置１０は、現在位置から経由地を廻って目的地へ至る経路を探索するとともに、目的地への到着予定時刻を算出する経路探索部１４と、以下の第１の再探索指示部１５および第２の再探索指示部１６を備える。第１の再探索指示部１５は、目的地への到着予定時刻が到着希望時刻よりも遅い場合に、経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を経路探索部１４に再度実行させる。第２の再探索指示部１６は、ユーザが経由地から出発する際に、目的地への到着予定時刻を再計算し、再計算した到着予定時刻が到着希望時刻よりも遅い場合に、この後に廻る経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を経路探索部１４に再度実行させる。【選択図】図１
2020101424.tif 000002
【特許請求の範囲】
【請求項１】
現在位置周辺の立ち寄りスポットの一覧をユーザに提示する立ち寄りスポット提示部と、
前記ユーザの操作に従って前記立ち寄りスポットの一覧から１つ以上の経由地を選択する経由地選択部と、
前記ユーザの操作に従って目的地および当該目的地への到着希望時刻を設定する目的地設定部と、
現在位置から前記経由地を廻って前記目的地へ至る経路を探索するとともに、探索の結果得られた経路を辿った場合の前記目的地への到着予定時刻を算出する経路探索部と、
前記目的地への到着予定時刻が前記到着希望時刻よりも遅い場合に、前記経由地を減少または変更して、前記目的地への経路の探索および前記目的地への到着予定時刻の算出を前記経路探索部に再度実行させる第１の再探索指示部と、
前記ユーザが経由地から出発する際に前記目的地への到着予定時刻を再計算し、前記再計算した到着予定時刻が前記到着希望時刻よりも遅い場合に、この後に廻る経由地を減少または変更して、前記目的地への経路の探索および前記目的地への到着予定時刻の算出を前記経路探索部に再度実行させる第２の再探索指示部と、
前記経路探索部による探索の結果得られた経路を前記ユーザに提示する経路提示部と、
を備える経路探索装置。
【請求項２】
前記経路探索部は、可能な限り、前記目的地への到着予定時刻が前記到着希望時刻よりも遅くならないように、前記経由地を廻る順番を設定する、
請求項１に記載の経路探索装置。
【請求項３】
各立ち寄りスポットには、優先度が予め設定されており、
前記第１の再探索指示部および前記第２の再探索指示部は、優先度の低い立ち寄りスポットに対応する経由地から削除または変更する、
請求項１または請求項２に記載の経路探索装置。
【請求項４】
前記経由地として選択された立ち寄りスポットの優先度は、前記ユーザによって変更可能である、
請求項３に記載の経路探索装置。
【請求項５】
各立ち寄りスポットの優先度は、立ち寄りスポットの情報を配信するサービス提供者が過去の訪問者による評価または過去の訪問者の延べ人数に基づいて設定したものである、
請求項３または請求項４に記載の経路探索装置。
【請求項６】
前記ユーザが訪問した立ち寄りスポットの前記ユーザによる評価を前記サービス提供者へ送信するフィードバック情報送信部をさらに備える、
請求項５に記載の経路探索装置。
【請求項７】
各立ち寄りスポットには、予定滞在時間が予め設定されており、
前記経路探索部および前記第２の再探索指示部は、各立ち寄りスポットの予定滞在時間を考慮して、前記目的地への到着予定時刻を算出する、
請求項１から請求項６のいずれか一項に記載の経路探索装置。
【請求項８】
前記経由地として選択された立ち寄りスポットの予定滞在時間は、前記ユーザによって変更可能である、
請求項７に記載の経路探索装置。
【請求項９】
各立ち寄りスポットの予定滞在時間は、立ち寄りスポットの情報を配信するサービス提供者が過去の訪問者の滞在時間の統計に基づいて設定したものである、
請求項７または請求項８に記載の経路探索装置。
【請求項１０】
前記ユーザが訪問した立ち寄りスポットでの前記ユーザの滞在時間を前記サービス提供者へ送信するフィードバック情報送信部をさらに備える、
請求項９に記載の経路探索装置。
【請求項１１】
経路探索装置の立ち寄りスポット提示部が、現在位置周辺の立ち寄りスポットの一覧をユーザに提示し、
前記経路探索装置の経由地選択部が、前記ユーザの操作に従って前記立ち寄りスポットの一覧から１つ以上の経由地を選択し、
前記経路探索装置の目的地設定部が、前記ユーザの操作に従って目的地および当該目的地への到着希望時刻を設定し、
前記経路探索装置の経路探索部が、現在位置から前記経由地を廻って前記目的地へ至る経路を探索するとともに、探索の結果得られた経路を辿った場合の前記目的地への到着予定時刻を算出し、
前記目的地への到着予定時刻が前記到着希望時刻よりも遅い場合に、前記経路探索装置の第１の再探索指示部が、前記経由地を減少または変更して、前記目的地への経路の探索および前記目的地への到着予定時刻の算出を前記経路探索部に再度実行させ、
前記ユーザが経由地から出発する際に、前記経路探索装置の第２の再探索指示部が、前記目的地への到着予定時刻を再計算し、前記再計算した到着予定時刻が前記到着希望時刻よりも遅い場合に、この後に廻る経由地を減少または変更して、前記目的地への経路の探索および前記目的地への到着予定時刻の算出を前記経路探索部に再度実行させ、
前記経路探索装置の経路提示部が、前記経路探索部による探索の結果得られた経路を前記ユーザに提示する、
経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路探索装置および経路探索方法に関し、特に、複数の経由地を廻って目的地へ至る経路を探索する技術に関する。
【背景技術】
【０００２】
複数の経由地を廻って目的地へ至る経路を探索することが可能なナビゲーション装置が広く知られている。一般的なナビゲーション装置では、立ち寄る経由地の順番をユーザが設定する必要があるが、例えば、下記の特許文献１には、ユーザが経由地を廻ることができる時間を考慮して、経由地の順番を自動的に設定するルート探索装置が提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１１−８３５１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ナビゲーション装置のユーザが複数の経由地を廻る途中で、ある経由地に予定以上に長く滞在してスケジュールに遅れが生じた場合、その後に廻る経由地を減らしたり変更したりするなどして、経路を変更する必要が生じる。特許文献１のルート探索装置は、一旦設定した経由地を変更することは考慮されていない。
【０００５】
本発明は以上のような課題を解決するためになされたものであり、ユーザのスケジュールの遅れに応じて、経由地を削減または変更した新たな経路を探索する経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る経路探索装置は、現在位置周辺の立ち寄りスポットの一覧をユーザに提示する立ち寄りスポット提示部と、ユーザの操作に従って立ち寄りスポットの一覧から１つ以上の経由地を選択する経由地選択部と、ユーザの操作に従って目的地および当該目的地への到着希望時刻を設定する目的地設定部と、現在位置から経由地を廻って目的地へ至る経路を探索するとともに、探索の結果得られた経路を辿った場合の目的地への到着予定時刻を算出する経路探索部と、目的地への到着予定時刻が到着希望時刻よりも遅い場合に、経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を経路探索部に再度実行させる第１の再探索指示部と、ユーザが経由地から出発する際に目的地への到着予定時刻を再計算し、再計算した到着予定時刻が到着希望時刻よりも遅い場合に、この後に廻る経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を経路探索部に再度実行させる第２の再探索指示部と、経路探索部による探索の結果得られた経路をユーザに提示する経路提示部と、を備える。
【発明の効果】
【０００７】
本発明によれば、ユーザのスケジュールに遅れが生じた場合に、目的地への到着予定時刻が到着希望時刻よりも遅くならない新たな経路が提示されるため、ユーザが目的地へ遅れて到着することを防止できる。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１に係るナビゲーションシステムの構成を示す図である。
【図２】実施の形態１に係るナビゲーション装置の動作を説明するための図である。
【図３】実施の形態１に係るナビゲーション装置の動作を説明するための図である。
【図４】実施の形態１に係るナビゲーション装置の動作を説明するための図である。
【図５】実施の形態１に係るナビゲーション装置の動作を説明するための図である。
【図６】実施の形態１に係るナビゲーション装置の動作を説明するための図である。
【図７】実施の形態１に係るナビゲーション装置の動作を説明するための図である。
【図８】実施の形態１に係るナビゲーション装置の動作を説明するための図である。
【図９】実施の形態１に係るナビゲーション装置の動作を説明するための図である。
【図１０】実施の形態１に係るナビゲーション装置の動作を示すフローチャートである。
【図１１】第１の経路探索処理を示すフローチャートである。
【図１２】経路案内処理を示すフローチャートである。
【図１３】第２の経路探索処理を示すフローチャートである。
【図１４】経路探索装置のハードウェア構成例を示す図である。
【図１５】経路探索装置のハードウェア構成例を示す図である。
【図１６】実施の形態２に係るナビゲーションシステムの構成を示す図である。
【発明を実施するための形態】
【０００９】
＜実施の形態１＞
図１は、実施の形態１に係るナビゲーションシステムの構成を示す図である。本実施の形態では、ナビゲーションシステムは車両に搭載されているものと仮定し、当該ナビゲーションシステムを搭載した車両を「自車両」といい、自車両の現在位置はユーザの現在位置とみなされる。ただし、ナビゲーションシステムは車両用でなくてもよく、歩行者用のものでもよい。
【００１０】
図１のように、実施の形態１に係るナビゲーションシステムは、ナビゲーション装置１と、それに接続された表示装置２、操作入力装置３、現在位置算出装置４、地図情報記憶装置５および通信装置６とを備えている。
【００１１】
ナビゲーション装置１は、自車両の現在位置から目的地までの経路を探索し、探索の結果得られた経路に沿って自車両を走行させるように、ユーザである自車両の運転者に対する経路案内を行う。後述するように、ナビゲーション装置１は、１つ以上の経由地を廻って目的地へ至る経路を探索する機能を有している。
【００１２】
表示装置２は、ナビゲーション装置１がユーザに情報を提示するためのユーザインターフェイスであり、例えば液晶表示装置などで構成される。操作入力装置３は、ユーザがナビゲーション装置１に対する操作を行うためのユーザインターフェイスである。操作入力装置３は、キーボードや押しボタン、操作レバー、タッチパッドのようなハードウェアであってもよいし、画面に表示されるソフトウェアキーであってもよい。操作入力装置３としてのソフトウェアキーを、表示装置２に表示させてもよく、その場合、表示装置２および操作入力装置３は１つのタッチパネルとして構成される。
【００１３】
現在位置算出装置４は、例えばＧＰＳ（Global Positioning System）衛星などのＧＮＳＳ（Global Navigation Satellite System）衛星から受信した測位信号を用いて、自車両の現在位置を算出する。地図情報記憶装置５は、地図情報が記憶された記憶媒体である。地図情報記憶装置５に記憶された地図情報には、道路網のデータの他、観光地や商業施設等の立ち寄りスポットの位置データなどが含まれている。通信装置６は、ナビゲーション装置１が、外部との通信を行うための通信手段である。通信装置６は、専用の通信機でもよいし、携帯電話やスマートフォンなど一般的な通信機でもよい。また、地図情報記憶装置５は、通信装置６を通してナビゲーション装置１に地図情報を配信するサーバであってもよい。
【００１４】
本実施の形態では、立ち寄りスポットの情報を配信するサーバを提供するサービス提供者（例えば地図情報や交通情報の配信業者など）が存在するものと仮定し、通信装置６は、当該サーバから、立ち寄りスポットの情報を取得できるものとする。また、サーバから配信される立ち寄りスポットの情報には、各立ち寄りスポットの優先度および予定滞在時間の情報が含まれるものとする。
【００１５】
立ち寄りスポットの優先度は、立ち寄りスポットの過去の訪問者による評価または過去の訪問者の延べ人数から判断される人気度に基づいて、サービス提供者により設定され、人気度の高い立ち寄りスポットには高い優先度が付されている。立ち寄りスポットの予定滞在時間は、過去の訪問者の滞在時間の統計（例えば平均値）に基づいて、サービス提供者により設定される。
【００１６】
図１では、ナビゲーション装置１、表示装置２、操作入力装置３、現在位置算出装置４、地図情報記憶装置５および通信装置６を、それぞれ個別の装置として示したが、それらの２つ以上が一体的に構成されてもよい。例えば、図１のナビゲーションシステムが、歩行者用のシステムや携帯型のシステムである場合、それら全てが１つの筐体に収められることが好ましい。
【００１７】
次に、ナビゲーション装置１の構成の詳細を説明する。図１のように、ナビゲーション装置１は、経路探索装置１０、表示処理部２０および案内処理部３０を備えている。
【００１８】
経路探索装置１０は、自車両の現在位置から目的地までの経路を探索し、探索の結果得られた経路を案内経路（自車両の走行予定経路）として設定する。経路探索装置１０は、１つ以上の経由地を廻って目的地へ至る経路を探索する機能を有している。
【００１９】
表示処理部２０は、経路探索装置１０および表示処理部２０から提供される情報に基づいて経路探索装置１０の操作画面を作成し、作成した操作画面を表示装置２に表示させる処理を行う。
【００２０】
案内処理部３０は、現在位置算出装置４が算出した自車両の現在位置および経路探索装置１０が設定した案内経路に基づき、自車両を案内経路に沿って走行させるように、運転者に対する経路案内を行う。具体的には、案内処理部３０は、表示処理部２０を通して、案内経路を示す地図を表示装置２に表示したり、自車両内のスピーカ（不図示）を通して、道路の交差点や分岐点での進行方向を指示する音声を出力したりする。
【００２１】
経路探索装置１０は、図１のように、立ち寄りスポット提示部１１、経由地選択部１２、目的地設定部１３、経路探索部１４、第１の再探索指示部１５、第２の再探索指示部１６および経路提示部１７を備えている。
【００２２】
立ち寄りスポット提示部１１は、自車両の現在位置周辺の立ち寄りスポットの一覧をユーザに提示する。具体的には、立ち寄りスポット提示部１１は、通信装置６を用いて、立ち寄りスポットの情報を配信する外部のサーバとの通信を行い、当該サーバから、現在位置算出装置４が算出した自車両の現在位置の周辺に存在する立ち寄りスポットの情報を取得する。そして、立ち寄りスポット提示部１１は、表示処理部２０を通して、自車両の現在位置の周辺に存在する立ち寄りスポットの一覧を表示装置２に表示することで、ユーザに提示する。
【００２３】
ユーザは、操作入力装置３を操作することにより、表示装置２に表示された立ち寄りスポットの一覧から、１つ以上の立ち寄りスポットを選択できる。経由地選択部１２は、ユーザが選択した立ち寄りスポットを、経由地として選択する。
【００２４】
また、ユーザは、操作入力装置３を操作することにより、最終的な目的地およびその目的地への到着希望時刻を入力できる。目的地設定部１３は、ユーザが入力した目的地および到着希望時刻の情報を経路探索部１４に設定する。
【００２５】
経路探索部１４は、現在位置から、経由地選択部１２により選択された経由地を廻って、目的地設定部１３により設定された目的地へ至る経路を探索する。そのとき、経路探索部１４は、探索の結果得られた経路を辿った場合の目的地への到着予定時刻を算出する。
【００２６】
第１の再探索指示部１５および第２の再探索指示部１６は、経路探索部１４に、目的地への経路の探索および目的地への到着予定時刻の算出の再実行（やり直し）を指示するものである。
【００２７】
第１の再探索指示部１５は、ユーザが経由地、目的地、目的地への到着時刻を入力した直後（案内経路が確定する前）に動作する。具体的には、第１の再探索指示部１５は、経路探索部１４が算出した目的地への到着予定時刻と、目的地設定部１３が設定した到着希望時刻とを比較し、到着予定時刻が到着希望時刻よりも遅い場合に、経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を経路探索部１４に再度実行させる。
【００２８】
第２の再探索指示部１６は、ユーザが経由地を出発する際に動作する。具体的には、第２の再探索指示部１６は、ユーザが経由地から出発する際に目的地への到着予定時刻を再計算し、再計算した到着予定時刻が到着希望時刻よりも遅い場合に、その後に廻る経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を経路探索部１４に再度実行させる。
【００２９】
経路提示部１７は、経路探索部１４による探索の結果得られた経路を、案内経路としてユーザに提示する。具体的には、経路提示部１７は、表示処理部２０を通して、案内経路を表示装置２に表示させる。ただし、第１の再探索指示部１５または第２の再探索指示部１６の指示によって経路探索部１４が経路の探索を再実行した場合には、経路提示部１７は、再実行の結果得られた経路を案内経路としてユーザに提示する。
【００３０】
次に、ナビゲーション装置１の動作を、図２〜図９を用いて具体的に説明する。図２〜図９は、ナビゲーション装置１の表示処理部２０が表示装置２に表示させる操作画面４０の例である。本実施の形態の操作画面４０には、自車両周辺の地図が表示される地図表示領域４１と、立ち寄りスポットの一覧が表示される立ち寄りスポット一覧表示領域４２と、案内経路に含まれる経由地（立ち寄りスポット）の立ち寄り計画が表示される立ち寄り計画表示領域４３とが含まれている。
【００３１】
なお、表示装置２に操作画面４０を表示する処理は表示処理部２０によって行われるが、以下では説明の簡単のため、例えば、「立ち寄りスポット提示部１１が立ち寄りスポット一覧を立ち寄りスポット一覧表示領域４２に表示する」、「経路提示部１７が案内経路を地図表示領域４１に表示する」などと表現する場合もある。
【００３２】
ユーザ（自車両の運転者）がナビゲーション装置１を起動させ、ナビゲーション装置１に経路の設定を命じると、経路探索装置１０が起動する。経路探索装置１０では、まず、立ち寄りスポット提示部１１が、図２のように、自車両の現在位置から一定距離内に存在する立ち寄りスポットの一覧を、立ち寄りスポット一覧表示領域４２に表示する。ここでは、立ち寄りスポットの一覧には、各立ち寄りスポットの予定滞在時間の情報も含まれている。また、立ち寄りスポット提示部１１は、各立ち寄りスポットの位置を示すアイコン（丸付き数字）を、地図表示領域４１の地図上に表示する。なお、地図表示領域４１の地図上の黒い丸は自車両の現在位置を示しており、それを中心とする点線の円は、立ち寄りスポット提示部１１が立ち寄りスポットを検索する範囲（自車両の現在位置から一定距離内の範囲）を示している。上記「一定距離」の大きさをユーザが変更できるようにしてもよい。
【００３３】
ユーザは、操作入力装置３を操作して、表示装置２に表示された立ち寄りスポットの一覧から、１つ以上の立ち寄りスポットを選択できる。ユーザが選択した立ち寄りスポットは、経由地選択部１２により、経由地として選択される。ここでは、図３のように、Ａ神社、Ｃ動物園、Ｄ水族館、Ｅ美術館およびＧ広場が、ユーザによって選択されたものとする。
【００３４】
このとき、ユーザが、経由地として選択した立ち寄りスポットの優先度を、好みに応じて変更できるようにしてもよい。本実施の形態では、ユーザが、立ち寄りを強く希望する立ち寄りスポットを指定でき、指定された立ち寄りスポットの優先度が最も高く設定されるものとする。ここでは、図４のように、Ｅ美術館が、立ち寄りを強く希望する立ち寄りスポットとして指定されたものとする。
【００３５】
また、ユーザが、経由地として選択した立ち寄りスポットの予定滞在時間を、好みに応じて変更できるようにしてもよい。ここでは、図５のように、Ｅ美術館の予定滞在時間が、ユーザによって６０分から９０分に変更されたものとする。
【００３６】
また、ユーザは、操作入力装置３を操作することにより、最終的な目的地およびその目的地への到着希望時刻を入力できる。ユーザにより入力された目的地および到着希望時刻は、目的地設定部１３によって経路探索部１４に設定する。ここでは、図６のように、Ｘホテルが目的地として設定され、その到着希望時刻が１９時と設定されたものとする。
【００３７】
経由地とする立ち寄りスポット、目的地および目的地への到着予定時刻が設定されると、経路探索部１４は、自車両の現在位置から経由地を廻って目的地へ至る経路を探索するとともに、探索の結果得られた経路を辿った場合の目的地への到着予定時刻を算出する。目的地への到着予定時刻を算出は、経由地間もしくは経由地と目的地との間の移動時間だけでなく、経由地である立ち寄りスポットの予定滞在時間を考慮して行われる。
【００３８】
なお、経由地が複数ある場合、それらの立ち寄り順は経路探索部１４によって自動的に設定される。経路探索部１４は、可能な限り、目的地への到着予定時刻が到着希望時刻よりも遅くならないように、経由地を廻る順番を設定する。経由地の順番を設定する方法としては、例えば、目的地への到着予定時刻が最も早くなるように経由地の順番を設定する方法や、経由地の順番を現在位置から近い順に並べる方法などが考えられる。
【００３９】
経路探索部１４による経路探索が完了すると、第１の再探索指示部１５は、目的地への到着予定時刻と到着希望時刻とを比較し、到着予定時刻が到着希望時刻よりも遅い場合に、経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を経路探索部１４に再度実行させる。このとき、優先度の高い立ち寄りスポットが、可能な限り経由地から外れないように、経由地の減少または変更は、優先度の低い立ち寄りスポットに対応する経由地から行われる。この第１の再探索指示部１５の処理は、到着予定時刻が到着希望時刻よりも早くなるまで、または、経由地の数が０になるまで行われる。
【００４０】
ここでは、ユーザが経由地として選択した立ち寄りスポットの全てを廻る経路では、Ｘホテルへの到着予定時刻が到着希望時刻よりも遅くなると判断され、第１の再探索指示部１５が経路探索部１４に経路の再探索を行わせた結果、図７のように、Ａ神社およびＧ広場が経由地から外された経路（Ｅ美術館、Ｃ動物園およびＤ水族館を廻ってＸホテルに至る経路）が得られたものとする。
【００４１】
経路提示部１７は、経路探索部１４による探索（または再探索）の結果得られた経路を、案内経路として表示装置２に表示させる。本実施の形態の経路提示部１７は、図７のように、案内経路を地図表示領域４１の地図上に表示するとともに、経由地（立ち寄りスポット）の立ち寄り順および到着予定時刻を含む経由地の立ち寄り計画を、立ち寄り計画表示領域４３に表示する。
【００４２】
ユーザが自車両を走行させて移動を開始すると、案内処理部３０が、ユーザに対し、自車両を案内経路に沿って走行させるための経路案内を行う。
【００４３】
ユーザが経由地へ到着し、その後、当該経由地を出発しようとすると、第２の再探索指示部１６が起動し、目的地への到着予定時刻を再計算して、再計算した到着予定時刻と到着希望時刻とを比較する。ここでも、目的地への到着予定時刻を算出は、各立ち寄りスポットの予定滞在時間を考慮して行われる。
【００４４】
例えば、渋滞などでユーザが経由地に到着するのが遅れた場合や、ユーザが経由地に予定滞在時間よりも長く滞在した場合などには、到着予定時刻が到着希望時刻よりも遅くなる。第２の再探索指示部１６は、到着予定時刻が到着希望時刻よりも遅いと判断すると、この後に廻る経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を経路探索部１４に再度実行させる。このとき、優先度の高い立ち寄りスポットが、可能な限り経由地から外れないように、経由地の減少または変更は、優先度の低い立ち寄りスポットに対応する経由地から行われる。この第２の再探索指示部１６の処理は、到着予定時刻が到着希望時刻よりも早くなるまで、または、経由地の数が０になるまで行われる。
【００４５】
経路提示部１７は、経路探索部１４による再探索の結果得られた経路を、案内経路として表示装置２に表示させる。
【００４６】
例えば、図７に示した案内経路に従ってＥ美術館に立ち寄ったユーザがＥ美術館に長く滞在し、Ｘホテルへの到着予定時刻が到着希望時刻よりも遅くなると判断されると、経路探索部１４による経路の再探索が実行される。その結果、例えば図８のように、経由地の１つがＣ動物園からＧ広場に変更されて、Ｘホテルへの到着予定時刻が早められた経路（Ｅ美術館からＤ水族館およびＧ広場を廻ってＸホテルに至る経路）が得られる。
【００４７】
さらに、例えば、図８に示した案内経路に従ってＤ水族館に立ち寄ったユーザがＤ水族館に長く滞在し、Ｘホテルへの到着予定時刻が到着希望時刻よりも遅くなると判断されると、再度、経路探索部１４による経路の再探索が実行される。その結果、例えば図９のように、最後の経由地であるＧ広場が経由地から外されて、Ｘホテルへの到着予定時刻が早められた経路（Ｄ水族館からＸホテルへ直接向かう経路）が得られる。
【００４８】
そして、自車両が目的地であるＸホテルへ到着すると、案内処理部３０による経路案内が完了し、ナビゲーション装置１の動作が終了する。
【００４９】
次に、図１０〜図１３のフローチャートを用いて、ナビゲーション装置１の動作を説明する。図２〜図９を用いて説明したナビゲーション装置１の動作は、ナビゲーション装置１が図１０〜図１３の処理を実行することによって実現される。
【００５０】
ユーザ（自車両の運転者）がナビゲーション装置１に経路の設定を命じると、経路探索装置１０が起動し、図１０のフローが開始される。まず、立ち寄りスポット提示部１１が、通信装置６を用いて外部のサーバから立ち寄りスポット情報を取得し（ステップＳ１０１）、立ち寄りスポットの一覧を表示処理部２０に表示してユーザに提示する（ステップＳ１０２）。次に、経由地選択部１２が、ユーザの操作に従い、立ち寄りスポットの一覧から経由地を選択する（ステップＳ１０３）。また、目的地設定部１３が、ユーザの操作に従い、目的地およびその目的地への到着希望時刻を設定する（ステップＳ１０４）。その後、図１１に示す「第１の経路探索処理」が実行される（ステップＳ１０５）。
【００５１】
第１の経路探索処理では、まず、経路探索部１４が、全ての経由地を廻って目的地へ至る経路を求める経路探索を実施する（ステップＳ２０１）。このとき経路探索部１４は、探索の結果得られた経路を辿った場合の目的地への到着予定時刻も算出する。
【００５２】
次に、第１の再探索指示部１５が、ステップＳ２０１で得られた経路の目的地への到着予定時刻が到着希望時刻よりも遅いか否かを判断する（ステップＳ２０２）。目的地への到着予定時刻が到着希望時刻よりも早ければ（ステップＳ２０２でＮＯ）、経路提示部１７がその経路を案内経路として採用し、当該案内経路を表示処理部２０に表示することでユーザに提示して（ステップＳ２０３）、第１の経路探索処理は終了する。
【００５３】
目的地への到着予定時刻が到着希望時刻よりも遅ければ（ステップＳ２０２でＹＥＳ）、第１の再探索指示部１５が、経由地の数を確認する（ステップＳ２０４）。経由地の数が０個であれば（ステップＳ２０４でＹＥＳ）、経由地を削減または変更する余地がないため、経路提示部１７が、直前に経路探索部１４が求めた経路を案内経路として採用し、当該案内経路をユーザに提示して（ステップＳ２０３）、第１の経路探索処理は終了する。
【００５４】
経由地の数が１個以上あれば（ステップＳ２０４でＮＯ）、第１の再探索指示部１５が、経由地から優先度の低い立ち寄りスポットを１つ暫定的に削除して（以下、暫定的な削除を「仮削除」という）、経路探索部１４に経路探索を再度実施させる（ステップＳ２０５）。このとき経路探索部１４は、探索の結果得られた経路を辿った場合の目的地への到着予定時刻も算出する。
【００５５】
その後、第１の再探索指示部１５は、ステップＳ２０５で得られた経路の目的地への到着予定時刻が到着希望時刻よりも遅いか否かを判断する（ステップＳ２０６）。目的地への到着予定時刻が到着希望時刻よりも早ければ（ステップＳ２０６でＮＯ）、経路提示部１７がその経路を案内経路として採用し、当該案内経路をユーザに提示して（ステップＳ２０３）、第１の経路探索処理は終了する。
【００５６】
目的地への到着予定時刻が到着希望時刻よりも遅ければ（ステップＳ２０６でＹＥＳ）、第１の再探索指示部１５は、経由地から仮削除する立ち寄りスポットを変更して、経路探索部１４に経路探索を再度実施させる（ステップＳ２０７）。
【００５７】
その後、第１の再探索指示部１５は、ステップＳ２０７で得られた経路の目的地への到着予定時刻が到着希望時刻よりも遅いか否かを判断する（ステップＳ２０８）。目的地への到着予定時刻が到着希望時刻よりも早ければ（ステップＳ２０８でＮＯ）、経路提示部１７がその経路を案内経路として採用し、当該案内経路をユーザに提示して（ステップＳ２０３）、第１の経路探索処理は終了する。
【００５８】
目的地への到着予定時刻が到着希望時刻よりも遅ければ（ステップＳ２０８でＹＥＳ）。第１の再探索指示部１５は、全ての経由地について仮削除を試したか否かを確認する（ステップＳ２０９）。仮削除を試していない経由地が残っていれば（ステップＳ２０９でＮＯ）、ステップＳ２０７へ戻り、経由地から仮削除する立ち寄りスポットを変更して、再度、経路探索部１４による経路探索が実施される。
【００５９】
全ての経由地についての仮削除が試されていれば（ステップＳ２０９でＹＥＳ）、第１の再探索指示部１５が、経由地から優先度の低い立ち寄りスポットを１つ正式に削除して（ステップＳ２１０）、ステップＳ２０４へ戻る。
【００６０】
以上の処理は、目的地への到着予定時刻が到着希望時刻よりも早くなる経路が見つかるまで、または、経由地の数が０になるまで行われる。
【００６１】
図１０に戻り、第１の経路探索処理（ステップＳ１０５）が完了すると、図１２に示す「経路案内処理」が実行される（ステップＳ１０６）。
【００６２】
経路案内処理では、まず、案内処理部３０が、経路探索装置１０で求められた案内経路に基づいて、経由地または目的地への経路案内を実施する（ステップＳ３０１）。その後、案内処理部３０は、現在位置算出装置４が算出した自車両の現在位置に基づいて、ユーザ（自車両）が目的地または経由地に到着したか否かを判断する（ステップＳ３０２，Ｓ３０３）。ユーザが目的地へ到着すれば（ステップＳ３０２でＹＥＳ）、経路案内処理は終了する。ユーザが目的地にも経由地にも到着していなければ（ステップＳ３０２，Ｓ３０３の両方でＮＯ）、ステップＳ３０１へ戻る。
【００６３】
ユーザが経由地に到着した場合（ステップＳ３０２ＮＯ、ステップＳ３０３でＹＥＳ）、第２の再探索指示部１６は、ユーザがその経由地から出発するまで待機する（ステップＳ３０４）。第２の再探索指示部１６は、ユーザが経由地から出発すると判断すると（ステップＳ３０４でＹＥＳ）、現在時刻に基づき目的地への到着予定時刻を再計算する（ステップＳ３０５）。なお、ユーザが経由地を出発するか否かの判断は、例えば、自車両が経由地から移動したか否かによって判断してもよいが、ユーザが経由地を実際に出発する前に、出発することを検知できることが好ましい。例えば、経由地に駐車された自車両が再起動されたときに、ユーザが経由地を出発すると判断してもよい。また、ユーザが、経由地を出発する際に、手動でステップＳ３０４からステップＳ３０５へ移行させることを可能にしてもよい。
【００６４】
第２の再探索指示部１６は、再計算した到着予定時刻が到着希望時刻よりも遅いか否かを確認する（ステップＳ３０６）。再計算した到着予定時刻が到着希望時刻よりも早ければ（ステップＳ３０６でＮＯ）、現状の案内経路を維持したままステップＳ３０１へと戻る。
【００６５】
再計算した到着予定時刻が到着希望時刻よりも遅ければ（ステップＳ３０６）、図１３に示す「第２の経路探索処理」が実行される（ステップＳ３０７）。
【００６６】
第２の経路探索処理では、まず、第２の再探索指示部１６が、経由地から既に廻った立ち寄りスポットを削除する（ステップＳ４０１）。このとき残った経由地は、これから廻る予定の経由地である。
【００６７】
そして、第２の再探索指示部１６は、残った経由地の数を確認する（ステップＳ４０２）。経由地の数が０個であれば（ステップＳ４０２でＹＥＳ）、経由地を削減または変更する余地がないため、現状の案内経路を維持して（ステップＳ４０３）、第２の経路探索処理は終了する。
【００６８】
経由地の数が１個以上あれば（ステップＳ４０２でＮＯ）、第２の再探索指示部１６は、経由地から優先度の低い立ち寄りスポットを１つ仮削除して、経路探索部１４に経路探索を再度実施させる（ステップＳ４０４）。このとき経路探索部１４は、探索の結果得られた経路を辿った場合の目的地への到着予定時刻も算出する。
【００６９】
その後、第２の再探索指示部１６は、ステップＳ４０４で得られた経路の目的地への到着予定時刻が到着希望時刻よりも遅いか否かを判断する（ステップＳ４０５）。目的地への到着予定時刻が到着希望時刻よりも早ければ（ステップＳ４０５でＮＯ）、経路提示部１７がその経路を案内経路として採用し、当該案内経路をユーザに提示して（ステップＳ４０６）、第２の経路探索処理は終了する。
【００７０】
目的地への到着予定時刻が到着希望時刻よりも遅ければ（ステップＳ４０５でＹＥＳ）、第２の再探索指示部１６は、経由地から仮削除する立ち寄りスポットを変更して、経路探索部１４に経路探索を再度実施させる（ステップＳ４０７）。
【００７１】
その後、第２の再探索指示部１６は、ステップＳ４０７で得られた経路の目的地への到着予定時刻が到着希望時刻よりも遅いか否かを判断する（ステップＳ４０８）。目的地への到着予定時刻が到着希望時刻よりも早ければ（ステップＳ４０８でＮＯ）、経路提示部１７がその経路を案内経路として採用し、当該案内経路をユーザに提示して（ステップＳ４０６）、第２の経路探索処理は終了する。
【００７２】
目的地への到着予定時刻が到着希望時刻よりも遅ければ（ステップＳ４０８でＹＥＳ）。第２の再探索指示部１６は、全ての経由地について仮削除を試したか否かを確認する（ステップＳ４０９）。仮削除を試していない経由地が残っていれば（ステップＳ４０９でＮＯ）、ステップＳ４０７へ戻り、経由地から仮削除する立ち寄りスポットを変更して、再度、経路探索部１４による経路探索が実施される。
【００７３】
全ての経由地についての仮削除が試されていれば（ステップＳ４０９でＹＥＳ）、第２の再探索指示部１６が、経由地から優先度の低い立ち寄りスポットを１つ正式に削除する（ステップＳ４１０）。
【００７４】
そして、第２の再探索指示部１６は、残った経由地の数を確認する（ステップＳ４１１）。経由地の数が１個以上あれば（ステップＳ４１１でＮＯ）、ステップＳ４０７へ戻る。経由地の数が０個であれば（ステップＳ４１１でＹＥＳ）、経由地を削減または変更する余地がないため、経路提示部１７が、直前に経路探索部１４が求めた経路を案内経路として採用し、当該案内経路をユーザに提示して（ステップＳ４０６）、第２の経路探索処理は終了する。
【００７５】
図１２に戻り、第２の経路探索処理（ステップＳ３０７）が完了すると、経路案内処理のステップＳ３０１へ移行する。
【００７６】
本実施の形態に係る経路探索装置１０によれば、ユーザのスケジュールに遅れが生じ、目的地への到着予定時刻が到着希望時刻よりも遅くなると判断されると、目的地への到着予定時刻が到着希望時刻よりも遅くならない新たな案内経路が提示されるため、ユーザが目的地へ遅れて到着することを防止できる。
【００７７】
図１４および図１５は、それぞれ経路探索装置１０のハードウェア構成の例を示す図である。図１に示した経路探索装置１０の構成要素の各機能は、例えば図１４に示す処理回路５０により実現される。すなわち、経路探索装置１０は、現在位置周辺の立ち寄りスポットの一覧をユーザに提示し、ユーザの操作に従って立ち寄りスポットの一覧から１つ以上の経由地を選択し、ユーザの操作に従って目的地および当該目的地への到着希望時刻を設定し、現在位置から経由地を廻って目的地へ至る経路を探索するとともに、探索の結果得られた経路を辿った場合の目的地への到着予定時刻を算出し、目的地への到着予定時刻が到着希望時刻よりも遅い場合に、経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を再度実行し、ユーザが経由地から出発する際に、目的地への到着予定時刻を再計算し、再計算した到着予定時刻が到着希望時刻よりも遅い場合に、この後に廻る経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を再度実行し、探索の結果得られた経路をユーザに提示するための処理回路５０を備える。処理回路５０は、専用のハードウェアであってもよいし、メモリに格納されたプログラムを実行するプロセッサ（中央処理装置（ＣＰＵ：Central Processing Unit）、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、ＤＳＰ（Digital Signal Processor）とも呼ばれる）を用いて構成されていてもよい。
【００７８】
処理回路５０が専用のハードウェアである場合、処理回路５０は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field-Programmable Gate Array）、またはこれらを組み合わせたものなどが該当する。経路探索装置１０の構成要素の各々の機能が個別の処理回路で実現されてもよいし、それらの機能がまとめて一つの処理回路で実現されてもよい。
【００７９】
図１５は、処理回路５０がプログラムを実行するプロセッサ５１を用いて構成されている場合における経路探索装置１０のハードウェア構成の例を示している。この場合、経路探索装置１０の構成要素の機能は、ソフトウェア等（ソフトウェア、ファームウェア、またはソフトウェアとファームウェアとの組み合わせ）により実現される。ソフトウェア等はプログラムとして記述され、メモリ５２に格納される。プロセッサ５１は、メモリ５２に記憶されたプログラムを読み出して実行することにより、各部の機能を実現する。すなわち、経路探索装置１０は、プロセッサ５１により実行されるときに、現在位置周辺の立ち寄りスポットの一覧をユーザに提示する処理と、ユーザの操作に従って立ち寄りスポットの一覧から１つ以上の経由地を選択する処理と、ユーザの操作に従って目的地および当該目的地への到着希望時刻を設定する処理と、現在位置から経由地を廻って目的地へ至る経路を探索するとともに、探索の結果得られた経路を辿った場合の目的地への到着予定時刻を算出する処理と、目的地への到着予定時刻が到着希望時刻よりも遅い場合に、経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を再度実行する処理と、ユーザが経由地から出発する際に、目的地への到着予定時刻を再計算し、再計算した到着予定時刻が到着希望時刻よりも遅い場合に、この後に廻る経由地を減少または変更して、目的地への経路の探索および目的地への到着予定時刻の算出を再度実行する処理と、探索の結果得られた経路をユーザに提示する処理と、が結果的に実行されることになるプログラムを格納するためのメモリ５２を備える。換言すれば、このプログラムは、経路探索装置１０の構成要素の動作の手順や方法をコンピュータに実行させるものであるともいえる。
【００８０】
ここで、メモリ５２は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリー、ＥＰＲＯＭ（Erasable Programmable Read Only Memory）、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）などの、不揮発性または揮発性の半導体メモリ、ＨＤＤ（Hard Disk Drive）、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ（Digital Versatile Disc）およびそのドライブ装置等、または、今後使用されるあらゆる記憶媒体であってもよい。
【００８１】
以上、経路探索装置１０の構成要素の機能が、ハードウェアおよびソフトウェア等のいずれか一方で実現される構成について説明した。しかしこれに限ったものではなく、経路探索装置１０の一部の構成要素を専用のハードウェアで実現し、別の一部の構成要素をソフトウェア等で実現する構成であってもよい。例えば、一部の構成要素については専用のハードウェアとしての処理回路５０でその機能を実現し、他の一部の構成要素についてはプロセッサ５１としての処理回路５０がメモリ５２に格納されたプログラムを読み出して実行することによってその機能を実現することが可能である。
【００８２】
以上のように、経路探索装置１０は、ハードウェア、ソフトウェア等、またはこれらの組み合わせによって、上述の各機能を実現することができる。
【００８３】
＜実施の形態２＞
実施の形態１において、立ち寄りスポットの優先度は、立ち寄りスポットの過去の訪問者による評価または過去の訪問者の延べ人数から判断される人気度に基づいて、サービス提供者により設定されたものである。また、立ち寄りスポットの予定滞在時間は、立ち寄りスポットの過去の訪問者の滞在時間の統計（例えば平均値）に基づいて、サービス提供者により設定されたものである。実施の形態２では、立ち寄りスポットのユーザの評価、および、立ち寄りスポットでのユーザの滞在時間を、サービス提供者へフィードバック可能なナビゲーション装置１を提案する。
【００８４】
図１６は、実施の形態２に係るナビゲーション装置１の構成を示す図である。図１６のナビゲーション装置１の構成は、図１に構成に対し、経路探索装置１０にフィードバック情報送信部１８を追加したものである。
【００８５】
フィードバック情報送信部１８は、通信装置６を用いて、ナビゲーション装置１のユーザが訪問した立ち寄りスポットの当該ユーザによる評価、および、ユーザが訪問した立ち寄りスポットでのユーザの滞在時間を、サービス提供者へ送信する。立ち寄りスポットの評価は、ユーザが操作入力装置３を用いて入力することができる。また、立ち寄りスポットでのユーザの滞在時間は、ユーザが操作入力装置３を用いて入力してもよいし、図１２の経路案内処理のステップＳ３０３でＹＥＳと判断されてから、ステップＳ３０４でＹＥＳと判断されるまでの時間を計測して求めてもよい。
【００８６】
本実施の形態によれば、立ち寄りスポットのユーザの評価、および、立ち寄りスポットでのユーザの滞在時間をサービス提供者へフィードバックできるため、サービス提供者が配信する情報の信頼性の向上に寄与できる。
【００８７】
なお、本発明は、その発明の範囲内において、各実施の形態を自由に組み合わせたり、各実施の形態を適宜、変形、省略したりすることが可能である。
【符号の説明】
【００８８】
１  ナビゲーション装置、２  表示装置、３  操作入力装置、４  現在位置算出装置、５  地図情報記憶装置、６  通信装置、１０  経路探索装置、１１  立ち寄りスポット提示部、１２  経由地選択部、１３  目的地設定部、１４  経路探索部、１５  第１の再探索指示部、１６  第２の再探索指示部、１７  経路提示部、１８  フィードバック情報送信部、２０  表示処理部、３０  案内処理部、４０  操作画面、４１  地図表示領域、４２  立ち寄りスポット一覧表示領域、４３  立ち寄り計画表示領域、５０  処理回路、５１  プロセッサ、５２  メモリ。
【図１】
2020101424.tif 000003
【図２】
2020101424.tif 000004
【図３】
2020101424.tif 000005
【図４】
2020101424.tif 000006
【図５】
2020101424.tif 000007
【図６】
2020101424.tif 000008
【図７】
2020101424.tif 000009
【図８】
2020101424.tif 000010
【図９】
2020101424.tif 000011
【図１０】
2020101424.tif 000012
【図１１】
2020101424.tif 000013
【図１２】
2020101424.tif 000014
【図１３】
2020101424.tif 000015
【図１４】
2020101424.tif 000016
【図１５】
2020101424.tif 000017
【図１６】
2020101424.tif 000018