A dynamic programming approach for the aircraft landing problem with aircraft classes

Highlights

• This paper considers the aircraft landing problem with multiple runways, positive target landing times, and time windows.

• We assume the set of aircraft to be landed is divided into a (small) number of aircraft classes.

• We provide an exact algorithm to minimize the total delay cost, yielding exact solutions in short time.

• We show the efficiency of our algorithm through a numerical study.

• We outline a possible implementation of our algorithm in a dynamic environment via a rolling horizon approach.

Abstract

The capacity of a runway system represents a bottleneck at many international airports. The current practice at airports is to land approaching aircraft on a first-come, first-served basis. An active rescheduling of aircraft landing times increases runway capacity or reduces delays. The problem of finding an optimal schedule for aircraft landings is referred to as the “aircraft landing problem”. The objective is to minimize the total delay of aircraft landings or the respective cost. The necessary separation time between two operations must be met. Due to the complexity of this scheduling problem, recent research has been focused on developing heuristic solution approaches. This article presents a new algorithm that is able to create optimal landing schedules on multiple independent runways for aircraft with positive target landing times and limited time windows. Our numerical experiments show that problems with up to 100 aircraft can be optimally solved within seconds.

Introduction

The number of passenger flights and cargo flights has been increasing over recent years and is expected to continue to increase. The number of aircraft in use, the number of passengers carried, and the air cargo tonnage are expected to double within the next two decades (Boeing, 2013). An important limitation in aviation, however, is the runway systems of airports, which limit the number of take-offs and landings per hour. The runway capacity of major European airports is exceeded in periods of high demand, which leads to delays in take-offs and landings. The cost of delays incurred by air traffic flow management (ATFM) (i.e., during take-off, flight, or landing) for all European airports was estimated to be as high as 1.25 billion euros (1.61 billion dollars) in 2011 (Cook and Tanner, 2011). The total ATFM delay cost in North America was estimated to be as high as 4.6 billion dollars in 2010 (Ball et al., 2010).

The number of possible landings per hour depends on the types of aircraft involved and on the sequence of operations. Depending on its size and shape, each aircraft causes air turbulence (“wake vortices”) that affects the following aircraft. Therefore a minimum separation time between two operations is required. Aircraft are usually divided into a small number of aircraft classes. Table 1 shows a matrix of class-dependent minimum separation times. The values in this matrix are based upon the spacing requirements imposed by the US Federal Aviation Administration (FAA, 2012). Different separation matrices can be found in the related literature, but most of these matrices consist of three to five aircraft classes and have a similar structure (Beasley, Sonander, Havelock, 2001, Harikiopoulo, Neogi, 2011, Psaraftis, 1980, Soomer).

The aircraft landing problem (ALP) assigns landing times and runways to a given set of aircraft approaching an airport. The planning horizon is very short as the mean time of an aircraft from the time it arrives within the radar range of an airport (the Terminal Maneuvering Area, TMA) to the targeted landing time is approximately 30 minutes (Balakrishnan and Chandran, 2010). As each aircraft has a preferred landing time, the objective is to minimize the total delay costs for all aircraft landings while respecting the separation requirements. The cost function approximates the actual costs such as fuel, maintenance, exhaust emissions, and passengers missing their connecting flights.

By re-arranging the sequence of runway operations instead of using a priority rule, such as FCFS, a significant reduction of total cost can be achieved. For congested runway systems, this optimization leads to either a reduction of the number of aircraft in holding patterns or to an increase of capacity, i.e., more landings per hour that can be performed. This would lead to a considerable increase in revenue.

Extensive reviews of the literature on the ALP are given by Beasley, Krishnamoorthy, Sharaiha, and Abramson (2000) and Bennell, Mesgarpour, and Potts (2013). Table 2 provides an overview of related articles. The columns in the table show the underlying assumptions of the ALP discussed in the respective articles; most of the articles discuss the ALP with a single runway (R = 1) while others consider multiple (parallel and independent) runways (R ≥ 1). The most common objective is to minimize the total delay costs, but other objectives (such as minimizing the longest delay or minimizing the makespan) are also presented. The delay costs are determined by cost functions that are linear or piecewise linear and convex (i.e., the additional cost per period of delay increases). Regarding the target time, we can distinguish two streams of literature; the target times (T_a) are assumed to be zero or are allowed to be positive. Some of the papers allowing positive target times allow early landings to occur, that is, landings between the target time and an earliest landing time (E_a), which are also associated with costs. Most articles assume limited time windows for landings, i.e., there is a latest landing time (L_a) for each aircraft that must not be exceeded by its actual landing time. The last column shows which solution approaches are discussed in the respective articles.

