Improving airline operational performance …

1 Ann Oper ResDOI airline operational performancethrough schedule perturbationAndrew J. Schaefer George L. NemhauserC Springer Science+Business Media, LLC 2006 AbstractSchedule development is typically the first phase of the airline planning present a framework for perturbing scheduled departure and arrival times after a crewschedule has been found. We characterize perturbations that keep a schedule legal while notincreasing the planned cost of the crew schedule . We show that when random delays occurin operations, the expected cost can be reduced and the on-time performance results are reported for two real fleets and a large number of crew crew programmingAMS Classification:90B06 airlines operate under uncertain conditions. Weather, congestion, and mechanical break-downs are examples of why flights may not operate as planned.

2 The operational performanceof airlines is becoming worse. In the United States, one flight in four is delayed during thesummer, and air traffic is expected to double by 2015 (Anonymous, 2001). At large airports,nearly half of all flights are delayed (Anonymous, 2001). On-time statistics are of great im-portance to airlines . The Bureau of Transportation Statistics (BTS, 1998) defines a flight tobe on-time if it arrives no later than 15 minutes after its scheduled arrival time and publishesrankings of airline on-time performance . These ratings can be used for marketing purposesand a good on-time performance may lead to greater customer schedules can affect their own on-time performance . In the airline planning process,the first step isschedule development. During the schedule development phase an airlinedetermines when and where it will fly.

3 It also determines thescheduled block timeof eachflight, that is, the planned duration of each flight, orleg. For the same origin and destinationA. J. Schaefer ( )Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA 15261e-mail: L. NemhauserSchool of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332 SpringerAnn Oper Resthis time can vary between airlines . It can also vary by time of day for a given airline . Forinstance, an airline might allocate a greater block time to a flight that departs or arrives duringthe busiest part of the development typically takes place at least one year before a flight departs. Afterschedule development, the airline solves thefleet assignmentproblem, which assigns eachleg to a fleet, or different aircraft type.

4 Theroutingproblem determines the sequence in whicheach plane will fly legs. After these problems have been solved thecrew schedulingproblemdetermines a set of crew trips, orpairings, that partition the set of legs to be , these problems have been considered sequentially, with little or no feedbackfrom later stages to earlier stages. However, some work has been done on integrating thevarious stages of airline planning. Lohatepanont and Barnhart (2004) integrate scheduledevelopment and fleet assignment to increase the number of flights that may be et al. (2002) combine crew scheduling and routing with time windows to increasethe number of feasible pairings, thus reducing the planned cost of the resulting crew , Barnhart and Krishnamurthy (2000) propose a fleeting model with time and Barnhart (2003) incorporate maintenance considerations into crew on-time performance is defined relative to scheduled block time, an airline canimprove its on-time performance by increasing the scheduled block times of legs.

5 However,the planned flying time of a crew schedule is a lower bound on its planned cost, which is inturn a lower bound on its operational cost (Schaefer et al., 2004). Crew costs are second onlyto fuel costs for airlines , and increasing the planned flying time could cause crew costs toincrease. This paper introduces a method for determining schedule perturbations that improveon-time performance without increasing crew propose a new approach that perturbs the original flight schedule to improve theoperational performance of a given crew schedule . The perturbation is made in such a waythat the crew schedule and the routing remain feasible. We show that such a perturbationwill lead to a performance in operations which, under certain conditions, is likely to bebetter than, and is at least as good as, the performance of the crew schedule under the originalschedule.

6 Our computational experiments indicate that a crew schedule can have a noticeableimprovement in operational cost and on-time percentage with the perturbed flight Section 1 we review how pairing feasibility and costs are determined. This descriptionis needed in Section 2 where we discuss schedule perturbations. The effect of scheduleperturbation in airline operations is considered in Section 3. We provide computationalresults in Section 4 and give conclusions in Section Feasibility and crew pairing costsBecause a pilot typically may fly only one fleet, the crew scheduling problem is separable byfleet. A crew flies a set of consecutive flight legs, called aduty, that follow certain regulationsand contractual restrictions. The time between two consecutive legs within a duty, orsit time,must be at least a minimum amount if a crew changes planes.

7 Theelapsed timeof a duty isthe number of minutes the duty lasts, including a briefing period before the first leg and adebriefing period after the last , or crew trip, is a sequence of duties, each separated by arestperiod whichmust exceed a minimum length. Thetime away from base(TAFB) of a pairing is the numberof minutes from the beginning to the end of the pairing. Pairings flown within the mustadhere to both FAA and contractual rules. For instance, to prevent crew fatigue the 8-in-24 rule requires compensatory rest for a crew that is scheduled to fly more than 8 hours withinSpringerAnn Oper Resany 24 hour period (FAA, 1999). Although we focus on the airline industry in the UnitedStates, similar regulations exist in other scheduleis a set of pairings that partitions the legs to be flown by a single crew scheduling problem is usually modeled as a set partitioning problem:{mincx:Ax=1,xbinary}(1)wherecjis the cost of pairingj, andaij, theijth component ofA, is 1 if pairingjflieslegi, and 0 otherwise.

8 A survey of recent advances in deterministic airline crew schedulingis given in Barnhart et al. (2002).When crew schedules are found, pairings are not yet assigned to particular pilots, and sothe cost of a crew schedule is not expressed in monetary terms, but in minutes of pay andcredit. Since pilot salaries differ, determining the monetary cost of a crew schedule is onlypossible once pairings have been assigned to particular pilots. The flight-time-credit (FTC)of a duty is the difference between its total cost in minutes of pay and credit and the totalblock time expressed as a percentage of the total block time of the duty. A similar measureexists for pairings and crew method for calculating the planned cost of a crew schedule varies by airline . We givean example of one method, using the notation from Schaefer et al.

9 (2004). LetFTC( ) denotethe planned FTC of any duty, pairing or crew schedule . Letqbe any pairing consisting ofdutiesd1,..,dk. For any legli, letdep(li) be the scheduled departure time of legliin minutesand letarr(li) be its scheduled arrival time in minutes. These times are relative to the start ofthe pairing, so that the beginning of dutydi+1is greater than the end of dutydi. Letblock(li)be the planned block time of legliin minutes, defined byblock(li)=arr(li) dep(li).Letbriefbe the length of the pilot briefing period prior to every duty anddebriefbe the length ofthe pilot debriefing period after every duty. The parametersbriefanddebriefare constants andare in minutes. For a given dutydi, letlsandltbe its first and last leg, respectively, and definethe plannedelapsedtime of the duty aselapse(di)=arr(lt) dep(ls)+brief+ <1 be a fraction representing the rate of pay for elapsed time in terms of minutesof pay and credit.

10 Letmgdbe the minimum guarantee for a duty, which is given in minutesof pay and credit. Theplanned duty costof dutydis expressed in minutes of pay and creditand is given byb(d)=max i dblock(li),re elapse(d),mgd .(2)Letlaandlbbe the first and last legs, respectively, of a pairingq. The plannedtime awayfrom baseof pairingqis the total number of minutes that elapse during the pairing givenbyTAFB(q)=arr(lb) dep(la)+brief+ <1 be a fraction representingthe rate of pay of time away from base, and letmgpbe a minimum guarantee per duty in apairing. Then theplanned pairing costof pairingqis given bycq=max k i=1b(di),rt TAFB(q),mgp k .(3)Vance et al. (1997) use values ofre=47,mgd=0,rt=27, andmgp= Oper ResThe planned FTC of pairingqis defined byFTC(q)=cq j qblock(lj) j qblock(lj) 100.(4)Letc(C) be the planned cost of a crew scheduleCconsisting of pairingsq1.