
small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


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 nonbinding 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, firstassigned 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.
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  A framework for the assessment of collaborative enroute assistance allocation strategies 
Subject  TA1001.C794 no. 20102; Air traffic controlUnited States.; Group decision makingUnited States. 
Description  "Month 2010."; Includes bibliographical references. 
Creator  Kim, Andy. 
Publisher  Institute of Transportation Studies, University of California 
Contributors  Hansen, Mark.; University of California, Berkeley. Institute of Transportation Studies. 
Type  Text 
Language  eng 
Relation  Available online.; http://www.its.berkeley.edu/publications/UCB/2010/WP/UCBITSWP20102.pdf; http://worldcat.org/oclc/677255173/viewonline 
DateIssued  [2010] 
FormatExtent  [23] leaves : ill., col. charts ; 28 cm. 
RelationIs Part Of  Working paper, UCBITSWP20102; Working paper (University of California, Berkeley. Institute of Transportation Studies) ; UCBITSWP20102. 
Transcript  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 nonbinding 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, firstassigned 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. 



B 

C 

I 

S 


