Full paper
Full paper

Column Generation with a Rule Modelling Language for Airline Crew Pairing

Curt Hjorring
Jesper Hansen


One important problem in the planning process is the construction of pairings, or legal lines of work, for anonymous crew members. Experimentation has shown that (delayed) column generation can produce high quality solutions, but there are difficulties in implementing a column generation method in a production environment. The rules that define legal lines of work are often complex, and in the past have been hard coded into the column generator, albeit with some parameters. European carriers often wish to modify rules, and these modifications sometimes require more than just a parameter change.

One solution to the problem of changing rules is to write a rule system that allows the airline carriers to easily write and maintain their own rules. These rule systems often present a black box interface to client applications, i.e. we can only ask the rule system if a partial/complete pairing is legal, and the system only returns a simple yes/no. This limited interface causes problems with a column generation approach. In this paper we show how these difficulties can be overcome with a pricing subproblem based on a duty network and a k-shortest path algorithm. Results based on production problems are given.