A fuzzy approach to transport optimization problem

Abstract

This paper presents an algorithm to solve a fuzzy transportation problem in which demand, supply and transportation costs are uncertain. Existing solution methods convert a fuzzy transportation problem into two or more crisp transportation problems and solves it. But, the proposed algorithm solves a fuzzy transportation problem without converting it into a crisp transportation problem. This approach results in a fuzzy total transportation cost, which is a fuzzy number. Sudhagar score method is used to rank fuzzy numbers. In comparing results of existing methods with the proposed method, this algorithm outperforms the previous ones. Two numerical examples explain working procedure of the proposed algorithm.

1 Introduction

Transportation problem has applications in decision making processes, Logistics and Supply Chain. Parameters of a transportation problem are unit transportation cost, demand and supply quantities. When transportation cost, demand and supplies are deterministic and crisp values, methods are available (Taha 2006) to determine an optimal solution. But demand and supply of a transportation problem are uncertain in nature. Transportation cost of a unit is not deterministic but imprecise. A frequent mean to express uncertainty or imprecision is fuzzy number. If some or all parameters of a transportation problem are fuzzy numbers then it is a Fuzzy Transportation Problem (FTP).

To solve a crisp transportation problem Taha (2006) uses tabular methods such as Northwest Corner Rule, Least Cost Method and Vogel’s Approximation Method (Reinfeld and Vogel 1958). These methods use techniques of a Linear programming problem. They differ only in steps of carrying out optimality conditions.

Lai and Hwang (1992) use tabular method for solving FTP by means of a crisp parametric programming problem. OhEigeartaigh (1982) consider particular cases where membership function of demand and supplies are triangular fuzzy numbers. Chanas et al. (Chanas and Kulej 1984; Chanas et al. 1984) provide a parametric programming approach to solve a FTP where resources have triangular membership function.

Ringuest and Rink (1987) use a linear programming technique to solve FTP. Geetha and Nair (1994) formulate a stochastic version of time minimizing transportation problem. Their method develops an algorithm based on parametric programming to solve FTP, when transportation time is an independent, positive normal random variable. Chanas and Kuchta (1996) discuss transportation problem with fuzzy cost coefficients and transform problem into a bi-criterion transportation problem; nevertheless, produce only crisp solution. Wahed (2001) proposes a fuzzy programming approach to find a compromise solution of multi objective transportation problem.

Liu and Kao (2004) develop a procedure to solve FTP based on Zadeh’s extension principle. A pair of two-level mathematical programs are formulated to calculate upper and lower bounds of α-level cut of objective value. The membership function of a fuzzy objective value is derived numerically by enumerating different values of α. Pandian and Natarajan (2010a, 2010b) propose an algorithm namely, fuzzy zero point method for finding an optimal solution to a FTP. Fuzzy zero point method consider optimal solution as a trapezoidal fuzzy number.

In all methods discussed above, solution of a FTP is considered as triangular or trapezoidal fuzzy number. Also these procedures convert a FTP into one or more crisp transportation problem at some level and use parametric programming technique or crisp linear programming technique to arrive at a solution. These approaches lead to a crisp solution, or a predetermined form of fuzzy number. For taking accurate and timely decisions, a general fuzzy number with less spread is more realiable.

This paper proposes a new algorithm for solving (FTP) based upon score method (Sudhagar and Ganesan 2009) of ranking fuzzy numbers. In this approach cost of unit transportation, demand and supply are general fuzzy numbers, which are not restricted to triangular or trapezoidal type. This algorithm, aims at a non negative fuzzy solution with less spread.

Rest of this paper is organized as follows: In Sect. 2, brief review on basics of a fuzzy number and their arithmetics are given. Section 3, proposes a new algorithm to solve a FTP. In Sect. 4, the algorithm is demonstrated by numerical examples. A comparison of solution derived from the proposed algorithm with solutions of existing methods show the rationale of this method. Section 5 lists conclusions and acknowledgments.

2 Preliminaries

Definition 1

A convex normal fuzzy set $\tilde{A}$ on real number set R, whose membership function is piecewise continuous is called Fuzzy Number.

$$ \tilde{A}=\bigl\{ \bigl(x,\mu_{\tilde{A}} (x) \bigr)\vert x\in R\bigr\}. $$

(1)

Definition 2

Let be set of all fuzzy numbers, which are upper semi continuous and have compact support. Support of a fuzzy number $\tilde{A}$ with membership function ${f_{\tilde {k}_{i}}}:R\rightarrow [0,1]$ is denoted by $\operatorname{supp}(\tilde{ A})=[a_{1},a_{4}]$, where

