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

Public transit plays a vital role in our society. Indeed, it offers a practical, sustainable and economical mobility solution. In addition, electric buses, which are becoming more and more popular, further reduce greenhouse gas emissions and thus contribute to the preservation of our environment. One of the crucial aspects of building an efficient transit system is scheduling electric buses from multiple depots. Considering a set of bus routes to be covered and a fleet of electric buses from different depots, the bus company must generate efficient schedules in order to ensure coverage of all routes while minimizing the cost of operation. In the literature, this is known as the Multiple Depot Electric Vehicle Scheduling Problem (MDEVSP). Solving this problem turns out to be very complex since it is NP-hard. Column generation is a method commonly used to solve the MDEVSP. This algorithm solves this problem gradually by inserting new routes at each iteration. However, some instances of the MDEVSP suffer from degeneracy and the resolution takes a very long time.

Résumé

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.