Problema del agente viajero en logística: calcular lo imposible

Es bien sabido que, gracias al desarrollo de las tecnologías de la información (TI), las empresas obtienen cada vez mejores resultados de ventas, por no hablar de que pueden funcionar gracias a soluciones informáticas. Además, las personas pueden gestionar cada vez más asuntos o trabajar a través de Internet. Sin embargo, no todo el mundo sabe que incluso la informática tiene sus límites y no puede dar una respuesta exacta a todo, incluido el chatGPT :).

Dentro del campo de la informática, existen desde hace años cuestiones y problemas para los que aún no se han propuesto soluciones eficientes y fundamentales. Uno de ellos es el problema de optimización denominado problema del agente viajero, estrechamente relacionado con el sector de la TSL (Logística de Transporte y Expedición). Siga leyendo para saber más sobre él. Quizás sea usted el afortunado que resuelva este problema.

¿Cómo surgió el «problema del agente viajero»?

Es difícil precisar la persona que anunció por primera vez la dificultad de indicar un conjunto de instrucciones para resolver el problema del agente viajero (TSP – Travelling Salesman Problem). Las primeras menciones al mismo se remontan a la década de 1830 y los primeros intentos de resolverlo se realizaron unos 100 años más tarde al tratar de encontrar la ruta óptima para un autobús escolar. Dejaremos el análisis del problema basado en complejas leyes y expresiones matemáticas a los científicos. Por eso me centraré en su esencia presentándolo de forma fácilmente comprensible.

¿Cuál es el problema del TSP?

Supongamos que hay un viajante que empieza y termina su trabajo en Boston. Un día tiene que entregar paquetes en direcciones de Nueva York, Denver, Los Ángeles, Austin, Portland y Chicago. El problema del agente viajero consiste en encontrar la ruta más corta que permita al viajante visitar todas estas ciudades. No tiene por qué tratarse sólo de la longitud de la ruta, ya que también puede centrarse en encontrar el camino más barato o más rápido. En nuestro ejemplo, el número de rutas posibles es de 5040..

¿Cómo afrontan las empresas el problema del TSP?

Si buscamos la ruta más corta para varias ciudades, encontrar la solución óptima puede llevar segundos o unos minutos en un ordenador normal. Sin embargo, cuando hablamos, por ejemplo, de 52 ciudades, se utilizan diversos algoritmos y la informática paralela y distribuida para encontrar soluciones aproximadas – suficientes para la logística-, porque comprobar todas las rutas posibles es prácticamente imposible. Probablemente no le sorprenderá que la inteligencia artificial (IA) desempeñe un papel en esto.

Aplicaciones del problema del agente viajero

El problema del agente viajero tiene muchas aplicaciones prácticas. La principal, y el motivo de escribir este artículo, es la optimización de rutas para flotas de vehículos, barcos o aviones, minimizando los costes y el tiempo de entrega. Otra aplicación es la planificación de rutas para robots en almacenes o centros logísticos. La TSP también se utiliza en el diseño de redes de telecomunicaciones para garantizar una calidad óptima de la señal y minimizar los costes.

Le ayudaremos a optimizar su carga

Aunque no podamos resolver el problema del agente viajero y encontrar la ruta óptima para cualquier número de ciudades, disponemos de un programa para la planificación de la carga de mercancías llamado EasyCargo. Además de crear un plan óptimo para la disposición de las mercancías (se pueden agrupar por lugares de descarga) y la distribución de la carga, permite generar informes en formato Excel o PDF. Incluso, dispone de un enlace público para colaborar con colegas en el trabajo de carga.

Adicionalmente, puede integrar EasyCargo con el software de su empresa u otros programas como el sistema de telemetría FleetUp utilizando nuestra API. Puede obtener más información detallada en este enlace.

Fuente: https://developer-blogs.nvidia.com/wp-content/uploads/2023/01/cuopt-featured.jpg

En realidad, se podría decir que, para el sector de TSL, el problema del agente viajero está dejando poco a poco de ser una preocupación gracias al desarrollo de la inteligencia artificial y el Big Data. Todo tipo de software de optimización de rutas de reparto ofrece una ruta que no se desvía significativamente de la más favorable y la ajusta dinámicamente en tiempo real en función de las condiciones de las carreteras.

¡Buena suerte con la propuesta de un algoritmo capaz de encontrar la ruta óptima para cualquier número de ciudades en tiempo polinómico!