Cientos de miles de rutas por segundo por núcleo. Experiencia Yandex.Routing

Hace un par de semanas, Danya Tararukhin le contó a Habré cómo apareció nuestro servicio, Yandex.Routing, y cómo ayuda a las empresas con la logística. Al crear la plataforma, resolvimos varios problemas interesantes, uno de los cuales está dedicado a la publicación de hoy. Quiero hablar sobre la planificación de rutas en sí y los recursos necesarios para esto.

Encontrar la mejor ruta entre múltiples puntos es un clásico problema de optimización discreta. Para resolverlo, debe conocer las distancias y los tiempos de viaje entre todos los puntos. Es decir, conocer la matriz de distancias y tiempos. Hace dos años, un cálculo de matriz largo era un problema muy crítico para nosotros y bloqueaba el desarrollo. La búsqueda de la solución óptima con la matriz conocida tomó 10 minutos, pero el cálculo de todas las celdas de la matriz para tareas grandes (para varios miles de pedidos) tomó horas.

Para resolver el problema con cinco mil pedidos, debe conocer las distancias y los tiempos de viaje entre todos los puntos. Estas son dos matrices de números con una dimensión de 5000x5000. Planificamos rutas de mensajería para todo el día, y por la mañana el servicio de mensajería llegará de un punto a otro en una hora y por la noche, por otra. Por lo tanto, debe calcular la matriz de tiempos y distancias para cada hora del día. No todas las horas del día son únicas, pero el tiempo de corcho (mañana y tarde) debe cubrirse bien. Por lo tanto, llegamos a una configuración con segmentos de trece horas. En total, necesitamos dos cubos (tiempos y distancias) cada uno de 13x5000x5000. Estos son 325 millones de rutas, calculadas de acuerdo con el gráfico real de carreteras, en el que 165 millones de bordes. El cálculo de una ruta en un algoritmo bien optimizado del equipo Yandex.Maps dura unos 10 ms, para un total de 900 horas de cálculos.Incluso en paralelo a 900 CPU, debe esperar 1 hora. No pudimos iniciar dicho servicio, necesitábamos un algoritmo más adecuado.

Para leer más, es útil conocer el algoritmo de Dijkstra para encontrar la ruta más corta en un gráfico. Se puede imaginar como una "ola" que emana del punto de inicio de la ruta y recorre todo el gráfico hasta que se alcanza el punto final. En este caso, el tiempo de ejecución del algoritmo es proporcional a los bordes del gráfico, es decir, el área cubierta por la ola:



casi todos los candidatos para una entrevista en una entrevista conocen el primer paso para optimizar dicha tarea: puede comenzar la ola desde dos lados y finalizar la búsqueda cuando las olas se encuentran. El área total de dos ondas de medio radio es menor que una grande.



El gráfico de ruta real está bastante estructurado, y esto se puede utilizar. Cuando esté buscando la distancia más corta entre Moscú y San Petersburgo, en Dijkstra clásica, se verá obligado a extender la ola en un círculo y a clasificar por todas las calles y callejones de Moscú, las ciudades y pueblos de la región de Moscú, las calles Tver y Novgorod. Esta es una gran cantidad de cálculos, pero puede prepararse con anticipación y recordar las rutas óptimas entre ciudades (también conocidos como atajos) y no repetirlas en tiempo de ejecución. Luego, para encontrar la ruta entre dos puntos en el Dijkstra jerárquico, debe calcular las distancias más cortas al acceso directo deseado. Como los niveles jerárquicos pueden no ser dos, sino 5-6, reducen drásticamente el tiempo de búsqueda.

El equipo del enrutador de tarjetas ha implementado tales optimizaciones durante bastante tiempo. Fueron ellos los que hicieron posible alcanzar 10 ms para encontrar una ruta entre dos puntos. :) Entonces, por ahora, no nos hemos acercado a resolver nuestro problema.

Dado que el modo de búsqueda punto a punto ya está extremadamente optimizado, podemos optimizar el cálculo de la serie en la matriz. Una fila es la distancia desde un punto a todos los demás. Mientras buscamos la distancia hasta el punto más lejano, calculamos simultáneamente las distancias a las más cercanas. Por lo tanto, calcular la serie es equivalente a calcular la distancia al punto más lejano.



