4 présentations

• 
  10h30 - 10h55

  Alternative fractional solutions in a column generation based diving heuristic

  • Théo Louesdon, prés., Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Andrea Lodi, CERC, Polytechnique Montréal, Montréal, Canada and Jacobs Technion-Cornell Institute, Cornell Tech and Technion - IIT, New York, USA

  This research explores optimization techniques for the Multi-Depot Electric Vehicle Scheduling Problem (MDEVSP), focusing on enhancing column generation with diving heuristics. Traditional heuristics solve the relaxed master problem to optimality through column generation, then fix the largest fractional value to one, and restart the entire column generation process with this additional constraint. This sequential fixing procedure can lead to suboptimal solutions due to early, irreversible decisions that propagate through subsequent iterations. We investigate whether generating alternative solutions during the column generation process using existing columns can improve solution quality. Two primary methodologies are examined: probing, which systematically evaluates promising candidates through linear programming, and specialized MIPs designed to identify variables with desirable characteristics. Experimental results demonstrate that our techniques on average improve the solution costs, though performance varies across instances.

• 
  10h55 - 11h20

  A Column Generation Heuristic for Multi-depot Electric Bus Scheduling

  • Yoann Sabatier Montanaro, prés., Polytechnique Montréal
  • Guy Desaulniers, GERAD
  • Quentin Cappart, Polytechnique Montréal
  • Thomas Jacquet, Polytechnique Montréal

  In public transit, the multi-depot electric vehicle scheduling problem (MDEVSP) involves assigning a fleet of electric buses to a set of timetabled trips while addressing constraints related to battery recharging.
  A common approach to solving this problem leverages column generation, wherein a master problem identifies a base solution, and subproblems generate additional schedules to enhance it. These subproblems are often modeled as shortest path problems on a graph, where nodes represent trips and potential recharging opportunities. Prior works have used time-space networks with dynamic selection of recharging opportunities.
  However, this network type introduces practical limitations, such as the inability to enforce ad-hoc constraints on trip sequences. Recently, Gerbaux et al. (2025) proposed a machine-learning-based method to accelerate the resolution of the subproblems by heuristically reducing their size.
  While effective, this approach raises concerns in industrial applications, including data privacy for customers and compliance with legal regulations. In this context, we propose a novel approach to model the subproblems within a column-generation-based algorithm for the MDEVSP. Our contributions are as follows: (1) A new graph formulation that preselects recharging opportunities, offering greater flexibility in trip assignment and enabling the integration of ad-hoc constraints; (2) A constructive meta-heuristic, based on a greedy randomized adaptive search procedure, to reduce the subproblem size without relying on machine learning or historical data; (3) Additional pruning rules to further reduce the subproblem size. Experimental results, conducted on hundreds of realistic instances derived from real bus lines in Montreal, show that our approach achieves comparable performance to the state-of-the-art method by Gerbaux et al. (2025), while avoiding the use of machine learning.

• 
  11h20 - 11h45

  Stochastic Electric Bus Depot Management: A Mixed Integer Programming Approach with Enhanced State-of-Charge Forecasting via Real-Time Tracking Signal

  • Khalilpourazari Soheyl, prés., Polytechnique Montreal
  • Romane Barra, Polytechnique Paris
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Jorge Mendoza, HEC Montréal

  We address a real-time stochastic electric bus depot management problem where arriving buses must be assigned to parallel FIFO lanes, charging schedules, and upcoming services under weather uncertainty. Our approach enhances a mixed-integer linear programming model with an adaptive tracking signal methodology that adjusts the expected state-of-charge (SOC) of arriving buses upon arrival across five weather scenarios (very cold, cold, normal, hot, and very hot). The system employs control parameters to monitor prediction bias by calculating relative errors between realized and expected SOCs upon arrival. When deviations are detected, the system dynamically adjusts forecasts for other incoming buses proportionally to the observed error magnitude. Computational experiments with up to 40 buses demonstrate improved charging schedule and service assignment stability despite weather variability, while maintaining solution times acceptable for real-time depot operations.

• 
  11h45 - 12h10

  Dual inequalities in column generation for the Multi-Depot Electric Vehicle Scheduling Problem

  • Antoine Demers-Bergeron, prés., GERAD
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  The rapid integration of electric buses into public transportation networks has introduced a range of new challenges, such as reduced autonomy and longer charging times. These factors complicate the Multi-Depot Electric Vehicle Scheduling Problem (MDEVSP), where trips must be assigned to buses from different depots while maintaining adequate battery levels. MDEVSP is typically solved using column generation, which often suffers from degeneracy, slowing down convergence. To address these challenges, we developed a machine learning-based approach to predict dual inequalities and incorporate them into the master problem. This technique aims to stabilize and accelerate the convergence of column generation, showing significant promise despite not yet yielding substantial performance improvements in our specific context. In my talk, I will outline our methodology, share the results obtained, and discuss why we believe this approach holds potential for speeding up column generation in future applications. Finally, I will present a simpler alternative method based on dual inequalities, which accelerates problem-solving by approximately 30% with minimal loss in solution quality.