Optimization of Hierarchical Decisions in Airline Manpower Planning
Examensarbete för masterexamen
Engineering mathematics and computational science (MPENM), MSc
This thesis work was performed at Jeppesen in Gothenburg, a company which develops and sells optimization software for scheduling to airlines. Among their different products, Manpower Planning has been the focus in this project. Airlines typically operate between many different airports, with several different aircraft types and a large number of crews. The major part of the manpower planning problem is that of deciding which and how many crews should be positioned at which base airport, operating which aircraft type. The promotion process differs between airlines. Typically, on the North American market, job vacancies are announced, whereafter crews make bids on the different vacancies. The allocation is then carried out according to several rules, such that, e.g., the most senior crews’ bids are prioritized. The allocation decisions may lead to deficiencies, meaning that for some fleets the crew demand exceeds the supply. By modifying the announced vacancies and by allowing staffing deviation on certain fleets, such deficiencies can be reduced, as well as the cost of simulator training and other tutoring needed for crews which are promoted. Such modifications are currently done manually. In this thesis, an optimization algorithm is developed for modifying vacancies and allowing staffing deviations. The problem itself is a black-box optimization problem, meaning that it is computationally expensive to evaluate, and that no analytical derivatives of the objective function exist. To solve such problems, a surrogate model can be built which approximates the true objective. The surrogate model implemented in this thesis is based on so-called Kriging, in which functions are modelled as realizations of Gaussian processes. In addition, due to the problem being high-dimensional, dimensionality reduction techniques are employed. The optimization algorithm is implemented in Python and communicates with the optimizer used at Jeppesen. Its performance and quality is tested on a benchmark problem as well as on real airline data. The allocation solutions found by the algorithm are associated with lower costs compared to manually constructed reference solutions.