(57)【要約】  異なるタイムゾーンに跨がる経路の探索処理を容易に行うことができる経路探索システムを提供することを目的とする。経路探索システム（10）は、交通ネットワークを構成する各ノードに対応付けて該ノードが属するタイムゾーンの情報を記憶するタイムゾーンデータ記憶手段（42）と、交通機関の時刻表データであって、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データを記憶する基準時時刻表データ記憶手段（44）と、出発地点または目的地点の属するタイムゾーンを決定するタイムゾーン決定手段（34）と、時刻変換手段（40）と、を備え、経路探索手段（38）は、交通ネットワークデータと基準時時刻表データに基づいて、出発地点から目的地点までの経路を探索し、時刻変換手段（40）は、出発地点または目的地点の属するタイムゾーンに基づいて、探索した経路の時刻データを変換して案内経路データとする。
2010067458.tif 000002
【特許請求の範囲】
【請求項１】
ノードとノード間を繋ぐリンクとで構成された交通ネットワークデータを記憶する経路探索用ネットワークデータ記憶手段と、出発地点および目的地点を設定するための地点設定手段と、前記交通ネットワークデータを用いて前記出発地点から目的地点までの経路探索を行う経路探索手段と、を備えた経路探索システムにおいて、
前記経路探索システムは、前記交通ネットワークを構成する各ノードに対応付けて該ノードが属するタイムゾーンの情報を記憶するタイムゾーンデータ記憶手段と、交通機関の時刻表データであって、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データを記憶する基準時時刻表データ記憶手段と、前記出発地点または目的地点の属するタイムゾーンを決定するタイムゾーン決定手段と、時刻変換手段と、を備え、
前記経路探索手段は、前記交通ネットワークデータと前記基準時時刻表データに基づいて、前記出発地点から目的地点までの経路を探索し、前記時刻変換手段は、前記出発地点または目的地点の属するタイムゾーンに基づいて、前記探索した経路の時刻データを変換して案内経路データとすることを特徴とする経路探索システム。
【請求項２】
前記経路探索システムは、前記地点設定手段によって設定された地点から最も近い距離にある最短ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検索手段により検索された最短ノードのタイムゾーンを取得する最短ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記最短ノードタイムゾーン取得手段が取得した最短ノードのタイムゾーンを、前記設定した地点のタイムゾーンとして決定することを特徴とする請求項１に記載の経路探索システム。
【請求項３】
前記経路探索システムは、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検出手段により検索された近傍ノードのタイムゾーンを取得する近傍ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記近傍ノードタイムゾーン取得手段が取得した近傍ノードのタイムゾーンのうち最も多数を占めるタイムゾーンを、前記設定した地点のタイムゾーンとして決定することを特徴とする請求項１に記載の経路探索システム。
【請求項４】
前記経路探索システムは、前記ノード検索手段は、前記最短ノードを検索するとともに、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段と、ノード抽出手段と、を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする請求項２に記載の経路探索システム。
【請求項５】
前記経路探索システムは、ノード抽出手段を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする請求項３に記載の経路探索システム。
【請求項６】
前記経路探索システムは、前記地点設定手段によって設定された地点から相対的に近い所定の距離範囲内にある近傍ノードを検索するノード検索手段を備え、前記経路探索手段は、前記ノード検索手段によって検索された全ての近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする請求項１に記載の経路探索システム。
【請求項７】
ノードとノード間を繋ぐリンクとで構成された交通ネットワークデータを記憶する経路探索用ネットワークデータ記憶手段と、出発地点および目的地点を設定するための地点設定手段と、前記交通ネットワークデータを用いて前記出発地点から目的地点までの経路探索を行う経路探索手段と、を備えた経路探索サーバにおいて、
前記経路探索サーバは、前記交通ネットワークを構成する各ノードに対応付けて該ノードが属するタイムゾーンの情報を記憶するタイムゾーンデータ記憶手段と、交通機関の時刻表データであって、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データを記憶する基準時時刻表データ記憶手段と、前記出発地点または目的地点の属するタイムゾーンを決定するタイムゾーン決定手段と、前記時刻変換手段と、を備え、
前記経路探索手段は、前記交通ネットワークデータと前記基準時時刻表データに基づいて、前記出発地点から目的地点までの経路を探索し、前記時刻変換手段は、前記出発地点または目的地点の属するタイムゾーンに基づいて、前記探索した経路の時刻データを変換して案内経路データとすることを特徴とする経路探索サーバ。
【請求項８】
前記経路探索サーバは、前記地点設定手段によって設定された地点から最も近い距離にある最短ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検索手段により検索された最短ノードのタイムゾーンを取得する最短ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記最短ノードタイムゾーン取得手段が取得した最短ノードのタイムゾーンを、前記設定した地点のタイムゾーンとして決定することを特徴とする請求項７に記載の経路探索サーバ。
【請求項９】
前記経路探索サーバは、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検出手段により検索された近傍ノードのタイムゾーンを取得する近傍ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記近傍ノードタイムゾーン取得手段が取得した近傍ノードのタイムゾーンのうち最も多数を占めるタイムゾーンを、前記設定した地点のタイムゾーンとして決定することを特徴とする請求項７に記載の経路探索サーバ。
【請求項１０】
前記経路探索サーバは、前記ノード検索手段は、前記最短ノードを検索するとともに、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段と、ノード抽出手段と、を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする請求項８に記載の経路探索サーバ。
【請求項１１】
前記経路探索サーバは、ノード抽出手段を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする請求項９に記載の経路探索サーバ。
【請求項１２】
前記経路探索サーバは、前記地点設定手段によって設定された地点から相対的に近い所定の距離範囲内にある近傍ノードを検索するノード検索手段を備え、前記経路探索手段は、前記ノード検索手段によって検索された全ての近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする請求項７に記載の経路探索サーバ。
【請求項１３】
ノードとノード間を繋ぐリンクとで構成された交通ネットワークデータを記憶する経路探索用ネットワークデータ記憶手段と、出発地点および目的地点を設定するための地点設定手段と、前記交通ネットワークデータを用いて前記出発地点から目的地点までの経路探索を行う経路探索手段と、を備えた経路探索サーバにおける経路探索方法において、
前記経路探索サーバは、前記交通ネットワークを構成する各ノードに対応付けて該ノードが属するタイムゾーンの情報を記憶するタイムゾーンデータ記憶手段と、交通機関の時刻表データであって、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データを記憶する基準時時刻表データ記憶手段と、前記出発地点または目的地点の属するタイムゾーンを決定するタイムゾーン決定手段と、時刻変換手段と、を備え、
前記経路探索手段が、前記交通ネットワークデータと前記基準時時刻表データに基づいて、前記出発地点から目的地点までの経路を探索するステップと、時刻変換手段が、前記出発地点または目的地点の属するタイムゾーンに基づいて、前記探索した経路の時刻データを変換して案内経路データとするステップと、を有することを特徴とする経路探索方法。
【請求項１４】
前記経路探索サーバは、前記地点設定手段によって設定された地点から最も近い距離にある最短ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検索手段により検索された最短ノードのタイムゾーンを取得する最短ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記最短ノードタイムゾーン取得手段が取得した最短ノードのタイムゾーンを、前記設定した地点のタイムゾーンとして決定するステップを有することを特徴とする請求項１３に記載の経路探索方法。
【請求項１５】
前記経路探索サーバは、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検出手段により検索された近傍ノードのタイムゾーンを取得する近傍ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記近傍ノードタイムゾーン取得手段が取得した近傍ノードのタイムゾーンのうち最も多数を占めるタイムゾーンを、前記設定した地点のタイムゾーンとして決定するステップを有することを特徴とする請求項１３に記載の経路探索方法。
【請求項１６】
前記経路探索サーバは、前記ノード検索手段は、前記最短ノードを検索するとともに、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段と、ノード抽出手段と、を備え、前記ノード抽出手段が、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出するステップと、経路探索手段が、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索するステップとを、有することを特徴とする請求項１４に記載の経路探索方法。
【請求項１７】
前記経路探索サーバは、ノード抽出手段を備え、前記ノード抽出手段が、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出するステップと、経路探索手段が、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索するステップと、を有することを特徴とする請求項１５に記載の経路探索方法。
【請求項１８】
前記経路探索サーバは、前記地点設定手段によって設定された地点から相対的に近い所定の距離範囲内にある近傍ノードを検索するノード検索手段を備え、前記経路探索手段が、前記ノード検索手段によって検索された全ての近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索するステップを有することを特徴とする請求項１３に記載の経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意の出発地から目的地に至る交通機関を用いた経路区間を含む経路を探索して案内する経路探索システムに関するものであり、特に、交通機関を用いた経路区間を探索するための交通ネットワークデータを含む経路探索用ネットワークデータと、異なるタイムゾーンに属する交通機関の時刻表情報を特定の基準時に基づいて変換した基準時時刻表データと、を備え、出発地と目的地とが異なるタイムゾーンに跨がる場合に、前記基準時時刻表データと経路探索用ネットワークデータに基づいて、前記出発地から目的地までの経路を探索するようにした経路探索システムに関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。【０００６】
また、下記の特許文献２（特開２０００−２５８１８４号公報）には、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定するようにした経路探索システムの発明が開示されている。【０００７】
交通機関を利用する経路を探索する経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。【０００８】
また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。【０００９】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。【００１０】
ところで、地球上の各地域はグリニッジ標準時刻を基準時刻としたタイムゾーンに分けられており、交通機関の時刻表データはそれぞれの地域のタイムゾーンに応じた現地の時刻（前記グリニッジ標準時刻からの時差を加味した時刻）で作成されている。一般的な経路探索システムは、基本的に一つのタイムゾーン内における経路探索を想定しており、出発地点と目的地点とが属するタイムゾーンが異なるケースは想定されていない。【００１１】
すなわち、出発地点と目的地点のタイムゾーンが異なる場合において、上記一般的な経路探索システムを用いると、出発時刻を設定して探索を行った場合、目的地到着時刻が目的地点の属するタイムゾーンを基準とした時刻で表示されず、また逆に、目的地到着時刻を設定して探索を行った場合、出発時刻が出発地点の属するタイムゾーンを基準とした時刻で表示されないという問題がある。【００１２】
また、電車などのように出発時刻、到着時刻が決まっている移動手段を用いる場合、出発地点の属するタイムゾーンを基準とした時刻データ、と、目的地点の属するタイムゾーンを基準とした時刻データ、という基準の異なる時刻データを用いて経路探索を行うことになる。従って、経路が異なるタイムゾーンに跨がる場合には、経路探索の過程で、各ノード（経路上の地点）のタイムゾーンを判別しながら、かつ、異なるタイムゾーン間の時刻を換算しながら経路探索することが必要になり、容易には経路探索ができないという問題がある。【００１３】
タイムゾーンの相違を考慮した経路探索システムとしては、例えば、下記の特許文献３（特開２００５−１２１４２５号公報）に車載用ナビゲーション装置の発明として開示されている。この特許文献３に開示された車載用ナビゲーション装置は、通行時間帯に制限があるような道路が探索経路上に存在し、当該道路が出発地と異なるタイムゾーンに属する場合にも制限時間を時差換算して経路探索できるようにしたものである。【００１４】
すなわち、この車載用ナビゲーション装置は、地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを含む地図データを記憶する記憶装置を有している。そして、出発地と目的地を設定し、地図データを用いて出発地から目的地までの間の推奨経路を探索する。経路探索は、時間規制情報とタイムゾーン情報とに基づいて、そのリンクの到着予想時刻において時間規制されているリンクを除外して行うように構成されている。また、各リンクは、異なるタイムゾーンに跨って存在しないようするため、異なるタイムゾーンに跨って存在するリンクを、タイムゾーン境界線で分割した複数のリンクとして扱うように構成されている。【００１５】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２０００−２５８１８４号公報（図４、図６）
【特許文献３】特開２００５−１２１４２５号公報（図１０、図１１）
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記特許文献３に開示された技術においては、異なるタイムゾーンを跨ぐリンクについてはタイムゾーンを特定することができないため、タイムゾーンの境界に新たなノードを設けてリンクを分割して、それぞれの属するタイムゾーンを示す情報とともにネットワークデータを作成する必要があり、既存の経路探索用のネットワークデータを利用することができないという問題点が生じる。【００１７】
特に、交通機関を用いる経路区間を含む経路を探索する場合、各リンクは時刻表データに従って運行される電車や航空機、船舶などの個々の交通手段毎に異なるリンクデータとして表現されるため、分割するリンク数が膨大になり、データ量が大量になるという問題点もある。【００１８】
また、経路探索の過程においてノード、リンクを辿る毎に該ノード、リンクが属するタイムゾーンを判定しながら経路探索をする必要がある。すなわち、直前のノード、リンクとその次のノード、リンクの属するタイムゾーンが異なる場合、時差換算をしながら経路探索をすることが必要になり、経路探索処理の負荷が増大するという問題点もある。【００１９】
更に、上記特許文献３に開示された技術を用いた場合、出発地や目的地の設定にノードを指定する場合には、当該ノードに接続されるリンクにタイムゾーンの情報を付加しているのでノードの属するタイムゾーンを特定することができるが、所望の地点を緯度、経度で指定したり、所望のＰＯＩ（興味対象場所：Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ）を選択して指定したりする場合、設定された地点が属するタイムゾーンを判定するための情報が必要になるという問題点も生じる。【００２０】
本願の発明者は、上記の問題点を解消すべく種々検討を重ねた結果、交通機関をノードとノード間を繋ぐリンクで表した交通ネットワークデータと、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データと、各ノードの属するタイムゾーンを対応付けたタイムゾーンデータと、を用い、交通ネットワークデータと基準時時刻表データを用いて出発地点から目的地点までの経路を探索し、出発地点または目的地点の属するタイムゾーンに基づいて探索した経路の出発地点または目的地点における時刻データ変換して案内経路データとするようにした経路探索システムに関するものである。【００２１】
すなわち、本発明は上記の問題点を解消することを課題とし、簡単な構成で異なるタイムゾーンに跨がる経路の探索処理を、容易に行うことができる経路探索システムを提供することを目的とするものである。また、経路探索条件として交通ネットワークデータのノードでない地点が出発地や目的地として設定された場合にも、容易に出発地や目的地の属するタイムゾーンを特定できるようにした経路探索システムを提供することを目的とするものである。
【課題を解決するための手段】
【００２２】
前記課題を解決するために、本願の第１発明は、
ノードとノード間を繋ぐリンクとで構成された交通ネットワークデータを記憶する経路探索用ネットワークデータ記憶手段と、出発地点および目的地点を設定するための地点設定手段と、前記交通ネットワークデータを用いて前記出発地点から目的地点までの経路探索を行う経路探索手段と、を備えた経路探索システムにおいて、
前記経路探索システムは、前記交通ネットワークを構成する各ノードに対応付けて該ノードが属するタイムゾーンの情報を記憶するタイムゾーンデータ記憶手段と、交通機関の時刻表データであって、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データを記憶する基準時時刻表データ記憶手段と、前記出発地点または目的地点の属するタイムゾーンを決定するタイムゾーン決定手段と、時刻変換手段と、を備え、
前記経路探索手段は、前記交通ネットワークデータと前記基準時時刻表データに基づいて、前記出発地点から目的地点までの経路を探索し、前記時刻変換手段は、前記出発地点または目的地点の属するタイムゾーンに基づいて、前記探索した経路の時刻データを変換して案内経路データとすることを特徴とする。【００２３】
本願の第２発明は、第１発明にかかる経路探索システムにおいて、前記経路探索システムは、前記地点設定手段によって設定された地点から最も近い距離にある最短ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検索手段により検索された最短ノードのタイムゾーンを取得する最短ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記最短ノードタイムゾーン取得手段が取得した最短ノードのタイムゾーンを、前記設定した地点のタイムゾーンとして決定することを特徴とする。【００２４】
本願の第３発明は、第１発明にかかる経路探索システムにおいて、前記経路探索システムは、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検出手段により検索された近傍ノードのタイムゾーンを取得する近傍ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記近傍ノードタイムゾーン取得手段が取得した近傍ノードのタイムゾーンのうち最も多数を占めるタイムゾーンを、前記設定した地点のタイムゾーンとして決定することを特徴とする。【００２５】
本願の第４発明は、第２発明にかかる経路探索システムにおいて、前記ノード検索手段は、前記最短ノードを検索するとともに、前記経路探索システムは、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段と、ノード抽出手段と、を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする。【００２６】
本願の第５発明は、第３発明にかかる経路探索システムにおいて、前記経路探索システムは、ノード抽出手段を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする。【００２７】
本願の第６発明は、第１発明にかかる経路探索システムにおいて、前記経路探索システムは、前記地点設定手段によって設定された地点から相対的に近い所定の距離範囲内にある近傍ノードを検索するノード検索手段を備え、前記経路探索手段は、前記ノード検索手段によって検索された全ての近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする【００２８】
本願の第７発明は、
ノードとノード間を繋ぐリンクとで構成された交通ネットワークデータを記憶する経路探索用ネットワークデータ記憶手段と、出発地点および目的地点を設定するための地点設定手段と、前記交通ネットワークデータを用いて前記出発地点から目的地点までの経路探索を行う経路探索手段と、を備えた経路探索サーバにおいて、
前記経路探索サーバは、前記交通ネットワークを構成する各ノードに対応付けて該ノードが属するタイムゾーンの情報を記憶するタイムゾーンデータ記憶手段と、交通機関の時刻表データであって、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データを記憶する基準時時刻表データ記憶手段と、前記出発地点または目的地点の属するタイムゾーンを決定するタイムゾーン決定手段と、時刻変換手段と、を備え、
前記経路探索手段は、前記交通ネットワークデータと前記基準時時刻表データに基づいて、前記出発地点から目的地点までの経路を探索し、時刻変換手段は、前記出発地点または目的地点の属するタイムゾーンに基づいて、前記探索した経路の時刻データを変換して案内経路データとすることを特徴とする。【００２９】
本願の第８発明は、第７発明にかかる経路探索サーバにおいて、前記経路探索サーバは、前記地点設定手段によって設定された地点から最も近い距離にある最短ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検索手段により検索された最短ノードのタイムゾーンを取得する最短ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記最短ノードタイムゾーン取得手段が取得した最短ノードのタイムゾーンを、前記設定した地点のタイムゾーンとして決定することを特徴とする。【００３０】
本願の第９発明は、第７発明にかかる経路探索サーバにおいて、前記経路探索サーバは、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検出手段により検索された近傍ノードのタイムゾーンを取得する近傍ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記近傍ノードタイムゾーン取得手段が取得した近傍ノードのタイムゾーンのうち最も多数を占めるタイムゾーンを、前記設定した地点のタイムゾーンとして決定することを特徴とする。【００３１】
本願の第１０発明は、第８発明にかかる経路探索サーバにおいて、前記経路探索サーバは、前記ノード検索手段は、前記最短ノードを検索するとともに、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段と、ノード抽出手段と、を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする。【００３２】
本願の第１１発明は、第９発明にかかる経路探索サーバにおいて、前記経路探索サーバは、ノード抽出手段を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする。【００３３】
本願の第１２発明は、第７発明にかかる経路探索サーバにおいて、前記経路探索サーバは、前記地点設定手段によって設定された地点から相対的に近い所定の距離範囲内にある近傍ノードを検索するノード検索手段を備え、前記経路探索手段は、前記ノード検索手段によって検索された全ての近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索することを特徴とする。【００３４】
本願の第１３発明は、
ノードとノード間を繋ぐリンクとで構成された交通ネットワークデータを記憶する経路探索用ネットワークデータ記憶手段と、出発地点および目的地点を設定するための地点設定手段と、前記交通ネットワークデータを用いて前記出発地点から目的地点までの経路探索を行う経路探索手段と、を備えた経路探索サーバにおける経路探索方法において、
前記経路探索サーバは、前記交通ネットワークを構成する各ノードに対応付けて該ノードが属するタイムゾーンの情報を記憶するタイムゾーンデータ記憶手段と、交通機関の時刻表データであって、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データを記憶する基準時時刻表データ記憶手段と、前記出発地点または目的地点の属するタイムゾーンを決定するタイムゾーン決定手段と、時刻変換手段と、を備え、
前記経路探索手段が、前記交通ネットワークデータと前記基準時時刻表データに基づいて、前記出発地点から目的地点までの経路を探索するステップと、時刻変換手段が、前記出発地点または目的地点の属するタイムゾーンに基づいて、前記探索した経路の時刻データを変換して案内経路データとするステップと、を有することを特徴とする経路探索方法。【００３５】
本願の第１４発明は、第１３発明にかかる経路探索方法において、前記経路探索サーバは、前記地点設定手段によって設定された地点から最も近い距離にある最短ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検索手段により検索された最短ノードのタイムゾーンを取得する最短ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記最短ノードタイムゾーン取得手段が取得した最短ノードのタイムゾーンを、前記設定した地点のタイムゾーンとして決定するステップを有することを特徴とする。【００３６】
本願の第１５発明は、第１３発明にかかる経路探索方法において、前記経路探索サーバは、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検出手段により検索された近傍ノードのタイムゾーンを取得する近傍ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記近傍ノードタイムゾーン取得手段が取得した近傍ノードのタイムゾーンのうち最も多数を占めるタイムゾーンを、前記設定した地点のタイムゾーンとして決定するステップを有することを特徴とする。【００３７】
本願の第１６発明は、第１４発明にかかる経路探索方法において、前記経路探索サーバは、前記ノード検索手段は、前記最短ノードを検索するとともに、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段と、ノード抽出手段と、を備え、前記ノード抽出手段が、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出するステップと、経路探索手段が、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索するステップとを、有することを特徴とする。【００３８】
本願の第１７発明は、第１５発明にかかる経路探索方法において、前記経路探索サーバは、ノード抽出手段を備え、前記ノード抽出手段が、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出するステップと、経路探索手段が、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索するステップと、を有することを特徴とする。【００３９】
本願の第１８発明は、第１３発明にかかる経路探索方法において、前記経路探索サーバは、前記地点設定手段によって設定された地点から相対的に近い所定の距離範囲内にある近傍ノードを検索するノード検索手段を備え、前記経路探索手段が、前記ノード検索手段によって検索された全ての近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索するステップを有することを特徴とする。
【発明の効果】
【００４０】
第１発明においては、経路探索システムは、前記交通ネットワークを構成する各ノードに対応付けて該ノードが属するタイムゾーンの情報を記憶するタイムゾーンデータ記憶手段と、交通機関の時刻表データであって、ノードの属するタイムゾーンによらず、所定の基準時刻を用いて作成した基準時時刻表データを記憶する基準時時刻表データ記憶手段と、前記出発地点または目的地点の属するタイムゾーンを決定するタイムゾーン決定手段と、時刻変換手段と、を備え、前記経路探索手段は、前記交通ネットワークデータと前記基準時時刻表データに基づいて、前記出発地点から目的地点までの経路を探索し、前記時刻変換手段は、前記出発地点または目的地点の属するタイムゾーンに基づいて、前記探索した経路の時刻データを変換して案内経路データとする。【００４１】
かかる構成によれば、タイムゾーンの境界に新たなノードを設けてリンクを分割して、それぞれの属するタイムゾーンを示す情報とともにネットワークデータを作成する必要がなく、また、電車や航空機、船舶などの個々の交通手段毎に異なるリンクデータとして表現されるが、タイムゾーンによってリンクを分割する必要がなくデータ量を抑制することができる。また、経路探索の過程においてノード、リンクを辿る毎に該ノード、リンクが属するタイムゾーンを判定しながら経路探索をする必要がなくなる。すなわち、直前のノード、リンクとその次のノード、リンクの属するタイムゾーンが異なっても、時差換算をしながら経路探索をする必要がなく、経路探索処理の負荷が増大することもない。【００４２】
第２発明においては、第１発明にかかる経路探索システムにおいて、前記経路探索システムは、前記地点設定手段によって設定された地点から最も近い距離にある最短ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検索手段により検索された最短ノードのタイムゾーンを取得する最短ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記最短ノードタイムゾーン取得手段が取得した最短ノードのタイムゾーンを、前記設定した地点のタイムゾーンとして決定する。【００４３】
かかる構成によれば、経路探索条件として設定された出発地点や目的地点が交通ネットワークのノード、すなわち、鉄道の駅や航空路線の空港でない場合は、経路探索サーバは、設定された地点に最も近い最寄り駅のノードを抽出し、抽出したノードのタイムゾーンを取得して、出発地点や目的地点のタイムゾーンを決定するから、任意の地点が出発地や目的地として設定された場合にも、交通機関を用いた経路区間の起点、終点とそれらの地点の属するタイムゾーンを決定することができる。【００４４】
第３発明においては、第１発明にかかる経路探索システムにおいて、前記経路探索システムは、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段を備え、前記タイムゾーン決定手段は、前記タイムゾーンデータ記憶手段に記憶されたタイムゾーンデータを参照して前記ノード検出手段により検索された近傍ノードのタイムゾーンを取得する近傍ノードタイムゾーン取得手段を含んで構成され、前記地点設定手段が、出発地点または目的地点として前記ノード以外の地点を設定した場合に、前記近傍ノードタイムゾーン取得手段が取得した近傍ノードのタイムゾーンのうち最も多数を占めるタイムゾーンを、前記設定した地点のタイムゾーンとして決定する。【００４５】
かかる構成によれば、経路探索条件として設定された出発地点や目的地点が交通ネットワークのノード、すなわち、鉄道の駅や航空路線の空港でない場合は、経路探索サーバは、設定された地点の近傍の最寄り駅のノードを抽出し、抽出した近傍の最寄り駅のノードのタイムゾーンを取得して、出発地点や目的地点のタイムゾーンを決定するから、任意の地点が出発地や目的地として設定された場合にも、交通機関を用いた経路区間の起点、終点とそれらの地点の属するタイムゾーンを決定することができる。【００４６】
第４発明においては、第２発明にかかる経路探索システムにおいて、前記経路探索システムは、前記ノード検索手段は、前記最短ノードを検索するとともに、前記地点設定手段によって設定された地点から相対的に近い位置にある近傍ノードを検索するノード検索手段と、ノード抽出手段と、を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索する。【００４７】
かかる構成によれば、経路探索条件として設定された出発地点や目的地点が交通ネットワークのノード、すなわち、鉄道の駅や航空路線の空港でない場合は、経路探索サーバは、設定された地点の近傍の最寄り駅のノードを検索し、検索した近傍の最寄り駅のノードのタイムゾーンを取得して、最短ノードのタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出して交通ネットワークを用いた経路区間の探索の起点または終点とするから、タイムゾーンの不明な地点が設定されても容易に経路探索することができ、また、探索した経路の時刻情報をタイムゾーンに応じた時刻に容易に変換することができるようになる。【００４８】
第５発明においては、第３発明にかかる経路探索システムにおいて、前記経路探索システムは、ノード抽出手段を備え、前記ノード抽出手段は、前記ノード検索手段が検索した近傍ノードのタイムゾーンと、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンとを比較し、前記タイムゾーン決定手段が決定した前記地点のタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出し、前記経路探索手段は、前記ノード抽出手段によって抽出された近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索する。【００４９】
かかる構成によれば、経路探索条件として設定された出発地点や目的地点が交通ネットワークのノード、すなわち、鉄道の駅や航空路線の空港でない場合は、経路探索サーバは、設定された地点の近傍の最寄り駅のノードを検索し、検索した近傍の最寄り駅のノードのタイムゾーンを取得して、最寄り駅のノードのタイムゾーンのうち、最も多数を占めるタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出して交通ネットワークを用いた経路区間の探索の起点または終点とするから、タイムゾーンの不明な地点が設定されても容易に経路探索することができ、また、探索した経路の時刻情報をタイムゾーンに応じた時刻に容易に変換することができるようになる。【００５０】
第６発明においては、第１発明にかかる経路探索システムにおいて、経路探索システムは、前記地点設定手段によって設定された地点から相対的に近い所定の距離範囲内にある近傍ノードを検索するノード検索手段を備え、前記経路探索手段は、前記ノード検索手段によって検索された全ての近傍ノードを、前記交通ネットワークを用いた経路区間の探索の起点または終点として経路探索する。【００５１】
かかる構成によれば、経路探索条件として設定された出発地点や目的地点が交通ネットワークのノード、すなわち、鉄道の駅や航空路線の空港でない場合は、経路探索サーバは、設定された地点の近傍の最寄り駅のノードを検索し、検索した近傍の最寄り駅を交通ネットワークを用いた経路区間の探索の起点または終点とするから、タイムゾーンの不明な地点が設定されても容易に経路探索することができようになる。【００５２】
第７発明〜第１２発明においては、第１発明〜第６発明にかかる経路探索システムを構成する経路探索サーバを提供することができるようになり、第１３発明〜第１８発明においては、第７発明〜第１２発明にかかる経路探索サーバを実現するための経路探索方法を提供することができるようになる。
【図面の簡単な説明】
【００５３】
【図１】本発明の実施例にかかる経路情報案内システムの構成を示すシステム構成図である。
【図２】本発明の実施例にかかる端末装置の詳細な構成を示すブロック図である。
【図３】本発明の実施例にかかる経路探索サーバの詳細な構成を示すブロック図である。
【図４】端末装置において経路探索条件の設定の際に表示される条件設定画面の一例を示す図である。
【図５】出発地点の近傍ノードを抽出する手順の概念を説明するための模式図である。
【図６】目的地点の近傍ノードを抽出する手順の概念を説明するための模式図である。
【図７】端末装置において、経路探索結果を表示する経路案内画面の一例を示す図である。
【図８】端末装置において、経路探索結果を表示する経路案内画面の他の一例を示す図である。
【図９】交通ネットワークデータを用いた経路探索の概念を示す模式図である。
【図１０】経路探索の手順を示すフローチャートである。
【図１１】経路探索条件として出発時刻や到着時刻などの時刻条件が設定された場合の経路探索の手順を示すフローチャートである。
【符号の説明】
【００５４】
１０・・・・経路探索システム
１２・・・・ネットワーク
２０・・・・端末装置
２１・・・・制御手段
２２・・・・通信手段
２３・・・・ＧＰＳ受信手段
２４・・・・探索要求手段
２５・・・・配信データ記憶手段
２６・・・・表示手段
２７・・・・操作入力手段
２８・・・・地点設定手段
３０・・・・経路探索サーバ
３１・・・・制御手段
３２・・・・通信手段
３３・・・・配信データ編集手段
３４・・・・タイムゾーン決定手段
３５・・・・ノード検索手段
３６・・・・ノード抽出手段
３７・・・・タイムゾーン比較手段
３８・・・・経路探索手段
３９・・・・探索要求記憶手段
４０・・・・時刻変換手段
４１・・・・地図データ記憶手段
４２・・・・タイムゾーンデータ記憶手段
４３・・・・交通ネットワークデータ記憶手段
４４・・・・基準時時刻表データ記憶手段
４５・・・・ＰＯＩデータ記憶手段
【発明を実施するための最良の形態】
【００５５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するための経路探索システムを例示するものであって、本発明をこの経路探索システムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態の経路探索システムにも等しく適用し得るものである。【００５６】
図１は、本発明の実施例にかかる経路情報配信システムの構成を示すシステム構成図である。本発明の実施例にかかる経路情報配信システム１０は、図１に示すように、携帯電話などの携帯型端末を用いた端末装置２０と、経路探索サーバ３０とがインターネットなどのネットワーク１２を介して接続される構成になっている。経路探索サーバ３０は、表示用の地図データを記憶する記憶手段（ＤＢ１）、鉄道や飛行機などの交通路線をノードとノード間を繋ぐリンクで構成された交通ネットワークデータを記憶する記憶手段（ＤＢ２）、交通ネットワークのノードの属するタイムゾーンを対応付けたタイムゾーンデータを記憶する記憶手段（ＤＢ３）、ノードとリンクの属するタイムゾーンによらず基準時、例えば、グリニッジ標準時を用いて交通機関の運行時刻を表現した時刻表データ（基準時時刻表データ）を記憶する記憶手段（ＤＢ４）を備えている。【００５７】
交通機関の路線ネットワーク、時刻表データなどの運行情報は、ネットワーク１２を介して各鉄道会社等の情報配信サーバ５０から取得することができる。また、経路探索システム１０が徒歩や自動車を用いた経路区間の経路探索も行う場合には、道路や歩行者専用の道路を含む道路ネットワークデータを記憶した記憶手段を備えて構成される。道路ネットワークデータを備えることにより、出発地から目的地までの、徒歩と交通機関を用いた経路を含むトータルの経路探索を行うことができる。【００５８】
経路探索サーバ３０は、端末装置２０から、出発地点、目的地地点を含む経路探索条件を設定した経路探索要求を受信すると、交通ネットワークデータと基準時時刻表データを用いて出発地点から目的地点までの経路を探索する。そして、出発地点または目的地点の属するタイムゾーンをタイムゾーンデータに基づいて決定し、探索した経路の時刻データを変換する。【００５９】
経路の時刻データとは、例えば、出発地点における電車の出発時刻や目的地地点に到着する電車の到着時刻、あるいは乗換え地点の到着時刻や出発時刻であり、その時刻を出発地点や目的地点の属するタイムゾーンに基づいた時刻データに変換して案内経路のデータとする。すなわち、本発明においては、交通機関を用いた経路区間を基準時刻（例えば、グリニッジ標準時）に基づいて作成された基準時時刻表データを用いて探索し、探索された経路の時刻データを、出発地点や目的地点の属するタイムゾーンに従って変換して案内経路とする。【００６０】
このようにすれば、タイムゾーンの境界に新たなノードを設けてリンクを分割して、それぞれの属するタイムゾーンを示す情報とともにネットワークデータを作成する必要がなく、また、電車や航空機、船舶などの個々の交通手段毎に異なるリンクデータとして表現されるが、タイムゾーンによってリンクを分割する必要がなくデータ量を抑制することができる。【００６１】
更に、経路探索の過程においてノード、リンクを辿る毎に該ノード、リンクが属するタイムゾーンを判定しながら経路探索をする必要がなくなる。すなわち、直前のノード、リンクとその次のノード、リンクの属するタイムゾーンが異なっても、時差換算をしながら経路探索をする必要がなく、経路探索処理の負荷が増大することもない。【００６２】
経路探索条件として設定された出発地点や目的地点が交通ネットワークのノード、すなわち、鉄道の駅や航空路線の空港である場合は、タイムゾーンデータに該当するノード毎のタイムゾーンが記憶されているから、当該出発地点や目的地点の属するタイムゾーンが特定できる。そうでない場合は、経路探索サーバ３０は、設定された地点に最も近い最寄り駅、あるいは、近傍の最寄り駅などのノードを抽出し、抽出したノードのタイムゾーンを取得して、出発地点や目的地点のタイムゾーンを決定する。ノードの抽出とタイムゾーンの決定の方法には後述するいくつかの方法を採ることができる。これにより、任意の地点が出発地や目的地として設定された場合にも、交通機関を用いた経路区間の起点、終点とそれらの地点の属するタイムゾーンを決定することができる。【００６３】
図２は、図１に示す経路探索システム１０を構成する端末装置２０の構成を示すブロック図である。図３は、図１に示す経路探索システム１０を構成する経路探索サーバ３０の構成を示すブロック図である。【００６４】
図２に示すように、端末装置２０は、制御手段２１、通信手段２２、位置検出のためのＧＰＳ受信手段２３、経路探索サーバ３０に経路探索要求を行うための経路探索要求手段２４、経路探索サーバ３０から受信した案内経路のデータを一時記憶する配信データ記憶手段２５、地図や案内経路を表示する表示手段２６、経路探索条件における出発地や目的地などの地点を設定するための地点設定手段２８を含む操作入力手段２７、ＰＯＩを検索するためのＰＯＩ検索手段２９などを備えて構成されている。【００６５】
制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２２はネットワーク１１を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。【００６６】
ＧＰＳ受信手段２３は、ＧＰＳ衛星からの信号を受信して現在位置を緯度・経度で算出する。表示手段２６は、液晶表示パネル等からなり、経路探索サーバ３０から配信（送信）された案内経路や推奨経路あるいは地図の表示に使用されるものである。また、表示手段２６は、メニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。また、表示手段２６はタッチパネル機能を備え、メニュー画面に表示される項目を指などでタッチすることによって選択できるように構成してもよい。【００６７】
操作入力手段２７は、キー、ダイヤル等からなり、端末装置２０を操作するための入力を行い、探索要求手段２４は、操作入力手段２７により入力された出発地、目的地、あるいは、ＧＰＳ受信手段２３により測位した現在位置情報に基づいて、経路探索サーバ３０に対する経路探索要求を編集し、通信手段２２を介して、経路探索サーバ３０に送信する。地点設定手段２８は、操作入力手段２５のキーなどを用いて、あるいは、表示手段２６に表示されたメニュー画面を用いて経路探索条件のうちの出発地および目的地を設定する手段である。【００６８】
配信データ記憶手段２５は、経路探索サーバ３０から端末装置２０に送信される案内経路や地図データを一時記憶する。配信データ記憶手段２５に記憶された案内経路のデータや地図データは、必要に応じて読み出され、表示手段２６に表示される。このような端末装置２０の構成は、通信型の経路探索システムにおける一般的な端末装置の構成と同様である。【００６９】
一方、経路探索サーバ３０は、図３に示すように、制御手段３１、通信手段３２、配信データ編集手段３３、タイムゾーン決定手段３４、ノード検索手段３５、ノード抽出手段３６、タイムゾーン比較手段３７、経路探索手段３８、探索要求記憶手段３９、時刻変換手段４０、地図データ記憶手段４１、タイムゾーンデータ記憶手段４２、交通ネットワークデータ記憶手段４３、基準時時刻表データ記憶手段４４、ＰＯＩデータ記憶手段４５などを備えて構成されている。【００７０】
制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３２は、ネットワーク１２を介して端末装置２０や各種のＰＯＩ情報を提供するＰＯＩ情報提供サーバ５０、交通機関の時刻表データや路線データ、運行状況データを提供する情報配信サーバ５０などと通信データを送受信するための通信インターフェースであり、端末装置２０からの各種要求を受信し、あるいは、端末装置２０に各種情報を配信する。【００７１】
地図データ記憶手段４１は表示用の地図データを記憶する。交通ネットワークデータ記憶手段４３は、鉄道や飛行機などの交通路線をノードとノード間を繋ぐリンクで構成した交通ネットワークデータを記憶する。タイムゾーンデータ記憶手段４２は、交通ネットワークの各ノードの属するタイムゾーンを対応付けたタイムゾーンデータを記憶する。基準時時刻表データ記憶手段４４は、交通ネットワークデータのノードやリンクの属するタイムゾーンによらず基準時、例えば、グリニッジ標準時を用いて交通機関の運行時刻を表現した時刻表データ（基準時時刻表データ）を記憶する。【００７２】
経路探索サーバ３０は、端末装置２０から、出発地点、目的地地点を含む経路探索条件を設定した経路探索要求を受信すると、端末装置２０の識別情報とともに経路探索条件を探索要求記憶手段３９に一時記憶する。そして、交通ネットワークデータと基準時時刻表データを用いて出発地点から目的地点までの経路を探索する。そして、出発地点または目的地点の属するタイムゾーンをタイムゾーンデータに基づいて決定し、探索した経路の時刻データを変換する。【００７３】
経路の時刻データとは、例えば、出発地点における電車の出発時刻や目的地地点に到着する電車の到着時刻、あるいは乗換え地点の到着時刻や出発時刻であり、その時刻を出発地点や目的地点の属するタイムゾーンに基づいた時刻データに変換して案内経路のデータとする。すなわち、本発明においては、交通機関を用いた経路区間を基準時刻（例えば、グリニッジ標準時）に基づいて作成された基準時時刻表データを用いて探索し、探索された経路の時刻データを、出発地点や目的地点の属するタイムゾーンに従って変換して案内経路とする。これにより端末装置２０の利用者は、探索された案内経路の時刻情報として、出発地あるいは目的地の属するタイムゾーンに応じた時刻情報を得ることができる。【００７４】
端末装置２０から指定された経路探索条件の出発地および目的地が交通ネットワークデータのノード、すなわち、駅や空港であれば、基準時時刻表データ記憶手段４４に記憶された基準時時刻表データと交通ネットワークデータ記憶手段４３に記憶された交通ネットワークデータを用いて基準時刻に統一された時刻表を用いて出発地から目的地までの最適経路や指定された数の候補経路を探索することができる。【００７５】
一方、タイムゾーン決定手段３４は、経路探索条件で設定された出発地または目的地について、タイムゾーンデータ記憶手段４２に記憶されたタイムゾーンデータ、すなわち、交通ネットワークの各ノードの属するタイムゾーンをノードに対応付けて記憶したデータを参照して、出発地または目的地の属するタイムゾーンを決定（特定）する。そして、経路探索サーバ３０は、時刻変換手段４０を用いて、経路探索手段３８が探索した経路（基準時時刻表データに基づく経路の時刻情報を、タイムゾーン決定手段３４が決定した出発地または目的地の属するタイムゾーンに基づいて時刻変換して端末装置２０に送信する。【００７６】
このようにすれば、経路探索はグリニッジ標準時を基準時刻として作成した統一的な時刻表データを用いて行い、探索の結果得られた経路の時刻情報については、出発地や目的地の属するタイムゾーンを特定し基準時刻から時刻換算した現地時刻を用いて端末装置２０に提供することができるようになる。経路探索条件に出発地の出発時刻や目的地への到着時刻などの時刻条件が設定されている場合、タイムゾーン決定手段３４が決定したタイムゾーンに基づいて、時刻変換手段４０は、設定された時刻条件を基準時刻に基づいて時差換算した上で経路探索することは勿論である。【００７７】
図４は、端末装置２０において経路探索条件を設定する際に、表示手段２６に表示される条件設定画面４００の一例を示す図である。図４に示す条件設定画面４００には、出発地点入力欄４０１、目的地点入力欄４０２、出発時刻入力欄４０３、到着時刻入力欄４０４、探索開始ボタン４０５が表示される。【００７８】
出発地点と目的地点の設定は、出発地点入力欄４０１、目的地点入力欄４０２に住所や電話番号あるいは駅名称、ビル名称などの地点名称、緯度・経度などを入力して設定する。すなわち、この入力欄は、原則としてフリーワード入力が可能であるが、住所、電話番号、ＰＯＩ（Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ）の名称などで設定することできる。【００７９】
また、プルダウンボタンを操作して、これまでに端末装置２０に登録した経路探索履歴や登録地点を呼び出して設定することもできる。出発時刻入力欄４０３には出発地点を出発する出発時刻を入力する。また、出発時刻には出発の日を出発時刻に含めて入力することもできる。到着時刻入力欄４０４には目的地点への到着時刻を入力する。同様に到着時刻には到着の日を含めて入力することもできる。【００８０】
時刻条件を設定しない場合には設定を省略することができる。図４に示す例は、出発地点として「＃＃ビル」が、目的地として「＊＊ホテル」が設定され、時刻条件として出発地点の出発時刻「１０：００」が設定された例を示している。必要な条件設定を終え、探索開始ボタン４０５を操作すると、経路探索要求が端末装置２０から経路探索サーバ３０に送信される。【００８１】
もしも、端末装置２０において設定された経路探索条件の出発地および目的地が交通ネットワークのノードでない地点である場合、タイムゾーンデータを参照しても当該出発地および目的地の属するタイムゾーンを特定することができない。
その場合、以下に述べる第１または第２の手順の何れかを用いて、設定された地点に対して近傍に位置する交通ネットワークのノードを検索して、検索されたノードから所定の条件によって特定の１つまたは複数のノードを抽出してそのノードのタイムゾーンを特定する。【００８２】
第１の手順は、端末装置２０において地点設定手段２８（図２参照）により設定された地点から最短距離にある交通ネットワークのノード（最短ノード）をノード検索手段３５により検索し、タイムゾーン決定手段３４は、ノード検索手段３５が検索した最短ノードのタイムゾーンを取得してそのタイムゾーンを、前記設定された地点のタイムゾーンとして特定する。このため、タイムゾーン決定手段３４は、タイムゾーンデータ記憶手段４２を参照して最短ノードの属するタイムゾーンを取得する最短ノードタイムゾーン取得手段（図示していない）を含んで構成される。【００８３】
第２の手順は、端末装置２０において地点設定手段２８（図２参照）により設定された地点から近傍（例えば、一定の距離範囲内）に位置する交通ネットワークのノード（以下、近傍ノードという）ノード検索手段３５により検索する。そして、タイムゾーン決定手段３４は、検索された各々の近傍ノードの属するタイムゾーンを取得し、そのうち最も数の多いタイムゾーンを、前記設定された地点のタイムゾーンとして決定する。このため、タイムゾーン決定手段３４は、タイムゾーンデータ記憶手段４２を参照して各近傍ノードの属するタイムゾーンを取得する近傍ノードタイムゾーン取得手段（図示していない）を含んで構成される。【００８４】
また、端末装置２０において設定された経路探索条件の出発地および目的地が交通ネットワークのノードでない地点である場合、前述の第1または第2の手順で決定した最短ノードのタイムゾーンまたは近傍ノードの属するタイムゾーンのうち最も数の多いタイムゾーンを用いて、ノード抽出手段は、交通機関を利用した経路探索の起点、終点、すなわち、経路探索手段３８が交通ネットワークデータを用いて経路探索するための出発地点および目的地地点となるノードを以下に説明する第１の手順または第２の手順で抽出する。【００８５】
第１の手順は、ノード検索手段３５により、最短ノードとともに複数の近傍ノードを検索し、検索された近傍ノードのうち、タイムゾーン決定手段３４が決定した最短ノードのタイムゾーン（前述の第１の手順によるタイムゾーンの決定を参照）と一致するタイムゾーンに属する近傍ノードのみを抽出して、経路探索手段３８による交通ネットワークを用いた経路区間を探索する際の起点、終点とする。このため、ノード抽出手段３６は、タイムゾーン決定手段３４が決定した最短ノードのタイムゾーンと、ノード検索手段３５が検索した各々の近傍ノードのタイムゾーンを比較するタイムゾーン比較手段３７を含んで構成される。【００８６】
第２の手順は、ノード検索手段３５により、複数の近傍ノードを検索し、検索された近傍ノードのうち、タイムゾーン決定手段３４が決定した最も数の多いタイムゾーンに属するノードのタイムゾーン（前述の第２の手順によるタイムゾーンの決定を参照）と一致するタイムゾーンに属する近傍ノードのみを抽出して、経路探索手段３８による交通ネットワークを用いた経路区間を探索する際の起点、終点とする。このため、ノード抽出手段３７は、タイムゾーン決定手段３４が決定した最多のタイムゾーンに属するノードのタイムゾーンと、ノード検索手段３５が検索した各々の近傍ノードのタイムゾーンを比較するタイムゾーン比較手段３７を含んで構成される。【００８７】
このようにして交通ネットワークを用いた経路区間を探索する際の起点、終点となる複数の近傍ノードを抽出すれば、経路探索手段３８は、地点設定された出発地点の近傍の同一のタイムゾーンに属する近傍ノードのそれぞれを出発地（出発地点の最寄り駅）とし、地点設定された目的地点の近傍の同一タイムゾーンに属する近傍ノードのそれぞれを目的地（目的地点の最寄り駅）として複数の候補経路を探索することができる。従って、設定された地点と最寄りの交通ネットワークのノードの間の徒歩経路区間を含めたトータルの経路探索を、基準時時刻表データを用いて行うことができるようになる。【００８８】
更に、もしも、端末装置２０において設定された経路探索条件の出発地および目的地が交通ネットワークのノードでない地点である場合、設定された出発地点と前述のようにして抽出された出発地点の各近傍ノード（出発地点の最寄り駅）との間の経路、および、設定された目的地点と前述のようにして抽出された目的地点の各近傍ノード（目的地点の最寄り駅）との間の経路（例えば、徒歩経路）は、道路ネットワークデータ（図示せず）を用いて通常の経路探索サーバと同様の手法により探索することができる。このようにすれば、経路探索サーバ３０は、出発地点から目的地点まで、徒歩と交通機関を用いて移動する複数の候補経路を探索して端末装置２０に提供することができるようになる。【００８９】
また、記憶容量は増加するが、経路探索サーバ３０が通常の時刻表データ（交通ネットワークが同一のタイムゾーンに属する場合に当該タイムゾーンの時刻情報）を備えていれば、出発地点と目的地点とが、それぞれ同一のタイムゾーンに属する場合、通常の経路探索サーバと同様の出発地および目的地の属するタイムゾーンに基づく現地時刻による経路を探索することもできる。【００９０】
図５、図６は、端末装置２０において設定された出発地点Ｓ、目的地点Ｇが交通ネットワークのノードでない場合に、それぞれの地点の近傍のノード、すなわち交通ネットワークのノードを抽出する概念を説明する模式図である。図５は、出発地点Ｓの近傍の近傍ノード抽出の概念を、図６は、目的地点Ｇの近傍の近傍ノード抽出の概念を示す。【００９１】
図５、図６において、実線は交通機関の路線、すなわち、交通ネットワークを示しており、交通機関の駅や空港をノード（参照符号Ｎｓ０〜Ｎｓ５等、Ｎｇ０〜Ｎｇ５等）とし、各ノード間を繋ぐリンク（区間）で表現されたものである。参照符号Ｓは端末装置２０において設定された出発地点を示し、参照符号Ｇは端末装置２０において設定された目的地点示す。【００９２】
また、各ノードに対しては、ノードの緯度、経度に基づいて、そのノード位置がグリニッジ標準時に対して設定されたタイムゾーンの何れに属するかを示すタイムゾーンデータがノードに対応付けて記憶されている。図５、図６においては、各ノード毎にＧＭＴ−７やＧＭＴ−８として当該ノードの属するタイムゾーンのデータを付してある。タイムゾーンデータは、図５、図６のように交通ネットワークデータのノードデータに付加して記憶してもよく、交通ネットワークデータ記憶手段４３とは別の記憶手段（タイムゾーンデータ記憶手段４２）にタイムゾーンテーブルの形式で記憶してもよい。【００９３】
図５においては、設定された出発地点Ｓが交通ネットワークのノードでないので、ノード検索手段３５は地点Ｓから直線距離で最短の位置にあるノードＮｓ０（最短ノードという）を検索するか、あるいは、地点Ｓから相対的に近い位置にある（所定の距離範囲内にある）複数の近傍ノードを検索する。図５ではノードＮｓ０〜Ｎｓ５が近傍ノードとして検索されたものとする。【００９４】
ノードが検索されると、タイムゾーン決定手段３４は検索されたノードのタイムゾーンを決定する。最短ノードＮｓ０を検索した場合は、その最短ノードＮｓ０が属するタイムゾーン、ここではタイムゾーンＧＭＴ−８を得て、これを設定された出発地点のタイムゾーンとして決定する。また、複数の近傍ノードＮｓ０〜Ｎｓ５を検索した場合は、各近傍ノードの属するタイムゾーンを調べ、最も多数を占めるタイムゾーンを出発地点のタイムゾーンとして決定する。図５の例ではタイムゾーンＧＭＴ−８が最多であるので、これを出発地点Ｓのタイムゾーンとする。【００９５】
次に、交通機関を用いた経路区間を探索する起点となるノードを選択するために、ノード抽出手段３６は、ノード検索手段３５が検索した近傍ノードノードＮｓ０〜Ｎｓ５のタイムゾーンをタイムゾーン決定手段３４が決定した出発地点Ｓのタイムゾーンと比較し、出発地点Ｓのタイムゾーンと同一のタイムゾーンに属する近傍ノードを抽出する。この例では、出発地点ＳのタイムゾーンがＧＭＴ−８に決定されているので、これと同一のタイムゾーンに属する近傍ノードＮｓ０〜Ｎｓ４が探索の起点のノードとして抽出される。ノードＮｓ５の属するタイムゾーンはＧＭＴ−７であるから探索の起点のノードとしては抽出しない。【００９６】
図６に示す目的地点Ｇのタイムゾーンの決定と、近傍ノードの抽出の手順も、図５において説明した手順と同様である。図６の例では、タイムゾーン決定手段３４が決定する目的地点ＧのタイムゾーンはＧＭＴ−６であり、ノード抽出手段３６が抽出するノードは属するタイムゾーンがＧＭＴ−６であるノードＮｇ０〜Ｎｇ４となる。ノードＮｇ５は属するタイムゾーンがＧＭＴ−７であるから抽出されない。図５、図６に示す例では出発地点Ｓと目的地点Ｇの属するタイムゾーンがそれぞれＧＭＴ−８とＧＭＴ−６であるからタイムゾーンの異なる地点間の経路探索となる。このような例は、大陸を横断するような長距離の経路区間や航空機を用いた経路区間の探索では通常よく起こり得るケースである。【００９７】
このようにして交通機関を用いた経路区間を探索するための起点ノード（出発地点Ｓ側）、終点ノード（目的地点Ｇ側）が抽出されると経路探索手段３８は、基準時時刻表データと交通ネットワークデータを用いて、それぞれの起点ノード、終点ノードの組み合わせについて、両ノード間の経路を探索して複数の候補経路を探索する。探索された経路の時刻情報は、当然基準時刻で表現されたものであるから、時刻変換手段４０は経路の時刻情報を、出発地点Ｓまたは目的地点Ｇの属するタイムゾーンに基づいて、何れかのタイムゾーンの現地時刻に変換して端末装置２０に提供する。【００９８】
なお、出発地点Ｓまたは目的地点Ｇと、ノード抽出手段３６において抽出された近傍ノード（交通ネットワークを用いた経路区間の起点ノードまたは終点ノード）との間の最適経路は、経路探索サーバ３０が通常の道路ネットワークデータを有していれば、該道路ネットワークデータを用いて探索することができるから、出発地点Ｓと各近傍ノード、目的地点Ｇと各近傍ノードとの間の徒歩経路を探索することができ、出発地点Ｓから目的地点Ｇの２地点間のトータルな経路探索が可能である。【００９９】
図７は、端末装置２０において、経路探索の結果を表示する経路案内画面の一例を示す図である。経路案内画面５００には、経路１〜経路Ｎまで候補経路の一覧が表示される。候補経路は、経路探索の起点として抽出されたノード間を移動する交通機関（交通ネットワーク）を利用した経路である。経路１は、１０：１３にＸＹ駅（ＸＹｓｔ）を出発し、１０：４７にＺＷ駅（ＺＷｓｔ）に到着し、乗換えの待ち時間が１４分あり、１１：０１にＺＷ駅（ＺＷｓｔ）を出発し、２２：３６にＵＶ駅（ＵＶｓｔ）に到着する経路である。経路の時刻情報は、出発地点の現地時刻表示（出発地点の属するタイムゾーンに基づく時刻）で表示されている。【０１００】
図７の例は、出発地や目的地の地点として交通ネットワークのノードが設定された場合を示しているが、出発地や目的地として交通ネットワークのノードでない地点が設定され、徒歩経路区間が含まれる場合には、設定された地点と交通ネットワークの最寄りノードまでの経路区間についても表示されることはいうまでもない。【０１０１】
経路案内画面５００には、スクロールボタン５０９が表示され、画面をスクロールして経路２以降の候補経路の情報を参照することができる。また、表示された候補経路の番号をクリックして所望の経路を選択すると、地図や経路の画像を表示し、経路の案内を受けることができる。なお、出発地点から交通機関を用いた経路区間の起点（経路１ではＸＹ駅）までの道路ネットワークを用いた経路区間（例えば、徒歩経路区間）を探索できる場合には、その経路区間を含めた経路表示が行われる。【０１０２】
なお、図７においては、経路全体の時刻情報が、出発地点の現地時刻表示（出発地点について決定されたタイムゾーンに基づく時刻で表示されているが、これに限られるものではない。例えば、目的地点の手前までは出発地点の現地時刻表示（出発地点について決定されたタイムゾーンに基づく時刻で表示し、目的地点の時刻情報を目的地点について決定されたタイムゾーンに基づく時刻で表示してもよく、また、経路全体の時刻情報を目的地点について決定されたタイムゾーンに基づく時刻で表示するようにすることもできる。また、経路の各ノード毎に、当該ノードの属するタイムゾーンに基づいてそれぞれの時刻を換算して現地時刻で表示してもよい。【０１０３】
また、経路の各ノード毎に、当該ノードの属するタイムゾーンに基づいてそれぞれの時刻を換算して現地時刻で表示してもよい。この場合には、各ノードの属するタイムゾーンも同時に表示する。図８は、そのようにして端末装置２０において、経路探索の結果を表示する場合の経路案内画面の一例を示す図である。経路案内画面５００には、経路１〜経路Ｎまで候補経路の一覧が表示される。候補経路は、経路探索の起点として抽出されたノード間を移動する交通機関（交通ネットワーク）を利用した経路である。経路１は、１０：１３にタイムゾーンＡに属するＸＹ駅（ＸＹｓｔ）を出発し、１０：４７にタイムゾーンＡに属するＺＷ駅（ＺＷｓｔ）に到着し、乗換えの待ち時間が１４分あり、１１：０１にＺＷ駅（ＺＷｓｔ）を出発し、８：３６にタイムゾーンＢに属するＵＶ駅（ＵＶｓｔ）に到着する経路である。時刻はそれぞれのノードに属するタイムゾーンに基づく現地時刻で表示される。出発地や目的地として交通ネットワークのノードでない地点が設定され、徒歩経路区間が含まれる場合には、設定された地点と交通ネットワークの最寄りノードまでの経路区間についても表示される。【０１０４】
図９は、交通ネットワークデータを用いた経路探索の概念を示す図である。交通機関の経路探索のための交通ネットワークデータは、図９に示すように、例えば、交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図９において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図９では図示を簡略化するため矢印の向きのリンクのみを図示している。【０１０５】
交通ネットワークでは、図９に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データにより規定される）、リンクコストは時刻表によって定まるリンクの一端のノード（駅）からリンクの他端のノード（駅）までの所要時間になる。【０１０６】
また、交通ネットワークにおいては、個々のリンクが必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間のリンクコストが交通手段により異なる場合もある。【０１０７】
図９に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。【０１０８】
図９に示すような物理的なノード、リンクのデータ（交通ネットワークデータ）を用いて、出発ノード（起点ノード）から目的ノード（終点ノード）までの経路を探索するためには、時刻表データを用いて、個々の電車の時刻情報およびリンクコストを出発ノード（起点ノード）から目的ノード（終点ノード）まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。【０１０９】
例えば、図９において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。【０１１０】
これに対して徒歩や自動者を用いた経路区間を探索するための道路ネットワークデータは、交通ネットワークデータと異なり、道路の物理的な構造ネットワーク（道路の起点、終点、交差点や屈曲点をノードとし、隣接ノード間をリンクとするネットワーク）で構成され、リンクコストはリンクの距離または標準的な移動速度で移動した場合の所要時間で表される。経路探索は、出発地点のノードから目的地点のノードまで到達できる全てノード、リンクを辿り、各リンクの累計コストが最小になる経路を探索する。【０１１１】
次に、以上説明した本発明の実施例にかかる経路探索システムにおける動作手順を説明する。図１０は、経路探索サーバ３０における経路探索の手順を示すフローチャートであり、図１１は、経路探索条件として出発時刻や到着時刻などの時刻条件が設定された場合の経路探索の手順を示すフローチャートである。【０１１２】
端末装置２０の地点設定手段２８（図２参照）によって出発地点及び目的地点が設定されると（ステップＳ１）、その設定データは経路探索要求に編集され、経路探索サーバ３０に送られる。ノード検索手段３５（図３参照）は、その設定された経路探索条件に基づき、設定された出発地点及び目的地点からの距離が短い順に、所定個数（例えば５個）の公共交通機関の交通ネットワーク上のノード（以下、近傍ノードという。）を検索するとともに、出発地点及び目的地点から最も距離の短い位置にあるノード（以下、最短ノードという。）を検索する（ステップＳ２）。【０１１３】
最短ノードが検索されると、タイムゾーン決定手段３４は、タイムゾーンデータ記憶手段４２に記憶されたタイムゾーンデータを参照して、最短ノードのタイムゾーンを取得し（ステップＳ３）、その取得したタイムゾーンを、前記経路探索条件として設定された出発地点または目的地点のタイムゾーンとして決定する（ステップＳ４）。【０１１４】
また、ノード抽出手段３６のタイムゾーン比較手段３７は、タイムゾーンデータ記憶手段４２に記憶されたタイムゾーンデータを参照して、ノード検索手段３５によりされた各近傍ノードのタイムゾーンを取得し（ステップＳ５）、その取得されたタイムゾーンと、前記タイムゾーン決定手段３４が決定したタイムゾーン、すなわち、最短ノードのタイムゾーンとを比較する（ステップＳ６）。【０１１５】
次いで、ノード抽出手段３６は、各近傍ノードのタイムゾーンと最短ノードのタイムゾーンとが異なる場合には（ステップＳ６のＮｏ）、その近傍ノードは経路探索の起点または終点から除外し（ステップＳ７）、近傍ノードのタイムゾーンと最短ノードのタイムゾーンとが同一の場合には（ステップＳ６のＹｅｓ）、その近傍ノードは経路探索の起点または終点として抽出する（ステップＳ８）。ステップＳ６の比較処理は、全ての近傍ノードについて終了するまで繰り返される（ステップＳ９）。【０１１６】
このようにして経路探索の基点となる近傍ノードが抽出されると、その近傍ノードを用いて、経路探索手段３８による経路探索が行われる（ステップＳ１０）。その探索結果は、経路探索サーバ３０から端末装置２０へ送られ、端末装置２０の表示手段２６に表示される（ステップＳ１１）。【０１１７】
ここで、出発時刻または到着時刻が設定されている場合の経路探索処理（ステップＳ１０）の詳細について説明する。図１１は、経路探索条件として出発時刻や到着時刻などの時刻条件が設定された場合の経路探索の詳細な手順を示すフローチャートである。例えば、出発時刻が設定されている場合、当該出発時刻は、図１０のステップＳ４で、タイムゾーン決定手段３４により決定されたタイムゾーンの情報（出発地点のタイムゾーン）を用いて、時刻変換手段４０によって基準時刻に変換される（ステップＳ１０１）。【０１１８】
次に、経路探索手段３８は、ステップＳ１０１の処理で基準時刻に変換された出発時刻を用い、交通ネットワークデータと基準時時刻表データ記憶手段４４に記憶されている基準時刻による時刻表データ（基準時時刻表データ）を用いて経路探索を行う（ステップＳ１０２）。
このとき求められた目的地点への到着時刻は基準時刻のものであるので、目的地点のタイムゾーン情報を用いて現地時刻へ変換される（Ｓ１０３）。【０１１９】
なお、本実施例では、近傍ノードを、出発地点または目的地点からの距離が近い順に所定個数のノードとしたが、近傍ノードの決定方法はこれに限られない。例えば、出発地点または目的地点から所定距離（例えば２ｋｍ）内にある公共交通機関ノードを検索し、近傍ノードとしても良い。この場合、上記所定距離では近傍ノードが検索されない場合には、当該所定距離は、近傍ノードが検索されるまで適宜長く再設定される。【０１２０】
また、上記実施例では、出発地点や目的地点として、ノード以外の地点が設定された例につき説明したが、出発地点や目的地点として交通ネットワークのノード（駅などの地点）を設定した場合にも適用可能であることはいうまでもない。【０１２１】
また、本実施例では、出発地点や目的地点としてノード以外の地点が設定された場合に、その地点のタイムゾーンを決定し、そのタイムゾーンと異なるタイムゾーンに属する近傍ノードを除外して経路探索を行っているが、本発明はこれに限定されるものではない。例えば、検索した近傍ノードの全てについて、タイムゾーンデータを用いて基準時刻への変換を行なって経路探索を行い、探索された経路毎に近傍ノードに付加されたタイムゾーン情報を用いて現地時刻に変換しても良い。【０１２２】
また、上記実施例では、ステップＳ４の処理において設定地点のタイムゾーンを決定するに際し、最短ノードが属するタイムゾーンを用いているが、これに代えて、近傍ノードの属するタイムゾーンのうち最も数の多いタイムゾーンを用いるようにしても良い。【０１２３】
以上、詳細に説明したように、本発明にかかる経路探索システムによれば、出発地点と目的地点のタイムゾーンが互いに異なる場合であっても、交通ネットワークデータを構成する各ノードにタイムゾーンデータが付加されているので、既存の交通ネットワークデータを改変せずに、所定時刻を基準とした時刻で表現されている時刻表データを用いて経路探索を行うことができる。【０１２４】
また、経路探索の際に、リンクあるいはノード同士のタイムゾーンの異同を判断しなくて済むので、経路探索処理が軽くなる。さらに、設定地点から最も近いノードのタイムゾーンを、その設定地点のタイムゾーンとして決定するので、タイムゾーンの決定が容易である。
【図１】
2010067458.tif 000003
【図２】
2010067458.tif 000004
【図３】
2010067458.tif 000005
【図４】
2010067458.tif 000006
【図５】
2010067458.tif 000007
【図６】
2010067458.tif 000008
【図７】
2010067458.tif 000009
【図８】
2010067458.tif 000010
【図９】
2010067458.tif 000011
【図１０】
2010067458.tif 000012
【図１１】
2010067458.tif 000013
【国際調査報告】
2010067458.tif 000014
2010067458.tif 000015
2010067458.tif 000016
2010067458.tif 000017