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.