INSTITUTE OF TRANSPORTATION STUDIES
UNIVERSITY OF CALIFORNIA, BERKELEY
A Framework for the Assessment of
Collaborative Enroute Resource Allocation
Strategies
Amy Kim, PhD Candidate, Civil and Environmental
Engineering, UC Berkeley
Mark Hansen, Professor of Civil and Environmental
Engineering, UC Berkeley
Working Paper
UCB- ITS- WP- 2010- 2
Abstract
The Airspace Flow Program ( AFP) ground delays flights in order to control their flow through capacity
constrained airspace regions. It has been successful in controlling traffic with reasonable delays, but the
procedures must be improved upon to handle future projected demands. This paper explores a future AFP
where centrally- managed rerouting and user input are incorporated into the initial resource allocations. A
modeling framework was developed to evaluate and compare allocation strategies, under differing
assumptions about traffic managers’ knowledge about airline flight costs. It is used to quantify tradeoffs
regarding the quality and timing of airlines’ input information. Three allocation strategies were developed;
they differ with respect to the input requested of airlines, and the resource allocation philosophy. They are
assessed based on the total cost impact of the AFP initiative on flight operators. To this end, a flight cost
function was developed to represent the cost of delay specific to each flight; it consists of deterministic
components to represent what traffic managers know about the airlines, and a stochastic component to
represent that which they do not. A numerical example demonstrates the situations under which better
information quality could be more desirable than timeliness, and vice versa. Identifying these types of tradeoff
points is a key contribution of this research effort.
Keywords:
Air traffic flow management ( ATFM); Airspace Flow Program ( AFP); Collaborative Decision Making ( CDM); user
cost; centralized decision making; strategic planning.
1. Introduction
Adverse weather frequently and severely impacts flight operations in the National Airspace System ( NAS). In
addition, with the growth in demand projected over the next 20 years, weather and traffic- induced delays are
also anticipated to increase under the current system ( Bureau of Transportation Statistics, 2007). Air traffic
flow management ( ATFM) programs are used to reduce the scale and cost of disruptions to flight operators.
One such initiative is the Airspace Flow Program ( AFP), which facilitates resource allocation decisions when en
route capacity/ demand imbalances exist. In the AFP, flights are held on the ground at departure airports in
order to meter their flow through capacity constrained airspace regions. The AFP was first implemented in
2006 in the northeast region of the U. S., and has demonstrated success in controlling traffic with reasonable
flight delays ( FAA, 2007). However, as traffic demands increase into the future, the benefits derived from the
AFP process will be limited unless a procedure to more effectively utilize airspace capacity is incorporated into
the process.
This research proposes and evaluates alternative mechanisms for a comprehensive, centrally- managed, and
user- input- based en route traffic management initiative. We develop a model framework through which we
formulate, evaluate, and compare flight assignment strategies that employ rerouting combined with ground
delay to minimize the impacts of AFP initiatives on users of the NAS. The assignment strategies differ with
respect to the inputs requested of users, and the resource allocations process. This paper presents three
strategies based on combinations of two resource allocation schemes and two forms of user input. The main
objective is to investigate how these strategies perform in comparison to one another under different
assumptions about airline utility – in particular, different assumptions regarding quality of airline utility
information available to the central planner. The performance of each strategy will be measured using the total
user generalized cost. In addition to the three assignment strategies considered here, others can also be
evaluated using the framework we have developed.
Throughout this paper, “ operator” or “ user” will be used to refer to NAS users such as commercial airlines and
general aviation aircraft. “ Traffic manager” will refer to the agent responsible for allocating resources. In the
US context these would be traffic management specialists at the Federal Aviation Administration’s ( FAA’s) Air
Traffic Control System Command Center ( ATCSCC). Section 2 describes the current system, and provides a
literature review. Section 3 contains a problem overview while Section 4 introduces the modeling framework
and models. Section 5 presents an illustrative numerical example and Section 6 concludes with a discussion
and further research needs.
2. Background
2.1 Rerouting in constrained airspace
Flight rerouting due to severe en route weather and traffic congestion is performed in both strategic and
tactical ATFM. It is manually intensive as it requires close coordination between several traffic management
units. As a result, FAA traffic managers typically select reroutes from a standard set, employing a “ one size fits
all” approach ( Taber, 2006) without operator input. Airlines also have the option of rerouting their own flights
before and after departure, subject to traffic managers' approvals. They often exercise this option to avoid
being assigned routes they consider undesirable, or long departure delays associated with certain routes.
However, if rerouting control were completely in the hands of the traffic managers, and performed without
operator input, these ATFM initiatives would likely be suboptimal. Concepts that propose more collaborative
approaches to rerouting have existed since the early 2000s; these concepts describe a more structured
approach to coordination between traffic managers and operators.
2.2 Collaborative Decision Making ( CDM)
A significant improvement to NAS air traffic flow management began in the mid- 1990s with the Collaborative
Decision Making ( CDM) program. CDM is a joint government and industry initiative that aims to improve both
the technological and procedural aspects of air traffic management, through improved information exchange
between government and industry. The first major application of CDM was to Ground Delay Programs ( GDPs).
When an airport has reduced arrival capacity due to severe weather either en route or near the airport, a GDP
holds flights destined for that airport on the ground at their origin airports to meter demand. CDM drastically
enhanced the effectiveness of GDPs in correcting demand/ capacity imbalances and reducing delays, by
ensuring that the airlines are incentivized to provide up- to- date demand information to traffic managers. GDPs
are very effective in managing reduced arrival capacity when it is caused by inclement weather near the
destination airport. However, GDPs can be inefficient, ineffective and inequitable in addressing en route
constraints. As a result, the AFP was first implemented in 2006 to handle en route constraints.
2.3 Airspace Flow Program ( AFP)
In an AFP, the constrained airspace region and the flights filed into this region during the time of reduced
capacity are identified. The reduced capacity is then allocated by assigning delayed departure times to the
impacted flights. Constrained airspace regions include those that are experiencing undesirable weather and/ or
heavy demands. Most AFPs begin after 2PM local time as airspace congestion and convective weather are more
likely to occur after this time. They typically end after 10PM.
An AFP flight will receive a delayed departure time on its original filed route. It can either accept the assigned
departure time, or reject it and reroute around the constrained airspace ( subject to traffic managers’
approval). Slots to fly through the constrained region are vacated as flights are canceled or routed out, and the
schedule is compressed such that remaining flights are moved up into earlier slots as available. Currently, the
distribution of delayed departure times combined with airline- initiated rerouting and cancellation has proven
to be adequate for handling capacity constraints. However, with growing demand, greater utilization of other
available airspace will be required, possibly resulting in the need to impose slots and assign departure times
for rerouted flights as well. One strategy is to incorporate rerouting options into the initial resource allocation,
such that delayed departure times combined with new route assignments are offered as part of the initial AFP
choice set. Flying a longer route with less ground delay may be a desirable alternative to accepting a long
ground delay on the original route. 1 Also, if neighboring routes could be more optimally utilized, the total delay
cost of the AFP could be reduced. In order to offer resource assignments that are desirable to operators,
however, the FAA will require a significant level of operator input.
2.4 Literature review
There has been much work in developing optimization models to support ATFM decisions. The objective of
many such models is to minimize the system- wide cost of delay. They consider ground holding, air holding and
rerouting decisions. One such model – the Bertsimas and Stock- Patterson model – provides for the input of
flight- specific air and ground hold cost ratios in their model ( Bertsimas and Stock Patterson, 1998). Goodhart
( 2000) provides a framework in which ATFM decisions are made through information exchange between the
FAA and operators.
Uncertainties in weather and capacity have been addressed in the single airport ground holding problem,
which has been considered in deterministic and stochastic, as well as static and dynamic formulations. The
earliest such work began with Andreatta and Romanin- Jacur ( 1987) and Richetta and Odoni ( 1993), and the
problem was addressed in a collaborative context by Ball et al ( 2003). Jakobovits et al ( 2005) formulated an
1 This would be particularly true when there are critical downline flight and crew connections to be made, such that additional en route costs are
outweighed by cost of being late at the destination.
algorithm to schedule, reroute and airhold flights flying into and around constrained airspace, imposing
ordering schemes that align with CDM. More recently, Mukherjee and Hansen ( 2009) considered an extended
variant of the problem for airport terminal routes using a dynamic stochastic approach.
Much literature exists about resource rationing and equity specifically within the context of GDPs. Vossen et al
( 2003) describe a framework for equitable allocation, illustrating its operational impacts and use in reducing
systematic biases, such as favoring longer flights that are frequently exempted. The Ration- By- Schedule ( RBS)
algorithm, where flights are assigned delayed departure times in the order by which they are scheduled to
arrive at the problematic airport, is a well- documented and well- accepted allocation scheme that has been in
use for many years ( Hoffman et al, 2005). Hoffman et al ( 2005) develop an algorithm that allows for
simultaneous rationing of ground and en route resources, as an alternative to using GDPs to handle en route
constraints.
The assumption of continuously distributed value of time ( VOT) over flight populations has not been studied in
the context of the ATFM problem; existing models do not provide for any special treatment of VOT parameters.
However, VOT has been examined as a continuous distribution over a vehicle population for a steady- state
congestion pricing model ( Mayet and Hansen, 2000), as well as for models with variable demand and elastic
travel time functions ( Leurent, 1993). Comparing different methods of incorporating heterogeneous users’
preferences into ATFM models has also not been studied extensively.
3. Problem overview
Flight assignment decisions in the AFP are shaped by system capacity constraints, the allocation and equity
principles chosen for implementation, and, under the CDM philosophy, user inputs. Furthermore, the quality of
an allocation result will of course depend on the assessment metrics used to gauge its performance.
Performance assessments are typically based on system efficiency measures such as total flight delay.
However, if operator cost considerations are included in the assessment of allocation quality, one can see that
the allocation quality would improve when user inputs are incorporated into the assignment process. In this
section we first introduce resource allocation schemes, followed by a brief discussion about user inputs into
the assignment process. The section ends with an introduction to the assignment mechanisms ( which specify
both an allocation scheme and one for obtaining user input) that are the subject of this paper.
There are many resource allocation schemes that could be considered. To demonstrate two possibilities,
consider the example illustrated in Figure 1. Two flights ( A and B) are planned to travel some nominal route
with original departure times 0 and 5 minutes, shown in the top box. The route is completely closed due to
convective weather; to accommodate these flights, departure slots on two alternative routes are offered
( middle box). Suppose that flights A and B provide the traffic manager with their en route costs ( in units of
ground delay minutes, as discussed further below) for each route, also shown in the top box. The final cost is
calculated based on the difference between the original departure time and the assigned departure time, plus
the en route cost. If traffic managers are obliged to serve Flight A first ( Allocation 1), then Flight A would be
given Route 1 slot 1 as it is the lowest cost option available to it. Flight B would be left with Route 1 slot 2 as its
best available option. The total cost of this allocation is 250. If the goal is to minimize total cost ( Allocation 2)
they would assign Flight A to Route 2 slot 1 and Flight B to Route 1 slot 1. The cost of this allocation is 240.
Clearly the allocation results could be different if airlines submitted different cost values, or if some equity
factor, such keeping the highest cost incurred as low as possible, were also included in Allocation 1.
Fig. 1. Illustration of possible allocation outcomes.
We list a few of the many other resource allocation schemes that could be considered ( Ball et al, 2002). Traffic
managers may be instructed to minimize system cost as measured by some metric such as the weighted sum,
with or without consideration of flight/ operator equity. Allocation could follow a “ first- come first- served”
process where the ordering is based on the time of resource requests, the original schedule, or some other
criterion. Airlines could also be assigned a proportion of the total available resources based on the number of
flights they have scheduled, perhaps with some additional weighting based on aircraft size.
As stated previously, user inputs into the assignment process currently consist of providing up- to- date demand
information ( involving flight schedules and cancellations). We are interested in a system where airlines, in
addition to providing updated demand information, provide richer and more detailed inputs into the
assignment process. This input would ideally consist of users’ flight cost and preference information. However,
we understand that in an industry as highly competitive as air travel, airlines must be offered sufficient
incentives and rewards in return for revealing more information about themselves. Additionally, it is not likely
that airlines would provide accurate cost information about their flights, particularly if they perceived that by
reporting higher cost differentials they could receive more desirable resources. This must be taken into
consideration when designing a user input scheme.
The following section introduces a functional form to represent the cost of an AFP resource allocation to
flights, which is then used to assess the performance of three flight assignment models that are also introduced
in detail. These three models are based on two user input types – stated route preference input and
parametric input. Stated route preference input ( Section 4.2) requires operators to supply route- level flight
cost information about each alternative route. It is based on the delay thresholds concept developed as part of
the Flow Constrained Area Rerouting ( FCAR) Decision Support Tool by Metron Aviation ( Hoffman et al, 2004).
Parametric input ( Section 4.3) requires flight operators to supply parameters of the flight cost function which
are not route- specific, but which traffic managers can use to calculate the user costs of reroute and ground
delay options available in an AFP.
Route 1 Route 2
Slot 1 5 0
Slot 2 60 20
Allocation 1
Route/ Slot Cost
A: R1, S1 100+( 5- 0)= 105
B: R1, S2 90+( 60- 5)= 145
Total 250
Allocation 2
Route/ Slot Cost
A: R2, S1 150+( 0- 0)= 150
B: R1, S1 90+( 5- 5)= 90
Total 240
Flight
Original Departure
Times
Cost ( before ground delay):
Route 1 Route 2
A 0 100 150
B 5 90 140
OR
Demand
Capacity
Allocation
The first two assignment models use the stated route preference user input scheme. The first model minimizes
total system cost ( without considering equity) while the second allocates resources through a first- submitted,
first assigned ( FSFA) process. In FSFA, flights are assigned the best available resources in the order they
submit their input data. FSFA is just one example of resource assignment according to a flight prioritization
scheme, which could also be based on other criteria, such as flight schedule. The last assignment model uses
the parametric user input scheme and again allocates resources to minimize total system cost.
4. Model framework
4.1 Flight cost model
Figure 2 depicts the geometry of our modeling framework. Two fixes in en route airspace are connected by a
nominal route, designated as such because it is the shortest path. Flights enter at entry fix “ A” and leave at exit
fix “ B”. The nominal route has sufficient capacity to serve the pre- AFP scheduled demand   (  ) between the
fixes, until a constraint develops at some point along its path and lasts for some duration. The capacity of the
nominal route is now reduced, and all  flights originally scheduled to use this route must be reassigned to
observe the reduced capacity. All  flights are either given delayed departure times, rerouted to an alternate
route, or both. Each alternate route  is characterized by its capacity and travel ( en route) time. We assume
that fixes A and B are not bottlenecks, and for the purpose of this model they are considered the flights’ origin
and destination ( their trajectories beyond these points are out of the analysis scope).
Fig. 2. Model airspace geometry and several parameters.
This analysis is not concerned with the costs of the airlines’ original scheduled flight plans, because we assume
that these flight plans were those most preferred under ideal conditions. Instead, this analysis focuses on
evaluating the added costs associated with greater en route time and ground delay due to the AFP. As
mentioned previously, FAA traffic managers have limited access to airline flight cost details and subsequent
resource preferences.
The flight cost function, 	 
 ,  , represents the added cost of flight  taking route  in an AFP. 	  ,  is a function of
