An adaptive greedy heuristic for large scale airline crew pairing problems

Zeren, Bahadır; Özcan, Ender; Deveci, Muhammet

Abstract

A crew pairing represents a sequence of flight legs that constitute a crew work allocation, starting and ending at the same crew base. A complete set of crew pairings covers all flight legs in the timetable of an airline for a given planning horizon. That determines the rosters for the crew and their quality, since those pairings would potentially include layovers, deadheads and connection times which are the key factors which directly contribute to the operational crew costs. Considering that crew costs form the second largest bit in the overall operational cost, generating optimized crew pairings is a vital process for the airline companies. In this study, a score-based adaptive greedy heuristic and a genetic algorithm are presented for solving large scale instances of airline crew pairing problems. Both solution methods are applied to a set of real-world problem instances from Turkish Airlines which is one of the largest carriers in the world. The empirical results show that the proposed approaches are indeed capable of generating high quality solutions for crew pairing, even for the large scale problem instances.

Citation

Zeren, B., Özcan, E., & Deveci, M. (2024). An adaptive greedy heuristic for large scale airline crew pairing problems. Journal of Air Transport Management, 114, Article 102492. https://doi.org/10.1016/j.jairtraman.2023.102492

• Journal Article Type: Article
• Acceptance Date: Sep 22, 2023
• Online Publication Date: Sep 29, 2023
• Publication Date: 2024-01
• Deposit Date: Oct 7, 2023
• Publicly Available Date: Oct 12, 2023
• Journal: Journal of Air Transport Management
• Print ISSN: 0969-6997
• Electronic ISSN: 0969-6997
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 114
• Article Number: 102492
• DOI: https://doi.org/10.1016/j.jairtraman.2023.102492
• Keywords: Airline crew pairing; Set covering; Heuristic; Genetic algorithm
• Public URL: https://nottingham-repository.worktribe.com/output/25707886
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S0969699723001357?via%3Dihub