WIXLIB

minimizing bank time (i.e., exchangepassengers/cargo, and aircraft servicing) [8].ofEarlier studies have shown that scheduling aircraftaccording to an FCFS sequence based on estimatedtime of arrival at the runway produces a schedulewhich is considered to be both fair to air carriersand efficient in terms of minimizing delays whichmust be absorbed [3]. These studies also haveshown that the resulting scheduled arrival sequenceat the runway will, for the most part, match theFCFS sequence which is input to the schedulingalgorithm. Because the scheduling algorithmattempts to preserve the input sequence,specifying a preferred sequence will result in aschedule which closely approximates the preferredarrival order. The concept of Òpriority schedulingÓis then defined as the scheduling of a bank ofarrival traffic according to a preferred order ofarrival. The focus of the present study is t odetermine the feasibility of scheduling a bank ofarrival aircraft using a preferred sequence insteadof an FCFS sequence based on ETA at the runway.It is importantto distinguishbetweenÒschedulingÓ or ÒscheduleÓ in the context ofairline operations,andÒschedulingÓorÒscheduleÓ in the context of air traffic controlautomation. The former refers to the dailyscheduled times of departure and arrival which anairline determines for all of its flights, while thelatter refers to the process of automaticallychoosing (a) the order or sequence in which theaircraft should land or cross a particular fix, and(b) the time that each aircraft in the sequenceshould pass over a specified fix [6].Fast-time SimulationA fast-time simulation originally developed forstatistical evaluation of CTAS sequencing andscheduling algorithms has been modified for use inthis investigation [9]. In contrast to real-timesimulation or field tests, which would require onthe order of ninety minutes to examine a singletraffic rush period, the fast-time simulation allowsexamination of large numbers of statisticallysimilar rush periods in a matter of minutes. Foreach simulated traffic situation, the deviation of adesignated bankÕs scheduled arrival order from thepreferred arrival order can be determined. Theimpact of priority scheduling on delays is alsodetermined by comparing delays for priorityscheduling and FCFS scheduling. Because thissimulation does not provide any information aboutthe controller workload required to meet thecalculated schedule, the output of the simulation isused only to determine the effectiveness ofpriority scheduling and its impact on scheduleddelays. The fast-time simulation is comprised ofthree major components: an airport model, astatistical model of the arrival traffic flow, and thescheduler.Airport ModelThe arrival airspace at DFW is divided into ns, with theTRACONencompassing the airspace within approximately40 n.mi. of the airport. Arrival traffic is merged atfour waypoints on the Center-TRACON boundarywhich correspond to the four primary arrivaldirections. These waypoints are referred to asfeeder gates because during heavy traffic periodstraffic is funnelled through these gates as a meansof controlling or metering the flow rate into theterminal area [6]. Traffic flowing to each gate isseparated into two independent streams which arevertically separated by 2,000 feet at the feedergate. This allows jet and turboprop aircraft, whichhave significantly different airspeed ranges, t ocross the feeder gates independently and avoidconflicts due to overtakes near the gates.The airport is modeled according to the landingpractices at DFW with four feeder gates and threerunways available for landing. The runways areconsidered to be independent so that no staggerrequirements are necessary for scheduling. Theairport model is comprised of the minimum flighttimes from each feeder gate to all landing runwaysfor each independent stream. These TRACONtransition times were obtained from an analysisusing the minimum flight times measured forseveral traffic samples [10]. The TRACONtransition times vary with feeder gate, ion. The airport model containstransition times for both airport configurations atDFW: ÒnorthflowÓ with arrival trafficarriving/departing in a northerly direction, andÒsouth flowÓ with traffic arriving/departing in asoutherly direction. It should be noted that sincethe data used in this simulation were collected, afourth arrival runway has been added at DFW.However, the three-runway model and traffic dataare sufficient for purposes of this investigation.Traffic ModelThe traffic model is based on actual traffic datarecorded during six rush periods at DFW. Although3

