Flight graph based genetic algorithm for crew scheduling in airlines

Crew scheduling is an NP-hard constrained combinatorial optimization problem, very important for the airline industry [G. Yu (Ed.), Operations Research in Airline Industry, Kluwer Academic Publishers, Dordrecht, 1998]. We solve this problem using a genetic algorithm applied to a flight graph representation that represents several problem-specific constraints, unlike previous attempts [D. Levine, Application of a hybrid genetic algorithm to airline crew scheduling, Ph.D. dissertation, Computer Science Department, IIT, Chicago, USA, 1995; J.E. Beasley, P.C. Chu, A genetic algorithm for the set covering problem, fur. J. Oper. Res. 94 (1996) 392-404; P.C. Chu, J.E. Beasley, A genetic algorithm for the set partitioning problem, Technical report, Imperial College, UK, 1995]. In extensive experimental comparisons on flight data of several airlines, the new approach performed better than other approaches in 17 out of 24 data sets. (C) 2001 Elsevier Science Inc. All rights reserved.