Búsqueda de vecindad variable para el problema de localización de instalaciones sin capacidad

Abstract

La localización de instalaciones sin capacidad constituye un problema relevante en ámbitos como la logística, la distribución de recursos y la planificación de redes de telecomunicaciones. Dados un conjunto de posibles instalaciones y un conjunto de clientes, el problema consiste en seleccionar un indeterminado número de instalaciones a abrir para servir a todos los clientes con el objetivo de minimizar los costes de apertura y asignación. Debido a su clasificación como problema N P-difícil, la obtención de soluciones exactas se vuelve inabordable a gran es- cala, obligando a explorar métodos aproximados y metaheurísticas. En el marco de este problema, inicialmente se desarrollaron diversas aproximaciones exactas basadas. Sin embargo, más recientemente han cobrado relevancia los algoritmos aproximados y metaheurísticos, que logran soluciones de alta calidad con un coste computacional reducido. En este trabajo se propone una estrategia de búsqueda de vecindad variable que, mediante la apertura y cierre de instalaciones, equilibra la intensificación y la diversificación de la búsqueda. Los resultados experimentales sobre distintos conjuntos de instancias muestran que la propuesta logra solucio- nes de alta calidad muy próximas a las óptimas pero con un tiempo de ejecución reducido, comparándose con otros algoritmos del estado del arte.

Lucas Martin Garcia

Artificial Intelligence Phd Student

Lucas Martin graduated in Mathematics and Computer Science in the Complutense University of Madrid in 2024. He is working here as a researcher focusing in optimization problems.

Isaac Lozano-Osorio

Phd in Artificial Intelligence

Isaac Lozano graduated with a double degree in Computer Engineering and Computer Engineering from the Universidad Rey Juan Carlos, where he was awarded the prize for the Best Final Project. Subsequently, he completed a Master in Artificial Intelligence Research (UIMP). His main research interests are focused on the interface between Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristic procedures for graph modeled optimization problems.