トランジットノードルーティング

応用数学では、トランジットノードルーティングは、長距離移動に関連するサブネットワークへの共通アクセスノード間の接続を事前に計算することで、最短経路ルーティングを高速化するために使用できます。 ^[1]

トランジットノードルーティングのフレームワークは2007年に確立され^{[1] 、その後、グリッド、ハイウェイ階層[2]}、収縮階層^[3] を使用したアプローチなど、多くの具体的な実装が浮上しました。トランジットノードルーティングは、グラフ内の重要なノード間のペアワイズ距離の前処理を必要とする静的アプローチです（これらのノードの選択方法については以下を参照してください）。動的なアプローチは公開されていません。^[4]

長距離の移動では通常、市街地の道路ではなく、高速道路などの道路ネットワークのサブセットに沿って運転することになります。このサブネットワークに入るには、まばらに分散したアクセスノードを使用する必要があります。互いに比較すると、同じ場所から始まる複数の長距離ルートは、常に開始場所に近い同じ少数のアクセス ノードを使用してこのネットワークに入ります。同様に、同様のターゲットの場所には、近くにある同じアクセス ノードを使用して常に到達します。この直感は長距離の移動にのみ当てはまります。短距離を移動する場合、ターゲットへの最速のパスにはローカル ロードのみを使用するため、このようなアクセス ノードが使用されることはありません。

このようなアクセス ノードの数は道路ネットワーク内のノードの総数に比べて少ないため、それらのノードを相互に接続するすべての最短ルートを事前に計算して保存できます。したがって、最短パスを計算するときは、開始位置と目標位置に近いアクセス ノードへのルートのみを計算する必要があります。

1. トランジット ノード ルーティングは、道路ネットワークのすべてのノードのサブセットとしてトランジット ノードを選択することから始まります。${\displaystyle T\subseteq V}$${\displaystyle V}$
2. 各ノードに対して、すべてのトランジット ノードから、前方アクセス ノードと後方アクセス ノードの専用セットが選択されます。${\displaystyle v\in V}$${\displaystyle {\overrightarrow {A}}(v)\subseteq T}$${\displaystyle {\overleftarrow {A}}(v)\subseteq T}$
3. ここで、トランジット ノード間のペアワイズ距離と、ノードと対応するアクセス ノード間の距離が計算され、保存されます。${\displaystyle D_{T}}$${\displaystyle v}$${\displaystyle d_{A}}$
4. 2つのノード間の距離は次のように計算できます。${\displaystyle d(s,t)=\min _{u\in {\overrightarrow {A}}(s),v\in {\overleftarrow {A}}(t)}d_{A}(s,u)+D_{T}(u,v)+d_{A}(v,t)}$

出発地と目的地の間の短いルートでは、トランジット ノードを必要としない場合があります。この場合、上記のフレームワークではルートが少なくとも 1 つのトランジット ノードを訪問するように強制されるため、距離が不正確になります。

この種の問題を防ぐために、ローカリティ フィルターを使用できます。指定された開始場所とターゲット場所に対して、ローカリティ フィルターは、トランジット ノード ルーティングを適用するか、フォールバック ルーチンを使用するか (ローカル クエリ) を決定します。

トランジット ノード ルーティングはアルゴリズムではなく、ルート計画を高速化するためのフレームワークにすぎません。一般的なフレームワークには、実装するために答える必要のあるいくつかの質問が残っています。

• トランジットノードはどのように選択されますか?
• アクセス ノードはどのように選択されますか?
• どの地域フィルターを使用すればよいですか?
• ローカルクエリはどのように処理すればよいですか?

このフレームワークの以下の実装例では、オーバーレイグリッドのセル内のノードのグループ化^[2]や、収縮階層に基づくより洗練された実装など、さまざまな基礎的な方法を使用してこれらの質問に答えます。^[3]

グリッドベースのアプローチでは、すべてのノードの境界の四角形が正方形のセルに均等に分割されます。

アクセス ノードはどのように選択されますか?

各セル について、 の周囲の 5x5 セルの内部領域と9x9 セルの外部領域を調べることでアクセス ノードのセットを見つけることができます。交差ノード ( 、またはの境界を横切るエッジの端) に注目すると、 のアクセス ノードは、内のノードから内のノードへの最短パスの一部である のノードです。任意のノード のアクセス ノードとして、のすべてのアクセス ノード が選択されます (右の図の赤い点)。 ${\displaystyle C}$${\displaystyle I}$${\displaystyle O}$${\displaystyle C}$${\displaystyle C}$${\displaystyle I}$${\displaystyle O}$${\displaystyle C}$${\displaystyle I}$${\displaystyle C}$${\displaystyle O}$${\displaystyle v\in C}$${\displaystyle C}$

トランジットノードはどのように選択されますか?

トランジット ノードのセットは、アクセス ノードのすべてのセットの和集合です。

どの地域フィルターを使用すればよいですか?

アクセス ノードの選択方法は、ソースとターゲットが 4 グリッド セル以上離れている場合、最短パスでトランジット ノードを通過する必要があり、距離は上記のように計算できることを意味します。ソースとターゲットが近い場合は、フォールバック アルゴリズムを使用して距離を取得します。

ローカルクエリはどのように処理すればよいですか?

ローカル クエリは、開始点とターゲット点がすでに近い場合にのみ必要となるため、ダイクストラ アルゴリズムやその拡張などの適切な最短経路アルゴリズムをすべて選択できます。

各ノードと対応するアクセス ノード間の事前計算された距離、およびトランジット ノード間のペアワイズ距離を距離テーブルに保存する必要があります。

上で概説したグリッドベースの実装では、道路グラフの各ノードに16バイトのストレージが必要になります。米国の道路網の完全なグラフには23,947,347個のノードがあります。^[5]したがって、距離テーブルを保存するには約383 MBのストレージが必要になります。

トランジットノードはどのように選択されますか?

定義により、縮約階層は重要なノード (つまり、多くの最短経路の一部であるノード) を階層の最上位に移動します。したがって、一連のトランジット ノードを縮約階層の最上位ノードとして選択できます。 ${\displaystyle k}$

アクセス ノードはどのように選択されますか?

ノードの前方アクセス ノードは、から始まる縮約階層の上方検索を実行することによって見つけることができます。上方検索の間、以前に見つかった通過ノードから出るエッジは緩和されません。検索で解決する上方ノードがなくなった場合、解決された通過ノードが のアクセス ノードになります。後方アクセス ノードも同様に見つけることができます。 ${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

どの地域フィルターを使用すればよいですか?

階層内の最短のアップダウンパスの最上位ノードがトランジット ノード セットの一部でない場合、クエリはローカルでした。つまり、パスのアップ部分 (開始ノードで始まる) もパスのダウン部分 (ターゲット ノードで終わる) もトランジット ノードを含むことができず、両方のパスに共通のノードが存在する必要があります。アクセス ノードの計算中は、各ノードの検索空間 (階層の最上位に向かって訪問したすべてのノード) は、トランジット ノードを含めずに保存できます。クエリを実行すると、開始ノードとターゲット ノードの検索空間で交差がチェックされます。これらの空間が互いに素である場合は、アップ パスとダウン パスがトランジット ノードで交わる必要があるため、トランジット ノード ルーティングを使用できます。それ以外の場合は、トランジット ノードのない最短パスが存在する可能性があります。

ローカルクエリはどのように処理すればよいですか?

ローカル クエリでは、収縮階層の 通常のクエリ アルゴリズムが使用されます。

• 最短経路問題
• ハブラベル
• 双方向検索
• 高速道路の寸法