Raveling Salesman Problem (TSP)Diseño de Algoritmos Heurísticos y Metaheurísticos eficientes para resolver el Problema del Agente Viajero

Mendoza Casanova, José Jesús (2017) Raveling Salesman Problem (TSP)Diseño de Algoritmos Heurísticos y Metaheurísticos eficientes para resolver el Problema del Agente Viajero. Doctoral thesis, Universidad Nacional Autónoma de Nicaragua, Managua.

Preview	Text (Texto Completo) 11129.pdf Download (7MB) | Preview
Preview	Image cc.jpg Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (6kB) | Preview

Resumen

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

Item Type:	Thesis (Doctoral)
Información Adicional:	Tesis-(Doctor en Matemática Aplicada)-Universidad Nacional Autónoma de Nicaragua DoOC MATAPLIC 378.242 Men 2017
Palabras Clave Informales:	Algoritmo, Investigación Operaciones, Matemática discreta, Matemática Aplicada-Tesis-2017
Materias:	500 Ciencias naturales y matemáticas > 510 Matemáticas 500 Ciencias naturales y matemáticas > 510 Matemáticas > 519 Probalidades y matemática aplicada
Divisiones:	CENTRO UNIVERSITARIO REGIONAL DE CHONTALES > Doctor en Matemática Aplicada
Depositing User:	MSc. David Montalvan
Date Deposited:	01 Dec 2018 16:24
Last Modified:	01 Dec 2018 16:24
URI:	http://repositorio.unan.edu.ni/id/eprint/8779

Downloads

Actions (login required)

View Item