道路網とグリッド地形コストを統合したハイブリッド経路探索システムの設計と実装

マルチレゾリューション・ピラミッド探索による道路・不整地統合ルーティング

要旨

道路網に基づく経路探索（カーナビゲーション等）と、道路の存在しない不整地における地形ベースの経路計画は、従来別個の技術領域として扱われてきた。しかし登山・トレイル探索、オフロード車両の走行計画、災害等により道路が寸断された状況での迂回路探索など、両者を単一の枠組みで扱う必要のある応用は少なくない。本稿では、PostGIS/pgRouting による道路網最短経路探索と、数値標高モデル（DTM）・土地被覆データに基づくグリッドベースの不整地経路探索を統合した、ハイブリッド経路探索システムの設計と実装について述べる。

本システムは、

地理 K 最近傍探索と同点帯によるロバストな道路スナップ
pgr_withPoints と Contraction Hierarchies（CH）を状況に応じて使い分ける道路網最短経路探索
Tobler の徒歩速度関数に基づく地形コストモデルと Dijkstra／A*／HPA* を切り替え可能なグリッド経路探索
道路経路周辺に自動生成した回廊内で粗い格子から細かい格子へと段階的に絞り込む多重解像度（ピラミッド）探索

という4つの要素技術から構成される。

本稿ではこれらのアルゴリズムを数式・疑似コード・計算量とともに整理し、OSRM／Valhalla に代表される既存の道路網ルーティングエンジンおよびロボティクス分野のグリッド経路計画手法との位置づけを比較する。さらに、システムアーキテクチャ、API 設計、リクエスト処理シーケンス、データベーススキーマ、キャッシュ機構を含む実装上の工夫を報告するとともに、CH を辺上任意点間の経路探索へ拡張する際に生じる3通りの設計選択肢とそのトレードオフを考察する。なお本稿は設計・実装の記述と理論的な計算量分析を主眼とし、実データ規模での定量的なベンチマーク測定は範囲外としている（7.3節で評価方針として位置づける）。

キーワード: 経路探索、道路網ルーティング、地形コストモデル、Contraction Hierarchies、階層的経路探索（HPA*）、多目的最適化、PostGIS/pgRouting

1. はじめに

一般に公開されている経路探索サービスの多くは、道路網を有向グラフとして表現し、Dijkstra 法や A* 法、あるいはその高速化手法である Contraction Hierarchies（CH）を用いて最短経路を計算する道路網ルーティングに特化している。一方、登山道や踏み跡程度の情報しかない山野、災害によって道路網が寸断された地域などでは、道路データそのものが存在しない、あるいは信頼できないため、数値標高モデル（Digital Terrain Model, DTM）や土地被覆データから地形の通行コストを見積もり、グリッド上の経路探索を行う不整地経路計画（off-road path planning）が必要になる。

これら2つの技術領域は、要求されるデータ構造（グラフ vs. グリッド）、コストの性質（線分単位 vs. セル単位）、探索アルゴリズムの選択（グラフ最短路 vs. 格子最短路）が大きく異なるため、実装上は独立したサブシステムとして扱われることが多い。しかし実際の移動計画では、「道路を使えるところまでは道路を使い、道路が途切れた区間だけ地形を考慮した迂回路を計画する」というように、両者を切れ目なく接続する必要が生じる場面が多い。

本稿で扱うシステム（以下「本システム」）は、この課題に対して、道路経路の周囲に探索範囲（回廊）を自動生成し、その内部でのみ地形グリッド探索を行うことで道路網と不整地グリッドを接続する、ハイブリッド経路探索方式を実装したものである。さらに、不整地側の計算コストを抑えるため、粗い解像度のグリッドで大域的な経路を求め、その周辺だけを段階的に細かい解像度で再探索する多重解像度（ピラミッド）方式を採用している。

本稿の構成は以下の通りである。2章で関連研究を概観し、既存の道路網ルーティングエンジン・グリッド経路計画手法との位置づけを比較する。3章でシステム全体のアーキテクチャを述べる。4章では道路スナップ、道路網最短経路、不整地グリッド探索、ハイブリッド統合の各アルゴリズムを数式・疑似コード・計算量とともに詳述する。5章で実装上の工夫（データ基盤、API 設計、キャッシュ、リクエスト処理シーケンス、データベーススキーマ、データ取り込み）を述べ、6章で CH 統合における設計上のトレードオフを考察し、7章でスコープ外の事項・未解決の設計課題・評価方針を含む制限事項と今後の課題を述べる。

2. 関連研究

2.1 道路網最短経路探索

