# Using Trapezoidal Intuitionistic Fuzzy Number to Find Optimized Path in a Network

Authors: P. Jayagowri; G. Geetha Ramani
Journal: Advances in Fuzzy Systems
 (2014)

---

## Abstract

In real life, information available on situations/issues/problems is vague, inexact, or insufficient and so the parameters involved therein are grasped in an uncertain way by the decision maker. But in real life such uncertainty is unavoidable. One possible way out is to consider the knowledge of experts about the parameters involved as fuzzy data. In a network, the arc length may represent time or cost. In Relevant literature reports there are several methods to solve such problems in network-flow. This paper proposes an optimized path for use in networks, using trapezoidal intuitionistic fuzzy numbers, assigned to each arc length in a fuzzy environment. It proposes a new algorithm to find the optimized path and implied distance from source node to destination node.


---

## Body

## 1. Introduction

Fuzzy network problems have appeared in literature for quite some time, of which the simplest and most often researched mode is the fuzzy shortest path problem. The main objective of the optimized path problem is to find a path with minimum distance. The classical fuzzy shortest path problem seems to have been first introduced by Dubois and Prade [1]. They employed the fuzzy minimum operator to find the shortest path length, but they did not develop any method to decide the shortest path. They have used a fuzzy number instead of a real number assigned to each of the edges. Okada and Soper [2] concentrated on an optimized path problem and introduced the concept of degree of possibility in which an arc is on the optimized path. Takahashi and Yamakami [3] discussed the optimized path from a specified node to every other node on a network. Another algorithm for this problem was presented by Okada and Gen [4, 5], where there is a generalization of Dijkstra’s algorithm. In this algorithm the weight of the arcs is considered to be interval numbers and is defined from a partial order between interval numbers.Klein [6] proposed an improved algorithm that can get the shortest path length as well as the shortest path. However, the assumption made in the algorithm, that each arc with the length between “1” and a fixed integer “M” was not reasonable and practical. Szmidt and Kacprzyk [7] found distance between intuitionistic fuzzy sets using Hamming distance, the normalized Hamming distance, the Euclidean distance, and the normalized Euclidean distance. Kung and Chuang [8] pointed out that there are several methods to solve this kind of problem in the available literature. Przemysław Grzegorzewski [9] discussed two families of metrics in space of intuitionistic fuzzy numbers. Nagoor Gani and Mohammed Jabarulla [10] introduced a new algorithm to find an intuitionistic fuzzy optimized path in network problems. Lin and Chern [11] discussed the fuzzy optimized path problem and its most vital arcs. Hernandes et al. [12] have proposed a new algorithm to find the shortest path with fuzzy parameters on networks.Kumar and Kaur [13] related an existing algorithm tracking the optimized path with fuzzy arc length. Jayagowri and Geetharamani [14] also did the same with a shortest path problem using intuitionistic triangular fuzzy numbers. Yu [15] proposed generalized intuitionistic trapezoidal fuzzy weighted average operator to aggregate the intuitionistic trapezoidal fuzzy numbers. Numerous articles have been published on fuzzy shortest path problems.The present paper is organized as follows. In Section2 some basic definitions are given and the required notations are explained. In Section 3 the optimized path obtained and its distance from intuitionistic trapezoidal fuzzy numbers are completed using the proposed algorithm with numerical examples. Section 4 discusses the results and advantages of the method proposed. In Section 5 the conclusions are presented.


## 2. Preliminary and Definitions

In this section, some basic definitions relating to fuzzy sets and intuitionistic fuzzy sets are given.


### 2.1. Acyclic Digraph

A directed graph is graph G, that is, a set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another. A directed graph is sometimes called a digraph. Also G does not perform a cycle. Hence G is an acyclic digraph.


### 2.2. Fuzzy Set(Zadeh [16])

Let “X” be the universal set. A fuzzy set A in X represented by A={(x,μA(x))/x∈X}, where the function μA(x):X→[0,1] is the membership degree of element x in the fuzzy set A.


### 2.3. Intuitionistic Fuzzy Set (Atanassov [17])

LetX be a universe of discourse, then an intuitionistic fuzzy set A in X is given by a set of ordered triples: A={(x,μA,γA(x))/x∈X}, where μA(x),γA(x):X→[0,1] are functions such that 0≤μA(x)+γA(x)≤1, for all x∈X. For each x  the numbers μA(x) and γA(x) represent the degree of membership and non-membership of the element x∈X to A⊂X, respectively.


### 2.4. Fuzzy Number

A fuzzy number is a quantity whose value is imprecise, rather than exact as is the case with “ordinary” (single-valued) numbers. Any fuzzy number can be thought of as a function whose domain is a specified set. Each numerical value in the domain is assigned a specific “grade of membership.”


