ハクソク

世界を動かす技術を、日本語で。

OsmAndのより高速なオフラインナビゲーション（2025年）

88日前原文(osmand.net)

概要

  • 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のまとめ

  • 独自設計の二層階層ルーティング と 高度なボーダーポイント選定 による圧倒的高速化
  • 柔軟性・省容量・地域地図管理・頻繁更新 の全てを両立
  • オフラインナビゲーション の新たな標準として、旅行・冒険・日常利用を劇的に快適化

Hackerたちの意見

ちょっと前に、OsmAndを使って約700マイルのルートを走ったんだけど、ほとんどが一つの高速道路なのに10分以上かかったんだ。さっき同じルートを試したら、7秒で終わった！すごい改善だね！

OSMAndを使ってる人に聞きたいんだけど、公共交通機関のルーティングを提供する可能性ってあると思う？もしそうなったら、すぐに15年プランのXVを買うんだけど、彼らのモットー「オフラインマップとナビゲーション」と矛盾するかもね。（個人的には、スケジュールベースのルーティング、つまりリアルタイムじゃないやつでもしばらくは我慢できるけど。）

└

今日からOsmAndで「公共交通」プロファイルを有効にできるよ。ただ、あなたの地域をサポートしてないかもしれないけどね。

└

公的資金で運営されている（その結果、あなたの収入の最大のシェアを支払う大きな単一の団体が、頑張れば多くを決定できるし、基本的に無料に近い）ところに、リアルタイムの交通情報をオープンデータとして公開させるべきだと思う。直接ソースから取得する場合、AWSの帯域幅料金に等しい手数料でね。ライセンスは、他の人がキャッシングプロキシアクセスを提供できるようにして、あまり制約を設けないようにすればいい。残念ながら、多くの場所でスケジュールを考慮せずにルーティングすると、乗客のかなりの部分で「典型的な」移動時間が50%以上増加しちゃうんだよね。その点で、私の市の公共事業がEUの強制的な「モビリティ」部門でリアルタイムデータをどう扱ってるか見てみるべきだと思う。バスのドアに貼ってある広告から、1、2年前に彼らがモバイルブラウザで使えるライブ位置トラッカーを提供し始めたのに気づいたから。これをスケジュールと一緒に使って、イヤフォンにストリーミングコマンドを送るための予測モデリングができるかもしれない。例えば、家を出るときに近い駅でバスを捕まえるべきか、もう一つの支線まで歩くべきかを教えてくれるといいな。そっちの方が1分遠いけど、バスは3分後に出発する予定なんだ。バスのルートは、物理的に交差するか、同じ「名付けられた停留所」で短時間だけ会うかのどちらかで接続するんだ。私はその「分岐点」までの共有の歩道をリアルタイムで確認する余裕がないから、交通渋滞に巻き込まれているか、実際に停留所に止まっているかを地図で確認するのが難しいんだよね。時間通りに出発することが重要で、靴ひもを結び直したり、郵便物をバックパックに詰めたりする余裕を持たないと、ちょっと遅れたときに近い駅を逃しちゃうことになるから。

Contraction Hierarchiesに対するいくつかの反論は、ちょっと古いかもしれないね。現代のバリエーションは、迅速なライブトラフィックのカスタマイズを可能にしてる。詳しくは、例えば https://arxiv.org/pdf/2502.10519 を見てみて。おそらく「ネストされた分割」アプローチも地域マップに対応してると思う。OSRMの実装を見たのはしばらく前だけど、ここでは最先端についていけてないんじゃないかな。

└

誰が知ってるんだろうね・・ ;)

OsmAndが大好きなんだけど、毎回のアップデートで遅くなる気がする。ナビゲーションの速度はまあまあだけど、歩いたり自転車に乗ったりするのに使ってるから、ルートは短いことが多い。だけど、地図をパンしたりズームしたりするのがイライラするほど遅い。地図の機能をほとんど無効にするとなんとか動くけど、その機能があるからOsmAndを使ってるんだよね…

└

