3 preguntas: mejorar la logística de última milla con aprendizaje automático | Noticias del MIT

En todo el país, cientos de miles de conductores entregan paquetes y encomiendas a clientes y empresas todos los días, y para muchos el tiempo promedio de clic hasta la puerta es de solo unos pocos días. Coordinar un esfuerzo de esta magnitud en la cadena de suministro de manera predecible y oportuna es un problema de larga data en la investigación de operaciones, y los investigadores trabajan para optimizar el tramo final de los viajes de entrega. Esto se debe a que la fase final 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 relacionados con el clima, tráfico, falta de estacionamiento, preferencias de entrega de los clientes o camiones parcialmente llenos. - ineficiencias, que empeoraron aún más y se volvieron exageradas y obvias durante la pandemia.

Con tecnología más nueva y datos más personalizados y matizados, los investigadores pueden desarrollar modelos con mejores opciones de enrutamiento, pero al mismo tiempo deben equilibrar los costos computacionales de ejecutarlos. Matthias Winkenbach, científico investigador senior 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 podría 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, se enfrentan a diario al problema de la planificación de rutas de vehículos. En pocas palabras, se trata de encontrar una ruta eficiente que conecte a un grupo de clientes que necesitan entrega o recogida. Se trata de decidir a qué clientes debe visitar cada uno de estos vehículos, los que ves por la carretera, en un día determinado y en qué orden. Normalmente el objetivo es encontrar rutas que conduzcan al camino más corto, más rápido o más barato. Pero muy a menudo también pueden atribuirse a limitaciones específicas del cliente. Por ejemplo, si tiene un cliente que tiene un horario de entrega especificado, o un cliente en el piso 15 de un edificio alto en comparación con la planta baja. Esto dificulta la integración de estos clientes en una ruta de entrega eficiente.

Para resolver el problema del guiado de vehículos, obviamente no podemos realizar nuestro modelado sin la información adecuada sobre la demanda y, idealmente, las características relacionadas con el cliente. Por ejemplo, necesitamos saber el tamaño o el peso de los paquetes pedidos por un cliente en particular, o cuántas unidades de un producto en particular deben enviarse a una ubicación en particular. Todo esto determina el tiempo que le llevaría atender esa parada en particular. Si hay problemas reales, también querrás saber dónde el conductor puede estacionar el vehículo de forma segura. Tradicionalmente, un planificador de rutas tenía que producir buenas estimaciones para estos parámetros. Por lo tanto, 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, ya que la mayoría de los conductores hoy en día tienen teléfonos inteligentes o rastreadores GPS y, por lo tanto, hay mucha información sobre cuánto tiempo tarda en entregarse un paquete. Ahora puede extraer esta información a escala y de forma automatizada y calibrar cada parada individual para modelarla de forma realista.

Si utiliza un enfoque OR tradicional, escribe un modelo de optimización donde primero define la función objetivo. En la mayoría de los casos se trata de algún tipo de función de costos. Luego hay una serie de otras ecuaciones que definen el funcionamiento interno de un problema de enrutamiento. Por ejemplo, es necesario decirle al modelo que cuando el vehículo visita a un cliente, también debe irse. En la jerga académica esto suele denominarse conservación del flujo. Asimismo, debes asegurarte de que cada cliente sea visitado exactamente una vez en una ruta específica. Estas y muchas otras limitaciones del mundo real se combinan para definir 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; los llamamos solucionadores. Con el tiempo, encuentran soluciones que superan todas las limitaciones. Luego intenta encontrar rutas cada vez mejores, es decir, más baratas, hasta que usted diga: "Está bien, eso es suficiente para mí" o hasta que pueda demostrar matemáticamente que ha encontrado la solución óptima. El vehículo de reparto promedio en una ciudad estadounidense hace alrededor de 120 paradas. Esto puede tardar un tiempo en resolverse explícitamente, por lo que esto no es lo que suelen hacer las empresas porque es demasiado intensivo desde el punto de vista computacional. Por lo tanto, utilizan las llamadas heurísticas, es decir, algoritmos que son muy eficientes para encontrar soluciones razonablemente buenas, pero que normalmente no pueden cuantificar qué tan lejos están estas soluciones del óptimo teórico.

P: Actualmente están aplicando el aprendizaje automático al problema de las rutas de vehículos. ¿Cómo se utiliza para aprovechar y potencialmente superar los métodos quirúrgicos tradicionales?

A: Actualmente estamos trabajando en esto con gente del MIT-IBM Watson AI Lab. La idea general aquí es entrenar un modelo en un gran conjunto de soluciones de enrutamiento existentes que haya observado en las operaciones reales de una empresa o generado utilizando una de estas heurísticas eficientes. En la mayoría de los modelos de aprendizaje automático, ya no existe una función objetivo explícita. En lugar de ello, es necesario dejarle claro al modelo qué tipo de problema es realmente y cómo sería una buena solución al problema. Por ejemplo, de manera similar a entrenar un modelo de lenguaje grande con palabras en un idioma específico, es necesario entrenar un modelo de aprendizaje de ruta sobre el concepto de diferentes paradas de entrega y sus características de demanda. Al igual que comprender la gramática inherente del lenguaje natural, su modelo debe comprender cómo conectar estas paradas de entrega de una manera que cree una buena solución (en nuestro caso, una solución rápida o de bajo costo). Luego, cuando lo enfrente con requisitos de clientes completamente nuevos, aún podrá literalmente conectar los puntos de la misma manera que lo haría si estuviera tratando de encontrar una buena manera de conectar a estos clientes.

