An application of airline crew scheduling by using a column generation approach; [Sütun oluçturma yaklaçimi île bîr havayolu ekîp çîzelgeleme uygulamasi]
No Thumbnail Available
Date
2009
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Crew scheduling problem is one of the hardest and most comprehensive problems encountered in airline planning. In crew scheduling problem, it is aimed to find the minimum costly set of pairings in that each flight leg is covered at least by one crew pairing. In this study, a column generation approach that is commonly used in crew scheduling literature in which variables are dynamically generated, is used to solve the problem. The master problem is formulated as a set covering problem while the subproblem is formulated as a shortest path problem. Initial pairings which are sufficient to obtain a feasible solution, are produced using a linear programming model. The master problem, sub-problem and the model used to generate initial pairings are encoded by GAMS optimization program in an integrated manner and this integrated model is solved iteratively. The algorithm is applied to a private airline company's crew scheduling problem using real data and optimal crew schedules are obtained.
Description
Keywords
Air transportation , Linearization , Optimization , Airline crew scheduling , Airline planning , Column generation algorithm , Column generation approaches , Crew pairing problem , Crew scheduling problems , Feasible solutions , Integrated models , Linear programming models , Optimization programs , Set covering problem , Shortest path problems , Problem solving