OsmAnd, una popular aplicación de mapas sin conexión, ha lanzado un nuevo motor de enrutamiento llamado Highway Hierarchy (HH) Routing, que promete una mejora de velocidad de hasta 100 veces en comparación con su algoritmo anterior (A). La necesidad surgió debido a que el algoritmo A original, aunque flexible, se volvía lento al procesar mapas cada vez más detallados y solicitudes de rutas complejas. OsmAnd exploró soluciones estándar como Contraction Hierarchies (CH), pero estas resultaron inviables debido a sus limitaciones en flexibilidad, tamaño de almacenamiento y compatibilidad con mapas regionales y actualizaciones frecuentes.
El nuevo motor HH Routing se basa en un sistema de dos niveles que divide el mapa en 'clusters' o áreas, con puntos de frontera predefinidos y 'shortcuts' precalculados entre ellos. Un algoritmo inspirado en Ford-Fulkerson se utiliza para identificar estos puntos de frontera, optimizando el equilibrio entre la reducción de puntos y la eficiencia del enrutamiento. Este enfoque permite a OsmAnd mantener su flexibilidad de personalización, su tamaño de archivo reducido (alrededor de 800MB para todo el mapa de carreteras) y su capacidad de actualización en tiempo real, a la vez que ofrece una navegación sin conexión significativamente más rápida.