最適ルート探索エンジンのアーキテクチャ探求

1. はじめに

経路探索は地図アプリケーションの根幹をなす問題であり、その本質はグラフ上の最短路問題として定式化できる。しかし実地での運用においては、単純な最短路に留まらない複数の要件が絡み合う。移動体の種別（車両・徒歩）によって通過可能な地形は大きく異なり、「時間を最小化したい」「危険を回避したい」「燃料消費を抑えたい」といった相互に相反しうる目的を同時に考慮しなければならない場面も多い。

本ドキュメントが対象とするシステムは、道路ネットワーク上の探索と任意地形上の格子グラフ探索という二種類の探索機構を統合し、単一の API エンドポイントから透過的に提供する経路探索エンジンの設計を扱う。設計の核心は次の三点に集約される。

1. 多目的コスト設計 — 時間・距離・リスク・エネルギーという異なる次元のコストを一つの合成スカラーに正規化する
2. アルゴリズム選択 — 道路グラフと格子グラフを横断しながらも計算量を現実的な範囲に抑える
3. インフラ設計 — 広域探索に伴うレイテンシを Redis キャッシュと解像度ピラミッドによって実用水準まで削減する

なお本稿では実装上の変数名やライブラリ固有の関数名を可能な限り排し、設計意図とアルゴリズムの本質的な構造に焦点を当てる。深層学習・メタヒューリスティック・動的交通流（時変コスト）は現バージョンのスコープ外であり、本稿では扱わない。

2. システム概観と動作モード

本エンジンは、入力パラメータの組み合わせに応じて三つの動作モードのいずれかを選択し、それぞれ専用のパイプラインで経路を算出する。モードの決定ロジックは、ユーザーが指定した優先設定（道路優先 / オフロード優先）と、数値標高モデル（DTM）の利用可否の論理積によって一意に定まる。

動作モード	適用条件	探索の本質
道路	道路優先の指定、またはオフロード優先だが DTM なし	登録済み道路グラフ $G=(V,E)$ 上の最短コスト路
オフロード	オフロード優先かつ DTM が利用可能	DTM から生成した格子グラフ上の最短コスト路
ハイブリッド	道路優先かつ DTM が利用可能（主用途）	道路経路で回廊を確定し、その内部だけ格子探索

「オフロード優先」が指定されても DTM が存在しない場合、格子のコストを計算するための標高データが欠如しているためオフロード探索は不可能となる。この場合システムはハイブリッドモードにフォールバックし、道路結果のみを返す。いかなる入力に対しても何らかの有効な経路を返すという堅牢性の確保が、この非対称なモード決定の設計意図である。

経由地が複数ある場合、各区間（leg）は互いに独立した探索問題として並列に処理される。道路探索の実体は I/O バウンドな SQL 実行であるため、非同期並列モデルとの親和性が高く、直列実行と比べて総レイテンシを $\sum T_i$ から $\max(T_i)$ に削減できる。

3. 多目的コスト合成と重みの正規化

道路グラフの辺コストと格子グラフのセルコストは、いずれも同一の合成式によって算出される。これにより「モードをまたいでも最適化の基準が一致する」という整合性を保証する。

四種類の目的——時間 $C^t$、距離 $C^d$、リスク $C^r$、エネルギー $C^e$——に対してユーザーは非負の重み $w_t, w_d, w_r, w_e \geq 0$ を与える。合計 $s = w_t + w_d + w_r + w_e$ で各重みを正規化する。

\tilde{w}_i = \frac{w_i}{s}, \qquad \sum_i \tilde{w}_i = 1
\tag{1}

この正規化済み重みを用いた多目的合成コスト $C$ を次式で定義する。

C = \tilde{w}_t C^t + \tilde{w}_d C^d + \tilde{w}_r C^r + \tilde{w}_e C^e
\tag{2}

時間はメートルを速度で割った秒、距離はメートル、リスク・エネルギーは後述の無次元スカラーであり、三者は単位が異なる。式 (1) の正規化によって「相対的な重要度だけ」がコストに反映されるため、単位の差異による支配を防ぐことができる。

主目的が一つに決まっている場合（たとえば時間最小のみ）は、対応する $\tilde{w}_t = 1$、残りは 0 とする。合計 $s \leq 0$ の場合は時間最小にフォールバックする。複数の主目的を同時に指定することは理論上可能だが、制約が厳しくなるほど実行可能経路が存在しなくなるリスクが高まるため、原則として一つ（多くても二つ）に限定することを推奨する。

