 Open Access
 Total Downloads : 508
 Authors : P. Jayagowri, Dr. G. Geetharamani
 Paper ID : IJERTV3IS10249
 Volume & Issue : Volume 03, Issue 01 (January 2014)
 Published (First Online): 10012014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
An Intuitionistic Fuzzy Shortest Path Problem Based on Level λ – LR Type Representation
P. Jayagowri, Dr. G. Geetharamani
Department of Mathematics, Sudharsan Engineering college, Pudukottai, Tamilnadu, India. Department of Mathematics, Anna University of Technology, Tiruchirappalli, Tamilnadu, India.
Abstract
The shortest path problem is an important, classical network optimization problem which has a wide range of application in various fields. This paper proposes to find the shortest path in an intuitionistic fuzzy weighted graph with nodes remaining crisp and links remaining crisp but the edge weight will be an Intuitionistic fuzzy number. An existing algorithm is proposed for finding the shortest path length. Finally illustrative numerical examples are given to demonstrate the proposed approach
Key words Acyclic Digraph, 2 Membership function, Weighted Average Index, Total integral index IT
cut interval for LR Trapezoidal Intuitionistic fuzzy number, Convex Index for Intuitionistic fuzzy number, Index Ranking of fuzzy numbers.
1. Introduction
In network problems the weight of the edge in a shortest path problem is supposed to be real numbers, but in most real world problems was the length of the network which represents the time or cost. Fuzzy set theory proposed by Zadeh L.A [1], The fuzzy shortest path problem was introduced by Dubois and Prade [2]. Klin C.M discussed about the fuzzy shortest path [4]. Hyung LK, Song YS, [7] Lee KM., discussed the Similarity Measure between Fuzzy Sets and elements Yao and Lin [10]developed two types of fuzzy shortest path network problem where the first type of fuzzy shortest path problem uses triangular fuzzy numbers and the second type uses level.
1 ,1 interval valued fuzzy numbers. The main result emerging from their study was that the shortest path in the fuzzy sense corresponds to the actual path in the network, and the fuzzy shortest path problem is an extension of the crisp case. Chuang T.N., Kung J.Y.[13] proposed a new algorithm for the discrete fuzzy shortest path problem in a network. L. Sujatha and S. Elizabeth [20,21] found the fuzzy shortest path problem based on Index ranking. In this paper they defined acceptability index, convex index and total integral index using this they proposed many algorithms and found the shortest distance. P.Jayagowri, Dr.G.Geetharamani,[23] discussed, various approaches to solving network problems using TLR intuitionistic fuzzy numbers. This paper is organized as follows; In Section 2 provides the preliminary concepts required for analysis and definitions in fuzzy set theory used throughout the paper, and some new indices and cut interval for LR Trapezoidal intuitionistic fuzzy numbers are introduced. Section 4 gives proposed algorithms based on the indices defined in section2. Section 5 showcases the proposed algorithm and explains its functions. In section 6 some conclusions are drawn.
Preliminaries
In this section ,some basic definitions relating to our work has given, and introduces new definition for convex index , Total integral index, Signed index of level LR intuitionistic trapezoidal fuzzy number.
Acyclic Digraph
A digraph is a graph each of whose edges are directed. Hence an acyclic digraph is a directed graph without cycle.
Membership function of the L.R trapezoidal fuzzy number
Membership function of the LR Trapezoidal fuzzy
number A a, b, c, dLR is
Minimum Operation on 2 shaped fuzzy numbers
The two 2 shaped fuzzy numbers
L1 lw1, lp1, rp1, rw1 and L2 lw 2 , lp2 , rp 2 , rw 2
then,
max lw , lw , min lp , lp , min rp , rp ,
L L , L
1 2 1 2 1 2
0 x a c
min 1 2
min rw1, rw 2
x a c
,
a c x a
Weighted Average Index for level
c
2 Membership Function
A (x) 1
a x b
Let
L =( lw , lp , rp
, rw
; and
b d x
I i i i i
b x b d
d
Lmin (lw,lp, rp, rw;) be two level 2 Membership
0
x b d
function, If
lp lpi , rp rp i ,
then the Weighted
Average Index between Li and Lmin can be calculated
A A i
2 Membership function
as WAI(L min , L I ) =
,0 1, where
2
,
The membership function that has the 2 shape has four parameters ;
lp rp
A
2
and A i
lpi rp i 2
i =1to n.
lw
In the Weighted Average Index, we have
L1 L 2 if
lp lw x
x lp
and only if WAI (L
min
, L1 ) WAI (L
min
, L2 )
2 (x : lw, lp, rp, rw)
1,
rw
lp x rp
, x rp
cut interval for LR trapezoidal fuzzy number
x rp rw
cut interval for LR trapezoidal fuzzy number
It is now used in current research to define the shortest path in a fuzzy sense.
A a, b, c, dLR is
A L U c p c, q s d
Addition operation on numbers
2 shaped fuzzy
A , A
cut interval for LR type representation of fuzzy interval
Assuming that both
A lw
, lp , rp
, rw
and
cut interval for LR type representation of fuzzy
1 1 1 1
interval
A a, b
is given by
B lw 2 , lp2 , rp 2 , rw 2 are fuzzy numbers, then
L U
A A , A a c, d b
A B lw1 lw 2 , lp1 lp2 , rp1 rp 2 , rw1 rw 2
Convex Index (COI)
Let A be an LR trapezoidal fuzzy number, then
CoI A L 1 A U is the cut interval of
A a, b, c, dLR ,if
The ranking of signed distance of level
AL 1 AU min
AL , AU
for
LR type representation of fuzzy interval.
A
A A
Let A p , q , r , s ; ; B p , q , r , s ; be
all , 0,1. If A and B are two LR trapezoidal fuzzy 1
1 1 1
LR 2
2 2 2 LR
numbers, then in convex Index, we have A < B if and only if CoI(A) < CoI(B)
two level intervals. For
LR type representation of fuzzy
(01] the ranking is defined as
Total Integral Index
For fuzzy number A a, b, c, dLR
the Total integral
A A B iff d (A.0) d (B,0)
Mean and standard deviation of level LR Trapezoidal Fuzzy number
index
I T (A) can be constructed from the left integral
Let
A p1, q1, r1, s1; LR
be a
values
I L (A) and the right integral values
I R (A).
the
trapezoidal fuzzy number, then the membership
total integral value
where 0 1
I T (A) with index of optimism
is then defined as,
function in terms of mean and standard deviation is defined as follows:
IT (A) I L (A) (1 )I R (A).———–(3)The left
x ( – )
,
if x
integral values
I L (A) and the right integral values
( ) x
I R (A) of a LR trapezoidal fuzzy number can be found
A (x)
, if
x
a
c
m
n
if
I L (A) a
b
l
2
2 2
2(p q) (s r)
where
and
3(q r) 2(s r)
o
c m n 4 4
a b l
2
If the
i th
fuzzy path Length is
n
c m
Li (pi , qi , ri , si ; )LRand the fuzzy
I R (A) a b
l
shortest lengthis L (p, q, r, s; )
Then the
2
2 2
min LR
a b l n c m
shortest Mean and StandardDeviation Index
2
between LMin and Li is
The signed distance of level
LR Type
I(L
, L ) ( ) (i i )
Representation of Fuzzy interval
Min i
o i
Let
A p , q
, r , s ;
LR
Where
2(p q) (s r)
and
3(q r) 2(s r)
o
be
The
level LR type representation of fuzzy interval.
4 4
Introduces new definition are here.
cut of A is
Minimum Operation on
2 shaped
A A L ()A R ( , 0
and
(01]
Intuitionistic fuzzy numbers:
Where
A L ( )
p r
, A R ( )
q s
Since
For two 2
shaped Intuitionistic fuzzy numbers
L lw
, lp
rp , rw
lw
, lp
rp , rw ,
2
the function is continuous over the interval 0
1 1 1 1 1
1 1 1 1
integration is used for obtaining the mean value of signed distance as follows: d(A.0) = Â¼(2(p+q)+(sr))
L 2 lw , lp2
rp 2
, rw
lw , lp rp , rw
2
2
2 2 2
max(lw 1, lw2 ), min(lp1, lp2 ),
A p , q , r , s
p , q , r , s
is A L U
L min (L1, L 2 )
LR
A , A
min(rp 1, rp 2 ), min(rw 1, rw 2 )
min(lw 1 , lw 2 ), max(lp 1 , lp2 ),
cut intervalis embershipfunctionand
.The above
nonmembershipfunctionas follows
Lmax (L1, L2 )
0,1
max(rp 1 , rp 2 ), max(rw 1 , rw 2 )
Weighted Average index for level 2 Membership function
AL c (a c ) ; AU (b d ) d and
A
A
L c (a c ) ; U (b d ) d
i i i , i i
Let L lw , lp rp , rw ; and
cut interval for LR type representation
Lmin
(lw , lp , rp , rw ; ) be two
2 .
of Intuitionistic fuzzy interval
membershipfunctions
If lp lpi , rp rpi
then theweightedaverage
cut interval for LR type representation of fuzzy
interval A a, b is given by
index between
A L U .The above representation cut
A , A .
L i and L min can be calculated as
A A
interval is obtained for membership function and
nonmember ship function as follows 0,1
2
WAI(Lmin , Li ) i
0 1
A L b c A U d b
WhereA
lp rp 2
and Ai
lp i rp i 2
and
L
A
b

c
U d

b
A
i 1,2,….n.
Weighted Average index for level 2 non membership function
Convex Index for Intuitionistic fuzzy number
Let A be an LR trapezoidal Intuitionistic fuzzy number, then
CoI(A ) A L 1 A U ; CoI(A ) (1 ) A L
A U
Let Li
and Lmax
lw i , lp i , rp i , rw i ;
(lw , lp , rp , rw ; )
be two non
,
Where A
A
L U
and A L
A
If
U are the
cut
membership functions, If
inter al of A p , q , r , s
p , q , r , s
A
A
A
A
l lpi , rp rp i then the weightedaverage index
betweenLi and Lmax can be calculatedas
A L 1 A U
min
L , U ;
A
A
(1 ) A L A U
max
L , U
A
A
A
A
WAI(L
, L ) A Ai
0 1
for all
max
WhereA
i
lp rp 2
2
andAi
lp i rp i 2
i 1,2,….n.
, 0,1
Total Integral Index
For an intuitionsiticfuzzy numberA p
, q
, r
, s
p , q
, r
, s
cut interval for LR trapezoidal
Intuitionistic fuzzy number
cut interval for LR trapezoidal Intuitionistic fuzzy number
The totalintegralindexIT (A)can be constructed from theleft integralsvaluesIL (A) and therightintervalvalue
Mean and standard deviation of level LR trapezoidal Intuitionistic Fuzzy Number
IR (A).The totalintegralvalue IT (A) with index
A p , q , r , s p , q , r , s
LR
of optimism where 0 1.
is intuitiontsictrapezoidal fuzzy number
Is then defined for both membership and non membership function.
If the i th fuzzy path Length for membershipfunction
IT A IL A (1 )I R A ;
is L i (p i , q i , r i , s i ; )LRand the
IT A (1 ) IL A I R A
nonmembershipfunction L i (p i , q i , r i , s i ; )LR
c m n
then fuzzy shortestlengthsare Lmin (p , q , r , s )
I L (A ) a b l
2
and Lmax (p , q , r , s ) Then the shortestMean
n d m
a b
and StandardDeviation Index between LMin andLi is
IR (A ) a b l
n l a , m b l
l ,
2 2
LMax andLi ,
I(LMin , Li )
( ) (i i ) , i
c m n
I(L
, L ) ( ) (i i )
where
IL (A ) a b l ;
Max i
o
2 i
I (A ) a b l n d m
2(p q) (s r)
R
2
and
4
Signed distance of level LR Intuitionistic
3(q p) 2(s r)
o
4
for membershipfunctionand
Fuzzy number(Membership Function)
2(p q) (r s)
A p , q , r , s p , q , r , s is A L U
and
4
LR
The mean valueof signeddistanceis
A , A
3(p q) 2(s r)
o
4
for
NonmembershipFunction
d(A,0)
1
(2(p q ) (s r ))
4
Proposed Algorithm
Algorithm for Intuitionistic fuzzy shortest path problem based on convex index
Signed distance of level LR Intuitionistic Fuzzy number(Non Membership Function)
A p ,q ,r ,s p ,q ,r ,s is A L U
In this section a new algorithm is proposed for finding the Intuitionistic fuzzy shortest path based on convex index.
Step 1:Construct a network G= (V, E) Where V is the
set of vertices and E is the set of edges.
LR
The mean valueof signeddistanceis
A , A
Step 2:Form he possible path
Pi from source node to
destination node and compute the corresponding path
1
d ( A,0)
(2( p q ) (r s ))
4
length Li ii=1,2,m for possible m path and set
Li p i , q i , r i , s i
p i , q i , r i , s i
LR
Step3:Calculate cut interval for LR trapezoidal Intuitionistic fuzzy number ( or LR Type representation of fuzzy interval) for all possible path length, Li I
=1,2,m and set
Step5:Rank the shortest path with the highest weighted index.
Algorithm For Intuitionistic Fuzzy Shortest path problem based on signed distance
Li ( LL
, LU
i 1,2,…m ;
A new algorithm is proposed for finding the
i ( i (
L LL , LU
i 1,2,…m
Intuitionistic fuzzy shortest path based on signed
i ( i (
i (
distance in this paper introduces a new method Signed
Step 4:Calculate Convex Index
distance
CoI(Li ) LL 1 A U ;
i (
L
i (
U
Let Li p i , q i , r i , s i
p i , q i , r i , s i
CoI(Li ) (1 ) Li ( Li (
LR
i
and i=1,2,n where
for all possiblepathlengths
Step 5:Ranking the shortest path with the minimum
L denotes the level LR Intuitionistic fuzzy path
convex index and the corresponding path length the Intuitionistic fuzzy shortest path.
Li is
length.
Step 1: Construct a network G=(V,E) Where V is the set of vertices and E is the set of edges. Here G is an
Algorithm for Intuitionistic fuzzy shortest path problem based on weighted average
acyclic digraph and the arc length takes the level –
LR intuitionistic fuzzy numbers.
index
Step 2: Calculate all possible paths
Pi from source
A new algorithm is proposed for finding the
node to destination node and compute the
Intuitionistic fuzzy shortest path based on weighted average index
corresponding path length
L i =1,2,m for possible
i
Step1:Construct a network G =(V,E) Where V is the set of vertices and E is the set of edges. Here G is an
m paths using definition and set
and
acyclic digraph.
Step 2:Calculate all possible paths Pi from source node
Li
p i , q i , r i , s i
p i , q i , r i , s
i LR
to destination node and compute the corresponding
i 1 to n and 0 1 .
path length Li i =1,2,m for possible m path and set
Step 3: calculate signed distance of level – LR type representation of fuzzy intervals for each possible path
Li p i , q i , r i , s i
p i , q i , r i , s i
LR
using definition 3.8&3.9
Step 4: The path having the minimum signed distance
Step3:Calculate the Intuitionistic fuzzy shortest length.
is identified as the shortest path.
Lmin
using definition and set
Algorithm for Intuitionistic Fuzzy Shortest path
Lmin
p
, q
, r , s ;
Lmax
using definition
problem based on Mean and standard deviation index
A new algorithm is proposed for finding the Intuitionistic fuzzy shortest path based on Mean and
and set
Lmax
p , q , r
, s
standard deviation index in this paper introduces a new method called Mean and Standard Deviation index
Step4:Calculate weighted average index using
which acts as the measurement tool between
Lmin
and
definition and the rank to the path based on weighted index.
L L
, L and
i max i
Let L
p , q
, r , s
p , q
, r , s
P1 :1 2 4
L1 (7,34,39,9;1)
i i
i i
i i
i i
i LR
and L
(7,36,34,9;1)
i
and i=1,2,n where L denotes the level LR Intuitionistic fuzzy path length.
1 P2 :1 4
L2 (6,28,30,7;1)
Step1:Construct a network G =(V,E) Where V is the
and
L2 (3,30,31,6;1)
set of vertices and E is the set of edges. here G is an acyclic digraph.
Step 2:Calculate all possible paths Pi from source node to destination node and compute the corresponding
P3 :1 3 4 L3 (9,41,49,14;1)
and L3 (13,46,467, ;1)
path length Li ,
i =1,2,m for possible m path and set
Step 3:
Lmin 9,28,30,7;1
and Lmax 3,46,46,9;1
Li p i , q i , r i , s i
p i , q i , r i , s i
LR
Step 4: Let distance index.
1
for weighted index, signed
Step 3:Calculate the Intuitionistc fuzzy shortest length.
Table 1 Results of the Network Based on Level
Lmin
using definitionand set
Lmin
p , q , r , s ;
Lamda TLR Weighted Index
Lmax
using definition and set
Lmax
p , q , r , s
Step 4:Calculate Mean and standard deviation index
between
definition 3.10.
Lmin ,
and
L Lmax and
i
,
L using
i
Step 5:The path having the maximum Mean and Standard deviation index is identified as the shortest path.
ILLUSTRATIVE EXAMPLE
Step1:Construct a network with 4 vertices and 5 edges as follows: Fig (1)
i 
paths 
W (L , L A min i 
R a n k 
W (L , L ) A max i 
Ra nk 
1 
P1 :1 2 4 
32.75 
2 
40.5 
2 
2 
P2 :1 4 
29 
1 
38.25 
1 
3 
P3 :1 3 4 
37 
3 
46 
3 
Table 2 Results of the Network Based on Level Lamda TLR Signed Distance Index
Step 2: The possible paths and the corresponding path lengths are as follows
i 
paths 
d(L i ,0) 
Ra nk 
d(L i ,0) 
Ra nk 
1 
P1 :1 2 4 
13 
2 
4 
2 
2 
P2 :1 4 
11.3 
1 
5 
1 
3 
P3 :1 3 4 
16.3 
3 
7.8 
3 
Let .3
and .5 for convex index
Table 3 Results of the Network Based on Convex Index
Step 5:Path P2 :1 4 is the Intuitionistic fuzzy shortest path since it has the highest level Trapezoidal LR weighted average index and the corresponding shortest path length is
i 
paths 
COI A (L min , L i ) 
R a n k 
COI A (L max , L i ) 
Ra nk 
1 
P1 :1 2 4 
5.15 
2 
7.35 
2 
2 
P2 :1 4 
1.15 
1 
4.85 
1 
3 
P3 :1 3 4 
7.85 
3 
12.45 
3 
L2 (6,28,30,7;1)LR
and
L2 (3,30,31,6;1)LR . he
Total integral index for different values of
solution obtained for Intuitionistic fuzzy shortest path problem in this paper coincides with the solution of the existing algorithm.
Conclusion
This paper developed three algorithms for solving the shortest path problem on a network with intuitionistic fuzzy arc length. The ranking given to the paths is helpful for the decisionmakers as they make decisions
(i)
Let .3 then,
in choosing the best of all the possible path alternatives.
(i)
Table 4 Results of the Network Based on Total Integral Index
i 
paths 
ITA (L min L i ) 
Ran k 
ITA (L max , L i ) 
Ran k 
1 
P1 :1 2 4 
64.2 
2 
80.85 
2 
2 
P2 :1 4 
53.4 
1 
64.85 
1 
3 
P3 :1 3 4 
79.0 
3 
110.15 
3 
1 then,
Table 5 Results of the Network Based on Total Integral Index
i 
paths 
I(Lmin , L i ) 
Rank 
I(Lmax , L i ) 
Rank 
1 
P1 :1 2 4 
.9967 
2 
1.070 
2 
2 
P2 :1 4 
1.022 
1 
1.131 
1 
3 
P3 :1 3 4 
.9603 
3 
.9421 
3 
Verification is also done with the existing methods, which helps to conclude that the algorithms developed in the current paper are an alternative and improved form of previous methods, to get the shortest path in intuitionistic fuzzy environments.
References
[1]Zadeh L.A Fuzzy sets as a basis for a theory of possibility,Fuzzy Sets and Systems,Vol 1, No 1,pp3 28,1978. [2]D.Dubois and H.Prade,Fuzzy Sets and Systems,Academic Press, New York,1980. [3]K.Atanassov, Intuitionistic Fuzzy Sets and Systems, volume 20, No. 1(1986),8796.
Klein,C.M, Fuzzy Shortest Paths, Fuzzy Sets and Systems 39,2741 1991.

Liu X. Entropy, Length Measure and Similarity Measure of Fuzzy Sets and their Relations, Fuzzy sets and systems,52.305 18 1992.

Lin K.C.,Chern M.S., The Fuzzy Shortest Path Problem and its Most Vital arcs., Fuzzy Sets and Systems 58,343 353,1993.

Hyung LK, Song YS, Lee KM., Similarity Measure between Fuzzy Sets and Elements .Fuzzy Sets and Systems, 62291 3, 1994.

Wang WJ. New Similarity Measures on Fuzzy Sets and On Elements. Fuzzy Sets and Systems., 85, 3059 1997. [9]Okada S.Soper.T.,A Shortest Path Problem on a Network with Fuzzy arc Lengths. Fuzzy Sets and Systems.109,129 140,2000.

Yao, J.S and Lin F.T. Fuzzy shortestpath network problems with uncertain edge weights, Journal of Information Science and Engineering, 19, 329351, 2003.

Takahashi M.T., Yaamakani . A On fuzzy optimized path problem with fuzzy parameter an algorithm approach.Proceeding of the Annual Meeting of the North American Fuzzy Information Processing Society 654 657.2005.

Kung J.Y.,Chuang T.N, and C.T.Lin ,Decision Making On Network Problem With Fuzzy arc lengths, IMACS Multiconference on Computational Engineering in Systems Applications(CESA)(2006)578580

Chuang T.N., Kung J.Y.,A new Algorithm for the Discrete Fuzzy Shortest Path Problem in a Network .Applied Mathematics and Computation.174.660668.2006 [14]Xinfan Wang, Fuzzy Number Intuitionistic Fuzzy arithmetic Aggregation Operators. International Journal of Fuzzy Systems, Volume 10, N0.2, jume 2008.
[16]S. Abbaasbandy and T. Hajjari, A New approach for ranking of trapezoidal fuzzy numbers, computer and mathematics with applications, Vol.57, pp 413 419 2009. [17]Kumar.A., Singh.P Kaur. A and Kaur. P Ranking of generalized trapezoidal fuzzy numbers based on rank, mode, divergence and spread, Turkish Journal of Fuzzy systems,1(2):141152.
[18]A.Nagoor gani, M.Mohammed Jabbarulla On Searching Intuitionistic Fuzzy Shortest Path in a Network .Applied Mathematical Sciences, Vol 4, 2010,no, 69,34473454. [19]Amit kumar,Manoj kaur,A new Algorithm for Solving Network Flow Problems with Fuzzy arc Lengths TJFS: Turkish Journal of Fuzzy Systemsvolume .2 No.1.pp.2011. [20]S.Elizabeth and L.Sujatha, Fuzzy Shortest path problem based on Index ranking, Journal of Mathematics Research Vol3, No.4, Nov 2011. [21]S.Elizabeth and L.Sujatha, Fuzzy Shortest PathPromblem Based on Level
LR type representation of
Fuzzy Interval; International conference on Mathematics in Engineering and Business management 9788182860155 2012.
[22]P.jayagowri, Dr.G.Geetharamani Using Similarity degree approach to find shortest path for intuitionistic fuzzy in a network in IEEE Xplore Digital library.March, 2012. [23]P.Jayagowri, Dr.G.Geetharamani,Various Approaches for Solving the Network Problems Using TLR Intuitionistic FuzzyNumbers ,InternationJournal of computer applications vol 63No.20, Feb 2013.