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

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.