道路の辺コストと格子のセルコストの両方でこの合成コスト $C$ が共通して用いられることが、モードをまたいだ最適化基準の一致を保証する根拠である。

4. 徒歩速度モデル

徒歩移動における時間コストを算出するにあたって、本システムは Tobler（1993）のハイキング関数を採用している。従来の単純な「傾斜が急なほどコスト増」というモデルは、登り坂と下り坂を対称に扱う点で実地形と乖離していた。Tobler 関数は勾配 $S = \tan\theta$（$\theta$ は傾斜角）に対する歩行速度 $W(S)$（km/h）を次のように定義する。

W(S) = 6 \cdot \exp\!\bigl(-3.5 \cdot |S + 0.05|\bigr)
\tag{3}

この式が示す最も重要な性質は非対称性である。最適勾配 $S = -0.05$（傾斜角 $\theta \approx -2.86°$、わずかな下り）のとき指数部がゼロとなり、最大速度 $W = 6.00$ km/h に達する。平坦地（$S = 0$）では $W(0) = 6 \cdot \exp(-3.5 \times 0.05) \approx 5.04$ km/h となり、最速点よりわずかに遅い。上り勾配では傾斜の増加とともに指数的に速度が低下し、急な下り勾配でも同様に低下する。その結果グラフは $S = -0.05$ を頂点とする左右非対称の鋭い山形を描く（図 3）。

格子のセルコストへの組み込みは次の手順で行う。セル $(r,c)$ の標高データから離散勾配を算出して勾配値 $S(r,c) = \tan\theta(r,c)$ を得た後、式 (3) で歩行速度 $W(S)$ を計算する。時間コストはセル幅を $g$（メートル）として

C^t(r,c) = \frac{g}{W(S(r,c))}
\tag{4}

と定義する。分母に実測に基づく非線形速度モデルを用いることで、下り坂を含む迂回路がペナルティではなくボーナスとして扱われ、実地形に即した時間最適経路が選択されやすくなる。特に山岳地形では、直線的な急登り経路よりも緩やかに迂回する経路の方が時間的に優れる場合があり、この判断が自動化される。

5. 格子コスト設計と通行制約

5.1 勾配とセルコスト

回廊内を一辺 $g$ メートルの正方形格子に分割し、各セル $(r,c)$ に標高 $z(r,c)$ が割り当てられる。地形の険しさを表す指標として、離散勾配の大きさ $\tau(r,c)$（無次元）を次のように定義する。

\tau(r,c) \approx \sqrt{\left(\frac{\partial z}{\partial x}\right)^2 + \left(\frac{\partial z}{\partial y}\right)^2}
\tag{5}

式 (2) の合成コスト $C$ に代入する各目的の単位コスト場を、この $\tau$ を用いて次のように定義する。

\begin{aligned}
C^d &= 1 \\
C^t &= \frac{g}{W(S(r,c))} \quad \text{（式 (4) による Tobler 関数値）} \\
C^r &= 1 + 3\tau \\
C^e &= 1 + 4\tau + \tfrac{1}{2}\tau^2
\end{aligned}
\tag{6}

距離コスト $C^d$ は平地を基準（1.0）とし、傾斜によらず一定である。時間コスト $C^t$ は、セクション 4 で定義した Tobler 関数（式 (4)）を直接使用し、実測に基づく非線形速度モデルをそのまま反映する。リスクコスト $C^r$ は $\tau$ に線形比例して増加する設計とした。係数 3 は、距離コスト（係数なし）よりも傾斜感度を強くし、後述のエネルギーコスト（係数 4）よりは緩やかにするためのものであり、キャリブレーションにより調整することを前提とした設計値である。

エネルギーコスト $C^e$ だけが $\tau^2$ 項をもつ。生理学的観点から、急坂での消費エネルギーは傾斜に対して非線形に増大することが知られており [4]、この二次項はその実態を近似している。線形項の係数 4 は $\tau = 0$ からの立ち上がり勾配を他コストより大きく設定することで、エネルギー重みが高いときに緩斜面への誘導が早く働くよう設計した値である。いずれの係数も実運用データへのキャリブレーションによって調整することを前提とする。

