Tres preguntas: mejorar la logística de última milla con aprendizaje automático

En todo el país, cientos de miles de conductores entregan paquetes y paquetes a clientes y empresas todos los días, y muchos tiempos de clic hasta la puerta promedian solo unos pocos días. Coordinar una hazaña de esta magnitud en la cadena de suministro de manera predecible y oportuna es un problema de investigación de operaciones de larga data, donde los investigadores han estado trabajando para optimizar la última parte de las rutas de entrega. Esto se debe a que la última fase del proceso suele ser la más costosa debido a ineficiencias como largas distancias entre paradas debido al aumento de la demanda del comercio electrónico, retrasos climáticos, tráfico, falta de disponibilidad de estacionamiento, preferencias de entrega de los clientes o camiones parcialmente llenos. ineficiencias que se han vuelto más exageradas y evidentes durante la pandemia.

Con tecnología más nueva y datos más individualizados y matizados, los investigadores pueden desarrollar modelos con mejores opciones de enrutamiento pero al mismo tiempo necesitan equilibrar el costo computacional de ejecutarlos. Matthias Winkenbach, científico investigador principal del MIT, director de investigación del Centro de Transporte y Logística (CTL) del MIT e investigador del Laboratorio de IA Watson del MIT-IBM, analiza cómo la inteligencia artificial puede proporcionar soluciones mejores y más eficientes desde el punto de vista computacional para una optimización combinatoria. problema como este.

P: ¿Cuál es el problema de las rutas de vehículos y cómo lo abordan los métodos tradicionales de investigación de operaciones (OR)?

A: Casi todas las empresas de logística y entrega, como USPS, Amazon, UPS, FedEx y DHL, enfrentan el problema de las rutas de vehículos todos los días. Simplemente, se trata de encontrar una ruta eficiente que conecte a un conjunto de clientes a los que es necesario entregarles algo o recogerles algo. Él decide qué clientes debe visitar cada uno de esos vehículos (que ves en la carretera) en un día determinado y en qué secuencia. Por lo general, el objetivo es encontrar rutas que conduzcan a la ruta más corta, rápida o barata. Pero a menudo también están impulsados ​​por limitaciones específicas de un cliente. Por ejemplo, si tiene un cliente que tiene un tiempo de entrega específico, o un cliente en el piso 15 de un edificio de gran altura en lugar de la planta baja. Esto hace que sea más difícil integrar a estos clientes en una ruta de entrega eficiente.

Para resolver el problema de las rutas de vehículos, obviamente no podemos hacer nuestro modelado sin información adecuada sobre la demanda e, idealmente, las características relacionadas con el cliente. Por ejemplo, queremos saber el tamaño o el peso de los paquetes pedidos por un cliente en particular, o cuántas unidades de un determinado producto deben enviarse a una ubicación determinada. Todo esto determina el tiempo que necesitas para cumplir ese descanso en particular. Para problemas realistas, también es necesario saber dónde el conductor puede aparcar el vehículo de forma segura. Tradicionalmente, un planificador de rutas tenía que realizar buenas estimaciones para estos parámetros, por lo que a menudo se encuentran modelos y herramientas de planificación que hacen suposiciones generales porque no había datos disponibles sobre paradas específicas.

El aprendizaje automático puede ser muy interesante para esto porque hoy en día la mayoría de los conductores tienen teléfonos inteligentes o rastreadores GPS, por lo que hay mucha información sobre cuánto tiempo se tarda en entregar un paquete. Ahora puede, a escala, de una manera algo automatizada, extraer esa información y calibrar cada ruptura para modelarla de manera realista.

Usar un enfoque OR tradicional significa escribir un modelo de optimización, donde se comienza definiendo la función objetivo. En la mayoría de los casos se trata de algún tipo de función de costos. Luego hay muchas otras ecuaciones que definen el funcionamiento interno de un problema de enrutamiento. Por ejemplo, desea decirle al modelo que, si el vehículo visita a un cliente, también debe dejarlo nuevamente. En términos académicos, esto suele denominarse conservación del flujo. Del mismo modo, debes asegurarte de que cada cliente visite exactamente una vez en una ruta determinada. Estas y muchas otras limitaciones del mundo real definen en conjunto lo que constituye una ruta viable. Puede parecernos obvio, pero es necesario codificarlo explícitamente.

