基于最小路集（割集）向量的多状态网络可靠性快速评估算法研究

In many real-world network systems, the network must not just be connected but function at a certain performance level. We refer to this kind of network as multistate network. Despite the increasing complexity of modern networks, the size of the network that can be analyzed by existing methods is still rather modest. This is expected since the network reliability analysis problem is NP-hard. Consequently, research aimed at improving the efficiency of reliability evaluation is needed. The proposed research proposal aims to improve the overall efficiency of the indirect method based on minimal path/cut vectors, namely d-MPs/d-MCs. Firstly, we propose an algorithm to search for all d-MPs without duplications for two-terminal multistate networks. Then, we extend the two-terminal networks to networks with multi sources and sinks, and propose an algorithm to search for d-MPs based on the components of networks. Given all d-MPs/d-MCs, an ordering heuristics method based on Multi-State Multi-Valued Decision Diagram are proposed for the exact evaluation respectively. Finally, given that some real-world multistate networks are too large to be evaluated exactly, d-MPs/d-MCs ordering heuristics and MPs/MCs ordering heuristics are proposed for the reliability bound evaluation. With efficient reliability evaluation algorithms and methods, the research results out of this project provide the reliability engineers and facility managers a more powerful tool for the design and maintenance of more complex networks.

在现实世界中很多网络不仅要求能够连通，而且要求部件能够传输一定流量，而整个网络具备一定的吞吐量。这种网络被称为多状态网络。由于其可靠度的求解时间随着网络规模和复杂程度呈指数式增长，迫切需要更高效的求解算法。本项目聚焦基于最小路集（割集）向量的多状态网络可靠度求解方法，首先针对多状态网络最小路集向量的搜索问题，分别研究单源单汇多状态网络最小路集向量免重复搜索算法和多源多汇多状态网络最小路集向量搜索算法；在此基础上，研究基于多元多值决策图法求解多状态网络可靠度的启发式排序算法，并根据实际网络规模过大的情况，研究加快多状态网络可靠度上下界收敛速率的启发式排序算法。通过以上研究有效降低该方法在搜索最小路集向量、求解精确可靠度和求解近似可靠度的复杂度，大幅提高该方法的算法效率和可求解网络的规模，为管理者在多状态网络的设计、建造、运行和维护过程中提供强有力的支撑，确保多状态网络的稳定、可靠运行。

多状态网络可靠性模型广泛应用于现实中的网络系统，如天然气、通讯、电力传输系统和交通系统等，理论上其可靠度求解是“NP”难问题。因此，寻求高效的算法来求解多状态网络的可靠度是当前多状态网络可靠性领域迫切需要解决的难点问题。本项目聚焦于基于最小路集向量（d-MP）的多状态网络可靠度求解方法，攻克当前制约该方法在搜索最小路集向量（d-MP）、求解精确可靠度、求解可靠度上下界的瓶颈问题，并构建一系列高效算法，大幅降低多状态网络可靠度求解的时间和空间复杂度。主要内容：1）针对搜索最小路集向量（d-MP）时产生的重复项问题，从网络结构出发，重点研究了d-MP重复项产生的机制，并在此基础上，提出了最小路集免重复搜索算法；2）针对多状态网络可靠度精确求解问题，提出了一个改进的状态空间分解方法（SSD），通过改进的启发式规则来选择合适的d-MP用以分解每组未指定状态的SSD改进算法，更进一步，在算法中引入了并行机制和新的启发式规则，进一步提高了算法效率；3)针对多状态网络可靠度近似求解问题，通过加入具有预先指定值的启发式规则过滤不重要的状态集，为多状态网络提供上下限可靠性序列值。以上算法研究，大幅提升了可求解的多状态网络规模，可为实际的多状态网络优化设计、平稳运行和维护管理提供强大的支撑，对确保网络的可靠、稳定地运行具有重要的现实意义和工程应用价值。