An implementation of a constraint branching algorithm for optimally solving airline crew pairing problems
| dc.contributor.author | Potter, Douglas | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för matematiska vetenskaper | sv |
| dc.contributor.department | Chalmers University of Technology / Department of Mathematical Sciences | en |
| dc.date.accessioned | 2019-07-03T12:12:35Z | |
| dc.date.available | 2019-07-03T12:12:35Z | |
| dc.date.issued | 2008 | |
| dc.description.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. | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12380/82068 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | PhysicsChemistryMaths | |
| dc.subject | Optimeringslära, systemteori | |
| dc.subject | Optimization, systems theory | |
| dc.title | An implementation of a constraint branching algorithm for optimally solving airline crew pairing problems | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master Thesis | en |
| dc.type.uppsok | H |