Para ello utilizamos arquitecturas modelo con las que la mayoría de la gente está familiarizada en el campo del procesamiento del lenguaje. Parece un poco contradictorio, porque ¿qué tiene que ver el procesamiento del lenguaje con el enrutamiento? Pero en realidad las propiedades de estos modelos, especialmente los modelos transformadores, son buenas para encontrar estructura en el lenguaje, conectando palabras de tal manera que formen oraciones. Por ejemplo, en un idioma hay un vocabulario determinado y ese es fijo. Es un conjunto discreto de posibles palabras que puedes usar y el desafío es combinarlas de manera significativa. Es similar con el enrutamiento. Hay alrededor de 40.000 direcciones en Cambridge 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 un orden significativo?

Ésta es, por así decirlo, la novedad de nuestro enfoque: utilizamos la estructura que ha demostrado ser muy eficaz en el ámbito lingüístico y la incorporamos a la optimización combinatoria. Las rutas son simplemente una gran prueba para nosotros porque es el problema más fundamental en la industria de la logística.

Por supuesto, ya existen muy buenos algoritmos de enrutamiento que han surgido de décadas de investigación de operaciones. Lo que intentamos hacer en este proyecto es mostrar que utilizando un enfoque metodológico completamente diferente, puramente basado en el aprendizaje automático, podemos predecir rutas que son tan buenas o mejores que las rutas que se obtendrían al ejecutar un estado de Heurística de optimización de rutas de última generación.

P: ¿Qué ventajas tiene un método como el suyo frente a otras técnicas quirúrgicas modernas?

A: Por el momento, los mejores métodos todavía tienen mucha hambre en términos de los recursos computacionales necesarios para entrenar estos modelos, pero usted puede realizar parte de ese esfuerzo. Entonces, el modelo entrenado es relativamente eficiente a la hora de crear una nueva solución cuando es necesaria.

Otro aspecto a considerar es que el entorno operativo de una ruta, especialmente en las ciudades, cambia constantemente. La infraestructura vial existente o las normas de tránsito y los límites de velocidad podrían cambiar, el espacio de estacionamiento ideal podría ser ocupado por otra cosa o una obra en construcción podría bloquear una carretera. Con un enfoque puramente basado en OR, usted podría meterse en problemas porque esencialmente tendría que resolver todo el problema inmediatamente tan pronto como estuviera disponible nueva información sobre el problema. Dado que el entorno operativo cambia dinámicamente, tendría que hacer esto una y otra vez. Por otro lado, si tiene un modelo bien entrenado que ha encontrado problemas similares antes, podría sugerir el siguiente mejor camino casi al instante. Es más bien una herramienta diseñada 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 crearse 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 complejidad 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 que defina la estructura del modelo, un modelo de aprendizaje de rutas bien diseñado filtrará posibles mejoras a su política de enrutamiento del gran conjunto de rutas en las que está entrenado. En pocas palabras, una herramienta de enrutamiento basada en el aprendizaje seguirá encontrando mejoras en sus rutas sin que usted tenga que invertir en diseñar explícitamente esas mejoras en el algoritmo.

Finalmente, los métodos basados ​​en optimización generalmente se limitan a la optimización de una función objetivo muy claramente definida, a menudo dirigida a minimizar costos o maximizar ganancias. De hecho, los objetivos a los que se enfrentan las empresas y los conductores son mucho más complejos y, a menudo, algo contradictorios. Por ejemplo, una empresa quiere encontrar rutas eficientes y al mismo tiempo tener una huella de emisiones baja. El conductor también quiere estar seguro y tener una forma cómoda de atender a estos clientes. Además, las empresas también valoran la coherencia. Un modelo de aprendizaje de ruta bien diseñado puede, en última instancia, capturar estos objetivos de alta dimensión por sí mismo, y eso es algo que nunca podría lograr de la misma manera con un enfoque de optimización tradicional.

Así que este es el tipo de aplicación de aprendizaje automático que realmente puede tener un impacto tangible en el mundo real en la industria, la sociedad y el medio ambiente. La industria de la logística tiene problemas que son mucho más complejos. 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 varios puertos en todo el mundo, a través de la red de distribución de un importante minorista en América del Norte, hasta su tienda donde realmente lo compras - son tantas decisiones involucradas, lo que por supuesto hace que sea una tarea mucho más difícil que optimizar la ruta de un solo vehículo. Esperamos que con este trabajo inicial podamos sentar las bases para los esfuerzos de investigación y desarrollo del sector privado para desarrollar herramientas que, en última instancia, permitan una mejor optimización de la cadena de suministro de extremo a extremo.