An IP Framework for the Crew Pairing Problem Using Subsequence Generation

Publication: ResearchReport – Annual report year: 2011

View graph of relations

In this paper we consider an important problem for the airline industry. The widely studied crew pairing problem is typically formulated as a set partitioning problem and solved using the branch-and-price methodology. Here we develop a new integer programming framework, based on the concept of subsequence generation, for solving the set partitioning formulation. In subsequence generation one restricts the number of permitted subsequent flights, that a crew member can turn to after completing any particular flight. By restricting the number of subsequences, the number of pairings in the problem decreases. The aim is then to dynamically add attractive subsequences to the problem, thereby increasing the number of possible pairings and improving the solution quality. Encouraging results are obtained on 19 real-life instances supplied by Air New Zealand and show that the described methodology is a viable alternative to column generation.
Original languageEnglish
Place of PublicationKgs. Lyngby
PublisherDTU Management
Number of pages19
StatePublished - 2011
SeriesDTU Management 2011


  • subsequence generation, integer programming, set partitioning, airline crew pairing
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

Download statistics

No data available

ID: 5760446