JP7618130B2 - ソース場所からターゲット場所への移動に対しルートまたはルート所要時間を提供する方法およびコンピュータシステム - Google Patents

Description

（関連出願への相互参照）
本出願は、下記の出願に基づくものであり、下記出願の優先日を主張する。
米国、出願番号６２／６０８５８６、提出日２０１７年１２月２１日
米国、出願番号６２／６１３７７９、提出日２０１８年０１月０５日
米国、出願番号６２／６５９１５７、提出日２０１８年０４月１８日
韓国、出願番号１０－２０１８－００４５５５８、提出日２０１８年４月１９日
米国、出願番号１６／１８００５０、提出日２０１８年１１月０５日
これらは参照により本明細書に組み込まれる。

本発明は、大都市圏におけるルート計画に関する。ルート計画の目的は、さまざまな輸送サービス提供者からの利用可能な車両を用いて、ある場所(location)から別の場所に移動する方法を決定することである。多くの場合、他の要件の中でも、とりわけ、移動の時間をできるだけ短くするか、特定の時間に出発することが要求される。ルート(route)は、通常、徒歩経路や乗車経路などを含む乗客(rider)への指示を指定する。

実施形態は、ルートを計算する方法、この方法を実装および実行するコンピュータシステム、およびユーザがルート決めクエリを発行し、応答としてルートを受け取ることを可能にするコンピュータサービス製品を含む。

本発明の一実施形態によれば、ルート計画を生成する方法が提供される。この方法は、ルートのソース(source)場所とターゲット(target)場所という形式のクエリ、および出発時刻(departure time)または到着期限(arrival deadline)を含む他の要件を受け取る。この方法は、車両の統計的特性をモデル化するグラフを作成する。その特徴の１つに、車両と徒歩のさまざまな選択肢のいずれかを用いてある場所から他の場所への移動をモデル化する「見込エッジ」がある。一実施形態において、そのエッジは、２つの場所の間の予想される最小移動所要時間(travel duration)をモデル化する。グラフ、またはクエリの詳細に依存するその拡張を用いて、その方法は、クエリへの応答としてルート計画を生成する。

本発明の一実施形態によれば、ルート計画を生成するためのコンピュータシステムが提供される。そのシステムは、ハードウェアとソフトウェアの組み合わせである。それは、場所間の交通システムと徒歩に関する情報を、複数のデータ提供者から取得する。システムは、輸送システムをモデル化する複数のグラフを作成し、ルート計画を生成するためにグラフ内の最短経路を計算する。

本発明の一実施形態によれば、ルート計画を生成するためのコンピュータサービス製品が提供される。このサービスにより、ユーザはスマートフォンなどのデバイスのユーザインターフェイスを介してクエリを指定し、生成されたルート計画をデバイスに表示できる。

ここに提示される本発明の実施形態は、例示目的のためのものであって、これらは網羅的なものではない。実施形態の範囲および精神から逸脱することなく、多くの修正および変形が当業者には明らかであろう。

本発明で開示されるデータ検索、処理操作などは、コンピュータシステムまたはサービスとして実装され、精神的なステップまたは具体化されない抽象的なアイデアとしては実装されない。

プレゼンテーションでは、「第１」、「第２」、「前記／その」などの用語は、限定的な意味では使用されないが、文脈からそうでないことが明確でない限り、区別する目的で使用される。文脈から明確でない限り、単数形の表現には複数形が含まれる。

本発明に含まれる図面は、本発明の実施形態の様々な特徴および利点を例示している。
図１は、本発明の一実施形態に係るグラフＧ０を示す。 図２は、本発明の一実施形態に係るグラフＧ０を構築するための処理流れを示す。 図３は、本発明の一実施形態に係る、徒歩、待ち、バス乗車、および徒歩を含む、ｃからｃ’への移動を示す。 図４は、本発明の一実施形態に係る、１つのバス路線であるが２つの移動方法を含む、ｃからｃ’への移動を示す。 図５は、本発明の実施形態に係る、それぞれがｃからｃ’への別個の移動方法を提供する２つのバス路線を示す。 図６は、本発明の一実施形態に係る、徒歩、待ち、地下鉄乗車、および徒歩を含む、ｃからｃ’への移動を示す。 図７は、本発明の一実施形態に係る、ｃからｃ’への移動の３つの選択肢の見込エッジを示す。 図８は、本発明の一実施形態に係る、乗客のｃへの到着時間を条件とする所要時間ランダム変数が与えられた場合の、ｃからｃ’への移動の２つの選択肢の見込エッジを示す。 図９は、本発明の一実施形態に係る待ち所要時間および固定移動所要時間の区間モデルの下で見込エッジを計算するための擬似コードを示す。 図１０は、本発明の一実施形態に係る、クエリにおけるソースが既知である場合に、グラフＧ１が、ソースからのエッジを持つグラフＧ０をどのように拡張するかを示す。 図１１は、本発明の一実施形態に係る、クエリにおけるターゲットが既知である場合に、グラフＧ２が、ターゲットへの見込エッジを持つグラフＧ０をどのように拡張するかを示す。 図１２は、本発明の実施形態に係る、クエリ時にターゲットが明らかにされた場合に、最後から２番目の停留所／駅から続く見込移動の選択肢を計算する例を示す。 図１３は、本発明の一実施形態に係る、ルート決めクエリに応答するためのコンピュータシステムの処理流れを示す。 図１４は、本発明の一実施形態に係る、ユーザのスマートフォン上のサービス製品によるクエリに応答するルートの表示の一例を示す。

発明の詳細な説明

（４ 詳細な説明）
首都圏交通システムは、地下鉄(subway)やバス(bus)などの車両で構成されている。乗客の一般的な目的は、特定の場所から首都圏内の他の場所への最速ルートを決定することである。ルートは、オンラインのマッピングサービスの主要提供者で見られるように、車両の時刻表、および希望する出発時刻または到着期限を用いて計算できる。ただし、実際には、一部の車両は、例えば交通事情により、時刻表に正確に従っていない。従来技術とは対照的に、本発明は、時刻表に追従する車両と追従しない車両とを混ぜて用いて、ルートを計算する方法を示す。本発明は、ルートの類似性と待ち所要時間を用いて、ルート決定結果を改善する。

簡単な例で、改善点を説明する。バスのルートに沿って２つの連続したバス停ｂ_１，ｂ_２を検討する。乗車時間は平均２０分である。さらに、バスが平均２４分ごとにｂ_１に到着するものとする。ランダムな時間にｂ_１に到着した乗客の場合、ｂ_２への平均移動所要時間は３２分（待ち＋乗車）である。ここで、これら２つのバス停間で運行される他のバスがあると仮定する。同じタイミングの仮定の下で、バスの独立性を仮定すると、平均移動所要時間は４分短くなる。通常、バスがｎ個ある場合、平均は２０＋２４／（ｎ＋１）分である。これは単に、乗客が最初にｂ_１に到着したバスに乗車できることによる。

ただし、自然の大都市は単純な図式よりも複雑であり、異なる到着パターンと速度パターンを有する車両による、ルートの洗練された重複パターンがある。乗客が停車地の間を歩く(walk)可能性があるので、改善を達成するためにルートを重複させることは、厳密に必要ではない。輸送システムは、時間とともに進化する可能性があり、例えば、地下鉄の時刻表が変更されたり、バスの路線が追加されたりする。さらに、大都市圏であっても、コンピュータが多くのルート決めクエリに迅速に応答できるように、ルートを計算する効率的な方法が必要である。

（４．１ モデル概要）
ルートまたはルート所要時間(route duration)を計算するための輸送システムのモデルを導入する。

輸送システムは２種類の車両で構成されていると仮定する。（１）固定時刻表(fixed timetables)に従い、例えば平日のスケジュールに従って１日の所定の時間に出発および到着する車両。この車両を地下鉄と呼び、その駅を地下鉄駅と呼ぶ。（２）出発時刻と到着時刻が固定されていない車両。この車両をバスと呼び、その停留所をバス停と呼ぶ。地下鉄駅とバス停は、両方とも固定された地理的な場所を有しているので、それらの間の徒歩を決定できる。バスは、バス路線にグループ化される。バス路線のバスは、通常バス路線のターミナルバス停まで、バス停の固定された順序に沿って運行される。

実際には、一部のバスは非常に正確に到着する可能性があり、これはモデルに準拠していないように見える場合がある。例えば、固定時刻表に従ってバス路線の最初のバス停を出たバスを考える。バスは、予測できない交通量の大都市圏に到達するまでは、最初のいくつか停留所に時間通りに到着するかも知れない。乗客が地下鉄に乗った後、これらの最初のバス停留所のいずれかに到着する場合、バスの待ち所要時間は予測可能であり、地下鉄－徒歩－バス移動所要時間の合計も予測可能である。この複数車両の地下鉄－徒歩－バス移動を表すために、地下鉄を概念的に追加して、このケースをモデル化できる。同様に、運行が同期されているか非常に時間厳守である場合、バス－徒歩－地下鉄、バス－徒歩－バス、および地下鉄－徒歩－地下鉄、および他の組み合わせ、を概念化できる。本発明の以下の説明では、開示の提示を単純化するために、固定時刻表地下鉄と非固定時刻表(non-fixed timetable)バスの仮定を維持する。

本方法は、バスまたは地下鉄によって人のルート決めをすることに限定されない。対照的に、本方法はより一般的である。それは、実際に発生する多種類の車両を確保する。例えば、それらには、地下鉄、バス、路面電車、電車、タクシー、共有バン、車、自動運転車、フェリー船、飛行機、配達用バイク、貨物自動車、またはコンテナトラックが含まれる。本方法で作成されるルートは、あらゆる対象物のルート決定に用いることができる。例えば、それらには、人、貨物、小包、手紙、または食料品が含まれる。この対象物は、乗客(rider)とも呼ばれる。

