Problema del agente viajero

Alejandro Fuentes Penna^[a]

Resumen

El presente artículo tiene como objetivo presentar un ensayo referente al problema del agente viajero – Travel Salesman Problem (TSP por sus siglas en inglés) cuya representación ha resuelto múltiples problemas que pueden ser modelados con base en las características del algoritmo base de TSP o de sus múltiples variables.

Se presenta una introducción donde se describe el origen de TSP; en la sección de desarrollo se muestra el algoritmo base y una descripción de TSP con base en las características que han propuesto diferentes autores, y la aplicación de TSP como simulación a problemas reales con. Por último, en la conclusión se aborda el tema de TSP como un paradigma que se puede emplear en situaciones donde se involucran puntos de control (nodos) y costo entre los nodos.

Palabras clave: Problema del Agente Viajero, Problema de Optimización Combinatoria, Optimización basada en Colonia de Hormigas, Inteligencia de Enjambre, Inteligencia Artificial

Abstract

The main target is to introduce an essay of the traveling salesman problem (TSP) whose structure has solved many problems that can be modeled based on base- algorithm or its multiple variables.

An introduction describes the origin of TSP, in the development section the basic algorithm and the TSP description are presented based on different viewpoints of some authors, and the TSP implementation on real problems based on simulation. Finally, in the conclusion the issue of TSP as a paradigm that can be used in situations which involve control points (nodes) and cost between nodes.

Keywords: Travel Salesman Problem (TSP), Combinatorial Optimization Problem (COP), Ant Colony Optimization (ACO), Swarm Intelligence, Artificial Intelligence.

Introducción

La primera solución reportada para resolver el problema del Agente Viajero fue en 1954, cuando George Dantzig, Ray Fulkerson, y Selmer Johnson  publicaron la descripción de un método de solución del PAV (Problema del Agente Viaje o sus siglas en inglés TSP – Travel Sailsman Problem) titulado “Solutions of a large scale traveling salesman problem“ (Soluciones de gran escala para el problema del agente viajero) para resolver una instancia de 49 ciudades donde un agente viajero desea visitar un conjunto de ciudades, asignándoles un costo por visitar ciudades contiguas (distancia de traslado entre dos ciudades). Para esta solución se propusieron 2 condiciones: regresar a      la misma ciudad de la cual partió y no repetir ciudades con el objetivo de encontrar una ruta o un camino con el menor costo posible.

Desarrollo

Descripción de TSP

Se tiene un número de nodos (ciudades, localidades, tiendas, empresas, etc.) que deben ser visitados por una entidad (persona, agente viajero, automotor, avión, autobús, etc.), sin visitar 2 veces el mismo nodo. Si tenemos 3 nodos (a, b y c) por visitar, entonces tendríamos una función de combinaciones sin repetición c(3,2), es decir, tendríamos 6 posibles soluciones: abc, acb, bac, bca, cab, cba, para el caso de 4 nodos tendríamos 12 combinaciones, para 10 nodos tendríamos 90  combinaciones, para 100 ciudades tendríamos 9,900 combinaciones y así sucesivamente. Como ejemplo en el problema del Ulises de Homero que intenta visitar las ciudades descritas en la Odisea exactamente una vez (16 ciudades) donde existen múltiples conexiones entre las diferentes ciudades, Grötschel y Padberg (1993) llegó a la conclusión de que existen 653,837’184,000 rutas distintas para la solución de este problema.

Algoritmo base

El Problema del Agente Viajero (TSP), es considerado como un conjunto de grafos cuyas aristas son los posibles caminos que puede seguir la entidad para visitar todos los nodos (Öncan et al., 2009), y cuyo algoritmo se puede representar de la siguiente manera:

Definir el número de nodos, su posición y el costo por cada arista (i, j) donde i = ciudad 1 y j = ciudad 2

Elegir el nodo inicial i

Hacer

Si el nodo más cercano no se ha visitado

Visitar nodo j

Actualizar lista de nodos visitados

Costo_total = costo_total + costoij

Nodo i = nodo j

Hasta haber visitado todos los nodos

Características de TSP

TSP se encuentra clasificado como Problema de optimización Combinatoria, es decir, es un problema donde intervienen cierto número de variables donde cada variable puede tener N diferentes valores y cuyo número de combinaciones es de carácter exponencial, lo que da lugar a múltiples soluciones óptimas (soluciones que se calculan en un tiempo finito) para una instancia.

TSP es un problema considerado difícil de resolver, denominándose en lenguaje computacional NP-Completo, es decir, es un problema para el que no podemos garantizar que se encontrará la mejor solución en un tiempo de cómputo razonable. Para dar solución se emplean diferentes métodos, entre los cuales, los principales se denominan heurísticas cuyo objetivo es generar soluciones de buena calidad en tiempos de cómputo mucho más pequeños (soluciones óptimas tiempo – respuesta).

