Alternative Pricing in Column Generation for Airline Crew Rostering

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/255713
Download file(s):
File Description SizeFormat 
255713.pdfFulltext660.17 kBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Alternative Pricing in Column Generation for Airline Crew Rostering
Authors: Curry, Emily
Abstract: In airline crew rostering, the objective is to create personalized schedules, i.e., rosters, for a set of crew members. Because of the large number of possible rosters that could be formed, the problem is solved using column generation, where each column corresponds to a specific roster. The pricing problem, which is the problem studied in this thesis, is then defined as to find legal rosters with the potential of improving the current solution. Since the rules and regulations regarding rosters vary between airlines, we have chosen to treat the pricing problem as a black-box optimization problem. Three different methods for solving the black-box pricing problem have been implemented. The first method uses binary particle swarm optimization (BPSO) to search for new rosters. The other two methods use surrogate modeling to fit a nonlinear surrogate function to a set of sampled rosters using radial basis functions. The surrogate function was then either linearly approximated, so that a shortest path problem could be set up and solved, or solved heuristically by a BPSO method. The three methods have been evaluated on five real-world test cases. For each test case, a large number of different pricing problems are solved. Our comparison of the methods’ performance shows that the method using BPSO performed the best, followed by the surrogate modeling approach without the linear approximation.
Keywords: Grundläggande vetenskaper;Matematik;Basic Sciences;Mathematics
Issue Date: 2018
Publisher: Chalmers tekniska högskola / Institutionen för matematiska vetenskaper
Chalmers University of Technology / Department of Mathematical Sciences
URI: https://hdl.handle.net/20.500.12380/255713
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.