Dijkstra 法 [1] は非負辺重みグラフにおける単一始点最短経路問題を多項式時間で解く古典的手法であり、双方向探索（bidirectional Dijkstra）はその探索空間を約半分に削減する実用上重要な変種である。A* 法 [2] は許容的ヒューリスティックを用いて探索順序を最適化し、実用上大幅な高速化を実現する。大規模道路網に対する前処理型高速化手法として、Contraction Hierarchies（CH）[3] は頂点を重要度順に縮約し、ショートカット辺を追加することで、オンラインクエリを対数的な計算量に近づける。Delling ら [6] はこうした前処理型高速化手法（CH、Arc-Flags、Hub Labeling 等）を体系的にサーベイしており、道路網ルーティングの高速化手法群の全体像を与える。OSRM [7] は CH を用いてリアルタイムに近い応答を実現する実運用エンジンであり、Valhalla も同様に前処理型グラフ縮約を採用している。これら既存エンジンは道路網単体の最短経路計算を対象としており、地形コストに基づく不整地探索や、道路網とグリッドの動的な接続は主要な設計対象になっていない。

2.2 不整地・グリッドベース経路計画

移動可能領域を正方格子として離散化し、各セルに地形由来のコストを割り当てて最短路を求める手法は、ロボティクスや地理情報科学の分野で広く用いられる。徒歩移動速度を地形勾配の関数として近似する Tobler のハイキング関数 [4] は、地形コストモデルの代表的な経験式である。広域グリッドにおける探索の高速化には、クラスタ分割と抽象グラフを用いる階層的経路探索（Hierarchical Path-finding A*, HPA*）[5] が知られており、クラスタ境界に配置したポータル間の抽象グラフ上で大域探索を行うことで、計算量を削減する一方、厳密最短性を保証しない場合があるというトレードオフを持つ。動的環境やセンサ情報の逐次更新を前提とするロボティクス分野では、D* Lite [8] や ARA*（Anytime Repairing A*）[9] のように、環境変化や計算時間予算に応じて経路を漸進的に再計算するインクリメンタル探索も発展している。本システムは静的な DTM・土地被覆データを前提とした一括計算を対象としており、これらの漸進的再計画手法は採用していない（7章で今後の課題として述べる）。

2.3 ハイブリッド・多目的経路計画の位置づけ

上記2領域は、データ構造（グラフ vs. グリッド）とコストの単位（線分 vs. セル）が異なるため、実装上は独立に発展してきた。道路網側では時間・距離・料金等を組み合わせた多目的（multi-criteria）経路探索が、不整地側では勾配・エネルギー消費・踏破性を組み合わせた地形コストモデルが、それぞれ個別に研究・実装されている。しかし「道路網が使える範囲は道路網を、途切れた区間は地形コストに基づくグリッド経路で補う」という、単一リクエスト内で2つの探索空間を切れ目なく接続し、かつ両者に共通の多目的重みベクトルを適用する枠組みは、個別の道路網エンジンやロボティクス向けグリッドプランナのいずれの主要な設計対象にもなっていない。本システムはこの間隙に対して、道路経路から自動生成した回廊内でのみグリッド探索を行うという限定的だが具体的な統合方式を提案するものである。

2.4 GIS 基盤上のルーティングと関連システムの比較

PostGIS は空間データに対する索引（GiST）と幾何演算を提供する空間データベース拡張であり、pgRouting はその上に Dijkstra・双方向 Dijkstra・pgr_withPoints（辺上の任意点をノードとして扱う最短経路）などのグラフアルゴリズムを実装するライブラリである。本システムはこれらを道路網側の基盤として採用し、不整地側は独自のグリッド経路探索モジュールで補完する構成をとる。表3 に、代表的な道路網ルーティングエンジンおよび汎用グリッドプランナと本システムの設計上の違いを整理する。

比較軸	OSRM／Valhalla	汎用グリッドプランナ（ロボティクス）	本システム
対象空間	道路網のみ	占有格子（2D/3Dグリッド）のみ	道路網＋グリッドの動的接続
主要アルゴリズム	CH／その発展形	A、D Lite、ARA* 等	pgr_withPoints／CH（端点限定）＋ Dijkstra／A／HPA
多重解像度	タイル分割はあるが探索自体は単一解像度	一般に単一解像度（階層グリッドは研究例あり）	ピラミッド型 L0〜L3 の段階的絞り込みを標準実装
コストモデル	道路属性ベース（時間・距離中心）	占有・コストマップ（用途依存）	4目的（時間・距離・リスク・エネルギー）の正規化線形結合を道路・グリッド双方に共通適用
動的再計画	非対応（都度再計算）	D* Lite 等で対応する実装が多い	非対応（本稿執筆時点、7章参照）
前提データ	道路網グラフ	占有格子／コストマップ	道路網（PostGIS）＋ DTM／土地被覆／水域／建物ラスタ・ベクタ

表3の比較が示すように、本システムの技術的な特徴は個々の要素技術（CH、A*、HPA*等）そのものの新規性ではなく、それらを道路網とグリッドの間で使い分けながら、共通の多目的重みベクトルと多重解像度探索の枠組みで接続している点にある。

3. システム概要

本システムは FastAPI によるルーティング API、PostGIS/pgRouting による道路網データベース、Redis による経路・標高格子キャッシュ、Celery による非同期ジョブ実行、nginx によるゲートウェイから構成される（図1）。データ取り込みは OSM（OpenStreetMap）の bbox 単位取得または Geofabrik 配布の PBF ファイルから行い、道路網テーブルおよびそのトポロジを構築する。不整地側は DTM・土地被覆・水域・建物の各データを GeoTIFF またはベクタ形式で読み込み、要求のあった経路周辺のみを対象にラスタ演算を行う。