輸送システムは、それぞれが頂点(vertices)とエッジ(edges)で構成される有向グラフ(directed graphs)の集りによってモデル化される。各頂点は、バス停、地下鉄駅、または補助要素を表す。頂点で表される他の例には、駅、タクシー乗り場、共有バンの乗車または下車場所、駐車場、自動運転車の乗車または下車場所、プラットフォーム、階層、港、フェリーまたはエアターミナル、空港、または荷積みドックが含まれる。エッジは、待ち、ある場所から別の場所への移動、または補助要素を表する。一実施形態において、エッジは、待ちまたは移動の所要時間を示す重みを有する。他の実施形態において、重みはランダム変数(random variables)である。他の実施形態において、いくつかのランダム変数は、例えば、とりわけ、１日の時刻、休日／非休日の種別に条件付け(conditioned)られる。他の実施形態において、いくつかのランダム変数は他のランダム変数と相関して(correlated)いてもよい。

一実施形態において、履歴データからランダム変数の確率分布(probability distribution)を決定する。例えば、特定のバス路線のバスが特定のバス停ｂ_１から特定のバス停ｂ_２に移動するのにかかった時間を、１か月間測定し、この１か月のサンプルから、移動所要時間の経験的分布を決定する。他の例では、特定のバス停において特定のバス路線のバスの到着または出発時間を一定期間にわたって測定し、そのバス路線のバスの待ち時間の経験的分布を、平日の分刻みで決定する。他の例では、バスオペレータによって報告される通過間隔を用いて、平均待ち時間を決定する。他の例では、バスの現在場所が、バスの待ち所要時間のより正確な分布を計算するために用いられる。

この方法で使用されるランダム変数のいくつかは自明ではない(non-trivial)。自明なランダム変数には、確率１の値が１つだけある。その他のランダム変数は自明ではない。

グラフの目的は、クエリに応答して２つの地理的な場所間のルートまたはルート所要時間を見つけるのを、支援することである。ルートの開始点はソースと呼ばれ、終了点はターゲットと呼ばれる。場所は、ルート決めシステムのアプリケーションによって決定される。例えば、場所は、営利企業、バスと地下鉄の駅自体、公園内の任意のポイント、または全地球測位システムによって決定される人の現在の場所である。一実施形態において、ダイクストラの最短経路アルゴリズムまたはＡ^＊（Ａスター）探索アルゴリズムをグラフに適用して、または後述するこれらのアルゴリズムのいくつかの翻案によって、ルートを探索する。

一部の実施形態において、ルートに制限を追加する。例えば、これらには、車両種別、車両停留所種別、車両乗り換え回数のしきい値(threshold)、待ち所要時間のしきい値、徒歩所要時間のしきい値、特定の車両にのみ適合してルートが設定される対象物の種別、移動の金銭的費用のしきい値、ソースからの出発時間、ターゲットへの到着時間、または期限前に到着する望ましい確率が含まれる。

一実施形態において、本方法は、最小の予想所要時間を有するルートまたはルート所要時間を計算する。ただし、本方法はより一般的である。また、ほぼ最速の、または最速ではないかも知れない、ルートまたはルート所要時間を計算するが、これは特定の期限後に到着するリスクを制限する。

本発明は、ルート決めクエリに応答するため、いくつかのグラフを構築する。いくつかの実施形態は、クエリに基づき、追加の頂点およびエッジを用いてグラフを拡張する。

（４．２ グラフＧ０）
Ｇ０と呼ばれるグラフは、バス停と地下鉄駅と間のルート決めを表す。その構造の詳細な説明は次のとおりである。グラフＧ０の説明は図１にあり、その構造の処理流れの説明は図２にある。

（４．２．１ 固定時刻表）
頂点とエッジの１番目のグループは、固定時刻表に従う車両によるルート決めを表す。時刻表が固定されているので、既知のアルゴリズムを用いて、２つの場所間の最速ルートを計算でき、それは間に徒歩を有する複数車両の連続を含み得る。そこで、ソースからターゲットへのこの複数車両の移動を抽象化するため、単一のエッジを用いる。

頂点を追加し、乗客が地下鉄の出発に合わせて駅への到着を時間指定されているかのように待ちなしで搭乗する地下鉄を、モデル化する。各地下鉄駅ｓに、次の２つの頂点を導入する、
ＳＵＢＷＡＹ＿ＦＲＯＭ＿ｓ、
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ。
任意の２つの異なる駅ｓ，ｓ’は、次のエッジを有する。
ＳＵＢＷＡＹ＿ＦＲＯＭ＿ｓ→ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ’
これは、ｓからｓ’への乗車所要時間を表し、地下鉄の乗り換えと徒歩を含むことができ（例えば、駅ｓから、まず地下鉄Ａに乗って駅Ｂに行き、次に駅Ｃに歩いてから、地下鉄Ｄに乗って駅ｓ’に行く）、このエッジは、ＲｉｄｅＭａｎｙＧｅｔＯｆｆ（多乗車下車）とラベル付けされる。一実施形態において、エッジの重みは、平日の朝のラッシュ時の最小乗車所要時間である。他の実施形態において、多くの時間窓のそれぞれにランダム変数を用いる。他の実施形態において、ランダム変数は、ｓの場所への乗客の到着時間、またはｓの場所からの出発時間を条件とする。

乗客が移動中に地下鉄の駅に到着して地下鉄を待つ必要がある場合のイベントをモデル化する。任意の２つの異なる駅ｓ’とｓ”に対し、ｓ’からｓ”への乗車を意味する次の頂点を追加する、
ＳＵＢＷＡＹ＿ＦＲＯＭ＿ＴＯ＿ｓ’＿ｓ”。
次のエッジがあり、ＷａｉｔＧｅｔＯｎ（乗車待ち）とラベル付けされ、ｓ’からｓ”への移動に地下鉄に乗るための待ち所要時間を表す。
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ’
→ＳＵＢＷＡＹ＿ＦＲＯＭ＿ＴＯ＿ｓ’＿ｓ”。
一実施形態において、エッジの重みは、平日の朝のラッシュ時のランダムな時間にｓ’に到着する乗客に対し、乗客を最も早くｓ”に輸送する地下鉄の平均待ち時間に設定される。他の実施形態において、重みは、ｓ’からｓ”までの地下鉄の平均到着時間の半分に設定される。他の実施形態において、多くの時間窓のそれぞれにランダム変数を用いる。他の実施形態において、そのランダム変数は、ｓ’の場所における乗客の到着時間または出発時間の分布を条件とする。

次のエッジが追加され、
ＳＵＢＷＡＹ＿ＦＲＯＭ＿ＴＯ＿ｓ’＿ｓ”
→ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ”、
ＲｉｄｅＭａｎｙＧｅｔＯｆｆ（多乗車下車）とラベル付けされ、ｓ’からｓ”への乗車所要時間を表し、地下鉄の乗り換えと徒歩を含むことができる、一実施形態において、エッジの重みは、平日の朝のラッシュ時の平均最短乗車所要時間に設定される。他の実施形態において、ランダム変数を用いる。他の実施形態において、そのランダム変数は、ｓ’の場所における乗客の到着時間、またはｓ’の場所からの出発時間を条件とする。

（４．２．２ 非固定時刻表）
頂点とエッジの２番目のグループは、固定時刻表に従わない車両によるルート決めを表す。

全てのバス路線について、バス停と、バス停におけるバスとをモデル化する頂点を追加する。前者はバス外の乗客を抽象化し、後者はバス内の乗客を抽象化する。ｂ_１，．．，ｂ_ｎを、バス路線ｅに沿ったｎ個の連続したバス停（オンデマンド停留所を含む）とする。次の頂点を、各ｋ、１≦ｋ≦ｎについて、追加する、
ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ
および
ＢＵＳ＿ＡＴ＿ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ＿ｋ＿ｅ。
２つのバス路線は、バス停を共有できる。次のエッジがあり、このバス停でバスを降りることを示すＧｅｔＯｆｆ（下車）とラベル付けされ、このエッジの重みはゼロである、
ＢＵＳ＿ＡＴ＿ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ＿ｋ＿ｅ→ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ。
逆向きのエッジがあり、乗車する前にバス停ｂ_ｋでバス路線ｅのバスを待っている所要時間を表すＷａｉｔＧｅｔＯｎ（乗車待ち）とラベル付けられている、
ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ→ＢＵＳ＿ＡＴ＿ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ＿ｋ＿ｅ。
一実施形態において、エッジの重みは、平日の朝のラッシュ時のバス路線ｅのバスの平均到着時間の半分に設定され、これはそのバス路線の全てのバス停で同じである。他の実施形態において、多くの時間窓およびバス停のそれぞれにランダム変数を用いる。他の実施形態において、ランダム変数は、ｂ_ｋの場所への乗客の到着時間、または到着時間の分布を条件とする。

同じバスでの移動をモデル化するため、次のエッジが追加され、ＲｉｄｅＳａｍｅ（同様乗車）とラベル付けされて、バス停ｂ_ｋから次のバス停ｂ_ｋ＋１までの乗車の所要時間を表す、
ＢＵＳ＿ＡＴ＿ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ＿ｋ＿ｅ
→ＢＵＳ＿ＡＴ＿ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ＋１＿ｋ＋ｌ＿ｅ。
一実施形態において、エッジの重みは、平日の朝のラッシュ時のこれらのバス停の間の平均乗車所要時間に設定される。他の実施形態において、多くの時間窓およびバス停のそれぞれにランダム変数を用いる。他の実施形態において、ランダム変数は、ｂ_ｋの場所へのバスの到着時間、またはｂ_ｋの場所からの出発時間を条件とする。

