A constructive hybrid algorithm for crew pairing optimization

Broderick Crawford, Carlos Castro, Eric Monfroy

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations


In this paper, we focus on the resolution of Crew Pairing Optimization problem that is very visible and economically significant. Its objective is to find the best schedule, i.e., a collection of crew rotations such that each airline flight is covered by exactly one rotation and the costs are reduced to the minimum. We try to solve it with Ant Colony Optimization algorithms and Hybridizations of Ant Colony Optimization with Constraint Programming techniques. We give an illustrative example about the difficulty of pure Ant Algorithms solving strongly constrained problems. Therefore, we explore the addition of Constraint Programming mechanisms in the construction phase of the ants, so they can complete their solutions. Computational results solving some test instances of Airline Flight Crew Scheduling taken from NorthWest Airlines database are presented showing the advantages of using this kind of hybridization.

Original languageEnglish
Title of host publicationArtificial Intelligence
Subtitle of host publicationMethodology, Systems, and Applications - 12th International Conference, AIMSA 2006, Proceedings
PublisherSpringer Verlag
Number of pages11
ISBN (Print)3540409300, 9783540409304
StatePublished - 2006
Event12th International Conference on Artificial Intelligence: Methodology, Systems, and Applications, AIMSA 2006 - Varna, Bulgaria
Duration: 12 Sep 200615 Sep 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4183 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Conference on Artificial Intelligence: Methodology, Systems, and Applications, AIMSA 2006


  • Ant Colony Optimization
  • Constraint Programming
  • Crew Pairing Optimization
  • Hybrid Algorithm
  • Set Partitioning Problem


Dive into the research topics of 'A constructive hybrid algorithm for crew pairing optimization'. Together they form a unique fingerprint.

Cite this