Research Article
Solving Fuzzy Transportation Problems using a New Algorithm
Department of Industrial Management, College of Administration and Economics, University of Baghdad, P.O. Box 4097, Alwaziria, Baghdad, Iraq
The transportation problem is the special application of linear programming problem which aims to assign the optimal amounts of a product to be transported from various supply points to various demand points so that the total transportation cost is a minimum (Hillier and Liberian, 2001).
There are many literatures devoted to research about the fuzzy transportation problem.
Due to some uncontrollable factors, Bellman and Zadeh (1970) and Zadeh (1978) introduced the notion of fuzziness to deal quantitatively with imprecise information in making decisions in many situations that the demand and/or supply quantities and cost coefficients of a transportation problem may be uncertain.
Zimmermann (1978) proved that solutions obtained by fuzzy linear programming are always efficient. Subsequently, Zimmermanns fuzzy linear programming has developed into several fuzzy optimization methods for solving the transportation problems.
In many real life situations, it is not possible to determine both transportation unit cost and quantities, but the fuzzy numbers gives best approximation of them. OhEigeartaigh (1982) supposed the case where the membership functions of the fuzzy demands are triangular forms for transportation problems and solved it using table method. Chanas and Kulej (1984) proposed a technique to solve a fuzzy linear programming problem with triangular membership functions of fuzzy resources. Chanas et al. (1984) presented a model of fuzzy linear programming to solve transportation problems with fuzzy supply and demand values and crisp cost coefficients. Lai and Hwang (1992) developed transportation model that solving the problem when quantities are fuzzy and prices are crisp. Chanas and Kuchta (1996) presented the concept of the optimal solution for the transportation problem with fuzzy coefficients expressed as fuzzy numbers and developed an algorithm for obtaining the optimal solution. Chanas and Kuchta (1998) presented an algorithm that solves the transportation problem with fuzzy supply and demand values and integrality condition imposed on the solution. Liu and Kao (2004) provided a process to derive the fuzzy objective value of the fuzzy transportation problem, in that the supply and demand quantities and the cost coefficients are fuzzy numbers basing on extension principle.
Kumar and Kaur (2011) proposed two new methods for solving fuzzy transportation problems to overcome the shortcomings and limitations of the existing methods. They showed that it is better to used the proposed methods as compared to the existing methods for solving some fuzzy transportation problems. Kumar and Murugesan (2012) provided an optimal solution for fuzzy transportation with triangular membership functions. They employed a new arithmetic operations of triangular fuzzy numbers to get the fuzzy optimal solutions.
In this study, Fuzzy Russells Approximation Method (FRAM) has been developed to find the Initial Fuzzy Basic Feasible Solution (IFBFS) by using ranking of triangular fuzzy numbers when all the cost coefficients are fuzzy numbers and all supply and demand are crisp numbers. Also Fuzzy Modified Distribution Method (FMDM) has been used to test fuzzy optimal solution from the IFBFS.
Fuzzy preliminaries: Fuzzy set theory was presented by Zadeh (1965). The theory provided a mathematical approach for dealing with imprecise concepts and problems that have many possible solutions. The following definitions of the fuzzy numbers and some basic arithmetic operations on it may be helpful (Dubois and Prade, 1990, 1981).
Definition: A fuzzy number is a Triangular-fuzzy number denoted by (a1, a, a2) and its membership function μ(x) is given below:
The α-cut of the triangular fuzzy number = (a1, a, a2) is the closed interval Aα = [aαL, aαR] = [a1+(a+a1)α, a2+(a-a2)α]∈(0,1]. The another representation of the triangular fuzzy number is = (a-α, a, a+β). Where, a-α = a1 and a+β = a2 and can also be written in another form as = (a, α, β).
Definition: Let = (a1, α1, β1) and = (a1, α2, β2) be two triangular fuzzy numbers. Then:
Ranking functions: A convenient method for comparing of fuzzy number is by use of ranking function (Zimmermann, 1991; Maleki, 2002). A ranking function : F(R)→R, where, F(R) (a set of all fuzzy numbers defined on set of real numbers), maps each fuzzy number into a real number of F(R).
Let, and be two fuzzy numbers in F(R), then:
• | if and only if |
• | if and only if |
• | if and only if |
Let be any linear ranking function. Then, if and only if if and only if - and .
Ranking functions for triangular fuzzy number: For triangular fuzzy number = (a1, a, a2) or (a, α, β), ranking function is given by:
where, aα is α-cut on . This reduces to:
Then triangular fuzzy number = (a, α, β) and = (b, y, θ), we have if and only if:
Fuzzy transportation problem
Formulation: The formulation of the Fuzzy Transportation Problem (FTP) is similar to the traditional transportation problem i.e., the objective function is to minimize the total fuzzy transportation cost and the constraints are the supply and demand available to each source and destination, respectively.
The mathematical model of the FTP when all the cost coefficients are fuzzy numbers and all supply and demand are crisp numbers is given by:
S.T.
where, is a ranking function (i.e., : F(R)→R) which maps each fuzzy number into the real line; ai is the quantity of material available at source Si (i = 1, 2,...,m), bi is the quantity of material required at destination Di (i = 1, 2,...,n) and cij is fuzzy unit cost of transportation from source Si to destination Di.
Every fuzzy transportation problem can be represented by a fuzzy matrix of order m by n, called the fuzzy cost matrix or fuzzy effectiveness matrix.
Algorithm of fuzzy russells approximation method (FRAM): FRAM is proposed to obtain the IFBFS of a particular type of the FTP. Russells approximation method provides another excellent criterion that is still quick to implement on a computer (but not manually) (Russell, 1969). Although is unclear as to which is more effective on average, this criterion frequently does obtain a better solution than Vogels. For a large problem, it may be worthwhile to apply both criteria and then use the better solution to start the iterations of the transportation simplex method. One distinct advantage of Russells approximation method is that it is patterned directly after step1 for the transportation simplex method which somewhat simplifies the overall computer code (Hillier and Liberian, 2001).
In FRAM the and alues have been defined as the largest fuzzy unit transportation cost for each row and column respectively. In this method, each allocation is made on the basis of the maximum
The algorithm of this method for the FTP when all the cost coefficients are fuzzy numbers and all demands and supply are crisp numbers are follows:
Step 1: | Let be the largest fuzzy unit transportation cost cij (i.e., select the unit cost whose the fuzzy unite cost has the largest rank) for each source row i remaining consideration |
Step 2: | Let be the largest fuzzy unit transportation cost cij (i.e., select the unit cost whose the fuzzy unite cost has the largest rank) for each destination column j remaining under consideration |
Step 3: | For each variable xij not previously selected in these rows and columns |
Compute for each row and each column under consideration.
Step 4: | Allocate as much as possible for the row and column with the maximum (i.e., select the whose the fuzzy has the largest rank) |
In case the maximum is not unique (i.e., the maximum of more than one is same), then select the variable xij where maximum allocation can be made.
Step 5: | Adjust the supply and demand requirements to reflect the allocations already made. Eliminate any rows and columns in which supply and demand have been exhausted |
Step 6: | If all supply and demand requirements have not been satisfied, go to the first step and recalculate new . If all row and column values have been satisfied the initial fuzzy solution has been obtained |
Algorithm of fuzzy modified distribution method (FMDM): In this study, FMDM has been illustrated to find optimal solution of the FTP. The steps for finding optimal solution are as follows:
Step 1: | Construct the IFBFS of the FTP by any of the initial methods |
Step 2: | Derive the values of and corresponding to each ith row and jth column, respectively. Write in front of each ith row and in bottom of each jth column |
Step 3: | For a basic variable xij, let and satisfy the set of equations for each (i, j) such that xij is basic There are m+n-1 basic variables and so there are m+n-1 of these equations. Since the number of unknown is m+n, none of these variables can be assigned a value arbitrarily without violating the equations. The choice of this one variable and its value does not affect the value of any even when xij is non-basic |
Step 4: | Take any one of the or to be zero ranked fuzzy number |
Step 5: | Calculate the rank of for every (i, j) such that xij is non-basic. The IFBFS is fuzzy optimal if and only if for each (i, j) such that xij is non-basic. If there exist at least one such that then this IFBFS is not fuzzy optimal solution. Go to the step 6 |
Step 6: | Determine the entering basic variable: Because the FTP seeks to minimize cost, the entering variable is the one having the most positive coefficient in the z-row. In the FTP chose that whose rank is most positive |
Step 7: | Determine the leaving basic variable: The leaving variable in the following manner. First, construct a closed loop that starts and ends at the entering variable cell. The loop consists of connected horizontal and vertical segments only (no diagonals are allowed). Except for the entering variable cell, each corner of the closed loop must coincide with a basic variable. Identify the chain reaction require to retain feasibility when the entering basic variable is increased. From the donor cells, select the basic variable having the smallest value |
Table 1: | Balanced fuzzy transportation problem represented transportation costs by triangular fuzzy, supply and demand are crisp numbers |
Table 2: | Ranks of the fuzzy transportation costs |
Step 8: | Determine the new fuzzy basic feasible solution: Add the value of the leaving basic variable to the allocation for each recipient cell. Subtract this value from the allocation for each donor cell |
Step 9: | Again use the latest IFBFS and repeat steps 1-8 until ∀i and j |
Practical example: One of the main products of the Al-Noor company is canned dates. A company has three warehouses (Karbala, Diyala and Basra) and wants to satisfy the four customers demands (Baghdad, Anbar, Arbil and Dohuk). The approximate cost per tons (in dollars) of the product is represented by triangular fuzzy number. Supply and demand are crisp numbers. A fuzzy transportation problem has feasible solutions because . Table 1 summarizes the fuzzy transportation costs along with the supply and demand for each warehouse and customer respectively.
In Table 1, the costs are triangular fuzzy numbers of the form (a-α, a, a+β). Convert all the costs into the form (a, α, β) and find the ranks of the costs using formula a+(β-α)/4 (Table 2).
Using the criterion for FRAM, the results, including the sequence of basic variables (allocations), are shown in Table 3. At iteration 1, the largest fuzzy unit transportation cost in row 1 is = (100, 40, 30), the largest in column 1 is = (70, 20, 30)and so forth. Thus:
Calculating all the () values for i = 1, 2, 3 and j shows that () = 147.5 has the largest positive value, so, x31 = 200000 is selected as the first basic variable (allocation). This allocation uses up 200000 unit from the supply in row 3 and fully meet the demand in column 1, so this column is eliminated from further consideration.
The second iteration requires recalculating the (). The largest positive value now is:
So, x22 = 100000 becomes the second basic variable (allocation), eliminating column 2 from further consideration.
The subsequent iterations proceed similarly.
The final table after applying the algorithm of the FRAM (Table 4).
The objective function value at the IFBFS of the FTP:
Table 3: | Results, including the sequence of basic variables (allocations) from fuzzy Russells approximation method |
= 34000000, 43000000, 57000000 |
Table 4: | Initial fuzzy basic feasible solution from fuzzy russells approximation method |
= 34000000, 43000000, 57000000 |
Use the IFBFS obtained in Table 4 by FRAM to illustrate the FMDM by taking fuzzy cost of the form (a, α, β) to check whether this initial solution is optimal by applying the optimality test.
The IFBFS is fuzzy optimal if and only if for every (i, j) such that xij is non-basic.
Thus, the only work required by the optimality test is the derivation of the values of and for the current basic feasible solution and then the calculation of these as described below.
To calculate the values of s (i = 1, 2, 3) and s (i = 1, 2, 3, 4) for each occupied cell, arbitrarily assign = (0, 0, 0) to simplify calculations. Therefore, can be computed immediately by using the relation for allocated cells as shown below:
and:
Now, the for each of the unoccupied cell is determined by using the relation
The () of the cell (1,1) is given by:
Similarly, others can be calculated and there values are given by:
According the optimality criterion for fuzzy cost minimizing FTP, the current solution is optimal, since the ranks of all of the unoccupied cells are negative. Thus the final fuzzy optimal value by taking fuzzy cost of the form (a-α, a, a+β) is given by:
So, the results obtained by solving fuzzy transportation problem by proposed methods can be illustrated as follows:
• | Maximum number of person are in favor that cost will be 43000000 |
• | Total cost of transportation is greater than 34000000 and less than 57000000 |
• | The membership function for the obtained result is shown in Fig. 1 |
• | The percentage of persons increases when cost varies from 34000000 to 43000000 and decreases when cost varies from 43000000 to 57000000 |
Fig. 1: | Membership function for the obtained result2 |
In this study, a new algorithm called Fuzzy Russells Approximation Method (FRAM) has been proposed to obtain the Initial Fuzzy Basic Feasible Solution (IFBFS) of a Fuzzy Transportation Problem (FTP) which would be a new attempt in solving the transportation problem in fuzzy environment. Also an algorithm called Fuzzy Modified Distribution Method (FMDM) has been proposed to test the fuzzy optimal solution from the initial fuzzy basic feasible solution. The arithmetic operations of ranking functions for triangular fuzzy numbers are employed to get the initial fuzzy basic feasible solution and the fuzzy optimal solutions of a fuzzy transportation problem.
The proposed method namely, FRAM has the following major advantages:
• | A systematic procedure |
• | Easy to understand and to apply |
• | The initial fuzzy basic feasible solution is the same as the optimum solution or it is very close to it |
• | This approach can be extended to solve other fuzzy transportation problem |
1The fuzzy transportation unit cost per ton represented by triangular fuzzy number
2The value zero on the y-axis is used to represent complete non-membership, the value one on same axis is used to represent complete membership, and values in between are used to represent intermediate degrees of membership
k.sathishkumar Reply
help in fuzzy transportation problem