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
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