Solving Competitive Location Problems via Memetic Algorithms: High Performance Computing Approaches

La localización de servicios (“Facility location” en inglés) pretende encontrar el emplazamiento de uno o más centros (servicios) de modo que se optimice una determinada función 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 más fielmente posible. Dichos modelos pueden llegar a ser realmente difíciles de tratar. Muchos algoritmos de optimización global, exactos y heurísticos han sido propuestos para resolver problemas de localización. Los algoritmos exactos se caracterizan por ser capaces de obtener el óptimo global con una cierta precisión. Sin embargo, suelen ser altamente costosos desde el punto de vista computacional, lo que implica que, en determinados casos, sea imposible aplicarlos para resolver un problema. Los algoritmos heurísticos se alzan entonces como una buena alternativa. No obstante, en determinadas circunstancias, los requerimientos computacionales son tan elevados, que el uso de algoritmos heurísticos ejecutándose en procesadores estándares no es suficiente. En tales situaciones, la computación de altas prestaciones es necesaria. Esta tesis, “Solving competitive location problems via memetic algorithms. High performance computing approaches” (Algoritmos meméticos para problemas de localización competitiva. Computación de altas prestaciones), proporciona, por un lado, algoritmos heurísticos capaces de resolver problemas de localización, tanto en el dominio continuo como en el discreto 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 incluye tres partes bien diferenciadas, cada una de las cuales se divide en varios capítulos. La primera parte Preliminaries (Preliminares), está compuesta por tres capítulos que revisan el estado actual de la optimización global, de la computación de altas prestaciones y de la ciencia de la localización, respectivamente. El Capítulo 1 comienza con la definición de los problemas de optimización, y continúa con la introducción de diferentes métodos heurísticos para tratar con ellos. El Capítulo 2 describe brevemente algunas de las arquitecturas paralelas y de los modelos de programación paralelos. Finalmente, en el Capítulo 3, se describen y analizan los principales ingredientes de la localización de servicios, y se presenta una revisión sobre problemas de localización continuos y discretos. La segunda parte de la tesis, Solving continuous location problems (Resolviendo problemas de localización continua), comienza en el Capítulo 4, donde se presenta un problema de localización competitiva en el plano y se revisan dos técnicas previamente propuestas en la literatura para resolverlo. Posteriormente, se describe una nuevo algoritmo evolutivo para resolver óptimamente el problema, llamado UEGO, y se comparan todas las alternativas. Finalmente, varias estrategias paralelas basadas en el algoritmo UEGO son analizadas y evaluadas. En el Capítulo 5, el problema de localizar un solo centro en el plano, se extiende al caso en el que la cadena o empresa quiere emplazar más de un servicio. Para abordar este problema, se adapta el algoritmo UEGO presentado en el Capítulo 4, además de otras técnicas descritas en la literatura. A través de un extenso estudio computational, todas los algoritmos son comparados y se concluye que UEGO es el mejor de todos ellos, tanto por su eficiencia como por su efectividad. UEGO es usado para realizar un estudio de sensibilidad con el fin de chequear los cambios de diseño/localización óptima cuando los parámetros del modelo cambian. Finalmente, se presentan y evalúan varias técnicas paralelas para tratar el problema de localización de varios centros. El Capítulo 6 está dedicado al problema de líder-seguidor. En dicho problema, tras la localización del líder, el competidor reacciona localizando otro nuevo centro en el lugar que maximice su propio beneficio. El objetivo del líder es encontrar la solución que maximice su beneficio, sabiendo que posteriormente, la competencia localizará un nuevo centro. Por tanto, hay que resolver dos problemas simultáneamente: el problema del seguidor, también denominado medianoide, y el problema del líder o centroide. El modelo del problema del líder-seguidor se describe al principio del capítulo. Posteriormente, se proponen y evalúan varios algoritmos para resolver tanto el problema del medianoide como el del centroide. El capítulo finaliza con la paralelización de uno de los algoritmos propuestos. La tercera parte de la tesis, Solving discrete location problems (Resolviendo problemas de localización discreta), comienza en el Capítulo 7 con una introducción sobre algunos problemas de localización discreta. Este capítulo analiza aquellos casos en los que dichos problemas podrían presentar varias soluciones óptimas. Además, se muestra cómo un usuario experimentado podría obtenerlas, y se establecen algunos criterios para seleccionar una solución óptima entre diferentes alternativas. El capítulo finaliza con la descripción del algoritmo MSH, un heurístico ampliamente usado en la literatura para la resolución de problemas de localización discreta. El Capítulo 8 describe un algoritmo genético multimodal, GASUB, capaz de resolver varios problemas de localización discreta. El algoritmo tiene diferentes parámetros de entrada que pueden ser ajustados para alcanzar diferentes metas. En este capítulo, el objetivo es obtener al menos una solución óptima, pero invirtiendo el menor esfuerzo (tiempo) computacional posible. Para tal fin, se lleva a cabo un estudio previo y se determina el conjunto de parámetros adecuado. GASUB, con este conjunto de parámetros, es comparado con el optimizador Xpress-MP y con la heurística MSH, los cuales son capaces de obtener un único óptimo global (de manera directa). Sin embargo, teniendo en cuenta que los problemas de localización discreta considerados en esta tesis pueden tener más de una solución óptima, en el Capítulo 9 se analiza la posibilidad de explotar las propiedades multimodales de GASUB. Con este fin, se propone un nuevo conjunto de parámetros, con el que GASUB es nuevamente evaluado. Finalmente, se da una paralelización de GASUB y se estudian algunas de las soluciones globales encontradas por los algoritmos. La tesis finaliza con un resumen sobre los principales resultados obtenidos y sobre la líneas de investigación futura.