Optimización de la confiabilidad global de redes generales mediante la asignación de arcos

Abstract

In general networks, the redundancy allocation problem (RAP) consists in allocating a number of links to each connection of a network, whether to minimize the cost of the system (subject to a reliability constraint), or to maximize the network reliability (subject to a total budget). Considering the computational complexity for the network reliability calculation and for the solution of the optimization problem, in this work we propose and compare three heuristics, which use efficient techniques for network connectivity evaluation, network reduction, reliability evaluation and solution finding. In computational experiments, the heuristic with the reliability upper bound outperformed the other two heuristics in terms of running time.

En redes generales, el problema de asignación de redundancias (redundancy allocation problem, RAP) consiste en determinar el número de arcos que se deben asignar a cada conexión de la red, bien sea para minimizar el costo del sistema, sujeto a una restricción de confiabilidad, o para maximizar la confiabilidad de la red, dado un presupuesto total. Considerando la complejidad computacional para el cálculo de la confiabilidad de la red, y para la solución del problema de optimización, en este trabajo se proponen y comparan tres heurísticos que utilizan técnicas eficientes para la evaluación de la conectividad de redes, la reducción de la red, la evaluación de la confiabilidad y la búsqueda de soluciones. En experimentos computacionales, el heurístico con la cota superior de confiabilidad superó a los otros dos heurísticos en términos de tiempos de ejecución.