Pythagorean fuzzy set as an extension of fuzzy set has been presented to handle the uncertainty in real-world decision-making problems. In this work, we formulate a shortest path (SP) problem in an interval-valued Pythagorean fuzzy environment. Here, the costs related to arcs are taken in the form of interval-valued Pythagorean fuzzy numbers (IVPFNs). The main contributions of this paper are fourfold: (1) the interval-valued Pythagorean fuzzy optimality conditions in directed networks are described to design of solution algorithm. (2) To do this, an improved score function is used to compare the costs between different paths with their arc costs represented by IVPFNs. (3) Based on these optimality conditions and the improved score function, the traditional Dijkstra algorithm is extended to find the cost of interval-valued Pythagorean fuzzy SP (IVPFSP) and corresponding IVPFSP. (4) Finally, a small sized telecommunication network is provided to illustrate the potential application of the proposed method.
Hinweise
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations
Introduction
Shortest path (SP) problems lie at the heart of network flows. They arise frequently in practice since the aim of a wide variety of real-life problems is to send some goods between two specified nodes in a network as cheaply as possible. Therefore, SP problems with the aim of finding a path with the least cost (time or length) from the source node to the destination node can be used for formulating such real applications. Traditionally, it has been generally assumed that traversal costs of arcs are expressed in terms of crisp numbers. But, these values are generally imprecise or vague in nature since the costs fluctuate with traffic conditions and weather. For this, Zadeh [1] proposed the fuzzy set theory which is a very useful tool to cope with imprecise data in SP problems. Consequently, various attempts have been made by researchers for different types of SP problems in fuzzy environment.
Based on possibility theory, Okada [2] proposed an algorithm for solving fuzzy SP problem to determine the degree of possibility for each arc. Keshavarz and Khorram [3] simplified the fuzzy SP problem into a bi-level programming problem and proposed an efficient algorithm, based on the parametric SP problem for solving the resulting problem. Dou et al. [4] solved the fuzzy SP problem in multiple constraints network with vague multi-criteria decision making methods based on similarity measures. Deng et al. [5] extended the Dijkstra algorithm for solving fuzzy SP problems using the graded mean integration representation of fuzzy numbers. Moreover, some authors [6, 7] focused on computing a shortest path in the network having various types of fuzzy arc cost based on heuristic algorithms.
Anzeige
However, fuzzy set takes only a membership function and cannot express non-membership function. Here, the degree of non-membership is just the complement of the degree of membership. Then Atanassov [8] introduced intuitionistic FS (IFS) to incorporate the non-membership degree during the analysis. Here, the sum of membership degree and the non-membership degree is equal to or less than one. Under IFS environment, some researchers pay more attention to solving SP problem with intuitionistic fuzzy arc costs. Mukherjee [9] considered the SP problem in an intuitionistic fuzzy environment. Geetharamani and Jayagowri [10] proposed a new algorithm to deal with the IFSP problem using intuitionistic fuzzy shortest path length procedure and similarity measure. Biswas et al. [11] developed a method to search for an intuitionistic fuzzy shortest path between the source node and the destination node. Kumar et al. [12] proposed an algorithm to find the shortest path and shortest distance in a network where interval-valued fuzzy intuitionistic arc weights. Sujatha and Hyacinta [13] proposed two different approaches for solving the SP problem under intuitionistic environment. Motameni and Ebrahimnejad [14] worked on solving SP with an additional constraint under intuitionistic fuzzy environment.
However, there may be a situation where the sum of the membership and non-membership degrees is greater than one. Thus, Yager [15] introduced a generalization of IFS called Pythagorean fuzzy set (PFS) where the square sum of the membership and non-membership degrees sum is equal to or less than one. Zhang [16] extended the concept of PFSs to interval-valued PF (IVPF) sets where the values of membership and non-membership functions are expressed in terms of intervals rather than crisp numbers. After PFSs, IVPF set and different extensions of them have been used by some researchers to process fuzzy information in multi criteria decision making problems [17‐27]. However, to the best of our knowledge there is no study in the literature on solving SP problems in IVPF environment.
Thus, the object of this paper was to propose a method for solving SP problems under IVPF environment. To do this, we first present the mathematical formulation on SP problems where the traversal costs of arcs are represented in terms of interval-valued Pythagorean fuzzy numbers (IVPFNs). Then, we describe the optimality conditions in IVPF networks to design of solution algorithm. To do this, an improved score function is used to compare the costs between different paths with their arc costs represented by IVPFNs. Then, the traditional Dijkstra algorithm is extended to find the cost of interval-valued Pythagorean fuzzy SP (IVPFSP) and corresponding IVPFSP. The proposed algorithm is illustrated by a small sized telecommunication network under IVPF environment.
The rest of the paper is organized as follows: In Sect. 2, some basic concepts of interval-valued Pythagorean fuzzy sets are presented. In Sect. 3, the mathematical formulation of the SP problem under IVPF environment is given. The IVPF shortest path optimality conditions and the extended Dijkstra’s algorithm are presented Sect. 4. In Sect. 5, a numerical example is given to illustrate the proposed solution technique. Last, the paper is concluded in Sect. 6.
Anzeige
Preliminaries
In this section, we present some necessary background and notions of the interval-valued Pythagorean fuzzy numbers which are applied throughout this paper [8, 15, 17‐19].
Definition 1
Let \( X \) denotes the universe set. An intuitionistic fuzzy set (IFS) \( \tilde{A}^{I} \) in \( X \) is defined by a set of ordered triple \( \tilde{A}^{I} = \left\{ {\left\langle {x,\,\mu_{{\tilde{A}^{I} }} (x),\upsilon_{{\tilde{A}^{I} }} (x)} \right\rangle ;\,x \in X} \right\}, \) where the functions \( \mu_{{\tilde{A}^{I} }} (x):X \to \,[0,\,1] \) and \( \upsilon_{{\tilde{A}^{I} }} (x):X \to \,[0,\,1] \), respectively, represent the membership degree and non-membership degree of \( x \) in \( \tilde{A}^{I} \) such that for each element \( x \in X \), \( 0 \le \mu_{{\tilde{A}^{I} }} (x) + \upsilon_{{\tilde{A}^{I} }} (x) \le 1 \). For any IFS \( \tilde{A}^{I} \) and \( x \in X \), \( \pi_{{\tilde{A}^{I} }} (x) = 1 - \mu_{{\tilde{A}^{I} }} (x) - \upsilon_{{\tilde{A}^{I} }} (x) \) is said to be the degree of hesitation of \( x \) to \( \tilde{A}^{I} \).
Definition 2
A Pythagorean fuzzy set (PFS) \( \tilde{A}^{P} \) in the universe set \( X \) is defined by the set \( \tilde{A}^{P} = \left\{ {\left\langle {x,\,\mu_{{\tilde{A}^{P} }} (x),\upsilon_{{\tilde{A}^{P} }} (x)} \right\rangle ;\,x \in X} \right\}, \) where the membership function \( \mu_{{\tilde{A}^{P} }} (x):X \to \,[0,\,1] \) and non-membership function \( \upsilon_{{\tilde{A}^{P} }} (x):X \to \,[0,\,1] \), satisfy the condition \( \left[ {\mu_{{\tilde{A}^{P} }} (x)} \right]^{2} + \left[ {\upsilon_{{\tilde{A}^{P} }} (x)} \right]^{2} \le 1 \) for each element \( x \in X \). For any PFS \( \tilde{A}^{P} \) and \( x \in X \), \( \pi_{{_{{\tilde{A}^{P} }} }} (x) = \sqrt {1 - \left[ {\mu_{{\tilde{A}^{P} }} (x)} \right]^{2} - \left[ {\upsilon_{{\tilde{A}^{P} }} (x)} \right]^{2} } \) is said to be the degree of hesitation of \( x \) to \( \tilde{A}^{P} \).
For convenience, Zhang and Xu [16] called \( \left( {\mu_{{\tilde{A}^{P} }} (x),\upsilon_{{\tilde{A}^{P} }} (x)} \right) \) a Pythagorean fuzzy number (PFN) denoted by \( \tilde{A}^{P} = \left( {\mu_{{\tilde{A}^{P} }} ,\upsilon_{{\tilde{A}^{P} }} } \right) \).
For example, assume that the membership degree of an element to a fuzzy set is \( \frac{\sqrt 3 }{2} \) and the non-membership degree of this element is \( \frac{1}{2} \). This situation cannot be described by utilizing the IFS since \( \frac{\sqrt 3 }{2} + \frac{1}{2} > 1 \). However, \( \left( {\frac{\sqrt 3 }{2}} \right)^{2} + \left( {\frac{1}{2}} \right)^{2} \le 1 \); thus PFN is suitable to handle this situation.
Definition 3
The score function and the accuracy function of any PFN \( \tilde{A}^{P} = \left( {\mu_{{\tilde{A}^{P} }} ,\upsilon_{{\tilde{A}^{P} }} } \right) \) are defined as follows, respectively:
An interval-valued Pythagorean fuzzy set (IVPFS) \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \) in the universe set \( X \) is defined by the set \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} = \{ {\langle {x,\,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\mu }}_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x),\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\upsilon }}_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} \rangle ;\,x \in X} \} \) where \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\mu }}_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x) = [ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x),\,\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ] \subseteq \,[0,\,1] \) and \( \bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon } }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x) = [ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x),\,\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ] \subseteq \,[0,\,1] \) are inteval numbers satisfying the condition \( [ {\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ]^{2} + [ {\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ]^{2} \le 1 \) for each element \( x \in X \). For any IVPFS \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \) and \( x \in X \), \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\pi }}_{{_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} }} (x) = [ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\pi }_{{_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} }} (x),\bar{\pi }_{{_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} }} (x)} ] = [ {\sqrt {1 - [ {\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ]^{2} - [ {\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ]^{2} } ,\sqrt {1 - [ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ]^{2} - [ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ]^{2} } } ] \) is said to be the hesitation interval of \( x \) to \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \).
For an IVPFS \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \), the pair \( \langle {[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x),\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ],[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x),\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} (x)} ]} \rangle \) is called an interval-valued Pythagorean fuzzy number (IVPFN) denoted by \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} = \langle {[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ],[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ]} \rangle \).
Remark 1
[18] Two IVPFNs, \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{0}}}^{P} = \langle {[ {0,0} ],[ {1,1} ]} \rangle \) and \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{1}}}^{P} = \langle {[ {1,1} ],[ {0,0} ]} \rangle \) are the smallest and the largest IVPFNs, respectively.
Definition 5
The IVPFN \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} = \langle {[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ],[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ]} \rangle \) is siad to be non-negative if \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} \ge \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} \) and \( \bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} \ge \bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} \).
For any IVPFN \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} = \langle {[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ],[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ]} \rangle \), we have \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \oplus \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{0}}}^{P} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \).
Definition 7
[19] The score function and the accuracy function of any IVPFN \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} = \langle {[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ],[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ]} \rangle \), are defined as follows, respectively:
Let \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} = \langle {[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ],[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ]} \rangle \) be an IVPFN. Based on three concepts, hesitation interval index, favor degrees and against degrees relative to \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \), Garg [19] defined an improved score function of \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \) as follows:
According to Definition 5, we have \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} \ge \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} \) and \( \bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} \ge \bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} \). Therefore, \( (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} )^{2} - (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} )^{2} \ge 0 \) and \( (\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} )^{2} - (\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} )^{2} \ge 0 \). Now, based on Eq. (1), we conclude that \( M(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} ) \ge 0 \).
Remark 4
Garg [19] used the improved score function given in (1) to compare two IVPFNs \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} = \langle {[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ],[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} ,\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} }} } ]} \rangle \) and \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} = \langle {[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} }} ,\bar{\mu }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} }} } ],[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} }} ,\bar{\upsilon }_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} }} } ]} \rangle \) as follows:
If \( M(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} ) > M(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} ) \), then \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \succ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} \).
If \( M(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} ) = M(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} ) \), then \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{A}}}^{P} \sim \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{B}}}^{P} \).
The existing approaches for comparing two IVPFNs are based on the score and accuracy functions. Such approaches neglect the hesitation interval index and thus they are unable to give the exact position of IVPFNs. However, the ranking function given in (1) overcomes this shortcoming and provides exact positions of IVPFNs by sufficiently considering the indeterminacy information of an IVPFS.
Interval-valued Fuzzy Pythagorean Shortest Path problem
In this section, the mathematical formulation of the interval-valued Pythagorean fuzzy shortest path (IVPFSP) problem is presented.
We consider a directed network \( G = (V,E) \), with node set \( V = \left\{ {1,2, \ldots ,m} \right\} \) and arc set \( E = \left\{ {(i,j):\,i,j \in V,\,i \ne j} \right\} \). For two different nodes \( i,j \in E \), the ordered pair \( (i,j) \) denotes an arc of the network. Two nodes 1 and m are considered as the source and destination nodes of the network, respectively. It is supposed that there is only one directed arc \( (i,j) \) from node \( i \) to node \( j \). A path \( p_{ij} \) from node \( i \) to node \( j \) is a sequence of arcs \( p_{ij} = \left\{ {(i,i_{1} ),\,(i_{1} ,i_{2} ), \ldots ,(i_{k} ,j)} \right\} \) in which the initial node of each arc is same as the terminal node of preceding arc in the sequence. The cost of a directed path is defined as the sum of the arc costs the path. We assume the network contains a directed path from the source node to every other node in the network.
The non–negative weight \( c_{ij} \) is associated with each arc \( (i,j) \) representing the cost associated with the respective arc. The main purpose of the SP problem is to find a path with the least cost, from node 1 to node m. Conventional SP problems consider certain and precise values for the arc costs, which is not always the case in real-life problems. As time and cost fluctuate with traffic conditions, weather and payload, different extensions of fuzzy set can be utilized to represent imprecise and vague arc costs. In this work, interval-valued Pythagorean fuzzy numbers are used to represent the vague parameters of the SP problem under consideration. The resulting problem is, therefore, referred to as an interval-valued Pythagorean fuzzy SP (IVPFSP) problem.
An IVPFSP problem having non-negative IVPFNs for the arc costs is formulated as follows:
If arc \( (i,j) \) is in the path, then \( x_{ij} = 1 \); otherwise \( x_{ij} = 0 \).
Let \( T_{st} \) denote the set of all paths from node \( s \) to node \( t \). Define \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{C}}} ^{P} (p_{{uv}} ) = \sum\limits_{{(i,j) \in p_{{uv}} }} {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{C}}} _{{ij}}^{P} } \) as the interval-valued Pythagorean fuzzy cost of path \( p_{uv} \) from node \( u \) to node \( v \).
Extended Dijkstra Algorithm in IVPF environment
In this section, the traditional Dijkstra algorithm is extended for solving the IVPFSP problem (2).
Theorem 1
(IVPFSP optimality conditions) For every node\( j \in E \), let\( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \)denote the interval-valued Pythagorean fuzzy cost of some directed path from the source node 1 to node\( j \). Then, IVPFNs\( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \)represent IVPFSP costs if and only if they satisfy the following IVPFSP optimality conditions:
If \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \) is the IVPF cost of a shortest path from the source node 1 to node \( j, \) then it must satisfy the conditions (3). Suppose not, i.e.\( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \succ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{i}^{P} + \tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{ij}^{P} \) for some arc \( (i,j) \in E \). By assumption \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{i}^{P} \) is the IVPF cost of a directed path like \( p_{1i} \) from the source node 1 to node \( i \). This path plus the arc \( (i,j) \) constructs a new path from the source node 1 to node \( j \) with the IVPF cost \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{i}^{P} + \tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{ij}^{P} \). This contradicts the optimality of IVPFSP cost \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \).
We now show if the IVPF costs \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \) satisfy the conditions in (3), they represent IVPFSP costs. To do this, consider any IVPF costs \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \) satisfying (3). Let \( 1 = i_{1} - i_{2} - \cdots - i_{k} = j \) be any path \( p_{1j} \) from the source node 1 to node \( j \). The conditions (3) imply that
The last equality follows from the fact that \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{{i_{1} }}^{P} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{1}^{P} = \left\langle {[0,0],\,[1,1]} \right\rangle \). Adding the equalities, we find that
Thus \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \) is a lower bound on the IVPF cost of any path from the source node 1 to node \( j \). On the other hand, since \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \) is the IVPF cost of some path from the source node 1 to node \( j \), it also is an upper bound on the IVPFSP cost. Therefore, \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{j}^{P} \) is the IVPFSP cost. □
Now, we are at a position to describe the extended Dijkstra’s algorithm for finding IVPFSP from the source node 1 to destination node m in a directed network with IVPF costs. This algorithm automatically yields the IVPFSP from the source node 1 to all other nodes as well.
Algorithm 1: The extended Dijkstra’s algorithm under IVPF environment
Initialization step:
Set \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{1}^{P} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{0}}}^{P} = \left\langle {\left[ {0,0} \right],\left[ {1,1} \right]} \right\rangle \),\( S = \left\{ 1 \right\} \) and \( Pred\left\{ 1 \right\} = 0 \).
Main step:
Let \( \bar{S} = V - S \) and consider all arcs in the set \( (S,\,\,\bar{S}) = \left\{ {(i,j):\,i \in S,\,j \in \bar{S}} \right\} \). Let
Set \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{v}^{P} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{u}^{P} \oplus \tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{uv}^{P} \),\( Pred\left\{ v \right\} = u \), and \( S: = S \cup \left\{ v \right\} \). Repeat the main step exactly \( m - 1 \) times and then stop. The IVPF cost of the SP and the corresponding IVPFSP are at hand.
Remark 5
Note that \( Pred\left\{ i \right\} \) gives the predecessor node of node \( i \).
Theorem 2
The extended Dijkstra’s algorithm under IVPF environment yields the IVPFSP and its IVPS cost.
Proof
Assume, inductively, that each \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{i}^{P} \) for \( i \in S \) represents the IVPF cost of the IVPFSP from the source node 1 to node \( i \). This is true for \( i = 1 \) since \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{1}^{P} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{0}}}^{P} = \left\langle {\left[ {0,0} \right],\left[ {1,1} \right]} \right\rangle \). Consider the point at which a new node \( v \) is trying to be added to \( S \). Assume that
We shall show that the IVPFSP from the source node 1 to node \( v \) has the IVPF cost \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{v}^{P} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{u}^{P} \oplus \tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{uv}^{P} \) and can be constructed iteratively as the IVPFSP from the source node 1 to node \( u \) plus the arc \( (u,v) \).Consider any IVPF path \( p_{1v} \) from the source node 1 to node \( v \). It suffices to prove that \( M\left( {\sum\nolimits_{{(i,j) \in p_{1v} }} {\tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{ij}^{P} } } \right) = M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{C}}}^{P} (p_{1v} )} \right) \ge M(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{v}^{P} ) \). Since \( 1 \in S \) and \( v \in \bar{S} \), there exists an arc \( (i,j) \in p_{1v} \) where \( i \in S \) and \( j \in \bar{S} \). Hence, path \( p_{1v} \) can be decomposed into three parts \( p_{1i} \), \( (i,j) \) and \( p_{jv} \). Based on the induction hypothesis, the IVPF cost of \( p_{1i} \) is greater than or equal to \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{i}^{P} \), i.e. \( M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{C}}}^{P} (p_{1i} )} \right) \ge M(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{i}^{P} ) \). Since the IVPF costs of all arcs are assumed to be nonnegative, \( M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{C}}}^{P} (p_{jv} )} \right) \ge 0 \) (see Proposition 1). Thus, \( M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{C}}}^{P} (p_{1v} )} \right)\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \succ } M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{i}^{P} \oplus \tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{ij}^{P} } \right) \). Based on Eq. (3) and since \( M(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{v}^{P} ) = M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{u}^{P} \oplus \tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{uv}^{P} } \right) \), we conclude that \( M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{C}}}^{P} (p_{1v} )} \right)\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \succ } M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{v}^{P} } \right) \). This completes the induction argument and the validity of the algorithm is established. □
Numerical example
In this section, a small sized telecommunication network is provided to illustrate the potential application of the proposed method.
Consider a mobile service company which handles six geographical centers. A configuration of a telecommunication network is presented in Fig. 1. Assume that the cost between any two centers is an interval-valued Pythagorean fuzzy number (the arc costs are given in Table 1). The company wants to find an interval-valued Pythagorean fuzzy shortest path for an effective message flow amongst the centers.
The interval-valued Pythagorean fuzzy shortest path cost and the corresponding interval-valued Pythagorean fuzzy shortest path can be obtained using the proposed extended Dijkstra’s algorithm (Algorithm 1), as follows:
Initialization step:
Set \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{1}^{P} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{0}}}^{P} = \left\langle {\left[ {0,0} \right],\left[ {1,1} \right]} \right\rangle \), \( S = \left\{ 1 \right\} \) and \( Pred\left\{ 1 \right\} = 0 \).
Main step:
Iteration 1:
Let \( \bar{S} = V - S = \left\{ {2,3,4,5,6} \right\} \) and \( (S,\,\,\bar{S}) = \left\{ {(i,j):\,i \in S,\,j \in \bar{S}} \right\} = \left\{ {(1,2),\,(1,3)} \right\} \). Thus, we have
Since \( M\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{5}^{P} \oplus \tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{56}^{P} } \right) \,{=}\, \hbox{min} \left\{ {\,0.95,\,0.99} \right\} \,{=}\, 0.95 \), we set \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{6}^{P}\, {=}\, \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{5}^{P} \oplus \tilde{\bar{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} }}_{56}^{P} \,{=}\, \left\langle {\left[ {0.71,0.82} \right],\left[ {0.018,0.024} \right]} \right\rangle \), \( Pred\left\{ 6 \right\}\, =\, 5 \), and \( S = \left\{ {1,2,3,5,4,6} \right\} \).
This means that the IVPFSP cost from the source node 1 to node 6 is equal to \( \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\bar{\tilde{w}}}_{6}^{P} = \left\langle {\left[ {0.71,0.82} \right],\left[ {0.018,0.024} \right]} \right\rangle \). The corresponding IVPFSP can be found as follows:
Hence, the IVPF shortest path is \( p_{16} :1 \to 2 \to 5 \to 6 \).
Conclusions
Traditional SP problem requires precise arc weights which is not always the case in real-life applications. In this present work, a shortest path problem having an interval-valued Pythagorean fuzzy arc costs has been investigated. We first formulated the SP problem in the interval-valued Pythagorean fuzzy environment. We used an existing improved score function to compare the costs between different paths with their arc costs represented by IVPFNs. Based on this improved score function, we described the IVPF shortest path optimality conditions for the SP problem under consideration. The traditional Dijkstra’s algorithm has been generalized to determine the IVPF cost of the shortest path and corresponding IVPFSP. Finally, a small sized telecommunication network has been provided to illustrate the proposed algorithm under IVPF environment. In the future, we will extend the method to more complicated network problems involving negative and non-negative IVPF costs. The proposed approach for solving SP problems in IVPF environment can be extended for solving them in generalized Pythagorean fuzzy environment [28, 29]. Moreover, he development of the proposed method for deriving the IVPF shortest path between all pairs of nodes is left to the next study.
Acknowledgement
The authors would like to thank the anonymous reviewers and the editors for their insightful comments and suggestions.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations
