In English

An implementation of a constraint branching algorithm for optimally solving airline crew pairing problems

Douglas Potter
Göteborg : Chalmers tekniska högskola, 2008. 60 s.
[Examensarbete på avancerad nivå]

Competition in the airline industry depends greatly on how efficiently crews are scheduled. Scheduling problems can be modeled as integer programs which can be solved exactly using branch-and-price methods. However, in practice, in order to find a good schedule expediently, the branch-and-price tree is often only partially explored. A constraint branching heuristic called connection fixing often selects branches containing optimal or near-optimal solutions. This thesis investigates utilizing connection fixing in a branchand-price algorithm to exactly solve airline crew scheduling problems.

We present a mathematical model for optimizing airline crew scheduling that is suitable for the branch-and-price algorithm. Then we present the branch-and-price method for solving integer programs, the connection fixing heuristic, and how this can be integrated into a branch-and-price method. Finally, we evaluate these ideas by implementing a branch-and-price system using connection fixing and use this system to solve exactly several small and medium sized crew scheduling problems. The numerical results suggest that the branch-and-price method with connection fixing is a promising method for exactly solving large-scale crew scheduling problems.

Nyckelord: optimization, crew scheduling, mathematical model, branch-and-price

Publikationen registrerades 2008-12-18. Den ändrades senast 2013-04-04

CPL ID: 82068

Detta är en tjänst från Chalmers bibliotek