Search

Mención Internacional en el título de doctor In this thesis we address the problem of Air Traffic Flow Management (ATFM). In brief, this problem consists of finding optimal schedules and routes for a set of flights in such a way that, when the flight plans are executed, no region of the airspace has more aircraft flying over it than allowed by security restrictions. Likewise, no airport should be assigned more departures or arrivals than it can handle. In the thesis, continuing a research line originated some decades ago, we cope with this problem using mathematical optimization. The thesis content is organized as follows. In Chapter 2 we give a detailed description of the ATFM problem and review some of the most recent works that also employ mathematical programming to tackle the problem. The chapter also contains our modeling proposals for the ATFM problem. These consist of two new and equivalent 0-1 mathematical programming formulations. The formulations are shown to be an easy way to model different complex situations arising in practice, and permit to solve some limitations of the state-of-the-art models. The chapter concludes presenting a novel methodology to detect, beforehand, routes that will be part of the optimal solution. In Chapter 3 we generalize some of the results obtained in Chapter 2. Concretely, we introduce a family of shortest path problems that, to the best of our knowledge, has not been previously investigated: the Shared Resource Constrained Multi-Shortest Path Problem. In the chapter we show how to use this family of shortest path problems to solve some type of project scheduling problems. This way, the results obtained in the previous chapter for the ATFM problem are extended to a broader family of scheduling problems. In Chapter 3 we also discuss two different solution methods for the family of shortest path problems presented. The first method consists of a matheuristic algorithm, while the second one is based on two Lagrangian Relaxations of the problem. Chapter 4 contains an extensive computational experience to validate the results presented in the previous chapters. Moreover, the chapter includes the creation of ATFM instances which have been released for free disposal. Finally, in Chapter 5 we summarize the main conclusions and contributions accomplished in the thesis. Future lines of research that this work opens are also discussed there. En esta tesis tratamos el problema de la Gestión de Flujo del Tráfico Aéreo (ATFM). De manera breve, este problema consiste en encontrar una planificación temporal y de rutas óptima para un conjunto de vuelos de manera que, cuando se ejecuten los planes de vuelo, ninguna región del espacio aéreo tenga más aeronaves volando sobre ella que las permitidas por las restricciones de seguridad. Asimismo, no se debe asignar a ningún aeropuerto más salidas o llegadas de las que pueda manejar. En la tesis, continuando una línea de investigación originada hace algunas décadas atrás, abordamos este problema mediante optimización matemática. El contenido de la tesis está organizado de la siguiente manera. En el capítulo 2 damos una descripción detallada del problema del ATFM y revisamos algunos de los trabajos más recientes que también emplean optimización matemática para abordar el problema. El capítulo también contiene nuestras propuestas de modelización para el problema del ATFM. Estas consisten en dos nuevas y equivalentes formulaciones 0-1 de optimización matemática. En el capítulo se muestra como dichas formulaciones permiten modelar de manera sencilla diferentes situaciones complejas que surgen en la práctica, y cómo permiten resolver algunas limitaciones de los modelos que conforman el estado del arte. El capítulo concluye presentado una nueva metodología para detectar, de antemano, rutas que formarán parte de la solución óptima. En el capítulo 3 generalizamos algunos de los resultados obtenidos en el capítulo 2. Concretamente, introducimos una familia de problemas de camino mínimo que, hasta nuestro entender, no ha sido investigada previamente: el problema de múltiples caminos mínimos con recursos compartidos y restringidos. En el capítulo mostramos cómo usar esta familia de problemas de camino mínimo para resolver algunos problemas de planificación de proyectos. De esta manera, los resultados obtenidos en el capítulo anterior para el problema del ATFM se extienden a una familia más amplia de problemas de planificación. En el capítulo 3 también presentamos dos métodos de resolución diferentes para la familia de problemas de camino mínimo presentada. El primer método consiste en un algoritmo matheurístico, mientras que el segundo se basa en dos Relajaciones Lagrangianas del problema. El capítulo 4 contiene una extensa experiencia computacional para validar los resultados presentados en los capítulos anteriores. Además, el capítulo incluye la creación de instancias para el problema del ATFM que han sido liberadas para su libre disposición. Finalmente, en el capítulo 5 resumimos las principales conclusiones y contribuciones realizadas en la tesis. También se discuten las futuras líneas de investigación que este trabajo abre. This research was partially funded by projects MTM2015-63710-P and RTI2018-094269-B-I00 (A. Alonso-Ayuso and D. García-Heredia) from the Government of Spain. Programa de Doctorado en Ingeniería Matemática por la Universidad Carlos III de Madrid Presidente: Laureano F. Escudero Bueno.- Secretario: Francisco Javier Prieto Fernández.- Vocal: Sergio García Quiles

Constraint Satisfaction Problems (CSP) belong to a kind of traditional NP-hard problems with a high impact on both research and industrial domains. The goal of these problems is to find a feasible assignment for a group of variables where a set of imposed restrictions is satisfied. This family of NP-hard problems demands a huge amount of computational resources even for their simplest cases. For this reason, different heuristic methods have been studied so far in order to discover feasible solutions at an affordable complexity level. This paper elaborates on the application of Ant Colony Optimization (ACO) algorithms with a novel CSP-graph based model to solve Resource-Constrained Project Scheduling Problems (RCPSP). The main drawback of this ACO-based model is related to the high number of pheromones created in the system. To overcome this issue we propose two adaptive Oblivion Rate heuristics to control the number of pheromones: the first one, called Dynamic Oblivion Rate, takes into account the overall number of pheromones produced in the system, whereas the second one inspires from the recently contributed Coral Reef Optimization (CRO) solver. A thorough experimental analysis has been carried out using the public PSPLIB library, and the obtained results have been compared to those of the most relevant contributions from the related literature. The performed experiments reveal that the Oblivion Rate heuristic removes at least 79% of the pheromones in the system, whereas the ACO algorithm renders statistically better results than other algorithmic counterparts from the literature.