（４．２．３ 徒歩）
徒歩を用いて、バス停と地下鉄駅の頂点を接続する。

本発明の開示のこのセクションおよび他のセクションでは、徒歩に関するさまざまな要件を許容する。一実施形態において、特定の速度４ｋｍ／ｈでの最短所要時間の徒歩を用いる。他の実施形態において、重みは速度６ｋｍ／ｈを含む、階段を避ける、暗い道を避けるなど、いくつかの徒歩経路要件のそれぞれに対するランダム変数である。他の実施形態において、最大でも時間の固定量、例えば１時間、の所要時間の徒歩のみを許容する。他の実施形態において、徒歩は障害物を無視する直線である。他の実施形態において、徒歩はリフト、移動式通路、エレベータ、またはエスカレータによる移動を含むことができる。

要件が許容されている場合の、任意のｂ，ｂ’，ｓ，ｓ’について、次のエッジが追加される、
ＢＵＳ＿ＳＴＯＰ＿ｂ
→ＢＵＳ＿ＳＴＯＰ＿ｂ’，

ＢＵＳ＿ＳＴＯＰ＿ｂ
→ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ，

ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ
→ＢＵＳ＿ＳＴＯＰ＿ｂ、および

ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ
→ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ’。
各エッジは、Ｗａｌｋ（徒歩）とラベルが付けされ、その重みは徒歩の所要時間を表す。

（４．２．４ 制約）
次に、ルートに沿った最初の待ちでの制約のモデリングを可能にする補助頂点を追加する。一実施形態において、待ちはゼロであり、これは、出発するバス／地下鉄に乗るのに十分に早いが、早すぎることなく、停留所／駅まで歩く乗客をモデル化する。他の実施形態において、待ちは移動の開始時間に依存し、特定の時間に、例えば午前８時に家を出て、移動を開始する乗客をモデル化する。

バスの停留所と地下鉄の駅を地理的な近接度に基づいてクラスタ化する(cluster)。一実施形態において、クラスタ半径を２メートルに固定する。他の実施形態において、ルート決めシステムのユーザが必要とするリソース／品質のトレードオフに応じてクラスタの数を選択する。他の実施形態において、クラスタ半径は０メートルであり、この場合、クラスタはバス停および地下鉄駅の単純な複製である。

各クラスタｃに対して、次の頂点が追加され、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
そして、ｂ_ｋまたはｓがクラスタｃにある場合に、クラスタをバスと地下鉄に接続する次のエッジが追加される、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
→ＢＵＳ＿ＡＴ＿ＢＵＳ＿ＳＴＯＰ＿ｂ_ｋ＿ｋ＿ｅ、および

ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
→ＳＵＢＷＡＹ＿ＦＲ０Ｍ＿ｓ。
エッジは、ＦｉｒｓｔＷａｉｔＧｅｔＯｎ（第１乗車待ち）とラベル付けされる。一実施形態において、エッジの重みは０である。他の実施形態において、エッジの重みは、頂点の場所（バス停ｂ_ｋ、または地下鉄駅ｓ）における乗客の到着時間を条件とする、車両（バスｅ、または地下鉄）の待ち所要時間を示すランダム変数である。他の実施形態において、例えばクラスタ半径が大きい場合、ｃとｂ_ｋまたはｓとの間の徒歩所要時間だけ重みが増加する。

グラフ内の、次の頂点
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
からの任意の自明でない経路は、ＦｉｒｓｔＷａｉｔＧｅｔＯｎ（第１乗車待ち）エッジを丁度１回だけ通る。

他の補助頂点
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ
を追加し、そして、クラスタｃ内の各ｂとｓに、次のエッジが追加される。
ＢＵＳ＿ＳＴＯＰ＿ｂ
→ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ、および

ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ
→ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ。
エッジは、Ｚｅｒｏ（ゼロ）とラベル付けされ、重み０を有する。他の実施形態において、例えばクラスタ半径が大きい場合、徒歩所要時間によって重みが増加する。

次の頂点、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ
の導入は、ルー決めターゲット場所が多数ある場合、グラフのサイズを小さくするのに役立つ。他の実施形態において、必要に応じて、これらの頂点を、
ＢＵＳ＿ＳＴＯＰ＿ｂ、および
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ
からターゲットへの、直接エッジに置き換えることができる。

これまでに作成されたグラフは、どのｃおよびｃ’に対しても、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’、
から、移動の所要時間をモデル化するものであり、最初のバスまたは地下鉄に待たずにまたは所定の待ち時間で乗車し、乗客がバスまたは地下鉄のシーケンスから降りた後、後続の車両乗車には、乗車待ちが必要である。

（４．２．５ 見込エッジ）
次に、いくつかの車両のいずれかを使用することによる移動所要時間の改善を示す補助の頂点とエッジを追加する。改善は、車両の待ち時間の短縮または車両の乗車時間の短縮によってなされ得る。

乗り物に乗るのを待つ所要時間は、乗客がランダムな時間に停留所／駅に到着すると仮定することによってモデル化でき、これは、非固定時刻表を用いる車両の確率的性質による。もし、グラフ経路上に２つの連続したＲｉｄｅＭａｎｙＧｅｔＯｆｆ（多乗車下車）乗車エッジがあれば、エッジを１つのＲｉｄｅＭａｎｙＧｅｔＯｆｆ（多乗車下車）エッジに置き換えることができる。

見込エッジ(prospect edge)を導入する、これは、車両のいくつかの選択肢(choices)の１つを用いて、２つの場所間の移動を抽象化するものである。一実施形態において、エッジの重みは、これらの選択肢の中で予想される最小(expected minimum)移動所要時間の値である。

このセクションにおいて、見込エッジで接続された２つの場所は、車両の停留所の近くにある。ただし、これは本方法を制限するものではない。実際、後のセクションでは、車両の停留所から遠くなる可能性のある任意の場所で終了する見込エッジについて説明する。一般に、見込エッジは、グラフ内の任意の２つの頂点を接続できる。ただし、説明のために、このセクションでは、車両の停留所の近くの見込エッジに焦点を当てる。

上記と同様に、地理的な近接度に基づいてバス停と地下鉄駅をクラスタ化する。２つの異なるクラスタｃ，ｃ’が与えられた場合、徒歩、バス乗車、そして徒歩によるｃからｃ’への移動を考え、２つの徒歩のいずれも長さ０をとることができるものとする。例えば、図３は、ｃから次の頂点
ＢＵＳ＿ＳＴＯＰ＿ｂ、
に向かう徒歩、そこから、ＷａｉｔＧｅｔＯｎ（乗車待ち）、ＲｉｄｅＳａｍｅ（同様乗車）、ＧｅｔＯｆｆ（下車）のエッジを持つバス路線ｅを含んで次の頂点
ＢＵＳ＿ＳＴＯＰ＿ｂ’、
で終わるグラフ経路、を通って、
ＢＵＳ＿ＳＴＯＰ＿ｂ’
からｃ’に至る例を示している。ここで、Ｔをｃからｃ’への移動の所要時間を表すランダム変数とし、徒歩によってｃからｂ、ｂ’からｃ’へと移動し、グラフ経路によってモデル化されたバス乗車でｂからｂ’へと移動するものとする。この変数は、経路に沿ったグラフエッジのランダム変数に、前段と後段の２つの徒歩のランダム変数を加えた合計である。その分布は、構成要素の分布から構築できる。一実施形態において、ランダム変数を、ｃからの出発時間によって条件付ける。

一実施形態において、このランダム変数Ｔは、区間(interval)［ｘ，ｙ］において均一に分布しており、その区間の両端は、
ｘ＝（ｃからｂまでの、最小徒歩所要時間）
＋（経路エッジに沿った予想ＲｉｄｅＳａｍｅ（同様乗車）所要時間の合計）
＋（ｂ’からｃ’までの、最小徒歩所要時間）、および
ｙ＝ｘ＋２・（予想ＷａｉｔＧｅｔＯｎ（乗車待ち）所要時間）、である。
他の実施形態において、両端は、ランダム変数の多数の標準偏差によって調整される。他の実施形態において、ｃからｂ、およびｂ’からｃ’への徒歩所要時間が多くともある固定時間、例えば１時間である場合にのみ、ｃ，ｂ，ｂ’，ｃ’を考慮する。他の実施形態において、徒歩のいずれもゼロ長さ（オプションの徒歩）であってもよい。他の実施形態において、ｃからｂ、またはｂ’からｃ’への最短所要時間徒歩を要求する。他の実施形態において、徒歩はセクション４．２．３におけるような実施形態を有してもよい。他の実施形態において、ランダム変数Ｔは不均一である。他の実施形態において、ランダム変数Ｔはｃの場所への乗客の到着時間を条件とする。

固定バス路線ｅの場合、乗客はそのバス路線のさまざまなバス停で乗降することができ、残りの移動には徒歩を使用できるので、ｃからｃ’への移動には多くの選択肢がある。例えば、図４は、図３を拡張しており、追加の１つの停留所、
ＢＵＳ＿ＳＴＯＰ＿ｂ”
における別の乗車によって、合計乗車所要時間は増加するが、合計徒歩所要時間が減少する。一実施形態において、これらの選択肢の中から、最小の期待値を持つランダム変数Ｔを用いる。これを変数Ｔｃｃ’ｅで示す。これは、バス路線ｅおよび開始と終了のクラスタｃ，ｃ’についての固定ランダム変数である。この変数は、バス路線ｅによって確率的にｃからｃ’に到達するための、最速移動所要時間を示す。一実施形態において、Ｔｃｃ’ｅの候補が間隔で均一に分布している場合、最小期待候補は、その区間の最小中央値を有する候補にすぎない。他の実施形態において、例えば、ピーク時間中にバスをより高い頻度で、そしてより高い道路交通量で確保するために、多くの時間窓のそれぞれに対して１つの変数を用いる。他の実施形態において、ランダム変数は、ｃの場所への乗客の到着時間を条件とする。

