Solving the Airline Crew Pairing Problem using Subsequence Generation

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

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    313 Downloads (Pure)

    Abstract

    Good and fast solutions to the airline crew pairing problem are highly interesting for the airline industry, as crew costs are the biggest expenditure after fuel for an airline. The crew pairing problem is typically modelled as a set partitioning problem and solved by column generation. However, the extremely large number of possible columns naturally has an impact on the solution time. In this work in progress we severely limit the number of allowed subsequent flights, i.e. the subsequences, thereby significantly decreasing the number of possible columns. Set partitioning problems with limited subsequence counts are known to be easier to solve, resulting in a decrease in solution time. The problem though, is that a small number of deep subsequences might be needed for an optimal or near-optimal solution and these might not have been included by the subsequence limitation. Therefore, we try to identify or generate such subsequences that potentially can improve the solution value.
    Original languageEnglish
    Title of host publicationProceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling
    PublisherQueen’s University Belfast
    Publication date2010
    Pages539-541
    ISBN (Print)08-538-9973-3
    Publication statusPublished - 2010
    Event8th International Conference on the Practice and Theory of Automated Timetabling - Belfast, Ireland
    Duration: 10 Aug 201013 Aug 2010
    Conference number: 8

    Conference

    Conference8th International Conference on the Practice and Theory of Automated Timetabling
    Number8
    Country/TerritoryIreland
    CityBelfast
    Period10/08/201013/08/2010

    Keywords

    • Limited subsequence
    • Airline crew pairing
    • Subsequence generation
    • Crew pairing
    • Column generation

    Fingerprint

    Dive into the research topics of 'Solving the Airline Crew Pairing Problem using Subsequence Generation'. Together they form a unique fingerprint.

    Cite this