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.