the additional travel time of route  compared to the nominal route ( assuming that aircraft fly at fuel- efficient
speeds), and time spent waiting for their assigned slot on their AFP route ( ground delay). Function 	 
 , 
accounts for direct costs including additional fuel, crew time, and equipment maintenance, and indirect costs
such as passenger satisfaction, gate time, flight coordination, and an airline’s satisfaction with their own
particular objectives. Air holding is not included because we assume that traffic managers have perfect
information about the capacity constraint location and duration, scheduled demand   (  ), and all AFP route
A B
Dotted lines represent alternative routes
Nominal route
...
......
Alternate route r
Capacity Sr( t)
Additional en route time r r
Capacity Constraint
At A:
Initial demand D0( t)
Total AFP capacity S rϵRSr( t)
capacities   (  ),…,   (  ). The flight cost function is specified such that the air time, ground delay, and error
components do not interact with one another. It is also a linear function of inputs, and is quantified in units of
ground delay minutes.
	 
 ,  = 	 
  ,    + 	 
  ,        +  
 ,  ,  
 ,  ∼  ( 1)
The components can be further identified as follows:
	 
 ,  =  
 ⋅    + ! 
 ,  − #  , 
 +  
 ,  ,  
 ,  ∼  ( 2)
Where
•  
 is a ratio that identifies flight  ’ s airborne time cost in units of ground delay minutes, and  
 ≥ 1 ;
