Interval Type 2 Fuzzy Set in Fuzzy Shortest Path Problem
The shortest path problem (SPP) is one of the most important combinatorial optimization problems in graph theory due to its various applications. The uncertainty existing in the real world problems makes it difficult to determine the arc lengths exactly. The fuzzy set is one of the popular tools to...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2016-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | http://www.mdpi.com/2227-7390/4/4/62 |
| _version_ | 1819263245462011904 |
|---|---|
| author | Arindam Dey Anita Pal Tandra Pal |
| author_facet | Arindam Dey Anita Pal Tandra Pal |
| author_sort | Arindam Dey |
| collection | DOAJ |
| description | The shortest path problem (SPP) is one of the most important combinatorial optimization problems in graph theory due to its various applications. The uncertainty existing in the real world problems makes it difficult to determine the arc lengths exactly. The fuzzy set is one of the popular tools to represent and handle uncertainty in information due to incompleteness or inexactness. In most cases, the SPP in fuzzy graph, called the fuzzy shortest path problem (FSPP) uses type-1 fuzzy set (T1FS) as arc length. Uncertainty in the evaluation of membership degrees due to inexactness of human perception is not considered in T1FS. An interval type-2 fuzzy set (IT2FS) is able to tackle this uncertainty. In this paper, we use IT2FSs to represent the arc lengths of a fuzzy graph for FSPP. We call this problem an interval type-2 fuzzy shortest path problem (IT2FSPP). We describe the utility of IT2FSs as arc lengths and its application in different real world shortest path problems. Here, we propose an algorithm for IT2FSPP. In the proposed algorithm, we incorporate the uncertainty in Dijkstra’s algorithm for SPP using IT2FS as arc length. The path algebra corresponding to the proposed algorithm and the generalized algorithm based on the path algebra are also presented here. Numerical examples are used to illustrate the effectiveness of the proposed approach. |
| first_indexed | 2024-12-23T20:10:31Z |
| format | Article |
| id | doaj.art-955f787a7f7244ba817283dedbfce655 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-12-23T20:10:31Z |
| publishDate | 2016-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-955f787a7f7244ba817283dedbfce6552022-12-21T17:32:48ZengMDPI AGMathematics2227-73902016-10-01446210.3390/math4040062math4040062Interval Type 2 Fuzzy Set in Fuzzy Shortest Path ProblemArindam Dey0Anita Pal1Tandra Pal2Department of Computer Science and Engineering, Saroj Mohan Institute of Technology, Hooghly 712512, West Bengal, IndiaDepartment of Mathematics, National Institute of Technology, Durgapur 713209, West Bengal, IndiaDepartment of Computer Science and Engineering, National Institute of Technology, Durgapur 713209, West Bengal, IndiaThe shortest path problem (SPP) is one of the most important combinatorial optimization problems in graph theory due to its various applications. The uncertainty existing in the real world problems makes it difficult to determine the arc lengths exactly. The fuzzy set is one of the popular tools to represent and handle uncertainty in information due to incompleteness or inexactness. In most cases, the SPP in fuzzy graph, called the fuzzy shortest path problem (FSPP) uses type-1 fuzzy set (T1FS) as arc length. Uncertainty in the evaluation of membership degrees due to inexactness of human perception is not considered in T1FS. An interval type-2 fuzzy set (IT2FS) is able to tackle this uncertainty. In this paper, we use IT2FSs to represent the arc lengths of a fuzzy graph for FSPP. We call this problem an interval type-2 fuzzy shortest path problem (IT2FSPP). We describe the utility of IT2FSs as arc lengths and its application in different real world shortest path problems. Here, we propose an algorithm for IT2FSPP. In the proposed algorithm, we incorporate the uncertainty in Dijkstra’s algorithm for SPP using IT2FS as arc length. The path algebra corresponding to the proposed algorithm and the generalized algorithm based on the path algebra are also presented here. Numerical examples are used to illustrate the effectiveness of the proposed approach.http://www.mdpi.com/2227-7390/4/4/62SPPfuzzy graphFSPPT1FSIT2FS |
| spellingShingle | Arindam Dey Anita Pal Tandra Pal Interval Type 2 Fuzzy Set in Fuzzy Shortest Path Problem Mathematics SPP fuzzy graph FSPP T1FS IT2FS |
| title | Interval Type 2 Fuzzy Set in Fuzzy Shortest Path Problem |
| title_full | Interval Type 2 Fuzzy Set in Fuzzy Shortest Path Problem |
| title_fullStr | Interval Type 2 Fuzzy Set in Fuzzy Shortest Path Problem |
| title_full_unstemmed | Interval Type 2 Fuzzy Set in Fuzzy Shortest Path Problem |
| title_short | Interval Type 2 Fuzzy Set in Fuzzy Shortest Path Problem |
| title_sort | interval type 2 fuzzy set in fuzzy shortest path problem |
| topic | SPP fuzzy graph FSPP T1FS IT2FS |
| url | http://www.mdpi.com/2227-7390/4/4/62 |
| work_keys_str_mv | AT arindamdey intervaltype2fuzzysetinfuzzyshortestpathproblem AT anitapal intervaltype2fuzzysetinfuzzyshortestpathproblem AT tandrapal intervaltype2fuzzysetinfuzzyshortestpathproblem |