乗客のｃからｃ’への移動に役立つ、全てのバス路線ｅ_１，．．，ｅ_ｎを考える。徒歩およびバス停の構成は異なってもよいことに注意。例えば、図５は、２つのバス路線ｅ_１およびｅ_２を示し、それぞれが別個のバス停を用い、異なる徒歩所要時間を有する。前に定義したように、Ｔｃｃ’ｅ_１，．．，Ｔｃｃ’ｅ_ｎを、それぞれの最速移動所要時間のランダム変数とする。

変数の予想される最小(expected minimum)値Ｅ［ｍｉｎ（１≦ｉ≦ｎ）Ｔｃｃ’ｅ_ｉ］を計算することができる。この予想値は、「どのバスが私をそこに、より早く連れて行くか」ということによって、移動所要時間をモデル化する。一実施形態において、異なるバス路線のランダム変数は、独立(independent)である。つまり、どの２つの異なるバス路線ｅ_ｉとｅ_ｊについても、Ｔｃｃ’ｅ_ｉは、Ｔｃｃ’ｅ_ｊから独立である。他の実施形態において、ランダム変数は共通の区間［ｘ，ｙ］において、独立均一である従って、予想される最小値は（ｙ＋ｎｘ）／（ｎ＋１）である。他の実施形態において、予想される最小値のための数式、近似積分、ランダムサンプリング、または他の近似アルゴリズム、または発見的手法を通して、予想値を計算する。近似アルゴリズムを用いると、本方法は、最短ルートが生成されなくなるが、代わりにほぼ最短ルートが生成される。

次に、予想される最小移動所要時間の計算に地下鉄を含める方法を説明する。バスと同様に、Ｔｃｃ’ｓｓ’を、徒歩と地下鉄乗車による、ｃからｃ’までの最速移動所要時間のランダム変数とする。図６に示すように、ｃからｓへの徒歩、グラフ内の経路である
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ
→ＳＵＢＷＡＹ＿ＦＲＯＭ＿ＴＯ＿ｓ＿ｓ’
→ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ’、
および、ｓ’からｃ’までの徒歩がある。この変数の分布は、構成要素の分布から構成できる。一実施形態において、ランダム変数を、ｃからの出発時間に条件付ける。

一実施形態において、Ｔｃｃ’ｓｓ’は、区間［ｘ，ｙ］に均一分布し、その区間の両端は、
ｘ＝（ｃからｓまでの、最小徒歩所要時間）
＋（グラフ経路での予想ＲｉｄｅＭａｎｙＧｅｔＯｆｆ（多乗車下車）所要時間）
＋（ｓ’からｃ’までの、最小徒歩所要時間）、および
ｙ＝ｘ＋２・（グラフ経路での予想ＷａｉｔＧｅｔＯｎ（乗車待ち）所要時間）である。
他の実施形態において、両端は、ランダム変数の多数の標準偏差によって調整される。他の実施形態において、ｃからｓ、およびｓ’からｃ’への徒歩所要時間を、多くともある固定時間、例えば１時間に制限する。他の実施形態において、徒歩のいずれも長さがゼロ（オプションの徒歩）であってもよい。他の実施形態において、ｃからｓへ、またはｓ’からｃ’への最短所要時間徒歩を要求する。他の実施形態において、徒歩はセクション４．２．３におけるような実施形態を有してもよい。他の実施形態において、Ｔｃｃ’ｓｓ’は不均一である。他の実施形態において、Ｔｃｃ’ｓｓ’は、ｃの場所への乗客の到着時間を条件とする。他の実施形態において、多くの時間窓のそれぞれに対して１つの変数を用いる。

複雑さは、地下鉄のランダム変数が固定の地下鉄スケジュールから派生しているため、ランダム変数が二つ一組になって依存するという点において、発生する。これにより、ｃからｃ’までの予想される最小移動所要時間の計算が複雑になる場合がある。

乗客をｃからｃ’に輸送するのに役立つ全ての地下鉄乗車を考え、ｓ_１，ｓ’_１，．．，ｓ_ｍ、ｓ’_ｍを、それぞれランダム変数Ｔｃｃ’ｓ_１ｓ’_１，．．，Ｔｃｃ’ｓ_ｍｓ’_ｍを有する、ｍ個の乗車下車地下鉄駅とする。

一実施形態において、任意の１つの地下鉄ランダム変数は、全てのバス路線ランダム変数と共に、独立している。その場合、バスと地下鉄の予想される最小移動所要時間を予想される複数の最小値の中の最小値として計算し、バスの乗車プールに一度に１つの地下鉄の乗車を追加し、それをＰ（ｃ，ｃ’）として下式のように表す：

Ｐ（ｃ，ｃ’）＝
min Ｅ［min（Ｔｃｃ’ｓ_ｊｓ’_ｊ，Ｔｃｃ’ｅ_１，．．，Ｔｃｃ’ｅ_ｎ］、 （１）
１≦ｊ≦ｍ


Ｐ（ｃ，ｃ’）は見込移動(prospect travel)と呼ばれ、都合の良い複数の交通手段の選択肢を含むｃからｃ’への移動を表す。ここに、（ｍ＋ｎ）個の構成ランダム変数Ｔｃｃ’ｓ_ｊｓ’_ｊ，Ｔｃｃ’ｅ_ｉは、選択肢(choices)と呼ばれる。

一実施形態において、Ｔｃｃ’ｅ_ｉは区間全体で均一であり、Ｔｃｃ’ｓ_ｊｓ’_ｊもそうである。その場合、ある数のＴ_ｉについて予想される最小値Ｅ［ｍｉｎ Ｔ_ｉ］を計算すると、それぞれの区間［ｘ_ｉ，ｙ_ｉ］全体で均一である。

例えば、図７は、下記の３つの選択肢（ｃｈｏｉｃｅｓ）を含む、ｃからｃ’への移動を示す：
・区間［０，９００］で均一な待ちと徒歩＆乗車１７００を有するバス路線ｅ’、
・区間［０，３６００］で均一な待ちと徒歩＆乗車１０００を有するバス路線ｅ”、
・区間［０，３００］で均一な待ちと徒歩＆乗車２２００を有する地下鉄。
この場合、最小の予想される移動所要時間は２１５０＝ｍｉｎ｛２１５０，２８００，２３５０｝であり、「どちらか速い方」による移動の改善を反映していない。ただし、予想される最小値は低くなる：Ｐ（ｃ、ｄ）＝１９３３。

他の例において、図８は、乗客がｃ（見込エッジのソース）に到着する時間を条件とする、確率分布を示す。ｃからｃ’に行くには２つの選択肢があり、１つはバスで、もう１つは地下鉄である。各選択肢には、待ちのため、および徒歩と乗車のための、条件付き確率分布がある。

もし、Ｐ（ｃ，ｃ’）の値が、予想の最小値ｍｉｎ（ｍｉｎ_{（１≦ｊ≦ｍ）}Ｅ［Ｔｃｃ’ｓ_ｊｓ’_ｊ］，ｍｉｎ_{（１≦ｉ≦ｍ）}Ｅ［Ｔｃｃ’ｅ_ｉ］）よりも小さければ、見込移動による所要時間に利得が生じる。その場合、グラフに、次の頂点と、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ、および
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’、
そして、重みＰ（ｃ，ｃ’）を有して、ＡｖｇＭｉｎＷａｌｋＷａｉｔＲｉｄｅＷａｌｋ（平均最小徒歩待ち乗車徒歩）とラベル付けられる、次のエッジと、を追加する、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
→ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’。
また、クラスタｃのバスと地下鉄の駅からのエッジを、次の頂点、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ、
に追加し、次の頂点、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’
から、クラスタｃ’のバスと地下鉄駅にエッジを追加し、これらのエッジはＺｅｒｏ（ゼロ）とラベル付けられ、重みゼロを有する。一実施形態において、その重みＰ（ｃ，ｃ’）が、例えば少なくとも１０秒のしきい値を超えるゲインをもたらす場合にのみ、見込エッジを追加する。

本方法は、最初に到着した交通手段の選択肢に乗車することを、乗客に要求するものではなく、それは、単に長い待ち時間を必要とする後の選択肢が目的地に早く到着する可能性があるためである（高速バスと通常のバスを考えるとよい）。本方法は、同じ停留所／駅でバスに乗る必要はなく、なぜなら、乗客は他の停留所／駅まで、例えば、そこから出発する急行列車を予想して、歩くことができるからである。

（定義１）
一実施形態において、見込移動は、以下によって定義される：
・任意の２つの場所ｃ，ｃ’、
・それぞれｃからｃ’への移動所要時間を表す任意の個数ｋ≧２のランダム変数Ｔ_１，．．，Ｔ_ｋ、
・そのｋ個の変数は互いに独立、依存、または任意に相関、
・そのｋ個の変数のいずれも、乗客が場所ｃに到着する時間Ａを条件としてもよく、その時間Ａはランダム変数であってもよい。
見込移動の所要時間は、最小値ｍｉｎ（Ｔ_１，．．，Ｔ_ｋ）であり、それ自体がランダム変数である。見込エッジの重みは、この最小値の期待値である、Ｐ（ｃ，ｃ’）＝Ｅ［ｍｉｎ（Ｔ_１，．．，Ｔ_ｋ）］。

