ABSTRACT

The reliability of facility location problem has aroused wide concern recently. Many researchers focus on reliable and robust facility systems design under component failures and have obtained promising performance. However, the target and reliability of a facility system are to a large degree adversely affected by the edge failures in the network, which remains a deep study. In this paper, we focus on facility systems’ reliability subject to edge failures. For a facility location system, we formulate two models based on classical uncapacitated fixed-charge location problem under deterministic and stochastic cases. For a specific example, location decisions and the comparison of reliability under different location models are given. Extensive experiments verify that significant improvements in reliability can be attained simply by increasing the amount of operating cost.

Keywords:Facility System, Reliability, Edge Failure, Uncapacitated Fixed-Charge Location Problem

1. Introduction

A facility system can be structured as a connected graph in which the vertices represent entities and the edges represent facilities such as the paths of goods or information [1] . In this paper, we distinguish two kinds of facilities, “vertex facilities” and “edge facilities”. For simplicity, we call them “vertices” and “edges”, respectively.

Every facility system in operation may face various disruptions. Since the facility location decisions are hard to reverse, the location decisions are of great importance and have aroused great attention from researchers and practitioners recently [2] .

While most of the literatures focus on the reliable and robust facility system design and analysis under component failures, the existing works are mainly concentrated on the “node” (e.g. suppliers, distribution centers) losses [3] . Snyder [4] has researched the influence of vertex failure situations. The author formulates Maximum Failure Cost Reliability Models and Expected Failure Cost Reliability Models. But both of the models don’t take the edge failures into consideration, which are more likely to occur in reality.

In most cases, facility system disruptions are caused by the failures of edges, e.g., closure of highway because of the inclement weather, traffic jam, road damage caused by earthquakes or debris flows [5] . Wei et al. [1] formulated two models based on deterministic and stochastic cases to measure the loss in efficiency due to edge failures. But they have not solved the facility location problem, which can help making facility location decisions and has more realistic significance.

Once a facility system is constructed, it’s hardly to inverse. If some failure scenarios occurred, whether you can afford the increase of operating cost is of great significance. No techniques can completely eliminate a loss by reducing the edge loss failure probability to zero, so the location decision making based on the reliability is very important. As far as we know, researchers and practitioners have not paid enough attention to the impact of edge failures on the efficiency of a facility system by so far.

The uncapacitated fixed-charge location problem (UFLP) [6] is a classical combinatorial optimization problem that determines facility locations and assignments of customers to facilities in such a way that the sum of fixed and transportation costs is minimized. We assume that the network is connected after a disruption [7] .

Based on the UFLP model, the main contributions of our work are as follows:

1) We introduce edge failures into the facility location problems to choose the facilities satisfying the reliability requests.

2) Two models based on deterministic and stochastic cases are formulated and the experiment results indicate that under edge failure situations, our models perform better than UFLP.

3) The improved stochastic reliable model is proposed to reduce the calculation amount.

The remainder of this paper is organized as follows: Section 2 introduces the reliability theory. In Section 3, we first introduce the classical uncapacitated fixed-charge location problem, and then propose two reliable location models under deterministic and stochastic situations according to the reliability theory. We use a scenariobased algorithm to compute a specific example. The experimental results and corresponding analysis are presented in Section 4. Finally, we conclude this paper in Section 5.

2. Reliability Theory

In this section, we introduce the reliability theory to facility location problem. Snyder and Daskin [8] define the reliability of a system as the ability of a system to perform well even when parts of the system have failed. Once the facility location decisions are confirmed, the reliability can be treated as an inherent property of the system. It’s related to network reliability theory, which is concerned with calculating or maximizing the probability that a graph remains connected after random failures due to congestion, disruptions, or blockages.

In this paper, the system’s reliability, denoted by, is defined to be the ratio of the system’s operating cost to the cost after some edges have failed [1] .

3. Reliable Facility Location Models

We view a facility system as a weighted connected simple graph, where; is the edge set with the edges denoting goods or information paths; is the vertex weight set with the weight of vertex i, denoting the demand of customer i, and is the edge weight set with the weight of edge, denoting the length between and under the existing conditions. By we also denote the shortest path length (or distance) between and if.

The following are the notations for our formulations.

Sets

: set of customers, indexed by.

: set of potential facility locations, indexed by.

Parameters

: demand at customer.

: fixed cost of open a facility at.

: delivery cost per unit per length.

The uncapacitated fixed-charge location problem (UFLP) [6] is a classical facility location problem that chooses facility locations and assignments of customers to facilities to minimize the sum of fixed and transportation costs. For simplicity, we call it “cost”.

Assume that is an feasible solution of the UFLP, i.e., , if a facility is established at location; 0,otherwise. The model of UFLP is as follows:

Min (1)

s.t.(2)

(3)

(4)

(5)

