公共トランジット旅行計画システム及び方法は、ジャーニーのための最適公共トランジットルートを決定するために、クエリ時間に先立って、トランジット情報の広範な前処理を用いる。クエリ時間では、トランジット情報が既にシステムにより処理されているので、クエリを遂行するためには非常に少しの計算しか要さない。システムは、公共トランジットジャーニーに関するクエリに応じた、公共トランジット指示をユーザに供給する。

【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、公共交通機関トリップ（trip: 旅行、移動）計画に関し、より詳しくは、処理されたトランジット（transit:交通、通行、乗換）情報を用いて公共交通機関の指示を提供するために必要な計算時間と資源を極小化することである。
【０００２】
関連する出願の参照
この出願は、２００９年１１月１１日に出願された米国特許仮出願番号第６１／２６０３４２号に基づく利益を主張し、当該仮出願に記載された全ての記載内容を援用するものである。
【背景技術】
【０００３】
公共交通機関インフラストラクチャーの向上、環境意識の高まり、及び、ガソリン料金の値上がりに伴い、多くの人々が各種形態の公共交通機関を使用し始めた。彼ら自身が所有する車両を使用するよりも、人々は、移動の必要に際して、いや増しに、鉄道、バス及び／又はフェリーを使用している。この公共交通機関の使用の増加のため、公共トランジット計画システムが発達している。これらシステムは、種々の形式の公共交通機関を経由する、スタート地から目的地までの間の移動の指示をユーザに供給する。
【０００４】
典型的には、これらのシステムにおいて、スタート地と目的地を含む問い合わせが受信され、トランジット計画システムは、１以上の形式の公共交通機関を用いた目的地に到達するための指示を漸次供給する。例えば、指示は、トリップの目的地に到達するためにどの公共トランジット車両（例えばバス、電車など）を使し、どの公共トランジット地点で停まるべきかのシークエンスを含む。指示は、旅中の種々のトランジット地点で必要とされる別のトランジット車両への乗換を含む。従って、計画システムは、公共交通機関を用いたトリップを容易に計画できる情報を人々に提案する機構を提供する。
【０００５】
典型的には、或るトリップのための指示を決定するために、これら従来の公共トランジット計画システムは、クエリ（問い合わせ）時間に、目的地に到達するための最適なルートを決定するためにトリップのスタートから行き先地点までの種々のルートを分析する。この手法は、２地点間に比較的少数の可能なルートしかないときには、利用可能なトランジットの選択肢の数が限られているため、有益である。しかし、公共交通機関インフラストラクチャーの拡張と、異なる交通システムの間の乗換能力（例えば、共通の駅での電車とバスの乗換）とのため、任意のスタート地及び目的地の間での多数の可能なルートが著しく増えている。従って、前記クエリ時間の間に目的地に到達するための最適ルートを計算するために必要な時間が劇的に増加しており、それにより、結果を得るためにユーザが待たなければならない時間が増加する。
【発明の概要】
【０００６】
公共トランジット旅行（travel:トラベル）計画システム及び方法は、公共トランジット（transit:交通機関、輸送、通行）を使ったジャーニー（journey:旅行）又はトリップ（trip:旅行）のためのクエリ（問い合わせ）に応じて、クエリ時間より前に、最適な公共トランジットのルートを決定するために、前処理されたトランジット情報を使用するように構成される。最適な公共トランジットのルートは、或るトリップのための時間とその他要素に関連する最良のルートであり、これは所与の出発地点から目的地点に到達するために公共交通機関及び／又は徒歩のみを使うものである。公共トランジット旅行計画システムは、クエリ時間より前に、任意の２つのトランジット駅の間の最適な乗換パターンを決定するためのトランジット情報（基本的な公共トランジットのスケジュールを表す情報）を処理する。より具体的には、乗換パターンは、目的地に到着するためになされるべき１以上のトランジット駅でのトランジット車両の乗換のシークエンスを表す。クエリ時間より前に、最適な公共トランジットのルートを決定するためトランジット情報を前処理することにより、クエリ時間の間の、或る公共トランジットルート用のユーザクエリを遂行するための計算量が極小となる。一般に、システムは前クエリ計算及び後クエリ計算を実行する。
【０００７】
クエリ時間より前に、システムは、種々のトランジット機関から受信したトランジット情報を既知のトランジット駅間の最適公共交通機関乗換パターンを計算する。記憶された各トランジットトリップは、起点位置と目的位置を含むトランジット情報により表される。トランジット駅におけるトランジット車両の１以上の停車スケジュール（すなわちルート）は、各記憶されたトリップから検索される。トランジットグラフは、各記憶されたトリップのルートを、弧によって連結された一連のノードとして表すものとして生成される。トランジットグラフ内の各ノードは、トランジット駅で実行される１つのイベントであって、そのトリップに関連するトランジット車両のイベントを表す。イベントの一例は、トランジット駅に到着する又はトランジット駅を出発するトランジット車両である。トランジットグラフ内に表された各トランジット駅のペア毎の最適乗換パターンは、乗換の数、旅の時間及び／又はその他要素の点から、最良の乗換ルートを表すものとなるように計算される。前述の通り、最適乗換パターンは、グラフ内の駅ペアの間のトランジット駅での１以上の乗換を表している。トランジット駅のペア毎の各最適乗換パターンは、クエリ時間における後の使用のために、記憶される。
【０００８】
クエリが受信されたら、システムは、前記クエリに含まれる所与のスタート地点と目的地点の間の公共トランジットルートを決定するために記憶された最適乗換パターンを使う。前記クエリを受信した後、システムは、スタート地点近在の駅を表す起点駅リストを生成するために、出発地点のラジアル距離内のトランジット駅を決定する。システムは、同様に、目的位置近在の駅を表す目標駅リストを生成するために、目的位置のラジアル距離内のトランジット駅を決定する。起点駅リストからの起点駅と目的駅リストからの目的駅とを示すトランジット駅の賢明な組み合わせのペア毎に、記憶された乗換パターンが検索され、その乗換パターンは起点駅と目的駅の間の中間駅でのトランジット車両の乗換を表す。クエリ時間より前に乗換パターンが既に計算されているので、システムはただ乗換パターンを検索しさえすればよい。システムは、そして、検索された乗換パターンに基づいて、起点駅から目的駅までの最適ルートを少なくとも１つ決定する。そして、最適ルートは、クエリを提示したユーザのクライアント装置に伝送される。
【０００９】
この概要及び以下の詳細な説明に記載された特徴及び利点は包括的なものではない。多くの付加的な特徴及び利点が、本願の図面、明細書及び特許請求の範囲を閲覧する当業者にとって明らかになるだろう。
【図面の簡単な説明】
【００１０】
【図１】一実施形態に従う、コンピュータ処理環境の概念的ブロック図。
【００１１】
【図２】一実施形態に従う、クエリ時間より先の、公共交通機関情報の前計算処理のフローチャート。
【００１２】
【図３】一実施形態に従う、トランジットグラフを生成する処理のフローチャート。
【００１３】
【図４】一実施形態に従う、トランジットグラフの一例を説明する図。
【００１４】
【図５Ａ】一実施形態に従う、グローバル駅を決定する処理のフローチャート。
【図５Ｂ】一実施形態に従う、グローバル駅を決定する処理のフローチャート。
【００１５】
【図６】一実施形態に従う、直通接続を決定する処理のフローチャート。
【００１６】
【図７】一実施形態に従う、直通接続トリップの一例を示す図。
【００１７】
【図８】一実施形態に従う、グローバル駅を使わない乗換パターンを計算する処理のフローチャート。
【００１８】
【図９】一実施形態に従う、グローバル駅を含む乗換パターンを計算する処理のフローチャート。
【００１９】
【図１０Ａ】一実施形態に従う、グローバル駅を用いたヒューリスティック乗換パターンを計算する処理のフローチャート。
【図１０Ｂ】一実施形態に従う、グローバル駅を用いたヒューリスティック乗換パターンを計算する処理のフローチャート。
【図１０Ｃ】一実施形態に従う、グローバル駅を用いたヒューリスティック乗換パターンを計算する処理のフローチャート。
【図１０Ｄ】一実施形態に従う、グローバル駅を用いたヒューリスティック乗換パターンを計算する処理のフローチャート。
【図１０Ｅ】一実施形態に従う、グローバル駅を用いたヒューリスティック乗換パターンを計算する処理のフローチャート。
【図１０Ｆ】一実施形態に従う、グローバル駅を用いたヒューリスティック乗換パターンを計算する処理のフローチャート。
【００２０】
【図１１】一実施形態に従う、乗換パターンを圧縮する処理のフローチャート。
【００２１】
【図１２】一実施形態に従う、ユーザクエリを遂行するためにクエリ時間に実行される乗換パターンを圧縮する処理のフローチャート。
【００２２】
【図１３】一実施形態に従う、起点位置及び目標位置に近在の駅を決定する処理のフローチャート。
【００２３】
【図１４】一実施形態に従う、クエリグラフを生成する処理のフローチャート。
【００２４】
【図１５】一実施形態に従う、クエリグラフの一例を示す図。
【００２５】
【図１６】一実施形態に従う、クエリグラフを拡張する処理のフローチャート。
【００２６】
【図１７】一実施形態に従う、拡張されたクエリグラフの一例を示す図。
【００２７】
【図１８】一実施形態に従う、拡張されたクエリグラフから最適なトリップを決定する処理のフローチャート。
【００２８】
【図１９】一実施形態に従う、最適なトリップを含むユーザインタフェースの一例を示す図。
【発明を実施するための形態】
【００２９】
これら図面は、本発明の種々の実施形態を説明するためにのみ描かれている。当業者は、以下の議論から、ここに開示された発明の本質から逸脱することなく、ここで説明された構成及び方法とは別の実施形態を採用できることが容易に理解できる。
システム概要
【００３０】
公共トランジット旅行（travel）計画システム及び方法は、ジャーニー（journey:旅行）のための最適公共トランジットルートを決定するために、クエリ時間に先立って、トランジット情報の広範な前処理を用いるように構成されている。最適公共トランジットルートは、時間及び／又は、その他の要素に関して最良の、出発地点から行き先地点に到達するために使用されるルートである。最適公共トランジットルートは、公共交通機関のみを使った（複数の異なる種類の公共交通機関が１つのルート内で使用されうる）、また、徒歩も含みうる、出発地点から行き先地点までの指示を備える。ルートは、この旅程にどのトランジット駅が使用されるかを表しており、また、目的地に到達するために必要とされる１以上のトランジット車両への任意の乗換（異なる種類の輸送（トランスポート）車両の間の乗換を含む）も表している。
【００３１】
トランジット旅行計画システムは、例えばバス路線や鉄道路線など公共交通機関を提供するトランジット機関からトランジット情報を受信する。トランジット情報は、１以上の形式の交通機関を用いる、種々の場所の間のトリップ（trip:旅行、移動）を表す。トランジット情報は公共トランジットのトリップのスケジュール情報を表しており、そのスケジュール情報は、当該トリップに関連する公共トランジット車両が駅に到着及び／又は駅から出発する時間のリストを表している。トランジット旅行計画システムは、クエリ時間に先行して、任意の２つのトランジット駅間のルートを表す最適乗換パターンを決定するために、トランジット情報を処理する。乗換パターンは、各旅の中で、どこでトランジット車両の乗換がなされるかを表している。従って、トランジット旅行計画システムは、何れの所与の駅のペアについても、可能な限りでの最良のルートを決定できる。
【００３２】
最適乗換目標を決定するために、トランジット旅行計画システムは、トランジットグラフ及びそれに関するトランジットテーブルであって、トランジットグラフの情報をテーブル形式で表すものを、生成する。トランジットグラフは、トランジット機関からの、例えば１週間又は１ヶ月など或る日数窓分のトランジット情報により指定される可能なトリップを表している。一般的に、各既知のトリップ毎に、トランジットグラフは、有方向の弧により連結された一連のノードを備えており、各ノードは、例えば特定の時間の公共トランジット車両の到着又は出発等の、駅でのイベントを表している。ノードのペアは、ペアにおける公共トランジット車両の移動を表す有方向の弧により連結される。
【００３３】
トランジット旅行計画システムは、トランジットグラフ内のトリップを表すために、第１の駅（起点ノード）から始まり第２の駅（目的ノード）に終わるトリップのトランジット情報を検索する。トランジット情報は、トランジット駅での公共トランジット車両についての、実際の時間及び位置（例えばスケジュール）の情報を備える。トランジット旅行計画システムは、そのトリップに関連するトランジット情報に基づいてトランジットグラフを作成する。トランジット旅行計画システムは、各トランジット車両の駅への到着及び／又は駅からの出発毎に、トランジットグラフに、特定駅の特定時間のイベントを表すノードを挿入する。
【００３４】
トランジット旅行計画システムは、トリップのルートを表す有方向の弧を使って複数ノードを連結する。各弧は起点ノードから目標ノードに到達するまでのコストに関連付けられている。トランジット旅行計画システムは、各弧のコストを決定するために、そのトリップに関連するトランジット情報を使用する。トランジット旅行計画システムは、トランジット情報が受信されたトリップ毎に、トランジットグラフに表される日数窓内の１日毎のトランジットグラフが作成されるまで、上述の処理を繰り返す。
【００３５】
トランジット旅行計画システムは、トランジットグラフの作成の後、当該トランジットグラフに基づいて、一続きのトランジットテーブルを作る。トランジットテーブルは、トランジットグラフ内の各ノード及び弧、トランジットグラフ内の各トリップが有効なときの日数窓内の日数、及び、駅の地理的位置を表す情報を含む。トランジットテーブルは、基本的には、トランジットグラフを表すテーブルである。一実施形態において、トランジット情報から、トランジットグラフを作るのではなく、トランジットテーブルが生成される。
【００３６】
トランジットグラフ及びトランジットテーブルを用いて、トランジット旅行計画システムは、全ての直通接続トリップを決定する。直通接続トリップは、起点駅から目的駅まで乗り換え無しのトリップである。また、１以上の停止がトリップ中になされるが、目的駅に到達するために乗り換えを行う必要がないならば、起点駅から目的駅は直通接続である。更に、トランジットトラベルトラベルシステムは、トランジットグラフ中のどの駅がグローバル駅（global station:汎用駅）であるかを決定する。グローバル駅は、長い距離のトリップの間にトランジット車両の乗り換えが頻繁に行われる駅である。直通接続情報はテーブル形式で記憶されてよい。
【００３７】
トランジット旅行計画システムは、トランジットグラフと直通接続情報テーブルを用いて、任意の所与の起点駅から、最小のコストで、トランジットグラフ内の任意の目的駅（すなわち行き先）到達するためのルートを表す最適乗換パターンを決定する。一実施形態において、乗換パターンは、公共トランジットルートの途中で、ユーザが公共交通機関の車両から降り（すなわち下車する）て、別の公共交通機関の車両に乗る（すなわち乗り換える）種々の公共トランジット駅（ここでは単に「駅」という）における、乗換のシークエンスを表す。好ましくは、乗換パターンは、駅間のトラベル時間、待ち時間及びその他のコスト要素を考慮に入れるコスト関数に関して（コストの状態により）最適化される。一般に、旅の乗換パターンは、トランジット車両の乗換が行われる駅とともに起点及び目的駅を含む。例えば、起点駅Ａ，目的駅Ｆであり、駅Ｄ，Ｅで乗換が行われるとする。この例では、乗換パターンは、ＡＤＥＦである。一実施形態において、乗換パターンは、乗り換える駅のための、時刻に論及することなく、駅のシークエンスを表しており、それゆえ、パターンは、単に具体的時刻で予め計算されたトリップではなく、複数の異なるスタート時間に関して具体例を挙げて示すことができるパターンとなる。
【００３８】
一般に、トランジット旅行計画システムは、最適乗換ルートを決定するために種々の方法論を使用する。方法論は、大域駅の概念を使用してもよいし、しなくても良く、或いは、乗換パターンを決定するためにヒューリスティックアプローチを使用してもよい。使用される方法論に関わらず、トランジット旅行計画システムは、所与の起点駅から目標駅に到達するためのコストに関して最良の経路を決定するために、例えばダイクストラアルゴリズムなどのグラフ探索アルゴリズムを用いる。従って、トランジット旅行計画システムは、トランジットグラフ内の起点駅と目的駅との全ての賢明な組み合わせのペアに対して、１以上の最適乗換パターンをもたらし、或いは、ルートが存在しなければ、乗換パターンを出さない。
【００３９】
乗換パターンは、クエリ処理時間における後の使用のために、記憶される。一実施形態において、各乗換パターンは、個別に且つ完全な形で記憶される。別の例として、トランジット旅行計画システムは、各乗換パターンを完全に記憶するのではなく、乗換パターンを圧縮する。乗換パターン内に含まれる情報は、基本的に、乗換パターン内に含まれる情報の冗長性のために、圧縮されうる小部分に分解されている。乗換パターンが圧縮されると、トランジット旅行計画システムは、圧縮された乗換パターンを記憶する。
【００４０】
クエリ時間において、記憶された乗換パターンは、起点位置から目的地までの指示のためのユーザクエリに応じた乗換ルートを生成するために使用される。一般に、ユーザは、或るジャーニーについて、すなわち、ユーザの現在位置又は興味のある位置から目的地までについての指示を要求する。起点位置及び目的地は、それぞれ、ユーザの現在位置及び興味の或る場所よりもむしろ、起点駅及び目的駅に関連付けられている。要求は、出発又は到着イベントに関連する日付及び／又は時間もまた含む。トランジット旅行計画システムは、そして、起点駅及び目的駅に近在する乗換駅を決定する。従って、起点及び目的に近い乗換駅は、異なる起点位置及び目的地のペアを形成するためにペア化されうる。乗換パターンは、予め計算されている記憶された乗換パターン情報の駅のペア毎に決定される。一般に、トランジット旅行計画システムは、駅のペアに関連する、記憶された乗換パターンを検索する。
【００４１】
乗換パターンを用いて、トランジット旅行計画システムはクエリグラフを生成する。クエリグラフは、起点位置から目的地までの最適ルートを決定するために使用される。クエリグラフは、クエリに関連するトランジット情報のみが含まれる。乗換パターン内の各駅は、クエリグラフ内のノードとして表され、ノードのペアはトランジットグラフと同様に有方向の弧により連結される。クエリグラフが生成されると、トランジット計画システムは、乗換パターン内の駅ペア間の複数の直通接続トリップを表す直通接続トランジット情報を用いて、クエリグラフ内の駅間の直通接続を決定する。
【００４２】
直通接続の決定は、検索クエリ内で受信された日付及び／又は時間により決定される。或る検索が或る日付の出発時間を含んでいる場合、指定された日付の、出発時間よりも後に出発する直通接続のみが検索される。同様に、到着時間が指定された場合は、その到着時間より前に到着する直通接続のみが決定される。直通接続トリップが決定されたら、トランジット旅行計画システムは、直通接続トリップのコストに基づく計算を行うことにより最適トリップを決定する。計算は、例えば時間又はトランジット車両の多様性など種々の要素に基づいて最適な複数のトリップをもたらす。そして、最適トリップは、検索クエリを遂行するために、ユーザに供給される。
【００４３】
従って、クエリ時間において、トランジット情報がトランジット旅行計画システムにより既に処理されているので、クエリを遂行するには非常に少ない時間しか要さない。例えば、カリフォルニア州サンノゼから、カリフォルニア州サンフランシスコへの最良の直通接続トリップを要求するクエリは、サンノゼからサンフランシスコへの記憶された直接接続を検索するために、前処理されたトランジット情報における相対的に短時間低価格の探索として処理できる。別の例として、クエリが、イギリスのドミニントンパーク乗り換えで、イタリアのムジェロから、オランダのアッセンへのトリップを要求する場合、クエリ時間よりも先に、最適乗換パターンが既に計算され記憶されているので、クエリは処理された乗換情報上の２つの直通接続クエリ経由で遂行できる。トランジット旅行計画システムは、ムジェロからオランダへの直通接続、及び、オランダからドミニントンパークへの直通接続の、２つの探索を実行する。従って、この発明のトランジット旅行計画システムは、公共トランジット指示のユーザクエリが遂行されるクエリ時間を最短で提供する。
【００４４】
図１を参照すると、この発明の一実施形態に従うコンピュータ処理環境の概念的ブロック図が示されている。トランジットサーバ１００（すなわち、トランジット旅行計画システム）は、特定の最適公共トランジットトリップを供給するために記憶された最適乗換パターンの広範な前処理アプローチを用いて、所与の日付及び時間の公共トランジットジャーニーのためのクエリに応じた公共トランジット（すなわち公共交通機関）指示をユーザに提供する。図１が一実施形態を示している一方で、この発明の全ての実施形態が、ここに記載される動作の実行及び種々のタイプのデータの記憶のために、コンピュータシステムの使用を必要とすることが理解されるべきである。以下の議論において、全ての動作、ステップ、データなどが、コンピュータシステム及びプログラミングロジックの組み合わせにより実装されるものであり、人の頭の中でのステップ又は実体化されない抽象的な概念を通じたどんな方法でも実行されないことは当然である。
【００４５】
一実施形態において、公共トランジットジャーニーは、公共交通機関のみを使用した、時間を特定された、起点（つまり出発）地点から目的（つまり行き先）地点へのルート又は経路からなる。種々の形式の公共交通機関は、バス、ライトレール（軽量軌道）、地下鉄、トロリー（市街電車）、通勤列車、フェリー又は飛行機などを含んでよい。当業者は、上記列挙したもの以外にも公共交通機関の別の形式があり、それを公共トランジットトリップ上の地点間を移動するための乗り物として使用できることを理解するだろう。以下では、簡略化のために、公共トランジットトリップを「トリップ」と称する。
【００４６】
前処理された最適乗換パターン情報を使用することにより、トランジットサーバ１００は、或るトリップのクエリを実行するためにクエリ時間に最小量の計算を実行する。これにより、ユーザの要求に対する最も迅速な応答時間が可能となる。特定時間におけるスタート地点から行き先地点へのトランジット指示のためのユーザのクエリに応じて、トランジットサーバ１００はユーザに、所望されたジャーニーのための１以上の最適公共トランジットルートを提供する。
【００４７】
一実施形態において、最適公共トランジットルートは、スタート地点近在の駅から目的地点近在の駅までのルートであって、コストに関して最適化されたルートである。トリップのコストは、一実施形態に従い目的地点近在の駅に到達するための時間及び／又は目的地点近在の駅に到達するために必要な乗換数に基づいて良い。
【００４８】
図１に示す通り、トランジットサーバ１００は、種々のモジュールを備える。周知の通り、「モジュール」との用語は、指定された機能を提供するために使用されるコンピューターロジックを指すものである。従って、モジュールは、汎用プロセッサを制御するためのハードウェア、ファームウェア、及び／又はソフトウェアにより実装され得る。一実施形態において、モジュールは、記憶装置に記憶され、メモリにロードされ、そして、プロセッサにより実行されたプログラムコードファイルであるか、又は、実体的なコンピュータ読み取り可能な記憶媒体（例えばＲＡＭ、ハードディスクもしくは光学的又は磁気的ディスク）に記憶されたコンピュータプログラム製品（例えばコンピュータにより実行可能な命令群）として提供され得る。更に、当業者たちは、図１に示したトランジットサーバ１００の別の実施形態が、ここに記載したのとは異なる及び／又は別のモジュールを持ち得ること、そして、その機能性が異なる方法でモジュールに分配され得ることを理解するだろう。
【００４９】
一実施形態において、トランジットサーバ１００は、クライアント１３１とネットワーク１３７経由で通信しており、このネットワーク１３７は、典型的にはインターネットであるが、次の例示に制限されないがＬＡＮ（ローカルエリアネットワーク）、ＭＡＮ（メトロポリタンエリアネットワー）、ＷＡＮ（ワイドエリアネットワーク）、携帯機器、有線又は無線ネットワーク、プライベートネットワーク又はヴァーチャルプライベートネットワークの任意の組み合わせを含んで良い。単一のクライアント１３１のみが示されているが、膨大な数（例えば数百万）のクライアントがサポートされ、いかなる時でもトランジットサーバ１００と通信できる。クライアント１３１は、或るトリップ向けの指示のためのトランジットサーバ１００へのクエリを供給するために、例えばモジラ又はインターネットエクスプローラなどのブラウザ１３３を実行する。クライアント１３１は、種々の異なるコンピューティング装置を含む。クライアント装置１３１の例は、パーソンバルコンピュータ、情報端末、携帯電話、移動電話、スマートフォン又はラップトップコンピュータなどである。当業者にとって明白な通り、この発明は上述に列挙した装置に限定されない。
【００５０】
一実施形態において、トランジットサーバ１００は、フロントエンドインターフェース１０１、トランジット情報インタフェース１２９、事前計算モジュール１０３、クエリ解決モジュール１１５、ルート情報データベース１２５、及び、トランジット情報データベース１２７を備える。フロントエンドインターフェース１０１はクライアント１３１からトランジットクエリを受信する。一実施形態において、クライアント１３１は、或るジャーニーについてのクエリをトランジットサーバ１００に送信する。クエリは、フロントエンドインターフェース１０１により受信されて、クエリを遂行するために、クエリ解決モジュール１１５と通信される。
【００５１】
トランジット情報インタフェース１２９は、例えば航空路、バス路線、或いは、その他任意の公共交通機関トリップを提供する公共トランジット機関など、複数の異なる公共トランジット機関から公共トランジットシステムのトランジットスケジュールに関するトランジット情報を受信する。一実施形態において、トランジットサーバ１００と通信している各トランジット機関は、例えば、http://code.google.com/transit/spec/transit_feed_specification.htmlに記載されたグーグルトランジットフィードスペシフィケーション（ＧＴＦＳ）（グーグルは登録商標）などの指定された形式に従うトランジット情報を供給する。ＧＴＦＳ形式のトランジット情報を受信することにより、トランジットサーバ１００は、異なるトランジット機関から均一のデータ形式で情報を受信できるようになる。一実施形態において、トランジット情報は、トランジット車両が運行する暦日付を表す当該トリップのための公共交通機関スケジュールと、該トリップの途中で停止する駅を現す駅情報（例えば住所）を含む。例えば、トリップにかかる金銭上のコスト、異なるトランジット駅での停止時間など、トリップのその他の属性が、トランジット情報に含まれていてもよい。トリップのためのトランジット情報が受信されたら、トランジット情報インタフェース１２９は、その情報をトランジット情報データベース１２７に記憶する。実際には、トランジット情報データベース１２７は、複数の異なるトランジット機関からのトランジット情報を記憶する。例えば、典型的な都市圏においては、トランジット情報データベース１２７は、公共バスシステムからのバススケジュール情報、地方通勤列車、ライトレール及び長距離列車のための列車スケジュール情報、地下鉄システムのための地下鉄スケジュールなどを記憶する。
【００５２】
一実施形態において、事前計算モジュール１０３は、クエリ時間に先行して、トランジット情報に関する事前計算処理を実行する。事前計算モジュール１０３は、トランジット情報データベース１２７内で示された任意の２駅間の全最適ルートの乗換パターンのセットを決定するために、トランジット情報データベース１２７に記憶されたトランジット情報を用いる。事前計算モジュール１０３は、また、トランジット情報を用いて、どの駅が別の駅から１以上の乗り換えをすることなしに直接到達できるかを決定する。これらの駅は、直通接続される、と呼ばれるものである。事前計算モジュール１０３は、ルート情報データベース１２５内の乗換パターンのセットと直通接続情報を記憶する。
【００５３】
クエリ解決モジュール１１５は、特定時間におけるスタート地点から目的地点までの指示のためのユーザクエリを遂行するために、最適トリップルートを決定する。クエリ解決モジュール１１５は、最適トリップを決定するために、事前計算処理モジュール１０３０により供給された前処理された最適乗換パターン及び直通接続を用いる。一般的には、クエリ時間において、クエリ解決モジュール１１５は、クエリを遂行するために、ルート情報データベース１２５からクエリに関連するスタート地点及び目的地点に関連付けられたいくつかの乗換パターンを検索すること、及び、最適トリップを決定するために該乗換パターンから具体例を挙げて（インスタンスを作成して）各トリップを評価することにより、縮減された計算のセットを実行する。特定のクエリに関連する乗換パターンの数が少ないので、乗換パターンの総数には依存せずに、スタート及び目的地点に関連付けられた乗換パターンのみを評価すればよく、最悪の場合のクエリ処理時間でも、概して、とても早い。
【００５４】
図１に示す通り、事前計算モジュール１０３は、トランジットグラフモジュール１０５、グローバル駅選択モジュール１０７、乗換パターン計算モジュール１０９、乗換パターン圧縮モジュール１１１、及び、直通接続モジュール１１３を備える。当業者は、事前計算モジュール１０３がこの発明の別の実施形態においては他のモジュールを含んでよいことを理解するだろう。次に図２を参照すると、事前計算モジュール１０３の事前計算処理の一実施形態は、以下の複数の機能的ステージを備える。
【００５５】
２００：トランジットグラフ及びトランジットテーブルを生成する。
【００５６】
２０１：グローバル駅を選択する。
【００５７】
２０３：直通接続トリップを決定する。
【００５８】
２０５：乗換パターンを計算する。
【００５９】
２０７：乗換パターンを圧縮する。
【００６０】
事前計算処理の各機能的ステージは以下に詳しく説明される。
１．トランジットグラフ及びトランジットテーブルの生成
【００６１】
事前計算処理の第１ステージにおいて、トランジットグラフモジュール１０５はトランジットグラフ及びそれに関連するトランジットテーブルを生成する（ステップ２００）。トランジットグラフは、トランジット情報データベース１２７に記憶された、例えば１週間や１ヶ月など所与の期間で可能なトリップの全ての表現である。一般に、トリップとは、乗換無しで特定の時間に種々の駅で１つのトランジット車両により行われる停車を表す。言い換えれば、トリップとは、所与の時刻に乗換無しで一連の複数の停車（又は停車無し）を行う１つのトランジット車両である。一実施形態において、ジャーニーは、起点駅から目的駅へ移動するために要する１以上のトリップを表す。すなわち、起点駅から目的駅へのジャーニーは、目的駅に到達するために別のトランジット車両への乗換を要する場合、一連の複数トリップとなるだろう。従って、ジャーニーは、目的駅に到達するために１以上のトランジット車両の使用を含むものとなる。トランジットグラフを生成することにより、トランジットグラフモジュール１０５は、所与の機関における異なる公共トランジット機関によるトリップの広範なネットワークを作成できる。トランジットグラフの構造は、以下で更に詳しく説明する。
【００６２】
一般に、トランジットグラフは、既知のトリップ毎に、そのトリップを表現するために、弧によって連結された一連のノードを備える。トリップ内の各ノードは、特定時間における或るトランジット駅での公共トリップ車両によるイベントを表す。有方向の弧は第１の駅を表す１つのノード（起点ノード）を第２の駅を表す１つのノード（目的ノード）に連結するものであり、公共トランジット車両が第１の駅から第２の駅へ移動し、且つ、第２の駅で停車する。例えば、カリフォルニア州マウンテンヴュー（Mountain View,CA）駅からカリフォルニア州サンフランシスコ（San Francisco,CA）駅へのカルトレイン（Cal Train）経由でのジャーニーはカリフォルニア州パロアルト（Palo Alto,CA）在の駅での１つの停止を含む。従って、トランジットグラフは、パロアルト（Palo Alto）駅への到着イベントに有方向の弧により連結されたマウンテンヴュー（Mountain View）駅でのイベントを表すノードを含み、パロアルト（Palo Alto）駅への到着イベントが更にサンフランシスコ（San Francisco）駅を表すノードに有方向の弧により連結される。
【００６３】
次に図３を参照すると、トランジットグラフモジュール１０５により実行されるトランジットグラフを生成するための処理のフローチャートの一実施形態が示されている。説明の便宜上、トランジットグラフの生成は、トランジットグラフによって表現された期間内の１つのトリップを参照して、説明される。一実施形態において、後述する通り、トランジットグラフ内の特定の弧は、その弧を生成したトリップに関するトリップ情報に関連付けられている。この情報は、時間窓内で関連付けられた旅が有効な日々を表す。従って、ここに示されたトランジットグラフモジュール１０５によって実行される１つのトリップのための処理は、全ての既知のトリップの情報を含むトランジットグラフ生成するために、既知のトリップ毎に繰り返される。従ってトランジットグラフモジュール１０５は、ここに示される教示を用いて、トランジット情報データベース１２７内に記憶された公共トランジット情報に表されていたのと同様に新しい期間内で可能な全てのトリップを表すように、該新しい期間のためにトランジットグラフを更新することもできる。
【００６４】
先ず、トランジットグラフモジュール１０５は、起点駅を出発し目的駅で終わるトリップのトランジット情報を検索する（ステップ３００）。一実施形態において、トランジットグラフモジュール１０５は、トランジット情報データベース１２７から、或るトリップに関するトリップ情報を検索して、当該トリップをトランジットグラフ内の他のトリップと識別するためにトリップ識別子（ＩＤ）を割り当てる。前述の通り、或るトリップのトリップ情報は、そのトリップの操業日スケジュールと、当該トリップ中に停車する時刻と駅の位置を表す駅情報を含む。言い換えれば、トランジットグラフモジュール１０５は、起点駅から目的駅までのトリップのためのルートを決定する。このルートは該ルート中で出発及び到着イベントがなされ停車の予定がある駅を表す。
【００６５】
トランジットグラフモジュール１０５は、トランジット情報を用いて、トランジット情報に基づくトランジットグラフを作成（つまり生成）する（ステップ３０１）。すなわち、トランジットグラフモジュール１０５は、トランジット情報から、トリップのための所与の起点駅及び目的駅及び全ての中間駅を決定し、停車及び／又は乗り換えが出発及び目的駅の間でなされる。トランジットグラフモジュール１０５は、また、各駅に関するスケジュール情報を決定する。この情報はいつ公共トランジット車両が駅に到着及び駅から出発するかを表す。
【００６６】
車両の各駅への到着及び／又は各駅からの出発毎に、トランジットグラフモジュール１０５は、それぞれ到着イベントと出発イベントを表すノードを２つまで、それぞれの時刻に、トランジットグラフに挿入する。従って、車両が駅に出発／到着しないときは、このトリップではこの駅で出発イベント又は到着イベントが行われないので、このトリップのためには、この駅にノードが生成されない。トランジット情報からトランジットグラフ内のノードが生成されると、各ノードは、いずれかの駅の特定時間におけるトランジット車両に関連付けられる。一実施形態において、トランジットグラフ内のノードは、駅ノード又は車中（機内）ノードのどちらでもあり得る。駅ノードは、トリップをなすためにユーザが乗車（つまり入場）できる駅の車両を表す。対照的に、車中ノードは、ノードに関連付けられた駅に位置されたユーザが現在乗っている公共トランジット車両を表す。トランジットグラフ中のノードは、一実施形態に従い、トリップのルートを示す互いに経由する弧に連結される。一般に、駅で乗車されるトランジット車両を表す乗車弧、人がジャーニーを完遂するためにトランジット車両に乗る別の駅まで歩かなければならない場合の最適徒歩を含む駅で降車されるトランジット車両を表す降車弧、人がトランジット駅で待つことを表す待機弧、及び、トリップの２つの停車の間で車両に乗車したままでいることを表すトランジット弧の４種類の弧がある。
【００６７】
ここで、弧は、駅Ａ及び駅Ｂの乗車及び駅ノードに関連して説明される。下付き文字“Ｏ”は、乗車ノードを表し、下付き文字“Ｓ”は駅ノードを表す。また、記号“→（矢印）”は２ノード間の弧を表す。以下は、駅間で行われるトランジットイベントを表す説明である。
１．Ａ_s→Ｂ_oは、駅Ａでのトランジット車両の乗車及び、駅Ａと駅Ｂとの間での停車無しの駅Ｂへの移動に対応する。
２．Ａ_o→Ｂ_sは、駅Ａでの車両の降車及び、駅Ｂへの徒歩移動に対応する。
３．Ａ_o→Ａ_sは、駅Ａでの車両の降車及び、同じ駅Ａでの待機に対応する。
４．Ａ_o→Ｂ_oは、駅Ａでトランジット車両に乗車すること、及び、少なくとも駅Ｂに到着するまで同じ車両に乗車したままでいることに対応する。
５．Ａ_s→Ａ_sは、駅Ａでの待機及びその時点で駅Ａを出発するトランジット車両に乗車しないことに対応する。
【００６８】
上述した遠い、トランジットグラフモジュール１０５は、各トリップのトランジット情報を、そのトリップの間に行われるイベントを決定するために、分析する。イベントに基づいて、トランジットグラフモジュール１０５は、対応するノード（駅又は乗車のいずれも）をトランジットグラフ内に配置して、ノードを弧で連結する。ノードのペアを連結する弧の種類は、連結されるノードが駅ノード又は乗車ノードのいずれであるかに基づく。例えば、トランジット情報が駅Ａでトランジット車両に乗車して駅Ｂまで乗換無しで移動することを表すものとすると、トランジットグラフモジュール１０５は、トランジットグラフ内に駅Ａに関連付けられた駅ノードを含め、且つ、トランジットグラフ内に駅Ｂに関連付けられた乗車ノードを含める。従って、それらノードを連結する弧は乗車弧となる。別の例では、乗車ノードが駅ノードに連結されたとすると、それらノードを連結する弧は降車弧である。
【００６９】
待機弧を表すために、トランジットグラフには時間の概念が表現される。ここで図４を参照すると、トランジットグラフの一部が示されている。この図において、トランジットグラフ４００は、Ｙ軸及びＸ軸に関して組織されたノードを示す。トランジットグラフのＹ軸は時間を表し、Ｘ軸は駅を表す。ここで、Ｘ及びＹ軸はトランジットグラフ内の時間の使用を説明するために便利なように説明されているのであり、ルート情報データベース１２５に記憶されたトランジットグラフの現実の実施においては、Ｘ又はＹ軸を含まず、また、グラフのノードも図４に示すような空間的な方法で配置されるのではないことは、理解される。
【００７０】
この図において、Ｙ軸は１日の時間表現である。トランジットグラフ内の時間の概念を説明するために、Ｘ軸に表された駅毎に、トランジットグラフモジュール１０５は、トランジットグラフに、Ｙ軸に沿って配列されるように描かれた一連のノードを追加する。駅に関連付けられた一連の各ノードは、そのノードに関連付けられた特定の時刻に駅で行われるトランジットイベントを表す。
【００７１】
トランジットグラフに示す通り、駅Ｓ₁は、異なる時間間隔の一連のノードを含む。“Ｓ”が付されたノードは駅ノードであり、“Ｏ”が付されたノードは乗車ノードである。所与の駅に関連付けられた各駅ノードは、特定の時刻にその駅で行われる何らかのイベントに関連付けられている。一実施形態において、全ての駅の駅ノードは、その特定の駅で待つ人を表すために、時間に基づいて順次リンクされている。例えば、トランジットグラフにおいて、Ｓ₁の駅ノード群は時間内で時順次に連結されており、Ｔ₁からＴ₄間の期間に駅Ｓ₁で人が待つという概念を表している。一実施形態において、トランジットグラフモジュール１０５は、所与の駅の各駅ノードを弧経由で次の出発イベントが行われる所与の駅に連結することにより、トランジットグラフに示された情報からトリップを推測する。
【００７２】
ここで、説明の簡易化のために、乗車弧、降車弧及び徒歩弧は時間に言及せずに、説明するものとする。トランジットグラフモジュール１０５が、駅Ｂ及びＣで途中停車するが乗換無しで、起点駅Ａから目的駅Ｄまでを表すランジット情報からのジャーニーを表現しているものと仮定する。なお、このシナリオでは、１つのトリップがジャーニーとみなされている。このジャーニーはこの表記法を使い、次のように表現される。
Ａ_s→Ｂ_o→Ｃ_o→Ｄ_o
【００７３】
上記の表記法につき、Ａ_s→Ｂ_oは、駅Ａで乗車され、駅Ｂに移動する車両を表す。Ｂ_o→Ｃ_oは、駅Ｂで乗車すること、そして駅Ｃに車両が到達するまで車両に居ることを表す。Ｃ_o→Ｄ_oは、Ｂ_o→Ｃ_oと同様なシナリオであるが、駅Ｄが目的駅を表し、乗車ノードが行き先への到着を表している。
【００７４】
トランジットグラフ内のジャーニーを表現するために、トランジットグラフモジュール１０５は、各到着／出発イベントをノードとして表現する。しかし、前述した通り、各ノードは、駅ノード又は乗車ノードのいずれにも対応する。トランジットグラフモジュール１０５は、トリップ内の駅ペアのためにどのノードを使用するかを、駅間で実行されるトランジットイベントに基づいて、決定する。前述した例を用いると、トランジット車両は駅Ａで乗車されて、トランジット車両は乗換無しで駅Ｂに移動するので、トランジットグラフモジュール１０５は、駅Ａでのイベントを駅ノードとして表し、駅Ｂでのイベントを乗車ノードとして表すだろう。次に、車両は駅Ｂから出発し、駅Ｃでのみ停車し乗換無しで、目的駅Ｄに移動するので、駅Ｃ，Ｄでのイベントは、トランジットグラフモジュール１０５により、乗車ノードとして表されるだろう。
【００７５】
別の例として、駅Ｃで乗換が行われることを除いて上述と同じジャーニーを仮定する。従って、駅Ｃで乗換が行われるので、このジャーニーには２つのトリップを要する。このジャーニーはトランジットグラフにおいて以下のように表されるだろう。
Ａ_s→Ｂ_o→Ｃ_o→Ｃ_s→Ｄ_o
【００７６】
上記の表記法を使うと、Ｂ_o→Ｃ_oは、駅Ｂから駅Ｃに車両が到着することを表す。Ｃ_o→Ｃ_sは、駅Ｃの車両が出発したこと、車両から離れ、駅Ｃから出発する別の車両に乗るために、駅Ｃで待つ人を表す。
【００７７】
前述の例を続けると、トランジットグラフ内において、駅Ａ及びＢでのイベントの表現は、上記説明により、駅Ａでのイベントについては駅ノードであり、駅Ｂでのイベントについては乗車ノードとなる。トランジットグラフモジュール１０５は、駅Ｃについて、２つのノード経由の駅Ｃのトランジットイベントを、駅ノード及び乗車ノードと表すだろう。トランジットグラフモジュール１０５は、駅Ｂの乗車ノードから、駅Ｃでの到着イベントとそのときにトランジット車両にいることを表すＣの乗車ノードに弧を連結する。トランジットグラフモジュール１０５は、駅Ｃの乗車ノードから、駅Ｃで車両から出てその駅で次の車両を待っていることを表すＣの駅ノードに別の弧を連結する。
【００７８】
更にトランジットグラフ内の時間の使用を説明するために、図４に戻る。先に述べた通り、この図では、Ｙ軸は１日の時間表現である。Ｘ軸に表された駅毎に、トランジットグラフモジュール１０５は、トランジットグラフに、Ｙ軸に沿って配列されるように描かれた一連のノードを追加する。駅に関連付けられた一連の各ノードは、そのノードに関連付けられた特定の時刻に駅で行われるトランジットイベントを表す。トランジットグラフモジュール１０５は、ノード毎に時刻情報を決定するために、記憶されたトランジット情報からのスケジューリング情報を使用する。従って、トランジットグラフモジュール１０５は、駅毎に、車両が駅に到着する／駅から出発する時間内の全ての事例のためのノードを含む。
【００７９】
一実施形態において、トランジットグラフ内のトリップのノードに連結される各弧は、トランジットグラフモジュール１０５により決定されるコストに関連付けられている。各コストは、弧に連結されている起点ノードから目的ノードに到達するための種々の要素に関する価格を表しており、それは金銭的コストを含むか又は含まない。トランジットグラフモジュール１０５は、各トリップに関連付けられた記憶されたトランジット情報を、弧のコストを決定するために、分析する。
【００８０】
一実施形態において、或る弧のためのコストは、多次元的コスト関数である。第１次元のコスト関数は、時間に基づく。トランジットグラフモジュール１０５は、目的ノードへの到達時間と起点ノードからの出発時間の間の時間の違いを決定するために、トランジット情報を分析する。目的ノードに関連付けられた駅に到達するための総時間は、コスト関数の第１次元として、目的ノードと起点ノードに連結された弧に関連付けられている。一実施形態において、時間長は秒単位で表されるが、別の実施形態においては別の時間表現も使用できる。
【００８１】
第２次元のコスト関数は、一実施形態に従えば、金銭的コスト、乗換総数、及び／又は徒歩のコストを含む種々の要素に基づく。これら種々の要素の集合は、総コストに含まれるペナルティになる。トランジットグラフモジュール１０５は、トリップの弧の脚に関連付けられたためのペナルティを決定する。
【００８２】
一例として、駅で乗換が行われたとき、弧のペナルティは増加し得る。ジャーニーの金銭的コストは、また、ペナルティに因数分解される。駅に到達するためのより大きい金銭的コストは、ジャーニーが１以上のトランジット車両の使用を含むときには、より高いペナルティとなる。また、トランジット車両を乗り換えるために或る駅から別の駅まで歩く距離は、トリップのコストに因数分解される。ペナルティにおける異なる要素の重み付けは、トランジットサーバ１００のシステム管理者によって調整される。
【００８３】
トランジットグラフモジュール１０５は、トランジット情報データベース１２７の情報からのジャーニーを表すノードをトランジットグラフ内に生成するために、上記の処理を実行する。トランジットグラフモジュール１０５は、期間内で有効な記憶されたジャーニー毎に、トランジットグラフがトランジットグラフ内に表された全てのトリップを表すまで、処理を繰り返す。
【００８４】
一実施形態において、日毎に新しいトランジットグラフを作成するのではなく、トランジットグラフの駅毎に、トランジットグラフモジュール１０５は、その日にその駅で行われる出発イベント毎に駅ノードを作成する。トランジットグラフモジュール１０５は、待機弧経由で駅ノードを連結する。その日の最後の駅ノードは、その日の最初の駅ノードに戻る待機弧４０９に割り当てられる。これは、前日の夜から、その翌日にその駅で行なわれる次の出発イベントまで、駅で待機することを表す。トランジットグラフ内の乗車ノードに関しては、各乗車ノードは、１以上のトリップに関連付けられており、従って、本質上、所与の期間内の日数内で１以上のトリップが有効なとき（つまり操業しているとき）を表す情報を含む。
【００８５】
図４において、トランジットグラフ４００は、一実施例に従う、時間と公共トランジット駅の関数である。トランジットグラフ４００は、グラフ内で弧４０５によって連結されたノードとして、種々の時刻Ｔ₁〜Ｔ₈で種々の駅Ｓ₁及びＳ₆の間で公共トランジット車両により行われるイベント（つまり到着又は出発）を表す。トランジット情報を用いて、トランジットグラフモジュール１０５は、３つのジャーニーを含むトランジットグラフ４００を作成している。トランジットグラフ４００内の各弧は、起点ノードが表す駅から目的ノードが表す駅まで移動するためのコスト４０７を含む。
【００８６】
例えば、トランジットグラフ４００に描かれた１つのジャーニーは、時刻Ｔ₄における駅Ｓ₁から時刻Ｔ₈における駅Ｓ₆間でのトリップである。トランジットグラフ４００に示す通り、時刻Ｔ₄における駅Ｓ₁のノードは、ノード内に位置する“Ｓ”により記されたとおり駅ノードである。時刻Ｔ₅における駅Ｓ₃のノードは、ノード内に位置する“Ｏ”により記されたとおり乗車ノードである。同様なノード指定が、トランジットグラフ４００内の残りのノードにも使用される。
【００８７】
ジャーニーによって示されたルートは、時刻Ｔ₄に駅Ｓ₁から出発し、続いて時刻Ｔ₅に駅Ｓ₃で停車し、時刻Ｔ₆に駅Ｓ₄での別の停車により後続される車両を表す。時刻Ｔ₆の駅Ｓ₄から、時刻Ｔ₈の駅Ｓ₆にて、車両は行き先に到達する。なお、ジャーニーは、また、時刻Ｔ₄から時刻Ｔ₅の間に駅Ｓ₂を通過する車両を表しているが、車両が駅Ｓ₂に止まらないので時刻Ｔ₄から時刻Ｔ₅の間の駅Ｓ₂を表すノードは作成されない。
【００８８】
また、トランジットグラフ４００は、また、時刻Ｔ₁における駅Ｓ₂から時刻Ｔ₈における駅Ｓ₆へのジャーニーを含み、同様に、時刻Ｔ₁における駅Ｓ₃から時刻Ｔ₈における駅Ｓ₆へのジャーニーも含む。なお、時刻Ｔ₁に駅Ｓ₂から出発する車両は時刻Ｔ₄に駅Ｓ₁から出発する車両と同じ時刻に駅Ｓ₃に到着する。一実施形態において、時刻Ｔ₅における駅Ｓ₃の単一イベントは、両方のイベントを表す。
【００８９】
更に、トランジットグラフ４００は、車両が駅に到着する／駅から出発する時間内のすべての事を示す一連の駅Ｓ₁のノード４０３を例示している。また、時刻Ｔ₄だけは、駅Ｓ₁から出発する車両を描いており、説明の便宜上、駅Ｓ₁のノードからの出発を描く弧が省略されていることを理解されたい。駅Ｓ₁の最後の駅ノードを表すノードは、駅Ｓ₁が運営している日の先頭の時刻を表す駅ノードに戻るようになっている。
【００９０】
図３に戻ると、トランジットグラフが作成されると、トランジットグラフモジュール１０５は、そのトランジットグラフに基づいて一連のトランジットテーブルを作成する。一実施形態において、トランジットテーブルは、トランジットグラフの弧とノードに関連付けられた情報を表す。トランジットグラフは、本質的には、トランジットグラフ内の各ノードと弧についての情報及びトランジットグラフに関するその他の情報を表すトランジットグラフのテーブル表現である。トランジットグラフモジュール１０５は、トランジットグラフ内の情報を、種々のトランジットテーブルに記憶する。トランジットテーブルは更なる詳細を後述される。なお、一実施形態において、トランジットグラフを生成し、それに続いてそのトランジットグラフからトランジットテーブルを作成するのではなく、トランジットテーブルはトランジット情報から直接作成される。
【００９１】
トランジットグラフモジュール１０５は、トランジット情報に基づいて、トリップマスクのセットを作成する（ステップ３０３）。一実施形態において、トリップマスクのセットは、全ての可能なトリップをリスト表示し且つ何時そのトリップが有効かを示すテーブルとして表される。テーブルの各行はトリップのトリップマスクを表す。各トリップマスクは、車両がトリップマスク内に示された特定のトリップをする期間内の日付を表す。一実施形態において、トリップマスク内の期間は６０日である。別の実施形態では別の期間を使用できる。トリップマスクの一例は以下の通りである。
【表１】