他の実施形態において、ランダム変数Ｔ_ｉは、区間に均一に分布する。一実施形態において、ランダム変数Ｔ_ｉは、特定の時間窓内に入る、ｃへの到着時間、またはｃへの到着時間の確率分布、を条件とする。

一実施形態において、ランダム変数Ｔ_１，．．，Ｔ_ｋを決定するために、ｃ付近の車両停留所およびｃからこれらの停留所までの徒歩の所要時間のリストと、ｃ’付近の車両停留所およびこれらの停留所からｃ’までの徒歩の所要時間のリストと、を決定し、２つのリストにおける車両停留所の各ペアに対して、移動所要時間ランダム変数を決定する。

一実施形態において、ランダム変数ｍｉｎ（Ｔ_１，．．，Ｔ_ｋ）に関する様々な統計量を計算する。１つは、すでに述べた期待値である。また、特定の確率で到達できる到着時間を決定するために用いることができる確率質量を計算する。これらの統計量を計算するために、サンプリング、閉形式の公式、近似積分、その他の近似アルゴリズムまたは発見的手法を含むいくつかの方法を用いる。

一実施形態において、見込移動のコンポーネントを事前計算して保存しておくことにより、見込移動を決定する必要がある場合に、ストレージからコンポーネントを取得し、コンポーネントをゼロから計算することを回避できる。そのようなコンポーネントの例として、車両停留所のペア間の移動の所要時間のランダム変数、２つ以上の移動所要時間ランダム変数の予想される最小値、少なくとも２つの移動時間ランダム変数の最小値の確率分布、または、車両停留所のペア間の経路または移動所要時間、がある。

これまで、特定のｃとｃ’の見込エッジを計算する方法を定義した。この定義を個別のｃとｃ’全てのペアに適用し、これにより、どの重みの見込エッジによって、どの見込クラスタが接続され、どれが接続されないか、が決定される。

一実施形態において、ｃ，ｃ’ペアの二次数を考える代わりに、グラフトラバーサルを実行する。一実施形態において、各ｃについて、頂点、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ、
から、徒歩－バス／地下鉄－徒歩によって到達可能な全ての頂点、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’
まで、前方向きに「前方」トラバーサルを用いる。このトラバーサル中に、各ｃ’に対ついて、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’、
に至るグラフ経路を特定する。特定のｃ’について、全てのそのような経路を特定したら、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ、と
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’
の間の、全ての選択肢を計算し、これらの選択肢の予想される最小値を計算できる（さらなる例については図９参照）。グラフの到達可能な部分のみに探索を制限するので、多くの場合、見込エッジをより効率的に計算できる。一実施形態において、各ｃ’について、頂点、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’、
から、「逆転された」経路の徒歩－バス／地下鉄－徒歩によって到達可能な全ての頂点、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
まで、後方向きに「後方」トラバーサルという対称的方法を用いる。

図９は、どの待ち所要時間もそれぞれのエッジの区間［０，２ＷａｉｔＧｅｔＯｎ（乗車待ち）］に均一に分布し、かつ乗車所要時間が決定的である場合に、グラフＧ０に見込エッジを追加する処理の実施形態を示している。

（４．３ グラフＧ０の拡張）
グラフＧ０の拡張について説明する。各拡張は、特定の種類のルート決めクエリに役立つ。

（４．３．１ ソースが既知）
いくつかの実施形態において、ルート決めクエリのソース場所は事前に知られている。例えば、首都圏の全てのレストランからの最短ルートを見つけることに興味があり、レストランの場所がわかっているとする。これは、拡張グラフＧ０を用いて実現できる。

一実施形態において、そのようなソースｓ毎に、下記頂点を追加する
ＳＯＵＲＣＥ＿ｓ。
図１参照。一実施形態において、
ＳＯＵＲＣＥ＿ｓ
から、任意のバス停と地下鉄駅のクラスタ
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
に向かうエッジを、グラフＧ０に追加する。エッジはＷａｌｋとラベル付けされ、その重みは徒歩の所要時間を表す。他の実施形態において、大きくともしきい値までの所要時間を有する最短徒歩、またはセクション４．２．３のような他の実施形態、を用いる。

得られるグラフは、Ｇ１（Ｇ０を含む）で表示される。Ｇ１は、任意の、
ＳＯＵＲＣＥ＿ｓ
から、任意の
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ
への最短経路を計算するために用いることができる。一実施形態において、クエリが提示されると、いくつかの経路が事前計算され、保存され、ストレージから取得される。

他の実施形態において、ターゲットが事前に知られている場合、対称方法が用いられる。各ターゲットｔについて、下記頂点を追加し、
ＴＡＲＧＥＴ＿ｔ、
任意の
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ
から任意の
ＴＡＲＧＥＴ＿ｔ
への、Ｗａｌｋ（徒歩）とラベル付けされるエッジを追加する。得られるグラフは、Ｇ１’で表示される。

（４．３．２ ターゲットが既知）
いくつかの実施形態において、ルート決めクエリのターゲット場所は事前に知られており、ターゲットまでの見込エッジを有するＧ０を拡張する。

各ターゲットｔに対して、下記の頂点を追加する、
ＴＡＲＧＥＴ＿ｔ。
図１参照。一実施形態において、グラフＧ０におけるバス停および地下鉄駅クラスタ
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ
から、
ＴＡＲＧＥＴ＿ｔ、
へのエッジを追加する。エッジにはＷａｌｋというラベル付けられ、その重みは徒歩の所要時間を表す。他の実施形態において、大きくともしきい値までの所要時間を有する最短徒歩、またはセクション４．２．３のような他の実施形態、を用いる。

セクション４．２．５と同様の処理に従い、見込エッジを追加する。具体的には、任意の
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
および
ＴＡＲＧＥＴ＿ｔ、
について、ｃからｔまでの全ての経路を、下記の２種類について、決定する。
（１）徒歩でバスに乗車するグラフ経路：ｃからｂまで徒歩、
ＢＵＳ＿ＳＴＯＰ＿ｂ
→ＢＵＳ＿ＡＴ＿ＢＵＳ＿ＳＴＯＰ＿ｂ＿ｉ＿ｅ
→ＢＵＳ＿ＡＴ＿ＢＵＳ＿ＳＴＯＰ＿ｂ’＿ｊ＿ｅ
→ＢＵＳ＿ＳＴＯＰ＿ｂ’
→ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ”
→ＴＡＲＧＥＴ＿ｔ、
（２）徒歩で地下鉄に乗車するグラフ経路：ｃからｓ’まで徒歩
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ’
→ＳＵＢＷＡＹ＿ＦＲＯＭ＿ＴＯ＿ｓ’＿ｓ”
→ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ”
→ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’
→ＴＡＲＧＥＴ＿ｔ。
他の実施形態において、大きくともしきい値までの所要時間を有する最短徒歩、またはセクション４．２．３のような他の実施形態、を用いる。セクション４．２．５のように、各経路に沿った移動所要時間のランダム変数を定義する。

一実施形態において、種類（１）は独立のランダム変数であり、種類（２）は非独立のものである、と仮定する。そして、全ての種類（１）ランダム変数のプールを考慮し（繰り返しバス路線の重複を適切に削除する）、Ｐ（ｃ，ｃ’）に関する式１におけるように、一度に、１種類（２）ランダム変数のプールに追加することにより、予想される最小移動所要時間を計算する。他の実施形態において、見込移動の定義１を用いる。これは、ｃからｔへの見込移動と呼ばれるＰ（ｃ，ｔ）を定義する。

最小限の期待以上に移動所要時間に利得がある場合、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
から、
ＴＡＲＧＥＴ＿ｔ
までのエッジを加え、このエッジは重みＰ（ｃ，ｔ）を有してＡｖｇＭｉｎＷａｌｋＷａｉｔＲｉｄｅＷａｌｋとラベル付けられる。また、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃから、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’
までの、以前に定義したエッジに用いたものと同様の実施形態を、これらに用いる。

一実施形態において、セクション４．２．５で説明したように「前方向」または「後方向」のグラフトラバーサルを用いて、全てのｃおよびｔについて、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ、と
ＴＡＲＧＥＴ＿ｔ、との間の見込エッジの計算を高速化する。他の実施形態において、このトラバーサルは、Ｇ０で見込エッジを計算するときのトラバーサルにマージすることができる。

得られるグラフは、Ｇ２（Ｇ０を含む）で表示される。Ｇ２は、任意の、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
から、任意の
ＴＡＲＧＥＴ＿ｔ
への最短経路を計算するために用いることができる。一実施形態において、クエリが提示されると、いくつかの経路が事前計算され、保存され、ストレージから取得される。

他の実施形態において、ソースが事前に知られている場合、対称方法が用いられる。各ソースｓについて、下記頂点を追加し、
ＳＯＵＲＣＥ＿ｓ、
任意の、
ＳＯＵＲＣＥ＿ｓ
から任意の
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ
への、見込エッジを計算する。得られるグラフは、Ｇ２’で表示される。

（４．３．３ クエリが提示されたときに明らかになるソース、ターゲットは既知）
いくつかの実施形態において、ルート決めクエリのターゲット場所は事前に知られているが、ソースはクエリが提示されたときにのみ明らかになる。

一実施形態において、セクション４．３．２のグラフＧ２を用いて最短乗車を計算する。