セル $(r,c)$ の合成通行コスト $m(r,c)$ は、式 (1)(2)(6) を組み合わせると

m(r,c) = \tilde{w}_t C^t + \tilde{w}_d C^d + \tilde{w}_r C^r + \tilde{w}_e C^e

となる。8 近傍格子上のステップコストはこの $m$ を用いて

\text{cost}(r_1,c_1 \to r_2,c_2) = \sigma \cdot \frac{m(r_1,c_1) + m(r_2,c_2)}{2},
\qquad \sigma = \begin{cases} 1 & \text{縦横移動} \\ \sqrt{2} & \text{斜め移動} \end{cases}
\tag{7}

と定義する。どちらかのセルが通行不可のとき $\text{cost} = \infty$ とする。両端セルの平均をとることで、セル境界をまたぐコストが連続的に変化するよう設計している。なお式 (6) において $C^t$ は秒・$C^d$ はメートル相当・$C^r$ と $C^e$ は無次元の近似値であり、単位が統一されていない。式 (1) の正規化によって「相対的な重要度だけ」が合成コストに反映されるため、単位の差異による支配は生じない（セクション 3 参照）。

5.2 通行不可制約（ハード制約）

次の条件に該当するセルは $\text{cost} = \infty$ として探索対象から除外される。優先順位は以下のとおりで、上位の制約が下位より常に優先する。

通行不可の優先順位

1. 勾配が上限 $\tau_{\max}$ を超過
2. 標高データ欠損（NoData）
3. 土地被覆の禁止クラス（水域・建物内部等）
4. 土地被覆クラス別コスト倍率（ソフト制約として最後に乗算）

土地被覆クラス別のコスト倍率はキャッシュの指紋（後述）に含まれるため、倍率を変更した際に古いキャッシュが誤って再利用されることはない。

6. 道路スナップ

ユーザーが指定した座標点 $p$ は、道路グラフの辺上にあるとは限らない。グラフ上の最短路アルゴリズムに渡す前に、$p$ を「最も適切な辺上の点」に投影するスナップ処理が必要である。

任意のセグメント $e$ に対する点 $p$ の最短距離を以下の通り定義する。

D(e,\,p) = \min_{x \in e} d(x,\,p)
\tag{8}

• $d(\cdot,\cdot)$：Haversine 近似による大円距離

全辺を毎回ソートするのは非効率であるため、空間インデックスを用いて距離の近い上位 $k$ 本のセグメント集合 $N_k$ を列挙する。集合内での最短距離を $d^* = \min_{e \in N_k} D(e,p)$ としたとき、同点許容幅 $\delta$（メートル）を用いた同点帯

T = \{\, e \in N_k \mid D(e,\,p) \leq d^* + \delta \,\}
\tag{9}

を構成し、その中から辞書式順序——第一キーは距離 $D(e,p)$ 最小、同距離なら第二キーとしてセグメント長 $\ell(e)$ 最大——で最終辺 $e^*$ を選ぶ。

この二段階選択の設計意図は、交差点付近で複数セグメントが近接する場合に「短い枝道」ではなく「長い本線側」に吸着させることである。セグメント長が長いほど幹線道路である可能性が高いという経験則に基づく。

空間索引には二種類を用意している。既定は DB 内の空間インデックス（$O(\log n)$ クエリ）であり、道路データの更新が即時に反映される。高スループットが必要な場合に限り、プロセス起動時に全辺をインメモリの空間木（STRtree、$O(\log n)$ 検索）に読み込む方式を選択できる。後者は DB 往復を削減できる反面、道路更新後はプロセス再起動が必要という運用上の制約を伴う。

7. 道路最短経路

7.1 辺コストの合成

道路グラフ $G = (V, E)$ において、各辺 $e \in E$ には目的別の基準コスト ${C^t(e), C^d(e), C^r(e), C^e(e)}$ があらかじめ格納されている。実際に最短化するスカラー辺コストは、セクション 3 で定義した式 (1)(2) を各辺に適用した

C(e) = \tilde{w}_t C^t(e) + \tilde{w}_d C^d(e) + \tilde{w}_r C^r(e) + \tilde{w}_e C^e(e)
\tag{2（再掲）}

