Optimización de redes con arcos de baja confiabilidad adicionando arcos redundantes

Abstract

This thesis develops a methodology to optimize the reliability of a complex network whose nodes are not necessarily in series or in parallel and their arcs have low known reliability. Network reliability is improved by using redundant arcs with a budgetary restriction. Two heuristic optimization algorithms are used and compared to solve this redundancy allocation problem: a genetic algorithm (AG) and an algorithm proposed by the doctor Noel Artiles and developed by the author based on sequential integer linear programming (PLES). Since the exact evaluation of the objective problem is very difficult, it is evaluated by Monte Carlo simulation. Two factorial designs were developed to compare the maximum network reliability (RRT) and the execution time (te) of the heuristics optimization, AG and PLES. In conclusion, the maximum network reliability only was affected by the network size (n), therefore both heuristics maximize the network reliability (RRT) with the same efficiency. Furthermore, the experiment results shown that the proposed heuristic PLES is a faster algorithm than AG for all the network sizes.

En esta tesis se desarrolla una metodología para optimizar la confiabilidad de una red compleja cuyos nodos no pueden ser agrupados en serie y paralelo y sus arcos tienen confiabilidades bajas conocidas. La confiabilidad de la red es mejorada adicionando arcos en redundancia con una restricción de presupuesto. Dos heurísticos de optimización son usados y comparados para resolver este problema de asignación de redundancia: un algoritmo genético (AG) y un algoritmos propuesto por el doctor Noel Artiles y desarrollado por la autora basado en programación lineal entera secuencia (PLES). La evaluación exacta de la función objetivo de este problema es muy difícil, por lo tanto ésta es evaluada utilizando simulación de Monte Carlo. Se desarrollaron dos experimentos factoriales con el fin de comparar la confiabilidad máxima alcanzada (RRT) y el tiempo de ejecución (te) de los dos heurísticos de optimización, AG vs. PLES. A partir de estos experimentos se concluyó que la confiabilidad máxima alcanzada sólo se veía afectada por el tamaño de la red (n) y por lo tanto los dos heurísticos maximizan la confiabilidad de la red (RRT) con igual eficiencia. Adicionalmente, los resultados de los experimentos también permitieron concluir que el heurístico propuesto PLES resultó ser un algoritmo significativamente más rápido que AG para todos los tamaños de red.