クエリ（ｓ，ｔ）が提示されると、ｓの場所から、下記のそれぞれへの徒歩を決定する、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ。
一実施形態において、大きくともしきい値までの所要時間を有する最短徒歩であって、それによりソース場所付近の車両停留所のリストを生成する最短徒歩、またはセクション４．２．３のような他の実施形態、を用いる。また、グラフＧ２において、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
から、
ＴＡＲＧＥＴ＿ｔ
への、最短移動の継続を決定する。一実施形態において、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
のそれぞれから、
ＴＡＲＧＥＴ＿ｔ、
までの最短経路所要時間を、事前計算し、その結果を保存する。クエリが提示されると、ストレージからこれらの結果を検索する。他の実施形態において、クエリが提示されたとき、所要時間を計算するため、Ｇ２において、最短経路アルゴリズムグラフを用いる。

ｓからｃへの徒歩とｃからｔへの移動の所要時間の合計を最小化するクラスタｃを見つける。この最小値は、ｓからｔまでの最短移動時間である。

他の実施形態において、クエリが提示されたときにのみターゲットが明らかにされるとき、対称方法を用いる。次に、ソース場所の近くの車両停留所のリストを生成する代わりに、ターゲット場所の近くの車両停留所のリストを生成する。

他の実施形態において、グラフＧ２を用いる代わりに、グラフＧ１’を用いる。

（４．３．４ クエリの提示時に明らかになるターゲット、ソースが既知）
一部の実施形態において、ルート決めクエリのソース場所は事前に知られているが、ターゲットはクエリが提示されたときにのみ明らかになる。

一実施形態において、セクション４．３．１のグラフＧ１を用いて最短乗車を計算する。ただし、ターゲットへの見込エッジを計算する必要がある。ターゲットは事前に不明であるため、この計算はセクション４．３．２よりも複雑である。

Ｇ０の各見込エッジに対して選択がどのように計算されたかを思い出す。各クラスタｃおよびｃ’について、選択肢（ｃ，ｃ’）を、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
から、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’
へのエッジのＰ（ｃ，ｃ’）を計算するために用いる選択肢とする。選択肢（ｃ，ｃ’）は、選択肢を１つだけ（例：バス１つ、地下鉄１つなど）持つことがあり得る。選択肢（ｃ，ｃ’）は、十分な利得がないため見込エッジがＧ０に追加されなかった場合であっても、定義される。

グラフＧ１において、次のソース、
ＳＯＵＲＣＥ＿ｓ
およびグラフに表されてなくともよい任意のターゲット場所ｔ、に対して提示されたクエリを（ｓ，ｔ）とする。

ｓからｔへの最短経路には、バスが１本のみ、または地下鉄のみが含まれる場合がある。その場合、見込エッジを考慮する必要はない。グラフＧ１を取得し、これをさらに拡張する。頂点、
ＴＡＲＧＥＴ＿ｔ、
と、任意のｃについて、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ、
から、
ＴＡＲＧＥＴ＿ｔ。
へのエッジを追加する。これらの各エッジは、Ｗａｌｋとラベル付けられ、その重みは徒歩所要時間である。一実施形態において、任意のエッジは、大きくともしきい値までの持続時間を有する最短徒歩所要時間、またはセクション４．２．３のような他の実施形態を表す。得られたグラフにおいて、
ＳＯＵＲＣＥ＿ｓ
から
ＴＡＲＧＥＴ＿ｔ
までの、最短経路を計算し、経路の長さをＡ（ｓ，ｔ）で表す。この長さは、ｓからｔまでの最短移動所要時間の候補である。

他の候補がある。最短経路には、より多くの車両が含まれることもある。その場合、経路に沿って最後から２番目の停留所／駅がある。このケースをカバーするために、ｔへの見込エッジを計算する。この処理は図１２に示されている。図を簡略化するため、図面には１枚札（ｓｉｎｇｌｅｔｏｎ）の見込クラスタが描かれている（それぞれにバス停が１つ、または地下鉄の駅が１つだけある）。

ｔへの見込エッジを計算するには、グラフＧ１から始める。最後から２番目の停留所／駅で終わるｓからｔまでの移動の各部を列挙する。具体的には、
ＳＯＵＲＣＥ＿ｓ
から、各ｃについて、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ、
までの最短移動所要時間を決定する。この所要時間を、最短（ｓ→ｃ）で表す。例えば、図１２において、
ＳＯＵＲＣＥ＿ｓ
から
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ_ｌ
へのエッジに付された値９００は、
ＳＯＵＲＣＥ＿ｓ
から、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｓ_１
への最短移動所要時間を示す。この移動は、グラフＧ１における見込エッジに沿って通過する場合があることに注意。一実施形態において、この所要時間は、クエリが提示される前に、事前計算および格納され、クエリ時にストレージから検索され得る。

最後から２番目の停留所／駅からターゲットｔまで、移動がどのように続くかを、見込エッジと徒歩を用いて決定する。全ての
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ、
について、最初に、選択肢（ｃ，ｃ’）と呼ばれる中間体、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’
に移動してｃ’からｔへの徒歩を続けることにより、ｃからｔに移動する選択肢を決定する。一実施形態において、大きくともしきい値までの所要時間を有する最短徒歩ｃ’からｔのみ、またはセクション４．２．３にあるような他の実施形態、を考慮する。例えば、図１２において、選択肢（ｂ_１，ｂ_０）は、
ＢＵＳ＿ＳＴＯＰ＿ｂ_１
から
ＢＵＳ＿ＳＴＯＰ＿ｂ_０
へのエッジに付されて示されており、２つの選択肢があり、１つは、バス路線ｅ”であり、［０，９００］において待ち所要時間が均一、移動所要時間１６００、他の１つは、バス線ｅ’”であり、［０，３６００］において待ち所要時間が均一、所要所要時間１０００である。続いて、
ＢＵＳ＿ＳＴＯＰ＿ｂ_０
から
ＴＡＲＧＥＴ＿ｔ
まで、徒歩２４０を要する。

ｃにいる乗客はｃ’を継続として選択する可能性があるので、ｔにおいて全てのｃ’の選択肢を組み合わせる。この組み合わせにより、ｃからｔへの移動の選択肢が形成される。例えば、図１２において、
ＢＵＳ＿ＳＴＯＰ＿ｂ_１
からの他のエッジがあり、そのエッジは、
ＢＵＳ＿ＳＴＯＰ＿ｂ_２
に行く。そのエッジに付された選択肢（ｂ_１，ｂ_２）には、ただ１つの選択肢を持ち、それはバス路線ｅ’であり、［０，３００］において待ち所要時間が均一、所要時間９００である。続いて、
ＢＵＳ＿ＳＴＯＰ＿ｂ_２
から
ＴＡＲＧＥＴ＿ｔ
まで、徒歩５００を要する。選択肢（ｂ_１，ｂ_０）と選択肢（ｂ_１，ｂ_２）の組み合わせにより、３つの選択肢（バス路線ｅ’，ｅ”，ｅ’”）が生成される。これらは、
ＢＵＳ＿ＳＴＯＰ＿ｂ_１
から
ＴＡＲＧＥＴ＿ｔ
への選択肢である。これらの選択肢を用いた場合の予想される最小移動時間は、２６３６である。

セクション４．２．５のように、同じバス路線によるバスの重複乗車を排除する必要がある。例えば、図１２において、乗客は、同じバス路線ｅ”を用いて、
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ_１
から出発できるが、２つの異なる場所、
ＢＵＳ＿ＳＴＯＰ＿ｂ_２
と、
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ_０
に行く。ｃにおけるバス路線については、ｃからｔまでの予想される移動所要時間が最も短いこのバス路線の選択肢のみを保持する（ｃにおけるこのバス路線の他の選択肢を排除する）。例えば、図１２における、
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ_０
の選択は、より高い期待を有しているので、排除する。セクション４．２．５においてＰ（ｃ，ｃ’）を計算した方法と同様に、残りの選択肢の中から予想される最小移動所要時間Ｐ（ｃ，ｔ）を計算する。

最短経路は、ｃのいずれかを通過する可能性があるため、ｃ全体で最小値を計算し、それを下記のＢ（ｓ，ｔ）で表す。
Ｂ（ｓ，ｔ）＝ｍｉｎ_ｃ｛最短（ｓ→ｃ）＋Ｐ（ｃ，ｔ）｝。
例えば、図１２において、最小値Ｂ（ＳＯＵＲＣＥ＿ｓ，ＴＡＲＧＥＴ＿ｔ）＝２４４５、つまり、ｍｉｎ｛２６３６，２４４５｝であり、これは、乗客が最後から２番目の
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ_１
に移動する方が、同じく最後から二番目の
ＢＵＳ＿ＳＴＯＰ＿ｂ_１
に移動するよりも有利だからである。

この量は、最後から２番目の車両を含む、ｓからｔまでの最短移動所要時間を示す。Ｂ（ｓ，ｔ）は、ｓからｔまでの最短移動所要時間のもう１つの候補である。

最後に、クエリへの応答は、２つの候補の最小値である：ｍｉｎ｛Ａ（ｓ，ｔ），Ｂ（ｓ，ｔ）｝。

例えば、図１２において、クエリへの応答はなおも２４４５であり、これは、
ＳＯＵＲＣＥ＿ｓ
から、
ＢＵＳ＿ＳＴＯＰ＿ｂ_０
を通して、
ＴＡＲＧＥＴ＿ｔ
まで移動する１台の車両のみを用いては移動を短縮できず、この移動所要時間がＡ（ＳＯＵＲＣＥ＿ｓ，ＴＡＲＧＥＴ＿ｔ）＝３０００＋２４０となるからである。

他の実施形態において、グラフＧ１を用いる代わりに、グラフＧ２’を用いる。