によって与えられる。逆方向の辺には対称な逆方向コストが存在する場合はそれを用いる。式 (2) は格子のセルコスト（セクション 5.1）でも同じ形で使われており、重みベクトル $\tilde{\boldsymbol{w}}$ を共通にすることでモードをまたいだ最適化基準の一致を保証している。

7.2 Contraction Hierarchies の原理と計算量

Contraction Hierarchies（CH）は Geisberger などが提案した前処理型最短路アルゴリズムである。その中心的なアイデアは次の二段階からなる。

前処理（オフライン）： グラフの全頂点に「重要度」ランクを割り当て、ランクの低い頂点から順に縮約（contract）する。頂点 $v$ を縮約する際、$v$ を経由する最短路が失われないよう隣接頂点間にショートカット辺を追加する。この処理で元のグラフは階層構造をもつ拡張グラフ $G^*$ に変換される。前処理の時間計算量は実用的な道路グラフで $O(m \log n)$（$n$ は頂点数、$m$ は辺数）のオーダーに収まることが知られているが、縮約戦略の選択に依存する。

クエリ（オンライン）： 出発点 $s$ からの前向き探索と目的点 $t$ からの後向き探索を双方向で行い、どちらの探索もランクが増加する方向にのみ辺をたどる。両探索が合流する頂点で最短路コストが確定する。

計算量の比較（実用的な道路グラフにおける近似）

• Dijkstra（単純）：$O((n + m) \log n)$
• 双方向 Dijkstra：$O((n + m) \log n)$　　// 定数項は約 $1/2$
• CH クエリ：$O(n^\varepsilon \cdot \log n)$　　// $\varepsilon < 1$、実用的には定数クエリに近い

7.3 辺の途中にある仮想ノードと CH の整合

スナップ処理が道路の途中（辺の内分点）を出発点・目的点として返す場合、それらの仮想ノードは $G^*$ の頂点集合に含まれない。この問題を解決するアプローチとして三種類が考えられる。

案	概要	精度	実装コスト	採用
① 端点丸め	仮想ノードを辺の最近傍実頂点に丸め、CH クエリに載せる	fraction 分だけ位置ずれ	低	◎
② 動的挿入	クエリごとに仮想ノードを $G^*$ に挿入してミニ CH を実行	理論上は精緻	極めて高	—
③ ステッチ	仮想ノード→最近傍実頂点まで局所 Dijkstra、以降 CH に引き渡す	実用的精度	高	—

本システムでは案①を採用し、スナップが辺の端点に一致した場合のみ CH を適用する。それ以外は仮想ノード対応の最短経路探索にフォールバックする。案③は OSRM や Valhalla などの実運用エンジンで採られている現実的な折衷案だが、乗換点の選択・コスト一貫性・ゴール側の対称処理という三つの論点を正しく設計・検証するコストが、現在のシステム規模では端点特化の分岐よりも大きいと判断した。

8. 格子探索アルゴリズムの選択と HPA*

8.1 アルゴリズムの選択基準

格子グラフ上の最短路問題に対して、本システムは次の三アルゴリズムを用途に応じて切り替える。

Dijkstra は非負コストグラフに対して常に最適解を保証し、計算量は優先度付きキューを用いる場合 $O((|V|+|E|)\log|V|)$ となる。8 近傍格子では $|E| = O(|V|)$ であるから実質 $O(|V|\log|V|)$ である。

A* はゴールまでの距離を過小評価する許容ヒューリスティック $h(v)$ を導入することで探索空間を絞る。現在ノードとゴールの座標差を $\Delta x,,\Delta y$ として、8 近傍格子ではオクタイル距離

h(v) = \max(|\Delta x|, |\Delta y|) + (\sqrt{2} - 1) \cdot \min(|\Delta x|, |\Delta y|)
\tag{10}

が許容ヒューリスティックとして機能し、最適解を保証したまま探索ノード数を大幅に削減できる。実用的なグリッドマップ上では Dijkstra の 3〜10 倍程度の高速化が得られることが多い。

アルゴリズム	最適性	計算量（格子 $|V|$）	適用場面
8近傍 Dijkstra	◎ 厳密最短	$O(|V| \log |V|)$	狭い領域・基準計算
A*（オクタイル、式 (10)）	◎ 厳密最短	$O(|V| \log |V|)$（定数小）	標準設定。高速かつ最適
HPA*	〇 準最適（誤差 ≤ 1%）	$O(|V|^{1/2} \log |V|)$	広域。A* の最大 10 倍高速
HPA* 失敗時 A*	◎ 厳密最短	$O(|V| \log |V|)$	フォールバック。最短性担保

