A novel approach for solving all-pairs shortest path problem in an interval-valued fuzzy network

Abstract

Researchers have studied several different types of directed shortest path (SP) problems under fuzzy environment. However, few researchers have focused on solving this problem in an interval-valued fuzzy network. Thus, in order to light these, we investigate a generalized kind of the SP problem under interval-valued fuzzy environment namely all pairs shortest path (APSP) problem. The main contributions of the present study are fivefold: (1) In the interval-valued fuzzy network under consideration, each arc weight is represented in terms of interval-valued fuzzy number. (2) We seek the shortest weights between every pair of nodes in a given interval-valued fuzzy network based on a dynamic approach. (3) In contrast to most existing approaches, which provide the shortest path between two predetermined nodes, the proposed approach provides the interval-valued fuzzy shortest path between every pair of nodes. (4) Similarly to the competing methods in the literature, the proposed approach not only gives the interval-valued fuzzy weights of all pairs shortest path but also provides the corresponding interval-valued fuzzy APSP. (5) The efficiency of the proposed approach is illustrated through two applications of APSP problems in wireless sensor networks and robot path planning problems.

Keywords

Shortest path problem dynamic programming interval-valued fuzzy numbers wireless sensor network

1 Introduction

The aim of the shortest path (SP) problem is to find the best way to traverse a network to get from one point to another with at least weight (time, cost or length). From this point of view, researchers have studied three forms of this problem classified as follows [1]:

Group 1: Finding shortest paths from one node to all other nodes with non-negative arc weights

Group 2: Finding shortest paths from one node to all other nodes with arbitrary arc weights

Group 3: Finding shortest paths from every node to every other node known as all-pairs SP problem.

The SP problem as a network structured optimization problem arises in numerous applications settings and in different forms. This problem arises in telecommunications in order to send a message between two locations with at least time. Moreover, the SP problem appears in transportations industries in order to send a vehicle between two points with at least cost. Also, the problem of finding urban traffic patterns solves a large number of SP problems as sub-problems [1]. Traffic-light networks, supply chain management, motion planning for car-like robots, investment planning, routing and models involving agents provide other applications of SP problem [2, 3]. In addition, SP problems appear frequently as sub-problems in more complex network optimization problems. In such real applications of SP problem, the cost and time values are generally imprecise or vague in nature as they fluctuated with traffic conditions and weather. But, SP problems are formulated with the assumptions that the arc weights are specified in terms of crisp numbers. Therefore, many researchers have focused on solving SP problems in uncertain environment.

Majority of inexact models in handling vague and imprecise data are related to stochastic programming, interval programming, and fuzzy programming models. But, stochastic and interval programming approaches are not very efficient to describe and tackle uncertainties associated with all real-world applications. In fact, in literature in stochastic optimization, parameters are assumed to be with known probability distributions while it is not always possible for a decision maker to determine the probability distribution in an inexact environment. Moreover, interval numbers are a special case of fuzzy numbers. Hence, in this work, we use fuzzy data in order to reflect uncertainty in the all-pairs SP problem belonging to Group 3 as the general case of SP in Group 1 and Group 2. The solution approaches for solving fuzzy SP (FSP) problems generally can be divided into two categories: directed approach and heuristic approach. An overview of the papers which have studied SP problems under fuzzy environment and investigated solution techniques can be summarized as follows.

According to the direct approach, some researchers have generalized present algorithms of this problem in a crisp environment to find the FSP. According to possibility theory, Okada and Soper [4] presented an algorithm to find SP in a network with fuzzy weights in which degree of possibility on an optimum path would be determined for each arc. Moazeni [5] proposed an algorithm based on the Dijkstra algorithm for finding all non-dominated paths in a network with fuzzy weights. Nayeem and Pal [6] presented an algorithm based on acceptance index that either finds the unique FSP or demonstrates a guide in which the best FSP would be chosen by the decision maker. Mahdavi et al. [7] used Floyd-Wrashal to find the FSP from one node to another. They used a distance function for comparing non-dominant fuzzy paths. Hernandes et al. [8] proposed a general algorithm for finding FSP that yields a unique fuzzy path or a set of fuzzy paths based on the decision makers opinion regarding the ranking index. Also, this algorithm works properly in a network with negative fuzzy parameters and is capable of distinguishing a negative circuit in the network. Ramazani et al. [9] used FSP algorithm in traffic forecasting. Deng et al. [10] generalized Dijkstra algorithm for solving this problem in a fuzzy environment which is more efficient than present algorithms due to introducing a new technique for summing up and comparing two fuzzy numbers. Zhang et al. [11] developed a biologically inspired for solving FSP problem without using any order relation between fuzzy numbers. Niroomand et al. [12] used the extension principle for solving the FSP problem. They have decomposed the FSP into two subproblems in order to find the lower and upper bounds of the membership function of the fuzzy cost of the shortest path.

Another approach that is used in solving the SP in a network with fuzzy arc weights is using heuristic algorithms. Hassanzadeh et al. [13] used a genetic algorithm for finding the shortest path in oriented graphs in which fuzzy weights of arcs have different membership functions. To do that, they presented an approximate method for summing up fuzzy numbers with different membership functions in order to find the length of paths. In fact, the fuzzy length of each path is approximately the sum of lengths of arcs in the path. Ebrahiminejad et al. [14] used Particle Swarm Optimization instead of genetic algorithm in order to reduce operation time and to increase convergence speed. In this problem, the position and velocity of each particle is an acceptable path of the graph. In that research, cross over operator is used in a particular way for updating velocity and position vectors of particles. That algorithm achieved to converge more quickly and find the optimum path in a shorter period of time compared to the genetic algorithm. In order to reduce the needed time for finding the shortest path in complicated graphs with fuzzy arcs, Ebrahimnejad et al. [15] used Artificial Bee Colony algorithm in which mutation operator is used for performing employed bees and onlooker bees search.

Despite a wide range of researches that have been done about the SP problem in a fuzzy environment, few have been done for finding an SP with interval-valued fuzzy data. In contrast to most existing approaches which use fuzzy numbers to represent vague data, we use an extension of fuzzy data, namely interval-valued fuzzy data, where the values of membership functions are expressed in terms of intervals rather than crisp numbers, to process fuzzy information in the SP problem under consideration [16, 17]. Dey et al. [18] proposed a procedure based on a genetic algorithm for solving the SP problem with interval-valued fuzzy weights. Enayyattabr et al. [19] developed traditional Dijkstra algorithm to find the cost of interval-valued Pythagorean fuzzy SP from a source node to a destination node. Here, we would propose an algorithm for solving all-pairs SP problem in a network with interval-valued fuzzy weights. To the best of my knowledge, there is no research in literature on solving interval-valued fuzzy all-pairs SP problem. That’s why in this research we would propose a dynamic approach for solving all-pairs SP problem in a network with interval-valued fuzzy weights. In contrast to most existing approaches [4 –15], in this work it would be assumed that fuzzy data of the problem have interval-valued trapezoidal fuzzy membership functions. In contrast to most existing approaches [4–6 , 13–15], the proposed approach utilizes a simple technique for summing up and comparing two interval-valued trapezoidal fuzzy numbers. In contrast to existing approaches [4–6 , 8–15], which provide the shortest path between two predetermined nodes, the proposed approach provides the interval-valued fuzzy shortest path between every arbitrary pair of nodes. Similarly to the competing methods in the literature [6, 10], the proposed approach not only gives the interval-valued fuzzy weights of all pairs shortest path but also provides the corresponding interval-valued fuzzy all-pairs SP. In contrast to heuristic approaches [13 –15] that provide an approximate solution to the fuzzy SP or Interval-valued FSP, the proposed approach provides an exact optimal solution.

The remainder of this paper is organized as follows. Some necessary concepts and backgrounds on interval-valued fuzzy set theory are reviewed in Section 3. In Section 3, we first formulate all pairs shortest path problem under interval-valued fuzzy network and then use a dynamic programming algorithm to compute shortest weighted paths for each pair of nodes of the interval-valued fuzzy network. In Section 4, two applications of the proposed algorithm in wireless sensor networks and robot path planning are presented. Lastly, the paper is concluded in Section 5.

2 Preliminaries

In this section, some basic definitions, the arithmetic operations and the comparison of the level (w^L, w^U)-interval-valued trapezoidal fuzzy numbers are reviewed [16 , 20–22].