Observamos el momento de calcular la serie usando este algoritmo y recordamos que el cálculo secuencial de 5000 rutas tomaría aproximadamente 5000 * 10 ms = 50 s:


El gráfico muestra el tiempo de cálculo de una fila en una matriz de distancia de tamaño 1 * N para diferentes N (según datos reales). Se puede ver que el cálculo de la fila de tamaño 1 * 5000 de interés para nosotros cabe en 1.3 segundos. Se ha agregado una línea de tendencia al gráfico, que muestra que el tiempo de cálculo está creciendo un poco más lento que linealmente en N, el orden de N ** 0.74 ¡

Ya no está mal! Con este algoritmo, podemos calcular nuestro cubo en 13 * 5000 * 1.3 s = 84 500 s = casi 24 horas. Es paralelo en filas fácilmente, y cuando se usan 50 CPU, las distancias se calculan en media hora. El orden de complejidad del algoritmo de cálculo del cubo es O (N ** 1.74):


13 N*N 50 CPU ( 13*N/50). , 5000 , . 10 000, : .

De esta forma, hace dos años y medio, lanzamos la primera versión de nuestra API, que resuelve el problema de logística. Los clientes a menudo se quejaron de un largo tiempo de decisión, y son fáciles de entender: comenzaste una tarea para resolver, esperas 1 hora, obtienes una solución y entiendes que olvidaste arreglar el turno con el conductor, lo corriges y todo comienza de nuevo. Los conductores comienzan a ponerse nerviosos porque corren el riesgo de entrar en la hora pico de la mañana o incluso no tienen tiempo para entregar el pedido a tiempo. Era necesario hacer algo. No queríamos "tirar" el problema con el hierro: nos estábamos preparando para cargas pesadas, habría requerido mucho hierro, y la compra de servidores no está sucediendo de inmediato.

Un estudio de artículos académicos mostró que, resulta que hay algoritmos con complejidad lineal para esta tarea *! (En el artículo de referencia, hay una gran visión general de todo tipo de métodos modernos de aceleración de Dijkstra, incluso para el caso de la matriz.) Calcular la matriz en tiempo lineal no cabía en mi cabeza. Uno de nuestros desarrolladores se ofreció como voluntario para escribir un prototipo, y esto es lo que sucedió: el


tiempo para calcular una matriz de tamaño N * N en una CPU utilizando el algoritmo de "matriz rápida". La complejidad se obtiene del orden de O (N ** 1,1). Las N altas se eliminan de la línea de tendencia, ya que la generación de la respuesta y su descarga a través de la red ya influyen más en el tiempo.

¡115 segundos por matriz de 5000x5000 usando un solo núcleo y una dependencia casi lineal de N. Fiction se ha convertido en una realidad! La idea del algoritmo combina las dos ideas descritas anteriormente: Dijkstra para series y búsqueda jerárquica. Obviamente, comenzando a calcular la segunda fila, en algún momento volveremos a recorrer la misma área del gráfico que acabamos de recorrer, calculando la fila anterior. Por lo tanto, memoricemos las distancias más cortas a todos los destinos en los nodos del gráfico jerárquico. Cuando comenzamos a calcular la siguiente serie, luego de haber alcanzado dicho nodo, obtendremos de inmediato casi todas las distancias a otros puntos.



Hace un año y medio, esto nos permitió ahorrar media hora de tiempo con eLogística y reducir significativamente la ingesta de hierro. Anteriormente, para una solicitud grande, necesitábamos 50 núcleos durante media hora, pero ahora, 13 núcleos durante 2 minutos. Esto es aproximadamente 200,000 rutas por segundo por núcleo. Ese raro caso cuando el nuevo algoritmo no solo cierra la clase de problemas, sino que expande nuestras ideas sobre lo posible.

---

_{^{* Artículo "Planificación de rutas en redes de transporte", ver párrafo 2.7.2 "Rutas más cortas por lotes"}}