Dynamic Constraint Aggregation for Solving Very Large-scale Airline Crew Pairing Problems
- PDF / 1,572,198 Bytes
- 23 Pages / 439.642 x 666.49 pts Page_size
- 62 Downloads / 193 Views
Dynamic Constraint Aggregation for Solving Very Large-scale Airline Crew Pairing Problems Guy Desaulniers1,2 Franc¸ois Soumis1,2
· Franc¸ois Lessard1,2 · Mohammed Saddoune1,3 ·
Received: 13 March 2020 / Accepted: 19 June 2020 / © Springer Nature Switzerland AG 2020
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
This article belongs to the Topical Collection on: Decomposition at 70 Guy Desaulniers
[email protected] 1
Department of Mathematics and Industrial Engineering, Polytechnique Montr´eal, Montr´eal, Canada
2
Group for Research in Decision Analysis (GERAD), Montr´eal, Canada
3
Department of Computer Science, University of Hassan II, FST of Mohammedia, Casablanca, Morocco
19
Page 2 of 23
SN Operations Research Forum
(2020) 1:19
1 Introduction When planning the operations of an airline, the crew scheduling phase consists of determining the work schedules of a set of crew members in order to operate a given one-week or one-month flight schedule at minimum cost. Given its complexity, this problem is usually decomposed in two problems that are solved sequentially: the crew pairing problem (CPP) and the crew rostering problem (CRP). The CPP aims at building least-cost crew pairings such that each flight is covered by at least one pairing and some side constraints are satisfied. A pairing is a sequence of one or more duties separated by rest periods which starts and ends at the same crew base (an airport where crew members are assigned). A duty is a sequence of flights separated by connections which form a working day. It can contain one or several deadheads, i.e., flights where the crew travels as passengers to be repositioned. Duties and pairings are subject to numerous feasibility rules imposed by the labor agreement and the aviation authorities. Given a set of pairings, the CRP consists of constructing work schedules for a g
Data Loading...
