Crew pairing optimization based on CLP

The crew pairing optimization problem is faced by airline companies as an intensive part of the crew scheduling process. Crew scheduling is the assignment of cockpit and cabin crews to the ight legs that a company has to carry out during a predened period of time. Due to the signicant contribution of the crew cost to the overall operating cost of an airline company, the automation of the crew scheduling proce-dure is highly desirable. However, the crew pairing optimization subproblem of crew scheduling is extremely dicult and combinatorial in nature due to the large number and complexity of the involved constraints. The requirement for optimality makes it even more dicult. Many attempts have been made in the past 40 years to tackle the crew pairing optimization problem using methods from Operations Research. In this paper, an approach based on pure Constraint Logic Programming is presented, which leads to an elegant and exible modeling of the problem. The whole process is divided into three distinct phases, the job construction, the pairing construction and a set partitioning problem. All three phases are viewed as constraint satisfac-tion problems. A prototype system that has been built using the Constraint Logi