図1. システムアーキテクチャ概要

API は主として POST /route/（結果を DB に保存し route_id を返す）と GET /route/compute（Redis キャッシュ対象の即時計算）の2系統を提供する。リクエストは mode（road / offroad / road+offroad）を明示指定するか、priority（road_first / offroad_first）と DTM の有無から resolved_mode を自動決定する。

フィールド	説明
`start` / `goal`	出発・目的地点（緯度・経度）
`waypoints`	経由地（最大32点）。指定時はセグメント分割し並列計算
`mode` / `priority`	探索モードの明示指定／優先方針からの自動決定
`objective`	`time` / `distance` / `risk` / `energy` / `multi`（多目的）
`w_time` `w_distance` `w_risk` `w_energy`	`objective=multi` 時の正規化重み
`corridor_m` `grid_m`	不整地探索の回廊バッファ幅・グリッド解像度
`slope.max_slope_deg`	通行可能な最大勾配（ハード制約）

表：主要リクエストパラメータ（詳細は docs/API.md を参照）

4. 経路探索アルゴリズム

本章で扱う主要なアルゴリズム・コンポーネントの全体像を表1に示す。詳細な数式・疑似コード・計算量は各節（4.2〜4.8）で述べる。

表1. 主要アルゴリズム・コンポーネント一覧（抜粋）

4.1 記号

記号	意味
$q_s, q_g$	出発点・目的点（緯度 $\phi$ 、経度 $\lambda$ ）
$p$	問い合わせ点（出発または目的と同一座標）
$e$	登録済みの道路セグメント（折れ線）
$G=(V,E)$	道路を頂点・辺に分割したネットワーク有向グラフ
$d(a,b)$	大円距離（メートル）
$x^\ast(e,p)$	セグメント $e$ 上で $p$ に最も近い足（射影点）
$\tau(r,c)$	格子点 $(r,c)$ における地形勾配（絶対値）
$\tilde w_t, \tilde w_d, \tilde w_r, \tilde w_e$	時間・距離・リスク・エネルギーの正規化重み（総和1）

4.2 モード決定

各リクエストは priority と DTM データの有無から実行モード resolved_mode を決定する。priority=road_first の場合は道路＋不整地のハイブリッドモードを既定とし、priority=offroad_first の場合は DTM が利用可能なら不整地単独モード、利用不可なら道路＋不整地モードにフォールバックする。図2 に、決定されたモードごとの処理系統を示す。

図2. モード別処理フロー

複数経由地が指定された場合、区間（leg）ごとに独立した経路探索が asyncio.gather によって並列実行され、区間順に結合される。

4.3 道路上へのスナップ

問い合わせ点 $p$ に対して、登録済み道路セグメントのうち実用上「最寄り」とみなせる1本を選び、その上の足 $x^\ast$ をスナップ点とする。セグメント $e$ と点 $p$ の距離は

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

と定義する（折れ線の場合は各線分への距離の最小値）。全辺を毎回比較するのではなく、PostGIS の geography 型と GiST 索引を用いた K 最近傍探索（演算子 <->）により、距離の近い順に高々 $k$ 本の候補集合 $N_k$ を取得する（ROAD_SNAP_STRTREE_ENABLED が有効な場合は Shapely STRtree による索引化とプロセス内計算に切り替え、索引が利用できない場合は PostGIS 経路にフォールバックする）。

候補内の最小距離を $d^\ast = \min_{e \in N_k} D(e,p)$ とし、しきい幅 $\delta$ による同点帯

T = \{\, e \in N_k \mid D(e,p) \le d^\ast + \delta \,\}

を設ける。これは交差点付近などでほぼ同距離の道路が並ぶ際に、極端に短い枝だけへ吸着することを避けるためのロバスト化である。最終的な選択は帯 $T$ の中で、①距離が小さいもの、②同距離なら長いセグメント（本線側）を優先する辞書式順序で決定する（図3）。スナップ距離が許容上限を超える場合は、該当地域にデータが無いものとして探索を打ち切る。

図3. 道路スナップにおける同点帯

疑似コード（道路スナップ）

function SNAP(p, k, delta):
    N_k ← KNN_QUERY(p, k)              # geography + GiST、距離順に高々 k 本
    if N_k is empty: return REJECT
    d_star ← min( D(e, p) for e in N_k )
    T ← { e in N_k : D(e, p) <= d_star + delta }   # 同点帯
    e_star ← argmin_{e in T} ( D(e, p), -length(e) )  # ①距離最小 ②同距離なら長辺優先
    x_star ← FOOT(e_star, p)
    if D(e_star, p) > MAX_SNAP_DISTANCE: return REJECT
    return (e_star, x_star, fraction)

