Exact and metaheuristic approaches for network desing problems

As a consequence of globalization, interactions among countries, companies, people, etc, have been increased during recent decades. The basic mathematical support structure for modeling such interactions is a network. Thus, Network Design plays an important role for facilitating the interactions. Nevertheless, the majority of Network Design problems are difficult to solve. Our goal is to study them from the Combinatorial Optimization point of view to find exact and metaheuristic approaches that improve the process of getting optimal ,or at least good, solutions for practical applications. In this thesis, we study some Network Design problems, which can be grouped into two large classes detailed below, according to the main feature of each one. In all the problems it is considered that the demand is given by a set of pairs of origin-destination points. That is, each demand has to move from an origin-node to a destination-node. Another feature in common is the existence of an alternative network that can be used by the demand set. In this situation, the possible existing competition between the network to be designed and the already actual alternative network has been highlighted. On the one hand, Chapters 2, 3 and 4 deal with Covering Network Design problems. These problems seek to design a network in such a way that the proportion of demand covered is maximized or exceeds a certain percentage of the total. Particularly, the third chapter shows a practical application for Network Design in the transportation area. On the other hand, Chapter 5 extends the existing notions in Facility Location Theory of -Cent-Dian and Generalized-Center to the area of Network Design. The problems in this chapter are focused on designing a network that minimizes the maximum distance of a known set of origin-destination pairs (within that network), the average distance, a linear combination of both objectives or the difference between them. These objectives may be of interest for some of
Como consecuencia de la globalización, las interacciones entre países, empresas, personas, etc., se han incrementado durante las últimas décadas. La estructura básica de soporte matemático para modelar interacciones es la red. Por lo tanto, el Diseño de Redes juega un papel importante para facilitar tales interacciones. Sin embargo, la mayoría de los problemas de Diseño de Redes son difíciles de resolver. Nuestro objetivo es estudiarlos desde el punto de vista de la Optimización Combinatoria para encontrar enfoques exactos y metaheurísticos que mejoren el proceso de obtención de soluciones óptimas, o al menos buenas, para aplicaciones prácticas. En esta tesis estudiamos algunos problemas de Diseño de Redes, los cuáles se pueden agrupar en dos grandes clases detalladas más adelante según la característica principal de cada uno. En todos los problemas se considera que la demanda está dada por un conjunto de pares de puntos origen/destino. Es decir, cada demanda tiene que pasar de un nodo de origen a un nodo de destino. Estos problemas diseñan una red para servir a cierta parte de este conjunto de pares de demanda. Otra característica que comparten es la de la existencia de una red alternativa que puede ser utilizada por este conjunto de demanda. De esta situación se ha destacado la posible competencia existente entre la red que se va a diseñar y la red alternativa actual. Por un lado, los Capítulos 2, 3 y 4 tratan con problemas de Cobertura para el Diseño de Redes. Estos problemas buscan diseñar una red de tal forma que se maximice la proporción de la demanda cubierta o se cubra un cierto porcentaje del total. En particular, el tercer capítulo muestra una aplicación práctica para el Diseño de Redes en el área del transporte. Por otro lado, el Capítulo 5 extiende las nociones de -Cent-Dian y Centro- Generalizado, ya existentes en Teoría de Localización de Instalaciones, al área de Diseño de Redes. Los problemas tratados en este capítulo están enfocados para diseñar red