A branch-and-price heuristic for the crew pairing problem with language constraints

Frédéric Quesnel, Guy Desaulniers and François Soumis

European Journal of Operational Research, 2020, vol. 283, issue 3, 1040-1054

Abstract: In large commercial airlines, the monthly schedule (roster) of the crew members is usually determined by solving two problems sequentially, namely, the crew pairing problem (CPP) and the crew rostering problem (CRP). While the CPP finds a set of low-cost feasible anonymous pairings, the CRP assigns these pairings to the crew members to create a valid roster. The CRP often involves language constraints, which request language qualifications among the crew members operating some flights. In this case, the pairings returned by the CPP are not necessarily compatible with the qualifications of the available crew members, resulting in a large number of violated language constraints in the CRP. In this paper, we propose a new CPP variant, called the CPP with language constraints (CPPLC), that takes into account two types of soft language constraints that help producing more suitable pairings for satisfying the CRP language constraints. To solve the CPPLC, we develop a branch-and-price heuristic that includes an efficient partial pricing strategy for handling the large number of subproblems needed to model the language constraints. We also propose an acceleration technique to compute a high-quality (usually fractional) solution at the root node of the search tree. The proposed algorithm is tested on seven real-world datasets. We show that pairings produced by the CPPLC are better-suited for the CRP, resulting in a reduction of the number of violated CRP language constraints that varies between 61% and 96%, when compared to the pairings obtained from the traditional CPP.

Keywords: OR in airlines; Aircrew scheduling; Crew pairing; Language constraints; Column generation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719309555
Full text for ScienceDirect subscribers only

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:eee:ejores:v:283:y:2020:i:3:p:1040-1054

DOI: 10.1016/j.ejor.2019.11.043

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().