Real-time flight scheduling for optimal air traffic flow management

Abstract

Inherent uncertainties of the air transportation system can induce unexpected anomalies in its operations such as deviations in flight schedules, sudden imbalances of demands and capacities, higher workload for Air Traffic Controllers (ATCos), etc. Current Air Traffic Flow Management (ATFM) models rarely consider uncertainty in their algorithms, and generally focus on minimizing the flight delays under deterministic constraints. Thus, to bridge this gap, the thesis proposes several frameworks for en-route ATFM, while scrutinizing different uncertainty components present in air transportation system. Generally, uncertainty exists in two major forms, i.e., capacity uncertainty and demand uncertainty, which result in the stochastic behavior of the Air Traffic Network (ATN).

Demand uncertainty is one critical form, which has an adverse effect on ATFM. It is mainly due to the deviation in departure time and aircraft speed from their scheduled values, and can further lead to an unexpected arrival of aircraft at certain routes at unscheduled times, causing unanticipated demands for those routes. The uncertainty of demand imposes several difficulties in air transportation systems, including higher workloads for air traffic controllers, higher delays, travel costs, as well as safety risks. Thus, in the initial part of the thesis, we propose a preliminary flight routing and scheduling scheme, while considering both departure and speed uncertainties present in ATN. Following robust optimization, we ensure that capacity violations are eliminated from the system while maintaining the required in-trail separation between aircraft even under the uncertainty of demand.

Similar to the demand, the uncertainty of capacity is also another critical form of uncertainty present in air transportation system, and it is primarily due to unexpected weather situations, emergency conditions, controller workload variations, etc. Thus, in this thesis, we further propose a framework for en-route ATFM, while scrutinizing uncertainties in en-route capacity and demand and their imbalance, via a chance constraint-based probabilistic approach. The proposed framework plays a key role in ensuring the safety of the overall air transportation system in terms of maintaining the safety separation between flights and constraining the capacity of the sectors as well. Moreover, a flight level assignment and a speed optimization scheme are proposed based on the Base of Aircraft Data (BADA) of the European Organization for the Safety of Air Navigation (EUROCONTROL) with the objective of minimizing the fuel consumption. The model further minimizes the overall expected delay of the network using the control actions of ground holding, speed control, rerouting, and flight cancellations. At the implementation stage, two phases of ATFM, i.e., the pre-tactical phase and tactical phase, are considered, in which the former focuses on generating optimal trajectories, and the latter focuses on real-time updates of flight plans.

However, due to the flight-by-flight structure, the above models scale poorly for large-scale systems. To overcome this drawback, especially anticipating the high volume of air traffic in the future, we finally present a two-stage architecture, in which the first stage scrutinizes the behavior of a set of flights as a flow, while the second stage decomposes them into individual flight plans. Due to the flow-based modeling structure at the first stage, it enhances the scalability while taking into account constraints of the link, sector and airport capacities and also the waypoint flow rate. The second stage ensures that the flights are safely separated with the required in-trail separation, thus, enhances the safety of the overall system.

Acknowledging the importance of computational complexity along with the optimality, several solution approaches are proposed for above optimization problems, which are primarily base on the concept of maximum independent set, in which the overall problem is decomposed into a set of subproblems based on their independence, and further optimized parallelly resembling a greedy approach, yet with a tighter closeness to the global optimality. Furthermore, each ATFM framework is evaluated in terms of flight delays and possible conflicts with simplified and realistic case studies.