【００９２】
テーブル内の各行は特定のトリップに関連付けられている。各欄は選択された期間内の日又は日付を表す。一実施形態において、トリップマスク内の所与の日の“１”はその日にトリップが有効であることを示し、“０”はその日にトリップが有効でないことを示す。別の実施形態では、トリップが有効か無効かを示すために別の表記方法が使用されうる。トリップマスクが作成されたら、トランジットグラフモジュール１０５はそのトリップマスクをトランジット情報データベース１２７に記憶する。
【００９３】
上記の例において、トリップマスクはトリップＴ₁、Ｔ₂からＴ_Nをリスト表示している。残りの欄は、特定の開始日（例えば２００９年６月８日）から末日（例えば２００９年８月８日）の間の日付を表す。各日付に対して、トリップ毎にその日にトリップが有効か又は無効化を示す“１”又は“０”のどちらかがリスト表示される。例えば、２００９年６月８日には、トリップＴ₂のみが有効であり、トリップマスクにリスト表示された他の全てのトリップは使用できない。次の日はＴ₁とＴ_Nだけが使用できる。
【００９４】
トリップマスクが作成されると、トランジットグラフモジュール１０５は、ノードテーブルを作成する（ステップ３０５）。一実施形態において、トランジットグラフモジュール１０５は、トランジットグラフに基づいてノードテーブルを作成する。ノードテーブルは、各ノードの識別子（ＩＤ）と各ノードに関連付けられた駅の駅ＩＤを指定する。ノードテーブルは、更に、各ノードに関連するノード種類を指定する。ノード種類は、そのノードが駅ノードか又は乗車ノードかを示す。ノードテーブルは、また、各ノードに関連付けられたイベントの時刻も含む。イベントは、ノード種類に応じて到着又は出発イベントになるだろう。最後に、ノードテーブルは、何時ノードが有効化を示すためにトリップマスクを指すトリップＩＤを含む。なお、一実施形態において、駅ノードは特定のトリップの一部でない駅で単に待っている人に関連付けられるので、乗車ノードのみが、トリップＩＤに関連付けられていてもよい。ノードテーブルが作成されたら、トランジットグラフモジュール１０５は、ノードテーブルをトランジット情報データベース１２７に記憶する。下記は、ノードテーブルの一例を示す。
【表２】

