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.

Abstract

Transit companies have the difficult task of creating shifts for all their bus drivers. Each trip segment must be assigned a driver. This driver scheduling problem (DSP) is large in terms of both the number of buses and the number of routes involved. It is also a problem with large economic costs associated with the salaries of the different drivers. In this paper, we present a modification to the current solution method of the DSP that would speed up the resolution of this problem while arriving at an optimal solution. This modification is based on the dynamic constraint aggregation (DCA) method. We present a new method that uses machine learning to create the initial aggregations to provide to DCA. Typically, for solving DSP, initial aggregations are created by grouping all segments that are part of the same bus route under a single aggregation in the order in which the bus traverses them. These aggregations allow the solver to treat these segments as one from the perspective of the partitioning constraints, which reduces the number of constraints and thus speeds up the resolution. These aggregations based on bus routes strongly accelerate the solution of the problem. However, they are not optimal, because in the optimal solution, it often happens that the segments belonging to the same bus route are not all covered by the same driver. The modification presented in this dissertation consists in integrating a machine learning model in the process of composing the initial aggregations of DCA, which would allow gener-ating aggregations that would better resemble the drivers shifts of the solution of the linear relaxation at node 0 of the branch-and-bound algorithm and thus require fewer disaggregations in order to reach the optimal solution. This approach is in line with the new paradigm in combinatorial optimization, which consists in using the tools of artificial intelligence in concert with the tools used in the optimization domain. The role of the machine learning algorithm is to predict, prior to the solution, the places where we should have an exchange of drivers in the solution of the linear relaxation at node 0 of the branch-and-price algorithm. An exchange of drivers occurs when a driver leaves a bus and is replaced by a new driver at a relief point. Aggregations based on bus routes are broken at locations where an exchange of drivers has been predicted. Thus, aggregations requiring less disaggregation in order to reach the optimal solution are created. This prediction task is formulated as a binary classification task. The data used to train the machine learning models are obtained from problems generated by a new generator to create problems inspired by real data. The location of the stops and the relative frequencies between the lines are similar to that of the Société de Transport de Montréal. Two sets of 12 problems were created with an average of 893 and 1075 trips. We compare the performance of a random forest classifier, a convolutional neural network and a graphical neural network. We show that these new aggregations created using machine learning speed up the DSP resolution by an average of 20.1% to 32.6% compared to aggregations created from bus routes.