the traffic data were recorded over a span ofseveral months, the mix of aircraft type remainednearly constant for each traffic sample. The datawere recorded during the Ònoon balloon,Ó a dailyarrival rush lasting approximately ninety minutes.The noon balloon was chosen as the basis for thetraffic model because during this arrival rushdemand exceeds airport capacity and air trafficmanagers impose time-based metering restrictionsthrough CTAS sequencing and schedulingalgorithms. Data recorded during the six rushperiods include the aircraft type, aircraftidentification, arrival stream, and the estimatedtime of arrival at the feeder gate (ETA FG). Theaverage of these estimated times of arrival for thesix rushes is taken as the nominal ETA FG. Errorsin aircraft time of arrival in Center airspace aremodeled by adding an approximately Gaussiandistribution to the nominal estimated time ofarrival at the feeder gate. The maximum range ofthe variation in the ETAFG is specified as an inputto the simulation and is referred to as the Centerarrival error.Bank DefinitionAlthough an actual arrival bank of aircraft for anairline may consist of between 30 and 50 aircraft,in this study it is assumed that a bank is comprisedof a single group of up to 20 aircraft belonging t oone airline and its subsidiary carrier. With amajority of the flights in the traffic modelbelonging to American Airlines (AAL) andAmerican Eagle (EGF), these flights are used t oform arrival banks. The bank is not a contiguousset of aircraft because aircraft belonging to otherairlines are interspersed among the bank aircraft,as would be the case in a real traffic situation. Thebank of aircraft is defined by specifying the firstmember of the bank, and the number of aircraftbelonging to the bank. For the purposes of thissimulation, we assume that the preferred order ofarrival at the runway equals the order of arrivalbased on the minimum ETA at the runway with noCenter arrival error. Each of the bank aircraft isassigned a priority ranking which is simply equal t othe preferred order of arrival for the aircraftwithin the bank. The minimum estimated time ofarrival at the runway (ETA RWY ) is calculated byadding the TRACON transition times for each ofthe three runways to the nominal ETA FG, andselecting the minimum of the three resultingvalues. This ETA RWY represents the earliestpossible time of arrival for an aircraft providedthat the aircraft could fly to the runway with nodelay.For example, consider the list of aircraft shown inTable 1, which represents a portion of a singlearrival rush where AAL1150 has been designatedas the lead aircraft in the bank, and the number ofaircraft in the bank has been specified as five. Thenumber in the first column represents the sequencenumber or position of the aircraft within thearrival rush when the aircraft are time-orderedaccording to increasing ETARWY. Each arrival rushor traffic sample consists of 108 aircraft, and inthe example in Table 1 the aircraft belonging t othe defined bank range from the 57th aircraft t othe 65th aircraft in the arrival rush (AAL1554).The resulting bank aircraft are denoted by boldtext for purposes of illustration. This exampleshows that aircraft belonging to other airlines areinterspersed among the arrival aircraft whichcomprise the bank. The second column is theaircraft identifier and the third column is eachaircraftÕs corresponding minimum ETA RWY . Thefourth column shows the priority ranking which isassigned to each of the aircraft belonging to thebank based on this preferred order of 68Aircraft 345337635313546Priority12345Table 1 Bank definition and preferred arrivalorderThe actual order of arrival for aircraft in a trafficrush period is generated by adding the Centerarrival error to the nominal ETA FG. The Centerarrival error represents the uncertainties in theNAS which cause the same flight to arrive inCenter airspace at different times on differentdays. Because the minimum ETA RWY is calculatedby adding a TRACON transition time to theETAFG, the minimum ETARWY will also vary. As aresult, when the aircraft are ordered according t o4

increasing ETA RWY , the actual order for the bankaircraft will differ from the preferred arrival order.In addition, the number of aircraft interspersedamong the arrival bank may vary because thevariation in arrival time is modeled for all aircraftin the traffic rush, not only those belonging to thespecified bank. Table 2 shows the resultingestimated arrival order for the specified bank whena Center arrival error having a range of up to /- 5minutes is added to the traffic 8Aircraft 00332634413624Priority14352Table 2 Actual arrival orderFCFS SchedulingThe FCFS scheduler is intended to approximatethe sequencing and scheduling algorithms presentlyused in CTAS at the Ft. Worth Center. A detaileddescription of the actual scheduling algorithm canbe found in [6]. Aircraft are sequenced andscheduled to be first-come-first-served at both thefeeder gates and runways while meeting feeder gateand runway threshold separation constraints.Because scheduling is done in time rather thandistance, the prescribed minimum separationcriteria are translated into minimum timeseparations at both the feeder gates and therunway threshold. For aircraft crossing the feedergate, the minimum in-trail separation requirementfor aircraft is 5 n. mi., which is translated to a 60second time separation for purposes of thissimulation. The separation criteria at the runwaythreshold are a function of both aircraft weightclass and landing order as determined by the FAAÕswake vortex safety rules. Airport acceptance rate(AAR) is taken into consideration by limiting thenumber of aircraft which are allowed to enter theTRACON in sliding ten minute intervals, and thescheduler balances flights between runways t ominimize overall delay.The FCFS sequence is established by time-orderingarrival aircraft according to increasing ETARWY .Beginning with the first aircraft in the sequence,each aircraft is tentatively scheduled to each ofthe three runways, while ensuring that theprescribed minimum time separation betweenaircraft at the runway thresholds is met for eachsubsequent aircraft. The runway which results inthe earliest scheduled time of arrival for theaircraft at the runway (STARWY) is then chosen asthe landing runway . Scheduling to the runwayautomatically provides the correct amount oftraffic to load the runways equally when traffic isheavy (runway balancing), and directs aircraft t othe closest available runway. The scheduled timeof arrival at the feeder gate (STAFG) is determinedby subtracting the sum of the TRACON transitiontime and any TRACON delay from the previouslycalculated STARWY. Finally, if STAFGÕs for twoflights are less than the required 60 seconds apart,the scheduled times will be altered to meet therequired separation at the feeder gate.Table 3 shows the resulting order of arrival whenthe aircraft are scheduled according to an FCFSsequence. The priority ranking of each bankaircraft is shown in parenthesis following theaircraft identifier. The second and third columns inthe table show the FCFS sequence which is input t othe scheduler, with the aircraft time-orderedaccording to increasing ETARWY . The fourth andfifth columns are the resulting schedule, withaircraft time-ordered according to increasingSTARWY. Note that the resulting scheduled order ofarrival at the runway does not precisely match theFCFS sequence based on ETARWY which is input t othe scheduler. Because the schedule must meet intrail separation criteria at both the feeder gate andthe runway threshold, and the separation criteriaat the runway threshold are a function of aircraftweight class and landing order, the FCFS sequencemay not be preserved at the runway. Among theaircraft belonging to the designated bank, flightsAAL1934 and AAL1428 have shifted positionsfrom the sequence which is input to the scheduler(as have aircraft DAL431 and AAL410, which donot belong to the designated bank). In this case,the position shift has resulted in a scheduledsequence which does more closely match the idealor desired order of arrival than does the inputFCFS sequence based on ETA RWY . However, it is5

