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

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.