Optimización de próxima generación para Dasher Dispatch en DoorDash

En DoorDash, nuestro equipo de logística se centra en realizar entregas eficientes y de alta calidad. Nuestro sistema de envío es una parte de nuestra plataforma logística que tiene un impacto sustancial tanto en nuestra eficiencia como en la calidad. A través de un óptimo emparejamiento de los repartidores con las entregas, podemos garantizar que los repartidores hagan más en menos tiempo, que los consumidores reciban sus pedidos rápidamente y que los comerciantes tengan un socio fiable que les ayude a hacer crecer sus negocios. En esta entrada del blog, exploraremos:

• Antecedentes del sistema de despacho
• Nuestros enfoques de optimización anteriores y actuales y cómo queríamos reformularlos.
• Modificar un servicio de nivel cero sin tiempo de inactividad
• Trabajo futuro para mejorar nuestro optimizador

Fondo

DoorDash impulsa un mercado a la carta que implica la demanda de pedidos en tiempo real y la oferta de entrega. Los consumidores piden que un comerciante les entregue productos en su domicilio. Para satisfacer esta demanda, ofrecemos a los repartidores rutas de reparto en las que se mueven entre la recogida de pedidos en los comercios y su entrega a los consumidores. 

Nuestro sistema de envío busca una alta eficiencia de los repartidores y calidad de la entrega teniendo en cuenta la distancia en coche, el tiempo de espera para que un pedido esté listo, los tiempos de entrega vistos por el consumidor, etc. Dada la información incompleta sobre el mundo, el sistema genera muchas predicciones, como cuándo se espera que un pedido esté listo para su recogida, para modelar los escenarios del mundo real. Con estos datos, el sistema de despacho genera estados futuros para cada posible emparejamiento y decide la mejor acción a tomar, dados nuestros objetivos de eficiencia y calidad.

Optimización

Con los estados actuales de los dashers disponibles en la red (como a la espera de recibir un pedido, ocupado entregando un pedido), y la información de todos los pedidos pendientes de los consumidores, necesitamos generar posibles rutas para cada pedido, y elegir la mejor ruta para asignar en tiempo real. Nuestro sistema de despacho anterior asignaba una entrega a una ruta cada vez, por lo que lo planteamos como un problema de emparejamiento bipartito. El problema puede resolverse con el algoritmo algoritmo húngaro. Este planteamiento tiene dos limitaciones: 1) aunque el algoritmo húngaro es polinómico, el tiempo de ejecución de instancias grandes es excesivo para nuestro sistema dinámico en tiempo real; 2) no admite rutas más complicadas con 2 o más entregas.

Formular el problema como un programa de enteros mixtos (PIM) y resolverlo con un solucionador comercial puede resolver ambos problemas. En primer lugar, descubrimos que los solucionadores comerciales como Gurobi son hasta diez veces más rápidos que el algoritmo húngaro a la hora de resolver el problema de emparejamiento. Esta mejora del rendimiento nos permite resolver problemas de mayor envergadura, a partir de los cuales podemos perfeccionar nuestros modelos para impulsar las métricas empresariales. Además, el solucionador ofrece flexibilidad para formular el problema como un problema de rutas de vehículosque permite múltiples entregas en una ruta.

En cuanto a la formación matemática del problema, se utilizan variables binarias para representar las decisiones de emparejamiento de la máquina lanzadora con el pedido. La función objetivo se formula para optimizar tanto la velocidad de entrega como la eficiencia de la máquina, representadas por los coeficientes de puntuación del modelo. Se utilizan dos conjuntos de restricciones para definir la disponibilidad de las máquinas y las preferencias de ruta. El optimizador se ejecuta en varias instancias distribuidas en función de los límites regionales varias veces por minuto.

Notación

Formulación

Solucionadores de optimización

Existen múltiples opciones de solucionadores de optimización que podríamos utilizar para resolver nuestro problema. Experimentamos con el solver de código abierto CBC y con solvers comerciales como XPress, CPLEX y Gurobi. Al final decidimos adquirir la licencia del servicio en la nube de Gurobi para nuestro sistema de producción. La decisión se basó en la velocidad (los puntos de referencia de nuestros problemas concretos indican que Gurobi es 34 veces más rápido de media que CBC) y la escalabilidad de los solucionadores, la facilidad para abstraer soluciones factibles cuando la optimalidad es difícil, la capacidad de ajuste para diferentes formaciones, la integración relativamente sencilla de la API con Python y Scala, la flexibilidad del prototipo y las condiciones de licencia de despliegue de los proveedores, y el soporte profesional.

Aplicación

