Description
In mathematics and civil engineering, traffic flow is the study of interactions between vehicles, drivers, and infrastructure (including highways, signage, and traffic control devices), with the aim of understanding and developing an optimal road network with efficient movement of traffic and minimal traffic congestion problems.
TECHNICAL RESEARCH REPORT
The Rate Control Index for Traffic Flow
by Robert L. Hoffman, Michael O. Ball
NEXTOR TR 2001-1 (ISR TR 2001-24)
NEXTOR
National Center of Excellence in Aviation Operations Research
The National Center of Excellence in Aviation Operations Research (NEXTOR) is a joint university, industry and Federal Aviation Administration research organization. The center is supported by FAA research grant number 96-C-001. Web site http://www.isr.umd.edu/NEXTOR/
The Rate Control Index for Tra?c Flow
Robert L. Ho?man, Michael O. Ball
March 26, 2001
?
Abstract: The objective of Air Tra?c Flow Management is to maintain safe and e?cient use of airspace and airports by regulating the ?ow of tra?c. In this paper, we introduce a single-valued metric for post-operatively rating the performance of achieved tra?c ?ow against targeted tra?c ?ow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how these improve on current tra?c control analysis techniques. The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be e?ciently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric. Although this metric was originally developed to rate the performance of Ground Delay Programs, it is equally applicable to any setting in which the ?ow of discrete objects such as vehicles is controlled and later evaluated.
?
Robert Ho?man is a senior analyst with Metron Scienti?c Consulting, 11911 Freedom
Drive, Reston VA 20190. Email: [email protected]. Michael Ball holds a joint appointment with the Robert H. Smith School of Business and the Institute for Systems Research at the University of Maryland, College Park, MD 20742. Email: [email protected].
1
Introduction
The ?ow of tra?c through airspace sectors and through airports is regulated by air tra?c ?ow managers to ensure that airspace components do not become overloaded and that throughput is maintained. Many of the short-term demand-capacity inequities in the NAS are smoothed out by FAA tra?c ?ow managers by tactics such as vectoring and miles-in-trail restrictions. Longerterm demand-capacity inequities (on the order of several hours) are more problematic. These usually occur when an airport acceptance rate is drastically reduced because of inclement weather, airport construction, or special runway operations. In these instances, air tra?c ?ow managers at the FAA employ ground holding strategies in which aircraft bound for an a?icted airport are held at their points of origin in lieu of costly and hazardous airborne holding that would occur if they were allowed to depart on schedule. The most prominent of these strategies is the ground delay program (GDP), which is an initiative taken by the FAA to lower the arrival rate to a level that can be safely handled by airport controllers. The increase in air tra?c in the United States over the last 20 years has necessitated more frequent use of tra?c ?ow management initiatives. For instance, in 1998, there were 187 ground delay programs run at San Francisco airport alone [1]. As a result, there has been considerable interest both in the aviation and research communities regarding tra?c ?ow management and its analysis. The issues of deepest concern have been the e?cient use of airport landing resources and the equitable distribution of arrival slots among competing airlines [2]. Substantial e?orts have been under way since the mid 1990’s to revamp the manner in which tra?c ?ow initiatives are 2
planned and executed. Most notable is the joint industry-FAA Collaborative Decision Making project (CDM), which has made major changes to GDP procedures. See [3] for details on ground delay program enhancements. One can see the need to assess the quality of tra?c control actions. In this paper, we provide practical solutions for three major aspects of postoperative, tra?c ?ow analysis. The ?rst aspect is the need for a simple way of contrasting aggregate tra?c ?ow with desired tra?c ?ow. We introduce the rate control index (RCI), which gives a single performance value to the ?ow of tra?c into an airport or sector of space as compared to the planned ?ow of tra?c. The rate control index bears an intuitive relation to the events that have lead to the deviation from the plan. In essence, the metric tracks the aggregate ?ight movements that have caused the realized tra?c ?ow to di?er from the planned tra?c ?ow. Although the basic concept behind the metric is easily understood, the normalization of the metric leads to an interesting optimization problem. The second aspect is the need to factor out from post analysis major stochastic factors upon which a control action is based. Every tra?c ?ow initiative is based on forecasts of demand and resource capacities, which are often not realized because they depend upon highly stochastic conditions. Air tra?c demand predictions, such as the number of arrivals to an airport, are vulnerable to airline operational deviations while capacity predictions for airspace sectors, runways, etc., are highly subject to weather conditions. Direct measurement of tra?c control actions is not always the best way to judge the performance of a new program or initiative; naive or ill-chosen metrics are heavily in?uenced by the quality of the forecasts upon which a
3
plan of action was based. For instance, in a GDP, the objective is to deliver a speci?ed number of aircraft to the airport during a ?xed time horizon. The metric generally used by tra?c ?ow managers for program evaluation is landings-per-hour [4]. If runway conditions turn out to be more severe than previously forecasted, then this metric will (correctly) reveal that the realized landing rate does not match the desired landing rate. However, to a large degree, the program performance was beyond the control of participating parties and is being judged in part by the forecast upon which it was based. For situations such as this, we show how to meter tra?c ?ow into an airport independently of the ability of the airport to land aircraft. The third aspect of tra?c ?ow analysis we address is the need for a metric that rates the performance of a group of controlled ?ights on a more individual basis than aggregate metrics. Directives are given to individual ?ights (altering ?ight paths, arrival times, etc.) in order to a?ect the aggregate ?ow of tra?c. Final success of these e?orts is typically measured using aggregate metering of tra?c. When the desired tra?c ?ow is achieved, the question arises whether or not this was due to the adherence of aircraft to their controlled arrival times or due to the fortuitous cancellation of early arrivals with late arrivals. To address this issue, we present a nominal version of the RCI metric that acts as a complement to the aggregate version of the metric. Section 2 of this paper provides motivation for the metric and an interpretation of its meaning. The rigorous formulation of the metric and its normalization process are deferred to Section 3. Section 4 demonstrates the application of both the nominal and aggregate versions of the metric to Ground Delay Program analysis. Conclusions are in Section 5.
4
2
The Core of the RCI Metric
The perspective taken in this paper is one of post-analysis. We view a tra?c ?ow initiative as a plan of action which is to be later analyzed for e?ectiveness. We assume that a tra?c ?ow manager has set a goal for each time period t = 0, 1, ..., T of a time horizon, meaning the number of vehicles that should be delivered to an airport (or more generally, pass through a region of airspace). A plan is enacted to achieve these goals. Once the time horizon has passed, the actual number of ?ights is recorded. This establishes two distributions: the planned distribution P = (p0 , p1 , ...pT ) and the realized distribution R = (r0 , r1 , ...rT ), where pt and rt are the planned and realized number of ?ights during time period t, respectively. The question is how to weigh the performance of the realized distribution against the planned distribution. We branch into two areas of concern, separated by a subtle but crucial distinction. One is the desire to measure program performance. Once a GDP is formulated, there are many factors that must fall into place in order for the GDP to be executed as planned. It is the duty of the controllers in the local tra?c management units to hold ?ights at their departure airports until their controlled times of departures. The airlines must notify passengers of the imposed ground delay and yet have them boarded and ready to takeo? at their controlled departure times without further delay. Pilots must maintain an enroute airspeed commensurate with that was used in the forecast of their enroute times. One can see that there are many entities that participate in the execution of the plan other than the tra?c ?ow specialists that have formulated the plan. A great deal of e?ort has been spent by the CDM com5
munity in improving GDP practices and performance. They have expressed a need to measure the execution of GDPs independent of the quality of its plan [5]. The other area of concern is the desire to measure program impact, meaning the e?ect that program performance has had on the system. Ideally, we would like a metric that produces a single, normalized value for the performance or impact of a program, so that programs can be tracked over long periods. This is especially valuable for discerning the e?ect of proposed program changes. Moreover, the metric should have a natural, intuitive interpretation to which cost bene?ts can be applied. Given the planned and realized distributions, P and R, a straight forward approach to distribution comparison is to form a distribution of errors E = P ? R = [p0 ? r0 , p1 ? r1 , ..., pT ? rT ] (1)
by vector subtraction, then to analyze the variance of the errors by averaging over the time periods or summing the squares of the deviations. Consider the planned distribution P = (30, 30, 30, 30, 30) of airport arrivals, meaning that 30 ?ights are intended to arrive in each of ?ve hours. Suppose that the actual number of arrivals per hour is given by R1 = (30, 30, 30, 31, 29). In this case, average error per hour is a poor measure; the excess of one ?ight in hour 4 cancels out with the shortage of one ?ight in hour 5 to produce a zero average. A more viable alternative is to compute the average absolute error, as below. Avg. Abs. Error = |0| + |0| + |0| + |1| + |?1| 5 2 = = 0.40 ?ights per hour 5 6 (2)
Although (2) correctly records an overdelivery in hour 4 and an underdelivery in hour 5, it fails to capture the events that have lead to R1 . Speci?cally, since 31 ?ights have arrived in hour 4 and only 29 in hour 5, then there must have been (in the aggregate) a migration of one ?ight from hour 4 to hour 5. The alternative measure of variance that we propose is to record the aggregate ?ight movement, or drift, that led to the deviation of R from P . This is the same as the minimum amount of ?ight movement that would be necessary to revert R to P . This can be viewed as an alternative way of measuring the di?erence between two distributions. This type of approach makes distinctions between realized distributions that (1) does not. For instance, consider the ?ight movements necessary to convert R2 = (31, 30, 30, 30, 29) into P . Since 31 ?ights arrived in the ?rst hour when only 30 were intended, one of the ?ights intended to arrive in a later hour arrived in hour 1. Let’s credit the participants with the least errors possible and say that this ?ight was intended to arrive in hour 2. Since 30 ?ights arrived in hour 2 instead of 30 ? 1 = 29, one of the ?ights intended to arrive in hour 3 must have arrived in hour 2. Similarly, one ?ight intended to arrive in hour 4 arrive in hour 3, and one ?ight intended to arrive in hour 5 arrived in hour 4. In all, we see that, as a minimum, there was a total migration of ?ve ?ight-hours. Note that if we computed average absolute error, as in (2), then R2 would receive the same rating as R1 , 0.40 ?ights per hour. In contrast, the aggregate ?ight movement method recognizes that four times as much movement has taken place in R2 as in R1 . The subtraction-based method (1) double-counts a single ?ight in hour 5. It can be argued that this correctly models the impact of the realized
7
distribution on the system, namely that the system is stressed in hour 4 and underutilized in hour 5. But this is based on the assumption that the airport capacity in each hour is as predicted, 30 aircraft per hour. Since 31 aircraft were accommodated in hour 4, the capacity of the airport clearly was not limited to 30 ?ights. Conversely, it is fairly common for an airport to accept fewer ?ights than were planned because airport acceptance rates are based not just on weather conditions and runway con?gurations, but also on departure demand and the abilities of air tra?c service providers. For this reason, it can be di?cult, if not impossible, to know what the actual airport capacity was, based solely on realized arrival rates. If these rates are known, metric (1) could be considered. The approach described in this paper primarily compares the planned distribution against the realized distribution, and not against the airport acceptance rate distribution. The main idea is to assess how closely the plan was followed. For a given planned distribution, P , and a realized distribution, R, the method is based on shifting aircraft in the R distribution to transform it to the P distribution. The rate control index (RCI) metric is the outcome of this method. The following example shows how the RCI metric would be computed in practice and how cost parameters can be applied. In Section 4, we show how to remove the e?ects that the air tra?c service providers at the airport may have had on the realized distribution. Section 3 covers the more complex aspects of the mathematics involved. Example: Suppose that a 4-hour GDP is planned and that the planned arrival acceptance rate (PAAR) for each of those 4 hours is 30 ?ights. Then the planned distribution is P = (30, 30, 30, 30) . Further suppose that the
8
Figure 1: Flight movements necessary to transform R into P
actual number of ?ights that arrived at the airport (or the airport terminal space) is given by R = (27, 32, 35, 24) . Then the rate control index for R (relative to P ), denoted RCI (P, R), is computed via the following two-part calculation. Part 1: Compute the di?erence P ? R. This is the minimum amount of ?ight movement that is necessary to turn R into P . We sweep left to right through R (increasing t), moving as many ?ights (say ft+1 ) as necessary from rt to rt+1 to achieve rt = rt ? ft+1 = pt . Counting left-hand movements as negative and right-hand movements as positive, we must move 3 ?ights from hour 1 to hour 0 (f1 = ?3), move 1 ?ight from hour 2 to hour 1 (f2 = ?1), and move 4 ?ights from hour 2 to hour 3 (f3 = 4). See Figure 1.
9
Movement Hr 0 ?? Hr 1 Hr 1 ?? Hr 2 Hr 2 ?? Hr 3 Hr 3 ?? Hr 4
Notation Flight-hours f1 f2 f3 f4 -3 -1 4 -2
Table 1: Summary of ?ight movements through time So far, R has been transformed into the distribution, R = (30, 30, 30, 28). Note that this is 2 ?ights short of the desired distribution, because pt ? rt = 120 ? 118 = 2. We create a “slush fund” of 2 ?ights at the end of R to compensate for the lack of conservation of ?ights. Equivalently, we could have started with an augmented distribution R = (27, 32, 35, 24, 2). Similarly, we extend P to a ?ve-hour distribution, P = (30, 30, 30, 30, 0). To complete the example, we move 2 ?ights from hour 4 to hour 3 (f4 = ?2). The summary of ?ight-movements is given in Table 1. We defer to Section 3 the formal proof that this correctly computes the minimum cost transformation. Now we can compute the cost of transforming R into P . Let c? be the average cost (say, in dollars per hour) of delaying a ?ight for one unit of time and let c+ be the average cost (say, in dollars per hour) of a ?ight arriving early by one unit of time. Then we break the ?ight-movements into left-hand movements M ? = |?3| + |?1| + |?2| = 6 and right-hand movements M + = 4, corresponding to tardiness and earliness, respectively. The ?nal cost is given by c? M ? + c+ M + = 6c? + 4c+ . (3)
In this example, we opt to set c? = c+ = 1.0 to obtain pure units of 4 + 10
6 = 10 ?ight-hours. In other words, R was o? from P by 10 ?ight-hours. Intuitively, this means that in order to turn R into P , one would have to do the work equivalent to moving 1 ?ight 10 hours, or 2 ?ights 5 hours, etc. One variation on the metric is to retain the positive and negative sums to show the breakdown of this total. Part 2: Normalize the distribution error P ? R . To compare GDPs of di?ering lengths and number of ?ights, we normalize by dividing the distribution error by the cost of the worst-case scenario. This means we must ?nd the ?ve-hour redistribution W of the 120 ?ights in P with the highest cost difference, P ? W . In general, this involves solving a max-min problem, which is covered in Section 3. For now, we take as a given that W = (0, 0, 0, 0, 120) with a cost of P ? W = (|?4| + |?3| + |?2| + |?1|) × 30 = (10) × 30 = 300 ?ight-hours. (W corresponds to the scenario in which all the ?ights land in the ?nal hour.) Thus, the rate control index we assign to the distribution R is 10 ?ight-hours = 0.033. 300 ?ight-hours (5) (4)
Since we have kept pure cost parameters of 1.0, this is a pure ratio that indicates the error of the realized distribution. In order to make the index more palatable, we phrase the performance of the realized distribution in terms of what was achieved rather than what was not achieved. Subtracting from 1.0, we obtain a ?nal rate control index (RCI) of Since we have kept pure cost parameters of 1.0, this is a pure ratio that indicates the error of the realized distribution. In order to make the index 11
more palatable, we phrase the performance of the realized distribution in terms of what was achieved rather than what was not achieved. Subtracting from 1.0, we obtain a ?nal rate control index (RCI) of RCI (P , R) = 1.0 ? .0333 = 0.966 (6)
If preferred, this ?nal index can be transformed into a percentage, 96.67%. The interpretation of the index is that the realized distribution achieved 96.67% of the intended (planned) distribution. This number can then be used for comparing GDP performance on di?erent days and lends itself nicely to trend analysis (see Section 4.
3
Formulation and Computation of the RCI Metric
In Section 2, we provided motivation and intuition for the RCI metric. In this section, we provide a more rigorous formulation of the RCI metric and show how to correctly compute the cost of the worst-case distribution in the normalization process. Also, we discuss the nuances behind normalization of the metric with respect to distribution length and mass.
3.1
The Raw RCI Score: Comparing Two Distributions
We de?ne a distribution to be a (T + 1)-tuple of nonnegative numbers and we de?ne its mass to be the sum of its entries. Let D and D be two distributions 12
that we wish to compare using the RCI metric. Based on the motivation provided in Section 2, we have chosen to represent the transformation of D into D by a T -tuple, F = (f1 , f2 , ..., fT ), where ft is the amount of mass necessary to move from dt?1 to dt . Speci?cally, dt receives an increment of ft units from dt?1 and sends ft+1 units to dt+1 . The net increment for period t is ?t = dt ? dt , as illustrated in Figure 2. Thus, in order to transform dt into dt the following condition must hold: dt + ft ? ft+1 = dt (7)
Note that ft can be positive or negative. Given D and D , F can by computed by initializing f1 using f1 = d0 ? d0 and then recursively applying, ft = dt?1 ? dt?1 + ft?1 for t = 2 to T . Alternatively, we can compute F directly from
t
(8)
(9)
ft =
s=1
(ds?1 ? ds?1 ) for t = 1, 2, ..., T.
(10)
If D and D do not have the same mass then, prior to computing F , their masses should be equalized by adding a (T + 2)nd component to each distribution. This extra component should have zero mass in the larger of the two masses and should have a mass equal to the nonnegative di?erence of their masses in the smaller of the two distributions. T is then incremented by one. Intuitively,
T t=1
|ft | is the amount of work necessary to transform D to
D . If we multiply the positive and negative values of ft by cost parameters 13
c+ and c? , respectively, then the cost of ft is given by cst(ft ) = c+ max {ft , 0} + c? max {?ft , 0} and the total cost of the transformation is computed via
T
(11)
C (D, D ) =
t=1
cst(ft )
(12)
which serves as the unnormalized, or raw, RCI score. Note that this expression is well-de?ned since for a given pair of distributions, D and D , F is unique. One can see from (12) that if C (D, D ) is given by ac+ + bc? , then C (D , D) is given by bc+ + ac? . This means that whenever c+ = c? , the cost of transforming D into D may not be the same as the cost of transforming D into D. For this reason, care must be taken when comparing multiple distributions against a baseline distribution: the direction of transformation should be made consistent. It is interesting to note that the computation of F could be recast as a network ?ow problem de?ned on a simple linear network with non-negative ?ow variables, xt and yt , where ft = xt + yt . In Figure 2, one would replace each arrow ft with a right arrow (xt ) and a left arrow (yt ). The vector F corresponds to an acyclic ?ow, i.e., a ?ow in which for each t, at most one of xt and yt is nonzero. An acyclic ?ow is optimal as long as the ?ow costs are non-negative (see [6] for an analysis of ?ow problems on linear networks and see [7] for a treatment of general network ?ow problems).
14
3.2
3.2.1
Normalization of RCI
The Worst-case Scenario
In the motivating example of Section 2, we saw that the normalization step of the RCI computation requires that we ?nd the redistribution W of a ?xed distribution P with the worst-case (maximum) value, C (W, P ). Consequently, we must consider any restrictions that may exist on the worst-case W . In the air tra?c management case, we can assume that there is an earliest possible arrival time for each aircraft. This time is usually the scheduled arrival time of the ?ight. Let B = (b0 , b1 , ..., bT ) be the distribution of earliest possible arrival times of the ?ights. That is, bt is the number of ?ights with an earliest arrival time in the tth time period. Note that for a ?xed time interval t, the cumulative number of aircraft that can arrive in time periods s = 0, 1, ..., t is limited by
t s=0 bs .
This means that vector W is restricted by Ws ? Bt for all t, (13)
where for any distribution E = (e0 , e1 , ..., eT ), we have de?ned the following partial sum notation:
t
Et =
s=0
es for t = 0, 1, ..., T.
(14)
B is said to be a (leftward) bounding distribution for P . Since there is no limit to how late a aircraft could arrive, there is no need to analogously de?ne a rightward bounding distribution. Let ?B be the set of redistributions of P that are restricted by (13). Then E ? ?B , if and only if E can be obtained from B by making strictly rightward shifts in B . For example, if P = (0, 3, 3) and B = (1, 2, 3), then (0, 0, 6) ? ?B while (3, 0, 3) ? / ?B . 15
Recall that our approach to the normalization of the RCI metric is to divide the cost of transforming a distribution E into a target distribution P , C (E, P ), by C (W, P ), where W is the worst case (highest cost) scenario. We assume that all distributions are rightward shifts of the distribution B so we seek a solution to max C (W, P ) | W ? ?B . (15)
We note that (15) is a max-min problem, since (C (W, P ) is the optimal objective value of a minimization problem. In the next section, we show how to solve this max-min problem by dynamic programming. 3.2.2 A Dynamic Programming Solution
Let distribution P = (p0 , p1 , p2 , ..., pT ) be given, along with bounding distribution B = (b0 , b1 , b2 , ..., bT ). We wish to write a recursive relation for ?nding a solution to (15) in the case where all distributions are integer. Fix an index t ? T and an integer amount of mass ? ? 0. Consider the truncated vector P t = (p0 , p1 , p2 , ..., pt ) . The subproblem we de?ne is to ?nd a truncated vector W t = (w0 , w1 , w2 , ..., wt ) of mass ? such that C (W t , P t ) is as expensive as possible. We denote this maximum cost by Cmax (t, ? ). To form the basis of a dynamic programming algorithm, we now derive a recursive relation to compute Cmax (t, ? ). See Figure 3. Based on our notation, (W t )t?1 is the (t ? 1)st partial sum of the vector W truncated at t. For a ?xed ? , the mass of (W t )t?1 can range over the values m = 0, 1, ..., Bt?1 ? ? . For each value of m, (10) dictates that the value of ft is uniquely determined by ft = (W t )t ? (P t )t?1 = m ? Pt?1 . This means that the value of Cmax (t, ? )
16
is related to Cmax (t ? 1, m) via the following recursion:
? ? ? ??, ? ? ? ?
if ? > Bt or t > T if t = 0 and ? ? Bt ?, otherwise (16)
Cmax (t, ? ) =
? ? ? ? ? ?
0,
m=0,1,...,?
max
where ? = {C (t ? 1, m) + cst (ft ) | ft = m ? Pt?1 }. The ?rst case in (16) prevents ? and t from taking on ill-de?ned values and the second case initializes the recursion. The third case expresses the fundamental recursion. The solution to our problem, (15), is given by Cmax (T, PT ). This recursion might seem simple, even trivial, since ft does not vary in the max operation. However, the complexity of this problem lies within the restrictions imposed by the bounding distribution B , which limits the values to which the max operation is applied. In fact, without, this restriction, extreme or trivial solutions would always result. Note that for a given ? and t, the computation of Cmax (t, ? ) is dependent upon the values Cmax (t ? 1, 0) , Cmax (t ? 1, 1) , ..., Cmax (t ? 1, ? ) (17)
This structure leads naturally to a forward recursion, dynamic programming algorithm. If we let S be the total mass in P , then the running time of such an algorithm is at most O(T S 2 ) since there are at most O(T S ) Cmax ( ) values to be computed and the computation of each one requires at most O(S ) comparisons.
17
Figure 2: Transformation of distribution D into distribution D by vector F
Figure 3: Finding the highest cost redistribution W when the partial sumWt?1 is set to ?
18
4
Ground Delay Program Analysis
In this section, we demonstrate the application of the RCI metric in the context of ground delay programs.
4.1
Modelling Air Tra?c Flow into an Airport
A Ground Delay Program (GDP) is an FAA tra?c ?ow action to reduce the ?ow of aircraft into an airport. A GDP is implemented whenever it is predicted that the arrival demand at an airport will exceed the arrival capacity for a signi?cant period of time. In essence, ?ights bound for a single airport are held at their origin airports so that they can be accepted to enroute and terminal area tra?c ?ows without delay. A light amount of airborne holding during times of reduced capacity is considered desirable because it ensures that airport arrival resources are being fully utilized. However, excessive airborne holding queues are considered undesirable because of the added workload on air tra?c controllers. Aircraft must be physically separated, placed in and out of layered holding patterns, and monitored for su?cient fuel reserves. Most GDPs are prompted by adverse weather conditions that can dramatically reduce the airport acceptance rate (AAR). Other causes are runway construction and special airport operations. GDPs are planned several hours in advance and can run for periods as long as 12 hours. For more background on ground delay programs and the ground holding problem, see [8], [9], [10], [11], [12]. Since the primary purpose of a GDP is to control the rate of aircraft ?ow
19
into an airport, the typical metric for evaluating the performance of a GDP is to measure the actual landings-per-hour (LAN Dt , where t varies over the discretized time intervals over which the GDP operated) against the planned landings per hour (P AARt ). Although this is often taken to be the “bottom line” in a GDP, it is in fact a hybrid analysis that blurs the appropriateness of the plan with the execution of the plan. The ability of air tra?c service providers to land aircraft is directly related to airport conditions and runway con?guration. These are, in turn, dependent upon weather conditions, which are highly stochastic. If weather conditions turn out to be worse than expected, then airport capacity is lower than forecasted and the desired arrival rate will not be achieved. If we measure program performance strictly by landings-per-hour, then we are e?ectively holding program participants responsible for the quality of the forecasts upon which the program was based. There needs to be a mechanism to analyze the success with which the plan was executed, independently of the appropriateness of the plan and the forecasts upon which it was based. (See [13] for treatment of stochastic airport capacity.) The solution to removing stochastic airport conditions from measurement is to meter the tra?c ?ow at a point close to the airport but before it could be directly a?ected by airport capacity. Ideally, we would like to know for each ?ight how much airborne holding it incurred as a result of restricted airport capacity. From this we can compute the time it would have arrived at the airport in the absence of airport capacity restrictions. Holding data is recorded by air tra?c service providers, but only when work conditions allow them su?cient time to do so. Hence, FAA ?ight holding databases are
20
often incomplete. As a surrogate for this holding data, several approaches can be used. A general idea is to de?ne a radius of geographical distance (or time) about the airport and declare that once a ?ight has passed over this boundary, it has been delivered to the airport. This should be the smallest possible radius that captures all, or most of, the airborne holding. For many airports, the holding location for a ?ight varies with the airport arrival ?x over which the ?ight will pass. The radius may have to be ?ight-path speci?c. Such a model can use as input readily available ?ight data, such as that provided by the Enhanced Tra?c Management System (ETMS). For each ?ight, ETMS provides a runway departure time, a runway arrival time, and a sequence of estimated arrival times (ETAs), as the ?ight moves along its ?ight path [14]. We assume the existence of a model that will estimate, post facto, for each ?ight f the amount of airborne holding that it incurred, which we denote ABHf (see [15] for one such model). From this, we can deduce that f was in a state of airborne holding at a given time t < ART Af if and only if ABHf ? ART Af ? t, where ARTA is the actual runway time of arrival as recorded by ETMS. For a set of contiguous time intervals t = 0, 1, ..., T , let DELt be the number of ?ights delivered to the airport during time interval t, meaning, the number of ?ights that would arrive given unlimited capacity. Let ABHt be the number of ?ights that are in a state of airborne holding at the end of interval t. Let LAN Dt be the number of ?ights that land during time period t. If we view the airport as a closed network, then we have the following
21
elementary relationship for each t (see Figure 4). DELt = (ABHt ? ABHt?1 ) + LAN Dt (18)
After a GDP, three distributions can be assembled: P AAR, DEL, and LAN D. In the case study that follows, we use RCI (P AAR, LAN D) to measure general program performance and we use RCI (P AAR, DEL) to measure program performance independent of stochastic airport conditions.
4.2
The Aggregate Version of RCI
Figure 5 shows a graphical analysis of the performance of a ground delay program (GDP) conducted at San Francisco airport (SFO) on March 5, 1998. The planned acceptance rate of ?ights (the P AAR distribution) was set at 32 ?ights per hour for each of the six hours of the GDP. The RCI value assigned to this GDP was 88.24%. Since this is below the 1998 RCI average for SFO, approximately 92.0%, it would be a likely candidate for further analysis. The RCI value of 88.24% was computed based on P AAR versus DEL, the distribution of “?ights delivered” to the terminal airspace of the airport (but not necessarily landed). The cost parameters were set to c+ = c? = 1.0, to obtain pure ?ight-movement units. Also shown are the distributions LAN D, ?ights landed at the airport, and ABH, the size of the airborne holding queue at the end of each hour. Figure 5 shows why the RCI(PAAR, DEL) was not closer to the optimal value, 100%. There were too many ?ights delivered to the airport early in the program: in the ?rst hour, 41 ?ights were delivered when only 32 were intended. One possible explanation for this is that the GDP was implemented 22
too late and some of these 41 ?ights were already airborne when the program was planned, hence, they could not have been held on the ground. Some of these ?ights may have been assigned ground holds but departed too early, but this is a less likely explanation. Moreover, there were drastically too few ?ights delivered in the 2100 (zulu) hour: 16 ?ights compared to the desired 32. Some of the ?ights intended to arrive in hour 2100 may have arrived in hour 2000. Note the increase in the airborne holding queue size in hour 2100 hour as a result of high arrival volume in hour 2000. One can see that the LAN D distribution more closely follows P AAR than does DEL. Thus, the value of RCI (P AAR, LAN D) (not computed) would be slightly better than RCI (P AAR, DEL). This is not uncommon: some of the arrival ?ow is smoothed out by airborne holding, resulting in a smoother distribution. An interesting feature of this GDP was that, during hour 2100, even with the pressure of a substantial airborne holding queue, the airport was able to land only 23 ?ights, instead of the forecasted number, 32. Airport tower tra?c counts con?rm that the controllers at the airport favored departures during the 2100 hour.
4.3
The Nominal Version of RCI
In this section, we demonstrate the use of a nominal version of the rate control index. For each ?ight f , we compute the amount of arrival delay, Mf via Mf = |actual arrival time ? planned arrival time| . (19)
23
Figure 4: Model of an airport as a closed system
Figure 5: Analysis of ground delay performance at San Francisco Airport, 3/5/98
24
The unnormalized RCI score is
f
M (f ), which represents the amount of
?ight movement through time that would be necessary to restore all ?ights to their planned arrival time. This number is normalized by dividing by the cost of the worst-case scenario,
f
W (f ), where W (f ) is the largest deviation
that could have occurred for ?ight f (i.e., the farthest time period in either direction from its planned period of arrival). The ?nal value is subtracted from 1.0 and multiplied by 100%. If desired, the positive delays (Mf > 0) and negative delays (Mf < 0) can be weighted with cost parameters c+ and c? before summing, as was done with the aggregate version of the metric. In the examples shown in this section, we have elected to set c+ = c? = 1.0 so that
f
M (f ) represents the (absolute) variance of ?ight arrivals from their RCI N om , RCI Agg , for a
planned arrival times. Each point in Figure 6 is an ordered pair,
GDP run at SFO during the period January 1 to October 28, 1998. Consider the point (64, 92) for July 10. The value RCI Agg = 92% indicates that, in the aggregate, the distribution of landed ?ights closely matched the desired distribution. However, the low value of RCI N om reveals that, too often, the ?ights that landed in a given time interval were not the ?ights that were intended to land in that time interval. Some of the ?ights arrived earlier than planned while others arrived too late. On the whole, for any given time interval, the number of ?ights that migrated out of a time interval was almost equal to the number of ?ights that migrated into that time interval, hence, the aggregate numbers of ?ights were preserved. The stochastic processes cancelled each other out and there was a great deal of ‘luck’ involved in achieving the high value of RCI Agg = 92%.
25
Figure 6: Nominal and aggregate RCI values for Ground Delay Programs at SFO, January - October, 1998
26
In general, points in the upper right quadrant of Figure 6 correspond to programs in which the aggregate distribution of ?ights was achieved and most of the ?ights arrived in their expected time periods. These are the best-run programs, the goal of each program being (100%, 100%). Given two points (x1 , y1 ) and (x2 , y2 ), with x1 < x2 and y1 = y2 , we can say that they had the same level of aggregate success but that the ?rst program involved more ‘luck’ while the second program involved more ‘skill’. The center of mass of the squares lies at about (82, 92), marked by the cross. This indicates that the overall ground delay performance at SFO is quite good. In general, RCI N om is about 10% less than RCI Agg . Note that all of the points lie above the 45-degree line. This is to be expected since as RCI N om increases, more ?ights are arriving in their planned arrival periods and so the aggregate distribution of ?ights is more likely to match the planned distribution, which also increases the value of RCI Agg . Note that when RCI N om = 100%, the only way for RCI Agg to fall below 100% is for there to be arrivals that were not anticipated by the GDP.
5
Closing Remarks
We have introduced a new metric for the evaluation of planned versus realized tra?c ?ow for a region of space or an airport. In its most general form, the metric generalizes to a comparison of two ?nite distributions, hence, has the potential for use in any area of tra?c management in which vehicular movement through time is regulated. This represents a substantial improvement over the standard techniques for comparing two ?nite distributions. The met-
27
ric naturally lends itself to intuitive interpretation (when decomposed into left and right-handed movements) and to cost evaluation. The development of an aggregate and nominal version of the metric captures the two crucial aspects of tra?c ?ow management: how many ?ights ?owed through a region of space and which ?ights ?owed through the region. Also, we have shown how to apply the metric to factor out the e?ects of inaccurate forecasts from performance analysis of a tra?c ?ow initiative. We showed how to compensate for controlled ?ights that arrive outside the planned time horizon by augmenting the realized distribution. The intuitive justi?cation for this was that the cost added is assessed at a rate commensurate with the wasted capacity due to these ?ight cancellations. However, there doesn’t seem to be an analogous compensation for the case in which unanticipated ?ights arrive within the planned time horizon. For consistency with ?ight shortages, the logical adjustment for these pop-up ?ights would be to augment the planned distribution. Unfortunately, the added cost would be assessed at a rate commensurate with the movement of ?ights backward in time, for which there is no intuitive obvious justi?cation. In practice, pop-up ?ights comprise a small enough percentage of the total ?ights that their e?ect on the RCI metric is minimal when they are ignored. However, future development of the metric should incorporate pop-up ?ights.
6
Acknowledgements
This work was funded by the Federal Aviation Administration (FAA) through NEXTOR, the National Center of Excellence for Aviation Operations Re-
28
search. The opinions expressed herein are solely those of the authors and do not re?ect the o?cial position of the FAA.
References
[1] Ground delay program summaries, available at the CDM web site, http://www.metsci.com/cdm. [2] M. O. Ball, R. L. Ho?man, C. Y. Chen, and T. Vossen, “Collaborative decision making in air tra?c management,” in Proceedings of Capri ATM-99 Workshop, 1999. [3] R. L. Ho?man, M. O. Ball, A. R. Odoni, W. D. Hall, and M. Wambsganss, “Collaborative decision making in air tra?c ?ow management,” available at the NEXTOR web site, http://www.nextor.umd.edu. [4] Personal conversations and interviews with tra?c ?ow managers at the FAA’s Air Tra?c Control System Command Center in Herndon, Virginia. [5] Minutes of the Collaborative Decision Making Analysis Subgroup, available at http://www.metsci.com/cdm. [6] M. O. Ball and M. J. Magazine, “Sequencing of insertions in printed circuit board assembly,” Operations Research, 1998. [7] R. Ahuja, T. Magnanti, and J. Orlin, Network Flows, Prentice Hall, 1993.
29
[8] R. L. Ho?man, Integer Programming Models for Ground-Holding in Air Tra?c Flow Management, Ph.D. thesis, University of Maryland, 1997. [9] A. R. Odoni, L. Bianco, and G. Szego, Eds., The Flow Management Problem in Air Tra?c Control; Flow Control of Congested Networks, Springer-Verlag, 1987. [10] O. Richetta and A. R. Odoni, “Solving optimally the static groundholding policy problem in air tra?c control,” Transportation Science, 1993. [11] O. Richetta, “Optimal algorithms and a remarkably e?cient heuristic for the ground-holding problem in air tra?c control,” Operations Research, 1995. [12] M. Terrab and A. R. Odoni, “Strategic ?ow management for air tra?c control,” Operations Research, 1993. [13] M. O. Ball, R. L. Ho?man, A. R. Odoni, and R. Rifkin, “The static stochastic ground holding problem with aggregate demands,” accepted for publication by Operations Research. [14] Volpe National Transportation Systems Center, “Enhanced Tra?c Management System (ETMS): Functional description,” Tech. Rep., United States Department of Transportation, 1999. [15] M. O. Ball, R. L. Ho?man, W. D. Hall, and A. Muharremoglu, “Collaborative decision making in air tra?c management: A preliminary assessment,” Tech. Rep., NEXTOR, 1998.
30
doc_577748921.pdf
In mathematics and civil engineering, traffic flow is the study of interactions between vehicles, drivers, and infrastructure (including highways, signage, and traffic control devices), with the aim of understanding and developing an optimal road network with efficient movement of traffic and minimal traffic congestion problems.
TECHNICAL RESEARCH REPORT
The Rate Control Index for Traffic Flow
by Robert L. Hoffman, Michael O. Ball
NEXTOR TR 2001-1 (ISR TR 2001-24)
NEXTOR
National Center of Excellence in Aviation Operations Research
The National Center of Excellence in Aviation Operations Research (NEXTOR) is a joint university, industry and Federal Aviation Administration research organization. The center is supported by FAA research grant number 96-C-001. Web site http://www.isr.umd.edu/NEXTOR/
The Rate Control Index for Tra?c Flow
Robert L. Ho?man, Michael O. Ball
March 26, 2001
?
Abstract: The objective of Air Tra?c Flow Management is to maintain safe and e?cient use of airspace and airports by regulating the ?ow of tra?c. In this paper, we introduce a single-valued metric for post-operatively rating the performance of achieved tra?c ?ow against targeted tra?c ?ow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how these improve on current tra?c control analysis techniques. The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be e?ciently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric. Although this metric was originally developed to rate the performance of Ground Delay Programs, it is equally applicable to any setting in which the ?ow of discrete objects such as vehicles is controlled and later evaluated.
?
Robert Ho?man is a senior analyst with Metron Scienti?c Consulting, 11911 Freedom
Drive, Reston VA 20190. Email: [email protected]. Michael Ball holds a joint appointment with the Robert H. Smith School of Business and the Institute for Systems Research at the University of Maryland, College Park, MD 20742. Email: [email protected].
1
Introduction
The ?ow of tra?c through airspace sectors and through airports is regulated by air tra?c ?ow managers to ensure that airspace components do not become overloaded and that throughput is maintained. Many of the short-term demand-capacity inequities in the NAS are smoothed out by FAA tra?c ?ow managers by tactics such as vectoring and miles-in-trail restrictions. Longerterm demand-capacity inequities (on the order of several hours) are more problematic. These usually occur when an airport acceptance rate is drastically reduced because of inclement weather, airport construction, or special runway operations. In these instances, air tra?c ?ow managers at the FAA employ ground holding strategies in which aircraft bound for an a?icted airport are held at their points of origin in lieu of costly and hazardous airborne holding that would occur if they were allowed to depart on schedule. The most prominent of these strategies is the ground delay program (GDP), which is an initiative taken by the FAA to lower the arrival rate to a level that can be safely handled by airport controllers. The increase in air tra?c in the United States over the last 20 years has necessitated more frequent use of tra?c ?ow management initiatives. For instance, in 1998, there were 187 ground delay programs run at San Francisco airport alone [1]. As a result, there has been considerable interest both in the aviation and research communities regarding tra?c ?ow management and its analysis. The issues of deepest concern have been the e?cient use of airport landing resources and the equitable distribution of arrival slots among competing airlines [2]. Substantial e?orts have been under way since the mid 1990’s to revamp the manner in which tra?c ?ow initiatives are 2
planned and executed. Most notable is the joint industry-FAA Collaborative Decision Making project (CDM), which has made major changes to GDP procedures. See [3] for details on ground delay program enhancements. One can see the need to assess the quality of tra?c control actions. In this paper, we provide practical solutions for three major aspects of postoperative, tra?c ?ow analysis. The ?rst aspect is the need for a simple way of contrasting aggregate tra?c ?ow with desired tra?c ?ow. We introduce the rate control index (RCI), which gives a single performance value to the ?ow of tra?c into an airport or sector of space as compared to the planned ?ow of tra?c. The rate control index bears an intuitive relation to the events that have lead to the deviation from the plan. In essence, the metric tracks the aggregate ?ight movements that have caused the realized tra?c ?ow to di?er from the planned tra?c ?ow. Although the basic concept behind the metric is easily understood, the normalization of the metric leads to an interesting optimization problem. The second aspect is the need to factor out from post analysis major stochastic factors upon which a control action is based. Every tra?c ?ow initiative is based on forecasts of demand and resource capacities, which are often not realized because they depend upon highly stochastic conditions. Air tra?c demand predictions, such as the number of arrivals to an airport, are vulnerable to airline operational deviations while capacity predictions for airspace sectors, runways, etc., are highly subject to weather conditions. Direct measurement of tra?c control actions is not always the best way to judge the performance of a new program or initiative; naive or ill-chosen metrics are heavily in?uenced by the quality of the forecasts upon which a
3
plan of action was based. For instance, in a GDP, the objective is to deliver a speci?ed number of aircraft to the airport during a ?xed time horizon. The metric generally used by tra?c ?ow managers for program evaluation is landings-per-hour [4]. If runway conditions turn out to be more severe than previously forecasted, then this metric will (correctly) reveal that the realized landing rate does not match the desired landing rate. However, to a large degree, the program performance was beyond the control of participating parties and is being judged in part by the forecast upon which it was based. For situations such as this, we show how to meter tra?c ?ow into an airport independently of the ability of the airport to land aircraft. The third aspect of tra?c ?ow analysis we address is the need for a metric that rates the performance of a group of controlled ?ights on a more individual basis than aggregate metrics. Directives are given to individual ?ights (altering ?ight paths, arrival times, etc.) in order to a?ect the aggregate ?ow of tra?c. Final success of these e?orts is typically measured using aggregate metering of tra?c. When the desired tra?c ?ow is achieved, the question arises whether or not this was due to the adherence of aircraft to their controlled arrival times or due to the fortuitous cancellation of early arrivals with late arrivals. To address this issue, we present a nominal version of the RCI metric that acts as a complement to the aggregate version of the metric. Section 2 of this paper provides motivation for the metric and an interpretation of its meaning. The rigorous formulation of the metric and its normalization process are deferred to Section 3. Section 4 demonstrates the application of both the nominal and aggregate versions of the metric to Ground Delay Program analysis. Conclusions are in Section 5.
4
2
The Core of the RCI Metric
The perspective taken in this paper is one of post-analysis. We view a tra?c ?ow initiative as a plan of action which is to be later analyzed for e?ectiveness. We assume that a tra?c ?ow manager has set a goal for each time period t = 0, 1, ..., T of a time horizon, meaning the number of vehicles that should be delivered to an airport (or more generally, pass through a region of airspace). A plan is enacted to achieve these goals. Once the time horizon has passed, the actual number of ?ights is recorded. This establishes two distributions: the planned distribution P = (p0 , p1 , ...pT ) and the realized distribution R = (r0 , r1 , ...rT ), where pt and rt are the planned and realized number of ?ights during time period t, respectively. The question is how to weigh the performance of the realized distribution against the planned distribution. We branch into two areas of concern, separated by a subtle but crucial distinction. One is the desire to measure program performance. Once a GDP is formulated, there are many factors that must fall into place in order for the GDP to be executed as planned. It is the duty of the controllers in the local tra?c management units to hold ?ights at their departure airports until their controlled times of departures. The airlines must notify passengers of the imposed ground delay and yet have them boarded and ready to takeo? at their controlled departure times without further delay. Pilots must maintain an enroute airspeed commensurate with that was used in the forecast of their enroute times. One can see that there are many entities that participate in the execution of the plan other than the tra?c ?ow specialists that have formulated the plan. A great deal of e?ort has been spent by the CDM com5
munity in improving GDP practices and performance. They have expressed a need to measure the execution of GDPs independent of the quality of its plan [5]. The other area of concern is the desire to measure program impact, meaning the e?ect that program performance has had on the system. Ideally, we would like a metric that produces a single, normalized value for the performance or impact of a program, so that programs can be tracked over long periods. This is especially valuable for discerning the e?ect of proposed program changes. Moreover, the metric should have a natural, intuitive interpretation to which cost bene?ts can be applied. Given the planned and realized distributions, P and R, a straight forward approach to distribution comparison is to form a distribution of errors E = P ? R = [p0 ? r0 , p1 ? r1 , ..., pT ? rT ] (1)
by vector subtraction, then to analyze the variance of the errors by averaging over the time periods or summing the squares of the deviations. Consider the planned distribution P = (30, 30, 30, 30, 30) of airport arrivals, meaning that 30 ?ights are intended to arrive in each of ?ve hours. Suppose that the actual number of arrivals per hour is given by R1 = (30, 30, 30, 31, 29). In this case, average error per hour is a poor measure; the excess of one ?ight in hour 4 cancels out with the shortage of one ?ight in hour 5 to produce a zero average. A more viable alternative is to compute the average absolute error, as below. Avg. Abs. Error = |0| + |0| + |0| + |1| + |?1| 5 2 = = 0.40 ?ights per hour 5 6 (2)
Although (2) correctly records an overdelivery in hour 4 and an underdelivery in hour 5, it fails to capture the events that have lead to R1 . Speci?cally, since 31 ?ights have arrived in hour 4 and only 29 in hour 5, then there must have been (in the aggregate) a migration of one ?ight from hour 4 to hour 5. The alternative measure of variance that we propose is to record the aggregate ?ight movement, or drift, that led to the deviation of R from P . This is the same as the minimum amount of ?ight movement that would be necessary to revert R to P . This can be viewed as an alternative way of measuring the di?erence between two distributions. This type of approach makes distinctions between realized distributions that (1) does not. For instance, consider the ?ight movements necessary to convert R2 = (31, 30, 30, 30, 29) into P . Since 31 ?ights arrived in the ?rst hour when only 30 were intended, one of the ?ights intended to arrive in a later hour arrived in hour 1. Let’s credit the participants with the least errors possible and say that this ?ight was intended to arrive in hour 2. Since 30 ?ights arrived in hour 2 instead of 30 ? 1 = 29, one of the ?ights intended to arrive in hour 3 must have arrived in hour 2. Similarly, one ?ight intended to arrive in hour 4 arrive in hour 3, and one ?ight intended to arrive in hour 5 arrived in hour 4. In all, we see that, as a minimum, there was a total migration of ?ve ?ight-hours. Note that if we computed average absolute error, as in (2), then R2 would receive the same rating as R1 , 0.40 ?ights per hour. In contrast, the aggregate ?ight movement method recognizes that four times as much movement has taken place in R2 as in R1 . The subtraction-based method (1) double-counts a single ?ight in hour 5. It can be argued that this correctly models the impact of the realized
7
distribution on the system, namely that the system is stressed in hour 4 and underutilized in hour 5. But this is based on the assumption that the airport capacity in each hour is as predicted, 30 aircraft per hour. Since 31 aircraft were accommodated in hour 4, the capacity of the airport clearly was not limited to 30 ?ights. Conversely, it is fairly common for an airport to accept fewer ?ights than were planned because airport acceptance rates are based not just on weather conditions and runway con?gurations, but also on departure demand and the abilities of air tra?c service providers. For this reason, it can be di?cult, if not impossible, to know what the actual airport capacity was, based solely on realized arrival rates. If these rates are known, metric (1) could be considered. The approach described in this paper primarily compares the planned distribution against the realized distribution, and not against the airport acceptance rate distribution. The main idea is to assess how closely the plan was followed. For a given planned distribution, P , and a realized distribution, R, the method is based on shifting aircraft in the R distribution to transform it to the P distribution. The rate control index (RCI) metric is the outcome of this method. The following example shows how the RCI metric would be computed in practice and how cost parameters can be applied. In Section 4, we show how to remove the e?ects that the air tra?c service providers at the airport may have had on the realized distribution. Section 3 covers the more complex aspects of the mathematics involved. Example: Suppose that a 4-hour GDP is planned and that the planned arrival acceptance rate (PAAR) for each of those 4 hours is 30 ?ights. Then the planned distribution is P = (30, 30, 30, 30) . Further suppose that the
8
Figure 1: Flight movements necessary to transform R into P
actual number of ?ights that arrived at the airport (or the airport terminal space) is given by R = (27, 32, 35, 24) . Then the rate control index for R (relative to P ), denoted RCI (P, R), is computed via the following two-part calculation. Part 1: Compute the di?erence P ? R. This is the minimum amount of ?ight movement that is necessary to turn R into P . We sweep left to right through R (increasing t), moving as many ?ights (say ft+1 ) as necessary from rt to rt+1 to achieve rt = rt ? ft+1 = pt . Counting left-hand movements as negative and right-hand movements as positive, we must move 3 ?ights from hour 1 to hour 0 (f1 = ?3), move 1 ?ight from hour 2 to hour 1 (f2 = ?1), and move 4 ?ights from hour 2 to hour 3 (f3 = 4). See Figure 1.
9
Movement Hr 0 ?? Hr 1 Hr 1 ?? Hr 2 Hr 2 ?? Hr 3 Hr 3 ?? Hr 4
Notation Flight-hours f1 f2 f3 f4 -3 -1 4 -2
Table 1: Summary of ?ight movements through time So far, R has been transformed into the distribution, R = (30, 30, 30, 28). Note that this is 2 ?ights short of the desired distribution, because pt ? rt = 120 ? 118 = 2. We create a “slush fund” of 2 ?ights at the end of R to compensate for the lack of conservation of ?ights. Equivalently, we could have started with an augmented distribution R = (27, 32, 35, 24, 2). Similarly, we extend P to a ?ve-hour distribution, P = (30, 30, 30, 30, 0). To complete the example, we move 2 ?ights from hour 4 to hour 3 (f4 = ?2). The summary of ?ight-movements is given in Table 1. We defer to Section 3 the formal proof that this correctly computes the minimum cost transformation. Now we can compute the cost of transforming R into P . Let c? be the average cost (say, in dollars per hour) of delaying a ?ight for one unit of time and let c+ be the average cost (say, in dollars per hour) of a ?ight arriving early by one unit of time. Then we break the ?ight-movements into left-hand movements M ? = |?3| + |?1| + |?2| = 6 and right-hand movements M + = 4, corresponding to tardiness and earliness, respectively. The ?nal cost is given by c? M ? + c+ M + = 6c? + 4c+ . (3)
In this example, we opt to set c? = c+ = 1.0 to obtain pure units of 4 + 10
6 = 10 ?ight-hours. In other words, R was o? from P by 10 ?ight-hours. Intuitively, this means that in order to turn R into P , one would have to do the work equivalent to moving 1 ?ight 10 hours, or 2 ?ights 5 hours, etc. One variation on the metric is to retain the positive and negative sums to show the breakdown of this total. Part 2: Normalize the distribution error P ? R . To compare GDPs of di?ering lengths and number of ?ights, we normalize by dividing the distribution error by the cost of the worst-case scenario. This means we must ?nd the ?ve-hour redistribution W of the 120 ?ights in P with the highest cost difference, P ? W . In general, this involves solving a max-min problem, which is covered in Section 3. For now, we take as a given that W = (0, 0, 0, 0, 120) with a cost of P ? W = (|?4| + |?3| + |?2| + |?1|) × 30 = (10) × 30 = 300 ?ight-hours. (W corresponds to the scenario in which all the ?ights land in the ?nal hour.) Thus, the rate control index we assign to the distribution R is 10 ?ight-hours = 0.033. 300 ?ight-hours (5) (4)
Since we have kept pure cost parameters of 1.0, this is a pure ratio that indicates the error of the realized distribution. In order to make the index more palatable, we phrase the performance of the realized distribution in terms of what was achieved rather than what was not achieved. Subtracting from 1.0, we obtain a ?nal rate control index (RCI) of Since we have kept pure cost parameters of 1.0, this is a pure ratio that indicates the error of the realized distribution. In order to make the index 11
more palatable, we phrase the performance of the realized distribution in terms of what was achieved rather than what was not achieved. Subtracting from 1.0, we obtain a ?nal rate control index (RCI) of RCI (P , R) = 1.0 ? .0333 = 0.966 (6)
If preferred, this ?nal index can be transformed into a percentage, 96.67%. The interpretation of the index is that the realized distribution achieved 96.67% of the intended (planned) distribution. This number can then be used for comparing GDP performance on di?erent days and lends itself nicely to trend analysis (see Section 4.
3
Formulation and Computation of the RCI Metric
In Section 2, we provided motivation and intuition for the RCI metric. In this section, we provide a more rigorous formulation of the RCI metric and show how to correctly compute the cost of the worst-case distribution in the normalization process. Also, we discuss the nuances behind normalization of the metric with respect to distribution length and mass.
3.1
The Raw RCI Score: Comparing Two Distributions
We de?ne a distribution to be a (T + 1)-tuple of nonnegative numbers and we de?ne its mass to be the sum of its entries. Let D and D be two distributions 12
that we wish to compare using the RCI metric. Based on the motivation provided in Section 2, we have chosen to represent the transformation of D into D by a T -tuple, F = (f1 , f2 , ..., fT ), where ft is the amount of mass necessary to move from dt?1 to dt . Speci?cally, dt receives an increment of ft units from dt?1 and sends ft+1 units to dt+1 . The net increment for period t is ?t = dt ? dt , as illustrated in Figure 2. Thus, in order to transform dt into dt the following condition must hold: dt + ft ? ft+1 = dt (7)
Note that ft can be positive or negative. Given D and D , F can by computed by initializing f1 using f1 = d0 ? d0 and then recursively applying, ft = dt?1 ? dt?1 + ft?1 for t = 2 to T . Alternatively, we can compute F directly from
t
(8)
(9)
ft =
s=1
(ds?1 ? ds?1 ) for t = 1, 2, ..., T.
(10)
If D and D do not have the same mass then, prior to computing F , their masses should be equalized by adding a (T + 2)nd component to each distribution. This extra component should have zero mass in the larger of the two masses and should have a mass equal to the nonnegative di?erence of their masses in the smaller of the two distributions. T is then incremented by one. Intuitively,
T t=1
|ft | is the amount of work necessary to transform D to
D . If we multiply the positive and negative values of ft by cost parameters 13
c+ and c? , respectively, then the cost of ft is given by cst(ft ) = c+ max {ft , 0} + c? max {?ft , 0} and the total cost of the transformation is computed via
T
(11)
C (D, D ) =
t=1
cst(ft )
(12)
which serves as the unnormalized, or raw, RCI score. Note that this expression is well-de?ned since for a given pair of distributions, D and D , F is unique. One can see from (12) that if C (D, D ) is given by ac+ + bc? , then C (D , D) is given by bc+ + ac? . This means that whenever c+ = c? , the cost of transforming D into D may not be the same as the cost of transforming D into D. For this reason, care must be taken when comparing multiple distributions against a baseline distribution: the direction of transformation should be made consistent. It is interesting to note that the computation of F could be recast as a network ?ow problem de?ned on a simple linear network with non-negative ?ow variables, xt and yt , where ft = xt + yt . In Figure 2, one would replace each arrow ft with a right arrow (xt ) and a left arrow (yt ). The vector F corresponds to an acyclic ?ow, i.e., a ?ow in which for each t, at most one of xt and yt is nonzero. An acyclic ?ow is optimal as long as the ?ow costs are non-negative (see [6] for an analysis of ?ow problems on linear networks and see [7] for a treatment of general network ?ow problems).
14
3.2
3.2.1
Normalization of RCI
The Worst-case Scenario
In the motivating example of Section 2, we saw that the normalization step of the RCI computation requires that we ?nd the redistribution W of a ?xed distribution P with the worst-case (maximum) value, C (W, P ). Consequently, we must consider any restrictions that may exist on the worst-case W . In the air tra?c management case, we can assume that there is an earliest possible arrival time for each aircraft. This time is usually the scheduled arrival time of the ?ight. Let B = (b0 , b1 , ..., bT ) be the distribution of earliest possible arrival times of the ?ights. That is, bt is the number of ?ights with an earliest arrival time in the tth time period. Note that for a ?xed time interval t, the cumulative number of aircraft that can arrive in time periods s = 0, 1, ..., t is limited by
t s=0 bs .
This means that vector W is restricted by Ws ? Bt for all t, (13)
where for any distribution E = (e0 , e1 , ..., eT ), we have de?ned the following partial sum notation:
t
Et =
s=0
es for t = 0, 1, ..., T.
(14)
B is said to be a (leftward) bounding distribution for P . Since there is no limit to how late a aircraft could arrive, there is no need to analogously de?ne a rightward bounding distribution. Let ?B be the set of redistributions of P that are restricted by (13). Then E ? ?B , if and only if E can be obtained from B by making strictly rightward shifts in B . For example, if P = (0, 3, 3) and B = (1, 2, 3), then (0, 0, 6) ? ?B while (3, 0, 3) ? / ?B . 15
Recall that our approach to the normalization of the RCI metric is to divide the cost of transforming a distribution E into a target distribution P , C (E, P ), by C (W, P ), where W is the worst case (highest cost) scenario. We assume that all distributions are rightward shifts of the distribution B so we seek a solution to max C (W, P ) | W ? ?B . (15)
We note that (15) is a max-min problem, since (C (W, P ) is the optimal objective value of a minimization problem. In the next section, we show how to solve this max-min problem by dynamic programming. 3.2.2 A Dynamic Programming Solution
Let distribution P = (p0 , p1 , p2 , ..., pT ) be given, along with bounding distribution B = (b0 , b1 , b2 , ..., bT ). We wish to write a recursive relation for ?nding a solution to (15) in the case where all distributions are integer. Fix an index t ? T and an integer amount of mass ? ? 0. Consider the truncated vector P t = (p0 , p1 , p2 , ..., pt ) . The subproblem we de?ne is to ?nd a truncated vector W t = (w0 , w1 , w2 , ..., wt ) of mass ? such that C (W t , P t ) is as expensive as possible. We denote this maximum cost by Cmax (t, ? ). To form the basis of a dynamic programming algorithm, we now derive a recursive relation to compute Cmax (t, ? ). See Figure 3. Based on our notation, (W t )t?1 is the (t ? 1)st partial sum of the vector W truncated at t. For a ?xed ? , the mass of (W t )t?1 can range over the values m = 0, 1, ..., Bt?1 ? ? . For each value of m, (10) dictates that the value of ft is uniquely determined by ft = (W t )t ? (P t )t?1 = m ? Pt?1 . This means that the value of Cmax (t, ? )
16
is related to Cmax (t ? 1, m) via the following recursion:
? ? ? ??, ? ? ? ?
if ? > Bt or t > T if t = 0 and ? ? Bt ?, otherwise (16)
Cmax (t, ? ) =
? ? ? ? ? ?
0,
m=0,1,...,?
max
where ? = {C (t ? 1, m) + cst (ft ) | ft = m ? Pt?1 }. The ?rst case in (16) prevents ? and t from taking on ill-de?ned values and the second case initializes the recursion. The third case expresses the fundamental recursion. The solution to our problem, (15), is given by Cmax (T, PT ). This recursion might seem simple, even trivial, since ft does not vary in the max operation. However, the complexity of this problem lies within the restrictions imposed by the bounding distribution B , which limits the values to which the max operation is applied. In fact, without, this restriction, extreme or trivial solutions would always result. Note that for a given ? and t, the computation of Cmax (t, ? ) is dependent upon the values Cmax (t ? 1, 0) , Cmax (t ? 1, 1) , ..., Cmax (t ? 1, ? ) (17)
This structure leads naturally to a forward recursion, dynamic programming algorithm. If we let S be the total mass in P , then the running time of such an algorithm is at most O(T S 2 ) since there are at most O(T S ) Cmax ( ) values to be computed and the computation of each one requires at most O(S ) comparisons.
17
Figure 2: Transformation of distribution D into distribution D by vector F
Figure 3: Finding the highest cost redistribution W when the partial sumWt?1 is set to ?
18
4
Ground Delay Program Analysis
In this section, we demonstrate the application of the RCI metric in the context of ground delay programs.
4.1
Modelling Air Tra?c Flow into an Airport
A Ground Delay Program (GDP) is an FAA tra?c ?ow action to reduce the ?ow of aircraft into an airport. A GDP is implemented whenever it is predicted that the arrival demand at an airport will exceed the arrival capacity for a signi?cant period of time. In essence, ?ights bound for a single airport are held at their origin airports so that they can be accepted to enroute and terminal area tra?c ?ows without delay. A light amount of airborne holding during times of reduced capacity is considered desirable because it ensures that airport arrival resources are being fully utilized. However, excessive airborne holding queues are considered undesirable because of the added workload on air tra?c controllers. Aircraft must be physically separated, placed in and out of layered holding patterns, and monitored for su?cient fuel reserves. Most GDPs are prompted by adverse weather conditions that can dramatically reduce the airport acceptance rate (AAR). Other causes are runway construction and special airport operations. GDPs are planned several hours in advance and can run for periods as long as 12 hours. For more background on ground delay programs and the ground holding problem, see [8], [9], [10], [11], [12]. Since the primary purpose of a GDP is to control the rate of aircraft ?ow
19
into an airport, the typical metric for evaluating the performance of a GDP is to measure the actual landings-per-hour (LAN Dt , where t varies over the discretized time intervals over which the GDP operated) against the planned landings per hour (P AARt ). Although this is often taken to be the “bottom line” in a GDP, it is in fact a hybrid analysis that blurs the appropriateness of the plan with the execution of the plan. The ability of air tra?c service providers to land aircraft is directly related to airport conditions and runway con?guration. These are, in turn, dependent upon weather conditions, which are highly stochastic. If weather conditions turn out to be worse than expected, then airport capacity is lower than forecasted and the desired arrival rate will not be achieved. If we measure program performance strictly by landings-per-hour, then we are e?ectively holding program participants responsible for the quality of the forecasts upon which the program was based. There needs to be a mechanism to analyze the success with which the plan was executed, independently of the appropriateness of the plan and the forecasts upon which it was based. (See [13] for treatment of stochastic airport capacity.) The solution to removing stochastic airport conditions from measurement is to meter the tra?c ?ow at a point close to the airport but before it could be directly a?ected by airport capacity. Ideally, we would like to know for each ?ight how much airborne holding it incurred as a result of restricted airport capacity. From this we can compute the time it would have arrived at the airport in the absence of airport capacity restrictions. Holding data is recorded by air tra?c service providers, but only when work conditions allow them su?cient time to do so. Hence, FAA ?ight holding databases are
20
often incomplete. As a surrogate for this holding data, several approaches can be used. A general idea is to de?ne a radius of geographical distance (or time) about the airport and declare that once a ?ight has passed over this boundary, it has been delivered to the airport. This should be the smallest possible radius that captures all, or most of, the airborne holding. For many airports, the holding location for a ?ight varies with the airport arrival ?x over which the ?ight will pass. The radius may have to be ?ight-path speci?c. Such a model can use as input readily available ?ight data, such as that provided by the Enhanced Tra?c Management System (ETMS). For each ?ight, ETMS provides a runway departure time, a runway arrival time, and a sequence of estimated arrival times (ETAs), as the ?ight moves along its ?ight path [14]. We assume the existence of a model that will estimate, post facto, for each ?ight f the amount of airborne holding that it incurred, which we denote ABHf (see [15] for one such model). From this, we can deduce that f was in a state of airborne holding at a given time t < ART Af if and only if ABHf ? ART Af ? t, where ARTA is the actual runway time of arrival as recorded by ETMS. For a set of contiguous time intervals t = 0, 1, ..., T , let DELt be the number of ?ights delivered to the airport during time interval t, meaning, the number of ?ights that would arrive given unlimited capacity. Let ABHt be the number of ?ights that are in a state of airborne holding at the end of interval t. Let LAN Dt be the number of ?ights that land during time period t. If we view the airport as a closed network, then we have the following
21
elementary relationship for each t (see Figure 4). DELt = (ABHt ? ABHt?1 ) + LAN Dt (18)
After a GDP, three distributions can be assembled: P AAR, DEL, and LAN D. In the case study that follows, we use RCI (P AAR, LAN D) to measure general program performance and we use RCI (P AAR, DEL) to measure program performance independent of stochastic airport conditions.
4.2
The Aggregate Version of RCI
Figure 5 shows a graphical analysis of the performance of a ground delay program (GDP) conducted at San Francisco airport (SFO) on March 5, 1998. The planned acceptance rate of ?ights (the P AAR distribution) was set at 32 ?ights per hour for each of the six hours of the GDP. The RCI value assigned to this GDP was 88.24%. Since this is below the 1998 RCI average for SFO, approximately 92.0%, it would be a likely candidate for further analysis. The RCI value of 88.24% was computed based on P AAR versus DEL, the distribution of “?ights delivered” to the terminal airspace of the airport (but not necessarily landed). The cost parameters were set to c+ = c? = 1.0, to obtain pure ?ight-movement units. Also shown are the distributions LAN D, ?ights landed at the airport, and ABH, the size of the airborne holding queue at the end of each hour. Figure 5 shows why the RCI(PAAR, DEL) was not closer to the optimal value, 100%. There were too many ?ights delivered to the airport early in the program: in the ?rst hour, 41 ?ights were delivered when only 32 were intended. One possible explanation for this is that the GDP was implemented 22
too late and some of these 41 ?ights were already airborne when the program was planned, hence, they could not have been held on the ground. Some of these ?ights may have been assigned ground holds but departed too early, but this is a less likely explanation. Moreover, there were drastically too few ?ights delivered in the 2100 (zulu) hour: 16 ?ights compared to the desired 32. Some of the ?ights intended to arrive in hour 2100 may have arrived in hour 2000. Note the increase in the airborne holding queue size in hour 2100 hour as a result of high arrival volume in hour 2000. One can see that the LAN D distribution more closely follows P AAR than does DEL. Thus, the value of RCI (P AAR, LAN D) (not computed) would be slightly better than RCI (P AAR, DEL). This is not uncommon: some of the arrival ?ow is smoothed out by airborne holding, resulting in a smoother distribution. An interesting feature of this GDP was that, during hour 2100, even with the pressure of a substantial airborne holding queue, the airport was able to land only 23 ?ights, instead of the forecasted number, 32. Airport tower tra?c counts con?rm that the controllers at the airport favored departures during the 2100 hour.
4.3
The Nominal Version of RCI
In this section, we demonstrate the use of a nominal version of the rate control index. For each ?ight f , we compute the amount of arrival delay, Mf via Mf = |actual arrival time ? planned arrival time| . (19)
23
Figure 4: Model of an airport as a closed system
Figure 5: Analysis of ground delay performance at San Francisco Airport, 3/5/98
24
The unnormalized RCI score is
f
M (f ), which represents the amount of
?ight movement through time that would be necessary to restore all ?ights to their planned arrival time. This number is normalized by dividing by the cost of the worst-case scenario,
f
W (f ), where W (f ) is the largest deviation
that could have occurred for ?ight f (i.e., the farthest time period in either direction from its planned period of arrival). The ?nal value is subtracted from 1.0 and multiplied by 100%. If desired, the positive delays (Mf > 0) and negative delays (Mf < 0) can be weighted with cost parameters c+ and c? before summing, as was done with the aggregate version of the metric. In the examples shown in this section, we have elected to set c+ = c? = 1.0 so that
f
M (f ) represents the (absolute) variance of ?ight arrivals from their RCI N om , RCI Agg , for a
planned arrival times. Each point in Figure 6 is an ordered pair,
GDP run at SFO during the period January 1 to October 28, 1998. Consider the point (64, 92) for July 10. The value RCI Agg = 92% indicates that, in the aggregate, the distribution of landed ?ights closely matched the desired distribution. However, the low value of RCI N om reveals that, too often, the ?ights that landed in a given time interval were not the ?ights that were intended to land in that time interval. Some of the ?ights arrived earlier than planned while others arrived too late. On the whole, for any given time interval, the number of ?ights that migrated out of a time interval was almost equal to the number of ?ights that migrated into that time interval, hence, the aggregate numbers of ?ights were preserved. The stochastic processes cancelled each other out and there was a great deal of ‘luck’ involved in achieving the high value of RCI Agg = 92%.
25
Figure 6: Nominal and aggregate RCI values for Ground Delay Programs at SFO, January - October, 1998
26
In general, points in the upper right quadrant of Figure 6 correspond to programs in which the aggregate distribution of ?ights was achieved and most of the ?ights arrived in their expected time periods. These are the best-run programs, the goal of each program being (100%, 100%). Given two points (x1 , y1 ) and (x2 , y2 ), with x1 < x2 and y1 = y2 , we can say that they had the same level of aggregate success but that the ?rst program involved more ‘luck’ while the second program involved more ‘skill’. The center of mass of the squares lies at about (82, 92), marked by the cross. This indicates that the overall ground delay performance at SFO is quite good. In general, RCI N om is about 10% less than RCI Agg . Note that all of the points lie above the 45-degree line. This is to be expected since as RCI N om increases, more ?ights are arriving in their planned arrival periods and so the aggregate distribution of ?ights is more likely to match the planned distribution, which also increases the value of RCI Agg . Note that when RCI N om = 100%, the only way for RCI Agg to fall below 100% is for there to be arrivals that were not anticipated by the GDP.
5
Closing Remarks
We have introduced a new metric for the evaluation of planned versus realized tra?c ?ow for a region of space or an airport. In its most general form, the metric generalizes to a comparison of two ?nite distributions, hence, has the potential for use in any area of tra?c management in which vehicular movement through time is regulated. This represents a substantial improvement over the standard techniques for comparing two ?nite distributions. The met-
27
ric naturally lends itself to intuitive interpretation (when decomposed into left and right-handed movements) and to cost evaluation. The development of an aggregate and nominal version of the metric captures the two crucial aspects of tra?c ?ow management: how many ?ights ?owed through a region of space and which ?ights ?owed through the region. Also, we have shown how to apply the metric to factor out the e?ects of inaccurate forecasts from performance analysis of a tra?c ?ow initiative. We showed how to compensate for controlled ?ights that arrive outside the planned time horizon by augmenting the realized distribution. The intuitive justi?cation for this was that the cost added is assessed at a rate commensurate with the wasted capacity due to these ?ight cancellations. However, there doesn’t seem to be an analogous compensation for the case in which unanticipated ?ights arrive within the planned time horizon. For consistency with ?ight shortages, the logical adjustment for these pop-up ?ights would be to augment the planned distribution. Unfortunately, the added cost would be assessed at a rate commensurate with the movement of ?ights backward in time, for which there is no intuitive obvious justi?cation. In practice, pop-up ?ights comprise a small enough percentage of the total ?ights that their e?ect on the RCI metric is minimal when they are ignored. However, future development of the metric should incorporate pop-up ?ights.
6
Acknowledgements
This work was funded by the Federal Aviation Administration (FAA) through NEXTOR, the National Center of Excellence for Aviation Operations Re-
28
search. The opinions expressed herein are solely those of the authors and do not re?ect the o?cial position of the FAA.
References
[1] Ground delay program summaries, available at the CDM web site, http://www.metsci.com/cdm. [2] M. O. Ball, R. L. Ho?man, C. Y. Chen, and T. Vossen, “Collaborative decision making in air tra?c management,” in Proceedings of Capri ATM-99 Workshop, 1999. [3] R. L. Ho?man, M. O. Ball, A. R. Odoni, W. D. Hall, and M. Wambsganss, “Collaborative decision making in air tra?c ?ow management,” available at the NEXTOR web site, http://www.nextor.umd.edu. [4] Personal conversations and interviews with tra?c ?ow managers at the FAA’s Air Tra?c Control System Command Center in Herndon, Virginia. [5] Minutes of the Collaborative Decision Making Analysis Subgroup, available at http://www.metsci.com/cdm. [6] M. O. Ball and M. J. Magazine, “Sequencing of insertions in printed circuit board assembly,” Operations Research, 1998. [7] R. Ahuja, T. Magnanti, and J. Orlin, Network Flows, Prentice Hall, 1993.
29
[8] R. L. Ho?man, Integer Programming Models for Ground-Holding in Air Tra?c Flow Management, Ph.D. thesis, University of Maryland, 1997. [9] A. R. Odoni, L. Bianco, and G. Szego, Eds., The Flow Management Problem in Air Tra?c Control; Flow Control of Congested Networks, Springer-Verlag, 1987. [10] O. Richetta and A. R. Odoni, “Solving optimally the static groundholding policy problem in air tra?c control,” Transportation Science, 1993. [11] O. Richetta, “Optimal algorithms and a remarkably e?cient heuristic for the ground-holding problem in air tra?c control,” Operations Research, 1995. [12] M. Terrab and A. R. Odoni, “Strategic ?ow management for air tra?c control,” Operations Research, 1993. [13] M. O. Ball, R. L. Ho?man, A. R. Odoni, and R. Rifkin, “The static stochastic ground holding problem with aggregate demands,” accepted for publication by Operations Research. [14] Volpe National Transportation Systems Center, “Enhanced Tra?c Management System (ETMS): Functional description,” Tech. Rep., United States Department of Transportation, 1999. [15] M. O. Ball, R. L. Ho?man, W. D. Hall, and A. Muharremoglu, “Collaborative decision making in air tra?c management: A preliminary assessment,” Tech. Rep., NEXTOR, 1998.
30
doc_577748921.pdf