Download Búsqueda tabú y búsqueda dispersa para el árbol de expansión

Búsqueda tabú y búsqueda dispersa para el
árbol de expansión capacitado de coste mínimo
Efraín Ruiz
Dept. d’Estadística i Investigació Operativa
Universitat Politècnica de Catalunya
Jordi Girona, 1-3. C5-224
08034, Barcelona, España
efrain.ruiz@upc.edu
1. Introducción
El problema del árbol de expansión capacitado de coste mínimo (CMST por sus siglas
en inglés) ha sido típicamente utilizado como un subproblema en el diseño de redes
de telecomuniación. Se requiere encontrar la mejor forma de conectar n terminales,
ubicadas en localizaciones predeterminadas, a un nodo central (comunmente un centro
de cómputo o un servidor). Cada terminal utiliza una línea de transmisión durante una
cierta fracción del tiempo, para enviar o recibir mensajes. Para utilizar eficientemente
la capacidad de las líneas de transmisión se consideran diseños en los que se conectan
varias terminales a cada línea de transmisión, de forma tal que cada línea pueda ser
compartida por varias terminales. A dichas líneas de transmisión se les denomina líneas
mutipunto. De esta manera, cada línea multipunto puede ser representada mediante
un árbol de expansión que a su vez está conectado con el nodo central. En el diseño
topológico de redes, este problema equivale a encontrar un árbol en un grafo G =
(V, E), donde cada uno de los vértices del conjunto V , exceptuando al nodo central,
corresponde a una terminal y las aristas del conjunto E representan cableados factibles.
Entonces, cada subárbol conectado con el nodo central representa una línea multipunto.
Sin embargo, cada uno de los puertos de entrada del nodo central puede manejar una
cierta cantidad fija de información y por lo tanto la cantidad de información que puede
fluir en cada una de las líneas de transmisión es limitada (no debe exceder una cierta
cantidad fija de flujo b).
El problema CMST es NP-completo para 2 < b < n/2 (ver, [7]). Esto implica que
el problema es difícil de resolver de manera exacta. Es por ello que en la mayoría de
las investigaciones previas se le ha dado un tratamiento heurístico.
El estudio del problema del árbol de expansión capacitado de coste mínimo también tiene interés en el contexto de los problemas de rutas de vehículos. Dicho interés
se deriva de la influencia que tienen los árboles de expansión en los procedimientos
constructivos de soluciones posibles para problemas de rutas de vehículos. Además,
en los problemas de rutas de vehículos es muy usual la consideración de restricciones
de capacidad. El estudio de los árboles de expansión capacitados permite el diseño de
procedimientos eficientes para la obtención de soluciones factibles en problemas de
rutas de vehíulos.
En este trabajo se propone un método heurístico para obtener cotas superiores para
el CMST basado en una combinación de las metodologías de búsqueda tabú y búsqueda
dispersa. Se realizaron pruebas computacionales para evaluar el comportamiento del
método propuesto. A partir de los resultados obtenidos se observa que el algoritmo propuesto produce soluciones factibles de buena calidad con un esfuerzo computacional
razonable.
2. El problema del árbol de expansión capacitado de
coste mínimo
El problema del árbol de expansión capacitado de coste mínimo (CMST ) considera la
siguiente situación. Sea G = (V, E) un grafo no dirigido, donde V = {0, 1, . . . , n} es un
conjunto de vértices y E = {e : e = {i, j}, i, j ∈ V } es un conjunto de aristas. Al vértice
0 se le denomina nodo raiz. A cada elemento del conjunto de aristas, e ∈ E, se le asocia
un coste ce ≥ 0 y a cada uno de los elementos i ∈ V \ {0} del conjunto de vértices, se
le asocia un peso di ≥ 0, que representa la demanda del vértice i. Adicionalmente, se
especifica un parámetro de capacidad b. Se require encontrar un árbol de expansion de
coste mínimo de manera que la suma de las demandas de cada subárbol conectado con
el nodo raíz sea menor o igual a b.
A continuación se proporciona un modelo de programación matemática para el
problema del CMST que se formula a partir de un grafo dirigido asociado al grafo
original G. Cada arista {i, j} ∈ E se reemplaza por dos arcos (i, j) y ( j, i) con costes
ci j = c ji = ce , y el conjunto de aristas E se reemplaza por el conjunto de arcos A =
{a : a = (i, j), i, j ∈ V }. Sea S ⊆ V \ {0} cualquier subconjunto de vértices, δ − (S) =
{a ∈ A : a = (i, j), i 6∈ S, j ∈ S} el conjunto de arcos incidentes con los vértices del conjunto S y d(S) = ∑ dk la demanda total de los vértices del conjunto S. Se definen las
k∈S
siguientes variables de decisión
1, si se selecciona el arco a,
xa =
0, en otro caso.
El CMST se puede formular de la siguiente manera
∑ ca xa
min
(1)
a∈A
∑
s.t.
a∈δ − (i)
∑
a∈δ − (S)
xa = 1 ∀i ∈ V \ {0}
(2)
xa ≥ dd(S)/be ∀S ⊆ V \ {0} ,
xa ∈ {0, 1}
2
|S| ≥ 2
(3)
∀a ∈ A
(4)
Grupo
tc40
te40
tc80
te80
cm50
cm100
cm200
DesvM
0.03 %
0.49 %
0.32 %
0.91 %
0.93 %
0.52 %
1.66 %
DesvP
0.04 %
0.72 %
0.47 %
1.42 %
1.62 %
1.07 %
2.73 %
Cuadro 1: Resultados obtenidos con el algoritmo combinado
Las restricciones (2) aseguran que existe un solo arco incidente con cada vértice.
Las restricciones (3) garantizan la conectividad de la solución y también aseguran que
la demanda agregada de cada subárbol es menor o igual que la capacidad.
3. Experiencia computacional
Para poder evaluar el desempeńo del algoritmo propuesto se consideraron diferentes
conjuntos de problemas de prueba disponibles en htt p : //people.brunel.ac.uk/ mast j jb/ jeb/ jeb.html.
Los problemas están divididos en tres clases: tc, te y cm. Para la clase tc y te se consideran dos grupos de problemas diferentes, de acuerdo con el número de vértices (40
y 80 vértices). Asimismo, para la clase cm, se consideran tres grupos de problemas de
acuerdo con el número de vértices (50, 100 y 200 vértices). Para cada conjunto de datos
se consideran distintos valores para el parámetro de capacidad b. Para los problemas
de las clases tc y te con 40 vértices se consideran dos valores distintos para b (5 y 10).
Para los problemas de la clases tc y te con 80 vértices se consideran tres valores distintos para b (5, 10 y 20). Finalmente, para los problemas de la clase cm se consideran
también tres valores distintos para el parámetro de capacidad b (200, 400 y 800).
El algoritmo propuesto se ejecutó 5 veces para cada uno de los problemas considerados. En el Cuadro 1 se muestran los resultados obtenidos con algoritmo que combina
las metodologías de búsqueda tabú y búsqueda dispersa. La información presentada es
la siguiente. Las columnas con el encabezado Grupo muestran el grupo de problemas.
Las columnas con el encabezado DesvM, muestran la desviación porcentual promedio
de la mejor solución obtenida (en las 5 ejecuciones) con respecto al valor de la mejor
solución conocida. Las columnas con el encabezado DesvP, muestran la desviación
porcentual promedio del valor medio de las soluciones obtenidas con respecto al valor
de la mejor solución conocida.
En términos de esfuerzo computacional, los tiempos medios de cpu requeridos para
la ejecución del algoritmo combinado (en segundos) son 9.02, 12.09, 60.71, 71,15,
15.41, 69.02 y 330.21 para los grupos de problemas tc40, te40, tc80, te80, cm50,
cm100 y cm200, respectivamente. Se puede observar que con excepción de los grupos tc40 y cm200, el procedimiento de búsqueda dispersa logra mejorar las soluciones
obtenidas con el procedimiento de búsqueda tabú. En particular, se observa un mayor
porcentaje de mejora para los problemas de la clase te.
3
4. Conclusión
En este trabajo se estudia el problema del árbol de expansión capacitado de coste mínimo. En particular, se propone un método basado en una combinación de las metodologías
de búsqueda tabú y búsqueda dispersa.
En el procedimiento de búsqueda tabú se considera una función objetivo que se
adapta utilizando información histórica de proceso de búsqueda. Esto permite implementar una estrategia de oscilación estratégica para obtener un mayor grado de flexibilidad durante le proceso de búsqueda.
En el procedimiento de búsqueda dispersa se combinan pares de soluciones utilizando un procedimiento de eliminación de aristas y compactación del grafo unión de
las soluciones a combinar.
De acuerdo con los resultados obtenidos se observa que con la metodología propuesta se obtienen soluciones de buena calidad con un esfuerzo computacional razonable.
Referencias
[1] Ahuja, R.K., Orlin, J.B. y Sharma, D., A composite very large-scale neighborhood
structur for the capacitated minimum spanning tree problem, Operations Research
31, 186-194, 2003.
[2] Amberg, A., Domeschke, W. y VoS, S., Capacitated minimum spanning tree: algorithms using intelligent search, Combinatorial Optimization: Theory and Practice
1, 9-33, 1996.
[3] Esau, D. y Williams, K.C., On teleprocessing system design. Part II, IBM System
Journal 5, 142-147.
[4] Gavish, B., Topological design of centralized computer networks: formulations and
algorithms , Networks 12, 355-377, 1982.
[5] Gavish, B., Formulation and algorithms for the capacitated minimal directed tree
problem , Journal of the ACM 30, 118-132, 1983.
[6] Gouveia, L., Determinacão da arvore de suporte de custo mínimo com restricões
de capacidade: formulacões e algoritmos, Tesis Doctoral, Universidad de Lisboa,
Portugal, 1991.
[7] Papadimitriou, C., The complexity of the capacitated tree problem, Networks 8,
217-230, 1978.
[8] Sharaiha, Y.M., Gendreau, M., Laporte, G. y Osman, I.H., A tabu search algorithm
for the capacitated shortest spanning tree problem, Networks 29, 161-167, 1997.
[9] Souza, M.C., Duhamel, C. y Ribeiro, C.C., A GRASP heuristic for the capacitated minimum spannig tree problem using memory-based local search strategy,
In Metaheuristics: Computer Decision-Making, M.G.C. Resende y J. Souza (eds.)
627-658, Kluwer, 2003.
4