To date, no efficient methods have been proposed in the reviewed literature for the multi-runway ALP that are capable of solving large problem instances. The most common solution approaches are (1) mixed-integer programming (MIP) formulations, which are solved with a standard solver; (2) branch-and-bound (B&B) algorithms; (3) dynamic programming (DP) approaches; and (4) heuristic solution approaches.

MIP formulations: the first mixed-integer formulation for the ALP on a single runway was published by Abela, Abramson, Krishnamoorthy, De Silva, and Mills (1993). The extension to multiple runways by Beasley et al. (2000) is the most cited MIP formulation of the ALP to date. Pinol and Beasley (2006) further generalize this formulation to runway-dependent time windows and separation times. Briskorn and Stolletz (2014) proposed a modification of the MIP of Beasley et al. (2000) that explicitly considers aircraft classes.

B&B algorithms: Abela et al. (1993) present a B&B approach for the single-runway ALP. Ernst, Krishnamoorthy, and Storer (1999) develop a B&B solution procedure for the ALP that outperforms standard solvers using the MIP formulation by Beasley et al. (2000) but, nevertheless, results in excessive computation times for all instances, except for small problem instances.

Dynamic programming approaches: Dear (1976) presents a dynamic programming formulation for the single runway problem with a constrained-position-shifting (CPS) assumption, i.e., each aircraft can be shifted only by a limited number of positions from the sequence of arrivals at the runway. CPS approaches are also presented by Psaraftis (1980), Dear and Sherif (1991), and, more recently, by Balakrishnan and Chandran (2010). Psaraftis (1980) presents a DP approach for the single-runway ALP that makes use of the class-dependent separation times to reduce the problem complexity. Bianco, Dell’Olmo, and Giordani (1999) present a DP approach for a single-machine scheduling problem with sequence-dependent setup times that is equivalent to the single-runway case of the ALP without consideration of aircraft classes. Briskorn and Stolletz (2014) describe a DP approach for the ALP with multiple runways and under consideration of limited time windows. However, they do not provide numerical results for their approach.

Heuristic solution approaches: Abela et al. (1993) propose a genetic algorithm (GA) as a heuristic solution approach. Bianco et al. (1999) propose two heuristic approaches (cheapest addition and cheapest insertion) for their DP approach. Fahle, Feldmann, Gtz, Grothklags, and Monien (2003) compare different exact and heuristic solution approaches for the ALP on a single runway: MIP, integer programming (IP), constraint programming (CP), hill climbing (HC), and simulated annealing (SA). Pinol and Beasley (2006) develop two population-based heuristic approaches (scatter search and a bionomic algorithm) for the ALP. Soomer (2008) and Soomer and Franx (2008) introduce fairness aspects to the ALP by providing airlines the opportunity to define their own cost functions. The numerical study is performed using a local search heuristic.

Many articles assume a fixed number of aircraft classes, but only a few actually use this property in their solution approaches (Bojanowski, Harikiopoulo, Neogi, 2011, Briskorn, Stolletz, 2014, Harikiopoulo, Neogi, 2011, Psaraftis, 1980). The algorithms presented in the remaining articles assume aircraft-dependent cost functions and separation requirements. However, most of the problems discussed feature class-dependent cost functions and separation requirements.

This article contributes to the current state of research in the scheduling of airport runway operations by providing a new optimization algorithm for the ALP with general assumptions (multiple runways, positive target times, and limited time windows). Existing approaches are either heuristic or rely on more restrictive assumptions concerning the number of runways, landing times, or time windows, see Table 2. Our method is based on the DP approach by Briskorn and Stolletz (2014). However, this paper focuses on computational complexity only. While polynomiality of the developed approach is proven, it is left open how to efficiently implement the approach and what actual computation times can be achieved. Certainly, computation times can be expected to be huge for a straightforward implementation since the run time complexity is reported to be O(n¹⁷) (n being the number of aircraft) for two runways and two aircraft classes. We purposefully modify the problem setting in order to allow more efficient solution methods without losing practice-orientation. Also, we develop a new dominance criterion for state space reduction by which we can reduce computation times significantly. We obtain a DP approach yielding optimum schedules significantly faster than a standard MIP solver (CPLEX).

Our approach does not consider stochastic events, e.g., changes in target landing times of approaching aircraft or weather conditions. We assume short planning horizon of approximately 45–60 minutes, in which it is possible to calculate the target landing times with a high precision, and to have a reliable weather forecast.

In Section 2, we provide a formal problem definition as well as a mixed-integer programming formulation. In Section 3, the new optimization algorithm is described in detail. The numerical study in Section 4 compares the results of the algorithm to optimal results of a MIP solver and provides a sensitivity analysis. Section 5 briefly describes how the algorithm could be used in practice by embedding it in a rolling horizon approach. Section 6 summarizes the major insights and outlines future research.