ABSTRACT

In this paper we study the problem of locating multiple facilities in convex sets with fuzzy parameters. This problem asks to find the location of new facilities in the given convex sets such that the sum of weighted distances between new facilities and existing facilities is minimized. We present a linear programming model for this problem with block norms, then we use it for problems with fuzzy data. We also do this for rectilinear and infinity norms as special cases of block norms.

1. Introduction

Within the wide interaction between operations research (OR) and computer science, a major application area concerns locational decisions. The locational decisions determine how to use the best case possible for achievement of activities with respect to existence a tools in our purpose direction. This aim is mostly contained of locating facilities. Multiple facility location problem is a well-known problem in operations research and especially in locational analysis and has been studied in depth, for more details see [1,2]. Locating facilities with some constraints on the regions which are contained facilities or customers is an interesting problem and has been studied by different constraints and conditions. Sarkar et al. [3] addressed the finite size 1-center placement problem on a rectangular plane in the presence of barriers. Barriers are regions in which both facility location and travel through are prohibited. The feasible region for facility placement is subdivided into cells along the lines by Larson and Sadiq [4]. Muoz-Pérez et al. [5] developed the problem of locating an undesirable facility in a bounded polygonal region (with forbidden polygonal zones), using Euclidean distances, under an objective function that generalizes the maximin and maxisum criteria, and includes other criteria such as the linear combinations of these criterions. Bhattacharya et al. [6], presented a fuzzy goal programming model for locating a single facility on a plane bounded by a convex polygon under the triple criteria maximin, minimax and minisum location. In [7] presented a fuzzy goal programming model for locating multiple new facilities on a plane bounded by a convex polygon under the criteria: 1) minimize the sum of all the transportation costs and 2) minimize the maximum distances from the facilities to the demand points. It has also been proved that the given methodology, always gives a nondominated solution. Nayeem and Pal [8] consider a facility location problem called p-center on fuzzy networks.

In this paper we present a model for locating multiple new facilities in convex sets with respect to multiple existing facilities and demand points, then present a linear programming model for this problem with block norms. We use this results for the problem with fuzzy data. We also do this for rectilinear and infinity norms as special cases of block norms. Rectilinear distances have been taken as the scenario may be thought of in an urban setting. Study of this problem and its modeling has many applications in industry such as locating machines in a workshop.

Let existing facilities be located at the known distinct points in the plane. In a multifacility location problem the optimal location of new facilities is sought with respect to the set of existing facilities. Let represents the distance between the locations of new facility and existing facility, and be the distance between the locations of new facilities and.

Let the cost per unit distance between new facility and existing facility be denoted by and being the corresponding cost per unit distance between new facilities and. The total transportation cost associated with new facilities located at is given by

(1)

The multifacility location problem can be stated as the selection of locations of new facilities such that total cost is minimized. For more details in location theory see [4,9-12].

The block norms are norms which their contours are polytopes. For example and are two block norms. The first application of block norms to solve the location problems suggested by Ward and Wendell [13,14]. They are shown that a block norm can be characterized as follows:

(2)

where the points and with form the extreme points of the polytope corresponding to the unit contour. They also presented another characterization based on polar set for block norms. This characterization follows:

(3)

where and with are extreme points of the polar set

By using these characterizations Ward and Wendell [13,14] shown that the minimax and minisum single facility location problems can be written as a LP problems.

If a block norm, is applied to measure the distances in the plane then we can write a linear programming for the problem in two ways:

1) For let

2) For let

By substituting these in models we have a linear programming. In this paper we assume that distance is measured by block norm and as a special case rectilinear norm in two dimensional space. When and, then objective function is as below:

(4)

If we use the rectilinear norm for measuring distances between points we have:

(5)

(6)

On substituting (5) and (6) into (1) and rearranging terms, we obtain

(7)

where

(8)

And

(9)

The expressions and give the total cost incurred due to “travel” in the and directions, respectively.

From (7), it follows that

