A crew pairing model and generation heuristic for airline disruption management using crew swaps and slack times

Date of Publication

2018

Document Type

Master's Thesis

Degree Name

Master of Science in Industrial Engineering

College

Gokongwei College of Engineering

Department/Unit

Industrial and Systems Engineering

Thesis Adviser

Charlie R. Sy

Defense Panel Chair

Bryan O. Gobaco

Defense Panel Member

Dennis E. Cruz
Willy F. Zalatar
Alma Maria Jennifer A. Gutierrez
Jonathan R. Dungca

Abstract/Summary

The trend in airlines, as more flights are being flown, is that delays have been less from unpredictable events and more from operations. Airlines push to maximize profits by scheduling flights with little to no regard for possible disruptions. Common practices that deal with disruptions, such as purposeful cancellation of flights, and assignment of emergency crew, are usually inefficient.

In the Philippines, the typical practice in industry is to plan schedules with the intention of minimizing costs, but no planning is made in preparation of disruptions. The typical viewpoint is that disruptions are random. However, data would suggest that over the years, delays in flights have been caused more by the air carriers themselves. Airlines also focus on recovery from disruptions as quick as possible, in order to be able to get back to the original schedule. This is usually costly as a lot of local resources are spent in order to get back on track.

More than just preparation for disruptions to prevent delays, it is more important to pinpoint were delay can propagate. While local resources will allow for lessening the effect of the delay, it is still likely to propagate towards those with connected resources in a system. Downstream propagation of initial delays to subsequent flights often occurs, and is what is often avoidable if correctly scheduled. Planning for disruptions in operations, while increasing planned costs, create flight schedules that are capable of handling disruptions. This, in comparison to post-flight recovery, is a more proactive approach. This becomes possible due to the prevalence of more predictable disruptions to airline operations, as well as the availability of large amounts of data to airlines.

This paper proposes a crew pairing model that schedules slack times and crew swaps that can potentially reduce the propagation of delay when a disruption occurs. The model consists of two phases that follow the set partitioning formulation. The first phase chooses the crew pairings for the schedule, while the second phase schedules crew swaps for contingencies. Mathematical formulations are presented.

The calculation of the delay propagation values using slack times, schedules on the timetable, historical flight delays and minimum ground connection times are essential to the models presented. They represent how likely each pairing is to propagate delay. The model chooses its pairings and swaps accordingly based on this delay propagation value.

A small set of flights is presented to show the schedules obtained from the traditional and robust models. This small set of flights is accompanied by a visual Gantt chart in order to depict how crew swaps, in particular, can affect the delay performance of a crew pairing schedule. This trivial example shows that the robust solution performs much better in terms of delays, primarily because the crew swaps were able to absorb much of the delay propagation.

The schedule using the traditional model and the robust model is then done for a set of 1890 flights from a real major airline. This is 2 weeks worth of operations for an entire fleet of the airline. The robust model is able to create solutions with higher planned costs but better delay indicators. To resolve the robustness-cost tradeoff, a function is introduced that gives an equivalent monetary cost to a delayed flight. The function follows an S curve, maintaining the characteristic that minor delays are tolerable while major delays are intolerable and costly for the airline. The function is open-ended, in that the airline can set its own multiplier to convert delay minutes into cost. It keeps the S curve shape no matter the input, but the airline is free to set at what level they are willing to pay and at what level they consider delays becoming intolerable. Sensitivity analysis shows that varying the perceived cost of delay of the airline greatly varies the optimal solution. The lower the cost of delay for the airline, the closer the optimal solution is to the traditional solution.

The best solution obtained, which balanced costs and robustness using the S function, was compared to an optimistic solution (low costs, low robustness), and a conservative solution (high costs, high robustness). Findings showed that the solution obtained by the robust model had good delay performance and an acceptable cost increase, and that this solution performed well across the different simulations, and different intensities of disruptions to the flight network.

Efforts to solve the large realistic crew pairing problem led to the implementation of using the duty tree and subsequence limitation, which improved computational time significantly. Furthermore, a heuristic is developed called the progressive pairing generation that places a hierarchy in the generation of pairings. Single-duty pairings are prioritized, then multiple-duty pairings, then pairings with deadheads. Using this heuristic resulted into the elimination of many suboptimal pairings that were generated and were part of the optimization phase when the exact algorithm was used. Due to there being less pairings generated using the heuristic, there is no assurance of optimality. Computational experiments showed a consistent ~2.5% higher costs using the heuristic as compared to using the exact algorithm. However, the exact algorithm was significantly more computationally intensive than the progressive pairing generation heuristic. So much so that it is likely that the exact algorithm can only be used for trivial sets of data. Computational complexity analysis showed that for the worst case scenario, the exact generation algorithm produced more pairings by a magnitude of 1,000,000.

The model presented is able to create crew pairing schedules using the heuristic as a methodology to solve large problems. The crew pairing schedules generated are of varying robustness depending on the needs of the airline. An approach to giving an equivalent cost to delays of flights is presented in order to resolve the robustness-cost tradeoff.

The study is able to obtain the schedule and crew swaps that are optimal for a hypothetical costing of delay. This crew pairing schedule is implementable and performs much better in simulations in terms of delay performance than that of the solution obtained from the traditional models.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTG007821

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

1 computer disc ; 4 3/4 in.

Keywords

Airlines--Management; Flight crews

This document is currently not available here.

Share

COinS