8.2 HPA*（Hierarchical Pathfinding A*）の構造

Botea などが提案した HPA* は、大規模格子マップに対して A* の探索空間が $O(|V|)$ で爆発する問題に対処するための階層化手法である。基本アイデアは格子を局所クラスタに分割し、クラスタ境界上の「ポータル」だけで構成する抽象グラフを事前計算することにある。

前処理： グリッドをサイズ $s \times s$ のクラスタに分割する。各クラスタ境界の通行可能領域から代表ポータル対を生成し、クラスタ内の最短路をキャッシュしてポータル間コストを事前計算する。抽象グラフのノード数は全格子 $|V| = W \times H$ に対して $O(|V|/s^2)$ に削減される。

クエリ： 出発点・目的点をそれぞれ最近傍ポータルに接続した後、抽象グラフ上で A*（式 (10)）を実行する。得られた抽象経路の各クラスタ区間を低レベルの経路に展開（refine）して最終経路を得る。HPA* の準最適性は実験的に最適解から 1% 以内に収まることが確認されており [2]、商用ゲームエンジンで広く採用されている所以でもある。

HPA* の計算量の概算

• 前処理：$O(|V| / s^2)$　　　　　　// 抽象グラフ構築
• クエリ：$O(|V|^{1/2} \cdot \log|V|)$　// 抽象 A*（式 (10) を使用）
  ※ $s$ を大きくするほどクエリは速いが精度は落ちる

本システムでは推定セル数に応じてクラスタサイズを動的に決定する。抽象グラフが通れない（孤立クラスタ等）場合は A* にフォールバックし、最短性を担保する。

9. 解像度ピラミッドによる多段探索

格子のセル数 $|V| = (W/g) \times (H/g)$ はセル幅 $g$ の二乗に反比例して増加する。たとえば回廊が 2 km × 2 km で $g = 2$ m なら $|V| = 10^6$、$g = 1$ m なら $|V| = 4 \times 10^6$ に達し、直接 A* を適用すると探索時間が実用水準を超えうる。

この問題に対して本システムは粗→細の多段探索を採用する。まず粗い格子（セル幅 $g_0$）で広い回廊全体を探索して大局ルートの骨格を得る。次にその骨格経路の周囲にバッファを設けた細い矩形領域だけを高解像度で再探索する。この手法の計算量上の優位性は次のように定式化できる。

\begin{aligned}
\text{単純全面} &: O\!\left(\frac{WH}{g^2} \log \frac{WH}{g^2}\right) \\[6pt]
\text{2段多段} &: \underbrace{O\!\left(\frac{WH}{g_0^2} \log \cdots\right)}_{\text{粗探索}} + \underbrace{O\!\left(\frac{Lw}{g^2} \log \cdots\right)}_{\text{細探索}}
\end{aligned}
\tag{11}

$w \ll W$ かつ $L \ll WH/g$ であれば、細探索の項が支配的でも総計は大幅に削減される（$L$ は大局ルート長、$w$ はバッファ幅）。

10. ハイブリッドパイプライン

ハイブリッドモードでは、まず道路経路 $\Gamma$（折れ線）を算出し、その全頂点とスナップ後の出発・目的点を包む最小矩形にバッファ幅 $B$（メートル）を加えた回廊 bbox を自動生成する。緯度方向の換算係数を $A \approx 111{,}320$ m/deg、代表緯度を $\bar\phi$ とすると、

\Delta\phi = \frac{B}{A}, \qquad
\Delta\lambda = \frac{B}{A \cdot \max(\cos\bar\phi,\; 0.2)}
\tag{12}

この $\cos\bar\phi$ のクランプ値 0.2 は高緯度での数値不安定化を防ぐためである。回廊の内部だけでセクション 9 の解像度ピラミッド探索を実施する。リクエストで指定できるのはバッファ幅 $B$ だけであり、探索範囲そのものをユーザーが直接指定するものではない。

統合戦略は設定に応じて次の三種類から選択される。

