A Heuristic Algorithm for the Allocation of Airport Runway System Capacity

Abstract

This paper develops a heuristic algorithm for the allocation of airport runway capacity to minimise the cost of arrival and departure aircraft/flight delays. The algorithm is developed as a potential alternative to optimisation models based on linear and integer programming. The algorithm is based on heuristic (‘greedy’) criteria that closely reflect the ‘rules of thumb’ used by air traffic controllers. Using inputs such as arrival and departure demand, airport runway system capacity envelopes and cost of aircraft/flight delays, the main output minimises the cost of arrival and departure delays as well as the corresponding interdependent airport runway system arrival and departure capacity allocation. The algorithm is applied to traffic scenarios at three busy US airports. The results are used to validate the performance of the proposed heuristic algorithm against results from selected benchmarking optimisation models.     

Dynamic airspace sectorisation for flight-centric operations

Today’s air traffic operations follow the paradigm of ‘flow follows structure’, which already limits the operational efficiency and punctuality of current air traffic movements. Therefore, we introduce the dynamic airspace sectorisation and consequently change this paradigm to the more appropriate approach of ‘structure follows flow’. The dynamic airspace sectorisation allows an efficient allocation of scarce resources considering operational, economic and ecological constraints in both nominal and variable air traffic conditions. Our approach clusters traffic patterns and uses evolutionary algorithms for optimisation of the airspace, focusing on high capacity utilisation through flexible use of airspace, appropriate distribution of task load for air traffic controllers and fast adaptation to changed operational constraints. We thereby offer a solution for handling non-convex airspace boundaries and provide a proof of concept using current operational airspace structures and enabling a flight-centric air traffic management. We are confident that our developed dynamic airspace sectorisation significantly contributes to the challenges of future airspace by providing appropriate structures for future 4D aircraft trajectories taking into account various operational aspects of air traffic such as temporally restricted areas, limited capacities, zones of convective weather or urban air mobility. Dynamic sectorisation is a key enabling technology in the achievement of the ambitious goals of Single European Sky and Flightpath 2050 through a reduction in coordination efforts, efficient resource allocation, reduced aircraft emissions, fewer detours, and minimisation of air traffic delays.     

Closing the loop in real-time railway control: Framework design and impacts on operations

Railway traffic is heavily affected by disturbances and/or disruptions, which are often cause of delays and low performance of train services. The impact and the propagation of such delays can be mitigated by relying on automatic tools for rescheduling traffic in real-time. These tools predict future track conflict based on current train information and provide suitable control measures (e.g. reordering, retiming and/or rerouting) by using advanced mathematical models. A growing literature is available on these tools, but their effects on real operations are blurry and not yet well known, due to the very scarce implementation of such systems in practice.In this paper we widen the knowledge on how automatic real-time rescheduling tools can influence train performance when interfaced with railway operations. To this purpose we build up a novel traffic control framework that couples the state-of-the art automatic rescheduling tool ROMA, with the realistic railway traffic simulation environment EGTRAIN, used as a surrogate of the real field. At regular times ROMA is fed with current traffic information measured from the field (i.e. EGTRAIN) in order to predict possible conflicts and compute (sub) optimal control measures that minimize the max consecutive delay on the network. We test the impact of the traffic control framework based on different types of interaction (i.e. open loop, multiple open loop, closed loop) between the rescheduling tool and the simulation environment as well as different combinations of parameter values (such as the rescheduling interval and prediction horizon). The influence of different traffic prediction models (assuming e.g. aggressive versus conservative driving behaviour) is also investigated together with the effects on traffic due to control delays of the dispatcher in implementing the control measures computed by the rescheduling tool.Results obtained for the Dutch railway corridor Utrecht–Den Bosch show that a closed loop interaction outperforms both the multiple open loop and the open loop approaches, especially with large control delays and limited information on train entrance delays and dwell times. A slow rescheduling frequency and a large prediction horizon improve the quality of the control measure. A limited control delay and a conservative prediction of train speed help filtering out uncertain traffic dynamics thereby increasing the effectiveness of the implemented measures.     

Ground delay program planning under uncertainty in airport capacity

Abstract

