Aircraft routing and crew pairing: Updated algorithms at Air France. (June 2020)

• Record Type: Journal Article
• Authors: Parmentier, Axel; Meunier, Frédéric
• Is Part Of: Omega. Volume 93(2020)
• Publication Date: 2020-06
• Subjects: Airline management -- Column generation -- Cut generation -- Shortest path algorithm; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2019.05.009
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: Compact integer program for aircraft routing. New pricing algorithm for crew pairing. Large industrial instances of aircraft routing and crew pairing solved to optimality. Algorithm for the integrated aircraft routing and crew pairing problem. Large industrial instances of the integrated problem solved to near optimality. Abstract: Aircraft routing and crew pairing problems aim at building the sequences of flight legs operated respectively by airplanes and by crews of an airline. Given their impact on airlines operating costs, both have been extensively studied for decades. Our goal is to provide reliable and easy to maintain frameworks for both problems at Air France. We propose simple approaches to deal with Air France current setting. For routing, we introduce an exact compact IP formulation that can be solved to optimality by current MIP solvers in at most a few minutes even on Air France largest instances. Regarding crew pairing, we provide a methodology to model the column generation pricing subproblem within a new resource constrained shortest path framework recently introduced by the first author. This new framework, which can be used as a black-box, leverages on bounds to discard partial solutions and speed-up the resolution. The resulting approach enables to solve to optimality Air France largest instances. Recent literature has focused on integrating aircraft routing and crew pairing problems. As a side result, we are able to solve to near optimality large industrial instances of the integrated problem by combining the aforementioned algorithms within a simple cut generating method.