PAROS - Parallel large scale automatic scheduling (April 1996 - December 1999)

The overall objective of the PAROS project was to improve and extend the use of automatic scheduling methods. An important target for the project was the crew pairing problem, where a new optimizer based on reduced cost column generation that can co-exist with Rave (Carmen's global rule and modeling language) was successfully introduced.

The project exceeded expectations in many ways. Lufthansa, the airline partner in the project, reported an increase in Crew Pairing performance of several hundred per cent, and also a significantly simplified planning process. Lufthansa's project representative noted: "We have removed all the manual steps. (...) We can now run major dated problems from scratch in one go." By the end of the project, Lufthansa could solve fully-dated variable crew problems with 45,000 legs in production. The final comment from the EU project officer, Michael Arentoft was: "Given the current state of the art in optimization and IT, you have achieved the maximum result possible."

Carmen introduced the first version of the new optimizer in the Crew Pairing product in 1999, and has further developed and extended it since then. PAROS provided an excellent method and basis for Carmen to develop today's industry leading pairing optimizer.

Links:
Carmen press release, December 1999: Paros finished - Lufthansa solves gigantic pairing problems

Column Generation with a Rule Modelling Language for Airline Crew Pairing (pdf)
Curt A. Hjorring and Jesper Hansen

Carmen Systems' Recent Advances in Crew Scheduling (pdf)
Curt A. Hjorring, Stefan E. Karisch, and Niklas Kohl

Article by our project partners: Parallel Integer Optimization for Crew Scheduling (postscript)
P. Alefragis, P. Sanders, T. Takkula and D. Wedelin Annals of Operations Research, 99(1), 141-166, 2000.