Caminos Pareto-eficientes en redes: aplicaciones

Abstract

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 so-called 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.