Erdmann, Andreas and Nolte, Andreas and Rathert, Jonas and Schrader, Rainer
(1999)
A Fast Solution Strategy for the Crew Pairing Problem.
Technical Report
p.
Abstract
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 (Login required) |
