Solving the shortest path problem in an imprecise and random environment

Abstract

This paper considers a shortest path problem in an imprecise and random environment. The edges in the network represent the approximate time required to cover the distance from one vertex to another vertex while the traffic conditions change randomly for each edge. The approximate time has been defined by using trapezoidal fuzzy number whereas the traffic conditions has been defined in linguistic term. Such type of network problem can be called as Fuzzy Stochastic Shortest Path Problem (FSSPP) in imprecise and random environment. In order to solve the model, a method has been proposed based on the Dijkstra’s algorithm and some numerous example have been solved to present its effectiveness.

1 Introduction

In a network, the problem of obtaining the shortest path from a designated source vertex to the other vertices is a basic problem that arises in various real-life applications. It produces necessary learning in shipping, routing, and communications purposes. So the shortest path problem has been examined widely in the areas of transportation, operation research and logistics and so on. The solution of deterministic variant of this problem is simply achievable. Several effective algorithms have been provided by Bellman, Dijkstra’s [1, 9, 10] to solve the standard shortest problem.

In this work, we consider a network where the arc lengths denote the time required to cover the arc length while the traffic condition on the particular arc is changing randomly. As the time required to cover the distance with the random change in traffic condition can not be defined precisely. A trapezoidal fuzzy number has been taken to define the time required to cover each arc length in the network. On the other hand, the traffic condition for each arc has been defined linguistically as low, medium and high. To solve the proposed problem, a matrix storing traffic condition for each arc has been defined. In the literature, the shortest path problem in the imprecise environment has been studied by many of the researchers. They used the fuzzy number to define the imprecise arc length and proposed various methods to solve fuzzy shortest path problem using ranking methods. Some of the references [2, 17, 20, 23, 25] can be found related to the fuzzy shortest path problem. Whereas the shortest path problem in a random environment has been termed as stochastic shortest path problem. In this case, the probability theory has been used to tackle the randomness. The following references [11, 22, 27, 32] can be found in the literature which solves the stochastic shortest path problem. However, it may not be possible always that the impreciseness and randomness [31] occur separately in the shortest path problem. To the best of author’s knowledge shortest path problem in the mixed environment has not been found in the literature. In real life situation, the problem of ambulance finding the shortest path to the hospital while covering the arcs with random traffic condition in a network is a problem of mixed environment where the impreciseness and randomness occur simultaneously. Inspired by[28,29,30] such type of problem can be formulated as fuzzy stochastic shortest path problem. To solve the fuzzy stochastic shortest path problem, Dijkstras’ algorithm has been proposed for which the system inputs are taken as the time taken to cover any arc in a given traffic condition which is in the form of trapezoidal fuzzy number and the network connecting the source node and destination node. Whereas the user inputs are: the source node, the destination node, the traffic conditions on every arc of the given network. The output of the system is the shortest path from the source vertex to destination vertex.

This paper is organized as follows. In section 2, some basic definitions regarding fuzzy sets and fuzzy numbers are reviewed. The method to compare two trapezoidal fuzzy numbers has also been discussed in this section and definitions of fuzzy random variables and their expectation with an example has also been illustrated. In section 3, we have introduced a mathematical model of shortest path problem in an imprecise and random environment. In section 4, a descriptive algorithm of the proposed method is given. This section also comprises of the flow chart of the given algorithm. In section 5, we have presented two different example where the adjacency matrices remains same as well as the source node and the destination node remains same but a slight change in the traffic conditions of the network results in the change of the shortest path. The last section comprises of the conclusion.

2 Preliminaries

2.1 Fuzzy Set [17]

Definition 1

If X is a universe of discourse and x is a particular element of X, then a fuzzy set A defined on X can be written as collection of ordered pairs,

$$\begin{aligned} A=\lbrace (x,\mu _{{\tilde{A}}}(x)),x\in X\rbrace \end{aligned}$$

(1)

where

$$\begin{aligned} \mu _{{\tilde{A}}}(x):X\rightarrow [0,1]. \end{aligned}$$

2.2 Fuzzy Number [35]

Definition 2

