An efficient alternative to the exact evaluation of the quickest path flow network reliability problem. (December 2016)

• Record Type: Journal Article
• Authors: El Khadiri, M.; Yeh, W.-C.
• Is Part Of: Computers & operations research. Volume 76(2016)
• Page Start: 22
• Page End: 32
• Publication Date: 2016-12
• Subjects: 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; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.06.010
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Abstract : Highlights: 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.