Las variables que han sido empleadas por la mayoría de los investigadores que dan solución a TSP son:

• Tiempo de recorrido entre ciudades: horas, minutos, días, semanas, etc.
• Distancia de recorrido entre ciudades: metros, kilómetros, millas, milímetros, etc.
• Costo de traslado: dinero, desgaste de las piezas, gasto de energía, etc.

Las variables que se pueden adoptar dependen de cada problema, por ejemplo:

• Circuitos electrónicos: cantidad de soldadura utilizada, menor espacio entre los puntos de soldadura de los circuitos, evitar el cruce entre las líneas de soldadura, tiempo de fabricación, distribución de los circuitos, entre otras.
• Control de semáforos: Número de semáforos (nodos), tiempo de traslado entre semáforos, cantidad de autos que pasan por un punto, entre otras variables.
• Previsión del tránsito terrestre: puntos en una ciudad, cantidad de vehículos, tiempo de traslado, tipos de vehículos, horas pico, correlación entre variables, regresión lineal, etc.
• Entrega de productos: Peso de las entregas, número de entregas, nodos (domicilios) a visitar, recorridos, tiempos de traslado, tipo de vehículo, etc.
• Estaciones de trabajo: secuencia de actividades, lugar de las herramientas (nodos), Tipo de herramientas, tiempo de uso, etc.
• Edificación: puntos de edificación (construcciones), distancia entre las construcciones y los insumos, vehículos (grúas, camiones de volteo, etc.), cantidad de combustible que emplean, etc.
• Entre otras variables

Aplicación de TSP

TSP se puede emplear en cualquier situación que requiere seleccionar nodos en cierto orden que reduzca los costos:

• Reparto de productos. Mejorar una ruta de entrega para seguir la más corta.
• Transporte. Mejorar el recorrido de caminos buscando la menor longitud (figura 1).
• Robótica. Resolver problemas de fabricación para minimizar el número de desplazamientos al realizar una serie de perforaciones en un circuito impreso.
• Turismo y agencias de viajes. Aun cuando los agentes de viajes no tienen un conocimiento explícito del Problema del Agente Viajero, las compañías dedicadas a este giro utilizan un software que hace todo el trabajo. Estos paquetes son capaces de resolver instancias pequeñas del TSP.
• Horarios de transportes laborales y/o escolares. Estandarizar los horarios de los transportes es claramente una de sus aplicaciones, tanto que existen empresas que se especializan en ayudar a las escuelas a programarlos para optimizarlos en base a una solución del TSP.
• Inspecciones a sitios remotos. Ordenar los lugares que deberá visitar un inspector en el menor tiempo.
• Secuencias. Se refiere al orden en el cual n trabajos tienen que ser procesados de tal forma que se minimice el costo total de producción.

Figura 1. Mapa de la región de Tlahuelilpan, Hidalgo
Fuente: Google maps

Algoritmos propuestos para dar solución a TSP

El Problema del Agente Viajero puede resolverse de diferentes maneras:

• Enumeración de todas las soluciones factibles. Es decir, enlistar todas las posibles soluciones al problema, calcular sus costos asociados, e identificar, por comparación, cuál es la solución con el costo más conveniente.
• Métodos exactos. También llamados algoritmos óptimos, intentan descartar familias enteras de posibles soluciones, tratando así de acelerar la búsqueda y llegar a una óptima. Los que más se usan para resolver el TSP son Ramificación y Acotamiento, y Ramificación y Corte.
• Heurísticas. Son métodos obtienen buenas soluciones en tiempos de cómputo muy cortos, aunque sin garantizar la solución única.

En la actualidad investigadores han propuesto diferentes estrategias para dar solución a TSP, de las cuales se pueden mencionar algunas técnicas empleadas:

• Algoritmos genéticos: la solución consiste en encontrar un individuo cuya combinación de genes (cada gen es una variable), den solución al problema de visitar todas las ciudades una vez. Otra solución es que cada gen es una ciudad y cuyo orden dependerá del orden en que serán visitadas.
• Redes neuronales: Una red neuronal simula las conexiones entre los nodos (lugares por visitar), y cada recorrido por las diferentes neuronas genera al final un camino que involucra el tour por todas las ciudades visitadas una sola vez.
• Colonia de hormigas (ACO): las hormigas encuentran el camino más corto entre 2 puntos; para TSP, se considera el punto de inicio como el punto final, el mismo nodo; de esta manera, las hormigas deben recorrer todas las ciudades en un circuito, sin pasar 2 veces por la misma ciudad.
• Project  Scheduling Problem (PSP): Buscar la solución considerando principalmente el uso mínimo de recursos durante cada recorrido.
• Búsqueda Tabú: consiste en buscar el vecino próximo cuyos costos de traslado del nodo actual al siguiente, sea el de menor costo en cuanto al uso de recursos
• Combinación de propuestas: Las técnicas de Inteligencia Artificial se pueden combinar para crear meta heurísticas, conformando diferentes soluciones tales como: algoritmos genéticos con redes neuronales, PSP con ACO, PSP con redes neuronales, etc.
• Entre otras soluciones.

