Metaheuristica

TÉCNICAS HEURÍSTICAS APLICADAS AL PROBLEMA DEL CARTERO VIAJANTE (TSP)
RESUMEN El problema del cartero viajante (Traveling Salesman Problem – TSP) es un problema típico de optimización. En este documento se presentan algunas técnicas heurísticas de optimización (Algoritmos Genéticos, Simulated Annealing, Colonia de Hormigas, Búsqueda Tabú y Grasp) aplicadas a la solución de este problema. Lasolución al problema consiste en encontrar la ruta óptima para recorrer n ciudades sin repetirlas finalizando en la ciudad de origen. PALABRAS CLAVES: Optimización, cartero viajante, algoritmos genéticos, simulated annealing, colonia de hormigas, tabu search, grasp, metaheurísticas. ABSTRACT The Traveling Salesman Problem is a typical problem of optimization. In this document are presented someoptimization heuristic techniques (Genetic Algorithms, Simulated Annealing, Ant Colony Optimization, Tabu Search and Grasp) used in the solution of this problem. To solve this problem is necessary to find the optimal way to travel on n cities without repeat them and ending at the original city. KEYWORDS: Optimization, traveling salesman problem, genetic algorithms, simulated annealing, ant colonyoptimization, tabu search, grasp, metaheuristics. Ricardo Alberto Hincapié Isaza Ingeniero Electricista Estudiante Maestría Ingeniería Eléctrica ricardohincapie@utp.edu.co

Carlos Alberto Ríos Porras Ingeniero Electricista Estudiante Maestría Ingeniería Eléctrica alpor@utp.edu.co

Ramón Alfonso Gallego R, Ph. D. Profesor Facultad de Ingeniería Eléctrica Universidad Tecnológica de Pereiraralfonso@utp.edu.co

Grupo de Investigación en Planeamiento de Sistemas Eléctricos. Universidad Tecnológica de Pereira.

1.

INTRODUCCION

Una gran cantidad de problemas importantes de optimización no pueden ser resueltos usando métodos exactos, es decir, no es posible encontrar su solución óptima con esfuerzos computacionales aceptables aunque se pueda contar con computadores de alta velocidadoperando en paralelo. Un gran problema de la optimización es el fenómeno llamado explosión combinatorial, que significa, que cuando crece el número de variables de decisión del problema, el número de decisiones factibles y el esfuerzo computacional crecen en forma exponencial. Sin embargo, no todos los problemas combinatoriales son tan complejos de resolver; existen algunos para los cuales hayalgoritmos que resuelven esos problemas con un esfuerzo computacional que crece de manera polinomial con el tamaño del problema, [4, 6]. Enmarcado dentro de estos problemas combinatoriales se encuentra el problema del cartero viajante (TSP). Este problema consiste en encontrar el camino más corto (ruta) para visitar n ciudades bajo la condición de visitar cada ciudad una sola vez, regresando a la ciudadde partida. Desde la década de los 50`s muchos algoritmos han sido desarrollados para encontrar la solución a este problema encontrando buenas soluciones pero no necesariamente

las soluciones óptimas. En los 80`s las técnicas de solución se centraron en la aplicación de metaheurísticas de propósito general incluyendo entre estas el simulated annealing, algoritmos genéticos, colonia de hormigas ybúsqueda tabú entre otros. En este trabajo se aplican algunas técnicas heurísticas como Simulated Annealing, Algoritmos Genéticos, Búsqueda Tabú, Grasp y Colonia de Hormigas para encontrar la solución óptima al problema del cartero viajante usando como sistema de prueba un conjunto de ocho ciudades.

2.

PLANTEAMIENTO MATEMÁTICO DEL PROBLEMA

En el problema del cartero viajante – TravelingSalesman Problem (TSP) existe un conjunto de n ciudades (nodos), V = {1, 2, 3,…, n}, y un conjunto de caminos (arcos) uniendo cada una de las ciudades, así el camino (i,j)ЄA, cij es la “distancia” (función objetivo) para ir de la ciudad i a la ciudad j (cij no necesariamente es igual a cji). Un cartero debe realizar un tour (recorrido) comenzando en una cierta ciudad de origen y luego visitar...