Resumen

El problema del Árbol de Expansión Capacitado de Costo Mínimo es un problema clásico relacionado con el diseño de redes de computadoras centralizadas. En una versión simplificada de este problema se tiene un grupo de terminales y una sola instalación central (centro de control). Las restricciones adicionales vienen del hecho de que las uniones tienen una capacidad de tráfico finita, y cada una de las terminales tiene un requerimiento del tráfico. La solución del problema se basa en el diseño del árbol de expansión de costo mínimo que satisfaga las restricciones de capacidad, obteniendo una foresta en la cual sus componentes no sumen un tráfico mayor al permitido.

En esta investigación se propone un algoritmo que emplea el método de Búsqueda Tabú para la solución de problema del Árbol de Expansión Capacitado de Costo Mínimo. A partir de una solución inicial se define una estructura de vecindad basada en el intercambio de aristas. El método permite visitar soluciones infactibles considerando una función objetivo modificada para dar mayor flexibilidad al proceso de búsqueda, utilizando un esquema de oscilación estratégica.

Los resultados obtenidos son de buena calidad comparándolos contra los valores reportados por investigaciones anteriores.

Palabras clave: optimización combinatoria, árbol de expansión, árbol de expansión capacitado de costo mínimo, búsqueda tabú, oscilación estratégica.

Esta tesis sólo puede ser consultada por miembros de la Comunidad Universitaria. (ir al índice de contenido)

Quiroz Sánchez, L. A. 2004. Búsqueda Tabú para el Árbol de Expansión Capacitado. Tesis Maestría. Ciencias con Especialidad en Ingeniería Industrial. Departamento de Ingeniería Industrial y Textil, Escuela de Ingeniería, Universidad de las Américas Puebla. Diciembre. Derechos Reservados © 2004.