Notice: Undefined variable: fterm_desc_sub in /mnt/www/biblio_conv.php on line 353
経路探索システム、経路探索方法及びコンピュータプログラム
説明

経路探索システム、経路探索方法及びコンピュータプログラム

【課題】駅構内を考慮した経路探索を可能にする。
【解決手段】経路探索ツール110は、出発地及び目的地の入力を受け付けると、駅情報DB131から、出発地において利用可能な1又は複数の駅出入口の情報と各駅出入口に繋がる改札及び当該改札から到達可能なホームの情報とを取得し、取得した情報に基づいて出発地に代わる出発地条件を生成する。同様に、目的地に代わる目的地条件を生成する。経路探索エンジン113は、運行情報DB132にアクセスして、出発地条件及び目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、出発地から目的地に至る最適経路候補を探索する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、徒歩及び電車等の公共交通網を利用して、任意の出発地から目的地に至る経路を探索する経路探索の技術に関する。
【背景技術】
【0002】
電車等の公共交通網における最適な運行経路の探索技術については、本出願人によって開発された運行経路探索ソフト「駅すぱあと」(登録商標、非特許文献1参照)以来、複数の企業技術者の手により幾多の改良・改善が試みられてきた。この経路探索技術の一つとして、出発地から出発駅及び目的地から目的駅までを結ぶ徒歩経路も考慮して、出発地及び目的地から最も近い駅(最寄り駅)を出発駅及び目的駅として特定した後、さらに、当該出発駅及び目的駅が複数の出入口を有する場合には、出発地及び目的地から最も近い出入口(最寄り出入口)を特定する経路探索方法が存在している。
【0003】
しかしながら、一旦、最寄り駅を特定した後に、当該最寄り駅の最寄り出入口を特定し、経路を探索する上記の方法では、最適経路が探索されない場合がある。
例えば、六本木ヒルズから新高円寺駅までを上記の方法で探索する場合、六本木ヒルズの最寄り駅は「日比谷線の六本木駅」で最寄り出入口は「出入口1c」であるため、最適経路は〈六本木ヒルズ→(徒歩0分)→六本木駅[出入口1c]→(日比谷線)→霞ヶ関→(丸の内線)→新高円寺〉となり、平均所要時間は39分となる。
【0004】
しかし、最寄り駅以外も出発駅の候補とすると、「大江戸線の六本木駅(出入口5)」も候補となり、経路は〈六本木ヒルズ→(徒歩4分)→六本木駅[出入口5]→(大江戸線)→中野坂上→(丸の内線)→新高円寺〉で、平均所要時間は34分となるため、この経路が、総所要時間の短い最適経路となる。
なお、「日比谷線の六本木駅」と「大江戸線の六本木駅」とは行き来することができないため、一旦、最寄り駅である「日比谷線の六本木駅」が出発駅と特定されてしまうと、「大江戸線の六本木駅」から出発する経路は探索されないこととなる。
【0005】
このように、出発地の最寄り駅を出発駅としない最適経路が存在する場合があり、上記のように、一旦、最寄り駅を特定した後に経路探索を行なう方法では、そのような最適経路が探索されないこととなる。
【0006】
他方、1又は複数の駅を出発駅候補又は目的駅候補としておき、当該出発駅候補又は目的駅候補が複数の出入口を有する場合に、出発地及び目的地から徒歩で一番早く到達できる出入口を特定して、当該出入口の位置を出発駅候補又は目的駅候補の位置とみなしたうえで、最適経路を探索する最適経路探索装置も提案されている(特許文献1参照)。
【0007】
この特許文献1に記載された最適経路探索装置では、はじめの段階で、最寄り駅以外の駅を出発駅候補から除外することがないため、最寄り駅を出発駅としない最適経路も探索することができる。また、出入口を複数有する出発駅候補又は目的駅候補については、最寄り出入口を特定するため、出発地から出発駅までを結ぶ徒歩経路と目的駅から目的地までを結ぶ徒歩経路も考慮した最適経路の探索を行なうことができる。
【先行技術文献】
【特許文献】
【0008】
【特許文献1】特開2003−182578号公報
【非特許文献】
【0009】
【非特許文献1】「駅すぱあと」風雲録 柏崎ほか 日経BP社 2006年3月20日発行
【発明の概要】
【発明が解決しようとする課題】
【0010】
特許文献1に記載された装置による経路探索方法は、出発地から出発駅までを結ぶ徒歩経路と目的駅から目的地までを結ぶ徒歩経路とを考慮した経路探索を行なうことができる点で便利である。
【0011】
しかし、駅の構内は、駅ごとに異なった構造となっており、曜日によっては利用できない出入口及び改札があったり、同じ路線でも上りホームと下りホームの間で行き来ができなかったり等、種々の要因により、出入口から所望の電車が発着するホームに至る経路は区々となり、その所要時間も大きく異なってしまう。
【0012】
例えば、同じ路線で上りのホーム側と下りのホーム側のそれぞれに出入口(改札)があり、かつ、上りホームと下りホームの間で行き来できない駅が出発駅であり、出発地からの最寄り出入口が上りホーム側の出入口で、乗車すべき電車が下り電車である場合には、最寄り出入口(上りのホーム側の出入口)から入場する経路が最適経路であるとは限らない。そうであるにも関わらず、特許文献1に記載された装置では、経路探索の際に、出発地から駅の出入口までの徒歩経路は考慮するものの、駅構内、すなわち、出入口から改札及びホームまでの徒歩経路は考慮されていなかった。
【0013】
本発明は、かかる背景のもと、駅構内、すなわち、駅出入口から改札、あるいはホームまでの経路を考慮した最適経路探索の技術を提供することを主たる課題とする。
【課題を解決するための手段】
【0014】
上記課題を解決するため、本発明は、経路探索システム、経路探索方法及びコンピュータプログラムを提供する。
本発明の経路探索システムは、利用者により指定された出発地及び目的地を特定する特定手段と、交通機関の駅の情報を蓄積した駅情報DB(DBはデータベースの略、以下同じ)から、前記特定された出発地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成する条件生成手段と、経路探索用の運行情報DBにアクセスして前記生成された出発地条件及び前記特定された目的地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段とを有するものである。
【0015】
本発明の他の経路探索システムは、利用者により指定された出発地及び目的地を特定する特定手段と、交通機関の駅の情報を蓄積した駅情報DBから、前記特定された目的地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件生成手段と、経路探索用の運行情報DBにアクセスして前記目的地条件及び前記特定された出発地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段とを有するものである。
駅出入口、改札、ホームもノードとして経路探索を行なうことから、駅構内の移動経路を考慮した経路探索を行なうことができる。
【0016】
ある実施の態様では、前記条件生成手段は、前記駅出入口の位置情報、前記駅出入口から前記改札までの移動に要する第1移動コスト、前記改札からホームまでの移動に要する第2移動コストを取得し、取得したこれらの移動コストを新たな条件として付加するように構成されており、前記経路探索手段は、探索された経路毎に、前記位置情報に基づき算出される前記利用可能な駅出入口までの移動に要する第3コストと、前記第1移動コスト及び前記第2移動コストとを合算することにより、経路全体の総移動コストを算出し、この総移動コストが小さい順に前記最適経路候補をソートする。この場合は、探索結果から、特に、総移動コストが小さい経路を選出することが可能となる。
移動コストは、例えば移動時間情報のようなものである。
【0017】
他の実施の態様では、さらに、前記条件生成手段は、前記駅出入口、前記改札又は前記ホームの利用制限情報を取得し、取得した利用制限情報をも出力するように構成されており、前記経路探索手段は、前記利用制限情報に基づき、前記探索された経路のうち利用が制限されている駅出入口、改札又はホームが含まれる最適経路候補を探索結果から除外するように動作する。
【0018】
他の実施の態様では、前記経路探索手段は、前記出発地と前記目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた駅出入口、改札及びホームのいずれかが複数存在する場合に、駅出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該駅出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、前記ノードより除外する最適化処理を行う。構成をより簡略化する観点からは、前記相対的に移動コストの大きい組み合わせが除外された前記出発地又は前記目的地をランドマークとして保持するランドマーク保持手段をさらに備えるようにし、前記経路探索手段は、保持されているランドマークを前記出発地又は前記目的地とした経路探索を行うようにする。
これにより、ランドマークを用いるだけで上記最適化処理が実行されるので、パフォーマンスがより向上する。
【0019】
本発明の経路探索方法は、交通機関の駅の情報を蓄積した駅情報DB及び経路探索用の運行情報DBにアクセス可能なコンピュータが、前記駅情報DBから、利用者に指定された出発地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者に指定された目的地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する処理と、前記運行情報DBにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する処理と、を実行することを特徴とする、コンピュータによる経路探索方法である。
【0020】
本発明のコンピュータプログラムは、交通機関の駅の情報を蓄積した駅情報DB及び経路探索用の運行情報DBにアクセス可能なコンピュータを、前記駅情報DBから、利用者により指定された出発地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者により指定された目的地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件出力手段;前記運行情報DBにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段;として機能させる、経路探索用のコンピュータプログラムである。
【発明の効果】
【0021】
本発明によれば、交通機関の駅名、駅出入口のほか、改札とホームの少なくとも一方をノードに含めて経路探索を行なうので、駅構内の徒歩経路を含む正確な経路探索が可能となるという特有の効果が得られる。改札や駅出入口等の利用制限情報を探索の条件として付加することも可能であり、この場合は、利用不可能な出入口及び改札を経由する経路を探索結果から除外して、実際に利用可能な経路のみの探索結果を得ることができるので、より現実に即した経路探索が可能となる。
経路探索手段がノードの最適化処理を行う構成では、探索ループ回数が減少するので、経路探索時のパフォーマンスが向上する。
【図面の簡単な説明】
【0022】
【図1】第1実施形態の経路探索システムの全体構成図である。
【図2】従来の経路探索処理の概要を示す図である。
【図3】本実施形態の経路探索ツールによる経路探索処理の概要を示す図である。
【図4】改札・出入口テーブルの構造説明図である。
【図5】出入口〜改札間の移動時間テーブルの構造説明図である。
【図6】改札〜ホーム間の移動時間テーブルの構造説明図である。
【図7】経路探索ツールの処理手順図である。
【図8】第2実施形態の経路探索システムにおいて、最適化処理を行う場合の駅構内の説明図である。
【発明を実施するための形態】
【0023】
以下、本発明を、携帯端末向けの経路探索サービスを可能にするネットワーク型の経路探索システムに適用した場合の実施の形態例を説明する。
【0024】
<第1実施形態>
図1は、この実施形態の経路探索システムの全体構成図であり、特徴的な部分を掲示してある。この経路探索システムは、インターネット等のディジタルネットワークNに接続される経路探索サーバ10と、1又は複数の情報端末サービスサーバ20(図示の例では1つ)と、交通機関の駅の情報、例えば駅の出入口(北口、南口、A出口、B出口等:「駅出入口」、以下、単に出入口という)の位置情報(緯度、経度等)、出入口に繋がる改札、改札から到達可能なホーム、利用制限条件等のデータを蓄積した駅情報DB131と、経路探索用の運行情報、例えば交通機関(鉄道/バス)の路線網、時刻表、駅周辺の地図情報等のデータを蓄積した運行情報DB132とを含んで構成される。
ディジタルネットワークNには、携帯端末50の他、メールサーバ60や情報端末の一例となるPC(パーソナルコンピュータ)70も接続可能になっている。
【0025】
携帯端末50及びPC70は、データ通信及びデータ処理機能を有する場合はダイレクトに、また、メール機能を有する場合にはメールサーバ60を通じて、それぞれディジタルネットワークNに接続することができる。
【0026】
[経路探索サーバ]
経路探索サーバ10は、サーバ本体と本発明のコンピュータプログラムとの協働により実現される。すなわち、サーバ本体が、コンピュータプログラムを読み込んで実行することにより、そのサーバ本体を、データ通信用インターフェース100及び経路探索ツール110として機能させ、経路探索のための情報処理を実行可能にする。
【0027】
データ通信用インターフェース100は、データ通信及びデータ処理機能を有する携帯端末50やPC70との双方向通信を可能にするとともに、これらの情報端末が閲覧可能な階層ページ画面を提供する。この階層ページ画面では、経路探索のWebサービスを行なうためのもので、経路探索条件の精緻な指定をシステム側と利用者との間でインタラクティブに行なうことにより、利用者が満足する経路探索を行なう環境を提供する。経路探索の結果情報の表示も、このページ画面で行なうことができる。
【0028】
経路探索ツール110は、探索条件受付部111、条件生成部112及び経路探索エンジン113とを含む。
【0029】
探索条件受付部111は、出発地及び目的地を含む経路探索条件を受け付ける。出発地と目的地の少なくとも一方については、利用者が直接入力(指定)したものをそのまま経路探索条件として特定してもよく、予め登録されているものを提示して選択させることで特定するようにしてもよい。
条件生成部112は、出発地から出発地条件、目的地から目的地条件を生成し、必要に応じて出入口や改札の利用制限情報を付加する。
経路探索エンジン113は、出入口、改札、ホーム、経由駅を、交通機関の路線網を構成するノードに含め、出発地から目的地に向かって各ノードに順次リンクを張ることを繰り返すことにより、経路探索条件に従う1又は複数の経路候補を探索し、経路探索条件に最も適合するものを最適経路候補とする。
【0030】
経路探索エンジン113は、公知の推論エンジンも搭載しており、経路探索途中で、つまりリンクを張り付けていく過程で、所要時間が現実的でなくなる経路となることが判明した場合、例えば予めメモリに記憶された閾値と比べて大きくなった場合は、その時点でその経路候補についての次のノード以降の探索を止める。
経路探索エンジン113は、また、複数の経路候補の各々について、出発地から目的地に至るまでの総移動コスト、例えば時間を移動コストと捉える観点からは総所要時間を算出し、算出された総所要時間の小さい順に、複数の経路をソートする。さらに、経路中にその利用が制限される出入口や改札がある場合には、当該経路を除外したうえで、経路候補を特定する。
【0031】
なお、経路探索エンジン113の基本機能部分は、本出願人が提供している経路探索ソフトウェア「駅すぱあと」(登録商標)を使用することができる。
【0032】
次に、経路探索ツール110による最も一般的な経路探索処理、すなわち出発地と目的地との間の最適経路候補の特定を行なう場合の探索の概要を説明する。なお、ここでは、出発地と出発駅、目的地と目的駅とがそれぞれ異なるものとして説明する。
【0033】
図2は、従来の経路探索処理の概要を示す図であり、図3は、本実施形態の経路探索ツール110による経路探索処理の概要を示す図である。
従来の経路探索ツールは、図2のように、出発地近くの最寄りの1または複数の出発駅候補を特定した後、各出発駅候補の出入口の位置情報に基づき、出発地から徒歩で一番早く到達できる1つの出入口を探索し、その出入口を経路探索の起点としていた。目的地についても同様の手順を行ない、経路探索を行なっていた。しかし、従来の経路探索ツールでは、出入口から改札を経由してホームに至る徒歩経路が考慮されていないため、出口改札が対向ホーム側に存在する場合があるなど、本来の最適経路候補が探索されるとは限らなかった。
【0034】
これに対して、本実施形態の経路探索ツール110は、図3のように、出入口、その駅出入口に繋がる駅内の改札、改札から到達可能なホームをノードに含めて経路探索を行なうため、出入口から改札を経由してホームに至るまでの経路及び移動コストの一例となる所要時間を考慮した最適経路候補の探索が可能となる。
【0035】
駅情報DB131には、改札・出入口テーブル、出入口〜改札間の移動時間テーブル及び改札〜ホーム間の移動時間テーブルが格納されている。図4乃至図6に各テーブルの概要を示す。
【0036】
図4は、改札・出入口テーブルの構造例を示した図である。
改札・出入口テーブル115には、出入口の位置、改札の位置、出入口・改札の利用制限情報等が記録されるようになっている。
具体的には、駅名称115aに、指標データとして各駅の名称が文字列で記録されている。駅コード115bには、各駅を識別するためのコード(数値)が記録されている。名称タイプ115c及び名称115dには、ホーム、改札、出入口のほか、他の交通機関であるバス乗降場がどこかを表す数値及び文字列が記録されている。名称真偽115eには、真正な名称であるか管理用の名称であるかの別を表す数値(0か1)が記録されている。コード115fには、当該データを別のデータに結びつけるためのコード(数値)が記録されており、案内コード115gには、出入口データが入力されたときのみ有効となるコード(数値)が記録されている。位置115hのフィールドには、ホーム、改札、出入口又はバス乗降場の緯度、経度、高度を表す数値が位置情報の一例として記録される。利用制限条件有無115iには、ホーム、改札、出入口又はバス乗降場の利用制限条件の有無を表す数値(0か1)が割り当てられており、利用制限条件115jには、乗車若しくは降車時のみしか利用できない、平日しか利用できない等の利用制限条件及び利用可能時間の割当等が記録されている。
【0037】
図5は、出入口〜改札間の移動時間テーブルの構造例を示した図である。
出入口〜改札間の移動時間テーブル116には、出入口から改札に至るまでの所要時間が記録されている。具体的には、駅名称116aに、指標データとして各駅の名称が文字列で記録されており、駅コード116bには、各駅を識別するためのコード(数値)が記録されている。出入口コード116cには、出入口を識別するためのコード(数値)が記録されており、改札コード116dには、改札を識別するためのコード(数値)が記録されている。移動時間116eには、出入口から改札までの移動時間が数値(秒)で記録されている。
【0038】
図6は、改札〜ホーム間の移動時間の移動時間テーブルの構造例を示した図である。
改札〜ホーム間の移動時間データ117には、改札からホームに至るまでの所要時間が記録されるようになっている。
具体的には、駅名称117aに、指標データとして各駅の名称が文字列で記録されており、駅コード117bには、各駅を識別するためのコード(数値)が記録されている。改札コードタイプ117cには、例えば、ゲートコード(10H)が固定値として記録されている。改札名称117dには、指標データとして改札の名称が文字列で記録されている。改札コード117eには、改札を識別するためのコード(数値)が記録されている。改札コード方向属性117fには、上り・下り両方向で利用可能であることを示す数値(例えば、0)が固定値として記録されている。ホーム側コードタイプ117gには、ホームのタイプを示すための数値(例えば、すべて(0H)、路線コード(1H)、交通手段コード(4H)、会社コード(8H)、ゲートコード(10H)等)が記録されている。ホーム側名称117hには、指標データとして、各ホームの名称が記録されている。ホーム側コード117iには、ホームを識別するためのコード(数値)が記録されている。ホーム側コード方向属性には117j、ホームが、上り方向を対象とするか、下り方向を対象とするか、両方向を対象とするかの別を識別するための数値(0、1、又は2)が記録されている。乗り換え時間117kには、乗換時間(改札からホームまでの所要時間)が数値(秒)で記録されている。
【0039】
[情報端末サービスサーバ]
情報端末サービスサーバ20は、主として、携帯端末50等からの電子メールでの経路探索の依頼に対応するためのもので、情報端末用インターフェース200、サービス制御部210、探索条件入力部220を含んで構成される。経路探索サーバ10が携帯端末50等から、メールを介さずに直接、経路探索条件の入力を受け付ける場合には、この情報端末サービスサーバはなくてもよい。
【0040】
情報端末用インターフェース200は、ディジタルネットワークNに接続されているメールサーバ60を介して携帯端末50又はPC70との電子メールによる双方向通信を可能にするものである。電子メールのみを受け付けるようにした点で、データ通信用インターフェース100とは区別される。
【0041】
サービス制御部210は、情報端末サービスサーバ全体における各種動作を制御する。例えば、携帯端末50から電子メールを受信したことを情報端末用インターフェース200が検知したときに、探索条件入力部220を制御して電子メール中の依頼文から経路探索条件を含む部分を抽出させ、抽出された経路探索条件を利用者による操作を要することなく経路探索ツール110に入力させる。つまり、自動入力・自動実行依頼である。経路探索ツール110で最適経路候補が特定されたときは、これを経路探索ツール110より受け取り、受け取った最適経路候補を編集部211で携帯端末50のディスプレイで表示可能なサイズの電子情報に編集する。そして、携帯端末用インターフェース220を制御することにより、編集した電子情報をメールサーバ60を介して電子メールの送信元である携帯端末50に返信し、表示させる。
【0042】
探索条件入力部220は、携帯端末50等から電子メールで送信された自然言語による探索条件を受け付けるためのものであり、ルールテーブル221、自然言語処理ツール222及び変換ツール223を有している。
【0043】
ルールテーブル221には、語又は語句と、経路探索ツール110が認識可能な経路探索条件との対応ルールが記録されている。また、自然言語処理ツール222は、情報端末用インターフェース200を通じて受信した、自然言語から成る依頼文から語又は語句を抽出する。さらに、変換ツール223は、自然言語処理ツール222で抽出した語又は語句をルールテーブル221に従って経路探索条件に変換する。
【0044】
[運用形態]
次に、本実施形態の経路探索システムの運用形態例を、経路探索ツール110での処理を中心に説明する。利用者が、携帯端末50によって、出発地から目的地までの経路候補のうち、総コスト、特に総所要時間が短い経路を最適経路候補として探索する場合の例を説明する。図7は 経路探索ツール110の処理手順図である。
【0045】
利用者は、携帯端末50の表示画面から直接、または、電子メールで、経路探索条件を入力することにより、経路探索を依頼する。その際、条件入力を簡易にするため、経路探索条件のうち、出発地については、携帯端末50のGPS受信機能を利用して取得した現在位置を自動的に設定するものとしてもよい。なお、携帯端末50が地図表示機能を有する場合には、地図上から出発地と目的地を選択するものとしてもよい。
【0046】
経路検索ツール110が、利用者によって入力された、出発地及び目的地を含む経路探索条件を受け付ける(ステップS101)。経路探索が、自然言語で記載された電子メールで依頼された場合には、一旦、情報端末サービスサーバ20の探索条件入力部220で、自然言語で記述された経路探索条件を経路探索ツール110が認識可能な経路探索条件に変換し、この変換された経路探索条件を受け付けることとなる。経路探索条件には、出発地及び目的地のほか、現在時刻、経由駅等の含まれるが、ここでは、便宜上、出発地及び目的地だけを受け付けたものとして説明する。
【0047】
経路探索ツール110は、条件生成部112で、出発地付近に存在する出入口の中から探し出された複数個の出入口候補に関する情報を、出発地をキーとして駅情報DB131より取得する(ステップS102)。例えば、出発地から、徒歩10分、半径300m以内等を基準に利用可能な出入口候補を特定する。次に、目的地付近に存在する出入口の中から探し出された複数個の出入口候補に関する情報を、目的地をキーとして駅情報DB131より取得する(ステップS103)。例えば、目的地から、徒歩10分、半径300m以内等を基準に利用可能な出入口候補を特定する。そして、取得した情報に基づいて、受け付けた出発地に代わる出発地条件、受け付けた目的地に代えて目的地条件を生成する。
【0048】
出発地条件及び目的地条件は、それぞれ出入口候補、当該出入口候補が存在する駅の改札、当該改札から到達可能なホームのようなノードの組み合わせ数だけ作成される。例えば、出発地付近の駅が三田駅(東京都)で、その駅の出入口が10個、改札が4つ、ホームが1つの場合、40通りの組み合わせのすべてを出発地条件とする。目的地条件についても同様である。
【0049】
経路探索ツール110は、出入口、改札及びホームをノードとして含む出発地条件及び目的地条件を用いて、出発地から目的地までの経路を探索する(ステップS104)。経路の探索は、駅情報DB131の駅情報及び運行情報DB132の運行情報を参照してノードとリンクの組み合わせを辿ることにより行う。
【0050】
このようにして探索された経路のそれぞれについて、駅情報DB131の改札・出入口テーブル115に記録される利用制限条件有無115iや利用制限条件115jを参照し、経路に含まれる出入口及び改札が全て利用可能であるか否かを判定する(ステップS105)。判定の結果、経路に利用不可能な出入口又は改札を含む場合には(ステップS105:No)、当該経路を探索結果から除外した上で、ステップS107の処理に移る(ステップS106)。一方、経路に含まれる出入口又は改札が全て利用可能である場合は、直ちにステップS107の処理に移る(ステップS105:Yes)。
【0051】
ステップS107では、経路毎にリンクの総所要時間を算出し、総所要時間の少ない順に経路のソートを行った後、1つ又は所定数の経路を、最適経路候補として、利用者宛に出力する。
リンクの総所要時間の計算は、例えば、運行情報DB132の地図情報と駅情報DB131の駅出入口の位置情報から、出発地及び目的地と出入口の間の徒歩による所要時間を算出し、駅情報DB114の出入口〜改札間の移動時間データ116と改札〜出入口間の移動時間データ117から出入口とホームの間の徒歩による所要時間を算出し、運行情報DB113の時刻表から、駅と駅の間の交通機関による所要時間を算出し、それらを合算することにより行なう。
【0052】
このように、本実施形態の経路探索システムでは、利用者によって入力された出発地、目的地に代えて、それぞれ駅の出入口、改札及びホームの組み合わせ数の分だけ出発地条件、目的地条件を生成することにより、駅の出入口、改札及びホームを、交通機関の路線網を構成するノードとして含めた経路探索を行うことができる。
これにより、駅構内の徒歩経路を含む経路探索が可能となるので、出発地の最寄り駅を出発駅、あるいは、目的地の最寄り駅を目的駅としない最適経路が探索されたり、同じ路線で上りのホーム側と下りのホーム側のそれぞれに出入口(改札)がある場合に誤って利用者を誘導してしまうことがなくなり、利用者にとって非常に便利な経路探索サービスを提供することができる。
【0053】
また、出入口や改札の利用制限条件を予め記録しておき、時間によっては利用不可能な出入口及び改札を経由する経路を探索結果から除外するようにしたので、曜日によっては利用できない出入口及び改札があったり、同じ路線でも上りホームと下りホームの間で行き来ができなかったりしても、それを考慮した所要時間を利用者に正しく伝達することができる。
【0054】
本実施形態は以上の通りであるが、本発明は、上記の実施形態例に限らず、以下のような種々の変形実施が可能である。
(1)本実施形態では、改札とホームの双方をノードに含めた場合の例を説明したが、これらはいずれか一方のみであっても良い。
(2)本実施形態では、利用者が入力する経路探索条件に必ず含むものとして出発地及び目的地の場合を例に挙げたが、出発予定時刻、到着予定時刻、利用時間帯等の時刻情報も必須入力としても良い。出入口の利用可能時間帯を考慮した探索結果をより正確にする上では、好ましい態様となり得る。
(3)本実施形態は、駅情報DB131と運行情報DB132とが独立して存在するものとして説明したが、これらを統合した1つのDBに置き換えても良い。また、駅情報DB131は、出発地条件及び目的地条件の生成用として1つ独立に存在させ、そのほかに運行情報DB132と共にもう1つ経路探索用として存在させるようにしても良い。
(4)本実施形態では、利用者による経路探索条件の入力を情報端末サービスサーバ20を通じて受け付け、経路探索サーバ10は、この経路探索条件に基づいて出発地条件、目的地条件を生成するとともに利用制限情報等を経路探索条件に付加し、最適経路候補を探索して利用者宛に出力するものとして説明したが、出発地及び目的地を含む経路探索条件の受付及びこれに基づく出発地条件及び目的地条件の生成までを他のサービスサーバで行い、経路探索ツール110は、出発地条件及び目的地条件に基づく経路探索を行い、探索結果を当該サービスサーバに出力するようにしても良い。
(5)本実施形態では、出発地条件と目的地条件の双方を経路探索に用いた場合の例を説明したが、利用者が入力した出発地と生成された目的地条件、あるいは、生成された出発地条件と利用者が入力した目的地の組み合わせを経路探索条件としても良い。
【0055】
<第2実施形態>
経路探索は、複数のノードを結ぶ枝葉(移動経路)の集まりであるネットワークが複雑になればなるほど探索ループ回数が増加し、パフォーマンスが低下する傾向にある。逆に、ネットワークの無駄な枝葉を落とすこと、つまり枝葉を最適化することにより、パフォーマンスを著しく向上させることができる。このことから、第2実施形態では、経路探索エンジン113に最適化処理を行う機能を持たせ、これにより、経路探索時のパフォーマンスを向上させる例を説明する。
【0056】
経路探索条件等については、第1実施形態と同じである。ここでは、一例として、ランドマーク機能を用いて利用者が登録した場所、施設等(便宜上、「ランドマーク」と称する)からの最寄駅の出入口、改札、ホームを含めた枝葉を最適化する場合の例を挙げる。「ランドマーク機能」とは、ランドマークを出発地又は目的地とし、そこからの最寄駅及びそこまでの移動経路、移動コスト(所要時間)等を、当該施設等の識別情報と関連付けて駅情報DB131において保持する機能である。ランドマークは、経路探索エンジン113による経路探索時に、ノードの一つとして扱われる。
また、ホームは、x(自然数)番線などのピンポイントの場所を示す場合のほか、駅によっては複数番線を束にしたゾーン的な場所を示す場合がある。利用制限条件は、例えば曜日及び時間帯による入場可否/出場可否であり、出発地側か目的地側かが確定することにより、それを利用できるかどうかの判別が可能となる。
【0057】
図8は、駅情報DB131に、ランドマークの最寄駅として関連付けられている駅の構内の説明図である。図8において、線の長さが相対的な距離(時間コスト)を表しているものとする。図示の例では、中央改札、北改札、東改札のように3つの改札が存在する。ホームには、路線の種類、列車進行方向(東京方面/高尾方面)等の属性情報が関連付けられている。例えば、第1ホームは「AAA線」用、第2ホームは「BBB線」用、第3ホームは「CCC線」用、第4ホームは「DDD線」用である。第1〜第3ホームは中央改札及び北改札と繋がっており、第4ホームは中央改札及び北改札のほか、東改札とも繋がっている。中央改札に近い出入口は第1〜第4出入口であり、北改札に近い出入口は第5及び第6出入口であり、東改札に近い出入口は第7出入口である。利用制限条件のある出入口は、第2出入口と第7出入口であり、改札は、東改札のみに利用制限条件がある。つまり、東改札に繋がる第7出入口は、共に利用制限条件がある。
【0058】
経路探索エンジン131は、最適化処理を、以下の手順で実行する。
=手順1=
まず、ランドマークと繋がる最寄駅毎に、当該駅の出入口及び改札の組を、各々の利用制限条件の有無に応じて、4つのパターンに分類する。
・第1パターン:出入口(無)〜改札(無)
・第2パターン:出入口(有)〜改札(有)
・第3パターン:出入口(無)〜改札(有)
・第4パターン:出入口(有)〜改札(無)
【0059】
このように分類する理由は、以下の通りである。
一般に、出入口に利用制限条件がある場合は改札に利用制限条件のない駅が多いが、例えば構内が広く、且つ、多くの改札が設けられている駅のように、改札毎に利用制限条件がある駅もある。また、百貨店や施設の出入口が駅の改札に直結しているために、出入口には利用制限条件はないが改札に利用制限条件がある駅もある。多数の出入口又は改札が設けられている駅では、両者の組み合わせを虱潰しのように探索していったのでは、それだけでパフォーマンスが著しく低下する(東京の新宿駅の組み合わせは200以上)。一方、出入口及び改札の利用制限条件の有無だけに着目した場合、組み合わせパターンは4つのみとなり、処理対象が単純化される。そのため、この実施形態では、上記の4パターンに分類している。
【0060】
=手順2=
パターン分類を終えると、いずれかのパターン、例えば第1パターンの出入口と改札との組をすべて抽出する。第1パターンは、いずれも利用制限条件のない組み合わせなので、図8の例では、以下の組が抽出される。
・第1出入口−中央改札
・第3出入口−中央改札
・第4出入口−中央改札
・第5出入口−北改札
・第6出入口−北改札
【0061】
=第3手順=
上記のようにして抽出した組のうち、ランドマークから異なる出入口を経由して同じ改札を利用する経路の移動コスト、例えば所要時間を比較する。そして、所要時間が余計にかかる出入口を除外し、残った1つの出入口を当該改札との組として保存する。この処理は、ランドマークから異なる出入口を経由しても改札が同じであれば、その改札からホームと繋がる全ての経路が同じとなるのが一般的である点に着眼した処理である。
第1パターンでは、中央改札と繋がる3つの出入口(第1、第3、第4出入口)のうち、第3及び第4出入口との組が除外される。また、北改札と繋がる2つの出入口(第5,6出入口)のうち、第6出入口の組が除外される。その結果、第1パターンでは、以下の組だけが保存される。
・第1出入口−中央改札
・第5出入口−北改札
【0062】
=第4手順=
次に、保存されている出入口と改札の組のうち、ランドマークから異なる出入口を経由して異なる改札を利用する場合において、ランドマーク−出入口−改札−ホームまでのすべての経路の移動コストを比較する。そして、比較対象となるものが無いか比較することが現実的でない経路、コストが同じになる経路、あるいは、移動コストの小さい経路以外の経路をすべて除外する。例えば、以下のように比較され、移動コストの大きい4つの組み併せが除外される。
・第1出入口−中央改札−第1ホーム < 第5出入口−北改札−第1ホーム
・第1出入口−中央改札−第2ホーム < 第5出入口−北改札−第2ホーム
・第1出入口−中央改札−第3ホーム < 第5出入口−北改札−第3ホーム
・第1出入口−中央改札−第4ホーム > 第5出入口−北改札−第4ホーム
【0063】
なお、「比較対象することが現実的でない経路」とは、例えばそれを除外してしまうと、予め設定した閾値、例えば目的のホームに10分以上の時間が余計にかかってしまう経路のようなものである。残った出入口と改札との組を保存する。
【0064】
=第5手順=
第1パターンについての処理を終えると、第2パターンについて、手順2〜手順4の処理を行う。これにより、第2パターンについては、共に利用制限条件のある以下の組だけが保存される。
・東改札−第7出入口
【0065】
また、第2パターンについての処理を終えると、第3パターンについて、手順2〜手順4の処理を行う。第3パターンは、利用制限条件の無い出入口と利用制限のある改札との組み合わせであるが、図8の例では、このような組み合わせは存在しないので、このパターンの処理の結果、保存される組は存在しない。
【0066】
また、第3パターンについての処理を終えると、第4パターンについて、手順2〜手順4の処理を行う。第4パターンは、利用制限条件がある出入口と利用制限条件のない改札との組み合わせであるが、図8の例では、この組み合わせに該当するのは、以下の組しか存在しないので、この組だけが保存される。
・第2出入口−中央改札
【0067】
以上の処理により、以下の組が保存される。
・第1出入口(無)−中央改札(無)
・第5出入口(無)−北改札(無)
・第2出入口(有)−中央改札(無)
・第7出入口(有)−東改札(有)
【0068】
保存された情報を最適化された駅の情報としてランドマークの最寄駅に関連付けられた当該情報として更新し、経路探索の際のノードの一つとして用いる。
【0069】
このように、第2実施形態では、ランドマークとして関連付けられた出発地又は目的地の最寄駅の出入口又は改札が複数存在する場合において、出入口−改札−ホームの移動経路の組み合わせを、動的に変化する出入口又は改札の利用制限条件を考慮して最適化処理を行うようにしたので、探索ループ回数が最適化処理前よりも軽減され、パフォーマンスの低下を抑制することができる。
【0070】
パフォーマンスの低下が抑制されることを経路探索サーバ10の性能向上とみなし、この性能向上の程度(性能向上率)をアムダールの法則(Amdahl's law)で定量化すると、以下のようになる。
最適化処理によって影響を受ける部分の割合、すなわち経路探索における駅情報DB131や運行情報DB132へのデータアクセスを除くタスクの割合をP、最適化処理による改善率(=総出入口数÷有効出入口数×100)をSとすると、
性能向上率は、「1÷(1−P)+P÷S」の式で表すことができる。
P=60%
S=175% (=7÷4×100)
とすると、性能向上率は、1.59倍となる。
【0071】
出入口−改札−ホームの移動パターンが非常に多い駅(新宿駅、東京駅など)を利用する経路探索と、逆に移動パターンが非常に少ない駅(目白駅など)を利用する経路探索とでは最適化を行った時と行わない時とでは性能向上率に大きな開きが生じ、これが処理速度の差として顕著に顕れる。
【0072】
なお、第2実施形態では、ランドマーク機能を用いた場合の例を説明したが、出発地と目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた出入口、改札及びホームのいずれかが複数存在する場合に最適化処理の需要が発生するので、ランドマーク機能は、必須ではない。
また、第2実施形態では、複数の出入口のいくつかに利用制限条件が設定されている場合の最適化処理例について説明したが、利用制限条件のまったく無い複数の出入口や改札のある駅についても、同様に適用が可能である。要は、出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、探索ノードより除外すればよい。
また、第2実施形態では、最適化処理に際し、駅の出入口及び改札の組を、各々の利用制限条件の有無に応じて4つのパターンに分類した場合の例を示したが、単純にユニークな移動経路を残すように集約することもできる。
また、相対的に移動コストの大きい組み合わせが除外された出発地又は目的地を、例えば駅情報DB131にランドマークとして保持する機能を形成し、経路探索エンジン113が、保持されているランドマークを出発地又は目的地とした経路探索を行うようにすることで、その都度最適化処理を行う必要がなくなり、これによっても、パフォーマンスを向上させることができる。
また、第2実施形態では、移動コストとして、移動に要する所要時間を例に挙げて説明したが、エスカレータの有無や歩道の広さなど、移動の容易性を定量化したものを移動コストとして用いてもよい。
【符号の説明】
【0073】
10 経路探索サーバ
20 情報端末サービスサーバ
50 携帯端末
60 メールサーバ
70 PC
100 データ通信用インターフェース
110 経路探索ツール
111 探索条件受付部
112 条件生成部
113 経路探索エンジン
131 駅情報DB
132 運行情報DB
200 情報端末用インターフェース
210 サービス制御部
220 探索条件入力部
221 ルールテーブル
222 自動言語処理ツール
223 変換ツール

【特許請求の範囲】
【請求項1】
利用者により指定された出発地及び目的地を特定する特定手段と、
交通機関の駅の情報を蓄積した駅情報DBから、前記特定された出発地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成する条件生成手段と、
経路探索用の運行情報DBにアクセスして前記生成された出発地条件及び前記特定された目的地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段と、
を有する経路探索システム。
【請求項2】
利用者により指定された出発地及び目的地を特定する特定手段と、
交通機関の駅の情報を蓄積した駅情報DBから、前記特定された目的地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件生成手段と、
経路探索用の運行情報DBにアクセスして前記目的地条件及び前記特定された出発地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段と、
を有する経路探索システム。
【請求項3】
前記条件生成手段は、前記駅出入口の位置情報、前記駅出入口から前記改札までの移動に要する第1移動コスト、前記改札からホームまでの移動に要する第2移動コストを取得し、取得したこれらの移動コストを新たな条件として付加するように構成されており、
前記経路探索手段は、探索された経路毎に、前記位置情報に基づき算出される前記利用可能な駅出入口までの移動に要する第3コストと、前記第1移動コスト及び前記第2移動コストとを合算することにより、経路全体の総移動コストを算出し、この総移動コストが小さい順に前記最適経路候補をソートする、
請求項1又は2記載の経路探索システム。
【請求項4】
前記条件生成手段は、前記駅出入口、前記改札又は前記ホームの利用制限情報を取得し、取得した利用制限情報を新たな条件として付加するように構成されており、
前記経路探索手段は、前記利用制限情報に基づき、前記探索された経路のうち利用が制限されている駅出入口、改札又はホームが含まれる最適経路候補を探索結果から除外する、
請求項3記載の経路探索システム。
【請求項5】
前記経路探索手段は、前記出発地と前記目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた駅出入口、改札及びホームのいずれかが複数存在する場合に、駅出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該駅出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、前記ノードより除外する最適化処理を行う、
請求項1ないし4のいずれかの項記載の経路探索システム。
【請求項6】
前記相対的に移動コストの大きい組み合わせが除外された前記出発地又は前記目的地をランドマークとして保持するランドマーク保持手段をさらに備えており、
前記経路探索手段は、保持されているランドマークを前記出発地又は前記目的地とした経路探索を行う、
請求項5記載の経路探索システム。
【請求項7】
交通機関の駅の情報を蓄積した駅情報DB及び経路探索用の運行情報DBにアクセス可能なコンピュータが、
前記駅情報DBから、利用者に指定された出発地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者に指定された目的地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する処理と、
前記運行情報DBにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する処理と、を実行することを特徴とする、
コンピュータによる経路探索方法。
【請求項8】
交通機関の駅の情報を蓄積した駅情報DB及び経路探索用の運行情報DBにアクセス可能なコンピュータを、
前記駅情報DBから、利用者により指定された出発地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者により指定された目的地において利用可能な1又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件出力手段;
前記運行情報DBにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段;として機能させる、
経路探索用のコンピュータプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate


【公開番号】特開2010−277575(P2010−277575A)
【公開日】平成22年12月9日(2010.12.9)
【国際特許分類】
【出願番号】特願2010−36409(P2010−36409)
【出願日】平成22年2月22日(2010.2.22)
【出願人】(596130185)株式会社 ヴァル研究所 (14)
【Fターム(参考)】