Introduction
The Lufthansa Flight Training (LFT) GmbH is a 100% subsidiary of Deutsche Lufthansa AG, which takes care of the training of cockpit and cabin crew. Practical training in a flight simulator is part of a pilot’s training.
Currently, over 150 airlines from all over the world train at five locations of the LFT Group. There are 45 Cockpit Simulators as either Full-Flight Simulators or Flat Panel Trainers that are available at these locations. The LFT operated Cockpit Simulators offer differing aircraft types. Thus, 13 simulator families and a total of 23 simulator groups of similar training devices can be distinguished. The simulators are available around the clock, seven days a week.
The Problem
What was being sought is a long-term training schedule, which maximizes the capacity and guarantees a high level of customer satisfaction. To this end, the development of an IT-supported scene-planning tool was the focus. In order to determine an optimum schedule, the requested training volume, the hit-rate of the customer restrictions and the revenue optimum would have to be considered.
The airlines book a number of trainings, which vary with regards to training sequences and times – some formulated as hard, and some as soft, constraints. One requirement, for example, is that between two trainings of one pilot crew there is a rest period of between 16 and 24 hours – under no circumstances less than 16 hours or more than 24.
In addition, the customer requested that this rest period be exactly 20 hours. The constraints resulting from this are referred to as hard (16 – 24 hours) and soft (20 hours). This restricts the possible training allocations. There are other individual customer requests. One request, for example, could be a preference for a particular weekday.
The training schedule is usually scheduled three months in advance and includes up to half a dozen simulators at differing locations at the same time. Prior to finding this solution, a planner needed several days to develop a custom-made schedule. In addition, it took considerable extra work to develop a statement as to how well the schedule solved all the soft conditions.
Solution
A solution had to be found in a short amount of time. The performance market leader came just in time. With the help of Gurobi’s extremely good solution times, planners perform the process several times, and also with different criteria. The software needs to produce a good solution within five minutes. Proven optimality is not possible in this short time, but we needed extremely good solutions for the results to be acceptable. The heuristics in Gurobi do their job very well and provide exactly these solutions. Also, the model is so big that it doesn’t fit in the memory.
We decided on an approach similar to column generation. The variables stored in the columns of the constraint matrix are thereby added only gradually to the model. Often, a smaller model of a subset of the variables is sufficient to deliver high-quality solutions.
This technique is made possible and is effective because Gurobi allows an extremely good warm start, meaning we have not had to begin from scratch every time.
Results
The solution to such a complex scheduling problem could not be quickly integrated into the existing processes of the company without additional planning. For example, processes had to be formalized, a model needed to be set up, and non-optimization experts had to be able to work easily and comfortably with the finished software.
The operations research specialists at ORCONOMY took responsibility for this part. A team of five optimizers have been focused on developing an interactive application for the simulator scheduler. Both the graphical interface and the integration with the existing systems were important.
This application has been finished and has been used by LFT with great success since the beginning of 2014. In addition to the automatically created schedules designed to optimize revenue, the quality of the schedules and the customer’s requests can also be analyzed in detail.
Lufthansa Flight Training GmbH
150 airline customers from all over the world
5 different locations with simulators
8 planners look after approximately 40 simulators
ORCONOMY GmbH
founded in 2009 – currently 15 employees
provides innovative and precise solutions for complex planning problems
delivers solutions: advice, software, implementation and support
highly qualified specialists for mathematical optimization technology
the finished solution for LFT also used a modelling tool (Optimisation.Framework) and the Rapid Application Framework Ceus from ORCONOMY GmbH