• a   n  dis   a  ≥ flig0h. t’s additional en route time when it is reassigned to route  from the nominal route,
• ! 
 ,  is the new departure time for flight  on route  at fix A;
• #  , 
 is the original scheduled departure time for flight  at fix A, and
•  s 
 o, m  eis dais rtrainbduotimon t. e Irtm re rperperseesnetns tAinFgP - f laignhdt r  o’us tue- nskpneocwifinc fcloigshtst cfoors tf lfyaicntog ros nt hraotu atree  , , b tyh daet ffionliltoiowns,
known to a flight’s operator but not to traffic managers nor other airlines.
 
 ≥ 1 because the unit cost of airborne delay costs exceeds that of ground delay.    is non- negative,
assuming the nominal route has the shortest flying time under optimal conditions. Ground delay, or ! 
 ,  − #  , 
 ,
is non- negative because aircraft cannot depart before their original scheduled time.
Let us index slots by increasing departure time on a given route  by A = 1,…, B  . The variable B  represents
the total number of flights assigned to route  , and it follows that Σ B   
D  =  . Each flight is assigned to a slot A
on some route  , and we can identify the route to which flight  is assigned by  (  ), and the slot on that route
by A  (  ).
The AFP capacity of each alternative route  is   (  ), and it follows that the instantaneous minimum headway
at time  is   E  (  ). Now assume that   (  ) is constant over the duration of the AFP such that   (  ) =   , and
aircraft on route  are scheduled at constant headways #  such that #  =   E  . By this assumption of constant
headways and the mapping of flights to their assigned route and slot, the departure time of flight  on route 
is #  (  ) ∙ A  (  ). It then follows that the total cost of an AFP can be expressed as:
G = H  
    ( 
 ) + #  ( 
 ) A  ( 
 )(  )− #  , 
 +  
 ,  ( 
 )
I 

D  ( 3)
Where
• G is the total cost of an AFP;
•    (  ) is flight  ’ s additional en route time when it has been assigned to route  from the nominal
route;
• #  ( 
 ) is the new AFP departure headway on the route  to which  has been assigned;
• A  ( 
 )(  ) is the slot on  to which  has been assigned, and
•   ,  (  ) is a random term representing the unknown ( to the central authority) costs of  flying on
the route  to which it was assigned.
It was previously stated that ground delay must be non- negative; however, we make this condition non-binding
such that the constraint #  ( 
 ) A  (  )− #  , 
 ≥ 0 (∀ A ,  ) need not be imposed on ( 3). In effect, this means
that a flight will never be assigned to a route simply because it is not scheduled to depart early enough to take
an earlier slot on a cheaper alternate route. Relaxing the hard constraint gives the models some convenient
properties that make them more analytically tractable. The assumption is completely valid when scheduled
demand is much higher than the total AFP capacity, or  0 ≫ Σ   K 
= 1 . This situation could occur, even though
the nominal route has adequate capacity in good weather, if the available capacity on alternate routes is very
low because they must accommodate their regular scheduled traffic demands in addition to the new AFP
flights, or are weather- impacted like the nominal route. Moreover, even when  0 ≈ Σ   K 
= 1 , numerical tests
have shown that violations of this earliness restriction are small.
Each flight  in the AFP has an en route cost parameter  
 . If flights are ordered by increasing  ,  (  ) =  
 is
the en route cost parameter for the  th flight, and is also the  th smallest value for this parameter. We assume
that the en route cost parameter has a uniform distribution with a minimum value  M  
 and a maximum value  N O P . This implies that  
 can be approximated as:
 
 =  M  
 + Q ⋅  ( 4)
Where Q = (  M  R −  M  
 )/  .
Recall that the random term in equations ( 1) through ( 3) represents the part of route- specific flight costs that
traffic managers have little to no information about. The specification of the random term is critical to the
performance of each allocation strategy. The random term enters the objective functions at different places in
the different strategies, depending on whether or not the traffic manager has received complete flight cost
information from the airlines. The distribution of the error term affects the comparative performances of the
different strategies. In this paper, the random term takes on an independent and identically distributed ( iid)
extreme value ( Gumbel) form. The Gumbel distribution is characterized by its location ( O ) and scale ( T )
parameters, where the variance is determined by the scale parameter alone but the mean is determined by
both O and T . In the standard Gumbel distribution, O = 0 and T = 1. The Gumbel distribution has several
important properties that makes it analytically convenient to use in the specification of choice probabilities
and expected cost when faced with a given set of choices ( Train, 2003). In addition, the Gumbel distribution is
fairly similar to the normal distribution. The independence assumption is reasonable if we trust that our cost
function captures the major elements of airlines’ AFP reassignment costs, both across flights and across routes.
Although the costs of flights operated by the same airline may be correlated, we assume here that intra- airline
flight differences are so pronounced that this correlation can be ignored.
The allocation models are based on the total cost formulation of ( 3), and they are presented in the following
sections ( 4.2 and 4.3). We first introduce two models based on the stated route preference input concept, and
then one additional model based on the parametric input concept.
4.2 Stated route preference
4.2.1 Concept
The stated route preference models utilize the FCAR delay threshold concept ( Hoffman et al, 2004) introduced
in Section 3. FCAR was developed in order to give operators flexibility in identifying the best reroute options
for their AFP- impacted flights.
In the FCAR process, operators of impacted flights are asked to submit route preference information to the
traffic managers. The information provided is as follows: for each route  , the operator of flight  submits a
delay threshold value Δ 
 ,  . The quantity Δ 
 ,  specifies the airline’s “ true” and complete generalized cost of
flight  traveling on route  without any additional ground delay costs, or before ground delay is assigned.
Delay threshold values are expressed in units of ground delay minutes so that true airline costs are not
explicitly revealed.
In the stated route preference model we assume that each airline would calculate the additional cost of a
reassignment option using ( 2). However, airlines do not know what slots the traffic managers have available
for their flight( s) on each route, and therefore have no information about the amount of ground delay that will
be assigned to their flights. As a result, assuming the flight cost model of ( 2), airlines would submit delay
thresholds ( Δ 
 ,  ) that are calculated as follows.
Δ 
 ,  =  
 ∙    +  
 ,  ( 5)
Where  
 ,  ∼ V W N T X Y ( O , T ). Once traffic managers receive a flight’s delay threshold values, they choose a
