Abstract FR:

L'objet de cette these est de resoudre le probleme de la partition d'ensemble optimale, dans le cadre de deux applications industrielles relatives a l'optimisation de l'allocation des ressources humaines dans les compagnies aeriennes. Mathematiquement, il s'agira d'optimiser une fonction economique lineaire soumise a un type particulier de contraintes lineaires dites contraintes de partitionnement, en plus d'autres contraintes de types quelconques propres a chaque application traitee. En pratique, il s'agira de planifier le travail du personnel navigant aerien et de minimiser les couts dus a son exploitation. Cette these a ete effectuee dans sa totalite dans un contexte industriel en collaboration avec la societe prologia, et a donne naissance au logiciel cp-air qui est actuellement en service dans trois compagnies aeriennes francaises. Les travaux que nous avons effectues autour de la partition d'ensemble peuvent etre utilises pour d'autres applications pratiques qui possedent la meme modelisation mathematique. Ces applications sont souvent relatives a l'allocation de ressources humaines ou materielles. Nos resultats peuvent etre facilement etendus a la couverture d'ensemble, et donc a une gamme plus larges d'applications. Nous avons du resoudre des instances de problemes d'optimisation combinatoire particulierement difficiles (certains prouves np-complets). Nous avons passe en revue les aspects theoriques et algorithmiques lies a des domaines aussi divers que la programmation lineaire, la programmation en nombres entiers, la programmation logique, la programmation par contraintes et la theorie des graphes. Plus precisemment, on traite dans ce document de l'application d'ordonnancement des vols ou construction de rotations d'equipage (crew pairing, en anglais), puis du probleme d'affectation du personnel navigant (crew rostering). Nous avons realise une etude plus theorique de ce second probleme en le considerant comme un veritable puzzle. L'approche de resolution que nous proposons est basee sur une methodologie de separation et evaluation combinee avec une generation de colonnes, qui est soit enumerative, soit utilise le plus court chemin avec contraintes de ressources. L'algorithme du simplexe represente la clef de voute de notre methodologie. Nous en avons fait notre propre implementation adaptee aux programmes lineaires de partition d'ensemble.