Qué son las contraction hierarchies, el truco que calcula rutas en microsegundos
Qué son las contraction hierarchies (jerarquías de contracción): la técnica de Karlsruhe de 2008 que ordena los cruces por importancia, añade atajos y calcula rutas continentales en microsegundos.
Qué son las contraction hierarchies, o jerarquías de contracción, se explica mejor con un pueblo partido por un río y un solo puente. Si vives al otro lado y quieres ir a cualquier sitio, pasas por ese puente. Si alguien te pide la ruta entre dos casas que están en orillas distintas, no hace falta que mires cada callejón del pueblo: lo primero es saber que el camino cruza el puente. El resto es llegar hasta él y salir de él.
En 2008, en la Universidad de Karlsruhe, Robert Geisberger presentó con Peter Sanders, Dominik Schultes y Daniel Delling un artículo titulado «Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks», salido de su tesis de diploma. Esa intuición del puente, convertida en método, sigue hoy dentro de muchos programas de rutas.
El problema que resuelven
El método clásico para el camino más corto es el de Edsger Dijkstra, publicado en 1959. Funciona como una mancha de aceite que crece desde el origen hasta tocar el destino. Es exacto, pero en una red de un continente la mancha es enorme. En la red de Europa occidental que se usa como banco de pruebas, con 18 millones de nodos y 42 millones de tramos, un Dijkstra bien programado tarda unos 2,2 segundos por consulta y revisa de media 9,3 millones de nodos, según la tabla 1 del estudio de referencia sobre planificación de rutas.
El otro extremo sería calcular de antemano todas las rutas posibles y guardarlas en una tabla. La consulta sería instantánea, pero el mismo estudio calcula que esa tabla necesitaría más de un petabyte de memoria. Las jerarquías de contracción buscan el término medio: algo de trabajo previo, consultas rapidísimas.
Qué son las contraction hierarchies, paso a paso
El método tiene dos fases. La primera se hace una vez, antes de que nadie pida una ruta.
- Ordenar los cruces por importancia. El puente del pueblo es muy importante; la entrada a una calle sin salida, casi nada. Geisberger usaba una fórmula que, entre otras cosas, mira cuántos atajos haría falta añadir si se quitara ese cruce.
- Contraer. Se retiran los cruces de uno en uno, empezando por el menos importante. Al quitar uno, se mira si algún camino más corto pasaba por él.
- Añadir atajos. Si lo había, se pone un atajo que lo sustituye.
Un ejemplo pequeño. Tres cruces en fila, X, Y y Z, con 3 minutos de X a Y y 4 de Y a Z. Y es poco importante y se contrae primero. Si no hay otra forma de ir de X a Z en 7 minutos o menos, se añade un atajo X–Z de 7 minutos. Ese atajo no existe en el asfalto. Es una nota que dice «de aquí a allí hay 7 minutos, pasando por cruces que ya no hace falta mirar».
La segunda fase es la consulta. Se lanzan dos búsquedas de Dijkstra, una desde el origen y otra desde el destino, con una sola regla: solo se puede subir hacia cruces más importantes. Las dos acaban encontrándose arriba, en el cruce más importante de la ruta, que suele ser algo parecido al puente del pueblo. Los atajos garantizan que no se pierde ningún camino más corto por el camino.
Cuánto se gana
En la misma red europea, la tabla del estudio da para las jerarquías de contracción unos 110 microsegundos por consulta y 280 nodos revisados, tras unos cinco minutos de preparación. Frente a los 2,2 segundos de Dijkstra, es unas 20.000 veces más rápido. Y los datos ocupan más o menos lo mismo que el propio mapa.
El problema de los atascos y la versión personalizable
La pega aparece cuando cambian los tiempos de los tramos, que es lo que pasa con el tráfico. El orden de importancia y los atajos se calcularon con unos tiempos concretos. Para eso se separó el trabajo en tres fases. En 2011, Daniel Delling, Andrew Goldberg, Thomas Pajor y Renato Werneck, de Microsoft Research, presentaron la planificación de rutas personalizable, capaz de incorporar una métrica nueva «en pocos segundos». Julian Dibbelt, Ben Strasser y Dorothea Wagner llevaron esa idea a las propias jerarquías con las jerarquías de contracción personalizables, publicadas en 2016. Ordenan los cruces por disección anidada, que consiste en partir el mapa en dos por el menor número posible de cruces (los puentes), y después cada mitad otra vez, y así hasta el final. La forma de la red casi nunca cambia y se prepara una vez; los tiempos de los tramos cambian a todas horas y se recalculan aparte, deprisa.
¿Lo usa Google Maps?
No se sabe. Google no ha publicado qué usa para calcular rutas en coche, y el estudio de referencia recuerda que las empresas suelen guardarse estos detalles. Lo que sí es público: según ese mismo trabajo, Bing Maps usa la planificación personalizable de Microsoft y el motor libre OSRM, que trabaja con datos de OpenStreetMap, usa jerarquías de contracción. De Google se sabe cómo predice el tráfico, porque lo explicó en su blog en 2020: mezcla datos en vivo con patrones históricos.
En OSRM, cada vez que alguien pide cómo llegar a un sitio, se lanzan esas dos búsquedas que suben por la jerarquía hasta encontrarse en su puente.