feasible departure time slot on each route for that flight. Based on the delay thresholds plus the ground delay
associated with departure time slots, traffic managers can determine the costs of different flight assignments
and then identify the minimum cost option.
An example is shown in Figure 3. Suppose a flight  has three route options, and the flight operator submits a
delay threshold value for each route  ( Δ 
 ,  ). When it is time to allocate a slot on a route to flight  , traffic
managers check the slot availability on each route and determine the ground delay that flight  must take on
each route: V  
 ,  , V  
 , Z , or V  
 , [ . Our specification assumes that each additional minute of ground delay
incurred by a flight waiting for a slot on a route increases by one minute its cost for that route ( represented by
the linearity of Figure 3). Through the full- information optimal ( FIO) allocation scheme, flight  could be
assigned any one of the three routes in the system- optimal allocation. Through the first- submitted, first-assigned
allocation, the route assigned to flight  would be the lowest cost route, or N V  
 , Z , Δ 
 , [ + V  
 , [ ). According to the figure, this would be Route 3. A  ( Δ 
 ,  + V  
 ,  , Δ 
 , Z +
Fig. 3. Illustrating the use of delay thresholds to determine flight costs.
Ground delay
( minutes)
Costn
( ground
delay
minutes)
R1
R2
R3
D n, 3
D n, 1
D n, 2
GDn, 1 GDn, 3 GDn, 2
1
As shown, traffic managers will allocate resources to each flight through a particular allocation scheme using
these delay thresholds. Delay thresholds ensure that under any combination of ground delay slots that could
be assigned to a flight, the operating airline has – implicitly – informed traffic managers about which resources
are of maximum utility to them.
We consider two allocation models that use these delay thresholds as input. In the first, when an AFP has been
announced, and traffic managers request flight operators to submit their delay threshold inputs by a given
deadline. Resources are allocated to all flight simultaneously after this deadline, when traffic managers have
presumably received most or all flights’ information. To represent this procedure we employ a model where
the entire set of inputs is considered simultaneously to allocate resources. We then consider a second system
where flight operators are allocated their preferred resources on a first- submitted, first- assigned ( FSFA) basis.
It is envisioned that operators would be incentivized to submit their inputs as soon as they are able. FSFA was
chosen amongst the many possible allocation schemes available because its prioritization logic and is simple
and easily understood. In addition, it is similar in construct to the ration- by- schedule ( RBS) allocation
algorithm, where flights are assigned delayed departure times in the order by which they are scheduled to
arrive at the capacity- constrained airport. RBS is a well- established allocation scheme that has been in use for
many years ( Hoffman et al, 2005).
4.2.2 Full information, optimal ( FIO) model
In the full information optimal ( FIO) model, we assume that traffic managers use the delay thresholds from all
airlines with AFP- impacted flights in order to make a system- optimal allocation. This allocation scheme does
not have any mechanism to reward or penalize flights based on the order by which delay thresholds are
submitted. This model is idealized in that it is unlikely airlines would offer so much of their flight information
without any equitable resource guarantee from the traffic managers. However, this model offers the best
system performance that can be achieved from any AFP allocation scheme and therefore its results can be used
a benchmark for other models.
The objective of the FIO model is to minimize the total operator cost of the AFP. Because the unknown part of
flight utility is used in the resource allocation process ( and therefore, realized values of the stochastic error
term are included in the model objective function), ( 3) cannot be solved analytically for the FIO model. Instead,
we rearrange ( 3) in order to treat each flight as an individual entity, and the decision variables are binary
indicators of each flight’s assigned route. The model is formulated as binary integer quadratic program; the
branch and bound algorithm can be used to find solutions. We index the AFP routes    , and flights in order of increasing  such that flight  = 1 has the smallest  value in s tuhceh f ltihgahtt   p  o> pu   la Z ti> on⋯. >
Decision variables: P 
 ,  ∈ _ 0,1 ` , ∀  ,  ; P 
 ,  = 1 if flight  is assigned to route  and P 
 ,  = 0 otherwise.
Objective function:
R a m, b ,∀ in 
 ,  G = H H c d 
 ,  + #  ⋅ H P e , 


e D  − #  , 
 f ⋅ P 
 , 

 D 
I

 D 
( 6)
Where
• Δ 
 ,  =    ∙[  M  
 + Q ∙( Σ B h E   h
D Z +  )]+  
 ,  ;
• Q = (  M  R −  M  
 )/ N, and
•  
 ,  ∼ V W N T X Y ( O , T ).
Constraints: Σ P 
 ,   
D  = 1 ∀  ; P 
 ,  ∈ _ 0,1 ` ,∀  ,  .
The constraints ensure that each flight has been assigned to exactly one route, and P 
 ,  can only take values of
zero or one. Preliminary numerical tests have demonstrated that the branch and bound algorithm yields
results that are very close or identical to the analytic solutions ( under k = 0) for this model .
4.2.3 First- submitted, first- assigned ( FSFA) model
In the first- submitted, first- assigned ( FSFA) model, FAA traffic managers receive delay thresholds from
operators in a sequence unknown beforehand. Each time an operator submits delay thresholds for their flight,
traffic managers identify the earliest available and feasible departure time slot on each route. The flight in
question is then assigned the minimum cost resource ( route/ slot combination) available at the time. Future
requests are not considered when an allocation is performed. As a result, the FSFA allocation scheme offers
flight operators an incentive to supply their delay thresholds in a timely manner.
A flight is assigned, or “ chooses”, the minimum cost resources available to it at the time it submits its delay
threshold values. If we assume that the stochastic part of the utility function is iid Gumbel with location
parameter O and scale parameter T , the FSFA process can be represented using the expected received utility
concept of the logit discrete choice model ( Train, 2003). Each flight’s expected minimum cost and choice
probabilities associated with a set of alternatives can be determined analytically. According to Domencich and
McFadden ( 1975) and Ben- Akiva and Lerman ( 1994), the probability of agent  choosing an alternative  is:
 l m 
 ,  n = exp l m 
 ,  / b n Σ exp l m 
 , h / T n  h
D 
( 7)
Where m 
 ,  is the deterministic utility of option  to agent  . Assuming the flight cost function of ( 2),
m 
 ,  = − G   o   M  
  p o  q = −(  
 ⋅    + ! 
 ,  − #  , 
 ), ( 8)
Let us say that r [ 	 
 ] represents the additional expected cost for flight  due to the AFP, based on the
assignment options available to this flight because of the AFP. If r [ 	 
 s t u ] is the expected cost of the AFP
resources available to  , and r [ 	 
  ] is the expected cost of  ’ s original resource prior to AFP inception, then the
difference between the two, or r [ 	 
 ], can be expressed as:
r [ 	 
 ]= r [ 	 
 s t u ]− r [ 	 
  ]
= T ⋅ Y  v H X P w x m 
 ,  T + O y   D  z – T ⋅ Y  | X P w } m 
 
T + O ~  ( 9)
Where O and T are the Gumbel distributional parameters, and m 
  is the deterministic utility of  ’ s original
resource prior to the AFP. As stated previously, we are not concerned with a flight’s cost under normal
operating conditions but rather the flight’s additional costs due to the AFP. As a result, m 
  = 0,∀  ,  .
Recall that ! 
 ,  is the departure time for flight  assigned to  . We can now rewrite ( 9):
r [ 	 
 ]= T ⋅ Y  v H X P w l m 
 ,  / T n   D  z ( 10)
The location parameter O cancels out of the expression due to its inclusion both in the AFP cost and in the
original cost. We now describe the recursive procedure by which the expected minimum AFP cost is calculated
for all flights. Note that this pseudo- analytic procedure yields an approximate solution because of a major
assumption in steps 3c and d. However, the results of this procedure have been checked against simulated
solutions and the error is insignificant. We are currently modifying the procedure in order to remove the
assumption.
1. Assign  value to each flight. Arrange flights in their order of input submission,  = 1,…,  .
2. For flight  = 1, we calculate m  ,  ,   (  ), and r [ 	  ] using ( 8), ( 7), and ( 10) respectively, for each route  .
3. For  = 2,3,…,  :
a) Determine the expected ground delay r ‚ ! 
 ,  ƒ on each route  for flight  . r ‚ ! 
 ,  ƒ is calculated
based on the conditional probability that the previous flight (  − 1) took  . Event “(  − 1) took
route  ” is represented by „ ; event “(  − 1) did not take route  ” is represented by „ q . r ‚ ! 
 ,  ƒ
then becomes:
r ‚ ! 
 ,  ƒ = r ‚ ! 
 ,  … „ ƒ ⋅  ( „ ) + = ( r ‚ ! 
 E  ,  ƒ + #  )⋅  r ( ‚ „ ! ) 
 +,  … r „ ‚ q ! ƒ 
 ⋅ E   (,  „ ƒ q ⋅)( 1 −  ( „ ))
( 11)
 ( „ ) is the probability of agent  − 1 taking route  , and was calculated in step 2 using ( 7).
b) F r i ‚ n ! d 
 ,  th ƒ e− e # x  p, 
 e) c. ted utility of each alternative route  for flight  , expressed as r ‚ m 
 ,  ƒ = −(  
    +
c) Calculate the expected cost r [ 	 
 ] using ( 10) and m 
 ,  = r [ m 
 ,  ] calculated in the previous step
