CREW PAIRING AT AIR-FRANCE

In the airline industry, crew schedules consist of a number of pairing s, These are round trips originating and terminating at the same crew home base composed of legal work days, called duties, separated by res t periods, The purpose of the airline crew pairing problem is to gener ate a set of minimal cost crew pairings covering all flight legs, The set of pairings must satisfy all the rules in the work convention and all the appropriate air traffic regulations, The resulting constraints can affect duty construction, may restrict each pairing, or be impose d on the overall crew schedule. The pairing problem is formulated as a n integer, nonlinear multi-commodity network flow problem with additio nal resource variables. Nonlinearities occur in the objective function as well as in a large subset of constraints. A branch-and-bound algor ithm based on an extension of the Dantzig-Wolfe decomposition principl e is used to solve this model. The master problem becomes a Set Partit ioning type model, as in the classical formulation, while pairings are generated using resource constrained shortest path subproblems, This primal approach implicitly considers all feasible pairings and also pr ovides the optimality gap value on a feasible solution. A nice feature of this decomposition process is that it isolates all nonlinear aspec ts of the proposed multi-commodity model in the subproblems which are solved by means of a specialized dynamic programming algorithm. We pre sent the application and implementation of this approach at Air France . It is one of the first implementations of an optimal approach for a large airline carrier We have chosen a subproblem network representati on where the duties rather than the legs are on the arcs, This ensures feasibility relative to duty restrictions by definition, As opposed t o Lavoie, Minoux and Odier (1988), the nonlinear cost function is mode led without approximations. The computational experiments were conduct ed using actual Air France medium haul data. Even if the branch-and-bo und trees were not fully explored in all cases, the gaps certify that the computed solutions are within a fraction of one percentage point o f the optimality. Our results illustrate that our approach produced su bstantial improvements over solutions derived by the expert system in use at Air France, Their magnitude led to the eventual implementation of the approach.