Ground staff shift planning under delay uncertainty at Air France

Airlines' ground staff agents perform many jobs at airports such as passengers check-in and planes cleaning. Shift planning aims at building the sequences of jobs operated by ground staff agents, so that all jobs are operated at minimum cost. Flight leg delays disrupt ground staff schedules, which leads to high additional costs. We therefore introduce a stochastic version of the shift planning problem that takes into account the cost of disruptions due to delay and a column generation approach to solve it. Column generation's key element is the algorithm for the pricing subproblem, which we model as a stochastic resource constrained shortest path problem. Numerical experiments on industrial instances have proven the relevance and efficiency of our approach. Including delay costs allows airlines to reduce the total operating costs by 3% to 5%, and column generation can solve to optimality instances with up to two hundred and fifty jobs, and one hundred scenarios.