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

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 tackl...

Full description

Saved in:
Bibliographic Details
Published in:Operations Research Forum 2020-09, Vol.1 (3), p.19, Article 19
Main Authors: Desaulniers, Guy, Lessard, François, Saddoune, Mohammed, Soumis, François
Format: Article
Language:English
Subjects:
Aircraft
Algorithms
Applications of Mathematics
Aviation
Business and Management
Decomposition
Decomposition at 70
Labor contracts
Math Applications in Computer Science
Mathematical and Computational Engineering
Operations Research/Decision Theory
Optimization
Original Research
Schedules
Windows (intervals)
Working hours
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2662-2556
2662-2556
DOI:10.1007/s43069-020-00016-1