Abstract: The standard uncapacitated facility location problem requires locating facilities on a network to service the demands on the network at a minimum total cost. It is assumed that the demand at each customer site must be satisfied. In this study we considered a generalized version of the problem where the demands are not known precisely (i.e., fuzzy) which makes the cost imprecise and has triangular possibility distribution. A numerical example is considered to illustrate the methodology.

INTRODUCTION

The Uncapacitated Facility Location Problem (UFLP) is a classical discrete location problem that has been widely studied and for which efficient techniques to obtain solutions are well known. This problem consists of opening a set of facilities among a potential set of locations to allocate a given set of customers in order to minimize the set-up cost of opening the facilities plus the cost of allocating the clients. In the Uncapacitated Facility Location (UFL) problem the cost of satisfying the client requirements has two components a fixed cost component of setting up a facility in a given site and a transportation cost component of satisfying the customer requirements. The UFL problems are also called the simple facility location problem, the simple (or uncapacitated) warehouse location problem or the simple (or uncapacitated) plant location problem in the literature. Many successful UFL model applications have been provided to some problems. The bank account location problem, net-work design, vehicle routing, distributed data and communication networks (Ghosh, 2003), cluster analysis, machine scheduling, economic lot sizing, portfolio management (Gen et al., 1996) are the some instance without facilities to locate problems that can be modeled as an UFL problem.

UFL problems have been studied and examined extensively by various attempts and approaches (Kratica et al., 2001). All important approaches relevant to UFL problems can be classified into two main categories: exact algorithm such as branch and bound, primal and dual ascent methods, linear programming and Lagrangean relaxation algorithms and metaheuristic based methods (Aydin and Fogarty, 2004). Erlenkotter (1978) developed a dual approach for the UFL problem. Although this dual approach is an exact algorithm, it can also be used as a heuristic to find good solutions. Kratica et al. (2001) have shown that genetic algorithms find optimal solutions on the OR Library with very good efficiency. presents Neighborhood Search Heuristics for the Uncapacitated Facility Location Problem. In addition artificial neural network approaches has been proposed to solve UFL problems by Gen et al. (1996) and Vaithyanathan et al. (1996).

Multicriteria analysis of location problems (Current et al., 1990) has received considerable attention within the scope of continuous and network models in the last years. Presently, there are several problems that are accepted as classical ones the point-objective problem (Hansen et al., 1980; Carrizosa et al., 1993) the continuous multicriteria min-sum facility location problem (Hamacher and Nickel, 1996; Puerto and Fernandez, 1999) and the network multicriteria median location problem (Hamacher et al., 1998; Wendell et al., 1977; Chaudhary and Kincaid, 1990) among others. On the contrary, multicriteria analysis of discrete location problems (Mirchandani and Francis, 1990) has attracted less attention so far. However, several authors have dealt with problems and applications of multicriteria decision analysis in this field. In Lee et al. (1981) an application of integer goal programming to facility location with multiple competing objectives is studied. Solanki (1991) applies an approximation scheme to generate the set of non-dominated solutions to a bi-objective location problem. Recently, Ogryczak (1999) looks for symmetrically efficient location patterns in a multicriteria discrete location problem. In general, none of the above papers, focuses in the complete determination of the whole set of non-dominated solutions.

Due to the imprecision and fuzziness of the information related to parameters, deterministic models are not suitable to obtain an effective solution for uncapacitated facility location problems. To overcome the natural difficulties of these problems, fuzzy set theory provides a way to obtain precise answers. Zadeh (1965) suggested a fuzzy set theory to describe systems of imprecise nature. Zadeh and Bellman (1970) presented a fuzzy programming model for decisions in fuzzy environments.

Based on this theory, Zimmerman (1987) developed a Fuzzy Linear Programming (FLP) method with single and multiple objectives. Zadeh (1965) in his pioneering research used the fuzzy sets as a basis to derive the theory of possibility. After his initial study, possibility theory has found considerable acceptance. Matthias and Verma (1999) have suggested to apply Fuzzy AHP when the weights of existing facility is not known precisely to locate a new facility in a plane.

Fuzzy theory is adopted for dealing with the uncertainties in cost, demand, etc. Consequently, Possibilistic Linear Programming (PLP) (Lai and Hwang, 1994) is proposed for solving the problem because it is apparently the best approach for absorbing the imprecise nature of the real world. This study deals with the uncapacitated facility location problem requires locating facilities on a network to service the demands on the network at a minimum total cost.

MATHEMATICAL MODEL OF UNCAPACITATED FACILITY LOCATION PROBLEMS (UFLP)

In an UFLP there are a number of sites, n and a number of customers, m. Each site has a fixed cost fc_. There is a transport cost from each site to each customer c_ij. There is no limit of capacity for any candidate site and the whole demand of each customer has to be assigned to one site. We are asked to find the number of sites (facilities) to be established and specify those sites such that the total cost will be minimized (Eq. 1). The mathematical formulation of UFL can be stated as follows (Cornuejols et al., 1990):

(1)

Subject to the constrains

(2)

(3)

(4)

where, I, J denotes the index sets of vertex locations on the network for potential facility sites and the specified customers, respectively.

The constraint Eq. 2 makes sure that all demands have been met by the open sites and the constraint Eq. 3 is to keep integrity. Since it is assumed that there is no capacity limit for any facility, the demand size of each customer is ignored and therefore constraint Eq. 2 established without considering demand variable.

