Reliable Reserve-Crew Scheduling for Airlines

We study the practical setting in which regular- and reserve-crew schedules are dynamically maintained up to the day of executing the schedule. At each day preceding the execution of the schedule, disruptions occur due to sudden unavailability of personnel, making the planned regular and reserve-cre...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-09
Main Authors: Schrotenboer, Albert H, Wenneker, Rob, Ursavas, Evrim, Zhu, Stuart X
Format: Article
Language:English
Subjects:
Airline operations
Algorithms
Flexibility
Markov chains
Recovery
Repair
Reserve crews
Robustness
Schedules
Scheduling
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the practical setting in which regular- and reserve-crew schedules are dynamically maintained up to the day of executing the schedule. At each day preceding the execution of the schedule, disruptions occur due to sudden unavailability of personnel, making the planned regular and reserve-crew schedules infeasible for its execution day. This paper studies the fundamental question how to repair the schedules' infeasibility in the days preceding the execution, taking into account labor regulations. We propose a robust repair strategy that maintains flexibility in order to cope with additional future disruptions. The flexibility in reserve-crew usage is explicitly considered through evaluating the expected shortfall of the reserve-crew schedule based on a Markov chain formulation. The core of our approach relies on iteratively solving a set-covering formulation, which we call the Robust Crew Recovery Problem, which encapsulates this flexibility notion for reserve crew usage. A tailored branch-and-price algorithm is developed for solving the Robust Crew Recovery Problem to optimality. The corresponding pricing problem is efficiently solved by a newly developed pulse algorithm. Based on actual data from a medium-sized hub-and-spoke airline, we show that embracing our approach leads to fewer flight cancellations and fewer last-minute alterations, compared to repairing disrupted schedules without considering our robust measure.
ISSN:2331-8422