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.

Abstract

Airlines have to provide schedules for pilots and flight attendants that minimize crew costs but also respect the regulations governing the airline industry and collective agreements. In addition, some airlines aim to consider the satisfaction of their employees. In our case, satisfaction is based on equity between employee schedules in terms of hours worked. AD OPT, a company that provides crew planning solutions for the airline industry, has developed software that creates monthly schedules with equity constraints. First, a linear program assigns a target for time worked to each employee, considering his/her work history and all the flights that need to be covered during the month. Then an integer program produces the monthly schedules, trying to respect these targets as well as possible. The software is used on a monthly basis to create new schedules. It is understood that results must be obtained in a relatively short time. However, the software takes 32 days in CPU time on a GERAD machine before providing an initial integer solution and this solution is not necessarily close to optimality. This time is much shorter at AD OPT that uses multi-thread computing. Nevertheless, it remains too long and must be reduced. This master's thesis examines why the software is so slow in providing integer solutions and describes new strategies to obtain equally good, if not better, solutions, in a much shorter time. First, we modify the role played by one of the resources in the dominance rules when generating new columns. This change eliminates many more partial paths and accelerates the search for a shortest path from the source node to the sink node in each subproblem. Secondly, we change the way that surplus days off, given to employees, are penalized. Instead of considering all occurrences across the entire body of staff and only penalizing if a threshold is exceeded, we propose a penalty for each occurrence directly in the subproblems. Third, we propose a new branching strategy. For the first 20 branching nodes, we fix columns that meet certain quality criteria. The criteria are initially very severe then soften whenever too few columns are fixed. For subsequent branching nodes, we alternate between fixing tasks to employees and fixing columns based only on flows in subproblems. Finally, we improve the calculation of the minimum number of days off that each employee may have in his/her schedule. In this way, the penalization of surplus days off is more realistic and we no longer pay for unavoidable days off. All these changes helped to decrease the amount of time needed by the software to provide solutions. We now have a first integer solution whose value is reduced by 71.72% and which was obtained in 1.33 days instead of 32.06. This represents a 95.85% reduction in time. The mentioned improvements have been implemented at AD OPT. The software's managers were satisfied both by the decreased computation time and the quality of the new solutions. Additional constraints, considering employees' preferences, may eventually be added, an option that was previously not possible given the difficulty of dealing with equity.