Definition 1: A level h–trapezoidal fuzzy number $\tilde{A}$ , denoted by $\tilde{A} = (a_{1}, a_{2}, a_{3}, a_{4}; h)$ , 0 < h ≤ 1, is a fuzzy set on $ℝ$ with the membership function as follows: $μ_{\tilde{A}} (x) = {\begin{matrix} h \frac{x - a_{1}}{a_{2} - a_{1}}, a_{1} \leq x \leq a_{2}, \\ h, a_{2} \leq x \leq a_{3}, \\ h \frac{a_{4} - x}{a_{4} - a_{3}}, a_{3} \leq x \leq a_{4}, \\ 0, otherwise . \end{matrix}$ (1)

The family of all level h–trapezoidal fuzzy numbers is denoted by F_TN (h).

Definition 2: Let ${\tilde{A}}^{L} \in F_{TN} (h^{L})$ and ${\tilde{A}}^{U}$ ∈F_TN (h^U). A level (h^L, h^U)–interval–valued trapezoidal fuzzy number $\tilde{\tilde{A}}$ , denoted by $\tilde{\tilde{A}} = [{\tilde{A}}^{L}, {\tilde{A}}^{U}] = 〈 (a_{1}^{L}, a_{2}^{L}, a_{3}^{L}, a_{4}^{L}; h^{L}), (a_{1}^{U}, a_{2}^{U},$ $a_{3}^{U}, a_{4}^{U}; h^{U}) 〉$ is an interval–valued fuzzy set on $ℝ$ . The membership function of the lower trapezoidal fuzzy number ${\tilde{A}}^{L}$ is given as $μ_{{\tilde{A}}^{L}} (x) = {\begin{matrix} h^{L} \frac{x - a_{1}^{L}}{a_{2}^{L} - a_{1}^{L}}, a_{1}^{L} \leq x \leq a_{2}^{L}, \\ h^{L}, a_{2}^{L} \leq x \leq a_{3}^{L}, \\ h^{L} \frac{a_{4}^{L} - x}{a_{4}^{L} - a_{3}^{L}}, a_{3}^{L} \leq x \leq a_{4}^{L}, \\ 0, otherwise, \end{matrix}$ (2)

The membership function of the upper trapezoidal fuzzy number ${\tilde{A}}^{U}$ is given as $μ_{{\tilde{A}}^{U}} (x) = {\begin{matrix} h^{U} \frac{x - a_{1}^{U}}{a_{2}^{U} - a_{1}^{U}}, a_{1}^{U} \leq x \leq a_{2}^{U}, \\ h^{U}, a_{2}^{U} \leq x \leq a_{3}^{U}, \\ h^{U} \frac{a_{4}^{U} - x}{a_{4}^{U} - a_{3}^{U}}, a_{3}^{U} \leq x \leq a_{4}^{U}, \\ 0, otherwise, \end{matrix}$ (3) where $0 < h^{L} \leq h^{U} \leq 1, a_{1}^{U} \leq a_{1}^{L}$ and $a_{4}^{L} \leq a_{4}^{U}$ (Fig. 1).

Fig. 1

The interval–valued trapezoidal fuzzy number.

Definition 3: The extended addition on $\tilde{\tilde{A}} = [{\tilde{A}}^{L},$ ${\tilde{A}}^{U}] = 〈 (a_{1}^{L}, a_{2}^{L}, a_{3}^{L}, a_{4}^{L}; h^{L}), (a_{1}^{U}, a_{2}^{U}, a_{3}^{U}, a_{4}^{U}; h^{U}) 〉$ and $\tilde{\tilde{B}} = [{\tilde{B}}^{L}, {\tilde{B}}^{U}] = 〈 (b_{1}^{L}, b_{2}^{L}, b_{3}^{L}, b_{4}^{L}; h^{L}), (b_{1}^{U},$ $b_{2}^{U}, b_{3}^{U}, b_{4}^{U}; h^{U}) 〉$ is defined as follows: $\tilde{\tilde{A}} \oplus \tilde{\tilde{B}} = 〈 \begin{matrix} (a_{1}^{L} + b_{1}^{L}, a_{2}^{L} + b_{2}^{L}, a_{3}^{L} + b_{3}^{L}, a_{4}^{L} + b_{4}^{L}; h^{L}), \\ (a_{1}^{U} + b_{1}^{U}, a_{2}^{U} + b_{2}^{U}, a_{3}^{U} + b_{3}^{U}, a_{4}^{U} + b_{1}^{U}; h^{U}) \end{matrix} 〉$

Theorem 1: Let $\tilde{\tilde{A}} \in F_{IVTN} (h^{L}, h^{U})$ . The signed distance of $\tilde{\tilde{A}}$ from O₁ (y-axis) is given as follows: $\begin{matrix} SD (\tilde{A}, O_{1}) = \frac{1}{4} [a_{1} + a_{2} + a_{3} + a_{4}], {\tilde{A}}^{L} = {\tilde{A}}^{U} = \tilde{A} \\ SD (\tilde{\tilde{A}}, O_{1}) \\ = \frac{1}{8} [a_{1}^{L} + a_{2}^{L} + a_{3}^{L} + a_{4}^{L} + a_{1}^{U} + a_{2}^{U} + a_{3}^{U} + a_{4}^{U}], \\ 0 < h^{L} = h^{U} \leq 1 \\ SD (\tilde{\tilde{A}}, O_{1}) \\ = \frac{1}{8} [\begin{matrix} a_{1}^{L} + a_{2}^{L} + a_{3}^{L} + a_{4}^{L} + 4 a_{1}^{U} + 2 a_{2}^{U} + 2 a_{3}^{U} \\ + 4 a_{4}^{U} + 3 (a_{2}^{U} + a_{3}^{U} - a_{1}^{U} - a_{4}^{U}) \frac{h^{L}}{h^{U}} \end{matrix}], \\ 0 < h^{L} < h^{U} \leq 1 \end{matrix}$

The signed distance ranking given in Theorem 1 is used to order of level (w^L, w^U)–interval–valued trapezoidal fuzzy numbers.

Definition 4: Let $\tilde{\tilde{A}}$ and $\tilde{\tilde{B}}$ be two level (h^L, h^U)–interval–valued trapezoidal fuzzy numbers. We say $\tilde{\tilde{A}} \underline{≺} \tilde{\tilde{B}}$ if and only if $SD (\tilde{\tilde{A}}, O_{1}) \leq SD (\tilde{\tilde{B}}, O_{1})$ .

3 Interval-valued fuzzy all pairs shortest path problem

In this section, we first give a mathematical formulation of the IVFAPSP problem and then propose a dynamic approach for solving the problem using the signed distance ranking to order interval–valued fuzzy weights.

3.1 Interval–valued fuzzy mathematical formulation

Consider a connected and directed network G = (N, E) where N = {1, 2, . . . , n} is the set of nodes and E is the set of arcs (|E| = m). Each arc is denoted by an ordered pair (i, j), where i, j ∈ N. The weight of arc (i, j) is denoted by c_ij. A path p_st from node s to node t is a sequence of arcs p_st = {(s, s₁) , (s₁, s₂) , . . . , (s_v, t)} in which the initial node of each arc is same as the terminal node of preceding arc in the sequence. For simplicity, we show this path as p_st = {s, s₁, s₂, . . . , s_v, t}. We define the weight of a path as the sum of the weights on the arcs in the path. All pairs shortest path problem is to find shortest weights between every pair of nodes in a given directed network [23]. Now, if the weight of each arc is represented in terms of an interval–valued trapezoidal fuzzy number then the weight of each path between any two given nodes will be an interval–valued trapezoidal fuzzy number. In this case, the problem of finding the shortest path between every pair of nodes in a network with interval–valued trapezoidal fuzzy arc weights is called interval–valued fuzzy all pairs shortest path (IVFAPSP) problem.

Let interval–valued trapezoidal fuzzy weight associated with the arc (i, j), corresponding to the cost necessary to traverse (i, j) from node i, to node j is denoted by $\begin{matrix} {\tilde{\tilde{C}}}_{ij} = 〈 (c_{1, ij}^{L}, c_{2, ij}^{L}, c_{3, ij}^{L}, c_{4, ij}^{L}; w^{L}), \\ (c_{1, ij}^{U}, c_{2, ij}^{U}, c_{3, ij}^{U}, c_{4, ij}^{U}; w^{U}) 〉 \end{matrix}$

In this case, the interval–valued fuzzy all pairs shortest path problem is formulated as the following interval–valued fuzzy linear programming problem: $\begin{matrix} min \sum_{i = 1}^{m} \sum_{j = 1}^{n} {\tilde{\tilde{C}}}_{ij} x_{ij} = \sum_{(i, j) \in E} {\tilde{\tilde{C}}}_{ij} x_{ij} \\ s . t . \\ \sum_{{j : (i, j) \in E} x_{ij} - \sum_{{j : (j, i) \in E} x_{ji} = {\begin{matrix} 1, i = s, \\ 0, i \neq s, t \\ - 1, i = t \end{matrix} \\ x_{ij} \geq 0, for all (i, j) \in E \end{matrix}$ (4)

The IVFAPSP problem requires determining the IVFSP costs between every pair of nodes in the network. With this in mind, the generic all pairs label-correcting (GAPLC) algorithm is generalized in interval-valued fuzzy environment for solving this problem. The extended GAPLC algorithm is called interval-valued fuzzy GAPLC (IVFGAPLC) algorithm. It is assumed that the network does not contain a negative cycle.

3.2 IVFAPSP optimality conditions and IVFGAPLC algorithm

Let [i, j] denotes a pair of nodes i and j in the network G = (N, E). The IVFGAPLC algorithm relies on IVFAPSP optimality conditions. The IVFGAPLC algorithm maintains an interval-valued fuzzy cost label $\tilde{\tilde{d}} [i, j]$ for every pair of nodes representing the interval-valued fuzzy cost of some directed path from nodes i to j and being an upper bound on the IVFSP cost from nodes i to j. It uses the following optimality conditions.

Theorem 2 (IVFAPSP optimality conditions): For every pair of nodes [i, j] ∈ N × N, let $\tilde{\tilde{d}} [i, j]$ represents the interval-valued fuzzy cost of some directed path from node i to node j. These labels represent IVAPSP costs if and only if they satisfy the following IVFAPSP optimality conditions: $SD (\tilde{\tilde{d}} [i, j], o_{1}) \leq SD (\tilde{\tilde{d}} [i, k] + \tilde{\tilde{d}} [k, j], o_{1}), \forall i, j, k .$ (5)

Proof: A contradiction discussion is used to establish that the labels $\tilde{\tilde{d}} [i, j]$ must satisfy the conditions (5). Suppose $SD (\tilde{\tilde{d}} [i, j], o_{1}) > SD (\tilde{\tilde{d}} [i, k] + \tilde{\tilde{d}} [k, j], o_{1})$ for nodes i, j, k. The shortest path from node i to node k plus the shortest path from node k to node j is a path of the cost $\tilde{\tilde{d}} [i, k] + \tilde{\tilde{d}} [k, j]$ , say Q, from node i to node j. The path Q is decomposed into a directed path, say P, from node i to node j and some directed cycle, say C. Since the network does not contain a negative cycle, the interval-valued fuzzy cost of the path P is at most $\tilde{\tilde{d}} [i, k] + \tilde{\tilde{d}} [k, j] \underline{≺} \tilde{\tilde{d}} [i, j]$ and hence $SD (\tilde{\tilde{d}} [i, k] + \tilde{\tilde{d}} [k, j], o_{1}) < SD (\tilde{\tilde{d}} [i, j], o_{1})$ , contradicting the optimality of $\tilde{\tilde{d}} [i, j]$ .

We now demonstrate if the interval-valued fuzzy costs $\tilde{\tilde{d}} [i, j]$ satisfy the conditions in (5), they represent IVFSP costs. Let P = {1 = i₁ - i₂- ⋯ - i_k = j} be a directed path of the interval-valued fuzzy cost $\tilde{\tilde{d}} [i, j]$ . The conditions (5) imply that $\begin{matrix} \tilde{\tilde{d}} [i, j] = \tilde{\tilde{d}} [i_{1}, i_{k}] \underline{≺} \tilde{\tilde{d}} [i_{1}, i_{2}] + \tilde{\tilde{d}} [i_{2}, i_{k}] \underline{≺} {\tilde{\tilde{C}}}_{i_{1} i_{2}} \\ + \tilde{\tilde{d}} [i_{2}, i_{k}] \tilde{\tilde{d}} [i_{2}, i_{k}] \underline{≺} \tilde{\tilde{d}} [i_{2}, i_{3}] + \tilde{\tilde{d}} [i_{3}, i_{k}] \underline{≺} {\tilde{\tilde{C}}}_{i_{2} i_{3}} \\ + \tilde{\tilde{d}} [i_{3}, i_{k}] \\ ⋮ \\ \tilde{\tilde{d}} [i_{k - 1}, i_{k}] \underline{≺} {\tilde{\tilde{C}}}_{i_{k - 1} i_{k}}, \end{matrix}$

This means that $\tilde{\tilde{d}} [i, j] \underline{≺} {\tilde{\tilde{C}}}_{i_{1} i_{2}} + {\tilde{\tilde{C}}}_{i_{2} i_{3}} + \dots + {\tilde{\tilde{C}}}_{i_{k - 1} i_{k}} = \sum_{(i, j) \in P} {\tilde{\tilde{C}}}_{ij}$

This confirms that $\tilde{\tilde{d}} [i, j]$ is a lower bound on the interval-valued fuzzy cost of any path from node i to node j. By assumption, $\tilde{\tilde{d}} [i, j]$ is also an upper bound of the IVFSP cost from node i to node j. Consequently, $\tilde{\tilde{d}} [i, j]$ must be the IVFSP cost between these nodes.□

The IVFAPSP optimality conditions immediately yield the following IVFGAPLC algorithm. This algorithm starts with some interval-valued fuzzy cost labels $\tilde{\tilde{d}} [i, j]$ and successively these labels until they satisfy the IVFAPSP optimality conditions. A formal description of this algorithm is given as follows:

Algorithm 1: The extended GAPLC’s algorithm under interval-valued fuzzy environment

Initialization Step:

For i = 1 to n do

For j = 1 to n do

$\tilde{\tilde{d}} [i, j] = {\tilde{\tilde{C}}}_{ij}$ ;

Main Step:

For k = 1 to n do

For i = 1 to n do

For j = 1 to n do

If $SD (\tilde{\tilde{d}} [i, k] + \tilde{\tilde{d}} [k, j], o_{1}) < SD (\tilde{\tilde{d}} [i, j],$ o₁)

$\tilde{\tilde{d}} [i, j] = \tilde{\tilde{d}} [i, k] + \tilde{\tilde{d}} [k, j]$ ;

3.3 Extended Floyd-Warshall algorithm under interval–valued fuzzy network

The Floyd-Warshall algorithm in the interval–valued fuzzy environment is based on inductive arguments developed by an application of a dynamic programming technique. Hence, in this subsection, we use a dynamic programming algorithm to compute shortest weighted paths for each pair of nodes of the interval–valued fuzzy network. To do this, we first need to derive a recursive formula for the optimal interval–valued fuzzy values.

Definition 6: The nodes s₂, s₃, . . . , s_v-1 are called the intermediate nodes of the path p = {s₁, s₂, s₃, . . . , s_v-1, s_v}.

Let ${\tilde{\tilde{d}}}^{k} [i, j]$ represents the interval-valued fuzzy cost of an interval-valued fuzzy shortest path from node i to node j such that all intermediate nodes on the path are in set {1, 2, . . . , k}. In this case, ${\tilde{\tilde{d}}}^{n - 1} [i, j]$ represents the actual interval-valued fuzzy shortest path cost from node i to node j. The algorithm first computes ${\tilde{\tilde{d}}}^{1} [i, j]$ for all node pairs i and j. This process is repeated until it obtains ${\tilde{\tilde{d}}}^{n} [i, j]$ for all node pairs i and j.

For a shortest path from node i to node j such that any intermediate nodes on the path are chosen from the set {1, 2, . . . , k}, there are two possibilities:

Case 1: The path does not pass through node k, i.e. node k is not an intermediate node on the path. In this case, we have ${\tilde{\tilde{d}}}^{k} [i, j] = {\tilde{\tilde{d}}}^{k - 1} [i, j]$ .

Case 2: The path passes through node k, i.e. node k is an intermediate node on the path. In this case, such path consists of a path from node i to node k and a path from node k to node j. Both paths can only contain intermediate nodes in set {1, 2, . . . , k - 1} and consequently have interval-valued fuzzy costs ${\tilde{\tilde{d}}}^{k - 1} [i, k]$ and ${\tilde{\tilde{d}}}^{k - 1} [k, j]$ . Hence the path has the interval-valued fuzzy costs ${\tilde{\tilde{d}}}^{k - 1} [i, k] + {\tilde{\tilde{d}}}^{k - 1} [k, j]$ .

Combining the two cases we get the dynamic programming formulation as follows: $\begin{matrix} Recurrence relation : \\ SD ({\tilde{\tilde{d}}}^{k} [i, j], o_{1}) = min {SD ({\tilde{\tilde{d}}}^{k - 1} [i, j], o_{1}), \\ SD ({\tilde{\tilde{d}}}^{k - 1} [i, k] + {\tilde{\tilde{d}}}^{k - 1} [k, j], o_{1})} \\ Boundary condition : \\ SD ({\tilde{\tilde{d}}}^{0} [i, j], o_{1}) = {\begin{matrix} 0, i = j, \\ \infty, (i, j) \notin E, \\ SD ({\tilde{\tilde{C}}}_{ij}, o_{1}), (i, j) \in E . \end{matrix} \end{matrix}$ (6)

Hence, a formal description of the extended Floyd-Warshall algorithm in the interval–valued fuzzy environment for finding an interval-valued fuzzy shortest chain cost and an interval-valued fuzzy shortest chain is given as follows:

Algorithm 2: Extended Floyed-Warshall algorithm in interval-valued fuzzy environment

Initialization Step:

For i = 1 to n do

For j = 1 to n do

${\tilde{\tilde{d}}}^{0} [i, j] = {\tilde{\tilde{C}}}_{ij};$

Main Step:

For k = 1 to n do

For i = 1 to n do

For j = 1 to n do

$SD ({\tilde{\tilde{d}}}^{k - 1} [i, k] + {\tilde{\tilde{d}}}^{k - 1} [k, j], o_{1}) < SD ({\tilde{\tilde{d}}}^{k} [i, j], o_{1})$ then $\begin{matrix} {\tilde{\tilde{d}}}^{k} [i, j] = {\tilde{\tilde{d}}}^{k - 1} [i, k] + {\tilde{\tilde{d}}}^{k - 1} [k, j]; \\ SD ({\tilde{\tilde{d}}}^{k} [i, j], o_{1}) = SD ({\tilde{\tilde{d}}}^{k - 1} [i, k] + {\tilde{\tilde{d}}}^{k - 1} [k, j], o_{1}); \\ pred [i, j] = k; \end{matrix}$

Else,

${\tilde{\tilde{d}}}^{k} [i, j] = {\tilde{\tilde{d}}}^{k - 1} [i, j] and SD ({\tilde{\tilde{d}}}^{k} [i, j], o_{1}) = SD ({\tilde{\tilde{d}}}^{k - 1} [i, j], o_{1});$

The index pred [i, j] denotes the last node prior to node j in the tentative interval-valued shortest path from node i to node j. Using the predecessor indices, the final path, say P, from node u to node v is extracted as follows. We backtrack along the path P starting at node v. If pred [u, v] =0, the interval-valued fuzzy shortest path does not pass through any intermediate node and path P is just the arc the (u, v). If pred [u, v] = t, then node t is the node prior to node vin P. Similarly, l = pred [v, t] is the node prior to node tin P. This process is continued until we reach node u.

4 Applications

In this section, the efficiency of the proposed algorithm in solving interval-valued fuzzy shortest path problem is demonstrated in wireless sensor networks and robot path planning problems.

4.1 Application in wireless sensor networks

Wireless sensor network (WSN) is comprised of lots of sensor nodes that use irreplaceable batteries. These nodes are usually scattered in a geographical area haphazardly. Generally, wireless sensor networks are responsible for collecting data from its environment and passing it to a specific node called

“Sink”. The most restrictive constraint imposed by WSNs is energy sources which limits the lifetime of the networks [24, 25]. The lifetime of the network can be extended by energy aware protocols by saving as much energy as possible. In other words, because the sensor nodes are unreachable, one of very important challenges in a WSN is energy consumption efficiency that prolongs network’s lifetime. Hence, how to find the shortest path for sending data in a WSN that will cause energy consumption reduction is a problem worthy of study. As energy consumption cannot be measured preciously because of environmental conditions, interval-valued fuzzy data is used for modeling the SP problem in a WSN.

Figure 2 shows an example of a WSN with ten sensor nodes. The neighbor nodes are connected to each other through 23 arcs.

Fig. 2

A wireless sensor network.

Table 1 shows the needed energy for data transferring between neighbor nodes in terms of interval-valued trapezoidal fuzzy numbers.

Table 1

Interval-valued fuzzy energy of WSN

	Arc	Lower membership function	Upper membership function
1	(1,2)	[110,118,120,128;0.6]	[108,116,121,129;0.9]
2	(1,3)	[145,153,155,163;0.7]	[133,151,156,164;0.8]
3	(1,4)	[115,123,124,131;0.4]	[112,120,125,133;0.8]
4	(1,5)	[105,108,111,119;0.3]	[101,107,113,12;,0.6]
5	(2,3)	[108,111,114,122;0.5]	[104,110,116,124; 0.8]
6	(2,9)	[140,144,150,154;0.5]	[138,142,152,156;0.7]
7	(3,6)	[120,124,130,134;0.4]	[118,122,132,139;0.5]
8	(3,9)	[122,126,132,136;0.2]	[120,124,134,138;0.9]
9	(3,10)	[148,152,158,162;0.6]	[146,150,160,16;,0.7]
10	(4,5)	[115,123,124,130;0.5]	[112,120,125,133;0.6]
11	(4,7)	[107,111,114,122;0.7]	[103,110,116,124;0.8]
12	(5,3)	[100,103,106,111;0.2]	[95,101,108,115;0.4]
13	(5,6)	[120,124,130,134;0.3]	[119,122,132,13;0.6]
14	(5,7)	[115,123,124,131;0.4]	[110,121,125,132;0.5]
15	(6,8)	[114,123,124,129;0.1]	[113,120,125,134;0.7]
16	(6,9)	[124,133,135,141;0.6]	[121,130,136,144;0.7]
17	(6,10)	[126,132,134,143;0.3]	[124,131,136,147;0.4]
18	(7,3)	[119,124,131,134;0.4]	[116,121,132,136;0.5]
19	(7,6)	[105,108,111,119;0.2]	[104,107,113,120;0.8]
20	(7,8)	[125,131,133,138;0.7]	[122,129,135,14;0.9]
21	(8,9)	[127,134,135,140;0.2]	[123,130,138,141;0.3]
22	(8,10)	[101,103,108,114;0.3]	[97,102,110,117;0.7]
23	(9,10)	[115,122,124,128;0.6]	[111,119,125,129;0.7]

We apply the extended Floyd-Warshall algorithm in the interval–valued fuzzy environment given by Algorithm 2 to solve this interval-valued fuzzy WSN problem. The results for consuming minimum energy between every two nodes of the WSN in terms of interval-valued trapezoidal fuzzy numbers are shown in Table 2. The first component of each element shows the lower bound of interval-valued fuzzy membership function of the minimum energy and the second component of each element shows the upper lower bound of interval-valued fuzzy membership function of the minimum energy. The results for paths are shown in Table 3.

Table 2

Minimum energy for WSN

i/ j	1	2	3	4	5
1	0	(110,118,120,128;0.6) (108,116,121,129;0.9)	(145,153,155,163;0.7) (133,151,156,164;0.8)	(115,123,124,131;0.4) (112,120,125,133;0.8)	(105,108,111,119;0.3) (101,107,113,121;0.6)
2	–	0	(104,110,116,124;0.8) (108,111,114,122;0.5)	–	–
3	–	–	0	–	–
4	–	–	(207,221,233,248;0.4) (215,226,230,241;0.2)	0	(112,120,125,133;0.6) (115,123,124,130;0.5)
5	–	–	(95,101,108,115;0.4) (100,103,106,111;0.2)	–	0
6	–	–	–	–	–
7	–	–	(116,121,132,136;0.5) (119,124,131,134;0.4)	–	–
8	–	–	–	–	–
9	–	–	–	–	–
	6	7	8	9	10
1	(220,229,245,257;0.6) (225,232,241,253;0.3)	(211,228,238,253;0.5) (220,231,235,250;0.3)	(333,349,370,391;0.6) (339,355,365,382;0.1)	(246,258,273,285;0.7) (250,262,270,282;0.5)	(279,301,316,328;0.7) (293,305,313,325;0.6)
2	(222,232,248,263;0.5) (228,235,244,256;0.4)	–	(335,352,373,397;0.5) (342,358,368,385;0.1)	(138,142,152,156;0.7) (140,144,150,154;0.5)	(250,260,276,288;0.7) (256,263,272,284;0.5)
3	(118,122,132,139;0.5) (120,124,130,134;0.4)	–	(231,242,257,273;0.5) (234,247,254,263;0.1)	(120,124,134,138;0.9) (122,126,132,136;0.2)	(146,150,160,164;0.7) (148,152,158,162;0.6)
4	(207,217,229,244;0.8) (212,219,225,241,0.2)	(103,110,116,124;0.8) (107,111,114,122,0.7)	(225,239,251,264;0.8) (232,242,247,260;0.7)	(327,345,367,386;0.4) (337,352,362,377;0.2)	(322,341,361,381;0.7) (333,345,355,374;0.3)
5	(119,122,132,136;0.6) (120,124,130,134,0.3)	(110,121,125,132;0.5) (115,123,124,131;0.4)	(232,242,257,270;0.6) (234,247,254,263;0.1)	(215,225,242,253;0.4) (222,229,238,247;0.2)	(241,251,268,279;0.4) (248,255,264,273;0.2)
6	0	–	(113,120,125,134;0.7) (114,123,124,129;0.1)	(121,130,136,144;0.7) (124,133,135,141,0.6)	(124,131,136,147;0.4) (126,132,134,143;0.3)
7	(104,107,113,120;0.8) (105,108,111,119;0.2)	0	(122,129,135,140;0.9) (125,131,133,138;0.7)	(225,237,249,264;0.7) (229,241,246,260;0.2)	(219,231,245,257;0.7) (226,234,241,252;0.3)
8	–	–	0	(123,130,138,141;0.3) (127,134,135,140;0.2)	(97,102,110,117;0.7) (101,103,108,114;0.3)
9	–	–	–	0	(111,119,125,129;0) (115,122,124,128;0.6)

Table 3

Results of paths information for WSN

	1	2	3	4	5	6	7	8	9	10
1	–	2	3	4	5	5	5	5	2	3
2	–	–	3	–	–	3	–	3	9	3
3	–	–	–	–	–	6	–	6	9	10
4	–	–	5	–	5	7	7	7	5	7
5	–	–	3	–	–	6	7	6	3	3
6	–	–	–	–	–	–	–	8	9	10
7	–	–	3	–	–	6	–	8	6	8
8	–	–	–	–	–	–	–	–	9	10
9	–	–	–	–	–	–	–	–	–	10

Table 4

The amount of energy consumption

Arc	Upper membership function	Lower membership function
(1,2)	(18,22,32,36;0.7)	(20,24,30,34;0.6)
(1,6)	(23,27,37,41;0.8)	(25,29,35,39;0.6)
(1,7)	(20,24,34,38;0.6)	(22,26,32,36;0.4)
(2,3)	(13,17,27,31;0.9)	(15,19,25,29;0.7)
(2,6)	(28,30,42,46;0.8)	(30,34,40,44;0.7)
(2,7)	(38,42,52,56;0.8)	(40,44,50,54;0.5)
(2,8)	(18,22,32,36;0.7)	(20,24,30,34;0.6)
(3,4)	(30,34,44,48;0.8)	(32,36,42,46;0.5)
(3,7)	(26,30,40,44;0.8)	(28,32,38,42;0.6)
(3,8)	(34,38,48,52;0.9)	(36,40,46,50;0.7)
(3,9)	(32,36,46,50;0.8)	(34,38,44,48;0.6)
(4,5)	(48,52,62,66;0.9)	(50,54,60,64;0.6)
(4,8)	(50,54,64,68;0.9)	(52,56,62,66;0.7)
(4,9)	(46,50,60,68;0.8)	(48,52,58,62;0.5)
(4,10)	(53,57,67,71;0.9)	(55,59,65,69;0.7)
(5,9)	(58,62,72,76;0.9)	(60,64,70,74;0.8)
(5,10)	(63,67,77,81;0.8)	(65,69,70,79;0.6)
(6,7)	(70,74,84,88;0.9)	(72,76,82,86;0.7)
(6,11)	(72,76,86,90;0.9)	(74,78,84,88;0.8)
(6,12)	(66,70,80,84;0.8)	(68,72,78,82;0.6)
(7,8)	(78,82,92,96;0.9)	(80,84,90,94;0.8)
(7,11)	(70,74,80,88;0.8)	(78,82,88,92;0.7)
(7,12)	(70,74,80,88;0.7)	(72,76,82,86;0.6)
(7,13)	(80,84,94,98;0.7)	(82,86,92,96;0.5)
(8,9)	(12,16,26,30;0.8)	(14,18,24,28;0.6)
(8,12)	(14,18,28,32;0.9)	(16,20,26,30;0.7)
(8,13)	(38,42,52,56;0.8)	(40,44,50,54;0.6)
(8,14)	(42,46,58,60;0.9)	(44,48,54,58;0.7)
(9,10)	(16,20,30,34;0.8)	(18,22,28,32;0.6)
(9,13)	(28,30,42,46;0.8)	(30,34,40,44;0.7)
(9,14)	(32,36,46,50;0.8)	(34,38,44,48;0.6)
(9,15)	(48,52,62,66;0.9)	(50,54,60,64;0.6)
(10,14)	(12,16,26,30;0.8)	(14,18,24,28;0.6)
(10,15)	(70,74,84,88;0.7)	(72,76,82,86;0.5)
(11,12)	(72,76,86,90;0.8)	(74,78,84,88;0.6)
(11,16)	(66,70,80,84;0.8)	(68,72,78,82;0.6)
(11,17)	(78,82,92,96;0.8)	(80,84,90,94;0.6)
(12,13)	(80,84,94,98;0.8)	(82,86,92,96;0.7)
(12,16)	(82,86,96,100;0.9)	(84,88,94,98;0.6)
(12,17)	(58,62,72,76;0.9)	(60,64,70,74;0.8)
(12,18)	(70,74,84,88;0.9)	(72,76,82,86;0.7)
(13,14)	(38,42,52,56;0.8)	(40,44,50,54;0.5)
(13,17)	(64,68,78,82;0.9)	(66,70,76,80;0.6)
(13,18)	(62,66,76,80;0.9)	(64,68,74,78;0.7)
(13,19)	(60,64,74,78;0.9)	(62,66,72,76;0.8)
(14,15)	(72,76,86,90;0.8)	(74,78,84,88;0.6)
(14,18)	(10,14,24,28;0.9)	(12,16,22,26;0.6)
(14,19)	(72,76,86,90;0.8)	(74,78,84,88;0.6)
(14,20)	(63,67,77,81;0.8)	(65,69,70,79;0.6)
(15,19)	(46,50,60,68;0.8)	(48,52,58,62;0.5)
(15,20)	(50,54,64,68;0.9)	(52,56,62,66;0.7)
(16,17)	(64,68,78,82;0.9)	(66,70,76,80;0.6)
(17,18)	(46,50,60,68;0.8)	(48,52,58,62;0.5)
(18,19)	(12,16,26,30;0.8)	(14,18,24,28;0.6)
(19,20)	(16,20,30,34;0.9)	(18,22,28,32;0.7)

Using the results of Table 2, the interval-valued fuzzy shortest chain cost between any two nodes is determined. For example, the interval-valued fuzzy shortest path cost between nodes 1 and 10 is 〈 (115, 122, 124, 128 ; 0.6) , (111, 119, 125, 129 ; 0.7)〉. Using the predecessor indices and the results of path information given in Table 3, one can conclude that node 3 is an intermediate node on the path 1 to 10 and path 3 to 10 is just the arc the (3, 10). This means that the corresponding interval-valued fuzzy shortest chain is 1-3-10.

4.2 Application in robot path planning problems

One of the fundamental challenges of the robatic field is robot’s movement. That is why path planning is an eminent issue of robotics research and it is used to enhance autonomy of moving robots in complex environments. The objective of robot path planning problem is to find the shortest path without collide from source point to destination point. Because the amount of energy cannot be measured precisely due to environmental conditions, fuzzy data or its extensions such as interval-valued fuzzy data would be used for modeling the problem and the problem would be called fuzzy or interval-value fuzzy robot path planning problem.

Figure 3 shows a network with 20 nodes and 55 arcs for robot path planning problem. Table 4 gives the amount of energy consumption between nodes in terms of interval-valued trapezoidal fuzzy numbers.

Fig. 3

A robot path planning network.

The results for all-pairs shortest paths are shown in Table 5(a)–(d). Using the results of Table 5, the interval-valued fuzzy shortest chain in terms of energy consumption between any two nodes is determined. For example, the interval-valued fuzzy shortest path in terms of energy consumption between nodes 1 and 20 is $〈 (128, 152, 188, 212, 0.6), (116, 140, 202, 224, 0.7) 〉 .$

Table 5

The interval-valued fuzzy shortest chain in terms of energy consumption (a)

	1	2	3	4	5	6
1	0	(18,22,32,36;0.7) (20,24,30,34;0.6)	(31,39,59,67,0.7) (35,43,55,63,0.6)	(61,73,103,115,0.7) (67,79,97,109,0.5)	(109,125,165,181,0.7) (117,133,157,173,0.5)	(23,27,37,41,0.8) (25,29,35,39,0.6)
2	–	0	(13,17,27,31;0.9) (15,19,25,29;0.7)	(43,51,71,79,0.8) (47,55,67,75,0.5)	(91,103,133,145,0.8) (97,109,127,139,0.5)	(28,30,42,46,0.8) (30,34,40,44,0.7)
3	–	–	0	(30,34,44,48;0.8) (32,36,42,46;0.5)	(78,86,106,114,0.8) (82,90,102,110,0.5)	–
4	–	–	–	0	(48,52,62,66;0.9) (50,54,60,64;0.6)	–
5	–	–	–	–	0	–
6	–	–	–	–	–	0
7	–	–	–	–	–	–
8	–	–	–	–	–	–
9	–	–	–	–	–	–
10	–	–	–	–	–	–
11	–	–	–	–	–	–
12	–	–	–	–	–	–
13	–	–	–	–	–	–
14	–	–	–	–	–	–
15	–	–	–	–	–	–
16	–	–	–	–	–	–
17	–	–	–	–	–	–
18	–	–	–	–	–	–
19	–	–	–	–	–	–
20	–	–	–	–	–	–

Table 5b

Continued (b)

	7	8	9	10	11
1	(20,24,34,38;0.6) (22,26,32,36;0.4)	(36,44,64,72,0.7) (40,48,60,68,0.6)	(48,60,90,102,0.7) (54,66,84,96,0.6)	(64,80,120,136,0.7) (72,88,112,128,0.6)	(90,98,114,126,0.6) (100,108,120,128,0.4)
2	(38,42,52,56;0.8) (40,44,50,54;0.5)	(18,22,32,36;0.7) (20,24,30,34;0.6)	(30,38,58,66,0.7) (34,42,54,62,0.6)	(46,58,88,100,0.7) (52,64,82,94,0.6)	(100,106,128,136,0.8) (104,112,124,132,0.7)
3	(26,30,40,44;0.8) (28,32,38,42;0.6)	(34,38,48,52;0.9) (36,40,46,50;0.7)	(32,36,46,50;0.8) (34,38,44,48;0.6)	(48,56,76,84,0.8) (52,60,72,80,0.6)	(96,104,120,132,0.8) (106,114,126,134,0.6)
4	–	(50,54,64,68;0.9) (52,56,62,66;0.7)	(46,50,60,68;0.8) (48,52,58,62;0.5)	(53,57,67,71;0.9) (55,59,65,69;0.7)	–
5	–	–	(58,62,72,76;0.9) (60,64,70,74;0.8)	(63,67,77,81;0.8) (65,69,70,79;0.6)	–
6	(70,74,84,88;0.9) (72,76,82,86;0.7)	(148,156,176,184,0.9) (152,160,172,180,0.7)	(160,172,202,214,0.8) (166,178,196,208,0.6)	(176,192,232,248,0.8) (184,200,224,240,0.6)	(72,76,86,90;0.9) (74,78,84,88;0.8)
7	0	(78,82,92,96;0.9) (80,84,90,94;0.8)	(28,36,56,64,0.8) (32,40,52,60,0.6)	(106,118,148,160,0.8) (112,124,142,154,0.6)	(70,74,80,88;0.8) (78,82,88,92;0.7)
8	–	0	(12,16,26,30;0.8) (14,18,24,28;0.6)	(28,36,56,64,0.8) (32,40,52,60,0.6)	–
9	–	–	0	(16,20,30,34;0.8) (18,22,28,32;0.6)	–
10	–	–	–	0	–
11	–	–	–	–	0
12	–	–	–	–	–
13	–	–	–	–	–
14	–	–	–	–	–
15	–	–	–	–	–
16	–	–	–	–	–
17	–	–	–	–	–
18	–	–	–	–	–
19	–	–	–	–	–
20	–	–	–	–	–

Table 5c

Continued (c)

	12	13	14	15	16
1	(50,62,92,104,0.7) (56,68,86,98,0.6)	(74,86,116,128,0.7) (80,92,110,122,0.6)	(78,90,122,132,0.7) (84,96,114,126,0.6)	(96,112,152,168,0.7) (104,120,144,160,0.6)	(132,148,188,204,0.7) (140,156,180,196,0.6)
2	(32,40,60,68,0.7) (36,44,56,64,0.6)	(56,64,84,92,0.7) (60,68,80,88,0.6)	(60,68,90,96,0.7) (64,72,84,92,0.6)	(78,90,120,132,0.7) (84,96,114,126,0.6)	(114,126,156,168,0.7) (120,132,150,162,0.6)
3	(48,56,76,84,0.9) (52,60,72,80,0.7)	(60,66,88,96,0.8) (64,72,84,92,0.6)	(64,72,92,100,0.8) (68,76,88,96,0.6)	(80,88,108,116,0.8) (84,92,104,112,0.6)	(130,142,172,184,0.9) (136,148,166,178,0.6)
4	(64,72,92,100,0.9) (68,76,88,96,0.7)	(74,80,102,114,0.8) (78,86,98,106,0.5)	(65,73,93,101,0.8) (69,77,89,97,0.6)	(94,102,122,134,0.8) (98,106,118,126,0.5)	(146,158,188,200,0.9) (152,164,182,194,0.6)
5	–	(86,92,114,122,0.8) (90,98,110,118,0.7)	(75,83,103,111,0.8) (79,87,94,107,0.6)	(106,114,134,142,0.9) (110,118,130,138,0.6)	–
6	(66,70,80,84,0.8) (68,72,78,82,0.6)	(146,154,174,182,0.8) (150,158,170,178,0.6)	(184,196,226,238,0.8) (190,202,220,232,0.5)	(208,224,264,280,0.8) (216,232,256,272,0.6)	(138,146,166,174,0.8) (142,150,162,170,0.6)
7	(70,74,80,88,0.7) (72,76,82,86,0.6)	(80,84,94,98,0.7) (82,86,92,96,0.5)	(118,126,146,154,0.7) (122,130,142,150,0.5)	(138,150,180,192,0.8) (144,156,174,186,0.6)	(136,144,160,172,0.8) (146,154,166,174,0.6)
8	(14,18,28,32;0.9) (16,20,26,30;0.7)	(38,42,52,56;0.8) (40,44,50,54;0.6)	(42,46,58,60;0.9) (44,48,54,58;0.7)	(60,68,88,96,0.8) (64,72,84,92,0.6)	(96,104,124,132,0.9) (100,108,120,128,0.6)
9	–	(28,30,42,46;0.8) (30,34,40,44;0.7)	(32,36,46,50;0.8) (34,38,44,48;0.6)	(48,52,62,66;0.9) (50,54,60,64;0.6)	–
10	–	–	(12,16,26,30;0.8) (14,18,24,28;0.6)	(70,74,84,88;0.7) (72,76,82,86;0.5)	–
11	(72,76,86,90;0.8) (74,78,84,88;0.6)	(152,160,180,188,0.8) (156,164,176,184,0.6)	(190,202,232,244,0.8) (196,208,226,238,0.5)	(262,278,318,334,0.8) (270,286,310,326,0.5)	(66,70,80,84;0.8) (68,72,78,82;0.6)
12	0	(80,84,94,98;0.8) (82,86,92,96;0.7)	(118,126,146,154,0.8) (122,130,142,150,0.5)	(190,202,232,244,0.8) (196,208,226,238,0.5)	(82,86,96,100;0.9) (84,88,94,98;0.6)
13	–	0	(38,42,52,56;0.8) (40,44,50,54;0.5)	(110,118,138,146,0.8) (114,122,134,142,0.5)	–
14	–	–	0	(72,76,86,90;0.8) (74,78,84,88;0.6)	–
15	–	–	–	0
16	–	–	–	–	0
17	–	–	–	–	–
18	–	–	–	–	–
19	–	–	–	–	–
20	–	–	–	–	–

Table 5d

Continued (d)

	17	18	19	20
1	(108,124,164,180,0.7) (116,132,156,172,0.6)	(88,104,146,160,0.7) (96,112,136,152,0.6)	(100,120,172,190,0.7) (110,130,160,180,0.6)	(116,140,202,224,0.7) (128,152,188,212,0.6)
2	(90,102,132,144,0.7) (96,108,126,138,0.6)	(70,82,114,124,0.7) (76,88,106,118,0.6)	(82,98,140,154,0.7) (90,106,130,146,0.6)	(98,118,170,188,0.7) (108,128,158,178,0.6)
3	(106,118,148,160,0.9) (112,124,142,154,0.7)	(74,86,116,128,0.8) (80,92,110,122,0.6)	(86,102,142,158,0.8) (94,110,134,150,0.6)	(102,122,172,192,0.8) (112,132,162,182,0.6)
4	(122,134,164,176,0.9) (128,140,158,170,0.7)	(75,87,117,129,0.8) (81,93,111,123,0.6)	(87,103,143,159,0.8) (95,111,135,151,0.6)	(103,123,173,193,0.8) (113,133,163,183,0.6)
5	(150,160,192,204,0.8) (156,168,186,198,0.6)	(85,97,127,139,0.8) (91,103,116,133,0.6)	(97,113,153,169,0.8) (105,121,140,161,0.6)	(113,133,183,203,0.8) (123,143,168,193,0.6)
6	(124,132,152,160,0.8) (128,136,148,156,0.6)	(136,144,164,172,0.8) (140,148,160,168,0.6)	(148,160,190,202,0.8) (154,166,184,196,0.6)	(164,180,220,236,0.8) (172,188,212,228,0.8)
7	(128,136,152,164,0.7) (132,140,152,160,0.6)	(128,140,170,180,0.7) (134,146,164,176,0.5)	(140,148,168,176,0.7) (144,152,164,172,0.5)	(156,168,198,210,0.7) (162,174,192,204,0.5)
8	(72,80,100,108,0.9) (76,84,96,104,0.7)	(52,60,82,88,0.9) (56,64,76,84,0.6)	(64,76,108,118,0.8) (70,82,100,112,0.6)	(80,96,138,152,0.8) (88,104,128,144,0.6)
9	(92,98,120,128,0.8) (96,104,116,124,0.6)	(42,50,70,78,0.8) (46,54,66,74,0.6)	(54,66,96,108,0.8) (60,72,90,102,0.6)	(70,86,126,142,0.8) (78,94,118,134,0.6)
10	–	(22,30,50,58,0.8) (26,34,46,54,0.6)	(34,46,76,88,0.8) (40,52,70,82,0.6)	(50,66,106,122,0.8) (58,74,98,114,0.6)
11	(78,82,92,96;0.8) (80,84,90,94;0.6)	(124,132,152,164,0.8) (128,136,148,156,0.5)	(136,148,178,194,0.8) (142,154,172,184,0.5)	(152,168,208,228,0.8) (160,176,200,216,0.5)
12	(58,62,72,76;0.9) (60,64,70,74;0.8)	(70,74,84,88;0.9) (72,76,82,86;0.7)	(82,90,110,118,0.8) (86,94,106,114,0.6)	(98,110,140,152,0.8) (104,116,134,146,0.6)
13	(64,68,78,82;0.9) (66,70,76,80;0.6)	(62,66,76,80;0.9) (64,68,74,78;0.7)	(60,64,74,78;0.9) (62,66,72,76;0.8)	(76,84,104,112,0.9) (80,88,100,108,0.7)
14	–	(10,14,24,28;0.9) (12,16,22,26;0.6)	(72,76,86,90;0.8) (74,78,84,88;0.6)	(63,67,77,81;0.8) (65,69,70,79;0.6)
15	–	–	(46,50,60,68;0.8) (48,52,58,62;0.5)	(50,54,64,68;0.9) (52,56,62,66;0.7)
16	(64,68,78,82;0.9) (66,70,76,80;0.6)	(110,118,138,150,0.8) (114,122,134,142,0.5)	(122,134,164,180,0.8) (128,140,158,170,0.5)	(138,154,194,214,0.8) (146,162,186,202,0.5)
17	0	(46,50,60,68;0.8) (48,52,58,62;0.5)	(58,66,86,98,0.8) (62,70,82,90,0.5)	(74,86,116,132,0.8) (80,92,110,122,0.5)
18	–	0	(12,16,26,30;0.8) (14,18,24,28;0.6)	(28,36,56,64,0.8) (32,40,52,60,0.6)
19	–	–	0	(16,20,30,34;0.9) (18,22,28,32;0.7)
20	–	–	–	0

Using the predecessor indices and the results of path information given in Table 6, one can conclude that the corresponding interval-valued fuzzy shortest chain is 1-2-8-14-18-19-20.

Table 6

All-pairs path information

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	–	2	2	2	2	6	7	2	2	2	7	2	2	2	2	2	2	2	2	2
2	–	–	3	3	3	6	7	8	8	8	6	8	8	8	8	8	8	8	8	8
3	–	–	–	4	4	–	7	8	9	9	7	8	9	9	9	8	8	9	9	9
4	–	–	–	–	5	–	–	8	9	10	–	8	9	10	9	8	8	10	10	10
5	–	–	–	–	–	–	–	–	9	10	–	–	9	10	9	–	9	10	10	10
6	–	–	–	–	–	–	7	7	7	7	11	12	12	12	7	11	12	12	12	12
7	–	–	–	–	–	–	–	8	8	8	11	12	13	13	8	11	12	13	13	13
8	–	–	–	–	–	–	–	–	9	9	–	12	13	14	9	12	12	14	14	14
9	–	–	–	–	–	–	–	–	–	10	–	–	13	14	15	–	13	14	14	14
10	–	–	–	–	–	–	–	–	–	–	–	–	–	14	15	–	–	14	14	14
11	–	–	–	–	–	–	–	–	–	–	–	12	12	12	12	16	17	17	17	17
12	–	–	–	–	–	–	–	–	–	–	–	–	13	13	13	16	17	18	18	18
13	–	–	–	–	–	–	–	–	–	–	–	–	–	14	14	–	17	14	19	19
14	–	–	–	–	–	–	–	–	–	–	–	–	–	–	15	–	–	18	18	18
15	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	19	20
16	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	17	17	17	17
17	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	18	18	18
18	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	19	19
19	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	20
20	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–

5 Conclusions

Based on the fact that shortest path problem as an important network optimization problem arises in numerous applications such as telecommunications, transportations industries, supply chain management, investment planning, routing and so on, many researchers have studied several types of this problem in crisp and uncertain environments and proposed some interesting algorithms to find the path with lowest weight. Here we formulated interval-valued all pairs shortest path problem as a general case of fuzzy shortest path problem and proposed an algorithm to find the shortest weights between every pair of nodes. To do so, we proved the optimality conditions for the APSP problem in the interval-valued fuzzy network. The dynamic approach proposed in this works utilized the signed distance ranking to order interval-valued fuzzy arc weights and provided simultaneously the interval-valued fuzzy weights of all pairs shortest path and the corresponding interval-valued fuzzy APSP. We illustrated the efficiency of the proposed approach through two applications of APSP problems in wireless sensor networks and robot path planning problems. Because the proposed method is based on the classical SP algorithm, it is easy to learn and apply for obtaining interval-valued fuzzy shortest path between every two nodes of the IVFAPSP problems pertaining to real-world applications. In sum the advantages of the proposed method over the existing methods for solving SP problem in fuzzy environment are discussed as follows:

In contrast to the exiting approach [12] that the membership function is derived numerically and no mathematical form is provided, the proposed algorithm derive the mathematical form of the membership function so that the membership degree can be calculated directly.

In contrast to the existing methods [4 –15], the proposed method provides interval-valued fuzzy optimal shortest path weight that indicates possible outcomes with an interval degree of membership to the decision maker. This is especially useful for strategic decisions in cases more uncertainty exists.

In contrast to heuristic approach [12 –15] that gives a solution near to optimal solution with high computational effort, the proposed approach not only gives the exact optimal solution, but also needs less computational effort.

In contrast to existing approaches [4–6 , 8–15] which provide the shortest path between two predetermined nodes, the proposed approach provides the interval-valued fuzzy shortest path between every arbitrary pair of nodes.

Similarly to the competing methods in the literature [4, 10], the proposed approach not only gives the interval-valued fuzzy weights of all pairs shortest path but also provides the corresponding interval-valued fuzzy all-pairs SP. This technique decreases the computational effort significantly.

Although the existing approach [18] can be used for solving interval-valued fuzzy APSP problem, but it should be implemented $(\begin{matrix} n \\ 2 \end{matrix})$ times. This process increases the computational complexity of the algorithm significantly. However, the proposed algorithm avoids this increased effort by generalizing a dynamic procedure and implementing one time.

Many other areas remain to be researched. Some of these are discussed below.

In many network routing problems several conflicting objectives must be considered. The proposed approach can be extended for solving multi objective APSP problem with interval-valued fuzzy parameters.

The proposed algorithm cannot be applied in networks with negative interval-valued fuzzy parameters and it cannot detect whether there are negative circuits. The generalization of the proposed algorithm to overcome these shortcomings is an interesting topic for future research.

Using interval-valued fuzzy data for modeling other real world problem such indoor air quality [26] and biological wastewater treatment process [27]; is left to the next study.

Footnotes

Acknowledgment

The authors would like to thank the anonymous reviewers and the associate editor for their insightful comments and suggestions.

References

Ahuja

R.K.

, Magnanti

T.L.

and Orlin

J.B.

, Network Flows: Theory, Algorithms and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1993.

Chen

Y.L.

and Yang

H.H.

, Shortest paths in traffic-light networks, Transp Res Part B 34 (2000), 241–253.

Xidias

E.K.

, Azariadis

P.N.

and Aspragathos

N.A.

, Time optimum motion planning for a set of car-like robots, IFAC Proc 42(16) (2009), 542–547.

Okada

and Soper

, A shortest path problem on a network with fuzzy arc lengths, Fuzzy Sets and Systems 109(1) (2000), 129–140.

Moazeni

, Fuzzy shortest path problem with finite fuzzy quantities, Applied Mathematics and Computation 183 (2006), 160–169.

Nayeem

S.M.A.

and Pal

, Shortest path problem on a network with imprecise edge weight, Fuzzy Optimization and Decision Making 4 (2005), 293–312.

Mahdavi

, Nourifar

, Heidarzade

and Mahdavi-Amiri

, A dynamic programming approach for finding shortest chains in fuzzy network, Applied Soft Computing 9(2) (2009), 503–511.

Hernandes

, Lamata

M.T.

, Verdegay

J.L.

and Yamakami

, The shortest path problem on networks with fuzzy parameters, Fuzzy Sets and Systems 1589(14) (2007), 1561–1570.

Ramazani

, Shafahi

and Seyedabrishami

S.E.

, A shortest path problem in an urban transportation network based on driver perceived travel time, Scientia Iranica, Transaction A, Civil Engineering 17(4) (2010), 285–296.

10.

Deng

, Chen

, Zhang

and Mahadevan

, Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment, Applied Soft Computing 12 (2012), 1231–1237.

11.

Zhang

, Zhang

, Deng

and Mahadevan

, A biologically inspired solution for fuzzy shortest path problems, Applied Soft Computing 13 (2013), 2356–2363.

12.

Niroomand

, Mahmoodirad

, Heydari

, Kardani

and Hadi-Vencheh

, An extension principle based solution approach for shortest path problem with fuzzy arc lengths, Operational Research 17(2) (2017), 395–411.

13.

Hassanzadeh

, Mahdavi

, Mahdavi-Amiri

and Tajdin

, A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths, Mathematical and Computer Modelling 57(1–2) (2013), 84–99.

14.

Ebrahimnejad

, Karimnejad

and Alrezaamiri

, Particle swarm optimization algorithm for solving shortest path problems with mixed fuzzy arc weights, International Journal of Applied Decision Sciences 8(2) (2015), 203–222.

15.

Ebrahimnejad

, Tavana

and Alrezaamiri

, A novel artificial bee colony algorithm for shortest path problems with fuzzy arc weights, Measurement 93 (2016), 48–56.

16.

Ebrahimnejad

, A method for solving linear programming with interval-valued trapezoidal fuzzy variables, RAIRO-Operations Research 52(3) (2018), 955–979.

17.

Ebrahimnejad

, Verdegay

J.L.

and Garg

, Signed distance ranking based approach for solving bounded interval-valued fuzzy numbers linear programming problems, International Journal of Intelligent Systems 9(34) (2019), 2055–2076.

18.

Dey

, Pradhan

, Pal

and Pal

, A Genetic algorithm for solving fuzzy shortest path problems with interval type-2 fuzzy arc lengths, Malaysian Journal of Computer Science 31(4) (2018), 255–270.

19.

Enayattabar

, Ebrahimnejad

and Motameni

, Dijkstra algorithm for shortest path problem under interval-valued Pythagorean fuzzy environment, Complex & Intelligent Systems 5(2) (2019), 93–100.

20.

Chiang

, Fuzzy linear programming based on statistical confidence interval and interval-valued fuzzy set, European Journal of Operational Research 129 (2001), 65–86.

21.

Wei

S.H.

and Chen

S.M.

, Fuzzy risk analysis based on interval-valued fuzzy numbers, Expert Systems with Applications 36 (2009), 2285–2299.

22.

Farhadinia

, Sensitivity analysis in interval-valued trapezoidal fuzzy number linear programming problems, Applied Mathematical Modeling 38 (2014), 40–62.

23.

Steebrink

P.A.

, Optimization of Transport Network, John Wiley and Sons, 1973.

24.

Chen

, Jiang

, Li

, Gao

, Xu

and Ding

, Wireless sensor network nodes correlation method in coal mine tunnel based on Bayesian decision, Measurement 46 (2013), 2335–2340.

25.

Funck

and Gühmann

, Comparison of approaches to time-synchronous sampling in wireless sensor networks, Measurement 56 (2014), 203–214.

26.

Liu

, Yang

, Huang

, Wang

and Yoo

C.K.

, Modeling of subway indoor air quality using Gaussian process regression, Journal of Hazardous Materials 359(5) (2018), 266–273.

27.

Huang

, Ma

, Wan

and Chen

, A sensor-software based on a genetic algorithm-based neural fuzzy system for modeling and simulating a wastewater treatment process, Applied Soft Computing 27 (2015), 1–10.

	1	2	3	4	5	6	7	8	9	10
1	–	2	3	4	5	5	5	5	2	3
2	–	–	3	–	–	3	–	3	9	3
3	–	–	–	–	–	6	–	6	9	10
4	–	–	5	–	5	7	7	7	5	7
5	–	–	3	–	–	6	7	6	3	3
6	–	–	–	–	–	–	–	8	9	10
7	–	–	3	–	–	6	–	8	6	8
8	–	–	–	–	–	–	–	–	9	10
9	–	–	–	–	–	–	–	–	–	10

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	–	2	2	2	2	6	7	2	2	2	7	2	2	2	2	2	2	2	2	2
2	–	–	3	3	3	6	7	8	8	8	6	8	8	8	8	8	8	8	8	8
3	–	–	–	4	4	–	7	8	9	9	7	8	9	9	9	8	8	9	9	9
4	–	–	–	–	5	–	–	8	9	10	–	8	9	10	9	8	8	10	10	10
5	–	–	–	–	–	–	–	–	9	10	–	–	9	10	9	–	9	10	10	10
6	–	–	–	–	–	–	7	7	7	7	11	12	12	12	7	11	12	12	12	12
7	–	–	–	–	–	–	–	8	8	8	11	12	13	13	8	11	12	13	13	13
8	–	–	–	–	–	–	–	–	9	9	–	12	13	14	9	12	12	14	14	14
9	–	–	–	–	–	–	–	–	–	10	–	–	13	14	15	–	13	14	14	14
10	–	–	–	–	–	–	–	–	–	–	–	–	–	14	15	–	–	14	14	14
11	–	–	–	–	–	–	–	–	–	–	–	12	12	12	12	16	17	17	17	17
12	–	–	–	–	–	–	–	–	–	–	–	–	13	13	13	16	17	18	18	18
13	–	–	–	–	–	–	–	–	–	–	–	–	–	14	14	–	17	14	19	19
14	–	–	–	–	–	–	–	–	–	–	–	–	–	–	15	–	–	18	18	18
15	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	19	20
16	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	17	17	17	17
17	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	18	18	18
18	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	19	19
19	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	20
20	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–

	1	2	3	4	5	6	7	8	9	10
1	–	2	3	4	5	5	5	5	2	3
2	–	–	3	–	–	3	–	3	9	3
3	–	–	–	–	–	6	–	6	9	10
4	–	–	5	–	5	7	7	7	5	7
5	–	–	3	–	–	6	7	6	3	3
6	–	–	–	–	–	–	–	8	9	10
7	–	–	3	–	–	6	–	8	6	8
8	–	–	–	–	–	–	–	–	9	10
9	–	–	–	–	–	–	–	–	–	10

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	–	2	2	2	2	6	7	2	2	2	7	2	2	2	2	2	2	2	2	2
2	–	–	3	3	3	6	7	8	8	8	6	8	8	8	8	8	8	8	8	8
3	–	–	–	4	4	–	7	8	9	9	7	8	9	9	9	8	8	9	9	9
4	–	–	–	–	5	–	–	8	9	10	–	8	9	10	9	8	8	10	10	10
5	–	–	–	–	–	–	–	–	9	10	–	–	9	10	9	–	9	10	10	10
6	–	–	–	–	–	–	7	7	7	7	11	12	12	12	7	11	12	12	12	12
7	–	–	–	–	–	–	–	8	8	8	11	12	13	13	8	11	12	13	13	13
8	–	–	–	–	–	–	–	–	9	9	–	12	13	14	9	12	12	14	14	14
9	–	–	–	–	–	–	–	–	–	10	–	–	13	14	15	–	13	14	14	14
10	–	–	–	–	–	–	–	–	–	–	–	–	–	14	15	–	–	14	14	14
11	–	–	–	–	–	–	–	–	–	–	–	12	12	12	12	16	17	17	17	17
12	–	–	–	–	–	–	–	–	–	–	–	–	13	13	13	16	17	18	18	18
13	–	–	–	–	–	–	–	–	–	–	–	–	–	14	14	–	17	14	19	19
14	–	–	–	–	–	–	–	–	–	–	–	–	–	–	15	–	–	18	18	18
15	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	19	20
16	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	17	17	17	17
17	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	18	18	18
18	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	19	19
19	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	20
20	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–

	1	2	3	4	5	6	7	8	9	10
1	–	2	3	4	5	5	5	5	2	3
2	–	–	3	–	–	3	–	3	9	3
3	–	–	–	–	–	6	–	6	9	10
4	–	–	5	–	5	7	7	7	5	7
5	–	–	3	–	–	6	7	6	3	3
6	–	–	–	–	–	–	–	8	9	10
7	–	–	3	–	–	6	–	8	6	8
8	–	–	–	–	–	–	–	–	9	10
9	–	–	–	–	–	–	–	–	–	10

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	–	2	2	2	2	6	7	2	2	2	7	2	2	2	2	2	2	2	2	2
2	–	–	3	3	3	6	7	8	8	8	6	8	8	8	8	8	8	8	8	8
3	–	–	–	4	4	–	7	8	9	9	7	8	9	9	9	8	8	9	9	9
4	–	–	–	–	5	–	–	8	9	10	–	8	9	10	9	8	8	10	10	10
5	–	–	–	–	–	–	–	–	9	10	–	–	9	10	9	–	9	10	10	10
6	–	–	–	–	–	–	7	7	7	7	11	12	12	12	7	11	12	12	12	12
7	–	–	–	–	–	–	–	8	8	8	11	12	13	13	8	11	12	13	13	13
8	–	–	–	–	–	–	–	–	9	9	–	12	13	14	9	12	12	14	14	14
9	–	–	–	–	–	–	–	–	–	10	–	–	13	14	15	–	13	14	14	14
10	–	–	–	–	–	–	–	–	–	–	–	–	–	14	15	–	–	14	14	14
11	–	–	–	–	–	–	–	–	–	–	–	12	12	12	12	16	17	17	17	17
12	–	–	–	–	–	–	–	–	–	–	–	–	13	13	13	16	17	18	18	18
13	–	–	–	–	–	–	–	–	–	–	–	–	–	14	14	–	17	14	19	19
14	–	–	–	–	–	–	–	–	–	–	–	–	–	–	15	–	–	18	18	18
15	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	19	20
16	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	17	17	17	17
17	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	18	18	18
18	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	19	19
19	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	20
20	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–