### 2.5. Intuitionistic Fuzzy Number

An intuitionistic fuzzy setA={〈x,μA(x),γA(x)〉,x∈R} such that μA and 1-γA, where (1-γA)(x)=1-γA(x) for all x∈X, are fuzzy numbers called intuitionistic fuzzy numbers.We denote byA=〈μA,γA〉 an intuitionistic fuzzy number and by IF (R) the set of all intuitionistic fuzzy numbers. It is obvious that any fuzzy number u can be represented as an intuitionistic fuzzy number by 〈u,1-u〉.We say (μA(x),γA(x)) is an intuitionistic fuzzy number throughout this paper, where the function μA(x):X→[0,1] and γA(x):X→[0,1]. For convenience, we denote an intuitionistic fuzzy number by A=(〈a,b,c〉〈l,m,n〉), where 〈a,b,c〉∈F(I)〈l,m,n〉∈F(I),I=[0,1]0≤c+n≤1.


### 2.6. Trapezoidal Fuzzy Number

A fuzzy numberA~=(a,b,c,d) is called trapezoidal fuzzy number if its membership function is given by (see Figure 1)
(1)μA¯(x)={x-ab-a,a≤x≤b;1,b≤x≤c;x-dc-d,c<x≤d;0,others,wherea,b,c,d∈R.Figure 1
Trapezoidal fuzzy number.


### 2.7. Trapezoidal Intuitionistic Fuzzy Number

Leta¯ be an intuitionistic trapezoidal fuzzy number, and its membership function is
(2)μa¯(x)={x-ab-aμa¯,a≤x≤b;μa¯,b≤x≤c;d-xd-cμa¯,c<x≤d;0,others.
Its nonmembership function is
(3)Va¯(x)={b-x+va¯(x-a)b-a,a1≤x<b;va¯,b≤x≤c;x-c+va¯(d1-x)d1-c,c<x≤d1;0,others,
where 0≤μa¯≤1;0≤va¯≤1 and μa¯+va¯≤1;a,b,c,d∈R. Then a¯=〈([a,b,c,d];μa¯),([a1,b,c,d1];va¯)〉 is called a trapezoidal intuitionistic fuzzy number (see Figure 2).Figure 2
Trapezoidal intuitionistic fuzzy number.


### 2.8. Addition of Two Trapezoidal Intuitionistic Fuzzy Numbers(Jianqiang and Zhong, 2009 [18])

Leta¯1=([a1,b1,c1,d1];μa¯1,va¯1) and a¯2=([a2,b2,c2,d2];μa-2,va-2) with λ≥0 be two intuitionistic trapezoidal fuzzy numbers; the following operations are valid:
(4)a¯1+a¯2=(μa¯1+μa¯2-μa¯1·μa¯2,va¯1·va¯2[a1+a2,b1+b2,c1+c2,d1+d2];cccccμa¯1+μa¯2-μa¯1·μa¯2,va¯1·va¯2).


### 2.9. Ranking Function

A ranking functionR:F(R)→R, where F(R) is set of all fuzzy numbers defined on set of real numbers and maps each fuzzy number into a real number. Let A¯ and B¯ be two triangular or trapezoidal fuzzy numbers; then(i)
A¯>B¯ifandonlyifR(A¯)>R(B¯),(ii)
A¯<B¯ifandonlyifR(A¯)<R(B¯),(iii)
A¯≈B¯ifandonlyifR(A¯)=R(B¯).


### 2.10. Notations

The notations that will be used throughout the paper are as follows.N={1,2,…n}: the set of all nodes in a network.Nm(j): the set of all predecessor nodes of node j.m¯i: the intuitionistic fuzzy membership function distance between node i and source node.m¯ij: the intuitionistic fuzzy distance between node i and j.n¯i: the intuitionistic fuzzy nonmembership function distance between node i and source node.n¯ij: the intuitionistic fuzzy nonmembership function distance between node i and j.pi: the path in the ith node.d~j: total intuitionistic fuzzy distance between the source node and destination node.Remark 1.
A nodei is said to be the predecessor node of node j if(i)
nodei is directly connected to node j,(ii)
the direction of path connecting nodesi and j is from i to j.


## 2.1. Acyclic Digraph

A directed graph is graph G, that is, a set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another. A directed graph is sometimes called a digraph. Also G does not perform a cycle. Hence G is an acyclic digraph.


## 2.2. Fuzzy Set(Zadeh [16])

Let “X” be the universal set. A fuzzy set A in X represented by A={(x,μA(x))/x∈X}, where the function μA(x):X→[0,1] is the membership degree of element x in the fuzzy set A.


## 2.3. Intuitionistic Fuzzy Set (Atanassov [17])

LetX be a universe of discourse, then an intuitionistic fuzzy set A in X is given by a set of ordered triples: A={(x,μA,γA(x))/x∈X}, where μA(x),γA(x):X→[0,1] are functions such that 0≤μA(x)+γA(x)≤1, for all x∈X. For each x  the numbers μA(x) and γA(x) represent the degree of membership and non-membership of the element x∈X to A⊂X, respectively.


## 2.4. Fuzzy Number

A fuzzy number is a quantity whose value is imprecise, rather than exact as is the case with “ordinary” (single-valued) numbers. Any fuzzy number can be thought of as a function whose domain is a specified set. Each numerical value in the domain is assigned a specific “grade of membership.”


## 2.5. Intuitionistic Fuzzy Number

An intuitionistic fuzzy setA={〈x,μA(x),γA(x)〉,x∈R} such that μA and 1-γA, where (1-γA)(x)=1-γA(x) for all x∈X, are fuzzy numbers called intuitionistic fuzzy numbers.We denote byA=〈μA,γA〉 an intuitionistic fuzzy number and by IF (R) the set of all intuitionistic fuzzy numbers. It is obvious that any fuzzy number u can be represented as an intuitionistic fuzzy number by 〈u,1-u〉.We say (μA(x),γA(x)) is an intuitionistic fuzzy number throughout this paper, where the function μA(x):X→[0,1] and γA(x):X→[0,1]. For convenience, we denote an intuitionistic fuzzy number by A=(〈a,b,c〉〈l,m,n〉), where 〈a,b,c〉∈F(I)〈l,m,n〉∈F(I),I=[0,1]0≤c+n≤1.


## 2.6. Trapezoidal Fuzzy Number

A fuzzy numberA~=(a,b,c,d) is called trapezoidal fuzzy number if its membership function is given by (see Figure 1)
(1)μA¯(x)={x-ab-a,a≤x≤b;1,b≤x≤c;x-dc-d,c<x≤d;0,others,wherea,b,c,d∈R.Figure 1
Trapezoidal fuzzy number.


## 2.7. Trapezoidal Intuitionistic Fuzzy Number

Leta¯ be an intuitionistic trapezoidal fuzzy number, and its membership function is
(2)μa¯(x)={x-ab-aμa¯,a≤x≤b;μa¯,b≤x≤c;d-xd-cμa¯,c<x≤d;0,others.
Its nonmembership function is
(3)Va¯(x)={b-x+va¯(x-a)b-a,a1≤x<b;va¯,b≤x≤c;x-c+va¯(d1-x)d1-c,c<x≤d1;0,others,
where 0≤μa¯≤1;0≤va¯≤1 and μa¯+va¯≤1;a,b,c,d∈R. Then a¯=〈([a,b,c,d];μa¯),([a1,b,c,d1];va¯)〉 is called a trapezoidal intuitionistic fuzzy number (see Figure 2).Figure 2
Trapezoidal intuitionistic fuzzy number.


## 2.8. Addition of Two Trapezoidal Intuitionistic Fuzzy Numbers(Jianqiang and Zhong, 2009 [18])

Leta¯1=([a1,b1,c1,d1];μa¯1,va¯1) and a¯2=([a2,b2,c2,d2];μa-2,va-2) with λ≥0 be two intuitionistic trapezoidal fuzzy numbers; the following operations are valid:
(4)a¯1+a¯2=(μa¯1+μa¯2-μa¯1·μa¯2,va¯1·va¯2[a1+a2,b1+b2,c1+c2,d1+d2];cccccμa¯1+μa¯2-μa¯1·μa¯2,va¯1·va¯2).


## 2.9. Ranking Function

A ranking functionR:F(R)→R, where F(R) is set of all fuzzy numbers defined on set of real numbers and maps each fuzzy number into a real number. Let A¯ and B¯ be two triangular or trapezoidal fuzzy numbers; then(i)
A¯>B¯ifandonlyifR(A¯)>R(B¯),(ii)
A¯<B¯ifandonlyifR(A¯)<R(B¯),(iii)
A¯≈B¯ifandonlyifR(A¯)=R(B¯).


## 2.10. Notations

The notations that will be used throughout the paper are as follows.N={1,2,…n}: the set of all nodes in a network.Nm(j): the set of all predecessor nodes of node j.m¯i: the intuitionistic fuzzy membership function distance between node i and source node.m¯ij: the intuitionistic fuzzy distance between node i and j.n¯i: the intuitionistic fuzzy nonmembership function distance between node i and source node.n¯ij: the intuitionistic fuzzy nonmembership function distance between node i and j.pi: the path in the ith node.d~j: total intuitionistic fuzzy distance between the source node and destination node.Remark 1.
A nodei is said to be the predecessor node of node j if(i)
nodei is directly connected to node j,(ii)
the direction of path connecting nodesi and j is from i to j.


## 3. Proposed Algorithm

In this section a new algorithm is proposed for finding the intuitionistic fuzzy shortest path and shortest distance of each node from source node. The steps of the algorithm are summarized as follows.Initially we have to label the source nodes asm¯1=(0,0,0,0) and n¯1=(0,0,0,0) which represent membership function and nonmembership function, respectively. We have to find the mj and nj using minimum of mj and mij for membership function ni and nij for nonmembership function, respectively, in order to find a path from i to j, where i and j are the minimum values which are in mj and nj. The above step is repeated until path is calculated for all the nodes starting from source node to destination node. We have to discard the path if there is no path between any nodes which do not have direct or indirect link. Thus fuzzy optimal path is obtained. The most optimal distance is measured by the summation of the value of the membership and nonmembership functions which are involved in fuzzy optimized path.Step
1. Initialize the label of the source nodes (i=1) m¯1=(0,0,0,0) and n¯1=(0,0,0,0).Step
2. Consider the following:findm¯j=min⁡(m¯j⊕m¯ij)/i∈N(m(j)),j≠1,j=2,3,4…n;n¯j=min⁡(n¯i⊕n¯ij)/i∈N(n(j)),j≠1,j=2,3,4…n.Then find pi=i→j, where i and j are the values of the minimum value which is in mj for membership function and nj for nonmembership function.Step
3. Repeat Step 2 until pi is calculated for all the nodes starting from source node to destination node, but fuzzy distance along all paths is d~j.Step
4. Discard the path which does not have either direct or indirect link with the source node and destination node.Step
5. Now the fuzzy optimized path can be obtained by combining the remaining paths starting from source node to destination node.Step
6. The intuitionistic fuzzy shortest distance between source node and destination node is calculated by the sum of the value of the intuitionistic fuzzy number which is involved in the intuitionistic fuzzy optimized path in Step 5.Illustrative Example. In order to illustrate the above procedure consider a small network shown in Figure 3, where each arc length is represented as a trapezoidal intuitionistic fuzzy number.Figure 3Initially we have to label the source nodes asm¯1=(0,0,0,0) and n¯1=(0,0,0,0) which represent membership function and nonmembership function, respectively. In Steps 2 and 3, first let us take i=1 and j=2 and then find m-2 and n-2 using the formula which is represented in the proposed algorithm. Next assume that i=1,2 and j=3 and find m-3 and n-3. Similarly we extend this value up to i=1,2,3,4,5 and j=6. (Since node 6 is the destination node, n=6.) Steps 4, 5, and 6 are briefly explained in Table 1. From the table we can easily identify the required optimal path and shortest distance.Table 1
Tabular representation of link between source and destination nodes.
j
m
p
i
n
p
i
D/ID link with source node
D/ID link with destination node
Direct/indirect link with source and destination nodes
Distance
2
m
p
1
= 1→2
n
p
1
= 1→2
YesDIRLink
No
Discard
Discard
3
m
p
1
= 1→3
n
p
1
= 1→3
YesDIRLink
YesIDLink
Yes
〈
3,2
,
1,5
〉
〈
5,4
,
3,7
〉
4
m
p
3
= 3→4
n
p
3
= 3→4
YesIDLink
YesIDLink
Yes
〈
8,10,4
,
12
〉
〈
11,13,8
,
17
〉
5
m
p
2
= 2→5
n
p
2
= 2→5
YesIDLink
No
Discard
Discard
6
m
p
4
= 4→6
n
p
4
= 4→6
YesIDLink
YesDIRLink
Yes
〈
10,13,9
,
18
〉
〈
14,18,14,25
〉
Hence the required path is 1→3→4→6.
Required shortest distance is (〈10, 13, 9, 18〉 〈14, 18, 14, 25〉).Step
1. Assume m¯1=(0,0,0,0) and n¯1=(0,0,0,0).Steps
2 and
3. Consider the following.(i)
Puti=1,   j=2;
m¯j=min⁡{mi⊕mij};m¯2=min⁡{m1⊕m12}=min⁡{(0,0,0,0)⊕(6,7,8,9)};m¯2=(6,7,8,9)andn¯j=min⁡{ni⊕nij};n¯2=min⁡{n1⊕n12}=min⁡{(0,0,0,0)⊕(7,8,9,10)};n¯2=(7,8,9,10)∴p1=1→2.(ii)
Puti=1,2,j=3;
m¯3=min⁡{m1⊕m13,m2⊕m23};m¯3=min⁡{(0,0,0,0)⊕(3,2,1,5)}(since there exists no path between any two vertices (edge connectivity), then we infer that d(u,v)=∞);m¯3=(3,2,1,5) and n¯3=min⁡{n1⊕n13,n2⊕n23};n¯3=min⁡{(0,0,0,0)⊕(5,4,3,7)};n¯3=(5,4,3,7)∴p1=1→3.(iii)
Puti=1,2,3,  j=4;
m¯4=min⁡{m1⊕m14,m2⊕m24,m3⊕m34};m¯4=min⁡{(3,2,1,5)⊕(5,8,3,7)};m¯4=(8,10,4,12) and  n¯4=min⁡{n1⊕n14,n2⊕n24,n3⊕n34};n¯4=min⁡{(5,4,3,7)⊕(6,9,5,10)};n¯4=(11,13,8,17)∴p3=3→4.(iv) Put
i=1,2,3,4,j=5;
m¯5=min⁡⁡{m1⊕m15,m2⊕m25,m3⊕m35,m4⊕m45};m¯5=min⁡⁡{(6,7,8,9)⊕(4,7,6,8),(8,10,4,12)⊕(3,6,7,8)};m¯5=min⁡{(10,14,14,17),(11,16,11,20)};m¯5=(10,14,14,17) and n¯5=min⁡⁡{n1⊕n15,n2⊕n25,n3⊕n35,n4⊕n45};n¯5=min⁡⁡{(7,8,9,10)⊕(6,8,7,9),(11,13,8,17)⊕(5,8,9,12)};n¯5=min⁡⁡{(13,16,16,19), (16,21,17,29)};n¯5=(13,16,16,19)∴p2=2→5.(v)
Puti=1,2,3,4,5, j=6;
m¯6=min⁡{m1⊕m16,m2⊕m26,m3⊕m36,m4⊕m46,m5⊕m56};m¯6=min⁡{(8,10,4,12)⊕(2,3,5,6),(10,14,14,17)⊕(5,10,11,12)};m¯6=min⁡{(10,13,9,18),(15,24,25,29)};m¯6=(10,13,9,18) and n¯6=min⁡{n1⊕n16,n2⊕n26,n3⊕n36,n4⊕n46,n5⊕n56};n¯6=min⁡{(11,13,8,17)⊕(3,5,6,8),(13,16,16,9)⊕(6,11,13,14)};n¯6=min⁡⁡{(14,18,14,25),(19,27,29,33)};n¯6=(14,18,14,25)∴p4=4→6.Steps
4,
5, and
6. Table 1 shows the results of membership and nonmembership functions, direct/indirect link with source node, and direct/indirect link with destination node from Steps 2 and 3. Direct/indirect link between source node and destination node and distance result through direct/indirect link with source node and direct/indirect link with destination node.


## 4. Results and Discussion

In this section the results obtained by using the proposed algorithm are discussed. The obtained fuzzy optimized path and fuzzy optimized distance between node 1 and node 6 are 1→3→4→6 and(〈10,13,9,18〉,〈14,18,14,25〉), respectively. The paper justifies that, each and every step derived from the direct or indirect link, the reader can decide whether to select the shortest path or to discard the path. The procedure for finding shortest path and distance is simple. If a decision maker wants to find the Intuitionistic fuzzy optimized path and Intuitionistic fuzzy optimized distance between source-node and sink-node, by using the suggested algorithm, the whole procedure need not be repeated again and again. For using the proposed algorithm the decision maker should have knowledge of ranking function and the additive arithmetic operations of Intuitionistic fuzzy numbers. A deep knowledge of intuitionistic fuzzy linear programming, crisp linear programming, and use of any operation research technique are not needed for finding the shortest path. It is very easy to learn and implement in any programming language. Thus the proposed algorithm is liable.


## 5. Conclusion

In real life networks, the number of nodes is larger. Intuitionistic fuzzy optimized path length and optimized distance are information vital for decision makers in the field of logistics. Here the objective is to transport various quantities of a single homogeneous commodity initially stored at various origins to different destinations in such a way that the transportation cost is minimum. In this paper we have developed an algorithm to find the intuitionistic fuzzy optimized paths and optimized distance of a network with its arc length as trapezoidal intuitionistic fuzzy numbers. An illustrative example has been included to demonstrate the proposed method.



---

*Source: 183607-2014-05-11.xml*