えっと、Gmapsが遅くない理由は、これらの機能を持った事前に用意された地図をストリーミングしているからだよ。オフラインモードに行けばそれを確認できる。

Googleマップを使うのをやめたいんだけど、他の選択肢で困るのは、行きたい場所を簡単に検索できないことなんだ。99%の確率で行く場所はビジネスで、「」をGoogleマップ以外で検索すると、何も出てこなかったり（このカテゴリではOsmAndがそう）、そのチェーンの店舗がランダムな順番で出てきたり、同じ名前の町が100マイル離れたところに混ざってたりする。もっと一般的なクエリ「ガソリンスタンド」なんてさらにひどい。私が考えた一番の解決策は、Googleマップで実際の住所を見つけて、それを他のアプリにコピーすることだけど、その時点でGoogleマップを使った方がいい気がする。これに対する解決策を知ってる人いる？

└

解決策はないけど、似たような経験はあるよ。いろんなクエリや地理空間データの違いがあるから、難しい問題なんだろうね。

└

同じ問題だね。OsmAndは素晴らしいけど、NominatimみたいなジオコーディングサービスがGoogleマップの検索と同じくらい良くならない限り、行き先の正確な場所を知らないと使えないな。

└

残念ながら、OpenStreetMapにはお店のデータが欠けていることが多いんだよね。（今、欠けているデータを見つけて追加しやすくするプロジェクトを進めてるけど、ほんの少しの前進に過ぎないかな、解決策にはならないけど）

└

僕は頑固だから、Googleマップをウェブブラウザ（サインアウトして）で使って、実際の目的地のアドレスをコピー＆ペーストしてアプリに入れてナビしてるよ（例えばCoMapsやOsmAnd）。不便だけど、Googleのアプリが一つ減るからね。Googleマップの強みは、正確で最新のビジネス情報が豊富なところなんだ。残念ながら、インターネット時代のイエローページみたいな存在だね。

└

小売チェーンの状況は、https://alltheplaces.xyz/ のようなプロジェクトのおかげで改善してるよ（注：僕は貢献者です）し、OSMの貢献者たちがOSMとATPの機能を比較して、欠けているお店を追加したり、閉店したお店を削除したり、営業時間を更新したりすることに焦点を当てている努力もあるんだ。例えば、https://matkoniecz.codeberg.page/improving_openstreetmap_usi... では、OSMとATPの機能をマッチング・比較するためのツールが紹介されてるよ（https://news.ycombinator.com/user?id=matkonieczが作成）。この作業は遅々として進まなかったけど、OSMコミュニティは伝統的に、店舗の壁に表示されている営業時間が著作権で保護されているかどうかの無駄な議論にハマっていたり、アームチェアマッピングと現地マッピングのメリットとデメリットを議論していたりしたからね。少なくとも、こうした歴史的な障害は今はほとんど解決されているみたい。OsmAndについては、OBFインポート機能を使って（https://www.osmand.net/docs/user/personal/import-export/を参照）、生のATPデータセットを追加できるかもしれないし、好みに応じてOverture Mapsのような他のオープンデータも使えるかもしれないよ。データは主にブランドのウェブサイトやAPIから直接取得されてる（まるで彼らのウェブサイトのストアファインダーマップを使っているかのように）。

└

私が思いついた最良の解決策は、Googleマップを使って実際のアドレスを見つけて、それを他のアプリにコピーすることです。これが私のやり方です。 > でも、その時点でGoogleマップを使った方が良いかもしれない。 僕はそうは思わないよ。OSMAndは地図としてはずっと使いやすいから。Googleマップはビジネスを探すには優れてるけど、それが本当に得意なことだからね。比較してみると、これがあるよ（ただし、これはOSMAndではなくopenstreetmap.orgを使ってるけど）：https://i.xkqr.org/gmapsvsosm.png

└

それをほぼ解決するジオコーダーを作ったよ。https://jonready.com/blog/posts/geocoder-for-ai-agents.html。Google Placesの98%に対して、約96%のリコール率なんだけど、クエリの計画とランキングにLLMを使ってるから、君にはあまり良い解決策じゃないかも。

