Alternative Pricing in Column Generation for Airline Crew Rostering

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.