Una vez formulado un problema de optimización, existen algoritmos que nos ayudan a encontrar la mejor solución posible; nos referimos a ellos como solucionadores. Con el tiempo, encuentran soluciones que cumplen con todas las limitaciones. Luego, intenta encontrar rutas cada vez mejores y, por lo tanto, cada vez más baratas hasta que usted diga: «Está bien, esto es suficiente para mí» o hasta que pueda demostrar matemáticamente que ha encontrado la mejor solución. El vehículo de reparto medio en una ciudad estadounidense realiza unas 120 paradas. Puede llevar un tiempo resolver esto explícitamente, por lo que normalmente no es lo que hacen las empresas, porque es demasiado costoso desde el punto de vista computacional. Por lo tanto, utilizan las llamadas heurísticas, que son algoritmos que son muy eficientes para encontrar soluciones razonablemente buenas pero que normalmente no pueden cuantificar qué tan lejos están estas soluciones de las mejores teóricamente.

P: Actualmente aplicando el aprendizaje automático al problema de rutas de vehículos. ¿Cómo lo está utilizando para aprovechar y posiblemente superar los métodos tradicionales de quirófano?

A: Esto es en lo que estamos trabajando actualmente con gente del MIT-IBM Watson AI Lab. Aquí, la idea general es entrenar un modelo en un gran conjunto de soluciones de enrutamiento existentes que haya observado en las operaciones del mundo real de una empresa o que haya generado utilizando una de estas heurísticas eficientes. En la mayoría de los modelos de aprendizaje automático, ya no tienes una función objetivo explícita. En cambio, desea que el modelo comprenda qué tipo de problema está analizando realmente y cómo es una buena solución al problema. Por ejemplo, de manera similar a entrenar un modelo de lenguaje grande con palabras en un idioma determinado, es necesario entrenar un modelo de aprendizaje de ruta sobre el concepto de las distintas paradas de entrega y sus características de demanda. Al igual que comprender la gramática inherente del lenguaje natural, su modelo necesita comprender cómo combinar estas pausas en la entrega de manera que resulte en una buena solución (en nuestro caso, una solución barata o rápida). Si luego le lanza un conjunto completamente nuevo de solicitudes de clientes, aún podrá conectar los puntos literalmente de la misma manera que lo haría si estuviera tratando de encontrar una buena ruta para conectar a estos clientes.

Para ello, utilizamos arquitecturas modelo que la mayoría de la gente conoce del espacio de procesamiento del lenguaje. Parece un poco contradictorio porque ¿qué tiene que ver el procesamiento del lenguaje con el enrutamiento? Pero, de hecho, las propiedades de estos modelos, especialmente los modelos de transformadores, son buenas para encontrar estructura en el lenguaje: combinan palabras para formar oraciones. Por ejemplo, en un idioma tienes un vocabulario determinado y esto es fijo. Es un conjunto discreto de posibles palabras que puedes usar, y el desafío es combinarlas de manera significativa. En el recorrido es similar. En Cambridge hay como 40.000 direcciones que puedes visitar. Por lo general, lo que es necesario visitar es un subconjunto de estas direcciones, y el desafío es: ¿Cómo combinamos este subconjunto (estas «palabras») en una secuencia que tenga sentido?

Ésa es la novedad de nuestro enfoque: aprovechamos esa estructura que ha demostrado ser extremadamente efectiva en el espacio del lenguaje y la llevamos a la optimización combinatoria. Para nosotros, el enrutamiento es simplemente un gran banco de pruebas porque es el problema más fundamental en la industria de la logística.