SequenceNumber545556575859606162636465666768FCFS SequenceAircraft IDETARWYResulting ScheduleAircraft IDSTARWYDAL428AAL1150 (1)DAL1670EGF006DAL834DAL2062UAL359ASE924AAL1428 (4)AAL1934 (3)AAL1554 (5)EGF628 (2)AAL410DAL431DAL756DAL428AAL1150 (1)DAL1670EGF006DAL834DAL2062UAL359ASE924AAL1934 (3)AAL1428 (4)AAL1554 (5)EGF628 13627369537373768378938433895395239534039Table 3 FCFS sequence and resulting schedulepurely fortuitous that the resulting schedule moreclosely matches the preferred order, and dependingon the magnitude of the Center arrival error, thescheduled order may actually deviate further fromthe preferred order.Priority SchedulingThe priority scheduling algorithm is identical t othe FCFS algorithm with one exception: instead oftime-ordering the aircraft according to increasingETA RWY prior to scheduling, the arrival aircraftbelonging to the designated bank are orderedaccording to their priority ranking, whichestablishes the bank aircraft in the preferredarrival order. It is important to note that only theaircraft belonging to the bank are reorderedaccording to their priority ranking, and that otheraircraft in the traffic sample are still sequenced inan FCFS order based on ETARWY. By reorderingonly the bank aircraft and scheduling theremaining aircraft according to an FCFS sequence,the impact of the reordering on schedulingefficiency is minimized. Table 4 shows theresulting order of arrival when the bank aircraftare scheduled according to the preferred sequenceof arrival. The second and third columns show thepriority sequence which is input to the scheduler,with the bank aircraft ordered according to theirpriority ranking, and the remaining aircraft timeordered according to increasing ETA RWY . Thefourth and fifth columns show the resultingschedule time-ordered according to STARWY. Aswas the case with FCFS scheduling, the resultingorder of arrival does not match the sequence whichwas input to the scheduler because the schedulemust meet separation criteria at the runwaythreshold which are a function of aircraft weightclass and landing order. Although the resultingscheduled bank order does not precisely match thepreferred order, it does indeed match more closelythe preferred bank order than does the FCFSschedule shown in Table 3.Order DeviationTo quantify the effectiveness of the priorityscheduling method we need a measure of howclosely the scheduled order of arrival for adesignated bank matches the preferred arrivalorder. We first define a position shift (PS) for anaircraft as the difference between the aircraftposition in the preferred bank order and thesequence number in the scheduled bank order.PS NPREFERRED NSCHEDULEDwhere N is the sequence numberof the aircraft within the bankTable 5 illustrates the calculation of the PS foreach of the aircraft in the bank defined in Table 1.The position shift of each aircraft is calculated forboth FCFS scheduling (Table 3) and priorityscheduling (Table 4). Note that a positive PSindicates that an aircraft is scheduled ahead of itspreferred position in the bank, and a negativeposition shift indicates that an aircraft is scheduledbehind its preferred position in the bank. For6

