New models and methods of mathematical optimization in air traffic flow management

Abstract

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.