A fuzzy set ${\tilde{A}}$ on $\mathsf {R}$ is said to be a fuzzy number [35], if the following three properties are satisfied:

• 1. Fuzzy set ${\tilde{A}}$ must be normal, i.e. $\exists \, x$ such that $sup \, \mu _{{\tilde{A}}}(x)=1$, where sup stands for supremum.

• 2. The support of fuzzy set, i.e. set of all the elements with non zero degree of membership, must be bounded.

• 3. $\alpha$ level set i.e. set of all the elements with membership degree greater than $\alpha$, must be a closed interval for $\alpha$ $\in$ [0,1].

2.3 Trapezoidal Fuzzy Number

Definition 3

A fuzzy number is said to be a trapezoidal fuzzy number[16] if the graph of its membership function is trapezium. The membership function of a trapezoidal fuzzy number is defined by Eq. (2) and the membership function of such a trapezoidal fuzzy number is represented by Figure 1.

$$\begin{aligned} \mu _{{\tilde{A}}}(x) = {\left\{ \begin{array}{ll} 0 &{} if \, x < a \\ \dfrac{x-a}{b-a} &{} if \, a \le x \le b \\ 1 &{} if \, b\le x \le c\\ \dfrac{d-x}{d-c} &{} if \, c \le x \le d \\ 0 &{} if \, x > d \end{array}\right. } \end{aligned}$$

(2)

This trapezoidal fuzzy number is denoted as (a, b, c, d)

Figure 1

A Trapezoidal Fuzzy Number.

2.4 Operations on Trapezoidal Fuzzy numbers[16]

Let ${\tilde{A}}$=(a,b,c,d) and ${\tilde{B}}$=(p,q,r,s) are two trapezoidal fuzzy numbers, then

• Addition:

  $$\begin{aligned} \quad (a,b,c,d)\oplus (p,q,r,s)=(a+p,b+q,c+r,d+s). \end{aligned}$$

  (3)

• Subtraction:

  $$\begin{aligned} \quad (a,b,c,d)\ominus (p,q,r,s)=(a-s,b-r,c-q,d-p). \end{aligned}$$

  (4)

• Scalar Multiplication:

  $$\begin{aligned} \quad k (p,q,r,s) = (kp,kq,kr,ks). \end{aligned}$$

  (5)

2.5 Defuzzy Value of A Trapezoidal Fuzzy numbers [3]

Definition 4

The defuzzy value of a trapezoidal fuzzy number[4] ${\tilde{A}}$ = (a,b,c,d) is given by Eq. (6)

$$\begin{aligned} Val({\tilde{A}})= & {} \int _{0}^{1} \alpha (A_{d}(\alpha )+A_{a}(\alpha ))d\alpha \\= & {} \int _{0}^{1} \alpha ((d-(d-c)\alpha ))+(a+\alpha (b-a))) d\alpha \\= & {} \int _{0}^{1} \alpha (d+a)+\alpha ^2(b-a-d+c) d\alpha \\= & {} \frac{d+a}{2}+\frac{b-a-d-c}{3}\\= & {} \frac{a}{6}+\frac{b}{3}+\frac{c}{3}+\frac{d}{6} \end{aligned}$$

Thus,

$$\begin{aligned} Val({\tilde{A}})=\frac{a}{6}+\frac{b}{3}+\frac{c}{3}+\frac{d}{6} \end{aligned}$$

(6)

2.6 Comparison of Trapezoidal Fuzzy numbers

Definition 5

Based on the defuzzy values of two trapezoidal fuzzy numbers, ${\tilde{A}}$ and ${\tilde{B}}$, they can be compared in the following manner:

$$\begin{aligned} \begin{array}{rcl} \text{ If } Val({\tilde{A}})>Val({\tilde{B}}) &{} \text{ then } &{} {\tilde{A}}>{\tilde{B}}\\ \text{ If } Val({\tilde{A}})<Val({\tilde{B}}) &{} \text{ then } &{} {\tilde{A}}<{\tilde{B}}\\ \text{ If } Val({\tilde{A}})=Val({\tilde{B}}) &{} \text{ then } &{} {\tilde{A}}={\tilde{B}} \end{array} \end{aligned}$$

