Exact and metaheuristic approaches for network desing problems

• Autores: Natividad González Blanco
• Directores de la Tesis: Juan Antonio Mesa López-Colmenar (dir. tes.) , Bernard Fortz (dir. tes.)
• Lectura: En la Universidad de Sevilla ( España ) en 2023
• Idioma: inglés
• Número de páginas: 211
• Enlaces
  • Tesis en acceso abierto en: Idus
• Resumen
  • español

    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 redes que minimicen la distancia máxima de un conjunto de pares de demanda conocido (dentro de esa red), la distancia promedio, una combinación lineal de ambos objetivos o la diferencia entre ellos. Estos objetivos pueden ser de interés para algunas de las necesidades existentes en la actualidad. Todos los problemas han sido abordados desde el punto de vista de la Programación Matemática. Cada uno de ellos ha sido descrito en detalle y se han encontrado algunas propiedades. Luego, se han propuesto formulaciones. Posteriormente, desde una perspectiva computacional, se han desarrollado métodos de preprocesamiento antes de centrarnos en los procedimientos de resolución. La investigación aquí realizada también se puede agrupar por la naturaleza de los métodos de resolución utilizados para abordar los problemas propuestos. Por un lado, se han desarrollado algunas estabilizaciones para el método de descomposición de Benders. Por otro lado, también se han considerado enfoques metaheurísticos para algunos de los problemas en cuestión. Se han evaluado procedimientos elaborados por otros autores: un GRASP (Greedy Randomized Adaptive Search Procedure), de tipo búsqueda adaptativa con aleatoriedad, y un algoritmo genético. Además, hemos desarrollado un algoritmo de recocido simulado (Simulated Annealing) y otro algoritmo de búsqueda adaptativa en el caso en el que se consideran vecindarios de gran tamaño (Adaptive Large Neighborhood Search).

  • English

    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 the needs at the present time. All problems are approached from the standpoint of Mathematical Programming. Each of them has been described in detail and some properties have been found. Then, formulations have been proposed. Afterwards, from a computational perspective, preprocessing methods have been developed before focusing on the resolution procedures. The research done can also be grouped by the nature of the resolution methods used to tackle the problems proposed. On the one hand, some stabilizations for the Benders decomposition method have been developed. On the other hand, metaheuristic approaches have been also considered for some of the problems concerned. In this situation, Greedy Randomized Adaptive Search Procedures and a Genetic Algorithm elaborated by other authors are evaluated. Furthermore, we have developed a Simulated Annealing and an Adaptive Large Neighborhood Search routine.