Set-cover master problem formulations for maximum flight coverage in branch & price solution algorithms for optimal aircrew rostering

George Kozanidis () and Odysseas Moschopoulos ()
Additional contact information
George Kozanidis: University of Thessaly
Odysseas Moschopoulos: University of Thessaly

Operational Research, 2025, vol. 25, issue 3, No 9, 34 pages

Abstract: Abstract We consider branch & price solution algorithms for optimal crew rostering in the context of airline management. Such methodologies employ an optimization model termed master, which, given a set of pre-constructed rosters (schedules), aims to assign a specific one to each crew member of the group under consideration, so that a suitable aggregate objective expressing the total system cost is minimized. The system cost is typically comprised of the cost related to the activities that remain uncovered plus the roster quality cost. Driven by the requirement that the number of crew members assigned to each activity must always match the corresponding crew complement, the master problem is typically formulated as a set-partition optimization model. We propose its alternative formulation as a set-cover optimization model, in which activity over-coverage is allowed, while roster quality is entirely ignored. This modeling choice expedites significantly the identification of the attainable duty coverage, which is of utter importance to airline practitioners. This is due to the superior computational behavior that the set-cover model exhibits compared to the set-partition one, combined with the fact that the suppression of the roster quality cost reduces significantly the computational effort involved. To transform the optimal set-cover solution into an equivalent set-partition one, we develop a mixed integer optimization model which removes suitably overcovered activities from the final rosters, so as to reach a solution that maximizes roster quality without affecting optimal coverage. The key property that removing activities from a legal and feasible crew roster cannot negate its legality nor its feasibility justifies the correctness of this approach. We report computational results on realistic problem instances demonstrating the behavior of the proposed methodology, assessing its computational performance, and highlighting the specific conditions under which it is preferable than the default one.

Keywords: Branch & price; Column generation; Set-cover vs. set-partition; Master problem formulation; Airline management; Crew rostering (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-025-00950-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:25:y:2025:i:3:d:10.1007_s12351-025-00950-0

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-025-00950-0

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().