Academic Journal of Science and Technology ISSN: 2771-3032 | Vol. 5, No. 2, 2023 149 Summary of Research on Reliability Evaluation Methods for Distribution Networks Guolin Wu School of Modern Posts, Chongqing University of Posts and Telecommunications, Chongqing 400065, China Abstract: Existing research has shown that highly reliable network systems can not only significantly reduce their own operation and maintenance costs, but also greatly improve service efficiency. Quick and accurate qualitative analysis and quantitative evaluation of the reliability of distribution networks are essential for both correctly estimating the performance of actual networks and improving network design. This overview will summarize the existing research from four aspects: the current research status of network reliability, logistics network reliability, network reliability under cost constraints, and network reliability under transportation distance constraints, laying a foundation for research on reliability evaluation methods for distribution networks. Keywords: Network reliability, Polymorphic networks, Distribution networks, Cost constraints, Diameter constraints. 1. Introduction With the continuous progress and development of economy and technology, modern logistics systems, as important supporting systems to ensure the normal operation of social and economic life, have made significant progress and development in automation and intelligence. The use of various modern technologies such as automatic identification technology, artificial intelligence technology, and GIS technology has made logistics systems increasingly intelligent, informative, global, and complex, These characteristics also put forward stricter requirements for the reliable performance of logistics system products and services. As an intermediate hub supporting the normal operation of logistics systems, the reliability of logistics distribution has also become a focus issue for enterprises and researchers. Failure events in logistics and distribution links can lead to disruption or even collapse of the entire supply chain with limited affordability. Especially for logistics systems with more stringent distribution requirements, the reliability of logistics distribution services will greatly affect the basic attributes of system operation such as efficiency, cost, and service. Logistics distribution refers to an organic whole with specific functions, which is composed of several factors that interact with each other, such as the goods to be transported, various links of transportation, relevant equipment, personnel, and communication links, within a certain time and space. According to the relevant definition in China's national standard "Logistics Terminology", distribution refers to "logistics activities in which items are selected, processed, divided, and assembled according to customer requirements within an economically reasonable area and delivered to designated locations on time." It can be seen that reliable and efficient distribution services are an important guarantee for maintaining the stable operation of the logistics system. In modern supply chain management, increasingly fierce market competition has made more and more logistics enterprises realize that the reliability of logistics distribution services is a crucial basic condition to ensure smooth production. For example, logistics distribution strategies such as "one day delivery" and "next day delivery" in JD Mall cannot be separated from the efficient and reliable guarantee provided by JD Group's self built logistics network system. Therefore, studying the reliability of logistics distribution networks has important practical significance. Mathematical modeling is conducted based on minimal capacity vector sets. Based on considering transportation cost and transportation distance constraints, a reliability evaluation method for multi-state logistics distribution networks is studied to systematically evaluate the impact of distribution network reliability. The existing classical theories and applications provide a wide range of reference significance, so it is proposed to comb the network reliability from different perspectives to provide reference for future research content. 2. Current Status of Network Reliability Research In 1982, Japanese scholar, Mine [1], proposed the concept of connectivity reliability, which reflects the probability of maintaining connectivity between two nodes in a transportation network. Generally, only two states of connectivity (0) and failure (1) are studied. Subsequently, based on Mine, Iida [2] expanded the connectivity between two points to k point and the reliability of the entire network. We also refer to this network connectivity reliability as two state network reliability. In real life, there are often more than two performance states for various network systems. Therefore, it is difficult to accurately describe the reliability of various network systems by relying solely on two-state networks. Therefore, with the development and wide application of reliability theory, scholars at home and abroad have begun to pay attention to more complex systems under various conditions. The research object of modern reliability engineering has undergone a transition from simple to complex, from component to system, and from single state to multi state, presenting new characteristics such as complexity, uncertainty, integration, and polymorphism. Reliability research on networks with these characteristics is known as polymorphic network reliability. Because polymorphic networks can better describe the characteristics of distribution networks in real life, this paper treats the distribution network 150 topology as a polymorphic network with complex behavioral characteristics of road sections, and the reliability evaluation of polymorphic networks naturally becomes the main focus of this study. The reliability evaluation methods for polymorphic networks are typical NP hard problems. Therefore, scholars at home and abroad have proposed many methods to evaluate network reliability. These methods can be mainly divided into analytical methods and simulation methods. The simulation method mainly uses the Monte Carlo method [3] to study network reliability issues, mainly estimating the probability of a random event through the frequency of its occurrence. This method can only obtain an approximate value of network reliability in most cases, and requires a high accuracy in sample selection. The core of analytical methods is to set efficient structural functions to obtain network reliability values. Analytical methods mainly include accurate algorithms and approximate algorithms, including the random process method [4,5], the multivalued decision graph method, the general generating function method, and the polymorphic minimum capacity vector method [5,6]. The core of polymorphic minimum capacity vector method is to construct a mathematical model of polymorphic minimum capacity vector satisfying constraints based on network topology. As one of the research hotspots in the field of reliability, the polymorphic minimum capacity vector method is mainly applied to evaluate the reliability of polymorphic networks [6], so this method is also the main focus of this study. Given the capacity level d, the reliability Rd of a polymorphic network refers to the probability that the network can successfully transport d units of traffic from the source point s to the sink point t [7]. The main method for calculating this reliability index is through the polymorphic minimum capacity vector (d-MCV) with the capacity level d. Therefore, solving the d-MCV in a network is the main goal of solving the reliability of a polymorphic network. Lin [7] and others first proposed the concept and mathematical model of candidate d-MCV, which is mainly constructed by assuming that the flow in the network satisfies the flow conservation law. According to the maximum flow network theory, Yeh [8] proposed a candidate d-MCV solution model with fewer constraints and variables than those of Lin [7] and others. Yeh [8] verified the effectiveness of this model through theoretical analysis. On the basis of the above model, Niu et al. [9] constructed a candidate d-MCV mathematical model with stricter constraints by introducing the concept of the lower limit of edge capacity. This method does not need to know all the minimum capacity vector information in the network, thereby reducing the time complexity of the above model. Based on the model of Lin [7] and others, Chen [10] and others proposed an improved algorithm for solving d- MCV using a fast enumeration method. Baiet al. [11] proposed a recursive algorithm for obtaining reliability values at all capacity state levels. It is worth noting that the candidate d-MCV is not a real d-MCV. Therefore, Lin [7] and others proposed a comparison method to determine whether the candidate d-MCV is a real d-MCV. Yeh [12] concluded through complexity analysis that the comparison method is very inefficient in verifying the candidate d-MCV. Therefore, a candidate d-MCV identification method called the loop test method was proposed. These two methods are also the main methods for verifying candidate d-MCVs. 3. Research Status of Logistics Network Reliability As an "artery" supporting the internal and external circulation of social economy, logistics distribution networks are fundamental logistics facilities that ensure the smooth flow of goods and achieve their temporal and spatial value, and are crucial to our society and economy. In theoretical research, distribution networks are often modeled as a polymorphic network model in which each side has a mutually independent, finite, nonnegative integer random capacity. In the multi-state network model, distribution network reliability refers to the probability that the network can deliver a certain amount of goods from supply location s to demand location t. Jane et al. [13] constructed a polymorphic network model to represent the logistics network, and proposed a hybrid algorithm related to capacity scaling algorithm and decomposition algorithm to directly calculate the reliability of the logistics network. In addition, some scholars [14-19] have also proposed algorithms to calculate logistics network reliability based on minimum capacity vectors (minimum capacity vectors under cost constraints) that meet demand d and budget b. 4. Current Status of Network Reliability Research Under Cost Constraints Reliability of distribution network service capability with cost constraints refers to the probability that the network can successfully deliver d units of goods from the origin to the destination and the total distribution cost does not exceed the given budget constraint b, expressed as Rel(d,b). The simplest method for calculating Rel(d,b) is the exhaustive method, which requires enumeration of each capacity vector in the capacity vector space one by one, so it has a high time complexity and is only suitable for small-scale distribution networks. Currently, the most commonly used method for calculating Rel(d,b) is to use a cost constrained minimum capacity vector [19,20], abbreviated as (d,b)-MCV. If a capacity vector X is satisfied, the network can successfully deliver d units of goods demand from the origin to the destination under X, and the total delivery cost does not exceed the given budget constraint b. Any other capacity vector smaller than X cannot meet both conditions, then X is called (d,b)-MCV. When all the (d,b)-MCVs of the network are obtained, Rel(d,b) can be calculated using the disjoint sum method [21,22] or the state space decomposition method [23,24]. Therefore, solving the (d,b)-MCV of a network is the core of computing Rel(d,b), and is also the focus of existing research. Currently, researchers have proposed some methods to search for cost constrained minimum capacity vectors. Based on key factors such as demand levels, budget constraints, and capacity conditions, Lin [20] constructed a search model for candidate (d,b)-MCVs using the network's minimum capacity vector. The feasible solution of the model is called candidate (d,b)-MCVs, and the candidate (d,b)- MCVs need to be further validated to determine whether they are true (d,b)-MCVs, as duplicate (d,b)-MCVs may appear in the results of the model, that is, multiple identical (d,b)-MCVs. Repeating (d,b)-MCVs only increases the complexity of reliability calculations without any impact on reliability values. Therefore, it is necessary to remove all duplicate(d,b)- MCVs so that the results no longer contain duplicate (d,b)- 151 MCVs. Lin [19] considered both the polymorphism of the capacity of edges and the polymorphism of the capacity of points when constructing the (d,b)-MCV search model; Moreover, Lin [20] proposes to use a comparison method to determine whether the candidate (d,b)-MCV is an (d,b)-MCV, and the comparison method can also remove the duplicate (d,b)-MCVs that occurs. Yeh [15] believes that the comparison method is not efficient in verifying candidate(d,b)-MCVs, and proposes a directed loop verification method to verify whether the candidate (d,b)- MCVs are genuine (d,b)-MCVs. Without knowing all the minimal capacity vectors of the network, Niu et al. [9] constructed a search model using the properties of (d,b)-MCV, but this model is only applicable to directed networks. Recently, Forghani-elahabad et al. [17] proposed a more efficient method to identify repetitive (d,b)-MCVs, and through numerical analysis, it was found that the solution efficiency of this algorithm is superior to other algorithms. In summary, although current researchers have proposed some algorithms for solving (d,b)-MCV, these algorithms still face two main challenges. First, it is very difficult to solve candidate (d,b)-MCV models; Secondly, there are still significant computational efficiency bottlenecks in the identification of repetitive (d,b)-MCVs. 5. Current Status of Network Reliability Research Under Transportation Distance Constraints In network models, the transportation distance constraint is often represented by the diameter constraint D, which represents the maximum distance from the source point s to the sink point t in the network. Currently, research on the reliability of networks with diameter constraints is mostly focused on two state networks. Peting et al. [25] first defined a diameter constraint, which is to set a positive integer D, so that the path length of all nodes in the network does not exceed D, and the reliability Rel(d,D) of a two-state network under the diameter constraint is the probability that all nodes in the network have at least one connected path that is not greater than D. In diameter limited networks, redundant edges or nodes may be generated. Therefore, in order to calculate Rel(d,D), Peting [26] and others proposed that the edges (i.e., redundant edges) in the network that only exist in st paths larger than D should be detected first and deleted from the network. However, the method proposed by Peting is only a sufficient condition for detecting redundant edges. Literature [27] proposed a method to adjust the sampling space based on using path structures called D-pathsets and D- cuts, and further developed a Monte Carlo method to obtain an approximate solution for the reliability of a two-state network. Wang et al. [28] proposed the expected path problem with diameter constraints and re evaluated the reliability of a two state network when nodes are unreliable. For K-terminal reliability under diameter constraints, Cancela et al. [29,30] defined the (s, K)-diameter as the maximum distance between the source node s and all nodes in the set K, and proposed a simple method to calculate the network reliability when the (s, K)-diameter is not greater than the given value D. Nesterov et al. [31] proposed an improved factorization method for computing network reliability under diameter constraints based on Page [32] parallel method for computing network reliability and Cancela et al. [30] method, and demonstrated the efficiency of the algorithm. For K-terminal reliability, he obtained a judgment theorem for independent edges and independent points of K-terminal active networks with diameter constraints, and then proposed a simplified algorithm for independent edges and a factorization algorithm for diameter constraints. Finally, an algorithm for solving the reliability upper bound of K-terminal active networks is presented. Zhang et al. [33] studied the reliability of social networks, using diameter constraints to describe neighborhood relationships in society, and studied the neighborhood relationship and reliability issues between user v and selected group K. It is noted that the two state network model only considers two extreme network states, so it is not suitable for reliability analysis of distribution networks. Under the polymorphic network model, Zhang et al. [34] studied the definition of network reliability Rel(d,D) under diameter constraints, and provided an algorithm for calculating Rel(d,D), which is implemented by deleting redundant edges in the polymorphic network. However, there are two problems in this study. First, the definition of network reliability under diameter constraints only considers the distance of the st-path in the network structure, while ignoring the actual transmission distance of the flow, resulting in insufficient rigor in the reliability index. Secondly, the proposed method only considers the presence of redundant edges in the network, and does not consider the coupling relationships between edges, nodes, and nodes in the network. As a result, the required st-path does not always meet the diameter constraint. Therefore, the calculated reliability value cannot accurately reflect the logistics service capacity of the distribution network under transportation distance constraints. 6. Existing Problems In recent years, domestic and foreign research on network reliability has achieved a wealth of theoretical and practical guiding research results, providing some inspiration and reference for the development of this article from the perspective of modeling and solving methods. However, the following issues need to be further explored in the study of evaluation methods for the reliability of distribution networks. On the one hand, when evaluating the reliability of distribution networks with transportation cost constraints, although current researchers have proposed some algorithms to solve (d,b)-MCVs, these algorithms still face two main challenges. First, it is very difficult to solve candidate (d,b)- MCV models; Secondly, there are still significant computational efficiency bottlenecks in the identification of candidate (d,b)-MCVs. It has been noted that the globalization and intelligent development of the logistics market have led to an increasingly large scale and complex network composition of distribution networks. Due to the NP hard attribute of reliability evaluation for logistics networks with transportation cost constraints, the increase in network size will lead to an exponential increase in the time consumed by the algorithm and the cost scale. Therefore, in order to adapt to the continuous expansion of the logistics market, there is an urgent need for practical and efficient algorithms to be applied to the reliability evaluation and analysis of distribution networks under transportation cost constraints. On the other hand, when evaluating the reliability of distribution networks with transportation distance constraints, the existing research on network reliability with diameter constraints mainly focuses on two state networks. However, in the actual operation process, due to the impact of uncertain factors, distribution networks have the characteristics of 152 polymorphism and complexity. Therefore, two-state networks are not suitable for reliability analysis of distribution networks. In addition, it is noted that there are still imperfections in the definition of reliability and computational methods in the study of discussing polymorphic network models. As a result, the impact of transportation distance constraints on distribution networks cannot be well described. 7. Further Work (1) It is difficult to solve the candidate (d,b)-MCV model. We propose to improve the existing candidate (d,b)-MCV model by introducing a lower capacity limit for edges. In the improved candidate (d,b)-MCV model, the constraints on variables are stricter, thereby reducing the search space for candidate (d,b)-MCV and improving search efficiency. (2) Identification efficiency bottlenecks for repetitive (d,b)- MCVs. By introducing the concept of transcendental numbers, we propose an efficient method for identifying repetitive (d,b)-MCVs by establishing a one-to-one mapping between (d,b)-MCVs and real numbers. (3) Aiming at the problems of network reliability evaluation under transportation distance constraints, a reliability index for distribution networks with transportation distance constraints is proposed. Note that the key to calculating this reliability index is to solve the d-MCV problem with diameter constraints. Therefore, it is hoped that based on determining the redundant edges of the network, the actual transmission distance of the stream will be fully considered, and then a mathematical model of d-MCV with diameter constraints will be constructed, and an accurate solution algorithm will be proposed. References [1] Mine H, Kawai H. Mathematics for reliability analysis[M]. Tokyo: Asakura—shoten, 1982. [2] Iida Y, Wakabayashi H. An approximation method of terminal reliability of a road network using partial minimal path and cut set[A]. Proceedings of the Fifth WCTR[C]. Japan: Yokohama, 1989, 367-380． [3] Okur N, Aliyev R. Some Hermite–Hadamard type integral inequalities for multidimensional general preinvex stochastic processes[J]. Communications in Statistics-Theory and Methods, 2021, 50(14): 3338-3351. [4] Kotrys D, Nikodem K. Stochastic processes generating Schur- convex sums[J]. Aequationes mathematicae, 2020, 94(3): 447- 453. [5] Zhao H, Bagherzadeh N, Wu J. A general fault-tolerant minimal routing for mesh architectures[J]. IEEE Transactions on Computers, 2017, 66(7): 1240-1246. [6] Niu Y F, Lam W H K, Gao Z. An efficient algorithm for evaluating logistics network reliability subject to distribution cost[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 67: 175-189. [7] Lin JS, Jane CC, Yuan J. On reliability evaluation of a capacitated‐flow network in terms of minimal pathsets [J]. Networks, 1995, 25(3): 131-138. [8] Yeh W C. A novel method for the network reliability in terms of capacitated-minimum-paths without knowing minimum- paths in advance[J]. Journal of the Operational Research Society, 2005, 56(10): 1235-1240. [9] Niu Y, Gao Z, Sun H. An improved algorithm for solving all d- MPs in multi-state networks[J]. Journal of Systems Science and Systems Engineering, 2017, 26(6): 711-731. [10] Chen S G, Lin Y K. Searching for d-MPs with fast enumeration[J]. Journal of Computational Science, 2016, 17: 139-147. [11] Bai G, Zuo M J, Tian Z. Search for all d-MPs for all d levels in multistate two-terminal networks[J]. Reliability Engineering & System Safety, 2015, 142: 300-309. [12] Yeh W C. A simple method to verify all d-minimal path candidates of a limited-flow network and its reliability[J]. The international journal of advanced manufacturing technology, 2002, 20(1): 77-81. [13] Jane, C. C., Y. W. Laih. Evaluating cost and reliability integrated performance of stochastic logistics systems[J]. Naval Research Logistics, 2012, 59(7): 577–586. [14] Xu X Z, Niu Y F, Song Y F. Computing the reliability of a stochastic distribution network subject to budget constraint [J]. Reliability Engineering & System Safety, 2021, 216: 107947. [15] Yeh, W. C. A new approach to evaluate reliability of multistate networks under the cost constraint[J]. Omega, 2005, 33(3): 203-209. [16] Yeh, W. C. An improved method for multistate flow network reliability with unreliable nodes and a budget constraint based on path set[J]. IEEE Transactions on Systems, Man, and Cybernetics- Part A: Systems and Humans, 2011, 41(2): 350- 355. [17] Forghani-elahabad, M., N. Kagan. Reliability evaluation of a stochastic-flow network in terms of minimal paths with budget constraint[J]. IIE Transactions, 2019, 51(5): 547-558. [18] Huang, C. F., D. H. Huang, Y. K. Lin. System reliability analysis for a cloud-based network under edge server capacity and budget constraints[J]. Annals of Operations Research, 2020, 1-18. [19] Lin, Y. K. Reliability of a stochastic-flow network with unreliable branches & nodes under budget constraints[J]. IEEE Transactions on Reliability, 2004, 53(3): 381-387. [20] Lin JS. Reliability evaluation of capacitated-flow networks with budget constraints [J]. IIE Transactions, 1998, 30(12): 1175-1180. [21] Zuo MJ, Tian ZG, Huang HZ. An efficient method for reliability evaluation of multi-state networks given all minimal path vectors[J]. IIE Transactions, 2007, 39: 811-817. [22] Bai GH, Zuo MJ, Tian ZG. Ordering heuristics for reliability evaluation of multi-state networks[J]. IEEE Transactions on Reliability, 2015, 64(3): 1015-1023. [23] Bai GH, Tian Z, Zuo MJ. Reliability evaluation of multi-state networks: An improved algorithm using state-space decomposition and experimental comparison[J]. IISE Transactions, 2018, 50(5): 407-418. [24] Liu T, Bai GH, Tao JY, Zhang YA, Fang YN. An improved bounding algorithm for approximating multi-state network reliability based on state-space decomposition method[J]. Reliability Engineering & System Safety, 2021, 210: 107500. [25] Petingi L, Rodriguez J. Reliability of networks with delay constraints [J]. Congressus Numerantium,2001: 117-124. [26] Petingi L A. Efficient evaluation of a diameter-constrained reliability measure of some families of graphs[J]. Graph Theory Notes New York, 2013, 64: 26-34. [27] del Giudice P E S. Diameter-constrained network reliability: properties and computation[D]. Université Rennes 1, 2013. 153 [28] Wang H, Li J, Shao F, et al. The expected path with diameter constraint in wireless sensor network[C]//2015 IEEE International Conference on Computer and Communications (ICCC). IEEE, 2015: 379-383. [29] CancelaH, petingi L A. On the characterization of the domination of a diameter-constraint network reliability model[J]. Discrete applied mathematics, 2006, 154: 1885-1896. [30] Cancela H, El Khadiri M, Petingi L A. Polynomial-time topological reductions that preserve the diameter constrained reliability of a communication network [J]. IEEE Transactions on Reliability, 2011, 60(4): 845-851. [31] Nesterov S N, Migov D A. Parallel calculation of diameter constrained network reliability[C]//International Conference on Parallel Computing Technologies. Springer, Cham, 2017: 473-479. [32] Page L B, Perry J E. A practical implementation of the factoring theorem for network reliability[J]. IEEE Transactions on Reliability, 1988, 37(3): 259-267. [33] Zhang Z, Shao F. Reliability Analysis with Diameter Constraint in Social Networks[J]. Journal of Internet Technology, 2018, 19(7): 2047-2055. [34] Zhang Z, Shao F. A diameter-constrained approximation algorithm of multistate two-terminal reliability[J]. IEEE Transactions on Reliability, 2018, 67(3): 1249-1260.