The objective function (1) minimizes the sum of the fixed cost for opening the facilities and the demand weighted total distance. Constraints (2) stipulate that each customer is assigned to exactly one facility, while constraints (3) limit assignments to open sites. Finally, constraints (4) and (5) are integrality constraints.

Let be the set of all feasible solutions and be the potential failure edge set, where the edge failure is defined as an edge losses its designed function completely. Therefore, a failed edge in is equivalent to delete (or close) the corresponding line from the facility system. We also assume that edge failures are independent and multiple edge failures may occur simultaneously.

Considering the edge loss scenarios, we define as set of all the edge loss scenarios. We define the edge loss level as the number of edges which fail simultaneously. Let be the set of scenarios corresponding to the closure or deletion of edges from, i.e., every explicitly specifies the failed edges in F.

We distinguish two cases: deterministic and stochastic, to formulate the UFLP-based reliability analysis models that evaluate the reliability of a facility system after some edges have failed.

3.1. Deterministic Facility Location Model

During the period of facility location design, the designer will always consider a question: under a specific edge loss level, if a failure scenario happened, the increased cost of serving all the customer in the network whether can be endured or not. As to every feasible solution, we have an operating cost under a specific scenario. Under the above consideration, it’s necessary to consider the worst scenario of every specific feasible solution in under edge level, and find out the lowest cost one.

We formulate the following deterministic reliability model(DRM) to minimum the maximal cost under a given edge loss level:

(6)

s.t. (7)

(8)

(9)

(10)

(11)

The objective function (6) and (7) minimize the maximum operating cost under the worst scenario in (i.e. (7) restricts the maximum operating cost of the worst scenario under a given level and a specific feasible solution, while (6) minimizes the worst operating cost of all feasible solutions). Under a specific scenario, constraints (8) stipulate that each customer is assigned to exactly one facility, while constraints (9) limit assignments to open sites. Finally, constraints (10) and (11) are integrality constraints.

3.2. Stochastic Facility Location Model

In section 3.1, we have discussed the case where the loss level is a certainty. We now consider the case where loss is not a certainty upon an edge failure. Usually, the chances of losing an edge are based upon some probability. We wish to derive the expected efficiencies associated with an existing system. To do this we need to take every scenario and it’s probability into consideration. Let be the failure probability of edge. We denote the set as the failure edge in scenario, and as the probability of scenario.

(12)

We formulate the following stochastic reliability model (SRM):

(13)

s.t. (14)

(15)

(16)

(17)

The objective function (13) minimizes the expected operating cost under every possible failure scenario. Constraints (14) stipulate that each customer is assigned to exactly one facility under a specific failure scenario, while constraints (15) limit assignments to open sites. Finally, constraints (16) and (17) are integrality constraints.

3.3. Improvement of the Stochastic Model

In this section, we introduce a new parameter confidence level, indexed by which is a predefined number and takes value from (0,1). We introduce the concept of interval estimation. If there exist two positive integer which satisfy the equation

(18)

then we take the probability of to fall into as. And the interval is the interval estimation of.

Noting that the edge loss level obeys the Multivariate Bernoulli distribution. Given the failure probability, we can easily get. So it’s easy to get the interval estimation of. Considering the low probability of the case when fall into the interval, we take no account of this interval. Let, and the model (13)-(17) can be modified as the improved stochastic reliability model(ISRM):

(19)

s.t. (20)

(21)

(22)

(23)

The objective function (19) minimizes the expected cost under the scenarios in. Constraints (20) stipulate that each customer is assigned to exactly one facility under a specific failure scenario, while constraints (21) limit assignments to open sites. Finally, constraints (22) and (23) are integrality constraints.

Obviously, the main difference between ISRM and SRM is just its neglect of low probability scenarios, which lead to the remarkable reduction in complexity.

4. Experiment and Reliability Analysis

In this section we apply the DRM and the SRM to a data set to get the facility location decisions and compare them with the classical UFLP. Given the edge loss level, one can easily enumerate each of the possible scenarios as well as calculate the operating cost under each specific scenario and find out the worst one. The ratio of systems efficiency and the worst operating cost under the edge loss level is defined as the systems reliability under a specific level.

Obviously the efficiency is measured at 100% if all edges are operating normally. If an edge is lost due to a natural disaster, intentional strike or planned closure, then the shortest paths from facilities to consumers will change, and the delivery scheme should be adjusted simultaneously.

The results of this series of calculations will define a series of reliability from (i.e. all edges are operating well) to (i.e. all edges in are lost). We can compare the reliability of different facility location models under different edge loss level. Note that once the facility location has been determined, we assume that it can’t be reversed.