This paper presents an algorithm for assigning flight departure delays under probabilistic airport capacity. The algorithm dynamically adapts to weather forecasts by revising, if necessary, departure delays. The proposed algorithm leverages state-of-the-art optimization techniques that have appeared in recent literature. As a case study, the algorithm is applied to assigning departure delays to flights scheduled to arrive at San Francisco International Airport in the presence of uncertainty in the fog clearance time. The cumulative distribution function of fog clearance time was estimated from historical data. Using daily weather forecasts to update the probabilities of fog clearance times resulted in improvement of the algorithm's performance. Experimental results also indicate that if the proposed algorithm is applied to assign ground delays to flights inbound at San Francisco International airport, overall delays could be reduced up to 25% compared to current level.     

A framework for the assessment of collaborative en route resource allocation strategies

Airspace Flow Programs (AFPs) assign ground delays to flights in order to limit flow through capacity constrained airspace regions. AFPs have been successful in controlling traffic with reasonable delays, but a new program called the Combined Trajectory Options Program, or CTOP, is being explored to further accommodate projected increases in traffic demand. In CTOP, centrally managed rerouting and user preference inputs are also incorporated into initial en route resource allocations. We investigate four alternative versions of resource allocation within CTOP in this research, under differing assumptions about the degree of random variability in airline flight assignment costs when measured against a simple model based upon the flight specific, but otherwise fixed, ratio of airborne flight time and ground delay unit cost. Two en route resource allocation schemes are based on ordered assignments that are similar to those used currently, and the other two are system-optimal assignment schemes. One of these system-optimal schemes is based on complete preference information, which is ideal but not realistic, and the other is based on partial information that may be feasible to implement but yields less efficient assignments. The main contribution of this research is a methodological framework to evaluate and compare these alternative en route resource allocation schemes, under varying assumptions about the information traffic managers have been provided about the flight operators’ route preferences. The framework allows us to evaluate these various schemes under differing assumptions about how well the traffic managers’ flight cost model captures flight costs. A numerical example demonstrates that a sequential resource allocation scheme – where flights are assigned resources in the order in which preference information is submitted – can be more efficient than a scheme that offers a cost minimizing allocation based on less complete preference information, and may at the same time be perceived as equitable. We also find that assigning resources in the order flights are scheduled results in less efficient allocations, but more equitable ones.     

Strategic de-confliction in the presence of a large number of 4D trajectories using a causal modeling approach

This paper presents a strategic de-confliction algorithm based on causal modeling developed under the STREAM project and launched under the umbrella of the Single European Sky ATM Research (SESAR) Program. The basic underlying concept makes use of the enriched information included in the Shared Business Trajectories (SBTs) of the flights prior to takeoff (or in the Reference Business Trajectories (RBTs) if the flight is airborne) to allocate conflict-free trajectories in a traffic planning phase that should lead to an actual conflict-free scenario in the flight execution phase in the absence of flight and/or network uncertainties. The proposed approach could decrease the workload of the air traffic controllers, thus improving the Air Traffic Management (ATM) capacity while meeting the maximum possible expectations of the Airspace Users’ requirements in terms of horizontal flight efficiency. The main modules of the implemented system are also presented in this paper; these modules are designed to enable the processing of thousands of trajectories within a few seconds or minutes and encompass a global network scope with a planning horizon of approximately 2–3 h. The causal model applied for network conflict resolution and flight routing allocation is analyzed to demonstrate how the emergent dynamics (i.e., domino effects) of local trajectory amendments can be efficiently explored to identify conflict-free Pareto-efficient network scenarios. Various performance indicators can be taken into account in the multi-criteria optimization process, thus offering to the network manager a flexible tool for fostering a collaborative planning process.     

Research review of air traffic management

As air transport demand keeps growing more quickly than system capacity, efficient and effective management of system capacity becomes essential to the operation of the future global air traffic system. Although research in the past two decades has made significant progress in relevant research fields, e.g. air traffic flow management and airport capacity modelling, research loopholes in air traffic management still exist and links between different research areas are required to enhance the system performance of air traffic management. Hence, the objective of this paper is to review systematically current research in the literature about the issue of air traffic management to prioritize productive research areas. Papers about air traffic management are discussed and categorized into two levels: system and airport. The system level of air transport research includes two main topics: air traffic flow management and airspace research. On the airport level, research topics are: airport capacity, airport facility utilization, aircraft operations in the airport terminal manoeuvring area as well as aircraft ground operations research. Potential research interests to focus on in the future are the integration between airspace capacity and airport capacity, the establishment of airport information systems to use airport capacity better, and the improvement in flight schedule planning to improve the reliability of schedule implementation.     

