Optimization of Hierarchical Decisions in Airline Manpower Planning
Typ
Examensarbete för masterexamen
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2020
Författare
Eriksson, Frida
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.