ty SequenceAircraft IDETARWYResulting ScheduleAircraft IDSTARWYDAL428AAL1150 (1)DAL1670EGF006DAL834DAL2062UAL359ASE924EGF628 (2)AAL1934 (3)AAL1428 (4)AAL1554 (5)AAL410DAL431DAL756DAL428AAL1150 (1)DAL1670EGF006DAL834DAL2062UAL359ASE924AAL1934 (3)EGF628 (2)AAL1428 (4)AAL1554 13627369537373782378938433895395239534005Table 4 Priority Sequence and resulting scheduleexample, the sequence number of flight EGF628 inthe preferred order of arrival is 2 while itssequence number in the FCFS schedule is 5 and itssequence number in the priority schedule is 3. Thisresults in a PS of -3 for the FCFS schedule and -1for the priority schedule and reflects the fact thatEGF628 is scheduled 3 slots behind its preferredposition in the bank using FCFS scheduling, and 1slot behind the preferred position using priorityscheduling.Because we are interested in how closely theoverall bank order matches the preferred order, wewant a single measure which will indicate thedeviation from the preferred order for a bank ofany length. We then define the order deviation(OD) for a bank as the algebraic sum of theabsolute value of the PS for each aircraft in thebank divided by the number of aircraft in the 1934AAL1428AAL1554EGF628OD PS # of bank aircraft# of bank aircraftIt can be seen from this definition that if the ODfor a bank of aircraft equals zero, then thescheduled bank order is the same as the preferredbank order. More importantly, the larger the valueof the OD, the further the scheduled bank orderdeviates from the preferred order. This will allowus to easily compare the relative effectiveness ofthe FCFS and priority scheduling methods inproducing the preferred order of arrival. The orderdeviations for each scheduling method using theexample in Table 5 are calculated below. Becausethe priority scheduling scheme results in thedesignated bank arriving in an order which moreclosely matches the preferred arrival order, theOD for the priority scheduled bank is smaller thanthat for the FCFS scheduled bank.PositionShift 4EGF628AAL1428AAL1554PositionShift forPrioritySchedule0-1100Table 5 Calculation of position shift for a bank of aircraft7

ODFCFS ODPRIORITY 0 3 1 1 1 1.25 0 1 1 0 0 0.45In order to investigate the statistical performanceof the two scheduling methods, a large number oftraffic samples are generated for a specified bank.To compare the effectiveness of FCFS schedulingand priority scheduling for a large number oftraffic samples, we define the average OD as thesum of the ODÕs for each traffic sample divided bythe number of traffic samples.ODAVERAGE OD# of traffic samples# of traffic samplesSimulation Inputs/OutputsInputs to the fast-time simulation include theaircraft identifier of the lead aircraft in the bank,the size of the bank, the number of trafficsamples, the range in Center arrival error, theairport configuration, and airport acceptance rate.In order to determine the statistical performanceof the FCFS algorithm and the priority algorithm,500 traffic samples are generated for eachdesignated bank. Each traffic sample is comprisedof 108 jet and turboprop aircraft, 72 of which areAAL or EGF flights. In this simulation themodeled airport configuration is south flow forDFW. Because the traffic model is limited to asingle arrival rush period, and because of themanner in which a bank is defined, banks cannotbe formed at or near the end of the arrival rushperiod. For example, if the bank length is specifiedas 20, and the designated lead aircraft is the 100thaircraft in the arrival rush, no bank will be formedbecause there are not enough aircraft following thelead aircraft to form a bank. Although we attemptto form banks across the entire range of the trafficrush period, this cannot be done for the reasonsjust outlined. The output of the fast-timesimulation includes the average OD as well ashistograms of the position shifts for each bank ofaircraft. Total delays and histograms of individualdelays for all aircraft in the traffic rush aregenerated as well. Results can then be comparedfor the FCFS scheduling algorithm and the priorityscheduling algorithm.Results and DiscussionThe primary measure of success of the priorityscheduling algorithm is the closeness of the matchbetween the scheduled order of arrival and thepreferred order of arrival. Figure 1 is a plot of theaverage order deviation for a bank size of 20, arange in Center arrival errors of /- 5 minutes, andan AAR of 96 aircraft/hour. For a designated bankwhose lead aircraft has a nominal ETAFG given onthe x-axis, a corresponding pair of ordinates showsthe average OD for the bank using FCFS schedulingand priority scheduling. Figure 1 confirms that thepriority scheduling algorithm significantly reducesthe avera

AIRLINE ARRIVAL PRIORITIZATION IN SEQUENCING AND SCHEDULING Gregory C. Carr Heinz Erzberger Frank Neuman NASA Ames Research Center Moffett Field, CA 94035-1000, USA phone: (650) 604-2545/ fax: (650) 604-0174/ email: gcarr@mail.arc.nasa.gov Abstract The basic objective of arrival sequencing and scheduling in air traffic control automation is to