Optimisation simultanée des rotations et des blocs mensuels des équipages aériens

The integrated crew pairing and crew assignment problem for pilots consists of producing
a minimum-cost set of pairings and schedules such that each flight leg is covered once by one
pairing and one schedule, and side constraints are satisfied such as pilot availability in each
crew base station. A pairing is a sequence of duties separated by rest periods that must start
and end at the same crew base. A duty is a sequence of flights separated by connections and
ground waiting times, forming a working day for a crew. The construction of pairings and
schedules must respect all safety and collective agreement rules. Besides the introduction,
literature review and conclusion, this thesis is composed of three main chapters where each
one presents the performed work for a specific research objective. These three chapters use
the same problem instances based on real-data provided by a major US airline.
The crew pairing problem has been traditionally solved in the industry by a heuristic
three-phase approach that solves sequentially a daily, a weekly, and a monthly problem.
This approach prohibits the repetition of the same flight number in a pairing. The first objective
in this thesis is to highlight two weaknesses of the three-phase approach and propose
an alternative solution approach that exploits flight number repetitions in pairings. First,
when the flight schedule is irregular, we show that better quality solutions can be obtained
in less computational times if the first two phases are skipped and the monthly problem is
solved directly using a rolling horizon approach based on column generation. In fact, this approach
has reduced the solution fat by 34%. The solution fat is a quality measure that shows
the percentage of time not worked but paid. Second, even if the flight schedule is completely
regular, we show that better quality solutions can be derived by skipping the daily problem
phase and solving the weekly problem directly. Indeed, the proportion of pairings with such
repetitions represents 48.8% causing a mean reduction in the solution fat by 16%.
In practice, both the crew pairing and crew assignment problems are independently modeled
and sequentially solved. The use of a sequential approach considerably reduces the
complexity of the global problem but produces solutions that may not be conform with airline
desires. The second objective in this thesis is to propose a model that fully integrates
the crew pairing and crew assignment problems and solve it in a single step. Due to the
large size of this integrated model, we propose a solution method that combines a column
generation and a dynamic constraint aggregation method. Since the latter method requires a
good initial partition, this partition is provided by a set of pairings found with the sequential

Résumé

R´esum´e
Le probl`eme int´egr´e de la construction des rotations et des blocs mensuels des pilotes
consiste `a d´eterminer un ensemble de rotations et de blocs mensuels pour les pilotes tels
que chaque segment de vol est couvert par une seule rotation et un seul bloc, et ce, tout en
satisfaisant des contraintes suppl´ementaires comme la disponibilit´e des pilotes dans chaque
base. Une rotation est une s´equence de vols effectu´ee par un ´equipage durant une p´eriode
donn´ee partant et revenant `a la mˆeme base. Un bloc (ou horaire) mensuel est une s´equence
de rotations s´epar´ees par des p´eriodes de repos. La construction des rotations et des blocs
mensuels doit ˆetre conforme aux r`egles de la s´ecurit´e a´erienne, aux r`egles d'op´eration de la
compagnie et aux r`egles contenues dans les conventions collectives entre les employ´es et la
compagnie a´erienne. `A part l'introduction, la revue de litt´erature et la conclusion, cette th`ese
est compos´ee de trois chapitres principaux dont chacun pr´esente les travaux r´ealis´ees pour un
objectif de recherche bien pr´ecis. Ces trois chapitres utilisent les mˆemes instances du probl`eme
bas´ees sur des donn´ees r´eelles fournies par une grande compagnie a´erienne am´ericaine.
Le probl`eme de construction des rotations se r´esout traditionnellement en trois phases
de mani`ere s´equentielle : un probl`eme journalier, un probl`eme hebdomadaire et un probl`eme
mensuel. Cette approche interdit la r´ep´etition du mˆeme num´ero de vol dans une rotation. Le
premier objectif de cette th`ese est de mettre en ´evidence deux faiblesses de cette approche
s´equentielle et proposer `a la place une approche alternative qui permet la r´ep´etition des vols
dans une mˆeme rotation. Premi`erement, nous montrons que lorsque l'horaire des vols est
irr´egulier, les deux premi`eres phases ne sont qu'une perte de temps et on peut obtenir de
meilleures solutions en moins de temps si le probl`eme mensuel est r´esolu directement en utilisant
une approche d'horizon fuyant faisant appel `a une m´ethode de g´en´eration de colonnes.
En effet, cette approche a permis de diminuer le gras de la solution de 34% en moyenne o`u le
gras est une mesure de qualit´e portant sur le pourcentage du temps non travaill´e mais pay´e
durant un horizon. Deuxi`emement, mˆeme si l'horaire des vols est compl`etement r´egulier, la
qualit´e de la solution est meilleure si le probl`eme hebdomadaire est trait´e directement sans
exploiter le probl`eme journalier. En effet, les diff´erents tests ont montr´e qu'une moyenne de
48.8% des rotations contiennent des r´ep´etitions causant une r´eduction moyenne de 16% dans
le gras.