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.

Abstract

The MDEVSP constitutes a critical optimization challenge for public transportation systems transitioning to electric fleets. This problem involves determining the best scheduling of electric vehicles from multiple depots, taking into account their specific constraints such as limited battery autonomy and charging needs, in order to satisfy a set of tasks (bus trips) while minimizing operational costs. This thesis focuses on enhancing column generation-based diving heuristics for solving the MDEVSP efficiently. Traditional approaches solve the master problem to optimality through column generation, fix the variable with the largest fractional value to one, then restart the entire process with this additional constraint. While computationally tractable, this sequential fixing procedure often leads to suboptimal solutions due to early, irreversible decisions that propagate through subsequent iterations. This research investigates whether exploring alternative optimal solutions of the master prob-lem, using the existing column pool, can improve final solution quality. We propose and analyze two methodological approaches: a probing technique that systematically evaluates promising candidates through linear programming, and specialized mixed-integer programs designed to identify variables with characteristics potentially leading to better overall solu-tions. The proposed methods maintain the heuristic nature of the resolution while attempting to make more informed branching decisions. Computational experiments were conducted on multiple instance types with varying com-plexities: single-depot instances with approximately 700 tasks, two-depot instances with approximately 750 tasks, and larger two-depot instances with approximately 1300 tasks. Ini-tial testing used 10 instances of each type, with promising techniques subsequently evaluated on larger scales. Results demonstrate modest improvements of average optimality gaps ranging, in the best cases, from 0.25% to 1.0%, with maximum improvements generally exceeding 2.5%. However, certain methods exhibited deteriorations in worst-case scenarios exceeding 2%, indicating the difficulty of developing systematically beneficial variable selection strategies. Contrary to initial hypotheses, a limited correlation was found between a variable’s proximity to 1 and its impact on solution quality when fixed. Our experiments further demonstrate that parallel execution of multiple methods enables improvement in the average optimality gap while reducing, in several cases, the maximum gap by up to 40%. This combinatorial approach presents a significant advantage for the overall robustness of the resolution process. Our research contributes practical enhancements applicable to column generation approaches employing diving heuristics, particularly for electric vehicle scheduling problems. The find-ings underline the critical impact of early branching decisions, as these fundamentally con-strain the solution space for subsequent iterations, highlighting an intrinsic challenge in diving heuristics that warrants further investigation.