Location: MF 12

Title: Regularized column generation applied to crew scheduling

Crew scheduling is one of the most intricate challenges in operations research, especially within the aviation industry. It involves modeling complex interactions between pilots and cabin crew who must be synchronized in space and time, within a strictly regulated environment. This problem results in linear programs with millions of decision variables.

A promising approach uses the time-space graph representation of crew movements, which naturally leads to a Dantzig-Wolfe decomposition. This framework allows for column generation, efficiently solving the linear relaxation by iteratively adding promising flight pairings – that are represented by paths on the pilot’s graph. However, on large real-world instances, the algorithm often encounters degenerate steps that hinder progress toward optimality, which results in the tailing off effect.

In this talk, we explain how we can model the movement of a pilot on a time-space graph. Then, we cover the basics of the column generation algorithm and lastly, we explore the use of regularization techniques to mitigate degeneracy in column generation, ensuring faster convergence and more stable solutions.