Por supuesto, ya existen muy buenos algoritmos de enrutamiento que surgen de décadas de investigación de operaciones. Lo que intentamos hacer en este proyecto es mostrar que con un enfoque metodológico completamente diferente, basado exclusivamente en el aprendizaje automático, podemos predecir rutas que son tan buenas o mejores que las rutas que obtienes. ejecutar heurísticas avanzadas de optimización de enrutamiento.

P: ¿Qué ventajas tiene un método como el suyo respecto a las técnicas de quirófano de última generación?

A: Actualmente, los mejores métodos todavía tienen mucha hambre en términos de recursos computacionales necesarios para entrenar estos modelos, pero puedes adelantar parte de este esfuerzo. Entonces, el modelo entrenado es relativamente eficiente a la hora de producir una nueva solución cuando sea necesaria.

Otro aspecto a considerar es que el entorno operativo de una ruta, especialmente en las ciudades, cambia constantemente. La infraestructura vial disponible, las reglas de tránsito y los límites de velocidad pueden cambiar, el estacionamiento ideal puede estar ocupado por otra cosa o una obra en construcción puede bloquear una carretera. Con un enfoque puramente basado en OR, usted puede realmente tener problemas porque básicamente tiene que resolver todo el problema instantáneamente una vez que haya nueva información disponible sobre el problema. Dado que el entorno operativo cambia dinámicamente, tendrá que hacer esto una y otra vez. Mientras que si tiene un modelo bien entrenado que ha visto problemas similares antes, potencialmente puede sugerir la siguiente mejor ruta a seguir, casi al instante. Es más bien una herramienta para ayudar a las empresas a adaptarse a cambios cada vez más impredecibles en el entorno.

Además, los algoritmos de optimización suelen diseñarse manualmente para resolver el problema específico de una empresa en particular. La calidad de las soluciones obtenidas a partir de algoritmos tan explícitos está limitada por el nivel de detalle y sofisticación que se incluyó en el diseño del algoritmo. Por otro lado, un modelo basado en el aprendizaje aprende continuamente una política de enrutamiento a partir de los datos. Una vez definida la estructura del modelo, un modelo de aprendizaje de rutas bien diseñado destila mejoras potenciales a su política de enrutamiento a partir de la gran cantidad de rutas en las que se está entrenando. En pocas palabras, una herramienta de enrutamiento basada en el aprendizaje continuará encontrando mejoras en sus rutas sin tener que invertir en diseñar explícitamente estas mejoras en el algoritmo.

Finalmente, los métodos basados ​​en optimización generalmente se limitan a optimizar una función objetivo muy claramente definida, que a menudo busca minimizar costos o maximizar ganancias. En realidad, los objetivos a los que se enfrentan las empresas y los conductores son mucho más complejos y, a menudo, también algo contradictorios. Por ejemplo, una empresa quiere encontrar rutas eficientes, pero también quiere tener una huella de emisiones baja. El conductor también debe estar seguro y tener una manera conveniente de atender a estos clientes. Aparte de todo esto, las empresas también se preocupan por la coherencia. Un modelo de aprendizaje de ruta bien diseñado puede eventualmente capturar estos objetivos de alta dimensión por sí solo, y esto es algo que nunca podría lograr de la misma manera con un enfoque de optimización tradicional.

Así pues, este es el tipo de aplicación del aprendizaje automático que realmente puede tener un impacto tangible en el mundo real de la industria, la sociedad y el medio ambiente. La industria de la logística tiene problemas mucho más complejos que esto. Por ejemplo, si desea optimizar toda una cadena de suministro, digamos, el flujo de un producto desde el fabricante en China a través de la red de diferentes puertos en todo el mundo, a través de la red de distribución de un gran minorista en América del Norte hasta su almacén. dónde realmente lo compras: hay tantas decisiones involucradas en esto, lo que obviamente hace que sea una tarea mucho más difícil que optimizar la ruta de un solo vehículo. Nuestra esperanza es que con este trabajo inicial podamos sentar las bases para la investigación y también los esfuerzos de desarrollo del sector privado para crear herramientas que eventualmente permitan una mejor optimización de la cadena de suministro de extremo a extremo hasta el final.