Search

We consider a stochastic, dynamic runway scheduling problem involving aircraft landings on a single runway. Sequencing decisions are made with knowledge of the estimated arrival times (ETAs) of all aircraft due to arrive at the airport, and these ETAs vary according to continuous-time stochastic processes. Time separations between consecutive runway landings are modeled via sequence-dependent Erlang distributions and are affected by weather conditions, which also evolve continuously over time. The resulting multistage optimization problem is intractable using exact methods, and we propose a novel simheuristic approach based on the application of methods analogous to variable neighborhood search in a high-dimensional stochastic environment. Our model is calibrated using flight tracking data for over 98,000 arrivals at Heathrow Airport. Results from numerical experiments indicate that our proposed simheuristic algorithm outperforms an alternative based on deterministic forecasts under a wide range of parameter values, with the largest benefits seen when the underlying stochastic processes become more volatile and also when the on-time requirements of individual flights are given greater weight in the objective function. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/M020258/1]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/trsc.2022.0400. [ABSTRACT FROM AUTHOR]

In response to the intricate interplay of uncertain factors within the airport system, which leads to challenges in predicting and optimizing departure operations in the airport, this study investigates a probabilistic prediction of operation times for departure flights, as well as an integrated stochastic optimized scheduling method considering multiple resources on the airport surface under the impact of these uncertain operation times. A probabilistic predictive model for departure operations is formulated, employing a combination of random forest regression and kernel density estimation. This model was used to obtain the prediction results of the probabilistic distribution of various departure operation times under uncertainty. Chance constraints are introduced to control the stability of the scheduling strategies including the push back time and takeoff time scheduling. Taking minimizing operational delays and maximizing the probability of satisfying the chance constraints as the optimization objectives, a comprehensive integrated stochastic scheduling model is developed for airport departure operations under uncertainty. Lastly, the method is validated and analyzed using Kunming Changshui International Airport as a case study. Experimental results firstly demonstrate that the proposed method is capable of effectively predict the probability distributions of estimated push back times and taxi times for departure flights. The continuous ranked probability scores of the estimated push back times and taxi times are 9.25 and 1.21 respectively, indicating that the estimated push back times of the departure flights is more uncertain than the taxi times. Then, results of the integrated airport surface departure scheduling model show that the model can comprehensively consider the minimization of flight delays and the satisfaction of the two chance constraints, and obtain the Pareto optimal solutions achieving balance between strategy efficiency and strategy stability.

With the rapid development of air transportation, the surface management of large airports has become more complicated. This paper proposes an integrated scheduling model of arrival aircraft (ISAA), in which complex constraints related to runway restrictions, gate assignment and taxiway conflicts are incorporated. With the aim of reducing the total passenger runway delay, passenger taxi delay, and passenger swap cost, the model is built as a set partition model. We propose various neighbourhood search (VNS) algorithm for solving the problem. A variable neighbourhood descent (VND) as local search is integrated into the general variable neighbourhood framework. This method is compared with a sequential method that solves runway sequencing, gate reassignment and taxiway scheduling problem separately. Numerical results based on Nanjing Lukou Internation Airport indicate that, although the swap cost for gate reassignment is slightly increased, the whole performance is significantly improved. [ABSTRACT FROM AUTHOR]

The rapid growth of the airline industry has caused an enormous demand in the context of air transport and air traffic congestion in several hub airports. In order to alleviate this situation and resolve the imbalance between the arrival and departure rate, efficient runway usage in airport capacity management is an immediate and feasible solution as compared to airport expansion and runway construction. Air Traffic Control (ATC) operators could optimize their runway capacity by operating dynamic runway configuration in switch-mode runways based on the air and airport traffic conditions. A semi-mixed mode runway is considered in this paper, wherein some runways are configured for either landing or take-off operations, while others are operated in switch mode. The demand for arrival and departure is subject to the passenger's demand, flight availability, and timings, preferred flight schedule, and frequency of flight schedule service, and usually vary in different hours (peak and nonpeak hours). Given this feature, ATC can reconfigure the runway mode responding to the current demand for arrival and departure and further seize the runway capacity via a systematic approach. Under the semi-mixed mode situation, formulating the coordination of dynamic runway configuration planning and the Aircraft Sequencing and Scheduling Problem is proposed. The air traffic pattern in Hong Kong International Airport (HKIA) is used as a test case to evaluate the performance of this proposed model. Based on the test results, it was found that this dynamic runway configuration planning and semi-mixed runway design can utilize runway capacity more efficiently. In the numerical study, the dynamic runway configuration planning achieved 71.6%% and 37.08% reduction of flight tardiness than the two segregated runway systems (two landings and one take-off runways and one landing and two take-off runways) in HKIA. [ABSTRACT FROM AUTHOR]

