Horaires mensuels en transport aérien avec équité

Une compagnie aérienne doit créer pour ses pilotes et agents de bord des horaires qui minimisent ses dépenses, mais qui respectent aussi toute la règlementation en vigueur dans le transport aérien ainsi que les conventions collectives des employés. Quelques compagnies considèrent aussi la satisfaction des employés. Dans le cas qui nous intéresse, la satisfaction est liée à l'équité des horaires élaborés en terme du nombre d'heures travaillées. Un logiciel de planification développé chez AD OPT, division spécialisée dans le transport aérien de la compagnie Kronos, crée des horaires mensuels avec cet objectif d'équité. Tout d'abord, un programme linéaire permet de définir pour chaque employé une cible de temps à travailler selon son historique de travail et l'ensemble des tâches à couvrir durant le mois. Ensuite, un programme en nombres entiers est résolu permettant de créer les horaires mensuels en tentant de respecter au mieux ces cibles de temps. Comme les horaires sont mensuels, ce logiciel doit être utilisé à chaque mois pour créer de nouveaux horaires. Il est donc entendu qu'un résultat doit être obtenu dans des délais assez brefs. Or, sur la machine du GERAD qui sera utilisée pour ce mémoire, le logiciel prend 32 jours en temps CPU avant de fournir une première solution entière et cette solution n'est pas nécessairement proche de l'optimalité. Ce temps est beaucoup plus court chez AD OPT, car ils utilisent des machines multi-processeurs. Il reste quand même trop long et doit être réduit. Ce projet de maîtrise a donc pour but de comprendre les raisons qui rendent le logiciel si lent à fournir des solutions entières et d'établir des stratégies qui permettront d'obtenir des résultats au moins aussi bons, mais en un laps de temps beaucoup plus court. Tout d'abord, nous modifions le rôle que prend l'une des ressources dans les règles de dominance lors de la génération de colonnes. Cette modification permet d'éliminer beaucoup plus de chemins partiels et d'accélérer la recherche de plus courts chemins dans les sous-problèmes. Ensuite, nous changeons la manière de pénaliser les jours de congé excédentaires donnés aux employés. Nous proposons une pénalisation individuelle pour chaque occurrence directement au niveau des sous-problèmes à la place de considérer le nombre total d'occurrences de l'ensemble des employés dans le problème maître et de pénaliser seulement s'il y a dépassement d'un certain seuil. Après, nous proposons une toute nouvelle stratégie de branchement. Pour les 20 premiers branchements, nous fixons uniquement des colonnes respectant certains critères de qualité. Les critères sont initialement très sévères pour ensuite s'adoucir à chaque fois que trop peu de colonnes sont fixées. Pour les branchements ultérieurs, nous alternons entre la fixation de tâches à des employés et la fixation de colonnes en se basant uniquement sur le flot. Finalement, nous améliorons le calcul du nombre minimal de jours de congé que chaque employé doit avoir dans son bloc. De cette façon, la pénalisation des jours de congé excédentaires est plus réaliste et on ne paie plus pour des congés inévitables. Tous ces changements ont permis à chaque fois de gagner en temps de résolution. Au final, on se retrouve maintenant avec une première solution entière dont la valeur a été réduite de 71.72% par rapport à celle de la solution de référence et qu'on a obtenue en 1.33 jours au lieu de 32.06, ce qui représente donc 95.85% moins de temps. Les améliorations mentionnées ont été implémentées chez AD OPT. Les responsables ont été satisfaits autant par le temps de résolution nettement diminué que par la qualité des nouvelles solutions. Des facteurs additionnels pour considérer les préférences des employés pourront éventuellement être ajoutés, option qui auparavant n'était pas envisageable étant donné la difficulté qu'on avait à traiter l'équité seulement.