候補取得 KNN_QUERY は PostGIS 経路では GiST 索引による $O(\log |E| + k)$ 程度の期待計算量、STRtree 経路では半径クエリ後に Python 側で候補を線形走査するため候補数に比例した計算量となる。同点帯 $T$ の構築・辞書式順序による選択は $|N_k|$ に対して $O(|N_k| \log |N_k|)$ （またはソートせず線形走査で $O(|N_k|)$ ）で行える。

4.4 道路網上の最短経路

道路セグメント $e$ の辺コストは、時間・距離・リスク・エネルギーの各基準コスト $c^{time}(e), \ldots, c^{energy}(e)$ の重み付き線形和

c(e) = \tilde w_t\, c^{time}(e) + \tilde w_d\, c^{dist}(e) + \tilde w_r\, c^{risk}(e) + \tilde w_e\, c^{energy}(e)

として合成される。出発・目的の多くは辺の途中にスナップされるため、辺 ID と内分位置（fraction）で定義される仮想ノードを両端に置き、pgRouting の pgr_withPoints により最短経路を求めるのが既定経路である。スナップ位置が辺の端点に十分近い場合に限り、実頂点間の経路として Contraction Hierarchies によるクエリを先に試行し、失敗時は pgr_withPoints にフォールバックする。グラフ側の単一始点最短路エンジンには、双方向 Dijkstra（pgr_bdDijkstra、既定）または片方向 Dijkstra（pgr_dijkstra）を設定により選択できる。

疑似コード（道路経路選択）

function ROAD_ROUTE(snap_s, snap_g, weights):
    edge_cost(e) ← w_t*c_time(e) + w_d*c_dist(e) + w_r*c_risk(e) + w_e*c_energy(e)
    if USE_CH and IS_ENDPOINT(snap_s) and IS_ENDPOINT(snap_g):
        result ← CH_QUERY(vertex_of(snap_s), vertex_of(snap_g))   # 双方向 CH
        if result succeeds: return INJECT_SNAP_ENDPOINTS(result)
    # 既定経路（辺上の仮想ノード同士）
    engine ← pgr_bdDijkstra if USE_BIDIRECTIONAL else pgr_dijkstra
    return WITH_POINTS(engine, snap_s, snap_g, edge_cost)

CH クエリはオフライン前処理（頂点の重要度順縮約とショートカット追加、前処理計算量はおおむね $O(|V|\log|V|)$ 程度）を前提に、オンラインクエリを縮約順位に基づく双方向探索へ置き換えることで、実務上ほぼ $O(\log |V|)$ に近い応答時間を狙う手法である。一方 pgr_withPoints／pgr_bdDijkstra は前処理なしで動作するが、クエリ計算量は $O((|V|+|E|)\log|V|)$ （片方向）ないしその探索空間を縮小した双方向版となる。本システムが CH を端点スナップに限定するのは、4.4節で述べた仮想ノードとの非整合を避けるための設計判断であり、辺上任意点への一般化については6章で考察する。

4.5 不整地（グリッド＋地形）における経路探索

道路経路が得られた場合、その折れ線と両端点を含む最小外接矩形を、緯度経度換算（ $A \approx 111320\,\mathrm{m/deg}$ ）に基づきメートル単位のバッファ幅 $B$ で外側に拡張し、不整地探索の対象範囲（回廊）とする。回廊内を一辺 $g$ メートルの正方格子に切り、標高 $z(r,c)$ から離散勾配 $\tau(r,c)$ を求める。

セルあたりの目的別基準コストは、Tobler のハイキング関数に基づき次のように定義される（表2）。

表2. 不整地グリッドにおけるセル単位コストモデル

これらを重み付き線形結合したスカラーコスト $m(r,c) = \tilde w_t c^{time} + \tilde w_d c^{dist} + \tilde w_r c^{risk} + \tilde w_e c^{energy}$ を用い、勾配上限超過・標高データ欠損・禁止土地被覆クラス・建物内部・水域に該当するセルは通行不可（無限大コスト）として除外する。隣接セル間のステップコストは、縦横／斜め移動の幾何長比 $s \in \{1, \sqrt2\}$ を用いて $s \cdot (m(a)+m(b))/2$ とする。

8近傍格子上の非負コスト最短路探索には、用途に応じて Dijkstra、オクタイル距離に基づく許容ヒューリスティックを用いる A*、クラスタ境界のポータルによる抽象化を用いる HPA* を切り替えて使用する。HPA* は厳密最短性を保証しない代わりに広域探索を高速化でき、推定セル数がしきい値を超える場合には自動的に HPA* へ切り替える設定も備える。HPA* が失敗した場合は A* にフォールバックする。

疑似コード（グリッド探索アルゴリズムの選択）

function OFFROAD_ROUTE(grid, s_cell, g_cell, pathfinder, N_cells):
    if pathfinder == "hpa" or (AUTO_HPA and N_cells > THRESHOLD):
        path ← HPA_STAR(grid, s_cell, g_cell)      # クラスタ分割＋ポータル抽象化
        if path is not None: return (path, "hpa")
        pathfinder ← "astar"                        # 失敗時フォールバック
    if pathfinder == "astar":
        return (A_STAR(grid, s_cell, g_cell, h=octile), "astar_fallback" if fell_back else "astar")
    return (DIJKSTRA8(grid, s_cell, g_cell), "dijkstra")

