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

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.