
2026/02/27 3:37
**OsmAndの高速オフラインナビゲーション(2025)**
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
概要:
OsmAnd の新しい Highway Hierarchy (HH) ルーティングエンジンは、従来の A* に比べ約100倍の速度向上を実現しつつ、全地球の車両データを約800 MB以下に抑えます。HH は領域クラスターの二層階層を構築し、大きなクラスターごとに Ford–Fulkerson 流量アルゴリズムで道路グラフのボトルネックを検出して 5〜10 個の境界点のみを選択します。これらの境界点間のショートカットは事前計算され(約91 M のショートカット)、抽象グラフに保存され、三段階でルーティングが行われます:開始/終了地点から境界へローカル Dijkstra、ショートカットネットワーク上の Dijkstra、およびユーザー定義パラメータを適用するローカル化 A* の微調整です。
システムは動的マップ更新に対応しています:ショートカットのコストが 20 % 超変化したり無効になった場合、該当クラスターのみのショートカットを再計算し、それ以外ではベースグラフを更新してローカルで Dijkstra を再実行します。極端に差異のあるプロファイルの場合は、HH が完全な A* 検索へフォールバックすることもあります。
ルートに使用されるすべてのマップファイルは同一世代日付である必要があり、バージョン不一致では互換性が失われます。全地球を前処理するには 2〜3 日かかり、新しい月次更新は毎月5日前後にリリースされ、時間単位の更新と代替ルート提案が可能でありながらストレージは最小限に保たれます。
OsmAnd は Facebook、TikTok、X、Reddit、および Telegram でコミュニティと積極的に交流し、速度向上やカスタマイズ機能に関するフィードバックを収集しています。
本文
オフラインナビゲーション――旅人・冒険者・日常通勤者の命綱
オフラインでの移動は、スピードと精度、そして自分のニーズに合わせてルートを調整できる柔軟性を求められます。数年前までは OsmAnd がポケットサイズに収まる高機能なオフライン地図で多くのユーザーを支えてきました。しかし、地図が詳細化し、複雑なルーティング要求が増えるにつれて、柔軟性はあるものの性能壁に直面するようになりました。
どうすれば 100 倍速化を実現しつつ、マップサイズを膨らませず、ユーザーが愛する高度なカスタマイズを維持できるか?
答えは――OsmAnd 独自設計の Highway Hierarchy (HH) ルーティング。
標準的なエンジンではなく、コンパクトでオフライン優先のデータに対し高度なナビゲーションを提供するための、ゼロから再設計されたアルゴリズムです。
開始点: 48.73829, 13.41383
終着点: 47.94505, 7.73573
OsmAnd Web プレビュー: ルートを見る
| HH (C++高速ルーティング) | 従来の A* ルーティング | 2 段階計算時間 |
|---|---|---|
| 13 秒 | 36 秒 | — |
100 倍速化は HH と双方向 A を比較した結果です。
2 段階 A* は多くのヒューリスティクスを使用していますが、必ずしも最適ルートを生成せず、5–10 倍遅いままです。*
標準手法が失敗した理由
OsmAnd は常に「ユーザーにコントロールを委ねる」ことを重視してきました。
routing.xml で設定可能な A* エンジンは、以下のような高度な機能を提供しました。
- 複雑なプロファイル定義
- 特定道路タイプの除外
- 真にパーソナライズされた旅程
地図データは最小化を徹底し(HH ルーティング用の全世界車両データは約 800 MB)、OsmAnd は軽量で高速なナビゲーション機器でした。
A* の限界
200–300 km の車用ルート、あるいは短距離の自転車・徒歩ルートを計算すると、100 万件以上の道路セグメントにアクセスし、10–20 秒かかるケースがありました。長時間の移動では待ち時間がフラストレーションにつながります。
Contraction Hierarchies (CH) などの標準的高速アルゴリズムを検討しましたが、以下の点で問題が残りました。
| 問題 | 影響 |
|---|---|
| 柔軟性との衝突 | CH は事前に最適経路を計算するため、OsmAnd の 10 種類以上のルーティングパラメータをサポートできない。 |
| ストレージ量 | 車両プロファイルで数十 GB(OSRM Europe)から全世界で 200 GB にも達する。目標は <20 GB。 |
| 地域マップの対応 | ユーザーが個別国をダウンロードする際、CH はグローバルネットワークを必要とする。 |
| 更新頻度 | 大規模な前処理により、時間単位での更新には不向き。 |
したがって、極めて高速化しつつも柔軟性・小容量・地域マップ対応・動的更新を実現する方法が求められました。
秘密 #1 ― 2 段階ルーティング
コアコンセプト
エリアクラスターに基づく二重階層:
- エリアクラスター – 地図を多数の小領域へ分割。
- 境界点 (Border Points) – 各クラスターは限られたゲートウェイを持つ。
- ショートカット – 同一クラスター内および隣接クラスター間で、境界点間の走行時間/距離を事前計算。
ローカル探索と高速なインタークラスターショートカットを組み合わせることで、ルーティング速度が劇的に向上します。
境界点選択
単純にランダムや幾何学的分割で選ぶと 50–80 点/クラスターとなり、ショートカットが爆発。そこで Ford–Fulkerson に基づく手法を採用し、ランダムな始点・終点から道路に「流量」を注ぎ、自然なボトルネック(グラフ理論でいう最小カット)を境界点として抽出。
汎用性
境界点の分布は走行速度プロファイルには依存せず、道路通行可能性だけに基づきます。したがって同じクラスターと境界点を車・自転車両どちらでも共有し、ショートカットコストのみをプロファイルごとに変えることで、追加ストレージは 約 0.5 % に抑えられます。
| 指標 | 値 |
|---|---|
| 元の OSM | 約 2.07 B 点, 2.42 B エッジ |
| HH 構造 | 約 3 M 境界点, 541 k クラスター |
| 推定ショートカット | 約 91 M (全世界ルーティングに耐える) |
OsmAnd がルートを構築する流れ
前処理(新マップ作成時)
- クラスターと境界点の決定 – 地図を分割し、Ford–Fulkerson で境界点を特定。
- ショートカット計算 – 各クラスター内の境界点間走行コストを、一般的な速度プロファイルに対して保存。
ユーザーからのルートリクエスト(デバイス上)
-
階層への接続
- 始点・終点が属するクラスターを特定。
- 詳細マップで Dijkstra を実行し、始点/終点から各境界点へ最短経路を取得。
-
抽象グラフ上のルーティング
- 境界点とショートカットのみで構成されるベースグラフで別途 Dijkstra を実行。
- これにより境界点列とショートカットが高速に決定。
-
詳細ショートカットの再計算(秘密 #2)
- 各ショートカットについて、該当クラスター内の詳細マップで最適化された A* を実行。
- 500 km のルートでは、1M 件以上だった詳細セグメント数が 10–50k 件 に削減。
この組み合わせにより、100 倍速化を実現します。
秘密 #2 ― 適応型ルーティング
- 完全なパラメータサポート – 最終的なショートカット再計算で A* を使用するため、通行料回避や平坦路優先など全
パラメータを自然に取り込む。routing.xml - ライブ更新と動的変更 – 橋が閉鎖されたりコストが大幅変化した場合は、影響を受けるショートカットのコストだけをベースグラフで更新し Dijkstra を再実行。局所的な変更なら該当クラスター内のみ再評価。
- 柔軟なフォールバック – 非常に異なるプロファイルでは、オリジナル A* が高速になる場合もあるため、そのケースへ自動で切り替え可能。
OsmAnd ユーザーへの実際のメリット
| メリット | 内容 |
|---|---|
| 驚異的速度 | 長距離ルートで平均 100 倍高速化。 |
| 軽量化 | HH ルーティングはマップサイズを 0.5–1 % のみ増加(全世界車用データ約 800 MB)。 |
| 完全カスタマイズ | のすべてのパラメータが保持。 |
| 地域マップ対応 | 必要な国だけダウンロードしても、境界点でスムーズに横断可能。 |
| 頻繁更新対応 | 時間単位でのマップ更新にも柔軟に適応。 |
| 将来性 | 境界点を利用した代替ルート提案など新機能の実装が容易。 |
重要なルーティング注意事項
- 極端に異なるプロファイル – 依然としてオリジナル A* が速い場合はそちらへフォールバック。
- マップバージョン同期(重要!) – HH ルーティングを複数のマップファイルで使用する場合、すべてが同じ世代日付である必要があります。異なるバージョンだと境界点間の互換性に問題が生じます。
- リリーススケジュール – 前処理は約 2–3 日かかり、新更新は毎月 5 日頃に公開予定。
一緒に議論しませんか!
HH ルーティングの導入で、OsmAnd はさらに進化しました。
- 新しい速度感覚を体験されましたか?
- サポートされているカスタム設定で特に重宝しているものは何ですか?
ぜひコメントやコミュニティフォーラムでご意見・ご質問をお寄せください!
フォローはこちらから:Facebook, TikTok, X (Twitter), Reddit, Instagram。
Telegram グループ へもご参加ください:OsmAnd News チャンネル(EN, IT, FR, DE, UA, ES, BR‑PT, PL, AR, TR)。
いつも OsmAnd コミュニティにご協力いただきありがとうございます!