セル数を $N$ （ $N = h \times w$ ）とすると、8近傍 Dijkstra は $O(N \log N)$ 、A* は最悪 $O(N \log N)$ だが許容ヒューリスティック（オクタイル距離）により実際の展開ノード数は経路長に対してより少なく抑えられる。HPA* はクラスタ辺長 $L$ （既定16セル、実装では8〜128の範囲で動的調整）に対し、クラスタ数 $O(N/L^2)$ ・ポータル数をクラスタ境界長に比例させた抽象グラフ上で大域探索を行うため、大域段の計算量は $N$ に対してほぼ線形（クラスタ内のローカル探索を合算しても $O(N)$ 近傍）に抑えられる一方、抽象化による経路の非最適性（厳密最短保証の喪失）とのトレードオフを持つ。

4.6 ハイブリッド統合とピラミッド型多重解像度探索

「道路＋不整地」モードでは、まず道路経路を求め、その周囲に前述の回廊を自動生成し、標高データが利用可能であれば内部で不整地探索を行う。1メートル級の細かい格子を回廊全体に適用するとメモリ・計算コストが過大となるため、本システムは粗い解像度から段階的に細かい解像度へ絞り込むピラミッド方式を採用する（図4）。

図4. ピラミッド型多重解像度によるハイブリッド探索

具体的には、粗いグリッド L0（grid_m に係数を乗じた解像度）で回廊全体の経路を求め、その経路の外接矩形をマージン付きで狭めた領域だけを、条件に応じて中間解像度 L1・L2 を経て、最終解像度 L3 で再探索する。高速モード（pyramid_fast）では中間段を省略し L0→L3 の2段構成に短縮する。ピラミッド機構が無効な場合は、同様の考え方に基づく従来実装（hybrid_router：粗い L0 と細かい L3 の2段構成）を用いる。

疑似コード（ピラミッド型多重解像度探索）

function PYRAMID_HYBRID(corridor, levels, fast):
    levels ← [L0, L3] if fast else [L0, L1, L2, L3]   # 解像度は粗→細
    bbox ← corridor
    path ← None
    for level in levels:
        grid ← BUILD_COST_GRID(bbox, resolution=level)
        path ← OFFROAD_ROUTE(grid, snap(bbox.start), snap(bbox.goal), pathfinder_for(level))
        if path is None:
            break                          # 失敗時は最終解像度のみ回廊全体で再試行
        bbox ← BUFFER(BOUNDING_BOX(path), margin=FINE_MARGIN_M) ∩ corridor
    return path

各段の格子セル数を $N_i$ （ $i=0,\ldots,3$ 、 $N_0 \gg N_3$ ）とすると、粗段は広い回廊を低解像度で走査するため $N_0$ 自体は大きくなりにくく、細段は狭められた bbox に限定されるため $N_i \ll N_0$ （ $i \ge 1$ ）に抑えられる。全域を最終解像度 grid_m で一括探索した場合の計算量 $O(N_{full}\log N_{full})$ （ $N_{full}$ は回廊全体を最終解像度で覆ったセル数）と比較して、段階的な絞り込みにより実効的な探索対象セル数の合計 $\sum_i N_i$ を $N_{full}$ より大幅に小さく保てる点が、1メートル級の細かい格子を広い回廊に適用する際のメモリ・計算コスト抑制の設計上の狙いである。

4.7 応答の組み立てと多目的重みの正規化

複数目的を同時に考慮する場合、非負の重み $w_t, w_d, w_r, w_e$ をその総和で正規化し、

s = w_t + w_d + w_r + w_e, \qquad \tilde w_t = \frac{w_t}{s},\ \ldots

として和が1のベクトルに変換する（総和が0以下の場合は時間のみを最適化する扱いにフォールバックする）。単一目的が指定された場合は、対応する成分のみを1、他を0とする。この正規化重みは道路の辺コストとグリッドのステップコストの双方で共通に使用される。

応答は、地図描画用の route_geojson（スナップ直線・道路・不整地の各レイヤを、表示設定に応じて1本の折れ線に統合可能）と、分析用の route_profile（大円距離に基づく区間長、DTM サンプリングによる標高・傾斜角、区間種別ごとの推定所要時間）の2系統として構成される。route_profile は統合前のより細かいセグメント列から算出されるため、route_geojson とセグメントの区切りが一致しない場合がある点に留意が必要である。

4.8 各アルゴリズムの計算量のまとめ

4.3〜4.6節で述べた各アルゴリズムの理論的な計算量を表4に整理する。ここで $|V|,|E|$ は道路網の頂点・辺数、 $k$ はスナップ候補数、 $N$ はグリッドの総セル数、 $L$ は HPA* のクラスタ辺長である。

