Optimal Path Problem with Possibilistic Weights - Geoinformatics for Intelligent Transportation - page 39

datasets. The range of possible utilization is very wide, from route planning to many
civil engineering applications especially in construction of various networks [ 1 ].
Like any other type of data even data for selecting optimal path are affected by
uncertainty. The main uncertainty affecting selection of optimal path is the uncer-
tainty of weights or in other words cost for travelling from one node to another.
These weights of edges can represent many real world phenomena, for example
geographical distance of nodes, time necessary to cover the distance or amount of
fuel needed for this particular distance. While distance can be measured quite
exactly it is not particularly suitable as a measure for

finding optimal path [ 2 ],
mainly because distance alone does not tell anything about fitness of the solution.

On the other hand, the time and/or amount of fuel necessary for travel are good
indicators for optimal path selection. Yet none of those two can be expressed
exactly for real world problems. Both of them are highly dependant on many other
variables and thus un

t to be expressed as a crisp number [ 3 ]. It is much better to
express them as a vague and ill-know values, using fuzzy set theory as fuzzy
numbers [ 4 ].
Modi cations of the Dijkstra and other algorithms for selection of the optimal

path were studied in several studies [ 1

9 ]. All of those papers aims at calculating
the optimal or the shortest path in a network when the uncertainty of the arc weights
is presented in the graph, however each of these studies utilize different ways to
obtain the results. The process has two main challenges that have to be addressed in
order to produce the algorithm. These challenges are addition of the fuzzy numbers
and their ranking. The addition of fuzzy numbers is usually described for the
triangular and the trapezoidal fuzzy numbers [ 3 , 4 , 6 ], however these are not all the
possible shapes of the fuzzy numbers and other variants can be also used. The
addition is presented for mentioned shapes mainly because it can be easily
implemented and calculated. But there are more general solutions that work for
variety of other fuzzy number shapes [ 10 ]. Some authors [ 4 ] even use methods that
provides a crisp value as the result of addition of fuzzy numbers. While this may be
easier for further ranking of the results it leads to the loss of information about
vagueness and/or imprecision of the fuzzy number.
The second challenge that need to be solved is ranking of fuzzy numbers. As
noted by Dubois and Prade [ 11 ] there is no natural total-ordering structure for a set
of fuzzy numbers and many of the approaches to the problem are either counter-
intuitive and/or consider only one point of view on the matter. Some studies pro-
pose algorithms where any of indices for comparison of fuzzy numbers can be used
[ 6 ]. While some use speci

-

c indice or even distance of fuzzy numbers for their
ranking [ 2 , 9 ]. While all mentioned approaches have their possible use, none of
them really address the problem of indistinguishability and overlap of fuzzy
numbers, which certainly should be solved. The solution can be found in use of
Possibility theory and indices proposed by Dubois and Prade [ 11 ].
The main advantage of the proposed algorithm is in generalization of fuzzy
numbers addition. There is no assumption about shape of fuzzy numbers, instead
the methods that use piecewise linear fuzzy number are used. Such fuzzy numbers
can have any shape. The framework of Possibility theory is used for ranking of