OsmAnd 作为开源离线地图导航应用，长期以来在处理复杂长距离路由时面临计算延迟问题，尤其在自行车或步行路径上，用户反馈计算时间可达数秒至分钟。为解决这一痛点，OsmAnd 引入自定义高速公路层次（Highway Hierarchy, HH）路由引擎，通过智能聚类和预计算捷径，实现平均 100 倍速度提升，同时保持地图数据紧凑，仅需全球汽车路由数据约 800MB。该优化聚焦单一技术点：结合矢量瓦片高效处理、多线程最短路径求解与低内存存储策略，确保在移动设备上流畅运行。
HH 路由的核心是二层架构设计，将地图划分为众多小区域簇（clusters），每个簇选定少量边界点（border points，通常 3–8 个）。边界点基于 Ford-Fulkerson 算法模拟流量瓶颈自动选取，确保拓扑结构与路由配置文件无关，仅预计算簇内及相邻簇间的捷径（shortcuts）成本。路由查询分为三步：首先在起始簇内用 Dijkstra 算法从起点连接所有边界点（局部小图，计算快）；其次在抽象边界图上 Dijkstra 求解簇间高层次路径（节点稀疏，~300 万边界点覆盖全球）；最后针对序列中每个捷径，在对应簇内运行受限 A* 算法精炼详细路径。此机制将长距离路由（如 500km）从百万级边扩展降至万级，OsmAnd 官方博客指出，与双向 A* 相比实现 “100x speedup”。
矢量瓦片处理优化是 HH 路由高效的基础。OsmAnd 使用紧凑二进制矢量地图（vector maps），节点坐标 delta 编码、边属性位字段打包，类似于 CSR（Compressed Sparse Row）表示，与渲染几何共享避免冗余。地图按国家 / 区域分块下载，支持灵活管理；簇边界对齐瓦片，确保跨区域路由无缝。渲染时动态缩放无损，支持自定义样式（如自行车专用路径突出、海拔等高线叠加），并集成 Wikipedia POI。低缩放级仅显示关键元素，高缩放揭示细节，结合 OpenGL 加速渲染，即使老设备也能流畅平移。
多线程最短路径计算进一步放大 HH 优势。抽象路径确定后，第三步的多个簇内 A* 独立，可并行执行：利用线程池处理 100+ 捷径，每个任务限于簇范围（数千节点），预分配工作空间避开分配器开销。边界图用结构化数组（SoA）布局，便于 SIMD 加速边松弛；启发式结合欧氏距离与簇内 ALT 预计算下界，提高剪枝效率。实际中，车速 200–300km 路由计算从 36 秒降至 13 秒，支持实时重路由（如偏离路径）。
紧凑存储特别适配低内存设备。全球预处理产出～54 万簇、9100 万捷径，但每配置文件仅增 0.5–1% 存储（成本表而非拓扑）。簇规模控制在 L2/L3 缓存内（几千节点），局部搜索命中率高；支持区域地图，无需全图加载。动态更新兼容：小时级地图变更仅局部失效捷径，成本偏差 >20% 时重算或回滚全 A*。风险包括极端自定义配置文件（如罕见路类偏好）fallback 原算法，以及跨地图版本不一致导致边界不兼容 —— 建议统一下载批次。
落地参数与清单：
- 簇划分：目标 几千节点 / 簇，边界点 3–8 个（基于流量瓶颈）。
- 预计算：仅常见配置文件捷径（10+ 参数组合），存储 baseline 成本 + 配置文件罚项。
- 线程配置：线程池大小 = CPU 核数，任务粒度 <1000 边 / 捷径。
- 启发式阈值：成本偏差 20% 重算捷径；50+ 失效 fallback A*。
- 监控点：路由时间（目标 <1s 短距、<10s 长距）、内存峰值（<100MB / 路由）、缓存命中率>90%。
- 回滚策略：设置中切换 “A* 引擎”；插件如 BRouter 备选复杂路径。
- 测试清单：下载同版欧洲地图，基准 500km 车 / 自行车路由；低端设备（2GB RAM）验证无 OOM。
此优化不复述新闻，而是提供工程化参数，帮助开发者复现或扩展 OsmAnd 式离线导航系统。
资料来源：
- OsmAnd 官方博客：https://osmand.net/blog/fast-routing/
- Hacker News 讨论：https://news.ycombinator.com/item?id=34545961
- OsmAnd 官网：https://osmand.net/