【００９５】
示されたテーブルは、５つの欄：ノードＩＤ、駅ＩＤ、イベント時刻、ノード種類及びトリップＩＤ、を持つ。ノードＩＤの欄は、トランジットグラフの全てのノードＮ₁からＮ_Nのリスト表示である。各ノードは駅ＩＤ、イベント時刻、ノード種類及びトリップＩＤに対応付けられている。例えば、ノードＮ₁は、駅Ａに関連付けられている。テーブルは、ノードＮ₁が８時００分のイベント時刻を持つ乗車ノードであることを示す。従って、その乗車ノードは、車両から降車する人無しで駅Ａに到着するトランジット車両、又は、駅Ａに到着し駅Ａで車両から人が降りるトランジット車両を表し得る。ノードテーブルは、また、乗車ノードが、そのノードに関連付けられた日付が有効であることを示すトリップマスクに戻るトリップＩＤＴ８に関連付けられていることを示す。別の例として、ノードＮ₃は、駅Ｃに関連付けられており、駅ノードである。ノードＮ₃に関連付けられたイベントは、２時００分に行われる。ノードが駅ノードなので、２時００分に行われるイベントは、駅Ｃでの待機イベント又は乗車イベントである。前述の通り、駅ノードはトリップＩＤへ戻すことができない。
【００９６】
ノードテーブルが作成された後、トランジットグラフモジュール１０５は、弧テーブルを作成する（ステップ３０７）。弧テーブルは、トランジットグラフ内の各弧に関連する情報を指定する。一実施形態において、弧テーブルは、各弧のペナルティとともに各弧の起点ノードＩＤと目的ノードＩＤを指定する。弧自身は明白には識別されない。むしろ、弧は、弧によって連結された特定のノードに基づいて、推測される。トランジットグラフ内の各ノードは特有のノードＩＤに関連づけられているので、弧は、或る弧によって連結されているノードのノードＩＤに基づいて決定され得る。弧テーブルは、また、起点及び目的ノードにより推測された各弧に関連づけられたペナルティを表す。弧テーブルが作成されると、トランジットグラフモジュール１０５は、弧テーブルをトランジット情報データベース１２７に記憶する。下記は、弧テーブルの一例を示す。
【表３】

【００９７】
テーブルは、起点ノードＩＤ、目的ノードＩＤ及びペナルティの、３つの欄を含む。起点ノードＩＤと目的ノードＩＤの欄は、どのノードが弧によって連結されているかを推測するトランジットグラフ内の全ての起点及び目的ノードのペアをリスト表示する。例えば、（Ｎ₁，Ｎ₂₄）の起点ノードＩＤと目的ノードＩＤは、これら２つのノードが弧によって連結されていることを示す。この例では、その弧は、１００のペナルティを持つ。
【００９８】
弧テーブルが作成された後、トランジットグラフモジュール１０５は、駅位置テーブルを作成する（ステップ３０９）。駅位置テーブルは、トランジットグラフ内の各駅の地理的位置を示す。一実施形態において、各駅の地理的位置は駅の緯度及び経度座標により表される。別の例として、例えば駅の住所など、地理的位置を表す別の方法が使用され得る。駅位置テーブルが作成されると、トランジットグラフモジュール１０５は、駅位置テーブルをトランジット情報データベース１２７に記憶する。下記は、駅位置テーブルの一例を示す。
【表４】

【００９９】
上記の例では、駅位置テーブルは、トランジットグラフ内の全ての駅をリスト表示する駅ノードＩＤ欄を含む。駅位置テーブルは、また、各駅ＩＤの地理的位置を緯度及び経度座標でリスト表示する地理的位置欄を含む。例えば、駅Ｄは、カリフォルニア州サンノゼ地域に対応する北緯３７度３７分、西経‐１２１度．９２分の地理的位置を持つ。
【０１００】
一実施形態において、トランジットグラフモジュール１０５は、前述の弧テーブルの作成を援助するために、近在駅テーブルを作成する（ステップ３１１）。具体的には、トランジットグラフモジュール１０５は、乗換弧を作成するために近在駅テーブルを用いる。前述した通り、乗換弧（人がその人が到着した駅で乗り換えるか、又は、別の駅へ歩くかに応じて、徒歩を含むか若しくは含まない）は、各乗車ノードから、その駅自身を含め人が到着した駅に近在の全ての駅で最も早く到達するイベントへ、作成される。乗換弧をメモリに記憶するよりもむしろ、近在駅テーブルが記憶され、乗換弧の要求があり次第、乗換弧が作成される。テーブル内の駅毎に、トランジットグラフモジュール１０５は、記憶されたトランジット情報を用いて、所与の駅からのラジアル距離内にある全ての駅を決定する。ラジアル距離内の駅は、或る駅の“近在”又は“ローカル”とみなされる。一実施形態において、ラジアル距離は２マイルであってよく、また、別の実施形態ではその他の距離であってよい。従って、システム管理者によって決定されるトランジットサーバ１００のラジアル距離に応じて、所与の駅は近在の駅を持たないかもしれない。近在駅テーブルが作成されると、トランジットグラフモジュール１０５は、近在駅テーブルをトランジット情報データベース１２７に記憶する。下記は、近在駅テーブルの一例を示す。
【表５】

【０１０１】
テーブルは、駅ＩＤと近在駅ＩＤのリストとの、２つの欄を含む。駅ＩＤ毎に、近在駅ＩＤのリストは、“近在”駅とみなされる駅と、駅から近在駅に乗り換えるのに必要な最小の時間長を示している。すなわち、近在駅ＩＤのリストは、指定されたラジアル距離内にあるこれらの駅と、近在駅に到達するのに必要な時間を示す。例えば、駅Ａは駅Ｄ，駅Ｑ，駅Ｒ、駅Ｚ及び駅Ｙに近い。駅Ａから駅Ｄに乗り換えるには、例えば最小時間６０秒が乗換実施のために必要である。対照的に、駅Ｃは近在駅が何もない。更に、一実施形態においては、或る駅はそれ自身の近在駅ＩＤのリストに含まれてよいことに留意されたい。これは、単一の駅において或るトランジット車両から別のトランジット車両に乗り換えるために必要となる最小時間長（すなわち安全バッファ）を示す。例えば、駅Ａにとって、その近在駅ＩＤのリストは、駅Ａで乗換を完遂するには最小時間６０秒を要することを示す。なお、図示の例では駅Ｂのための近在駅ＩＤのリストに示すように、その駅で乗換が行われならば、全ての駅がそれら自身の近在駅ＩＤのリストに含まれるのではないことに留意されたな。
２．グローバル駅選択
【０１０２】
図２に戻ると、事前計算処理の第２ステージ（随意）において、グローバル駅（グローバル駅）選択（ＧＧＳ）モジュール１０７はグローバル駅を選択（つまり決定）する（ステップ２０１）。一実施形態において、グローバル駅は、長い接続（コネクション）の間に、乗換が行われるであろう駅である。すなわち、グローバル駅は、長距離に広がるトリップにおいて乗換が頻繁に行われる駅である。ＧＧＳモジュール１０７は、或る駅で乗り換えるトランジットルートの数に基づいて、又は、時間独立ヒューリスティックに基づいて、グローバル駅を選択する。各実施例は更に詳しく後述されるだろう。
【０１０３】
次に図５Ａを参照すると、或る駅で乗り換えるルートの数に基づいてグローバル駅を計算するためにＧＧＳモジュール１０７によって実行される方法のフローチャートが示されている。ＧＧＳモジュール１０７は、トランジットグラフを入力として受信する（ステップ５０５）。ＧＧＳモジュール１０７は、トランジットグラフから、各駅で行われる乗換の数を決定する（ステップ５００）。ＧＧＳモジュール１０７は、トランジットグラフにおいて各駅で車両乗換が行われる回数を決定するために、そのトランジットグラフを分析する。ＧＧＳモジュール１０７は、各駅で行われる乗換の数に基づいてグローバル駅を識別する（ステップ５０１）。一実施形態において、グローバル駅とみなされるために或る駅で行われるべき乗換の最小数を指定するように、乗換閾値が適用される。ＧＧＳモジュール１０７は、乗換閾値に従い各駅をフィルタし、残った駅がグローバル駅とみなされる（ステップ５０３）。
【０１０４】
次に、図５Ｂを参照すると、時間独立ヒューリスティックに基づいてグローバル駅を決定するためのＧＧＳモジュール１０７の処理が示されている。ＧＧＳモジュール１０７は、トランジットグラフを入力として受信する（ステップ５０５）。ＧＧＳモジュール１０７は、次に、トランジットグラフ内の各駅の駅ノードを、単一のノードにグループ化する（ステップ５０７）。前述の通り、各駅は車両が駅に到着又は駅から出発する種々の時間を表す１以上のノードを持つ。これらノードの、部分集合は駅ノードである。ＧＧＳモジュール１０７は、各駅の駅ノードを、その駅のための駅ノードグループを形成するようにグループ化する。例えば、図４に示す駅Ｓ₁の８つのノードは、それらが全て駅ノードとすると、８つのノードからなる駅ノードグループを形成するように、グループ化されるだろう。
【０１０５】
ＧＧＳモジュール１０７は、それから、乗車ノードをグループ化する（ステップ５０９）。一実施形態において、ＧＧＳモジュール１０７は、乗車ノードグループを形成するために、トランジットグラフ内で、同じ先行駅のシークエンスを持ち乗車ノードによって表される車両間で追い越しがない乗車ノードをグループ化する。すなわち、ＧＧＳモジュール１０７は、その一日のうちの類似するトリップをグループ化する。一実施形態において、類似するトリップは、互いに追い越さず、トリップの間は同じ駅のシークエンスを辿るトリップである。ＧＧＳモジュール１０７は、トリップのグループ毎に、そのグループの各トリップの第１の乗車ノードを、或る乗車ノードグループにグループ化する。なお、乗車ノードグループは、そのグループが類似するトリップからできているので、１つの駅の乗車ノード群を表すことに留意されたい。そして、ＧＧＳモジュール１０７は、そのグループの各トリップの第２の乗車ノードを、第２の乗車ノードグループにグループ化する。そして、全ての乗車ノードがグループ化されるまで、これを繰り返す。
【０１０６】
ＧＧＳモジュール１０７がトランジットグラフの駅ノードと乗車ノードをグループ化したら、ＧＧＳモジュール１０７は、グループ間の弧を追加する（ステップ５１１）。一実施形態において、ＧＧＳモジュール１０７は、トランジットグラフのグループ化されていない表現（リプリゼンテーション）を分析し、トランジットグラフ内の異なる駅ノードグループ又は乗車ノードグループに属する２つのノード間に少なくとも１つの弧が存在するかどうかを決定する。ＧＧＳモジュール１０７は、トランジットグラフ内の２つのノード間に弧が存在していた場合、異なるグループ間に弧を追加する。
【０１０７】
ＧＧＳモジュール１０７は、トランジットグラフ内のグループ化された表現（リプリゼンテーション）における弧毎に、コストを決定する（ステップ５１３）。一実施形態において、２グループ間の弧毎に、ＧＧＳモジュール１０７は、トランジットグラフから、トランジットグラフ内の弧経由で連結された各ノードのペアであって、ペアになっている各ノードが連結されている２つの異なるグループに属するものを決定する。本質的に、ＧＧＳモジュール１０７は、トランジットグラフから、互いに連結されたグループのペアに属し、且つ、連結されたノードのペアのセットを作成する。ＧＧＳモジュール１０７は、そのセットから、どのノードのペアが最小コストに関連づけられているかを決定し、そして、グループ化されたトランジットグラフ内の２つのグループ間の弧に最小コストを割り当てる（ステップ５１５）。
【０１０８】
一実施形態において、トランジットグラフのグループ化された表現は、トランジットグラフ内で時間を持っていたノードが時間相を持たないノードグループにフラット化されているので、時間独立（時間に依存しない）とされる。トランジットグラフのグループ化された表現における各ノードグループが時間を横断して類似するノードを表すので、結果として得たトランジットグラフは、ノードグループがもう特定の時間に関連付けられていないため、時間独立（時間に依存しない）とみなされる。
【０１０９】
次に、ＧＧＳモジュール１０７は、コストの点での最短経路を決定するために、毎回ランダムな駅グループをソースとして取り（すなち、この駅ノードグループに属する全ての結ばれたノードが最短経路探索のソースとなる）ダイクストラのアルゴリズムを繰り返し適用する（ステップ５１７）。なお、ダイクストラのアルゴリズムの動作は、周知技術であるため、ここでは説明しない。一実施形態において、ＧＧＳモジュール１０７は、時間独立なグラフ内の駅ノードグループの複数のランダムなサンプルに、ダイクストラのアルゴリズムを適用する。ダイクストラのアルゴリズムの適用により、アルゴリズムの各適用毎に最短経路ツリーを得ることができる。
【０１１０】
ＧＧＳモジュール１０７は、ダイクストラのアルゴリズムにより得たツリー内の各駅ノードグループのためのスコアを決定する（ステップ５１９）。一実施形態において、ＧＧＳモジュール１０７は、スコア付けされる所与の駅ノードグループより下流のサブツリー内の駅ノードグループの数に基づいて、当該所与の駅ノードグループにスコアを割り当てる。ＧＧＳモジュール１０７は、ダイクストラのアルゴリズムにより得た、異なるツリーからの各駅ノードグループのスコアを合計することにより、各駅ノードグループのための総スコアを生成する。
【０１１１】
各駅ノードグループのための総スコアが生成されたら、ＧＧＳモジュール１０７は、総スコアに基づいてグローバル駅を選択する（ステップ５２１）。一実施形態において、ＧＧＳモジュール１０７は、小さい割合の駅ノードグループしか選択しない。ＧＧＳモジュール１０７は、総スコアに基づいて降順にグローバル駅を配列して、グローバル駅の上から１パーセントを選択し、グローバル駅のセットを得る（ステップ５０３）。
３.直通接続の事前計算
【０１１２】
図２に戻ると、事前計算処理の第３ステージにおいて、直通接続モジュール１１３は、トランジットグラフを用いて、直通接続情報を事前計算する（ステップ２０３）。一実施形態において、直通接続トリップは、起点駅から目的駅まで乗換の無いトリップである。また、トリップは起点駅から目的駅までの間に中間駅での停車も含んでいてもよく、中間駅で乗換が行われないならばそのトリップは直通接続トリップとみなされる。トランジットグラフに関して、直通接続トリップは、トランジットグラフ内の駅ノードから出発して、トランジットグラフ内の目的駅に関連付けられた乗車ノードに到着する、乗換無しのトリップである。
【０１１３】
次に、図６を参照すると、直通接続モジュール１１３によって実行される直通接続を計算するための方法のフローチャートである。一実施形態において、直通接続モジュール１１３は、トランジットグラフを入力としてとる（ステップ５０５）。直通接続モジュール１１３は、トランジットグラフを決定（すなわち捜し出す）して（ステップ６０１）、トリップを識別する。すなわち、直通接続モジュール１１３は、その日の所与の時刻に複数駅のセットを通過する単一のトランジット車両を現すトランジットグラフ内の経路を識別する。
【０１１４】
直通接続モジュール１１３は、それから、トランジット路線を決定する（ステップ６０３）。一実施形態において、トランジット路線は、起点及び目的駅を連結する複数トリップのセットであり、路線内の各トリップが同じ順番又はシークエンスで同じ駅を通過する。すなわち、トランジット路線内の各トリップは、同じ起点駅と、同じ目的駅と、該起点駅と該目的駅の間に位置し、そのトリップに関連付けられたトランジット車両が停車する、同じ中間駅のセットとを持つ。一実施形態において、トランジット路線の各トリップは、また、同じペナルティを持っている。従って、２つトリップが同じ起点駅と同じ目的駅とを持ち、同じ駅を同じ順番で通過するとしても、その２つのトリップのペナルティが異なっていれば、それらトリップは同じトランジット路線には含まれないだろう。なお、中間駅での停車がなければ、トランジット路線の或るトリップは、起点駅と目的駅のみを含むだろう。トランジット路線内のトリップは、起点駅、出発駅、及び／又は、トリップ中に停車がなされる中間駅からの出発／到着の時刻によって互いに区別される。
【０１１５】
一実施形態において、トランジット路線内のトリップ毎に、直通接続モジュール１１３は、トリップ内の各駅にポイント性質を関連付ける。各駅は、トリップ中のポイントと、そのポイントで行われるイベントを表すポイント性質とを考慮される。直通接続モジュール１１３は、各駅ノードにポイント性質“乗車ポイント”を割り当て、各乗車ノードにポイント性質“降車ポイント”を割り当てる。直通接続モジュール１１３は、各ノードにポイント指標（インデックス）を割り当てて、下記の２つの特質に基づき各ノードに関連付けられたポイントを使用して、標準的順番でトリップを整列する。２つの特質は次の通り
１．トリップ中のより高い指標を持つポイントからより低い指標を持つポイントへの経路がない。
２．より低い指標を持つ乗車ポイントからより高い指標を持つポイントへの経路が常にある。
【０１１６】
一実施形態において、直通接続モジュール１１３は、また、各ノードに累積ペナルティを割り当てる。累積ペナルティは、トリップにおける乗車ポイントと降車ポイントの間の総ペナルティを表す。累積ペナルティは、ノード間のペナルティを決定するためのノードペアに連結された弧の分析の必要性を回避するために、各ノードに追加される。むしろ、直通接続モジュール１１３は、降車ポイントの累積ペナルティから乗車ポイントの累積ペナルティを、引き算することにより、累積ペナルティを決定できる。直通接続モジュール１１３が上述した情報をトリップに含ませたら、そのトリップ情報が記憶される。したがって、直通接続トリップに関連付けられたトランジットグラフ内の各ノードは、一意のトリップに対応付けられるだろう。各トリップは、ノードに関連付けられたトランジット路線を示す路線ＩＤ、トランジット路線からのトリップを示すトリップＩＤ、及び、ポイント指標を含む。
【０１１７】
次に図７を参照すると、起点駅を示す駅ノード（例えばＡ_S）と、弧７０１により連結された複数の乗車ノード（例えばＢ_O，Ｄ_O、Ｅ_O及びＦ_O）を含むトランジット路線の表現の一例が示されている。各ノードは、直通接続モジュール１１３によって割り当てられたポイント指標７０３に関連付けられている。図７は、また、各弧に割り当てられたペナルティも描いており、そのペナルティは当該弧により連結されたノード間のペナルティを表す。最適トリップについての情報を含むトランジット路線が以下に示されている。トランジット路線は、直通接続データベース１２５における直通接続トリップの記憶構造を描いている。
【表６】