A probabilistic framework for weather-based rerouting and delay estimations within an Airspace Planning model

In this paper, we develop a novel severe weather-modeling paradigm to be applied within the context of a large-scale Airspace Planning and collaborative decision-making model in order to reroute flights with respect to a specified probability threshold of encountering severe weather, subject to collision safety, airline equity, and sector workload considerations. This approach serves as an alternative to the current practice adopted by the Federal Aviation Administration (FAA) of adjusting flight routes in accordance with the guidelines specified in the National Playbook. Our innovative contributions in this paper include (a) the concept of “Probability-Nets” and the development of discretized representations of various weather phenomena that affect aviation operations; (b) the integration of readily accessible severe weather probabilities from existing weather forecast data provided by the National Weather Service; (c) the generation of flight plans that circumvent severe weather phenomena with specified probability threshold levels, and (d) a probabilistic delay assessment methodology for evaluating planned flight routes that might encounter potentially disruptive weather along its trajectory. Additionally, we conduct an economic benefit analysis using a k-means clustering mechanism in concert with our delay assessment methodology in order to evaluate delay costs and system disruptions associated with variations in probability-net refinement-based information. Computational results and insights are presented based on flight test cases derived from the Enhanced Traffic Management System data provided by the FAA and using weather scenarios derived from the Model Output Statistics forecast data provided by the National Weather Service.     

Predicting the operational acceptance of airborne flight reroute requests using data mining

For tools that generate more efficient flight routes or reroute advisories, it is important to ensure compatibility of automation and autonomy decisions with human objectives so as to ensure acceptability by the human operators. In this paper, the authors developed a proof of concept predictor of operational acceptability for route changes during a flight. Such a capability could have applications in automation tools that identify more efficient routes around airspace impacted by weather or congestion and that better meet airline preferences. The predictor is based on applying data mining techniques, including logistic regression, a decision tree, a support vector machine, a random forest and Adaptive Boost, to historical flight plan amendment data reported during operations and field experiments. Cross validation was used for model development, while nested cross validation was used to validate the models. The model found to have the best performance in predicting air traffic controller acceptance or rejection of a route change, using the available data from Fort Worth Air Traffic Control Center and its adjacent Centers, was the random forest, with an F-score of 0.77. This result indicates that the operational acceptance of reroute requests does indeed have some level of predictability, and that, with suitable data, models can be trained to predict the operational acceptability of reroute requests. Such models may ultimately be used to inform route selection by decision support tools, contributing to the development of increasingly autonomous systems that are capable of routing aircraft with less human input than is currently the case.     

Stochastic optimization models for ground delay program planning with equity–efficiency tradeoffs

Bad weather is a major contributor to air traffic delays. The ration-by-distance algorithm was proposed to increase the efficiency of ground delay program (GDP) planning in situations where there is uncertainty regarding the duration of the weather conditions that motivated the GDP. This algorithm, however, can treat shorter flights unfairly. We describe a two-stage stochastic, multi-objective integer program for GDP planning. This multi-objective approach allows one to balance equity and efficiency. We provide experimental evidence showing the effectiveness of the solutions generated.     

Surrounding traffic complexity analysis for efficient and stable conflict resolution

