(57)【特許請求の範囲】
【請求項１】
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索システムであって、
前記経路探索システムは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定し、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続し、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出し、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出し、前記目的地までの経路とともに到着予想時刻および滞在時間を案内することを特徴とする経路探索システム。
【請求項２】
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索システムであって、
前記経路探索システムは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定し、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続し、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出し、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出して第１経路探索結果とし、
前記ネットワークデータ編集手段は、前記第１経路探索結果を得た際に用いた目的仮想リンクを前記経路探索用ネットワークデータから除外し、
前記経路探索手段は、前記ネットワークデータ編集手段によって前記目的仮想リンクが除外された経路探索用ネットワークデータを用いて残った目的仮想ノードまでの最適経路を第２経路として探索し、前記滞在時間算出手段が算出した前記第２経路における滞在時間を前記第１経路探索結果の滞在時間と比較し、前記第２経路の滞在時間が前記第１経路探索結果における滞在時間より長い場合、前記第２経路を経路探索結果として案内することを特徴とする経路探索システム。
【請求項３】
前記目的仮想ノードは、前記イベントを実行する目的対象の種別に応じた位置情報を持たないカテゴリ仮想ノードに接続され、該カテゴリ仮想ノードと前記目的仮想ノードとの間は、コスト一定のリンクコストを有するリンクで接続され、前記カテゴリ仮想ノードを目的地として経路探索することを特徴とする請求項１または請求項２に記載の経路探索システム。
【請求項４】
前記滞在時間算出手段は、前記目的地への到着予想時刻が前記目的地ノードにおける前記推奨時間帯の開始時刻よりも前である場合には、前記目的仮想リンクに設定された出発時刻を前記推奨時間帯の開始時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出することを特徴とする請求項１または請求項２に記載の経路探索システム。
【請求項５】
前記経路探索システムは、経路探索手段が探索した経路を表示する表示手段を備え、前記表示手段に表示する経路探索結果が所定数になった場合、前記経路探索手段は経路探索の処理を終了することを特徴とする請求項２に記載の経路探索システム。
【請求項６】
前記目的仮想ノードに接続された目的仮想リンクを用いる経路探索を繰り返し行い、目的とする目的仮想ノードに到達するリンクが無くなった場合に経路探索の処理を終了することを特徴とする請求項２に記載の経路探索システム。
【請求項７】
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索サーバであって、
前記経路探索サーバは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定し、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続し、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出し、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出し、前記目的地までの経路とともに到着予想時刻および滞在時間を案内することを特徴とする経路探索サーバ。
【請求項８】
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索サーバであって、
前記経路探索サーバは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定し、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続し、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出し、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出して第１経路探索結果とし、
前記ネットワークデータ編集手段は、前記第１経路探索結果を得た際に用いた目的仮想リンクを前記経路探索用ネットワークデータから除外し、
前記経路探索手段は、前記ネットワークデータ編集手段によって前記目的仮想リンクが除外された経路探索用ネットワークデータを用いて残った目的仮想ノードまでの最適経路を第２経路として探索し、前記滞在時間算出手段が算出した前記第２経路における滞在時間を前記第１経路探索結果の滞在時間と比較し、前記第２経路の滞在時間が前記第１経路探索結果における滞在時間より長い場合、前記第２経路を経路探索結果として案内することを特徴とする経路探索サーバ。
【請求項９】
前記目的仮想ノードは、前記イベントを実行する目的対象の種別に応じた位置情報を持たないカテゴリ仮想ノードに接続され、該カテゴリ仮想ノードと前記目的仮想ノードとの間は、コスト一定のリンクコストを有するリンクで接続され、前記カテゴリ仮想ノードを目的地として経路探索することを特徴とする請求項７または請求項８に記載の経路探索サーバ。
【請求項１０】
前記滞在時間算出手段は、前記目的地への到着予想時刻が前記目的地ノードにおける前記推奨時間帯の開始時刻よりも前である場合には、前記目的仮想リンクに設定された出発時刻を前記推奨時間帯の開始時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出することを特徴とする請求項７または請求項８に記載の経路探索サーバ。
【請求項１１】
前記経路探索システムは、経路探索手段が探索した経路を表示する表示手段を備え、前記表示手段に表示する経路探索結果が所定数になった場合、前記経路探索手段は経路探索の処理を終了することを特徴とする請求項８に記載の経路探索サーバ。
【請求項１２】
前記目的仮想ノードに接続された目的仮想リンクを用いる経路探索を繰り返し行い、目的とする目的仮想ノードに到達するリンクが無くなった場合に経路探索の処理を終了することを特徴とする請求項８に記載の経路探索サーバ。
【請求項１３】
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索サーバにおける経路探索方法であって、
前記経路探索サーバは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定するステップと、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続するステップと、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出するステップと、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出し、前記目的地までの経路とともに到着予想時刻および滞在時間を案内するステップと、を有することを特徴とする経路探索方法。
【請求項１４】
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索サーバにおける経路探索方法であって、
前記経路探索サーバは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定するステップと、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続するステップと、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出するステップと、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出して第１経路探索結果とするステップと、
前記ネットワークデータ編集手段は、前記第１経路探索結果を得た際に用いた目的仮想リンクを前記経路探索用ネットワークデータから除外するステップと、
前記経路探索手段は、前記ネットワークデータ編集手段によって前記目的仮想リンクが除外された経路探索用ネットワークデータを用いて残った目的仮想ノードまでの最適経路を第２経路として探索し、前記滞在時間算出手段が算出した前記第２経路における滞在時間を前記第１経路探索結果の滞在時間と比較し、前記第２経路の滞在時間が前記第１経路探索結果における滞在時間より長い場合、前記第２経路を経路探索結果として案内するステップと、を有することを特徴とする経路探索方法。
【請求項１５】
前記目的仮想ノードは、前記イベントを実行する目的対象の種別に応じた位置情報を持たないカテゴリ仮想ノードに接続され、該カテゴリ仮想ノードと前記目的仮想ノードとの間は、コスト一定のリンクコストを有するリンクで接続され、前記カテゴリ仮想ノードを目的地として経路探索することを特徴とする請求項１３または請求項１４に記載の経路探索方法。
【請求項１６】
前記滞在時間算出手段は、前記目的地への到着予想時刻が前記目的地ノードにおける前記推奨時間帯の開始時刻よりも前である場合には、前記目的仮想リンクに設定された出発時刻を前記推奨時間帯の開始時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出することを特徴とする請求項１３または請求項１４に記載の経路探索方法。
【請求項１７】
前記経路探索システムは、経路探索手段が探索した経路を表示する表示手段を備え、前記表示手段に表示する経路探索結果が所定数になった場合、前記経路探索手段は経路探索の処理を終了することを特徴とする請求項１４に記載の経路探索方法。
【請求項１８】
前記目的仮想ノードに接続された目的仮想リンクを用いる経路探索を繰り返し行い、目的とする目的仮想ノードに到達するリンクが無くなった場合に経路探索の処理を終了することを特徴とする請求項１４に記載の経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所望の出発地から目的地までの最適経路を探索する経路探索システムに関するものであり、特に、例えば、磯釣りのように、複数の場所（ポイント）において同質のイベントを実行することができるが、場所によって当該イベントの実行に適した推奨時間帯が異なり、その場所への到着時刻によって滞在時間が異なるようなイベントを実行するに際して、イベントの実行に適した推奨時間帯に到着可能な場所や、推奨時間帯に到着可能で、且つ、より長い滞在時間を得ることができる場所（ポイント）を抽出し、当該場所までの案内経路を探索するようにした経路探索システムに関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
交通機関を利用する経路を探索する経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータベースを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗り換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレス情報により特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。
【０００８】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００９】
従って端末装置に配信される案内経路データには、利用者が指定した経路探索条件である出発地から目的地までの路線経路や乗車を案内するバス、電車、列車およびその時刻が含まれ、運行時刻表や駅に掲示されるいわゆる駅貼り時刻表などがそのままあるいは必要部分が画面表示できる表示データなどの形式に加工されて端末装置に配信される。端末装置では案内経路のデータや運行時刻表あるいは駅貼り時刻表を表示して経路や乗車すべき交通手段を確認することができる。
【００１０】
交通機関を利用した経路探索を行う経路探索方法は、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に交通ネットワーク経路探索方法として開示されている。この特許文献２に開示された交通ネットワーク経路探索方法は、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する方法である。
【００１１】
この方法においては、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を、緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するようにしている。
【００１２】
利用者が目的地として設定する施設や場所は、利用できる時間帯が限られている場合がある。例えば、商店や飲食店にあっては営業時間が決まっている場合が多く、その商店や飲食店までの経路を探索して経路案内しても、営業時間外にその商店や飲食店を訪れても利用できないことになる。
【００１３】
このような問題点を解消する発明としては、例えば、下記の特許文献３（特開２００４−５５０２号公報）、特許文献４（特開２００２−９８５３９）、下記の特許文献５（２００５−３１５６６０号公報）に開示された情報提供サーバやナビゲーション装置の発明がある。
【００１４】
特許文献３に開示された情報提供サーバの発明は、店舗の店名、最寄り駅、所在地のいずれか１つ以上を含む店舗情報と共に、各店舗に設置された店舗端末から送信される営業時間、準備時間、ラストオーダー時刻、客の平均滞在時間、待ち時間のいずれか１つ以上を記憶するデータベースを保持している。また、特定の地点から店舗までの距離を元に移動時間を算出し、さらに平均滞在時間、待ち時間との加算値と、検索条件になる時刻とを比較し時間内に利用可能な店舗の抽出を行うように構成されたものである。
【００１５】
特許文献４に開示されたナビゲーション装置の発明は、ユーザの指示に基づいて目的地候補を検索しリスト表示を行う。また、この目的地候補の施設情報にはそれぞれ営業時間の情報が含まれており、現在地からその目的地候補の施設への到着予想時刻を算出し、到着予想時刻が営業時間内であるか否かを判断し、その結果を表示するように構成されたものである。
【００１６】
また、特許文献５に開示されたナビゲーション装置の発明は、予め、例えば営業時間のような条件と関連付けて目的地と、その目的地のそれぞれに対応した代替目的地を登録しておく。そして、現在地から目的地にいたるまでの経路案内において、その目的地が営業時間の許容範囲内にあるか否かを判断し、許容範囲外であれば営業時間の許容範囲内にある代替の目的地を提案するように構成されたものである。
【００１７】
特許文献３〜特許文献５のようなナビゲーション装置によれば、目的とする施設を利用できる時間に当該施設に到着する経路を探索して利用者に案内することができる。
【００１８】
一方、利用者が所望の目的地を設定する場合、コンサート、映画、スポーツなどのイベントに参加したり、スポーツや釣りなどのイベントを実行したりするための施設や場所（ポイント）を目的地として設定することもある。このようなイベントのための施設や場所を目的地として設定しても、一般の目的地設定と同様、自宅や職場などを出発地として該目的地までの最適経路や候補経路を探索することができる。
【００１９】
ところで、このようなイベントの中には、必ずしも特定の１ケ所でなく、複数の施設や場所のうちの何れかを選んで参加したり、実行したりできるイベントも存在する。例えば、映画を例にとると、特定の映画タイトルは封切り時においては、複数の映画館で上映され、どの映画館で鑑賞しても内容は同じであり等質のイベントに参加できることになる。この場合、利用者は出発地から最も便利な場所に所在する映画館を選んで所望の映画タイトルを鑑賞すればよい。
【００２０】
ところで、映画の上映開始時刻、上映時間は映画館によって異なるから、単に所望の映画タイトルを上映している映画館を目的地とした最適経路を案内するだけでは、鑑賞したい映画タイトルの上映開始まで待ち時間が生じたりする。映画館に到着する経路は最短でなくても所望の映画タイトルを最も早く鑑賞できる場合もある。
【００２１】
映画タイトルの鑑賞のように、複数の施設、異なる時間帯に実行される等質のイベントの１つを選択して効率的に当該イベントに参加するための経路探索システムは次のように構成することができる。すなわち、交通機関を用いた経路探索のネットワークデータの概念を用いて、各イベントの開催場所を、位置情報を有するイベント会場ノードとし、イベント（上映回ごとの映画タイトル）を、位置情報を持たない目的仮想ノードとして当該イベントが開催されるイベント会場ノードに接続し、イベント会場ノードと目的仮想ノード間を、イベントの開催時刻に基づくリンクで接続し、前記イベント会場ノードを、交通ネットワークデータを含む経路探索用ネットワークデータに接続して経路探索するようになせば解決することができる。
【００２２】
このような経路探索の概念を説明する。図１３は、イベント会場ノードである映画館ＴＡや映画館ＴＢが経路探索用ネットワークデータに接続された状態を模式的に示している。図１３において実線ＴＲは交通路線区間を、点線ＲＤは徒歩区間（道路区間）を示し、参照符号ＴＡ、ＴＢはイベント会場ノードである映画館Ａ、映画館Ｂを示し、ＳＴは交通路線の各駅を示す。映画館Ａ、映画館Ｂは緯度・経度によって位置が特定されるから、点線で示す道路区間（徒歩区間）によって、最寄りの駅ＳＴのノードに接続することができる。イベント会場ノードは他にも多数あるが図１３では代表的に映画館Ａ、映画館Ｂのみを図示している。
【００２３】
ここで、各映画館（イベント会場ノード）で上映される映画タイトルを目的仮想ノードとし、映画タイトルの上映時間（開始時刻、終了時刻）を電車の出発時刻、到着時刻に見立てたリンクで映画館（イベント会場ノード）と映画タイトル（目的仮想ノード）間を接続することにより交通機関を用いた経路探索に含めて所望の映画タイトルの仮想ノードまでの経路を探索することができるようになる。
【００２４】
【特許文献１】特開２００１−１６５６８１号公報
【特許文献２】特開２０００−２５８１８４号公報
【特許文献３】特開２００４−５５０２号公報
【特許文献４】特開２００２−９８５３９号公報
【特許文献５】特開２００５−３１５６６０号公報
【発明の開示】
【発明が解決しようとする課題】
【００２５】
上記特許文献３〜５のような従来技術においては、所在地や営業時間に関する情報を保持した店舗情報について、現在地や任意の出発地を指定してから経路探索を行い、店舗所在地と現在地から移動の所要時間から店舗への到達時刻と営業時間を比較し平均滞在時間等を考慮して、営業時間に間に合うか否かを判断していた。
【００２６】
しかしながら、例えば個々の店舗の営業時間が異なる場合に、その営業時間内に間に合いながらも一番長く滞在できる店舗を検索するという条件を設定することはできない。目的地に一番早く到達しても、その目的地に滞在できる時間が短いのでは意味がなく、目的地への移動の所要時間を多く費やして到着時間が遅くなっても、より長く滞在できる目的地を検索できる必要がある。
【００２７】
また、前述した映画鑑賞のような異なる複数の場所で、それぞれ異なる時間帯において実行される同質のイベントの場合、イベントの開始時刻および終了時刻は固定でありイベント実行中の滞在時間も固定されている。このため、図１３に示したようなネットワークデータを用いて経路探索を行うことができた。しかしながら、異なる複数の場所で、それぞれ異なる推奨時間帯において実行することが好ましいイベントの中には、イベントの実行に適した推奨時間帯の開始時刻および終了時刻が場所によって異なるイベントが存在する。このようなイベントにあっては、場所によりイベント実行中の推奨時間帯における滞在時間が異なることになる。
【００２８】
このようなイベントの具体例としては、例えば、磯釣りなどがあげられる。磯釣りなどのイベントにあっては、干潮と満潮との間の釣りに適した時間帯があり、場所によってこの時間帯の開始時刻、終了時刻は異なる。釣り自体は推奨時間帯でなくても楽しむことはできるが、推奨時間帯を外れた場合大きな成果を期待することができない。従って、釣りを楽しむ利用者にとっては、イベント実行場所（釣りに適したポイント）までの到着予想時刻が上記の推奨時間帯の終了時刻に間に合うことが目的地選択の最も重要な条件であり、更に、移動時間が長くても上記の時間帯の範囲内で、より長い滞在時間が得られることも目的地選択の重要な要因の１つになる。
【００２９】
本発明は、上記のような問題点を解消すべくなされたものであり、それぞれ異なる訪問に適した時間帯を有する複数の選択可能な目的地の中で、出発地から移動して最も適した時間帯に最も長く滞在できる目的地及びその経路を探索して案内することができる経路探索システムを提供することを目的とするものである。
【課題を解決するための手段】
【００３０】
前記課題を解決するために、本願の請求項１にかかる発明は、
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索システムであって、
前記経路探索システムは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定し、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続し、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出し、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出し、前記目的地までの経路とともに到着予想時刻および滞在時間を案内することを特徴とする。
【００３１】
また、本願の請求項２にかかる発明は、
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索システムであって、
前記経路探索システムは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定し、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続し、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出し、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出して第１経路探索結果とし、
前記ネットワークデータ編集手段は、前記第１経路探索結果を得た際に用いた目的仮想リンクを前記経路探索用ネットワークデータから除外し、
前記経路探索手段は、前記ネットワークデータ編集手段によって前記目的仮想リンクが除外された経路探索用ネットワークデータを用いて残った目的仮想ノードまでの最適経路を第２経路として探索し、前記滞在時間算出手段が算出した前記第２経路における滞在時間を前記第１経路探索結果の滞在時間と比較し、前記第２経路の滞在時間が前記第１経路探索結果における滞在時間より長い場合、前記第２経路を経路探索結果として案内することを特徴とする。
【００３２】
本願の請求項３にかかる発明は、請求項１または請求項２にかかる発明において、前記目的仮想ノードは、前記イベントを実行する目的対象の種別に応じた位置情報を持たないカテゴリ仮想ノードに接続され、該カテゴリ仮想ノードと前記目的仮想ノードとの間は、コスト一定のリンクコストを有するリンクで接続され、前記カテゴリ仮想ノードを目的地として経路探索することを特徴とする。
【００３３】
本願の請求項４にかかる発明は、請求項１または請求項２にかかる発明において、前記滞在時間算出手段は、前記目的地への到着予想時刻が前記目的地ノードにおける前記推奨時間帯の開始時刻よりも前である場合には、前記目的仮想リンクに設定された出発時刻を前記推奨時間帯の開始時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出することを特徴とする。
【００３４】
本願の請求項５にかかる発明は、請求項２にかかる発明において、前記経路探索システムは、経路探索手段が探索した経路を表示する表示手段を備え、前記表示手段に表示する経路探索結果が所定数になった場合、前記経路探索手段は経路探索の処理を終了することを特徴とする。
【００３５】
本願の請求項６にかかる発明は、請求項２にかかる発明において、前記目的仮想ノードに接続された目的仮想リンクを用いる経路探索を繰り返し行い、目的とする目的仮想ノードに到達するリンクが無くなった場合に経路探索の処理を終了することを特徴とする。
【００３６】
また、本願の請求項７にかかる発明は、
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索サーバであって、
前記経路探索サーバは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定し、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続し、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出し、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出し、前記目的地までの経路とともに到着予想時刻および滞在時間を案内することを特徴とする。
【００３７】
また、本願の請求項８にかかる発明は、
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索サーバであって、
前記経路探索サーバは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定し、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続し、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出し、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出して第１経路探索結果とし、
前記ネットワークデータ編集手段は、前記第１経路探索結果を得た際に用いた目的仮想リンクを前記経路探索用ネットワークデータから除外し、
前記経路探索手段は、前記ネットワークデータ編集手段によって前記目的仮想リンクが除外された経路探索用ネットワークデータを用いて残った目的仮想ノードまでの最適経路を第２経路として探索し、前記滞在時間算出手段が算出した前記第２経路における滞在時間を前記第１経路探索結果の滞在時間と比較し、前記第２経路の滞在時間が前記第１経路探索結果における滞在時間より長い場合、前記第２経路を経路探索結果として案内することを特徴とする。
【００３８】
本願の請求項９にかかる発明は、請求項７または請求項８にかかる発明において、前記目的仮想ノードは、前記イベントを実行する目的対象の種別に応じた位置情報を持たないカテゴリ仮想ノードに接続され、該カテゴリ仮想ノードと前記目的仮想ノードとの間は、コスト一定のリンクコストを有するリンクで接続され、前記カテゴリ仮想ノードを目的地として経路探索することを特徴とする。
【００３９】
本願の請求項１０にかかる発明は、請求項７または請求項８にかかる発明において、前記滞在時間算出手段は、前記目的地への到着予想時刻が前記目的地ノードにおける前記推奨時間帯の開始時刻よりも前である場合には、前記目的仮想リンクに設定された出発時刻を前記推奨時間帯の開始時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出することを特徴とする。
【００４０】
本願の請求項１１にかかる発明は、請求項８にかかる発明において、前記経路探索システムは、経路探索手段が探索した経路を表示する表示手段を備え、前記表示手段に表示する経路探索結果が所定数になった場合、前記経路探索手段は経路探索の処理を終了することを特徴とする。
【００４１】
本願の請求項１２にかかる発明は、請求項８にかかる発明において、前記目的仮想ノードに接続された目的仮想リンクを用いる経路探索を繰り返し行い、目的とする目的仮想ノードに到達するリンクが無くなった場合に経路探索の処理を終了することを特徴とする。
【００４２】
また、本願の請求項１３にかかる発明は、
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索サーバにおける経路探索方法であって、
前記経路探索サーバは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定するステップと、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続するステップと、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出するステップと、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出し、前記目的地までの経路とともに到着予想時刻および滞在時間を案内するステップと、を有することを特徴とする。
【００４３】
また、本願の請求項１４にかかる発明は、
所望の出発地を設定して、複数の目的地および該目的地ごとに異なる複数の推奨時間帯において実行することが好ましいイベントを実行する前記複数の目的地への経路を探索する経路探索サーバにおける経路探索方法であって、
前記経路探索サーバは、経路を探索するための経路探索用ネットワークデータを蓄積した経路探索用ネットワークデータベースと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの推奨時間帯に関するデータを蓄積したイベントデータデータベースと、前記複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成する目的仮想ノード設定手段と、目的仮想リンク設定手段と、滞在時間算出手段と、を備え、
前記目的仮想リンク設定手段は、目的仮想ノードが選択されると、前記イベントデータデータベースを参照して目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、前記目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定するステップと、
前記ネットワークデータ編集手段は、前記目的仮想リンク設定手段が設定した目的仮想リンクに接続された目的仮想ノードを前記経路探索用ネットワークデータに接続するステップと、
前記経路探索手段は前記出発地から前記目的仮想ノードまでの最適経路を探索し、前記目的地ノードへの到着予想時刻を算出するステップと、
前記滞在時間算出手段は、前記目的仮想リンクの出発時刻を前記到着予想時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出して第１経路探索結果とするステップと、
前記ネットワークデータ編集手段は、前記第１経路探索結果を得た際に用いた目的仮想リンクを前記経路探索用ネットワークデータから除外するステップと、
前記経路探索手段は、前記ネットワークデータ編集手段によって前記目的仮想リンクが除外された経路探索用ネットワークデータを用いて残った目的仮想ノードまでの最適経路を第２経路として探索し、前記滞在時間算出手段が算出した前記第２経路における滞在時間を前記第１経路探索結果の滞在時間と比較し、前記第２経路の滞在時間が前記第１経路探索結果における滞在時間より長い場合、前記第２経路を経路探索結果として案内するステップと、を有することを特徴とする。
【００４４】
本願の請求項１５にかかる発明は、請求項１３または請求項１４にかかる発明において、前記目的仮想ノードは、前記イベントを実行する目的対象の種別に応じた位置情報を持たないカテゴリ仮想ノードに接続され、該カテゴリ仮想ノードと前記目的仮想ノードとの間は、コスト一定のリンクコストを有するリンクで接続され、前記カテゴリ仮想ノードを目的地として経路探索することを特徴とする。
【００４５】
本願の請求項１６にかかる発明は、請求項１３または請求項１４にかかる発明において、前記滞在時間算出手段は、前記目的地への到着予想時刻が前記目的地ノードにおける前記推奨時間帯の開始時刻よりも前である場合には、前記目的仮想リンクに設定された出発時刻を前記推奨時間帯の開始時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出することを特徴とする。
【００４６】
本願の請求項１７にかかる発明は、請求項１４にかかる発明において、前記経路探索システムは、経路探索手段が探索した経路を表示する表示手段を備え、前記表示手段に表示する経路探索結果が所定数になった場合、記経路探索手段は経路探索の処理を終了することを特徴とする。
【００４７】
本願の請求項１８にかかる発明は、請求項１４にかかる発明において、前記目的仮想ノードに接続された目的仮想リンクを用いる経路探索を繰り返し行い、目的とする目的仮想ノードに到達するリンクが無くなった場合に経路探索の処理を終了することを特徴とする。
【発明の効果】
【００４８】
請求項１にかかる発明においては、複数の目的地を、それぞれ位置情報を有する目的地ノードとし、前記イベントを実行する目的対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成して経路探索用ネットワークデータに接続し、目的仮想ノードを選択して経路探索する際、目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、目的仮想リンクが接続される目的地ノードの出発時刻と目的仮想ノードへの到着時刻を、前記目的仮想リンクが接続される目的地ノードにおける前記推奨時間帯の終了時刻を用いて設定して最適経路を探索する。そして、目的仮想リンクの出発時刻を探索により得た目的地ノードへの到着予想時刻で置き換え、目的仮想リンク設定手段により設定された到着時刻との間の時間を目的地ノードにおける滞在時間として算出する。
【００４９】
このような構成によれば、出発地から目的地ノードへの到着時刻が推奨時間帯の終了時刻に間に合う目的仮想ノードまでの経路が探索され、この経路における目的地ノードへの到着予想時刻を目的仮想リンクの出発時刻に置き換えれば、目的仮想リンクの到着時刻との差から目的地ノードにおける滞在時間を算出することができるから、目的地ノードにおいて、推奨時間帯の範囲内でイベント、例えば、釣りを実行できる滞在時間を案内することができるようになる。すなわち、目的地での推奨時間帯の終了時刻に間に合うように最も早く到着できる目的地を案内することができるようになる。
【００５０】
請求項２にかかる発明においては、前記請求項１において探索した経路を第１経路とし、第１経路探索結果を得た際に用いた目的仮想リンクを前記経路探索用ネットワークデータから除外し、
前記経路探索手段は、前記ネットワークデータ編集手段によって前記目的仮想リンクが除外された経路探索用ネットワークデータを用いて残った目的仮想ノードまでの最適経路を第２経路として探索し、前記滞在時間算出手段が算出した前記第２経路における滞在時間を前記第１経路探索結果の滞在時間と比較し、前記第２経路の滞在時間が前記第１経路探索結果における滞在時間より長い場合、前記第２経路を経路探索結果として案内する。
【００５１】
このような構成によれば、第１経路に対して、目的地への到着時刻は遅くなるが、当該目的地における推奨時間帯の範囲内での滞在時間を第１経路よりも長くとることができる経路を案内することができるようになる。
【００５２】
請求項３にかかる発明においては、請求項１または請求項２にかかる発明において、目的仮想ノードは、前記イベントを実行する目的対象の種別に応じた位置情報を持たないカテゴリ仮想ノードに接続され、該カテゴリ仮想ノードと前記目的仮想ノードとの間は、コスト一定のリンクコストを有するリンクで接続され、前記カテゴリ仮想ノードを目的地として経路探索する。
【００５３】
このような構成によれば、イベントの対象、例えば、釣りであるイベントの対象である魚の特徴ごとにカテゴリが分けられ、目的仮想ノードとカテゴリ仮想ノードがリンクで接続されたネットワークを用いるから、カテゴリ仮想ノードを選択することによりイベント実行の対象である魚の種類に応じた目的地ノードを探索することができるようになる。
【００５４】
請求項４にかかる発明においては、請求項１または請求項２にかかる発明において、滞在時間算出手段は、前記目的地への到着予想時刻が前記目的地ノードにおける前記推奨時間帯の開始時刻よりも前である場合には、前記目的仮想リンクに設定された出発時刻を前記推奨時間帯の開始時刻で置き換え、該出発時刻と前記目的仮想リンク設定手段により設定された到着時刻との間の時間を前記目的地ノードにおける滞在時間として算出する。
【００５５】
このような構成によれば、目的仮想リンクに設定された出発時刻が目的地ノードへの到着予想時刻で置き換えられるから、推奨時間帯の開始時刻前に到着する場合であっても、目的地ノードにおける滞在時間を算出することができるようになる。
【００５６】
請求項５にかかる発明においては、請求項２にかかる発明において、経路探索システムは、経路探索手段が探索した経路を表示する表示手段を備え、前記表示手段に表示する経路探索結果が所定数になった場合、経路探索手段は経路探索の処理を終了する。かかる構成によれば、所定数の候補経路を案内して経路探索を終了することができるようになり、利用者は候補経路の中から所望の目的地を選択することができるようになる。
【００５７】
請求項６にかかる発明においては、請求項２にかかる発明において、経路探索システムは、目的仮想ノードに接続された目的仮想リンクを用いる経路探索を繰り返し行い、目的とする目的仮想ノードに到達するリンクが無くなった場合に経路探索の処理を終了する。かかる構成によれば、利用者が選択した目的仮想ノードに到達するリンクに接続された目的地ノードの到着予想時刻、推奨時間帯の範囲内での滞在時刻を知ることができるようになる。
【００５８】
また、請求項７ないし請求項１２にかかる発明においては、それぞれ請求項１ないし請求項６にかかる経路探索システムを構成する経路探索サーバを提供することができるようになる。また、請求項１３ないし請求項１８にかかる発明においては、それぞれ請求項７ないし請求項１２にかかる経路探索サーバを実現する経路探索方法を提供することができるようになる。
【発明を実施するための最良の形態】
【００５９】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するための経路探索システムを例示するものであって、本発明をこの経路探索システムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態の経路探索システムにも等しく適用し得るものである。
【実施例】
【００６０】
本発明の実施例にかかる経路探索システム１０は、図１に示すように、携帯電話やＰＤＡ、ミュージックプレーヤーなどの携帯型端末を用いた携帯端末装置２０と経路探索サーバ３０とがインターネットなどのネットワーク１２を介して接続される構成になっている。なお、本実施例においては、通信型の経路探索、案内経路を提供する経路探索システム１０を具体例として説明するが、本発明はこれに限ることなく、スタンドアロンタイプの経路探索システムになどにも適用可能である。
【００６１】
経路探索サーバ３０は、経路探索のため道路ネットワークのデータを蓄積したデータベース（ＤＢ１）、時刻表データに基づく交通ネットワークのデータを蓄積したデータベース（ＤＢ２）、異なる複数の場所で、それぞれ異なる推奨時間帯において実行することが好ましいイベントのデータを蓄積したイベントデータベース（ＤＢ３）、表示用の地図データなどを蓄積したデータベース（ＤＢ４）を備えている。
【００６２】
以下、本発明の実施例の説明において、異なる複数の場所で、それぞれ異なる推奨時間帯において実行することが好ましいイベントの例として、磯釣りなど釣りの場合を具体例として説明する。イベントが釣りの場合、イベントデータは日々の潮汐表に基づいて算出した各地点の釣りスポットにおける推奨時間帯の開始時刻、終了時刻のデータである。潮汐表をイベントデータとして記憶し、推奨時間帯をその都度算出するようにしてもよい。イベントデータの詳細については、後述する。
【００６３】
図２は、本発明の実施例にかかる経路探索システム１０の詳細な構成を示すブロック図である。本発明の実施例にかかる経路探索システム１０は、図２のブロック図に示すようにインターネットなどのネットワーク１２を介して通信する携帯端末装置２０と、経路探索サーバ３０とを備えて構成されている。
【００６４】
携帯端末装置２０は、ナビゲーションサービスを受けることができる携帯電話機などの端末であり、制御手段２０１、通信手段２１、ＧＰＳ受信手段２２、処理要求手段２３、配信データ記憶手段２４、表示手段２５、操作入力手段２６などを備えて構成されている。操作入力手段２６には、目的とするイベントを設定するための目的イベント設定手段２６１が含まれる。目的イベント設定手段２６１は具体的には文字入力キー、表示手段２５の表示画面に表示されたメニュー画面の設定項目などを選択するカーソルキーなどで構成されており、利用者は釣りをイベントとして実行したい場合、目的イベント設定手段２６１を用いて後述する目的仮想ノードを設定（選択）する。
【００６５】
一方、経路探索サーバ３０は、制御手段３０１、通信手段３１、配信データ編集手段３２、代替経路探索制御手段３３、地図データベース３４、経路探索用ネットワークデータベース３５、イベントデータデータベース３６、ネットワークデータ編集手段３７、目的仮想ノード設定手段３７１、目的仮想リンク設定手段３７２、滞在時間算出手段３７３、処理要求記憶手段３８、経路探索手段３９などを備えて構成されている。
【００６６】
携帯端末装置２０は、経路探索サーバ３０に出発地と目的地などの経路探索条件を設定して経路探索要求を送信し、経路探索サーバ３０は携帯端末装置２０から経路探索やＰＯＩ検索あるいは地図配信の要求があると、処理要求記憶手段３８に一次記憶する。要求が経路探索要求である場合、経路探索手段３９は経路探索用ネットワークデータベース３５を参照して最適経路あるいは推奨経路（案内経路）を探索する。
【００６７】
探索された案内経路のデータは配信データ編集手段３２により携帯端末装置２０に対する配信データに編集され、携帯端末装置２０に配信される。また、地図データベース３４から案内経路を含む地図データが読み出され、携帯端末装置２０に配信される。
【００６８】
図３は、釣りをイベントとして実行する場合の複数の目的地（釣り場）を示す模式図である。図３において参照符号ＳＴは出発地を、釣り場１を示すＯＰ１は那珂湊（茨城県）、釣り場２を示すＯＰ２は銚子港（千葉県）、釣り場３を示すＯＰ３は鴨川（千葉県）、釣り場４を示すＯＰ４は真鶴岬（神奈川県）を示し、釣りのポイントとなる地点である。通常の経路探索においては、特定の目的地、例えば、釣り場ＯＰ１の那珂湊を設定して出発地から最短時間で到達できる経路を探索する。その結果、目的地への最短経路と、所要時間と、到着時刻とを知ることができた。
【００６９】
しかしながら、後述するように、釣りは魚を釣り上げるのに適した時間帯というものが場所と日によって大よそ決まっている。従って、目的地として設定した釣り場ＯＰ１の那珂湊への到着時刻を、釣りに適した時間帯に入るように設定して到着時刻指定の経路探索条件とすれば、案内経路と出発地ＳＴの出発時刻が案内される。この場合、利用者が釣りのポイントにおける釣りに適した時間帯を知っていることが前提となる。また、複数の目的地について経路や出発時刻、滞在時間（適した時間帯で釣りをてきる時間）を比較したい場合には、目的地や到着時刻を順次設定して経路探索して結果を比較するという手間が必要であった。
【００７０】
本実施例にかかる経路探索システムにおいては、釣りのポイント（目的地）と日付けごとに釣りに適した推奨時間帯（開始時刻と終了時刻）、あるいは、推奨時間帯算出のもとになる潮汐表のデータをデータベースとして用意しておき、複数の釣り場を候補目的地とし、各釣り場における推奨時間帯の間にその釣り場に到着することができ、また、該推奨時間帯の中でより長く滞在して釣りのイベントを実行できる目的地を探索して案内するようにしたものである。
【００７１】
一般に、釣りに最も適した時間帯と言われるのはマズメと呼ばれる日の出・日の入時刻付近や、潮の動きが早くなる時合いと呼ばれる時間帯である。ここでは、この時合いを釣りに最も適した時間帯とする。時合いの考え方は、人によって違いはあるが、大よそ満潮の前に起きる干潮から満潮までの時間の七分（７／１０のこと）から満潮までと、その後に訪れる干潮までの時間の三分（３／１０のこと）までを上げ七分下げ三分と表現し、それを時合いと呼ぶ。この潮位の変化は位置、および日付けに依存するため、釣り場によって、日によってそれぞれその時合いは異なる。
【００７２】
例えば、図３に示す釣り場ＯＰ１〜ＯＰ４（那珂湊〜真鶴岬）のある日（日付）の各地点の潮汐表は図４に示すようになっている。釣り場ＯＰ１の那珂湊であれば、この日の満潮は０：４９と１５：０１であるということが分かる。そこから、釣り場ＯＰ１の那珂湊の時合いは前日の２３：２０から当日の３：００までと１２：５５から１６：４０までであると予測することが出来る。同様に、その他の釣り場についてもそれぞれ釣りの時合いを算出できる。図５は、図４の潮汐表に基づいて各釣り場ＯＰ１〜ＯＰ４おける時合い（推奨時間帯）を算出した結果を示している。
【００７３】
イベントデータデータベース３６には、図４に示す各釣り場を含む釣りの各ポイントの日付けごとの推奨時間帯のデータが蓄積されている。また、イベントデータデータベース３６には図４に示す各釣り場を含む釣りの各ポイントの日付ごと潮汐表を記憶しておき、経路探索時に時合いを算出して用いるようにすることもできる。
【００７４】
次に、このようなイベントデータを用い、複数の釣り場を候補にして一番長く所定の時間帯に滞在できる目的地を探索して案内する経路探索の概念について説明する。先ず、道路および交通機関のネットワークデータを用いた経路探索の概念を説明する。経路探索用ネットワークデータベース３５には自動車や歩行区間の経路探索のための道路ネットワークデータ（ＤＢ１）と、交通機関を用いた経路探索のための交通ネットワークデータ（ＤＢ２）とが蓄積されている。
【００７５】
経路探索のための道路ネットワークデータ（ＤＢ１）は以下のように構成されている。例えば、道路が図６に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００７６】
すなわち、図６において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図６では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７７】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図６において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積する。そして、リンクコストの累積値が最少になる経路を探索して案内する。
【００７８】
図６ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００７９】
これに対して、交通機関の経路探索のための交通ネットワークデータ（ＤＢ２は）以下のように構成されている。例えば、図７に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図７において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図７では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００８０】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図７に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００８１】
図７に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。
【００８２】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【００８３】
例えば、図７において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００８４】
ここで、釣り場ＯＰ１〜ＯＰ４は、緯度、経度を位置情報として表される地理上の特定の位置であるから、位置情報を有する目的地のノードとすることができる。このノードを目的地ノードということとする。また、釣り場ＯＰ１〜ＯＰ４における釣りに適した推奨時間帯はそれぞれ異なる開始時刻、終了時刻を持つ時合い時間であるから、釣りのイベントを目的仮想ノードとし、目的地ノードと目的仮想ノード間を目的仮想リンクで接続する。
【００８５】
目的仮想ノード設定手段３７１は、後述するようにして、目的地ノードと目的仮想ノードおよび目的仮想リンクを予め釣りのイベントに対する経路探索のネットワークデータとして作成しておく。釣りをイベントとした経路探索時に経路探索用ネットワークデータベースのネットワークデータに接続される。
【００８６】
目的仮想リンクは、推奨時間帯の開始時刻と終了時刻を交通ネットワークにおける電車の出発時刻、到着時刻に見立てて、推奨時間帯の開始時刻を、目的地ノードを出発する出発時刻、推奨時間帯の終了時刻を目的仮想ノードに到着する到着時刻としたリンクである。経路探索にあたり、目的仮想ノードが選択されると目的仮想リンク設定手段３７２はイベントデータデータベース３６に記憶された潮汐表あるいは時合いデータから当日の時合いを抽出して推奨時間帯の開始時刻を、目的地ノードを出発する出発時刻、推奨時間帯の終了時刻を目的仮想ノードに到着する到着時刻に設定し、ネットワークデータ編集手段３７はこの目的仮想リンクおよび目的仮想ノードを経路探索用ネットワークデータベース３５のネットワークデータに接続して経路探索する。
【００８７】
経路探索は次のような手順で行われる。先ず、目的仮想リンクの出発時刻と到着時刻を、目的仮想リンクが接続される目的地ノードにおける推奨時間帯の終了時刻とするリンクコスト０のリンクとして経路探索する。これにより出発地から目的地ノードへの到着時刻が推奨時間帯の終了時刻に間に合う目的仮想ノードが第１経路として探索される。次に、探索された第１経路における目的地ノードへの到着予想時刻を目的仮想リンクの出発時刻に置き換えて、該目的仮想リンクの到着時刻との差から目的地ノードにおける滞在時間を算出する。これにより、目的地ノードにおいて、推奨時間帯の範囲内で釣りを実行できる滞在時間を案内することができる。なお、ここでいう目的仮想リンクの出発時刻の置き換えとは滞在時間を算出するためのものであり、予め釣りのイベントに対して作成された経路探索のネットワークデータにおける目的仮想リンクの時刻データを一時的に置き換える処理であり、直接的に滞在時間を算出する処理をも含むものである。
【００８８】
次に、滞在時間を最も長くとれる目的地ノードを案内するために、代替経路探索制御手段３３は、前記第１の経路において用いた目的仮想リンクを経路探索用ネットワークデータから除いて、前記の経路探索手順を繰り返し、算出した滞在時間が第１経路よりも大きい場合に経路探索結果とする手順を繰り返す。これにより、目的地ノードにおける推奨時間帯の範囲内で最も滞在時間を長くとることのできる目的地ノードを目的地とする経路を案内することができるようになる。
【００８９】
この概念を図８に示す。釣り場ＯＰ１〜ＯＰ４は図３に示した各釣り場を示している。各釣り場ＯＰ１〜ＯＰ４は経路探索のネットワークデータにおける目的地ノードに設定される。各目的地ノードからイベントである釣りの対象となる魚を目的仮想ノードとして設定し、各目的地ノードＯＰ１〜ＯＰ４との間を目的仮想リンクＬ−１ＡないしＬ−４Ｃで接続する。このように目的地ノードと目的仮想ノードとを目的仮想リンクにより接続する構成にすれば、全ての釣り場（目的地ノード）を対象とした経路探索をする必要がなく、効率的な経路探索が可能になる。
【００９０】
ここで、各釣り場ＯＰ１〜ＯＰ４においては、図５に示したように、１日に訪れる時合いは２回あるので、目的地ノードに接続する目的仮想リンクを２つ設定し、これを各釣り場ＯＰ１〜ＯＰ４のそれぞれに接続し、それぞれの時合いの終了時刻を各目的仮想リンクの出発時刻と到着時刻とするネットワークデータを生成する。図９は、魚Ａの目的仮想ノードから目的地ノードＯＰ１に接続される２つの目的仮想リンクを示す模式図である。
【００９１】
図９に示すように、釣り場ＯＰ１（目的地ノード）と目的仮想ノード（魚Ａ）との間は目的仮想リンクＬ−１Ａ−１と、目的仮想リンクＬ−１Ａ−２で接続される。釣り場ＯＰ１における時合いは、図５に示す時間帯（開始時刻２３：２０、終了時刻３：００）であるから、目的仮想リンクＬ−１Ａ−１は目的仮想ノードの出発時刻、到着時刻を時合いの終了時刻（３：００）とするリンクである。
【００９２】
同様に、もう一方の目的仮想リンクＬ−１Ａ−２は、２回目の時合いの時間帯（開始時刻１２：５５、終了時刻１６：４０であるから、目的仮想リンクＬ−１Ａ−２は目的仮想ノードの出発時刻、到着時刻を時合いの終了時刻（１６：４０）とするリンクである。この目的仮想リンクＬ−１Ａ−１、Ｌ−１Ａ−２および目的仮想ノード（魚Ａ）を目的地ノードＯＰ１に接続し、経路探索用ネットワークデータに接続して目的仮想ノードを目的地とした経路探索を行う。
これは、魚（目的仮想ノード）が各釣り場（目的地ノード）からリンクコストが「０」の値を持つリンクで接続されるということを意味している。ここで、各釣り場ＯＰ １ 〜 ＯＰ４ から目的仮想ノードＡ〜Ｃへのリンクのリンクコストは論理的にはそれぞれの値が等しければよく必ずしも値が「０」である必要はない。
【００９３】
ところで、釣りの対象とする魚の特徴等を示すカテゴリにもカテゴリ仮想ノードを与え、各カテゴリに属する魚（目的仮想ノード）から該当カテゴリに該当するカテゴリ仮想ノードにカテゴリ仮想リンクを接続しても良い。このようにする理由は魚の種類によって旬の時期など特徴が異なるからである。例えば、魚ごとに釣りの時期、漁場が異なる。例えば、旬の時期が冬期である魚や逆に夏期である魚などの別があり、海底が砂地である地形を好む魚がある一方、海底が岩場である地形を好む魚もある。また、日中に活動的になる魚や夜間あるいは明け方に活動的になる魚もある。
【００９４】
このような魚の特徴を表すカテゴリを仮想ノードとして目的を設定できるようにすれば、魚の特徴に応じた目的の設定、経路探索を適切に効率よく実施することができるようになる。そこで、本実施例においては、例えば、図８に示すように、イベントを実行しようとする月が、特に釣れどきの旬の魚をまとめてカテゴリＣ１「○月が旬の魚」というカテゴリを用意する。魚Ａがそれに該当する場合には、魚Ａの目的仮想ノードからカテゴリＣ１のカテゴリ仮想ノードにカテゴリ仮想リンクＬ−ＡＣ1を接続する。これもカテゴリへの片方向リンクであり、この部分のリンクコストは、差が付かないようにコスト０、あるいは一定の値に決めておく。
【００９５】
携帯端末装置２０の利用者がイベントである釣り対象として選択する魚は、図８に示すように、魚Ａ、魚Ｂ、魚Ｃのように種々の魚があり、それぞれの特徴に従って、カテゴリＣ１やＣ２に分けられ、カテゴリ仮想リンクによって接続されている。目的地となる釣り場ＯＰ１〜ＯＰ４は、図３に図示した各釣り場である。そして、目的地ノードを釣り場ＯＰ１〜ＯＰ４とし、イベントである釣りの対象である魚Ａ〜魚Ｃを目的仮想ノードとし、各目的地ノードと目的仮想ノードとの間を目的仮想リンクＬ−１Ａ〜Ｌ４Ｃで接続する。
【００９６】
図８において、目的地ノードである釣り場ＯＰ１〜ＯＰ４と目的仮想ノードである魚Ａ〜魚Ｃの全ての組み合わせについて目的仮想リンクが接続されていない理由は、前述のように、魚の種類によって釣りに適した釣り場が異なるからである。図８を参照すると、魚Ｃを目的仮想ノードとした場合、目的仮想リンクＬ−１Ｃが目的地ノードＯＰ１に、目的仮想リンクＬ−４Ｃが目的地ノードＯＰ４に接続されている。このように魚のカテゴリごとに目的地ノードと目的仮想ノードとを接続する目的仮想リンクを必要なものだけに絞ることができ、経路探索処理を効率的に進めることができるようになる。
【００９７】
再び、図３に示す目的地ノードの概念図に戻り、本実施例にかかる経路探索の具体的な例について説明する。本実施例においては現在地Ｓを出発地ＳＴとしてどこかの釣り場で釣りをする場合の経路探索になる。現在地Ｓの位置をＧＰＳなどで取得し、釣りたい魚が魚Ｃである場合には、一般の経路探索のように釣り場ＯＰ１〜ＯＰ４を目的として設定せず、釣り対象である対象物（魚Ｃ）を目的仮想ノードとして設定して経路探索を行う。ここでは、現在地Ｓを東京、神田としておく。さらに、経路探索条件として、現在地Ｓを時刻１３：００に出発し自動車で目的地に向かうものとしておく。
【００９８】
先ず、図８に示すように目的仮想ノードである魚Ｃに接続されているリンクはＬ−１ＣとＬ−４Ｃ（実線で示されている）であるから、経路探索上の位置情報を持つ目的地すなわち目的地ノードは、目的仮想ノードＣと目的仮想リンクＬ−１Ｃが接続されている釣り場ＯＰ１の那珂湊及び目的仮想ノードＣと目的仮想リンクＬ−４Ｃ釣り場ＯＰ４の真鶴岬である。
【００９９】
一般的な経路探索システムであれば、道路ネットワークのデータを参照して目的地である釣り場ＯＰ１や釣り場ＯＰ４までの最適経路が探索される。例えば、現在地Ｓ（出発地ＳＴ）から釣り場ＯＰ１への所要時間は２時間２分、現在地Ｓから釣り場ＯＰ４への所要時間は２時間１７分であるとすると、最短経路は所要時間の短い釣り場ＯＰ１の那珂湊が案内される。
【０１００】
これに対して、本実施例にかかる経路探索システム１０においては、道路ネットワークに各目的地ノード（ＯＰ１、ＯＰ４）において目的仮想リンクＬ−１Ｃ、１−４Ｃで接続された目的仮想ノード（魚Ｃ）が加えられ、目的仮想ノード（魚Ｃ）を目的地とした経路探索が行われる。各釣り場ＯＰ１、ＯＰ４から目的仮想ノード（魚Ｃ）には、それぞれ所要時間が０（出発時刻と到着時刻が時合いの終了時刻）とされた目的仮想リンクＬ−１Ｃ、Ｌ−４Ｃが接続されている。
【０１０１】
出発地ＳＴから釣り場ＯＰ１（目的地ノード）への所要時間が２時間２分であるから、釣り場ＯＰ１への到着予想時刻は１５：０２であることがわかる。図５に示すイベントデータ（推奨時間帯データ）を参照すると、釣り場ＯＰ１の時合い終了時刻は１６：４０であるので、この到着予想時刻は時合いの終了時刻に間に合っていることが分かるのでこの経路を第１経路とする。もし、時合い終了時刻に間に合っていなければ、この経路探索結果は表示されない。そして、時合い終了時刻に間に合う他の目的地ノードに至る経路を探索する。
【０１０２】
次に、前述のようにして探索された第１経路の釣り場ＯＰ１への到着予想時刻について、釣り場ＯＰ１の時合い開始時刻と比較する。釣り場ＯＰ１の時合い開始時刻が１２：５５であることから、到着予想時刻の１５：０２が時合い開始時刻以降であることが分かる。この場合には、釣り場ＯＰ１（目的地ノード）から目的仮想ノード（魚Ｃ）に設定した目的仮想リンクＬ−１Ｃの出発時刻を到着予想時刻である１５：０２に置き換える。
【０１０３】
すると、目的仮想リンクＬ−１Ｃに設定された時刻表は１５：０２に出発して１６：４０に到着するように設定される。この出発時刻（１５：０２）から到着時刻（１６：４０）の間、すなわち、目的仮想リンクＬ−１Ｃの所要時間１：３８は、釣り場ＯＰ１に到着してから時合いの間に釣りが出来る時間となる。なぜなら、出発時刻の１５：０２は釣り場ＯＰ１への到着予想時刻であり、到着時刻の１６：４０は釣り場ＯＰ１における時合いの終了時刻であるからである。
【０１０４】
これに対して、釣り場ＯＰ１への到着予想時刻が時合い開始時刻より早い場合には、時合い目的仮想リンクＬ−１Ｃの出発時刻を釣り場ＯＰ１における時合いの開始時刻（１５：０１）で置き換える。釣りは、釣り場に到着していれば時合いでなくても開始可能なので、ユーザには到着予想時刻と共に、時合いに間に合うこと、時合い時刻等を通知する。
【０１０５】
このようにして探索した第１経路が、魚Ｃを対象として釣りのイベントを実行する場合に、一番早く釣り場に到着して時合いの時間帯の中で少しでも釣りができる経路であるということを意味している。このようにして得られた経路探索結果を、第１の経路探索結果（第１経路）とする。
【０１０６】
次に、前記の第１の経路探索結果に該当する目的仮想リンクＬ−１Ｃを経路探索用のネットワークからはずして再び経路探索を行い、時合いの間に釣りが出来る釣り場と到着予想時刻、推奨時間帯の範囲内での滞在時間（時合いの範囲内での釣り時間）を得たら、その滞在時間を第１の経路探索結果と比較を行う。もし、時合いの間に釣りが出来る時間が第１の経路探索の結果より長い場合には、到着時刻は遅いが時合いの間に釣りが出来る時間が長いということを意味するので、これを第２の経路探索結果（第２経路）として表示する。
【０１０７】
以上、説明した第１経路と第２経路の比較表を図１０に示す。図１０に示すように第１経路探索結果は、釣り場ＯＰ１を目的地ノードとする経路であり、目的地ノードである釣り場ＯＰにおける時合い時間（推奨時間帯）は１２：５５〜１６：４０である。そして釣り場ＯＰ１への到着予想時刻は１５：０２であり、時合い（推奨時間帯）の範囲内での釣り時間（イベントの実行時間）は１：３８である。
【０１０８】
これに対して第２経路探索結果は、釣り場ＯＰ４を目的地ノードとする経路であり、目的地ノードである釣り場ＯＰにおける時合い時間（推奨時間帯）は１４：０１〜１７：５２である。そして釣り場ＯＰ４への到着予想時刻は１５：１７であり、時合い（推奨時間帯）の範囲内での釣り時間（イベントの実行時間）は２：３５である。
【０１０９】
この結果からわかるように、目的地を釣り場ＯＰ４とした第２の経路探索結果においては、釣り場ＯＰ４の時合い時間から、時合いの中で釣りが出来る時間は２：３５と、第１の経路探索結果より５７分長く推奨時間帯の範囲内で釣りができることがわかる。従って、時合いの終了時刻の前に到着することができ、推奨時間帯（時合い）の範囲の間でより長い時間滞在可能（イベントである釣りを実行可能）な経路、目的地を利用者に案内することができる。
【０１１０】
もし、第２の経路探索結果において、時合いの間に釣りが出来る時間が第１の経路探索結果より短い場合はこの経路探索の結果は表示しない。そして、この経路探索で使用した目的仮想リンクＬ４−Ｃをはずして再度経路探索を行う。この経路探索を繰り返し行い、目的とする目的仮想ノード（魚Ｃ）に到達するリンクが無くなった場合には経路探索を終了する。または、表示する経路探索結果が所定の数だけ得られた場合に経路探索を終了してもよい。
【０１１１】
上記の第２経路において、釣り場ＯＰ４への到着時刻が推奨時間帯（時合い）の開始時刻よりも前である場合には、時合いの開始時刻も案内する。釣りは、釣り場に到着していれば時合いでなくても開始可能なので、ユーザには到着予想時刻と共に、時合いに間に合うこと、時合い時刻等を通知する。
【０１１２】
なお、上記の例においては、目的仮想リンクのリンクコストを「０」とする例（時合いの終了時刻をリンクの出発時刻および到着時刻とする例）を説明したが、目的仮想リンクには、ユーザが所望する時合いの間に釣りをする滞在時間を予めそのリンクコストとして設定しておいてもよい。この場合には、目的地ノードである釣り場に接続される目的仮想ノードにはそれぞれ時合い終了の時刻情報が設定されているので、ユーザの所望する時間を引いた時刻を目的仮想ノードの出発時間とし、時合い終了時刻を到着時刻と設定すればよい。
【０１１３】
このように設定した目的仮想リンクの時刻条件に従って、釣り場（目的地ノード）から目的仮想ノードへの時刻条件として、出発時刻に間に合う経路探索を行えばよい。この経路探索の結果、釣り場（目的地ノード）への到着時予想時刻を釣り場から目的仮想ノードを接続する目的仮想リンクの出発時間に書き換える。ここから得られる目的仮想リンクの所要時間を、ユーザが釣り場で釣りが出来る滞在時間として表示することができる。
【０１１４】
以上、説明した本実施例の経路探索処理の手順について図１１、図１２に示すフローチャートを参照して説明する。図１１は、推奨時間帯に目的地に到着可能であり、推奨時間帯の範囲内でイベントの実行が可能な経路を探索する手順を示すフローチャート、図１２は、推奨時間帯に目的地に到着可能であり、推奨時間帯の範囲内で最も長くイベントの実行が可能な経路を探索する手順を示すフローチャートである。
【０１１５】
先ず、携帯端末装置２０においてステップＳ１０１でイベントである釣りの対象とする魚（例えば、図８の魚Ｃ）を選択する。経路探索サーバ３０は携帯端末装置２０から釣りの対象とする魚Ｃの情報を受信すると、該当する目的仮想ノード（魚Ｃ）が特定され、ステップＳ１０２において、目的仮想リンク設定手段３７２はイベントデータデータベース３６に記憶された潮汐表あるいは時合いデータを参照して、各目的仮想リンクの出発時刻と目的時刻を当該目的仮想リンクが接続された目的地ノードにおける時合いの終了時刻に設定する（図９参照）。
【０１１６】
ネットワークデータ編集手段３７は、目的仮想ノードと、前述のようにして目的仮想リンク設定手段３７２が設定した目的仮想リンクを経路探索用ネットワークデータベース３５に接続する（ステップＳ１０３）。次に、経路探索手段３９は、ステップＳ１０４の処理で目的仮想ノードを対象として経路探索を行い、経路探索の結果が得られたら、目的地ノードへの到着予想時刻を算出する（図１０参照）。
【０１１７】
次いで、ステップＳ１０５で経路探索手段３９は、目的地ノードへの到着予想時刻と該目的地ノードと目的仮想ノードとを接続する目的仮想リンクの出発時刻を比較して、到着予想時刻が出発時刻より前かを判別する。判別結果が「ＹＥＳ」である時、目的地ノードへの到着が時合いの終了の前であるから、その目的地の推奨時間帯である時合いに間に合うということがわかる。その場合、ステップＳ１０６の処理に進み、滞在時間算出手段３７３は目的仮想リンクの出発時刻を目的地ノードへの到着予想時刻で置換し、目的仮想リンクの出発時刻と到着時刻との間の時間を滞在時間として算出する。この滞在時間が目的地ノードにおいて推奨時間帯である時合いの時間帯の範囲の中で釣りのイベントを実行できる時間を示している。
【０１１８】
経路探索手段３９は、ステップＳ１０７の処理でこの経路を第１経路探索結果として、ステップＳ１０８の処理において第１経路探索結果を案内して処理を終了する。案内の内容は、出発地から目的地への案内経路の他、図１０に示すように、目的地ノードへの到着予想時刻、時合い時間、滞在時間（時合いの範囲内での釣り時間）などである。
【０１１９】
一方、ステップＳ１０５の判別処理において判別結果が「ＮＯ」である場合、目的地ノードへの到着が時合いの終了の後であるから、その目的地の推奨時間帯である時合いに間に合わないことになるから、推奨経路になり得ない。そこで、経路探索手段３９はステップＳ１０９に進み、他に候補経路があるか探索し、他に候補経路があればステップＳ１０５の判別処理に戻る。他に候補経路がなければ該当経路なしとして経路探索を終了する。
【０１２０】
図１１の処理により時合いの終了前に目的地ノードに到着できる経路（第１経路）が探索された。しかしながら、この第１経路は、目的地ノードに推奨時間帯の終了前で、かつ、最も早く到着でき、その時間帯の中で釣りができる経路であるが、推奨時間帯の範囲の中で最も長く釣りができる経路であるとは限らない。このような目的地ノードを探索するためには、図１１の処理に続いて図１２に示す処理を行う。
【０１２１】
先ず、ネットワークデータ編集手段３７は、図１１の処理で探索した第１経路探索結果を得た際に用いた目的仮想リンクを経路探索用ネットワークデータベース３５のネットワークデータ接続から除く（ステップＳ２０１）。その後、経路探索手段３９は目的仮想ノードを目的地とした経路探索を行って第２経路を得て、第２経路における目的地ノードへの到着予想時刻を算出する（ステップＳ２０２）。
【０１２２】
次に、ステップＳ２０３で経路探索手段３９は、目的地ノードへの到着予想時刻と該目的地ノードと目的仮想ノードとを接続する目的仮想リンクの出発時刻を比較して、到着予想時刻が出発時刻より前かを判別する。判別結果が「ＹＥＳ」である時、目的地ノードへの到着が時合いの終了の前であるから、その目的地の推奨時間帯である時合いに間に合うということがわかる。その場合、ステップＳ２０４の処理に進み、滞在時間算出手段３７３は目的仮想リンクの出発時刻を目的地ノードへの到着予想時刻で置換し、目的仮想リンクの出発時刻と到着時刻との間の時間を滞在時間として算出する。
【０１２３】
ステップＳ２０５の判別処理で、経路探索手段３９は、滞在時間が第１経路の滞在時間より大（長い）かを判別する。判別結果が「ＹＥＳ」の場合、今回の経路の滞在時間が第１経路の滞在時間より長いことになり、第１経路を破棄あるいは保存して、新たな第２経路を経路探索結果として選択する。そしてステップＳ２０７で第２経路を探索結果として案内し、処理を終了する。
【０１２４】
ステップＳ２０３の判別処理で判別結果が「ＮＯ」であった場合、あるいは、ステップＳ２０５の判別処理で判別結果が「ＮＯ」であった場合、経路探索手段３９における処理はステップＳ２０８に進み、他に候補経路があるか探索し、他に候補経路があればステップＳ２０３の判別処理に戻る。他に候補経路がなければ該当経路なしとして経路探索を終了する。
【０１２５】
もしも、経路探索結果において、目的地ノードへの到着予想時刻が時合い開始時刻より前である場合には、時合い開始時刻も経路探索結果として表示するとよい。このような経路探索によれば、ユーザが所望する時合いの間に釣りが出来る時間を確保できる釣り場が経路探索結果として表示できる。もし、ユーザが所望する時合いの間に釣りが出来る時間を確保できる時刻に到着できる釣り場がない場合には、その旨を結果に表示する。ここで、時合いの間に釣りが出来る時間は時合いの時間帯を上限にしか設定できないとする。
【０１２６】
図１１の手順および図１２の手順のように行えば、「早く到着して早く釣りが始められるが、釣りに最適な時間帯は短い」釣り場と「遅く到着して釣りを始める時間は遅くなるが、釣りに最適な時間帯は長い」釣り場の２つの経路探索結果を利用者に案内することが可能になる。
【０１２７】
なお、図１２に示す手順においては、第１経路における目的地ノードでの推奨時間帯の範囲内での滞在時間よりも第２経路における滞在時間が長い場合に経路探索結果として第２経路を案内するものであったが、所定の数の目的仮想ノード、目的仮想リンクについて図１１、図１２と同様の手順を繰り返して探索したら経路探索処理を終了し、その間に得られた経路のデータを保存しておき、滞在時間の長い順に候補経路を案内するようにしてもよい。また、目的仮想ノードに接続された目的仮想リンクを用いる経路の全てを探索したら経路探索処理を終了し、その間に得られた経路のデータを目的地ノードへの到着時刻の早い順や目的地ノードでの滞在時間の長い順にソートして案内するようにしてもよい。
【０１２８】
以上、詳細に説明したように、本発明にかかる経路探索システムによれば、釣りのようにその場所その場所ごとに釣りに最適な時間帯が異なっており、さらに釣りをするためにその時間帯に最初から最後まで居る必要がない場合において、魚に対して設定した目的仮想ノードと、目的地ノードである釣り場からその目的仮想ノードへのリンク（目的仮想リンク）を用意し、目的地ノードへの所要時間の最短な経路だけでなく、その目的地ノードにおける釣りに最適な時間帯に、より長く滞在できる目的地ノードの経路探索が可能となる。
【産業上の利用可能性】
【０１２９】
本発明は、複数の場所において同質のイベントを実行することができるが、場所によって当該イベントの実行に適した時間帯や持続時間が異なるようなイベントを実行するに際して、イベントの実行に適した時間帯に到着可能な場所や、その時間帯に到着可能で、且つ、より長い持続時間滞在することができる場所を抽出し、当該場所までの案内経路を探索する場合に適用することができる。
【図面の簡単な説明】
【０１３０】
【図１】本発明の実施例にかかる経路探索システムの構成を示すシステム構成図である。
【図２】本発明の実施例にかかる経路探索システムの詳細な構成を示すブロック図である。
【図３】釣りをイベントとして実行する場合の複数の目的地（釣り場）を示す模式図である。
【図４】イベントデータデータベースに蓄積されるイベントデータの一例を示す図であり、各釣り場における潮汐データを示す図である。
【図５】イベントデータデータベースに蓄積されるイベントデータの一例を示す図であり、各釣り場における推奨時間帯（時合い）のデータを示す図である。
【図６】道路ネットワークのデータの概念を示す模式図である。
【図７】交通ネットワークのデータの概念を示す模式図である。
【図８】図３に示す各釣り場を目的地ノードとし、イベントである釣りの実行の対象である魚を仮想目的ノードとして目的仮想リンクにより接続する概念を説明するめの模式図である。
【図９】目的地ノードと目的仮想ノードを接続する目的仮想リンクを説明するための図である。
【図１０】本発明の実施例にかかる経路探索システムによる経路探索の結果を説明するための図である。
【図１１】本発明の実施例にかかる経路探索システムにおいて、推奨時間帯に目的地に到着可能で推奨時間帯の範囲内であり、イベントの実行が可能な経路を探索する手順を示すフローチャートである。
【図１２】本発明の実施例にかかる経路探索システムにおいて、推奨時間帯に目的地に到着可能であり、推奨時間帯の範囲内で最も長くイベントの実行が可能な経路を探索する手順を示すフローチャートである。
【図１３】異なる複数の場所で開催される等質のイベントの１つに参加するための経路探索の概念を示す図である。
【符号の説明】
【０１３１】
１０・・・・経路探索システム
１２・・・・ネットワーク
２０・・・・携帯端末装置
２０１・・・制御手段
２１・・・・通信手段
２２・・・・ＧＰＳ受信手段
２３・・・・処理要求手段
２４・・・・配信データ記憶手段
２５・・・・表示手段
２６・・・・操作入力手段
２６１・・・目的イベント設定手段
３０・・・・経路探索サーバ
３０１・・・制御手段
３１・・・・通信手段
３２・・・・配信データ編集手段
３３・・・・代替経路探索制御手段
３４・・・・地図データベース
３５・・・・経路探索用ネットワークデータベース
３６・・・・イベントデータデータベース
３７・・・・ネットワークデータ編集手段
３７１・・・目的仮想ノード設定手段
３７２・・・目的仮想リンク設定手段
３７３・・・滞在時間算出手段
３８・・・・処理要求記憶手段
３９・・・・経路探索手段
【要約】
【課題】それぞれ異なる訪問に適した時間帯がある複数の選択できる目的地の中で、出発地から移動して最も適した時間帯に最も長く滞在できる目的地及びその経路を探索する。
【解決手段】複数の目的地を、それぞれ位置情報を有する目的地ノードとし、イベントの対象を目的仮想ノードとして、目的仮想ノードと目的地ノードとを目的仮想リンクで接続したネットワークを生成して経路探索用ネットワークデータに接続する（Ｓ１０３）。目的仮想ノードを選択して経路探索する際、目的仮想ノードが接続される目的地ノードにおける推奨時間帯を抽出し、目的仮想リンクの出発時刻と到着時刻を前記推奨時間帯の終了時刻として設定して最適経路を探索する。目的仮想リンクの出発時刻を探索により得た目的地ノードへの到着予想時刻で置き換え、目的仮想リンクに設定された到着時刻との間の時間を目的地ノードにおける滞在時間として算出する（Ｓ１０６）。
【選択図】図１１【図１】
0004113909.tif 000002
【図２】
0004113909.tif 000003
【図３】
0004113909.tif 000004
【図４】
0004113909.tif 000005
【図５】
0004113909.tif 000006
【図６】
0004113909.tif 000007
【図７】
0004113909.tif 000008
【図８】
0004113909.tif 000009
【図９】
0004113909.tif 000010
【図１０】
0004113909.tif 000011
【図１１】
0004113909.tif 000012
【図１２】
0004113909.tif 000013
【図１３】
0004113909.tif 000014