$$ f_{\tilde{k}_i}(t)=\left \{\begin{array}{l@{\quad }l}{f_{\tilde{k}_l}}(t) &{a_1\leq t\leq a_2}\\[2pt] 1 & {a_2\leq t \leq a_3} \\[2pt] {f_{\tilde{k}_r} }(t) & {a_3 \leq t \leq a_4} \\[2pt] 0 & \mathrm{otherwise}. \end{array} \right . $$

(2)

Definition 3

A fuzzy number $\tilde{A}$ is defined as a discrete fuzzy number if $\tilde{A}$ has a finite support x ₁<x ₂<⋯<x _n and there are indices s, t; 1≤s≤t≤n such that

(i):

$\tilde {A}( x_{i} ) = 1$, whenever s≤i≤t,

(ii):

If h<k<s, then $\tilde{A}(x_{h} ) \preccurlyeq \tilde{A}(x_{k} ) \prec 1$,

(iii):

If t<p<q, then $1 \succ \tilde{A}( x_{p} ) \succcurlyeq \tilde{A}( x_{q})$.

Definition 4

The height, $h( \tilde{A})$ of a fuzzy number $\tilde{A}$ is the largest membership grade obtained by any element in $\tilde{A}$. That is

$$ h( \tilde{A})= \mathop{\mathrm{Sup}}\limits_{x\in R} \bigl(\mu_{\tilde{A}} (x) \bigr). $$

(3)

Definition 5

Let $\tilde{A} = (a_{1},a_{2},a_{3},a_{4})$ and $\tilde{B} = (b_{1},b_{2},b_{3},b_{4})$ be any two trapezoidal fuzzy numbers with $\tilde{A} \succ 0$, $\tilde{B} \succ 0$, then the fuzzy arithmetic is defined as follows:

• (i) Image of $\tilde{B} = (-b_{4},-b_{3},-b_{2},-b_{1})$.

• (ii) Inverse of $\tilde{B}$ is $\tilde{B}^{-1} = (1/b_{4},1/b_{3},1/b_{2},1/b_{1})$.

• (iii) Addition is $\tilde{A} + \tilde{B} = (a_{1}+b_{1},a_{2}+b_{2},a_{3}+b_{3},a_{4}+b_{4})$.

• (iv) Subtraction is $\tilde{A} - \tilde{B} = (a_{1}-b_{4},a_{2}-b_{3},a_{3}-b_{2},a_{4}-b_{1})$.

• (v) Multiplication is $\tilde{A} \tilde {B} = (a_{1}b_{1},a_{2}b_{2},a_{3}b_{3},a_{4}b_{4})$.

• (vi) Scalar Multiplication is $k\tilde {A} = (ka_{1},ka_{2},ka_{3},ka_{4})$; where K>0.

• (vii) Division is $\frac{\tilde{A}}{\tilde{B}} = (\frac{a_{1}}{b_{4}},\frac{a_{2}}{b_{3}}, \frac{a_{3}}{b_{2}},\frac{a_{4}}{b_{1}})$.

Definition 6

If $\tilde {A} = [a_{1}, a_{2}]$ and $\tilde {B} = [b_{1}, b_{2}]$, then equation $\tilde {A} + \tilde {X} = \tilde {B}$ has a solution (Klir and Yuan 1995) if and only if b ₁−a ₁≤b ₂−a ₂. The solution is

$$ \tilde{X} = [ b_1-a_1, b_2-a_2 ]. $$

(4)

Definition 7

The Score of a fuzzy number (Sudhagar and Ganesan 2009) $\tilde{A}_{i}$ is defined as follows:

$$ \mathit{Score}(\tilde{A}_{i} )= S_{i} *e^{U_{i}} *h_{i} *\alpha , $$

(5)

where

(6)

(7)

(8)

Here k denotes indices of different polynomials defining membership function in interval [a ₁,a ₄], h _i is height of fuzzy number $\tilde{A}_{i}$, and α∈(0,1] is expert’s coefficient. The fuzzy number with higher score will rank higher.

Remark 1

If $\tilde{A}_{i}$ and $\tilde{A}_{j}$ are two fuzzy numbers, then ordering procedure defined by Sudhagar score method is as follows:

• 1. $\tilde{A}_{i} \succ \tilde{A}_{j}$ if and only if $\mathit{Score}(\tilde{A}_{i} ) > \mathit{Score}(\tilde{A}_{j} )$

• 2. $\tilde{A}_{i} \prec \tilde{A}_{j}$ if and only if $\mathit{Score}(\tilde{A}_{i} ) < \mathit{Score}(\tilde{A}_{j} )$

• 3. $\tilde{A}_{i} \approx \tilde{A}_{j}$ if and only if $\mathit{Score}(\tilde{A}_{i} )=\mathit{Score}(\tilde{A}_{j} )$

• 4. $\tilde{A}_{i} = \tilde{A}_{j}$ if and only if $\mathit{Score}(\tilde{A}_{i})= \mathit{Score}(\tilde{A}_{j})$ and $\tilde{A}_{i}(x) = \tilde{A}_{j}(x)$; ∀x∈U.

Remark 2

Let M be an ordering method, S be a set of fuzzy quantities for which method M can be applied. $\tilde {\mathcal{A}}$ be a finite subset of S. The following axioms are satisfied (Sudhagar and Ganesan 2012) by ranking method defined in Definition 7.

A ₁ :

For an arbitrary finite subset $\tilde{\mathcal{A}}$ of S and $\tilde {A} \in \tilde{\mathcal{A}}$, $\tilde {A} \succcurlyeq \tilde {A}$ by M on $\tilde{\mathcal{A}}$.

A ₂ :

For an arbitrary finite subset $\tilde{\mathcal{A}}$ of S and $(\tilde {A},\tilde {B}) \in \tilde{\mathcal{A}}^{2} , \tilde {A} \succcurlyeq \tilde {B}$ and $\tilde{B} \succcurlyeq \tilde{A}$ by M on $\tilde{\mathcal{A}}$, we should have $\tilde{A} \approx \tilde{B}$ by M on $\tilde{\mathcal{A}}$.

A ₃ :

For an arbitrary finite subset $\mathcal{A}$ of S and $(\tilde{A}, \tilde{B}, \tilde{C}) \in \tilde{\mathcal{A}}^{3}$, $\tilde{A} \succcurlyeq \tilde{B}$ and $\tilde{B} \succcurlyeq \tilde{C}$ by M on $\tilde{\mathcal{A}}$, we should have $\tilde{A} \succcurlyeq \tilde{C}$ by M on $\tilde{\mathcal{A}}$.

A ₄ :

For an arbitrary finite subset $\tilde{\mathcal{A}}$ on S and $(\tilde{A}, \tilde{B}) \in\tilde{\mathcal{A}}^{2}$, $\inf \mathit{Supp}(\tilde{A}) \,{>} \sup \mathit{Supp}(\tilde{B})$, we should have $\tilde{A} \succcurlyeq \tilde{B}$ by M on $\tilde{\mathcal{A}}$.

$A_{4}'$ :

For an arbitrary finite subset $\tilde{\mathcal{A}}$ on S and $(\tilde{A}, \tilde{B}) \in\tilde{\mathcal{A}}^{2}$, $\inf \mathit{Supp}(\tilde{A}) \,{>} \sup \mathit{Supp}(\tilde{B})$, we should have $\tilde{A} \succ \tilde{B}$ by M on $\tilde{\mathcal{A}}$.

A ₅ :

Let S and S′ be two arbitrary finite sets of fuzzy quantities in which M can be applied and $\tilde{A}, \tilde{B}$ are in S∩S′. $\tilde {A} \succ \tilde {B}$ by M on S′ if and only if $\tilde{A} \succ \tilde{B}$ by M on S.

A ₆ :

Let $\tilde{A}$, $\tilde{B}$, $\tilde{A} +\tilde {C}$ and $\tilde{B} + \tilde{C}$ be elements of S. If $\tilde{A} \succcurlyeq B$ by M on $\{\tilde{A}, \tilde{B}\}$, then $\tilde{A} + \tilde{C} \succcurlyeq \tilde{B} + \tilde{C}$ by M on $\{\tilde{A} + \tilde{C}, \tilde{B} + \tilde{C}\}$.

$A_{6}'$ :

Let $\tilde{A}$, $\tilde{B}$, $\tilde{A} +\tilde {C}$ and $\tilde{B} + \tilde{C}$ be elements of S. If $\tilde{A} \succcurlyeq B$ by M on $\{\tilde{A}, \tilde{B}\}$, then $\tilde {A} + \tilde{C} \succcurlyeq \tilde {B} + \tilde{C}$ by M on $\{\tilde{A} + \tilde{C}, \tilde{B} + \tilde{C}\}$; when $\tilde{C} \succcurlyeq \emptyset$.

A ₇ :

Let $\tilde{A}$, $\tilde{B}$, $\tilde{A} \tilde{C}$, and $\tilde{B}\tilde{C}$, $\tilde{C}$ be elements of S and $\tilde{C} \succcurlyeq 0$. If $\tilde{A} \succcurlyeq \tilde{B}$ by M on $\{\tilde{A}, \tilde{B}\}$, then $\tilde{A}\tilde{C} \succcurlyeq \tilde{B}\tilde{C}$ by M on $\{\tilde{A}\tilde{C},\tilde{B}\tilde{C}\}$.

Remark 3

Even if transportation parameters are fuzzy integers, crisp numbers or discrete fuzzy numbers; nevertheless, they can be ranked by using extension (Sudhagar and Ganesan 2010) of score method of ranking given in Definition 7.

3 Main result

The objective of a FTP is to determine optimal amount of quantities to be transported from supply points to demand points, so that total transportation cost is minimum. Unit transportation costs, quantity available at supply points and quantity required at demand points are the parameters of a transportation problem. In practice, these parameters are not always exactly known. This imprecision arises from lack of data, high information cost or a consequence of certain flexibility required by a supply company or demand market. Therefore an able procedure to find an optimal solution of a transportation problem with fuzzy cost coefficients, fuzzy demand and fuzzy supply is important.

3.1 Formulation

Consider a transportation problem with p supply nodes and q demand nodes. From node i, total supply is m _i >0 units and at node j, total demand is d _j >0 units. Associated with each link (i,j) there is a cost c _ij ≥0, which represents cost of transporting one unit from supply node i to demand node j. Let x _ij ≥0 denote number of units to be transported from i to j.

The mathematical description of a crisp transportation problem is as follows:

$$ \everymath{\displaystyle} \begin{array}{l} \mathrm{min}\ Z = \sum_{i=1}^{p} \sum_{j=1}^{q}c_{ij}x_{ij} \\[12pt] \begin{array}{l@{\quad }l} \mbox{subject\ to}& \sum_{j=1}^{q}x_{ij}\leq m_i , \quad i = 1,2,3,\ldots,p \\[12pt] &\sum_{i=1}^{p}x_{ij}\geq d_j, \quad j = 1,2,3,\ldots,q \\[12pt] &x_{ij}\geq 0, \quad \forall i, j. \end{array} \end{array} $$

(9)

Suppose c _ij , m _i and d _j are approximately known, then they are represented by convex fuzzy numbers, $\tilde{C}_{ij}$, $\tilde {M}_{i}$ and $\tilde {D}_{j}$ respectively. The Mathematical description of FTP corresponding to (9) is as follows:

$$ \everymath{\displaystyle} \begin{array}{l} \min \tilde{Z} = \sum_{i=1}^{p} \sum_{j=1}^{q} \tilde{C}_{ij} \tilde{X}_{ij} \\[12pt] \begin{array}{l@{\quad }l} \mbox{subject\ to}& \sum_{j=1}^{q} \tilde{X}_{ij}\leq \tilde{M}_i ,\quad i = 1,2,3,\ldots,p \\[12pt] &\sum_{i=1}^{p} \tilde{X}_{ij} \geq \tilde{D}_j, \quad j = 1,2,3,\dots,q \\[12pt] &\tilde{X}_{ij}\geq 0, \quad \forall i, j \end{array} \end{array} $$

(10)

where

3.2 Fuzzy transportation algorithm

Step 1. :

If $\sum_{i=1}^{p} \tilde{M}_{i} = \sum_{j=1}^{q} \tilde{D}_{j}$ in a FTP then it is a balanced problem. If an equality¹ is not satisfied then it is an unbalanced problem. Convert an unbalanced FTP into a balanced FTP by introducing a fictitious supply $\tilde{M}_{p+1}= ( \alpha, \beta, \gamma, \delta )$ and a fictitious demand $\tilde{D}_{q+1}=( \theta, \vartheta, \phi, \psi )$ satisfying following conditions:

• (i) 0≤α≤β≤γ≤δ

• (ii) 0≤θ≤ϑ≤ϕ≤ψ.

Assign fuzzy cost to each fictitious cell as $\tilde{C}_{ij}=(0,0,0,0)$.

Step 2. :

Using (7), calculate the score of all fuzzy costs. Scores of fuzzy cost function C _ij are denoted by Score(C _ij )=χ _ij . Rank cost functions in ascending order according to the Sudhagar score method. If there is a tie, break it arbitrarily.

Step 3. :

Start to allocate fuzzy quantities from least cost cell. If the cell (i,j) has the least score then allocate maximum possible fuzzy quantity $\tilde{X}_{ij}=(x_{1ij},x_{2ij},x_{3ij},x_{4ij})$ satisfying all the following conditions:

• (i) 0≤m _1i −x _1ij ≤m _2i −x _2ij ≤m _3i −x _3ij ≤m _4i −x _4ij ,

• (ii) 0≤d _1j −x _1ij ≤d _2j −x _2ij ≤d _3j −x _3ij ≤d _4j −x _4ij ,

• (iii) 0≤x _1ij ≤x _2ij ≤x _3ij ≤x _4ij .

Step 4. :

Calculate remaining unsatisfied demand and available supply at all nodes. Computation of unsatisfied supply and demand are as follows:

$$\everymath{\displaystyle} \begin{array}{l} \tilde{M}_{i}^{1}=(m_{1i} - x_{1ij}, m_{2i} - x_{2ij},m_{3i} - x_{3ij}, m_{4i} - x_{4ij})\quad \mbox{and}\\[6pt] \tilde{D}_{j}^{1}= (d_{1j} - x_{1ij}, d_{2j} - x_{2ij} ,d_{3j} - x_{3ij} , d_{4j} - x_{4ij}). \end{array} $$

If $\tilde{M}_{i}^{1}=\tilde {D}_{j}^{1}=(0,0,0,0)$, ∀i,j then iteration is over. Then the basic feasible solution is $\tilde {X}_{ij}=(x_{1ij},x_{2ij},x_{3ij},x_{4ij})$. Otherwise, repeat Step 3 until supply and demand are completely satisfied. Fuzzy objective value corresponding to basic feasible solution can be calculated from Eq. (10) and by using fuzzy arithmetic defined in Definition 5.

Step 5. :

To find an optimal solution, check for non-degeneracy of a solution. If a basic feasible solution of FTP contains at least p+q−1 allocations in independent positions² then proceed to next step; else resolve degeneracy by making use of an infinitesimally small quantity $\tilde {\epsilon}$ almost close to zero, to one or more cells. Allocation of $\tilde {\epsilon}$ should be assigned to an independent cell.³ In case of more than one independent cell, $\tilde {\epsilon}$ should preferably be assigned to a cell, which has the minimum transportation cost. If number of allocation is more than the required p+q−1 allocations then arbitrarily choose any p+q−1 independent allocation cells as basic cells.

Step 6. :

Determine crisp values v _i and w _j in such a way that χ _ij of p+q−1 basic cells equal sum of v _i and w _j . For computational convenience take v _i =0 for a row, where number of allocation is maximum. Obtain other values v _i and w _j by using relation χ _ij =v _i +w _j , only in selected p+q−1 cells. Then define implied cost λ _ij of a non basic cell as λ _ij =χ _ij −(v _i +w _j ).

Step 7. :

If λ _ij ≥0, ∀i,j then current feasible solution is optimal. If λ _ij <0, for some i,j then current feasible solution is not optimal. To get an optimal solution, choose a cell with most negative λ _ij value. Now establish a closed path employing only horizontal and vertical path only, starting from the selected non basic cell. A right angle turn can be made only at a basic cell, though a path may skip over basic and non basic cells.

Step 8. :

Assign signs (+) and (−) alternatively to turning points of the closed path starting with a (+) in the selected non basic cell. Now compare fuzzy allocations in all (−) sign cells and determine a fuzzy quantity to be placed into selected (+) signed cell. To determine this fuzzy quantity, form constraint equations and solve them according to Definition 6. Effect changes and form a new table.

Step 9. :

Repeat Steps 6, 7 and 8 for new table until λ _ij ≥0, ∀i,j. The resultant allocation is then optimal.

Step 10. :

Optimal fuzzy objective value corresponding to an optimal allocation can be calculated from Eq. (10) and by using fuzzy arithmetic defined in Definition 5.

Theorem 1

If $(\tilde {x}_{11}^{*}, \tilde {x}_{12}^{*},\tilde {x}_{13}^{*}, \ldots,\tilde {x}_{ij}^{*},\ldots,\tilde {x}_{pq}^{*})$ is a feasible solution to the FTP,

$$ \everymath{\displaystyle} \begin{array}{l} \min\ \tilde {z} = \sum_{i=1}^{p} \sum_{j=1}^{q}\mathit{Score}(\tilde{c}_{ij}) \tilde{x}_{ij} \\[12pt] \begin{array}{l@{\quad }l} \mathrm{subject\ to}& \sum_{j=1}^{q}\tilde{x}_{ij}\leq \tilde{M}_i ,\quad i = 1,2,3,\dots,p \\[12pt] &\sum_{i=1}^{p}\tilde{x}_{ij} \geq \tilde{D}_j, \quad j = 1,2,3,\ldots, q \\[12pt] &\tilde {x}_{ij}\geq 0, \quad \forall i, j \end{array} \end{array} $$

(11)

and λ _ij =χ _ij −(v _i +w _j )≥0, ∀i,j then $(\tilde{x}_{11}^{*}, \tilde{x}_{12}^{*},\tilde{x}_{13}^{*}, \ldots, \tilde{x}_{ij}^{*}, \ldots, \tilde{x}_{pq}^{*})$ is an optimal solution to the FTP (11); where $\chi_{ij}= \mathit{Score}(\tilde{c}_{ij})$, v _i and w _j are real numbers.

Proof

Dual FTP of (11) is given by

$$ \everymath{\displaystyle} \begin{array}{l} \max\ z^{\prime} =\sum_i \tilde {M}_iv_i + \sum_j \tilde {D}_jw_j \\[12pt] \begin{array}{l@{\quad }l} \mbox{subject\ to} & v_{i} + w_{j} \leq \mathit{Score}(\tilde{c}_{ij}) \\[12pt] &v_i,w_j\ \mathrm{are\ unrestricted}\ \forall\ i, j. \end{array} \end{array} $$

(12)

From Score(C _ij )=χ _ij , constraints of dual FTP (12) becomes

For a minimization transportation problem, entering variable is one with the largest negative λ _ij . According to dual simplex method, at optimum iteration λ _ij ≥0; ∀i,j. Here the feasible solution satisfies optimal condition. Therefore any feasible solution to FTP (11) satisfies constraint λ _ij =χ _ij −(v _i +w _j )≥0; ∀i,j is an optimal solution. □

Theorem 2

If $(\tilde {x}_{11}^{*}, \tilde {x}_{12}^{*},\tilde {x}_{13}^{*}, \ldots, \tilde {x}_{ij}^{*},\ldots, \tilde {x}_{pq}^{*})$ is an optimal solution of modified FTP (13)

$$ \everymath{\displaystyle} \begin{array}{l} \min \tilde {z} = \sum_{i=1}^{p} \sum_{j=1}^{q}\mathit{Score}(\tilde{c}_{ij}) \tilde {x}_{ij} \\[8pt] \begin{array}{l@{\quad }l} \mathrm{subject\ to}& \sum_{j=1}^{q}\tilde {x}_{ij} \leq \tilde {M}_i ,\quad i = 1,2,3,\ldots,p \\[8pt] &\sum_{i=1}^{p}\tilde{x}_{ij}\geq \tilde {D}_j ,\quad j = 1,2,3,\ldots,q \\[12pt] &\tilde{x}_{ij}\geq 0 \quad \forall i, j. \end{array} \end{array} $$

(13)

then $(\tilde {x}_{11}^{*}, \tilde {x}_{12}^{*},\tilde {x}_{13}^{*},\ldots,\tilde {x}_{pq}^{*})$ is an optimal solution of completely fuzzified FTP (14).

$$ \everymath{\displaystyle} \begin{array}{l} \min \tilde {z} = \sum_{i=1}^{p} \sum_{j=1}^{q}\tilde {c}_{ij}\tilde{x}_{ij} \\[8pt] \begin{array}{l@{\quad }l} \mathrm{subject\ to}& \sum_{j=1}^{q}\tilde{x}_{ij}\leq \tilde {M}_i ,\quad i = 1,2,3,\dots,p \\[8pt] &\sum_{i=1}^{p}\tilde {x}_{ij}\geq \tilde {D}_j,\quad j = 1,2,3,\ldots,q \\[12pt] &\tilde {x}_{ij} \geq 0 \quad \forall i, j. \end{array} \end{array} $$

(14)

Proof

On the contrary it is assumed that an optimal solution of modified FTP and solution of the corresponding completely fuzzified FTP are not same.

Let $\tilde{X}= (\tilde {x}_{11}^{*}, \tilde {x}_{12}^{*},\tilde {x}_{13}^{*},\ldots,\tilde {x}_{ij}^{*},\ldots,\tilde {x}_{pq}^{*})$ is an optimal solution of modified FTP and $\tilde {Y} = (\tilde {y}_{11}^{*}, \tilde{y}_{12}^{*},\tilde{y}_{13}^{*},\ldots,\tilde {y}_{ij}^{*},\ldots,\tilde {y}_{pq}^{*})$ be an optimal solution of the corresponding completely fuzzified FTP. Since $\tilde {X}$ is an optimal solution of (13), for any linearly independent feasible solution $\tilde {Y}$ of modified FTP, the following inequality holds true.

$$ \sum_i\sum_j \mathit{Score}(\tilde{c}_{ij})\tilde{X}_{ij}^* \leq\sum_i\sum_j \mathit{Score}(\tilde{c}_{ij})\tilde{Y}_{ij}^*. $$

(15)

Similarly if $\tilde{Y}_{ij}^{*}$ is an optimal solution of FTP (14), for any linearly independent feasible solution $\tilde {X}$ of a completely fuzzified FTP results in the following inequality.

$$ \sum_i\sum_j \tilde{c}_{ij}\tilde {Y}_{ij}^*\leq\sum _i\sum_j \tilde{c}_{ij}\tilde {X}_{ij}^*. $$

(16)

Finding scores of inequality (16) gives that

$$ \mathit{Score}\biggl(\sum_i\sum _j \tilde{c}_{ij}\tilde{Y}_{ij}^*\biggr)\ \leq\ \mathit{Score}\biggl(\sum_i\sum _j \tilde{c}_{ij}\tilde{X}_{ij}^* \biggr). $$

(17)

Application of ranking properties A ₅ to A ₇ from Remark 2 to Eq. (17) results that

$$ \sum_i\sum_j \mathit{Score}(\tilde{c}_{ij})\tilde{Y}_{ij}^* \leq\ \sum_i\sum_j \mathit{Score}(\tilde{c}_{ij})\tilde{X}_{ij}^*. $$

(18)

Comparison of Eqs. (15) and (18) concludes

$$ \sum_i\sum_j \mathit{Score}(\tilde{c}_{ij})\tilde{Y}_{ij}^* = \sum_i\sum_j \mathit{Score}(\tilde{c}_{ij})\tilde{X}_{ij}^*. $$

(19)

Since $\tilde {X}_{ij}^{*}$ and $\tilde {Y}_{ij}^{*}$ are defined by same type of membership functions (trapezoidal), according to Remark 1, $\tilde {X}_{ij}^{*} = \tilde {Y}_{ij}^{*}$; ∀i,j. Hence if $(\tilde {x}_{11}^{*}, \tilde {x}_{12}^{*} ,\tilde {x}_{13}^{*},\ldots,\tilde {x}_{ij}^{*},\ldots,\tilde {x}_{pq}^{*})$ is an optimal solution of modified FTP (13) then $(\tilde {x}_{11}^{*}, \tilde {x}_{12}^{*},\tilde {x}_{13}^{*},\ldots,\tilde {x}_{ij}^{*} ,\ldots, \tilde {x}_{pq}^{*})$ is an optimal solution of FTP (14). □

4 Numerical example

Example 1

Consider a transportation problem with fuzzy costs as given in Table 1. Each manufacturer M ₁ and M ₂ can deliver 70 units of product. Demands of market are D ₁=30, D ₂=30 and D ₃=80. The objective of problem is to minimize total transportation cost, where all demands are satisfied from maximum available supplies.

Table 1 Example from Chanas and Kuchta

Solution

Step 1 :

Total demand =30+30+80=140 and total supply =70+70=140. Therefore problem is balanced.

Step 2 :

Now use score Definition 7 to assign scores to fuzzy cost functions. Scores and order (in parenthesis) of fuzzy numbers are given in Table 2.

Table 2 Sudhagar score values and rank order

Step 3 :

The cell (2,3) has the least rank. Transport maximum possible units to this destination. For this cell supply is 70 and demand is 80. So assign x ₂₃=70. Now total supply from M ₂ is exhausted. Hence, rule out the second row and choose next least rank cell from remaining rows.

Step 4 :

It happens in the cell (1,3). For D ₃ remaining demand is 10 and supply from M ₁ is 70. Allocate x ₁₃=10 and proceed to next least rank cell. Continue this process till all demands are satisfied and supplies are exhausted. End of this process results in a basic feasible solution as given in Table 3.

Table 3 Initial basic feasible solution

The fuzzy objective value corresponding to the basic feasible solution is given by

Step 5 :

Here p=2, q=3, so p+q−1=2+3−1=4. The basic feasible solution shown in Table 3 of the given FTP contains 4 allocations in independent positions. The allocations are non-degenerate.

Step 6 :

Find the crisp values v _i and w _j by using the relation χ _ij =v _i +w _j . The implied cost of a non basic cell is calculated by using the equation λ _ij =χ _ij −(v _i +w _j ). For the non basic cell (1,2) the calculation is 47−(94+(−45))=−2. Similarly for all non basic cells the implied values are calculated and the respective values are shown in Table 4.

Table 4 Calculation of λ _ij , v _i , and w _j values

Step 7 :

Check the λ _ij values for the non basic cells. In the cell (2,1), λ _ij <0 value is negative. Establish a closed rectilinear path starting from (2,1) as in Table 5. (⇑) denotes origin point of rectilinear path and the closed circuit is illustrated by using ←, →, ↑ and ↓.

Table 5 Closed path from the non basic cell

Step 8 :

From the most negative cell (2,1) signs (+) and (−) are assigned alternatively along the closed circuit, starting with a plus in the (2,1) non basic cell. Comparing allocations in all (−) sign cells, quantity 30 was chosen to be adjusted along the closed circuit. Add the quantity 30 to cells with (+) sign and reduce from cells with (−) sign. The new allocation is given in Table 6.

Table 6 Adjusted allocation—Iteration 1

Step 9 :

The total number of allocations in Table 6 is 4. So, the number of allocation is non-degenerate. Determine crisp values v _i , w _j and finally derive implied cost λ _ij for non basic cells. The values are shown in Table 7.

Table 7 Calculation of λ _ij , v _i and w _j values—Iteration 1

Step 10 :

All λ _ij values (given in parenthesis) in Table 7 are positive. Hence the allocation given in Table 6 is optimal. The optimal fuzzy objective value is

 □

Remark 4

The allocation given by Chanas Method is given in Table 8. The score value of the fuzzy objective got by the proposed algorithm is 7291 which is less than the score value 7516 of Chanas method.

Table 8 Allocation given by Chanas method

Hence solution given by proposed method is better than existing Chanas method. Moreover, in Chanas method demand and supply are assumed to be crisp; whereas, the proposed method can be applied for fuzzy demand and supply also.

Example 2

Consider the following FTP (Pandian and Natarajan 2010a). Here all the parameters of a FTP demand, supply and unit transport costs are fuzzy numbers. This is a Fully Fuzzy Transportation Problem (Table 9).

Table 9 FFTP

Solution

The total supply $\sum_{i=1}^{3}\tilde {M}_{i} =(6, 17, 21, 32)$ and total demand $\sum_{j=1}^{4} \tilde {D}_{j}=(8, 17, 21, 30)$. This is an unbalanced problem. Now introduce imaginary supply $\tilde {M}_{4} =(2,2,2,2)$ and imaginary demand $\tilde {D}_{5} =(0,2,2,4)$ such that $\sum_{i=1}^{4}\tilde {M}_{i} =(8,19,23,34)= \sum_{j=1}^{5} \tilde {D}_{j}$ and assign $\tilde {c}_{ij}=(0,0,0,0)$; for i=4, j=5.

The next step is to calculate the Score value of all cost functions. The score value of the cost functions are given in Table 10.

Table 10 Score values of the fuzzy cost functions

Now allocations are made according to Step 3 of the Fuzzy Transportation Algorithm (FTA). The Initial basic feasible solution constructed by using the proposed algorithm is given in Table 11.

Table 11 Initial basic feasible solution

Therefore fuzzy objective value corresponding to solution given in Table 11 is

To improve this solution, use Steps 6, 7 and 8 given in FTA.

Calculate v _i and w _j values. The values are given in Table 12. The closed rectilinear path and the alternate signs assigned are indicated in Table 13.

Table 12 λ _ij , v _i and w _j values—Iteration 1

Table 13 Closed path and alternate signs assigned—Iteration 1

Here maximum possible reallocation satisfying conditions of Step 3 of FTA is (1,1,1,1). Reallocation was done according to Definition 6. After adjusting fuzzy quantity along closed path, new allocation is given in Table 14.

Table 14 Improved Initial basic feasible solution—Iteration 2

Again repeating the Steps 6, 7 and 8. The closed rectilinear path and alternative signs assigned are illustrated in Table 15. Here maximum possible reallocation is (0,2,2,4). Table 16 gives reallocated fuzzy quantities.

Table 15 Closed path and alternate signs assigned—Iteration 2

Table 16 Improved Initial basic feasible solution—Iteration 3

Redoing the Steps 6, 7 and 8, the assigned closed path and alternative signs are illustrated in Table 17.

Table 17 Closed path and alternate signs assigned—Iteration 3

The reallocation possible here is (0,1,2,3). The new allocation is given in Table 18.

Table 18 Improved Initial basic feasible solution—Iteration 4

To check the possibility of improving the solution, calculate the λ _ij , v _i and w _j values. The calculated values are listed in Table 19.

Table 19 λ _ij , v _i and w _j values—Iteration 4

Since all λ _ij ≥0, the allocation shown in Table 18 is optimal. The fuzzy objective value at various iterations are listed in Table 20. This comparison clearly indicates the improvement in the solution.

Table 20 Comparison of the fuzzy objective values in each iteration

 □

Remark 5

Allocations obtained by Pandian and Natarajan (Pandian and Natarajan 2010a) for Example 2 are $\tilde {x}_{12}=(1,5,6,10)$, $\tilde {x}_{13}=(-9,0,2,11)$, $\tilde{ x}_{23} = (0,1,2,3)$, $\tilde{x}_{31} = (5,7,8,10)$, $\tilde {x}_{23}=(-9,-1,3,11)$, $\tilde {x}_{34}=(1,2,3,4)$. The fuzzy objective value is $\tilde {z} = ( -274,58,188,575)$. This solution is more wide in range, comparing to the solution (22,83,125,236) obtained by the proposed method. Hence solution got by proposed method is more effective.

5 Conclusion

This paper proposed an algorithm to find an optimal solution of a fuzzy transportation problem, where supply, demand and cost coefficients all are fuzzy numbers. It provides decision maker with an effective solution in comparison to existing methods. Since objective value and allocations are fuzzy numbers, more flexibility was given to decision maker. Most of existing procedures convert a transportation problem into a finite number of crisp linear programming problems and use linear programming techniques to solve it. The derived crisp solution gives a very less flexibility to the decision maker. Some methods get a negative allocation (whose membership value is positive) which is not possible in real situations. The solution derived by proposed method is more flexible and optimal in nature. The allocations are always non negative. Hence there is no information loss and the solution derived can be directly used to take decisions. Examples are used from papers Chanas and Kuchta (1996), Pandian and Natarajan (2010a). Comparison of results shows that proposed method derives an optimal solution which is cost efficient.