4 présentations

• 
  10h30 - 10h55

  Crew pairing problem with regularity

  • Mohamed Faouzi Benammour, prés., Gerad
  • Frédéric Quesnel, GERAD
  • Francois Soumis, GERAD et Polytechnique

  The Crew Pairing Problem seeks to find a set of feasible crew rotations at minimum cost that cover all flights. However, some airlines are willing to sacrifice a portion of their savings to achieve regularity. This is because regular solutions are much easier to implement and manage, including booking the same hotels, rooms, and limousines for the crew. It also enhances employee satisfaction.
  Traditional approaches have their limitations. The three-phase method can be effective in achieving regular rotations for regular flight schedules, but it performs less well in terms of costs and rotation regularity for irregular flights. Conversely, the rolling horizon approach, while better at minimizing costs, often leads to irregular rotations. Our goal is to produce more regular rotations while keeping costs as close to the minimum as possible.
  Our alternative is a two-step method. The first step is the Aggregated Daily Problem, a modified version of the daily problem covering each flight the number of times they appear during the month. An advanced column generation strategy will be developed, accompanied by an efficient branching methodology. Step 2, the Regular Monthly Problem, which assigns bonuses for using pre-selected patterns recommended in Step 1 by the Aggregated Daily Problem. A feedback loop between the two steps allows for refinement and convergence towards optimality by integrating necessary adjustments and feedback.

• 
  10h55 - 11h20

  Crew split problem: team creation for the cabin crew pairing problem

  • Mohand Ryad Chelbani, prés., Gerad
  • Francois Soumis, GERAD et Polytechnique
  • Frédéric Quesnel, Polytechnique Montréal

  It is usually beneficial for airlines that cabin crews travel in teams for entire pairings (sequence of flights, connections, and rest, forming one or several days of work). In addition to improving morale and team efficiency, travelling in teams increases the robustness of the schedule. However, different flights may have different crew requirements, so it is not always possible to have a whole team work on two consecutive flights. In those cases, it may be beneficial to use a core team to cover most of the requirements and use complementary crews to cover the missing assignments. Finding the optimal way to form teams has been identified as an issue but has never been tackled.
  In this talk, we formulate the crew split problem, whose role is to determine the core team composition of each flight as well as the complementary crews that will join it. It is a multi-objective optimization problem that, among others, maximizes the size of each core team, minimizes the estimated connexion times, and minimizes the estimated deadhead costs. In addition, our model allows for downranking, which is the possibility of a higher-ranked crew to work a lower-ranked position. We show the benefits of using the crew split problem on a large real-world instance.

• 
  11h20 - 11h45

  A Branch-and-Price Algorithm for Multiple Depot Bus scheduling Problem in Public Transit Systems

  • Nadia Rasouli, prés., Gerad
  • Francois Soumis, GERAD et Polytechnique
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Mohammed Saddoune, Faculté des sciences et techniques Mohammedia

  Bus scheduling problem is one of the most important scheduling problems in public transit since it guarantees minimum cost running for the transportation companies. A bus schedule defines the number of trips made by a bus in a workday, from the time it leaves the depot until it returns to the depot. Our study focuses on a large-scale multiple-depot bus scheduling problem in the public bus transportation industry with homogeneous fleets of vehicles. Using a timetable of trips, this research targets finding feasible bus schedules that cover each trip exactly once. With this approach, we use a set partitioning model with side constraints, and a connection-based network. Our solution approach is based on column generation (CG) embedded in a branch and bound method. As part of CG, we use a shortest path subproblem with resource constraints, which is then solved with a labeling algorithm considering dominance rules. To speed up the solution process, we use some heuristics branching including variable fixing and inter-task fixing. Despite the complexity of our model compared to most of those in literature reviews, computational experiments show that our approach is fast.

• 
  11h45 - 12h10

  Branch-and-Price Algorithm for Electric Bus Scheduling Optimization and Fast Charging Infrastructure Location Planning

  • Kayhan Alamatsaz, prés., Concordia University
  • Frédéric Quesnel, Polytechnique Montréal
  • Ursula Eicker, Concordia University

  Transit authorities are increasingly switching from traditional buses to electric buses to address air quality concerns, greenhouse gas emissions, and energy needs. Although there are many optimization models for scheduling traditional buses, these models are not suitable for electric buses due to their shorter range and longer charging times. This has led to new research into optimal locations for electric bus charging stations. Our study aims to efficiently schedule electric buses and plan the locations of fast-charging stations to minimize total costs. These costs include bus scheduling, electricity, bus ownership, and the installation of fast-chargers. We developed two models: a Mixed-Integer Linear Programming (MILP) model for an arc-based approach and an Integer Linear Programming (ILP) model for a path-based approach. We solved these models using the Cplex solver and a branch-and-price algorithm, respectively. Our tests on various scenarios revealed that the branch-and-price algorithm performs faster than the Cplex solution for the arc-based model. Additionally, we conducted a sensitivity analysis to determine the most cost-effective electric bus type, taking into account different bus features and how changes in battery capacity and travel range affect the optimal solution.