- Tytuł:
- Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms
- Autorzy:
- Tarapata, Z.
- Powiązania:
- https://bibliotekanauki.pl/articles/929638.pdf
- Data publikacji:
- 2007
- Wydawca:
- Uniwersytet Zielonogórski. Oficyna Wydawnicza
- Tematy:
-
problem najkrótszej ścieżki
złożoność algorytmu
algorytm aproksymacji
multiobjective shortest path
stochastic shortest path
algorithm complexity
routing problem
terrain-based modeling
approximation algorithm - Opis:
- The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multiobjective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness of solving selected MOSP problems defined as mathematical programming problems (using the CPLEX 7.0 solver) and multi-weighted graph problems (using modified Dijkstra’s algorithm) is given. Experimental results of using the presented methods for multicriteria path selection in a terrain-based grid network are given.
- Źródło:
-
International Journal of Applied Mathematics and Computer Science; 2007, 17, 2; 269-287
1641-876X
2083-8492 - Pojawia się w:
- International Journal of Applied Mathematics and Computer Science
- Dostawca treści:
- Biblioteka Nauki
Artykuł