Localización en redes complejas

Abstract

During last decades, it has been taken an interest in the modeling of complex systems that could not be represented by classical graph theory. Such systems are characterized by a structure that cannot be reduced or simplified to a simple network, even by projection, without loss of information. This would be the case, for example, of the transportation network that is established in a certain city, where different means of transport (metro, bus, tram, ...) can coexist with different natures. There are many complex representation models, but in this paper we are going to focus on multilayer graphs. A multilayer graph is a pairM = (G, C) where G = fGa; a 2 Mg (with M = f1, . . . ,mg being the layer’s index subset of M) is a family of (directed or undirected, weighted or unweighted) graphs Ga = (Va, Ea), called layers ofM, and C = fEab Va Vb; a, b 2 M, a 6= bg is the set of interconnections between nodes of different layers Ga y Gb with a 6= b. In this structure we will study two types of location problems. On the one hand, we will see the network design problems where we have origin-destination demand pairs we must satisfy according to different imposed and objective conditions. We will provide a formulation of the three possibly most studied location problems: the Median Problem, the Center Problem and the Coverage Problem. On the other hand, we will see the point location problems, where we are not going to have origin-destination pairs to satisfy, but we will consider different objectives taking into account the nodes of the network, without distinguishing whether a node is the origin or the destination of a pair or not. In both types, we will see how beyond the most basic cases of the problem, the multilayer structure is required. Thus, it is not possible to make a projection of the multilayer network to transform it into a graph with the classic topology where to solve it, but a different topology of the problem is required.

Durante las últimas décadas, se ha puesto un especial interés en el modelado de sistemas complejos que no han podido ser representados mediante la teoría de grafos clásica. Dichos sistemas se caracterizan por tener una estructura que no puede ser reducida o simplificada a un grafo simple, ni siquiera mediante una proyección, sin que eso conlleve pérdida de información. Éste sería el caso, por ejemplo, de la red de transporte que está establecida en una cierta ciudad, donde pueden coexistir distintos medios de transporte (metro, autobús, tranvía, ...) con distintas naturalezas. Existen multitud de sistemas complejos, pero en el presente trabajo vamos a centrarnos en los grafos multicapa. Una red multicapa es un par M = (G, C) donde G = fGa; a 2 Mg (con M = f1, . . . ,mg el conjunto de indices de las capas de M) es una familia de grafos (dirigidos o no, ponderados o no) Ga = (Va, Ea), llamados las capas deM, siendo C = fEab Va Vb; a, b 2 M, a 6= bg el conjunto de interconexiones entre nodos de diferentes capas Ga y Gb con a 6= b. En esta estructura estudiaremos dos tipo de problemas de localización. Por un lado, veremos los problemas de diseño de redes en los que tenemos pares origen-destino que debemos satisfacer atendiendo a diferentes condiciones impuestas y objetivos. Proporcionaremos una formulación de los tres problemas de localización posiblemente más estudiados: el Problema de la mediana, el del centro y el de cobertura. Por otro lado, veremos los problemas puntuales de localización, en los que ya no habra pares origen-destino que satisfacer, sino que consideraremos diferentes objetivos teniendo en cuenta los nodos del grafo, sin distinguir si un nodo es origen o destino de algún par. Tanto de un tipo como de otro, veremos como más allá de los casos más básicos del problema, se requiere de la estructura multicapa, no pudiéndose realizar una proyección del grafo multicapa para transformarlo en un grafo unicapa, donde resolverlo, sino requeriendo una topología del problema diferente.