経路探索システム、経路探索方法及びコンピュータプログラム
【課題】駅構内を考慮した経路探索を可能にする。
【解決手段】経路探索ツール１１０は、出発地及び目的地の入力を受け付けると、駅情報ＤＢ１３１から、出発地において利用可能な１又は複数の駅出入口の情報と各駅出入口に繋がる改札及び当該改札から到達可能なホームの情報とを取得し、取得した情報に基づいて出発地に代わる出発地条件を生成する。同様に、目的地に代わる目的地条件を生成する。経路探索エンジン１１３は、運行情報ＤＢ１３２にアクセスして、出発地条件及び目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、出発地から目的地に至る最適経路候補を探索する。
【解決手段】経路探索ツール１１０は、出発地及び目的地の入力を受け付けると、駅情報ＤＢ１３１から、出発地において利用可能な１又は複数の駅出入口の情報と各駅出入口に繋がる改札及び当該改札から到達可能なホームの情報とを取得し、取得した情報に基づいて出発地に代わる出発地条件を生成する。同様に、目的地に代わる目的地条件を生成する。経路探索エンジン１１３は、運行情報ＤＢ１３２にアクセスして、出発地条件及び目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、出発地から目的地に至る最適経路候補を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、徒歩及び電車等の公共交通網を利用して、任意の出発地から目的地に至る経路を探索する経路探索の技術に関する。
【背景技術】
【０００２】
電車等の公共交通網における最適な運行経路の探索技術については、本出願人によって開発された運行経路探索ソフト「駅すぱあと」（登録商標、非特許文献１参照）以来、複数の企業技術者の手により幾多の改良・改善が試みられてきた。この経路探索技術の一つとして、出発地から出発駅及び目的地から目的駅までを結ぶ徒歩経路も考慮して、出発地及び目的地から最も近い駅（最寄り駅）を出発駅及び目的駅として特定した後、さらに、当該出発駅及び目的駅が複数の出入口を有する場合には、出発地及び目的地から最も近い出入口（最寄り出入口）を特定する経路探索方法が存在している。
【０００３】
しかしながら、一旦、最寄り駅を特定した後に、当該最寄り駅の最寄り出入口を特定し、経路を探索する上記の方法では、最適経路が探索されない場合がある。
例えば、六本木ヒルズから新高円寺駅までを上記の方法で探索する場合、六本木ヒルズの最寄り駅は「日比谷線の六本木駅」で最寄り出入口は「出入口１ｃ」であるため、最適経路は〈六本木ヒルズ→（徒歩０分）→六本木駅［出入口１ｃ］→（日比谷線）→霞ヶ関→（丸の内線）→新高円寺〉となり、平均所要時間は３９分となる。
【０００４】
しかし、最寄り駅以外も出発駅の候補とすると、「大江戸線の六本木駅（出入口５）」も候補となり、経路は〈六本木ヒルズ→（徒歩４分）→六本木駅［出入口５］→（大江戸線）→中野坂上→（丸の内線）→新高円寺〉で、平均所要時間は３４分となるため、この経路が、総所要時間の短い最適経路となる。
なお、「日比谷線の六本木駅」と「大江戸線の六本木駅」とは行き来することができないため、一旦、最寄り駅である「日比谷線の六本木駅」が出発駅と特定されてしまうと、「大江戸線の六本木駅」から出発する経路は探索されないこととなる。
【０００５】
このように、出発地の最寄り駅を出発駅としない最適経路が存在する場合があり、上記のように、一旦、最寄り駅を特定した後に経路探索を行なう方法では、そのような最適経路が探索されないこととなる。
【０００６】
他方、１又は複数の駅を出発駅候補又は目的駅候補としておき、当該出発駅候補又は目的駅候補が複数の出入口を有する場合に、出発地及び目的地から徒歩で一番早く到達できる出入口を特定して、当該出入口の位置を出発駅候補又は目的駅候補の位置とみなしたうえで、最適経路を探索する最適経路探索装置も提案されている（特許文献１参照）。
【０００７】
この特許文献１に記載された最適経路探索装置では、はじめの段階で、最寄り駅以外の駅を出発駅候補から除外することがないため、最寄り駅を出発駅としない最適経路も探索することができる。また、出入口を複数有する出発駅候補又は目的駅候補については、最寄り出入口を特定するため、出発地から出発駅までを結ぶ徒歩経路と目的駅から目的地までを結ぶ徒歩経路も考慮した最適経路の探索を行なうことができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００３−１８２５７８号公報
【非特許文献】
【０００９】
【非特許文献１】「駅すぱあと」風雲録 柏崎ほか 日経ＢＰ社 ２００６年３月２０日発行
【発明の概要】
【発明が解決しようとする課題】
【００１０】
特許文献１に記載された装置による経路探索方法は、出発地から出発駅までを結ぶ徒歩経路と目的駅から目的地までを結ぶ徒歩経路とを考慮した経路探索を行なうことができる点で便利である。
【００１１】
しかし、駅の構内は、駅ごとに異なった構造となっており、曜日によっては利用できない出入口及び改札があったり、同じ路線でも上りホームと下りホームの間で行き来ができなかったり等、種々の要因により、出入口から所望の電車が発着するホームに至る経路は区々となり、その所要時間も大きく異なってしまう。
【００１２】
例えば、同じ路線で上りのホーム側と下りのホーム側のそれぞれに出入口（改札）があり、かつ、上りホームと下りホームの間で行き来できない駅が出発駅であり、出発地からの最寄り出入口が上りホーム側の出入口で、乗車すべき電車が下り電車である場合には、最寄り出入口（上りのホーム側の出入口）から入場する経路が最適経路であるとは限らない。そうであるにも関わらず、特許文献１に記載された装置では、経路探索の際に、出発地から駅の出入口までの徒歩経路は考慮するものの、駅構内、すなわち、出入口から改札及びホームまでの徒歩経路は考慮されていなかった。
【００１３】
本発明は、かかる背景のもと、駅構内、すなわち、駅出入口から改札、あるいはホームまでの経路を考慮した最適経路探索の技術を提供することを主たる課題とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明は、経路探索システム、経路探索方法及びコンピュータプログラムを提供する。
本発明の経路探索システムは、利用者により指定された出発地及び目的地を特定する特定手段と、交通機関の駅の情報を蓄積した駅情報ＤＢ（ＤＢはデータベースの略、以下同じ）から、前記特定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成する条件生成手段と、経路探索用の運行情報ＤＢにアクセスして前記生成された出発地条件及び前記特定された目的地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段とを有するものである。
【００１５】
本発明の他の経路探索システムは、利用者により指定された出発地及び目的地を特定する特定手段と、交通機関の駅の情報を蓄積した駅情報ＤＢから、前記特定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件生成手段と、経路探索用の運行情報ＤＢにアクセスして前記目的地条件及び前記特定された出発地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段とを有するものである。
駅出入口、改札、ホームもノードとして経路探索を行なうことから、駅構内の移動経路を考慮した経路探索を行なうことができる。
【００１６】
ある実施の態様では、前記条件生成手段は、前記駅出入口の位置情報、前記駅出入口から前記改札までの移動に要する第１移動コスト、前記改札からホームまでの移動に要する第２移動コストを取得し、取得したこれらの移動コストを新たな条件として付加するように構成されており、前記経路探索手段は、探索された経路毎に、前記位置情報に基づき算出される前記利用可能な駅出入口までの移動に要する第３コストと、前記第１移動コスト及び前記第２移動コストとを合算することにより、経路全体の総移動コストを算出し、この総移動コストが小さい順に前記最適経路候補をソートする。この場合は、探索結果から、特に、総移動コストが小さい経路を選出することが可能となる。
移動コストは、例えば移動時間情報のようなものである。
【００１７】
他の実施の態様では、さらに、前記条件生成手段は、前記駅出入口、前記改札又は前記ホームの利用制限情報を取得し、取得した利用制限情報をも出力するように構成されており、前記経路探索手段は、前記利用制限情報に基づき、前記探索された経路のうち利用が制限されている駅出入口、改札又はホームが含まれる最適経路候補を探索結果から除外するように動作する。
【００１８】
他の実施の態様では、前記経路探索手段は、前記出発地と前記目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた駅出入口、改札及びホームのいずれかが複数存在する場合に、駅出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該駅出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、前記ノードより除外する最適化処理を行う。構成をより簡略化する観点からは、前記相対的に移動コストの大きい組み合わせが除外された前記出発地又は前記目的地をランドマークとして保持するランドマーク保持手段をさらに備えるようにし、前記経路探索手段は、保持されているランドマークを前記出発地又は前記目的地とした経路探索を行うようにする。
これにより、ランドマークを用いるだけで上記最適化処理が実行されるので、パフォーマンスがより向上する。
【００１９】
本発明の経路探索方法は、交通機関の駅の情報を蓄積した駅情報ＤＢ及び経路探索用の運行情報ＤＢにアクセス可能なコンピュータが、前記駅情報ＤＢから、利用者に指定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者に指定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する処理と、前記運行情報ＤＢにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する処理と、を実行することを特徴とする、コンピュータによる経路探索方法である。
【００２０】
本発明のコンピュータプログラムは、交通機関の駅の情報を蓄積した駅情報ＤＢ及び経路探索用の運行情報ＤＢにアクセス可能なコンピュータを、前記駅情報ＤＢから、利用者により指定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者により指定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件出力手段；前記運行情報ＤＢにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段；として機能させる、経路探索用のコンピュータプログラムである。
【発明の効果】
【００２１】
本発明によれば、交通機関の駅名、駅出入口のほか、改札とホームの少なくとも一方をノードに含めて経路探索を行なうので、駅構内の徒歩経路を含む正確な経路探索が可能となるという特有の効果が得られる。改札や駅出入口等の利用制限情報を探索の条件として付加することも可能であり、この場合は、利用不可能な出入口及び改札を経由する経路を探索結果から除外して、実際に利用可能な経路のみの探索結果を得ることができるので、より現実に即した経路探索が可能となる。
経路探索手段がノードの最適化処理を行う構成では、探索ループ回数が減少するので、経路探索時のパフォーマンスが向上する。
【図面の簡単な説明】
【００２２】
【図１】第１実施形態の経路探索システムの全体構成図である。
【図２】従来の経路探索処理の概要を示す図である。
【図３】本実施形態の経路探索ツールによる経路探索処理の概要を示す図である。
【図４】改札・出入口テーブルの構造説明図である。
【図５】出入口〜改札間の移動時間テーブルの構造説明図である。
【図６】改札〜ホーム間の移動時間テーブルの構造説明図である。
【図７】経路探索ツールの処理手順図である。
【図８】第２実施形態の経路探索システムにおいて、最適化処理を行う場合の駅構内の説明図である。
【発明を実施するための形態】
【００２３】
以下、本発明を、携帯端末向けの経路探索サービスを可能にするネットワーク型の経路探索システムに適用した場合の実施の形態例を説明する。
【００２４】
＜第１実施形態＞
図１は、この実施形態の経路探索システムの全体構成図であり、特徴的な部分を掲示してある。この経路探索システムは、インターネット等のディジタルネットワークＮに接続される経路探索サーバ１０と、１又は複数の情報端末サービスサーバ２０（図示の例では１つ）と、交通機関の駅の情報、例えば駅の出入口（北口、南口、Ａ出口、Ｂ出口等：「駅出入口」、以下、単に出入口という）の位置情報（緯度、経度等）、出入口に繋がる改札、改札から到達可能なホーム、利用制限条件等のデータを蓄積した駅情報ＤＢ１３１と、経路探索用の運行情報、例えば交通機関（鉄道／バス）の路線網、時刻表、駅周辺の地図情報等のデータを蓄積した運行情報ＤＢ１３２とを含んで構成される。
ディジタルネットワークＮには、携帯端末５０の他、メールサーバ６０や情報端末の一例となるＰＣ（パーソナルコンピュータ）７０も接続可能になっている。
【００２５】
携帯端末５０及びＰＣ７０は、データ通信及びデータ処理機能を有する場合はダイレクトに、また、メール機能を有する場合にはメールサーバ６０を通じて、それぞれディジタルネットワークＮに接続することができる。
【００２６】
［経路探索サーバ］
経路探索サーバ１０は、サーバ本体と本発明のコンピュータプログラムとの協働により実現される。すなわち、サーバ本体が、コンピュータプログラムを読み込んで実行することにより、そのサーバ本体を、データ通信用インターフェース１００及び経路探索ツール１１０として機能させ、経路探索のための情報処理を実行可能にする。
【００２７】
データ通信用インターフェース１００は、データ通信及びデータ処理機能を有する携帯端末５０やＰＣ７０との双方向通信を可能にするとともに、これらの情報端末が閲覧可能な階層ページ画面を提供する。この階層ページ画面では、経路探索のＷｅｂサービスを行なうためのもので、経路探索条件の精緻な指定をシステム側と利用者との間でインタラクティブに行なうことにより、利用者が満足する経路探索を行なう環境を提供する。経路探索の結果情報の表示も、このページ画面で行なうことができる。
【００２８】
経路探索ツール１１０は、探索条件受付部１１１、条件生成部１１２及び経路探索エンジン１１３とを含む。
【００２９】
探索条件受付部１１１は、出発地及び目的地を含む経路探索条件を受け付ける。出発地と目的地の少なくとも一方については、利用者が直接入力（指定）したものをそのまま経路探索条件として特定してもよく、予め登録されているものを提示して選択させることで特定するようにしてもよい。
条件生成部１１２は、出発地から出発地条件、目的地から目的地条件を生成し、必要に応じて出入口や改札の利用制限情報を付加する。
経路探索エンジン１１３は、出入口、改札、ホーム、経由駅を、交通機関の路線網を構成するノードに含め、出発地から目的地に向かって各ノードに順次リンクを張ることを繰り返すことにより、経路探索条件に従う１又は複数の経路候補を探索し、経路探索条件に最も適合するものを最適経路候補とする。
【００３０】
経路探索エンジン１１３は、公知の推論エンジンも搭載しており、経路探索途中で、つまりリンクを張り付けていく過程で、所要時間が現実的でなくなる経路となることが判明した場合、例えば予めメモリに記憶された閾値と比べて大きくなった場合は、その時点でその経路候補についての次のノード以降の探索を止める。
経路探索エンジン１１３は、また、複数の経路候補の各々について、出発地から目的地に至るまでの総移動コスト、例えば時間を移動コストと捉える観点からは総所要時間を算出し、算出された総所要時間の小さい順に、複数の経路をソートする。さらに、経路中にその利用が制限される出入口や改札がある場合には、当該経路を除外したうえで、経路候補を特定する。
【００３１】
なお、経路探索エンジン１１３の基本機能部分は、本出願人が提供している経路探索ソフトウェア「駅すぱあと」（登録商標）を使用することができる。
【００３２】
次に、経路探索ツール１１０による最も一般的な経路探索処理、すなわち出発地と目的地との間の最適経路候補の特定を行なう場合の探索の概要を説明する。なお、ここでは、出発地と出発駅、目的地と目的駅とがそれぞれ異なるものとして説明する。
【００３３】
図２は、従来の経路探索処理の概要を示す図であり、図３は、本実施形態の経路探索ツール１１０による経路探索処理の概要を示す図である。
従来の経路探索ツールは、図２のように、出発地近くの最寄りの１または複数の出発駅候補を特定した後、各出発駅候補の出入口の位置情報に基づき、出発地から徒歩で一番早く到達できる１つの出入口を探索し、その出入口を経路探索の起点としていた。目的地についても同様の手順を行ない、経路探索を行なっていた。しかし、従来の経路探索ツールでは、出入口から改札を経由してホームに至る徒歩経路が考慮されていないため、出口改札が対向ホーム側に存在する場合があるなど、本来の最適経路候補が探索されるとは限らなかった。
【００３４】
これに対して、本実施形態の経路探索ツール１１０は、図３のように、出入口、その駅出入口に繋がる駅内の改札、改札から到達可能なホームをノードに含めて経路探索を行なうため、出入口から改札を経由してホームに至るまでの経路及び移動コストの一例となる所要時間を考慮した最適経路候補の探索が可能となる。
【００３５】
駅情報ＤＢ１３１には、改札・出入口テーブル、出入口〜改札間の移動時間テーブル及び改札〜ホーム間の移動時間テーブルが格納されている。図４乃至図６に各テーブルの概要を示す。
【００３６】
図４は、改札・出入口テーブルの構造例を示した図である。
改札・出入口テーブル１１５には、出入口の位置、改札の位置、出入口・改札の利用制限情報等が記録されるようになっている。
具体的には、駅名称１１５ａに、指標データとして各駅の名称が文字列で記録されている。駅コード１１５ｂには、各駅を識別するためのコード（数値）が記録されている。名称タイプ１１５ｃ及び名称１１５ｄには、ホーム、改札、出入口のほか、他の交通機関であるバス乗降場がどこかを表す数値及び文字列が記録されている。名称真偽１１５ｅには、真正な名称であるか管理用の名称であるかの別を表す数値（０か１）が記録されている。コード１１５ｆには、当該データを別のデータに結びつけるためのコード（数値）が記録されており、案内コード１１５ｇには、出入口データが入力されたときのみ有効となるコード（数値）が記録されている。位置１１５ｈのフィールドには、ホーム、改札、出入口又はバス乗降場の緯度、経度、高度を表す数値が位置情報の一例として記録される。利用制限条件有無１１５ｉには、ホーム、改札、出入口又はバス乗降場の利用制限条件の有無を表す数値（０か１）が割り当てられており、利用制限条件１１５ｊには、乗車若しくは降車時のみしか利用できない、平日しか利用できない等の利用制限条件及び利用可能時間の割当等が記録されている。
【００３７】
図５は、出入口〜改札間の移動時間テーブルの構造例を示した図である。
出入口〜改札間の移動時間テーブル１１６には、出入口から改札に至るまでの所要時間が記録されている。具体的には、駅名称１１６ａに、指標データとして各駅の名称が文字列で記録されており、駅コード１１６ｂには、各駅を識別するためのコード（数値）が記録されている。出入口コード１１６ｃには、出入口を識別するためのコード（数値）が記録されており、改札コード１１６ｄには、改札を識別するためのコード（数値）が記録されている。移動時間１１６ｅには、出入口から改札までの移動時間が数値（秒）で記録されている。
【００３８】
図６は、改札〜ホーム間の移動時間の移動時間テーブルの構造例を示した図である。
改札〜ホーム間の移動時間データ１１７には、改札からホームに至るまでの所要時間が記録されるようになっている。
具体的には、駅名称１１７ａに、指標データとして各駅の名称が文字列で記録されており、駅コード１１７ｂには、各駅を識別するためのコード（数値）が記録されている。改札コードタイプ１１７ｃには、例えば、ゲートコード（１０Ｈ）が固定値として記録されている。改札名称１１７ｄには、指標データとして改札の名称が文字列で記録されている。改札コード１１７ｅには、改札を識別するためのコード（数値）が記録されている。改札コード方向属性１１７ｆには、上り・下り両方向で利用可能であることを示す数値（例えば、０）が固定値として記録されている。ホーム側コードタイプ１１７ｇには、ホームのタイプを示すための数値（例えば、すべて（０Ｈ）、路線コード（１Ｈ）、交通手段コード（４Ｈ）、会社コード（８Ｈ）、ゲートコード（１０Ｈ）等）が記録されている。ホーム側名称１１７ｈには、指標データとして、各ホームの名称が記録されている。ホーム側コード１１７ｉには、ホームを識別するためのコード（数値）が記録されている。ホーム側コード方向属性には１１７ｊ、ホームが、上り方向を対象とするか、下り方向を対象とするか、両方向を対象とするかの別を識別するための数値（０、１、又は２）が記録されている。乗り換え時間１１７ｋには、乗換時間（改札からホームまでの所要時間）が数値（秒）で記録されている。
【００３９】
［情報端末サービスサーバ］
情報端末サービスサーバ２０は、主として、携帯端末５０等からの電子メールでの経路探索の依頼に対応するためのもので、情報端末用インターフェース２００、サービス制御部２１０、探索条件入力部２２０を含んで構成される。経路探索サーバ１０が携帯端末５０等から、メールを介さずに直接、経路探索条件の入力を受け付ける場合には、この情報端末サービスサーバはなくてもよい。
【００４０】
情報端末用インターフェース２００は、ディジタルネットワークＮに接続されているメールサーバ６０を介して携帯端末５０又はＰＣ７０との電子メールによる双方向通信を可能にするものである。電子メールのみを受け付けるようにした点で、データ通信用インターフェース１００とは区別される。
【００４１】
サービス制御部２１０は、情報端末サービスサーバ全体における各種動作を制御する。例えば、携帯端末５０から電子メールを受信したことを情報端末用インターフェース２００が検知したときに、探索条件入力部２２０を制御して電子メール中の依頼文から経路探索条件を含む部分を抽出させ、抽出された経路探索条件を利用者による操作を要することなく経路探索ツール１１０に入力させる。つまり、自動入力・自動実行依頼である。経路探索ツール１１０で最適経路候補が特定されたときは、これを経路探索ツール１１０より受け取り、受け取った最適経路候補を編集部２１１で携帯端末５０のディスプレイで表示可能なサイズの電子情報に編集する。そして、携帯端末用インターフェース２２０を制御することにより、編集した電子情報をメールサーバ６０を介して電子メールの送信元である携帯端末５０に返信し、表示させる。
【００４２】
探索条件入力部２２０は、携帯端末５０等から電子メールで送信された自然言語による探索条件を受け付けるためのものであり、ルールテーブル２２１、自然言語処理ツール２２２及び変換ツール２２３を有している。
【００４３】
ルールテーブル２２１には、語又は語句と、経路探索ツール１１０が認識可能な経路探索条件との対応ルールが記録されている。また、自然言語処理ツール２２２は、情報端末用インターフェース２００を通じて受信した、自然言語から成る依頼文から語又は語句を抽出する。さらに、変換ツール２２３は、自然言語処理ツール２２２で抽出した語又は語句をルールテーブル２２１に従って経路探索条件に変換する。
【００４４】
［運用形態］
次に、本実施形態の経路探索システムの運用形態例を、経路探索ツール１１０での処理を中心に説明する。利用者が、携帯端末５０によって、出発地から目的地までの経路候補のうち、総コスト、特に総所要時間が短い経路を最適経路候補として探索する場合の例を説明する。図７は 経路探索ツール１１０の処理手順図である。
【００４５】
利用者は、携帯端末５０の表示画面から直接、または、電子メールで、経路探索条件を入力することにより、経路探索を依頼する。その際、条件入力を簡易にするため、経路探索条件のうち、出発地については、携帯端末５０のＧＰＳ受信機能を利用して取得した現在位置を自動的に設定するものとしてもよい。なお、携帯端末５０が地図表示機能を有する場合には、地図上から出発地と目的地を選択するものとしてもよい。
【００４６】
経路検索ツール１１０が、利用者によって入力された、出発地及び目的地を含む経路探索条件を受け付ける（ステップＳ１０１）。経路探索が、自然言語で記載された電子メールで依頼された場合には、一旦、情報端末サービスサーバ２０の探索条件入力部２２０で、自然言語で記述された経路探索条件を経路探索ツール１１０が認識可能な経路探索条件に変換し、この変換された経路探索条件を受け付けることとなる。経路探索条件には、出発地及び目的地のほか、現在時刻、経由駅等の含まれるが、ここでは、便宜上、出発地及び目的地だけを受け付けたものとして説明する。
【００４７】
経路探索ツール１１０は、条件生成部１１２で、出発地付近に存在する出入口の中から探し出された複数個の出入口候補に関する情報を、出発地をキーとして駅情報ＤＢ１３１より取得する（ステップＳ１０２）。例えば、出発地から、徒歩１０分、半径３００ｍ以内等を基準に利用可能な出入口候補を特定する。次に、目的地付近に存在する出入口の中から探し出された複数個の出入口候補に関する情報を、目的地をキーとして駅情報ＤＢ１３１より取得する（ステップＳ１０３）。例えば、目的地から、徒歩１０分、半径３００ｍ以内等を基準に利用可能な出入口候補を特定する。そして、取得した情報に基づいて、受け付けた出発地に代わる出発地条件、受け付けた目的地に代えて目的地条件を生成する。
【００４８】
出発地条件及び目的地条件は、それぞれ出入口候補、当該出入口候補が存在する駅の改札、当該改札から到達可能なホームのようなノードの組み合わせ数だけ作成される。例えば、出発地付近の駅が三田駅（東京都）で、その駅の出入口が１０個、改札が４つ、ホームが１つの場合、４０通りの組み合わせのすべてを出発地条件とする。目的地条件についても同様である。
【００４９】
経路探索ツール１１０は、出入口、改札及びホームをノードとして含む出発地条件及び目的地条件を用いて、出発地から目的地までの経路を探索する（ステップＳ１０４）。経路の探索は、駅情報ＤＢ１３１の駅情報及び運行情報ＤＢ１３２の運行情報を参照してノードとリンクの組み合わせを辿ることにより行う。
【００５０】
このようにして探索された経路のそれぞれについて、駅情報ＤＢ１３１の改札・出入口テーブル１１５に記録される利用制限条件有無１１５ｉや利用制限条件１１５ｊを参照し、経路に含まれる出入口及び改札が全て利用可能であるか否かを判定する（ステップＳ１０５）。判定の結果、経路に利用不可能な出入口又は改札を含む場合には（ステップＳ１０５：No）、当該経路を探索結果から除外した上で、ステップＳ１０７の処理に移る（ステップＳ１０６）。一方、経路に含まれる出入口又は改札が全て利用可能である場合は、直ちにステップＳ１０７の処理に移る（ステップＳ１０５：Yes）。
【００５１】
ステップＳ１０７では、経路毎にリンクの総所要時間を算出し、総所要時間の少ない順に経路のソートを行った後、１つ又は所定数の経路を、最適経路候補として、利用者宛に出力する。
リンクの総所要時間の計算は、例えば、運行情報ＤＢ１３２の地図情報と駅情報ＤＢ１３１の駅出入口の位置情報から、出発地及び目的地と出入口の間の徒歩による所要時間を算出し、駅情報ＤＢ１１４の出入口〜改札間の移動時間データ１１６と改札〜出入口間の移動時間データ１１７から出入口とホームの間の徒歩による所要時間を算出し、運行情報ＤＢ１１３の時刻表から、駅と駅の間の交通機関による所要時間を算出し、それらを合算することにより行なう。
【００５２】
このように、本実施形態の経路探索システムでは、利用者によって入力された出発地、目的地に代えて、それぞれ駅の出入口、改札及びホームの組み合わせ数の分だけ出発地条件、目的地条件を生成することにより、駅の出入口、改札及びホームを、交通機関の路線網を構成するノードとして含めた経路探索を行うことができる。
これにより、駅構内の徒歩経路を含む経路探索が可能となるので、出発地の最寄り駅を出発駅、あるいは、目的地の最寄り駅を目的駅としない最適経路が探索されたり、同じ路線で上りのホーム側と下りのホーム側のそれぞれに出入口（改札）がある場合に誤って利用者を誘導してしまうことがなくなり、利用者にとって非常に便利な経路探索サービスを提供することができる。
【００５３】
また、出入口や改札の利用制限条件を予め記録しておき、時間によっては利用不可能な出入口及び改札を経由する経路を探索結果から除外するようにしたので、曜日によっては利用できない出入口及び改札があったり、同じ路線でも上りホームと下りホームの間で行き来ができなかったりしても、それを考慮した所要時間を利用者に正しく伝達することができる。
【００５４】
本実施形態は以上の通りであるが、本発明は、上記の実施形態例に限らず、以下のような種々の変形実施が可能である。
（１）本実施形態では、改札とホームの双方をノードに含めた場合の例を説明したが、これらはいずれか一方のみであっても良い。
（２）本実施形態では、利用者が入力する経路探索条件に必ず含むものとして出発地及び目的地の場合を例に挙げたが、出発予定時刻、到着予定時刻、利用時間帯等の時刻情報も必須入力としても良い。出入口の利用可能時間帯を考慮した探索結果をより正確にする上では、好ましい態様となり得る。
（３）本実施形態は、駅情報ＤＢ１３１と運行情報ＤＢ１３２とが独立して存在するものとして説明したが、これらを統合した１つのＤＢに置き換えても良い。また、駅情報ＤＢ１３１は、出発地条件及び目的地条件の生成用として１つ独立に存在させ、そのほかに運行情報ＤＢ１３２と共にもう１つ経路探索用として存在させるようにしても良い。
（４）本実施形態では、利用者による経路探索条件の入力を情報端末サービスサーバ２０を通じて受け付け、経路探索サーバ１０は、この経路探索条件に基づいて出発地条件、目的地条件を生成するとともに利用制限情報等を経路探索条件に付加し、最適経路候補を探索して利用者宛に出力するものとして説明したが、出発地及び目的地を含む経路探索条件の受付及びこれに基づく出発地条件及び目的地条件の生成までを他のサービスサーバで行い、経路探索ツール１１０は、出発地条件及び目的地条件に基づく経路探索を行い、探索結果を当該サービスサーバに出力するようにしても良い。
（５）本実施形態では、出発地条件と目的地条件の双方を経路探索に用いた場合の例を説明したが、利用者が入力した出発地と生成された目的地条件、あるいは、生成された出発地条件と利用者が入力した目的地の組み合わせを経路探索条件としても良い。
【００５５】
＜第２実施形態＞
経路探索は、複数のノードを結ぶ枝葉（移動経路）の集まりであるネットワークが複雑になればなるほど探索ループ回数が増加し、パフォーマンスが低下する傾向にある。逆に、ネットワークの無駄な枝葉を落とすこと、つまり枝葉を最適化することにより、パフォーマンスを著しく向上させることができる。このことから、第２実施形態では、経路探索エンジン１１３に最適化処理を行う機能を持たせ、これにより、経路探索時のパフォーマンスを向上させる例を説明する。
【００５６】
経路探索条件等については、第１実施形態と同じである。ここでは、一例として、ランドマーク機能を用いて利用者が登録した場所、施設等（便宜上、「ランドマーク」と称する）からの最寄駅の出入口、改札、ホームを含めた枝葉を最適化する場合の例を挙げる。「ランドマーク機能」とは、ランドマークを出発地又は目的地とし、そこからの最寄駅及びそこまでの移動経路、移動コスト（所要時間）等を、当該施設等の識別情報と関連付けて駅情報ＤＢ１３１において保持する機能である。ランドマークは、経路探索エンジン１１３による経路探索時に、ノードの一つとして扱われる。
また、ホームは、ｘ（自然数）番線などのピンポイントの場所を示す場合のほか、駅によっては複数番線を束にしたゾーン的な場所を示す場合がある。利用制限条件は、例えば曜日及び時間帯による入場可否／出場可否であり、出発地側か目的地側かが確定することにより、それを利用できるかどうかの判別が可能となる。
【００５７】
図８は、駅情報ＤＢ１３１に、ランドマークの最寄駅として関連付けられている駅の構内の説明図である。図８において、線の長さが相対的な距離（時間コスト）を表しているものとする。図示の例では、中央改札、北改札、東改札のように３つの改札が存在する。ホームには、路線の種類、列車進行方向（東京方面／高尾方面）等の属性情報が関連付けられている。例えば、第１ホームは「ＡＡＡ線」用、第２ホームは「ＢＢＢ線」用、第３ホームは「ＣＣＣ線」用、第４ホームは「ＤＤＤ線」用である。第１〜第３ホームは中央改札及び北改札と繋がっており、第４ホームは中央改札及び北改札のほか、東改札とも繋がっている。中央改札に近い出入口は第１〜第４出入口であり、北改札に近い出入口は第５及び第６出入口であり、東改札に近い出入口は第７出入口である。利用制限条件のある出入口は、第２出入口と第７出入口であり、改札は、東改札のみに利用制限条件がある。つまり、東改札に繋がる第７出入口は、共に利用制限条件がある。
【００５８】
経路探索エンジン１３１は、最適化処理を、以下の手順で実行する。
＝手順１＝
まず、ランドマークと繋がる最寄駅毎に、当該駅の出入口及び改札の組を、各々の利用制限条件の有無に応じて、４つのパターンに分類する。
・第１パターン：出入口（無）〜改札（無）
・第２パターン：出入口（有）〜改札（有）
・第３パターン：出入口（無）〜改札（有）
・第４パターン：出入口（有）〜改札（無）
【００５９】
このように分類する理由は、以下の通りである。
一般に、出入口に利用制限条件がある場合は改札に利用制限条件のない駅が多いが、例えば構内が広く、且つ、多くの改札が設けられている駅のように、改札毎に利用制限条件がある駅もある。また、百貨店や施設の出入口が駅の改札に直結しているために、出入口には利用制限条件はないが改札に利用制限条件がある駅もある。多数の出入口又は改札が設けられている駅では、両者の組み合わせを虱潰しのように探索していったのでは、それだけでパフォーマンスが著しく低下する（東京の新宿駅の組み合わせは２００以上）。一方、出入口及び改札の利用制限条件の有無だけに着目した場合、組み合わせパターンは４つのみとなり、処理対象が単純化される。そのため、この実施形態では、上記の４パターンに分類している。
【００６０】
＝手順２＝
パターン分類を終えると、いずれかのパターン、例えば第１パターンの出入口と改札との組をすべて抽出する。第１パターンは、いずれも利用制限条件のない組み合わせなので、図８の例では、以下の組が抽出される。
・第１出入口−中央改札
・第３出入口−中央改札
・第４出入口−中央改札
・第５出入口−北改札
・第６出入口−北改札
【００６１】
＝第３手順＝
上記のようにして抽出した組のうち、ランドマークから異なる出入口を経由して同じ改札を利用する経路の移動コスト、例えば所要時間を比較する。そして、所要時間が余計にかかる出入口を除外し、残った１つの出入口を当該改札との組として保存する。この処理は、ランドマークから異なる出入口を経由しても改札が同じであれば、その改札からホームと繋がる全ての経路が同じとなるのが一般的である点に着眼した処理である。
第１パターンでは、中央改札と繋がる３つの出入口（第１、第３、第４出入口）のうち、第３及び第４出入口との組が除外される。また、北改札と繋がる２つの出入口（第５，６出入口）のうち、第６出入口の組が除外される。その結果、第１パターンでは、以下の組だけが保存される。
・第１出入口−中央改札
・第５出入口−北改札
【００６２】
＝第４手順＝
次に、保存されている出入口と改札の組のうち、ランドマークから異なる出入口を経由して異なる改札を利用する場合において、ランドマーク−出入口−改札−ホームまでのすべての経路の移動コストを比較する。そして、比較対象となるものが無いか比較することが現実的でない経路、コストが同じになる経路、あるいは、移動コストの小さい経路以外の経路をすべて除外する。例えば、以下のように比較され、移動コストの大きい４つの組み併せが除外される。
・第１出入口−中央改札−第１ホーム ＜ 第５出入口−北改札−第１ホーム
・第１出入口−中央改札−第２ホーム ＜ 第５出入口−北改札−第２ホーム
・第１出入口−中央改札−第３ホーム ＜ 第５出入口−北改札−第３ホーム
・第１出入口−中央改札−第４ホーム ＞ 第５出入口−北改札−第４ホーム
【００６３】
なお、「比較対象することが現実的でない経路」とは、例えばそれを除外してしまうと、予め設定した閾値、例えば目的のホームに１０分以上の時間が余計にかかってしまう経路のようなものである。残った出入口と改札との組を保存する。
【００６４】
＝第５手順＝
第１パターンについての処理を終えると、第２パターンについて、手順２〜手順４の処理を行う。これにより、第２パターンについては、共に利用制限条件のある以下の組だけが保存される。
・東改札−第７出入口
【００６５】
また、第２パターンについての処理を終えると、第３パターンについて、手順２〜手順４の処理を行う。第３パターンは、利用制限条件の無い出入口と利用制限のある改札との組み合わせであるが、図８の例では、このような組み合わせは存在しないので、このパターンの処理の結果、保存される組は存在しない。
【００６６】
また、第３パターンについての処理を終えると、第４パターンについて、手順２〜手順４の処理を行う。第４パターンは、利用制限条件がある出入口と利用制限条件のない改札との組み合わせであるが、図８の例では、この組み合わせに該当するのは、以下の組しか存在しないので、この組だけが保存される。
・第２出入口−中央改札
【００６７】
以上の処理により、以下の組が保存される。
・第１出入口（無）−中央改札（無）
・第５出入口（無）−北改札（無）
・第２出入口（有）−中央改札（無）
・第７出入口（有）−東改札（有）
【００６８】
保存された情報を最適化された駅の情報としてランドマークの最寄駅に関連付けられた当該情報として更新し、経路探索の際のノードの一つとして用いる。
【００６９】
このように、第２実施形態では、ランドマークとして関連付けられた出発地又は目的地の最寄駅の出入口又は改札が複数存在する場合において、出入口−改札−ホームの移動経路の組み合わせを、動的に変化する出入口又は改札の利用制限条件を考慮して最適化処理を行うようにしたので、探索ループ回数が最適化処理前よりも軽減され、パフォーマンスの低下を抑制することができる。
【００７０】
パフォーマンスの低下が抑制されることを経路探索サーバ１０の性能向上とみなし、この性能向上の程度（性能向上率）をアムダールの法則（Amdahl's law）で定量化すると、以下のようになる。
最適化処理によって影響を受ける部分の割合、すなわち経路探索における駅情報ＤＢ１３１や運行情報ＤＢ１３２へのデータアクセスを除くタスクの割合をＰ、最適化処理による改善率（＝総出入口数÷有効出入口数×１００）をＳとすると、
性能向上率は、「１÷（１−Ｐ）＋Ｐ÷Ｓ」の式で表すことができる。
Ｐ=６０％
Ｓ=１７５％ （＝７÷４×１００）
とすると、性能向上率は、１.５９倍となる。
【００７１】
出入口−改札−ホームの移動パターンが非常に多い駅（新宿駅、東京駅など）を利用する経路探索と、逆に移動パターンが非常に少ない駅（目白駅など）を利用する経路探索とでは最適化を行った時と行わない時とでは性能向上率に大きな開きが生じ、これが処理速度の差として顕著に顕れる。
【００７２】
なお、第２実施形態では、ランドマーク機能を用いた場合の例を説明したが、出発地と目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた出入口、改札及びホームのいずれかが複数存在する場合に最適化処理の需要が発生するので、ランドマーク機能は、必須ではない。
また、第２実施形態では、複数の出入口のいくつかに利用制限条件が設定されている場合の最適化処理例について説明したが、利用制限条件のまったく無い複数の出入口や改札のある駅についても、同様に適用が可能である。要は、出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、探索ノードより除外すればよい。
また、第２実施形態では、最適化処理に際し、駅の出入口及び改札の組を、各々の利用制限条件の有無に応じて４つのパターンに分類した場合の例を示したが、単純にユニークな移動経路を残すように集約することもできる。
また、相対的に移動コストの大きい組み合わせが除外された出発地又は目的地を、例えば駅情報ＤＢ１３１にランドマークとして保持する機能を形成し、経路探索エンジン１１３が、保持されているランドマークを出発地又は目的地とした経路探索を行うようにすることで、その都度最適化処理を行う必要がなくなり、これによっても、パフォーマンスを向上させることができる。
また、第２実施形態では、移動コストとして、移動に要する所要時間を例に挙げて説明したが、エスカレータの有無や歩道の広さなど、移動の容易性を定量化したものを移動コストとして用いてもよい。
【符号の説明】
【００７３】
１０ 経路探索サーバ
２０ 情報端末サービスサーバ
５０ 携帯端末
６０ メールサーバ
７０ ＰＣ
１００ データ通信用インターフェース
１１０ 経路探索ツール
１１１ 探索条件受付部
１１２ 条件生成部
１１３ 経路探索エンジン
１３１ 駅情報ＤＢ
１３２ 運行情報ＤＢ
２００ 情報端末用インターフェース
２１０ サービス制御部
２２０ 探索条件入力部
２２１ ルールテーブル
２２２ 自動言語処理ツール
２２３ 変換ツール
【技術分野】
【０００１】
本発明は、徒歩及び電車等の公共交通網を利用して、任意の出発地から目的地に至る経路を探索する経路探索の技術に関する。
【背景技術】
【０００２】
電車等の公共交通網における最適な運行経路の探索技術については、本出願人によって開発された運行経路探索ソフト「駅すぱあと」（登録商標、非特許文献１参照）以来、複数の企業技術者の手により幾多の改良・改善が試みられてきた。この経路探索技術の一つとして、出発地から出発駅及び目的地から目的駅までを結ぶ徒歩経路も考慮して、出発地及び目的地から最も近い駅（最寄り駅）を出発駅及び目的駅として特定した後、さらに、当該出発駅及び目的駅が複数の出入口を有する場合には、出発地及び目的地から最も近い出入口（最寄り出入口）を特定する経路探索方法が存在している。
【０００３】
しかしながら、一旦、最寄り駅を特定した後に、当該最寄り駅の最寄り出入口を特定し、経路を探索する上記の方法では、最適経路が探索されない場合がある。
例えば、六本木ヒルズから新高円寺駅までを上記の方法で探索する場合、六本木ヒルズの最寄り駅は「日比谷線の六本木駅」で最寄り出入口は「出入口１ｃ」であるため、最適経路は〈六本木ヒルズ→（徒歩０分）→六本木駅［出入口１ｃ］→（日比谷線）→霞ヶ関→（丸の内線）→新高円寺〉となり、平均所要時間は３９分となる。
【０００４】
しかし、最寄り駅以外も出発駅の候補とすると、「大江戸線の六本木駅（出入口５）」も候補となり、経路は〈六本木ヒルズ→（徒歩４分）→六本木駅［出入口５］→（大江戸線）→中野坂上→（丸の内線）→新高円寺〉で、平均所要時間は３４分となるため、この経路が、総所要時間の短い最適経路となる。
なお、「日比谷線の六本木駅」と「大江戸線の六本木駅」とは行き来することができないため、一旦、最寄り駅である「日比谷線の六本木駅」が出発駅と特定されてしまうと、「大江戸線の六本木駅」から出発する経路は探索されないこととなる。
【０００５】
このように、出発地の最寄り駅を出発駅としない最適経路が存在する場合があり、上記のように、一旦、最寄り駅を特定した後に経路探索を行なう方法では、そのような最適経路が探索されないこととなる。
【０００６】
他方、１又は複数の駅を出発駅候補又は目的駅候補としておき、当該出発駅候補又は目的駅候補が複数の出入口を有する場合に、出発地及び目的地から徒歩で一番早く到達できる出入口を特定して、当該出入口の位置を出発駅候補又は目的駅候補の位置とみなしたうえで、最適経路を探索する最適経路探索装置も提案されている（特許文献１参照）。
【０００７】
この特許文献１に記載された最適経路探索装置では、はじめの段階で、最寄り駅以外の駅を出発駅候補から除外することがないため、最寄り駅を出発駅としない最適経路も探索することができる。また、出入口を複数有する出発駅候補又は目的駅候補については、最寄り出入口を特定するため、出発地から出発駅までを結ぶ徒歩経路と目的駅から目的地までを結ぶ徒歩経路も考慮した最適経路の探索を行なうことができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００３−１８２５７８号公報
【非特許文献】
【０００９】
【非特許文献１】「駅すぱあと」風雲録 柏崎ほか 日経ＢＰ社 ２００６年３月２０日発行
【発明の概要】
【発明が解決しようとする課題】
【００１０】
特許文献１に記載された装置による経路探索方法は、出発地から出発駅までを結ぶ徒歩経路と目的駅から目的地までを結ぶ徒歩経路とを考慮した経路探索を行なうことができる点で便利である。
【００１１】
しかし、駅の構内は、駅ごとに異なった構造となっており、曜日によっては利用できない出入口及び改札があったり、同じ路線でも上りホームと下りホームの間で行き来ができなかったり等、種々の要因により、出入口から所望の電車が発着するホームに至る経路は区々となり、その所要時間も大きく異なってしまう。
【００１２】
例えば、同じ路線で上りのホーム側と下りのホーム側のそれぞれに出入口（改札）があり、かつ、上りホームと下りホームの間で行き来できない駅が出発駅であり、出発地からの最寄り出入口が上りホーム側の出入口で、乗車すべき電車が下り電車である場合には、最寄り出入口（上りのホーム側の出入口）から入場する経路が最適経路であるとは限らない。そうであるにも関わらず、特許文献１に記載された装置では、経路探索の際に、出発地から駅の出入口までの徒歩経路は考慮するものの、駅構内、すなわち、出入口から改札及びホームまでの徒歩経路は考慮されていなかった。
【００１３】
本発明は、かかる背景のもと、駅構内、すなわち、駅出入口から改札、あるいはホームまでの経路を考慮した最適経路探索の技術を提供することを主たる課題とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明は、経路探索システム、経路探索方法及びコンピュータプログラムを提供する。
本発明の経路探索システムは、利用者により指定された出発地及び目的地を特定する特定手段と、交通機関の駅の情報を蓄積した駅情報ＤＢ（ＤＢはデータベースの略、以下同じ）から、前記特定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成する条件生成手段と、経路探索用の運行情報ＤＢにアクセスして前記生成された出発地条件及び前記特定された目的地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段とを有するものである。
【００１５】
本発明の他の経路探索システムは、利用者により指定された出発地及び目的地を特定する特定手段と、交通機関の駅の情報を蓄積した駅情報ＤＢから、前記特定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件生成手段と、経路探索用の運行情報ＤＢにアクセスして前記目的地条件及び前記特定された出発地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段とを有するものである。
駅出入口、改札、ホームもノードとして経路探索を行なうことから、駅構内の移動経路を考慮した経路探索を行なうことができる。
【００１６】
ある実施の態様では、前記条件生成手段は、前記駅出入口の位置情報、前記駅出入口から前記改札までの移動に要する第１移動コスト、前記改札からホームまでの移動に要する第２移動コストを取得し、取得したこれらの移動コストを新たな条件として付加するように構成されており、前記経路探索手段は、探索された経路毎に、前記位置情報に基づき算出される前記利用可能な駅出入口までの移動に要する第３コストと、前記第１移動コスト及び前記第２移動コストとを合算することにより、経路全体の総移動コストを算出し、この総移動コストが小さい順に前記最適経路候補をソートする。この場合は、探索結果から、特に、総移動コストが小さい経路を選出することが可能となる。
移動コストは、例えば移動時間情報のようなものである。
【００１７】
他の実施の態様では、さらに、前記条件生成手段は、前記駅出入口、前記改札又は前記ホームの利用制限情報を取得し、取得した利用制限情報をも出力するように構成されており、前記経路探索手段は、前記利用制限情報に基づき、前記探索された経路のうち利用が制限されている駅出入口、改札又はホームが含まれる最適経路候補を探索結果から除外するように動作する。
【００１８】
他の実施の態様では、前記経路探索手段は、前記出発地と前記目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた駅出入口、改札及びホームのいずれかが複数存在する場合に、駅出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該駅出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、前記ノードより除外する最適化処理を行う。構成をより簡略化する観点からは、前記相対的に移動コストの大きい組み合わせが除外された前記出発地又は前記目的地をランドマークとして保持するランドマーク保持手段をさらに備えるようにし、前記経路探索手段は、保持されているランドマークを前記出発地又は前記目的地とした経路探索を行うようにする。
これにより、ランドマークを用いるだけで上記最適化処理が実行されるので、パフォーマンスがより向上する。
【００１９】
本発明の経路探索方法は、交通機関の駅の情報を蓄積した駅情報ＤＢ及び経路探索用の運行情報ＤＢにアクセス可能なコンピュータが、前記駅情報ＤＢから、利用者に指定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者に指定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する処理と、前記運行情報ＤＢにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する処理と、を実行することを特徴とする、コンピュータによる経路探索方法である。
【００２０】
本発明のコンピュータプログラムは、交通機関の駅の情報を蓄積した駅情報ＤＢ及び経路探索用の運行情報ＤＢにアクセス可能なコンピュータを、前記駅情報ＤＢから、利用者により指定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者により指定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件出力手段；前記運行情報ＤＢにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段；として機能させる、経路探索用のコンピュータプログラムである。
【発明の効果】
【００２１】
本発明によれば、交通機関の駅名、駅出入口のほか、改札とホームの少なくとも一方をノードに含めて経路探索を行なうので、駅構内の徒歩経路を含む正確な経路探索が可能となるという特有の効果が得られる。改札や駅出入口等の利用制限情報を探索の条件として付加することも可能であり、この場合は、利用不可能な出入口及び改札を経由する経路を探索結果から除外して、実際に利用可能な経路のみの探索結果を得ることができるので、より現実に即した経路探索が可能となる。
経路探索手段がノードの最適化処理を行う構成では、探索ループ回数が減少するので、経路探索時のパフォーマンスが向上する。
【図面の簡単な説明】
【００２２】
【図１】第１実施形態の経路探索システムの全体構成図である。
【図２】従来の経路探索処理の概要を示す図である。
【図３】本実施形態の経路探索ツールによる経路探索処理の概要を示す図である。
【図４】改札・出入口テーブルの構造説明図である。
【図５】出入口〜改札間の移動時間テーブルの構造説明図である。
【図６】改札〜ホーム間の移動時間テーブルの構造説明図である。
【図７】経路探索ツールの処理手順図である。
【図８】第２実施形態の経路探索システムにおいて、最適化処理を行う場合の駅構内の説明図である。
【発明を実施するための形態】
【００２３】
以下、本発明を、携帯端末向けの経路探索サービスを可能にするネットワーク型の経路探索システムに適用した場合の実施の形態例を説明する。
【００２４】
＜第１実施形態＞
図１は、この実施形態の経路探索システムの全体構成図であり、特徴的な部分を掲示してある。この経路探索システムは、インターネット等のディジタルネットワークＮに接続される経路探索サーバ１０と、１又は複数の情報端末サービスサーバ２０（図示の例では１つ）と、交通機関の駅の情報、例えば駅の出入口（北口、南口、Ａ出口、Ｂ出口等：「駅出入口」、以下、単に出入口という）の位置情報（緯度、経度等）、出入口に繋がる改札、改札から到達可能なホーム、利用制限条件等のデータを蓄積した駅情報ＤＢ１３１と、経路探索用の運行情報、例えば交通機関（鉄道／バス）の路線網、時刻表、駅周辺の地図情報等のデータを蓄積した運行情報ＤＢ１３２とを含んで構成される。
ディジタルネットワークＮには、携帯端末５０の他、メールサーバ６０や情報端末の一例となるＰＣ（パーソナルコンピュータ）７０も接続可能になっている。
【００２５】
携帯端末５０及びＰＣ７０は、データ通信及びデータ処理機能を有する場合はダイレクトに、また、メール機能を有する場合にはメールサーバ６０を通じて、それぞれディジタルネットワークＮに接続することができる。
【００２６】
［経路探索サーバ］
経路探索サーバ１０は、サーバ本体と本発明のコンピュータプログラムとの協働により実現される。すなわち、サーバ本体が、コンピュータプログラムを読み込んで実行することにより、そのサーバ本体を、データ通信用インターフェース１００及び経路探索ツール１１０として機能させ、経路探索のための情報処理を実行可能にする。
【００２７】
データ通信用インターフェース１００は、データ通信及びデータ処理機能を有する携帯端末５０やＰＣ７０との双方向通信を可能にするとともに、これらの情報端末が閲覧可能な階層ページ画面を提供する。この階層ページ画面では、経路探索のＷｅｂサービスを行なうためのもので、経路探索条件の精緻な指定をシステム側と利用者との間でインタラクティブに行なうことにより、利用者が満足する経路探索を行なう環境を提供する。経路探索の結果情報の表示も、このページ画面で行なうことができる。
【００２８】
経路探索ツール１１０は、探索条件受付部１１１、条件生成部１１２及び経路探索エンジン１１３とを含む。
【００２９】
探索条件受付部１１１は、出発地及び目的地を含む経路探索条件を受け付ける。出発地と目的地の少なくとも一方については、利用者が直接入力（指定）したものをそのまま経路探索条件として特定してもよく、予め登録されているものを提示して選択させることで特定するようにしてもよい。
条件生成部１１２は、出発地から出発地条件、目的地から目的地条件を生成し、必要に応じて出入口や改札の利用制限情報を付加する。
経路探索エンジン１１３は、出入口、改札、ホーム、経由駅を、交通機関の路線網を構成するノードに含め、出発地から目的地に向かって各ノードに順次リンクを張ることを繰り返すことにより、経路探索条件に従う１又は複数の経路候補を探索し、経路探索条件に最も適合するものを最適経路候補とする。
【００３０】
経路探索エンジン１１３は、公知の推論エンジンも搭載しており、経路探索途中で、つまりリンクを張り付けていく過程で、所要時間が現実的でなくなる経路となることが判明した場合、例えば予めメモリに記憶された閾値と比べて大きくなった場合は、その時点でその経路候補についての次のノード以降の探索を止める。
経路探索エンジン１１３は、また、複数の経路候補の各々について、出発地から目的地に至るまでの総移動コスト、例えば時間を移動コストと捉える観点からは総所要時間を算出し、算出された総所要時間の小さい順に、複数の経路をソートする。さらに、経路中にその利用が制限される出入口や改札がある場合には、当該経路を除外したうえで、経路候補を特定する。
【００３１】
なお、経路探索エンジン１１３の基本機能部分は、本出願人が提供している経路探索ソフトウェア「駅すぱあと」（登録商標）を使用することができる。
【００３２】
次に、経路探索ツール１１０による最も一般的な経路探索処理、すなわち出発地と目的地との間の最適経路候補の特定を行なう場合の探索の概要を説明する。なお、ここでは、出発地と出発駅、目的地と目的駅とがそれぞれ異なるものとして説明する。
【００３３】
図２は、従来の経路探索処理の概要を示す図であり、図３は、本実施形態の経路探索ツール１１０による経路探索処理の概要を示す図である。
従来の経路探索ツールは、図２のように、出発地近くの最寄りの１または複数の出発駅候補を特定した後、各出発駅候補の出入口の位置情報に基づき、出発地から徒歩で一番早く到達できる１つの出入口を探索し、その出入口を経路探索の起点としていた。目的地についても同様の手順を行ない、経路探索を行なっていた。しかし、従来の経路探索ツールでは、出入口から改札を経由してホームに至る徒歩経路が考慮されていないため、出口改札が対向ホーム側に存在する場合があるなど、本来の最適経路候補が探索されるとは限らなかった。
【００３４】
これに対して、本実施形態の経路探索ツール１１０は、図３のように、出入口、その駅出入口に繋がる駅内の改札、改札から到達可能なホームをノードに含めて経路探索を行なうため、出入口から改札を経由してホームに至るまでの経路及び移動コストの一例となる所要時間を考慮した最適経路候補の探索が可能となる。
【００３５】
駅情報ＤＢ１３１には、改札・出入口テーブル、出入口〜改札間の移動時間テーブル及び改札〜ホーム間の移動時間テーブルが格納されている。図４乃至図６に各テーブルの概要を示す。
【００３６】
図４は、改札・出入口テーブルの構造例を示した図である。
改札・出入口テーブル１１５には、出入口の位置、改札の位置、出入口・改札の利用制限情報等が記録されるようになっている。
具体的には、駅名称１１５ａに、指標データとして各駅の名称が文字列で記録されている。駅コード１１５ｂには、各駅を識別するためのコード（数値）が記録されている。名称タイプ１１５ｃ及び名称１１５ｄには、ホーム、改札、出入口のほか、他の交通機関であるバス乗降場がどこかを表す数値及び文字列が記録されている。名称真偽１１５ｅには、真正な名称であるか管理用の名称であるかの別を表す数値（０か１）が記録されている。コード１１５ｆには、当該データを別のデータに結びつけるためのコード（数値）が記録されており、案内コード１１５ｇには、出入口データが入力されたときのみ有効となるコード（数値）が記録されている。位置１１５ｈのフィールドには、ホーム、改札、出入口又はバス乗降場の緯度、経度、高度を表す数値が位置情報の一例として記録される。利用制限条件有無１１５ｉには、ホーム、改札、出入口又はバス乗降場の利用制限条件の有無を表す数値（０か１）が割り当てられており、利用制限条件１１５ｊには、乗車若しくは降車時のみしか利用できない、平日しか利用できない等の利用制限条件及び利用可能時間の割当等が記録されている。
【００３７】
図５は、出入口〜改札間の移動時間テーブルの構造例を示した図である。
出入口〜改札間の移動時間テーブル１１６には、出入口から改札に至るまでの所要時間が記録されている。具体的には、駅名称１１６ａに、指標データとして各駅の名称が文字列で記録されており、駅コード１１６ｂには、各駅を識別するためのコード（数値）が記録されている。出入口コード１１６ｃには、出入口を識別するためのコード（数値）が記録されており、改札コード１１６ｄには、改札を識別するためのコード（数値）が記録されている。移動時間１１６ｅには、出入口から改札までの移動時間が数値（秒）で記録されている。
【００３８】
図６は、改札〜ホーム間の移動時間の移動時間テーブルの構造例を示した図である。
改札〜ホーム間の移動時間データ１１７には、改札からホームに至るまでの所要時間が記録されるようになっている。
具体的には、駅名称１１７ａに、指標データとして各駅の名称が文字列で記録されており、駅コード１１７ｂには、各駅を識別するためのコード（数値）が記録されている。改札コードタイプ１１７ｃには、例えば、ゲートコード（１０Ｈ）が固定値として記録されている。改札名称１１７ｄには、指標データとして改札の名称が文字列で記録されている。改札コード１１７ｅには、改札を識別するためのコード（数値）が記録されている。改札コード方向属性１１７ｆには、上り・下り両方向で利用可能であることを示す数値（例えば、０）が固定値として記録されている。ホーム側コードタイプ１１７ｇには、ホームのタイプを示すための数値（例えば、すべて（０Ｈ）、路線コード（１Ｈ）、交通手段コード（４Ｈ）、会社コード（８Ｈ）、ゲートコード（１０Ｈ）等）が記録されている。ホーム側名称１１７ｈには、指標データとして、各ホームの名称が記録されている。ホーム側コード１１７ｉには、ホームを識別するためのコード（数値）が記録されている。ホーム側コード方向属性には１１７ｊ、ホームが、上り方向を対象とするか、下り方向を対象とするか、両方向を対象とするかの別を識別するための数値（０、１、又は２）が記録されている。乗り換え時間１１７ｋには、乗換時間（改札からホームまでの所要時間）が数値（秒）で記録されている。
【００３９】
［情報端末サービスサーバ］
情報端末サービスサーバ２０は、主として、携帯端末５０等からの電子メールでの経路探索の依頼に対応するためのもので、情報端末用インターフェース２００、サービス制御部２１０、探索条件入力部２２０を含んで構成される。経路探索サーバ１０が携帯端末５０等から、メールを介さずに直接、経路探索条件の入力を受け付ける場合には、この情報端末サービスサーバはなくてもよい。
【００４０】
情報端末用インターフェース２００は、ディジタルネットワークＮに接続されているメールサーバ６０を介して携帯端末５０又はＰＣ７０との電子メールによる双方向通信を可能にするものである。電子メールのみを受け付けるようにした点で、データ通信用インターフェース１００とは区別される。
【００４１】
サービス制御部２１０は、情報端末サービスサーバ全体における各種動作を制御する。例えば、携帯端末５０から電子メールを受信したことを情報端末用インターフェース２００が検知したときに、探索条件入力部２２０を制御して電子メール中の依頼文から経路探索条件を含む部分を抽出させ、抽出された経路探索条件を利用者による操作を要することなく経路探索ツール１１０に入力させる。つまり、自動入力・自動実行依頼である。経路探索ツール１１０で最適経路候補が特定されたときは、これを経路探索ツール１１０より受け取り、受け取った最適経路候補を編集部２１１で携帯端末５０のディスプレイで表示可能なサイズの電子情報に編集する。そして、携帯端末用インターフェース２２０を制御することにより、編集した電子情報をメールサーバ６０を介して電子メールの送信元である携帯端末５０に返信し、表示させる。
【００４２】
探索条件入力部２２０は、携帯端末５０等から電子メールで送信された自然言語による探索条件を受け付けるためのものであり、ルールテーブル２２１、自然言語処理ツール２２２及び変換ツール２２３を有している。
【００４３】
ルールテーブル２２１には、語又は語句と、経路探索ツール１１０が認識可能な経路探索条件との対応ルールが記録されている。また、自然言語処理ツール２２２は、情報端末用インターフェース２００を通じて受信した、自然言語から成る依頼文から語又は語句を抽出する。さらに、変換ツール２２３は、自然言語処理ツール２２２で抽出した語又は語句をルールテーブル２２１に従って経路探索条件に変換する。
【００４４】
［運用形態］
次に、本実施形態の経路探索システムの運用形態例を、経路探索ツール１１０での処理を中心に説明する。利用者が、携帯端末５０によって、出発地から目的地までの経路候補のうち、総コスト、特に総所要時間が短い経路を最適経路候補として探索する場合の例を説明する。図７は 経路探索ツール１１０の処理手順図である。
【００４５】
利用者は、携帯端末５０の表示画面から直接、または、電子メールで、経路探索条件を入力することにより、経路探索を依頼する。その際、条件入力を簡易にするため、経路探索条件のうち、出発地については、携帯端末５０のＧＰＳ受信機能を利用して取得した現在位置を自動的に設定するものとしてもよい。なお、携帯端末５０が地図表示機能を有する場合には、地図上から出発地と目的地を選択するものとしてもよい。
【００４６】
経路検索ツール１１０が、利用者によって入力された、出発地及び目的地を含む経路探索条件を受け付ける（ステップＳ１０１）。経路探索が、自然言語で記載された電子メールで依頼された場合には、一旦、情報端末サービスサーバ２０の探索条件入力部２２０で、自然言語で記述された経路探索条件を経路探索ツール１１０が認識可能な経路探索条件に変換し、この変換された経路探索条件を受け付けることとなる。経路探索条件には、出発地及び目的地のほか、現在時刻、経由駅等の含まれるが、ここでは、便宜上、出発地及び目的地だけを受け付けたものとして説明する。
【００４７】
経路探索ツール１１０は、条件生成部１１２で、出発地付近に存在する出入口の中から探し出された複数個の出入口候補に関する情報を、出発地をキーとして駅情報ＤＢ１３１より取得する（ステップＳ１０２）。例えば、出発地から、徒歩１０分、半径３００ｍ以内等を基準に利用可能な出入口候補を特定する。次に、目的地付近に存在する出入口の中から探し出された複数個の出入口候補に関する情報を、目的地をキーとして駅情報ＤＢ１３１より取得する（ステップＳ１０３）。例えば、目的地から、徒歩１０分、半径３００ｍ以内等を基準に利用可能な出入口候補を特定する。そして、取得した情報に基づいて、受け付けた出発地に代わる出発地条件、受け付けた目的地に代えて目的地条件を生成する。
【００４８】
出発地条件及び目的地条件は、それぞれ出入口候補、当該出入口候補が存在する駅の改札、当該改札から到達可能なホームのようなノードの組み合わせ数だけ作成される。例えば、出発地付近の駅が三田駅（東京都）で、その駅の出入口が１０個、改札が４つ、ホームが１つの場合、４０通りの組み合わせのすべてを出発地条件とする。目的地条件についても同様である。
【００４９】
経路探索ツール１１０は、出入口、改札及びホームをノードとして含む出発地条件及び目的地条件を用いて、出発地から目的地までの経路を探索する（ステップＳ１０４）。経路の探索は、駅情報ＤＢ１３１の駅情報及び運行情報ＤＢ１３２の運行情報を参照してノードとリンクの組み合わせを辿ることにより行う。
【００５０】
このようにして探索された経路のそれぞれについて、駅情報ＤＢ１３１の改札・出入口テーブル１１５に記録される利用制限条件有無１１５ｉや利用制限条件１１５ｊを参照し、経路に含まれる出入口及び改札が全て利用可能であるか否かを判定する（ステップＳ１０５）。判定の結果、経路に利用不可能な出入口又は改札を含む場合には（ステップＳ１０５：No）、当該経路を探索結果から除外した上で、ステップＳ１０７の処理に移る（ステップＳ１０６）。一方、経路に含まれる出入口又は改札が全て利用可能である場合は、直ちにステップＳ１０７の処理に移る（ステップＳ１０５：Yes）。
【００５１】
ステップＳ１０７では、経路毎にリンクの総所要時間を算出し、総所要時間の少ない順に経路のソートを行った後、１つ又は所定数の経路を、最適経路候補として、利用者宛に出力する。
リンクの総所要時間の計算は、例えば、運行情報ＤＢ１３２の地図情報と駅情報ＤＢ１３１の駅出入口の位置情報から、出発地及び目的地と出入口の間の徒歩による所要時間を算出し、駅情報ＤＢ１１４の出入口〜改札間の移動時間データ１１６と改札〜出入口間の移動時間データ１１７から出入口とホームの間の徒歩による所要時間を算出し、運行情報ＤＢ１１３の時刻表から、駅と駅の間の交通機関による所要時間を算出し、それらを合算することにより行なう。
【００５２】
このように、本実施形態の経路探索システムでは、利用者によって入力された出発地、目的地に代えて、それぞれ駅の出入口、改札及びホームの組み合わせ数の分だけ出発地条件、目的地条件を生成することにより、駅の出入口、改札及びホームを、交通機関の路線網を構成するノードとして含めた経路探索を行うことができる。
これにより、駅構内の徒歩経路を含む経路探索が可能となるので、出発地の最寄り駅を出発駅、あるいは、目的地の最寄り駅を目的駅としない最適経路が探索されたり、同じ路線で上りのホーム側と下りのホーム側のそれぞれに出入口（改札）がある場合に誤って利用者を誘導してしまうことがなくなり、利用者にとって非常に便利な経路探索サービスを提供することができる。
【００５３】
また、出入口や改札の利用制限条件を予め記録しておき、時間によっては利用不可能な出入口及び改札を経由する経路を探索結果から除外するようにしたので、曜日によっては利用できない出入口及び改札があったり、同じ路線でも上りホームと下りホームの間で行き来ができなかったりしても、それを考慮した所要時間を利用者に正しく伝達することができる。
【００５４】
本実施形態は以上の通りであるが、本発明は、上記の実施形態例に限らず、以下のような種々の変形実施が可能である。
（１）本実施形態では、改札とホームの双方をノードに含めた場合の例を説明したが、これらはいずれか一方のみであっても良い。
（２）本実施形態では、利用者が入力する経路探索条件に必ず含むものとして出発地及び目的地の場合を例に挙げたが、出発予定時刻、到着予定時刻、利用時間帯等の時刻情報も必須入力としても良い。出入口の利用可能時間帯を考慮した探索結果をより正確にする上では、好ましい態様となり得る。
（３）本実施形態は、駅情報ＤＢ１３１と運行情報ＤＢ１３２とが独立して存在するものとして説明したが、これらを統合した１つのＤＢに置き換えても良い。また、駅情報ＤＢ１３１は、出発地条件及び目的地条件の生成用として１つ独立に存在させ、そのほかに運行情報ＤＢ１３２と共にもう１つ経路探索用として存在させるようにしても良い。
（４）本実施形態では、利用者による経路探索条件の入力を情報端末サービスサーバ２０を通じて受け付け、経路探索サーバ１０は、この経路探索条件に基づいて出発地条件、目的地条件を生成するとともに利用制限情報等を経路探索条件に付加し、最適経路候補を探索して利用者宛に出力するものとして説明したが、出発地及び目的地を含む経路探索条件の受付及びこれに基づく出発地条件及び目的地条件の生成までを他のサービスサーバで行い、経路探索ツール１１０は、出発地条件及び目的地条件に基づく経路探索を行い、探索結果を当該サービスサーバに出力するようにしても良い。
（５）本実施形態では、出発地条件と目的地条件の双方を経路探索に用いた場合の例を説明したが、利用者が入力した出発地と生成された目的地条件、あるいは、生成された出発地条件と利用者が入力した目的地の組み合わせを経路探索条件としても良い。
【００５５】
＜第２実施形態＞
経路探索は、複数のノードを結ぶ枝葉（移動経路）の集まりであるネットワークが複雑になればなるほど探索ループ回数が増加し、パフォーマンスが低下する傾向にある。逆に、ネットワークの無駄な枝葉を落とすこと、つまり枝葉を最適化することにより、パフォーマンスを著しく向上させることができる。このことから、第２実施形態では、経路探索エンジン１１３に最適化処理を行う機能を持たせ、これにより、経路探索時のパフォーマンスを向上させる例を説明する。
【００５６】
経路探索条件等については、第１実施形態と同じである。ここでは、一例として、ランドマーク機能を用いて利用者が登録した場所、施設等（便宜上、「ランドマーク」と称する）からの最寄駅の出入口、改札、ホームを含めた枝葉を最適化する場合の例を挙げる。「ランドマーク機能」とは、ランドマークを出発地又は目的地とし、そこからの最寄駅及びそこまでの移動経路、移動コスト（所要時間）等を、当該施設等の識別情報と関連付けて駅情報ＤＢ１３１において保持する機能である。ランドマークは、経路探索エンジン１１３による経路探索時に、ノードの一つとして扱われる。
また、ホームは、ｘ（自然数）番線などのピンポイントの場所を示す場合のほか、駅によっては複数番線を束にしたゾーン的な場所を示す場合がある。利用制限条件は、例えば曜日及び時間帯による入場可否／出場可否であり、出発地側か目的地側かが確定することにより、それを利用できるかどうかの判別が可能となる。
【００５７】
図８は、駅情報ＤＢ１３１に、ランドマークの最寄駅として関連付けられている駅の構内の説明図である。図８において、線の長さが相対的な距離（時間コスト）を表しているものとする。図示の例では、中央改札、北改札、東改札のように３つの改札が存在する。ホームには、路線の種類、列車進行方向（東京方面／高尾方面）等の属性情報が関連付けられている。例えば、第１ホームは「ＡＡＡ線」用、第２ホームは「ＢＢＢ線」用、第３ホームは「ＣＣＣ線」用、第４ホームは「ＤＤＤ線」用である。第１〜第３ホームは中央改札及び北改札と繋がっており、第４ホームは中央改札及び北改札のほか、東改札とも繋がっている。中央改札に近い出入口は第１〜第４出入口であり、北改札に近い出入口は第５及び第６出入口であり、東改札に近い出入口は第７出入口である。利用制限条件のある出入口は、第２出入口と第７出入口であり、改札は、東改札のみに利用制限条件がある。つまり、東改札に繋がる第７出入口は、共に利用制限条件がある。
【００５８】
経路探索エンジン１３１は、最適化処理を、以下の手順で実行する。
＝手順１＝
まず、ランドマークと繋がる最寄駅毎に、当該駅の出入口及び改札の組を、各々の利用制限条件の有無に応じて、４つのパターンに分類する。
・第１パターン：出入口（無）〜改札（無）
・第２パターン：出入口（有）〜改札（有）
・第３パターン：出入口（無）〜改札（有）
・第４パターン：出入口（有）〜改札（無）
【００５９】
このように分類する理由は、以下の通りである。
一般に、出入口に利用制限条件がある場合は改札に利用制限条件のない駅が多いが、例えば構内が広く、且つ、多くの改札が設けられている駅のように、改札毎に利用制限条件がある駅もある。また、百貨店や施設の出入口が駅の改札に直結しているために、出入口には利用制限条件はないが改札に利用制限条件がある駅もある。多数の出入口又は改札が設けられている駅では、両者の組み合わせを虱潰しのように探索していったのでは、それだけでパフォーマンスが著しく低下する（東京の新宿駅の組み合わせは２００以上）。一方、出入口及び改札の利用制限条件の有無だけに着目した場合、組み合わせパターンは４つのみとなり、処理対象が単純化される。そのため、この実施形態では、上記の４パターンに分類している。
【００６０】
＝手順２＝
パターン分類を終えると、いずれかのパターン、例えば第１パターンの出入口と改札との組をすべて抽出する。第１パターンは、いずれも利用制限条件のない組み合わせなので、図８の例では、以下の組が抽出される。
・第１出入口−中央改札
・第３出入口−中央改札
・第４出入口−中央改札
・第５出入口−北改札
・第６出入口−北改札
【００６１】
＝第３手順＝
上記のようにして抽出した組のうち、ランドマークから異なる出入口を経由して同じ改札を利用する経路の移動コスト、例えば所要時間を比較する。そして、所要時間が余計にかかる出入口を除外し、残った１つの出入口を当該改札との組として保存する。この処理は、ランドマークから異なる出入口を経由しても改札が同じであれば、その改札からホームと繋がる全ての経路が同じとなるのが一般的である点に着眼した処理である。
第１パターンでは、中央改札と繋がる３つの出入口（第１、第３、第４出入口）のうち、第３及び第４出入口との組が除外される。また、北改札と繋がる２つの出入口（第５，６出入口）のうち、第６出入口の組が除外される。その結果、第１パターンでは、以下の組だけが保存される。
・第１出入口−中央改札
・第５出入口−北改札
【００６２】
＝第４手順＝
次に、保存されている出入口と改札の組のうち、ランドマークから異なる出入口を経由して異なる改札を利用する場合において、ランドマーク−出入口−改札−ホームまでのすべての経路の移動コストを比較する。そして、比較対象となるものが無いか比較することが現実的でない経路、コストが同じになる経路、あるいは、移動コストの小さい経路以外の経路をすべて除外する。例えば、以下のように比較され、移動コストの大きい４つの組み併せが除外される。
・第１出入口−中央改札−第１ホーム ＜ 第５出入口−北改札−第１ホーム
・第１出入口−中央改札−第２ホーム ＜ 第５出入口−北改札−第２ホーム
・第１出入口−中央改札−第３ホーム ＜ 第５出入口−北改札−第３ホーム
・第１出入口−中央改札−第４ホーム ＞ 第５出入口−北改札−第４ホーム
【００６３】
なお、「比較対象することが現実的でない経路」とは、例えばそれを除外してしまうと、予め設定した閾値、例えば目的のホームに１０分以上の時間が余計にかかってしまう経路のようなものである。残った出入口と改札との組を保存する。
【００６４】
＝第５手順＝
第１パターンについての処理を終えると、第２パターンについて、手順２〜手順４の処理を行う。これにより、第２パターンについては、共に利用制限条件のある以下の組だけが保存される。
・東改札−第７出入口
【００６５】
また、第２パターンについての処理を終えると、第３パターンについて、手順２〜手順４の処理を行う。第３パターンは、利用制限条件の無い出入口と利用制限のある改札との組み合わせであるが、図８の例では、このような組み合わせは存在しないので、このパターンの処理の結果、保存される組は存在しない。
【００６６】
また、第３パターンについての処理を終えると、第４パターンについて、手順２〜手順４の処理を行う。第４パターンは、利用制限条件がある出入口と利用制限条件のない改札との組み合わせであるが、図８の例では、この組み合わせに該当するのは、以下の組しか存在しないので、この組だけが保存される。
・第２出入口−中央改札
【００６７】
以上の処理により、以下の組が保存される。
・第１出入口（無）−中央改札（無）
・第５出入口（無）−北改札（無）
・第２出入口（有）−中央改札（無）
・第７出入口（有）−東改札（有）
【００６８】
保存された情報を最適化された駅の情報としてランドマークの最寄駅に関連付けられた当該情報として更新し、経路探索の際のノードの一つとして用いる。
【００６９】
このように、第２実施形態では、ランドマークとして関連付けられた出発地又は目的地の最寄駅の出入口又は改札が複数存在する場合において、出入口−改札−ホームの移動経路の組み合わせを、動的に変化する出入口又は改札の利用制限条件を考慮して最適化処理を行うようにしたので、探索ループ回数が最適化処理前よりも軽減され、パフォーマンスの低下を抑制することができる。
【００７０】
パフォーマンスの低下が抑制されることを経路探索サーバ１０の性能向上とみなし、この性能向上の程度（性能向上率）をアムダールの法則（Amdahl's law）で定量化すると、以下のようになる。
最適化処理によって影響を受ける部分の割合、すなわち経路探索における駅情報ＤＢ１３１や運行情報ＤＢ１３２へのデータアクセスを除くタスクの割合をＰ、最適化処理による改善率（＝総出入口数÷有効出入口数×１００）をＳとすると、
性能向上率は、「１÷（１−Ｐ）＋Ｐ÷Ｓ」の式で表すことができる。
Ｐ=６０％
Ｓ=１７５％ （＝７÷４×１００）
とすると、性能向上率は、１.５９倍となる。
【００７１】
出入口−改札−ホームの移動パターンが非常に多い駅（新宿駅、東京駅など）を利用する経路探索と、逆に移動パターンが非常に少ない駅（目白駅など）を利用する経路探索とでは最適化を行った時と行わない時とでは性能向上率に大きな開きが生じ、これが処理速度の差として顕著に顕れる。
【００７２】
なお、第２実施形態では、ランドマーク機能を用いた場合の例を説明したが、出発地と目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた出入口、改札及びホームのいずれかが複数存在する場合に最適化処理の需要が発生するので、ランドマーク機能は、必須ではない。
また、第２実施形態では、複数の出入口のいくつかに利用制限条件が設定されている場合の最適化処理例について説明したが、利用制限条件のまったく無い複数の出入口や改札のある駅についても、同様に適用が可能である。要は、出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、探索ノードより除外すればよい。
また、第２実施形態では、最適化処理に際し、駅の出入口及び改札の組を、各々の利用制限条件の有無に応じて４つのパターンに分類した場合の例を示したが、単純にユニークな移動経路を残すように集約することもできる。
また、相対的に移動コストの大きい組み合わせが除外された出発地又は目的地を、例えば駅情報ＤＢ１３１にランドマークとして保持する機能を形成し、経路探索エンジン１１３が、保持されているランドマークを出発地又は目的地とした経路探索を行うようにすることで、その都度最適化処理を行う必要がなくなり、これによっても、パフォーマンスを向上させることができる。
また、第２実施形態では、移動コストとして、移動に要する所要時間を例に挙げて説明したが、エスカレータの有無や歩道の広さなど、移動の容易性を定量化したものを移動コストとして用いてもよい。
【符号の説明】
【００７３】
１０ 経路探索サーバ
２０ 情報端末サービスサーバ
５０ 携帯端末
６０ メールサーバ
７０ ＰＣ
１００ データ通信用インターフェース
１１０ 経路探索ツール
１１１ 探索条件受付部
１１２ 条件生成部
１１３ 経路探索エンジン
１３１ 駅情報ＤＢ
１３２ 運行情報ＤＢ
２００ 情報端末用インターフェース
２１０ サービス制御部
２２０ 探索条件入力部
２２１ ルールテーブル
２２２ 自動言語処理ツール
２２３ 変換ツール
【特許請求の範囲】
【請求項１】
利用者により指定された出発地及び目的地を特定する特定手段と、
交通機関の駅の情報を蓄積した駅情報ＤＢから、前記特定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成する条件生成手段と、
経路探索用の運行情報ＤＢにアクセスして前記生成された出発地条件及び前記特定された目的地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段と、
を有する経路探索システム。
【請求項２】
利用者により指定された出発地及び目的地を特定する特定手段と、
交通機関の駅の情報を蓄積した駅情報ＤＢから、前記特定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件生成手段と、
経路探索用の運行情報ＤＢにアクセスして前記目的地条件及び前記特定された出発地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段と、
を有する経路探索システム。
【請求項３】
前記条件生成手段は、前記駅出入口の位置情報、前記駅出入口から前記改札までの移動に要する第１移動コスト、前記改札からホームまでの移動に要する第２移動コストを取得し、取得したこれらの移動コストを新たな条件として付加するように構成されており、
前記経路探索手段は、探索された経路毎に、前記位置情報に基づき算出される前記利用可能な駅出入口までの移動に要する第３コストと、前記第１移動コスト及び前記第２移動コストとを合算することにより、経路全体の総移動コストを算出し、この総移動コストが小さい順に前記最適経路候補をソートする、
請求項１又は２記載の経路探索システム。
【請求項４】
前記条件生成手段は、前記駅出入口、前記改札又は前記ホームの利用制限情報を取得し、取得した利用制限情報を新たな条件として付加するように構成されており、
前記経路探索手段は、前記利用制限情報に基づき、前記探索された経路のうち利用が制限されている駅出入口、改札又はホームが含まれる最適経路候補を探索結果から除外する、
請求項３記載の経路探索システム。
【請求項５】
前記経路探索手段は、前記出発地と前記目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた駅出入口、改札及びホームのいずれかが複数存在する場合に、駅出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該駅出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、前記ノードより除外する最適化処理を行う、
請求項１ないし４のいずれかの項記載の経路探索システム。
【請求項６】
前記相対的に移動コストの大きい組み合わせが除外された前記出発地又は前記目的地をランドマークとして保持するランドマーク保持手段をさらに備えており、
前記経路探索手段は、保持されているランドマークを前記出発地又は前記目的地とした経路探索を行う、
請求項５記載の経路探索システム。
【請求項７】
交通機関の駅の情報を蓄積した駅情報ＤＢ及び経路探索用の運行情報ＤＢにアクセス可能なコンピュータが、
前記駅情報ＤＢから、利用者に指定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者に指定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する処理と、
前記運行情報ＤＢにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する処理と、を実行することを特徴とする、
コンピュータによる経路探索方法。
【請求項８】
交通機関の駅の情報を蓄積した駅情報ＤＢ及び経路探索用の運行情報ＤＢにアクセス可能なコンピュータを、
前記駅情報ＤＢから、利用者により指定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者により指定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件出力手段；
前記運行情報ＤＢにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段；として機能させる、
経路探索用のコンピュータプログラム。
【請求項１】
利用者により指定された出発地及び目的地を特定する特定手段と、
交通機関の駅の情報を蓄積した駅情報ＤＢから、前記特定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成する条件生成手段と、
経路探索用の運行情報ＤＢにアクセスして前記生成された出発地条件及び前記特定された目的地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段と、
を有する経路探索システム。
【請求項２】
利用者により指定された出発地及び目的地を特定する特定手段と、
交通機関の駅の情報を蓄積した駅情報ＤＢから、前記特定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件生成手段と、
経路探索用の運行情報ＤＢにアクセスして前記目的地条件及び前記特定された出発地をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段と、
を有する経路探索システム。
【請求項３】
前記条件生成手段は、前記駅出入口の位置情報、前記駅出入口から前記改札までの移動に要する第１移動コスト、前記改札からホームまでの移動に要する第２移動コストを取得し、取得したこれらの移動コストを新たな条件として付加するように構成されており、
前記経路探索手段は、探索された経路毎に、前記位置情報に基づき算出される前記利用可能な駅出入口までの移動に要する第３コストと、前記第１移動コスト及び前記第２移動コストとを合算することにより、経路全体の総移動コストを算出し、この総移動コストが小さい順に前記最適経路候補をソートする、
請求項１又は２記載の経路探索システム。
【請求項４】
前記条件生成手段は、前記駅出入口、前記改札又は前記ホームの利用制限情報を取得し、取得した利用制限情報を新たな条件として付加するように構成されており、
前記経路探索手段は、前記利用制限情報に基づき、前記探索された経路のうち利用が制限されている駅出入口、改札又はホームが含まれる最適経路候補を探索結果から除外する、
請求項３記載の経路探索システム。
【請求項５】
前記経路探索手段は、前記出発地と前記目的地の一方が固定され、且つ、固定された出発地又は目的地に関連付けられた駅出入口、改札及びホームのいずれかが複数存在する場合に、駅出入口毎に、改札までの移動に要する移動コスト又は改札−ホームまでの移動に要する移動コストを当該駅出入口を含むすべての組み合わせについて比較し、相対的に移動コストの大きい組み合わせを、経路探索前に、前記ノードより除外する最適化処理を行う、
請求項１ないし４のいずれかの項記載の経路探索システム。
【請求項６】
前記相対的に移動コストの大きい組み合わせが除外された前記出発地又は前記目的地をランドマークとして保持するランドマーク保持手段をさらに備えており、
前記経路探索手段は、保持されているランドマークを前記出発地又は前記目的地とした経路探索を行う、
請求項５記載の経路探索システム。
【請求項７】
交通機関の駅の情報を蓄積した駅情報ＤＢ及び経路探索用の運行情報ＤＢにアクセス可能なコンピュータが、
前記駅情報ＤＢから、利用者に指定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者に指定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する処理と、
前記運行情報ＤＢにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する処理と、を実行することを特徴とする、
コンピュータによる経路探索方法。
【請求項８】
交通機関の駅の情報を蓄積した駅情報ＤＢ及び経路探索用の運行情報ＤＢにアクセス可能なコンピュータを、
前記駅情報ＤＢから、利用者により指定された出発地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記出発地に代わる出発地条件を生成するとともに、利用者により指定された目的地において利用可能な１又は複数の駅出入口の情報と、各駅出入口に繋がる改札及び当該改札から到達可能なホームの少なくとも一方の情報とを取得し、取得した情報に基づいて前記目的地に代わる目的地条件を生成する条件出力手段；
前記運行情報ＤＢにアクセスして前記出発地条件及び前記目的地条件をそれぞれ交通機関の路線網を構成するノードに含めた経路探索を行うことにより、前記出発地から前記目的地に至る最適経路候補を探索する経路探索手段；として機能させる、
経路探索用のコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−２７７５７５（Ｐ２０１０−２７７５７５Ａ）
【公開日】平成２２年１２月９日（２０１０．１２．９）
【国際特許分類】
【出願番号】特願２０１０−３６４０９（Ｐ２０１０−３６４０９）
【出願日】平成２２年２月２２日（２０１０．２．２２）
【出願人】（５９６１３０１８５）株式会社 ヴァル研究所 (14)
【Ｆターム（参考）】
【公開日】平成２２年１２月９日（２０１０．１２．９）
【国際特許分類】
【出願日】平成２２年２月２２日（２０１０．２．２２）
【出願人】（５９６１３０１８５）株式会社 ヴァル研究所 (14)
【Ｆターム（参考）】
[ Back to top ]