### Skapa referens, olika format (klipp och klistra)

**Harvard**

Potter, D. (2008) *An implementation of a constraint branching algorithm for optimally solving airline crew pairing problems*. : Chalmers University of Technology

** BibTeX **

@mastersthesis{

Potter2008,

author={Potter, Douglas},

title={An implementation of a constraint branching algorithm for optimally solving airline crew pairing problems},

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.<p/>
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.},

publisher={Institutionen för matematiska vetenskaper, matematik, Chalmers tekniska högskola},

year={2008},

keywords={optimization, crew scheduling, mathematical model, branch-and-price},

note={60},

}

** RefWorks **

RT Generic

SR Electronic

ID 82068

A1 Potter, Douglas

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

YR 2008

AB 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.<p/>
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.

PB Institutionen för matematiska vetenskaper, matematik, Chalmers tekniska högskola,

LA eng

LK http://www.chalmers.se/en/sections/education/current_students/programmespecific/engineering-mathematics/master-thesis-reports/2008/downloadFile/attachedFile_9_f0/2008-11.pdf?nocache=1228124596.82

OL 30