Our data set is derived from the 2008 China census data: a 49-node set consisting of the capitals of all the provinces in China plus the two special administrative regions Hong Kong and Macao, as well as other 15 big cities [1] . The demand of city, is settled to be the city’s administrative region population divided by 10000. The transportation links (edges) are set to the recent national highways and the transportation costs per unit per length through different roads are all set to. The fixed cost of facilities setup are estimated by considering the factors such as local labor price, facility size, and other natural conditions. The potential failure edges set are consisted of 8 edges, . And the corresponding probability are given in Table 1.

By using the above data set we optimally solve a UFLP to site an existing facility system, the solutions are given in Table 2. In Table 2, the serving facilities set are fixed as the optimal solution of UFLP without edge failure. For each loss level, Objec.Value is the fixed and transportation cost under the worst scenario. The corresponding failed edges and the reliability are given as well. In Table 2, column 5 demonstrates that reliability drops down to 79.20% with the increase of level. And the reliability drops quickly by 17.87% from to while it drops slowly by 2.93% form to, relatively. From column 2, we find that the edges 2, 4, 5, 7, 8 always appear in the failed edges set, which demonstrate that a minority of failed edges may play the leading role in system’s reliability.

In Table 3, column 3 is the location decisions correspond to the worst scenarios with edge loss levels in column 1. The Objec.Values in column 4 are fixed and transportation cost under location decisions in column 3 and failed edges in column 2. From column 3, we find that location decisions under different level is very similar to each other, especially when r = 4, 6, 7, 8, the location decisions are exactly the same. This discovery indicates that the system’s reliability are affected by some specific serving facilities. When all edges are in operation, the system’s reliability is measured at 100%. The reliability drops down to 93.11% with the increase of level, and its falling speed exhibits the same characteristics as that in UFLP(see Table 2), which slow down gradually.

In Table 4, we use the SRM to find out the optimal location decisions in column 3. The worst failed edges set are given in column 2. The reliability’s variation shows the same properties as that of DRM in Table 3. The reliability fall from 100% where no edge losses to 94.88% where the worst scenario of edge loss level.

We compare the reliability and operating cost of UFLP, DRM and SRM in Table 5. From Table 5, we can see:

1) In the deterministic cases, when the edge loss level, UFLP and DRM have the same results of operating cost as 9197100. But under a given edge loss level, the operating cost of UFLP will exceed the cost of DRM, and the reliability of the UFLP will drop dramatically, while that of DRM drops slightly. For example, when, the costs of UFLP and DRM are 11,413,215 and 9,868,450, while the corresponding reliability is 80.58% and 93.20%.

2) In the stochastic cases, the decision made by SRM is a little inferior to one chose by classical UFLP on operating cost when all edges are operating well. But once the edge losses occur, the operating cost of UFLP will increase to 11,612,964, and its reliability drops fast to 79.2%. On the contrary, the serving facilities selected by our proposed SRM perform very well. Its cost is only 9903637 and the reliability drops slightly to 94.88%. Both of the cost and the reliability perform better than the classical UFLP. Figure 1 shows the variation of the reliability.

As to the improved stochastic reliability model, Table 6 shows the probability of different edge loss levels. We draw out the probability distribution of, see Figure 2. The advantage of our handling is that it can simplify the calculation and we can get the roughly estimation of operating cost under different edge loss levels. Table 7 gives out the reliability and operating cost of ISRM.

5. Summary and Conclusion

In this paper, we propose two types of scenario based facility location models in order to make facility location decisions which can improve the system’s reliability. We distinguish deterministic and stochastic cases to formulate and compute a specific example. We have successfully made the location decisions. Reliability of two different location models is also given and is compared with the classical UFLP model.

1) As to a facilities fixed system, if all edges are in operation, the classical UFLP will get the optimal solution with the lowest operating cost, but once the edge failure situations occur, the operating cost will increase dramatically.

2) Under different location schemes, the edge set which plays the leading role of systems reliability is different. In other words, each edge’s influence on system’s reliability depends on its conjoint facilities.

3) By increasing a small amount of operating cost, we can get a much more reliable location design.

According to the practical situations, our models can be improved in the following ways. Firstly, we assume that the edge failures are independent from each other, but in practice, once an edge failed, the function of its adjacent edges will be impacted. Secondly, we assume that the edges are not limited on transport capacity, which is not real. Thirdly, through our analysis, we also find that under different edge loss levels, the facility location designs don’t differ too much from each other. So the location decisions are relevant to the network’s inherent properties. It’s important to filter out some facilities as the alternative facility set, which can reduce the number of feasible solutions without losing the optimal solution. Thereby, the calculation amount can be reduced a lot. Modeling the reliable facility location problems and related problems under this situation are worthy of study.

Acknowledgements

This work was supported by the national college student innovative entrepreneurial training project (Grant No. 201310699066), NSRP (Grant No. 2012JC2-03) and ESF (Grant No. 12JK0888). The authors are grateful to the anonymous referees of this article.

References

NOTES

^*Corresponding author.