engleski

Algebraic formulation and solution of robust path problems

Path problems in graphs deal with finding shortest paths, most-reliable paths, paths of maximum capacity, etc. It is well known that various types of such problems can be treated together within a common algebraic framework. Then, each type is characterized by a different "path algebra", i.e. a different instance of the same abstract algebraic structure. In this work, robust variants of path problems are considered, where arc lengths, reliabilities or capacities are uncertain and expressed through explicitly given scenarios. It is demonstrated that the common algebraic framework, although originally intended for conventional problem variants, can be extended to cover robust variants. Consequently, this work is mainly concerned with constructing new path algebras that correspond to robust path problems. Such algebras are relatively complex, and they incorporate algebras associated with conventional problems as their building blocks. A benefit of the obtained algebraic formulation is that robust path problems can be solved by well-known general algorithms designed to work over an arbitrary path algebra (e.g. analogues of Gaussian elimination). Indeed, the same algorithms that are used for conventional problems can as well be used for robust problems, although individual algebraic operations within those algorithms are in the robust case more complex. The resulting robust solutions are represented as sets of vectors that are efficient in the Pareto sense.

Directed graph ; Path problem ; Path algebra ; Robust optimization ; Pareto efficiency

nije evidentirano