# A Runway Configuration Management Model with Marginally Decreasing Transition Capacities

Authors: Christopher Weld; Michael Duarte; Rex Kincaid
Journal: Advances in Operations Research
 (2010)

---

## Abstract

The runway configuration management (RCM) problem governs what combinations of airport runways are in use at a given time, and to what capacity. Runway configurations (groupings of runways) operate under runway configuration capacity envelopes (RCCEs) which limit arrival and departure capacities. The RCCE identifies unique capacity constraints based on which tarmacs are used for arrivals, departures, or both, and their direction of travel. When switching between RCCEs, some decrement in arrival and departure capacities is incurred by the transition. A previous RCM model (Frankovich et al., 2009) accounted for this cost through a required period of inactivity. In this paper, we instead focus on the introduction and assessment of a model capable of marginally decreasing RCCE capacities during configuration transitions. A transition penalty matrix is introduced, specifying the relative costs (in terms of accepted arrival and departure capacities) for switching between RCCEs. The new model benefits from customizable transition penalties which more closely represent real-world conditions, at a reasonable computational cost.


---

## Body

## 1. Introduction

The dynamics of a metroplex—a grouping of airports in close geographic proximity—are governed by a complex underlying framework of airport regulatory guidance, competition, and feasibility constraints. Much is riding on efficient metroplex operations, from the service quality to millions of travelers worldwide, to the financial gains and losses of a multibillion dollars a year airline industry. With up to three times the current traffic demand expected by 2025, this problem turns from a matter of efficiency to one of necessity [1]. An intuitive response to the forecasted increase is to expand existing or build new airports. This approach, however, is not always practical or possible. Expanding existing or building new airports is not only an expensive and time-consuming task, but more critically it is often geographically infeasible due to space limitations. It is a paradox of the air transportation system: high-demand areas in greatest need of expansion are inherently populated city centers or urban areas without required space to expand.To alleviate congestion while maintaining connectivity to desired destinations, airport operations are tuned as closely to optimal conditions as possible. This goal introduces several challenging subproblems, including the focus of this research: forecasting runway configuration management (RCM) decisions. A “big picture” introduction follows detailing the decomposition approach used to address our problem and the nested airport management problems surrounding RCM.


### 1.1. Problem Approach

The Air Transportation System is a globally connected network. It is necessary to decompose this complex system into workable problem sizes. Decomposition starts at the national and regional levels and is further divided into metroplexes—defined earlier as clusters of nodes (airports) in close proximity. Examples of well-known metroplexes include the airports in proximity of San Francisco, Los Angeles, Atlanta, Chicago, and New York (Figure1(b)). Metroplex operations are increasingly the focus of ongoing research due to their highly dependent nature. An airport's operation within the metroplex is significantly influential on its neighbors and is therefore a system worthy of attention.Components of the Air Transportation System.
(a)
United States Air Transportation System(b)
New York City MetroplexFor this study, the metroplex architecture is further decomposed to an individual airport level (Figure2). This is done while mindful of the fact that optimization of airport systems independently does not imply optimization of the system as a whole. It is nonetheless a good place to start analysis and improvements and a necessary first step preceding metroplex and higher level analysis.Figure 2
Decomposing the Air Transportation System into workable subproblems.Future airspace management systems are likely to consolidate air transportation decisions at a centralized metroplex command center rather than individual airports. Metroplex decision makers will require models incorporating each airport's operations. While management of smaller airports with limited capacities (i.e., one or two runways) may be comfortable meeting their requirements without computational assistance, the metroplex runway configuration planner is unlikely to do so. First, decision makers at the metroplex level are inherently less familiar with individual airport operations. Second, the number of feasible runway configurations in a metroplex grows exponentially large. Managing runway configuration changes at the metroplex level requires capturing noteworthy aspects of each airport operation to generate solutions beneficial to metroplex airspace. This reinforces the necessity of computational models for even relatively simple aspects of an individual airport's runway system, as a base of analysis to later facilitate metroplex models.


### 1.2. Airport Subproblems

When addressing the RCM problem, it is important to understand the larger scope of Air Transportation System problems surrounding it. This provides perspective of the dynamic, nested environment the RCM problem lies within. As dependent subproblems, outputs from one system are treated as inputs to another. This division of labor is necessary to decompose the multitude of problems implicit with airport operations. Connecting its pieces together is a complicated undertaking, and outside the scope of this study. Familiarity with its dynamics, however, remains important.Of the many subproblems pertinent to airport operations, the four chosen to discuss next adequately place the framework of the RCM problem and highlight arguably the most significant aspects effecting day-to-day airport operations. Although such a division is not so clearly defined in practice, this compartmented view facilitates understanding of the total operating environment. Four problems are illustrated in Figure3 followed by a short description of each.Figure 3
Typical Air Transportation System subproblems.


#### 1.2.1. Distributed Trajectory and Route Planning

This sub-problem focuses on the flight path taken by aircraft between locations. Its intent is to identify the most efficient (shortest or fastest) flight path between origin and destination while addressing constraints associated with air traffic (see [2–6]). Constraints include safe travel distances between aircraft, alleviating congestion, and avoiding problematic areas due to weather and no-fly restrictions. This problem requires flight departure location and time and scheduled destination and time, as input.


#### 1.2.2. Arrival and Departure Scheduling

This sub-problem focuses on sequencing aircraft into and outof an airport. It aims to maximize throughput and minimize delay for inbound flights (see [7, 8]). Time between aircraft, a function of both the departing aircraft size and the size of its predecessor, is a primary constraint of this problem. For example, a smaller plane requires a larger gap when following a larger plane to allow the currents/vortexes created behind the larger aircraft to dissipate. It additionally takes into account the runways available for use, and the size and capabilities of those runways. Required as input to this problem are forecasted runways for use, and scheduled arrival and departure demand by aircraft type (size).


#### 1.2.3. Runway Configuration Management

The RCM sub-problem is the focus of this paper (Figure4). Its intent is to produce a schedule identifying what runway(s) is placed into operation accepting arrivals, departures, or both (see [9–11]). Constraints are imposed by the subset of configurations available for future use (based on forecasted weather conditions), capabilities of each configuration to satisfy demand, and the cost of transitioning between configurations. Required parameters of input are unique airport/runway characteristics, forecasted weather, and forecasted demand.Figure 4
The RCM problem uses a mixed integer linear program to recommend scheduled configuration changes.


#### 1.2.4. Combined Arrival and Departure Runway Scheduling

This sub-problem controls ground movement and gate sequencing. Its intent is to efficiently manage ground traffic, increasing throughput while meeting scheduled arrival and departures time lines (see [12, 13]). Constraints coinciding with ground movement are specific to tarmac size and shape—maneuverability of aircraft around each other is typically possible but restrictive. It also governs constraints concerning gate assignment: identifying locations compatible with aircraft sizes and maintaining appropriate airline affiliations. Inputs to this problem include airport characteristics (tarmac, gates), runways in use, and flight arrival and departure schedules.


### 1.3. RCM Dynamic Operating Environment

RCM decisions are complicated by a dynamic system rich with uncertainty. It is therefore not possible to deterministically forecast configurations in which to operate throughout the day. Weather conditions such as wind speed, wind direction, and cloud cover ceiling are among the most influential characteristics governing available configurations for use. Additionally, environmental constraints such as noise and no-fly restrictions over populated areas are often present at varying times of the day.Despite uncertainty in the system, flight demand and weather conditions are input into the RCM problem deterministically based on forecasts. Processing updated solutions every 5 to 10 minutes is assumed adequate to recalculate using previously unknown system parameters as they unfold. Regardless of its instability, forecasting an optimal schedule of configuration changes provides an efficient solution for RCM managers to adjust from.


## 1.1. Problem Approach

