INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL Online ISSN 1841-9844, ISSN-L 1841-9836, Volume: 17, Issue: 1, Month: February, Year: 2022 Article Number: 4573, https://doi.org/10.15837/ijccc.2022.1.4573 CCC Publications Multi-Objective Model to Improve Network Reliability Level under Limited Budget by Considering Selection of Facilities and Total Service Distance in Rescue Operations Yiying Wang, Zeshui Xu, Florin Gheorghe Filip Yiying Wang Business School Sichuan University Chengdu, Sichuan, 610064, China wanggyiying@163.com Zeshui Xu* Business School Sichuan University Chengdu, Sichuan, 610064, China xuzeshui@263.net *Corresponding author Florin Gheorghe Filip Romanian Academy 125 Calea Victoriei, Bucharest 010071, Romania ffilip@acad.ro Abstract Sudden disasters may damage facilities, transportation networks and other critical infrastruc- tures, delay rescue and bring huge losses. Facility selection and reliable transportation network play an important role in emergency rescue. In this paper, the reliability level between two points in a network is defined from the point of view of minimal edge cut and path, respectively, and the equivalence of these two definitions is proven. Based on this, a multi-objective optimization model is proposed. The first goal of the model is to minimize the total service distance, and the second goal is to maximize the network reliability level. The original model is transformed into a model with three objectives, and the three objectives are combined into one objective by the method of weighting. The model is applied to a case, and the results are analyzed to verify the effectiveness of the model. Keywords: Facility selection; Reinforce edges; Minimal edge cut; Path; Network reliability level. https://doi.org/10.15837/ijccc.2022.1.4573 2 1 Introduction Natural disasters include floods and droughts [1], earthquake and tsunami disasters [2],[3], fires [4], [5], hurricane disaster [6] and so on [7]. The occurrence of natural disasters may bring huge casualties and property losses [8]. Many scholars have conducted extensive research on rescue actions to scientifically respond to the threats caused by disasters. The proposed solutions regard issues such as the location of emergency facilities, the enhancement of traffic network reliability and so on The emergency facilities play an important role in the rescue operation [9]. In recent years, many location problems of emergency facilities have been proposed. In emergency rescue, time or distance affects rescue effectiveness. Shorter rescue time and distance will usually lead to better rescue results. Therefore, rescue distance or rescue time is an important aspect to be considered in emergency rescue, and it is an important factor to be considered in multi-objective problems for location decision-making. The classical p-median problem (PMP) assumes that demands get services from the facilities that minimize the total distance [10]. Based on PMP, Berman et al. [11] put forward a new model, which is expected to find m facility locations to minimize the expected sum of the weighted travel distances between demands and their nearest operating facilities. Coutinho- Rodrigues et al. [? ] introduced a mixed integer linear programming model to determine the evacuation routes and the location of shelters. Six objectives including the length of evacuation routes are considered. Rabta et al. [13] presented an optimization model for the delivery of light-weight relief items, which aims at minimizing the total traveling distance/time/cost under the condition of limited payload and energy. Trivedi et al. [14] described a hybrid multi-objective decision model based on analytic hierarchy process, fuzzy set theory and goal programming approach, which aims at minimizing distance, risk, number of sites, uncovered demand, and maximize suitability while taking into some other considerations. Bai [15] proposed a multi-objective expected value model including facility location, vehicle routing and supply allocation decisions. The goals of the model are to minimize the proportion of unsatisfied demands, the response time of emergency reliefs and the total cost. Early system reliability analyses have often focused on connectivity and the research on system reliability primarily concerns with the enumeration of cuts or paths [16], [17], [18]. For example, Aggarwal et al. [19] firstly studied the reliability evaluation problem without flow in a binary-state network. However, in many practical network systems, such as circuit network, transportation system, communication system, oil pipeline, each link or edge is associated with specific values. For example, in the transportation network, each road has a specific traffic flow. Therefore, after the maximum-flow minimum-cut theorem was proposed, scholars have done a lot of research on the reliability of networks with flow [20]. Lee [16] defined the criterion for evaluating network reliability as that a specific flow is transported from input node to output node, i.e., the probability that the maximal flow is at least equal to the system demand. Xue [21] used discrete function theory to expand binary state network to multistate network, which is also called stochastic-flow network, to study reliability evaluation. One of the popular methods for network reliability evaluation is the three-stages method [20], [22], [23], [24]. Later, some scholars continuously improved these methods [20], [25]. For example, Lin presented a novel maximal flow searching method along with fast enumeration to improve the efficiency of reliability evaluation [20]. Alkaff [26] presented modeling techniques for the exact dynamic reliability analyses. A quick binary-addition tree algorithm was proposed by Yeh to evaluate the binary-state network reliability [27]. A binding technique was presented by Huang et al. to solve the lower boundary points problem, which is used to compute the network reliability for a stochastic flow network [28]. In order to compute the two- terminal reliability of a dynamic network, a new method was put forward by Khanna et al. to enumerate both time-stamped-minimal path sets and time-stamped-minimal cut sets [29]. Disasters may cause damage to traffic routes, thus seriously affecting the progress of rescue operations. Therefore, some authors have studied the reliability of networks from the perspective of possible failure of edges (links or arcs) [30], [31], [32], [33]. For example, Horner and Widener [34] simulated the failure of partial road network and test how these damages affect the victims’ access to relief goods. Zhang et al. [35] studied the optimal distribution of k terminal vertices to maximize k terminal network reliability in sparse graphs, in which the edges are subject to failure. In these studies which consider edge failure, many authors assume that the network links have homogeneous or heterogeneous failure probabilities and this kind of assumptions implies that the interruption of the link is caused by its own failure [36]. Yu [36] thought the interruption of the link is actually caused by the damage that the link sustains beyond its tolerance, and on this basis, defined the reachability guarantee between the two points. Based on the concept of damage tolerance of edge in Yu’s paper, our paper defines the reliability level between two points in the network and the reliability level of the whole network, uses the optimization model to locate emergency facilities, and maximizes the network reliability level at the same time. In the decision-making of site selection, budget is another important factor affecting the solution. Peeta et al. [37] selected the links to invest under the limited budget, so as to maximize the post-disaster connectivity and minimize the travel costs between the origin and destination nodes. Amin et al. [38] described an optimization model which has two objectives. The first objective is to minimize the costs which are used to maintain the https://doi.org/10.15837/ijccc.2022.1.4573 3 road condition and the second objective is to minimize the pavement roughness and geophysical risks. Vahdani et al. [39] proposed a nonlinear multi-objective model to improve the reliability of the routes and minimize the travel time and cost. Hu et al. [40] proposed a two-stage stochastic programming model, aiming at minimizing budgets and the punishment caused by risk. In our paper, we assume that the budget is limited. We use certain budget for facility selection and edge reinforcement to minimize the total service distance and maximize the network reliability level. This paper proposes the following innovative issues: The reliability level between two points and the network reliability level are defined from the point of view of minimal edge cut and path, and the equivalence theorem of the two definitions is proven. The definition of reliability level between two points and network reliability level are used to establish a location decision-making model, which minimizes the total service distance and maximizes the network reliability level under certain budget constraint. In order to make full use of budget, this paper assumes that the increment of the reliability level of edges is continuous. Based on the definition of network reliability level, this paper balances the reliability level of selected paths with variance weight, and studies how variance weight affects the goal with a case study. We find that by changing the variance weight, we can get satisfactory network reliability level. The rest of the paper is as follows. Section 2 contains a methodology, which consists of basic concepts, the definitions of reliability levels, the equivalence theorem, and the reinforcement of edges. In Section 3, we construct a multi-objective model, which aims to minimize the total service distance and maximize the network reliability level. Section 4 presents a case study, in which we conduct some analyses to discuss the relationship between some variables. Section 5 concludes the paper and gives the future research direction. 2 Methodology When the destructive power of natural disasters reaches a certain degree, the road between rescue facilities and demand points may be damaged. Therefore, the road construction between rescue facilities and demand points plays an important role in disaster prevention. In order to study the goal of road construction, we form the concepts of the reliability level of edge, reliability level of the minimum edge cut, reliability level of path, reliability level between two points and network reliability level, and discuss how to calculate the network reliability level. 2.1 Basic concepts The problem studied in this paper is defined by the connected graph G(N,A), that is undirected and weighted, where the symbol N represents a point set, and A represents an edge set. The value of each edge is nonnegative. The demand set and facility set are different subsets of the point set N. In this subsection, we give two definitions: The reliability level of each edge and the reliability level of a path in the network. Definition 1 (The reliability level of an edge). Assume that each undirected edge a ∈ A has a damage tolerance ra ∈ [0, 1], which represents the maximum degree of disaster damage it can withstand. If the damage of the disaster exceeds ra, the edge a will be interrupted. If the damage of the disaster does not exceed ra, then the edge a can still pass normally [36]. Since ra represents the maximum ability of an edge to withstand disasters, in this paper, we call ra the reliability level of the edge a(a ∈ A). The reliability level of each edge can be evaluated in advance according to the specific conditions of the edge. The larger the value of ra, the stronger the ability of the edge a to resist disasters. Theoretically, ra can be equal to 1, indicating that edge a can withstand any degree of damages. However, the value of ra of the actual road a cannot reach the value 1, because the actual road cannot survive in all degrees of disasters. Therefore, ra of the actual road is less than 1. Definition 2 (The reliability level of a path). As described in definition 1, given the damage tolerance ra,a ∈ A for all edges of path p, the minimum ra of all edges on the path p is called the damage tolerance of the path p [36]. If the damage of the disaster exceeds the damage tolerance of the path p, the path p will be interrupted, otherwise, the path p will not be interrupted. It can be seen that this value represents the maximum ability of the path p to withstand disasters. Therefore, we call it the reliability level of the path p. Let E′ be the set of all paths between the two points X and Y , H ′ e′ (e ′ ∈ E′) be the edge set of the path e′, be′h′ be the edge h′ on the path e′ between the two points X and Y , w(be′h′ ) be the reliability level of the edge be′h′ , then min h′∈H ′ e′ w(be′h′ ) is called the reliability level of the path e′. When the destructive power on the path e′ does not exceed min h′∈H ′ e′ w(be′h′ ), the path e′ is connected, otherwise, the path e′ is interrupted. https://doi.org/10.15837/ijccc.2022.1.4573 4 2.2 Reliability levels in the network In system reliability analysis, the system is thought to be functioning if there exists a path from the input point to the output point [16]. Therefore, the concepts of reliability level of the edge and the path are extended to any two points in the network. Below, we first give the definition of the reliability level of every minimal cut, then, the definition of the reliability level of any two points in G. Definition 3 (The reliability level of every minimal cut in the connected weighted graph G). Let X and Y be two points in G, E be the set of minimal edge cut sets between the two points X and Y , He(e ∈ E) be the edge set of the minimal edge cut e, aeh be the edge h(h ∈ He) of the minimum edge cut e between the two points X and Y , w(aeh) be the reliability level of the edge aeh, then max h∈He w(aeh) is called the reliability level of the minimal edge cut e, which is written as we. When the destructive power in the network does not exceed we, the two points X and Y are connected; otherwise, they are not connected. Definition 4 (The reliability level between two points in the connected weighted graph G by minimal edge cut). Let X and Y be two points in G, E be the set of minimal edge cut sets between the two points X and Y , He(e ∈ E) be the edge set of the minimal edge cut e, aeh be the edge h(h ∈ He) of the minimum edge cut e between the two points X and Y , w(aeh) be the reliability level of the edge aeh, then min e∈E max h∈He w(aeh) is called the reliability level between the two points X and Y in G. In order to get min e∈E max h∈He w(aeh), it is necessary to find the maximum reliability level of the cut edge in each minimal edge cut between the two points X and Y in G, and then take the minimum value. This value represents the maximum ability of the network between the two points X and Y to resist disasters. If the damage degree does not exceed min e∈E max h∈He w(aeh), the two points X and Y are connected, otherwise, they are not connected. In the network, assume that the demand point set is I(i ∈ I), the demand point i is assigned to the facility ji(ji ∈ J), the reliability level of the edge a in the network is r(a), the set of minimal edge cut sets between the demand point i and its service facility ji is Si,ji , Si,ji = {S1i,ji,S 2 i,ji ,S3i,ji, . . . ,S |i,ji| i,ji } (Sxi,ji is the x-th minimal edge cut set between the two points i and ji, |i,ji| is the number of minimal edge cut sets between the two points i and ji). For the minimal cut set Sxi,ji , there is S x i,ji = {l Sxi,ji 1 , l Sxi,ji 2 , l Sxi,ji 3 , . . . , l Sxi,ji∣∣Sx i,ji ∣∣} (where ∣∣Sxi,ji∣∣ is the number of cut edges in the minimal edge cut Sxi,ji ). In S x i,ji , we sort the reliability level of cut edges in a non-decreasing order, and assume that the reliability level of each edge is r(l Sxi,ji 1 ),r(l Sxi,ji 2 ),r(l Sxi,ji 3 ), . . . ,r(l Sxi,ji∣∣Sx i,ji ∣∣) that is r(l Sxi,ji 1 ) ≤ r(l Sxi,ji 2 ) ≤ r(l Sxi,ji 3 ) ≤ . . . ≤ r(l Sxi,ji∣∣Sx i,ji ∣∣). Among them, the maximum reliability level is r(l Sxi,ji∣∣Sx i,ji ∣∣). For all minimal edge cut sets between the two points i and ji, the reliability level of each minimal edge cut set is r(l S1i,ji∣∣S1 i,ji ∣∣), r(lS3i,ji∣∣S2 i,ji ∣∣), r(lS4i,ji∣∣S3 i,ji ∣∣), . . . r(lS|i,ji|i,ji∣∣S|i,ji | i,ji ∣∣). Then, let the reliability level between the two points i and ji be Rjii , and by Definition 4, there is: Ri,ji = min { r(l S1i,ji∣∣S1 i,ji ∣∣),r(lS2i,ji∣∣S2 i,ji ∣∣),r(lS3i,ji∣∣S3 i,ji ∣∣), . . .r(lS|i,ji |i,ji∣∣S|i,ji | i,ji ∣∣) } . Let the minimum reliability level between all pairs of demand points and corresponding service facilities be R, defined as R = min i∈I Ri,ji . We call R the network reliability level of G. When the destructive power does not exceed R, all the demand points in G are connected with the corresponding service facilities. When the destructive power exceeds R, at least one demand point cannot be served. 2.3 Equivalence theorem Now, we consider the reliability level between two points in the network from the perspective of path. Firstly, we get two theorems as follows: Theorem 1. There is at least one path existing between the two points X and Y in the connected graph G, if and only if every minimal edge cut between the two points X and Y keeps at least one uncut edge in the graph. https://doi.org/10.15837/ijccc.2022.1.4573 5 Proof. First, we prove the necessity by disproof. If every edge in a minimal edge cut set between the two points X and Y is cut, then the two points of G are not connected (there is no path between the two points X and Y ), which contradicts that there is at least one path between the two points X and Y . Therefore, when there is at least one path between the two points X and Y , each minimal edge cut between the two points X and Y leaves at least one edge uncut. Then, we prove the sufficiency: If every minimal edge cut between the two points X and Y leaves at least one edge uncut in the graph, that is to say, there is no minimal edge cut between the two points X and Y in G that separates the point X from the point Y , we assert that the two points X and Y are connected. Assuming that there is no connection between the two points X and Y , then all the cut edges at this time form an edge cut set, and at least one minimal edge cut can be obtained by removing the redundant cut edges from the edge cut set, that is, all the edges in this obtained minimal edge cut set are disconnected at this time, which contradicts “every minimal edge cut between the two points X and Y still has at least one uncut edge in the graph”. Therefore, when every minimal edge cut between the two points X and Y retains at least one uncut edge in the graph, there is at least one path existing between the two points X and Y in G. Theorem 2. As shown in figure 1, Let X and Y be two points in the connected graph G, E be the set of minimal edge cut sets between the two points X and Y , He(e ∈ E) be the edge set of the minimal edge cut set e, aeh be the edge h(h ∈ He) of the minimum edge cut e between the two points X and Y , E′ be the set of all paths between the two points X and Y , H ′ e ′ (e′ ∈ E′) be the edge set of the path e′, be′h′ be the edge h′ on the path e′ between the two points X and Y , w(aeh) be the weight of the edge aeh, w(be′h′ ) be the weight of the edge b(e′h′), then min e∈E max h∈He w(aeh) = max e ′∈E′ min h ′∈H ′ e ′ w(be′h′ ) . Proof. In the connected graph G, the edges are cut out in sequence according to the non-decreasing weights of the edges, until when an edge with the weight w0 is cut out, the two points X and Y are just divided into two connected components, and stop. We assert that w0 = min e∈E max h∈He w(aeh), w0 = max e ′∈E′ min h ′∈H ′ e ′ w(be′h′ ) . According to the above operation, when the edge with the weight w0 is cut, the cut edge forms an edge cut set between the two points X and Y . This edge cut set is not necessarily a minimal edge cut set. If this edge cut set is not a minimal edge cut set, then we remove the redundant edges from it and form a minimal edge cut set. This minimal edge cut set must contain edges with the weight w0. Because once the edge of w0 is removed from the initial edge cut set, all other cut edges cannot form a minimal edge cut set. Obviously, w0 is the maximum weight of edges in this minimal edge cut set. Because we cut the edges in the order of non-decreasing weight of edges, and other minimal edge cut sets have not yet been formed, the maximum weight of edges in all other minimal edge cut sets is not less than w0. Therefore, w0 = min e∈E max h∈He w(aeh) can be obtained. On the other hand, the corresponding paths between the two points X and Y are broken in the order of minimum edge weight from small to large, and no minimal edge cut set between the two points X and Y is formed before the edge with the weight w0 is cut off. According to Theorem 1, there is at least one path uncut between the two points X and Y at this time. After the edge with the weight w0 is cut off, all X −Y paths are cut off. At this time, we assert that the edge with minimum weight on every path is cut off. If the edge with the minimum weight on a path is not cut, the edge with the larger weight on the same path is also not cut. Then, there exists at least one path uncut between the two points X and Y , which is contrary to “all paths are cut off”. Obviously, w0 is the minimum edge weight on the last broken paths, and it is not less than the minimum edge weight on other X −Y paths. Therefore w0 = max e ′∈E′ min h ′∈H ′ e ′ w(be′h′ ). According to above discussion, min e∈E max h∈He w(aeh) = max e ′∈E′ min h ′∈H ′ e ′ w(be′h′ ) holds. From the proof process of Theorem 2, we can see that, the value w0 plays an important role in the graph G. Actually, w0 has different meanings in different scenarios. For example, in the graph G, if the value of each edge represents the allowed load of the vehicle to pass through, then w0 represents the maximum load of the vehicle allowed to pass through between the two points X and Y . If the value of each edge represents the water surface width of the river channel in the water network, then w0 represents the maximum width at the water surface of object allowed to pass through between the two points X and Y . If the value of each edge represents the depth of the waterway, then w0 represents the maximum height of the submarine allowed to pass through under water between the two points X and Y . As we can see from these examples, in the graph G, w0 represents the maximum ability of the network between the two points X and Y to allow the object to pass through as a whole (indivisible). In our paper, w0 is defined as the reliability level, which refers to the maximum ability of the network between the two points X and Y to withstand disasters. Here, withstand could be understood as “allowing to pass through”. Example 1. As shown in figure 2, the number next to edge represents the weight. https://doi.org/10.15837/ijccc.2022.1.4573 6 Figure 1: A connected weighted graph with the two points X and Y Figure 2: A weighted graph The minimal edge cut sets between a and c are ab,ad, bc,dc, ab,bd,dc, ad,db,bc The maximum weights of these minimal edge cuts are 4, 5, 3, 5 respectively, and the minimum value of these maximum weights is 3. Paths between a and c are abc, adc, abdc, adbc. The minimum weights of the edges on these paths are 1, 3, 1 and 2, respectively, and the maximum value of these minimum weights is 3. According to theorem 2, the reliability level between two points in a network can also be defined by paths. Next, we give the definitions of the reliability level between two points and the network reliability level from the perspective of path. Definition 5 (The reliability level between two points by path). Let E′ be the set of all paths between the two points X and Y , H′e′ (e ′ ∈ Eprime) be the edge set of the path e′, be′h′ be the edge h′ on the path e′ between the two points X and Y , w(bb′h′ ) be the reliability level of the edge be′h′ , then max e′∈E′ min h′∈H ′ e′ w(be′h′ ) is called the reliability level between the two points X and Y in G. In order to get max e′∈E′ min h′∈H ′ e′ w(be′h′ ), we need to find the minimum reliability level on each path between the two points X and Y , and then take the maximum value of these minimum reliability levels. This value represents the maximum ability of the network between these two points to resist disasters. If the damage degree does not exceed max e′∈E′ min h′∈H ′ e′ w(be′h′ ), then the two points X and Y are connected, otherwise, they are not connected. In the network, assume that the demand point set is I(e ∈ I), the demand point i is assigned to the facility ji(ji ∈ J), the reliability level of the edge a in the network is r(a), the path set between the demand point i and its service facility ji is Pi,ji , (Pi,ji = { P 1i,ji,P 2 i,ji ,P 3i,ji, . . . ,P |i,ji| i,ji } (P ui,ji is the path u between the point i and the point ji, |i,ji| is the number of paths between the point i and the point ji), P ui,ji ={ l P ui,ji 1 , l P ui,ji 2 , l P ui,ji 3 , . . . , l P ui,ji∣∣P u i,ji ∣∣ } ( ∣∣P ui,ji∣∣ is the number of edges on the path P ui,ji ). On P ui,ji , we sort the reliability level of cut edges in a non-decreasing order, and assume that the reliability level of each edge is r(l P ui,ji 1 ), r(l P ui,ji 2 ), r(l P ui,ji 3 ), . . ., r(l P ui,ji∣∣P u i,ji ∣∣), that is r(l P ui,ji 1 ) ≤ r(l P ui,ji 2 ) ≤ r(l P ui,ji 3 ) ≤ . . . ≤ r(l P ui,ji∣∣P u i,ji ∣∣). Among them, the minimum reliability level is r(l P ui,ji 1 ). For all paths between the demand point i and the facility ji, the minimum reliability level of each path is r(l P 1i,ji 1 ), r(l P 2i,ji 1 ), r(l P 3i,ji 1 ), . . ., r(l P |i,ji | i,ji 1 ). Let R′i,ji be the reliability level between the demand point i and the facility ji: R′i,ji = max { r ( l P 1i,ji 1 ) ,r ( l P 2i,ji 1 ) ,r ( l P 3i,ji 1 ) , . . . ,r ( l P |i,ji | i,ji 1 )} . According to theorem 2, Ri,ji = R′i,ji . Now, we uniformly use Ri,ji to represent the reliability level between https://doi.org/10.15837/ijccc.2022.1.4573 7 the demand point i and the facility ji. So, Ri,ji = max { r ( l P 1i,ji 1 ) ,r ( l P 2i,ji 1 ) ,r ( l P 3i,ji 1 ) , . . . ,r ( l P |i,ji | i,ji 1 )} . The network reliability level is still recorded as R, then R = min i∈I Ri,ji . 2.4 Reinforcement of edges In case of disaster, edges may be interrupted. We can take reinforcement measures to improve the reliability level between two points. Let the original reliability level of the edge a be r0a and the reinforcement coefficient be βa(0 ≤ βa ≤ 1,a ∈ A). When βa = 0, the edge a is not reinforced. When βa = 1, the edge a is completely reinforced and the increment of the reliability level is ∆r(a) = 1 − r0a. When 0 < βa < 1, the increment of the reliability level is ∆r(a) = βa(1 −r0a) (0 < ∆r(a) < 1 −r0a), a ∈ A. Let the cost of elevating unit reliability level of the edge a be ca(a ∈ A). The reinforcement costs of different edges are different. The maximum reinforcement cost of each edge a is (1−r0a)ca, and the actual reinforcement cost is βa(1 −r0a)ca, a ∈ A . 3 The model • The main assumptions: 1. The set of alternative facilities and demand points is known; 2. There is a fixed setup cost for each facility; 3. The reliability level of each edge can be continuously improved and is up to 1; 4. The total budget is fixed, which is used for selecting facilities and reinforcing edges; 5. Each demand point can only be assigned to one facility, and one facility can serve multiple demand points; 6. We believe that disasters have the same impact on all edges of the same network. • Set definitions: I : The set of demand points J : The set of alternative facilities A : The set of edges • Parameters: B : The budget to locate facilities and reinforce edges cj : The fixed setup cost of the locating facility j, j ∈ J ca : Reinforcement cost of improving unit reliability level of the edge a, a ∈ A r0a : The original reliability level of the edge a, a ∈ A Pi,j : Path set between the demand i and the facility j dui,j : The distance of the path u between the demand point i and the alternative facility j, ∀i ∈ I, ∀j ∈ J, ∀u ∈ Pi,j M : Number of selected facilities • Decision variables: R(i) : Reliability level between the demand point i and the corresponding service facility f : Variance of reliability level between all demand points and the corresponding service facilities ∆ra : The increment of the reliability level after the edge a is reinforced R : Network reliability level ra : The reliability level of the edge a, 0 ≤ ra ≤ 1, a ∈ A. • Binary variables: yj = { 1 iffacility j is selected 0 otherwise ,j ∈ J xij = { 1 if facility j is allocated to provide service for demand point i 0 otherwise ,i ∈ I,j ∈ J https://doi.org/10.15837/ijccc.2022.1.4573 8 yui,j =   1 if path u between demand point i and facility j is selected to be reinforced 0 otherwise ,i ∈ I,j ∈ J,u ∈ Pi,j Model 1: • Objectives: MIN ∑ i∈I ∑ j∈J ∑ u∈Pi,j (1) MAX R (2) • Constraints: ∑ j∈J yj = M (3) xij ≤ yj,∀i ∈ I,∀j ∈ J (4) xij ≥ yui,j,∀i ∈ I,∀j ∈ J,∀u ∈ Pi,j (5)∑ j∈J xij = 1,∀i ∈ I (6) ∑ i∈I ∑ j∈J xij = |I| (7) ∑ j∈J cjyj + ∑ a∈A ∆raca ≤ B, 0 ≤ ∆ra ≤ 1 −r0a (8) ∑ u∈Pi,j yui,j = 1,∀i ∈ I,∀j ∈ J (9) yj,xij,y u i,j ∈ 0, 1,∀i ∈ I,∀j ∈ J,∀u ∈ Pi,j (10) In the above model 1, the formula 1 requires the sum of distances between all demand points and the corresponding service facilities to be minimized, and the formula 2 requires the network reliability level to be maximized. The formula 3 is used to constrain the total number of selected facilities. Constraint 4 means that only after the facility is selected can it serve the demand point. Constraint 5 means that only when the facility actually provides service for the demand point can a certain path between them be selected. Constraint 6 means that each demand point has only one facility to provide service for it. Equation 7 is a constraint on the total number of demand points, where |I| represents the number of demand points. Constraint 8 means that the cost of locating facilities and the cost of strengthening edges shall not exceed the budget. Constraint 9 means that only one path is selected between a demand point and the facility serving it. Constraint 10 indicates that yj, xij, yui,j are binary variables. We will solve the above model after making appropriate changes. We maximize the total reliability level after reinforcement and take it as an objective of the changed model. In order to balance the reliability level between all demand points and the corresponding service facilities, so as to improve the network reliability level and achieve the second goal of Model 1, we calculate the variance of these reliability levels and set the minimization of variance as the third goal. Therefore, the following model is obtained: Model 2: MIN ∑ i∈I ∑ j∈J ∑ u∈Pi,j yui,jd u i,j (11) MAX ∑ i∈I R(i) (12) MIN f (13) Let g1 = ∑ i∈I ∑ j∈J ∑ u∈Pi,j y u i,jd u i,j, g2 = ∑ i∈I R(i), g3 = f and g = ω1g1 −ω2g2 + ω3g3. Then, the above three objectives are combined into a single objective, and set the single objective as: MIN g (14) among which, ω1, ω2 and ω3 are the weights of g1, g2 and g3. As the two goals of total service distance and total reliability level after reinforcement are different in scale, we deal with these three goals as follows. For a given budget, we take g1 and g2 as single objective and get their optimal values respectively. For example, when the budget is 1150, we get the optimal values of g1 and g2 as separate objective, which are 128 and 2.99, respectively. We take 1/128 and 1/2.99 as ω1 and ω2 in g, respectively. When ω1 and ω2 are determined, ω3 takes different values from small to large. In this paper, ω3 is taken as 0, 1, 2,. . . , 14. https://doi.org/10.15837/ijccc.2022.1.4573 9 4 Case study 4.1 Data We use the network in figure 3 to test the model. This network has 11 points and 16 edges, and it shows the locations of demand points and alternative facilities. Table 1 lists the location cost of each alternative facility. Table 2 lists the original reliability level and unit reinforcement cost of each edge. The model is programmed on the platform of Python 3.8, runs on a 64-bit i5-7300U laptop, and is solved by Gurobi 9.1.2. 4.2 Analysis In this case, the number of the selected facilities M is 2, and the number of demand points |I| is 3. The values of B are 800, 850, 875, 900, 925, 950, 1000, 1050, 1100, 1150, and 1175, respectively. 4.2.1 Relationship between network reliability level, total reliability level and variance weight Table 3 shows the solution results of network reliability level. It can be seen from Table 3 that, in general, the network reliability level R is positively correlated with the variance weight ω3, that is, when the value of ω3 increases, R tends to rise (the situation is special when B = 900, which will be analyzed later). For example, when B = 1150, ω3 is 1 and 6 respectively, and R is 0.8 and 0.887. Therefore, we can draw the conclusion that the reliability level between demand points and facilities serving them can be improved by strengthening certain edges. At the same time, R can also be improved. This phenomenon can also be visually noticed from figure 4. Figure 3: A weighted connected graph Table 1: The location cost of each alternative facility Location Q C D F V U W K Cost 550 380 700 650 400 600 530 450 Table 2: Original reliability level and unit re- inforcement cost of each edge Edge r0a ca Edge r0a c_a OU 0.5 150 LF 0.6 200 UV 0.6 200 FT 0.3 180 TV 0.5 210 DW 0.4 130 UW 0.5 120 WT 0.7 150 OQ 0.6 170 QW 0.5 120 QC 0.4 100 DF 0.4 150 CD 0.6 160 KC 0.7 100 DL 0.5 180 KL 0.5 220 The influence of ω3 on R can be seen more clearly from table 4 and table 5. Table 4 lists the reliability level of each edge on each selected path before and after reinforcement when B = 850. Table 5 lists the reliability level of each edge on each selected path before and after reinforcement when B = 1150. It can be seen from table 4 that when B = 850, with the increase of ω3, the variance F generally shows a downward trend. For example, when ω3 = 0, f = 0.00129; When ω3 = 14, f = 0.00014. Therefore, the process of increasing ω3 is the process of decreasing the fluctuation of reliability level after strengthening each selected path. For example, when ω3 increases from 0 to 14, the reliability level of OU increases from 0.6 to 0.6112, that of UV increases from 0.6 to 0.6112, that of DC increases from 0.6 to 0.6128, that of LD increases from 0.6 to 0.6128, and that of TV decreases from 0.6762 to 0.6368. When ω3 = 0, the maximum difference of reliability level of the three paths after reinforcement is 0.6762−0.6 = 0.0762; When ω3 = 14, the maximum difference of the reinforced reliability level of the three paths is 0.6368 − 0.6112 = 0.0256. Obviously, ω3 plays an important role in balancing the reliability level of the three paths. A similar analysis can be made for B = 1150. We take B = 1150 as an example to analyze how ω3 affects R by affecting the allocation of reinforcement budget. It can be seen from table 6 that when B = 1150, the selected facilities are V and K, the cost of the selected facilities is 850, and the cost of edge reinforcement is 300, the selected three paths are OU-UV, TV and LK, and the edges to be reinforced are OU, UV, TV and LK respectively. As shown in table ??, the unit reinforcement costs of these four edges are 150, 200, 210 and 220 respectively. Since the unit reinforcement cost of OU is the lowest, budget is firstly allocated to increase the reliability level of OU to 0.6. At this time, the https://doi.org/10.15837/ijccc.2022.1.4573 10 Table 3: Solution results of network reliability level under different budgets ω3 800 850 875 900 925 950 1000 1050 1100 1150 1175 0 0.500 0.600 0.600 0.600 0.600 0.500 0.600 0.600 0.657 0.800 0.871 1 0.500 0.600 0.600 0.600 0.600 0.600 0.600 0.622 0.695 0.800 0.871 2 0.500 0.600 0.600 0.573 0.600 0.600 0.632 0.701 0.770 0.839 0.873 3 0.500 0.600 0.615 0.576 0.600 0.600 0.660 0.729 0.795 0.863 0.894 4 0.503 0.600 0.622 0.577 0.600 0.607 0.675 0.742 0.808 0.875 0.906 5 0.510 0.600 0.627 0.579 0.600 0.617 0.683 0.750 0.816 0.881 0.914 6 0.515 0.602 0.630 0.579 0.600 0.623 0.689 0.755 0.821 0.887 0.919 7 0.518 0.604 0.632 0.579 0.600 0.627 0.693 0.759 0.825 0.889 0.922 8 0.520 0.606 0.635 0.580 0.600 0.631 0.697 0.762 0.827 0.892 0.925 9 0.522 0.607 0.636 0.579 0.600 0.633 0.699 0.764 0.830 0.895 0.927 10 0.523 0.608 0.636 0.579 0.602 0.636 0.701 0.766 0.831 0.896 0.928 11 0.525 0.609 0.637 0.580 0.604 0.637 0.702 0.768 0.832 0.897 0.930 12 0.526 0.610 0.638 0.580 0.606 0.639 0.704 0.769 0.833 0.898 0.930 13 0.526 0.611 0.639 0.580 0.607 0.640 0.704 0.770 0.834 0.899 0.931 14 0.528 0.611 0.639 0.580 0.608 0.641 0.706 0.770 0.835 0.900 0.932 reliability level of path OU-UV is 0.6, the increment of reliability level of this path is 0.1, and the reinforcement budget consumed is 15. Thereafter, for every 0.1 increase in the reliability level, the reinforcement fund of path OU-UV is 0.1 × (150 + 200) = 35, while the reinforcement fund of path TV is only 0.1 × 210 = 21, and that of path LK is only 0.1 × 220 = 22. It can be seen that, when , in order to minimize the overall goal, after the reliability level of OU-UV reaches 0.6, the reinforcement funds will be used to reinforce path TV first, then path LK, and finally path OU-UV. The funds needed to increase the reliability level of TV from 0.5 to 1 are 0.5×210=105, and the funds needed to increase the reliability level of LK from 0.5 to 1 are 0.5 × 220 = 110. When the reliability level of path OU-UV reaches 0.6, and the reliability level of TV and LK reaches 1, the total capital for edge reinforcement is 15 + 105 + 110 = 230. As the available edge reinforcement fund is 300, 70 can be continuously used to reinforce path OU-UV, and the increased reliability level of path OU-UV is 70/350 = 0.2. Therefore, the reliability level of OU and UV is finally raised to 0.8, as shown in table 5. Thereafter, with the increase of the value of ω3, the balancing effect on the reliability level of each selected path increase, part of the funds used to reinforce TV and LK are gradually used to reinforce the edges on the path OU-UV. Therefore, the reliability level of TV and LK gradually decreases, while the reliability level of the path OU-UV continuously increases, and the reliability level of the network continuously improves. However, since the funds used to improve the unit reliability level of the path OU-UV are greater than those used to improve the unit reliability level of TV or LK, when part of the reinforcement funds of TV or LK are used to reinforce the path OU-UV, the total reliability level after reinforcement will decrease continuously, as shown in table 5 and table 8. When ω3 = 14, the reliability level of path TV decreases to 0.9195, the reliability level of path LK decreases to 0.9181, and the reliability level of path OU-UV increases to 0.8998. The variance of the reliability level of the three paths is only 8.09 × 10−5, which is far less than the variance value of 0.0089 when the variance weight ω3 is 0. If the ω3 continues to increase, more funds will be transferred to the reinforced path OU-UV, and the reliability level of the three paths will be more balanced, thus obtaining higher R. Figure 4: Network reliability level under different budgets and different variance weights Figure 5: Total reliability level of each budget with different variance weights https://doi.org/10.15837/ijccc.2022.1.4573 11 Table 4: B=850, reliability level of each edge on each selected path before and after reinforcement SP OU-UV SP TV SP LD-DC ω3 f TR R Be Af Be Af Be Af Be Af Be Af OU OU UV UV TV TV DC DC LD LD 0 0.0013 1.8762 0.6000 0.50 0.6000 0.60 0.6000 0.50 0.6762 0.60 0.6000 0.50 0.6000 1 0.0013 1.8762 0.6000 0.50 0.6000 0.60 0.6000 0.50 0.6762 0.60 0.6000 0.50 0.6000 2 0.0013 1.8762 0.6000 0.50 0.6000 0.60 0.6000 0.50 0.6762 0.60 0.6000 0.50 0.6000 3 0.0013 1.8762 0.6000 0.50 0.6000 0.60 0.6000 0.50 0.6762 0.60 0.6000 0.50 0.6000 4 0.0013 1.8762 0.6000 0.50 0.6000 0.60 0.6000 0.50 0.6762 0.60 0.6000 0.50 0.6000 5 0.0011 1.8749 0.6000 0.50 0.6000 0.60 0.6000 0.50 0.6727 0.60 0.6022 0.50 0.6022 6 0.0008 1.8714 0.6018 0.50 0.6018 0.60 0.6018 0.50 0.6637 0.60 0.6059 0.50 0.6059 7 0.0006 1.8689 0.6041 0.50 0.6041 0.60 0.6041 0.50 0.6574 0.60 0.6074 0.50 0.6074 8 0.0004 1.8668 0.6059 0.50 0.6059 0.60 0.6059 0.50 0.6521 0.60 0.6088 0.50 0.6088 9 0.0004 1.8656 0.6068 0.50 0.6068 0.60 0.6068 0.50 0.6490 0.60 0.6098 0.50 0.6098 10 0.0003 1.8641 0.608 0.50 0.608 0.60 0.608 0.50 0.6451 0.60 0.611 0.50 0.611 11 0.0002 1.8632 0.609 0.50 0.609 0.60 0.609 0.50 0.6429 0.60 0.6113 0.50 0.6113 12 0.0002 1.8622 0.6098 0.50 0.6098 0.60 0.6098 0.50 0.6403 0.60 0.6121 0.50 0.6121 13 0.0002 1.8616 0.6107 0.50 0.6107 0.60 0.6107 0.50 0.6387 0.60 0.6121 0.50 0.6121 14 0.0001 1.8608 0.6112 0.50 0.6112 0.60 0.6112 0.50 0.6368 0.60 0.6128 0.50 0.6128 Selected path: SP; Total reliability level of network: TR; Before: Be; After: Af. Table 5: B=1150, reliability level of each edge on each selected path before and after reinforcement SP OU-UV SP TV SP LK ω3 f TR R Be Af Be Af Be Af Be Af OU OU UV UV TV TV LK LK 0 0.0089 2.8000 0.800 0.50 0.8000 0.60 0.8000 0.50 1.0000 0.50 1.0000 1 0.0089 2.8000 0.800 0.50 0.8000 0.60 0.8000 0.50 1.0000 0.50 1.0000 2 0.0038 2.7759 0.839 0.50 0.8387 0.60 0.8387 0.50 0.9732 0.50 0.9638 3 0.0016 2.7606 0.863 0.50 0.8629 0.60 0.8629 0.50 0.9518 0.50 0.9458 4 0.0009 2.7532 0.875 0.50 0.8746 0.60 0.8746 0.50 0.9417 0.50 0.9368 5 0.0006 2.7491 0.881 0.50 0.8812 0.60 0.8812 0.50 0.9359 0.50 0.9319 6 0.0004 2.7457 0.887 0.50 0.8866 0.60 0.8866 0.50 0.9308 0.50 0.9283 7 0.0003 2.7440 0.889 0.50 0.8892 0.60 0.8892 0.50 0.9291 0.50 0.9257 8 0.0002 2.7423 0.892 0.50 0.8920 0.60 0.8920 0.50 0.9262 0.50 0.9240 9 0.0002 2.7406 0.895 0.50 0.8947 0.60 0.8947 0.50 0.9240 0.50 0.9219 10 0.0002 2.7400 0.896 0.50 0.8956 0.60 0.8956 0.50 0.9233 0.50 0.9211 11 0.0001 2.7390 0.897 0.50 0.8972 0.60 0.8972 0.50 0.9220 0.50 0.9200 12 0.0001 2.7384 0.898 0.50 0.8982 0.60 0.8982 0.50 0.9212 0.50 0.9190 13 8.784 × 10−5 2.7377 0.899 0.50 0.8993 0.60 0.8993 0.50 0.9197 0.50 0.9186 14 8.09 × 10−5 2.7374 0.900 0.50 0.8998 0.60 0.8998 0.50 0.9195 0.50 0.9181 Selected path: SP; Total reliability level of network: TR; Before: Be; After: Af. https://doi.org/10.15837/ijccc.2022.1.4573 12 4.2.2 Relationship between facility location and variance weight In addition, we can also notice the fact that the change of ω3 may change the combination of the selected facilities. This happens twice in this case. As shown in table 6, when B = 900, ω3 are 0 and 1, the selected facilities are C and V , while when ω3 are 2-14, the selected facilities are V and K. When B = 925, ω3 is 0, the combination of selected facilities is C and V , while ω3 is 1-14, the combination of selected facilities is V and K. The influence of the change of the values of ω3 on the selected facilities can be understood as follows. As analyzed in Subsection 4.2.1, when the selected facilities are unchanged, with the increase of ω3, part of the reinforcement funds of the paths with larger reliability level are gradually transferred to the paths with smaller reliability level. This transfer of funds leads to a decrease in the total reliability level of the network (as shown in table 8 and figure 5), which in turn leads to an increase in the total objective (as shown in table 9). Therefore, there may be such a situation: under a certain budget, when ω3 exceeds a certain value, although the change of the selected facilities leads to an increase in the cost of the selected facilities, the reinforcement funds of the edge decrease, and the total reliability level of the network decreases. However, the total service distance decreases, resulting in a decrease in the total objective. In this case, when B = 900 and ω3 = 2, if the selected facilities remain unchanged, then they are still C and V . Thus, the total objective value is 0.1698. If the selected facilities become V and K, then the total objective is 0.1662. Obviously, the change of the selected facilities makes the overall objective smaller. Therefore, under this variance weight, the change of the selected facilities is realized. In the process of changing the selected facilities, the reinforcement funds of the edges decreased by 70, only 50, which was not enough to raise R to the level before changing the selected facility. Therefore, with the change of the selected facilities, R decreases. However, we find that when B = 925, the change of the selected facilities does not lead to the decrease of R, as shown in table 7. We analyze this situation. When B = 925 and ω3 = 0, the selected facilities are C and V , the cost of the selected facilities is 780, and the cost of edge reinforcement is 145. The selected paths are OU-UV, LD-DC and TV, and the reliability level of each edge after reinforcement is OU (0.6), UV (0.6), LD (0.6206), DC (0.6206) and TV (1.0) respectively. The reinforcement amounts of each edge are: OU (0.1), UV (0), LD (0.1206), DC (0.0206), TV (0.5), the reliability level of path OU-UV is 0.6, and the reliability level of the path LD-DC is 0.6206, the reliability level of TV is 1.0, and is 0.6. When ω3 = 1, the selected facilities are changed to V and K, the cost of the selected facilities is 850, and the cost of edge reinforcement is 75. The selected paths are OU-UV, LK and TV, and the reliability level of each edge after reinforcement is OU (0.6), UV (0.6), LK (0.6240) and TV (0.6558). The reinforcement amounts of each edge are: OU (0.1000), UV (0), LK (0.1240), TV (0.1558), the reliability level of the path OU-UV is 0.6, the reliability level of the path LK is 0.6240, the reliability level of the path TV is 0.6558, and R is 0.6. Therefore, in the process of changing the selected facilities, due to the influence of ω3, the reinforcement funds transferred from the path with higher reliability level to the path with lower reliability level can make up for the impact of the reduction of reinforcement funds on R. However, when B = 900, less edge reinforcement funds (50) are not enough to improve R to the level before the change of selected facilities. 4.2.3 Relationship between network reliability level, facility selection and budget From table 3 and figure 4, we can see that, on the whole, when ω3 is kept, the more the budget, the larger the R and the higher the curve. This can be understood as follows. When the selected facilities are unchanged, the cost of selected facilities is unchanged, and more budget means higher R. For example, when the budget is 800 and 850 respectively, the selected facilities are both V and C, the cost of selected facility is 780, and the cost of edge reinforcement is 20 and 70 respectively. As ω3 is 14, R is 0.528 and 0.611 respectively. When the budget is 950 and 1150 respectively, the selected facilities are both V and K, the cost of the selected facility is 850, and the cost of edge reinforcement is 100 and 300 respectively. As ω3 is 12, R is 0.639 and 0.898 respectively. The size of the budget can not only affect R, but also influences the choice of facilities in some cases. More budgets provide more possibilities for selecting facilities. If more costs of site selection mean smaller total service distance, then this site selection is possible. When B = 850, the selected facilities are V and C with a total service distance of 158, while when B = 950, the selected facilities are V and C with a total service distance of 139. The reason why the selected facilities change is precisely because the increase of budget provides more choices for selecting facilities. In new facility selection, there is a combination of facilities with less total service distance, which is more conducive to minimizing the objective. From table 3 and the above analyses, it can be seen that under the same ω3, when the selected facilities are unchanged, the more the budget, the higher the R. Figure 6 is the network reliability level curve when the budget is from 800 to 1150 and ω3 is 14. When B = 900, there is a decline in network reliability level, which is caused by the change of selected facilities. In other parts of the curve, R increases with the increase of budget. Moreover, in the latter part of the curve, with the increase of budget, R basically rises linearly. Therefore, in order to achieve higher R, we can consider investing more budget. In this paper, the formula (14) is actually to realize the bi-objective model 1. That is, our ultimate goal https://doi.org/10.15837/ijccc.2022.1.4573 13 Table 6: Solution results of the selected path (SP), total service distance (TSD), selected facilities (SF), cost of selected facilities (CSF), reinforced edges (RE) and cost of edge reinforcement (CER) B ω3 SP TSD SF CSF RE CER 800 [0-3] OU-UV, LD-DC, TV 158 C, V 780 OU, DL 20 [4-6], [8-14] OU-UV, LD-DC, TV 158 C, V 780 OU, TV, DL 20 [7] OU-UV, LD-DC, TV 158 C, V 780 OU, TV, DL, KL 20 850 [0-4] OU-UV, LD-DC, TV 158 C, V 780 OU, TV, DL 70 [5-14] OU-UV, LD-DC, TV 158 C, V 780 OU, UV, TV, CD, DL 70 875 [0-1] OU-UV, LD-DC, TV 158 C, V 780 OU, TV, DL 95 [2] OU-UV, LD-DC, TV 158 C, V 780 OU, TV, CD, DL 95 [3-14] OU-UV, LD-DC, TV 158 C, V 780 OU, UV, TV, CD, DL 95 900 [0] OU-UV, LD-DC, TV 158 C, V 780 OU, TV, DL 120 [1] OU-UV, LD-DC, TV 158 C, V 780 OU, TV, CD, DL 120 [2-14] OU-UV, LK, TV 139 V, K 850 OU, TV, KL 50 925 [0] OU-UV, LD-DC, TV 158 C, V 780 OU, TV, CD, DL 145 [1-3], [5], [7-8] OU-UV, LK, TV 139 V, K 850 OU, TV, LK 75 [4], [6], [9-14] OU-UV, LK, TV 139 V, K 850 OU, UV, TV, LK 75 950 [0] OU-UV, LK, TV 139 V, K 850 OU, TV 100 [1-3] OU-UV, LK, TV 139 V, K 850 OU, TV, LK 100 [4-14] OU-UV, LK, TV 139 V, K 850 OU, UV, TV, LK 100 1000 [0-1] OU-UV, LK, TV 139 V, K 850 OU, TV, LK 150 [2-14] OU-UV, LK, TV 139 V, K 850 OU, UV, TV, LK 150 1050 [0] OU-UV, LK, TV 139 V, K 850 OU, TV, LK 200 [1-14] OU-UV, LK, TV 139 V, K 850 OU, UV, TV, LK 200 1100 [0-14] OU-UV, LK, TV 139 V, K 850 OU, UV, TV, LK 250 1150 [0-14] OU-UV, LK, TV 139 V, K 850 OU, UV, TV, LK 300 1175 [0-14] OU-UV, LK, TV 139 V, K 850 OU, UV, TV, LK 325 Table 7: B=925, the reliability level of each edge on each selected path (SP) before and after rein- forcement SP OU-UV SP TV SP LD-DC SP LK ω3 f TR R Be Af Be Af Be Af Be Af Be Af Be Af OU OU UV UV TV TV DC DC LD LD LK LK 0 0.0338 2.2206 0.600 0.5 0.6000 0.6 0.6000 0.5 1.000 0.6 0.6206 0.5 0.6206 0.5 0.5000 1 0.0005 1.8798 0.600 0.5 0.6000 0.6 0.6000 0.5 0.6558 0.6 0.6000 0.5 0.500 0.5 0.6240 2 0.0004 1.8794 0.600 0.5 0.6000 0.6 0.6000 0.5 0.6475 0.6 0.6000 0.5 0.500 0.5 0.6320 3 0.0004 1.8793 0.600 0.5 0.6000 0.6 0.6000 0.5 0.6445 0.6 0.6000 0.5 0.500 0.5 0.6348 4 0.0004 1.8792 0.600 0.5 0.6000 0.6 0.6000 0.5 0.6431 0.6 0.6000 0.5 0.500 0.5 0.6361 5 0.0004 1.8792 0.600 0.5 0.6000 0.6 0.6000 0.5 0.6421 0.6 0.6000 0.5 0.500 0.5 0.6371 6 0.0004 1.8792 0.600 0.5 0.6000 0.6 0.6000 0.5 0.6425 0.6 0.6000 0.5 0.500 0.5 0.6367 7 0.0004 1.8792 0.600 0.5 0.6000 0.6 0.6000 0.5 0.6418 0.6 0.6000 0.5 0.500 0.5 0.6374 8 0.0003 1.8791 0.600 0.5 0.6000 0.6 0.6000 0.5 0.6413 0.6 0.6000 0.5 0.500 0.5 0.6379 9 0.0003 1.8789 0.600 0.5 0.6004 0.6 0.6004 0.5 0.6406 0.6 0.6000 0.5 0.500 0.5 0.6379 10 0.0003 1.8776 0.602 0.5 0.6025 0.6 0.6025 0.5 0.6385 0.6 0.6000 0.5 0.500 0.5 0.6365 11 0.0002 1.8764 0.604 0.5 0.6043 0.6 0.6043 0.5 0.6373 0.6 0.6000 0.5 0.500 0.5 0.6348 12 0.0002 1.8751 0.606 0.5 0.6064 0.6 0.6064 0.5 0.6354 0.6 0.6000 0.5 0.500 0.5 0.6333 13 0.0002 1.8747 0.607 0.5 0.6071 0.6 0.6071 0.5 0.6350 0.6 0.6000 0.5 0.500 0.5 0.6326 14 0.0001 1.8740 0.608 0.5 0.6081 0.6 0.6081 0.5 0.6336 0.6 0.6000 0.5 0.500 0.5 0.6323 Selected path: SP; Total reliability level of network: TR; Before: Be; After: Af. https://doi.org/10.15837/ijccc.2022.1.4573 14 Table 8: Solution results of total reliability level of network under different budgets ω3 B 800 850 875 900 925 950 1000 1050 1100 1150 0 1.6278 1.8762 1.9952 2.1143 2.2206 2.0048 2.2364 2.4636 2.6571 2.8000 1 1.6278 1.8762 1.9952 2.1136 1.8798 1.9960 2.2285 2.4474 2.6340 2.8000 2 1.6278 1.8762 1.9874 1.7632 1.8794 1.9957 2.2082 2.3972 2.5863 2.7759 3 1.6260 1.8762 1.9708 1.7630 1.8793 1.9955 2.1901 2.3799 2.5705 2.7606 4 1.6238 1.8762 1.9622 1.7630 1.8792 1.9909 2.1811 2.3717 2.5622 2.7532 5 1.6213 1.8749 1.9570 1.7630 1.8792 1.9849 2.1757 2.3666 2.5577 2.7491 6 1.6196 1.8714 1.9536 1.7630 1.8792 1.9809 2.1719 2.3629 2.5545 2.7457 7 1.6182 1.8689 1.9512 1.7630 1.8792 1.9783 2.1694 2.3605 2.5520 2.7440 8 1.6175 1.8668 1.9492 1.7629 1.8791 1.9760 2.1672 2.3587 2.5503 2.7423 9 1.6168 1.8656 1.9480 1.7629 1.8789 1.9745 2.1661 2.3575 2.5489 2.7406 10 1.6163 1.8641 1.9468 1.7629 1.8776 1.9731 2.1646 2.3561 2.5479 2.7400 11 1.6157 1.8632 1.9461 1.7628 1.8764 1.9722 2.1637 2.3553 2.5473 2.7390 12 1.6153 1.8622 1.9453 1.7628 1.8751 1.9710 2.1630 2.3545 2.5468 2.7384 13 1.6152 1.8616 1.9443 1.7626 1.8747 1.9705 2.1623 2.3538 2.5462 2.7377 14 1.6147 1.8608 1.9440 1.7626 1.8740 1.9697 2.1616 2.3535 2.5456 2.7374 Table 9: Results of solving the overall objective under different budgets ω3 B 800 850 875 900 925 950 1000 1050 1100 1150 0 0.0001 -0.0001 0.1366 0.1366 0.1369 0.1351 0.1015 0.1238 0.1483 0.1495 1 0.0019 0.0012 0.1450 0.1585 0.1541 0.1412 0.1150 0.1488 0.1734 0.1584 2 0.0037 0.0025 0.1532 0.1662 0.1546 0.1434 0.1237 0.1583 0.1818 0.1651 3 0.0053 0.0038 0.1574 0.1663 0.1549 0.1455 0.1274 0.1614 0.1846 0.1676 4 0.0064 0.0051 0.1595 0.1664 0.1553 0.1475 0.1292 0.1630 0.1860 0.1689 5 0.0072 0.0063 0.1608 0.1665 0.1557 0.1487 0.1303 0.1639 0.1868 0.1696 6 0.0078 0.0073 0.1617 0.1666 0.1560 0.1496 0.1310 0.1646 0.1874 0.1701 7 0.0081 0.0080 0.1623 0.1666 0.1564 0.1502 0.1315 0.1650 0.1878 0.1705 8 0.0084 0.0085 0.1627 0.1667 0.1567 0.1506 0.1319 0.1653 0.1881 0.1707 9 0.0086 0.0089 0.1631 0.1668 0.1571 0.1510 0.1322 0.1656 0.1883 0.1710 10 0.0088 0.0092 0.1634 0.1669 0.1574 0.1513 0.1325 0.1658 0.1885 0.1711 11 0.0089 0.0094 0.1636 0.1670 0.1576 0.1515 0.1327 0.1660 0.1887 0.1713 12 0.0091 0.0097 0.1638 0.1670 0.1578 0.1517 0.1328 0.1661 0.1888 0.1714 13 0.0092 0.0099 0.1640 0.1671 0.1580 0.1518 0.1330 0.1663 0.1889 0.1715 14 0.0092 0.0100 0.1641 0.1672 0.1582 0.1520 0.1331 0.1664 0.1890 0.1715 https://doi.org/10.15837/ijccc.2022.1.4573 15 Table 10: The result when B=1150 ω3 g g1 g2 g3 R SF RE CSF CER 0 0.1494 139 2.8000 0.0089 0.800 ’V’, ’K’ OU, UV, TV, KL 850 300 1 0.1584 139 2.8000 0.0089 0.800 ’V’, ’K’ OU, UV, TV, KL 850 300 2 0.1651 139 2.7759 0.0038 0.839 ’V’, ’K’ OU, UV, TV, KL 850 300 3 0.1676 139 2.7606 0.0016 0.863 ’V’, ’K’ OU, UV, TV, KL 850 300 4 0.1689 139 2.7532 0.0009 0.875 ’V’, ’K’ OU, UV, TV, KL 850 300 5 0.1696 139 2.7491 0.0006 0.881 ’V’, ’K’ OU, UV, TV, KL 850 300 6 0.1701 139 2.7457 0.0004 0.887 ’V’, ’K’ OU, UV, TV, KL 850 300 7 0.1705 139 2.7440 0.0003 0.889 ’V’, ’K’ OU, UV, TV, KL 850 300 8 0.1707 139 2.7423 0.0002 0.892 ’V’, ’K’ OU, UV, TV, KL 850 300 9 0.1710 139 2.7406 0.0002 0.895 ’V’, ’K’ OU, UV, TV, KL 850 300 10 0.1711 139 2.7400 0.0002 0.896 ’V’, ’K’ OU, UV, TV, KL 850 300 11 0.1713 139 2.7390 0.0001 0.897 ’V’, ’K’ OU, UV, TV, KL 850 300 12 0.1714 139 2.7384 0.0001 0.898 ’V’, ’K’ OU, UV, TV, KL 850 300 13 0.1715 139 2.7377 8.784 × 10−5 0.899 ’V’, ’K’ OU, UV, TV, KL 850 300 14 0.1715 139 2.7374 8.09 × 10−5 0.900 ’V’, ’K’ OU, UV, TV, KL 850 300 Selected facilities: SF; Reinforced edges: RE; Cost of selected facilities: CSF; Cost of edge reinforcement: CER. is to minimize the total service distance and maximize R in model 1, instead of minimizing g in formula (14). It can be seen from table 9 that under the same budget, with the increase of ω3, the total objective of Model 2 is rising, but the network reliability level is rising when selected facilities are unchanged. Therefore, in order to obtain the higher R, we can select the solution with the larger ω3. In this case, we can choose the solution when ω3 = 14. For example, when B = 1150, the selected facilities are V and K, and the selected paths are OU-UV, TV and LK, with a total service distance of 139 and a network reliability level of 0.900, as shown in table 10. Figure 7 is the distribution diagram between facilities and demand points when B = 1150. The thick black lines in the figure represent the reinforced edges, and the arrows point to the facilities serving the demand points. Figure 6: The network reliability level under different budgets when variance weight is 14 Figure 7: B=1150, distribution diagram between facilities and demand points 5 Conclusions In this paper, two definitions of network reliability level are given, and the equivalence of these two definitions is proven. By using the definition of network reliability level from the perspective of path, a model is established with the goal of minimizing the total service distance and maximizing the network reliability level under the condition of constant budget. The goal of maximizing network reliability level is decomposed into two goals, namely, maximizing the total reliability level of the network and minimizing the variance of the reliability level of each selected path. Then, a three-objective model is obtained from the original model. A single objective model is obtained by weighting three objectives. Finally, this model is applied to a case study. The solution results of the model, including the choice of facilities, the choice of paths, the total reliability level of the network, the network reliability level, the edge of reinforcement and the process of edge reinforcement, have strong regularity, https://doi.org/10.15837/ijccc.2022.1.4573 16 which not only shows the rationality of defining the network reliability level from the perspective of paths, but also fully verifies the feasibility and stability of the model. In formula (14), the variance weight has an expected impact on the fluctuation of the reliability levels of the selected paths. The successful operation of the model provides a good choice for the emergency management department to choose appropriate emergency facilities and reinforce roads. In addition, we think the results can be generalized and embedded in a real-time decision support system meant for crisis prevention and loss mitigation [41], [42]. This model can also be established by using the definition of network reliability level from the perspective of minimal edge cut, which is the envisaged continuation of the research. Future research will include presenting more demand points and location facilities for more complex networks to solve the model. Conflict of interest No potential conflict of interest was reported by the authors. References [1] Chen, Q. H., Chen, H., Wang, J. X., et al. Impacts of climate change and land-use change on hydrological extremes in the Jinsha river basin. Water, 11(7): 1398, 2019. https://doi.org/10.3390/w11071398. [2] Zhang, W. T., Yun, Y. X. Multi-scale accessibility performance of shelters types with diversity layout in coastal port cities: A case study in Nagoya city, Japan. Habitat International, 83: 55-64, 2019. https://doi. org/10.1016/j.habitatint.2018.11.002. [3] Wu, H. Y., Xu, Z. S., Ren, P. J. Addressing site selection for earthquake shelters with hesitant multiplicative linguistic preference relation. Information Sciences, 516: 370-387, 2020. https://doi.org/10.1016/j.ins.20 19.12.059. [4] Faas, A. J., Velez, A. L. K., Nowell, B. L., et al. Methodological considerations in Pre- and Post-emergency network identification and data collection for disaster risk reduction: Lessons from wildfire response networks in the American northwest. International Journal of Disaster Risk Reduction, 40: 101260, 2019. https://doi.org/10.1016/j.ijdrr.2019.101260. [5] Liao, H. C., Si, G. S., Xu, Z. S., Fujita, H. Hesitant fuzzy linguistic preference utility set and its application in selection of fire rescue plans. International Journal of Environmental Research and Public Health, 15(4), 664, 2018. https://doi.org/10.3390/ijerph15040664. [6] Goodie, A. S., Sankar, A. R., Doshi, P. Experience, risk, warnings, and demographics: Predictors of evacuation decisions in hurricanes Harvey and Irma. International Journal of Disaster Risk Reduction, 41: 101320, 2019. https://doi.org/10.1016/j.ijdrr.2019.101320. [7] Zhou, L., Xu, Z. S., Wu, X. H., Fujita, H. Emergency decision making for natural disasters: An overview. International Journal of Disaster Risk Reduction, 27: 567-576, 2018. https://doi.org/10.1016/j.ijdrr.2017. 09.037. [8] Xu, J. H., Yin, X. Z., Chen, D. C., et al. Multi-criteria location model of earthquake evacuation shelters to aid in urban planning. International Journal of Disaster Risk Reduction, 20: 51-62, 2016. https://doi.org/ 10.1016/j.ijdrr.2016.10.009. [9] Men, J. K., Jiang, P., Zheng, S., et al. A multi-objective emergency rescue facilities location model for catastrophic interlocking chemical accidents in chemical parks. IEEE Transactions on Intelligent Trans- portation Systems, 21(11): 4749 -4761, 2020. https://doi.org/10.1109/TITS.2019.2946209. [10] Hakimi, S. L. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3): 450-459, 1964. https://doi.org/10.1287/opre.12.3.450. [11] Berman, O., Krass, D., Menezes, M. B. C. Facility reliability issues in network p-Median problems: Strategic centralization and co-Location effects. Operations Research, 55(2): 332-350, 2007. https://doi. org/10.1287/opre.1060.0348. [12] Coutinho-Rodrigues, J., Tralhão, L., Alçada-Almeida, L. Solving a location-routing problem with a mul- tiobjective approach: The design of urban evacuation plans. Journal of Transport Geography, 22(2): 206-218, 2012. https://doi.org/10.1016/j.jtrangeo.2012.01.006. https://doi.org/10.15837/ijccc.2022.1.4573 17 [13] Rabta, B., Wankmüller, C., Reiner, G. A drone fleet model for last-mile distribution in disaster relief operations. International Journal of Disaster Risk Reduction, 28: 107-112, 2018. https://doi.org/10.1016/ j.ijdrr.2018.02.020. [14] Trivedi, A., Singh, A. A hybrid multi-objective decision model for emergency shelter location-relocation projects using fuzzy analytic hierarchy process and goal programming approach. International Journal of Project Management, 35(5): 827-840, 2017. https://doi.org/10.1016/j.ijproman.2016.12.004. [15] Bai, X. J. Two-stage multiobjective optimization for emergency supplies allocation problem under in- tegrated uncertainty. Mathematical Problems in Engineering, 2016. https://doi.org/10.1155/2016/2823 835. [16] Lee. S. H. Reliability evaluation of a flow network. IEEE Transactions on Reliability, R-29(1): 24-26, 1980. https://doi.org/10.1109/TR.1980.5220695. [17] Arunkumar, S., Lee, S. H. Enumeration of all minimal cut-sets for a node pair in a graph. IEEE Trans- actions on Reliability, R-28(1): 51-55, 1979. https://doi.org/10.1109/TR.1979.5220473. [18] Lin, P. M., Leon, B. J., Huang, T. C. A new algorithm for symbolic system reliability analysis. IEEE Transactions on Reliability, R-25(1): 2-15, 1976. https://doi.org/ 10.1109/TR.1976.5214942. [19] Aggarwal, K. K., Gupta, J. S., Misra, K. B. A simple method for reliability evaluation of a communication system. IEEE Transactions on Communications, 23(5): 563-566, 1975. https://doi.org/10.1109/TCOM.1 975.1092838. [20] Lin, Y. K., Chen, S. G. A maximal flow method to search for d-MPs in stochastic-flow networks. Journal of Computational Science, 22: 119-125, 2017. https://doi.org/10.1016/j.jocs.2017.09.009. [21] Xue, J. On multistate system analysis. IEEE Transactions on Reliability, R-34(4): 329-337, 1985. https:// doi.org/ 10.1109/TR.1985.5222178. [22] Chen, S. G., Lin, Y. K. Search for all minimal paths in a general large flow network. IEEE Transactions on Reliability, 61(4): 949-956, 2012. https://doi.org/10.1109/TR.2012.2220897. [23] Yeh, W. C. A simple algorithm to search for all d-MPs with unreliable nodes. Reliability Engineering & System Safety, 73(1): 49–54, 2001. https://doi.org/10.1016/S0951-8320(01)00032-1. [24] Zuo, M. J., Tian, Z. and Huang, H. Z. An efficient method for reliability evaluation of multistate networks given all minimal path vectors. IIE Transactions, 39(8): 811-817, 2007. https://doi.org/10.1080/0740817 0601013653. [25] Chen, S. G., Lin, Y. K. Searching for d-MPs with fast enumeration. Journal of Computational Science, 17(1): 139–147, 2016. https://doi.org/10.1016/j.jocs.2016.05.011. [26] Alkaff, A. Discrete time dynamic reliability modeling for systems with multistate components. Reliability Engineering & System Safety, 209: 107462, 2021. https://doi.org/10.1016/j.ress.2021.107462. [27] Yeh, W. C. A quick BAT for evaluating the reliability of binary-state networks. Reliability Engineering & System Safety, 216: 107917, 2021. https://doi.org/10.1016/j.ress.2021.107917. [28] Huang, D. H., Huang, C. F., Lin, Y. K. A binding algorithm of lower boundary points generation for network reliability evaluation. IEEE Transactions on Reliability, 69(3): 1087-1096, 2020. https://doi.or g/10.1109/TR.2019.2924448. [29] Khanna, G., Chaturvedi, S. K., Soh, S. Two-terminal reliability analysis for time-evolving and predictable delay-tolerant networks. Recent Advances in Electrical & Electronic Engineering, 13(2): 236-250, 2020. https://doi.org/10.2174/2213111607666190215121814. [30] Garg, M., Smith, J. C. Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios. Omega, 36(6): 1057-1071, 2008. https://doi.org/10.1016/j.omega.2006.05. 006. [31] Lee, H. W., Lee, K., Modiano, E. Maximizing reliability in WDM networks through lightpath routing. IEEE/ACM Transactions on Networking, 22(4): 1052-1066, 2014. https://doi.org/10.1109/TNET.2013.2 266666. https://doi.org/10.15837/ijccc.2022.1.4573 18 [32] Ahmadi, M., Seifi, A., Tootooni, B. A humanitarian logistics model for disaster relief operation considering network failure and standard relief time: A case study on San Francisco district. Transportation Research Part E, 75: 145-163, 2015. https://doi.org/10.1016/j.tre.2015.01.008. [33] Migov, D. A. Vertex decomposition to calculate the network probabilistic connectivity. Prikladnaya Diskretnaya Matematika, 47: 62-86, 2020. https://doi.org/ 10.17223/20710410/47/6. [34] Horner, M. W., Widener, M. J. The effects of transportation network failure on people’s accessibility to hurricane disaster relief goods: A modeling approach and application to a Florida case study. Natural Hazards, 59(3): 1619-1634, 2011. https://doi.org/10.1007/s11069-011-9855-z. [35] Zhang, Z. Y., Shao, F, M., Zhang, N., et al. Maximizing k-Terminal network reliability in some sparse graphs. IEEE/ACM Transactions on Networking, 29(1): 190-202, 2021. https://doi.org/10.1109/TNET.2 020.3030819. [36] Yu, W. Y. Reachability guarantee based model for Pre-positioning of emergency facilities under uncertain disaster damages. International Journal of Disaster Risk Reduction, 42: 101335, 2020. https://doi.org/ 10.1016/j.ijdrr.2019.101335. [37] Peeta, S., Salman, F. S., Gunnec, D., Viswanath, K. Pre-disaster investment decisions for strengthening a highway network. Computers & Operations Research, 37(10): 1708-1719, 2010. https://doi.org/ 10.10 16/j.cor.2009.12.006. [38] Amin, S., Tamima, U., Amador, L. Optimal pavement management: Resilient roads in support of emer- gency response of cyclone affected coastal areas. Transportation Research Part A: Policy and Practice, 119: 45-61, 2019. https://doi. org/10.1016/j.tra.2018.11.001. [39] Vahdani, B., Veysmoradi, D., Shekari, N., Mousavi, S. M. Multi-objective, multi-period location-routing model to distribute relief after earthquake by considering emergency roadway repair. Neural Computing & Applications, 30(3): 835-854, 2018. https://doi.org/10.1007/s00521-016-2696-7. [40] Hu, S. L., Han, C. F., Meng, L. P. Stochastic optimization for investment in facilities in emergency prevention. Transportation Research Part E, 89: 14-31, 2016. https://doi.org/10.1016/j.tre.2016.02.006. [41] Filip, F. G. Decision support and control for large-scale complex systems. Annual Reviews in Control, 32(1): 61-70, 2008. https://doi.org/10.1016/j.arcontrol.2008.03.002. [42] Filip, F. G., Zamfirescu, C. B., Ciurea, C. Computer-supported collaborative decision-making. Springer, 2017. http://link.springer.com/book/10.1007/978-3-319-47221-8. Copyright ©2022 by the authors. Licensee Agora University, Oradea, Romania. This is an open access article distributed under the terms and conditions of the Creative Commons Attribution-NonCommercial 4.0 International License. Journal’s webpage: http://univagora.ro/jour/index.php/ijccc/ This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE). https://publicationethics.org/members/international-journal-computers-communications-and-control Cite this paper as: Wang Y.; Xu Z.; Filip F.G. (2022). Multi-Objective Model to Improve Network Reliability Level under Limited Budget by Considering Selection of Facilities and Total Service Distance in Rescue Operations, International Journal of Computers Communications & Control, 17(1), 4573, 2022. https://doi.org/10.15837/ijccc.2022.1.4573 Introduction Methodology Basic concepts Reliability levels in the network Equivalence theorem Reinforcement of edges The model Case study Data Analysis Relationship between network reliability level, total reliability level and variance weight Relationship between facility location and variance weight Relationship between network reliability level, facility selection and budget Conclusions