戦略	設定	ピラミッド段数	特性と設計意図
A：2段高速	ピラミッド有効 ＋ 高速モード	L0 → L3	L1・L2 を省略して最速。精度より速度が優先される場面向け。
B：4段標準	ピラミッド有効（通常）	L0→L1→L2→L3	条件によって L2 を省略する自動最適化あり。精度と速度のバランス型。
C：クラシック2段	ピラミッド無効	粗（L0）→細（L3）	道路計算と標高グリッドのウォームアップを非同期並列化できる。道路計算の待ち時間に標高 I/O を先行して実施し、格子探索の I/O 待ちをほぼゼロにする設計。

DTM が存在しない場合は格子探索をスキップして道路結果のみを返す。「道路優先」のハイブリッドにおいて道路区間は必ず存在するため、フォールバックしても有効な経路が返ることが保証される。

11. 応答整形と route_profile の設計

地図表示用の経路データ（GeoJSON 折れ線）と、傾斜・距離・所要時間を含む分析用プロファイルは、責務を分離して独立に生成する。この分離の根拠は、表示のために複数フィーチャを一本化すると境界情報が失われ、セグメント単位の分析精度が低下するからである。プロファイルは常に一本化前の細粒度 Feature 列を入力とし、地図表示と分析の粒度が食い違うことを許容する設計としている。

各セグメントの水平長は Haversine 公式による大円距離でメートル換算する。標高が利用可能な場合、セグメント水平長を $\ell$、両端頂点の標高を $z_1,,z_2$ として傾斜角は

\theta_{\text{seg}} = \arctan\!\left(\frac{z_2 - z_1}{\ell}\right) \times \frac{180}{\pi}
\tag{13}

で算出する（どちらかが null のとき $\theta_{\text{seg}} = \text{null}$）。なお式 (13) で得られる傾斜角から勾配 $S = \tan\theta_{\text{seg}}$ を求めれば、セクション 4 の Tobler 関数（式 (3)）に直接代入して徒歩所要時間を再計算することができる。

所要時間は二系統を提供する。

• 推定 ETA： セグメント長 ÷ 代表速度（車両用・徒歩用を設定で指定）の積算。探索コストとは独立して算出される。
• ソルバコスト： 探索ソルバが出力した総コストを秒として解釈した値。最適化目的が時間最小である場合にのみ意味をもち、多目的設定（時間・リスク・エネルギーを混合）では null となる。

ハイブリッドモードでは「どちらの区間のコストを所要時間として使うか」を道路優先・オフロード優先の設定に従って固定する。

12. コンテナ構成

本システムは Kubernetes クラスタ上の複数コンテナとして展開される。処理特性の違いに基づき三種類のノードプールを設定し、各コンポーネントを特性の合ったプールに配置する。オンライン処理（リクエスト応答）とオフライン処理（事前ビルド）は完全に分離されている。

コンテナ	役割	ノードプール	スペック目安
api-gateway	認証・ルーティング・レート制限	低レイテンシ	CPU 16コア / RAM 64〜128 GB / NVMe 1〜2 TB
orchestrator	モード判定・重み正規化・並列制御	低レイテンシ	同上
road-router	道路グラフ常駐・CH クエリ	低レイテンシ	同上
offload-worker	格子グラフ探索（A* / HPA*）	重計算	CPU 32〜64コア / RAM 128〜256 GB / NVMe 2〜4 TB
corridor-builder	回廊 bbox 生成・DTM タイル取得（式 (12) を適用）	重計算	同上
tile-service	COG 形式 DTM の部分読み込み	I/O 優先	CPU 16〜32コア / RAM 128 GB以上 / NVMe 4〜8 TB
redis	経路 / 標高格子キャッシュ（2層）	I/O 優先	同上
postgis	道路グラフ・空間インデックス	I/O 優先	同上

13. キャッシュ戦略

同一条件への再計算を避けるため、Redis に二種類のキャッシュを独立した設計で実装する。両者を独立させる根拠は、標高グリッドデータが出発・目的点に依存しないという事実にある。同じ回廊・格子設定で異なる出発・目的のリクエストが来ても、標高 I/O を共有できるよう、標高グリッドは経路キャッシュとは別のキーで管理する。もし共通キーで管理すると、出発点が 1 点変わるだけで高コストな標高 I/O が再実行される。

• 経路キャッシュ：

  • 経路キャッシュのキーは、探索モード・格子設定・スナップ数値・ピラミッド設定・代表速度・出発目的座標（量子化済み）を含むフィンガープリントハッシュで構成される。
  • 量子化の粒度はファジーマッチモードで調整可能であり、近傍の座標を同一キーとして扱うことで高いヒット率を得られる（応答の cache フィールドに hit_fuzzy として記録される）。

