Alternative Fractional Solutions in a Column-Generation-Based Diving Heuristic Applied to the Multi-Depot Electric Vehicle Scheduling Problem

Le MDEVSP constitue un défi d’optimisation critique pour les systèmes de transport public en transition vers des flottes électriques. Ce problème consiste à déterminer le meilleur ordonnancement des véhicules électriques provenant de plusieurs dépôts, en tenant compte de leurs contraintes spécifiques comme l’autonomie limitée des batteries et les besoins de recharge, afin de satisfaire un ensemble de tâches tout en minimisant les coûts opérationnels. Cette thèse se concentre sur l’amélioration des heuristiques de plongée basées sur la génération de colonnes pour résoudre efficacement le MDEVSP. Les approches traditionnelles résolvent le problème maître jusqu’à l’optimalité par génération de colonnes, fixent à 1 la variable ayant la plus grande valeur fractionnaire, puis recommencent l’ensemble du processus avec cette contrainte supplémentaire. Bien que calculatoirement abordable, cette procédure de fixation séquentielle conduit souvent à des solutions sous-optimales en raison de décisions précoces et irréversibles qui se propagent lors des itérations suivantes. Cette recherche examine si l’exploration de solutions optimales alternatives du problème maître, en utilisant le groupe de colonnes existant, peut améliorer la qualité finale des solutions. Nous proposons et analysons deux approches méthodologiques : une technique de sondage qui évalue individuellement les candidats prometteurs par programmation linéaire, et des programmes en nombres entiers conçus pour identifier les variables dont les caractéristiques pourraient conduire à de meilleures solutions globales. Les méthodes proposées conservent la nature heuristique de la résolution tout en tentant de prendre des décisions de branchement plus réfléchies. Des expériences computationnelles ont été menées sur plusieurs types d’instances de complexités variées : des instances à dépôt unique avec environ 700 tâches, des instances à deux dépôts avec environ 800 tâches, et des instances à deux dépôts plus importantes avec environ 1300 tâches. Les tests initiaux ont utilisé 10 instances de chaque type, les techniques prometteuses étant ensuite évaluées à plus grande échelle. Les résultats démontrent des améliorations d’écart d’optimalité moyennes modestes allant dans les meilleurs cas de 0,25% à 1,0%, avec des améliorations maximales généralement supérieures à 2,5%. Cependant, certaines méthodes ont présenté des détériorations dans le pire des cas dépassant 2%, ce qui indique la difficulté de développer des stratégies de sélection de variables efficaces. Contrairement aux hypothèses initiales, une corrélation limitée a été trouvée entre la proximité d’une variable à 1 et son impact sur la qualité de la solution lorsqu’elle est fixée. Nos expérimentations montrent également que l’exécution parallèle de plusieurs méthodes permet d’améliorer l’écart d’optimalité moyen tout en réduisant, dans plusieurs cas, l’écart maximal jusqu’à 40%. Cette approche combinatoire présente un avantage significatif pour la robustesse globale du processus de résolution. Notre recherche apporte des améliorations pratiques applicables aux approches par génération de colonnes utilisant des heuristiques de plongée, particulièrement pour les problèmes de planification de véhicules électriques. Les résultats soulignent l’impact critique des décisions de branchement précoces, car elles contraignent l’espace de solution pour les itérations suivantes, mettant en évidence un défi des heuristiques de plongée qui mérite d’être approfondi.