We minimize with constraints that new facilities be in convex sets, by transforming it to an equivalent LP problem will provide optimum coordinate of the new facilities. An exactly analogous procedure is used to minimize.

In Section 2 we introduce a model for locating multiple facilities in convex sets. In Section 3 we give a practical exampl. A method for fuzzy linear programming problems and locating for fuzzy data are introduced in Section 4. Conclusion is achieved in the last section.

2. Locating Multiple Facilities in Convex Sets

Suppose that we have a set of m machines in a workshop for which their captured spaces are intervals. Assume that corresponding to the coordinates of machines. Also, suppose that we divide the remaining region of the workshop to K convex regions (here we consider convex regions as rectangle ones) which are given as follows.

for.

Now, we want to find points in these regions to locate new machines such that the sum of movement costs between each two new facilities and also new facilities and machines is minimized. We assume the movement cost between new facilities and machines to be proportional to the distance between them with a weight. Let be the weight of movement between facilities j and k, and be the weight of movement between facility j and machine k. Then we have the following problem.

(10)

In this paper we consider the special case that only one machine is assigned to each region and for each machine, only one region contains it. In fact, this part of problem reduces to an assignment problem. So we define binary variables which are equal to 1 if machine is assigned to region and are equal to 0 otherwise, and replace the constraints of the problem with the following.

where M is an upper bound for variables. This constraints ensure that only one machine is assigned to each region and for each machine, only one region contains it.

2.1. The Problem with Block Norms

Suppose the distances are measured by a block norm, then we can write the problem as follows.

(11)

So by definition of block norms and using transformations for the problem by variables, we have

(12)

which is a linear programming model.

2.2. The Problem with Rectilinear Norm

With rectilinear norm, model (10) is convertible to the following model:

(13)

Note that the objective function of model (13) is nonlinear. However we can linearize it as follows. Let

, ,

and

for.

If

then. So by using this transformation in model (13), we have:

(14)

Note that we have deleted the sets of multiplicative constraints, , , and. Since in solving model (14) by linear programming the theory of linear programming guarantees that some basic feasible solution, will be a minimum feasible solution. For any basic feasible solution, if is in the basic feasible solution, will not be and vice versa. Since variables not in the basic feasible solution, are zero, the multiplicative constraints will therefore be satisfied for every basic feasible solution. To see why both and would not be in the same basic feasible solution , suppose that the first two sets of equality constraints of model (14) are written in matrix form; then the column of the matrix corresponding to is −1 times the column corresponding to, so that the two columns are linearly dependent. Likewise, the two columns corresponding to and are linearly dependent but a basis consists of linearly independent vectors. If both and were in the same basic feasible solution, the corresponding columns making up the basis would be linearly dependent which can not be.

3. Examples

In this section we give some examples for the mentioned models. We solve them by LINGO software.

Example 1. Consider the problem of locating a new machine in an existing layout consisting of five machines. The coordinate of machines are presented in the Table 1. Also consider the four possible regions, in order to locate two new machines in Table 2. The problem is to obtain an optimal location for the new machines in the region, so that the sum of the rectilinear distances of the new machines from the other machines is minimized.

Using model (14) we obtain, and the optimal value of objective function is.

Example 2. Consider six important industrial regions in a city which receive compulsory services from two fire stations. These industrial regions are shown in Table 3. Also three sites are considered for building fire stations according to Table 4. The problem is to determine two sites considering of three sites for building two fire stations so that the sum of the distances of the fire stations from the six industrial regions is minimized. Let the distances are measured by a block norm which its extreme points are

Using model (12) we obtain the optimal solution

, and

. The weights of regions and sites are the same.

4. Fuzzy Linear Programming

