||Rostering Optimization for Business Jet Airlines
Andersen, Alex Chizeck
||Larsen, Allan (Logistics & ITS, Department of Transport, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||The purpose of this thesis is to investigate how various optimization methods
from Operations Research can be applied to a Business Jet Airline Rostering
Problem (BJARP). Business Jet Airlines are sometimes also referred to as
Fractional Jets. Customers buy a share of an airplane, contrary to regular
commercial airlines, where they buy a ticket for a certain pre-scheduled flight.
Fractional shareholders (customers) can request customized flight(s) on a short
notice. The BJARP deals with the scheduling of pilots for expected demand
over a planning period, while satisfying various rules and regulations.
Methods guaranteeing optimal solutions are studied and developed in order to
achieve insight into the problem. The problem is modeled as a Binary Integer
Problem and as a Multi-Commodity Network Flow Problem. Both models
provide optimal results for very small problem sizes within a short time. Even for
medium-sized problems and definitely for any problem sizes derived from real-
life problems, the models cannot be solved. We demonstrate how the problem
sizes grow drastically.
Methods which do not guaranteeing optimal solutions are applied. A Simulated
Annealing heuristic is implemented. This provides quick and fairly good
solutions to problems of all sizes. The heuristic is not stable; the quality of each
solution can vary greatly. To counteract this, a Matheuristic method inspired
partly by Column Generation is applied. Instead of a ”usual” Sub Problem, the
Simulated Annealing is used when needed to generate new columns to be added
to the master problem. Due to formulation, columns are greatly intertwined -
choosing one column can easily rule out choosing many other columns and vice
versa. The consequence hereof is that the master problem is only solvable to
a certain problem size. A Column Management Scheme is utilized in order to
keep the size of the column pool under a certain limit. In effect this enables
solving real-life problem sizes.
Finally the performance of the Simulated Annealing and the Matheuristic
is compared. We show that even though the Matheuristic ”builds” on
Simulated Annealing, this solution approach is a great improvement with
regards to solution quality. When compared on stability issues, the Matheuristic
outperforms the Simulated Annealing.
The conclusion drawn from this project is that the use of a Matheuristic
approach makes it possible to solve real-life problem sizes with quite good
solution results. In future work, improving on the Simulated Annealing
embedded in the Matheuristic or exchanging it with another heuristic approach,
would most likely render even better results.
Keywords: business jet airline rostering problem; BJARP; business jet airline;
fractional management; fractional ownership; mathematical modeling; mathematical
programming; optimization; heuristic; matheuristic; hybrid heuristic; integer pro-
gramming; column generation; multi-commodity network flow; crew scheduling; crew
rostering; workforce scheduling
||Department of Transport, Technical University of Denmark, DTU : DK-2800 Kgs. Lyngby, Denmark
Creation date: 2009-01-08
Update date: 2012-12-19