(7)

2.7 Fuzzy Linguistic variables [35]

Definition 6

There are linguistic variables whose states are fuzzy numbers. Fuzzy variables representing linguistic concepts such as hot, cold, pleasant etc. with respect to temperature are known as fuzzy linguistic variables.

The Figure 2 represents the fuzzy linguistic variable cool, pleasant and hot with respect to the environment temperature.

Figure 2

Fuzzy linguistic variable.

2.8 Fuzzy Random Variable [18]

Definition 7

A fuzzy random variable[26] is a random variable whose value is not real, but a fuzzy number.

Example 1

Consider a survey where individuals are questioned about the customer services of a particular company. The responses of customers are classified into three categories:

• 1. Disappointing

• 2. Satisfactory

• 3. Amazing

In the above case, randomness occurs because the opinion of customers are not known. Once the opinion of customer is available, there is still some uncertainty about the accurate meaning of the response. This lack of preciseness denotes the fuzziness of random variable customer services.

2.9 Expectation of a Fuzzy Random Variable

Definition 8

Let $\tilde{\mathbf{X }}$ be a fuzzy random variable. Then the expectation of $\tilde{\mathbf{X }}$ is defined as fuzzy number $E\tilde{\mathbf{X }}$, which can be formally defined as

$$\begin{aligned} E[\tilde{X}]=\sum _{\tilde{x} \in \tilde{X}}\tilde{x}\odot p(\tilde{x}) \end{aligned}$$

(8)

where $p(\tilde{x})$ denotes the probability of fuzzy random variable $\tilde{X}$ taking the value $\tilde{x}$

3 Impreciseness and Randomness in shortest path problems

In the case of shortest path problem[9, 15], the motive is to find a shortest path from the source node to the destination node in such a way that the sum of weights of constituent edges is minimized. In classical shortest path problem, the weight of the edge represents the distance of that edge or time taken to cover that edge, which is always given in crisp form. But in day to day life, situations are not always defined in the crisp form. Time taken to cover a path is not always crisp. One may take more time to cover a path depending upon various conditions. In the case of impreciseness and randomness in shortest path problem, if we take the weight of the edge to be the approximate time taken to cover that edge, this approximate time will never be a real number (crisp). It will always be something imprecise given in the form of fuzzy number. In real life situations, to go from one node to another node we follow different paths and those different paths may have different traffic conditions. These different traffic conditions are random in nature. In the mathematical modeling of the shortest path problem in an imprecise and random environment, our objective is to find the path with minimum weight from the source vertex to destination vertex with the assumption that formation of such a path is possible.

A function $\tilde{f_{ij}}$ denotes the fuzzy random variable for each edge $e_{ij}$ joining the vertex i and j. This sample space for this fuzzy random variable include the different types of traffic conditions and this fuzzy random variable maps each traffic condition with the time taken (here, it is expressed in form of trapezoidal fuzzy number) to cover a certain edge under those traffic conditions. This introduces randomness as well as impreciseness in the model.

$$\begin{aligned} \tilde{f}_{ij}(D)\rightarrow \tilde{F}_{K}(R) \end{aligned}$$

The domain is the set of traffic conditions. D=$\lbrace$High, Low, Usual$\rbrace .$ The range set is the set of fuzzy number which informs about approximate time taken to cover that edge in a given traffic condition.

3.1 Mathematical model

Objective: Minimize: $\sum$ E[$\tilde{f}_{ij}].a_{ij}$

where, $a_{ij}$ is an indicator function.

