3 Presentations

• 
  10:30 AM - 10:55 AM

  Alternating Lagrangian decomposition for integrated airline crew scheduling problem

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

  Abstract: The airline crew scheduling problem involves determining schedules for airline crew members such that all the scheduled flights over a planning horizon (usually a month) are covered and the constraints are satisfied. Because of its complexity, this problem is usually solved sequentially in two main steps: the crew pairing followed by the crew assignment. However, finding a globally optimal solution via the sequential approach may be impossible because the decision domain of the crew assignment problem is reduced by decisions made in the pairing problem. This study considers the crew scheduling problem in a personalized context where each pilot and copilot requests a set of preferred flights and vacations each month. We propose a model that completely integrates the crew pairing and personalized assignment problems to generate personalized monthly schedules for a given set of pilots and copilots simultaneously in a single optimization step. The model keeps the pairings in the two problems as similar as possible so that the propagation of perturbations arising during the operation is reduced. We develop an integrated algorithm that combines alternating Lagrangian decomposition, column generation, and dynamic constraint aggregation. We conduct computational experiments on a set of real instances from a major US carrier. Our integrated approach produces significant cost savings and better satisfaction of crew preferences compared with the traditional sequential approach.

  keywords: Integrated crew scheduling problem; column generation; dynamic constraint aggregation; alternating Lagrangian decomposition
• 
  10:55 AM - 11:20 AM

  Integrated bus driver rostering and days off scheduling problem

  • Safae Er-Rbib, presenter, GERAD, Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  We consider the integrated problem of assigning duties and days off to bus drivers rosters in order to balance as much as possible the weekly working time among the rosters while satisfying various working rules concerning mostly the rest period between two working days.
  We model this problem as an integer linear program with big M constraints, then we apply the reformulation-linearization technique to derive a tight and equivalent linear model, we report computational results obtained on real-world instances.
• 
  11:20 AM - 11:45 AM

  The air crew pairing problem with language constraints

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

  We propose an efficient solution method for the CPPLC, a variant of the air crew pairing problem with additional constraints limiting the amount of work performed in any language. We show that fewer language constraints are violated in the schedules when the CPPLC is used, compared to traditional approaches.