In real life situation, the demands at the customers points not always are crisp rather its fuzzy in nature and triangular in shape. If this is the case then the demands variable d_j = (d^p_j, d^m_j, d^o_j) is considered to be triangular possibilistic distribution at each customer points j. Although, a various number of distributions exist, triangular and trapezoidal are the most commonly used distributions in solving possibilistic mathematical programming problems. In this study, only triangular fuzzy numbers will use because it is simpler to do so. Since real world problems usually involve uncertain data, decision makers should handle this imprecise or fuzzy environment.

Hence, the possibility distributions estimated by the decision makers can be described more simply by triangular fuzzy numbers. The most possible value is d^m_j (possibility = 1, if normalized); d^p_j (the most pessimistic value) and d^o_j (the most optimistic value) are the least possible values.

are the imprecise distribution cost for serving customer jfrom a facility at i is calculated as the rectangular distance from j to i, multiplied by the fuzzy demand and have the triangular possibility distribution, so these are fuzzy cost transporting units of fuzzy demand from the facility site i to customerb j. c^p_ij, c^m_ij, c^o_ij represents the pessimistic value, most possible value and optimistic value, respectively. is the fuzzy fixed cost for opening a facility at site i.

Hence, the above model become fuzzy and is mathematically represented as:

(5)

subject to:

(6)

(7)

(8)

Hence, further it can be represented as:

(9)

Subject to:

(10)

(11)

(12)

Where:

where, I, J denotes the index sets of vertex locations on the network for potential facility sites and the specified customers, respectively.

SOLUTION PROCEDURE

To solve the above UFLP, consider the fuzzy objective function with a triangular shape.

Fig. 1:	Fuzzy weight

This fuzzy criterion is fully defined geometrically by three corner points (f^m (x), 1), (f^p (x), 0) and (f⁰ (x), 1), geometrically (Fig. 1) where:

Thus, minimizing the fuzzy objective can be obtained by pushing these three critical points in the direction of the left-hand side.

Fortunately, the vertical coordinates of the critical points are fixed at either 1 or 0. The only considerations then are the three horizontal coordinates. Therefore, the problem is to solve:

(13)

Where (f^P (x), f^m (x) f^o (x)) is the vector of the three objective functions. In order to keep the triangular shape of the possibility distribution it is necessary to make a small change. Instead of minimizing these three objectives (Eq. 13) simultaneously, three optimization problems will solve:

The first and the last criteria measure the relative distance from f^m (x) the second criterion. The solution of three new problems written for all original criteria also supports the previous observation of shifting the triangular distribution to the left:

(14)

(15)

(16)

Subject to:

(17)

(18)

(19)

So, the original fuzzy UFLP (Eq. 5) is replaced with the three new multicriteria problems (Eq. 14-16). The above problem can be solved using any MOIP technique such as utility theory, goal programming, fuzzy programming and interactive approach. However, in this study we used Zimmerman (1987) fuzzy programming method with normalization process.

To solve the newly formulated fuzzy UFLP we use the Zimmerman (1987) approach with positive and negative ideal solutions as follows. First, the Positive Ideal Solution (PIS) is found for all the criteria. It is obtained by maximizing/minimizing the criteria for the maximization/minimization problem:

Then, the Negative Ideal Solution (NIS) is found for all the criteria. It is obtained by minimizing/maximizing the criteria for the maximization/minimization problem.

The best decisions are those that have the shortest distance from PIS and the largest distance from NIS provide as much as possible gain and avoid as much as possible risk. Multicriteria UFLP is reduced to a single objective UFLP problem, by the introduction of linear membership functions for each of the criteria:

(20)

(21)

(22)

Above problem is resolved by using the max–min operation as proposed by Zadeh and Bellman (1970) and for simplicity we applied the Zimmerman (1987) approach to solve the problem. Let us call λ the membership degree to the decision set. We will call it the global degree of satisfaction of a given solution. We are looking for solution with the greatest value of λ. This can be found with the following auxiliary crisp problem:

(23)

Subject to the constrains:

(24)

(25)

(26)

(27)

(28)

NUMERICAL EXAMPLE

Considering the 5-facility problem with 5 customers. All the date like fixed costs which is fuzzy, distance between each location to customers and the demand for each customers which fuzzy are given in Table 1.

Table 1:	An example of 5-customer 5-facility

Table 2:	Fuzzy cost of 5-facilities

Table 3:	Result of fuzzy programming approach

The fixed costs of opening a facility and the demands of customers are fuzzy in nature and are represented as triangular fuzzy numbers and hence Fuzzy costs are:

Cost c_ij are the distribution cost for serving customers from facilities is calculated as the multiplication of distance by the fuzzy demand of the customers and have the triangular possibility distribution so these are fuzzy cost transporting units of fuzzy demand from the facility site I to customer j. Hence will be as shown in Table 2.

The result obtained using fuzzy programming approach discussed is shown in Table 3.

We can see the solution achieved with maximum value of λ^* = 0.782609 with opening of all five facilities satisfying all five customers.

CONCLUSION

In this study, considere an Uncapaciated facility Location problem where the demand and fixed cost are uncertain. They are fuzzy, rather than crisp and triangular in shape. Developed methodology provides a new approach to solve the problems. The most preferred solution should be determined on the basis of the shortest distance from the Positive Ideal Solution (PIS) and the largest distance from the Negative Ideal Solution (NIS).

The best decisions are those that provide as-much-as-possible gain and avoid as much as possible risk. Further extensions of the presented concepts will focus on probabilistic Uncapaciated facility Location problem where the demand would be random variables and follow some probability distribution and also discuss with different shape of fuzzy membership functions.