アルゴリズム	前処理	クエリ計算量（概算）	備考
道路スナップ（KNN, GiST）	索引構築 $O(\lvert E\rvert\log\lvert E\rvert)$ （DB 側で継続維持）	$O(\log\lvert E\rvert + k)$	STRtree 経路は起動時 $O(\lvert E\rvert)$ で索引構築、クエリは候補数に線形
`pgr_dijkstra` / `pgr_withPoints`	なし	$O((\lvert V\rvert+\lvert E\rvert)\log\lvert V\rvert)$	片方向。双方向 `pgr_bdDijkstra` は探索空間を実務上大きく削減
Contraction Hierarchies	$O(\lvert V\rvert\log\lvert V\rvert)$ 程度（オフライン、`build_ch`）	実務上 $O(\log\lvert V\rvert)$ 近傍	端点スナップ限定。辺上任意点には非対応（6章）
8近傍 Dijkstra（グリッド）	なし	$O(N\log N)$	非負コスト・8近傍固定次数
A*（オクタイル）	なし	最悪 $O(N\log N)$ 、実効的にはヒューリスティックで削減	許容ヒューリスティックのため最短性は保証
HPA*	クラスタ・ポータル構築 $O(N)$	大域段はクラスタ数 $O(N/L^2)$ に比例、局所段を合算し概ね $O(N)$	厳密最短性は非保証。失敗時 A* にフォールバック
ピラミッド（L0〜L3）	なし（都度構築）	$\sum_i O(N_i\log N_i)$ 、 $N_i \ll N_{full}$ （ $i\ge1$ ）	全域最終解像度一括探索（ $O(N_{full}\log N_{full})$ ）との対比が設計上の主眼

表4は漸近的な計算量の整理であり、5章で述べる実装（並列 leg 計算、Redis キャッシュ、ラスタの window read 等）による定数項の削減効果は含まれていない点に注意されたい。実データにおける絶対的な応答時間は7.3節で述べる方針に基づく実測評価が必要である。

5. システム実装

5.1 データ基盤

道路網データは OSM から取得し、局所領域は bbox 指定での直接取得、広域は Geofabrik 配布の PBF ファイルからの一括投入により PostGIS の ways テーブルへ格納する。標高（DTM）・土地被覆・水域は GeoTIFF またはベクタ（Shapefile／PostGIS テーブル）として管理し、要求のあった回廊範囲のみを rasterio の窓読み込み（rasterio.windows.from_bounds）で取得し、EPSG:3857 の固定グリッドへ再投影する。これにより、ラスタファイル全体をメモリに保持することなく、任意規模の広域データセットに対応できる。

5.2 API 設計

同期エンドポイント POST /route/ と GET /route/compute に加え、POST /route/ に async: true を指定することで Celery による非同期ジョブとしての実行を受け付ける。保存された経路は UUID を発行して DB（saved_routes）に保持され、後から GET /route/{route_id} で再取得できる。外部からのアクセスは nginx ゲートウェイ経由に統一する運用を想定している。

5.3 キャッシュ機構

同一条件の再計算を避けるため、探索モード・グリッド設定・スナップ関連パラメータ・ピラミッド設定・表示統合の有無などを含む指紋（_layer_fingerprint）を鍵として Redis に経路応答全体をキャッシュする。標高格子（elev）のキャッシュは経路キャッシュとは独立しており、回廊 bbox・グリッド解像度・DTM の指紋のみを鍵とすることで、出発・目的地点が変わっても同一回廊・同一データソースであれば I/O を削減できる。座標は既定で高精度に量子化してキー化するが、設定によりやや粗い桁への丸め（ファジーマッチ）を許容し、近接した OD ペアのキャッシュヒット率を高めることも可能である。

5.4 データ取り込みパイプライン

道路データの投入は経路計算そのものとは独立した運用オペレーションとして設計されている。局所検証には bbox 指定によるオンライン取得、広域・全国規模の展開には Geofabrik PBF と差分更新（osmChange / .osc）を用いたパイプラインを用意する。DTM・土地被覆・水域データについても、ファイルベース（GeoTIFF/Shapefile）と PostGIS テーブルベースの双方をサポートし、優先順位（ファイル優先）を明確にすることで運用環境の柔軟性を確保している。

5.5 リクエスト処理シーケンス

3〜4章で述べた各要素技術が、実際の1リクエストの中でどの順序・どのコンポーネント間でやり取りされるかを図5に示す。road+offroad・priority=road_first・経路キャッシュ未ヒットという代表的なケースを例に、クライアント・API（Orchestrator）・PostGIS/pgRouting・Redis の4者間のメッセージフローを時系列で表す。

図5. road+offroad リクエストの処理シーケンス

図5で特に強調したいのは、不整地側のグリッド構築・ピラミッド探索（⑤）が独立したサービスへの呼び出しではなく、API プロセス内の同一リクエストスレッド上で完結する点である。DTM のラスタ読み込みも、そのつどファイル全体を読むのではなく、道路経路から生成した回廊 bbox に限定した window read（rasterio.windows.from_bounds）として実行される。標高格子キャッシュ（⑤′）は経路キャッシュ（②・⑥）とは独立した鍵空間を持ち、回廊 bbox・グリッド解像度・DTM 指紋が一致する限り、出発・目的地点が異なっていても再利用され得る（5.3節）。非同期実行（POST /route に async: true を指定した場合）では、この一連の処理が Celery Worker 上で実行され、API はジョブ受付のみを即時応答する構成になる。

