Stabilisation de la génération de colonnes par chaînes d'inégalités duales : Application au problème d'horaires d'autobus électriques avec dépôts multiples

L’intégration rapide des autobus électriques dans les réseaux de transport en commun introduit de nouveaux défis, tels qu’une autonomie limitée et des temps de recharge prolongés. Ces contraintes compliquent le problème d’horaires d’autobus électriques avec dépôts multiples (MDEVSP), qui consiste à assigner un ensemble de trajets à des autobus provenant de différents dépôts tout en assurant une gestion adéquate du niveau de batterie. Le MDEVSP est souvent résolu à l’aide de la génération de colonnes, une méthode qui souffre toutefois de dégénérescence, i.e., que la valeur de la solution courante n’évolue pas nécessairement à chaque itération. Cette dégénérescence provient du fait qu’il y a plusieurs solutions duales associées à la même solution primale. Ainsi, une façon de limiter la dégénérescence consiste à réduire l’espace dual en ajoutant des inégalités duales au modèle. Dans ce mémoire, nous poursuivons les travaux de Popovic (2023) qui a développé une approche basée sur l’apprentissage machine pour prédire des chaînes d’inégalités duales et les intégrer au problème maître de la génération de colonnes afin de stabiliser les variables duales, réduire la dégénérescence et accélérer la convergence. Nous poussons plus loin ces idées qui ont été testées sur la relaxation linéaire du problème et nous les appliquons sur la résolution complète en appliquant une stratégie de branchement heuristique adaptée. Bien que cette méthode montre un potentiel intéressant, nos résultats expérimentaux révèlent des améliorations limitées dans les cas testés. Par la suite, nous menons une analyse détaillée des conditions nécessaires à l’efficacité de ces inégalités et identifions les principales limites de l’approche par apprentissage machine. À partir de ces constats, nous terminons en proposant une méthode alternative consistant à construire une longue chaîne d’inégalités duales à partir de la solution duale de la première relaxation linéaire. Cette stratégie permet d’obtenir jusqu’à 30% d’accélération sur l’ensemble des instances testées, tout en offrant une solution plus fiable et plus facile à implémenter.

Abstract

The rapid integration of electric buses into public transportation networks introduces new challenges, such as limited range and extended charging times. These constraints complicate the Multi-Depot Electric Vehicle Scheduling Problem (MDEVSP), which requires assigning trips to buses from various depots while managing battery levels. The MDEVSP is often solved using column generation, but this technique suffers from degeneracy, i.e. that the current solution does not necessarily evolve at every iteration. This degeneracy comes from the fact that there are many dual solutions associated with the same primal solution. Therefore, one way to limit degeneracy consists in reducing the dual space by adding dual inequalities to the model. In this thesis, we build upon the work of Popovic (2023) who developed a machine-learningbased approach to predict dual inequalities and incorporate them into the master problem of the column generation to stabilize dual variables, reduce degeneracy, and accelerate the convergence of the algorithm. We take these ideas that were tested on the linear relaxation of the problem, and we apply them on the complete resolution by using an adapted heuristic branching strategy. Although the method shows theoretical potential, our results indicate limited performance improvements in the tested scenarios. We conduct a detailed analysis of the structural conditions required for these dual inequalities to be effective and identify key limitations of the machine-learning-based approach. From this insight, we propose an alternative method that constructs a long chain of dual inequalities from the dual solution of the first linear relaxation. This strategy achieves up to 30% acceleration across all tested instances and offers a more reliable and easier-to-implement solution.