• 標高格子キャッシュ：

  • 標高格子キャッシュのキーは回廊 bbox・格子セル幅・解像度・DTM 指紋（GeoTIFF のファイル情報またはテーブルサイズ）のみで構成され、出発・目的を含まない。
  • DTM 側のテーブルサイズが変化しない更新では指紋が変わらないため誤ったキャッシュヒットが起きうる。
  • 大規模更新後は指紋オーバーライドを変更するか、明示的にキャッシュを無効化する運用が必要である。

GeoTIFF の読み込みは回廊 bbox（式 (12) で算出）に合わせた部分読み込みで実施するため、広大な国土全体のラスタをメモリに展開する必要はなく、必要な矩形領域だけを固定グリッドへ再投影して扱う。Redis の 1 キーあたりのペイロード上限は既定 25 MB に設定しており、float32 で 4 バイト/セルの見当から、広い回廊と細い格子の組み合わせでは最大セル数パラメータとの調整が必要になる場合がある。

総評

ハイブリッド経路探索エンジンの実験結果、素晴らしい成果ですね。総評セクションを書きます。

---

総評

本実験では、PostGIS/pgRouting ベースの道路グラフと DTM ラスターグリッドを統合したハイブリッド経路探索エンジンについて、実地データを用いた動作検証を行った。

精度面では、道路優先モード・オフロード優先モードの双方において、地形・道路網に沿った妥当な経路が生成されており、実用上の精度水準を満たしていることを確認した。

図10 (a) の道路優先経路では、市街地の道路ネットワークを適切にトレースした経路が、図10 (b) のオフロード経路では、山間部の等高線形状に追従した経路が、それぞれ得られており、モード切替の挙動も期待通りである。

パフォーマンス面では、初回リクエスト時に DTM グリッドの構築と Redis へのキャッシュ書き込みが発生するため、道路優先、オフロード優先ともに、約 3～5 秒の初期レイテンシが生じる。

しかし 2 回目以降はキャッシュが有効化され、道路優先では 89～413 ms、オフロード優先では 112〜169 ms 程度まで大幅に短縮された。これはウォームアップ後の応答性として十分実用的な水準であり、bbox とDTM ファイルフィンガープリントをキャッシュキーとする設計の有効性が実証された形となる。

課題と展望としては、初回レイテンシの削減が次の改善ポイントとなる。頻繁にアクセスされるタイルの事前ウォームアップ（プリフェッチ）や、Contraction Hierarchies (CH) の導入による探索グラフの圧縮が有効な対策として挙げられる。また、GeofabrikPBF を用いた全国 OSM データの取り込みパイプラインと組み合わせることで、より広域かつ高密度な道路ネットワークへのスケールアウトが見込まれる。

総じて、本エンジンは精度・応答性ともに基本要件を達成しており、実運用フェーズへの移行に向けた基盤として十分な完成度を持つと判断できる。

付録 A. 制約とデータソース

区分	制約項目	利用データ	種別
地形・物理	最大斜度超過（式 (5) の $\tau > \tau_{\max}$） / 崖・段差	DTM	ハード
地形・物理	水域（渡渉不可）/ 地盤支持力不足	土地被覆図 / 土壌図	ハード
人工物・インフラ	橋梁耐荷重 / トンネル高さ / 幅員不足	道路地図（OSM等）	ハード
人工物・インフラ	森林・藪 / 谷筋	土地被覆図 / DTM / 道路地図	ソフト減
規則・状況	立入禁止	国土数値情報 / ユーザ設定	ハード
規則・状況	通信不安定 / 情報不確実	電波シミュレーション / 道路地図	ソフト増
規則・状況	高速道路 / 代替路多	道路ネットワーク	ソフト減

付録 B. 探索アルゴリズムの系譜

