En todo el país, cientos de miles de conductores entregan paquetes y encomiendas a clientes y empresas cada día, 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 larga data de la investigación de operaciones, donde los investigadores han estado trabajando para optimizar el último tramo 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 volvieron más exagerado y evidente 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 podría proporcionar soluciones mejores y más eficientes desde el punto de vista computacional para una optimización combinatoria. problema como éste.
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. En pocas palabras, se trata de encontrar una ruta eficiente que conecte a un conjunto de clientes a los que es necesario entregarles algo o recogerles algo. Se trata de decidir qué clientes debe visitar cada uno de esos vehículos (que se ven 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 muy a menudo también están impulsados por limitaciones específicas de un cliente. Por ejemplo, si tiene un cliente que tiene un plazo de entrega especificado, o un cliente en el piso 15 de un edificio alto en lugar de en 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 la información adecuada sobre la demanda e, 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 determinado, o cuántas unidades de un determinado producto deben enviarse a una ubicación determinada. Todo esto determina el tiempo que necesitarías para atender esa parada en particular. Para problemas realistas, también conviene 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 muy 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 forma algo automatizada, extraer esa información y calibrar cada parada para modelarla de forma realista.
Usar un enfoque OR tradicional significa redactar 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, debe decirle al modelo que, si el vehículo visita a un cliente, también debe abandonarlo nuevamente. En términos académicos, esto suele denominarse conservación del flujo. Del mismo modo, debe asegurarse de que cada cliente sea visitado 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, es decir, cada vez más baratas, hasta que usted diga: “Está bien, esto es suficiente para mí” o hasta que pueda demostrar matemáticamente que encontró la solución óptima. El vehículo de reparto promedio en una ciudad estadounidense hace alrededor de 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 del óptimo teórico.
P: Actualmente está aplicando el aprendizaje automático al problema de generación de rutas para vehículos. ¿Cómo lo está empleando para aprovechar y posiblemente superar los métodos tradicionales de quirófano?
A: En eso 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 observó en las operaciones del mundo real de una empresa o que generó 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 lugar de ello, es necesario hacer que el modelo comprenda qué tipo de problema está analizando realmente y cuál 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 conectar estas paradas de 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 demandas de los clientes, todavía podrá conectar los puntos literalmente de una manera que también 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 en realidad, las propiedades de estos modelos, especialmente los modelos transformadores, son buenas para encontrar estructura en el lenguaje: conectar palabras de manera que formen oraciones. Por ejemplo, en un idioma, tienes cierto vocabulario y eso es fijo. Es un conjunto discreto de posibles palabras que puedes usar y el desafío es combinarlas de manera significativa. En el enrutamiento, 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?
Esa es la novedad de nuestro enfoque: aprovechar esa estructura que ha demostrado ser extremadamente efectiva en el espacio del lenguaje y llevarla a la optimización combinatoria. El enrutamiento es simplemente un gran banco de pruebas 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 surgieron 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, puramente basado en el aprendizaje automático, podemos predecir rutas que son tan buenas o mejores que las rutas que se obtendrían a partir de ejecutar una 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 de quirófano de última generación?
A: En este momento, los mejores métodos todavía tienen mucha hambre en términos de recursos computacionales necesarios para entrenar estos modelos, pero puedes anticipar parte de este esfuerzo. Entonces, el modelo entrenado es relativamente eficiente a la hora de producir una nueva solución a medida que se requiere.
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 verse alterados, 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, es posible que realmente tenga problemas porque básicamente tendría 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, habría que hacerlo una y otra vez. Mientras que si tienes un modelo bien entrenado que ha visto problemas similares antes, podría sugerir la siguiente mejor ruta a seguir, casi instantáneamente. Es más bien una herramienta que ayudaría 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 determinada. 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 que haya definido la estructura del modelo, un modelo de aprendizaje de rutas bien diseñado extraerá 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 que usted tenga que invertir en diseñar explícitamente estas mejoras en el algoritmo.
Por último, los métodos basados en optimización generalmente se limitan a optimizar para 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 que eso 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 quiere estar seguro y tener una forma cómoda de atender a estos clientes. Además de todo eso, las empresas también se preocupan por la coherencia. Un modelo de aprendizaje en ruta bien diseñado puede eventualmente capturar estos objetivos de alta dimensión por sí solo, y eso es algo que nunca podría lograr de la misma manera con un enfoque de optimización tradicional.
Por lo tanto, 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 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 tienda. dónde realmente lo compras: hay tantas decisiones involucradas en eso, 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.
