High perfomance computing applied to competitive facility location and design problemssingle and multi-objective optimization algorithms

Resumen

La localización de servicios pretende encontrar el emplazamiento de uno o más centros (servicios) de modo que se optimice una o varias funciones objetivo. Dicha función objetivo puede, por ejemplo, tratar de minimizar el coste de transporte, proporcionar a los clientes un servicio de forma equitativa, capturar la mayor cuota de mercado posible, etc. La localización de servicios abarca muchos campos, como la investigación operativa, la ingeniería industrial, la geografía, la economía, las matemáticas, el marketing, el planning urbanístico, además de otros muchos campos relacionados. Existen muchos problemas de localización en la vida real, como por ejemplo, la localización de hospitales, de colegios o vertederos, por nombrar algunos. Para ser capaces de obtener soluciones a los problemas de localización, es necesario desarrollar/diseñar un modelo que represente la realidad lo mas fielmente posible. Dichos modelos pueden llegar a ser realmente difíciles de tratar. Para resolver tales problemas de localización, se han propuesto muchos algoritmos de optimización global, tanto exactos como heurísticos. Los algoritmos exactos se caracterizan por ser capaces de obtener el óptimo global con una cierta precisión. Los algoritmos heurísticos, sin embargo, no pueden demostrar matemáticamente su convergencia al óptimo global, aunque pueden llegar a obtener soluciones tan buenas y precisas como las proporcionadas por los exactos. Los exactos son altamente costosos desde el punto de vista computacional, lo que implica que, en determinados casos, sea imposible aplicarlos para resolver un problema utilizando incluso los computadores más avanzados. De este modo los algoritmos heurísticos, con menos requerimientos computacionales que los exactos, se alzan entonces como una buena alternativa. No obstante, en determinadas circunstancias, las necesidades computacionales son tan elevadas, que el uso de algoritmos heurísticos ejecutándose en procesadores estándares actuales no es suficiente. En tales situaciones, se hace necesario el uso de computación de altas prestaciones. Esta tesis, High performance computing applied to competitive facility location and design problems: single and multi-objective optimization algorithms (Aplicación de la computación de altas prestaciones a problemas de localización competitiva con decisiones en diseño: algoritmos de optimización uni y multi-objetivo), proporciona, por un lado, algoritmos heurísticos capaces de resolver problemas de localización competitiva, tanto para funciones escalares como vectoriales, y por otro lado, técnicas paralelas que permiten reducir el tiempo de ejecución, resolver problemas más grandes, e incluso, en ocasiones, mejorar la calidad de las soluciones. Esta tesis esta organizada en cuatro capítulos. El primero de ellos es una introducción a las tres áreas de investigación en las que se enmarca esta tesis: localización, algoritmos de búsqueda y computación de altas prestaciones. Primeramente se describen de forma sucinta los principales elementos de un problema de localización. A continuación, se introducen los campos de la optimización global y multi-objetivo, y se definen los correspondientes conceptos de solución. Finalmente, se revisan brevemente las arquitecturas paralelas así como los modelos de programación utilizados en esta tesis. En el Capitulo 2, se presenta un nuevo modelo de localización competitiva en el plano de un solo centro, en el que la demanda varia dependiendo de la localización de dicho centro. Este nuevo modelo se compara con su correspondiente modelo de demanda fija, mediante algoritmos disponibles en la literatura. En particular, el algoritmo evolutivo UEGO se ha adaptado al nuevo modelo, mediante el diseño y desarrollo de un nuevo optimizador local. Además, se ha llevado a cabo un extenso estudio computacional con la intención de estudiar el impacto que tiene la consideración de demanda fija o demanda variable en la localización. Finalmente, se presenta una paralelización del algoritmo UEGO, que permite resolver problemas mas costosos. El Capitulo 3 esta dedicado al problema de líder-seguidor con demanda variable. Este problema se puede considerar una extensión del modelo anterior para el caso en el que el competidor (el seguidor) reacciona localizando un nuevo centro después de que la cadena (el líder) localice su propio centro. El objetivo del líder es encontrar la solución que maximice su beneficio, teniendo en cuenta la futura reacción del seguidor. Por tanto, hay que resolver dos problemas: el problema del seguidor, también denominado medianoide, y el problema del líder o centroide. El modelo matemático se detalla al comienzo del capitulo. Posteriormente, se proponen y evalúan varios algoritmos para resolver el problema del centroide. TLUEGO, basado en UEGO, es el algoritmo que proporciona mejores resultados. El capitulo finaliza presentando tres paralelizaciones de TLUEGO, que permiten resolver problemas mas grandes de forma precisa. El ultimo capitulo aborda un problema de localización bi-objetivo del franquiciado y del franquiciado. Este problema se define en el plano y ya estaba propuesto en la literatura. Para la obtención de una buena aproximación de todo el frente de Pareto, se propone un nuevo algoritmo evolutivo, llamado FEMOEA, que también se puede emplear para resolver otros problemas multi-objetivo generales tipo caja negra en donde no se conocen las características matemáticas de tales problemas. Para la resolución del problema bi-objetivo, FEMOEA incluye una búsqueda local, basada en el gradiente, para mejorar la calidad (eficiencia) del las soluciones. FEMOEA además, presenta un criterio de finalización que permite al algoritmo parar tan pronto como obtenga una buena aproximación del frente de Pareto. Para analizar el comportamiento y buen rendimiento de FEMOEA, se ha realizado un extenso estudio computacional. Finalmente, se propone una versión paralela de FEMOEA eficiente y eficaz que permite resolver problemas de mayor dimensión. La tesis finaliza con un resumen de los principales resultados obtenidos y apuntando líneas de investigación futura.