Génération de colonnes et sélection d'arcs de recharge pour un problème d'horaires d'autobus électriques

Dans le cadre de la transition énergétique et de la réduction des émissions de gaz à effet de serre, l’adoption des autobus électriques se généralise, apparaissant comme une solution clé pour rendre les transports en commun durables. Cependant, cette transition soulève de nouveaux défis en termes d’optimisation, notamment en raison des contraintes liées à la recharge des batteries. L’optimisation associée consiste à assigner un ensemble de trajets planifiés à une flotte de véhicules, problème connu sous le nom de problème d’horaires de véhicule (vehicle scheduling problem). Lorsqu’il s’agit de gérer plusieurs dépôts, le problème se complique et devient le problème d’horaires de véhicules multi-dépôts (multi depot vehicle scheduling problem). Dans le cas des autobus électriques, le problème se transforme en problème d’horaires de véhicules électriques multi-dépôts (multi depot electric vehicle scheduling problem), où il devient nécessaire de prendre en compte non seulement les itinéraires, mais également les temps et lieux de recharge. Une méthode largement reconnue pour résoudre ces problèmes complexes est la génération de colonnes, qui divise le problème en deux étapes : un problème maître, qui génère une solution à partir d’un sous-ensemble d’horaires possibles, et des sous-problèmes, qui ajoutent des colonnes (horaires de bus) pour améliorer cette solution. Ces sous-problèmes sont souvent modélisés sous forme de problèmes de plus courts chemins sur un graphe, où les noeuds représentent notamment les trajets à effectuer. Dans les approches précédentes, les graphes utilisaient un réseau espace-temps avec une sélection dynamique des opportunités de recharge lors de la résolution du sous-problème. Cependant, cette approche ne permet pas d’imposer des contraintes ad-hoc sur les transitions entre trajets, ce qui est essentiel pour les sociétés de transport en commun et, donc, pour les entreprises spécialisées en logiciels d’optimisation pour le transport public, telles que GIRO Inc. Dans ce travail, nous proposons une nouvelle formulation de graphe qui offre la possibilité d’imposer des contraintes supplémentaires sur les arcs reliant les trajets, répondant ainsi aux besoins des opérateurs. De plus, afin de réduire la taille du graphe et d’accélérer les calculs, nous avons intégré des stratégies avancées de sélection d’arcs. Ces stratégies incluent un précalcul des opportunités de recharge les plus pertinentes et une adaptation de l’algorithme Greedy Randomized Adaptive Search Procedure proposé par Jacquet et al. [1], spécifiquement modifié pour fonctionner dans le cadre de notre graphe reformulé. Nos résultats expérimentaux, obtenus sur des instances réalistes dérivées de données de lignes de bus montréalaises, montrent que notre approche atteint des performances comparables à celles des méthodes de l’état de l’art, tout en offrant une flexibilité supplémentaire pour respecter des contraintes opérationnelles spécifiques. Par ailleurs, nous proposons une méthodologie permettant aux utilisateurs d’ajuster facilement l’équilibre entre la réduction du temps de calcul et le surcoût en fonction de leurs besoins, offrant ainsi une solution adaptable et robuste dans des contextes variés.

Abstract

In the context of the energy transition and the reduction of greenhouse gas emissions, the adoption of electric buses is gaining momentum, emerging as a key solution to make public transportation sustainable. However, this transition introduces new optimization challenges, particularly due to constraints related to battery recharging. The optimization problem involves assigning a set of timetabled trips to a fleet of vehicles, a problem known as the Vehicle Scheduling Problem. When multiple depots are involved, the problem becomes more complex and is referred to as the Multi Depot Vehicle Scheduling Problem. In the case of electric buses, the problem evolves into the Multi Depot Electric Vehicle Scheduling Problem, requiring not only the planning of routes but also the scheduling of recharging times and locations. A widely recognized method for addressing such complex problems is Column Generation, which divides the problem into two stages: a master problem that generates a solution based on a subset of bus schedules and subproblems that add columns (bus schedules) to improve this solution. These subproblems are often modeled as shortest path problems on a graph, where nodes represent trips and potential recharging opportunities. In previous approaches, these graphs relied on a time-space network with dynamic selection of recharging opportunities during the subproblem resolution. However, this approach does not allow for the enforcement of ad-hoc constraints on transitions between trips, which is essential for public transit companies and, therefore, for software optimization firms specializing in public transportation, such as GIRO Inc. In this work, we propose a novel graph formulation that pre-selects recharging opportunities before solving the subproblems. This reformulation enables the enforcement of additional constraints on arcs connecting trips, meeting the specific needs of operators. Additionally, to reduce the graph size and accelerate computation, we have implemented advanced arc selection strategies. These include a pre-computation of the most relevant recharging opportunities and an adaptation of the Greedy Randomized Adaptive Search Procedure proposed by Jacquet et al. [1], specifically tailored to operate within our reformulated graph. Our experimental results, conducted on realistic instances derived from Montreal’s bus network data, demonstrate that our approach achieves performance comparable to state-of-theart methods while providing additional flexibility to enforce operational constraints. Moreover, we propose a methodology that allows users to easily balance computation time reduction and solution cost according to their needs, offering a robust and adaptable solution for diverse operational contexts.