$$\begin{aligned} a_{ij}= {\left\{ \begin{array}{ll} 1 &{} \text{ if } \text{ edge } \text{ ij } \text{ is } \text{ included } \text{ in } \text{ path } \\ 0 &{} \text{ otherwise } \end{array}\right. } \end{aligned}$$

subject to:

$$\begin{aligned} \sum _{j}^{} a_{ij}-\sum _{j}^{} a_{ji}= {\left\{ \begin{array}{ll} 1 &{} \text{ if } \text{ i } \text{ is } \text{ source } \text{ node }\\ -1 &{} \text{ if } \text{ j } \text{ is } \text{ destination } \text{ node }\\ 0 &{} \text{ otherwise } \end{array}\right. } \end{aligned}$$

The function $\tilde{f}_{ij}$ satisfies a specific distribution or the distribution can be already provided. The major intuition behind the indicator function, $a_{ij}$ is to find out whether the edge (i, j) is a part of shortest path or not. We wish to select the set of edges with minimal weight, subject to the constraint that this set forms a path from the source node to destination node.

4 Methodology

Suppose we are given a network that consists of a path from the source node to the destination node. Three adjacency matrices storing the information about the time taken to cover every edge in three different traffic conditions, namely, high, low and usual are also given and corresponding to every edge, a probability mass function stores the probability values of different traffic conditions of that edge, e.g. let $p_{ij}=(a,b,c)$ be the probability mass function storing the information that a, b and c corresponds to the probabilities of having low, medium and high traffic densities respectively on edge ij. A matrix ${\tilde{D}}$ storing the pmf values for different edges is also provided and the objective is to find a shortest path from source node to a destination node. Since there is no unique explanation about finding a shortest path under uncertainty. One possible way to do this could be to find a path with minimum expected time i.e. the objective is to find a path with minimum expected time.

4.1 Procedure

Step 1: With the help of given three adjacency matrices and probability mass function corresponding to every edge, assign a fuzzy number to every edge of the network, where the fuzzy number represents the expected time taken to cover that edge.

Step 2: Now, we have obtained a network whose weights are fuzzy and the aim is to find the shortest path for this network. Now, these fuzzy weights can be defuzzified by replacing the fuzzy number with the defuzzy value of the given fuzzy number as stated in Eq. (6).

Step 3: Djikstra method [6] can now be used to solve the fuzzy stochastic shortest path model.

Step 4: Assign the source vertex a permanent label of 0 and all other vertices are assigned a temporary label of $\infty$.

Step 5: Starting from the source vertex, search for all the adjacent vertices and the vertex with minimum weight is given a permanent label.

Step 6: Explore the vertices which are adjacent to the vertices with permanent label and repeat Step 5 until we reach the destination vertex.

System Inputs System Inputs are the inputs which are given to the system to solve a particular problem. Here, the system inputs are:

• 1. The time taken to cover every arc in any given traffic conditions which is in the form of a trapezoidal fuzzy number.

• 2. The network connecting the source node and destination node.

User Inputs The User Inputs are the inputs which are given by the user and on the basis of these inputs only, the system gives the best suitable path. In our example, the user inputs are:

• 1. The source node.

• 2. The destination node.

• 3. A probability mass function indicating the probabilities of various traffic conditions on every edge.

Output The output of the system is a shortest path from source node to destination node i.e. a path such that the sum of the constituent edges is minimum. The method also gives us vague information about the time taken to reach destination node from the source node.

4.2 Flowchart

The flowchart of the model is represented by Figure 3.

Figure 3

Flowchart of the proposed method.

4.3 Algorithm

In the given algorithm, the symbols along with their descriptions has been provided in Table 1.

Table 1 Symbols used in the algorithm with their descriptions.

5 Numerical example

5.1 Example 1

User Input The inputs given by user will be in the form of a source node and a destination node and in this case user will also be entering about the traffic conditions on the different arcs. For current example, the user inputs are:

• The source node i.e. node A.

• The destination node i.e. node C.

• The matrix representing the probability mass function of every arc of the network.

Let ${\tilde{A}}$, ${\tilde{B}}$ and ${\tilde{C}}$ are three fuzzy matrices storing the fuzzy time taken to cover each vertices when the traffic conditions are low, usual and high respectively and a matrix storing the probability mass function values of different traffic condition values on different edges of the network is also given. Our aim is to find the shortest path from the source vertex, i.e. A, to the destination vertex, i.e. C.

$$\begin{aligned} {\tilde{A}}=\begin{bmatrix} {[}0, 0, 0, 0]&{}[2, 4, 6, 8]&{}[4, 7, 9, 13]&{} [5, 7, 9, 11]\\ {[}2, 4, 6, 8] &{} [0, 0, 0, 0] &{} [1, 3, 5, 7] &{} [0, 0, 0, 0]\\ {[}4, 7, 9, 13] &{} [1, 3, 5, 7] &{} [0, 0, 0, 0] &{} [1, 4, 6, 9]\\ {[}5, 7, 9, 11] &{} [0, 0, 0, 0] &{} [1, 4, 6, 9] &{} [0, 0, 0, 0]\\ \end{bmatrix}\\ {\tilde{B}}=\begin{bmatrix} {[}0, 0, 0, 0]&{}[4, 6, 9, 11]&{}[7, 10, 14, 17] &{} [12, 14, 16, 18]\\ {[}4, 6, 9, 11] &{} [0, 0, 0, 0] &{} [2, 4, 6, 8] &{} [0, 0, 0, 0]\\ {[}7, 10, 14, 17] &{} [2, 4, 6, 8] &{} [0, 0, 0, 0] &{} [8, 10, 14, 16]\\ {[}12, 14, 16, 18] &{} [0, 0, 0, 0] &{} [8, 10, 14, 16] &{} [0, 0, 0, 0]\\ \end{bmatrix}\\ {\tilde{C}}=\begin{bmatrix} {[}0, 0, 0, 0]&{}[8, 11, 14, 17]&{}[12, 14, 16, 18]&{} [15, 18, 22, 25]\\ {[}8, 11, 14, 17] &{} [0, 0, 0, 0] &{} [3, 5, 7, 9] &{} [0, 0, 0, 0]\\ {[}12, 14, 16, 18] &{} [3, 5, 7, 9] &{} [0, 0, 0, 0] &{} [12, 17, 19, 23]\\ {[}15, 18, 22, 25] &{} [0, 0, 0, 0] &{} [12, 17, 19, 23] &{} [0, 0, 0, 0]\\ \end{bmatrix} \end{aligned}$$

If the matrix storing pmf values, i.e. probability values of different traffic conditions on the network is given by ${\tilde{D}}_{1}$, then the shortest path is A-C, i.e. via the diagonal.

$$\begin{aligned} {\tilde{D}}_{1}=\begin{bmatrix} (0,0,0) &{} (0.2, 0.3, 0.5) &{} (0.6, 0.3, 0.1) &{} (0.4, 0.5, 0.1)\\ (0.2, 0.3, 0.5) &{} (0, 0, 0) &{} (0.1, 0.6, 0.3) &{} (0, 0, 0) \\ (0.6, 0.3, 0.1) &{} (0.1, 0.6, 0.3) &{} (0, 0, 0) &{} (0.3, 0.4, 0.3)\\ (0.4, 0.5, 0.1) &{} (0, 0, 0) &{} (0.3, 0.4, 0.3) &{} (0, 0, 0)\\ \end{bmatrix} \end{aligned}$$

A detailed solution is given below:

Step 1: First we construct a network, where each edge has a fuzzy weight representing the expected fuzzy time taken to cover that edge. The Figure 4 corresponds to this information.

Figure 4

A network with fuzzy edge weights.

Step 2: Now we construct a network where the edge represents the defuzzy value of the trapezoidal fuzzy numbers given in the above network. The Figure 5 corresponds to this information.

Figure 5

A network with crisp edge weights.

Step 3: Now we have obtained a weighted graph, same as we get in the classical shortest path problem. So, Dijkstra’s method can be easily applied to solve this shortest path problem.

Step 4: We assign a permanent label of 0 to the source vertex and every other edge is assigned a temporary label of $\infty$.

Step 5: Out of all the adjacent vertices, the vertex with minimum weight is B. We make the temporary label of B permanent and now we look at only those vertices which are adjacent to either A or B.

Step 6: Now, the vertex C adjacent to A via the edge A-C gives the minimum weight and hence this vertex gets a permanent label.

Since we have reached the destination vertex. So, the process stops here. Hence, the shortest path from source vertex to destination vertex is the path A-C, i.e. via the diagonal and the weight of that path is calculated as 10.

5.2 Example 2

Let ${\tilde{A}}$, ${\tilde{B}}$ and ${\tilde{C}}$ are three matrices storing the time taken to cover each vertices when the traffic conditions are low, usual and high respectively and a matrix storing the probability mass function values of different traffic conditions on different edges of the network is also given. The aim is to find the shortest path from the source vertex i.e. A to the destination vertex i.e. D.

$$\begin{aligned} {\tilde{A}}=\left[ \begin{array}{cccccccc} {[}0,0,0,0] &{} [2,4,8,10] &{}[0,0,0,0]&{} [0,0,0,0] &{} [0,0,0,0] &{}[1,3,7,9]&{} [0,0,0,0]&{} [0,0,0,0]\\ {[}2,4,8,10]&{}[0,0,0,0] &{}[3,5,7,9] &{}[0,0,0,0] &{} [0,0,0,0]&{} [0,0,0,0]&{} [4,6,8,10] &{} [0,0,0,0]\\ {[}0,0,0,0] &{}[3,5,7,9] &{} [0,0,0,0] &{}[2,6,10,14]&{}[0,0,0,0] &{}[0,0,0,0] &{} [0,0,0,0] &{} [0,1,5,6]\\ {[}0,0,0,0] &{}[0,0,0,0] &{} [2,6,10,14]&{} [0,0,0,0]&{} [3,4,7,11]&{} [0,0,0,0]&{} [0,0,0,0]&{} [0,0,0,0]\\ {[}0,0,0,0] &{}[0,0,0,0] &{} [0,0,0,0] &{} [3,4,7,11] &{}[0,0,0,0] &{}[1,5,8,9]&{} [0,0,0,0] &{}[1,3,5,7]\\ {[}1,3,7,9] &{}[0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0]&{} [1,5,8,9]&{} [0,0,0,0] &{}[2,4,8,10]&{} [0,0,0,0]\\ {[}0,0,0,0] &{}[4,6,8,10] &{} [0,0,0,0] &{} [0,0,0,0]&{} [0,0,0,0] &{}[2,4,8,10] &{}[0,0,0,0] &{}[3,4,7,11]\\ {[}0,0,0,0] &{}[0,0,0,0] &{}[0,1,5,6] &{} [0,0,0,0]&{} [1,3,5,7] &{}[0,0,0,0] &{}[3,4,7,11]&{} [0,0,0,0]\\ \end{array}\right] \\ {\tilde{B}}=\left[ \begin{array}{cccccccc} {[}0,0,0,0] &{} [8,10,12,14] &{}[0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0]&{} [1,3,5,7] &{}[0,0,0,0] &{} [0,0,0,0]\\ {[}8,10,12,14]&{} [0,0,0,0] &{} [4,9,16,18] &{} [0,0,0,0] &{} [0,0,0,0]&{} [0,0,0,0] &{} [6,8,10,12] &{}[0,0,0,0]\\ {[}0,0,0,0] &{} [4,9,16,18] &{} [0,0,0,0] &{} [6,8,11,16] &{}[0,0,0,0] &{}[0,0,0,0] &{}[0,0,0,0] &{} [4,7,9,12]\\ {[}0,0,0,0] &{} [0,0,0,0] &{} [6,8,11,16] &{} [0,0,0,0] &{} [2,6,10,14]&{} [0,0,0,0]&{} [0,0,0,0] &{}[0,0,0,0]\\ {[}0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0] &{} [2,6,10,14]&{}[0,0,0,0] &{} [5,7,9,11]&{} [0,0,0,0] &{}[0,1,5,6]\\ {[}1,3,5,7] &{} [0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0] &{} [5,7,9,11]&{} [0,0,0,0]&{} [2,6,10,14]&{} [0,0,0,0]\\ {[}0,0,0,0] &{} [6,8,10,12] &{} [0,0,0,0] &{} [0,0,0,0]&{} [0,0,0,0] &{} [2,6,10,14] &{}[0,0,0,0]&{} [4,7,9,12]\\ {[}0,0,0,0] &{} [0,0,0,0] &{} [4,7,9,12] &{} [0,0,0,0] &{} [0,1,5,6] &{} [0,0,0,0] &{} [4,7,9,12]&{} [0,0,0,0]\\ \end{array}\right] \\ {\tilde{C}}=\left[ \begin{array}{cccccccc} {[}0,0,0,0] &{} [10,12,16,18] &{}[0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0] &{} [4,6,8,10]&{} [0,0,0,0] &{} [0,0,0,0]\\ {[}10,12,16,18]&{} [0,0,0,0] &{} [13,15,17,19]&{} [0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0] &{} [12,14,18,20]&{} [0,0,0,0]\\ {[}0,0,0,0] &{} [13,15,17,19]&{} [0,0,0,0] &{} [8,10,12,14]&{}[0,0,0,0] &{} [0,0,0,0]&{} [0,0,0,0] &{} [4,7,9,12]\\ {[}0,0,0,0] &{} [0,0,0,0] &{} [8,10,12,14] &{} [0,0,0,0] &{} [6,8,10,12]&{}[0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0]\\ {[}0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0] &{} [6,8,10,12]&{} [0,0,0,0] &{}[5,8,10,13]&{}[0,0,0,0] &{} [1,3,7,9]\\ {[}4,6,8,10] &{} [0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0] &{} [5,8,10,13]&{}[0,0,0,0] &{}[8,11,13,16] &{} [0,0,0,0]\\ {[}0,0,0,0] &{} [12,14,18,20] &{} [0,0,0,0] &{} [0,0,0,0] &{} [0,0,0,0] &{} [8,11,13,16]&{}[0,0,0,0] &{} [5,8,11,16]\\ {[}0,0,0,0] &{} [0,0,0,0] &{} [4,7,9,12] &{} [0,0,0,0] &{} [1,3,7,9] &{}[0,0,0,0] &{} [6,8,11,16] &{} [0,0,0,0]\\ \end{array}\right] \end{aligned}$$

If the matrix storing pmf values, i.e. probability values of different traffic conditions on the network is given by $D_{2}$, then the shortest path is via the lower outer boundary i.e. via the path A-F-E-D.

$$\begin{aligned} {\tilde{D}}=\left[ \begin{array}{cccccccc} (0,0,0) &{} (0.2,0.7,0.1) &{}(0,0,0) &{} (0,0,0) &{} (0,0,0) &{} (0.4,0.5,0.1) &{} (0,0,0) &{} (0,0,0)\\ (0.2,0.7,0.1)&{} (0,0,0) &{} (0.3,0.4,0.3) &{} (0,0,0) &{} (0,0,0) &{} (0,0,0) &{} (0.5,0.3,0.2) &{} (0,0,0)\\ (0,0,0) &{} (0.3,0.4,0.3) &{} (0,0,0) &{} (0.2,0.6,0.2) &{} (0,0,0) &{} (0,0,0) &{} (0,0,0) &{} (0.2,0.3,0.5)\\ (0,0,0) &{} (0,0,0) &{} (0.2,0.6,0.2) &{} (0,0,0) &{} (0.7,0.2,0.1)&{}(0,0,0) &{} (0,0,0) &{} (0,0,0)\\ (0,0,0) &{} (0,0,0) &{} (0,0,0) &{} (0.7,0.2,0.1) &{} (0,0,0) &{} (0.3,0.5,0.2) &{} (0,0,0) &{} (0.2,0.5,0.3)\\ (0.4,0.5,0.1) &{} (0,0,0) &{} (0,0,0) &{} (0,0,0) &{} (0.3,0.5,0.2) &{} (0,0,0) &{} (0.6,0.2,0.2) &{} (0,0,0)\\ (0,0,0) &{} (0.5,0.3,0.2) &{} (0,0,0) &{} (0,0,0) &{} (0,0,0) &{} (0.6,0.2,0.2) &{} (0,0,0) &{} (0.4,0.3,0.3)\\ (0,0,0) &{} (0,0,0) &{} (0.2,0.3,0.5) &{} (0,0,0) &{} (0.2,0.5,0.3) &{} (0,0,0) &{} (0.4,0.3,0.3) &{} (0,0,0)\\ \end{array}\right] \end{aligned}$$

Step 1: First we construct the network where each edge has a fuzzy weight representing the expected fuzzy time taken to cover that edge. Figure 6 corresponds to this information.

Figure 6

A network of 8 vertices with fuzzy edges weights corresponding to pmf values given by ${\tilde{D}}_{2}$.

Step 2: Now we obtain a network where the edge represents the value of the trapezoidal fuzzy numbers given in the above network. Figure 7 corresponds to this information.

Figure 7

A network of 8 vertices with crisp edges weights.

Step 3: Now we have obtained a weighted graph same as we get in the classical shortest path problem. Now we can apply Dijkstra method to solve this shortest path problem.

Step 4: We assign a permanent label of 0 to the source vertex and every other edge is assigned a temporary label of $\infty$.

Step 5: Out of all the adjacent vertex, the vertex having minimum weight is F. We make the temporary label of F permanent and now we look at only those vertices which are adjacent to A or F.

Step 6: The vertex B adjacent to A via the edge A-B gives the minimum weight and hence this vertex gets a permanent label. Now, we look for the vertices which are adjacent to A, B or F. The vertex G(or E) adjacent to F via the edge F-G gives the minimum weight and hence G gets the permanent label. Now, we search for the vertices adjacent to B, G or F. This time the vertex E via the edge F-E gives the minimum weight, same as that of G and hence gets the permanent label. On further solving, vertex H gets permanent label via edge E-H and after that finally our destination vertex D gets permanent label via the edge E-D.

Hence, the shortest path from source vertex to destination vertex is via the lower outer boundary i.e. from A-F-E-D and weight of this path is calculated as 19.06 units.

5.3 Discussion and analysis

The presented method to find the path of Shortest path Problem in imprecise and random environment is based on Dijkstra’s algorithm, which is a greedy approach, i.e. in this method, the traveler keeps on choosing the path with lowest expected weight without having a visionary approach. The method always guarantees an optimal solution, when all the edge weights are positive which is the case considered in this work. In other classical methods used for solving fuzzy shortest path problem, issues like random nature of the network because of various conditions on the network have not been discussed. In this work, randomness has also been dealt by fuzzy random variable. Expectation of fuzzy random variable has been used to convert the given imprecise and random network into the corresponding fuzzy network, where edge weights are given by fuzzy numbers. There are several methods in the literature for solving fuzzy shortest path problem which uses the linear programming approach like an extension principle based approach by Niroomand et. al [24] and [23]. The time complexity of the methods based on linear programming approach is exponential whereas the time complexity of the proposed method is polynomial. The method presented earlier either have time complexity or optimality issues whereas the proposed method overcome both the issues with consideration of impreciseness and randomness of SPP, which has not been discussed earlier. Comparison of the method with other works can only be done once a fuzzy network has been obtained from the corresponding imprecise and random network. Table 2 comprises the comparison of the method presented in this paper with other works. The comparison has been done on the network presented in Example 2.

Table 2 Comparison of various methods.

6 Conclusion

In this work, the mathematical model of a fuzzy stochastic shortest path problem and the algorithm to solve this problem has been introduced. In real life situations, to go from one node to another node, we follow different paths and those different paths have different traffic conditions. These different traffic conditions are random in the shortest path model. In the mathematical modeling of the shortest path problem in an imprecise and random environment, our objective is to find the path with minimum weight from the source vertex to destination vertex with the assumption that formation of such a path is possible. In this work, different traffic conditions occur on different edges with certain probabilities and in those traffic conditions, time taken to cover every vertex is given by trapezoidal fuzzy numbers. Randomness and impreciseness has been dealt in this work by using expectations of fuzzy random variables and ranking of trapezoidal fuzzy numbers respectively. Two examples have also been solved using the proposed approach. This result may be useful to find the shortest path for ambulance problem in a route, when the traffic conditions are changing randomly.