The concept of decision making in fuzzy environment was first proposed by Bellman and Zadeh [1]. Subsequently, Tanaka et al. [15] made use of this concept in mathematical programming (see also [16]). A Fuzzy Linear Programming (FLP) is concerned with the optimization (minimization or maximization) of a fuzzy linear function while satisfying a set of linear equality and/or inequality fuzzy constraints. Fuzzy linear programming problem with fuzzy coefficients was proposed by Negoita [17]. A formulation of fuzzy linear programming with fuzzy constraints and a solution method were given by Tanaka and Asai [18]. Maleki et al. [19] introduced a linear programming problem with fuzzy variables and proposed a method for solving it. Fang and Hu [20] consider linear programming with fuzzy constraint coefficients (see also [21]). Gasimov and Yenilmez [22] discuss solution of fuzzy linear programming problems using linear membership functions (see also [23]). Maleki [24] used a certain ranking function to solve fuzzy linear programming problems. He also introduced a new method for solving linear programming problems with vagueness in constraints using a linear ranking function. Mishmast et al. [25] introduced the lexicographic ranking function to order fuzzy numbers and solved fuzzy number linear programming problems by lexicographic ranking function. In this paper FLP with Right Hand Solution (R.H.S) is considered.

An ordered pair of functions

is called a fuzzy number if and only if it satisfied in the following requirements.

1) is a bounded left continues non decreasing function over.

2) is a bounded left continues non increasing function over.

3) and are right continues in 0.

4) where

and

which,

is called Symmetric Triangular Fuzzy Number (STFN). Let ST be the set of all STFN.

A crisp number is simply represented by

.

The proofs of all the theorems in this section are given in [1].

4.1. Theorem

If be STFNs, and A be a matrix then1) if and only if

2)

3)

4), which.

4.2. Definition

Let be STFNs, we say if and only if 1) or 2)

and if and only if or.

Now consider fuzzy LP as follows

(15)

which, and is an triangular fuzzy vector. We reduce problem (15), to two following problems.

(16)

and

(17)

where.

4.3. Theorem

is a feasible solution problem (15) if and only if is a feasible solution of problem (16) and is feasible solution of problem (17).

4.4. Theorem

is an optimal solution of problem (15) if and only if is an optimal solution of problem (16) and is an optimal solution of problem (17).

4.5. Locating Multiple Facilities in Convex Sets with Fuzzy Data

Suppose that we have a set of machines in a workshop for which the captured spaces are as intervals. Assume that corresponding to their coordinates , (the sign is used for fuzzy numbers). Also, suppose that we divide the remaining region of the workshop to convex regions (here we consider convex regions as rectangle ones) which are given as follows:

where and are triangular symmetric fuzzy numbers. It is obvious that also is fuzzy numbers. Now, we want to find a point in one of the regions for a new machines such that the objective function of our considered problem in fuzzy case is minimized.

Hosseinzadeh et al. [26] consider the single facility case and present a linear programming for it.

For the fuzzy block norm case we have the following model.

(18)

Equivalently, according model (14) in Section 2 we have the following model for fuzzy numbers:

(19)

The problem (19) can be converted to standard form as follows.

(20)

In order to obtain the optimal solution of problem (20), we solve two problems in below:

(21)

and

(22)

Note that Theorem 4.4 is hold when the optimal values of the variables in models (21) and (22) are the same.

In the case norm is rectelinear we have the following nonlinear model:

(23)

Equivalently, according model (12) in Section 2 we have the below model for fuzzy numbers:

(24)

The problem (24) can be converted to standard form as:

(25)

In order to obtain the optimal solution of problem (25), we solve two problems in below:

(26)

and

(27)

Again the theorem 4.4 is hold when the optimal values of the variables in models (26) and (27) are the same.

5. Summary and Conclusion

In this paper we presented a linear model for finding optimal locations for multiple facilities with respect to the other facilities and then use it for fuzzy data. Here we use block norm and rectilinear norm as a special case, for finding the optimal locations. Also in order to avoid congestion, we suppose that an eligible site must be as interval. Finally, in order to locate new facilities in convex sets, we suggest a model by which the weighted distance between new facilities and all the other existing facilities and the new ones is minimized.

REFERENCES