# An Intuitionistic Fuzzy Shortest Path Problem Based on Level λ – LR Type Representation

DOI : 10.17577/IJERTV3IS10249

Text Only Version

#### 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)+(s-r))

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

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

#### Step3:Calculate the Intuitionistic fuzzy shortest length.

is identified as the shortest path.

Lmin

using definition and set

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

#### 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

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

#### 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 decision-makers 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),87-96.

1. Klein,C.M, Fuzzy Shortest Paths, Fuzzy Sets and Systems 39,27-41 1991.

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

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

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

5. Wang WJ. New Similarity Measures on Fuzzy Sets and On Elements. Fuzzy Sets and Systems., 85, 305-9 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.

1. Yao, J.S and Lin F.T. Fuzzy shortest-path network problems with uncertain edge weights, Journal of Information Science and Engineering, 19, 329-351, 2003.

2. 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.

3. 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)578-580

4. Chuang T.N., Kung J.Y.,A new Algorithm for the Discrete Fuzzy Shortest Path Problem in a Network .Applied Mathematics and Computation.174.660-668.2006 [14]Xinfan Wang, Fuzzy Number Intuitionistic Fuzzy arithmetic Aggregation Operators. International Journal of Fuzzy Systems, Volume 10, N0.2, jume 2008.

[15]Iraj Mahdavi, Ali Tajdin, Rahele Nourifar Hasanzade R and Amiri, N.M, A dynamic programming approach for finding shortest chains in fuzzy network, Applied Soft computing, Vol 9, No.2, pp. 503-511, 2009.

[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):141-152.

[18]A.Nagoor gani, M.Mohammed Jabbarulla On Searching Intuitionistic Fuzzy Shortest Path in a Network .Applied Mathematical Sciences, Vol 4, 2010,no, 69,3447-3454. [19]Amit kumar,Manoj kaur,A new Algorithm for Solving Network Flow Problems with Fuzzy arc Lengths TJFS: Turkish Journal of Fuzzy Systems-volume .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 Path

Promblem Based on Level

LR type representation of

Fuzzy Interval; International conference on Mathematics in Engineering and Business management 978-81-8286-015-5 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 ,Internation

Journal of computer applications vol 63-No.20, Feb 2013.