-How to find optimal route between two cities of Silesian voivodeship taking into consideration four factors road's distance, condition, traffic level and maximum speed? A combination of fuzzy logic, graphs theory and Dijkstra's algorithm is an answer for this quation. Taking all this components, a simple system solving this problem was presented in this paper. A weighted graph with edges' weights defined by fuzzy logic was applied in Dijkstra's algorithm and a route between two given cities was found as a result. The proposed solution and conducted experiments are described and discussed in this paper.
In XII century technical development and geopolitical
situation caused sudden increase of travel possibilities and therefore
showed up new problems connected with transport. People
could not memorize all the roads and using regular paper
map costed valuable time, not necessarily giving the best
of possible ways. Furthermore, there was no possibility of
measuring other factors than distance, like traffic level or
road’s condition, which are also very important. So people
began to look for mathematical models to solve cumulative
problems. New way of describing the world was invented
fuzzy sets [
Fuzzy sets are an important element of today’s computer
science, which find a wide range of applications in
practical problems. To this day, mathematical aspects are being
expanded and improved, what can be seen on the example
of the presented works around the world. In [
not describe things in true or false terms. If some people are c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) hot (1) (2) 1 0:8 p i h s r e b 0:6 m e m f o 0:4 e e r g e D 0:2 0 0 10 20 30 40 50
At the example fuzzy set above we can see that for values 18 C - 24 C it is hot in some extent defined by the membership function, then from 24 C to 30 C it is definitely hot and finally, again, definition of hotness is not so clear. Such functions are based on expert knowledge - experience, statistics or other sources. It depends on modeled system.
A = f(x); A(x)jx 2 X) where A : X ! [0; 1] is a membership function. It is often denoted by (proposed by Lotfi Zadeh): for finite set X:
n A = X i=1
A(x)=x; where / is not division mark and sum does not mean summing, but the fuzzy set being built from elements xi of finite set X and being described by membership function A(x); for infinite set X:
Z
x2X A =
A(x)=x; (3) where / is not division mark and sum does not mean summing, but the fuzzy set being built from elements xi of infinite set X and being described by membership function A(x).
Membership functions have many shapes, but the most used ones are trapezoidal, triangular, Gaussian and sigmoid.
With help of fuzzy sets it is possible to make a decision making system. For example, we wonder if it is a good idea to go running given the time of the day and the temperature. Using suitable mathematical method, this decision can be easily made. One of those methods is Mamdani’s fuzzy inference system. It’s schematic way of working is shown below:
function for each element of input vector.
If time is late and temperature is high, then probability of running is high
We have two parameters having their own membership functions, defining their states (like hot, early). We convert crisp input values into fuzzy ones and take minimum of them for logical operator or between the parameters and maximum for and. Later, we aggregate the results of all rules by taking their maximum.
Defuzzification: Sharpening the result of inferencing (fuzzy set) into numeric value. One of defuzzification methods is centre of gravity method. Outcome is calculated from formula: (4) (5) for finite sets for infinite sets n
X xi (xi) output = i=1 n X (xi)
; i=1 Z X
a) Graph definition: Graph is a mathematical structure used for showing relations between objects. In a simplified way, it is a collection of vertices (or nodes) and connections between them, called edges. There are specific types of graphs i.a.: weighted graph - edges have weights undirected graph - edges do not have orientations b) Adjacency matrix: It is a square matrix used to represent graph. Value of element aij indicate if there is a connection (edge) between vertices i and j.
Algorithm step by step: 1) Mark all vertices unvisited and make a set of them. Label the starting vertice as current. 2) For each vertice assign a distance - zero for the one you start from, infinity for the rest. 3) Calculate distance from starting point for all unvisited neighbours of current vertice. Compare the new value with the old one and save smaller. 4) Remove the current vertice from the unvisited set (it will not be checked again). 5) If all vertices have been visited or the smallest distance among vertices in unvisited set is infinity, then stop. 6) Otherwise, set the vertice with shortest distance as current and go to step 3.
Weighted, undirected graph was made, where cities of Silesian voivodeship were vertices and roads between them were edges. The weights consisted of length, condition, level of traffic and maximum speed. To save the data in memory a slightly modified adjacency matrix was used - values inside it kept not only the information about existence of the road, but also it’s weight.
1
Fuzzy sets were modelled for every parameter of the road’s weight. Length of the road to actual distance ratio was used to check how much "unnecessary" track has to be driven. Choosing only length would make no sense, because it would always return the same values, no matter if the road would lead in straight line or be a winding one (so a longer one). For example, if there would be two roads from city A to B, one longer that another, but not long enough to qualify to different fuzzy set, the result might be the same for both. The method using ratio takes it into consideration.
The actual distance between cities was calculated using geographical coordinates and formula: r (x2 x1)2 + (cos (y2
y1))2 0:8 0:2 0 0 short average
long very long groups for each linguistic expression in output set (bad, average, good), for example: 0:2 0:4 0:6
20 40 60 80 100 120 140
Maximum speed [ khm ]
Output membership function 1 0:8 0:8 i c ´ s o n ˙ze 0:6 l a n y z r ´np 0:4 e i p o t S 0:2
0:8 e e r g d 0:6 e p i h s r b 0:4 e m e M 0:2 0 0 0:2
0:4 0:6
0:8 1 Set of rules was implemented. They were divided into Having been applied, Mamdani’s inference system evaluated weight of every road in adjacency matrix. Dijkstra’s algorithm used this modified matrix to determine optimal road between given cities. low average
high 0:8
1 slow medium
fast very fast
If length to actual distance ratio is short and condition is good and traffic level is low and max speed is fast, then quality of road is good
If length to actual distance ratio is short and condition is average and traffic level is high and max speed is fast, then quality of road is average If length to actual distance ratio is very long and condition is bad and traffic level is high and max speed is slow, then quality of road is bad
We took two cities - Gliwice and Zawiercie to check Dijkstra’s algorithm. As shown on Table II, each route’s weight was determined using fuzzy logic.
On this small example it is easy to calculate without any algorithm, that the finest route from Gliwice to Zawiercie leads through Ruda S´ la˛ska and Katowice. Outcome of Dijsktra’s algorithm matches with this calculation.
ID 1 2
Connecting described mathematical models - fuzzy sets, graphs theory and Dijkstra’s algorithm - can result in properly working system for determining optimal route between two points at the map. In this project data regarding road status was set statically, but if some sensors or processed satellite’s images were used to provide the data and graph was expanded, it could be utilized as navigating system. However, it’s efficiency might not be the best, as Dijkstra’s algorithm looks through all vertices, so it could be replaced by different route finding algorithm.
Defining fuzzy sets also needs a closer look. As they are created on basis of experts knowledge, it is not easy to check if we made them properly. Some research should be made to have a foundation to work on and determine them the finest way. [10] A. Fornaia, C. Napoli, and E. Tramontana, “Cloud services for ondemand vehicles management,” Information Technology and Control, vol. 46, no. 4, pp. 484–498, 2017.