Problema del mínimo árbol con capacidades: modelización y resolución heurística

Abstract

Es evidente que vivimos en un mundo conectado. Podemos encontrar sistemas de conexión a mayor o menor escala en, prácticamente, cualquier ámbito en el que se nos ocurra pensar: desde infraestructuras de carácter civil como carreteras, hasta en el terreno personal como es el caso de las redes sociales. Dada la utilidad y la importancia de unir elementos que, por determinada razón, interesa que estén relacionados, es necesario dedicar esfuerzo a encontrar la mejor forma de hacerlo. En este trabajo de fin de carrera se aborda el problema del mínimo árbol expandido con capacidades conocido como CMST. A lo largo de estas páginas se aporta información sobre las características y la implementación de estas estructuras, y se exponen distintos métodos exactos y heurísticos (inluyendo métodos de mejor y metaheurísticas) de enfrentar el problema. Todos los modelos se han aplicado sobre varios conjuntos de datos para poder comparar y sacar conclusiones sobre el desempeño de cada uno.

It is evident that we live in a connected world. Connecting systems can be found in such different fields like road infrastructures or social networks. Due to how important and useful connecting up several elements can be, it is necessary to design carefully a way to do it. This paper is an approach to the capacitated minimum spanning tree problem. In the following pages some characteristics will be provided as well as a couple of ways to implement the solution trees. Also, exact and heuristic methods (including enhancements and metaheuristics) to solve the CMST problem are exposed. These methods have been applied to several different data files in order to compare their performance.