GPS, Waze: ¿cómo funcionan sus algoritmos?

Trabajar en el desarrollo de TI a menudo lleva a interesarse por el funcionamiento de las herramientas que podemos usar en el día a día. Este fue el caso en la carretera recientemente, con el lanzamiento de Waze, preguntándose cómo podrían funcionar los algoritmos de guía GPS. Porque cuando lo piensas, ir del punto A al punto B, con la multitud de rutas posibles, te puede marear un poco saber cuál elegir. Especialmente cuando agrega las restricciones relacionadas con las condiciones del tráfico que pueden cambiar rápidamente.

La idea en este artículo no es decirte con precisión cómo funcionan los algoritmos de GPS o Waze, porque son propietarios. Sin embargo, durante mucho tiempo ha habido una serie de algoritmos que deben desempeñar su papel en la «receta» para llegar a la mejor ruta.

Cuando lo piensas de una manera simple, para encontrar una ruta, tienes que:

cartografía actualizada, para tener en cuenta los últimos cambios (nuevas carreteras, cambio de sentido de la circulación, etc.)
calcular la mejor ruta entre dos puntos. En condiciones estándar, y teniendo en cuenta también eventos de tráfico (atascos, accidentes, cierres excepcionales, etc.)

GPS, Waze: tener cartografía actualizada

Hay varias posibilidades para tener una cartografía actualizada. Esto puede pasar a través de servicios de mapeo oa través de comunidades que mantienen un mapa actualizado. Por ejemplo, en Waze puedes enviar cambios en el mapa .

No podemos saber en detalle cómo funcionan los algoritmos de Waze u otros GPS. Pero también se puede imaginar que el algoritmo permite deducir información cartográfica. Por ejemplo, si un coche pasa por un lugar donde no se conoce ninguna carretera, puede surgir una duda. Si por allí pasan muchos coches, probablemente podamos deducir en algún momento la presencia de una carretera. Esto también puede ser cierto para las direcciones de tráfico. Un carril en sentido contrario pero ocupado por muchos vehículos durante varios días puede permitir deducir un cambio (incluso temporal por obras, por ejemplo).

Esto también puede causar algunos problemas en algunos casos. Recuerdo una vez que conducía por la Ile de Ré y Waze me envió por una carretera pequeña porque la carretera principal estaba atascada. Sin embargo, estaba prohibido excepto para vehículos agrícolas. Podemos imaginar que lo propuso porque cierto número de autos lo tomaron prestado.

GPS, Waze: encuentra la mejor ruta

Ahora que tenemos un mapa actualizado, necesitamos determinar la mejor ruta. Y aquí es donde las cosas se ponen difíciles. Porque imagina del punto A al punto B las posibilidades de itinerarios, con el número de opciones creciendo exponencialmente con la distancia.

Teoría de grafos

La primera clave es pensar en un mapa como un gráfico , con vértices y aristas. Los vértices son intersecciones y los bordes son los caminos que conectan estas intersecciones.

Una vez representada la gráfica, existen dos posibilidades para recorrerla:

Para el cálculo del recorrido, se privilegiará el recorrido en anchura.

En cuanto a la aplicación de estos algoritmos al desarrollo, te recomiendo que mires este artículo del blog “Soy dev”.

Algoritmo de Dijkstra

Ya sabemos cómo recorrer una gráfica, ahora la idea es hacerlo de la forma más óptima posible. Para responder rápidamente y evitar usar demasiados recursos computacionales innecesariamente. Esto es lo que propone el algoritmo de Dijkstra para calcular el camino más corto, publicado en 1959.

Te ofrezco dos videos explicativos sobre el tema, que valdrán más que un largo discurso para entender el principio:

El algoritmo A*

Siempre con la idea de optimizar al máximo los cálculos, existen otros algoritmos. Este es el caso del algoritmo A* . La idea es agregar criterios heurísticos a la búsqueda , es decir, criterios que permitan resolver un problema rápidamente, quizás no necesariamente de la manera más óptima. Esto significa que en muchos casos será más óptimo que Dijkstra. Pero en algunos casos más específicos no. Un posible criterio heurístico en el contexto de la búsqueda de ruta es la distancia en línea recta.

En el contexto de A*, la opción es tener en cuenta el costo anterior, el costo futuro y la distancia en línea recta para guiar las elecciones. La idea es decir que cuanto más te acerques al objetivo, mejor será la decisión.

Recomiendo este video (en ingles pero facil de entender) para aclarar todo esto

GPS, Waze: Calcular el tiempo de viaje

Vimos en el párrafo anterior que para encontrar la mejor ruta, varios algoritmos eran posibles. Pero todos ellos siguen la teoría de grafos. Es decir, desde el punto A, atraviesa crestas para llegar a otros picos y finalmente al punto B.

Entonces entendemos que el tiempo de viaje se puede asociar con un borde. A través de un atributo que indica el tiempo que se tarda en navegar por este último. De hecho, es fácil imaginar que los bordes pueden llevar una cierta cantidad de información útil:

distancia
hora de pasar por eso
posiblemente tasa de peaje
…

La siguiente pregunta es ¿cómo determinar este tiempo?

Una vez más, varias opciones son posibles. Este puede ser un tiempo teórico si no tenemos más información. Si por el contrario disponemos de datos relacionados con el uso del software, podemos ser más precisos. Esto es lo que hace Waze, cuando usas el software aprovecha la oportunidad para recuperar datos. En particular saber cuál es la velocidad en un borde, cuánto tiempo se tarda en cruzarlo. Los valores atípicos (conductor mucho más rápido o mucho más lento que los demás) se dejan de lado, como suele ocurrir en los estudios estadísticos.

Esta información se utiliza para dos cosas:

uso a corto plazo para poder dar a los automovilistas información actualizada sobre los tiempos de viaje. También tenga en cuenta la posibilidad a través de la aplicación de informar eventos (accidentes, ralentizaciones, vehículos detenidos, etc.).
un uso a largo plazo para tener datos estadísticos en el borde en cuestión. Esto permitirá por ejemplo hacer promedios según días y horas. Y para determinar incluso por adelantado un tiempo aproximado conduciendo en tal día a tal hora.

También he visto en un viaje reciente el uso de estos tiempos estadísticos en tiempos de viaje. Llegué un martes por la tarde a la región de París durante las vacaciones de Navidad. No se anunció ningún atasco de tráfico, pero creo que tuvo en cuenta las condiciones del tráfico en un martes por la tarde habitual (excluyendo los días festivos). Porque sobreestimó la ETA (hora estimada de llegada) al anticipar los atascos.

También puede ver el tráfico en tiempo real y calcular un tiempo de viaje estimado por hora en https://www.waze.com/livemap