The constant increase in air traffic demand increases a probability of the separation minima infringements in certain areas as a consequence of increased traffic density. The Annual Safety Report 2016 reports that in recent years the number of infringements, measured per million flight hours, had been increased at a lower rate (Eurocontrol, 2018). However, this level of infringements still generates a continuous pressure on the air traffic control (ATC) system and seeks for more control resources ready to tactically solve potential conflicts, while increasing at the same time the operational costs. Considering present air traffic management (ATM) trade-off criteria: increased airspace capacity and traffic efficiency but reducing the cost while preserving safety, new services must be designed to distribute the separation management ATC task loads among other actors. Based on the Single European Sky Air Traffic Management Research and Next Generation Air Transportation System initiatives, this paper proposes an innovative separation management service to shift the completely centralized tactical ATC interventions to more efficient decentralized tactical operations relying on an advanced surrounding traffic analysis tool, to preserve the safety indicators while considering the operational efficiency. A developed methodology for the proposed service is an application-oriented, trying to respond to characteristics and requirements of the current operational environment. The paper further analysis the traffic complexity taking into consideration the so-called domino effect, i.e. a number of the surrounding aircraft causally involved in the separation management service by the means of identification of the spatiotemporal interdependencies between them and the conflicting aircraft. This complexity is driven by the interdependencies structure and expressed as a time-criticality in quantifying the total number of the system solutions, that varies over time as the aircraft are approaching to each other. The results from two randomly selected ecosystem scenarios, extracted from a simulated traffic, illustrate different avoidance capacities for a given look-ahead time and the system solutions counts, that in discrete moments reach zero value.     

Flight delays,capacity investment and social welfare under air transport supply-demand equilibrium

This paper analyzes benefits from aviation infrastructure investment under competitive supply-demand equilibrium. The analysis recognizes that, in the air transportation system where economies of density is an inherent characteristic, capacity change would trigger a complicated set of adjustment of and interplay among passenger demand, air fare, flight frequency, aircraft size, and flight delays, leading to an equilibrium shift. An analytical model that incorporates these elements is developed. The results from comparative static analysis show that capacity constraint suppresses demand, reduces flight frequency, and increases passenger generalized cost. Our numerical analysis further reveals that, by switching to larger aircraft size, airlines manage to offset part of the delay effect on unit operating cost, and charge passengers lower fare. With higher capacity, airlines tend to raise both fare and frequency while decreasing aircraft size. More demand emerges in the market, with reduced generalized cost for each traveler. The marginal benefit brought by capacity expansion diminishes as the capacity-demand imbalance becomes less severe. Existing passengers in the market receive most of the benefit, followed by airlines. The welfare gains from induced demand are much smaller. The equilibrium approach yields more plausible investment benefit estimates than does the conventional method. In particular, when forecasting future demand the equilibrium approach is capable of preventing the occurrence of excessive high delays.     

Adaptive cruise control design for active congestion avoidance

We present an adaptive cruise control (ACC) strategy where the acceleration characteristics, that is, the driving style automatically adapts to different traffic situations. The three components of the concept are the ACC itself, implemented in the form of a car-following model, an algorithm for the automatic real-time detection of the traffic situation based on local information, and a strategy matrix to adapt the driving characteristics (that is, the parameters of the ACC controller) to the traffic conditions. Optionally, inter-vehicle and infrastructure-to-car communication can be used to improve the accuracy of determining the traffic states. Within a microscopic simulation framework, we have simulated the complete concept on a road section with an on-ramp bottleneck, using empirical loop-detector data for an afternoon rush-hour as input for the upstream boundary. We found that the ACC vehicles improve the traffic stability and the dynamic road capacity. While traffic congestion in the reference scenario was completely eliminated when simulating a proportion of 25% ACC vehicles, travel times were already significantly reduced for much lower penetration rates. The efficiency of the proposed driving strategy even for low market penetrations is a promising result for a successful application in future driver assistance systems.     

Do cooperative systems make drivers’ car-following behavior safer?

The main goal of in-vehicle technologies and co-operative services is to reduce congestion and increase traffic safety. This is achieved by alerting drivers on risky traffic conditions ahead of them and by exchanging traffic and safety related information for the particular road segment with nearby vehicles. Road capacity, level of service, safety, and air pollution are impacted to a large extent by car-following behavior of drivers. Car-following behavior is an essential component of micro-simulation models. This paper investigates the impact of an infrastructure-to-vehicle (I2V) co-operative system on drivers’ car-following behavior. Test drivers in this experiment drove an instrumented vehicle with and without the system. Collected trajectory data of the subject vehicle and the vehicle in front, as well as socio-demographic characteristics of the test drivers were used to estimate car-following models capturing their driving behavior with and without the I2V system. The results show that the co-operative system harmonized the behavior of drivers and reduced the range of acceleration and deceleration differences among them. The observed impact of the system was largest on the older group of drivers.     

