Tesis doctoral de Héctor Efraín Ruiz Y Ruiz
En esta tesis nos enfocamos en el problema del árbol de expansión capacitado de coste mínimo (cmst, por sus siglas en inglés), que es una extensión del problema del árbol de expansión de coste mínimo (mst, por sus siglas en inglés). El cmst considera un vértice raíz que funciona como servidor central y que envía y recibe bienes (información, objetos, etc) a un conjunto de vértices llamados terminales. Los bienes solo pueden fluir entre el servidor y las terminales a través de enlaces cuya capacidad es limitada. Dichas restricciones sobre los enlaces dan relevancia al problema, ya que existen muchas aplicaciones en que las restricciones de capacidad son de vital importancia. Dentro de las áreas de aplicación del cmst más importantes se encuentran las relacionadas con el diseño de redes de telecomunicación, el diseño de rutas de vehículos y problemas de localización. Dentro del diseño de redes de telecomunicación, el cmst está presente cuando se considera un servidor central, cuya capacidad de transmisión y envío está limitada por las características de los puertos del servidor o de las líneas de transmisión. Dentro del diseño de rutas de vehículos el cmst resulta relevante debido a la influencia que pueden tener los árboles en el proceso de construcción de soluciones. Por el simple de añadir las restricciones de capacidad, el problema pasa de resolverse de manera exacta en tiempo polinomial usando un algoritmo voraz, a un problema que es muy difícil de resolver de manera exacta. en el primer capítulo se describe y define el problema, se introduce notación y se presenta una revisión bibliográfica de la literatura existente. En dicha revisión bibliográfica se incluyen formulaciones, métodos exactos y los métodos heurísticos utilizados más importantes. En el siguiente capítulo se muestran dos formulaciones binarias existentes, así como las desigualdades válidas más usadas para resolver el cmst. Para cada una de las formulaciones propuestas, se describe un algoritmo de planos de corte. dos nuevas formulaciones para el cmst se presentan en el tercer capítulo. Dichas formulaciones estás basadas en la identificación de un tipo de vértices especiales llamados subraíces. Los subraíces son aquellos vértices que se encuentran directamente conectados al raíz. Un forma de caracterizar las soluciones del cmst es a través de identificar los nodos subraíces y los nodos dependientes a ellos. Ambas formulaciones utilizan variables para identificar los subraices y variables adicionales para identificar los arcos que forman parte del árbol. Adicionalmente, las variables en la segunda formulación ayudan a identificar la profundidad con respecto al raíz a la que se encuentran dichos arcos. Para cada formulación se presentan desigualdades válidas y se plantean procedimientos para resolver el problema de su separación. en el cuarto capítulo se presenta un algoritmo genético llamado brkga para resolver el cmst. El brkga está basado en el uso de poblaciones generadas por secuencias de números aleatorios, que posteriormente evolucionan. Diferentes decodificadores, un método de búsqueda local, espacios de búsqueda y estrategias de exploración son presentados y analizados. El capítulo termina presentando un algoritmo final que permite la obtención de cotas superiores para el cmst.
Datos académicos de la tesis doctoral «The capacitated minimum spanning tree problem«
- Título de la tesis: The capacitated minimum spanning tree problem
- Autor: Héctor Efraín Ruiz Y Ruiz
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 15/07/2013
Dirección y tribunal
- Director de la tesis
- Elena Fernández Aréizaga
- Tribunal
- Presidente del tribunal: jaume Barceló bugeda
- Francisco Saldanha-da-gama (vocal)
- (vocal)
- (vocal)