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

• 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.

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.