└

これに対する解決策を持ってる人いる？ 解決策はないね。OSMの大ファンなんだけど、現代の地図はストリート名や建物じゃなくて、POI（ポイント・オブ・インタレスト）に関するものなんだ。どこかに行くときは、ストアや博物館、薬局に行くわけで、そのデータが信頼できないと意味がない。電話番号や営業時間、ウェブサイトの情報なんかは次のレベルで、OSMでは実現できないんだよね。

└

自分だけがこんな思いをしてるのかと思ってた。

CoMapsは、オフラインナビゲーションマップアプリの中では間違いなく最高の一つだよ。Organic Mapsプロジェクトから派生したみたいだけど、そっちはちょっと悪化しちゃったみたい。CoMapsの計算はすごく速いし、地図の更新も常に行われてる。軽量で、レイアウトもすごくきれいだし、使いやすさはトップクラス。CoMapsはビジネス名で場所を探せるし、改善の余地はあるけどちゃんと機能してる。前はEarthMagicを使ってたけど、あれは完璧なオープンソースアプリだったのに、 greedyになっちゃって今は問題だらけ。だからSygicに戻ったんだけど、あれは素晴らしいオフラインマップアプリだよ。生涯プレミアムライセンスを持ってるし、今はプレミアムプラスライセンスがあって、TTSや限られた地図更新機能がそっちに移動したみたい。CoMapsはAndroid Autoとも相性が良くて、僕はGrapheneOSを使ってるんだけど、実はGOSの中の誰かが勧めてくれたんだ。CoMapsは電車の路線やバス停、公衆トイレ、バイク駐車場も表示してくれるよ。ドラマに疲れたら、CoMapsを試してみて。CoMapsはCodebergでGitHubのオープンソース代替として利用できて、問題報告にもかなり積極的だよ。

└

Organic Mapsはどうなったの？

└

どうやってルーティングしてるの？こんなに速いの？

誰か説明してくれないかな、彼らが言ってる100倍の加速はどこにあるの？画面の記録では36秒と13秒を比較してるけど、これは大体3倍だよね。それに、この部分：> 100倍のスピードアップは、HHと双方向Aを比較することで達成されます。2フェーズAはすでに多くのヒューリスティックを使用していて、必ずしも最適なルートを作成するわけではなく、まだ5〜10倍遅い。つまり、2フェーズAは双方向Aよりも5〜10倍遅いってこと？

└

もしかして、CPU時間のトリック、つまりマルチコア？

└

ドキュメントも分かりづらいし、これらのラベルは全然意味がわからない。ルーティングタイプ（Android）/ ルーティングアルゴリズム（iOS） - A* 2フェーズ（Android）/ A*（iOS） - A classic*（Android）/ ハイウェイ階層（iOS） - HH（ハイウェイ階層） x C++（Androidのみ）

└

引用した部分が説明してるよ。100倍のスピードアップは、そもそも使ってなかった遅い方法と比較して得られたもので、HHが最適なルートを見つけるような方法なんだろうね。デフォルトのプロファイルを使ってるときは、カスタムの車速（130km/hで走らない自分みたいに、燃料やCO2の無駄を減らすために最大速度105の車に合わせてルーティングエンジンを設定してる）じゃないときに。

OsmAndはまだユタ州の住所を直してないんだよね。地元のスラングで住所を入力しても、全然見つけられない。

└

なんだそれ？いくつか例を共有してくれる？

└

自分でOpenstreetmapを修正し始めるか、もっといいのはユタ州で活動しているOSMマッパーに連絡を取って、このことについて話してみることだよ。OsmAndはOSMのデータを使ってるだけだからね。

OSMに貢献する簡単な方法は、Street Completeを使うことだよ。https://streetcomplete.app/ これは周りのことについて質問をしてくれるアプリなんだ。「このアプリは、あなたの近くの欠けている地図データを見つけて、クエストとして地図に表示します。現地に行って簡単な質問に答えることで、地図を更新するクエストを解決します。」f-droidから入手できるよ。