【０１１８】
トランジットグラフから全てのトランジット路線が決定されたら、直通接続モジュール１１３は、トランジット路線を分析する（ステップ６０５）。直通接続モジュール１１３は、トランジット路線から直通接続テーブルを決定する。直通接続テーブルは、整列された駅のペアと、そのペア内の起点駅での乗車とそのペア内の目的駅での降車とを示すペア毎の路線のセットとのリストである。一般に、直通接続モジュール１１３は、トランジットグラフ内の可能な駅のペアのための直通接続を決定する（ステップ６０７）。下記は直通接続テーブルの一例である。
【表７】

【０１１９】
上記直通接続テーブルの例は、駅ペアのリストと、ペア内の起点駅から目的駅までのトリップを含むトランジット路線を示す路線ＩＤの各ペア毎のリストを描いている。例えば、駅ペア（Ａ，Ｂ）は、Ｌ₁、Ｌ₄、Ｌ₅及びＬ₉の路線ＩＤに関連付けられている。これは、これら路線ＩＤに関連付けられたトランジット路線が、人に駅Ａで乗車して駅Ｂで降車させるトリップを持つことを示す。別の例では、駅ペア（Ｂ，Ａ）は、人が駅Ｂで乗車して駅Ａで降車できるトリップを持たないものとみなされる。
４．乗換パターンの計算
【０１２０】
図２に戻ると、事前計算処理の第４のステージにおいて、乗換パターン計算（ＴＰＣ）モジュール１０９は最適乗換パターンを計算する（ステップ２０５）。前述の通り、ジャーニーの乗換パターンは、そのジャーニーの行き先に到達するために行う必要がある１以上の駅でのトランジット車両乗換のシークエンスを表す。最適乗換パターンは、最小のコストで起点駅から目的駅に到達するためのルートを表す。なお、最適乗換パターンは、何らかの特定の時間において且つ何らかの距離コストの点で最適な、ジャーニーの乗換パターンである。従って、異なる乗換パターンに従う、異なるジャーニーは、その日の別の時刻で、且つ、最適化がトランジットの時間長、徒歩の量、乗換の数、又はその他の距離に基づくかどうかに応じて、最適でありうる。一実施形態において、ＴＰＣモジュール１０９は、３つの異なる実施形態に従い乗換パターンを計算する。それは、グローバル駅無しの正確な乗換パターンの計算、グローバル駅有りの正確な乗換パターンの計算、及び、グローバル駅有りのヒューリスティック乗換パターンの計算である。各実施形態はここで説明される。
Ａ．グローバル駅無しの正確な乗換パターンの計算
【０１２１】
一実施形態において、ＴＰＣモジュール１０９は、グローバル駅を利用せずに乗換パターンを計算する。図８を参照すると、この実施例に従い、最適乗換パターンを計算する（ステップ８１１）ためにＴＰＣモジュール１０９によって実行される方法のフローチャートが示されている。一実施形態において、図８に示す方法は、各駅毎に、他の全ての駅に対して、各駅のペアの最適乗換パターンを決定するために、実行される。説明の便宜上、方法は、出発（つまり起点）駅及び目的駅に関して説明される。
【０１２２】
一実施形態において、ＴＰＣモジュール１０９は、入力としてトランジットグラフを取る（ステップ５０５）。ＴＰＣモジュール１０９は、トランジットグラフ内の起点駅の駅ノード全てを初期化する（ステップ８０１）。すなわち、ＴＰＣモジュール１０９は、起点駅の駅ノード全てにコスト０というラベルを割り当てる。従って、各駅ノードは、そのラベルにリスト表示された時間長０、及び、ペナルティ０を持つ。前述の通り、各駅の駅ノードは、駅からの異なる出発時刻を表す。
【０１２３】
駅ノードが初期化されたら、ＴＰＣモジュール１０９は、出発地点から目的駅の各ノードまでの各駅ノードからパレート‐ダイクストラ検索を実行する（ステップ８０３）。一実施形態において、パレート‐ダイクストラ検索は、ＴＰＣモジュール１０９が、ダイクストラアルゴリズムに典型的な単一のコストの代わりに、例えば「ペナルティ、時間長」などの多次元ラベルをノードにタグ付けすることを除き、ダイクストラ検索と同様なグラフの探索である。パレート‐ダイクストラ検索は、全てのノード用にパレート最適ラベルのセットを保持する。ダイクストラでは１つの最適コストでけがあったが、パレート‐ダイクストラ検索において多次元ラベルを持つことは、多数の潜在的な最適ラベルをもたらす。例えば、パレート‐ダイクストラ検索により得たラベルセットを検討すると、そのセットは｛（ペナルティ＝３、時間長＝１０）、（ペナルティ＝５、時間長＝７）及び（ペナルティ＝８、時間長＝２）｝を含む。この例では、いずれのラベルも多次元コストの点で他よりも厳密により良いものではないため、全てのラベルが最適とみなされる。
【０１２４】
パレート‐ダイクストラ検索の結果として、ＴＰＣモジュール１０９は、各起点ノードから、目的駅の特定の目的ノードへの最適ルートを提供する。各ルートは、起点駅と目的駅の間で乗換が行われる種々の駅を含む。一実施形態において、ルート内の各ノードは、対応するラベルセットを持っており、そのラベルセットはペナルティと時間長に関するコストを特定する。ＴＰＣモジュール１０９は、トランジットグラフによって記述されたルート内の弧に関連付けられたコストに基づいて、ラベルセット内のラベルを割り当てる。
【０１２５】
ＴＰＣモジュール１０９は、駅毎に、支配的ラベルを決定する（ステップ８０５）。一実施形態において、パレート‐ダイクストラ検索が完了した後、トランジットグラフ内の各ノードは、最適ラベルのセットに関連付けられる。ＴＰＣモジュール１０９は、目的駅のラベルから、最適ラベルが決定された起点駅に後戻りすることにより、最適経路を決定する。
【０１２６】
一実施形態において、ＴＰＣモジュール１０９は、各乗車ノードのラベルセットを緩める（減ずる）。一実施形態によれば、ラベルセットの軽減は、ＴＰＣモジュール１０９が１つのラベルセットからパレート最適性を保っている別のラベルセットにラベルを伝播することを含む。すなわち、第１のラベルセットから第２のラベルセットにラベルを追加したとき、全てのコスト次元において他のラベルに支配されているラベルは、第２のラベルセットから取り除かれる（フィルタされる）。一実施形態において、ＴＰＣモジュール１０９は、以下の条件を満たすならば、経路１のコストペア（ｄ１，ｐ１）が経路２のコストペア（ｄ２，ｐ２）より支配的であることを決定する。
ｄ１≦ｄ２且つｐ１≦ｐ２
ＴＰＣモジュール１０９は、経路１の時間長が経路２の時間長よりも短いか又は等しく、且つ、経路１のペナルティが経路２のペナルティよりも小さいか又は等しい場合、経路１のコストペアが経路２のコストペアより支配的であることを決定する。言い換えれば、コストの全ての次元において経路１が経路２よりも良い場合、経路１は経路２より支配的である。例えば、経路１が３６００秒の時間長と１００のペナルティを持っている一方、経路２が５４００秒の時間長と２００のペナルティを持っている場合、経路１は時間長及びペナルティの両方に関して経路２より支配的である。従って、ラベルセットの軽減は、支配的なラベルを取り除くことにより、第２のラベルセットが数を増やさないようにする。むしろ、各ラベルセットが軽減を用いてラベルの数を減少される。軽減の後にラベルセット内に残るラベルは、支配的なラベルとみなされる。一実施形態において、２つのラベルが時間長とペナルティに関して等しい場合、より早い到着時刻のラベルが支配的となる。
【０１２７】
例えば、駅Ａの乗車ノードを検討する。ＴＰＣモジュール１０９は、ラベルセットを仮想的待機弧に沿って伝えることにより、駅Ａの各乗車ノードのラベルセットを軽減する。例えば、ＴＰＣモジュール１０９は、時刻“Ｔ”における駅Ａの或る乗車ノードの或るラベル（ペナルティ＝１００、時間長＝６００）を、同じ駅Ａの全ての乗車ノードに伝える。すなわち、時刻“Ｔ+ｄｔ”における駅Ａの別の乗車ノードは、ラベル（ペナルティ＝１００、時間長＝６００+ｄｔ）を受信する。ＴＰＣモジュール１０９は、それから、上述した支配的要素に基づいて、各乗車ノードのラベルセット内にて、他のラベルに支配されているラベルを取り除く。一実施形態において、駅ノードのラベルセットは、上述と同様の方法で、乗車ノードに軽減される。
【０１２８】
支配的ラベルが決定されたら、ＴＰＣモジュール１０９は、各乗車ノードに残っている各支配的ラベルから、検索が実行された起点ノードへ最適経路を後戻りすることにより、最適乗換パターンを計算する（ステップ８０７）。ＴＰＣモジュール１０９は、また、経路が決定されるのと同様に、各最適経路に対して乗換パターンを決定して良い。すなわち、ＴＰＣモジュール１０９は、各最適経路内に示されたノードを分析して、どのノードがトランジット車両乗換に関連付けられているかを決定する。各ノードが特定の駅に関連付けられているので、ＴＰＣモジュール１０９は、乗換が行われるノードに基づいて、経路から乗換パターンを抽出できる。
【０１２９】
最適経路から乗換パターンを決定することの一例は、以下の通りである。最適経路を返された駅Ａから駅Ｆまでのパレート‐ダイクストラ検索を検討する。返された最適経路の１つは、一連の駅ＡＢＤＥＦに関連付けられた一連のノードである。ＴＰＣモジュール１０９は、経路内の各ノードに関連付けられた情報を分析して、駅Ｂ及びＥで行われる乗換を決定する。従って、この例では、ＴＰＣモジュール１０９は、この経路から乗換パターンＡＢＥＦを抽出する。
【０１３０】
乗換パターンが決定されたら、ＴＰＣモジュール１０９は、乗換パターンを後の使用のために記憶する（ステップ８０９）。一実施形態において、支配的ラベルは、各駅の乗換パターンの計算が完了したとき、捨てられる。
Ｂ．グローバル駅ありの正確な乗換パターンの計算
【０１３１】
一実施形態において、ＴＰＣモジュール１０９は、グローバル駅選択モジュール１０７により決定されたグローバル駅を使って乗換パターンを計算する。トランジットグラフから最適乗換パターンを決定するために、ＴＰＣモジュール１０９は、グローバル駅選択モジュール１０７により決定されたグローバル駅のために、１つのグローバル駅検索を行う。一実施形態において、グローバル駅検索は、経路を決定すべきトランジットグラフ内のグローバル駅から、トランジットグラフ内の該グローバル駅から到達可能な他の全てのノードまでのパレート‐ダイクストラ検索である。すなわち、ＴＰＣモジュール１０９は、トランジットグラフ内のそれぞれ別の駅に到達するための最適路を決定するために、各グローバル駅から全グラフ探索を行う。一実施形態において、例えばトリップの時間長及びペナルティなど異なる抽出条件に基づく、グローバル駅からトランジットグラフ内の駅に到達するための最適路が１以上ある。
【０１３２】
次に図９を参照すると、このアプローチに従い、乗換パターンを決定するためにＴＰＣモジュール１０９が実行する方法が示されている。ＴＰＣモジュール１０９は、ルート情報データベース１２５から全てのグローバル駅を決定する（ステップ９００）。一般に、グローバル駅毎に、ＴＰＣモジュール１０９は、グローバル駅から、１つのグローバル駅検索を実行する（ステップ９０１）。つまり、ＴＰＣモジュール１０９は、トランジットグラフ内の、グローバル駅に到達しうる他の全てのノードへの最適経路を決定するために、各グローバル駅の全ノード（駅ノードと乗車ノード）から、トランジットグラフ内で１つのダイクストラ検索を実行する。或るグローバル検索において、グローバル駅の全ノードは、時間長及びペナルティの両次元において、コスト０に初期化される。
【０１３３】
トランジットグラフ内のグローバル駅からのグローバル検索の結果として返された最適経路毎に、ＴＰＣモジュール１０９は、返された経路からグローバル乗換パターンを決定する（ステップ９０３）。一実施形態において、グローバル乗換パターンは、グローバル検索の結果として得られる乗換パターンである。ＴＰＣモジュール１０９は、返された各経路において示されたノードを分析すること、及び、どのノードがトランジット車両乗換に関連付けられているかを決定することにより、グローバル乗換パターンを決定する。各ノードが特定の駅に関連付けられているので、ＴＰＣモジュール１０９は、グローバル駅無しの乗換パターン計算に関して上述した通り乗換が行われるノード経路から乗換パターンを抽出できる。
【０１３４】
グローバル乗換パターンが決定されたら、ＴＰＣモジュール１０９は、ローカル乗換パターンを決定するために、ローカル検索を実行する（ステップ９０５）。一実施形態において、ローカル検索は、抽出条件に基づく非グローバル駅（つまりローカル駅）のノードからの検索である。一実施形態において、抽出条件は、トランジットグラフ内のローカル駅の駅ノードから別の駅への最短経路を決定するために、トランジットグラフを探索するためのものであり、その最短経路は経路内のグローバル駅での乗換を示さない。すなわち、ＴＰＣモジュール１０９は、トランジットグラフ内のそれぞれ別の駅への最適経路を決定するために、各ローカル駅の駅ノードからの検索を実行する。
【０１３５】
ＴＰＣモジュール１０９は、そして、最適経路からローカル乗換パターンを決定する（ステップ９０７）。一般に、ローカル乗換パターンは、ローカル検索の結果として得られる乗換パターンである。ＴＰＣモジュール１０９は、各返された経路に示されたノードを分析して、どのノードがトランジット車両乗換に関連付けられているかを決定する。前述の通り、各ノードが特定の駅に関連付けられているので、ＴＰＣモジュール１０９は、乗換が行われるノードに基づいて、経路から乗換パターンを抽出できる。
【０１３６】
ＴＰＣモジュール１０９は、更に、乗換パターンが受動的部分を含むかどうかを決定するために、各抽出された乗換パターンを分析する。一実施形態において、乗換パターンの受動的部分とは、乗換パターン内のグローバル駅での乗換が後続する一連の駅である。すなわち、乗換パターンが、グローバル駅で行われた乗換を示している場合、乗換パターン内の残りの駅のシークエンスは、乗換パターンの受動的部分とみなされる。起点駅から始まり、乗換が行われるグローバル駅で終わる乗換パターンの部分は、乗換パターンの能動的部分とみなされる。一実施形態に従うと、乗換パターンの能動的部分は、グローバル駅を含む。一実施形態において、乗換パターンに含まれるグローバル駅は、ローカル検索がそこから実行されるローカル駅のアクセス駅とみなされる。アクセス駅は、本質的に、ローカル駅に関連付けられたグローバル駅であり、ローカル駅からのトランジット車両が、アクセス駅無しでは到達できない目的駅に到達できるようにするものである。従って、各ローカル駅は、ローカル乗換パターンの決定の結果として得られる１以上のアクセス駅を具備する。なお、ローカル乗換パターンは、受動的部分を持たなくてもよい。ローカル乗換パターン内のグローバル駅で乗換が行われない場合、又は、ローカル乗換パターン内の最後の駅がグローバル駅の場合、ローカル乗換パターンの全体が能動的とみなされる。
【０１３７】
ローカル乗換パターンが決定されたら、ＴＰＣモジュール１０９は、汎用乗換パターンとローカル乗換パターンを、ルート情報データベース１２５に記憶する（ステップ９０９）。一実施形態において、各ローカル乗換パターンの能動的部分のみが記憶される。
Ｃ．グローバル駅有りのヒューリスティック乗換パターン計算
【０１３８】
一実施形態において、ＴＰＣモジュール１０９は、種々のヒューリスティックアプローチに基づいて、グローバル駅選択モジュール１０７により決定されたグローバル駅を用いて、トランジットグラフの乗換パターンを計算する。一実施形態において、グローバル駅有りの乗換パターンを計算するために、ＴＰＣモジュール１０９により、下記のアプローチが使用される。
【０１３９】
ｉ．ペナルティにより軽減された時間長
【０１４０】
ｉｉ．多数の乗換後のローカル検索を停止する
【０１４１】
ｉｉｉ．グローバル駅の乗車でローカル検索を停止する
【０１４２】
ｉｖ．全ての最適トリップを説明するために複数の乗換パターンの部分集合を使用する
【０１４３】
ｖ．最初及び最後の徒歩を取り除く
【０１４４】
各アプローチは以下に詳しく説明される。
ｉ．ペナルティにより軽減された時間長
【０１４５】
次に図１０Ａを参照すると、経路のコストに基づいて乗換パターンを決定するためにＴＰＣモジュール１０９により行われる方法が示されている。以下の説明は、起点駅と目的駅に関してなされる。一実施形態において、起点駅又は目的駅のいずれかがグローバル駅である。一実施形態において、下記の処理は、トランジットグラフ内の全ての可能な起点ノード毎に、ＴＰＣモジュール１０９により繰り返される。それにより、ＴＰＣモジュール１０９は、トランジットグラフから起点駅毎の支配的経路を決定し、結果として起点駅毎に乗換パターンのセットを得る。
【０１４６】
まず、ＴＰＣモジュール１０９は、トランジットグラフ上で起点駅からパレート‐ダイクストラ検索を実行する（ステップ１００１）。起点駅のノード毎に、パレート‐ダイクストラ検索が実行され、その結果として可能な各目的駅のノードへの経路を得る。従って、ダイクストラ検索は、起点駅から各目的駅の複数の最適経路をもたらす。
【０１４７】
ダイクストラ検索の一部として、ＴＰＣモジュール１０９は、コストに基づくダイクストラ検索の結果として得た経路の中から、支配的経路を決定する（ステップ１００３）。ＴＰＣモジュール１０９は、どの経路が支配的かを決定するために、経路のコストペアの累積を分析する。一実施形態において、支配的経路は、検索結果として得た他の全ての経路のコストに比較して、時間長とペナルティに関してより少ないコストを持つ。
【０１４８】
一実施形態によれば、ＴＰＣモジュール１０９は、以下の条件を満たすならば、経路１のコストペア（ｄ１，ｐ１）が経路２のコストペア（ｄ２，ｐ２）より支配的であることを決定する。
第１条件．ｄ１≦ｄ２且つｐ１≦ｐ２、又は、
第２条件．ｄ１＜ｄ２且つｐ１≧ｐ２、並びに、［ｄ１+Ａ×（ｐ１−ｐ２）］≦ｄ２、ここでＡ＝８
【０１４９】
第１条件において、上述の通り、ＴＰＣモジュール１０９は、経路１の時間長が経路２の時間長よりも短いか又は等しい場合、経路１のコストペアが経路２のコストペアより支配的であることを決定する。加えて、経路１のコストペアが経路２のコストペアより支配的であるには、経路１のペナルティが、経路２のペナルティよりも小さいか又は等しくなければならない。
【０１５０】
ＴＰＣモジュール１０９が経路１の時間長は経路２の時間長よりも短いけれども、経路１のペナルティは経路２のペナルティよりも大きいと判定した場合、ＴＰＣモジュール１０９は、ルート１の時間長と、重さ要素Ａが乗算されるルート１とルート２のペナルティの差分と、の合計に基づく計算を実行する。上記の一実施形態ではＡ＝８と示されている。しかし、別の実施形態では、別の値が使用され得る。計算の結果が、ルート２の時間長よりも小さいか又は等しい場合、ＴＰＣモジュール１０９は、経路１が経路２より支配的であると決定する。一例として、経路１が３６００秒の時間長と５００ペナルティを持っている一方、経路２が４０００秒の時間長と１００のペナルティを持っているとする。この例では、経路１の時間長が経路２の時間長より小さいので第２条件が適用されるが、経路１のペナルティは経路２のペナルティよりも大きい。支配的経路を決定するために、第２条件の式が使用される。上記の式を使用すると、［３６００＋８×（５００−１００）］は４４００であり、経路２の時間長よりも小さいくも等しくもないため、経路１は経路２に対して支配的ではない。従って、この例の経路１は経路２に対して支配的でない。支配的経路が決定された、ＴＰＣモジュール１０９は支配的経路の乗換パターンを記憶する（ステップ１００５）。
【０１５１】
上記の処理がトランジットグラフ内の全ての可能な起点駅毎に繰り返されるので、ＴＰＣモジュール１０９は、記憶された最適乗換パターンのセットを結果として得る。
ｉｉ．多数の乗換後のローカル検索を停止する
【０１５２】
次に、図１０Ｂを参照すると、人口密集地域ではトリップのルートは一般に最小の乗換数でグローバル駅に到着し、田園地方では多数駅の中で乗換が行われる駅は少ししかないとするヒューリスティックに基づいて、グローバル駅への乗換パターンを決定するためにＴＰＣモジュール１０９により行われる方法が示されている。一実施形態において、このヒューリスティックは、２つのトランジット車両乗換以内でグローバル駅に到達しなければならない（つまりトリップの間に３つのトランジット車両が使用される）という条件下で、動作する。別の実施形態では、異なる乗換数が使用され得る。
【０１５３】
グローバル駅への乗換パターンを決定するために、ＴＰＣモジュール１０９は、トランジットグラフ内の所要の出発ノードからローカル検索を行う（ステップ１００７）。上述の通り、ローカル検索は、トランジットグラフ内の他の駅への最適経路を決定するための、ローカル駅の駅ノードからの検索である。ＴＰＣモジュール１０９は、出発ノードから開始してトランジットグラフ内の他のノードに広がるトランジットグラフ内の最短経路を捜し出す。ＴＰＣモジュール１０９は、その経路から、グローバル駅が、出発ノードから出発して２つのトランジット車両乗換以内で到達されているかどうかを、決定する（ステップ１００９）。具体的には、出発ノードから開始して、トランジットグラフ内のルートに沿って、各後続ノード毎に、ＴＰＣモジュール１０９は、乗換が行われるか、又は、ノードに関連付けられた駅がグローバル駅かを決定する。グローバル駅に到達するまえに多くとも２つの乗換が行われるならば、グローバル駅に至る駅の経路は乗換パターンとみされる。
【０１５４】
例えば、トランジットグラフ内のローカル駅Ａの出発ノードが経路に含まれており、経路に沿う第１グローバル駅が駅Ｇとする。駅Ａのノードは、ＡＢＣＤＥＦＧの経路を表す一連のノードに連結される。駅Ａから駅Ｇの間で乗換が行われないとする。駅Ａから開始して、ＴＰＣモジュール１０９は、経路を捜し出し、各後続駅がグローバル駅であるか、又は、その後続駅で乗換が行われるかどうかを決定する。この例では、駅Ａから駅Ｇの間で乗換が行われないので、ＴＰＣモジュール１０９は、駅Ｇまで到達したら経路をトラバースする（スキャンする）のを停止する。従って、経路ＡＢＣＤＦＦＧのための乗換パターンは、駅Ａ及びＣの間で乗換が行われないことを示すＡＧである。
【０１５５】
非グローバル駅で乗換が行われる場合、ＴＰＣモジュール１０９は、乗換の実行を捜し出し、且つ、経路内のグローパル駅又は非グローバル駅での第３の乗換に到達するまで処理を繰り返す。ＴＰＣモジュール１０９が２つの乗換以内でグローバル駅に到達したと決定した場合は、その経路に関連付けられた乗換パターンが決定される。ＴＰＣモジュール１０９が最大２つの乗換の後または３つ目の乗換でグローバル駅に到達していないと決定した場合は、分析中の経路は無視されて、ＰＣモジュール１０９は、別の非グローバル駅を対象として上記の処理を繰り返す。ＴＰＣモジュール１０９は、グローバル駅への乗換パターンのセットを決定するために、トランジットグラフ内の全ての非グローバル駅の各ノードに対して分析を行う。
【０１５６】
一例として、上記で用いたＡＢＣＤＥＦＧの経路において、駅Ｇがグローバル駅でありトランジット車両乗換が駅Ｃと駅Ｆで行われるものとする。駅Ａから開始して、ＴＰＣモジュール１０９は、各後続駅がグローバル駅であるか、又は、その後続駅で乗換が行われるかどうかを決定する。駅Ｃで乗換が行われるので、ＴＰＣモジュール１０９は乗換を追跡する。グローバル駅Ｇに到達する前に駅Ｆで２番目の乗換が行われるのみであるため、ＴＰＣモジュール１０９は、経路ＡＣＦＧを、駅Ａからグローバル駅Ｇまでの乗換パターンとみなす。
【０１５７】
次に、駅Ｂ、Ｃ及びＦで乗換が行われるとする。この例では、グローバル駅Ｇに到達する前に３つのトランジット車両の乗換が行われるので、ＴＰＣモジュール１０９は、第３番目の乗換に到達したら、汎用駅への経路を広げるのを停止する。一般に、３番目の乗換で経路の拡張を停止することにより、ＴＰＣモジュール１０９は、多くの経路を検討からはずし、且つ、最適経路の事前計算を実質的により速くできる。
【０１５８】
前述の処理が、トランジットグラフ内のローカル駅とグローバル駅の賢明な組み合わせのペアの全てに対して繰り返し行われるので、ＴＰＣモジュール１０９は、乗換パターンのセットを結果として得て、そして、それを記憶する。
ｉｉｉ．グローバル駅の乗車でローカル検索を停止する
【０１５９】
次に図１０Ｃを参照すると、ローカル駅からグローバル駅への乗換パターンを決定するためにＴＰＣモジュール１０９によって実行される方法が示されている。なお、説明の便宜上、以下の説明は、トランジットグラフ内の１つのノードからの乗換パターンの決定に関して記載している。当業者にとっては、以下の説明が、グローバル駅への乗換パターンを決定するために、トランジットグラフ内のローカル駅の各駅ノード毎に繰り返され得ることが明白である。
【０１６０】
一実施形態において、ＴＰＣモジュール１０９は、ローカル駅の所与の駅ノードからローカル検索を実行する（ステップ１０１１）。ＴＰＣモジュール１０９は、トランジットグラフ内の駅ノードから始まる経路を捜し出して、トランジットグラフ内の他のノードに広げる。ＴＰＣモジュール１０９は、その経路から、いつグローバル駅の乗車ノードが到達されるかを決定する（ステップ１０１３）。より具体的には、駅ノードから始まり、トランジットグラフ内の経路に沿う後続のノード毎に、ＴＰＣモジュール１０９は、トランジットグラフ内の後続のノードがグローバル駅に関連付けられた乗車ノードであるか決定する。グローバル駅の後続のノードに到達したら、ＴＰＣモジュール１０９は、グローバル駅の乗車ノードに至る経路の乗換パターン（駅ノードを含む）を決定する（ステップ１０１５）。一実施形態において、後述する通り、グローバル駅に停車しないジャーニーを説明するための縫い合わせ（スティッチング）が要求される。
【０１６１】
例えば、前述のように、駅Ｃ及びＤで乗り換えるローカル駅Ａからグローバル駅Ｇの経路ＡＢＣＤＥＦＧを検討する。経路内で駅Ｇに関連付けられたノードが乗車ノードと仮定する。ＴＰＣモジュール１０９は、グローバル駅に関連付けられた乗車ノードに到達するまで経路をたどる。従って、この場合、駅Ｇが経路内で到達されるグローバル駅の最初の乗車ノードであるため、経路ＡＣＤＧが乗換パターンとみなされる。駅Ａと駅Ｇの間で乗換が行われないならば、その経路の乗換パターンは、乗換が行われないことを示すＡＧになる。前述の通り、乗換パターンは、トリップの出発及び目的駅を含む。
【０１６２】
別の例として、駅Ｅもまたグローバル駅であり、経路内の駅Ｄに関連付けられたノードが乗車ノードと仮定する。この場合、ＴＰＣモジュール１０９は、グローバル駅の最初の乗車ノードに到達するまで、経路をたどる。この場合、駅Ｇの乗車ノードではなく、駅Ｄの乗車ノードがそれである。従って、ＡＣＤＥの乗換パターンが生成される。
【０１６３】
上述の処理がトランジットグラフ内のローカル駅とグローバル駅の賢明な組み合わせのペア毎に繰り返されるので、ＴＰＣモジュール１０９は、その結果として乗換パターンのセットを得て、それからそれを記憶する。
ｉｖ．全ての最適トリップを説明するために複数の乗換パターンの部分集合を使用する
【０１６４】
次に、図１０Ｄを参照すると、トランジットグラフ内の全ての駅から乗換パターンを決定するために、ＴＰＣモジュール１０９により実行される方法がしめされている。図１０Ｄに示されたアプローチが、起点駅からの目的駅へのトリップ数を減少するために使用される。一般に、下記のアプローチは、全ての乗換パターンのセットを目的駅への最適トリップに、目的駅への全ての最適トリップをカバーするのに十分な部分集合によって置き換えるために使用される。一実施形態において。トランジットグラフ内の全ての駅ペア毎に、駅間の乗換パターンを決定するために、以下の記述が繰り返される。
【０１６５】
一実施形態において、ＴＰＣモジュール１０９は、トランジットグラフ内の起点駅の各ノード（すなわち起点駅）から目的駅のノードへのローカル検索を実行する（ステップ１０１７）。その検索から、ＴＰＣモジュール１０９は、起点駅からの種々の出発時間における、起点駅から目的駅への最適経路のセットを、結果として得る。ＴＰＣモジュール１０９は、検索から返された最適経路毎に、起点駅から目的駅への乗換パターンを決定して（ステップ１０１９）、最適乗換パターンのセットを形成する。最適乗換パターンのセットは、特定の日における起点駅から目的駅への全ての可能なトリップをカバーするだろう。
【０１６６】
ＴＰＣモジュール１０９は、セット内の乗換パターンに含まれた冗長なトリップを決定する（ステップ１０２１）。すなわち、起点駅から目的駅へのトリップを表す乗換パターン毎に、ＴＰＣモジュール１０９は、同じ起点駅から目的駅への、他の乗換パターンを決定する。ＴＰＣモジュール１０９は、両方の乗換パターンを保持しておく必要性を除去するために、乗換パターンの１つが起点駅から目的駅へのトリップをカバーできるかどうかを決定する。一実施形態において、運行日毎に時刻Ｔ´の第２のトリップが存在するとき、１以上の乗換パターンは時刻Ｔのトリップをカバーしており、その第２のトリップは同じ乗換パターンを持つ決定されたセットからの乗換パターンを持ち、出発地点から第１のトリップよりも早く出発せず、且つ、第１のトリップのコストをわずか閾値よりも超えるコストを持つ。
【０１６７】
例えば、所与のトリップのためのシナリオを検討する。一日を通じてそのトリップのための乗換パターンＡＢＣを持つ多数の最適トリップがあるとする。それら最適トリップの中で、トリップは、駅Ａを２２時４０分に出発して駅Ｃに２３時２５分に到着し、２００のペナルティを持つものである。更に、乗換パターンＡＤＣの一度限りのトリップがある。その一度限りのトリップは、駅Ａを２２時３８分に出発して駅Ｃに２３時２２分に到着し、１８０のペナルティを持つ。たとえ一度限りのトリップが、２２時３８分に出発したいユーザにとってより良い結果であっても、一度限りのトリップは、乗換パターンＡＢＣに関連付けられたトリップへの支持から、却下される。というのも、乗換パターンＡＢＣに関連付けられたトリップは、後の時刻に同じ起点駅から出発するのであるから、却下されたトリップがいつ実行されるときはいつでも、実行されるトリップを提供するからである。更に、乗換パターンＡＢＣのトリップの最低のコスト（すなわち３分遅れの到着時刻で、２０の余分なペナルティ）は閾値より低い。
ｖ．最初及び最後の徒歩を取り除く
【０１６８】
一実施形態において、ＴＰＣモジュール１０９は、最適と思われるが、出発及び行き先地点に近在の複数の駅がトランジットサーバ１００によって検討されるクエリ時間の間は最適ではない駅間の経路を取り除くために、初期の及び徒歩ヒューリスティックを使用する。一例として、４００メートル離れており、同じバス路線により提供されていないバス駅Ａ及びＢを検討する。クエリ時間における、このヒューリスティックのために、バス駅ＡからＢへの徒歩が最適と決定される。しかし、ヒューリスティックなしには、駅Ａを出発するローカル検索からの最適の結果は、駅Ａを出発して、駅Ｃに遠回りしてから駅Ｂに到達するトリップである。従って、このヒューリスティックは、ＴＰＣモジュール１０９がＡからＢへのトランジットトリップを取り除くことを可能とする。駅Ａから駅Ｂへは単に歩くのが最適だからである。
【０１６９】
次に、図１０Ｅを参照すると、ローカル起点駅から近隣のローカル駅への徒歩コストを決定するためにＴＰＣモジュール１０９により実行される方法である。一実施形態において、ＴＰＣモジュール１０９は、所与のローカル駅からのローカル検索を実行する（ステップ１０２３）。ローカル検索から、ＴＰＣモジュール１０９は、ローカル駅に近在の全ての駅を決定する（ステップ１０２５）。一実施形態において、ＴＰＣモジュール１０９は、例えば１マイルなどラジアル距離で近在駅を決定する。近在駅毎に、ＴＰＣモジュール１０９は、検索が実行されたトランジット駅から近在駅への徒歩コストに等しいコストラベルを加える。一実施形態において、徒歩のコストは、トランジット駅から近在駅へ歩くのにかかる推測の時間量を表す。
【０１７０】
例えば、ローカル駅Ａを仮定する。ＴＰＣモジュール１０９は、トランジットグラフ内で半径２マイル内の全ての近在駅を決定するためにローカル駅Ａからローカル検索を実行する。検索は、駅Ａの半径２マイル内にある駅Ｍ，Ｋ及びＧのリストを結果としてもたらす。ＴＰＣモジュール１０９は、それから、近在駅のそれぞれに、駅Ａからその近在駅への徒歩のコストを示すラベルを追加する。例えば、駅Ａから駅Ｍに或る人が歩くのに平均で１８００秒（０．５時間）かかるとする。ＴＰＣモジュール１０９は、駅Ｍに１８００秒のコストを示すラベルを追加する。
【０１７１】
一実施形態において、ＴＰＣモジュール１０９は、前述と同様な処理をグローバル駅毎に実行する。所与のグローバル駅に対して、ＴＰＣモジュール１０９は、トランジットグラフ内でグローバル駅から到達可能な全ての近在駅を決定するために、グローバル検索を実行する。近在駅毎に、ＴＰＣモジュール１０９は、近在駅の駅ノードにコストを追加する。一実施形態において、ＴＰＣモジュール１０９は、ノードに関連付けられた乗換ペナルティと徒歩コストに基づいてグローバル駅にペナルティを追加する。
【０１７２】
次に、図１０Ｆを参照すると、近在駅から目的駅までの徒歩コストを決定するために、ＴＰＣモジュール１０９が実行する方法が示されている。例えば、起点駅から目的駅への所与のトリップは、起点駅から目的駅に直接行くよりもむしろ、起点駅から目的駅の近在駅を通過して、その近在駅から目的駅まで歩いたほうが最適であるかもしれない。
【０１７３】
一実施形態において、トリップの目的駅は、到着ループを備える。到着ループは、目的駅の乗車ノードのループと、弧によって連結されたそれらラベルである。ＴＰＣモジュール１０９は、到着ループで弧を緩和して（ステップ１０２９）、それぞれ対応する乗車ノードで最適な、とはいえ実際のところは最適ではない、トリップのラベルを取り除く。というのも、より早く到着するというコストの点でより良いトリップが存在するからである。
【０１７４】
ＴＰＣモジュール１０９は、近くにある駅を決定するために目的駅でローカル検索を実行する（ステップ１０３１）。ＴＰＣモジュール１０９は、近在駅の乗車ノードから目的駅の駅ノードへの弧を追加することにより、目的駅の到着ループを拡張する（ステップ１０３３）。一実施形態において、それら弧は、近在駅から目的駅への徒歩を示す徒歩弧を表す。
【０１７５】
前述の処理を、ローカル駅毎に繰り返すことにより、ＴＰＣモジュール１０９は、気かｋとして、乗換パターンのセットを得て、それからそれらを記憶する。
５．乗換パターンの圧縮
【０１７６】
一実施形態において、事前計算処理の最終局面は随意である。乗換パターン圧縮モジュール１１１は、前述した乗換パターンを完全な形で保存するよりも、効率的に保存することを目的として、ＴＰＣモジュール１０９により決定された乗換パターンを圧縮する。一般に、乗換パターン圧縮モジュール１１１は、各乗換パターンを小さい部分に分割する。乗換パターンを圧縮することにより、乗換パターンは、一般により小さい断片に分解され、それらのサイズのために、高い冗長性を持ち、それら断片をより効果的に記憶できる効果的な方法で圧縮されるだろう。
【０１７７】
図１１を参照すると、乗換パターンを圧縮するために乗換パターン圧縮モジュール１１１が実行する処理の流れが示されている。後述の処理は、前述したＴＰＣモジュール１０９により決定された全乗換パターン毎に繰り返される。
【０１７８】
一実施形態において、乗換パターン圧縮モジュール１１１は、入力として乗換パターンを取る（
ステップ１１００）。乗換パターン圧縮モジュール１１１は、トランジットグラフ内の、単一の駅の実体を用いた繰り返し的駅の連なりをそれぞれ置き換えるために、乗換パターンを随意でフィルタする（ステップ１１０１）。例えば、次のようなジャーニーの乗換パターンを考える：駅Ａで乗車し、駅Ｂに到着し、駅Ｂで乗車し、駅Ｃに到着し、駅Ｄで乗車して駅Ｆに到着する。言い換えれば、ジャーニーの乗換パターンは、ＡＢＢＣＤＦである。乗換パターンの全ての乗車イベントはトランジットグラフの駅ノードを表し、全ての到着イベントはトランジットグラフの乗車ノードを表す。この例では、乗換パターン圧縮モジュール１１１は、駅Ｂが繰り返されており、単一の実体“Ｂ”を用いた駅の連なり“ＢＢ”に取って代わることを決定する。乗換パターン圧縮モジュール１１１は、本質的に、駅又は乗車ノードの間の区別をしない。従って、その結果として得るパターンは、ＡＢＢＣＤＦではなくて、ＡＢＣＤＦになる。別の実施形態では、乗換パターンは、乗換パターン内の繰り返し的駅の連なりを取り除くためのフィルタをされない。
【０１７９】
乗換パターンがフィルタされるか否かにかかわらず、乗換パターン圧縮モジュール１１１は、乗換パターンサフィックスを決定する（ステップ１１０３）。乗換パターンサフィックスは、サフィックに関連付けられた駅に先行する乗換パターン内の２つの駅の連なりを示す。本質的に、２つの駅に先行されない何れの駅も除くと、乗換パターン内の各駅は、目的駅とみなされ得るものであり、従って、それらは関連付けられたサフィックスを持ち得る。従って、乗換パターン内の、２つの駅に先行された駅毎に、乗換パターン圧縮モジュール１１１は、サフィックスに関連付けられた駅に先行する乗換パターン内の２つの駅を示す乗換パターンサフィックスを決定する（ステップ１１０５）。起点駅から目的駅への乗換パターンサフィックスは、そのパターンのための、乗換パターンサフィックスセットとみなされる。乗換パターンサフィックスが決定されたら、乗換パターン圧縮モジュール１１１は、各乗換パターンサフィックスとそれに関連する駅（乗換指示セット）を記憶する（ステップ１１０７）ことにより、圧縮された乗換パターンを得る（ステップ１１０９）。このようにして乗換パターンを記憶することにより、乗換パターン圧縮モジュール１１１は乗換パターンのセグメント（区切られた部分）を記憶する。
【０１８０】
圧縮された乗換パターンＡＢＣＤＦの記憶構成の一例は、下記の通りである。
【表８】