Air traffic flow management is one of the most important operations in terminal airports heavily relying on advanced intelligence transportation techniques. This work considers a two-stage runway scheduling problem given a set of flights with uncertain arrival times. The first-stage problem is to identify a sequence of aircraft weight classes (e.g., Heavy, Large and Small) that minimizes runway occupying time (i.e., makespan). Then the second-stage decision is dedicated to scheduling the flights as punctually as possible after their arrival times realized, which translates into determining a sequence of flights for each aircraft category such that the total deviation time imposed on the flights is minimized. Instead of an exactly known probability distribution, information on uncertain parameters is limited (i.e., ambiguous), such as means, mean absolute deviations and support set of random parameters derived from historical data. Under this information on the random parameters, an ambiguous mixed-integer stochastic optimization model is proposed. For such a problem, we approximately construct a worst-case discrete probability distribution with three possible realizations per random parameter, and adopt a hybrid sample average approximation algorithm in which genetic algorithms are used to replace commercial solvers. To illustrate the effectiveness and efficiency of the proposed model and algorithm, extensive numerical experiments are carried out.

Runway systems are among the most stringent bottlenecks at global hub airports, which have been identified as a major source of airport inefficiency. Runway system inefficiencies are manifested in multiple dimensions such as delay, throughput reduction and excessive emission, whose tradeoffs are investigated in this paper as part of an airport runway scheduling problem in the presence of uncertainty. We formulate a multi-objective optimization model aiming to minimize flight delays, maximize airport throughput, and minimize aircraft emissions, subject to a variety of constraints such as minimum separation, time window, runway occupancy and flight turnaround. The computational performance is enhanced with an efficient multi-objective evolutionary algorithm, with two mechanisms of adaptive and controllable time-coding and objective-guided individual selection. The proposed method is flexible in adjusting conservatism when it comes to optimization with uncertainty, and offers a set of Pareto optimal solutions for different stakeholders without using scalarization of different objectives. A real-world case study is carried out for one of the world's buiest airports, Shanghai Pudong, under the case of 2 runways, 2 operation types, 12 uncertain conditions and 4 tradeoff scenarios. The computational results show that the proposed optimized method has overall advantages in improving the runway scheduling performance over some meta-heuristics and the First Come First Served strategy. The tradeoff analysis reveals that the minimum delay schedule is preferable for balancing delay, throughtput and emission. The findings provide managerial insights regarding traffic management measures for different stakeholders at high-density airports. [ABSTRACT FROM AUTHOR]

Runway scheduling deals with the sequencing of arriving and departing aircraft at airports such that a predefined objective is optimized subject to several operational constraints. Different from the existing deterministic approaches in the literature, we consider a new approach to the stochastic version of this problem within the general context of machine scheduling problems. As part of our analysis, we first show that a restricted version of the stochastic runway-scheduling problem is equivalent to a machine-scheduling problem on a single machine with sequence-dependent setup times and stochastic due dates. We then extend this restricted model by considering characteristics specific to the runway-scheduling problem and present two different stochastic integer programming models. We derive some tight valid inequalities for these formulations and propose a solution methodology based on sample average approximation and Lagrangian-based scenario decomposition. Realistic data sets are then used to perform a detailed computational study involving implementations and analyses of several different configurations of the models. The results from the computational tests indicate that truncated versions of the proposed solution algorithm, where the best solution is reported after short run times, almost always produce very high-quality solutions, implying that the proposed stochastic approach to runway scheduling is likely to be practically implementable with potential value over current practice or deterministic models. The online appendix is available at https://doi.org/10.1287/trsc.2017.0784. [ABSTRACT FROM AUTHOR]

In addition to time efficiency, minimisation of fuel consumption and related emissions has started to be considered by research on optimisation of airport surface operations as more airports face severe congestion and tightening environmental regulations. Objectives are related to economic cost which can be used as preferences to search for a region of cost efficient and Pareto optimal solutions. A multi-objective evolutionary optimisation framework with preferences is proposed in this paper to solve a complex optimisation problem integrating runway scheduling and airport ground movement problem. The evolutionary search algorithm uses modified crowding distance in the replacement procedure to take into account cost of delay and fuel price. Furthermore, uncertainty inherent in prices is reflected by expressing preferences as an interval. Preference information is used to control the extent of region of interest, which has a beneficial effect on algorithm performance. As a result, the search algorithm can achieve faster convergence and potentially better solutions. A filtering procedure is further proposed to select an evenly distributed subset of Pareto optimal solutions in order to reduce its size and help the decision maker. The computational results with data from major international hub airports show the efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

