概要
- OsmAnd の新しい Highway Hierarchy (HH) Routing による100倍の高速化
- 柔軟なカスタマイズ性 と 省ストレージ を両立した独自アルゴリズム
- 地域ごとの地図管理 や 頻繁な更新 にも対応
- 従来のA*アルゴリズム の限界を克服
- ユーザー体験 の劇的な向上を実現
OsmAndのHHルーティング：オフラインナビゲーションの新時代
- 旅行者や通勤者の オフラインナビゲーション に不可欠な高速・高精度ルート検索
- OsmAndは 小容量で高機能な地図 を提供し続けてきたが、従来のA*アルゴリズムでは複雑ルートで 計算速度 に限界
- 従来のA *：200〜300kmの自動車ルート計算で数百万の道路セグメントを探索、10〜20秒以上かかる課題
- 新開発のHHルーティング ：100倍の高速化を実現しつつ、地図サイズ増加を最小限に抑制
- 柔軟なルート設定 や カスタムプロファイル も維持
標準的なアルゴリズムが直面した課題
- Contraction Hierarchies (CH) などの標準高速化手法はOsmAndに不向き
- 柔軟性の欠如：10以上のルーティングパラメータ対応が困難
- ストレージ問題：CHのデータは巨大（例：OSRMのヨーロッパだけで数十GB）
- 地域地図管理との非整合：個別ダウンロードや頻繁更新に非対応
- OsmAndの目標 ：全地球の全プロファイル合計20GB未満、かつリアルタイム更新対応
Secret Sauce #1: 二層階層ルーティング
- 地図を 小さなエリアクラスタ に分割し、各クラスタに ボーダーポイント（出入口） を設定
- クラスタ内・隣接クラスタ間の ショートカット（事前計算済み経路） を保存
- Ford-Fulkersonアルゴリズム による「ボトルネック」検出で最小限のボーダーポイント選出
- 複雑なエリアでも数個の出入口だけで効率的に表現
- 例：5,000ポイント・10,000エッジの複雑クラスタを5ボーダーポイント・10ショートカットで高効率化
- プロファイル非依存 のクラスタ・ボーダーポイント設計で、全プロファイルのデータ増加を約0.5%に抑制
OsmAndのルート構築プロセス
- A. 事前処理（地図作成時）
- クラスタ分割・ボーダーポイント定義
- 主要プロファイル向けショートカットのコスト（時間・距離）を事前計算・保存
- B. ルート検索時（端末上）
- ステップ1：出発地・目的地のクラスタ内で Dijkstra で最適経路を探索
- ステップ2：ボーダーポイント間の抽象グラフ上で Dijkstra による高速経路探索
- ステップ3：各ショートカット区間ごとに限定範囲で A *を使い詳細経路を再計算
- 例：500kmルートなら100区間、全体で10,000〜50,000セグメントのみ探索
- 従来のA*の1,000,000+セグメント探索と比較し圧倒的な効率化
Secret Sauce #2: アダプティブルーティング
- 全パラメータ対応 ：各クラスタ内でA*を使うため、routing.xmlによる細かな設定や回避指定も完全反映
- ライブ更新・動的変化対応 ：
- 例：橋の通行止めなどでショートカットが無効化された場合、該当ショートカットのコストを即時更新し再探索
- 極端なカスタマイズ時は全体A*への自動/手動切り替えも可能
- 地域ごとの地図管理 や 頻繁な地図更新 にも柔軟対応
OsmAndユーザーへのメリット
- 圧倒的な速度向上 ：ルート計算が従来比100倍高速化
- ストレージ極小化 ：HHルーティングデータ追加分は0.5〜1%、地球全体の自動車ルーティングデータで約800MB
- カスタマイズ性維持 ：従来のrouting.xmlや詳細パラメータもそのまま利用可能
- 地域地図対応 ：必要な国や地域のみダウンロードしても、シームレスにルート計算が可能
OsmAnd HH Routingのまとめ
- 独自設計の二層階層ルーティング と 高度なボーダーポイント選定 による圧倒的高速化
- 柔軟性・省容量・地域地図管理・頻繁更新 の全てを両立
- オフラインナビゲーション の新たな標準として、旅行・冒険・日常利用を劇的に快適化