【０１８１】
上記の通り、関連付けられた乗換パターンサフィックスを持つ乗換パターンＡＢＣＤＦの駅は、Ｆ，Ｄ及びＣである。乗換パターンサフィックスは、関連付けられた駅に到着するために使用される乗換パターン内の２つの駅の連なりを示す。上記の乗換パターンサフィックスの集合は、起点駅Ａ及び目的駅Ｆのための、乗換パターンセットとみなされる。また、この記憶構成は、実際の乗換パターンを失くしており、駅ＡからＦへの乗換パターンは、上記記憶構成から再構築できる。
【０１８２】
更なる例として、所与の乗換パターンＱＹＧＬＭＫＲを挙げる。圧縮された乗換パターンＱＹＧＬＭＫＲの記憶構成の一例は、下記の通りである。
【表９】

【０１８３】
この例では、関連付けられた乗換パターンサフィックスを持つ乗換パターンＱＹＧＬＭＫＲの駅は、Ｒ，Ｋ，Ｍ，Ｌ及びＧである。各乗換パターンサフィックスは、サフィックスに関連付けられた駅に到着するために使用される、フィルタされた乗換パターン内の２つの駅の連なりを示す。例えば、駅Ｒに関して、駅Ｍ及びＫの連なりは、フィルタされた乗換パターン内で駅Ｒに先行する駅の順を示す。テーブル内のその他の駅毎に、対応する乗換パターンサフィックスは、乗換パターンサフィックスに関連付けられた駅に先行する２つの駅の連なりを示す。乗換パターンサフィックスの集合は、起点駅Ｑから目的駅Ｒへの乗換パターンサフィックスのセットである。
【０１８４】
クエリ時間において、乗換パターンは乗換パターンサフィックスのセットから再帰的に再構築される。この処理は、更に詳細に後述される。また、乗換パターン自身は失われ、記憶領域の量は著しく減少する。
III．クエリ時間処理
【０１８５】
図１に戻ると、前述の通り、クエリ解決モジュール１１５は、ユーザのクエリ（問い合わせ）に応じて最適ジャーニールートを決定するために、事前計算モジュール１０３により提供される乗換パターン計算を使用する。事前計算の間に決定された乗換パターンを用いることにより、クエリ解決モジュール１１５は、要求を遂行するために必要となる計算量を極小にできる。図１に示すとおり、クエリ解決モジュール１１５は、ローカル駅決定モジュール１１７と、クエリグラフ生成モジュール１１９と、クエリグラフ分析モジュール１２１と、トリップ供給モジュール１２３と、乗換パターン構築モジュール１３５を備える。次に、図１２を参照すると、クエリ解決モジュール１１５によりクエリを処理するための行程の一実施形態は、下記の機能的ステージを備える。
【０１８６】
１２００：近在駅を決定する
【０１８７】
１２０１：乗換パターンを構築する
【０１８８】
１２０３：クエリグラフを生成する
【０１８９】
１２０５：クエリグラフを拡張する
【０１９０】
１２０７：クエリグラフを評価する
【０１９１】
１２０９：最適ジャーニーを決定する
【０１９２】
１２１１：最適ジャーニーを供給する
【０１９３】
クエリを処理する各機能的ステージは以下に詳しく説明される。
１．近在駅を決定する
【０１９４】
図１３は、一実施形態に従って、ローカル駅決定（ＬＳＤ）モジュール１１７により実行される、起点（つまり出発）地点と目的地点に関する近在駅を決定すること（ステップ１２００）によりクエリを処理する第１ステージの処理フローを示す。一実施形態において、ローカル駅決定（ＬＳＤ）モジュール１１７は、入力としてクエリ１３００を受信する。クエリ１３００は、公共トランジット指示のために、ユーザから受信する。一実施形態において、クエリ１３００は、或るジャーニーのための起点地点及び目的地点を少なくとも含む。起点地点は、ユーザの現在の地理的位置又はユーザがトリップを開始したい任意の位置であり、一方、目的地点は、行き先の地理的位置である。起点及び目的地点は、トランジット駅の位置であってもよいし、そうでなくてもよい。一実施形態において、起点及び目的地点は住所の形式である。これら受信したクエリは、また、起点地点からの出発又は目的地点への到着の時刻及び／又は日付を含んでよい。例えば、クエリは、「午後２時発カリフォルニア州９４０４１、マウンテンヴュー、カリフォルニア通り８０１（801 California Street,Mountain View,CA94041）から、カリフォルニア州９４１０４、サンフランシスコ、カリフォルニア通り５５５（555 California San Francisco,CA94104）へのルートが欲しい」と言明するだろう。
【０１９５】
クエリ１３００を受信すると、ＬＳＤモジュール１１７は、ステップ１３０１において、起点地点と目的地点との両方を、各地点に対応する緯度及び経度座標に対応付ける。そして、ＬＳＤモジュール１１７は、ステップ１３０３において、起点地点と目的地点との緯度及び経度座標から、ラジアル距離内の全ての駅を決定する（つまり位置を示す）。一実施形態において、ラジアル距離は、起点及び目的地点の半径２マイル内の全ての駅が決定されるように、２マイルに設定される。別の実施形態では、異なるラジアル距離を使用できる。
【０１９６】
近在駅の位置を示した後、ＬＳＤモジュール１１７は、起点地点に近在の全ての駅を含む駅ＩＤの起点駅リストを作成し（ステップ１３０５）、且つ、目的地点に近在の全ての駅を含む駅ＩＤの目的駅リストを作成する（ステップ１３０７）。また、起点駅から、それに関連付けられた近在駅のそれぞれへの徒歩コストもまた、起点駅リストに供給される。同様に、各近在駅から目的駅への徒歩コストもまた、目的駅リストに供給される。
２．乗換パターン構築
【０１９７】
クエリ時間処理の第２ステージにおいて、乗換パターン構築モジュール１３５は、乗換パターンを作成する（ステップ１２０３）。以下の乗換パターン構築の説明は、乗換パターンがグローバル駅を使って計算されたものであるとの仮定に基づいている。一実施形態において、乗換パターンを作成するために、乗換パターン構築モジュール１３５は、入力として、起点駅リスト１３０５及び目的駅リスト１３０７を受信する。乗換パターン構築モジュール１３５は、起点駅リスト１３０５内の起点駅から、目的駅リスト１３０７内の目的駅への乗換パターンを決定する。乗換パターンの決定は、起点駅がグローバル駅かローカル駅かに依存する。
【０１９８】
一実施形態において、起点駅リスト１３０５内のグローバル駅毎に、乗換パターン構築モジュール１３５は、記憶されたグローバル乗換パターンから、グローバル駅から目的駅リスト１３０７内の各駅への乗換パターンを示すグローバル乗換パターンを決定する（つまり検索する）。一例として、グローバル駅とみなされた起点駅Ａと、グローバル駅又はローカル駅のどちらでもありうる目的駅Ｌを検討する。乗換パターン構築モジュール１３５は、記憶されたグローバル乗換パターンから、駅Ａから出発して駅Ｌで終わるグローバル乗換パターンを決定すると、駅Ａから駅Ｌへの１以上のグローバル乗換パターンを結果として得る。この処理は、起点駅リスト１３０５内のグローバル駅毎に、目的駅リスト１３０７内の各駅まで、繰り返される。
【０１９９】
一実施形態において、起点駅リスト１３０５内のローカル駅毎に、乗換パターン構築モジュール１３５は、各ローカル駅に関連付けられたアクセス駅のセットを決定する。前述の通り、アクセス駅は、ローカル駅に関連付けられたグローバル駅である。各ローカル駅のアクセス駅のセットが決定されたら、乗換パターン構築モジュール１３５は、ローカル駅毎に、そのローカル駅からその各アクセス駅へのローカル乗換パターンを決定する。乗換パターン構築モジュール１３５は、そして、各アクセス駅から目的駅リスト１３０７内の各目的駅へのグローバル乗換パターンを決定する。従って、ローカル駅から目的駅への乗換パターンは、ローカル乗換パターンとグローバル乗換パターンとの組み合わせである。
【０２００】
しかしながら、随意の乗換パターン圧縮が実行された場合には、乗換パターンそれ自身は記憶されないことに留意されたい。したがって、乗換パターン構築モジュール１３５は、ジャーニーのための完全な乗換パターンを作るために、乗換パターンを復元する。言い換えれば、乗換パターン構築モジュール１３５は、起点駅及び目的駅に関連付けられた乗換パターンサフィックスを用いてグローバル乗換パターンとローカル乗換パターンとを再帰的に作る。前述の通り、乗換パターンサフィックスセットは、駅のペアに関連付けられたサフィックスのセットを表す。セット内の各サフィックスは、乗換パターンサフィックスに関連付けられた駅に到達するのに先立つ２つの駅でのトランジット車両の乗換を表す２つの駅の連なりを表す。
【０２０１】
例えば、所与の起点駅Ａと目的駅Ｆのペアのための乗換パターンを決定するために、乗換パターン構築モジュール１３５は、ＡからＦへのサフィックスのセットを決定する。駅Ｆに関連付けられたサフィックスの１つが（Ｄ，Ｆ）とする。このことは、Ａ、・・・Ｄ，Ｅ，Ｆに至るＡからＦへの乗換パターンがいくつか存在することを示す。
【０２０２】
乗換パターンの次の脚を作るために、乗換パターン構築モジュール１３５は、直前の乗換パターンサフィックスに記録された２つの駅に関連付けられた乗換パターンサフィックスセットを決定する。そして、乗換パターンサフィックスは連結され、乗換パターンの部分集合を結果として得る。乗換パターン構築モジュール１３５は、起点地点から目的駅までの乗換パターンが構築されるまで、乗換パターンサフィックスセットの検索を繰り返す。
【０２０３】
前述したＡ、・・・Ｄ，Ｅ，Ｆで終わるＡからＦへの乗換パターンの例を続けると、乗換パターン構築モジュール１３５は、Ｄに至るペア（Ａ，Ｅ）のためのサフィックスのセットを検索する。この場合、乗換パターン構築モジュール１３５は、駅Ｄのためのサフィックス（Ｃ，Ｄ）又は（Ｂ，Ｄ）を検索する。乗換パターン構築モジュール１３５は、そして、Ｃに至るペア（Ａ，Ｄ）のためのサフィックスと、Ｂに至るペア（Ａ，Ｄ）のためのサフィックスを検索する。これは、サフィックス（Ａ，Ｃ）と（Ｂ，Ｃ）が検索される結果となる。乗換パターン構築モジュール１３５は、それから、Ｂに至るペア（Ｂ，Ｄ）のためのサフィックスを決定し、結果としてサフィックス（Ａ，Ｂ）と、サフィックス（Ａ，Ｂ）をもたらすＢに至るペア（Ｂ，Ｃ）とを得ることとなる。乗換パターン構築モジュール１３５は、起点駅Ａから目的駅Ｄへの乗換パターンを形成するために、乗換パターンサフィックスを連結する。上述したこの例では、ＡからＦへの乗換パターンセットは、（Ａ，Ｂ，Ｄ，Ｅ，Ｆ）、（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ）及び（Ａ，Ｃ，Ｄ，Ｅ，Ｆ）である。
３．クエリグラフ生成
【０２０４】
クエリ処理の第３ステージにおいて、クエリグラフ生成（ＱＧＧ）モジュール１１９は、クエリグラフを生成する（ステップ１２０５）。一般に、クエリグラフは、クエリに関するトランジット情報のみを含み、時間独立である（時間に依存しない）。クエリグラフは、起点地点から目的地点への最適ルートを決定するために使用される。クエリグラフは、クエリグラフに含まれる情報が当該クエリにのみ関連しているので、最適ルートを決定するために必要とされる計算を極小にする。一実施形態において、クエリグラフは、クエリに関連する起点地点と目的地点、駅を表すノード、及び、駅を連結する弧を含む。クエリグラフ内の駅は、トランジット車両の乗換が行われる起点地点から目的地点に到達するための経路に含まれるトランジット駅を表す。クエリグラフ内の各弧は、ノードを連結する、駅ペア間の直通接続を表す。従って、弧は、その弧によって連結された目的駅に到達するための経路上で停車が行われる（しかし乗換はしない）１以上の中間駅を表す。更に、或る弧は、車両を出る駅から車両に乗車する駅までの徒歩をも表す。
【０２０５】
図１４を参照すると、受信したクエリに関するクエリグラフを生成するための、ＱＧＧモジュール１１９の処理フローが示されている。ＱＧＧモジュール１１９は、乗換パターン構築モジュール１３５により決定された起点地点と目的地点に関連付けられた乗換パターン１４００を入力として取る。
【０２０６】
駅ペア（すなわち起点駅と目的駅）毎の乗換パターンを受信したら、ＱＧＧモジュール１１９は、駅ペア毎の乗換パターンのセットを用いてクエリグラフを生成する（ステップ１４０３）。ＱＧＧモジュール１１９は、各駅ペアのセットを一連のノードとして表す（ステップ１４０１）ことにより、クエリグラフを生成する。すなわち、乗換パターン内に示された各駅は、クエリグラフ内のノードとして表され、そのノードは乗換パターンによって示された順に配列される。ＱＧＧモジュール１１９は、そして、乗換パターン何に示されたシークエンス（順列）に従って、各駅のペアを弧で連結する。弧はクエリグラフ内の移動の方向を表しており、クエリグラフ内のノードのペアを連結する。一実施形態において、各弧は、駅への歩行又はトランジット車両での駅への移動のいずれも表す。各弧の表現は、乗換パターン内の繰り返しシークエンスが乗換パターン圧縮のときにフィルタされているかどうかに応じて、クエリグラフに供給されてよい。この説明においては、乗換パターンは、繰り返しシークエンスのフィルタが成されているものである。
【０２０７】
一実施形態において、ＱＧＧモジュール１１９は、起点地点と目的地点を表す２つの人為的なノードを除いて、トランジットグラフ内の各ノードのノードＩＤにトランジットグラフ内の駅ＩＤを割り当てる。ＱＧＧモジュール１１９は、これら人為的なノードに、一実施形態によれば、例えば出発地点に“１”、行き先地点に“２”などという汎用的ＩＤを与える。ＱＧＧモジュール１１９は、起点地点及び目的地点を表すノードを、クエリグラフ内の他のノードに、徒歩を表す弧によって連結する。ＱＧＧモジュール１１９が各ノードに識別ＩＤを割り当てることを終えたら、クエリグラフが完成する（ステップ１４０５）。
【０２０８】
図１５を参照すると、“１”とラベル付けされたノードによって表された起点地点から“２”とラベル付けされたノードによって表された目的地点までのクエリグラフ１５００の一例が示されている。また、起点駅から目的駅までの３つの乗換パターンだけが示されているが、クエリグラフが任意の数の乗換パターンを持っていて良いことは理解されるべきである。
【０２０９】
この例では、各ジャーニーは、乗換パターンの凡例１５０１により支持されている。乗換パターンの凡例１５０１に示す通り、乗換パターン１は実線弧に関連付けられており、乗換パターン２は点線弧に関連付けられており、乗換パターン３は破線弧に関連付けられている。クエリグラフ１５００は、乗換パターン１が｛１ＡＢＣ２｝の乗換パターンを持つことを描いている。したがって、この乗換パターンは、起点地点から駅Ａまで歩き、駅Ａから駅Ｂまで通行し（すなわちトランジット車両又は徒歩のどちらかを使用する）、駅Ｂから駅Ｃまで通行し、そして、駅Ｃから目的地点まで歩くことを表している。一方、乗換パターン２は｛１ＤＥＦＧ２｝の乗換パターンを持っている。したがって、乗換パターン２に対しては、クエリグラフ１５００は、出発地点から駅Ｄまで歩き、駅Ｄから駅Ｅまで通行し、駅Ｅから駅Ｆまで通行し、駅Ｆから駅Ｇまで通行し、そして、駅Ｇから目的地点まで歩くことを示す。乗換パターン３は｛１ＡＦＣ２｝の乗換パターンを持っており、トリップ１及び２と同様な方法で、記述され得る。前述の通り、各弧に関連付けられたトランジットの形式はクエリグラフによっては表現されず、クエリグラフはクエリグラフ内の駅で乗換が行われるか否かを示さない。
４．クエリグラフ拡張
【０２１０】
クエリ処理の第４ステージは、随意の乗換パターンの圧縮ステップが実行され、且つ、乗換パターンの圧縮の間に乗換パターンがそれらに対応する駅のシークエンスのフィルタされたかどうかに依存して随意であることに留意されたい。しかし、前述の通り、説明の文脈では、乗換パターンがフィルタされることを想定している。クエリ処理の第４ステージにおいて、クエリグラフ分析（ＱＧＡ）モジュール１２１は、ＱＧＧモジュール１１９により生成されたクエリグラフを拡張する（ステップ１２０５）。前述の通り、クエリグラフは、駅を表すノード及びノードを連結するノードのみが含まれている。拡張していない形式のクエリグラフは、弧が徒歩の通行又はトランジット車両をあらわしているかどうかを表さない。クエリグラフを拡張することにより、ＱＧＡモジュール１２１は、乗換パターン内の各駅間の可能なルートを決定する。各ルートが特定時刻の乗換パターンの具体例であるから、決定される可能なルートは各駅で乗換が行われるかどうか及び到着／出発の時刻を表す。
【０２１１】
図１６を参照すると、クエリグラフを拡張するための、ＱＧＡモジュール１２１の処理フローが示されている。ＱＧＡモジュール１２１は、入力として、ＱＧＧモジュール１１９により生成されたクエリグラフを取る（ステップ１４０５）。ＱＧＡモジュール１２１は、起点地点と目的地点とを除いて、クエリグラフ内の各ノードを駅ノード及び乗車ノードに拡張する（ステップ１６００）。従って、クエリグラフ内の各ノードは、拡張されたクエリグラフにおいて、２つのノードによって表される。
【０２１２】
次に、乗換パターンが、乗換パターン計算の間に、乗換パターン内の駅の繰り返しシーケンスのフィルタをしない乗換パターンの実施形態を検討する。この実施形態では、乗換パターンが駅で乗換が行われるか否かを示すものであるから、クエリグラフの構築は、結果として、拡張されたクエリグラフをもたらす。例えば、ＡＢＢＣＤＦの乗換パターンにおいて、この乗換パターンは、人が駅Ｂに到着し駅Ｂでトランジット車両を出て、駅Ｂで別のトランジット車両に乗車することを示す。従って、この実施例では、クエリグラフは、駅Ｂの駅ノードと乗車ノードを持って生成される。クエリグラフは、本質的に、その拡張された形式で作成される。従って、この実施例では、クエリグラフの拡張に関して上述した教示はクエリグラフの生成の間に含まれる。
５．クエリグラフの評価
【０２１３】
各ノードが拡張されたら、ＱＧＡモジュール１２１は、拡張されたクエリグラフを評価する（ステップ１２０７）。一実施形態において、ＱＧＡモジュール１２１は、直通接続データベース１２５に記憶された直通接続情報（ステップ１６０３）を使って拡張されたクエリグラフ内の駅間の直通接続を決定する（ステップ１６０１）。すなわち、クエリグラフ内の乗換パターン毎に、ＱＧＡモジュール１２１は、記憶された直通接続情報から、起点駅から後続の駅への直通接続があるかどうかを、その後続の駅から更に次に続く駅への直通接続があるかどうかを、以下同様に目的駅まで、決定する。一実施形態において、受信したクエリが出発時刻を含んでいるので、ＱＧＡモジュール１２１は、示された時刻よりも大きいか又は等しい時刻に出発する直通接続のみを決定する。受信したクエリが目的駅への到達時刻を含んでいる場合は、ＱＧＡモジュール１２１は、示された時刻よりも小さい又は等しい時刻に、目的駅に到着する直通接続のみを決定する。したがって、ＱＧＡモジュール１２１は、クエリに関連する直通接続のみを検索する。
【０２１４】
一般に、ＱＧＡモジュール１２１は、乗換パターン内の各駅ペア間から１以上の直通接続を決定する。各直通接続は、各駅ペア間の異なるトリップを示す。例えば、トリップは、各直通接続トリップで使用されるトランジット車両の違いにより、互いに異なる。従って、直通接続は、トリップ内の各駅におけるまったく同じ到着／出発時刻を持つ駅ペア間のトリップを含むかもしれないが、トリップのために使われるトランジット車両の違いにより異なるものとなる。また、直通接続トリップは、トリップに関連付けられたスケジュール情報に基づいて差別化されてよい。例えば、単一のトランジット車両が、駅ペア間の複数の直通接続トリップを成してよく、その直通接続トリップは、各トリップのスケジュールによって特定される。
【０２１５】
例えば、乗換パターンＡＢＣを検討する。乗換パターン内の駅に関連付けられた直通接続を決定するために、ＱＧＡモジュール１２１は、駅Ａから駅Ｂへの直通接続を検索する（取ってくる）。ＱＧＡモジュール１２１は、それから、駅Ａから駅Ｂへの到着後に出発する、駅Ｂから駅Ｃへの直通接続を検索する。なお、駅間の直通接続は、トリップに関連付けられたトランジット車両が乗換駅に到達する前に停止する駅を本来的に示していることに留意されたい。例えば、駅Ａから駅Ｂでは、これら駅間の直通接続は駅Ｅ及びＦで停車を含む。
【０２１６】
直通接続トリップが検索されたら、ＱＧＡモジュール１２１は、起点駅から目的駅までのジャーニーを生成するために、直通接続を繋ぎ合わせる（スティッチ）。１以上の直通接続を縫い合わせること（つまり連結すること）は、起点駅から目的駅までのジャーニーをカバーするために、直通接続合併をすることを含む。
【０２１７】
例えば、再び乗換パターンＡＢＣを検討する。ＱＧＡモジュール１２１は、駅Ａから駅Ｂへの直通接続と、駅Ｂへの到着後の出発時刻の駅Ｂから駅Ｃへの直通接続を決定する。駅Ａから駅Ｂへの直通接続が１時００分に到着するものと仮定する。トリップを縫い合わせるためには、ＱＧＡモジュール１２１は、ユーザが駅Ｂで駅Ｃに向かうトランジット車両に乗り換えるために十分な時間を持つように１時００分よりもいくらか後に駅Ｃに向けて駅Ｂを離れる直通接続トリップを検索する。
【０２１８】
駅間の直通接続が検索されたら、ＱＧＡモジュール１２１は、１以上の直通接続により形成された乗換パターンのトリップを表すために、拡張されたクエリグラフ内のノードに弧を加える（ステップ１６０５）。一実施形態において、拡張されたクエリグラフは、トランジットグラフの説明と同様に４種類の弧を持ち、駅間で行われるトランジットイベントを説明するために前述したのと同じ概念を用いる。
【０２１９】
一実施形態において、起点駅と目的駅は、駅への歩行を表すために、それぞれ、起点駅の駅ノードと目的駅の乗車ノードとに連結される。その他の全てのノードに対して、ＱＧＡモジュール１２１は、直通接続クエリ経由で決定されたトリップに基づいて、前述の構成でノード間に弧を追加する。拡張されたクエリグラフにおいて各駅で行われる乗換を表すために、駅のペアに対して、ＱＧＡモジュール１２１は、起点駅の乗車ノードと乗換が行われる駅の駅ノードとの間に、弧を追加する。例えば、乗換パターンＡＢＣにおいて、駅Ａで車両に乗り駅Ｂに移動し、駅Ｂで車両を離れてその駅Ｂで別の車両に乗車するする人を表すペアＡＢを検討する。この例において、駅Ａの乗車ノードは、乗換が行われることを表すために、駅Ｂの駅ノードに連結される。
【０２２０】
なお、トリップを作成するために使用される直通接続情報は、駅の出発又は到着時刻を示すスケジュール情報を持つことに留意されたい。従って、拡張されたクエリグラフ内の弧は、本質的に、スケジュール情報に関連付けられている。例えば、駅ノードＡと乗車ノードＢの間に２つの弧が存在する場合、第１の弧は８時００分の駅Ａからの出発と１２時００分の駅Ｂへの到着とを表し、一方、第２の弧は１０時００分の駅Ａからの出発と１１時００分の駅Ｂへの到着とを表すだろう。弧は、また、直通接続トリップの間に停車が行われる駅への到着／駅からの出発を示してもよい。
【０２２１】
図１７を参照すると、図１５に示すクエリグラフ１５００の拡張されたクエリグラフ１７００の一例が示されている。なお、トリップ凡例１７０１は３つのトリップを描いている：ジャーニー１、ジャーニー２、ジャーニー３である。ジャーニー１は、実線弧の経路により表されており、クエリグラフ１５００の乗換パターン１に対応している。ジャーニー２及び３は、それぞれ、クエリグラフ１５００の乗換パターン２，３に対応している。
【０２２２】
クエリグラフ１７００に示す通り、ジャーニー１、２及び３は、異なるタイプのノードを連結する弧の意味の説明に基づいて、駅で行われる乗換を描いている。具体的には、ジャーニー１及び３は１回の乗換を描いており、一方、ジャーニー２は２回の乗換を描いている。一例としてジャーニー１を使うと、拡張されたクエリグラフは、人は起点地点“１”から駅Ａまで歩き、駅Ａでトランジット車両に乗車することを描いている。トランジット車両は駅Ｂまで移動して、ユーザはそのトランジット車両から降りて、この乗換の実行が示された駅Ｂで第２の車両に乗る。駅Ｂから、第２のトランジット車両は駅Ｃまで移動し、ユーザはここで第２の車両を離れて、行き先地へ徒歩で向う。ジャーニー２に関しては、拡張されたクエリグラフは、駅Ｅと駅Ｆで乗換が行われることが描かれており、そのことは、両駅Ｅ及びＦの乗車ノードと駅ノードを連結する弧によって表されている。
【０２２３】
なお、クエリグラフ１５００内に乗換パターン毎に、ＱＧＡモジュール１２１は、起点駅から目的駅までの１以上のジャーニーを見つけるだろう。拡張されたクエリグラフ１７００において、説明の便宜上、乗換パターン毎に、１つのジャーニーのみが示されている。しかし、乗換パターン毎の駅のシークエンスは、起点駅から目的駅までの異なるトリップを表す駅間のトリップを１つ以上持ち得る。例えば、ジャーニー１に関連付けられた駅は、乗換パターン１Ａ_sＢ_oＢ_sＣ_o２の間を連結する、異なる弧を３セット持っていてよく、各弧のセットは異なるトリップを表す。
６．最適トリップの決定
【０２２４】
図１８を参照すると、最適ジャーニーを決定する（ステップ１２０９）ために、ＱＧＡモジュール１２１により実行される処理フローが示されている。一実施形態において、ＱＧＡモジュール１２１は、拡張されたクエリグラフ１６０７を用いて最適ジャーニーを決定する。ＱＧＡモジュール１２１は、クエリグラフの出発地点を初期化することにより始める（ステップ１８０１）。出発地点を初期化することにより、ＱＧＡモジュール１２１は、出発地点にコスト０をセットする。拡張されたクエリグラフ内の各弧に対して、ＱＧＡモジュール１２１は、コストを適用する（ステップ１８０３）。或るコストは起点地点から起点駅までの徒歩を表す弧に適用され、また、或るコストは目的駅から目的地点までの徒歩を表す弧にも適用される。コストは、それから、拡張されたクエリグラフ内の残りの弧に適用される。
【０２２５】
ＱＧＡモジュール１２１は、直通接続テーブル１８０７により特定されたトリップのコストに基づいて、拡張されたクエリグラフ内の最適ジャーニーを決定するために、パレート‐ダイクストラ計算を適用する（ステップ１８０５）。一実施形態において、パレート‐ダイクストラ計算の結果は多様とみなされる複数の最適ジャーニー１８０９を返す。ＱＧＡモジュール１２１は、ジャーニーの乗換パターンが異なっていることを意味する地理的に異なる経路を進むという点で異なっている複数の低コストジャーニーを決定する。別の実施形態では、ＱＧＡモジュール１２１は、多様な車両を使うジャーニーを決定する。例えば、ＱＧＡモジュール１２１は、バス経由の最適ジャーニー、地下鉄による最適ジャーニー、路面電車による最適ジャーニーを決定する。最後に、ＱＧＡモジュール１２１は、ジャーニーがルートにおいて共通しているものの、ジャーニーの行われる（つまり到着／出発する）時刻が異なるという点で、時間的に異なる最適ジャーニーを決定する。例えば、同じルートを持つ２つのジャーニーは、同じコストを持つだろうが、出発時刻は１５分離れている。
【０２２６】
別の実施形態において、最適ジャーニーを決定するためにパレート‐ダイクストラ計算を適用するのではなく、ＱＧＡモジュール１２１は、別の技術を使って、拡張されたクエリグラフを探索してもよい。一実施形態において、ＱＧＡモジュール１２１は、例えばダイクストラアルゴリズムなど、１つの判定基準グラフ探索計算を使う。パレート‐ダイクストラの適用は複数の判定基準でクエリグラフを評価するのに対して、ダイクストラアルゴリズムはクエリグラフを評価するために１つの判定基準のみを使うので、クエリグラフへのダイクストラアルゴリズムの適用は、最適ジャーニーのより迅速な決定をもたらす。しかし、クエリグラフを評価するためのダイクストラアルゴリズムの使用は、クエリグラフの評価に例えば時間又は車両乗換など単一の判定基準しか用いないため、パレート‐ダイクストラ計算の適用の結果として得る最適ジャーニーのセットよりも多様性のより少ない最適ジャーニーのセットを結果としてもたらすことになる。
【０２２７】
別の実施形態において、ＱＧＡモジュール１２１は、また、最適ジャーニーを決定するためのクエリグラフの評価を速くするために、更に別の技術を使用してもよい。例えば、ＱＧＡモジュール１２１は、最適ジャーニーを決定する速度及び／又はシステムの要求に従う結果の多様性を改善するために、当業者にＡ＊（Ａ‐ｓｔａｒ,エースター）探索アルゴリズムとして知られる目標指向検索、或いは、その他のユーリスティックを適用できる。
７．最適ジャーニーの提供
【０２２８】
クエリ処理の最終ステージにおいて、トリップ供給モジュール１２３は、ユーザに最適ジャーニーを供給する（ステップ１２１１）。一実施形態において、トリップ供給モジュール１２３は、結果ページ１９００上の表示用に最適ジャーニーをフォーマットする。図１９を参照すると、結果ページ１９００の一例が示されている。クエリ入力部１９０１は、起点地点と目的地点が入力されるテキストボックスが描かれている。提案ルート部１９０３は、トランジットサーバ１００により決定された最適ジャーニーを描いている。提案ルート部１９０３に示されたように、トランジットサーバ１００は、同じトランジット時間長を持つが出発時間の異なる３つの最適ジャーニーを提供する。ジャーニー情報選択部１９０５は、ジャーニーのルートを説明する。ここに示された例では、ジャーニー１のルートが示されている。指示は、出発地点からカルトレイン（caltrain）駅まで歩くことを示している。また、図示していないが、詳細表示ボタン１９０７を押すことで、出発地点からカルトレイン（caltrain）駅までどうやって到達するかの指示が与えられる。それから、カルトレイン駅から、指示は、午前８時５９分にマウンテンヴューカルトレイン（Mountain View Caltrain）駅を出発して、午前１０時０２分にサンフランシスコカルトレイン（San Francisco Caltrain）駅に到着する列車２３３号に乗車することを示す。そしてサンフランシスコカルトレイン（San Francisco Caltrain）駅から、午前１０時０９分にタウンゼンド通り＆４番通り（Townsend St&4thSt）から午前１０時２０分にサンソム通り＆カリフォルニア通り（Sansome St&California St）に到着するバス１０号に乗る。ユーザは、それから、行き先地点であるカリフォルニア通り５５５番地（555 California St）まで歩く。
ＩＶ．むすび
【０２２９】
この発明は１つの可能な実施形態に関する詳細を説明された。当業者たちは、この発明が別の実施形態においても実行できることを理解するだろう。第１に、構成要素の個々の名付け、用語の大文字使用、属性、データ構成、或いは、その他のプログラミング又は構造的様相は必須又は重要ではなく、発明を実装する機構又はその特徴は、異なる名前、形式又はプロトコルを持っていてよい。更に、システムは、前述の通りハードウェア及びソフトウェアの組み合わせで実装されてもよいし、或いは、完全にハードウェア実装されてもよい。また、本明細書に記載された種々のシステム構成要素の間の機能の個々の区分は、単に一例に過ぎず、必須ではない。単一のシステム構成要素により実行される機能は複数の構成要素により実行されてもよく、また、複数の構成要素により実行される機能は単一のシステム構成要素により実行されてもよい。
【０２３０】
本開示のいくつかの部分は、この発明の特徴を、情報処理のアルゴリズム及び記号的表現の言葉で記述した。これらアルゴリズム的記述及び表現は、データ処理技術の当業者において、他の当業者に彼らの仕事の要旨を効果的に伝えるために、使われる手段である。これらの動作は、機能的に、又は、論理的に記述されたが、コンピュータプログラムにより実装できることは理解できる。更に、一般性を失することなしに、これらの動作の配置をモジュールとして又は機能的名前（functional name;ファンクショナルネーム）により適用することが時として便利なことは証明されている。
【０２３１】
特に述べられていない限り本開示から明らかな通り、上述の説明を通じて、例えば“処理する”、や“計算する（コンピューティング）”や“計算する（カリキュレイティング）”や“決定する”や“表示する”などといった用語を使用する説明は、コンピュータシステムの動作及び処理、又は、ンピュータシステムメモリ又はレジスタ又はその他の情報記憶装置、伝送又は表示装置の中で
物理的（電子的）量として表されたデータを操作及び伝送する同様な電子計算装置に適用されることは理解される。
【０２３２】
開示された発明のいくつかの側面は、ここではアルゴリズムの形式で説明された処理ステップ及び命令を含む。説明され且つ請求範囲に記載された本発明の、それら処理ステップや命令は、プログラム制御の下でコンピュータハードウェアの動作により実行され、人により行われる精神的ステップは含まない。同様に、説明され且つ請求範囲に記載された全ての種類のデータは、コンピュータシステムによって操作されるコンピュータ読み取り可能な記憶媒体に記憶されるものであり、それらは物理的実体の無い抽象的アイディアではない。
【０２３３】
本発明は、また、ここに開示された動作を実行する装置に関する。この装置は、要求された目的のために特別に構築されたものであってもよいし、或いは、汎用コンピュータからなり、該コンピュータによって実行可能な、コンピュータ読み取り可能な媒体に記憶されたコンピュータプログラムにより、選択的に作動又は再構築される。かかるコンピュータプログラムは、例えば、以下の例示に限定されないが、フロッピーディスク（登録商標）、光学ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気又は光学カード、ＡＳＩＣ（特定用途向け集積回路）を含む任意の種類のディスクなど、コンピュータ読み取り可能な媒体、又は、電子的命令の記憶に適した任意の種類の媒体に記憶され、それぞれコンピュータシステムバスに接続される。更に、詳細な説明で言及したコンピュータは、単一のプロセッサからなるものであってもよいし、又は、計算処理能力を向上させるために複数のプロセッサを使用する構造であってもよい。
【０２３４】
ここに開示したアルゴリズム及び動作は、任意の種類の又はブランドのコンピュータ又はその他の装置により実行され得る。種々の汎用システムが、ここに示された技術に従うプログラムとともに使用されてよく、又は、要求された方法ステップを実行するためのより専用の装置の構成が便利なことは証明されているだろう。それら多様なシステムのために要求される構造は、等価な変形例とともに、当業者にとって明らかであろう。加えて、本発明は、どの特定のプログラミング言語に関しても記述されていない。種々のプログラミング言語がここに記載された通りこの発明の技術を実装するために使用されてよいこと、及び、いずれの特定言語に言及することも本開示を可能にすること、及び、この発明の最良の形態のために提供されていることは、理解されるだろう。
【０２３５】
この発明は、多数形態にわたる広く多様なコンピュータネットワークシステムに適している。この分野において、大規模ネットワークの構成及び管理は、例えばインターネットなどネットワーク経由で、異種のコンピュータ及び記憶装置と通信可能に接続された記憶装置及びコンピュータからなる。
【０２３６】
最後に、この明細書で使用された言葉は、原則的に、読み易さと説明の目的で選択されており、発明の主題を表現又は制限するために選択されたのではない。従って、この発明の開示は、説明的であることを意図しており、以下に述べる特許請求の範囲の発明の範囲を制限することを意図していない。
【符号の説明】
【０２３７】
１００ トランジットサーバ、１０１ フロントエンドインターフェース、１０３ 事前計算モジュール、１０５ トランジットグラフモジュール、１０７ グローバル駅選択モジュール、１０９ 乗換パターン計算モジュール、１１１ 乗換パターン圧縮モジュール、１１３ 直通接続モジュール、１１５ クエリ解決モジュール、１１７ ローカル駅決定モジュール、１１９ クエリグラフ生成モジュール、１１９ モジュール、１２１ クエリグラフ分析モジュール、１２３ トリップ供給モジュール、１２５ ルート情報データベース、１２７ トランジット情報データベース、１２９ トランジット情報インタフェース、１３１ クライアント装置 １３３ ブラウザ、１３５ 乗換パターン構築モジュール、１３７ ネットワーク、４００ トランジットグラフ、４０３ ノード、４０５，４０９ 弧、４０７ コスト、１５００ クエリグラフ、１５０１ 乗換パターン凡例、１７００ クエリグラフ、１７０１ トリップ凡例、１９００ 結果ページ、１９０１ クエリ入力部、１９０３ 提案ルート部、１９０５ ジャーニー情報選択部、１９０７ 詳細表示ボタン