他の実施形態において、クエリが提示されたときにのみソースが明らかにされる場合に、ソースからの見込エッジを計算するため、対称方法を用いる。そこで、ターゲットに到達する前の、最後から２番目と最後の停留所を検討する代わりに、ソースを出発後の、最初と２番目の停留所を検討する。

（４．３．５ クエリ時に明らかにされたソースとターゲット）
クエリのソースとターゲットの両方が事前に不明な場合、前セクションの方法を選択して組み合わせる。一実施形態において、ソースｓの場所から、各ｃについて、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ、
までの徒歩を決定し、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
からターゲットｔ（最後から２番目の選択肢を含むか、または含まない）まで移動する。ｃで選択された最小合計で応答する。一実施形態において、大きくともしきい値までの所要時間を有する最短徒歩、またはセクション４．２．３のような他の実施形態を用いる。

（４．４ 変形例）
実施形態の範囲および精神から逸脱することなく、多くの修正および変形が当業者には明らかであろう。説明のため、いくつかの変形例を紹介する。

一実施形態において、見込エッジのより一般的な概念を用いる。移動に複数の車両と待ちが含まれる場合、グラフ内の最短経路検索は複数の見込エッジを横断する可能性があり、経路に沿ったこれらの見込エッジは一緒に複数の待ちと乗車の繋がりを抽象化する。この多重度を捕捉するために、一実施形態において、最大でｄ個の待ちと乗車の繋がりを抽象化する深さｄの見込エッジのより一般的な概念を用いる。例えば、ｃ－ｗａｌｋ１－ｗａｉｔ１－ｂｕｓ１－ｗａｌｋ２－ｗａｉｔ２－ｂｕｓ２－ｗａｌｋ３－ｃ’という経路は、ｃからｃ’への深さ２の見込エッジとして抽象化できる。一実施形態において、１よりも大きいｄについて、深さｄの見込エッジをグラフに追加する。

一実施形態において、本方法は、出発時間を与えられてルートを構築する。例えば、乗客が火曜日の午前８時に移動を開始する場合を考える。ここで、ルート決めクエリは、ソース場所とターゲット場所に加え、出発時間を指定する。一実施形態において、ソースは、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｓ、
であり、ターゲットは、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｔ
である。グラフＧ０、図１参照、を変更する。ここでは最初の乗車でも待ちが必要な場合があるので、ＦｉｒｓｔＷａｉｔＧｅｔＯｎエッジ、および
ＳＵＢＷＡＹ＿ＦＲＯＭ＿ｓ
頂点とを取り除き、クラスタｃ内の任意のｂおよびｓについて、
ＳＴＯＰＳＴＡＴＩＯＮ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
から、
ＢＵＳ＿ＳＴＯＰ＿ｂ
と
ＳＵＢＷＡＹ＿ＳＴＡＴＩＯＮ＿ｓ、
へのそれぞれに、エッジを追加する。一実施形態において、見込エッジを用いるために、ダイクストラの最短経路アルゴリズムを採用する。各頂点、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
について、頂点での乗客の既知の最低予想到着時間を維持し、この時間を用いて待ち、徒歩、および乗車所要時間ランダム変数を調整し、それぞれの
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ’
に対する見込エッジを計算する。このように計算されたエッジの重みを用いて、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ’
における既知の最低予想到着時間を更新する。他の実施形態において、各既知の最低予想到着時間を、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
または、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＴＡＲＧＥＴ＿ｃ
のそれぞれにおいて維持または更新する代わりに、到着時間の確率分布を維持または更新する。他の実施形態において、他の最短経路アルゴリズム、例えば同様の方法におけるＡ^＊（Ａスター）探索アルゴリズムを採用する。他の実施形態において、例えば、出発時間が「今／まもなく」である場合、条件付きランダム変数は、クエリの時点での輸送システムの状態を用いて計算され、待ち時間および乗車所要時間のより正確な分布を提供する。

一実施形態において、本方法は、到着期限が与えられたルートを構築する。例えば、乗客が火曜日の午前９時より前に目標に到着したい場合を考える。これは、午前９時にターゲットから出発するのと同じであるが、時間と空間を遡る。これは、グラフを適切に逆に構成することで簡単に抽象化できる（バスと地下鉄は逆の時間と空間で移動させる）。

一実施形態において、最終期限前の所望の到着確率ｐを満たす見込移動を決定する。ｃからｄへの見込エッジを考える場合、ｃにおける乗客の到着時間を示すランダム変数Ａを用いる。次に、選択肢を用いて、ｃからｄまでの移動所要時間の、ｋ個のランダム変数Ｔ_１，．．，Ｔ_ｋが与えられると、見込移動ｍｉｎ（Ａ＋Ｔ_１，．．，Ａ＋Ｔ_ｋ）を用いて、ｃ’における到着時間の分布を決定する。次に、この分布が、どの時間ｔまで、所望の確率ｐである質量を持つかを決定する。

一実施形態において、最短経路に沿った車両、または経路に沿った各点についての到着／出発時間、を報告する。この情報は、グラフ内の経路、および経路に沿った見込エッジの選択肢から簡単に読み取ることができる。

一実施形態において、ストレージが制限され、バックエンドサーバとの通信が制限されているコンピューティングデバイス上のルート決めクエリに応答する。例えば、これはプライバシーを懸念するユーザの携帯電話で発生する可能性がある。その場合、グラフＧ０で適切に少数のクラスタを用いる。他のグラフでも同様の手法を使用できる。

一実施形態において、最大徒歩所要時間、最大乗り換え回数、最大待ち所要時間、特定の種類の車両への制限（例えば、高速バスと地下鉄のみを用いる）を含む要件を、ルー決め応答に課する。本発明は、グラフの適切な修正およびグラフの最短経路アルゴリズムによってこれらの要件を実現する。

一実施形態において、本方法は不完全なグラフに適用される。例えば、エッジＷａｉｔＧｅｔＯｎの重みが地下鉄の予想される待ち所要時間を正確に反映していない可能性があり、おそらく所要時間を誤って推定したかまたは大都市圏に存在しないバスの頂点とエッジを使ったから、おそらくバス路線が市政府によってキャンセルされたのに本方法がそのキャンセルに気付かなかったか、または選択肢の最小値の期待値を大きな誤差でサンプリングしたまたは近似の数式／アルゴリズムを使用したから、であろう。これらは不完全性のほんの数例に過ぎない。いずれにせよ、本方法はまだ適用できる。何らかのエラーを伴うルートを生成するだけである。

一実施形態において、グラフから不要な頂点とエッジを削除する。例えば、Ｇ０における「通過」頂点、
ＳＵＢＷＡＹ＿ＡＶＧ＿ＦＲＯＭ＿ＴＯ＿ｓ’＿ｓ”
は、入エッジと出エッジとを融合させることにより、削除する。

一実施形態において、本方法のステップは、他の順序で適用される。例えば、グラフＧ０を構築するとき、セクション４．２．１と４．２．２で説明されている順序を逆にすることができ、最初に非固定時刻表車両の頂点とエッジを追加し、次に固定時刻表車両の頂点とエッジを追加する。

一実施形態において、方法を並列化する。例えば、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ
のそれぞれから見込エッジを計算する代わりに、任意の２つのｃ_１とｃ_２を考え、
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ_１
からの見込エッジを計算する際に、次の
ＰＲＯＳＰＥＣＴ＿ＣＬＵＳＴＥＲ＿ＳＯＵＲＣＥ＿ｃ_２
からの見込エッジの計算と並行して行う。

（５ コンピュータシステム）
本発明の実施形態の１つは、ルート決めクエリに応答するコンピュータシステムである。

一実施形態において、本システムは、出発時刻が与えられると、場所間の最短ルートのクエリに応答する：ここで、任意のクエリは、所定形式（ソース、ターゲット、ｍｉｎｕｔｅＯｆＤａｙ（分時刻））を有する。応答は、所要時間、選択肢付きルート、の形式である。実施形態の説明は図１３にある。

本明細書では「モジュール」という用語を用いる。この用語は、特定の機能を提供するコンピュータ（サブ）システムを意味することは当技術分野で知られている。コンピュータシステムを特定のモジュールに分割するというこの選択は例示的なものであり、必須ではない。当業者は、本発明の範囲から逸脱することなく、システムを他の方法でモジュールに編成できることに気付くであろう。

システムの１つのモジュール（１２０２）は、複数のデータソース（１２０１）から大都市交通システムに関する情報を読み取る。このモジュールは、どの車両、ルート、またはそれらの各部が、固定時刻表のものと見なされ、どの非固定時刻表のものと見なされるかを決定する。このモジュールは、固定時刻表車両のルートを計算する。このモジュールは、また、非固定時刻表車両の時間に基づいて、待ち所要時間と乗車所要時間の分布を計算する。

出力は、見込エッジを計算するモジュール（１２０４）に渡される。そのモジュールは、複数のデータソース（１２０３）からの徒歩に関する情報を照会する。選択された見込クラスタｃとｃ’、およびｃにおけるの乗客の到着時間について、モジュールは、ｃにおける乗客の到着時間を条件とするランダム変数を用いて、見込エッジの重みＰ（ｃ、ｃ’）と選択肢を計算する。結果はストレージ（１２０５）に保存される。

モジュール（１２０２）および（１２０４）は、継続的に動作する。その結果、システムは、輸送システムの新しいモデルを維持する。

