Résolution heuristique par génération de colonnes et apprentissage automatique du problème d'horaires d'autobus électriques

De plus en plus d’autobus électriques sont utilisés dans les transports en commun pour les bénéfices environnementaux qu’ils apportent par rapport à un autobus classique. Cependant, utiliser des autobus électriques demande de repenser le processus de planification et d’opération des autobus. En particulier le problème d’horaires de véhicules (Vehicle Scheduling Problem) (VSP) et sa résolution doivent être revus. En effet, ce problème qui vise à affecter les autobus aux différents trajets de bus est complexe et crucial pour minimiser les coûts d’opération liés au nombre d’autobus utilisés et à la distance qu’ils parcourent. Dans le cas de véhicules électriques, la minimisation de la distance est essentielle et de nouvelles contraintes liées à l’autonomie et à la recharge des véhicules doivent être considérées. De nombreux travaux ont été menés sur le problème d’horaires de véhicules électriques (Electric Vehicle Scheduling Problem) (EVSP). Différentes formulations et méthodes de résolution ont été proposées. Le problème résolu dans ce travail est le problème d’horaires de véhicules électriques multi-dépôt (Multi Depot Electric Vehicle Scheduling Problem) (MDEVSP) avec recharge partielle et linéaire par morceaux, un seul type de véhicules électriques et un seul type de chargeur. La modélisation choisie discrétise les temps de recharge et permet de tenir compte du nombre de chargeurs disponibles aux différentes stations de recharge. Ce modèle se veut proche de la réalité et permet ainsi d’être utilisée en pratique. À notre connaissance, peu de méthodes de résolution ont été proposées pour résoudre cette variante du MDEVSP. Une des méthodes habituellement utilisée et très performante pour résoudre le problème d’horaires de véhicules multi-dépôt (Multi Depot Vehicle Scheduling Problem) (MDVSP) (qui est un problème NP-difficile) est la génération de colonnes (GC) qui se base à la fois sur un modèle de partitionnement d’ensemble et sur un modèle de réseau dans lequel on cherche des plus courts chemins. Cette méthode, même en utilisant des accélérations heuristiques, ne permet pas de résoudre assez rapidement le EVSP. On propose donc une nouvelle méthode pour accélérer la GC qui s’appuie sur une réduction heuristique du nombre de variables dans le problème. La réduction est faite par élimination d’arcs dans le graphe qui modélise le problème. Pour cela, on combine deux méthodes : un algorithme glouton et de l’apprentissage supervisé basé sur un réseau de neurones pour graphe (Graph Neural Network) (GNN). Le GNN est une architecture neuronale qui est entrainée sur des instances résolues par GC heuristique. La méthode proposée est validée sur des instances comprenant environ 700 trajets et 2500 trajets générées aléatoirement à partir de données de la ville de Montréal. Les tests montrent que la combinaison des deux méthodes apporte un gain significatif par rapport à l’utilisation séparée des méthodes. En divisant le nombre d’arcs dans la modélisation par 5, elle permet de réduire, pour les plus petites instances, entre 65% et 87% le temps de résolution avec un écart du coût de la solution à la valeur optimale d’au plus 3,7%. Avec une division par 10 du nombre d’arcs, la méthode permet aussi un gain de temps de 49% avec un écart de 4,2% sur les grandes instances grâce à un apprentissage par transfert du GNN. Malheureusement, les tests font apparaitre que les modèles appris généralisent mal à des instances ayant une distribution différente de celles utilisées lors de l’entrainement.

Abstract

More and more electric buses are used in public transport, thanks to the environmental benefits they bring compared to traditional buses. However, using electric buses requires rethinking the bus operational planning process. In particular, the Vehicle Scheduling Problem (VSP) and its resolution must be adapted. Indeed, the resolution of this problem, which consists in assigning vehicles to different bus trips, is major to minimize the operating costs related to the fleet size and the travelling distance. In the case of electric vehicles, distance minimization is critical and new constraints related to vehicle autonomy and charging process must be considered. Many works have studied the Electric Vehicle Scheduling Problem (EVSP). Different formulations and approaches have been proposed. The problem solved in this work is the Multi Depot Electric Vehicle Scheduling Problem (MDEVSP) with partial and piecewise linear charging, only one type of electric vehicles and one type of chargers. The model discretizes the charging periods and takes into account the number of chargers available at the different charging stations. It is designed to be realistic and, therefore, to be used in practice. To the best of our knowledge, only few solution methods have been proposed to solve this variant of the MDEVSP. One of the approaches usually very efficient to solve the Multi Depot Vehicle Scheduling Problem (MDVSP) is column generation (GC) which is based on a set partitioning model and a network model to generate resource-constraint shortest paths. This approach does not solve the EVSP fast enough, even with heuristic speed-up strategies. Consequently, we propose a new strategy to accelerate the GC based on a heuristic reduction of the number of variables in the problem. The reduction is done by eliminating arcs in the graph that models the problem. For this, we combine two techniques: a greedy algorithm and supervised learning based on a graph neural network (GNN). The GNN is a neural architecture that is trained on instances solved by GC. The proposed approach is validated on instances involving around 700 and 2500 randomly generated trips from Montreal real-life data. The experiments show that the combination of the two techniques provides a significant gain compared to the separate use of the techniques. For the smallest instances, it allows reducing between 65% and 87% of the computational time, with a gap to the optimal value less than 3.7%. For the large instances, the solution method also provides a time saving of 49% with a gap of 4,2% thanks to a transfer learning approach. The number of arcs is divided by 5 and 10 for the small and large instances respectively. Unfortunately, the learned GNN generalizes poorly to instances with a different distribution than the one used during training.