3 Presentations

• 
  03:30 PM - 03:55 PM

  Solving the Crew Rostering Problem With Reinforcement Learning

  • Philippe Racette, presenter, Polytechnique Montréal

  We present a new framework for the resolution of the crew rostering problem for pilots with machine learning. A sequential assignment procedure whose arc costs are computed using a policy over state-action pairs is implemented to generate initial solutions. The policy is based on parameters learned through a reinforcement learning algorithm adapted from a well-established evolutionary strategy (CMA-ES). The initial solutions obtained are passed to the GENCOL-DCA optimization solver and improved through branch-and-price using column generation with dynamic constraint aggregation.

  Our method is tested on several instances of varying sizes derived from data provided by a major North American airline carrier. Results show significantly reduced computational time for similar solution quality when the improved solutions are compared to those obtained from GENCOL-DCA without initial solutions.

• 
  03:55 PM - 04:20 PM

  Using deep learning to speed up a branch-and-price algorithm for cabin crew rostering

  • Frédéric Quesnel, presenter, GERAD
  • Alice Wu, Polytechnique Montréal

  Airlines go to great lengths to create satisfactory schedules for cabin crews. In addition to increasing productivity, this decreases the staff turnover rate. Monthly crew schedules are created by solving the crew rostering problem, which assigns a set of pairings (sequence of flights, repositioning, connections, rest, forming one or more working days) to crews to form a schedule that maximizes total satisfaction. This problem is usually solved using a branch-and-price algorithm with one subproblem per crew member. The current algorithms considers all pairings in each subproblem, which significantly slows down the resolution.
  We propose a partial pricing method that only considers promising pairings in each subproblem. The selection of pairings to include in each subproblem is performed using deep neural network, trained on historical data. We test our method on several large instances from an international airline. Our method produces solution of similar quality as those obtained using the standard branch-and-evaluate algorithm, in less than half the time.

• 
  04:20 PM - 04:45 PM

  Imitation learning to speed up solving crew pairing problems

  • Pierre Pereira, presenter, Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique
  • Frédéric Quesnel, Polytechnique Montréal

  Pairing problems are solved every month by airlines companies to compute the schedules of their pilots. It is a hard problem that needs to be solved by a diving branch and price algorithm.

  The best branching strategy known is the strong branching heuristic, which usually produces the closest to optimal solutions. But the computational time is so huge that it can't be used in practice. On the other hand, branching on the closest-to-integer variable produces good solutions with little computational time.

  Our goal is to learn a branching heuristic based on strong branching decisions. Since we are doing imitation learning, our heuristic is learnt in a supervised way. To do this, we collected branching decisions and some features on the nodes during many B&P instances. Different models are trained offline, and then evaluated by the GENCOL solver. To avoid unnecessary evaluations, we measure different metrics that can help select the best models beforehand.

  While we still have not been able to beat the fractional value, we showed that this fractional value is the most important feature (among the ones we collected) to approximate the strong branching decisions.