【特許請求の範囲】
【請求項１】
トランジット駅間の最適公共交通機関乗換パターンを計算するために、コンピュータに実装される方法であって、前記方法はコンピュータにより実行され、且つ、
それぞれ起点駅と目的駅を示す記憶された公共トランジットトリップ毎に、その起点駅から目的駅までの公共トランジットトリップの間のトランジット車両によるトランジット駅での１以上の停車のスケジュールを表す記憶されたトランジットルートを検索するステップと、
記憶された公共トランジットトリップ毎の前記検索されたルートを、複数の弧により連結された複数のノードのシークエンスとして表すことにより、トランジットグラフを生成するステップであって、前記トランジットグラフ内の各ノードが、前記トランジットトリップに関連付けられたトランジット車両によりトランジット駅で行われるイベントを表すものと、
前記トランジットグラフ内に表されたトランジット駅のペア毎に、
前記トランジットグラフ内の駅のペアの間のトランジット駅での１以上の乗換についての最適トランジットルートを表す少なくとも１つの最適乗換パターンを、前記トランジットグラフから計算するステップと、
トランジット駅のペア毎の前記少なくとも１つの最適乗換パターンを記憶するステップと
を備えることを特徴とする方法。
【請求項２】
前記トランジットグラフ内の各ノードは、それぞれ、駅ノードに関連付けられた駅で乗車できるトランジット車両を表す該駅ノード、又は、乗車ノードに関連付けられた駅にトランジット車両が到着している間、乗車されたままであるトランジット車両を表す該乗車ノードのどちらかを表すことを特徴とする請求項１に記載の方法。
【請求項３】
各弧は、駅で乗車されるトランジット車両を表す乗車弧、駅で降車されるトランジット車両を表す降車弧、人が駅で待つことを表す待機弧、又は、駅への到着時にトランジット車両に乗車したままでいることを表すトランジット弧のいずれか１つを表すことを特徴とする請求項１に記載の方法。
【請求項４】
各弧のコストを生成するステップを更に備え、前記コストは、その弧により連結された第１駅から第２駅まで移動するための価格を、第１駅から第２駅まで移動するための時間長及び関連付けられたペナルティの少なくとも一部に基づいて、表すものであることを特徴とする請求項１に記載の方法。
【請求項５】
前記ペナルティは、金銭的コスト、第１駅から第２駅に到達するために必要なトランジット車両の乗換数、及び、第１駅から第２駅までの徒歩コストに基づくものであることを特徴とする請求項１に記載の方法。
【請求項６】
前記トランジットグラフ内の各弧及び各ノードについての情報を含む１以上のテーブルを生成するステップを更に備えることを特徴とする請求項１に記載の方法。
【請求項７】
前記トランジットグラフのどの駅がグローバル駅を表しているかを決定するステップを更に備え、前記グローバル駅は長距離トリップの間に頻繁にトランジット車両の乗換が行われる駅であることを特徴とする請求項１に記載の方法。
【請求項８】
前記トランジットグラフのどの駅がグローバル駅を表しているかを決定する前記ステップは、
前記トランジットグラフ内の駅毎に、その駅で行われるトランジット車両の乗換数を決定するステップであって、前記トランジット車両の乗換は、駅で人が降車する第１トランジット車両と、駅に居り人が乗車する第２トランジット車両とを表すものと、
各駅で行われる前記トランジット車両の乗換数の少なくとも一部に基づいてグローバル駅を選択するステップと
を備えることを特徴する請求項７に記載の方法。
【請求項９】
前記トランジットグラフのどの駅がグローバル駅を表しているかを決定する前記ステップは、
前記トランジットグラフ内の駅毎に、その駅に関連付けられたノードの駅ノードグループを形成するために、該駅で乗車されるトランジット車両を表すノードをグループ化し、且つ、その駅に関連付けられたノードの乗車ノードグループを形成するために、前記トランジットグラフ内で同じ後続駅のシークエンスを持つ、異なるルートに関連付けられたノードをグループ化するステップと、
前記トランジットグラフ内の駅のペア毎に、その駅のペアに関連付けられたノードのペアの少なくとも一方が該トランジットグラフ内の弧によって連結されているかを決定するステップと、
前記ノードのグループのペア毎に、トランジットグラフ内で弧によって連結されている駅のペアに関連付けられたノードの少なくとも１ペアに応答して前記駅のペアに関連付けられたノードのグループのペアの間に弧を追加するステップと、
前記ノードのグループのペア間の弧毎に、前記ノードのグループのペアに属するノードのペアに関連付けられた最小コストの少なくとも一部に基づくコストを割り当てるステップであって、前記ノードのペアはトランジットグラフ内で弧によって連結されたものと、
前記コストに基づいて複数の前記駅ノードグループから最適経路を決定するステップと、
前記最適経路を示す駅ノードグループ毎に、前記最適経路内でその駅ノードグループに先行する駅ノードグループの数に基づいてスコアを決定するステップと、
各駅ノードグループ毎の前記スコアの少なくとも一部に基づいてグローバル駅を決定するステップと
を備えることを特徴する請求項７に記載の方法。
【請求項１０】
前記トランジットグラフから直通接続トリップを決定するステップを更に備え、前記直通接続トリップは起点駅から目的駅まで、前記起点駅と前記目的駅の間の中間駅でのトランジット車両の乗換無しのトリップであることを特徴とする請求項１に記載の方法。
【請求項１１】
前記トランジットグラフから直通接続トリップを決定する前記ステップは、
前記トランジットグラフ内の起点駅と目的駅の可能なペア毎に、前記トランジットグラフ内の起点駅に関連付けられたノードを目的駅と関連付けられたノードに連結するトリップのセットを決定するステップであって、前記セット内の各トリップは、そのトリップの間にトランジット車両によりなされる停車を表す同じノードのシークエンスを含むものと、
前記トリップのセットを記憶するステップと
を備えることを特徴とする請求項１に記載の方法。
【請求項１２】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、
起点駅と目的駅を示す駅の賢明な組み合わせの可能なペア毎に、前記起点駅の駅ノードをゼロコスト値に初期化するステップと、
前記トランジットグラフ内の最適ルートを決定するために、前記起点駅内の各駅ノードから前記目的駅内の各ノードまで多次元のコストに基づくパレート-ダイクストラ検索を行うステップであって、最適ルートの各ノードは時間長及びペナルティに関するコストを特定するラベルセットを含み、
前記ノード毎に、支配的ラベルを取り除くために前記ラベルセットをフィルタするステップであって、ｄ１がｄ２よりも小さく、ｐ１がｐ２よりも小さいことに応答して第１のラベル（ｄ１，ｐ１）が第２のラベル（ｄ２，ｐ２）より支配的であるものと、
前記フィルタされたラベルセットに基づいて最適経路を決定するステップと、
前記最適経路毎の乗換パターンのフィルタされたラベルセットに関連付けられた駅の順序に基づいて、前記最適経路毎の乗換パターンを決定するステップと
を備えることを特徴とする請求項１に記載の方法。
【請求項１３】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、
前記トランジットグラフ内のグローバル駅毎に、前記トランジットグラフ内の前記グローバル駅に関連付けられた全てのノードから該グローバル駅から到達できる各他のノードへの最適経路を決定するステップと、
前記最適経路毎に、該最適経路の乗換パターンを決定するステップと
を備えることを特徴とする請求項７に記載の方法。
【請求項１４】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、
起点駅と目的駅を示す前記トランジットグラフ内の駅の賢明な組み合わせの可能なペア毎に、前記起点駅に関連付けられた各ノードから前記目的駅に関連付けられた各ノードへの最適経路を決定するステップと、
前記最適経路毎に、その最適経路に関連付けられたコストを決定するステップであって、前記コストは時間及びペナルティの関数であるものと、
前記コストの少なくとも一部に基づいて、前記最適経路から支配的経路を決定するステップであって、前記支配的経路は最小のコストを持つ最適経路であるものと、
前記支配的経路に関連付けられた乗換パターンを決定するステップと
を備えることを特徴とする請求項１に記載の方法。
【請求項１５】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、
前記トランジットグラフ内の非グローバル駅のノードからグローバル駅のノードへの経路を決定するステップであって、前記経路はそれぞれ前記グローバル駅に到達するための経路中で中間駅でのみ最大数のトランジット車両の乗換が行われるものと、
前記決定された経路毎に、前記経路に関連付けられた乗換パターンを決定するステップと
を備えることを特徴とする請求項７に記載の方法。
【請求項１６】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、
前記トランジットグラフ内の非グローバル駅のノードからグローバル駅のノードへの経路を決定するステップであって、前記グローバル駅のノードは前記グローバル駅のノードに関連付けられた駅で乗車されたままでいるトランジット車両を表すものと、
前記決定された経路毎に、前記経路に関連付けられた乗換パターンを決定するステップと
を備えることを特徴とする請求項７に記載の方法。
【請求項１７】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、
前記トランジットグラフ内の非グローバル駅のノードからグローバル駅のノードへ出発する最適経路を決定するステップと、
乗換パターンのセットを形成するために、前記最適経路毎に乗換パターンを決定するステップと、
前記セット内の１以上の乗換パターンに含まれる冗長な乗換パターンを取り除くステップと
を備えることを特徴とする請求項７に記載の方法。
【請求項１８】
起点駅から前記起点駅に関連付けられた近在駅までの徒歩コストを決定するステップと、
目的駅に関連付けられた近在駅から前記目的駅までの徒歩コストを決定するステップと
を更に備えることを特徴とする請求項１に記載の方法。
【請求項１９】
起点駅から前記起点駅に関連付けられた近在駅までの徒歩コストを決定する前記ステップは、
前記トランジットグラフ内の非グローバル駅毎に、前記非グローバル駅のラジアル距離内にある前記トランジットグラフ内の近在駅を決定するステップと、
前記トランジットグラフ内の非グローバル駅と近在駅のペア毎に、前記非グローバル駅から前記近在駅までの徒歩コストを決定するステップと
を備えることを特徴とする請求項１８に記載の方法。
【請求項２０】
トランジット駅のペア毎の前記少なくとも１つの最適乗換パターンを記憶する前記ステップは、
前記少なくとも１つの最適乗換パターン内の１以上の駅の繰り返しシークエンスを取り除くステップと、
前記少なくとも１つの最適乗換パターンを、取り除かれた１以上の駅の繰り返しシークエンスに応答する１以上の乗換パターンサフィックスに区分するステップであって、前記乗換パターンサフィックスのそれぞれは前記少なくとも１つの最適乗換パターン内の乗換パターンサフィックスに関連付けられた駅に先行する駅の連なりのペアを示すものと、
前記１以上の乗換パターンサフィックスを記憶するステップと
を備えることを特徴する請求項１に記載の方法。
【請求項２１】
出発地点から目的地点へのジャーニーの公共トランジット経路を決定するために、コンピュータに実装される方法であって、前記方法はコンピュータにより実行され、且つ、
出発地点から目的地点への公共トランジット経路の要求をクライアント装置から受信するステップと、
前記出発地点のラジアル距離内のトランジット駅を決定し、それにより前記目的地点のラジアル距離内のトランジット駅を含む目的駅リストを生成するステップと、
前記目的地点のラジアル距離内のトランジット駅を決定し、それにより前記出発地点のラジアル距離内のトランジット駅を含む起点駅リストを生成するステップと、
前記起点駅リスト中の起点駅と前記目的駅リスト中の目的駅とを表すトランジット駅の賢明な組み合わせのペア毎に、前記起点駅から前記目的駅へ移動するための前記起点駅及び前記目的駅の間の中間トランジット駅でのトランジット車両の乗換を示す少なくとも１つの記憶された乗換パターンを検索するステップと、
前記検索された乗換パターン毎に、特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定するステップと
を備えることを特徴とする方法。
【請求項２２】
前記出発地点は前記クライアント装置のユーザの現在の地理的位置であることを特徴とする請求項２１に記載の方法。
【請求項２３】
前記目的地点は前記クライアント装置のユーザが望む行き先の地理的位置であることを特徴とする請求項２１に記載の方法。
【請求項２４】
前記出発地点又は前記目的地点はトランジット駅の地理的地位であることを特徴とする請求項２１に記載の方法。
【請求項２５】
前記要求は、更に、前記出発地点からの出発時刻又は前記目的地点への到達時刻を含むことを特徴とする請求項２１に記載の方法。
【請求項２６】
少なくとも１つの記憶された乗換パターンを検索する前記ステップは、
乗換パターンサフィックスに関連付けられた駅に先行する駅の連なりのペアを示す１以上の該乗換パターンサフィックスを検索するステップと、
前記少なくとも１つの記憶された乗換パターンを生成するために、前記１以上の乗換パターンサフィックスを連結するステップ
を備えることを特徴とする請求項２１に記載の方法。
【請求項２７】
前記トランジット駅の賢明な組み合わせのペア毎の少なくとも１つの記憶された乗換パターンを、該少なくとも１つの記憶された乗換パターンにより表された順番で、弧によって連結されたノードのシークエンスとして表すクエリグラフを生成するステップを更に備えることを特徴とする請求項２１に記載の方法。
【請求項２８】
特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定する前記ステップは、
前記クエリグラフ内の各ノードを、駅ノードに関連付けられた駅で乗車できるトランジット車両を表す該駅ノード、及び、乗車ノードに関連付けられた駅にトランジット車両が到着している間、乗車されたままであるトランジット車両を表す該乗車ノードとして表すことにより、クエリグラフを拡張するステップと、
前記起点駅から各後続駅への１以上の直通接続ルートを決定するステップであって、直通接続ルートは、前記起点駅から１つの後続駅へのルートと、前記少なくとも１つの記憶された乗換パターンに関連付けられた前記起点駅と前記後続駅の間の中間トランジット駅での停車スケジュールとを表すものと、
前記１以上の直通接続ルート毎に、前記拡張されたクエリグラフ内のノードの連なりを、前記直通接続ルートを表す弧により連結するステップであり、前記ノードの連なりはそれぞれ、前記少なくとも１つの記憶された乗換パターンに関連付けられた駅を表すものと
を備えることを特徴とする請求項２７に記載の方法。
【請求項２９】
前記起点駅から少なくとも１つの後続駅への１以上の直通接続を決定するステップと、
前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続を決定するステップと、
前記起点駅から前記目的駅へのルートを形成するために、前記起点駅から少なくとも１つの後続駅への１以上の直通接続を、前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続に連結するステップと、
前記拡張されたクエリグラフ内のノードの連なりを、前記形成されたルートを表す弧により連結するステップと
を備えることを特徴とする請求項２８に記載の方法。
【請求項３０】
特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定する前記ステップは、
多次元のコストに基づいて前記起点駅から前記目的駅への前記少なくとも１つの最適ルートを決定するために、前記拡張されたクエリグラフにパレート‐ダイクストラ計算を適用することにより、前記少なくとも１つの最適ルートを計算するステップであって、前記多次元のコストは駅ペアの間の時間長とペナルティを含むもの、を備えることを特徴とする請求項２８に記載の方法。
【請求項３１】
前記ペナルティは、金銭的コスト、前記起点駅から前記目的駅に到達するために必要なトランジット車両の乗換数、及び、徒歩コストの少なくとも一部に基づくものであることを特徴とする請求項１に記載の方法。
【請求項３２】
特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定する前記ステップは、
１次元のコストに基づいて前記起点駅から前記目的駅への前記少なくとも１つの最適ルートを決定するために、前記拡張されたクエリグラフにダイクストラ計算を適用することにより、前記少なくとも１つの最適ルートを計算するステップであって、前記１次元のコストは、前記起点駅から前記目的駅へのトリップを完遂するために要する総時間、前記起点駅から前記目的駅に到達するために要する乗換数、又は、金銭的コストのいずれか１つを含むものである
ことを特徴とする請求項２８に記載の方法。
【請求項３３】
特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定する前記ステップは、前記少なくとも１つの最適ルートを決定するために目標指向検索を適用することを含み、前記目標指向検索はＡ＊探索アルゴリズムであることを特徴とする請求項２８に記載の方法。
【請求項３４】
トランジット駅間の最適公共交通機関乗換パターンを計算するために、コンピュータプロセッサに、
それぞれ起点駅と目的駅を示す記憶された公共トランジットトリップ毎に、その起点駅から目的駅までの公共トランジットトリップの間のトランジット車両によるトランジット駅での１以上の停車のスケジュールを表す記憶されたトランジットルートを検索するステップと、
記憶された公共トランジットトリップ毎の前記検索されたルートを、複数の弧により連結された複数のノードのシークエンスとして表すことにより、トランジットグラフを生成するステップであって、前記トランジットグラフ内の各ノードが、前記トランジットトリップに関連付けられたトランジット車両によりトランジット駅で行われるイベントを表すものと、
前記トランジットグラフ内に表されたトランジット駅のペア毎に、
前記トランジットグラフ内の駅のペアの間のトランジット駅での１以上の乗換についての最適トランジットルートを表す少なくとも１つの最適乗換パターンを、前記トランジットグラフから計算するステップと、
トランジット駅のペア毎の前記少なくとも１つの最適乗換パターンを記憶するステップと
を実行させることを特徴とするプログラム。
【請求項３５】
前記コンピュータプロセッサに、更に、前記トランジットグラフのどの駅がグローバル駅を表しているかを決定するステップを実行させるプログラムであって、前記グローバル駅は長距離トリップの間に頻繁にトランジット車両の乗換が行われる駅であることを特徴とする請求項３４に記載のプログラム。
【請求項３６】
前記トランジットグラフのどの駅がグローバル駅を表しているかを決定する前記ステップは、前記コンピュータプロセッサに、
前記トランジットグラフ内の駅毎に、その駅で行われるトランジット車両の乗換数を決定するステップであって、前記トランジット車両の乗換は、駅で人が降車する第１トランジット車両と、駅に居り人が乗車する第２トランジット車両とを表すものと、
各駅で行われる前記トランジット車両の乗換数の少なくとも一部に基づいてグローバル駅を選択するステップと
を実行させることを特徴する請求項３５に記載のプログラム。
【請求項３７】
前記トランジットグラフのどの駅がグローバル駅を表しているかを決定する前記ステップは、前記コンピュータプロセッサに、
前記トランジットグラフ内の駅毎に、その駅に関連付けられたノードの駅ノードグループを形成するために、該駅で乗車されるトランジット車両を表すノードをグループ化し、且つ、その駅に関連付けられたノードの乗車ノードグループを形成するために、前記トランジットグラフ内で同じ後続駅のシークエンスを持つ、異なるルートに関連付けられたノードをグループ化するステップと、
前記トランジットグラフ内の駅のペア毎に、その駅のペアに関連付けられたノードのペアの少なくとも一方が該トランジットグラフ内の弧によって連結されているかを決定するステップと、
前記ノードのグループのペア毎に、トランジットグラフ内で弧によって連結されている駅のペアに関連付けられたノードの少なくとも１ペアに応答して前記駅のペアに関連付けられたノードのグループのペアの間に弧を追加するステップと、
前記ノードのグループのペア間の弧毎に、前記ノードのグループのペアに属するノードのペアに関連付けられた最小コストの少なくとも一部に基づくコストを割り当てるステップであって、前記ノードのペアはトランジットグラフ内で弧によって連結されたものと、
前記コストに基づいて複数の前記駅ノードグループから最適経路を決定するステップと、
前記最適経路を示す駅ノードグループ毎に、前記最適経路内でその駅ノードグループに先行する駅ノードグループの数に基づいてスコアを決定するステップと、
各駅ノードグループ毎の前記スコアの少なくとも一部に基づいてグローバル駅を決定するステップと
を実行させることを特徴する請求項３５に記載のプログラム。
【請求項３８】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、前記コンピュータプロセッサに、
起点駅と目的駅を示す駅の賢明な組み合わせの可能なペア毎に、前記トランジットグラフ内の起点駅に関連付けられたノードを目的駅と関連付けられたノードに連結するトリップのセットを決定するステップであって、前記セット内の各トリップは、そのトリップの間にトランジット車両によりなされる停車を表す同じノードのシークエンスを含むものと、
前記トリップのセットを記憶するステップと
を実行させることを特徴とする請求項３４に記載のプログラム。
【請求項３９】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、前記コンピュータプロセッサに、
起点駅と目的駅を示す駅の賢明な組み合わせの可能なペア毎に、前記起点駅の駅ノードをゼロコスト値に初期化するステップと、
前記トランジットグラフ内の最適ルートを決定するために、前記起点駅内の各駅ノードから前記目的駅内の各ノードまで多次元のコストに基づくパレート-ダイクストラ検索を行うステップであって、最適ルートの各ノードは時間長及びペナルティに関するコストを特定するラベルセットを含み、
前記ノード毎に、支配的ラベルを取り除くために前記ラベルセットをフィルタするステップであって、ｄ１がｄ２よりも小さく、ｐ１がｐ２よりも小さいことに応答して第１のラベル（ｄ１，ｐ１）が第２のラベル（ｄ２，ｐ２）より支配的であるものと、
前記フィルタされたラベルセットに基づいて最適経路を決定するステップと、
前記最適経路毎の乗換パターンのフィルタされたラベルセットに関連付けられた駅の順序に基づいて、前記最適経路毎の乗換パターンを決定するステップと
を実行させることを特徴とする請求項３４に記載のプログラム。
【請求項４０】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、前記コンピュータプロセッサに、
前記トランジットグラフ内のグローバル駅毎に、前記トランジットグラフ内の前記グローバル駅に関連付けられた全てのノードから該グローバル駅から到達できる各他のノードへの最適経路を決定するステップと、
前記最適経路毎に、該最適経路の乗換パターンを決定するステップと
を実行させることを特徴とする請求項３５に記載のプログラム。
【請求項４１】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、前記コンピュータプロセッサに、
起点駅と目的駅を示す前記トランジットグラフ内の駅の賢明な組み合わせの可能なペア毎に、前記起点駅に関連付けられた各ノードから前記目的駅に関連付けられた各ノードへの最適経路を決定するステップと、
前記最適経路毎に、その最適経路に関連付けられたコストを決定するステップであって、前記コストは時間及びペナルティの関数であるものと、
前記コストの少なくとも一部に基づいて、前記最適経路から支配的経路を決定するステップであって、前記支配的経路は最小のコストを持つ最適経路であるものと、
前記支配的経路に関連付けられた乗換パターンを決定するステップと
を実行させることを特徴とする請求項３４に記載のプログラム。
【請求項４２】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、前記コンピュータプロセッサに、
前記トランジットグラフ内の非グローバル駅のノードからグローバル駅のノードへの経路を決定するステップであって、前記経路はそれぞれ前記グローバル駅に到達するための経路中で中間駅でのみ最大数のトランジット車両の乗換が行われるものと、
前記決定された経路毎に、前記経路に関連付けられた乗換パターンを決定するステップと
を実行させることを特徴とする請求項３５に記載のプログラム。
【請求項４３】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、前記コンピュータプロセッサに、
前記トランジットグラフ内の非グローバル駅のノードからグローバル駅のノードへの経路を決定するステップであって、前記グローバル駅のノードは前記グローバル駅のノードに関連付けられた駅で乗車されたままでいるトランジット車両を表すものと、
前記決定された経路毎に、前記経路に関連付けられた乗換パターンを決定するステップと
を実行させることを特徴とする請求項３５に記載のプログラム。
【請求項４４】
前記トランジットグラフから少なくとも１つの最適乗換パターンを計算する前記ステップは、前記コンピュータプロセッサに、
前記トランジットグラフ内の非グローバル駅のノードからグローバル駅のノードへ出発する最適経路を決定するステップと、
乗換パターンのセットを形成するために、前記最適経路毎に乗換パターンを決定するステップと、
前記セット内の１以上の乗換パターンに含まれる冗長な乗換パターンを取り除くステップと
を実行させることを特徴とする請求項３５に記載のプログラム。
【請求項４５】
トランジット駅のペア毎の前記少なくとも１つの最適乗換パターンを記憶する前記ステップは、前記コンピュータプロセッサに、
前記少なくとも１つの最適乗換パターン内の１以上の駅の繰り返しシークエンスを取り除くステップと、
前記少なくとも１つの最適乗換パターンを、取り除かれた１以上の駅の繰り返しシークエンスに応答する１以上の乗換パターンサフィックスに区分するステップであって、前記乗換パターンサフィックスのそれぞれは前記少なくとも１つの最適乗換パターン内の乗換パターンサフィックスに関連付けられた駅に先行する駅の連なりのペアを示すものと、
前記１以上の乗換パターンサフィックスを記憶するステップと
を実行させることを特徴とする請求項３４に記載のプログラム。
【請求項４６】
出発地点から目的地点へのジャーニーの公共トランジット経路を決定するために、コンピュータプロセッサに、
出発地点から目的地点への公共トランジット経路の要求をクライアント装置から受信するステップと、
前記出発地点のラジアル距離内のトランジット駅を決定し、それにより前記目的地点のラジアル距離内のトランジット駅を含む目的駅リストを生成するステップと、
前記目的地点のラジアル距離内のトランジット駅を決定し、それにより前記出発地点のラジアル距離内のトランジット駅を含む起点駅リストを生成するステップと、
前記起点駅リスト中の起点駅と前記目的駅リスト中の目的駅とを表すトランジット駅の賢明な組み合わせのペア毎に、前記起点駅から前記目的駅へ移動するための前記起点駅及び前記目的駅の間の中間トランジット駅でのトランジット車両の乗換を示す少なくとも１つの記憶された乗換パターンを検索するステップと、
前記検索された乗換パターン毎に、特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定するステップと
を実行させることを特徴とするプログラム。
【請求項４７】
少なくとも１つの記憶された乗換パターンを検索する前記ステップは、前記コンピュータプロセッサに、
乗換パターンサフィックスに関連付けられた駅に先行する駅の連なりのペアを示す１以上の該乗換パターンサフィックスを検索するステップと、
前記少なくとも１つの記憶された乗換パターンを生成するために、前記１以上の乗換パターンサフィックスを連結するステップ
を実行させることを特徴とする請求項４６に記載のプログラム。
【請求項４８】
前記コンピュータプロセッサに、更に、前記トランジット駅の賢明な組み合わせのペア毎の少なくとも１つの記憶された乗換パターンを、該少なくとも１つの記憶された乗換パターンにより表された順番で、弧によって連結されたノードのシークエンスとして表すクエリグラフを生成するステップを実行させることを特徴とする請求項４６に記載のプログラム。
【請求項４９】
特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定する前記ステップは、前記コンピュータプロセッサに、
前記クエリグラフ内の各ノードを、駅ノードに関連付けられた駅で乗車できるトランジット車両を表す該駅ノード、及び、乗車ノードに関連付けられた駅にトランジット車両が到着している間、乗車されたままであるトランジット車両を表す該乗車ノードとして表すことにより、クエリグラフを拡張するステップと、
前記起点駅から各後続駅への１以上の直通接続ルートを決定するステップであって、直通接続ルートは、前記起点駅から１つの後続駅へのルートと、前記少なくとも１つの記憶された乗換パターンに関連付けられた前記起点駅と前記後続駅の間の中間トランジット駅での停車スケジュールとを表すものと、
前記１以上の直通接続ルート毎に、前記拡張されたクエリグラフ内のノードの連なりを、前記直通接続ルートを表す弧により連結するステップであり、前記ノードの連なりはそれぞれ、前記少なくとも１つの記憶された乗換パターンに関連付けられた駅を表すものと
を実行させることを特徴とする請求項４８に記載のプログラム。
【請求項５０】
前記コンピュータプロセッサに、
前記起点駅から少なくとも１つの後続駅への１以上の直通接続を決定するステップと、
前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続を決定するステップと、
前記起点駅から前記目的駅へのルートを形成するために、前記起点駅から少なくとも１つの後続駅への１以上の直通接続を、前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続に連結するステップと、
前記拡張されたクエリグラフ内のノードの連なりを、前記形成されたルートを表す弧により連結するステップと
を実行させることを特徴とする請求項４６に記載のプログラム。
【請求項５１】
特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定する前記ステップは、前記コンピュータプロセッサに、
多次元のコストに基づいて前記起点駅から前記目的駅への前記少なくとも１つの最適ルートを決定するために、前記拡張されたクエリグラフにパレート‐ダイクストラ計算を適用することにより、前記少なくとも１つの最適ルートを計算するステップであって、前記多次元のコストは駅ペアの間の時間長とペナルティを含むもの、を実行させることを特徴とする請求項４６に記載のプログラム。
【請求項５２】
トランジット駅間の最適公共交通機関乗換パターンを計算するためのコンピュータシステムにおいて、前記システムは、
コンピュータプロセッサと、
前記コンピュータプロセッサに実行されるよう構成されたコンピュータプログラムモジュールを記憶するコンピュータ読み取り可能な記憶媒体とを備え、
前記コンピュータプログラムモジュールが、
それぞれ起点駅と目的駅を示す記憶された公共トランジットトリップ毎に、その起点駅から目的駅までの公共トランジットトリップの間のトランジット車両によるトランジット駅での１以上の停車のスケジュールを表す記憶されたトランジットルートを検索し、
記憶された公共トランジットトリップ毎の前記検索されたルートを、複数の弧により連結された複数のノードのシークエンスとして表すことにより、トランジットグラフを生成する、ここで前記トランジットグラフ内の各ノードが前記トランジットトリップに関連付けられたトランジット車両によりトランジット駅で行われるイベントを表す、ように構成されたトランジットグラフモジュールと、
前記トランジットグラフ内に表されたトランジット駅のペア毎に、前記トランジットグラフ内の駅のペアの間のトランジット駅での１以上の乗換についての最適トランジットルートを表す少なくとも１つの最適乗換パターンを、前記トランジットグラフから計算し、
トランジット駅のペア毎の前記少なくとも１つの最適乗換パターンを記憶するように構成された乗換パターン計算モジュールと
を備えることを特徴とするコンピュータシステム。
【請求項５３】
出発地点から目的地点へのジャーニーの公共トランジット経路を決定するためのコンピュータシステムにおいて、前記システムは、
コンピュータプロセッサと、
前記コンピュータプロセッサに実行されるよう構成されたコンピュータプログラムモジュールを記憶するコンピュータ読み取り可能な記憶媒体とを備え、
前記コンピュータプログラムモジュールが、
出発地点から目的地点への公共トランジット経路の要求をクライアント装置から受信し、
前記出発地点のラジアル距離内のトランジット駅を決定し、それにより前記目的地点のラジアル距離内のトランジット駅を含む目的駅リストを生成し、
前記目的地点のラジアル距離内のトランジット駅を決定し、それにより前記出発地点のラジアル距離内のトランジット駅を含む起点駅リストを生成するように構成されたローカル駅決定モジュールと、
前記起点駅リスト中の起点駅と前記目的駅リスト中の目的駅とを表すトランジット駅の賢明な組み合わせのペア毎に、前記起点駅から前記目的駅へ移動するための前記起点駅及び前記目的駅の間の中間トランジット駅でのトランジット車両の乗換を示す少なくとも１つの記憶された乗換パターンを検索するように構成された乗換パターン構築モジュールと、
前記検索された乗換パターン毎に、特定時刻での前記乗換パターンの実体化である前記起点駅から前記目的駅への少なくとも１つの最適ルートを決定するように構成されたクエリグラフ分析モジュールと、
前記少なくとも１つの最適ルートを示す情報を前記クライアント装置に伝送するように構成されたトリップ供給モジュールと
を備えることを特徴とするシステム。

【図１】

【図２】

【図３】

【図４】

【図５Ａ】

【図５Ｂ】

【図６】

【図７】

【図８】

【図９】

【図１０Ａ】

【図１０Ｂ】

【図１０Ｃ】

【図１０Ｄ】

【図１０Ｅ】

【図１０Ｆ】

【図１１】

【図１２】

【図１３】

【図１４】

【図１５】

【図１６】

【図１７】

【図１８】

【図１９】

【公表番号】特表２０１３−５１１０９５（Ｐ２０１３−５１１０９５Ａ）
【公表日】平成２５年３月２８日（２０１３．３．２８）
【国際特許分類】
【出願番号】特願２０１２−５３８９６５（Ｐ２０１２−５３８９６５）
【出願日】平成２２年１１月１１日（２０１０．１１．１１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０５６３１６
【国際公開番号】ＷＯ２０１１／０６０１２２
【国際公開日】平成２３年５月１９日（２０１１．５．１９）
【出願人】（５０５２８１０６７）グーグル　インコーポレイテッド (58)
【氏名又は名称原語表記】ＧＯＯＧＬＥ　ＩＮＣ．
【Ｆターム（参考）】