1. Introducción
Las plataformas de transporte de pasajeros en línea, como Uber, DiDi y Yandex, surgieron recientemente, mientras que rápidamente alcanzaron un tamaño impresionante y, a pesar de su corta edad, alteraron y complementaron significativamente el sistema de transporte de la ciudad. Las tecnologías y modelos teóricos utilizados por estas plataformas (o desarrollados para ellas) son actualmente un área de investigación activa para una amplia gama de especialistas en la comunidad científica: economistas, matemáticos, programadores e ingenieros.
En este artículo, nosotros (como representantes del equipo de Optimización del Mercado de Uber) presentaremos brevemente una mirada interna a las principales palancas para administrar la efectividad de las plataformas en línea: algoritmos responsables de enviar decisiones (emparejamiento), precios dinámicos y también presentaremos uno de los nuevos conceptos: tiempo dinámico de cita del automóvil (espera dinámica). Con base en la experiencia práctica real, mostraremos que los tres algoritmos juegan un papel importante en la creación de un sistema con alto rendimiento y bajos tiempos de espera para pedidos tanto de pasajeros como de conductores.
La descripción presentada de los algoritmos será de naturaleza exploratoria e intencionalmente desprovista de profundidad técnica y rigor. Se invita a un lector interesado a estudiar el artículo original (
Fijación dinámica de precios y emparejamiento en plataformas de transporte -
N. Korolko , D.Woodard, C.Yan, H.Zhu - 2019), publicado por investigadores del Uber Marketplace, en base al cual esta breve revisión introductoria y creado
2. Descripción de los algoritmos principales.
Durante la última década, la industria de soluciones de transporte ha crecido rápidamente gracias a nuevas ideas conceptuales y tecnologías, como las plataformas de transporte de pasajeros en línea, el desarrollo de automóviles autónomos y automóviles eléctricos. La sinergia de estas tecnologías, que muchas empresas y laboratorios están trabajando al mismo tiempo, promete un gran avance en la reducción del costo unitario del transporte de pasajeros, no menos de 10 veces en un par de décadas.
El crecimiento más explosivo de esta lista de tecnologías lo demuestran actualmente las plataformas de transporte de pasajeros en línea. Por ejemplo, Uber ha generado más de 10 mil millones de viajes en más de 80 países y 700 ciudades de todo el mundo durante sus 10 años de existencia [Figura 1]. El mercado global para este tipo de transporte en línea promete alcanzar un tamaño increíble de $ 285 mil millones para 2030. Por lo tanto, no es sorprendente que la efectividad de tales plataformas que controlan dinámicamente el mercado bilateral de pasajeros y conductores sea de gran importancia práctica.
Los estudios empíricos muestran que los algoritmos automatizados para el procesamiento de datos, enrutamiento, fijación de precios y pedidos permiten a las plataformas en línea lograr una mayor utilización de las horas de trabajo de los conductores y tiempos de espera más cortos para los pasajeros que un servicio de taxi clásico. Además, estas dos características clave del sistema (utilización del tiempo del conductor y del tiempo de espera de los pasajeros) están estrechamente relacionadas con la confiabilidad y la estabilidad del servicio: los brotes locales repentinos de demanda (por ejemplo, al final de un gran concierto o en la víspera de Año Nuevo) pueden empeorar significativamente ambas métricas, haciendo uso de servicio poco atractivo para ambos lados del mercado. Esto se debe al hecho de que los conductores en la línea en la zona de alta demanda reciben rápidamente una pequeña parte del número total de pedidos, y los conductores de áreas remotas se asignan a la parte restante de los pedidos. Esto aumenta el tiempo de entrega del automóvil, que a menudo no se paga al conductor (y, por lo tanto, reduce sus ganancias por unidad de tiempo), y al mismo tiempo forma una impresión negativa en el pasajero. Por lo tanto, ambas partes que usan la plataforma comienzan a usarla menos. Debido a esto, ambas métricas comienzan a deteriorarse aún más, lo que hace girar la espiral descendente del rendimiento de la plataforma en la dirección de eficiencia cero. En la literatura inglesa, este fenómeno negativo se llama Wild Goose Chase (WGC), cuya traducción literal es "la búsqueda del ganso salvaje".
Dos tecnologías clave destinadas a aumentar la estabilidad y la productividad de la plataforma son los algoritmos de distribución de pedidos y precios dinámicos. La primera tecnología controla las decisiones de despacho, y los precios dinámicos en tiempo real equilibran la relación de oferta-demanda extremadamente volátil para el transporte de pasajeros. La fijación dinámica de precios es fundamental para mantener el rendimiento del sistema, reducir el tiempo de espera de un automóvil y aumentar el número de conductores durante los períodos de alta demanda. Además, los estudios empíricos y teóricos muestran que los precios dinámicos pueden reducir la escala del efecto patológicamente peligroso de WGC.
2.1 Algoritmos para la distribución de pedidos (coincidencia)
El algoritmo de despacho más simple para asignar un controlador a pedido es el llamado protocolo de primer despacho. A pesar de su simplicidad y buenos indicadores de rendimiento prácticos, es fácil demostrar que este algoritmo es ineficaz en una gran cantidad de situaciones frecuentes. En primer lugar, selecciona un conductor solo de ese subconjunto de conductores que están libres en el momento del pedido, ignorando a aquellos conductores que pueden estar cerca de completar un viaje en las inmediaciones de un nuevo pedido [Figura 4]. En segundo lugar, este algoritmo simple tiene en cuenta solo la información sobre el sistema en un período de tiempo determinado, mientras que la mayoría de las veces se puede proporcionar a la plataforma información suficientemente precisa sobre lo que sucederá con el flujo de pedidos y la distribución espacial de los controladores en el futuro cercano. En la literatura, una clase de tareas similares que dan recetas prácticas de cómo se puede usar esa información para mejorar la calidad del algoritmo se denomina "problema del servidor K".
Otra familia popular de algoritmos de despacho se basa en la idea de combinar un grupo de órdenes de viaje en un corto intervalo de tiempo y resolver el problema de optimización agregada de la asignación por pares. En otras palabras, en lugar de asignar un automóvil de forma instantánea y secuencial a cada pedido individual, el sistema recopila información sobre los pedidos entrantes y distribuye los pedidos acumulados entre los conductores en la línea con cierta frecuencia. Si algunas órdenes se dejan sin un controlador designado, entonces permanecen en el sistema y participan en la tarea de distribuir el siguiente paso de tiempo. La función objetivo de la tarea de optimización que debe resolverse en cada paso puede incluir una amplia gama de métricas que caracterizan la calidad de las citas de despacho generadas: tiempo de espera del pasajero para el automóvil, distancia entre el pedido y el conductor designado, probabilidad de cancelación del pedido por parte del pasajero o conductor, etc.
En la práctica, los algoritmos de despacho parecen mucho más complicados, ya que deben tener en cuenta una gran cantidad de características de diferentes productos que se presentan simultáneamente en la interfaz de la aplicación. Por ejemplo, los automóviles registrados en la plataforma pueden ser de diferentes clases de confort y de diferentes capacidades. Algunos productos de plataformas en línea implican el uso simultáneo de un automóvil por diferentes pasajeros (UberPool, Lyft Line), si sus rutas están bastante cerca. Además, las decisiones de despacho a menudo deben tener en cuenta las preferencias de los conductores para las áreas de servicio y las instrucciones de los pedidos que reciben. Por lo tanto, la gama de problemas de optimización que surgen para aumentar la eficiencia de las decisiones de envío, que también deben resolverse en tiempo real, se actualiza continuamente con nuevas formulaciones cada vez más complejas.
2.2 Algoritmos de precios dinámicos
Una de las principales dificultades operativas en la gestión de la plataforma de transporte de pasajeros en línea es el volumen de la demanda y la oferta de servicios de taxi que cambian constantemente en el espacio y el tiempo. La figura a continuación [Figura 5] muestra la relación entre la cantidad de solicitudes de viaje en línea de los pasajeros y la cantidad de horas que los conductores pasaron en la línea en dos áreas de San Francisco: el centro financiero y el área residencial para dormir en las afueras de la ciudad. Este gráfico ilustra bien la alta volatilidad y la falta de equilibrio entre la oferta y la demanda (cuya relación a veces puede tomar valores extremadamente altos), así como la diversidad del comportamiento de este equilibrio dependiendo de la ubicación geográfica.
Para controlar el equilibrio de la oferta y la demanda en el espacio y el tiempo, las plataformas en línea utilizan algoritmos de fijación de precios dinámicos que aumentan la tarifa básica en tiempo real si el número de pedidos recibidos de los pasajeros supera significativamente el número de conductores gratuitos. Los beneficios de la fijación dinámica de precios para mantener un rendimiento estable de la plataforma están respaldados por una gran cantidad de modelos teóricos, experimentos y observaciones empíricas asociadas con cargas de sistema de récord. Tales cargas pueden ocurrir debido a una gran cantidad de razones predecibles y no muy importantes: condiciones climáticas adversas, eventos públicos, mal funcionamiento del sistema de transporte público, etc. En caso de funcionamiento incorrecto del algoritmo de fijación de precios, con un fuerte aumento en el número de solicitudes de pasajeros (o con una fuerte disminución en el número de automóviles disponibles), puede observar una proporción muy baja de pasajeros a los que se asigna el automóvil como resultado y el tiempo insatisfactoriamente alto de su envío. El papel clave de los precios dinámicos para una plataforma en línea es permitir que cualquier usuario en cualquier lugar y en cualquier momento llame a un taxi. Incluso si la tarifa propuesta es más alta de lo habitual, será una opción más favorable que informar al usuario de la plataforma (que puede necesitar urgentemente un automóvil) que actualmente no hay máquinas disponibles.
Los métodos populares de modelado dinámico de precios incluyen modelos económicos que describen los modelos de estado estable, modelos de programación dinámica, análisis de regresión y modelos de optimización que describen los efectos de la red. Estudios recientes de economistas (Castillo, 2017) mostraron que un aumento dinámico de las tarifas también permite que la plataforma evite caer en la zona del efecto negativo del WGC, del que hablamos anteriormente.
El precio dinámico tiene defectos objetivos. En primer lugar, el precio final de un viaje, que los pasajeros ven al pedir un taxi, puede variar significativamente debido a la volatilidad de la oferta y la demanda, lo que aumenta la imprevisibilidad de la tarifa en la misma ruta. Por otro lado, los conductores de plataformas en línea a menudo tienen acceso a información en la aplicación sobre aquellas áreas de la ciudad donde está activo el factor de aumento. Sin embargo, debido a la alta volatilidad de este coeficiente, para cuando el conductor se mude a la zona de precios más altos, la tarifa puede volver a los valores de referencia. Además, un aumento automático de tarifas por el algoritmo puede alentar a los conductores a cooperar y crear artificialmente en el mercado local una situación de escasez de automóviles disponibles para ordenar, activando así coeficientes crecientes para los viajes. Por supuesto, este comportamiento coordinado de los conductores no es difícil de detectar para las plataformas que procesan una gran cantidad de datos de pedidos y toman las medidas de protección necesarias, pero para los pasajeros, tal experiencia de precios artificialmente altos puede ser insatisfactoria.
2.3 Tiempo de espera dinámico del automóvil (espera dinámica)
Para evitar problemas asociados con la fijación dinámica de precios, en la práctica, se utilizan otros algoritmos para equilibrar la oferta y la demanda, así como para evitar que el sistema entre en la zona del efecto WGC. Estos incluyen la idea de limitar la distancia máxima entre el pedido y el conductor designado (Radio de envío máximo), así como la formación de una cola de órdenes de viaje (colas) recibidas en el sistema, reemplazando la cita instantánea del conductor para cada pedido.
Un concepto más nuevo destinado a reemplazar o complementar un aumento dinámico de los precios es el mecanismo para controlar dinámicamente el tiempo de espera antes de asignar un automóvil (espera dinámica). Una variante de este mecanismo se utiliza en el producto Express Pool, lanzado recientemente por Uber en algunos mercados grandes. Este tipo de transporte de pasajeros se caracteriza por las tarifas más bajas posibles e implica el uso simultáneo de un solo automóvil por varios pasajeros independientes para viajar en el camino.
La idea general del mecanismo de tiempo de destino dinámico es la siguiente. Para un pasajero que solicita un viaje, la aplicación no designa un conductor al instante, pero ofrece esperar, pero no más de una cierta cantidad de tiempo indicada con anticipación (los límites superiores típicos son 2 o 5 minutos). Además, la cita del conductor puede ocurrir en cualquier momento conveniente para la plataforma: desde el instante hasta el límite superior especificado. En este caso, el tiempo total de espera del pasajero para el automóvil consta de dos partes (casi independientes): el tiempo hasta que se nombra al conductor y el tiempo desde su cita hasta la llegada al lugar del pedido. El inconveniente de esperar a un pasajero se compensa con una tarifa más baja.
En el lado de la plataforma, se usa un grado adicional de libertad sobre el tiempo que se asignan los conductores a las órdenes de la siguiente manera. Dado que el producto implica la combinación de pedidos y la designación de un automóvil para el transporte simultáneo de varios pasajeros, el tiempo adicional para recopilar información le permite aumentar el número de opciones combinatorias y, como resultado, generar viajes más eficientes. En este caso, la métrica de eficiencia puede ser, por ejemplo, la proximidad de las rutas de los pasajeros que caen en un automóvil. Obviamente, tan pronto como la plataforma encuentre una combinación de viajes suficientemente efectiva, inmediatamente hace la cita necesaria para el conductor y notifica a todos sus participantes. Si no se encuentra una combinación exitosa y conveniente, entonces la plataforma envía un conductor individual a cada uno de los pasajeros que hicieron el pedido.
El mecanismo descrito optimiza principalmente las decisiones de despacho y el momento en que se toman estas decisiones, y puede usarse simultáneamente con la optimización dinámica de precios. El modelo teórico desarrollado y analizado en el original del artículo principal demuestra que la optimización simultánea de precios y tiempo tiene una gran cantidad de ventajas: puede reducir la volatilidad de las tarifas, reducir los riesgos del efecto WGC y también aumentar el número total de viajes generados por la plataforma por unidad de tiempo. Además, estas opciones de transporte son más económicas tanto para los conductores (que reciben simultáneamente a varios pasajeros que pagan el viaje) como para los pasajeros (que reciben un descuento a cambio de flexibilidad con el tiempo de espera).
3. Conclusión
En este artículo, describimos brevemente las principales tareas de gestión de optimización que resuelven las plataformas de transporte de pasajeros en línea para garantizar un funcionamiento estable y aumentar su eficiencia. Dichas tareas incluyen la construcción de algoritmos de despacho, algoritmos de fijación de precios dinámicos y la determinación dinámica de los tiempos de cita del conductor. La gestión simultánea de estas palancas permite lograr altas tasas de utilización del tiempo de los conductores, bajo tiempo de espera para el automóvil y la cantidad de viajes generados por la plataforma por unidad de tiempo. La clase de estas tareas se actualiza constantemente con ejemplos nuevos, cada vez más realistas, que abren amplios horizontes para la investigación teórica y práctica.
Todas las referencias a las fuentes citadas se pueden encontrar en el artículo original (
Precios dinámicos y emparejamiento en plataformas de transporte de pasajeros -
N. Korolko , D. Woodard, C. Yan, H. Zhu - 2019).