航班延误与时刻设计课件

1、New Approaches to Improving the Robustness of Airline SchedulesProf. John-Paul ClarkeDepartment of Aeronautics & AstronauticsMassachusetts Institute of TechnologyOutlineBackground & MotivationRobust Maintenance RoutingFlight Schedule Re-TimingDegradable Airline ScheduleConclusionsSchedule DesignCrew

2、 SchedulingFleet AssignmentMaintenance RoutingAirline Schedule Planning ProcessMost existing airline schedule planning methods assume that aircraft, crews, and passengers will operate as plannedAirline OperationsBad weather reduces airport capacityAirlines cancel or delay flights to reduce demandDel

3、ays propagate through the networkAirlines must reschedule aircraft/crew and re-accommodate passengersPassengers are not satisfiedThey are delayedThey have no control over their delayAll passengers on a given aircraft are delayed equally regardless of fare classDelays & CancellationsTrend (1995-1999)

4、Significant increase (100%) in flights delayed more than 45 minSignificant increase (500%) in the number of cancelled flightsYear 2000 30% of flights delayed3.5% of flights (approx. 140,000) cancelledFuture:Delays and cancellations may increase dramatically more frequent and serious schedule disrupt

5、ions and revenue loss RobustnessNeed schedules that are robust (insensitive) to delays and cancellationsDefinitions of robustness Minimize cost (expected/worst case deviations from optimal)Minimize aircraft/passenger delays and disruptions Easy to recover (aircraft, crew, passenger)Isolate disruptio

6、ns and reduce the downstream impactTwo ways to provide robustness Re-optimize schedule after disruptions occur (operation stage)Build robustness into the schedules (planning stage)OutlineBackground & MotivationRobust Maintenance RoutingGraduate Student: Shan LanJoint work with Prof. Cindy BarnhartFl

7、ight Schedule Re-TimingDegradable Airline ScheduleConclusionsDelay PropagationArrival delay may cause departure delay for the next flight that is using the same aircraft if there is not enough slack between these two flightsDelay propagation may cause schedule, passenger and crew disruptions for dow

8、nstream flights (especially at hubs)f1MTTf2f1f2Propagated v. Independent DelayFlight delay may be divided into two categories:Propagated delayCaused by inbound aircraft delay function of routing20-30% of total delay (Continental Airlines)Independent delayCaused by other factors not a function of rou

9、tingAppropriately allocated slack can reduce propagated delayAdd slack where advantageousReduce slack where less neededDefinitionsijSlackMin Turn TimePDTPATADTAATPDIADTADjiiPDIDDTDDPlanned Turn TimeModeling IssuesDifficult to use leg-based models to track the delay propagationOne variable (string) f

10、or each aircraft route between two maintenance events (Barnhart, et al. 1998)A string: a sequence of connected flights that begins and ends at maintenance stationsDelay propagation for each route can be determinedNeed to determine delays for each feasible routeMost of the feasible routes havent been

11、 realized yetPD and TAD are a function of routingPD and TAD for these routes cant be found in the historical dataIAD is not a function of routing and can be calculated by tracking the route of each individual aircraft in the historical data String Based FormulationComputational ResultsTest NetworksJ

12、uly 2000 dataModelRoutesAug 2000 data Propagated delays (August 2000) Model Building and ValidationResults - DelaysTotal delays and on-time performance Passenger misconnectsOutlineBackground & MotivationRobust Maintenance RoutingFlight Schedule Re-TimingGraduate Student: Shan LanJoint work with Prof

13、. Cindy BarnhartDegradable Airline ScheduleConclusionsFlight Schedule Re-TimingObjective Reduce the number of passenger misconnections by adjusting departure times so that passenger connection times are correlated with the likelihood of a missed connection (disruption)Add connection slack where it i

14、s need mostSolution ApproachDerive distributions from historical data for number of passengers disrupted for each connectionFormulate and solve re-timing model that minimizes the number of disrupted passengersDefinitionsAAT = Actual Arrival TimeACT = Actual Connection TimeADT = Actual Departure Time

15、MCT = Minimum Connection TimePAT = Planned Arrival TimePCT = Planned Connection TimePDT = Planned Departure TimeSlackMCTPCTPDTAATPATADTACT Illustration of the IdeaAirport AAirport BAirport CAirport DSuppose 100 passengers in flight f2 will connect to f3P (misconnect)= 0.3, E(disrupted pax) = 30P(mis

16、connect)=0.1,E(disrupted pax) =10 Expected disrupted passengers reduced: 20Connection-Based FormulationObjectiveminimize the expected total number of passenger misconnectsConstraints:For each flight, exactly one copy will be selected.For each connection, exactly one copy will be selected and this se

