An integer optimization framework for future air traffic flow management

• Main Author: Diao, Xudong
• Other Authors: Mao Jianfeng
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Science::Mathematics::Applied mathematics::Optimization
• Online Access: https://hdl.handle.net/10356/69272
• Institution: Nanyang Technological University

In this thesis, an integer optimization framework for future Air Traffic Flow Management (ATFM) is proposed. Here we address three major issues in ATFM systems: a) flexible rerouting operations, b) new airspace structure with large capacity, and c) efficient solution methodologies. All these issues focus on improving capacity and predictability of Air Traffic Management (ATM) systems while reducing various types of costs under safety considerations, which is the fundamental requirement of the future ATFM systems. In the first part of this dissertation, we propose a binary integer optimization model to address the complex practical ATFM rerouting problem on a flight-by-flight basis. In some practical situations, the set of origin-destination (o-d) routes based on sectors must be represented by directed graphs with cycles and the advantage of our model is that it allows the existence of directed graphs with no limitations. Unrestricted directed graph is a type of general structure which allows not only complex o-d routes to be theoretically represented but also preserves global optimal solutions of the ATFM rerouting problem in some specific situations. Optimal traffic flow strategy which includes rerouting, ground-holding, airborne holding and speed control could be obtained directly for each individual flight by solving the model with commercial software. In order to improve the computational performance, we also propose two types of valid inequalities according to the model structure, and these inequalities could reduce solution time very significantly. The computational results indicate that the solution time can be controlled within 5 minutes for instances of a size which is comparable to that of the whole Southeast Asia ATM system. In the second part, we introduce a type of new airspace structure to replace the traditional sector-based structure in order to improve the capacity and predictability of the ATFM system. The new airspace structure could ensure safety separation between flights and improve airspace capacity compared with the traditional airspace structure. Then, we propose a new ATFM model based on the new airspace structure and in the model, operations like rerouting, ground-holding and cancellations are all considered on a flight-by-flight basis. In order to solve the model efficiently, we apply Danzig-Wolfe decomposition to decompose the original model formulation. After that, a distributed heuristic approach based on column generation is developed to generate conflict-free trajectories for each flight under airway entrance capacity constraints. By using commercial optimization software, integer solutions of good quality could be obtained in 20 minutes for the ATFM rerouting problems of the whole Southeast Asia region.