Raveling Salesman Problem (TSP)Diseño de Algoritmos Heurísticos y Metaheurísticos eficientes para resolver el Problema del Agente Viajero
El Problema del Agente Viajero (Traveling Salesman Problem, TSP) es aún un problema abierto en el área de conocimiento de la Programación Matemática. Desde los años cincuenta ha despertado mucho interés dentro de la comunidad científica por su forma sencilla de enunciarse y por su extrema dificultad...
| Autor Principal: | Mendoza Casanova, José Jesús |
|---|---|
| Formato: | Tesis |
| Idioma: | Español Español |
| Publicado: |
2017
|
| Materias: | |
| Acceso en línea: |
http://repositorio.unan.edu.ni/8779/ http://repositorio.unan.edu.ni/8779/1/11129.pdf http://repositorio.unan.edu.ni/8779/2/cc.jpg |
| Sumario: |
El Problema del Agente Viajero (Traveling Salesman Problem, TSP) es aún un problema abierto en el área de conocimiento de la Programación Matemática. Desde los años cincuenta ha despertado mucho interés dentro de la comunidad científica por su forma sencilla de enunciarse y por su extrema dificultad en resolverse, aún teniendo a mano el desarrollo tecnológico con computadoras cada día más veloces y un sinnúmero de ideas para tratarlo, desde los aportes teóricos, hasta métodos de aproximación como Simulated Annealing, Greedy, Inteligencia Artificial, Simulación heurística, entre otros. En esta investigación, la metodología que se ha utilizado para abordar el Problema del Agente Viajero ha sido la siguiente: estructurar la teoría referida a convexidad y poliedros sobre el TSP; diseñar algoritmos heurísticos tales como el Nearest Neighbor (Vecino Más Cercano) y el Greedy Randomized
Adaptive Search Procedures-GRASP (Procedimientos de Búsqueda Basados en Funciones Voraces o Codiciosas), y metaheurísticos como el Tabu Search (Búsqueda Tabú) o el Scatter Search (Búsqueda Dispersa). Ambos tipos de algoritmos se implementaron en lenguaje C++ del ambiente de programación Microsoft Visual Studio 2008, y los resultados se compararon con los obtenidos
mediante el uso de los softwares académicos Solver de Excel y WinQSB.
Finalmente, se compararon los resultados obtenidos por los algoritmos de esta investigación, con los encontrados por el Solver, WinQSB y los que aparecen en la TSPLIB, y se concluyó que de los dos algoritmos heurísticos y los dos metaheurísticos diseñados, resultaron muy satisfactorios los dos últimos en el balance entre eficacia y eficiencia. El mejor algoritmo para instancias pequeñas y medianas fue el Tabu Search, y para instancias grandes el Scatter Search. Palabras claves: Investigación de Operaciones, Problema del Agente Viajero, Métodos Exactos, Métodos Heurísticos, Métodos Metaheurísticos |
|---|