Problemas de Cubrimiento Máximo. Modelización y métodos de resolución exactos y heurísticos

Abstract

En este trabajo se tratan diferentes problemas de Cubrimiento Máximo, que entran dentro de problemas de localización más generales. Se comparan, a partir de dos tipos de archivos de datos, distintos métodos de resolución heurística de problemas de Cubrimiento Máximo, para hallar la disposición de los servicios que atienda de la mejor forma posible las diferentes demandas dada una serie de restricciones. Se empieza con un capítulo, en el que se abordan los principales problemas de localización discreta de los servicios, así como los distintos tipos de objetivo que se pueden lograr. En los dos siguientes capítulos, se habla de las diferentes aplicaciones y adecuación del problema de Cubrimiento Máximo, y de las heurísticas y metaheurísticas para hallar su solución aproximada. También se realiza un breve análisis de los resultados para esos métodos heurísticos, que concluye con la elección del método Greedy + Búsqueda Local como el que más rápidamente se aproxima a la solución óptima del problema de Cubrimiento Máximo y que en algunas ocasiones puede llegar a alcanzarlo. A continuación se detallan algunos modelos de cubrimiento adicionales de interés, como son los modelos de varios equipos y los de cubrimiento reforzado, no estudiados durante el Grado. Finalmente se muestran las conclusiones obtenidas de este trabajo.

In this project, different Maximum Coverage problems are dealt with, which are part of more general location problems. Using two types of data files, different methods for solving Maximum Coverage problems are compared to find the provision of services that best meets the different demands given a series of restrictions. It begins with a chapter, in which the main problems of discrete location of services are addressed, as well as the different types of objectives that can be achieved. In the next two chapters, we discuss the different applications and adequacy of the Maximum Coverage problem, and the heuristics and metaheuristics to find its approximate solution. A brief analysis of the results for these heuristic methods is also carried out, which concludes with the choice of the Greedy + Local Search method as the one that most quickly approaches the optimal solution of the Maximum Coverage problem and that can sometimes reach it. . Some additional coverage models of interest are detailed below, such as the multi-equipment models and the reinforced coverage models, not studied during the Degree. Finally the conclusions obtained from this project are shown.