A Fast Solution Strategy for the Crew Pairing Problem

Erdmann, Andreas and Nolte, Andreas and Rathert, Jonas and Schrader, Rainer (1999) A Fast Solution Strategy for the Crew Pairing Problem.
Technical Report p.


Airline crew scheduling is concerned with finding a minimum cost assignment of crews to flights while satisfying a number of rules like minimum rest time and maximal duty periods specified by union and governmental agreements. In this paper we describe a strategy for solving the Airline Crew Scheduling Problem approximately. The problem is modeled as a set partitioning problem. We employ a dynamic column generation approach that adds columns to each node of the branch-and-bound tree and present computational results of our algorithm on problem instances of a major European airline. We investigate the influences of various strategies like branching rules and column selection on the solution time and quality. Additionally, our results are compared to the results of a local search implementation on the same instances, thus yielding one of the first direct comparisons of the two approaches. The main point of this paper is that our algorithm is capable of solving large real world instances with a size typical for major carriers (up to 1400 flights) in the order of minutes on a usual PC. This opens up for the first time the possibility to integrate this approach in an interactive decision support environment.

Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: No citation data.
Uncontrolled Keywords: column generation crew pairing Dantzig-Wolfe decomposition set partitioning
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
Related URLs:
    Deposit Information:
    ZAIK Number: zaik1999-350
    Depositing User: Rainer Schrader
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 16 Jan 2012 14:19
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/350