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, Eur. 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.