Paralelización de heurísticas para el problema del vendedor viajero en grafos de gran tamaño
Cargando...
Archivos
Fecha
2009
Autores
Profesor/a Guía
Facultad/escuela
Idioma
es
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Andrés Bello
Nombre de Curso
Licencia CC
Licencia CC
Resumen
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.
Notas
Tesis (Magíster en Logística y Gestión de Operaciones, Ingeniero Civil Informático)
Palabras clave
Programación Heurística, Optimización Combinatoria, Vendedores Viajeros