Métodos exacto y matemático-heurístico para la localización de conmutadores
M. Landete Ruiz, A. Marín Pérez, J. L. Sainz-Pardo Auñón
Los conmutadores son nodos con grado mayor que dos. En esta exposición se analiza el problema de localización de conmutadores sobre el árbol generador de un grafo. Localizar un conmutador implica dos tipos de costes, los costes de conexión usuario-conmutador y el coste de instalación, siendo la finalidad el minimizar la suma de ambos.
Este problema de localización es una generalización de los problemas: 'árbol de expansión con menor número de vértices de ramificación' y 'árbol de expansión con menor suma de grados'. Se propone un método exacto empleando un algoritmo de descomposición en bloques de forma que, para cada bloque, se resuelve un modelo de programación entera. En aquellos grafos donde no es posible la descomposición en bloques, se propone un método matemático-heurístico basado en la resolución exacta de un grafo reducido obtenido al suprimir algunas aristas del grafo original y que por tanto se beneficia del estudio hecho en el caso de la descomposición en bloques.
Palabras clave / Keywords: árboles, vértices de corte, bloques, conmutador
Programado
Sesión M07 Grafos, Distribuciones, rutas y transporte
30 de mayo de 2018 17:10
Sala 1
Otros trabajos en la misma sesión
F. Salas Molina, D. Pla-Santamaria
L. Carpente, J. Costa, M. Fontenla, I. García Jurado, S. Lorenzo Freire, G. Novoa
J. M. Belenguer Ribera, E. Benavent, J. M. Daza-Escorcia
Últimas noticias
-
04/06/18
Certificados -
13/04/18
Resumen del programa y Programa detallado -
22/03/18
Descuentos en medios de trasporte para congresistas y acompañantes -
01/02/18
Ampliación del plazo de tarifa superreducida -
19/01/18
Ampliación de plazos -
15/01/18
Programación para el día 29 de mayo -
15/01/18
Conferenciantes plenarios -
12/01/18
Sede: Palacio de Congresos -
24/12/17
Sesión plenaria en memoria del Profesor Pedro Gil -
24/12/17
Corrección bases del Premio Ramiro Melendreras