Reinventando el algoritmo de precios para transportistas de Uber Freight para lograr mejores resultados
Por: Kenneth Chong (Científico Aplicado Sr.), Joon Ro (Científico Aplicado Sr.), Emir Poyraz (Ingeniero Sr.) y May Wu (Gerente de Ciencia Aplicada)
Una innovadora variante de un algoritmo clásico
Uber Freight opera un mercado de dos caras, que interactúa por separado con expedidores (quienes buscan transportar cargas del punto A al punto B) y con transportistas (conductores de camiones que mueven estas cargas). Ambos lados de este mercado funcionan mediante algoritmos de precios dinámicos. Cada uno está estructurado de manera ligeramente diferente según las necesidades del mercado respectivo.
Recientemente, nuestro equipo identificó la necesidad de cambiar el algoritmo que determina los precios para transportistas. El algoritmo genera una tarifa basada en diversos factores como las condiciones del mercado, el tamaño de la carga, la distancia para mover la carga, etcétera. Hasta este momento, utilizábamos un algoritmo basado en Procesos de Decisión de Markov (MDP) para establecer los precios para transportistas (consulta esta publicación anterior del blog para una descripción completa de cómo funciona el modelo MDP) porque es natural para nuestro problema: necesitamos tomar decisiones de precios secuencialmente a lo largo del tiempo. Sin embargo, con el tiempo, nos dimos cuenta de que, aunque el algoritmo tenía un buen rendimiento, presentaba deficiencias difíciles de abordar con una implementación estándar de MDP.
Superamos estos desafíos mediante:
La truncación de la inducción hacia atrás
Una mayor dependencia del aprendizaje automático (ML) para aproximar la función de valor
El desarrollo de un nuevo algoritmo de agrupamiento para identificar cargas "similares" que pueden ser útiles para estimar costos—combinando creativamente la optimización y el ML para desarrollar lo que consideramos una versión más robusta de MDP.
MDP es una elección natural de algoritmo, pero su implementación es desafiante
Para ilustrar brevemente el problema de los precios para transportistas, supongamos que hemos asumido un compromiso con el expedidor para transportar una carga desde Chicago, IL a Dallas, TX. La cita de recogida comienza exactamente dentro de 5 días: en otras palabras, el tiempo de anticipaciónT es de 120 horas**. Debido a que se vuelve más difícil encontrar transportistas con menor anticipación, los precios tienden a aumentar a medida que disminuye el tiempo de anticipación. Por lo tanto, tenemos una secuencia de decisiones que tomar a lo largo del tiempo, a la que nos referimos como una trayectoria de precios:
[Imagen: Figura 1: Ejemplo de una trayectoria de precios durante un tiempo de anticipación de 5 días]
Dado que actualizamos los precios cada hora, esta trayectoria puede representarse como una secuencia {pt}t∈{T, T-1, …, 0}, donde pt es el precio ofrecido t horas antes de la recogida. El objetivo de nuestro algoritmo es elegir una trayectoria que minimice, en expectativa, el costo total para cubrir la carga. Nos referimos a esta cantidad como eCost:
eCostT=∑t=T0 pt·Pr(Bt=1 | pt,St),
donde Bt = 1 si la carga i se reserva con un tiempo de anticipación t (0 en caso contrario), y St denota variables de estado (posiblemente variables en el tiempo) distintas del precio que pueden afectar la probabilidad de reserva. Esta cantidad generalmente aumenta a medida que pasa el tiempo y la carga permanece sin reservar.
Con MDP, calcular eCost implica resolver la ecuación de Bellman
Vt = minpt [Pr(Bt | pt, St)·pt + (1-Pr(Bt | pt, St))·Vt-1] t∈{0, 1, …, T}
Las cantidades {Vt} son directamente interpretables como eCost, condicionadas a nuestra política de precios. Sin embargo, un insumo crucial para MDP son estimaciones precisas de las probabilidades de reserva Pr(Bt=1 | pt, St). Aunque el modelo de ML que usamos para esto funciona bien, los errores pueden acumularse con el tiempo. Esto significa que nos volvemos vulnerables a la maldición del optimizador, que establece que en presencia de ruido, las estimaciones de costo total asociadas con la decisión óptima probablemente sean subestimadas. Esto, a su vez, conduce a precios más bajos y excesivamente optimistas que tienden a disminuir aún más con mayores tiempos de anticipación.
Además, la maldición de la dimensionalidad presenta desafíos significativos al modelar transiciones de estado más complejas. Por ejemplo, incorporar características en tiempo casi real (NRT), como la actividad de la aplicación, en nuestros precios implica agregarlas a las variables de estado, lo que rápidamente hace que nuestro problema sea computacionalmente inviable.
Nuestro enfoque: combinando cuidadosamente predicción y optimización
Para mejorar la precisión de los precios, exploramos el uso de un modelo predictivo, en lugar de una inducción hacia atrás estándar, para estimar eCost. En particular, realizamos K ≤ T etapas de inducción hacia atrás, y si la carga permanece sin reservar después de K horas, sustituimos el valor de continuación VT-K por una predicción de este modelo. En este caso, las ecuaciones de Bellman se convierten en:
Vt = minpt [Pr(Bt | pt, St)·pt + (1-Pr(Bt | pt, St))·Vt-1] t∈{T-K+1, …, T-1, T}
con la condición de frontera VT-K = eCostT-K.
[Imagen: Figura 2: Ilustración de la toma de decisiones secuencial en MDP]
Elegir un valor apropiado para K requirió cierta iteración, pero esta inducción hacia atrás truncada ayuda a mitigar cada uno de los problemas que destacamos anteriormente.
Un candidato inicial para tal modelo predictivo fue un conjunto XGBoost que habíamos utilizado previamente en otros aspectos de los precios para transportistas. Los datos de entrenamiento consistían en cargas históricas, sus características (las describimos con más detalle a continuación), los tiempos de anticipación en los que fueron reservadas, así como sus costos realizados.
Sin embargo, las predicciones generadas por este modelo no eran adecuadas para estimar eCost por dos razones.
Hay una distinción importante entre el tiempo de anticipación restante de una carga y su tiempo de anticipación disponible. Si bien incluiríamos el primero en el vector de características al momento de servir, hay patrones sistemáticos en el segundo. Es decir, cargas similares tienden a estar disponibles en tiempos de anticipación específicos. Por ejemplo, los transportes más largos tienden a estar disponibles con mayores tiempos de anticipación que los transportes más cortos. Por lo tanto, tendríamos concentraciones de puntos de datos alrededor de ciertos tiempos de anticipación disponibles, lo que hace que las predicciones en otros tiempos de anticipación sean menos confiables.
Los datos de entrenamiento consistían únicamente en resultados—las realizaciones de variables aleatorias, en lugar de sus expectativas—por lo que las predicciones de este modelo tampoco podían interpretarse como un eCost. No estaba claro cómo modificar el conjunto de entrenamiento para que las predicciones del modelo XGBoost pudieran tratarse como expectativas.
En lugar de intentar predecir eCost directamente, tomamos principios del agrupamiento para encontrar un conjunto de cargas similares a la que se va a cotizar, y calculamos un promedio ponderado de sus costos totales. Con este enfoque, los tiempos de anticipación restantes pueden incorporarse explícitamente en eCost—podemos excluir, del conjunto de cargas similares, aquellas que fueron reservadas antes que el tiempo de anticipación restante de la carga actual. Además, cada una de las cargas similares identificadas puede verse como un resultado potencial para la carga actual, a las que se les asignan probabilidades iguales a los pesos utilizados en el promedio.
El desafío principal aquí es desarrollar una forma de medir la similitud entre cargas, que describimos con varios atributos:
Ubicaciones de las instalaciones de recogida y entrega
Hora del día, día de la semana en que está programada la recogida o entrega de la carga
Condiciones del mercado en torno al momento en que está programado el traslado de la carga
Hay una mezcla de características continuas y categóricas, y no está claro en absoluto cómo deberían ponderarse entre sí al calcular la similitud.
... con un algoritmo de agrupamiento no convencional
Desarrollamos un nuevo algoritmo donde nuestro modelo XGBoost mencionado anteriormente se utiliza para realizar el agrupamiento. Consideremos el caso simple donde nuestro modelo es un único árbol de decisión (poco profundo) con una sola característica: la distancia de conducción. Podríamos obtener un árbol como el siguiente:
[Imagen: Figura 3: Ilustración de un único árbol de decisión para agrupamiento]
Dos cargas pueden considerarse "similares" si sus predicciones se realizan desde el mismo nodo hoja. En el caso del nodo hoja #6, sabemos que las distancias de sus rutas están ambas entre 282 y 458 millas.
Esto puede parecer una forma rudimentaria de medir la similitud, pero al desarrollar árboles de decisión más profundos e incorporar más características, requerimos que las dos cargas tengan valores comparables en varias dimensiones para ser consideradas "similares". Podemos diferenciar aún más cultivando árboles adicionales. En resumen, asociamos con cada carga un vector de incrustación, que consiste en valores distintos de cero en ubicaciones que coinciden con los nodos hoja en los que cae la carga. Medimos la similitud entre cargas a través de la similitud del coseno de sus incrustaciones, que está directamente relacionada con el número de árboles en los que ambas tienen nodos hoja comunes.
Precios más estables llevaron a mejores resultados de reserva
Dados los cambios bastante sustanciales que hicimos al algoritmo, realizamos una implementación en dos fases principales. Primero, incorporamos eCost en los algoritmos que usamos en canales de reserva secundarios y realizamos una prueba A/B para garantizar que no hubiera disminución en el rendimiento. Segundo, ejecutamos un experimento de alternancia comparándolo con la versión anterior de MDP. El efecto neto de estos dos experimentos fue una reducción estadísticamente significativa en el costo total de cobertura de cargas, sin ningún impacto negativo en métricas secundarias. Atribuimos esto a las trayectorias de precios más estables generadas por el nuevo algoritmo, lo que resulta en que las cargas se reserven antes en sus ciclos de vida. Esto es particularmente relevante, ya que los costos tienden a aumentar bruscamente una vez que los tiempos de anticipación caen por debajo de las 24 horas.
Con la implementación de este nuevo algoritmo vienen una serie de beneficios secundarios. La reserva más temprana de cargas, debido a trayectorias de precios más estables, no solo reduce los costos sino que es crucial para evitar los fuertes aumentos de costos asociados con tiempos de anticipación más cortos. Reducir el costo total para cubrir cargas nos permite ofrecer precios más competitivos a los expedidores, lo que, a su vez, aumenta el volumen. Además, las trayectorias de precios más planas podrían llevar a los transportistas a verificar las cargas en la aplicación más temprano en sus ciclos de vida. Más allá de estas ventajas comerciales, el algoritmo también ha contribuido a reducir la deuda técnica al unificar los precios en todos los canales de reserva, así como al eliminar componentes no esenciales utilizados en la implementación anterior de MDP.
Aunque creemos que hay áreas para seguir mejorando, este nuevo algoritmo de precios proporciona un modelo para cómo se puede aplicar MDP a nuevos casos de uso dentro de Uber Freight.
*Dado que también estamos usando eCost como una especie de aproximador de función de valor, el problema que ahora resolvemos comparte algunas similitudes con un programa dinámico aproximado.