A Monte Carlo-based algorithm for the quickest path flow network reliability problem

Cheng‐Fu Huang

doi:10.1007/s10479-024-06377-8

A Monte Carlo-based algorithm for the quickest path flow network reliability problem

2024-11-08

0

PRE

AI

C

Cheng‐Fu Huang *

DOI：10.1007/s10479-024-06377-8

原文链接

原文求助

摘要

En 中文

The importance of supply chain resilience has been highlighted in recent years, particularly during events such as wars and pandemics. Supply chain resilience is typically defined as the ability of a system to either return to its original state or evolve to a new, more advantageous state following a disruption. Therefore, it is imperative to evaluate the performance of real-world systems to mitigate risks or enhance capabilities. Computer systems are integral to supply chain operations and form the backbone of its overall functioning. To accurately reflect these computer systems, they are represented as Multi-State Flow Networks (MSFN). This paper evaluates the probability that an MSFN can transmit a given amount of demand through a minimal path (MP) connecting the source and terminal within a fixed time. This specific computational issue, referred to as the quickest path (QP) flow network reliability problem, is classified as NP-hard. Alternatively, the Monte Carlo simulation is developed to estimate the QP network reliability problem. The proposed Monte Carlo-based algorithm involves the random generation of a capacity vector representing the current state of the network. The generated capacity is then evaluated to determine whether the given amount of demand can be satisfied within the given time constraint. This evaluation takes into account the transmission times associated with all MP. To demonstrate the effectiveness and efficiency of the proposed Monte Carlo-based algorithm, extensive tests are conducted on a substantial practical network and parallel MSFN. In particular, the proposed Monte Carlo-based algorithm quickly provides precise solutions to the QP flow network reliability problem, even in situations characterized by a significant number of MP and arcs, numbering in the hundreds.

Keyword:

Supply chain resilience

Computer systems

Network reliability

Quickest path (QP)

Multi-state flow network (MSFN)

Monte Carlo simulation

A Monte Carlo-based algorithm for the quickest path flow network reliability problem

摘要

期刊

机构

引用论文