Introducción a técnicas de resolución del problema del viajante de comercio

Implementación de soluciones para el Problema del Viajante de Comercio
Fernando Valenzuela† y Claudio Verrastro‡

†Dto Electrónica UTN FRBA
fdvalenzuela@electron.frba.utn.edu.ar
‡Grupo de Inteligencia Artificial UTN FRBA

Resumen— El presente trabajo tiene como objetivo presentar una implementación realizada tratando el problema del Viajante de Comercio, problema típico en la búsquedaoperativa. La intención de este trabajo es ofrecer una plataforma para facilitar el abordaje del problema y servir como material de soporte para las clases introductorias a la Inteligencia Artificial.

Se realizaron tres implementaciones, la primera es la del algoritmo A-estrella (A*), el cual asegura encontrar el camino óptimo. Ésta metodología de resolución resulta apta para problemas con menosde 16 nodos aproximadamente ya que el tiempo de resolución depende exponencialmente de la cantidad de éstos. La segunda metodología implementada es la de Recocido Simulado (Simulated Annealing), algoritmo que encuentra soluciones sub-óptimas pero en un tiempo de resolución mucho menor, lo que lo hace adecuado para problemas con mayor cantidad de nodos. Finalmente se realizó la implementación de unalgoritmo descripto por el Ingeniero Claudio Verrastro, que se basa principalmente en seleccionar caminos, y luego calcular los ahorros que se producirían reemplazando algunos de ellos por otros que eliminen el exceso de caminos entrantes a cada nodo.

Palabras Clave— TSP Viajante de Comercio Algoritmos VisualBasic .NET Educación

I. INTRODUCCIÓN

El problema del Viajante de Comercioes típico en la Inteligencia Artificial, y plantea la situación que dada una serie de ciudades y los costos asociados a desplazarse entre cualquiera de ellas, se debe encontrar un camino cerrado de manera de recorrer todas las ciudades pasando únicamente una vez por cada una de ellas y que presente el menor costo total. [1]
El problema recién descrito es muy amplio, por lo cual para éste trabajose han realizado ciertas restricciones sin que esto afecte en gran medida la generalidad. A saber:
• El costo de ir de un nodo X a un nodo Y es igual al costo de ir del nodo Y al nodo X.
• Todos los nodos están conectados, es decir, que existe un camino entre un nodo X y cualquier otro nodo del problema. Ésta restricción puede ser sorteada poniendo un costo mucho mayor a los costossignificativos del problema.
[pic]
Fig. 1: Descripción del problema

Los algoritmos desarrollados son capaces de resolver el problema con las condiciones recién detalladas. De todas maneras, la implementación que aplica estos algoritmos introduce un limitante más: que los nodos están ubicados en un plano Euclídeo. Esto fue planteado así de manera de tener una representación gráfica del problema, dondemuchas veces es sencillo evaluar qué tan buena resulta una solución observando el recorrido y los cruces entre los caminos.

[pic][pic]

Fig 2: Comparación gráfica de soluciones.

Planteado el problema, pasamos a introducir los algoritmos implementados.
En primer lugar, el algoritmo A* [2] es un método de búsqueda informada en grafos, esto quiere decir que para funcionar debe tener undenominado “conocimiento” del grafo que pretende resolver. Brevemente, este “conocimiento” está dado por una función heurística minorante, es decir, un costo hipotético inferior al menor costo posible en el cual se basa para ordenar las posibles soluciones.

El algoritmo de Recocido Simulado [3] inspira su funcionamiento en el proceso de recocido de acero, que consiste en calentar el materialde manera que sus átomos ganen energía y se desplacen aleatoriamente para que luego mediante un enfriamiento lento pasen a ocupar su lugar de menor energía. La analogía que se realiza en el algoritmo consiste en obtener un camino inicial y luego generar permutaciones aleatorias entre nodos. Si la permutación resulta en un camino de menor costo, ésta es consolidada (proceso de enfriamiento). Si...