5.6 データベーススキーマ（道路網・CH 関連）

道路網および Contraction Hierarchies に関わる主要テーブルの関係を図6に簡略化して示す。ways は pgr_createTopology によって source／target（ways_vertices_pgr への参照）が付与された道路網本体であり、時間・距離・リスク・エネルギーの4種の基準コスト列（および逆方向用の列）を持つ。CH を利用する場合、ways_vertices_pgr の各頂点に対して python -m app.scripts.build_ch がオフラインで ch_vertex_rank（縮約順位）と ch_shortcut（ショートカット辺）を構築し、ROAD_USE_CH=true のときのみ道路経路探索から参照される。saved_routes はこれらとは独立に、POST /route（save: true）で得られたリクエスト・結果の JSON スナップショットを保持するテーブルであり、道路網テーブルのコスト列を直接参照するのではなく、計算時点の結果を記録する点に注意されたい。DTM・土地被覆・水域・建物の各データは config/data_catalog.yaml が示す別テーブル・ラスタ層として管理されるため、本図では省略している。

6. 設計上の考察：CH と辺上任意点間経路探索の統合

CH は事前に縮約したランク付きグラフ上でのクエリを前提とするため、実頂点集合にのみ定義される。一方、実運用上の出発・目的地点の多くは辺の途中にスナップされ、pgr_withPoints が扱う「仮想ノード」として表現される。この不整合を解消する方式には、少なくとも3通りが考えられる。

端点への丸め — スナップ点を最寄りの実頂点に丸め、既存の CH クエリへそのまま載せる。実装は単純だが、fraction 分の位置ずれによって幾何・コストの精度が低下する。
動的挿入 — スナップ点をクエリごとに CH グラフへ挿入し、局所的な再ランク付けを行う。理論上は精度を保てるが、クエリ毎の局所グラフ再構築が必要となり実装・検証コストが大きい。
ステッチ（ハンドオフ） — スナップ点から最寄りの実頂点までを局所的な Dijkstra で接続し、以降は CH クエリに切り替える。OSRM や Valhalla 等の実運用エンジンで採用される現実的な折衷案だが、乗換点の選択、乗換前後のコスト整合、始点・終点双方をステッチする際の中間区間の重複回避など、正しさを保ったまま実装・回帰検証すべき論点が複数存在する。

本システムでは方式①に相当する範囲、すなわちスナップ位置が辺の端点に十分近い場合に限って CH を試行し、それ以外の典型的なケースでは pgr_withPoints を既定として採用している。これは、CH を辺上 OD 問題全体の代替とするのではなく、「頂点が確定している場合の高速経路」として限定的に活用する設計判断である。方式③のステッチは理論的には精度と速度を両立しうるが、実装・検証コストの観点から本システムのスコープ外としている。

同様に、HPA* は探索空間をクラスタとポータルによって抽象化することで大域探索を高速化する一方、厳密最短性を保証しない。本システムでは失敗時に A* へフォールバックする設計とすることで、速度と正確性のトレードオフを状況に応じて調整可能にしている。

7. 制限事項と今後の課題

7.1 スコープ外の事項

本システムは、深層学習に基づく学習型コスト推定、メタヒューリスティックな探索手法（遺伝的アルゴリズム等）、時々刻々変化する動的コスト（交通流や気象条件の変化等）を明示的にはスコープに含めていない。これらは経路探索の高度化として有力な方向性ではあるが、本システムは静的な道路網属性・DTM・土地被覆データに基づく決定論的な最短路計算を対象としており、意図的にスコープを限定している。

7.2 未解決の設計課題

6章で述べた CH のステッチ（辺上任意点への一般化）は、乗換点の選択・乗換前後のコスト整合・始点終点双方の対称処理という3つの論点を含み、実装・検証コストの観点から本システムでは採用を見送っている。また、経路の途中変更や環境更新に対する再計画は、D* Lite [8] や ARA* [9] のような増分探索アルゴリズムの導入によって効率化できる可能性があるが、本システムは経路ごとに独立した一括計算を前提としており、こうしたインクリメンタルな再探索には対応していない。ピラミッド型多重解像度探索（4.6節）についても、粗い解像度段での経路が実際には存在しない狭い回廊に迷い込んだ場合の復帰戦略（バックトラック）は限定的であり、より頑健な多重解像度探索アルゴリズムの検討余地がある。

7.3 評価に関する方法論的な位置づけと今後の計画

本稿は4.8節で各アルゴリズムの理論的な計算量を整理したが、実データ規模における定量的なベンチマーク測定（クエリ応答時間、CH 有効化前後の速度比較、A* と HPA* の速度・経路長トレードオフ、キャッシュヒット率とその効果、ピラミッド段数と応答時間の関係等）は実施していない。これは測定を軽視しているためではなく、実測を伴わない推測値を確定的な数値として提示することを避けるための意図的な選択である。

今後実施すべき評価の枠組みとして、少なくとも以下の要素を想定している。

