Apprentissage d'inégalités duales pour la génération de colonnes appliquée au problème d'horaires d'autobus électriques avec dépôts multiples

Le transport en commun joue un rôle primordial dans notre société. En effet, il offre une solution de mobilité pratique, durable et économique. De plus, les autobus électriques, de plus en plus présents, permettent de réduire davantage les émissions de gaz à effet de serre et contribuent ainsi à la préservation de notre environnement. L’un des aspects cruciaux de la mise en place d’un système de transport en commun efficace est la planification des horaires d’autobus électrique provenant de différents dépôts. Considérant un ensemble de trajets d’autobus à couvrir et une flotte d’autobus électriques provenant de différents dépôts, la compagnie d’autobus doit générer des horaires efficaces afin d’assurer la couverture de l’ensemble des trajets tout en minimisant le coût d’opération. Dans la littérature, c’est ce qu’on appelle le problème d’horaires d’autobus électriques avec dépôts multiples (MDEVSP). Résoudre ce problème s’avère très complexe puisqu’il est NP-difficile. Une méthode de résolution fréquemment employée pour résoudre le MDEVSP est la génération de colonnes. Cet algorithme résout ce problème progressivement en insérant de nouveaux itinéraires à chaque itération. Cependant, certaines instances du MDEVSP souffrent de dégénérescence et la résolution prend énormément de temps.