Con el aumento del eCommerce y las necesidades de transporte y logística para el Retail se hace cada vez más necesario optimizar las rutas de distribución y reparto, especialmente en lo que se conoce como última milla. Un modelo de aprendizaje automático que proporciona información sobre cuáles han sido las mejores rutas anteriores y una herramienta ‘metaheurística’ que utiliza esta información para ensamblar la nueva ruta, dan como resultado un algoritmo capaz de resolver lo que se conoce como “problema del vendedor ambulante”.
Enfoque mejorado del ‘Problema del vendedor ambulante’ o ‘viajante de comercio‘
Una pregunta teórica notoria que ha desconcertado a los investigadores durante 90 años, el problema del viajante de comercio (Travelling Salesperson Problem) también tiene una relevancia real para la industria actual. Esencialmente es una pregunta sobre cómo combinar mejor un conjunto de tareas para que se puedan realizar de la manera más rápida y eficiente, y encontrar buenas soluciones al problema puede ayudar mucho a mejorar sectores como el transporte y la logística.
Investigadores de la Universidad de Cambridge han desarrollado un enfoque híbrido basado en datos para el problema que no solo produce soluciones de alta calidad, sino también a un ritmo más rápido que otros enfoques de vanguardia. Sus resultados se presentaron en la Conferencia Internacional sobre Representaciones de Aprendizaje .
“La importancia del sistema logístico global se nos hizo evidente durante la pandemia”, dijo la Dra. Amanda Prorok del Departamento de Ciencias de la Computación y Tecnología de Cambridge, quien dirigió la investigación.
“Dependemos en gran medida de este tipo de infraestructura para ser más eficientes, y nuestra solución podría ayudar con eso, ya que se enfoca tanto en la logística del almacén, como el enrutamiento de los robots alrededor de un almacén para recoger los productos para su entrega, como en el exterior. como el enrutamiento de bienes a personas”.
El problema del vendedor ambulante involucra a un repartidor ficticio que debe llamar a un número determinado de ciudades (por ejemplo, 20, 50 o 100) que están conectadas por carreteras en un solo viaje. El desafío es encontrar la ruta más corta posible que llame a cada destino una vez y encontrarla rápidamente.
“Hay dos componentes clave en el problema. Queremos ordenar las paradas y también queremos saber el costo, en tiempo o distancia, de ir de una parada a otra en ese orden”, dijo Prorok.
Hace veinte años, la ruta desde el almacén hasta los destinos podría haberse fijado de antemano
Pero con la disponibilidad actual de información de tráfico en tiempo real y la capacidad de enviar mensajes al conductor para agregar o eliminar ubicaciones de entrega sobre la marcha, la ruta ahora puede cambiar durante el viaje. Pero minimizar su longitud o duración sigue siendo clave.
A menudo, se atribuye un costo a la espera de una solución óptima o plazos estrictos en los que se deben tomar decisiones. Por ejemplo, el conductor no puede esperar a que se calcule una nueva solución: puede perder sus entregas o las condiciones del tráfico pueden cambiar nuevamente.
Y es por eso que existe la necesidad de algoritmos de optimización combinatoria generales y en cualquier momento que produzcan soluciones de alta calidad con un tiempo de cálculo restringido.
El enfoque híbrido desarrollado por Cambridge hace esto al combinar un modelo de aprendizaje automático que proporciona información sobre cuáles han sido las mejores rutas anteriores y una herramienta ‘metaheurística’ que utiliza esta información para ensamblar la nueva ruta. “Queremos encontrar buenas soluciones más rápido”, dijo Ben Hudson, el primer autor del artículo.
“Si soy conductor de una empresa de mensajería, tengo que decidir cuál será mi próximo destino mientras conduzco. No puedo permitirme esperar una solución mejor. Es por eso que en nuestra investigación nos enfocamos en la compensación entre el tiempo computacional necesario y la calidad de la solución que obtuvimos”.
Para hacer esto, Hudson ideó un algoritmo de búsqueda local guiada que podía diferenciar las rutas de una ciudad a otra que serían costosas, en tiempo o distancia, de las rutas que serían menos costosas de incluir en el viaje. Esto permitió a los investigadores identificar rápidamente soluciones de alta calidad, en lugar de soluciones óptimas.
Hicieron esto utilizando una medida de lo que ellos llaman el ‘arrepentimiento global’ (el costo de hacer cumplir una decisión en relación con el costo de una solución óptima) de cada ruta de ciudad a ciudad en el algoritmo de búsqueda local guiada. Utilizaron el aprendizaje automático para llegar a una aproximación de este «arrepentimiento».
“Ya conocemos la solución correcta a un conjunto de estos problemas”, dijo Hudson. “Así que usamos algunas técnicas de aprendizaje automático para probar y aprender de esas soluciones. En base a eso, tratamos de aprender para un nuevo problema, para un nuevo conjunto de ciudades en diferentes ubicaciones, qué caminos entre las ciudades son prometedores.
“Cuando tenemos esta información, se alimenta a la siguiente parte del algoritmo, la parte que realmente dibuja las rutas. Utiliza esa información adicional sobre cuáles pueden ser los buenos caminos para crear una buena solución mucho más rápido de lo que podría haberlo hecho de otra manera”.
Los resultados que obtuvieron fueron impresionantes. Sus experimentos demostraron que el enfoque híbrido basado en datos converge en soluciones óptimas a un ritmo más rápido que tres enfoques recientes basados en el aprendizaje para el problema del viajante de comercio.
En particular, al tratar de resolver el problema cuando tenía una ruta de 100 ciudades, el método de Cambridge redujo la brecha de optimización media de 1,534 % a 0,705 %, una mejora doble.
Al generalizar desde la ruta del problema de 20 ciudades a la ruta del problema de 100 ciudades, el método redujo la brecha de optimización del 18,845 % al 2,622 %, una mejora de siete veces.
“Muchas empresas de logística utilizan métodos de enrutamiento en la vida real”, dijo Hudson. “Nuestro objetivo con esta investigación es mejorar dichos métodos para que produzcan mejores soluciones, soluciones que resulten en distancias más cortas recorridas y, por lo tanto, menos emisiones de carbono y un impacto reducido en el medio ambiente”.
Amanda Prorok es miembro del Pembroke College, Cambridge.
Referencia:
Benjamin Hudson et al. Graph Neural Network Guided Local Search for the Traveling Salesperson Problem ‘(Gráfica de búsqueda local guiada por red neuronal para el problema del vendedor ambulante) Documento presentado en la Conferencia Internacional sobre Representaciones de Aprendizaje: https://iclr.cc/virtual/2022/calendar .
Fuente: University of Cambridge. El texto de este trabajo tiene una licencia internacional Creative Commons Attribution 4.0
Otras noticias sobre Logística y Retail que te pueden interesar:
- Etiquetas 3D escaneables invisibles para Retail
- Cómo está impactando 5G en los distintos sectores industriales
- Los drones para reparto a domicilio son aprobados por los consumidores
- Perspectivas del Retail, Distribución, Logística y Consumer Goods
- Los retos de la distribución analizados por sus protagonistas
- Los retos del transporte y la logística para el comercio online analizados por sus protagonistas
- Customer Journey en Retail y tecnología ante el COVID-19
- Transformación del Retail y tecnología
- Laboratorio de Inteligencia Artificial para el Retail
- Smart Factories o Fábricas Hiperconectadas para aumentar la productividad