データセット: docs/INGEST_OSM.md に示される bbox 単位の局所領域（検証用の小規模データ）と、Geofabrik PBF による広域データ（本番相当のデータ規模）の両方で計測し、規模依存性を確認する。
評価指標: クエリ応答時間の分布（P50/P95/P99）、HPA* 使用時の経路長が Dijkstra／A* による厳密最短路からどれだけ乖離するか、Redis キャッシュのヒット率とヒット時／ミス時の応答時間差、CH 有効化による端点スナップクエリの高速化率。
比較対象（ベースライン）: CH 無効時の pgr_withPoints のみの構成、ピラミッド無効時の hybrid_router（4.6節）、HPA* 無効時の A* のみの構成など、本システムが内部に備えるフォールバック構成同士の比較により、外部エンジンとの直接比較が難しい環境（データセットの違い等）でも設計判断の妥当性を検証できる。

8. おわりに

本稿では、道路網に基づく最短経路探索と、地形コストに基づくグリッドベースの不整地経路探索を統合したハイブリッド経路探索システムの設計と実装について述べた。地理 KNN と同点帯によるロバストなスナップ、CH と pgr_withPoints を状況に応じて使い分ける道路網探索、Tobler 関数に基づく地形コストモデルと Dijkstra／A*／HPA* の切り替え、道路周囲に自動生成した回廊内での粗→細ピラミッド探索という4つの要素技術の組み合わせにより、道路と不整地を切れ目なく接続する経路計画を実現した。

2章で整理したように、本システムの技術的な位置づけは、CH や HPA* といった個々のアルゴリズムそのものの新規性ではなく、それらを共通の多目的重みベクトルの下で道路網とグリッドの間で使い分け、多重解像度探索によって接続している点にある。4.8節で示した計算量の整理、5.5〜5.6節で示したリクエスト処理シーケンスとデータベーススキーマは、この統合がどのコンポーネント境界でどのような計算量特性のもとに行われているかを具体的に裏付けるものである。CH の辺上任意点への拡張という設計上の未解決課題（6章）、D* Lite・ARA* 等の増分探索アルゴリズム未対応（7.2節）を含め、本システムの構成は、道路網ルーティングと不整地経路計画という従来別個に扱われてきた技術領域を統合する際に生じる技術的トレードオフの具体例を提供するものである。実データ規模での定量評価は7.3節で述べた方針のもとでの今後の課題としたい。

参考文献

[1] E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, pp. 269–271, 1959.

[2] P. E. Hart, N. J. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths," IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.

[3] R. Geisberger, P. Sanders, D. Schultes, and D. Delling, "Contraction hierarchies: Faster and simpler hierarchical routing in road networks," in Proc. 7th International Workshop on Experimental Algorithms (WEA), 2008, pp. 319–333.

[4] W. R. Tobler, "Three presentations on geographical analysis and modeling: Non-isotropic geographic modeling; speculations on the geometry of geography; and global spatial analysis," National Center for Geographic Information and Analysis, Technical Report 93-1, 1993.

[5] A. Botea, M. Müller, and J. Schaeffer, "Near optimal hierarchical path-finding," Journal of Game Development, vol. 1, no. 1, pp. 7–28, 2004.

[6] D. Delling, P. Sanders, D. Schultes, and D. Wagner, "Engineering route planning algorithms," in Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, vol. 5515, Springer, 2009, pp. 117–139.

[7] D. Luxen and C. Vetter, "Real-time routing with OpenStreetMap data," in Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS), 2011, pp. 513–516.

[8] S. Koenig and M. Likhachev, "D* Lite," in Proc. 18th National Conference on Artificial Intelligence (AAAI), 2002, pp. 476–483.

[9] M. Likhachev, G. J. Gordon, and S. Thrun, "ARA*: Anytime A* with provable bounds on sub-optimality," in Advances in Neural Information Processing Systems (NeurIPS) 16, 2003.

付録A. 主要環境変数（抜粋）

変数	既定値	説明
`ROAD_USE_BIDIRECTIONAL`	`true`	道路探索で双方向 Dijkstra を使用するか
`ROAD_USE_CH`	`false`	端点スナップ時に CH を試行するか
`ROAD_MAX_SNAP_DISTANCE_M`	`30000`	道路スナップの許容距離上限（m）
`OFFROAD_GRID_PATHFINDER`	`astar`	不整地グリッド探索アルゴリズム（`dijkstra`/`astar`/`hpa`）
`OFFROAD_MAX_SLOPE`	―	通行可能な最大勾配（ハード制約）
`PYRAMID_ENABLED`	`true`	ピラミッド型多重解像度探索の有効化
`PYRAMID_L0_M` / `L1` / `L2`	`100`/`25`/`5`	ピラミッド各段のグリッド解像度（m）
`ROUTE_CACHE_TTL_SEC`	`300`	経路キャッシュの有効期限（秒）

本稿は本リポジトリのソースコードおよび内部設計ドキュメント（docs/ALGORITHM.md、docs/API.md、docs/ROADMAP.md）に基づき執筆した。