17、lected copy must connect the selected flight-leg copies.The current fleeting and routing solution cannot be altered. Connection-Based FormulationsTheorem 1:The second set of constraints are redundant and can be relaxedTheorem 2:The integrality of the connection variables can be relaxed Formulation I

18、: CFSRMore Model PropertiesTheorem 3: ACFSR model is equivalent to CFSR modelTheorem 4:DCFSR model is equivalent to CFSR modelTheorem 5: The LP relaxation of CFSR model is at least as strong as that of ACFSR, and can be strictly stronger.Theorem 6: The LP relaxation of CFSR model is at least as stro

19、ng as that of DCFSR, and can be strictly stronger.Solution ApproachRandom variables can be replaced by their meanDistribution ofBranch-and-PriceJuly 2000 dataRAMRRoutesAug 2000 dataFSRScheduleCFSRACFSRComputational ResultsNetworkWe use the same four networks, but add all flights together and form on

20、e network with total 278 flights.Model Building and ValidationStrength of the formulationsComputational ResultsAssume 30 minute minimum connecting timeAssume 25 minute minimum connecting timeAssume 20 minute minimum connecting timeComputational ResultsNumber of copiesEstimated reduction in total pas

21、senger delays: (30 minutes MCT)20% (30 minute time window), 16% (20 minute time window), 10% (10 minute time window)OutlineBackground & MotivationRobust Maintenance RoutingFlight Schedule Re-TimingDegradable Airline ScheduleGraduate Student: Laura KangConclusionsDegradable Airline ScheduleObjectiveD

22、evelop airline schedule that is robust, i.e. delays are isolated Provide priority (and thus reliability) for each flight Improve customer satisfaction by giving passengers an accurate expectation of the level of serviceProvide basis for revenue management and ATC auctionsSolution ApproachPartition s

23、chedule into smaller independent prioritized schedules (layers) subject to operational feasibilityImplementation Optionsfleet assignmentaircraft routingcrew schedulingschedule design DASD-ARM (Route-based Formulation)DASD-FAMD-SPM (Flight-based Formulation)DASIP ModelPrioritize layers based on reven

24、ue (e.g. group highest revenue flights together in most reliable layer)Revenue is “protected” if all flight legs in an itinerary are in a “protected” layerIP model maximizes the total protected revenue subject to feasibility constraintsPrototype 2 layers implementationLayer 1: 60% (protected layer)L

25、ayer 2: 40%Model Statistics1,134 flight legs274 aircraft1,744 itineraries (8% of total)Single flight leg: 1,1302 flight legs: 6133 flight legs: 153,091 passengers (80% of total)$10,839,340 revenue (84% of total)NotationIndicesrroutefitineraryijflightklayer (k=1 K)ijf 1 if flight ij is in itinerary f

26、, 0 otherwiseDecision variablesyrk1 if route r is in layer k, 0 otherwisezfk 1 if itinerary f is in layer k, 0 otherwisexijk 1 if flight ij is in layer k, 0 otherwiseParametersvfkrevenue for itinerary f is placed in layer k Chcapacity at hub h in bad weatherSk fraction of layer k ar number of flight

27、s in route rarhnumber of flights departing at hub h in route rACNnumber of aircraftFlight-based FormulationRoute-based FormulationGreedy Flight-Leg PairingSTEP 0: Fix connections for non-hub to non-hub flightsSTEP 1: Pair flight segments at spoke airports using the revenue paring with aircraft utili

28、zation heuristicSTEP 2: Combine paired flight segments from step 1 at hub airports using the revenue paring with aircraft utilization heuristicSTEP 3: Partition very long routes into several shorter routesGreedy Flight-Leg Pairing1001010100Swapping SearchCheck swapping feasibilityCheck constraints s

29、atisfactionCheck objective function improvementAssume revenue is protected proportionally to the number of flight legs in the protected layerSwaproute iroute ji1i2i3i4i5i6j1j2j3j4j5j6i1i2i3i4i5i6j1j2j3j4j5j6i1i2i3i4i5i6j1j2j3j4j5j6i1i2i3i4i5i6j1j2j3j4j5j6Tabu SearchSTEP 0: start with initial solutio

30、n x* from revenue paring heuristicsWHILE( number of iteration is less than N )STEP 1: Swapping Search. If f(x) f(x*), x* xSTEP 2: Update Tabu listIf a pair was in a tabu list for Y iterations, remove it from the tabu listSet X pairs which were swapped in the search in the tabu listTabu search is sensitive to its parameters X, Y, N State-of-art decision for X, Y, N D-ARM w/Heuristics8,123,060D-SPM8,667,632IP Objective Function Val