Determinação dos k Caminhos Mínimos Disjuntos Mais Confiáveis em Uma Rede de Fluxo Multiestado
DOI:
https://doi.org/10.5540/03.2026.012.01.0275Palavras-chave:
Caminhos Mínimos Disjuntos, Redes de Fluxo Multiestado, Confiabilidade, AlgoritmosResumo
A determinação de k caminhos mínimos disjuntos (CMDs) em uma rede de fluxo multi-estado (RFM) desempenha um papel fundamental na garantia da confiabilidade e disponibilidade de sistemas reais, como telecomunicações, transporte e redes de distribuição. Embora estudos anteriores tenham se concentrado na identificação do número máximo de CMDs entre dois nós em um grafo, a confiabilidade dos caminhos selecionados em uma RFM tem sido pouco explorada. Neste trabalho, introduzimos o problema de determinar os k CMDs mais confiáveis capazes de transmitir d unidades de fluxo de uma fonte a um destino dentro de T unidades de tempo. Além disso, propomos um algoritmo para sua resolução e demonstramos sua correção.
Downloads
Referências
Y. L. Chen e Y. H. Chin. “The quickest path problem”. Em: Computers & Operations Research 17.2 (1990), pp. 153–161.
M. Forghani-elahabad. “1 Exact reliability evaluation of multistate flow networks”. Em: Systems Reliability Engineering. De Gruyter, 2021, pp. 1–24.
M. Forghani-elahabad. “3 The Disjoint Minimal Paths Reliability Problem”. Em: Operations Research. CRC Press, 2022, pp. 35–66.
M. Forghani-elahabad e O. M. Alsalami. “Using a Node–Child Matrix to Address the Quickest Path Problem in Multistate Flow Networks under Transmission Cost Constraints”. Em: Mathematics 11.24 (2023), p. 4889.
M. Forghani-elahabad e N. Mahdavi-Amiri. “A New Algorithm for Generating All Minimal Vectors for the q SMPs Reliability Problem With Time and Budget Constraints”. Em: IEEE Transactions on Reliability 65.2 (2015), pp. 828–842.
M. Forghani-elahabad e N. Mahdavi-Amiri. “An efficient algorithm for the multi-state two separate minimal paths reliability problem with budget constraint”. Em: Reliability Engineering & System Safety 142 (2015), pp. 472–481.
M. Forghani-elahabad e N. Mahdavi-Amiri. “An improved algorithm for finding all upper boundary points in a stochastic-flow network”. Em: Applied Mathematical Modelling 40.4 (2016), pp. 3221–3229.
M. Forghani-elahabad e N. T. Matos. “Buscando os dois caminhos mínimos disjuntos mais confiáveis em uma rede de fluxo multiestado com restrição de tempo”. Em: Proceeding Series of the Brazilian Society of Computational and Applied Mathematics 11.1 (2025), pp. 1–7.
M. Forghani-elahabad e W. C. Yeh. “An improved algorithm for reliability evaluation of flow networks”. Em: Reliability Engineering & System Safety 221 (2022), p. 108371.
Z. Hao, W. C. Yeh, Z. Liu e M. Forghani-elahabad. “General multi-state rework network and reliability algorithm”. Em: Reliability Engineering & System Safety 203 (2020), p. 107048.
J. Kleinberg e E. Tardos. Algorithm design. Pearson Education India, 2006.
C. L. Li, S.T. McCormick e D. Simchi-Levi. “Finding disjoint paths with different path-costs: Complexity and algorithms”. Em: Networks 22.7 (1992), pp. 653–667.
Y. K. Lin. “Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network”. Em: Computers & Operations Research 30.4 (2003), pp. 567–575.
Y. F. Niu, Xiao-Yu Wan, X. Z. Xu e Dong Ding. “Finding all multi-state minimal paths of a multi-state flow network via feasible circulations”. Em: Reliability Engineering & System Safety 204 (2020), p. 107188.
Y. F. Niu, J. H. Wei e X. Z. Xu. “Computing the Reliability of a Multistate Flow Network with Flow Loss Effect”. Em: IEEE Transactions on Reliability (2023).
D. Ronen e Y. Perl. “Heuristics for finding a maximum number of disjoint bounded paths”. Em: Networks 14.4 (1984), pp. 531–544.
W. Samotij. “Counting independent sets in graphs”. Em: European journal of combinatorics 48 (2015), pp. 5–18.
J. Vygen. “NP-completeness of some edge-disjoint paths problems”. Em: Discrete Applied Mathematics 61.1 (1995), pp. 83–90.
J. Weiner, T.E. Andreas, X. Li, Y. Sun e K. Deb. “Solving the maximum edge disjoint path problem using a modified Lagrangian particle swarm optimisation hybrid”. Em: European Journal of Operational Research 293.3 (2021), pp. 847–862.
W. C. Yeh e M. Forghani-elahabad. “An efficient algorithm for sorting and duplicate elimination by using logarithmic prime numbers”. Em: Big Data and Cognitive Computing 8.9 (2024), p. 96.
W. C. Yeh e M. Forghani-elahabad. “An efficient parallel approach for binary-state network reliability problems”. Em: Annals of Operations Research (2024), pp. 1–22.
