OsmAnd 作为开源离线地图导航应用，其路由引擎的核心在于自定义 Highway Hierarchies (HH) 架构，专为低内存移动设备设计，支持长距离（数百公里）实时重规划，通常在 1 秒内完成。这避免了传统 A* 算法在复杂路网中探索数百万边的瓶颈，转而通过预计算捷径和局部搜索实现高效性。
HH 架构将全球路网划分为约 54 万个区域簇（clusters），每个簇内有少量边界面点（border points，总计 300 万），使用 Ford-Fulkerson 算法识别自然瓶颈点作为出口，仅预计算簇内及相邻簇间的 shortcuts（约 9100 万条）。全球汽车 profile 数据仅 800MB，新增 profile 仅增 0.5% 存储。这种拓扑无关 profiles 的设计，确保 routing.xml 定义的 10+ 参数（如避开收费站、转弯罚分）仅影响 costs，而非重建图结构。“OsmAnd HH 比双向 A* 快 100 倍”。
路由计算分三步：首先在起点 / 终点簇内用 Dijkstra 连接实际位置到所有 border points（局部小图，快速）；其次在精简 base graph（border points + shortcuts）上 Dijkstra 求高层次路径；最后对每条 shortcut 在对应簇内运行 bounded A* 细化（每个簇仅探索数百边，长距离 500km 仅 100 个簇，总探索量降至数万边）。多线程化体现在 C++/Java 双实现中：高层次 Dijkstra 单线程保确定性，局部 A*/Dijkstra 并行 worker threads，利用多核 CPU；UI 渲染线程独立，避免阻塞。偏离路径时，重规划仅重跑局部簇和部分 base graph，阈值如 shortcut cost 偏差 >20% 触发更新，典型 <1s。
低内存是移动端关键，OBF 矢量格式压缩存储 geometry、attributes 和 HH 数据，按需加载簇细节。缓存策略：LRU eviction 优先簇 metadata，热点簇（如当前路径）预加载；瓦片失效阈值设为 map 更新周期（每月），live updates 时仅局部 shortcut 失效（<1%）。低 RAM 时（<2GB），fallback 到更保守 profiles，减少同时加载簇数至 50 个以内。监控点包括：搜索前沿大小（visited nodes>10k 告警）、线程利用率（<50% 优化 affinity）、内存峰值（>80% 触发 GC）。
落地参数与清单：
- 线程配置：worker threads = CPU cores -1（Android 设置 developer options）；优先 C++ impl（settings > routing > HH C++）。
- 重规划阈值：deviation distance >50m 或 time >10s 触发；shortcut invalid if delta_cost >15-25%。
- 簇参数：默认簇大小～5km²，border points 4-8 个 / 簇；长距离加 waypoints 每 100km 减负载。
- 缓存阈值：max loaded clusters 100；OBF cache size 256MB/region，SD 卡优先。
- profiles 优化：routing.xml 中 罚速限； tolls/ferries threshold 0.8。
- 监控 / 回滚：日志 metrics：route_time, visited_edges, mem_usage；>2s fallback A*；测试长距如 Munich-Basel（~400km，13s → 0.13s）。
- 部署清单：1. 下载同批次 maps（避免跨版本 HH 不兼容）；2. 启用 HH in navigation settings；3. 预热热点 regions；4. 低端设备限 profiles=3；5. 集成 GPX recording 验证。
此设计平衡速度、灵活与资源，适用于户外 / 旅行场景。风险：极端自定义 profile 过多 shortcut recalc（fallback A*）；maps 不同代跨区路由失效。
资料来源：