Beta 1

Title Airline crew scheduling during tracking
Author Holm, Jesper
Supervisor Clausen, Jens (Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2002
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%.
Imprint Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU : DK-2800 Kgs. Lyngby, Denmark
Keywords Airline crew scheduling; Simulated Annealing; Combinatorial Optimization; Heuristics
Original PDF imm389.pdf (0.55 MB)
Admin Creation date: 2006-06-22    Update date: 2012-12-20    Source: dtu    ID: 58306    Original MXD