Publication: New models and methods of mathematical optimization in air traffic flow management
Loading...
Identifiers
Publication date
2021-01
Defense date
2021-02-18
Authors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
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.
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.
Description
Mención Internacional en el título de doctor
Keywords
Air traffic flow management, 4D-networks, Matheuristics, 0-1 mathematical optimization model, Shortest path with constrained resources, Project scheduling problems