(57)【特許請求の範囲】
【請求項１】
所望の出発地を設定して、複数の場所および複数の時間帯に開催される同質のイベントに参加するための経路を探索する経路探索システムであって、
前記経路探索システムは、徒歩と交通機関を利用した経路を探索するための経路探索用ネットワークデータと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの開催場所、開催時刻を備えたイベントデータと、イベント参加計画順列作成手段と、を備え、
前記ネットワークデータ編集手段は、前記イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続し、
前記イベントの中から複数の特定のイベントが指定された時、
前記イベント参加計画順列作成手段は、前記指定されたイベントの参加計画順列を作成し、前記経路探索手段は、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内することを特徴とする経路探索システム。
【請求項２】
前記経路探索システムは、前記順列に従って前記経路探索手段が探索した案内経路のデータを、指定されたソート条件に従ってソートして案内することを特徴とする請求項１に記載の経路探索システム。
【請求項３】
前記イベント会場は映画館であり、前記イベントは前記映画館で上映される映画タイトルであることを特徴とする請求項１に記載の経路探索システム。
【請求項４】
所望の出発地を設定する端末装置とネットワークを介して接続され、複数の場所および複数の時間帯に開催される同質のイベントに参加するための経路を探索する経路探索サーバであって、
前記経路探サーバは、徒歩と交通機関を利用した経路を探索するための経路探索用ネットワークデータと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの開催場所、開催時刻を備えたイベントデータと、イベント参加計画順列作成手段と、を備え、
前記ネットワークデータ編集手段は、前記イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続し、
前記イベントの中から複数の特定のイベントが指定された時、
前記イベント参加計画順列作成手段は、前記指定されたイベントの参加計画順列を作成し、前記経路探索手段は、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内することを特徴とする経路探索サーバ。
【請求項５】
前記経路探索サーバは、前記順列に従って前記経路探索手段が探索した案内経路のデータを、前記端末装置により指定されたソート条件に従ってソートして案内することを特徴とする請求項４に記載の経路探索サーバ。
【請求項６】
前記イベント会場は映画館であり、前記イベントは前記映画館で上映される映画タイトルであることを特徴とする請求項４に記載の経路探索サーバ。
【請求項７】
複数の場所および複数の時間帯に開催される同質のイベントに参加するための経路を探索する経路探索サーバとネットワークを介して接続され、所望の出発地を設定する端末装置であって、
前記経路探索サーバは、徒歩と交通機関を利用した経路を探索するための経路探索用ネットワークデータと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの開催場所、開催時刻を備えたイベントデータと、イベント参加計画順列作成手段と、を備え、
前記ネットワークデータ編集手段は、前記イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続し、
前記イベントの中から複数の特定のイベントが指定された時、
前記イベント参加計画順列作成手段は、前記指定されたイベントの参加計画順列を作成し、前記経路探索手段は、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内する経路探索サーバであって、
前記端末装置は、前記イベントのうち、参加を所望する少なくとも２つ以上のイベントを指定する手段を備えたことを特徴とする端末装置。
【請求項８】
前記端末装置は、前記順列に従って前記経路探索手段が探索した案内経路のデータをソートするソート条件を指定する手段を備えたことを特徴とする請求項７に記載の端末装置。
【請求項９】
所望の出発地を設定して、複数の場所および複数の時間帯に開催される同質のイベントに参加するための経路を探索する経路探索システムにおける経路探索方法であって、
前記経路探索システムは、徒歩と交通機関を利用した経路を探索するための経路探索用ネットワークデータと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの開催場所、開催時刻を備えたイベントデータと、イベント参加計画順列作成手段と、を備え、
前記ネットワークデータ編集手段が、前記イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続するステップと、
前記イベントの中から複数の特定のイベントが指定された時、
前記イベント参加計画順列作成手段が、前記指定されたイベントの参加計画順列を作成するステップと、
前記経路探索手段が、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索ステップと、を有し、該当するイベントおよび該イベントの開催場所を案内することを特徴とする経路探索方法。
【請求項１０】
前記経路探索方法は、前記順列に従って前記経路探索手段が探索した案内経路のデータを、指定されたソート条件に従ってソートして案内する処理を含むことを特徴とする請求項９に記載の経路探索方法。
【請求項１１】
前記イベント会場は映画館であり、前記イベントは前記映画館で上映される映画タイトルであることを特徴とする請求項９に記載の経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、映画上映のように、複数の場所および複数の時間帯において同質のイベントが開催される場合に、徒歩と交通機関を利用して前記のようなマルチ開催イベントのうちの少なくとも２つ以上に参加するための最適経路、候補経路などの案内経路を探索する、経路探索システムに関するものである。
本発明は、上記のような経路探索システムにおいて、各イベントの開催場所を、位置情報を有するイベント会場ノードとし、イベントを、位置情報を持たないイベント仮想ノードとして当該イベントが開催されるイベント会場ノードに接続し、イベント会場ノードとイベント仮想ノード間を、イベントの開催時刻に基づくリンクで接続し、イベントの中から、複数の特定のイベントを指定して所望の出発地からの経路探索が要求された場合、該当するイベントの参加計画順列を作成して、順列に従って該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内するようにした経路探索システムに関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
交通機関を利用する経路を探索する経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗り換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。
【０００８】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路経探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００９】
従って端末装置に配信される案内経路データには、利用者が指定した経路探索条件である出発地から目的地までの路線経路や乗車を案内するバス、電車、列車およびその時刻が含まれ、運行時刻表や駅に掲示されるいわゆる駅貼り時刻表などがそのままあるいは必要部分が画面表示できる表示データなどの形式に加工されて端末装置に配信される。端末装置では案内経路のデータや運行時刻表あるいは駅貼り時刻表を表示して経路や乗車すべき交通手段を確認することができる。
【００１０】
交通機関を利用した経路探索を行う経路探索方法は、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に交通ネットワーク経路探索方法として開示されている。この特許文献２に開示された交通ネットワーク経路探索方法は、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する交通ネットワーク経路探索方法である。
【００１１】
この方法においては、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を、緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するようにしている。
【００１２】
徒歩と交通機関を併用した経路探索システムを利用すれば、利用者は、所望の出発地（例えば自宅）から周辺の最寄り駅まで徒歩で移動し、目的地（例えば映画館）の最寄り駅まで交通機関で移動し、更に最寄り駅から目的地（映画館）まで徒歩で移動する、それぞれ最適経路を総合的に探索した結果を案内経路として得ることができる。ところで、映画館を目的地とする場合には、映画鑑賞を目的とするのが自然である。
【００１３】
映画などのイベントに関する情報を一般に提供するシステムは、例えば、下記の特許文献３（特開２００１−３２５５１４号公報）に「サーバ装置」として開示されている。この特許文献３に開示されたサーバ装置は、所望のエリアやジャンルにおける上映映画の映
画紹介情報等を配信可能とするものであり、携帯端末装置から送信されるエリア情報を受信し、このエリア情報に対する映画タイトルの一覧情報を携帯端末装置に送信するように構成されている。
【００１４】
そして、携帯端末装置から送信された、上記一覧情報の内のいずれかの映画タイトルを示す情報を受信し、この受信した情報で示される映画タイトルの映画の映画紹介情報を携帯端末装置に送信するようにされている。これによって、利用者はサーバ装置から所望のエリア内における映画紹介情報の配信を受けることができるようになる。
【００１５】
映画鑑賞の場合、公開されたばかりの最新の映画の場合、複数の映画館で同じ映画が上映される。この場合、上映時刻は映画館全てで同じではなく、映画館ごとに上階時間が異なるのが一般的である。従って、映画館を目的地として経路探索システムを用いて経路探索する場合には、利用者は、目的地としての映画館を特定する他に、映画の上映開始時刻を念頭において目的地への到着時刻を条件として経路探索を要求する必要がある。
【００１６】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２０００−２５８１８４号公報（図４、図７）
【特許文献３】特開２００１−３２５５１４号公報（図１、図６）
【発明の開示】
【発明が解決しようとする課題】
【００１７】
前述のように、映画鑑賞の場合、公開されたばかりの最新の映画の場合、複数の映画館で同じ映画が上映される。この場合、上映時刻は映画館全てで同じではなく、映画館ごとに上映時刻が異なるのが一般的である。従って、映画館を目的地として経路探索システムを用いて経路探索する場合には、利用者は、目的地としての映画館を特定する他に、映画の上映開始時刻を念頭において目的地への到着時刻を条件として経路探索を要求する必要があり、上記特許文献３に開示されたようなサーバ装置は、映画に関する情報を提供するものであり、目的とする映画を鑑賞するためどの映画館を選択するか、その映画館までの経路をどのような経路とするかは、利用者が決定しなければならないという問題点があった。
【００１８】
また、特許文献２に開示された経路探索システムにおいては、目的地とする映画館の物理的な位置をノードとして徒歩、交通機関を利用してそのノードに到達する最適経路や複数の選択可能な候補経路を探索することはできるが、映画の上映時刻までを考慮した経路探索はできないという基本的な問題点もある。このため、同じ映画を上映する近辺の複数の映画館までの経路を比較検討するためには、それぞれの映画館を目的地として個別に経路探索をする必要が生じる。
【００１９】
徒歩と交通機関を併用した経路探索システムを利用して映画館までの経路を探索した場合、経路探索の結果、目的地として設定した映画館への最適経路の案内を受けて、該当する映画館に行っても、その回の上映は既に満員で入場できないということをよく経験する。その場合、近辺にある他の映画館で同じ映画が上映されていて、そちらの映画館には空席があるという場合がある。このような場合、上記特許文献２に開示された経路探索システムにおいては、前述したように、目的地とする映画館を複数設定してそれぞれの経路を探索しなければならないという問題点がある。
【００２０】
このような問題は、映画鑑賞に限らず、複数の場所および複数の時間帯において同質のイベントが開催される場合に、徒歩と交通機関を利用してマルチ開催イベントの１つに参加するための経路を探索する場合に共通して生ずる問題である。例えば、美容院や病院、レストランなど、複数の場所にほぼ同質のサービスを提供する施設が存在し、サービスを提供する時間帯を予約により決定することができ、予約されていない空き時間帯がデータベース化されているサービスを受けるための経路探索においても同様の問題が生ずる。
【００２１】
このようなイベントの１つに参加するための最適経路の探索は、各イベントの開催場所を、位置情報を有するイベント会場ノードとし、イベントを、位置情報を持たないイベント仮想ノードとして当該イベントが開催されるイベント会場ノードに接続し、イベント会場ノードとイベント仮想ノード間を、イベントの開催時刻に基づくリンクで接続し、前記イベント会場ノードを、交通ネットワークデータを含む経路探索用ネットワークデータに接続して、所望の出発地から参加を希望するイベント仮想ノードまでの経路を探索するようになせば解決することができる。
【００２２】
しかしながら、利用者によっては、同日のうちに複数のイベントに効率よく参加したいという要求を持つ場合がある。例えば、興味を持つ映画タイトルが複数あり、１日のうちにそれらを上映している映画館を効率的に選択して鑑賞したい場合である。このような場合、上記のような経路探索を実施しても、効率の良い最適解が提供される保証はない。
【００２３】
なぜならば、映画タイトルごとに上映する映画館、および上映時間が異なり、同じ映画館で鑑賞したい映画タイトルを上映していたとしても、鑑賞したい映画タイトルの上映時間までに２時間程度の待ち時間が生じてしまう場合もあるからである。別の映画館に移動しても待ち時間を減らすことができれば、効率良く所望の映画タイトルを鑑賞することができる。
【００２４】
本明細書においては、このように複数の場所および複数の時間帯において同質のイベントやサービスが開催されるケースを「マルチ開催イベント」ということとし、本発明は、徒歩と交通機関を利用してマルチ開催イベントのうちの少なくとも２つ以上に参加するための最適経路、候補経路などを探索して案内できる経路探索システムを提供するものである。
【００２５】
本願の発明者は前記の課題を解消すべく種々検討を重ねた結果、イベントの開催場所を、位置情報を有するイベント会場ノードとし、イベントを、位置情報を持たないイベント仮想ノードとして当該イベントが開催されるイベント会場ノードに接続し、イベント会場ノードとイベント仮想ノード間を、イベントの異なる開催時刻に基づく複数のリンクで接続し、イベントの中から、複数の特定のイベントを指定して所望の出発地からの経路探索が要求された場合、該当するイベントの参加計画順列を作成して、順列に従い各イベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内するようになせば、上記問題点を解消し得ることに想到して本発明を完成するに至ったものである。
【００２６】
すなわち、本発明は、複数の場所および複数の時間帯において開催される同質のイベントのうち、少なくともその２つ以上に効率よく参加するための経路を複数の場所を設定することなく簡単に探索して案内できる経路探索システム、経路探索サーバ、端末装置および経路探索方法を提供することを目的とするものである。
【課題を解決するための手段】
【００２７】
前記課題を解決するために、本願の請求項１にかかる発明は、
所望の出発地を設定して、複数の場所および複数の時間帯に開催される同質のイベントに参加するための経路を探索する経路探索システムであって、
前記経路探索システムは、徒歩と交通機関を利用した経路を探索するための経路探索用ネットワークデータと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの開催場所、開催時刻を備えたイベントデータと、イベント参加計画順列作成手段と、を備え、
前記ネットワークデータ編集手段は、前記イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続し、
前記イベントの中から複数の特定のイベントが指定された時、
前記イベント参加計画順列作成手段は、前記指定されたイベントの参加計画順列を作成し、前記経路探索手段は、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内することを特徴とする。
【００２８】
本願の請求項２にかかる発明は、請求項１にかかる経路探索システムにおいて、前記経路探索システムは、前記順列に従って前記経路探索手段が探索した案内経路のデータを、指定されたソート条件に従ってソートして案内することを特徴とする。
【００２９】
本願の請求項３にかかる発明は、請求項１にかかる経路探索システムにおいて、前記イベント会場は映画館であり、前記イベントは前記映画館で上映される映画タイトルであることを特徴とする。
【００３０】
また、本願の請求項４にかかる発明は、
所望の出発地を設定する端末装置とネットワークを介して接続され、複数の場所および複数の時間帯に開催される同質のイベントに参加するための経路を探索する経路探索サーバであって、
前記経路探索サーバは、徒歩と交通機関を利用した経路を探索するための経路探索用ネットワークデータと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの開催場所、開催時刻を備えたイベントデータと、イベント参加計画順列作成手段と、を備え、
前記ネットワークデータ編集手段は、前記イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続し、
前記イベントの中から複数の特定のイベントが指定された時、
前記イベント参加計画順列作成手段は、前記指定されたイベントの参加計画順列を作成し、前記経路探索手段は、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内することを特徴とする経路探索サーバ。
【００３１】
本願の請求５にかかる発明は、請求項４にかかる経路探索サーバにおいて、前記経路探索サーバは、前記順列に従って前記経路探索手段が探索した案内経路のデータを、前記端末装置により指定されたソート条件に従ってソートして案内することを特徴とする。
【００３２】
本願の請求項６にかかる発明は、請求項４にかかる経路探索サーバにおいて、前記イベント会場は映画館であり、前記イベントは前記映画館で上映される映画タイトルであることを特徴とする。
【００３３】
また、本願の請求項７にかかる発明は、
複数の場所および複数の時間帯に開催される同質のイベントに参加するための経路を探索する経路探索サーバとネットワークを介して接続され、所望の出発地を設定する端末装置であって、
前記経路探索サーバは、徒歩と交通機関を利用した経路を探索するための経路探索用ネットワークデータと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの開催場所、開催時刻を備えたイベントデータと、イベント参加計画順列作成手段と、を備え、
前記ネットワークデータ編集手段は、前記イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続し、
前記イベントの中から複数の特定のイベントが指定された時、
前記イベント参加計画順列作成手段は、前記指定されたイベントの参加計画順列を作成し、前記経路探索手段は、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内する経路探索サーバであって、
前記端末装置は、前記イベントのうち、参加を所望する少なくとも２つ以上のイベントを指定する手段を備えたことを特徴とする。
【００３４】
本願の請求項８にかかる発明は、請求項７にかかる端末装置において、
前記端末装置は、前記順列に従って前記経路探索手段が探索した案内経路のデータをソートするソート条件を指定する手段を備えたことを特徴とする。
【００３５】
また、本願の請求項９にかかる発明は、
所望の出発地を設定して、複数の場所および複数の時間帯に開催される同質のイベントに参加するための経路を探索する経路探索システムにおける経路探索方法であって、
前記経路探索システムは、徒歩と交通機関を利用した経路を探索するための経路探索用ネットワークデータと、経路探索手段と、ネットワークデータ編集手段と、前記イベントの開催場所、開催時刻を備えたイベントデータと、イベント参加計画順列作成手段と、を備え、
前記ネットワークデータ編集手段が、前記イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続するステップと、
前記イベントの中から複数の特定のイベントが指定された時、
前記イベント参加計画順列作成手段が、前記指定されたイベントの参加計画順列を作成するステップと、
前記経路探索手段が、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索ステップと、を有し、該当するイベントおよび該イベントの開催場所を案内することを特徴とする。
【００３６】
本願の請求項１０にかかる発明は、請求項９にかかる経路探索方法において、前記経路探索方法は、前記順列に従って前記経路探索手段が探索した案内経路のデータを、指定されたソート条件に従ってソートして案内する処理を含むことを特徴とする。
【００３７】
本願の請求項１１にかかる発明は、請求項９にかかる経路探索方法において、前記イベント会場は映画館であり、前記イベントは前記映画館で上映される映画タイトルであることを特徴とする。
【発明の効果】
【００３８】
請求項１にかかる発明においては、イベントの開催場所を、位置情報を持ったイベント会場ノードとして前記経路探索用ネットワークデータに接続し、前記イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続し、前記イベントの中から複数の特定のイベントが指定された時、
イベント参加計画順列作成手段は、前記指定されたイベントの参加計画順列を作成し、前記経路探索手段は、所望の地点を出発地とし、前記イベント参加順列作成手段が作成した順列に従って、該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内する。
【００３９】
このような構成によれば、複数の場所および複数の時間帯において同質のイベントが開催される場合に、徒歩と交通機関を利用して前記のようなマルチ開催イベントのうちの少なくとも２つ以上に参加するための効率的な案内経路を提供することができるようになる。
【００４０】
請求項２にかかる発明においては、請求項１にかかる経路探索システムにおいて、経路探索システムは、前記順列に従って前記経路探索手段が探索した案内経路のデータを、前記端末装置により指定されたソート条件に従ってソートして案内する。
【００４１】
このような構成によれば、複数の場所および複数の時間帯において同質のイベントが開催される場合に、徒歩と交通機関を利用して前記のようなマルチ開催イベントのうちの少なくとも２つ以上に参加するための効率的な案内経路を提供することができ、利用者は所望の条件に従った案内経路、例えば、時間、運賃などを条件から所望の案内経路を選択することができるようになる。
【００４２】
請求項３にかかる発明においては、請求項１にかかる経路探索システムにおいて、前記イベント会場は映画館であり、前記イベントは前記映画館で上映される映画タイトルである。
【００４３】
このような構成によれば、複数の映画館および複数の時間帯で上映される映画のうち、所望の複数の映画を鑑賞する場合に、徒歩と交通機関を利用して当該複数の映画を鑑賞するための効率的な案内経路を提供することができ、利用者は、映画館で希望の映画を効率よく、限られた時間内に見る計画をたてることができるようになる。
【００４４】
また、請求項４ないし請求項６にかかる発明においては、それぞれ請求項１ないし請求３にかかる経路探索システムを構成する経路探索サーバを提供することができ、請求項７、請求項８にかかる発明においては、それぞれ請求項１、請求項２にかかる経路探索システムを構成する端末装置を提供することができるようになる。また、請求項９ないし請求項１１にかかる発明においては、それぞれ請求項１ないし請求３にかかる経路探索システムにおける経路探索方法を提供することができるようになる。
【発明を実施するための最良の形態】
【００４５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するための経路探索システムを例示するものであって、本発明をこの経路探索システムに特定することを意図するものではなく、請求の範囲に含まれるその他の実施形態の経路探索システムにも等しく適用し得るものである。
【実施例】
【００４６】
本発明の実施例にかかる経路探索システム１０は、図１に示すように、携帯電話やＰＤＡ、ミュージックプレーヤーなどの携帯型端末を用いた端末装置２０と経路探索サーバ３０とがインターネットなどのネットワーク１２を介して接続される構成になっている。なお、本実施例においては、通信型の経路探索、案内経路を提供する経路探索システム１０を具体例として説明するが、本発明はこれに限ることなく、スタンドアロンタイプの経路探索システムになどにも適用可能である。
【００４７】
経路探索サーバ３０は、経路探索のため道路ネットワークのデータを蓄積したデータベース（ＤＢ１）、時刻表データに基づく交通ネットワークのデータを交通ネットワークデータとして蓄積したデータベース（ＤＢ２）、複数の場所および複数の時間帯に開催される同質のイベントに関するデータを蓄積したイベントデータのデータベース（ＤＢ３）、表示用の地図データなどを蓄積したデータベース（ＤＢ４）を備えている。イベントデータはネットワークを介して情報配信サーバ５０から取得することができる。イベントデータの構成については、後述する。
【００４８】
図２は、本発明の実施例にかかる経路探索システム１０の詳細な構成を示すブロック図である。本発明の実施例にかかる経路探索システム１０は、図２のブロック図に示すようにインターネットなどのネットワーク１２を介して通信する端末装置２０と、経路探索サーバ３０と、情報配信サーバ５０を備えて構成されている。
【００４９】
端末装置２０は、経路探索サーバ３０に出発地と目的地などの経路探索条件を設定して経路探索要求を送信し、経路探索サーバ３０は経路探索条件に従って、道路ネットワークデータ３６、交通ネットワークデータ３７からなる経路探索用ネットワークデータ３５を参照して最適経路を探索し、その最適経路を案内経路データに編集して端末装置２０に配信する。
【００５０】
経路探索サーバ３０は、歩行者のためのナビゲーションや自動車のためのカーナビゲーションにおける経路探索のための地図データを含む道路ネットワークデータ３６と交通機関を利用する経路区間を探索するための交通ネットワークデータ３７を蓄積した経路探索用ネットワークデータ３５（データベース）と、前述のイベントデータ３９を蓄積したデータベースとを備えている。
【００５１】
本実施例において、複数の場所および複数の時間帯に開催される同質のイベントとしては、映画を具体的な例として説明する。従来、映画鑑賞しようとする人は、上記特許文献１に開示されたシステム等を利用し、エリア（映画館の所在エリア）やジャンル（映画のカテゴリ）、鑑賞時間帯を選択して鑑賞する映画を決定し、該当映画を上映する映画館の地図の配信を受けるようになっていた。つまり、従来から映画雑誌などに掲載された情報を、最新情報として携帯端末から入手しているのと変わりない。
【００５２】
特に都市部においては、人気のある映画は多くの映画館で封切られ、同じエリアでも複数の映画館で上映され、またあるエリアで満席でもすぐ近くのエリアでは空席があるなど、検索するのはなかなか大変である。また映画館によって上映開始時刻が異なるため、実際にその映画館まで行く経路の所要時間などを考慮すると、選択肢が非常に多くなり自分にとって最適な選択をすることは困難である。
【００５３】
特に、同日のうちに複数のイベントに効率よく参加したいという要求を持つ場合、例えば、興味を持つ映画タイトルが複数あり、１日のうちにそれらを上映している映画館を効率的に選択して鑑賞したい場合には、更に最適な選択することが困難になる。なぜならば、映画タイトルごとに上映する映画館、および上映時間が異なり、同じ映画館で鑑賞したい映画タイトルを上映していたとしても、鑑賞したい映画タイトルの上映時間までに２時間程度の待ち時間が生じてしまう場合もあるからである。別の映画館に移動しても待ち時間を減らすことができれば、効率良く所望の映画タイトルを鑑賞することができる。
【００５４】
そこで、先ず、本発明においては、映画館で行う映画の興行のように、開始時間と終了時間が決まっていて、また複数の場所、複数の時間帯に催されるイベントの複数、例えば、少なくとも２つ以上のイベントに参加する際の経路探索を簡単に行うことができるように構成する。このため、映画上映に関するデータをイベントデータ３９に蓄積する。
【００５５】
イベントデータ３９に蓄積されるデータは、アプリケーションリンク手段４０を起動して、例えば、図３に示すデータ構成に従って、情報配信サーバ５０から収集する。すなわち、イベントの開催場所、映画の場合には映画館ごとにその位置情報（緯度・経度）、各映画館で上映される映画のタイトル（イベントタイトル）、映画のカテゴリ、開催期間を蓄積する。映画館で上映時刻を区切って複数回上映される各イベント（映画上映）を個々のイベントとして識別符号（イベントＩＤ）を付し、その上映開始時刻、終了時刻が記録される。そして各イベントに関して、上映開始時刻、終了時刻に基づくリンク番号が付される。
【００５６】
図３において、映画館Ａ（TheaterＡ）の位置は緯度・経度がそれぞれ（Ｘ１・Ｙ１）であり、上映する映画は映画１（Movie１でカテゴリはRomance：ロマンス）であり、イベントＩＤであるＡ１０１〜Ａ１０４の４回、図３のそれぞれの開始時刻〜終了時刻に従って上映される。映画館Ｂ（TheaterＢ）の位置は緯度・経度がそれぞれ（Ｘ２・Ｙ２）であり、上映する映画は映画館Ａと同じ映画１（Movie１でカテゴリはRomance：ロマンス）であり、イベントＩＤであるＢ１０１〜Ｂ１０４の４回、図３のそれぞれの開始時刻〜終了時刻に従って上映される。
【００５７】
映画１が上映される映画館Ａや映画館Ｂは位置情報（緯度・経度）を持つイベント会場ノードであり、経路探索用のネットワークデータに接続すれば、映画館Ａや映画館Ｂを目的地とする経路を探索することができる。そして、各映画館で上映される映画をイベント仮想ノードとして定義し、上映時刻帯（開始時刻、終了時刻）に基づく異なる複数のリンク（図３のリンクＬ−ＡＭ１等を参照）でイベント会場ノードと接続すると、イベント仮想ノードは交通機関の駅に相当し、個々のリンクはイベント会場ノードである映画館Ａや映画館Ｂを発着駅とする電車と同様に扱うことができる。
【００５８】
ここで、交通ネットワークと異なるのは、イベント仮想ノードが電車の駅のように位置情報を持たない点である。そして、イベント会場ノードとイベント仮想ノードが異なる開催時刻に基づく複数のリンク（図３のリンクＬ−ＡＭ１等を参照）で接続される。このことは、前述したように、イベント会場ノードとイベント仮想ノードを接続するリンクがイベント会場を発駅とし、かつ、イベント仮想ノードを着駅とする電車と同様に定義できることを示している。なお、本発明において、位置情報を持たないイベント仮想ノードとは、位置情報の必要がないノードという意味であり、仮に、何らかの位置情報を付しても、その位置情報を使用することはなく、実質的に位置情報を持たないイベント仮想ノードであればよい。
【００５９】
ネットワークデータ編集手段３８は、端末装置２０から所望の出発地が指定され、イベントである映画が選択されて経路探索要求がなされた場合、イベントデータ３９を参照して、上記のように、指定された映画（イベント）の開催場所（映画館Ａや映画館Ｂ）を、位置情報を持ったイベント会場ノードとして経路探索用ネットワークデータ３５に接続し、各イベントを、位置情報を持たないイベント仮想ノードとして登録し、イベント会場ノードからイベント仮想ノードへはイベントの異なる開催時刻に基づく複数のリンクで接続する編集を行い、経路探索手段３３は編集された経路探索用のネットワークデータを参照して指定された映画を鑑賞するのに最適な案内経路、あるいは、最適な案内経路を含むいくつかの候補経路を案内経路として探索することができる。
【００６０】
このように構成すれば、所望の出発地と特定のイベントが指定されれば、経路探索サーバ３０は、該当するイベントのイベント仮想ノードを目的地とする経路探索を行うことで、そのイベントに参加するための最適経路を探索することができる。このような経路探索方法は本出願人により国際特許出願ＰＣＴ／ＪＰ２００６／３１２２７５として先に出願されている。しかしながら、イベントの複数に参加する場合には、このような経路探索方法を採っても、前述したように最適解を求めるには困難をともなう。
【００６１】
もしも、２０箇所の映画館を対象に４本の映画タイトルを鑑賞する案内経路を探索しようとする場合、映画館の順番だけで２０４ ＝１６万通りあり、これに映画タイトルを観る順番の組み合わせを加えたら、案内経路の探索が困難になることは明らかである。しかも東京の都心部などでは、実際の映画館の数はもっと多く、更に経路探索は困難になる。
【００６２】
本発明においては、経路探索サーバ３０に、イベント参加計画順列作成手段３３１を備え、出発地の他に参加を所望する複数のイベントが指定された時、該当するイベントの参加計画順列を作成して、経路探索サーバはイベント参加計画順列作成手段３３１が作成した順列に従い該当するイベント仮想ノードを順次目的地として案内経路を探索し、該当するイベントおよび該イベントの開催場所を案内するように構成する。
【００６３】
イベント参加計画順列作成手段３３１が作成する順列とは、次のようなものである。
例えば、利用者が参加を所望する映画タイトルがＭ１、Ｍ２の２本である場合、イベント参加計画順列作成手段３３１が作成する順列は、［Ｍ１→Ｍ２，Ｍ２→Ｍ１］の２通りである。
参加を所望する映画タイトルがＭ１、Ｍ２、Ｍ３の３本である場合、イベント参加計画順列作成手段３３１が作成する順列は、３！＝６通りである。
同様に、参加を所望する映画タイトルが４本である場合、イベント参加計画順列作成手段３３１が作成する順列は、４！＝２４通りである。
【００６４】
所望の映画タイトルを４本見るとなると、さすがに順列が多くなるが、それでも２４通りに限定される。
また、特殊な組み合わせとして、映画タイトルが属する特定のカテゴリの中から２本見たいという希望、例えばロマンスのカテゴリに分類される映画タイトルに対して、該当する「Romance」カテゴリから２本選ぶことも可能で、たとえばそのときに上映している「Romance」の作品が６本ある場合は、順番も考慮して６×５＝３０通りが選ばれる。（ここでは、いちおう同じ映画を２回観る態様は除外してある）。
【００６５】
経路探索サーバ３０は、上記のようにしてイベント参加計画順列作成手段３３１が作成する順列に従って、順次該当するイベント仮想ノードを目的地として案内経路を探索する。例えば、参加を所望する映画タイトルがＭ１、Ｍ２の２本である場合、イベント参加計画順列作成手段３３１が作成する順列は、先に述べた通り、［Ｍ１→Ｍ２，Ｍ２→Ｍ１］の２通りである。
【００６６】
経路探索手段３３は、先ず最初の順列［Ｍ１→Ｍ２］の案内経路を探索する。すなわち、先ずイベント仮想ノードをＭ１とし、  出発地  →  イベント仮想ノードＭ１  までの案内経路を１回探索する。その後、先の経路探索で得られたイベント仮想ノードＭ１が接続された映画館ノード→イベント仮想ノードＭ２  までの経路を１回探索する。これにより出発地→イベント仮想ノードＭ１→Ｍ２までの案内経路が探索される。
【００６７】
次いで、経路探索手段３３は次の順列［Ｍ２→Ｍ１］の案内経路を探索する。この探索は順列［Ｍ１→Ｍ２］の案内経路探索と同様である。先ず  イベント仮想ノードをＭ２とし、出発地  →  Ｍ２  までの案内経路を１回探索する。その後、先の経路探索で得られたイベント仮想ノードＭ２が接続された映画館ノード→イベント仮想ノードＭ１  までの経路を１回探索する。これにより出発地→イベント仮想ノードＭ２→Ｍ１までの案内経路が探索される。
【００６８】
このようにして順列に従って順次該当するイベント仮想ノードを目的地とした案内経路を探索することにより、計４回の案内経路の探索で、イベント仮想ノードＭ１→Ｍ２の案内経路と、イベント仮想ノードＭ２→Ｍ１の案内経路との２種類の経路を探索することができる。利用者はこの案内経路に基づいて何れかの経路を選択することができる。
【００６９】
１日に映画タイトルを４本見る場合でも、探索回数は２４通り×４＝９６回であり、映画の上映回数、１タイトルあたりの上映時間からもこのあたりが実用上の上限であり、十分経路探索処理できる。
【００７０】
以上のようにして案内経路を探索し、求めた経路の中から、所要時間の短いもの、運賃の少ないもの、など指定された条件でソートして探索結果を表示する。
なお、映画館の入場料も運賃として扱えば、トータルなコストも表示できる。（映画により、また映画館により料金が異なる場合もある。各映画館の映画の上映１本ごとに仮想リンクがあるので、リンクコストを付与することができる。）
もしも、案内経路が見つからなければ、鑑賞したい映画タイトル本数が多すぎるか、出発が遅すぎるので、その旨を表示して、条件の再入力を促す。
【００７１】
次に、前述のイベント会場ノードやイベント仮想ノードが接続される経路探索用のネットワークデータについて説明する。歩行者のためのナビゲーションや自動車のためのカーナビゲーションにおける経路探索のための道路ネットワークデータ３６は、以下のように構成されている。例えば、道路が図４に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００７２】
すなわち、図４において、Ｎｎ、Ｎｍがノードを示し、Nｍは道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図４では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７３】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図４において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００７４】
図４ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至る可能な経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００７５】
これに対して、交通機関の経路探索のための交通ネットワークデータ３７は以下のように構成されている。例えば、図５に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図５において、Ｎｎ、Ｎｍがノードを示し、Nｍは交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図５では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７６】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図５に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００７７】
図５に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００７８】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
例えば、図５において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００７９】
従って、この経路探索用ネットワークデータ３５に、前述したイベント会場ノード、イベント仮想ノードを接続し、所望の出発地を設定し、参加したいイベント（映画１や映画２）を指定すれば、該当する該イベント仮想ノードを目的地として経路探索手段３３は、通常の経路探索と同様に経路を探索することができる。そして所望の時刻に目的地に到着する（映画鑑賞を終了する）最適経路やいくつかの候補経路を案内経路として探索し、該当するイベント仮想ノードが接続されるイベント会場ノードを案内することができるようになる。
【００８０】
利用者が参加を所望する複数のイベントを指定した時は、前述したように、イベント参加計画順列作成手段が作成した順列に基づき、該当するイベント仮想ノードを順次目的地として内経路を探索し、該当するイベントおよび該イベントの開催場所を案内する。例えば、先に述べたように、参加を所望する映画タイトルがＭ１、Ｍ２の２本である場合、出発地  →  イベント仮想ノードＭ１  で１回探索、その後、Ｍ１の映画館ノード→イベント仮想ノードＭ２  で１回探索し、次いで、イベント仮想ノードをＭ２とし、出発地  →  Ｍ２  で１回探索、その後、Ｍ２１の映画館ノード→イベント仮想ノードＭ１  で１回探索し、計４回の案内経路の探索で２種類の経路を探索することができる。
【００８１】
経路探索サーバ３０は、また、一般の経路探索サーバと同様に、制御手段３１、経路案内手段３２、通信手段３４などを備えて構成されている。制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３４はネットワーク１２を介して端末装置２０などと通信データを送受信するための通信インターフェースである。経路案内手段３２は、経路探索手段３３が探索した案内経路のデータや表示用の地図データ、ガイダンスデータなどを編集して端末装置２０に配信する。
【００８２】
一方、端末装置２０は、制御手段２１、通信手段２２、測位手段２３、表示手段２４、案内経路データ記憶手段２５、配信要求編集手段２６、操作・入力手段２７を備えて構成されている。制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。測位手段２３は、ＧＰＳ受信機を備えＧＰＳ衛星信号を受信、処理してナビゲーション端末装置２０の現在位置（緯度・経度）を測位する。
【００８３】
通信手段２２は、無線通信ユニットを含み、経路探索サーバ３０と通信するためのものである。操作・入力手段２７は、キー、ダイヤル等からなり、端末装置２０を操作するための入力、出発地、目的地などの入力機能として用いられる。表示手段２４は液晶表示パネル等からなり、経路探索サーバ３０から配信された案内経路データの案内経路、地図の表示に使用されるものである。また、表示手段２４はメニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。
【００８４】
配信要求編集手段２６は、操作・入力手段２７を使用して入力された出発地、目的地、あるいは、測位手段２３で測位したナビゲーション端末装置２０の現在位置を出発地として、これらの情報に基づいて、経路探索サーバ３０に送信する経路探索要求を作成するものである。経路探索サーバ３０に、映画などのイベントに参加するための経路探索を要求する場合、利用者は、操作・入力手段２７から、または、表示手段２４に表示されたメニュー画面から、所望の出発地、鑑賞したい映画タイトル（複数の映画タイトル鑑賞を所望する場合は当該複数の映画タイトル）、所望の日時（所望の日、出発時刻あるいは映画終了時刻など）を指定する。
【００８５】
なお、配信要求編集手段２６は、後述するように、経路探索サーバ３０が映画のカテゴリを示すカテゴリ仮想ノードを経路探索用ネットワークデータ３５に接続する機能を有する場合には、操作・入力手段２７、あるいは、表示手段２４に表示されるメニュー画面を利用して鑑賞したい映画のカテゴリを指定し、該当カテゴリに属する映画タイトルから１本または複数本の映画タイトルを選択し、経路探索サーバ３０に送信する経路探索要求を編集することもできる。
【００８６】
案内経路データ記憶手段２５は、経路探索サーバ３０から配信された経路探索結果である案内経路データ、地図データ、ガイダンスなどを記憶するものであり、これらのデータは必要に応じて案内経路データ記憶手段２５から読み出され、表示手段２４に表示される。一般的には、測位手段２３で測位したナビゲーション端末装置２０の現在位置を含む一定の縮尺、一定の範囲の地図に、案内経路と、ナビゲーション端末装置２０の現在位置を示すマークを重ね合わせて該現在位置マークが表示画面の中心になるように表示する。
【００８７】
測位手段２３によりＧＰＳ衛星信号を受信して測位した現在位置情報（緯度・経度の情報）には誤差が含まれるため、現在位置が案内経路からずれている場合には現在位置を案内経路上に補正するルートマッチング処理や地図上の道路にマッチングするマップマッチング処理が行われる。また、経路探索サーバ３０から配信される案内経路データに音声ガイド（例えば、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージ）のデータが付加されている場合は、スピーカを介して音声メッセージを再生出力してユーザをガイドする。
【００８８】
次に、以上説明した本発明の実施例にかかる経路探索システム１０におけるネットワークデータの編集方法、経路探索方法について詳細に説明する。以下の例では、例えば、現在地（自宅）から最も早く所望の映画を見るための経路探索の例で説明する。
【００８９】
経路探索サーバ３０には、イベントデータ３９に興味対象場所（ＰＯＩ：Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ）の情報として映画館が位置情報付で登録されている。このようなＰＯＩ情報は、各種の情報配信サーバ５０から収集し、ＰＯＩデータとしてイベントデータ３９とは別に蓄積しておいてもよい。ＰＯＩ情報を蓄積したデータベースを備えれば、ＰＯＩ検索サービスを提供することもできる。また、イベントデータ３９には、映画興行を案内するものであるから、各映画館の上映スケジュールもデータとして蓄積されている（図３参照）。
【００９０】
図６は、イベント会場ノードである映画館Ａや映画館Ｂが経路探索用ネットワークデータ３５に接続された状態を模式的に示す図である。図６において実線ＴＲは交通路線区間を、点線ＲＤは徒歩区間（道路区間）を示し、参照符号ＴＡ、ＴＢはイベント会場ノードである映画館Ａ、映画館Ｂを示し、ＳＴは交通路線の各駅を示す。映画館Ａ、映画館Ｂは緯度・経度によって位置が特定されるから、点線で示す道路区間（徒歩区間）によって、最寄りの駅ＳＴのノードに接続することができる。イベント会場ノードは他にも多数あるが図６では代表的に映画館Ａ、映画館Ｂのみを図示している。
【００９１】
図７は、イベント会場ノードＴＡ、ＴＢ（映画館Ａ、映画館Ｂ）などで開催される映画の作品をイベントとして、イベント会場ノードに接続する概念を示す模式図である。なお、理解を容易にするため、図７は図６の経路探索用ネットワークデータ３５に対応するネットワークデータを用いて表現した図としてある。イベントとしては、例えば、映画Ｍ１、映画Ｍ２、映画Ｍ３があり、それぞれにイベント仮想ノードＭ１〜Ｍ３を与える。この仮想ノードは経路探索ネットワークに含まれるが、位置情報は持たない（適当な位置情報をつけても良いが、経路探索上は用いない）。また、これらのイベント仮想ノードには、上映している映画館からリンクを接続する。
【００９２】
リンクは、イベント会場ノードとイベント仮想ノードとを接続するものであり、映画Ｍ１が上映される時間帯（開始時刻と終了時刻）ごとに異なる複数のリンクで接続される。図７では、理解を容易にするために、映画館ＴＡ（イベント会場ノード）で上映される映画１（イベント仮想ノード）を結ぶリンクはリンクＬ−ＡＭ１、映画館ＴＢ（イベント会場ノード）で上映される映画１（イベント仮想ノード）を結ぶリンクはリンクＬ−ＢＭ１のみを図示している（他のリンクは図３を参照）。これらのリンクは片方向リンクであって、映画館から映画に伸びている。これらのリンクには時刻表（開催時間帯）が関連付けてあり、その時刻表には、映画の上映開始時刻と終了時刻が含まれている。この時刻表は図３に示すように、電車などの運行時刻表と同じフォーマットのデータである。
【００９３】
すなわち、電車時刻表に対照すると、イベント会場ノードを発駅、着駅とする時刻表と見なす下記のような時刻表として表現する。
映画Ｍ１  １回目上映    10:00発    12：30着
映画Ｍ１  ２回目上映    13:00発    15：30着
映画Ｍ１  ３回目上映    16:00発    18：30着
映画Ｍ１  ４回目上映    19:00発    21：30着
このようにすれば、あたかも映画館で各上映開始時刻に電車に乗って、上映が終ったら映画仮想ノードに到着するような交通ネットワークに編集される。
【００９４】
また、イベント（映画）のカテゴリにもカテゴリ仮想ノードを設定し、イベント（映画）から該当カテゴリにリンクＬ−Ｍ１Ｒを接続する。例えば、イベントである映画Ｍ１の属するカテゴリ（分野）がロマンス（Romance）である場合、イベント仮想ノードから「Romance」のカテゴリ仮想ノードにリンクＬ−Ｍ１Ｒが接続される。この部分を抜き出して図示したものが図８である。このリンクＬ−Ｍ１Ｒもカテゴリへの片方向リンクであり、この部分のリンクコストは、差が付かないようにコスト０、あるいは一定の値に決めてある。この場合、「Romance」のカテゴリ仮想ノードには、映画２も同じカテゴリに属する映画であれば、この映画２も接続されている。このようにすれば、後述するようにカテゴリ仮想ノード、すなわち、映画のカテゴリを選択して関心ある映画を選択して鑑賞するための経路探索も可能になる。
【００９５】
図７に戻って、現在地Ｓ（例えば自宅）から映画１（Ｍ１）を見たい場合の経路探索を説明すると、現在地Ｓの位置をＧＰＳなどで取得し、現在地Ｓを出発地とし、見たい映画が映画１（Ｍ１）なら目的地を映画１（Ｍ１）のイベント仮想ノードにして経路探索を行う。この経路探索自体は電車の時刻表も考慮した上記特許文献２や特開２００３−２２７７３２号公報に開示された方法によって行うことができる。
【００９６】
例えば、出発地を９：３０に出発するという条件では、その経路探索結果は、図９のようになり、最も早く映画を見ることができる（見終わることが出来る）のは映画館ＴＡの１回目の上映１０：３０であるという探索結果になる。出発地に近いのは映画館ＴＢであるが、上映時刻や移動時間を総合的に考慮すると上記結果が得られたことになる。なお、この探索は試行錯誤を繰り返すのでなく、条件に従って目的地までの最適経路を１回求めることで、最適解が得られるのである。また、経路探索手段３３が最適経路だけでなく、条件を満足するいくつかの候補経路も探索して案内することもできる。候補経路を案内すれば、利用者は、最適経路で特定された映画館が満席であった場合に、第２候補以下の映画館に移動することも検討することができるようになる。
【００９７】
また、見たい映画を直接指定するのではなくて、カテゴリで指定することもできる。
カテゴリの「Romance」を指定すると、Romanceのカテゴリ仮想ノードが目的地になって最適経路探索が行われる。映画２の属するカテゴリがRomanceの場合、Romanceのカテゴリ仮想ノードには映画２も接続されているので、図７のようになり、上映時刻によっては、映画２が最適経路に選ばれることもある。このようにすれば、カテゴリを選択してそのカテゴリに属する複数のイベント（映画）の中から所望の時間帯に鑑賞できる映画館が探索され、その映画に興味が持てれば、希望した時間を映画鑑賞で過ごすことができるようになる。
【００９８】
なお、上記の説明では、一番早く映画を見たいという条件で探索を行ったが、仮想ノードへの到着時刻を条件に探索することで、到着時刻に最も近くなるように映画を見終わる経路を見つけることもできる。
【００９９】
また、上記の説明ではイベントである映画のイベント仮想ノードを目的地とした経路探索を説明したが、その先にまだ経路を期待したいこともある。すなわち、映画館は経由地であって、その先に次の経由地や最終目的地を設定する場合もありうる。そのような用途に対応するためには、イベント仮想ノードを出発点にすることなく、図１０に示すようにそこに至るまでの経路を逆戻りして、実位置を持つノード、すなわち、映画館ＴＡや映画館ＴＢ（イベント会場ノード）まで経路を戻り、そこから次の目的地に至る経路の探索を開始するようにすればよい。
【０１００】
以上の説明は、理解を容易にするため１本の映画タイトルを鑑賞する場合を説明したが、１日の間に複数本の映画タイトルを鑑賞するための経路探索も同様にすることができる。この場合は図１０に示す経路探索の方法を適用することも考えられるが、この方法では１つのイベントと次の目的地の順番を暗黙のうちに決めているため、経路全体では適した解になっていないことがある。
【０１０１】
例えば、複数の映画を１日のうちに連続して鑑賞しようとする利用者も多い。そのような目的で、図１０の方法で第１の映画Ｍ１を探索したあとに、第２の映画Ｍ２の探索を行っても、この順番で見ることが経路全体として効率が良いとは必ずしも言えない。また、図８に示す経路探索方法は、映画のカテゴリを指定する場合の探索方法を示しているが、この経路探索では、カテゴリ仮想ノードに１回到達する経路を探索するものであるが、例えば同じカテゴリの映画から２作品見たいという希望もある。本発明によればこのような経路探索も可能である。
【０１０２】
前述したように、先ず、イベント参加計画順列作成手段３３１が指定されたイベントの順列（イベント仮想ノードを巡る順列）を作成し、その後、経路探索手段３３がこの順列を用いて経路探索することで、実用上、処理可能な経路探索システムを提供することができる。
【０１０３】
図１１は、以上説明した本発明にかかる経路探索システムにおける経路探索処理の手順を示すフローチャートである。端末装置２０においてステップＳ１０１の処理で条件入力画面を表示し、ステップＳ１０２で日時条件を入力する。次いでステップＳ１０３で出発地を、ステップＳ１０４で所望の複数のイベント（例えば、鑑賞したい映画タイトル）を選択し、ステップＳ１０５で案内経路のソート条件（例えば、所要時間の短い順あるいは運賃の安い順など）を入力する。
【０１０４】
以上の条件入力が完了すると、端末装置２０の配信要求編集手段２６は経路探索要求としてこれらの入力条件を編集し、経路探索サーバ３０に経路探索要求を送信する。
端末装置２０から送信された経路探索要求を経路探索サーバ３０が受信すると、ステップＳ１０６の処理においてイベント参加計画順列作成手段３３１は、ステップＳ１０４の条件入力において選択された複数のイベントから該イベントに参加するための順列を作成する。
【０１０５】
順列が作成されると、ステップＳ１０７の処理で、経路探索手段３３は順列に従って各仮想イベントノードを順次目的地として案内経路を探索する。その際、ネットワークデータ編集手段３８が経路探索用ネットワークデータ３５のネットワークデータに選択されたイベントに該当するイベント仮想ノードを接続する処理を行うことは既に説明した通りである。
【０１０６】
ステップＳ１０８の処理においては前記順列の全てについて案内経路の探索が終了したか否かが判別される。順列の全てについて経路探索を終了していなければ、ステップＳ１０７の経路探索処理に戻り、順列の全てについて経路探索を終了していればステップＳ１０９の処理において探索した案内経路を指定されたソート条件に従ってソートする。
【０１０７】
案内経路のソートが完了すると、ステップＳ１１０の処理で経路探索サーバ３０は案内経路のデータを端末装置２０に配信して処理を終了する。端末装置２０は経路探索サーバ３０から配信された案内経路のデータを表示手段２４に表示し、利用者はその中から所望の案内経路を選択する。
【０１０８】
以上、詳細に説明したように、本発明にかかる経路探索システムによれば、所望の複数のイベントを指定することにより限られた時間内で、当該複数のイベントに順次参加することのできる効率的な案内経路を探索して利用者に案内することができるようになる。
【産業上の利用可能性】
【０１０９】
本発明は、映画上映のように、複数の場所および複数の時間帯において同質のイベントが開催される場合に、徒歩と交通機関を利用して前記のようなマルチ開催イベントのうちの少なくとも２つ以上に参加するための効率的な案内経路を提供できるものである。従って例えば、映画館で希望の映画を効率よく、限られた時間内に見る計画を提供でき、一般的なナビゲーション装置の機能に加えたり、映画の案内サイトで本サービスを提供することができる。
【図面の簡単な説明】
【０１１０】
【図１】本発明の実施例にかかる経路探索システムの構成を示すシステム構成図である。
【図２】本発明の実施例にかかる経路探索システムの詳細な構成を示すブロック図である。
【図３】複数の場所および複数の時間帯に開催される同質のイベントに関する情報（イベントデータ）を蓄積するデータベースのデータ構成の一例を示す図である。
【図４】道路ネットワークのデータの概念を示す模式図である。
【図５】交通ネットワークのデータの概念を示す模式図である。
【図６】イベント会場ノードが経路探索用ネットワークデータに接続された状態を示す模式図である。
【図７】イベント会場ノードとイベント仮想ノードとの接続の概念を示す模式図である。
【図８】イベントのカテゴリをカテゴリ仮想ノードとして該当するカテゴリのイベント仮想ノードに接続する概念を示す模式図である。
【図９】図７の地点Ｓを出発点とし、イベントを選択して経路探索した結果を示す模式図である。
【図１０】イベント仮想ノードを経由地とし、その先に別の実位置を持つ地点を最終目的地とする経路探索の概念を示す模式図である。
【図１１】本発明の実施例にかかる経路探索システムにおける経路探索の動作手順を示すフローチャートである。
【符号の説明】
【０１１１】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２１・・・・制御手段
２２・・・・通信手段
２３・・・・測位手段
２４・・・・表示手段
２５・・・・案内経路データ記憶手段
２６・・・・配信要求編集手段
２７・・・・操作・入力手段
３０・・・・経路探索サーバ
３１・・・・制御手段
３２・・・・経路案内手段
３３・・・・経路探索手段
３３１・・・イベント参加計画順列作成手段
３４・・・・通信手段
３５・・・・経路探索用ネットワークデータ
３６・・・・道路ネットワークデータ
３７・・・・交通ネットワークデータ
３８・・・・ネットワークデータ編集手段
３９・・・・イベントデータ
４０・・・・アプリケーションリンク手段
５０・・・・情報配信サーバ
【図１】
0004448532.tif 000002
【図２】
0004448532.tif 000003
【図３】
0004448532.tif 000004
【図４】
0004448532.tif 000005
【図５】
0004448532.tif 000006
【図６】
0004448532.tif 000007
【図７】
0004448532.tif 000008
【図８】
0004448532.tif 000009
【図９】
0004448532.tif 000010
【図１０】
0004448532.tif 000011
【図１１】
0004448532.tif 000012