航班快速恢复建模与仿真研究

随着民用航空的发展与竞争,航班延误不仅影响航空飞行的安全与正常,更与航空公司的运营效率、运营成本及乘客利益息息相关。针对某一恶劣天气影响,对某公司受影响航班进行重新调配,考虑到航班的备降、盘旋等待、延误、取消等多种状态,以总成本最小为目标函数,建立航班快速恢复模型,通过MATLAB运用遗传算法设计航班恢复算法进行求解,得出最经济的航班恢复方案。     

Prediction of travel time variability for cost-benefit analysis

Unreliable travel times cause substantial costs to travelers. Nevertheless, they are often not taken into account in cost-benefit analyses (CBA), or only in very rough ways. This paper aims at providing simple rules to predict variability, based on travel time data from Dutch highways. Two different concepts of travel time variability are used, which differ in their assumptions on information availability to drivers. The first measure is based on the assumption that, for a given road link and given time of day, the expected travel time is constant across all working days (rough information: RI). In the second case, expected travel times are assumed to reflect day-specific factors such as weather conditions or weekdays (fine information: FI). For both definitions of variability, we find that the mean travel time is a good predictor. On average, longer delays are associated with higher variability. However, the derivative of variability with respect to delays is decreasing in delays. It can be shown that this result relates to differences in the relative shares of observed traffic ‘regimes’ (free-flow, congested, hyper-congested) in the mean delay. For most CBAs, no information on the relative shares of the traffic regimes is available. A non-linear model based on mean travel times can then be used as an approximation.     

An efficient algorithm for smoothing airspace congestion by fine-tuning take-off times

Current technological advances in communications and navigation have improved air traffic management (ATM) with new decision support tools to balance airspace capacity with user demands. Despite agreements achieved in flying reference business trajectories (RBTs) among different stakeholders, tight spatio-temporal connectivity between trajectories in dense sectors can cause perturbations that might introduce time or space deviations into the original RBTs, thus potentially affecting other 4D trajectories. In this paper, several challenging results are presented by properly tuning the Calculated Take-Off Times (CTOTs) as a tool for mitigating the propagation of perturbations between trajectories that can readily appear in dense sectors. Based on the identification of “collective microregions”, a tool for predicting potential spatio-temporal concurrence events between trajectories over the European airspace was developed, together with a CTOT algorithm to sequence the departures that preserve the scheduled slots while relaxing tight trajectory interactions. The algorithm was tested by considering a realistic scenario (designed and analyzed in the STREAM project (Stream, 2013)) to evaluate relevant ATM KPIs that provide aggregated information about the sensitivity of the system to trajectory interactions, taking into account the system dynamics at a network level. The proposed approach contributes to enhancing the ATM capacity of airports to mitigate network perturbations.     

An environmental assessment of air traffic speed constraints in the departure phase of flight: A case study at Gothenburg Landvetter Airport,Sweden

This paper considers the environmental effects of air traffic management speed constraints during the departure phase of flight. We present a CO₂ versus noise trade-off study that compares aircraft departure procedures subject to speed constraints with a free speed scenario. A departure route at Gothenburg Landvetter Airport in Sweden is used as a case study and the analysis is based on airline flight recorded data extracted from the Airbus A321 aircraft. Results suggest that CO₂ emissions could be reduced by 180 kg per flight if all departure speed constraints were removed at a cost of increased noise exposure below 70 dB(A).     

Urban traffic studies from aerial photographs

Two problems concerning the use of aerial photographs for conducting traffic studies in urban areas are considered in this paper: (1) Suitable procedures requiring simple equipment and methods and the appropriate formulae for determining the traffic characteristics of density, volume, traffic count, speed, composition; (2) Problems relating to flight planning for traffic surveys from the points of view of duration of photography and the scale of the photography from considerations of the reliability of the determined traffic characteristics, vehicle identification, and also economy. The conclusions concerning the flight planning were applied in a test flight from which traffic data were determined as illustrated in a sample calculation.