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

Optimal Path Problem with Possibilistic
Weights

Jan Caha and Ji

ř í

Dvorsk ý

Abstract The selection of optimal path is one of the classic problems in graph
theory. Its utilization have various practical uses ranging from the transportation,
civil engineering and other applications. Rarely those applications take into account
the uncertainty of the weights of the graph. However this uncertainty can have high
impact on the results. Several studies offer solution by implementing the fuzzy
arithmetic for calculation of the optimal path but even in those cases neither of
those studies proposed complete solution to the problem of ranking of the fuzzy
numbers. In the study the ranking system based on the Theory of Possibility is used.
The biggest advantage of this approach is that it very well addresses the indistin-
guishability of fuzzy numbers. Lengths of the paths are compared based on the
possibility and the necessity of being smaller than the alternative. The algorithm
offers the user more information than only the optimal path, instead the list of
possible solutions is calculated and the alternatives can be ranked using the pos-
sibility and the necessity to identify the possibly best variant.

Keywords Fuzzy numbers Dijkstra algorithm Optimal path Uncertainty

1 Introduction

The selection of optimal or least-cost path through space is one of the common
issues in the GIS. The optimal path may be chosen either in a network or on a
surface. In both cases the algorithms used for selecting optimal path are based on
graph theory, so there is actually little difference between the raster and the vector