4 Presentations

• 
  10:30 AM - 10:55 AM

  Combining Benders decomposition and column generation for integrated crew pairing and personalized crew assignment problems

  • Vahid Zeighami, presenter, Polytechnique Montréal

  The airline crew scheduling problem, because of its size and complexity, is usually solved in two phases: the crew pairing problem and the crew assignment problem. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. The crew pairing problem consists of determining a minimum-cost set of feasible pairings such that each flight is covered exactly once. In the crew assignment problem, the goal is to construct monthly schedules from these pairings for a given set of pilots and copilots independently, while respecting all the safety and collective agreement rules. However, this sequential approach may lead to significantly suboptimal solutions since it does not take into account the crew assignment constraints and objective during the building of the pairings. In this paper, first, we propose an extension of the crew pairing problem that incorporates pilot and copilot vacation requests at the crew pairing stage. Second, we introduce a model that completely integrates the crew pairing and crew assignment problems simultaneously for pilots and copilots. To solve this integrated problem, we develop a method that combines Benders decomposition and column generation. We conduct computational experiments with real-world data from a major US carrier.

• 
  10:55 AM - 11:20 AM

  Alternate Lagrangian decomposition for solving integrated crew pairing and crew assignment problems

  • Francois Soumis, presenter, GERAD et Polytechnique
  • Mohammed Saddoune, Polytechnique Montréal
  • Vahid Zeighami, Polytechnique Montréal

  We propose an integrated crew scheduling model to generate personalized monthly schedules for pilots and copilots simultaneously in a single optimization step where we keep the pairings in the two problems as similar as possible. We develop a method that combines Lagrangian relaxation, column generation, and dynamic constraint aggregation.

• 
  11:20 AM - 11:45 AM

  Airline crew assignment problem solved by branch and price using neighborhood

  • Salah-Eddine Makhloufi, presenter, GERAD
  • Francois Soumis, GERAD et Polytechnique
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  The crew assignment problem aims to cover, by crew members monthly covering blocks, every task of the pairings generated in a previous phase. A task represents a crew position on a pairing needing many crew members. We should also respect others constraints like government regulations and collective agreements.
  The crew assignment problem is a large scale problem solved by branch and price. Its solution is a very time consuming because of many reasons. The dual variable values have strong variation from iteration to iteration, thus, a large diversity of columns and a tailing-off effect. This produces a very fractional LP solution yielding a difficult branch and bound.
  To shorten the time solution process of a crew assignment software of a specific airline, we propose to use the solution of the cabin manager category (CM) (a small size problem) as set of reference paths (columns) to stabilize the solution of the largest category(FA). We will try to generate, as much as possible, columns in the neighbourhood of these paths. This will reduce the diversity of columns and the number of column generation iterations. It will also produce less fractional solutions and permit to converge rapidly to an integer solution.
  We experiment our work on instances with up to twenty five thousand pairing tasks and two thousand FA crew members.

• 
  11:45 AM - 12:10 PM

  Considering crew preferences in the airline crew pairings to improve rostering

  • Frédéric Quesnel, presenter, GERAD
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique

  Airline crew scheduling is usually divided in two steps : the crew pairing problem (CPP) and the crew rostering problems (CRP). While the goal of the CPP is to find feasible pairings at minimum cost, the CRP aims at finding a feasible schedule that satisfy as many employee preferences (preferred airlegs, vacations, etc.) as possible. The main challenge with this approach is that the pairings generated by the CPP may not be suitable for the objective of the CRP. In this talk, we propose a new variant of the CPP, called the CPP with complex features (CPPCF) that takes into account crew preferences in order to create pairings that are better suited for the CRP. Specifically, we identify six pairing features related to crew preferences that are beneficial for the CRP, and the objective function of the CPPCF rewards pairings that contain these features. The CPPCF is solved using a column generation algorithm in which new pairings are generated by solving subproblems consisting of constrained shortest path problems. For this purpose, we introduce a new type of path resources designed to handle complex features and we adapt the dominance rules accordingly. Finally, we present results showing the effectiveness of our method.