Hernández O., GonzaloFernández Soto, César AntonioFacultad de Ingeniería2021-03-312021-03-312009http://repositorio.unab.cl/xmlui/handle/ria/18405Tesis (Magíster en Logística y Gestión de Operaciones, Ingeniero Civil Informático)El Traveling Salesman Problem (TSP) es uno de los problemas NP-Completos más estudiados en la literatura desde la década de los 50's. Esto debido a la enorme cantidad de aplicaciones que presenta, los que van desde el ruteo vehicular hasta el diseño de circuitos electrónicos impresos en placas. El TSP aplicado a problemas de transporte, se torna un problema logístico-operativo, por lo que su resolución en tiempos y optimalidad razonables sigue siendo un reto. Existen diversas formas de resolver el problema, pero su costo computacional es alto y se requiere una gran cantidad de tiempo de ejecución al resolver instancias sobre los 10.000 nodos. Para mejorar el tiempo de ejecución se utilizará programación paralela basada en C++/MPI, ejecutando las implementaciones en un Cluster Intel Xeon Multicore1. Para obtener una paralelización de heurísticas del TSP, se han definido los siguientes objetivos generales (números) y específicos (letras): 1. Establecer la evolución del problema a través del tiempo, en términos computacionales y de metologías empleadas. a) Mostrar los diferentes modelos matemáticos que representan el problema. b) Destacar los principales investigadores y sus aportes vs tamaño del problema. e) Indicar la curva de evolución en términos de las soluciones alcanzadas desde sus inicios hasta la actualidad. 2. Analizar el marco conceptual y metodológico de las técnicas utilizadas para resolver el problema a) Entregar una revisión detallada de las principales técnicas exactas, heurísticas y metaheurísticas. b) Clasificar las técnicas de acuerdo al tipo de búsqueda (global o local), generación de solución inicial y selección del vecindario. e) Realizar una comparación de métodos de acuerdo a su clasificación. 3. Analizar el comportamiento de las heurísticas en instancias de gran tamaño (sobre 10.000 ciudades), utilizando grafos totalmente conexos y una función de distancia Euclidiana. 1 Cluster de Laboratorio de Modelos y Métodos Cuantitativos del Departamento de Informática, UTFSM. a) Construir curva de complejidad computacional (Tiempo de CPU vs Número de Ciudades del tour) para cada método heurístico utilizado. b) Análisis de la profundidad (número de ejecuciones en cadena) que puede ser alcanzada hasta lograr una condición de parada. e) Realizar mejoras a la implementación, basándose en la representación del tour y características particulares del problema. 4. Estudiar, diseñar e implementar heurísticas paralelas para el TSP. a) Entregar una descripción de los conceptos más relevantes de computación paralela. b) Diseñar e implementar una heurística que obtenga resultados comparativos en términos de optimalidad, tiempo de ejecución y eficiencia respecto de otras heuristícas que se mencionan en la literatura. En este último objetivo, se plantea una heurística paralela que pueda reducir el tiempo de ejecución como también escalar el problema a instancias de gran tamaño, utilizando una técnica de descomposición del problema en subtours, lo que a través de una heurística de agregación, entrega un tour de igual cantidad de ciudades que el original. La descomposición propuesta utiliza el concepto de multinivel descrito en Karypis y Kumar (1998), Walshaw (2001a) y las ideas de partición basadas en vecindarios geométricos de Aarts y Lenstra (1997), obteniendo una partición del grafo, dividiéndolo en,\ (par) cuadrantes. En cada cuadrante se aplica un refinamiento basado en 2-0pt hasta que la solución S obtenida en la iteración n + l sea igual a la obtenida en la iteración n. Para establecer la optimalidad de la heurística propuesta se utiliza una selección de instancias de TSPLIB (2008) y NationalTSP (2008), que van desde los 10.639 hasta las 85.900 ciudades y que poseen el valor del tour óptimo. La heurística propuesta obtiene su mejor cercanía al óptimo en la instancia pla85900, obteniendo en promedio un 6.3577 % con respecto del óptimo y en términos globales un 9.0596 %. Se registra una eficiencia de 41.36 % y se observa que el speed-up mejora al aumentar el número de ciudades, adquiendo la heurística propuesta mayores beneficios al aumentar el tamaño del problema. La estructura de los grafos euclideanos de instancias con una alta densidad de ciudades y con una distribución poco esparcida en las regiones rectangulares, tienen un efecto positivo en términos de optimalidad, ya que esta configuración favorece la disminución de la pérdida de optimalidad producida por la agregación de los subtours.esProgramación HeurísticaOptimización CombinatoriaVendedores ViajerosTesis