An IP Framework for the Crew Pairing Problem Using Subsequence Generation

Matias Sevel Rasmussen, Richard Martin Lusby, David Ryan, Jesper Larsen

    Research output: Book/ReportReportResearch

    255 Downloads (Pure)

    Abstract

    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
    Publication statusPublished - 2011
    SeriesDTU Management 2011
    Number10

    Keywords

    • subsequence generation
    • integer programming
    • set partitioning
    • airline crew pairing

    Cite this