2026-04-28T19:42:35Zhttps://uvadoc.uva.es/oai/requestoai:uvadoc.uva.es:10324/438372021-06-30T03:58:58Zcom_10324_38col_10324_852
00925njm 22002777a 4500
dc
Padrones Rengel, María
author
2020
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.
http://uvadoc.uva.es/handle/10324/43837
Problema del mínimo árbol con capacidades: modelización y resolución heurística