Détermination de la taille des effectifs et affectation des séquences de repos dans les horaires d'employés de compagnies de transport public

Public transit companies build schedules for their employees in multiple steps. One of those steps is the construction of the sequence of rest days. In an environment where multiple collective agreements govern multiple employee groups, this step is very important. In fact, it is at this step that the exact number of employees required for each group is determined. The objective of this master's thesis is to model the problems of constructing rest day sequences and of determining the size of the workforce in a context where there are multiple employee groups. A few models will be proposed and compared in experimentations on data sets. Those data sets represent multiple public transit companies around the world. In this master's thesis, two models will be presented. The first one is 0-1 linear mathematical model. The second mathematical model is a composition of multiple flows. Both models will lead to finding an optimal solution for problems with a size exceeding 450 employees. In fact, we will show that with the second model, complexity is not dependent of the number of employees nor the number of tasks.

Résumé

Les compagnies de transport public construisent les horaires de leurs employés en plusieurs étapes. Une de ces étapes est la construction des séquences de repos. Dans un environnement où plusieurs conventions collectives régissent différents groupes d'employés, cette étape est très importante. En effet, c'est à cette étape que le nombre exact d'employés requis pour chaque groupe est déterminé. L'objectif de ce mémoire est de modéliser les problèmes de construction des séquences de repos et de détermination de la taille des effectifs dans des horaires cycliques dans un contexte où il y a plusieurs groupes d'employés. Quelques modélisations seront proposées et seront comparées à l'aide d'expérimentations sur des jeux de données. Ces jeux de données réelles représentent différentes compagnies de transport public dans le monde. Dans le cadre de ce mémoire, deux modélisations seront présentées. La première modélisation est une modélisation 0-1 linéaire. La deuxième modélisation est une composition de plusieurs flots. Les deux modélisations permettront de trouver une solution optimale des problèmes dont la taille dépasse 450 employés. En fait, nous montrons qu'avec la deuxième modélisation, la complexité du problème ne dépend pas du nombre d'employés ni du nombre de tâches.