Share from the GERAD Journals by Jean-François Cordeau, Goran Stojković, François Soumis, and Jacques Desrosiers Given a set of flight legs to be flown by a single type of aircraft, the simultaneous aircraft routing and crew scheduling problem consists of determining a minimum-cost set of aircraft routes and crew pairings such that each flight leg is covered by one aircraft and one crew, and side constraints are satisfied. While some side constraints such as maximum flight time and maintenance requirements involve only crews or aircraft, linking constraints impose minimum connection times for crews that depend on aircraft connections. To handle these linking constraints, a solution approach based on Benders decomposition is proposed. The solution process iterates between a master problem which solves the aircraft routing problem, and a subproblem which solves the crew pairing problem. Because of their particular structure, both of these problems are themselves decomposed and solved by column generation. A heuristic branch-and-bound method is used to compute integer solutions. On a set of test instances based on data provided by an airline, the integrated approach produced significant cost savings in comparison with the sequential planning process commonly used in practice. The largest instance solved contains more than 500 flight legs over a three-day period. Read More Keywords: air transportation; integer programming; multi-commodity network flow; Benders decomposition; Dantzig-Wolfe decomposition; column generation.