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.