An efficient alternative to the exact evaluation of the quickest path flow network reliability problem

• Published in: Computers & operations research 2016-12, Vol.76, p.22-32
• Main Authors: El Khadiri, M., Yeh, W.-C.
• Format: Article
• Language: English
• Subjects: Arc capacity; Arc lead time; Central processing units; Computer simulation; CPUs; Flow network; Inclusion–Exclusion; Mathematical analysis; Mathematical models; Minimal Path; Monte Carlo simulation; Network flow problem; Networks; Path capacity; Path lead time; Path transmission time; Polynomials; Quickest path; Reliability; Run time (computers); Stochastic models; Studies; System reliability
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2016.06.010

In this paper we consider the evaluation of the probability that a stochastic flow network allows the transmission of a given amount of flow through one path, connecting the source and the sink node, within a fixed amount of time. This problem, called the quickest path flow network reliability problem, belongs to the NP-hard family. This implies that no polynomial algorithm is known for solving it exactly in a CPU runtime bounded by a polynomial function of the network size. As an alternative, we propose to perform estimations by a Monte–Carlo simulation method. We illustrate that the proposed tool evaluates, with high precision and within small CPU runtime, configurations which cannot be handled, in reasonable CPU runtime, by means of a well-known exact method. •Efficient alternative to the NP-hard exact evaluation of the quickest path reliability problem.•Fast and accurate Monte–Carlo estimator when the reliability is not very close to 1.•For a fixed sample size, CPU runtime is a linear function of the network parameters.