Resumen:

The problem of finding the path in a network connecting two given nodes,
source and sink, with minimum possible cost is known in the literature as
the shortest path problem (SPP) and it is a core model that lies at the
heart of network optimization. The reason is the wide range of its practical
applications and the large amount of interesting generalizations that can be
considered, among them, the analysis of the multiobjective shortest path
problem. This last model allows us to find how to send a given product
between two specified nodes of a network as quickly, as cheaply and as reliable as possible taking into account the socalled Pareto optimal paths.
The text presented here consists of two chapters. The first one is devoted
to the introduction of some notation and properties related to networks where each arc is associated to just one cost value. The formulation of the SPP as a Mathematical Programming model is considered as well as its corresponding dual problem. The c...
[Ver más]
The problem of finding the path in a network connecting two given nodes,
source and sink, with minimum possible cost is known in the literature as
the shortest path problem (SPP) and it is a core model that lies at the
heart of network optimization. The reason is the wide range of its practical
applications and the large amount of interesting generalizations that can be
considered, among them, the analysis of the multiobjective shortest path
problem. This last model allows us to find how to send a given product
between two specified nodes of a network as quickly, as cheaply and as reliable as possible taking into account the socalled Pareto optimal paths.
The text presented here consists of two chapters. The first one is devoted
to the introduction of some notation and properties related to networks where each arc is associated to just one cost value. The formulation of the SPP as a Mathematical Programming model is considered as well as its corresponding dual problem. The complementary slackness theorem provides us with a characterization of any basic feasible solution as a spanning tree in the original network. A sufficient optimality condition is also derived from this relation. Finally, the Dijkstra algorithm is studied as well as other specific algorithms that use special properties on acyclic networks.
The second chapter extends the hypotheses considered in the previous
one to a multiobjective context. The continuous formulation of the problem
of finding the Pareto optimal paths is compared with its discrete version
and some properties are stated. A generalization of the Dijkstra algorithm
is proposed in order to find the whole set of Pareto optimal solutions. This
procedure allows us to determine that the optimal set of paths corresponds
with a set of adjacent trees. This property is very important in order to
generate the Pareto optimal set of solutions and is the basis of a new improved algorithm that, starting with a given optimal tree, explores its adjacent trees and finds those Pareto optimal ones by using the duality conditions of the complementary slackness theorem presented in the chapter one.
[Ver menos]
