Accélération d'une méthode d'agrégation dynamique de contraintes par apprentissage automatique pour le problème de construction d'horaires de conducteurs d'autobus

Les compagnies de transport en commun ont la difficile tâche de créer des quarts de travail pour l'ensemble de leurs conducteurs d'autobus. Chaque segment de voyage doit se faire attribuer un conducteur. Ce problème de construction d'horaire de conducteurs d'autobus (DSP) est d'une taille importante tant par rapport à la quantité de bus que par rapport au nombre de lignes faisant partie du problème. C'est aussi un problème engendrant de grands coûts économiques associés à la rémunération des conducteurs. Dans ce mémoire, on présente une modification de la méthode actuelle de résolution de DSP qui permettrait d'accélérer la résolution de ce problème tout en arrivant à une solution optimale. Cette modification repose sur la méthode d'agrégation dynamique de contraintes (DCA). Nous présentons une nouvelle méthode qui utilise l'apprentissage automatique afin de créer les agrégations initiales à fournir à DCA. Habituellement, dans le cadre de résolution de DSP, les agrégations initiales sont créées en regroupant tous les segments faisant partie d'un même horaire de bus sous une seule agrégation dans l'ordre auquel le bus les parcourt. Ces agrégations permettent au solveur de traiter ces voyages comme en étant un seul au point de vue des contraintes de partitionnement, ce qui réduit le nombre de contraintes et ainsi accélère la résolution. Ces agrégations basées sur les sorties de bus accélèrent fortement la résolution du problème. Elles ne sont donc pas optimales, car il arrive souvent, dans la solution optimale, que les segments faisant partie d'une même sortie de bus ne soient pas tous couverts par le même conducteur. La modification présentée dans ce mémoire consiste à intégrer un modèle d'apprentissage automatique dans le processus de composition des agrégations initiales de DCA, ce qui permettrait de générer des agrégations qui ressembleraient mieux aux quarts de travail de la solution de la relaxation linéaire au nœud 0 du branch and price et ainsi nécessiter moins de désagrégations afin d'atteindre la solution optimale. Cette approche se cadre dans le nouveau paradigme en optimisation combinatoire qui consiste à utiliser les outils de l'intelligence artificielle en concert avec les outils utilisés dans le domaine de l'optimisation. Le rôle de l'algorithme d'apprentissage automatique est de prédire, au préalable de la résolution, les endroits où on devrait avoir des échanges de conducteurs dans la solution de la relaxation linéaire du nœud 0 du branch and price. Un échange de conducteurs se produit lorsqu'un conducteur quitte un autobus et est remplacé par un nouveau conducteur à un point de relève. Les agrégations de départ basées sur les sorties de bus sont brisées aux en-droits où un échange de conducteurs a été prédit. Ainsi, des agrégations nécessitant moins de désagrégation afin d'atteindre la solution optimale sont créées. Cette tâche de prédiction est formulée comme étant une tâche de classification binaire. Les données utilisées pour l'entraînement des modèles d'apprentissage automatique sont obtenues à partir de problèmes générés par un nouveau générateur permettant de créer des problèmes inspirés de données réelles. La position des arrêts et les fréquences relatives entre les lignes sont similaires à celle de la Société de Transport de Montréal. Deux ensembles de 12 pro-blèmes ont été créés ayant en moyenne 893 et 1075 voyages. Nous comparons les performances d'un modèle de forêt d'arbres décisionnels, d'un réseau de neurones convolutifs et d'un ré-seau de neurones graphiques. Nous montrons que ces nouvelles agrégations créées à l'aide de l'apprentissage automatique permettent d'accélérer la résolution des DSP d'en moyenne 20.1% à 32,6% comparativement aux agrégations créées à partir des sorties de bus.