<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multi-objective 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.</p></abstract>

The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multi-objective 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.

Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms

Division of Operations Research and Decision Support Cybernetics Faculty, Military University of Technology, ul. Kaliskiego 2, 00-908 Warsaw, Poland

International Journal of Applied Mathematics and Computer Science

The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multi-objective shortest path (MOSP)...

Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms

Published Online: Jul 17, 2007

Page range: 269 - 287

DOI: https://doi.org/10.2478/v10006-007-0023-2

Keywords
multiobjective shortest path, stochastic shortest path, algorithm complexity, routing problem, terrain-based modeling, approximation algorithm

This content is open access.

Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms

Published Online: Jul 17, 2007

Page range: 269 - 287

DOI: https://doi.org/10.2478/v10006-007-0023-2

Keywordsmultiobjective shortest path, stochastic shortest path, algorithm complexity, routing problem, terrain-based modeling, approximation algorithm

This content is open access.

Keywords
multiobjective shortest path, stochastic shortest path, algorithm complexity, routing problem, terrain-based modeling, approximation algorithm