その間、他のモジュール（１２０６）は最短経路を事前計算する。モジュールは、時々、（１２０５）から見込エッジを読み取り、（１２０２）から非見込エッジを読み取とって、場所をつなぐグラフを構築する。所定形式（停留所／駅クラスタソース、停留所／駅クラスタターゲット、ｍｉｎｕｔｅＯｆＤａｙ）のクエリから選択されたクエリについて、経路を計算するため、最短経路アルゴリズムがグラフに適用される。結果は、後で必要になったときストレージ（１２０７）から結果を検索できるように、保存される。

同時に、クエリ応答モジュール（１２０８）がクエリに応答する。クエリ（ソース、ターゲット、ｍｉｎｕｔｅＯｆＤａｙ）（１２０９）が届くと、モジュールはセクション４に従って最短経路を計算する。モジュールは、（１２０３）に連絡して、ソースとターゲット、および停留所／駅クラスタ間の徒歩を決定する。モジュールは、（１２０７）から関連する事前計算された最短経路を検索する。必要であるがまだ利用できない場合、モジュールは、モジュール（１２０６）に最短経路を要求し、結果の最短経路を将来の使用のためにストレージ（１２０７）に保存する。モジュール（１２０８）は、（１２０５）からの選択肢と時間も検索する。これらの徒歩、最短経路、および選択肢が組み合わされて、クエリに対する応答（１２１０）が生成される。

本発明の態様は、ハードウェアの実施形態、ソフトウェアの実施形態、またはこの２つの組み合わせの形をとることができる。本発明のステップは、任意のフローチャートのブロックを含み、機能性および最適化に応じて、順不同で、部分的に並行して、または貯蔵所から提供されて、実行され得る。態様は、シーケンシャルシステムまたはパラレル／分散システムの形をとることができ、各コンポーネントは他のコンポーネントと重複する可能性のあるいくつかの態様を実現し、コンポーネントは、例えばあらゆる種類のネットワークを用いて通信できる。本発明の態様のための動作を実行するコンピュータプログラムは、Ｃ＋＋，Ｊａｖａ（登録商標）、またはＪａｖａＳｃｒｉｐｔ（登録商標）を含む任意のプログラミング言語で書かれてもよい。任意のプログラムは、中央処理装置（ＣＰＵ）、グラフィック処理装置（ＧＰＵ）、および関連するメモリとストレージデバイスを含む、任意のハードウェアプラットフォームで実行できる。プログラムは、本発明の態様を１つ以上のソフトウェアプラットフォーム上で実行でき、そのプラットフォームは、ＡｎｄｒｏｉｄまたはｉＯＳなどのオペレーティングシステム、またはＦｉｒｅｆｏｘ，Ｃｈｒｏｍｅ，Ｉｎｔｅｒｎｅｔ Ｅｘｐｌｏｒｅｒ、またはＳａｆａｒｉなどを含むＷｅｂブラウザ、を実行するスマートフォンを含むが、これらに限定されない。

（６ コンピュータサービス製品）
本発明の実施形態の１つは、ユーザ対面デバイスを介してユーザが利用可能な、スマートフォンアプリケーションまたはウェブページなどのサービス製品である。本発明がこれらの装置に限定されないことは、当業者には明らかであろう。また、図面によるサービスの表示は、本発明の範囲から逸脱することなく修正（再配置、サイズ変更、色、形状の変更、コンポーネントの追加または削除を含む）できることも明らかである。

一実施形態において、サービスは、スマートフォンアプリケーションからアクセスされる。ユーザは、スマートフォン上のアプリケーションのユーザインターフェイスを操作して、出発時間、ソース、およびターゲットを指定する。すると、サービスは、ルートを生成してスマートフォン上にルートを示す。図１４は、午前８時にＡからＬに出発するクエリの結果例を、示す。

一実施形態において、サービスは、どの選択肢が現在最短の移動所要時間をもたらすかを報告する。一実施形態において、システムは、このより速い選択肢を強調表示する（ルート上に１４０１で示されている）か、その選択肢の移動所要時間を示すか、現在の待ち所要時間（Ｄ付近の１４０２で示されている）を示す。一実施形態において、車両の現在場所が与えられると、このより速い選択が計算される。一実施形態において、このレポートは、ユーザが現在選択の場所の近くにいるときに示され、例えば、ユーザがＡから出発しようとしている場合、サービスは、現在の状況化で、ＢおよびＣ経由ではなく、ＤおよびＥ経由でＦに到達する方が高速になる可能性がある、ことを示す。

一実施形態において、サービスは、ある場所の選択肢の中から各選択肢の現在の待ち所要時間（Ｆ付近の１４０３で示されている）、または各選択肢の予想される乗車所要時間（１４０４で示されている）を示す。これは、最適ではない場合でも、ユーザが自分で選択を決定するのに役立つ。

一実施形態において、サービスは、ある場所での全ての選択肢に対する１つの予想される待ち所要時間を報告する。その所要時間は、予想される最小移動所要時間（Ｈ近くの１４０５で示されている）を達成する選択肢にユーザが乗ることを想定した予想される待ち時間である。一実施形態において、この報告は、例えば、ユーザの現在位置と比較して道路のはるか先であるルートの部分について、車両場所が不確実なときに示される。これは、車両を待っている停留所／駅で暇な状態になる時間をユーザに通知する。

一実施形態において、サービスは、２つの場所（ルート上の１４０６によって示されている）間の見込移動の所要時間を報告する。これは、セクション４でＰ（ｃ，ｃ’）で示されている値である。

一実施形態において、サービスは、以下の少なくとも１つを用いてユーザに応答する。
１．マップに示されたソース場所。
２．マップに示されたターゲット場所。
３．ルートに沿ってマップに示された任意の停留所の場所。
４．ルートに沿ってマップに示された一連の停留所の場所。
５．ソースの場所、ターゲットの場所、またはルート沿いの停留所のいずれかの、名前、住所、または識別子。
６．出発時刻。
７．出発時刻範囲。
８．到着時刻。
９．到着時刻範囲。
１０．期限前に到着する確率。
１１．マップに示された２つの場所の間の複数の選択肢に沿う一連の場所。
１２．任意の選択における徒歩コンポーネントのための指示。
１３．任意の選択における待ちコンポーネントの場所または所要時間。
１４．任意の選択における乗車コンポーネントのための指示。
１５．少なくとも２つの選択肢における予想される最小待ち所要時間。
１６．少なくとも２つの選択肢における現在の最小待ち所要時間。
１７．選択肢の任意のコンポーネントまたは選択肢について、予想される移動所要時間、または、少なくとも２つの選択肢の中で予想される最小移動所要時間。
１８．選択肢の任意のコンポーネントまたは選択肢について、現在の移動所要時間。または、少なくとも２つの選択肢の中の最小移動所要時間。
１９．選択肢内の任意のコンポーネント、選択肢、または少なくとも２つの選択肢のうちの最小値について、予想される出発時刻または予想される到着時刻。
２０．選択肢内の任意のコンポーネント、選択肢、または少なくとも２つの選択肢のうちの最小値について、現在の出発時刻または現在の到着時刻。
２１．任意の選択肢における任意の車両の名前または識別子。
２２．任意の選択肢における任意の車両の名前、住所、または停留所の識別子。
２３．任意の選択肢における任意の車両の現在の場所。
２４．車両の現在の場所が与えられたとき、２つ以上の選択肢の中から、どの選択肢が最も速く示されるかについての提示。

（７ 申し立て）
当業者は、本発明の範囲から逸脱することなく、様々な修正を行うことができ、本質的に等価なもので置換を行うことができることに気付くであろう。さらに、特定の状況は、その範囲から逸脱することなく、本発明の教示に適合させることができる。従って、開示された実施形態を参照して本発明を説明したという事実にもかかわらず、本発明はこれらの実施形態に限定されるものではない。むしろ、本発明は、添付の特許請求の範囲内に入る全ての実施形態を含む。

Claims (1)

1. ソース場所からターゲット場所までの移動のルートを示す情報を提供する方法、
   前記方法は以下の事を含む：
   （ａ）前記ソース場所と前記ターゲット場所とを含むクエリを受け取り、
   （ｂ）前記情報を生成し、および
   （ｃ）前記情報によって前記クエリに応答する、
   前記方法は以下の事によって特徴付けられる：
   （ｄ）グラフ経路を決定する、ここにおいて、前記グラフ経路は前記ソース場所からの第１距離しきい値内のグラフ頂点と、前記ターゲット場所からの第２距離しきい値内のグラフ頂点と、の間の経路であり、
   ここにおいて、前記グラフ経路はグラフに含まれ、前記グラフは以下の事を含む：
   （ｉ） 複数のグラフ頂点、ここにおいて、場所を表す少なくとも２つのグラフ頂点は前記複数のグラフ頂点に含まれ、および
   （ｉｉ） 複数のグラフエッジ、ここにおいて、移動所要時間を表す少なくとも２つのグラフエッジは前記複数のグラフエッジに含まれ、
   ここにおいて、前記グラフ経路は少なくとも２つの見込エッジ(prospect edge)を含み、
   ここにおいて：
   （ｉｉｉ）各見込エッジは前記複数のグラフエッジに含まれ、
   （ｉｖ） 各見込エッジは前記見込エッジの始頂点から前記見込エッジの着頂点に通じ、前記始頂点と前記着頂点の両方が前記複数のグラフ頂点に含まれ、および
   （ｖ） 各見込エッジは２つ以上の見込ルート(prospect routes)を決定して計算され、
   ここにおいて：
   （Ａ）各見込ルートは前記始頂点の場所から前記着頂点の場所までの前記移動を表す、および
   （Ｂ）各見込ルートは前記移動のルートに含まれる移動の選択肢である、および
   （ｅ）前記情報を生成するとき、前記２つ以上の見込ルートを使用する。

Images