Cómo calcula Google Maps la ruta más rápida sin probar todas las rutas

Cómo calcula Google Maps la ruta más rápida es una pregunta que empieza en 1956, en una terraza de Ámsterdam, con un holandés de 26 años tomando café con su prometida. Tú pides ruta de Madrid a Berlín, el móvil se lo piensa un instante y te la da. Detrás hay setenta años de ideas para evitar lo que parecería lógico: probar todos los caminos y quedarse con el mejor.

Por qué no se pueden probar todas las rutas

Para un matemático, una red de carreteras es un grafo: cruces unidos por tramos, y cada tramo con su coste en metros o en segundos. El número de caminos entre dos puntos crece de una forma absurda. En una cuadrícula de 9 por 9 manzanas hay 48.620 formas de ir de una esquina a la opuesta si solo avanzas hacia el destino. Si permites cualquier recorrido que no pase dos veces por el mismo cruce, salen más de 41 trillones, un 41 seguido de 18 ceros, según la enciclopedia de sucesiones de enteros OEIS.

Eso en 81 manzanas. La red de Europa occidental que usan los investigadores de rutas tiene 18 millones de nodos.

El truco del café: el algoritmo de Dijkstra

Edsger W. Dijkstra trabajaba en el Centro Matemático de Ámsterdam y necesitaba una demostración del ordenador ARMAC que entendiera cualquiera. Eligió el camino más corto entre Róterdam y Groninga. Según contó en una entrevista publicada en Communications of the ACM, lo diseñó en unos veinte minutos sentado en aquel café, sin lápiz ni papel. Lo publicó en 1959, en tres páginas de Numerische Mathematik.

La idea es avanzar como una mancha de aceite desde el origen. Siempre se explora el cruce más cercano que aún no está cerrado, se apunta cuánto cuesta llegar a sus vecinos y, cuando le toca el turno al destino, ese camino es con seguridad el más corto. No hace falta mirar las rutas una a una.

El problema: la mancha crece en todas direcciones

Dijkstra no sabe dónde está el destino, así que también explora hacia atrás. En la red europea, un Dijkstra bien programado tarda unos 2,2 segundos por consulta y revisa de media 9,3 millones de nodos, según la tabla de rendimiento del gran estudio sobre planificación de rutas de Delling, Sanders, Wagner y otros. Dos segundos parecen poco hasta que los multiplicas por millones de personas pidiendo rutas a la vez.

Los primeros parches fueron dos:

• Buscar desde los dos extremos. Una búsqueda sale del origen y otra del destino, y se paran al encontrarse. Dos círculos de medio radio ocupan la mitad que uno grande, así que se explora más o menos la mitad.
• Apuntar hacia el destino. El algoritmo A*, publicado en 1968 por Hart, Nilsson y Raphael, suma a cada cruce una estimación de lo que falta. Con distancias funciona bien. Con tiempos de viaje, la estimación segura es la distancia en línea recta dividida por la velocidad máxima de la red, que da por hecho que irás a tope todo el rato. Es tan optimista que la ganancia es pequeña o nula, como reconoce el mismo estudio.

La idea buena: preparar el mapa antes de que preguntes

Cuando conduces de Madrid a Berlín no te planteas cada calle de Burdeos. Sales a la autovía y al final bajas a calles locales. En 2008, en Karlsruhe, Robert Geisberger presentó con Peter Sanders, Dominik Schultes y Daniel Delling las jerarquías de contracción, que convierten esa intuición en matemáticas:

• Se ordenan los cruces de menos a más importantes.
• Se retiran uno a uno, empezando por los de menos importancia.
• Cada vez que quitar uno rompería un camino más corto, se añade un atajo que lo sustituye.
• Al consultar, las dos búsquedas solo suben hacia cruces más importantes y se encuentran arriba.

En la misma red europea, la consulta baja a unos 110 microsegundos y a 280 nodos revisados, con cinco minutos de preparación previa. Unas 20.000 veces más rápido que Dijkstra a pelo.

¿Y qué pasa con los atascos?

Un atasco cambia lo que cuesta cada tramo, y eso obliga a rehacer parte de la preparación. Para eso existen las variantes personalizables: la planificación de rutas personalizable (CRP) de Microsoft Research, que incorpora una métrica nueva «en pocos segundos», y las jerarquías de contracción personalizables de Julian Dibbelt, Ben Strasser y Dorothea Wagner. Las dos separan lo que casi nunca cambia, la forma de la red, de lo que cambia cada minuto, lo que se tarda en cada tramo.

Cómo calcula Google Maps la ruta más rápida: lo que cuenta y lo que se calla

Google no ha publicado qué algoritmo de rutas usa para coches. El estudio de Delling y compañía lo dice tal cual: las empresas suelen ser reservadas. Sí se sabe que Bing Maps usa CRP, que el motor libre OSRM usa jerarquías de contracción y que Google Maps usa desde 2010 un algoritmo llamado Transfer Patterns para el transporte público.

La parte que Google sí ha explicado es la del tiempo. En septiembre de 2020 contó en su blog que combina el tráfico en vivo con patrones históricos y que sus previsiones de llegada aciertan en más del 97 % de los viajes. Ese mismo día, DeepMind publicó que sus redes neuronales sobre grafos habían mejorado la precisión de esas previsiones un 51 % en Taichung y un 16 % en Londres.

Así que, cuando el móvil te da la ruta, hay dos piezas trabajando: una que adivina cuánto vas a tardar en cada tramo y otra que busca el mejor camino sin mirarlos todos. Y la segunda, por muchas capas de atajos que lleve encima, sigue haciendo por dentro lo que Dijkstra pensó en veinte minutos sin papel.