Flight graph based genetic algorithm for crew scheduling in airlines

H. Timucin Ozdemir, Chilukuri K. Mohan

Research output: Contribution to journalArticle

36 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)165-173
Number of pages9
JournalInformation sciences
Volume133
Issue number3-4
DOIs
StatePublished - Apr 1 2001

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Flight graph based genetic algorithm for crew scheduling in airlines'. Together they form a unique fingerprint.

  • Cite this