The shortest path problem (SPP) is an optimization problem of determining a path between specified source vertex s and destination vertex t in a fuzzy network. Fuzzy logic can handle the uncertainties, associated with the information of any real life problem, where conventional mathematical models may fail to reveal proper result. In classical SPP, real numbers are used to represent the arc length of the network. However, the uncertainties related with the linguistic description of arc length in SPP are not properly represented by real number. We need to address two main matters in SPP with fuzzy arc lengths. The first matter is how to calculate the path length using fuzzy addition operation and the second matter is how to compare the two different path lengths denoted by fuzzy parameter. We use the graded mean integration technique of triangular fuzzy numbers to solve this two problems. A common heuristic algorithm to solve the SPP is the genetic algorithm. In this manuscript, we have introduced an algorithmic method based on genetic algorithm for determining the shortest path between a source vertex s and destination vertex t in a fuzzy graph with fuzzy arc lengths in SPP. A new crossover and mutation is introduced to solve this SPP. We also describe the QoS routing problem in a wireless ad hoc network.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Introduction
The shortest path problem (SPP), which concentrates on obtaining a shortest path between a specified starting node and other destination nodes, is one of the most important and fundamental combinatorial network optimization problems [6, 8] in graph theory that has been appeared in several real life applications as a sub problem. fields including routing, transportation, supply chain management, communications and wireless network. The SPP has been researched extensively in several academic fields such as operations research and computer engineering in the conditions of efficiency ,effectiveness and analytical algorithmic techniques. Recently, many different types of SPPs have been studied. For e.g., Cheng et al. [4] have presented SPP for (n, k)-star graphs. In [40], Zhu and Wilhelm described the resource constrained SPP on a graph.
Experts emerge graph the modeling as a mathematical model for several decision making problems, e.g., routing [27], transportation [10], supply chain management [20], communications [31], wireless network [36], etc. They have remodeled those problems as a SPP between source node and other nodes within the modeled graph of the specific problem. The best path is determined using on the total number of predetermined measurement. In classical SPP, we find the shortest path in terms of edge weights which are classical numbers and all edges are linked with those numbers of the graph. The classical SPPs with deterministic edge weights have been researched intensively, and these SPPs can be found the solutions analytically and efficiently based on several algorithmic techniques presented by excellent researchers. These algorithmic techniques are considered to as classical shortest path algorithmic techniques. In any real world application of SPP, an edge/arc/link may represent traveling cost, traveling time, traveling distance or another variables. The weights of those edges are generally related with environmental scenarios and those values may be changeable in different condition. For example, the traveling time may change due traffic or weather conditions, however, the distance between two areas is same. Experts face difficulties to track the exact path length in such real life scenarios. Experts are generally considered the concept of fuzzy set into a network to deal this uncertain scenarios.
Anzeige
However, in real life scenarios, many kinds of uncertainty are generally encountered, because of imperfect data, failure, or some other reasons. In real world applications of SPP, like scheduling, transportation, vehicle green routing, etc. which are linked to environmental scenarios and the edge weights could be very much uncertain due to the fluctuation with weather or traffic conditions. Therefore finding the exact optimal path in such networks could be challenging. In such cases, many experts use the probability theory to manage the uncertainties of the SPP due to randomness. They have studied the stochastic SPP or fuzzy SPP. For e.g., an network administrator wants to design a communication network. It is very to hard to determine the accurate routing delays on communication links [17] because of the time changing scenarios of the traffic frequency on the telecommunication network. It is required to create a network system that can work in uncertain traffic frequency. The server node always requires to send some control message to all other client nodes in the telecommunication network whose transmission frequency are generally uncertain. In the present of aforementioned uncertainties, a network admin may get it very hard to find the precise random distributions of arc length/weight. It is very authentic and useful to consider the fuzzy arc lengths in SPP in uncertain environment. While presenting an algorithmic technique for dealing fuzzy SPP, we require ranking method and addition method between two different fuzzy numbers. Several researchers have studied a lots on SPP with different types fuzzy number as edge weights over the last two decades. This type SPP in fuzzy scenarios is known as fuzzy SPP (FSPP). There exists many researches in fuzzy shortest pathproblem (FSPP) [2, 3, 7, 9, 16, 18, 19, 21‐26, 28, 30, 32, 35, 37, 39].
There exists several routes and paths within two places. It is an important information for the decision maker to decide the minimum traveling time and cost for transportation, the robust path, the least traffic frequency, etc. Decision makers are considered as graph and they need to find the shortest path to solve this optimization problem. For e.g., in the fire stations, the main focus is to go the fire van to the home within their area in the minimum possible time. It is very much useful for disaster management term to find the lowest destructed path for fastest evacuation.
Decision maker used SPP to model many real life problems, e.g., telecommunication communications [29, 34], scheduling [1, 14, 33] etc. In [9], Dubois and Prade first time described fuzzy shortest path problem. They presented an algorithm for fuzzy shortest path problem which is the modification of the classical Ford Moore Bellman algorithm. In their paper, they used the concept of criticality of a path. In [3], Chanas and Kamburowski presented the idea of fuzzy preference relationship to find the shortest path and considered the concept of fuzzy preference relationship in their introduced method for the SPP. In [19], the authors represented each edge using an integer number in between a fixed upper integer number and 1. They considered the dynamic programming approach in their introduced algorithm to choose the path based on the membership grade which is settled by the expert. Lin and Chern [21] considered the edge as a most significant edge (vital edge) in the graph if its delete from the graph which will increase the shortest path maximum. They have presented a fuzzy membership function of the shortest path by using a linear programming method. They have proposed an algorithmic technique for determining the single most significant edge in a fuzzy graph. In [30], Takahashi et al. presented the SPP with fuzzy arc lengths and extended the method introduced by Okada [25]. The authors introduced a genetic algorithm to determine an approximate shortest path for large fuzzy graph. Nayeem and Pal [24] expressed the edge weights of a graph by triangular fuzzy number and interval number. Their proposed algorithm can solve the fuzzy shortest path problem and their proposed algorithm can work on both types of numbers. Hernandes et al. [18] described an algorithmic technique for solving fuzzy shortest path problem. The authors have used triangular fuzzy number to represent the weight of the each edge. In [22], Mahdavi et al. presented a dynamic programming technique to find the solution of the fuzzy shortest path chain problem. They proposed a ranking technique for their proposed algorithm which can help to avoid creating the set of shortest paths because the total count of shortest paths from a big fuzzy graph can be a high. It may be very difficult for an expert to chose an exact shortest path. In [7], Deng et al. have presented a extended classical Dijkstra’s technique to find the solution of the shortest path problem in an uncertain environment. The authors have represented the edge weights of the fuzzy network using trapezoidal fuzzy numbers. They have considered the graded mean integration method of fuzzy number in their algorithm to determine the length of the fuzzy path and it also helps to compare the fuzzy path distance between two distinct fuzzy paths. In [16], Hassanzadeh et al. presented a method for the finding the shortest path in a fuzzy graph with fuzzy edge weights. The authors used an addition operation based on \(\alpha \) cut to determine the length of the path. In their proposed addition operation, a least square method is proposed to compute an approximate fuzzy membership function for the corresponding addition operation. A genetic algorithm is also proposed for solving the fuzzy SPP which can deal the complexity of the addition of fuzzy numbers for a high scale fuzzy network.
Many scientists have worked a lots to present the exact algorithmic method, mathematical technique, heuristic technique and metaheuristic techniques for this SPP in fuzzy environment. Both mathematical technique and exact algorithmic technique are used to get the exact shortest path from a source node to a destination node of a graph within a very short time. However, the both of the algorithms require lots of the time to get the shortest path if the dimension of the networks are extremely high. The algorithm needs to search all possible paths to decide the shortest path which takes times. Due to this reason, heuristic network optimization algorithms are very much efficient to solve the SPP. There are many distinct types of heuristic algorithms to solve SPP such as artificial bee colony (ABC) algorithm, harmony search method, and genetic algorithm. Genetic algorithm is a popular and efficient algorithm to solve the SPP. It is population based searching method. In this algorithm, an individual (chromosome) presents a potential solution of the decision making problem. A set of distinct individuals(chromosomes) generates the population. In genetic algorithm, some individuals (chromosomes) of the population are recombined to produce new chromosomes. The new chromosomes are done by three genetic operations, selection method, mutation method and crossover method. Then, the chromosomes with more fitness values replace the chromosomes with more fitness values in the current population. In this technique, genetic algorithm determines the best solutions of the decision making problem. Many decision making problems can be figured out by genetic algorithm.
Anzeige
The motivation of this study is to present an extension of FSPP which will be efficient but simple enough to use in real life scenarios. To the best of our information, most of the researches done on FSPP with several different types of fuzzy numbers as the edge weights and there is no research work on the SPP based on genetic algorithm with fuzzy numbers as arc lengths in the literature till now. We require to predict the traveling time and traveling cost for formulating the SPP. It is very difficult for the decision maker to decide the exact time and cost of any route due to road condition, traffic load, accidents, and varying weather conditions. In this paper, we present the SPP from a specified source vertex to destination nodes on a fuzzy graph in which a trapezoidal fuzzy number is assigned to each edge as its edge weight. This SPP is defined as FSPP. We use the edge weights to represent the traveling time and traveling cost. A mathematical model is formulated for a FSPP and a software is used to determine the solution this problem. We introduce an algorithmic method based on genetic algorithm for determining the solution of the FSPP. Finally, we also describe the QoS routing problem in a wireless ad hoc network.
This manuscript is organized as follows. In this section, we describe some basic ideas and definitions of fuzzy set, fuzzy number, triangular fuzzy number, trapezoidal fuzzy number, and genetic algorithm. The next section presents the mathematical model for FSPP. The proposed genetic algorithm is described in the section. We introduce some examples in the section to present the idea of the algorithm. Finally, the conclusion is described in the last section.
Preliminaries
Definition 1
Generalized form of simple crisp set is said to be fuzzy set, where each element has various grade of membership value. In crisp set, it bases on two values, either it is zero (false) or it is one (true). It may not be sufficient to handle the human thoughts. However, fuzzy set can consider the total interval between one(true) and zero (false) for better outcome. In a fuzzy set, each member has membership within the [0, 1]. Let n be an object of N, then the fuzzy set \({\tilde{Q}}\) can be described as follows
Let \({\tilde{Q}}\) is a fuzzy set and \({\tilde{Q}}\) will be fuzzy number if it follows the four conditions
(a)
\({\tilde{Q}}\) must be normalize fuzzy set.
(b)
\({\tilde{Q}}\) must be convex fuzzy set.
(c)
The membership grade of \({\tilde{Q}}\) must be continuous.
(d)
The degree of membership of \({\tilde{Q}}\) must be in the real number.
In literature, there exists many different forms of fuzzy number, e.g., triangular, bell shape, trapezoidal, LR fuzzy number, etc.
Definition 3
Let \({\widetilde{U}}=\{{\underline{u}},u_{0}, {\overline{u}}\}\) be a fuzzy number. \({\widetilde{U}}\) has a triangular shaped membership function and it is a triangular fuzzy number (TFN). The TFN \({\widetilde{U}}\) is shown by its membership function \(\mu _{{\widetilde{U}}}(y)\) and it is described as follows.
$$\begin{aligned} \mu _{{\widetilde{U}}}(y)= {\left\{ \begin{array}{ll} \frac{y-{\underline{u}}}{u_{0}-{\underline{u}}} &{}\quad \textit{ if } \, u_{0} \ge y \ge {\underline{u}} \\ \frac{{\overline{u}}-y}{{\overline{u}}-u_{0}} &{}\quad \textit{ if }\, {\overline{u}} \ge y \ge u_{0}\\ 0 &{}\quad \textit{ otherwise } \end{array}\right. } \end{aligned}$$
Let \({\widetilde{V}}\)= \(\left\{ {\underline{v}}, v_{1}, v_{2}, {\overline{v}}\right\} \) be a fuzzy number. \({\widetilde{V}}\) always has a trapezoidal shaped membership function and it is a trapezoidal fuzzy number (TrFN). The membership function \(\mu _{{\widetilde{V}}}\) satisfy following conditions.
$$\begin{aligned} \mu _{{\widetilde{V}}}(y)= {\left\{ \begin{array}{ll} \frac{y-v_{1}}{v_{1}-{\underline{v}}}&{}\quad \text { if }\, v_{1} \ge y \ge {\underline{v}}\\ 1 &{}\quad \text { if }\, v_{1} \ge y \ge v_{2}\\ \frac{{\overline{v}}-y}{{\overline{v}}-v_{2}} &{}\quad \text { if }\, {\overline{v}} \ge y \ge v_{2}\\ 0 &{}\quad \text { if }\, y < {\underline{v}} \text { or } y > {\overline{v}} \end{array}\right. } \end{aligned}$$
(3)
Here, the \(v_{1}\) and \(v_{2}\) are 2 main possible value, \({\underline{v}}\) and \({\overline{v}}\) are the the least possible value and maximum possible value respectively. An example of TrFN is presented in Fig. 2.
Fig. 2
A TrFN
×
Ranking of operations on fuzzy numbers
In fuzzy optimization problem, ranking of fuzzy set is one of the most important part to solve this problem. It is done by defuzzification method which converts a fuzzy set into a specific real number. We use those real values is used for the rank of n of the fuzzy numbers. In this study, we consider the graded mean ranking method of TrFN [5] in our proposed genetic algorithm.
Definition 5
Let \({\widetilde{U}} = \left\{ {\underline{u}}, u_{0}, {\overline{u}}\right\} \) be a TFN and the graded mean value of TFN \({\widetilde{U}}\) is computed as
Let \({\widetilde{U}} = \left\{ {\underline{u}}, u_{0}, {\overline{u}}\right\} \) and \({\widetilde{V}} = \left\{ {\underline{v}}, v_{0}, {\overline{v}}\right\} \) be 2 TFNs. The fuzzy graded mean value of 2 TFNs can be found by the following two equations.
The \(P({\widetilde{U}})\) and \(P({\widetilde{V}})\) values are used to compare two fuzzy number \({\widetilde{U}}\) and \({\widetilde{V}}\) as follows.
(a)
If the value \({\widetilde{U}}\) and \({\widetilde{V}}\) both are equal then \(P({\widetilde{U}})\)\(=\)\(P({\widetilde{V}})\).
(b)
If the value of \({\widetilde{U}} > {\widetilde{V}}\) then \(P({\widetilde{U}})\) > \(P({\widetilde{V}})\).
(c)
If the value of \({\widetilde{U}} < {\widetilde{V}}\) if \(P({\widetilde{U}})\) < \(P({\widetilde{V}})\).
Definition 7
Let \({\widetilde{U}} = \left\{ {\underline{u}}, u_{0}, {\overline{u}}\right\} \) and \({\widetilde{V}} = \left\{ {\underline{v}}, v_{0}, {\overline{v}}\right\} \) be 2 TFNs. The addition method of this 2 TFNs can be performed as follows
Let \({\widetilde{U}} = \left\{ {\underline{u}}, u_{1}, u_{2}, {\overline{u}}\right\} \) be a TrFN. The graded mean value of \({\widetilde{U}}\) can be determined as
Let \({\widetilde{U}} = \left\{ {\underline{u}}, u_{1}, u_{2}, {\overline{u}}\right\} \) and \({\widetilde{V}}\) = \(\left\{ {\underline{v}}, v_{1}, v_{2}, {\overline{v}}\right\} \) be 2 TrFNs. The addition method of this 2 TrFNs can be performed as follows
Genetic algorithm is a heuristic based searching algorithm. Genetic algorithm uses the concepts of natural genetics. This algorithm is inspired by Darwin’s principal of survival of fittest. Genetic algorithms have been treated as a strong solver to solve combinational optimization problems [11‐13]. In the past years, they have been successfully used for dealing with complex optimization problems.
1.
Begin: A initial population of size N which consists of chromosomes is created.
2.
Fitness value determination: The fitness of chromosome in the current population is computed.
3.
New population creation: A new population is created by executing the following step.
3.1.
Selection operation: Two different chromosomes are chosen as parent chromosomes from the current population. The section method is done on based on the fitness values of the chromosomes. If a chromosome has higher fitness value then it has more possibility to be chosen.
3.2.
Crossover method: The crossover method is executed on the selected parent chromosomes to develop new chromosomes (children). The crossover probability is the main parameter in crossover operation which tells that how often this operation will be executed. If no crossover method is executed, then the child chromosomes are the precisely same copies as the parent chromosomes.
3.3.
Mutation method: Some selected chromosomes are performed the mutation operation with a specified mutation probability.
3.4.
Accepting: All the newly generated chromosomes are accepted and placed in the current new population.
3.5.
Replace: Then, the genetic algorithm uses the newly generated population for a further computation.
3.6.
Test: The terminal condition of the genetic algorithm satisfies, then end and return the chromosome with highest fitness value in that population. This chromosome is taken as the optimal solution of the decision making problem.
3.7.
Loop: Else, Go to Step 2 and perform all other step.
Formulation of FSPP
In this section, we present the idea of the SPP in fuzzy environment. This SPP is said to be FSPP. We introduce a fuzzy linear programming method to formulated and solve the FSPP.
Let \({\mathcal {G}} = (Y,Z)\) be directed weighted fuzzy graph. The fuzzy graph has p number of nodes represented as \(Y=\{1,2,\ldots ,p\}\) and of q number of directed weighted arcs \(Z \subseteq Y \times Y\). Each arc of the fuzzy graph \({\mathcal {G}}\) is described by an order pair \((y_1, y_2)\), here \(y_1 \ne y_2\) and \(y_1, y_2\in Z\). In this fuzzy graph, we have assumed that there is only one directed arc \((y_1, y_2)\) between the two nodes \(y_1\) and \(y_2\). The starting node of the path is x and target node is y. Here, we consider a non negative TrFNs \({\tilde{c}}_{y_1,y_2}\) which are related to the arc \((y_1,y_2)\). Here, \({\tilde{c}}_{y_1y_2}\) is utilized to describe the fuzzy cost from the vertex \(y_1\) and \(y_2\).
We introduce the fuzzy linear programming model of FSPP as follows:
Here, \(F_{ab}\) is binary variable related with arc \((y_1,y_2)\). If arc \((y_1 y_2)\) presents in the fuzzy shortest path, then \(F_{y_1 y_2}\) =1 else \(F_{y_1 y_2} =0.\)
Proposed algorithm for FSPP
Given a directed weighted fuzzy graph and its edge weight, our proposed genetic algorithm determines the fuzzy shortest path between two specific nodes, starting and target nodes of the fuzzy graph. In this section, a genetic algorithm is introduced to solve the FSPP in a fuzzy graph. We have shown the flowchart of our proposed algorithm in Fig. 3.
Fig. 3
A flowchart of our proposed genetic algorithm for FSPP
×
Chromosome encoding
In our proposed genetic algorithm, each chromosome describes a path between the starting node and target node of the fuzzy graph. It is a possible solution which may not be shortest path, i.e., optimal solution. A chromosome consists of a finite set of nodes in the same place as present within the path. Every nodes in the fuzzy graph are assigned unique integer numbers. In this FSPP, the first node of a chromosome is always the starting node. For creating a path (starting node to target node) needed to encode a chromosome, the starting vertex is assumed first to produce the next node of the specific path. We are tried to determine its next node of the path in representing chromosome. To solve this problem, a node, say x, is randomly selected from the list of adjacent nodes of the starting node. If the selected node x is not still present in the chromosome, then the node x is used as the next node of starting node in the chromosome. The method of including the next node in the specific chromosome is done until it comes the destination node.
Fitness function
The fitness value of any chromosome describes the quality of corresponding chromosome. In our algorithm, the objective is to determine a path between specified starting node x and target node y in a fuzzy network such that the path length is minimum. A fuzzy path starting node x and target node y can be described by a TrFN. The graded mean ranking technique is applied to computed the rank of the specified path. The rank of the path is the real number of the corresponding fuzzy number.
Selection method
In genetic algorithm, the selection method uses for choosing the more number of chromosomes having higher fitness values and so choosing less number of chromosomes having less fitness values. In our proposed genetic algorithm, we use binary tournament selection technique, where the fitness values are compared between 2 randomly chosen chromosomes and choose the good chromosome for the crossover.
Crossover method
Crossover method is employed to recombine two parent chromosomes to generate two new child chromosomes. In the crossover method, several properties of two parent chromosomes are inherited to their two child chromosome which describes different solutions from their parent chromosomes. We have used the following crossover method in our proposed algorithm.
Fig. 4
A fuzzy network with fuzzy arc length
×
×
Results
We have executed our proposed genetic algorithm on a fuzzy graph with 24 nodes and 43 edges. We have numbered randomly from 1 to 23, as shown in the Fig. 4. Let the starting node be node 1. The fuzzy edge weights of the fuzzy graph are presented in Table 1 as TrFNs. In the literature, we do not find any fuzzy graph whose each edge has two weights. One is for fuzzy traveling cost and an another is fuzzy traveling time. For this fuzzy graph, presented in Fig. 4, 86 different random values of TrFN are taken for fuzzy arc lengths and each edge consists two edge weights. They are shown in Table 1.
Table 1
The fuzzy traveling costs of the network
Edge
Fuzzy traveling cost
Edge
Fuzzy traveling cost
(1, 2)
(8, 9, 10, 12)
(1, 3)
(13, 15, 16, 17)
(1, 4)
(1, 2, 3, 7)
(2, 7)
(13, 15, 16, 17)
(1, 5)
(7, 9, 10, 12)
(2, 6)
(5, 8, 9, 10)
(3, 8)
(8, 9, 10, 12)
(4, 7)
(3, 5, 7, 9)
(4, 11)
((2, 4, 5, 10))
(5, 8)
(5, 8, 9, 10)
(5, 11)
(8, 9, 10, 12)
(5, 12)
(13, 15, 16, 17)
(6, 9)
(32, 33, 35, 37)
(6, 10)
(13, 16, 20, 22)
(7, 10)
(9, 11, 12, 13)
(7, 11)
(2, 4, 5, 10)
(8, 12)
(7, 10, 12, 19)
(8, 13)
(5, 8, 9, 10)
(9, 16)
(13, 15, 16, 17)
(10, 16)
(2, 4, 5, 10)
(10, 17)
(22, 23, 24, 26)
(11, 14)
(1, 2, 3, 7)
(11, 17)
((3, 5, 7, 9))
(12, 14)
(5, 8, 9, 10)
(12, 15)
(10, 15, 16, 17)
(13, 15)
(10, 11, 13, 15)
(13, 19)
(13, 15, 16, 17)
(14, 21)
(5, 8, 9, 10)
(15,18)
(9, 10, 12, 16)
(15, 19)
(9, 10, 12, 14)
(16,20)
(1, 2, 3, 7)
(17, 20)
(9, 10, 13, 16)
(17,21)
(1, 2, 3, 7)
(18, 21)
(1, 6, 9, 15)
(18,22)
(18, 20, 21, 23)
(18, 23)
(21, 25, 26, 28)
(19,22)
(13, 15, 16, 17)
(20, 23)
(10, 12, 15, 16)
(21,23)
(12, 16, 18, 20)
(22, 23)
(7, 8, 9, 10)
(22,24)
(6, 7, 8, 9)
(20, 24)
(3, 5, 7, 9)
(23,24)
(5, 8, 9, 10)
Our proposed genetic algorithm is applied to select the fuzzy shortest path (FSPP) between the starting node 1 and several different target nodes. The average fuzzy values are considered of the fuzzy shortest path lengths in distinct generation from 20 runs of our proposed genetic algorithm. For this problem, we consider the crossover probability and mutation probability as 0.7 and 0.6. For every cases, the fuzzy shortest path length is found exactly same. We have pointed the fuzzy values of traveling cost of the FSPP between the starting node 1 and several target nodes In Table 2. The FSPP from the starting node 1 to the target node 24 is \(1 \rightarrow 4 \rightarrow 7 \rightarrow 10 \rightarrow 16 \rightarrow 20 \rightarrow 24\). The computed traveling cost of this FSPP is [12, 22, 30, 52]. The FSPP from the starting node 1 to the target node 20 is \(1 \rightarrow 4 \rightarrow 7 \rightarrow 10 \rightarrow 16 \rightarrow 20\). The computed traveling cost of this FSPP is [9, 17, 23, 43]. The FSPP from the starting node 1 to the target node 14 is \(1 \rightarrow 4 \rightarrow 11 \rightarrow 14\). The computed traveling cost of this FSPP is [5, 9, 13, 23].
In this study, this FSPP is also solved using fuzzy mathematical model. We have presented the fuzzy mathematical model of FSPP in (10). We have used the CPLEX software to solve this FSPP. The solution of our proposed genetic algorithm and CPLEX are shown in Table 3. The computed FSPP from the starting node 1 to all other target nodes using of our genetic algorithm is properly same to the path of the CPLEX software. However, our genetic algorithm requires less time than the solution of CPLEX software.
Application of FSPP
Many researchers have worked on mobile wireless networking over the last few years due to its significant applications in real life situations. There exist no wired or cellular networks in mobile wireless network. The mobile device communicates with other mobile device using a single hop wireless link if and only if the receiver mobile device is in the transmission range of the sender mobile device. Otherwise it can communicates using multi-hop transmission method based on intermediate mobile devices to send the control message. Each mobile device in the mobile wireless network works as a router and it forwards the data packets to another mobile devices. In a single hop wireless link, a mobile device can be received by all other mobile devices within its range of transmission. Each and every mobile device has a global position system collector, which helps to provide the position of the mobile device and each mobile device also knows the information about the positions of all other mobile devices that are in its range of transmission. A mobile wireless network can be modeled by using a weighted directed fuzzy graph \(\mathcal {G=X,Y}\). Here, \({\mathcal {X}}\) represents the finite set of all the mobile devices in the wireless network and arc \(a,b\in {\mathcal {Y}}\) if the mobile device a is within the transmission range of the mobile device b. \({\mathcal {G}}\) is strongly weighted connected fuzzy graph, in which there exist only directed path between any two nodes. Unicast routing technique is used to choose a connecting path of given two mobile devices and multicast routing method is to determine a tree that links a set of mobile devices. Unicast routing is an application constrained shortest path problem. There exists several fuzzy cost parameters \(c_1,c_2,\ldots ,c_n\) related with the transmission links of the network \({\mathcal {G}}\). A fuzzy path p is said to be a fuzzy feasible path if the all fuzzy cost parameters \(c_1,c_2,..,c_n\) fulfill the given n constraints. A feasible path is said to be the FSPP if the path is the minimum (optimal) between all the feasible paths.
Conclusion
The fuzzy shortest path problem is a very popular combinatorial network optimization problem in the field of fuzzy graph theory. Many scientists work several different kinds of fuzzy shortest path problem. In SPP, decision maker determines a path between specified source vertex s and destination vertex t in a graph such that the path length is minimum and traveling time within two vertices. In this study, we present the SPP, where arc lengths are represented by TrFNs. This type of SPP is defined as FSPP. The importance of considering TrFNs as arc lengths in FSPP is presented in this study. This paper presents a fuzzy mathematical model for FSPP. We have used the CPLEX software to solve this FSPP. We introduce an algorithmic method based on genetic algorithm for solving this FSPP. FSPP is one of the most important problems in supply chain management which contains multiple organizers such as production manufacturers and distributors. In future study, the FSPP can be remodeled to real life problems in supply chain management, production and distribution problems [15, 38], transportation, telecommunication and other relevant areas.
Acknowledgements
Science and Technology Project of State Grid Xizang Electric Power Co., Ltd SGXZJY00JHJS2000007. Influence of Energy Storage Technology Application on Power Grid. Science and Technology Project of State Grid Zizang Electric Power Co., Ltd SGXZJY00JHJS2000008. Research Technology Service of Multi Energy Complementary Demonstration Application. Project supported by the National Natural Science Foundation of China Research on Precision Evaluation Model of Goaf Pressure Relief Gas Drainage Based on LSTM Regression No. 51804248.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