3( b).
d) Find the route choice probabilities  l m 
 ,  n using ( 7) and m 
 ,  = r [ m 
 ,  ].
e) Repeat ( a) through ( d) until  =  .
4. Find Σ r [ 	 
 ] I 

D  .
We can perform the above calculations for different values of the Gumbel scale parameter T , where increasing T increases the variance of the Gumbel- distributed error term  
 ,  .
4.3 Parametric
4.3.1 Concept
In the parametric model setup, we envision that an FAA mandate would require flight operators to provide
cost parameters for their domestic flights to a central, FAA- managed database. This requested parameter is  if
we assume that traffic managers have adopted the flight cost model of ( 2). Operators would be encouraged to
update their parameters as necessary. When an AFP is announced ( typically several hours prior to its start
time ( Hoffman et al, 2004), the parameter values in the database at that time are used to determine route and
ground delay assignments for all AFP- affected flights. We assume that airlines are implicitly incentivized to
provide their most up- to- date cost parameters, in order to maximize their likelihood of obtaining desirable
allocations in the AFP. This model does not employ provide additional incentives to flight operators for
providing this information.
In this scenario the only flight information that traffic managers have from flight operators are  values; traffic
managers do not receive flight information that would be provided through the stochastic error term. As a
result if the stochastic error has a small variance, it can provide a good reflection of operator utility and the
resource allocation can be very efficient. If, however, the stochastic term has a high variance, resource
allocations will be less efficient. We would like to ascertain how this approach performs in comparison to the
stated route preference strategies as the variance of the stochastic utility— and hence the incompleteness of
traffic manager information about flight operator preferences— increases.
4.3.2 Parametric optimal ( PO) model
The parametric optimal model aims to minimize the deterministic portion of the total AFP flight cost. To obtain
analytic solutions where the decision variable is the number of flights to assign to each route  , or B  , we solve
the deterministic part of equation ( 3) using properties that result from the non- binding schedule constraint.
As stated previously in Section 4.1, under the non- binding schedule constraint assumption, flight  ’ s resource
assignment is not influenced by its original scheduled departure time, †  such that   is the pre- AFP
characteristic that decides which resource  receives in the allocation process. As a result, it follows that flights
with the highest  values should be assigned to the routes with lowest en route times, and vice versa, if the
minimum cost solution is to be obtained ( see Appendix for proof). We can achieve this by ordering flights by
increasing  values and routes by decreasing en route times ( such that    >   Z > ⋯ >    ). For instance, if
there are two routes where    >   Z , flights with lower  are assigned to Route 1 such that those with higher 
are assigned to Route 2. If   is the en route cost parameter of any flight on route  , then   <  Z . This is
illustrated in Figure 4.
Fig. 4. Assignment of flights to routes by increasing ˆ values.
Out of the population of flights assignment to route  , the smallest en route cost parameter value of these
flights is   M  
 , and the largest   M  R . B  is the number of flights on a route, and is also expressed as the number
of flights that take en route cost parameter values between   M  
 and   M  R inclusively. If B  flights btoyt a( la ecnco rroduinteg ctoos te qfoura ftliiognh t( s4 o) n, l rinoeuatrel y  ) i si necxrperaessisnegd  a sv: a lues between   M  
 and   M  R , then we can saarye othradte rtehde
G     = Ž   Ž ∙ B  ∙    ( 12a)
Where
Ž   Ž = 0.5∙(   M  
 +   M  R ) ( 12b)
According to equation ( 4), it is also true that
X1
N
X2 Xr ...
Route 1 Route 2 … Route r … Route R
XR ...
a
min
r a
max a
min a
max
r a
n
  M  R =   M  
 + Q ∙( B  − 1) ( 12c)
And, if routes are ordered such that    >   Z > ⋯ >    :
  M  
 =  M  
 + Q H B h E 
 h
D  + Q ( 12d)
Where B 0 = 0. We now substitute ( 12c & d) into ( 12b) to obtain
Ž   Ž =  M  
 + Q H B h E 

h D  + 0.5∙ Q ∙( B  + 1) ( 12e)
We can now rewrite equation ( 3) for the objective function of the PO model below, with the intent of finding B  ,∀  .
Decision variables: B  , the total number of flights assigned to route  ∈ K ; B  ∈ _ 0,  ` ,∀  .
Objective function:
N A  ‘ ’ ,…, ‘ “ G ” = H l   Ž Ž ⋅ B  ⋅    + 0.5⋅ #  ⋅ B  ⋅( B  + 1) n  
D  − H #  , 

I 

D  ( 13)
Where
•   Ž Ž =  M  
 + Q Σ B h E   h
D  + 0.5⋅ Q ⋅( B  + 1);
• Q = (  M  R −  M  
 )/ N, and
• B 0 = 0.
Constraints: Σ B   
D  =  ; 0 ≤ B  ≤  ,∀  .
The first constraint ensures that the number of flights assigned to the available routes equals the total number
of AFP flights  such that each flight is assigned to an available route. The second constraint ensures that all
route counts are non- negative and do not exceed the number of AFP flights. The objective function of ( 13) was
checked for convexity. B  is integer, but this is relaxed in order to obtain the analytic solution. Even if solutions
are not integer, rounding ( to preserve  ) will still produce acceptable solutions ( Richetta and Odoni, 1993); in
a practical sense, the headways on each route should be designed to include some buffer space that would
allow for slightly more aircraft than the capacity permits. As a result, if by rounding up B  the route capacities
were exceeded occasionally, the result would not be catastrophic.
If B 
 < 0 or B 
 >  ∀  , then interior solutions to the objective function of ( 13) do not exist, and solutions lie at
the boundaries. In these two cases, B 
 ∗
= 0 and B 
 ∗
=  , respectively.
Recall that this resource allocation is performed using only the deterministic portion of operator flight cost.
Once resource allocations are made, we can calculate the expected “ true” cost of the allocation by adding the
stochastic error term that represents the unknown AFP- and route- specific flight cost components. If  
 ,  ( 
 ) are
iid Gumbel with parameters ( O , T ), then according to the central limit theorem their sum is asymptotically
distributed normal with mean 0 and standard deviation — T  /√ 6, and
r [ G ] = G ” + r v H  
 ,  ( 
 )
I 

D  z = G ” ,  
 ,  ( 
 ) ∼ r m ( O , T ) ( 14)
5. Numerical examples
When the traffic managers have perfect information about the flight operators ( and therefore  
 ,  = 0 ∀  ,  ),
the parametric optimal ( PO) and full information optimal ( FIO) models are identical and hence yield identical
resource allocations and total generalized operator costs. As the traffic managers’ uncertainty about the
operators increases, the total cost of the PO allocation would be expected to increase relative to that of FIO, as
the PO resource allocations do use the operator information provided through the ( changing) stochastic error
term. The FIO model uses complete information to perform a system- optimal resource allocation; as such, it
will always yield the minimum total cost solution under any circumstance. For this reason we treat the FIO
solution as the baseline result. Under a zero error assumption, the first- submitted, first- assigned ( FSFA) model
solution will be inferior to the PO/ FIO model solution because FSFA does not offer a system- optimal allocation.
However, under increasing uncertainty about user cost, we should expect that the FSFA results would also
improve in comparison to the PO results, just as the FIO results do.
To obtain insight into the performance of the three models under increasing uncertainty, which we represent
through increasing error variances, a numerical example is presented here. Suppose  flights must be
reassigned routes and departure times as part of the AFP. The nominal route remains open, but under a
reduced capacity. There are a total of K = 3 routes ( including the nominal route) to which flights can be
reassigned. A common assumption in the existing literature is that one unit of en route time is equal in cost to
two units of delay incurred on the ground; as a result  is often assumed to take on a value of two in the
existing literature ( Mukherjee and Hansen, 2009). For this analysis we assume that air cost ratios are evenly
distributed in ( 1.5,2.5] across all flights.
The details of the Base Scenario ( 1) are contained in Table 1, and the results are contained in Figure 5.
Table 1. Base Scenario ( 1)
Route Capacity
( aircraft per hour)
Departure Headway š › ( min) a
En Route Time œ › ( min)  › ( min)
1 40 1.5 135 35
2 24 2.5 115 15
3 ( nominal) 15 4b 100 0
a This is the arrival ( and departure) headway at Fix A.
b Headways after AFP capacity reduction.
Fig. 5. Total cost results for models PO and FSFA as a ratio of FIO, base scenario.
In Figure 5, the x- axis represents increasing values of the standard deviation of the error term in the flight cost
model, which in turn represents traffic managers having less and less information about the flight operators.
The value at each point on the x- axis represents the standard deviation as a percentage of the average flight
cost for the FIO solution under perfect information ( i. e.  = 0). For instance, if the total AFP operator cost using
the FIO allocation scheme under perfect information is ž G  , the point “ P = 10%” represents k = 10%∙ ž G  /  .
As our interest is in relative rather than absolute performance, the y- axis represents the ratio of the total cost
of each model to the FIO model total cost, such that   = ž G M ¡    / ž G t ¢ £ . Each point represents the average of
500 simulation runs ( of the FIO model solutions using the branch and bound algorithm).
We can make two main conclusions from Figure 5. As traffic managers know less and less about the flight
operators, the PO model solutions degrade at an increasing rate over the standard deviation, in comparison to
those of the FIO and FSFA models. One can also observe that the PO solution is superior to the FSFA solution
only when traffic managers have relatively good quality information about the operators ( represented by
smaller standard deviation values, in this case, under about 9%). Beyond this point, the FSFA model is more
user cost efficient. This result is intuitive: when traffic managers have more accurate information about the
flight operators, a system optimal allocation with incomplete information is superior to an FSFA allocation
with complete information. However, when traffic managers have less accurate information about flight
operators, it may be more advisable to use an FSFA allocation with complete operator information. Identifying
these types of trade- off points is a core component of this research.
The above observations can have some important policy implications. If traffic managers know that their cost
model specification is quite good, such that it contains a lot of information about the airlines’ flights, they
would be advised to adopt the parametric user input and a system- optimal allocation scheme of the PO
assignment method. If traffic managers know that their cost model does not capture very much information
about flight costs, then they would be advised to use the FSFA allocation method. If the traffic managers have
no idea about the accuracy of their cost model specification but are adverse to the amount of “ damage”
possible using the PO model at high values of k , they would be advised to use the FSFA model as well. However,
if we could assume that the occurrence of information quality level is represented by some probability
distribution, and assume that traffic managers are risk neutral, we could calculate the expected cost of each
strategy over all values of k , and then choose a model.
1.00
1.05
1.10
1.15
1.20
1.25
1.30
1.35
0% 5% 10% 15% 20% 25% 30% 35% 40%
s (% TC0/ N)
PO FSFA ž G N ¤ ! X Y ž G ¥ ¦ §
The next set of tables display the results of sensitivity analyses on the Base Scenario of Figure 5. We consider
five additional scenarios ( Scenarios 2- 6) where we investigate the results of changing capacity characteristics
of the AFP, and two additional scenarios ( 7 & 8) where we change demand characteristics. The details of these
scenarios are listed below.
Scenario 1 ( Base): details as shown in Table 1.
Scenario 2: Route 3 ( nominal) capacity is decreased to 8.57 aircraft per hour, which is 7 minute departure
headways ( # [ = 7). All other characteristics of Scenario 1 retained.
Scenario 3: Route 1 en route time is increased to 145 minutes such that    = 45; Route 1 capacity
increased to 60 aircraft per hour, or #  = 1. All other characteristics of Scenario 1 retained.
Scenario 4: All route capacities are set to 20 aircraft per hour, or #  = 3 ∀  . All other characteristics of
Scenario 1 retained.
Scenario 5: Add 4th route to Base scenario, with capacity of 20 aircraft per hour ( 3 minute headways) and
en route time of 120 minutes. All other characteristics of Scenario 1 retained.
Scenario 6: Add 5th route, with capacity of 12 aircraft per hour ( 5 minute headways) and en route time of
115 minutes.
Scenario 7: Scenario set for  = 25− 70, in increments of 5. All other characteristics of Scenario 1
retained.
Scenario 8: Scenario set for  M  R = 5,10, and 20. All other characteristics of Scenario 1 retained.
Tables 2 through 4 contain some features of the results of Scenarios 1 through 6, 7, and 8, respectively.
Table 2. Scenarios 1- 6, ( PO- FSFA)/ FIO
k = P %∙ ž G   ž G u £ ž G t ¢ £ = ž G t © t s ž G t ¢ £
ž G M ¡    ž G t ¢ £ O 
k = 20% ž G  
0 2% 4% 6% 8% 10% 12% 14% 16% 18% 20% PO FSFA
S1 - 0.03 - 0.02 - 0.02 - 0.01 - 0.01 0.00 0.01 0.03 0.04 0.05 0.07 1.03 1.12 1.05
S2 - 0.03 - 0.02 - 0.02 - 0.01 0.00 0.01 0.02 0.03 0.05 0.07 0.08 1.03 1.13 1.05
S3 - 0.02 - 0.01 - 0.01 - 0.01 0.00 0.01 0.02 0.03 0.04 0.05 0.07 1.02 1.10 1.03
S4 - 0.02 - 0.02 - 0.01 - 0.01 0.00 0.01 0.02 0.03 0.04 0.05 0.06 1.02 1.10 1.04
S5 - 0.02 - 0.02 - 0.01 0.00 0.01 0.02 0.04 0.05 0.07 0.09 0.12 1.03 1.16 1.05
S6 - 0.02 - 0.02 - 0.01 0.00 0.02 0.04 0.06 0.08 0.10 0.13 0.15 1.03 1.20 1.05
The cells of Table 2 contain the results of the difference between the PO and FSFA results. Each row contains
model results from the scenario identified at the very left of the table, over increasing standard deviation
values. Each column represents model results at the given standard deviation value. The darkest ( red) cells at
the left of the table represent those results where the PO total assignment costs are less than FSFA costs, at the
value contained in the cell. So, for instance, in Scenario 3 at standard deviation 0 the cell contains “- 0.016”. This
tells us that under zero error in Scenario 3 the PO total cost ratio is 0.016 less than that of FSFA. The opposite
is true at the right side of the table ( blue cells): for example, in Scenario 6 at 20% standard deviation, the value
in the cell is “ 0.151”. This indicates that under 20% standard deviation in Scenario 6, the PO total cost ratio is
0.151 greater than that of FSFA. Towards the middle of this table are the lightest cells, where the PO and FSFA
results are similar ( near the “ crossing point” shown in Figure 5). The third- to- last column of the table lists the
approximate cost ratio values where the PO and FSFA model results are the same ( or, the y- axis value of the
“ crossing point”) for each scenario. The last two columns identify the cost ratio values when the x- axis value is
20%. Again, the results represent the average of 500 simulation runs per model.
The results in the third- to- last column of Table 2 suggest that the relationship between the FSFA and PO model
is relatively constant over the different scenarios. However, adding additional routes ( Scenarios 5 and 6)
appears to lower the k value at which the FSFA model allocation results begin to outperform the PO results.
Based on the last two columns, it appears that the PO model results ( compared to the FIO results) degrade at a
faster rate when more routes are added ( Scenarios 5 and 6), while the FSFA results remain relatively constant
over all scenarios. With more routes, a larger number of desirable slot options are made available as well. As k
and the number of routes increases, the FIO model can more readily accommodate flights in desirable slots.
However, the PO model always results in the same allocation regardless of k because the stochastic error term
is not accounted for in the allocation. This, we conjecture, results in the PO cost ratio degrading at a faster rate
when there are more routes available. Overall, it appears that the relationships between the models is
relatively consistent over different capacity scenarios. This implies that if the traffic managers had consistent
information about demand and the accuracy of their cost model specification, the decision to use a given
allocation scheme would be relatively robust over changing AFP capacities.
For Scenarios 7 and 8 model results were generated for k values up to 40%.
Table 3. Scenario 7, ( PO- FSFA)/ FIO
k = P %∙ ž G   ž G u £ ž G t ¢ £ = ž G t © t s ž G t ¢ £
ª « ¬ ­ ® ¯ ° ª « ± ² ³ ´ µ
k = 20% ž G  
 0 5% 10% 15% 20% 25% 30% 35% 40% PO FSFA
25 - 0.02 - 0.02 0.00 0.01 0.04 0.07 0.10 0.15 0.20 1.03 1.08 1.04
30 - 0.02 - 0.01 0.00 0.03 0.06 0.09 0.13 0.18 0.24 1.03 1.10 1.04
35 - 0.02 - 0.02 0.00 0.03 0.06 0.10 0.15 0.20 0.26 1.03 1.11 1.04
40 - 0.03 - 0.02 0.00 0.03 0.07 0.11 0.17 0.22 0.29 1.035 1.12 1.05
45 - 0.03 - 0.02 0.00 0.03 0.07 0.12 0.17 0.23 0.29 1.035 1.12 1.05
50 - 0.03 - 0.02 0.01 0.04 0.08 0.13 0.18 0.24 0.32 1.035 1.13 1.04
55 - 0.02 - 0.01 0.01 0.05 0.09 0.13 0.19 0.26 0.33 1.03 1.13 1.04
60 - 0.02 - 0.01 0.01 0.05 0.09 0.14 0.20 0.26 0.33 1.03 1.13 1.05
65 - 0.02 - 0.01 0.02 0.05 0.09 0.15 0.20 0.26 0.34 1.025 1.14 1.04
70 - 0.02 - 0.01 0.02 0.05 0.10 0.15 0.21 0.27 0.35 1.025 1.14 1.04
The results of Table 3 indicate that the models are relatively insensitive to different flight populations,  . We
can observe that the cost results of the PO and FSFA allocations are similar at a k value of about 10% and cost
ratio of about 1.03 over all values of  .
Table 4. Scenario 8, ( PO- FSFA)/ FIO
k = P %∙ ž G   ž G u £ ž G t ¢ £ = ž G t © t s ž G t ¢ £
ª « ¬ ­ ® ¯ ° ª « ± ² ³ ´ µ
k = 20% ž G  
 M  R 0 5% 10% 15% 20% 25% 30% 35% 40% PO FSFA
2.5 - 0.03 - 0.02 0.00 0.03 0.07 0.11 0.17 0.22 0.29 1.03 1.12 1.05
5 - 0.04 - 0.04 - 0.03 - 0.02 0.01 0.03 0.06 0.09 0.13 1.05 1.06 1.05
10 - 0.06 - 0.06 - 0.05 - 0.05 - 0.04 - 0.02 - 0.01 0.01 0.03 1.06 1.02 1.06
20 - 0.06 - 0.06 - 0.06 - 0.06 - 0.05 - 0.05 - 0.04 - 0.03 - 0.01 - 1.01 1.06
Table 4 indicates that as en route cost ratios increase for the flight population, the k value at which the FSFA
model allocation results begins to outperform the PO results increases. In fact when  = 20, we do not observe
the point where the FSFA model becomes more cost efficient than the PO model, over the range of k values
from 0 through 40%. We can also conjecture that as flight  values increase, the significance of the en route
portion of the flight cost model increases and the effect of the unknown portion decreases. Consequently, the
PO model allocation results do not deteriorate as quickly compared to the FIO results with increasing  . The
results of Scenario 8 suggest that the choice of an allocation scheme is highly dependent on the distribution of
flight  parameters. This suggests that the choice of a suitable allocation scheme may vary from one situation
to another depending on the population of flights involved.
6. Discussion and future work
We have proposed a modeling framework through which we investigate the use of systematic user inputs in
allocating constrained airspace capacity. We develop, evaluate and compare three user input and resource
allocation schemes, under differing assumptions about the quality of traffic managers’ information about
operator flight costs. The numerical examples demonstrate situations in which obtaining better information
quality by sacrificing some system efficiency would be desirable, and vice versa. The establishment of a
modeling framework through which we can identify these types of tradeoff points is a key contribution of this
research effort.
There are several ideas that we continue to explore in our on- going work. One of these ideas is to quantify how
much flight operators might be willing to sacrifice input quality in order to submit their inputs faster than their
competitor in the first- submitted, first assigned scheme. We analyze this in a game theoretic setup where we
investigate how valuable it is to flight operators to submit earlier than their competitor, although they may not
be in the position to submit their most accurate and up- to- date information at the time and therefore receive
an lower- utility allocation. We have also developed a third stated route preference model that is a hybrid of the
FIO and FSFA resource allocation schemes. The advantage of this model is that it preserves the FSFA reward
structure to a pre- specified degree but offers greater overall user cost efficiency. Finally, we have formulated
scenarios where the earliness restriction is binding. Preliminary numerical results reveal more interesting and
informative interactions between the models. Finally, we would like to improve the user cost model
specification such that it accounts for missed connections, or the downstream effects of flight delay.
Other questions we would like to address are as follows: How does the timing of traffic managers’ decisions
affect the quality of their decisions to the operators? Also, it is known that airlines update their flight
information constantly in the GDP and AFP databases. Given that their objectives and goals change so
continually and rapidly, how will this affect decision- making when the goal is to maximize their utility?
Addressing these questions is central to our on- going research efforts. As a result, it is important to continue
discussions with practitioners, in order to better understand and represent airline behavior within our
modeling framework.
This research investigates the interaction and information exchange between flight operators and FAA traffic
managers. The ultimate goal is to provide insight into the potential mechanisms of collaborative resource
allocation within the context of the AFP, in order to guide future AFP policy decisions.
Acknowledgments
The authors would like to thank the FAA for sponsoring this work. We would also like to thank Bob Hoffman,
Dennis Gallus, and Nathaniel Gaertner at Metron Aviation for their great assistance, insights, and suggestions.
Appendix
Show that flights with higher  values should be assigned to routes with lower en route times, and vice versa,
to obtain the optimal assignment solution to the optimal total AFP cost.
Order routes such that    >   Z > ⋯ >    ; #  = ⋯ = #  .
Based on ( 13), when flights with lower α assign to Route 1 ( higher ρ  ):
G ” = B   M  
    +( Q    + g  )⋅ } B  ( B  2+ 1) ~ + B Z (  M  
 + Q B  )   Z +( Q   Z + g Z )⋅ } B Z ( B Z 2+ 1) ~
+⋯+ B  (  M  
 + Q ( B  +⋯+ B  E  ))    +( Q    + #  )⋅ } B  ( B  2+ 1) ~
When flights with higher  assign to Route 1 ( higher O A   ):
G ” = H H [  M  
 + Q ⋅(  − H B h
 h
‘ b D  +  )]⋅    +

 D 
  D  #  
= H [ B   M  
 + B  Q ⋅(  − H B h
 h
D  )+ Q ⋅ B  ( B  2+ 1)]⋅    + #  ⋅ B  ( B 2  + 1)
  D 
= B   M  
    + B  Q    ⋅(  − B  )+( Q    + #  )⋅ } B  ( B  2+ 1) ~
+ B Z  M  
   Z + B Z Q   Z ⋅(  − B  − B Z )+( Q   Z + # Z )⋅ } B Z ( B Z 2+ 1) ~
+⋯+ B   M  
    + B  Q    ⋅(  − B  )+( Q    + #  )⋅ } B  ( B 2  + 1) ~
Note that all flights’ scheduled departure times have been omitted because they are identical in both the
allocations shown above.
Show ( 1) < ( 2).
B   M  
    +( Q    + #  )⋅ } B  ( B  2+ 1) ~ + B Z (  M  
 + Q B  )   Z +( Q O A  Z ¸ + # Z )⋅ } B Z ( B Z 2+ 1) ~
+⋯+ B  (  M  
 + Q ( B  +⋯+ B  E  ))    +( Q    + #  )⋅ } B  ( B  2+ 1) ~
< B   M  
    + B  Q    ⋅(  − B  )+( Q    + #  )⋅ } B  ( B  2+ 1) ~ + B Z  M  
   Z
+ B Z Q   Z ⋅(  − B  − B Z )+( Q   Z + # Z )⋅ } B Z ( B Z 2+ 1) ~ +⋯+ B   M  
   
+ B  Q    ⋅(  − B  )+( Q    + #  )⋅ } B  ( B 2  + 1) ~
We can remove some terms from both sides of the inequality:
+ Q B  Q E B  B  B  Z      Z + Q B  B [   [ + Q B Z B [   [ + Q B  B ¹   ¹ + Q B Z B ¹   ¹ + Q B [ B ¹   ¹ +⋯+ Q B  B     + Q B Z B     +⋯ +< Q Q B B   E B  Z B       +  E Q  B  B [    + Q B  B ¹    +⋯+ Q B  B     + Q B Z B [   Z + Q B Z B ¹   Z + Q B Z B º   Z +⋯+ Q B Z B    Z +⋯
Remove all Q from both sides:
B  B Z   Z + B  B [   [ + B Z B [   [ + B  B ¹   ¹ + B Z B ¹   ¹ + B [ B ¹   ¹ +⋯+ B  B     + B Z B     +⋯+ B  E  B     < B  B Z    + B  B [    + B  B ¹    +⋯+ B  B     + B Z B [   Z + B Z B ¹   Z + B Z B º   Z +⋯+ B Z B    Z +⋯+ B  E  B     E 
Rearrange terms:
+ B [ B ¹ (   ¹ −   B [  ) B + Z (⋯   Z +− B     B )  +(   B   − B [   (    ) [ +− B   Z  B )  +(   B  Z B − [   (   Z ) [ +−⋯   Z +)+ B  B E   B B ¹  (   (   ¹  −−      )  E +  ) B Z < B ¹ 0(   ¹ −   Z )
Since    >   Z > ⋯ >    , the above inequality holds true. ∎
We can point out that this solution holds when B  , B Z ,…, B  are optimal solutions to ( 2).
References
Andreatta, G., and Romanin- Jacur, G., 1987. Aircraft flow management under congestion. Transportation Science 21( 4),
249- 253.
Ball, M., Futer, A., Hoffman, R., and Sherry, J., 2002. Rationing Schemes for En- route Air Traffic Management.
[ memorandum] February 22 2002.
Ball, M. O., Hoffman, R., Odoni, A., and Rifkin, R., 2003. A Stochastic Integer Program with Dual Network Structure and its
Application to the Ground- Holding Problem. Operations Research 51( 1), 167- 171.
Ben- Akiva, M., and Lerman, S. R., 1994. Discrete Choice Analysis: Theory and Application to Travel Demand. Cambridge: MIT
Press.
Bertsimas, D., and Stock Patterson, S., 1998. The Air Traffic Flow Management Problem with Enroute Capacities.
Operations Research 46( 3), 406- 422.
Domencich, T. A., and McFadden, D., 1975. Urban Travel Demand: A Behavioral Analysis. Amsterdam: North- Holland.
FAA, 2007. Press Release - FAA Greatly Expands Air Traffic Program to Minimize Summer Delays. [ press release], May 23
2007, Available at: < http:// www. faa. gov/ news/ press_ releases/ news_ story. cfm? newsID= 8889> [ Accessed August
2010].
Goodhart, J., 2000. Increasing Airline Operational Control in a Constrained Air Traffic System. Ph. D. University of California
Berkeley.
Hoffman, R., Burke, J., Lewis, T., Futer, A., and Ball, M. ( 2005). Resource Allocation Principles for Airspace Flow Control.
San Francisco: AIAA Guidance, Navigation, and Control Conference and Exhibit.
Hoffman, R., Lewis, T., and Jakobovits, R., 2004. Flow Constrained Area Rerouting Decision Support Tool, Phase I SBIR: Final
Report. [ research report to NASA Ames] July 2004.
Jakobovits, R., Krozel, J., and Penny, S., 2005. Ground Delay Programs to Address Weather within En Route Flow
Constrained Areas. In: AIAA Guidance, Navigation and Control Conference and Exhibit. San Francisco, CA 15- 18 August
2005.
Leurent, F., 1993. Cost versus time equilibrium over a network. European Journal of Operations Research 71( 2), 205- 221.
Mayet, J., and Hansen, M., 2000. Congestion Pricing with Continuously Distributed Values of Time. Journal of Transport
Economics and Policy 34( 3), 359- 369.
Mukherjee, A., and Hansen, M., 2009. A dynamic rerouting model for air traffic management. Transportation Research Part
B 43( 1), 159- 171.
Richetta, O., and Odoni, A. R., 1993. Solving Optimally the Static Ground- Holding Policy Problem in Air Traffic Control.
Transportation Science 27( 3), 228- 238.
Bureau of Transportation Statistics ( BTS), 2007. Airline On- Time Statistics and Delay Causes. [ online] Available at
< http:// www. transtats. bts. gov/ OT_ Delay/ OT_ DelayCause1. asp> [ Accesed April 11, 2009].
Taber, N. J., 2006. Operational Concept for Integrated Collaborative Rerouting ( ICR). [ research report] May 2006.
Train, K., 2003. Discrete Choice Methods with Simulation. New York: Cambridge University Press.
Vossen, T., Ball, M., Hoffman, R., and Wambsganss, M. ( 2003). A General Approach to Equity in Traffic Flow Management
and its Application to Mitigating Exemption Bias in Ground Delay Programs.