アルゴリズム	分類	計算量	最適性	位置づけ
Dijkstra（1956）	探索制御型	$O((V+E)\log V)$	◎ 最適	基礎。格子 8 近傍で常用（式 (7)）
A*（1968）	探索制御型	$O((V+E)\log V)$（定数小）	◎ 最適	標準。オクタイルヒューリスティック（式 (10)）
CH（2008）	前処理型	クエリ $O(n^\varepsilon \log n)$	◎ 最適	道路辺コスト（式 (2)）を用い端点限定で適用
HPA*（2004）	階層化型	$O(|V|^{1/2} \log |V|)$	〇 準最適（≤1%）	広域格子（式 (11) の優位性を享受）
D* Lite（2002）	増分再計画型	差分更新	◎ 最適（動的）	障害物変化時の再計画（任意）
ARA*（2007）	Anytime 型	時間制御可	〇 準最適→収束	時間制約付き探索（任意）
Theta*（2010）	Any-angle 型	A* 相当	〇 近似最短	格子制約を外した短い経路生成
JPS（2011）	対称性除去型	A* の 1/10 以下	◎ 最適	等コスト格子での A* 高速化候補

太字：現システムで主として使用。D* Lite・ARA* は動的環境・時間制約がある場面で組み合わせる。

付録 C. メッシュサイズの設計根拠

格子のセル幅 $g$ は、通行可否の判定精度と計算量のトレードオフで決まる。式 (11) からわかるとおり、セル幅を半分にすると格子のノード数は 4 倍になり、探索時間は概ね 4〜6 倍増加する。段差（0.3〜1.0 m）・溝（幅 1〜3 m）・低い壁（0.5〜1.5 m）といった障害物の寸法から、通行可否を識別するには $g \leq 1$ m が実質的な下限となる。

セル幅	ノード数比（10m=1）	探索時間比（式 (11) より）	用途
10 m	1×	1×	大局探索（L0）
5 m	4×	4〜6×	中解像補完（L1）
2 m	25×	25〜40×	回廊絞込み（L2）
1 m	100×	100〜180×	最終解（L3）。採用下限
0.5 m	400×	400〜800×	実用的でない

粗いメッシュで生じる問題の本質は平均化による非線形破壊である。たとえば 10 m セルでは、セル内に 1 m の壁が存在しても標高の平均値は緩やかになり、式 (5) の $\tau$ がほぼ 0 に見えてしまう。このため粗いレベル（L0/L1）では大局的な方向性の決定のみに使い、最終的な通行可否判定は必ず細いセル（L3：1〜2 m）で実施する設計としている。

車両種別と最小検出すべき障害物の対応は、徒歩・軽車両で 0.5〜1 m　を推奨値として設定した。なお車両は点ではなく剛体であり、腹摺り判定を厳密に行うには車両の長さ・底面高さ・接地圧も考慮する必要があるが、現バージョンでは傾斜の上限閾値（$\tau_{\max}$）でこれを近似している。

参考文献

1. Geisberger, R., Sanders, P., Schultes, D., Delling, D. (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks*. WEA 2008. https://turing.iem.thm.de/routeplanning/hwy/contract.pdf
2. Botea, A., Müller, M., Schaeffer, J. (2004). Near Optimal Hierarchical Path-Finding (HPA*). Journal of Game Development. https://www.researchgate.net/publication/228785110_Near_optimal_hierarchical_path-finding_HPA
3. Tobler, W. (1993). Three Presentations on Geographical Analysis and Modeling. UCSB Technical Report. https://escholarship.org/uc/item/05r820mz
4. Minetti, A. E., Moia, C., Roi, G. S., Susta, D., Ferretti, G. (2002). Energy cost of walking and running at extreme uphill and downhill slopes. Journal of Applied Physiology. https://journals.physiology.org/doi/pdf/10.1152/japplphysiol.01177.2001
5. Koenig, S., Likhachev, M. (2002). D* Lite. AAAI 2002. https://cdn.aaai.org/AAAI/2002/AAAI02-072.pdf
6. Likhachev, M., et al. (2003). ARA*: Anytime A* with Provable Bounds on Sub-Optimality. NIPS 2003. http://papers.neurips.cc/paper/2382-ara-anytime-a-with-provable-bounds-on-sub-optimality.pdf
7. Nash, A., Daniel, K., Koenig, S., Felner, A. (2010). Theta*: Any-Angle Path Planning on Grids. JAIR. https://arxiv.org/pdf/1401.3843
8. Harabor, D., Grastien, A. (2011). Online Graph Pruning for Pathfinding on Grid Maps (JPS). AAAI 2011. https://harabor.net/data/papers/harabor-grastien-aaai11.pdf