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

作者：El Khadiri M^*; Yeh W C

来源：Computers & Operations Research, 2016, 76: 22-32.

DOI：10.1016/j.cor.2016.06.010

• Arc capacity
• Arc lead time
• Flow network
• Inclusion-Exclusion
• Minimal Path
• Monte-Carlo simulation
• Path capacity
• Path lead time
• Path transmission time
• Quickest path
• Reliability

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.

• 出版日期2016-12
• 单位清华大学