Using a Node–Child Matrix to Address the Quickest Path Problem in Multistate Flow Networks under Transmission Cost Constraints

Majid Forghani-elahabad () and Omar Mutab Alsalami
Additional contact information
Majid Forghani-elahabad: Center of Mathematics, Computing, and Cognition, Federal University of ABC, Santo André 09210-580, SP, Brazil
Omar Mutab Alsalami: Department of Electrical Engineering, College of Engineering, Taif University, P.O. Box 11099, Taif 21944, Saudi Arabia

Mathematics, 2023, vol. 11, issue 24, 1-15

Abstract: The quickest path problem in multistate flow networks, which is also known as the quickest path reliability problem (QPRP), aims at calculating the probability of successfully sending a minimum of d flow units/data/commodity from a source node to a destination node via one minimal path (MP) within a specified time frame of T units. Several exact and approximative algorithms have been proposed in the literature to address this problem. Most of the exact algorithms in the literature need prior knowledge of all of the network’s minimal paths (MPs), which is considered a weak point. In addition to the time, the budget is always limited in real-world systems, making it an essential consideration in the analysis of systems’ performance. Hence, this study considers the QPRP under cost constraints and provides an efficient approach based on a node–child matrix to address the problem without knowing the MPs. We show the correctness of the algorithm, compute the complexity results, illustrate it through a benchmark example, and describe our extensive experimental results on one thousand randomly generated test problems and well-established benchmarks to showcase its practical superiority over the available algorithms in the literature.

Keywords: quickest path reliability problem; network reliability; multistate flow networks; minimal paths; algorithms (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/24/4889/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/24/4889/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:24:p:4889-:d:1295171

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().