An implementation of a constraint branching algorithm for optimally solving airline crew pairing problems
Examensarbete för masterexamen
Please use this identifier to cite or link to this item:
There are no files associated with this item.
|Type: ||Examensarbete för masterexamen|
|Title: ||An implementation of a constraint branching algorithm for optimally solving airline crew pairing problems|
|Authors: ||Potter, Douglas|
|Abstract: ||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.|
|Keywords: ||Optimeringslära, systemteori;Optimization, systems theory|
|Issue Date: ||2008|
|Publisher: ||Chalmers tekniska högskola / Institutionen för matematiska vetenskaper|
Chalmers University of Technology / Department of Mathematical Sciences
|Collection:||Examensarbeten för masterexamen // Master Theses|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.