Title: A simulation method for network performability estimation using heuristically computed pathsets and cutsets
Authors: Franco Robledo; Pablo Sartor
Addresses: Departamento de Investigación Operativa, Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565, Montevideo, Uruguay ' Departamento de Investigación Operativa, Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Julio Herrera y Reissig 565, Montevideo, Uruguay
Abstract: Consider a set of terminal nodes K that belong to a network whose nodes are connected by links that fail independently with known probabilities. We introduce a method for estimating a performability measure that depends on the hop distance between terminal nodes. The new measure generalises the diameter-constrained network reliability measure. We propose a Monte Carlo method with significant variance reduction compared to crude Monte Carlo. It is based on using edge sets named d-pathsets and d-cutsets for reducing the variance of the estimator. These edge sets, considered as a priori known in previous literature, heavily affect the attained performance; we hereby introduce and compare a family of heuristics for their selection. Numerical examples are presented, showing the significant efficiency improvements that can be obtained by chaining the edge set selection heuristics to the proposed Monte Carlo sampling plan.
Keywords: metaheuristics; Monte Carlo simulation; rare events; networks; network reliability; performability; bounded length; diameter constraints; path sets; cut sets; sampling planning.
International Journal of Metaheuristics, 2013 Vol.2 No.4, pp.370 - 391
Received: 08 Dec 2012
Accepted: 27 Sep 2013
Published online: 24 Dec 2013 *