The Air Transportation System is a globally connected network. It is necessary to decompose this complex system into workable problem sizes. Decomposition starts at the national and regional levels and is further divided into metroplexes—defined earlier as clusters of nodes (airports) in close proximity. Examples of well-known metroplexes include the airports in proximity of San Francisco, Los Angeles, Atlanta, Chicago, and New York (Figure1(b)). Metroplex operations are increasingly the focus of ongoing research due to their highly dependent nature. An airport's operation within the metroplex is significantly influential on its neighbors and is therefore a system worthy of attention.Components of the Air Transportation System.
(a)
United States Air Transportation System(b)
New York City MetroplexFor this study, the metroplex architecture is further decomposed to an individual airport level (Figure2). This is done while mindful of the fact that optimization of airport systems independently does not imply optimization of the system as a whole. It is nonetheless a good place to start analysis and improvements and a necessary first step preceding metroplex and higher level analysis.Figure 2
Decomposing the Air Transportation System into workable subproblems.Future airspace management systems are likely to consolidate air transportation decisions at a centralized metroplex command center rather than individual airports. Metroplex decision makers will require models incorporating each airport's operations. While management of smaller airports with limited capacities (i.e., one or two runways) may be comfortable meeting their requirements without computational assistance, the metroplex runway configuration planner is unlikely to do so. First, decision makers at the metroplex level are inherently less familiar with individual airport operations. Second, the number of feasible runway configurations in a metroplex grows exponentially large. Managing runway configuration changes at the metroplex level requires capturing noteworthy aspects of each airport operation to generate solutions beneficial to metroplex airspace. This reinforces the necessity of computational models for even relatively simple aspects of an individual airport's runway system, as a base of analysis to later facilitate metroplex models.


## 1.2. Airport Subproblems

When addressing the RCM problem, it is important to understand the larger scope of Air Transportation System problems surrounding it. This provides perspective of the dynamic, nested environment the RCM problem lies within. As dependent subproblems, outputs from one system are treated as inputs to another. This division of labor is necessary to decompose the multitude of problems implicit with airport operations. Connecting its pieces together is a complicated undertaking, and outside the scope of this study. Familiarity with its dynamics, however, remains important.Of the many subproblems pertinent to airport operations, the four chosen to discuss next adequately place the framework of the RCM problem and highlight arguably the most significant aspects effecting day-to-day airport operations. Although such a division is not so clearly defined in practice, this compartmented view facilitates understanding of the total operating environment. Four problems are illustrated in Figure3 followed by a short description of each.Figure 3
Typical Air Transportation System subproblems.


### 1.2.1. Distributed Trajectory and Route Planning

This sub-problem focuses on the flight path taken by aircraft between locations. Its intent is to identify the most efficient (shortest or fastest) flight path between origin and destination while addressing constraints associated with air traffic (see [2–6]). Constraints include safe travel distances between aircraft, alleviating congestion, and avoiding problematic areas due to weather and no-fly restrictions. This problem requires flight departure location and time and scheduled destination and time, as input.


### 1.2.2. Arrival and Departure Scheduling

This sub-problem focuses on sequencing aircraft into and outof an airport. It aims to maximize throughput and minimize delay for inbound flights (see [7, 8]). Time between aircraft, a function of both the departing aircraft size and the size of its predecessor, is a primary constraint of this problem. For example, a smaller plane requires a larger gap when following a larger plane to allow the currents/vortexes created behind the larger aircraft to dissipate. It additionally takes into account the runways available for use, and the size and capabilities of those runways. Required as input to this problem are forecasted runways for use, and scheduled arrival and departure demand by aircraft type (size).


### 1.2.3. Runway Configuration Management

The RCM sub-problem is the focus of this paper (Figure4). Its intent is to produce a schedule identifying what runway(s) is placed into operation accepting arrivals, departures, or both (see [9–11]). Constraints are imposed by the subset of configurations available for future use (based on forecasted weather conditions), capabilities of each configuration to satisfy demand, and the cost of transitioning between configurations. Required parameters of input are unique airport/runway characteristics, forecasted weather, and forecasted demand.Figure 4
The RCM problem uses a mixed integer linear program to recommend scheduled configuration changes.


### 1.2.4. Combined Arrival and Departure Runway Scheduling

This sub-problem controls ground movement and gate sequencing. Its intent is to efficiently manage ground traffic, increasing throughput while meeting scheduled arrival and departures time lines (see [12, 13]). Constraints coinciding with ground movement are specific to tarmac size and shape—maneuverability of aircraft around each other is typically possible but restrictive. It also governs constraints concerning gate assignment: identifying locations compatible with aircraft sizes and maintaining appropriate airline affiliations. Inputs to this problem include airport characteristics (tarmac, gates), runways in use, and flight arrival and departure schedules.


## 1.2.1. Distributed Trajectory and Route Planning

This sub-problem focuses on the flight path taken by aircraft between locations. Its intent is to identify the most efficient (shortest or fastest) flight path between origin and destination while addressing constraints associated with air traffic (see [2–6]). Constraints include safe travel distances between aircraft, alleviating congestion, and avoiding problematic areas due to weather and no-fly restrictions. This problem requires flight departure location and time and scheduled destination and time, as input.


## 1.2.2. Arrival and Departure Scheduling

This sub-problem focuses on sequencing aircraft into and outof an airport. It aims to maximize throughput and minimize delay for inbound flights (see [7, 8]). Time between aircraft, a function of both the departing aircraft size and the size of its predecessor, is a primary constraint of this problem. For example, a smaller plane requires a larger gap when following a larger plane to allow the currents/vortexes created behind the larger aircraft to dissipate. It additionally takes into account the runways available for use, and the size and capabilities of those runways. Required as input to this problem are forecasted runways for use, and scheduled arrival and departure demand by aircraft type (size).


## 1.2.3. Runway Configuration Management

The RCM sub-problem is the focus of this paper (Figure4). Its intent is to produce a schedule identifying what runway(s) is placed into operation accepting arrivals, departures, or both (see [9–11]). Constraints are imposed by the subset of configurations available for future use (based on forecasted weather conditions), capabilities of each configuration to satisfy demand, and the cost of transitioning between configurations. Required parameters of input are unique airport/runway characteristics, forecasted weather, and forecasted demand.Figure 4
The RCM problem uses a mixed integer linear program to recommend scheduled configuration changes.


## 1.2.4. Combined Arrival and Departure Runway Scheduling

This sub-problem controls ground movement and gate sequencing. Its intent is to efficiently manage ground traffic, increasing throughput while meeting scheduled arrival and departures time lines (see [12, 13]). Constraints coinciding with ground movement are specific to tarmac size and shape—maneuverability of aircraft around each other is typically possible but restrictive. It also governs constraints concerning gate assignment: identifying locations compatible with aircraft sizes and maintaining appropriate airline affiliations. Inputs to this problem include airport characteristics (tarmac, gates), runways in use, and flight arrival and departure schedules.


## 1.3. RCM Dynamic Operating Environment

RCM decisions are complicated by a dynamic system rich with uncertainty. It is therefore not possible to deterministically forecast configurations in which to operate throughout the day. Weather conditions such as wind speed, wind direction, and cloud cover ceiling are among the most influential characteristics governing available configurations for use. Additionally, environmental constraints such as noise and no-fly restrictions over populated areas are often present at varying times of the day.Despite uncertainty in the system, flight demand and weather conditions are input into the RCM problem deterministically based on forecasts. Processing updated solutions every 5 to 10 minutes is assumed adequate to recalculate using previously unknown system parameters as they unfold. Regardless of its instability, forecasting an optimal schedule of configuration changes provides an efficient solution for RCM managers to adjust from.


## 2. Problem Formulation

The RCM problem is formulated as a mixed integer linear program (MILP). A base model for the RCM problem, taken from Frankovich, et al. [10] is given. Following its description, we then introduce the marginally decreasing transition capacities (MDTCs) formulation.


### 2.1. Terms and Definitions

