Notre étude porte sur la planification des emplois du temps des Agents de Conduite (AdC) de trains de passagers. Dans le ferroviaire, ce problème de "crew scheduling" est souvent résolu en trois étapes successives : 1) génération de Journées de Service (JS) (plannings réglementaires d'un AdC sur une journée), 2) mise en place de tournées (enchaînement de deux JS, avec découché éventuel) et 3) mise en place de grilles horaires (plannings hebdomadaires respectant des contraintes de capacité d'effectifs). 

Nous traitons ici un problème qui intègre les étapes 1 et 2, et porte des contraintes a priori de capacité d'effectifs. Le principal objectif consiste à couvrir le maximum de trains, mais d'autres critères tels que le nombre de découchés sont aussi optimisés. 

Nous proposons une approche de type « Generate-And-Select » dans laquelle on génère dans un premier temps des emplois du temps (JS et tournées) réalisables du point de vue des contraintes, puis on en sélectionne un sous-ensemble répondant au mieux aux objectifs. La phase de génération est une énumération contrôlée par un moteur interne de règles. La phase de sélection est une heuristique lagrangienne combinée à des techniques de fixation de colonnes et de « pricing », adaptée de Caprara et al. Elle est basée sur un algorithme en 3 phases : algorithme de sous-gradient, heuristique et phase de fixations d'emplois du temps dans la solution. 

Des expérimentations ont été menées sur des données réelles issues de la production TER d'une région française sur une semaine-type. Nous obtenons des solutions de qualité (en comparaison d'un solveur commercial), cohérentes avec le métier et ne nécessitant pas le recours à un solveur externe de programmation mathématique.