Airline crew scheduling during tracking | Jesper Holm
| | Abstract | This thesis investigates airline crew scheduling, which covers the problem of assigning crew to planned departures. The problem is often subdivided into several phases: The pairing phase, the assignment phase, the tracking phase and the day-to-day phase. In this thesis, the tracking phase has been the main focus. An existing system developed by Scandinavian IT Group has been used as a starting point for the developed
software.
The properties of the tracking phase make it desirable to construct individual work shifts for each crew. This approach is in contrast to the usual approaches taken during the assignment and pairing phases. Hence, a set of individual work shifts is constructed for each crew to be considered. From each set, a work shift for each crew to man is chosen using a Set Covering formulation.
The construction of work shifts is done by enumerating a subset of all possible work shifts by using heuristics or by using an existing generator developed by Scandinavian IT Group. The resulting Set Covering Problem is solved using Simulated Annealing.
A total of 16 ``real-life'' problems are considered. The smallest contains slightly more than 200 crew and 150 open flights and the largest contains just above 600 crew and 900 open flights. Using the developed heuristics around 90% of the planned departures were covered. In comparison, the existing heuristic resulted in a coverage around 60%. | | Keywords | Airline crew scheduling, Simulated Annealing, Combinatorial Optimization, Heuristics | | Type | Master's thesis [Academic thesis] | | Year | 2002 | | Publisher | Informatics and Mathematical Modelling, Technical University of Denmark, DTU | | Address | Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby | | Series | IMM-THESIS | | ISBN / ISSN | 2002-15 | | Electronic version(s) | [pdf] | | BibTeX data | [bibtex] | | IMM Group(s) | Operations Research |
|