Una de las tareas principales en Yandex.Taxi es cómo asegurarse de que un automóvil llegue rápidamente al usuario, y se reduzca el tiempo del conductor para "marcha en vacío" (es decir, el tiempo cuando está en la línea sin un pasajero). Parecería que todo es simple: el usuario selecciona la tarifa, indica deseos adicionales (asiento infantil, por ejemplo). Queda por filtrar los controladores en la línea de acuerdo con estos criterios, seleccionar el más cercano y ofrecerle un pedido. Sin embargo, todo es tan simple solo a primera vista.
Hoy contaré a la comunidad de Habr cómo elegimos el controlador más adecuado y cómo este proceso ha evolucionado con el tiempo. Aprenderá acerca de dos enfoques para resolver el problema.
Arquitectura de búsqueda general
Cuando el usuario hace clic en el botón "Llamar a un taxi", se crea un objeto de pedido en el back-end y su procesamiento comienza de acuerdo con la máquina de estados. Para que la orden pase del estado "Pendiente" a "El conductor está asignado", debe encontrar el controlador, ofrecerle una orden y esperar la confirmación de que la orden ha sido aceptada.
Enfoque codicioso
Durante mucho tiempo, un enfoque
codicioso funcionó en Yandex.Taxi. Con este enfoque, en la etapa de búsqueda del contratista, se realiza una solicitud al microservicio Tracker, que es responsable de los controladores. Tracker sabe todo sobre los automóviles: desde el color y la marca hasta su
ubicación actual . El rastreador tiene un índice geográfico local para controladores y conectores para servicios de enrutamiento (enrutadores) para construir rutas desde el punto A al punto B (e incluso a través de los puntos B, D, D). Por lo tanto, cuando se realiza una solicitud para buscar un conductor, el Rastreador primero determina los automóviles más cercanos en el geo-índice local a lo largo del radio directo, teniendo en cuenta las restricciones de orden "duras" (clase de automóvil, requisitos: asiento infantil, números amarillos). Luego, se especifica el tiempo y la duración de la ruta de suministro del vehículo y, teniendo en cuenta esta información, se selecciona la mejor opción.
Más tarde, esta lógica evolucionó: para cada conductor comenzaron a contar con su "puntuación" en el pedido, una función del momento en que se entregó el automóvil. Y los conductores ya estaban clasificados por valor de puntuación. La función tiene en cuenta no solo el tiempo de entrega en sí, sino también muchos otros factores: desde el nivel de demanda en los puntos A y B hasta la "experiencia" del conductor. Esta cita codiciosa se llama un bono.
Enfoque de búfer (haz)
Sin embargo, con un enfoque codicioso, el conductor más cercano recibirá al que primero ordenó un taxi. Sin embargo, algunos usuarios pueden incluso quedarse sin automóvil.
Con una mayor demanda, cuando comienza la competencia por los artistas, el enfoque codicioso no es bueno. Para satisfacer la demanda tanto como sea posible incluso en las horas más ocupadas, utilizamos muchos enfoques y algoritmos. Uno de ellos es la designación de buffer (haz) de los conductores en los pedidos. Se basa en la conocida tarea del campo de la optimización combinatoria:
el problema de asignación . En resumen, su esencia: tengamos N obras y M artistas, cualquier empleado puede completar cualquier tarea durante el tiempo p (i, j) [0 <= i <N, 0 <= j <M]. Es necesario asignar dicho contratista a cada tarea para reducir el tiempo total de ejecución de todo el trabajo (en este caso, un contratista puede ocupar solo un trabajo).
Al resolver dicho problema de asignación, nuestro "costo" de realizar el trabajo (orden) por el albacea (flota de taxis y conductor) es el valor de la función de puntuación desde el momento en que el vehículo fue entregado al usuario. La tarea se puede describir en términos de gráficos bipartitos: por un lado, órdenes, por otro, ejecutantes. Entre las órdenes y los ejecutantes hay bordes ponderados (puntuación). Por lo tanto, uno de nuestros objetivos es minimizar el tiempo total de entrega del vehículo maximizando el número de pedidos completados (coincidencia máxima). Una de las formas más famosas de resolver este problema es el
algoritmo húngaro .
Obviamente, con una cita intermedia, no podemos dar un controlador a pedido, como con un enfoque codicioso. Primero debe poner el pedido en la cola, luego jugar e informar sobre el controlador encontrado. Esto no encajaba en la máquina de estado del procesamiento de pedidos en absoluto, y tuvo que mejorarse un poco. Para probar y crear una nueva solución sin afectar a nuestros colegas, acordamos de inmediato que haríamos todo en un microservicio DriverDispatcher por separado. Tomará órdenes, hará cola, buscará conductores y guardará los resultados de las manifestaciones.
En primer lugar, tuvimos que preparar el Rastreador para un nuevo perfil de carga. Si con un enfoque codicioso, las solicitudes de controladores simplemente caían individualmente en el equilibrador de Tracker y se redirigían a sus instancias con equilibrio de carga, entonces, en el destino del búfer, todas las solicitudes eran de una máquina: las solicitudes individuales simplemente obstruirían el grupo de conexiones. Por lo tanto, agregamos al rastreador la capacidad de procesar lotes de solicitudes que se procesaron simultáneamente dentro del rastreador. En el camino, también tuvimos que resolver el problema de un número razonable de solicitudes de procesamiento por lotes. Del lado del cliente (DriverDispatcher), dividimos el lote grande en varios pequeños y lo enviamos a diferentes instancias de Tracker.
Entonces, el rastreador está preparado, la puntuación se considera tanto en Tracker (cita codiciosa) como en el nuevo servicio (DriverDispatcher'e), el algoritmo para resolver el problema de asignación se depura y funciona correctamente. Se planteó la cuestión de cómo integrar todo esto en la máquina de estado del procesamiento de pedidos. Agregamos el envío y la eliminación de la metainformación del pedido en DriverDispatcher cuando el pedido se transfiere de estado a estado. Y eso casi funcionó. Casi, porque las iteraciones de búsqueda de un contratista para ordenar no se controlaron externamente. Podríamos simplemente reemplazar el viaje al rastreador con el conductor con un viaje a nuestro servicio y darle al conductor cuando se encuentre, y antes de eso solo dar 404. Pero esto es malo, porque necesita ofrecer un pedido al conductor tan pronto como encontramos un pedido, e incluso varios los segundos de retraso juegan un papel aquí: el conductor simplemente puede girar en la dirección equivocada, y el orden será irrelevante. Para hacer esto, hicimos posible llamar el proceso de búsqueda de un artista sin afectar las tareas planificadas. Así que guardamos la lógica de búsqueda (con nuevas solicitudes) y agregamos la capacidad de llamarla fuera del programador.
Por lo tanto, pudimos combinar la máquina de estado principal para el procesamiento de pedidos con la máquina de estado en el despacho del búfer sin afectar la lógica de trabajo y sin correr entre estados. Puede ejecutar los primeros experimentos con usuarios en vivo.
Todo esto es muy bueno, pero ¿qué pasa con el tiempo para buscar un artista? Si la búsqueda no se lleva a cabo inmediatamente después de recibir el pedido, ¿aumenta el tiempo de búsqueda y, como resultado, se compensa con una alimentación más rápida? Esto no es del todo cierto: con la ayuda de varias técnicas (incluido el uso del aprendizaje automático), pudimos aislar casos cuando la espera tiene sentido, en otros casos, el tiempo de espera no cambia.
Pin dibujar
Otra forma de encontrar un artista más rápido es comenzar a buscarlo ANTES de crear un pedido. Cuando aparece un nuevo
pin (es decir, el usuario solo ingresa los datos del pedido en la aplicación), los
algoritmos de aprendizaje automático evalúan la probabilidad de que siga un pedido y deciden si se debe tener en cuenta al almacenar en memoria intermedia los controladores. Podemos encontrar el automóvil por adelantado, y cuando el usuario hace clic en el botón de pedido, inmediatamente haga una oferta a un conductor adecuado.
Conclusión
Hacer coincidir los pedidos y los conductores no es una tarea fácil; requiere tener en cuenta muchos factores. Uno de ellos es el contexto de los movimientos de los conductores al elegir candidatos para el orden. Hablaremos de esto en las siguientes publicaciones.
Otros puestos de tecnología de taxi