The objective of the PARROT project was to provide efficient means to address the airline crew rostering problem. Given the traditional breakdown of crew scheduling into (i) crew pairing: identifying a sequence of duty periods from (a) home-base to (another) home-base, and (ii) crew rostering: assigning a set of pairings to each crew, usually on a monthly basis, the project concentrated on improving crew rostering quality and performance by applying a parallel approach, and developing on promising results in the combination of Operations Research (OR) techniques and Constraint Programming (CP). Identification of the optimal "mix" of techniques and the appropriate degree of parallelization for the characteristics of different airlines could result in approaches that are adaptable for small, medium and large-size companies.

For Carmen, one of the main objectives in the project was to gain knowledge in CP and its application in combination with OR techniques. Within the project we created a foundation for the exploitation of CP/OR methods in our product suite. For Carmen Crew Rostering, PARROT related results were incorporated in the product release in 2000 and showed performance improvements of up to 300% on some of our clients' data. CP has since then also been successfully applied in other products.

Links:
Carmen co-organized CP-AI-OR'00 - Second International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems March 8-10, 2000, Paderborn, Germany

Application of OR and CP Techniques in a Real World Crew Scheduling System (pdf)
Niklas Kohl

Constraint Programming Based Column Generation for Crew Assignment (pdf)
Torsten Fahle, Ulrich Junker, Stefan E. Karisch, Niklas Kohl, Meinolf Sellmann, and Bo Vaaben