Metaheurísticas paralelas basadas en poblaciones aplicadas a problemas de optimización combinatorial en logística / Armin Mauricio Lüer Villagra ; profesor guía : Jaime Marcelo Bustos Gómez.

Incluye índice de contenidos, índice de tablas, índice de figuras, anexos.

Tesis a texto completo en formato PDF: Biblioteca Digital UFRO

Trabajo de Título : (Ingeniero Civil Industrial mención Informática).-- Universidad de La Frontera, Facultad de Ingeniería y Ciencias, 2009.

Bibliografía: hojas 98-102.

El presente trabajo aborda la aplicación de métodos heurísticos generales a problemas logísticos, desde la perspectiva metodológica (diseño de algoritmos) y computacional (implementación de éstos). Se estudian específicamente uno de localización: el de las p-medianas, y el de ruteo de vehículos clásico. La relevancia del presente trabajo radica en que tanto el diseño algorítmico para problemas matemáticamente complejos y de características comunes en la práctica, como su implementación computacional eficiente son áreas de trabajo de gran relevancia actual. Los métodos utilizados son llamados basados en poblaciones pues trabajan con un conjunto de soluciones factibles del problema, que combinan y mejoran en búsqueda del óptimo global del problema. Específicamente, se investiga la influencia que tiene en los resultados obtenidos el transformar algoritmos presentes en la literatura reciente en sus equivalentes paralelos. Para esto, se programan utilizando el lenguaje C++ junto con las bibliotecas STL y MPI dos algoritmos extraídos de artículos publicados, para luego transformarlos en algoritmos paralelos de múltiples poblaciones. La paralelización de los algoritmos para ambos problemas tuvo la misma estructura general, aunque para el caso del problema de ruteo de vehículos, el procesador encargado de coordinar el cómputo debía realizar operaciones de una mayor complejidad temporal tras cada comunicación, lo que ocasionó que limitará, en la mayoría de las pruebas, el desempeño del algoritmo. Esto no ocurrió para el caso del problema de las p-medianas, debido a su menor complejidad matemática subyacente, que permitió el uso de algoritmos de evaluación de soluciones más simples. Los algoritmos implementados son probados en un cluster de computadores de tamaño pequeño, y se realizan pruebas con distintos valores de los parámetros, como cantidad de soluciones migradas, tasas de migración, cantidad de procesos vecinos, etc. Se estudia, en un nivel medio de profundidad, la influencia de estos parámetros en la calidad de las soluciones obtenidas (efectividad) y el tiempo requerido para encontrarlas (eficiencia). En términos generales, se observa que los algoritmos paralelos permiten encontrar mejores soluciones que sus equivalentes secuenciales, requiriendo además una menor cantidad de iteraciones para alcanzar una misma calidad de soluciones. En las pruebas realizadas además queda de manifiesto que la implementación de estos algoritmos no es trivial, pues debe considerarse la capacidad de la red de comunicaciones que posee el cluster a utilizar, así como requerimientos específicos de implementación, tanto de hardware como software. Como proyecciones de este trabajo se encuentran ejecutar los algoritmos en una máquina masivamente paralela (también conocida multiprocesador), así como realizar pruebas computacionales más extensas, que permitan perfilar de forma más precisa la influencia promedio de los parámetros y la implementación bajo un esquema de paso de mensajes asíncrono.