Dado que el envío de una pala para un pedido es un componente esencial de nuestro producto de entrega, el cambio a la nueva solución de optimización tenía que hacerse sin tiempo de inactividad y sin afectar a la calidad de la entrega. Normalmente, realizamos experimentos para nuevas funcionalidades y medimos el impacto en las métricas de calidad, pero como la optimización es una parte tan fundamental del algoritmo, un experimento es a la vez de mayor riesgo y no lo suficientemente granular como para entender el cambio en el nivel más bajo de detalle. Afortunadamente, una iniciativa para refactorizar nuestra base de código había finalizado más o menos al mismo tiempo. Uno de los cambios consistía en trasladar el código de optimización a un componente independiente detrás de una interfaz extensible, así que probamos un enfoque diferente.

En lugar de realizar un experimento, implementamos la lógica MIP como otro optimizador detrás de la interfaz existente, junto con código para convertir los parámetros estándar del optimizador en entradas del solucionador MIP. A continuación, creamos un tercer optimizador que combinaba los otros dos y comparaba los resultados de cada uno. El optimizador combinado devolvía los resultados del optimizador original, descartando los del optimizador MIP, y generaba registros con las diferencias entre las dos soluciones y cuál era la mejor. Con estos datos comprobamos que los resultados de los dos optimizadores coincidían más del 99% de las veces, y que los únicos desajustes se debían a situaciones en las que había varias soluciones igual de buenas. Esto nos dio confianza para adoptar el nuevo optimizador sin más pruebas y dio lugar a una transición fluida.

Resultados y trabajo futuro

Tras implementar la formulación MIP, ahora podemos resolver modelos más flexibles y complejos con mayor rapidez. Combinado con nuestro marco de experimentación, podemos iterar sobre nuestros modelos a un ritmo mucho más rápido. Estamos explorando diversas mejoras del modelo y de nuestro sistema de despacho.

La primera es que simplemente podemos resolver un problema mayor. Como el optimizador MIP es hasta 10 veces más rápido, podemos resolver el problema de emparejamiento de una región más grande en el mismo tiempo. Esto tiene la ventaja de ser más sencillo, ya que tenemos menos regiones que procesar, pero también es más óptimo. Con un problema de mayor tamaño, aumentamos el número de compensaciones que tiene en cuenta el optimizador y reducimos los efectos de borde causados por los límites entre regiones, lo que conduce a decisiones de mayor calidad.

Otra característica que ha permitido la nueva formulación es ofrecer varias entregas a la vez en rutas más complicadas, como ya se ha mencionado. Esto era una limitación del algoritmo húngaro, pero la flexibilidad del MIP nos permite tener en cuenta esas rutas, y las restricciones de la formulación garantizan que seguimos igualando correctamente cada entrega. Hacer coincidir estas rutas más complejas nos ayuda a dar entregas adicionales y más deseables a los dashers, y también allana el camino para crear nuevos tipos de productos.

Por último, estamos trabajando en fórmulas aún más complejas que combinan datos históricos y predicciones futuras para considerar el estado del mundo a lo largo del tiempo. A menudo hay casos en los que es mejor esperar para ofrecer una entrega en lugar de hacerlo de inmediato. Con la formulación MIP, podemos incorporar este tipo de consideraciones directamente en el modelo y aumentar la eficacia y calidad del sistema.

Factores de éxito y lecciones aprendidas

Es vital que el modelo que construyamos pueda representar fielmente el problema empresarial en cuestión, lo que requiere una comprensión precisa de la lógica y el flujo empresariales. Los coeficientes de las funciones objetivo también deben predecirse con exactitud para que el modelo proporcione realmente resultados optimizados para nuestra empresa. Pudimos conseguirlo trabajando estrechamente con nuestros modelos de aprendizaje automático para proporcionar predicciones precisas.

Otro factor que nos ayudó a que un proyecto como este tuviera éxito es la estrecha interacción entre nuestros científicos de datos e ingenieros de software. Tener un conocimiento más profundo del código base sobre el que se construye el modelo fue una gran ventaja para el éxito del despliegue del método que elegimos.

Lastly, we need our company's management team’s alignment since a project that involves a new data science method requires a longer-term strategic vision for it to be successful. These projects generally need a longer than regular feature development cycle for their fruition. Luckily, at DoorDash, our management team bought into investing in short-term as well as long-term bets.

Conclusión

Hemos visto el papel que desempeña la optimización para garantizar que todas las entregas de DoorDash sean de alta calidad y se realicen de forma eficiente. Discutimos las motivaciones para reencuadrar la optimización del problema de emparejamiento a una formulación MIP, y cómo llevamos a cabo quirúrgicamente el intercambio. Con nuestro nuevo método de optimización en su lugar, destacamos varias áreas de mejora que hemos desbloqueado, así como hacia dónde estamos mirando para el futuro.

Si te interesan los algoritmos en tiempo real en la intersección de la ingeniería, el aprendizaje automático y la investigación operativa, ¡ponte en contacto con nosotros! Estamos contratando personal para el equipo de envíos. Visite nuestra página de empleo para obtener más información: https://www.doordash.com/careers

Y, un agradecimiento muy especial a Richard Hwang por sus aportaciones y orientación en este proyecto.