In a typical aviation environment today, the precise landing times of en route aircraft are not set until each aircraft approaches the airspace adjacent to the destination airport. In times of congestion, it is not unusual for air traffic controllers to subject arriving aircraft to various maneuvers so as to create an orderly flow of aircraft onto an arrival runway. Typical maneuvers might include flying in zigzag patterns and flying in circular holding patterns, as well as others. These maneuvers serve to delay the arrival time of the flight. On the other hand, if the arrival time was established much earlier, then that delay could be realized by having the aircraft fly slower while still at a higher altitude, which would burn much less fuel than the described maneuvers. Three integer programming models are proposed to assign delay to aircraft approaching a single airport, well in advance of each aircraft's entry into the terminal airspace. The baseline model is deterministic and seeks to maximize the available throughput at the runway over a rolling horizon. The latter two models are stochastic and account for uncertainty regarding the status and controllability of certain flights. The first stochastic model is scenario based, while the second relies on a functional approximation of uncertainty. The results of computational experiments show that these approaches can transfer a considerable portion of the delay that would otherwise occur in the terminal area to the en route phase of flight, and also that the stochastic models are noticeably more effective. The model relying on functional approximation shows particular promise because of its efficient run time. The delay transfer yielded by each model resulted in significant predicted fuel savings. The functional approximation model performed particularly well under declining operational conditions, demonstrating itself to be a promising means of achieving delay transfer. [ABSTRACT FROM AUTHOR]

At busy airports, air traffic controllers seek to find schedules for aircraft at the runway that aim to minimize delays of the aircraft while maximizing runway throughput. In reality, finding optimal schedules by a human controller is hard to accomplish since the number of feasible schedules available for the scheduling problem is quite large. In this paper, we pose this problem as a multiobjective optimization problem, with respect to total aircraft delay and runway throughput. Using principles of multiobjective dynamic programming, we develop an algorithm to find a set of Pareto-optimal solutions that completely specify the nondominated frontier. In addition to finding these solutions, this paper provides a proof of the algorithm's correctness and gives an analysis of its performance against a baseline algorithm using the operational data for a model of the Dallas/Fort Worth International Airport. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of allocating pushback times to departing aircraft, specifying the time at which they will be given permission to push back from their allocated stand, start their engines, and commence their taxi to the runway. The aim of this research is to first predict the delay (defined as the waiting time at the stand or runway) for each departure, then to use this to calculate a pushback time such that an appropriate amount of the delay is absorbed at the stand, prior to starting the engines. A two-stage approach is used, where the feasibility of the second stage (pushback time allocation) has to be considered within the first stage (takeoff sequencing). The characteristics of this real-world problem and the differences between it and similar problems are thoroughly discussed, along with a consideration of the important effects of these differences. Differences include a nonlinear objective function with a nonconvex component; the integration of two sequence dependent separation problems; separations that can vary over time; and time-slot extensions. Each of these factors has contributed to the design of the solution algorithm. Results predict significant fuel-burn benefits from absorbing some of the delay as stand hold, as well as delay benefits from indirectly aiding the runway controllers by reducing runway queue sizes. A system for pushback time allocation at London Heathrow has been developed by NATS (formerly National Air Traffic Services) based upon the algorithm described in this paper. [ABSTRACT FROM AUTHOR]

This paper describes recent research into the departure process at London Heathrow, with the primary motivation of reducing the amount of fuel used, improving both the economic and environmental costs. Two proposals are considered here. The first proposal considers the practicality and potential benefits of aiding the controller in improving the take-off sequencing. The second proposal aims to absorb some of the inevitable delay for aircraft at the stands, before the engines are started, but also involves a take-off sequencing aspect. Models for the two take-off sequencing problems are presented in this paper, the second of which includes an additional pushback time (or TSAT) allocation sub-problem which has to be solved subsequently. These models have distinctive differences from the models for the take-off and arrival sequencing problems which are usually considered in the literature, since they take into account necessary constraints imposed due to the control problem (whether a sequence can actually be achieved, and how) in each case. As discussed in this paper, the control problem cannot be ignored by the controllers at Heathrow, and so it cannot be ignored by any realistic system to aid them in their tasks. Comparative take-off sequencing results are presented for the two systems, and the potential benefits from providing decision support to the runway controllers or improved TSAT allocation at the stands are considered. The paper ends with some overall conclusions from the research, showing the large potential benefits of these systems. The TSAT allocation system which is discussed in this paper has been developed for implementation at London Heathrow as one element of a major project which focuses upon collaborative decision making. [ABSTRACT FROM AUTHOR]