Humboldt-Universität zu Berlin, Institut für Informatik
Lehrstuhl für Algorithmen und Komplexität

Kombinatorische Optimierungsverfahren
für die Flugdienstplanung

Dissertation

Thomas Emden-Weinert

18. April 1998


Abstract

We report about an experimental study of local search optimization algorithms for the airline pairing problem using a run-cutting formulation. Computational results are reported for some real-world short-haul test problems with up to 4600 flights per month. In particular, we evaluate the relative performance of simulated annealing, modified versions of the waterlevel algorithms proposed by Dueck [Due93], an elementary tabu search, and a GRASP approach. We find that the waterlevel algorithms compare well with simulated annealing and both improve on mere improvement heuristics by about 40%. Tabu search and GRASP do not yield competitive results here. Simulated annealing and the waterlevel algorithms also compare favourably with LP-bounds for a SET PARTITIONING formulation with knapsack constraints containing up to 3.9 million columns. A clustering parallelization of simulated annealing on a GigaCluster PowerPlus parallel computer exhibits an excellent speed-up.


Keywords: airline crew scheduling, simulated annealing, waterlevel algorithms, tabu search, pairing problem, set partitioning, parallel computing


Download PostScript document:


Thomas Emden-Weinert created 1999/1/29.