Shift planning under delay uncertainty at air France: A vehicle-scheduling problem with outsourcing

Airlines must operate many jobs in airports, such as passenger check-in or runway tasks. In airlines' hubs, airlines generally choose to perform these jobs with their own agents. Shift planning aims at building the sequences of jobs operated by the airline agents and has been widely studied given its impact on operating costs. The impact of delayed flights is generally not taken into account despite the propagation of flight delays along these sequences: If a flight is late, then the agents doing the corresponding jobs are delayed, and may arrive late to their next jobs and delay the corresponding flights. Since delay costs are much higher than the costs of outsourcing jobs, if the agent who is supposed to operate a job is still working elsewhere when the job begins, then airlines tend to outsource the job to their own dedicated team or to a third party. We introduce a stochastic version of the shift-planning problem that takes into account outsourcing costs due to delay. It can be seen as a natural stochastic generalization of the vehicle-scheduling problem in which delayed jobs are outsourced. We propose a column-generation approach to solve it, whose key element is the pricing subproblem algorithm, modeled as a stochastic resource-constrained shortest-path problem. Numerical results on Air France industrial instances show the benefits of using our stochastic version of the shift-planning problem and the efficiency of the solution method. Moving to the stochastic version enables Air France to reduce total operating costs by 3.5%-4.8% on instances with more than 200 jobs, and our algorithm can solve to near optimality instances with up to 400 jobs.