Optimisation de roulements de chauffeurs d'autobus

Le problème de roulements de chauffeurs d'autobus vise à déterminer les horaires de travail des chauffeurs d'autobus sur un horizon donné. Il s'agit d'un problème où des séquences de jours de repos et de journées de travail sont construites. Les journées de travail sont générées lors de la résolution du problème de construction de journées de travail. Ce problème a pour objectif de générer des journées de travail anonymes afin d'assurer, à un coût minimum, la couverture complète des horaires d'autobus. Plusieurs règles doivent être respectées lors de la résolution, entre autres, l'amplitude maximale ou minimale d'une journée de travail, le temps maximal ou minimal de travail, etc. Lorsque les journées de travail sont déterminées, elles sont affectées aux différents chauffeurs disponibles et les roulements des chauffeurs sont construits à cette étape. Les journées de travail sont affectées en respectant un ensemble de règles dérivées des conventions collectives, et chaque journée de travail est effectuée par un chauffeur durant un jour de la semaine. Dans notre contexte, les roulements de chauffeurs d'autobus sont cycliques et définis sur une semaine pour un certain horizon de planification. Ainsi les journées de travail peuvent varier d'un jour à l'autre mais se répètent d'une semaine à une autre. Le problème de roulements avec jours de repos fixés vise à affecter les journées de travail aux différents chauffeurs dans les jours de travail (c'est-à-dire, les jours qui ne sont pas des jours de repos). Nous proposons, d'abord, une nouvelle formulation forte en nombres entiers du problème de roulements avec repos fixés. Les règles d'affectation des journées de travail sont diverses et compliquées, surtout qu'elles impliquent des contraintes de repos de nuit entre deux journées de travail et des contraintes qui s'étendent sur plusieurs jours et parfois sur plusieurs semaines. La fonction objectif vise à équilibrer le plus possible la charge de travail entre tous les chauffeurs. Ceci a été traduit par la minimisation des déviations positives par rapport à la moyenne des charges de travail totale par semaine de toutes les journées de travail. Différentes modélisations des contraintes de repos de nuit ont été proposées, ainsi qu'une deuxième formulation de la fonction objectif, mais qui vise aussi à équilibrer la charge de travail entre les chauffeurs d'autobus. Nous avons montré que la nouvelle formulation permet de reserrer l'espace de recherche lors du branchement, ce qui permet d'avoir des solutions entières plus rapidement. Ensuite, une approche est proposée pour résoudre le problème de roulements intégré de construction de jours de repos et d'affectation de journées de travail. Le problème est modélisé comme un programme linéaire mixte en nombres entiers. Étant donné que le problème ne contient pas de règles de quarts de travail ni de règles souples (des préférences par exemple), le problème présente beaucoup de symétrie. Le modèle s'est avéré très difficile à résoudre à l'optimalité avec le solveur commercial CPLEX malgré l'ajustement très poussé des paramètres et l'utilisation des méthodes avancées de programmation en nombres entiers (fixation de variables, branchement priorisé, ...). Sur la base de ce modèle, nous avons introduit une matheuristique à deux étapes qui permet de trouver des solutions de très bonne qualité. En utilisant une telle solution comme donnée d'entrée dans un solveur commercial, le modèle intégré peut être résolu beaucoup plus rapidement. Nos expériences de calcul testées sur des instances réelles de grande taille ont montré l'efficacité de la matheuristique. Des solutions optimales ont été obtenues dans des temps de calcul relativement courts (3.5 heures pour le cas impliquant jusqu'à 333 chauffeurs). En outre, en fournissant ces solutions comme solutions initiales au solveur CPLEX, de grandes accélérations (jusqu'à 99%) ont été obtenues pour résoudre le problème intégré avec une optimalité prouvée. L'article intitulé "Integrated and sequential solution methods for the cyclic bus driver rostering problem" traitant cet objectif a été publié dans la revue "Journal of the Operational Research Society" Finalement, nous avons intégré des règles relatives aux préférences des chauffeurs dans le modèle de roulements. Le nouveau modèle vise à affecter les journées de travail aux différents chauffeurs sur un horizon prédéfini, tout en respectant les règles strictes d'affectation, en équilibrant la charge de travail entre les chauffeurs et en minimisant le plus possible les violations des règles souples (les préférences). Deux nouvelles matheuristiques ont été proposées. La première limite l'espace de recherche en pré-assignant les journées de travail aux roulements avec des jours de repos fixés. La deuxième matheuristique utilise un problème de partitionnement d'ensemble pour décomposer les roulements de grande taille en sous-roulements de tailles petites à moyennes. Dans une série d'expériences de calcul menées sur des instances réelles, nous montrons que ces matheuristiques peuvent être utilisées pour produire des solutions de bonne qualité pour des grandes instances (333 chauffeurs et 1509 journées de travail) dans des temps de calcul relativement courts. L'article intitulé "Preference-based bus driver rostering problem with fixed days off" traitant cet objectif a été soumis à la revue "Public Transport"