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.

[img]
Preview
Text (Texto Completo)
11129.pdf

Download (7MB) | Preview
[img]
Preview
Image
cc.jpg
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (6kB) | Preview

Abstract

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)
Additional Information: Tesis-(Doctor en Matemática Aplicada)-Universidad Nacional Autónoma de Nicaragua DoOC MATAPLIC 378.242 Men 2017
Uncontrolled Keywords: Algoritmo, Investigación Operaciones, Matemática discreta, Matemática Aplicada-Tesis-2017
Subjects: 500 Ciencias naturales y matemáticas > 510 Matemáticas
500 Ciencias naturales y matemáticas > 510 Matemáticas > 519 Probalidades y matemática aplicada
Divisions: FACULTAD REGIONAL MULTIDISCIPLINARIA DE CHONTALES > Doctor en Matemática Aplicada
Depositing User: Lic 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

Actions (login required)

View Item View Item
Estadisticas: Clic Aquí
Exportar: Clic Aquí