Dynamic Constraint Aggregation for Solving Very Large-scale Airline Crew Pairing Problems

Guy Desaulniers (), François Lessard, Mohammed Saddoune and François Soumis
Additional contact information
Guy Desaulniers: Polytechnique Montréal
François Lessard: Polytechnique Montréal
Mohammed Saddoune: Polytechnique Montréal
François Soumis: Polytechnique Montréal

SN Operations Research Forum, 2020, vol. 1, issue 3, 1-23

Abstract: Abstract The monthly crew pairing problem (CPP) consists of determining a least-cost set of feasible crew pairings (sequences of flights starting and ending at a crew base) such that each flight is covered once and side constraints are satisfied. This problem has been widely studied but most works have tackled daily or weekly CPP instances with up to 3500 flights. Only a few papers have addressed monthly instances with up to 14,000 flights. In this paper, we propose an effective algorithm for solving very large-scale CPP instances. This algorithm combines, among others, column generation (CG) with dynamic constraint aggregation (DCA) that can efficiently exploit the CG master problem degeneracy. When embedded in a rolling-horizon (RH) procedure, DCA allows to consider wider time windows in RH and yields better solutions. Our computational results show, first, the potential gains that can be obtained by using wider time windows and, second, the very good performance of the proposed algorithm when compared with a standard CG/RH algorithm for solving an industrial monthly CPP instance with 46,588 flights.

Keywords: Airline crew pairing problem; Large-scale instances; Column generation; Dynamic constraint aggregation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s43069-020-00016-1 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:snopef:v:1:y:2020:i:3:d:10.1007_s43069-020-00016-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-020-00016-1

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

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