Regresar

Diseño e implementación de un algoritmo de tipo recocido simulado para la resolución del problema del agente viajero

Abstract:

En el presente trabajo resolveremos el problema del Agente Viajero haciendo uso del Algoritmo del Recocido Simulado, para determinar \as rutas validas entre dos o mas nodos. El algoritmo fue aplicado en el sector centric0 de Guayaquil considerado como el sector 44 en el plano General de Guayaquil. El algoritmo de Recocido Simulado fue disefiado para el area de termodinam ica. Dada la dificultad practica para resolver de forma exacta (simplex, "ramificacion y acotacion", teoria de grafos, etc) toda una serie de importantes problemas combinatorios complejos ya sea por que utilizan un tiempo no polinomial de resolucion o por que no necesitan llagar a un optimo, comenzaron aparecer algoritmos que proporcionan soluciones factibles (es decir, que satisfacen las restricciones del problema), las cuales aunque no optimicen la solucion objetivo, se supone que al menos se acercan al valor optimo en un tiempo de calculos razonables. Podriamos llamarlas en lugar de optimas, "sa.tisfactorias", pues al menos es de suponer que son lo suficientemente buenas como para servirnos. Este tip0 de algoritmo se denominan heuristicos. Esta tesis esta dividida en 6 capitulos ademas de las conclusiones y recomendaciones. Capitulo 1 , llamado Teoria de Grafos que nos muestra antecedente necesario para la compresion de esta Tesis. En el Capitulo 2 se presenta una amplia descripcion de la Heuristica y sus formas de resolver problemas dificiles. En el siguiente Capitulo, se analiza la teoria relacionada con la implementacion cornputacional de este algoritmo, por lo cual se le ha llamado al capitulo Complejidad Computacional. Los capitulos 4,5 y 6 son el desarrollo de mi tesis, en el Capitulo 4 present0 el disetio del algoritmo de tipo Recocido Simulado, su analogia parametrica, el Modelamiento, el algoritmo y como resuelve el Problema del Agente Viajero. En el Capitulo 5 se realizo la implementacion del algoritmo de Recocido Simulado V.2, donde se comenzo el levantamiento de la inforrnacion de campo, se determino nrtas y nodos, georeferenciacion de planos y puntos, determinacion de la matriz de distancia y la implementacion cornputacional en si, considerando importante dedicar el capitulo 6 unicamente al analisis de resultados.