Program > By author > Meunier Frédéric

Once an airline has chosen the set of flights it operates, it must solve two problems. The Aircraft Routing Problem selects the sequences of flights or rotations operated by airplanes, and the Crew Pairing Problem selects the rotations operated by crews in order to minimize operational costs, while ensuring that each flight is covered by one aircraft and one crew, and that rotations respect aircraft maintenance and crew working rules. These two problems are usually solved sequentially, but as the feasible crew rotations depend on feasible aircraft rotations, the sequential approach leads to non-optimal solutions. This talk focuses on algorithms for Air France Integrated Aircraft Routing and Crew Pairing Problem. Column generation based matheuristics have been developed for the Integrated Problem during the last decade. The column generation subproblem builds feasible rotations, and happens to be a non-linear Resource Constrained Shortest Path Problem (RCSPP). Due to the complexity of the new European IR-OPS crew working rules, the usual RCSPP algorithms do not enable to solve exactly or approximately the subproblem in reasonable time. We introduce new bounds to discard partial solutions in the RCSPP, which enable to solve all Air France subproblem instances in at most a few seconds. We design a new cutting plane approach to transfer information between the Aircraft Routing and the Crew Pairing problems. Finally, we enforce robustness of the solution with respect to delay propagation through probabilistic constraints. Numerical experiments prove the efficiency of the approach on Air France instances.