The following key terms and definitions define the base RCM problem formulation [10, 14]. Concepts contained in this section, however, are consistent with the MDTC formulation.While defined elsewhere within the text, Table1 is provided as a tool to reference frequently used acronyms.Table 1
Frequently used acronyms.
MDTCMarginally decreasing transition capacitiesMILPMixed integer linear programRCCERunway configuration capacity envelopeRCMRunway configuration managementRCM problems use aggregate traffic demand through uniform time increments several hours into the future. Aggregating traffic over the next five hours into 15-minute windows, for example, is a sufficient level of detail to drive runway management decisions. There are two reasons for this. First, cumulative overall system performance, rather than individual flight performance, is the objective of interest to RCM. Second, system uncertainties prohibit a fine level of detail for future planning. These intervals and significant data associated with them are𝒯: set  of  equidistant  time  intervals,t∈{1,2,3,…,T},at, dt: arrivals and  departures,  respectively,   at  time t,ct, qt: delay  cost  for  a  single  arrival,  or  departure,  at  time  t.RCCEs are a configuration-dependent series of piecewise segments limiting arrival and departure capacities during a given time period. Multiple RCCEs are possible under the same configuration. Real-world RCCEs are theorized to be entirely concave, and this allows for a straightforward series of constraints within our linear program through a combination of the piecewise linear concave segments. An example of three distinct RCCEs is shown in Figure5.RCCEs supporting departure-heavy, neutral, anVd arrival-heavy runway options for a given configuration,k.
(a)
Three example RCCEs (Rk) supporting a given configuration (k)(b)
Analogous runway illustrations corresponding toRkThree piecewise segments are assumed sufficient to capture any RCCE and are represented asj∈{1,2,3}. These pieces are defined by the parameters α, β, and γ such that:(2.1)γjkrykrt-βjkrxkrt≤αjkr∀j,k,r,t,
where αjkr>0, βjkr≤0, and γjkr>0, with each parameter indexed by configuration, k, and RCCE, r, for each segment, j. From this point forward γ is assumed to be equal to one, which in turn associates α with the y-intercept and β with the slope of the piecewise linear functions.Availability of a given configuration is subject to environmental constraints such as noise and no-fly restrictions over populated areas during specified hours. More critically, it is a function of forecasted weather conditions. Primary concern for aircraft is that they land, and take off, into the wind. This increases air flow over their wings, creating lift during takeoff and while decelerating for landing. An example of available runways to select between based on wind direction is provided in Figure6 (although wind magnitude is also significant, it is ignored for the illustration).Wind effects on availability of airport runways.
(a)
North-Eastern Wind(b)
Eastern Wind(c)
South-Eastern WindThe operating status of each RCCE is modeled by a set of binary integer variables,zkrt with k as the configuration and r as the RCCE. If the RCCE is active, the binary variable is set to 1, otherwise 0. Additional variables xkrt, ykrt, ut, and vt are also required to model met and unmet demand:(2.2)K=setofallconfigurations,k∈{1,2,…,K},Kt=setofallconfigurationsavailableattimet,Rk=setofRCCE,r∈{1,2,…,nk}availablefork,Rkt=setofRCCEavailableforconfigurationkatt,Jk=setofRCCElinearsegments,j∈{1,2,3},availablefork,zkrt={1,ifconfigurationk,RCCErchosenatt,0,otherwise,(xkrt,ykrt)={ofdepartureandarrivaldemandmetbyconfigurationk,RCCEr,attimet0,otherwise,(ut,vt)=unmetdepartureandarrivaldemandatt.


### 2.2. RCM Base Model

The RCM formulation by Frankovich, et al. [10] is provided next. It will be referenced as the “base model.” Its purpose is both to introduce an RCM formulation, and for comparison in computational experiments.The model formulation is given below, followed by a short description of its objective function and constraints:(2.3)minimize∑t∈T(ctut+qtvt),(2.4)st:at+ut-1-∑k∈Kt∑r∈Rktykrt≤ut∀t∈T,(2.5)dt+vt-1-∑k∈Kt∑r∈Rktxkrt≤vt∀t∈T,(2.6)∑k∈Kt∑r∈Rktzkrt≤1∀t∈T,(2.7)γjkrykrt-βjkrxkrt-αjkrzkrt≤0,∀t∈T,∀k∈Kt,∀r∈Rkt,∀j∈Jk,(2.8)∑k′∈Kt∖{k}∑r′∈Rk′tzk′r′t-1+∑r∈Rktzkrt≤1∀t∈T∖{1},∀k∈Kt,(2.9)xkrt,ykrt,ut,vt≥0,int⁡∀t∈T,(2.10)u0,v0=0,(2.11)zkrt∈{0,1}.The objective function (2.3) aims to minimize the weighted total unmet arrival and departure demand experienced through configuration and RCCE selection over all time periods. This objective is achieved while operating within the constraints listed, which are briefly described below.Constraints (2.4) and (2.5) ensure conservation of demand (i.e., demand at t, plus carryover demand from t-1, minus demand satisfied at t, does exceed unmet demand for t) for arrivals and departures, respectively. Constraint (2.6) ensures at most one RCCE is selected to operate in for each time interval. Constraint (2.7) restricts an activated RCCE to only satisfy demand contained within its capacity capabilities. Constraint (2.8) necessitates any changeover between RCCEs in different configurations results in a period of inactivity. In other words, two consecutive zkrt values from one time period to the next cannot sum past one if their configurations are different (k≠k′). Lastly, constraint (2.9) necessitates nonnegative unmet demand, constraint (2.10) sets the initial unmet demand values to zero, and constraint (2.11) requires an RCCE for any configuration to either be inactive or active.


### 2.3. MDTC Formulation

The model provided in Section2.2 is now adjusted to better reflect real-world operating conditions. To do so, we adopt a more detailed approach to quantifying transition costs incurred by an RCCE's capacity during configuration changes. In the previous model these costs necessitated a period of inactivity (see constraint (2.8), Section 2.2). Our alternate formulation allows us to measure the operational impact of a configuration change as a quantifiable, marginally decreased transition capacity unique to the configuration change of interest.Figure7 illustrates the significance of this contribution. Figure 7(a) demonstrates how relative effects of a configuration change will vary depending on the ease of transition. The scenario on the left of this subfigure experiences a relatively small decrement in capabilities due to the addition of a runway for arrivals and departures. A much larger decrement in transition capabilities is seen on the right of this subfigure and is attributed to the inherent complexities of both removing a runway from operation while activating two additional. Figure 7(b) illustrates the calculations supporting a marginally decremented capability.Fundamental principal of the MDTC formulation.
(a)
Unique pairwise exchange of configurations determines relative operational costs(b)
A transitioning RCCE atpij percent operational capacityThis approach more accurately represents real-world circumstances, where the capacity of a given RCCE is decremented (rather than eliminated) during a period of transition, and this marginal impact is a function of its previous state.Two significant adjustments to the previous model are made to achieve this goal. The first is a conceptual change; each RCCE of a configuration is now referenced as its own unique configuration. For this reason, terms previously indexed as an RCCE,r, in a given configuration, k, are now represented with a single subscript, k, and treated as their own configuration. Therefore, zkrt, xkrt, and ykrt as defined in the base model are represented in the MDTC model as zkt, xkt, and ykt, while defined similarly. Table 2 illustrates this important difference indexing terms between models.Table 2
Reindexing under MDTC model; each RCCE of the base model now represented as a unique configuration.
Base modelMDTCConfiguration (k∈𝒦)RCCE (r∈ℛk∀k)Configuration (k)11122⋮⋮n1212⋮n2⋮K12⋮⋮nK∑i=1KniThe second adjustment is the introduction of a penalty matrix,P, and a switch variable, skt. The penalty matrix serves to capture the decremented capacity inherent when switching between configurations such that (2.12)pij=percentageofRCCEjcapableofsupportingdemandafterswitchingfromRCCEiforanytimet∈T.
In accordance with this definition, pij=1 when i=j.As customizable constants,pij matrix values are altered to achieve an appropriate percentage operating capability during a period of transition. For example, the base model of Section 2.2 is a special case of this penalty matrix having no cost (pij=1) for ij transitions previously categorized as RCCEs under a single configuration of the base model, and complete inactivity (pij=0) when switching between configurations under their definition. Additionally, MDTC formulation improves model accuracy by allowing any operating capacity, 0≤pij≤1, during transition to mirror real-world circumstances.To construct theP matrix, airport runway management assesses relative costs for potential runway transitions. In doing so, they consider runway dynamics including but not limited to repositioning of aircraft on the tarmac, repositioning of inbound flights, delays required to transition a runway from arrivals to departures (or viceversa), and movement of key runway personnel and equipment. Conceptually, pij “costs” approximate the effective percentage operating capability remaining over a time interval, t, following inactivity due to configuration changes. For example, given equidistant time intervals of 15 minutes in 𝒯 and a transition from i to j requiring three minutes of inactivity to execute, the corresponding pij value is 12/15=0.8.In practice, the three minutes of inactivity described above are not necessarily a continuous block of time. Based on runway dynamics previously discussed, controllers may expect effects of the transition to persist over six minutes, during which time the configuration will average approximately half its typical arrival and departure capabilities. Although not truly binary in terms of “active” or “inactive,” an assessment ofpij in these terms is necessary for the MDTC model and is approximated. These estimated values improve accuracy over the base model, which required a uniform period of inactivity for any transition consistent with the time interval defined by 𝒯 (i.e., a 15-minute inactive period given the example described above). The resulting P matrix is provided as input to the MDTC MILP:(2.13)P=[1p12p13⋯⋯p1np211p2,np31⋱⋮⋮⋮⋮pn-1,1⋱pn-1,npn1pn2⋯⋯pn,n-11].WhileP is a matrix of constants determined by airport management to capture the percent operating capacity between any pairwise configuration change over the transition, skt is a variable assuming the cost of a specific switch under consideration: (2.14)skt={1-pijifconfigurationjisswitchedtofromconfigurationiattimet,0,otherwise.Provided next is the problem formulation updated under these circumstances. As evident, the changes discussed have second-order effects throughout the problem formulation.ℛkt is removed, and items previously indexed over ℛkt and 𝒦t are now solely indexed over 𝒦t (with the cardinality of 𝒦t increasing to ∑i=1Kni as demonstrated in Table 2):(2.15)minimize∑t∈T(ctut+qtvt),(2.16)st:at+ut-1-yt≤ut,∀t∈T,(2.17)dt+vt-1-xt≤vt,∀t∈T,(2.18)∑k∈Ktzkt≤1,∀t∈T,(2.19)γjkyt-βjkxt-αjk(1-skt)≤M(1-zkt),∀t∈T,∀k∈Kt,∀j∈Jk(2.20)skt≤zkt,∀t∈T,∀k∈Kt,(2.21)∑k′∈Kt∖{k}(1-pk′k)zk′t-1+zkt≤skt+1,∀t∈T∖{1},∀k∈Kt,(2.22)∑k′∈Kt∖{k}(1-pk′k)zk′t-1≥skt,∀t∈T∖{1},∀k∈Kt(2.23)xt,yt,ut,vt≥0,int,∀t∈T,u0,v0=0,zkt∈{0,1}.Constraint (2.20) forces skt to zero for all k not selected, and less than or equal to one for selected k at time interval t. For selected k, constraints (2.21) and (2.22) force skt to the switch cost (1-pk′k) associated with a transition from k′ to k (as provided by the P matrix). The switch cost (skt) is then used to marginally decrease the frontier represented by constraint (2.19) to a degree appropriate for the transition.Variables representing met demand(xt,yt) are now index by time period only. This change requires a new approach to the piecewise RCCEs constraints given in (2.19). A large numeric constant, M, is introduced to ensure only active configurations are used to determine met demand. If a configuration is not selected at time t, zkt=0, and M amplifies the RCCE to an unrestrictive degree (capable of meeting all demands). When a configuration is activated, zkt=1, M(1-zkt)=0, and the selected RCCE is therefore restrictive for satisfying demand at time t.M is chosen carefully to ensure proper implementation. If M is too large, slightly nonzero values of (1-zkt) due to computer roundoff error (despite zkt set to one) are multiplied to significant proportions. Conversely, an M value too small will inadequately “push out” a piecewise linear RCCE segment with a largely negative slope. By controlling the maximum negative slope of generated piecewise RCCE segments and assessing the largest level of departure demand anticipated during any time interval, an appropriately large M value is calculated specific to problem parameters.


## 2.1. Terms and Definitions

The following key terms and definitions define the base RCM problem formulation [10, 14]. Concepts contained in this section, however, are consistent with the MDTC formulation.While defined elsewhere within the text, Table1 is provided as a tool to reference frequently used acronyms.Table 1
Frequently used acronyms.
MDTCMarginally decreasing transition capacitiesMILPMixed integer linear programRCCERunway configuration capacity envelopeRCMRunway configuration managementRCM problems use aggregate traffic demand through uniform time increments several hours into the future. Aggregating traffic over the next five hours into 15-minute windows, for example, is a sufficient level of detail to drive runway management decisions. There are two reasons for this. First, cumulative overall system performance, rather than individual flight performance, is the objective of interest to RCM. Second, system uncertainties prohibit a fine level of detail for future planning. These intervals and significant data associated with them are𝒯: set  of  equidistant  time  intervals,t∈{1,2,3,…,T},at, dt: arrivals and  departures,  respectively,   at  time t,ct, qt: delay  cost  for  a  single  arrival,  or  departure,  at  time  t.RCCEs are a configuration-dependent series of piecewise segments limiting arrival and departure capacities during a given time period. Multiple RCCEs are possible under the same configuration. Real-world RCCEs are theorized to be entirely concave, and this allows for a straightforward series of constraints within our linear program through a combination of the piecewise linear concave segments. An example of three distinct RCCEs is shown in Figure5.RCCEs supporting departure-heavy, neutral, anVd arrival-heavy runway options for a given configuration,k.
(a)
Three example RCCEs (Rk) supporting a given configuration (k)(b)
Analogous runway illustrations corresponding toRkThree piecewise segments are assumed sufficient to capture any RCCE and are represented asj∈{1,2,3}. These pieces are defined by the parameters α, β, and γ such that:(2.1)γjkrykrt-βjkrxkrt≤αjkr∀j,k,r,t,
where αjkr>0, βjkr≤0, and γjkr>0, with each parameter indexed by configuration, k, and RCCE, r, for each segment, j. From this point forward γ is assumed to be equal to one, which in turn associates α with the y-intercept and β with the slope of the piecewise linear functions.Availability of a given configuration is subject to environmental constraints such as noise and no-fly restrictions over populated areas during specified hours. More critically, it is a function of forecasted weather conditions. Primary concern for aircraft is that they land, and take off, into the wind. This increases air flow over their wings, creating lift during takeoff and while decelerating for landing. An example of available runways to select between based on wind direction is provided in Figure6 (although wind magnitude is also significant, it is ignored for the illustration).Wind effects on availability of airport runways.
(a)
North-Eastern Wind(b)
Eastern Wind(c)
South-Eastern WindThe operating status of each RCCE is modeled by a set of binary integer variables,zkrt with k as the configuration and r as the RCCE. If the RCCE is active, the binary variable is set to 1, otherwise 0. Additional variables xkrt, ykrt, ut, and vt are also required to model met and unmet demand:(2.2)K=setofallconfigurations,k∈{1,2,…,K},Kt=setofallconfigurationsavailableattimet,Rk=setofRCCE,r∈{1,2,…,nk}availablefork,Rkt=setofRCCEavailableforconfigurationkatt,Jk=setofRCCElinearsegments,j∈{1,2,3},availablefork,zkrt={1,ifconfigurationk,RCCErchosenatt,0,otherwise,(xkrt,ykrt)={ofdepartureandarrivaldemandmetbyconfigurationk,RCCEr,attimet0,otherwise,(ut,vt)=unmetdepartureandarrivaldemandatt.


## 2.2. RCM Base Model

The RCM formulation by Frankovich, et al. [10] is provided next. It will be referenced as the “base model.” Its purpose is both to introduce an RCM formulation, and for comparison in computational experiments.The model formulation is given below, followed by a short description of its objective function and constraints:(2.3)minimize∑t∈T(ctut+qtvt),(2.4)st:at+ut-1-∑k∈Kt∑r∈Rktykrt≤ut∀t∈T,(2.5)dt+vt-1-∑k∈Kt∑r∈Rktxkrt≤vt∀t∈T,(2.6)∑k∈Kt∑r∈Rktzkrt≤1∀t∈T,(2.7)γjkrykrt-βjkrxkrt-αjkrzkrt≤0,∀t∈T,∀k∈Kt,∀r∈Rkt,∀j∈Jk,(2.8)∑k′∈Kt∖{k}∑r′∈Rk′tzk′r′t-1+∑r∈Rktzkrt≤1∀t∈T∖{1},∀k∈Kt,(2.9)xkrt,ykrt,ut,vt≥0,int⁡∀t∈T,(2.10)u0,v0=0,(2.11)zkrt∈{0,1}.The objective function (2.3) aims to minimize the weighted total unmet arrival and departure demand experienced through configuration and RCCE selection over all time periods. This objective is achieved while operating within the constraints listed, which are briefly described below.Constraints (2.4) and (2.5) ensure conservation of demand (i.e., demand at t, plus carryover demand from t-1, minus demand satisfied at t, does exceed unmet demand for t) for arrivals and departures, respectively. Constraint (2.6) ensures at most one RCCE is selected to operate in for each time interval. Constraint (2.7) restricts an activated RCCE to only satisfy demand contained within its capacity capabilities. Constraint (2.8) necessitates any changeover between RCCEs in different configurations results in a period of inactivity. In other words, two consecutive zkrt values from one time period to the next cannot sum past one if their configurations are different (k≠k′). Lastly, constraint (2.9) necessitates nonnegative unmet demand, constraint (2.10) sets the initial unmet demand values to zero, and constraint (2.11) requires an RCCE for any configuration to either be inactive or active.


## 2.3. MDTC Formulation

The model provided in Section2.2 is now adjusted to better reflect real-world operating conditions. To do so, we adopt a more detailed approach to quantifying transition costs incurred by an RCCE's capacity during configuration changes. In the previous model these costs necessitated a period of inactivity (see constraint (2.8), Section 2.2). Our alternate formulation allows us to measure the operational impact of a configuration change as a quantifiable, marginally decreased transition capacity unique to the configuration change of interest.Figure7 illustrates the significance of this contribution. Figure 7(a) demonstrates how relative effects of a configuration change will vary depending on the ease of transition. The scenario on the left of this subfigure experiences a relatively small decrement in capabilities due to the addition of a runway for arrivals and departures. A much larger decrement in transition capabilities is seen on the right of this subfigure and is attributed to the inherent complexities of both removing a runway from operation while activating two additional. Figure 7(b) illustrates the calculations supporting a marginally decremented capability.Fundamental principal of the MDTC formulation.
(a)
Unique pairwise exchange of configurations determines relative operational costs(b)
A transitioning RCCE atpij percent operational capacityThis approach more accurately represents real-world circumstances, where the capacity of a given RCCE is decremented (rather than eliminated) during a period of transition, and this marginal impact is a function of its previous state.Two significant adjustments to the previous model are made to achieve this goal. The first is a conceptual change; each RCCE of a configuration is now referenced as its own unique configuration. For this reason, terms previously indexed as an RCCE,r, in a given configuration, k, are now represented with a single subscript, k, and treated as their own configuration. Therefore, zkrt, xkrt, and ykrt as defined in the base model are represented in the MDTC model as zkt, xkt, and ykt, while defined similarly. Table 2 illustrates this important difference indexing terms between models.Table 2
Reindexing under MDTC model; each RCCE of the base model now represented as a unique configuration.
Base modelMDTCConfiguration (k∈𝒦)RCCE (r∈ℛk∀k)Configuration (k)11122⋮⋮n1212⋮n2⋮K12⋮⋮nK∑i=1KniThe second adjustment is the introduction of a penalty matrix,P, and a switch variable, skt. The penalty matrix serves to capture the decremented capacity inherent when switching between configurations such that (2.12)pij=percentageofRCCEjcapableofsupportingdemandafterswitchingfromRCCEiforanytimet∈T.
In accordance with this definition, pij=1 when i=j.As customizable constants,pij matrix values are altered to achieve an appropriate percentage operating capability during a period of transition. For example, the base model of Section 2.2 is a special case of this penalty matrix having no cost (pij=1) for ij transitions previously categorized as RCCEs under a single configuration of the base model, and complete inactivity (pij=0) when switching between configurations under their definition. Additionally, MDTC formulation improves model accuracy by allowing any operating capacity, 0≤pij≤1, during transition to mirror real-world circumstances.To construct theP matrix, airport runway management assesses relative costs for potential runway transitions. In doing so, they consider runway dynamics including but not limited to repositioning of aircraft on the tarmac, repositioning of inbound flights, delays required to transition a runway from arrivals to departures (or viceversa), and movement of key runway personnel and equipment. Conceptually, pij “costs” approximate the effective percentage operating capability remaining over a time interval, t, following inactivity due to configuration changes. For example, given equidistant time intervals of 15 minutes in 𝒯 and a transition from i to j requiring three minutes of inactivity to execute, the corresponding pij value is 12/15=0.8.In practice, the three minutes of inactivity described above are not necessarily a continuous block of time. Based on runway dynamics previously discussed, controllers may expect effects of the transition to persist over six minutes, during which time the configuration will average approximately half its typical arrival and departure capabilities. Although not truly binary in terms of “active” or “inactive,” an assessment ofpij in these terms is necessary for the MDTC model and is approximated. These estimated values improve accuracy over the base model, which required a uniform period of inactivity for any transition consistent with the time interval defined by 𝒯 (i.e., a 15-minute inactive period given the example described above). The resulting P matrix is provided as input to the MDTC MILP:(2.13)P=[1p12p13⋯⋯p1np211p2,np31⋱⋮⋮⋮⋮pn-1,1⋱pn-1,npn1pn2⋯⋯pn,n-11].WhileP is a matrix of constants determined by airport management to capture the percent operating capacity between any pairwise configuration change over the transition, skt is a variable assuming the cost of a specific switch under consideration: (2.14)skt={1-pijifconfigurationjisswitchedtofromconfigurationiattimet,0,otherwise.Provided next is the problem formulation updated under these circumstances. As evident, the changes discussed have second-order effects throughout the problem formulation.ℛkt is removed, and items previously indexed over ℛkt and 𝒦t are now solely indexed over 𝒦t (with the cardinality of 𝒦t increasing to ∑i=1Kni as demonstrated in Table 2):(2.15)minimize∑t∈T(ctut+qtvt),(2.16)st:at+ut-1-yt≤ut,∀t∈T,(2.17)dt+vt-1-xt≤vt,∀t∈T,(2.18)∑k∈Ktzkt≤1,∀t∈T,(2.19)γjkyt-βjkxt-αjk(1-skt)≤M(1-zkt),∀t∈T,∀k∈Kt,∀j∈Jk(2.20)skt≤zkt,∀t∈T,∀k∈Kt,(2.21)∑k′∈Kt∖{k}(1-pk′k)zk′t-1+zkt≤skt+1,∀t∈T∖{1},∀k∈Kt,(2.22)∑k′∈Kt∖{k}(1-pk′k)zk′t-1≥skt,∀t∈T∖{1},∀k∈Kt(2.23)xt,yt,ut,vt≥0,int,∀t∈T,u0,v0=0,zkt∈{0,1}.Constraint (2.20) forces skt to zero for all k not selected, and less than or equal to one for selected k at time interval t. For selected k, constraints (2.21) and (2.22) force skt to the switch cost (1-pk′k) associated with a transition from k′ to k (as provided by the P matrix). The switch cost (skt) is then used to marginally decrease the frontier represented by constraint (2.19) to a degree appropriate for the transition.Variables representing met demand(xt,yt) are now index by time period only. This change requires a new approach to the piecewise RCCEs constraints given in (2.19). A large numeric constant, M, is introduced to ensure only active configurations are used to determine met demand. If a configuration is not selected at time t, zkt=0, and M amplifies the RCCE to an unrestrictive degree (capable of meeting all demands). When a configuration is activated, zkt=1, M(1-zkt)=0, and the selected RCCE is therefore restrictive for satisfying demand at time t.M is chosen carefully to ensure proper implementation. If M is too large, slightly nonzero values of (1-zkt) due to computer roundoff error (despite zkt set to one) are multiplied to significant proportions. Conversely, an M value too small will inadequately “push out” a piecewise linear RCCE segment with a largely negative slope. By controlling the maximum negative slope of generated piecewise RCCE segments and assessing the largest level of departure demand anticipated during any time interval, an appropriately large M value is calculated specific to problem parameters.


## 3. MDTC Formulation Assessment

### 3.1. Random RCCE, Test Scenario Generation

The ability to quickly generate unique RCCE and configuration scenarios is applicable to any RCM problem and necessary to evaluate how well a given problem formulation performs. This section details how we completed this task. A four-step approach is provided. Those four steps are graphically illustrated in Figures8 to 11 and detailed below.Figure 8
Step  1: thex and y intercepts (xint,yint) are determined.Step one (Figure8) determines the x and y intercepts:(3.1)Xint⁡~U(1,C-1),(3.2)Yint⁡_μ=C-xint⁡,(3.3)Yint⁡~N(Yint⁡_μ,(0.1*Yint⁡_μ)2).
While their sum remains approximately constant—(3.2) only subject to variation in (3.3)—the uniform distribution of xint in its feasible range (3.1) creates variation in the RCCEs. This generates RCCEs with very different capabilities (i.e., more arrival-capable, mid-range, more departure-capable).Step two (Figure9) determines the first pivot point of the piecewise linear graph. Construction of all pivot points will be governed by the fact that RCCEs are comprised entirely of piecewise linear segments with decreasing slopes:(3.4)X1~U(1,xint⁡-1),(3.5)ylb1=yint⁡-yint⁡xint⁡x1,(3.6)Y1~U(ylb1,yint⁡),(3.7)β1=yint⁡-y1-γ1x1,(3.8)α1=yint⁡.Figure 9
Step  2: the first pivot location(x1,y1) is identified.The first pivot pointx value, x1, is sampled from a uniform distribution within its feasible region defined by (3.4) (scenarios with x1≤1, or x1≥(xint-1) are ignored because the resulting convex hull would encompass no integral points). Based on x1, a feasible region for y1 (maintaining the piecewise concave assembly of the RCCE) is identified (3.5), and y1 is chosen randomly within it (3.6). The α and β values for the first piecewise segment are subsequently computed (3.7) and (3.8).Step three (Figure10) determines a second pivot point, (x2,y2), in a technique synonymous to the selection of the first pivot point. One additional parameter is required (3.11), an upper bound for y2 to ensure decreasing slopes of the RCCE are maintained: (3.9)X2~U(x1,xint⁡),(3.10)ylb2=y1+y1x1-xint⁡(x2-x1),(3.11)yub2=y1+yint⁡-y1-x1(x2-x1),(3.12)Y2~U(ylb2,yub2),(3.13)β2=y1-y2γ2(x1-x2),(3.14)α2=y1-x1(y1-y2)x1-x2.Figure 10
Step  3: the second pivot location(x2,y2) is identified.Figure 11
Step  4: the final piecewise linear segment is identified.The fourth and final step (Figure11) generates the last RCCE segment and identifies its associated α and β values:(3.15)β3=y2γ3(x2-xint⁡),α3=xint⁡(-y2x2-xint⁡).The convex hull about the resulting RCCEs integral points is the feasible region it operates within since arrivals and departures are restricted to nonnegative integer values.The associated code was programmed inC, with number of configurations and number of time periods as user input.


### 3.2. Experimental Results

The RCCE generation technique described in Section3.1, combined with probabilistic arrival and departure demand, comprises, the data sets for the experimental trials (specifics of probabilistic data parameters are omitted here for brevity but are available from the authors upon request.) Several trials of the base [10] and the MDTC (Section 2.3) formulations were conducted and analyzed. The trials were run using the Gurobi 2.0.0 solver for AMPL on a dual-core Opteron 2218 system with 8 Gb of memory. This system [15] boasted a significant advantage by allowing a batch file of our design to queue and process hundreds of jobs in succession. It is important to note, however, its processing speed for AMPL under a single node is comparable to widely available CPU processing times, and therefore trials are representative of airport management operating conditions.All statistical comparisons made between models in this section are done using identical input parameters. In other words, both models run synonymous data files (identical number of time units, configurations with their associated capacity curves, arrival and departure demand, etc.) to compute results with one exception: the penalty matrix ofpij values unique to the MDTC formulation. Values of pij=1 were assigned to any two configurations (or, in terms of the original model, RCCEs) i, j, which carried no cost for transitions between them. However, all other i, j, combinations were assigned a pij value between 0 and 1 representing the percentage of their capacity envelope in which they are able to operate over a transition period.


#### 3.2.1. Problem Size

Growth in MILP size in accordance with problem parameters is provided in Table3. A variety of sizes are listed, but real-world RCM scenarios are noteworthy. The typical real-world problem forecasts five hours out. Using 15-minute aggregate time intervals, this requires 20 time periods. The number of runway configuration permutations available will vary in accordance with airport size. Using the relatively large JFK airport as an example, between 2005 and 2009 it operated in one of 13 configurations over 95% of its use, and the remaining 5% encompassed over 50 seldom-used additional configurations [16]. Seldom-used configurations are of interest to this problem. If their infrequent use is a function of simplicity (i.e., management uses 13 “primary” configurations to ease decision making), an accurate RCM MILP could expose utility in choosing lesser used configurations. Considering more candidates for use, the optimal solution may select those not typically considered.Table 3
Average (utilizing 30 trials per parameterization) problem sizes under various parameters.
Base model configurations (𝒦)MDTC configurations (𝒦)TimesVariables (V) Constraints (C)510152051015205V—103.8193.2208.8—83.2142.8153.2C—131.2224.4246.0—221.2419.8446.210V103.6193.6332.8308.296.4156.4249.2232.8C147.0251.0409.4378.4232.4432.4747.2679.815V166.4227.6464.0392.0151.6192.4350.0302.0C235.2308.2576.0493.4380.6513.41055.0877.020V231.0303.0594.8480.0208.0256.0450.5192.4C322.8412.0708.0628.2533.0691.01361.8513.4Comparison of problem sizes is assisted by a scatter plot of relative values (Figure12). The number of variables in the MDTC formulation is consistently lower than (between 70 and 100%) the base formulation. The primary reason for this is demand served is index solely by time period in the MDTC formulation, whereas in the base formulation it carries three indices: time period, configuration, and RCCE.Figure 12
MDTC and base formulation relative size comparison.The MDTC formulation does, however, require more constraints to address the same scenario. This is primarily due to the second order effects of eliminating RCCEs in MDTC formulation. In the base formulation only the RCCEs available during a time period produced constraints. For the MDTC formulation, each RCCE is represented as its own configuration which always provides an active constraint, made less restrictive through the use ofM (Constraint 15) when not under assessment.


#### 3.2.2. Runtime

The most significant statistical measure is runtime. Since MDTC captures the nuances of transition capabilities to a higher level of detail it will more closely mirror real-world conditions. The question becomes: is the computational expense paid worth the model improvement?Table4 and Figure 13 reflect variations in solve time (determined using AMPL's timing parameter _total_solve_time, a measure of system and user CPU seconds used by all solve commands.) for the MDTC model based on the number of time periods and configurations. Large solve times correlate mostly, though not exclusively, to large time period and configuration sizes.Table 4
Percentage of MDTC model solve times within 10 minutes (30 trials conducted per parameterization).
ConfigurationsTime Periods51015205—0.930.970.8310110.770.6715110.970.832010.930.90.83MDTC solve times (Determined using AMPL's timing parameter _total_solve_time, a measure of system and user CPU seconds used by all solve commands.) under various problem parameters.
(a)
Given 5 or 10 Time Intervals(b)
Given 15 or 20 Time IntervalsA 10-minute solve time threshold is adopted in Table4 under the assumption that model updates provided to RCM managers at this frequency are sufficient to account for previously unknown system parameters as they unfold and adequately assist in the RCM forecast decision making process. MDTC formulations attained solutions within this threshold with relatively high, but varying degrees of success (Table 4). With 30 trials per parameterization, sampling variability is attributed to inconsistencies in the trends seen at 10 configurations for 15 and 20 time periods.


#### 3.2.3. Objective Function

The MDTC formulation always provides an equal or better solution than the base model. The base formulation objective value is an upper-bound of the MDTC formulation because the MDTCpij matrix relaxes base formulation constraint (2.8) requiring a period of inactivity during configuration transitions. The degree to which the MDTC solution betters the base model is a function of the pij values used, scheduled demand, and cost of unmet demand (all random variables in experimental trials).Figure14 compares the ratio of objective function values with problem solve time. Moving from right to left on the graph x-axis represents the degree which MDTC formulation objective function value bettered the base formulation value. Moving up the y-axis corresponds to the additional computational cost incurred over the base model to achieve the MDTC solution.Figure 14
Comparison of MDTC/base model solve time to objective function value.


### 3.3. Implementing the MDTC Model

MDTC formulation remains a viable option for practical implementation despite occasionally large solve times. Two options below support this conclusion.The MDTC model MILP implements branch and bound, therefore an incumbent feasible solution can be returned when a time limit is reached. To determine the entire range of solve times, batch processing trials presented in Section3.2 did not store or print intermediate solutions; however, most solvers permit this activity. For instance, the Gurobi solver has an iteration limit option available allowing the user to specify the maximum number of branch and bound iterations performed before returning its best incumbent feasible solution. Closely matching this limit with the appropriate time limitation (i.e., 10 minutes) ensures a good feasible solution (although not verified optimal) is returned to runway management using the MDTC model at the time needed.Alternatively, given an initial condition, both the base model and MDTC model may be run in parallel. For the given set of input parameters, each model is executed to obtain a recommended forecast of configuration changes. In the event MDTC solve time becomes prohibitively large its execution is terminated and the base model formulation is referenced runway controllers. The MDTC model more accurately portrays real world conditions, and therefore its solution is preferred; however, the base model solution serves as a “safety net” to use when MDTC model runs long.


## 3.1. Random RCCE, Test Scenario Generation

The ability to quickly generate unique RCCE and configuration scenarios is applicable to any RCM problem and necessary to evaluate how well a given problem formulation performs. This section details how we completed this task. A four-step approach is provided. Those four steps are graphically illustrated in Figures8 to 11 and detailed below.Figure 8
Step  1: thex and y intercepts (xint,yint) are determined.Step one (Figure8) determines the x and y intercepts:(3.1)Xint⁡~U(1,C-1),(3.2)Yint⁡_μ=C-xint⁡,(3.3)Yint⁡~N(Yint⁡_μ,(0.1*Yint⁡_μ)2).
While their sum remains approximately constant—(3.2) only subject to variation in (3.3)—the uniform distribution of xint in its feasible range (3.1) creates variation in the RCCEs. This generates RCCEs with very different capabilities (i.e., more arrival-capable, mid-range, more departure-capable).Step two (Figure9) determines the first pivot point of the piecewise linear graph. Construction of all pivot points will be governed by the fact that RCCEs are comprised entirely of piecewise linear segments with decreasing slopes:(3.4)X1~U(1,xint⁡-1),(3.5)ylb1=yint⁡-yint⁡xint⁡x1,(3.6)Y1~U(ylb1,yint⁡),(3.7)β1=yint⁡-y1-γ1x1,(3.8)α1=yint⁡.Figure 9
Step  2: the first pivot location(x1,y1) is identified.The first pivot pointx value, x1, is sampled from a uniform distribution within its feasible region defined by (3.4) (scenarios with x1≤1, or x1≥(xint-1) are ignored because the resulting convex hull would encompass no integral points). Based on x1, a feasible region for y1 (maintaining the piecewise concave assembly of the RCCE) is identified (3.5), and y1 is chosen randomly within it (3.6). The α and β values for the first piecewise segment are subsequently computed (3.7) and (3.8).Step three (Figure10) determines a second pivot point, (x2,y2), in a technique synonymous to the selection of the first pivot point. One additional parameter is required (3.11), an upper bound for y2 to ensure decreasing slopes of the RCCE are maintained: (3.9)X2~U(x1,xint⁡),(3.10)ylb2=y1+y1x1-xint⁡(x2-x1),(3.11)yub2=y1+yint⁡-y1-x1(x2-x1),(3.12)Y2~U(ylb2,yub2),(3.13)β2=y1-y2γ2(x1-x2),(3.14)α2=y1-x1(y1-y2)x1-x2.Figure 10
Step  3: the second pivot location(x2,y2) is identified.Figure 11
Step  4: the final piecewise linear segment is identified.The fourth and final step (Figure11) generates the last RCCE segment and identifies its associated α and β values:(3.15)β3=y2γ3(x2-xint⁡),α3=xint⁡(-y2x2-xint⁡).The convex hull about the resulting RCCEs integral points is the feasible region it operates within since arrivals and departures are restricted to nonnegative integer values.The associated code was programmed inC, with number of configurations and number of time periods as user input.


## 3.2. Experimental Results

The RCCE generation technique described in Section3.1, combined with probabilistic arrival and departure demand, comprises, the data sets for the experimental trials (specifics of probabilistic data parameters are omitted here for brevity but are available from the authors upon request.) Several trials of the base [10] and the MDTC (Section 2.3) formulations were conducted and analyzed. The trials were run using the Gurobi 2.0.0 solver for AMPL on a dual-core Opteron 2218 system with 8 Gb of memory. This system [15] boasted a significant advantage by allowing a batch file of our design to queue and process hundreds of jobs in succession. It is important to note, however, its processing speed for AMPL under a single node is comparable to widely available CPU processing times, and therefore trials are representative of airport management operating conditions.All statistical comparisons made between models in this section are done using identical input parameters. In other words, both models run synonymous data files (identical number of time units, configurations with their associated capacity curves, arrival and departure demand, etc.) to compute results with one exception: the penalty matrix ofpij values unique to the MDTC formulation. Values of pij=1 were assigned to any two configurations (or, in terms of the original model, RCCEs) i, j, which carried no cost for transitions between them. However, all other i, j, combinations were assigned a pij value between 0 and 1 representing the percentage of their capacity envelope in which they are able to operate over a transition period.


### 3.2.1. Problem Size

Growth in MILP size in accordance with problem parameters is provided in Table3. A variety of sizes are listed, but real-world RCM scenarios are noteworthy. The typical real-world problem forecasts five hours out. Using 15-minute aggregate time intervals, this requires 20 time periods. The number of runway configuration permutations available will vary in accordance with airport size. Using the relatively large JFK airport as an example, between 2005 and 2009 it operated in one of 13 configurations over 95% of its use, and the remaining 5% encompassed over 50 seldom-used additional configurations [16]. Seldom-used configurations are of interest to this problem. If their infrequent use is a function of simplicity (i.e., management uses 13 “primary” configurations to ease decision making), an accurate RCM MILP could expose utility in choosing lesser used configurations. Considering more candidates for use, the optimal solution may select those not typically considered.Table 3
Average (utilizing 30 trials per parameterization) problem sizes under various parameters.
Base model configurations (𝒦)MDTC configurations (𝒦)TimesVariables (V) Constraints (C)510152051015205V—103.8193.2208.8—83.2142.8153.2C—131.2224.4246.0—221.2419.8446.210V103.6193.6332.8308.296.4156.4249.2232.8C147.0251.0409.4378.4232.4432.4747.2679.815V166.4227.6464.0392.0151.6192.4350.0302.0C235.2308.2576.0493.4380.6513.41055.0877.020V231.0303.0594.8480.0208.0256.0450.5192.4C322.8412.0708.0628.2533.0691.01361.8513.4Comparison of problem sizes is assisted by a scatter plot of relative values (Figure12). The number of variables in the MDTC formulation is consistently lower than (between 70 and 100%) the base formulation. The primary reason for this is demand served is index solely by time period in the MDTC formulation, whereas in the base formulation it carries three indices: time period, configuration, and RCCE.Figure 12
MDTC and base formulation relative size comparison.The MDTC formulation does, however, require more constraints to address the same scenario. This is primarily due to the second order effects of eliminating RCCEs in MDTC formulation. In the base formulation only the RCCEs available during a time period produced constraints. For the MDTC formulation, each RCCE is represented as its own configuration which always provides an active constraint, made less restrictive through the use ofM (Constraint 15) when not under assessment.


### 3.2.2. Runtime

The most significant statistical measure is runtime. Since MDTC captures the nuances of transition capabilities to a higher level of detail it will more closely mirror real-world conditions. The question becomes: is the computational expense paid worth the model improvement?Table4 and Figure 13 reflect variations in solve time (determined using AMPL's timing parameter _total_solve_time, a measure of system and user CPU seconds used by all solve commands.) for the MDTC model based on the number of time periods and configurations. Large solve times correlate mostly, though not exclusively, to large time period and configuration sizes.Table 4
Percentage of MDTC model solve times within 10 minutes (30 trials conducted per parameterization).
ConfigurationsTime Periods51015205—0.930.970.8310110.770.6715110.970.832010.930.90.83MDTC solve times (Determined using AMPL's timing parameter _total_solve_time, a measure of system and user CPU seconds used by all solve commands.) under various problem parameters.
(a)
Given 5 or 10 Time Intervals(b)
Given 15 or 20 Time IntervalsA 10-minute solve time threshold is adopted in Table4 under the assumption that model updates provided to RCM managers at this frequency are sufficient to account for previously unknown system parameters as they unfold and adequately assist in the RCM forecast decision making process. MDTC formulations attained solutions within this threshold with relatively high, but varying degrees of success (Table 4). With 30 trials per parameterization, sampling variability is attributed to inconsistencies in the trends seen at 10 configurations for 15 and 20 time periods.


### 3.2.3. Objective Function

The MDTC formulation always provides an equal or better solution than the base model. The base formulation objective value is an upper-bound of the MDTC formulation because the MDTCpij matrix relaxes base formulation constraint (2.8) requiring a period of inactivity during configuration transitions. The degree to which the MDTC solution betters the base model is a function of the pij values used, scheduled demand, and cost of unmet demand (all random variables in experimental trials).Figure14 compares the ratio of objective function values with problem solve time. Moving from right to left on the graph x-axis represents the degree which MDTC formulation objective function value bettered the base formulation value. Moving up the y-axis corresponds to the additional computational cost incurred over the base model to achieve the MDTC solution.Figure 14
Comparison of MDTC/base model solve time to objective function value.


## 3.2.1. Problem Size

Growth in MILP size in accordance with problem parameters is provided in Table3. A variety of sizes are listed, but real-world RCM scenarios are noteworthy. The typical real-world problem forecasts five hours out. Using 15-minute aggregate time intervals, this requires 20 time periods. The number of runway configuration permutations available will vary in accordance with airport size. Using the relatively large JFK airport as an example, between 2005 and 2009 it operated in one of 13 configurations over 95% of its use, and the remaining 5% encompassed over 50 seldom-used additional configurations [16]. Seldom-used configurations are of interest to this problem. If their infrequent use is a function of simplicity (i.e., management uses 13 “primary” configurations to ease decision making), an accurate RCM MILP could expose utility in choosing lesser used configurations. Considering more candidates for use, the optimal solution may select those not typically considered.Table 3
Average (utilizing 30 trials per parameterization) problem sizes under various parameters.
Base model configurations (𝒦)MDTC configurations (𝒦)TimesVariables (V) Constraints (C)510152051015205V—103.8193.2208.8—83.2142.8153.2C—131.2224.4246.0—221.2419.8446.210V103.6193.6332.8308.296.4156.4249.2232.8C147.0251.0409.4378.4232.4432.4747.2679.815V166.4227.6464.0392.0151.6192.4350.0302.0C235.2308.2576.0493.4380.6513.41055.0877.020V231.0303.0594.8480.0208.0256.0450.5192.4C322.8412.0708.0628.2533.0691.01361.8513.4Comparison of problem sizes is assisted by a scatter plot of relative values (Figure12). The number of variables in the MDTC formulation is consistently lower than (between 70 and 100%) the base formulation. The primary reason for this is demand served is index solely by time period in the MDTC formulation, whereas in the base formulation it carries three indices: time period, configuration, and RCCE.Figure 12
MDTC and base formulation relative size comparison.The MDTC formulation does, however, require more constraints to address the same scenario. This is primarily due to the second order effects of eliminating RCCEs in MDTC formulation. In the base formulation only the RCCEs available during a time period produced constraints. For the MDTC formulation, each RCCE is represented as its own configuration which always provides an active constraint, made less restrictive through the use ofM (Constraint 15) when not under assessment.


## 3.2.2. Runtime

The most significant statistical measure is runtime. Since MDTC captures the nuances of transition capabilities to a higher level of detail it will more closely mirror real-world conditions. The question becomes: is the computational expense paid worth the model improvement?Table4 and Figure 13 reflect variations in solve time (determined using AMPL's timing parameter _total_solve_time, a measure of system and user CPU seconds used by all solve commands.) for the MDTC model based on the number of time periods and configurations. Large solve times correlate mostly, though not exclusively, to large time period and configuration sizes.Table 4
Percentage of MDTC model solve times within 10 minutes (30 trials conducted per parameterization).
ConfigurationsTime Periods51015205—0.930.970.8310110.770.6715110.970.832010.930.90.83MDTC solve times (Determined using AMPL's timing parameter _total_solve_time, a measure of system and user CPU seconds used by all solve commands.) under various problem parameters.
(a)
Given 5 or 10 Time Intervals(b)
Given 15 or 20 Time IntervalsA 10-minute solve time threshold is adopted in Table4 under the assumption that model updates provided to RCM managers at this frequency are sufficient to account for previously unknown system parameters as they unfold and adequately assist in the RCM forecast decision making process. MDTC formulations attained solutions within this threshold with relatively high, but varying degrees of success (Table 4). With 30 trials per parameterization, sampling variability is attributed to inconsistencies in the trends seen at 10 configurations for 15 and 20 time periods.


## 3.2.3. Objective Function

The MDTC formulation always provides an equal or better solution than the base model. The base formulation objective value is an upper-bound of the MDTC formulation because the MDTCpij matrix relaxes base formulation constraint (2.8) requiring a period of inactivity during configuration transitions. The degree to which the MDTC solution betters the base model is a function of the pij values used, scheduled demand, and cost of unmet demand (all random variables in experimental trials).Figure14 compares the ratio of objective function values with problem solve time. Moving from right to left on the graph x-axis represents the degree which MDTC formulation objective function value bettered the base formulation value. Moving up the y-axis corresponds to the additional computational cost incurred over the base model to achieve the MDTC solution.Figure 14
Comparison of MDTC/base model solve time to objective function value.


## 3.3. Implementing the MDTC Model

MDTC formulation remains a viable option for practical implementation despite occasionally large solve times. Two options below support this conclusion.The MDTC model MILP implements branch and bound, therefore an incumbent feasible solution can be returned when a time limit is reached. To determine the entire range of solve times, batch processing trials presented in Section3.2 did not store or print intermediate solutions; however, most solvers permit this activity. For instance, the Gurobi solver has an iteration limit option available allowing the user to specify the maximum number of branch and bound iterations performed before returning its best incumbent feasible solution. Closely matching this limit with the appropriate time limitation (i.e., 10 minutes) ensures a good feasible solution (although not verified optimal) is returned to runway management using the MDTC model at the time needed.Alternatively, given an initial condition, both the base model and MDTC model may be run in parallel. For the given set of input parameters, each model is executed to obtain a recommended forecast of configuration changes. In the event MDTC solve time becomes prohibitively large its execution is terminated and the base model formulation is referenced runway controllers. The MDTC model more accurately portrays real world conditions, and therefore its solution is preferred; however, the base model solution serves as a “safety net” to use when MDTC model runs long.


## 4. Future Study

The next step in research is to apply MDTC formulation to real-world data. While we believe that RCCEs provide an accurate assessment of runway capabilities, they remain purely theoretical and must be developed with airport management. Once the gap between real-world execution and academic modeling is bridged, practical application can be explored. Through historic records of projected and satisfied flight demand, in addition to management's working knowledge of viable options and capabilities surrounding runway usage, a MILP RCM formulation (such as the MDTC model) can be put to test by assessing its performance against historical results.Another natural extension of the RCM single airport problem is to pursue multiple airport or metroplex operation optimizations. A single airport configuration change has second-order effects on its neighbors, and maximizing throughput or minimizing delay for a metroplex will likely produce configuration changes thought suboptimal by individual airports operating independently. Higher-level coordination for the greater good is paramount to address increasing demand throughout the system and warrants specific attention.Finally, a key component to the Air Transportation System which must not be overlooked is the integration of subproblems into a cohesive network. With results highly dependent upon each other, ordering and synchronizing inputs and outputs between models is necessary to achieve accurate results. The RCM problem is integral to coordination between the arrival and departure scheduling problem, and the combined arrival and departure runway scheduling problems Synchronizing their tasks will enable their successful independent optimizations.


## 5. Conclusions

The RCM problem uses a MILP formulation to determine a schedule of runway configuration changes to maximize efficiency, given forecasted available configurations and demand. RCM is one of many problems facing air traffic controllers in congested metropolitan areas. In a stressed system, whose demand is expected to eventually exceed its capabilities, even marginal improvements are vital. Further underscoring the necessity to generate RCM solutions is its incorporation into a metroplex model. In a metroplex setting the locally managed and relatively simple RCM problems at individual airports are brought to a higher level of management complexity as multiple airports' airspace needs are addressed simultaneously. Such complexity underscores the need for computational tools to assist in RCM decisions.The MDTC RCM formulation improves the existing base model [10] by providing precise configuration transition costs quantified in a pij matrix. Despite reducing the number of variables, with up to double the number of constraints, the MDTC formulation often experiences a significant computational cost. For trials with parameters comparable to real-world circumstances, greater than half of MDTC formulations solved within 2 minutes. Among the same trials, solve time required is prohibitively large (greater than 10 minutes) roughly 20% of the time. Processing both models in parallel could therefore benefit from the model accuracy of the MDTC formulation, with a viable contingency solution available under base model formulation if MDTC solve time is prohibitively large.



---

*Source: 436765-2010-12-29.xml*