Simulación de TSP

En Fuentes-Penna and González-Ramírez (2013) se presenta una simulación del Problema del Agente Viajero (TSP por sus siglas en inglés), donde se tienen 100 ciudades que deberán ser visitadas en el menor tiempo y con el menor costo de traslado. Se asigna de manera aleatoria la distancia y el costo entre los nodos con un máximo de 10 nodos colindantes. El Algoritmo propuesto se denomina Scheduling Project Ant Colony Optimization (SPANCO) y se comparan los resultados con una solución aleatoria y con el algoritmo basado en Optimización de Colonia de Hormigas (ACO por sus siglas en inglés). En este artículo se muestra que el algoritmo SPANCO reduce el costo total y la distancia total del recorrido en un rango del 3% al 8%. La simulación se relación con el software AIMMS para modelado matemático y de optimización (AIMMS, 2013). Las áreas de aplicación de AIMMS son:

• Planificación estratégica de la producción
• Optimización de redes de distribución
• Programación y mezcla de crudo
• Modelado y optimización de procesos
• Planificación de la utilización de plantas de generación eléctrica
• Gestión estratégica de bosques
• Optimización de aprovisionamientos
• Gestión de riesgo financiero
• Optimización en el diseño de productos
• Planificación de la cartera de I+D y asignación de recursos

Figura 2. Simulación de TSP
Fuente: Fuentes-Penna y González-Ramírez (2013)

Conclusiones

El problema del Agente Viajero (TSP) es un problema cuya solución ha sido estudiada desde los inicios de la Inteligencia Artificial considerando que su aplicación puede ser en cualquier área de estudio cuyos problemas reflejen una situación donde se tienen diferentes puntos a visitar con un costo considerado en el enlace entre dichos puntos (costo: recursos empleados como distancia, tiempo, monto económico, etc.). Cada autor ha propuesto soluciones para ciertas instancias de TSP, cada uno con una perspectiva diferente empleando técnicas que no son repetibles pero que, en determinado momento, se pueden emplear para dar lugar a nuevas soluciones; de las técnicas empleadas la más común es el uso de redes neuronales dada su similitud, donde cada neurona es un nodo a visitar y las relaciones entre neuronas es el vector que representa el costo.

Referencias bibliográficas

Applegate, D., Bixby,R., Chvatal V., Cook,W. “On the solution of the Traveling Salesman Problem”. DocumentaMathematica-Extra Volume ICM III. 1998. 645-656.

Brest,J., Zerovnik,J. “A heuristic for the Asymmetric Traveling Salesman Problem”. The 6th Metaheuristics International Conference. 2005. 145-150.

Cirasella,J., Lyle,D.., McGeoch,L., Zhang,W. “The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests”. Springer Lecture Notes in Computer Science 2153. 2000. 32-59.

Glover,F., Gutin,G., Yeo,A., Zverovich,A. “Construction Heuristics for the asymmetric TSP”. European Journal of Operational Research 129 III. 2001. 555- 568.

Öncan,T., Kuban A., Laporte, G. “A comparative analysis of several asymmetric traveling salesman problem formulations”. Computers and Operational Research. 36 Issue III. 2009. 637-654

M. Grötschel and M. Padberg, (1993). "Ulysses 2000: In Search of Optimal Solutions to Hard Combinatorial Problems," Technical Report, New York University Stern School of Business.

Fuentes-Penna Alejandro and González-Ramírez Marcos S. (2013). Meta-Heuristic Algorithm based on Ant Colony Optimization Algorithm and Project Scheduling Problem (PSP) for the Traveling Salesman Problem. Journal of Network and Innovative Computing ISSN 2160-2174 Volume 1 (2013) pp. XXX-XXX © MIR Labs, www.mirlabs.net/jnic/index.html.

Optimization Software for Mathematical Programming (2013). http://business.aimms.com/. Last visited: 15/06/2013.

Ruiz-Vanoye J.A., Díaz-Parra O. (2011). An Overview of the Theory of Instances Computational Complexity. International Journal of Combinatorial Optimization Problems and Informatics, Vol. 2, No. 2. pp. 21-27, May-Aug. ISSN: 2007-1558.

 

^[a] Área académica: Lic. en Sistemas Computacionales